A general system of differential equations to model first order adaptive algorithms

Abstract

First order optimization algorithms play a major role in large scale machine learning. A new class of methods, called adaptive algorithms, were recently introduced to adjust iteratively the learning rate for each coordinate. Despite great practical success in deep learning, their behavior and performance on more general loss functions are not well understood. In this paper, we derive a non-autonomous system of differential equations, which is the continuous time limit of adaptive optimization methods. We prove global well-posedness of the system and we investigate the numerical time convergence of its forward Euler approximation. We study, furthermore, the convergence of its trajectories and give conditions under which the differential system, underlying all adaptive algorithms, is suitable for optimization. We discuss convergence to a critical point in the non-convex case and give conditions for the dynamics to avoid saddle points and local maxima. For convex and deterministic loss function, we introduce a suitable Lyapunov functional which allow us to study its rate of convergence. Several other properties of both the continuous and discrete systems are briefly discussed. The differential system studied in the paper is general enough to encompass many other classical algorithms (such as Heavy ball and Nesterov's accelerated method) and allow us to recover several known results for these algorithms.

References in corpus (9)

• ADADELTA: An Adaptive Learning Rate Method
• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• A Variational Perspective on Accelerated Methods in Optimization
• Gradient Descent Converges to Minimizers
• A geometric alternative to Nesterov's accelerated gradient descent
• First-order Methods Almost Always Avoid Saddle Points
• On Symplectic Optimization
• Normalized Direction-preserving Adam
• On Accelerated Methods in Optimization

Cited by in corpus (6)

• LaProp: Separating Momentum and Adaptivity in Adam
• Non-Convergence and Limit Cycles in the Adam optimizer
• A Qualitative Study of the Dynamic Behavior for Adaptive Gradient Algorithms
• On the Distributional Properties of Adaptive Gradients
• A closed loop gradient descent algorithm applied to Rosenbrock's function
• Local Convergence of Adaptive Gradient Descent Optimizers