Restarting Frank–Wolfe: Faster Rates under Hölderian Error Bounds

Abstract

Conditional gradient algorithms (aka Frank–Wolfe algorithms) form a classical set of methods for constrained smooth convex minimization due to their simplicity, the absence of projection steps, and competitive numerical performance. While the vanilla Frank–Wolfe algorithm only ensures a worst-case rate of ${\mathcal {O}}(1/\epsilon )$, various recent results have shown that for strongly convex functions on polytopes, the method can be slightly modified to achieve linear convergence. However, this still leaves a huge gap between sublinear ${\mathcal {O}}(1/\epsilon )$ convergence and linear ${\mathcal {O}}(\log 1/\epsilon )$ convergence to reach an $\epsilon$-approximate solution. Here, we present a new variant of conditional gradient algorithms that can dynamically adapt to the function’s geometric properties using restarts and smoothly interpolates between the sublinear and linear regimes. These interpolated convergence rates are obtained when the optimization problem satisfies a new type of error bounds, which we call strong Wolfe primal bounds. They combine geometric information on the constraint set with Hölderian error bounds on the objective function.

Appendices

Appendix A. One Shot Application of the Fractional Away-Step Frank–Wolfe

Fractional Away-step Frank–Wolfe output a point $x_t\in {\mathcal {C}}$ s.t. $w(x_t) \le e^{-\gamma }w_0$. Hence, running once fractional Away-step Frank–Wolfe with a large value of $\gamma$ allows finding an approximate minimizer with the desired precision. The following lemma proves a sublinear ${\mathcal {O}}(1/T)$ convergence rate which corresponds to the convergence rate of the Frank–Wolfe algorithm. Importantly, the rate does not depend on r. Hence, there is no hope of observing linear convergence for the strongly convex case.

Lemma A.1

Let f be a smooth convex function, $\epsilon > 0$ be a target accuracy, and $x_0 \in {\mathcal {C}}$ be an initial point. Then for any $\gamma > \ln \frac{w(x_0)}{ \epsilon }$, Algorithm 1 satisfies:

$$\begin{aligned} f(x_T) - f^* \le \epsilon , \end{aligned}$$

for $T \ge \frac{2C_f^{{\mathcal {A}}}}{\epsilon }$.

Proof

We can stop the algorithm as soon as the criterion $w(x_t) < \epsilon$ in step 2 is met or we observe an away step, whichever comes first. In former case, we have $f(x_t) - f^* \le w(t) < \epsilon$, in the latter it holds

$$\begin{aligned} f(x_t) - f^* \le -\nabla f(x_t)(d_t^{FW}) \le \epsilon /2 < \epsilon . \end{aligned}$$

Thus, when the algorithms stops, we have achieved the target accuracy and it suffices to bound the number of iterations required to achieve that accuracy. Moreover, while running, the algorithm only executes Frank–Wolfe and we drop the FW superscript in the directions; otherwise, we would have stopped.

From the proof of Proposition 4.1, we have each Frank–Wolfe step ensures progress of the form

$$\begin{aligned} f(x_t) - f(x_{t+1}) \ge {\left\{ \begin{array}{ll} \frac{\langle -\nabla f(x_t), \, d_t \rangle ^2}{2C_f^{{\mathcal {A}}}} &{} \text { if } \langle -\nabla f(x_t), \, d_t \rangle \le C_f^{{\mathcal {A}}} \\ \langle -\nabla f(x_t), \, d_t \rangle - C_f^{{\mathcal {A}}} / 2 &{} \text {otherwise}. \end{array}\right. } \end{aligned}$$

For convenience, let $h_t \triangleq f(x_t) - f^*$. By convexity, we have $h_t \le \langle -\nabla f(x_t), \, d_t \rangle$, so that the above becomes

$$\begin{aligned} f(x_t) - f(x_{t+1}) \ge {\left\{ \begin{array}{ll} \frac{h_t^2}{2C_f^{{\mathcal {A}}}} &{} \text { if } h_t \le C_f^{{\mathcal {A}}} \\ h_t - C_f^{{\mathcal {A}}} / 2 &{} \text { otherwise}. \end{array}\right. }, \end{aligned}$$

and moreover observe that the second case can only happen in the very first step: $h_{1} \le h_0 - (h_0 - C_f^{{\mathcal {A}}} / 2) = C_f^{{\mathcal {A}}} / 2 \le 2 C_f^{{\mathcal {A}}} / t$ for $t=1$ providing the start of the following induction: we claim $h_t \le \frac{2C_f^{{\mathcal {A}}}}{t}$.

Suppose we have established the bound for t, then for $t+1$, we have

$$\begin{aligned} h_{t+1} \le \left( 1-\frac{h_t}{2 C_f^{{\mathcal {A}}}}\right) h_t \le \frac{2C_f^{{\mathcal {A}}}}{t} - \frac{2C_f^{{\mathcal {A}}}}{t^2} \le \frac{2C_f^{{\mathcal {A}}}}{t+1}. \end{aligned}$$

The induction is complete and it follows that the algorithm requires $T \ge \frac{2C_f^{{\mathcal {A}}}}{\epsilon }$ to reach $\epsilon$-accuracy. $\square$

Appendix B. Non-Standard Recurrence Relation

This is a technical Lemma derived in [47, proof of Theorem 1. ], and we repeat it here for the sake of completeness. It is used in Sect. 7.

Lemma B.1

(Recurrence and sub-linear rates) Consider a sequence $(h_n)$ of non-negative numbers. Assume there exists $M>0$ and $0 < \beta \le 1$ s.t.

$$\begin{aligned} h_{t+1} \le h_t ~\text {max}\{1/2, 1 - M h_t^{\beta } \}, \end{aligned}$$

(20)

then $h_T = {\mathcal {O}}\big (1/T^{1/\beta } \big )$. More precisely for all $t\ge 0$,

$$\begin{aligned} h_t \le \frac{C}{(t+k)^{1/\beta }} \end{aligned}$$

with (k, C) such that $\frac{2 - 2^{\beta }}{2^\beta -1} \le k$ and $\text {max}\{h_0 k^{1/\beta }, 2(C^\prime /M)^{1/\beta }\} \le C$, with $C^\prime \ge \frac{1}{\beta -(1-\beta )(2^\beta -1)}$.

Proof

Let (k, C) satisfying the condition in Lemma B.1. Let us show by induction that

$$\begin{aligned} h_t \le \frac{C}{(t+k)^{1/\beta }}~. \end{aligned}$$

For $t=0$, it is true because we assumed $h_0 k^{1/\beta } \le C$. Let $t \ge 1$. Consider the case where the maximum in the right hand side of (20) is obtained with $\frac{1}{2}$, then

$$\begin{aligned} h_{t+1}\le & {} \frac{C}{(t+k+1)^{1/\beta }} \Big (\frac{t+k+1}{t+k}\Big )^{1/\beta } \frac{1}{2}\\\le & {} \frac{C}{(t+k+1)^{1/\beta }}, \end{aligned}$$

because $k\ge \frac{2 - 2^{\beta }}{2^\beta - 1}$. Otherwise we have

$$\begin{aligned} h_{t+1} \le h_t (1 - M h_t^{\beta }). \end{aligned}$$

If $h_t \le \frac{C}{2(t+k)^{1/\beta }}$, conclusion holds as before. Otherwise, assume $\frac{C}{2(t+k)^{1/\beta }} \le h_t \le \frac{C}{(t+k)^{1/\beta }}$ and (20) implies

$$\begin{aligned} h_{t+1}\le & {} \frac{C}{(t+k)^{1/\beta }} \Big ( 1 - M \Big (\frac{C}{2}\Big )^{\beta } \frac{1}{t+k}\Big )\\ h_{t+1}\le & {} \frac{C}{(t+k+1)^{1/\beta }} \Big (1 + \frac{1}{t+k}\Big )^{1/\beta }\Big ( 1 - M \Big (\frac{C}{2}\Big )^{\beta } \frac{1}{t+k}\Big ) \end{aligned}$$

From Lemma B.2, for $C\ge 2(C^\prime /M)^{1/\beta }$ with $C^\prime \ge \frac{1}{\beta -(1-\beta )(2^\beta -1)}$, we have

$$\begin{aligned} h_{t+1} \le \frac{C}{(t+k+1)^{1/\beta }} \Big (1 + \frac{C^\prime }{t+k}\Big )\Big ( 1 - \frac{C^\prime }{t+k}\Big ) \le \frac{C}{(t+k+1)^{1/\beta }}~, \end{aligned}$$

which proves the induction. $\square$

Lemma B.2

For any $t\ge 1$, we have

$$\begin{aligned} \Big (1+ \frac{1}{t+k}\Big )^{1/\beta } \Big (1 - M \Big (\frac{C}{2}\Big )^\beta \frac{1}{t+k}\Big ) \le \Big (1 + \frac{C^\prime }{t+k}\Big )\Big (1 - \frac{C^\prime }{t+k}\Big ), \end{aligned}$$

(21)

where $k\ge \frac{2 - 2^{\beta }}{2^\beta - 1}$, $\beta \in ]0,1]$, $C^\prime \ge \frac{1}{\beta -(1-\beta )(2^\beta -1)}$ and C such that $C\ge 2 (C^\prime /M)^{1/\beta }$.

Proof

Write $x = \frac{1}{t+k}$. Because $t\ge 1$ and $k\ge \frac{2 - 2^{\beta }}{2^\beta - 1}$, we have $x\in ]0, 2^{\beta }-1]$. (21) is equivalent to

$$\begin{aligned} \frac{1}{\beta }\log (1+ \frac{1}{t+k}) + \log (1 - M \Big (\frac{C}{2}\Big )^\beta x) \le \log (1 + C^\prime x) + \log (1 - C^\prime x) \end{aligned}$$

Choosing C greater or equal to $2 \Big (C^\prime /M\Big )^{1/\beta }$ ensures that $\log (1 - M \Big (\frac{C}{2}\Big )^\beta x)\le \log (1 - C^\prime x)$. Also for $C^\prime \ge \frac{1}{\beta -(1-\beta )(2^\beta -1)}$, the function $h(x)\triangleq \log (1 + C^\prime x) - \frac{1}{\beta }\log (1 + x)$ is non-decreasing (and hence nonnegative) on $]0,2^\beta -1]$. Reciprocally for $C^\prime \ge \frac{1}{\beta -(1-\beta )(2^\beta -1)}$ and $C\ge \Big (C^\prime /M\Big )^{1/\beta }$, (21) holds. $\square$