Bias-Reduced and Parallel Heavy-Tailed Stochastic Convex Optimization in Geometries
Organizations: Purdue University
Abstract
We consider the fundamental problem of parallel stochastic convex optimization (SCO), whose aim is to approximately minimize a convex objective when given the ability to query a moment-bounded stochastic gradient oracle multiple times in parallel per round. Whereas most previous results have focused on the variance-bounded Euclidean (-norm) setting, meaning the objective is Lipschitz with respect to the -norm over an -bounded feasible set in , in this work we study parallel SCO in settings for under a heavy-tailed noise model. We begin by introducing a new class of -optimal-distance-convergence (ODC) algorithms, drawing on prior stochastic bias-reduced techniques [ACJ+21], which combine with multilevel Monte Carlo methods to efficiently estimate the optimum of uniformly convex objectives. As a consequence of our ODC algorithms, we first establish rates for projection-efficient -Lipschitz optimization, composite convex minimization, and efficient -proximal point estimation. Combining our ODC algorithms with a new -generalized Gaussian-based stochastic gradient estimator (-GREG), we provide two efficient parallel algorithms, EpochDA and -AC-SA, which achieve optimization error with at most query depth, improving upon the sequential heavy-tailed stochastic query depth of for . We also establish dimension-dependent lower bounds of adaptive rounds for nonsmooth convex optimization over a subset of the unit ball. Our results improve upon the bounds of [DG19], when adapted to the same feasible set.
Figures & tables
| Method | Query depth | Computational depth |
| Stochastic Mirror Descent ( VYB+ (22) , Theorem 6) | ||
| BallAccel + EpochSGD ( CJJ+ (23) , Theorem 1) | ||
| BallAccel + AC-SA ( CJJ+ (23) , Theorem 2) | ||
| JST (24) (Theorem 2) | ||
| BallAccel + EpochDA (Theorem 14 ) | ||
| BallAccel + -AC-SA (Theorem 17 ) |
| Method | Total query complexity |
| Stochastic Mirror Descent ( VYB+ (22) , Theorem 6) | |
| BallAccel + EpochSGD ( CJJ+ (23) , Theorem 1) | |
| BallAccel + AC-SA ( CJJ+ (23) , Theorem 2) | |
| JST (24) (Theorem 2) | |
| BallAccel + EpochDA (Theorem 14 ) | |
| BallAccel + -AC-SA (Theorem 17 ) |
Stochastic Optimization
Stochastic optimization studies how to find good decisions or model parameters when objectives, data, or feedback are random or noisy.
See all 226 papers