Simple steps are all you need: Frank-Wolfe and generalized self-concordant functions
Year: 2021

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 γt = 2/(t + 2), obtaining a 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.

heading: 1 Introduction
text: Constrained convex optimization is the cornerstone of many machine learning problems. We consider such problems, formulated as:
min x∈X
𝑓 (x), (1.1)
where 𝑓 : ℝ𝑛 → ℝ ∪ {+∞} is a generalized self-concordant function and X ⊆ ℝ𝑛 is a 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 of their convergence often relies on the assumption that the gradient is Lipschitzcontinuous. This assumption does not necessarily hold for generalized self-concordant functions, an important class of functions for which the growth can be unbounded.

heading: 1.1 Related work
text: In the classical analysis of Newton’s method, when the Hessian of 𝑓 is assumed to be Lipschitz continuous and the function is strongly convex, one arrives at a convergence rate for the algorithm that depends on the Euclidean structure of ℝ𝑛, despite the fact that the algorithm is 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-invariant convergence rate for the aforementioned algorithm. More importantly, many of the barrier functions used in interior-point methods are self-concordant, which extended the use of polynomial-time interior-point methods to many settings of interest.
∗Georgia Institute of Technology. E-mail: alejandro.carderera@gatech.edu †Zuse Institute Berlin. E-mail: besancon@zib.de ‡Zuse Institute Berlin and Technische Universität Berlin. E-mail: pokutta@math.tu-berlin.de
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-Ferey 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-like properties without satisfying the strict definition of self-concordance. For example, the logistic loss function used in logistic regression is not strictly self-concordant, but it fits into a class of pseudo-self-concordant functions, which allows one to obtain similar 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-concordant functions were established. This was fully formalized in Sun & Tran-Dinh (2019), in which the concept of generalized self-concordant functions was introduced, along with key bounds, properties, and variants of Newton methods for the unconstrained setting which make use of this property.
Most algorithms that aim to solve Problem (1.1) assume access to second-order information, as this often allows the algorithms to make monotonous progress, remain inside the domain of 𝑓 , and often, converge quadratically when close enough to the optimum. Recently, several lines of work have focused on using Frank-Wolfe algorithm variants to solve these types of problems in the projection-free setting, for example constructing second-order approximations to a self-concordant 𝑓 using first and second-order information, and minimizing these approximations over X using the Frank-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-concordant 𝑓 , 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 𝑓 , 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 𝑓 , 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 FrankWolfe 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 involving generalized self-concordant 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 in Odor et al. (2016), where the Frank-Wolfe algorithm is shown to converge on a self-concordant non-Lipschitz smooth objective.

heading: 1.2 Contribution
text: The contributions of this paper are detailed below and summarized in Table 1.
Simple FW for generalized self-concordant functions. We show that a small variation of the original Frank-Wolfe algorithm (Frank & Wolfe, 1956) with an open-loop step size of the form 𝛾𝑡 = 2/(𝑡+2), where 𝑡 is the iteration count is all that is needed to achieve a convergence rate of O(1/𝑡) 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 𝑓 . 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 𝑓 (x). 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).
Moreover, our variant relying on the open-loop step size 𝛾𝑡 = 2/(𝑡 +2) allows us to establish a O(1/𝑡) convergence rate for the Frank-Wolfe gap, is agnostic, i.e., does not need to estimate local smoothness parameters, and is parameter-free, leading to convergence rates and oracle complexities that are independent of any tuning parameters.
Faster rates in common special cases. We also obtain improved convergence rates when the optimum is contained in the interior of X ∩ dom( 𝑓 ), or 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 to depend also on the ambient dimension of the polytope; this applies to our linear rates and those in Table 1 established elsewhere (see Diakonikolas et al. (2020)). In contrast the O(1/𝜀) rates are dimension-independent.
Numerical experiments. We provide numerical experiments that showcase the performance of the algorithms on generalized self-concordant objectives to complement the theoretical 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 an analysis of the Away-Step Frank-Wolfe algorithm which is complementary to ours (considering a slightly different setup and regimes) and was conducted independently; we have updated the tables to include these additional results.

heading: 1.3 Preliminaries and Notation
text: We denote the domain of 𝑓 as dom( 𝑓 ) def= {x ∈ ℝ𝑛, 𝑓 (x) < +∞} and the (potentially nonunique) minimizer of Problem (1.1) by x∗. Moreover, we denote the primal gap and the Frank-Wolfe gap at x ∈ X ∩dom( 𝑓 ) as ℎ(x) def= 𝑓 (x) − 𝑓 (x∗) and 𝑔(x) def= maxv∈X ⟨∇ 𝑓 (x), x − v⟩, respectively. We use ∥·∥, ∥·∥𝐻 , and ⟨·, ·⟩ to denote the Euclidean norm, the matrix norm induced by a symmetric positive definite matrix 𝐻 ∈ ℝ𝑛×𝑛, and the Euclidean inner product, respectively. We denote the diameter of X as 𝐷 def= maxx,y∈X ∥x − y∥. Given a non-empty set X ⊂ ℝ𝑛 we refer to its boundary as Bd(X) and to its interior as Int (X). We use Δ𝑛 to denote the probability simplex of dimension 𝑛. Given a compact convex set C ⊆ dom( 𝑓 ) we denote 𝐿C 𝑓 = max
u∈C,d∈ℝ𝑛 ∥d∥2∇2 𝑓 (u) /∥d∥22 and 𝜇C𝑓 = minu∈C,d∈ℝ𝑛 ∥d∥ 2 ∇2 𝑓 (u) /∥d∥22. We assume access to:
1. Domain Oracle (DO): Given x ∈ X, return true if x ∈ dom( 𝑓 ), false otherwise. 2. Zeroth-Order Oracle (ZOO): Given x ∈ dom( 𝑓 ), return 𝑓 (x). 3. First-Order Oracle (FOO): Given x ∈ dom( 𝑓 ), return ∇ 𝑓 (x). 4. Linear Minimization Oracle (LMO): Given d ∈ ℝ𝑛, return argminx∈X ⟨x,d⟩.
The FOO and LMO oracles are standard in the FW literature. The ZOO oracle is often implicitly assumed to 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. It is reasonable to assume the availability of the DO oracle: following the definition of the function codomain, one could simply evaluate 𝑓 at x and assert 𝑓 (x) < +∞, thereby combining the DO and ZOO oracles into one oracle. However, in many cases testing the membership of x ∈ dom( 𝑓 ) is computationally less demanding than the function evaluation.
Remark 1.1. Requiring access to a 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 6 in the Appendix. The remaining two variants ensure that x ∈ dom( 𝑓 ) by using second-order information about 𝑓 , which we explicitly do not rely on. The following example motivates the use of Frank-Wolfe algorithms in the context of generalized 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 ∩ C, P is a polytope over which we can minimize a linear function efficiently, and C is a convex compact set for which one can easily build a barrier function.
Solving a linear optimization problem over X may be extremely expensive. In light of this, we can incorporate C into the problem through the use of a barrier penalty in the objective function, minimizing instead 𝑓 (x) + 𝜇ΦC (x) where ΦC (x) is a log-barrier function for C and 𝜇 is a parameter controlling the penalization. This reformulation is illustrated in Figure 1. Note that if the original objective function is generalized self-concordant, so is the new objective function (see Proposition 1 in Sun & Tran-Dinh (2019)). We assume that computing the gradient of 𝑓 (x) + 𝜇ΦC (x) is roughly as expensive as computing the gradient for 𝑓 (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 a 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 ∩ C could potentially select a large number of extremal points from Bd(C) if C is non-polyhedral. In contrast, P has a finite number of vertices, a 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 a small number of vertices of P, improving sparsity and interpretability in many applications. The following definition formalizes the setting of Problem (1.1). Definition 1.3 (Generalized self-concordant function). Let 𝑓 ∈ 𝐶3 (dom( 𝑓 )) be a closed convex function with dom( 𝑓 ) ⊆ ℝ𝑛 open. Then 𝑓 is (𝑀, 𝜈) generalized self-concordant if:
| 〈D3 𝑓 (x) [w]u,u〉 | ≤ 𝑀 ∥u∥2∇2 𝑓 (x) ∥w∥𝜈−2∇2 𝑓 (x) ∥w∥3−𝜈2 , for any x ∈ dom( 𝑓 ) and u,w ∈ ℝ𝑛, where D3 𝑓 (x) [w] = lim
𝛼→0 𝛼−1 (∇2 𝑓 (x + 𝛼w) − ∇2 𝑓 (x)).

heading: 2 Frank-Wolfe Convergence Guarantees
text: We establish convergence rates for a 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 1 is a simple, but powerful modification of the standard Frank-Wolfe algorithm, with the only difference that before taking a step, we verify if x𝑡 + 𝛾𝑡 (v𝑡 − x𝑡 ) ∈ dom( 𝑓 ), and if so, we check whether moving to the next iterate provides primal progress. Note, that the open-loop step size rule 2/(𝑡 + 2) does not guarantee monotonous primal
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 6 of Algorithm 1.
Algorithm 1 Monotonous Frank-Wolfe (M-FW)
Input: Point x0 ∈ X ∩ dom( 𝑓 ), function 𝑓 Output: Iterates x1, . . . ∈ X 1: for 𝑡 = 0 to . . . do 2: v𝑡 ← argminv∈X ⟨∇ 𝑓 (x𝑡 ), v⟩ 3: 𝛾𝑡 ← 2/(𝑡 + 2) 4: x𝑡+1 ← x𝑡 + 𝛾𝑡 (v𝑡 − x𝑡 ) 5: if x𝑡+1 ∉ dom( 𝑓 ) or 𝑓 (x𝑡+1) > 𝑓 (x𝑡 ) then 6: x𝑡+1 ← x𝑡 As customary, we assume short-circuit evaluation of the logical conditions in Algorithm 1, i.e., if the first condition in Line 5 is true, then the second condition is not even checked, and the algorithm directly goes to Line 6. This minor modification of the vanilla Frank-Wolfe algorithm enables us to use the monotonicity of the iterates in the proofs to come, at the expense of at most one extra function 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𝑡 ) and v𝑡 . This effectively means that between successive iterations in which we search for an acceptable value of 𝛾𝑡 , we only need to call the zeroth-order and domain oracle. Remark 2.1. In practice, one can search for a suitable step size logarithmically, that is, halving the value of 𝛾𝑡 if either x𝑡+1 ∉ dom( 𝑓 ) or 𝑓 (x𝑡+1) > 𝑓 (x𝑡 ). This would lead to a 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 a factor of 2. The motivation and implications of this variant are detailed in Appendix A. For simplicity, we focus on the step size presented in Algorithm 1 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 (𝑀, 𝜈) generalized self-concordant function, then for 𝜈 ≥ 2, we have that:
𝑓 (y) − 𝑓 (x) − ⟨∇ 𝑓 (x), y − x⟩ ≤ 𝜔𝜈 (𝑑𝜈 (x − y)) ∥y − x∥2∇2 𝑓 (x) , (2.1) where the inequality holds if and only if 𝑑𝜈 (x, y) < 1 for 𝜈 > 2, and we have that,
𝑑𝜈 (x, y) def= { 𝑀 ∥y − x∥ if 𝜈 = 2 ( 𝜈2 − 1)𝑀 ∥y − x∥3−𝜈 ∥y − x∥𝜈−2∇2 𝑓 (x) if 𝜈 > 2,
where:
𝜔𝜈 (𝜏) def=  𝑒𝜏−𝜏−1 𝜏2 if 𝜈 = 2 −𝜏−ln(1−𝜏 ) 𝜏2 if 𝜈 = 3 (1−𝜏 )ln(1−𝜏 )+𝜏 𝜏2 if 𝜈 = 4( 𝜈−2 4−𝜈 ) 1 𝜏 [ 𝜈−2 2(3−𝜈)𝜏 ( (1 − 𝜏) 2(3−𝜈)2−𝜈 − 1 ) − 1 ] otherwise.
The inequality shown in Equation (2.1) is very similar to the one that we would obtain if the gradient of 𝑓 were Lipschitz continuous, however, while the Lipschitz continuity of the gradient leads to an inequality that holds globally for all x, y ∈ dom( 𝑓 ), the inequality in Equation (2.1) only holds for 𝑑𝜈 (x, 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 ℓ2 norm, and the term multiplying the norm is 𝜔𝜈 (𝑑𝜈 (x, y)) instead of 1/2. We deal with the latter issue by bounding 𝜔𝜈 (𝑑𝜈 (x, y)) with a constant that depends on 𝜈 for any x, y ∈ dom( 𝑓 ) such that 𝑑𝜈 (x, y) ≤ 1/2, as shown in Remark 2.3. Remark 2.3. As d𝜔𝜈 (𝜏)/d 𝜏 > 0 for 𝜏 < 1 and 𝜈 ≥ 2, then 𝜔𝜈 (𝜏) ≤ 𝜔𝜈 (1/2) for 𝜏 ≤ 1/2. Due to the fact that we use a simple step size 𝛾𝑡 = 2/(𝑡 + 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𝑡 + 𝛾𝑡 (v𝑡 − x𝑡 )) ≤ 1/2. Before formalizing the convergence rate we first review a lemma that we will need in the proof.
Lemma 2.4. (C.f., (Sun & Tran-Dinh, 2019, Proposition 7)) Let 𝑓 be a generalized selfconcordant function with 𝜈 > 2. If 𝑑𝜈 (x, y) < 1 and x ∈ dom( 𝑓 ) then y ∈ dom( 𝑓 ). For the case 𝜈 = 2 we have that dom( 𝑓 ) = ℝ𝑛. Putting all these things together allows us to obtain a convergence rate for Algorithm 1. Theorem 2.5. Suppose X is a compact convex set and 𝑓 is a (𝑀, 𝜈) generalized self-concordant function with 𝜈 ≥ 2. Then the Monotonous Frank-Wolfe algorithm (Algorithm 1) satisfies:
ℎ(x𝑡 ) ≤ 4(𝑇𝜈 + 1) 𝑡 + 1 max { ℎ(x0), 𝐿L0𝑓 𝐷2𝜔𝜈 (1/2) } . (2.2)
for 𝑡 ≥ 𝑇𝜈, where 𝐿L0𝑓 = maxu∈L0 ,d∈ℝ𝑛 ∥d∥2∇2 𝑓 (u) /∥d∥22 and 𝑇𝜈 is defined as:
𝑇𝜈 def = {⌈4𝑀𝐷⌉ − 2 if 𝜈 = 2⌈ 2𝑀𝐷 (𝐿L0
𝑓 )𝜈/2−1 (𝜈 − 2)
⌉ − 2 otherwise. (2.3)
Otherwise it holds that ℎ(x𝑡 ) ≤ ℎ(x0) for 𝑡 < 𝑇𝜈. Proof. Consider the compact set L0 def= {x ∈ dom( 𝑓 ) ∩ X | 𝑓 (x) ≤ 𝑓 (x0)}. As the algorithm makes monotonous progress and moves towards points such that x𝑡 ∈ X, then x𝑡 ∈ L0 for 𝑡 ≥ 0. As the smoothness parameter of 𝑓 is bounded over L0, we have from the properties of smooth functions that the bound ∥d∥2∇2 𝑓 (x𝑡 ) /∥d∥ 2 ≤ 𝐿L0 𝑓
holds for any d ∈ ℝ𝑛. Particularizing for d = x𝑡 − v𝑡 and noting that ∥x𝑡 − v𝑡 ∥ ≤ 𝐷 leads to ∥x𝑡 − v𝑡 ∥2∇2 𝑓 (x𝑡 ) ≤ 𝐿 L0 𝑓 𝐷2. We then define 𝑇𝜈 as in Equation (2.3). Note that for 𝑡 ≥ 𝑇𝜈 we have that 𝑑 (x𝑡 , x𝑡 + 𝛾𝑡 (v𝑡 − x𝑡 )) ≤ 1/2, and so as x𝑡 ∈ dom( 𝑓 ) we will have x𝑡 + 𝛾𝑡 (v𝑡 − x𝑡 ) ∈ dom( 𝑓 ), by application of Lemma 2.4. This means that the non-zero step size 𝛾𝑡 will ensure that x𝑡 + 𝛾𝑡 (v𝑡 − x𝑡 ) ∈ dom( 𝑓 ) in Line 5 of Algorithm 1. Moreover, it allows us to use the bound between points x𝑡 and x𝑡 +𝛾𝑡 (v𝑡 − x𝑡 ) in Proposition 2.2, which holds for 𝑑 (x𝑡 , x𝑡 + 𝛾𝑡 (v𝑡 − x𝑡 )) < 1. With this we can estimate the primal progress we can guarantee for 𝑡 ≥ 𝑇𝜈 if we move from x𝑡 to x𝑡 + 𝛾𝑡 (v𝑡 − x𝑡 ):
ℎ(x𝑡 + 𝛾𝑡 (v𝑡 − x𝑡 )) ≤ ℎ(x𝑡 ) − 𝛾𝑡𝑔(x𝑡 ) + 𝛾2𝑡 𝜔𝜈 (𝑑𝜈 (x𝑡 , x𝑡 + 𝛾𝑡 (v𝑡 − x𝑡 ))) ∥v𝑡 − x𝑡 ∥2∇2 𝑓 (x𝑡 ) ≤ ℎ(x𝑡 ) (1 − 𝛾𝑡 ) + 𝛾2𝑡 𝐿L0𝑓 𝐷2𝜔𝜈 (1/2),
where the second inequality follows from the upper bound on the primal gap via the Frank-Wolfe gap 𝑔(x𝑡 ), the application of Remark 2.3 as for 𝑡 ≥ 𝑇𝜈 we have that 𝑑𝜈 (x𝑡 , x𝑡 + 𝛾𝑡 (v𝑡 − x𝑡 )) ≤ 1/2, and from the fact that x𝑡 ∈ L0 for all 𝑡 ≥ 0. With the previous chain of inequalities we can bound the primal progress for 𝑡 ≥ 𝑇𝜈 as
ℎ(x𝑡 ) − ℎ(x𝑡 + 𝛾𝑡 (v𝑡 − x𝑡 )) ≥ 𝛾𝑡ℎ(x𝑡 ) − 𝛾2𝑡 𝐿L0𝑓 𝐷2𝜔𝜈 (1/2). (2.4) From these facts we can prove the convergence rate shown in Equation (2.2) by induction. The base case 𝑡 = 𝑇𝜈 holds trivially by the fact that using monotonicity we have that ℎ(x𝑇𝜈 ) ≤ ℎ(x0). Assuming the claim is true for some 𝑡 ≥ 𝑇𝜈 we distinguish two cases. Case 𝛾𝑡ℎ(x𝑡 ) − 𝛾2𝑡 𝐿L0𝑓 𝐷2𝜔𝜈 (1/2) > 0: Focusing on the first case, we can plug the previous inequality into Equation (2.4) to find that 𝛾𝑡 guarantees primal progress, that is, ℎ(x𝑡 ) > ℎ(x𝑡 + 𝛾𝑡 (v𝑡 − x𝑡 )) with the step size 𝛾𝑡 , and so we know that we will not go into Line 6 of Algorithm 1, and we have that ℎ(x𝑡+1) = ℎ(x𝑡 + 𝛾𝑡 (v𝑡 − x𝑡 )). Thus using the induction hypothesis and plugging in the expression for 𝛾𝑡 = 2/(𝑡 + 2) into Equation (2.4) we have:
ℎ(x𝑡+1) ≤ 4 max { ℎ(x0), 𝐿L0𝑓 𝐷2𝜔𝜈 (1/2) } ( (𝑇𝜈 + 1)𝑡 (𝑡 + 1) (𝑡 + 2) + 1 (𝑡 + 2)2 ) ≤ 4(𝑇𝜈 + 1) 𝑡 + 2 max { ℎ(x0), 𝐿L0𝑓 𝐷2𝜔𝜈 (1/2) } ,
where we use that (𝑇𝜈 + 1)𝑡/(𝑡 + 1) + 1/(𝑡 + 2) ≤ 𝑇𝜈 + 1 for all 𝑡 ≥ 0 and any 𝑡 ≥ 𝑇𝜈. Case 𝛾𝑡ℎ(x𝑡 ) − 𝛾2𝑡 𝐿L0𝑓 𝐷2𝜔𝜈 (1/2) ≤ 0: In this case, we cannot guarantee that the step size 𝛾𝑡 provides primal progress by plugging into Equation (2.4), and so we cannot guarantee if a step size of 𝛾𝑡 will be accepted and we will have x𝑡+1 = x𝑡 + 𝛾𝑡 (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𝑡 ) − 𝛾2𝑡 𝐿L0𝑓 𝐷2𝜔𝜈 (1/2) ≤ 0, by monotonicity we will have that:
ℎ(x𝑡+1) ≤ ℎ(x𝑡 ) ≤ 2 𝑡 + 2𝐿 L0 𝑓 𝐷2𝜔𝜈 (1/2) ≤ 4(𝑇𝜈 + 1) 𝑡 + 2 max { ℎ(x0), 𝐿L0𝑓 𝐷2𝜔𝜈 (1/2) } .
Where the last inequality holds as 2 ≤ 4(𝑇𝜈 + 1) for any 𝑇𝜈 ≥ 0. □ Remark 2.6. In the case where 𝜈 = 2 we can easily bound the primal gap ℎ(x1), as in this setting dom( 𝑓 ) = ℝ𝑛, which leads to ℎ(x1) ≤ 𝐿X𝑓 𝐷2 from Equation (2.4), regardless of if we set x1 = x0 or x1 = v0. Moreover, as the upper bound on the Bregman divergence holds for 𝜈 = 2 regardless of the value of 𝑑2 (x, y), we can modify the proof of Theorem 2.5 to obtain a convergence rate of the form ℎ(x𝑡 ) ≤ 2/(𝑡 + 1)𝐿X𝑓 𝐷2𝑤2 (𝑀𝐷) for 𝑡 ≥ 1, which is reminiscient of the O(𝐿X
𝑓 𝐷2/𝑡) 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 as opposed to the progress bound that arises from 𝐿L0
𝑓 -smoothness, as there
is no straightforward way to bound the number of iterations until the latter progress bound holds indefinitely for all x𝑡 + 𝛾𝑡 (v𝑡 − x𝑡 ), while there is a straightforward criterion on 𝛾𝑡 that allows us to ensure that the former holds from some point onward (see Remark A.1 in the Appendix for more details). Furthermore, with this simple step size we can also prove a 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 𝑓 is a (𝑀, 𝜈) generalized self-concordant function with 𝜈 ≥ 2. Then if the Monotonous Frank-Wolfe algorithm (Algorithm 1) is run for 𝑇 ≥ 𝑇𝜈 + 6 iterations, we will have that min1≤𝑡≤𝑇 𝑔(x𝑡 ) ≤ O(1/𝑇). 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 𝑇𝜈 and 𝜀; note that 𝑇𝜈 is independent of 𝜀. This is an important difference with respect to existing bounds, as the existing Frank-Wolfe-style first-order algorithms for generalized self-concordant functions 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 a 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 𝜀-optimal solution. Note that these bounds depend on user-defined initialization or tuning parameters provided by the user.
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.

heading: 2.1 Improved convergence guarantees
text: Algorithm 2 Frank-Wolfe with Backtrack of Pedregosa et al. (2020) (B-FW)
Input: x0 ∈ X ∩ dom( 𝑓 ), function 𝑓 , estimate 𝐿−1 Output: Iterates x1, . . . ∈ X 1: for 𝑡 = 0 to . . . do 2: v𝑡 ← argminv∈X ⟨∇ 𝑓 (x𝑡 ), v⟩ 3: 𝛾𝑡 , 𝐿𝑡 ← Backtrack( 𝑓 , x𝑡 , v𝑡 − x𝑡 , 𝐿𝑡−1, 1) 4: x𝑡+1 ← x𝑡 + 𝛾𝑡 (v𝑡 − x𝑡 ) We will now establish improved convergence rates for various special cases. We first focus on the assumption that x∗ ∈ Int (X ∩ dom( 𝑓 )), obtaining improved rates when we use the FW algorithm coupled with the adaptive step size strategy from Pedregosa et al. (2020) (see Algorithm 6 in Appendix).This assumption is reasonable if for example Bd(X) ⊈ dom( 𝑓 ), and Int (X) ⊆ 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( 𝑓 ) is a proper subset of X. In this case the optimum is guaranteed to be in Int (X ∩ dom( 𝑓 )). The analysis in this case is reminiscent of the one in the seminal work of Guélat & Marcotte (1986), and is presented in Appendix A.2. Note that we can upper bound the value of 𝐿𝑡 for 𝑡 ≥ 0 by ?̃? def= max{𝜏𝐿L0
𝑓 , 𝐿−1}, where 𝜏 > 1 is the backtracking parameter and 𝐿−1 is the
initial smoothness estimate in Algorithm 6 .
Theorem 2.9. Let 𝑓 be a (𝑀, 𝜈) generalized self-concordant function with 𝜈 ≥ 2 and let dom( 𝑓 ) not contain straight lines. Furthermore, we denote by 𝑟 > 0 the largest value such that B(x∗, 𝑟) ⊆ X ∩dom( 𝑓 ). Then the Frank-Wolfe algorithm with Backtrack (Algorithm 2) achieves a convergence rate for 𝑡 ≥ 1 of ℎ(x𝑡 ) ≤ ℎ(x0) ( 1 − 𝜇L0 𝑓 /(2?̃?) (𝑟/𝐷)2 ) 𝑡 .
The assumption that dom( 𝑓 ) does not contain straight lines in Theorem 2.9 is related to the Hessian being positive definite over dom( 𝑓 ) (see the proof in the Appendix in Theorem A.5). Note that this is a very mild assumption as we can simply modify the function with a very small ℓ2 regularizer, as e.g., in Nesterov (2012). Next, we recall the definition of uniformly convex sets, used in Kerdreux et al. (2021), which will allow us to obtain improved convergence rates for the FW algorithm over uniformly convex feasible regions.
Definition 2.10 ((𝜅, 𝑞)-uniformly convex set). Given two positive numbers 𝜅 and 𝑞, we say the set X ⊆ ℝ𝑛 is (𝜅, 𝑞)-uniformly convex with respect to a norm ∥·∥ if for any x, y ∈ X, 0 ≤ 𝛾 ≤ 1, and z ∈ ℝ𝑛 with ∥z∥ = 1 we have that y + 𝛾(x − y) + 𝛾(1 − 𝛾) · 𝜅 ∥x − y∥𝑞 z ∈ X. Theorem 2.11. SupposeX is a compact (𝜅, 𝑞)-uniformly convex set and 𝑓 is a (𝑀, 𝜈) generalized self-concordant function with 𝜈 ≥ 2. Furthermore, assume that minx∈X ∥∇ 𝑓 (x)∥ ≥ 𝐶 > 0. Then the Frank-Wolfe algorithm with Backtrack (Algorithm 2) achieves a convergence rate of:
ℎ𝑡 ≤  ℎ(x0) ( 1 − 12 min { 1, 𝜅𝐶 ?̃? }) 𝑡 if 𝑞 = 2 ℎ (x0 ) 2𝑡 if 𝑞 > 2, 1 ≤ 𝑡 ≤ 𝑡0 ?̃?𝑞/(𝑞−2) /(𝜅𝐶 )2/(𝑞−2) (1+(𝑞−2) (𝑡−𝑡0 )/(2𝑞) )𝑞/(𝑞−2) = O ( 𝑡−𝑞/(𝑞−2) ) if 𝑞 > 2, 𝑡 > 𝑡0,
for 𝑡 ≥ 1, where 𝑡0 = max{1, ⌊log1/2 (( ?̃?𝑞/(𝜅𝐶)2)1/(𝑞−2)ℎ(x0)⌋}.
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. SupposeX is a compact (𝜅, 𝑞)-uniformly convex set and 𝑓 is a (𝑀, 𝜈) 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 a convergence rate: ℎ𝑡 ≤  ℎ (x0 ) 2𝑡 if 1 ≤ 𝑡 ≤ 𝑡0 ( ?̃?𝑞/(𝜅2𝜇L0 𝑓 ) )1/(𝑞−1) (1+(𝑞−1) (𝑡−𝑡0 )/(2𝑞) )𝑞/(𝑞−1) = O ( 𝑡−𝑞/(𝑞−1) ) if 𝑡 > 𝑡0,
for 𝑡 ≥ 1, where 𝑡0 = max{1, ⌊log1/2 (( ?̃?𝑞/(𝜅2𝜇L0𝑓 ))1/(𝑞−1)/ℎ(x0))⌋}.
In Table 3 in Appendix A.2 we summarize the oracle complexity results shown in this paper for the B-FW algorithm when minimizing over a (𝜅, 𝑞)-uniformly 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 X is a polytope and 𝑓 is generalized self-concordant. This is not surprising, as 𝑓 is strongly convex and smooth over L0 if dom( 𝑓 ) 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.

heading: 3 Computational experiments
text: We showcase the performance of the M-FW algorithm, the second-order step size and the LLOO algorithm from Dvurechensky et al. (2020b) (denoted by GSC-FW and LLOO 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 in Julia using the FrankWolfe.jl package (Besançon et al., 2021), and the examples considered extend the ones presented in Dvurechensky et al. (2020b) and Liu et al. (2020). The code can be found in the fw-generalized-selfconcordant repository. We also use the vanilla FW algorithm denoted by FW, which is simply Algorithm 1 without Lines 5 and 6 using the traditional 𝛾𝑡 = 2/(𝑡 + 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 ℎ(x𝑡 ) and 𝑔(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 Δ𝑛; 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-Wolfe 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 a 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 𝑓 (x) = −∑𝑝 𝑡=1 log(⟨r𝑡 , x⟩), where 𝑝 denotes the number of periods and X = Δ𝑛. 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-Leibler divergence, expressed as 𝑓 (x) = 𝐷 (𝑊x, y) = ∑𝑁𝑖=1 {⟨w𝑖 , x⟩ log ( ⟨w𝑖 ,x⟩𝑦𝑖 ) − ⟨w𝑖 , x⟩ + 𝑦𝑖}, where w𝑖 is the 𝑖th row of a matrix 𝑊 . In order to promote sparsity and enforce nonnegativity of the solution, we use the unit simplex of radius 𝑅 as the feasible set X = {x ∈ ℝ𝑑+ , ∥x∥1 ≤ 𝑅}. The results are shown in Figure 3. We used the same 𝑀 = 1 choice for the second-order method as in Dvurechensky et al. (2020b) for comparison; its admissibility is unknown (see Remark C.1).
Logistic regression. We consider a logistic regression task with a design matrix with rows a𝑖 ∈ ℝ𝑛 with 1 ≤ 𝑖 ≤ 𝑁 and a vector y ∈ {−1, 1}𝑁 and formulate the problem with elastic net regularization, in a similar fashion as is done in Liu et al. (2020), with 𝑓 (x) = 1/𝑁 ∑𝑁𝑖=1 log(1 + exp(−𝑦𝑖 ⟨x, a𝑖⟩)) + 𝜇/2 ∥x∥2, where 𝜇 is a regularization parameter and X is the ℓ1 ball of radius 𝜌. The results can be seen in Figure 4 and Appendix C. Birkhoff polytope. All previously considered applications have in common a feasible region possessing computationally inexpensive LMOs (probability/unit simplex and ℓ1 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 a 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 5.

heading: Acknowledgements
text: Research reported in this paper was partially supported through the Research Campus Modal funded by the German Federal Ministry of Education and Research (fund numbers 05M14ZAM,05M20ZBM) and the Deutsche Forschungsgemeinschaft (DFG) through the DFG Cluster of Excellence MATH+. We would like to thank the anonymous reviewers for their suggestions and comments.

Review summaries:
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. 

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.

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.