Error bounds, PL condition, and quadratic growth for weakly convex functions, and linear convergences of proximal point methods
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912873920331776 |
|---|---|
| author | Liao, Feng-Yi Ding, Lijun Zheng, Yang |
| author_facet | Liao, Feng-Yi Ding, Lijun Zheng, Yang |
| contents | Many practical optimization problems lack strong convexity. Fortunately, recent studies have revealed that first-order algorithms also enjoy linear convergences under various weaker regularity conditions. While the relationship among different conditions for convex and smooth functions is well-understood, it is not the case for the nonsmooth setting. In this paper, we go beyond convexity and smoothness, and clarify the connections among common regularity conditions in the class of weakly convex functions, including $\textit{strong convexity}$, $\textit{restricted secant inequality}$, $\textit{subdifferential error bound}$, $\textit{Polyak-Łojasiewicz inequality}$, and $\textit{quadratic growth}$. In addition, using these regularity conditions, we present a simple and modular proof for the linear convergence of the proximal point method (PPM) for convex and weakly convex optimization problems. The linear convergence also holds when the subproblems of PPM are solved inexactly with a proper control of inexactness. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_16775 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Error bounds, PL condition, and quadratic growth for weakly convex functions, and linear convergences of proximal point methods Liao, Feng-Yi Ding, Lijun Zheng, Yang Optimization and Control Systems and Control Many practical optimization problems lack strong convexity. Fortunately, recent studies have revealed that first-order algorithms also enjoy linear convergences under various weaker regularity conditions. While the relationship among different conditions for convex and smooth functions is well-understood, it is not the case for the nonsmooth setting. In this paper, we go beyond convexity and smoothness, and clarify the connections among common regularity conditions in the class of weakly convex functions, including $\textit{strong convexity}$, $\textit{restricted secant inequality}$, $\textit{subdifferential error bound}$, $\textit{Polyak-Łojasiewicz inequality}$, and $\textit{quadratic growth}$. In addition, using these regularity conditions, we present a simple and modular proof for the linear convergence of the proximal point method (PPM) for convex and weakly convex optimization problems. The linear convergence also holds when the subproblems of PPM are solved inexactly with a proper control of inexactness. |
| title | Error bounds, PL condition, and quadratic growth for weakly convex functions, and linear convergences of proximal point methods |
| topic | Optimization and Control Systems and Control |
| url | https://arxiv.org/abs/2312.16775 |