In constrained optimization, the Frank-Wolfe (FW) algorithm—also known as the Conditional Gradient method—is a favorite for its "projection-free" nature. Unlike projected gradient descent, which requires a computationally expensive projection step (often $O(n^3)$ or worse) to keep the solution within the feasible region, Frank-Wolfe only requires a Linear Minimization Oracle (LMO). This oracle finds a vertex of the feasible set that minimizes a linear approximation of the objective function.
However, as Gábor Braun, Sebastian Pokutta, and Daniel Zink point out in Lazifying Conditional Gradient Algorithms, even this linear subproblem can become a massive bottleneck. When the feasible region is defined by complex constraints—such as doubly stochastic matrices or high-dimensional polytopes—solving the LMO in every single iteration is prohibitively slow.
"Lazification" is the strategy of replacing these expensive, exact searches with a "good enough" shortcut.
The Intuition of the Weak Separation Oracle
The core insight of lazification is that we don't actually need the absolute best vertex in every step to make progress. We only need a vertex that provides "sufficient" descent relative to our current progress.
This is formalized through a Weak Separation Oracle. Instead of solving the full linear minimization problem: $$\min_{v \in \mathcal{C}} \langle \nabla f(x), v \rangle$$ the lazy algorithm asks a simpler question: "Is there a vertex $v$ in my cache, or easily findable, that satisfies a specific improvement threshold?"
If such a vertex exists, the algorithm takes the step immediately. It only triggers the expensive, full LMO as a last resort when the "lazy" options fail to meet the threshold. As shown in Conditional Accelerated Lazy Stochastic Gradient Descent by Guanghui Lan et al., this approach can improve convergence rates from $O(1/\epsilon^4)$ to $O(1/\epsilon^2)$ in stochastic settings by focusing computational effort where it matters most.
Caching and the Geometry of Progress
Why does this work so well in practice? In most optimization trajectories, the algorithm tends to move toward the same "neighborhood" of the feasible region's boundary. This means the vertices that were useful five iterations ago are likely to be useful again.
By maintaining a cache of previously identified vertices, lazified algorithms exploit this geometric redundancy. Mathieu Besançon, Alejandro Carderera, and Sebastian Pokutta demonstrate in their work on FrankWolfe.jl that cache hit rates often exceed 90%. In these cases, the algorithm avoids the expensive LMO for the vast majority of its runtime, leading to wall-clock speedups of several orders of magnitude.
This caching mechanism is particularly potent in:
- High-Dimensional Spaces: Where each LMO call involves a complex sub-solver.
- Active Set Methods: Such as Blended Pairwise Conditional Gradients, where Kazuma Tsuji and colleagues use lazification to handle infinite-dimensional problems like kernel herding.
- Branch-and-Bound Trees: In Boscia.jl, Wenjie Xiao and others show that vertices can be reused from parent nodes to child nodes, drastically reducing the cost of solving mixed-integer nonlinear programs.
Blending and Duality Gaps
To ensure that "lazy" doesn't mean "inaccurate," these algorithms use the Frank-Wolfe duality gap as a guide. The duality gap provides an upper bound on how far the current solution is from the optimum.
In Blended Conditional Gradients, Gábor Braun and Stephen Wright describe a mechanism where the algorithm "blends" different types of steps. It prioritizes cheap steps (using the cache or simplex-style descent) and only calls the full LMO when the estimated duality gap suggests that the current "lazy" progress is no longer sufficient to guarantee convergence.
This creates a self-regulating system: when the algorithm is far from the solution, almost any direction is "good enough," and the cache handles the work. As the algorithm nears the optimum and the requirements for progress become stricter, it naturally spends more time on precise LMO calls.
Broader Impact
The shift toward lazification represents a move from theoretical oracle complexity (counting the number of iterations) to practical wall-clock efficiency (minimizing total time). Whether it's applied to Robust Optimization by Jannis Kurtz or Quadratic Corrections by Jannis Halbey, the principle remains the same: by being strategically "lazy" and reusing historical computation, we can solve massive, constrained problems that were previously out of reach for exact methods.