math.OCNov 16, 2026

Bias-Reduced and Parallel Heavy-Tailed Stochastic Convex Optimization in ℓp\ell_p Geometries

Authors: Zhengyun Nie, Anant Shyam, Brian Bullins

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 (ℓ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.

Figures & tables

Explore similar work

CardsList
  1. Accelerated stochastic first-order method for convex optimization under heavy-tailed noise

    Oct 13, 2025Chuan He, Bowen Li, Zhaosong LuStochastic OptimizationHeavy-Tailed Noise

  2. Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise

    Jul 28, 2026Bin Luo, Chengchang Liu, Jonathan Allcock +2Nonconvex Stochastic OptimizationHeavy-Tailed Noise