The Complexity of Convex Optimization with Mismatched Geometry
Optimal first-order methods on non-Euclidean domains such as the $\ell_1$ ball $B_1^n(R)=\{x\in\mathbb R^n:\|x\|_1\le R\}$ pair the prox-function with the norm in which smoothness is measured. When the gradient is $L$-Lipschitz in the Euclidean norm only, the accelerated method with a Euclidean prox-setup reduces the functional gap $f(x_N)-\min_{B_1^n(R)}f$ to $O(LR^2/N^2)$ after $N$ first-order queries (an entropic $\ell_1$ prox-setup replaces $L$ by the $\ell_1\to\ell_\infty$ constant $L_1\le L$, at the cost of a factor $\log n$ and with the same exponent). The lower bound of Guzmán and…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.32910
curl -X POST /api/v1/records/arxiv/2609.32910/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.32910/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'