First Order Algorithm on an Optimization Problem with Improved Convergence when Problem is Convex
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912541801709568 |
|---|---|
| author | Sim, Chee-Khian |
| author_facet | Sim, Chee-Khian |
| contents | We propose a first order algorithm, a modified version of FISTA, to solve an optimization problem with an objective function that is a sum of a possibly nonconvex function, with Lipschitz continuous gradient, and a convex function which can be nonsmooth. The algorithm is shown to have an iteration complexity of $\mathcal{O}(ε^{-2})$ to find an $ε$-approximate solution to the problem, and this complexity improves to $\mathcal{O}(ε^{-2/3})$ when the objective function turns out to be convex. We further provide asymptotic convergence rate for the algorithm of worst case $o(ε^{-2})$ iterations to find an $ε$-approximate solution to the problem, with worst case $o(ε^{-2/3})$ iterations when its objective function is convex. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_13302 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | First Order Algorithm on an Optimization Problem with Improved Convergence when Problem is Convex Sim, Chee-Khian Optimization and Control We propose a first order algorithm, a modified version of FISTA, to solve an optimization problem with an objective function that is a sum of a possibly nonconvex function, with Lipschitz continuous gradient, and a convex function which can be nonsmooth. The algorithm is shown to have an iteration complexity of $\mathcal{O}(ε^{-2})$ to find an $ε$-approximate solution to the problem, and this complexity improves to $\mathcal{O}(ε^{-2/3})$ when the objective function turns out to be convex. We further provide asymptotic convergence rate for the algorithm of worst case $o(ε^{-2})$ iterations to find an $ε$-approximate solution to the problem, with worst case $o(ε^{-2/3})$ iterations when its objective function is convex. |
| title | First Order Algorithm on an Optimization Problem with Improved Convergence when Problem is Convex |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2508.13302 |