AI & ML
Bias-Reduced and Parallel Heavy-Tailed Stochastic Convex Optimization in $\ell_p$ Geometries
arXiv stat.ML0 views
arXiv:2611.21844v1 Announce Type: cross 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 ($\ell_2$-norm) setting, meaning the objective is Lipschitz with respect to the $\ell_2$-norm over an $\ell_2$-bounded feasible set in $\mathbb{R}^d$, in this work we study parallel SCO in $\ell_p$ settings for $2 \le p < \infty$ under a heavy-tailed noise model. We begin by introducing a new class of $\ell_p$-optimal-distance-convergence (ODC$_p$) 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$_p$ algorithms, we first establish rates for projection-efficient $\ell_p$-Lipschitz optimization, composite convex minimization, and efficient $\ell_p$-proximal point estimation. Combining our ODC$_p$ algorithms with a new $\ell_p$-generalized Gaussian-based stochastic gradient estimator ($p$-GREG), we provide two efficient $\ell_p$ parallel algorithms, EpochDA and $\ell_p$-AC-SA, which achieve optimization error $\epsilon > 0$ with at most $\tilde{O}(d^{\frac{p}{2p + 2}} \epsilon^{-\frac{p}{p + 1}})$ query depth, improving upon the sequential heavy-tailed stochastic query depth of $O(\epsilon^{-p})$ for $\epsilon \leq \tilde{O}(d^{-1/(2p)})$. We also establish dimension-dependent lower bounds of $\Omega\bigl(\min\{\epsilon^{-p},d^{p/(3p-2)}\}\bigr)$ adaptive rounds for nonsmooth convex optimization over a subset of the unit $\ell_p$ ball. Our results improve upon the $\Omega(\min\{\epsilon^{-p},\epsilon^{2/3}d^{1/3}\})$ bounds of [DG19], when adapted to the same feasible set.
Source:https://arxiv.org/abs/2611.21844PreviousBandit Online Submodular Minimisation Using Zeroth-Order OraclesNextAdaptive Memory for Online Reinforcement Learning under Sparse Model Changes
Related posts
Criminals Have a New Favorite ‘Point-and-Shoot’ AI Hacking Tool
0Wired

GTA 6 Leads The Game Awards 2026 Nominees With 8 Nods Before Launch: Key Craft & Gamedev Takeaways
0dev.to
Waymo suspends freeway driving after California construction zone complaint
0Ars Technica
Como uma pipeline de IA ajudou no desenvolvimento de um app para uma rede de Supermercados
0dev.to

Remember the frontier AI pause? Chip companies don’t either
0The Verge

8BitDo’s new gamepad modernizes the Nintendo GameCube’s WaveBird
0The Verge