Exponential Convergence of Stochastic Mirror Descent in Over-parameterized Linear Models

Abstract

Stochastic Mirror Descent (SMD) has emerged as a method for solving various convex optimization problems and, under appropriate conditions, has been shown to exponentially converge to the global optimum when the underlying loss is strongly convex. However, strong convexity of the loss fails to hold when the optimization problem is over a set of over-parameterized linear equations, a scenario that frequently occurs in modern machine learning and signal processing. In this setting, prior literature only guarantees much slower convergence rates. In this paper, we show exponential convergence of the SMD iterates to a global optimum (the one that exhibits the appropriate implicit bias) in such over-parameterized linear models. As an extension of this result, we show the exponential convergence of the related Regularizer Mirror Descent (RMD) iterates to the global optimum of explicitly regularized over-parameterized linear models.