Linear Convergence of Generalized Mirror Descent with Time-Dependent Mirrors

Abstract

The Polyak-Lojasiewicz (PL) inequality is a sufficient condition for establishing linear convergence of gradient descent, even in non-convex settings. While several recent works use a PL-based analysis to establish linear convergence of stochastic gradient descent methods, the question remains as to whether a similar analysis can be conducted for more general optimization methods. In this work, we present a PL-based analysis for linear convergence of generalized mirror descent (GMD), a generalization of mirror descent with a possibly time-dependent mirror. GMD subsumes popular first order optimization methods including gradient descent, mirror descent, and preconditioned gradient descent methods such as Adagrad. Since the standard PL analysis cannot be extended naturally from GMD to stochastic GMD, we present a Taylor-series based analysis to establish sufficient conditions for linear convergence of stochastic GMD. As a corollary, our result establishes sufficient conditions and provides learning rates for linear convergence of stochastic mirror descent and Adagrad. Lastly, for functions that are locally PL*, our analysis implies existence of an interpolating solution and convergence of GMD to this solution.

References in corpus (5)

• AdaGrad stepsizes: Sharp convergence over nonconvex landscapes
• Characterizing Implicit Bias in Terms of Optimization Geometry
• Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?
• Global Convergence of Adaptive Gradient Methods for An Over-parameterized Neural Network
• Stochastic Gradient/Mirror Descent: Minimax Optimality and Implicit Regularization