# A Contraction Theory Approach to Optimization Algorithms from Acceleration Flows

arXiv: https://arxiv.org/abs/2105.08832 · HTML: https://mlsanity.com/paper/2105.08832/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 34 references that are in the map.
- First posted on arXiv 18 May 2021.

## Builds on (most cited first, 16 of 16)

- [A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights](https://mlsanity.com/paper/1503.01243/) (2015)
- [A Variational Perspective on Accelerated Methods in Optimization](https://mlsanity.com/paper/1603.04245/) (2016)
- [Understanding the Acceleration Phenomenon via High-Resolution Differential Equations](https://mlsanity.com/paper/1810.08907/) (2018)
- [A Dynamical Systems Perspective on Nesterov Acceleration](https://mlsanity.com/paper/1905.07436/) (2019)
- [Time-Varying Convex Optimization: Time-Structured Algorithms and Applications](https://mlsanity.com/paper/2006.08500/) (2020)
- [Conformal Symplectic and Relativistic Optimization](https://mlsanity.com/paper/1903.04100/) (2019)
- [A Lyapunov Analysis of Momentum Methods in Optimization](https://mlsanity.com/paper/1611.02635/) (2016)
- [Acceleration via Symplectic Discretization of High-Resolution Differential Equations](https://mlsanity.com/paper/1902.03694/) (2019)
- [Direct Runge-Kutta Discretization Achieves Acceleration](https://mlsanity.com/paper/1805.00521/) (2018)
- [Beyond Convexity -- Contraction and Global Convergence of Gradient Descent](https://mlsanity.com/paper/1806.06655/) (2018)
- [Contracting Implicit Recurrent Neural Networks: Stable Models with Improved Trainability](https://mlsanity.com/paper/1912.10402/) (2019)
- [Non-Euclidean Contraction Theory for Robust Nonlinear Stability](https://mlsanity.com/paper/2103.12263/) (2021)
- [Contraction and Robustness of Continuous Time Primal-Dual Dynamics](https://mlsanity.com/paper/1803.05975/) (2018)
- [Distributed and time-varying primal-dual dynamics via contraction analysis](https://mlsanity.com/paper/2003.12665/) (2020)
- [A continuous-time analysis of distributed stochastic gradient](https://mlsanity.com/paper/1812.10995/) (2018)
- [On Existence of Separable Contraction Metrics for Monotone Nonlinear Systems](https://mlsanity.com/paper/1704.02676/) (2017)

## Built on by (most cited first, 3 of 3)

- [Magnitude and Angle Dynamics in Training Single ReLU Neurons](https://mlsanity.com/paper/2209.13394/) (2022)
- [Accelerated forward-backward and Douglas-Rachford splitting dynamics](https://mlsanity.com/paper/2407.20620/) (2024)
- [Fusing Multiple Algorithms for Heterogeneous Online Learning](https://mlsanity.com/paper/2312.05432/) (2023)

## Abstract (arXiv)

Much recent interest has focused on the design of optimization algorithms from the discretization of an associated optimization flow, i.e., a system of differential equations (ODEs) whose trajectories solve an associated optimization problem. Such a design approach poses an important problem: how to find a principled methodology to design and discretize appropriate ODEs. This paper aims to provide a solution to this problem through the use of contraction theory. We first introduce general mathematical results that explain how contraction theory guarantees the stability of the implicit and explicit Euler integration methods. Then, we propose a novel system of ODEs, namely the Accelerated-Contracting-Nesterov flow, and use contraction theory to establish it is an optimization flow with exponential convergence rate, from which the linear convergence rate of its associated optimization algorithm is immediately established. Remarkably, a simple explicit Euler discretization of this flow corresponds to the Nesterov acceleration method. Finally, we present how our approach leads to performance guarantees in the design of optimization algorithms for time-varying optimization problems.