a) There exists $\bar{v}_1 \in K^t$ such that $\phi(\bar{v}_1) > 0$. To show that $\phi \notin \partial_{l_{M^+(K^t)}}(m)$, we have to find $\bar{m} \in M^+(K^t)$ such that $\int_{K^t} \phi(d\bar{m} - dm) > 0$. We set $\bar{m} = m + \delta_{\bar{v}_1}$. Then clearly $\bar{m} \in M^+(K^t)$, and we have

$$ \int_{K^t} \phi(d\bar{m} - dm) = \phi(\bar{v}) > 0. $$

And thus, $\phi \notin \partial_{l_{M^+(K^t)}}(m)$.

b) We have $\phi \in C(K^t; \mathbb{R}_-)$ and $\int_{K^t} \phi dm < 0$. Set $\bar{m} = \frac{1}{2}m$. Then $\bar{m} \in M^+(K^t)$ and

$$ \int_{K^t} \phi(d\bar{m} - dm) = -\frac{1}{2} \int_{K^t} \phi dm > 0. $$

Thus, $\phi \notin \partial_{l_{M^+(K^t)}}(m)$.

c) We have $\phi \in C(K^t; \mathbb{R}_-)$ and $\int_{K^t} \phi dm = 0$. Let $\bar{m} \in M^+(K^t)$. Then

$$ \int_{K^t} \phi(d\bar{m} - dm) = \int_{K^t} \phi d\bar{m} \le 0. $$

Thus, $\phi \in \partial_{l_{M^+(K^t)}}(m)$.

Since those three cases make a partition of $C(K^t)$, the result follows. $\square$

Our next result proves that there is strong duality between between Problems (48) and (49) and provides optimality conditions for these problems.

**Proposition 5.4.** There exists $(\bar{\mu}, \bar{z}) \in \mathcal{E} \times \mathbb{R}$ such that $F^t(\bar{\mu}, \bar{z}) < +\infty$ and $G^t$ is continuous at $L^t(\bar{\mu}, \bar{z})$. Thus, Problems (48) and (49) have opposite values and, for all $(\mu, z, m) \in \mathcal{E} \times \mathbb{R} \times M(K^t)$, the following are equivalent:

i) $(\mu, z)$ is solution to Problem (48) and $m$ is solution to Problem (49).

ii) $L^t * m \in \partial F^t(\mu, z)$ and $-m \in \partial G^t(L^t(\mu, z))$.

iii) $(\mu, z) = \nabla F^t * (L^t * m)$ and $L^t(\mu, z) \in \partial G^t * (-m)$.

*Proof.* Notice that $\psi + \sigma_{E^t} \in \Gamma_0(\mathcal{E})$ and it is coercive since it is lower bounded by $\psi + \sigma_{E^t}$, which is coercive thanks to Lemma 4.11. Let then $\bar{\mu} \in \mathcal{E}$ be a solution to

$$ \underset{\mu \in \mathcal{E}}{\text{minimize}} \psi(\mu) + \sigma_{E^t}(\mu) $$

and set $\alpha = \psi(\bar{\mu}) + \sigma_{E^t}(\bar{\mu})$. Note that, since $E^t \subset \tilde{E}^t$ (where $\tilde{E}^t$ is the set defined in Algorithm 6), we deduce that $\alpha \le \underline{h}^t$ (where we use once again the notations of Algorithm 6).

It follows from (28) that $f^*(\bar{\mu}_1) < +\infty$ and $\bar{\mu}_2 \in Q$, and we deduce from (47) that $F^t(\bar{\mu}, f^*(\bar{\mu}_1)) < +\infty$. Notice also that, for every $v \in K^t$, we have

$$ L^t(\bar{\mu}, f^*(\bar{\mu}_1))(v) = \psi(\bar{\mu}) - \langle \bar{\mu}, (v, Av) \rangle_{\mathcal{E}_2} \le \psi(\bar{\mu}) + \sigma_{E^t}(\bar{\mu}) = \alpha \le \underline{h}^t < \ell^t, $$

and thus $G^t$ is continuous at $L^t(\bar{\mu}, f^*(\bar{\mu}_1))$.

We thus obtain that $0 \in \text{int}(L^t \text{dom}(F^t) - \text{dom}(G^t))$, and the other conclusions of the proof follow from Theorem 2.5, Corollary 2.6, and the fact that $1 - m(K^t) > 0$. $\square$

The aim of our next results is to show that, if $w^{t+1}$ and $\mu^{t+1}$ are defined as in Algorithm 5, then they necessarily satisfy the properties required for the corresponding elements in Algorithm 6. We start with the following property of $w^{t+1}$.

**Lemma 5.5.** Let $m^t$ be a solution to Problem (49) and set $w^{t+1}$ as in Algorithm 5, i.e., as

$$ w^{t+1} = \frac{w^t - \mathfrak{E}m^t}{1 - m^t(K^t)}. $$

Then $w^{t+1} \in \overline{\text{conv}}(\{w^t\} \cup K^t)$.
Proof. We recall that $m^t \in -\mathcal{M}^+(K^t)$. There are two cases. If $m^t(K^t) = 0$, then $w^{t+1} = w^t$. Otherwise, if $m^t(K^t) < 0$ we set $\tilde{m}^t = \frac{m^t}{m^t(K^t)} \in \mathcal{P}(K^t)$ so that $\mathfrak{E}\tilde{m}^t \in \overline{\mathfrak{conv}}(K^t)$. Then, using the linearity of $\mathfrak{E}$, we have

$$w^{t+1} = \frac{1}{1 - m^t(K^t)} w^t - \frac{m^t(K^t)}{1 - m^t(K^t)} \mathfrak{E}\tilde{m}^t.$$

The result follows.

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

Note that, if Assumption (H2) is satisfied, then the sets $K^t$ are uniformly bounded in $t$. Hence, as an immediate consequence of Lemma 5.5, we obtain the following result.

**Corollary 5.6.** Assume that Assumption (H2) is satisfied. Then we can bound $w^t$ uniformly in $t$.

We next verify that the choices of $w_1^{t+1}$ and $\mu^{t+1}$ in Algorithm 5 satisfy the required conditions from Algorithm 6.

**Lemma 5.7.** Let $t \in \mathbb{N}$ and consider the elements $\mu^t$, $\mu^{t+1}$, $w_1^t$, and $w_1^{t+1}$ defined as in Algorithm 5. Define $Q^t$ as in Algorithm 6. Then

$$Q^t = \{\mu \in \mathcal{E}_1 \times Q \mid f^*(\mu_1) + \langle \mu_2, b \rangle_{\mathcal{E}_2} - \langle \mu_1 + A^*\mu_2, v_1 \rangle_{\mathcal{E}_1} \le l^t \text{ for all } v_1 \in \overline{\mathfrak{conv}}(K^t)\}, \quad (50)$$

$\mu^{t+1}$ is the solution to Problem (35), and

$$(w_1^t - w_1^{t+1}, \mu_2^t - \mu_2^{t+1}) \in N_{Q^t}(\mu^{t+1}). \quad (51)$$

*Proof.* First, Equation (50) derives from the definition of $Q^t$ in Algorithm 6 and from eq. (34).

To prove the second statement, note that, thanks to Assumption (A1), $f^*$ is strongly convex, and thus Problem (35) admits a unique solution $\mu$. Due to the discussion at the beginning of the section, $\mu$ is solution to Problem (35) if and only if $(\mu, f^*(\mu_1))$ is solution to Problem (48).

On the other hand, the element $m^t$ from Algorithm 5 is solution to Problem (33) with $S = K^t$, which, thanks to Lemmas 5.1 and 5.2, is equivalent to $m^t$ being a solution to Problem (49). Thus, by Proposition 5.4, we necessarily have $(\mu, f^*(\mu_1)) = \nabla F^{t*}(L^{t*}m^t)$. Using the expression of $\nabla F^{t*}$ from Lemma 5.3 and that of $L^{t*}$ from Lemma 5.2, we finally deduce that $\mu = \mu^{t+1}$.

Let us now turn to the proof of (51). Note that, by definition of the normal cone, (51) is equivalent to having

$$\langle w_1^t - w_1^{t+1}, \mu_1 - \mu_1^{t+1} \rangle_{\mathcal{E}_1} + \langle \mu_2^t - \mu_2^{t+1}, \mu_2 - \mu_2^{t+1} \rangle_{\mathcal{E}_2} \le 0$$

for every $\mu = (\mu_1, \mu_2) \in Q^t$.

For $\mu \in Q^t$, we set

$$\Lambda^t(\mu) = \langle w_1^t - w_1^{t+1}, \mu_1 - \mu_1^{t+1} \rangle_{\mathcal{E}_1} + \langle \mu_2^t - \mu_2^{t+1}, \mu_2 - \mu_2^{t+1} \rangle_{\mathcal{E}_2}.$$

First, we notice that

$$\begin{aligned} \langle \mu_2^t - \mu_2^{t+1}, \mu_2 - \mu_2^{t+1} \rangle_{\mathcal{E}_2} &= \langle \mu_2^t - A \mathfrak{E} m^t + m^t(K^t)b - \mu_2^{t+1}, \mu_2 - \mu_2^{t+1} \rangle_{\mathcal{E}_2} + \langle A \mathfrak{E} m^t - m^t(K^t)b, \mu_2 - \mu_2^{t+1} \rangle_{\mathcal{E}_2} \\ &\le \langle A \mathfrak{E} m^t - m^t(K^t)b, \mu_2 - \mu_2^{t+1} \rangle_{\mathcal{E}_2}, \end{aligned}$$

since $\mu_2^{t+1} = \text{proj}_Q(\mu_2^t - A \mathfrak{E} m^t + m(K^t)b)$. Also notice that, by definition of $w_1^{t+1}$, we have

$$w_1^t = \mathfrak{E} m^t + (1 - m^t(K^t)) w_1^{t+1}$$

and thus

$$w_1^t - w_1^{t+1} = \mathfrak{E} m^t - m^t(K^t) w_1^{t+1}$$

and

$$\Lambda^t(\mu) \le \langle \mu - \mu^t, (\mathfrak{E} m^t, A \mathfrak{E} m^t) \rangle_{\mathcal{E}} - m^t(K^t) \langle \mu - \mu^{t+1}, (w_1^{t+1}, b) \rangle_{\mathcal{E}}.$$

Clearly, the result holds if $m^t = 0_{\mathcal{M}(K^t)}$.

Now, assume that $m^t \ne 0_{\mathcal{M}(K^t)}$. We recall that, by definition of $\mu_1^{t+1}$ in Algorithm 5, we have $w_1^{t+1} \in \partial f^*(\mu_1^{t+1})$, and thus

$$\langle \mu_1 - \mu_1^{t+1}, w_1^{t+1} \rangle_{\mathcal{E}_1} \le f^*(\mu_1) - f^*(\mu_1^{t+1})$$
Proof. We recall that $m^t \in -\mathcal{M}^+(K^t)$. There are two cases. If $m^t(K^t) = 0$, then $w^{t+1} = w^t$. Otherwise, if $m^t(K^t) < 0$ we set $\tilde{m}^t = \frac{m^t}{m^t(K^t)} \in \mathcal{P}(K^t)$ so that $\mathfrak{E}\tilde{m}^t \in \overline{\mathfrak{conv}}(K^t)$. Then, using the linearity of $\mathfrak{E}$, we have

$$w^{t+1} = \frac{1}{1 - m^t(K^t)} w^t - \frac{m^t(K^t)}{1 - m^t(K^t)} \mathfrak{E}\tilde{m}^t.$$

The result follows.

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

Note that, if Assumption (H2) is satisfied, then the sets $K^t$ are uniformly bounded in $t$. Hence, as an immediate consequence of Lemma 5.5, we obtain the following result.

**Corollary 5.6.** Assume that Assumption (H2) is satisfied. Then we can bound $w^t$ uniformly in $t$.

We next verify that the choices of $w_1^{t+1}$ and $\mu^{t+1}$ in Algorithm 5 satisfy the required conditions from Algorithm 6.

**Lemma 5.7.** Let $t \in \mathbb{N}$ and consider the elements $\mu^t$, $\mu^{t+1}$, $w_1^t$, and $w_1^{t+1}$ defined as in Algorithm 5. Define $Q^t$ as in Algorithm 6. Then

$$Q^t = \{\mu \in \mathcal{E}_1 \times Q \mid f^*(\mu_1) + \langle \mu_2, b \rangle_{\mathcal{E}_2} - \langle \mu_1 + A^*\mu_2, v_1 \rangle_{\mathcal{E}_1} \le l^t \text{ for all } v_1 \in \overline{\mathfrak{conv}}(K^t)\}, \quad (50)$$

$\mu^{t+1}$ is the solution to Problem (35), and

$$(w_1^t - w_1^{t+1}, \mu_2^t - \mu_2^{t+1}) \in N_{Q^t}(\mu^{t+1}). \quad (51)$$

*Proof.* First, Equation (50) derives from the definition of $Q^t$ in Algorithm 6 and from eq. (34).

To prove the second statement, note that, thanks to Assumption (A1), $f^*$ is strongly convex, and thus Problem (35) admits a unique solution $\mu$. Due to the discussion at the beginning of the section, $\mu$ is solution to Problem (35) if and only if $(\mu, f^*(\mu_1))$ is solution to Problem (48).

On the other hand, the element $m^t$ from Algorithm 5 is solution to Problem (33) with $S = K^t$, which, thanks to Lemmas 5.1 and 5.2, is equivalent to $m^t$ being a solution to Problem (49). Thus, by Proposition 5.4, we necessarily have $(\mu, f^*(\mu_1)) = \nabla F^{t*}(L^{t*}m^t)$. Using the expression of $\nabla F^{t*}$ from Lemma 5.3 and that of $L^{t*}$ from Lemma 5.2, we finally deduce that $\mu = \mu^{t+1}$.

Let us now turn to the proof of (51). Note that, by definition of the normal cone, (51) is equivalent to having

$$\langle w_1^t - w_1^{t+1}, \mu_1 - \mu_1^{t+1} \rangle_{\mathcal{E}_1} + \langle \mu_2^t - \mu_2^{t+1}, \mu_2 - \mu_2^{t+1} \rangle_{\mathcal{E}_2} \le 0$$

for every $\mu = (\mu_1, \mu_2) \in Q^t$.

For $\mu \in Q^t$, we set

$$\Lambda^t(\mu) = \langle w_1^t - w_1^{t+1}, \mu_1 - \mu_1^{t+1} \rangle_{\mathcal{E}_1} + \langle \mu_2^t - \mu_2^{t+1}, \mu_2 - \mu_2^{t+1} \rangle_{\mathcal{E}_2}.$$

First, we notice that

$$\begin{aligned} \langle \mu_2^t - \mu_2^{t+1}, \mu_2 - \mu_2^{t+1} \rangle_{\mathcal{E}_2} &= \langle \mu_2^t - A \mathfrak{E} m^t + m^t(K^t)b - \mu_2^{t+1}, \mu_2 - \mu_2^{t+1} \rangle_{\mathcal{E}_2} + \langle A \mathfrak{E} m^t - m^t(K^t)b, \mu_2 - \mu_2^{t+1} \rangle_{\mathcal{E}_2} \\ &\le \langle A \mathfrak{E} m^t - m^t(K^t)b, \mu_2 - \mu_2^{t+1} \rangle_{\mathcal{E}_2}, \end{aligned}$$

since $\mu_2^{t+1} = \text{proj}_Q(\mu_2^t - A \mathfrak{E} m^t + m(K^t)b)$. Also notice that, by definition of $w_1^{t+1}$, we have

$$w_1^t = \mathfrak{E} m^t + (1 - m^t(K^t)) w_1^{t+1}$$

and thus

$$w_1^t - w_1^{t+1} = \mathfrak{E} m^t - m^t(K^t) w_1^{t+1}$$

and

$$\Lambda^t(\mu) \le \langle \mu - \mu^t, (\mathfrak{E} m^t, A \mathfrak{E} m^t) \rangle_{\mathcal{E}} - m^t(K^t) \langle \mu - \mu^{t+1}, (w_1^{t+1}, b) \rangle_{\mathcal{E}}.$$

Clearly, the result holds if $m^t = 0_{\mathcal{M}(K^t)}$.

Now, assume that $m^t \neq 0_{\mathcal{M}(K^t)}$. We recall that, by definition of $\mu_1^{t+1}$ in Algorithm 5, we have $w_1^{t+1} \in \partial f^*(\mu_1^{t+1})$, and thus

$$\langle \mu_1 - \mu_1^{t+1}, w_1^{t+1} \rangle_{\mathcal{E}_1} \le f^*(\mu_1) - f^*(\mu_1^{t+1})$$
which yields, using the fact that $-m^t \in \mathcal{M}^+(K^t)$,

$$ \Lambda^t(\mu) \leq \langle \mu - \mu^{t+1}, (\mathfrak{E}m^t, A\mathfrak{E}m^t) \rangle_{\mathcal{E}} - m^t(K^t) \left( f^*(\mu_1) - f^*(\mu_1^{t+1}) + \langle \mu_2 - \mu_2^{t+1}, b \rangle_{\mathcal{E}_2} \right). $$

Recalling that $m^t$ is solution to Problem (49) and $(\mu^{t+1}, f^*(\mu_1^{t+1}))$ is solution to Problem (48), it follows from Proposition 5.4 that $L^t(\mu^{t+1}, f^*(\mu_1^{t+1})) \in \partial G^{t*}(-m^t)$. Hence, from Lemma 5.3, we have

$$ \int_{K^t} [f^*(\mu_1^{t+1}) + \langle \mu_2^{t+1}, b \rangle_{\mathcal{E}_2} - \ell^t - \langle \mu_1^{t+1} + A^*\mu_2^{t+1}, v_1 \rangle_{\mathcal{E}}] dm^t(v_1) \\ = m^t(K^t) \left( f^*(\mu_1^{t+1}) + \langle \mu_2^{t+1}, b \rangle_{\mathcal{E}_2} - \ell^t \right) - \langle \mu_1^{t+1} + A^*\mu_2^{t+1}, \mathfrak{E}m^t \rangle_{\mathcal{E}} = 0, $$

and thus

$$ \Lambda^t(\mu) \leq \langle \mu_1 + A^*\mu_2, \mathfrak{E}m^t \rangle_{\mathcal{E}} - m^t(K^t) \left( f^*(\mu_1) + \langle \mu_2, b \rangle_{\mathcal{E}_2} - \ell^t \right). $$

Since $\mu \in Q^t$, it follows from (50) that, for all $v_1 \in \overline{\text{conv}}(K^t)$,

$$ \Lambda^t(\mu) \leq \langle \mu_1 + A^*\mu_2, \mathfrak{E}m^t \rangle_{\mathcal{E}} - m^t(K^t)\langle \mu_1 + A^*\mu_2, v_1 \rangle_{\mathcal{E}_1}. $$

Set $\bar{v}_1 = \frac{\mathfrak{E}m^t}{m^t(K^t)}$. We have $\bar{v}_1 \in \overline{\text{conv}}(K^t)$ since $\frac{m^t}{m^t(K^t)} \in \mathcal{P}(K^t)$ and $\mathfrak{E}$ is linear, and taking $v_1 = \bar{v}_1$ in the above inequality yields $\Lambda^t(\mu) \leq 0$, which concludes the proof. $\square$

We finally collect the results of this section in order to provide a proof for Proposition 4.9.

**Proof of Proposition 4.9.** i) Thanks to Lemmas 5.1 and 5.2, Problem (33) coincides with Problem (49), and the latter is the dual of Problem (48), which is equivalent (up to a change in its value and a transformation in its variables, as discussed in the beginning of this section) to Problem (35).

ii) Part a of the conclusion follows from Lemma 5.7, while part b follows by combining the definition of $\mu_1^{t+1}$ in Algorithm 5, Lemma 2.2, Corollary 5.6, and Lemma 5.7. $\square$

# 6 Numerical examples

In this section, given $n \in \mathbb{N}^*$ and $p \in [1, +\infty]$, we denote by $B_p^n$ the closed unit ball in $\mathbb{R}^n$ for the $\ell^p$ norm, which is denoted by $\| \cdot \|_p$. We denote by $M_{n,m}(\mathbb{R})$ the set of real matrices of size $n \times m$. For square matrices, we write $M_n(\mathbb{R})$ instead of $M_{n,n}(\mathbb{R})$. The vector space of symmetric matrices of size $n$ is denoted by $S_n(\mathbb{R})$ and the subset of those which are positive semidefinite is denoted by $S_n^+(\mathbb{R})$.

## 6.1 A projection problem

We first test our algorithm in a simple problem taken from [20]. Let $p \in \{1, 2\}$ and $A \in M_{1,2}(\mathbb{R}) \setminus \{0\}$. We aim at solving

$$ \underset{x \in B_p^2}{\text{minimize}} \quad \frac{1}{2} \|x - y\|^2 \text{ s.t. } Ax = 0. \qquad (52) $$

Notice that the feasible set of the problem is a segment, obtained as the intersection of a convex set and a line, whose extremities can be computed analytically. The projection of a point onto a segment being easy to solve, the problem can be solved analytically without difficulty.

**Structure** This problem fits in our framework if we take $\mathcal{E}_1 = \mathbb{R}^2$, $f = \frac{1}{2}\|\cdot - y\|^2$, $\mathcal{E}_2 = \mathbb{R}$, $Q_1 = \{0\}$, $Q_2 = \mathbb{R}$, $b = 0$, and $K = B_p^2$. For this choice, we indeed have $\sigma_Q = \iota_{\{0\}}$. Notice that, since $K$ is compact, Assumption (H2) is satisfied.

**Qualification condition** This problem is qualified. Indeed, if $\text{Ker}(A) = \mathbb{R} \times \{0\}$, then we can take $K^{-1} = \{(0, -1), (0, 1)\}$, and otherwise we can take $K^{-1} = \{(-1, 0), (1, 0)\}$.

**Oracle** The LMO writes: minimize $\langle \mu, x \rangle$, for a given $\mu \in \mathbb{R}^2$. For $p = 1$, the set $K = B_1^2$ is the convex hull of the four points $(0, 1)$, $(0, -1)$, $(1, 0)$, and $(-1, 0)$, therefore, for any $\mu \in \mathbb{R}^2$, one of them is solution to the LMO, making its resolution easy. For $p = 2$, two cases must be considered. If $\mu = 0$, any point in $K$ is a solution. Otherwise, the unique solution is given by $-\mu/\|\mu\|_2$.
which yields, using the fact that $-m^t \in \mathcal{M}^+(K^t)$,

$$ \Lambda^t(\mu) \leq \langle \mu - \mu^{t+1}, (\mathfrak{E}m^t, A\mathfrak{E}m^t) \rangle_{\mathcal{E}} - m^t(K^t) \left( f^*(\mu_1) - f^*(\mu_1^{t+1}) + \langle \mu_2 - \mu_2^{t+1}, b \rangle_{\mathcal{E}_2} \right). $$

Recalling that $m^t$ is solution to Problem (49) and $(\mu^{t+1}, f^*(\mu_1^{t+1}))$ is solution to Problem (48), it follows from Proposition 5.4 that $L^t(\mu^{t+1}, f^*(\mu_1^{t+1})) \in \partial G^{t*}(-m^t)$. Hence, from Lemma 5.3, we have

$$ \int_{K^t} [f^*(\mu_1^{t+1}) + \langle \mu_2^{t+1}, b \rangle_{\mathcal{E}_2} - \ell^t - \langle \mu_1^{t+1} + A^*\mu_2^{t+1}, v_1 \rangle_{\mathcal{E}}] dm^t(v_1) \\ = m^t(K^t) \left( f^*(\mu_1^{t+1}) + \langle \mu_2^{t+1}, b \rangle_{\mathcal{E}_2} - \ell^t \right) - \langle \mu_1^{t+1} + A^*\mu_2^{t+1}, \mathfrak{E}m^t \rangle_{\mathcal{E}} = 0, $$

and thus

$$ \Lambda^t(\mu) \leq \langle \mu_1 + A^*\mu_2, \mathfrak{E}m^t \rangle_{\mathcal{E}} - m^t(K^t) \left( f^*(\mu_1) + \langle \mu_2, b \rangle_{\mathcal{E}_2} - \ell^t \right). $$

Since $\mu \in Q^t$, it follows from (50) that, for all $v_1 \in \overline{\text{conv}}(K^t)$,

$$ \Lambda^t(\mu) \leq \langle \mu_1 + A^*\mu_2, \mathfrak{E}m^t \rangle_{\mathcal{E}} - m^t(K^t) \langle \mu_1 + A^*\mu_2, v_1 \rangle_{\mathcal{E}_1}. $$

Set $\bar{v}_1 = \frac{\mathfrak{E}m^t}{m^t(K^t)}$. We have $\bar{v}_1 \in \overline{\text{conv}}(K^t)$ since $\frac{m^t}{m^t(K^t)} \in \mathcal{P}(K^t)$ and $\mathfrak{E}$ is linear, and taking $v_1 = \bar{v}_1$ in the above inequality yields $\Lambda^t(\mu) \leq 0$, which concludes the proof. $\square$

We finally collect the results of this section in order to provide a proof for Proposition 4.9.

**Proof of Proposition 4.9.** i) Thanks to Lemmas 5.1 and 5.2, Problem (33) coincides with Problem (49), and the latter is the dual of Problem (48), which is equivalent (up to a change in its value and a transformation in its variables, as discussed in the beginning of this section) to Problem (35).

ii) Part a of the conclusion follows from Lemma 5.7, while part b follows by combining the definition of $\mu_1^{t+1}$ in Algorithm 5, Lemma 2.2, Corollary 5.6, and Lemma 5.7. $\square$

# 6 Numerical examples

In this section, given $n \in \mathbb{N}^*$ and $p \in [1, +\infty]$, we denote by $B_p^n$ the closed unit ball in $\mathbb{R}^n$ for the $\ell^p$ norm, which is denoted by $\| \cdot \|_p$. We denote by $\mathcal{M}_{n,m}(\mathbb{R})$ the set of real matrices of size $n \times m$. For square matrices, we write $\mathcal{M}_n(\mathbb{R})$ instead of $\mathcal{M}_{n,n}(\mathbb{R})$. The vector space of symmetric matrices of size $n$ is denoted by $\mathcal{S}_n(\mathbb{R})$ and the subset of those which are positive semidefinite is denoted by $\mathcal{S}_n^+(\mathbb{R})$.

## 6.1 A projection problem

We first test our algorithm in a simple problem taken from [20]. Let $p \in \{1, 2\}$ and $A \in \mathcal{M}_{1,2}(\mathbb{R}) \setminus \{0\}$. We aim at solving

$$ \underset{x \in B_p^2}{\text{minimize}} \quad \frac{1}{2} \|x - y\|^2 \text{ s.t. } Ax = 0. \qquad (52) $$

Notice that the feasible set of the problem is a segment, obtained as the intersection of a convex set and a line, whose extremities can be computed analytically. The projection of a point onto a segment being easy to solve, the problem can be solved analytically without difficulty.

**Structure** This problem fits in our framework if we take $\mathcal{E}_1 = \mathbb{R}^2$, $f = \frac{1}{2}\|\cdot - y\|^2$, $\mathcal{E}_2 = \mathbb{R}$, $Q_1 = \{0\}$, $Q_2 = \mathbb{R}$, $b = 0$, and $K = B_p^2$. For this choice, we indeed have $\sigma_Q = \iota_{\{0\}}$. Notice that, since $K$ is compact, Assumption (H2) is satisfied.

**Qualification condition** This problem is qualified. Indeed, if $\text{Ker}(A) = \mathbb{R} \times \{0\}$, then we can take $K^{-1} = \{(0, -1), (0, 1)\}$, and otherwise we can take $K^{-1} = \{(-1, 0), (1, 0)\}$.

**Oracle** The LMO writes: minimize $\langle \mu, x \rangle$, for a given $\mu \in \mathbb{R}^2$. For $p = 1$, the set $K = B_1^2$ is the convex hull of the four points $(0, 1)$, $(0, -1)$, $(1, 0)$, and $(-1, 0)$, therefore, for any $\mu \in \mathbb{R}^2$, one of them is solution to the LMO, making its resolution easy. For $p = 2$, two cases must be considered. If $\mu = 0$, any point in $K$ is a solution. Otherwise, the unique solution is given by $-\mu/\|\mu\|_2$.
**Numerical results** We provide numerical results for a fixed value of $A$ and for $10^4$ iterations of the algorithm. For the two possible values of $p$, we consider two values of $y$, denoted $y_1$ and $y_2$ and chosen in such a way that, for $y = y_1$, the solution to Problem (52) lies on the boundary of $K$ (i.e., on the unit sphere) and, for $y = y_2$, the solution lies in the interior of $K$.

Let us note that for $p = 1$, the (primal) solution is obtained after finitely many iterations, since $K$ is the convex hull of finitely many points. We also obtain an optimal primal solution in a finite number of iterations if it lies in the interior of $K$ (for $y = y_2$). We do not expect in general to find the dual solution in finitely many iterations.

In Figures 1a to 1d, we show the evolution of the primal-dual gap $\Delta^t$ at each iteration, in log-log scale, for $\lambda \in \{0.05, 0.1, 1 - \sqrt{2} - \sqrt{2}, 0.5\}$, for the pairs $(y, p)$ taken respectively as $(y_1, 1)$, $(y_2, 1)$, $(y_1, 2)$, and $(y_2, 2)$. For the pruning rule, we simply take $K^t = \{\hat{x}^t\} \cup K^{-1}$ at critical iterations.

We notice that, in all of these cases, the primal-dual gap shows a numerical decrease toward 0 with a speed of order $1/t$, with the curves for $\lambda = 0.5$ decreasing slightly more slowly than those with the other choices of $\lambda$. We recall that our proof shows only a speed of order $1/\sqrt{t}$. In Figures 2a and 2b, we show the number of cuts at each iteration for the same values of $\lambda$ and for the pairs $(y, p)$ taken respectively as $(y_1, 2)$ and $(y_2, 2)$. We do not show the number of cuts for $p = 1$ since in that case it is bounded by 4 (the four extremal points of $K$, which contains $K^{-1}$). We notice that the number of cuts stays lower for smaller values of $\lambda$. This result was to be expected, since pruning steps should happen more often for lower values of $\lambda$.

<figure><img src="image_3.png" /><figcaption>(a) $y = y_1$ and $p = 1$</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>(b) $y = y_2$ and $p = 1$</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>(c) $y = y_1$ and $p = 2$</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>(d) $y = y_2$ and $p = 2$</figcaption></figure>

<caption>Figure 1: Primal-dual gap for 4 instances of Problem (52)</caption>
**Numerical results** We provide numerical results for a fixed value of $A$ and for $10^4$ iterations of the algorithm. For the two possible values of $p$, we consider two values of $y$, denoted $y_1$ and $y_2$ and chosen in such a way that, for $y = y_1$, the solution to Problem (52) lies on the boundary of $K$ (i.e., on the unit sphere) and, for $y = y_2$, the solution lies in the interior of $K$.

Let us note that for $p = 1$, the (primal) solution is obtained after finitely many iterations, since $K$ is the convex hull of finitely many points. We also obtain an optimal primal solution in a finite number of iterations if it lies in the interior of $K$ (for $y = y_2$). We do not expect in general to find the dual solution in finitely many iterations.

In Figures 1a to 1d, we show the evolution of the primal-dual gap $\Delta^t$ at each iteration, in log-log scale, for $\lambda \in \{0.05, 0.1, 1 - \sqrt{2} - \sqrt{2}, 0.5\}$, for the pairs $(y, p)$ taken respectively as $(y_1, 1)$, $(y_2, 1)$, $(y_1, 2)$, and $(y_2, 2)$. For the pruning rule, we simply take $K^t = \{\hat{x}^t\} \cup K^{-1}$ at critical iterations.

We notice that, in all of these cases, the primal-dual gap shows a numerical decrease toward 0 with a speed of order $1/t$, with the curves for $\lambda = 0.5$ decreasing slightly more slowly than those with the other choices of $\lambda$. We recall that our proof shows only a speed of order $1/\sqrt{t}$. In Figures 2a and 2b, we show the number of cuts at each iteration for the same values of $\lambda$ and for the pairs $(y, p)$ taken respectively as $(y_1, 2)$ and $(y_2, 2)$. We do not show the number of cuts for $p = 1$ since in that case it is bounded by 4 (the four extremal points of $K$, which contains $K^{-1}$). We notice that the number of cuts stays lower for smaller values of $\lambda$. This result was to be expected, since pruning steps should happen more often for lower values of $\lambda$.

<figure><img src="image_5.png" /><figcaption>(a) $y = y_1$ and $p = 1$</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>(b) $y = y_2$ and $p = 1$</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>(c) $y = y_1$ and $p = 2$</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>(d) $y = y_2$ and $p = 2$</figcaption></figure>

<caption>Figure 1: Primal-dual gap for 4 instances of Problem (52)</caption>
<figure><img src="image_7.png" /><figcaption>Figure 2: Evolution of the number of cuts for 2 instances of Problem (52)</figcaption></figure>

## 6.2 A semidefinite program

We now test our algorithm with the following problem, extracted from [22]. Let $n \in \mathbb{N}^*$ and let $C \in S_n(\mathbb{R})$. We aim at solving

$$ \underset{X \in S_n^+(\mathbb{R})}{\text{minimize}} \langle C, X \rangle_{M_n(\mathbb{R})} \quad \text{s.t.} \quad \text{diag}(X) = 1_{\mathbb{R}^n} \qquad (53) $$

where $\langle A, B \rangle_{M_n(\mathbb{R})} = \text{tr}(A^T B)$ is the canonical inner product.

**Structure** This problem fits in our framework if we take $\mathcal{E}_1 = S_n(\mathbb{R})$, $f = \langle C, \cdot \rangle_{M_n(\mathbb{R})}$, $\mathcal{E}_2 = \mathbb{R}^n$, $A$ the linear operator which maps $X$ to its diagonal, $Q_1 = \{0\}$, $Q_2 = \mathbb{R}^n$, $b = 1_{\mathbb{R}^n}$ and $K = S_n^+(\mathbb{R}) \cap \{\text{tr} \le n+1\}$. Notice that, in this context, $A^*$ is the linear operator which maps a vector $Y$ to the diagonal matrix whose diagonal is $Y$. The definition of the set $K$ is dictated by the qualification condition and by the necessity to have an oracle.

**Qualification condition** This problem verifies the qualification condition by taking $K^{-1}$ as the convex hull of the null matrix and of the matrices $(n+1)E_{i,i}$, $i \in \{1, \dots, n\}$, where $E_{i,j}$, $i, j \in \{1, \dots, n\}$ are the elementary matrices.

**Oracle** A direct application of the spectral theorem reveals that $K = (n+1)\text{conv}(K')$, where the set $K'$ is defined by $K' = \{0\} \cup \{vv^T \mid \|v\|_2 = 1\}$. This allows to show the following lemma.

**Lemma 6.1.** Let $M \in S_n(\mathbb{R})$. Consider the problem

$$ \underset{V \in K}{\text{minimize}} \langle M, V \rangle_{M_n(\mathbb{R})}. \qquad (54) $$

Let $s$ denote the small eigenvalue of $M$. If $s \ge 0$, then the null matrix is a solution to the problem. Otherwise, if $s < 0$, let $\bar{v}$ be an eigenvector associated with $s$, of norm equal to 1. Then $(n+1)\bar{v}\bar{v}^T$ is a solution to the problem.

As in the previous subsection, since $K$ is bounded, Assumption (H2) is satisfied.

**Numerical results** We set $n = 10$ and take a random matrix $C \in S_n(\mathbb{R})$. We then run the algorithm until the primal-dual gap $\Delta^t$ reaches $10^{-6}$. We use the same pruning rule as in Section 6.1. In Figure 4, we show the number of cuts at each iteration, respectively for $\lambda = 0.05$ and $\lambda = 0.7$. Although we do not show it, the number of cuts for the other values of $\lambda$ stays below 45. We notice that, as we expected, the maximal number of cuts is lower for smaller values of $\lambda$.
<figure><img src="image_9.png" /><figcaption>Figure 2: Evolution of the number of cuts for 2 instances of Problem (52)</figcaption></figure>

## 6.2 A semidefinite program

We now test our algorithm with the following problem, extracted from [22]. Let $n \in \mathbb{N}^*$ and let $C \in S_n(\mathbb{R})$. We aim at solving

$$ \min_{X \in S_n^+(\mathbb{R})} \langle C, X \rangle_{M_n(\mathbb{R})} \quad \text{s.t.} \quad \operatorname{diag}(X) = 1_{\mathbb{R}^n} \qquad (53) $$

where $\langle A, B \rangle_{M_n(\mathbb{R})} = \operatorname{tr}(A^T B)$ is the canonical inner product.

**Structure** This problem fits in our framework if we take $\mathcal{E}_1 = S_n(\mathbb{R})$, $f = \langle C, \cdot \rangle_{M_n(\mathbb{R})}$, $\mathcal{E}_2 = \mathbb{R}^n$, $A$ the linear operator which maps $X$ to its diagonal, $Q_1 = \{0\}$, $Q_2 = \mathbb{R}^n$, $b = 1_{\mathbb{R}^n}$ and $K = S_n^+(\mathbb{R}) \cap \{\operatorname{tr} \le n+1\}$. Notice that, in this context, $A^*$ is the linear operator which maps a vector $Y$ to the diagonal matrix whose diagonal is $Y$. The definition of the set $K$ is dictated by the qualification condition and by the necessity to have an oracle.

**Qualification condition** This problem verifies the qualification condition by taking $K^{-1}$ as the convex hull of the null matrix and of the matrices $(n+1)E_{i,i}$, $i \in \{1, \dots, n\}$, where $E_{i,j}$, $i, j \in \{1, \dots, n\}$ are the elementary matrices.

**Oracle** A direct application of the spectral theorem reveals that $K = (n+1)\operatorname{conv}(K')$, where the set $K'$ is defined by $K' = \{0\} \cup \{vv^T \mid \|v\|_2 = 1\}$. This allows to show the following lemma.

**Lemma 6.1.** Let $M \in S_n(\mathbb{R})$. Consider the problem

$$ \min_{V \in K} \langle M, V \rangle_{M_n(\mathbb{R})}. \qquad (54) $$

Let $s$ denote the small eigenvalue of $M$. If $s \ge 0$, then the null matrix is a solution to the problem. Otherwise, if $s < 0$, let $\bar{v}$ be an eigenvector associated with $s$, of norm equal to 1. Then $(n+1)\bar{v}\bar{v}^T$ is a solution to the problem.

As in the previous subsection, since $K$ is bounded, Assumption (H2) is satisfied.

**Numerical results** We set $n = 10$ and take a random matrix $C \in S_n(\mathbb{R})$. We then run the algorithm until the primal-dual gap $\Delta^t$ reaches $10^{-6}$. We use the same pruning rule as in Section 6.1. In Figure 4, we show the number of cuts at each iteration, respectively for $\lambda = 0.05$ and $\lambda = 0.7$. Although we do not show it, the number of cuts for the other values of $\lambda$ stays below 45. We notice that, as we expected, the maximal number of cuts is lower for smaller values of $\lambda$.
<figure><img src="image_8.png" /><figcaption>Figure 3: Primal-dual gap</figcaption></figure>

In Figure 3, we show the primal-dual gap at each iteration for $\lambda \in \{0.05, 0.1, 1 - \sqrt{2} - \sqrt{2}, 0.5, 0.7\}$, in y-log scale. We can see that, numerically, our algorithm has a linear convergence speed for this problem. Also notice that, unlike the previous problem, the algorithm seems to converge faster for larger values of $\lambda$. We do not know the reason for this behavior.

<figure><img src="image_9.png" /><figcaption>Figure 4: Number of cuts at each iteration</figcaption></figure>

# 7 Conclusion and open problems

In this article, we proposed a Dualized Level-Set method for problems of the form

$$ \min_{x_1 \in \mathcal{E}_1} f(x_1) + \sigma_Q(Ax_1 - b) + \iota_K(x_1), $$

which we derived from an extension of the Level-Set method. We showed guarantees for the convergence of this algorithm. There are some improvement perspectives we can think of.

* Our experiments show better numerical convergence rates than we expected, which might be due to the specific form of these problems. This should not be surprising since some classical versions of the FWA are also known to have an improved convergence rate in some contexts, see for instance [6, Section 2.2].

* We assume that we are able to solve exactly our subproblems. An extension of our results could concern the situation where the problems are only solved up to a certain precision, as was done in [11] for the FWA.

* We chose to keep the parameter $\lambda$ fixed along the iterations. Our numerical results, in particular those done for the semidefinite program, show that the value of $\lambda$ may have a significant impact
<figure><img src="image_10.png" /><figcaption>Figure 3: Primal-dual gap</figcaption></figure>

In Figure 3, we show the primal-dual gap at each iteration for $\lambda \in \{0.05, 0.1, 1 - \sqrt{2} - \sqrt{2}, 0.5, 0.7\}$, in y-log scale. We can see that, numerically, our algorithm has a linear convergence speed for this problem. Also notice that, unlike the previous problem, the algorithm seems to converge faster for larger values of $\lambda$. We do not know the reason for this behavior.

<figure><img src="image_11.png" /><figcaption>Figure 4: Number of cuts at each iteration</figcaption></figure>

# 7 Conclusion and open problems

In this article, we proposed a Dualized Level-Set method for problems of the form

$$ \min_{x_1 \in \mathcal{E}_1} f(x_1) + \sigma_Q(Ax_1 - b) + \iota_K(x_1), $$

which we derived from an extension of the Level-Set method. We showed guarantees for the convergence of this algorithm. There are some improvement perspectives we can think of.

* Our experiments show better numerical convergence rates than we expected, which might be due to the specific form of these problems. This should not be surprising since some classical versions of the FWA are also known to have an improved convergence rate in some contexts, see for instance [6, Section 2.2].

* We assume that we are able to solve exactly our subproblems. An extension of our results could concern the situation where the problems are only solved up to a certain precision, as was done in [11] for the FWA.

* We chose to keep the parameter $\lambda$ fixed along the iterations. Our numerical results, in particular those done for the semidefinite program, show that the value of $\lambda$ may have a significant impact
on the efficiency of the algorithm. Future improvements may therefore concern variants of the algorithm in which $\lambda$ is adapted along the algorithm. For instance, we think our proof could be adapted if we take $0 < \lambda_{\min} \le \lambda \le \lambda_{\max} < 1$, with changes of $\lambda$ occurring only at critical iterations.

* The nonsmooth term in the cost function is restricted to be of the form $\sigma_Q(Ax - b)$, with $Q$ of a specific shape. A possible extension may deal with the case of a general nonsmooth term $g$. From an algorithmic point of view, this would lead to a more general projection problem, whose dual (Problem (33)) would involve the Moreau envelope of $g^*$. Yet some difficulties would arise in the extension of Lemma 4.11, whose proof heavily relies on the structure of the nonsmooth term.

* Our numerical experience shows that pruning rules are unavoidable. Indeed, an implementation of the algorithm which retains all cuts computed at each iteration quickly becomes intractable. Yet the pruning rule that we proposed is not completely satisfactory in so far as we do not have a priori bounds on the number of cuts which need to be stored. As was seen on Figure 2, the critical iterations may occur at diminishing frequency, leading to an accumulation of many cuts. In [13], the author develops a variant of the Level-Set method with a different pruning rule, for which the number of cuts to be stored is bounded by the dimension of the space. We expect that his method can be extended in the same manner as we extended the Level-Set method of [17].

## References

[1] Francis Bach. Learning with submodular functions: A convex optimization perspective. *Foundations and Trends in Machine Learning*, 6(2-3):145–373, 2013.

[2] Francis Bach. Duality between subgradient and conditional gradient methods. *SIAM J. Optim.*, 25(1):115–129, 2015.

[3] Heinz H Bauschke and Patrick L Combettes. *Convex analysis and monotone operator theory in Hilbert spaces*, volume 408. Springer, 2011.

[4] Amir Beck and Marc Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. *Operations Research Letters*, 31(3):167–175, 2003.

[5] Joseph-Frédéric Bonnans, Jean Charles Gilbert, Claude Lemaréchal, and Claudia A Sagastizábal. *Numerical optimization: theoretical and practical aspects*. Springer Science & Business Media, 2006.

[6] Gábor Braun, Alejandro Carderera, Cyrille W. Combettes, Hamed Hassani, Amin Karbasi, Aryan Mokhtari, and Sebastian Pokutta. Conditional gradient methods, 2023.

[7] Patrick L Combettes. Perspective functions: Properties, constructions, and examples. *Set-Valued and Variational Analysis*, 26:247–264, 2018.

[8] Rémi Flamary, Nicholas Courty, Davis Tuia, and Alain Rakotomamonjy. Optimal transport for domain adaptation. *IEEE Trans. Pattern Anal. Mach. Intell.*, 1(1-40):2, 2016.

[9] Marguerite Frank and Philip Wolfe. An algorithm for quadratic programming. *Naval Research Logistics Quarterly*, 3(1-2):95–110, 1956.

[10] Gauthier Gidel, Fabian Pedregosa, and Simon Lacoste-Julien. Frank-Wolfe splitting via augmented Lagrangian method. In *International Conference on Artificial Intelligence and Statistics*, pages 1456–1465. PMLR, 2018.

[11] Martin Jaggi. Revisiting Frank-Wolfe: Projection-free sparse convex optimization. In *International conference on machine learning*, pages 427–435. PMLR, 2013.

[12] Armand Joulin, Kevin Tang, and Li Fei-Fei. Efficient image and video co-localization with Frank-Wolfe algorithm. In *Computer Vision-ECCV 2014: 13th European Conference, Zurich, Switzerland, September 6-12, 2014, Proceedings, Part VI 13*, pages 253–268. Springer, 2014.

[13] Krzysztof C. Kiwiel. Proximal level bundle methods for convex nondifferentiable optimization, saddle-point problems and variational inequalities. *Math. Programming*, 69(1):89–109, 1995.
on the efficiency of the algorithm. Future improvements may therefore concern variants of the algorithm in which $\lambda$ is adapted along the algorithm. For instance, we think our proof could be adapted if we take $0 < \lambda_{\min} \le \lambda \le \lambda_{\max} < 1$, with changes of $\lambda$ occurring only at critical iterations.

* The nonsmooth term in the cost function is restricted to be of the form $\sigma_Q(Ax - b)$, with $Q$ of a specific shape. A possible extension may deal with the case of a general nonsmooth term $g$. From an algorithmic point of view, this would lead to a more general projection problem, whose dual (Problem (33)) would involve the Moreau envelope of $g^*$. Yet some difficulties would arise in the extension of Lemma 4.11, whose proof heavily relies on the structure of the nonsmooth term.

* Our numerical experience shows that pruning rules are unavoidable. Indeed, an implementation of the algorithm which retains all cuts computed at each iteration quickly becomes intractable. Yet the pruning rule that we proposed is not completely satisfactory in so far as we do not have a priori bounds on the number of cuts which need to be stored. As was seen on Figure 2, the critical iterations may occur at diminishing frequency, leading to an accumulation of many cuts. In [13], the author develops a variant of the Level-Set method with a different pruning rule, for which the number of cuts to be stored is bounded by the dimension of the space. We expect that his method can be extended in the same manner as we extended the Level-Set method of [17].

## References

[1] Francis Bach. Learning with submodular functions: A convex optimization perspective. *Foundations and Trends in Machine Learning*, 6(2-3):145–373, 2013.

[2] Francis Bach. Duality between subgradient and conditional gradient methods. *SIAM J. Optim.*, 25(1):115–129, 2015.

[3] Heinz H Bauschke and Patrick L Combettes. *Convex analysis and monotone operator theory in Hilbert spaces*, volume 408. Springer, 2011.

[4] Amir Beck and Marc Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. *Operations Research Letters*, 31(3):167–175, 2003.

[5] Joseph-Frédéric Bonnans, Jean Charles Gilbert, Claude Lemaréchal, and Claudia A Sagastizábal. *Numerical optimization: theoretical and practical aspects*. Springer Science & Business Media, 2006.

[6] Gábor Braun, Alejandro Carderera, Cyrille W. Combettes, Hamed Hassani, Amin Karbasi, Aryan Mokhtari, and Sebastian Pokutta. Conditional gradient methods, 2023.

[7] Patrick L Combettes. Perspective functions: Properties, constructions, and examples. *Set-Valued and Variational Analysis*, 26:247–264, 2018.

[8] Rémi Flamary, Nicholas Courty, Davis Tuia, and Alain Rakotomamonjy. Optimal transport for domain adaptation. *IEEE Trans. Pattern Anal. Mach. Intell.*, 1(1-40):2, 2016.

[9] Marguerite Frank and Philip Wolfe. An algorithm for quadratic programming. *Naval Research Logistics Quarterly*, 3(1-2):95–110, 1956.

[10] Gauthier Gidel, Fabian Pedregosa, and Simon Lacoste-Julien. Frank-Wolfe splitting via augmented Lagrangian method. In *International Conference on Artificial Intelligence and Statistics*, pages 1456–1465. PMLR, 2018.

[11] Martin Jaggi. Revisiting Frank-Wolfe: Projection-free sparse convex optimization. In *International conference on machine learning*, pages 427–435. PMLR, 2013.

[12] Armand Joulin, Kevin Tang, and Li Fei-Fei. Efficient image and video co-localization with Frank-Wolfe algorithm. In *Computer Vision-ECCV 2014: 13th European Conference, Zurich, Switzerland, September 6-12, 2014, Proceedings, Part VI 13*, pages 253–268. Springer, 2014.

[13] Krzysztof C. Kiwiel. Proximal level bundle methods for convex nondifferentiable optimization, saddle-point problems and variational inequalities. *Math. Programming*, 69(1):89–109, 1995.
[14] Karl Kunisch and Daniel Walter. On fast convergence rates for generalized conditional gradient methods with backtracking stepsize. *Numerical Algebra, Control and Optimization*, pages 0–0, 2022.

[15] Simon Lacoste-Julien, Martin Jaggi, Mark Schmidt, and Patrick Pletscher. Block-coordinate Frank-Wolfe optimization for structural SVMs. In *International Conference on Machine Learning*, pages 53–61. PMLR, 2013.

[16] Pierre Lavigne and Laurent Pfeiffer. Generalized conditional gradient and learning in potential mean field games. *Applied Mathematics & Optimization*, 88(3):89, 2023.

[17] Claude Lemaréchal, Arkadii Nemirovskii, and Yurii Nesterov. New variants of bundle methods. *Mathematical programming*, 69:111–147, 1995.

[18] Kang Liu and Laurent Pfeiffer. Mean field optimization problems: stability results and Lagrangian discretization. *arXiv preprint arXiv:2310.20037*, 2023.

[19] Sebastian Pokutta. The Frank-Wolfe algorithm: a short introduction. *Jahresbericht der Deutschen Mathematiker-Vereinigung*, pages 1–33, 2023.

[20] Antonio Silveti-Falls, Cesare Molinari, and Jalal Fadili. Generalized conditional gradient with augmented Lagrangian for composite minimization. *SIAM Journal on Optimization*, 30(4):2687–2725, January 2020.

[21] Elias Wirth, Thomas Kerdreux, and Sebastian Pokutta. Acceleration of Frank-Wolfe algorithms with open-loop step-sizes. In *International Conference on Artificial Intelligence and Statistics*, pages 77–100. PMLR, 2023.

[22] Alp Yurtsever, Olivier Fercoq, and Volkan Cevher. A conditional-gradient-based augmented Lagrangian framework. In *International Conference on Machine Learning*, pages 7272–7281. PMLR, 2019.

[23] Constantin Zălinescu. Convex analysis in general vector spaces. World Scientific Publishing Co., Inc., River Edge, NJ, 2002.

[24] Song Zhou, Swati Gupta, and Madeleine Udell. Limited memory Kelley's method converges for composite convex and submodular objectives. *Advances in Neural Information Processing Systems*, 31, 2018.
[14] Karl Kunisch and Daniel Walter. On fast convergence rates for generalized conditional gradient methods with backtracking stepsize. *Numerical Algebra, Control and Optimization*, pages 0–0, 2022.

[15] Simon Lacoste-Julien, Martin Jaggi, Mark Schmidt, and Patrick Pletscher. Block-coordinate Frank-Wolfe optimization for structural SVMs. In *International Conference on Machine Learning*, pages 53–61. PMLR, 2013.

[16] Pierre Lavigne and Laurent Pfeiffer. Generalized conditional gradient and learning in potential mean field games. *Applied Mathematics & Optimization*, 88(3):89, 2023.

[17] Claude Lemaréchal, Arkadii Nemirovskii, and Yurii Nesterov. New variants of bundle methods. *Mathematical programming*, 69:111–147, 1995.

[18] Kang Liu and Laurent Pfeiffer. Mean field optimization problems: stability results and Lagrangian discretization. *arXiv preprint arXiv:2310.20037*, 2023.

[19] Sebastian Pokutta. The Frank-Wolfe algorithm: a short introduction. *Jahresbericht der Deutschen Mathematiker-Vereinigung*, pages 1–33, 2023.

[20] Antonio Silveti-Falls, Cesare Molinari, and Jalal Fadili. Generalized conditional gradient with augmented Lagrangian for composite minimization. *SIAM Journal on Optimization*, 30(4):2687–2725, January 2020.

[21] Elias Wirth, Thomas Kerdreux, and Sebastian Pokutta. Acceleration of Frank-Wolfe algorithms with open-loop step-sizes. In *International Conference on Artificial Intelligence and Statistics*, pages 77–100. PMLR, 2023.

[22] Alp Yurtsever, Olivier Fercoq, and Volkan Cevher. A conditional-gradient-based augmented Lagrangian framework. In *International Conference on Machine Learning*, pages 7272–7281. PMLR, 2019.

[23] Constantin Zălinescu. Convex analysis in general vector spaces. World Scientific Publishing Co., Inc., River Edge, NJ, 2002.

[24] Song Zhou, Swati Gupta, and Madeleine Udell. Limited memory Kelley's method converges for composite convex and submodular objectives. *Advances in Neural Information Processing Systems*, 31, 2018.