# Stochastic Non-Smooth Convex Optimization with Unbounded Gradients

arXiv: https://arxiv.org/abs/2605.15522 · HTML: https://mlsanity.com/paper/2605.15522/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 30 of its 54 references that are in the map.
- First posted on arXiv 15 May 2026.

## Builds on (most cited first, 30 of 30)

- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [signSGD: Compressed Optimisation for Non-Convex Problems](https://mlsanity.com/paper/1802.04434/) (2018)
- [Why gradient clipping accelerates training: A theoretical justification for adaptivity](https://mlsanity.com/paper/1905.11881/) (2019)
- [Error Feedback Fixes SignSGD and other Gradient Compression Schemes](https://mlsanity.com/paper/1901.09847/) (2019)
- [A Simple Convergence Proof of Adam and Adagrad](https://mlsanity.com/paper/2003.02395/) (2020)
- [The Road Less Scheduled](https://mlsanity.com/paper/2405.15682/) (2024)
- [An Alternative View: When Does SGD Escape Local Minima?](https://mlsanity.com/paper/1802.06175/) (2018)
- [Convergence of Adam Under Relaxed Assumptions](https://mlsanity.com/paper/2304.13972/) (2023)
- [Scale-Free Online Learning](https://mlsanity.com/paper/1601.01974/) (2016)
- [Robustness to Unbounded Smoothness of Generalized SignSGD](https://mlsanity.com/paper/2208.11195/) (2022)
- [Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion](https://mlsanity.com/paper/2302.03775/) (2023)
- [Convex and Non-convex Optimization Under Generalized Smoothness](https://mlsanity.com/paper/2306.01264/) (2023)
- [SGD Converges to Global Minimum in Deep Learning via Star-convex Path](https://mlsanity.com/paper/1901.00451/) (2019)
- [Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond](https://mlsanity.com/paper/1906.11985/) (2019)
- [Understanding Adam Optimizer via Online Learning of Updates: Adam is FTRL in Disguise](https://mlsanity.com/paper/2402.01567/) (2024)
- [Methods for Convex (L0,L1)-Smooth Optimization: Clipping, Acceleration, and Adaptivity](https://mlsanity.com/paper/2409.14989/) (2024)
- [Adam with model exponential moving average is effective for nonconvex optimization](https://mlsanity.com/paper/2405.18199/) (2024)
- [Normalized Gradients for All](https://mlsanity.com/paper/2308.05621/) (2023)
- [Random Scaling and Momentum for Non-smooth Non-convex Optimization](https://mlsanity.com/paper/2405.09742/) (2024)
- [Clipping Improves Adam-Norm and AdaGrad-Norm when the Noise Is Heavy-Tailed](https://mlsanity.com/paper/2406.04443/) (2024)
- [Adaptive Matrix Online Learning through Smoothing with Guarantees for Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2602.08232/) (2026)
- [SGD with Adaptive Preconditioning: Unified Analysis and Momentum Acceleration](https://mlsanity.com/paper/2506.23803/) (2025)
- [Grad-GradaGrad? A Non-Monotone Adaptive Stochastic Gradient Method](https://mlsanity.com/paper/2206.06900/) (2022)
- [Universality of AdaGrad Stepsizes for Stochastic Optimization: Inexact Oracle, Acceleration and Variance Reduction](https://mlsanity.com/paper/2406.06398/) (2024)
- [Non-Euclidean SGD for Structured Optimization: Unified Analysis and Improved Rates](https://mlsanity.com/paper/2511.11466/) (2025)
- [Universal Gradient Methods for Stochastic Convex Optimization](https://mlsanity.com/paper/2402.03210/) (2024)
- [Reevaluating Theoretical Analysis Methods for Optimization in Deep Learning](https://mlsanity.com/paper/2407.01825/) (2024)
- [Avoiding Bias in Clipped SGD for Overparameterized Models under Generalized Smoothness](https://mlsanity.com/paper/2605.14800/) (2026)
- [Optimal Projection-Free Adaptive SGD for Matrix Optimization](https://mlsanity.com/paper/2604.02505/) (2026)

## Abstract (arXiv)

Much of the existing theory on first-order non-smooth optimization is built on a restrictive assumption that the gradients of the objective function are uniformly bounded. We introduce a much more realistic class of generalized Lipschitz functions, where the gradient norms are bounded by an affine function of the optimality gap. We then ask a natural question: what algorithm achieves the best global convergence rates for solving convex stochastic generalized Lipschitz optimization problems? To address this, we develop a new convergence analysis for several existing algorithms and find that AdamW with clipped updates, provably outperforms other popular stochastic optimization methods, such as SGD and AdaGrad. Moreover, our analysis establishes the critical role of AdamW's exponentially weighted gradient accumulation, as opposed to simple averaging. We further show that clipped AdamW is universal and achieves improved rates under the popular generalized smoothness assumption, analyze the convergence of clipped AdamW with diagonal and matrix preconditioners, and extend our results to the quasar-convex setting.