Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization under Infinite Noise Variance
This work addresses robust optimization problems in statistics and machine learning where noise variance is unbounded, offering theoretical guarantees for practical algorithms.
The paper tackles stochastic convex optimization with infinite noise variance by analyzing Stochastic Mirror Descent with uniformly convex mirror maps, achieving convergence rates quantified in terms of iterations and problem parameters without explicit gradient clipping, and provides matching information-theoretic lower bounds.
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.