When we seek to accelerate first-order optimization algorithms, we traditionally look to the properties of the objective function. We ask whether the function is strongly convex, or if its gradients are Lipschitz continuous. However, a powerful parallel paradigm has emerged: acceleration driven entirely by the geometric curvature of the constraint set.
This perspective is particularly transformative for projection-free optimization, such as the classic Frank-Wolfe (conditional gradient) method. By understanding how the boundary shape of a feasible region dictates algorithmic stability, we can achieve dramatic speedups without adding computational complexity.
The Intuition: Why Polytopes Cause Zig-Zagging
To understand why constraint curvature helps, we must first look at where projection-free methods struggle. Consider minimizing a smooth convex function over a polytope (a constraint set with flat faces and sharp corners, like a cube or simplex).
At each iteration, the Frank-Wolfe algorithm avoids expensive projection steps by solving a Linear Minimization Oracle (LMO):
$$\min_{s \in \mathcal{C}} \langle s, \nabla f(x_t) \rangle$$
Because the objective is linear and the constraint set $\mathcal{C}$ is a polytope, the solution $s_t$ will always be one of the extreme points—a vertex. As the algorithm approaches the true optimum, the gradient $\nabla f(x_t)$ changes direction slightly. This slight shift causes the LMO to abruptly jump from one vertex to an entirely different vertex on the other side of the optimum.
Consequently, the algorithm is forced to "zig-zag" back and forth between these discrete vertices. This chattering behavior acts as a fundamental bottleneck, dragging the convergence rate down to a relatively slow $O(1/t)$.
Polytopic Constraint (Flat Faces) Curved Constraint (Strongly Convex)
Vertex A Smoothly
o moving oracle
/ \ <-- Abrupt jumps .---''''---.
/ \ between vertices / \
/ x* \ | x* | <-- Continuous
/ \ \ / tracking
o---------o '---____---'
Vertex B Vertex C
How Curvature Smooths the Trajectory
Now, imagine replacing that polytope with a "round" constraint set, such as an $\ell_p$ ball where the boundary is strongly or uniformly convex.
When the constraint boundary is curved, a tiny change in the gradient $\nabla f(x_t)$ no longer causes a massive, discontinuous jump to a distant vertex. Instead, the optimal solution to the LMO slides continuously and smoothly along the curved surface of the boundary. This smooth tracking implicitly dampens the erratic zig-zagging behavior.
In their seminal paper, Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets, Garber et al. proved that this geometric phenomenon yields a massive theoretical upgrade. Without making any modifications to the vanilla Frank-Wolfe update rule, the convergence rate automatically jumps from $O(1/t)$ to a quadratic rate of $O(1/t^2)$. This acceleration is entirely dimension-independent and requires no additional computational overhead or memory-heavy modifications like "away steps."
This boundary-driven acceleration applies broadly across projection-free architectures. For instance, Rector-Brooks et al. demonstrated in Revisiting Projection-Free Optimization for Strongly Convex Constraint Sets that Primal Averaging algorithms similarly exploit strongly convex constraints to secure a state-of-the-art $O(1/t^2)$ convergence rate without requiring expensive line searches.
Local Curvature is Enough
Does the entire feasible region need to be perfectly round to achieve these faster rates? Fortunately, no.
In Projection-Free Optimization on Uniformly Convex Sets, d'Aspremont et al. extended this framework to uniformly convex sets (such as $\ell_p$ balls for $p > 2$). Crucially, the authors showed that global curvature is an unnecessarily strict requirement; the algorithm accelerates as long as the constraint set exhibits curvature locally, near the optimal solution. If the optimum resides on a curved portion of the boundary, the algorithm reaps the benefits of accelerated convergence, bridging the gap between sublinear and linear rates even if other regions of the set are flat.
This geometric stability also simplifies algorithmic tuning. Wirth et al. proved in Acceleration of Frank-Wolfe Algorithms with Open-Loop Step-Sizes that when the geometry is favorable, simple, pre-determined (open-loop) step sizes can actually outperform complex adaptive feedback loops, providing non-asymptotic $O(1/t^2)$ rates. However, the authors also highlighted the flip side of this geometric dependency: if the optimum happens to sit on a flat face of the constraint region, traditional algorithms lose this advantage and struggle to surpass sublinear efficiency.
Scaling to Momentum and Non-Euclidean Spaces
The principle of leveraging boundary geometry can be combined with other acceleration techniques or translated to non-Euclidean domains:
- Momentum Integration: Rather than choosing between geometric acceleration and Nesterov-style momentum, Li et al. developed A Momentum-Guided Frank-Wolfe Algorithm. By guiding the optimization direction with a momentum term over active norm-ball constraints, they consistently achieved quadratic convergence rates in a parameter-free manner.
- Manifold Optimization: In Strongly Convex Sets in Riemannian Manifolds, Scieur et al. formalized what it means for a constraint set to be strongly convex within a curved, non-Euclidean space. By introducing a "Riemannian Scaling Inequality," the authors proved that the Riemannian Frank-Wolfe algorithm can transition all the way to full linear convergence when operating on these well-behaved, round sets.
The Dual Nature of Boundary Geometry
While curvature acts as a powerful accelerator for projection-free minimization, its impact is highly context-dependent. In fact, changing the optimization objective from standard minimization to a saddle-point problem can completely invert the role of geometry.
In Linear Last-iterate Convergence in Constrained Saddle-point Optimization, Wei et al. analyzed optimistic gradient methods for constrained min-max games. Surprisingly, they discovered that for saddle-point dynamics, flat-faced boundaries like polytopes support exponential (linear) last-iterate convergence. Conversely, curved boundaries introduce a geometric bottleneck that degrades the convergence rate to sublinear performance.
This contrast underscores that constraint geometry is a fundamental physical property of the optimization landscape. Whether analyzing sensitivity to perturbations in semi-infinite optimization as explored by Bonnans et al., or computing large-scale market equilibria where constraint-derived Hoffman constants dictate step sizes as shown by Kroer et al., the shape of the boundary dictates the ultimate limits of algorithmic speed.
Key Foundational Work
Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets (2015) — contributed 2 concept elements to this direction.
Perturbed Optimization in Banach Spaces III: Semi-Infinite Optimization (1996) — contributed 1 concept elements to this direction.