Preconditioned subgradient method for composite optimization: overparameterization and fast convergence
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908574161043456 |
|---|---|
| author | Díaz, Mateo Jiang, Liwei Labassi, Abdel Ghani |
| author_facet | Díaz, Mateo Jiang, Liwei Labassi, Abdel Ghani |
| contents | Composite optimization problems involve minimizing the composition of a smooth map with a convex function. Such objectives arise in numerous data science and signal processing applications, including phase retrieval, blind deconvolution, and collaborative filtering. The subgradient method achieves local linear convergence when the composite loss is well-conditioned. However, if the smooth map is, in a certain sense, ill-conditioned or overparameterized, the subgradient method exhibits much slower sublinear convergence even when the convex function is well-conditioned. To overcome this limitation, we introduce a Levenberg-Morrison-Marquardt subgradient method that converges linearly under mild regularity conditions at a rate determined solely by the convex function. Further, we demonstrate that these regularity conditions hold for several problems of practical interest, including square-variable formulations, matrix sensing, and tensor factorization. Numerical experiments illustrate the benefits of our method. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_11486 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Preconditioned subgradient method for composite optimization: overparameterization and fast convergence Díaz, Mateo Jiang, Liwei Labassi, Abdel Ghani Optimization and Control Machine Learning 65K05, 65K10, 90C30, 90C06, 68U15 Composite optimization problems involve minimizing the composition of a smooth map with a convex function. Such objectives arise in numerous data science and signal processing applications, including phase retrieval, blind deconvolution, and collaborative filtering. The subgradient method achieves local linear convergence when the composite loss is well-conditioned. However, if the smooth map is, in a certain sense, ill-conditioned or overparameterized, the subgradient method exhibits much slower sublinear convergence even when the convex function is well-conditioned. To overcome this limitation, we introduce a Levenberg-Morrison-Marquardt subgradient method that converges linearly under mild regularity conditions at a rate determined solely by the convex function. Further, we demonstrate that these regularity conditions hold for several problems of practical interest, including square-variable formulations, matrix sensing, and tensor factorization. Numerical experiments illustrate the benefits of our method. |
| title | Preconditioned subgradient method for composite optimization: overparameterization and fast convergence |
| topic | Optimization and Control Machine Learning 65K05, 65K10, 90C30, 90C06, 68U15 |
| url | https://arxiv.org/abs/2509.11486 |