Catalyst Acceleration for First-order Convex Optimization: from Theory to Practice

Introduction

A large number of machine learning and signal processing problems are formulated as the minimization of a convex objective function:

where $f_{0}$ is convex and $L$-smooth, and $\psi$ is convex but may not be differentiable. We call a function $L$-smooth when it is differentiable and its gradient is $L$-Lipschitz continuous.

In statistics or machine learning, the variable $x$ may represent model parameters, and the role of $f_{0}$ is to ensure that the estimated parameters fit some observed data. Specifically, $f_{0}$ is often a large sum of functions and (1) is a regularized empirical risk which writes as

We present a unified framework allowing one to accelerate gradient-based or first-order methods, with a particular focus on problems involving large sums of functions. By “accelerating”, we mean generalizing a mechanism invented by Nesterov (1983) that improves the convergence rate of the gradient descent algorithm. When $\psi=0$, gradient descent steps produce iterates $(x_{k})_{k\geq 0}$ such that $f(x_{k})-f^{*}\leq\varepsilon$ in $O(1/\varepsilon)$ iterations, where $f^{*}$ denotes the minimum value of $f$. Furthermore, when the objective $f$ is $\mu$-strongly convex, the previous iteration-complexity becomes $O(\left(L/\mu)\log(1/\varepsilon)\right)$, which is proportional to the condition number $L/\mu$. However, these rates were shown to be suboptimal for the class of first-order methods, and a simple strategy of taking the gradient step at a well-chosen point different from $x_{k}$ yields the optimal complexity—$O(1/\sqrt{\varepsilon})$ for the convex case and $O(\sqrt{L/\mu}\log(1/\varepsilon))$ for the $\mu$-strongly convex one (Nesterov, 1983). Later, this acceleration technique was extended to deal with non-differentiable penalties $\psi$ for which the proximal operator defined below is easy to compute (Beck and Teboulle, 2009; Nesterov, 2013).

where $\|.\|$ denotes the Euclidean norm.

For machine learning problems involving a large sum of $n$ functions, a recent effort has been devoted to developing fast incremental algorithms such as SAG (Schmidt et al., 2017), SAGA (Defazio et al., 2014a), SDCA (Shalev-Shwartz and Zhang, 2012), SVRG (Johnson and Zhang, 2013; Xiao and Zhang, 2014), or MISO/Finito (Mairal, 2015; Defazio et al., 2014b), which can exploit the particular structure (2). Unlike full gradient approaches, which require computing and averaging $n$ gradients $(1/n)\sum_{i=1}^{n}\nabla f_{i}(x)$ at every iteration, incremental techniques have a cost per-iteration that is independent of $n$. The price to pay is the need to store a moderate amount of information regarding past iterates, but the benefits may be significant in terms of computational complexity. In order to achieve an $\varepsilon$-accurate solution for a $\mu$-strongly convex objective, the number of gradient evaluations required by the methods mentioned above is bounded by $O\left(\left(n+\frac{\bar{L}}{\mu}\right)\log(\frac{1}{\varepsilon})\right)$, where $\bar{L}$ is either the maximum Lipschitz constant across the gradients $\nabla f_{i}$, or the average value, depending on the algorithm variant considered. Unless there is a big mismatch between $\bar{L}$ and $L$ (global Lipschitz constant for the sum of gradients), incremental approaches significantly outperform the full gradient method, whose complexity in terms of gradient evaluations is bounded by $O\left(n\frac{L}{\mu}\log(\frac{1}{\varepsilon})\right)$.

Yet, these incremental approaches do not use Nesterov’s extrapolation steps and whether or not they could be accelerated was an important open question when these methods were introduced. It was indeed only known to be the case for SDCA (Shalev-Shwartz and Zhang, 2016) for strongly convex objectives. Later, other accelerated incremental algorithms were proposed such as Katyusha (Allen-Zhu, 2017), or the method of Lan and Zhou (2017).

Some approaches such as MISO, SDCA, or SVRG are only defined for strongly convex objectives. A classical trick to apply them to general convex functions is to add a small regularization term $\varepsilon\|x\|^{2}$ in the objective (Shalev-Shwartz and Zhang, 2012). The drawback of this strategy is that it requires choosing in advance the parameter $\varepsilon$, which is related to the target accuracy. The approach we present here provides a direct support for non-strongly convex objectives, thus removing the need of selecting $\varepsilon$ beforehand. Moreover, we can immediately establish a faster rate for the resulting algorithm. Finally, some methods such as MISO are numerically unstable when they are applied to strongly convex objective functions with small strong convexity constant. By defining better conditioned auxiliary subproblems, Catalyst also provides better numerical stability to these methods.

A short version of this paper has been published at the NIPS conference in 2015 (Lin et al., 2015a); in addition to simpler convergence proofs and more extensive numerical evaluation, we extend the conference paper with a new Moreau-Yosida smoothing interpretation with significant theoretical and practical consequences as well as new practical stopping criteria and warm-start strategies.

The paper is structured as follows. We complete this introductory section with some related work in Section 1.1, and give a short description of the two-loop Catalyst algorithm in Section 1.2. Then, Section 2 introduces the Moreau-Yosida smoothing and its inexact variant. In Section 3, we introduce formally the main algorithm, and its convergence analysis is presented in Section 4. Section 5 is devoted to numerical experiments and Section 6 concludes the paper.

Catalyst can be interpreted as a variant of the proximal point algorithm (Rockafellar, 1976; Güler, 1991), which is a central concept in convex optimization, underlying augmented Lagrangian approaches, and composite minimization schemes (Bertsekas, 2015; Parikh and Boyd, 2014). The proximal point algorithm consists of solving (1) by minimizing a sequence of auxiliary problems involving a quadratic regularization term. In general, these auxiliary problems cannot be solved with perfect accuracy, and several notions of inexactness were proposed by Güler (1992); He and Yuan (2012) and Salzo and Villa (2012). The Catalyst approach hinges upon (i) an acceleration technique for the proximal point algorithm originally introduced in the pioneer work of Güler (1992); (ii) a more practical inexactness criterion than those proposed in the past.Note that our inexact criterion was also studied, among others, by Salzo and Villa (2012), but their analysis led to the conjecture that this criterion was too weak to warrant acceleration. Our analysis refutes this conjecture. As a result, we are able to control the rate of convergence for approximately solving the auxiliary problems with an optimization method $\mathcal{M}$. In turn, we are also able to obtain the computational complexity of the global procedure, which was not possible with previous analysis (Güler, 1992; He and Yuan, 2012; Salzo and Villa, 2012). When instantiated in different first-order optimization settings, our analysis yields systematic acceleration.

Beyond Güler (1992), several works have inspired this work. In particular, accelerated SDCA (Shalev-Shwartz and Zhang, 2016) is an instance of an inexact accelerated proximal point algorithm, even though this was not explicitly stated in the original paper. Catalyst can be seen as a generalization of their algorithm, originally designed for stochastic dual coordinate ascent approaches. Yet their proof of convergence relies on different tools than ours. Specifically, we introduce an approximate sufficient descent condition, which, when satisfied, grants acceleration to any optimization method, whereas the direct proof of Shalev-Shwartz and Zhang (2016), in the context of SDCA, does not extend to non-strongly convex objectives. Another useful methodological contribution was the convergence analysis of inexact proximal gradient methods of Schmidt et al. (2011) and Devolder et al. (2014). Finally, similar ideas appeared in the independent work (Frostig et al., 2015). Their results partially overlap with ours, but the two papers adopt rather different directions. Our analysis is more general, covering both strongly-convex and non-strongly convex objectives, and comprises several variants including an almost parameter-free variant.

Then, beyond accelerated SDCA (Shalev-Shwartz and Zhang, 2016), other accelerated incremental methods have been proposed, such as APCG (Lin et al., 2015b), SDPC (Zhang and Xiao, 2015), RPDG (Lan and Zhou, 2017), Point-SAGA (Defazio, 2016) and Katyusha (Allen-Zhu, 2017). Their techniques are algorithm-specific and cannot be directly generalized into a unified scheme. However, we should mention that the complexity obtained by applying Catalyst acceleration to incremental methods matches the optimal bound up to a logarithmic factor, which may be the price to pay for a generic acceleration scheme.

A related recent line of work has also combined smoothing techniques with outer-loop algorithms such as Quasi-Newton methods (Themelis et al., 2016; Giselsson and Fält, 2016). Their purpose was not to accelerate existing techniques, but rather to derive new algorithms for nonsmooth optimization.

To conclude this survey, we mention the broad family of extrapolation methods (Sidi, 2017), which allow one to extrapolate to the limit sequences generated by iterative algorithms for various numerical analysis problems. Scieur et al. (2016) proposed such an approach for convex optimization problems with smooth and strongly convex objectives. The approach we present here allows us to obtain global complexity bounds for strongly convex and non strongly convex objectives, which can be decomposed into a smooth part and a non-smooth proximal-friendly part.

2 Overview of Catalyst

Before introducing Catalyst precisely in Section 3, we give a quick overview of the algorithm and its main ideas. Catalyst is a generic approach that wraps an algorithm $\mathcal{M}$ into an accelerated one $\mathcal{A}$, in order to achieve the same accuracy as $\mathcal{M}$ with reduced computational complexity. The resulting method $\mathcal{A}$ is an inner-outer loop construct, presented in Algorithm 1, where in the inner loop the method $\mathcal{M}$ is called to solve an auxiliary strongly-convex optimization problem, and where in the outer loop the sequence of iterates produced by $\mathcal{M}$ are extrapolated for faster convergence.

There are therefore three main ingredients in Catalyst: a) a smoothing technique that produces strongly-convex sub-problems; b) an extrapolation technique to accelerate the convergence; c) a balancing principle to optimally tune the inner and outer computations.

Catalyst can be used on any algorithm $\mathcal{M}$ that enjoys a linear-convergence guarantee when minimizing strongly-convex objectives. However the objective at hand may be poorly conditioned or even might not be strongly convex. In Catalyst, we use $\mathcal{M}$ to approximately minimize an auxiliary objective $h_{k}$ at iteration $k$, defined in (4), which is strongly convex and better conditioned than $f$. Smoothing by infimal convolution allows one to build a well-conditioned convex function $F$ from a poorly-conditioned convex function $f$ (see Section 3 for a refresher on Moreau envelopes). We shall show in Section 3 that a notion of approximate Moreau envelope allows us to define precisely the information collected when approximately minimizing the auxiliary objective.

Catalyst uses an extrapolation scheme “ à la Nesterov ” to build a sequence $(y_{k})_{k\geq 0}$ updated as

where $(\beta_{k})_{k\geq 0}$ is a positive decreasing sequence, which we shall define in Section 3.

We shall show in Section 4 that we can get faster rates of convergence thanks to this extrapolation step when the smoothing parameter $\kappa$, the inner-loop stopping criterion, and the sequence $(\beta_{k})_{k\geq 0}$ are carefully built.

The optimal balance between inner loop and outer loop complexity derives from the complexity bounds established in Section 4. Given an estimate about the condition number of $f$, our bounds dictate a choice of $\kappa$ that gives the optimal setting for the inner-loop stopping criterion and all technical quantities involved in the algorithm. We shall demonstrate in particular the power of an appropriate warm-start strategy to achieve near-optimal complexity.

Finally, we provide in Table 1 a brief overview of the complexity results obtained from the Catalyst acceleration, when applied to various optimization methods $\mathcal{M}$ for minimizing a large finite sum of $n$ functions. Note that the complexity results obtained with Catalyst are optimal, up to some logarithmic factors (see Agarwal and Bottou, 2015; Arjevani and Shamir, 2016; Woodworth and Srebro, 2016).

The Moreau Envelope and its Approximate Variant

In this section, we recall a classical tool from convex analysis called the Moreau envelope or Moreau-Yosida smoothing (Moreau, 1962; Yosida, 1980), which plays a key role for understanding the Catalyst acceleration. This tool can be seen as a smoothing technique, which can turn any convex lower semicontinuous function $f$ into a smooth function, and an ill-conditioned smooth convex function into a well-conditioned smooth convex function.

The Moreau envelope results from the infimal convolution of $f$ with a quadratic penalty:

where $\kappa$ is a positive regularization parameter. The proximal operator is then the unique minimizer of the problem—that is,

Note that $p(x)$ does not admit a closed form in general. Therefore, computing it requires to solve the sub-problem to high accuracy with some iterative algorithm.

The smoothing effect of the Moreau regularization can be characterized by the next proposition (see Lemaréchal and Sagastizábal, 1997, for elementary proofs).

Given a convex continuous function $f$ and a regularization parameter $\kappa>0$, consider the Moreau envelope $F$ defined in (5). Then,

$F$ is convex and minimizing $f$ and $F$ are equivalent in the sense that

Moreover the solution set of the two above problems coincide with each other.

$F$ is continuously differentiable even when $f$ is not and

Moreover the gradient $\nabla F$ is Lipschitz continuous with constant $L_{F}=\kappa$.

If $f$ is $\mu$-strongly convex, then $F$ is $\mu_{F}$-strongly convex with $\mu_{F}=\frac{\mu\kappa}{\mu+\kappa}.$

Interestingly, $F$ is friendly from an optimization point of view as it is convex and differentiable. Besides, $F$ is $\kappa$-smooth with condition number $\frac{\mu+\kappa}{\mu}$ when $f$ is $\mu$-strongly convex. Thus $F$ can be made arbitrarily well conditioned by choosing a small $\kappa$. Since both functions $f$ and $F$ admit the same solutions, a naive approach to minimize a non-smooth function $f$ is to first construct its Moreau envelope $F$ and then apply a smooth optimization method on it. As we will see next, Catalyst can be seen as an accelerated gradient descent technique applied to $F$ with inexact gradients.

2 A Fresh Look at Catalyst

First-order methods applied to $F$ provide us several well-known algorithms.

By noticing that $\nabla F(x_{k})=\kappa(x_{k}-p(x_{k}))$ and $L_{f}=\kappa$, we obtain in fact

which is exactly the proximal point algorithm (Martinet, 1970; Rockafellar, 1976).

If gradient descent steps on $F$ yields the proximal point algorithm, it is then natural to consider the following sequence

where $\beta_{k+1}$ is Nesterov’s extrapolation parameter (Nesterov, 2004). Again, by using the closed form of the gradient, this is equivalent to the update

which is known as the accelerated proximal point algorithm of Güler (1992).

While these algorithms are conceptually elegant, they suffer from a major drawback in practice: each update requires to evaluate the proximal operator $p(x)$. Unless a closed form is available, which is almost never the case, we are not able to evaluate $p(x)$ exactly. Hence an iterative algorithm is required for each evaluation of the proximal operator which leads to the inner-outer construction (see Algorithm 1). Catalyst can then be interpreted as an accelerated proximal point algorithm that calls an optimization method $\mathcal{M}$ to compute inexact solutions to the sub-problems. The fact that such a strategy could be used to solve non-smooth optimization problems was well-known, but the fact that it could be used for acceleration is more surprising. The main challenge that will be addressed in Section 3 is how to control the complexity of the inner-loop minimization.

3 The Approximate Moreau Envelope

Since Catalyst uses inexact gradients of the Moreau envelope, we start with specifying the inexactness criteria.

Given a proximal center $x$, a smoothing parameter $\kappa$, and an accuracy $\varepsilon\!>\!0$, we denote the set of $\varepsilon$-approximations of the proximal operator $p(x)$ by

and $h^{*}$ is the minimum function value of $h$.

Checking whether $h(z)-h^{*}\leq\varepsilon$ may be impactical since $h^{*}$ is unknown in many situations. We may then replace $h^{*}$ by a lower bound that can be computed more easily. We may use the Fenchel conjugate for instance. Then, given a point $z$ and a lower-bound $d(z)\leq h^{*}$, we can guarantee $z\in p^{\>\!\varepsilon}(x)$ if $h(z)-d(z)\leq\varepsilon$. There are other choices for the lower bounding function $d$ which result from the specific construction of the optimization algorithm. For instance, dual type algorithms such as SDCA (Shalev-Shwartz and Zhang, 2012) or MISO (Mairal, 2015) maintain a lower bound along the iterations, allowing one to compute $h(z)-d(z)\leq\varepsilon$.

When none of the options mentioned above are available, we can use the following fact, based on the notion of gradient mapping; see Section 2.3.2 of (Nesterov, 2004). The intuition comes from the smooth case: when $h$ is smooth, the strong convexity yields

In other words, the norm of the gradient provides enough information to assess how far we are from the optimum. From this perspective, the gradient mapping can be seen as an extension of the gradient for the composite case where the objective decomposes as a sum of a smooth part and a non-smooth part (Nesterov, 2004).

Consider a proximal center $x$, a smoothing parameter $\kappa$ and an accuracy $\varepsilon>0$. Consider an objective with the composite form (1) and we set function $h$ as

Then, the gradient mapping of $h$ at $z$ is defined by $\frac{1}{\eta}(z-[z]_{\eta})$ and

The proof is given in Appendix B. The lemma shows that it is sufficient to check the norm of the gradient mapping to ensure condition (C1). However, this requires an additional full gradient step and proximal step at each iteration.

As soon as we have an approximate proximal operator $z$ in $p^{\>\!\varepsilon}(x)$ in hand, we can define an approximate gradient of the Moreau envelope,

by mimicking the exact gradient formula $\nabla F(x)=\kappa(x-p(x))$. As a consequence, we may immediately draw a link

where the first implication is a consequence of the strong convexity of $h$ at its minimum $p(x)$. We will then apply the approximate gradient $g$ instead of $\nabla F$ to build the inexact proximal point algorithm. Since the inexactness of the approximate gradient can be bounded by an absolute value $\sqrt{2\kappa\varepsilon}$, we call (C1) the absolute accuracy criterion.

Another natural way to bound the gradient approximation is by using a relative error, namely in the form $\|g(z)-\nabla F(x)\|\leq\delta^{\prime}\|\nabla F(x)\|$ for some $\delta^{\prime}>0$. This leads us to the following inexactness criterion.

Given a proximal center $x$, a smoothing parameter $\kappa$ and a relative accuracy $\delta$ in $[0,1)$, we denote the set of $\delta$-relative approximations by

At a first glance, we may interpret the criterion (C2) as (C1) by setting $\varepsilon=\frac{\delta\kappa}{2}\|x-z\|^{2}$. But we should then notice that the accuracy depends on the point $z$, which is is no longer an absolute constant. In other words, the accuracy varies from point to point, which is proportional to the squared distance between $z$ and $x$. First one may wonder whether $g^{\>\!\delta}(x)$ is an empty set. Indeed, it is easy to see that $p(x)\in g^{\>\!\delta}(x)$ since $h(p(x))-h^{*}=0\leq\frac{\delta\kappa}{2}\|x-p(x)\|^{2}$. Moreover, by continuity, $g^{\>\!\delta}(x)$ is closed set around $p(x)$. Then, by following similar steps as in (9), we have

By defining the approximate gradient in the same way $g(z)=\kappa(x-z)$ yields,

which is the desired relative gradient approximation.

Finally, the discussion about bounding $h(z)-h^{*}$ still holds here. In particular, Lemma 2 may be used by setting the value $\varepsilon=\frac{\delta\kappa}{2}\|x-z\|^{2}$. The price to pay is as an additional gradient step and an additional proximal step per iteration.

Inexactness criteria with respect to subgradient norms have been investigated in the past, starting from the pioneer work of Rockafellar (1976) in the context of the inexact proximal point algorithm. Later, different works have been dedicated to more practical inexactness criteria (Auslender, 1987; Correa and Lemaréchal, 1993; Solodov and Svaiter, 2001; Fuentes et al., 2012). These criteria include duality gap, $\varepsilon$-subdifferential, or decrease in terms of function value. Here, we present a more intuitive point of view using the Moreau envelope.

While the proximal point algorithm has caught a lot of attention, very few works have focused on its accelerated variant. The first accelerated proximal point algorithm with inexact gradients was proposed by Güler (1992). Then, Salzo and Villa (2012) proposed a more rigorous convergence analysis, and more inexactness criteria, which are typically stronger than ours. In the same way, a more general inexact oracle framework has been proposed later by Devolder et al. (2014). To achieve the Catalyst acceleration, our main effort was to propose and analyze criteria that allow us to control the complexity for finding approximate solutions of the sub-problems.

Catalyst Acceleration

Catalyst is presented in Algorithm 2. As discussed in Section 2, this scheme can be interpreted as an inexact accelerated proximal point algorithm, or equivalently as an accelerated gradient descent method applied to the Moreau envelope of the objective with inexact gradients. Since an overview has already been presented in Section 1.2, we now present important details to obtain acceleration in theory and in practice.

One of the main characteristic of Catalyst is to apply the method $\mathcal{M}$ to strongly-convex sub-problems, without requiring strong convexity of the objective $f$. As a consequence, Catalyst provides direct support for convex but non-strongly convex objectives to $\mathcal{M}$, which may be useful to extend the scope of application of techniques that need strong convexity to operate. Yet, Catalyst requires solving these sub-problems efficiently enough in order to control the complexity of the inner-loop computations. When applying $\mathcal{M}$ to minimize a strongly-convex function $h$, we assume that $\mathcal{M}$ is able to produce a sequence of iterates $(z_{t})_{t\geq 0}$ such that

where $z_{0}$ is the initial point given to $\mathcal{M}$, and $\tau_{\mathcal{M}}$ in $(0,1)$, $C_{\mathcal{M}}>0$ are two constants. In such a case, we say that $\mathcal{M}$ admits a linear convergence rate. The quantity $\tau_{\mathcal{M}}$ controls the speed of convergence for solving the sub-problems: the larger is $\tau_{\mathcal{M}}$, the faster is the convergence. For a given algorithm $\mathcal{M}$, the quantity $\tau_{\mathcal{M}}$ depends usually on the condition number of $h$. For instance, for the proximal gradient method and many first-order algorithms, we simply have $\tau_{\mathcal{M}}=O((\mu+\kappa)/(L+\kappa))$, as $h$ is $(\mu+\kappa)$-strongly convex and $(L+\kappa)$-smooth. Catalyst can also be applied to randomized methods $\mathcal{M}$ that satisfy (12) in expectation:

Then, the complexity results of Section 4 also hold in expectation. This allows us to apply Catalyst to randomized block coordinate descent algorithms (see Richtárik and Takáč, 2014, and references therein), and some incremental algorithms such as SAG, SAGA, or SVRG. For other methods that admit a linear convergence rates in terms of duality gap, such as SDCA, MISO/Finito, Catalyst can also be applied as explained in Appendix C.

Catalyst may be used with three types of stopping criteria for solving the inner-loop problems. We now detail them below.

Besides linear convergence rate, an adequate warm-start strategy needs to be used to guarantee that the sub-problems will be solved in reasonable computational time. The intuition is that the previous solution may still be a good approximation of the current subproblem. Specifically, the following choices arise from the convergence analysis that will be detailed in Section 4.

𝑘1(k+1)-th subproblem $h_{k+1}(z)=f(z)+\frac{\kappa}{2}\|z-y_{k}\|^{2}$, we warm start the optimization method $\mathcal{M}$ at $z_{0}$ as following: (a) when using criterion (C1) to find $x_{k+1}$ in $p^{\>\!\varepsilon_{k}}(y_{k})$, – if $f$ is smooth ($\psi=0$), then choose $z_{0}=x_{k}+\frac{\kappa}{\kappa+\mu}(y_{k}-y_{k-1})$. – if $f$ is composite as in (1), then define $w_{0}=x_{k}+\frac{\kappa}{\kappa+\mu}(y_{k}-y_{k-1})$ and $z_{0}=[w_{0}]_{\eta}=\text{prox}_{\eta\psi}\left(w_{0}-\eta g\right)\text{ with }\eta=\frac{1}{L+\kappa}\text{ and }g=\nabla f_{0}(w_{0})+\kappa(w_{0}-y_{k}).$ (b) when using criteria (C2) to find $x_{k+1}$ in $g^{\>\!\delta_{k}}(y_{k})$, – if $f$ is smooth ($\psi=0$), then choose $z_{0}=y_{k}$. – if $f$ is composite as in (1), then choose $z_{0}=[y_{k}]_{\eta}=\text{prox}_{\eta\psi}(y_{k}-\eta\nabla f_{0}(y_{k}))\quad\text{with}\quad\eta=\frac{1}{L+\kappa}.$ (c) when using a fixed budget $T$, choose the same warm start strategy as in (b). Note that the earlier conference paper (Lin et al., 2015a) considered the the warm start rule $z_{0}=x_{k-1}$. That variant is also theoretically validated but it does not perform as well as the ones proposed here in practice.

Finally, the last ingredient is to find an optimal balance between the inner-loop (for solving each sub-problem) and outer-loop computations. To do so, we minimize our global complexity bounds with respect to the value of $\kappa$. As we shall see in Section 5, this strategy turns out to be reasonable in practice. Then, as shown in the theoretical section, the resulting rule of thumb is We select $\kappa$ by maximizing the ratio $\tau_{\mathcal{M}}/\sqrt{\mu+\kappa}$. We recall that $\tau_{\mathcal{M}}$ characterizes how fast $\mathcal{M}$ solves the sub-problems, according to (12); typically, $\tau_{\mathcal{M}}$ depends on the condition number $\frac{L+\kappa}{\mu+\kappa}$ and is a function of $\kappa$. Note that the rule for the non strongly convex case, denoted here by $\mu=0$, slightly differs from Lin et al. (2015a) and results from a tighter complexity analysis. In Table 2, we illustrate the choice of $\kappa$ for different methods. Note that the resulting rule for incremental methods is very simple for the pracitioner: select $\kappa$ such that the condition number $\frac{\bar{L}+\kappa}{\mu+\kappa}$ is of the order of $n$; then, the inner-complexity becomes $O(n\log(1/\varepsilon))$.

Convergence and Complexity Analysis

We now present the complexity analysis of Catalyst. In Section 4.1, we analyze the convergence rate of the outer loop, regardless of the complexity for solving the sub-problems. Then, we analyze the complexity of the inner-loop computations for our various stopping criteria and warm-start strategies in Section 4.2. Section 4.3 combines the outer- and inner-loop analysis to provide the global complexity of Catalyst applied to a given optimization method $\mathcal{M}$.

The complexity analysis of the first variant of Catalyst we presented in (Lin et al., 2015a) used a tool called “estimate sequence”, which was introduced by Nesterov (2004). Here, we provide a simpler proof. We start with criterion (C1), before extending the result to (C2).

The next theorem describes how the errors $(\varepsilon_{k})_{k\geq 0}$ accumulate in Catalyst.

Consider the sequences $(x_{k})_{k\geq 0}$ and $(y_{k})_{k\geq 0}$ produced by Algorithm 2, assuming that $x_{k}$ is in $p^{\>\!\varepsilon_{k}}(y_{k-1})$ for all $k\geq 1$, Then,

Before we prove this theorem, we note that by setting $\varepsilon_{k}=0$ for all $k$, the speed of convergence of $f(x_{k})-f^{*}$ is driven by the sequence $(A_{k})_{k\geq 0}$. Thus we first show the speed of $A_{k}$ by recalling the Lemma 2.2.4 of Nesterov (2004).

Consider the quantities $\gamma_{0},A_{k}$ defined in (14) and the $\alpha_{k}$’s defined in Algorithm 2. Then, if $\gamma_{0}\geq\mu$,

For non-strongly convex objectives, $A_{k}$ follows the classical accelerated $O(1/k^{2})$ rate of convergence, whereas it achieves a linear convergence rate for the strongly convex case. Intuitively, we are applying an inexact Nesterov method on the Moreau envelope $F$, thus the convergence rate naturally depends on the inverse of its condition number, which is $q=\frac{\mu}{\mu+\kappa}$. We now provide the proof of the theorem below.

Proof We start by defining an approximate sufficient descent condition inspired by a remark of Chambolle and Pock (2015) regarding accelerated gradient descent methods. A related condition was also used by Paquette et al. (2018) in the context of non-convex optimization.

where the $(\mu+\kappa)$-strong convexity of $h_{k}$ is used in the first inequality; Lemma 19 is used in the second inequality, and the last one uses the relation $h_{k}(x_{k})-h_{k}^{*}\leq\varepsilon_{k}$. Moreover, when $\theta_{k}\geq 1$, the last term is positive and we have

If instead $\theta_{k}\leq 1$, the coefficient $\frac{1}{\theta_{k}}-1$ is non-negative and we have

As a result, we have for all value of $\theta_{k}>0$,

After expanding the expression of $h_{k}$, we then obtain the approximate descent condition

We introduce a sequence $(S_{k})_{k\geq 0}$ that will act as a Lyapunov function, with

where $x^{*}$ is a minimizer of $f$, $(v_{k})_{k\geq 0}$ is a sequence defined by $v_{0}=x_{0}$ and

and $(\eta_{k})_{k\geq 0}$ is an auxiliary quantity defined by

The way we introduce these variables allow us to write the following relationship,

which follows from a simple calculation. Then by setting $z_{k}=\alpha_{k-1}x^{*}+(1-\alpha_{k-1})x_{k-1}$ the following relations hold for all $k\geq 1$.

where we used the convexity of the norm and the fact that $\eta_{k}\leq\alpha_{k}$. Using the previous relations in (15) with $x=z_{k}=\alpha_{k-1}x^{*}+(1-\alpha_{k-1})x_{k-1}$, gives for all $k\geq 1$,

and the quadratic terms involving $x^{*}-x_{k-1}$ cancel each other. Then, after noticing that for all $k\geq 1$,

we immediately derive from equation (18) that

By minimizing the right-hand side of (19) with respect to $\theta_{k}$, we obtain the following inequality

From Equation (17), the lefthand side is larger than $\frac{(\mu+\kappa)\alpha_{k-1}^{2}\|x^{*}-v_{k}\|^{2}}{2A_{k-1}}$. We may now define $u_{j}=\frac{\sqrt{(\mu+\kappa)}\alpha_{j-1}\|x^{*}-v_{j}\|}{\sqrt{2A_{j-1}}}$ and $a_{j}=2\frac{\sqrt{\varepsilon_{j}}}{\sqrt{A_{j-1}}}$, and we have

This allows us to apply Lemma 20, which yields

which provides us the desired result given that $f(x_{k})-f^{*}\leq\frac{S_{k}}{1-\alpha_{k}}$ and that $v_{0}=x_{0}$.

We are now in shape to state the convergence rate of the Catalyst algorithm with criterion (C1), without taking into account yet the cost of solving the sub-problems. The next two propositions specialize Theorem 3 to the strongly convex case and non strongly convex cases, respectively. Their proofs are provided in Appendix B.

In Algorithm 2, choose $\alpha_{0}=\sqrt{q}$ and

Then, the sequence of iterates $(x_{k})_{k\geq 0}$ satisfies

Then, Algorithm 2 generates iterates $(x_{k})_{k\geq 0}$ such that

1.2 Analysis for Criterion (C2)

Then, we may now analyze the convergence of Catalyst under criterion (C2), which offers similar guarantees as (C1), as far as the outer loop is concerned.

Consider the sequences $(x_{k})_{k\geq 0}$ and $(y_{k})_{k\geq 0}$ produced by Algorithm 2, assuming that $x_{k}$ is in $g^{\>\!\delta_{k}}(y_{k-1})$ for all $k\geq 1$ and $\delta_{k}$ in $(0,1)$. Then,

where $\gamma_{0}$ and $(A_{k})_{k\geq 0}$ are defined in (14) in Theorem 3.

Proof Remark that $x_{k}$ in $g^{\>\!\delta_{k}}(y_{k-1})$ is equivalent to $x_{k}$ in $p^{\>\!\varepsilon_{k}}(y_{k-1})$ with an adaptive error $\varepsilon_{k}=\frac{\delta_{k}\kappa}{2}\|x_{k}-y_{k-1}\|^{2}$. All steps of the proof of Theorem 3 hold for such values of $\varepsilon_{k}$ and from (18), we may deduce

Then, by choosing $\theta_{k}=\delta_{k}<1$, the quadratic term on the right disappears and the left-hand side is greater than $\frac{1-\delta_{k}}{1-\alpha_{k}}S_{k}$. Thus,

which is sufficient to conclude since $(1-\alpha_{k})(f(x_{k})-f^{*})\leq S_{k}$.

The next propositions specialize Theorem 7 for specific choices of sequence $(\delta_{k})_{k\geq 0}$ in the strongly and non strongly convex cases.

In Algorithm 2, choose $\alpha_{0}=\sqrt{q}$ and

Then, the sequence of iterates $(x_{k})_{k\geq 0}$ satisfies

Proof This is a direct application of Theorem 7 by remarking that $\gamma_{0}=(1-\sqrt{q})\mu$ and

And $\alpha_{k}=\sqrt{q}$ for all $k\geq 0$ leading to

Then, Algorithm 2 generates iterates $(x_{k})_{k\geq 0}$ such that

Proof This is a direct application of Theorem 7 by remarking that $\gamma_{0}=\kappa$, $A_{k}\leq\frac{4}{(k+2)^{2}}$ (Lemma 4) and

In fact, the choice of $\delta_{k}$ can be improved by taking $\delta_{k}=\frac{1}{(k+1)^{1+\gamma}}$ for any $\gamma>0$, which comes at the price of a larger constant in (20).

2 Analysis of Warm-start Strategies for the Inner Loop

In this section, we study the complexity of solving the subproblems with the proposed warm start strategies. The only assumption we make on the optimization method $\mathcal{M}$ is that it enjoys linear convergence when solving a strongly convex problem—meaning, it satisfies either (12) or its randomized variant (13). Then, the following lemma gives us a relation between the accuracy required to solve the sub-problems and the corresponding complexity.

Let us consider a strongly convex objective $h$ and a linearly convergent method $\mathcal{M}$ generating a sequence of iterates $(z_{t})_{t\geq 0}$ for minimizing $h$. Consider the complexity $T(\varepsilon)=\inf\{t\geq 0,h(z_{t})-h^{*}\leq\varepsilon\}$, where $\varepsilon>0$ is the target accuracy and $h^{*}$ is the minimum value of $h$. Then,

If $\mathcal{M}$ is deterministic and satisfies (12), we have

If $\mathcal{M}$ is randomized and satisfies (13), we have

The proof of the deterministic case is straightforward and the proof of the randomized case is provided in Appendix B.4. From the previous result, a good initialization is essential for fast convergence. More precisely, it suffices to control the initialization $\frac{h(z_{0})-h^{*}}{\varepsilon}$ in order to bound the number of iterations $T(\varepsilon)$. For that purpose, we analyze the quality of various warm-start strategies.

The next proposition characterizes the quality of initialization for (C1).

Assume that $\mathcal{M}$ is linearly convergent for strongly convex problems with parameter $\tau_{\mathcal{M}}$ according to (12), or according to (13) in the randomized case. At iteration $k+1$ of Algorithm 2, given the previous iterate $x_{k}$ in $p^{\>\!\varepsilon_{k}}(y_{k-1})$, we consider the following function

which we minimize with $\mathcal{M}$, producing a sequence $(z_{t})_{t\geq 0}$. Then,

when $f$ is smooth, choose $z_{0}=x_{k}+\frac{\kappa}{\kappa+\mu}(y_{k}-y_{k-1})$;

We also assume that we choose $\alpha_{0}$ and $(\varepsilon_{k})_{k\geq 0}$ according to Proposition 5 for $\mu>0$, or Proposition 6 for $\mu=0$. Then,

if $f$ is $\mu$-strongly convex, $h_{k+1}(z_{0})-h_{k+1}^{*}\leq C\varepsilon_{k+1}$ where,

if $f$ is convex with bounded level sets, there exists a constant $B>0$ that only depends on $f,x_{0}$ and $\kappa$ such that

Proof We treat the smooth and composite cases separately.

When $f$ is smooth, by the gradient Lipschitz assumption,

Since $x_{k}$ is in $p^{\varepsilon_{k}}(y_{k-1})$, we may control the first quadratic term on the right by noting that

Moreover, by the coerciveness property of the proximal operator,

see Appendix B.5 for the proof. As a consequence,

Then, we need to control the term $\|y_{k}-y_{k-1}\|^{2}$. Inspired by the proof of accelerated SDCA of Shalev-Shwartz and Zhang (2016),

The last inequality was due to the fact that $\beta_{k}\leq 1$. In fact,

where the last equality uses the relation $\alpha_{k}^{2}+\alpha_{k}\alpha_{k-1}^{2}=\alpha_{k-1}^{2}+q\alpha_{k}$ from (10). Then,

where the last inequality is obtained from Proposition 5. As a result,

Since $\varepsilon_{k+1}=(1-\rho)^{2}\varepsilon_{k-1}$, we may now obtain (21) from (24) and the previous bound.

When $\mu=0$, Eq. (24) is still valid but we need to control $\|y_{k}-y_{k-1}\|^{2}$ in a different way. From Proposition 6, the sequence $(f(x_{k}))_{k\geq 0}$ is bounded by a constant that only depends on $f$ and $x_{0}$; therefore, by the bounded level set assumption, there exists $R>0$ such that

Thus, following the same argument as the strongly convex case, we have

and we obtain (23) by combining the previous inequality with (24).

By using the notation of gradient mapping introduced in (7), we have $z_{0}=[w_{0}]_{\eta}$. By following similar steps as in the proof of Lemma 2, the gradient mapping satisfies the following relation

and it is sufficient to bound $\|w_{0}-z_{0}\|=\|w_{0}-[w_{0}]_{\eta}\|$. For that, we introduce

and we will bound each term on the right. By construction

Next, it is possible to show that the gradient mapping satisfies the following relation (see Nesterov, 2013),

We have used the fact that $\|x-\eta\nabla h(x)-(y-\eta\nabla h(y))\|\leq\|x-y\|$. By combining the previous inequalities with (25), we finally have

Thus, by using the fact that $(a+b)^{2}\leq 2a^{2}+2b^{2}$ for all $a,b$,

and we can obtain (22) and (23) by upper-bounding $\|y_{k}-y_{k-1}\|^{2}$ in a similar way as in the smooth case, both when $\mu>0$ and $\mu=0$.

Finally, the complexity of the inner loop can be obtained directly by combining the previous proposition with Lemma 11.

Consider the setting of Proposition 12; then, the sequence $(z_{t})_{t\geq 0}$ minimizing $h_{k+1}$ is such that the complexity $T_{k+1}=\inf\{t\geq 0,h_{k+1}(z_{t})-h_{k+1}^{*}\leq\varepsilon_{k+1}\}$ satisfies

where $C$ is the constant defined in (21) or in (22) for the composite case; and

2.2 Warm Start Strategies for Criterion (C2)

We may now analyze the inner-loop complexity for criterion (C2) leading to upper bounds with smaller constants and simpler proofs. Note also that in the convex case, the bounded level set condition will not be needed, unlike for criterion (C1). To proceed, we start with a simple lemma that gives us a sufficient condition for (C2) to be satisfied.

then $z$ is in $g^{\>\!\delta_{k+1}}(y_{k})$.

Rearranging the terms gives the desired result. With the previous result, we can control the complexity of the inner-loop minimization with Lemma 11 by choosing $\varepsilon=\frac{\delta_{k+1}\kappa}{8}\|p(y_{k})-y_{k}\|^{2}$. However, to obtain a meaningful upper bound, we need to control the ratio

Assume that $\mathcal{M}$ is linearly convergent for strongly convex problems with parameter $\tau_{\mathcal{M}}$ according to (12), or according to (13) in the randomized case. At iteration $k+1$ of Algorithm 2, given the previous iterate $x_{k}$ in $g^{\>\!\delta_{k}}(y_{k-1})$, we consider the following function

which we minimize with $\mathcal{M}$, producing a sequence $(z_{t})_{t\geq 0}$. Then,

Proof When $f$ is smooth, the optimality conditions of $p(y_{k})$ yield $\nabla h_{k+1}(p(y_{k}))=\nabla f(p(y_{k}))+\kappa(p(y_{k})-y_{k})=0$. As a result,

When $f$ is composite, we use the inequality in Lemma 2.3 of Beck and Teboulle (2009): for any $z$,

Then, we apply this inequality with $z=p(y_{k})$, and thus,

We are now in shape to derive a complexity bound for criterion (C2), which is obtained by combining directly Lemma 11 with the value $\varepsilon=\frac{\delta_{k+1}\kappa}{8}\|p(y_{k})-y_{k}\|^{2}$, Lemma 14, and the previous proposition.

Consider the setting of Proposition 15 when $\mathcal{M}$ is deterministic; assume further that $\alpha_{0}$ and $(\delta_{k})_{k\geq 0}$ are chosen according to Proposition 8 for $\mu>0$, or Proposition 9 for $\mu=0$.

Then, the sequence $(z_{t})_{t\geq 0}$ is such that the complexity $T_{k+1}=\inf\{t\geq 0,z_{t}\in g^{\>\!\delta_{k+1}}(y_{k})\}$ satisfies

The inner-loop complexity is asymptotically similar with criterion (C2) as with criterion (C1), but the constants are significantly better.

3 Global Complexity Analysis

In this section, we combine the previous outer-loop and inner-loop convergence results to derive a global complexity bound. We treat here the strongly convex $(\mu>0)$ and convex $(\mu=0)$ cases separately.

When $f$ is $\mu$-strongly convex and all parameters are chosen according to Propositions 5 and 12 when using criterion (C1), or Propositions 8 and 15 for (C2), then Algorithm 2 finds a solution $\hat{x}$ such that $f(\hat{x})-f^{*}\leq\varepsilon$ in at most $N_{\mathcal{M}}$ iterations of a deterministic method $\mathcal{M}$ with

where $\rho=0.9\sqrt{q}$ and $C$ is the constant defined in (21) or (22) for the composite case;

Note that similar results hold in terms of expected number of iterations when the method $\mathcal{M}$ is randomized (see the end of Proposition 12).

Proof Let $K$ be the number of iterations of the outer-loop algorithm required to obtain an $\varepsilon$-accurate solution. From Proposition 5, using (C1) criterion yields

From Proposition 8, using (C2) criterion yields

Then since the number of runs of $\mathcal{M}$ is constant for any inner loop, the total number $N_{\mathcal{M}}$ is given by $KT$ where $T$ is respectively given by Corollaries 13 and 16.

3.2 Convex, but not Strongly Convex Case

When $\mu=0$, the number of iterations for solving each subproblems grows logarithmically, which means that the iterate $x_{k}$ in Algorithm 2 is obtained after $s=\leq kT\log(k+2)$ iterations of the method $\mathcal{M}$, where $T$ is a constant. By using the global iteration counter $s=kT\log(k+2)$, we finally have

This rate is near-optimal, up to a logarithmic factor, when compared to the optimal rate $O(1/s^{2})$. This may be the price to pay for using a generic acceleration scheme. As before, we detail the global complexity bound for convex objectives in the next proposition.

When $f$ is convex and all parameters are chosen according to Propositions 6 and 12 when using criterion (C1), or Propositions 9 and 15 for criterion (C2), then Algorithm 2 finds a solution $\hat{x}$ such that $f(\hat{x})-f^{*}\leq\varepsilon$ in at most $N_{\mathcal{M}}$ iterations of a deterministic method $\mathcal{M}$ with

Note that similar results hold in terms of expected number of iterations when the method $\mathcal{M}$ is randomized (see the end of Proposition 15).

Proof Let $K$ denote the number of outer-loop iterations required to achieve an $\varepsilon$-accurate solution. From Proposition 6, when (C1) is applied, we have

From Proposition 9, when (C2) is applied, we have

Since the number of runs in the inner loop is increasing, we have

Respectively apply $T_{K}$ obtained from Corollary 13 and Corollary 16 gives the result.

The parameter $\kappa$ plays an important rule in the global complexity result. The linear convergence parameter $\tau_{\mathcal{M}}$ depends typically on $\kappa$ since it controls the strong convexity parameter of the subproblems. The natural way to choose $\kappa$ is to minimize the global complexity given by Proposition 17 and Proposition 18, which leads to the following rule Choose $\bm{\kappa}$ to maximize $\bm{\displaystyle}\frac{\tau_{\mathcal{M}}}{\sqrt{\mu+\kappa}}$, where $\mu=0$ when the problem is convex but not strongly convex. We now illustrate two examples when applying Catalyst to the classical gradient descent method and to the incremental approach SVRG.

When $\mathcal{M}$ is the gradient descent method, we have

Maximizing the ratio $\displaystyle\frac{\tau_{\mathcal{M}}}{\sqrt{\mu+\kappa}}$ gives

Consequently, the complexity in terms of gradient evaluations for minimizing the finite sum (2), where each iteration of $\mathcal{M}$ cost $n$ gradients, is given by

These rates are near-optimal up to logarithmic constants according to the first-order lower bound (Nemirovskii and Yudin, 1983; Nesterov, 2004).

For SVRG (Xiao and Zhang, 2014) applied to the same finite-sum objective,

Thus, maximizing the corresponding ratio gives

Consequently, the resulting global complexity, here in terms of expected number of gradient evaluations, is given by

Note that we treat here only the case $\bar{L}>(n+2)\mu$ to simplify, see Table 1 for a general results. We also remark that Catalyst can be applied to similar incremental algorithms such as SAG/SAGA (Schmidt et al., 2017; Defazio et al., 2014a) or dual-type algorithm MISO/Finito (Mairal, 2015; Defazio et al., 2014b) or SDCA Shalev-Shwartz and Zhang (2012). Moreover, the resulting convergence rates are near-optimal up to logarithmic constants according to the first-order lower bound (Woodworth and Srebro, 2016; Arjevani and Shamir, 2016).

3.3 Practical Aspects of the Theoretical Analysis

So far, we have not discussed the fixed budget criterion mentioned in Section 3. The idea is quite natural and simple to implement: we predefine the number of iterations to run for solving each subproblems and stop worrying about the stopping condition. For example, when $\mu>0$ and $\mathcal{M}$ is deterministic, we can simply run $T_{\mathcal{M}}$ iterations of $\mathcal{M}$ for each subproblem where $T_{\mathcal{M}}$ is greater than the value given by Corollaries 13 or 16, then the criterions (C1) and (C2) are guaranteed to be satisfied. Unfortunately, the theoretical bound of $T_{\mathcal{M}}$ is relatively poor and does not lead to a practical strategy. On the other hand, using a more aggressive strategy such as $T_{\mathcal{M}}=n$ for incremental algorithms, meaning one pass over the data, seems to provide outstanding results, as shown in the experimental part of this paper.

Finally, one could argue that choosing $\kappa$ according to a worst-case convergence analysis is not necessarily a good choice. In particular, the convergence rate of the method $\mathcal{M}$, driven by the parameter $\tau_{\mathcal{M}}$ is probably often under estimated in the first place. This suggests that using a smaller value for $\kappa$ than the one we have advocated earlier is a good thing. In practice, we have observed that indeed Catalyst is often robust to smaller values of $\kappa$ than the theoretical one, but we have also observed that the theoretical value performs reasonably well, as we shall see in the next section.

Experimental Study

In this section, we conduct various experiments to study the effect of the Catalyst acceleration and its different variants, showing in particular how to accelerate SVRG, SAGA, and MISO. In Section 5.1, we describe the data sets and formulations considered for our evaluation, and in Section 5.2, we present the different variants of Catalyst. Then, we study different questions: which variant of Catalyst should we use for incremental approaches? (Section 5.3); how do various incremental methods compare when accelerated with Catalyst? (Section 5.4); what is the effect of Catalyst on the test error when Catalyst is used to minimize a regularized empirical risk? (Section 5.5); is the theoretical value for $\kappa$ appropriate? (Section 5.6). The code used for all our experiments is available at https://github.com/hongzhoulin89/Catalyst-QNing/.

We consider six machine learning data sets with different characteristics in terms of size and dimension to cover a variety of situations.

While the first four data sets are standard ones that were used in previous work about optimization methods for machine learning, the last two are coming from a computer vision application. MNIST and CIFAR-10 are two image classification data sets involving 10 classes. The feature representation of each image was computed using an unsupervised convolutional kernel network Mairal (2016). We focus here on the the task of classifying class #1 vs. the rest of the data set.

which leads to a $\mu$-strongly convex smooth optimization problem.

which is non smooth and convex but not strongly convex.

which is based on the Elastic-Net regularization (Zou and Hastie, 2005) and leading to a strongly-convex optimization problem.

Each feature vector $a_{i}$ is normalized, and a natural upper-bound on the Lipschitz constant $L$ of the un-regularized objective can be easily obtained with $L_{\text{logistic}}=1/4$ and $L_{\text{lasso}}=1$. The regularization parameter $\mu$ and $\lambda$ are choosing in the following way:

For Logistic Regression, we find an optimal regularization parameter $\mu^{*}$ by 10-fold cross validation for each data set on a logarithmic grid $2^{i}/n$, with $i\in$. Then, we set $\mu=\mu^{*}/2^{3}$ which corresponds to a small value of the regularization parameter and a relatively ill-conditioned problem.

For Elastic-Net, we set $\mu=0.01/n$ to simulate the ill-conditioned situation and add a small $l_{1}$-regularization penalty with $\lambda=1/n$ that produces sparse solutions.

For the Lasso problem, we consider a logarithmic grid $10^{i}/n$, with $i=-3,-2,\ldots,3$, and we select the parameter $\lambda$ that provides a sparse optimal solution closest to $10\%$ non-zero coefficients, which leads to $\lambda=10/n$ or $100/n$.

Note that for the strongly convex problems, the regularization parameter $\mu$ yields a lower bound on the strong convexity parameter of the problem.

In this chapter, and following previous work about incremental methods (Schmidt et al., 2017), we plot objective values as a function of the number of gradients evaluated during optimization, which appears to be the computational bottleneck of all previously mentioned algorithms. Since no metric is perfect for comparing algorithms’ speed, we shall make the two following remarks, such that the reader can interpret our results and the limitations of our study with no difficulty.

Ideally, CPU-time is the gold standard but CPU time is implementation-dependent and hardware-dependent.

We have chosen to count only gradients computed with random data access. Thus, computing $n$ times a gradient $f_{i}$ by picking each time one function at random counts as “$n$ gradients”, whereas we ignore the cost of computing a full gradient $(1/n)\sum_{i=1}^{n}\nabla f_{i}$ at once, where the $f_{i}$’s can be accessed in sequential order. Similarly, we ignore the cost of computing the function value $f(x)=(1/n)\sum_{i=1}^{n}f_{i}(x)$, which is typically performed every pass on the data when computing a duality gap. While this assumption may be inappropriate in some contexts, the cost of random gradient computations was significantly dominating the cost of sequential access in our experiments, where (i) data sets fit into memory; (ii) computing full gradients was done in C++ by calling BLAS2 functions exploiting multiple cores.

2 Choice of Hyper-parameters and Variants

Before presenting the numerical results, we discuss the choice of default parameters used in the experiments as well as different variants.

We consider the acceleration of incremental algorithms which are able to adapt to the problem structure we consider: large sum of functions and possibly non-smooth regularization penalty.

The proximal SVRG algorithm of Xiao and Zhang (2014) with stepsize $\eta=1/L$.

The SAGA algorithm Defazio et al. (2014a) with stepsize $\eta=1/3L$.

The proximal MISO algorithm of Lin et al. (2015a).

As suggested by the theoretical analysis, we take $\kappa$ to minimize the global complexity, leading to the choice

The choice of the accuracies are driven from the theoretical analysis described in paragraph 3. Here, we specify it again for the clarity of presentation:

Stopping criterion (C1). Stop when $h_{k}(z_{t})-h_{k}^{*}\leq\varepsilon_{k}$, where

The duality gap $h(w_{t})-h^{*}$ can be estimated either by evaluating the Fenchel conjugate function or by computing the squared norm of the gradient.

Stopping criterion (C2). Stop when $h_{k}(z_{t})-h_{k}^{*}\leq\delta_{k}\cdot\frac{\kappa}{2}\|z_{t}-y_{k-1}\|^{2}$, where

Stopping criterion (C3) . Perform exactly one pass over the data in the inner loop without checking any stopping criteria.This stopping criterion is heuristic since one pass may not be enough to achieve the required accuracy. What we have shown is that with a large enough $T_{\mathcal{M}}$, then the convergence will be guaranteed. Here we take heuristically $T_{\mathcal{M}}$ as one pass.

This is an important point to achieve acceleration which was not highlighted in the conference paper (Lin et al., 2015a). At iteration $k+1$, we consider the minimization of

We warm start according to the strategy defined in Section 3. Let $x_{k}$ be the approximate minimizer of $h_{k}$, obtained from the last iteration.

Initialization for (C1). Let us define $\eta=\frac{1}{L+\kappa}$, then initialize at

Initialization for (C3). Take the best initial point among $x_{k}$ and $z_{0}^{C1}$

Initialization for (C1∗). Use the strategy (C1) with $z_{0}^{C3}$.

The warm start at $z_{0}^{C3}$ requires to choose the best point between the last iterate $x_{k}$ and the point $z_{0}^{C1}$. The motivation is that since the one-pass strategy is an aggressive heuristic, the solution of the subproblems may not be as accurate as the ones obtained with other criterions. Allowing using the iterate $x_{k}$ turned out to be significantly more stable in practice. Then, it is also natural to use a similar strategy for criterion (C1), which we call ($\textsf{C1}^{*}$). Using a similar strategy for (C2) turned out not to provide any benefit in practice and is thus omitted from the list here.

3 Comparison of Stopping Criteria and Warm-start Strategies

First, we evaluate the performance of the previous strategies when applying Catalyst to SVRG, SAGA and MISO. The results are presented in Figures 1, 2, and 3, respectively.

We remark that in most of the cases, the curve of (C3) and ($\textsf{C1}^{*}$)are superimposed, meaning that one pass through the data is enough for solving the subproblem up to the required accuracy. Moreover, they give the best performance among all criterions. Regarding the logistic regression problem, the acceleration is significant (even huge for the covtype data set) except for alpha, where only (C3) and ($\textsf{C1}^{*}$)do not degrade significantly the performance. For sparse problems, the effect of acceleration is more mitigated, with 7 cases out of 12 exhibiting important acceleration and 5 cases no acceleration. As before, (C3) and ($\textsf{C1}^{*}$)are the only strategies that never degrade performance.

One reason explaining why acceleration is not systematic may be the ability of incremental methods to adapt to the unknown strong convexity parameter $\mu^{\prime}\geq\mu$ hidden in the objective’s loss, or local strong convexity near the solution. When $\mu^{\prime}/L\geq 1/n$, we indeed obtain a well-conditioned regime where acceleration should not occur theoretically. In fact the complexity $O(n\log(1/\varepsilon))$ is already optimal in this regime, see Arjevani and Shamir (2016); Woodworth and Srebro (2016). For sparse problems, conditioning of the problem with respect to the linear subspace where the solution lies might also play a role, even though our analysis does not study this aspect. Therefore, this experiment suggests that adaptivity to unknown strong convexity is of high interest for incremental optimization.

Our conclusions with SAGA are almost the same as with SVRG. However, in a few cases, we also notice that criterion C1 lacks stability, or at least exhibits some oscillations, which may suggest that SAGA has a larger variance compared to SVRG. The difference in the performance of (C1) and ($\textsf{C1}^{*}$)can be huge, while they differ from each other only by the warm start strategy. Thus, choosing a good initial point for solving the sub-problems is a key for obtaining acceleration in practice.

The warm-start strategy of MISO is different from primal algorithms because parameters for the dual function need to be specified. The most natural way for warm starting the dual functions is to set

where $d_{k}$ is the last dual function of the previous subproblem $h_{k}$. This gives the warm start

For other choices of $z_{0}$, the dual function needs to be recomputed from scratch, which is computationally expensive and unstable for ill-conditioned problems. Thus, we only present the experimental results with respect to criterion (C1) and the one-pass heuristic (C3) . As we observe, a huge acceleration is obtained in logistic regression and Elastic-net formulations. For Lasso problem, the original Prox-MISO is not defined since the problem is not strongly convex. Thus, in order to make a comparison, we compare with Catalyst-SVRG which shows that the acceleration achieves a similar performance. This aligns with the theoretical result stating that Catalyst applied to incremental algorithms yields a similar convergence rate. Notice also that the original MISO algorithm suffers from numerical stability in this ill-conditioned regime chosen for our experiments. Catalyst not only accelerates MISO, but it also stabilizes it.

4 Acceleration of Existing Methods

Then, we put the previous curves into perspective and make a comparison of the performance before and after applying Catalyst across methods. We show the best performance among the three developed stopping criteria, which corresponds to be (C3) .

In Figure 4, we observe that by applying Catalyst, we accelerate the original algorithms up to the limitations discussed above (comparing the dashed line and the solid line of the same color). In three data sets (covtype, real-sim and rcv1), significant improvements are achieved as expected by the theory for the ill-conditioned problems in logistic regression and Elastic-net. For data set alpha, we remark that an relative accuracy in the order $10^{-10}$ is attained in less than 10 iterations. This suggests that the problems is in fact well-conditioned and there is some hidden strong convexity for this data set. Thus, the incremental algorithms like SVRG or SAGA are already optimal under this situation and no further improvement can be obtained by applying Catalyst.

5 Empirical Effect on the Generalization Error

A natural question that applies to all incremental methods is whether or not the acceleration that we may see for minimizing an empirical risk on training data affects the objective function and the test accuracy on new unseen test data. To answer this question, we consider the logistic regression formulation with the regularization parameter $\mu^{*}$ obtained by cross-validation. Then, we cut each data set into $80\%$ of training data and set aside $20\%$ of the data point as test data.

The left column of Figure 5 shows the loss function on the training set, where acceleration is significant in 5 cases out of 6. The middle column shows the loss function evaluated on the test set, but on a non-logarithmic scale since the optimal value of the test loss is unknown. Acceleration appears in 4 cases out of 6. Regarding the test accuracy, an important acceleration is obtained in 2 cases, whereas it is less significant or negligible in the other cases.

6 Study of the Parameter κ𝜅\kappa

Finally, we evaluate the performance for different values of $\kappa$.

We consider a logarithmic grid $\kappa=10^{i}\kappa_{0}$ with $i=-2,-1,\cdots,2$ and $\kappa_{0}$ is the optimal $\kappa$ given by the theory. We observe that for ill-conditioned problems, using optimal choice $\kappa_{0}$ provides much better performance than other choices, which confirms the theoretical result. For the data set of alpha or Lasso problems, we observe that the best choice is given by the smallest $\kappa=0.01\kappa_{0}$. This suggests that, as discussed before, there is a certain degree of strong convexity present in the objective even without any regularization.

Conclusion

We have introduced a generic algorithm called Catalyst that allows us to extend Nesterov’s acceleration to a large class of first-order methods. We have shown that it can be effective in practice for ill-conditioned problems. Besides acceleration, Catalyst also improves the numerical stability of a given algorithm, by applying it to auxiliary problems that are better conditioned than the original objective. For this reason, it also provides support to convex, but not strongly convex objectives, to algorithms that originally require strong convexity. We have also studied experimentally many variants to identify the ones that are the most effective and the simplest to use in practice. For incremental methods, we showed that the “almost-parameter-free” variant, consisting in performing a single pass over the data at every outer-loop iteration, was the most effective one in practice.

Even though we have illustrated Catalyst in the context of finite-sum optimization problems, the main feature of our approach is its versatility. Catalyst could also be applied to other algorithms that have not been considered so far and give rise to new accelerated algorithms.

The authors would like to thank Dmitriy Drusvyatskiy, Anatoli Juditsky, Sham Kakade, Arkadi Nemirovski, Courtney Paquette, and Vincent Roulet for fruitful discussions. Hongzhou Lin and Julien Mairal were supported by the ERC grant SOLARIS (# 714381) and a grant from ANR (MACARON project ANR-14-CE23-0003-01). Zaid Harchaoui was supported by NSF Award CCF-1740551 and the program “Learning in Machines and Brains” of CIFAR. This work was performed while Hongzhou Lin was at Inria and Univ. Grenoble Alpes.

A Useful Lemmas

Consider a increasing sequence $(S_{k})_{k\geq 0}$ and two non-negative sequences $(a_{k})_{k\geq 0}$ and $(u_{k})_{k\geq 0}$ such that for all $k$,

Proof This lemma is identical to the Lemma A.10 in the original Catalyst paper (Lin et al., 2015a), inspired by a lemma of Schmidt et al. (2011) for controlling errors of inexact proximal gradient methods.

We give here an elementary proof for completeness based on induction. The relation (30) is obviously true for $k=0$. Then, we assume it is true for $k-1$ and prove the relation for $k$. We remark that from (29),

We may now prove the relation (30) by induction,

The last inequality is obtained by developing the square $\left(\sqrt{S_{k-1}+\sum_{i=1}^{k-1}a_{i}}\right)^{2}$ and use the increasing assumption $S_{k-1}\leq S_{k}$.

Let $(A_{k})_{k\geq 0}$ be the sequence defined in (14) where $(\alpha_{k})_{k\geq 0}$ is produced by (10) with $\alpha_{0}=1$ and $\mu=0$. Then, we have the following bounds for all $k\geq 0$,

Proof The righthand side is directly obtained from Lemma 4 by noticing that $\gamma_{0}=\kappa$ with the choice of $\alpha_{0}$. Using the recurrence of $\alpha_{k}$, we have for all $k\geq 1$,

Thus, $\alpha_{k}\leq\frac{2}{k+2}$ for all $k\geq 1$ (it is also true for $k=0$). We now have all we need to conclude the lemma:

B Proofs of Auxiliary Results

Proof Let us introduce the notation $h^{\prime}(z)\triangleq\frac{1}{\eta}(z-[z]_{\eta})$ for the gradient mapping at $z$. The first order conditions of the convex problem defining $[z]_{\eta}$ give

where the first inequality comes from the relation (Nesterov, 2004, Theorem 2.1.5) using the fact $h_{0}$ is $(1/\eta)$-smooth

B.2 Proof of Proposition 5

Proof We simply use Theorem 3 and specialize it to the choice of parameters. The initialization $\alpha_{0}=\sqrt{q}$ leads to a particularly simple form of the algorithm, where $\alpha_{k}=\sqrt{q}$ for all $k\geq 0$. Therefore, the sequence $(A_{k})_{k\geq 0}$ from Theorem 3 is also simple since we indeed have $A_{k}=(1-\sqrt{q})^{k}$. Then, we remark that $\gamma_{0}=\mu(1-\sqrt{q})$ and thus, by strong convexity of $f$,

Therefore, Theorem 3 combined with the previous inequality gives us

Since $\sqrt{1-x}+\frac{x}{2}$ is decreasing in $$, we have$\sqrt{1-\rho}+\frac{\rho}{2}\geq\sqrt{1-\sqrt{q}}+\frac{\sqrt{q}}{2}$. Consequently,

B.3 Proof of Proposition 6

Proof The initialization $\alpha_{0}=1$ leads to $\gamma_{0}=\kappa$ and $S_{0}=\frac{\kappa}{2}\|x^{*}-x_{0}\|^{2}$. Then,

where the last inequality uses Lemma 21 to upper-bound the ratio $\varepsilon_{j}/A_{j}$. Moreover,

The last inequality uses $(a+b)^{2}\leq 2(a^{2}+b^{2})$.

B.4 Proof of Lemma 11

Proof We abbreviate $\tau_{\mathcal{M}}$ by $\tau$ and $C=C_{\mathcal{M}}(h(z_{0})-h^{*})$ to simplify the notation. Set

A simple calculation shows that for any $\tau\in(0,1)$, $\frac{\tau}{2}\leq 1-e^{-\tau}$ and then

B.5 Proof of coerciveness property of the proximal operator

Proof By the definition of $p(x)$, we have $0\in\partial f(p(x))+\kappa(p(x)-x)$, meaning that $\kappa(x-p(x))\in\partial f(p(x))$. By strong convexity of $f$,

Rearranging the terms yields the desired inequality. As a consequence,

C Catalyst for MISO/Finito/SDCA

In this section, we present the application of Catalyst to MISO/Finito (Mairal, 2015; Defazio et al., 2014b), which may be seen as a variant of SDCA (Shalev-Shwartz and Zhang, 2016). The reason why these algorithms require a specific treatment is due to the fact that their linear convergence rates are given in a different form than (12); specifically, Theorem 4.1 of Lin et al. (2015a) tells us that MISO produces a sequence of iterates $(z_{t})_{t\geq 0}$ for minimizing the auxiliary objective $h(z)=f(z)+\frac{\kappa}{2}\|z-y\|^{2}$ such that

where $d_{0}$ is a lower-bound of $h$ defined as the sum of a simple quadratic function and the composite regularization $\psi$. More precisely, these algorithms produce a sequence $(d_{t})_{t\geq 0}$ of such lower-bounds, and the iterate $z_{t}$ is obtained by minimizing $d_{t}$ in closed form. In particular, $z_{t}$ is obtained from taking a proximal step at a well chosen point $w_{t}$, providing the following expression,

Then, linear convergence is achieved for the duality gap

Indeed, the quantity $h(z_{t})-d_{t}(z_{t})$ is a natural upper-bound on $h(z_{t})-h^{*}$, which is simple to compute, and which can be naturally used for checking the criterions (C1) and (C2). Consequently, the expected complexity of solving a given problem is slightly different compared to Lemma 11.

Let us consider a strongly convex objective $h$ and denote $(z_{t})_{t\geq 0}$ the sequence of iterates generated by MISO/Finito/SDCA. Consider the complexity $T(\varepsilon)=\inf\{t\geq 0,h(z_{t})-d_{t}(z_{t})\leq\varepsilon\}$, where $\varepsilon>0$ is the target accuracy and $h^{*}$ is the minimum value of $h$. Then,

where $d_{0}$ is a lower bound of $f$ built by the algorithm.

For the convergence analysis, the outer-loop complexity does not change as long as the algorithm finds approximate proximal points satisfying criterions (C1) and (C2). It is then sufficient to control the inner loop complexity. As we can see, we now need to bound the dual gap $h^{*}-d_{0}(z_{0})$ instead of the primal gap $h(z_{0})-h^{*}$, leading to slightly different warm start strategies. Here, we show how to restart MISO/Finito.

when $f$ is $\mu$-strongly convex, we have $h_{k+1}^{*}-d_{0}(z_{0})\leq C\varepsilon_{k+1}$ with the same constant as in (21) and (22), where $d_{0}$ is the dual function corresponding to $z_{0}$;

when $f$ is convex with bounded level sets, there exists a constant $B>0$ identical to the one of (23) such that

Proof The proof is given in Lemma D.5 of Lin et al. (2015a), which gives

This term is smaller than the quantity derived from (24), leading to the same upper bound.

Consider applying Catalyst with the same parameter choices as in Proposition 15 to MISO/Finito. At iteration $k+1$ of Algorithm 2, we assume that we are given the previous iterate $x_{k}$ in $g^{\>\!\delta_{k}}(y_{k-1})$ and the corresponding dual function $d(x)$. Then, initialize the sequence $(z_{t})_{t\geq 0}$ for minimizing $h_{k+1}=f+\frac{\kappa}{2}\|\cdot-y_{k}\|^{2}$ by

where $f=f_{0}+\psi$ and $f_{0}$ is the smooth part of $f$, and set the dual function $d_{0}$ by

Proof Since $p(y_{k})$ is the minimum of $h_{k+1}$, the optimality condition provides

The bound obtained from (31) is similar to the one form Proposition 15, and differs only in the constant factor. Thus, the inner loop complexity in Section 4.2.2 still holds for MISO/Finito up to a constant factor. As a consequence, the global complexity of MISO/Finito applied to Catalyst is similar to one obtained by SVRG, yielding an acceleration for ill-conditioned problems.

References