Sharp High-Probability Statistical Rates for Heavy-Tailed Nonsmooth Convex Optimization
Abstract
We establish sharp high-probability statistical rates for nonsmooth stochastic convex optimization under heavy-tailed noise, closing the confidence-dependence gap in both general convex and strongly convex settings. We consider composite objectives with a Lipschitz convex loss and a known proximal regularizer, accessed through fresh unbiased stochastic subgradients. The centered noise has conditional norm and directional pth moments bounded by Lp and sp, respectively, where 1<p≤2 and 0<s≤ L. For T oracle calls and failure probability 0<δ<1/10, set q=1−1/p, ℓ=log(3/δ), and A=s(L2/s2)q. With initial distance bound D, the minimax objective error is Θ(D(A+sℓq)/Tq) in the nonsaturated statistical regime. For a μ-strongly convex regularizer, the corresponding quadratic-regime rate is Θ((A2+s2ℓ2q)/(μT2q)). These rates require domination of the deterministic and finite-variance terms; matching lower bounds require d≥⌈ L2/s2⌉, while the upper bounds hold in every finite dimension. The new upper bounds attain known statistical lower-bound orders, replacing the previous confidence coefficient s1/pL1−1/p by s, and its square by s2 under strong convexity. The key is an online inequality that separates directional fluctuations from the total second moment created by rejection sampling. Localization preserves this separation under strong convexity without additional horizon logarithms. The results characterize oracle complexity with unrestricted internal computation.
Related
- Revisiting AdaGrad in Stochastic Convex Optimization: Last Iterates, High Probability, and Lower Bounds
- On Nonsmooth and Relatively Weakly Convex Minimization
- A Flexible Heavy-Tailed Probability Model for Skewed Positive Data: Theory, Estimation, and Empirical Assessment
- Projection-Free Algorithms for Nonsmooth Stochastic Convex-Concave Saddle-Point Problems
- High-Probability Guarantees for SGD under β-Heavy-Tailed Gradient Noise
BibTeX
@misc{zhang2026sharp,
title = {{Sharp High-Probability Statistical Rates for Heavy-Tailed Nonsmooth Convex Optimization}},
author = {Haihan Zhang and Wendao Wu and Chenheng Zhang and Yanyi Li and Chunyuan Zheng and Cong Fang and Haoxuan Li and Zhouchen Lin},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.00260},
eprint = {2610.00260},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.00260},
}
RIS
TY - UNPB
TI - Sharp High-Probability Statistical Rates for Heavy-Tailed Nonsmooth Convex Optimization
AU - Haihan Zhang
AU - Wendao Wu
AU - Chenheng Zhang
AU - Yanyi Li
AU - Chunyuan Zheng
AU - Cong Fang
AU - Haoxuan Li
AU - Zhouchen Lin
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.00260
UR - https://arxiv.org/abs/2610.00260
AB - We establish sharp high-probability statistical rates for nonsmooth stochastic convex optimization under heavy-tailed noise, closing the confidence-dependence gap in both general convex and strongly convex settings. We consider composite objectives with a Lipschitz convex loss and a known proximal regularizer, accessed through fresh unbiased stochastic subgradients. The centered noise has conditional norm and directional pth moments bounded by L^p and s^p, respectively, where 1<p≤2 and 0<s≤ L. For T oracle calls and failure probability 0<δ<1/10, set q=1−1/p, ℓ=log(3/δ), and A=s(L^2/s^2)^q. With initial distance bound D, the minimax objective error is Θ(D(A+sℓ^q)/T^q) in the nonsaturated statistical regime. For a μ-strongly convex regularizer, the corresponding quadratic-regime rate is Θ((A^2+s^2ℓ^2q)/(μT^2q)). These rates require domination of the deterministic and finite-variance terms; matching lower bounds require d≥⌈ L^2/s^2⌉, while the upper bounds hold in every finite dimension. The new upper bounds attain known statistical lower-bound orders, replacing the previous confidence coefficient s^1/pL^1−1/p by s, and its square by s^2 under strong convexity. The key is an online inequality that separates directional fluctuations from the total second moment created by rejection sampling. Localization preserves this separation under strong convexity without additional horizon logarithms. The results characterize oracle complexity with unrestricted internal computation.
ER -