Inexact subgradient methods for semialgebraic functions: J. Bolte et al.
Bolte, Jerome Le, Tam Moulines, Eric Pauwels, Edouard
Bolte, Jerome
Le, Tam
Moulines, Eric
Pauwels, Edouard
Supervisor
Department
Machine Learning
Embargo End Date
Type
Journal article
Date
2025
License
Language
English
Collections
Research Projects
Organizational Units
Journal Issue
Abstract
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 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.
Citation
J. Bolte, T. Le, E. Moulines, and E. Pauwels, “Inexact subgradient methods for semialgebraic functions,” Math Program, pp. 1–27, Jun. 2025, https://doi.org/10.1007/s10107-025-02245-w
Source
Mathematical Programming, 1-27, 2025
Conference
Keywords
Inexact subgradient, Clarke subdifferential, Nonsmooth nonconvex optimization, Path differentiable functions, First-order methods, Semialgebraic functions
Subjects
Source
Publisher
Springer Nature