Projection Free Optimization via Linear Minimization Oracles

664 concepts387 papers1 proposal

In constrained optimization, the traditional approach is to take a gradient step and then "snap" the result back into the feasible region. This snapping—known as a projection—is mathematically defined as finding the closest point in the feasible set $\mathcal{C}$ to your current iterate. While conceptually simple, this operation is often the primary computational bottleneck in high-dimensional machine learning.

Projection-free optimization, rooted in the Frank-Wolfe (or Conditional Gradient) algorithm, replaces these expensive projections with a much simpler operation: the Linear Minimization Oracle (LMO).

The Projection Bottleneck

To understand why projections fail at scale, consider a common constraint in signal processing: the nuclear norm ball (the set of matrices whose singular values sum to less than a threshold). As noted by Pedregosa et al., projecting a matrix onto this set requires a full Singular Value Decomposition (SVD), an $O(n^3)$ operation. When your matrix represents millions of users or items, this becomes intractable.

Moharrer argues in Distributing Frank-Wolfe via Map-Reduce that traditional interior-point methods and projection-based solvers struggle precisely because the cost of maintaining feasibility grows faster than the optimization progress itself. This creates a need for algorithms where the cost of staying within the constraints is significantly lower than the cost of the gradient update.

The Intuition of Linear Oracles

Instead of asking "What is the closest point in the set?" (a quadratic problem), projection-free methods ask "What is the most extreme point in the set in this direction?" (a linear problem).

Formally, an LMO solves: $$\text{argmin}_{s \in \mathcal{C}} \langle s, \nabla f(x) \rangle$$

For the nuclear norm ball mentioned earlier, this LMO only requires finding the top singular vector, which can be computed in $O(n^2)$ or less using iterative methods like the power method. As Hazan et al. highlight in Variance-Reduced and Projection-Free Stochastic Optimization, this shift from $O(n^3)$ to $O(n^2)$ allows algorithms to handle constraints that were previously considered "too expensive" for real-time applications.

Once the LMO identifies this extreme point $s$, the algorithm simply moves a small step toward it: $x_{t+1} = (1-\gamma)x_t + \gamma s$. Because both $x_t$ and $s$ are in the convex set $\mathcal{C}$, their convex combination is also guaranteed to be in $\mathcal{C}$. No projection is ever needed.

Accelerating Convergence

Historically, the "vanilla" Frank-Wolfe algorithm was criticized for its slow $O(1/t)$ convergence rate. However, recent research has shown that the geometry of the constraint set can be leveraged for speed.

Garber et al. demonstrate that if the feasible set is strongly convex (like an $\ell_p$ ball for $p \in (1, 2]$), the convergence rate improves quadratically to $O(1/t^2)$. Furthermore, Rector-Brooks et al. show that techniques like Primal Averaging can achieve these faster rates without the need for expensive line searches, making them highly efficient for large-scale problems like sparse recovery.

For more complex structures like polytopes, Gidel et al. prove that using "away-steps"—which allow the algorithm to move away from "bad" corners of the set—can lead to geometric (exponential) convergence for saddle-point problems.

Scaling to Stochastic and Online Settings

The projection-free philosophy is particularly potent when combined with stochastic gradients. Négiar et al. propose a Stochastic Frank-Wolfe variant that maintains a constant per-iteration cost regardless of the dataset size, which is critical for finite-sum minimization in deep learning.

In the realm of Online Convex Optimization (OCO), where decisions must be made sequentially, Hazan provides a unified framework in Introduction to Online Convex Optimization for achieving low "regret" without projections. This is extended to bandit settings (where only function values, not gradients, are known) by Garber et al., who achieve state-of-the-art performance for complex decision sets like large polytopes.

Beyond Convexity and Gradients

The utility of LMOs extends even to non-convex and derivative-free scenarios:

  • Zeroth-Order Optimization: Balasubramanian et al. and Sahu et al. show that one can estimate gradients using only function evaluations and still apply Frank-Wolfe updates, effectively optimizing "black-box" functions over complex constraints.
  • Submodular Maximization: For discrete-like problems, Chen et al. utilize a Black-box Continuous Greedy algorithm that replaces projections with linear optimization to achieve optimal approximation guarantees.
  • Distributed Systems: Wang et al. demonstrate that projection-free methods are naturally suited for decentralized learning, as they reduce the computational burden on individual nodes while maintaining differential privacy.

By shifting the focus from "staying close" to "moving in the right direction," projection-free methods enable the optimization of high-dimensional models that were once restricted by the geometric complexity of their constraints.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 409 papers
  2. Version 1 · 2026-10-04 · 348 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_projection_free_optimization_b309b6e3,
  title = {projection-free optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/projection-free-optimization/rdr_b309b6e35ffc48a989f0385f064c3c89},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_projection_free_optimization_b309b6e3_v2,
  title = {projection-free optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/projection-free-optimization/rdr_b309b6e35ffc48a989f0385f064c3c89/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake