# Inexact subgradient methods for semialgebraic functions

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 79 references that are in the map.
- First posted on arXiv 30 Apr 2024.

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

- [SGDR: Stochastic Gradient Descent with Warm Restarts](https://mlsanity.com/paper/1608.03983/) (2016)
- [Switch Transformers: Scaling to Trillion Parameter Models with Simple and Efficient Sparsity](https://mlsanity.com/paper/2101.03961/) (2021)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [OptNet: Differentiable Optimization as a Layer in Neural Networks](https://mlsanity.com/paper/1703.00443/) (2017)
- [Gradient Descent on Neural Networks Typically Occurs at the Edge of Stability](https://mlsanity.com/paper/2103.00065/) (2021)
- [Efficient and Modular Implicit Differentiation](https://mlsanity.com/paper/2105.15183/) (2021)
- [Gradient Sparsification for Communication-Efficient Distributed Optimization](https://mlsanity.com/paper/1710.09854/) (2017)
- [Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimization](https://mlsanity.com/paper/1308.6594/) (2013)
- [Stochastic subgradient method converges on tame functions](https://mlsanity.com/paper/1804.07795/) (2018)
- [Distributed Learning with Compressed Gradient Differences](https://mlsanity.com/paper/1901.09269/) (2019)
- [Conservative set valued fields, automatic differentiation, stochastic gradient method and deep learning](https://mlsanity.com/paper/1909.10300/) (2019)
- [From error bounds to the complexity of first-order descent methods for convex functions](https://mlsanity.com/paper/1510.08234/) (2015)
- [One-step differentiation of iterative algorithms](https://mlsanity.com/paper/2305.13768/) (2023)
- [Convergence of constant step stochastic gradient descent for non-smooth non-convex functions](https://mlsanity.com/paper/2005.08513/) (2020)
- [Analysis of nonsmooth stochastic approximation: the differential inclusion approach](https://mlsanity.com/paper/1805.01916/) (2018)
- [Asymptotic Bias of Stochastic Gradient Search](https://mlsanity.com/paper/1709.00291/) (2017)
- [Stochastic Approximation Beyond Gradient for Signal Processing and Machine Learning](https://mlsanity.com/paper/2302.11147/) (2023)
- [Analysis of gradient descent methods with non-diminishing, bounded errors](https://mlsanity.com/paper/1604.00151/) (2016)
- [Long term dynamics of the subgradient method for Lipschitz path differentiable functions](https://mlsanity.com/paper/2006.00098/) (2020)
- [Subgradient sampling for nonsmooth nonconvex minimization](https://mlsanity.com/paper/2202.13744/) (2022)
- [Global stability of first-order methods for coercive tame functions](https://mlsanity.com/paper/2308.00899/) (2023)
- [Lyapunov stability of the subgradient method with constant step size](https://mlsanity.com/paper/2211.14850/) (2022)
- [Quantitative convergence analysis of iterated expansive, set-valued mappings](https://mlsanity.com/paper/1605.05725/) (2016)
- [Local Linear Convergence of the ADMM/Douglas--Rachford Algorithms without Strong Convexity and Application to Statistical Imaging](https://mlsanity.com/paper/1508.04468/) (2015)
- [Necessary conditions for linear convergence of iterated expansive, set-valued mappings with application to alternating projections](https://mlsanity.com/paper/1704.08926/) (2017)
- [Openness, Holder metric regularity and Holder continuity properties of semialgebraic set-valued maps](https://mlsanity.com/paper/2004.02188/) (2020)

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

- [Ultra-Reliable Risk-Aggregated Sum Rate Maximization via Model-Aided Deep Learning](https://mlsanity.com/paper/2509.26311/) (2025)

## Abstract (arXiv)

Motivated by the extensive application of approximate gradients in machine learning and optimization, we investigate inexact subgradient methods subject to persistent additive errors. Within a nonconvex semialgebraic framework, assuming boundedness or coercivity, we establish that the method yields iterates that eventually fluctuate near the critical set at a proximity characterized by an O(ερ) distance, where ε denotes the magnitude of subgradient evaluation errors, and ρ encapsulates geometric characteristics of the underlying problem. Our analysis comprehensively addresses both vanishing and constant step-size regimes. Notably, the latter regime inherently enlarges the fluctuation region, yet this enlargement remains on the order of ερ. In the convex scenario, employing a universal error bound applicable to coercive semialgebraic functions, we derive novel complexity results concerning averaged iterates. Additionally, our study produces auxiliary results of independent interest, including descent-type lemmas for nonsmooth nonconvex functions and an invariance principle governing the behavior of algorithmic sequences under small-step limits.