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.

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

References in corpus (86)

• Decoupled Weight Decay Regularization
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Deep Speech 2: End-to-End Speech Recognition in English and Mandarin
• On the Convergence of Adam and Beyond
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• The Loss Surfaces of Multilayer Networks
• AutoAugment: Learning Augmentation Policies from Data
• A Convergence Theory for Deep Learning via Over-Parameterization
• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• Train longer, generalize better: closing the generalization gap in large batch training of neural networks
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Shake-Shake regularization
• Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• On Lazy Training in Differentiable Programming
• How to Escape Saddle Points Efficiently
• Scaling Limits of Wide Neural Networks with Weight Sharing: Gaussian Process Behavior, Gradient Independence, and Neural Tangent Kernel Derivation
• The Mechanics of n-Player Differentiable Games
• Recovery Guarantees for One-hidden-layer Neural Networks
• A Lyapunov Analysis of Momentum Methods in Optimization
• On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization
• When Are Nonconvex Problems Not Scary?
• Online Learning: A Modern Introduction Using Convex Optimization
• A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks
• Gradient descent aligns the layers of deep linear networks
• Gradient Descent Maximizes the Margin of Homogeneous Neural Networks
• Efficient approaches for escaping higher order saddle points in non-convex optimization
• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets
• Unified Convergence Analysis of Stochastic Momentum Methods for Convex and Non-convex Optimization
• A geometric alternative to Nesterov's accelerated gradient descent
• The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle
• Understanding the Acceleration Phenomenon via High-Resolution Differential Equations
• Escaping Saddles with Stochastic Gradients
• On the Computational Efficiency of Training Neural Networks
• Depth Creates No Bad Local Minima
• Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernel
• An Analytical Formula of Population Gradient for two-layered ReLU network and its Applications in Convergence and Critical Point Analysis
• SGD Learns the Conjugate Kernel Class of the Network
• Identity Matters in Deep Learning
• Projection-free Online Learning
• The Power of Normalization: Faster Evasion of Saddle Points
• Implicit Regularization in Deep Learning May Not Be Explainable by Norms
• Neon2: Finding Local Minima via First-Order Oracles
• Gradient Descent Can Take Exponential Time to Escape Saddle Points
• The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods
• A Linearly Convergent Conditional Gradient Algorithm with Applications to Online and Stochastic Optimization
• Global optimality conditions for deep neural networks
• Quadratic Suffices for Over-parametrization via Matrix Chernoff Bound
• On the linearity of large non-linear models: when and why the tangent kernel is constant
• Classification vs regression in overparameterized regimes: Does the loss function matter?
• Understanding the Role of Momentum in Stochastic Gradient Methods
• Global Convergence of Adaptive Gradient Methods for An Over-parameterized Neural Network
• Width Provably Matters in Optimization for Deep Linear Neural Networks
• Parallel and Distributed Block-Coordinate Frank-Wolfe Algorithms
• Online Linear Optimization via Smoothing
• Gram-Gauss-Newton Method: Learning Overparameterized Neural Networks for Regression Problems
• Escaping Saddle Points in Constrained Optimization
• Why do Larger Models Generalize Better? A Theoretical Perspective via the XOR Problem
• A Generic Approach for Escaping Saddle points
• Accelerated Linear Convergence of Stochastic Momentum Methods in Wasserstein Distances
• Acceleration through Optimistic No-Regret Dynamics
• A Variant of Azuma's Inequality for Martingales with Subgaussian Tails
• A Distributed Frank-Wolfe Framework for Learning Low-Rank Matrices with the Trace Norm
• Negative Momentum for Improved Game Dynamics
• 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
• Stochastic Frank-Wolfe for Constrained Finite-Sum Minimization
• Curvature of Feasible Sets in Offline and Online Optimization
• Learning Distributions Generated by One-Layer ReLU Networks
• On the Global Convergence of Training Deep Linear ResNets
• Escaping Saddle Points Faster with Stochastic Momentum
• Stochastic Heavy Ball
• Memorizing Gaussians with no over-parameterizaion via gradient decent on neural networks
• Neural Networks and Polynomial Regression. Demystifying the Overparametrization Phenomena
• Spectral Frank-Wolfe Algorithm: Strict Complementarity and Linear Convergence
• Generalized Leverage Score Sampling for Neural Networks
• Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Method
• Global Convergence of Second-order Dynamics in Two-layer Neural Networks
• A new regret analysis for Adam-type algorithms
• On the Convergence of Projected-Gradient Methods with Low-Rank Projections for Smooth Convex Minimization over Trace-Norm Balls and Related Problems
• Parametrized Accelerated Methods Free of Condition Number
• Conditional gradient methods for stochastically constrained convex minimization
• On the Efficient Implementation of the Matrix Exponentiated Gradient Algorithm for Low-Rank Matrix Optimization