Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum

Abstract

In the first part of this dissertation research, we develop a modular framework that can serve as a recipe for constructing and analyzing iterative algorithms for convex optimization. Specifically, our work casts optimization as iteratively playing a two-player zero-sum game. Many existing optimization algorithms including Frank-Wolfe and Nesterov's acceleration methods can be recovered from the game by pitting two online learners with appropriate strategies against each other. Furthermore, the sum of the weighted average regrets of the players in the game implies the convergence rate. As a result, our approach provides simple alternative proofs to these algorithms. Moreover, we demonstrate that our approach of optimization as iteratively playing a game leads to three new fast Frank-Wolfe-like algorithms for some constraint sets, which further shows that our framework is indeed generic, modular, and easy-to-use. In the second part, we develop a modular analysis of provable acceleration via Polyak's momentum for certain problems, which include solving the classical strongly quadratic convex problems, training a wide ReLU network under the neural tangent kernel regime, and training a deep linear network with an orthogonal initialization. We develop a meta theorem and show that when applying Polyak's momentum for these problems, the induced dynamics exhibit a form where we can directly apply our meta theorem. In the last part of the dissertation, we show another advantage of the use of Polyak's momentum -- it facilitates fast saddle point escape in smooth non-convex optimization. This result, together with those of the second part, sheds new light on Polyak's momentum in modern non-convex optimization and deep learning.

PhD dissertation at Georgia Tech. arXiv admin note: text overlap with arXiv:2010.01618

References in corpus (26)

• On the Convergence of Adam and Beyond
• The Loss Surfaces of Multilayer Networks
• Shake-Shake regularization
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• How to Escape Saddle Points Efficiently
• Recovery Guarantees for One-hidden-layer Neural Networks
• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• On the Computational Efficiency of Training Neural Networks
• Projection-free Online Learning
• The Power of Normalization: Faster Evasion of Saddle Points
• Understanding the Role of Momentum in Stochastic Gradient Methods
• Width Provably Matters in Optimization for Deep Linear Neural Networks
• Online Linear Optimization via Smoothing
• A Generic Approach for Escaping Saddle points
• Online to Offline Conversions, Universality and Adaptive Minibatch Sizes
• Optimization Theory for ReLU Neural Networks Trained with Normalization Layers
• Following the Leader and Fast Rates in Linear Prediction: Curved Constraint Sets and Other Regularities
• Over Parameterized Two-level Neural Networks Can Learn Near Optimal Feature Representations
• On the Global Convergence of Training Deep Linear ResNets
• Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Method
• Stochastic Heavy Ball
• Escaping Saddle Points Faster with Stochastic Momentum
• Spectral Frank-Wolfe Algorithm: Strict Complementarity and Linear Convergence
• Generalized Leverage Score Sampling for Neural Networks
• Global Convergence of Second-order Dynamics in Two-layer Neural Networks
• Conditional gradient methods for stochastically constrained convex minimization