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

Zhengyun Nie, Anant Shyam, Brian BullinsarXiv 2026 · arXiv

TL;DR

This paper expands the frontiers of parallel stochastic convex optimization (SCO) by moving beyond standard Euclidean ($\ell_2$) settings into more general $\ell_p$ geometries. By introducing a novel gradient estimator and a class of bias-reduced algorithms, the authors achieve significantly faster optimization rates in the presence of heavy-tailed noise, providing both new upper bounds for parallel efficiency and tighter lower bounds on what is theoretically possible.

What Problem Does This Paper Address?

In Stochastic Convex Optimization (SCO), we aim to minimize a convex function using only noisy estimates of its gradients. Most existing research assumes a "Euclidean" world ($\ell_2$-norm) and "light-tailed" noise (where the variance is bounded). However, many real-world problems—ranging from training deep neural networks to flow problems—behave better in non-Euclidean $\ell_p$ geometries and often involve "heavy-tailed" noise, where only higher-order moments (like the $q$-th moment) are bounded rather than the variance.

Furthermore, as we move toward massive-scale computing, we need algorithms that can handle parallelism. The challenge is "query depth": how many sequential rounds of interaction are required if we can submit multiple queries in parallel during each round? While parallel SCO is well-understood for $\ell_2$, it has remained largely unexplored for $\ell_p$ geometries ($2 \le p < \infty$) under heavy-tailed noise.

Methods

The authors introduce three primary technical pillars to solve these challenges:

  1. $\ell_p$-Optimal-Distance-Convergence ($ODC_p$) Algorithms: These are a new class of algorithms designed to estimate the optimum of uniformly convex objectives. They utilize Multilevel Monte Carlo (MLMC) methods to create low-bias, bounded-moment estimators of the "Moreau gradient"—a smoothed version of the objective's gradient.
  2. $p$-GREG Estimator: The authors develop the $\ell_p$-Generalized Gaussian Reweighting for Gradient Estimation. This tool allows the algorithm to compute unbiased estimates of a convolved (smoothed) version of the objective function. Crucially, this estimator is designed to be computed in parallel.
  3. EpochDA and $\ell_p$-AC-SA: By combining the $ODC_p$ framework with the $p$-GREG estimator and recent advances in $\ell_p$ ball-oracle acceleration, the authors propose two solvers. EpochDA uses geometrically increasing epoch lengths to refine the solution, while $\ell_p$-AC-SA provides an accelerated counterpart that further reduces computational depth.

Datasets

This is a theoretical paper focused on algorithmic complexity and mathematical proofs. Consequently, it does not use empirical datasets. Instead, the authors construct "hard instances"—mathematical functions designed to be difficult for any algorithm to solve—to establish theoretical lower bounds.

Key Insights and Ideas

  • The Nonlinearity Hurdle: In standard Euclidean optimization, the mapping from a proximal point to a gradient is linear. In $\ell_p$ spaces (where $p > 2$), this mapping becomes nonlinear. The authors bypass this by applying MLMC directly to the Moreau gradient approximations rather than the proximal points themselves.
  • Parallelism vs. Sequential Depth: The paper shows that parallelism can significantly "beat" the sequential bottleneck. While a sequential algorithm might take $O(\epsilon^{-p})$ steps, their parallel approach reduces the required sequential rounds (query depth) to a factor involving the dimension $d$, making it much faster when high-accuracy solutions are needed in high-dimensional spaces.
  • The "Wall" Construction: To prove lower bounds, the authors adapt a "wall function" to $\ell_p$ geometry. This function essentially "hides" information about the true optimum from the algorithm for a certain number of rounds, allowing them to prove that no algorithm can be faster than their established limit.

Key Results

The paper provides a comprehensive comparison of their new methods against existing baselines.

  • Improved Upper Bounds: The proposed algorithms achieve an optimization error $\epsilon$ with a query depth of $\tilde{O}(d^{\frac{p}{2p + 2}} \epsilon^{-\frac{p}{p + 1}})$. This is a significant improvement over the sequential heavy-tailed stochastic query depth of $O(\epsilon^{-p})$ in the high-accuracy regime.
  • Tighter Lower Bounds: They establish a new dimension-dependent lower bound of $\Omega\bigl(\min\{\epsilon^{-p}, d^{p/(3p-2)}\}\bigr)$ adaptive rounds. This improves upon previous bounds from the literature when adapted to the same feasible set.

The trade-offs between query depth and computational depth are summarized in the following table from the paper:

Comparison of query and computational depths for various methods.

Additionally, the total query complexity (the total amount of work done across all parallel units) is detailed here:

Total query complexity comparison.

Limitations and Future Work

The authors identify a remaining gap between their upper bounds (which have a dimension exponent of $1/2$ when $p=2$) and their lower bounds (where the exponent is $p/(3p-2)$). Closing this gap to determine the absolute optimal parallel complexity in general $\ell_p$ geometry remains an open question.

Additionally, the authors suggest that these bias-reduction and parallelization tools could be extended to Differentially Private SCO, where the goal is to optimize a function while protecting the privacy of the underlying data points.

Summary updated

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 $ε> 0$ with at most $\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})$ for $ε\leq \tilde{O}(d^{-1/(2p)})$. We also establish dimension-dependent lower bounds of $Ω\bigl(\min\{ε^{-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 $Ω(\min\{ε^{-p},ε^{2/3}d^{1/3}\})$ bounds of [DG19], when adapted to the same feasible set.
BibTeX
@misc{nie2026bias,
  author = {Zhengyun Nie and Anant Shyam and Brian Bullins},
  title = {{Bias-Reduced and Parallel Heavy-Tailed Stochastic Convex Optimization in $\textbackslash\{\}ell\_p$ Geometries}},
  year = {2026},
  eprint = {2611.21844},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.21844},
}
Figure