In this paper we consider a composite optimization problem in the form of
where E is a finite dimensional real Hilbert space endowed with an inner product •, • , and the functions f, g : E → R ∪ {+∞} are proper and lower-semicontinuous. Assume that ϕ * is finite and attainable, and that g is a convex function, while f is possibly nonconvex.
In the recent years conditional gradient methods (e.g., Bach, 2015;Harchaoui et al., 2015;Nesterov, 2018;Ghadimi, 2019) have been developed for solving problem (1), which generate the iterates {x t } by the following scheme:
for each t ≥ 0, where τ t ∈ [0, 1] is a step size chosen by a certain rule. These methods originate from the Frank-Wolfe method (Frank and Wolfe, 1956) that was initially proposed for quadratic programming and later studied for more general or structured problems (e.g., Levitin and Polyak, 1966;Demyanov and Rubinov, 1970;Dunn, 1979;Beck and Teboulle, 2004). Conditional gradient methods have found rich applications in machine learning and statistics, where f and g are typically a loss function and a regularizer, respectively. The advantage of conditional gradient methods in these applications is that the solution v t to the subproblem in ( 2) is efficiently computable and also has some desirable property, such as preserving sparsity or low rank (Hazan, 2008;Clarkson, 2010;Jaggi, 2013;Harchaoui et al., 2015;Freund and Grigas, 2016;Nesterov, 2018).
The conditional gradient methods provide a computable quantity δ t , commonly referred to as the Frank-Wolfe gap, which is given by
Notice that δ t = 0 if and only if x t is a stationary point of ϕ. In addition, if f is convex, one can have ϕ(x t )-ϕ * ≤ δ t (see Lemma 3). Consequently, δ t ≤ ε is often used as a termination criterion for the conditional gradient methods.
The choice of step sizes is crucial for the performance of the conditional gradient methods, which is typically measured by the iteration complexity, namely, the worst-case number of iterations for reaching δ t ≤ ε or ϕ(x t ) -ϕ * ≤ ε for a prescribed tolerance ε > 0. There are numerous studies (e.g., Frank and Wolfe, 1956;Levitin and Polyak, 1966;Dunn, 1979;Freund and Grigas, 2016) on the step size rule when f is L-smooth, i.e., ∇f is Lipschitz continuous with constant L under a norm • . For example, the choice
guarantees an iteration complexity of O(ε -2 ) for reaching δ t ≤ ε (Lacoste-Julien, 2016). When f is additionally convex, it can be improved to O(ε -1 ), which can also be achieved by the step size τ t = 2 t+2 , a well-known choice for convex f (Jaggi, 2013;Freund and Grigas, 2016).
More generally, step size rules were studied when f is weakly smooth, that is, ∇f is Hölder continuous with exponent ν ∈ (0, 1]. In particular, when f is additionally convex, the choice τ t = 2 t+2 ensures an iteration complexity of O(ε -1/ν ) for reaching ϕ(x t ) -ϕ * ≤ ε (Nesterov, 2018), which is known to be nearly optimal from complexity theory perspective (Guzmán and Nemirovski, 2015). When g is strongly convex, Nesterov (2018) proposed the step size τ t = 6(t+1) (t+2)(2t+3) for obtaining a better iteration complexity of O(ε -1 2ν ). Recently, Ghadimi (2019) improved this complexity to O(ε -1-ν 2ν log 1 ε ) by using a step size τ t determined by a backtracking line search procedure. Remarkably, his method enjoys a linear rate of convergence when ν = 1. Ghadimi's method is also applicable to the case where f is nonconvex and achieves an iteration complexity of O(ε -1-ν 2ν -1 ) for reaching δ t ≤ ε. Conditional gradient methods were also studied for minimizing an L-smooth convex function over a strongly convex set (e.g., see Levitin and Polyak, 1966;Dunn, 1979;Garber and Hazan, 2015). Under the assumption that the set does not contain a stationary point of the function, it was established that the conditional gradient method with the step size given in (4) has a linear rate of convergence (Levitin and Polyak, 1966;Dunn, 1979). Such a method was also generalized to minimize an L-smooth convex function over a uniformly convex set (Kerdreux et al., 2021a).
In this paper we first study a parameter-dependent conditional gradient method proposed in (Zhao and Freund, 2020, Algorithm 4) with a step size depending explicitly on the problem parameters for solving a broad class of problems in the form of (1), including but not limited to the problems considered in the above references (Levitin and Polyak, 1966;Dunn, 1979;Jaggi, 2013;Garber and Hazan, 2015;Freund and Grigas, 2016;Lacoste-Julien, 2016;Nesterov, 2018;Ghadimi, 2019;Kerdreux et al., 2021a;Zhao and Freund, 2020). Though this method was analyzed in (Zhao and Freund, 2020) for problem (1) with convex f and bounded dom g, there is a lack of analysis for (1) with nonconvex f . In this paper, we analyze the rate convergence of this method for problem (1) with f being possibly nonconvex under the assumption that ∇f is Hölder continuous and dom g is bounded or the problem has a uniformly convex structure. As a byproduct, we obtain a new iteration complexity of O(ε -1-ν 2ν ) 1 for problem (1) with ∇f being Hölder continuous with exponent ν ∈ (0, 1) and g being strongly convex, which improves by the factor log(1/ε) the previously best known one (Ghadimi, 2019).
Though the aforementioned parameter-dependent method (Algorithm 1) is simple and also enjoys a nice iteration complexity, its step size may suffer from some issues. Indeed, its step size requires prior knowledge of the parameters ν and M ν associated with the Hölder continuity of ∇f . Since they depend on f , g, and also a particular norm on E, they may be hard to be found if f is sophisticated. On another hand, the parameters ν and M ν are not unique. The tighter value of them typically leads to a faster convergent algorithm. Yet, it may be challenging to find the tightest possible value for them. Motivated by these, we further propose a parameter-free conditional gradient method (see Algorithm 2) in which the step size is chosen by using a constructive local quadratic upper approximation and an adaptive line search scheme, without using prior knowledge of ν and M ν . We show that this method achieves the same rate of convergence as the parameter-dependent conditional gradient method, which, however, uses prior knowledge of the problem parameters ν and M ν .
The results of this paper were presented in the SIAM Conference on Optimization in July 2021 (Ito et al., 2021). During the preparation of this paper, a concurrent work (Peña, 2022) proposed a parameter-free conditional gradient method for problem (1) with convex f and established similar complexity bounds as the ones obtained in this paper yet in terms of primal-dual optimality gap that is typically weaker than the Frank-Wolfe gap which we use. It shall be mentioned that our analyses are vastly different from those in (Peña, 2022) and shed new insights into conditional gradients for solving a broader class of problems.
The rest of this paper is organized as follows. In Section 2 we introduce some notation and make some assumptions on the problem studied in this paper. In Section 3 we propose a parameter-dependent conditional gradient method, and show some results on its rate of convergence. In Section 4 we propose a parameter-free conditional gradient method, and establish its rate of convergence and also iteration complexity. Section 5 presents numerical experiments to compare the performance of this method with the conditional gradient methods with some other step size rules. The proofs of main results are given in Section 6. Finally, we make some concluding remarks in Section 7.
Throughout the paper, E is a finite dimensional real Hilbert space endowed with an inner product •, • . Let • be an arbitrary norm on E and • * its dual, i.e., z * = sup x ≤1 z, x for z ∈ E. We denote by R + and Z + the set of nonnegative real numbers and the set of nonnegative integers, respectively. For any real number a, we denote by a + the nonnegative part of a, that is, a + = max{a, 0}. For the convex function g, dom g denotes the domain of g, i.e., dom g = {x ∈ E : g(x) = +∞}. We denote by D g the diameter of dom g, that is,
Clearly, D g = +∞ if dom g is unbounded.
We make the following assumption on the functions f and g throughout this paper.
Assumption 1 (i) The function f : E → R∪{+∞} is a proper and lower-semicontinuous function. Moreover, f is differentiable on dom g and the gradient ∇f is Hölder continuous on dom g, i.e., there exist ν ∈ (0, 1] and M ν > 0 such that
(ii) The function g : E → R ∪ {+∞} is a proper, lower-semicontinuous, and convex function. In addition, for each x ∈ dom g, the subproblem
has at least one optimal solution.
The function f satisfying Assumption 1(i) is commonly referred to as a (ν, M ν )-weakly smooth function on dom g. There are many instances of problem (1) satisfying Assumption 1(i). For example, problem (1) with ∇f being semi-algebraic 2 continuous and dom g being a compact semi-algebraic set is one of them (Bolte et al., 2020, Proposition C.1). Also, there are some machine learning models satisfying Assumption 1(i) (see, e.g., Bolte 2. A semi-algebraic set is a finite union of sets of the form {x ∈ E | pi(x) = 0, i = 1, . . . , k, qj(x) < 0, j = 1, . . . , l} for some real polynomials pi, qj. A map h : R m → R n is said to be semi-algebraic if its graph et al., 2020;Zwiernik, 2016;Chen et al., 2020). In addition, Assumption 1(ii) plays an important role in a conditional gradient method for solving problem (1). Indeed, all the conditional gradient methods in the literature solve a subproblem in the form of (7) per iteration.
In this paper, we will consider problem (1) satisfying Assumption 1 and one additional assumption that g has a bounded domain or problem (1) has a uniformly convex structure introduced below.
Assumption 2 Problem (1) has a uniformly convex structure, that is, there exist κ > 0 and ρ ≥ 2 such that for any x ∈ dom g and any optimal solution v * to the subproblem (7), we have
There are many instances of problem (1) with a uniformly convex structure. We next provide two examples of (1) for which Assumptions 1 and 2 hold.
Example 1 (Optimization over a uniformly convex set) Let C ⊂ E be a nonempty compact (c, ρ)-uniformly convex set with respect to • for some c > 0 and ρ ≥ 2, 3 that is, C is a nonempty compact convex set satisfying that (1 -λ)x + λy + z ∈ C for any x, y ∈ C, λ ∈ [0, 1], and z with z ≤ λ(1 -λ) c ρ x -y ρ . Consider the problem
where f is differentiable on C, ∇f is Hölder continuous on C, and α = min x∈C ∇f (x) * > 0 (i.e., no stationary point of f belongs to C). Let g be the indicator function of C. One can easily observe that problem (9) is a special case of (1), and moreover, Assumption 1 holds for it. We next verify that Assumption 2 also holds for it. Indeed, let x ∈ dom g and v * ∈ Argmin v∈E { ∇f (x), v + g(v)} be arbitrarily chosen. Then we have that x ∈ C and v * ∈ Argmin v∈C ∇f (x), v . Since C is a (c, ρ)-uniformly convex set, one has that
for any λ ∈ (0, 1), v ∈ C, and z with z ≤ 1. This and the optimality of v * lead to
Taking sup z ≤1 on both sides of this inequality, letting λ ↑ 1, and using α = min x∈C ∇f (x) * , we obtain that
This, together with g being the indicator function of C, implies that (8) is satisfied with κ = αc. Therefore, Assumption 2 holds for problem (9).
3. For example, the p-balls are uniformly convex with ρ = max(2, p) for p ∈ (1, ∞). In addition, C is often referred to as a strongly convex set if ρ = 2. See Vial (1982); Levitin and Polyak (1966); Garber and Hazan (2015); Kerdreux et al. (2021a,b) for the discussion on uniformly or strongly convex sets.
Example 2 (Optimization with a uniformly convex function) Consider a special case of problem (1), where ∇f is Hölder continuous on dom g, and g is a proper, lower-semicontinuous and (κ, ρ)-uniformly convex function with respect to • for some κ > 0 and ρ ≥ 2, that is, g satisfies that
By this, one can observe that (e.g., see Zȃlinescu, 2002)
where g (x; d) = lim s↓0 (g(x + sd) -g(x))/s is the directional derivative of g along the direction d. It then follows that g is coercive, which together with the lower-semicontinuity of g implies that subproblem (7) has at least one optimal solution. Thus, Assumption 1 holds for this problem. We next verify that Assumption 2 also holds for it. Indeed, let x ∈ dom g and v * = argmin v∈E { ∇f (x), v + g(v)}. By these and (10), one has
for all v ∈ dom g. In addition, by the optimality of v * , we have ∇f (x), v -v * + g (v * ; vv * ) ≥ 0 for all v ∈ dom g. These two inequalities immediately yield (8). Therefore, Assumption 2 also holds for this problem.
In this section we present in Algorithm 1 a parameter-dependent conditional gradient method for solving problem (1), whose step size τ t depends on the problem parameters ν and M ν explicitly. This algorithm was proposed in (Zhao and Freund, 2020, Algorithm 4) and analyzed by them for the case where f is convex and dom g is bounded. However, it was not analyzed for the case where f is nonconvex. In what follows, we will analyze its rate of convergence for solving (1) with f being possibly nonconvex under the assumption that dom g is bounded or problem (1) has a uniformly convex structure. It shall be mentioned that the convergence results established in this section also hold for a variant of Algorithm 1 with the exact step size
Before proceeding, we state a well-known lemma (e.g., see Ghadimi, 2019), which shows that the quantity δ t , commonly referred to as the Frank-Wolfe gap, provides an upper bound on the optimality gap of problem (1) at x t when f is convex. For the sake of completeness, we include a proof for it.
Lemma 3 Let the sequences {x t } and {δ t } be generated in Algorithm 1. Suppose that f is convex. Then it holds that δ t ≥ ϕ(x t ) -ϕ * for all t ≥ 0.
Parameter-Free Conditional Gradient Method Algorithm 1: A parameter-dependent conditional gradient method Input: x 0 ∈ dom g.
1: for t = 0, 1, 2, . . . , do 2: x t+1 = (1 -τ t )x t + τ t v t . 6: end for Proof Let x * be an arbitrary optimal solution of problem (1). Then f (x * ) + g(x * ) = ϕ * . By this, the expression of δ t , and the convexity of f , we have that for all t ≥ 0,
Remark 4 From the proof of Lemma 3, one can observe that the convexity of f is only used in (11). More generally, (11) is also valid if f satisfies the star-convexity property (Nesterov and Polyak, 2006): there exists some x * ∈ Argmin x ϕ(x) such that f (λx * + (1 -λ)x) ≤ λf (x * ) + (1 -λ)f (x) for all λ ∈ [0, 1] and x ∈ dom g. Thus, the conclusion of Lemma 3 also holds if f satisfies the star-convexity property. Moreover, all the results established in this paper for a convex f also hold for a star-convex f .
In what follows, we state some results regarding the rate of convergence of Algorithm 1 in Theorems 5 and 7, whose proofs are deferred to Section 6.2. In particular, we first present the results under the assumption that g has a bounded domain, namely, D g < +∞.
Theorem 5 Let the sequences {x t } and {δ t } be generated in Algorithm 1. Suppose that Assumption 1 holds, D g < +∞, and that δ t > 0 for all t ≥ 0, where D g is defined in (5). Let δ * t = min 0≤i≤t δ i and
Then the following statements hold.
(i) {ϕ(x t )} is non-increasing and ϕ * = lim t→∞ ϕ(x t ) exists. In addition, {δ * t } satisfies
Remark 6 When f is nonconvex, the limit ϕ * = lim t→∞ ϕ(x t ) in Theorem 5 can be interpreted as the function value at some stationary point of ϕ. Indeed, for any convergent subsequence {x t } t∈T with limit x * such that {δ t } t∈T → 0, it follows from (3) that
Taking the limit over t ∈ T , we can see that x * ∈ Argmin x { ∇f (x * ), x + g(x)}. Thus, x * is a stationary point of ϕ and moreover ϕ * = ϕ(x * ).
We next present some results regarding the rate of convergence of Algorithm 1 under the assumption that problem (1) has a uniformly convex structure, namely, Assumption 2 holds.
Theorem 7 Let the sequences {x t } and {δ t } be generated in Algorithm 1. Suppose that Assumptions 1 and 2 hold and that δ t > 0 for all t ≥ 0. Let δ * t = min 0≤i≤t δ i for all t ≥ 0 and
Then the following statements hold.
(i) {ϕ(x t )} is non-increasing and ϕ * = lim t→∞ ϕ(x t ) exists. In addition, {δ * t } satisfies
for all t ≥ 0.
(ii) Assume additionally that f is convex.
(a) When ν = 1 and ρ = 2, we have
Parameter-Free Conditional Gradient Method
Algorithm 2: A parameter-free conditional gradient method Input: x 0 ∈ dom g and L -1 > 0.
1: for t = 0, 1, 2, . . . , do 2:
3:
).
repeat for i = 0, 1, 2, . . . , 5:
Remark 8 It can be observed from Theorem 7 that under Assumptions 1 and 2, Algorithm 1 enjoys a linear rate of convergence when applied to problem (1) with f being convex, ν = 1 and ρ = 2.
As seen from above, Algorithm 1 is not only simple but also enjoys a nice rate of convergence. However, its step size τ t may suffer from some practical issues. Indeed, to evaluate τ t , one needs to know the problem parameters ν and M ν in advance. As observed from ( 6), these parameters depend on f , g, and also a particular norm on E. Thus, it may not be easy to find them if f is a sophisticated function. On another hand, the parameters ν and M ν are not unique. The tighter value of them typically leads to a faster convergent algorithm. Yet, it may be challenging to find the tightest possible value for them. Motivated by these, we next propose a parameter-free conditional gradient method (Algorithm 2) in which the step size is chosen by using a constructive local quadratic upper approximation and an adaptive line search scheme, without using prior knowledge of ν and M ν .
We now provide some explanation for Algorithm 2. Observe that the step size τ t in Algorithm 1 is the minimizer of h
Assuming that ν and M ν are unknown, we can find a quadratic approximation to h t , without explicitly involving ν and M ν , and then obtain a step size by minimizing it over [0, 1]. Indeed, by the Hölder continuity of ∇f , the following inequality holds (e.g, see Nesterov, 2015, Lemma 2):
where
By ( 15) and a suitable choice of ε (see the proof of next theorem for details), one can obtain a quadratic approximation to h t given by
for some L t > 0, which is determined by an adaptive line search scheme without explicitly using ν and M ν . The step size τ t in Algorithm 2 is then obtained by minimizing ht in place of h t over [0, 1]. Therefore, Algorithm 2 does not explicitly use the parameters ν and M ν .
The following theorem shows that Algorithm 2 is well-defined, whose proof is deferred to Section 6.3. In particular, we will establish that in each outer iteration of Algorithm 2 the adaptive line search procedure must terminate after a finite number of trials. We will also establish some other properties for the adaptive line search procedure.
Theorem 9 Let the sequences {L t } and {δ t } be generated in Algorithm 2. Suppose that Assumption 1 holds and that δ t > 0 for all t ≥ 0. 6 Let
for all t ≥ 0, where L(•) is defined in (16). For any δ > 0, let
(18) Then the following statements hold.
(i) The inequality (14) holds whenever
(iii) Suppose further that min 0≤i≤t δ i ≥ ε for some t ≥ 0 and ε > 0. Then the total number of inner iterations performed by the adaptive line search procedure until the t-th iteration of Algorithm 2 is bounded by 2t + 2 + [log 2 (2L(ε)/L -1 )] + .
5. By convention, we set 0 0 = 1. One can observe that when ν = 1, L(ε) becomes Mν and thus (15) still holds. 6. If δt = 0 for some t ≥ 0, xt is already a stationary point of problem (1) and Algorithm 2 shall be terminated.
The next theorem establishes some results for the case where g has a bounded domain, namely, D g < +∞, whose proof is deferred to Section 6.3.
Theorem 10 Let the sequences {x t } and {δ t } be generated in Algorithm 2. Suppose that Assumption 1 holds, D g < +∞, and that δ t > 0 for all t ≥ 0, where D g is defined in (5). Let δ * t = min 0≤i≤t δ i for all t ≥ 0 and
where L 0 is defined in (17). Then the following statements hold.
(i) {ϕ(x t )} is non-increasing and ϕ * = lim t→∞ ϕ(x t ) exists. In addition, {δ * t } satisfies
.
As an immediate consequence of Theorem 10, we obtain the following complexity results for Algorithm 2 for finding an approximate solution of problem (1) with an ε-Frank-Wolfe gap, whose proofs are omitted.
Corollary 11 Under the same settings as in Theorem 10, Algorithm 2 reaches the criterion
In what follows, we present some results regarding the rate of convergence of Algorithm 2 for the case where problem (1) has a uniformly convex structure, namely, Assumption 2 holds, whose proof is deferred to Section 6.3.
Theorem 12 Let the sequences {x t } and {δ t } be generated by Algorithm 2. Suppose that Assumptions 1 and 2 hold and that δ t > 0 for all t ≥ 0. Let δ * t = min 0≤i≤t δ i for all t ≥ 0, and
where L 0 is defined in (17). Then the following statements hold.
(i) {ϕ(x t )} is non-increasing and ϕ * = lim t→∞ ϕ(x t ) exists. In addition, {δ * t } satisfies
for all t ≥ t0 .
(ii) Assume additionally that f is convex.
(a) When ν = 1 and ρ = 2, we have
As an immediate consequence of Theorem 12, we obtain the following complexity results for Algorithm 2 for finding an approximate solution of problem (1) with an ε-Frank-Wolfe gap, whose proofs are omitted.
Corollary 13 Under the same settings as in Theorem 12, Algorithm 2 reaches the criterion
iterations. In addition, if f is convex, and ν = 1 or ρ = 2, Algorithm 2 reaches the criterion δ t ≤ ε within
Remark 14 In view of the identity lim α→0 1 α (x α -1) = log x, one can observe that the limit of (22
which is consistent with the bound (21) for the case with ν = 1 and ρ = 2.
As mentioned earlier, the Frank-Wolfe gap δ t defined in (3) is a computable quantity and can be used to measure whether the associated iterate x t is an approximate stationary point of problem (1). Therefore, δ t ≤ ε can be used as a practical termination criterion for Algorithms 1 and 2 for a prescribed tolerance ε > 0. Besides, one can observe from Theorems 5, 7, 10 and 12 that Algorithms 1 and 2 enjoy the same rate of convergence and thus the same iteration complexity with respect to the termination criterion δ t ≤ ε.
Consequently, it suffices to discuss the iteration complexity of Algorithm 2 with such a termination criterion. One can observe from Corollaries 11 and 13 that the iteration complexity of Algorithm 2 for reaching the termination criterion δ t ≤ ε is:
) if f is nonconvex and problem (1) has a uniformly convex structure;
(iii) O(ε -1/ν ) if f is convex and dom g is bounded;
(iv) O(log(1/ε)) if f is convex and problem (1) has a uniformly convex structure with ν = 1 and ρ = 2;
) if f is convex and problem (1) has a uniformly convex structure with ν = 1 or ρ = 2.
Since ρ ≥ 2 and ν ∈ (0, 1], one has ε -(ρ-1-ν)/(ρν) < ε -1/ν and ε -1-(ρ-1-ν)/(ρν) < ε -1-1/ν when ν = 1 or ρ = 2. In view of this and the above complexity results, we can observe that Algorithm 2 enjoys a lower iteration complexity bound under Assumption 2 than the one under the assumption that dom g is bounded. Besides, the iteration complexity bound in (iii) matches the ones obtained in (Nesterov, 2015;Zhao and Freund, 2020). It should, however, be noted that the conditional gradient methods in (Nesterov, 2015;Zhao and Freund, 2020) use the step size τ t = 2/(t + 2) and the same one as given in Algorithm 1, respectively. These step sizes are not locally adaptive because they use none of local or global problem information, and could be conservative in practice. Moreover, the latter one requires prior knowledge of the parameters ν and M ν . In contrast with them, the step size in Algorithm 2 is locally adaptive and free of problem parameters. In addition, the iteration complexity bounds in (ii) and (iv) match the ones obtained in (Ghadimi, 2019) for the case with ρ = 2. The iteration complexity bound in (v) improves by the factor log(1/ε) the one established in (Ghadimi, 2019) for the case with ν < 1 and ρ = 2. For a smooth convex f with ν = 1 and g being the indicator function of a uniformly convex set, similar iteration complexity bounds as in (iv) and (v) with ν = 1 were established in (Kerdreux et al., 2021a) for a parameter-dependent conditional gradient method for reaching the criterion ϕ(x t ) -ϕ * ≤ ε.
In addition, as observed from Theorem 9 (iii), the total number of inner iterations of Algorithm 2 for reaching the termination criterion δ t ≤ ε is at most 2t+[log 2 (2L(ε)/L -1 )] + . Also, notice from (18) that log L(ε) = O(log(1/ε)). In view of these, one can see that the total number of inner iterations of Algorithm 2 enjoys the same complexity bounds as given in (i)-(v) for reaching the termination criterion δ t ≤ ε.
In this section we conduct some numerical experiments to compare the performance of the conditional gradient methods studied in this paper with the ones with some other step size rules. For the comparison, we construct the problems whose Hölder continuity exponent ν and uniform convexity exponent ρ are known in advance. More specifically, we generate the test instances from the problem classes discussed in Examples 1 and 2, respectively. Our experiments are conducted in Matlab on an Apple desktop with the 3.0GHz Intel Xeon E5-1680v2 processor and 64GB of RAM.
In our first experiment, we consider the following problem:
where 1 < p ≤ 2, q > 1, A ∈ R m×n , and b ∈ R m . Note that B q is a uniformly convex set with exponent ρ = max(2, q) (e.g., see Kerdreux et al., 2021a,b). In addition, as shown in Lemma 17 in Section 6.1, the gradient of the objective function of ( 23) is Hölder continuous with respect to • 2 with exponent ν = p -1 and modulus
A p 2 . Thus, problem (23) belongs to the class of the problems minimizing a weakly smooth convex function over a uniformly convex set discussed in Example 1. Note that when A = I, it reduces to the problem of the p -norm projection of a vector onto the q unit ball.
We next apply the following three conditional gradient methods to solve problem (23), and compare their performance.
A p 2 .
• Algorithm 2 with • = • 2 .
• The conditional gradient method with the well-known diminishing step size τ t = 2/(t + 2) (Jaggi, 2013;Freund and Grigas, 2016), which is similar to Algorithm 1 except the choice of τ t .
As discussed in Section 4.1, for finding an approximate solution of ( 23) with an ε-Frank-Wolfe gap, the conditional gradient method with step size τ t = 2/(t + 2) enjoys an iteration complexity of O(ε -1/ν ), while Algorithms 1 and 2 enjoy the following iteration complexity:
with ρ = max(2, q) and ν = p -1.
When applied to (23), the above three methods need to solve the subproblems of the form min
x { u, x : x q ≤ 1} for u ∈ R n . It is not hard to observe that this problem has a closed-form solution given by
The instances of problem ( 23) are generated as follows. In particular, we generate matrix A by letting A = U DU T , where D ∈ R n×n is a diagonal matrix, whose diagonal entries are randomly generated according to the uniform distribution over [1, 100] and U ∈ R n×n is a randomly generated orthogonal matrix. We set b = Ax for some x generated from a uniform distribution over {x ∈ R n : x q = 10}.
In this experiment, we consider p ∈ {1.3, 1.6, 2}, q ∈ {1.5, 2, 3} and m = n ∈ {1000, 5000}. For each choice of (p, q, n), we randomly generate 10 instances of problem (23) by the procedure mentioned above, and apply the aforementioned three conditional gradient methods to solve them, starting with the initial point x 0 = 0 and terminating them once the criterion δ t /δ 0 ≤ 10 -6 is met, where δ t and δ 0 are the Frank-Wolfe gap at the iterates x t and x 0 , respectively. Table 1 presents the average CPU time (in seconds) and the average number of iterations of these methods over the 10 random instances. In detail, the values of n, q, p are given in the first three columns, and the average CPU time and the average number of iterations of Algorithms 1, 2 and the conditional gradient method with step size τ t = 2/(t + 2) are given in the rest of the columns. In addition, Figure 1 illustrates the behavior of the best relative Frank-Wolfe gap δ * t /δ 0 := min 0≤i≤t δ i /δ 0 and the objective value gap ϕ(x t ) -ϕ * with respect to CPU time on a single random instance of problem ( 23) with n = 5000, q = 3, and p = 1.3, 1.6, 2, respectively, where ϕ * is the minimum objective function value of all iterates generated by the three algorithms. One can see that Algorithm 2 generally outperforms the other two methods. This is perhaps because: (i) Algorithm 2 improves the iteration complexity of the conditional gradient method with step size τ t = 2/(t + 2); (ii) Algorithm 2 uses an adaptive step size determined by using a constructive local quadratic upper approximation of the objective function and an adaptive line search scheme.
Figure 1: Numerical results on a single random instance of problem ( 23) with n = 5000, q = 3, and p = 1.3, 1.6, 2, respectively. These sub-figures illustrate the behavior of the best relative Frank-Wolfe gap δ * t /δ 0 := min 0≤i≤t δ i /δ 0 and the objective value gap ϕ(x t ) -ϕ * with respect to CPU time in seconds, where ϕ * is the minimum objective function value of all iterates generated by the three algorithms for solving one problem instance.
In our second experiment, we consider the following problem:
where p > 1, λ > 0, A ∈ R m×n , and b ∈ R m . Note that f (x) = 1 p Ax -b p p is weakly smooth and g(x) = λ n i=1 x i log x i + ι ∆n (x) is λ-strongly convex with respect to the 1norm (e.g., see Beck and Teboulle, 2003), where ι ∆n denotes the indicator function of ∆ n . Thus, problem ( 24) is a special case of Example 2 with ν = p -1 and ρ = 2.
We next apply Algorithms 1 and 2 with the same settings as in Subsection 5.1 and the conditional gradient method with the diminishing step size
proposed by Nesterov (2018) to solve problem (24), and compare their performance. The latter method is similar to Algorithm 1 except the choice of τ t and enjoys an iteration complexity of O(ε -1/(2(p-1)) ) for finding an approximate solution of ( 24) with an ε-Frank-Wolfe gap (Nesterov, 2018). In addition, as seen from Section 4.1, Algorithms 1 and 2 enjoy the following iteration complexity for finding an approximate solution of ( 24) with an ε-Frank-Wolfe gap:
When applied to (24), the aforementioned three methods need to solve the subproblems of the form min x∈∆n u, x + λ n i=1
x i log x i for some u ∈ R n . It is well-known that this problem has a closed-form solution given by
The instances of problem ( 24) are generated as follows. In particular, we generate matrix A with A 2 ≤ 100 by letting A = V DU T , where D is a m × m diagonal matrix, whose diagonal entries are randomly generated according to the uniform distribution over [0, 100], and U ∈ R n×m and V ∈ R m×m are randomly generated orthonormal matrices. Each entry of b ∈ R m is generated from the uniform distribution on [0, 1].
In this experiment, we consider m = n/2 ∈ {1000, 5000}, p ∈ {1.5, 1.75, 2}, and λ ∈ {1, 10, 50}. For each choice of (m, n, p, λ), we randomly generate 10 instances of problem ( 24) by the procedure mentioned above, and apply the aforementioned three conditional gradient methods to solve them, starting with the initial point x 0 = (1/n, . . . , 1/n) T and terminating them once the criterion δ t /δ 0 ≤ 10 -8 is met, where δ t and δ 0 are the Frank-Wolfe gap at the iterates x t and x 0 , respectively. Table 2 presents the average CPU time (in seconds) and the average number of iterations of these methods over the 10 random instances. In detail, the values of m, p, λ are given in the first three columns, and the average CPU time and the average number of iterations of Algorithms 1, 2 and the conditional gradient method with step size τ t = 6(t + 1)/((t + 2)(2t + 3)) are given in the rest of the columns. In addition, Figure 2 illustrates the behavior of the best relative Frank-Wolfe gap δ * t /δ 0 := min 0≤i≤t δ i /δ 0 and the objective value gap ϕ(x t ) -ϕ * with respect to CPU time on a single random instance of problem ( 24) with m = 5000, n = 10,000, λ = 10, and p = 1.5, 1.75, 2, respectively, where ϕ * is the minimum objective function value of all iterates generated by the three algorithms. One can see that Algorithm 2 generally outperforms the other two methods, which is perhaps for the similar reasons as explained at the end of Subsection 5.1.
In our third experiment, we consider the following simplex-constrained nonnegative matrix factorization problem (see Thanh et al., 2022): Figure 2: Numerical results on a single random instance of problem ( 24) with m = 5000, n = 10,000, λ = 10, and p = 1.5, 1.75, 2, respectively. These sub-figures illustrate the behavior of the best relative Frank-Wolfe gap δ * t /δ 0 := min 0≤i≤t δ i /δ 0 and the objective function value gap ϕ(x t ) -ϕ * with respect to CPU time in seconds. Here, ϕ * denotes the minimum objective function value of all iterates generated by the three algorithms for solving one problem instance.
where X ∈ R n×m , α, λ > 0, • F is the Frobenius norm, and 1 d ∈ R d is the all-ones vector for any d ≥ 1. Problem ( 26) can be viewed as min U,V {ϕ(U,
where ι B n,k and ι ∆ k,m denote the indicator function of B n,k and ∆ k,m , respectively. Notice that f is nonconvex and smooth, dom g is compact, and g is strongly convex. Clearly, problem ( 26) is a special case of problem (1) satisfying Assumptions 1 and 2 with ν = 1 and ρ = 2. We next apply the following two conditional gradient methods to solve problem ( 26), and compare their performance.
• Algorithm 2 with • = • F .
• The conditional gradient method with line search (Ghadimi, 2019, Algorithm 2), abbreviated as CGM-LS. We set the parameters γ = 0.5 and δ = εδ 0 /4 for this method as suggested in (Ghadimi, 2019), where δ 0 is the Frank-Wolfe gap at the initial point and ε is the targeted tolerance for the final relative Frank-Wolfe gap.
It shall be mentioned that these two methods enjoy an iteration complexity of O(1/ε) for finding an approximate solution of ( 26) with an ε-Frank-Wolfe gap (see Section 4.1 and equation (1.8) in (Ghadimi, 2019)).
The data matrix X ∈ R n×m for problem ( 26) is generated as follows. In particular, we first randomly generate U * ∈ R n×k with all entries following the uniform distribution over [0, α]. We next randomly generate V ∈ R k×m with all entries following the standard normal distribution and set V * = V D, where D ∈ R m×m is a diagonal matrix such that (V * ) T 1 k = 1 m . Finally, we set X = U * V * + E, where the entries of E ∈ R n×m follow the normal distribution with mean zero and standard deviation 0.01.
In this experiment, we set λ = 0.01, α = 2, and consider m = n ∈ {100, 200, 300, 400, 500} and k ∈ {5, 10}. For each choice of (m, n, k), we randomly generate 10 instances of problem (26) by the procedure mentioned above. Then we apply the aforementioned two conditional gradient methods to solve them with the initial point U 0 and V 0 being the matrices of all entries equal to 1 and 1/k, respectively, and terminate the methods once the criterion δ t /δ 0 ≤ 10 -5 is met, where δ t is the Frank-Wolfe gap at the t-th iteration (U t , V t ). The computational results are presented in Table 3. In particular, the values of m and k are given in the first two columns, and the average CPU time (in seconds) and the average number of iterations over each set of 10 random instances for these methods are given in the rest of the columns. Besides, in Figure 3 we illustrate the behavior of the best relative Frank-Wolfe gap δ * t /δ 0 := min 0≤i≤t δ i /δ 0 and the relative objective function value ϕ(U t , V t )/ϕ(U 0 , V 0 ) with respect to CPU time on a single random instance of problem ( 24) with m = n = 300, λ = 0.01, α = 2, and k = 5, 10, respectively.
One can observe that Algorithm 2 significantly outperforms the conditional gradient method with line search proposed in Ghadimi (2019). This is perhaps because: (i) the line search criterion of the conditional gradient in Ghadimi (2019) explicitly depends on the targeted accuracy ε, while the line search criterion of Algorithm 2 does not; (ii) at each iteration, the initial trial step size in Algorithm 2 is determined by using a constructive local quadratic upper approximation of the objective function, while the line search procedure in Ghadimi (2019) does not use such a novel scheme.
In this section, we provide a proof of our main results presented in Sections 3 and 4.
In this subsection we establish some technical lemmas that will be used subsequently.
Lemma 15 Suppose that {β t } and {γ t } are sequences of nonnegative real numbers such that
for some constants c ∈ (0, 1), α ≥ 0 and A > 0. Then, γ = lim t→∞ γ t exists and the sequence β * t = min 0≤i≤t β i satisfies
, ∀t ≥ 0.
In particular, we have
Proof Since {β t } ⊂ R + , the relation ( 27) implies that {γ t } is non-increasing, which together with {γ t } ⊂ R + further implies that γ = lim t→∞ γ t exists. In addition, by β * t = min 0≤i≤t β i and ( 27), one can obtain that
Summing up these inequalities yields γ t+1 ≤ γ 0 -(t + 1)cβ * t min{1, (β * t ) α /A}, ∀t ≥ 0. By this and γ t+1 ≥ γ, we have β * t min{1, (β * t ) α /A} ≤ (γ 0 -γ)/(c(t + 1)), which implies the desired assertions.
Lemma 16 Suppose that {β t } and {γ t } are sequences of nonnegative real numbers such that the recurrence (27) holds for some constants c ∈ (0, 1), α ≥ 0 and A > 0. Assume additionally that β t ≥ γ t for all t ≥ 0. Let β * t = min 0≤i≤t β i . Then the following statements hold.
(i) If α = 0, then we have γ t ≤ γ t for all t ≥ 0 and β * t ≤ γ (t+2)/2 for all t ≥ 2 max{1, A}/c, where
Consequently, we have Figure 3: Numerical results on a single random instance of problem ( 26) with m = n = 300, λ = 0.01, α = 2, and k = 5, 10, respectively. These sub-figures illustrate the behavior of the best relative Frank-Wolfe gap δ * t /δ 0 := min 0≤i≤t δ i /δ 0 and the relative function value ϕ(U t , V t )/ϕ(U 0 , V 0 ) with respect to CPU time in seconds.
(ii) If α > 0, then we have γ t ≤ γ t for all t ≥ t 0 and β * t ≤ (1 + α) 1 1+α γ (t+t 0 +1)/2 ≤ e 1 e γ (t+t 0 +1)/2 for all t ≥ t 0 + 2A/(cγ α t 0 ), where
Consequently, we have β * t ≤ ε whenever
Proof (i) Consider the case α = 0. By ( 27) and β t ≥ γ t ≥ 0 for all t ≥ 0, one can obtain for all t ≥ 0 that
and hence γ t ≤ γ 0 exp(-c min{1, A -1 }t) = γ t for all t ≥ 0. By this, {γ t } ⊂ R + , and ( 28) with α = 0, one has that for any k ≤ t,
For convenience, let T 0 = 2 max{1, A}/c and T 1 = max{1, A} log(γ 0 /ε)/c. For any t ≥ T 0 , letting k = (t + 2)/2 in (31), we obtain β * t ≤ γ (t+2)/2 due to
Hence, statement (i) holds.
(ii) We now consider the case α > 0. It follows from the relation γ t ≤ β t and the monotonicity of the sequence {γ t } that γ t ≤ β * t . As long as
Claim that β * t 0 ≤ A 1/α for t 0 defined in (29). Suppose for contradiction that β * t 0 > A 1/α . Then, as (32) holds for t = 0, . . . , t 0 , we have γ t 0 ≤ γ 0 exp(-ct 0 ) and thus γ t 0 ≤ cA 1/α follows by the expression of t 0 . However, since {γ t } is nonnegative, the first inequality of (32) implies β * t 0 ≤ c -1 γ t 0 ≤ A 1/α , which leads to a contradiction. Hence, β * t 0 ≤ A 1/α holds as claimed.
It follows from the monotonicity of {β * t } that γ t ≤ β * t ≤ A 1/α for all t ≥ t 0 . By this and (28), one can obtain the recurrence
Then, by (Borwein et al., 2014, Lemma 4.1), this recurrence implies the assertion
We next show that β * t ≤ (1 + α)
. It follows from the first inequality in (33) and the monotonicity of
Let k = (t + t 0 + 1)/2 . Observe that t -k + 1 ≥ k -t 0 . When t ≥ t 0 + 1, we have t ≥ k ≥ t 0 + 1 and thus γ k ≤ γ k holds from (34). By these relations, γ t+1 ≥ 0, and summing up the inequality (35) for i = k, . . . , t, one has
In view of this and the expression of γ t , we obtain that for all t ≥ t 0 + 1,
where
. Observe that θ k is non-increasing and θ k ↓ 1 as k → ∞. For convenience, let T 2 = t 0 + 2A/(cγ α t 0 ). Claim that θ k ≤ (1 + α) 1 1+α whenever t ≥ T 2 . Indeed, fix any t ≥ T 2 . By this and the expression of k, one can observe that k ≥ t 0 + A/(cγ α t 0 ), which along with the expression of θ k implies that θ k ≤ (1 + α) 1 1+α holds as claimed. Using this and (36), we conclude that
where the second inequality follows from (1 + α)
Finally, by the expression of γ t , one can see that the relation e 1 e γ (t+t 0 +1)/2 ≤ ε holds if t ≥ T 3 , where
It then follows that β * t ≤ ε holds whenever t ≥ max{T 2 , T 3 } and hence (30) holds. This completes the proof of statement (ii).
The following lemma establishes the weak smoothness of the function 1 p Ax -b p p for p ∈ (1, 2] which has been used in Section 5.
A p 2 and A 2 = max x 2 ≤1 Ax 2 .
By the convexity of g, and (39) with y = (1 -τ )x t + τ v t and x = x t , one can obtain that for any τ ∈ [0, 1],
Letting τ = τ t in (40), and using the expression of τ t and x t+1 , we obtain that for any t ≥ 0,
We are now ready to prove Theorems 5 and 7.
Proof of Theorem 5 Let the sequences {x t } and {v t } be generated in Algorithm 1. One can observe that x t , v t ∈ dom g for all t ≥ 0. It then follows that x t -v t ≤ D g . By this and Lemma 18, one can obtain
(i) It follows from (41) that {ϕ(x t )} is non-increasing, which, together with the fact that ϕ(x t ) ≥ ϕ * for all t ≥ 0, implies that ϕ * = lim t→∞ ϕ(x t ) exists. In addition, one can observe from (41) that the recurrence (27) holds for
. The inequality (12) then directly follows from Lemma 15. (ii) One can observe from (41) that the recurrence (27) holds for
. In addition, β t ≥ γ t due to Lemma 3. The conclusion of this statement then immediately follows from Lemma 16 (ii).
Proof of Theorem 7 Let the sequences {x t } and {v t } be generated in Algorithm 1. One can observe that x t , v t ∈ dom g for all t ≥ 0. By this, the expression of δ t , and Assumption 2, one has
Using this inequality, we can obtain that
, which together with (38) yields
(i) By ( 43) and a similar argument as in the proof of Theorem 5 (i), one can see that {ϕ(x t )} is non-increasing and ϕ * = lim t→∞ ϕ(x t ) exists. In addition, one can observe from (43) that the recurrence (27) holds for ν . Also, β t ≥ γ t due to Lemma 3. In addition, by ν ∈ (0, 1], ρ ≥ 2, and the expression of α, it is not hard to see that α = 0 if and only if ν = 1 and ρ = 2. Also, one can see from the expression of c and A that c = 1/2 and A = 2M 1 /κ when ν = 1 and ρ = 2. The conclusion of this statement then follows from these observations and Lemma 16.
In subsection, we prove Theorems 9, 10, and 12. Proof of Theorem 9 (i) For any τ ∈ [0, 1], by the convexity of g, the expression of δ t , and ( 15
Hence, (14) holds if
where the equality follows from the expression of τ (i)
t and the fact that L(•) is non-increasing. By (16), one can verify that
, In addition, from the proof of statement (ii), we can observe that L t ≤ max{L -1 /2, 2 L * t } for all t ≥ 0. Also, by the definition of i s , one can see that L s = 2 is-1 L s-1 for s ≥ 0, and the total number of inner loops performed by the adaptive line search procedure until the t-th iteration of Algorithm 2 is given by t s=0 (1 + i s ). By these observations, one can have
and hence the conclusion holds. Before proving Theorems 10 and 12, we establish a lemma that will be used shortly.
Lemma 19 Let the sequences {x t }, {δ t } and {v t } be generated in Algorithm 2. Suppose that Assumption 1 holds and that δ t > 0 for all t ≥ 0. Let t0 = (log 2 (L -1 / L 0 )) + , δ * t = min 0≤i≤t δ t , and L t and L(•) be defined in (17) and (18), respectively. Then it holds that
where
Proof One can observe from Algorithm 2 that
It then follows that
Recall from the proof of Theorem 9 (iii) that L t ≤ L(δ t ) for all t ≥ 0. Using this, Theorem 9 (ii), δ * t = min 0≤i≤t δ t , and the monotonicity of L(•), we have
The conclusion then follows from this, (49), and δ * t = min 0≤i≤t δ t .
We are now ready to prove Theorems 10 and 12.
Proof of Theorem 10 One can observe that x t , v t ∈ dom g. It then follows that x t -v t ≤ D g for all t ≥ 0. By this and δ * t = min 0≤i≤t δ i , one has
Let C t be defined in (48). We next bound C t from below by considering two cases in view of the definition of L(•) in (18).
Case
By this, ( 48) and ( 50), we obtain that
. By this, ( 48) and ( 50), one has
Combining these two cases, and using ( 18) and ( 48), we conclude that C t ≥ min{D t , D 2ν 1+ν t }. By this and 2ν/(1 + ν) ≤ 1, one can observe that min{1, C t } ≥ min{1, D t }, ∀t ≥ 0.
In view of this, (47), and the expression of D t , one has
where the last inequality is due to 2 1+ν 2ν ≤ 2 1+1 2ν and 1-ν 1+ν ≤ 1. (i) It follows from (49) that {ϕ(x t )} is non-increasing, which, together with the fact that ϕ(x t ) ≥ ϕ * for all t ≥ 0, implies that ϕ * = lim t→∞ ϕ(x t ) exists. In addition, one can observe from (51) that ( 27 Hence, β t ≥ γ t for all t ≥ 0. The conclusion of this statement then follows from Lemma 16 (ii).
Proof of Theorem 12 It follows from (42) and δ * t = min 0≤i≤t δ i that
Let C t be defined by (48). We next bound C t from below by considering two cases in view of the definition of L(•) in (18).
Parameter-Free Conditional Gradient Method
Case 1) L(δ * t ) = 2(1-ν) 1+ν
1-ν νρ . By this, ( 48) and ( 52), we obtain that
. By this, ( 48) and ( 52), one has
Combining these two cases, and using ( 18) and ( 48), we conclude that C t ≥ min{E t , E 2ν 1+ν t }. By this and 2ν/(1 + ν) ≤ 1, one can observe that min{1, C t } ≥ min{1, E t }, ∀t ≥ 0.
In view of this, (47), and the expression of E t , one has
where the last inequality is due to 2 1+ν 2ν ≤ 2 1+1 2ν and 1-ν 1+ν ≤ 1. (i) In view of (49) and ϕ(x t ) ≥ ϕ * ∈ R, the sequence {ϕ(x t )} is non-increasing and ϕ * = lim t→∞ ϕ(x t ) exists. In addition, one can observe from (53) that ( 27
In this paper we first analyzed iteration complexity of a parameter-dependent conditional gradient method for solving problem (1), whose step sizes depend explicitly on the problem parameters. We then proposed a novel parameter-free conditional gradient method for solving (1) without using any prior knowledge of the problem parameters and showed that it enjoys the same order of iteration complexity as the the parameter-dependent conditional gradient method. Preliminary numerical experiments demonstrate the practical superiority of our parameter-free conditional gradient method over the other variants.
It shall be mentioned that our proposed method requires a pre-specified norm and thus it is norm-dependent. In contrast, some existing conditional gradient methods (e.g., Jaggi, 2013;Lacoste-Julien, 2016;Peña, 2022) are norm-independent. It would be interesting to develop a parameter-free but norm-independent conditional gradient method achieving the same complexity bounds as obtained this paper for solving (1). This is left for future research.
For the case ρ = 2, the function g is a usual strongly convex function with modulus κ.