Geometry-dependent matching pursuit: a transition phase for convergence on linear regression and LASSO
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911789539655680 |
|---|---|
| author | Moucer, Céline Taylor, Adrien Bach, Francis |
| author_facet | Moucer, Céline Taylor, Adrien Bach, Francis |
| contents | Greedy first-order methods, such as coordinate descent with Gauss-Southwell rule or matching pursuit, have become popular in optimization due to their natural tendency to propose sparse solutions and their refined convergence guarantees. In this work, we propose a principled approach to generating (regularized) matching pursuit algorithms adapted to the geometry of the problem at hand, as well as their convergence guarantees. Building on these results, we derive approximate convergence guarantees and describe a transition phenomenon in the convergence of (regularized) matching pursuit from underparametrized to overparametrized models. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_03072 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Geometry-dependent matching pursuit: a transition phase for convergence on linear regression and LASSO Moucer, Céline Taylor, Adrien Bach, Francis Optimization and Control 90C25, 68Y25, 60B20 Greedy first-order methods, such as coordinate descent with Gauss-Southwell rule or matching pursuit, have become popular in optimization due to their natural tendency to propose sparse solutions and their refined convergence guarantees. In this work, we propose a principled approach to generating (regularized) matching pursuit algorithms adapted to the geometry of the problem at hand, as well as their convergence guarantees. Building on these results, we derive approximate convergence guarantees and describe a transition phenomenon in the convergence of (regularized) matching pursuit from underparametrized to overparametrized models. |
| title | Geometry-dependent matching pursuit: a transition phase for convergence on linear regression and LASSO |
| topic | Optimization and Control 90C25, 68Y25, 60B20 |
| url | https://arxiv.org/abs/2403.03072 |