Logo image
Back
On the Optimal Linear Minimization Oracle Complexity of Active-Hull Methods for Minimizing Convex Hölder Smooth Functions
Preprint   Open access

On the Optimal Linear Minimization Oracle Complexity of Active-Hull Methods for Minimizing Convex Hölder Smooth Functions

Renbo Zhao
arXiv
arXiv
09/28/2026
DOI: 10.48550/arxiv.2609.34101
url
https://doi.org/10.48550/arxiv.2609.34101View
Preprint (Author's original) This preprint has not been evaluated by subject experts through peer review. Preprints may undergo extensive changes and/or become peer-reviewed journal articles. Open Access

Abstract

We consider the convex problem (P ) : miny∈Rn f (Ay) + g(y), where A : Rn → Rm is a linear operator, f is convex and (M, ν)-H¨older smooth on Rm, and g is proper, closed convex on Rn, 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 ) is OM 2/(1+ν)D2ε−2/(1+ν) , where D denotes the diameter of the feasible region and ε denotes the objective sub-optimality gap. In particular, the optimal LMO complexity is achieved by a single-loop first-order primal- dual splitting method. Since this method requires knowledge of the problem parameters (e.g., M , D and ν), we propose two meta parameter-search algorithms that aim to resolve this issue. These algorithms are parameter-free, but come with the price of an additional log-factor in their LMO complexities.
Mathematics - Optimization and Control

Details

Metrics

1 Record Views
Logo image