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

'This is not about short-term playtests’ — Disney's AI-powered Star Wars Anzellans offer a glimpse at the future of its parks
0TechRadar

Best Amazon early Black Friday deals — Fire Sticks, AirPods, LEGO, Ring Doorbells and more
0TechRadar

AI meets innovation in the stunning Creality K1 Max, now with a $350 discount
0TechRadar

GTA 6 head of development says ‘the emphasis on interactivity’ adds ‘friction’ to almost every facet of gameplay — ‘It means you have to think a little bit more about what you want to do and when and
0TechRadar

‘People will ask, agents will act’: Workday CEO outlines how AI is coming to help unleash “an incredible world of work”
0TechRadar

Elon Musk’s SpaceXAI suffers chemical spill at Mississippi AI data center
0Tom's Hardware