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

Apr 7, 2026

Optimal Rates for Pure ε\varepsilon-Differentially Private Stochastic Convex Optimization with Heavy Tails

We study stochastic convex optimization (SCO) with heavy-tailed gradients under pure ε\varepsilon-differential privacy (DP). Instead of assuming a bound on the worst-case Lipschitz parameter of the loss, we assume only a bounded kk-th moment. This assumption allows for unbounded, heavy-tailed stochastic gradient distributions, and can yield sharper excess risk bounds. Prior work characterized the minimax optimal rate for ρρ-zero-concentrated DP SCO up to logarithmic factors in this setting, but the pure ε\varepsilon-DP case has remained open. We characterize the minimax optimal excess-risk rate for pure ε\varepsilon-DP heavy-tailed SCO up to logarithmic factors. Our algorithm achieves this rate in polynomial time with high probability. Moreover, it runs in deterministic polynomial time when the worst-case Lipschitz parameter is polynomially bounded. For important structured problem classes -- including hinge/ReLU-type and absolute-value losses on Euclidean balls, ellipsoids, and polytopes -- we achieve deterministic polynomial time even when the worst-case Lipschitz parameter is infinite. Our approach is based on a novel framework for privately optimizing Lipschitz extensions of the empirical loss. We complement our upper bound with a nearly matching high-probability lower bound.
Oct 13, 2025

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

We study convex composite optimization problems, where the objective function is given by the sum of a prox-friendly function and a convex function whose subgradients are estimated under heavy-tailed noise. Existing work often employs gradient clipping or normalization techniques in stochastic first-order methods to address heavy-tailed noise. %In this paper, we demonstrate that a vanilla stochastic algorithm---without additional modifications such as clipping or normalization---can achieve optimal complexity for these problems. In this paper, we analyze the first-order oracle complexity of vanilla stochastic algorithms---without additional modifications such as clipping or normalization---for solving these problems. In particular, we establish that an accelerated stochastic proximal subgradient method achieves a first-order oracle complexity for finding an approximate optimal solution in expectation that is universally optimal for smooth, weakly smooth, and nonsmooth convex optimization, as well as for stochastic convex optimization under heavy-tailed noise. Moreover, we derive high-probability first-order oracle complexity bounds for the accelerated stochastic proximal subgradient method under heavy-tailed and sub-Weibull noise, respectively. Numerical experiments are further provided to illustrate the numerical behavior of the methods.
Jul 28, 2026

Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise

We study stochastic optimization with heavy-tailed gradient noise. We first propose a novel quantum mean estimator for multivariate heavy-tailed random variables that achieves lower query complexity than optimal classical estimators in the low-dimensional regime. We further develop an unbiased quantum mean estimator by applying a generalized multi-level Monte Carlo technique. We prove quantum lower bounds showing that, when the dimension dd of the random vector is small and can be viewed as a constant, our quantum estimators are optimal up to logarithmic factors. We further derive stronger dimension-dependent lower bounds for tail index p>4/3p>4/3, showing that a nontrivial dependence on the dimension is unavoidable in the low-dimensional regime. Based on these estimators, we propose a quantum normalized stochastic gradient descent method (QNSGD\texttt{QNSGD}), which finds an εε-stationary point using O~(d ε−5p−42p−2)\tilde{\mathcal{O}}\big(\sqrt d\,ε^{-\frac{5p-4}{2p-2}}\big) queries to the quantum stochastic gradient oracle. For a convex objective function, we propose a quantum projected stochastic gradient descent method (QPSGD\texttt{QPSGD}), which computes a solution with εε-optimal solution using O~(d ε−3p−22p−2+ε−2)\tilde{\mathcal{O}}\big(\sqrt d\,ε^{-\frac{3p-2}{2p-2}}+ε^{-2}\big) queries in expectation. These sharper bounds improve upon the classical lower bounds Ω(ε−3p−2p−1)Ω\big(ε^{-\frac{3p-2}{p-1}}\big) for nonconvex problems and Ω(ε−pp−1)Ω\big(ε^{-\frac{p}{p-1}}\big) for convex problems in the low-dimensional regimes d≲ε−pp−1d\lesssimε^{-\frac{p}{p-1}} and d≲ε−2−pp−1d\lesssimε^{-\frac{2-p}{p-1}}, respectively.