Heavy Ball Momentum for Conditional Gradient
Year: 2022

Abstract:
Conditional gradient, aka Frank Wolfe (FW) algorithms, have well-documented merits in machine learning and signal processing applications. Unlike projectionbased methods, momentum cannot improve the convergence rate of FW, in general. This limitation motivates the present work, which deals with heavy ball momentum, and its impact to FW. Specifically, it is established that heavy ball offers a unifying perspective on the primal-dual (PD) convergence, and enjoys a tighter per iteration PD error rate, for multiple choices of step sizes, where PD error can serve as the stopping criterion in practice. In addition, it is asserted that restart, a scheme typically employed jointly with Nesterov’s momentum, can further tighten this PD error bound. Numerical results demonstrate the usefulness of heavy ball momentum in FW iterations.

heading: 1 Introduction
text: This work studies momentum in Frank Wolfe (FW) methods [9, 10, 16, 20] for solving
min x∈X f(x). (1)
Here, f is a convex function with Lipschitz continuous gradients, and the constraint set X ⊂ Rd is assumed convex and compact, where d is the dimension of variable x. Throughout, we let x∗ ∈ X denote a minimizer of (1). FW and its variants are prevalent in various machine learning and signal processing applications, such as traffic assignment [12], non-negative matrix factorization [30], video colocation [17], image reconstruction [15], particle filtering [19], electronic vehicle charging [36], recommender systems [11], optimal transport [26], and neural network pruning [34]. The popularity of FW is partially due to the elimination of projection compared with projected gradient descent (GD) [29], leading to computational efficiency especially when d is large. In particular, FW solves a subproblem with a linear loss, i.e., vk+1 ∈ arg minv∈X 〈∇f(xk),v〉 at kth iteration, and then updates xk+1 as a convex combination of xk and vk+1. When dealing with a structured X , a closed-form or efficient solution for vk+1 is available [13, 16], which is preferable over projection.
Unlike projection based algorithms [14, 32] though, momentum does not perform well with FW. Indeed, the lower bound in [16,20] demonstrates that at leastO( 1 ) linear subproblems are required to ensure f(xk)− f(x∗) ≤ , which does not guarantee that momentum is beneficial for FW, because even vanilla FW achieves this lower bound. In this work, we contend that momentum is evidently useful for FW. Specifically, we prove that the heavy ball momentum leads to tightened and efficiently computed primal-dual error bound, as well as numerical improvement. To this end, we outline first the primal convergence.
Primal convergence. The primal error refers to f(xk) − f(x∗). It is guaranteed for FW that f(xk)− f(x∗) = O ( 1/k ) ,∀k ≥ 1 [16,22]. This rate is tight in general since it matches to the lower bound [16, 20]. Other FW variants also ensure the same order of primal error; see e.g., [20, 21].
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
Primal-dual convergence. The primal-dual (PD) error quantifies the difference between both the primal and the ‘dual’ functions from the optimal objective, hence it is an upper bound on the primal error. When the PD error is shown to converge, it can be safely used as the stopping criterion: whenever the PD error is less than some prescribed > 0, f(xk)−f(x∗) ≤ is ensured automatically. The PD error of FW is convenient to compute, hence FW is suitable for the requirement of “solving problems to some desirable accuracy;” see e.g., [33]. For pruning (two-layer) neural networks [34], the extra training loss incurred by removing neurons can be estimated via the PD error. However, due to technical difficulties, existing analyses on PD error are not satisfactory enough and lack of unification. It is established in [6, 10, 16] that the minimum PD error is sufficiently small, namely mink∈{1,...,K} PDErrork = O ( 1 K ) , where K is the total number of iterations. We term such a bound for the minimum PD error as Type I guarantee. Another stronger guarantee, which directly implies Type I bound, emphasizes the per iteration convergence, e.g., PDErrork ≤ O( 1k ),∀k. We term such guarantees as Type II bound. A Type II bound is reported in [18, Theorem 2], but with an unsatisfactory k dependence. This is improved by [7,28] with the price of extra computational burden since it involves solving two FW subproblems per iteration for computing this PD error. Several related works such as [10] provide a weaker PD error compared with [28]; see a summary in Table 1.
In this work, we show that a computationally affordable Type II bound can be obtained by simply relying on heavy ball momentum. Interestingly, FW based on heavy ball momentum (HFW) also maintains FW’s neat geometric interpretation. Through unified analysis, the resultant type II PD error improves over existing bounds; see Table 1. This PD error of HFW is further tightened using restart. Although restart is more popular in projection based methods together with Nesterov’s momentum [31], we show that restart for FW is natural to adopt jointly with heavy ball. In succinct form, our contributions can be summarized as follows.
• We show through unified analysis that HFW enables a tighter type II guarantee for PD error for multiple choices of the step size. When used as stopping criterion, no extra subproblem is needed. • The Type II bound can be further tightened by restart triggered through a comparison between two PD-error-related quantities. • Numerical tests on benchmark datasets support the effectiveness of heavy ball momentum. As a byproduct, a simple yet efficient means of computing local Lipschitz constants becomes available to improve the numerical efficiency of smooth step sizes [13, 22].
Notation. Bold lowercase (capital) letters denote column vectors (matrices); ‖x‖ stands for a norm of a vector x, whose dual norm is denoted by ‖x‖∗; and 〈x,y〉 is the inner product of x and y.

heading: 2 Preliminaries
text: This section outlines FW, starting with standard assumptions that will be taken to hold true throughout. Assumption 1. (Lipschitz continuous gradient.) The objective function f : X → R has L-Lipchitz continuous gradients; i.e., ‖∇f(x)−∇f(y)‖∗ ≤ L‖x− y‖,∀x,y ∈ X . Assumption 2. (Convexity.) The objective function f : X → R is convex; that is, f(y)− f(x) ≥ 〈∇f(x),y − x〉,∀x,y ∈ X . Assumption 3. (Convex and compact constraint set.) The constraint set X ⊂ Rd is convex and compact with diameter D, that is, ‖x− y‖ ≤ D,∀x,y ∈ X .
Algorithm 1 FW [9] 1: Initialize: x0 ∈ X 2: for k = 0, 1, . . . ,K − 1 do 3: vk+1 = arg minv∈X 〈∇f(xk),v〉 4: xk+1 = (1− ηk)xk + ηkvk+1 5: end for 6: Return: xK FW for solving (1) under Assumptions 1 – 3 is listed in Alg. 1. The subproblem in Line 3 can be visualized geometrically as minimizing a supporting hyperplane of f(x) at xk, i.e., vk+1 ∈ arg min v∈X f(xk) + 〈∇f(xk),v − xk〉. (2) For many constraint sets, efficient implementation or a closed-form solution is available for vk+1; see e.g., [16] for a comprehensive summary. Upon minimizing the supporting hyperplane in (2), xk+1 is updated as a convex combination of vk+1 and xk in Line 4 so that no projection is required. The choices on the step size ηk ∈ [0, 1] will be discussed shortly.
The PD error of Alg. 1 is captured by the so-termed FW gap, formally defined as
Ḡk := 〈∇f(xk),xk − vk+1〉 = f(xk)−f(x∗)︸ ︷︷ ︸ primal error + f(x∗)−min v∈X
[ f(xk) + 〈∇f(xk),v−xk〉 ] ︸ ︷︷ ︸
dual error
(3)
where the second equation is because of (2). It can be verified that both primal and dual errors marked in (3) are no less than 0 by appealing to the convexity of f . If Ḡk converges, one can deduce that the primal error converges. For this reason, Ḡk is typically used as a stopping criterion for Alg. 1. Next, we focus on the step sizes that ensure convergence.
Parameter-free step size. This type of step sizes does not rely on any problem dependent parameters such as L and D, and hence it is extremely simple to implement. The most commonly adopted step size is ηk = 2k+2 , which ensures a converging primal error f(xk) − f(x ∗) ≤ 2LD 2
k+1 ,∀k ≥ 1, and a weaker claim on the PD error, mink∈{1,...,K} Ḡk = 27LD 2
4K [16]. A variant of PD convergence has been established recently based on a modified FW gap [28]. Although Type II convergence is observed, the modified FW gap therein is inefficient to serve as stopping criterion because an additional FW subproblem has to be solved per iteration to compute its value.
Smooth step size. When the (estimate of) Lipschitz constant L is available, one can adopt the following step sizes in Alg. 1 [22]
ηk = min { 〈∇f(xk),xk − vk+1〉 L‖vk+1 − xk‖2 , 1 } . (4)
Despite the estimated L is typically too pessimistic to capture the local Lipschitz continuity, such a step size ensures f(xk+1) ≤ f(xk); see derivations in Appendix A.1. The PD convergence is studied in [11], where the result is slightly weaker than that of [28].

heading: 3 FW with heavy ball momentum
text: After a brief recap of vanilla FW, we focus on the benefits of heavy ball momentum for FW under multiple step size choices, with special emphasis on PD errors.

heading: 3.1 Prelude
text: HFW is summarized in Alg. 2. Similar to GD with heavy ball momentum [14, 32], Alg. 2 updates decision variables using a weighted average of gradients gk+1. In addition, the update direction of Alg. 2 is no longer guaranteed to be a descent one. This is because in HFW, 〈∇f(xk),xk − vk+1〉 can be negative. Although a stochastic version of heavy ball momentum was adopted in [27] and its variants, e.g., [37], to reduce the mean square error of the gradient estimate, heavy ball is introduced here for a totally different purpose, that is, to improve the PD error. The most significant difference comes at technical perspectives, which is discussed in Sec. 3.4. Next, we gain some intuition on why heavy ball can be beneficial.
Consider X as an `2-norm ball, that is, X = {x|‖x‖2 ≤ R}. In this case, we have vk+1 = − R‖gk+1‖2 gk+1 in Alg. 2. The momentum gk+1 can smooth out the changes of {∇f(xk)}, resulting
Algorithm 2 FW with heavy ball momentum 1: Initialize: x0 ∈ X ,g0 = ∇f(x0) 2: for k = 0, 1, . . . ,K − 1 do 3: gk+1 = (1− δk)gk + δk∇f(xk) 4: vk+1 = arg minv∈X 〈gk+1,v〉 5: xk+1 = (1− ηk)xk + ηkvk+1 6: end for 7: Return: xK in a more concentrated sequence {vk+1}. Recall that the PD error is closely related to vk+1 [cf. equation (3)]. We hope the “concentration” of {vk+1} to be helpful in reducing the changes of PD error among consecutive iterations so that a Type II PD error bound is attainable.
A few concepts are necessary to obtain a tightened PD error of HFW. First, we introduce the generalized FW gap associated with Alg. 2 that captures the PD error. Write gk+1 explicitly as gk+1 = ∑k τ=0 w τ k∇f(xτ ), where wτk =
δτ ∏k j=τ+1(1− δj) > 0, ∀τ ≥ 1, and w0k = ∏k j=1(1− δj) > 0. Then, define a sequence of linear functions {Φk(x)} as
Φk+1(x) := k∑ τ=0 wτk [ f(xτ ) + 〈∇f(xτ ),x− xτ 〉 ] , ∀k ≥ 0. (5)
It is clear that Φk+1(x) is a weighted average of the supporting hyperplanes of f(x) at {xτ}kτ=0. The properties of Φk+1(x), and how they relate to Alg. 2 are summarized in the next lemma. Lemma 1. For the linear function Φk+1(x) in (5), it holds that: i) vk+1 minimizes Φk+1(x) over X ; and, ii) f(x) ≥ Φk+1(x),∀k ≥ 0,∀x ∈ X .
From the last lemma, one can see that vk is obtained by minimizing Φk(x), which is an affine lower bound on f(x). Hence, HFW admits a geometric interpretation similar to that of FW. In addition, based on Φk(x) we can define the generalized FW gap. Definition 1. (Generalized FW gap.) The generalized FW gap w.r.t. Φk(x) is
Gk := f(xk)−min x∈X Φk(x) = f(xk)− Φk(vk). (6)
In words, the generalized FW gap is defined as the difference between f(xk) and the minimal value of Φk(x) over X . The newly defined Gk also illustrates the PD error
Gk = f(xk)− Φk(vk) = f(xk)− f(x∗)︸ ︷︷ ︸ primal error + f(x∗)− Φk(vk)︸ ︷︷ ︸ dual error . (7)
For the dual error, we have f(x∗) − Φk(vk) ≥ Φk(x∗) − Φk(vk) ≥ 0, where both inequalities follow from Lemma 1. Hence, Gk ≥ 0 automatically serves as an overestimate of both primal and dual errors. When establishing the convergence of Gk, it can be adopted as the stopping criterion for Alg. 2. Related claims have been made for the generalized FW gap [20, 23, 28]. Lack of heavy ball momentum leads to inefficiency, because an additional FW subproblem is needed to compute this gap [28]. Works [20, 23] focus on Nesterov’s momentum for FW, that incurs additional memory relative to HFW; see also Sec. 3.4 for additional elaboration. Having defined the generalized FW gap, we next pursue parameter choices that establish Type II convergence guarantees.

heading: 3.2 Parameter-free step size
text: We first consider a parameter-free choice for HFW to demonstrate the usefulness of heavy ball
δk = ηk = 2
k + 2 , ∀k ≥ 0. (8)
Such a choice on δk puts more weight on recent gradients when calculating gk+1, since wτk = O( τk2 ). The following theorem specifies the convergence of Gk. Theorem 1. If Assumptions 1-3 hold, then choosing δk and ηk as in (8), Alg. 2 guarantees that
Gk = f(xk)− Φk(vk) ≤ 2LD2
k + 1 , ∀k ≥ 1.
Theorem 1 provides a much stronger PD guarantee for all k than vanilla FW [16, Theorem 2]. In addition to a readily computable generalized FW gap, our rate is tighter than [28], where the provided bound is 4LD 2
k+1 . In fact, the constants in our PD bound even match to the best known primal error of vanilla FW. A direct consequence of Theorem 1 is the convergence of both primal and dual errors.
Corollary 1. Choosing the parameters as in Theorem 1, then ∀k ≥ 1, Alg.2 guarantees that
primal conv.: f(xk)− f(x∗) ≤ 2LD2
k + 1 ; dual conv.: f(x∗)− Φk(vk) ≤
2LD2 k + 1 .
Proof. Combine Theorem 1 with f(xk)− f(x∗) ≤ Gk and f(x∗)− Φk(vk) ≤ Gk [cf. (7)].

heading: 3.3 Smooth step size
text: Next, we focus on HFW with a variant of the smooth step size
δk = 2
k + 2 and ηk = max
{ 0,min { 〈∇f(xk),xk − vk+1〉 L‖vk+1 − xk‖2 , 1 }} . (9)
Comparing with the smooth step size for vanilla FW in (4), it can be deduced that the choice on ηk in (9) has to be trimmed to [0, 1] manually. This is because 〈∇f(xk),xk − vk+1〉 is no longer guaranteed to be positive. The smooth step size enables an adaptive means of adjusting the weight for ∇f(xk). To see this, note that when ηk = 0, we have xk+1 = xk. As a result, gk+2 = (1− δk+1)gk+1 + δk+1∇f(xk+1) = (1− δk+1)gk+1 + δk+1∇f(xk), that is, the weight on ∇f(xk) is adaptively increased to δk(1 − δk+1) + δk+1 if one further unpacks gk+1. Another analytical benefit of the step size in (9) is that it guarantees a non-increasing objective value; see Appendix A.2 for derivations. Convergence of the generalized FW gap is established next. Theorem 2. If Assumptions 1-3 hold, while ηk and δk are chosen as in (9), Alg. 2 guarantees that
Gk = f(xk)− Φk(vk) ≤ 2LD2
k + 1 , ∀k ≥ 1.
The proof of Theorem 2 follows from that of Theorem 1 after modifying just one inequality. This considerably simplifies the analysis on the (modified) FW gap compared to vanilla FW with smooth step size [11]. The PD convergence clearly implies the convergence of both primal and dual errors. A similar result to Corollary 1 can be obtained, but we omit it for brevity. We further extend Theorem 2 in Appendix B.4 by showing that if a slightly more difficult subproblem can be solved, it is possible to ensure per step descent on the PD error; i.e., Gk+1 ≤ Gk. Line search. When choosing δk = 2k+2 and ηk via line search, HFW can guarantee a Type II PD error of 2LD 2
k+1 ; please refer to Appendix B.5 due to space limitation. For completeness, an iterative manner to update Gk for using as stopping criterion is also described in Appendix C.

heading: 3.4 Further considerations
text: There are more choices of δk and ηk leading to (primal) convergence. For example, one can choose δk ≡ δ ∈ (0, 1) and ηk = O ( 1 k ) as an extension of [27].1 A proof is provided in Appendix B.7 for completeness. This analysis framework in [27], however, has two shortcomings: i) the convergence can be only established using `2-norm (recall that in Assumption 1, we do not pose any requirement on the norm); and, ii) the final primal error (hence PD error) can only be worse than vanilla FW because their analysis treats gk+1 as∇f(xk) with errors but not momentum, therefore, it is difficult to obtain the same tight PD bound as in Theorem 1. Our analytical techniques avoid these limitations.
When choosing δk = ηk = 1k+1 , we can recover Algorithm 3 in [1]. Notice that such a choice on δk makes gk+1 a uniform average of all gradients. A slower convergence rate f(xk) − f(x∗) = O ( LD2 ln k
k
) was established in [1] through a sophisticated derivation using no-regret online learning.
Through our simpler analytical framework, we can attain the same rate while providing more options for the step size. Theorem 3. Let Assumptions 1-3 hold, and select δk = 1k+1 with ηk using one of the following options: i) ηk = 1k+1 ; ii) as in (9); or iii) line search as in (26b). The generalized FW gap of Alg. 2 then converges with rate
Gk = f(xk)− Φk(vk) ≤ LD2 ln(k + 1)
2k , ∀k ≥ 1.
1We are unable to derive even a primal error bound using the same analysis framework in [27] for step sizes listed in Theorem 1.
The rate in Theorem 3 has worse dependence on k relative to Theorems 1 and 2, partially because too much weight is put on past gradients in gk+1, suggesting that large momentum may not be helpful.
Heavy ball versus Nesterov’s momentum. A simple rule to compare these two momentums is whether gradient is calculated at the converging sequence {xk}. Heavy ball momentum follows this rule, while Nesterov’s momentum computes the gradient at some extrapolation points that are not used in Alg. 2. It is unclear how the original Nesterov’s momentum benefits the PD error, but the ∞-memory variant of Nesterov’s momentum [20, 23, 24], which can be viewed as a combination of heavy ball and Nesterov’s momentum, yields a Type II PD error. However, compared with HFW, additional memory should be allocated. In sum, these observations suggest that heavy ball momentum is essentially critical to improve the PD performance of FW. Nesterov’s momentum, on the other hand, does not influence PD error when used alone; however, it gives rise to faster (local) primal rates under additional assumptions [20, 23].

heading: 3.5 A side result: Directional smooth step sizes
text: Common to both FW and HFW is that the globally estimated L might be too pessimistic for a local update. In this subsection, a local Lipschitz constant is investigated to further improve the numerical efficiency of smooth step sizes in (9). This easily computed local Lipschitz constant is another merit of (H)FW over projection based approaches.
Definition 2. (Directional Lipschitz continuous.) For two points x,y ∈ X , the directional Lipschitz constant L(x,y) ensures ‖∇f(x̂)−∇f(ŷ)‖∗ ≤ L(x,y)‖x̂− ŷ‖ for any x̂ = (1− α)x + αy, ŷ = (1− β)x + βy with some α ∈ [0, 1] and β ∈ [0, 1].
In other words, the directional Lipschitz continuity depicts the local property on the segment between points x and y. It is clear that L(x,y) ≤ L. Using logistic loss for binary classification as an example, we have L(x,y) ≤ 14N ∑N i=1 〈ai,x−y〉2 ‖x−y‖22 , where N is the number of data, and ai is the
feature of the ith datum. As a comparison, the global Lipschitz constant is L ≤ 14N ∑N i=1 ‖ai‖22. We show in Appendix E that at least for a class of functions, including widely used logistic loss and quadratic loss, L(x,y) has an analytical form.
Simply replacing L in (9) with L(xk,vk+1), i.e.,
ηk = max
{ 0,min { 〈∇f(xk),xk − vk+1〉 L(xk,vk+1)‖vk+1 − xk‖2 , 1 }}
(10)
we can obtain what we term directionally smooth step size. Upon exploring the collinearity of xk, xk+1 and vk+1, a simple modification of Theorem 2 ensures the PD convergence.
Corollary 2. Choosing δk = 2k+2 , and ηk via (10), Alg. 2 ensures
Gk = f(xk)− Φk(vk) ≤ 2LD2
k + 1 , ∀k ≥ 1.
The directional Lipschitz constant can also replace the global one in other FW variants, such as [13,22], with theories therein still holding. As we shall see in numerical tests, directional smooth step sizes outperform the vanilla one by an order of magnitude.

heading: 4 Restart further tightens the PD error
text: Up till now it is established that the heavy ball momentum enables a unified analysis for tighter Type II PD bounds. In this section, we show that if the computational resources are sufficient for solving two FW subproblems per iteration, the PD error can be further improved by restart when the standard FW gap is smaller than generalized FW gap. Restart is typically employed by Nesterov’s momentum in projection based methods [31] to cope with the robustness to parameter estimates, and to capture the local geometry of problem (1). However, it is natural to integrate restart with heavy ball momentum in FW regime. In addition, restart provides an answer to the following question: which is smaller, the generalized FW gap or the vanilla one? Previous works using the generalized FW gap have not addressed this question [20, 23, 28].
Algorithm 3 FW with heavy ball momentum and restart 1: Initialize: x00 ∈ X ,g00 = ∇f(x00), s← 0, C0 = 0, G00 = Ḡ00 2: while [not terminated] do 3: k ← 0, gs0 = ∇f(xs0) 4: while [Gsk ≤ Ḡsk or k = 0] and [not terminated] do . Check whether restart is needed 5: δsk = 2 k+2+Cs
6: gsk+1 = (1− δsk)gsk + δsk∇f(xsk) 7: vsk+1 = arg minx∈X 〈gsk+1,x〉 8: xsk+1 = (1− ηsk)xsk + ηskvsk+1 9: v̄sk+1 = arg minx∈X 〈∇f(xsk+1),x〉
10: Gsk+1 = f(xsk+1)− Φsk+1(vsk+1) . Generalized FW gap 11: Ḡsk+1 = 〈∇f(xsk),xsk − v̄sk+1〉 . Vanilla FW gap 12: k ← k + 1 13: end while 14: Ks ← k, xs+10 = xsKs , C s+1 = 2LD 2
GsKs , s← s+ 1
15: end while
FW with heavy ball momentum and restart is summarized under Alg. 3. For exposition clarity, when updating the counters such as k and s, we use notation ‘←’. Alg. 3 contains two loops. The inner loop is the same as Alg. 2 except for computing a standard FW gap (Line 11) in addition to the generalized one (Line 10). The variable Ks, depicting the iteration number of inner loop s, is of analysis purpose. Alg. 3 can be terminated immediately whenever min{Gsk, Ḡsk} ≤ for a desirable > 0. The restart happens when the standard FW gap is smaller than generalized FW gap. And after restart, gsk+1 will be reset. For Alg. 3, the linear functions used for generalized FW gap are defined stage-wisely
Φs0(x) = f(x s 0) + 〈 ∇f(xs0),x− xs0 〉 (11a)
Φsk+1(x) = (1− δsk)Φsk(x) + δsk [ f(xsk) + 〈 ∇f(xsk),x− xsk 〉] ,∀ k ≥ 0. (11b)
It can be verified that vsk+1 minimizes Φ s k+1(x) over X for any k ≥ 0. In addition, we also have f(xs0)− Φs0(vs0) = Ḡs−1Ks−1 where v s 0 = arg minx∈X Φ s 0(x).
There are two tunable parameters ηsk and δ s k. The choice on δ s k has been provided directly in Line 5, where it is adaptively decided using a variable Cs relating to the generalized FW gap. Three choices are readily available for ηsk: i) η s k = δ s k; ii) smooth step size:
ηsk = max
{ 0,min { 〈∇f(xsk),xsk − vsk+1〉 L‖vsk+1 − xsk‖2 , 1 }} ; (12)
and, iii) line search
ηsk = arg min η∈[0,1]
f ( (1− η)xsk + ηvsk+1 ) . (13)
Note that the directionally smooth step size, i.e., replacing L with L(xsk,v s k+1) in (12) is also valid for convergence. We omit it to reduce repetition. Next we show how restart improves the PD error. Theorem 4. Choose ηsk via one of the three manners: i) ηsk = δsk; ii) as in (12); or iii) as in (13). If there is no restart (e.g., s = 0 when terminating), then Alg. 3 guarantees that
G0k = f(x0k)− Φk(v0k) ≤ 2LD2
k + 1 ,∀k ≥ 1. (14a)
If restart happens, in additional to (14a), we have
Gsk = f(xsk)− Φk(vsk) < 2LD2
k + Cs ,∀k ≥ 1,∀s ≥ 1, with Cs ≥ 1 + s−1∑ j=0 Kj . (14b)
Besides the convergence of both primal and dual errors of Alg. 3, Theorem 4 implies that when no restart happens, the generalized FW gap is smaller than the standard one, demonstrating that the
former is more suitable for the purpose of “stopping criterion”. When restarted, Theorem 4 provides a strictly improved bound compared with Theorems 1, 2, and 6, since the denominator of the RHS in (14b) is no smaller than the total iteration number. An additional comparison with [28], where two subproblems are also required, once again confirms the power of heavy ball momentum to improve the constants in the PD error rate, especially with the aid of restart. The restart scheme (with slight modification) can also be employed in [23, 24, 28] to tighten their PD error.

heading: 5 Numerical tests
text: This section presents numerical tests to showcase the effectiveness of HFW on different machine learning problems. Since there are two parameters’ choices for HFW in Theorems 1 and 3, we term them as weighted FW (WFW) and uniform FW (UFW), respectively, depending on the weight of {∇f(xk)} in gk+1. When using smooth step size, the corresponding algorithms are marked as WFW-s and UFW-s. For comparison, the benchmark algorithms include: FW with ηk = 2k+2 (FW); and, FW with smooth step size (FW-s) in (4).

heading: 5.1 Binary classification
text: We first test the performance of Alg. 2 on binary classification using logistic regression
f(x) = 1
N N∑ i=1 ln ( 1 + exp(−bi〈ai,x〉) ) . (15)
Here (ai, bi) is the (feature, label) pair of datum i, and N is the number of data. Datasets from LIBSVM2 are used in the numerical tests, where details of the datasets are deferred to Appendix F due to space limitation.
`2-norm ball constraint. We start with X = {x|‖x‖2 ≤ R}. The primal errors are plotted in the first row of Fig. 1. We use primal error here for a fair comparison. It can be seen that the parameter-free step sizes achieve better performance compared with the smooth step sizes mainly because the quality of L estimate. Such a problem can be relived through directional smooth step sizes as we shall shortly. Among parameter-free step sizes, it can be seen that WFW consistently
2https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/binary.html.
outperforms both UFW and FW on all tested datasets, while UFW converges faster than FW only on datasets realsim and mushroom. For smooth step sizes, the per-step-descent property is validated. The excellent performance of HFW can be partially explained by the similarity of its update, namely xk+1 = (1− ηk)xk + ηkR gk+1‖gk+1‖2 , with normalized gradient descent (NGD) one, that is given by xk+1 = ProjX ( xk − ηk gk+1‖gk+1‖2 ) . However, there is also a subtle difference between HFW and NGD updates. Indeed, when projection is in effect, xk+1 in NGD will lie on the boundary of the `2-norm ball. Due to the convex combination nature of the update in HFW, it is unlikely to have xk+1 on the boundary, though it can come arbitrarily close.
`1-norm ball constraint. Here X = {x|‖x‖1 ≤ R} denotes the constraint set that promotes sparse solutions. In the simulation, R is tuned for a solution with similar sparsity as the dataset itself. The results are showcased in the second row of Fig. 1. For smooth step sizes, FW-s, UFW-s, and WFW-s exhibit similar performances, and their curves are smooth. On the other hand, parameter-free step sizes eventually outperform smooth step sizes though the curves zig-zag. (The curves on realsim are smoothed to improve figure quality.) UFW has similar performance on w7a and mushroom with FW and faster convergence on other datasets. Once again, WFW consistently outperforms FW and UFW.
n-support norm ball constraint. The n-support norm ball is a tighter relaxation of a sparsity enforcing `0-norm ball combined with an `2-norm penalty compared with ElasticNet [38]. It gives rise to X = conv{x|‖x‖0 ≤ n, ‖x‖2 ≤ R}, where conv{·} denotes the convex hull [3]. The closed-form solution of vk+1 is given in [25]. In the simulation, we choose n = 2 and tune R for a solution whose sparsity is similar to the adopted dataset. The results are showcased in the third row of Fig. 1. For smooth step sizes, FW-s and WFW-s exhibit similar performance, while UFW-s converges slightly slower on ijcnn1. Regarding parameter-free step sizes, UFW does not offer faster convergence compared with FW on the tested datasets, but WFW again has numerical merits.
Directionally smooth step sizes. The results in Fig. 2 validate the effectiveness of directionally smooth (-ds) step sizes. For all datasets tested, the benefit of adopting L(xk,vk+1) is evident, as it improves the performance of smooth step sizes by an order of magnitude. In addition, it is also observed that UFW-ds performs worse than WFW-ds, which suggests that putting too much weight on past gradients could be less attractive in practice.
Additional comparisons. We also compare HFW with a generalized version of [27], where we set δk = δ ∈ (0, 1),∀k in Alg. 2. Two specific choices, i.e., δ = 0.6, and δ = 0.8, are plotted in Fig. 3, where the `2-norm ball and n-support norm ball are adopted as constraints. In both cases, WFW converges faster than the algorithm adapted from [27]. In addition, the choice of δ has major impact on convergence behavior, while WFW avoids this need for manual tuning of δ. The performance of WFW with restart, i.e., Alg. 3, is also shown in Fig. 3. Although it slightly outperforms WFW,
restart also doubles the computational burden due to the need of solving two FW subproblems. From this point of view, WFW with restart is more of theoretical rather than practical interest. In addition, it is observed that Alg. 3 is not restarted after the first few iterations, which suggests that the generalized FW gap is smaller than the vanilla one, at least in the early stage of convergence. Thus, the generalized FW gap is attractive as a stopping criterion when a solution with moderate accuracy is desirable.
In a nutshell, the numerical experiments suggest that heavy ball momentum performs best with parameter-free step sizes with the momentum weight carefully adjusted. WFW is mainly recommended because it achieves improved empirical performance compared to UFW and FW, regardless of the constraint sets. The smooth step sizes on the other hand, eliminate the zig-zag behavior at the price of convergence slowdown due to the need of L, while directionally smooth step sizes can be helpful to alleviate this convergence slowdown.

heading: 5.2 Matrix completion
text: This subsection focuses on matrix completion problems for recommender systems. Consider a matrix A ∈ Rm×n with partially observed entries, i.e., entries Aij for (i, j) ∈ K are known, where K ⊂ {1, . . . ,m} × {1, . . . , n}. Based on the observed entries that can be contaminated by noise, the goal is to predict the missing entries. Within the scope of recommender systems, a commonly adopted empirical observation is that A is low rank [4, 5, 8], leading to the following problem formulation.
min X
1
2 ∑ (i,j)∈K (Xij −Aij)2 s.t. ‖X‖nuc ≤ R. (16)
Problem (16) is difficult to solve using GD because projection onto a nuclear norm ball requires a full SVD, which has complexity O ( mn(m ∧ n) ) with (m ∧ n) := min{m,n}. In contrast, FW and its variants are more suitable for (16) since the FW subproblem has complexity less than O(mn) [2]. Heavy ball based FW are tested using dataset MovieLens100K3. Following the initialization of [11], the numerical results can be found in Fig. 4. Subfigures (a) and (b) depict the optimality error and rank versus k for R = 3. For parameter-free step sizes, WFW converges faster than FW while finding solutions with lower rank. The low rank solution of UFW is partially because it does not converge sufficiently. For smooth step sizes, UFW-s finds a solution with slightly larger objective value but much lower rank compared with WFW-s and FW-s. Overall, when a small optimality error is the priority, WFW is more attractive; while UFW-s is useful for finding low rank solutions.

heading: 6 Conclusions and future directions
text: This work demonstrated the merits of heavy ball momentum for FW. Multiple choices of the step size ensured a tighter Type II primal-dual error bound that can be efficiently computed when adopted as stopping criterion. An even tighter PD error bound can be achieved by relying jointly on heavy ball momentum and restart. A novel and general approach was developed to compute local Lipschitz constants in FW type algorithms. Numerical tests in the paradigms of logistic regression and matrix completion demonstrated the effectiveness of heavy ball momentum in FW.
Our future research agenda includes performance evaluation of heavy ball momentum for various learning tasks. For example, HFW holds great potential when fairness is to be accounted for [35].
3https://grouplens.org/datasets/movielens/100k/

heading: Acknowledgement
text: This work is supported by NSF grants 1901134, 2126052, and 2128593. The authors would also like to thank the anonymous reviewers for their feedback.

Review summaries:
This work presents the heavy ball frank wolfe (HFW) method and shows that it establishes a $\mathcal{O}(1/K)$ last-iterate rate on a primal-dual gap (and hence also on the primal function-value suboptimality). In contrast, prior work established a $\mathcal{O}(1/K)$ last-iterates rate on the primal suboptimality or a $\mathcal{O}(1/K)$ best-iterate rate on the primal-dual gap. The work also presents variations of the HFW method and brief experiments.

The authors provide an analysis of Frank Wolfe (FW) algorithms with heavy ball momentum. After a recap of standard FW including common assumptions, choices of step size and convergence guarantees, they introduce FW with heavy ball momentum. Different variants for step size and weighting parameter are considered and it is shown that using heavy ball momentum stabilizes convergence in terms of an improved rate. Subsequently, the authors consider FW with heavy ball momentum prove that this leads to further improvement of the convergence rate. Finally, numerical results for binary classification on multiple datasets and matrix completion are reported.

This paper considers the effect of the heavy ball momentum on the Frank-Wolfe method. The $O(1/k)$ last-term convergence (type II as described in the paper) of a generalized FW gap is provided as the main contribution of this paper. Such a result is missing in the previous literature without the extra computational burden (only $O(1/\sqrt{k})$ result is available). The extension of the FW gap to the proposed generalized FW gap is natural, and this proposed quantity can also serve as the stopping criterion in practice. Other than the classic step-size choice of $2/(k+2)$, a similar result is obtained under smooth step size with the additional beneﬁt of a non-increasing objective value, but at the cost of some prior knowledge of the smoothness parameter $L$. The problem of the pessimistic estimation of $L$ is then alleviated with the introduction of the directionally smooth step size. Finally, the authors show that the restart technique further improves the last-term convergence.

This paper proposes a conditional gradient algorithm that uses heavy ball type acceleration to solve the constrained optimization problem. After introducing the vanilla Frank Wolfe method which is one of the common methods to solve these types of problems, authors introduce their FW with heavy ball momentum and provide convergence guarantees on L-smooth and convex objectives under various step-size choices. Furthermore, they also consider another version of the algorithm (FW with restart) which solves two subproblems to further improve the primal-dual error in the problem. Lastly, the authors present the performance of their algorithms on binary classification and matrix completion.