TY - GEN

T1 - Implicit Regularization Properties of Variance Reduced Stochastic Mirror Descent

AU - Luo, Yiling

AU - Huo, Xiaoming

AU - Mei, Yajun

N1 - Publisher Copyright:
© 2022 IEEE.

PY - 2022

Y1 - 2022

N2 - In machine learning and statistical data analysis, we often run into objective function that is a summation: the number of terms in the summation possibly is equal to the sample size, which can be enormous. In such a setting, the stochastic mirror descent (SMD) algorithm is a numerically efficient method - each iteration involving a very small subset of the data. The variance reduction version of SMD (VRSMD) can further improve SMD by inducing faster convergence. On the other hand, algorithms such as gradient descent and stochastic gradient descent have the implicit regularization property that leads to better performance in terms of the generalization errors. Little is known on whether such a property holds for VRSMD. We prove here that the discrete VRSMD estimator sequence converges to the minimum mirror interpolant in the linear regression. This establishes the implicit regularization property for VRSMD. As an application of the above result, we derive a model estimation accuracy result in the setting when the true model is sparse. We use numerical examples to illustrate the empirical power of VRSMD.

AB - In machine learning and statistical data analysis, we often run into objective function that is a summation: the number of terms in the summation possibly is equal to the sample size, which can be enormous. In such a setting, the stochastic mirror descent (SMD) algorithm is a numerically efficient method - each iteration involving a very small subset of the data. The variance reduction version of SMD (VRSMD) can further improve SMD by inducing faster convergence. On the other hand, algorithms such as gradient descent and stochastic gradient descent have the implicit regularization property that leads to better performance in terms of the generalization errors. Little is known on whether such a property holds for VRSMD. We prove here that the discrete VRSMD estimator sequence converges to the minimum mirror interpolant in the linear regression. This establishes the implicit regularization property for VRSMD. As an application of the above result, we derive a model estimation accuracy result in the setting when the true model is sparse. We use numerical examples to illustrate the empirical power of VRSMD.

KW - implicit regularization

KW - overparameterization

KW - stochastic mirror descent

KW - variance reduction

UR - http://www.scopus.com/inward/record.url?scp=85136293808&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85136293808&partnerID=8YFLogxK

U2 - 10.1109/ISIT50566.2022.9834827

DO - 10.1109/ISIT50566.2022.9834827

M3 - Conference contribution

AN - SCOPUS:85136293808

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 696

EP - 701

BT - 2022 IEEE International Symposium on Information Theory, ISIT 2022

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2022 IEEE International Symposium on Information Theory, ISIT 2022

Y2 - 26 June 2022 through 1 July 2022

ER -