A Generic Acceleration Framework for Stochastic Composite Optimization

Introduction

In this paper, we consider stochastic composite optimization problems of the form

Yet, as noted in , one is typically not interested in the minimization of the empirical risk—that is, a finite sum of functions—with high precision, but instead, one should focus on the expected risk involving the true (unknown) data distribution. When one can draw an infinite number of samples from this distribution, the true risk (1) may be minimized by using appropriate stochastic optimization techniques. Unfortunately, fast methods designed for deterministic objectives would not apply to this setting; methods based on stochastic approximations admit indeed optimal “slow” rates that are typically $O(1/\sqrt{k})$ for convex functions and $O(1/k)$ for strongly convex ones, depending on the exact assumptions made on the problem, where $k$ is the number of noisy gradient evaluations .

Better understanding the gap between deterministic and stochastic optimization is one goal of this paper. Specifically, we are interested in Nesterov’s acceleration of gradient-based approaches . In a nutshell, gradient descent or its proximal variant applied to a $\mu$-strongly convex $L$-smooth function achieves an exponential convergence rate $O((1-\mu/L)^{k})$ in the worst case in function values, and a sublinear rate $O(L/k)$ if the function is simply convex ($\mu=0$). By interleaving the algorithm with clever extrapolation steps, Nesterov showed that faster convergence could be achieved, and the previous convergence rates become $O((1-\sqrt{\mu/L})^{k})$ and $O(L/k^{2})$, respectively. Whereas no clear geometrical intuition seems to appear in the literature to explain why acceleration occurs, proof techniques to show accelerated convergence and extensions to a large class of other gradient-based algorithms are now well established .

Yet, the effect of Nesterov’s acceleration to stochastic objectives remains poorly understood since existing unaccelerated algorithms such as stochastic mirror descent and their variants already achieve the optimal asymptotic rate. Besides, negative results also exist, showing that Nesterov’s method may be unstable when the gradients are computed approximately . Nevertheless, several approaches such as have managed to show that acceleration may be useful to forget faster the algorithm’s initialization and reach a region dominated by the noise of stochastic gradients; then, “good” methods are expected to asymptotically converge with a rate exhibiting an optimal dependency in the noise variance , but with no dependency on the initialization. A major challenge is then to achieve the optimal rate for these two regimes.

In this paper, we consider an optimization method ${\mathcal{M}}$ with the following property: given an auxiliary strongly convex objective function $h$, we assume that ${\mathcal{M}}$ is able to produce iterates $(z_{t})_{t\geq 0}$ with expected linear convergence to a noise-dominated region—that is, such that

where $C,\tau,B>0$, $h^{\star}$ is the minimum function value, and $\sigma^{2}$ is an upper bound on the variance of stochastic gradients accessed by ${\mathcal{M}}$, which we assume to be uniformly bounded. Whereas such an assumption has limitations, it remains the most standard one for stochastic optimization (see for more realistic settings in the smooth case). The class of methods satisfying (2) is relatively large. For instance, when $h$ is $L$-smooth, the stochastic gradient descent method (SGD) with constant step size $1/L$ and iterate averaging satisfies (2) with $\tau=\mu/L$, $B=1/L$, and $C=1$, see .

In this paper, we extend the Catalyst approach to general stochastic problems.All objectives addressed by the original Catalyst approach are deterministic, even though they may be large finite sums. Here, we consider general expectations as defined in (1). Under mild conditions, our approach is able to turn ${\mathcal{M}}$ into a converging algorithm with a worst-case expected complexity that decomposes into two parts: the first one exhibits an accelerated convergence rate in the sense of Nesterov and shows how fast one forgets the initial point; the second one corresponds to the stochastic regime and typically depends (optimally in many cases) on $\sigma^{2}$. Note that even though we only make assumptions about the behavior of ${\mathcal{M}}$ on strongly convex sub-problems (2), we also treat the case where the objective (1) is convex, but not strongly convex.

Other contributions.

In this paper, we generalize the analysis of Catalyst to handle various new cases. Beyond the ability to deal with stochastic optimization problems, our approach (i) improves Catalyst by allowing sub-problems of the form (2) to be solved approximately in expectation, which is more realistic than the deterministic requirement made in and which is also critical for stochastic optimization, (ii) leads to a new accelerated stochastic gradient descent algorithms for composite optimization with similar guarantees as , (iii) handles the analysis of accelerated proximal gradient descent methods with inexact computation of proximal operators, improving the results of while also treating the stochastic setting.

Finally, we note that the extension of Catalyst we propose is easy to implement. The original Catalyst method introduced in indeed required solving a sequence of sub-problems while controlling carefully the convergence, e.g., with duality gaps. For this reason, Catalyst has sometimes been seen as theoretically appealing but not practical enough . Here, we focus on a simpler and more practical variant presented later in , which consists of solving sub-problems with a fixed computational budget, thus removing the need to define stopping criterions for sub-problems. The code used for our experiments is available here: http://github.com/KuluAndrej/NIPS-2019-code.

Related Work on Inexact and Stochastic Proximal Point Methods.

Catalyst is based on the inexact accelerated proximal point algorithm , which consists in solving approximately a sequence of sub-problems and updating two sequences $(x_{k})_{k\geq 0}$ and $(y_{k})_{k\geq 0}$ by

where $\beta_{k}$ in $(0,1)$ is obtained from Nesterov’s acceleration principles , $\kappa$ is a well chosen regularization parameter, and $\|\cdot\|^{2}$ is the Euclidean norm. The method ${\mathcal{M}}$ is used to obtain an approximate minimizer of $h_{k}$; when ${\mathcal{M}}$ converges linearly, it may be shown that the resulting algorithm (4) enjoys a better worst-case complexity than if ${\mathcal{M}}$ was used directly on $f$, see .

Since asymptotic linear convergence is out of reach when $f$ is a stochastic objective, a classical strategy consists in replacing $F(x)$ in (4) by a finite-sum approximation obtained by random sampling, leading to deterministic sub-problems. Typically without Nesterov’s acceleration (with $y_{k}=x_{k}$), this strategy is often called the stochastic proximal point method . The point of view we adopt in this paper is different and is based on the minimization of surrogate functions $h_{k}$ related to (4), but which are more general and may take other forms than $F(x)+\frac{\kappa}{2}\|x-y_{k\text{--}1}\|^{2}$.

Preliminaries: Basic Multi-Stage Schemes

In this section, we present two simple multi-stage mechanisms to improve the worst-case complexities of stochastic optimization methods, before introducing acceleration principles.

Consider an optimization method ${\mathcal{M}}$ with convergence rate (2) and assume that there exists a hyper-parameter to control a trade-off between the bias $B\sigma^{2}$ and the computational complexity. Specifically, we assume that the bias can be reduced by an arbitrary factor $\eta<1$, while paying a factor $1/\eta$ in terms of complexity per iteration (or $\tau$ may be reduced by a factor $\eta$, thus slowing down convergence). This may occur in two cases:

by using a mini-batch of size $1/\eta$ to sample gradients, which replaces $\sigma^{2}$ by $\eta\sigma^{2}$;

or the method uses a step size proportional to $\eta$ that can be chosen arbitrarily small.

For instance, stochastic gradient descent with constant step size and iterate averaging is compatible with both scenarios . Then, consider a target accuracy $\varepsilon$ and define the sequences $\eta_{k}=1/2^{k}$ and $\varepsilon_{k}=2B\sigma^{2}\eta_{k}$ for $k\geq 0$. We may now solve successively the problem up to accuracy $\varepsilon_{k}$—e.g., with a constant number $O(1/\tau)$ steps of ${\mathcal{M}}$ when using mini-batches of size $1/\eta_{k}=2^{k}$ to reduce the bias—and by using the solution of iteration ${k\text{--}1}$ as a warm restart. As shown in Appendix B, the scheme converges and the worst-case complexity to achieve the accuracy $\varepsilon$ in expectation is

For instance, one may run SGD with constant step size $\eta_{k}/L$ at stage $k$ with iterate averaging as in , which yields $B=1/L$, $C=1$, and $\tau=\mu/L$. Then, the left term is the classical complexity $O((L/\mu)\log(1/\varepsilon))$ of the (unaccelerated) gradient descent algorithm for deterministic objectives, whereas the right term is the optimal complexity for stochastic optimization in $O(\sigma^{2}/\mu\varepsilon)$. Similar restart principles appear for instance in in the design of a multistage accelerated SGD algorithm.

Restart: from sub-linear to linear rate with strong convexity.

A natural question is whether asking for a linear rate in (2) for strongly convex problems is a strong requirement. Here, we show that a sublinear rate is in fact sufficient for our needs by generalizing a restart technique introduced in for stochastic optimization, which was previously used for deterministic objectives in .

Specifically, consider an optimization method ${\mathcal{M}}$ such that the convergence rate (2) is replaced by

where $D,d>0$ and $z^{\star}$ is a minimizer of $h$. Assume now that $h$ is $\mu$-strongly convex with $D\geq\mu$ and consider restarting $s$ times the method ${\mathcal{M}}$, each time running ${\mathcal{M}}$ for constant $t^{\prime}=\lceil(2D/\mu)^{1/d}\rceil$ iterations. Then, it may be shown (see Appendix B) that the relation (2) holds with constant $t=st^{\prime}$, $\tau=\frac{1}{2t^{\prime}}$, and $C=1$. If a mini-batch or step size mechanism is available, we may then proceed as before and obtain a converging scheme with complexity (5), e.g., by using mini-batches of exponentially increasing sizes once the method reaches a noise-dominated region, and by using a restart frequency of order $O(1/\tau)$.

Generic Multi-Stage Approaches with Acceleration

We are now in shape to introduce a generic acceleration framework that generalizes (4). Specifically, given some point $y_{k\text{--}1}$ at iteration $k$, we consider a surrogate function $h_{k}$ related to a parameter $\kappa>0$, an approximation error $\delta_{k}\geq 0$, and an optimization method ${\mathcal{M}}$ that satisfy the following properties:

$h_{k}$ is $(\kappa+\mu)$-strongly convex, where $\mu$ is the strong convexity parameter of $f$;

The generic acceleration framework is presented in Algorithm 1. Note that the conditions on $h_{k}$ bear similarities with estimate sequences introduced by Nesterov ; indeed, ($\mathcal{H}_{3}$) is a direct generalization of (2.2.2) from and ($\mathcal{H}_{2}$) resembles (2.2.1). However, the choices of $h_{k}$ and the proof technique are significantly different, as we will see with various examples below. We also assume at the moment that the exact minimizer $x_{k}^{\star}$ of $h_{k}$ is available, which differs from the Catalyst framework ; the case with approximate minimization will be presented in Section 4.1.

The proof of the proposition is given in Appendix C and is based on an extension of the analysis of Catalyst . Next, we present various application cases leading to algorithms with acceleration.

When $f$ is deterministic and the proximal operator of $\psi$ (see Appendix A for the definition) can be computed in closed form, choose $\kappa=L-\mu$ and define

Consider ${\mathcal{M}}$ that minimizes $h_{k}$ in closed form: $x_{k}\!=\!x_{k}^{\star}\!=\!\text{Prox}_{\psi/L}\left[y_{k\text{--}1}-\frac{1}{L}\nabla f(y_{k\text{--}1})\right]$. Then, ($\mathcal{H}_{1}$) is obvious; ($\mathcal{H}_{2}$) holds from the convexity of $f$, and ($\mathcal{H}_{3}$) with $\delta_{k}=0$ follows from classical inequalities for $L$-smooth functions . Finally, we recover accelerated convergence rates .

Accelerated proximal point algorithm.

We consider $h_{k}$ given in (4) with exact minimization (thus an unrealistic setting, but conceptually interesting) with $\kappa=L-\mu$. Then, the assumptions ($\mathcal{H}_{1}$), ($\mathcal{H}_{2}$), and ($\mathcal{H}_{3}$) are satisfied with $\delta_{k}=0$ and we recover the accelerated rates of .

Accelerated stochastic gradient descent with prox.

A more interesting choice of surrogate is

where we used the non-expansiveness of the proximal operator . Therefore, ($\mathcal{H}_{3}$) holds with $\delta_{k}\!=\!\sigma^{2}/(\kappa+\mu)$. The resulting algorithm is similar to and offers the same guarantees. The novelty of our approach is then a unified convergence proof for the deterministic and stochastic cases.

Consider Algorithm 1 with $h_{k}$ defined in (10). When $f$ is $\mu$-strongly convex, choose $\kappa=L-\mu$. Then,

which is of the form (2) with $\tau=\sqrt{\mu/L}$ and $B=\sigma^{2}/(\sqrt{\mu L})$. Interestingly, the optimal complexity $O\left(\sqrt{L/\mu}\log((F(x_{0})-F^{\star})/\varepsilon)+\sigma^{2}/\mu\varepsilon\right)$ can be obtained by using the first restart strategy presented in Section 3, see Eq. (5), either by using increasing mini-batches or decreasing step sizes.

When the objective is convex, but not strongly convex, Proposition 1 gives a bias term $O(\sigma^{2}k/\kappa)$ that increases linearly with $k$. Yet, the following corollary exhibits an optimal rate with finite horizon, when both $\sigma^{2}$ and an upper-bound on $\|x_{0}-x^{\star}\|^{2}$ are available. Even though non-practical, the result shows that our analysis recovers the optimal dependency in the noise level, as and others.

Consider a fixed budget $K$ of iterations of Algorithm 1 with $h_{k}$ defined in (10). When $\kappa=\max(L,\sigma(K+1)^{3/2}/\|x_{0}-x^{\star}\|)$,

While all the previous examples use the choice $x_{k}=x_{k}^{\star}$, we will see in Section 4.2 cases where we may choose $x_{k}\neq x_{k}^{\star}$. Before that, we introduce a variant when $x_{k}^{\star}$ is not available.

In principle, it is possible to design other surrogates, which would lead to new algorithms coming with convergence guarantees given by Propositions 1 and 4, but the given examples (4), (10), and (10) already cover all important cases considered in the paper for functions of the form (1).

1 Variant with Inexact Minimization

In this variant, presented in Algorithm 2, $x_{k}^{\star}$ is not available and we assume that ${\mathcal{M}}$ also satisfies:

The next proposition, proven in Appendix C, gives us some insight on how to achieve acceleration.

Consider Alg. 2. Then, for any $\gamma\in(0,1]$,

To maintain the accelerated rate, the sequence $(\delta_{k})_{k\geq 0}$ needs to converge at a similar speed as in Proposition 1, but the dependency in $\varepsilon_{k}$ is slightly worse. Specifically, when $\mu$ is positive, we may have both $(\varepsilon_{k})_{k\geq 0}$ and $(\delta_{k})_{k\geq 0}$ decreasing at a rate $O((1-\rho)^{k})$ with $\rho<\sqrt{q}/2$, but we pay a factor $(1/\sqrt{q})$ compared to (8). When $\mu=0$, the accelerated $O(1/k^{2})$ rate is preserved whenever $\varepsilon_{k}=O(1/k^{4+2\gamma})$ and $\delta_{k}=O(1/k^{3+\gamma})$, but we pay a factor $O(1/\gamma)$ compared to (8).

Consider Alg. 2 with $h_{k}$ defined in (4). Then, for $k\geq 2$,

Our results improve upon Catalyst in two aspects that are crucial for stochastic optimization: (i) we allow the sub-problems to be solved in expectation, whereas Catalyst requires the stronger condition $h_{k}(x_{k})-h_{k}^{\star}\leq\varepsilon_{k}$; (ii) Proposition 5 removes the requirement of to perform a full gradient step for initializing the method ${\mathcal{M}}$ in the composite case (see Prop. 12 in ).

Proximal gradient descent with inexact prox [45].

The surrogate (10) with inexact minimization can be treated in the same way as Catalyst, which provides a unified proof for both problems. Then, we recover the results of , while allowing inexact minimization to be performed in expectation.

Stochastic Catalyst.

Accelerated stochastic proximal gradient descent with inexact prox.

Finally, consider $h_{k}$ defined in (10) but the proximal operator is computed approximately, which, to our knowledge, has never been analyzed in the stochastic context. Then, it may be shown (see Appendix B for details) that, even though $x_{k}^{\star}$ is not available, Proposition 4 holds nonetheless with $\delta_{k}=2\varepsilon_{k}+{3\sigma^{2}}/({2(\kappa+\mu))}$. Then, an interesting question is how small should $\varepsilon_{k}$ be to guarantee the optimal dependency with respect to $\sigma^{2}$ as in Corollary 2. In the strongly-convex case, Proposition 4 simply gives $\varepsilon_{k}=O(\sqrt{q}\sigma^{2}/(\kappa+\mu))$ such that $\delta_{k}\approx\varepsilon_{k}/\sqrt{q}$.

2 Exploiting methods ℳℳ{\mathcal{M}} providing strongly convex surrogates

Among various application cases, we have seen an extension of Catalyst to stochastic problems. To achieve convergence, the strategy requires a mechanism to reduce the bias $B\sigma^{2}$ in (2), e.g., by using mini-batches or decreasing step sizes. Yet, the approach suffers from two issues: (i) some of the parameters are based on unknown quantities such as $\sigma^{2}$; (ii) the worst-case complexity exhibits a sub-optimal dependency in $\sigma^{2}$, typically of order $1/\sqrt{q}$ when $\mu>0$. Whereas practical workarounds for the first point are discussed in Section 5, we now show how to solve the second one in some cases, by using Algorithm 1 with an optimization method ${\mathcal{M}}$, which is able not only to minimize an auxiliary objective $H_{k}$, but also at the same time is able to provide a model $h_{k}$, typically a quadratic function, which is easy to minimize. Consider then a method ${\mathcal{M}}$ satisfying (2) and which produces, after $T$ steps, a point $x_{k}$ and a surrogate $h_{k}$ such that

As shown in Appendix D, even though (14) looks technical, a large class of optimization techniques are able to provide the condition (14), including many variants of proximal stochastic gradient descent methods with variance reduction such as SAGA , MISO , SDCA , or SVRG .

Whereas (14) seems to be a minor modification of (2), an important consequence is that it will allow us to gain a factor $1/\sqrt{q}$ in complexity when $\mu>0$, corresponding precisely to the sub-optimality factor. Therefore, even though the surrogate $H_{k}$ needs only be minimized approximately, the condition (14) allows us to use Algorithm 1 instead of Algorithm 2. The dependency with respect to $\delta_{k}$ being better than $\varepsilon_{k}$ (by $1/\sqrt{q}$), we have then the following result:

Consider Algorithm 1 with a method ${\mathcal{M}}$ and surrogate $h_{k}$ satisfying (14) when ${\mathcal{M}}$ is used to minimize $H_{k}$ by using $x_{k\text{--}1}$ as a warm restart. Assume that $f$ is $\mu$-strongly convex and that there exists a parameter $\eta$ that can reduce the bias $B\sigma^{2}$ by a factor $\eta<1$ while paying a factor $1/\eta$ in terms of inner-loop complexity.

The term on the left is the accelerated rate of Catalyst for deterministic problems, whereas the term on the right is potentially optimal for strongly convex problems, as illustrated in the next table. We provide indeed practical choices for the parameters $\kappa$, leading to various values of $B,\tau,q$, for the proximal stochastic gradient descent method with iterate averaging as well as variants of SAGA,MISO,SVRG that can cope with stochastic perturbations, which are discussed in Appendix D. All the values below are given up to universal constants to simplify the presentation.

Experiments

In this section, we perform numerical evaluations by following , which was notably able to make SVRG and SAGA robust to stochastic noise, and accelerate SVRG. Code to reproduce the experiments is provided with the submission and more details and experiments are given in Appendix E.

where $\phi$ is either the logistic loss $\phi(u)=\log(1+e^{-u})$, or the squared hinge loss $\phi(u)=\frac{1}{2}\max(0,1-u)^{2}$, which are both $L$-smooth, with $L=0.25$ for logistic and $L=1$ for the squared hinge loss. Studying the squared hinge loss is interesting since its gradients are unbounded on the optimization domain, which may break the bounded noise assumption. The regularization parameter $\mu$ acts as the strong convexity constant for the problem and is chosen among the smallest values one would try when performing parameter search, e.g., by cross validation. Specifically, we consider $\mu=1/10n$ and $\mu=1/100n$, where $n$ is the number of training points; we also try $\mu=1/1000n$ to evaluate the numerical stability of methods in very ill-conditioned problems. Following , we consider DropOut perturbations —that is, setting each component $(\nabla f(x))_{i}$ to 0 with a probability $\delta$ and to $(\nabla f(x))_{i}/(1-\delta)$ otherwise. This procedure is motivated by the need of a simple optimization benchmark illustrating stochastic finite-sum problems, where the amount of perturbation is easy to control. The settings used in our experiments are $\delta=0$ (no noise) and $\delta\in\{0.01,0.1\}$.

Datasets.

alpha is from the Pascal Large Scale Learning Challenge websitehttp://largescale.ml.tu-berlin.de/ and contains $n=250\,000$ points in dimension $p=500$.

gene consists of gene expression data and the binary labels $b_{i}$ characterize two different types of breast cancer. This is a small dataset with $n=295$ and $p=8\,141$.

ckn-cifar is an image classification task where each image from the CIFAR-10 datasethttps://www.cs.toronto.edu/~kriz/cifar.html is represented by using a two-layer unsupervised convolutional neural network . We consider here the binary classification task consisting of predicting the class 1 vs. other classes, and use our algorithms for the classification layer of the network, which is convex. The dataset contains $n=50\,000$ images and the dimension of the representation is $p=9\,216$.

Methods.

We consider the variants of SVRG and SAGA of , which use decreasing step sizes when $\delta>0$ (otherwise, they do not converge). We use the suffix “-d” each time decreasing step sizes are used. We also consider Katyuasha when $\delta=0$, and the accelerated SVRG method of , denoted by acc-SVRG. Then, SVRG-d, SAGA-d, acc-SVRG-d are used with the step size strategies described in , by using the code provided to us by the authors.

Practical questions and implementation.

In all setups, we choose the parameter $\kappa$ according to theory, which are described in the previous section, following Catalyst . For composite problems, Proposition 5 suggests to use $x_{k\text{--}1}$ as a warm start for inner-loop problems. For smooth ones, shows that in fact, other choices such as $y_{k\text{--}1}$ are appropriate and lead to similar complexity results. In our experiments with smooth losses, we use $y_{k\text{--}1}$, which has shown to perform consistently better.

Experiments and conclusions.

We run each experiment five time with a different random seed and average the results. All curves also display one standard deviation. Appendix E contains numerous experiments, where we vary the amount of noise, the type of approach (SVRG vs. SAGA), the amount of regularization $\mu$, and choice of loss function. In Figure 1, we show a subset of these curves. Most of them show that acceleration may be useful even in the stochastic optimization regime, consistently with . At the same time, all acceleration methods may not perform well for very ill-conditioned problems with $\mu=1/1000n$, where the sublinear convergence rates for convex optimization ($\mu=0$) are typically better than the linear rates for strongly convex optimization ($\mu>0$). However, these ill-conditioned cases are often unrealistic in the context of empirical risk minimization.

Acknowledgments

This work was supported by the ERC grant SOLARIS (number 714381) and ANR 3IA MIAI@Grenoble Alpes. The authors would like to thank Anatoli Juditsky for numerous interesting discussions that greatly improved the quality of this manuscript.

References

Appendix A Useful Results and Definitions

In this section, we present auxiliary results and definitions.

Consider the sequence in $(0,1)$ defined by the recursion

and define $A_{k}=\prod_{t=1}^{k}(1-\alpha_{t})$. Then,

if $q=0$ and $\alpha_{0}=1$, then, for all $k\geq 1$,

if $\alpha_{0}=\sqrt{q}$, then for all $k\geq 1$,

if $\alpha_{0}=1$, then for all $k\geq 1$,

Let us prove the first point when $q=0$ and $\alpha_{0}=1$. The relation $A_{k}=\alpha_{k}^{2}$ is obvious for all $k\geq 1$ and the relation $\alpha_{k}^{2}\leq\frac{4}{(k+2)^{2}}$ holds for $k=0$. By induction, let us assume that we have the relation $\alpha_{{k\text{--}1}}^{2}\leq\frac{4}{(k+1)^{2}}$ and let us show that it propagates for $\alpha_{k}^{2}$. Assume, by contradiction, that $\alpha_{k}^{2}>\frac{4}{(k+2)^{2}}$, meaning that $\alpha_{k}>\frac{2}{(k+2)}$. Then,

and we obtain a contradiction. Therefore, $\alpha_{k}^{2}\leq\frac{4}{(k+2)^{2}}$ and the induction hypothesis allows us to conclude for all $k\geq 1$. Then, note that we also have for all $k\geq 1$,

Second point.

The second point is obvious by induction.

Third point.

For the third point, we simply assume $\alpha_{0}=1$ such that $\alpha_{0}\geq\sqrt{q}$. Then, the relation $\alpha_{k}\geq\sqrt{q}$ and therefore $A_{k}\leq(1-\sqrt{q})^{k}$ are easy to show by induction. Then, consider the sequence defined recursively by $u_{k}^{2}=(1-u_{k})u_{{k\text{--}1}}^{2}$ with $u_{0}=1$. From the first point, we have that $\frac{\sqrt{2}}{k+2}\leq u_{k}\leq\frac{{2}}{k+2}$. We will show that $\alpha_{k}\geq u_{k}$ for all $k\geq 0$, which will be sufficient to conclude since then we would have $A_{k}\leq\prod_{t=1}^{k}(1-u_{t})\leq\frac{4}{(k+2)^{2}}$. First, we note that $\alpha_{0}=u_{0}$; then, assume that $\alpha_{{k\text{--}1}}\geq u_{{k\text{--}1}}$ and also assume by contradiction that $\alpha_{k}>u_{k}$. This implies that

which contradicts the assumption $\alpha_{k}>u_{k}$. This allows us to conclude by induction. ∎

Consider the sequence $\theta_{j}=\frac{\gamma}{(1+j)^{1+\gamma}}$ with $\gamma$ in $(0,1]$. Then,

We use the classical inequality $\log(1+u)\geq\frac{u}{1+u}$ for all $u>-1$:

when noting that the function $g(x)=(1+x)^{1+\gamma}-x^{1+\gamma}$ is greater than $\gamma$ for all $x\geq 1$, since $g(1)\geq 1\geq\gamma$ and $g$ is non-decreasing. Then,

Appendix B Details about Complexity Results

Consider the complexity (2) with $h=F$. To achieve the accuracy $2B\sigma^{2}$, it is sufficient to run the method ${\mathcal{M}}$ for $t_{0}$ iterations, such that

It is then easy to see that this inequality is satisfied as soon as $t_{0}$ is greater than $\frac{1}{\tau}\log(C(F(x_{0})-F^{\star})/B\sigma^{2})$. Since $\varepsilon\leq B\sigma^{2}$ and using the concavity of the logarithm function, it is also sufficient to choose $t_{0}=\frac{1}{\tau}\log(C(F(x_{0})-F^{\star})/\varepsilon)$.

and (5) follows by elementary calculations.

B.2 Obtaining (5) from (6)

Since $h$ is $\mu$-strongly convex, we notice that (6) implies the rate

by using the strong convexity inequality $h(z_{0})\geq h^{\star}+\frac{\mu}{2}\|z_{0}-z^{\star}\|^{2}$. After running the algorithm for $t^{\prime}=\lceil(2D/\mu)^{1/d}\rceil$ iterations, we can show that

Then, when restarting the procedure $s$ times (using the solution of the previous iteration as initialization), and denoting by $h_{st^{\prime}}$ the last iterate, it is easy to show that

Then, calling $t=st^{\prime}$, we can use the inequality $2^{-u}\leq 1-\frac{u}{2}$ for $u$ in $$, due to convexity, and

which gives us (2) with $C=1$ and $\tau=\frac{1}{2t^{\prime}}$. It is then easy to obtain (5) by following similar steps as in Section B.1, by noticing that the restart frequency is of the same order $O(1/\tau)$.

B.3 Details about (13)

Outer-loop complexity.

Global complexity.

where the last relation uses the fact that $\varepsilon=O(\varepsilon_{K}/q)=O((1-\sqrt{q}/3)^{K}(F(x_{0})-F^{\star})/q)$.

B.4 Complexity of accelerated stochastic proximal gradient descent with inexact prox

Assume that $h_{k}(x_{k})-h_{k}^{\star}\leq\varepsilon_{k}$. Then, following similar steps as in (11),

And thus, $\delta_{k}=2\varepsilon_{k}+\frac{3\sigma^{2}}{2(\kappa+\mu)}$.

Appendix C Proofs of Main Results

In order to treat both propositions jointly, we introduce the quantity

with $v_{0}=x_{0}$, as well as $\eta_{k}=\frac{\alpha_{k}-q}{1-q}$ for all $k\geq 0$.

Note that the following relations hold for all $k\geq 1$, keeping in mind that $\alpha_{k}^{2}=(1-\alpha_{k})\alpha_{k\text{--}1}^{2}+q\alpha_{k}$:

Then, based on the previous relations, we have

Introduce now the following quantity for the convergence analysis:

and consider $x=z_{k\text{--}1}$ in (17) while taking expectations, noting that all random variables indexed by ${k\text{--}1}$ are deterministic given ${\mathcal{F}}_{k\text{--}1}$,

where the last inequality is due to ($\mathcal{H}_{2}$).

The first relation is due to the convexity of $f$; the second one can be obtained from the definition of $v_{k}$ in (16) after simple calculations; the last one can be obtained as in the proof of Theorem 3 in (end of page 16).

We may now come back to (18) and we use the relations (19):

It is then easy to see that the terms involving $X_{k\text{--}1}$ cancel each other since $\eta_{k\text{--}1}=\alpha_{k\text{--}1}-\frac{\mu}{\kappa}(1-\alpha_{k\text{--}1})$.

We may finally define the Lyapunov function

For variant Algorithm 1, we have $\Delta_{k}(z_{k\text{--}1})=0$ since $w_{k}=x_{k}^{\star}$, and we obtain the following relation by unrolling the recursion:

Specialization to μ>0𝜇0\mu>0.

When $\mu>0$, we have $\alpha_{0}=\sqrt{q}$ and

Specialization to μ=0𝜇0\mu=0.

When $\mu=0$, we have $\alpha_{0}=1$ and $S_{0}=\frac{\kappa}{2}\|x_{0}-x^{\star}\|^{2}$. Then, according to Lemma 8 and (22), for $k\geq 1$,

and we obtain the second part of (8) noting that $A_{k\text{--}1}\leq\frac{4}{(k+1)^{2}}$ and that $A_{j\text{--}1}\geq\frac{2}{(j+1)^{2}}$. Then, Proposition 1 is proven.

Proof of Proposition 4.

When $w_{k}=x_{k}$, we need to control the quantity $\Delta_{k}(z_{k\text{--}1})$. Consider any scalar $\theta_{k}$ in $(0,1)$. Then,

Then, we take expectations and, noticing that the quadratic term involving $\|x^{\star}-v_{k}\|^{2}$ is smaller than $\theta_{k}S_{k}/(1-\alpha_{k})$ in expectation (from the definition of $S_{k}$ in (20)), we obtain

Specialization to μ>0𝜇0\mu>0.

When $\mu>0$, we have $\alpha_{k}=\sqrt{q}$ for all $k\geq 0$. Then, we may choose $\theta_{k}=\frac{\sqrt{q}}{2}$; then, $1-\sqrt{q}\leq\left(1-\frac{\sqrt{q}}{2}\right)^{2}$ and \frac{A_{k}}{\Theta_{k}}\leq\big{(}1-\frac{\sqrt{q}}{2}\big{)}^{k} for all $k\geq 0$. By using the relation (23), we obtain

Specialization to μ=0𝜇0\mu=0.

When $\mu=0$, we have $\alpha_{0}=1$ and $S_{0}=\frac{\kappa}{2}\|x_{0}-x^{\star}\|^{2}$. We may then choose $\theta_{k}=\frac{\gamma}{(k+1)^{1+\gamma}}$ for any $\gamma$ in $(0,1]$, leading to $e^{-(1+\gamma)}\leq\Theta_{k}\leq 1$ for all $k\geq 0$ according to Lemma 9. Besides, according to the proof of Lemma 8, $\frac{2}{(k+2)^{2}}\leq A_{k}\leq\frac{4}{(k+2)^{2}}$ for all $k\geq 1$.

which yields the second part of Proposition (4). ∎

C.2 Proof of Proposition 5

Assume that for $k\geq 2$, we have the relation

Then, we want to evaluate the quality of the initial point $x_{k\text{--}1}$ to minimize $h_{k}$.

where the third inequality uses the non-expansiveness of the proximal operator; the fourth inequality uses the inequality $a^{\top}b\leq\frac{\|a\|^{2}}{2}+\frac{\|b\|^{2}}{2}$ for vectors $a,b$, and the last inequality uses the strong convexity of $h_{k\text{--}1}$. Then, we may use the same upper-bound on $\|y_{k\text{--}1}-y_{k\text{--}2}\|$ as [33, Proposition 12], namely

C.3 Proof of Proposition 6

The proof is similar to the derivation described in Section B.3.

Outer-loop complexity.

Global complexity.

We use the exact same derivations as in Section B.3 except that we use the fact that $\varepsilon=O(\varepsilon_{K}/\sqrt{q})=O((1-\sqrt{q}/3)^{K}(F(x_{0})-F^{\star})/\sqrt{q})$ instead of $\varepsilon=O(\varepsilon_{K}/q)$, which gives us the desired complexity.

Appendix D Methods ℳℳ{\mathcal{M}} with Duality Gaps Based on Strongly-Convex Lower Bounds

In this section, we summarize a few results from and introduce minor modifications to guarantee the condition (14). For solving a stochastic composite objectives such as (1), where $F$ is $\mu$-strongly convex, consider an algorithm ${\mathcal{M}}$ performing the following classical updates

where $\eta\leq 1/L$, and the variance of $g_{t}$ is upper-bounded by $\sigma_{t}^{2}$. Inspired by estimate sequences from , the authors of build recursively a $\mu$-strongly convex quadratic function $d_{t}$ of the form

From the proof of Proposition 1 in , we then have

which is a minor modification of Proposition 1 in that is better suited to our purpose.

Assume now that $\sigma_{t}=\sigma$ for all $k\geq 1$. Following the iterate averaging procedure used in Theorem 1 of , which produces an iterate $\hat{z}_{t}$, we obtain

where $z^{\star}$ is a minimizer of $F$, which is sufficient to guarantee (2) given that $d_{t}(z^{\star})\geq d_{t}^{\star}$.

such that ($\mathcal{H}_{2}$) is satisfied, and finally (29) becomes

Variance-reduction methods.

In , gradient estimators $g_{t}$ with variance reduction are studied, leading to variants of SAGA , MISO , and SVRG , which can deal with the stochastic finite-sum problem presented in Section 1. Then, the variance of $\sigma_{t}^{2}$ decreases (Proposition 2 in ).

Let us then consider again the guarantees of the method obtained when minimizing $F$ with $\frac{\mu}{L}\leq\frac{1}{5n}$. From Corollary 5 of , we have

and (2) is satisfied. Consider now two cases at iteration $T$:

otherwise, it is easy to modify Theorem 2 and Corollary 5 of to obtain

Consider now applying the method for minimizing $H_{k}$, with the same choice of $d_{0}^{\star}$ as (31), which ensures ($\mathcal{H}_{2}$), and same definitions as above for $x_{k}$ and $h_{k}$. Note that the conditions on $\mu$ and $L$ above are satisfied when $\kappa=\frac{L}{5n}-\mu$ under the condition $\frac{L}{5n}\geq\mu$. Then, we have from the previous results, after replacing $F$ by $H_{k}$ making the right subsitutions

Other schemes.

Whereas we have presented approaches were $d_{t}$ is quadratic, also studies another class of algorithms where $d_{t}$ is composite (see Section 2.2 in ). The results we present in this paper can be extended to such cases, but for simplicity, we have focused on quadratic surrogates.

Appendix E Additional Experimental Material

The numerical evaluation was performed by using four nodes of a CPU cluster with 56 cores of Intel CPUs each. The full set of experiments presented in this paper (with $5$ runs for each setup) takes approximately half a day.

Making plots.

We run each experiment five times and average the outputs. We display plots on a logarithmic scale for the primal gap $F(x_{k})-F^{\star}$ (with $F^{\star}$ estimated as the minimum value observed from all runs). Note that for SVRG, one iteration is considered to perform two epochs since it requires accessing the full dataset every $n$ iterations on average.

E.1 Additional experiments.

We start evaluating the acceleration approach when there is no noise. This is essentially evaluating the original Catalyst method in a deterministic setup in order to obtain a baseline comparison when $\delta=0$. The results are presented in Figures 2 and 3 for the logistic regression problem. As predicted by theory, acceleration is more important when conditioning is low (bottom curves).

Stochastic acceleration with no noise, δ=0.01𝛿0.01\delta=0.01 and δ=0.1𝛿0.1\delta=0.1.

Then, we perform a similar experiments by adding noise and report the results in Figures 4, 5, 6, 7. In general, the stochastic Catalyst approach seems to perform on par with the accelerated SVRG approach of and even better in one case.

Evaluating the square hinge loss.

In Figure 8, we perform experiments using the square hinge loss, where the methods perform similarly as for the logistic regression case, despite the fact that the bounded noise assumption does not necessarily hold on the optimization domain for the square hinge loss.

Evaluating ill-conditioned problems.

Finally, we study in Figure 10 how the methods behave when the problems are badly conditioned. There, acceleration seems to work on ckn-cifar, but fails on gene and alpha, suggestions that acceleration is difficult to achieve when the condition number is extremely low.