Complexity of Linear Minimization and Projection on Some Sets

By Cyrille W. Combettes, Sebastian Pokutta. 2021

58 citations recorded by the source corpus.

Abstract The Frank-Wolfe algorithm is a method for constrained optimization relying on linear minimizations, as opposed to projections. Therefore, a motivation put forward in a large body of work on the Frank-Wolfe algorithm is the computational advantage of solving linear minimizations instead of projections. However, the discussions supporting this advantage are often incomplete. We review the complexity bounds for both tasks on several sets commonly used in optimization. Projection methods onto the l p -ball, p ∈ ] 1 , 2 [ ∪ ] 2 , + ∞ [ , and the Birkhoff polytope are also proposed.

Subfields: Computational Mechanics, Computational Theory and Mathematics, Numerical Analysis

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computational Theory and Mathematics

In Numerical Analysis

Citations in the corpus

Linear Bandits on Uniformly Convex Sets (2021, background): “Such projection-free schemes have several beneﬁts, e.g. , computational eﬃciency [CP21] but in the case of FTL they also do not require smoothness of the action set [Mol20] as opposed to Algorithm 1 which requires it to ensure diﬀerentiability of F K and F K ◦ simultaneously.”
The Frank-Wolfe Algorithm: A Short Introduction (2023, unknown): “This sub-routine only involves optimizing a linear function over the feasible region, often proving more cost-effective than traditional projections; see Combettes and Pokutta [24] for an in-depth comparison.”
Projection-Free Optimization on Uniformly Convex Sets (2020, methodology): “Each iteration requires to solve a Linear Minimization Oracle (see line 2 in Algorithm 1), instead of a projection or proximal operation that is not computationally competitive in various settings [Combettes and Pokutta, 2021].”