A Universally Optimal Multistage Accelerated Stochastic Gradient Method

Introduction

First order optimization methods play a key role in solving large scale machine learning problems due to their low iteration complexity and scalability with large data sets. In several cases, these methods operate with noisy first order information either because the gradient is estimated from draws or subset of components of the underlying objective function or noise is injected intentionally due to privacy or algorithmic considerations . A fundamental question in this setting is to design fast algorithms with optimal convergence rate, matching the lower bounds on the oracle complexity in terms of target accuracy and other important parameters both for the deterministic and stochastic case (i.e., with or without gradient errors).

In this paper, we design an optimal first order method to solve the problem

This oracle model is commonly considered in the literature (see e.g. ). In Appendix K, we show how our analysis can be extended to the following more general noise setting, same as the one studied in , where the variance of the noise is allowed to grow linearly with the squared distance to the optimal solution:

With noise, Raginsky and Rakhlin provided the following (much larger) lower boundThe authors show this result for $\mu=1$. Nonetheless, it can be generalized to any $\mu>0$ by scaling the problem parameters properly. on function suboptimality which also provides a lower bound on the variance term:

Several algorithms have been proposed in the recent literature attempting to achieve these lower bounds.Here we review their error bounds after $n$ iterations highlighting dependence on $\sigma^{2}$, $n$, and initial point $x_{0}$, suppressing $\mu$ and $L$ dependence. Xiao obtains $\mathcal{O}(\log(n)/n)$ performance guarantees in expected suboptimality for an accelerated version of the dual averaging method. Dieuleveut et al. consider quadratic objective function and develop an algorithm with averaging to achieve the error bound $\mathcal{O}(\tfrac{\sigma^{2}}{n}+\tfrac{\|x_{0}-x^{*}\|^{2}}{n^{2}})$. Hu et al. consider general strongly convex and smooth functions and achieve an error bound with similar dependence under the assumption of bounded noise. Ghadimi and Lan and Chen et al. extend this result to the noise model in (3) by introducing the accelerated stochastic approximation algorithm (AC-SA) and optimal regularized dual averaging algorithm (ORDA), respectively. Both AC-SA and ORDA have multistage versions presented in and where authors improve the bias term of their single stage methods to the optimal $\exp(-\mathcal{O}(1)n/\sqrt{\kappa})$ by exploiting knowledge of $\sigma$ and the optimality gap $\Delta$, i.e., an upper bound for $f(x_{0})-f^{*}$, in the operation of the algorithm. Another closely related paper is which proposed $\mu$AGD+ and showed under additive noise model that it admits the error bound $\mathcal{O}(\tfrac{\sigma^{2}}{n}+\tfrac{\|x_{0}-x^{*}\|^{2}}{n^{p}})$ for any $p\geq 1$ where the constants grow with $p$, and in particular, they achieve the bound $\mathcal{O}(\tfrac{\sigma^{2}\log n}{n}+\tfrac{\|x_{0}-x^{*}\|^{2}\log n}{n^{\log n}})$ for $p=\log n$.

In this paper, we introduce the class of Multistage Accelerated Stochastic Gradient (M-ASG) methods that are universally optimal, achieving the lower bound both in the noiseless deterministic case and the noisy stochastic case up to some constants independent of $\mu$ and $L$. M-ASG proceeds in stages that use a stochastic version of Nesterov’s accelerated method with a specific restart and parameterization. Given an arbitrary length and constant stepsize for the first stage together with geometrically growing lengths and shrinking stepsizes for the following stages, we first provide a general convergence rate result for M-ASG (see Theorem 3.4). Given the computational budget $n$, a specific choice for the length of the first stage is shown to achieve the optimal error bound without requiring knowledge of the noise bound $\sigma^{2}$ and the initial optimality gap (See Corollary 3.8). To the best of our knowledge, this is the first algorithm that achieves such a lower bound under such informational assumptions. In Table 1, we provide a comparison of our algorithm with other algorithms in terms of required assumptions and optimality of their results in both bias and variance terms. In particular, we consider ACSA , Multistage AC-SA , ORDA and Multistage ORDA , and the algorithm proposed in .

Our paper builds on an analysis of Nesterov’s accelerated stochastic method with a specific momentum parameter presented in Section 2 which may be of independent interest. This analysis follows from a dynamical system representation and study of first order methods which has gained attention in the literature recently . In Section 3, we present the M-ASG algorithm, and characterize its behavior under different assumptions as summarized in Table 1. In particular, we show that it achieves the optimal convergence rate with the given budget of iterations $n$. In Section 4, we show how additional information such as $\sigma$ and $\Delta$ can be leveraged in our framework to improve practical performance. Finally, in Section 5, we provide numerical results on the comparison of our algorithm with some of the other most recent methods in the literature.

Modeling Accelerated Gradient method as a dynamical system

In this section we study Nesterov’s Accelerated Stochastic Gradient method (ASG) with the stochastic first-order oracle in (3):

where $\alpha\in(0,\frac{1}{L}]$ is the stepsize and $\beta=\tfrac{1-\sqrt{\alpha\mu}}{1+\sqrt{\alpha\mu}}$ is the momentum parameter. This choice of momentum parameter has already been studied in the literature, e.g., . In the next lemma, we provide a new motivation for this choice by showing that for quadratic functions and in the noiseless setting, this momentum parameter achieves the fastest asymptotic convergence rate for a given fixed stepsize $\alpha\in(0,\frac{1}{L}]$. The proof of this lemma is provided in Appendix A.

for some non-negative sequence $\{\epsilon_{k}\}_{k}$ that goes to zero is $\rho=1-\sqrt{\alpha\mu}$Note that although this rate is asymptotic, its smaller than the non-asymptotic rate that we provide for general strongly convex functions in Theorem 2.3, as there $\rho=\sqrt{1-\sqrt{\alpha\mu}}$. and it is achieved by $\beta=\tfrac{1-\sqrt{\alpha\mu}}{1+\sqrt{\alpha\mu}}$. As a consequence, for this choice of $\beta$, there exists $\{\epsilon_{k}\}$ such that $\lim_{k\to\infty}\epsilon_{k}=0$ and

Our analysis builds on the reformulation of a first-order optimization algorithm as a linear dynamical system. Following , we write ASG iterations as

We can also relate the state $\xi_{k}$ to the iterate $x_{k}$ in a linear fashion through the identity $x_{k}=T\xi_{k},\quad T\triangleq[I_{d}\quad 0_{d}]$. We study the evolution of the ASG method through the following Lyapunov function which also arises in the study of deterministic accelerated gradient methods:

where $P$ is a symmetric positive semi-definite matrix. We first state the following lemma which can be derived by adapting the proof of Proposition 4.6 in to our setting with less restrictive noise assumption compared to the additive noise model of . Its proof can be found in Appendix B.

We use this lemma and derive the following theorem which characterize the behavior of ASG method for when $\alpha\in(0,1/L]$ and $\beta=\tfrac{1-\sqrt{\alpha\mu}}{1+\sqrt{\alpha\mu}}$ (see the proof in Appendix C).

This result relies on the special structure of $P_{\alpha}$ which will also be key for our analysis in Section 3.

A class of multistage ASG algorithms

In this section, we introduce a class of multistage ASG algorithms, represented in Algorithm 1 which we denote by M-ASG. The main idea is to run ASG with properly chosen parameters $(\alpha_{k},\beta_{k})$ at each stage $k\in{1,\ldots,K}$ for $K\geq 2$ stages. In addition, each new stage is dependent on the previous stage as the first two initial iterates of the new stage are set to the last iterate of the previous stage.

To analyze Algorithm 1, we first characterize the evolution of iterates in one specific stage through the Lyapunov function in (10). The details of the proof is provided in Appendix D.

Given a computational budget of $n$ iterations, we use this result to choose a stepsize that help us achieve an approximately optimal decay in the variance term which yields the following corollary for M-ASG algorithm with $K=1$ stage, and its proof can be found in Appendix E.

provided that $n\geq p\sqrt{\kappa}\max\{2\log(p\sqrt{\kappa}),e\}$.

For subsequent analysis, given $K\geq 1$, for all $1\leq k\leq K$, we define the state vector $\xi_{i}^{k}=\left[{x_{i}^{k}}^{\top},{x_{i-1}^{k}}^{\top}\right]^{\top}$ for $1\leq i\leq n_{k}+1$ –recall that $x_{0}^{k}=x_{1}^{k}=x_{n_{k-1}+1}^{k-1}$, where $K$ is the number of stages. We analyze the performance of each stage with respect to a stage-dependent Lyapunov function $V_{P_{\alpha_{k}}}$. The following lemma relates the performance bounds with respect to consecutive choice of Lyapunov functions, building on our specific restarting mechanism (The proof can be found in Appendix F).

Now, we are ready to state and prove the main result of the paper (see proof in Appendix G):

We next define $N_{K}(p,n_{1})$ as the number of iterations needed to run M-ASG for $K\geq 1$ stages, i.e., $N_{K}(p,n_{1})\triangleq\sum_{k=1}^{K}n_{k}$. Note for $K\geq 2$ and with parameters given in Theorem 3.4,

The next theorem remarks the behavior of M-ASG after running it for $n$ iterations with the parameters in the preceding theorem, and its proof is provided in Appendix H.

Under the premise of Theorem 3.6, choosing $n_{1}=\lceil(p+1)\sqrt{\kappa}\log\left(12(p+1)\kappa\right)\rceil$, the suboptimality error of M-ASG after $n\geq 2n_{1}$ admits

Theorem 3.6 immediately yields the result in Corollary 3.7, (suboptimal with respect to dependence on initial optimality gap); see Appendix I for the proof. Similar rate results have also been obtained by AC-SA and ORDA algorithms.

We continue this section by pointing out some important special cases of our result. We first show in the next corollary how our algorithm is universally optimal and capable of achieving the lower bounds (5) and (6) simultaneously. The proof follows from (19) and $n-n_{1}\geq\frac{n}{2}\geq\sqrt{\kappa}$.

Under the premise of Theorem 3.6, consider a computational budget of $n\geq 2\sqrt{\kappa}$ iterations. By setting $n_{1}=\frac{n}{C}$ for some positive constant $C\geq 2$, we obtain a bound matching the lower bounds in (5) and (6), i.e.,

We note that achieving the lower bound through the M-ASG algorithm requires the knowledge or estimation of the strong convexity constant $\mu$. In some applications, $\mu$ may not be known a priori. However, for regularized risk minimization problems, the regularization parameter is known and it determines the strong convexity constant. It is also worth noting that, even for the deterministic case, has shown that for a wide class of algorithms including ASG, it is not possible to obtain the lower bound (5) without knowing the strong convexity parameter. In addition, in Appendix L, we show how our framework can be extended to obtain nearly optimal results in the merely convex setting; i.e. when $\mu=0$. Finally, note that the Lipschitz constant $L$ can be estimated from data using standard line search techniques in practice, see and [32, Alg. 2].

Recall that we presented a comparison with other state-of-the-art algorithms in Table 1. In particular, this table shows that Multistage AC-SA and Multistage ORDA also achieve the lower bounds provided that noise parameters are known – note we do not make this extra assumption for M-ASG. It is also worth noting that the idea of restart, which plays a key role in achieving the lower bounds, has been studied before in the context of deterministic accelerated methods . However, a naive extension of these restart methods to the stochastic setting leads to a two-stage algorithm which switches from constant step-size to diminishing step-size when the variance term dominates the bias term. Nevertheless, implementing this technique requires the knowledge of $\sigma^{2}$ and optimality gap to tune algorithms for achieving optimal rates in both bias and variance terms. M-ASG, on the other hand, achieves the optimal rates using a specific multistage scheme that does not require the knowledge of the parameter $\sigma^{2}$. In the supplementary material, we also discuss how M-ASG is related to AC-SA and Multistage AC-SA algorithms proposed in .

M-ASG∗: An improved bias-variance trade-off

In section 3, we described a universal algorithm that do not require the knowledge of neither initial suboptimality gap $\Delta$ nor the noise magnitude $\sigma^{2}$ to operate. However, as we will argue in this section, our framework is flexible in the sense that additional information about the magnitude of $\Delta$ or $\sigma^{2}$ can be leveraged to improve practical performance. We first note that several algorithms in the literature assume that an upper bound on $\Delta$ is known or can be estimated, as summarized in Table 1. This assumption is reasonable in a variety of applications when there is a natural lower bound on $f$. For example, in supervised learning scenarios such as support vector machines, regression or logistic regression problems, the loss function $f$ has non-negative values . Similarly, the noise level $\sigma^{2}$ may be known or estimated, e.g., in private risk minimization , the noise is added by the user to ensure privacy; therefore, it is a known quantity.

There is a natural well-known trade-off between constant and decaying stepsizes (decaying with the number of iterations $n$) in stochastic gradient algorithms. Since the noise is multiplied with the stepsize, a stepsize that is decaying with the number of iterations $n$ leads to a decay in the variance term; however, this will slow down the decay of the bias term, which is controlled essentially by the behavior of the underlying deterministic accelerated gradient algorithm (AG) that will give the best performance with the constant stepsize (note that when $\sigma=0$, the bias term gives the known performance bounds for the AG algorithm). The main idea behind the M-ASG algorithm (which allows it to achieve the lower bounds) is to exploit this trade-off to decide on the right time, $n_{1}$, to switch to decaying stepsizes, i.e., when the bias term is sufficiently small so that the variance term dominates and should be handled with the decaying stepsize. This insight is visible from the results of Theorem 3.4 which gives further insights on the choice of the stepsize at every stage to achieve the lower bounds. Theorem 3.4 shows that if M-ASG is run with a constant stepsize $\alpha_{1}=\frac{1}{L}$ in the first stage, then the variance term admits the bound $\frac{\sigma^{2}\sqrt{\kappa}}{L}$ which does not decay with the number of iterations $n_{1}$ in the first stage. However, in later stages, when $n>n_{1}$, the stepsize $\alpha_{k}$ is decreased as the number of iterations grows and this results in a decay of the variance term. Overall, the choice of the length of the first stage $n_{1}$, has a major impact in practice which we will highlight in our numerical experiments.

This result allows one to fine-tune the switching point to start using the decaying stepsizes within our framework as a function of $\sigma^{2}$ and $\Delta$. In scenarios, when the noise level $\sigma$ is small or the initial gap $\Delta$ is large, $n_{1}$ is chosen large enough to guarantee a fast decay in the bias term. We would like to emphasize that this modified M-ASG algorithm only requires the knowledge of $\sigma$ and $\Delta$ for selecting $n_{1}$ and the rest of the parameters can be chosen as in Theorem 3.4 which are independent of both $\sigma$ and $\Delta$. Finally, the following theorem provides theoretical guarantees of our framework for this choice of $n_{1}$. The proof is omitted as it is similar to the proofs of Theorems 3.4 and 3.6.

Numerical experiments

In this section, we demonstrate the numerical performance of Algorithm 1 with parameters specified by Corollary 3.7 (M-ASG) and Theorem 4.1 (M-ASG∗) and compare with other methods from the literature. In our first experiment, we consider the strongly convex quadratic objective $f(x)=\frac{1}{2}x^{\top}Qx-bx+\lambda\|x\|^{2}$ where $Q$ is the Laplacian of a cycle graphAll diagonal entries of $Q$ are 2, $Q_{i,j}=-1$ if $|i-j|\equiv 1\pmod{d}$, and the remaining entries are zero., $b$ is a random vector and $\lambda=0.01$ is a regularization parameter. We assume the gradients $\nabla f(x)$ are corrupted by additive noise with a Gaussian distribution $\mathcal{N}(0,\sigma_{n}^{2})$ where $\sigma_{n}^{2}\in\{10^{-6},10^{-4},10^{-2}\}$. We note that this example has been previously considered in the literature as a problem instance where Standard ASG (ASG iterations with standard choice of parameters $\alpha=\frac{1}{L}$ and $\beta=\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}$) perform badly compared to Standard GD (Gradient Descent with standard choice of the stepsize $\alpha=1/L$) . In Figures 1 and 2, we compare M-ASG and M-ASG∗ with Standard GD, Standard AG, $\mu$AGD+ , and Multistage AC-SA . We consider dimension $d=100$ and initialize all the methods from $x_{0}^{0}=0$. We run the algorithms Multistage AC-SA, and M-ASG∗, having access to the same estimate of $\Delta$. Figures 1- 2 show the average performance of all the algorithms along with the $95\%$ confidence interval over 50 sample runs while the total number of iterations $n=1000$ and $n=10000$ respectively as the noise level $\sigma^{2}$ is varied. The simulation results reveal that both M-ASG and M-ASG∗ have typically a faster decay of the error in the beginning and outperforms the other algorithms in general when the number of iterations is small to moderate. In this case, the speed-up obtained by M-ASG and M-ASG∗ is more prominent if the noise level $\sigma^{2}$ is smaller. However, as the number of iterations grows, the performance of the algorithms become similar as the variance term dominates. In addition, we would like to highlight that when the noise is small, using $n_{1}$ as suggested in (21), M-ASG∗ runs stage one longer than M-ASG; hence, enjoys the linear rate of decay for more iterations before the variance term becomes the dominant term.

For the second set of experiments, we consider a regularized logistic regression problem for binary classification. In particular, we read $10000$ images from the M-NIST data-set, and our goal is to distinguish the image of digit zero from that of digit eight.We provide an experiment with synthetic data for logistic loss in Appendix N. The number of samples is $N=1945$, and the size of each image is 20 by 20 after removing the margins (hence $d=400$ after vectorizing the images). At each iteration, we randomly choose a batch size $b$ of images to compute an estimate of the gradient.This is an unbiased estimate of the gradient with finite but unknown variance, and therefore we do not use M-ASG∗ or other algorithms that need the knowledge of variance. We choose the regularization parameter equal to $\frac{1}{\sqrt{N}}$ following the standard practice (see e.g. ). In Figure 3,we compare M-ASG with Standard GD, Standard AG, $\mu$AGD+ , and AC-SA for $b\in\{50,100,500\}$. The batch size controls the noise level, with larger batches leading to smaller $\sigma$. We run each of these algorithms for 50 times, and plot their average performance and $95\%$ confidence intervals. It can be seen that M-ASG usually start faster, and achieves the asymptotic rate of other algorithms for all different batch sizes.

Conclusion

In this work, we consider strongly convex smooth optimization problems where we have access to noisy estimates of the gradients. We proposed a multistage method that adapts the choice of the parameters of the Nesterov’s accelerated gradient at each stage to achieve the optimal rate. Our method is universal in the sense that it does not require the knowledge of the noise characteristics to operate and can achieve the optimal rate both in the deterministic and stochastic settings. We provided numerical experiments that compare our method with existing approaches in the literature, illustrating that our method performs well in practice.

The work of Necdet Serhat Aybat is partially supported by NSF Grant CMMI-1635106. Alireza Fallah is partially supported by Siebel Scholarship. Mert Gürbüzbalaban acknowledges support from the grants NSF DMS-1723085 and NSF CCF-1814888.

References

Appendix A Proof of Lemma 2.1

Let us denote the asymptotic convergence rate of the ASG method as a function of $\alpha$ and $\beta$ by $\rho(\alpha,\beta)$. It is well-known that $\rho(\alpha,\beta)$ has the following characterization (see e.g. , ):

where $\lambda\in\{\mu,L\}$ and $\rho_{\lambda}$ is defined as:

with $\Delta_{\lambda}=(1+\beta)^{2}(1-\alpha\lambda)^{2}-4\beta(1-\alpha\lambda)$. Note that, since $\alpha\leq\frac{1}{L}$, we have $1-\alpha\lambda\geq 0$ for $\lambda\in\{\mu,L\}$; therefore, $\Delta_{\lambda}\geq 0$ if and only if $(1+\beta)^{2}(1-\alpha\lambda)\geq 4\beta$, which is equivalent to $\frac{1-\sqrt{\alpha\lambda}}{1+\sqrt{\alpha\lambda}}\geq\beta$.

Using the fact that $\mu\leq L$ and $\frac{1-\sqrt{\alpha\lambda}}{1+\sqrt{\alpha\lambda}}$ is decreasing in $\lambda>0$, we obtain $\frac{1-\sqrt{\alpha\mu}}{1+\sqrt{\alpha\mu}}\geq\frac{1-\sqrt{\alpha L}}{1+\sqrt{\alpha L}}$; hence, for $\beta>\frac{1-\sqrt{\alpha\mu}}{1+\sqrt{\alpha\mu}}$, we have both $\Delta_{\mu}<0$ and $\Delta_{L}<0$. As a consequence, (22) implies that for $\beta>\frac{1-\sqrt{\alpha\mu}}{1+\sqrt{\alpha\mu}}$, we have

Moreover, for $\beta=\frac{1-\sqrt{\alpha\mu}}{1+\sqrt{\alpha\mu}}$, the two branches in (23) take the same value for $\lambda=\mu$ and $\alpha\in(0,1/L]$; therefore, when $\beta$ is set to this critical value, we also get $\rho(\alpha,\beta)=\sqrt{\beta(1-\alpha\mu)}$ for $\alpha\in(0,1/L]$. Note (24) is an increasing function of $\beta$ for any $\alpha\in(0,1/L]$; thus, given $\alpha\in(0,1/L]$, the smallest rate possible is equal to $\inf\{\rho(\alpha,\beta):\ \beta\geq\frac{1-\sqrt{\alpha\mu}}{1+\sqrt{\alpha\mu}}\}=1-\sqrt{\alpha\mu}$, which is the rate given in the statement of the lemma and it is achieved by $\beta=\frac{1-\sqrt{\alpha\mu}}{1+\sqrt{\alpha\mu}}$.

Now, we consider the case $\beta\leq\frac{1-\sqrt{\alpha\mu}}{1+\sqrt{\alpha\mu}}$. From (22), if $\rho_{\mu}(\alpha,\beta)\geq 1-\sqrt{\alpha\mu}$, then we also have $\rho(\alpha,\beta)\geq 1-\sqrt{\alpha\mu}$. Thus, showing $\rho_{\mu}(\alpha,\beta)\geq 1-\sqrt{\alpha\mu}$ suffices us to claim that for any $\alpha\in(0,1/L]$, the best possible rate is $1-\sqrt{\alpha\mu}$ and this can be achieved by setting $\beta=\frac{1-\sqrt{\alpha\mu}}{1+\sqrt{\alpha\mu}}$. Indeed, as we discussed above, for the case $\beta\leq\frac{1-\sqrt{\alpha\mu}}{1+\sqrt{\alpha\mu}}$, we have $\Delta_{\mu}\geq 0$; thus,

Therefore, to show $\rho_{\mu}(\alpha,\beta)\geq 1-\sqrt{\alpha\mu}$, we just need to prove

Taking the square of both sides of (25), it follows that (25) is equivalent to

and this holds when $\beta\leq\frac{1-\sqrt{\alpha\mu}}{1+\sqrt{\alpha\mu}}$. Therefore, for any $\alpha\in(0,1/L]$, we have $\rho_{\mu}(\alpha,\beta)\geq 1-\sqrt{\alpha\mu}$ for $\beta\leq\frac{1-\sqrt{\alpha\mu}}{1+\sqrt{\alpha\mu}}$. which completes the proof.

Appendix B Proof of Lemma 2.2

We first state the following lemma which is an extension of Lemma 4.1 in for ASG.

Similarly, by extending Lemma 4.5 in to the noise setting (3), for every $k\geq 0$ we obtain

Appendix C Proof of Theorem 2.3

$\begin{aligned} \Gamma_{3,3}&=\frac{\alpha(1-L\alpha)}{2},\end{aligned}$

\begin{aligned} \Gamma_{2,2}&=\frac{\mu\sqrt{\mu\alpha}(1-\sqrt{\mu\alpha})^{2}}{2(1+\sqrt{\mu\alpha})^{2}}+\frac{\mu(1-\sqrt{\mu\alpha})^{3}}{2(1+\sqrt{\mu\alpha})^{2}}-\frac{(1-\sqrt{\mu\alpha})^{2}}{2\alpha(1+\sqrt{\mu\alpha})^{2}}+\frac{(1-\sqrt{\mu\alpha})^{3}}{2\alpha}\\ &=\frac{(1-\sqrt{\mu\alpha})^{2}}{2\alpha(1+\sqrt{\mu\alpha})^{2}}\bigg{(}\alpha\Big{(}\mu\sqrt{\mu\alpha}+\mu(1-\sqrt{\mu\alpha})\Big{)}-1+(1-\sqrt{\mu\alpha})(1+\sqrt{\mu\alpha})^{2}\bigg{)}\\ &=\frac{(1-\sqrt{\alpha\mu})^{3}\sqrt{\mu}}{2\sqrt{\alpha}(1+\sqrt{\alpha\mu})}\geq 0\\ \end{aligned}

which is positive semidefinite. Now, consider the case that $\alpha<\frac{1}{L}$. For any $\epsilon>0$, let

Note that, for any $\epsilon>0$, (i) implies $\Gamma_{3,3}^{\epsilon}>0$. This fact, along with (ii) and (iii), indicates that $\det(\Gamma_{[2:3],[2:3]}^{\epsilon})>0$. Hence,

where the second equality comes from (iv). Therefore, the determinant of $\Gamma^{\epsilon}$, itself, and two submatrices $\Gamma_{3,3}^{\epsilon}$ and $\Gamma_{[2:3],[2:3]}^{\epsilon}$ are all positive. Thus, by Sylvester’s criterion, $\Gamma^{\epsilon}$ is positive definite for any $\epsilon>0$. As a consequence, since $\Gamma=\lim_{\epsilon\to 0}\Gamma^{\epsilon}$, $\Gamma$ is positive semidefinite.

Appendix D Proof of Theorem 3.1

Using Theorem 2.3, for every $k\geq 1$, we have

where in the last inequality we used the fact that $c^{2}\leq 1$. Using this bound recursively for $n$ times, we obtain

where the second inequality follows from the inequality that $1-t\leq\exp(-t)$ for every $t\geq 0$, and the third inequality is obtained by replacing $1-(1-\frac{c}{\sqrt{\kappa}})^{n}$ by $1$.

Appendix E Proof of Corollary 3.2

We first show $\alpha_{1}\leq\frac{1}{L}$. Note that, by assumption, $n$ can be written as $p\sqrt{\kappa}n_{0}$ where $n_{0}\geq 2\log(p\sqrt{\kappa})$ and $n_{0}\geq e$. This assumption, along with the fact that $\frac{\log n}{n}$ is a decreasing function of $n$ as $n\geq e$, implies

where in (31) we used the assumption $n_{0}\geq 2\log(p\sqrt{\kappa})$, and (32) follows from the fact that $n_{0}\geq e$, and therefore, $\tfrac{\log n_{0}}{n_{0}}\leq 1/e\leq 1/2$.

Next, using Theorem 3.1 with $c=\frac{p\sqrt{\kappa}\log n}{n}$ immediately gives the desired bound.

Appendix F Proof of Lemma 3.3

First, note that $\xi_{1}^{k+1}=\left[{x_{n_{k}+1}^{k}}^{\top},{x_{n_{k}+1}^{k}}^{\top}\right]^{\top}$, and therefore,

Plugging (33) into (10) for $V_{P_{\alpha_{k+1}}}(\xi_{1}^{k+1})$ yields

where (34) follows from (2) with $x=x_{n_{k}+1}^{k}$ and $y=x^{*}$. Finally, taking expectation from (35) completes the proof.

Appendix G Proof of Theorem 3.4

which implies (17) as $V_{P_{\alpha_{k}}}(\xi_{n_{k}+1}^{k})\geq f(x_{n_{k}+1}^{k})-f^{*}$. We show (36) by induction on $k$. For $k=1$, using Theorem 3.1, we obtain

where the second inequality comes from the inequality $V_{P_{\alpha_{1}}}(\xi_{1})\leq 2(f(x_{0}^{0})-f^{*})$ which can be derived similar to (34).

Next, we assume (36) holds for $k$ and show it also holds for $k+1$. Note that

where, (38) and (39) are obtained by using Theorem 3.1 and Lemma 3.3, respectively, and in (40) we used the assumption that (36) holds for $k$.

Appendix H Proof of Theorem 3.6

First, we will show that for every $k\geq 1$ and $0\leq m\leq n_{k}+1$, we have

where, (43) and (44) follows again from Theorem 3.1 and Lemma 3.3, and we obtain (45) using (36).

Recall the definition $N_{K}(p,n_{1})\triangleq\sum_{k=1}^{K}n_{k}$ which denotes the total number of stochastic gradient iterations required to complete $K$ stages of M-ASG for parameter $p$ and first-stage iteration number $n_{1}$ fixed. Given the computational budget of $n$ iterations such that $n\geq n_{1}$, let $K$ be the largest number such that $n\geq N_{K}\triangleq N_{K}(p,n_{1})$. As a result, at iteration $n$ we are in stage $K+1$. Note that (18) implies $2^{K-1}\geq\tfrac{N_{K}-n_{1}+\Psi}{\Psi}$ with $\Psi=4\lceil(p+2)\sqrt{\kappa}\log(2)\rceil$; therefore

Thus, we get the following upper bound on the suboptimality:

and by substituting (46) in (H) we obtain the bound

Next, by (18), $N_{K+1}-n_{1}\leq 2(N_{K}-n_{1}+\Psi)$, and thus, $n-n_{1}\leq 2(N_{K}-n_{1}+\Psi)$. Replacing $\frac{1}{N_{K}-n_{1}+\Psi}$ by $\frac{2}{n-n_{1}}$ in (H) completes the proof of (19).

Appendix I Proof of Corollary 3.7

Note that by setting $n_{1}=\lceil(p+1)\sqrt{\kappa}\log\left(12(p+1)\kappa\right)\rceil$, we have $\exp(-n_{1}/\sqrt{\kappa})\leq\frac{1}{\left(16\log(2)(p+1)\sqrt{\kappa}\right)^{p+1}}$; hence, plugging $n_{1}=\lceil(p+1)\sqrt{\kappa}\log\left(12(p+1)\kappa\right)\rceil$ in (19) implies the following bound with an $\mathcal{O}(1)$ constant that does not depend on $\mu$, $L$ and $x_{0}^{0}$:

Finally, note that $n\geq 2n_{1}$; therefore, $n-n_{1}\geq n/2$ and using it in (49) completes the proof.

Appendix J Proof of Corrolary 3.9

By plugging $p=1$ and $n_{1}=\lceil\sqrt{\kappa}\log\left(\frac{4\Delta}{\epsilon}\right)\rceil$ in (17), it is straightforward to check the bias term is bounded by $\tfrac{\epsilon}{2}$. Next, consider running M-ASG with given parameters, possibly without knowing and/or specifying the exact number of stages. Consider the end of the $K$-th stage, where $K\triangleq\lceil\log_{2}(\frac{\sigma^{2}\sqrt{\kappa}}{L\epsilon})\rceil+2$. Since $\frac{1}{2^{K-1}}\leq\frac{L\epsilon}{2\sigma^{2}\sqrt{\kappa}}$, the variance term in (17) is also bounded by $\tfrac{\epsilon}{2}$, and as a result $x_{n_{K}+1}^{K}$ is an $\epsilon-$solution.

Now, by using (18), we can bound the number of iterations for completing $K$ stages:

where in (50) we used the fact that $\lceil\sqrt{\kappa}\log(8)\rceil\leq(1+\tfrac{1}{\log(8)})\sqrt{\kappa}\log(8)$ since $\kappa\geq 1$, and (51) follows from the bound $K\leq 3+\log_{2}(\frac{\sigma^{2}\sqrt{\kappa}}{L\epsilon})$.

Appendix K Results for More General Noise Setting

where $w$ is a random variable independent of previous iterates.

In what follows, we first show how the results of Theorem 2.3 and Lemma 3.3 extends to this setting, and then briefly discuss the results of our multistage scheme for this noise setting.

First, note that similar to the proof of Lemma 2.2 and by using $\alpha L\leq 1$, we can show

Using $y_{k}=C\xi_{k}$, we can substitute $\|y_{k}-x^{*}\|^{2}$ by $(\xi_{k}-\xi^{*})^{\top}C^{\top}C(\xi_{k}-\xi^{*})$ in (55); hence,

where the last inequality follows from $1-\sqrt{\alpha\mu}\geq 1/2$ which is true since \alpha\leq{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}1/L} and $\kappa\geq 4$. Also note that

where (57) follows from $(a+b)^{2}\leq 2a^{2}+2b^{2}$ and (58) follows from $\beta\leq 1$ and the strong convexity assumption, i.e., f(x)-f^{*}\geq{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\frac{\mu}{2}}\|x-x^{*}\|^{2}. Finally, (59) is obtained using $\min\{{V_{P_{\alpha}}(\xi_{k}),~{}V_{Q_{\alpha}}(\xi_{k})\}\geq f(x_{k})-f^{*}}$. Plugging (59) into the definition of $V_{Q_{\alpha}}(\xi_{k+1})$ implies

where the last inequality follows from the assumption $\alpha\leq\frac{\mu^{3}}{(60\eta^{2})^{2}}$ which implies

Finally, note that, (62) along with $\alpha\leq 1/L$ also implies $1\geq 60\alpha\eta^{2}/\mu$; thus, we can bound $1+{32\alpha\eta^{2}}/{\mu}$ in (61) by $2$ which gives us the desired result. ∎

The proof is very similar to the arguments in Appendix F. In particular,

where (64) follows from (2) with $x=x_{n_{k}+1}^{k}$ and $y=x^{*}$. Finally, (65) follows from $1/60\geq\alpha\eta^{2}/\mu$, which holds due to (62) and $\alpha\leq\frac{1}{L}$, along with {\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}V_{Q_{\alpha_{k}}}}(\xi_{n_{k}+1}^{k})\geq f(x_{n_{k}+1}^{k})-f^{*}. Taking expectations of both sides of (65) completes the proof. ∎

Using the results in Theorem K.1 and Lemma K.2, we can analyze M-ASG for this more general noise setting in (52) as well and extend our complexity result in Corollary 3.8 as follows:

for $n$ sufficiently large and known in advance. It is worth noting that we can also derive similar results to Theorems 3.4 and 3.6 when $n$ is not known. We skip the details as all the arguments follow very similar to our analysis in Section 3.

Appendix L M-ASG for Convex Objective Functions

The author of obtains this lower bound for the case of compact domain with the additional knowledge of noise parameter $\sigma$. For unconstrained optimization, and without using the information on the noise parameter, $\sigma^{2}$, it is shown in that one can achieve the rate $\mathcal{O}(\frac{1}{\sqrt{n}})$ in both bias and variance terms (see last part of Corollary 3.9 and also Corollary 4.1 in ). As we state below, a direct application of our current results recovers a similar result up to a log factor.

Now, using the fact that $x_{0}=x_{-1}$, and similar to the proof of Lemma 3.3, we can show

Therefore, plugging this into (68), we obtain

This result along with $f(x_{n+1})\leq f_{\lambda}(x_{n+1})$ implies

Appendix M AC-SA from the perspective of Nesterov’s Accelerated Method

Recall that AC-SA with initial point $x_{0}$ and sequence of stepsize parameters $\{\eta_{t}\}_{t\geq 1}$ and $\{\gamma_{t}\}_{t\geq 1}$ has the following update rule:

Set $x_{t}^{md}=\frac{(1-\eta_{t})(\mu+\gamma_{t})x_{t-1}^{ag}+\eta_{t}[(1-\eta_{t})\mu+\gamma_{t}]x_{t-1}}{\gamma_{t}+(1-\eta_{t}^{2})\mu};$

Set $x_{t}^{ag}=\eta_{t}x_{t}+(1-\eta_{t})x_{t-1}^{ag}$;

Set $t\leftarrow t+1$ and go to step (ii).

We claim that this algorithm can be cast as an ASG method in (7) with a specific varying stepsize rule. In fact, we show it can be represented as

To show this, first, multiplying both sides of ((ii)) by $\frac{\gamma_{t}+(1-\eta_{t}^{2})\mu}{\mu+\gamma_{t}}$ implies

and by substituting $(1-\eta_{t})x_{t-1}^{ag}$ by $x_{t}^{ag}-\eta_{t}x_{t}$ from ((iv)) we obtain

To show (72a), first note that by ((iv)) for $t-1$, we obtain $x_{t-1}=\frac{1}{\eta_{t-1}}(x_{t-1}^{ag}-(1-\eta_{t-1})x_{t-2}^{ag})$. Plugging in this in ((ii)), leads to

which is (72a) and the proof is complete.

As a consequence, Multistage AC-SA is a variant of M-ASG Algorithm that has a different length $n_{k}$ for each stage $k\geq 1$ and employs a specific varying stepsize rule together with a different selection for the momentum parameter at each stage.

Appendix N Additional Numerical Experiments