Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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.
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.

More 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.

Granted, 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.
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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.
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.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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.
main_review: Originality and quality:
The 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. 

Clarity:
This 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. 

Significance:
This is an important result to the literature of Frank-Wolfe method. 

Questions:
In 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.


typos: 
In Table 1, the "computation" in the 'second' column.
limitations_and_societal_impact: This work is theoretical and I believe there is no potential negative societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.


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).

I 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. 

I 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.

Lastly, 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. 
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_title: null

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)