Beyond Convexity -- Contraction and Global Convergence of Gradient Descent

Abstract

This paper considers the analysis of continuous time gradient-based optimization algorithms through the lens of nonlinear contraction theory. It demonstrates that in the case of a time-invariant objective, most elementary results on gradient descent based on convexity can be replaced by much more general results based on contraction. In particular, gradient descent converges to a unique equilibrium if its dynamics are contracting in any metric, with convexity of the cost corresponding to the special case of contraction in the identity metric. More broadly, contraction analysis provides new insights for the case of geodesically-convex optimization, wherein non-convex problems in Euclidean space can be transformed to convex ones posed over a Riemannian manifold. In this case, natural gradient descent converges to a unique equilibrium if it is contracting in any metric, with geodesic convexity of the cost corresponding to contraction in the natural metric. New results using semi-contraction provide additional insights into the topology of the set of optimizers in the case when multiple optima exist. Furthermore, they show how semi-contraction may be combined with specific additional information to reach broad conclusions about a dynamical system. The contraction perspective also easily extends to time-varying optimization settings and allows one to recursively build large optimization structures out of simpler elements. Extensions to natural primal-dual optimization and game-theoretic contexts further illustrate the potential reach of these new perspectives.

author typesetting of extended final version (expanded appendix)

References in corpus (19)

• A Convergence Theory for Deep Learning via Over-Parameterization
• A Variational Perspective on Accelerated Methods in Optimization
• Optimizing Neural Networks with Kronecker-factored Approximate Curvature
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Stability and Robustness Analysis of Nonlinear Systems via Contraction Metrics and SOS Programming
• Poincaré Embeddings for Learning Hierarchical Representations
• Characterizing Implicit Bias in Terms of Optimization Geometry
• Conic geometric optimisation on the manifold of positive definite matrices
• Gradient Descent Converges to Minimizers
• First-order Methods Almost Always Avoid Saddle Points
• On exponential convergence of SGD in non-convex over-parametrized learning
• Direct Runge-Kutta Discretization Achieves Acceleration
• The loss landscape of overparameterized neural networks
• Transient stability guarantees for ad hoc dc microgrids
• Contraction Metrics in Adaptive Nonlinear Control
• Weight-space symmetry in deep networks gives rise to permutation saddles, connected by equal-loss valleys across the loss landscape
• A continuous-time analysis of distributed stochastic gradient
• Deep Primal-Dual Reinforcement Learning: Accelerating Actor-Critic using Bellman Duality
• On the primal-dual dynamics of Support Vector Machines

Cited by in corpus (9)

• Contraction Theory for Nonlinear Stability Analysis and Learning-based Control: A Tutorial Overview
• Implicit Regularization and Momentum Algorithms in Nonlinearly Parameterized Adaptive Control and Prediction
• On the Sample Complexity of Stability Constrained Imitation Learning
• Loss landscapes and optimization in over-parameterized non-linear systems and neural networks
• Serial interconnections of 1-contracting and 2-contracting systems
• On continuation and convex Lyapunov functions
• Wasserstein Contraction of Stochastic Nonlinear Systems
• A Contraction Theory Approach to Optimization Algorithms from Acceleration Flows
• From Contraction Theory to Fixed Point Algorithms on Riemannian and Non-Euclidean Spaces