论文标题
镜像下降再次罢工：无限噪声方差下的最佳随机凸优化
Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization under Infinite Noise Variance
论文作者
论文摘要
我们研究无限噪声方差下的随机凸优化。具体而言，当随机梯度是公正的，并且在（0,1] $中的某些$κ\中，$（1+κ）$ - 第thism arm-thist，我们量化了与特定的均匀凸出镜像的随机镜像型算法的收敛速率，并且相关的是均无用的参数，并且相关的是相关的界面。算法不需要任何明确的梯度剪辑或归一化，在最近的几个经验和理论工作中，我们的收敛结果与信息理论下限相辅相成，没有其他算法，表明只有使用随机的一阶口腔来启动了一些有趣的在线速度，因此，我们只能使用其他算法。 学习。
We study stochastic convex optimization under infinite noise variance. Specifically, when the stochastic gradient is unbiased and has uniformly bounded $(1+κ)$-th moment, for some $κ\in (0,1]$, we quantify the convergence rate of the Stochastic Mirror Descent algorithm with a particular class of uniformly convex mirror maps, in terms of the number of iterations, dimensionality and related geometric parameters of the optimization problem. Interestingly this algorithm does not require any explicit gradient clipping or normalization, which have been extensively used in several recent empirical and theoretical works. We complement our convergence results with information-theoretic lower bounds showing that no other algorithm using only stochastic first-order oracles can achieve improved rates. Our results have several interesting consequences for devising online/streaming stochastic approximation algorithms for problems arising in robust statistics and machine learning.
