Inexact subgradient methods for semialgebraic functions
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915284548321280 |
|---|---|
| author | Bolte, Jérôme Le, Tam Moulines, Éric Pauwels, Edouard |
| author_facet | Bolte, Jérôme Le, Tam Moulines, Éric Pauwels, Edouard |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_19517 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Inexact subgradient methods for semialgebraic functions Bolte, Jérôme Le, Tam Moulines, Éric Pauwels, Edouard Optimization and Control Machine Learning 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. |
| title | Inexact subgradient methods for semialgebraic functions |
| topic | Optimization and Control Machine Learning |
| url | https://arxiv.org/abs/2404.19517 |