Inexact subgradient methods for semialgebraic functions

Jérôme Bolte (1) , Tam Le (2) , Éric Moulines (3, 4) , Edouard Pauwels (1, 5)

1 TSE-R - Toulouse School of Economics
2 DAO - Données, Apprentissage et Optimisation
3 CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique
4 MBZUAI - Mohamed bin Zayed University of Artificial Intelligence
5 IUF - Institut universitaire de France

Motivated by the widespread use of approximate derivatives in machine learning and optimization, we study inexact subgradient methods with non-vanishing additive errors and step sizes. In the nonconvex semialgebraic setting, under boundedness assumptions, we prove that the method provides points that eventually fluctuate close to the critical set at a distance proportional to $\epsilon^\rho$ where $\epsilon$ is the error in subgradient evaluation and $\rho$ relates to the geometry of the problem. In the convex setting, we provide complexity results for the averaged values. We also obtain byproducts of independent interest, such as descent-like lemmas for nonsmooth nonconvex problems and some results on the limit of affine interpolants of differential inclusions.

Mots clés: Clarke subdifferential; Biased gradient; Semialgebraic optimization; Nonsmooth optimization; Differential inclusion

Domaines: Optimisation et contrôle [math.OC]; Machine Learning [stat.ML]

Jérôme Bolte, Tam Le, Éric Moulines, Edouard Pauwels. Inexact subgradient methods for semialgebraic functions. 2024. ⟨hal-04562371⟩