Year: 2021

Abstract:
Conventional machine learning applications typically assume that data samples are independently and identically distributed (i.i.d.). However, practical scenarios often involve a data-generating process that produces highly dependent data samples, which are known to heavily bias the stochastic optimization process and slow down the convergence of learning. In this paper, we conduct a fundamental study on how different structures of stochastic update schemes affect the sample complexity of stochastic gradient descent (SGD) over highly dependent data. Specifically, with a φ-mixing model of data dependence, we show that SGD with proper periodic data-subsampling achieves an improved sample complexity over the standard SGD in the full spectrum of the data dependence level. Interestingly, even subsampling a subset of data samples can accelerate the convergence of SGD over highly dependent data. Moreover, we show that mini-batch SGD can further substantially improve the sample complexity over SGD with periodic data-subsampling over highly dependent data. We also conduct some numerical experiments to validate our theoretical results.

heading: 1 INTRODUCTION
text: Stochastic optimization algorithms have attracted great attention in the past decade due to its successful applications to a broad research areas, including deep learning (Goodfellow et al., 2016), reinforcement learning (Sutton & Barto, 2018), online learning (Bottou, 2010; Hazan, 2017), control (Marti, 2017), etc. In the conventional analysis of stochastic optimization algorithms, it is usually assumed that all data samples are independently and identically distributed (i.i.d.) and queried. For example, data samples in the traditional empirical risk minimization framework are assumed to be queried independently from the underlying data distribution, while data samples in reinforcement learning are assumed to be queried from the stationary distribution of the underlying Markov chain.
Although the i.i.d. data assumption leads to a comprehensive understanding of the statistical limit and computation complexity of SGD, it violates the nature of many practical data-generating stochastic processes, which generate highly correlated samples that depend on the history. In fact, dependent data can be found almost everywhere, e.g., daily stock price, weather/climate data, state transitions in Markov chains, etc. To understand the impact of data dependence on the convergence and complexity of stochastic algorithms, there is a growing number of recent works that introduce various definitions to quantify data dependence. Specifically, to analyze the finite-time convergence of various stochastic reinforcement learning algorithms, recent studies assume that the dependent samples queried from the Markov decision process satisfy a geometric mixing property (Dalal et al., 2018; Zou et al., 2019; Xu & Gu, 2020; Qu & Wierman, 2020), which requires the underlying Markov chain to be uniformly ergodic or has a finite mixing time (Even-Dar et al., 2003). On the other hand, to analyze the convergence of stochastic optimization algorithms over dependent data, Karimi et al. (2019) assumed the existence of a solution to the Poisson equation associated with the underlying Markov chain, which is a weaker condition than the uniform ergodic condition (Glynn & Meyn, 1996). Moreover, Agarwal & Duchi (2012) introduced a φ-mixing property of the datagenerating process that quantifies how fast the distribution of future data samples (conditioned on a fixed filtration) converges to the underlying stationary data distribution. In particular, the φ-mixing property is more general than the previous two notions of data dependence (Douc et al., 2018).
While the aforementioned works leveraged the above notions of data dependence to characterize the sample complexity of various standard stochastic algorithms over dependent data, there still lacks theoretical understanding of how algorithm structure affects the sample complexity of stochastic algorithms under different levels of data dependence. In particular, a key algorithm structure is the stochastic update scheme, which critically affects the bias and variance of the stochastic optimization process. In fact, under i.i.d. data and convex geometry, it is well known that SGD achieves the sample complexity lower bound under various stochastic update schemes (Bottou, 2010), e.g., single-sample update and mini-batch update. However, these stochastic update schemes may lead to substantially different convergence behaviors over highly dependent data, as they are no longer unbiased. Therefore, it is of vital importance to understand the interplay among data dependence, structure of stochastic update and convergence rate of stochastic algorithms, and we want to ask the following fundamental question.
• Q: How does the structure of stochastic updates affect the convergence rate and sample complexity of stochastic algorithms over dependent data?
In this paper, we provide comprehensive answers to the above fundamental question. Specifically, we conduct a comprehensive study of the convergence rate and sample complexity of the SGD algorithm over a wide spectrum of data dependence levels under various types of stochastic updates, including periodic subsampling and mini-batch sampling. Our results show that SGD with both stochastic updates achieves a substantially improved sample complexity over the standard SGD under highly dependent data. We summarize our contributions as follows.

heading: 1.1 OUR CONTRIBUTIONS
text: We consider the following standard stochastic optimization problem.
min w∈W
f(w) := Eξ∼µ [ F (w; ξ) ] , (P)
where the objective function f is convex and Lipschitz continuous, and the expectation is taken over the stationary distribution µ of the underlying data-generating process P. To perform stochastic optimization, we query a stream of dependent data samples from the underlying data-generating process. Specifically, we adopt the φ-mixing model to quantify the data dependence via a decaying mixing coefficient function φξ(k) (see Definition 2.2) (Agarwal & Duchi, 2012). We study the convergence of the stochastic gradient descent (SGD) algorithm over φ-mixing dependent data samples under various stochastic update schemes, including data subsampling and mini-batch sampling.
We first study the convergence of SGD over φ-mixing dependent data samples under the data subsampling update scheme. In particular, the data subsampling update scheme utilizes only one data sample per r consecutive data samples by periodically skipping r − 1 samples. With this data subsampling scheme, the subsampled data samples are less dependent for a larger subsampling period r. Consequently, we show that SGD with a proper data subsampling period achieves an improved sample complexity over that of the standard SGD in the full spectrum of the convergence rate of the φ-mixing coefficient. In particular, the improvement is substantial when the data is highly dependent with an algebraic decaying φ-mixing coefficient.
Moreover, we study the sample complexity of SGD over φ-mixing dependent data samples under the mini-batch update scheme. Compare to the data subsampling update, mini-batch update can substantially reduce the mini-batch data dependence without skipping data samples. Consequently, mini-batch update leverages the sample average over a mini batch of data samples to reduce both the bias (caused by the data dependence) and the optimization variance. Specifically, we show that SGD with mini-batch update achieves an orderwise lower sample complexity than both the standard SGD and the SGD with data subsampling in the full spectrum of the convergence rate of the φ-mixing coefficient. We summarize and compare the sample complexities of these stochastic algorithms under different φ-mixing data dependence models in Table 1.

heading: 1.2 RELATED WORK
text: Stochastic Algorithms over Dependent Data Steinwart & Christmann (2009) and Modha & Masry (1996) established the convergence analysis of online stochastic algorithms for streaming
data with geometric ergodicity. Duchi et al. (2011) proved that the stochastic subgradient method has strong convergence guarantee if the mixing time is uniformly bounded. Agarwal & Duchi (2012) studied the convex/strongly convex stochastic optimization problem and proved high-probability convergence bounds for general stochastic algorithms under general stationary mixing processes. Godichon-Baggioni et al. (2021) provided the non-asymptotic analysis of stochastic algorithms with strongly convex objective function over streaming mini-batch data. In a more general setting, the stochastic approximation (SA) problem was studied in (Karimi et al., 2019) by assuming the existence of solution to a Poisson equation. Recently, Debavelaere et al. (2021) developed the asymptotic convergence analysis of SA problem for sub-geometric Markov dynamic noises.
Finite-time convergence of reinforcement learning Recently, a series of work studied the finitetime convergence of many stochastic reinforcement learning algorithms over Markovian dependent samples, including TD learning (Dalal et al., 2018; Xu et al., 2019; Kaledin et al., 2020), Q-learning (Qu & Wierman, 2020; Li et al., 2021; Melo et al., 2008; Chen et al., 2019; Xu & Gu, 2020), fitted Qiteration (Mnih et al., 2013; 2015; Agarwal et al., 2021), actor-critic algorithms (Wang et al., 2019; Yang et al., 2019; Kumar et al., 2019; Qiu et al., 2019; Wu et al., 2020; Xu et al., 2020), etc. In these studies, the dependent Markovian samples are assumed to satisfy the geometric φ-mixing property, which is satisfied when the underlying Markov chain is uniformly ergodic or time-homogeneous with finite-states.
Regret of Stochastic Convex Optimization There have been many known regret bounds for online convex optimization problem. Hazan (2017) has built the standardO( √ T ) regret bound for online SGD algorithm with assuming the bounded gradient. Xiao (2009) introduces the regret bound of online dual averaging method. To our best knowledge, there is no high-probability guaranteed regret bound for mini-batch SGD algorithm with considering the data dependence.

heading: 2 PROBLEM FORMULATION AND ASSUMPTIONS
text: In this section, we introduce the problem formulation and some basic assumptions. Consider a model with parameters w. For any data sample ξ, denote F (w; ξ) ∈ R as the sample loss of this data sample under the model w. In this paper, we consider the following standard stochastic optimization problem that has broad applications in machine learning.
min w∈W
f(w) := Eξ∼µ [ F (w; ξ) ] . (P)
Here, the expectation is taken over the randomness of the data sample ξ, which is drawn from an underlying distribution µ. In particular, we make the following standard assumptions regarding the problem (P) (Agarwal & Duchi, 2012). Assumption 2.1. The stochastic optimization problem (P) satisfies
1. For every ξ, function F (·; ξ) is G-Lipschitz continuous overW , i.e., for all w, v ∈ W , |F (w; ξ)− F (v; ξ)| ≤ G‖w − v‖.
2. Function f(·) is convex and bounded below, i.e., f(w∗) := infw∈W f(w) > −∞.
3. W is a convex and compact set with bounded diameter R, i.e., supw,v∈W ‖w − v‖ ≤ R.
To solve this stochastic optimization problem, one often needs to query a set of data samples from the distribution µ to perform optimization. Unlike traditional stochastic optimization that usually assumes that the data samples are i.i.d. we consider a more general and practical dependent datagenerating process as we elaborate below.
Dependent data-generating process: We consider a stochastic process P that generates a stream of data samples {ξ1, ξ2, ..., }, which are not necessarily independent. In particular, the stochastic process P has an underlying stationary distribution µ. To quantify the dependence of the data generation process, we introduce the following standard φ-mixing model (Agarwal & Duchi, 2012), where we denote {Ft}t as the canonical filtration generated by {ξt}t. Definition 2.2 (φ-mixing process). Consider a stochastic process {ξt}t with a stationary distribution µ. Let P(ξt+k ∈ ·|Ft) be the distribution of the (t+k)-th sample conditioned on Ft, and denote dTV as the total variation distance. Then, the process {ξt}t is called φ-mixing if the following mixing coefficient φξ(·) converges to 0 as k tends to infinity.
φξ(k) := sup t∈N,A∈Ft
2dTV ( P(ξt+k ∈ ·|A), µ ) .
Intuitively, the φ-mixing coefficient describes how fast the distribution of sample ξt+k converges to the stationary distribution µ when conditioned on the filtration Ft, as the time gap k → ∞. The φmixing process can be found in many applications, which involve mixing coefficients that converge to zero at different convergence rates. Below we mention some popular examples.
• Geometric φ-mixing process. Such a type of process has a geometrically diminishing mixing coefficient, i.e., φξ(k) ≤ φ0 exp(−ckθ) for some φ0, c, θ > 0. Examples include finite-state ergodic Markov chains and some aperiodic Harris-recurrent Markov processes (Modha & Masry, 1996; Agarwal & Duchi, 2012; Meyn & Tweedie, 2012);
• Algebraic φ-mixing process. Such a type of process has a polynomially diminishing mixing coefficient, i.e., φξ(k) ≤ φ0k−θ for some φ0, θ > 0. Examples include a large class of Metropolis-Hastings samplers (Jarner & Roberts, 2002) and some queuing systems (Agarwal & Duchi, 2012).

heading: 3 CONVERGENCE OF SGD WITH SUBSAMPLING OVER DEPENDENT DATA
text: In this section, we study the convergence rate and sample complexity of SGD with data subsampling update over φ-mixing dependent data. In Section 3.1, we recap the convergence results of the standard SGD over dependent data established in (Agarwal & Duchi, 2012). In Section 3.2, we establish convergence results of SGD with the data subsampling update.
Throughout, we define the sample complexity as the total number of samples required for the algorithm to output a model w that achieves an convergence error, i.e., f(w) − f(w∗) ≤ . Also, the standard regret of a stochastic algorithm is defined as
(Regret): Rn := n∑ t=1 F (w(t); ξt)− F (w∗; ξt),
where the models {w1, w2, ..., wn} are generated using the data samples {ξ1, ξ2, ..., ξn}, respectively, and w∗ is the minimizer of f(w). For this sequence of models {w1, w2, ..., wn}, we make the following mild assumption, which is satisfied by many SGD-type algorithms. Assumption 3.1. There is a non-increasing sequence {κ(t)}t such that ‖w(t+1)−w(t)‖ ≤ κ(t).

heading: 3.1 STOCHASTIC GRADIENT DESCENT
text: Stochastic gradient descent (SGD) is a popular and classical algorithm for stochastic optimization. In every iteration t, SGD queries a sample ξt from the data-generating process and performs the following update.
(SGD): w(t+ 1) = w(t)− ηt∇F (w(t); ξt), (1)
where ηt is the learning rate. In Theorem 2 of (Agarwal & Duchi, 2012), the authors established a high probability convergence error bound for a generic class of stochastic algorithms. Specifically, under the Assumptions 2.1 and 3.1, they showed that for any τ ∈ N with probability at least 1 − δ, the averaged predictor ŵn := 1n ∑n t=1 w(t) satisfies
f(ŵn)− f(w∗) ≤ Rn n + (τ−1)G n n∑ t=1 κ(t) + 2(τ−1)GR n + 2GR
√ 2τ
n log
τ δ + φξ(τ)GR. (2)
Here, Rn is the regret of the algorithm of interest, and τ ∈ N is an auxiliary parameter that is introduced to decouple the dependence of the data samples. From the above bound, one can see that the optimal choice of τ depends on the convergence rate of the mixing coefficient φξ(τ). Specifically, consider the SGD algorithm in (1). It can be shown that it achieves the regret Rn = O( √ n)
and satisfies κ(t) = O(1/ √ t) with a proper diminishing learning rate. Consequently, the above high-probability convergence bound for SGD reduces to
f(ŵn)− f(w∗) ≤ O ( 1√
n + inf τ∈N {τ − 1√ n + √ τ n log τ δ + φξ(τ) }) . (3)
Such a bound further implies the following sample complexity results of SGD under different convergence rates of the mixing coefficient φξ. Corollary 3.2. The sample complexity of SGD in (1) for achieving an convergence error over φ-mixing dependent data is given as follows.
• If the data is geometric φ-mixing with parameter θ > 0, then we choose τ = O ( (log 1 ) 1 θ ) .
The resulting sample complexity is in the order of n = O ( −2(log 1 ) 2 θ ) .
• If the data is algebraic φ-mixing with parameter θ > 0, then we choose τ = O( − 1θ ). The resulting sample complexity is in the order of n = O( −2− 2θ ).
It can be seen that if the data-generating process has a fast geometrically diminishing mixing coefficient, i.e., the data samples are close to being independent from each other, then the resulting sample complexity is almost the same as that of SGD with i.i.d. samples. On the other hand, if the data-generating process mixes slowly with an algebraically diminishing mixing coefficient, i.e., the data samples are highly dependent, then the data dependence increases the sample complexity by a non-negligible factor of − 2 θ . In particular, such a factor is substantially large if the mixing rate parameter θ is close to zero.

heading: 3.2 SGD WITH SUBSAMPLING
text: When apply SGD to solve stochastic optimization problems over dependent data, the key challenge is that the data dependence introduces non-negligible bias that slows down the convergence of the algorithm. Hence, a straightforward solution is to reduce data dependence before performing stochastic optimization. In the existing literature, a simple and useful approach is data subsampling (Nagaraj et al., 2020; Kotsalis et al., 2020). Next, we show that such an approach leads to an improved convergence bound and sample complexity of SGD over highly dependent data.
Specifically, consider a stream of φ-mixing data samples {ξ1, ξ2, ξ3, . . . }. Instead of utilizing the entire stream of data, we subsample a subset of this data stream with period r ∈ N and obtain the following subsampled data stream
{ξ1, ξr+1, ξ2r+1, . . . }.
In particular, let {Ft}t be the canonical filtration generated by {ξtr+1}t. Since the consecutive subsampled samples are r time steps away from each other, it is easy to verify that the subsampled data stream {ξtr+1}t is also a φ-mixing process with mixing coefficient given by φrξ(t) = φξ(rt), where φrξ denotes the mixing coefficient of the subsampled data stream {ξtr+1}t. Therefore, by periodically subsampling the data stream, the resulting subsampled process has a faster-converging mixing coefficient. Then, we apply SGD over such subsampled data, i.e.,
(SGD with subsampling): w(t+ 1) = w(t)− ηt∇F (w(t); ξtr+1). (4)
In particular, the convergence error bound in eq. (2) still holds by replacing φξ(τ) with φξ(rτ), and we obtain the following bound for SGD with subsampling.
f(ŵn)− f(w∗) ≤ O ( 1√
n + inf τ∈N { (τ − 1)√ n + √ τ n log τ δ + φξ(rτ) }) . (5)
Such a bound further implies the following sample complexity results of SGD with subsampling under different convergence rates of the mixing coefficient φξ. Corollary 3.3. The sample complexity of SGD with subsampling in (4) for achieving an convergence error over φ-mixing dependent data is given as follows.
• If the data is geometric φ-mixing with parameter θ > 0, then we choose r = O ( (log 1 ) 1 θ ) and τ = O(1). The resulting sample complexity is in the order of rn = O ( −2(log 1 ) 1 θ ) .
• If the data is algebraic φ-mixing with parameter θ > 0, then we choose r = O ( − 1 θ ) and
τ = O(1). The resulting sample complexity is in the order of rn = O ( −2− 1 θ ) .
Compare the above sample complexity results with those of the standard SGD in Corollary 3.2, we conclude that data-subsampling can improve the sample complexity by a factor of (log 1 ) 1 θ and
− 1 θ for geometric φ-mixing and algebraic φ-mixing data, respectively. Intuitively, this is because with data subsampling, we can choose a sufficiently large subsampling period r to decouple the data dependence in the term φξ(rτ), as opposed to choosing a large τ in Corollary 3.2. In this way, the order of the dominant term √ τ n log τ δ is reduced. Therefore, when the data is highly dependent, it is beneficial to subsample the dependent data before performing SGD. We also note another advantage of using data-subsampling, i.e., it only requires computing the stochastic gradients of the subsampled data, and therefore can substantially reduce the computation load.

heading: 4 CONVERGENCE OF MINI-BATCH SGD OVER DEPENDENT DATA
text: Although the data-subsampling update scheme studied in the previous section helps improve the sample complexity of SGD, it does not leverage the full information of all the queried data. In particular, when the data is highly dependent, we need to choose a large period r to reduce data dependence, and this will throw away a huge amount of valuable samples. In this section, we study SGD with another popular update scheme that leverages the full information of all the sampled data, i.e., the mini-batch update scheme. We show that this simple and popular scheme can effectively reduce data dependence without skipping data samples, and can achieve an improved sample complexity over SGD with subsampling.
Specifically, we consider a data stream {ξt}t with φ-mixing dependent samples. We rearrange the data samples into a stream of mini-batches {xt}t, where each mini-batch xt contains B samples, i.e., xt = {ξ(t−1)B+1, ξ(t−1)B+2, . . . , ξtB}. Then, we perform mini-batch SGD update as follows.
(Mini-batch SGD): w(t+ 1) = w(t)− ηt B ∑ ξ∈xt ∇F (w(t); ξ). (6)
Performing SGD updates with mini-batch data has several advantages. First, it substantially reduce the optimization variance and allows to use a large learning rate to facilitate the convergence of the algorithm. As a comparison, SGD with subsampling still suffers from a large optimization variance. Second, unlike SGD with subsampling, mini-batch SGD utilizes the information of all the data samples to improve the performance of the model. Moreover, as we show in the following lemma, mini-batch update substantially reduces the stochastic bias caused by the data dependence. In the sequel, we denote F (w;x) := 1B ∑ ξ∈x F (w; ξ) as the average loss on a mini-batch of samples. With a bit abuse of notation, we also define {Ft}t as the canonical filtration generated by the minibatch samples {xt}t. Lemma 4.1. Let Assumption 2.1 hold and consider the mini-batch data stream {xt}t. Then, for any w, v ∈ W measureable with regard to Ft and any τ ∈ N, it holds that
E [ F (w;xt+τ )− F (v;xt+τ )|Ft ] − ( f(w)− f(v) ) ≤ GR
B B∑ i=1 φξ(τB + i). (7)
With dependent data, the above lemma shows that we can approximate the population risk f(w) by the conditional expectation E[F (w;xt+τ )|Ft], which involves the sample xt+τ that is τ steps ahead of the filtration Ft. Intuitively, by the φ-mixing principle, as τ gets larger, the distribution of xt+τ conditional on Ft gets closer to the stationary distribution µ. In general, the estimation bias GR B ∑B i=1 φξ(τB + i) depends on both the batch size and the accumulated mixing coefficient over the corresponding batch of samples. To provide a concrete understanding, below we calculate the estimation bias for several different mixing models.
• Geometric φ-mixing: In this case, ∑B i=1 φξ(τB + i) ≤ ∑∞ i=1 φξ(i) = O(1). Hence, the
estimation bias is in the order of O(GRB ). • Fast algebraic φ-mixing (θ ≥ 1): In this case, ∑B i=1 φξ(τB + i) ≤ ∑∞ i=1 φξ(i) = Õ(1).
Hence, the estimation bias is in the order of Õ(GRB ), where Õ hides all logarithm factors. • Slow algebraic φ-mixing (0 < θ < 1): In this case, ∑B i=1 φξ(τB + i) ≤ O((τB)1−θ).
Hence, the estimation bias is in the order of O(GRτ 1−θ
Bθ ).
It can be seen that if the mixing coefficient converges fast, i.e., either geometrically or fast algebraically, then the data dependence has a negligible impact on the estimation error. Consequently, choosing a large batch size can substantially reduce the estimation bias. On the other hand, when the mixing coefficient converges slow algebraically, it substantially increases the estimation bias, but it is still beneficial to use a large batch size. This result shows that mini-batch update can effectively reduce the statistical bias of stochastic approximation for a wide spectrum of dependent data generating processes.
We obtain prove the following convergence error bound for mini-batch SGD over dependent data. Theorem 4.2. Let Assumption 2.1 and 3.1 hold. Apply mini-batch SGD to solve the stochastic optimization problem (P) over φ-mixing dependent data and assume that it achieves regret Rn. Then, for any τ ∈ N and any minimizer w∗ with probability at least 1 − δ, the averaged predictor ŵn := 1 n ∑n t=1 w(t) satisfies
f(ŵn)− f(w∗) ≤ Rn n + G(τ − 1) n n−τ+1∑ t=1 κ(t) + GR(τ − 1) n
+O ( 1
nB B∑ i=1 φ(τB + i) + √ τ nB log τ δ log n δ ( B− 1 4 + [ B∑ i=1 φ(i) ] 1 4 )) . (8)
To further understand the order of the above bound, a standard regret analysis shows that mini-batch SGD achieves a regret in the order of Rnn = Õ( √∑n j=1 φ(j) nB ) and κ(t) ≡ O( √ B n ) (see Theorem C.3 for the proof). Consequently, the above convergence error bound reduces to the following bound, where we hide all logarithm factors for simplicity of presentation.
f(ŵn)− f(w∗) ≤ Õ (√∑n j=1 φ(j)
nB + GR(τ − 1) n (9)
+ 1
nB B∑ i=1 φ(τB + i) + √ τ nB ( B− 1 4 + [ B∑ i=1 φ(i) ] 1 4 )) . (10)
Such a bound further implies the following sample complexity results of mini-batch SGD under different convergence rates of the mixing coefficient φξ. Corollary 4.3. The sample complexity of mini-batch SGD in (6) for achieving an convergence error over φ-mixing dependent data is given as follows.
• If the data is geometric φ-mixing with parameter θ > 0, then we choose τ = 1, B = O( −1), n = O( −1). The overall sample complexity is nB = O( −2).
• If the data is fast algebraic φ-mixing with parameter θ ≥ 1, then we choose τ = 1, B = O( −1), n = O( −1). The overall sample complexity is nB = Õ( −2).
• If the data is slow algebraic φ-mixing with parameter 0 < θ < 1, then we choose τ = 1, B = O( − 1θ ), n = O( −1). The overall sample complexity is nB = O( −1− 1θ ).
It can be seen that mini-batch SGD can achieve an order-wise lower sample complexity than the SGD with subsampling in the full spectrum of φ-mixing convergence rate. Specifically, mini-batch SGD improves the sample complexity over that of SGD with subsampling by a factor of O((log 1 ) 1 θ ), Õ( − 1θ ) and O( −1) for geometric φ-mixing, fast algebraic φ-mixing and slow algebraic φ-mixing data samples, respectively. This shows that mini-batch update can effectively reduce the bias caused by data dependence and leverage the full information of all the data samples to improve the learning performance.
To intuitively explain, this is because with mini-batch updates, we can choose a sufficiently large batch size B to reduce the bias caused by the data dependence and choose a small auxiliary parameter τ = 1. As a comparison, to control the bias caused by data dependence, the standard SGD needs to choose a very large τ and the SGD with subsampling needs to choose a large subsampling period r that skips a huge amount of valuable data samples, especially when the mixing coefficient converges slowly. Therefore, our result proves that it is beneficial to use mini-batch stochastic gradient updates when the data samples are highly dependent.
We note that our proof of the tight high-probability bound in Theorem 4.2 for mini-batch SGD involves substantial new developments compared with the proof of (Agarwal & Duchi, 2012). Next, we elaborate on our technical novelty.
• In (Agarwal & Duchi, 2012), they defined the following random variable Xit := f ( w((t− 1)τ + i) ) − f(w∗) + F ( w((t− 1)τ + i); ξt+τ−1 ) − F ( w∗; ξt+τ−1 ) .
As this random variable involves only one sample ξt+τ−1, they bound the bias term Xit −E[Xit |F it−1] as a universal constant. As a comparison, the random variable Xit would involve a mini-batch of samples xt+τ−1 in our analysis. With the mini-batch structure, the biasXit−E[Xit |F it−1] can be written as an average ofB zero-mean dependent random variables, which is close to zero with high probability due to the concentration phenomenon. Consequently, we are able to apply a Bernstein-type inequality developed in (Delyon et al., 2009) for dependent stochastic process to obtain an improved bias bound from O(1) to Õ(1/ √ B). This is critical for obtaining the improved bound.
• Second, with the improved high-probability bias bound mentioned above, the remaining proof of (Agarwal & Duchi, 2012) no longer holds. Specifically, we can no longer apply the Azuma’s inequality to bound the accumulated bias ∑ t(X i t−E[Xit |F it−1]), as each bias
term is no longer bounded with probability one. To address this issue, we developed a generalized Azuma’s inequality for martingale differences in Lemma B.3 based on Proposition 34 of (Tao et al., 2015) for independent zero-mean random variables.
• Third, we develop a high-probability regret bound for mini-batch SGD over dependent data so that it can be integrated with the high-probability convergence bound in Theorem 4.2. To our best knowledge, the regret of SGD over dependent data has not been studied before.

heading: 5 NUMERICAL EXAMPLE
text: We examine our theory via a basic convex quadratic optimization problem, which is written as
min w∈Rd
f(w) := Eξ∼µ [ (w − ξ)>A(w − ξ) ] ,
where A 0 is a fixed positive semi-definite matrix and µ is the uniform distribution on [0, 1]d. Then, following the construction in (Jarner & Roberts, 2002), we generate an algebraic φ-mixing Markov chain that has the stationary distribution µ. In particular, its mixing coefficient φξ(k) converges at a sublinear convergence rate k− 1 r , where r > 0 is a parameter that controls the speed of convergence. Please refer to Appendix D for more details of the experiment setup.
We first estimate the following stochastic bias at the fixed origin point w = 0d. (Bias): ∣∣∣E[F (w;xτ )|x0 = 0d]− f(w)∣∣∣,
where the expectation is taken over the randomness of the mini-batch of samples queried at time τ ∈ N. Such a bias is affected by several factors, including the time gap τ , the batch size B and the convergence rate parameter r of the mixing coefficient.
In Figure 1, we investigate the impact of these factors on the stochastic bias, and we use 10k Monte Carlo samples to estimate the stochastic bias. The left two figures fix the batch size, and it can be seen that the bias decreases as τ increases, which matches the definition of the φ-mixing property. Also, a faster-mixing Markov chain (i.e., smaller r) leads to a smaller bias. In particular, with batch size B = 1 and a slow-mixing chain r = 2, it takes an unacceptably large τ to achieve a relatively small bias. This provides an empirical justification to Corollary 3.2 and explains why the standard SGD suffers from a high sample complexity over highly dependent data. Moreover, as the batch size gets larger, one can achieve a numerically smaller bias, which matches our Lemma 4.1. The right two figures fix the convergence rate parameter of the mixing coefficient, and it can be seen that increasing the batch size significantly reduces the bias. Consequently, instead of choosing a large τ to reduce the bias, one can simply choose a large batch size B = 100 and set τ = 1. This observation matches and justifies our theoretical results in Corollary 4.3.
We further compare the convergence of SGD, SGD with subsampling and mini-batch SGD. Here, we set r = 2 to generate highly dependent data samples. We set learning rate η = 0.01 for both SGD and SGD with subsampling, and set learning rate η = 0.01× √ B∑B
j=1 φξ(j) = 0.01×1001/4 for mini-batch SGD with
batch size B = 100, as suggested by Theorem C.3 in the appendix. The results are plotted in Figure 2, where each curve corresponds to the mean of 100 independent trails. It can be seen that SGD with subsampling achieves a lower loss than the standard SGD asymptotically, due to the use of less dependent data. Moreover, mini-batch SGD achieves the smallest asymptotic loss. All these observations are consistent with our theoretical results.

heading: 6 CONCLUSION
text: In this study, we investigate the convergence property of SGD under various popular stochastic update schemes over highly dependent data. Unlike the conventional i.i.d. data setting in which the stochastic update schemes do not affect the sample complexity of SGD, the convergence of SGD in the data-dependent setting critically depends on the structure of the stochastic update scheme. In particular, we show that both data subsampling and mini-batch sampling can substantially improve the sample complexity of SGD over highly dependent data. Our study takes one step forward toward understanding the theoretical limits of stochastic optimization over dependent data, and it opens many directions for future study. For example, it is interesting to further explore the impact of algorithm structure on the sample complexity of stochastic reinforcement learning algorithms. Also, it is important to develop advanced algorithm update schemes that can facilitate the convergence of learning over highly dependent data.

heading: A Proof of Corollary 3.3 12

heading: B Proof of Theorem 4.2 13
text: B.1 Key Lemmas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 B.2 Proof of the Main Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

heading: C Regret Analysis of Mini-Batch SGD 20

heading: D Experiment Setup 24
text: Notation: To simplify the notation, throughout the appendix, we denote ξ(i)t := ξ(t−1)B+i, which corresponds to the i-th data sample of the t-th mini-batch data xt. With this notation, we have xt = {ξ(1)t , ξ (2) t , ..., ξ (B) t }.

heading: A PROOF OF COROLLARY 3.3
text: In this section, we analyze the convergence error bound of the SGD with data-subsampling in (4).
Given a φξ-mixing data stream {ξ1, ξ2, ξ3, . . . }, we consider the following subsampled data stream {ξ1, ξr+1, ξ2r+1, . . . }.
Let F be the canonical filtration generated by {xt}. Then the subsampled data stream {ξtr+1}t is φrξ-mixing with the mixing coefficient given by
φrξ(t) = φξ(rt).
With this mixing coefficient, we can apply Theorem 2 of (Agarwal & Duchi, 2012) and obtain the following convergence error bound for any τ ∈ N.
f(ŵn)− f(w∗) ≤ O (Rn n + (τ − 1) n n∑ t=1 κ(t) + τ n + √ τ n log τ δ + φξ(rτ) ) .
Consider the standard SGD with a diminishing learning rate, we have κ(t) = O( 1√ t ) and Rn =
O( √ n). Then, the convergence error bound becomes
f(ŵn)− f(w∗) ≤ O ( 1√
n + inf τ∈N { (τ − 1)√ n + √ τ n log τ δ + φξ(rτ) }) .
The above result further implies the following sample complexity results for different convergence rates of the mixing coefficient.
• Geometric φ-mixing: In this case, φξ(k) ≤ O(exp(−kθ)) for some θ > 0. Set the last term φξ(rτ) = O( ). We obtain that rτ = O((log 1 ) 1 θ ). Further set the second term
τ−1√ n = O( ). We obtain that nτ−2 = O( −2). By choosing τ = O(1), the sample complexity is in the order of
-complexity = r · n = O (( log 1 ) 1 θ τ2 −2 ) = O ( −2 ( log −1 ) 1 θ ) .
• Algebraic φ-mixing: In this case, φξ(k) ≤ O(k−θ) for some θ > 0. Set the last term φξ(rτ) = O( ). We obtain that τr = O( − 1 θ ). Set the second term τ−1√
n = O( ). We
obtain that nτ−2 = O( −2). By setting τ = O(1), the sample complexity is in the order of -complexity = r · n = O( − 1θ τ2 −2) = O( −2− 1θ ).

heading: B PROOF OF THEOREM 4.2
text: B.1 KEY LEMMAS
In this subsection, we present several useful preliminary results for proving Theorem 4.2. Define N := {1, 2, 3, . . . }. Throughout this subsection, we assume that Assumption 2.1 holds. The following lemma is a generalization of the Lemma 1 in (Agarwal & Duchi, 2012).
Lemma B.1. Let w, v be measurable with respect to Ft. Then for any τ ∈ N,
E [ F (w;xt+τ )− F (v;xt+τ )|Ft ] ≤ GR
B B∑ i=1 φξ(τB + i) + f(w)− f(v).
Proof. For any τ ∈ N, we consider the following decomposition.
E[F (w;xt+τ )− F (v;xt+τ )|Ft] =E[F (w;xt+τ )− f(w) + f(v)− F (v;xt+τ )|Ft] + f(w)− f(v)
= [ 1 B B∑ i=1 ∫ F (w; ξ (i) t+τ )dP(ξ (i) t+τ ∈ ·|Ft)− ∫ F (w; ξ)dµ ] − [ 1 B B∑ i=1 ∫ F (v; ξ (i) t+τ )dP(ξ (i) t+τ ∈ ·|Ft)− ∫ F (v;x)dµ ] ︸ ︷︷ ︸
(A)
+ f(w)− f(v).
We can further bound the term (A) using the mixing property of the dependent data stream. (A) = [ 1 B B∑ i=1 ∫ F (w; ξ (i) t+τ )dP(ξ (i) t+τ ∈ ·|Ft)− ∫ F (w; ξ)dµ ] − [ 1 B B∑ i=1 ∫ F (v; ξ (i) t+τ )dP(ξ (i) t+τ ∈ ·|Ft)− ∫ F (v;x)dµ ] = 1
B B∑ i=1 ∫ (F (w; ξ)− F (v; ξ))d ( P(ξ(i)t+τ ∈ dξ|Ft)− µ(dξ) ) ≤ 1 B B∑ i=1 ∫ GRd
∣∣P(ξ(i)t+τ ∈ dξ|Ft)− µ(dξ)∣∣ ≤GR B B∑ i=1 φξ(τB + i),
where in the first inequality we use the facts that F (·; ξ) is G-Lipschitz and the domain is bounded by R, and the second inequality is implied by the φ-mixing property. Substituting the above upper bound of (A) into the previous equation yields that
E[F (w;xt+τ )− F (v;xt+τ )|Ft] ≤ GR
B B∑ i=1 φξ(τB + i) + f(w)− f(v).
This completes the proof.
Proposition B.2. Let {w(t)}t∈N be the model parameter sequence generated by (6). Also suppose that Assumption 3.1 holds. Then for any τ ∈ N, we have
n∑ t=1 [f(w(t))− f(w∗)]
≤ n∑ t=1 [f(w(t))− F (w(t);xt+τ−1) + F (w∗;xt+τ−1)− f(w∗)] +Rn +G(τ − 1) n−τ+1∑ t=1 κ(t) +GR(τ − 1).
Proof. For any τ ∈ N, we consider the following decomposition,
n∑ t=1 [f(w(t))− f(w∗)]
= n∑ t=1 [f(w(t))− F (w(t);xt+τ−1) + F (w∗;xt+τ−1)− f(w∗) + F (w(t);xt+τ−1)− F (w∗;xt+τ−1)]
= n∑ t=1 [f(w(t))− F (w(t);xt+τ−1) + F (w∗;xt+τ−1)− f(w∗)] (11)
+ n∑ t=1 [ F (w(t);xt+τ−1)− F (w∗;xt+τ−1) ] ︸ ︷︷ ︸
(B)
.
We will keep the first term and bound the term (B).
(B) = n∑ t=1 F (w(t);xt+τ−1)− F (w∗;xt+τ−1)
= n∑ t=1
[F (w(t);xt)− F (w∗;xt)]︸ ︷︷ ︸ (B1) +
n−τ+1∑ t=1
[F (w(t);xt+τ−1)− F (w(t+ τ − 1);xt+τ−1)]︸ ︷︷ ︸ (B2)
+ n∑ t=n−τ+2 F (w(t);xt+τ−1)− τ−1∑ t=1 F (w(t);xt) + τ−1∑ t=1 F (w∗;xt)− n+τ−1∑ t=n+1
F (w∗;xt)︸ ︷︷ ︸ (B3) .
Recall that the term (B1) is the regret Rn. We can bound the term (B2) by noting that
F (w(t);xt+τ−1)− F (w(t+ τ − 1);xt+τ−1) ≤ G‖w(t+ τ − 1)− w(t)‖
≤ G τ−2∑ i=0 ‖w(t+ i+ 1)− w(t+ i)‖
≤ G τ−2∑ i=0 κ(t+ i)
≤ G(τ − 1)κ(t).
For the term (B3), we can bound it using theG-Lipschitzness of F (·; ξ) and theR-bounded domain.
n∑ t=n−τ+2 F (w(t);xt+τ−1)− τ−1∑ t=1 F (w(t);xt) + τ−1∑ t=1 F (w∗;xt)− n+τ−1∑ t=n+1 F (w∗;xt+τ−1)
= [ n∑ t=n−τ+2 F (w(t);xt+τ−1)− n+τ−1∑ t=n+1 F (w∗;xt+τ−1) ] − [ τ−1∑ t=1 F (w(t);xt)− τ−1∑ t=1 F (w∗;xt) ]
≤ G [ n∑ t=n−τ+2 ‖w(t)− w∗‖ ] +G [ τ−1∑ t=1 ‖w(t)− w∗‖ ]
≤ GR(τ − 1).
Combining the above bounds of (B1), (B2), and (B3), we obtain the upper bound of (B) as follows.
n∑ t=1 F (w(t);xt+τ−1)− F (w∗;xt+τ−1)
= n∑ t=1
[F (w(t);xt)− F (w∗;xt)]︸ ︷︷ ︸ (B1) +
n−τ+1∑ t=1
[F (w(t);xt+τ−1)− F (w(t+ τ − 1);xt+τ−1)]︸ ︷︷ ︸ (B2)
+ n∑ t=n−τ+2 F (w(t);xt+τ−1)− τ−1∑ t=1 F (w(t);xt) + τ∑ t=1 F (w∗;xt)− n+τ−1∑ t=n+1
F (w∗;xt)︸ ︷︷ ︸ (B3) .
≤ Rn +G(τ − 1) n−τ+1∑ t=1 κ(t) +GR(τ − 1).
Then the proof is completed by substituting the upper bound of (B) into (11).
The following generalized Azuma’s inequality generalizes the Proposition 34 of (Tao et al., 2015). The inequality can be used to bound sum of martingale difference random variables.
Lemma B.3 (Generalized Azuma’s Inequality). Let {Xt} be a martingale difference sequence with respect to its canonical filtration F . Define Y = ∑T i=1Xi and assume E|Y | < ∞. Then for any {αt}t > 0,
P |Y − EY | ≥ λ √√√√ T∑
t=1
α2t  ≤ 2 exp(−λ2 2 ) + T∑ t=1 P(|Xt| ≥ αt).
Proof. Let T := min{t : |Xt| > αt}. Then the sets Bt := {ω : T (ω) = t} are disjoint. Construct
Y ′(ω) := Y (ω) if ω ∈ (⋃T t=1Bt )C ,
E[Y |Bt] if ω ∈ Bt for all t ∈ {1, 2, . . . , T}.
By the above construction, the associated Doob martingale of Y ′ with respect to F is {Zt :=∑t∧T i=1 Xi}. It satisfies the conditions of Azuma’s inequality, i.e.,
• {Zt} forms a martingale with respect to F (because the stopped martingale is still a martingale).
• |Zt − Zt−1| ≤ αt.
Then we can apply Azuma’s inequality to Y ′.
P |Y ′ − EY ′| ≥ λ √√√√ T∑
t=1
α2t  ≤ 2 exp(−λ2 2 ) .
Now we can bound P ( |Y − EY | ≥ λ √∑T t=1 α 2 t ) as follows.
P |Y − EY | ≥ λ √√√√ T∑
t=1
α2t  =P |Y − EY | ≥ λ √√√√ T∑
t=1
α2t , Y = Y ′
+ P |Y − EY | ≥ λ √√√√ T∑ t=1 α2t , Y 6= Y ′ 
≤P |Y ′ − EY ′| ≥ λ √√√√ T∑
t=1
α2t + P (Y 6= Y ′) ≤2 exp ( −λ 2
2
) + T∑ t=1 P(|Xt| ≥ αt).
Then the proof is completed. Here we notice the fact that EY ′ = EY by our construction.
The following lemma is taken from (22), Theorem 4 of (Delyon et al., 2009).
Lemma B.4 (Bernstein’s Inequality for Dependent Process). Let {Zt} be a centered adaptive process with respect to F . Define the following quantities.
q = n∑ k=1 k−1∑ i=1 ‖Zi‖∞ · ‖E[Zk|Fi]‖∞,
v = ∑ k ‖E[Z2k |Zk−1, . . . , Z1]‖∞,
m = sup 1≤i≤n
‖Zi‖∞.
Then, it holds that
P ( n∑ i=1 Zi ≥ t ) ≤ exp ( − t 2 2(v + 2q) + 2tm/3 ) .
Application of Lemma B.4 to our proof. Here we make some comments about how to apply this inequality in our main proof. We define the following random variable in our proof. Throughout, we use the batch-level filtration F and the intra-batch level filtration F̂ . The formal definition is given in Section B.2.
Xit = f ( w((t− 1)τ + 1) ) − f(w∗) + F (w∗;xtτ+i−1)− F ( w((t− 1)τ + 1);xtτ+i−1 ) .
We also define the filtration F it := Ftτ+i−1 for simplicity. Then, we have E[Xit |F it−1] = f ( w((t− 1)τ + 1) ) − f(w∗) + E [ F (w∗;xtτ+i−1)− F ( w((t− 1)τ + 1);xtτ+i−1 ) |F it−1 ] .
Then, the bias can be rewritten as
Xit − E[Xit |F it−1] =F (w∗;xtτ+i−1)− F (w((t− 1)τ + 1);xtτ+i−1)− E [ F (w∗;xtτ+i−1)− F ( w((t− 1)τ + 1);xtτ+i−1 ) |F it−1 ] = 1
B ∑ ξ∈xtτ+i−1 Y it (ξ),
where Y it is defined as
Y it (ξ) = F (w ∗; ξ)− F
( w((t− 1)τ + 1); ξ ) − E [ F (w∗; ξ)− F ( w((t− 1)τ + 1); ξ ) |F it−1 ] .
More specifically, we have
Xit − E[Xit |F it−1] = 1
B ∑ ξ∈xtτ+i−1 Y it (ξ) = 1 B B∑ j=1 Y it (ξ (j) tτ+i−1).
Recall that F̂ is the canonical filtration generated from the data stream (12). Moreover, {Y it (ξ (j) tτ+i−1)}j=1,2,...,B is centered and adaptive with respect to this filtration. Then we can evaluate the quantities q, v, and m in Lemma B.4 as follows.
• Bounding m is simple. By Assumption 2.1 we have ‖Y it (ξ (j) tτ+i−1)‖ ≤ 2GR.
• The above bound of m leads to a simple bound for v, i.e., v ≤ 2nG2R2. • The quantity q can be bounded as follows.
q := n∑ k=1 k−1∑ j=1 ‖Y it (ξ (j) tτ+i−1)‖∞‖E[Y i t (ξ (k) tτ+i−1)|F̂ (j) tτ+i−1]‖∞
≤ 2GR n∑ k=1 k−1∑ j=1 ‖E[Y it (ξ (k) tτ+i−1)|F̂ (j) tτ+i−1]‖∞
= 2GR n∑ k=1 k−1∑ j=1 ‖E[Y it (ξ (k) tτ+i−1)|F̂ (j) tτ+i−1]− Eξ∼µY i t (ξ (k) tτ+i−1)‖∞ ≤ 4G2R2 n∑ k=1 k−1∑ i=1 φξ(k − i)
≤ 4G2R2n n∑ i=1 φξ(i).
Then, by applying Lemma B.4, we obtain the following high-probability bound.
P ( |Xit − E[Xit |F it−1]| ≥ t ) ≤ 2 exp ( − B 2t2
2(v + 2q) + 2Btm/3 ) ≤ 2 exp ( − B 2t2
2(2G2R2B + 8G2R2B ∑B i=1 φξ(i)) + 4GRBt/3
)
= 2 exp ( − Bt 2
2(2G2R2 + 8G2R2 ∑B i=1 φξ(i)) + 4GRt/3
) .
Simplifying yields that
P ( |Xit − E[Xit |F it−1]| ≥ t ) ≤ 2 exp ( − Bt 2
C + 43GRt+ 16G 2R2 ∑B i=1 φξ(i)
) ,
where C := 4G2R2.
B.2 PROOF OF THE MAIN RESULT
Recall that we are considering a data stream divided into small mini-batches. For convenience, we re-label the data stream {ξ1, ξ2, ξ3, . . . } as follows to explicitly indicate its mini-batch index.
{ξ(1)1 , ξ (2) 1 , . . . , ξ (B) 1 , ξ (1) 2 , ξ (2) 2 , . . . , ξ (B) 2 , . . . }. (12)
The canonical filtration generated by the re-labeled data stream is denoted by F̂ . Also, when the batch size is clear in the context, we denote the data in the specified mini-batch as x. For example,
we use xt to represent the t-th mini-batch {ξ(1)t , ξ (2) t , . . . , ξ (B) t }. Then we can re-writhe the above data stream as
{x1, x2, x3. . . . }.
We denote the canonical filtration generated by the above sequence as F . Note that we have the following relation:
Ft = F̂ (B)t .
In summary, when we analyze the mini-batch SGD dynamics, we use the filtration F , and when we need to consider intra-batch samples, we use the filtration F̂ . Theorem B.5. Let {w(t)}t∈N be the model parameter sequence generated by (6). Suppose Assumptions 2.1 and 3.1 hold. Then, for any τ ∈ N, with probability at least 1− δ, we have
n∑ t=1 [f(w(t))− f(w∗)]
≤GR n B B∑ i=1 φξ(τB + i)
+ √√√√√2τn B · (2 3 GR B log 4n δ + √√√√4 9 G2R2 B (log 4n δ )2 + ( 4G2R2 + 16G2R2 B∑ i=1 φξ(i) ) log 4n δ ) · log 4τ δ log 4n δ +Rn +G(τ − 1) n−τ+1∑ t=1 κ(t) +GR(τ − 1).
In particular, if τ = 1, then n∑ t=1 [f(w(t))− f(w∗)]
≤Rn +GR n
B B∑ i=1 φξ(B + i)
+ √√√√√2n B · (2 3 GR B log 4n δ + √√√√4 9 G2R2 B (log 4n δ )2 + ( 4G2R2 + 16G2R2 B∑ i=1 φξ(i) ) log 4n δ ) · log 4τ δ log 4n δ .
Proof. From Proposition B.2, we obtain the following bound. n∑ t=1 [f(w(t))− f(w∗)]
≤ n∑ t=1 [f(w(t))− F (w(t);xt+τ−1) + F (w∗;xt+τ−1)− f(w∗)] +Rn +G(τ − 1) n−τ+1∑ t=1 κ(t) +GR(τ − 1).
To complete the proof, it suffices to bound the first term; we define this term as
Zn := n∑ t=1 [f(w(t))− F (w(t);xt+τ−1) + F (w∗;xt+τ−1)− f(w∗)].
We apply the same decomposition as the (13) of (Agarwal & Duchi, 2012). Define the index set I(i) as {1, . . . , bnτ c+ 1} for i ≤ n− τb n τ c and {1, . . . , b n τ c} otherwise. Then we have
Zn = τ∑ i=1 ∑ t∈I(i) [Xit − E[Xit |F it−1]] + τ∑ i=1 ∑ t∈I(i) E[Xit |F it−1],
where Xit = f ( w((t− 1)τ + 1) ) − f(w∗) + F (w∗;xtτ+i−1)− F ( w((t− 1)τ + 1);xtτ+i−1 ) .
Note that by Lemma 4.1, we have that E[Xit |F it−1] ≤ GRB ∑B i=1 φξ(τB + i). Then, we have
P ( Zn > nGR
B B∑ i=1 φξ(τB + i) + γ ) ≤ P( τ∑ i=1 ∑ t∈I(i) [Xit − E[Xit |F it−1]] > γ)
≤ P ( τ⋃ i=1 { ∑ t∈I(i) [Xit − E[Xit |F it−1]] > γ τ })
≤ τ∑ i=1 P ( ∑ t∈I(i) [Xit − E[Xit |F it−1]] > γ τ ) .
Define Y := ∑ t∈I(i)[X i t −E[Xit |F it−1]] and α := λ√B . Notice that X i t −E[Xit |F it−1] is a centered random variable, that is, E[Xit − E[Xit |F it−1]] = 0. Then by the generalized Azuma’s inequality (Lemma B.3), we conclude that
P ( Y ≥ γ
τ
) ≤ 2 exp ( − γ 2
2τ2 nτ α 2
) + n τ∑ t=1 P(|Xit − E[Xit |F it−1]| ≥ α).
The second term can be bounded by using the generalized Bernstein’s inequality. The detailed calculation can be found in the discussion after Lemma B.4. We obtain that
P ( |Xit − E[Xit |F it−1]| ≥ α ) ≤ 2 exp ( − λ 2
C + 43GR λ√ B + 16G2R2 ∑B i=1 φξ(i)
) ,
where C = 4G2R2. In summary, the concentration bound for Zn is P ( Zn > GR n
B ∑ i φξ(τB + i) + γ )
≤ 2τ exp ( − γ 2
2τ2 nτ α 2
) + τ n τ∑ t=1 P(|Xit − E[Xit |F it−1]| ≥ α)
≤ 2τ exp ( − γ 2
2τnλ 2
B
) + 2n exp ( − λ 2
C + 43GR λ√ B + 16G2R2 ∑B i=1 φξ(i)
) .
Then, let δ2 = 2n exp ( − λ 2
C+ 43GR λ√ B +16G2R2 ∑B i=1 φξ(i)
) , and we obtain that
λ2 = ( C + 4
3 GR λ√ B + 16G2R2 B∑ i=1 φξ(i) ) · log 4n δ .
It is a quadratic function of λ. Solving it yields that
λ = 2
3
GR
B log
4n
δ + √√√√4 9 G2R2 B ( log 4n δ )2 + ( C + 16G2R2 B∑ i=1 φξ(i) ) log 4n δ . (13)
Also, let δ2 = 2τ exp ( − γ 2
2τnλ 2
B
) , we have that
γ2 = 2τn λ2 B · log 4τ δ .
Substituting (13) into the above equation, we obtain that
γ = √√√√√2τn B · (2 3 GR B log 4n δ + √√√√4 9 G2R2 B ( log 4n δ )2 + ( C + 16G2R2 B∑ i=1 φξ(i) ) log 4n δ ) · log 4τ δ log 4n δ .
Then, we conclude that with probability at least 1− δ, n∑ t=1 [f(w(t))− f(w∗)]
≤GR n B B∑ i=1 φξ(τB + i)
+ √√√√√2τn B · (2 3 GR B log 4n δ + √√√√4 9 G2R2 B ( log 4n δ )2 + ( 4G2R2 + 16G2R2 B∑ i=1 φξ(i) ) log 4n δ ) · log 4τ δ log 4n δ +Rn +G(τ − 1) n−τ+1∑ t=1 κ(t) +GR(τ − 1). (14)
The desired result follows by noting that ∑n t=1 f(w(t)) ≥ nf(ŵn).

heading: C REGRET ANALYSIS OF MINI-BATCH SGD
text: In this section, we derive the regret bound of mini-batch SGD algorithm. Throughout, for each sample loss F (w; ξ), recall that its gradient ‖∇F (w; ξ)‖ is uniformly bounded by G (see Assumption 2.1). In particular, we assume the k-th coordinate of ∇F (w; ξ) is uniformly bounded by Gk, and we have G = √∑ kG 2 k.

heading: 1. Gradient Variance Bound under Dependent Data
text: In the i.i.d. setting, the variance of stochastic gradient decreases as the batch size increases. Specifically, we have
E‖ 1 B B∑ i=1 ∇F (w; ξi)−∇f(w)‖2 = 1 B2 B∑ i=1 E‖∇F (w; ξi)−∇f(w)‖2 ≤ 2G2 B .
Therefore, E‖ 1B ∑B i=1∇F (w; ξi) − ∇f(w)‖2 = O( 1 B ). However, this bound no longer holds if the data samples are dependent. In the following lemma, we develop a similar result when the data is collected from a dependent stochastic process. Recall that ∇F (w(t);xt) denotes the averaged gradient over the mini-batch xt, i.e.,
∇F (w(t);xt) = 1
B B∑ i=1 F (w(t); ξ (i) t ).
Lemma C.1. Let {w(t)}t∈N be the model parameter sequence generated by the mini-batch SGD in (6). Let Assumptions 2.1 and 3.1 hold. Then, with probability at least 1− δ, ‖∇F (w(t);xt)−∇f(w(t))‖2 ≤ [268
3 G2 + 256G2 B∑ j=1 φξ(j) ] · log 2dδ B + 2G2 (∑B i=1 φξ(i) B )2 .
Proof. Let xt = {ξ(i)t }Bi=1 be the t-th mini-batch samples. We consider the filtration within xt and denote it as {F̂ (i)t }. Then, by the definition of canonical filtration,
Xi := ∇F (w(t); ξ(i)t )
is measurable with respect to F̂ (i)t . Define
Yi,k := (Xi − E[Xi|Ft−1])k where (·)k denotes the k-th entry of the specified vector. And it is easy to see that {Yi,k}i is a centered process for any k ∈ {1, 2, . . . , d}. With these construction, we start from the following
decomposition.
‖∇F (w(t);xt)−∇f(w(t))‖2
=‖∇F (w(t);xt)− E[∇F (w(t);xt)|Ft−1] + E[∇F (w(t);xt)|Ft−1]−∇f(w(t))‖2 ≤2 ‖∇F (w(t);xt)− E[∇F (w(t);xt)|Ft−1]‖2︸ ︷︷ ︸ (A) +2 ‖E[∇F (w(t);xt)|Ft−1]−∇f(w(t))‖2︸ ︷︷ ︸ (B) .
Then we will bound the term (A) and (B), respectively.
• Bounding (A): Note that
‖∇F (w(t);xt)− E[∇F (w(t);xt)|Ft−1]‖2 = 1
B2 ‖ B∑ i=1 [Xi − E[Xi|Ft−1]]‖2
= 1
B2 d∑ k=1 [ B∑ i=1 (Xi − E[Xi|Ft−1])k ]2
= 1
B2 d∑ k=1 [ B∑ i=1 Yi,k ]2 .
Then, we show that the process {Yi,k}i satisfies the conditions of Lemma B.4.
◦ Since E[Yi,k|Ft−1] = 0, we conclude that {Yi,k}i is a centered process. ◦ Denote the k-th entry of Xi as Xi,k. We know that |Xi,k| ≤ Gk. Hence, we conclude
that 0 ≤ |Yi,k| ≤ 2Gk. Then, we can set bi = 2Gk for all i. ◦ Lastly, we can bound the quantity q defined in Lemma B.4 as follows.
q ≤ 2Gk B∑ j=1 j−1∑ i=1 ‖E[Yj,k|F (i)t ]‖+ 4 3 G2kB
≤ 4G2k B∑ j=1 j−1∑ i=1 φξ(j − i) + 4 3 G2kB ≤ 4G2kB B∑ j=1 φξ(j) + 4 3 G2kB.
Now, we can apply Lemma B.4 and obtain that
P (∑ i Yi,k > λ ) ≤ exp ( − λ 2 134 3 G 2 kB + 128G 2 kB ∑B j=1 φξ(j) ) .
With a union bound, we obtain that
P (∣∣∑ i Yi,k ∣∣ > λ) ≤ 2 exp(− λ2 134 3 G 2 kB + 128G 2 kB ∑B j=1 φξ(j) ) .
Further applying the union bound over k = 1, 2, . . . , d, we obtain that
P ( d⋃ k=1 {∣∣∑ i Yi,k ∣∣2 > λ2k} ) ≤ 2 ∑ k exp ( − λ 2 k 134 3 G 2 kB + 128G 2 kB ∑B j=1 φξ(j) ) .
Let δd = 2 exp ( − λ 2 k
134 3 G 2 kB+128G 2 kB ∑B j=1 φξ(j)
) , we obtain that
λ2k = [134
3 G2kB + 128G 2 kB B∑ j=1 φξ(j) ] · log 2d δ .
Then we conclude that,
P  d⋂ k=1 {∣∣∑ i Yi,k ∣∣2 ≤ [134 3 G2kB + 128G 2 kB B∑ j=1 φξ(j) ] · log 2d δ } ≥ 1− δ. It implies that with the probability at least 1− δ,
∑ k ∣∣∑ i Yi,k ∣∣2 ≤ [134 3 B (∑ k G2k ) + 128B ( B∑ j=1 φξ(j) )(∑ k G2k )] · log 2d δ .
By definition, G = √∑
kG 2 k. Finally, we have the following bound for term (A): with
probability at least 1− δ,
‖∇F (w(t);xt)− E[∇F (w(t);xt)|Ft−1]‖2 ≤ [134
3 G2 + 128G2 B∑ j=1 φξ(j) ] · log 2dδ B .
• Bounding (B): Note that ‖E[∇F (w(t); ξ(i)t )|Ft−1]−∇f(w(t))‖ = ∥∥∥∫ ∇F (w(t); ξ(i)t )dP(ξ(i)t ∈ ·|Ft−1)− ∫ ∇F (w(t); ξ)dµ(ξ)∥∥∥
≤ ∫ ‖∇F (w(t); ξ(i)t )‖|dP(ξ (i) t ∈ ·|Ft−1)− dµ|
≤ G · φξ(i).
Then we bound the norm by triangle inequality,
‖E[∇F (w(t);xt)|Ft−1]−∇f(w(t))‖ ≤ 1
B B∑ i=1 ‖E[∇F (w(t); ξ(i)t )|Ft−1]−∇f(w(t))‖
≤ G B B∑ i=1 φξ(i).
Finally, we obtain the bound for the term (B) as
‖E[∇F (w(t);xt)|Ft−1]−∇f(w(t))‖2 ≤ G2 (∑B i=1 φξ(i)
B
)2 .
Combing the bounds of (A) and (B) yields that with probability at least 1− δ, ‖∇F (w(t);xt)−∇f(w(t))‖2 ≤ [268
3 G2 + 256G2 B∑ j=1 φξ(j) ] · log 2dδ B + 2G2 (∑B i=1 φξ(i) B )2 .

heading: 2. High-Probability Regret Bound
text: To derive the regret bound for the mini-batch SGD algorithm, we make the following additional mild assumption.
Assumption C.2. The stochastic optimization problem (P) satisfies
1. Each sample loss F (·; ξ) :W → R is convex.
2. The objective function f :W → R is L-smooth.
Theorem C.3 (High-probability regret bound). Let {w(t)}t∈N be the model parameter sequence generated by the mini-batch SGD in (6). Suppose Assumptions C.2, 3.1 and 2.1 hold. Then, with probability at least 1− δ,
RT ≤ ‖w(1)− w∗‖2
2η + ηT [(268 3 G2 + 256G2 B∑ j=1 φξ(j) ) log 2dTδ B + 2G2 (∑B i=1 φξ(i) B )2]
+ 2ηL T∑ t=1 ( f(w(t))− f(w∗) ) .
Moreover, let η = O( √
B T · ∑B j=1 φξ(j) ), the optimized upper bound is in the order of
RT = Õ (√T ·∑Bj=1 φξ(j)
B
) + 2ηL T∑ t=1 ( f(w(t))− f(w∗) ) .
Proof. For convenience, we define gt = 1B ∑B i=1∇F (w(t); ξ (i) t ). By the algorithm update (6), we obtain that
2〈gt, w(t)− w∗〉 ≤ ‖w(t)− w∗‖2 − ‖w(t+ 1)− w∗‖2
η + η‖gt‖2
≤ ‖w(t)− w ∗‖2 − ‖w(t+ 1)− w∗‖2
η + 2η‖gt −∇f(w(t))‖2 + 2η‖∇f(w(t))‖2.
Summing the above inequality over t yields that
2 T∑ t=1 〈gt, w(t)− w∗〉
≤‖w(1)− w ∗‖2 − ‖w(T + 1)− w∗‖2
η + 2η T∑ t=1 ‖gt −∇f(w(t))‖2 + 4ηL T∑ t=1 (f(w(t))− f(w∗)).
By convexity of the function, we further obtain that
2 T∑ t=1 (F (w(t);xt)− F (w∗;xt)) ≤ ‖w(1)− w∗‖2 η + 2η T∑ t=1 ‖gt −∇f(w(t))‖2 + 4ηL T∑ t=1 (f(w(t))− f(w∗)).
Then, we apply Lemma C.1 to bound the second term ∑T t=1 ‖gt − ∇f(w(t))‖2 and then apply a union bound on over t. We conclude that, with probability at least 1− δ, T∑ t=1 (F (w(t);xt)− F (w∗;xt))
≤‖w(1)− w ∗‖2
2η + ηT · [(268 3 G2 + 256G2 B∑ j=1 φξ(j) ) log 2dTδ B + 2G2 (∑B i=1 φξ(i) B )2 ]
+ 2ηL T∑ t=1 (f(w(t))− f(w∗)).
The proof is completed. Lastly, we set the learning rate η. To minimize the obtained upper bound, it suffices to minimize the first two terms, as the last term can be combined with the left hand side of (14) when we apply this regret bound. The optimized learning rate is achieved when
‖w(1)− w∗‖2
2η = ηT · [(268 3 G2 + 256G2 B∑ j=1 φξ(j) ) log 2dTδ B + 2G2 (∑B i=1 φξ(i) B )2 ] .
Then, η is chosen as
η = √√√√ ‖w(1)− w∗‖2/2 T · [(
268 3 G 2 + 256G2 ∑B j=1 φξ(j) ) log 2dTδ B + 2G 2 (∑B i=1 φξ(i) B )2 ] = O (√ B
T · ∑B j=1 φξ(j)
) .

heading: D EXPERIMENT SETUP
text: Recall that we consider the following convex quadratic optimization problem:
min w∈Rd
Eξ∼µ(w − ξ)TA(w − ξ),
whereA is a fixed positive semi-definite matrix and µ is the uniform distribution on [0, 1]d. The data stream admitting such a stationary distribution µ can be generated by a certain Metropolis-Hastings sampler provided in (Jarner & Roberts, 2002). Specifically, it is described as follows.
Step 1: Let the “proposal” distribution q(x) have the density of Beta(r + 1, 1); that is,
q(x) = { (r + 1)xr x ∈ [0, 1] 0 x /∈ [0, 1] .
Define the acceptance probability α(x, y) = min{ q(x)q(y) , 1}.
Step 2: If the current state is ξt, then we sample ζ ∼ q. Define the next state ξt+1:
ξt+1 = { ξt w.p. 1− α(ξt, ζ), ζ w.p. α(ξt, ζ).
Step 3: Go back to Step 2 to generate the next state.
We repeatedly generate d independent sequences starting from the same initial state s0 = 0 to obtain a d-dimension Markov chain. It has been shown that the above generated Markov chain converges to µ in distribution with an algebraic convergence rate φξ(k) ≤ O(k−1/r) in Proposition 5.2, (Jarner & Roberts, 2002).
We consider the following bias term at the fixed point w = 0d. (Bias): ∣∣E[F (w;xτ )|x0 = 0d]− f(w)∣∣.
It can be used to approximate the left-hand side of Lemma 4.1. Since E [ F (w;xτ )|s0 = 0d ] cannot be explicitly obtained, we use Monte Carlo method to estimate this conditional expectation. That is, we generate n = 10, 000 independent trajectories starting from x0 = 0d. At the step τ , we estimate the expected value as 1n ∑n i=1 F (w;x (i) τ ), where x (i) τ with the superscript (i) indicates that it is sampled from the i-th trajectory. Then we investigate the relation between the step τ and the mixing parameter r and the relation between the step τ and the batch size B. All the results are presented in Section 5.

Review summaries:
In stochastic convex optimization (SCO) characterized by the following objective for convex $f$, $$\min_w f(w) := \mathbb{E}_{\xi\sim \mu}[F(w; \xi)],$$ we typically assume repeated access to the noise distribution $\mu$, for sampling i.i.d. random variables $(\xi_t)_t$. This access can be used to obtain unbiased estimates $\nabla F(w; \xi_t)$ of the true gradient $\nabla f(w)$. This oracle access can be used to implement stochastic gradient methods, which are well studied and known to have optimal sample complexity under certain regularity conditions.   On the other hand in online convex optimization, at each time step, we obtain a loss function $f_t$ from some function class $\mathcal{F}$, and we have to minimize some notion of regret. This can be modeled like SCO by defining, $f_t:= F(.; \xi_t)$, but since there was no restriction on $f_t$'s, the $\xi_t$'s here can have arbitrary dependencies over time. In particular, they could be chosen adversarially.   In between both these extremes is the setting where $\xi_t$ could have some dependency structure. One such structure called $\phi$-mixing was introduced by [Agarwal and Duchi](https://arxiv.org/abs/1110.2529). Under this dependence assumption, they provide upper bounds on the convergence of SGD. This paper generalizes these upper bounds to a sub-sampling variant of SGD as well as mini-batch SGD. It shows that mini-batch SGD essentially attains the $1/\epsilon^2$ sample complexity of for i.i.d. sampling when there is a low level of dependence in $\xi_t$'s, and more generally improves over vanilla SGD across various levels of dependence captured by the $\phi$-mixing assumption.

This paper studies the sample complexity of a few variants of SGD in solving optimization problems over dependent data. The dependent data introduces non-negligible bias in SGD that slows down convergence of the algorithm, and this paper adopts \phi-mixing data dependence models, to quantify the level of dependence in the queried samples, and analyze how much the convergence of SGD can be slowed down in terms of the phi-mixing model. Then, this paper demonstrates the benefits of SGD with subsampling and mini-batch SGD over SGD for dependent data.