Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction
Dec 6, 2021
Speakers
Dominik Stöger
Speaker · 0 followers
Mahdi Soltanolkotabi
Speaker · 1 follower
About
Recently there has been significant theoretical progress on understanding the convergence and generalization of gradient-based methods on non-convex losses with overparameterized models. Nevertheless, many aspects of optimization and generalization and in particular the critical role of small random initialization are not fully understood. In this paper, we take a step towards demystifying this role by proving that small random initialization followed by a few iterations of gradient descent behaves akin to popular spectral methods. We also show that this implicit spectral bias from small random initialization, which is provably more prominent for overparameterized models, also puts the gradient descent iterations on a particular trajectory towards solutions that are not only globally optimal but also generalize well. Concretely, we focus on the problem of reconstructing a low-rank matrix from a few measurements via a natural non-convex formulation. In this setting, we show that the trajectory of the gradient descent iterations from small random initialization can be approximately decomposed into three phases:(I) a spectral or alignment phase where we show that that the iterates have an implicit spectral bias akin to spectral initialization allowing us to show that at the end of this phase the column space of the iterates and the underlying low-rank matrix are sufficiently aligned, (II) a saddle avoidance/refinement phase where we show that the trajectory of the gradient iterates moves away from certain degenerate saddle points, and (III) a local refinement phase where we show that after avoiding the saddles the iterates converge quickly to the underlying low-rank matrix. Underlying our analysis are insights for the analysis of overparameterized non-convex optimization schemes that may have implications for computational problems beyond low-rank reconstruction.Recently there has been significant theoretical progress on understanding the convergence and generalization of gradient-based methods on non-convex losses with overparameterized models. Nevertheless, many aspects of optimization and generalization and in particular the critical role of small random initialization are not fully understood. In this paper, we take a step towards demystifying this role by proving that small random initialization followed by a few iterations of gradient descent beha…
Organizer
NeurIPS 2021
Account · 1.9k followers
About NeurIPS 2021
Neural Information Processing Systems (NeurIPS) is a multi-track machine learning and computational neuroscience conference that includes invited talks, demonstrations, symposia and oral and poster presentations of refereed papers. Following the conference, there are workshops which provide a less formal setting.
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
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
Watch later
Omar Khattab, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Two steps to risk sensitivity
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Exploiting Local Convergence of Quasi-Newton Methods Globally: Adaptive Sample Size Approach
Watch later
Qiujiang Jin, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Towards Sample-Efficient Overparameterized Meta-learning
Watch later
Yue Sun, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Fair Clustering Under a Bounded Cost
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Rethinking the Variational Interpretation of Accelerated Optimization Methods
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%