On The Convergence of Euler Discretization of Finite-Time Convergent Gradient Flows
arXiv:2010.02990
Abstract
In this study, we investigate the performance of two novel first-order optimization algorithms, namely the rescaled-gradient flow (RGF) and the signed-gradient flow (SGF). These algorithms are derived from the forward Euler discretization of finite-time convergent flows, comprised of non-Lipschitz dynamical systems, which locally converge to the minima of gradient-dominated functions. We first characterize the closeness between the continuous flows and the discretizations, then we proceed to present (linear) convergence guarantees of the discrete algorithms (in the general and the stochastic case). Furthermore, in cases where problem parameters remain unknown or exhibit non-uniformity, we further integrate the line-search strategy with RGF/SGF and provide convergence analysis in this setting. We then apply the proposed algorithms to academic examples and deep neural network training, our results show that our schemes demonstrate faster convergences against standard optimization alternatives.
References in corpus (12)
- Discontinuous Dynamical Systems: A tutorial on solutions, nonsmooth analysis, and stability
- A Variational Perspective on Accelerated Methods in Optimization
- Error Feedback Fixes SignSGD and other Gradient Compression Schemes
- signSGD with Majority Vote is Communication Efficient And Fault Tolerant
- Understanding the Acceleration Phenomenon via High-Resolution Differential Equations
- Direct Runge-Kutta Discretization Achieves Acceleration
- A Dynamical Systems Perspective on Nesterov Acceleration
- On Biased Compression for Distributed Learning
- Shadowing Properties of Optimization Algorithms
- Stochastic Sign Descent Methods: New Algorithms and Better Theory
- The Geometry of Sign Gradient Descent
- On Faster Convergence of Scaled Sign Gradient Descent