A Near-Optimal Total Complexity for the Inexact Accelerated Proximal Gradient Method via Quadratic Growth
We consider the optimization problem $\min_{x\in \mathbb R^n}{F(x):=f(x)+ω(Ax)}$, where $f$ is an $L$-Lipschitz smooth function, and $ω$ is a proper, lower semicontinuous, and convex function. We prove in this paper that when $ω$ is a conic polyhedral function, the inexact accelerated proximal gradient method (IAPG), employed in a double-loop structure, achieves a total complexity of $\mathcal O(\ln(1/\varepsilon)/\sqrt{\varepsilon})$ measured by the total number of calls to the proximal operator of the convex conjugate $ω^\star$ and the gradient of $f$ to achieve $\varepsilon$-optimality in…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2604.04551
curl -X POST /api/v1/records/arxiv/2604.04551/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.04551/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'