CCCP is Frank-Wolfe in disguise
Authors: Alp Yurtsever
Suvrit Sra
Venue: NeurIPS 2022 Accept (2022)
Keywords: convex-concave procedure
cccp
frank-wolfe
conditional gradient method
difference of convex programming
expectation maximization
sinkhorn

Abstract: This paper uncovers a simple but rather surprising connection: it shows that the well-known convex-concave procedure (CCCP) and its generalization to constrained problems are both special cases of the Frank-Wolfe (FW) method. This connection not only provides insight of deep (in our opinion) pedagogical value, but also transfers the recently discovered convergence theory of nonconvex Frank-Wolfe methods immediately to CCCP, closing a long-standing gap in its non-asymptotic convergence theory. We hope the viewpoint uncovered by this paper spurs the transfer of other advances made for FW to both CCCP and its generalizations.

CCCP is Frank-Wolfe in disguise
Alp Yurtsever
Suvrit Sra Massachusetts Institute of Technology suvrit edu
Umeå University alp. www.ustrreeruuu..eee
Abstract
This paper uncovers simple but rather surprising connection: it shows that the well- known convex-concad procedure (CCCP) and its generalization to constrained problems are both special cases of the Frank- Wolfe (FW) method. This connection not only provides insight of deep (in our opinion) pedagogical value, but also transfers the recently discovered convergence theory of nonconvex Frank-Wole Wolfe methods immediately to CCCP, closing long-standing gap in its non-asymplotic convergence theory. We hope the viewpoint uncovered by this paper spurs the transfer of other advances made for FW to both CCCP and its generalizations.
Introduction
We study non-convex difference of convex (DC) optimization problems of the form:
min f(x) g(x);
x E D,
(1.1)
where both f and g are convex functions and D is a constraint set that might itself be non-convex (we will specify its structure later). Throughout, assume that the optimal value f* 9" is finite.
Formulation (1.1) is a DC program. When f and g are smooth, powerful local method is Convex- Concave Procedure (CCCP) [Yuille and Rangarajan, 2003] that reduces (1.1) to sequence of convex also widely applicable and numerous
problems. CCCP is not only algorithmically appealing. algorithms can be viewed as special cases of CCCP, most notably the famous EM algorithm- see [$4 Yuille and Rangarajan, 2003].
But despite its wide applicability (see $2.2) and elegance, convergence theory for CCCP is quite limited. Its asymptotic convergence can be obtained by viewing it as specialization of the DC algorithm (DCA) [Le Thi and Pham Dinh, 2018), or via more refined analysis designed for CCCP in [Lanckriet and Sriperumbudur, 2009]. A long-standing gap in the literature CCCP has been to obtain con-tsymptoiic convergence theory that establishes convergence to an e-stationary point in (pooyy11/e) fewer iterations.'
The starting point of this paper is discovery that is elementary yet surprising: CCCP is special case of the Frank- Wolfe (FW) method! This discovery not only provides insight of deep (in opinion) pedagogical value, but also transfers the convergence theory nonconvex FW to CCCP which closes the abovementioned gap in CCCP's non-asymptotic convergence theory.
1.1 Main contributions
In light of this short background, we summarize now the key contributions of this paper.
We recognize the basic (unconstrained) CCCP method to special case Frank-Wolf By the same argument, even its generalization to convex constrained instances of (1.1) is a special case of FW. This realization allows us immediately transfer non-asymptotic convergence theory of FW to CCCP and convex constrained CCCP.
We became aware of some recent discoveries on the non-asymptotic convergence of basic CCCP in AAbbaszadehpeivasti et al., 2021, Lê-Huu and Alahari, 2021] after completing this work-see Remark 3,4.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Building on the above connection, we subsequently propose a new variant of FW (called FW+) that applies to the most general form of CCCP (called CCCP+), where the constraint set D in (1.1) is specified via several DC constraints. The variant FW+ not only allows us to syntactically view CCCP+ as a special case, but more importantly allows us to transfer non-asymptotic convergence guarantees that we prove for FW+ directly to CCCP+.
While the FW+ variant and its analysis are slightly more subtle than basic FW, the connection between CCCP and FW uncovered by our work is remarkably simple. The introduction of FW+ itself is an immediate consequence of the connection uncovered. It is also quite plausible that the connections described in this paper will have various further consequences, including development of new variants of CCCP and other related methods. For a more concrete discussion of potential implications, see the discussion in $5.
Finally, we note few additional connections of the view uncovered in this paper in the appendix. In particular, we show that various other methods such as the proximal point method, mirror descent and mirror prox can also be seen as special instances of the FW method. A deeper exploration of these connections is left as future work.
1.2 Related work
FW. Frank and Wolfe [1956] proposed the FW algorithm originally for minimizing a convex quadratic function over a polyhedron and proved O(k-1) convergence rate in this setting, Levitin and Polyak [1966] extended the analysis and proved the same rate for minimization of an arbitrary smooth convex function over generic convex compact set, and Canon and Cullum [1968] showed that this rate is optimal. The analysis is extended for broader Hölder-smooth function class by Nesterov [201 8). Jaggi [2013] presented an affine invariant analysis for the FW algorithm by replacing smoothness with the bounded curvature assumption, see (2.3). The analysis of FW for non-convex functions appeared in [Lacoste-Julien, 2016]-the method finds a stationary point as the gap function converges to zero with (k-21/2) rate, see (2.4) for the gap function. It is easy to show that the rate improves to O(k-) for mininization of a concave function, see Lemma 2.1. An application of the FW algorithm to minimization of a concave function appears in [Luss and Teboulle, 2013].
Design variants of FW with away, pairwise, or in-face steps and line-scarch or momentum strategies; and extensions of FW for stochastic gradients or block-coordinate updates are extensively studied in the literature. We refer to [Kerdreux, 2020] for an excellent overview on these recent developments. To our knowledge, the variant FW+ introduced in this paper is new.
CCCP. The CCCP method of Yuille and Rangarajan [2003] is special case of the more general DC algorithm (DCA) [Tao, 1997, Le Thi and Pham Dinh, 2018 10... CCCP often provides strong baseline method for tackling non-convex problems where DC structure is already known or relatively easy to obtain- see [Lipp and Boyd, 2016] for some recent variations on the CCCP method. As already noted, asymptotic convergence of CCCP follows from the more general convergence theory of DCA [Tao, 1997], while simplified, more direct convergence analysis was obtained in [Lanckriet and Sriperumbudur, 2009], who analyzed convergence of both function values and iterates; moreover, these convergence results apply to the most general CCCP+ formulation (DC objective with DC constraints). A more recent work [Khamaru and Wainwright, 2018] considers gradient and subgradient based alternatives to DCA and CCCP, establishing their corresponding non-asymptotic convergence; however, its focus is on alternatives and its guarantees do not transfer to CCCP, and thus a fortiori not to CCCP+ Both CCCP and DCA have received large number of applications, in a variety of areas including statistics, machine lcarning, signal processing, operations research, and many more-we we refer the reader to the extensive list documented in the survey [Le Thi and Pham Dinh, 2018] and to examples in [Yuille and Rangarajan, 2003].
We became aware of some important items of related work in the recent literature after completing this work. (Abbaszadehpeivasti et al., 2021] proposes non-asymptotic convergence guarantees for unconstrained DC optimization. Their analysis is based on the performance estimation technique [Drori and Teboulle, 2014], which is a computer-assisted methodology for estimating the worst-case complexity of an algorithm by solving semidefinite programs. They conjecture the convergence guarantees through systematic numerical experimentation and then analytically verify them. Their proof provides limited insight and does not extend to the more general constrained settings.

---

The closest in relevance to our work is [Lê-Huu and Alahari, 2021]. The authors therein recognize the connection between CCCP and FW from a conceptually different viewpoint and show that the unconstrained CCCP is a special instance of the generalized FW studied in [Bredies et al., 2009]. Generalized FW an extension FW for solving composite optimization problems through partial linearization leading to modified FW subproblem. Although not identified explicitly before, generalized FW is algebraically equivalent to the original FW applied to an epigraph reformulation in the context of CCCP. We independently discovered the connection between CCCP and FW through the lens this epigraph reformulation.
We emphasize the value of our conceptual perspective: the epigraph reformulation allows us to transfer existing guarantees of FW to CCCP without having to perform new convergence analysis for the unconstrained and convex constrained CCCP case. We further expound this connection and develop to the DC constrained setting for CCCP+, leading to the discovery of FW+ as natural extension of the FW method for functional constraints. Our FW+ analysis gives the first non-asymptotic convergence guarantees for the CCCP+ We further observe that the proximal point method (PPM), mirror descent, and mirror prox are also special cases of FW applied to suitable epigraph reformulation, see Appendices and B. Since we reduce PPM to FW, and many other optimization methods reduce to PPM, all these methods are inherently special instances of FW.
2 Background on Frank- Wolfe and CCCP
2.1 Frank-Wolfe Algorithm
We begin by recalling the basic Frank-Wolf method (FW) and some of its key properties. We focus in particular the nonconvex case, it is key to the rest of our theory. Consider therefore the prototypical constrained optimization template:
min
(w s.t. WED,
(2.1)
where D is closed and convex set in R" and e is continuously differentiable (potentially nonconvex) function over the domain D. FW applied to (2.1) performs the following steps for k: 1,...
wi E argmin ((wx) + (V (ol(w)) w -wk).
WED
(FW)
wk+1 = (1 Th )w + maa
where 77 E J0, 1] is step-size. There multiple design choices for the step-size. A common choice is the greedy step-size
argmin s((1 - ()w + mww))
(2.2)
nE|0,1]
The standard convergence theory FW crucially depends on the boundedness curvature constant of & over D. defined as follows:
(d()) - )(w) (Vol)), a --w)) -wi)
C == W D. [0
(2.3)
172
@= (1(1)))w+m
The bounded curvature assumption is closely related to the Lipschitz smoothness assumption. If Vg is L-LLipschizz continuous and the domain D has bounded diameter D. then Co < LD2 However, the former more general. For instance, it is easy to see that C. = 0 if & is concave. This becomes useful in our analysis later in this paper, and allows us to derive guarantees without any Lipschitz smoothness assumption on the functions involved and without an explicit assumption on the boundedness of the domain.
Φ convex and C is bounded, then the sequence {uk)k20 generated by (FW) converges to a solution in objective value (see e.g., [Jaggi, 2013, Theorem 1]); where the convergence rate is
2C
((wx) 0- < 1+1 where o² min ((w). wDD
When ó is non-convex, (FW) can be shown to find a stationary point [Lacoste-Julien. 2016, Theo- rem 1]. with the following guarantee: there exists an index [k), such that
max (Co, 2(0(w)) - x³)}
(Vo(ur), wr - w/ s
Ye E D.
Vk
3

---

This bound is often presented in terms of the so-called ga-g
(w,) := max (Vo(u=), Wr w) - (Vo(wr), Wr w/). WED
(2.4)
This quantity naturally arises in the FW algorithm and its analysis, and provides a reliable stopping criterion.
In our analysis, we particularly need apply FW to concave objectives. In this case, (FW) exhibits better convergence rates than general non-convex costs. More precisely, we note the following result.
Lemma 2.1. Suppose that the sequence {wi} generated by the FW method with greedy step-size (2.2) applied to Problem (2.1) with a concave objective. Then, there exists E [k)], such that
(Vo(wr), wy w) Φ(w1) o²
Vw E D.
k
Proof. First, observe that = 1 in (2.2) when Φ is concave. Then, (FW) becomes Wh+1 E argmin <(wx)= + (Vo(w)), w - www) 8. t. w E D.
By concavity of o, we have max WED
(Vo(wn): We - ww = (Vo(ur), We - wk+1) S ((wu)) - o(WR+1).
(2.5)
Then, averaging (2.5) over k gives
I (Volwi), wi w) S b [(((w)) 2.).
max
(2.6)
WED
We conclude the proof by noting that the minimum over k is less than or equal to the average.
2.2 The Convex-Concave Procedure (CCCP)
The starting point for the Convex-Concave Procedure (CCCP) of Yuille and Rangarajan [2003] is the unconstrained DC program
min f(x) g(x),
(2.7)
where both f and g are C'l (once continuously differentiable) convex functions; CCCP can also be viewed as a special case the more general DCA algorithm (Tao,, 1997] that does not require differentiability. The key idea behind the success of CCCP is the convexity of g(rr) linearize and obtain the following global upper bound on f(xx) g(x):
Q):;) == f(x) g g x - v)-
(2.8)
At each iteration, CCCP then updates its guess by solving the convex problem
Øb+1 E argmin Q(æ;xz).
(2.9)
solution to (2.9) always exists because f - g" is finite by assumption and min Q(=; 2 min f(x) g(x) = f" -9" g"
(2.10)
CCCP is thus a specific Majorize Majorize-Minorize Minorize (MM) algorithm [Hunter and Lange, 2004], and owing to the update (2.9), it generates a monotonically decreasing sequence {f(xx) - g(x))) 1220 of objective
values. When f is differentiable, update (2.9) is tantamount to the implicit update
f((++1) Vg(xz).
(CCCP)
Note that the subproblem (2.9) is convex optimization problem that does not approximate the function fx), and thus likely offers a tighter approximate model to the DC cost (2.7), an aspect that might help explain its strong empirical performance [Lipp and Boyd, 2016].
The original CCCP paper [Yuille and Rangarajan, 2003] presented various important applications that could be viewed through the CCCP lens, of which perhaps the EM algorithm [Dempster et al., 1977] and Sinkhorn's 's method for matrix scaling [Sinkhorn, 1967] two very familiar special cases. A formal study of CCCP's asymptotic convergence properties was undertaken in [Lanckriet and Sriperumbudur, 2009], who studied all three variants: unconstrained CCCP, convex constrained, as well DC constrained CCCP.

---

Unconstrained CCCP and convex constrained CCCP via FW
Our first result shows that CCCP can be viewed as a special case of the FW method.
Proposition 3.1. CCCP is equivalent to the FW method applied to the following epigraph reformula- tion of Problem (2.7):
min 1 (-9(z)
S. f(x) S.
(3.1)
Proof. If we apply FW to (3.1), the linear minimization step is
E
arg min (z,()
t (V x) s.t. f(z) St.
(3.2)
KKT conditions are necessary and sufficient for optimality in Problem (3.2) since it convex optimization problem and the Slater's condition holds. The Lagrangian of this problem is
((x,4, 4, A) (Vg(ss), 2) ((((x) 1).
Lagrangian stationarity condition implies
VoL(I,t, t= = Vg(()) + =0 vf(xt) -Vg(z))
(3.3)
v,l(x,t, s=ri,t=t = =1-1=
We also get t = f(a)) ) by the complementary slackness condition.
Finally, FW updates its estimate via
Ik-1 (1 > + m- 1x+1 (1 TT)4 + muli
where 7is E [0, 1] is chosen to minimize the objective function in (3.1). Since this function is concave, ? 1, and conclude that the linear system in (3.3) is exactly the CCCP subproblem.
Proposition 3.1 recognizes a simple derivation of the CCCP update- reformulate the unconstrained convex set and apply FW. This recognition transfers
DC program concave minimization the convergence theory of FW to CCCP as we present in the next corollary.
Corollary 3.2. Suppose that the sequence {1x) is generated by (CCCP) applied to Problem (2.7). Then, there exists E [k), such that
1 f(x,) f(x) (Vg(z)), x+ - x) S (f(x)) gg(1)) -f') for all x.
Proof. By Proposition 3.1, CCCP equivalent FW applied to (3.1). Observe that (3.1) is an instance of (2.1) with w = (x, t), Φ(w) t- g(x), and D {(x, t) f(x) I f). Since ó is concave, we can use Lemma 2.1. Hence, there exists [k], such that
(t1 - g(x1)) gg)
4, - (Vg(x,), T4 1 x) S
V(a, t) f(x) St.
k
1" 1" by definition, ( =f(x1) by initialization, and 4, f(x+) by complementary slackness, see the proof of Proposition 3.
Corollary 3.2 establishes non-asymptotic convergence guarantees of CCCP to a stationary point of the unconstrained DC program (2.7). Remarkably, this result does not require any assumptions the Lipschitz-smoothnes of the functions or an explicit assumption on the boundedness of the domain.
The main result in Corollary 3.2 is based the variational inequality characterization of first-order stationarity. Similar measures are used in the literature for various problems [Yurtsever et al., 2021]. The next lemma clarifies the value of this stationarity condition.
Lemma 3.3. A point x² is first-order stationary point of Problem (2.7) if
f(x") f(x) (Vg(x"), x- - x) s 0 for all x.
(3.4)
5

---

Proof. By definition, the point x² is first-order stationary if
(Vf(z") Vg(x"), x² - x) S for all æ.
(3.5)
Since is convex, [(x*) (ax) S (VI(x*); x² -)), and (3.5) immediately implies (3.4).
Next, we show (3.5) implies (3.4) as well. Suppose (3.4) holds and consider x = x² + as for an arbitrary direction and step-length
0:
f(z + as) - - (Vg(z"),
-Vg=")((V((""")) as) 2 0.
We divide both sides by a and take the limit as -> 0+:
lim f(x* + as) as) f(x")
(Vg(>"), s) = -V
8) 2
a-0++
a
Finally, we arrive at (3.5) by substituting a In conclusion, (3.4) and (3.5) are equivalent for Problem (2.7).
- (x - x²).
Remark 3.4 (Comparison with the existing results). There are two other recent works that provides non-asymptotic convergence guarantees for CCCP the unconstrained setting.
1. Abbaszadehpeivasti et al. [2021] present two main results:
(i) Under the assumption that at least one of the terms, f or y is smooth, they show
min ||l, u, ll & O(L/Vk) T
where Uy E (xx, and u, E Ōg(x,).
(ii) For the non-smooth setting, they show
min max (f(x)) f(x) (ur, 24 - x}} S (1/kk) where Ur E 0g(x+).
rE(R)
This second result matches our guarantees in Corollary 3.2. As we also note above, Corollary 3.2 does not require any assumption on the smoothness, and holds with subgradients as well.
2. Lê-Huu and Alahari [2021] provide convergence guarantees for the generalized FW algorithm [Bredies et al., 2009] in the non-convex settings. Moreover, they identify CCCP as special instance of generalized FW. As a result, the guarantees that they present for the 'concave f setting (which corresponds to the DC template) in Theorem in their paper is equivalent our Corollary 3.2.
Intriguingly, in this setting, the generalized FW algorithm itself algebraically equivalent to the standard FW applied to the epigraph reformulation (3.1). This recognition, although it seems simple, interesting on its own right because the recent literature on FW habitually associates the algorithm with optimization convex, closed and bounded domains. Nevertheless, the bounded domain assumption can be relaxed without losing the guarantees, as
VW D, min (V (W)), w)
is bounded below.
(3.6)
W
In other words, the linear minimization subproblem is well-defined everywhere in the domain. As an interesting fact, Frank and Wolfe [1956] use assumption (3.6) in their original work and not restrict their algorithm for bounded domains, see Hypothesis A in their paper. Assumption (3.6) trivially holds if D is bounded but not vice versa. It is easy show that assumption (3.6) is satisfied in Proposition 3.1 since
min t- (Vg(t), x) 2 min f(x) (V)(.), f()st
min f(x) g(x) ((0) + (Vg(+), #)
ʃ g (Vg(e),
and f* -g" is finite by the blanket assumption.

---

3.1
Convex constrained CCCP via FW
Here the problem of interest is:
min -(x),, s.t. x DED,
(3.7)
for closed convex set D. We can equivalently write this problem
min f(z) + xD(x) g(z),
(3.8)
where Xx(()) denotes the indicator function of D. Since h := f + XD convex, we can apply the same idea as for the unconstrained case by looking at the equivalent problem
min 2,(
L g(r); s.t. h()) S.
(3.9)
we apply FW to (3.9), the linear minimization step involves solving
min (Vg(zz), 2), s.t. f(x) + xD(x) St.
(3.10)
which is clearly equivalent to solving
min
f(x) - (Vg(zx), x), s.t. *ED.
(3.11)
Subproblem (3.11) is precisely the update convex constrained CCCP
4 CCCP with difference of convex constraints via FW
At this point, it natural to wonder whether the most general version of CCCP also admits a natural FW interpretation? Consider therefore the DC programming problem with DC constraints:
min x
fo(x) - -o( s.t. f((x) (x) S 0, i 1,....m.
(4.1)
Motivated by the applications in Gaussian processes and support vector machines with missing variables, the advanced CCCP for Problem (4.1) is introduced in [Smola et al., 2005, Theorem 1]. This method updates its estimation solution of the following subproblem:
min fo(x) go(#x) (V x -x
I s. f((x) - (zx) - (TK) x - xR) S O, i I....,, m.
(CCCP+)
A large body of DC programming literature focuses on template (), or even more general versions of it. To name few examples, [Fardad and Jovanović, 2014] studies this template for finding optimal feedback gains in the presence of structural constraints, and [Tao et al., 2016] uses it for solving content-centric sparse multicast beamforming. [Lipp and Boyd, 2016] focuses on the same template and provides discussion on the applications, also introducing several extensions and variations of CCCP+ (e.g., with line-search). [Shen al., 2016] proposes a structured way to formulate and handle problems as DC programs with DC constraints, called disciplined convex-concave programming (DCCP). DCCP is generic framework which covers the boolean linear program, boolean least squares, and quadratic assignment problem special instances. DC programming has long history, beyond the references we cite above, we refer to [Le Thi and Pham Dinh, 2018) for an overview.
There is major challenge to make natural connection between CCCP+ and FW: The feasible set of (4.1) is non-convex, and the feasible sets for (4.1) and (CCCP+) are not the same. As a result, it seems impossible to write CCCP+ as a special instance of the standard FW method. However, searching for connection between CCCP+ and FW leads us to the discovery of more general form of the FW method itself that we call FW+, This method is obtained by linearizing constraints along with the objective function, and it recovers CCCP+ as a special case while remaining amenable to transparent FW-style convergence analysis.
7

---

4.1 Extended FW algorithm
Here the problem template:
min
((w) s.t. (i(w) s 0,
i= m,
(4.2)
WDD
where D is closed and convex set in R" and ø and de are continuously differentiable functions with bounded curvature.
The FW+ steps for Problem (4.2) are as follows:
w E argmin ((w)) + (Vo(we), w - wk);
WED
S. t.
4/ (ww))) + (Vel(we): w - wk) 50, i= 1=.....,
(FW+)
wk+11 = (1 - wu + m
Here, we focus on setting where both á and sb are concave. In this setting, we can choose 1. We defer more general discussion on FW+ for other settings to an extension this paper.
Theorem 4.1. Suppose that the sequence {wx} is generated by the FW+ algorithm for Problem (4.2)
with concave functions & and v. Then, there exists an index E [k], at which (w(,)) S 0 for i 1.... m, and
(Vo(wr); wy - -w) < ((w1) - -0²
Va E n (w e D: (w, S 0},
(4.3)
where (/(w,,)) vb((+)) (V))) w+).
Proof. First, we focus on the constraint function vh. By concavity, for all i, vb+(w++1) S (wx) + (Vir(we), wk+1 wx) S O,
where the last inequality follows from the constraint the linear minimization step of FW+,
Similarly, by concavity of é, we have
(Vo(ux), we wh+1) S 6(wx) - ((wx+1).
Averaging this inequality over ls gives
1 T
Volwe) w141)= S p(w1) - ((Wk+1)
p(wr) 0²
k
where the second inequality holds since wh+1 is in restriction of the feasible set of (4.2). Then, there exists an index E [k). at which
(Volw,), wr+1) ((w)) - 0*
k
This inequality leads to (4.3) by definition of wy+1 = w in (FW+).
Before moving on, characterize stationary points of Problem (4.2) in the next lemma. This gives clear interpretation of the bounds in (4.1) l) as perturbation of the stationarity condition.
Lemma 4.2. Consider Problem (4.2) and assume & and i are concave. Then, w" R is a feasible stationary point of Problem (4.2) if
w D and (x(ww) 50, =i= l==..... L....,m. m.
(fcasibility)
(Vo(w*), w w²) 20 Ae N ( D: "lw,w") 0}
(stationarity)
where Vl(w, = vi(ww) + (V)( w*)

---

Proof. Let's note that ()(w) I Vil w") due to concavity, therefore the set considered for the stationarity condition in Lemma 4.2 is restriction of the feasible set. The lemma implies that this restriction contains all feasible directions at w". Here is simple proof.
First, suppose that that the conditions in Lemma 4.2 satisfied w" and the inequality constraint is (w=) 0. Assume that there exists a direction d I2" such that == w ad is feasible for small enough a > and that is descent direction, (V (V((")) ), d) < O. By the stationarity condition in Lemma 4.2, this implies either & D or ( w > The former clearly contradicts our feasibility assumption. Suppose the latter holds, then we get (V", d) > O, meaning that d is an ascent direction for th at w". This also contradicts our feasibility assumption constraint is active and is an ascent direction, hence is directed outwards from the feasible region. By contradiction, we conclude that there is no feasible descent direction w"
active, i.e., (.( = 0. Then, J is also active since ("(W"""))
Next, suppose the constraint is inactive. This means v/ is also inactive as vi( ([W"".W) _w") (1("") < 0. Then, we can place an open ball B(w*) of infinitesimal radius centered wt such that (1, w²) for all points in ((w"). This implies (Vo(w"), w w²) 2 0 for all w E "DB((w") by the stationarity condition in Lemma 4.2.
FW+ is natural extension of FW with extensively broader applications. Theorem 4.1 and Lemma 4.2 together imply that FW+ provably finds a stationary point of Problem (4.2) under the concavity assumptions with non-asymptotic convergence guarantees. We complement this result in Appendix by deriving convergence guarantees of FW+ when é and y are convex. Importantly, FW+ can be used for finding stationary point of QCQP (quadratically constrained quadratic program) by solving sequence of linear programs.
4.2 CCCP+ via FW+
We are ready to establish the connection between CCCP+ and FW+ by following similar ideas as in Section 3.
Proposition 4.3. CCCP+ is equivalent to the FW+ method applied to the following epigraph reformulation of Problem (4.1):
min
to fol0)(>)
s.t. f1(z) S t4p i= 0.1...., g1(2) 2 t, i= 1...., m.
(4.4)
Proof. Problem (4.4) is special case of (4.2) with
(z, to ... fm), ((w)= to (o(),, vi = - and D (w f((x) S tt..
We consider FW+ for (4.4). Since & and the are concave, we can use 7/k- and the (FW+) procedure accounts to solving
min fo bm
to - (0-9((x)) -VV(=))(V x xxr
s.t.
f((x) S ti
0, I....,
4 g: (xx) - (Vg.( I - xn) 50 i= 1, 1,2, 1,2.....
which is clearly equivalent to the (CCCP+) subproblem.
This connection also transfers the convergence theory of FW+ to CCCP+ Corollary 4.4. Suppose that the sequence {xx} is generated by (CCCP+) applied to Problem (4.1). Then, there exists an index T E [Re), such that
1 x (1o(z)) -90(2))) - (Jō :5)). -x) -((o))((VVV((+)))))))
fo(x)) So(x) (Vgo(Et), xr
for all x that satisfies f((x) - (x())) (1,))g;(07))
(Vgi(z)), x - xx,) S 0, = 1, 2, ..., m.

---

Proof. By Proposition 4.3 and Theorem 4.1, we get
tor to (V 2, xx S k
1
-to.1- - (to - (96)
for all (x, to.................. .........m fm) that satisfies
f() S tip
i= 0, ...... m i= 1........ . m.
t, (x+) (Vgi(ar), x --277 xT) S 0,
This is equivalent to the desired bounds by eliminating to, tyy..,, fm in these formula.
Implications and Discussion
Discussion. We reiterate an important aspect of the -snasptpi convergence guarantees proved for CCCP and CCCP+ in this paper. Owing to the special structure involving minimization of concave functions, the convergence rates are independent of the curvature constant of FW (see (2.3)). This property valuable since delivers a convergence analysis of CCCP without imposing usual L-- smoothness assumptions on either f' or 9 or their difference f 9. limitation that typical first-order methods impose. While surprising at first sight, we can reconcile with this intuitively because CCCP requires solving an optimization subproblem (2.9), which is stronger oracle than merely gradient oracle for f - g. The ensuing faster convergence (i.e., tighter bound on the rate) may offer one explanation to the intuitive view on why CCCP can often be quite competitive [Yuille and Rangarajan, 2003, Lipp and Boyd, 2016].
Implications. Beyond generic convergence guarantees and the transfer of other progress on FW to CCCP, we note some specific implications worth further study here. The EM algorithm is a special case of CCCP [Yuille and Rangarajan, 2003, $4], and therefore a special case of FW. Thus, one should be able to develop a more refined understanding of global iteration complexity of EM, as well as sharper local convergence properties. Given the large number of settings in machine learning and statisties where the EM algorithm, or more generally, variational methods [Blei et al., 2017] are used, a further deepening of their relation to FW-methods should prove fruitful. Similar implications about algorithms, convergence, and complexity apply to other instances of CCCP that have been studied, notably for problems such as matrix scaling [Sinkhorn, 1967].
Extensions. The connection established between FW and CCCP (FW+ and CCCP+) paves the path for numerous extensions that are worthy pursuing. We hope our work motivates others to pursue some of these other extensions that these connections can inspire
The first important extension worthy study to obtain stochastic variants of CCCP by building on the recent progress on non-convex stochastic FW [Reddi et al., 2016b] well as non-convex variance reduced versions the case of finite-sum problems [Reddi et al., 2016a, Allen-Zhu and Hazan, 2016, Yurtsever et al., 2019].
Another line of research worthy of closer attention is study the case where either g is non- differentiable, or even both f and in (1.1) are non-differentiable. In that case, developing an extension of the relation between FW and CCCP to a relation between nonsmooth FW [Thekumpara- mpil et al., 2020] (although, as of now this nonsmooth FW method is limited to convex problems) and DCA should also prove to be fruitful, given the extensive progress DCA has witnessed over the decades [Le Thi and Pham Dinh, 2018]. The case where f(x) is an indicator function of convex set already fits trivially, as already discussed above. One might also speculate that progress on DCA could be transferred back to discover and develop nonsmooth FW methods.
Finally, given that both DCA and CCCP are special instances of MM methods [Hunter and Lange, 2004], it is possible that other MM methods might be profitably viewed as instances of an optimization procedure (not necessarily FW) whose geometric and convergence properties are better understood. We hope our work inspires the discovery of additional such connections.
Acknowledgments
Alp Yurtsever received support from the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation. Suvrit Sra acknowledges support from the NSF CAREER grant (1846088) and the NSF CCF-21 (TILOS AI Research Institute).
10

---

References
Hadi Abbaszadehpcivasti, Etienne de Klerk, and Moslem Zamani. On the rate of convergence of the differennce-o--convex algorithm (dca). arXiv preprint arXiv:2109.13566 2021.
Zeyuan Allen-Zhu and Elad Hazan. Variance reduction for faster non-convex optimization. In International conference machine learning, pages 699-707. PMLR, 2016.
David M Blei, Alp Kucukelbir, and Jon D McAuliffe. Variational inference: A review for statisticians.
Journal of the American statistical Association,
877,
Kristian Bredies, Dirk A Lorenz, and Peter Maass. generalized conditional gradient method and its connection an iterative shrinkage method. Computational Optimization and applications, 42(2): 173-193, 2009.
Michael D Canon and Clifton D Cullum. A tight upper bound the rate of convergence of frank-wolfe algorithm. SIAM Journal on Control, 6(4):509-516, 1968.
Arthur P Dempster, Nan M Laird, and Donald B Rubin. Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society: Series B (Methodological) 39(1):
1-22, 1977.
Yoel Drori and Marc Teboulle. Performance of first-order methods for smooth convex minimization: novel approach. Mathematical Programming. 145(1):451-48)) 2014.
Makan Fardad and Mihailo R Jovanović. On the design of optimal structured and sparse feedback gains via sequential convex programming. In 2014 American Control Conference, pages 2426- 2431. IEFF, 2014.
M. Frank and P. Wolfe. An algorithm for quadratic programming. Naval Research Logistics Quarterly, 3(95, 1956.
David R Hunter and Kenneth Lange. A tutorial MM algorithms. The American Statistician, 58(1): 30-37, 2004.
Martin Jaggi. Revisiting Frafk-Wolfe: Projection-free sparse convex optimization. In International Conference on Machine Learning (ICML), pages 427-435, 2013.
Thomas Kerdreux. Accelerating conditional gradient methods. PhD thesis, Université Paris sciences
et lettres, 2020.
Koulik Khamaru and Martin Wainwright. Convergence guarantees for a class of non-convex and non-smooth optimization problems. In International Conference on Machine Learning, pages 2601-2610. PMLR, 2018.
Simon Lacoste-Julien. Convergence Rate of Trank-Wolft for Non-Convex Objectives.
arXiv:1607.00344 2016.
Gert Lanckriet and Bharath K Sriperumbudur. On the convergence of the concave-convex procedure. Advances in Neural Information Processing Systems, 22, 2009.
D Khuê Lu-Huu and Karteek Alahari. Regularized frank-wolfe for dense crfs: Generalizing mean field and beyond. Advances Neural Information Processing Systems, 34:1453-1467, 2021.
Hoai An Le Thi and Tao Pham Dinh. De programming and DCA: thirty years of developments. Mathematical Programming, 169(1):5-68. 2018
Evgeny S Levitin and Boris T Polyak. Constrained minimization methods. USSR Computational mathematics and mathematical physics, 6(5):1-50, 1966.
Thomas Lipp and Stephen Boyd. Variations and extension of the convex-concave procedure. Opti-
mization and Engineering, 17(2):263-287, 2016.
Ronny Luss and Marc Teboulle. Conditional gradient algorithmsfor rank-one matrix approximations
with a sparsity constraint. siam REVIEW, 55(1):65 98, 2013.
B Martinet. Regularisation, d' d'inequations variationelles par approximations succesives. Revue Francaise d' d'Informatique et de Recherche Operationelle, 1970.
Yu Nesterov. Complexity bounds for primal-dual methods minimizing the model of objective function. Mathematical Programming, 171(1):311-333 2018.
Sashank Reddi, Ahmed Hefny, Suvrit Sra, Barnabas Poczos, and Alex Smola. Stochastic variance reduction for nonconvex optimization. International conference on machine learning, pages 314-323. PMLR, 2016a.
11

---

Sashank J Reddi, Suvrit Sra, Barnabás Póczos, and Alex Smola. Stochastic Frank- Wolfe methods for nonconvex optimization. In Communication, Control, and Computing (Allerton), 2016 54th Annual Allerton Conference on, pages 1244-1251. IEFE, 2016b.
Tyrrell Rockafellar. Monotone operators and the proximal point algorithm. SIAM journal on control and optimization, 14(5):877-898, 1976.
Xinyue Shen, Steven Diamond, Yuantao Gu, and Stephen Boyd. Disciplined convex-concans programming. In 2016 IEEE 55th Conference on Decision and Control (CDC), pages 1009-1014.
IEEE, 2016.
Richard Sinkhorn. Diagonal equivalence to matrices with prescribed row and column sums. The American Mathematical Monthly, 74(4):402-405, 1967.
Alex J Smola, SVN Vishwanathan, and Thomas Hofmann. Kernel methods for missing variables. In International Workshop on Artificial Intelligence and Statistics, pages 325-332. PMLR, 2005. Meixia Tao, Erkai Chen, Hao Zhou, and Wei Yu. Content-centric sparse multicast beamforming for cache-enabled cloud ran. IEEE Transactions on Wireless Communications, 15(9)6118-66) 6131, 2016.
Pham Dinh Tao. Convex analysis approach to DC programming: theory, algorithms and applications. Acta mathematica vietnamica, 22(1):289-355, 1997.
Kiran K Thekumparampil, Prateek Jain, Praneeth Netrapalli, and Sewoong Oh. Projection efficient subgradient method and optimal nonsmooth Frank- Wolfe method. Advances in Neural Information Processing Systems, 33:12211-12224 2020.
Alan L Yuille and Anand Rangarajan. The concave-convex procedure. Neural computation, 15(4):
915-936, 2003.
Alp Yurtsever, Suvrit Sra, and Volkan Cevher. Conditional gradient methods via stochastic path- integrated differential estimator. International Conference on Machine Learning, pages 7282- 7291. PMLR, 2019.
Alp Yurtsever, Varun Mangalick, and Suvrit Sra. Three operator splitting with a nonconvex loss function. In International Conference Machine Learning, pages 12267-12277. PMLR, 2021.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] The main contribution is the realization of a simple connection between CCCP and FW, clearly described in the title and abstract.
(b) Did you describe the limitations of your work? [Yes] The limitations and some future directions are discussed in detail in Section 5
(c) Did you discuss any potential negative societal impacts of your work? [No] The paper of theoretical nature and does not have an immediate societal impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] We explicitly state the full set of assumptions for all theoretical results.
(b) Did you include complete proofs of theoretical results? [Yes] Complete proofs are present in the paper, with some extensions and extra details in the appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "w-qz8cpcKo", "reviewer": "Reviewer_y2XT", "summary": "The paper studies the CCCP (convex-concave procedure through the lens of Frank-Wolfe.  Reframing CCCP as Frank Wolfe in epigraph reformulations, the authors provide some of the first non-asymptotic convergence results of CCCP to stationary points.  The work has results for an unconstrained setting, convex constrained setting, and generalizations of FW for DC constraints.", "questions": "Convex constrained analysis seems to subsume the unconstrained analysis without too much additional complexity.  Maybe it would be worth combining these?\n\nThe acronym MM is used in line 111 without Majorization Minimization.  Including this would help clarity.", "limitations": "The authors adequately addressed limitations of the work.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper finds a fundamental and elegant connection between CCCP and FW style algorithms which provide novel convergence bounds.\n- EM is a specific case of CCCP.  Further investigation fro insights in this paper may result in improved understanding of convergence of such methods.\n-  Paper is well written and contextualized well with related work.  Section F in the appendix does a good job of comparison to the closest related work. the more general analysis, connections to FW, and simpler analysis seem worthwhile even though some finite-time convergence results are known via [Abbaszadehpeivasti et al 2021].\n\nWeakness:\n- Notation could be a bit more consistent, for example Theorem 4.1 and Lemma 4.2 could both us $\\psi'$\n- More discussion on the stationary point notions for CCCP would be useful", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "pTyXhWgbpPi", "reviewer": "Reviewer_cenk", "summary": "This paper develops a novel equivalence between the convex-concave procedure (CCCP) for difference of convex (DC) programming and the Frank-Wolfe (FW) algorithm for minimization. The key idea is to show that CCCP is exactly FW applied to an epigraph reformulation of the original DC problem. Based on this equivalence, the authors are able to directly apply computational guarantees for non-convex FW (particularly, FW applied to concave *minimization*) to CCCP, yielding novel non-asymptotic convergence guarantees to a stationary point for CCCP. The equivalence also leads to several natural extensions including CCCP with convex constraints. The authors also consider a more intricate extension of CCCP involving DC constraints. To accommodate this, the authors develop an extension of FW -- called FW+ -- for dealing with concave minimization subject to concave <= constraints. Applying this algorithm to the appropriate epigraph reformulation of CCCP with DC constraints yields a natural extension of CCCP, called CCCP+, with similar non-asymptotic convergence guarantees as before.", "questions": "Despite the strengths listed above, still some steps can be taken to improve the quality of the paper. I outline my main comments/questions below.\n\n1. **Being more upfront about assumptions:** There are several implicit assumptions made in the paper (to my knowledge) that the authors should be more upfront about. I list these implicit assumptions below.\n     - $f^* - g^*$, which is the optimal value of the DC problem, is assumed to be finite (hence not unbounded)\n     - the above assumption implies that a solution to the CCCP subproblem always exists (authors should comment on this)\n     - Related, the fact that $\\phi^*$ is finite implies that the subproblem solutions always exist for FW in Section 2.1 (authors should comment on this)\n\n2. **The stationarity criterion in Corollary 3.2** To be honest, it took me some time to realize that Corollary 3.2 is at all interesting. The main reason for this is that the authors did not motivate or discuss the stationarity criterion on the LHS of the inequality. The authors should add some discussion and be careful about doing this in the revised version. In particular, I would suggest defining a formal stationarity measure, e.g., $G(x_\\tau)$ defined as the supremum of the LHS over all $x$. The authors should then add some discussion and perhaps a lemma justifying that this is an interesting stationarity criterion, i.e., the lemma should show that $G(x_\\tau) = 0$ implies that $x_\\tau$ is a stationary point of the DC problem. Such a lemma is very simple but not obvious to someone who is not readily familiar with DC programming. A result and some discussion along these lines -- currently there is none -- would strongly help to justify the value of Cor 3.2.\n\n3. Why is the CCCP problem setting and algorithm defined twice in Sections 2.2 and 3? The discussion should be consolidated and moved to one location.\n\n4. There seems to be a strong disconnect between CCCP+ and FW+ since FW+ deals with a *single* differentiable functional constraint and CCCP+ deals with multiple. This is not commented on as far as I can tell. Can FW+ be extended to multiple differentiable constraints so it can apply to CCCP+? (I suspect yes.)\n\n5. The simplicity of the proofs of Lemma 2.1 and Proposition 3.1 suggest that there should be a simple and **direct proof** of Corrollary 3.2. Is there? While I greatly appreciate the proof based on the equivalence with FW -- indeed that is the main point of this paper and how Cor 3.2 came about -- still a direct proof may add some clarity to the ideas as it helps to cement everything and remove any doubts. I think that adding a short alternative direct proof to the supplement (or at least a discussion) would add expository value to the paper.\n\n6. The authors say several times in several places that the analysis of FW considered -- in particular for concave minimization -- does not rely on the typical bounded curvature/Lipschitz smoothness assumptions. Another surprising fact is that it does not rely on a *bounded domain* assumption. (In a sense, this is included in the curvature part but is only obvious to an expert.) I would also add emphasis to this point, since in particular the domain for CCCP+ will be an unbounded epigraph, which is a non-traditional aspect of FW as well.\n\nMinor comments:\n\nThe paper is quite well-written and I did not find many typos. Still, I have the following minor comments:\n\n1. Line 56:  \"alternative\" -> \"alternatives\"\n2. Lemma 2.1 and line 99:  clarify in the statement of the Lemma that this is FW *with line-search*\n3. Line 111:  The acronym \"MM\" has yet to be specified\n4. Line 132:  The fact that KKT is necessary also requires a constraint qualification. In this case, Slater's condition will do.\n5. Line 226:  \"formula\" should be plural", "limitations": "The authors have discussed several limitations in Section 5 -- including e.g., that the results do not work directly for non-smooth problems -- and have appropriately left these extensions for future works. Discussion concerning potential negative societal impact is not applicable for this paper.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\n1. The main idea of this paper -- finding the right way to represent the DC problem so that CCCP is FW -- is novel, clear, and significant. On the surface it feels like a simple idea, but in my opinion this is a strength of the paper. The authors have cleverly uncovered a gap in the literature. To the best of my knowledge, the connection uncovered here is completely new. \n\n2. DC programming has emerged as a convenient class for modeling certain structured non-convex problems, yet the analysis of algorithms for DC programming is not nearly as developed as convex optimization. DC programming -- and also FW -- are quite important topics in the optimization literature with strong connections to ML. This paper takes a strong step forward in our understanding of the convergence and structure of DC algorithms. \n\n3. The direct implications of the equivalence are immediately developed by the authors. However, this paper has potential for longer lasting impact and may end up being quite significant. The connection between FW and CCCP uncovered allows the rich literature of FW analysis (which is mainly finite iteration convergence analysis) to be transferred to the DC literature (which is mainly asymptotic analysis). Ideas from DC literature may also have impact on FW. Additionally, as CCCP is related to others algorithms such as EM, there are potentials for even broader reaching impact as well. Quite simply the cross-cutting nature of this paper -- and it being the first such paper to draw a connection between FW and DC literatures -- makes it very significant to me.\n\n4. The paper is well written and the proofs are easy to follow. Again, the latter is a strength of the paper to me. To the best of my knowledge the proofs are mathematically correct. The paper is simply a pleasure to read.\n\n### Weaknesses\n\n1. Although the paper is written very well, the authors are (in my opinion) not careful enough regarding certain assumptions/definitions. Some simple fixes (which I outline in the next section) can help dramatically to overcome this weakness.\n\n2. Similar non-asymptotic convergence results for CCCP have appeared in [Abbaszadehpeivasti et al., 2021], which the authors point out in the supplement. Although this weakens the novelty of the implications of the connection, in my view this does not detract too much from the quality and novelty of this paper. The results of this paper are based on a novel structural connection between the two algorithms, and the proofs are very simple. These appealing connections and simple proofs are a strength not shared by [Abbaszadehpeivasti et al., 2021]. \n\n3. There are no numerical experiments. However, in my view this paper does not need them. They would be besides the main point of the paper. ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "NPzVR-zKHVX", "reviewer": "Reviewer_ubjs", "summary": "The authors propose an equivalence between two optimization methods: the convex-concave procedure (CCCP) and the Franke-Wolfe algorithm (FW). This equivalence is shown through an epigraphical lifting, resulting in a concave minimization problem that can be solved by the Frank-Wolfe algorithm with unit step size. This equivalence is shown to hold for unconstrained CCCP, convex constrained CCCP, and difference-of-convex constrained CCCP with various flavors of the FW algorithm with unit step size.", "questions": "Besides the FW+/CCCP+ method for difference-of-convex constrained CCCP, what novel contributions does the paper offer?", "limitations": "There is discussion of transferring convergence proofs from FW methods to CCCP, for instance there is even mention of possibly using nonsmooth FW to say something about CCCP. However, since all proofs I know of nonsmooth FW variants depend on the compactness of the constraint set, it's not obvious how these would transfer. In this way, the fact that CCCP is equivalent to an unbounded version of FW is itself a limitation that should be addressed in the paper.", "rating": 3, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I found the idea of the paper to be compelling, since connections of this sort usually offer a lot of insight into design and analysis of algorithms, but there is a question of novelty/originality that I will come back to. \n\nRegarding clarity, it should be stressed that this is not the ordinary FW algorithm, which usually requires the constraint set to be compact and the step size to decay like O(1/k) to prove convergence. Indeed, the constraint set D is not assumed to be bounded in the paper (nor can it be for the equivalence with CCCP to hold in general), yet at some points the diameter of the set D is used (i.e., line 85). \n\nThere are some questions about the novelty of the results of the paper, however, when it comes to analyzing FW with unit step size for minimizing a concave function. There is the work [Luss, Teboulle 2012] which analyzes ConGradU, a conditional gradient algorithm with unit stepsize to maximize a convex function over a compact set. The algorithm ConGradU is extremely similar to the algorithm analyzed here, except for the difference in compactness assumption, and should be discussed as a related work.\n\nIt also appears that the central idea of the paper, the equivalence between FW and CCCP, has already been published in NeurIPS 2021 [Lê-Huu, Alahari 2021] and was not cited. In their paper, there is a section that describes CCCP as equivalent to the generalized conditional gradient (equivalent to the epigraphical lifting given here) with unit step size. In light of this, it would seem that only the FW+/CCCP+ algorithms for dealing with difference-of-convex constrained CCCP problems are novel and, although interesting, do not seem significant enough on their own to justify publication here.\n\nFinally, I think it would be beneficial to include some sort of numerical experiment demonstrating the method FW+/CCCP+. Seeing the algorithm works in practice would improve the significance and quality of the paper as well.\n\n1. Regularized Frank-Wolfe for Dense CRFs: Generalizing Mean Field and Beyond - Đ.Khuê Lê-Huu, Karteek Alahari, 2021\n2. Conditional Gradient Algorithms for Rank-One Matrix Approximations with a Sparsity Constraint - Ronny Luss, Marc Teboulle, 2012", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept