# A Unified Analysis on the Subgradient Upper Bounds for the Subgradient Methods Minimizing Composite Nonconvex, Nonsmooth and Non-Lipschitz Functions

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 38 references that are in the map.
- First posted on arXiv 30 Aug 2023.

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

- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Stochastic model-based minimization of weakly convex functions](https://mlsanity.com/paper/1803.06523/) (2018)
- [Subgradient methods for sharp weakly convex functions](https://mlsanity.com/paper/1803.02461/) (2018)
- [The importance of better models in stochastic optimization](https://mlsanity.com/paper/1903.08619/) (2019)
- [Solving (most) of a set of quadratic equalities: Composite optimization for robust phase retrieval](https://mlsanity.com/paper/1705.02356/) (2017)
- [Convergence Rates for Deterministic and Stochastic Subgradient Methods Without Lipschitz Continuity](https://mlsanity.com/paper/1712.04104/) (2017)
- ["Relative-Continuity" for Non-Lipschitz Non-Smooth Convex Optimization using Stochastic (or Deterministic) Mirror Descent](https://mlsanity.com/paper/1710.04718/) (2017)
- [Regret Bounds without Lipschitz Continuity: Online Learning with Relative-Lipschitz Losses](https://mlsanity.com/paper/2010.12033/) (2020)
- ["Efficient" Subgradient Methods for General Convex Optimization](https://mlsanity.com/paper/1605.08712/) (2016)
- [Radial Subgradient Method](https://mlsanity.com/paper/1703.09280/) (2017)
- [Revisiting Subgradient Method: Complexity and Convergence Beyond Lipschitz Continuity](https://mlsanity.com/paper/2305.14161/) (2023)
- [Randomized Coordinate Subgradient Method for Nonsmooth Composite Optimization](https://mlsanity.com/paper/2206.14981/) (2022)

## Built on by (most cited first, 2 of 2)

- [Stochastic Weakly Convex Optimization Beyond Lipschitz Continuity](https://mlsanity.com/paper/2401.13971/) (2024)
- [Quantitative Convergence Analysis of Projected Stochastic Gradient Descent for Non-Convex Losses via the Goldstein Subdifferential](https://mlsanity.com/paper/2510.02735/) (2025)

## Abstract (arXiv)

This paper presents a unified analysis for the proximal subgradient method (Prox-SubGrad) type approach to minimize an overall objective of f(x)+r(x), subject to convex constraints, where both f and r are weakly convex, nonsmooth, and non-Lipschitz. Leveraging on the properties of the Moreau envelope of weakly convex functions, we are able to relate error-bound conditions, the growth conditions of the subgradients of the objective, and the behavior of the proximal subgradient iterates on some remarkably broad classes of objective functions. Various existing as well as new bounding conditions are studied, leading to novel iteration complexity results. The terrain of our exploration expands to stochastic proximal subgradient algorithms.