Efficient Quadratic Corrections for Frank-Wolfe Algorithms
Authors: Jannis Halbey
Seta Rakotomandimby
Mathieu Besançon
Sébastien Designolle
Sebastian Pokutta
Venue: NeurIPS 2025 poster ()
Keywords: Convex optimization
conditional gradient method
Frank-Wolfe method
Primary area: optimization

Abstract: We develop a Frank-Wolfe algorithm with corrective steps, generalizing previous algorithms including Blended Conditional Gradients, Blended Pairwise Conditional Gradients, and Fully-Corrective Frank-Wolfe.
For this, we prove tight convergence guarantees together with an optimal face identification property.
Furthermore, we propose two highly efficient corrective steps for convex quadratic objectives based on linear optimization or linear system solving, akin to Wolfe's Minimum-Norm Point algorithm, and prove finite-time convergence under suitable conditions.
Beyond optimization problems that are directly quadratic, we revisit two algorithms, Split Conditional Gradient and Second-Order Conditional Gradient Sliding, which can leverage quadratic corrections to accelerate the solution of their quadratic subproblems.
We show improved convergence rates for the first and prove broader applicability for the second.
Finally, we demonstrate substantial computational speedups for Frank-Wolfe-based algorithms with quadratic corrections across the considered problem classes.

Efficient Quadratic Corrections for Frank-Wolfe Algorithms
Jannis Halbey
Seta Rakotomandimby École nationale des ponts et chaussées, IP Paris Champs-sur Champs-su--Maree, France seta. wwtarrrkoootomannnbbebo.....ppp fr
Zuse Institute Berlin & TU Berlin Berlin, Germany
halbey8zib.cc
Mathieu Besançon
Sébastien Designolle
Université Grenoble Alpes, Inria, LIG, CNRS Grenoble, France
Zuse Institute Berlin Berlin, Germany designolleGzib.. de
mathieu. aeshieeu.beanccniiniiie
Sebastian Pokutta
Zuse Institute Berlin & TU Berlin Berlin, Germany
pokutta@zib.de
Abstract
We develop a Frank-Woon Wolfe algorithm with corrective steps, generalizing previous algorithms including Blended Conditional Gradients, Blended Pairwise Conditional Gradients, and Fully-Corrective Frank-Wolfs For this, we prove tight convergence guarantees together with optimal face identification property. Furthermore, we propose two highly efficient corrective steps for convex quadratic objectives based on linear optimization linear system solving, akin Wolfe's Minimum- Norm Point algorithm, and prove finite-time convergence under suitable conditions. Beyond optimization problems that directly quadratic, revisit two algorithms, Split Conditional Gradient and Second-Order Conditional Gradient Sliding, which can leverage quadratic corrections to accelerate the solution of their quadratic subproblems. We show improved convergence rates for the first and prove broader applicability for the second. Finally, we demonstrate substantial computational speedups for Frank- Wolfe-based algorithms with quadratic corrections across the considered problem classes.
Introduction
In this paper, we consider convex constrained optimization problems of the form
min fx).
where X' is compact, convex set and / is convex, differentiable function. A particularly interesting family of first-order methods for this setting is the class of Conditional Gradient (CG) or Frank- Wolfe (FW) methods [Levitin and Polyak 1966 Frank and Wolfe [956]. One major advantage of these methods is that they access X' only through a Linear Minimization Oracle (LMO), which solves linear subproblems over the set. The methods then construct solutions as convex combinations of the vertices returned by the LMO. In particular, these methods avoid costly projection steps while ensuring an (1//t) convergence rate in general and linear convergence rates in specific settings.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Over the years, several FW variants have been designed to exploit the so-called active ser, i.e., the vertices used to form the current iterate, the oldest and best-known variant being the Away-step Frank- Wolfe (AFW) [Guélat and Marcotte| 1986]. By maintaining the convex combination, these methods significantly reduce the number of LMO calls. Furthermore, they achieve accelerated convergence rates on polytopes for sharp functions, whereas standard FW remains at rate of (1)/t). Additionally, they have been shown to produce sparse solutions (constructed as convex combinations of few iterates), which motivated strong interest in FW methods for sparse optimization and machine learning applications. The Colly--orreeeive
Woole (FCFW) algorithm, presented in some form in Wolfe [976], Holloway 1974] and named in corrective paradigm to its limit by computing a minimizer of the objective over the convex hull of the active set after each FW step. Besides its favorable convergence properties and sparsity of solutions,
and Jaggi [2013], drives the
FCFW is also closely related to column-generation and cutting-plan methods (Vinyes and Obozinski 2017 Zhou et al., 2018). Nonetheless, FCFW is often computationally impractical since minimizing over the convex hull of the active set can be computationally as hard as the original problem.
In this work, we generalize the idea of corrective steps on the active set to new framework, Corrective Frank-Wolfe Wolfe (CFW), and design two new Quadratic Correction (QC) steps tailored to quadratic objective functions. While many applications involve quadratic objectives, such as matrix recovery (Garber et al. 2019], spectral clustering (Ding et al. 2022]. and entanglement detection [Liu et al. 2025]. , also revisit two FW-based algorithms that benefit from QC and strengthen their theoretical guarantees (with improved rates and applicability to new function classes).
Split Conditional Gradient (SCG) [Woodstock and Pokutta| 2025 tackles optimization problems over finite intersections of convex sets via splitting, avoiding the potential intractable linear minimization over the intersection. SCG is inspired by the Alternating Linear Minimization (ALM) algorithm Braun et al. 2023] and solves the problem by alternating between update steps for iterates on the respective sets. Each iterate minimizes an auxiliary quadratic objective, incurring increasing penalty on the squared distance to the other iterate. Besides the computational benefits of the quadratic corrections, we also prove faster convergence rate for SCG.
Additionally, we consider Second- Order Conditional Gradient Sliding (SOCGS) [Carderera and Pokutta|(220) which follows an inexact Newton approach, adapting the Conditional Gradient Sliding (CGS) method Lan and Zhou 2016) with a quadratic approximation of the original problem at each iteration. The method enjoys very fast convergence rates and has been shown to outperform first-order Frank- Wolfe variants on various problems. However, the main computational bottleneck of SOCGS is solving the quadratic subproblems, which can be significantly accelerated using our proposed quadratic corrections. Furthermore, we establish a global linear convergence rate of SOCGS for generalized self-concordant functions [Sun and Tran-Dinh 2019) without requiring global Lipschitz smoothness or strong convexity.
Related work
The literature on Frank-Woor methods is vast, and we only cover a few related methods here; for
more comprehensive overview, we refer Braun et al. [2022]. The corrective framework is inspired by ideas from Blended Conditional Gradients (BCG) Braun et al. [219]] and Blended Pairwise Conditional Gradients (BPCG) [Tsjii et al. 2022]. Furthermore, Lacoste-iil and Jaggi (2015) present, besides the already mentioned AFW and FCFW, Pairwise Frank-Wolfe (PFW) and an approximate variant of FCFW. Additionally, they introduce a generalized version of the Minimum-Norm Point (MNP) algorithm [Wolfe, 1976) for corrections in approximate FCFW, called MNN--Coreectio. Finally, we follow the idea of Braun et al. [017 to introduce a lazified variant of the corrective step framework.
Contributions
Our contributions can be summarized as follows:
Corrective Frank-Wolft We introduce Corrective Frank- (CFW), a new framework for FW variants that perform corrective steps on the active set and prove linear convergence for smooth, sharp functions over polytopes. We show that active-set-based methods like AFW, BCG, and BPCG fit into the corrective step framework. Furthermore, we introduce lazified variant of CFW, which avoids

---

LMO calls during iterations with corrective steps, Lastly, we prove that CFW identifies the optimal face of a polytope finite time under strict complementarity.
Quadratic corrections We introduce two new quadratic correction steps tailored for quadratic objectíve functions. The first one, QC-LP, is direct linear program solving the quadratic problem over the convex hull of the active set via relaxed optimality conditions. The second type, QC-MNP, is specialized variant of the Minimum-Norm Point (MNP) algorithm [Wolfe) 1976], solving the quadratic problem over the affine hull. Both steps are approximate variants of an FCFW step, but require only solving a linear program linear system, respectively. Additionally,
propose hybrid method that combines these corrections with the local pairwise steps BPCG (Tsuji et al. 2022], yielding highly efficient update scheme for quadratic problems. Finally, we show that CFW with QC-LP and QC-MNP converges in finite time.
Theoretical results for SCG and SOCGS Besides the practical benefits of the new quadratic corrections for SCG and SOCGS, also present new theoretical results. First, prove that SCG converges for a smaller step size, yielding faster rate of ((1/V)) compared to the original rate / /)t provided in Woodstock and Pokutta (2025). This closes the gap to the complexity bound of (1/vVt) for the underlying non-smooth problem Yudin 1983). Second, we show that the Projected PeriableMMetri method SOCGS converges globally for generalized self-concordant functions.
of (log(())
Experiments We demonstrate the excellent computational benefits of the quadratic corrections on a variety of problems, including sparse regression, entanglement detection, projections onto the Birkhoff polytope, and tensor completion problems. Further experiments show that quadratic corrections also improve the convergence of ALM and SCG. For SOCGS, the quadratic corrections enable us solve the quadratic subproblem efficiently.
Preliminaries
be the of minimizers of f over X, and (X)) be the set of extreme points of X. X' is polytope, we denote its pyramidal width by 8 [Lacoste-Julien and Jaggi 2015 and the minimal face containing X by F*. Striet complementarity holds if there exists p O such that for all x" X and v E V(t), we have
Let A' be compact convex set with diameter D def maxx x |x 1xyyl,, ""l,.""
E (VEV =0 V(vEV())
(VI(x'), x*)
We denote the active set, i.e., the set of vertices used by FW algorithm, by S X. For given weight vector X, we denote the weight of an atom v E S by Av. For a given convex combination Eves V. we denote the corresponding weight vector by X(x) def X. Furthermore, we denote the convex hull of S by cSnv(S), the affine hull of S by aS), and the boundary of a set M by OM. Let f: X + TR. be differentiable, convex function. The function is I-smooth if
L f(y) - f(x) < (Vf(x). x) ly x|1
Vx,y e X.
The function f is p-strongly convex if
f
(Vf(x).
ly x Vx,y E
In the following, we will use the notion of sharpness, generalizing strong convexity. Let f denote the optimal value of of over X. A proper convex function ff is (c, -h-sarp with > 0 and 0 (0,1) for all x E X.
c(f(x) - -²
min ||x - yll- yEX*
In particular, j-sttrongly convex function is
v/2 Vp
-sharp over any compact set.
3

---

2 Corrective Frank-Wolfe
We present the Corrective Frank-Wolfe Wolfe (CFW) algorithm in Algorithm 1 its convergence analysis, and specialized corrections for quadratic objectives.
CFW provides general framework for FW methods that perform corrective steps on the active set. Unlike approximate FCFW, CFW does not perform an FW step in each iteration but instead compares the so-called local pairwise gap (V I (x+), ar sr) with the global Frank-Wolfe gap (V](x;) X Ve) to decide whether to perform a corrective step or an FW step. Algorithm a template for corrective steps that ensures convergence of CFW.
Algorithm Corrective Frank- Wolfe (CFW)
Require: convex smooth function f, starting point Xo E V(X).
I: So {xo}
2: for = to T do
3: a, + argmax V (xx), v)
away vertex b local FW global FW
4:
St f argmin (Vx)),), v)
5: Vi argmnn (X)()),, v)
6: if (Vf(x)), ar 5,) 2 (Vf(x),, - then
vi)
7:
X1+1. St+1 t CS St, Xe, St)
8:
else
9:
7t f argmin f(x: - -7xx-- v.))
10:
X(+1 -x((x; -v))
11: S + S, [vi)
12: end if
13:
end for
Algorithm 2 Corrective Step CS(S, x, a,
Require: $ X, x. a.s X' Return: S' C S,x' E conv(S') satisfying satisfiing (i fx') < fxx and S' S S
drop step > descent step
(ii) fxx) f(x') > a-s)
A corrective step is either descent step that yields sufficient primal progress drop step that decreases the size of the active set without increasing the objective value. In contrast to approximate the away gap and compare the primal progress only to the local
FCFW, we omit any conditions pairwise gap rather than the global FW step. The update steps in BCG, BPCG, and FCFW meet the criteria of corrective step. The proof is given in Section[A]
Proposition 1. Algorithm 3 Algorithm 4 and the simplex gradient descent step from Braun al. [2099] satisfy the criteria of Algorithm
Algorithm Local Pairwise Step LPS(S, x, a,
Algorithm 4 Fully-Correctvv Step FCS(S)
Require: SC X, Return: S',x'
Require: SCX
Return: S',x' I: x' + argminxccoovvss fx)
1: 7 < argmin f(x -ss
2: x - x + (s a)
2: S' < (vES Xx > 0}
3: S' S (a)
S
otherwise.
This result enables designing new corrective steps without theoretical verification. The conditions of a drop step can be verified easily at runtime. For the descent step, one can compare the primal value of the new point with the result of the local pairwise step. If neither of the conditions is met, one can perform the local pairwise step, which provides an inexpensive fallback option. Furthermore, one can also use hybrid methods that combine different steps to balance computational effort and progress. Remark 1. The result of Proposition also applies to AFW if the gap comparison in Algorithm Juses the away gap instead of the local pairwise gap. We choose the pairwise gap since it can computed with the same complexity and leads to fewer FW steps.

---

2.1 Convergence analysis
In the following, we will state two convergence results for CFW and its lazified variant, as well as result on active set identification. The proofs are independent of the specific implementation of the corrective step, thereby simplifying the verification of these properties for new variants.
Theorem 2. Let X be a convex feasibbe set with diameter D and f be convex, L-smooth function over X. Consider the sequence {xi)t X obtained by Algorithm / Then we have
4LD² T
f(x))-F <
(1)
If additionally is (c, 2 --sharr and X is polytope with pyramidal width ó, then f(xT)
f < (f(xo) - - -c,(-c,,x)),
(2)
where Cf,x def
min
6
16Le.
The proof is given in Section A
The CFW algorithm needs to call the LMO at each iteration to compare the FW gap with the local pairwise gap, even if the FW step is not taken after all. We follow the approach of Braun et al. [2017] and adopt a lazified version of CFW to avoid this requirement.
The Lazified Corrective Frank-Wolfe (LCFW) method replaces the FW gap with an estimate D, which is updated if the gap becomes smaller than 2r/J for some parameter J > 1. The convergence results are stated in Theorem 3 and we present its proof together with the algorithm in Section B Theorem 3. Let X be convex convex feasible set with diameter D and f be convex, L-smooth function over X. Consider the sequence (xi) C. X obtained by the Algorithm Then we have
[(xT) l 0 -
additionally is (c, -hharp and X is a polytope with pyramidal width ö, then [(XT) - f = O (exp(-aT)),
for some constant a > 0 independent of
Finally, we state a theorem that ensures identification of the optimal face by CFW in finite time under strict complementarity. Identifying the optimal face F of X' crucial, as it simplifies the optimization problem to one over F instead of X. An early result by Guélat and Marcotte (1986) proves this property for AFW under the additional assumption of strong convexity of |Bomze et al.)
(0200 extend this result to AFW for general convex functions and Wirth et al. (2025 prove the same result for BPCG. The proof of Theorem 4 given in Section A
Theorem 4. Let X be polytope and let J be a convex, L-smooth function over X. Assume that strict complementarity holds. Consider the sequence {x) generated by Algorithm 0
Then there
exists an iteration T such that
F for all t t>T.
2.2 Quadratic corrections
In this section, we introduce two types of corrective steps for the CFW algorithm that are especially suited for quadratic problems: Quadratic Correction LP (QC-LP) and Quadratic Correction MNP (QC- MNP). Here, we assume that f is convex quadratic function, i.c., can be written as f(x) (x, Ax) + (b, x) + c, where A is a symmetric positive semidefinite matrix. This can be extended to general finite-dimensional Hilbert spaces, in which case A is symmetric linear operator.
The quadratic corrections are inspired by FCFW, which solves the minimization prob- lem ginnx)) fxx in each iteration. Unfortunately, minimizing quadratic functions over poly- topes such as conv(S) is computationally demanding (we discuss this in Remark 2). To circumvent
this difficulty, the QC algorithms instead exploit the finiteness of the active set S and relax this problem into minimizing the function f over the affine hull of S,
min
fxx
min XEConv(S)
f(x)
(5)
xEa)f(S)
and then reconstruct point in cSnv(S).
5

---

Solving the minimization problem over the affine hull Let xat E argmin fxx. First- order optimality conditions imply that (V)(xaa) d) = 0 for any feasible direction d. The feasible directions in (S) are spanned by d = v w for v, w E S. Thus, the first-order optimality conditions are equivalent to the system of equalities,
(v](xam), v w) 0 W
which is equivalent to the gradient at X being orthogonal to the affine space. Writing x as an affine combination of the atoms in S yields V (x(+)) Ax b A Lves Av (x + bb-
AVA(x b. By fixing an anchor w E S, we obtain a linear system,
(AVX + b, w) = 0 AVES\ (w),
Σ ~v= VES
(6)
Remark 2. Applying first-order optimality conditions to X E arg millx f(x) with the barycentric coordinates yields (AVX + b, v VX) > 0 for all v S. which is a quadratic inequality system in À that can be as hard to solve as the original problem. However, if x lies in the relative interior of conv(S), these quadratic inequalities simplify to linear equalities as in (6).
The linear system (6) is equivalent to the KKT conditions of (5) and thus sufficient. As formalized in the following proposition, an affine minimizer exists if the linear term b yields no descent in any direction in the affine hull in which f is not curved. Otherwise, the problem is unbounded and the system is infeasible. The proof is given in Section C.2
Proposition 5. Equation (6) feasible if and only if 1 span(S) (A). In particular, is feasible if A is posilive definite.
Quadratic correction through Linear Programs To ensure that the new weights À non- negative, we consider two approaches. The QC-LP approach enforces this directly, yielding
(AVA+b,v w) (w),
Σ>= > 0. VES
The LP is only feasible if the affine minimizer exists and lies in conv Otherwise, we perform a local pairwise step computationally cheap fallback option. The method is stated in Algorithm S
Algorithm 5 QQaddatic Correction LP
Algorithm 6 Quadratic Correction MNP
Require: S SCX,x
Require: S X,,,EE
Return: S',x'
Return: S',x' X Solve (6)
X t Solve
if feasible then
FCFW step
if feasible then
x' + Eves X,v
x then
D FCFW step
S
EVES d. S
else
Fallback step
S'xx's + LPS S. a,
else
> MNP step
end
t + min { [xxl)) ( < <xx(x)}
x' + Eves(T)y + ()
S' + (v E Xv(x') > 0}
end if
else
b Fallback step
S' x
LPS S. x, a,
end if
Quadratic correction through the Sinimum-NNorm-Pinn algorithm The second approach, QC-MNP, is inspired by the Minimum-Nore -ooruum--oo--Pooor -Pint algorithm |Wolfe (1976). Instead of enforcing the non-negativity directly, one considers the line segment between the weights of the current point and the affine minimizer. If at least one of the new weights is negative, we perform a ratio test to find the intersection of the line segment with the |S||simplex. This step will drop at least one atom from the active set, improving sparsity. However, it can happen that this atom belongs to the optimal face. Unlike the
step from Laccstte-Julie and Jaggi 20055. QC-MNP will stop after

---

single truncation, alleviating the need to solve multiple linear systems in single iteration. This also avoids dropping more than one atom per iteration, which can be problematic in some cases. As for QC-LP, we perform a local pairwise step if there is no affine minimizer. The standard implementation of QC-MNP is presented in Algorithm 6 and we derive more efficient variant for the case of C.
multiple affine minimizers in Section
Both QC-LP and QC-MNP are corrective steps the sense of Algorithm 2 Furthermore, an affine minimizer is guaranteed to exist if the current iterate lies in the optimal face.
Proposition 6. QC-LP and QC-MNP satisfy the criteria of corrective steps in Algorithm
Proposition 7. Let X' be polytope and F be the minimal face of X containing the optimal
points X S F", then argmin fxx + 0. If additionally there exists x* X with x" E cOnv(S), then x" aaagminzeaf(s)) f(x).
We would like to emphasize that the sizes of the linear system and the IP do not depend on the ambient dimension but only on the size of the active set. Furthermore, similarly to Besançon et al. 2025 can cache the scalar products (v, Aw) and (b, v) for v, S, accelerating the setup of the linear system and LP while only marginally increasing storage.
Remark The linear system (6 is usually not symmetric, which can be problematic for solvers like Conjugate Gradient (CG). However, subtracting W Aw1 X W Aw from (6) yields the
equivalent symmetric system
W AW = W (Aw + b),
(8)
where the matrix W has columns
w for ESS (w). The new weights are then given by
A 1 v
Fv
otherwise.
Finally, we come to the main result of this section. As seen in Theorem 4 CFW identifies the optimal face of polytope in finitely many iterations if strict complementarity holds. This is crucial for fully-corrective steps as they converge to an optimal solution if the optimal face is identified and the convex hull of the active contains at least one solution. Thus, CFW with QC-LP, QC-MNP or FCFW converges to an optimal solution in finitely many iterations. The proof is given in Section C.2
Theorem 8. Let X be a polytope and let f be convex, quadratic function over X, i.e. f(x)
(x, Ax) + (b, x) + c where A is a symmetric positive semidefinite matrix. Assume that strict complementarity holds. Consider the sequence {x+) generated by Algorithm 7 with Algorithm
Algorithm 5 Algorithm Then, there exists an iteration I such that Xx E X
3
Accelerated algorithms through quadratic corrections
In this section, we leverage quadratic corrections for two classes of algorithms that require solving quadratic subproblems and provide additional theoretical results that might be of independent interest.
3.1 Split Conditional Gradient
A key limitation of Frank-Wolt methods is their reliance Linear Minimization Oracle. This becomes particularly problematic for optimization over intersections of convex sets, where no efficient procedure for linear minimization is generally available. |Brunn al. 2023 introduced the Alternating Linear Minimization (ALM) method for finding a point in the intersection of two convex P and Q. drawing parallel with von Neumann's alternating projection. ALM alternates between Frank-Woud steps, solving minxe P.yoo ||x - y| and therefore avoids projections in an FW-like manner. WWodstock and Pokutta (2025) extended their approach to optimization problems over intersections by penalizing the distance,
X +y
min xEP
Fx(x,)) -
+
y|
Their method, Split Conditional Gradient (SCG), performs parallel FW steps both sets and can therefore be easily extended to use corrective steps. Particularly, if the original objective is linear or quadratic, one can leverage quadratic corrections.
7

---

Independently of CFW, we prove tighter convergence rate for the original SCG. Woodstock and
Pokutta (2025) prove that the primal gap of F' converges at rate of O (log t/ Vt). By analyzing 2
a different auxiliary objective, we show that replacing the step size 7/- v142 by the smaller step
size /t-2log(t+22 improves the convergence rate of SCG to O (1/v7). The proof for the more
2
general case of finite intersections over Hilbert spaces is provided in Section D
Theorem 9. Let T. + TR be convex and L-smooth, P,Q& R be non-empty compact and convex sets with diameters Dp and Do such that P PNQ= # 0. For t i O, set X = In(t + 2).
x2) E axgmin Fx, For 7 = V1+2ln(t+2) the iterates of Algorithm 9 satisfy
2
(Dr DO (T. V2eg
0 (x (x,
(9)
V++2
for all t > 0, where ey = ma f
( f
x+y < 00.
3.2 (Second-Order Conditional Gradient Sliding
Another class of algorithms that benefit from quadratic corrections is sliding methods, specifically Conditional Gradient Sliding (CGS) [Lan and Zhou 2016) and Second-Order Conditional Gradient Sliding (SOCGS) [Carderera and Pokutta 2020J. These methods reduce the number of first-order oracle calls by iteratively solving quadratic problems with FW variant. While the original papers considered vanilla FW and AFW steps, one can use quadratic corrections to accelerate the inner steps.
Unlike regular FW variants, CGS requires only O(1/ instead of (1/E)) gradient calls to achieve e-optimality, matching existing lower bounds. SOCGS achieves a linear rate for strongly convex functions over polytopes, replacing the Euclidean projection subproblem in CGS with projected variable- metric problem. The convergence of CGS and SOCGS was analyzed on globally smooth, strongly convex functions. We extend this rate to generalized self-concordant functions, detailed description is given in Section
Theorem 10. Let X be compact convex set of diameter and f be a geenerrliee self- concordant function with v 2> 2 such that f is strongly convex on dom(f) niX if 3. Given starting point Xu E X dfm(f), the Algorithm with a step size 7hh guarantees for all k: > 0:
((x++))- < (1 d(w)) (f(xx) f(x)))
where c(TR) 1 is constant depending on the step size Tkk
4 Experiments
In this section, present numerical experiments on two classical quadratic problems and on two applications of quadratic corrections to SCG and SOCGS. In all experiments, we use a hybrid of BPCG and QC steps, performing QC step whenever N new atoms have been added to the active set. In the first two experiments, we compare QC-LP and QC-MNP with four baselines: FW, AFW, PFW, and BPCG. For SCG and SOCGS, we compare against the original used FW variant and BPCG, to demonstrate the effectiveness of the quadratic corrections. Additional details and further experiments are provided in Section F All runs were executed on cluster with Intel Xeon Gold 6338 CPUs at GHz and 12 GB RAM, with time and iteration limits chosen according to problem size.
4.1 Regression over the K K-Sparse polytope
In the first experiment, we consider a sparse regression problem over the K K-Sparse polytope, (T) (TK))) n (T). The problem is to minimize fx) = "Em((xx ax) - y1)²
||Ax - y 11 over (T( given data points ((a, y1 m ) C R x I.. We generated synthetic normally distributed a, and y; with n = 500, m = 10000 and K E (5, 20). and used a fixed interval length of N = 10 for the quadratic correction steps. As shown Figure [ all methods except FW converge linearly, with QC-LP and QC-MNP providing substantial acceleration for both instances. For smaller values of K, the benefit of QC is more pronounced as the optimal face contains more atoms and therefore the active set is larger. Both QC methods reach optimality significantly faster than the basclines.
8

---

1243
10
12
2613
12
AVC
1050
109
10
10
1074
20%
ko
(tanstara
Tima
Figure 1: Sparse regression over the K- K-Sparse polytope for K E 25,
4.2 Entanglement detection
Certifying the entanglement of quantum states is fundamental challenge in quantum information theory. |hang and Gühne 2018 use Gilbert's algorithm [Gilbert, 1966]. a simplified FW method, together with heuristic LMO for computing the minimal distance of given state the set of separable quantum states. Liu et al. 2025 extend their approach to general FW methods and propose an approximate LMO with a provable multiplicative error. For our experiments, we consider family of 3 x 3 entangled states proposed in [Horodecki [997] and use a fixed interval length of N = 1 for QC-MNP and N 10 for QC-LP, A complete description of the setup as well results for noisy states are given in Section F The results for E {0.25, 0.5) are shown in Figure 2 We use logarithmic scale on the horizontal axis to visualize the differences between the methods more clearly. QC-MNP shows drastic initial acceleration, solving the problem to optimality in fraction of the iterations and time of the other baselines. The LP in the QC-LP is rarely feasible, leading to pairwise steps and thus similar trajectory to BPCG. FW and PFW perform worse than the other baselines in terms of time due to the high number LMO calls.
10
DCUP
COPN
10
16
22n9
10"
Figure 2: Entanglement detection for f0.25, 0.5}
4.3 Projection onto intersections with Split Conditional Gradient
SCG to project onto the intersection of the Birkhoff polytope B(n), the set of all n x n doubly stochastic matrices, and a shifted & ball. For the shift, we sample a point on face of (n) and move the center the ball from there in the direction of the normal vector of the face. The shift is parametrized by E [0, 1] and q E [0, 1]; a complete description is given in the appendix. The objective is given by f(X)= + X X 2 where X₂ E gn8n sampled with uniformly distributed entries. The results for E (300, 500} using = 0.9, 0.1 and N = are given Figure We compare the hybrid methods QC-MNP and QC-LP with BPCG and the FW variant from [Woodstock and Pokutta 2025). The split approach, with its dynamically changing objective, makes this problem more difficult than the previous ones. Both QC methods hit numerical precision limits on these instances and would need adjusted tolerances for longer runs. Nevertheless, QC-MNP and QC-L. outperform BPCG for n = 500 and achieve similar results for 300. The FW variant from Woodstock and Pokutta
In this experiment,
2025 performs the worst on both instances.

---

14
1/
107
107
10
12
107
Ponationa
5J
Timma
Figure 3: Projection onto the intersection of the Birkhoff polytope and shifted E2 ball for dimension 72 E {300, 500}
4.4 Projecting with quadratic corrections in Second-Order Conditional Gradient Sliding
In the last experiment, we solve logistic regression problem over the & ball with SOCGS. The objective is to minimize f (x) 1 Σ In (1 exp(- Yi (x, 2,))) + ||x| The labels Yr 7i
1-1.1) and feature vectors 2; E RR are taken from the gisette training dataset [Guyon et al. 2007], with n 5000 and m 6000. Recall that each iteration of SOCGS corresponds solving an outer problem and an inner problem. We use the BPCG step for the outer problem and compare BPCG, QC-MNP, and QC-LP for the inner step, Additionally, we also test AFW for the inner step as proposed in [Carderera and Pokutta 2020). The results for k E {50, 200} inner iterations are depicted Figure 4 All methods follow an identical trajectory in the initial phase, indicating that SOCGS chooses only the outer step. Once the distance to the optimum is sufficiently small, the QC methods exhibit substantial improvements over BPCG in both instances. Further analysis reveals that QC-MNP and QC-LP perform more FW steps than BPCG on the inner problem by avoiding additional pairwise steps, which yields a drastic initial decrease primal values and the FW gap. For longer runs of the inner problem, i.e., larger the acceleration of the QC methods is less pronounced, yielding a similar performance as AFW. The hybrid method with QC-MNP performs more quadratic corrections than QC-LP, yielding more significant acceleration but also longer runs in wall-clock time.
SPCU
16/
177
1075
12"5
10"3
26-7
Hanatoro
Figure 4: Logistic regression over the l ball for maximum number of inner steps At E {50, 200}
5
Conclusion
In this paper, we present new framework for conditional gradient methods, Corrective Frank- Wolfe, that uses corrective steps on the active set to improve convergence while avoiding additional LMO calls. Instances of the proposed framework provide state-of-the-arr convergence rates for sharp functions over polytopes and identify the optimal face of a polytope in finite time. The proposed quadratic corrections are very effective in practice, outperforming methods of comparable convergence both in iteration count and runtime. This allows us to revisit and accelerate previous algorithms, Split Conditional Gradient and Second-Order Conditional Gradient Sliding, by applying quadratic corrections to the arising subproblems.
10

---

Acknowledgments and Disclosure of Funding
Research reported in this paper was partially supported by the Deutsche Forschungsgemeinschatt (DFG, German Research Foundation) under Germany's Excellence Strategy The Berlin Mathematics Research Center MATH+ (EXC-2046/1, project ID: 390685689). The work of Mathieu Besançon was supported by MIAI at Université Grenoble Alpes (grant ANR- 19-11--331A-0033.
References
Amir Beck, Edouard Pauwels, and Shoham Sabach. The cyclic block conditional gradient method for convex optimization problems. SIAM Journal on Optimization, 25(4):2024-2449, 2015. doi: 10.1 /0.113///500003977 URL httph:/t////ooo org/10. 100.01111//100000000000
Aharon Ben-Tal Tal and Arkadi Nemirovski. Lecture notes Optimization III Convex analysis nonlinear programming theory nonlinear programming algorithms. Lecture Notes, Spring 2023. https
//www2. isye..isye... www.:ettcee....c..o.oooooo...... seatecchedduueemrrreeeee
pdf
Mathieu Besançon, Alejandro Carderera, and Sebastian Pokutta. Frank Jolff a high-performanee and flexible toolbox for Frank- Wolfe algorithms and conditional gradients. INFORMS Journal on Computing, 34(5):2611-229) 2022.
Mathieu Besançon, Sébastien Designolle, Jannis Halbey, Deborah Hendrych, Dominik Kuzinow- icz, Sehastian Pokutta, Hannah Troppens, Daniel Viladrich Herrmanssdeerfer, and Elias Wirth. Improved algorithms and novel applications of the Frank Frofeel library. ACM Transactions Mathematical Software, 2025.
Immanuel M Bomze, Francesco Rinaldi, and Damiano Zeffiro. Active set complexity of the atep Frank-Wolfe algorithm. SIAM Journal on Optimizaation, 3073):270-- 2020.
G. Braun, S. Pokutta, and Zink. Lazifying conditional gradient algorithms. Proceedings of the 34th International Conference on Machine Learning, pages 566-575, 2017.
G. Braun, S. Pokutta, D Tu, and S. Wright. Blended conditional gradients: the unconditioning of conditional gradients. In Proceedings of the 36th International Conference on Machine Learning, 2019.
Gábor Braun, Alejandro Carderera, Cyrille W Combettes, Hamed Hassani, Amin Karbasi, Aryan Mokhtari, and Sebastian Pokutta. Conditional gradient methods. arXiv preprint arXiv:2211.14103 2022.
Gábor Braun, Sebastian Pokutta, and Robert Weismantel. Altemating linear minimization: Revisiting von neumann's 's alternating projections, 2023. URL https: http://axxivv...aaaaa/ /2tp
Caleb Bugg, Chen Chen, and Anil Aswani. Nonnegative tensor completion via integer optimization, 2022.
A. Carderera, M. Besançon, and Pokutta. Scalable Frank-Wolf on generalized self-concordant functions via simple steps. SIAM Journal Optimization, 34(3), 4 2024.
Alejandro Carderera and Sebastian Pokutta. Second-order conditional gradient sliding. arXiv preprint arXiv:2002.08907, 2020.
Cyrille W Combettes and Sebastian Pokutta. Complexity of linear minimization and projection on some sets. Operations Research Letters, 4945)5565-57, 2021.
Tianjiao Ding. Derek Lim, Rene Vidal, and Benjamin D Haeffele. Understanding doubly stochastic clustering. In Kamalika Chaudhuri. Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning. volume 162 of Proceedings of Machine Learning Research, pages 5165-5165. PMLR, 17-23 Jul 2022. URL
mmr.anng..........mmm.mm....mmim mlr. press/ wtt.v11////a/// diigg///in22a...m/ html
Marguerite Frank and Philip Wolfe. algorithm for quadratic programming. Naval research logistics quarterly, 3(1-2):95-10,, 1956.

---

Dan Garber, Atara Kaplan, and Shoham Sabach. Improved complexities of conditional gradient-type methods with applications robust matrix recovery problems. Mathematical Programming. 186, 11 2019. doi: 10. 10.10077/110007-019-014553
Elmer G. Gilbert. An iterative procedure for computing the minimum of a quadratic form on a convex set. SIAM Journal on Control, 4(1):61-80, 1966. doi: 10.1137/0304007. URL https
//doi.org/10 1trg/10..0 1137/0304007
Jacques Guélat and Patrice Marcotte. Some comments on Wolfe's "away step'. Mathematical Programmiing 35(1):110 111110011111 119, 1986.
Isabelle Guyon, Jiwen Li, Theodor Mader, Patrick A Pletscher, Georg Schneider, and Markus Uhr. Competitive baseline methods set new standards for the NIPS 2003 feature selection benchmark. Pattern recognition letters, 28(12) 1444, 2007.
Deborah Hendrych, Mathieu Besangon, and Sebastian Pokutta. Solving the optimal experiment design problem with mixed-integer convex methods. arXiv preprint arXiv:23/2.11200, 2023.
Deborah Hendrych, Mathieu Besançon, David Martínez-Rubio, and Sebastian Pokutta. Secant line search for Frank- algorithms. In Forty-second International Conference on Machine Learning, 2025. URL htttp:///axxi... org/ aba/ wawp///1.... 18775
Charles A. Holloway. An extension of the Frank and Wolfe method of feasible directions. Math. Program., 6(1):14-21 December 1974. ISSN 0025-5610. doi: 10.10077/BF05580219 URL
http:///00...00111.000000///////
Michal Horodecki, Pawel Horodecki, and Ryszard Horodecki. Separability of mixed states: necessary and sufficient conditions. Physics Letters A, 223(1):1-8, 1996. ISSN 0375-9601. doi: hups://doi.
[ep110000166s0007556000000000660 articlee/s1//0077911160677/
URL http::///www.ccinccirerrttt wwwp:/ttt.coo///eeeeeeeeeee
Pawel Horodecki. Separability criterion and inseparable mixed states with positive partial transposi- tion. Physics Letters A, 232(5):333 339, 1997. ISSN 0375-9601. doi: http:://di..or//0..100 1016/
107754996 URL httL:htts////t httttps://ww..... www.ssccccccccccccccoomm http///eteeeeeeeeeeeeee/eerrttaa $037/5900197004167
Sai Praneeth Karimireddy, Sebastian U. Stich, and Martin Jaggi. Adaptive balancing of gradient and update computation times using global geometry and approximate subproblems. In International Conference on Artificial Intelligence and Statistics, 2018.
Simon Lacoste-Julien and Martin Jaggi. On the global linear convergence of Frank-Wolfe optimization variants. In Proceedings of the 29th Conference on Neural Information Processing Systems, pages 566-575. PMLR, 2015.
Simon Jacoste-Julieen Martin Jaggi, Mark Schmidt, and Patrick Pletscher. Block-coordinate Frank- Wolfe optimization for structural SVMs. In Sanjoy Dasgupta and David McAllester, editors, Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pages 53-61, Atlanta, Georgia, USA, 17-19 Jun 2013. PMLR. URL
mmr. cassss/v28/laccoee julienn3...n.n html
Guanghui Lan and Yi Zhou. Conditional gradient sliding for convex optimization. SIAM Journal on Optimization, 26(2):1379-14 1379-1409, 2016.
E. S. Levitin and B. T. Polyak. Constrained minimization methods. USSR Computational Mathematics and Mathematical Physics, 6-5).1-50, 1966.
Ye-Chao Liu, Jannis Halbey, Sebastian Pokutta, and Sébastien Designolle. unified toolbox for multipartite entanglement characterization. Manuscript in preparation (private communication with authors), 2025.
Yurii Nesterov. Lectures convex optimization, volume 137. Springer, 2018.
Jiangwei Shang and Otfried Gühne. Convex optimization over classes of multiparticle entanglement. Phys. Rev. Leut 120:050506, Feb 2018. doi: 10. 10. It..1 120.050506. URL hhtpps
//link. opg. /oi/ 11t.::..1//11111/111ee 120. 050506
12

---

Tianxiao Sun and Quoe Tran-Dinh. Generalized self-concordant functions: recipe for Newton-type methods. Mathematical Programming. 178(1):145-213, 2019.
Kazuma K Tsuji, Ken'ichine Tanaka, and Sebastian Pokutta. Pairwise conditional gradients without swap steps and sparser kernel herding. In International Conference on Machine Learning, pages 11864-21883. PMLR, 2022.
Marina Vinyes and Guillaume Obozinski. Fast column generation for atomic norm regularization. In Aarti Singh and Jemry Zhu, editors, Proceedings of the 20th International Conference Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pages 547- URL Inttps://proceddings mlr www.ppreeesss....
556. PMLR, 20-22 Apr 2017.
html
Elias Wirth, Mathieu Besançon, and Sebastian Pokutta. The pivoting framework: Frank- algo- rithms with active set size control. In The 28th International Conference on Artificial Intelligence and Statistics, 2025. URL
arxiv. org/abs/ /200//247.... 11760
Philip Wolfe. Finding the nearest point in polytope. Math. Program. 11()):22-149, Decem- ber 1976. ISSN 0025-5610. BF01580381
doi: 10.1007/BF01580081 URL littps://do) http://do...or11110000007
Zev Woodstock and Sebastian Pokutta. Splitting the conditional gradient algorithm. SIAM Journal on Optimization, 35(1): (5(1):347-36, 2025. doi: (0.1137/24M1638008 URL org/10
1137/24M1 638008
David Borisovich Yudin. Problem complexity and method efficiency in optimization. Wiley, 1983,
Renbo Zhao. New analysis of an away-step Frank- Wolfe method for minimizing log- homogeneous barriers. Mathematics of Operations Research, 2025.
Song Zhou, Swati Gupta, and Madeleine Udell. Limited memory Kelley's method converges for composite convex and submodular objectives. In S. Bengio, H. Wallach, Larochelle, K. Grauman, N. Cesa-Bianchi and R. Garnett, editors, Advances in Neural Information Processing Systems.
volume 31. Curran Associates, Inc., 2018 URL / hewpesseerrrsp.p. cc/paper.
fttpapppppr/00////////eeeeffeftp Paper. pdf
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: All presented theoretical results are proven and the experimental results show the computational benefits of the proposed methods.
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 in the paper and important assumptions and limitations. A No
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 can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
The proposed Corrective Frank-Won method comes with the usual limitations of the Frank-Wolfe variants, which discussed the introduction. The limitations of the new quadratic corrections, i.e., the quadratic objective and the need for an LP solver, are discussed corresponding section.
Justification:
Guidelines:
The answer NA means that the paper has 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 in their paper.
The paper should point out any strong assumptions and how robust the results are to 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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should 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 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
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play 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
14

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
All presented theoretical results are proven and the proofs are provided in the appendix.
Justification:
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 in 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 provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: We provide detailed information about the experimental setup in the appendix and the code is provided in the supplemental material.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to 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 on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general, relcasing 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 hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to 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
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a 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 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 are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
15

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [Yes]
Justification: We provide the code for reproducing the experimental results in the supple- mental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nnis.cc)
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.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
/nips. wwtpcc/pccppcpcceeeooooooop htte:gguuuddeeoeSuuubbbbiiiii seaibbmsssionPo swiniiossiiiyccyy for more details.
The authors should provide instructions on data access and preparation, including how 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 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) is recommended, but including URLs to data and code is 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: Details about the experimental setup are provided the appendix. Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: We do not report error bars because the methods are deterministic. For exper- iments with synthetic data, we tested the methods for different seeds, yielding consistent results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
16

---

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).
It should be clear whether the error bar is the standard deviation or 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 is 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 of range (e.g., negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: The computational resources needed for the experiments are provided in the experiments section.
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 well 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 make into the paper).
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: The authors have reviewed the NeurlPS Code of Ethics and the paper conforms to it.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., s if there is special consid- eration due to laws or regulations in 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:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
17

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or 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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that 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 or 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 attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
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:
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 to 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
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
18

---

If assets are released, the license, copyright information, and terms of use in the thcode has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssi
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent 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. Crowdsoureing and research with human subjects
Question: 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)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper doess not involve crowdsourcing nor research with human subjects.
Including this information 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 in 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 the requirements of your country institution) were obtained?
Answer: [NA]
Justification:
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.
19

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS 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, formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: /ttpps////eurpss.... /ccc////eeeeeeecs///22////// for what should or should be described.
20

---

A Proofs for Corrective Frank-Wold
In this section, we provide proofs for the theoretical results on CFW stated in Section Before we present more general version of Theorem 2 and its proof, recall two lemmas resulting from the sharpness of the objective function and a conversion from contraction to convergence rates.
Lemma 11. [Braum et al. 2022 Lemma 3 Let X be a polytope of pyramidal width 5 > 0 and let f be a (c, sharp convex function over X. Let and v be defined as in Algorithm / then
(((x) 11)1- (V((x).a-
(10)
Lemma 12. [Braun al. [022 Lemma 2.21] Let {h+]r Jt be sequence of positive numbers and let CD2 C1, C2 be posilive numbers with < 1 such that hy co and h4 - -1411 2 hy min(er (ci, o2h()) for all t. 1, then
co(1 -
if FlEteR ift to.
he <
(Itqa((-to))u4a = 0(1/8//)
(0//2))2/0
where
to
del
max
{
1ogi-a
(1a1/19))/1) 2,
Cu
Theorem 2. Let X be a convex feasible set with diameter D and f be convex, L-smooth function over X. Consider the sequence {xi)/=0 C X obtained by Algorithm Then we have
4LD
f(xT) f
(1)
T
If additionally f is (c, 2)) -hhrrp and X is polytope with pyramidal width ö, then ((xT) - < (f(xo) - f*) (x)ex((-cfxx"
(2)
where xx def min
8
IoL D
Proof. Let T' be the number of iterations of the algorithm, TEw the number of Frank-Wolfe steps, Teese the number of descent steps, and Tarop the number of drop steps. Frank- Wolfe steps are the only steps that add vertices to the active set, and they do so one at time. As drop step reduces the active set by at least one vertex, we have Tarop & Tew and thus,
T = TFw + Tárop + Taese & 2TFF + Taese & 2(TFW + Tdese)-
(11)
Next, we bound the primal gap h, = f(x)) - f at iteration t.
First, we consider the case when Frank-Wolfe step is taken. Using L-smoothness of f. the definition of the FW step X = Xx + 7c(v, - x,). and the diameter D of the feasible region yields
h4 h441 f(x,) f(x++1)
>> 71 (V X - vi)
|x] vell
2
72 LDD
7/ (Vf())), Xx - -v))
(12)
2
As v, argmax (V](x,), v) by definition, and by convexity of f, we get
LD
T.
h h1t1 n (Vf(x;) xx)
The
(13)
2
Let 2
LDZ, which yields lower bound on the progress made by the exact line search if f < 1. For we have then
he
LD2
h
h4 h441 > 2/hh
(14)
2
2LD
21

---

If 7/2 > 1, we have by definition he > LD?. We can bound the progress of the line search using
Tt in 13.. which yields
LDa
h1 11411 2 14
2
hr-
(15)
2
Combining
(14 15
have
h2
he
if <
h+41
2LD
(16)
1
he
if > 1
Next, we consider the case when a descent step taken. Using the criterion for performing corrective step, the optimality of and the convexity of f, we have
V [x(x),, a. 8t)
h, - h4+1 f(xx)) - f(x++1)
2LD2
[ X1 - v1)
2LD²
(x -xx--xx+ x²)
2LD
hi
(17)
2LD
Together with (6).. we get
2LD
h
TFw + Tdese
which be shown in the same way in the proof of Corollary 4.2 in Braun et 2019 with 2LD replacing the value 4.y. Together with (II. we get
4LD²
ht T
which proves
Now we prove the accelerated convergence rate @ with the additional assumptions that f is (c, 0)- sharp and X' is a polytope. Again, we will bound the primal gap h, for different steps of algorithm.
First, we consider the iterations when the Frank-Wolfe step is taken. By line of Algorithm we have
(Vf(x),, vi) > (x)(x)) a - Ss) > (Vf(())) xx)
Adding the left-hand side to both sides yields:
2 (xV5 x, v.) fx;)), a; v,)-
(18)
Similar to the proof of the sublinear rate, consider primal progress bound induced by smoothness, specifically (12). and choose specific step size, 7/t
(xx
(V
For the case % 1, we have
L.D2
[[((x), Xx - v.)²
h h
(19)
2LD2
Together with (8) and Lemma 11 we get
fxxt), Xt - vz)²
h: he+1
2L.D2
fxx();) a, v,)²
8L.D2
8c LD h ((1-))
(20)
22

---

In the case 9t > 1 we have (Vf(x)).x) -vi) > LD?
Again, we can bound the progress of the
exact line search using 7/ in which yields
LDa
he het1 > ( Xt - vi)
2
V fxxx), (x -vi)
(21)
2
f xi)
1
2 hr.
(22)
2
For the descent step, we have
(Vf(x,), a 8t) 3 (Vf(x,), X - vz) 3 (VI(x;)) ve)
Adding (Vf(x)). st) both sides yields
(V)(x,), sx) (Vf(x,), vo)
Together with the definition of a descent step, line 6 of Algorithm T and again Lemma 11
we get
f a
h4 h4+1
2LD2
V (xx), a4 Vi)
8LD2
8²
21100)
h4
(23)
_ LD
Together with 200g and 22
we have
8²
h4 h441 he min
h
(24)
2
80
LD
for any iteration that a drop step. For 0
1. this simplities to
1
8²
he41 & min
h4-
2
8c2
LD
By 11 and the fact that drop steps are non-increasing, i.c., hx+1 & hr, we have
82
Tuos
ht < ho min
2
Sr.2.12
< ho 20
< ho exp (-cr,xT))
where cf,x min
82 16c 1,7e
Next, we prove that different types steps arising in typical FW variants satisfy the requirement from the CFW framework.
Proposition 1. Algorithm 3 Algorithm 4 and the simplex gradient descent step from Braun et al.
2019 satisfy the criteria of Algorithm
Proof. First, we consider the local pairwise step given in Algorithm 3 point produced by a short step, i.c., 7 L||a-s||
Let 7(a s) be the
(V/(x).a-s) If & & Tmaxx we have by smoothness of f that
IG²
||a s/ (Vf(x), 1 s)²
(V)()), a - =s?
f(x) f(x) > (Vf(xx) a -s)
2L a s|
2LD2
23

---

Hence, & satisfies the criteria of the descent step, and thus so does x' produced by the optimal step size y"
y > Tmax. convexity of f yields that either fxx) & (x) or 7 = Yimax- In the first case, we have valid descent step, and in the second case, have drop step.
Second, we consider the fully-corrective step in Algorithm 4 We compare the update to x. ÿ & Tmax and therefore & E cOnv(S), the descent criterion is satisfied. We now analyze the case cSnv(S). If
f(x') < f(x) then we have a valid descent step. However, if f(x' > f(x), we
know that x' & relint(conv(S5) Otherwise, there is a X conv(S) the line segment between and x' with f(x) < fxx'.. This contradicts the optimality of x', thus we have x' à conv Consequently, there exists atom u E S which can be dropped without increasing the objective.
Finally, the simplex gradient descent step of BCG a valid corrective step, as shown in Lemma 4.1 in Braun et al. 2019).
L
Finally, we prove the active set identificatinn property of CFW in finite time under the assumption of strict complementarity.
Theorem 4. Let be a polytope and let f be a convex, L-smooth function over X. Assume that strict complementarity holds. Consider the sequence {x1)t-o generated by Algorithm 7 Then there
exists an iteration T such that
X₁ E F for all t7 T.
Proof. Let > O. For any x" Ex V E V(X) and x E X with ||x- x*1 & E, L-smoothness yields
(Vf(x), x) (Vf(('), ) - x) + (Vf(x) Vf(xx)
(VI(x"), - x*) + (V/(x"), ), -x (V/(x) - VX(x',,
(Vf(x"), -x") / - -V(xx) -
VV Vf(xxxI|
(Vf(x"), - -x" |V fx -||x''' -xxx-xX] -x| X --x-xx111 - -
v=(x"))v-x"
x'1|
(VI(x*), - x*) /
L
(VV(("),, v x")
+ LD)
Strict complementarity with constant > 0 yields now
SC V EC V
(Vf(x), v x) >
For sufficiently small e we have that - 8c > Ec, e.g., s 36 By Theorem 2 f(xT) converges to f*. Since f is continuous and X is compact, follows that dist(x,, x²) converges to O. Thus, there is 7i such that dist(x,, X*), < e for all / > Ti. Therefore, there exists a x E X such that ||x;
x <
Let Vt. a,, S; be defined as in Algorithm
I Next, we consider the cases where the current iterate x; lies inside outside the optimal face F If Xx & F", then there exists E Se \. F Consequently,
we have
V [ - si) (xx)))) x1)
30 Ec (V vv)
(25)
Therefore, CFW would choose to perform corrective step. Let now (p-ec)² there exists T2 such that f(x.) - for all / T2. Next, 25 yields
2LD By Theorem
f(x:) - f < EC- (V)())) a. -s))
2LD
2L.D2
and thus the optimal primal progress is smaller than the required progress for valid descent step in Algorithm Since we cannot perform descent steps and since drop steps are non non-increasing, CFW has to perform drop steps in every iteration ' max(Ti, T2) where x, & F*
Assume now that we always keep one vertex g F the active set. Then in each iteration x, stays outside F², and we would keep dropping vertices until x, V. This contradicts the convergence
24

---

of Theorem Therefore, there exists an iteration T max(T1, T2) such that Sq. S F and thus X F
We turn to the case where X E F*. Strict complementarity and convexity yield
(Vf(x,), - xx) V x,) < Ec v x,)
for any v E ((x) \ FF. Therefore, we have V, E F and thus X,+1 E F as neither FW step nor corrective steps move the iterate X out of F*. Finally, induction yields x, E F for all / > T. O
B Lazified Corrective Frank- Polfe
In this section, we will prove the convergence results of a more general version of Theorem for the Lazified Corrective Frank-Wor Wolfe method (LCFW) proposed in Algorithm
Algorithm 7 Lazified Corrective Frank Wolfe (LCFW)
Require: convex smooth function S. starting point Xg (XY), accuracy parameter J > 1: Po t maXvev(x) (xx())), X v)
2: So f- [xo]
3: for = to T 1 do
4:
a; + argmaxves; V (x+), v)
D. away vertex local FW
5:
St argmin (V (x+), v)
6:
if (VI(x)), Sp) > 4 then
7:
Xt+1: St+1 CorrectiveStep(S,,,..aa st) P141 +- 4z
8:
9:
else
10:
Vi + argmax eeV(x) (Vf(x;). vv
>> global FW
11:
if (V/((xx), vi) 2 then
12:
d, + X V
13:
Tn argmin f(x: yd:)
14:
X++1 t x, de
SH11 S {vr)
16:
P++1 t- p,
b FW step
17:
else
18:
X1+1 f
19:
S t S₁
20:
P1+1 4
gap step
21:
end
22:
end if
23:
end for
Theorem 3. Let X be a convex feasible set with diameter D and f be a convex, L-smooth function
over X. Consider the sequence (x1)To X obtained by the Algorithm Then we have
=
(3)
If additionally is (c, -hhurp and X is polytope with pyramidal width 8, then f(xr) - ( (cxp(-oTT)
(4)
for some constant a > 0 independent T.
Proof. Similar to the proof of Theorem 2 will prove upper bound on the total number of necessary iterations for achieving E primal accuracy.
Let New, Naese Narop, Ngp denote the number of FW, descent, drop, and gap steps, respectively. Let ti...., tvp be the iterations of the gap steps. We set to = -1 for consistency. Then let New and Ni Wesse be the number of FW and descent steps in the i-th epoch, the iterations between f,-1 and t,. To
25

---

bound the total number of iterations T necessary to achieve primal accuracy, we first bound the number of gap steps gap
Let = 1 + for some i E {1,..., Ngpp) be the iteration after a gap step. Note that X = X2, and thus v. Vt,- By convexity and the optimality of Vus we have
2 f(xx)- 5 < (Vf(xx), x") Vf(xx),,. - Va)
< 2
(26)
J
By definition of oo this also holds for u = O. Furthermore, the gap step always halves the value of 4 so we have 4. D1,+1 22 By bounding the right-hand side of (26) by E, we get
240
Nap
log2
(27)
8
With Ndrop New we have that
E New + NNese + Nggpp + Ndrop
2Nrw Ndesc + gap
Naw
2N + Niese + Ngap-
(28)
In the remainder of the proof, we find upper bounds for 2N + Násse by lower bounding the progress of FW and descent steps for both cases considered for f. First, we consider the case where / is convex and smooth.
Let & (t,, t++1), so 9 2.. If we perform FW step, we have that (Vf(x)) vz) > D./J Lu/ Pu/J. Here we can use results from the proof of Theorem i.c., (99 and (2T). which yield
f X vo)²
1 [V vo)
f(x,) f(x++1) & min
2LD22
4u 2J
& u
min
(29)
LD2JJ'
Next, we consider the case of descent step, i.e., (Vf(x;), st) 42. Together with the definition of the descent step, we have
f(x,) f(x++1) (Vx(),)) a, 8,)
22
(30)
2LD
2LD
We now (26) upper bound of the primal progress in the i-th epoch, and use 22) and to lower bound the primal progress. Let
30
[log2
4. 1. For i < 1 we have that do 2 L
T.D
and thus L > L. Then we get with 22
29
and 30
20, > fxx,) l f(x,)
f(x(.+1)
Qu + Niess
42
Now 2J
2T.D2
P,
JJ.JJ
2N/
NN
4J
22N
1
+
Ndoso 2
4.J
and thus
8J, 4
2N + Ni
max
]
(31)
26

---

For i > I we have that 4, < J and thus with (26).
29
and (30
2 > f(x.) - -f"
fxxx) (x
T
T
New
N
2.2
desc
2LD
Φ 2N JLD2J3
+ N dese
2LD
Thus we have
1
2'
2N + N < $
max {8LD2 (
max { (8LD2 (4,LD²)
(32)
We can now bound the number of total iterations using (28 and 27
Nap
T
2N
+ Nosie + Ngn
New 2
4
< max
8J, J
max (8LD"JJ, + Nga
4
< 1 max
8J, J
+ (2 N20 +1 1) 1
max {8LD2 (SLLD?,,ALD')) + Ngap
4
+ (2 200 +2 - -) max (8LD2 J2 (P,4DD3 +
2@o
< 1 -max
8J, 7
log2
D0
4
240
< 1 max
8J, J
+ max {8LD? (2,DD + 1og2
Finally, 26 yields
DT _ o (
f(xT) f
Consider now the case where f is (c, -harr and X' a polytope. Let again u = 1, + 1 for some i E {1,..., Ngap be the iteration after gap step. Then we have
(xf(x,), an vu) (Vf(x.), a. s.) + (Vf((x), X., -vu) < 2 + D./ < 24...
With Lemma 11 we have that
f(xx) -f < (c(Vf(x)) a. Vu)
2oc
+
(33)
With this new upper bound on the primal gap, we can improve the bound on 2. + Ni for i 2 I. Using (33). (29) and (30), we get
200 "
> [(xu) l
8
3 f(xx) f(x((4))
$2
T2
> Now LD2
Nieso 2LD
22N
N
+ dese
LD
4.22
2
Consequently, we have
1c
I
(4.22 2. 1
2N + No
desc
<
8
2 max
2c
1-7
LD
max (4J2,2)
(34)
2:
27

---

For this yields
New
4ca LD max (4.
2N + - dess & N
sap
(35)
82
The bounds for the case
in (31) stay unchanged. Together with (2 and (28) this yields,
App T
2N Fw -Nees Ngap
4
+ (Nyap - 1). 4c² LD2
max 8J, JJ
max (4J2,2) + Ngo
52
2
< CCi & &i log2
E
where C1 =1 max max (8J, }}
LD* max (4
This is equivalent to
< 24 di exp ( (- = (espp (-
Finally, with 333 we get
c (<(V((x)), ar vr)) v.l) < 2c -((ep(-aT))
f(xT)- f &
6
with 2 CT
C Quadratic Corrections
C.1 QC-MNP for convex objectives
In this section, we derive variant of the QC-MNP method tailored for non-strongly convex objectives, ie.. when the affine minimizer might not be unique. This is not only more efficient in practice but also relevant for Theorem 8 to guarantee finite convergence.
For convenience, we restate the relevant linear system,
AVA - w) =0 AvES\(w),
Σ\, VES
(36)
For given solution the ratio test in Algorithm maximizes such that the new weights = + (1 T) Axx) are non-negative. If the solution is not unique, we can choose À that allows for the largest т. This will ensure that we pick an affine minimizer inside the convex hull if such exists.
Adding the non-negativity constraint and the objective to 36) yields the following non- con-iiner program:
max AER" (0)
s.t.
(AVA + b, w) =0 SvES\(w)
1 X = 1, 7À (1 -)--)
As x lies in the relative interior of cSnv(S), there always exists feasible 7 > To obtain linear inequality constraint, we divide the inequality constraint by and set / 1-7
A + 3X(x) 0.
28

---

Since maximizing 7 on (0, 1] is equivalent to minimizing 3 on [0, oo), we obtain the following linear program:
min AERT
B
(37)
.900
s.t.
(AVA+ b, w) =0 Vv
1,
3x(x) > O.
Algorithm presents the alternative implementation of the QC-MNP-correction step, relying on the newly derived L.. We use again Algorithm 3 as a fallback step if there exists no affine minimizer.
Algorithm 8 Quadratic Correction MNP
Require: S.C.C x X
8, À < Solve (37)
if feasible then
if B then
D FCFW step
x' Eves AVv
S' +- S
else
MNP step
1
341
x' + Eves(T +1 -1--)) (xx))
S" + E (x(xx)) > 00}
end if
else
b Fallback step
S' x
LPS S. a,
end if
We can now prove that Algorithm always chooses an affine minimizer in conv(S) if such exists. Lemma 13. Let S X. If of arcoin)) f(x) C argmin fxx), then Algorithm performs an FCFW step.
Proof. Since the linear system in (36) is sufficient optimality condition for the affine minimizer, we know by assumption that it has at least one solution. Furthermore, there exists solution which additionally satisfies À > O. Therefore, 3 and X are optimal solutions to (37) Consequently. Algorithm performs an FCFW step.
C.2 Proofs for Quadratic Corrections
In this section, we prove the results for the quadratic corrections given in Section 2.2
Proposition 5. Equation (6) feasible if and only if span(S) ker(A). In particular, is feasible if A is positive definite
Proof. Instead of (6) we consider the equivalent system Since the matrix W AW is symmetric, the system is feasible if and only if
W (Aw + b) E im WT AW) ker W AW)
One can easily see that ker( (AW) C ker W AW), Let E ker W AW), then we have
W AWv (Wv) ( A(Wv) 0.
and thus Wv E ker(A) since A is positive semi-definite. Consequently,
feasible if and only
W (Ww + for all v E ker( The condition simplifies as A is symmetric,
W (Aw b) v "WT A w + TWWD (Wv) b 0. Therefore, is feasible if and only if b for all z E im(W) O ker(A) This equivalent to b L. span S) ker(A).
D
29

---

Proposition 6. QC-LP and QC-MNP satisfy the criteria of corrective steps in Algorithm
Proof. For the QC-LP, if the LP in 7 feasible, the solution coincides with the FCFW step. If the LP is infeasible, we perform local pairwise step, which satisfies the criteria of a corrective step, as shown in Proposition T
For QC-MNP, if a solution of 6 exists and lies already in the |i-mpipe, the step is equívalent to the FCFW step. Otherwise, we perform a drop step, because at least one new weight is negative. The primal value does not increase, as f convex and one moves towards the affine minimizer. If there exists no affine minimizer, perform local pairwise step.
Proposition 7. Let X be polytope and F be the minimal face of containing the optimal points X" S C FF, then 2ead(S) fxx + 0. If additionally there exists x* E X with x" E conv(SS, then x" (agmminzaaf(()) (1:)..
Proof. For contradiction, assume the problem milxxea((s)) [(x) would be unbounded. Then there exists an X E (S) such that fx) < f*. If the optimal face F is singleton, S would be also a singleton yielding x E (S) C X' which contradicts the minimality of f*. If If at least one dimensional, there exists an x* E relint(FF) (F* due to minimality and convexity of F². Consequently, there exists À E (0. 1) with y Λ (1 A)x F C X. Convexity yields then,
f(y) f(*x + (1 A)x*) < Af(x) + +1 (1-))((x'* <S
which contradicts the minimality of f*. Consequently, the problem is bounded below by f If there exists an x* E X n conv(S), then is also a solution to the affine problem since x* aff(S). O
Theorem 8. Let X be polytope and let f be convex, quadratic function over X, iee. f(x) Ax) + (b, x) + c where A is a symmetric positive semidefinite matrix. Assume that strict complementarity holds. Consider the sequence {x:]T= generated by Algorithm 7 with Algorithm Algorithm 5 or Algorithm Then, there exists an iteration such that Xx E X
Proof. By Theorem 4 we know that there exists Ti such that St C J= holds for all t > Ty. Let
min dist(conv($),
SCV("))
(S)
By Theorem 2 there exists a T2 such that dist x²) < E and thus dist(conv(S.) X²) < holds for all > T2. Consequently, we have conv X for all t Ty. In total, we have St C F and conv (S,) nM # 0 for all t > T m, T2).
By Proposition 7 we know there exists an E argmin f(x) n x C conv(S.) for all t> Т. If CFW performs now fully-correctivve a QC-LP step, converge directly to x" E X For QC-MNP, we need to use the implementation in Algorithm Otherwise, we might pick an affine minimizer not in X, see Lemma 13
Finally, remains to show that CFW performs a corrective step after at most some finite iterations after î. By Theorem we know that v. F* for all T. If E S,, then (V,(x,), v:) = (v)(x),, and thus
[x v.) < (V)()),
Therefore, CFW performs an FW step if v, & St- This yields that CFW could perform at most [V(F*) | consecutive FW steps after T, before performing corrective step.
D Split Conditional Gradient
In this section, we consider the Split Conditional Gradient (SCG) method of Woodstock and Pokutta 2025). The algorithm is presented in Algorithm
30

---

2025 The key difference is Algorithm 9 Split Conditional Gradient (SCG)
Require: Convex, smooth function ʃ. weights {wi)ier C (0, with Eier wi 1, starting point
E iX1s (E1 &
1: Xo f Lier WX
2: for 1= 0,0,1 1, do
3:
Choose penalty parameter A 0
4:
Choose step size to E (0,1)
5:
g: - fx(:)
6:
for i E do
7:
vi + argmin (ge + Ae(x 81).v)
8:
x + x + mi(;; x()
9:
end for
Xx+1
EiEl wix!
11:
end for
We prove the convergence rate of the SCG method stated in Theorem in general setting, ie.. for arbitrary Hilbert spaces and any finite intersection. Let be a real Hilbert space, let H 4t be the product space of H. We denote the components of H as (x+ ,..., ). Let = {x ε H x = x2 ... x") denote the diagonal space of H. Furthermore, let 1= (1,.... m and let {w: be selection of weights such that wh 0 for all I and
Eier w; = 1. The averaging operator is defined as A: 7 + H: X H CiEr W,X'.
Proposition 14. /Woodstock and Pokutta be a finite selection of non-empty, compuct, and convex sets of H. For every À > O, set Fx(x) f(Ax) + À d Suppose that (Na)nen / co. Then 2
2025
Proposition 2.13] Let f H - R. let (Xt)EE)
lim (+000 XEXxer X;
inf
Fx,(())
inf lim Fx, (x)(x)) = xE X; (1-000
inf f(x).
XEX X,
Theorem 15. Let f: H + R be corvex and L-smooth and let (Ki)ier be a finite selection of non-empty, compact, and convex sets of H with diameters (Ri and Nier X: $ D. For X 2 O. ser (x f(Ax) + 2 dist) x arrgiinxen Fx, (x) and H, = Fv, (x,) Fx, Fx,(x;). For 2
d₂ In(l + 2) and the step size 7t (1+21m(442) for all 2 the iterates of SCG satisfy
0 Hi & (L 22g
(38)
Vi+2
for all t > O, where cf def max ex x, f(Ax) - f(A)) < 3o and R del Eier W.R.R
Furthermore, we get that limy-+00 Fx, (xx) = infxex,er N, f(x) and lim, distp(xi = 0. In
particular, any accumulation point & of the sequence {xt tezu lies in Nier X₁ and satisfies f f(AX) inlxex N. (x))
Proof. This proof is inspired by the proof of Woodstock and Pokutta analyze the alternative auxiliary objective,
Fx Fx(x)
f(Ax) +
I dist (x).
We will see that one can find smaller upper bounds on the primal gap H, = (x,) FA, (x;). However, even for X, H, H,, we achieve faster rates of convergence. Note that
x E argmin Fx, (x) argmin Fx, (x),
xEX,er X.
xEX:er X,
since Ps, and Fx, only differ in scaling. Furthermore, the function Fx, is ( +
+1))smmoothh -smooth.
31

---

Analogous to Lemma 3.2 in Woodstock and Pokutta (005], we first prove a bound on the primal gap H4 Using smoothness, the FW update rule, the optimality of the FW vertex Ve, and convexity, we get
Fx, (x4+1) - Fx, (xx)
+
VFx, (xx) Xx+1 x,
A. +
||
xel2
2
L
+
= (VF,, (xi); V2 -xxx +
A
llve -x1l1
"
L
+
<7 (V (xi); xi -xi) -xx)
Ax
1i
R2
2
< (F(x)) (xx)) + 78
R2
L
+1
where R2 is an upper bound on ||x y|1 for all x,y Nier Xi see Woodstock and Pokutta 2225 Lemma 3.1]. Adding Fx, (xt) Fx. (x?) to both sides leads
+ 172 R2 A
(x.1)) < (1 -1) (xx, (xx) Fs, (xx
2
H.
Together with the definition of Fx, and the optimality of x yields
H.4 Fr... (xx+1) Fxom (x(+1)
1
1) (F(Ax)+1) - ((Ax++))
(x++1) 1x((x(++ +
A141 X,
(x111 (x(()))) +
(F(AX)L1) ((Ax++1)
Aet1
(1-11 1
--1)
< (x.1)) (x +
(xx
Aet1
(1 1 1
< (x++1) (x)) +
A4+1 )
+1
(
-111)
1
< (1 - 71) Hi + R2
tcl
(39)
2
de
A
where ey maxx.yex,e X. f(Ax)
f(Ay) co. The result in 39 analogous to the result in
Lemma 3.2 in Woodstock and Pokutta 2025 However, it involves difference of inverse values of
Ax, which will be the key difference here. This allows us to use larger step size "/t (EF2in(t+2) for the SCG method.
For the given d In(t 2) and by using In(x) < 1, we obtain
L+3 In
1
Ae+1 A
1+2
1
(40)
X
A+41
X;
In(t + 2)
(t+ 2) In(t + 2)²
We can now show by induction that
E H. & G. del 2R +1) 1)+ /2eg
(41)
21+2 +2)
32

---

For t = 0 we have
Ho - (x0) - Fxo (x6)
s(Ax0) ((Ax))
+ dist (xo) - disti(x)) (xo)
A0
2
cf
R²
(2)
2
2 (L 1) + V2ef Go-
(2
The induction hypothesis together with (39 and 40 yields
+1
c ( - 1)
-
Ho+1 (1- - H1 + 7/ RR R
2
Net1
vt +++22n( + 2) G. +
2R (R+1++1) +1)
V2es
(1+ 2) In(t + 2)2 + 2) + 2)²
Vt+ 21(( +
2l + -2)
(21 (L + + + v20g)
(1+ In(1 222
31+31n(++3) (2R + V20)) = T441-
To finish the induction, it is left to show that
V 2n(( + 2) -1
< (t + In(t + +2)
V1+31n(t +3)
Consider
vt + 21n(t + 2) Ilnt +
(1 22+2)
=In
II+
(t+2 VF+2
In
[+1
(t+ (1+])+AZ-VEF
-V + 2
1 (+++tt
(v1+2 i+1
vt+ In(t +
v++2 2 def (t).
[+1 1
The function (() is monotonically decreasing and satisfies <(t) < 1 for t 2 1. Thus, we have
2 + 2) < vt 1 1 + 1), for all > 1. One can even see that (42) holds for 0. It remains to show that
(42)
vt + T 1) 3) < (t 2) In(t + 2)2.
One can easily see that Furthermore, using twice the concavity of In yields
122 + 41 + 4 - 1 2.
In(I(( + 1) In(t + 3)) = In (t + 1)) + In(In(t + 3))
In(t+1)
+ In(t + 3)
2 2l
2
2
[t+1
t+3
< ln
In
2
2
2nn(In + 2)) = In(In(t + 2)²),
33

---

and thus
In(t+ 1) In(t + In(t 2)
This concludes the induction. Using H, = He yields the proposed upper boundary
= A.Hee & 2R 1) V2c,
+
Vt
Together with Proposition 14 get that lim Fx, (xx) exists and that
lim Fx, (xx))= 10000
lim (x() t-+00
inf f(x). xeXier X
As X - oc, we have dist ( (x,) -> 0. Thus, every accumulation point x lies in the diagonal space D and therefore A& NiEr Nr. Considering subsequence (fx) we get
inf xEfier X.
f(x)= & f(Ax) = lim f(Ax;,) < lim Fx, (xxx) = inf f(x). xefier X,
k-000
k-000
E
Second-Order Conditional Gradient Sliding
In this section, we first introduce the SOCGS algorithm before proving its convergence for self- concordant functions.
E.1 SOCGS algorithm
Introduced in Carderera and Pokutta 2020]. the SOCGS algorithm minimizes smooth strongly
convex function / with Lipschitz continuous Hessian V over polytope X.. For each iteration
a quadratic approximation fe minimized over the polytope using a projection-free method.
Minimizing such quadratic forms over polytope amounts to Projected Variable-Metric (PVM)
algorithm Nesterov [0188) Ben-Tal and Nemirovski (Spring 2023] (we state PVM in Algorithm [T].
To do so, Hessian oracle yields for each iteration / an approximation H, of the Hessian fx,,) at the current iterate x,, The quadratic approximatior fa (x) (V f xx) x + 2 ||x x; ll. then built and minimized inexactly using Corrective Frank- Wolfe algorithm. We call this an Inexact PVM step. This step is solved up to some precision on the Frank-Wolfe gap given by the threshold e,. This threshold involves the computation a lower bound lb(x,) < f(x.) f on primal gap.
On top of the Inexact PVM step, the SOCGS algorithm also performs independent corrective steps. as presented in Section 2 We call these steps the Outer Corrective Steps (OCS), outer steps for short. Hence, the SOCGS algorithm enjoys the global convergence rate of the outer steps and the local convergence rate of the Inexact PVM steps.
Now, present the pseudo-code of the SOCGS algorithm. The statement of Algorithm i0]s directly adapted from Carderera and Pokutta 2020). Compared to its original statement, we distinguish the OCS from the Inner Corrective Steps (ICS), inner steps for short, used inside the Inexact PVM step.
'The norm ||x yll / - y) is induced by a symmetric positive definite matrix H.
34

---

Algorithm 10 Second-Order Conditional Gradient Sliding (SOCGS)
Require: Point x E X Return: Point XT X
1: X & argmin (Vf(x). v) So t {xo}: Ax(x)) t- 1 So OCS (xo) f-1
2: x +- X0, 50
3: for = 0 to T do
4:
sCS x +115541+ 1+1 t OCS(CC fl (xx) x0c3 spccs 2o Xocs)
Outer Corrective Step > Call Hessian oracle
5:
H. + ((xx))
6:
fi(x) + (Vf(x),, , x
xz)+ xxx xx-xx x
> Build quadratic approximation
18(x))
7: E + [
00 XL+1 t Xe: 5 f St, A + Xc. h + 0
8:
f(()) x/+ -v v) > do
9:
while maxvEx
> Compute Inexact PVM step
10:
X++ 2411
h+1 ah+1
x+1
h+l
ICS( V fe (e x S 241)
Inner Corrective Step
11:
4 +
12:
end while
PVM x x SPYM Stti 1+1 X1+1
h
14:
if f(xPHM & (xS) then
15:
X++1 f- [+1 Se+1 < SPM Ac+1 + PVM
PVM
D Choose Inexact PVM step
else
17:
DCS X1+1 + x x S.+1 f SOCS
141 A++1 + A
Choose Outer Corrective Step
end if
19:
end for
E.2
Convergence with generalized self-concordant functions
We first recall the definition of generalized self-concordant functions as introduced in |Snn and Tran-Dinh [2019] Definition 2). Let f IR" + R U {+00) be convex function, with its effective domain dfm(()) def {x E [x) +oo}. We assume that dom(f) is an open set and that the function ff is three times continuously differentiable on dom(f) with third order derivative V The function f is a (M, -eneralizzed self-concordant function of order v > O and constant M 0 if
Kv$ (x) u < M ||]l==/(<>)
/ ||v||="", Vx E dom(f), Vu, v IR". (43)
This bound on the third derivative can be used to derive inequalities akin to generalized smoothness and generalized strong convexity.
Proposition 16. [Sun and Tran-Dinh 2019 Proposition 10] Given an (M, -)-geeeral self- concordant function J. then for v 2 2, we have that:
f(y) - f(x) (V)()). - x) & wa (dy (x. Iyy x x()))
(44)
fly) fxx) - (V x x) 3 w (-d (x. y)) ||y x (2)(x))
(45)
where 44) holds if (x. < 1 1 V > 2, and we have that,
M Ily - x||
if = 2 if > 2,
de yx del
(46)
15z 1)M Iyy - x1 3-v Ily x||
where:
e'-r-1
if = 2
1a(1 [-
if
(T) det
(47)
if =
P-2
(1-
2(3-e 2- - 1) -1 -1]
otherwise.
2 u)
Lemma 17. Karimireddy et al.
2018 Lemma 9] Given convex set X and H E S4+ and two
scalars a > 0, 3 0 such that a;
3 I. we have that:
min (V fxx)x) xx) + x
α ||x xx 1
min (Vf(x)), x Xx) +
1
x| - x 1
2
XEX
23
35

---

Lemma 18. [Carderera and Pokutta 2020 Lemma A.6] Given two matrices P, Q E S then we have for all V K
| p <
lvll Enllvllp
(48)
with 1j = max {Amax (P-1Q), Amax (Q 1P) 11
We now present the PVM algorithm in Algorithm II from Carderera and Pokutta (2020) and its convergence for generalized self-concordant functions Theorem
Algorithm 11 Projected Variable-Metrii (PVM) algorithm
Require: Point X E X, step sizes [-.,
Return: Point X E X'
1: for k = 0 K
do
2:
x - argminxex* [(xx)) + (Vf(xx), x- +
||x xx xxllit.))
X1++1 f X + 7x xx)
4: end for
Theorem 19 (Global convergence of the Projected Variable-Metrie algorithm on generalized self-con- cordant functions.). Let X' be a compact convex set of diameter D and f be (M, v) -.l.vv--eeeraizee self-concordant function with v > 2 such that is strongly convex on dom(f) n X if Given a starting point Xo E X n dom(f), (f), the Projected Variable- Metric algorithm (Algorithm) with step size "[k guarantees for all k > 0:
f(x++1) -(xx+1)- f(x')((xxx)))))()))) < (1- (11122 (f(x*) f(x')).
where the parameter Th measures how well Ha approximates V ((x() in the sense of Lemma 18 and "Ik is such that
1
The & min
(49)
2mp
(w(l))
and additionally,
7kk (nwwe(DD
if ifv= =2
(50)
Tkk 1, if 2
(51)
where I is the maximum value, such that:
x
Xx H.
(52)
nk M 12v 1)
where x = argmin (V f(xx), x- Xx.
+
|x - X2 HH
21
if = 3 otherwise.
with Ho
min dER" d ||]]= (x))
||d]|
Proof. The iterate X can be rewritten as:
X
argmin xx
(VI(xx), Xx)
||x
xx
2
(53)
2
seg. Using (M, (-gnnerrrrlle self-concordance of f and Proposition 16 we can write:
f(xx+1) - f(xx) < (xf(x)) xx) + wy (dy (x+, xx+1)) [|x xx11 xx
(54)
(x(e),, X Xx) + mewa (dl (xt, xx+1)) ||x-1 - x
(55)
36

---

where 55 follows from the approximation of the Hessian by H3. If V = 2, we have from 500) that
Th (yww((D) 2m (dy xx+1))
Note that we use the fact that wa(a) & (1/2) hold for all a & 1/2, which we will also use for
other y values. If v > 2, using the upper bound assumption on " (51) and the associated upper bound on the -ornorm (52) we can ensure that:
(xx++1 1 xx.)
1)
M |xx+1
Xx
10- 3- ||x241
Xx ((x)))
V
1)
M
1
|x6+1 -xellv/(xx)
2
11
3-v
V
- 1)
M
|x++1 -
XXelHA H2 < 2
2
3-v
where the last inequality uses the maximum distance in local norm between X₃ and X as a solution to the subproblem. Note that I > O can be ensured, among other means, by the fact that V (xx)
bounded on any finite sublevel set even if the function does not possess a global finite Lipschitz smoothness constant. These two cases ensure that 2yx 2 mas (dy(X X++1)). Continuing the chain of inequalities:
f(x++1) f(xx) < (V (xx), X6+1 xx) + neww (x xx+1)) ||XK- XxI
H.
(56)
V fxx), Xb+1 - xx) + 27 ||xx+1 - Xx HH
2
(57)
min xE(1-76 +
(VI(xx),
x - xx) + 27kx
||x
xx
(58)
where (7p
follows from the upper bound on 7% from (49). (58) directly follows from the definition
of X in (33
fxx++1 f(xx)
(VI((x)) x Xa) + 1. 1|x xallit.
min
(59)
xE(1 - >x + t
27k6
W/( dy (Xx, x²) 117k
((Ff(x))) - xx) + wal wul-da (x),, x"))
min
||x Xxx
Thk
xE xE(1-Tx)x4 tve
20
(60)
W/( (dd (XE,, x² 1m
(VV((x)) x -xx) wyrl dr (xXx, ||x xxx xx s((w))
min (11-7))x4 tre
(61)
W/ dy (XX, x² 11
((Vf(x)),) xx)) + wo( (- du (xxx M), 1|x - Xx s((m))
(62)
17:
W/r( dy (X x" 1)ri
((Vf(x))) x" - -xx) wp ( du (xxx ||x" -xxxl xxx
(63)
Thk
We (1/2)) (f(x*) f(xs))
(64)
7hk
We obtain (60) by applying Lemma with a = 1/Ts and B = me/wa (- (xe. x*)) Note that the lemma requirements impose ? & (h//wy(dd, (x,, x*) )). which is ensured by (49) by monotonicity of
Wy. 61 follows from the Hessian-induuced norm approximation with H₃, i.e., 1/mx ||x xx li <
||x x following Lemma 18 (62) follows from setting in x (1-7w)x+ + into 61
(since x X²). We obtain (63) by considering that 7 < 1, since x;+1 is constructed as convex combination of & and Xs. Finally, (64) follows from (45) and from the fact that (a) & (1/2)
hold for all & 1/2. We can finally rewrite the expression
f(x++1) - f(x*) & (1- (1/2))2 (f(x)) f(x')).
7k
37

---

If Th remains bounded above and below across iterations, fixed step size respecting the hypotheses from the initial statement achieves linear convergence. step size " obtained through line search will achieve more progress per iteration than fixed step size respecting the provided bounds and hence also achieves linear convergence.
Corollary 20. The SOCGS algorithm applied to a generalized self-concordant objective I of purameters (M,)) with 2 2 on polytope X achieves linear convergence when performing Blended Pairwise Conditional Gradients or Away-Step Frunk- Wolfe inner steps for the subproblems if f is strongly convex or if it is the composition of log-homogeneous barrier with an affine map.
Linear convergence of BPCG and AFW on strongly convex generalized self ceff-concrdaant functions was established in Carderera et al. 2024] while the case of the composition of a Nog-homogeneous barrier (a special case of self-concordant functions) was tackled in Zhao 2025 for AFW and extended to BPCG in Hendrych et al. [2023]. Linear convergence of SOCGS itself follows from observing that the algorithm selects the best primal progress between the FW variant and the Projected Variable-
highlight that this result also applies to CGS by using, c.g., AFW or BPCG algorithms for the projection subproblems and starting from a first point in dom(f). Since the algorithm provides primal progress at each iteration, convergence follows from Mis = max Lo. 1/ where Lo- Ho are local smoothness and strong convexity parameters computed the sublevel set of (xo), the value of the initial point.
step, both of which provide linear convergence. Finally,
F Experiment details and additional computational results
In this section, we provide additional details on the experiments presented in Section 4 as well as present additional experiments. For all problems, we use hybrid methods combining QC-MNP or QC-LP with local pairwise steps of the BPCG algorithm. The steps are combined as follows. We use LCFW with J and local pairwise steps the default corrective step. Additionally, if given number of atoms N is added to the active set, a single QC step is performed and the counter is reset afterwards. This hybrid approach yields a good trade-off between the computational cost of solving the linear system or LP, respectively, and the gained acceleration by the QC methods. We consider hy hybrid approaches with other FW methods in Section F.6 As baselines, we use lazified versions of FW. AFW, PFW, and BPCG. All methods use the secant line search strategy from Hendrych et al. 2025). J. yielding sufficient progress. For the actual implementation, we have used the FrankWolfe wel.olffe...o j1 package [Besançon et al. 2022). Furthermore, we use the implementation and setup of Liu et al. 2025 for the entanglement detection problem.
F.1 K- K-Sparse regression
In the first experiment, we consider a sparse regression problem over the K- K-Sparse polytope, i.e.. the intersection of an fnorm ball and an foe -oom ball, (x( B₁ (rK) n B (T). The vertices of the polytope are given by the vectors with entries in f-T, 0, with at most K non-zeros. We consider a classical linear regression problem, i.e., solving
372
min f(x) (EPx(T)
> ((x - y1)² =|AAx 312
given data points {(a,, y1) mm C. 2n x R. We used synthetic data for the experiment and generated normally distributed a; and y1 with n 500 and m 10000. In Section 4 we already presented the results for the case K E {5, 20} and r - 1. Here we provide some more insights into the advantage of the QC methods by analyzing the size of the active set for the more extreme cases K (3, 30). Again, we use fixed interval length of N = 10 for the quadratic correction steps. The results are shown in Figure 5 For smaller K, the necessary active set size for reaching optimality larger. Both QC methods benefit from avoiding running many pairwise steps like BPCG. Therefore, these methods perform earlier FW steps and add more atoms to the active set during earlier iterations. Consequently, both QC methods accelerate the convergence of the primal values and the FW gap.
38

---

12
14
10h0
16/-2
107
1000
2000
3330
1000
2000
120
1.00
200
1003
2000
3092
4000
1000
2033
1000
139
302
199
220
200
100
167
10
10
1411
107
2000 tarstone
3332
1000
Time
Itaratons
Time
Figure 5: Sparse regression with K [3,30] and 7
Entanglement detection
In the second experiment, consider bipartite entanglement detection. Solving this problem is equivalent to projecting given state onto the set separable states,
SAB conv {PA X PB Pa D(A), D(B)),
where @ denotes the tensor product and where D(A) and (BB) are the sets of density matrices on systems and B respectively, i.e., (hermitian) positive semidefinite matrices with unit trace. Consequently, the projection problem can be written as
|l Poll PESAB
min
where || || is the Frobenius norm and Po is the given state. In experiments, consider family of bipartite 3 x entangled states proposed in Horodecki 1997]. Given a parameter a E [0, 1]. these states defined by
0
0
0
a
0
0
a
0
0
0
0
00000
0
0
0
0
0
0
0000
0
0
0
P#
0
0
0
0
0
(6.5)
8a +
1
0
0
0
0
0
0
0
1+a
0
VI-a"
0
0
0
VI-g"
0
1+e
The positive partial transpose (PPT) criterion yields necessary and sufficient conditions for systems of the sizes 2 and 2 3 to be separable; however, it is only necessary for dimees-aimensional systems Horodecci et al. 1996). For a 1), the entangled states Ph are not detected by PPT [Horodecki 1997]. making them weakly entangled and thus harder to detect, which justifies our choice.
Liu et al. 2025 consider adding white noise to the state, i.e.,
Po rp +
9 I.
(66)
for a given noise level v [0, 1]. Figure we present results for different noise levels E (0.95, 0.97) for fixed state with parameter = 0.5. We used again a correction interval of N 1 for QC-MNP and
for QC-LP. Comparing the two plots, one can see that adding white noise decreases the distance to SAB and therefore leads to smaller primal values. Interestingly,
39

---

QC-LP is performing worse than BPCG for the pure state. This is because the LP solved by QC-LP often infeasible, leading to computational overhead without any benefit in terms of primal progress. On the other hand, QC-MNP is reaching optimality in both cases by far the fastest. This indicates that QC-MNP is more suited than QC-LP for non-polytope domains like the set of separable states SAB-
127
10"
307
APCO
10
1071
107
16
10
16'
10/
19.
129
107
2077
157
177
20.
10'*
167
1.2
10'
Hine
Figure Entanglement detection for state Pu given in (66 with different noise levels v {0.95, 1.0} applied fixed state from (65) with parameter 0.5
E,3 Projection onto the intersection of the Birkhoff polytope and shifted Eg ball
Experiment details The Birkhoff polytope (nn) the set of all n x n doubly stochastic matrices, and its vertices permutation matrices and therefore particularly sparse. Furthermore, solve linear minimization problems over the Birkhoff polytope with a complexity ( using the Hungarian algorithm [Combettes and Pokutta 2021].
For shifting the center of the & ball, we first sample vertices Vi,..., Vm of the Birkhoff polytope by calling the LMO with uniform random directions d1,... dm- The ball is then shifted to s such
E V; and d m Σm= d,- The radius of the ball is set that the ball and the polytope intersect if and only if & Note the diameter of the Birkhoff polytope /2n and therefore much larger than the given radius of the ball. This setting can understood as projection onto the Birkhoff polytope with some noise or flexibility in the projection direction.
- Cijlll where
The number of sampled vertices m controls the dimension of the face where is located, i.e., the number of non-zero entries in V. In particular, the expected number of non-zero entries V is
[||v||o] = n (1-
1
n² (1-e
n² 4.
for 1n(11 4). Let B2 c) denote the fg ball of radius and center c. The problem we consider is,
min Xe
f(x)
n - Xol2.
where Xo E gnxx is sampled with uniform distributed entries over [0, 1].
Since the SCG method alternates between updating the point on the Birkhoff polytope and the shifted Eg ball, we use cyclic block-coordinart scheme [Lacoste-Julien et al. 2013 Beck et al. 2015] with different update steps on the two sets. While we perform vanilla FW steps for the &g ball, we compare different methods for updating the point on the Birkhoff polytope. Just like in the other experiments, we compare vanilla FW steps, which are used in the original version of SCG, with BPCG and the mentioned hybrid methods. Note, we use the new penalty schedule A = In(t + 2) proposed in 9 but not the proposed monotonic step size. BPCG relies on step sizes that consider the current FW gap or pairwise gap to perform proper update steps on the active set. The monotone step size would lead to suboptimal updates and thus give the QC methods an advantage, they do not depend on any line search. Consequently, we use the new secant line search proposed by Hendrych al. 2025
Theorem
Additional results In this paragraph, we present additional results related problem settings. In particular, decompose the above problem and solve relaxed settings, projection just onto the
40

---

12 177
10
10
POC OOONN
22
10
20
10"
15
1071
1070
1071
1275
Time
Figure 7: Projection onto the Birkhoff polytope for {300, 500}
10
MEP
1071
101
290
1000
1000
2353
520
1000
0900
2000
100
107
2072
10
250
1000
5:0 7aa Isaratoora
1.000
2000
2000
Perution
Thm 01
Timma Eel
Figure 8: ALM applied to the intersection of shifted Eg ball and the Birkhoff polytope for the intersecting scenario e 0.9 and the disjoint one with c 1.1
Birkhoff polytope, and the intersection problem between the Birkhoff polytope and a shifted l ball for different intersection scenarios. Furthermore, present how SCG with vanilla FW steps both sets perform for the original problem, comparing the new proposed step size schedule with the one from [Woodstock and Pokutta [025].
First, we consider the problem of projecting onto the Birkhoff polytope, i.e., without the additional &g ball constraint. We ran the experiment for E {300, 500} with a time limit of 3600 seconds. For the hybrid methods, we used a fixed interval of N 20 for the quadratic correction. The results are shown in Figure 7 While both QC methods outperform the baselines with respect to the FW gap in terms of the number of iterations, the runtime worse for both instances. This demonstrates the need for fine-tuning the rate of the quadratic correction, especially for easier problems like projections, where the Hessian is the identity matrix.
In the next set of experiments, we consider the problem of finding a point in the intersection of the Birkhoff polytope and a shifted & ball. We use the same setup for placing the l ball as described above. However, since we do not have an additional objective, we use the ALM method by Braun al. [2023] solve the problem. We consider the cases of c {0.9. 1.1), i.e., when the two sets have a full-dimensional intersection and when the sets are disjoint. For all instances, we again used 1. Additionally, we disabled the quadratic corrections until
q 0.1, = 1, n 500, and the active set has at least 30 atoms. This helps to avoid the computational overhead of quadratic corrections in the first iterations when ALM adds and drops atoms very quickly due to its alternating nature. Besides BPCG and the QC methods, also compare the vanilla FW steps from the original version of ALM. The results of the two experiments are shown in Figure
In both experiments, the two QC methods show very similar behavior. For 0.9, i.e., when the two sets have a dall-dimensional intersection, both QC methods and BPCG enjoy linear convergence, while the vanilla FW steps show sublinear convergence. However, QC-MNP and QC-LP converge faster and achieve a smaller FW gap, in terms of the number of iterations and time. In the case of = 1.1, i.e., when the two sets are disjoint, all four methods show sublinear convergence. While QC-LP and QC-MNP accelerate the convergence, especially of the FW gap, the benefit of the QC methods is not pronounced as in the previous experiment.
41

---

18
12
12
107
14
1.7
teerations
Time
Figure 9: Comparison of the new step size and penalty-schedull schedule (N-FW) proposed in Theorem with the original ones (O-FW) in Woodstock and Pokutta 2025
Finally, compare the step size and penalty schedule proposed in Theorem with the ones in the original paper [Woodstock and Pokutta 2025 We compare the new setting for vanilla FW steps, which are used in the original version of SCG. For the experiment,
again used 0.9, q 0.1, We use logarithmic scale on the horizontal axis visualize the difference in the convergence rates more clearly. The results confirm our theoretical results that SCG enjoys a faster convergence with the new step size and penalty schedule.
and n = 300. The results are depicted in Figure 9
F.4 Projecting with quadratic correction in Second-Order Conditional Gradient Sliding
In the experiment of Subsection 4.4 we tested the acceleration provided by both quadratic corrections QC-LP and QC-MNP by comparing the hybrid methods with BPCG for solving the Inexact PVM step at Line 9 in Algorithm I0 For the outer step, use the lazified BPCG.
Due numerical instabilities for the PVM stop condition Line 9 in Algorithm 10 (we were getting threshold values 5, > 0 too close to 0), we replaced the stop condition at Line by fixed number & E {50, 200) of inner steps. Tightening the lower bound estimations 1b(x;) of the primal gaps or designing stop conditions for the Inexact PVM step, which preserve the convergence rate of SOCGS without any lower bound estimation, are left for future work.
During the initial phase of SOCGS, only the outer steps are selected. To avoid the computational overhead of quadratic corrections, do not perform any QC steps in the first 25 iterations of SOCGS. This leads to identical trajectories between BPCG, QC-LP, and QC-MNP at the beginning Figure 4 After iteration 25 SOCGS, both QC-LP and QC-MNP perform in each PVM step QC step at the first inner iteration. A second quadratic correction is performed after 30 atoms were added to the active set Eh+1 of the PVM step. This yields a quick adjustment to the new quadratic model 1++1
and additional correction if relevant amount of new vertices were added the active set. The experiments were run with limit of 100 SOCGS iterations and a time limit of 2000 seconds.
We consider the same structured logistic regression problem over the & ball as in Carderera and Pokutta 2020]. We solve
m
min X (1)
Σ
In exp( (x, zz
|
2m
The labels y {-1,1} and feature vectors z, are taken from the gisette training dataset [uuyon et al.) 2007], so that 5000 and m 6000. As mentioned in [Sun and Tran-Dine -inh 2019 Subsection I,, the function f an example of 3M,3)-gent -ggeeerrall self-concordant function in
(43 where M Vm.max max [||z||] | & E m).
The evaluation of the gradient of
yiZ;
1
vx(x)
- ER"
exp( (x, 2,))
i=1
is computationally demanding, as one has to compute inner products of size for each gradient evaluation. For the quadratic approximations f. exact Hessian approximation H,
42

---

f2x(x) with
1
1
v25(x) = m
I" E R m
(1 exp( V/ (x, + exp(y> (x, 2)))
where I" E Ruxx is the identity matrix. The gradients f of the quadratic approximations ft are given by [x(()) fx(x) + (x
It is worth noticing that in our current implementation, we storing the full Hessian matrices for each PVM step. This could be avoided by computing Hessian- vector products and Hessian- induced norms for any given using the decomposition of the Hessian rank-one terms given in its expression.
Experimenting with line search after the Inexact PVM step. We experimented with adding a secant line search [Hendrych et al., 2025) after the Inexact PVM step and before the if clause at Line L4ii Algorithm I0] We did not see significant change the trajectories as plotted in Figure except for a slight computational overhead of the line search.
F.5
Tensor completion
We consider the non-negative tensor completion problem from Bugg et al. 2022]. in which one reconstructs a non-negative tensor from some entries. The problem is NP-hard, and the corresponding LMO can be implemented as a mixed -ixtedr linear problem, with a polyhedral feasible set. We compare the Blended Conditional Gradient algorithm [Braun et al. 2019]. which was used in the original paper to BPCG, and the two quadratic corrections variants.
Results are presented in Figure TO for different types of instances. All algorithms use lazification. The BCG, BPCG and PFW methods perform well for instances with a low radius and low number of vertices forming the optimal solution. The QC algorithms outperform these methods for larger settings of these parameters, and are particularly advantageous for problems which LMO calls are much costlier than solving any number of linear programs.
F.6 Performance profile and success rates
In this final section, we investigate how quadratic corrections can accelerate Frank-Wolfe variants beyond BPCG. In particular, augment three additional methods with both quadratic correction steps (QC-LP and QC-MNP): an active-set variant of vanilla Frank- Wolfe (FW). Away Frank- Wolfe (AFW), and Pairwise Frank-Wolfe (PFW). For clarity of presentation, we omit the prefix "QC" in the method names; for example, Away Frank- Wolfe with QC-MNP is denoted AFW-MNP, In total, compare twelve methods, four baseline algorithms, and eight variants enhanced with quadratic corrections. We consider 37 quadratic problem instances from the K K-sparse regression problem, the entanglement detection, the Birkhoff projection, and the tensor completion problem with varying problem parameters and seeds. The experiments with SCG and SOCGS are not considered here.
First, we present performance profile illustrating the number of problem instances solved within given time. All methods had a time limit of one hour and 10000 iterations, except for the entanglement detection problem, which allowed 10a iterations. An instance is solved if either the optimality criterion, i.e., FW gap is smaller than 10-7 (or 10-5 for the tensor completion problem), or the iteration time limit is reached. The results given in Figure 11
The graphic demonstrates that QC-MNP improves the performance of all bascline methods. For both small and large instances, methods with QC-MNP belong to the fastest solvers. The QC-LP variants are not as effective as QC-MNP, but still outperform the baseline methods in most cases. This was expected as the benefit of QC-LP is only gained when the affine minimizer lies in the convex hull of the active set, which is not necessary for QC-MNP. In the case of PFW-LP, the benefit of QC-LP is not pronounced as for other methods. The additional runtime for solving the linear problem is not compensated for by the reduced number iterations.
Finally, we present the success rates for the aforementioned methods, i.e., the ratio of QC steps that are colly There are no guarantees as when the affine minimizer lies within the convex hull of the active sets. However, the performance of the quadratic correction steps depends heavily on
43

---

10P
12
10
500
10
BC0
200
400
632
600
1000
2000
200
400
664
309
1000
2006
3000
10
2074
10"
200
400
000
1050
400
E02
1303
2000
3950
Tr 51
Rio stoue
Trene be
(a) d 10, ny
7, P 11
(b) d f2 7, P
30
10'
40
+ DCAMP
10
1000
890
1500
2000
107
10"
18-1
10"
11me 91
Time
(c)
10, Flg
40, p
(d)
10, Thg
40, 30
8 JEW
9 ANV
CORN
107
3379
10"
300
480
250
450
200
7900
1
1950
2872
10"
(c) 12, n1 10, 14
(f) d = 12, no 10, p 15
Figure 10: Results the tensor completion problem. The dimension of the tensor is d d x d. The parameter n, indicates how many vertices were sampled to construct the underlying ground truth, and p the radius of the tensor norm ball.
44

---

FW
AFW
30
FW LP
AFW-LP
Instances solved
PFW-LP
BPCG-LP
FW-MNP AFW-MNP
20
PEW-MNP
BPCG-MNP
10
0
Time (seconds)
Figure 11: Performance profile of different FW methods with quadratic corrections over a problem set of 37 instances.
this. In cases where the affine minimizer lies outside the convex hull, QC-LP uses the local pairwise step, yielding significantly less progress, and QC-MNP must truncate its update.
The results are given Table Table 2 We present the shifted geometric mean the number of fully-corrective QC steps and the total number of QC steps for different problem instances per experiment.
For both the K-sparse regression and the Birkhoff projection problem, the success rates are very high both QC methods. This result aligns with the fast convergence observed in the previous section, where QC-LP and QC-MNP outperformed the baselines, especially in terms of iteration counts. In the entanglement detection problem, the success rates are moderately high for QC-MNP and very low for QC-LP, explaining why QC-LP performs poorly, sometimes this problem class. In the tensor completion problem, the success rates are moderately high. However, the overall numbers comparably small due to the low number of total iterations.
slower than some baselines in
Method
FW-LP
AFW-LP
PFW-LP
BPCG-LP
K K-sparse regression
16/40
29 30
3/4
29 / 30
Entanglement detection
2/ 14803
2/ 544
1/274
2/473
Birkhoff projection
0/
19
1/2
18 / 19
Tensor completion
4/6
3/5
1/3
3/4
Table 1: Shifted geometric mean of the number of successful QC-LP steps and the total number of QC-LP steps across different problem instances.
Method
FW-MNP
AFW-MNP
PFW-MNP
BPCG-MNP
K K-sparse regression
29 / 30
29 30
3/5
29 30
Entanglement detection
68 / 746
492 897
651/933
596 889
Birkhoff projection
/4
28
1/2
18 19
Tensor completion
4/6
3/4
1/3
3 /
Table Shifted geometric mean of the number successful QC-MNP steps and the total number of MC-MNP steps across different problem instances.
45


Reviews:
[{"review_id": "ok6xeC0jkT", "reviewer": "Reviewer_i92J", "summary": "This paper introduces approximate versions of the fully-corrective Frank-Wolfe \n(FCFW) method applied to quadratic objectives.\nFirst, the authors develop a framework for general corrective\nsteps and prove fast convergence rates for their algorithm, which they call\ncorrective Frank-Wolfe (CFW).\nThen they propose two quadratic corrections which specialize their algorithm:\nQuadratic Correction LP, which solves a linear program and then checks if\nit yields a feasible point, and Quadratic Correction MNP, which solves\na linear system and computes the closes feasible point along the chord between\nthe solution and the current iterate.\nExperiments show that these corrective steps outperform significantly outperform\nblended pairwise conditional gradients (BPCG) on synthetic and real-world problems. \nIn addition, the authors develop a faster convergence rate for split\ncondition gradient (shaving off a log term) and also show how to incorporate \nlazy evaluation of the linear minimization oracle into their framework.", "questions": "- Algorithm 1: I assume that every extreme point of $\\mathcal{X}$ is treated as\n  a vertex if $\\mathcal{X}$ is not polyhedral? Or do you require a polyhedral\n  constraint set?\n\n- Algorithm 1, Line 5: What is $P$? Should this be $\\mathcal{X}$?\n\n- Algorithm 1, Line 10: Do you have perform this minimization exactly?\n\n- Algorithm 2: Where do $s, v$ get used? Aren't these equivalent to $u, w$ in\n    the descent step?\n\n- Algorithm 3: How often can we expect Eq. (7) to return an interior point\n    (see also detailed discussion)?", "limitations": "Limitations are reasonably addressed with the exception of using only a single\nexperimental baseline. \nThe authors should provide a strong argument justifying this choice in the\npaper or they should extend their comparison to include additional methods.", "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\n- The theoretical framework for CFW is general and may encourage other\n  researchers to develop corrective steps for non-quadratic objectives.\n\n- The quadratic corrective steps work very well compared to BPCG, both\n    in terms of iterations and wall-clock time.\n\n- Corrective steps can also be applied to split conditional gradient and\n    and conditional gradient sliding.\n\n- The authors improve the best known convergence rate for split conditional\n    gradient.\n\n- The paper is well-written.\n\n**Weaknesses**\n\n- The corrective steps the authors propose only apply to quadratic objectives.\n    This may not be a strong restriction since Frank-Wolfe requires a linear \n    minimization oracle, which already restricts the function class in practice.\n\n- No evaluation of the success rates (i.e. how often they reduce to FCFW steps) \n    of the quadratic corrections is provided. \n\n- The experiments only compare to one baseline algorithm, BPCG. It's\n    not clear how much CFW under-performs the ideal method (FCFW) and how\n    it compares to similar similar methods, like approximate FCFW or pairwise \n    Frank-Wolfe.\n\n\n### Detailed Comments\n\nI am not an expert in Frank-Wolfe methods, so it is difficult for me to judge\nthe novelty and potential impact of this paper. \nHowever, I found it interesting to read and I think there are several clever\nideas here which will be useful to other researchers.\nI particularly like that CFW is presented in a general framework, which will\nencourage other researchers to develop new corrective steps for more general\nobjectives.\nWith this said, I think there are several important issues (discussed in detail\nbelow) whose resolution will improve the paper.\nThus, I will recommend weak accept for the moment, with the option to raise\nmy score if these issues are resolved satisfactorily.\n\n**Limitation to Quadratics**:\nWhile the theoretical results for CFW apply to any corrective steps which\nsatisfy the structure of Algorithm 2, the two proposed corrections are only\nuseful for quadratic objective functions.\nThe authors are straightforward about this limitation, which is refreshing.\nMoreover, Frank-Wolfe methods already require access to a linear minimization \noracle (which restricts the applicable function class in practice), so this\nmay not be too significant a drawback.\n\n**Limited Experimental Comparison**:\nI list that CFW significantly outperforms the BPCG baseline as a strength,\nwhich it is. \nYet, the main weaknesses of this paper is still the experimental comparison.\nComparing to only one baseline in a crowded area like Frank-Wolfe methods\nis limited at best and misleading at worst.\nCFW is an approximation to FCFW, yet there are no experiments presented in the\nmain paper comparing these two methods.\nThe authors also draw attention to approximate FCFW and pairwise Frank-Wolfe as\nthe two closest methods to theirs, but then don't compare them experimentally.\nI think this is a glaring problem in a paper which advertises \"the excellent\ncomputation benefits\" of their approach.\n\n**Success Rates of Quadratic Corrections**:\nThe authors mention in Section 4.2 that \"the LP in the QC-LP is almost never\nfeasible, leading to pairwise steps and thus a similar trajectory as BPCG\".\nThis raises a key question which isn't addressed theoretically or empirically:\nhow often do the quadratic correction methods succeed and return feasible \nsolutions which correspond to FCFW steps?\nSection 4.2 shows that sometimes they mostly fail, meaning solving the\nLP/linear system is a waste of computation overall.\nWhile theoretical analysis may impractical, the paper would be strengthened by\nincluding ablation studies on the success of proposed quadratic corrections.\n\n### Minor Comments\n\n- Line 65: It would be helpful to define the MNP algorithm. Is this Wolfe's\n    minimum-norm point that was mentioned in the abstract? Edit: I see this\n    is introduced in Line 87 but I think it would better to state it here.\n\n- Line 72: The large number of acronyms in this paragraph make the discussion\n  difficult to follow. Some paragraphs later on also devolve into \"acronym\n  soup\".\n\n- Line 118: It would be useful to define $a_t, s_t$, and $x_t$ outside of \n    Algorithm 1. Otherwise the reader has to leave the first paragraph\n    of Section 2, reader Algorithm 1, and then combine back in order to \n    understand the discussion.\n\n- Algorithm 2: I interpret $S' \\subset S$ as non-strict inclusion equivalent to\n  $S' \\subseteq S$. The drop step seems to imply $S' \\subset S$ only in that\n  case.\n\n- Line 168: I think it's simpler and clearer to say \"writing $x^*$ as an affine\n    combination of vertices.\n\n- Algorithms 3 and 4: I think the presentation would be better if these were\n    top-aligned.\n\n- Line 176: \"The QC-LP approach assumes enforces the\" --- unnecessary word?\n\n- Algorithm 3: $\\tilde{S}$ appears to define the solution $x^*$ in barycentric\n    coordinates. If this is true, how does the local pairwise step\n    reduce the cardinality compared to $S$ as required by Algorithm 2? \n    Or is the local pair-wise step guaranteed to make sufficient progress?\n\n- Algorithms 3, 4: It would be helpful if the return values matched Algorithm 2.\n\n- Line 192: is it ever possible that the number of atoms exceeds the dimension\n    of the atoms? In this case, it will be more efficient to solve directly\n    in terms of $x$, so you can depend on minimum of the dimension and\n    the size of the active set. Is this meaningful at all?\n\n- Theorem 5: This result fits awkwardly into the current story. Maybe\n    you can remind the reader before this paragraph that each\n    sub-step of SCG can be combined with the ideas from CFW to obtain\n    faster convergence. Thus, it is desirable to improve the rates for\n    SCG and bring them into correspondence with the standard CFW framework. \n\n- All Figures: the lines and font-sizes are too small to be legible without\n    unreasonable zooming.\n\n- Figure 1: The scale of the y-axis in the first row prevents these plots \n    from showing any useful information.\n    I suggest subtracting the optimal value (if you aren't already) and \n    changing the y-limit to cut-off the first few iterations.\n\n- Figure 2: Same comments as for Figure 1.\n\n- Line 271: \"Mentioning that quadratic corrections...\"  --- was this sentence\n    supposed to be an internal comment?\n\n- Line 278: \"We remind that each iteration...\" --- Where does the quadratic\n    sub-problem come from? Is this a feature of AFW? I know the authors\n    have limited space, but providing more details would make this experiment\n    easier to understand.\n\n- I think you could cut down on the discussion in Section 1 to get more space. \n    In particular, the contributions subsection is long and could\n    be reduced by summarizing the just key contributions in a bulleted list. \n    Three pages for the introduction is quite a lot for a NeurIPS paper;\n    two pages is perhaps standard.\n\n- It's not necessary to capitalize every word in an acronym when you introduce\n    it. For example, in \"Fully-Corrective Frank-Wolfe\", only Frank-Wolfe \n    should capitalized, since these are proper nouns.", "was_revised": true, "final_justification": "The authors addressed my concerns. They include new baseline comparisons and an empirical study of the success rate for QC steps. As a result, I raise my scores to 5.", "rebuttal": "We thank the referee for their encouragement and feedback and address several points below.\n### Weaknesses\n**Comment on Limitation to Quadratics:**\n\nThe class of quadratic functions already encompasses many real-world applications, making our approach broadly relevant. Moreover, Quadratic Correction (QC) steps can be used to accelerate algorithms that depend on solving quadratic subproblems via FW-type approaches, including SCG and SOCGS.\nIn particular, we have observed significant potential for QC to improve the convergence of SOCGS when optimizing general convex functions.\nBeyond SCG and SOCGS, QC steps are also applicable for submodular function minimization [1] and Frank-Wolfe variants of the Difference Convex algorithm [2,3].\nFinally, we note that requiring access to a linear minimization oracle (LMO) primarily restricts the feasible region, rather than the objective function class.\n\n**Comment on Limited Experimental Comparison:**\n\nWe will add results for additional baseline algorithms, including AFW, PFW, and an active set-based variant of vanilla FW.\nTo ensure a fair comparison, we also augmented each of these methods with QC steps using the same hybrid strategy previously applied to BPCG. We present below the results for the first experiment showing the absolute and relative values of the runtime in seconds and the number of iteration. The relative values in parentheses compare to the corresponding baseline. The full evaluation will be included in the revised version of the paper.\n\n|Runtime in seconds|FW|AFW|PFW|BPCG|FW-LP|AFW-LP|PFW-LP|BPCG-LP|FW-MNP|AFW-MNP|PFW-MNP|BPCG-MNP|\n|-|-|-|-|-|-|-|-|-|-|-|-|-|\n|$K$-Sparse regression $n=500$, $K=5$|2604|1673|1265|1451|**490** (0.19)|534 (0.32)|1197 (0.95)|731 (0.50)|945 (0.36)|950 (0.57)|1374 (1.09)|1130 (0.78)|\n|$K$-Sparse regression $n=500$, K=20$|148|169|222|206|**112** (0.75)|139 (0.83)|249 (1.12)|178 (0.86)|112 (0.75)|146 (0.87)|242 (1.09)|186 (0.90)|\n|$K$-Sparseregression $n=1000, K=5$|3600|3600|3600|3600|3566 (0.99)|**1433** (0.40)|3486 (0.97)|2001 (0.56)|2503 (0.70)|2683 (0.75)|3576 (0.99)|2882 (0.80)|\n|$K$-Sparseregression $n=1000, K=20$|1028|1028|979|1073|486 (0.47)|**548** (0.53)|1454 (1.49)|642 (0.60)|627 (0.61)|654 (0.64)|1467 (1.50)|736 (0.69)|\n\n|Number of iterations|FW|AFW|PFW|BPCG|FW-LP|AFW-LP|PFW-LP|BPCG-LP|FW-MNP|AFW-MNP|PFW-MNP|BPCG-MNP|\n|-|-|-|-|-|-|-|-|-|-|-|-|-|\n|$K$-Sparse regression $n=500, K=5$|10000|5225|3291|3710|**388** (0.04)|431 (0.08)|899 (0.27)|611 (0.16)|**388** (0.04)|431 (0.08)|904 (0.27)|611 (0.16)|\n|$K$-Sparse regression $n=500, K=20$|481|492|784|668|**165** (0.34)|225 (0.46)|414 (0.53)|254 (0.38)|**165** (0.34)|225 (0.46)|408 (0.52)|254 (0.38)|\n|$K$-Sparse regression $n=1000, K=5$|7431|7480|7401|6718|1123 (0.15)|747 (0.10)|1473 (0.20)|1066 (0.16)|**631** (0.08)|700 (0.09)|1159 (0.16)|988 (0.15)|\n|$K$-Sparse regression $n=1000, K=20$|2010|2032|1939|1896|**315** (0.16)|380 (0.19)|736 (0.38)|411 (0.22)|**315** (0.16)|380 (0.19)|721 (0.37)|411 (0.22)|\n\nFurthermore, FCFW is an idealized algorithm lacking a practical implementation of the correction step for general convex functions. This was also one of the motivations for the QC steps, providing a specific algorithm for one problem class that can be performed efficiently and without relying on a tolerance or working limit for the correction step.\n\nFinally, approximate FCFW provides a general framework similar to CFW. The focus of our computational analysis lies on quadratic corrections. The idea of CFW is to provide a flexible framework that unifies already existing methods. Therefore, we do not include a direct experimental comparison between CFW and approximate FCFW.\n\n**Comment on Success Rates of Quadratic Corrections:**\n\nTo provide insight into the computational benefit of QC steps, we measured success rates—i.e., how often the affine minimizer lies within the convex hull of the current active set. Therefore, we not only measure how often the LP for QC-LP is feasible, but also how often the QC-MNP step is truncated.\nWe will provide a table with the per-experiment success rates in the appendix of the paper and present an excerpt from this here:\n\n|Experiment|QC-LP|QC-MNP|\n|-|-|-|\n|$K$-sparse regression $K=5$|37 / 37|37 / 37|\n|$K$-sparse regression $K=20$|15 / 15|15 / 15|\n|Entanglement detection $a=0.5$|2 / 557|6 / 526|\n|Entanglement detection $a=0.25$|2 / 599|7 / 577|\n|Birkhoff projection $n=300$|13 / 17|15 / 23|\n|Birkhoff projection $n=500$|19 / 19|19 / 19|\n\nWhile in the $K$-sparse regression and the Birkhoff projection task, both QC steps are almost always successful, the affine minimizer usually lies outside the convex hull in the entanglement detection experiment.\n\nFurthermore, we would like to emphasize that the scheduling of the QC steps is an active topic of further research. Instead of using a fixed schedule, as in our current experiments, one could employ adaptive strategies that consider the current size of the active set or the success rate of previous QC to avoid computational overhead, as in the mentioned experiment.\n\nFinally, we would like to point to an additional theoretical result that relates to this topic.\nOne can show that under suitable assumptions, the affine minimizer computed in QC steps lies in the convex hull of the active set if the optimal face is completely contained in this hull. In consequence, both quadratic correction steps perform a fully corrective step, which in this case yields the overall optimal point in $\\mathcal{X}$. Thus, quadratic corrections reduce the time of convergence to the optimum to the time until the optimal face is contained in the convex hull of extreme points in the active set.\n\nWe will include this result in the revised version and expand on a strong theoretical consequence of this:\nAssuming $\\mathcal{X}$ is a polyhedron, the function is convex and smooth, and strict complementarity holds, we can leverage the fact that AFW and BPCG identify the optimal fact in a finite number of iterations, a result proved in [4] and extended to BPCG in [5]. These results extend to CFW with QC steps since they operate local pairwise and FW steps, which constitute BPCG, and QC steps, which do not add new extreme points to the active set.\nIn consequence, CFW with QC steps converges in finitely many iterations given the additional assumptions, a strong result that otherwise requires fully-corrective FW.\n\n\n### Minor comments\n\nWe thank the reviewer for the detailed list of editorial suggestions, which helped us to improve the quality and clarity of the paper. There is one content-related comment, which we would like to address:\n\n>Line 192: is it ever possible that the number of atoms exceeds the dimension of the atoms? In this case, it will be more efficient to solve directly in terms of x, so you can depend on minimum of the dimension and the size of the active set. Is this meaningful at all?\n\nA simple example where the number of atoms exceeds the dimension arises with the unit cube in $\\mathbb{R}^2$, where FW selects at least three vertices when the minimizer lies in the interior. In practice, this gap between the dimension and the active set size can be even larger.\nFurthermore, as stated in line 199, one can use the pivoting framework from [5] to decrease the number of atoms to the dimension of the spanned subspace, which is usually much smaller than the full dimension in practice. Empirical results in [5] also showed that BPCG never maintains more vertices than necessary to represent the current iterate.\n\n### Questions\n\n>Algorithm 1: I assume that every extreme point of $\\mathcal{X}$ is treated as a vertex if $\\mathcal{X}$ is not polyhedral? Or do you require a polyhedral constraint set?\n\nNo, we do not require $\\mathcal{X}$ to be a polyhedral constraint set.\nWe generalized the definition of the set $V(\\mathcal{X})$ for non-polyhedral sets to be $\\mathcal{X}$, the set of extreme points, i.e., the points that cannot be written as a strict convex combination of points in $\\mathcal{X}$.\n\n>Algorithm 1, Line 5: What is P? Should this be X?\n\nYes, this is a typo and will be corrected in the revised version.\n\n>Algorithm 1, Line 10: Do you have perform this minimization exactly?\n\nAn exact line search is not required; there exist several step size strategies guaranteeing sufficient descent ([6,7]), which also apply to CFW. We will comment on this in the paper.\n\n>Algorithm 2: Where do s, v get used? Aren't these equivalent to u, w in the descent step?\n\nWe agree, $u$ and $w$ are exactly the local FW vertex $s$ and the away vertex $a$. We will remove $u$ and $w$, simplifying the constraint.\n\n>Algorithm 3: How often can we expect Eq. (7) to return an interior point (see also detailed discussion)?\n\nThe frequency with which the LP in (7) is feasible is problem-specific and can vary significantly, as demonstrated by the experiments on sparse regression and entanglement detection. However, we introduced the result that QC steps are successful when the optimal face is contained in the convex hull of the active set and therefore converge to the optimal point in a single additional step.\n\n\n### References\n\n[1] Provable Submodular Minimization using Wolfe’s Algorithm, D. Chakrabarty, P. Jain, P. Kothari, 2014\n\n[2] Revisiting Frank-Wolfe for Structured Nonconvex Optimization, H. Maskan, Y. Hou, S. Sra, A. Yurtsever, 2025\n\n[3] Scalable DC Optimization via Adaptive Frank-Wolfe Algorithms, S. Pokutta, 2025\n\n[4] Active set complexity of the away-step Frank-Wolfe algorithm, I. Bomze, F. Rinaldi, D. Zeffiro, SIAM Journal on Optimization.\n\n[5] The pivoting framework: Frank-Wolfe algorithms with active set size control, E. Wirth, M. Besançon, S. Pokutta, AISTATS 2025.\n\n[6] Linearly Convergent Frank-Wolfe with Backtracking Line-Search, F. Pedregosa, G. Negiar, A. Askari, M. Jaggi, 2022\n\n[7] The Frank-Wolfe Algorithm: A Short Introduction, S. Pokutta, 2024"}, {"review_id": "uZIbo0zggH", "reviewer": "Reviewer_K84e", "summary": "This work develops a variant of the Frank-Wolfe algorithm, which they refer to as the Corrective Frank-Wolfe (CFW) algorithm. The authors claim it to be a generalization of a previous variant called the Fully Corrective Frank-Wolfe  (FCFW) Algorithm. The authors claim that FCFW is often computationally impractical and their proposed CFW method is a means to overcome this challenge. Their main results derive convergence rates for this algorithm and its lazified variant. As part of their CFW framework, the work also designs two quadratic correction steps: (i) QC-LP which involves a direct linear program and (ii) QC-MNP which is a specialized variant of the minimum-norm point algorithm. With these new quadratic corrections, the authors show that the Split Conditional Gradient (SCG) algorithm enjoys a faster convergence rate of $O(1/\\sqrt{t}),$ improving a $\\log t$ factor from the previously known result. Secondly, for Second-Order Conditional Gradient Sliding (SOCGS), the authors show global convergence for generalized self-concordant functions. Finally, the work empirically demonstrates the computational benefits of their quadratic corrections on four specific problem instances.", "questions": "1. In Algorithm 2, can you explictly highlight when the drop step would be executed and when the descent step would be executed?\n\n2. It is unclear how the three steps in Proposition 1 are to be utilized. Should they be tried one by one in order until either the drop or descent step criterion is met?\n\n3. I am new to this field. However, in my understanding, the convergence rates in Theorem 2 and 3 do not appear to be new. So, what is the benefit of your proposed algorithm? Shouldn't you be quantifying the reduction in the computational effort to demonstrate the superiority of your algorithm?", "limitations": "Yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**:\n\n1. Extremely well-written paper.\n2. The proposed algorithm introduces several corrective steps that can potentially improve computational efficiency. \n3. Empirical results demonstrate significant improvement in iteration complexity over BPCG across a range of tasks.\n\n**Weaknesses**:\n\n1. The theoretical results do not quantify the computational benefits of using the new corrective steps. In particular, it is unclear why the corrective steps lead to computational benefits over the traditional FW update rules. \n\n**Minor issues**:\n\n1. The first two sentences in your abstract are too long. Please break them into smaller, easy-to-digest\n\n2. Explicitly define the vertex set of a compact convex set in the preliminaries section.\n\n3. What is $V(P)$ in Step 5 of your algorithm? I presume you meant $V(\\mathcal{X})$.", "was_revised": true, "final_justification": "The work presents a framework of corrective steps that unifies already existing Frank-Wolfe algorithms, which I find to be interesting and useful. Despite being an outsider, I found the paper well-written. \n\nHowever, there are some aspects that the current draft doesn't address, such as computational benefits of using the new corrective step.\n\nAccordingly, I recommend a borderline accept for this paper.", "rebuttal": "We thank the referee for their encouragement and feedback and address several points below.\n\n### Weaknesses\n\n>The theoretical results do not quantify the computational benefits of using the new corrective steps. In particular, it is unclear why the corrective steps lead to computational benefits over the traditional FW update rules.\n\nWe will strengthen the theoretical results, proving that CFW with QC can converge in some settings in finite time to an optimal solution, independently of any suboptimality tolerance, a strong result that otherwise requires fully-corrective FW (FCFW), which is in general not tractable.\nWe will include this additional result in the corrected version of the paper and state it below:\n\nThe affine minimizer computed in equation (6) lies in the convex hull of the active set if the optimal face is completely contained in this convex hull.\nIn consequence, both quadratic correction steps perform a fully corrective step, which in this case yields the overall optimal point in $\\mathcal{X}$. Thus, quadratic corrections reduce the time of convergence to the optimum to the time until the optimal face is contained in the convex hull of extreme points in the active set.\nAssuming $\\mathcal{X}$ is a polyhedron, the function is convex and smooth, and strict complementarity holds, we can leverage the fact that AFW and BPCG identify the optimal fact in a finite number of iterations, a result proved in [1] and extended to BPCG in [2]. Identification here means that all vertices contained in the active set of $\\mathcal{S}_t$ are contained in the optimal face after this finite number of iterations.\nThis identification result extends to CFW with QC steps since they operate local pairwise and FW steps, which constitute BPCG, and QC steps, which do not add new extreme points to the active set.\nGrouping the two results, we can conclude that CFW with QC steps converges in finitely many iterations given the additional assumptions and therefore provably outperforms existing methods while requiring only tractable steps.\n\n\n### Minor issues:\n\nWe thank the referee for their careful reading and suggestions to improve our manuscript.\n\n>The first two sentences in your abstract are too long. Please break them into smaller, easy-to-digest\n\nIn the revised version, we will split the sentences as suggested.\n\n>Explicitly define the vertex set of a compact convex set in the preliminaries section.\n\nWe agree that the notion of the vertices of general convex sets is not clear. Therefore, we have generalized the definition of the set $V(\\mathcal{X})$ for non-polyhedral sets to be the set of extreme points of $\\mathcal{X}$, i.e., the points that cannot be written as a strict convex combination of points in $\\mathcal{X}$. \n\n\n> What is V(P) in Step 5 of your algorithm? I presume you meant V(X)\n\nWe thank the reviewer for their careful reading and will fix this typo in the revised version.\n\n### Questions\n\n>In Algorithm 2, can you explicitly highlight when the drop step would be executed and when the descent step would be executed?\n\nAlgorithm 2 is only a template for possible correction steps, giving conditions for valid corrections, ensuring that CFW converges. Therefore, it depends on the actual corrective step when a drop step or descent step would be executed. Furthermore, these two steps also do not exclude each other, i.e. a corrective step could meet both conditions at the same time. We will highlight that this is a template of requirements for a corrective step in the revised manuscript.\n\n>It is unclear how the three steps in Proposition 1 are to be utilized. Should they be tried one by one in order until either the drop or descent step criterion is met?\n\nProposition 1 shows that the mentioned steps satisfy the conditions of corrective steps; hence, the criteria do not need to be checked during runtime. Therefore, we conclude that these algorithms suit the framework of corrective FW. Furthermore, we mention in remark 2 how these steps can be used as fallback options for new steps, which do not satisfy the conditions of corrective steps in each iteration.\n\n\n>I am new to this field. However, in my understanding, the convergence rates in Theorem 2 and 3 do not appear to be new. So, what is the benefit of your proposed algorithm? Shouldn't you be quantifying the reduction in the computational effort to demonstrate the superiority of your algorithm?\n\nThe idea of CFW is to present a framework of corrective steps that unifies already existing algorithms through the concepts of local updates on the active step.\nBy providing proofs for convergence rates in two problem settings, we encourage other researchers developing new algorithms for which they only have to check that their corrective steps meet the mild conditions in Algorithm 2.  \nQuadratic corrections, however, enjoy faster convergence guarantees under the additional assumption that the objective is convex quadratic. CFW with QC steps converges to the optimum in finite time if $f$ is convex and smooth, strict complementarity holds, and $\\mathcal{X}$ is a polytope.\n\n[1] Active set complexity of the away-step Frank-Wolfe algorithm, Immanuel Bomze, Francesco Rinaldi, Damiano Zeffiro, SIAM Journal on Optimization.\n\n[2] The pivoting framework: Frank-Wolfe algorithms with active set size control, Elias Wirth, Mathieu Besançon, Sebastian Pokutta, AISTATS 2025."}, {"review_id": "V3ZKCrJLpx", "reviewer": "Reviewer_eCQa", "summary": "The authors propose a Frank-Wolfe algorithm with corrective steps. Their modification relies on a relaxed optimality condition, as detailed in Algorithm 2. They then specialize the proposed algorithm and establish convergence guarantees for quadratic functions minimized over an affine hull.\n\nThe paper also presents results for constraint sets formed by the intersection of two convex sets. Finally, it extends the analysis from optimizing strongly convex functions over polytopes to self-concordant functions.\n\nThe main message of the paper is that the proposed modification accelerates the algorithm, and this claim is supported by numerical experiments presented in the final section.", "questions": "1. Could the authors clarify whether their claim is that they analytically outperform existing algorithms for a specific family of functions or constraint sets? Or is it primarily an intuition they aim to convey by guiding the reader through the steps of the algorithm? In particular, could the authors be more precise about the following statements:\n“It converges within a single step to the optimal value as soon as …” and “This is both computationally more efficient and avoids dropping too many potentially good vertices from the active set.”\n\n2.  In Section 3.1, which algorithm was ultimately used? Is it the one from [1] with a modified step size? If it is exactly the algorithm from [1], what is the relationship between this section and the rest of the paper? If it is not the same as [1], why is this not clearly stated in the theorem’s statement?\n\n3. It would be helpful if the authors could specify what the step size was in [1] and what the main technical challenges are in improving the logarithmic factor beyond simply adjusting the step size.\n\n4. In Section 3.2, the authors state:\n“Unlike regular FW variants, CGS requires only \n$\\mathcal{O}(\\sqrt{\\epsilon}$ gradient calls to achieve  $\\epsilon$-optimality.” It would be useful if the authors could also mention the gradient call complexity required by standard Frank-Wolfe algorithms for comparison.\n\n5. Regarding the result mentioned in Section 3.2, “we extend this rate to generalized self-concordant functions,”\nhave the authors actually extended the algorithm to self-concordant functions? Could they please clarify this part and elaborate on the technical challenges involved?\n\n6. Regarding the results for quadratic functions, could you generalize your analysis to quadratic functions with a positive semi-definite matrix instead of a positive definite one? Additionally, instead of restricting to strongly convex functions, could you provide comments on functions that satisfy the Polyak-Łojasiewicz (PL) condition?\n\n\n\n[1] Zev Woodstock and Sebastian Pokutta. Splitting the conditional gradient algorithm. SIAM Journal on Optimization.", "limitations": "I address the limitations that I have in mind in the previous sections..", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Weaknesses:\n\nThe main weakness of the paper is that some of its claims feel vague and hand-wavy, lacking concrete justification. I attempt to clarify these points by raising questions in the following sections.\n\nStrengths:\n\nAside from these concerns, the algorithms and technical proofs are presented very clearly and are a pleasure to read. The literature review covers most of the important related works.", "was_revised": true, "final_justification": "The authors have addressed all of my concerns; therefore, I am maintaining my score.", "rebuttal": "We thank the referee for their encouragement and feedback and address several points below.\n\n### Weaknesses:\n\n> The main weakness of the paper is that some of its claims feel vague and hand-wavy, lacking concrete justification. I attempt to clarify these points by raising questions in the following sections.\n\nThank you for pointing out that some of our claims lacked clarity. We will revise the manuscript accordingly to make the arguments more precise and to provide clearer, more concrete explanations where needed.\n\n### Questions:\n\n> Could the authors clarify whether their claim is that they analytically outperform existing algorithms for a specific family of functions or constraint sets? Or is it primarily an intuition they aim to convey by guiding the reader through the steps of the algorithm? \n\nOur main result is that the novel quadratic corrections outperform existing FW methods for quadratic convex objectives, provably in certain settings we expand below.\nComputationally, the experiments provide empirical evidence for this performance.\n\nWe can prove that under suitable assumptions, CFW with QC steps converges in a finite number of iterations to the optimum, a strong result that otherwise requires fully-corrective FW (FCFW). This finite-time convergence to the optimum is independent of any suboptimality tolerance; we reach the optimum up to floating-point error in finite time.\nWe will include this additional result in the corrected version of the paper and state it below:\n\nThe affine minimizer computed in equation (6) lies in the convex hull of the active set if the optimal face is completely contained in this convex hull.\nIn consequence, both quadratic correction steps perform a fully corrective step, which in this case yields the overall optimal point in $\\mathcal{X}$. Thus, quadratic corrections reduce the time of convergence to the optimum to the time until the optimal face is contained in the convex hull of extreme points in the active set.\nAssuming $\\mathcal{X}$ is a polyhedron, the function is convex and smooth, and strict complementarity holds, we can leverage the fact that AFW and BPCG identify the optimal fact in a finite number of iterations, a result proved in [2] and extended to BPCG in [3]. Identification here means that all vertices contained in the active set of $S_t$ are contained in the optimal face after this finite number of iterations.\nThis identification result extends to CFW with QC steps since they operate local pairwise and FW steps, which constitute BPCG, and QC steps, which do not add new extreme points to the active set.\nGrouping the two results, we can conclude that CFW with QC steps converges in finitely many iterations given the additional assumptions and therefore provably outperforms existing methods while requiring only tractable steps.\n\nThis result will be added to Section 2 of the revised paper.\n\n> In particular, could the authors be more precise about the following statements: “It converges within a single step to the optimal value as soon as …” and “This is both computationally more efficient and avoids dropping too many potentially good vertices from the active set.”\n\nThe theoretical result relating to the first statement is explained in detail in the previous section. \nWe will formulate the given statement more explicitly in the revised version of the paper.\n\nRegarding the second statement, we will also clarify the benefits of QC-MNP over the MNP-Correction step from [4].\nUnlike QC-MNP, the MNP correction step performs multiple rounds of the affine minimization and truncation until the affine minimizer lies inside the convex hull. Thus, QC-MNP comes with a smaller per-iteration cost. Furthermore, both methods can drop vertices from the optimal face in the worst case. Therefore, multiple rounds of truncation in the MNP correction step can become costly in terms of LMO calls.  \nFinally, and maybe most importantly, the MNP correction step does not specify how the affine minimization is performed.\nIn the case of quadratic objectives, our method can be directly used for this.\n\n\n> In Section 3.1, which algorithm was ultimately used? Is it the one from [1] with a modified step size? If it is exactly the algorithm from [1], what is the relationship between this section and the rest of the paper? If it is not the same as [1], why is this not clearly stated in the theorem’s statement?\n\nWe will improve the explanation of how Section 3.1 connects with the rest of the paper.\nThe algorithm we propose here is the modified step size, which improves the convergence guarantees of SCG.\nTheorem 5 performs Split Conditional Gradient (SCG) with standard FW steps, thus it does not rely on CFW.\nIf the original function is quadratic, SCG performs a FW step on a quadratic subproblem changing at each iteration,\nwe therefore propose to use QC to accelerate convergence.\nThe modified step size and resulting accelerated convergence were added to improve the algorithm, besides the acceleration by QC steps, complementing the computational acceleration from QC with an algorithmic improvement.\n\n\n>It would be helpful if the authors could specify what the step size was in [1] and what the main technical challenges are in improving the logarithmic factor beyond simply adjusting the step size.\n\nThe main technical challenge is the analysis of an alternative auxiliary objective, which ultimately allows us to use a smaller step size, which would not have worked in the original proof. Furthermore, we simplify steps of the original proof by providing an explicit schedule of the penalty parameter $\\lambda$ instead of the recursive one. We will state these challenges in the corresponding paragraph.\n\n\n>In Section 3.2, the authors state: “Unlike regular FW variants, CGS requires only $\\mathcal{O}(\\sqrt{\\epsilon})$ gradient calls to achieve $\\epsilon$-optimality.” It would be useful if the authors could also mention the gradient call complexity required by standard Frank-Wolfe algorithms for comparison.\n\nStandard FW methods compute the gradient in each iteration, therefore require $\\mathcal{O}(\\epsilon)$ many gradient calls in the general convex, smooth setting. We will add this fact to the given paragraph.\n\n\n> Regarding the result mentioned in Section 3.2, “we extend this rate to generalized self-concordant functions,” have the authors actually extended the algorithm to self-concordant functions? Could they please clarify this part and elaborate on the technical challenges involved?\n\nWe kept the improved convergence result in the appendix due to space limitations.\nIn the revised version, we will add a simplified version in the given section.\nWe established that SOCGS converges and established the linear convergence rate for generalized self-concordant functions that are not globally Lipschitz-smooth. The challenge lay in the replacement of properties resulting from Lipschitz smoothness with inequalities derived from the generalized self-concordance.\n\n\n> Regarding the results for quadratic functions, could you generalize your analysis to quadratic functions with a positive semi-definite matrix instead of a positive definite one? Additionally, instead of restricting to strongly convex functions, could you provide comments on functions that satisfy the Polyak-Łojasiewicz (PL) condition?\n\nOur analysis does not require positive definiteness of the quadratic objective; both quadratic correction steps only assume convexity, so they remain applicable when the objective is defined by a positive semi-definite (PSD) matrix. In particular, the results extend to general convex quadratic functions, even when the Hessian is singular.\n\nRegarding the PL condition: although we do not assume it directly, we prove linear convergence under the assumption that the objective is 1/2-sharp. For smooth objectives, 1/2-sharpness implies the Polyak–Łojasiewicz (PL) condition, so our results cover a broad class of functions beyond the strongly convex case, including those satisfying PL.\n\nThe only place in the paper where we do require strong convexity is the analysis of SOCGS; indeed, a strongly convex function is required and inherited from the original SOCGS paper, since the Hessian needs to induce a metric. It is an open question whether this assumption could be removed in future work; communication with the SOCGS authors confirmed that removing this assumption prevents the analysis from being carried over.\n\n### References\n\n[1] Splitting the conditional gradient algorithm, Zev Woodstock and Sebastian Pokutta. SIAM Journal on Optimization.\n\n[2] Active set complexity of the away-step Frank-Wolfe algorithm, Immanuel Bomze, Francesco Rinaldi, Damiano Zeffiro, SIAM Journal on Optimization.\n\n[3] The pivoting framework: Frank-Wolfe algorithms with active set size control, Elias Wirth, Mathieu Besançon, Sebastian Pokutta, AISTATS 2025.\n\n[4] On the Global Linear Convergence of Frank-Wolfe Optimization Variants, Simon Lacoste-Julien, Martin Jaggi, 2015"}, {"review_id": "8ajtwF9G9L", "reviewer": "Reviewer_4JW7", "summary": "The authors introduce Corrective Frank-Wolfe, a framework unifying many frank-wolfe algorithms. They describe two correction schemes for quadratic problems which are implementations of the new framework. They also mention two specific algorithms which should benefit from the proposed quadratic corrections. Finally the authors present some empirical results demonstrating the convergence rates of their corrected algorithms.", "questions": "See questions under “weaknesses”.\nSome proofing mistakes:\n* In algorithm 1, the global FW vertex uses V(P) which is undefined (I assume you mean V(X)?)\n* In 2.1 you don’t prove your theorems, you only state them, so you should write “in the following we state two theorems”. It’s fine to have proofs in the appendix if they aren’t particularly enlightening.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths\n1. The framework of Corrected Frank-Wolfe seems to be a useful generalization of existing algorithms, potentially enriching future work.\n2. The specific implementation of the framework for quadratic optimization is novel and seems useful as well.\n3. The experiments show significant improvement over the baseline.\n\nWeaknesses\n\n1. Remark 1 after proposition 1 should have been elaborated on. Why would choosing the pairwise gap lead to fewer LMO calls than choosing the away gap?\n2. The paper is very dense in details making it hard to follow. Almost every paragraph contains either new ideas or new formalisms, which leaves little room for explanations. For example one of the major claims of the paper is about SCG and SOCGS, but SOCGS only has one small paragraph and SCG has a theorem with no proof. From reading the paper alone I couldn’t figure out your contribution to these algorithms.\n3. The experiments only compare with one baseline algorithm. More should have been measured, there’s no guarantee that BPCG is the fastest algorithm for the two example problems given, making its choice as baseline questionable.\n4. The experimental section contains graphs which aren’t explained well. There are 8 sets of images for each figure but its not clear what’s the differences between them. Are they different experiments? Different seeds?\n5. It would be beneficial to add a direct speed comparison between the algorithms. How much faster is your approach at reaching a specified gap value?", "was_revised": true, "final_justification": "Due to the authors' adequate response to my clarity concerns and their thorough new set of experiments, I'm increasing my scores for quality and clarity. While I still believe the paper requires significant revisions for clarity, particularly in the presentation and explanation of figures, the response demonstrates a clear effort to improve, so I changed my scores accordingly.", "rebuttal": "We thank the referee for their encouragement and feedback and address several points below.\n\n### Weaknesses\n> Remark 1 after proposition 1 should have been elaborated on. Why would choosing the pairwise gap lead to fewer LMO calls than choosing the away gap?\n\nThank you for pointing this out. For standard Corrective Frank-Wolfe (CFW), the local pairwise gap yields the same number of LMO calls but fewer FW steps since it is larger than the away gap. The lazified version of CFW, which is introduced later in the paper, only calls the LMO if an FW step is performed. Thus, the number of LMO calls for LCFW is smaller. We will update the corresponding sentence to clarify this.\n\n> The paper is very dense in details making it hard to follow. Almost every paragraph contains either new ideas or new formalisms, which leaves little room for explanations. For example one of the major claims of the paper is about SCG and SOCGS, but SOCGS only has one small paragraph and SCG has a theorem with no proof. From reading the paper alone I couldn’t figure out your contribution to these algorithms.\n\nWe will streamline the presentation of the article. The theorem for SCG is proved in the appendix due to space constraints; we will mention it specifically. Similarly, for SOCGS, we will state the theorem on self-concordance in the main part of the text.\n\n> The experiments only compare with one baseline algorithm. More should have been measured, there’s no guarantee that BPCG is the fastest algorithm for the two example problems given, making its choice as baseline questionable.\n\nWe agree that relying on a single baseline could limit the conclusions drawn from the experiments. \nTo address this, we will add results for additional baseline algorithms, including AFW, PFW, and an active set-based variant of vanilla FW. \nTo ensure a fair comparison, we also augmented each of these methods with QC steps using the same hybrid strategy previously applied to BPCG. These additions provide a broader and more balanced evaluation of the practical benefit of QC across different FW methods. We present below the results for the first experiment showing the absolute and relative values of the runtime in seconds and the number of iteration. The relative values in parentheses compare to the corresponding baseline. The full evaluation will be included in the revised version of the paper.\n\n|Runtime in seconds|FW|AFW|PFW|BPCG|FW-LP|AFW-LP|PFW-LP|BPCG-LP|FW-MNP|AFW-MNP|PFW-MNP|BPCG-MNP|\n|-|-|-|-|-|-|-|-|-|-|-|-|-|\n|$K$-Sparse regression $n=500$, $K=5$|2604|1673|1265|1451|**490** (0.19)|534 (0.32)|1197 (0.95)|731 (0.50)|945 (0.36)|950 (0.57)|1374 (1.09)|1130 (0.78)|\n|$K$-Sparse regression $n=500$, K=20$|148|169|222|206|**112** (0.75)|139 (0.83)|249 (1.12)|178 (0.86)|112 (0.75)|146 (0.87)|242 (1.09)|186 (0.90)|\n|$K$-Sparseregression $n=1000, K=5$|3600|3600|3600|3600|3566 (0.99)|**1433** (0.40)|3486 (0.97)|2001 (0.56)|2503 (0.70)|2683 (0.75)|3576 (0.99)|2882 (0.80)|\n|$K$-Sparseregression $n=1000, K=20$|1028|1028|979|1073|486 (0.47)|**548** (0.53)|1454 (1.49)|642 (0.60)|627 (0.61)|654 (0.64)|1467 (1.50)|736 (0.69)|\n\n|Number of iterations|FW|AFW|PFW|BPCG|FW-LP|AFW-LP|PFW-LP|BPCG-LP|FW-MNP|AFW-MNP|PFW-MNP|BPCG-MNP|\n|-|-|-|-|-|-|-|-|-|-|-|-|-|\n|$K$-Sparse regression $n=500, K=5$|10000|5225|3291|3710|**388** (0.04)|431 (0.08)|899 (0.27)|611 (0.16)|**388** (0.04)|431 (0.08)|904 (0.27)|611 (0.16)|\n|$K$-Sparse regression $n=500, K=20$|481|492|784|668|**165** (0.34)|225 (0.46)|414 (0.53)|254 (0.38)|**165** (0.34)|225 (0.46)|408 (0.52)|254 (0.38)|\n|$K$-Sparse regression $n=1000, K=5$|7431|7480|7401|6718|1123 (0.15)|747 (0.10)|1473 (0.20)|1066 (0.16)|**631** (0.08)|700 (0.09)|1159 (0.16)|988 (0.15)|\n|$K$-Sparse regression $n=1000, K=20$|2010|2032|1939|1896|**315** (0.16)|380 (0.19)|736 (0.38)|411 (0.22)|**315** (0.16)|380 (0.19)|721 (0.37)|411 (0.22)|\n\nFor each instance, quadratic corrections outperform the baseline both in the number of iterations and runtime. Moreover, QC steps reduce the number of iterations for all baselines by at least 48%. The runtime of the QC-equipped baselines is shorter in every case except for PFW-MNP.\n\n> The experimental section contains graphs which aren’t explained well. There are 8 sets of images for each figure but its not clear what’s the differences between them. Are they different experiments? Different seeds?\n\nThank you for pointing this out. We will add an explanation of the plots at the beginning of the section, helping the reader to interpret the results. \nFor each problem, the figures show the results of two experiments with different parameter settings specified in their caption. For each experiment, we have a 2 by 2 presentation of the trajectories of the primal value and the FW gap over the number of iterations and time. \nThe FW gap is an upper bound on the primal gap and, therefore, a commonly used optimality measure.\n\n> It would be beneficial to add a direct speed comparison between the algorithms. How much faster is your approach at reaching a specified gap value?\n\nWe will include a performance profile together with additional statistics in the appendix of the paper to offer an aggregated view of the performance of the algorithm.\n\n### Questions\n> - In algorithm 1, the global FW vertex uses V(P) which is undefined (I assume you mean V(X)?)\n> - In 2.1 you don’t prove your theorems, you only state them, so you should write “in the following we state two theorems”. It’s fine to have proofs in the appendix if they aren’t particularly enlightening.\n\nWe thank the referee for their careful reading and will update the paper following the suggestions."}]

Author rebuttal:

Meta-review: This paper first proposes Corrective Frank-Wolfe (CFW)---a new framework for FW variants that perform corrective steps on the active set, and proves linear convergence for smooth, sharp functions over polytopes. Then, as a detailed implementation of corrective steps in the CFW algorithm, two new Quadratic Correction (QC) steps tailored for quadratic objective functions have also been proposed. Moreover, the authors showed that the corrective steps can also be applied to existing algorithms, including split conditional gradient and conditional gradient sliding.

Reviewers appreciate the theoretical framework of CFW and the practical benefits of the quadratic corrections. Nonetheless, reviewers have also raised some concerns about the limitation of the corrective steps, the experiments compare only against BPCG (omitting other close Frank-Wolfe variants), and the clarity issue about some technical details (e.g., computational benefits of using the new corrective step).

After the rebuttal and discussion phase, most concerns have been addressed, and all reviewers give a positive score. Based on my own reading and the reviewers' evaluations, I recommend accepting this paper. The authors should also revise this paper carefully according to the reviewers' comments, especially the concerns about the experimental results and the clarity issues.
Decision: Accept (poster)