Algorithms of Robust Stochastic Optimization Based on Mirror Descent Method

2019/07/05 by Juditsky, Anatoli, Nazin, Alexander, Nemirovsky, Arkadi +1 · 5 citations
#FOS: Mathematics #Optimization and Control (math.OC) #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.1907.02707

Abstract

We propose an approach to construction of robust non-Euclidean iterative algorithms for convex composite stochastic optimization based on truncation of stochastic gradients. For such algorithms, we establish sub-Gaussian confidence bounds under weak assumptions about the tails of the noise distribution in convex and strongly convex settings. Robust estimates of the accuracy of general stochastic algorithms are also proposed.

Cited by

• Stress-Aware Learning under KL Drift via Trust-Decayed Mirror Descent
• Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limits
• Stochastic Bilevel Optimization with Heavy-Tailed Noise
• Breaking a Logarithmic Barrier in the Stopping Time Convergence Rate of Stochastic First-order Methods
• Convergence of Clipped-SGD for Convex (L₀,L₁)-Smooth Optimization with Heavy-Tailed Noise

Related

• Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization under Infinite Noise Variance
• Estimate Sequences for Stochastic Composite Optimization: Variance Reduction, Acceleration, and Robustness to Noise
• Gradient-Free Methods for Non-Smooth Convex Stochastic Optimization with Heavy-Tailed Noise on Convex Compact
• Oblivious Stochastic Composite Optimization
• Accelerated Randomized Mirror Descent Algorithms For Composite Non-strongly Convex Optimization