Global non-asymptotic super-linear convergence rates of regularized proximal quasi-Newton methods on non-smooth composite problems
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912128369164288 |
|---|---|
| author | Wang, Shida Fadili, Jalal Ochs, Peter |
| author_facet | Wang, Shida Fadili, Jalal Ochs, Peter |
| contents | In this paper, we propose two regularized proximal quasi-Newton methods with symmetric rank-1 update of the metric (SR1 quasi-Newton) to solve non-smooth convex additive composite problems. Both algorithms avoid using line search or other trust region strategies. For each of them, we prove a super-linear convergence rate that is independent of the initialization of the algorithm. The cubic regularized method achieves a rate of order $\left(\frac{C}{N^{1/2}}\right)^{N/2}$, where $N$ is the number of iterations and $C$ is some constant, and the other gradient regularized method shows a rate of the order $\left(\frac{C}{N^{1/4}}\right)^{N/2}$. To the best of our knowledge, these are the first global non-asymptotic super-linear convergence rates for regularized quasi-Newton methods and regularized proximal quasi-Newton methods. The theoretical properties are also demonstrated in two applications from machine learning. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_11676 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Global non-asymptotic super-linear convergence rates of regularized proximal quasi-Newton methods on non-smooth composite problems Wang, Shida Fadili, Jalal Ochs, Peter Optimization and Control In this paper, we propose two regularized proximal quasi-Newton methods with symmetric rank-1 update of the metric (SR1 quasi-Newton) to solve non-smooth convex additive composite problems. Both algorithms avoid using line search or other trust region strategies. For each of them, we prove a super-linear convergence rate that is independent of the initialization of the algorithm. The cubic regularized method achieves a rate of order $\left(\frac{C}{N^{1/2}}\right)^{N/2}$, where $N$ is the number of iterations and $C$ is some constant, and the other gradient regularized method shows a rate of the order $\left(\frac{C}{N^{1/4}}\right)^{N/2}$. To the best of our knowledge, these are the first global non-asymptotic super-linear convergence rates for regularized quasi-Newton methods and regularized proximal quasi-Newton methods. The theoretical properties are also demonstrated in two applications from machine learning. |
| title | Global non-asymptotic super-linear convergence rates of regularized proximal quasi-Newton methods on non-smooth composite problems |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2410.11676 |