Beyond lazy training for over-parameterized tensor decomposition

Xiang Wang; Chenwei Wu; Jason D. Lee; Tengyu Ma; Rong Ge

Beyond lazy training for over-parameterized tensor decomposition

Xiang Wang
, Chenwei Wu
, Jason D. Lee
, Tengyu Ma
, Rong Ge

Research output: Contribution to journal › Conference article › peer-review

Abstract

Over-parametrization is an important technique in training neural networks. In both theory and practice, training a larger network allows the optimization algorithm to avoid bad local optimal solutions. In this paper we study a closely related tensor decomposition problem: given an l-th order tensor in (R^d)?^l of rank r (where r « d), can variants of gradient descent find a rank m decomposition where m > r? We show that in a lazy training regime (similar to the NTK regime for neural networks) one needs at least m = ?(d^l-1), while a variant of gradient descent can find an approximate tensor when m = O^*(r^2.5l log d). Our results show that gradient descent on over-parametrized objective could go beyond the lazy training regime and utilize certain low-rank structure in the data.

Original language	American English
Journal	Advances in Neural Information Processing Systems
Volume	2020-December
State	Published - 2020
Event	34th Conference on Neural Information Processing Systems, NeurIPS 2020 - Virtual, Online Duration: Dec 6 2020 → Dec 12 2020

ASJC Scopus subject areas

Computer Networks and Communications
Information Systems
Signal Processing

Cite this

@article{7df37102a9e844cbb246df1a08e147a9,

title = "Beyond lazy training for over-parameterized tensor decomposition",

abstract = "Over-parametrization is an important technique in training neural networks. In both theory and practice, training a larger network allows the optimization algorithm to avoid bad local optimal solutions. In this paper we study a closely related tensor decomposition problem: given an l-th order tensor in (Rd)?l of rank r (where r « d), can variants of gradient descent find a rank m decomposition where m > r? We show that in a lazy training regime (similar to the NTK regime for neural networks) one needs at least m = ?(dl-1), while a variant of gradient descent can find an approximate tensor when m = O*(r2.5l log d). Our results show that gradient descent on over-parametrized objective could go beyond the lazy training regime and utilize certain low-rank structure in the data.",

author = "Xiang Wang and Chenwei Wu and Lee, \{Jason D.\} and Tengyu Ma and Rong Ge",

note = "Publisher Copyright: {\textcopyright} 2020 Neural information processing systems foundation. All rights reserved.; 34th Conference on Neural Information Processing Systems, NeurIPS 2020 ; Conference date: 06-12-2020 Through 12-12-2020",

year = "2020",

language = "American English",

volume = "2020-December",

journal = "Advances in Neural Information Processing Systems",

issn = "1049-5258",

publisher = "Neural information processing systems foundation",

}

TY - JOUR

T1 - Beyond lazy training for over-parameterized tensor decomposition

AU - Wang, Xiang

AU - Wu, Chenwei

AU - Lee, Jason D.

AU - Ma, Tengyu

AU - Ge, Rong

PY - 2020

Y1 - 2020

N2 - Over-parametrization is an important technique in training neural networks. In both theory and practice, training a larger network allows the optimization algorithm to avoid bad local optimal solutions. In this paper we study a closely related tensor decomposition problem: given an l-th order tensor in (Rd)?l of rank r (where r « d), can variants of gradient descent find a rank m decomposition where m > r? We show that in a lazy training regime (similar to the NTK regime for neural networks) one needs at least m = ?(dl-1), while a variant of gradient descent can find an approximate tensor when m = O*(r2.5l log d). Our results show that gradient descent on over-parametrized objective could go beyond the lazy training regime and utilize certain low-rank structure in the data.

AB - Over-parametrization is an important technique in training neural networks. In both theory and practice, training a larger network allows the optimization algorithm to avoid bad local optimal solutions. In this paper we study a closely related tensor decomposition problem: given an l-th order tensor in (Rd)?l of rank r (where r « d), can variants of gradient descent find a rank m decomposition where m > r? We show that in a lazy training regime (similar to the NTK regime for neural networks) one needs at least m = ?(dl-1), while a variant of gradient descent can find an approximate tensor when m = O*(r2.5l log d). Our results show that gradient descent on over-parametrized objective could go beyond the lazy training regime and utilize certain low-rank structure in the data.

UR - https://www.scopus.com/pages/publications/85108404512

UR - https://www.scopus.com/pages/publications/85108404512#tab=citedBy

M3 - Conference article

SN - 1049-5258

VL - 2020-December

JO - Advances in Neural Information Processing Systems

JF - Advances in Neural Information Processing Systems

T2 - 34th Conference on Neural Information Processing Systems, NeurIPS 2020

Y2 - 6 December 2020 through 12 December 2020

ER -

Beyond lazy training for over-parameterized tensor decomposition

Abstract

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this