Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: ### Strengths

1. 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. 

2. 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. 

3. 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.

4. 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.

### Weaknesses

1. 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.

2. 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]. 

3. 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. 
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.

1. **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.
     - $f^* - g^*$, which is the optimal value of the DC problem, is assumed to be finite (hence not unbounded)
     - the above assumption implies that a solution to the CCCP subproblem always exists (authors should comment on this)
     - 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)

2. **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.

3. 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.

4. 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.)

5. 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.

6. 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.

Minor comments:

The paper is quite well-written and I did not find many typos. Still, I have the following minor comments:

1. Line 56:  "alternative" -> "alternatives"
2. Lemma 2.1 and line 99:  clarify in the statement of the Lemma that this is FW *with line-search*
3. Line 111:  The acronym "MM" has yet to be specified
4. Line 132:  The fact that KKT is necessary also requires a constraint qualification. In this case, Slater's condition will do.
5. 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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths:
- The paper finds a fundamental and elegant connection between CCCP and FW style algorithms which provide novel convergence bounds.
- EM is a specific case of CCCP.  Further investigation fro insights in this paper may result in improved understanding of convergence of such methods.
-  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].

Weakness:
- Notation could be a bit more consistent, for example Theorem 4.1 and Lemma 4.2 could both us $\psi'$
- More discussion on the stationary point notions for CCCP would be useful
questions: Convex constrained analysis seems to subsume the unconstrained analysis without too much additional complexity.  Maybe it would be worth combining these?

The acronym MM is used in line 111 without Majorization Minimization.  Including this would help clarity.
limitations: The authors adequately addressed limitations of the work.
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: 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.
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. 

Regarding 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). 

There 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.

It 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.

Finally, 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.

1. Regularized Frank-Wolfe for Dense CRFs: Generalizing Mean Field and Beyond - Đ.Khuê Lê-Huu, Karteek Alahari, 2021
2. Conditional Gradient Algorithms for Rank-One Matrix Approximations with a Sparsity Constraint - Ronny Luss, Marc Teboulle, 2012
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.
review_title: null

Meta-review: metareview: Many reviewers have found that the paper contains many interesting elements and its theoretical derivations are solid. The paper is also very well written. There are some minor suggestions that could greatly help improve the quality of the final paper.  
confidence: Certain
Decision: Accept