Bias-Reduced and Parallel Heavy-Tailed Stochastic Convex Optimization in ℓp Geometries
Nie et al.
Parallel algorithms for convex optimisation in \(\ell_p\) geometries under heavy-tailed gradient noise reach error \(\epsilon\) with query depth \(\tilde{O}(d^{p/(2p+2)}\epsilon^{-p/(p+1)})\), with matching-style lower bounds.
Source published · In the Daily Brief of 19 November 2026
Filed under Optimization, Probability
The paper studies stochastic convex optimisation when several gradient queries can be made in parallel per round, the gradient noise has only bounded moments, and the geometry is \(\ell_p\) for \(2 \le p < \infty\) rather than Euclidean. It combines bias-reduced estimators with multilevel Monte Carlo and a new generalised-Gaussian gradient estimator.
The resulting methods reach error \(\epsilon\) with query depth \(\tilde{O}(d^{p/(2p+2)}\epsilon^{-p/(p+1)})\), improving on the sequential \(O(\epsilon^{-p})\) for small enough \(\epsilon\). The authors also prove a lower bound of \(\Omega(\min\{\epsilon^{-p}, d^{p/(3p-2)}\})\) adaptive rounds for nonsmooth problems on the unit \(\ell_p\) ball.