论文标题
在线学习中的root-SGD算法的协方差估计器
Covariance Estimators for the ROOT-SGD Algorithm in Online Learning
论文作者
论文摘要
在线学习自然出现在许多统计和机器学习问题中。在线学习中使用最广泛的方法是随机的一阶算法。在该算法家族中，有一种最近开发的算法，递归单位sgd（root-sgd）。根-SGD是有利的，因为它以非质子快速速率收敛，其估计器进一步收敛到正态分布。但是，这种正态分布具有未知的渐近协方差。因此，不能直接应用来测量不确定性。为了填补这一空白，我们为根 - SGD的渐近协方差开发了两个估计量。我们的协方差估计器可用于root-SGD的统计推断。我们的第一个估计器采用了插件的想法。对于渐近协方差公式中的每个未知组件，我们用其经验对应物代替它。插件估算器以$ \ MATHCAL {O}（1/\ sqrt {t}）$收敛，其中$ t $是样本大小。尽管具有快速的收敛性，但插件估算器仍依赖于损失功能的Hessian的限制，在某些情况下可能无法使用。我们的第二个估计器是一个无用的估计器，它克服了上述限制。无Hessian估计器使用随机缩放技术，我们表明它是对真实协方差的渐近一致估计器。
Online learning naturally arises in many statistical and machine learning problems. The most widely used methods in online learning are stochastic first-order algorithms. Among this family of algorithms, there is a recently developed algorithm, Recursive One-Over-T SGD (ROOT-SGD). ROOT-SGD is advantageous in that it converges at a non-asymptotically fast rate, and its estimator further converges to a normal distribution. However, this normal distribution has unknown asymptotic covariance; thus cannot be directly applied to measure the uncertainty. To fill this gap, we develop two estimators for the asymptotic covariance of ROOT-SGD. Our covariance estimators are useful for statistical inference in ROOT-SGD. Our first estimator adopts the idea of plug-in. For each unknown component in the formula of the asymptotic covariance, we substitute it with its empirical counterpart. The plug-in estimator converges at the rate $\mathcal{O}(1/\sqrt{t})$, where $t$ is the sample size. Despite its quick convergence, the plug-in estimator has the limitation that it relies on the Hessian of the loss function, which might be unavailable in some cases. Our second estimator is a Hessian-free estimator that overcomes the aforementioned limitation. The Hessian-free estimator uses the random-scaling technique, and we show that it is an asymptotically consistent estimator of the true covariance.
