On the Optimal Linear Minimization Oracle Complexity of Active-Hull Methods for Minimizing Convex Hölder Smooth Functions
We consider the convex problem $(P): {\min}_{y\in \mathbb{R}^n}\, f(Ay)+g(y)$, where $A:\mathbb{R}^n\to \mathbb{R}^m$ is a linear operator, $f$ is convex and $(M,ν)$-Hölder smooth on $\mathbb{R}^m$, and $g$ is proper, closed convex on $\mathbb{R}^n$, and admits a (generalized) linear minimization oracle (LMO). An active-hull (AH) method calls the LMO in each iteration and outputs a point that lies in the convex hull of all the past LMO returns. We show that under the Euclidean geometry (and in the high-dimensional regime), the optimal LMO complexity for the class of AH methods to solve $(P)$…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.34101
curl -X POST /api/v1/records/arxiv/2609.34101/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.34101/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'