← 研踪 PaperTrailarXiv:2611.21844 · v1
Bias-Reduced and Parallel Heavy-Tailed Stochastic Convex Optimization in $\ell_p$ Geometries
首次提交 2026-11-17 04:00
版本更新 2026-11-17 04:00
雷达观测 2026-11-18 19:44
摘要
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.
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-17 04:00 · 最新观测版本
Bias-Reduced and Parallel Heavy-Tailed Stochastic Convex Optimization in $\ell_p$ Geometries
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.
查看此版本解读 →查看此版本原文 ↗