Implicit Regularization Properties of Variance Reduced Stochastic Mirror Descent

In statistics and machine learning, it is common to optimize an objective function that is a finitesum. SMD efficiently optimizes such an objective by using a subset of data to do one step update of the variable/parameter. Further adopting the variance reduction technique to SMD, we get the VRSMD algorithm that enjoys fast convergence [1], [2]. The implicit regularization is a relatively new concept [3] that explains why a result of an algorithm generalizes well in some overparameterized models [3], [4]. It refers to the fact that an algorithm can automatically select a minimum norm solution, which is not explicitly induced by the objective function. There are works on implicit regularization for Gradient Descent [5]- [8], Stochastic Gradient Descent [9]-[12], and Stochastic Mirror Descent [13]. Considering the computational advantage of VRSMD compared to all the algorithms above, it would be even better if VRSMD also has the useful implicit regularization property. From technical point of view, our work contains the following two results: In linear regression (including underfitting and overfitting), we show that the solution sequence of VRSMD converges to the minimum mirror interpolant, which is the implicit regularization property of VRSMD, and we also specify the convergence rate.