# Efficient Quadratic Corrections for Frank-Wolfe Algorithms

Jannis Halbey, Seta Rakotomandimby, Mathieu Besançon, Sébastien

Designolle, Sebastian Pokutta

► To cite this version:

Jannis Halbey, Seta Rakotomandimby, Mathieu Besançon, Sébastien Designolle, Sebastian Pokutta. Efficient Quadratic Corrections for Frank-Wolfe Algorithms. NeurIPS, Dec 2025, San Diego, United States. hal-05426705

HAL Id: hal-05426705

https://hal.science/hal-05426705v1

Submitted on 19 Dec 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Efficient Quadratic Corrections for Frank-Wolfe Algorithms

**Jannis Halbey**

Zuse Institute Berlin & TU Berlin
Berlin, Germany

halbey@zib.de

**Seta Rakotomandimby**

École nationale des ponts et chaussées, IP Paris
Champs-sur-Marne, France

seta.rakotomandimby@enpc.fr

**Mathieu Besançon**

Université Grenoble Alpes, Inria, LIG, CNRS
Grenoble, France

mathieu.besancon@inria.fr

**Sébastien Designolle**

Zuse Institute Berlin
Berlin, Germany

designolle@zib.de

**Sebastian Pokutta**

Zuse Institute Berlin & TU Berlin
Berlin, Germany

pokutta@zib.de

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

## 1 Introduction

In this paper, we consider convex constrained optimization problems of the form

$$ \min_{x \in \mathcal{X}} f(x), $$

where $\mathcal{X}$ is a compact, convex set and $f$ is a 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, 1956]. One major advantage of these methods is that they access $\mathcal{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 $O(1/t)$ convergence rate in general and linear convergence rates in specific settings.
Over the years, several FW variants have been designed to exploit the so-called *active set*, 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 a rate of $\Omega(1/t)$. Additionally, they have been shown to produce sparse solutions (constructed as convex combinations of a few iterates), which motivated strong interest in FW methods for sparse optimization and machine learning applications. The Fully-Corrective Frank-Wolfe (FCFW) algorithm, presented in some form in Wolfe [1976], Holloway [1974] and named in Lacoste-Julien and Jaggi [2015], drives the 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, FCFW is also closely related to column-generation and cutting-plane 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 a new framework, *Corrective Frank-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], we 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 an increasing penalty on the squared distance to the other iterate. Besides the computational benefits of the quadratic corrections, we also prove a faster convergence rate for SCG.

Additionally, we consider *Second-Order Conditional Gradient Sliding (SOCGS)* [Carderera and Pokutta, 2020] which follows an inexact Newton approach, adapting the Conditional Gradient Sliding (CGS) method of 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-Wolfe methods is vast, and we only cover a few related methods here; for a more comprehensive overview, we refer to Braun et al. [2022]. The corrective framework is inspired by ideas from Blended Conditional Gradients (BCG) [Braun et al., 2019] and Blended Pairwise Conditional Gradients (BPCG) [Tsuji et al., 2022]. Furthermore, Lacoste-Julien 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 MNP-Correction. Finally, we follow the idea of Braun et al. [2017] to introduce a lazified variant of the corrective step framework.

## Contributions

Our contributions can be summarized as follows:

**Corrective Frank-Wolfe** We introduce Corrective Frank-Wolfe (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 a 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 in finite time under strict complementarity.

**Quadratic corrections** We introduce two new quadratic correction steps tailored for quadratic objective functions. The first one, QC-LP, is a 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 a 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 or linear system, respectively. Additionally, we propose a hybrid method that combines these corrections with the local pairwise steps of BPCG [Tsuji et al., 2022], yielding a 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, we also present new theoretical results. First, we prove that SCG converges for a smaller step size, yielding a faster rate of $O(1/\sqrt{t})$ compared to the original rate of $O(\log(t)/\sqrt{t})$ provided in Woodstock and Pokutta [2025]. This closes the gap to the complexity bound of $O(1/\sqrt{t})$ for the underlying non-smooth problem [Yudin, 1983]. Second, we show that the Projected Variable-Metric method in SOCGS converges globally for generalized self-concordant functions.

**Experiments** We demonstrate the excellent computational benefits of the new 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 to solve the quadratic subproblem efficiently.

## Preliminaries

Let $\mathcal{X}$ be a compact convex set with diameter $D \stackrel{\text{def}}{=} \max_{\mathbf{x},\mathbf{y} \in \mathcal{X}} \|\mathbf{x} - \mathbf{y}\|$, $\mathcal{X}^*$ be the set of minimizers of $f$ over $\mathcal{X}$, and $V(\mathcal{X})$ be the set of extreme points of $\mathcal{X}$. If $\mathcal{X}$ is a polytope, we denote its pyramidal width by $\delta$ [Lacoste-Julien and Jaggi, 2015] and the minimal face containing $\mathcal{X}^*$ by $\mathcal{F}^*$. Strict complementarity holds if there exists $\rho > 0$ such that for all $\mathbf{x}^* \in \mathcal{X}^*$ and $\mathbf{v} \in V(\mathcal{X})$, we have

$$ \langle \nabla f(\mathbf{x}^*), \mathbf{v} - \mathbf{x}^* \rangle \begin{cases} \ge \rho & \text{if } \mathbf{v} \in V(\mathcal{X}) \setminus \mathcal{F}^*; \\ = 0 & \text{if } \mathbf{v} \in V(\mathcal{X}) \cap \mathcal{F}^*. \end{cases} $$

We denote the active set, i.e., the set of vertices used by an FW algorithm, by $S \subset \mathcal{X}$. For a given weight vector $\lambda$, we denote the weight of an atom $\mathbf{v} \in S$ by $\lambda_{\mathbf{v}}$. For a given convex combination $\mathbf{x} = \sum_{\mathbf{v} \in S} \lambda_{\mathbf{v}} \mathbf{v}$, we denote the corresponding weight vector by $\lambda(\mathbf{x}) \stackrel{\text{def}}{=} \lambda$. Furthermore, we denote the convex hull of $S$ by $\text{conv}(S)$, the affine hull of $S$ by $\text{aff}(S)$, and the boundary of a set $M$ by $\partial M$.

Let $f: \mathcal{X} \to \mathbb{R}$ be a differentiable, convex function. The function $f$ is $L$-smooth if

$$ f(\mathbf{y}) - f(\mathbf{x}) \le \langle \nabla f(\mathbf{x}), \mathbf{y} - \mathbf{x} \rangle + \frac{L}{2} \|\mathbf{y} - \mathbf{x}\|^2 \quad \forall \mathbf{x}, \mathbf{y} \in \mathcal{X}. $$

The function $f$ is $\mu$-strongly convex if

$$ f(\mathbf{y}) - f(\mathbf{x}) \ge \langle \nabla f(\mathbf{x}), \mathbf{y} - \mathbf{x} \rangle + \frac{\mu}{2} \|\mathbf{y} - \mathbf{x}\|^2 \quad \forall \mathbf{x}, \mathbf{y} \in \mathcal{X}. $$

In the following, we will use the notion of sharpness, generalizing strong convexity. Let $f^*$ denote the optimal value of $f$ over $\mathcal{X}$. A proper convex function $f$ is $(c, \theta)$-sharp with $c > 0$ and $\theta \in (0, 1]$ if for all $\mathbf{x} \in \mathcal{X}$,

$$ c(f(\mathbf{x}) - f^*)^\theta \ge \min_{\mathbf{y} \in \mathcal{X}^*} \|\mathbf{x} - \mathbf{y}\|. $$

In particular, a $\mu$-strongly convex function is $(\frac{\sqrt{2}}{\sqrt{\mu}}, \frac{1}{2})$-sharp over any compact set.
## 2 Corrective Frank-Wolfe

We now present the Corrective Frank-Wolfe (CFW) algorithm in Algorithm 1, its convergence analysis, and specialized corrections for quadratic objectives.

CFW provides a 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 $\langle \nabla f(\mathbf{x}_t), \mathbf{a}_t - \mathbf{s}_t \rangle$ with the global Frank-Wolfe gap $\langle \nabla f(\mathbf{x}_t), \mathbf{x}_t - \mathbf{v}_t \rangle$ to decide whether to perform a corrective step or an FW step. Algorithm 2 is a template for corrective steps that ensures convergence of CFW.

<caption>**Algorithm 1 Corrective Frank-Wolfe (CFW)**</caption>

**Require:** convex smooth function $f$, starting point $\mathbf{x}_0 \in V(\mathcal{X})$.
1: $S_0 \leftarrow \{\mathbf{x}_0\}$
2: **for** $t = 0$ to $T-1$ **do**
3: &nbsp;&nbsp;&nbsp;&nbsp; $\mathbf{a}_t \leftarrow \operatorname*{argmax}_{\mathbf{v} \in S_t} \langle \nabla f(\mathbf{x}_t), \mathbf{v} \rangle$
4: &nbsp;&nbsp;&nbsp;&nbsp; $\mathbf{s}_t \leftarrow \operatorname*{argmin}_{\mathbf{v} \in S_t} \langle \nabla f(\mathbf{x}_t), \mathbf{v} \rangle$
5: &nbsp;&nbsp;&nbsp;&nbsp; $\mathbf{v}_t \leftarrow \operatorname*{argmin}_{\mathbf{v} \in V(\mathcal{X})} \langle \nabla f(\mathbf{x}_t), \mathbf{v} \rangle$
6: &nbsp;&nbsp;&nbsp;&nbsp; **if** $\langle \nabla f(\mathbf{x}_t), \mathbf{a}_t - \mathbf{s}_t \rangle \ge \langle \nabla f(\mathbf{x}_t), \mathbf{x}_t - \mathbf{v}_t \rangle$ **then**
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\mathbf{x}_{t+1}, S_{t+1} \leftarrow \mathrm{CS}(S_t, \mathbf{x}_t, \mathbf{a}_t, \mathbf{s}_t)$
8: &nbsp;&nbsp;&nbsp;&nbsp; **else**
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\gamma_t \leftarrow \operatorname*{argmin}_{\gamma \in [0,1]} f(\mathbf{x}_t - \gamma(\mathbf{x}_t - \mathbf{v}_t))$
10: &nbsp;&nbsp;&nbsp;&nbsp; $\mathbf{x}_{t+1} \leftarrow \mathbf{x}_t - \gamma_t(\mathbf{x}_t - \mathbf{v}_t)$
11: &nbsp;&nbsp;&nbsp;&nbsp; $S_{t+1} \leftarrow S_t \cup \{\mathbf{v}_t\}$
12: &nbsp;&nbsp;&nbsp;&nbsp; **end if**
13: &nbsp;&nbsp;&nbsp;&nbsp; **end for**

<caption>**Algorithm 2 Corrective Step CS(S, x, a, s)**</caption>

**Require:** $S \subset \mathcal{X}, \mathbf{x}, \mathbf{a}, s \in \mathcal{X}$
**Return:** $S' \subseteq S, \mathbf{x}' \in \mathrm{conv}(S')$ satisfying
(i) $f(\mathbf{x}') \le f(\mathbf{x})$ and $S' \subsetneq S$ or
(ii) $f(\mathbf{x}) - f(\mathbf{x}') \ge \frac{\langle \nabla f(\mathbf{x}), \mathbf{a} - \mathbf{s} \rangle^2}{2LD^2}$
$\triangleright$ drop step
$\triangleright$ descent step

A corrective step is either a descent step that yields sufficient primal progress or a drop step that decreases the size of the active set without increasing the objective value. In contrast to approximate FCFW, we omit any conditions on the away gap and compare the primal progress only to the local pairwise gap rather than the global FW step. The update steps in BCG, BPCG, and FCFW meet the criteria of a corrective step. The proof is given in Appendix A.

**Proposition 1.** *Algorithm 3, Algorithm 4, and the simplex gradient descent step from Braun et al. [2019] satisfy the criteria of Algorithm 2.*

**Algorithm 3 Local Pairwise Step**
LPS(S, x, a, s)

**Require:** $S \subset \mathcal{X}, \mathbf{x}, \mathbf{a}, s \in \mathcal{X}$
**Return:** $S', \mathbf{x}'$
1: $\gamma^* \leftarrow \operatorname*{argmin}_{\gamma \in [0, \lambda_{\mathbf{a}}(\mathbf{x})]} f(\mathbf{x} + \gamma(\mathbf{s} - \mathbf{a}))$
2: $\mathbf{x}' \leftarrow \mathbf{x} + \gamma^*(\mathbf{s} - \mathbf{a})$
3: $S' \leftarrow \begin{cases} S \setminus \{\mathbf{a}\} & \text{if } \gamma^* = \lambda_{\mathbf{a}}(\mathbf{x}), \\ S & \text{otherwise.} \end{cases}$

**Algorithm 4 Fully-Corrective Step FCS(S)**

**Require:** $S \subset \mathcal{X}$
**Return:** $S', \mathbf{x}'$
1: $\mathbf{x}' \leftarrow \operatorname*{argmin}_{\mathbf{x} \in \mathrm{conv}(S)} f(\mathbf{x})$
2: $S' \leftarrow \{\mathbf{v} \in S \mid \lambda_{\mathbf{v}}(\mathbf{x}') > 0\}$

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 1 also applies to AFW if the gap comparison in Algorithm 1 uses the away gap instead of the local pairwise gap. We choose the pairwise gap since it can be 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 a 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 $\mathcal{X}$ be a convex feasible set with diameter $D$ and $f$ be a convex, L-smooth function over $\mathcal{X}$. Consider the sequence $\{\mathbf{x}_t\}_{t=0}^T \subset \mathcal{X}$ obtained by Algorithm 1. Then we have

$$f(\mathbf{x}_T) - f^* \le \frac{4LD^2}{T}. \qquad (1)$$

If additionally $f$ is $(c, \frac{1}{2})$-sharp and $\mathcal{X}$ is a polytope with pyramidal width $\delta$, then

$$f(\mathbf{x}_T) - f^* \le (f(\mathbf{x}_0) - f^*) \exp(-c_f \mathcal{X} T), \qquad (2)$$

where $c_f, \mathcal{X} = \min\{\frac{1}{4}, \frac{\delta^2}{16Lc^2D^2}\}$. If $f$ is $(c, \theta)$-sharp with $\theta < \frac{1}{2}$, then

$$f(\mathbf{x}_T) - f^* = \mathcal{O}\left(\frac{1}{T^{\frac{1}{1-2\theta}}}\right). \qquad (3)$$

The proof is given in Appendix 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 $\Phi_t$, which is updated if the gap becomes smaller than $\Phi_t/J$ for some parameter $J \ge 1$. The convergence results are stated in Theorem 3, and we present its proof together with the algorithm in Appendix B.

**Theorem 3.** Let $\mathcal{X}$ be a convex feasible set with diameter $D$ and $f$ be a convex, L-smooth function over $\mathcal{X}$. Consider the sequence $\{\mathbf{x}_t\}_{t=0}^T \subset \mathcal{X}$ obtained by the Algorithm 7. Then we have

$$f(\mathbf{x}_T) - f^* = \mathcal{O}\left(\frac{1}{T}\right). \qquad (4)$$

If additionally $f$ is $(c, \frac{1}{2})$-sharp and $\mathcal{X}$ is a polytope with pyramidal width $\delta$, then

$$f(\mathbf{x}_T) - f^* = \mathcal{O}(\exp(-aT)), \qquad (5)$$

for some constant $a > 0$ independent of $T$. If $f$ is $(c, \theta)$-sharp with $\theta < \frac{1}{2}$, then

$$f(\mathbf{x}_T) - f^* = \mathcal{O}\left(\frac{1}{T^{\frac{1}{1-2\theta}}}\right). \qquad (6)$$

Finally, we state a theorem that ensures identification of the optimal face by CFW in finite time under strict complementarity. Identifying the optimal face $\mathcal{F}^*$ of $\mathcal{X}$ is crucial, as it simplifies the optimization problem to one over $\mathcal{F}^*$ instead of $\mathcal{X}$. An early result by Guélat and Marcotte [1986] proves this property for AFW under the additional assumption of strong convexity of $f$. Bomze et al. [2020] 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 is given in Appendix A.

**Theorem 4.** Let $\mathcal{X}$ be a polytope and let $f$ be a convex, L-smooth function over $\mathcal{X}$. Assume that strict complementarity holds. Consider the sequence $\{\mathbf{x}_t\}_{t=0}^T$ generated by Algorithm 1. Then there exists an iteration $\bar{T}$ such that

$$\mathbf{x}_t \in \mathcal{F}^* \quad \text{for all } t \ge \bar{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 a convex quadratic function, i.e., can be written as $f(x) = \frac{1}{2}\langle x, Ax\rangle + \langle b, x\rangle + c$, where $A \in \mathbb{R}^{n \times n}$ is a symmetric positive semidefinite matrix. This can be extended to general finite-dimensional Hilbert spaces, in which case $A$ is a symmetric linear operator.

The quadratic corrections are inspired by FCFW, which solves the minimization problem $\min_{x \in \text{conv}(S)} f(x)$ in each iteration. Unfortunately, minimizing quadratic functions over polytopes such as $\text{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_{x \in \text{aff}(S)} f(x) \left( \le \min_{x \in \text{conv}(S)} f(x) \right), \qquad (7) $$

and then reconstruct a point in $\text{conv}(S)$.

**Solving the minimization problem over the affine hull** Let $x_{\text{aff}}^* \in \text{argmin}_{x \in \text{aff}(S)} f(x)$. First-order optimality conditions imply that $\langle \nabla f(x_{\text{aff}}^*), d \rangle = 0$ for any feasible direction $d$. The feasible directions in $\text{aff}(S)$ are spanned by $d = v - w$ for $v, w \in S$. Thus, the first-order optimality conditions are equivalent to the system of equalities,

$$ \langle \nabla f(x_{\text{aff}}^*), v - w \rangle = 0 \quad \forall v, w \in S, $$

which is equivalent to the gradient at $x_{\text{aff}}^*$ being orthogonal to the affine space. Writing $x_{\text{aff}}^*$ as an affine combination of the atoms in $S$ yields $\nabla f(x_{\text{aff}}^*) = Ax_{\text{aff}}^* + b = A \sum_{v \in S} \lambda_v(x_{\text{aff}}^*)v + b = AV\lambda(x_{\text{aff}}^*) + b$. By fixing an anchor $w \in S$, we obtain a linear system,

$$ \langle AV\lambda + b, v - w \rangle = 0 \quad \forall v \in S \setminus \{w\}, \quad \sum_{v \in S} \lambda_v = 1. \qquad (8) $$

*Remark 2.* Applying first-order optimality conditions to $x_{\text{conv}}^* \in \text{argmin}_{x \in \text{conv}(S)} f(x)$ with the barycentric coordinates yields $\langle AV\lambda + b, v - V\lambda \rangle \ge 0$ for all $v \in S$, which is a quadratic inequality system in $\lambda$ that can be as hard to solve as the original problem. However, if $x_{\text{conv}}^*$ lies in the relative interior of $\text{conv}(S)$, these quadratic inequalities simplify to linear equalities as in (8).

The linear system (8) is equivalent to the KKT conditions of (7) 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 Appendix C.2.

**Proposition 5.** Equation (8) is feasible if and only if $b \perp \text{span}(S) \cap \text{ker}(A)$. In particular, it is feasible if $A$ is positive definite.

**Quadratic correction through Linear Programs** To ensure that the new weights $\lambda$ are non-negative, we consider two approaches. The QC-LP approach enforces this directly, yielding

$$ \langle AV\lambda + b, v - w \rangle = 0 \quad \forall v \in S \setminus \{w\}, \quad \sum_{v \in S} \lambda_v = 1, \quad \lambda \ge 0. \qquad (9) $$

The LP is only feasible if the affine minimizer exists and lies inside $\text{conv}(S)$. Otherwise, we perform a local pairwise step as a computationally inexpensive fallback option. The method is presented in Algorithm 5.
**Algorithm 5 Quadratic Correction LP**

**Require:** $S \subset \mathcal{X}$, $x, a, s \in \mathcal{X}$

**Return:** $S', x'$

$\lambda' \leftarrow \text{Solve (9)}$

if feasible then

$$x' \leftarrow \sum_{v \in S} \lambda_v' v \\ S' \leftarrow S$$

else

$$S', x' \leftarrow \text{LPS}(S, x, a, s)$$

end if

▷ FCFW step

▷ Fallback step

**Algorithm 6 Quadratic Correction MNP**

**Require:** $S \subset \mathcal{X}$, $x, a, s \in \mathcal{X}$

**Return:** $S', x'$

$\tilde{\lambda} \leftarrow \text{Solve (8)}$

if feasible then

if $\tilde{\lambda} \ge 0$ then

$$x' \leftarrow \sum_{v \in S} \tilde{\lambda}_v' v \\ S' \leftarrow S$$

▷ FCFW step

else

$$\tau \leftarrow \min \left\{ \frac{\lambda_v(x)}{\lambda_v(x) - \tilde{\lambda}_v} \middle| \tilde{\lambda}_v < \lambda_v(x) \right\} \\ x' \leftarrow \sum_{v \in S} (\tau \tilde{\lambda}_v + (1 - \tau) \lambda_v(x)) v \\ S' \leftarrow \{ v \in S \mid \lambda_v(x') > 0 \}$$

▷ MNP step

end if

else

$$S', x' \leftarrow \text{LPS}(S, x, a, s)$$

end if

▷ Fallback step

**Quadratic correction through the Minimum-Norm-Point algorithm** The second approach, QC-MNP, is inspired by the Minimum-Norm-Point algorithm in 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 MNP-Correction step from Lacoste-Julien and Jaggi [2015], QC-MNP will stop after a single truncation, alleviating the need to solve multiple linear systems in a 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 a more efficient variant for the case of multiple affine minimizers in Appendix C.1.

Both QC-LP and QC-MNP are corrective steps in 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 2.

**Proposition 7.** Let $\mathcal{X}$ be a polytope and $\mathcal{F}^*$ be the minimal face of $\mathcal{X}$ containing the optimal points $\mathcal{X}^*$. If $S \subset \mathcal{F}^*$, then $\text{argmin}_{x \in \text{aff}(S)} f(x) \neq \emptyset$. If additionally there exists $x^* \in \mathcal{X}^*$ with $x^* \in \text{conv}(S)$, then $x^* \in \text{argmin}_{x \in \text{aff}(S)} f(x)$.

We would like to emphasize that the sizes of the linear system and the LP do not depend on the ambient dimension but only on the size of the active set. Furthermore, similarly to Besançon et al. [2025], we can cache the scalar products $\langle v, Aw \rangle$ and $\langle b, v \rangle$ for $v, w \in S$, accelerating the setup of the linear system and LP while only marginally increasing storage.

**Remark 3.** The linear system in (8) is usually not symmetric, which can be problematic for solvers like Conjugate Gradient (CG). However, subtracting $W^\top Aw 1^\top \lambda = W^\top Aw$ from (8) yields the equivalent symmetric system

$$W^\top Aw \mu = -W^\top (Aw + b), \quad (10)$$

where the matrix $W$ has columns $v - w$ for $v \in S \setminus \{w\}$. The new weights are then given by

$$\lambda_v = \begin{cases} 1 - 1^\top \mu & \text{if } v = w, \\ \mu_v & \text{otherwise.} \end{cases}$$

Finally, we come to the main result of this section. As seen in Theorem 4, CFW identifies the optimal face of a 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 set 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 Appendix C.2.
**Theorem 8.** Let $\mathcal{X}$ be a polytope and let $f$ be a convex, $L$-smooth function over $\mathcal{X}$. Assume that strict complementarity holds. Consider the sequence $\{\mathbf{x}_t\}_{t=0}^T$ generated by Algorithm 1 with Algorithm 4, Algorithm 5, or Algorithm 8. Then, there exists an iteration $\tilde{T}$ such that $\mathbf{x}_{\tilde{T}} \in \mathcal{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-Wolfe methods is their reliance on a Linear Minimization Oracle. This becomes particularly problematic for optimization over intersections of convex sets, where no efficient procedure for linear minimization is generally available. Braun et al. [2023] introduced the Alternating Linear Minimization (ALM) method for finding a point in the intersection of two convex sets $P$ and $Q$, drawing a parallel with von Neumann's alternating projection. ALM alternates between Frank-Wolfe steps, solving $\min_{\mathbf{x} \in P, \mathbf{y} \in Q} \|\mathbf{x} - \mathbf{y}\|^2$, and therefore avoids projections in an FW-like manner. Woodstock and Pokutta [2025] extended their approach to optimization problems over intersections by penalizing the distance,

$$ \min_{\mathbf{x} \in P, \mathbf{y} \in Q} F_{\lambda}(\mathbf{x}, \mathbf{y}) = f\left(\frac{\mathbf{x} + \mathbf{y}}{2}\right) + \frac{\lambda}{2} \|\mathbf{x} - \mathbf{y}\|^2. $$

Their method, Split Conditional Gradient (SCG), performs parallel FW steps on 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.

Independently of CFW, we prove a tighter convergence rate for the original SCG. Woodstock and Pokutta [2025] prove that the primal gap of $F_{\lambda}$ converges at a rate of $O(\log t/\sqrt{t})$. By analyzing a different auxiliary objective, we show that replacing the step size $\gamma_t = \frac{2}{\sqrt{t+2}}$ by the smaller step size $\gamma_t = \frac{2}{\sqrt{t+2}\log(t+2)}$ improves the convergence rate of SCG to $O(1/\sqrt{t})$. The proof for the more general case of finite intersections over Hilbert spaces is provided in Appendix D.

**Theorem 9.** Let $f: \mathbb{R}^n \to \mathbb{R}$ be convex and $L$-smooth, $P, Q \subset \mathbb{R}^n$ be non-empty compact and convex sets with diameters $D_P$ and $D_Q$ such that $P \cap Q \neq \emptyset$. For $t \ge 0$, set $\lambda_t = \ln(t+2)$, $(\mathbf{x}_t^*, \mathbf{y}_t^*) \in \text{argmin}_{(\mathbf{x}, \mathbf{y}) \in P \times Q} F_{\lambda_t}(\mathbf{x}, \mathbf{y})$. For $\gamma_t = \frac{2}{\sqrt{t+2}\ln(t+2)}$, the iterates of Algorithm 9 satisfy

$$ 0 \le F_{\lambda_t}(\mathbf{x}_t, \mathbf{y}_t) - F_{\lambda_t}(\mathbf{x}_t^*, \mathbf{y}_t^*) \le \frac{(D_P + D_Q)^2(L+1) + \sqrt{2}c_f}{\sqrt{t+2}} \quad (11) $$

for all $t \ge 0$, where $c_f = \max_{(\mathbf{x}, \mathbf{y}), (\tilde{\mathbf{x}}, \tilde{\mathbf{y}}) \in P \times Q} f(\frac{\mathbf{x}+\mathbf{y}}{2}) - f(\frac{\tilde{\mathbf{x}}+\tilde{\mathbf{y}}}{2}) < \infty$.

## 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, 2020]. These methods reduce the number of first-order oracle calls by iteratively solving quadratic problems with a 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/\sqrt{\epsilon})$ instead of $O(1/\epsilon)$ gradient calls to achieve $\epsilon$-optimality, matching existing lower bounds. SOCGS achieves a linear rate for strongly convex functions over polytopes, replacing the Euclidean projection subproblem in CGS with a 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, a detailed description is given in Appendix E.

**Theorem 10.** Let $\mathcal{X}$ be a compact convex set of diameter $D$ and $f$ be a $(M, \nu)$-generalized self-concordant function with $\nu \ge 2$ such that $f$ is strongly convex on $\text{dom}(f) \cap \mathcal{X}$ if $\nu = 3$. Given a
starting point $\mathbf{x}_0 \in \mathcal{X} \cap \text{dom}(f)$, the Algorithm 11 with a step size $\gamma_k$ guarantees for all $k \ge 0$:

$$f(\mathbf{x}_{k+1}) - f(\mathbf{x}^*) \le (1 - c(\gamma_k))(f(\mathbf{x}_k) - f(\mathbf{x}^*))$$

where $c(\gamma_k) < 1$ is a constant depending on the step size $\gamma_k$.

# 4 Experiments

In this section, we 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 a 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 Appendix F. All runs were executed on a cluster with Intel Xeon Gold 6338 CPUs at 2 GHz and 12 GB RAM, with time and iteration limits chosen according to problem size.

## 4.1 Regression over the K-Sparse polytope

In the first experiment, we consider a sparse regression problem over the K-Sparse polytope, $P_K(\tau) = B_1(\tau K) \cap B_\infty(\tau)$. The problem is to minimize $f(\mathbf{x}) = \sum_{i=1}^m (\langle \mathbf{x}, \mathbf{a}_i \rangle - y_i)^2 = \|\mathbf{A}\mathbf{x} - \mathbf{y}\|_2^2$ over $P_K(\tau)$ given data points $\{(\mathbf{a}_i, y_i)\}_{i=1}^m \subset \mathbb{R}^n \times \mathbb{R}$. We generated synthetic normally distributed $\mathbf{a}_i$ and $y_i$ with $n = 500$, $m = 10000$ and $K \in \{5, 20\}$, and used a fixed interval length of $N = 10$ for the quadratic correction steps. As shown in Figure 1, all methods except FW converge linearly, with QC-LP and QC-MNP providing a 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 baselines.

<figure><img src="image_2.png" /><figcaption>Figure 1: Sparse regression over the K-Sparse polytope for $K \in \{5, 20\}$</figcaption></figure>

## 4.2 Entanglement detection

Certifying the entanglement of quantum states is a fundamental challenge in quantum information theory. Shang and Gühne [2018] use Gilbert’s algorithm [Gilbert, 1966], a simplified FW method, together with a heuristic LMO for computing the minimal distance of a given state to 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 a family of $3 \times 3$ entangled states proposed in Horodecki [1997] 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 as results for noisy states are given in Appendix F. The results for $a \in \{0.25, 0.5\}$ are shown in Figure 2. We use a logarithmic scale on the horizontal axis to visualize the differences between the methods more clearly. QC-MNP shows a drastic initial acceleration, solving the problem to optimality in a 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 a similar trajectory to BPCG. FW and PFW perform worse than the other baselines in terms of time due to the high number of LMO calls.
<figure><img src="image_3.png" /><figcaption>Figure 2: Entanglement detection for $a \in \{0.25, 0.5\}$</figcaption></figure>

## 4.3 Projection onto intersections with Split Conditional Gradient

In this experiment, we use SCG to project onto the intersection of the Birkhoff polytope $B(n)$, the set of all $n \times n$ doubly stochastic matrices, and a shifted $\ell_2$ ball. For the shift, we sample a point on a face of $B(n)$ and move the center of the ball from there in the direction of the normal vector of the face. The shift is parametrized by $c \in [0, 1]$ and $q \in [0, 1]$; a complete description is given in the appendix. The objective is given by $f(\mathbf{X}) = \frac{1}{n^2} \|\mathbf{X} - \mathbf{X}_0\|_F^2$ where $\mathbf{X}_0 \in \mathbb{R}^{n \times n}$ is sampled with uniformly distributed entries. The results for $n \in \{300, 500\}$ using $c = 0.9$, $q = 0.1$ and $N = 1$ are given in Figure 3. 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-LP outperform BPCG for $n = 500$ and achieve similar results for $n = 300$. The FW variant from [Woodstock and Pokutta, 2025] performs the worst on both instances.

<figure><img src="image_4.png" /><figcaption>Figure 3: Projection onto the intersection of the Birkhoff polytope and a shifted $\ell_2$ ball for dimension $n \in \{300, 500\}$</figcaption></figure>

## 4.4 Projecting with quadratic corrections in Second-Order Conditional Gradient Sliding

In the last experiment, we solve a logistic regression problem over the $\ell_1$ ball with SOCGS. The objective is to minimize $f(\mathbf{x}) = \frac{1}{m} \sum_{i=1}^m \ln(1 + \exp(-y_i \langle \mathbf{x}, \mathbf{z}_i \rangle)) + \frac{1}{2m} \|\mathbf{x}\|^2$. The labels $y_i \in \{-1, 1\}$ and feature vectors $\mathbf{z}_i \in \mathbb{R}^n$ are taken from the gisette training dataset [Guyon et al., 2007], with $n = 5000$ and $m = 6000$. Recall that each iteration of SOCGS corresponds to 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 \in \{50, 200\}$ inner iterations are depicted in 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 in primal values and the FW gap. For
longer runs of the inner problem, i.e., larger *k*, 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.

<figure><img src="image_5.png" /><figcaption>Figure 4: Logistic regression over the $l_1$-ball for maximum number of inner steps $k \in \{50, 200\}$</figcaption></figure>

# 5 Conclusion

In this paper, we present a 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-art 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.
Acknowledgments and Disclosure of Funding

Research reported in this paper was partially supported by the Deutsche Forschungsgemeinschaft (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-P3IA-0003).

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–2049, 2015. doi: 10.1137/15M1008397. URL https://doi.org/10.1137/15M1008397.

Aharon Ben-Tal and Arkadi Nemirovski. Lecture notes Optimization III Convex analysis nonlinear programming theory nonlinear programming algorithms. Lecture Notes, Spring 2023. https://www2.isye.gatech.edu/~nemirovs/PTIIILN2023Spring.pdf.

Mathieu Besançon, Alejandro Carderera, and Sebastian Pokutta. FrankWolfe.jl: a high-performance and flexible toolbox for Frank-Wolfe algorithms and conditional gradients. *INFORMS Journal on Computing*, 34(5):2611–2620, 2022.

Mathieu Besançon, Sébastien Designolle, Jannis Halbey, Deborah Hendrych, Dominik Kuzinowicz, Sebastian Pokutta, Hannah Troppens, Daniel Viladrich Herrmannsdoerfer, and Elias Wirth. Improved algorithms and novel applications of the FrankWolfe.jl library. *ACM Transactions on Mathematical Software*, 2025.

Immanuel M Bomze, Francesco Rinaldi, and Damiano Zeffiro. Active set complexity of the away-step Frank-Wolfe algorithm. *SIAM Journal on Optimization*, 30(3):2470–2500, 2020.

G. Braun, S. Pokutta, and D. Zink. Lazifying conditional gradient algorithms. In *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. Alternating linear minimization: Revisiting von neumann's alternating projections, 2023. URL https://arxiv.org/abs/2212.02933.

Caleb Bugg, Chen Chen, and Anil Aswani. Nonnegative tensor completion via integer optimization, 2022.

A. Carderera, M. Besançon, and S. Pokutta. Scalable Frank-Wolfe on generalized self-concordant functions via simple steps. *SIAM Journal on 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*, 49(4):565–571, 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 5153–5165. PMLR, 17–23 Jul 2022. URL https://proceedings.mlr.press/v162/ding22a.html.

Marguerite Frank and Philip Wolfe. An algorithm for quadratic programming. *Naval research logistics quarterly*, 3(1-2):95–110, 1956.
Dan Garber, Atara Kaplan, and Shoham Sabach. Improved complexities of conditional gradient-type methods with applications to robust matrix recovery problems. *Mathematical Programming*, 186, 11 2019. doi: 10.1007/s10107-019-01452-6.

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.1137/0304007.

Jacques Guélat and Patrice Marcotte. Some comments on Wolfe's 'away step'. *Mathematical Programming*, 35(1):110–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):1438–1444, 2007.

Deborah Hendrych, Mathieu Besançon, and Sebastian Pokutta. Solving the optimal experiment design problem with mixed-integer convex methods. *arXiv preprint arXiv:2312.11200*, 2023.

Deborah Hendrych, Mathieu Besançon, David Martínez-Rubio, and Sebastian Pokutta. Secant line search for Frank-Wolfe algorithms. In *Forty-second International Conference on Machine Learning*, 2025. URL https://arxiv.org/abs/2501.18775.

Charles A. Holloway. An extension of the Frank and Wolfe method of feasible directions. *Math. Program.*, 6(1):14–27, December 1974. ISSN 0025-5610. doi: 10.1007/BF01580219. URL https://doi.org/10.1007/BF01580219.

Michał Horodecki, Paweł Horodecki, and Ryszard Horodecki. Separability of mixed states: necessary and sufficient conditions. *Physics Letters A*, 223(1):1–8, 1996. ISSN 0375-9601. doi: https://doi.org/10.1016/S0375-9601(96)00706-2. URL https://www.sciencedirect.com/science/article/pii/S0375960196007062.

Pawel Horodecki. Separability criterion and inseparable mixed states with positive partial transposition. *Physics Letters A*, 232(5):333–339, 1997. ISSN 0375-9601. doi: https://doi.org/10.1016/S0375-9601(97)00416-7. URL https://www.sciencedirect.com/science/article/pii/S0375960197004167.

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 Lacoste-Julien, 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 https://proceedings.mlr.press/v28/lacoste-julien13.html.

Guanghui Lan and Yi Zhou. Conditional gradient sliding for convex optimization. *SIAM Journal on Optimization*, 26(2):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. A unified toolbox for multipartite entanglement characterization. Manuscript in preparation (private communication with authors), 2025.

Yurii Nesterov. *Lectures on convex optimization*, volume 137. Springer, 2018.

Jiangwei Shang and Otfried Gühne. Convex optimization over classes of multiparticle entanglement. *Phys. Rev. Lett.*, 120:050506, Feb 2018. doi: 10.1103/PhysRevLett.120.050506. URL https://link.aps.org/doi/10.1103/PhysRevLett.120.050506.
Tianxiao Sun and Quoc Tran-Dinh. Generalized self-concordant functions: a recipe for Newton-type methods. *Mathematical Programming*, 178(1):145–213, 2019.

Kazuma K Tsuji, Ken'ichiro Tanaka, and Sebastian Pokutta. Pairwise conditional gradients without swap steps and sparser kernel herding. In *International Conference on Machine Learning*, pages 21864–21883. PMLR, 2022.

Marina Vinyes and Guillaume Obozinski. Fast column generation for atomic norm regularization. In Aarti Singh and Jerry Zhu, editors, *Proceedings of the 20th International Conference on Artificial Intelligence and Statistics*, volume 54 of *Proceedings of Machine Learning Research*, pages 547–556. PMLR, 20–22 Apr 2017. URL https://proceedings.mlr.press/v54/vinyes17a.html.

Elias Wirth, Mathieu Besançon, and Sebastian Pokutta. The pivoting framework: Frank-Wolfe algorithms with active set size control. In *The 28th International Conference on Artificial Intelligence and Statistics*, 2025. URL https://arxiv.org/abs/2407.11760.

Philip Wolfe. Finding the nearest point in a polytope. *Math. Program.*, 11(1):128–149, December 1976. ISSN 0025-5610. doi: 10.1007/BF01580381. URL https://doi.org/10.1007/BF01580381.

Zev Woodstock and Sebastian Pokutta. Splitting the conditional gradient algorithm. *SIAM Journal on Optimization*, 35(1):347–368, 2025. doi: 10.1137/24M1638008. URL https://doi.org/10.1137/24M1638008.

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, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, *Advances in Neural Information Processing Systems*, volume 31. Curran Associates, Inc., 2018. URL https://proceedings.neurips.cc/paper_files/paper/2018/file/f8e59f4b2fe7c5705bf878bbd494ccdf-Paper.pdf.
A Proofs for Corrective Frank-Wolfe

In this section, we provide proofs for the theoretical results on CFW stated in Section 2. Before we present a more general version of Theorem 2 and its proof, we recall two lemmas resulting from the sharpness of the objective function and a conversion from contraction to convergence rates.

**Lemma 11.** [Braun et al., 2022, Lemma 3.32] Let $\mathcal{X}$ be a polytope of pyramidal width $\delta > 0$ and let $f$ be a $(c, \theta)$-sharp convex function over $\mathcal{X}$. Let $\mathbf{a}$ and $\mathbf{v}$ be defined as in Algorithm 1, then

$$ \frac{1}{c}(f(\mathbf{x}) - f^*)^{1-\theta} \le \frac{\langle \nabla f(\mathbf{x}), \mathbf{a} - \mathbf{v} \rangle}{\delta}. \quad (12) $$

**Lemma 12.** [Braun et al., 2022, Lemma 2.21] Let {$h_t$}$_t$ be a sequence of positive numbers and let $c_0, c_1, c_2, \alpha$ be positive numbers with $c_1 < 1$ such that $h_1 \le c_0$ and $h_t - h_{t+1} \ge h_t \min\{c_1, c_2h_t^\alpha\}$ for all $t \ge 1$, then

$$ h_t \le \begin{cases} c_0(1-c_1)^{t-1} & \text{if } 1 \le t \le t_0 \\ \frac{(c_1/c_2)^{1/\alpha}}{(1+c_1\alpha(t-t_0))^{1/\alpha}} = \mathcal{O}(1/t^{1/\alpha}) & \text{if } t \ge t_0, \end{cases} $$

where

$$ t_0 \stackrel{\text{def}}{=} \max \left\{ \left\lfloor \log_{1-c_1} \left( \frac{(c_1/c_2)^{1/\alpha}}{c_0} \right) \right\rfloor + 2, 1 \right\}. $$

**Theorem 2.** Let $\mathcal{X}$ be a convex feasible set with diameter $D$ and $f$ be a convex, $L$-smooth function over $\mathcal{X}$. Consider the sequence {$\mathbf{x}_t$}$_{t=0}^T \subset \mathcal{X}$ obtained by Algorithm 1. Then we have

$$ f(\mathbf{x}_T) - f^* \le \frac{4LD^2}{T}. \quad (1) $$

If additionally $f$ is $(c, \frac{1}{2})$-sharp and $\mathcal{X}$ is a polytope with pyramidal width $\delta$, then

$$ f(\mathbf{x}_T) - f^* \le (f(\mathbf{x}_0) - f^*) \exp(-c_f \mathcal{X} T), \quad (2) $$

where $c_f, \mathcal{X} \stackrel{\text{def}}{=} \min \left\{ \frac{1}{4}, \frac{\delta^2}{16Lc^2D^2} \right\}$. If $f$ is $(c, \theta)$-sharp with $\theta < \frac{1}{2}$, then

$$ f(\mathbf{x}_T) - f^* = \mathcal{O} \left( \frac{1}{T^{\frac{1}{1-2\theta}}} \right). \quad (3) $$

*Proof.* Let $T$ be the number of iterations of the algorithm, $T_{FW}$ the number of Frank-Wolfe steps, $T_{desc}$ the number of descent steps, and $T_{drop}$ 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 a time. As a drop step reduces the active set by at least one vertex, we have $T_{drop} \le T_{FW}$ and thus,

$$ T = T_{FW} + T_{drop} + T_{desc} \le 2T_{FW} + T_{desc} \le 2(T_{FW} + T_{desc}). \quad (13) $$

Next, we bound the primal gap $h_t \stackrel{\text{def}}{=} f(\mathbf{x}_t) - f^*$ at iteration $t$.

First, we consider the case when a Frank-Wolfe step is taken. Using $L$-smoothness of $f$, the definition of the FW step $\mathbf{x}_{t+1} = \mathbf{x}_t + \gamma_t(\mathbf{v}_t - \mathbf{x}_t)$, and the diameter $D$ of the feasible region yields

$$ \begin{aligned} h_t - h_{t+1} &= f(\mathbf{x}_t) - f(\mathbf{x}_{t+1}) \\ &\ge \gamma_t \langle \nabla f(\mathbf{x}_t), \mathbf{x}_t - \mathbf{v}_t \rangle - \frac{\gamma_t^2 L}{2} \|\mathbf{x}_t - \mathbf{v}_t\|^2 \\ &\ge \gamma_t \langle \nabla f(\mathbf{x}_t), \mathbf{x}_t - \mathbf{v}_t \rangle - \frac{\gamma_t^2 L D^2}{2}. \end{aligned} \quad (14) $$

As $\mathbf{v}_t \in \operatorname*{argmax}_{\mathbf{v} \in V(\mathcal{X})} \langle \nabla f(\mathbf{x}_t), \mathbf{x}_t - \mathbf{v} \rangle$ by definition, and by convexity of $f$, we get

$$ h_t - h_{t+1} \ge \gamma_t \langle \nabla f(\mathbf{x}_t), \mathbf{x}_t - \mathbf{x}_t^* \rangle - \frac{\gamma_t^2 L D^2}{2} \ge \gamma_t h_t - \frac{\gamma_t^2 L D^2}{2}. \quad (15) $$

Let $\hat{\gamma}_t = \frac{h_t}{LD^2}$, which yields a lower bound on the progress made by the exact line search if $\hat{\gamma}_t \le 1$. For (15) we have then

$$ h_t - h_{t+1} \ge \hat{\gamma}_t h_t - \frac{\hat{\gamma}_t^2 L D^2}{2} = \frac{h_t^2}{2LD^2}. \quad (16) $$
If $\hat{\gamma}_t > 1$, we have by definition $h_t \geq LD^2$. We can bound the progress of the line search using $\gamma_t = 1$ in (15), which yields

$$h_t - h_{t+1} \geq h_t - \frac{LD^2}{2} \geq \frac{1}{2}h_t. \qquad (17)$$

Combining (16), (17), we have

$$h_{t+1} \leq \begin{cases} h_t - \frac{h_t^2}{2LD^2} & \text{if } \hat{\gamma}_t \leq 1 \\ \frac{1}{2}h_t & \text{if } \hat{\gamma}_t > 1. \end{cases} \qquad (18)$$

Next, we consider the case when a descent step is taken. Using the criterion for performing a corrective step, the optimality of $\mathbf{v}_t$ and the convexity of $f$, we have

$$\begin{aligned} h_t - h_{t+1} &= f(\mathbf{x}_t) - f(\mathbf{x}_{t+1}) \geq \frac{\langle \nabla f(\mathbf{x}_t), \mathbf{a}_t - \mathbf{s}_t \rangle^2}{2LD^2} \\ &\geq \frac{\langle \nabla f(\mathbf{x}_t), \mathbf{x}_t - \mathbf{v}_t \rangle^2}{2LD^2} \\ &\geq \frac{\langle \nabla f(\mathbf{x}_t), \mathbf{x}_t - \mathbf{x}^* \rangle^2}{2LD^2} \\ &\geq \frac{h_t^2}{2LD^2}. \end{aligned} \qquad (19)$$

Together with (18), we get

$$h_{t+1} \leq \frac{2LD^2}{T_{\text{FW}} + T_{\text{desc}}},$$

which can be shown in the same way as in the proof of Corollary 4.2 in Braun et al. [2019], with $2LD^2$ replacing the value $4L_f$. Together with (13), we get

$$h_T \leq \frac{4LD^2}{T},$$

which proves (1).

Now we prove the accelerated convergence rate (2) and (3) with the additional assumptions that $f$ is $(c, \theta)$-sharp and $\mathcal{X}$ is a polytope. Again, we will bound the primal gap $h_t$ for different steps of the algorithm.

First, we consider the iterations when the Frank-Wolfe step is taken. By line 6 of Algorithm 1 we have

$$\langle \nabla f(\mathbf{x}_t), \mathbf{x}_t - \mathbf{v}_t \rangle \geq \langle \nabla f(\mathbf{x}_t), \mathbf{a}_t - \mathbf{s}_t \rangle \geq \langle \nabla f(\mathbf{x}_t), \mathbf{a}_t - \mathbf{x}_t \rangle.$$

Adding the left-hand side to both sides yields:

$$2 \langle \nabla f(\mathbf{x}_t), \mathbf{x}_t - \mathbf{v}_t \rangle \geq \langle \nabla f(\mathbf{x}_t), \mathbf{a}_t - \mathbf{v}_t \rangle. \qquad (20)$$

Similar to the proof of the sublinear rate, we consider a primal progress bound induced by smoothness, specifically (14), and choose a specific step size, $\tilde{\gamma}_t = \frac{\langle \nabla f(\mathbf{x}_t), \mathbf{x}_t - \mathbf{v}_t \rangle}{LD^2}$. For the case $\tilde{\gamma}_t < 1$, we have

$$h_t - h_{t+1} \geq \frac{\langle \nabla f(\mathbf{x}_t), \mathbf{x}_t - \mathbf{v}_t \rangle^2}{2LD^2}. \qquad (21)$$

Together with (20) and Lemma 11 we get

$$\begin{aligned} h_t - h_{t+1} &\geq \frac{\langle \nabla f(\mathbf{x}_t), \mathbf{x}_t - \mathbf{v}_t \rangle^2}{2LD^2} \\ &\geq \frac{\langle \nabla f(\mathbf{x}_t), \mathbf{a}_t - \mathbf{v}_t \rangle^2}{8LD^2} \\ &\geq \frac{\delta^2}{8c^2LD^2} h_t^{2(1-\theta)}. \end{aligned} \qquad (22)$$
In the case $\tilde{\gamma}_t \ge 1$ we have $\langle \nabla f(\mathbf{x}_t), \mathbf{x}_t - \mathbf{v}_t \rangle \ge LD^2$. Again, we can bound the progress of the exact line search using $\gamma_t = 1$ in (14), which yields

$$h_t - h_{t+1} \ge \langle \nabla f(\mathbf{x}_t), \mathbf{x}_t - \mathbf{v}_t \rangle - \frac{LD^2}{2} \\ \ge \frac{\langle \nabla f(\mathbf{x}_t), \mathbf{x}_t - \mathbf{v}_t \rangle}{2} \quad (23)$$

$$\ge \frac{\langle \nabla f(\mathbf{x}_t), \mathbf{x}_t - \mathbf{x}_t^* \rangle}{2} \ge \frac{1}{2} h_t. \quad (24)$$

For the descent step, we have

$$\langle \nabla f(\mathbf{x}_t), \mathbf{a}_t - \mathbf{s}_t \rangle \ge \langle \nabla f(\mathbf{x}_t), \mathbf{x}_t - \mathbf{v}_t \rangle \ge \langle \nabla f(\mathbf{x}_t), \mathbf{s}_t - \mathbf{v}_t \rangle.$$

Adding $\langle \nabla f(\mathbf{x}_t), \mathbf{a}_t - \mathbf{s}_t \rangle$ to both sides yields

$$2 \langle \nabla f(\mathbf{x}_t), \mathbf{a}_t - \mathbf{s}_t \rangle \ge \langle \nabla f(\mathbf{x}_t), \mathbf{a}_t - \mathbf{v}_t \rangle.$$

Together with the definition of a descent step, line 6 of Algorithm 1 and again Lemma 11, we get

$$h_t - h_{t+1} \ge \frac{\langle \nabla f(\mathbf{x}_t), \mathbf{a}_t - \mathbf{s}_t \rangle^2}{2LD^2} \\ \ge \frac{\langle \nabla f(\mathbf{x}_t), \mathbf{a}_t - \mathbf{v}_t \rangle^2}{8LD^2} \\ \ge \frac{\delta^2}{8c^2LD^2} h_t^{2(1-\theta)}. \quad (25)$$

Together with (22) and (24) we have

$$h_t - h_{t+1} \ge h_t \min \left\{ \frac{1}{2}, \frac{\delta^2}{8c^2LD^2} h_t^{1-2\theta} \right\}, \quad (26)$$

for any iteration $t$ that is not a drop step. For $\theta = \frac{1}{2}$, this simplifies to

$$h_{t+1} \le \min \left\{ \frac{1}{2}, 1 - \frac{\delta^2}{8c^2LD^2} \right\} h_t.$$

By (13) and the fact that drop steps are non-increasing, i.e., $h_{t+1} \le h_t$, we have

$$h_T \le h_0 \min \left\{ \frac{1}{2}, 1 - \frac{\delta^2}{8c^2LD^2} \right\}^{T_{FW}+T_{desc}} \\ \le h_0 (1 - 2c_{f,\chi})^{\frac{T}{2}} \\ \le h_0 \exp(-c_{f,\chi}T),$$

where $c_{f,\chi} = \min \left\{ \frac{1}{4}, \frac{\delta^2}{16c^2LD^2} \right\}$.

For $\theta < \frac{1}{2}$, we use again that drop steps are non-increasing, and the result of Lemma 12 with $c_0 = h_0$, $c_1 = \frac{1}{2}$, $c_2 = \frac{\delta^2}{8c^2LD^2}$ and $\alpha = 1 - 2\theta$ yielding

$$h_T \le \begin{cases} \frac{h_0}{2^{T_{FW}+T_{desc}-1}} & \text{if } 1 \le T_{FW} + T_{desc} \le t_0, \\ \left( \frac{4c^2LD^2}{1+\frac{1-2\theta}{2}(T_{FW}+T_{desc}-t_0)} \right)^{\frac{1}{1-2\theta}} & \text{if } T_{FW} + T_{desc} \ge t_0, \end{cases} \quad (27)$$

where

$$t_0 \stackrel{\text{def}}{=} \max \left\{ \left\lfloor \log_{\frac{1}{2}} \left( \frac{4c^2LD^2}{\delta} \right)^{\frac{1}{1-2\theta}} \right\rfloor + 2, 1 \right\}.$$

In particular, the above bound yields

$$h_T \le \left( \frac{4c^2LD^2}{1 + \frac{1-2\theta}{2}(T_{FW} + T_{desc} - t_0)} \right)^{\frac{1}{1-2\theta}} = \mathcal{O} \left( \frac{1}{T^{\frac{1}{1-2\theta}}} \right).$$

□
Next, we prove that different types of 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 2.*

*Proof.* First, we consider the local pairwise step given in Algorithm 3. Let $\hat{x} = x - \hat{\gamma}(a - s)$ be the point produced by a short step, i.e., $\hat{\gamma} = \frac{\langle \nabla f(x), a-s \rangle}{L \|a-s\|^2}$. If $\hat{\gamma} \le \gamma_{\max}$, we have by smoothness of $f$ that

$$f(x) - f(\hat{x}) \ge \hat{\gamma} \langle \nabla f(x), a-s \rangle - \frac{L \hat{\gamma}^2}{2} \|a-s\|^2 = \frac{\langle \nabla f(x), a-s \rangle^2}{2L \|a-s\|^2} \ge \frac{\langle \nabla f(x), a-s \rangle^2}{2LD^2}.$$

Hence, $\hat{x}$ satisfies the criteria of the descent step, and thus so does $x'$ produced by the optimal step size $\gamma^*$.

If $\hat{\gamma} > \gamma_{\max}$, convexity of $f$ yields that either $f(x') \le f(x)$ or $\gamma^* = \gamma_{\max}$. In the first case, we have a valid descent step, and in the second case, we have a drop step.

Second, we consider the fully-corrective step in Algorithm 4. We compare the update to $\hat{x}$. If $\hat{\gamma} \le \gamma_{\max}$ and therefore $\hat{x} \in \text{conv}(S)$, the descent criterion is satisfied. We now analyze the case $\hat{x} \notin \text{conv}(S)$. If $f(x') \le f(\hat{x})$ then we have a valid descent step. However, if $f(x') > f(\hat{x})$, we know that $x' \notin \text{relint}(\text{conv}(S))$. Otherwise, there is a $\tilde{x} \in \text{conv}(S)$ on the line segment between $\hat{x}$ and $x'$ with $f(\tilde{x}) < f(x')$. This contradicts the optimality of $x'$, thus we have $x' \in \partial \text{conv}(S)$. Consequently, there exists an atom $u \in S$ which can be dropped without increasing the objective.

Finally, the simplex gradient descent step of BCG is a valid corrective step, as shown in Lemma 4.1 in Braun et al. [2019]. □

Finally, we prove the active set identification property of CFW in finite time under the assumption of strict complementarity.

**Theorem 4.** Let $\mathcal{X}$ be a polytope and let $f$ be a convex, $L$-smooth function over $\mathcal{X}$. Assume that strict complementarity holds. Consider the sequence $\{x_t\}_{t=0}^T$ generated by Algorithm 1. Then there exists an iteration $\tilde{T}$ such that

$$x_t \in \mathcal{F}^* \quad \text{for all } t \ge \tilde{T}.$$

*Proof.* Let $\varepsilon > 0$. For any $x^* \in \mathcal{X}^*$, $v \in V(\mathcal{X})$ and $x \in \mathcal{X}$ with $\|x - x^*\| \le \varepsilon$, $L$-smoothness of $f$ yields

$$\begin{align*}
\langle \nabla f(x), v - x \rangle &= \langle \nabla f(x^*), v - x \rangle + \langle \nabla f(x) - \nabla f(x^*), v - x \rangle \\
&= \langle \nabla f(x^*), v - x^* \rangle + \langle \nabla f(x^*), x^* - x \rangle + \langle \nabla f(x) - \nabla f(x^*), v - x \rangle \\
&\ge \langle \nabla f(x^*), v - x^* \rangle - \|\nabla f(x^*)\| \cdot \|x^* - x\| - \|\nabla f(x) - \nabla f(x^*)\| \cdot \|v - x\| \\
&\ge \langle \nabla f(x^*), v - x^* \rangle - \|\nabla f(x^*)\| \cdot \|x^* - x\| - L \|x - x^*\| \cdot \|v - x\| \\
&\ge \langle \nabla f(x^*), v - x^* \rangle - \|\nabla f(x^*)\| \cdot \varepsilon - L \cdot \varepsilon \cdot D \\
&= \langle \nabla f(x^*), v - x^* \rangle - \varepsilon \cdot \underbrace{(\|\nabla f(x^*)\| + LD)}_{\text{def}=c}
\end{align*}$$

Strict complementarity with constant $\rho > 0$ yields now

$$\langle \nabla f(x), v - x \rangle \ge \begin{cases} \rho - \varepsilon c & v \notin \mathcal{F}^*, \\ -\varepsilon c & v \in \mathcal{F}^*. \end{cases}$$

For sufficiently small $\varepsilon$ we have that $\rho - \varepsilon c > \varepsilon c$, e.g., for $\varepsilon = \frac{\rho}{3c}$. By Theorem 2, $f(x_T)$ converges to $f^*$. Since $f$ is continuous and $\mathcal{X}^*$ is compact, it follows that $\text{dist}(x_t, \mathcal{X}^*)$ converges to 0. Thus, there is a $T_1$ such that $\text{dist}(x_t, \mathcal{X}^*) \le \varepsilon$ for all $t \ge T_1$. Therefore, there exists a $x_t^* \in \mathcal{X}^*$ such that $\|x_t - x_t^*\| \le \varepsilon$.

Let $v_t$, $a_t$, $s_t$ be defined as in Algorithm 1. Next, we consider the cases where the current iterate $x_t$ lies inside or outside the optimal face $\mathcal{F}^*$. If $x_t \notin \mathcal{F}^*$, then there exists a $w \in S_t \setminus \mathcal{F}^*$. Consequently, we have

$$\langle \nabla f(x_t), a_t - s_t \rangle \ge \langle \nabla f(x_t), w - x_t \rangle \ge \rho - \varepsilon c > \varepsilon c \ge \langle \nabla f(x_t), x_t - v_t \rangle. \quad (28)$$
Therefore, CFW would choose to perform a corrective step. Let now $\tilde{\epsilon} = \frac{(\rho-\epsilon c)^2}{2LD^2}$. By Theorem 2 there exists a $T_2$ such that $f(\mathbf{x}_t) - f^* \le \tilde{\epsilon}$ for all $t \ge T_2$. Next, (28) yields

$$f(\mathbf{x}_t) - f^* \le \frac{(\rho - \epsilon c)^2}{2LD^2} \le \frac{\langle \nabla f(\mathbf{x}_t), \mathbf{a}_t - \mathbf{s}_t \rangle^2}{2LD^2}$$

and thus the optimal primal progress is smaller than the required progress for a valid descent step in Algorithm 2. Since we cannot perform descent steps and since drop steps are non-increasing, CFW has to perform drop steps in every iteration $t \ge \max(T_1, T_2)$ where $\mathbf{x}_t \notin \mathcal{F}^*$.

Assume now that we always keep one vertex $\tilde{\mathbf{v}} \notin \mathcal{F}^*$ in the active set. Then in each iteration $\mathbf{x}_t$ stays outside $\mathcal{F}^*$, and we would keep dropping vertices until $\mathbf{x}_t = \tilde{\mathbf{v}}$. This contradicts the convergence of Theorem 2. Therefore, there exists an iteration $\tilde{T} \ge \max(T_1, T_2)$ such that $S_{\tilde{T}} \subseteq \mathcal{F}^*$ and thus $\mathbf{x}_{\tilde{T}} \in \mathcal{F}^*$.

We turn to the case where $\mathbf{x}_t \in \mathcal{F}^*$. Strict complementarity and convexity yield

$$\langle \nabla f(\mathbf{x}_t), \mathbf{v}_t - \mathbf{x}_t \rangle \le \langle \nabla f(\mathbf{x}_t), \mathbf{x}_t^* - \mathbf{x}_t \rangle \le 0 < \rho - \epsilon c \le \langle \nabla f(\mathbf{x}_t), \mathbf{v} - \mathbf{x}_t \rangle$$

for any $\mathbf{v} \in V(\mathcal{X}) \setminus \mathcal{F}^*$. Therefore, we have $\mathbf{v}_t \in \mathcal{F}^*$ and thus $\mathbf{x}_{t+1} \in \mathcal{F}^*$ as neither FW step nor corrective steps move the iterate $\mathbf{x}_t$ out of $\mathcal{F}^*$. Finally, induction yields $\mathbf{x}_t \in \mathcal{F}^*$ for all $t \ge \tilde{T}$. $\square$

## B Lazified Corrective Frank-Wolfe

In this section, we will prove the convergence results of a more general version of Theorem 3 for the Lazified Corrective Frank-Wolfe method (LCFW) proposed in Algorithm 7.

<caption>**Algorithm 7 Lazified Corrective Frank-Wolfe (LCFW)**</caption>

**Require:** convex smooth function $f$, starting point $\mathbf{x}_0 \in V(\mathcal{X})$, accuracy parameter $J \ge 1$.
1: $\Phi_0 \leftarrow \max_{\mathbf{v} \in V(\mathcal{X})} \langle \nabla f(\mathbf{x}_0), \mathbf{x}_0 - \mathbf{v} \rangle / 2$
2: $S_0 \leftarrow \{\mathbf{x}_0\}$
3: **for** $t = 0$ to $T-1$ **do**
4: &nbsp;&nbsp;&nbsp;&nbsp;**a**$_t \leftarrow \operatorname*{argmax}_{\mathbf{v} \in S_t} \langle \nabla f(\mathbf{x}_t), \mathbf{v} \rangle$ &nbsp;&nbsp;&nbsp;&nbsp;▷ away vertex
5: &nbsp;&nbsp;&nbsp;&nbsp;**s**$_t \leftarrow \operatorname*{argmin}_{\mathbf{v} \in S_t} \langle \nabla f(\mathbf{x}_t), \mathbf{v} \rangle$ &nbsp;&nbsp;&nbsp;&nbsp;▷ local FW
6: &nbsp;&nbsp;&nbsp;&nbsp;**if** $\langle \nabla f(\mathbf{x}_t), \mathbf{a}_t - \mathbf{s}_t \rangle \ge \Phi_t$ **then**
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**x**$_{t+1}$, $S_{t+1} \leftarrow \text{CorrectiveStep}(S_t, \mathbf{x}_t, \mathbf{a}_t, \mathbf{s}_t)$
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**\Phi**$_{t+1} \leftarrow \Phi_t$
9: &nbsp;&nbsp;&nbsp;&nbsp;**else**
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**v**$_t \leftarrow \operatorname*{argmax}_{\mathbf{v} \in V(\mathcal{X})} \langle \nabla f(\mathbf{x}_t), \mathbf{x}_t - \mathbf{v} \rangle$ &nbsp;&nbsp;&nbsp;&nbsp;▷ global FW
11: &nbsp;&nbsp;&nbsp;&nbsp;**if** $\langle \nabla f(\mathbf{x}_t), \mathbf{x}_t - \mathbf{v}_t \rangle \ge \Phi_t / J$ **then**
12: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**d**$_t \leftarrow \mathbf{x}_t - \mathbf{v}_t$
13: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**\gamma**$_t \leftarrow \operatorname*{argmin}_{\gamma \in [0,1]} f(\mathbf{x}_t - \gamma \mathbf{d}_t)$
14: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**x**$_{t+1} \leftarrow \mathbf{x}_t - \gamma_t \mathbf{d}_t$
15: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**S**$_{t+1} \leftarrow S_t \cup \{\mathbf{v}_t\}$
16: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**\Phi**$_{t+1} \leftarrow \Phi_t$ &nbsp;&nbsp;&nbsp;&nbsp;▷ FW step
17: &nbsp;&nbsp;&nbsp;&nbsp;**else**
18: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**x**$_{t+1} \leftarrow \mathbf{x}_t$
19: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**S**$_{t+1} \leftarrow S_t$
20: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**\Phi**$_{t+1} \leftarrow \Phi_t / 2$ &nbsp;&nbsp;&nbsp;&nbsp;▷ gap step
21: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
22: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
23: **end for**

**Theorem 3.** Let $\mathcal{X}$ be a convex feasible set with diameter $D$ and $f$ be a convex, $L$-smooth function over $\mathcal{X}$. Consider the sequence $\{\mathbf{x}_t\}_{t=0}^T \subset \mathcal{X}$ obtained by the Algorithm 7. Then we have

$$f(\mathbf{x}_T) - f^* = \mathcal{O}\left(\frac{1}{T}\right). \qquad (4)$$

If additionally $f$ is $(c, \frac{1}{2})$-sharp and $\mathcal{X}$ is a polytope with pyramidal width $\delta$, then

$$f(\mathbf{x}_T) - f^* = \mathcal{O}(\exp(-aT)), \qquad (5)$$
for some constant $a > 0$ independent of $T$. If $f$ is $(c, \theta)$-sharp with $\theta < \frac{1}{2}$, then

$$f(\mathbf{x}_T) - f^* = \mathcal{O}\left(\frac{1}{T^{\frac{1}{1-2\theta}}}\right). \qquad (6)$$

*Proof.* Similar to the proof of Theorem 2, we will prove an upper bound on the total number of necessary iterations $T$ for achieving $\varepsilon$ primal accuracy.

Let $N_{\text{FW}}$, $N_{\text{desc}}$, $N_{\text{drop}}$, $N_{\text{gap}}$ denote the number of FW, descent, drop, and gap steps, respectively. Let $t_1, \dots, t_{N_{\text{gap}}}$ be the iterations of the gap steps. We set $t_0 = -1$ for consistency. Then let $N_{\text{FW}}^i$ and $N_{\text{desc}}^i$ be the number of FW and descent steps in the $i$-th epoch, the iterations between $t_{i-1}$ and $t_i$. To bound the total number of iterations $T$ necessary to achieve $\varepsilon$ primal accuracy, we first bound the number of gap steps $N_{\text{gap}}$.

Let $u = t_i + 1$ for some $i \in \{1, \dots, N_{\text{gap}}\}$ be the iteration after a gap step. Note that $\mathbf{x}_u = \mathbf{x}_{t_i}$ and thus $\mathbf{v}_u = \mathbf{v}_{t_i}$. By convexity and the optimality of $\mathbf{v}_u$, we have

$$f(\mathbf{x}_u) - f^* \le \langle \nabla f(\mathbf{x}_u), \mathbf{x}_u - \mathbf{x}^* \rangle \le \langle \nabla f(\mathbf{x}_u), \mathbf{x}_u - \mathbf{v}_u \rangle \le \frac{2\Phi_u}{J} \le 2\Phi_u. \qquad (29)$$

By definition of $\Phi_0$, this also holds for $u = 0$. Furthermore, the gap step always halves the value of $\Phi$, so we have $\Phi_u = \Phi_{t_i+1} = 2^{-i}\Phi_0$. By bounding the right-hand side of (29) by $\varepsilon$, we get

$$N_{\text{gap}} \le \left\lceil \log_2 \frac{2\Phi_0}{\varepsilon} \right\rceil. \qquad (30)$$

With $N_{\text{drop}} \le N_{\text{FW}}$ we have that

$$\begin{aligned} T &\le N_{\text{FW}} + N_{\text{desc}} + N_{\text{gap}} + N_{\text{drop}} \\ &\le 2N_{\text{FW}} + N_{\text{desc}} + N_{\text{gap}} \\ &\le \sum_{i=1}^{N_{\text{gap}}} 2N_{\text{FW}}^i + N_{\text{desc}}^i + N_{\text{gap}}. \end{aligned} \qquad (31)$$

In the remainder of the proof, we find upper bounds for $2N_{\text{FW}}^i + N_{\text{desc}}^i$ by lower bounding the progress of FW and descent steps for both cases considered for $f$. First, we consider the case where $f$ is convex and smooth.

Let $t \in (t_i, t_{i+1})$, so $\Phi_t = \Phi_u$. If we perform a FW step, we have that $\langle \nabla f(\mathbf{x}_t), \mathbf{x}_t - \mathbf{v}_t \rangle \ge \Phi_t/J = \Phi_u/J$. Here we can use results from the proof of Theorem 2, i.e., (21) and (23), which yield

$$\begin{aligned} f(\mathbf{x}_t) - f(\mathbf{x}_{t+1}) &\ge \min \left\{ \frac{\langle \nabla f(\mathbf{x}_t), \mathbf{x}_t - \mathbf{v}_t \rangle^2}{2LD^2}, \frac{1}{2} \langle \nabla f(\mathbf{x}_t), \mathbf{x}_t - \mathbf{v}_t \rangle \right\} \\ &\ge \frac{\Phi_u}{2J} \min \left\{ \frac{\Phi_u}{LD^2J}, 1 \right\}. \end{aligned} \qquad (32)$$

Next, we consider the case of a descent step, i.e., $\langle \nabla f(\mathbf{x}_t), \mathbf{a}_t - \mathbf{s}_t \rangle \ge \Phi_t$. Together with the definition of the descent step, we have

$$f(\mathbf{x}_t) - f(\mathbf{x}_{t+1}) \ge \frac{\langle \nabla f(\mathbf{x}_t), \mathbf{a}_t - \mathbf{s}_t \rangle^2}{2LD^2} \ge \frac{\Phi_u^2}{2LD^2}. \qquad (33)$$

We now use (29) as an upper bound of the primal progress in the $i$-th epoch, and we use (32) and (33) to lower bound the primal progress. Let $I = \lceil \log_2 \frac{\Phi_0}{LD^2J} \rceil$. For $i < I$ we have that $\Phi_0 \ge 2^i LD^2J$ and thus $\Phi_u \ge LD^2J$. Then we get with (29), (32) and (33),

$$\begin{aligned} 2\Phi_u &\ge f(\mathbf{x}_u) - f^* \\ &\ge f(\mathbf{x}_u) - f(\mathbf{x}_{t_{i+1}}) \\ &\ge N_{\text{FW}}^i \frac{\Phi_u}{2J} + N_{\text{desc}}^i \frac{\Phi_u^2}{2LD^2} \\ &\ge 2N_{\text{FW}}^i \frac{\Phi_u}{4J} + N_{\text{desc}}^i \frac{\Phi_u J}{2} \\ &= \Phi_u \left( 2N_{\text{FW}}^i \frac{1}{4J} + N_{\text{desc}}^i \frac{J}{2} \right), \end{aligned}$$
and thus

$$2N_{\text{FW}}^{i} + N_{\text{desc}}^{i} \le \max \left\{ 8J, \frac{4}{J} \right\}. \qquad (34)$$

For $i \ge I$ we have that $\Phi_u \le LD^2J$ and thus with (29), (32) and (33),

$$\begin{aligned} 2\Phi_u &\ge f(\mathbf{x}_u) - f^* \\ &\ge f(\mathbf{x}_u) - f(\mathbf{x}_{t_{i+1}}) \\ &\ge N_{\text{FW}}^i \frac{\Phi_u^2}{2J^2LD^2} + N_{\text{desc}}^i \frac{\Phi_u^2}{2LD^2} \\ &= \Phi_u^2 \left( 2N_{\text{FW}}^i \frac{1}{4LD^2J^2} + N_{\text{desc}}^i \frac{1}{2LD^2} \right) \end{aligned}$$

Thus we have

$$2N_{\text{FW}}^{i} + N_{\text{desc}}^{i} \le \frac{1}{\Phi_{u}} \max \{8LD^{2}J^{2}, 4LD^{2}\} = \frac{2^{i}}{\Phi_{0}} \max \{8LD^{2}J^{2}, 4LD^{2}\}. \quad (35)$$

We can now bound the number of total iterations using (31) and (30),

$$\begin{aligned} T &\le \sum_{i=1}^{N_{\text{gap}}} 2N_{\text{FW}}^{i} + N_{\text{desc}}^{i} + N_{\text{gap}} \\ &\le I \cdot \max \left\{ 8J, \frac{4}{J} \right\} + \sum_{i=I}^{N_{\text{gap}}} \frac{2^i}{\Phi_0} \max \{8LD^2J^2, 4LD^2\} + N_{\text{gap}} \\ &\le I \cdot \max \left\{ 8J, \frac{4}{J} \right\} + (2^{N_{\text{gap}}+1}-1) \frac{1}{\Phi_0} \max \{8LD^2J^2, 4LD^2\} + N_{\text{gap}} \\ &\le I \cdot \max \left\{ 8J, \frac{4}{J} \right\} + (2^{\log_2 \frac{2\Phi_0}{\varepsilon}} + 2 - 1) \frac{1}{\Phi_0} \max \{8LD^2J^2, 4LD^2\} + \left[ \log_2 \frac{2\Phi_0}{\varepsilon} \right] \\ &\le I \cdot \max \left\{ 8J, \frac{4}{J} \right\} + \frac{4}{\varepsilon} \max \{8LD^2J^2, 4LD^2\} + \left[ \log_2 \frac{2\Phi_0}{\varepsilon} \right]. \end{aligned}$$

Finally, (29) yields

$$f(\mathbf{x}_T) - f^* \le \frac{\Phi_T}{2} \le \frac{\varepsilon}{2} = \mathcal{O}\left(\frac{1}{T}\right).$$

Consider now the case where $f$ is $(c, \theta)$-sharp and $\mathcal{X}$ is a polytope. Let again $u = t_i + 1$ for some $i \in \{1, \dots, N_{\text{gap}}\}$ be the iteration after a gap step. Then we have

$$\langle \nabla f(\mathbf{x}_u), \mathbf{a}_u - \mathbf{v}_u \rangle \le \langle \nabla f(\mathbf{x}_u), \mathbf{a}_u - \mathbf{s}_u \rangle + \langle \nabla f(\mathbf{x}_u), \mathbf{x}_u - \mathbf{v}_u \rangle < \Phi_u + \Phi_u/J \le 2\Phi_u.$$

With Lemma 11 we have that

$$f(\mathbf{x}_u) - f^* \le \left( \frac{c \langle \nabla f(\mathbf{x}_u), \mathbf{a}_u - \mathbf{v}_u \rangle}{\delta} \right)^{\frac{1}{1-\theta}} \le \left( \frac{2c\Phi_u}{\delta} \right)^{\frac{1}{1-\theta}}. \qquad (36)$$

With this new upper bound on the primal gap, we can improve the bound on $2N_{\text{FW}}^i + N_{\text{desc}}^i$ for $i \ge I$. Using (36), (32) and (33), we get

$$\begin{aligned} \left( \frac{2c\Phi_u}{\delta} \right)^{\frac{1}{1-\theta}} &\ge f(\mathbf{x}_u) - f^* \\ &\ge f(\mathbf{x}_u) - f(\mathbf{x}_{t_{i+1}}) \\ &\ge N_{\text{FW}}^i \frac{\Phi_u^2}{2J^2LD^2} + N_{\text{desc}}^i \frac{\Phi_u^2}{2LD^2} \\ &\ge \frac{\Phi_u^2}{LD^2} \left( \frac{2N_{\text{FW}}^i}{4J^2} + \frac{N_{\text{desc}}^i}{2} \right). \end{aligned}$$
Consequently, we have

$$ 
\begin{aligned}
2N_{\text{FW}}^{i} + N_{\text{desc}}^{i} &\le \left(\frac{2c}{\delta}\right)^{\frac{1}{1-\theta}} LD^{2} \max\{4J^{2}, 2\} \Phi_{u}^{\frac{1}{1-\theta}-2} \\
&\le \left(\frac{2c}{\delta}\right)^{\frac{1}{1-\theta}} LD^{2} \max\{4J^{2}, 2\} \left(\frac{\Phi_{0}}{2^{i}}\right)^{\frac{1}{1-\theta}-2}.
\end{aligned} 
\quad (37) $$

For $\theta = \frac{1}{2}$ this yields

$$ \sum_{i=I}^{N_{\text{gap}}} 2N_{\text{FW}}^{i} + N_{\text{desc}}^{i} \le N_{\text{gap}} \frac{4c^2}{\delta^2} LD^2 \max\{4J^2, 2\}. \quad (38) $$

The bounds for the case $i < I$ in (34) stay unchanged. Together with (30) and (31) this yields,

$$ 
\begin{aligned}
T &\le \sum_{i=1}^{N_{\text{gap}}} 2N_{\text{FW}}^{i} + N_{\text{desc}}^{i} + N_{\text{gap}} \\
&\le I \cdot \max\left\{8J, \frac{4}{J}\right\} + (N_{\text{gap}} - I) \cdot \frac{4c^2 LD^2}{\delta^2} \max\{4J^2, 2\} + N_{\text{gap}} \\
&\le C_1 N_{\text{gap}} \le C_1 \left[\log_2 \frac{2\Phi_0}{\varepsilon}\right],
\end{aligned} 
$$

where $C_1 = 1 + \max\{\max\{8J, \frac{4}{J}\}, \frac{4c^2 LD^2}{\delta^2} \max\{4J^2, 2\}\}$. This is equivalent to

$$ \varepsilon \le 2\Phi_0 e^{\frac{1}{C_1}} \exp\left(-\frac{1}{C_1}T\right) = \mathcal{O}\left(\exp\left(-\frac{1}{C_1}T\right)\right). $$

Finally, with (36) we get

$$ f(\mathbf{x}_T) - f^* \le \left( \frac{c \langle \nabla f(\mathbf{x}_T), \mathbf{a}_T - \mathbf{v}_T \rangle}{\delta} \right)^2 \le \left( \frac{2c\Phi_T}{\delta} \right)^2 = \mathcal{O}(\exp(-aT)), $$

with $a = \frac{2}{C_1}$.

For $\theta < \frac{1}{2}$, (37) yields

$$ 
\begin{aligned}
\sum_{i=I}^{N_{\text{gap}}} 2N_{\text{FW}}^{i} + N_{\text{desc}}^{i} \\
&\le \left(\frac{2c}{\delta}\right)^{\frac{1}{1-\theta}} LD^{2} \max\{4J^{2}, 2\} \Phi_{0}^{\frac{1}{1-\theta}-2} \sum_{i=I}^{N_{\text{gap}}} 2^{i(2-\frac{1}{1-\theta})} \\
&\le \left(\frac{2c}{\delta}\right)^{\frac{1}{1-\theta}} LD^{2} \max\{4J^{2}, 2\} \Phi_{0}^{\frac{1}{1-\theta}-2} 2^{N_{\text{gap}}(2-\frac{1}{1-\theta})+1}
\end{aligned} 
$$

and similarly to the previous case, we get

$$ 
\begin{aligned}
T &\le \sum_{i=1}^{N_{\text{gap}}} 2N_{\text{FW}}^{i} + N_{\text{desc}}^{i} + N_{\text{gap}} \\
&\le I \cdot \max\left\{8J, \frac{4}{J}\right\} + \left(\frac{2c}{\delta}\right)^{\frac{1}{1-\theta}} LD^2 \max\{4J^2, 2\} \Phi_0^{\frac{1}{1-\theta}-2} 2^{N_{\text{gap}}(2-\frac{1}{1-\theta})+1} + N_{\text{gap}} \\
&\le I \cdot \max\left\{8J, \frac{4}{J}\right\} + \left(\frac{2c}{\delta}\right)^{\frac{1}{1-\theta}} LD^2 \max\{4J^2, 2\} \Phi_0^{\frac{1}{1-\theta}-2} 2^{\lceil \log_2 \frac{2\Phi_0}{\varepsilon} \rceil(2-\frac{1}{1-\theta})+1} + \left[\log_2 \frac{2\Phi_0}{\varepsilon}\right] \\
&\le I \cdot \max\left\{8J, \frac{4}{J}\right\} + \left(\frac{2c}{\delta}\right)^{\frac{1}{1-\theta}} LD^2 \max\{4J^2, 2\} \Phi_0^{\frac{1}{1-\theta}-2} 4 \cdot \left(\frac{2\Phi_0}{\varepsilon}\right)^{2-\frac{1}{1-\theta}} + \left[\log_2 \frac{2\Phi_0}{\varepsilon}\right] \\
&= \mathcal{O}\left(\frac{1}{\varepsilon^{\frac{1-2\theta}{1-\theta}}}\right).
\end{aligned} 
$$
This yields $\Phi_T \le \varepsilon = \mathcal{O}\left(\frac{1}{T^{\frac{1-\theta}{1-2\theta}}}\right)$. Finally, with (36) we get

$$f(\mathbf{x}_T) - f^* \le \left( \frac{c \langle \nabla f(\mathbf{x}_T), \mathbf{a}_T - \mathbf{v}_T \rangle}{\delta} \right)^{\frac{1}{1-\theta}} \le \left( \frac{2c\Phi_T}{\delta} \right)^{\frac{1}{1-\theta}} = \mathcal{O}\left( \frac{1}{T^{\frac{1}{1-2\theta}}} \right). \quad \square$$

# C Quadratic Corrections

## C.1 QC-MNP for convex objectives

In this section, we derive a variant of the QC-MNP method tailored for non-strongly convex objectives, i.e., 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,

$$\langle \mathbf{A}\mathbf{V}\boldsymbol{\lambda} + \mathbf{b}, \mathbf{v} - \mathbf{w} \rangle = 0 \quad \forall \mathbf{v} \in S \setminus \{\mathbf{w}\}, \quad \sum_{\mathbf{v} \in S} \boldsymbol{\lambda}_{\mathbf{v}} = 1. \qquad (39)$$

For a given solution $\boldsymbol{\lambda}$, the ratio test in Algorithm 6 maximizes $\tau$ such that the new weights $\tau\boldsymbol{\lambda} + (1 - \tau)\boldsymbol{\lambda}(\mathbf{x})$ are non-negative. If the solution is not unique, we can choose $\boldsymbol{\lambda}$ that allows for the largest $\tau$. 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 (39) yields the following non-linear program:

$$\begin{array}{ll}
\max_{\boldsymbol{\lambda} \in \mathbb{R}^m, \tau \in [0,1]} & \tau \\
\text{s.t.} & \langle \mathbf{A}\mathbf{V}\boldsymbol{\lambda} + \mathbf{b}, \mathbf{v} - \mathbf{w} \rangle = 0 \quad \forall \mathbf{v} \in S \setminus \{\mathbf{w}\}, \\
& \mathbf{1}^{\top}\boldsymbol{\lambda} = 1, \\
& \tau\boldsymbol{\lambda} + (1 - \tau)\boldsymbol{\lambda}(\mathbf{x}) \ge 0.
\end{array}$$

As $\mathbf{x}$ lies in the relative interior of $\text{conv}(S)$, there always exists a feasible $\tau > 0$. To obtain a linear inequality constraint, we divide the inequality constraint by $\tau$ and set $\beta = \frac{1-\tau}{\tau}$,

$$\boldsymbol{\lambda} + \beta\boldsymbol{\lambda}(\mathbf{x}) \ge 0.$$

Since maximizing $\tau$ on $(0, 1]$ is equivalent to minimizing $\beta$ on $[0, \infty)$, we obtain the following linear program:

$$\begin{array}{ll}
\min_{\boldsymbol{\lambda} \in \mathbb{R}^m, \beta \ge 0} & \beta \\
\text{s.t.} & \langle \mathbf{A}\mathbf{V}\boldsymbol{\lambda} + \mathbf{b}, \mathbf{v} - \mathbf{w} \rangle = 0 \quad \forall \mathbf{v} \in S \setminus \{\mathbf{w}\}, \\
& \mathbf{1}^{\top}\boldsymbol{\lambda} = 1, \\
& \boldsymbol{\lambda} + \beta\boldsymbol{\lambda}(\mathbf{x}) \ge 0.
\end{array} \qquad (40)$$

Algorithm 8 presents the alternative implementation of the QC-MNP-correction step, relying on the newly derived LP. We use again Algorithm 3 as a fallback step if there exists no affine minimizer.

We can now prove that Algorithm 8 always chooses an affine minimizer in $\text{conv}(S)$ if such exists.

**Lemma 13.** Let $S \subset \mathcal{X}$. If $\emptyset \ne \text{argmin}_{\mathbf{x} \in \text{conv}(S)} f(\mathbf{x}) \subseteq \text{argmin}_{\mathbf{x} \in \text{aff}(S)} f(\mathbf{x})$, then Algorithm 8 performs an FCFW step.

*Proof.* Since the linear system in (39) is a sufficient optimality condition for the affine minimizer, we know by assumption that it has at least one solution. Furthermore, there exists a solution which additionally satisfies $\boldsymbol{\lambda} \ge 0$. Therefore, $\beta = 0$ and $\boldsymbol{\lambda}$ are optimal solutions to (40). Consequently, Algorithm 8 performs an FCFW step. $\square$
**Algorithm 8** Quadratic Correction MNP

**Require:** $S \subset \mathcal{X}, \mathbf{x} \in \mathcal{X}$

$\beta, \tilde{\lambda} \leftarrow \text{Solve } (40)$

**if feasible then**

**if** $\beta = 0$ **then** ▷ FCFW step

$$ \mathbf{x}' \leftarrow \sum_{\mathbf{v} \in S} \tilde{\lambda}_{\mathbf{v}} \mathbf{v} \\ S' \leftarrow S $$

**else** ▷ MNP step

$$ \tau \leftarrow \frac{1}{\beta+1} \\ \mathbf{x}' \leftarrow \sum_{\mathbf{v} \in S} (\tau \tilde{\lambda}_{\mathbf{v}} + (1-\tau)\lambda_{\mathbf{v}}(\mathbf{x}))\mathbf{v} \\ S' \leftarrow \{\mathbf{v} \in S \mid \lambda_{\mathbf{v}}(\mathbf{x}') > 0\} $$

**end if**
**else** ▷ Fallback step

$$ S', \mathbf{x}' \leftarrow \text{LPS}(S, \mathbf{x}, \mathbf{a}, \mathbf{s}) $$

**end if**

## 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 (8) is feasible if and only if $\mathbf{b} \perp \text{span}(S) \cap \text{ker}(\mathbf{A})$. In particular, it is feasible if $\mathbf{A}$ is positive definite.

*Proof.* Instead of (8), we consider the equivalent system (10). Since the matrix $\mathbf{W}^\top \mathbf{A} \mathbf{W}$ is symmetric, the system is feasible if and only if

$$ \mathbf{W}^\top (\mathbf{A} \mathbf{w} + \mathbf{b}) \in \text{im}(\mathbf{W}^\top \mathbf{A} \mathbf{W}) = \ker(\mathbf{W}^\top \mathbf{A} \mathbf{W})^{-1}. $$

One can easily see that $\ker(\mathbf{A} \mathbf{W}) \subseteq \ker(\mathbf{W}^\top \mathbf{A} \mathbf{W})$. Let $\mathbf{v} \in \ker(\mathbf{W}^\top \mathbf{A} \mathbf{W})$, then we have

$$ \mathbf{v}^\top \mathbf{W}^\top \mathbf{A} \mathbf{W} \mathbf{v} = (\mathbf{W} \mathbf{v})^\top \mathbf{A} (\mathbf{W} \mathbf{v}) = 0, $$

and thus $\mathbf{W} \mathbf{v} \in \ker(\mathbf{A})$ since $\mathbf{A}$ is positive semi-definite. Consequently, (10) is feasible if and only if $\mathbf{W}^\top (\mathbf{A} \mathbf{w} + \mathbf{b}) \perp \mathbf{v}$ for all $\mathbf{v} \in \ker(\mathbf{A} \mathbf{W})$. The condition simplifies as $\mathbf{A}$ is symmetric,

$$ \mathbf{v}^\top \mathbf{W}^\top (\mathbf{A} \mathbf{w} + \mathbf{b}) = \mathbf{v}^\top \mathbf{W}^\top \mathbf{A}^\top \mathbf{w} + \mathbf{v}^\top \mathbf{W}^\top \mathbf{b} = (\mathbf{W} \mathbf{v})^\top \mathbf{b} = 0. $$

Therefore, (10) is feasible if and only if $\mathbf{b} \perp \mathbf{z}$ for all $\mathbf{z} \in \text{im}(\mathbf{W}) \cap \ker(\mathbf{A})$. This is equivalent to $\mathbf{b} \perp \text{span}(S) \cap \ker(\mathbf{A})$. $\square$

**Proposition 6.** QC-LP and QC-MNP satisfy the criteria of corrective steps in Algorithm 2.

*Proof.* For the QC-LP, if the LP in (9) is feasible, the solution coincides with the FCFW step. If the LP is infeasible, we perform a local pairwise step, which satisfies the criteria of a corrective step, as shown in Proposition 1.

For QC-MNP, if a solution of (8) exists and lies already in the $|S|$-simplex, the step is equivalent 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$ is convex and one moves towards the affine minimizer. If there exists no affine minimizer, we perform a local pairwise step. $\square$

**Proposition 7.** Let $\mathcal{X}$ be a polytope and $\mathcal{F}^*$ be the minimal face of $\mathcal{X}$ containing the optimal points $\mathcal{X}^*$. If $S \subset \mathcal{F}^*$, then $\text{argmin}_{x \in \text{aff}(S)} f(x) \neq \emptyset$. If additionally there exists $\mathbf{x}^* \in \mathcal{X}^*$ with $\mathbf{x}^* \in \text{conv}(S)$, then $\mathbf{x}^* \in \text{argmin}_{x \in \text{aff}(S)} f(x)$.

*Proof.* For contradiction, assume the problem $\text{min}_{x \in \text{aff}(S)} f(x)$ would be unbounded. Then there exists an $\tilde{\mathbf{x}} \in \text{aff}(S)$ such that $f(\tilde{\mathbf{x}}) < f^*$. If the optimal face $\mathcal{F}^*$ is a singleton, $S$ would be also a singleton yielding $\tilde{\mathbf{x}} \in \text{aff}(S) \subset \mathcal{X}$ which contradicts the minimality of $f^*$. If $\mathcal{F}^*$ is at least one
dimensional, there exists an $\mathbf{x}^* \in \text{relint}(\mathcal{F}^*)$ due to minimality and convexity of $\mathcal{F}^*$. Consequently, there exists a $\lambda \in (0, 1)$ with $\mathbf{y} = \lambda \tilde{\mathbf{x}} + (1 - \lambda)\mathbf{x}^* \in \mathcal{F}^* \subset \mathcal{X}$. Convexity yields then,

$$f(\mathbf{y}) = f(\lambda \tilde{\mathbf{x}} + (1 - \lambda)\mathbf{x}^*) \le \lambda f(\tilde{\mathbf{x}}) + (1 - \lambda)f(\mathbf{x}^*) < f^*,$$

which contradicts the minimality of $f^*$. Consequently, the problem is bounded below by $f^*$. If there exists an $\mathbf{x}^* \in \mathcal{X}^* \cap \text{conv}(S)$, then it is also a solution to the affine problem since $\mathbf{x}^* \in \text{aff}(S)$. $\square$

**Theorem 8.** Let $\mathcal{X}$ be a polytope and let $f$ be a convex, $L$-smooth function over $\mathcal{X}$. Assume that strict complementarity holds. Consider the sequence $\{\mathbf{x}_t\}_{t=0}^T$ generated by Algorithm 1 with Algorithm 4, Algorithm 5, or Algorithm 8. Then, there exists an iteration $\tilde{T}$ such that $\mathbf{x}_{\tilde{T}} \in \mathcal{X}^*$.

*Proof.* By Theorem 4 we know that there exists a $T_1$ such that $S_t \subset \mathcal{F}^*$ holds for all $t \ge T_1$. Let

$$\varepsilon = \min_{\substack{S \subset V(\mathcal{F}^*) \\ \text{conv}(S) \cap \mathcal{X}^* = \emptyset}} \text{dist}(\text{conv}(S), \mathcal{X}^*).$$

By Theorem 2 there exists a $T_2$ such that $\text{dist}(\mathbf{x}_t, \mathcal{X}^*) \le \varepsilon$ and thus $\text{dist}(\text{conv}(S_t), \mathcal{X}^*) < \varepsilon$ holds for all $t \ge T_2$. Consequently, we have $\text{conv}(S_t) \cap \mathcal{X}^* \ne \emptyset$ for all $t \ge T_2$. In total, we have $S_t \subset \mathcal{F}^*$ and $\text{conv}(S_t) \cap \mathcal{X}^* \ne \emptyset$ for all $t \ge \tilde{T} = \max(T_1, T_2)$.

By Proposition 7, we know there exists an $x^* \in \text{argmin}_{\mathbf{x} \in \text{aff}(S_t)} f(\mathbf{x}) \cap \mathcal{X}^* \subset \text{conv}(S_t)$ for all $t \ge \tilde{T}$. If CFW performs now a fully-corrective or a QC-LP step, we converge directly to an $x^* \in \mathcal{X}^*$. For QC-MNP, we need to use the implementation in Algorithm 8. Otherwise, we might pick an affine minimizer not in $\mathcal{X}$, see Lemma 13.

Finally, it remains to show that CFW performs a corrective step after at most some finite iterations after $\tilde{T}$. By Theorem 4 we know that $\mathbf{v}_t \in \mathcal{F}^*$ for all $t \ge \tilde{T}$. If $\mathbf{v}_t \in S_t$, then $\langle \nabla f(\mathbf{x}_t), \mathbf{v}_t \rangle = \langle \nabla f(\mathbf{x}_t), \mathbf{s}_t \rangle$ and thus

$$\langle \nabla f(\mathbf{x}_t), \mathbf{x}_t - \mathbf{v}_t \rangle \le \langle \nabla f(\mathbf{x}_t), \mathbf{a}_t - \mathbf{s}_t \rangle.$$

Therefore, CFW performs an FW step if $\mathbf{v}_t \notin S_t$. This yields that CFW could perform at most $|V(\mathcal{F}^*)| - |S_{\tilde{T}}|$ consecutive FW steps after $\tilde{T}$, before performing a corrective step. $\square$

## 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 9.

<caption>**Algorithm 9 Split Conditional Gradient (SCG)**</caption>

**Require:** Convex, smooth function $f$, weights $\{w_i\}_{i \in I} \subset (0, 1)$ with $\sum_{i \in I} w_i = 1$, starting point $\mathbf{x}_0 \in \mathcal{X}_0$
1: $\bar{\mathbf{x}}_0 \leftarrow \sum_{i \in I} w_i \mathbf{x}_0$
2: **for** $t = 0, 1, \dots$ **do**
3: &nbsp;&nbsp;&nbsp;&nbsp;Choose penalty parameter $\lambda_t > 0$
4: &nbsp;&nbsp;&nbsp;&nbsp;Choose step size $\gamma_t \in (0, 1)$
5: &nbsp;&nbsp;&nbsp;&nbsp;g_t \leftarrow \nabla f(\bar{\mathbf{x}}_t)$
6: &nbsp;&nbsp;&nbsp;&nbsp;**for** $i \in I$ **do**
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;v_t^i \leftarrow \text{argmin}_{v \in \mathcal{H}} \langle g_t + \lambda_t(\mathbf{x}_t^i - \bar{\mathbf{x}}_t), v \rangle$
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;\*x_t^i \leftarrow \*x_t^i + \gamma_t(\mathbf{v}_t^i - \mathbf{x}_t^i)$
9: &nbsp;&nbsp;&nbsp;&nbsp;**end for**
10: $\bar{\mathbf{x}}_{t+1} \leftarrow \sum_{i \in I} w_i \mathbf{x}_t^i$
11: **end for**

We prove the convergence rate of the SCG method stated in Theorem 9 in a more general setting, i.e., for arbitrary Hilbert spaces and any finite intersection. Let $\mathcal{H}$ be a real Hilbert space, let $\mathcal{H} = \mathcal{H}^m$ be the product space of $\mathcal{H}$. We denote the components of $\mathbf{x} \in \mathcal{H}$ as $\mathbf{x} = (\mathbf{x}^1, \dots, \mathbf{x}^m)$. Let $\mathcal{D} = \{\mathbf{x} \in \mathcal{H} \mid \mathbf{x}^1 = \mathbf{x}^2 = \dots = \mathbf{x}^m\}$ denote the diagonal space of $\mathcal{H}$. Furthermore, let $I = \{1, \dots, m\}$ and let $\{w_i\}_{i \in I}$ be a selection of weights such that $w_i > 0$ for all $i \in I$ and $\sum_{i \in I} w_i = 1$. The averaging operator is defined as $A: \mathcal{H} \to \mathcal{H}: \mathbf{x} \mapsto \sum_{i \in I} w_i \mathbf{x}^i$.
**Proposition 14.** [Woodstock and Pokutta, 2025, Proposition 2.13] Let $f: \mathcal{H} \to \mathbb{R}$, let $(\chi_i)_{i \in I}$ be a finite selection of non-empty, compact, and convex sets of $\mathcal{H}$. For every $\lambda \ge 0$, set $F_\lambda(\mathbf{x}) = f(\mathbf{Ax}) + \frac{\lambda}{2} \mathrm{dist}_{\mathcal{D}}^2(\mathbf{x})$. Suppose that $(\lambda_n)_{n \in \mathbb{N}} \nearrow \infty$. Then

$$ \lim_{t \to \infty} \left( \inf_{\mathbf{x} \in \mathcal{X}_{i \in I}} F_{\lambda_t}(\mathbf{x}) \right) = \inf_{\mathbf{x} \in \mathcal{X}_{i \in I}} \left( \lim_{t \to \infty} F_{\lambda_t}(\mathbf{x}) \right) = \inf_{\mathbf{x} \in \bigcap_{i \in I} \chi_i} f(\mathbf{x}). $$

**Theorem 15.** Let $f: \mathcal{H} \to \mathbb{R}$ be convex and L-smooth and let $(\chi_i)_{i \in I}$ be a finite selection of non-empty, compact, and convex sets of $\mathcal{H}$ with diameters $\{R_i\}_{i \in I}$ and $\bigcap_{i \in I} \chi_i \ne \emptyset$. For $\lambda \ge 0$, set $F_\lambda(\mathbf{x}) = f(\mathbf{Ax}) + \frac{\lambda}{2} \mathrm{dist}_{\mathcal{D}}^2(\mathbf{x})$, $\mathbf{x}_t^* \in \mathrm{argmin}_{\mathbf{x} \in \mathcal{H}} F_{\lambda_t}(\mathbf{x})$ and $H_t = F_{\lambda_t}(\mathbf{x}_t) - F_{\lambda_t}(\mathbf{x}_t^*)$. For $\lambda_t = \ln(t+2)$ and the step size $\gamma_t = \frac{2}{\sqrt{t+2} \ln(t+2)}$ for all $t \ge 0$, the iterates of SCG satisfy

$$ 0 \le H_t \le \frac{2R^2(L+1) + \sqrt{2}c_f}{\sqrt{t+2}} \quad (41) $$

for all $t \ge 0$, where $c_f \stackrel{\text{def}}{=} \max_{x,y \in \mathcal{X}_{i \in I}} \chi_i f(Ax) - f(Ay) < \infty$ and $R^2 \stackrel{\text{def}}{=} \sum_{i \in I} w_i R_i^2$.

Furthermore, we get that $\lim_{t \to \infty} F_{\lambda_t}(\mathbf{x}_t) = \inf_{\mathbf{x} \in \mathcal{X}_{i \in I}} \chi_i f(\mathbf{x})$ and $\lim_{t \to \infty} \mathrm{dist}_{\mathcal{D}}(\mathbf{x}_t) = 0$. In particular, any accumulation point $\tilde{\mathbf{x}}$ of the sequence $\{\mathbf{x}_t\}_{t \ge 0}$ lies in $\bigcap_{i \in I} \chi_i$ and satisfies $f(A\tilde{\mathbf{x}}) = \inf_{\mathbf{x} \in \mathcal{X}_{i \in I}} \chi_i f(\mathbf{x})$.

*Proof.* This proof is inspired by the proof of Woodstock and Pokutta [2025]. The key difference is to analyze the alternative auxiliary objective,

$$ \tilde{F}_{\lambda}(\mathbf{x}) = \frac{F_{\lambda}(\mathbf{x})}{\lambda} = \frac{f(A\mathbf{x})}{\lambda} + \frac{1}{2} \mathrm{dist}_{\mathcal{D}}^2(\mathbf{x}). $$

We will see that one can find smaller upper bounds on the primal gap $\tilde{H}_t = \tilde{F}_{\lambda_t}(\mathbf{x}_t) - \tilde{F}_{\lambda_t}(\mathbf{x}_t^*)$. However, even for $\lambda_t \tilde{H}_t = H_t$, we achieve faster rates of convergence. Note that

$$ \mathbf{x}_t^* \in \mathrm{argmin}_{\mathbf{x} \in \mathcal{X}_{i \in I}} F_{\lambda_t}(\mathbf{x}) = \mathrm{argmin}_{\mathbf{x} \in \mathcal{X}_{i \in I}} \tilde{F}_{\lambda_t}(\mathbf{x}), $$

since $F_{\lambda_t}$ and $\tilde{F}_{\lambda_t}$ only differ in scaling. Furthermore, the function $\tilde{F}_{\lambda_t}$ is $(\frac{L}{\lambda_t} + 1)$-smooth.

Analogous to Lemma 3.2 in Woodstock and Pokutta [2025], we first prove a bound on the primal gap $\tilde{H}_t$. Using smoothness, the FW update rule, the optimality of the FW vertex $\mathbf{v}_t$, and convexity, we get

$$ \begin{aligned} & \tilde{F}_{\lambda_t}(\mathbf{x}_{t+1}) - \tilde{F}_{\lambda_t}(\mathbf{x}_t) \\ & \le \langle \nabla \tilde{F}_{\lambda_t}(\mathbf{x}_t), \mathbf{x}_{t+1} - \mathbf{x}_t \rangle + \frac{\frac{L}{\lambda_t} + 1}{2} \|\mathbf{x}_{t+1} - \mathbf{x}_t\|^2 \\ & = \gamma_t \langle \nabla \tilde{F}_{\lambda_t}(\mathbf{x}_t), \mathbf{v}_t - \mathbf{x}_t \rangle + \frac{\frac{L}{\lambda_t} + 1}{2} \gamma_t^2 \|\mathbf{v}_t - \mathbf{x}_t\|^2 \\ & \le \gamma_t \langle \nabla \tilde{F}_{\lambda_t}(\mathbf{x}_t), \mathbf{x}_t^* - \mathbf{x}_t \rangle + \frac{\frac{L}{\lambda_t} + 1}{2} \gamma_t^2 R^2 \\ & \le \gamma_t (\tilde{F}(\mathbf{x}_t^*) - \tilde{F}_{\lambda_t}(\mathbf{x}_t)) + \gamma_t^2 R^2 \frac{\frac{L}{\lambda_t} + 1}{2} \end{aligned} $$

where $R^2$ is an upper bound on $\|\mathbf{x} - \mathbf{y}\|^2$ for all $\mathbf{x}, \mathbf{y} \in \bigcap_{i \in I} \chi_i$, see Woodstock and Pokutta [2025, Lemma 3.1].

Adding $\tilde{F}_{\lambda_t}(\mathbf{x}_t) - \tilde{F}_{\lambda_t}(\mathbf{x}_t^*)$ to both sides leads to

$$ \tilde{F}_{\lambda_t}(\mathbf{x}_{t+1}) - \tilde{F}_{\lambda_t}(\mathbf{x}_t^*) \le (1 - \gamma_t) \underbrace{(\tilde{F}_{\lambda_t}(\mathbf{x}_t) - \tilde{F}_{\lambda_t}(\mathbf{x}_t^*))}_{\tilde{H}_t} + \gamma_t^2 R^2 \frac{\frac{L}{\lambda_t} + 1}{2}. $$
Together with the definition of $\tilde{F}_{\lambda_t}$ and the optimality of $\mathbf{x}_t^*$ yields

$$
\begin{align*}
\tilde{H}_{t+1} &= \tilde{F}_{\lambda_{t+1}}(\mathbf{x}_{t+1}) - \tilde{F}_{\lambda_{t+1}}(\mathbf{x}_{t+1}^*) \\
&= \tilde{F}_{\lambda_t}(\mathbf{x}_{t+1}) - \tilde{F}_{\lambda_t}(\mathbf{x}_{t+1}^*) + \left(\frac{1}{\lambda_t} - \frac{1}{\lambda_t}\right) (f(A\mathbf{x}_{t+1}) - f(A\mathbf{x}_{t+1}^*)) \\
&= \tilde{F}_{\lambda_t}(\mathbf{x}_{t+1}) - \tilde{F}_{\lambda_t}(\mathbf{x}_{t+1}^*) + \left(\frac{1}{\lambda_t} - \frac{1}{\lambda_{t+1}}\right) (f(A\mathbf{x}_{t+1}^*) - f(A\mathbf{x}_{t+1})) \\
&\le \tilde{F}_{\lambda_t}(\mathbf{x}_{t+1}) - \tilde{F}_{\lambda_t}(\mathbf{x}_{t+1}^*) + c_f \left(\frac{1}{\lambda_t} - \frac{1}{\lambda_{t+1}}\right) \\
&\le \tilde{F}_{\lambda_t}(\mathbf{x}_{t+1}) - \tilde{F}_{\lambda_t}(\mathbf{x}_t^*) + c_f \left(\frac{1}{\lambda_t} - \frac{1}{\lambda_{t+1}}\right) \\
&\le (1 - \gamma_t) \tilde{H}_t + \gamma_t^2 R^2 \frac{\frac{L}{\lambda_t} + 1}{2} + c_f \left(\frac{1}{\lambda_t} - \frac{1}{\lambda_{t+1}}\right), \tag{42}
\end{align*}
$$

where $c_f = \max_{\mathbf{x},y \in \chi_{i \in I}} \chi_i (f(\mathbf{Ax}) - f(\mathbf{Ay})) < \infty$. The result in (42) is analogous to the result in Lemma 3.2 in Woodstock and Pokutta [2025]. However, it involves a difference of inverse values of $\lambda_t$, which will be the key difference here. This allows us to use a larger step size $\gamma_t = \frac{2}{\sqrt{t+2 \ln(t+2)}}$ for the SCG method.

For the given $\lambda_t = \ln(t+2)$ and by using $\ln(x) \le x-1$, we obtain

$$
\frac{1}{\lambda_t} - \frac{1}{\lambda_{t+1}} \le \frac{\lambda_{t+1} - \lambda_t}{\lambda_t^2} = \frac{\ln\left(\frac{t+3}{t+2}\right)}{\ln(t+2)^2} \le \frac{1}{(t+2)\ln(t+2)^2}. \quad (43)
$$

We can now show by induction that

$$
0 \le \tilde{H}_t \le \tilde{G}_t \stackrel{\text{def}}{=} \frac{2R^2(L+1) + \sqrt{2}c_f}{\sqrt{t+2}\ln(t+2)}. \quad (44)
$$

For $t=0$ we have

$$
\begin{align*}
\tilde{H}_0 &= \tilde{F}_{\lambda_0}(\mathbf{x}_0) - \tilde{F}_{\lambda_0}(\mathbf{x}_0^*) \\
&= \frac{f(A\mathbf{x}_0) - f(A\mathbf{x}_0^*)}{\lambda_0} + \frac{\mathrm{dist}_D^2(\mathbf{x}_0) - \mathrm{dist}_D^2(\mathbf{x}_0^*)}{2} \\
&\le \frac{c_f}{\ln(2)} + \frac{R^2}{2} \\
&\le \frac{2R^2(L+1) + \sqrt{2}c_f}{\sqrt{2}\ln(2)} = \tilde{G}_0.
\end{align*}
$$

The induction hypothesis together with (42) and (43) yields

$$
\begin{align*}
\tilde{H}_{t+1} &\le (1 - \gamma_t) \tilde{H}_t + \gamma_t^2 R^2 \frac{\left(\frac{L}{\lambda_t} + 1\right)}{2} + c_f \left(\frac{1}{\lambda_t} - \frac{1}{\lambda_{t+1}}\right) \\
&\le \frac{\sqrt{t+2} \ln(t+2) - 2}{\sqrt{t+2} \ln(t+2)} \tilde{G}_t + \frac{2R^2(L+1)}{(t+2) \ln(t+2)^2} + \frac{\sqrt{2}c_f}{(t+2) \ln(t+2)^2} \\
&= \frac{\sqrt{t+2} \ln(t+2) - 2 + 1}{(t+2) \ln(t+2)^2} \cdot (2R^2(L+1) + \sqrt{2}c_f) \\
&\le \frac{1}{\sqrt{t+3} \ln(t+3)} \cdot (2R^2(L+1) + \sqrt{2}c_f) = \tilde{G}_{t+1}.
\end{align*}
$$

To finish the induction, it is left to show that

$$
\frac{\sqrt{t+2} \ln(t+2) - 1}{(t+2) \ln(t+2)^2} \le \frac{1}{\sqrt{t+3} \ln(t+3)}.
$$
Consider

$$
\begin{align*}
& \sqrt{t+2} \ln(t+2) - \sqrt{t+1} \ln(t+1) \\
= & \ln \left( \frac{(t+2)^{\sqrt{t+2}}}{(t+1)^{\sqrt{t+1}}} \right) \\
= & \ln \left( \left( \frac{t+2}{t+1} \right)^{\sqrt{t+2}} \cdot \frac{1}{(t+1)^{\sqrt{t+2}-\sqrt{t+1}}} \right) \\
= & \sqrt{t+2} \ln \left( 1 + \frac{1}{t+1} \right) - (\sqrt{t+2} - \sqrt{t+1}) \ln(t+1) \\
\le & \frac{\sqrt{t+2}}{t+1} \stackrel{\text{def}}{=} \phi(t).
\end{align*}
$$

The function $\phi(t)$ is monotonically decreasing and satisfies $\phi(t) \le 1$ for $t \ge 1$. Thus, we have

$$
\sqrt{t+2} \ln(t+2) - 1 \le \sqrt{t+1} \ln(t+1), \quad (45)
$$

for all $t \ge 1$. One can even see that (45) holds for $t = 0$. It remains to show that

$$
\sqrt{t+1} \ln(t+1) \sqrt{t+3} \ln(t+3) \le (t+2) \ln(t+2)^2.
$$

One can easily see that

$$
\sqrt{t+1}\sqrt{t+3} = \sqrt{t^2+4t+3} \le \sqrt{t^2+4t+4} = t+2.
$$

Furthermore, using twice the concavity of ln yields

$$
\begin{align*}
\ln(\ln(t+1) \cdot \ln(t+3)) &= \ln(\ln(t+1)) + \ln(\ln(t+3)) \\
&\le 2 \ln \left( \frac{\ln(t+1)}{2} + \frac{\ln(t+3)}{2} \right) \\
&\le 2 \ln \left( \ln \left( \frac{t+1}{2} + \frac{t+3}{2} \right) \right) \\
&= 2 \ln(\ln(t+2)) = \ln(\ln(t+2)^2),
\end{align*}
$$

and thus

$$
\ln(t+1) \cdot \ln(t+3) \le \ln(t+2)^2.
$$

This concludes the induction. Using $H_t = \lambda_t \tilde{H}_t$ yields the proposed upper boundary

$$
H_t = \lambda_t \tilde{H}_t \le \frac{2R^2(L+1) + \sqrt{2}c_f}{\sqrt{t+2}} = \mathcal{O}\left(\frac{1}{\sqrt{t}}\right).
$$

Together with Proposition 14 we get that $\lim_{t \to \infty} F_{\lambda_t}(\mathbf{x}_t)$ exists and that

$$
\lim_{t \to \infty} F_{\lambda_t}(\mathbf{x}_t) = \lim_{t \to \infty} F_{\lambda_t}(\mathbf{x}_t^*) = \inf_{\mathbf{x} \in \mathcal{X}_{i \in I}} f(\mathbf{x}).
$$

As $\lambda_t \to \infty$, we have $\text{dist}_D^2(\mathbf{x}_t) \to 0$. Thus, every accumulation point $\tilde{\mathbf{x}}$ lies in the diagonal space $\mathcal{D}$ and therefore $A\tilde{\mathbf{x}} \in \bigcap_{i \in I} \mathcal{X}_i$. Considering a subsequence $(t_k)_{k \in \mathbb{N}}$ we get

$$
\inf_{\mathbf{x} \in \bigcap_{i \in I} \mathcal{X}_i} f(\mathbf{x}) \le f(A\tilde{\mathbf{x}}) = \lim_{k \to \infty} f(A\mathbf{x}_{t_k}) \le \lim_{k \to \infty} F_{\lambda_{t_k}}(\mathbf{x}_{t_k}) = \inf_{\mathbf{x} \in \bigcap_{i \in I} \mathcal{X}_i} f(\mathbf{x}).
$$

□

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 a smooth strongly convex function $f$ with Lipschitz continuous Hessian $\nabla^2 f$ over a polytope $\mathcal{X}$. For each iteration $t$, a quadratic approximation $\hat{f}_t$ is minimized over the polytope $\mathcal{X}$ using a projection-free method. Minimizing such quadratic forms over a polytope amounts to a *Projected Variable-Metric* (PVM) algorithm Nesterov [2018], Ben-Tal and Nemirovski [Spring 2023] (we state PVM in Algorithm 11).

To do so, a Hessian oracle $\Omega$ yields for each iteration $t$ an approximation $\mathbf{H}_t$ of the Hessian $\nabla^2 f(\mathbf{x}_t)$ at the current iterate $\mathbf{x}_t$. The quadratic approximation<fnref n="1" /> $\hat{f}_t(\mathbf{x}) = \langle \nabla f(\mathbf{x}_t), \mathbf{x} - \mathbf{x}_t \rangle + \frac{1}{2} \|\mathbf{x} - \mathbf{x}_t\|_{\mathbf{H}_t}^2$ is then built and minimized inexactely using a 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 $\varepsilon_t$. This threshold involves the computation of a lower bound $\text{lb}(\mathbf{x}_t) \le f(\mathbf{x}_t) - f^*$ on the 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), or *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, we present the pseudo-code of the SOCGS algorithm. The statement of Algorithm 10 is directly adapted from Carderera and Pokutta [2020]. Compared to its original statement, we distinguish the OCS from the *Inner Corrective Steps* (ICS), or *inner steps* for short, used inside the Inexact PVM step.

<caption>**Algorithm 10** Second-Order Conditional Gradient Sliding (SOCGS)</caption>

**Require:** Point $\mathbf{x} \in \mathcal{X}$
**Return:** Point $\mathbf{x}_T \in \mathcal{X}$
1: $\mathbf{x}_0 \leftarrow \operatorname*{argmin}_{\mathbf{v} \in \mathcal{X}} \langle \nabla f(\mathbf{x}), \mathbf{v} \rangle$, $S_0 \leftarrow \{\mathbf{x}_0\}$, $\lambda_0(\mathbf{x}_0) \leftarrow 1$
2: $\mathbf{x}_0^{\text{OCS}} \leftarrow \mathbf{x}_0$, $S_0^{\text{OCS}} \leftarrow S_0$, $\lambda_0^{\text{OCS}}(\mathbf{x}_0) \leftarrow 1$
3: **for** $t = 0$ to $T-1$ **do**
4: &nbsp;&nbsp;&nbsp;&nbsp; $\mathbf{x}_{t+1}^{\text{OCS}}, S_{t+1}^{\text{OCS}}, \lambda_{t+1}^{\text{OCS}} \leftarrow \text{OCS}(\nabla f(\mathbf{x}_t), \mathbf{x}_t^{\text{OCS}}, S_t^{\text{OCS}}, \lambda_t^{\text{OCS}})$ ▷ Outer Corrective Step
5: &nbsp;&nbsp;&nbsp;&nbsp; $\mathbf{H}_t \leftarrow \Omega(\mathbf{x}_t)$ ▷ Call Hessian oracle
6: &nbsp;&nbsp;&nbsp;&nbsp; $\hat{f}_t(\mathbf{x}) \leftarrow \langle \nabla f(\mathbf{x}_t), \mathbf{x} - \mathbf{x}_t \rangle + \frac{1}{2} \|\mathbf{x} - \mathbf{x}_t\|_{\mathbf{H}_t}^2$ ▷ Build quadratic approximation
7: &nbsp;&nbsp;&nbsp;&nbsp; $\varepsilon_t \leftarrow \left( \frac{\text{lb}(\mathbf{x}_t)}{\|\nabla f(\mathbf{x}_t)\|} \right)^4$ ▷ Compute Inexact PVM step
8: &nbsp;&nbsp;&nbsp;&nbsp; $\tilde{\mathbf{x}}_{t+1}^0 \leftarrow \mathbf{x}_t$, $\tilde{S}_{t+1}^0 \leftarrow S_t$, $\tilde{\lambda}_{t+1}^0 \leftarrow \lambda_t$, $h \leftarrow 0$
9: **while** $\max_{\mathbf{v} \in \mathcal{X}} \langle \nabla \hat{f}_t(\tilde{\mathbf{x}}_{t+1}^h), \tilde{\mathbf{x}}_{t+1}^h - \mathbf{v} \rangle \ge \varepsilon_t$ **do**
10: &nbsp;&nbsp;&nbsp;&nbsp; $\tilde{\mathbf{x}}_{t+1}^{h+1}, \tilde{S}_{t+1}^{h+1}, \tilde{\lambda}_{t+1}^{h+1} \leftarrow \text{ICS}(\nabla \hat{f}_t(\tilde{\mathbf{x}}_{t+1}^h), \tilde{\mathbf{x}}_{t+1}^h, \tilde{S}_{t+1}^h, \tilde{\lambda}_{t+1}^h)$ ▷ Inner Corrective Step
11: &nbsp;&nbsp;&nbsp;&nbsp; $h \leftarrow h+1$
12: **end while**
13: $\mathbf{x}_{t+1}^{\text{PVM}} \leftarrow \tilde{\mathbf{x}}_{t+1}^h$, $S_{t+1}^{\text{PVM}} \leftarrow \tilde{S}_{t+1}^h$, $\lambda_{t+1}^{\text{PVM}} \leftarrow \tilde{\lambda}_{t+1}^h$
14: **if** $f(\mathbf{x}_{t+1}^{\text{PVM}}) \le f(\mathbf{x}_{t+1}^{\text{OCS}})$ **then**
15: &nbsp;&nbsp;&nbsp;&nbsp; $\mathbf{x}_{t+1} \leftarrow \mathbf{x}_{t+1}^{\text{PVM}}, S_{t+1} \leftarrow S_{t+1}^{\text{PVM}}, \lambda_{t+1} \leftarrow \lambda_{t+1}^{\text{PVM}}$ ▷ Choose Inexact PVM step
16: **else**
17: &nbsp;&nbsp;&nbsp;&nbsp; $\mathbf{x}_{t+1} \leftarrow \mathbf{x}_{t+1}^{\text{OCS}}, S_{t+1} \leftarrow S_{t+1}^{\text{OCS}}, \lambda_{t+1} \leftarrow \lambda_{t+1}^{\text{OCS}}$ ▷ Choose Outer Corrective Step
18: **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 Sun and Tran-Dinh [2019, Definition 2]. Let $f: \mathbb{R}^n \to \mathbb{R} \cup \{+\infty\}$ be a convex function, with its effective domain $\text{dom}(f) \stackrel{\text{def}}{=} \{\mathbf{x} \in \mathbb{R}^n | f(\mathbf{x}) < +\infty\}$. We assume that $\text{dom}(f)$ is an open set and that the

<footnote n="1">¹The norm $\|\mathbf{x} - \mathbf{y}\|_{\mathbf{H}} = \|\mathbf{H}^{1/2}(\mathbf{x} - \mathbf{y})\|$ is induced by a symmetric positive definite matrix $\mathbf{H}$.</footnote>
function $f$ is three times continuously differentiable on $\text{dom}(f)$ with third order derivative $\nabla^3 f$. The function $f$ is a $(M, \nu)$-generalized self-concordant function of order $\nu > 0$ and constant $M \ge 0$ if

$$ \left| \langle \nabla^3 f(\mathbf{x})_v \mathbf{u}, \mathbf{u} \rangle \right| \le M \|\mathbf{u}\|^2_{\nabla^2 f(\mathbf{x})} \|\mathbf{v}\|_{\nabla^2 f(\mathbf{x})}^{\nu-2} \|\mathbf{v}\|^{3-\nu}, \quad \forall \mathbf{x} \in \text{dom}(f), \forall \mathbf{u}, \mathbf{v} \in \mathbb{R}^n. \quad (46) $$

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, \nu)$-generalized self-concordant function $f$, then for $\nu \ge 2$, we have that:

$$ f(\mathbf{y}) - f(\mathbf{x}) - \langle \nabla f(\mathbf{x}), \mathbf{y} - \mathbf{x} \rangle \le \omega_{\nu}(d_{\nu}(\mathbf{x}, \mathbf{y})) \|\mathbf{y} - \mathbf{x}\|_{\nabla^2 f(\mathbf{x})}^2, \quad (47) $$

$$ f(\mathbf{y}) - f(\mathbf{x}) - \langle \nabla f(\mathbf{x}), \mathbf{y} - \mathbf{x} \rangle \ge \omega_{\nu}(-d_{\nu}(\mathbf{x}, \mathbf{y})) \|\mathbf{y} - \mathbf{x}\|_{\nabla^2 f(\mathbf{x})}^2, \quad (48) $$

where (47) holds if $d_{\nu}(\mathbf{x}, \mathbf{y}) < 1$ for $\nu > 2$, and we have that,

$$ d_{\nu}(\mathbf{x}, \mathbf{y}) \stackrel{\text{def}}{=} \begin{cases} M \|\mathbf{y} - \mathbf{x}\| & \text{if } \nu = 2 \\ \left(\frac{\nu}{2} - 1\right) M \|\mathbf{y} - \mathbf{x}\|^{3-\nu} \|\mathbf{y} - \mathbf{x}\|_{\nabla^2 f(\mathbf{x})}^{\nu-2} & \text{if } \nu > 2, \end{cases} \quad (49) $$

where:

$$ \omega_{\nu}(\tau) \stackrel{\text{def}}{=} \begin{cases} \frac{e^{\tau} - \tau - 1}{\tau^2} & \text{if } \nu = 2 \\ \frac{-\tau - \ln(1-\tau)}{(1-\tau)\ln(1-\tau) + \tau} & \text{if } \nu = 3 \\ \frac{\tau^2}{(\tau - 2)(4-\nu)} \frac{1}{\tau} \left[ \frac{\nu-2}{2(3-\nu)\tau} \left( (1-\tau)^{\frac{2(3-\nu)}{2-\nu}} - 1 \right) - 1 \right] & \text{otherwise.} \end{cases} \quad (50) $$

**Lemma 17.** [Karimireddy et al., 2018, Lemma 9] Given a convex set $\mathcal{X}$ and $\mathbf{H} \in \mathbb{S}_{++}^n$, and two scalars $\alpha > 0, \beta > 0$ such that $\alpha\beta \ge 1$, we have that:

$$ \min_{\mathbf{x} \in \mathcal{X}} \langle \nabla f(\mathbf{x}_k), \mathbf{x} - \mathbf{x}_k \rangle + \frac{\alpha}{2} \|\mathbf{x} - \mathbf{x}_k\|_{\mathbf{H}}^2 \le \frac{1}{\alpha\beta} \min_{\mathbf{x} \in \mathcal{X}} \langle \nabla f(\mathbf{x}_k), \mathbf{x} - \mathbf{x}_k \rangle + \frac{1}{2\beta} \|\mathbf{x} - \mathbf{x}_k\|_{\mathbf{H}}^2. $$

**Lemma 18.** [Carderera and Pokutta, 2020, Lemma A.6] Given two matrices $\mathbf{P}, \mathbf{Q} \in \mathbb{S}_{++}^n$, then we have for all $\mathbf{v} \in \mathbb{R}^n$:

$$ \frac{1}{\eta} \|\mathbf{v}\|_{\mathbf{P}}^2 \le \|\mathbf{v}\|_{\mathbf{Q}}^2 \le \eta \|\mathbf{v}\|_{\mathbf{P}}^2, \quad (51) $$

$$ \text{with } \eta = \max \{ \lambda_{\max}(\mathbf{P}^{-1}\mathbf{Q}), \lambda_{\max}(\mathbf{Q}^{-1}\mathbf{P}) \} \ge 1. $$

We now present the PVM algorithm in Algorithm 11 from Carderera and Pokutta [2020] and its convergence for generalized self-concordant functions in Theorem 19.

**Algorithm 11 Projected Variable-Metric (PVM) algorithm**

**Require:** Point $\mathbf{x}_0 \in \mathcal{X}$, step sizes $\{\gamma_0, \dots, \gamma_K\}$

**Return:** Point $\mathbf{x}_K \in \mathcal{X}$

1: **for** $k = 0$ to $K-1$ **do**

2: &nbsp;&nbsp;&nbsp;&nbsp; $\hat{\mathbf{x}} \leftarrow \operatorname*{argmin}_{\mathbf{x} \in \mathcal{X}} \left( f(\mathbf{x}_k) + \langle \nabla f(\mathbf{x}_k), \mathbf{x} - \mathbf{x}_k \rangle + \frac{1}{2} \|\mathbf{x} - \mathbf{x}_k\|_{\mathbf{H}_k}^2 \right)$

3: &nbsp;&nbsp;&nbsp;&nbsp; $\mathbf{x}_{k+1} \leftarrow \mathbf{x}_k + \gamma_k (\hat{\mathbf{x}} - \mathbf{x}_k)$

4: **end for**

**Theorem 19 (Global convergence of the Projected Variable-Metric algorithm on generalized self-concordant functions).** Let $\mathcal{X}$ be a compact convex set of diameter $D$ and $f$ be a $(M, \nu)$-generalized self-concordant function with $\nu \ge 2$ such that $f$ is strongly convex on $\text{dom}(f) \cap \mathcal{X}$ if $\nu = 3$. Given a starting point $\mathbf{x}_0 \in \mathcal{X} \cap \text{dom}(f)$, the Projected Variable-Metric algorithm (Algorithm 11) with a step size $\gamma_k$ guarantees for all $k \ge 0$:

$$ f(\mathbf{x}_{k+1}) - f(\mathbf{x}^*) \le \left(1 - \frac{\omega_{\nu}(1/2)\gamma_k^2}{\eta_k}\right) (f(\mathbf{x}_k) - f(\mathbf{x}^*)) $$
where the parameter $\eta_k$ measures how well $\mathbf{H}_k$ approximates $\nabla^2 f(\mathbf{x}_k)$ in the sense of Lemma 18, and $\gamma_k$ is such that

$$ \gamma_k \le \min \left\{ \frac{1}{2\eta_k}, \eta_k \right\} \frac{1}{\omega_\nu(\frac{1}{2})} \qquad (52) $$

and additionally,

$$ \gamma_k \le \frac{1}{2\eta_k\omega_\nu(MD)} \quad \text{if } \nu = 2 \qquad (53) $$

$$ \gamma_k \le \Gamma, \quad \text{if } \nu > 2 \qquad (54) $$

where $\Gamma$ is the maximum value, such that:

$$ \|\bar{\mathbf{x}} - \mathbf{x}_k\|_{\mathbf{H}_k} \le \frac{\mu_0^{3-\nu}}{\eta_k M(2\nu - 1)} \qquad (55) $$

$$ \begin{array}{ll} \text{where } \bar{\mathbf{x}} = \underset{\mathbf{x}}{\operatorname{argmin}} & \langle \nabla f(\mathbf{x}_k), \mathbf{x} - \mathbf{x}_k \rangle + \frac{1}{2\Gamma} \|\mathbf{x} - \mathbf{x}_k\|_{\mathbf{H}_k}^2, \\ \text{with } \mu_0 = & \begin{cases} 1 & \text{if } \nu = 3 \\ \min_{\mathbf{d} \in \mathbb{R}^n, \|\mathbf{d}\|_2=1} \|\mathbf{d}\|_{\nabla^2 f(\mathbf{x})} & \text{otherwise.} \end{cases} \end{array} $$

*Proof.* The iterate $\mathbf{x}_{k+1}$ can be rewritten as:

$$ \mathbf{x}_{k+1} = \underset{\mathbf{x} \in (1-\gamma_k)\mathbf{x}_k + \gamma_k \mathcal{X}}{\operatorname{argmin}} \langle \nabla f(\mathbf{x}_k), \mathbf{x} - \mathbf{x}_k \rangle + \frac{1}{2\gamma_k} \|\mathbf{x} - \mathbf{x}_k\|_{\mathbf{H}_k}^2. \qquad (56) $$

Using $(M, \nu)$-generalized self-concordance of $f$ and Proposition 16, we can write:

$$ f(\mathbf{x}_{k+1}) - f(\mathbf{x}_k) \le \langle \nabla f(\mathbf{x}_k), \mathbf{x}_{k+1} - \mathbf{x}_k \rangle + \omega_\nu(d_\nu(\mathbf{x}_k, \mathbf{x}_{k+1})) \|\mathbf{x}_{k+1} - \mathbf{x}_k\|_{\nabla^2 f(\mathbf{x}_k)}^2 \qquad (57) $$

$$ \le \langle \nabla f(\mathbf{x}_k), \mathbf{x}_{k+1} - \mathbf{x}_k \rangle + \eta_k \omega_\nu(d_\nu(\mathbf{x}_k, \mathbf{x}_{k+1})) \|\mathbf{x}_{k+1} - \mathbf{x}_k\|_{\mathbf{H}_k}^2, \qquad (58) $$

where (58) follows from the $\eta_k$ approximation of the Hessian by $\mathbf{H}_k$. If $\nu = 2$, we have from (53) that

$$ \gamma_k \le \frac{1}{2\eta_k\omega_\nu(MD)} \le \frac{1}{2\eta_k\omega_\nu(d_\nu(\mathbf{x}_k, \mathbf{x}_{k+1}))}. $$

Note that we use the fact that $\omega_\nu(a) \le \omega_\nu(1/2)$ hold for all $a \le 1/2$, which we will also use for other $\nu$ values. If $\nu > 2$, using the upper bound assumption on $\gamma_k$ (54) and the associated upper bound on the $\mathbf{H}_k$-norm (55), we can ensure that:

$$ \begin{aligned} d_\nu(\mathbf{x}_{k+1}, \mathbf{x}_k) &= \left(\frac{\nu}{2} - 1\right) M \|\mathbf{x}_{k+1} - \mathbf{x}_k\|_2^{3-\nu} \|\mathbf{x}_{k+1} - \mathbf{x}_k\|_{\nabla f(\mathbf{x}_k)}^{\nu-2} \\ &\le \left(\frac{\nu}{2} - 1\right) M \frac{1}{\mu_0^{3-\nu}} \|\mathbf{x}_{k+1} - \mathbf{x}_k\|_{\nabla f(\mathbf{x}_k)} \\ &\le \left(\frac{\nu}{2} - 1\right) M \frac{\eta_k}{\mu_0^{3-\nu}} \|\mathbf{x}_{k+1} - \mathbf{x}_k\|_{\mathbf{H}_k} \le \frac{1}{2}, \end{aligned} $$

where the last inequality uses the maximum distance in local norm between $\mathbf{x}_k$ and $\mathbf{x}_{k+1}$ as a solution to the subproblem. Note that $\Gamma > 0$ can be ensured, among other means, by the fact that $\nabla f(\mathbf{x}_k)$ is bounded on any finite sublevel set even if the function does not possess a global finite Lipschitz smoothness constant. These two cases ensure that $\frac{1}{2\gamma_k} \ge \eta_k \omega_\nu(d_\nu(\mathbf{x}_k, \mathbf{x}_{k+1}))$. Continuing the chain of inequalities:

$$ f(\mathbf{x}_{k+1}) - f(\mathbf{x}_k) \le \langle \nabla f(\mathbf{x}_k), \mathbf{x}_{k+1} - \mathbf{x}_k \rangle + \eta_k \omega_\nu(d_\nu(\mathbf{x}_k, \mathbf{x}_{k+1})) \|\mathbf{x}_{k+1} - \mathbf{x}_k\|_{\mathbf{H}_k}^2 \qquad (59) $$

$$ \le \langle \nabla f(\mathbf{x}_k), \mathbf{x}_{k+1} - \mathbf{x}_k \rangle + \frac{1}{2\gamma_k} \|\mathbf{x}_{k+1} - \mathbf{x}_k\|_{\mathbf{H}_k}^2 \qquad (60) $$

$$ = \min_{\mathbf{x} \in (1-\gamma_k)\mathbf{x}_k + \gamma_k \mathcal{X}} \left( \langle \nabla f(\mathbf{x}_k), \mathbf{x} - \mathbf{x}_k \rangle + \frac{1}{2\gamma_k} \|\mathbf{x} - \mathbf{x}_k\|_{\mathbf{H}_k}^2 \right), \qquad (61) $$
where (60) follows from the upper bound on $\gamma_k$ from (52). (61) directly follows from the definition of $\mathbf{x}_{k+1}$ in (56).

$$f(\mathbf{x}_{k+1}) - f(\mathbf{x}_k) \leq \min_{\mathbf{x} \in (1-\gamma_k)\mathbf{x}_k + \gamma_k \mathcal{X}} \left( \langle \nabla f(\mathbf{x}_k), \mathbf{x} - \mathbf{x}_k \rangle + \frac{1}{2\gamma_k} \|\mathbf{x} - \mathbf{x}_k\|_{\mathbf{H}_k}^2 \right) \quad (62)$$

$$\leq \frac{\omega_{\nu}(-d_{\nu}(\mathbf{x}_k, \mathbf{x}^*))\gamma_k}{\eta_k} \min_{\mathbf{x} \in (1-\gamma_k)\mathbf{x}_k + \gamma_k \mathcal{X}} \left( \langle \nabla f(\mathbf{x}_k), \mathbf{x} - \mathbf{x}_k \rangle + \frac{\omega_{\nu}(-d_{\nu}(\mathbf{x}_k, \mathbf{x}^*))}{2\eta_k} \|\mathbf{x} - \mathbf{x}_k\|_{\mathbf{H}_k}^2 \right) \quad (63)$$

$$\leq \frac{\omega_{\nu}(-d_{\nu}(\mathbf{x}_k, \mathbf{x}^*))\gamma_k}{\eta_k} \min_{\mathbf{x} \in (1-\gamma_k)\mathbf{x}_k + \gamma_k \mathcal{X}} \left( \langle \nabla f(\mathbf{x}_k), \mathbf{x} - \mathbf{x}_k \rangle + \omega_{\nu}(-d_{\nu}(\mathbf{x}_k, \mathbf{x}^*)) \|\mathbf{x} - \mathbf{x}_k\|_{\nabla^2 f(\mathbf{x}_k)}^2 \right) \quad (64)$$

$$\leq \frac{\omega_{\nu}(-d_{\nu}(\mathbf{x}_k, \mathbf{x}^*))\gamma_k^2}{\eta_k} \left( \langle \nabla f(\mathbf{x}_k), \mathbf{x}^* - \mathbf{x}_k \rangle + \omega_{\nu}(-d_{\nu}(\mathbf{x}_k, \mathbf{x}^*))\gamma_k \|\mathbf{x}^* - \mathbf{x}_k\|_{\nabla^2 f(\mathbf{x}_k)}^2 \right) \quad (65)$$

$$\leq \frac{\omega_{\nu}(-d_{\nu}(\mathbf{x}_k, \mathbf{x}^*))\gamma_k^2}{\eta_k} \left( \langle \nabla f(\mathbf{x}_k), \mathbf{x}^* - \mathbf{x}_k \rangle + \omega_{\nu}(-d_{\nu}(\mathbf{x}_k, \mathbf{x}^*)) \|\mathbf{x}^* - \mathbf{x}_k\|_{\nabla^2 f(\mathbf{x}_k)}^2 \right) \quad (66)$$

$$\leq \frac{\omega_{\nu}(1/2)\gamma_k^2}{\eta_k} (f(\mathbf{x}^*) - f(\mathbf{x}_k)). \quad (67)$$

We obtain (63) by applying Lemma 17 with $\alpha = 1/\gamma_k$ and $\beta = \eta_k/\omega_{\nu}(-d_{\nu}(\mathbf{x}_k, \mathbf{x}^*))$. Note that the lemma requirements impose $\gamma_k \leq \eta_k/\omega_{\nu}(-d_{\nu}(\mathbf{x}_k, \mathbf{x}^*))$, which is ensured by (52) by monotonicity of $\omega_{\nu}$. (64) follows from the Hessian-induced norm approximation with $\mathbf{H}_k$, i.e., $1/\eta_k \|\mathbf{x} - \mathbf{x}_k\|_{\mathbf{H}_k}^2 \leq \|\mathbf{x} - \mathbf{x}_k\|_{\nabla^2 f(\mathbf{x}_k)}^2$ following Lemma 18. (65) follows from setting in $\mathbf{x} = (1 - \gamma_k)\mathbf{x}_k + \gamma_k \mathbf{x}^*$ into (64) (since $\mathbf{x}^* \in \mathcal{X}$). We obtain (66) by considering that $\gamma_k \leq 1$, since $\mathbf{x}_{k+1}$ is constructed as a convex combination of $\tilde{\mathbf{x}}$ and $\mathbf{x}_k$. Finally, (67) follows from (48) and from the fact that $\omega_{\nu}(a) \leq \omega_{\nu}(1/2)$ hold for all $a \leq 1/2$. We can finally rewrite the expression as:

$$f(\mathbf{x}_{k+1}) - f(\mathbf{x}^*) \leq \left(1 - \frac{\omega_{\nu}(1/2)\gamma_k^2}{\eta_k}\right) (f(\mathbf{x}_k) - f(\mathbf{x}^*)).$$

If $\eta_k$ remains bounded above and below across iterations, a fixed step size respecting the hypotheses from the initial statement achieves linear convergence. A step size $\gamma_k$ obtained through line search will achieve more progress per iteration than a fixed step size respecting the provided bounds and hence also achieves linear convergence. $\square$

**Corollary 20.** The SOCGS algorithm applied to a generalized self-concordant objective $f$ of parameters $(M, \nu)$ with $\nu \geq 2$ on a polytope $\mathcal{X}$ achieves linear convergence when performing Blended Pairwise Conditional Gradients or Away-Step Frank-Wolfe inner steps for the subproblems if $f$ is strongly convex or if it is the composition of a log-homogeneous barrier with an affine map.

Linear convergence of BPCG and AFW on strongly convex generalized self-concordant functions was established in Carderera et al. [2024] while the case of the composition of a log-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-Metric step, both of which provide linear convergence. Finally, we highlight that this result also applies to CGS by using, e.g., AFW or BPCG algorithms for the projection subproblems and starting from a first point in $\mathrm{dom}(f)$. Since the algorithm provides primal progress at each iteration, convergence follows from $\eta_k = \max\{L_0, 1/\mu_0\}$ where $L_0, \mu_0$ are local smoothness and strong convexity parameters computed on the sublevel set of $f(\mathbf{x}_0)$, the value of the initial point.

## 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
<figure><img src="image_6.png" /><figcaption>Figure 5: Sparse regression with $K \in \{3, 30\}$ and $\tau = 1$</figcaption></figure>

use LCFW with $J = 2$ and local pairwise steps as the default corrective step. Additionally, if a 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 hybrid approaches with other FW methods in Appendix 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], yielding sufficient progress. For the actual implementation, we have used the FrankWolfe.jl 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-Sparse regression

In the first experiment, we consider a sparse regression problem over the K-Sparse polytope, i.e., the intersection of an $l_1$-norm ball and an $l_\infty$-norm ball, $P_K(\tau) = B_1(\tau K) \cap B_\infty(\tau)$. The vertices of the polytope are given by the vectors with entries in $\{-\tau, 0, \tau\}$ with at most $K$ non-zeros. We consider a classical linear regression problem, i.e., solving

$$ \min_{\mathbf{x} \in P_K(\tau)} f(\mathbf{x}) = \sum_{i=1}^{m} (\langle \mathbf{x}, \mathbf{a}_i \rangle - y_i)^2 = \| \mathbf{A}\mathbf{x} - \mathbf{y} \|_2^2 $$

given data points $\{(\mathbf{a}_i, y_i)\}_{i=1}^m \subset \mathbb{R}^n \times \mathbb{R}$. We used synthetic data for the experiment and generated normally distributed $\mathbf{a}_i$ and $y_i$ with $n = 500$ and $m = 10000$. In Section 4 we already presented the results for the case $K \in \{5, 20\}$ and $\tau = 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 \in \{3, 30\}$. Again, we use a 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 is 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.

## F.2 Entanglement detection

In the second experiment, we consider bipartite entanglement detection. Solving this problem is equivalent to projecting a given state onto the set of separable states,

$$ S_{AB} = \mathrm{conv}\{\rho_A \otimes \rho_B : \rho_A \in \mathbb{D}(A), \rho_B \in \mathbb{D}(B)\}, $$

where $\otimes$ denotes the tensor product and where $\mathbb{D}(A)$ and $\mathbb{D}(B)$ are the sets of density matrices on systems $A$ and $B$ respectively, i.e., (hermitian) positive semidefinite matrices with unit trace.
Consequently, the projection problem can be written as

$$ \min_{\rho \in S_{AB}} \|\rho - \rho_0\|_F^2, $$

where $\|\cdot\|_F$ is the Frobenius norm and $\rho_0$ is the given state. In our experiments, we consider a family of bipartite 3 × 3 entangled states proposed in Horodecki [1997]. Given a parameter $a \in [0, 1]$, these states are defined by

$$ \rho_H^a = \frac{1}{8a+1} \begin{pmatrix} a & 0 & 0 & 0 & a & 0 & 0 & a \\ 0 & a & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & a & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & a & 0 & 0 & 0 & 0 \\ a & 0 & 0 & 0 & a & 0 & 0 & a \\ 0 & 0 & 0 & 0 & 0 & a & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & \frac{1+a}{2} & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & \frac{\sqrt{1-a^2}}{2} \end{pmatrix} \begin{pmatrix} \frac{1+a}{2} & 0 & \frac{\sqrt{1-a^2}}{2} & 0 \\ 0 & a & 0 & 0 \\ 0 & 0 & a & 0 \\ 0 & 0 & 0 & a & 0 & \frac{1+a}{2} & 0 & \frac{\sqrt{1-a^2}}{2} \end{pmatrix} $$

The positive partial transpose (PPT) criterion yields necessary and sufficient conditions for systems of the sizes 2 × 2 and 2 × 3 to be separable; however, it is only necessary for higher-dimensional systems [Horodecki et al., 1996]. For $a \in [0, 1)$, the entangled states $\rho_H^a$ 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.,

$$ \rho_0 = v \rho_H^a + \frac{1-v}{9} \mathbf{I}, \qquad (69) $$

for a given noise level $v \in [0, 1]$. In Figure 6 we present the results for different noise levels $v \in \{0.95, 0.97\}$ for a fixed state with parameter $a = 0.5$. We used again a correction interval of $N = 1$ for QC-MNP and $N = 10$ for QC-LP. Comparing the two plots, one can see that adding white noise decreases the distance to $S_{AB}$ and therefore leads to smaller primal values. Interestingly, QC-LP is performing worse than BPCG for the pure state. This is because the LP solved by QC-LP is 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 $S_{AB}$.

<figure><img src="image_7.png" /><figcaption>Figure 6: Entanglement detection for a state $\rho_0$ given in (69) with different noise levels $v \in \{0.95, 1.0\}$ applied on a fixed state from (68) with parameter $a = 0.5$.</figcaption></figure>

### F.3 Projection onto the intersection of the Birkhoff polytope and a shifted $\ell_2$ ball

**Experiment details** The Birkhoff polytope $B(n)$ is the set of all $n \times n$ doubly stochastic matrices, and its vertices are permutation matrices and therefore particularly sparse. Furthermore, one can solve linear minimization problems over the Birkhoff polytope with a complexity of $O(n^3)$ using the Hungarian algorithm [Combettes and Pokutta, 2021].

For shifting the center of the $\ell_2$ ball, we first sample vertices $v_1, \dots, v_m$ of the Birkhoff polytope by calling the LMO with uniform random directions $d_1, \dots, d_m$. The ball is then shifted to $s =$
<figure><img src="image_8.png" /><figcaption>Figure 7: Projection onto the Birkhoff polytope for $n \in \{300, 500\}$</figcaption></figure>

$\bar{v} - c \frac{\bar{d}}{\|\bar{d}\|_2}$ where $\bar{v} = \frac{1}{m} \sum_{i=1}^{m} v_i$ and $\bar{d} = \frac{1}{m} \sum_{i=1}^{m} d_i$. The radius of the ball is set to $r = 1$, such that the ball and the polytope intersect if and only if $c \le 1$. Note the diameter of the Birkhoff polytope is $\sqrt{2n}$ and therefore much larger than the given radius of the ball. This setting can be understood as a projection onto the Birkhoff polytope with some noise or flexibility in the projection direction.

The number of sampled vertices $m$ controls the dimension of the face where $\bar{v}$ is located, i.e., the number of non-zero entries in $\bar{v}$. In particular, the expected number of non-zero entries in $\bar{v}$ is

$$ \mathbb{E}[\|\bar{v}\|_0] = n^2 \left(1 - \left(1 - \frac{1}{n}\right)^m\right) \approx n^2 \left(1 - e^{-m/n}\right) = n^2 \cdot q, $$

for $m = -n \ln(1 - q)$. Let $B_2(r, c)$ denote the $\ell_2$ ball of radius $r$ and center $c$. The problem we consider is,

$$ \min_{\mathbf{X} \in B(n) \cap B_2(r,s)} f(\mathbf{X}) = \frac{1}{n^2} \|\mathbf{X} - \mathbf{X}_0\|_F^2, $$

where $\mathbf{X}_0 \in \mathbb{R}^{n \times n}$ 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 $\ell_2$ ball, we use a cyclic block-coordinate 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 $\ell_2$ 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 $\lambda_t = \ln(t + 2)$ proposed in Theorem 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, as they do not depend on any line search. Consequently, we use the new secant line search proposed by Hendrych et al. [2025].

**Additional results** In this paragraph, we present additional results for related problem settings. In particular, we decompose the above problem and solve relaxed settings, a projection just onto the Birkhoff polytope, and the intersection problem between the Birkhoff polytope and a shifted $\ell_2$ ball for different intersection scenarios. Furthermore, we present how SCG with vanilla FW steps on both sets perform for the original problem, comparing the new proposed step size schedule with the one from [Woodstock and Pokutta, 2025].

First, we consider the problem of projecting onto the Birkhoff polytope, i.e., without the additional $\ell_2$ ball constraint. We ran the experiment for $n \in \{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 is 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 $\ell_2$ ball. We use the same setup for placing the $\ell_2$ ball as described
<figure><img src="image_9.png" /><figcaption>Figure 8: ALM applied to the intersection of a shifted $ℓ_2$ ball and the Birkhoff polytope for the intersecting scenario $c = 0.9$ and the disjoint one with $c = 1.1$</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>Figure 9: Comparison of the new step size and penalty-schedule (N-FW) proposed in Theorem 9 with the original ones (O-FW) in Woodstock and Pokutta [2025]</figcaption></figure>

above. However, since we do not have an additional objective, we use the ALM method by Braun et al. [2023] to solve the problem. We consider the cases of $c \in \{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 $q = 0.1$, $r = 1$, $n = 500$, and $N = 1$. Additionally, we disabled the quadratic corrections until 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, we also compare the vanilla FW steps from the original version of ALM. The results of the two experiments are shown in Figure 8.

In both experiments, the two QC methods show a very similar behavior. For $c = 0.9$, i.e., when the two sets have a full-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 $c = 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 as pronounced as in the previous experiment.

Finally, we compare the step size and penalty schedule proposed in Theorem 9 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, we again used $c = 0.9$, $q = 0.1$, and $n = 300$. The results are depicted in Figure 9. We use a logarithmic scale on the horizontal axis to 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.

## 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 10. For the outer step, we use the lazified BPCG.
Due to numerical instabilities for the PVM stop condition at Line 9 in Algorithm 10 (we were getting threshold values $\epsilon_t \ge 0$ too close to 0), we replaced the stop condition at Line 9 by a fixed number $k \in \{50, 200\}$ of inner steps. Tightening the lower bound estimations $lb(x_t)$ 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, we 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 in Figure 4. After iteration 25 of SOCGS, both QC-LP and QC-MNP perform in each PVM step a QC step at the first inner iteration. A second quadratic correction is performed after 30 atoms were added to the active set $\tilde{S}_{t+1}^{h+1}$ of the PVM step. This yields a quick adjustment to the new quadratic model and an additional correction if a relevant amount of new vertices were added to the active set. The experiments were run with a limit of 100 SOCGS iterations and a time limit of 2000 seconds.

We consider the same structured logistic regression problem over the $\ell_1$ ball as in Carderera and Pokutta [2020]. We solve

$$ \min_{\mathbf{x} \in B_1(1)} \frac{1}{m} \sum_{i=1}^{m} \ln (1 + \exp(-y_i \langle \mathbf{x}, \mathbf{z}_i \rangle)) + \frac{1}{2m} \|\mathbf{x}\|^2. $$

The labels $y_i \in \{-1, 1\}$ and feature vectors $\mathbf{z}_i \in \mathbb{R}^n$ are taken from the gisette training dataset [Guyon et al., 2007], so that $n = 5000$ and $m = 6000$. As mentioned in [Sun and Tran-Dinh, 2019, Subsection 6.1], the function $f$ is an example of $(M, 3)$-generalized self-concordant function as in (46), where $M = \sqrt{m} \max \{\|\mathbf{z}_i\| \mid 1 \le i \le m\}$.

The evaluation of the gradient of $f$,

$$ \nabla f(\mathbf{x}) = -\frac{1}{m} \sum_{i=1}^{m} \frac{y_i \mathbf{z}_i}{1 + \exp(y_i \langle \mathbf{x}, \mathbf{z}_i \rangle)} + \frac{1}{m} \mathbf{x} \in \mathbb{R}^n, $$

is computationally demanding, as one has to compute $m$ inner products of size $n$ for each gradient evaluation. For the quadratic approximations $\hat{f}_t$, we use an exact Hessian approximation $\mathbf{H}_t = \nabla^2 f(\mathbf{x}_t)$ with

$$ \nabla^2 f(\mathbf{x}) = \frac{1}{m} \sum_{i=1}^{m} \frac{\mathbf{z}_i \mathbf{z}_i^T}{(1 + \exp(-y_i \langle \mathbf{x}, \mathbf{z}_i \rangle))(1 + \exp(y_i \langle \mathbf{x}, \mathbf{z}_i \rangle))} + \frac{1}{m} \mathbf{I}^n \in \mathbb{R}^{n \times n}, $$

where $\mathbf{I}^n \in \mathbb{R}^{n \times n}$ is the identity matrix. The gradients $\nabla \hat{f}_t$ of the quadratic approximations $\hat{f}_t$ are given by $\nabla \hat{f}_t(\mathbf{x}) = \nabla f(\mathbf{x}_t) + \mathbf{H}_t(\mathbf{x} - \mathbf{x}_t)$.

It is worth noticing that in our current implementation, we are 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 $\mathbf{x}$ using the decomposition of the Hessian as 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 14 in Algorithm 10. We did not see a significant change in the trajectories as plotted in Figure 4, 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-integer 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 10 for different types of instances. All algorithms use lazification. The BCG, BPCG and PFW methods perform well for instances with a low radius and a 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 in which LMO calls are much costlier than solving any number of linear programs.
<figure><img src="image_11.png" /><figcaption>(a) $d = 10, n_v = 7, \rho = 11$</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>(c) $d = 10, n_v = 40, \rho = 11$</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>(e) $d = 12, n_v = 10, \rho = 14$</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>(b) $d = 10, n_v = 7, \rho = 30$</figcaption></figure>

<figure><img src="image_15.png" /><figcaption>(d) $d = 10, n_v = 40, \rho = 30$</figcaption></figure>

<figure><img src="image_16.png" /><figcaption>(f) $d = 12, n_v = 10, \rho = 15$</figcaption></figure>

<caption>Figure 10: Results on the tensor completion problem. The dimension of the tensor is $d \times d \times d$. The parameter $n_v$ indicates how many vertices were sampled to construct the underlying ground truth, and $\rho$ is the radius of the tensor norm ball.</caption>
<figure><img src="image_17.png" /><figcaption>Figure 11: Performance profile of different FW methods with quadratic corrections over a problem set of 37 instances.</figcaption></figure>

## 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, we 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, we compare twelve methods, four baseline algorithms, and eight variants enhanced with quadratic corrections. We consider 37 quadratic problem instances from the *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 a performance profile illustrating the number of problem instances solved within a given time. All methods had a time limit of one hour and 10000 iterations, except for the entanglement detection problem, which allowed $10^8$ 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 if the iteration or time limit is reached. The results are given in Figure 11.

The graphic demonstrates that QC-MNP improves the performance of all baseline 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 as pronounced as for other methods. The additional runtime for solving the linear problem is not compensated for by the reduced number of iterations.

Finally, we present the success rates for the aforementioned methods, i.e., the ratio of QC steps that are fully-corrective. There are no guarantees as to when the affine minimizer lies within the convex hull of the active sets. However, the performance of the quadratic correction steps depends heavily on 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 in Table 1 and Table 2. We present the shifted geometric mean of 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 for 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 so poorly, sometimes even slower than some baselines in this problem class. In the tensor completion problem, the success rates are moderately high. However, the overall numbers are comparably small due to the low number of total iterations.

<table><caption>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.</caption><thead><tr><th>Method</th><th>FW-LP</th><th>AFW-LP</th><th>PFW-LP</th><th>BPCG-LP</th></tr></thead><tbody><tr><td>K-sparse regression</td><td>16 / 40</td><td>29 / 30</td><td>3 / 4</td><td>29 / 30</td></tr><tr><td>Entanglement detection</td><td>2 / 14803</td><td>2 / 544</td><td>1 / 274</td><td>2 / 473</td></tr><tr><td>Birkhoff projection</td><td>0 / 45</td><td>19 / 28</td><td>1 / 2</td><td>18 / 19</td></tr><tr><td>Tensor completion</td><td>4 / 6</td><td>3 / 5</td><td>1 / 3</td><td>3 / 4</td></tr></tbody></table>

<table><caption>Table 2: Shifted geometric mean of the number of successful QC-MNP steps and the total number of QC-MNP steps across different problem instances.</caption><thead><tr><th>Method</th><th>FW-MNP</th><th>AFW-MNP</th><th>PFW-MNP</th><th>BPCG-MNP</th></tr></thead><tbody><tr><td>K-sparse regression</td><td>29 / 30</td><td>29 / 30</td><td>3 / 5</td><td>29 / 30</td></tr><tr><td>Entanglement detection</td><td>68 / 746</td><td>492 / 897</td><td>651 / 935</td><td>596 / 889</td></tr><tr><td>Birkhoff projection</td><td>20 / 24</td><td>21 / 28</td><td>1 / 2</td><td>18 / 19</td></tr><tr><td>Tensor completion</td><td>4 / 6</td><td>3 / 4</td><td>1 / 3</td><td>3 / 4</td></tr></tbody></table>