Optimal Convergence Rate for Mirror Descent Methods with special Time-Varying Step Sizes Rules
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866918043367505920 |
|---|---|
| author | Alkousa, Mohammad Stonyakin, Fedor Abdo, Asmaa Alcheikh, Mohammad |
| author_facet | Alkousa, Mohammad Stonyakin, Fedor Abdo, Asmaa Alcheikh, Mohammad |
| contents | In this paper, the optimal convergence rate $O\left(N^{-1/2}\right)$ (where $N$ is the total number of iterations performed by the algorithm), without the presence of a logarithmic factor, is proved for mirror descent algorithms with special time-varying step sizes, for solving classical constrained non-smooth problems, problems with the composite model and problems with non-smooth functional (inequality types) constraints. The proven result is an improvement on the well-known rate $O\left(\log (N) N^{-1/2}\right)$ for the mirror descent algorithms with the time-varying step sizes under consideration. It was studied a new weighting scheme assigns smaller weights to the initial points and larger weights to the most recent points. This scheme improves the convergence rate of the considered mirror descent methods, which in the conducted numerical experiments outperform the other methods providing a better solution in all the considered test problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_04754 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Optimal Convergence Rate for Mirror Descent Methods with special Time-Varying Step Sizes Rules Alkousa, Mohammad Stonyakin, Fedor Abdo, Asmaa Alcheikh, Mohammad Optimization and Control In this paper, the optimal convergence rate $O\left(N^{-1/2}\right)$ (where $N$ is the total number of iterations performed by the algorithm), without the presence of a logarithmic factor, is proved for mirror descent algorithms with special time-varying step sizes, for solving classical constrained non-smooth problems, problems with the composite model and problems with non-smooth functional (inequality types) constraints. The proven result is an improvement on the well-known rate $O\left(\log (N) N^{-1/2}\right)$ for the mirror descent algorithms with the time-varying step sizes under consideration. It was studied a new weighting scheme assigns smaller weights to the initial points and larger weights to the most recent points. This scheme improves the convergence rate of the considered mirror descent methods, which in the conducted numerical experiments outperform the other methods providing a better solution in all the considered test problems. |
| title | Optimal Convergence Rate for Mirror Descent Methods with special Time-Varying Step Sizes Rules |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2401.04754 |