Heavy Ball Momentum for Conditional Gradient
Authors: Bingcong Li
Alireza Sadeghi
Georgios B. Giannakis
Venue: NeurIPS 2021 Poster (2021)
Keywords: Frank Wolfe
conditional gradient
heavy ball momentum

Abstract: Conditional gradient, aka Frank Wolfe (FW) algorithms, have well-documented merits in machine learning and signal processing applications. Unlike projection-based 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 \textit{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.

Heavy Ball Momentum for Conditional Gradient
Bingeong Li
Alireza Sadeghi
Georgios B. Giannakis
University of Minnesota Twin Cities
Minncapolis, MN, USA
(1ixx5599, sadeg012, georgios @umn. edu
Abstract
Conditional gradient, aka Frank Wolfe (FW) algorithms, have well-documented merits in machine learning and signal processing applications. Unlike projection- based 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 unifying perspective on the primal-dual (PD) convergence, and enjoys tighter per iteration PD error rate, for multiple choices of step sizes, where PD error can the stopping criterion in practice. In addition, it is asserted that restart, 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.
1 Introduction
This work studics momentum in Frank Wolfe (FW) methods [9, 10, 16, for solving
min fx))
xEX
Here, is convex function with Lipschitz continuous gradients, and the constraint set X Rd is assumed convex and compact, where is the dimension variable x. Throughout, we let x* e X denote 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 subproblem with a linear loss, i.e., Vk++ arg min f(xx), v) kth iteration, and then updates X as a convex combination of X₃ and V 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, 20j demonstrates that at least O( linear subproblems are required to ensure f(xx) ) fxx) I c, which does not guarantee that momentum is beneficial for FW, because 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, well as numerical improvement. To this end, outline first the primal convergence.
Primal convergence. The primal enror refers to f(xx) f(x"). It is guaranteed for FW that fx*) fxx) (1/k), Yk 2 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 (NcurIPS 2021).

---

Table I: A comparison of HFW with relevant works. The "computation" in the third column is short
for "the number of required FW subproblems to calculate the PD error per iteration."
reference
computation
PD conv. type
PD conv. rate
[16]
subproblem
Type
27L,D*
+[K+1]
[18]
2 subproblems
Type II
21,1"
Vk
vk+11
[28]
2 subproblems
Type II
41.D² Vk
I+T
This work (Alg. 2)
subproblem
Type II
21.D vk
K+T
This work (Alg. 3) 2 subproblems
Type II
21.D
Vk with 2 0
k+1+61
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 shown to converge, can be safely used as the stopping criterion: whenever the PD error is less than some prescribed c >> 0. 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.
S c cis ensured automatically.
established in [6, 10, 16] that the minimum PD error sufficiently small, namely minke (1..... K) PDError,
O ((x) ). where K is the total number of iterations. We term such bound for the minimum PD error as Type guarantee. Another stronger guarantee, which directly implies Type I bound, emphasizes the per iteration convergence, e.g., PDErrOr; S (OE)), Ak. We term such guarantees as Type II bound. A Type II bound is reported in [18, Theorem 2), but with an unsatisfactory i 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 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 adopt jointly with heavy ball. In succinet 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 effectiivneess of heavy ball momentum. As byproduct, a simple yet efficient means of computing local Lipschitz constants becomes available to improve the numerical efficiency of smooth step sizes 22].
Notation. Bold lowercase (capital) letters denote column vectors (matrices); ||x|| stands for a norm of vector x, whose dual norm is denoted by ||x||<; and (x, is the inner product of x and y.
2 Preliminaries
This section outlines FW, starting with standard assumptions that will be taken hold true throughout. Assumption 1. (Lipschitz continuous gradient.) The objective function f X - IR has L-Lipchitz continuous gradients; i.e., f vf())). S L|x yll, Vx,y X.
Assumption 2. (Convexity.) The objective function f X + is convex; that is, f(y) - f(x) 2
(Vf(x), x), Vx, X.
Assumption 3. (Convex and compact constraint set.) The constraint set X C. Rd is convex and compact with diameter D, that is, ||x yll D,Vx,y E X.

---

FW for solving (1) under Assumptions 1 3
Algorithm 1 FW [9]
listed in Alg. 1. The subproblem in Line can be visualized geometrically as minimizing a supporting hyperplane of (x) at Xx, i.e.
1: Initialize: Xy a
2: for == 0, 0.1..... K do
3: Ve++ arg minve (V (xx),,
Vi+1 arg min (xx) + fxxs), xk).
4: Xx+1 = 1/s )xx 7/6 VK+1
veX
5: end for
(2)
6: Return: XK
For many constraint sets, efficient implementa-
tion closed-fore solution is available for Vk+11 e.g., [16] for comprehensive summary.
Upon minimizing the supporting hyperplane in (2), X is updated as a convex combination of Vk+1 and X2 in Line that projection is required. The choices on the step size лk E [0, 1] will be discussed shortly.
The PD error of Alg. 1 is captured by the so-termed FW gap, formally defined as
G. = (Vf(x)), X Vk+1)
fxx))-((x + f(x')xxx))))))))>
min
f(xx) + (Vf(x)). V Xx) VEX
(3)
primal error
dual emnor
where the second equation because of (2). It be verified that both primal and dual errors marked in (3) are no less than 0 by appealing to the convexity of f. If Ge converges, one can deduce that the primal error converges. For this reason, 9% typically used as a stopping criterion for Alg. Next, we focus on the step sizes that ensure convergence.
Parameter- free step size. This type 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 7/
2_ which ensures converging primal error f fxxx) f(x') I
2LD
K+I Ak > and
F+2
weaker claim the PD error, minge (1.... K) G 27 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 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. [22]
m min (Vf(x,), X2 VR+1) x
(4)
L L|
Despite the estimated T. is typically too pessimistic to capture the local Lipschitz continuity, such a step size ensures fx*+11 fxxx);; ); derivations in Appendix A.I. The PD convergence studied
in [1 I], where the result is slightly weaker than that of [28].
FW with heavy ball momentum
After a brief recap of vanilla FW, focus on the benefits heavy ball momentum for FW under multiple step size choices, with special emphasis on PD errors.
3.1 Prelude
HFW is summarized in Alg. 2. Similar GD with heavy ball momentum [2), Alg. 2 updates
decision variables using a weighted average of gradients g++1- addition, the update direction of
Alg. 2 is no longer guaranteed to be descent one. This is because in HFW, (V [xxx)) ), X2, V can be negative. Although a stochastic version of heavy ball momentum was adopted in [27] and its variants, e.g., [37]. 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 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 fo-norm ball, that is, X [x|| R). In this case, we have V6+1 R g++ g++1lla 8k-1 10-110 in Alg, 2. The momentum gx+1 smooth out the changes of (Vf(x))) resulting

---

in more concentrated sequence (vk+1}. Re-
Algorithm 2 FW with heavy ball momentum
call that the PD error closely related Vi-1
1: Initialize: X E X go = fxxo)
[ef. equation (3)]. We hope the "concentration" of (Vs++1 J to be helpful reducing the changes of PD error among consecutive iterations so that
2:
for k = 0, 1...................... K do
gt + V (xx)) 4: Va++1 arg min (g++1, v)
3:
gk+1 = (1
a Type II PD error bound is attainable.
5:
X|++ = (1 - 1/2 X 7h V++1
A few concepts are necessary to obtain a tight- ened PD error of HFW. First, we introduce the generalized FW gap associated with Alg. 2 that captures the PD error. Write g++1 explicitly ge+1 Er= 1 fxx)), where w
6: end for
7: Return: XK
6, +1 (1 - 6,) > O, VT 2 1, and w = 1I 6,) > O. Then, define a sequence of linear
functions (fx(x)) as
R
T 1 = Σ
Th [x(+)) + (Vf(x)), xx)], Wk 0.
(5)
T=0
It clear that P&+1 (x) is a weighted average of the supporting hyperplanes of f(x) at {x, } The properties of +x+1(xx, (x), and how they relate to Alg. 2 are summarized in the next lemma.
Lemma 1. For the linear function F (x) in (5), holds that: i) Vx+1 minimizes +x+1(x) over X; and, üi fxx) 2 1x+1 vk 2 0, Vx E X.
From the last lemma, one can see that Vi is obtained by minimizing & (x), which is an affine lower bound on (x). Hence, HFW admits geometric interpretation similar to that of FW. In addition,
based on (x) we can define the generalized FW gap.
Definition 1. (Generalized FW gap.) The generalized FW gap w.r.t. (x(xx)
Gk fxx) min T (x) f(xx) (v)(V))
x
In words, the generalized FW gap is defined as the difference between f(xx) and the minimal value of &x(x)) over X. The newly defined GR also illustrates the PD error
Gk = f(xx) - (v(v)) = f(xx) -(xx) f(x") + f(x") 4 (va)
(7)
peimal error
dual erroe
For the dual error, we have f(x*) pu((s) 2 Px(x*) - (vx))) 2 O, where both inequalities follow from Lemma 1. Hence, Go 2 0 automatically serves an overestimate of both primal and dual errors. When establishing the convergence of GR. 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 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. next pursue parameter choices that establish Type II convergence guarantees.
3.2 Parameter-free step size
We first consider parameter-free choice for HFW to demonstrate the usefulness of heavy ball
82 =
4k 2 0.
(8)
k
+ 2'
Such a choice on du puts more weight on recent gradients when calculating g since w ( The following theorem specifies the convergence of Gz.
Theorem 1. If Assumptions 1-3 hold, then choosing &a and mE in (8), Alg. 2 guarantees that
2LD2
Gx f((x)) 4 < k+1
2k
Theorem 1 provides much stronger PD guarantee for all ls than vanilla FW [16. Theorem 2]. In addition to readily computable generalized FW gap, our rate is tighter than [28], where the provided ALD* bound is R+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 I is the convergence of both primal and dual errors.

---

Corollary 1. Choosing the parameters as in Theorem 1, then Ak 2 1, Alg.2 guarantees that
primal conv:: f(xx) - f(x*) - k dual conv:: f(x") (v(x)) - 2LD
2LD²
k
Proof. Combine Theorem 1 with f(xx) f(x*) ) S GR and f(x') *x((v)) S Gn lef. (7)).
3.3 Smooth step size
Next, we focus on HFW with variant of the smooth step size
and Mi max (0, min (Vf(x)),xz - Vk+1) -v++1) L||VR+1 xx
6x ++
1
(9)
Comparing with the smooth step size for vanilla FW in (4), it can be deduced that the choice Ths in (9) has be trimmed to [0, 1J manually. This is because (xx(x)) Vk++)) is no longer guaranteed to be positive. The smooth step size enables an adaptive means of adjusting the weight for fx(x). To this, note that when Ti O, we have X++1 Xç. As result, gk+2 = (1 8 + -x+1 ( = (1 5 0x+1)g++1 + 6k+1 (f(x)) that is, the weight on fx(x)) is adaptively increased to 61 5k+1) + 5k+1 if one further unpacks g 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 Asssuptiions 1-3 hold, while The and 6g are chosen as in (9), Alg. 2 guarantees that
2LD
G3 = f(xx) (v(v)) S k+1 Ak
The proof of Theorem 2 follows from that of Theorem 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 omit for brevity. We further extend Theorem in Appendix B.4 by showing that if a slightly more difficult subproblem can be solved, it is possible ensure per step descent on the PD error; i.e., Gk+1 < Gk-
and 1/ via line search, HFW can guarantee a Type PD) Line search. When choosing 6N k+2
error of 2LD2 k+1 please refer to Appendix B.5 due to space limitation. For completeness, an iterative manner to update GE for using stopping criterion is also described in Appendix C.
3.4 Further considerations
There are more choices of 6R and 7/s leading to (primal) convergence. For example, one can choose extension of [27].' A proof is provided in Appendix B.7 for completeness. This analysis framework [27], however, has two shortcomings: i) the convergence can be only established using m--norm (recall that in Assumption 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 gx+1 V fx with errors but not momentum, therefore, it is difficult to obtain the same tight PD bound as in Theorem Our analytical techniques avoid these limitations.
6, d (0, 1) and 7 = (
When choosing 6₁- = 7Jk E we can recover Algorithm 3 in [1]. Notice that such a choice on òR makes g uniform average of all gradients. A slower convergence rate f(xx) f(x*)
O( L.D2 ink) 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 8 k+1 with qh using one of the following
1
options: i) m Z ii) as in (9); or iii) line search as in (26b). The generalized FW gap of Alg. then converges with rate
LD In(k ln(k+1)
= fxx)) Px. (Vx)
vk >
2k
We are unable to derive even primal error bound using the same analysis framework in [27] for step sizes listed in Theorem 1.
5

---

The rate in Theorem 3 has worse dependence on k relative to Theorems and 2. partially because too much weight is put on past gradients g.++1. suggesting that large momentum may not be helpful.
Heavy ball versus Nesterov's momentum. simple rule to compare these two momentums is whether gradient is calculated the converging sequence {xx} 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 oo-memory variant of Nesterov's momentum [20, 23, 24], which can be viewed as a combination of heavy ball and Nesterov's momentum, yields Type II PD error. However, compared with HFW, additional memory should be allocated. In sum, these observations suggest that heavy ball momentum essentially critical improve the PD performance of FW. Nesterov's '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 23].
3.5 A side result: Directional smooth step sizes
Common both FW and HFW is that the globally estimated L. might be too pessimistic for 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 another merit of (H)FW over projection based approaches.
Definition 2. (Directional Lipschitz continuous.) For two points x,y E X, the directional Lipschitz S L(x. 8 for any (1 a)x ay,
constant L y) ensures || f f(+)]l
3)= + By with some E [0, 1] and E 10.
In other words, the directional Lipschitz continuity depicts the local property on the segment between points and y. It is clear that L(x,
S L. Using logistic loss for binary classification as an example, we have y(x,y) I IN E (a: where N is the number of data, and a, is the 1x-yl
feature of the ith datum. As comparison, the global Lipschitz constant is L S 4N Σ ||a.1l2. We show in Appendix E that at least for a class of functions, including widely used logistic loss and quadratic loss, y(x,y) has analytical form.
Simply replacing (9) with L(Xx, Vk+ 14+1), i.e.
max (0 min [[XK; Vk+1 V6+1 X
( - Vs+1)
(10)
we can obtain what we term directionally smooth step size. Upon exploring the collinearity of x Xk+1 and Vk+1. simple modification of Theorem 2 ensures the PD convergence.
Corollary 2. Choosing óy = 2 and me via (10), Alg. ensures
2LD²
GN f(x)) (v S
Wk 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 shall see in numerical tests, directional smooth step sizes outperform the vanilla one by an order of magnitude.
4 Restart further tightens the PD error
Up till now it is established that the heavy ball momentum enables 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 smaller than generalized FW gap. Restart typically employed by Nesterov's '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,
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: xi E X, g0 = Vf(()), 8 O, C O. 9 9
2: while [not terminated] do
3: k < 0. gn (x
4: while g 9
0] and [not terminated] do
Check whether restart is needed
5:
og k+2+0"
6:
Sk+1 (1
jgg + o% (xxx)
7:
V&+1 arg arg x))
8:
xi+1 (1 Th )x + v
9:
VR+1 = arg min x (Vxxx++))
10:
9 = f(x++11 - 1 k++ (v
> Generalized FW gap
11:
G gi+1 (V (x(())), x 1
Vanilla FW gap
12:
13:
end while
Kg + k, x = x C5-1 2LD2
14:
k 8 1
end while
FW with heavy ball momentum and restart is summarized under Alg. 3. For exposition clarity, when updating the counters such as l and 8, we use notation 'r".. Alg. contains two loops. The inner loop is the same Alg. 2 except for computing standard FW gap (Line 11) in addition to the generalized one (Line 10). The variable K,, depicting the iteration number inner loop s, is of analysis purpose. Alg. 3 can be terminated immediately whenever (gg } < for desirable e > 0. The restart happens when the standard FW gap is smaller than generalized FW gap. And after restart, gk+1 will be reset. For Alg. 3, the linear functions used for generalized FW gap are defined stage-wisely
xi) (x) (x) (1 (x) 02 fx(() + (Vf(x)), xxx,, x 0.
xx) f(x))
(11a)
(1lb)
It can be verified that v minimizes + (x) over X for any k 2 0. In addition, also have fxxx) (v(()) = _ where v arg minxex (x)).
There are two tunable parameters V/ and og. The choice on of has been provided directly in Line where it is adaptively decided using variable O' relating to the generalized FW gap. Three choices are readily available for : 1/f og: ii) smooth step size:
T max 0, min {
(VF(x)) xi.
V 11
(12)
T. [. xf
and, iii) line search
1 = arg min s((1- - x))x 1(vb+11) [E[00.]
(13)
Note that the directionally smooth step size, i.e., replacing L with L(xi, vi+1) in (12) is also valid for convergence. We omit reduce repetition. Next we show how restart improves the PD error
Theorem 4. Choose vi via one of the three manners: i) nh 5%. ii) in (12); iii) in (13). If there is no restart (e.g., s = 0 when terminating). then Alg. 3 guarantees that
2LD k+1 1
Ga f(x+) (v(v
(14a)
restart happens, in additional (14a), have
2LD²
5 = f(x)) - 2x
Vk 2 1,22,, with C* > 1+
Σ Kj. j=0
(14b)
k C
Besides the convergence of both primal and dual emror of Alg. 3, Theorem implies that when no restart happens, the generalized FW gap is smaller than the standard one, demonstrating that the
7

---

100
(a) w7a
(b) realsim
(c) mushroom
(d) ijennl
Figure I: Performance of FW variants for binary classification with the constraint being f-rnr ball (first row), an -ormm ball (second row), and an n-support norm ball (third row).
former is more suitable for the purpose "stppping criterion". When restarted, Theorem 4 provides strictly improved bound compared with Theorems I, 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 also required, once again confirms the power of heavy ball momentum to improve the constants in the PD eтror rate, especially with the aid of restart. The restart scheme (with slight modification) also be employed in [23, 24, 28) tighten their PD) emror.
5 Numerical tests
This section presents numerical tests to showcase the effectiveness of HFW on different machine learning problems. Since there are parameters' choices for HFW in Theorems and 3, term them as weighted FW (WFW) and uniform FW (UFW), respectively, depending on the weight of (xx)) in g++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 2 (FW); and, FW with smooth step size (FW-s) in (4).
b+2
5.1 Binary classification
We first test the performance of Alg. 2 on binary classification using logistic regression
N
1
f(x) = Σ In (x 1=1
(15)
N
Here b;) is the (feature, label) pair datum i, and N is the number of data. Datasets from L are used in the numerical tests, where details of the datasets are deferred to Appendix F due to space limitation.
norm ball constraint. We start with X' [x|]|x|2 < R). The primal emrors are plotted in the first row of Fig. 1. We use primal error here for fair comparison. 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 relived through directional smooth step sizes as we shall shortly. Among parameter-free step sizes, it can be seen that WFW consistently
Phttps: http:p:://wwwwccc
wttp//wwwww.......///..//......s csie. atu. http://wwwww..oooo..oooooo///aa/ http:///w/ww..////tttt/t/t//// /ttps//ddaaaattaaaaaeeeeeeeeeeee html.

---

20
180
20
(a) n-rm ball
(b) n-rmr ball
(a) 1-0orm ball
(b) E -norm ball
Figure 2: Performance of directionally smooth step sizes. (a) and (c) are tested on mushroom; and (b)
and (d) use ijeml.
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
X (1 7k Xx + 776 R ge+1 with normalized gradient descent (NGD) one, that is given by 1
X Projx Xx Tik 1| However, there is also subtle difference between HFW and NGD) updates. Indeed, when projection is in effect, X in NGD will lie on the boundary of the f-rnrrm ball. Due to the convex combination nature of the update in HFW, it is unlikely to have Xx+1 on the boundary, though can come arbitrarily close.
& f-oorm ball constraint. Here X' = |x|||x||= S R} denotes the constraint set that promotes sparse solutions. In the simulation, R 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 w 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 tighter relaxation of sparsity enforcing to norm ball combined with an 22-norm penalty compared with ElasticNet [38]. It gives rise X' conv(x|| |x|||] I n, ||||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 solution whose sparsity 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 ijennl. Regarding parameter- frree 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. validate the effectiveness of directionally smooth (-ds) step sizes. For all datasets tested, the benefit of adopting L(Xk, Vk+11 is evident, as 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 generalized version of [27], where we set 5e 5 E (0, 1), vk in Alg. 2. Two specific choices, i.e., 5 = 0.6, and 8 0.8, plotted in Fig. 3, where the fo-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 5 has major impact on convergence behavior, while WFW avoids this need for manual tuning of 5. The performance of WFW with restart, i.e., Alg. 3, is also shown in Fig. 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 inter- est. 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 attractive as a stopping criterion when a so- lution with moderate accuracy is desirable.
(a) la norm ball
(b) n-supp norm ball
Figure 3: Comparison of HFW with other algo- rithms on muchroom.

---

FW
FW-s
150
WFW
WPW
16'
120
WFW-s
UFW
FFFW
UFW
200
400
600
800
1000
0
200
400
600
800
1000
(a) objective
(b) rank
Figure 4: Performance of FW variants for matrix completion on MovieLens100K.
In nutshell, the numerical experiments suggest that heavy ball momentum performs best with parameter-free step sizes with the momentum weight carefully adjusted. WFW mainly recom- mended 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 the need of while directionally smooth step sizes can be helpful to alleviate this convergence slowdown.
5.2 Matrix completion
This subsection focuses matrix completion problems for recommender systems. Consider matrix A mmx with partially observed entries, i.e., entries As for (i.j) E K. are known, where K. C f1...., m) x (1....,77 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
Σ (Xi Aij)2 s.t. X nnc S R. (i.))K
(16)
2
Problem (16) difficult to solve using GD because projection
a nuclear norm ball requires
full SVD, which has complexity O (mmnm A n)) with (m A n) == min(m,n) In contrast, FW and its variants are more suitable for (16) since the FW subproblem has complexity less than ((m)) [2].
Heavy ball based FW are tested using dataset MovieLens//0K Foolowing the initialization of [11] the numerical results can found Fig. 4. Subfigures (a) and (b) depict the optimality error and rank versus & for R = 3. For parameter-fres free step sizes, WFW converges faster than FW while finding solutions with lower rank. The low rank solution of UFW 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 the priority, WFW is more attractive; while UFW-s is useful for finding low rank solutions.
6 Conclusions and future directions
This work demonstrated the merits heavy ball momentum for FW. Multiple choices of the step size ensured 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. novel and general approach constants FW type algorithms. Numerical tests in the paradigms of logistic regression and matrix completion demonstrated the effectiveness of heavy ball momentum in FW.
developed to compute local Lipschitz
Our future research agenda includes performance evaluation of heavy ball momentum for various learning tasks. For example, HFW holds great potential when faimess is to be accounted for [35].
Phttps: / http:///gooo....///// org/datasets htt.aaatttttteeeeeeeeeeeeeeeee/e
10

---

Acknowledgement
This work is supported by NSF grants 1901 134, 2126052, and 2128593. The authors would also like to thank the anonymous reviewers for their feedback.
References
[1] J. D. Abernethy and J.-K. Wang, "On Frank-Wolfe and equilibrium computation," in Proc. Advances in Neural Info. Process. Syst., 2017, pp. 6584-6593.
[2] Z. Allen-Zhu, E. Hazan, W. Hu, and Li, "Linear convergence of Frank-Wolfe type algorithm
over trace-norm balls," " in Proc. Advances in Neural Info. Process. Syst., 2017, pp. 6191-6200.
[3] A. Argyriou, R. Foygel, and N. Srebro, "Sparse prediction with the k-support norm," in Proc. Advances in Neural Info. Process. Syst. 2012. pp. 1457-1465.
[4] R. M. Bell and Y. Koren, "Lessons from the Netfix prize challenge." SiGKDD Explorations, vol. 9, no. 2, pp. 75-79, 2007.
[5] J. Bennett, S. Lanning et al., "The Netflix prize," in Proc. KDD cup and workshop, vol. 2007. New York, NY, 2007, p. 35.
[6] K. L. Clarkson, "Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm," ACM Transactions on Algorithms (TALG), vol. 6, no. 4, p. 63, 2010.
[7] J. Diakonikolas and L. Orecchia, "The approximate duality gap technique: A unified theory of first-order methods," 5 SIAM Journal on Optimization, vol. 29, pp. 660-689, 2019.
[8] M. Fazel, "Matrix rank minimization with applications," 2002.
[9] M. Frank and P. Wolfe, "An algorithm for quadratic programming." Naval research logistics quarterly, vol. 3, no. 1-2, pp. 95-110, 1956.
[10] R. M. Freund and P. Grigas, "New analysis and results for the Frank-Wai Wolfe method," Mathe- matical Programminng, vol. 155, no. 1-2, pp. 199-230, 2016.
[11] R. M. Freund, P. Grigas, and R. Mazumder, "An extended Frank- -olfe method with "in-face" directions, and its application to low-rank matrix completion." SIAM Journal on Optimization, vol. 27, no. 1, pp. 319-346, 2017.
[12] M. Fukushima, "A modified Frank-Wolfe algorithm for solving the traffic assignment problem." Transportation Research Part B: Methodological, vol. 18, no. 2, pp. 169-177, 1984.
[13] D. Garber and E. Hazan, "Faster rates for the Frank-Wou Wolfe method over strongly-convex sets," in Proc. Intl. Conf. on Machine Learning, 2015.
[14] E. Ghadimi, H. R. Feyzmahdavian, and M. Johansson, "Global convergence of the heavy-ball method for convex optimization," in Proc. of European control conference, 2015, pp. 310-315.
[15] Z. Harchaoui, A. Juditsky, and A. Nemirovski, "Conditional gradient algorithms for norm- regularized smooth convex optimization," Mathematical Programming, vol. 152, no. 1-2, pp. 75-112. 12, 2015.
[16] M. Jaggi, "Revisiting Frank-Woll Projection-free sparse convex optimization." " in Prec. Intl. Conf. Machine Learning, 2013, pp. 427-435.
[17] A. Joulin, K. Tang, and L. Fei-Fei, "Efficient image and video co-localization with Frank-Wolfe algorithm,"" in Proc. European Conf. on Computer Vision. Springer, 2014, pp. 253-268.
[18] Lacoste-Julien and M. Jaggi, "On the global linear convergence of Trank-Wolfs optimization variants," in Proc. Advances in Neural Info. Process. Syst., 2015, pp. 496-504.
[19] S. Lacoste-Julien, F. Lindsten, and F. Bach, "Sequential kernel herding: Frank- optimiza- tion for particle filtering," Proc. Inil. Conf. on Artificial Intelligence and Statistics, 2015, pp. 544-552.
[20] G. Lan, "The complexity of large-scale convex programming under linear optimization oracle," arXiv preprint 1rXiv:109.55500 2013.
[21] G. Lan and Y. Zhou, "Conditional gradient sliding for convex optimization," t SIAM Journal on Optimization, vol. 26, no. 2, pp. 1379-1409, 2016.

---

[22] E. S. Levitin and B. T. Polyak. "Constrained minimization methods," USSR Computational mathematics and mathematical physies, vol. 6, no. 5, pp. 1-50, 1966.
[23] B. Li, M. Coutino, G.B. B. Giannakis, and G. Leus, "A momentun-guided Frank-Wolf algorithm," IEEE Trans. on Signal Processing, vol. 69, pp. 3597-3611, 2021.
[24] B. Li, L. Wang. G. B. Giannakis, and Z. Zhao, "Enhancing Frank Wolfe with an extra subprob- lem," in Proc. of 35th AAAI Conf. on Artificial Intelligence, 2021.
[25] B. Liu, X.-T. Yuan, S. Zhang, Q. Liu, and D. N. Metaxas, "Efficient k-support-non regularized minimization via fully corrective Trank-Wolft method." Proc. Inil. Joint Conf. on Artifical Intelligence, 2016, pp. 1760-1766.
[26] G. Luise, S. Salzo, M. Pontil, and C. Ciliberto, "Sinkhorn barycenters with free support via Frank-Wolfe algorithm," in Proc. Advances in Neural Info. Process. Syst., 2019, pp. 9318-9329.
[27] A. Mokhtari, H. Hassani, and A. Karbasi, "Stochastic conditional gradient methods: From convex minimization to submodular maximization," arXiv preprint arXiv: (0:i::8800.00000 095400954, 2018.
[28] Y. Nesterov, "Complexity bounds for primal-dual methods minimizing the model of objective function," Mathematicul Progrumming, vol. 171, no. 1-2, pp. 31 1-330, 2018.
[29]
Introductory lectures on convex optimization: A basic course. Springer Science &
Business Media, 2004, vol. 87.
[30] T. Nguyen, X. Fu, and R. Wu, "Memory--fficient convex optimization for self-dictionary separable nonnegative matrix factorization: A frank-wolfe approach," arXiv preprint arXiv:2109.11135 2021.
[31] B. O' O'donoghue and E. Candes, "Adaptive restart for accelerated gradient schemes," Foundations of computational mathematics, vol. 15, no. pp. 715-732, 2015.
[32] B. T. Polyak, "Some methods of speeding up the convergence iteration methods." Ussr computational mathematics and mathematical physics, vol. 4, no. 5, pp. 1-17, 1964.
[33] A. Schwing, T. Hazan, M. Pollefeys, and R. Urtasun, "Globally convergent parallel MAP LP relaxation solver using the Frank-Wolfe algorithm."" in Proc. Intl. Conf. Machine Learning, 2014, pp. 487-495.
[34] M. Ye, C. Gong, L.. Nie, D. Zhou, Klivans, and Q. Liu, "Good subnetworks provably exist: Pruning via greedy forward selection," in Proc. Intl. Conf. Machine Learning. 2020.
[35] M. B. Zafar, 1. Valera, M. Gomez Rodriggzd and K. P. Gummadi, "Fairness constraints: A
flexible approach for fair classification." " The Journal of Machine Learning Research, vol. 20,
no. 1, pp. 2737-2778, 2019.
[36] I.. Zhang, G. Wang, D. Romero, and G. B. Giannakis, "Randomized block Frank-Wolfe for convergent large-scale learning." IEEE Transactions Signal Processing, vol. 65, no. 24, pp. 6448-6461, 2017.
[37] M. Zhang, Z. Shen, A. Mokhtari, H. Hassani, and A. Karbasi, "One sample stochastic Frank- Wolfe," in Proc. Intl. Conf. on Artificial Intelligence and Statistics. PMLR, 2020, pp. 4012- 4023.
[38] H. Zou and T. Hastie, "Regularization and variable selection via the elastic net," Journal of the royal statistical society: series B (statistical methodology). vol. 67, no. 2, pp. 301-320, 2005.
12


Reviews:
[{"review_id": "zCG4hrDxe7", "reviewer": "Reviewer_DsMv", "summary": "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.\nOther 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.\nFinally, the authors show that the restart technique further improves the last-term convergence.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality and quality:\nThe result is interesting to me as the momentum technique has been the \"crown jewel\" of first order optimization but is rarely studied in the literature of Frank-Wolfe. The slowness of the FW is usually attributed to the zig-zag phenomenon and \"smoothing\" the update direction seems (and is proved to be in this paper) a plausible strategy to alleviate this issue. \n\nClarity:\nThis paper is well written and I enjoy reading it (there could be some bias because I am familiar with the literature already). The idea of generalized FW gap is well explained. \n\nSignificance:\nThis is an important result to the literature of Frank-Wolfe method. \n\nQuestions:\nIn the experiment section, the first row of Figure 1 looks impressive. However, since the constraint is the `$\\ell$2-norm ball, the HFW method is equivalent to the normalized gradient descent method with heavy ball momentum (with an additional moving average on the variable). The zig-zag phenomenon is potentially missing in this setting and such a success may be due to that the HFW in this setting is indeed of the $O(1/k^2)$ accelerated convergence rate. The authors should clarify this point in their revision because this will not be a common observation of FW under a polytope constraint where FW often has a zig-zag trajectory.\n\n\ntypos: \nIn Table 1, the \"computation\" in the 'second' column.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This work is theoretical and I believe there is no potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "aEmtibd2SOq", "reviewer": "Reviewer_rTkg", "summary": "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.\n\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I believe heavy ball adaptation of the FW algorithm is an original idea. In practice, computing Lipschitz constants may be expensive or even impossible; but these assumptions are common in the literature and provides helpful tools to understand the performance of the algorithms. In that perspective, I believe the authors did a good work providing convergence analysis for various step-size choices (especially the parameter-free step size which does not require computation of these parameters).\n\nI am concerned about the computation cost of solving two subproblems at Algorithm 3, even though restart improves the PD error. Can authors also add the computation time or memory use comparisons of these algorithms? I suspect that the restart approach may be costly at large problems and the benefit we get from restart may not compensate for the PD error improvement. \n\nI found the discussions in the paper clear; however, it would be great if the authors can provide the advantage of heavy ball momentum over Nesterov's momentum numerically. In addition to discussion on the paper, including a comparison of memory use (or Type II PD error) on these algorithms could show the advantage of HFW over Nesterov or make the motivation more clear.\n\nLastly, best to my knowledge, projected gradient descent methods such as projected GD are commonly used in practice. Therefore, including projected GD in the numerical experiments (in addition to FW variants) would help to understand the performance of the algorithm. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Fairness in machine learning is becoming more important nowadays and there has been some work to provide more fair (!) models in machine learning. One of the proposed methods is to introduce some fair constraints (!) to optimization problems (e.g. Fairness Constraints: A Flexible Approach for Fair Classification by Zafar et al). Therefore, I believe this work can have potential in the context of Fairness in ML. ", "review_text": "", "extra_scores": {"ethical_concerns": "I don't see any ethical issues with this paper.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "a0K9HxN-mO-", "reviewer": "Reviewer_Tvht", "summary": "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.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In my view, the main and most original contribution of this work is the proof technique used in Theorem 1. The conciseness and simplicity of the proof of Theorem 1 make the technique not only elegant but likely useful in other related Frank-Wolfe type setups. The remaining content of the paper, in my view, is ancillary.\n\nMore specifically, I feel that the core proof idea of defining the dual error via a weighted average of supporting hyperplanes and having this weighted average of gradients correspond to momentum in the FW algorithm is a very nice and original idea. In hindsight, this is a simple and perhaps natural idea, since the averaging of gradients is reminiscent of dual averaging, but good ideas are often obvious is hindsight.\n\nGranted, I have not written a Frank-Wolfe paper myself so I do not claim full expertise in this area. However, I have read many Frank-Wolfe-type papers, and this technique feels original and worthy publication to me.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "HMUHcUhbSj", "reviewer": "Reviewer_BKNr", "summary": "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.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "From my point of view, this is a very good paper. The presentation is clear and concise and, to the best of my knowledge, the reported results and proof techniques are novel and correct. FW algorithms are relevant for various applications and incorporating heavy ball momentum seems natural. This paper fills a gap in the sense that improved convergence guarantees for this case are shown. The reported numerical results support the theoretical claims. I have no further concerns.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: While the paper received a relatively high score by the reviewers and it does contain some interesting ideas, I am not not quite convinced that the merit justifies acceptance at NeurIPS. Not wanting to overrule the reviewers I recommend weak acceptance.  
Decision: Accept (Poster)