Efficient Quadratic Corrections for Frank-Wolfe Algorithms

We thank the referee for their encouragement and feedback and address several points below.

Weaknesses

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?

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

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.

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

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.

We agree that relying on a single baseline could limit the conclusions drawn from the experiments. To address this, we will add results for additional baseline algorithms, including AFW, PFW, and an active set-based variant of vanilla FW. To 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.

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

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?

Thank 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. For 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. The FW gap is an upper bound on the primal gap and, therefore, a commonly used optimality measure.

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?

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

Questions

• In algorithm 1, the global FW vertex uses V(P) which is undefined (I assume you mean V(X)?)
• 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.

We thank the referee for their careful reading and will update the paper following the suggestions.

We thank the referee for their encouragement and feedback and address several points below.

Weaknesses

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.

We 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. We will include this additional result in the corrected version of the paper and state it below:

The 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. 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. Assuming $\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. This 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. Grouping 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.

Minor issues:

We thank the referee for their careful reading and suggestions to improve our manuscript.

The first two sentences in your abstract are too long. Please break them into smaller, easy-to-digest

In the revised version, we will split the sentences as suggested.

Explicitly define the vertex set of a compact convex set in the preliminaries section.

We 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}$.

What is V(P) in Step 5 of your algorithm? I presume you meant V(X)

We thank the reviewer for their careful reading and will fix this typo in the revised version.

Questions

In Algorithm 2, can you explicitly highlight when the drop step would be executed and when the descent step would be executed?

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

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?

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

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?

The 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. By 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.
Quadratic 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.

[1] Active set complexity of the away-step Frank-Wolfe algorithm, Immanuel Bomze, Francesco Rinaldi, Damiano Zeffiro, SIAM Journal on Optimization.

[2] The pivoting framework: Frank-Wolfe algorithms with active set size control, Elias Wirth, Mathieu Besançon, Sebastian Pokutta, AISTATS 2025.

We thank the referee for their encouragement and feedback and address several points below.

Weaknesses:

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.

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

Questions:

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?

Our main result is that the novel quadratic corrections outperform existing FW methods for quadratic convex objectives, provably in certain settings we expand below. Computationally, the experiments provide empirical evidence for this performance.

We 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. We will include this additional result in the corrected version of the paper and state it below:

The 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. 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. Assuming $\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. This 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. Grouping 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.

This result will be added to Section 2 of the revised paper.

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

The theoretical result relating to the first statement is explained in detail in the previous section. We will formulate the given statement more explicitly in the revised version of the paper.

Regarding the second statement, we will also clarify the benefits of QC-MNP over the MNP-Correction step from [4]. Unlike 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.
Finally, and maybe most importantly, the MNP correction step does not specify how the affine minimization is performed. In the case of quadratic objectives, our method can be directly used for this.

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?

We will improve the explanation of how Section 3.1 connects with the rest of the paper. The algorithm we propose here is the modified step size, which improves the convergence guarantees of SCG. Theorem 5 performs Split Conditional Gradient (SCG) with standard FW steps, thus it does not rely on CFW. If the original function is quadratic, SCG performs a FW step on a quadratic subproblem changing at each iteration, we therefore propose to use QC to accelerate convergence. The 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.

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.

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

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.

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

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?

We kept the improved convergence result in the appendix due to space limitations. In the revised version, we will add a simplified version in the given section. We 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.

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?

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

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

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

References

[1] Splitting the conditional gradient algorithm, Zev Woodstock and Sebastian Pokutta. SIAM Journal on Optimization.

[2] Active set complexity of the away-step Frank-Wolfe algorithm, Immanuel Bomze, Francesco Rinaldi, Damiano Zeffiro, SIAM Journal on Optimization.

[3] The pivoting framework: Frank-Wolfe algorithms with active set size control, Elias Wirth, Mathieu Besançon, Sebastian Pokutta, AISTATS 2025.

[4] On the Global Linear Convergence of Frank-Wolfe Optimization Variants, Simon Lacoste-Julien, Martin Jaggi, 2015

I wish to thank the authors for their responses. I agree with most of the points raised by the other reviewers. I strongly encourage the authors to carefully address the suggestions made by the reviewers, as incorporating these points will significantly improve the clarity of the paper. Given the authors’ promised revisions, my score remains unchanged.

We thank the referee for their encouragement and feedback and address several points below.

Weaknesses

Comment on Limitation to Quadratics:

The 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. In particular, we have observed significant potential for QC to improve the convergence of SOCGS when optimizing general convex functions. Beyond SCG and SOCGS, QC steps are also applicable for submodular function minimization [1] and Frank-Wolfe variants of the Difference Convex algorithm [2,3]. Finally, we note that requiring access to a linear minimization oracle (LMO) primarily restricts the feasible region, rather than the objective function class.

Comment on Limited Experimental Comparison:

We will add results for additional baseline algorithms, including AFW, PFW, and an active set-based variant of vanilla FW. To 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.

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

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

Comment on Success Rates of Quadratic Corrections:

To 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. We will provide a table with the per-experiment success rates in the appendix of the paper and present an excerpt from this here:

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

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

Finally, we would like to point to an additional theoretical result that relates to this topic. One 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.

We will include this result in the revised version and expand on a strong theoretical consequence of this: Assuming $\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. In consequence, CFW with QC steps converges in finitely many iterations given the additional assumptions, a strong result that otherwise requires fully-corrective FW.

Minor comments

We 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:

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?

A 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. Furthermore, 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.

Questions

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?

No, we do not require $\mathcal{X}$ to be a polyhedral constraint set. We 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}$.

Algorithm 1, Line 5: What is P? Should this be X?

Yes, this is a typo and will be corrected in the revised version.

Algorithm 1, Line 10: Do you have perform this minimization exactly?

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

Algorithm 2: Where do s, v get used? Aren't these equivalent to u, w in the descent step?

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

Algorithm 3: How often can we expect Eq. (7) to return an interior point (see also detailed discussion)?

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

References

[1] Provable Submodular Minimization using Wolfe’s Algorithm, D. Chakrabarty, P. Jain, P. Kothari, 2014

[2] Revisiting Frank-Wolfe for Structured Nonconvex Optimization, H. Maskan, Y. Hou, S. Sra, A. Yurtsever, 2025

[3] Scalable DC Optimization via Adaptive Frank-Wolfe Algorithms, S. Pokutta, 2025

[4] Active set complexity of the away-step Frank-Wolfe algorithm, I. Bomze, F. Rinaldi, D. Zeffiro, SIAM Journal on Optimization.

[5] The pivoting framework: Frank-Wolfe algorithms with active set size control, E. Wirth, M. Besançon, S. Pokutta, AISTATS 2025.

[6] Linearly Convergent Frank-Wolfe with Backtracking Line-Search, F. Pedregosa, G. Negiar, A. Askari, M. Jaggi, 2022

[7] The Frank-Wolfe Algorithm: A Short Introduction, S. Pokutta, 2024