Simple steps are all you need: Frank-Wolfe and generalized self-concordant functions
Authors: Alejandro Carderera
Mathieu Besançon
Sebastian Pokutta
Venue: NeurIPS 2021 Poster (2021)
Keywords: Convex Optimization
Machine Learning

Abstract: Generalized self-concordance is a key property present in the objective function of many important learning problems.  We establish the convergence rate of a simple Frank-Wolfe variant that uses the open-loop step size strategy $\gamma_t = 2/(t+2)$, obtaining a $\mathcal{O}(1/t)$ convergence rate for this class of functions in terms of primal gap and Frank-Wolfe gap, where $t$ is the iteration count. This avoids the use of second-order information or the need to estimate local smoothness parameters of previous work. We also show improved convergence rates for various common cases, e.g., when the feasible region under consideration is uniformly convex or polyhedral.

Simple steps are all you need: Frank-Wolfe and generalized self-concordant functions
Alejandro Carderera
Mathieu Besançon
Sebastian Pokutta
Abstract
Generalized self-concordance is key property present in the objective function many important learning problems. We establish the convergence rate of simple Frank-Wolfe variant that uses the open-loop step size strategy Y = 2/(1+ 2), obtaining ((/1t) convergence rate for this class of functions in terms of primal gap and Frank-Wolfe gap, where is the iteration count. This avoids the use second-order information or the need to estimate local smoothness parameters of previous work. We also show improved convergence rates for various common cases, e.g., when the feasible region under consideration is uniformly convex or polyhedral.
Introduction
Constrained convex optimization is the cornerstone of many machine learning problems. We consider such problems, formulated as:
min f(x), xEX
(1.1)
where R" - R U (+0o) is a generalized self-concordant function and X C R" is compact convex set. When computing projections onto the feasible regions as required in, e.g., projected gradient descent, is prohibitive, Frank-Wolfe (FW) (Frank & Wolfe, 1956) algorithms (a.k.a. Conditional Gradients (CG) (Levitin & Polyak, 1966)) are the algorithms of choice, relying on Linear Minimization Oracles (LMO) at each iteration to solve Problem (1.1). The analysis their convergence often relies on the assumption that the gradient is Lipschitz- continuous. This assumption does not necessarily hold for generalized self-concordant functions, an important class of functions for which the growth can be unbounded.
1.1 Related work
In the classical analysis of Newton's method, when the Hessian of f is assumed to be Lipschitz continuous and the function is strongly convex, one arrives convergence rate for the algorithm that depends on the Euclidean structure of R" despite the fact that the algorithm affine-invariant. This motivated the introduction of self-concordant functions in Nesterov & Nemirovskii (1994), functions for which the third derivative is bounded by the second-order derivative, with which one can obtain an affine-invarian convergence rate for the aforementioned algorithm. More importantly, many of the barrier functions used in interior-poll methods are oiff-concordntt, which extended the use of polynomial-time interior-point methods many settings of interest.
'Georgia Institute of Technology. E-mail: alejandro. alejandro.carderenee marderera@gateedlee Zuse Institute Berlin. E-mail: besancon@zib.de $ Zuse Institute Berlin and Technische Universität Berlin. E-mail: pokutta@math.tu ttt.raatt...uubbb.deee.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

---

Self-concordant functions have received strong interest in recent years due to the attractive properties that they allow to prove for many statistical estimation settings (Marteau-Fere) et al., 2019; Ostrovskii & Bach, 2021). The original definition of self-concordance has been expanded and generalized since its inception, as many objective functions of interest have self-concordant-lik properties without satisfying the strict definition of colcoraccce,,.... For example, the logistic loss function used in logistic regression is not strictly self-concordant, but it fits into a class of properties and bounds as those obtained for self-concordant functions (Bach, 2010). This was also the case in Ostrovskii & Bach (2021) and Tran-Dinh et al. (2015), in which more general properties of these pseudo-self-com conf-cann functions were established. This was fully formalized in Sun & Tran-Dinh (2019), in which the concept of generalized self-conccl celforanno functioos was introduced, along with key bounds, properties, and variants of Newton methods for the unconstrained setting which make use of this property.
functions, which allows one to obtain similar
Most algorithms that aim to solve Problem (1.1) assume access to second-orde information, as this often allows the algorithms to make monotonous progress, remain inside the domain of f, and often, converge quadratically when close enough to the optimum. Recently, several lines of work have focused on using Frank-Wolf algorithm variants to solve these types of problems in the projection-free setting, for example constructing second-order approxima- tions to self-concordant f using first and second-order information, and minimizing these approximations over X using the Frank-Wole Wolfe algorithm (Liu et al., 2020). Other approaches, such as the ones presented in Dvurechensky et al. (2020a) (later extended in Dvurechensky et al. (2020b)), apply the Frank-Wolfe algorithm to a generalized self-concordans f, using first and second-order information about the function to guarantee that the step sizes are so that the iterates do not leave the domain of f, and monotonous progress is made. An additional Frank-Wolfe variant in that work, in the spirit of Garber & Hazan (2016), utilizes first and second order information about f, along with a Local Linear Optimization Oracle for X, to obtain a linear convergence rate in primal gap over polytopes given in inequality description. The authors in Dvurechensky et al. (2020b) also present an additional Frank- Wolfe variant which does not use second-order information, and uses the backtracking line search of Pedregosa et al. (2020) to estimate local smoothness parameters at a given iterate. Other specialized Frank-Wolfe algorithms have been developed for specific problems involv- ing generalized celf-connordant functions, such as the Frank-Wolfe variant developed for marginal inference with concave maximization (Krishnan et al., 2015), the variant developed in Zhao & Freund (2020) for (-homogeneous barrier functions, or the application for phase retrieval Odor et al. (2016), where the Frank-Wolfe algorithm is shown to converge on a self-concordant non-Lipschitz smooth objective.
1.2 Contribution
The contributions of this paper are detailed below and summarized in Table 1.
Simple FW for generalized self-concordant functions. We show that small variation of the original Frank-Wolfe algorithm (Frank & Wolfe, 1956) with an open-loop step size of the form y 2/(1+2),, where 1 is the iteration count is all that is needed rate of (1/r) in primal gap; this also answers an open question posed in Dvurechensky et al. (2020b). Our variation ensures monotonous progress while employing an open-loop strategy which, together with the iterates being convex combinations, ensures that we do not leave the domain of f. In contrast to other methods that depend on either a line search or second-order information, our variant uses only a linear minimization oracle, zeroth-order and first-order information and a domain oracle for fxx). The assumption of the latter oracle is very mild and was also implicitly assumed in several of the algorithms presented in Dvurechensky et al. (2020b). As such, our iterations are much cheaper than those in previous work, while essentially achieving the same convergence rates for Problem (1.1).
achieve a convergence
Moreover, our variant relying on the open-loop step size y, = 2/(1+2) allows us to establish ((1/1) convergence rate for the Frank-Wolfe gap, is agnostic, i.e., does not need to estimate local smoothness parameters, and is parameter- leading to convergence rates and oracle complexities that are independent of any tuning parameters.
2

---

Convergence
1 1 LS free?
Algorithm
Reference
Requirements
Primal gap
FW gap
FW-GSC
0(1/e)
[1, Alg.221
x X
SOO ZOO, DO ZOO, SOO, DO polyh. X, LLOO, SOO polyh. X, SOO Z00,D0 polyh. X, 200,D0
LBTFW-GSC
0(1/a)
[1, Alg.3]
/ x
MBTFW-GSC
0(1/s)
[1, Alg.5]
X X
FW-LLOO
O
[1, Alg.7]
X
ASFW-GSC
(log 1/e)
[1, Alg.8]
x
M-FW
0(1/8)
0(1/e)
This work
B-AFW
Ollog 1/6)
Ollog 1/e) This work
x/X
Table 1: Number of iterations needed to achieve an s-optimal solution for Problem 1.1. We denote Dvurechensky et al. (2020b) by [1], line search by LS, local linear optimization oracle by LLOO, and the assumption that X is polyhedral by polyh. X. The oracles listed under Requirements are the additional oracles needed, other than the FOO and the LMO.
Faster rates in common special cases. We also obtain improved convergence rates when the optimum is contained in the interior of X dom(/) (f), when the set X is uniformly or strongly convex, using the backtracking line search of Pedregosa et al. (2020). We also show that the Away-Step Frank-Wolfe algorithm (Lacoste-Julien & Jaggi, 2015; Wolfe, 1970) can use the aforementioned line search to achieve linear rates over polytopes. For clarity we want to stress that any linear rate over polytopes has depend also on the ambient dimension of the polytope; this applies to our linear rates and those in Table established elsewhere (see Diakonikolas et al. (2020)). In contrast the O(1/E) rates are dimension dimension-independeen
Numerical experiments. We provide numerical experiments that showcase the perfor- mance of the algorithms on generalized self-concordant objectives complement the theo- retical results. In particular, they highlight that the simple step size strategy we propose is competitive with and sometimes outperforms other variants on many instances.
After publication of our initial draft, in a revision of their original work, Dvurechensky et al. (2020b) added analysis of the Away-Step Frank-Wolfe algorithm which is complementary to ours (considering slightly different setup and regimes) and was conducted independently; we have updated the tables to include these additional results.
1.3 Preliminaries and Notation
We denote the domain of f as dom(f) {x R" f(x) < +o0} and the (potentially non- unique) minimizer of Problem (1.1) by x". Moreover, we denote the primal gap and the Frank-Wolfe gap E X n dom(f) ff h(x) def respectively. We use I| |I and (-.)) to denote the Euclidean norm, the matrix norm induced by symmetric positive definite matrix !/ Rox., and the Euclidean inner product,
f(x)) and g(x) del maxvex (xx(),, v),
respectively. We denote the diameter of as D maxx,yex ||x - yll. Given non-empty set X с R" we refer its boundary Bd(X) and to its interior as Int (X). We A, denote the probability simplex of dimension n. Given a compact convex set C s dom(f) we denote We assume access to:
1.C uEC.deRa
max ||d]| /Idll| and J
min ueC.deR"
||dll /|
1. Domain Oracle (DO): Given X, return true if e dom(f), false otherwise.
2. Zeroth-Order Oracle (Z00): Given dom(f), return fx).
3. First-Order Oracle (FO0): Given x E dom(f), return (x()).
4. Linear Minimization Oracle (LMO): Given RR", return argmin (x, d).
The FOO and LMO oracles are standard in the FW literature. The ZOO oracle is often implicitly assumed be included with the FOO oracle; we make this explicit here for clarity. Finally, the DO oracle is motivated by the properties of generalized self-concordant functions. is reasonable to assume the availability of the DO oracle: following the definition of the function codomain, one could simply evaluate f at x and assert f(x) < +0o, thereby combining the DO and ZOO oracles into one oracle. However, in many cases testing the membership of x dom(f) is computationally less demanding than the function evaluation.

---

Remark 1.1. Requiring access to zeroth-order and domain oracle are mild assumptions, that were also implicitly assumed in one of the three FW-variants presented in Dvurechensky et al. (2020b) when computing the step size according to the strategy from Pedregosa et al. (2020); see Line 3 in Algorithm in the Appendix. The remaining two variants ensure that x E dom(f) by using second-ord -rder information about f, which we explicitly do not rely on.
The following example motivates the use of Frank-Wolfe algorithms in the context of general- ized self-concordant functions. We present more examples in the computational results.
Example 1.2 (Intersection of a convex set with a polytope). Consider Problem (1.1) where X P n C, P is a polytope over which we can minimize linear function efficiently, and C is a convex compact set for which one can easily build a barrier function.
P
P
P
0.5
40
C
6.0
C
4,5
(a) Plot of f(x).
(b) Plot of f(x) + 1 (x)).
(c) Plot of f(x) + (xc(
Figure 1: Minimizing fxx over P nc, versus minimizing the sum of f(x) and (x(x) over P for two different penalty values μ² and μ such that n μ.
Solving a linear optimization problem over X may be extremely expensive. In light of this, we can incorporate into the problem through the use of barrier penalty in the objective function, minimizing instead f(x) + +xbc(() where (x) is log-barrier function for C and a parameter controlling the penalization. This reformulation illustrated in Figure Note that if the original objective function is generalized ceff-concordant, so is the new objective function (see Proposition in Sun & Tran-Dinh (2019)). We assume that computing the gradient of f((x) + c is roughly as expensive as computing the gradient for f(x) and solving an LP over P is inexpensive relative to solving an LP over P C. The μ parameter can be driven down to 0 after a solution converges in warm-starting procedure similar to interior-point methods, ensuring convergence to the true optimum.
An additional advantage of this transformation of the problem is the solution structure. Running Frank-Wolfe on the set P n C could potentially select large number of extremal points from Bd(C)) if C is non polyyheell.... In contrast, P has a finite number of vertices, small subset of which will be selected throughout the optimization procedure. The same solution as that of the original problem can thus be constructed as a convex combination of small number of vertices of P, improving sparsity and interpretabilitt in many applications.
The following definition formalizes the setting of Problem (1.1).
Definition 1.3 (Generalized self-concordant function). Let f E C (dom(f)) be closed convex function with dom( f) R" open. Then is (M, v) generalized self-concordant if:
( f(x) [w]u, u) s M [|ul|/2
[|wll>>>0x) ||
for any x e dom(f) and u, w e RR," where D3 f(x)[w] lim a f(++ - f(x)). a-0
Frank-Wolfe Convergence Guarantees
We establish convergence rates for Frank-Wolfe variant with an open-loop step size strategy on generalized self-concordant functions. The Monotonous Frank-Wolfe (M-FW) algorithm presented in Algorithm is a simple, but powerful modification of the standard Frank-Wolfe algorithm, with the only difference that before taking step, we verify if x, y, x,) dom(f), and if so, we check whether moving to the next iterate provides primal progress. Note, that the open-loop step size rule 2/(1 + 2) does not guarantee monotonous primal
4

---

progress for the vanilla Frank-Wolfe algorithm in general. If either of these two checks fails, we do not move: the algorithm sets X,+1 x, in Line of Algorithm 1.
As customary, we assume short-circuit evaluation of the logical conditions in Algorithm 1, i.e., if the first condition in Line is true, then the second condition is not even checked, and the algorithm directly goes Line 6. This minor mod- ification of the vanilla Frank-Wolft algo- rithm enables us use the monotonic- ity of the iterates in the proofs to come, the expense of at most one extra func- tion evaluation per iteration. Note that if we set X,+1 = x,, we do not need to call the FOO or LMO oracle at iteration + 1, as we can simply reuse (x,(x,) and v, This effectively means that between successive iterations in which we search for an acceptable value of y,, we only need to call the zeroth-order and domain oracle.
Algorithm 1 Monotonous Wolnk-Wolfe (M-FW)
Input: Point X X dom(f) f), function f Output: Iterates XI.... E X
1: for r = 0 to do
2:
V, - veg (Vf(x))
3:
Y/ - 2/(1+2) 2)
4:
Xr41 + x, Yr (V, -X,) x,)
5: x,+1 & dfm(f) or f(X(+1) f(x,) then
6: X,+1 xx X
Remark 2.1. In practice, one can search for a suitable step size logarithmically, that is, halving the value of y, if either X,,1 & dom(f) f(x,1)) f(x)). This would lead to step size that is at most a factor of 2 smaller than the non-zero step size that would have been eventually accepted by the Monotonous Frank-Wolfe (M-FW) algorithm in Algorithm 1. Moreover, this strategy would allow us to obtain convergence rates that are very similar to those of the Monotonous Frank-Wolfe (M-FW) algorithm, with the exception of factor of The motivation and implications of this variant are detailed in Appendix A. For simplicity, we focus on the step size presented in Algorithm in the main body of the paper.
In order to establish the main convergence results for the algorithm, we lower bound the progress per iteration with the help of Proposition 2.2. Proposition 2.2. (C.f., (Sun & Tran-Dinh, 2019, Proposition 10)) Given a (M, generalized self-concordant function, then for v 2 2, we have that:
f(y) f(x) fx).) x) s wr(d(( y)) lly x00
(2.1)
where the inequality holds if and only if d,, y) 1 for <> 2, and we have that,
M lly x||
if v if v 2,
yx def
\/21 - 1)M lly x||3 3-v 1ly xI1 x11
where:
e ---
if 2 if v 3
bn(-r)
(T(T) def
(1-7)ln(1 (T-r)
if v 4 otherwise.
y-2
2-2 2(3
2(- (1-
2-v -1)-
The inequality shown in Equation (2.1) is very similar to the one that we would obtain if the gradient of f were Lipschitz continuous, however, while the Lipschitz continuity of the gradient leads to an inequality that holds globally for all x, E dom(f), the inequality in Equation (2.1) only holds for dx,(x.y) y) 1. Moreover, there are two other important differences, the norm used in Equation (2.1) is now the norm defined by the Hessian at x,
instead of the le norm, and the term multiplying the norm is w, (x. y)) instead of 1/2. We deal with the latter issue by bounding (d, y)) with a constant that depends on v for any x, E dom(f) such that d, (x. y) $ 1/2, as shown in Remark 2.3.
Remark 2.3. As (r)(d) 0 for
and 2 2, then (T( S (1/2) for s 1/2.
Due to the fact that we use a simple step size y, = 2/(1 + 2), that we make monotonous progress, and we ensure that the iterates are inside dom()), careful accounting allows us to bound the number of iterations until (x, X, + 7, xx)) z 1/2. Before formalizing the convergence rate we first review lemma that we will need in the proof.

---

Lemma 2.4. (C.f, (Sun & Tran-Dinh, 2019, Proposition 7)) Let f be a generalized self- concordant function with v 2. dx(x, y) < 1 and E dom( f) then y E dom(f). For the case = 2 we have that dom( RR
Putting all these things together allows us obtain convergence rate for Algorithm 1. Theorem 2.5. Suppose X is compact convex and is a (M, v) generalized self-concordant function with v 2 2. Then the Monotonous Frank-Wolfe algorithm (Algorithm 1) satisfies:
4(T, +
h(x)
max L.
(2.2)
1+1
for Tv, where 7
||d|| F2 /lldl12 and Ty is defined as:
max ue Lo.
[4MD] - T, def
v
L / 2) otherwise.
(2.3)
Otherwise it holds that hxx, h(xo) for TTy
Proof. Consider the compact set Lo (x dom( nX f(x) & f(x))) As the algorithm
makes monotonous progress and moves towards points such that x, X, then x, Lo for s 2 0. As the smoothness parameter of f is bounded over Lo, we have from the properties of smooth functions that the bound ||d]| ((x,)) /||d]] f holds for any d E R". Particularizing
$ D. We then define T, as in Equation (2.3). Note that for 2 T, we have that d(x, X, + (v, -x)) & 1/2, and so as E dfm(f) we will have + + (v, x,) ffm by application of Lemma 2.4. This means that the non-zero step size y; will ensure that x, + (V, x,) dom(f) in Line of Algorithm 1. Moreover, it allows us to use the bound between points and x, + (v, -x,) in Proposition 2.2, which holds for d(x,, X, + 7r (v, - x,))
for d = x,
and noting that ||x, - v, s D leads to ||x, - v,ll
With this we can estimate the primal progress we can guarantee for 2 T, if we move from x, to Y (V, x,):
h(x, + y (v, x,)) - h(x,) (x)(x) w, (d, (X,, + y (v, x,)) |[v, x, f(x))
s h(x, (1-y)) ,
La Dz (1/2),
where the second inequality follows from the upper bound on the primal gap via the Frank-Wolfe gap g (x,,, the application of Remark 2.3 as for t T, we have that dx, X Yr (V,-x,, xx)) s 1/2, and from the fact that x, E Lo for all r 2 O. With the previous chain of inequalities we can bound the primal progress for 2 Ty
h(x,) - n(x + Yr (V, - -x))) 2 (xx) - Y D² (1/2).
(2.4)
From these facts we can prove the convergence rate shown in Equation (2.2) by induction. The base case t = T, holds trivially by the fact that using monotonicity we have that h(xT,) S (xx)). Assuming the claim is true for some 2 T, we distinguish two cases.
Case hx,) - y 7 D222 O: Focusing on the first case, we can plug the previous inequality into Equation (2.4) to find that yr guarantees primal progress, that is, h(x,) > h(x, + yr (v, x,)) with the step size yr, and so know that we will not go into Line of Algorithm 1, and we have that h(X(+1) = h(x; + y, (v, x))). Thus using the induction hypothesis and plugging in the expression for y, 2/(1 + 2) into Equation (2.4) have:
h(x,+1) max (1ax)
Lo Do
(T,
1
(1+1)(r+2)
(1 2)2
4(T,+ max ((xx),, 1, Lo (,/2)
2
where we use that (T, + 1)1/(1 1) +)+ +1 for all / 0 and any / 2 T,. Case hx, y; D2 (1/2) 0: In this case, cannot guarantee that the step size y, provides primal progress by plugging into Equation (2.4), and so we cannot guarantee if step size of y, will be accepted and we will have X,+1 X, + Yr (v, x,), or we will simply

---

have X,+1 x,, that is, we may go into Line 6 of Algorithm 1. Nevertheless, if we reorganize the expression )x,) -v, (1/2( 0, by monotonicity we will have that:
h(x,+1) s h(x)
fo w,, D 1+2
2
1) max
1+2
Where the last inequality holds as 2 s 4(T, + 1) for any T, 2 0.
Remark 2.6. In the case where 2 we can easily bound the primal gap h(x1), as in this setting ff = R", which leads to h((x)) s L D2 from Equation (2.4), regardless of we
set Xo or Vo. Moreover, as the upper bound on the Bregman divergence holds for = 2 regardless of the value of d2(x. (x.)), y), we can modify the proof of Theorem 2.5 to obtain a convergence rate of the form h(x) 2/(1+ 1 D2 for 1, which is reminiscient of the O /r) rate of the original Frank-Wolfe algorithm for the smooth and convex case.
Note that in the proof of Theorem 2.5 we explicitly use the progress bound from generalized self-concordance opposed to the progress bound that arises from 1.,0 -soosthnssss,, as there no straightforward way to bound the number of iterations until the latter progress bound holds indefinitely for all x, + (, x,), while there is straightforward criterion on y, that allows us to ensure that the former holds from some point onward (see Remark A. in the Appendix for more details). Furthermore, with this simple step size we can also prove convergence rate for the Frank-Wolfe gap, as shown in Theorem 2.7 (see Theorem A.2 in the Appendix for the proof).
Theorem 2.7. Suppose X is a compact convex set and f is a (M, v) generalized self- function with v 2. Then if the Monotonous Soank-Wolfe algorithm (Algorithm 1) is run for T 2 T + 6 iterations, we will have that minisrst g 8(x,) s 0(177).
Remark 2.8. Note that the Monotonous Frank-Wolfe algorithm (Algorithm 1) performs at most one ZOO, FOO, DO, and LMO oracle call per iteration. This means that Theorems 2.5 and 2.7 effectively bound the number of ZOO, FOO, DO, and LMO oracle calls needed to achieve a target primal gap or Frank-Wolfe gap accuracy & as a function of T, and E; note that T, is independent of e. This is an important difference with respect to existing bounds, as the existing Frank-Wolfe-see in the literature that utilize various types of line searches may perform more than one ZOO or DO call per iteration in the line search. This means that the convergence bounds in terms of iteration count of these algorithms are only informative when considering the number of FOO and LMO calls that are needed to reach target accuracy in primal gap, and do not directly provide any information regarding the number of ZOO or DO calls that are needed. In order to bound the latter two quantities one typically needs additional technical tools. For example, for the backtracking line search of Pedregosa et al. (2020), one can use Theorem 1 in Appendix C of Pedregosa et al. (2020), or a slightly modified version of Lemma 4 in Nesterov (2013), to find a bound for the number of ZOO or DO calls that are needed to find an 6-optimal solution. Note that these bounds depend on defrede initialization or tuning parameters provided by the user.
first-order algorithms for generalized self-concordant functions
In Table 2 we provide detailed complexity comparison between the Monotonous Frank-
Wolfe (M-FW) algorithm (Algorithm 1), and other comparable algorithms in the literature.
Algorithm
SOO calls
FOO calls
ZOO calls
LMO calls
DO calls
FW-GSC [1, Alg.2]
0(1/s)
0(1/s)
(116s)
LBTFW-GSC [1, Alg.3]
0(1/8)
0(1/8)
O(1/8)
0(1/8)
MBTFW-GSC' [1, Alg.5]
0(1/e)
((1/e)
0(1/e)
O(1/8)
0(1/e)
M-FW# [This work]
0(1/s)
0(1/a)
0(1/s)
0(1/s)
Table 2: Complexity comparison: Number of iterations needed to reach a solution with
h(x) below for Problem 1.1. We denote Dvurechensky et al. (2020b) using [1]. We use the superscript it to indicate that the same complexities hold for reaching an e-optimal solution in g 8(x). The superscript is used to indicate that constants in the convergence bounds depend on user-defined inputs; the other algorithms are parameter-fres
7

---

We note that the LBTFW-GSC algorithm from Dvurechensky et al. (2020b) is in essence the Frank-Wolfe algorithm with a modified version of the backtracking line search of Pedregosa et al. (2020). In the next section, we provide improved convergence guarantees for various cases of interest for this algorithm, which we refer to as the Frank-Wolfe algorithm with Backtrack (B-FW) for simplicity.
2.1 Improved convergence guarantees
We will now establish improved con- vergence rates for various special cases. We first focus on the assumption that x E Int (X n dom(f)), obtain- ing improved rates when we use the FW algorithm coupled with the adap- tive step size strategy from Pedregosa al. (2020) (see Algorithm 6 in Ap- pendix). This assumption is reasonable if for example Bd( & d/m(/), and Int (X) s dom( That is to say, we will have that x" Int (X dom( if for example we use logarithmic barrier functions to encode a set of constraint, and we have that dom(f) is proper subset of X. In this case the optimum is guaranteed to be in Int (X n ddoms)):
Algorithm 2 Frank-Wolfe with Backtrack of Pe- dregosa et al. (2020) (B-FW)
Input: Xo X n dom(), function f, estimate I.-1 Output: Iterates X1....
1: for = to do
2:
V, < argmin (Vf(x;).))
3: Yr, L, + Backtrack f. X,, V, - X, 1)
4:
X,41
(V, x,)
The analysis in this case is reminiscent of the one in the seminal work of Guélat & Marcotte (1986), and presented in Appendix A.2. Note that we can upper bound the value of L, for 2 0 by m L-1), where > 1 is the backtracking parameter and L-1 is the initial smoothness estimate in Algorithm 6.
Theorem 2.9. Let f be a (M.v) generalized self-concordant function with v 2 2 and let dom(f) f) not contain straight lines. Furthermore, denote by O the largest value such that B(x",)) .)) s X dom Then the Frank Wolfe algorithm with Backtrack (Algorithm 2) achieves a convergence rate for 2 1 of h(x,) h(xo) (1 / (22)((/D))
The assumption that dom(f) does not contain straight lines in Theorem 2.9 is related to the Hessian being positive definite over (f) (see the proof in the Appendix in Theorem A.5). Note that this is very mild assumption as we can simply modify the function with very small le regularizer, as e.g,, in Nesterov (2012). Next, we recall the definition of uniformly convex sets, used in Kerdreux al. (2021), which will allow us obtain improved convergence rates for the FW algorithm over uniformly convex feasible regions.
Definition 2.10 ((K, -unuffrrmlyy convex set). Given two positive numbers and 4, say the set X ç R² is (k, 9o -)unifformly convex with respect to norm ||-I| if for any x, E X, Y <
and R with ||z||
have that y y(x y) y(1 7) ||x yl1 X.
Theorem 2.11. Suppose X a compact (k, q)-uniformly convex set and f is a (M, v) generalized self-concordant function with v 2. Furthermore, assume that minxe [[V C > 0. Then the Frank-Wolfe algorithm with Backtrack (Algorithm 2) achieves a convergence rate of:
hxx)) (1 min (1, =fl)
ifq=
h
h(xg)
if > 2, $1510 to if 2, > to.
21
(1+(g- (00))) = 0 (1-9/(9-2)
for / 1, where to = m1, ((x33
However, in the general case, we cannot assume that the norm of the gradient is bounded away from zero over X. We deal with the general case in Theorem 2.12
Theorem 2.12. Suppose a compact (k, -)-unfformly convex set and f is (M, v) generalized self-concordant function with 2 for which the domain does not contain straight lines. Then

---

the Frank-Wolfe algorithm with Backtrack (Algorithm 2) results in convergence rate:
h(xa)
if 1 to
h S
(L* (LM/0x2 1))
(L40-D)00000//22)))000 0 (1-9/(0-1)
ift> to.
for 1, where to max(1, (10
In Table in Appendix A.2 we summarize the oracle complexity results shown in this paper for the B-FW algorithm when minimizing over a (k, q)-unfoormly convex set. Note that this algorithm is referred to as LBTFW-GSC in Dvurechensky et al. (2020b).
Remark 2.13. Contrary to previous claims, there is no obstacle for the Away-step Frank-Wolfe (AFW) algorithm (Guélat & Marcotte, 1986; Lacoste-Julien & Jaggi, 2015) together with the step size strategy in Algorithm 6 to obtain a linear convergence rate in primal and Frank-Wolfe gap when is a polytope and f generalized celf-concordant. This not surprising, as f is strongly convex and smooth over Lo if ffm(f) does not contain straight lines, and monotonicity ensures the feasibility of the iterates. We leave the analysis for this case to Appendix B, and the formal convergence statement to Theorem B.2 and B.3.
In Table 4 in Appendix B we provide a complexity comparison between the B-AFW algorithm, which can be found in Algorithm 7 in the appendix, and other comparable algorithms in the literature. Note that these complexities assume that X is polyhedral.
3 Computational experiments
We showcase the performance of the M-FW algorithm, the second-order step size and the LLO0 algorithm from Dvurechensky et al. (2020b) (denoted by GSC-FW and LLO0 in the figures) and the Frank-Wolfe and the Away-Step Frank-Wolfe algorithm with the backtracking stepsize of Pedregosa et al. (2020), denoted by B-FW and B-AFW respectively. All experiments are carried out Julia using the FrankWolfe. j1 package (Besançon et al., 2021), and the examples considered extend the ones presented in Dvurechensky et al. (2020b) and Liu repository.
et al. (2020). The code can be found in the fw- fi-generalizen weleeeddsslffooorraaaree We also use the vanilla FW algorithm denoted by FR, which is simply Algorithm without Lines and 6 using the traditional y, 2/(1 + 2) open-loop step size rule. Note that there are no formal convergence guarantees for this algorithm when applied to Problem (1.1). Details and remarks on the data and the experimental setup are provided in Appendix C. All figures show the evolution of the hxx,) and g(x,) against and time with a log-log scale. As in Dvurechensky et al. (2020b) we implemented the LLOO based variant only for the portfolio optimization instance A for the other examples, the oracle implementation was not implemented due to the need to estimate non-trivial parameters.
As can be seen in all experiments, the Monotonous Frank-Wolft algorithm is very competitive, outperforming previously proposed variants in both in progress per iteration and time. The only other algorithm that is sometimes faster is the Away-Step Frank-Wolfe variant as detailed in Remark 2.13, which however depends on an active set, and can induce up to quadratic overhead, making iterations progressively more expensive; this can also be observed in our experiments as the advantage in time is much less pronounced than in iterations.
Portfolio optimization. We consider f(x) Σp log( x)), where p denotes the number of periods and X = A,,- The results are shown in Figure 2.
Signal recovery with KL divergence. We apply the aforementioned algorithms to the recovery of a sparse signal from a noisy linear image using the Kullback-Leebllr divergence,
(w,, x) y where w; is the th row of matrix W. In order to promote sparsity and enforce nonnegativity of the solution, we use the unit simplex of radius R as the feasible set X = (x e R. xx/11 s R). The results are shown in Figure 3. We used the same M 1 choice for the second-order method as in Dvurechensky et al. (2020b) for comparison; its admissibility is unknown (see Remark C.1).
expressed as fx) = (Wx, MN (w,, x) log
(w..)

---

Logistic regression. We consider a logistic regression task with design matrix with rows a, E R" with with elastic net regularization, in a similar fashion as is done in Liu er al. (2020), with f(x) 1/N Σ log(1 + exp(-y; (x, a;))) 2 ||x| where μ is a regularization parameter and X is the & ball of radius p. The results can be seen in Figure and Appendix C.
N and vector y E {-1. 1) and formulate the problem
Birkhoff polytope. All previously considered applications have in common feasible region possessing computationally inexpensive LMOs (probability/unit simplex and norm ball). Additionally, each vertex returned from the LMO is highly sparse with at most one non-zero element. To complement the results, we consider convex quadratic optimization problem over the Birkhoff polytope, where the LMO call uses the Hungarian method and is not as inexpensive as in the other examples. The results are shown in Figure
10'
10-2
10"1
10-5
10--
FM
n-F2
10-13
10"
D-AFU
10000
10 10'
10 10 10'
10
10
Iteration
Time [s]
Iterstion
Time [s]
Figure Portfolio Optimization: LLO0 and GSC-FW perform similarly FW on per-iteration basis but the iterations are computationally more expensive. B-AFW is the fastest method both in terms iteration and runtime, followed by M-FW which is the only other method to terminate with the specified dual gap tolerance.
POOOOO
16F
10-3
n-4r%
G2D-PV
107
100
10P
10
10
10P
107
101
10
107
1011
10
1P
Derraii
Time [+]
Ducration
Time [s]
Figure 3: Signal Recovery: B-AFW significantly outperforms all other methods. FW and B-FW perform similarly in dual gap progress and converge slower than M-FW. In terms of primal gap progress, M-FW and FW perform similarly and outperform B-FW.
I0
10-2
B-ew B-APM
10-5
10-1
10-11
10-4
10
10
101
10
107
102
10"
10
10
10
Teeratio
Time [s]
Renuion
Time [s]
Figure 4: Logistic Regression: This instance shows that although simple in essence, M-FW can outperform other methods including B-AFW in terms of convergence. The primal and dual gaps for B-FW and GSC-FW converge at similar rates against iteration count.
1ff
10"2
10=2
x
10-11
10
10P
10P
10P
10
10
107
10a Tensinn
10"
10"1
10'
Jeraiio
Time [-]
Time [s]
Figure 5: Birkhoff Polytope: B-AFW the cestest-oonverging method for measures. However, the dual gap reaches a plateau due to numerical issues above the termination threshold, unlike M-FW which reaches the dual gap tolerance. GSC-FW is run for 1000 iterations only given the longer runtime. Its slow progress is likely due to numerical instabilities in the Hessian computation which do not occur in first-order methods.
10

---

Acknowledgements
Research reported this paper was partially supported through the Research Campus Modal funded by the German Federal Ministry of Education and Research (fund numbers and the Deutsche Forschunggemeinschatt (DFG) through the DFG Cluster of Excellence MATH+ We would like to thank the anonymous reviewers for their suggestions and comments.
References
Bach, F. Self-concordant analysis for logistic regression. Electronic Journal of Statistics, 4: 384-414, 2010.
Besançon, M., Carderera, A., and Pokutta, S. FrankWolfe.jl: a high- Seigh-pefformacce and flexible toolbox for Frank-Wolfe algorithms and conditional gradients. arXiv preprint vrXiv:210400667. 2021.
Carderera, A., Besançon, M., and Pokutta, S. Frank-Wolfe for Generalized Self-Concordant Functions Problem Instances, May 2021. URL https://doot http:///.ooooo//....0 httpg//1..281//eeeeee 4836009.
Csiszar, Why least squares and maximum entropy? axiomatic approach inference for linear inverse problems. The annals of statistics, 19(4):2032-2000 -266, 1991.
Diakonikolas, J., Carderera, A., and Pokutta, S. Locally accelerated conditional gradients. In Proceedings of the 23th International Conference on Artificial Intelligence and Statistics, pp. 1737-1747. PMLR, 2020.
Dvurechensky, P., Ostroukhov, P., Safin, K., Shtern, S., and Staudigl, M. Self-concordant analysis of Frank-Wolfe algorithms. In Proceedings of the 37th International Conference Machine Learning, pp. 2814-2824. PMLR, 2020a
Dvurechensky, P., Safin, K., Shtern, S., and Staudigl, M. Generalized self-concordant analysis of Frank-Wolfe algorithms. arXiv preprint arXiv:2010.01009 2020b.
Frank, M. and Wolfe, P. An algorithm for quadratic programming. Naval research logistics quarterly, 3(1-2):95-110, 1956.
Garber, D. and Hazan, E. A linearly convergent variant the conditional gradient algorithm under strong convexity, with applications to online and stochastic optimization. SIAM Journal on Optimization, 26(3):1493-1522 2016.
Guélat, J. and Marcotte, P. Some comments on Wolfe's 'away step'. Mathematical Program- ming, 35(1):110-119, 1986.
Jaggi, M. Revisiting Wolfe: Projection-free sparse convex optimization. Proceedings of the 30th International Conference Machine Learning, pp. 427-435. PMLR, 2013.
Kerdreux, T., d'Aspremont, A., and Pokutta, Restarting Frlnk-Wolfe. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, pp. 1275-1283. PMLR, 2019.
Kerdreux, T., d'Aspremont, A., and Pokutta, S. Projection-free optimization on uniformly convex sets. In Proceedings of the 24th International Conference Artificial Intelligence and Statistics, pp. 19-27. PMLR, 2021.
Krishnan, R. G., Lacoste-Julien, S., and Sontag, D. Barrier Frank-Wolfe for Marginal Inference. In Proceedings of the 28th Conference Neural Information Processing Systems. PMLR, 2015.
Lacoste-Julien, S. and Jaggi, M. On the global linear convergence of Frank-Wolfe optimization variants. Proceedings of the 29th Conference on Neural Information Processing Systems, pp. 566-575. PMLR, 2015.
11

---

Levitin, E. S. and Polyak, B. T. Constrained minimization methods. USSR Computational Mathematics and Mathematical Physics, 6(5):1-50, 1966.
Liu, D., Cevher, V., and Tran-Dinh, Q. A Newton Frank-Wolfe method for constrained self-concordant minimization. arXiv preprint arXiv:2002.07003, 2020.
Marron, J. S., Todd, M. J., and Ahn, J. Distance-weiighred discrimination. Journal of the American Statistical Association, 102(480):226-1127,, 2007.
Marteau-Perey, U., Ostrovskii, D., Bach, F., and Rudi, A. Beyond least-squares: Fast rates for regularized empirical risk minimization through self-concordance. In Proceedings of the 32nd Conference on Learning Theory, pp. 2294-2340. PMLR, 2019.
Nesterov, Y. How to make the gradients small. Optima. Mathematical Optimization Society Newsletter, (88):10-11, 2012.
Nesterov, Gradient methods for minimizing composite functions. Mathematical Program- ming, 140(1):125-111, 2013.
Nesterov, Y. Lectures convex optimization, volume 137. Springer, 2018.
Nesterov, Y. and Nemirovskii, A. Interior-point polynomial algorithms in convex programming. SIAM, 1994.
Odor, G., Li, Y.-H., Yurtsever, A., Hsieh, Y.-P., Tran-Dinh, Q., El Halabi, M., and Cevher, V. Frank-wolfe works for non-lipschitz continuous gradient objectives: scalable poisson phase retrieval. In 2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 6230-6233 leee, 2016.
Ostrovskii, M. and Bach, F. Finite-sample analysis M-estimators using celf-concordance. Electronic Journal of Statistics, 15(1):326-391. 2021.
Pedregosa, F., Negiar, G., Askari, A., and Jaggi, M. Linearly convergent Frank-Wolfe with backtracking line-search. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics. PMLR, 2020.
Sun, T. and Tran-Dinh, Q. Generalized self-concordant functions: recipe for Newton-type methods. Mathematical Programming, 178(1):145-213, 2019.
Temlyakov, V. Greedy approximation in convex optimization. Constructive Approximation, 41 (2):269-296, 2015.
Tran-Dinh, Q., Li, Y.HH., and Cevher, V. Composite convex minimization involving self- concordant-like cost functions. In Modelling, Computation and Optimization in Information Systems and Management Sciences, pp. 155-168. Springer, 2015.
Wolfe, P. Convergence theory in nonlinear programming. In Integer and Nonlinear Program- ming, pp. 1-36. North-Hollan Amsterdam, 1970.
Zhao, R. and Freund, R. M. Analysis of the Trank-Wolf, method for logarithmically- homogeneous barriers, with an extension. arXiv preprint arXiv:2010.08999, 2020.
12


Reviews:
[{"review_id": "_7JiYZMB0qz", "reviewer": "Reviewer_62NX", "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. ", "questions": "", "limitations": "", "rating": 6, "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": "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.\n\nQ1. What are the choices of parameters (e.g., for line search) in different experiments? Is it possible to fine tune them?\n\nQ2. 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.\n\nQ3. 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.\n\n========\nI have read the rebuttal and updated my score accordingly. I do think that more discussions on comparison with line search should be added.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is mainly a theoretical work that helps to understand FW for generalized self-concordant functions.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "QM0Jqx6vpnF", "reviewer": "Reviewer_JRkk", "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. ", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "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 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). \n\nThe 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. \n\nI have checked the proof in Section 2. I do not check the proofs in the supplementary material. \n\nOther comments: \n- 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. \n- 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\"? \n- 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. \n- I don't get Line 202--205, though the conclusion is obviously correct. \n- Line 241: What does \"a reasonable assumption\" refer to? Perhaps there are missing words. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "OPXOH8NSZCw", "reviewer": "Reviewer_MQCq", "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\n1. the universal classical choice of the parameter: $\\gamma_t = 2 / (2 + t)$\n2. a check for monotonicity\n3. a check for domain feasibility\n\nFor 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.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "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).\n\nIn 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.\n\nHowever, I have one major question related to the main result of the paper. For the classical FW algorithm, the known convergence rate is:\n$f(x_t) - f^* <= LD^2 / t$ \n(up to constant factors), where L is the Lipschitz constant for the gradient and D is the diameter of the set. \nIt looks that the result of Theorem 2.4 provides a bound which is not significantly better than this one. \nInstead 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}$).\nIt 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.\nMaybe, 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).\n\nMinor remarks:\n\n1. It must be wrong 'et al' in the references: (Bach et al., 2010) and (Nesterov et al., 2018) \n\n2. 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.\n\n3. 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.\n\n4. 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).\n\n5. Line 193: The dot is probably missing after 'the primal progress'.\n\n6. 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "-", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "CYNM1SgoWs_", "reviewer": "Reviewer_pJc9", "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.", "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": "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.\n\nQuality:  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.\n\nClarity:  the paper is very well-written and complete.\n\nSignificance:  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.\n\nMinor Comments:\n\n1.) The font appears to be non-standard?\n2.) Should Theorems 2.9 and 2.10 say \"uniformly convex set\" instead of \"strongly convex set\"?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes/NA", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}]

Author rebuttal:

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)