Track new results across pure and applied mathematics.
Search papers, labs, and topics across Lattice.
This work establishes the optimal linear minimization oracle (LMO) complexity for active-hull methods optimizing convex composite objectives with $(M, \nu)$-Hölder smooth terms. The authors prove that the minimax rate in the high-dimensional regime is $O(M^{\frac{2}{1+\nu}}D^2\varepsilon^{-\frac{2}{1+\nu}})$, showing this tight bound is directly achievable by a single-loop first-order primal-dual splitting scheme. To address practical implementation barriers, they further design parameter-free meta-search algorithms that achieve this optimal bound up to a logarithmic factor without prior knowledge of the Hölder exponent or constant.
Active-hull and Frank-Wolfe-style algorithms can hit the theoretical lower bound for non-Lipschitz, Hölder-smooth optimization with a single-loop primal-dual split—even when smoothness parameters are entirely unknown.
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 %refers to the one that %is the one that that 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 in the high-dimensional regime, the optimal LMO complexity for the class of AH methods to solve $(P)$ is $O\big(M^{{2}/({1+ν})}D^2\varepsilon^{-{2}/({1+ν})}\big)$, where $D$ denotes the diameter of the feasible region and $\varepsilon$ 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.