An Improved Analysis of the Clipped Stochastic subGradient Method under Heavy-Tailed Noise

2024/10/01 by Daniela A. Parletta, Andrea Paudice, Parletta, Daniela Angela +3 · 1 citation
Mathematics · #FOS: Mathematics #Optimization and Control (math.OC) #Statistical and numerical algorithms

paper · pdf · doi:10.48550/arxiv.2410.00573

openalex publication_date 2024/10/01 · openalex created_date 2024/10/29 · openalex updated_date 2026/07/28

Abstract

In this paper, we provide novel optimal (or near optimal) convergence rates for a clipped version of the stochastic subgradient method. We consider nonsmooth convex problems over possibly unbounded domains, under heavy-tailed noise that possesses only the first p moments for p ∈ ]1,2]. For the last iterate, we establish convergence in expectation for the objective values with rates of order (log^1/p k)/k^(p-1)/p and 1/k^(p-1)/p, for anytime and finite-horizon respectively. We also derive new convergence rates, in expectation and with high probability, for the objective values along the average iterates--improving existing results by a log^(2p-1)/p k factor. Those results are applied to the problem of supervised learning with kernels demonstrating the effectiveness of our theory. Finally, we give preliminary experiments.

Cited by

• Online Convex Optimization with Heavy Tails: Old Algorithms, New Regrets, and Applications

Related

• Clipped Gradient Methods for Nonsmooth Convex Optimization under Heavy-Tailed Noise: A Refined Analysis
• High Probability Convergence of Clipped-SGD Under Heavy-tailed Noise
• Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises: High-Probability Bound, In-Expectation Rate and Initial Distance Adaptation
• Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping
• Stability and Convergence of Stochastic Gradient Clipping: Beyond Lipschitz Continuity and Smoothness