Frank–Wolfe and friends: a journey into projection-free first-order optimization methods

The present review is not intended to provide an exhaustive literature survey, but rather as an advanced tutorial demonstrating versatility and power of this approach. The article is structured as follows: in Sect. 2, we introduce the classic FW method, together with a general scheme for all the methods we consider. In Sect. 3, we present applications from classic optimization to more recent machine learning problems. In Sect. 4, we review some important stepsizes for first order methods. In Sect. 5, we discuss the main theoretical results about the FW method and the most popular variants, including the \({{\mathcal {O}}}(1/k)\) convergence rate for convex objectives, affine invariance, the sparse approximation property, and support identification. In Sect. 6 we illustrate some recent improvements on the \({{\mathcal {O}}}(1/k)\) convergence rate. Finally, in Sect. 7 we present recent FW variants fitting different optimization frameworks, in particular block coordinate, distributed, accelerated, and trace norm optimization. We highlight that all the proofs reported in the paper are either seminal, or simplified versions of proofs reported in published papers, and we believe they might give some useful technical insights to the interested reader.

For any integers a and b, denote by \([{a}\! : \! {b}] = \{ x \text{ integer }: a\le x\le b\}\) the integer range between them. For a set V, the power set \(2^V\) denotes the system all subsets of V, whereas for any positive integer \(s\in {\mathbb {N}}\) we set \({V\atopwithdelims ()s} := \{ S\in 2^V : |S| = s\}\), with |S| denoting the number of elements in S. Matrices are denoted by capital sans-serif letters (e.g., the zero matrix \({\mathsf {O}}\), or the \(n\times n\) identity matrix \({\mathsf {I}}_n\) with columns \({\mathsf {e}}_i\) the length of which should be clear from the context). The all-ones vector is \({\mathsf {e}}:=\sum _i {\mathsf {e}}_i\in {\mathbb {R}}^n\). Generally, vectors are always denoted by boldface sans-serif letters \({\mathsf {x}}\), and their transpose by \({\mathsf {x}} ^{\intercal }\). The Euclidean norm of \({\mathsf {x}}\) is then \(\Vert {\mathsf {x}} \Vert := \sqrt{{\mathsf {x}} ^{\intercal }{\mathsf {x}}}\) whereas the general p-norm is denoted by \({\Vert {\mathsf {x}} \Vert }_p\) for any \(p\ge 1\) (so \({\Vert {\mathsf {x}} \Vert }_2=\Vert {\mathsf {x}} \Vert \)). By contrast, the so-called zero-norm simply counts the number of nonzero entries:For a vector \({\mathsf {d}}\) we denote as \({\widehat{{\mathsf {d}}}} :=\frac{1}{\Vert {\mathsf {d}} \Vert }\,{\mathsf {d}}\) its normalization, with the convention \({\widehat{{\mathsf {d}}}} = {\mathsf {o}}\) if \({\mathsf {d}}= {\mathsf {o}}\). Here \({\mathsf {o}}\) denotes the zero vector. In context of symmetric matrices, “\({{\,\mathrm{psd}\,}}\)” abbreviates “positive-semidefinite”.

The classical FW method for minimization of a smooth objective f generates a sequence of feasible points \(\{{\mathsf {x}}_k\}\) following the scheme of Algorithm 2. At the iteration k it moves toward a vertex i.e., an extreme point, of the feasible set minimizing the scalar product with the current gradient \(\nabla f({\mathsf {x}}_k)\). It therefore makes use of a linear minimization oracle (LMO) for the feasible set \(C\)defining the descent direction asIn particular, the update at step 6 in Algorithm 2 can be written asSince \(\alpha _k \in [0, 1]\), by induction \({\mathsf {x}}_{k + 1}\) can be written as a convex combination of elements in the set \(S_{k + 1} := \{{\mathsf {x}}_0\} \cup \{{\mathsf {s}}_i\}_{0 \le i \le k}\). When \(C = {{\,\mathrm{conv}\,}}(A)\) for a set A of points with some common property, usually called “elementary atoms”, if \(x_0 \in A\) then \(x_{k}\) can be written as a convex combination of \(k + 1\) elements in A. Note that due to Caratheodory’s theorem, we can even limit the number of occurring atoms to \(\min \{k,n\}+1\). In the rest of the paper the primal gap at iteration k is defined as \(h_k=f({\mathsf {x}}_k)-f^*\).

Finding a traffic pattern satisfying the equilibrium conditions in a transportation network is a classic problem in optimization that dates back to Wardrop’s paper (Wardrop 1952). Let \({\mathcal {G}}\) be a network with set of nodes \([{1}\! : \! {n}]\). Let \(\{D(i, j)\}_{i \ne j}\) be demand coefficients, modeling the amount of goods with destination j and origin i. For any i, j with \(i\ne j\) let furthermore \(f_{ij}: {\mathbb {R}}\rightarrow {\mathbb {R}}\) be the non-linear (convex) cost functions, and \(x_{ij}^s\) be the flow on link (i, j) with destination s. The traffic assignment problem can be modeled as the following non-linear multicommodity network problem (Fukushima 1984):Then the linearized optimization subproblem necessary to compute the FW vertex takes the formand can be split in n shortest paths subproblems, each of the formfor a fixed \(s \in [{1}\! : \! {n}]\), with \(c_{ij}\) the first-order derivative of \(f_{ij}\) (see Fukushima 1984 for further details). A number of FW variants were proposed in the literature for efficiently handling this kind of problems (see, e.g., Bertsekas 2015; Fukushima 1984; LeBlanc et al. 1975; Mitradjieva and Lindberg 2013; Weintraub et al. 1985 and references therein for further details). Some of those variants represent a good (if not the best) choice when low or medium precision is required in the solution of the problem (Perederieieva et al. 2015).

In the more recent work Joulin et al. (2014) a FW variant also solving a shortest path subproblem at each iteration was applied to image and video co-localization.

Given a finite set V, a function \(r: 2^V \rightarrow {\mathbb {R}}\) is said to be submodular if for every \(A, B \subset V\)As is common practice in the optimization literature (see e.g. Bach 2013, Section 2.1), here we always assume \(s(\emptyset ) = 0\). A number of machine learning problems, including image segmentation and sensor placement, can be cast as minimization of a submodular function (see, e.g., Bach 2013; Chakrabarty et al. 2014 and references therein for further details):Submodular optimization can also be seen as a more general way to relate combinatorial problems to convexity, for example for structured sparsity (Bach 2013; Jaggi 2013). By a theorem from Fujishige (1980), problem (9) can be in turn reduced to an minimum norm point problem over the base polytopeFor this polytope, linear optimization can be achieved with a simple greedy algorithm. More precisely, consider the LPThen if the objective vector \({\mathsf {w}}\) has a negative component, the problem is clearly unbounded. Otherwise, a solution to the LP can be obtained by ordering \({\mathsf {w}}\) in decreasing manner as \(w_{j_1} \ge w_{j_2} \ge ... \ge w_{j_n}\), and settingfor \(k \in [{1}\! : \! {n}]\). We thus have a LMO with a \({\mathcal {O}}(n\log n)\) cost. This is the reason why FW variants are widely used in the context of submodular optimization; further details can be found in, e.g., Bach (2013), Jaggi (2013).

The LASSO, proposed by Tibshirani in 1996 (Tibshirani 1996), is a popular tool for sparse linear regression. Given the training setwhere \({\mathsf {r}}_i ^{\intercal }\) are the rows of an \(m\times n\) matrix \({\mathsf {A}}\), the goal is finding a sparse linear model (i.e., a model with a small number of non-zero parameters) describing the data. This problem is strictly connected with the Basis Pursuit Denoising (BPD) problem in signal analysis (see, e.g., Chen et al. 2001). In this case, given a discrete-time input signal b, and a dictionaryof elementary discrete-time signals, usually called atoms (here \({\mathsf {a}}_j\) are the columns of a matrix \({\mathsf {A}}\)), the goal is finding a sparse linear combination of the atoms that approximate the real signal. From a purely formal point of view, LASSO and BPD problems are equivalent, and both can be formulated as follows:where the parameter \(\tau \) controls the amount of shrinkage that is applied to the model (related to sparsity, i.e., the number of nonzero components in \({\mathsf {x}}\)). The feasible set isThus we have the following LMO in this case:with \(i_k \in \displaystyle {\mathop {{{\,\mathrm{arg\,max}\,}}}\limits _{i}} |\nabla _i f({\mathsf {x}}_k)|\). It is easy to see that the FW per-iteration cost is then \({\mathcal {O}}(n)\). The peculiar structure of the problem makes FW variants well-suited for its solution. This is the reason why LASSO/BPD problems were considered in a number of FW-related papers (see, e.g., Jaggi 2011, 2013; Lacoste-Julien and Jaggi 2015; Locatello et al. 2017).

Matrix completion is a widely studied problem that comes up in many areas of science and engineering, including collaborative filtering, machine learning, control, remote sensing, and computer vision (just to name a few; see also Candès and Recht (2009) and references therein). The goal is to retrieve a low rank matrix \({\mathsf {X}}\in {\mathbb {R}}^{n_1 \times n_2}\) from a sparse set of observed matrix entries \(\{U_{ij}\}_{(i,j) \in J}\) with \(J \subset [{1}\! : \! {n_1}] \times [{1}\! : \! {n_2}]\). Thus the problem can be formulated as follows (Freund et al. 2017):where the function f is given by the squared loss over the observed entries of the matrix and \(\delta >0\) is a parameter representing the assumed belief about the rank of the reconstructed matrix we want to get in the end. In practice, the low rank constraint is relaxed with a nuclear norm ball constraint, where we recall that the nuclear norm \({\Vert {\mathsf {X}} \Vert }_*\) of a matrix \({\mathsf {X}}\) is equal the sum of its singular values. Thus we get the following convex optimization problem:The feasible set is the convex hull of rank-one matrices:If we indicate with \({\mathsf {A}}_J\) the matrix that coincides with \({\mathsf {A}}\) on the indices J and is zero otherwise, then we can write \(\nabla f({\mathsf {X}})={2}\,({\mathsf {X}}-{\mathsf {U}})_J\). Thus we have the following LMO in this case:which boils down to computing the gradient, and the rank-one matrix \(\delta {\mathsf {u}}_1 {\mathsf {v}}_1 ^{\intercal }\), with \({\mathsf {u}}_1, {\mathsf {v}}_1\) right and left singular vectors corresponding to the top singular value of \(-\nabla f({\mathsf {X}}_k)\). Consequently, the FW method at a given iteration approximately reconstructs the target matrix as a sparse combination of rank-1 matrices. Furthermore, as the gradient matrix is sparse (it only has |J| non-zero entries) storage and approximate singular vector computations can be performed much more efficiently than for dense matrices¹. A number of FW variants has hence been proposed in the literature for solving this problem (see, e.g., Freund et al. 2017; Jaggi 2011, 2013).

Adversarial examples are maliciously perturbed inputs designed to mislead a properly trained learning machine at test time. An adversarial attack hence consists in taking a correctly classified data point \(x_0\) and slightly modifying it to create a new data point that leads the considered model to misclassification (see, e.g., Carlini and Wagner 2017; Chen et al. 2017; Goodfellow et al. 2014 for further details). A possible formulation of the problem (see, e.g., Chen et al. 2020; Goodfellow et al. 2014) is given by the so called maximum allowable \(\ell _p\)-norm attack that is,where f is a suitably chosen attack loss function, \({\mathsf {x}}_0\) is a correctly classified data point, \({\mathsf {x}}\) represents the additive noise/perturbation, \(\varepsilon > 0\) denotes the magnitude of the attack, and \(p\ge 1\). It is easy to see that the LMO has a cost \({\mathcal {O}}(n)\). If \({\mathsf {x}}_0\) is a feature vector of a dog image correctly classified by our learning machine, our adversarial attack hence suitably perturbs the feature vector (using the noise vector \({\mathsf {x}}\)), thus getting a new feature vector \({\mathsf {x}}_0+{\mathsf {x}}\) classified, e.g., as a cat. In case a target adversarial class is specified by the attacker, we have a targeted attack. In some scenarios, the goal may not be to push \({\mathsf {x}}_0\) to a specific target class, but rather push it away from its original class. In this case we have a so called untargeted attack. The attack loss function f will hence be chosen depending on the kind of attack we aim to perform over the considered model. Due to its specific structure, problem (16) can be nicely handled by means of tailored FW variants. Some FW frameworks for adversarial attacks were recently described in, e.g., Chen et al. (2020), Kazemi et al. (2021), Sahu and Kar (2020).

Given a set of points \(P = \{{\mathsf {p}}_1,\ldots , {\mathsf {p}}_n\}\subset {\mathbb {R}}^d\), the minimum enclosing ball problem (MEB, see, e.g., Clarkson 2010; Yıldırım 2008) consists in finding the smallest ball containing P. Such a problem models numerous important applications in clustering, nearest neighbor search, data classification, machine learning, facility location, collision detection, and computer graphics, to name just a few. We refer the reader to Kumar et al. (2003) and the references therein for further details. Denoting by \({\mathsf {c}}\in {\mathbb {R}}^d\) the center and by \(\sqrt{\gamma }\) (with \(\gamma \ge 0\)) the radius of the ball, a convex quadratic formulation for this problem isThis problem can be formulated via Lagrangian duality as a convex Standard Quadratic Optimization Problem (StQP, see, e.g. Bomze and de Klerk 2002)with \({\mathsf {A}}= [{\mathsf {p}}_1, ..., {\mathsf {p}}_n]\) and \({\mathsf {b}} ^{\intercal }= [{\mathsf {p}}_1^{\intercal }{\mathsf {p}}_1, \ldots , {\mathsf {p}}_n^{\intercal }{\mathsf {p}}_n]\). The feasible set is the standard simplexand the LMO is defined as follows:with \(i_k \in {\mathop {{{\,\mathrm{arg\,min}\,}}}\nolimits _{i}} \nabla _i f({\mathsf {x}}_k)\). It is easy to see that cost per iteration is \({\mathcal {O}}(n)\). When applied to (19), the FW method can find an \(\varepsilon \)-cluster in \({{\mathcal {O}}}(\frac{1}{\varepsilon })\), where an \(\varepsilon \)-cluster is a subset \(P'\) of P such that the MEB of \(P'\) dilated by \(1 + \varepsilon \) contains P (Clarkson 2010). The set \(P'\) is given by the atoms in P selected by the LMO in the first \({{\mathcal {O}}}(\frac{1}{\varepsilon })\) iterations. Further details related to the connections between FW methods and MEB problems can be found in, e.g., Ahipaşaoğlu et al. (2008), Ahipaşaoğlu and Todd (2013), Clarkson (2010) and references therein.

Support Vector Machines (SVMs) represent a very important class of machine learning tools (see, e.g., Vapnik 2013 for further details). Given a labeled set of data points, usually called training set:the linear SVM training problem consists in finding a linear classifier \({\mathsf {w}}\in {\mathbb {R}}^d\) such that the label \(y_i\) can be deduced with the “highest possible confidence” from \({\mathsf {w}}^{\intercal }{\mathsf {p}}_i\). A convex quadratic formulation for this problem is the following Clarkson (2010):where the slack variable \(\rho \) stands for the negative margin and we can have \(\rho < 0\) if and only if there exists an exact linear classifier, i.e. \({\mathsf {w}}\) such that \({\mathsf {w}}^\intercal {\mathsf {p}}_i = {{\,\mathrm{sign}\,}}(y_i)\). The dual of (20) is again an StQP:with \({\mathsf {A}}= [y_1{\mathsf {p}}_1, ..., y_n{\mathsf {p}}_n]\). Notice that problem (21) is equivalent to an MNP problem on \( {{\,\mathrm{conv}\,}}\{ y_i{\mathsf {p}}_i : i\in [{1}\! : \! {n}]\}\), see Sect. 7.2 below. Some FW variants (like, e.g., the Pairwise Frank–Wolfe) are closely related to classical working set algorithms, such as the SMO algorithm used to train SVMs (Lacoste-Julien and Jaggi 2015). Further details on FW methods for SVM training problems can be found in, e.g., Clarkson (2010), Jaggi (2011).

In the context of network analysis the clique model, dating back at least to the work of Luce and Perry (1949) about social networks, refers to subsets with every two elements in a direct relationship. The problem of finding maximal cliques has numerous applications in domains including telecommunication networks, biochemistry, financial networks, and scheduling (see, e.g., Bomze et al. 1999; Wu and Hao 2015). Let \(G=(V,E)\) be a simple undirected graph with V and E set of vertices and edges, respectively. A clique in G is a subset \(C\subseteq V\) such that \((i,j)\in E\) for each \((i,j)\in C\), with \(i\ne j\). The goal in finding a clique C such that it is maximal (i.e., it is not contained in any strictly larger clique). This corresponds to find a local solution to the following equivalent (this time non-convex) StQP (see, e.g., Bomze 1997; Bomze et al. 1999; Hungerford and Rinaldi 2019 for further details):where \({\mathsf {A}}_G\) is the adjacency matrix of G. Due to the peculiar structure of the problem, FW methods can be fruitfully used to find maximal cliques (see, e.g., Hungerford and Rinaldi 2019).

Given a non-empty polyhedron \(P\subset {\mathbb {R}}^n\), the goal is finding a sparse point \({\mathsf {x}}\in P\) (i.e., a point with as many zero components as possible). This sparse optimization problem can be used to model a number of real-world applications in fields like, e.g., machine learning, pattern recognition and signal processing (see Rinaldi et al. 2010 and references therein). Ideally, what we would like to get is an optimal solution for the following problem:Since the zero norm is non-smooth, a standard procedure is to replace the original formulation (23) with an equivalent concave optimization problem of the form:where \(\phi :\left[ 0\right. \!, +\infty \left[ \right. \rightarrow {\mathbb {R}}\) is a suitably chosen smooth concave univariate function bounded from below, like, e.g.,with \(\alpha \) a large enough positive parameter (see, e.g., Mangasarian 1996; Rinaldi et al. 2010 for further details). The LMO in this case gives a vertex solution for the linear programming problem:with \(({{\mathsf {c}}}_k)_i\) the first-order derivative of \(\phi \) calculated in \(({{\mathsf {y}}}_k)_i\). Variants of the unit-stepsize FW method have been proposed in the literature (see, e.g., Mangasarian 1996; Rinaldi et al. 2010) to tackle the smooth equivalent formulation (24).

A key parameter often used as a measure of convergence is the FW gapwhich is always nonnegative and equal to 0 only in first order stationary points. This gap is, by definition, readily available during the algorithm. If f is convex, using that \(\nabla f({\mathsf {x}})\) is a subgradient we obtainso that \(G({\mathsf {x}})\) is an upper bound on the optimality gap at \({\mathsf {x}}\). Furthermore, \(G({\mathsf {x}})\) is a special case of the Fenchel duality gap (Lacoste-Julien et al. 2013).

If \(C=\varDelta _{n - 1}\) is the simplex, then G is related to the Wolfe dual as defined in Clarkson (2010). Indeed, this variant of Wolfe’s dual readsand for a fixed \({\mathsf {x}}\in {\mathbb {R}}^n\), the optimal values of \(({\mathsf {u}}, {\lambda })\) arePerforming maximization in problem (34) iteratively, first for \(({\mathsf {u}},\lambda )\) and then for \({\mathsf {x}}\), this implies that (34) is equivalent toFurthermore, since Slater’s condition is satisfied, strong duality holds by Slater’s theorem (Boyd et al. 2004), resulting in \( G({\mathsf {x}}^*) = 0\) for every solution \({\mathsf {x}}^*\) of the primal problem.

The FW gap is related to several other measures of convergence (see e.g. Lan 2020, Section 7.5.1). First, consider the projected gradientwith \(\pi _{B}\) the projection on a convex and closed subset \(B\subseteq {\mathbb {R}}^n\). We have \(\Vert {\widetilde{{\mathsf {g}}}}_k \Vert = 0\) if and only if \({\mathsf {x}}_k\) is stationary, withwhere we used \([{\mathsf {y}}- \pi _{C}({\mathsf {x}})]^\intercal [{\mathsf {x}}- \pi _{C}({\mathsf {x}})] \le 0\) in the first inequality, with \({\mathsf {x}}= {\mathsf {x}}_k - \nabla f({\mathsf {x}}_k)\) and \({\mathsf {y}}= {\mathsf {x}}_k\).

Let now \(N_{C}(x)\) denote the normal cone to \(C\) at a point \({\mathsf {x}}\in C\):First-order stationarity conditions are equivalent to \( - \nabla f({\mathsf {x}}) \in N_{C}({\mathsf {x}})\), orThe FW gap provides a lower bound on the distance from the normal cone \({{\,\mathrm{dist}\,}}(N_{C}({\mathsf {x}}), - \nabla f({\mathsf {x}}))\), inflated by the diameter \(D>0\) of \(C\), as follows:where in the first inequality we used \(({\mathsf {s}}_k - {\mathsf {x}}_k)^\intercal [\pi _{N_{C}({\mathsf {x}}_k)}(-\nabla f({\mathsf {x}}_k))] \le 0\) together with the Cauchy-Schwarz inequality, and \(\Vert {\mathsf {s}}_k - {\mathsf {x}}_k \Vert \le D\) in the second.

If f is non-convex, it is possible to prove a \({{\mathcal {O}}}(1/\sqrt{k})\) rate for \(\min _{i \in [1:k]} G(x_i)\) (see, e.g., Lacoste-Julien 2016). On the other hand, if f is convex, we have an \({{\mathcal {O}}}(1/k)\) rate on the optimality gap (see, e.g., Frank and Wolfe 1956; Levitin and Polyak 1966) for all the stepsizes discussed in Sect 4. Here we include a proof for the Lipschitz constant dependent stepsize \(\alpha _k\) given by (28).

Before proving the theorem we prove a lemma concerning the decrease of the objective in the case of a full FW step, that is a step with \({\mathsf {d}}_k = {\mathsf {d}}_k^{FW}\) and with \(\alpha _k\) equal to 1, the maximal feasible stepsize.

We can now proceed with the proof of the main result.

As can be easily seen from above argument, the convergence rate of \({{\mathcal {O}}}(1/k)\) is true also in more abstract normed spaces than \({\mathbb {R}}^n\), e.g. when \(C\) is a convex and weakly compact subset of a Banach space (see, e.g., Demyanov and Rubinov 1970; Dunn and Harshbarger 1978). A generalization for some unbounded sets is given in Ferreira and Sosa (2021). The bound is tight due to a zigzagging behaviour of the method near solutions on the boundary, leading to a rate of \(\varOmega (1/k^{1 + \delta })\) for every \(\delta > 0\) (see Canon and Cullum 1968 for further details), when the objective is a strictly convex quadratic function and the domain is a polytope.

Also the minimum FW gap \(\min _{i \in [0: k]} G({\mathsf {x}}_i) \) converges at a rate of \({{\mathcal {O}}}(1/k)\) (see Jaggi 2013; Freund and Grigas 2016). In Freund and Grigas (2016), a broad class of stepsizes is examined, including \(\alpha _k= \frac{1}{k + 1}\) and \(\alpha _k = {\bar{\alpha }}\) constant. For these stepsizes a convergence rate of \({{\mathcal {O}}}\left( \frac{\ln (k)}{k}\right) \) is proved.

Active set FW variants mostly aim to improve over the \({{\mathcal {O}}}(1/k)\) rate and also ensure support identification in finite time. They generate a sequence of active sets \(\{A_k\}\), such that \({\mathsf {x}}_k \in {{\,\mathrm{conv}\,}}(A_k)\), and define alternative directions making use of these active sets.

For the pairwise FW (PFW) and the away step FW (AFW) (see Clarkson 2010; Lacoste-Julien and Jaggi 2015) we have that \(A_k\) must always be a subset of \(S_k\), with \({\mathsf {x}}_k\) a convex combination of the elements in \(A_k\). The away vertex \({\mathsf {v}}_k\) is then defined byThe AFW direction, introduced in Wolfe (1970), is hence given bywhile the PFW direction, as defined in Lacoste-Julien and Jaggi (2015) and inspired by the early work (Mitchell et al. 1974), iswith \({\mathsf {s}}_k\) defined in (3).

The FW method with in-face directions (FDFW) (see Freund et al. 2017; Guélat and Marcotte 1986), also known as Decomposition invariant Conditional Gradient (DiCG) when applied to polytopes (Bashiri and Zhang 2017), is defined exactly as the AFW, but with the minimal face \({\mathcal {F}}({\mathsf {x}}_k)\) of \(C\) containing \({\mathsf {x}}_k\) as the active set. The extended FW (EFW) was introduced in Holloway (1974) and is also known as simplicial decomposition (Von Hohenbalken 1977). At every iteration the method minimizes the objective in the current active set \(A_{k + 1}\)where \(A_{k + 1} \subseteq A_k \cup \{s_k\}\) (see, e.g., Clarkson 2010, Algorithm 4.2). A more general version of the EFW, only approximately minimizing on the current active set, was introduced in Lacoste-Julien and Jaggi (2015) under the name of fully corrective FW. In Table 1, we report the main features of the classic FW and of the variants under analysis.

As discussed in the previous section, for the classic FW method and the AFW, PFW, EFW variants \({\mathsf {x}}_k\) can always be written as a convex combination of elements in \(A_k \subset S_k\), with \(|A_k| \le k + 1\). Even for the FDFW we still have the weaker property that \({\mathsf {x}}_k\) must be an affine combination of elements in \(A_k \subset A\) with \( |A_k| \le k + 1\). It turns out that the convergence rate of methods with this property is \(\varOmega (\frac{1}{k})\) in high dimension. More precisely, if \(C= {{\,\mathrm{conv}\,}}(A)\) with A compact, the \({{\mathcal {O}}}(1/k)\) rate of the classic FW method is worst case optimal given the sparsity constraintAn example where the \({{\mathcal {O}}}(1/k)\) rate is tight was presented in Jaggi (2013). Let \(C= \varDelta _{n - 1}\) and \(f({\mathsf {x}}) = \Vert {\mathsf {x}}- \frac{1}{n}\, {\mathsf {e}} \Vert ^2\). Clearly, \(f^* = 0\) with \({\mathsf {x}}^* = \frac{1}{n}\, {\mathsf {e}}\). Then it is easy to see that \(\min \{f({\mathsf {x}}) - f^* : {\Vert {\mathsf {x}}\Vert }_0 \le k + 1 \} \ge \frac{1}{k + 1} - \frac{1}{n}\) for every \(k \in {\mathbb {N}}\), so that in particular under (52) with \(A_k = \{e_i : i \in [{1}\! : \! {n}]\}\), the rate of any FW variant must be \(\varOmega (\frac{1}{k})\).

The FW method and the AFW, PFW, EFW are affine invariant (Jaggi 2013). More precisely, let \({\mathsf {P}}\) be a linear transformation, \({\hat{f}}\) be such that \({\hat{f}}({\mathsf {P}}{\mathsf {x}}) = f({\mathsf {x}})\) and \({\hat{C}} = {\mathsf {P}}(C)\). Then for every sequence \(\{{\mathsf {x}}_k\}\) generated by the methods applied to \((f, C)\), the sequence \(\{{\mathsf {y}}_k\} := \{{\mathsf {P}}{\mathsf {x}}_k\}\) can be generated by the FW method with the same stepsizes applied to \(({\hat{f}}, {\hat{C}})\). As a corollary, considering the special case where \({\mathsf {P}}\) is the matrix collecting the elements of A as columns, one can prove results on \(C= \varDelta _{|A| - 1}\) and generalize them to \({\hat{C}}:= {{\,\mathrm{conv}\,}}(A)\) by affine invariance.

An affine invariant convergence rate bound for convex objectives can be given using the curvature constantIt is easy to prove that \(\kappa _{f, C} \le LD^2\) if D is the diameter of \(C\). In the special case where \(C= \varDelta _{n - 1}\) and \(f({\mathsf {x}}) = {\mathsf {x}}^\intercal {\tilde{{\mathsf {A}}}}^\intercal {\tilde{{\mathsf {A}}}} {\mathsf {x}}+ {\mathsf {b}} ^{\intercal }{\mathsf {x}}\), then \(\kappa _{f, C} \le {{\,\mathrm{diam}\,}}({\mathsf {A}}\varDelta _{n - 1})^2\) for \({\mathsf {A}} ^{\intercal }= [{\tilde{{\mathsf {A}}}} ^{\intercal }, {\mathsf {b}}]\); see Clarkson (2010).

When the method uses the stepsize sequence (25), it is possible to give the following affine invariant convergence rate bounds (see Freund and Grigas 2016):thus in particular slightly improving the rate we gave in Theorem 1 since we have that \(\kappa _{f, C} \le LD^2\).

It is a classic result that the AFW under some strict complementarity conditions and for strongly convex objectives identifies in finite time the face containing the solution (Guélat and Marcotte 1986). Here we report some explicit bounds for this property proved in Bomze et al. (2020). We first assume that \(C= \varDelta _{n - 1}\), and introduce the multiplier functionsfor \(i \in [{1}\! : \! {n}]\). Let \({\mathsf {x}}^*\) be a stationary point for f, with the objective f not necessarily convex. It is easy to check that \(\{\lambda _i({\mathsf {x}}^*)\}_{i \in [1:n]}\) coincide with the Lagrangian multipliers. Furthermore, by complementarity conditions we have \(x^*_i \lambda _i({\mathsf {x}}^*) = 0\) for every \(i \in [{1}\! : \! {n}]\). It follows that the setcontains the support of \({\mathsf {x}}^*\), The next lemma uses \(\lambda _i\), and the Lipschitz constant L of \(\nabla f\), to give a lower bound of the so-called active set radius \(r_*\), defining a neighborhood of \({\mathsf {x}}^*\). Starting the algorithm in this neighbourhood, the active set (the minimal face of \(C\) containing \({\mathsf {x}}^*\)) is identified in a limited number of iterations.

The above lemma does not require convexity and was applied in Bomze et al. (2020) to derive active set identification bounds in several convex and non-convex settings. Here we focus on the case where the domain \(C= {{\,\mathrm{conv}\,}}(A)\) with \(|A| < + \infty \) is a generic polytope, and where f is \(\mu \)-strongly convex for some \(\mu >0\), i.e. Let \(E_{C}({\mathsf {x}}^*)\) be the face of \(C\) exposed by \(\nabla f(x^*)\):Let then \(\theta _{A}\) be the Hoffman constant (see Beck and Shtern 2017) related to \([{\bar{{\mathsf {A}}}} ^{\intercal }, {\mathsf {I}}_n, {\mathsf {e}}, -{\mathsf {e}}] ^{\intercal }\), with \({\bar{{\mathsf {A}}}}\) the matrix having as columns the elements in A. Finally, consider the function \( {f}_A({\mathsf {y}}) := f({\bar{{\mathsf {A}}}}{\mathsf {y}})\) on \( \varDelta _{|A| - 1}\), and let \(L_{A}\) be the Lipschitz constant of \({\nabla } {f_A}\) as well asUsing linearity of AFW convergence for strongly convex objectives (see Sect. 6.1), we have the following result:

Additional bounds under a quadratic growth condition weaker than strong convexity and strict complementarity are reported in Garber (2020).

Convergence and finite time identification for the PFW and the AFW are proved in Bomze et al. (2019) for a specific class of non-convex minimization problems over the standard simplex, under the additional assumption that the sequence generated has a finite set of limit points. In another line of work, active set identification strategies combined with FW variants have been proposed in Cristofari et al. (2020) and Sun (2020).

In many real-world applications, linear subproblems can only be solved approximately. This is the reason why the convergence of FW variants is often analyzed under some error term for the linear minimization oracle (see, e.g., Braun et al. 2019, 2017; Freund and Grigas 2016; Jaggi 2013; Konnov 2018). A common assumption, relaxing the FW vertex exact minimization property, is to have access to a point (usually a vertex) \({\tilde{{\mathsf {s}}}}_k\) such thatfor a sequence \(\{\delta _k\}\) of non negative approximation errors.

If the sequence \(\{\delta _k\}\) is constant and equal to some \(\delta > 0\), then trivially the lowest possible approximation error achieved by the FW method is \(\delta \). At the same time, (Freund and Grigas 2016, Theorem 5.1) implies a rate of \({{\mathcal {O}}}(\frac{1}{k} + \delta )\) if the stepsize \(\alpha _k= \frac{2}{k + 2}\) is used.

The \({{\mathcal {O}}}(1/k)\) rate can be instead retrieved by assuming that \(\{\delta _k\}\) converges to 0 quickly enough, and in particular iffor a constant \(\delta > 0 \). Under (62), in Jaggi (2013) a convergence rate ofwas proved for the FW method with \(\alpha _k\) given by exact line search or equal to \(\frac{2}{k + 2}\), as well as for the EFW.

A variant making use of an approximated linear oracle recycling previous solutions to the linear minimization subproblem is studied in Braun et al. (2019). In Freund and Grigas (2016), Hogan (1971), the analysis of the classic FW method is extended to the case of inexact gradient information. In particular in Freund and Grigas (2016), assuming the availability of the \((\delta , L)\) oracle introduced in Devolder et al. (2014), a convergence rate of \({{\mathcal {O}}}(1/k + \delta k)\) is proved.

In the rest of this section we assume that f is \(\mu \)-strongly convex (57). We also assume that the stepsize is given by exact linesearch or by (28).

Under the strong convexity assumption, an asymptotic linear convergence rate for the FDFW on polytopes was given in the early work (Guélat and Marcotte 1986). Furthermore, in Garber and Hazan (2016) a linearly convergent variant was proposed, making use however of an additional local linear minimization oracle. See also Table 2 for a list of improvements on the \({\mathcal {O}}(1/k)\) rate under strong convexity.

Recent works obtain linear convergence rates by proving the angle conditionfor some \(\tau >0\) and some \({\mathsf {x}}^* \in {\mathop {{{\,\mathrm{arg\,min}\,}}}\nolimits _{{\mathsf {x}}\in C}} f({\mathsf {x}})\). As we shall see in the next lemma, under (64) it is not difficult to prove linear convergence rates in the number of good steps. These are FW steps with \(\alpha _k = 1\) and steps in any descent direction with \(\alpha _k < 1\).

As a corollary, under (64) we have the ratefor any method with non increasing \(\{f({\mathsf {x}}_k)\}\) and following Algorithm 1, with \(\gamma (k) \le k\) an integer denoting the number of good steps until step k. It turns out that for all the variants we introduced in this review we have \(\gamma (k) \ge Tk\) for some constant \(T > 0\). When \({\mathsf {x}}^*\) is in the relative interior of \(C\), the FW method satisfies (64) and we have the following result (see Guélat and Marcotte 1986; Lacoste-Julien and Jaggi 2015):

In Lacoste-Julien and Jaggi (2015), the authors proved that directions generated by the AFW and the PFW on polytopes satisfy condition (64), with \(\tau = {{\,\mathrm{PWidth}\,}}(A)/D\) and \({{\,\mathrm{PWidth}\,}}(A)\), pyramidal width of A. While \({{\,\mathrm{PWidth}\,}}(A)\) was originally defined with a rather complex minmax expression, in Peña and Rodriguez (2018) it was then provedThis quantity can be explicitly computed in a few special cases. For \(A = \{0, 1\}^n\) we have \({{\,\mathrm{PWidth}\,}}(A) = 1/\sqrt{n}\), while for \(A = \{e_i\}_{i \in [1:n]}\) (so that \(C\) is the \(n - 1\) dimensional simplex)Angle conditions like (64) with \(\tau \) dependent on the number of vertices used to represent \(x_k\) as a convex combination were given in Bashiri and Zhang (2017) and Beck and Shtern (2017) for the FDFW and the PFW respectively. In particular, in Beck and Shtern (2017) a geometric constant \(\varOmega _{C}\) called vertex-facet distance was defined aswith \(V(C)\) the set of vertices of \(C\), and \({{\mathcal {H}}}(C)\) the set of supporting hyperplanes of \(C\) (containing a facet of \(C\)). Then condition (64) is satisfied for \(\tau = \varOmega _{C}/s\), with \({\mathsf {d}}_k\) the PFW direction and s the number of points used in the active set \(A_k\).

In Bashiri and Zhang (2017), a geometric constant \(H_s\) was defined depending on the minimum number s of vertices needed to represent the current point \(x_k\), as well as on the proper² inequalities \({\mathsf {q}}_i ^{\intercal }{\mathsf {x}}\le b_i\), \(i \in [{1}\! : \! {m}]\), appearing in a description of \(C\). For each of these inequalities the second gap \(g_i\) was defined aswith the secondmax function giving the second largest value achieved by the argument. Then \(H_s\) is defined asThe arguments used in the paper imply that (64) holds with \(\tau = \frac{1}{{2}D\sqrt{H_s}}\) if \({\mathsf {d}}_k\) is a FDFW direction and \({\mathsf {x}}_k\) the convex combination of at most s vertices. We refer the reader to Peña and Rodriguez (2018) and Rademacher and Shu (2020) for additional results on these and related constants.

The linear convergence results for strongly convex objectives are extended to compositions of strongly convex objectives with affine transformations in Beck and Shtern (2017), Lacoste-Julien and Jaggi (2015), Peña and Rodriguez (2018). In Gutman and Pena (2021), the linear convergence results for the AFW and the FW method with minimum in the interior are extended with respect to a generalized condition number \(L_{f, C, D}/\mu _{f, C, D}\), with D a distance function on \(C\).

For the AFW, the PFW and the FDFW, linear rates with no bad steps (\(\gamma (k) = k\)) are given in Rinaldi and Zeffiro (2020) for non-convex objectives satisfying a Kurdyka-Łojasiewicz inequality. In Rinaldi and Zeffiro (2020), condition (64) was proved for the FW direction and orthographic retractions on some convex sets with smooth boundary. The work Combettes and Pokutta (2020) introduces a new FW variant using a subroutine to align the descent direction with the projection on the tangent cone of the negative gradient, thus implicitly maximizing \(\tau \) in (64).

When \(C\) is strongly convex we have a \({{\mathcal {O}}}(1/k^2)\) rate (see, e.g., Garber and Hazan 2015; Kerdreux et al. 2021) for the classic FW method. Furthermore, when \(C\) is \(\beta _{C}\)-strongly convex and \(\Vert \nabla f({\mathsf {x}}) \Vert \ge c > 0\), then we have the linear convergence rate (see Demyanov and Rubinov 1970; Dunn 1979; Kerdreux et al. 2020; Levitin and Polyak 1966)Finally, it is possible to interpolate between the \({{\mathcal {O}}}(1/k^2)\) rate of the strongly convex setting and the \({{\mathcal {O}}}(1/k)\) rate of the general convex one by relaxing strong convexity of the objective with Hölderian error bounds (Xu and Yang 2018) and also by relaxing strong convexity of the domain with uniform convexity (Kerdreux et al. 2021).

The block coordinate FW (BCFW) was introduced in Lacoste-Julien et al. (2013) for block product domains of the form \(C= C^{(1)} \times ... \times C^{(m)} \subseteq {\mathbb {R}}^{n_1 + ... + n_m} \), and applied to structured SVM training. The algorithm operates by selecting a random block and performing a FW step in that block. Formally, for \({\mathsf {s}}\in {\mathbb {R}}^{m_i}\) let \({\mathsf {s}}^{(i)} \in {\mathbb {R}}^n\) be the vector with all blocks equal to \({\mathsf {o}}\) except for the i-th block equal to \({\mathsf {s}}\). We can write the direction of the BCFW asfor a random index \(i \in [{1}\! : \! {n}]\).

In Lacoste-Julien et al. (2013), a convergence rate ofis proved, for \(K = h_0 + \kappa _f^{\otimes }\), with \(\kappa _f^{\otimes }\) the product domain curvature constant, defined as \(\kappa _f^{\otimes } = \sum \kappa _f^{\otimes , i}\) where \(\kappa _f^{\otimes , i}\) are the curvature constants of the objective fixing the blocks outside \(C^{(i)}\):An asynchronous and parallel generalization for this method was given in Wang et al. (2016). This version assumes that a cloud oracle is available, modeling a set of worker nodes each sending information to a server at different times. This information consists of an index i and the following LMO on \(C^{(i)}\):The algorithm is called asynchronous because \({\widetilde{k}}\) can be smaller than k, modeling a delay in the information sent by the node. Once the server has collected a minibatch S of \(\tau \) distinct indexes (overwriting repetitions), the descent direction is defined asIf the indices sent by the nodes are i.i.d., then under suitable assumptions on the delay, a convergence rate ofcan be proved, where \(K_{\tau } = m\kappa _{f, \tau }^{\otimes }(1 + \delta ) + h_0\) for \(\delta \) depending on the delay error, with \(\kappa _{f, \tau }^{\otimes }\) the average curvature constant in a minibatch keeping all the components not in the minibatch fixed.

In Osokin et al. (2016), several improvements are proposed for the BCFW, including an adaptive criterion to prioritize blocks based on their FW gap, and block coordinate versions of the AFW and the PFW variants.

In Shah et al. (2015), a multi plane BCFW approach is proposed in the specific case of the structured SVM, based on caching supporting planes in the primal, corresponding to block linear minimizers in the dual. In Berrada et al. (2018), the duality for structured SVM between BCFW and stochastic subgradient descent is exploited to define a learning rate schedule for neural networks based on only one hyper parameter. The block coordinate approach is extended to the generalized FW in Beck et al. (2015), with coordinates however picked in a cyclic order.

Consider the min-norm point (MNP) problemwith \(C\) a closed convex subset of \({\mathbb {R}}^n\) and \({\Vert \cdot \Vert }_{*}\) a norm on \({\mathbb {R}}^n\). In Wolfe (1976), a FW variant is introduced to solve the problem when \(C\) is a polytope and \({\Vert \cdot \Vert }_*\) is the standard Euclidean norm \(\Vert \cdot \Vert \). Similarly to the variants introduced in Sect. 5.3, it generates a sequence of active sets \(\{A_k\}\) with \( {\mathsf {s}}_k\in A_{k + 1}\). At the step k the norm is minimized on the affine hull \({{\,\mathrm{aff}\,}}(A_k)\) of the current active set \(A_k\), that isThe descent direction \({\mathsf {d}}_k\) is then defined asand the stepsize is given by a tailored linesearch that allows to remove some of the atoms in the set \(A_k\) (see, e.g. Lacoste-Julien and Jaggi 2015; Wolfe 1976). Whenever \({\mathsf {x}}_{k + 1}\) is in the relative interior of \({{\,\mathrm{conv}\,}}(A_k)\), the FW vertex is added to the active set (that is, \({\mathsf {s}}_k \in A_{k + 1}\)). Otherwise, at least one of the vertices not appearing in a convex representation of \({\mathsf {x}}_k\) is removed. This scheme converges linearly when applied to generic smooth strongly convex objectives (see, e.g., Lacoste-Julien and Jaggi 2015).

In Harchaoui et al. (2015), a FW variant is proposed for minimum norm problems of the formwith K a convex cone, f convex with L-Lipschitz gradient. In particular, the optimization domain is \(C= \{{\mathsf {x}}\in {\mathbb {R}}^n : f({\mathsf {x}}) \le 0\} \cap K\). The technique proposed in the article applies the standard FW method to the problemswith \(\{\delta _k\}\) an increasing sequence convergent to the optimal value \({\bar{\delta }}\) of the problem (88). Let \(C(\delta ) = \{{\mathsf {x}}\in {\mathbb {R}}^n : {\Vert {\mathsf {x}} \Vert }_* \le \delta \} \cap K \) for \(\delta \ge 0\), and letso that by homogeneity for every k the linear minimization oracle on \(C(\delta _k)\) is given byFor every k, applying the FW method with suitable stopping conditions an approximate minimizer \({\mathsf {x}}_k\) of \(f( {\mathsf {x}})\) over \(C(\delta _k)\) is generated, with an associated lower bound on the objective, an affine function in \({\mathsf {y}}\):Then the functionis decreasing and affine in \(\delta \) and satisfiesTherefore, forthe quantity \(\delta _{k + 1}\) can be defined as \(\min \{\delta \ge 0 : {{{\bar{\ell }}}_{k}(\delta )} \le 0 \}\), hence \(F(\delta _{k + 1}) \ge 0\). A complexity bound of \({{\mathcal {O}}}(\frac{1}{\varepsilon } \ln (\frac{1}{\varepsilon }))\) was given to achieve precision \(\varepsilon \) applying this method, with \({{\mathcal {O}}}(1/\varepsilon )\) iterations per subproblem and length of the sequence \(\{\delta _k\}\) at most \({{\mathcal {O}}}(\ln (1/\varepsilon ))\) (see (Harchaoui et al. 2015, Theorem 2) for details).

The FW method has found many applications for optimization problems over the trace norm ball. In this case, as explained in Example 3.4, linear optimization can be obtained by computing the top left and right singular vectors of the matrix \(-\nabla f({\mathsf {X}}_k)\), an operation referred to as 1-SVD (see Allen-Zhu et al. 2017) .

In the work Freund et al. (2017), the FDFW is applied to the matrix completion problem (13), thus generating a sequence of matrices \(\{{\mathsf {X}}_k\}\) with \({\Vert {\mathsf {X}}_k \Vert }_* \le \delta \) for every k. The method can be implemented efficiently exploiting the fact that for \({\mathsf {X}}\) on the boundary of the nuclear norm ball, there is a simple expression for the face \({\mathcal {F}}({\mathsf {X}})\). For \({\mathsf {X}}\in {\mathbb {R}}^{m \times n}\) with \({{\,\mathrm{rank}\,}}({\mathsf {X}}) = k\) let \({\mathsf {U}}{\mathsf {D}}{\mathsf {V}}^{\intercal }\) be the thin SVD of \({\mathsf {X}}\), so that \({\mathsf {D}}\in {\mathbb {R}}^{k \times k}\) is the diagonal matrix of non zero singolar values for \({\mathsf {X}}\), with corresponding left and right singular vectors in the columns of \({\mathsf {U}}\in {\mathbb {R}}^{m \times k}\) and \({\mathsf {V}}\in {\mathbb {R}}^{n \times k}\) respectively. If \({\Vert {\mathsf {X}} \Vert }_* = \delta \) then the minimal face of the domain containing \({\mathsf {X}}\) is the setIt is not difficult to see that we have \({{\,\mathrm{rank}\,}}({\mathsf {X}}_k) \le k + 1\) for every \(k \in {\mathbb {N}}\), as well. Furthermore, the thin SVD of the current iterate \({\mathsf {X}}_k\) can be updated efficiently both after FW steps and after in face steps. The convergence rate of the FDFW in this setting is still \({{\mathcal {O}}}(1/k)\).

In the recent work Wang et al. (2020), an unbounded variant of the FW method is applied to solve a generalized version of the trace norm ball optimization problem:with \({\mathsf {P}}, {\mathsf {Q}}\) singular matrices. The main idea of the method is to decompose the domain in the sum \(S + T\) between the kernel T of the linear function \(\varphi _{{\mathsf {P}}, {\mathsf {Q}}}({\mathsf {X}})= {\mathsf {P}}{\mathsf {X}}{\mathsf {Q}}\) and a bounded set \(S \subset T^{\perp }\). Then gradient descent steps in the unbounded component T are alternated to FW steps in the bounded component S. The authors apply this approach to the generalized LASSO as well, using the AFW for the bounded component.

In Allen-Zhu et al. (2017), a variant of the classic FW using k-SVD (computing the top k left and right singular vectors for the SVD) is introduced, and it is proved that it converges linearly for strongly convex objectives when the solution has rank at most k. In Mu et al. (2016), the FW step is combined with a proximal gradient step for a quadratic problem on the product of the nuclear norm ball with the \(\ell _1\) ball. Approaches using an equivalent formulation on the spectrahedron introduced in Jaggi and Sulovský (2010) are analyzed in Ding et al. (2020), Garber (2019).