Identifying good directions to escape the NTK regime and efficiently learn low-degree plus sparse polynomials
Nov 28, 2022
Speakers
Eshaan Nichani
Speaker · 0 followers
Jason D. Lee
Speaker · 0 followers
About
A recent goal in the theory of deep learning is to identify how neural networks can escape the “lazy training,” or Neural Tangent Kernel (NTK) regime, where the network is coupled with its first order Taylor expansion at initialization. While the NTK is minimax optimal for learning dense polynomials (Ghorbani et al, 2021), it cannot learn features, and hence has poor sample complexity for learning many classes of functions including sparse polynomials. Recent works have thus aimed to identify settings where gradient based algorithms provably generalize better than the NTK. One such example is the “QuadNTK” approach of Bai Lee (2020), which analyzes the second-order term in the Taylor expansion. Bai Lee (2020) show that the second-order term can learn sparse polynomials efficiently; however, it sacrifices the ability to learn general dense polynomials.In this paper, we analyze how gradient descent on a two-layer neural network can escape the NTK regime by utilizing a spectral characterization of the NTK (Montanari Zhong, 2020) and building on the QuadNTK approach. We first expand upon the spectral analysis to identify “good” directions in parameter space in which we can move without harming generalization. Next, we show that a wide two-layer neural network can jointly use the NTK and QuadNTK to fit target functions consisting of a dense low-degree term and a sparse high-degree term – something neither the NTK nor the QuadNTK can do on their own. Finally, we construct a regularizer which encourages our parameter vector to move in the “good" directions, and show that gradient descent on the regularized loss will converge to a global minimizer, which also has low test error. This yields an end to end convergence and generalization guarantee with provable sample complexity improvement over both the NTK and QuadNTK on their own.A recent goal in the theory of deep learning is to identify how neural networks can escape the “lazy training,” or Neural Tangent Kernel (NTK) regime, where the network is coupled with its first order Taylor expansion at initialization. While the NTK is minimax optimal for learning dense polynomials (Ghorbani et al, 2021), it cannot learn features, and hence has poor sample complexity for learning many classes of functions including sparse polynomials. Recent works have thus aimed to identify se…
Organizer
NeurIPS 2022
Account · 952 followers
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
Opening remarks - Senior Program Chair
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
A generalist Agent
Watch later
Scott Reed, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
A Unified Framework for Deep Symbolic Regression
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Physical Data Model for Machine Learning Imaging Pipelines
Watch later
Marco Aversa, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Learning Tractable Probabilistic Models from Inconsistent Local Estimates
Watch later
Shasha Jin, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Modern Hopfield Networks
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%