Optimal Methods for Unknown Piecewise Smooth Problems I: Convex Optimization
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918350092763136 |
|---|---|
| author | Lin, Zhenwei Zhang, Zhe |
| author_facet | Lin, Zhenwei Zhang, Zhe |
| contents | We introduce an optimal and nearly parameter-free algorithm for minimizing piecewise smooth (PWS) convex functions under the quadratic growth (QG) condition, where the locations and structure of the smooth regions are entirely \textit{unknown}. Our algorithm, \apex{} (Accelerated Prox-Level method for Exploring Piecewise Smoothness), is an accelerated bundle-level method designed to adaptively exploit the underlying PWS structure. APEX enjoys optimal theoretical guarantees, achieving a tight oracle complexity bound that matches the lower bound established in this work for convex PWS optimization. Furthermore, APEX generates a verifiable and accurate termination certificate, enabling a robust, almost parameter-free implementation. To the best of our knowledge, APEX is the first algorithm to simultaneously achieve the optimal convergence rate for PWS optimization and provide certificate guarantees. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_14680 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Optimal Methods for Unknown Piecewise Smooth Problems I: Convex Optimization Lin, Zhenwei Zhang, Zhe Optimization and Control 90C25, 49J52 We introduce an optimal and nearly parameter-free algorithm for minimizing piecewise smooth (PWS) convex functions under the quadratic growth (QG) condition, where the locations and structure of the smooth regions are entirely \textit{unknown}. Our algorithm, \apex{} (Accelerated Prox-Level method for Exploring Piecewise Smoothness), is an accelerated bundle-level method designed to adaptively exploit the underlying PWS structure. APEX enjoys optimal theoretical guarantees, achieving a tight oracle complexity bound that matches the lower bound established in this work for convex PWS optimization. Furthermore, APEX generates a verifiable and accurate termination certificate, enabling a robust, almost parameter-free implementation. To the best of our knowledge, APEX is the first algorithm to simultaneously achieve the optimal convergence rate for PWS optimization and provide certificate guarantees. |
| title | Optimal Methods for Unknown Piecewise Smooth Problems I: Convex Optimization |
| topic | Optimization and Control 90C25, 49J52 |
| url | https://arxiv.org/abs/2601.14680 |