SGD: General Analysis and Improved Rates

Introduction

Stochastic gradient descent (SGD) Robbins & Monro (1951); Nemirovski & Yudin (1978; 1983); Shalev-Shwartz et al. (2007); Nemirovski et al. (2009); Hardt et al. (2016), has become the workhorse for training supervised machine learning problems which have the generic form (1).

Linear convergence of SGD. Moulines & Bach (2011) provided a non-asymptotic analyses of SGD showing linear convergence for strongly convex $f$ up to a certain noise level. Needell et al. (2016) improved upon these results by removing the quadratic dependency on the condition number in the iteration complexity results, and considered importance sampling. The analysis of Needell et al. (2016) was later extended to a mini-batch variant where the mini-batches are formed by partitioning the data Needell & Ward (2017). These works are the main starting point for ours.

Contributions: We further tighten and generalize these results to virtually all forms of sampling. We introduce an expected smoothness assumption (Assumption 2.1), first introduced in Gower et al. (2018) in the context of a certain class of variance-reduced methods. This assumption is a joint property of $f$ and the sampling scheme ${\cal D}$ utilized by an SGD method, and allows us prove a generic complexity result (Theorem 3.1) that holds for arbitrary sampling schemes ${\cal D}$. Our work is the first time SGD is analysed under this assumption. We obtain linear convergence rates without strong convexity; in particular, assuming strong quasi-convexity (this class includes some non-convex functions as well). Furthermore, we do not require the functions $f_{i}$ to be convex.

Contributions: Our analysis does not directly assume a growth condition. Instead, we make use of the remarkably weak expected smoothness assumption.

Optimal mini-batch size. Recently it was experimentally shown by Goyal et al. (2017) that using larger mini-batches sizes is key to efficient training of large scale non-convex problems, leading to the training of ImageNet in under 1 hour. The authors conjectured that the stepsize should grow linearly with the mini-batch size.

Contributions: We prove (see Section 4) that this is the case, upto a certain optimal mini-batch size, and provide exact formulas for the dependency of the stepsizes on the mini-batch sizes.

Learning schedules. Chee & Toulis (2018) develop techniques for detecting the convergence of SGD within a region around the solution.

Contributions: We provide a closed-form formula for when should SGD switch from a constant stepsize to a decreasing stepsize (see Theorem 3.2). Further, we clearly show how the optimal stepsize (learning rate) increases and the iteration complexity decreases as the mini-batch size increases for both independent sampling and sampling with replacement. We also recover the well known $L/\mu\log(1/\epsilon)$ convergence rate of gradient descent (GD) when the mini-batch size is $n$; this is the first time a generic SGD analysis recovers the correct rate of GD.

Over-parameterized models. There has been some recent work in analysing SGD in the setting where the underlying model being trained has more parameters than there is data available. In this zero–noise setting, Ma et al. (2018) showed that SGD converges linearly.

Contributions: In the case of over-parametrized models, we extend the findings of Ma et al. (2018)Recently, the results of Ma et al. (2018) were extended to the accelerated case by Vaswani et al. (2018); however, we do not study accelerated methods in this work. to independent sampling and sampling with replacement by showing that the optimal mini-batch size is $1$. Moreover, we provide results in the more general setting where the model is not necessarily over-parametrized.

Practical performance. We corroborate our theoretical results with extensive experimental testing.

2 Stochastic reformulation

In this work we provide a single theorem through which we can analyse all importance sampling and mini-batch variants of SGD. To do this, we need to introduce a sampling vector which we will use to re-write our problem (1).

With each distribution ${\cal D}$ we now introduce a stochastic reformulation of (1) as follows

By the definition of the sampling vector, $f_{v}(x)$ and $\nabla f_{v}(x)$ are unbiased estimators of $f(x)$ and $\nabla f(x),$ respectively, and hence probem (4) is indeed equivalent (i.e., a reformulation) of the original problem (1). In the case of the gradient, for instance, we get

Similar but different stochastic reformulations were recently proposed by Richtárik & Takáč (2017) and further used in (Loizou & Richtárik, 2017; 2019) for the more special problem of solving linear systems, and by Gower et al. (2018) in the context of variance-reduced methods. Reformulation (4) can be solved using SGD in a natural way:

where $v^{k}\sim{\cal D}$ is sampled i.i.d. at each iteration and $\gamma^{k}>0$ is a stepsize. However, for different distributions ${\cal D}$, (6) has a different interpretation as an SGD method for solving the original problem (1). In our main result we will analyse (6) for any ${\cal D}$ satisfying (3). By substituting specific choices of ${\cal D}$, we obtain specific variants of SGD for solving (1).

Expected Smoothness and Gradient Noise

In our analysis of SGD (6) applied to the stochastic reformulation (4) we rely on a generic and remarkably weak assumption of expected smoothness, which we now define and relate to existing growth conditions.

Expected smoothness Gower et al. (2018) is an assumption that combines both the properties of the distribution ${\cal D}$ and the smoothness properties of function $f$.

We say that $f$ is ${\cal L}$–smooth in expectation with respect to distribution ${\cal D}$ if there exists ${\cal L}={\cal L}(f,{\cal D})>0$ such that

There are scenarios where the above inequality is tight. Indeed, in the setting of stochastic reformulations of linear systems considered in Richtárik & Takáč (2017), one has $f_{v}(x)=\frac{1}{2}\|\nabla f_{v}(x)\|^{2}$, $\nabla f_{v}(x^{*})=0$ and $f_{v}(x^{*})=0$, which means that (7) holds as an identity with ${\cal L}=1$.

In Section 3.3 we show how convexity and $L_{i}$–smoothness of $f_{i}$ implies expected smoothness. However, the opposite implication does not hold. Indeed, the expected smoothness assumption can hold even when the $f_{i}$’s and $f$ are not convex, as we show in the next example.

where the last inequality follows from Proposition A.1. So, $(f,{\cal D})\sim ES({\cal L})$ for ${\cal L}=\frac{\theta L_{\phi}}{n^{2}}$.

2 Gradient noise

Our second key assumption is finiteness of gradient noise, defined next:

The gradient noise $\sigma=\sigma(f,{\cal D})$, defined by

3 Key lemma and connection to the weak growth condition

When the gradient noise is zero ($\sigma=0$), inequality (9) is known as the weak growth condition Vaswani et al. (2018). We have the following corollary:

If $(f,{\cal D})\sim ES({\cal L})$ and if $\sigma=0$, then $f$ satisfies the weak growth condition

This corollary should be contrasted with Proposition 2 in Vaswani et al. (2018) and Lemma 1 in Nguyen et al. (2018), where it is shown, by assuming the $f_{i}$ functions to be smooth and convex, that the weak growth condition holds with $\rho=2L_{\max}$. However, as we will show in Lemma E.1, $L_{\max}\geq{\cal L}$, and hence our bound is often tighter.

Convergence Analysis

We now present our main theorem, and include its proof to highlight how we make use of expected smoothness and gradient noise.

Assume $f$ is $\mu$-quasi-strongly convex and that $(f,{\cal D})\sim ES({\cal L})$. Choose $\gamma^{k}=\gamma\in(0,\frac{1}{2{\cal L}}]$ for all $k$. Then iterates of SGD given by (6) satisfy:

Hence, given any $\epsilon>0$, choosing stepsize

Let $r^{k}=x^{k}-x^{*}$. From (6), we have

Taking expectation conditioned on $x^{k}$ we obtain:

Taking expectations again and using Lemma 2.4:

where we used in the last inequality that $2\gamma{\cal L}\leq 1$ since $\gamma\leq\frac{1}{2{\cal L}}.$ Recursively applying the above and summing up the resulting geometric series gives

To obtain an iteration complexity result from the above, we use standard techniques as shown in Section A.1. ∎

Note that we do not assume $f_{i}$ nor $f$ to be convex. Theorem 3.1 states that SGD converges linearly up to the additive constant $2\gamma\sigma^{2}/\mu$ which depends on the gradient noise $\sigma^{2}$ and on the stepsize $\gamma$. We obtain a more accurate solution with a smaller stepsize, but then the convergence rate slows down. Since we control ${\cal D}$, we also control $\sigma^{2}$ and ${\cal L}$ (we compute these parameters for several distributions ${\cal D}$ in Section 3.3).

Furthermore, we can control this additive constant by carefully choosing the stepsize, as shown in the next result.

Assume $f$ is $\mu$-quasi-strongly convex and that $(f,{\cal D})\sim ES({\cal L})$. Let $\mathcal{K}:=\left.{\cal L}\right/\mu$ and

If $k\geq 4\lceil\mathcal{K}\rceil$, then SGD iterates given by (6) satisfy:

2 Choosing 𝒟𝒟{\cal D}

For (6) to be efficient, the sampling vector $v$ should be sparse. For this reason we will construct $v$ so that only a (small and random) subset of its entries are non-zero.

The first analysis of a randomized optimization method with an arbitrary (proper) sampling was performed by Richtárik & Takáč (2016) in the context of randomized coordinate descent for strongly convex functions. This arbitrary sampling paradigm was later adopted in many other settings, including accelerated coordinate descent for strongly convex functions Hanzely & Richtárik (2018), coordinate and accelerated descent for convex functions Qu & Richtárik (2016), primal-dual methods Qu et al. (2015); Chambolle et al. (2018), variance-reduced methods with convex Csiba & Richtárik (2015) and nonconvex Horváth & Richtárik (2018) objectives. Arbitrary sampling arises as a special case of our more general analysis by specializing the sampling vector to one dependent on a sampling $S$. We now define practical sampling vector $v=v(S)$ as follows:

Let $S$ be a proper sampling, and let ${\hat{\bf P}}={\rm Diag}(p_{1},...,p_{n}).$ Then the random vector $v=v(S)$ given by

We can further specialize and define the following commonly used samplings. Each sampling $S$ gives rise to a particular sampling vector $v=v(S)$ (i.e., distribution ${\cal D}$), which in turn gives rise to a particular stochastic reformulation (4) and SGD variant (6).

Independent sampling. The sampling $S$ includes every $i$, independently, with probability $p_{i}>0$. This type of sampling was considered in different contexts in Horváth & Richtárik (2018); Hanzely & Richtárik (2018).

By assuming that the $f_{i}$ functions are convex and smooth we can calculate closed form expressions for the expected smoothness ${\cal L}$ and gradient noise $\sigma^{2}$. In particular we make the following smoothness assumption:

To better relate the above assumption to the standard smoothness assumptions we make the following remark.

As a consequence of Assumption 3.4 we also have that each $f_{i}$ is $L_{i}:=\lambda_{\max}({\bf M}_{i})$–smooth and $f$ is $L:=\frac{1}{n}\lambda_{\max}(\sum_{i=1}^{n}{\bf M}_{i})$–smooth. Let $L_{\max}:=\max_{i\in[n]}L_{i}.$

Using Assumption 3.4 and a sampling we establish the following bounds on ${\cal L}$.

and $L_{C}:=\frac{1}{n}\lambda_{\max}(\sum_{j\in C}\frac{1}{p_{j}}{\bf M}_{j})$. If $|S|\equiv\tau$, then

By applying the above result to specific samplings, we obtain the following practical bounds on ${\cal L}$:

(i) For single element sampling $S$, we have

(ii) For partition sampling $S$ with partition ${\cal G}$, we have

For $\tau$-nice sampling and independent sampling, we get the following very informative bounds on ${\cal L}$.

(iii) For independent sampling $S$, we have

Gazagnadou et al. (2019) were the first to suggest using (24) as an approximation for ${\cal L}$. Through extensive experiments, they showed that the bound (24) is very tight. Here we give the first proof that (24) is indeed a valid upper bound.

For $v=v(S)$ given by (17), formulas for the gradient noise $\sigma^{2}$ are provided in the next result:

Specializing the above theorem to specific samplings $S$ gives the following formulas for $\sigma^{2}$:

(i) For single element sampling $S$, we have

(iii) For $\tau$-nice sampling $S$, we have

(iv) For partition sampling $S$ with partition ${\cal G}$, we have

Generally, we do not know the values of $h_{i}=\nabla f_{i}(x^{*})$. But if we have prior knowledge that $x^{*}$ belongs to some set ${\cal C}$, we can obtain upper bounds for $\sigma^{2}$ for these samplings from Proposition 3.10 in a straightforward way.

Optimal Mini-Batch Size

Here we develop the iteration complexity for different samplings by plugging in the bounds on ${\cal L}$ and $\sigma$ given in Section 3.3 into Theorem 3.1. To keep the notation brief, in this section we drop the logarithmic term $\log\left(2\|x^{0}-x^{*}\|^{2}/\epsilon\right)$ from the iteration complexity results. Furthermore, for brevity and to better compare our results to others in the literature, we will use $L_{i}=\lambda_{\max}({\bf M}_{i})$ and $L_{\max}=\max_{i\in[n]}L_{i}$ (see Remark 3.5). Finally let $\overline{h}=\frac{1}{n}\sum_{i\in[n]}\|h_{i}\|^{2}$ for brevity.

Gradient descent. As a first sanity check, we consider the case where $|S|=n$ with probability one. That is, each iteration (6) uses the full batch gradient. Thus $\sigma=0$ and it is not hard to see that for $\tau=n$ in (24) or $p_{i}=1$ for all $i$ in (23) we have ${\cal L}_{\max}=L.$ Consequently, the resulting iteration complexity (12) is now $k\geq 2L/\mu$. This is exactly the rate of gradient descent, which is precisely what we would expect since the resulting method is gradient descent. Though an obvious sanity check, we believe this is the first convergence theorem of SGD that includes gradient descent as a special case. Clearly, this is a necessary pre-requisite if we are to hope to understand the complexity of mini-batching.

To better appreciate how our iteration complexity evolves with increased mini-batch sizes, we now consider independent sampling with $|S|=\tau$ and $\tau$-nice sampling.

Independent sampling. Inserting the bound on ${\cal L}$ (23) and $\sigma$ (27) into (12) gives the following iteration complexity

This is a completely new mini-batch complexity result, which opens up the possibility of optimizing the mini-batch size and probabilities of sampling. For instance, if we fix uniform probabilities with $p_{i}=\frac{\tau}{n}$ then (30) becomes $k\geq\frac{2}{\mu}\max\left\{l(\tau),r(\tau)\right\}$, where

This complexity result corresponds to using the stepsize

if $\tau<n$, otherwise only the left-hand-side term in the minimization remains. The stepsize (32) is increasing since both $l(\tau)$ and $r(\tau)$ decrease as $\tau$ increases.

With such a simple expression for the iteration complexity we can choose a mini-batch size that optimizes the total complexity. By defining the total complexity $T(\tau)$ as the number of iterations $k$ times the number of gradient evaluations ($\tau$) per iteration gives

Minimizing $T(\tau)$ in $\tau$ is easy because $T(\tau)$ is a max of a linearly increasing term $\tau\times l(\tau)$ and a linearly decreasing term $\tau\times r(\tau)$ in $\tau$. Furthermore $n\times l(n)\geq 0=n\times r(n)$. Consequently, if $l(1)\geq r(1)$, then $\tau^{*}=1$, otherwise

Since $r(1)$ is proportional to the noise and $1/\epsilon$ and $l(1)$ is proportional to the smoothness constants the condition $l(1)\leq r(1)$ holds when there is comparatively a lot of noise or the precision is high. As we will see in Section 4.2 this logic extends to the case where the noise is zero, where the optimal mini-batch size is $\tau^{*}=1.$

$\tau$–nice sampling. Inserting the bound on ${\cal L}$ (24) and $\sigma$ (28) into (12) gives the iteration complexity $k\geq\frac{2}{\mu}\max\{l(\tau),r(\tau)\}$, where

Again, this is an increasing function in $\tau.$

We are now again able to calculate the mini-batch size that optimizes the total complexity $T(\tau)$ given by $T(\tau)=\frac{2\tau}{\mu}\max\{l(\tau),r(\tau)\}.$ Once again $T(\tau)$ is a max of a linearly increasing term $\tau\times l(\tau)$ and a linearly decreasing term $\tau\times r(\tau)$ in $\tau$. Furthermore $r(n)=0\leq l(n)$. Consequently, if $r(1)\leq l(1)$ then $\tau^{*}=1$, otherwise

2 Zero gradient noise

Consider the case where the gradient noise is zero ($\sigma=0$). According to Theorem 3.1, the resulting complexity of SGD with constant stepsize $\gamma=\frac{1}{2{\cal L}}$ is given by the very simple expression

where we have dropped the logarithmic term $\log\left(\left.\|x^{0}-x^{*}\|^{2}\right/\epsilon\right)$. In this setting, due to Corollary 2.5, we know that $f$ satisfies the weak growth condition. Thus our results are directly comparable to those developed in Ma et al. (2018) and in Vaswani et al. (2018).

In particular, Theorem 1 in Ma et al. (2018) states that when running SGD with mini-batches based on sampling with replacement, the resulting iteration complexity is

again dropping the logarithmic term. Now gaining insight into the complexity (39) is a matter of studying the expected smoothness parameter ${\cal L}$ for different sampling strategies.

Independent sampling. Setting $\sigma=0$ (thus $\overline{h}=0$) and using uniform probabilities with $p_{i}=\frac{\tau}{n}$ in (30) gives

$\tau$ –nice sampling. If we use a uniform sampling and $\sigma=0$ then the resulting iteration complexity is given by

Iteration complexities (40), (41) and (42) tell essentially the same story. Namely, the complexity improves as $\tau$ increases to $n$, but this improvement is not enough when considering the total complexity (multiplying by $\tau$). Indeed, for total complexity, these results all say that $\tau=1$ is optimal.

Importance Sampling

For single element sampling, plugging (21) and (26) into (12) gives the following iteration complexity

where $0<p_{i}\leq 1$ and $\sum_{i\in[n]}p_{i}=1$. In order to optimize this iteration complexity over $p_{i}$, we need to solve a $n$ dimensional linearly constrained nonsmooth convex minimization problem, which could be harder than the original problem (1). So instead, we will focus on minimizing ${\cal L}_{\max}$ and $\sigma^{2}$ over $p_{i}$ seperately. We will then use these two resulting (sub)optimal probabilities to construct a sampling.

In particular, for single element sampling we can recover the partially biased sampling developed in Needell et al. (2016). First, from (21) it is easy to see that the probabilities that minimize ${\cal L}_{\max}$ are $p_{i}^{\cal L}=\left.L_{i}\right/\sum_{j\in[n]}L_{j},$ for all $i$. Using these suboptimal probabilities we can construct a partially biased sampling by letting $\hat{p}_{i}:=\frac{1}{2}p_{i}^{\cal L}+\frac{1}{2n}.$ Plugging this sampling in (21) gives ${\cal L}_{\max}\leq 2\overline{L}:=\frac{2}{n}\sum_{i\in[n]}L_{i}$, and from (26), we have $\sigma^{2}\leq\frac{2}{n}\sum_{i\in[n]}\|h_{i}\|^{2}:=2\overline{h}$. This sampling is the same as the partially biased sampling in Needell et al. (2016). From (30) in Theorem 3.1, we get that the total complexity is now given by

For uniform sampling, ${\cal L}_{\max}=\max_{i\in[n]}L_{i}\geq\overline{L}$ and $\sigma^{2}=\frac{1}{n}\sum_{i\in[n]}\|h_{i}\|^{2}$. Hence, compared to uniform sampling, the iteration complexity of partially biased sampling is at most two times larger, but could be $n/2$ smaller in the extreme case where $L_{\max}=n\,\overline{L}.$

2 Minibatches

Importance sampling for minibatches was first considered in (Csiba & Richtárik, 2018); but not in the context of SGD. Here we propose the first importance sampling for minibatch SGD. In Section J.2 in the appendix we introduce the use of partially biased sampling together with independent sampling with $|S|=\tau$ and show that we can achieve a total complexity of (by Proposition J.3)

which not only eliminates the dependence on $L_{\max}$, but also improves as the mini-batch size $\tau$ increases.

Experiments

In this section, we empirically validate our theoretical results. We perform three experiments in each of which we highlight a different aspect of our contributions.

In the first two experiments we focus on ridge regression and regularized logistic regression problems (problems with strongly convex objective $f$ and components $f_{i}$) and we evaluate the performance of SGD on both synthetic and real data. In the second experiment (Section 6.2) we compare the convergence of SGD for several choices of the distribution ${\cal D}$ (different sampling strategies) as described in Section 3.2. In the last experiment (Section 6.3) we focus on the problem of principal component analysis (PCA) which by construction can be seen as a problem with a strongly convex objective $f$ but with non-convex functions $f_{i}$ Allen-Zhu & Yuan (2016); Garber & Hazan (2015); Shalev-Shwartz (2016).

In all experiments, to evaluate SGD we use the relative error measure $\frac{\|x^{k}-x^{*}\|^{2}}{\|x^{0}-x^{*}\|^{2}}$. For all implementations, the starting point $x^{0}$ is sampled from the standard Gaussian. We run each method until $\|x^{k}-x^{*}\|^{2}\leq 10^{-3}$ or until a pre-specified maximum number of epochs is achieved. For the horizontal axis we always use the number of epochs.

For more experiments we refer the interested reader to Section K of the Appendix.

Regularized Regression Problems: In the case of the ridge regression problem we solve:

while for the $L2$-regularized logistic regression problem we solve:

We now compare the performance of SGD in the constant and decreasing stepsize regimes considered in Theorems 3.1 (see (11)) and 3.2 (see (14)), respectively. Here we use a uniform single element sampling. As expected from theory, we see in Figure 1 that the decreasing stepsize regime is vastly superior at reaching a higher precision than the constant step-size variant. In our plots, the vertical red line denotes the value of $4\lceil\mathcal{\left.{\cal L}\right/\mu}\rceil$ predicted from Theorem 3.2 and highlights the point where SGD needs to change its update rule from constant to decreasing step-size.

2 Minibatches

In Figures 2 and 5 we compare the single element sampling (uniform and importance), $\tau$ independent sampling (uniform, uniform with optimal batch size and importance) and $\tau$ nice sampling (with some $\tau$ and with optimal $\tau^{*}$). The probabilities of importance samplings in the single element sampling and $\tau$ independent sampling are calculated by formulas (67) and (77) in the Appendix. Formulas for optimal minibatch size $\tau^{*}$ in independent sampling and $\tau$-nice samplings are given in (34) and (38), respectively. Observe that minibatching with optimal $\tau^{*}$ gives the best convergence. In addition, note that for constant step size, the importance sampling variants depend on the accuracy $\epsilon$. From Figure 2 we can see that before the error reaches the required accuracy, the importance sampling variants are comparable or better than their coresponding uniform sampling variants.

3 Sum-of-non-convex functions

where $D_{i},$ $i\in[n]$ are diagonal matrices satisfying $D:=D_{1}+\cdots+D_{n}=0$. In particular, to guarantee that $D=0$, we randomly select half of the matrices and assign their $j$-th diagonal value $(D_{i})_{jj}$ equal to $11$; for the other half we assign $(D_{i})_{jj}$ to be $-11$. We repeat that for all diagonal values. Note that under this construction, each $f_{i}$ is a non-convex function. Once again, in the first plot we observe that while both are equally fast in the beginning, the decreasing stepsize variant is better at reaching higher accuracy than the fixed stepsize variant. In the second plot we see, as expected, that all four minibatch versions of SGD outperform single element SGD. However, while the $\tau$-nice and $\tau$-independent samplings with $\tau=n/5$ lead to a slight improvement only, the theoretically optimal choice $\tau=\tau^{*}$ leads to a vast improvement.

Acknowledgements

RMG acknowledges the support by a public grant as part of the Investissement d’avenir project, reference ANR-11-LABX-0056-LMH, LabEx LMH, in a joint call with Gaspard Monge Program for optimization, operations research and their interactions with data sciences.

References

Appendix A Elementary Results

In this section we collect some elementary results; some of them we use repeatedly.

Lipschitz continuity of the gradient implies that

Now plugging $h=-\frac{1}{L_{\phi}}\nabla\phi(x)$ into the above inequality, we get $\frac{1}{2L_{\phi}}\|\nabla\phi(x)\|^{2}\leq\phi(x)-\phi(x+h)\leq\phi(x)-\phi(x^{*})$. It remains to note that $\nabla\phi(x^{*})=0$. ∎

In this section we summarize some elementary results which we use often in our proofs. We do not claim novelty; we but we include them for completeness and clarity.

Taking logarithms and rearranging (47) gives

Now using that $\log\left(\frac{1}{\rho}\right)\geq 1-\rho,$ for $0<\rho\leq 1$ gives (46). ∎

To analyse the iteration complexity, let $\epsilon>0$ and choosing the stepsize so that $\frac{2\gamma\sigma^{2}}{\mu}\leq\frac{1}{2}\epsilon,$ gives (11). Next we choose $k$ so that

Taking logarithms and re-arranging the above gives

Now using that $\log\left(\frac{1}{\rho}\right)\geq 1-\rho,$ for $0<\rho\leq 1$ gives

Appendix B Proof of Lemma 2.4

The first inequality follows from the estimate $\|a+b\|^{2}\leq 2\|a\|^{2}+2\|b\|^{2}$, and the second inequality follows from (7).

Appendix C Proof of Theorem 3.2

Let $\gamma_{k}:=\frac{2k+1}{(k+1)^{2}\mu}$ and let $k^{*}$ be an integer that satisfies $\gamma_{k^{*}}\leq\frac{1}{2{\cal L}}.$ In particular this holds for

Note that $\gamma_{k}$ is decreasing in $k$ and consequently $\gamma_{k}\leq\frac{1}{2{\cal L}}$ for all $k\geq k^{*}.$ This in turn guarantees that (13) holds for all $k\geq k^{*}$ with $\gamma_{k}$ in place of $\gamma$, that is

Multiplying both sides by $(k+1)^{2}$ we obtain

where the second inequality holds because $\frac{2k+1}{k+1}<2$. Rearranging and summing from $t=k^{*}\ldots k$ we obtain:

For $k\leq k^{*}$ we have that (13) holds, which combined with (53), gives

Choosing $k^{*}$ that minimizes the second line of the above gives $k^{*}=4\lceil\mathcal{K}\rceil$, which when inserted into (54) becomes

where we have used that $\left(1-\frac{1}{2x}\right)^{4x}\leq e^{-2}$ for all $x\geq 1.$

Appendix D Proof of Theorem 3.6

Since $v_{i}=v_{i}(S)=\mathbf{1}_{(i\in S)}\frac{1}{p_{i}}$. and since $f_{i}$ is ${\bf M}_{i}$-smooth, the function

We also define the following smoothness related quantities

Let $y=x^{*}$ and notice that $\nabla f(x^{*})=0$, which gives (19). We prove (20) in the following slightly more comprehensive Lemma E.1. ∎

Appendix E Bounds on the Expected Smoothness Constant ℒℒ{\cal L}

Below we establish some lower and upper bounds on the expected smoothness constant ${\cal L}={\cal L}_{\max}$. These bounds were referred to in the main paper in Section 2.3. We also make use of notation introduced in Section 3.3.

Assume that there exists $\tau\in[n]$ such that $|S|=\tau$ with probability 1. Let

Define ${\bf M}_{S}:=\frac{1}{n}\sum_{i\in S}\frac{{\bf M}_{i}}{p_{i}}$ and note that $f$ is $\frac{1}{n}\sum_{i\in[n]}{\bf M}_{i}$–smooth. Furthermore

We will now establish the inequalities in (61) starting from left to the right.

(Part III ${\cal L}_{\max}\leq L_{\max}$). Finally, since

Consequently taking the maximum over $i\in[n]$ in the above gives ${\cal L}_{\max}\leq L_{\max}.$ ∎

Appendix F Proof of Proposition 3.7

First note that by combining (19) and (D) we have that

(i) By straight forward calculation from (63) and using that each set $C$ is a singleton.

(ii) For every partition sampling we have that $p_{i}=p_{C}$ if $i\in C$, hence

Appendix G Proof of Proposition 3.8

First, since $f_{i}$ is $L_{i}$-smooth with $L_{i}=\lambda_{\max}({\bf M}_{i})$ and convex, it follows from equation (2.1.7) in Theorem 2.1.5 in Nesterov (2013) that

Now consider the case where ${\bf P}_{ij}/(p_{i}p_{j})=c_{2}$ for $i\neq j.$ Recalling that ${\bf P}_{ii}=p_{i}$ we have from the above that

Substituting $y=x^{*}$ and comparing the above to the definition of expected smoothness (7) we have that

(i) For independent sampling, we have that ${\bf P}_{ij}=p_{i}p_{j}$ for $i\neq j$, consequently $c_{2}=1.$ Thus (66) gives (23).

(ii) For $\tau$-nice sampling, we have that ${\bf P}_{ij}=\frac{\tau(\tau-1)}{n(n-1)}$ for $j\neq i$ and ${\bf P}_{ii}=p_{i}=\frac{\tau}{n}$, hence $c_{2}=\frac{n(\tau-1)}{\tau(n-1)}$ and (66) gives (24). ∎

Appendix H Proof of Theorem 3.9

Appendix I Proof of Proposition 3.10

(ii) For independent sampling $S$, ${\bf P}_{ij}=p_{i}p_{j}$ for $i\neq j$, hence,

(iii) For $\tau$-nice sampling $S$, if $\tau=1$, it is obvious. If $\tau\geq 1$, then ${\bf P}_{ij}=\frac{C_{n-2}^{\tau-2}}{C_{n}^{\tau}}$ for $i\neq j$, and $p_{i}=\frac{\tau}{n}$ for all $i$. Hence,

(iv) For partition sampling, ${\bf P}_{ij}=p_{C}$ if $i,j\in C$, and ${\bf P}_{ij}=0$ otherwise. Hence,

Appendix J Importance sampling

From (21) it is easy to see that the probabilities that minimize ${\cal L}_{\max}$ are $p_{i}^{\cal L}=\left.L_{i}\right/\sum_{j\in[n]}L_{j},$ for all $i$, and consequently ${\cal L}_{\max}=\overline{L}$. On the other hand the probabilities that minimize (26) are given by $p_{i}^{\sigma^{2}}=\left.\|h_{i}\|\right/\sum_{j\in[n]}\|h_{j}\|,$ for all $i$, with $\sigma^{2}=(\sum_{i\in[n]}\|h_{i}\|/n)^{2}:=\sigma_{opt}^{2}$.

From $p_{i}^{\cal L}$ and $p_{i}^{\sigma^{2}}$, we construct interpolated probabilities $p_{i}$ as follows:

where $\alpha\in(0,1)$. Then $0<p_{i}<1$ and from (21) we have

Similarly, from (26) we have that $\sigma^{2}\leq\frac{1}{1-\alpha}\sigma^{2}_{opt}$. Now by letting $p_{i}=p_{i}(\alpha)$, from (30) in Theorem 3.1, we get an upper bound of the right hand side of (12):

By minimizing this bound in $\alpha$ we can get

where the right hand side comes by setting $\alpha=1/2$. Notice that the minimum of the iteration complexity in (12) is not less than $\max\left\{\frac{2\overline{L}}{\mu},\frac{4\sigma^{2}_{opt}}{\epsilon\mu^{2}}\right\}$. Hence, the iteration complexity of this importance sampling(left hand side of (70)) is at most two times larger than the minimum of the iteration complexity in (12) over $p_{i}$.

J.2 Independent sampling

For the independent sampling $S$, in this section we will use the following upper bound on ${\cal L}$ given by

which follows immediatly from (23) by using that $L\leq\frac{1}{n}\sum_{i=1}^{n}L_{i}:=\overline{L}.$

Minimizing the upper bound of ${\cal L}_{\max}$ in (71) boils down to minimizing $\max_{i\in[n]}(\frac{1}{p_{i}}-1)L_{i}$, which is not easy generally. Instead, as a proxy we obtain the probabilities $p_{i}$ by solving

Let $q_{i}=\frac{L_{i}}{\sum_{j\in[n]}L_{j}}\cdot\tau$ for all $i$, and $T=\{i|q_{i}>1\}$. If $T=\emptyset$, it is easy to see $p_{i}=p_{i}^{\cal L}(\tau)=q_{i}$ solves (72). Otherwise, in order to solve (72), we can choose $p_{i}=p_{i}^{\cal L}(\tau)=1$ for $i\in T$, and $q_{i}\leq p_{i}=p_{i}^{\cal L}(\tau)\leq 1$ for $i\notin T$ such that $\sum_{i\in[n]}p_{i}^{\cal L}(\tau)=\tau$. By letting $p_{i}=p_{i}^{\cal L}(\tau)$, we have that (72) becomes

For $\sigma^{2}$, from (27), we need to solve

Let $q_{i}=\frac{\|h_{i}\|}{\sum_{j\in[n]}\|h_{j}\|}\cdot\tau$ for all $i$, and let $T=\{i|q_{i}>1\}$. If $T=\emptyset$, it is easy to see that $p_{i}=p_{i}^{\sigma^{2}}(\tau)=q_{i}$ solve (74). Otherwise, it is a little complicated to find the optimal solution. For simplicity, if $T\neq\emptyset$, we choose $p_{i}=p_{i}^{\sigma^{2}}(\tau)=1$ for $i\in T$, and $q_{i}\leq p_{i}=p_{i}^{\sigma^{2}}(\tau)\leq 1$ for $i\notin T$ such that $\sum_{i\in[n]}p_{i}^{\sigma^{2}}(\tau)=\tau$. By letting $p_{i}=p_{i}^{\sigma^{2}}(\tau)$, from (27), we have

Importance sampling.

Since by (73) we have that ${\cal L}_{\max}\leq\left(1+\frac{1}{\tau}\right)\overline{L}$ and $\sigma=\sigma^{2}_{opt}(\tau)$ are obtained by using the upper bounds in (71) and (27), and the upper bounds are nonincreasing as $p_{i}$ increases, we get the following property.

If $p_{i}\geq p_{i}^{\cal L}(\tau)$ for all $i$, then ${\cal L}_{\max}\leq(1+\frac{1}{\tau})\overline{L}$, and if $p_{i}\geq p_{i}^{\sigma^{2}}(\tau)$, then $\sigma^{2}\leq\sigma^{2}_{opt}(\tau)$.

From Proposition J.1, we can get the following result.

For $0<\alpha<1$, let $p_{i}(\alpha)$ satisfy

If $p_{i}=p_{i}(\alpha)$ where $p_{i}(\alpha)$ satisfies (75), then we have

First , we claim that $p_{i}(\alpha)$ can be constructed to satisfy (75). Since $0<p_{i}^{{\cal L}}(\alpha)\leq 1$ and $0<p_{i}^{\sigma^{2}}((1-\alpha)\tau)\leq 1$, we know

From (75), we have $p_{i}=p_{i}(\alpha)\geq p_{i}^{{\cal L}}(\alpha\tau)$. Then by Proposition J.1, we have

We also have $p_{i}(\alpha)\geq p_{i}^{\sigma^{2}}((1-\alpha)\tau)$, hence, by Proposition J.1, we get

From (12) in Theorem 3.1, by letting $p_{i}=p_{i}(\alpha)$ in Proposition J.2, we get an upper bound of the right hand side of (12):

where $a=2(\frac{\sum_{i\in[n]}\|h_{i}\|}{n})^{2}/(\epsilon\mu\overline{L})$. So suboptimal probabilities

where $\alpha$ is given in Equation (76).

Partially biased sampling.

In practice, we do not know $\|h_{i}\|$ generally. But we can use $p_{i}^{{\cal L}}(\tau)$ and the uniform probability $\frac{\tau}{n}$ to construct a new probability just as that in Proposition J.2. More specific, we have the following result.

The proof for ${\cal L}_{\max}$ is the same as Proposition J.2. For $\sigma^{2}$, from (27), since $p_{i}\geq\tau/2n$, we have

This sampling is very nice in the sense that it can maintain ${\cal L}_{\max}$ at least close to $\overline{L}$, and meanwhile, can acheive nearly linear speedup in $\sigma^{2}$ by increasing $\tau$. We can compare the upper bounds of ${\cal L}_{\max}$ and $\sigma^{2}$ for this sampling, $\tau$-nice sampling, and $\tau$-uniform independent sampling when $1<\tau={\cal O}(1)$ in the following table.

From Table 1, compared to $\tau$-nice sampling and $\tau$-uniform independent sampling, the iteration complexity of this $\tau$-partially biased independent sampling is at most two times larger, but could be about $\frac{2\tau}{n}$ smaller in some extremely case where $L_{\max}\approx n{\bar{L}}$ and $2{\cal L}/\mu$ dominates in (12).

Appendix K Additional Experiments

Here we evaluate the choice of the switching moment from a constant to a decreasing step size according to (14) from Theorem 3.2. We are using synthetic data that was generated in the same way as it had been in the Section 6 for the ridge regression problem $(n=1000,d=100)$. In particular we evaluate 4 different cases: (i) the theoretical moment of regime switch at moment $k$ as predicted from the Theorem, (ii) early switch at $0.3\times k$, (iii) late switch at $0.7\times k$ and (iv) the optimal $k$ for switch, where the optimal $k$ is obtained using one-dimensional numerical minimization of (54) as a function of $k^{*}$.

According to Figure 4, when $x^{0}$ is close to $x^{*}$, the moment of regime switch does not play a significant role in minimizing the number of iteration except for a very early switch, which actually also leads to almost the same situation in the long run. The case when $x^{0}$ is far from $x^{*}$ shows that preliminary one-dimensional optimization makes sense and allows to reduce the error at least during the early iterations.

K.2 More on minibatches

Figure 5 reports on the same experiment as that described in Section 6.2 (Figure 2) in the main body of the paper, but on ridge regression instead of logistic regression, and using different data sets. Our findings are similar, and corroborate the conclusions made in Section 6.2.

K.3 Stepsize as a function of the minibatch size

In our last experiment we calculate the stepsize $\gamma$ as a function of the minibatch size $\tau$ for $\tau$-nice sampling using equation (37). Figure 6 depicts three plots, for three synthetic data sets of sizes $(n,d)\in\{(50,5),(100,10),(500,50)\}$. We consider regularized ridge regression problems with $\lambda=1/n$. Note that the stepsize is an increasing function of $\tau$.