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

@misc{zhao2026optimal,
  title = {{On the Optimal Linear Minimization Oracle Complexity of Active-Hull Methods for Minimizing Convex Hölder Smooth Functions}},
  author = {Renbo Zhao},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2609.34101},
  eprint = {2609.34101},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.34101},
}

TY  - UNPB
TI  - On the Optimal Linear Minimization Oracle Complexity of Active-Hull Methods for Minimizing Convex Hölder Smooth Functions
AU  - Renbo Zhao
PY  - 2026
DA  - 2026/10/01
PB  - arXiv
DO  - 10.48550/arxiv.2609.34101
UR  - https://arxiv.org/abs/2609.34101
AB  - We consider the convex problem (P): min_y∈ ℝ^n f(Ay)+g(y), where A:ℝ^n→ ℝ^m is a linear operator, f is convex and (M,ν)-Hölder smooth on ℝ^m, and g is proper, closed convex on ℝ^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) is O(M^2/(1+ν)D^2ε^−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.
ER  -