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
Quantized Training of Gradient Boosted Decision Trees
Watch later
Yu Shi, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Augmentations in Hypergraph Contrastive Learning: Fabricated and Generative
Watch later
Tianxin Wei, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
CLVR: Coordinate Linear Variance Reduction for Generalized Linear Programming
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
LIPS - Learning Industrial Physical Simulation benchmark suite
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Pragmatically Learning from Pedagogical Demonstrations in Multi-Goal Environments
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Optimal Comparator Adaptive Online Learning with Switching Cost
Watch later
Zhiyu Zhang, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%