Revisiting Frank-Wolfe for Structured Nonconvex Optimization
Authors: Hoomaan Maskan
Yikun Hou
Suvrit Sra
Alp Yurtsever
Venue: NeurIPS 2025 poster ()
Keywords: Frank-Wolfe
nonconvex optimization
difference of convex
gradient sliding
Primary area: optimization

Abstract: We introduce a new projection-free (Frank-Wolfe) method for optimizing structured nonconvex functions that are expressed as a difference of two convex functions. This problem class subsumes smooth nonconvex minimization, positioning our method as a promising alternative to the classical Frank-Wolfe algorithm. DC decompositions are not unique; by carefully selecting a decomposition, we can better exploit the problem structure, improve computational efficiency, and adapt to the underlying problem geometry to find better local solutions. We prove that the proposed method achieves a first-order stationary point in $\mathcal{O}(1/\epsilon^2)$ iterations,  matching the complexity of the standard Frank-Wolfe algorithm for smooth nonconvex minimization in general. Specific decompositions can, for instance, yield a gradient-efficient variant that requires only $\mathcal{O}(1/\epsilon)$ calls to the gradient oracle by reusing computed gradients over multiple iterations. Finally, we present numerical experiments demonstrating the effectiveness of the proposed method compared to other projection-free algorithms.

Revisiting Frank-Wolft for Structured Nonconvex Optimization
Hoomaan Maskan
Yikun Hou"
Suvrit Sra
Alp Yurtsever"
*Umeå University, Sweden Technical University of Munich, Germany
Abstract
We introduce a new projection-free (Frank-Wons method for optimizing structured nonconvex functions that are expressed as a difference of two convex functions. This problem class subsumes smooth nonconvex minimization, positioning our method promising alternative to the classical Frank-Wold algorithm. DC decompositions are not unique; by carefully selecting a decomposition, we can better exploit the problem structure, improve computational efficiency, and adapt to the underlying problem geometry to find better local solutions. We prove that the proposed method achieves first-order stationary point in O(1/e²) 2) iterations, matching the complexity of the standard Frank-Wolfe algorithm for smooth non- convex minimization in general. Specific decompositions can, for instance, yield gradient-efficient variant that requires only (1) calls to the gradient oracle by reusing computed gradients over multiple iterations. Finally, we present numerical experiments demonstrating the effectiveness of the proposed method compared to other projection-free algorithms.
1 Introduction
We study projection-free (Frank-War Wolfe) algorithms for nonconvex optimization problems of the form:
min xx))== 9(x),
where D C Rdd is convex, compact set, and the objective function D TR. is the difference of two convex functions D + IR and g D + IR. We assume that f is Ly-smooth on D (i.e., its gradient is -Liischhitz continuous) while g may be nonsmooth.
At first glance, the difference--f-coovvex (DC) structure may seem like a restriction for nonconvex Frank-Woll (FW) methods; but the opposite true. FW primarily designed for smooth objectives (Frank & Wolfe, 1956; Jaggi, 2013). Since any smooth function can be expressed as a DC decom- position, our problem template encompasses the minimization nonconvex smooth functions and extends beyond.
The significance of problem (1) lies its generality. DC functions form a vector space and constitute a rich subclass of locally Lipschitz nonconvex functions, a class that has received significant atten- tion (Zhang et al., 2020; Kong Lewis, 2023; Davis al., 2022). As a result, this problem class has broad applications, including nonconvex quadratic problems (An & Tao, 1997, 1998), convex- concave programming (Yuille Rangarajan, 2003; Shen al., 2016), kernel selection (Argyriou et al., 2006), bilevel programming (Hoai An et al., 2009), linear contextual optimization (Bennouna et al., 2024), discrepancy estimation in domain adaptation (Awasthi et al., 2024a), determinantal point processes (Mariet & Sra, 2015), and robustness of neural networks (Awasthi et al., 2024b). We refer to (Le Thi Pham Dinh, 2018) for recent survey on the history, development, and applications of DC programming.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Our goal in this paper is to develop flexible projection-fre frre algorithmic framework that preserves the scalability advantages of FW while leveraging the DC structure of the problem. Since DC decompositions are not unique, carefully selecting decomposition allows us to derive algorithms tailored to address practical limitations in specific problem settings, ultimately leading to improved computational efficiency and better local solutions.
1.1 Summary of Contributions
With this background, let summarize the key contributions of this paper.
1. We design and investigate the convergence behavior of a general projection-free algorithmic framework, which we call Frank- Wolfe for Difference of Convex problems (Dc-Fw). This framework builds on the general template of DC Algorithm (DCA) (Tao & Souad, 1986) and employs FW solve its subproblems. We show that Dc-Fw finds an e-suboptimal first-order stationary point in ()=-2) FW steps, matching the complexity of standard FW for smooth nonconvex minimization (Lacoste-Julien, 2016).
DC decomposition for any given function & is not unique, and applying DC-Fw to different decompositions of the same objective function yields different algorithms. We focus on the general template of L-smooth nonconvex minimization over convex and compact set and examine two natural DC decompositions. The first setting leads to a new nonconvex variant of the conditional gradient sliding algorithm (Lan & Zhou, 2016), which reduces gradient computations by reusing the same gradient over multiple FW steps. As result, the gradient complexity improves from O(c-²) to O(e='), making it effective for problems where gradient computation is expensive. Moreover, when the problem domain is strongly convex, the linear minimization oracle complexity also improves, from O 22) to O( -/2). The second setting yields an algorithm that follows an inexact proximal point method.
3. Finally, we evaluate the empirical performance of the proposed framework through numerical experiments, comparing with other FW algorithms on quadratic assignment problems and the alignment of partially observed embeddings.
Related Work
This section presents related work and background on DC programming and projection-free methods.
2.1 DC Algorithm
Many problems nonconvex optimization can be formulated as a DC program. A widely used approach for solving these problems is the DC Algorithm (DCA), general framework originally introduced by (Tao & Souad, 1986). DCA has been broadly acknowledger over the past three decades for its wide range of applications. For comprehensive survey on its variants and applications, we refer to (Le Thi & Pham Dinh, 2018).
The asymptotic convergence theory of DCA was introduced in (Tao, 1997), with simplified analysis under certain differenntiailiiyy assumptions later provided in (Lanckriet & Sriperumbudur, 2009). More recently, a non-asymptotic convergence rate of (1/k) was established by (Khamaru & Wainwright, 2019; Yurtsever & Sra, 2022; Abbaszadehpeivasti et al., 2023).
2.2 Projection-free Methods
In many applications, optimization problems are subject to constraints that impose limits solutions or act as a form of regularization. When the constraint set D admits an efficient projection operator, projected gradient methods can be used to solve these problems. However, the projection step be computationally expensive in many applications. In such settings, projection-fris -fee methods, such as the FW algorithm, can offer significant computational advantages.
2.2.1 Frank-Wolt Algorithm
FW was originally proposed by (Frank & Wolfe, 1956) for solving smooth convex minimization problems with polyhedral domain constraints. Its analysis was later extended to arbitrary convex compact sets (Levitin Polyak, 1966). The algorithm gained recognition for simple structure and computational efficiency in data science and classical machine learning problems (Jaggi, 2013). The analysis of FW for nonconvex functions was first introduced in (Lacoste-Julien, 2016). Extensions of FW, such as stochastic and block-coordinate versions, well variants incorporating away steps,

---

pairwise steps, and in-face steps for faster convergence, have been extensively studied in the literature. For comprehensive overview of these developments, we refer (Kerdreux, 2020).
Khamaru & Wainwright (2019) studied an adaptation of the standard FW algorithm for DC problems, by replacing the gradient in FW with the difference V ff(x) u, for some subgradient E @g(x:). They showed that this method finds an e-suboptimal critical point within ((L/=") iterations. More recently, Millán al. (2023) studied the same algorithm with backtracking line-search strategy. For general DC problems, the method with this line-search strategy retains the same complexity guarantee of (.)/=²). However, it achieves a faster rate of (1//e) for specific class of DC problems where the objective function o is weakly-star convex, which means that for every point x E D, there exists global optimal point 2, such that ø is convex on the line segment between x and 2
2.2.2 Conditional Gradient Sliding
Lan & Zhou (2016) proposed Conditional Gradient Sliding (CGS) for the constrained minimization of a convex and smooth function. Rather than solving the problem directly with the FW algorithm, CGS formulates an inexact accelerated projected gradient method and employs FW to solve the projection subproblems. While this approach maintains total of (1/fe) FW steps, which matches the complexity of FW for convex minimization, CGS improves the gradient oracle complexity to O(I/VC,, as the gradient remains unchanged within each projection subproblem. Qu et al. (2018) analyzed the convergence of CGS in the nonconvex setting and proved that it requires (1/c²) FW step and (1/cc) gradient evaluations to reach an c-suboptimal stationary point with respect to the squared norm of the gradient mapping.
3 Frank-Wolfe for DC Functions
We are now ready to outline the design of our method, which is based on a general class of algorithms for DC problems called the DC Algorithm (DCA). Starting from a feasible initial point xn E DD DCA iteratively updates its estimation by solving the following subproblem:
It-1 = argmin (x(x) = fxx - g(xe) - (u,, nz),
(2)
ZED
where u4 E (3t))) is an arbitrary subgradient of g at x4 Namely, at each iteration, DCA considers a convex surrogate function dr (x:) obtained by linearizing the concave component around 24.
Definition 1. We measure convergence in terms of the following gap definition:
{1(x.) f(x) (u, 24 2t)
gaPpe max min
zED uE8g(
When g is differentiable, the subdifferential becomes a singleton, 0g(z;) [Vg(z))), and the gap measure simplifies to gapbe( = max.ed (f - f(z) (Vg( Iz x)))
Lemma 1. The measure gap (2;) is nonnegative for any 2; DD and it is equal to zero if and only if xr is critical point satisfying
(V)(a)) +
+ 0,
where ND(x1) is the normal cone of DD at Zt.
Moreover, if g is differentiable (but not necessarily smooth, i.e., its gradients may not be Lipschitz continuous), then the condition (3) reduces to the characterization of a first-order stationary point. In other words, under the assumption that is differentiable, gapne( = 0 if and only if xz is first-order stationury point of problem (1).
The following theorem provides convergence guarantees for DCA. Since DCA subproblems may not generally admit a closed-form solution, it is desirable allow inexact solutions to the DCA subproblem. The theorem ensures that, even when the subproblems are solved inexactly, the method converges a stationary point (or a critical point when g is non-differentiable).
Theorem 2. Suppose that the sequence x, is generated by an inexact-De DCA algorithm designed to solve the subproblems described in (2) approximately, satisfying the inequality (e( - min de (x) $ 4/2 for some 0. Then, the following bound holds:
RED
min gapoc(Z,) ((00) - 6(Ix) SST
+
(4)
1+1
2
3

---

Algorithm DC-FW
1: Input: initial point 21 D, target accuracy
2: for (or(=1 1, ., do
3: Initialize Xt,1 = Zt
4: for k = 1,2.... do
5: St. = arg mD (Vf(X),)) Vg(xz).
6: Dr. = St.k Xt,
7:
if (V-Vx((X,,)) Vg(xt), Dr,a) e/2 then
8:
Ic+1 Xt, and break
9: end if
10: Xt.++1 = Xe, + ne Di,k
// use nt, 2/(k + 1), or the strategies in (5) or (6)
11: end for
12:
end for
Note that the subproblem (2) involves smooth convex minimization convex compact set, making it suitable for the FW algorithm:
Ss argmin (V²(Iz),
xED
(FW)
F&+1 z6 (7 rk),
where E [0, is the step-size. There are various step-size strategies in the literature, common choices are 7h2 = 2/(k: + 1), the exact line-search
nh argmin (E
δ(хx + m(sx xk)).
(5)
and the Dem' yanov & Rubinov (1970) step-size
(Vo(z)), 8k)
min
(6)
L D
The following result from (Jaggi, 2013) formulates the convergence result for solving these subprob- lems using the FW algorithm.
Lemma 3 (Theorem in (Jaggi, 2013)). Suppose & is a proper, convex, and L-smooth function.
Consider the problem of minimizing over convex and compact set DD of diameter D. Then, the sequence {øk] generated by the FW algorithm satisfies
2LD
-(zz)- - )(x) <
Vx E D.
k ++1
This result holds for 7) = 2/(1 1). the line-search, and the Demyanov-Rubee Rubbnoo step-size.
We are now ready to incorporate DCA and FW algorithms, resulting in projection- free approach for solving DC problems. The proposed algorithm, Dc-Fw, applies the inexact- DCA method and employs the FW algorithm to solve the subproblems in (2), detailed in Algorithm
Corollary 4. DC-Fw generates sequence of solutions that satisfies minogrst gapue gxPoc(#r) within O(1/e) iterations, requiring at most (1)e²)) calls to the linear minimization oracle.
Improvements for Strongly Convex Sets
Given a DC function d(x) fz) ((x), we can always express as a difference of strongly convex functions by adding the same quadratic term both o and g. In this case, subproblem (2) becomes strongly convex. raising a natural question of whether this strong convexity can be exploited. Unfortunately, FW algorithm generally does not benefit from strong convexity, as worst-case complexity examples also involve strongly convex objective functions (see Lemma 3 in (Jaggi. 2013)). However, if the constraint set D is also strongly convex, FW achieves a faster convergence rate of OLL/k²), as shown by Garber & Hazan (2015).

---

Definition 2. A set D S IR' is said to be a-strongly convex with respect to norm |I if for all y,y E D, all E [0, 1). and all 2 E TRd with ||=|| I 1, the following inclusion holds:
x n - z) 7 7) || y 1 D.
In other words, D is a-strongly convex if, for all æ E 'D and E [0, 1]. it contains a ball of radius || n) of strongly convex functions, as well as e--norm balls and Schatten p-norm balls for 1 < p S 2; see (Garber & Hazan, 2015) for details.
yll centered at + ( - Examples of strongly convex sets include the epigraphs
Lemma (Theorem in (Garber & Hazan, 2015)), Suppose à is a proper. lower semi-continuous, j--strongyy convex and L-smooth function. Consider the problem of minimizing & over an a-strongly convex and compact set D of diameter D. Then, the sequence {IN} generated by the FW algorithm
satisfies
9LD
48-12]
x(zz)- -xx) S (k ++11 1)2 max
E D.
2
a²p
This result holds with the line-search or the Demyanov- Rubinov step-size.
Corollary 6. Consider the DC problem in (I), and assume that I is a strongly convex function and D is strongly convex set. Then, the DC-Fw algorithm generates sequence of solutions satisfying minggrse gappe (x,) S e within (1/e) iterations, requiring at most (1/e² calls to the linear minimization oracle.
Remark (Comparison with (Khamaru & Wainwright, 2019; Millán et al., 2023)). In contrast to our work, these methods do not fully exploit the DC structure of the underlying problem, but rather focus on the classical FW algorithm. While they achieve similar iteration complexity guarantees for the gradient oracle (V l') and the linear minimization oracle of order O(1/e), DC-Fw benefits from an improved subgradient oracle (u E 8g) complexity of O(1/e). Moreover, if a strongly convex set, our complexity guarantees for both the gradient and linear minimization oracles improve to (1))2()) Notably, while the linear minimization is typically the primary computational cost in many FW applications within the convex setting, the subgradient computation significant challenge in DC problems. Additionally, the method proposed by Millán et al. (2023) adopts an iterative line fine-search strategy that requires function evaluations of o, incurring additional computational cost. We evaluate the empirical performance of DC-Fw against these methods on a partially observed embedding aligument problem in Section 6.2, demonstrating its effectiveness.
also present
4 Special Cases for Smooth Optimization
A particular problem setting for the standard FW algorithm is the minimization of smooth nonconvex objective function over compact convex set (Lacoste-Julice 2016):
min ((x)) =ED
where D S Rd is a convex and compact set and 6 D - R is a nonconvex T-smooth function. Due to smoothness, both d(x) + 2 ||=|| and 2 ||==|| ((x) are convex, providing two natural DC decompositions of the objective function, leading to two different algorithms.
4.1 Conditional Gradient Sliding
One possible DC decomposition of Problem (7) is:
L
f(x) = 1 |= g(x)
マ || 6(z).
(8)
When DCA is applied to this formulation with exact solutions the subproblems, it recovers the projected gradient method. Specifically, subproblem (2) becomes:
L
min ZED
- | (La, V)(x)), 2
In other words, DC-Fw applied to this formulation simplifies to an inexact projected gradient method, where FW is used to approximately solve the subproblems. This naturally leads nonconvex variant of the conditional gradient sliding algorithm.
5

---

Remark 8. In this setting, the search rule (5) is equal to the Demyanov-Rubing step-size (6).
I-smooth (possibly nonconvex) objective function & over a convex and compact set 'D Suppose we apply DC-FW using the DC decomposition in (8). Then, the sequence {It} generated by the algorithm satisfies
Theorem 9. Consider the problem of minimizing
min (x,) S 0(IO) -(xo)-6(zz) + 2 0g
(10)
t+1
and the inner loop terminates after at most K S ALD2/e /e iterations. As consequence, the method provably finds an e-suboptimal stationary point after O(L/c) gradient evaluations and O(1/²²) linear minimization oracle calls. Moreover. if is a strongly convex set, the linear minimization oracle complexity improves to ((1/6(2), provided that the Semnynnv-Rubiiee step-size is used.
Lemma 10.
When applied the decomposition in (8), gaP provides upper bound on the widely used projected gradient mapping (PGM) measure:
gap)c( 2 gappaa (1)) 11 - projo - - \V((z.))
Remark 11 (Comparison with (Qu et al., 2018)). Our gradient and linear minimization oracle complexities match those established by Qu et al. (2018) for the standard conditional gradient sliding algorithm the nonconvex setting. However, when adapting the method from the original work of Lan & Zhou (2016), they also inherited the momentum steps. These steps appear redundant in the nonconvex setting in terms of complexity guarantees and complicate the analysis. Our framework simplifies both the method and the analysis while strengthening the guarantees by reducing the constant from 24(6(zo) ó(z.)) to (Ø(x0) - =o(z)). and deriving guarantees in terms of the stronger notion of gaPoc instead of gaProm- Notably, while Qu et al. (2018) derived guarantees based on the gradient mapping norm instead of the standard Frank- Wolfe gap, they explicitly noted that understanding the precise relationship between these convergence criteria was an important direction for future research. We established a clear connection between these convergence criteria.
4.2 Proximal Point Frank-Wole
Alternativey., we consider the decomposition:
f(z) <xx) |1
4 _ |0/.
g(x)
(II)
In this setting, subproblem (2) simplifies to
min <(x) + ||: (Lx,, EDD
2
As result, this decomposition leads to inexact proximal point algorithm where FW is used to approximately solve the subproblems.
Theorem 12. Consider the problem of minimizing an L-smooth (possibly nonconvex) objective function & over convex and compact set Suppose we apply Dc-Fw using the DC decomposition in (11). Then, the sequence {xt} generated by the algorithm satisfies the bound in (10). In particular, the method finds an e-suboptimal stationary point after O(1/e) iterations. This leads to ((1/²2) gradient evaluations and linear minimization oracle calls.
Lemma 13. When applied to the decomposition in (11), gaPoc provides an upper bound on the widely used proximal point mapping (PPM) measure:
gappe (z:) Z gapte L (xt) = 2 x - - (orxxo((z)) (2:)))
On the role of the decomposition. is important to note that gappe is cetppppossiioodddpeeeeede The choice of DC decomposition determines the notion of stationarity captured by the gap function. Consequently, it allows one to trade off computational efficiency against the strength of the stationarity notion achieved. Recall from Definition I that gappe retains the convex component f while linearizing the concave part -g. effectively discarding higher-order information g. To illustrate this effect, consider the smooth nonconvex function ((z) sin(T21) cos(TT22) over the domain [-1, 1]2 with

---

Lavel curves of 4in(T (ooe)
gap 3s)
03
03
0.3
0.2
0.2
-0.5
005 -0.5
-0.5
-1 0
-1
-1 -0.5
0.5
-0.5 0
0.5 1 -1 -0.5
0.5
(2)
22
Figure 1: Comparison of the DC gap function for different decompositions of 6(F1, sin (T21) co5() on the domain [_1, [Left] Level curves of Φ. [Middle] gaproMe corre- sponding to the decomposition in Section 4.1, which linearizes & and therefore does not distinguish between local minima, saddle points, and local maxima. [Right] gap corresponding to decomposition in Section 4.2, which retains curvature information in Øi it is flatter around local minima and sharper around saddle points and local maxima.
L= . We evaluate both gapros and gapérg over a fine grid on the domain. The results, shown in Figure 1, reveal that while gapboM behaves similarly across all stationary points (whether they local minima, saddle points, and local maxima), gapии distinguishes between them: it is flatter near the local minimum but sharper near the saddle and local maximum. This difference arises because L retains the curvature of o within f, whereas gapras linearizes it away.
gap
5 Special Cases for Nonsmooth Optimization
We now extend the discussion to class of nonsmooth problems that fit into the proposed framework.
5.1 Conditional Subgradient Sliding
Consider an objective function Φ D + IR, which may be nonsmooth and nonconvex, but whose neg- ative is w-weakly convex; that is, (xxx) + / ||=||| is convex. Then the following DC decomposition valid:
(xx 2 a 13
g(x) = -1=1--1---- -
Unlike in Section 4.1, ø is not required to be smooth (or even continuously differentiable), it suffices that a subgradient of (equivalently, of -)) can be computed. Under this formulation, Dc-Fw naturally extends the conditional gradient sliding method to the nonsmooth setting. The result in Theorem continues to hold in this setting after replacing the smoothness constant T. with the weak convexity constant w, and gradient evaluations with subgradient evaluations.
A notable subclass arises when & admits the composite form
d(x) p(x) ((x).
(12)
where p is w-smooth (possibly nonconvex) and is convex (possibly nonsmooth). In this case, - w-weakly convex and g admits a well-defined subgradient. Applying Dc-Fw this formulation economizes on both gradient evaluations of p and subgradient computations of g. As an example, the alignment problem of partially observed embeddings presented in Section 6.2 belongs to this class, characterized by a convex smooth loss term and concave nonsmooth regularizers.
5.2 Proximal Subgradient Frank-Word
Consider the composite objective in (12), but using the following DC decomposition:
f(x) p(x) + || 9(x) ||0|| + q(x).
This is valid decomposition for Dc-Fw, since both and g are convex, and f is 2w-smooth. The resulting algorithm can interpreted as an inexact proximal subgradient method with FW for solving each subproblem approximately. Similar to the result in Theorem 12, the method attains an e-suboptimal stationary point after 0(1 /e) iterations. However, this requires (11ee) subgradient evaluations of and O(1/e²) gradient evaluations of and lincar minimization oracle calls.
7

---

6 Numerical Experiments
In this section, we numerically evaluate DC-FW on solving the quadratic assignment problem (QAP) and alignment of partially observed embeddings. Simulations were run on single core of an Intel Xeon Gold 6132 processor using MATLAB 2021a.
6.1 Quadratic Assignment Problem
The goal in QAP is to find a permutation that optimally aligns two matrices A and B g"x", This amounts to minimizing a nonconvex quadratic objective function over the set of permutation matrices, an NP-Hard combinatorial optimization problem. A promising approach approximate QAP is to use the following convex-hull relaxation (Vogelstein et al., 2015):
min X E
XA
subj.to X [0,1] X1, x In>
(13)
where 1, denotes the n-dimensional vector of ones. The feasible set in this problem, known as the Birkhoff polytope, is the convex hull of permutation matrices. In general, this relaxation is still nonconvex due the quadratic objective function. The relax-and-round strategy of Vogelstein al. (2015) involves two main steps: Finding a local optimal solution of (13) and rounding it to the closest permutation matrix.
Projecting matrix onto the Birkhoff polytope is computationally expensive. Therefore, Vogelstein al. (2015) employs the FW algorithm for solving (13). The linear minimization oracle for this problem corresponds to solving linear assignment problem (LAP), which can be solved ((23) arithmetic operations by using the Hungarian method or the Jonker-Volgenee Volgenant algorithm (Kuhn, 1955; Munkres, 1957; Jonker & Volgenant, 1987). After finding solution to the relaxed problem (13), we can round it to the closest permutation matrix (in Frobenius norm) also by solving LAP.
DC-Fw for solving QAP. components
We consider the decomposition ((X) f(X) g( (X) with the
1 IIA X f(x) = -
- X-X X 3
(14)
While other decompositions, such as those in (8) and (11) are also possible, here we show the results for (14) which performed the best. The numerical results for other decompositions and the non-convex CGS method (Qu et al., 2018) are given in Appendix B.
Evaluation metric. To compare the solutions of Dc-Fw and FW (as used in (Vogelstein et al., 2015)), evaluate the assignment error from rounded permutation matrices:
assignment error (x( - o( hest)
(AE)
max { (X 1]
where Xrest denotes the best known solution to QAP, which available for the QAPLIB benchmark datasets (Burkard et al., 1997).
Implementation details. All methods start from the same initial point, obtained by projecting the sum of normalized matrix of ones and i.i.d. standard Gaussian random matrix onto the Birkhoff polytope. This projection is performed using 103 iterations of the alternating projections method. We compute the gap the initial point, denoted cu. and terminate the algorithms once the gap reaches 0.001 x cp. Additionally, we impose a maximum iteration limit of 10a. For both Dc-Fw and FW, we used the exact line-search method for step-size selection, Appendix for more details. The inner loop for DC-Fw terminates with respect to a specific tolerance level e. We employed an adaptive strategy where the tolerance e, is updated dynamically. We fixed a multiplication parameter and initially we set E 8 x ep- Then, at each iteration t, we update the tolerance as follows: if the gap falls below et, we decrease the tolerance by setting 1 = Sez. Otherwise, we keep unchanged, 1 = ct. Further details and discussion on this strategy are provided in Appendix D.
0.8,
Results. Figure 2 demonstrate the superior performance of DC-FW over the FW method on 73 out of 134 datasets in terms of the assignment error. In 18 cases, both methods produced equal errors, while FW achieved lower error datasets. Moreover, Dc-FW achieved a lower average assignment error (0.0085) compared to FW (0.0112).
8

---

10-1
pGrn
10
nasignmmnt
10
aosigamennt
10-3
10
Figure 2: Assignment error of FW and Dc-Fw for solving QAP using and-round strategy. Zero shows an exact solution. The instances are ordered from best worst performance of FW. In total, 134 datasets from QAPLIB were used: DC-Fw outperformed FW in 73 cases, FW performed better in 43 cases, and both methods achieved the same assignment error in 18 cases.
6.2 Alignment of Partially Observed Embeddings
We consider cross-lingual word embedding alignment problem, where the goal is align the source embedding matrix (E₃ E Bdxx) with the target embedding matrix (E2 E IRd*") using an orthogonal transformation matrix X E Radxd When the embedding matrices are fully available, this problem can be efficiently solved using the Procrustes algorithm (Xing et al., 2015; Comneau et al., 2017). Here, we consider a more challenging setting where target embedding is partially observed. In this scenario, we are given measurement mask P E {0, 1 1] and the partial observations Y = 3 Eg E Rdxa, where @ denotes the Hadamard product. Our goal is to find an orthogonal transformation that minimizes the mean squared loss. We consider the following objective with nonconvex regularizer that promotes orthogonality:
min XeRaxa
|P (XE,) YI -||XII subj.to
|X| 11
(15)
2n
Here, the spectral norm constraint ensures that the singular values of X are bounded by 1, and the negative nuclear norm regularization encourages them approach this limit, promoting orthogonality.
We compare the performance of Dc-Fw with other FW variants for DC problems as described in (Khamaru & Wainwright, 2019) and (Millán et al., 2023), which we denote by FW-K and FW-M respectively. A subgradient of nuclear norm can be found as UVT, where U and V are the left and right singular vector matrices. Similarly, linear minimization oracle over the spectral norm can be obtained as T Additionally, FW-M requires evaluating the objective function during its line-search, which involves calculating the nuclear norm, which has similar cost (i.e.. SVD computation). While we implemented the oracles using full SVD computations in this experiment, the approximation UVT can obtained using a few iterations of the Newton-Schulz method (Bernstein & Newhouse, 2024) in large-scale implementations. However, it is worth noting that implementing FW-M with inexact oracles can be challenging, as the backtracking line-search procedure may enter an infinite loop when the objective evaluations are inaccurate.

---

10
10
10-
Pranke- Wolle Gop
10-2
10
10.3
10
10
FW-K
FW-M
10-4
DC-FW
10-1
10-
10"
10
10P
10
caleulations x10 0 300
600
900
1200
Sterations
(sec)
Figure 3: FW gap evolution as function of the iteration counter (left), the number of SVD computa- tions (middle), and the wall clock time (right) for the alignment of partially observed embeddings. In 10 iterations, FW-K and FW-M called the subgradient and linear minimization oracles 101 times each; FW-M performed an additional 19, 990 function evaluations during the backtracking line-search; DC-FW called the linear minimization 10a times and the subgradient 88 times.
We use the 300 -i0-dimensional English and French word embeddings from the FestText library (Bo- janowski et al., 2017) as the source and target embecldigs, selecting the 10,000 most common words from each dictionary. We model partial observations by assuming that each entry in the target embedding is independently observed with a probability of 0.1. We choose regularization parameter
A 10-4, All algorithms are initialized the origin. Figure 3 presents the results of this experiment. Both FW-M and Dc-Fw outperform FW-K. While the iteration convergence rates of FW-M and DC-Fw appear similar, the iterations of FW-M are more expensive because they require computing the subgradient at every iteration and evaluating the objective function within the backtracking line-search procedure. FW-M also appears to oscillate more.
To evaluate the quality of the obtained solution, we use the baseline aligmment quality computed by assuming that E2 is fully available and solving the problem via the Procrustes algorithm. After rounding our solutions to the closest orthogonal matrix, we compare the achieved alignment quality with the baseline. Our formulation and method achieves 93. 11% of the original alignment quality despite observing only 10% of the target embedding, demonstrating that the formulation is effective even under partial observations.
7 Conclusions
We studied the DC-Fw framework, which integrates DCA with the FW algorithm. We established that DC-Fw retains the same oracle complexity for linear minimization steps as standard FW in nonconvex optimization. However, by carefully selecting the DC decomposition, Dc-Fw to the underlying problem geometry in different ways, offering flexible approach for a variety of problem settings. We examined two natural DC decompositions within the standard smooth minimization template. One dccomposition, in particular, led to an algorithm that reduces gradient computations, improving the gradient complexity from (c--2) to O(c-1). Additionally, when the problem domain is strongly convex, this approach improves the linear minimization oracle complexity to O(c-%a) Through numerical experiments quadratic assignment problem and alignment of partially observed embeddings, we demonstrated the effectiveness of Dc-Fw in comparison to the standard FW approach. After the initial submission of this paper, Pokutta (2025) presented an extensive computational study that builds upon our framework, combining our approach with some advanced FW variants (for example, with blended pairwise steps (Tsuji et al., 2022)). Their results provide complementary evidence for the scalability and efficiency of the proposed approach.
adapt
Our findings provide a concrete example where a simple but deliberate manipulation of the DC decomposition enables better algorithm, and calls for wider future study. The simplicity of our analysis in achieving these results shows the potential of problem reformulations within the DC framework. Rather than relying intricate analytical techniques, we overcome technical challenges through carefully chosen problem reformulations. Our work also suggests noteworthy future directions. Extending the analysis of Dc-Fw to stochastic settings and making it more compatible with modern machine learning practices, remains a crucial next step. Another potential avenue is to develop adaptive DC decompositions that dynamically adjust to the problem's geometry.
10

---

Acknowledgments and Disclosure of Funding
Hoomaan Maskan, Yikun Hou, and Alp Yurtsever were supported by the Wallenberg AI, Autonomous Systems, and Software Program (WASP), funded by the Knut and Alice Wallenberg Foundation. Suvrit Sra acknowledges generous support from the Alexander von Humboldt Foundation. Part of the computations was conducted using resources from the High Performance Computing Center North (HPC2N) and were enabled by the National Academic Infrastructure for Supercomputing in Sweden (NAISS), partially funded by the Swedish Research Council under grant no. 2022-06725. The remaining computations were performed on the Berzelius resource, provided by the Knut and Alice Wallenberg Foundation at the National Supercomputer Centre. We thank Ahmet Alacaoglu and Yura Malitsky for insightful discussions on the relationships between different gap functions.
References
Ahhasvadchpccivasi, H., de Klerk, E.,, and Zamani, M. On the of convergence of the difference-of-comvex algorithm (DCA). Journal of Optimization Theory and Applications, pp. 1-22, 2023.
Alfaro, C. A., Perez, S. L.,, Valencia, E., and Vargas, M. C. The assignment problem revisited. Optimization Letters, 16(5):1531-1555 2022.
L. and Tao, Solving a class of linearly constrained indefinite quadratic problems by DC algorithms. Journal of global optimization, 11:253-285, 1997.
and Tao, P. D. A branch and bound method DC optimization algorithms and ellipsoidal technique box constrained nonconvex quadratic problems. Journal of Global Optimization, 13(2):71-2066 1998.
Argyriou, A., Hauser, R., Micchelli, A.. Pontil, M. A propogganminng algorithm for kernel selection. In Proceedings of the 23rd international conference on Machine learning. pp. 41-48, 2006.
Awasthi, P., Cortes, C., Mohri, M. Best-effort adaptation. Annals of Mathematics and Artificial Intelligncee pp. 1-46, 2024a.
Awasthi, Mao, A.. Mohri, M., and Zhong, Y. DC-programming for neural network optmizatiins. Journal of Global Optimization, pp. 1-17, 2024b.
Bennouna, O., Zhang, J., Amin, S., Ozdaglar, A. Addressing misspecification contextual optimization. arXiv preprint ar Xiv: 10479, 2024.
Bernstein, J. and Newhouse, L. Old optimizer, new norm: An anthology. arXiv preprint arXiv:2409.23325. 2024.
Bertsekas, D. Auction algorithms for network flow problems: tutorial introduction. Computational optimization and applications, 1:7-66, 1992.
Bojanowski, P., Grave, E., Joulin, A.. and Mikolov, T. Enriching word vectors with subword information. Transactions of the Association for Computational Linguistics. 5:135-146, 2017. ISSN 2307-387X.
Burkard, R. E., Karisch, E., and Rendl, QAPLIB-a quadratic assignment problem library. Journal of Global optimization, 10:391-403, 1997.
Combettes, and Pokutta, S. Complexity of linear minimization and projection on some sets. Operations Rexearch Letters, 555455555-57,, 2021.
Conneau, A., Lample, G., Ranzato, M., Denoyer, L.,, and Jégou, H. Word translation without parallel data, arXiv preprint arXiv:1710.04088, 2017.
Davis, D., Drusvyatskiy, D., Lee, T., Padmanabhan, S., Ye, G. gradient sampling method with complexity guarantces for Lipschitz functions in high and low dimensions. Advances in neural information processing systems, 35:6692-6703,, 2022.
Dem' yanov, V. F. and Rubinov, A. M. Approximate methods in optimization problems. American Elsevier Publishing Company, 1970.
Frank, M. and Wolfe, P. An algorithm for quadratic programming. Naval research logistics quarterly, 3(1-2): 95-110, 1956.
Garber, D. and Hazan, E. Faster rates for the Frank- Wolfe method over strongly-convex sets. In International Conference on Machine Learming, pp. 341-549, PMLR, 2015.
Hoai An, L. T., Tao, P. D., Nguyen Canh, N., and Van Thoai, N. DC programming techniques for solving class of nonlinear bilevel programs. Journal of Global Optimization, 44:313 337, 2009.
Jaggi. M. Revisiting Frank- Wolfe: Projection free sparse convex optimization. In International conference on machine learning, pp. 427-435. PMLR, 2013.
11

---

Jonker, R. and Volgenant, A. A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing, 38(4):325-34) 1987.
Kerdreux, T. Accelerating conditional gradient methods. PhD thesis, Université Paris sciences et lettres, 2020.
Khamaru, K. and Wainwright, M. Convergence guarantees for class of non-convex and non-smooth optimization problems. Journal of Machine Learning Research, 20(154):1-52.1 2019.
Kong, S. and Lewis, A. The cost of nonconvexity in deterministic nonsmooth optimization. Mathematics of Operations Research, 2023.
Krizhevsky, A. and Hinton, G. Learning multiple layers of features from tiny images. 2009.
Kuhn, H. W. The Hungarian method for the assignment problem. Naval research logistics quarterly, 2(1-2): 83-97, 1955.
Lacoste-Julien, S. Convergence rate of Trank-Wolfs for non-convex objectives. arXiv preprint arXiv: 1607.00363 2016.
Lan, G. and Zhou, Y. Conditional gradient sliding for convex optimization. SIAM Journal on Optimization, 26 (2):1379-1409, 2016.
Lanekrict, G. and Sriperumbudur, K. On the convergence of the concave-coneex procedure. Advances Neural Information Processing Systems, 22, 2009.
Le Thi, H. A. and Pham Dinh, T. DC programming and DCA: Thirty years of developments. Mathematical Programming, 169(1))5-668 2018.
Levitin, E. S. and Polyak, B. T. Constrained minimization methods. USSR Computational mathematics and mathematical physics, 6(5):1-50, 1966.
Mariet, Z. and Sra, Fixed-point algorithms learning determinantal point processes. International Conference on Machine Leurning, pp. 2389-2397. PMLR, 2015.
Millán, R. D., Ferreira, O., and Ugon, J. Frank-Woll algorithm for DC optimization problem. arXiv preprint arXiv:2308. 16444, 2023.
Munkres, J. Algorithms for the assignment and transportation problems. Journal of the society for industrial and applied mathematics, 5(1):32-38, 38, 1957.
Pokutta, S. Scalable de optimization via adaptive Trank-Wold algorithms. arXiv preprint arXiv:2507.17555 2025.
Pokutta, S. Spiegel, and Zimmer, M. Deep neural network training with Wolle. arXiv preprint arXiv:0010.02433, 2020.
Qu. C., Li. Y., and Xu, H. Non-convex conditional gradient sliding. In international conference on machine learning, pp. 4208-4217. PMLR, 2018
Shen, X., Diamond, S., Gu, Y., and Boyd, S. Disciplined convex-concant programming, In 2016 IEEE 55th IEEE, 2016.
conference decision and control (CDC), pp.
Tan, M. and Le, Q. EfficientNet: Rethinking model scaling for convolutional neural networks. International conference on machine learning, pp. 6105-61 14, PMI.R, 2019.
Tao, P. D. Convex analysis approach DC programming: theory, algorithms and applications. Acta mathematica vietnamica, 22(1):289) (3855339,,55 1997.
Tao, P. D. and Souad, E. B. Algorithms for solving a class of nonconvex optimization problems. Methods of subgradients. In North-Holland Mathematics Studies, volume 129, pp. 249-271. Elsevier, 1986.
Tsuji, K. K., Tanaka, K., and Pokutta, S. Pairwise conditional gradients without swap steps and sparser kernel herding. In International Conference on Machine Learning, pp. 21864 111864-21888 21883. PMLR, 2022.
Vogelstein, T., Conroy, M., Lyzinski, V., Podrazik. L. J., Kratzer, S. G., Harley, T., Fishkind. D. E., Vogelstein, R. J., and Priebe, C. E. Fast approximate quadratic programming for graph matching. PLOS one, 10(4):s0121002, 2015.
Xing, C., Wang. D., Liu. C., and Lin, Y. Normalized word embedding and orthogonal transform bilingual word translation. In Proceedings of the 2015 conference of the North American chapter of the association for computational linguistics: human language technologies, pp. 1006-1011, 1, 2015.
Yuille, A. and Rangarajan, The concave-convex procedure. Neural computation, 15(4):915 9366, 2003.
Yurtsever, A. and Sra. S. CCCP is Frank- Wolfe in disguise. Advances in Neural Information Processing Systems,
35:35352 35364, 2022.
Zhang, J. Lin, H., Jegelka, S., Sra, S., and Jadbabaie, A. Complexity of finding stationary points of nonconvex nonsmooth functions. In International Conference on Machine Learning, pp- 11173-11182 PMLR, 2020.
12

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect paper's contributions and scope?
Question:
Answer: [Yes]
Sections and propose the new algorithm and shows its convergence rate in addition to the comparisons and simulation results which clearly reflect the paper's contribution and claims.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We have mentioned some limitations in the numerical section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point any strong assumptions and how robust the results are violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). ). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best
13

---

judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: All the theories in Sections 3 and 4 are comprehensively proved and all the assumptions are given. We also checked the proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof's provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We have clearly mentioned all the requirements reproduce the experiments and the claims of the paper. In addition, more detail to numerical results is given in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
14

---

(a) If the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
We will disclose all the code used in experimental results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.c cc/ public/ Soaedeee/oooeSuumiseseeeeeeee
olicy) for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: // //iips.cc. cctpsscccpuuui heablicggguies////eeee SCodeSubmissiia simiinossiiiyyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question:
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We have mentioned all the detail of our experiments in addition to more experiments and comparisons done in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
15

---

The experimental setting should be presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: Since the algorithm is deterministic and data is real, it is not relevant to include the statistical significance.
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative етrоr rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We have included all the detail about our computational resources in section 5,
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
16

---

9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: yes, we followed exactly the code of ethics provided by NeurlPS and remained anonymous.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work theoretical and proposes a new algorithm and has no societical impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinfornation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI...
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Since our paper theoretical, it is not relevant to put any safeguard on the theoretical results.
17

---

Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We made include all the citations the used datasets and resources in the paper.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: Our code original and we are owners of the code which disclosed and well documented.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details of the dataset/code/mmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
18

---

The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Question:
Answer:
[NA]
Justification:
Our research is not related to crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
19

---

The answer NA means that the core method development in this research does not involve LLMs as any important. original, or non-standard components.
Please refer to our L.M policy (ttrgg//eaariig..c///foeeeeeeeee / for what should or should not be described.
20

---

A Proofs and Technical Details
A.1 Proof of Lemma
Proof. The first statement straightforward, since 22 E D, and choosing I = Iz. within the maximization gives zero.
Suppose we have gap (w+) = 0. Then, there exists a subgradient uz dg(()) such that f(z) - f(x)) (ut, x - xτ) 2 O, Vo D.
Consider æ = It + ad for an arbitrary feasible direction and step-size a > 0. Then, (Ir + ad) - f(x))) (ut, ad) 2 Vad I + ad D. Dividing by and taking limit as a - 0+ we obtain (V)(z)) d) (u7. d) 2 Ad : lim It + ad E a-40
Since D is closed and convex, lima-+0! I2z + ad D for any d Iz such that E D. Consequently.
(V)(z)) ui m) Vr ED, or, equivalently, "n - Vf(()) E (x))). Therefore, we have condition (3) satisfied.
Next, suppose condition (3) satisfied. Then, there exists a subgradient ug E dg(xz) such that u Vx4) E (xxx),, which means
(Vf(z,) uh 24 x) Vr D.
Since is convex, it follows that
f(x)) f(x) (u,, 24 x) S Vr E D.
Since this inequality holds for all D, maximize the left-hand side over D. Moreover, since it holds for at least one subgradient už E @g(x)). we can minimize over the subdifferential set:
{f(m)) f(x) (u. x> - 0.
min max xEdg(a,) RED
By Von Neumann's 's minimax theorem, we can exchange the order of min and max since (i) 3g((),) and D are convex and compact sets; and (ii) the expression inside the braces is concave with respect 0g(z)), and convex (in fact, linear) with respect for any fixed x D.
x for any fixed After this change, we obtain gappe (2t) ) < O. Since the gap measure is nonnegative by definition, we conclude that gappe (2t) O.
A.2 Proof of Theorem
Proof. By convexity of we have
f(1++1) - g(xe+1) S f g(xx) (w4. Fe41 - xx))
where E 0g((z;) is the subgradient used at iteration t of the algorithm. Then, by the update rule (2), the following bound holds Vz E D:
f( 1( S f(x) g(xx) (we, arr) +
Then, we add f(xz) to both sides and rearrange as follows:
f(x1) fz) (u,, xz- 2) < (f(z)) o(ze) (((044)))((0+1))
Since this inequality holds for all D, we can maximize the left-hand side over D. Moreover, since it holds for at least one subgradient ui E (g()) we can minimize over the subdifferential set:
min max (f(x)) f(x) (we, T. x < (f(zz) - s(xx)) (f(x)41) -(((+i)))((++))) + wE D
By Von Neumann's 's minimax theorem,
exchange the order of min and max, and get gapoc (wx) < (f(x)) - -((e))
g(xx+1) + (f(Ze+1)= -
Finally, we obtain (4) by taking the average of this inequality over and noting that the minimum less than or equal to the average.
21

---

A.3 Proof of Corollary 4
Proof. The first results an immediate consequence of Theorem Moreover, by Lemma 3, the condition for FW is achieved at most after K -. 4LD2 /e iterations. Therefore, the total number of calls to the linear minimization oracle is bounded by tK s O(1/e).
A.4 Proof of Corollary 6
Proof. The first results an immediate consequence Theorem 2. Moreover, by Lemma 5, the condition for FW is achieved at most after K & max (L a/P
48 } l/vC iterations. Therefore, the
total number of calls to the linear minimization oracle is bounded by tK S O(1/c²)
A.5 Proof of Theorem
The first results immediately follows from Theorem 2. By Lemma 3, the e/2-accuracy for FW achieved at most after K S 4LD2 /e iterations, Therefore, the total number of calls to linear minimization oracle is bounded by LK s 011/²).
Proof.
When an strongly convex set, since (9) is a strongly convex problem with a strongly convex compact constraint set, by Lemma 5, the E e/2-accuracy for FW is achieved at most after K s max(3vLD) 18v/2L }/ V iterations provided that Demyanov-Rubino step-size is used. Therefore, av
the total number of calls to the linear minimization oracle is bounded by tk & O(1/e")).
A.6 Proof of Lemma 10
Proof. If we substitute the terms in (8) into the definition of gappe. we get
L |0ll|
max RED
2 ||x11/
-LLxe - Ve(xt), 24 - x)
max {
(Vb((z)) -x)
// 1| x.a 112
I
xED
2
L -Voolz) x, -z1) - _1lat 1|
where 27 prooo Vo(z)). By the variational inequality characterization of projection, we have
(or - Vo(xx)) - ,;, - -x;x x7) 50, Ya D.
In particular, using this with we get
L || - zell2 = gapne (xt).
|2, 2; (V((z)) z²))
2
A.7 Proof of Theorem 12
Proof. The first results immediately follows from Theorem 2. Since the subproblems are convex, by Lemma 3, the c/2 accuracy for FW is achieved most after K < 4LD² /e iterations. Therefore, the total number of calls to the linear minimization oracle is bounded by tk < O(1/e)).
A.8 Proof of Lemma 13
Proof. Plugging the terms from (11) into the definition of gappe gives
L
max (ax)) + ZED
- ||r.a| ((x)
- | - ( (Lare x))
.ED { (5(2z)) -b(x)=
_ x x12)
L
=max
max
L ||,,
=((x,) - -z(xt)
-2,1²²
22

---

where x; prox y (z)).
The variational inequality characterization of the proximal operator gives
1 [)(z) ((()), Va E D.
- x;)
In partieular, applying this F2, we obtain
L a 2 & x(x²) - v(x;)
L
|| - x7 = gappe (21).
2
2
B
Additional Details on the QAP Experiments
B.1
Exact Line-Search
Here, we derive the exact line-search step. We consider the decomposition o(X) = f(X) (X) with three different variants of components
f(x) 4 | x + XBI
9(X) = II X - -X
(variant 1)
4
f(x) = マ |
g = | 1E (A X, 2
(variant 2)
2
f(x) = (AT XB) + 2 |
g(z) = |
(variant 3)
Variant
We can compute the gradients for f and g by
1
VS(X)= 2 (A(ATX + XA
Vg(X)= XA(A - - (A" -XBBB".
For the line-search in (5), we get
d drj
d
5(Xi + D(i)))) d
(e(e + +nDxx)
(g(())) X + nDxx X(k)
dnj
dn
d [1(AT Xex + B) + nnAAA Dix + Dus B) 13 - (Vg(X,), D(N)
= dn
1 (AT Dis + B, (AT (AT Xtk + Xx+ + (1A D3A + Ba) - (Vg(X,), Dza)
=2 7I1A Du + Du + 1
(AT ( Due + DDs B, A Xu + X B) - (Vo(X,), Dik)
Equating this to 0, we get
2(Vg(X.., Daa) - (AT Dis + Due B, A A + B) |AT Duu + BI
Variant
We can solve (13) using Dc-FW for
L f(x) 2 |
g(2) 2 | XB),
(16)
Now, the gradients for f and g become
vf(X) LX
Vg(X) LX A XBT_ - AXB.
Utilizing the gradients in line-search (5) we get
d
d f(xx + nDik)
d (Vg(X.), Xax nDEx X(k)
dn (Xix + DDck)
dn
dn
(Dek. L(Xix + nD(a))) (Vg().), Dea)
Equating this to gives
7 (Vg(X)),, D(A) L(Du,,
L|| 11
23

---

Variant 3
We can solve (13) using Dc-Fw for
L + 2
L 2
= (A (A
X 12.
g(z) = 1
(17)
Now, the gradients for f and 9 become
Vf(X) A XBT + +X Vg(X)= = LX.
Utilizing the gradients in lencch (5) we get
(Xi: nDix)= f(X1s nDn)) _- d dn
d
d (Vg( + nDek - X(s)
dnj
dnj
-Diks (A (Xix + (AT(Xi
BB² + A(Xix + DB B+ + L(Xx (Deu))) - (Vg((e)) D(a)
(Dis, A BT + Ax LX + 71A DT + ADuB LD(s)) (Vg(Xi), D(s)
Equating this to 0 gives
(g(())), DOA) - (Dek, A Bx + AX + LXee)
2(A Dan Dv + D.x
B.1.1 Numerical Results
We have conducted additional experiments to emphasize the superiority of DC-FW in finding better stationary solutions. We denote DC-Fw (var 2) in (16) and DC-Fw (var 2) as in (17).
Further, we implemented the Non-convex CGS as explained in the (Qu et al., 2018). According to the original work, if the CGS is called T times, then the inner loop requires an accuracy of (1/TT) for the subproblems. This, however, takes a very long time. Therefore, we used a similar technique to the Dc-Fw implementation to both improve the accuracy and the speed of Non-convex CGS.
For all the methods similar stopping criteria (as explained in Section 6) was used and line search method determined the step-sizes. Additionally, stop-time of 10 hours was considered for all the implementations. We repeated Monte-Carlo instances per method per dataset. The results are summarized in Figure 4.
The heatmap shows the average number of datasets with lower assignment error for each method in the y-axis against each method on the x-axis. 90% confidence intervals were used to show the statistical significance of the experiments. For example, DCFW (var 1) performs better than the CGS method in 68.70 cases on average with 90% confidence interval [66. 17, 71.23J. On the other hand, CGS did better than DCFW (var 1) in 46.40 cases on average with 90% confidence interval [43.76 76, 49.04] The table shows the superiority of Dc-Fw type methods (all variations) against CGS and the FW methods.
B,2 Projection vs Linear Minimization for the Birkhoff Polytope
Consider for instance the set of (n n) doubly stochastic matrices (i.e., the convex hull of permutation matrices, also known as the Birkhoff polytope). This constraint frequently appears in allocation problems like optimal transport or quadratic assignment problems. To our knowledge, no polynomial- time exact solution method is known for this projection. An e-precise approximation can be computed via iterative methods, such as operator splitting methods like Douglas-Rachford splitting, incurring an arithmetic cost of O(n3/ /c²) (Combettes & Pokutta, 2021; Bertsekas, 1992). In contrast, an exact solution to the linear minimization oracle of FW can be found by using the Hungarian method or the Jonker- Volgenant algorithm at ((2²) arithmetic operations (Kuhn, 1955: Munkres, 1957; Jonker & Volgenant, 1987). Alternatively, an e-precise approximation can be achieved in O(n /e) operations with the auction algorithm (Alfaro et al., 2022; Bertsekas, 1992).
C Additional Numerical Experiments on Neural Network Training
Classification on Neural Networks We used a heuristic stochastic variant of the proposed Dc-Fw algorithm and the stochastic Wolfe (FW) algorithm (Pokutta et al., 2020) train neural networks with constrained parameters on two classification datasets: CIFAR- 10 and CIFAR-100
24

---

FW
44.5
30.2
59.8
70
[41.82, 47.18)
[48.61, 56.191
[47.54, 52.86]
[56.12, (3.48]
DC-FW (var I)
65
73.4
62.1
58.4
68.7
[70.80,
[59.10, 10, 65.
[56.23, 60.57]
[66.17, 71.23]
60
DC DC-FW C-FFW (var 2)
Score
66.9
51.5
48.4 [46.05, 50.751
69.4
[63.20, 70.60]
[48.25, 54.75)
[67.76, 71.04]
55
DC DC-FW FW (var 3)
50
69.1
70.5 [67.88, 73.12]
[65.94, 72.26]
[52.64, 56.36]
[54.48, 57.92]
45
CGS
59.2
46.4
38.0
37.8 [34.66 40.64]
[55 63.32]
[43.76, 49.04]
[36.61, 39.39]
40
FW
DC-FW (var 1)
DC-FW (var 2)
DC- DC-FW (var 3)
CGS
Figure 4: Comparison between FW, DC-FW variants, and CGS with 90% confidence intervals.
Transfer learning (CIFARIO)
Transfer Learning (CIFARI0O)
CNN (CIFARIO)
CNN (CIFARIO0
10
10a
10a
eatoopy)
10-1
10
0.3
10
20
10
60
100
Epoch
Epoch
Epoch
Epoch
0.8
0.6
Accutiyy
0.8
0.8
0.7
0.4
0.6
0.6
FW
0.6
0.4
0.4
0.2
0.2
0.5
20
10
60
80
100
20
40
60
80
100
0
20
40
60
80
100
0
20
10
60
80
100
Epoch
Epoch
Epoch
Epoch
Figure 5: Comparing FW and DC-Fw train classification task using CE loss using transfer learning on EfficientNetB00 and customized CNN. The training datasets were CIFAR- and CIFAR-100. In all the Figures, dashed and solid lines refer to the validation and the training data, respectively.
(Krizhevsky & Hinton, 2009). The stochastic version of Dc-Fw involves random selection of the input data every iteration the outer loop. This essentially means that an unbiased estimator of the gradients used at every iteration.
25

---

DC decomposition (9) was used in Dc-Fw with Φ(x) being the empirical loss function using Cross Entropy (CE) for the classification tasks. Note that this decomposition relates to the CGS version of the DC-Fw algorithm. All experiments were conducted using Python (3.9.5) and PyTorch (2.0.1) on an NVIDIA A100 GPU.
We first trained two customized convolutional neural networks (CNN) for CIFAR-10 and CIFAR- Subsequently, EfficientNet-BO (Tan & Le, 2019) with frozen feature layers was applied to both datasets. All models were initialized using the same seed and trained for 100 epochs with a batch size of 256.
Structure of the customized convolutional neural networks. The customized convolutional neural network consists of two convolutional layer blocks followed by a single dense layer block for CIFAR-10, and three convolutional layer blocks followed by a single dense layer block for CIFAR-100 1000 Each convolutional layer block consists of two consecutive convolutional layers with a 3 x 3 kernel size, followed by ReLU activations and Batch Normalization. This is followed by a 2 x 2 max pooling layer and dropout layer with a 0.01 probability. This dense layer block starts with flattening the input, followed by two dense linear layers. Each of them uses ReLU activation, Batch Normalization, and Dropout (0.01 probability). The final layer of this block is the classification output layer (dense layer), mapping the extracted high-level features to the desired number of output classes. For CIFAR-10, the network outputs 10 classes, whereas for CIFAR- 100, it outputs 100 classes.
Transfer learning with EfficientNet-BO. EfficientNet-BO is the smallest model in the EfficientNet family and serves as a baseline for sealing up to larger variants like EfficientNet-B1 to B7 (Tan & Le, 2019). The detailed structure of EfficientNet-B00 can be found in (Tan & Le, 2019). We applied transfer learning to EfficientNet-BOO by freezing all its feature layers, meaning that the pretrained weights from the model trained on the ImageNet dataset are kept fixed and are not updated during training. Only the classifier layers are trainable. consisting of dropout layer (with a rate of 0.2) for regularization and a linear layer for classification. This configuration reduces the number of parameters to be trained, thereby saving computational resources while maintaining competitive performance. However, due to the difference between the original domain (features in the ImageNet dataset) and the transferred domain (features in the of EfficientNet-B0 was not fully exploited without trainable feature layers.
100 dataset), the full potential
Training setup. Training was performed with parameters constrained by an f ball of radius c, following (Pokutta et al.. 2020). For the proposed Dc-Fw algorithm, in addition to the breaking condition based on gappe (see Appendix D) for more details), an upper bound was applied to the inner loop. This bound was set to 10000 for CNN and 2000 for transfer learning. We further considered the line search for updating lt. to improve convergence.
The CE loss and the top-1 accuracy were the main metrics used for comparison. For the proposed DC-FW algorithm and FW algorithm, various choices of I. and e were tested. Figure 5 illustrates performance comparison among different algorithms. The example is based on the hyperparam- eters L = 10, c = 10 for Dc-Fw and FW. Furthermore, Dc-Fw with syper-parameter L = 10, demonstrates superior performance compared to the FW method and in both training and validation.
Effects of c in neural networks. The constant scalar c is used to bound the parameters of the network while training. This was shown to be effective in generalization by Pokutta et al. (2020). The value of c, however, is dependent on the model and the target dataset and in turn, affects the generalization capabilities of the trained model.
In numerical simulations, we observed that if increases, the FW method converges slower. However, DC-Fw was able to maintain its original performance almost regardless of the value of Figure 6 depicts an instance of the accuracy of each method in our results. Similar setting in Section was used and all simulations are for = 10. As shown in the Figure, when e increases, for both datasets and both models, FW becomes slower while Dc-Fw maintains it behavior.
D Adaptive Inner-Loop Tolerance Strategy for Dc-Fw
According to Theorem 2, we require (11/e) calls to the subproblem solver (in this case, the FW algorithm) reach an e/2 accuracy. In many practical tasks, this equals high computational load.
26

---

To improve the efficiency of DC-FW we used an adaptive tolerance strategy. Suppose we require an accuracy of Eo for the final solution's 's gap and each subproblem is solved for an &, accuracy. Then, from the proof of Theorem 2, we have
((x) - [(x) - (Vg(z.), - =x) - (x())) -(x)) (s(x)+1) - s(
+ cr 2
If we only update when the problem's gap value at its current iterate is below ég, then we can write f(x)) f(x) - (Vg(z;), x)
m f(E))) f(z) (Vg(2z (3) Tt- 2)
$ -(())))((a)) -
(f(xc+)) g(x241))
Transeer Learning (Ciar10))
0.8
0.8
0.8
0.7
0.7
0.7
DC-Fw-
0.6
0.6
FW
0.5
20
40
60
80
100
20
40
6U
80
100
20
100
Epoch
Epoch
Epoch
CNN (Cifar10)
0.8
0.8
47
0.8
0.6
0.6
0.6
100
Epoch
Epoch
Epoch
Tramserr Learning (C)farl00)
0.8
0.8
0.8
0.4
0.4
0.4
0.2
0.2
0.2
0
20
40
60
80
100
20
40
60
80
100
20
10
60
80
100
Epoch
Epach
Epach
CNN (Cifar 00)
0.8
0.8
0.8
0.6
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.2
0
20
40
60
80
100
0
20
40
60
80
100
0
20
40
60
80
100
Epoch
Epoch
Epoch
Figure 6: Comparing FW and DC-Fw to train classification task using CE loss using transfer learning
on EfficientNetBO and customized CNN for constraint bounds 1, 10, 100. The training datasets were CIFAR-I0 and CIFAR-100. In all the Figures, dashed and solid lines refer to the test and training data, respectively.
27

---

Maximizing the left hand side for z E D gives
max f(z)) - f(z) (Vg(z)), - z) (f((t))) - (f (f(((1)) a(o++1))]
ZED
Now, averaging over gives the desired inequality below:
min max f(x,) - - (Vg())) 2) 2 (d(zo) - (b(x))
(18)
oStst DED
Consequently, we update e, whenever the gap value falls below it. Here, we assumed constant multiplier 0 < 3 < 1 to update 6x41 = 3eg. Note however, if this gap falls below 60, then we the desired accuracy is reached.
terminate the algorithm
With this strategy, & which is also used to terminate the inner loop, can initially take larger values and gradually becomes smaller. In this way, the number of calls the LMO after ' iiterations is
millorrree Er
Also, due to (18), will be of (11/e)). Eventually, this implies O minocrci
calls to the LMO.
28


Reviews:
[{"review_id": "F73fiAG387", "reviewer": "Reviewer_YETC", "summary": "The article presents a Frank-Wolfe variant (also called projection-free method) DC-FW to minimize a difference of convex functions.\nA proof of rate of convergence matching previously known results is presented.\nIn case of strongly convex constraint set, an improvement for the rate of convergence according to linear minimization oracles is proved.\nTwo main experiments are conducted to compare the performances of the DC-FW against algorithms found in the literature.", "questions": "Here are some questions and remarks I had while reading the paper:\n- Line 22-24 Please provide a roof or reference that \"any smooth function can be expressed as a DC decomposition\".\n- In Definition 1, the authors are actually defining a generalized Bregman divergence. See  paragraph 2.2 in  K. C. Kiwiel. _Proximal minimization methods with generalized Bregman functions_. SIAM journal on control and optimization, 35(4):1142–1168, 1997.\n-  Line 120 Please add \"under assumption of $g$ differentiability\"\n- Line 126 Maybe write the formula with a $min$\n  $$\\hat \\Phi_t(x_{t+1}) - \\hat \\Phi_t(x) \\leq \\epsilon/2, \\; \\forall x \\in \\mathcal{D}$$ \n- Line 135-136 Isn't the lsc assumption implied by $L$-smoothness?\n- Line 145-146 \"we can always express as a difference of strongly  convex functions by adding the same quadratic term to both f and g. In this case, subproblem \" proof or reference?\n- Line 168-169 \"but rather focus on the classical FW algorithm\" Where in the Khamaru & Wainwright reference do we have a mention to FW?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\nThe paper is well organized and well written.\nThe setting and contributions are clearly \npresented in the introduction.\nThe paper provides theoretical contribution on the convergence rate \nfor DC programming using FW over strongly convex set.\nThe efficiency of DC-FW is demonstrated\nthrough two experiments in paper:\n - Quadratic Assignment Problem (QAP) with  comparisons conducted over **134 datasets**\n - Alignment of Partially Observed Embeddings for 300-dimensional English and French word embeddings.\n The appendix also contains additional experiments with other variants of the algorithm for QAP and additional numerical experiments on neural network training.\n\n**Weaknesses:**\n\nThe influence of the choice of the DC decomposition on the convergence rate is not discussed.\nIn section 4., we are shown two special cases of DC decomposition leading respectively to a gradient sliding problem and proximal point problem for the subproblem of DC-FW. Thus, a  comparison of  between gradient sliding algorithms and proximal point algorithms might be a starting point for a discussion.", "was_revised": true, "final_justification": "The authors have answered to all my questions and clarified what I've misunderstood. Thus, I retain my current score for the paper.", "rebuttal": "We thank the reviewer for their detailed review and useful suggestions.\n\n**W:** We appreciate this suggestion. The influence of the DC decomposition on the behavior of the DC gap was central to our thinking while writing the paper, as reflected in the paper’s abstract and main narrative. That said, we agree that demonstrating this explicitly in the specific settings of Sections 4.1 and 4.2 would greatly improve clarity. In response, we have conducted additional numerical experiments on some functions in 2D, where we visualize how different DC decompositions affect the notion of stationarity captured by the DC gap. Unfortunately, due to this year’s rebuttal format, we are unable to upload figures. However, we have included a table that showcases our main observations from one such example, and we kindly refer the reviewer to our answer to Q3 for Reviewer ydyb for further details on this example. \n\n**Q1:** Let $\\phi : \\mathbb{R}^n \\to \\mathbb{R}$ be an $L$-smooth function:\n$$ \n|| \\nabla \\phi(x) - \\nabla \\phi(y) || \\leq L ||x - y||, \\quad \\forall x,y \\in \\mathbb{R}^n.\n$$\n\nThen, $\\hat{\\phi}(x) = \\frac{L}{2}||x||^2 - \\phi(x)$ is convex, since $\\forall x,y \\in \\mathbb{R}^n$, we have\n\\begin{aligned}\n\\langle \\nabla \\hat{\\phi}(x) - \\nabla \\hat{\\phi}(y), x - y \\rangle \n& = L ||x-y||^2 - \\langle \\nabla \\phi(x) - \\nabla \\phi(y), x - y \\rangle \\\\\\\\\n& \\geq L ||x-y||^2 - || \\nabla \\phi(x) - \\nabla \\phi(y) || \\cdot || x - y || \\\\\\\\\n& \\geq L ||x-y||^2 - L || x - y||^2 \\\\\\\\\n& = 0\n\\end{aligned}\nwhere the first inequality is due to Cauchy-Schwarz, and the second one follows from the smoothness of $\\phi$. \n\nWe can show convexity of $\\frac{L}{2}||x||^2 + \\phi(x)$ in a similar way. \nHowever, this follows immediately from the observation that smoothness is preserved under negation: If $\\phi$ is $L$-smooth, then $-\\phi(x)$ is $L$-smooth as well. Applying the previous result to $-\\phi(x)$, we conclude that $\\bar{\\phi}(x) = \\frac{L}{2}||x||^2 - (-\\phi(x)) = \\frac{L}{2}||x||^2 + \\phi(x)$ is also convex. \n\n**Q2:** The generalized Bregman Divergence as in (Kiwiel, 1997) is defined as\n\n$$D_h(x,y) = h(x) - h(y) - \\langle u ,x-y \\rangle , \\quad u \\in \\partial h.$$\n\nAlthough it looks similar to the gap function in Definition 1, the main difference lies in the subgradient component. Our subgradient belongs to another function and not $h$. For example, if the DC decomposition is $\\phi(x) = h(x) - g(x)$, our gap becomes\n$$gap(x) =\\max_y \\left\\\\{ h(x) - h(y) - \\langle u ,x-y \\rangle \\right\\\\} , \\quad u \\in \\partial g.$$\n\n**Q3:** We will rephrase this sentence as suggested to avoid confusion. \n\n**Q4:** We will rewrite the formula using min as suggested. \n\n**Q5:** Yes it does, thank you for pointing out. We will remove the redundant assumption. \n\n**Q6:** A standard definition of strong convexity states that a function $\\psi : \\mathbb{R}^n \\to \\mathbb{R}$ is $\\mu$-strongly convex (with respect to the Euclidean norm) if and only if $\\psi(x) - \\frac{\\mu}{2}||x||^2$ is convex. Now suppose $\\phi(x) = f(x) - g(x)$ is a DC decomposition, hence $f$ and $g$ are convex. Then, we can define:\n$$f’(x) = f(x) + \\frac{\\mu}{2}||x||^2 \\quad \\text{and} \\quad g’(x) = g(x) + \\frac{\\mu}{2}||x||^2.$$\nThis gives another DC decomposition $\\phi(x) = f’(x) - g’(x)$ where both $f’$ and $g’$ are $\\mu$-strongly convex by construction.\n\n**Q7:** Thank you for your careful reading and for raising this point. Your question led us to realize that there are two versions of Khamaru & Wainwright's paper, one presented at ICML and a longer version published in JMLR. The Frank-Wolfe method appears only in the JMLR version (as Algorithm 3, in Section 2.5), whereas we mistakenly cited the ICML version. We will correct this reference."}, {"review_id": "pPutAvkBkc", "reviewer": "Reviewer_KRwt", "summary": "The paper proposes DC-FW, a projection-free optimization framework for nonconvex problems expressible as the difference of convex (DC) functions. By combining the DC Algorithm (DCA) with Frank-Wolfe (FW) iterations to solve the linearized subproblems, the authors derive an algorithm that maintains the scalability of FW while gaining flexibility from DC decomposition.", "questions": "Q1. Could the authors clarify how to choose an optimal DC decomposition for a given objective?\n\nQ2. Is gradient reuse always beneficial?\n\nQ3. Can your method be extended to stochastic settings?\n\nQ4. How does the algorithm behave when $g$ is not differentiable and subgradients are hard to compute?", "limitations": "- Line-search or step-size tuning in practice might be sensitive, especially in large-scale or noisy settings.\n\n- No statistical significance reported for experimental results.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n- A unified view of DC and FW with tight non-asymptotic convergence analysis.\n- Accommodates multiple DC decompositions for the same objective.\n- Avoids projections—a major bottleneck in constrained optimization.\n- Via decomposition that reuses gradients.\n- Strong results in classical nonconvex domains.\n\n**Weaknesses**\n\n- Missing real-world deep learning examples: Experiments focus on classical problems.\n- Quantitative gains from reusing gradients are not isolated in experiments.", "was_revised": true, "final_justification": "I thank the authors for nicely and carefully addressing my comments. Considering the contribution and results of this work I raised my score.", "rebuttal": "We thank the reviewer for their thoughtful comments and questions. \n\n**W1:** In the supplementary material, we presented a simple neural network experiment to illustrate that projection-free methods can perform reasonably well with a suitable DC decomposition. This is interesting because the FW methods have historically not been very successful for neural network training. However, our goal in this experiment is not to position FW as a replacement for state-of-the-art optimizers in large-scale modern applications. Finding the right decompositions for such modern neural architectures in a nontrivial task, and benchmarking against advanced optimizers like Adam, AdamW, or Muon would require substantial additional effort beyond the scope of our study. \n\n**W2:** We appreciate this feedback. As noted in Section 5.2, DC-FW reuses the subgradients of g, resulting in only 88 oracle calls over 10,000 total inner iterations in the embedding alignment experiment. However, we realize we did not report similar results in the conditional gradient sliding setting.\n\nAfter the submission, we observed that our framework naturally enables gradient sliding for DC functions where $f$ is smooth and $g$ is nonsmooth. This is more general than the smooth setting we considered in Section 4.1. Specifically, since $\\frac{L}{2}||x||^2 - f(x)$ is convex for $L$-smooth $f$, we can define a new DC decomposition \\phi(x) = f’(x) - g’(x) with\n$$\nf’(x) = \\frac{L}{2}||x||^2 \\quad \\text{and} \\quad g’(x) = g(x) + \\frac{L}{2}||x||^2 - f(x).\n$$\nApplying DC-FW to this decomposition economizes on both gradient evaluations of $f$ and subgradient evaluations of $g$. This problem setting also covers our experiment in Section 5.2. We will incorporate this variant into this experiment.\n\n**Q1:**  This is an important question, but unfortunately there is no universally optimal way to choose a DC decomposition. Our goal is not to propose a one-size-fits-all projection-free method; such a goal would be unrealistic given the complexity of nonconvex optimization. Our main contribution lies in highlighting how the DC decomposition provides a design space for projection-free methods, where one can balance computational cost and optimality criteria depending on the problem. That said, in certain settings, the trade-offs can be clearly understood; we kindly refer the reviewer to our answer to W2 for Reviewer iHJV, where we discuss two such example cases in detail.\n\n**Q2:** This question is related to the previous one and to our answer to W2 for Reviewer iHJV. The short answer is: *not necessarily*. While the method improves the worst-case gradient oracle complexity for the given problem class, success in nonconvex optimization is not only measured by the rate of convergence, but it also depends on the type of stationary points the method finds. We expect the method to perform well in practice for problems where f is moderately well-conditioned, or in applications such as neural network training where (stochastic) gradient-type methods are empirically known to be effective. \n\n**Q3:** There are at least two natural ways to extend our results to a stochastic setting. First, one can retain the deterministic DCA framework but solve the subproblems using a stochastic FW variant. Second, one can consider a stochastic variant of DCA itself. We note, however, that stochastic DCA variants are less developed in the literature, and existing approaches we are aware of rely on variance-reduction techniques such as SVRG or SAGA. We refer the reviewer to [R1] and [R2] (and references therein) for more details on stochastic FW and stochastic DCA methods, respectively. \n\n[R1] Yurtsever et al., Conditional gradient methods via stochastic path-integrated differential estimator, 2019. \n\n[R2] Le Thi et al., Stochastic DCA with variance reduction and applications in machine learning, 2022. \n\n**Q4:** Since DCA relies on linearizing $g(x)$, it is effective only when its (sub)gradients are accessible. For many common nonsmooth terms such as ReLU, norms, or support function, subgradients are either in closed form or can be efficiently approximated using numerical linear algebra techniques. This is for example the case in Section 5.2, where $g$ is the nuclear norm, and its subgradient can be computed via a singular value decomposition or can be approximated using Newton–Schulz iterations. It is also worth noting that approximate subgradients are available for any prox-friendly function.\n\n\n**Limitations:** In response to the reviewer’s comment on statistical significance, we have also conducted additional experiments. Note that the alignment experiment is a deterministic experiment. We repeated all QAP experiments over 10 Monte Carlo runs and computed 90% confidence intervals (shown in brackets in the form of \"**average** [lowerbound upperbound]\"). A summary of these extended results is presented in the table below:\n\n| Method     | FW          | DCFW         | DCFW2        | DCFW3       | CGS    |\n|----|-------|---------------|---------------|-----------|----------|\n| **FW**       | 0.0                     | **44.50** [41.82, 47.18]     | **52.40** [48.61, 56.19]     | **50.20** [47.54, 52.86]     | **59.80** [56.12, 63.48]     |\n| **DCFW**     | **73.40** [70.80, 76.00]    | 0.0     | **62.10** [59.10, 65.10]     | **58.40** [56.23, 60.57]     | **68.70** [66.17, 71.23]     |\n| **DCFW2**    | **66.90** [63.20, 70.60]    | **51.50** [48.25, 54.75]     | 0.0         | **48.40** [46.05, 50.75]     | **69.40** [67.76, 71.04]     |\n| **DCFW3**    | **69.10** [65.94, 72.26]    | **54.50** [52.64, 56.36]     | **56.20** [54.48, 57.92]     | 0.0           | **70.50** [67.88, 73.12]     |\n| **CGS**  | **59.20** [55.08, 63.32]    | **46.40** [43.76, 49.04]     | **38.00** [36.61, 39.39]     | **37.80** [34.96, 40.64]     | 0.0       |\n\nThe table shows the one on one comparison between the performance of different methods against each other. The inputs represent the average number of datasets (among 10 experiments), that a method on each row wins (achieves lower assignment error) against other methods in each column. For example, DCFW performs better than the CGS method  in **68.70** cases on average with 90% confidence interval [66.17, 71.23].  On the other hand, CGS did better than DCFW in **46.40** cases on average with 90% confidence interval [43.76, 49.04]."}, {"review_id": "uU0OPRngsn", "reviewer": "Reviewer_AnH8", "summary": "In this paper, the authors investigate the Frank-Wolfe algorithm for nonconvex constrained optimization problems with the difference-of-convex structure $f(x) – g(x)$. For this type of problems, a new Frank-Wolfe variant called DC-FW is proposed, which matches the best FW step complexity and achieves a better gradient complexity with respect to function $g(x)$. For strongly-convex feasible domain, it achieves better minimization oracle complexity when the objective functions are strongly-convex or Lipschitz smooth.", "questions": "1. Can we split any nonconvex objective function into the dffference of two convex functions? For example, we have a two-layer neural network, how should we convert it to a DC problem?\n2. After converting a nonconvex problem to a DC problem, will DC-FW still suffer from the saddle point issue?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength\n\nThe authors design a novel and efficient variant of Frank-Wolfe algorithm to solve difference-of-convex optimization problems. The new method matches the best FW step complexity and achieves a better gradient complexity with respect to function $g(x)$. For strongly-convex or Lipschitz smooth problems, the minimization oracle complexity can be improved from $O(1/\\epsilon^2)$ to $O(1/\\epsilon^{\\frac{3}{2}})$.\n\nWeakness\n\nAlthough the generality of the method is clarified in the introduction section, it is not trivial to convert a practical nonconvex loss function to a DC problem, especially for some complicated tasks in CV or NLP.", "was_revised": true, "final_justification": "My concerns are addressed by the rebuttal. I will retain my score.", "rebuttal": "We thank the reviewer for their thoughtful questions.\n\n**W/Q1:** We agree that finding a practical DC decomposition for modern neural architectures used in CV or NLP is a nontrivial task. However, there is growing interest in developing DC decompositions for neural network training. Recent works have already demonstrated such decompositions for multilayer perceptrons and convolutional neural networks [R1, R2], and we expect further progress in this direction. \n\nAs for whether any nonconvex objective function can be expressed as a DC function: the strict answer is no. However, DC programming captures a very broad class of nonconvex problems. Verbatim quote from [R3], “DC programs cover most of all nonconvex realistic optimization problems” (see p.6 for a technical discussion). For example, the maximum of a family of twice differentiable functions is DC, any function with locally Lipschitz continuous gradients is DC, the sum or product of two (real-valued) DC functions is also DC. It is important to emphasize, however, that these are existence results. Even when a DC decomposition exists, finding one that is useful for optimization can be challenging.\n\n[R1] Askarizadeh et al., Convex-concave programming: An effective alternative for optimizing shallow neural networks, 2024.\n\n[R2] Awasthi et al., DC-programming for neural network optimizations, 2024. \n\n[R3] Le Thi & Pham Dinh, DC programming and DCA: thirty years of developments, 2018.\n\n**Q2:** This is an interesting question. The short answer is: yes, the method can still suffer from saddle point issues. The DC framework is quite general and also covers standard methods such as gradient descent and the proximal point method as special cases. Since gradient descent is a special case of DCA, all its limitations naturally extend to DCA in general. However, specific DC decompositions may be more or less prone to such issues. The intuition is that DCA retains the function $f$ and linearizes $g$ at each iteration, discarding higher-order information in $g$, both in the algorithm and in the resulting notion of “DC gap” (note that the DC gap is decomposition-dependent). Consequently, a decomposition that retains more of the problem’s geometric structure in $f$ can yield a gap function that more accurately reflects the landscape of the original objective. To illustrate this phenomenon, we conducted a numerical experiment in 2D showing how different DC decompositions affect the behavior of the gap function in smooth nonconvex settings (specifically, we compare the settings from Sections 4.1 and 4.2). We kindly refer the reviewer to our response Q3 for Reviewer ydyb for further details on this example."}, {"review_id": "isHalPo444", "reviewer": "Reviewer_iHJV", "summary": "This paper introduces a DC Frank-Wolfe algorithm for DC programming. The proposed method achieves a first-order stationary point in\n$O(1/\\epsilon^2)$ linear minimization oracle calls. When the set is strongly convex, the oracle complexity improves to $O(1/\\epsilon^{1.5})$. The authors also use the proposed method to smooth optimization and specific decompositions can achieve the gradient computation oracle complexity the same as gradient descent.", "questions": "1. For the general DC functions, what is the relation bewteen gap_{DC} and $||\\hat \\partial \\phi||$ with $\\hat\\partial \\phi\\in \\partial \\phi$? How to translate gap_{DC} to $||\\hat \\partial \\phi||$ ?\n\n2. What is the benifit of DC structure in nonconvex programming? Can we achieve faster convergence rate than the standard GD or PGD by employing the DC structure?\n\n3. What is the advantage of the DC-FW view compared to the standard analysis framework in Section 4.1?\n\n4. What is the advantage of DC-FW compared to ADMM and its linearized variant.", "limitations": "1. For general DC programming, the proposed method seems a straightforward application of the FW algorithm to DC programming.\n\n2. For the special cases of smooth nonconvex optimization, the DC programming framework seems unnecessary.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n1. For general DC programming, this paper introduces a DC Frank-Wolfe algorithm, which achieves a first-order stationary point in\n$O(1/\\epsilon^2)$ linear minimization oracles. When the set is strongly convex, the calls of linear minimization oracles improve to $O(1/\\epsilon^{1.5})$. \n\n2. For the special cases of smooth nonconvex optimization, the proposed DC-FW algorithm with a specific decomposition can achieve a $\\epsilon$-suboptimal stationary point measured by $|| x_t - proj_D(x_t-\\nabla \\phi(x_t)) ||^2\\leq gap_{DC}\\leq \\epsilon$ after $O(1/\\epsilon)$ gradient evaluations, which is the same with gradient descent. The proposed DC-FW algorithm is projection-free and it needs $O(1/\\epsilon^2)$ linear minimization oracle calls. When the set is strongly convex,  the oracle complexity improves to $O(1/\\epsilon^{1.5})$.\n\nWeaknesses:\n\n1. For general DC programming, after reading Section 3, it seems that the proposed method is a straightforward application of the FW algorithm to DC programming. The enhanced performance on strongly convex sets directly applies the theoretical results established in (Garber & Hazan, 2015) and this paper contributes nothing new. The novelty and originality seem below the bar of NeurIPS.\n\n2. For the special cases of smooth nonconvex optimization, I wonder whether the DC programming framework is necessary. For problem (7), we can apply the general projected gradient mehtod with the following iterations: \n\n$x_{t+1}=argmin_{x\\in D} \\frac{L}{2} || x - (x_t-\\frac{1}{L}\\nabla \\phi(x_t)) ||^2=argmin_{x\\in D} \\frac{L}{2}||x||^2 - <Lx_t-\\nabla \\phi(x_t), x>$\n\nWhen projection is forbidden, we can use the FW algorithm to solve the above problem in the second equation, that is, subproblem (9) in the main paper. Using the standard analysis of inexact projected gradient descent, we can achieve the $O(1/\\epsilon)$ gradient oracle complexity (the same with PGD). Using the standard analysis of FW algorithm and the theory in (Garber & Hazan, 2015), we can achieve the $O(1/\\epsilon^2)$ and $O(1/\\epsilon^{1.5})$ linear minimization oracle complexity, respectively. The DC programming framework seems unnecessary. We can get the same algorithm and achieve the same complexity using existing standard techniques.\n\n3. For the special cases of smooth nonconvex optimization, when using the decomposition in 4.2, the gradient oracle complexity becomes $O(1/\\epsilon^2)$, which is higher than the $O(1/\\epsilon)$ complexity of PGD.\n\n4. The experiment is inefficient. This paper only compares the posed DC-FW with the original FW algorithm. Suggest also comparing DC-FW with ADMM and its linearized variant (important).\n\nIn conclusion, this paper is well-written. However, the theoretical contribution and novelty are limited.", "was_revised": true, "final_justification": "I have read the rebuttal and the other reviewers' comments. Most of my concerns have been addressed.", "rebuttal": "We thank the reviewer for their detailed review and thoughtful questions. \n\n**W1:** We respectfully disagree. We believe the reviewer has misinterpreted our contribution as isolated derivations of several projection-free algorithms. In contrast, our work proposes a reinterpretation of projection-free optimization as a modular framework shaped by the DC structure. Each decomposition induces its distinct algorithmic effect, and this perspective is not captured by standard analyses of projection-free methods. We believe this viewpoint offers a novel and valuable lens and would be of interest to the NeurIPS audience.\n\n**W2:** The connection to the projected gradient method is clearly stated in our paper. In lines 187–191, we write:\n>When DCA is applied to this formulation with exact solutions to the subproblems, it recovers the projected gradient method. [...] In other words, DC-FW applied to this formulation simplifies to an inexact projected gradient method, where Frank-Wolfe is used to approximately solve the subproblems. This naturally leads to a nonconvex variant of the conditional gradient sliding algorithm.\n\nWe believe this criticism arises from the misunderstanding of our contribution as isolated derivations of several projection-free methods. In contrast, our central message is that the DC framework provides a versatile design tool for constructing and analyzing a broad class of projection-free algorithms. It provides a unified (and surprisingly simple) analysis. More importantly, the guarantees are based on the *DC gap*, which is a generic measure of approximate stationarity (resp., criticality, for nonsmooth problems), and directly reflects the characteristics of the chosen decomposition. This provides insight into which decompositions are better suited in which settings. Since DCA linearizes the $g(x)$ component, the curvature of $g$ is discarded while the curvature of $f$ is preserved. As a result, ill-conditioned terms are better placed in $f$ rather than $g$, to achieve a better notion of stationarity. However, there is a trade-off here, because DC-FW queries the first-order oracle of $f$ more frequently than $g$. \n\nAnother trade-off could be the choice of strong convexity in the decomposition. Given any DC decomposition, one can generate a new decomposition with arbitrarily large strong convexity constants simply by adding and subtracting a quadratic term: $f_{\\mu}(x) = f(x) + \\frac{\\mu}{2}||x||^2$, $g_{\\mu}(x) = g(x) + \\frac{\\mu}{2}||x||^2$. The notion of DC gap is strongest when $g$ is merely convex. To see this: \n\n\\begin{aligned}\n\\text{gap}\\_{DC}^{\\mu}(x_t)\n&= \\max\\_{x \\in \\mathcal{D}} f(x_t) + \\frac{\\mu}{2}||x_t||^2 - f(x) - \\frac{\\mu}{2}||x||^2 - \\langle \\nabla g(x_t) + \\mu x_t, x_t - x \\rangle \\\\\\\\\n&= \\max\\_{x \\in \\mathcal{D}}  f(x_t) - f(x) - \\langle \\nabla g(x_t), x_t - x \\rangle - \\frac{\\mu}{2}||x_t - x||^2  \\\\\\\\\n&\\leq \\max\\_{x \\in \\mathcal{D}} f(x_t) - f(x) - \\langle \\nabla g(x_t), x_t - x \\rangle \\\\\\\\\n&= \\text{gap}\\_{DC} (x_t).\n\\end{aligned}\n\nThis shows that as we artificially increase strong convexity, DC gap becomes less sensitive to the actual structure of the problem. However, when $\\mathcal{D}$ is also strongly convex, we know that strong convexity of $f$ improves the convergence rate for the subproblems. Therefore once again we face a trade-off between computational efficiency and the notion of stationarity. \n\nThere is no single universally best method in nonconvex optimization. Our goal is not to propose a one-size-fits-all projection-free method; that would be an unrealistic goal. We instead emphasize the flexibility of the DC decompositions, and how it can be used to balance computational cost and meaningful notions of optimality. Practitioners can try standard FW on nonconvex problems and conclude that it underperforms in their settings. Our work shows that there is more to FW in the nonconvex setting, and that the DC perspective offers a simple and flexible framework for making it work. \n\n**W3:** PGM has convergence guarantees in terms of $\\frac{L}{2}||x_k - proj_{\\mathcal{D}}(x_k - \\frac{1}{L}\\nabla \\phi(x_k))||^2$. It does not guarantee convergence to a point satisfying $\\frac{L}{2}||x_k - prox_{\\frac{1}{L}\\phi + \\iota_\\mathcal{D}}(x_k)||^2 \\leq \\epsilon$ in finite time. The gap between these two quantities can be significant particularly when $\\phi$ is ill-conditioned. \n\n**W4:** The comparison with ADMM and its linearized variant is not directly relevant to our setting. Our goal in the experiments is not to compete with proximal or dual-based methods, but to explore how different DC decompositions lead to qualitatively different projection-free algorithms. Therefore, we focus on standard FW methods and DC-FW variants using different decompositions, which is aligned with the core objective of our study. That said, if the reviewer has a specific ADMM variant in mind for a particular experiment with references, we would be happy to include it (potentially in the supplementary material due to space constraints).\n\n**Q1:** Please note that $\\partial \\phi$ is not always well-defined when $\\phi$ is nonconvex, since the subdifferential is only properly defined for convex functions (or defined under more refined notions such as Clarke or limiting subdifferentials). It is important to note that even when $\\phi$ is convex but nonsmooth, the subgradient norm $||\\hat{\\partial} \\phi||$ is not a suitable convergence measure. The gradient-norm-based stationarity condition used in smooth nonconvex optimization does not extend meaningfully to nonsmooth settings.  For example, consider the function $\\phi(x) = |x|$. Its subdifferential is given by $\\text{sign}(x)$ for $x \\neq 0$ and the entire interval $[-1, 1]$ at $x = 0$. Although $x = 0$ is the unique stationary point, the subgradient norm remains constant at $1$ as long as $x \\neq 0$, regardless of how close we are to the solution. Therefore, subgradient norm cannot be used as a meaningful measure of approximate stationarity in nonsmooth settings.\n\n**Q2/Q3:** These questions are related to W2 and the discussion above addresses them. One additional point worth mentioning is that the DC gap defines a stronger notion of stationarity than the classical projected gradient mapping in Section 4.1. In Lemma 10, we show that\n$$\\text{gap}\\_{DC}(x_t) \\geq \\text{gap}\\_{PGM}^L(x_t).$$\nThis inequality is in fact strict except when both sides are zero (i.e., except when $x_t$ is a stationary point). It is easy to see in the derivation in Appendix A.6, equality holds when\n$$\n\\langle \\nabla \\phi(x_t), x_t - x_t^\\star \\rangle = L ||x_t - x_t^\\star||^2,\n\\quad \\text{where} \\quad x_t^\\star = \\text{proj}\\_{\\mathcal{D}} (x_t - \\frac{1}{L} \\nabla \\phi(x_t)), \n$$\nwhich happens only when $x_t$ minimizes the proximal subproblem, implying $x_t$ is stationary. For any other point, the DC gap is strictly larger than the projected gradient norm. \n\n**Q4:** This question is related to W4 and the discussion above addresses it. We explore how different DC decompositions influence projection-free optimization algorithms within a unified framework. To our knowledge, standard ADMM is not designed for DC optimization and it is not projection-free. If the reviewer has specific variants of ADMM in mind that are particularly relevant to our problem template, we would greatly appreciate references. We are happy to include a discussion (or even additional experiments) if there is a meaningful connection."}, {"review_id": "9Ob6eeS3f7", "reviewer": "Reviewer_ydyb", "summary": "This paper introduces DC-FW, a novel projection-free optimization framework for nonconvex problems formulated as the difference of convex (DC) functions. It combines the classical DCA (Difference-of-Convex Algorithm) structure with the Frank-Wolfe method to solve DC problems without projections. The paper provides theoretical convergence guarantees using a new gap measure (gapDC), and demonstrates that in certain cases, the method achieves improved complexity bounds compared to standard FW. Numerical experiments on QAP, embedding alignment, and neural network training show the versatility and effectiveness of DC-FW.", "questions": "1.\tWhile Figure 2 presents FW gap plots against iterations, SVD calls, and wall-clock time, it does not reflect the proposed gapDC measure introduced in the paper. Moreover, the plots do not include theoretical reference lines or convergence slopes (e.g., $O(1/t)$), which would help verify the claimed complexity bounds.\n2.\tWhy are there no comparisons with standard optimizers (e.g., Adam) in the neural network experiments? How does DC-FW perform in such settings? \n3.\tCan the authors elaborate or visualize the effect of different DC decompositions on performance and convergence? \n4.\tPlease clarify the computational cost per iteration of DC-FW compared to CGS and FW-M, especially in large-scale settings. \n5.\tCould the authors improve the readability of the QAP results table (e.g., using heatmaps or grouped bar plots with clearer labels)? Additionally, it would be helpful to analyze why DC-FW performs worse than FW on certain QAP instances, to better understand the limitations of the proposed method.\n6.\tIn Figure 4 of the supplementary material, some of the test accuracy curves — particularly for CIFAR-10 under certain constraint values — exhibit sharp downward spikes followed by immediate recovery. Could the authors clarify the cause of this behavior? Is it due to instability in the line search, stochastic subgradient estimation, or numerical issues arising from the projection-free update?", "limitations": "N/A", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1.\tThe paper addresses a relevant and challenging class of nonconvex problems in a principled way. \n2.\tThe theoretical contributions are solid, and the proposed gapDC measure is well-motivated and rigorously analyzed. \n3.\tThe framework is general, supports multiple DC decompositions, and includes complexity analysis under different conditions. \n4.\tNumerical experiments are diverse, covering discrete optimization, matrix problems, and deep learning.\nWeaknesses:\n1.\tThe theoretical innovation primarily lies in combining known components (DCA + FW), and is more of a well-engineered synthesis than a fundamentally new algorithm. \n2.\tThe numerical experiments, while varied, lack strong verification of theoretical claims such as complexity bounds (e.g., no clear log-log error vs iteration plots). \n3.\tThe neural network experiments are weakly motivated and lack comparison with standard optimizers (e.g., Adam or SGD). \n4.\tPresentation of results (especially the QAP table) is dense and difficult to interpret; no standard deviations or statistical significance is reported.", "was_revised": true, "final_justification": "The authors cleared some of my doubts during the rebuttal. Other reviewers also raised good points, and I took due notes.", "rebuttal": "We thank the reviewer for their detailed review and thoughtful questions.\n\n**W1:** Our paper is transparent about the connections to existing methods. Our contribution lies in reinterpreting projection-free optimization as a modular framework shaped by the DC structure. This viewpoint highlights that each DC decomposition induces a qualitatively different algorithmic behavior, which is not captured by the standard FW methods. We believe this viewpoint offers a novel and valuable lens and would be of interest to the NeurIPS audience. Please refer to our response to W2 for Reviewer iHJV for some concrete examples of the trade-offs exposed through the DC framework. \n\n**W2:** We appreciate this constructive feedback. The goal of our current experiments is to demonstrate the impact and practical differences between DC-FW variants arising from different DC decompositions. Verifying the theoretical complexity bounds was not the primary focus of our initial experiments. That said, we will include additional experiments to empirically verify the theoretical complexity bounds for completeness (potentially in the supplementary material due to space constraints). We will also include illustrations comparing different notions of gap functions to further clarify the distinctions between convergence criteria. \n\n**W3:** We respectfully disagree. FW has historically not been very successful for neural network training. Our goal in this experiment is not to propose FW as a replacement for optimizers like Adam or SGD. We simply illustrate that by exploiting the right geometric structure, FW can be made to perform reasonably well in a problem where it has been traditionally ineffective. This aligns with the core contribution and main message of our paper. The problem is therefore well-motivated, but our motivation is not to tune FW for large-scale neural network architectures or to benchmark against state-of-the-art optimizers, which would require substantial additional effort beyond the scope of our study. \n\n**W4:** We appreciate this feedback and will improve the presentation of the QAP results. We can also add a table in the appendix to provide complete numerical data. If the reviewer has specific suggestions, we would be happy to incorporate them. \n\n**Q1:** We chose to present the results using the FW gap since it is naturally evaluated by all three methods. For DC-FW, this corresponds to the gap computed in the first inner iteration of each round. While DC-FW also computes the DC gap (approximately, at the final inner iteration), evaluating it for FW-K and FW-M would incur additional computational overhead. Since we report wall-clock time, we did not want to disadvantage the baseline methods by adding this cost. That said, we agree with the reviewer that showing results also with the DC gap would be valuable to verify the theoretical rates. We will conduct these additional experiments for completeness. (We also note that the FW gap is an upper bound on the DC gap, since $f$ is convex.) \n\nIt is also worth noting that an $O(1/K)$ rate appears as a straight line with slope -1 in a log-log plot. As seen in Figure 1 [left panel], the rates (in terms of FW gap) for DC-FW and FW-M follow with $O(1/K)$ (where $K$ is the total number of inner iterations for DC-FW), while FW-K exhibits a slightly slower rate. All methods outperform the worst-case $O(1/\\sqrt{K})$ bound in this experiment. We will incorporate additional figures (potentially in the supplementary material, due to space constraints) to showcase the empirical convergence rates in detail. \n\n**Q2:** This question relates to W3, and the discussion above addresses it in part. That said, in response to the reviewer’s suggestion, we conducted additional tests. In general, DC-FW performs very similarly to SGD, which is expected given the close connections between the two algorithms under specific DC decompositions. \n\n**Q3:** We appreciate this suggestion, as it truly helps clarifying our main messages in the paper. We have numerically visualized the impact of DC decomposition on gap functions for smooth nonconvex problems in 2D. Unfortunately, due to this year’s rebuttal format, we cannot include figures, but we describe a representative example below. \n\nConsider $\\phi(x_1,x_2) = \\text{sin}(\\pi x_1) ~ \\text{cos}(\\pi x_2)$ over the domain $[-1,1]^2$, with smoothness constant $L=\\pi^2$. We evaluate both the PGM gap and the PPM gap at first-order stationary points (a local minimum, a saddle point, and a local maximum), as well as at small perturbations of these points. We use step size and prox parameter $1/L$. See the table below:\n\n|   x₁   |   x₂   |        Type         |  PGM gap  |  PPM gap  |\n|--------|--------|---------------------|-----------|-----------|\n| -0.50  |  0.00  | Local minimum       |  0.0000   |  0.0000   |\n| -0.49  |  0.01  | Local-min perturbed |  0.0010   |  0.0002   |\n|  0.00  |  0.50  | Saddle              |  0.0000   |  0.0000   |\n|  0.01  |  0.51  | Saddle perturbed    |  0.0010   |  0.1109   |\n|  0.50  |  0.00  | Local maximum       |  0.0000   |  0.0000   |\n|  0.51  |  0.01  | Local-max perturbed |  0.0010   |  0.1110   |\n\nThe PGM gap behaves similarly across all stationary points and their perturbations. This is expected because it comes from the decomposition $f(x) = \\frac{L}{2}||x||^2$ and $g(x) = \\frac{L}{2}||x||^2 - \\phi(x)$. Since $g$ is linearized, PGM gap completely discards the curvature information in $\\phi$. In contrast, the PPM gap can clearly differentiate between the three types of stationary points. It is relatively flat around the local minimum but sharp near the saddle and local maximum. This behavior arises from the underlying decomposition, $f(x) = \\frac{L}{2}||x||^2 + \\phi(x)$ and $g(x) = \\frac{L}{2}||x||^2$. Since $f$ is not linearized, PPM gap can preserve curvature information in $\\phi$. \n\n**Q4:** The overall cost of DC-FW is:\n$$C\\_{DC-FW}=\\mathcal{O} \\left( T_{\\epsilon} \\left( C\\_{\\partial g} +  K_{\\epsilon} \\left( C_{\\nabla f} + C_{lmo} + d \\right) \\right) \\right)$$\nwhere $T_{\\epsilon}$ is the number of outer iterations, $K_{\\epsilon}$ is the number of inner iterations per outer step, $d$ is the problem dimension, $C_{\\partial g}$, $C_{\\nabla f}$, and $C_{\\text{lmo}}$ denote the cost of computing a subgradient of $g$, a gradient of $f$, and the linear minimization oracle, respectively. Importantly, both $T_{\\epsilon}$ and $K_{\\epsilon}$ scale with $\\epsilon^{-1}$, hence we get \n$$C\\_{DC-FW}=\\mathcal{O} \\left( \\epsilon^{-1} C\\_{\\partial g} +  \\epsilon^{-2}  \\left( C_{\\nabla f} + C_{lmo} + d \\right) \\right).$$\nIt is worth noting that $\\epsilon^{-2}$ improves to $ \\epsilon^{-3/2}$ if both $\\mathcal{D}$ and $f$ are strongly convex. \n\nThe cost of FW-K is given by\n$C\\_{FW-K}=\\mathcal{O} \\left( T_{\\epsilon}^{FK-K} \\left( C\\_{\\partial g} + C_{\\nabla f} + C_{lmo} + d \\right) \\right)$,\nwhere $T_{\\epsilon}^{FK-K}$ scales with $\\epsilon^{-2}$. Hence, the overall cost is\n$$C\\_{FW-K}=\\mathcal{O} \\left( \\epsilon^{-2} \\left( C\\_{\\partial g} + C_{\\nabla f} + C_{lmo} + d \\right) \\right).$$\nThe cost of FW-M is similar, except for an additional overhead from backtracking line search. Roughly, we have:\n$$C\\_{FW-M}=\\mathcal{O} \\left( \\epsilon^{-2} \\left( C\\_{\\partial g} + C_{\\nabla f} + C_{lmo} + K_{line-search}(C_{f} + d) \\right) \\right),$$\nwhere $K_{\\text{line-search}} \\geq 1$ is the number of line search steps per iteration, and $C_f$ denotes the cost of evaluating the function $f$. During line search, (sub)gradient and linear minimization oracles are not invoked, but function evaluations and basic arithmetic operations are performed. While line search improves the practical performance of the algorithm, it does not enhance the theoretical guarantees of FW-K in general.\n\nFor the specific setting of conditional gradient sliding, that we consider in Section 4.1, we have $f(x) = \\frac{L}{2} ||x||^2$ and $g(x) = \\frac{L}{2} ||x||^2 - \\phi(x)$. Hence, gradient of $f$ comes at the cost of $d$, and the gradient of $g$ comes at the cost of $d + C_{\\nabla \\phi}$, leading to \n$$C\\_{CGS}^{ours} =\\mathcal{O} \\left( \\epsilon^{-1} C_{\\nabla \\phi} +  \\epsilon^{-2}  \\left( C_{lmo} + d \\right) \\right).$$\nThis is similar to Qu et al.'s CGS variant, except for the constants. Our CGS strictly improves the constants against Qu et al., specifically, $T_{\\epsilon}$ is improved by a factor of $24$. Furthermore, Qu et al. require two FW subroutines (inner loops) per outer iteration, which increases the constants associated with $C_{\\text{lmo}}$ and introduces additional arithmetic operations, further increasing the constants in front of $d$.\n\n**Q5:** This question is related to W4 and the discussion above addresses it in part. The current table is in fact similar to a heatmap. We can improve its presentation with clearer labels or by using a heatmap instead. Additionally, we will include a table summarizing the key highlights from this experiment, such as how many times each method achieves the best objective value and relative speed comparisons. \n\nIn response to the reviewer’s suggestion, we have also conducted additional experiments. We repeated all QAP experiments over 10 Monte Carlo runs and computed 90% confidence intervals. Due to space limitations, a summary of these extended results is presented in the table in response to \"Reviewer KRwt, Limitations\".\n\n**Q6:** This occurs only rarely. We note that our current analysis does not account for stochastic gradients, though they are used heuristically in this experiment. Additionally, we employed an adaptive stopping criterion in these experiments. Especially when combined with stochastic gradients, it is possible that the projection subproblem is not solved with sufficient accuracy in some iterations, leading to such unexpected behavior. We believe this issue can be resolved through a more careful analysis that explicitly incorporates gradient noise."}]

Author rebuttal:

Meta-review: **Summary:** 
The paper considers constrained optimization problem whose objective is the difference of convex functions, classic Frank-Wolfe (FW) method and difference-of-convex algorithm are adopted which lead to the proposed DC-FW method. Theoretical analysis of the proposed scheme under different condition of the constraint set is provided, and numerical experiments are presented to validate the performance. 

**Strength:**
 - A novel and efficient variant of FW method to solve difference-of-convex optimization problem with constraint.
 - Theoretical guarantees with match the existing complexity bound.
 - Solid numerical experiments. 

**Weakness:**
 - The presentation of the paper can be improved for better clarity, including 1) discussions on comparison with existing approaches; 2) needs better explained motivation and challenges; 3) numerics can be further strengthened. 

**Reason of decision:** 
The topic of the paper and its presented result have potential broad interests to the community. During the rebuttal phase, most concerns from the reviewers are fairly addressed. However, incorporating them into the final version of the paper needs substantial work and the authors are recommended to make a thorough revision.
Decision: Accept (poster)