A conditional-gradient single-loop augmented Lagrangian method achieves optimal convergence rates for minimizing a Lipschitz differentiable convex f plus convex h subject to smooth convex inequalities.
Lower Bounds for Frank-Wolfe on Strongly Convex Sets
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We present a constructive lower bound of $\Omega(1/\sqrt{\varepsilon})$ for Frank-Wolfe (FW) when both the objective and the constraint set are smooth and strongly convex, showing that the known uniform $\mathcal{O}(1/\sqrt{\varepsilon})$ guarantees in this regime are tight. It is known that under additional assumptions on the position of the optimizer, FW can converge linearly. However, it remained unclear whether strong convexity of the set can yield rates uniformly faster than $\mathcal{O}(1/\sqrt{\varepsilon})$, i.e., irrespective of the position of the optimizer. To investigate this question, we focus on a simple yet representative problem class: minimizing a strongly convex quadratic over the Euclidean unit ball, with the optimizer on the boundary. We analyze the dynamics of FW for this problem in detail and develop a novel computational approach to construct worst-case FW trajectories, which is of independent interest. Guided by these constructions, we develop an analytical proof establishing the lower bound.
fields
math.OC 1years
2026 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
A conditional-gradient-based single-loop augmented Lagrangian method for inequality constrained optimization
A conditional-gradient single-loop augmented Lagrangian method achieves optimal convergence rates for minimizing a Lipschitz differentiable convex f plus convex h subject to smooth convex inequalities.