Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper studies the Frank-Wolfe algorithm applied to generalized self-concordant functions. The main result is that the basic Frank-Wolfe method with the standard 2/(t+2) step size and a simple modification to check for feasibility/monotonicty (M-FW) achieves an O(1/t) convergence rate. They show convergence in terms of primal gap, as well as Frank-Wolfe gap, and improved rates under uniform convexity assumptions. Experimental results show that for the class of problems considered, the M-FW method is very competitive, especially in terms of run time, as compared to other FW variants.
main_review: Originality:  this work considers a new algorithm/analysis that extends the literature on FW and self-concordant functions. The algorithm proposed is simpler and more elegant than previous algorithms for this problem, and its analysis is clean. The relevant literature is adequately cited and it is clear how this work differs from previous contributions.

Quality:  this is a high quality submission. The results appear to be strong and mathematically correct, to the best of my knowledge. This is a complete and thorough piece of work.

Clarity:  the paper is very well-written and complete.

Significance:  this paper makes a very nice contribution to an important problem. This is the first paper to study the basic Frank-Wolfe method (with a very slight modification) on generalized self-concordant functions. All other papers require stronger assumptions (e.g., second order information) and/or more complicated algorithms. The analysis is clear and the theoretical convergence results are strong. The experimental results also serve to support the theoretical results in a meaningful way. Overall, I think this paper makes a very strong contribution and is perhaps the strongest paper that I've seen on Frank-Wolfe methods specifically for self-concordant functions.

Minor Comments:

1.) The font appears to be non-standard?
2.) Should Theorems 2.9 and 2.10 say "uniformly convex set" instead of "strongly convex set"?
limitations_and_societal_impact: Yes/NA
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: Consider the problem of minimizing a generalized self-concordant function on a convex compact set. Notice that a generalized self-concordant function is not smooth (Lipschitz gradient) in general. This paper shows that if we slightly modify the Frank-Wolfe method such that the sequence of function values is non-increasing, then standard analyses of the Frank-Wolfe method based on smoothness and/or strong convexity basically go through. The paper gives a $O(1/t)$ convergence guarantee for the proposed Monotonous Frank-Wolfe (M-FW) method and linear convergence rates for M-FW with backtracking with additional assumptions. 
main_review: I like the simple yet very effective idea presented in this paper. Dvurechensky et al., 2020b also study generalized self-concordant minimization by Frank-Wolfe-type methods; the analyses therein treat generalized self-concordant inequalities (Proposition 2.1 in the submission) as analogues of the standard smoothness inequality and require arguably quite complicated calculations; moreover, their analytical step size involves computing the local norm w.r.t. the Hessian of the function, adding computational burden. In comparison, this paper forces the the sequence of function values to be non-increasing. Hence, it suffices to consider the (well-defined) local smoothness and strong convexity parameters on the level set at the initial iterate. The analysis becomes much simpler; the "analytical" step size is simply 2/(t + 2). 

The presentation is clear. However, the definition of the Backtrack function in Algorithm 2 is missing in the main text and presented in the appendix, which harms readability. 

I have checked the proof in Section 2. I do not check the proofs in the supplementary material. 

Other comments: 
- As far as I know, the paper "Frank-Wolfe works for non-Lipschitz continuous gradient objectives: Scalable Poisson phase retrieval" by Odor et al. is the first work on Frank-Wolfe minimizing a self-concordant function with a simple step size similar to the one proposed in this paper. Hence, I think the paper should be cited. 
- Whereas it is popular to put "all you need" in ML paper titles nowadays, I think such a title is obviously imprecise and mostly misleading. How can one rigorously justify that the step size proposed in this paper is "all you need"? 
- Please make $D$ in the Frechet derivatives and $d$ in Remark 2.2 upright. Then, for example, we can easily tell the $D$ in Definition 1.3 is not the diameter of the constraint set. 
- I don't get Line 202--205, though the conclusion is obviously correct. 
- Line 241: What does "a reasonable assumption" refer to? Perhaps there are missing words. 
limitations_and_societal_impact: Whereas simplicity in the analysis and algorithm is definitely appreciated, it is natural to ask then, whether there is any tradeoff in the iteration complexity or computational complexity. I suggest the authors make a comparison between their results and results in literature and, if possible, add the discussion to the main text.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work studies simple step size, i.e., 2/(t+2), in FW for generalized self-concordant functions. The main idea is to wait the step size to shrink until f(x_{t+1}) <= f(x_t). By doing so, one can avoid relying on second order information or line search. 
main_review: While the main idea is interesting, but it looks to me that waiting for a satisfactory small step size (in Alg.1) is equivalent to a lazy manner for line search. And in fact, while waiting this small step size, one must also check f(x_t) or x_t \in dom f, it is intuitively not convincing that this scheme is more efficient than line search. There are some questions regarding this.

Q1. What are the choices of parameters (e.g., for line search) in different experiments? Is it possible to fine tune them?

Q2. How many iterations are needed to wait for a useful step size? If this number is small, it is not surprising that the proposed algorithm will have a small runtime compared with line-search.

Q3. Suppose that t is large, then it may take a long time to get a satisfactory step size since 2/(t+2) and 2/(t+1+2) may not differ too much. In such a case, it is not clear that why the proposed algorithm is more efficient than line-search.

========
I have read the rebuttal and updated my score accordingly. I do think that more discussions on comparison with line search should be added.

limitations_and_societal_impact: This is mainly a theoretical work that helps to understand FW for generalized self-concordant functions.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In this paper, the authors analyse the Conditional Gradient method (Frank-Wolfe algorithm) under the assumption that the objective is a generalized self-concordant function. They propose a simple variant of this method that uses both
1. the universal classical choice of the parameter: $\gamma_t = 2 / (2 + t)$
2. a check for monotonicity
3. a check for domain feasibility

For the method with these settings, the authors establish the global rate of the order O(1/t) in terms of the functional residual and in terms of the duality gap, on the given class of functions.
main_review: The paper is generally well-written. It adresses an interesting and popular research direction related to the analysis of the Conditional Gradient Methods under different assumptions on the problem structure.  In particular, the classes of self-concordant and generalized self-concordant functions are received a substentional attention after the work (Dvurechensky et al. 2020). In the latter paper, there were proposed different step-size strategies for the Frank-Wolfe method that ensure its global convergence. However, these strategies require some additional efforts (such as computation of the Hessian or a line-search).

In the current paper, the author propose a simple and universal stepsize policy ($\gamma_t = 2 / (2 + t)$) which ensures the global rate for the generalized self-concordant functions, when coupled with the monotonicity and feasibility checks. While the combination of these techniques is not novel, the overall setup and new convergence results seem to be interesting for me.

However, I have one major question related to the main result of the paper. For the classical FW algorithm, the known convergence rate is:
$f(x_t) - f^* <= LD^2 / t$ 
(up to constant factors), where L is the Lipschitz constant for the gradient and D is the diameter of the set. 
It looks that the result of Theorem 2.4 provides a bound which is not significantly better than this one. 
Instead of $L$, the authors use $L_f$, which is a Lipschitz constant not over the whole set, but only over the initial level set. The payment for such an improvement is an additional factor $T_{\nu}$ and the fact that the new convergence estimate holds for sufficiently big iterations only ($t  \geq T_{\nu}$).
It is not clear to me, how reasonable such result is. What if the value of $T_{\nu}$ is very big (and how big can it be?). Why $L_f$ is much better than $L$, and why it is important for applications.
Maybe, it would be helpful to provide an example when the new estimate is better than the classical one (and what are the values of all the parameters in this case).

Minor remarks:

1. It must be wrong 'et al' in the references: (Bach et al., 2010) and (Nesterov et al., 2018) 

2. Line 79: Maybe, it is better not to call the step size $\gamma_t = 2 / (2 + t)$ 'adaptive', since it is predefined in advance and does not depend on the actual objective (does not 'adapt' to its smoothness as for example in the line-search for the gradient methods). For me, it seems to be rather a 'conservative' strategy. I would just propose to pick the most standard terminology.

3. Line 91: 'potentially non-unique': it seems to me that the Hessian is assumed to be strictly positive definite on its domain (to ensure the definition of self-concordance). If so, the function is strictly convex and has a unique minimizer.

4. Line 123: 'Note that if the original objective function is generalized self-concordant, so is the new objective function.' It is not clear to me, why the sum of two generalized self-concordant function (with possibly different $\nu$) is generalized self-concordant. The usual log-barriers are just self-concordant ($\nu$ = 3 is fixed).

5. Line 193: The dot is probably missing after 'the primal progress'.

6. Line 186: 'in a similar fashion as is done in Dvurechensky et al. 2020b ...' -- I would prefer to see the proof of this fact included, or, at least, precise formulation and exact reference (Lemma ??) are given, since it looks like an important part of the proof.
limitations_and_societal_impact: -
review_title: null

Meta-review: Overall all reviewers, and also me, liked the paper, which very elegantly simplifies a recent result of interest regarding convergence of Frank-Wolfe for self-concordent functions, which required a more involved appraoch.
Decision: Accept (Poster)