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.

A celebrated result by Gordon allows one to compare the min-max behavior of two Gaussian processes if certain inequality conditions are met. The consequences of this result include the Gaussian min-max (GMT) and convex Gaussian min-max (CGMT) theorems which have had far-reaching implications in high-dimensional statistics, machine learning, non-smooth optimization, and signal processing. Both theorems rely on a pair of Gaussian processes, first identified by Slepian, that satisfy Gordon’s comparison inequalities. In this paper, we identify a new pair of Gaussian processes satisfying these inequalities. The resulting theorems extend the classical GMT and CGMT Theorems from the case where the underlying Gaussian matrix in the primary process has iid rows to where it has independent but non-identically-distributed ones. The new CGMT is applied to the problems of multi-source Gaussian regression, as well as to binary classification of general Gaussian mixture models.

We study the precise asymptotic behavior of stochastic mirror descent (SMD) algorithms in over-parameterized binary linear classification using regression. In this over-parameterized regime, the training loss has infinitely many global minima which defines a manifold of interpolating solutions. SMD exhibits implicit regularization and finds the interpolating solution that is closest to the initial weight vector in Bregman divergence (corresponding to the mirror's potential function). It has been empirically observed that different potentials lead to different generalization errors and different distributions of the weights. In this paper, we explicitly compute closed form expressions of the distribution of the solution and characterise its generalization performance on data generated by a Gaussian Mixture model (GMM). The theory presented well matches empirical simulations and can provide insights in understanding the generalization performance of SMD on nonlinear models, such as in deep learning.

The stochastic mirror descent (SMD) algorithm is a generalization of the celebrated stochastic gradient descent (SGD)—the workhorse of modern machine learning. In over-parameterized models, such as in deep learning, it is well known that SGD finds the weight vector that interpolates the training data and is closest to the initial weight vector in Euclidean distance. This phenomenon is called "implicit regularization". SMD allows for different implicit regularizations and finds the interpolating solution that is closest to the initial weight vector in Bregman divergence (corresponding to the mirror’s potential function). It has been empirically observed that different potentials lead to different generalization errors and different distributions of the weights. In this paper, we explicitly compute the asymptotic distribution of the optimal weight vector for SMD applied to over-parameterized linear models with Gaussian training vectors. The theory presented well matches empirical simulations and can provide a stepping stone toward the analysis of SMD on nonlinear models, such as in deep learning.