{'fraction_non_alphanumeric': 0.04692966304547965, 'fraction_numerical': 0.012658810532130364, 'mean_word_length': 4.0793780687397705, 'pattern_counts': {'":': 0, '<': 12, '<?xml version=': 0, '>': 23, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Random Shuffling Beats SGD after Finite Epochs

A long-standing problem in the theory of stochastic gradient descent (SGD) is to prove that its without-replacement version RandomShuffle converges faster than the usual with-replacement version. We present the first (to our knowledge) non-asymptotic solution to this problem, which shows that after a"reasonable"number of epochs RandomShuffle indeed converges faster than SGD. Specifically, we prove that under strong convexity and second-order smoothness, the sequence generated by RandomShuffle converges to the optimal solution at the rate O(1/T^2 + n^3/T^3), where n is the number of components in the objective, and T is the total number of iterations. This result shows that after a reasonable number of epochs RandomShuffle is strictly better than SGD (which converges as O(1/T)). The key step toward showing this better dependence on T is the introduction of n into the bound; and as our analysis will show, in general a dependence on n is unavoidable without further changes to the algorithm. We show that for sparse data RandomShuffle has the rate O(1/T^2), again strictly better than SGD. Furthermore, we discuss extensions to nonconvex gradient dominated functions, as well as non-strongly convex settings.


Introduction
We consider stochastic optimization methods for the finite-sum problem where each function f i : R d → R is smooth and convex, and the sum F is strongly convex. A classical approach to solving (1.1) is stochastic gradient descent (SGD). At each iteration SGD independently samples an index i uniformly from {1, . . . , n}, and uses the (stochastic) gradient ∇f i to compute its update. The stochasticity makes each iteration of SGD cheap, and the uniformly independent sampling of i makes ∇f i an unbiased estimator of the full gradient ∇F . These properties are central to SGD's effectiveness in large scale machine learning, and underlie much of its theoretical analysis (see for instance, [2,5,26,30,34]).
However, what is actually used in practice is the without replacement version of SGD, henceforth called RANDOMSHUFFLE. Specifically, at each epoch RANDOMSHUFFLE samples a random permutation of the n functions uniformly independently (some implementations shuffle the data only once at load, rather than at each epoch). Then, it iterates over these functions according to the sampled permutation and updates in a manner similar to SGD. Avoiding the use of random sampling at each iteration, RANDOMSHUFFLE can be computationally more practical [4]; furthermore, as one would expect, empirically RANDOMSHUFFLE is known to converge faster than SGD [3].
This discrepancy between theory and practice has been a long-standing problem in the theory of SGD. It has drawn renewed attention recently, with the goal of better understanding convergence of RANDOMSHUFFLE. The key difficulty is that without-replacement leads to statistically non-independent samples, which greatly complicates analysis. Two extreme case positive results are however available: Shamir [32] shows that RANDOMSHUFFLE is not much worse than usual SGD, provided the number of epochs is not too large; while Gürbüzbalaban et al. [11] show that RANDOMSHUFFLE converges faster than SGD asymptotically at the rate O( 1 T 2 ).
But it remains unclear what happens in between, after a reasonable finite number of epochs are run. This regime is the most compelling one to study, since in practice one runs neither one nor infinitely many epochs. This motivates the central question of our paper: Does RANDOMSHUFFLE converge faster than SGD after a reasonable number of epochs?
We answer this question positively in this paper; our results are more precisely summarized below.

Summary of results
We follow the common practice of reporting convergence rates depending on T , the number of calls to the (stochastic / incremental) gradient oracle. For instance, SGD converges at the rate O( 1 T ) for solving (1.1), ignoring logarithmic terms in the bound [26]. The underlying argument is to view SGD as stochastic approximation with noise [21], therefore ignoring the finite-sum structure of (1.1). Our key observation for RANDOMSHUFFLE is that one should reasonably include dependence on n into the bound (see Section 3.3). Such a compromise leads to a better dependence on T , which further shows how RANDOMSHUFFLE beats SGD after a finite number of epochs. Our main contributions are the following: Under a mild assumption on second order differentiability, and assuming strong-convexity, we establish a convergence rate of O 1 T 2 + n 3 T 3 for RANDOMSHUFFLE, where n is the number of components in (1.1), and T is the total number of iterations (Theorem 1 and 2). From the bounds we can calculate the precise number of epochs after which RANDOMSHUFFLE is strictly better than SGD.
We prove that a dependence on n is necessary for beating the SGD rate O( 1 /T ). This tradeoff precludes the possibility of proving a convergence rate of the type O 1 /T 1+δ with some δ > 0 in the general case, and justifies our choice of introducing n into the rate (Theorem 3).
Assuming a sparse data setting common in machine learning, we further improve the convergence rate of RANDOMSHUFFLE to O 1 /T 2 . This rate is strictly better than SGD, indicating RANDOMSHUFFLE's advantage in such cases (Theorem 4).
We extend our results to the non-convex function class with Polyak-Łojasiewicz condition, establishing a similar O 1 T 2 + n 3 T 3 rate for RANDOMSHUFFLE (Theorem 5). We show a class of examples where RANDOMSHUFFLE is provably faster than SGD after arbitrary number (even less than one epoch) of iterations (Theorem 7).
We provide a detailed discussion of various aspects of our results in Section 6, including explicit comparisons to SGD, the role of condition numbers, as well as some limitations. Finally, we end by noting some extensions and open problems in Section 7. As one of the extensions, for non-strongly convex problems, we prove that RANDOMSHUFFLE achieves a comparable convergence rate as SGD, with possibly smaller constant in the bound under certain parameter paradigms (Theorem 6). Recht and Ré [27] conjecture a tantalizing matrix AM-GM inequality that underlies RANDOMSHUF-FLE's superiority over SGD. While limited progress on this conjecture has been reported [14,38], the correctness of the full conjecture is still wide open. With the technique of transductive Rademacher complexity, Shamir [32] shows that SGD is not worse than RANDOMSHUFFLE provided the number of iterations is not too large. Asymptotic analysis is provided in [11], which proves that RAN-DOMSHUFFLE limits to a O 1 /T 2 rate for large T . Ying et al. [37] show that for a fixed step size, RANDOMSHUFFLE converges to a distribution closer to optimal than SGD asymptotically.

Related work
When the functions are visited in a deterministic order (e.g., cyclic), the method turns into Incremental Gradient Descent (IGD), which has a long history [2]. Kohonen [16] shows that IGD converges to a limit cycle under constant step size and quadratic functions. Convergence to neighborhood of optimality for more general functions is studied in several works, under the assumption that step size is bounded away from zero (see for instance [33]). With properly diminishing step size, Nedić and Bertsekas [20] show that an O 1 / √ T convergence rate in terms of distance to optimal can be achieved under strong convexity of the finite-sum. This rate is further improved in [10] to O( 1 /T ) under a second order differentiability assumption.
In the real world, RANDOMSHUFFLE has been proposed as a standard heuristic [4]. With numerical experiments, Bottou [3] notices an approximately O( 1 /T 2 ) convergence rate of RANDOMSHUFFLE. Without-replacement sampling also improves data-access efficiency in distributed settings, see for instance [9,18]. The permutation-sampling idea has been further embedded into more complicated algorithms; see [6,8,32] for variance-reduced methods, and [31] for decomposition methods.
Finally, we note a related body of work on coordinate descent, where a similar problem has been studied: when does random permutation over coordinates behave well? Gürbüzbalaban et al. [12] give two kinds of quadratic problems when cyclic version of coordinate descent beats the with replacement one, which is a stronger result indicating that random permutation also beats the with replacement method. However, such a deterministic version of the algorithm suffers from poor worst case. Indeed, in [35] a setting is analyzed where cyclic coordinate descent can be dramatically worse than both with-replacement and random permutation versions of coordinate descent. Lee and Wright [17] further study this setting, and analyze how the random permutation version of coordinate descent avoids the slow convergence of cyclic version. In [36], Wright et el. propose a more general class of quadratic functions where random permutation outperforms cyclic coordinate descent.

Background and problem setup
For problem (1.1), we assume the finite sum function F (x) : R d → R is strongly convex, i.e., where x, y ∈ R d , and µ > 0 is the strong convexity parameter. Furthermore, we assume each component function is L-smooth, so that for i = 1, . . . , n, there exists a constant L such that The norm is the spectral norm for matrices and 2 norm for vectors. We denote the unique minimizer of F (x) as x * , the index set {1, · · · , n} as [n]. The complexity bound is represented as O(·), with all logarithmic terms hidden. All other parameters that might be hidden in the complexity bounds will be clarified in corresponding sections.

The algorithms under study: SGD and RANDOMSHUFFLE
For both SGD and RANDOMSHUFFLE, we use γ as the step size, which is predetermined before the algorithms are run. The sequences generated by both methods are denoted as (x k ) T k=0 ; here x 0 is the initial point and T is the total number of iterations (i.e., number of stochastic gradients used).
SGD is defined as follows: for each iteration 1 ≤ k ≤ T , it picks an index s(k) independently uniformly from the index set [n], and then performs the update In contrast, RANDOMSHUFFLE runs as follows: for each epoch t, it picks one permutation σ t (·) : [n] → [n] independently uniformly from the set of all permutations of [n]. Then, it sequentially visits each of the component functions of the finite-sum (1.1) and performs the update for 1 ≤ k ≤ n. Here x t k = x (t−1)n+k represents the k-th iterate within the t-th epoch. For two consecutive epochs t and t + 1, one has x t+1 0 = x t n ; for the initial point one has x 1 0 = x 0 . For convenience of analysis, we always assume RANDOMSHUFFLE is run for an integer number of epochs, i.e., T = ln for some l ∈ Z + . This is a reasonable assumption given our main interest is when several epochs of RANDOMSHUFFLE are run.

Convergence analysis of RANDOMSHUFFLE
The goal of this section is to build theoretical analysis for RANDOMSHUFFLE. Specifically, we answer the following question: when can we show RANDOMSHUFFLE to be better than SGD? We begin by first analyzing quadratic functions in Section 3.1, where the analysis benefits from having a constant Hessian. Subsequently, in Section 3.2, we extend our analysis to the general (smooth) strongly convex setting. A key idea in our analysis is to make the convergence rate bounds sensitive to n, the number of components in the finite-sum (1.1). In Section 3.3, we discuss and justify the necessity of introducing n into our convergence bound.

RANDOMSHUFFLE for quadratics
We first consider the quadratic instance of (1.1), where where A i ∈ R d×d is positive semi-definite, and b i ∈ R d . We should notice often in analyzing strongly convex problems, the quadratic case presents a good example when tight bounds are achieved.
Quadratic functions have a constant Hessian function H i (x) = A i , which eases our analysis. Similar to the usual SGD, our bound also depends on the following constants: (i) strong convexity parameter µ, and component-wise Lipschitz constant L; (ii) diameter bound x − x * ≤ D (i.e., any iterate x remains bounded; can be enforced by explicit projection if needed); and (iii) bounded gradients and any x satisfying (ii). We omit these constants for clarity, but discuss the condition number further in Section 6.
Our main result for RANDOMSHUFFLE is the following (omitting logarithmic terms): Theorem 1. With f i defined by (3.1), let the condition number of problem (1.1) be κ = L/µ. So long as T log T > 6(1 + κ)n, with step size γ = 4 log T T µ , RANDOMSHUFFLE achieves convergence rate: We provide a proof sketch in Section 5, deferring the fairly involved technical details to Appendix A.
In terms of sample complexity, Theorem 1 yields the following corollary: Corollary 1. Let f i be defined by (3.1). The sample complexity for RANDOMSHUFFLE to achieve We observe that in the regime when T gets large, our result matches [11]. But it provides more information when the number of epochs is not so large that the n 3 T 3 can be neglected. This setting is clearly the most compelling to study. Formally, we recover the main result of [11] as the following: As T → ∞, RANDOMSHUFFLE achieves asymptotic convergence rate O 1 T 2 when run with the proper step size schedule.

RANDOMSHUFFLE for strongly convex problems
Next, we consider the more general case where each component function f i is convex and the sum F (x) = 1 n i f i (x) is strongly convex. Surprisingly 1 , one can easily adapt the methodology of the proof for Theorem 1 in this setting. To this end, our analysis requires one further assumption that each component function is second order differentiable and its Hessian satisfies the Lipschitz condition (2.2) with constant L H .
Under these assumptions, we obtain the following result: . So long as T log T > Cn, with step size η = 8 log T T µ , RANDOMSHUFFLE achieves convergence rate: Except for extra dependence on L H and a mildly different step size, this rate is essentially the same as that in quadratic case. The proof for the result can be found in Appendix B. Due to the similar formulation, most of the consequences noted in Section 3.1 also hold in this general setting.

Understanding the dependence on n
Since the motivation of building our convergence rate analysis is to show that RANDOMSHUFFLE behaves better than SGD, we would definitely hope that our convergence bounds have a better dependence on T compared to the O( 1 T ) bound for SGD. In an ideal situation, one may hope for a rate of the form O( 1 T 1+δ ) with some δ > 0. One intuitive criticism toward this goal is evident: if we allow T < n, then by setting n > T 2 , RANDOMSHUFFLE is essentially same as SGD by the birthday paradox. Therefore, a O 1 T 1+δ bound is unlikely to hold. However, this argument is not rigorous when we require a positive number of epochs to be run (at least one round through all the data). To this end, we provide the following result indicating the impossibility of obtaining O( 1 T 1+δ ) even when T ≥ n is required. Theorem 3. Given the information of µ, L, G. Under the assumption of constant step sizes, no step size choice for RANDOMSHUFFLE leads to a convergence rate o( 1 /T ) for any T ≥ n, if we do not allow n to appear in the bound.
The key idea to prove Theorem 3 is by constructing a special instance of problem (1.1). In particular, the following quadratic instance of (1.1) lays the foundation of our proof: Here (·) denotes the transpose of a vector, A ∈ R d×d is some positive definite matrix, and b ∈ R d is some vector. Running RANDOMSHUFFLE on (3.2) leads to a close-formed expression of RANDOMSHUFFLE's error. Then by setting T = n (i.e., only running RANDOMSHUFFLE for one epoch) and assuming a convergence rate of o 1 T , we deduce a contradiction by properly setting A and b. The detailed proof can be found in Appendix C. We directly have the following corollary: Corollary 3. Given the information of µ, L, G, under the assumption T ≥ n and constant step size, there is no step size choice that leads to a convergence rate O 1 T 1+δ for δ > 0. This result indicates that in order to achieve a better dependence on T using constant step sizes, the bound should either: (i) depend on n; (ii) make some stronger assumptions on T being large enough (at least exclude T = n); or (iii) leverage a more versatile step size schedule, which could potentially be hard to design and analyze.
Although Theorem 3 shows that one may not hope (under constant step sizes) for a better dependence on T for RANDOMSHUFFLE without an extra n dependence, whether the current dependence on n we have obtained is optimal still requires further discussion. In the special case n = T , numerical evidence has shown that RANDOMSHUFFLE behaves at least as well as SGD. However, our bound fails to even show RANDOMSHUFFLE converges in this setting. Therefore, it is reasonable to conjecture that a better dependence on n exists. In the following section, we improve the dependence on n under a specific setting. But whether a better dependence on n can be achieved in general remains open. 2

Sparse functions
In the literature on large-scale machine learning, sparsity is a common feature of data. When the data are sparse, each training data point has only a few non-zero features. Under such a setting, each iteration of SGD only modifies a few dimensions of the decision variables. Some commonly occurring sparse problems include large-scale logistic regression, matrix completion, and graph cuts.
Sparse data provides a prospective setting under which RANDOMSHUFFLE might be powerful. Intuitively, when data are sparse, with-replacement sampling used by SGD is likely to miss some decision variables, while RANDOMSHUFFLE is guaranteed to update all possible decision variables in one epoch. In this section, we show some theoretical results justifying such intuition.
Formally, a sparse finite-sum problem assumes the form where e i (1 ≤ i ≤ n) denotes a small subset of {1, . . . , d} and x ei denotes the entries of the vector x indexed by e i . Define the set E := {e i : 1 ≤ i ≤ n}. By representing each subset e i ⊆ E with a node, and considering edges (e i , e j ) for all e i ∩ e j = ∅, we get a graph with n nodes. Following the notation in [28], we consider the sparsity factor of the graph: One obvious fact is 1 n ≤ ρ ≤ 1. The statistic (4.1) indicates how likely is it that two subsets of indices intersect, which reflects the sparsity of the problem. For a problem with strong sparsity, we may anticipate a relatively small value for ρ. We summarize our result with the following theorem: . So long as T log T > Cn, with step size η = 8 log T T µ , RANDOMSHUFFLE achieves convergence rate: Compared with Theorem 2, the bound in Theorem 4 depends on the parameter ρ, so we can exploit sparsity to obtain a faster convergence rate. The key to proving Theorem 4 lies in constructing a tighter bound for the error term in the main recursion (see §5) by including a discount due to sparsity.
We end this section by noting the following simple corollary: there is some constant C only dependent on µ, L, L H , D, G, such that as long as T log T > Cn, for a proper step size, RANDOMSHUFFLE achieves convergence rate

Proof sketch of Theorem 1
In this section we provide a proof sketch for Theorem 1. The central idea is to establish an inequality are the beginning and final points of the t-th epoch, respectively, and the randomness is over the permutation σ t (·) of functions in epoch t. The constant α 1 captures the speed of convergence for the linear convergence part, while α 2 and α 3 together bound the error introduced by randomness. The underlying motivation for the bound (5.1) is: when the latter two terms depend on the step size γ with order at least 3, then by expanding the recursion over all the epochs, and setting γ = O 1 T , we can obtain a convergence of O 1 T 2 . By the definition of the RANDOMSHUFFLE update and simple calculations, we have the following key equality for one epoch of RANDOMSHUFFLE: The idea behind this equality is to split the progress made by RANDOMSHUFFLE in a given epoch into two parts: a part that behaves like full gradient descent (A t 1 and A t 3 ), and a part that captures the effects of random sampling (A t 2 and A t 4 ). In particular, for a permutation σ t (·), R t denotes the gradient error of RANDOMSHUFFLE for epoch t, i.e., which is a random variable dependent on σ t (·). Thus, the terms A t 2 and A t 4 are also random variables that depend on σ t (·), and require taking expectations. The main body of our analysis involves bounding each of these terms separately.
The term A t 1 can be easily bounded by exploiting the strong convexity of F , using a standard inequality (Theorem 2.1.11 in [23]), as follows The first term (gradient norm term) in (5.2) is used to dominate later emerging terms in our bounds on A t 2 and A t 3 , while the second term (distance term) in (5.2) will be absorbed into α 1 in (5.1). A key step toward building , where the expectation is over σ t (·). However, it is not easy to directly bound this term with γ 3 C for some constant C. Instead, we decompose this term further into three parts: (i) the first part depends on x t 0 − x * 2 (which will be then captured by α 1 in (5.1)); (ii) the second part depends on ∇F (x t 0 ) 2 (which will be then dominated by gradient norm term in A t 1 's bound (5.2)); and (iii) the third part has an at least γ 3 dependence on γ (which will be then jointly captured by α 2 and α 3 in (5.1)). Specifically, by introducing second-order information and somewhat involved analysis, we obtain the following bound for A t 2 : Lemma 1. Over the randomness of the permutation, we have the inequality: Since x * is the minimizer, we have an elegant bound on the second-order interaction term: , and x * is the minimizer of sum function, then ∆ ≤ 1 n−1 LG. We tackle A t 3 by dominating it with the gradient norm term of A t 1 's bound (5.2), and finally bound the second permutation dependent term E[A t 4 ] using the following lemma. Lemma 3. For any possible permutation in the t-th epoch, we have bound Using this bound, the term E[A t 4 ] can be captured by α 3 in (5.1). Based on the above results, we get a recursive inequality of the form (5.1). Expanding the recursion and substituting into it the step-size choice ultimately leads to an bound of the form O 1 (see (A.17) in the Appendix for dependence on hidden constants). The detailed technical steps can be found in Appendix A.

Discussion of results
We discuss below our results in more detail, including their implications, strengths, and limitations.

Comparison with SGD.
It is well-known that under strong convexity SGD converges with a rate of O 1 T [26]. A direct comparison indicates the following fact: RANDOMSHUFFLE is provably better than SGD after O( √ n) epochs. This is an acceptable amount of epochs for even some of the largest data sets in current machine learning literature. To our knowledge, this is the first result rigorously showing that RANDOMSHUFFLE behaves better than SGD within a reasonable number of epochs. To some extent, this result confirms the belief and observation that RANDOMSHUFFLE is the "correct" choice in real life, at least when the number of epochs is comparable with √ n.

Deterministic variant.
When the algorithm is run in a deterministic fashion, i.e., the functions f i are visited in a fixed order, better convergence rate than SGD can also be achieved as T becomes large. For instance, a result in [10] translates into a O n 2 T 2 bound for the deterministic case. This directly implies the same bound for RANDOMSHUFFLE, since random permutation always has the weaker worst case. But according to this bound, at least n epochs are required for RANDOMSHUFFLE to achieve an error smaller than SGD, which is not a realistic number of epochs in most applications.

Comparison with GD. Another interesting viewpoint is by comparing RANDOMSHUFFLE with
Gradient Descent (GD). One of the limitations of our result is that we do not show a regime where RANDOMSHUFFLE can be better than GD. By computing the average for each epoch and running exact GD on (1.1), one can get a convergence rate of the form O(exp(−T /n)). This fact shows that our convergence rate for RANDOMSHUFFLE is worse than GD. This comes naturally from the epoch based recursion (5.1) in our proof methodology, since for one epoch the sum of the gradients is only shown to be no worse than a full gradient. It is true that GD should behave better in long-term as the dependence on n is negligible, and comparing with GD is not the major goal for this paper. However, being worse than GD even when T is relatively small indicates that the dependence on n probably can still be improved. It may be worth investigating whether RANDOMSHUFFLE can be better than both SGD and GD in some regime. However, different techniques may be required.

Epochs required.
It is also a limitation that our bound only holds after a certain number of epochs. Moreover, this number of epochs is dependent on κ (e.g., O(κ) epochs for the quadratic case). This limits the interest of our result to cases when the problem is not too ill-conditioned. Otherwise, such a number of epochs will be unrealistic by itself. We are currently not certain whether similar bounds can be proved when allowing T to assume smaller values, or even after only one epoch.
Dependence on κ. It should be noticed that κ can be large sometimes. Therefore, it may be informative to view our result in a κ-dependent form. In particular, we still assume D, L, L H are constant, but no longer µ. We use the bound At first sight, the dependence on κ in the convergence rate may seem relatively high. However, it is important to notice that our sample complexity's dependence on κ is actually better than what is known for SGD. A O( 4G 2 T µ 2 ) convergence bound for SGD has long been known [26], which translates into a O( κ 2 ), κ-dependent sample complexity in our notation. Although better κ dependence has been shown for F (x T ) − F (x * ) < (see e.g., [13]), no better dependence has been shown for < as far as we know. Furthermore, according to [22], the lower bound to achieve F (x T ) − F (x * ) < for strongly convex F using stochastic gradients is Ω( κ / ). Translating this into the sample complexity to achieve E[ x T − x * 2 ] < is likely to introduce another κ into the bound. Therefore, it is reasonable to believe that O( κ 2 / ) is the best sample complexity one can get for SGD (which is worse than RANDOMSHUFFLE), to achieve Sparse data setting. Notably, in the sparse setting (with sparsity factor ρ = O 1 n ), the proven convergence rate is strictly better than the O 1 T rate of SGD. This result follows the following intuition: when each dimension is only touched by several functions, letting the algorithm to visit every function would avoid missing certain dimensions. For larger ρ, similar speedup can be observed. In fact, so long as we have ρ = o(n − 1 /2 ), the proven bound is better off than SGD. Such a result confirms the usage of RANDOMSHUFFLE under sparse setting.

Extensions
In this section, we provide some further extensions before concluding with some open problems.

RANDOMSHUFFLE for nonconvex optimization
The first extension that we discuss is to nonconvex finite sum problems. In particular, we study RANDOMSHUFFLE applied to functions satisfying the Polyak-Łojasiewicz condition (also known as gradient dominated functions): Here µ > 0 is some real number, F * is the minimal function value of F (·). Strongly convexity is a special situation of this condition with µ being the strongly convex parameter. One important implication of this condition is that every stationary point is a global minimum. However function F can be non-convex under such setting. Also, it doesn't imply a unique minimum of the function.
This setting was proposed and analyzed in [25], where a linear convergence rate for GD was shown.
Later, many other optimization methods have been proven efficient under this condition (see [24] for second order methods and [29] for variance reduced gradient methods). Notably, SGD can be proven to converge with rate O( 1 /T ) under this setting (see appendix for a proof).
Assume each component function f i being L Lipschitz continuous, and the average function F (x) satisfying the Polyak-Łojasiewicz condition with some constant µ. We have the following extension of our previous result: Theorem 5. Under the Polyak-Łojasiewicz condition, define condition number κ = L/µ. So long as T log T > 16κ 2 n, with step size η = 2 log T T µ , RANDOMSHUFFLE achieves convergence rate:

RANDOMSHUFFLE for convex problems
An important extension of RANDOMSHUFFLE is to the general (smooth) convex case without assuming strong convexity. There are no previous results on the convergence rate of RANDOMSHUFFLE in this setting that show it to be faster than SGD. The only result we are aware of is by Shamir [32], who shows RANDOMSHUFFLE to be not worse than SGD in the general (smooth) convex setting. We extend our results to the general convex case, and show a convergence rate that is possibly faster than SGD, albeit only up to constant terms.
We take the viewpoint of gradients with errors, and denote the difference between component gradient and full gradient as the error: . Different assumptions bounding the error term e i (x) have been studied in optimization literature. We assume that there is a constant δ that bound the norm of the gradient error: Here i is any index and x is any point in domain. Obviously, δ ≤ 2G, with G being the gradient norm bound as before. 3 We have some discussion of this result: Firstly, it is interesting to see what happens asymptotically. We can observe three levels of possible asymptotic (ignore n) convergence rates for RANDOMSHUFFLE from this theorem: (1)

Vanishing variance
Our previous results show that RANDOMSHUFFLE converges faster than SGD after a certain number of epochs. However, one may want to see whether it is possible to show faster convergence of RANDOMSHUFFLE after only one epoch, or even within one epoch. In this section, we study a specialized class of strongly convex problems where RANDOMSHUFFLE has faster convergence rate than SGD after an arbitrary number of iterations.
We build our example based on a vanishing variance setting: ∇f i (x * ) = ∇F (x * ) for the optimal point x * . Moulines and Bach [19] show that when F (x) is strongly convex, SGD converges linearly in this setting. For the construction of our example, we assume a slightly stronger situation: each component function f i (x) is strongly convex.
Given n pairs of positive numbers (µ 1 , L 1 ), · · · , (µ n , L n ) such that µ i ≤ L i , a dimension d and a point x * ∈ R d , we define a valid problem as a d dimensional finite sum function where each component f i (x) is µ i strongly convex and has L i Lipschitz continuous gradient, with some x * minimizing all functions at the same time (which is equivalent to vanishing gradient). Let P be the set of all such problems, called valid problems below. For a problem P ∈ P, let random variable X RS (T, x 0 , γ, P ) be the result of running RANDOMSHUFFLE from initial point x 0 for T iterations with step size γ on problem P . Similarly, let X SGD (T, x 0 , γ, P ) be the result of running SGD from initial point x 0 for T iterations with step size γ on problem P .
We have the following result on the worst-case convergence rate of RANDOMSHUFFLE and SGD: Theorem 7. Given n pairs of positive numbers (µ 1 , L 1 ), · · · , (µ n , L n ) such that µ i ≤ L i , a dimension d, a point x * ∈ R d and an initial set This theorem indicates that RANDOMSHUFFLE has a better worst-case convergence rate than SGD after an arbitrary number of iterations under this noted setting.

Conclusion and open problems
A long-standing problem in the theory of stochastic gradient descent (SGD) is to prove that RAN-DOMSHUFFLE converges faster than the usual with-replacement SGD. In this paper, we provide the first non-asymptotic convergence rate analysis for RANDOMSHUFFLE. We show in particular that after O( √ n) epochs, RANDOMSHUFFLE behaves strictly better than SGD under strong convexity and second-order differentiability. The underlying introduction of dependence on n into the bound plays an important role toward a better dependence on T . We further improve the dependence on n for sparse data settings, showing RANDOMSHUFFLE's advantage in such situations.
An important open problem remains: how (and to what extent) can we improve the bound such that RANDOMSHUFFLE can be shown to be better than SGD for smaller T . A possible direction is to improve the n dependence arising in our bounds, though different analysis techniques may be required. It is worth noting that for some special settings, this improvement can be achieved. (For example in the setting of Theorem 7, RANDOMSHUFFLE is shown better than SGD for any number of iterations.) However, showing RANDOMSHUFFLE converges better in general, remains open.

A Proof of Theorem 1
Proof. Assume T = nl where l is positive integer. Notate x t i as the ith iteration for tth epoch. There is Assume the permutation used in tth epoch is σ t (·). Define error term For one epoch of RANDOMSHUFFLE, We have the following inequality where the inequality is due to Theorem 2.1.11 in [23].
Take the expectation of (A.1) over randomness of permutation σ t (·), we have What remains to be done is to bound the two terms with R t dependence. Firstly, we give a bound on the norm of R t : where the first and second inequality is by triangle inequality of vector norm, the third inequality is by definition of L, the fourth inequality is by definition of G. By this result, we have For the E [R t ] term, we need more careful bound. Since the Hessian is constant for quadratic functions, we use H i to denote the Hessian matrix of function f i (·). We begin with the following decomposition: Here we define random variables There is

Using (A.4) and (A.5), we can decompose the inner product of
For the first term in (A.7), there is Here we introduce variable ∆ = E i =j [H i ∇f j (x * )] for simplicity of notation, with i, j uniformly sampled from all pairs of different indices. The first inequality is by Set λ 2 = 1 4 µ (n − 1) in (A.9) and using (A.6), there is The next step requires to bound the ∆ term. Toward this end, we use the following important fact: LG.
So whenever T log T > 6 1 + L µ n, the three assumptions hold. Therefore the theorem is proved.

B Proof of Theorem 2
Proof. The idea is similar to the proof of theorem 1, with a slightly different analysis on the R t term capturing the changing Hessian. For any i, we use H i to denote H i (x * ). For any vector v not being zero, define vector value directional function with norm being 2 norm. For the convenience of notation, we define dir 0 = 0, where 0 is the zero vector. For any two points a, b ∈ R d , and a matrix function g (·) : where the integral on the right hand side is integral of vector valued function over real number interval. This integral represents integrating the matrix values function along the line from a to b. Again, define error term We have the following decomposition for the error term: Here we define random variables Compared with quadratic case, C t is the new term capturing the difference introduced by a changing Hessian. There is Using (B.1) (B.2), we can decompose the innerproduct of x t 0 − x * and E [R t ] as following: For the first term in the (B.5), we have further bound: For the third term in (B.5), we use the bound Substituting (B.6) (B.7) (B.8) back to (B.5), we get Substituting (B.9) to (A.2), for one epoch we get recursion bound: which we call assumption 1 and assumption 2, (B.10) can be further turned into: Further assume nγ Lµ L+µ < 1, which we call assumption 3, expanding (B.11) over all the epochs we finally get a bound for RANDOMSHUFFLE: What remains to determine is to satisfy the three assumptions: L+µ − 3γ 2 n 2 > 0, and (3) nγ Lµ L+µ < 1. The first is satisfied when which is naturally satisfied and which is equivalent to T log T > 16 L + µ Lµ 2 (L H LD + 3L H G) n, which is obviously satisfied if we assume The second assumption is equivalent to which is satisfied when T log T > 8n.
Since 12 1 + L µ > 8, we only need So whenever T log T > max 32 µ 2 (L H LD + 3L H G) , 12 1 + L µ n, the three assumptions hold. Therefore the theorem is proved.

C Proof of Theorem 3
Proof. We only need to show that when T = n (i.e., one epoch is run for each problem) and n is even, no such step size schedule exists. We note the random permutation of this single epoch as σ(·). For n even, consider the following quadratic problem: where A is some d × d positive definite matrix with minimal eigenvalue µ and maximal eigenvalue L, b is a d dimensional vector. We use (·) to notate the transpose, so as to distinguish from exponential T . The exact value of A and b will be determined later. Obviously, x * = 0 is the minimizer. In this setting, we have: Expanding (C.1) over iterations leads to: Taking expectation of (C.2) over the randomness of σ, there is With (C.2) (C.3), we have close-formed expression on the final error: Assume the eigenvalues of A are λ 1 , λ 2 , · · · , λ d , there is an orthogonal basis e 1 , · · · , e d for R d such that e k is eigenvector of A with eigenvalue λ k . We can write Since e i , e j = 0 for i = j, we can simplify the last term in (C.4): (C.5) Once again, we can write Then (C.6) can simplified as Define random variables s t = (−1) σ(t) for t = 1, · · · , T . Then for any index pair t = u, over randomness of σ, there is Using this fact, we can simplify the last term in (C.7) as: For contradiction, we assume for any T , there is a γ dependent on T such that Now we determine the specific requirement of A and b. The only requirement is: A has at least three different positive eigenvalues λ 1 > λ 2 > λ 3 , and b i = 0 for any i. Furthermore, we assume a i = 0 for any i. Now for the faster convergence rate (C.9) to hold, from (C.7) we know there must be hold for any i.

D Proof of Theorem 4
Proof. The idea is similar to the proof of theorem 2, with a slightly different analysis on the R t term adopting the sparsity parameter. For any i, we use H i to denote H i (x * ). Again, we have the following decomposition for the error term: Here we define random variables This time, we have bounds for these three terms adopting sparsity information: Here the introduction of ρ in (D.3) is because: if f σt(k) and f σt(j) depend on disjoint dimensions of variables and k < j, then there must be ∇f σt(j) (x t k ) = ∇f σt(j) (x t k−1 ). The introduction of ρ in (D.4) is similar: if f σt(i) and f σt(j) depend on disjoint dimensions of variables and j < i, then there must For the first term in the (D.5), there is Where the last inequality is because of For the third term in (D.5), we use the bound (D.9) Substituting (D.9) to (A.2), we have recursion bound for one epoch: Here the last inequality is because ≤ n 2 ρLγG. Finally, we again use the fact LG.
The remaining process is same as proof of theorem 2, leading to a bound O( 1 T 2 + ρ 2 n 3 T 3 ).

E Proof of Theorem 5
Proof. The idea is similar to the proof of theorem 2. For any vector v not being zero, define vector value directional function with norm being 2 norm. For the convenience of notation, we define dir 0 = 0, where 0 is the zero vector. For any two points a, b ∈ R d , and a matrix function g (·) : where the integral on the right hand side is integral of vector valued function over real number interval. This integral represents integrating the matrix values function along the line from a to b. Again, define error term Assume F * being the minimum of function F (·). For one epoch of RANDOMSHUFFLE, we have Here the second inequality is by the definition of Polyak-Łojasiewicz condition, the last inequality uses the fact We have the following decomposition for the error term: Here we define random variables There is Using (E.2) (E.3), we can decompose the innerproduct of ∇F (x t 0 ) and E [R t ] as following: For the first term in the (E.6), we have further bound: For the second term in (E.6), we use the bound For the third term in (E.6), we use the bound Substituting (E.7) (E.8) (E.9) back to (E.6), we get Substituting (E.10) to (E.1), for one epoch we get recursion bound: (E.11) Now assume 1 2 nµγ > 4L 2 n 2 γ 2 , which we call assumption 1, (E.11) can be further turned into: Further assume nγµ < 1, which we call assumption 2, expanding (E.12) over all the epochs we finally get a bound for RANDOMSHUFFLE: What remains to determine is to satisfy the two assumptions: (1) 1 2 nµγ > 4L 2 n 2 γ 2 , (2) nγµ < 1. The first is satisfied when T log T > 16 L 2 µ 2 n. The second assumption is satisfied when T log T > 2n.
Since 2 < L µ , the theorem is proved.

F Proof of Theorem 6
Proof. For one epoch of RANDOMSHUFFLE, We have the following inequality where the first inequality is because of Therefore, taking expectation of (F.1) leads to: Define random variables where 1 ≤ k ≤ n. Obviously R t n = R t . We firstly show that R t k ≤ 3n 2 Lγ( ∇F (x t 0 ) + δ), which is an important fact to be used in further analysis.
For any index 1 ≤ id ≤ n, there is . Assume for any 1 ≤ id ≤ n and some i, there is (which is obviously true when i = 1) Then for i + 1, there is

So by induction, there is
Similar to the previous proof, we have the following decomposition for the error term: Here we define random variables There is Using (F.3) and (F.4), we can decompose the inner product of x t 0 − x * and E [R t ] into: For the first term in (F.7), there is Here we introduce variable ∆ = E i =j [H i ∇f j (x * )] for simplicity of notation, with i, j uniformly sampled from all pairs of different indices. The last inequality is because of For the second term in (F.7), we use (F.5) and have the bound For the third term in (F.7), we use (F.6) and have the bound −2γ x t 0 − x * , E C t ≤ 2γ 2 n 2 L H D 2 G. (F.10) Substituting (F.8) (F.9) and (F.10) back to (F.7), we get −2γ x t 0 − x * , E R t ≤ γ 2 n 2 ∇F x t 0 2 + γ 2 n (n − 1) D ∆ + 6γ 3 n 3 L 2 D( ∇F (x t 0 ) + δ) + γ 2 n 2 L H (LD 3 + 2D 2 G).
Obviously, this result is of the form

G Proof of Theorem 7
Proof. For both SGD and RANDOMSHUFFLE, we use s(i) to denote the index of component function picked in the ith iteration. We have the following inequality (1 − γµ s(t) ) 2 ]||x t−1 − x * || 2 .
By the AM-GM inequality, we know the term E[ T i=1 (1 − γµ s(t) ) 2 ] for RANDOMSHUFFLE is no larger than that of SGD. Also, this bound is tight when we consider f i (x) = µi 2 ||x − x * || 2 , which completes the proof.

H SGD under Polyak-Łojasiewicz condition
For the completeness of the paper, we include the following analysis of SGD under Polyak-Łojasiewicz condition. there is Proof. We have the following one iteration for SGD with step size γ: x t+1 = x t − γ∇f s(t) (x t ).
(H.1) Given x t , there is randomness over index The first inequality is because F (x) ≤ F (y) + x − y, ∇F (y) + L 2 x − y 2 .
The second inequality is because of the definition of LP condition.
Expanding over iterations leads to Setting γ = log T µT leads to a O( 1 T ) convergence of F (x T ) − F * .