跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv: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
arXiv ↗PDF ↗

摘要

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 (ℓ2\ell_2-norm) setting, meaning the objective is Lipschitz with respect to the ℓ2\ell_2-norm over an ℓ2\ell_2-bounded feasible set in Rd\mathbb{R}^d, in this work we study parallel SCO in ℓp\ell_p settings for 2≤p<∞2 \le p < \infty under a heavy-tailed noise model. We begin by introducing a new class of ℓp\ell_p-optimal-distance-convergence (ODCp_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 ODCp_p algorithms, we first establish rates for projection-efficient ℓp\ell_p-Lipschitz optimization, composite convex minimization, and efficient ℓp\ell_p-proximal point estimation. Combining our ODCp_p algorithms with a new ℓp\ell_p-generalized Gaussian-based stochastic gradient estimator (pp-GREG), we provide two efficient ℓp\ell_p parallel algorithms, EpochDA and ℓp\ell_p-AC-SA, which achieve optimization error ε>0ε> 0 with at most O~(dp2p+2ε−pp+1)\tilde{O}(d^{\frac{p}{2p + 2}} ε^{-\frac{p}{p + 1}}) query depth, improving upon the sequential heavy-tailed stochastic query depth of O(ε−p)O(ε^{-p}) for ε≤O~(d−1/(2p))ε\leq \tilde{O}(d^{-1/(2p)}). We also establish dimension-dependent lower bounds of Ω(min⁡{ε−p,dp/(3p−2)})Ω\bigl(\min\{ε^{-p},d^{p/(3p-2)}\}\bigr) adaptive rounds for nonsmooth convex optimization over a subset of the unit ℓp\ell_p ball. Our results improve upon the Ω(min⁡{ε−p,ε2/3d1/3})Ω(\min\{ε^{-p},ε^{2/3}d^{1/3}\}) bounds of [DG19], when adapted to the same feasible set.

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 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 (ℓ2\ell_2-norm) setting, meaning the objective is Lipschitz with respect to the ℓ2\ell_2-norm over an ℓ2\ell_2-bounded feasible set in Rd\mathbb{R}^d, in this work we study parallel SCO in ℓp\ell_p settings for 2≤p<∞2 \le p < \infty under a heavy-tailed noise model. We begin by introducing a new class of ℓp\ell_p-optimal-distance-convergence (ODCp_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 ODCp_p algorithms, we first establish rates for projection-efficient ℓp\ell_p-Lipschitz optimization, composite convex minimization, and efficient ℓp\ell_p-proximal point estimation. Combining our ODCp_p algorithms with a new ℓp\ell_p-generalized Gaussian-based stochastic gradient estimator (pp-GREG), we provide two efficient ℓp\ell_p parallel algorithms, EpochDA and ℓp\ell_p-AC-SA, which achieve optimization error ε>0ε> 0 with at most O~(dp2p+2ε−pp+1)\tilde{O}(d^{\frac{p}{2p + 2}} ε^{-\frac{p}{p + 1}}) query depth, improving upon the sequential heavy-tailed stochastic query depth of O(ε−p)O(ε^{-p}) for ε≤O~(d−1/(2p))ε\leq \tilde{O}(d^{-1/(2p)}). We also establish dimension-dependent lower bounds of Ω(min⁡{ε−p,dp/(3p−2)})Ω\bigl(\min\{ε^{-p},d^{p/(3p-2)}\}\bigr) adaptive rounds for nonsmooth convex optimization over a subset of the unit ℓp\ell_p ball. Our results improve upon the Ω(min⁡{ε−p,ε2/3d1/3})Ω(\min\{ε^{-p},ε^{2/3}d^{1/3}\}) bounds of [DG19], when adapted to the same feasible set.

查看此版本解读 →查看此版本原文 ↗