Implicit Regularization Properties of Variance Reduced Stochastic Mirror Descent
Implicit Regularization Properties of Variance Reduced Stochastic Mirror Descent
复制标题
DOI：
10.1109/isit50566.2022.9834827
复制
发表时间：
2022-04
期刊：
影响因子：
--
通讯作者：
Yiling Luo;X. Huo;Y. Mei
中科院分区：
文献类型：
--
作者：
Yiling Luo;X. Huo;Y. Mei
在机器学习和统计数据分析中，我们经常遇到目标函数是求和：求和中的项数可能等于样本大小，这可能是巨大的。在这样的设置中，随机镜像下降（SMD）算法是一种数值上有效的方法，每次迭代涉及的数据的一个非常小的子集。方差减少版本的SMD（VRSMD）可以通过诱导更快的收敛来进一步改善SMD。另一方面，梯度下降和随机梯度下降等算法具有隐式正则化特性，这导致在泛化误差方面具有更好的性能。很少有人知道这样的属性是否适用于VRSMD。本文证明了离散VRSMD估计序列收敛于线性回归中的最小镜像插值。这建立了VRSMD的隐式正则化属性。作为上述结果的应用，我们导出了当真实模型稀疏时的设置中的模型估计精度结果。我们用数值例子来说明VRSMD的经验功率。
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.