Open Research Index

An optimal first-order method for smooth and strongly convex composite optimization and its stationary limit

Manu Upadhyaya, Daniel Berg Thomsen, Aymeric Dieuleveut, Adrien B. Taylor

arXivarxiv/2605.22929May 21, 2026math.OCscore 0

We introduce Prox-ITEM, an optimal proximal gradient method for minimizing $f+g$, where $f$ is smooth and strongly convex, and $g$ is convex, proper, and lower semicontinuous. In the smooth case $g=0$, Prox-ITEM reduces to the information-theoretic exact method (ITEM). We prove an exact distance-to-solution bound for Prox-ITEM with the same distance-convergence rate as ITEM, and show that this rate is minimax optimal among span-based first-order methods using the same number of gradient-oracle calls for $f$ and an arbitrary number of proximal-oracle calls for $g$. We also identify the…

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2605.22929
curl -X POST /api/v1/records/arxiv/2605.22929/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.22929/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'