How to Improve Sample Complexity of SGD over Highly Dependent Data?
Authors: Shaocong Ma
Ziyi Chen
Yi Zhou
Kaiyi Ji
Yingbin Liang
Venue: ICLR 2022 Submitted (2022)
Keywords: Dependent data sampling
SGD
sample complexity

Abstract: Conventional machine learning applications typically assume that data samples are independently and identically distributed (i.i.d.). However, many practical scenarios naturally 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 to facilitate the convergence of SGD over highly dependent data using different popular update schemes. Specifically, with a $\phi$-mixing model that captures both exponential and polynomial decay of the data dependence over time, we show that SGD with periodic data-subsampling achieves an improved sample complexity over the standard SGD in the full spectrum of the $\phi$-mixing data dependence. Moreover, we show that by fully utilizing the data, mini-batch SGD can further substantially improve the sample complexity with highly dependent data. Numerical experiments validate our theory.  

Under review as a conference paper at ICLR 2022
HOW TO IMPROVE SAMPLE COMPLEXITY OF SGD OVER HIGHLY DEPENDENT DATA?
Anonymous authors Paper under double-blind review
ABSTRACT
Conventional machine learning applications typically assume that data samples are independently and identically distributed (i.i.d.). However, practical scenar- ios often involve data-generatinn samples, which are known to heavily bias the stochastic optimization process and slow down the convergence of learning, In this paper, conduct a fundamental study on how different structures of stochastic update schemes affect the sam- ple complexity of stochastic gradient descent (SGD) over highly dependent data. Specifically, with a d-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. Interest- ingly, 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.
process that produces highly dependent data
INTRODUCTION
Stochastic optimization algorithms have attracted great attention in the past decade due to its suc- cessful applications broad research areas, including deep learning (Goodfellow et al., 2016), re- inforcement 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.id.) 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 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, 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 al., 2018: Zou et al., 2019; Xu & Gu, 2020; Qu & Wierman, 2020), which requires the underlying Markov chain to 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 underlying Markov chain, which is a weaker condition than the uniform ergodic condition (Glynn & Meyn, 1996). Moreover, Agarwal & Duchi (2012) introduced a o-mixing property of the data- generating process that quantifies how fast the distribution of future data samples (conditioned fixed filtration) converges to the underlying stationary data distribution. In particular, the o-mixing property is general than the previous two notions of data dependence (Douc al., 2018).
solution to the Poisson equation associated with the

---

Under review as a conference paper at ICLR 2022
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 optimiza- tion process. In fact, under i.idd. 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, 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 batch sampling. Our results show that SGD with both stochastic updates achieves substantially improved sample complexity over the standard SGD under highly dependent data. We summarize our contributions as follows.
1.1
OUR CONTRIBUTIONS
We consider the following standard stochastic optimization problem.
min fww) := Eę=μ ((ww:))] wEW
(P)
where the objective function 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 eeta-generating process. Specifically, adopt the o-mixing model to quantify the data dependence via decaying mixing coefficient function Φe (k) (see Definition 2.2) (Agarwal & Duchi, 2012). We study the con- vergence of the stochastic gradient descent (SGD) algorithm over o-mixing dependent data samples under various stochastic update schemes, including data subsampling and mini-batch sampling.
We first study the convergence of SGD over 6-mixing dependent data samples under the data sub- sampling update scheme. In particular, the data subsampling update scheme utilizes only one data sample per consecutive data samples by periodically skipping 1 samples. With this data sub- sampling scheme, the subsampled data samples are less dependent for a larger subsampling period Consequently, we show that SGD with 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 b-mixing coefficient. In particular, the improvement is substantial when the data highly dependent with an algebraic decaying o-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 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 o-mixing coefficient. We summarize and compare the sample complexities of these stochastic algorithms under different ş-mmxxig data dependence models in Table 1.
1.2 RELATED WORK
Stochastic Algorithms over Dependent Data Steinwart & Christmann (2009) and Modha & Masry (1996) established the convergence analysis of online stochastic algorithms for streaming
2

---

Under review as a conference paper at ICLR 2022
Table I: Comparison of sample complexities of SGD, SGD with data subsampling and Mini-batch SGD under different levels of data dependence for achieving [(w) f(w") S 6. Note that 0 is parameter the convergence rate of the e-mixing coefficient.
Data dependence level
(k)
SGD
SGD w/ subsampling
Mini-batch SGD
Geometric d--mxxing
exp(-k"), 0>0
O(e (log ()))
O(e (lge
O(e
(Weakly dependent)
Fast algebraic é-mixing (Medium dependent)
k-
O(c-2-8)
O(c-2-b)
Ö(e-3)
021
Slow algebraic g-mixing (Highly dependent)
k- 0<o<
2(--2
((6-2-))
(
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- Godichon-Buggioni et al. (2021) provided the non-asy 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 studied in (Karimi al., 2019) by assuming the exis- tence 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, series of work studied the finite- time 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 al., 2021; Melo et al., 2008; Chen al., 2019; Xu Gu, 2020), fitted Q- iteration (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. these studies, the dependent Markovian samples are assumed to satisfy the geometric o-mixing property, which 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 on-
line convex optimization problem. Hazan (2017) has built the standard ((vT) regret bound for on- line 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-probabiin guaranteed regret bound for mini-batch SGD algorithm with considering the data dependence.
PROBLEM FORMULATION AND ASSUMPTIONS
In this section, introduce the problem formulation and some basic assumptions. Consider model with parameters w. For any data sample &, denote F(w; < E R as the sample loss of this data sample under the model w. In this paper, consider the following standard stochastic optimization problem that has broad applications in machine learning.
min f(w) := Eę~u [F(w;))) E)].
(P)
wEW
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(::E) is G-Lipschitz continuous over W, i.e., for all E W, [F(w: F(v: & Gllw vll.
2. Function f(:) is convex and bounded below, iee, f(w") = inf f(w) -x.
3

---

Under review as a conference paper at ICLR 2022
3. W is convex and compact with bounded diameter R, i.e., wew || - 2 R.
To solve this stochastic optimization problem, one often needs to query a set of data samples from the distribution μ 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 data- elaborate below.
generating process
Dependent data-generating process: We consider a stochastic process that generates a stream of data samples (2,, ). which are not necessarily independent. In particular, the stochastic process P has an underlying stationary distribution generation process, we introduce the following standard e-mixing model (Agarwal & Duchi, 2012), where we denote {Fitt as the canonical filtration generated by {Erh.
To quantify the dependence of the data
Definition 2.2 (ő-mixing process). Consider a stochastic process {Ee]: with a stationary distribution μ.. Let P(E++ E F(F,)) be the distribution of the (-+-h)-th sample conditioned on Fr, and denote drv as the total variation distance. Then, the process {Er,, is called d-mixing if the following mixing coefficient ob (-) converges to 0 as k tends to infinity.
0g (A)) = sup AEN.AEF.
2d (P(EL+ E (4),
Intuitively, the ş-mixing coefficient describes how fast the distribution of sample Êr+* converges to the stationary distribution when conditioned on the filtration F, as the time gap k: - oo. The ø- mixing process can be found many applications, which involve mixing coefficients that converge to zero at different convergence rates. Below we mention some popular examples.
Geometric o-mixing process. Such type of process has geometrically diminishing mixing coefficient, i.e., (e(k) S 6o exp(-ck") for some Φb, c, / > O. Examples include finite-state ergodic Markov chains and some aperiodic Harris-recurret Markov processes
(Modha & Masry, 1996; Agarwal & Duchi, 2012; Meyn & Tweedie, 2012);
Algebraic o-mixing process. Such a type of process has a polynomially diminishing mix- ing coefficient, i.e., (k) Φok- for some Φo. 0 0. Examples include large class of Metropolis- Hastons samplers (Jarner & Roberts, 2002) and some queuing systems (Agar- wal & Duchi, 2012).
CONVERGENCE OF SGD WITH SUBSAMPLING OVER DEPENDENT DATA
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 stan- dard SGD over dependent data established in (Agarwal & Duchi, 2012). In Section 3.2, establish convergence results of SGD with the data subsampling update.
Throughout, we define the sample complexity the total number of samples required for the algo- rithm to output model w that achieves an convergence error, i.e., f(w) f(w*) I c. Also, the standard regret of stochastic algorithm is defined
(Regret): RR Σ F(w(()):E) F()
where the models {wi, W2,..., Wn) are generated using the data samples {E1, Ez,.... {n), respec- tively, and w² is the minimizer of fww. For this sequence of models {w1, W2, ...; W,, }. we make the following mild assumption, which is satisfied by many SGD-type algorithms.
Assumption 3.1. There a non-increasing sequence {n(t)}e such that [[o(t [w(t+1)= w(t)ll S k(t).
3.1 STOCHASTIC GRADIENT DESCENT
Stochastic gradient descent (SGD) is a popular and classical algorithm for stochastic optimization. In every iteration t, SGD queries a sample & from the data-generating process and performs the following update.
(SGD): w(t + 1) w(t) Tp F()(())
4

---

Under review as a conference paper at ICLR 2022
where N7 is the learning rate. In Theorem 2 of (Agarwal & Duchi, 2012), the authors established high probability convergence error bound for generic class of stochastic algorithms. Specifically, under the Assumptions 2.1 and 3.1. they showed that for any N with probability at least - 6,
the averaged predictor i. == Ei= we(t) satisfies
Ri (T (T- Σ x(t))+ 1(T-I)GR n
2T T log ( (2)
f( - f(w")
2GR n
72
n
Here, R, is the regret of the algorithm of interest, and E N is an auxiliary parameter that is in- troduced to decouple the dependence of the data samples. From the above bound, one can see that the optimal choice of 7 depends on the convergence rate of the mixing coefficient (T()). Specifi- cally, consider the SGD algorithm in (1), It can be shown that it achieves the regret Ri, (vvn) and satisfies kt() = Ol1/Vi) with a proper diminishing learning rate. Consequently, the above high-probability convergence bound for SGD reduces
f(w,)) ((0)) S ( inf TEN
T
log
T
+
(3)
Vn
Such bound further implies the following sample complexity results of SGD under different con- vergence rates of the mixing coefficient Φ5.
Corollary 3.2. The sample complexity of SGD in (1) for achieving convergence error over 6-mixing dependent data is given as follows.
If the data is geometric d-mixing with parameter 0 >> 0, then we choose ((log 1) The resulting sample complexity in the order of -0e 1)
If the data is algebraic 6-mixing with parameter 0 > then we choose T O(E The resulting sample complexity is in the order of n ( 22-
It be seen that if the data-generating process has fast geometrically diminishing mixing co- efficient, i.c., 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 date-gengg 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 c- In particular, such factor is substantially large if the mixing rate parameter 0 is close to zero.
3.2 SGD WITH SUBSAMP
When apply SGD to solve stochastic optimization problems over dependent data, the key chal- lenge is that the data dependence introduces non-negligible bias that slows down the convergence of the algorithm. Hence, straightforward solution is to reduce data dependence before performing stochastic optimization. In the existing literature, simple and useful approach is data subsam- pling (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 E2,,E2,3. f..... }. Instead of utilizing the entire stream of data, we subsample a subset of this data stream with period N and obtain the following subsampled data stream
(Ei, 1..
In particular, let (Fe) be the canonical filtration generated by (hr+th Since the consecutive subsampled samples are r time steps away from each other, it is easy to verify that the subsampled data stream te is also ø-mixing process with mixing coefficient given by oT(() de (rt), where of denotes the mixing coefficient of the subsampled data stream {Er+ hr- Therefore, by periodically subsampling the data stream, the resulting subsampled process has faster-converging mixing coefficient. Then, we apply SGD over such subsampled data, i.c..
(SGD with subsampling):
w(t 1) w(t) 17. (((((()):
(4)
5

---

Under review as a conference paper at ICLR 2022
In partieular, the convergence error bound in eq. (2) still holds by replacing (e(r) with Øe (e(rT), and we obtain the following bound for SGD with subsampling.
f(ūw) f(w") S o Vn
inf
{
(-- V
(T
1 T 3 + (e(rr)))
(5)
Such a bound further implies the following sample complexity results of SGD with subsampling under different convergence rates of the mixing coefficient de.
Corollary 3.3. The sample complexity of SGD with subsampling in (4) for achieving an conver- gence error over Q-mixing dependent data is given as follows.
If the data is geometric d-mixing with parameter 0 > 0, then we choose T = ((log 4)b and (1). The resulting sample complexity is in the order of rm
(log !
* If the data is algebraic d-mixing with parameter 0 > 0, then we choose O b) and T == The resulting sample complexity is in the order of rn = O
Compare the above sample complexity results with those of the standard SGD in Corollary 3.2, conclude that data- data-subsampling can improve the sample complexity by factor of (log ) and e for geometric d-mixing and algebraic d-mixing data, respectively. Intuitively, this is because with data subsampling, we can choose a sufficiently large subsampling period to decouple the data dependence in the term &e (rT). as opposed to choosing a large T in Corollary 3.2. In this way, the order of the dominant term / 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.c., it only requires computing the stochastic gradients of the subsampled data, and therefore can substantially reduce the computation load.
CONVERGENCE OF MINI-BATCH SGD OVER DEPENDENT DATA
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 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 effec- tively reduce data dependence without skipping data samples, and can achieve an improved sample complexity over SGD with subsampling.
Specifically, we consider data stream { with ø-mixing dependent samples. We rearrange the data samples into a stream of mini-batches {æthe where each mini-batch Ty contains B samples, i.e., Ft- (E(e-1)B++1 ((-1))++2 {.B} Then, we perform mini-batch SGD update as follows.
(Mini-batch SGD): w(t + 1) = w(t)
th
Σ (t)(()) EEA:
(6)
B
Performing SGD updates with mini- 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;;)) == B Σςea F(w;; E) as the average loss on a mini-batch of samples. With a bit abuse of notation, we also define J. as the canonical filtration generated by the mini- batch samples {xz]e.
Lemma 4.1. Let Assumption 2.1 hold and consider the mini- batch data stream (1the Then, for any w, U E W measureable with regard to F, and any T E N. it holds that
B GR
B[F(w;IL+7)+ - ((u: [FF]] - (f(w) - f(v)) <
Σ
(
(7)
B
1=1
6

---

Under review as a conference paper at ICLR 2022
With dependent data, the above lemma shows that we approximate the population risk f(w) by the conditional expectation E(F(w;; ( which involves the sample Zt+r that is T steps ahead of the filtration Fr, Intuitively, by the o-mixing principle, Jt-r conditional on Ft gets closer to the stationary distribution μ.. In general, the estimation bias GR > é ( + 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.
gets larger, the distribution of
B
Σ i== (E(1) 0(1). Hence, the Geometric o-mixing: In this case, Σ (e(T
estimation bias is in the order of O
Fast algebraic o-mixing (0 2 1): In this case, Σ De (e Ei= 05 =1)) Hence, the estimation bias is in the order of
where hides all logarithm factors.
Slow algebraic d-mixing (0 < 0 1): In this case, Σ ( B (((B))-0))
Hence, the estimation bias is in the order of O -R-
8
can be seen that if the mixing coefficient converges fast, i... either geometrically or fast alge- braically, 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 effee- tively 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 T E N and any minimizer w" with probability at least 1 - 8, the averaged predictor wn := n Σr Et=1 w() satisfies
R
G(T-
R-741
GR(T - 1)
f((m) - f(w²) S
Σ
k(t)+
n
n
7
1
B
Φ +1) +
T nB
log
log 71 B i +
Σ )()) )())))))
(8)
nB
To further understand the order of the above bound, a standard regret analysis shows that mini-hatch
(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.
SGD achieves a regret in the order of 2t.. Õ(V - p()) x
and x(t) O(V B)
nB
[(wx) - -(ww((() -(w00s (1
+()) j=
R
GR(T
-
nB
B
B
1))
( + (T
B
Σ
(10)
nB
nB
Such 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 follows.
If the data is geometric d-mixing with parameter > 0, then we choose T = 1, B (1) O()-)). The overall sumple complexity is nB = O2)
If the data is fast algebraic d-mixing with parameter 0 > then we choose 1,B ( O()))). The overall sample complexity nB (
7

---

Under review as a conference paper at ICLR 2022
If the data is slow algebraic o-mixing with parameter 0 < 0 1, then we choose =(E=)). The overall sample complexity is nB =))
1, B = O ))
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 d-mixing convergence rate. Specifically. mini-batch SGI) improves the sample complexity over that of SGD with subsampling by a factor of O(loo 4)$ ((-=b) and O) for geometric d-mixing, fast algebraic é-mixing and slow algebraic e-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 reduce the bias caused by the data dependence and choose small auxiliary parame- ter = 1. As a comparison, to control the bias caused by data dependence, the standard SGD needs to choose a very large T and the SGD with subsampling needs to choose large subsampling period that skips huge amount of valuable data samples, especially when the mixing coefficient con- verges slowly. Therefore, our result proves that it is beneficial to use mini-bate stochastic gradient updates when the data samples are highly dependent.
We note that our proof of the tight -robabbbbybylity bound in Theorem 4.2 for mini- 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 X = f(w((t - 1)r + i)) - f(w") + F(w((t - 1)r + ():r))) - ((+r-)). As this random variable involves only one sample f++r-1, they bound the bias term X; [_ as a universal constant. As comparison, the random variable X; would involve a mini-batch of samples T++r-1 in our analysis. With the mini-batch structure, the bias - can be written as an average of B zero-mean dependent random vari- ables, 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 al., 2009) for dependent stochastic process to obtain an improved bias bound from O(1) ) to O(I//B). This is critical for obtaining the improved bound.
Second, with the improved high-rrobbbility 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 (x; F[(x))F-11)) as each bias term is no longer bounded with probability one. To address this issue, we developed a gen- eralized Azuma's '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 high-probability regret bound for mini-batch SGD over dependent data so that it can be integrated with the bigh-probability convergence bound in Theorem 4.2. To our best knowledge, the regret of SGD over dependent data has not been studied before.
NUMERICAL EXAMPLE
We examine our theory via basic convex quadratic optimization problem, which is written
min f(w) := Ee= [w - = AAw - - WERd
where A > O is fixed positive semi-definite matrix and f is the uniform distribution on [o, 1]d. Then, following the construction in (Jarner & Roberts, 2002), we generate an algebraic d-mixing Markov chain that has the stationary distribution μ.. In particular, its mixing coefficient (k) con- verges at sublinear convergence rate k 7, where r > 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 = 0a-
(Bias):
B (ww; I = 0.]] - f(w))
8

---

Under review as a conference paper at ICLR 2022
where the expectation is taken over the randomness of the mini-batch of samples queried time T E N. Such a bias is affected by several factors, including the time gap T, the batch size B and the convergence rate parameter 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 = 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 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 large batch size B 100 and set 1. This observation matches and justifies our theoretical results in Corollary 4.3.
Batch
100
0.75
bla
0.30
0.50
0.50
8-000
0.50
1-100
0.25
2-2
0.25
2-2
0.25
0.25
0.00
0.00
50
150
200
100
25
50
Figure 1: Impact of r, batch size B and convergence rate of mixing coefficient on the bias.
We further compare the convergence of SGD, SGD with sub- sampling and mini-batch SGD. Here, we set = 2 to generate highly dependent data samples. We set learning rate 77 = 0.01 for both SGD and SGD with subsampling, and set learning rate
0.25
0.20
Bell-batchh SGD
0.15
" 0.01 Σ -وー1 tg
0.01 100 for mini-batch SGD with
0.05
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 seen that SGD with subsampling achieves lower loss than the standard SGD asymptot- ically, 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.
batch size
2x10t 4x10" 6x10f BK30" 10K10" Number of Observations
Figure 2: Comparison of sam- ple complexity of different SGD algorithms.
CONCLUSION
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-batce 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.
REFERENCES
Alekh Agarwal and John Duchi. The generalization ability of online algorithms for dependent data. IEEE Transactions on Information Theory, 59(1):573-587, 2012.
Alckh Agarwal, Nan Jiang. Kakade Sham M. and Wen Sun. Reinforcement learning: Theory and algorithms. https///tthhorybook.kkk github.oo. 2021.

---

Under review as a conference paper at ICLR 2022
Léon Bottou. Large-scale machine learning with stochastic gradient descent. In Yves Lechevallier and Gilbert Saporta (eds.), Proc. COMPSTAT, pp. 177-186, 2010.
Zaiwei Chen, Sheng Zhang, Thinh Doan, John-Paul Clarke, and Siva Theja Maguluri. Finite- sample analysis nonlinear stochastic approximation with applications reinforcement learn- ing. arXiv: 1905. 1425, 2019.
Gal Dalal, Balázs Szörényi, Gugan Thoppe, and Shie Mannor. Finite sample analyses for td (0) with function approximation. In Proc. AAAI conference on artificial intelligence, 2018.
Vianney Debavelaere, Stanley Durrleman, and Stéphanie Allassonnière. On the convergence of stochastic approximations under a subgeometric ergodic Markov dynamie. Electronic Journal of Statistics, 15(1):1583 1609, 2021.
Bernard Delyon et al. Exponential inequalities for sums of weakly dependent variables. Electronic Journal of Probability, 14:752-779, 2009.
Randal Douc, Eric Moulines, Pierre Priouret, and Philippe Soulier. Markov chains. Springer, 2018.
John Duchi, Alekh Agarwal, Mikael Johansson, and Michael Jordan. Ergodic subgradient descent. In Allerton Conference, 2011.
Eyal Even-Dar, Yishay Mansour, and Peter Bartlett. Learning rates for q-learning. Journal of machine learning Research, 5(1), 2003.
Peter W. Glymn and Sean Meyn. Lyapunov bound for solutions of the Poisson equation. The Annals of Probability, 24(2):916 - 931, 1996.
Antoine Godichon- Godichon-Baggioni, Nicklas Werge, and Olivier Wintenherger. Non-asymptotic analysis of stochastic approximation algorithms for streaming data. arXiv:2109.07117, 2021.
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, 2016.
Elad Hazan. Introduction to Online Convex Optimization. Elad Hazan, Erscheinungsort nicht mittelbar, 2017. ISBN 1521133301.
Søren F Jarner and Gareth O Roberts. Polynomial convergence rates of markov chains. The Annals of Applied Probability, 12(1):224 247, 2002.
Maxim Kaledin, Eric Moulines, Alexey Naumov, Vladislav Tadic, and Hoi-To Wai. Finite time analysis of linear two-timescale stochastic approximation with markovian noise. In Conference on Learning Theory, pp. 2144-2200 PMLR, 2020.
Belhal Karimi, Blazej Miasojedow, Eric Moulines, and Hoi-To Wai. Non-asymptotic analysis of biased stochastic approximation scheme. Proc. Conference on Learning Theory, pp. 1944 1974, 2019.
Georgios Kotsalis, Guanghui Lan, and Tianjiao Li. Simple and optimal methods for stochastic variational inequalities, ii: Markovian noise and policy evaluation in reinforcement learning. HrXiv:2011.02990 11 2020.
Harshat Kumar, Alec Koppel, and Alejandro Ribeiro. On the sample complexity of actor-critic method for reinforcement learning with function approximation. ArX1v.1910.084122 2019.
Gen Li, Changxiao Cai, Yuxin Chen, Yuantao Gu, Yuting Wei, and Yuejic Chi. Tightening the depen- dence on horizon in the sample complexity of q-learning. In ICML, volume 139 Proceedings of Machine Learning Research, pp. 6296-6300 PMLR, 2021.
Kurt Marti. Stochastic optimization of regulators. Computers and Structures, 180:40-51, February 2017.
Francisco S Melo, Sean P Meyn, and M Isabel Ribeiro. An analysis of reinforcement learning with function approximation. In Proc. International Conference on Machine Learning, pp. 664-671, 2008.
10

---

Under review as a conference paper at ICLR 2022
Sean P Meyn and Richard L Tweedie. Markov chains and stochastic stability. Springer Science & Business Media, 2012.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wier- stra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv:1312.5602, 2013.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning, nature, 5 518(7540):529-533 2015.
Dharmendra Modha and Elias Masry. Minimum complexity regression estimation with weakly dependent observations. IEEE Transactions on Information Theory, 42(6))2133-21455 1996.
Dheeraj Nagaraj, Xian Wu, Guy Bresler, Prateek Jain, and Praneeth Netrapalli. Least squares re- gression with markovian data: Fundamental limits and algorithms. In Proc. Advances in Neural Information Processing Systems, volume 33, 2020.
Shuang Qiu, Zhuoran Yang, Jieping Ye, and Zhaoran Wang. On the finite-time convergence of actor- critic algorithm. In NeurlPS Optimization Foundations for Reinforcement Learning Workshop, 2019.
Guannan Qu and Adam Wierman. Finite-time analysis of asynchronous stochastic approximation and q-learning. In Proc. Conference on Learning Theory, pp. 3185-3205, 2020.
Ingo Steinwart and Andreas Christmann. Fast learning from non-iid observations. Advances in neural information processing systems, 12:1768-1776 2009.
Richard Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. Bradford, 2018.
Terence Tao, Van Vu, et al. Random matrices: universality local spectral statistics of non- hermitian matrices. Annals of probability, 43(2):782-874 2015.
Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods: Global optimality and rates of convergence. In International Conference on Learning Representations, 2019.
Yue Frank Wu, Weitong ZHANG, Pan Xu, and Quanquan Gu. finite-time analysis of two time-scale actor-critic methods. In Proc. Advances in Neural Information Processing Systems (NeurlPS), volume 33, pp. 17617-17628, 2020.
Lin Xiao. Dual averaging method for regularized stochastic learning and online optimization. Proc. Advances in Neural Information Processing Systems, 22:2116-22 122114 2009.
Pan Xu and Quanquan Gu. A finite-time analysis of q-learning with neural network function ap- proximation. In Proc. International Conference on Machine Learning, pp. 10555-10565, 2020.
Tengyu Xu, Shaofeng Zou, and Yingbin Liang. Two time-scale off-policy TD learning: Non- asymptotic analysis over Markovian samples. In Proc. Advances in Neural Information Processing Systems (NeurIPS), 2019.
Tengyu Xu, Zhe Wang, and Yingbin Liang. Improving sample complexity bounds for (natural) actor-critic algorithms. In Proc. Advances in Neural Information Processing Systems (NeurIPS). volume 33, 2020.
Zhuoran Yang. Yongxin Chen, Mingyi Hong, and Zhaoran Wang. Provably global convergence of actor-critic: A case for linear quadratic regulator with ergodic cost. In Proc. Advances in Neural Information Processing Systems (NeurIPS), 2019.
Shaofeng Zou, Tengyu Xu, and Yingbin Liang. Finite-sample analysis for SARSA with linear function approximation. In Proc. Advances in Neural Information Processing Systems, pp. 8665- 8675, 2019.

---

Under review as a conference paper at ICLR 2022
Appendix
Table of Contents
A Proof of Corollary 3.3
12
B Proof of Theorem 4.2
13
B.1 Key Lemmas
B.2 Proof of the Main Result
17
C Regret Analysis of Mini-Batch SGD
20
Experiment Setup
24
Notation:
To simplify the notation, throughout the appendix, we denote <(00 == E(t-1)844 which
corresponds to the i-th data sample of the t-th mini-batch data With this notation, we have
It (E(1) (22 (1))).
A PROOF OF COROLLARY 3.3
In this section, we analyze the convergence error bound of the SGD with data-subsampling in (4).
Given mixxingg data stream (21, 3, we consider the following subsampled data stream (fi,Er+1 E2r+1....
Let F. be the canonical filtration generated by { Then the subsampled data stream {Etr4 J is o with the mixing coefficient given by
(t = (rtr).
With this mixing coefficient, following convergence eтror bound for any T N.
apply Theorem 2 of (Agarwal & Duchi, 2012) and obtain the
R. 7
T
I log dee(TT)
f(w)) f(w)) <
x(1)
n
Consider the standard SGD with a diminishing learning rate, we have x(t) = 0 and R. O(yn). Then, the convergence error bound becomes
f(w,)) f( < o Vn
(2= inf TEN
(T (T-
vn + Vnn - log ,c(r7))))
n
The above result further implies the following sample complexity results for different convergence rates of the mixing coefficient.
Geometric o-mixing: In this case, (k) < O(exp(-k*) for some 0 0. Set the last term de (rT) = (e). We obtain that rr O(log 1)² Further set the second term T-1 Oee). We obtain that nt = -E 2). By choosing = O(1), the sample vn
complexity is in the order of
e-complexity = = =r-n=0((lo) 1 -) Pe =
Algebraic d-mixing: In this case, (k) < ( for some O. Set the last term
(b((r)) = Oce). We obtain that tr O ). Set the second term _=1 O(e). We obtain that = ( By setting - = (1). the sample complexity is in the order of e-complexity
O - 3 -66---1)
12

---

Under review as a conference paper at ICLR 2022
B PROOF OF THEOREM 4.2
B. 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 follow- ing lemma is generalization of the Lemma in (Agarwal & Duchi, 2012).
Lemma B.1. Let w. v be measurable with respect to Ft. Then for any E N,
GR B B
E F(W F(u:0++))))) Fi &
+ f(e) f(c).
Proof. For any N, we consider the following decomposition.
E (( F F(1:
E (WW x++7) f(w) + f(v) F(u; + s(w) ((v)
B
Flw; (2) (f7 E e11F)) - f F(w; E)du)
Σ
B
Flu: CdPP) E .FF) -
/ =(r;
+ (w) - ((v).
We can further bound the term (A) using the mixing property of the dependent data stream.
F(w; Fl (aP E -FFi) / F(w:;
(l. E -F..). / F(o:z)du)
(A)
B
B
B
(F(w; ((P E dgFF)) - m(dE))
B
1=1
B
GRd|P(CE4 E dc(FF) m(dE)
B
i=1
GR
Be(TB + +),
B
where in the first inequality we the facts that F(:E) is G-Lipschitz and the domain is bounded by R. and the second inequality is implied by the d-mixing property. Substitting the above upper bound of (A) into the previous equation yields that
GR
[[F(w; F(1 Fd
(T( f(o).
This completes the proof.
Proposition B.2. Let {w(t))eN be the model parameter sequence generated by (6). Also suppose that Assumption 3.1 holds. Then for any N, have
(f(w(t))- f(w")]
Σ [[w(()) - F(w(()3 + :(4r=) f(w")) []]"]] + R. + G(T - 1) m-++1
Σ 1=1l
<(1) + GRGT -
13

---

Under review as a conference paper at ICLR 2022
Proof. For any N. we consider the following decomposition,
Ii((w(t)) - f(w")]
Σif(w(()) F(w((); ((4))))))))-------0000-00))))))- f(w") + F(w(():((+r-1) F( ;a---1)
[f(((t)) F(w((); + F F(w"; f(w")]
(11)
((((()=44t-1))- - (/o(::::rn-)--/(:::-
(B)
We will keep the first term and bound the term (B).
(B)
F(w(())a47-11)- F(W";xe4r1
Σ F(w(t); - Fow*:
((w(())247-11 - F(w(t + T 1);
(Bi)
(B2)
-+
F(w(f);a))+ +
F F(w ;rt) -
Σ
1=++1
(Bs)
Recall that the term (Bi) is the regret R., We can bound the term (B2) by noting that
F(w((); - F(w(l 7 + 1); S Gl + 1) w(!)l
G
|| w + w(t + +)]
T-2
$ G
<(t + i)
G(T 1)s(t).
For the term (Bz), we can bound it using the G-Lipschitzness of F(::E) and the R-bounded domain.
Σ F(w(t):x;) +
Σ F(w ;x,) Σ
n
Σ
F(w(t):24+-1)--
Σ f(w::000 ((4
(wx(t): xx)
Σ F(w):z))
(=n- 1+2
1=
<
G
[[w( -01l-w1ll +
Σ
[l(() w01l
1=n-742
t=1
<
GR( 1).
14

---

Under review as a conference paper at ICLR 2022
Combining the above bounds of (B1), (B2), and (By), obtain the upper bound of (B) as follows.
=(+(1)=++-11) F(w"; :0447-1))
((w(()) F(w"; +
( F(w(t + - - x1++-1)]
(B1)
(Ba)
n+--1
F(w(();++rr-)
Σ
F(w(();z)) + Σ
F(w" ;24)
Σ
Faw";
t=1
(=n+1
(Bs)
n-++1
S Rr G 1)
Σ
x(t) + GR((
Then the proof 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 of martingale difference random variables.
Lemma B.3 (Generalized Azuma's Inequality). Let (X,) be martingale difference sequence with respect to its canonical filtration F. Define Y Σ X and assume E co. Then for any {arh > 0,
12
T
IP I - EY
X
Σ at
S 2eep
(
+
Σ t=1
P([x 2 at).
Proof.
Let 9 = min(t: |Xel > ar). Then the sets B, = {w (W) = f} are disjoint. Construct
C
Y(w) if (ULL B1
Y'(w):
B|] if E B, for all E 21, .T..
By the above construction, the associated Doob martingale of y' with respect to F is (Z: EAA X.). It satisfies the conditions of Azuma's inequality, i.c.
(Z:) forms martingale with respect to F (because the stopped martingale is still mar- tingale).
Z 7 I at.
Then apply Azuma's inequality to Y"
12
P
Y
EY
2
Σ
of
<
2 exp
(-2
15

---

Under review as a conference paper at ICLR 2022
Now we can bound P
2
AV
E
ož as follows.
T Σ at
Y EY
2
T
T
Y EY 2 A
Σ
2
Y = Y
+P
Y EY 2 X
Σ t=1
a Y
X
1=1
YY
EY 2
+P 48)
1 2
2epp
2 at).
Then the proof is completed. Here we notice the fact that IEY" = EY by our construction.
The following lemma is taken from (22), Theorem 4 of (Delyon al., 2009).
Lemma B.4 (Bersttein's Incquality for Dependent Process). Let {Zi} be centered adaptive pro- cess with respect to F. Define the following quantities.
| ~0
||[ 207
[2
Zn 2i]l
sup Isisn
|| 1l.0
Then, holds that
t²
P
Z,
2) S exp
2(v 2q) + 26m/3
Application of Lemma B.4 to proof. Here make some comments about how 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 Section B.2.
X [w((t 1)r + 1)) f(w") F(w";; (3174111
We also define the filtration Fi := Forti-1 for simplicity. Then, we have
B[X;|F[-1]] = (w((t - 1)T + 1)) - (w) + : F(u((1 - 1)7 + 1); 1);
Then, the bias can be rewritten as
X - E[X|FFL1]
- -E[Fww" =F(w" ( - F(w((t 1)7 + 1); - Fw"" ; F(w((t- 1)T + 1): x6r45-1))Fi
EE
where Y is defined as
(E) F(w": - F Fw(((t 1)7 1): E[F(w":)) - F(w((t 1)r + +))5))=1111
16

---

Under review as a conference paper at ICLR 2022
More specifically, we have
1 B Σ ri( = B (((
x - EXX
ÇEFir+i-1
Recall that F is the canonical filtration generated from the data stream (12). Moreover, (1 1.2,.., is centered and adaptive with respect to this filtration. Then we can evalu- ate the quantities q, U, and in Lemma B.4 follows.
Bounding m is simple. By Assumption 2.1 we have | (1) s 2GR.
The above bound of m leads to simple bound for e, i.e. S 2nG nt2
The quantity q can be bounded as follows.
a
Σ
F(( 1 co
q =
2GR
1 tr+t-1lll
2GR
EE (S br+--1l - BE V (7
(R)
j=1
k-1
S 4G
be (k:
k=1 i=1
s 4G R2n Σ (b)))
Then, by applying Lemma B.4, we obtain the following high-probabilityy bound.
B²1²
- - 2 1) < 2exp
2(c 2q) 2Btmm/3
/3
B212
< 2 exp
()) +GG
Bi²
2exp
2(2G2 8G
B -==
(
Simplifying yields that
P - 2exp (-c+ GRR (-c+
Bta
16G R$ Σ (1))
where C= R2
B.2 PROOF OF THE MAIN RESULT
Recall that we are considering data stream divided into small mini-batches. For convenience, we re-label the data stream {E1, E2, fa....} } as follows to explicitly indicate its mini-batch index.
(1 (2) (B)
((B)
(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, denote the data in the specified mini-batch For example,
17

---

Under review as a conference paper at ICLR 2022
2i, represent the I-th mini-batch (4 (0 1. (11)). data stream as
Then we can re-writhe the above
02, 03.
We denote the canonical filtration generated by the above sequence as F. Note that have the following relation:
==
In summary, when we analyze the mini-batch SGD dynamics, we use the filtration F, and when need to consider intra-batch samples, we use the filtration F.
Theorem B.5. Let (w(t))eN be the model parameter sequence generated by (6). Suppose Assump- tions 2.1 and 3.1 hold. Then, for any т E N, with probability at least - 6, we have
Σ (ww(()) f(w")]
B (T +i)
<GR n
B 1ml
+
2nn
2 GR
log
4n
4 RRR
(log
4n
ह + +4G2R2
16G R2 Σ
og (c( log
4n
log
47
4n log
B 3 B
8
9 B
8
8
R-T+1
+ R. + -
- 1)
Σ
ktt) + GR(T -
In particular, ifT = 1, then
Σ ((w((() f(w))]
RR, + GR n Σ
( +
B
2n
2
GR
4n
4 G2R2
4n o
4n
47
4n
+
log
(log
+ (4G 16G R2
Σ
dr (i)) log
log
log
3
B
9
8
Proof. From Proposition B.2, we obtain the following bound.
[sw((()) f(w")]
n-T+1 <(t) GR(T 1).
Σ [f(w(t)) F(w((t; + Fl=": 244--1) [w=)]} Ri + G
To complete the proof, it suffices to bound the first term; we define this term
On = Σ (f(w(()) - (()(() + F(w"; 2147-1) - f(w*)).
We apply the same decomposition as the (13) of (Agarwal & Duchi, 2012). Define the index set I(i) as (1...., | + 1) for i < n ---n== and (1...., # otherwise. Then we have
2n Σ
Σ
x B
B[x:FLL tEZ
Σ
1=1 (EI(6)
18

---

Under review as a conference paper at ICLR 2022
where
x fwo((t 1)7 + 1)) f(ww) F( ( F(w((t 1)T + 1); 2tr+s-1).
Note that by Lemma 4.1, have that B[X;| F- - GR Σ (T B i). Then, we have
nGR
P Zn
de(T
P
[ E[ >>) 7)
B
1=1 (s)
Σ TE
x - E[X 2))
xxt - -[X 7) (EZ
Define :=
:= E1ETT - - E[ and a = /
Notice that x; - -[ is a centered
random variable, that is, B[X; E[X;)iLill O. Then by the generalized Azuma's inequality (Lemma B.3), we conclude that
2
P Y 2 S 2 exx
P( - E[ 2 a).
272
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
A
P - - 2 a) S 2exp
C + 160 R22 E 6e(1))
VB
where C = R2 In summary, the concentration bound for 7,, is
p(Z, GR " B be(TB+o)+))
Σ
< 2T exp
+ T
p(
2
2r2 o2
1=1
?2
X2
2 2r exp
+ 22
2rn
A= B
C+ 1
GR VB
+ 16G H2 E
de (i)
Then, let 6 exp
C+ L +160 R Dn de(t))
)
and we obtain that
2
X² = ==
4
GR VB
A
+ 16G R2
Σ Ei(
B
4n log
1=1
It is quadratic function of A. Solving it yields that
X
2GR 3 B
4n log
4 G
log )
2 + (C+ 16 (6+16GRR²
> (1)
B
log
4n
(13)
9 B
Also, let 5 = 2r exp
y2 2nn x
we have that
3
2 4T
72
2nn log
B
8
Substituting (13) into the above equation, we obtain that
7
27n
2 GR
log
4n
+
AGR2
R
log
4n +
(c
(C+16G2 R6 Σ (c(1)
log
4n
log
4r
log
4n
B
B
8
9 B
8
19

---

Under review as a conference paper at ICLR 2022
Then, conclude that with probability at least - 8,
Σ 1=1
((w((() [(w")]
<GR
De (T +
B
1=1
2nn
2 G2R
4n
4 R
log ) (4G2R² +6G Σ (3(1)
B
4n
4T
4n
+
log
+
log
llog
log
B
3 B
8
9 B
8
8
1-++1
+ R. G(T 1)
Rit) GR(T 1).
(14)
The desired result follows by noting that Ei=1s(10() 2 nf(w)).
C REGRET ANALYSIS OF MINI-BATCH SGD
In this section, we derive the regret bound of mini-batch SGD algorithm. Throughout, for each sam- ple loss F(w; {), recall that its gradient /VF(w; EI is uniformly bounded by G (see Assumption 2.1). In particular, we assume the k-th coordinate of FF {) is uniformly bounded by Gs. and we have G = V G
Gradient Variance Bound under Dependent Data
In the i.i.d setting, the variance of stochastic gradient decreases as the batch size increases. Specifi- cally, we have
B Σ E VF(W;
20 vf(w) B
VF(W: -f B
1
Therefore, El E VF(w; Vf(w)]=== However, this bound no longer holds B the data samples are dependent. In the following lemma, develop similar result when the data collected from a dependent stochastic process. Recall that FF(n((t); denotes the averaged gradient over the mini-batch Iı, i.e.,
VF(W(():))) = B
Σ F(w(();
Lemma C.1. Let (w(t))eN be the model parameter sequence generated by the mini-batch SGD in (6). Let Assumptions 2.1 and 3.1 hold. Then, with probability least 1 8,
[VF((()) - ((((())) 268
log
E (e()) de(i)
G + 256G
pc(i)
8
+ 2G2
B
B
Proof. Let I = " 1==1 be the t-th mini-bateh samples. We consider the filtration within 2, and denote it as (. Then, by the definition of canonical filtration,
X : VF(w((;;)))
is measurable with respect to 200 Define
Y == (Xi - E[
where (.)x denotes the k-th entry of the specified vector. And it is easy to see that {Y,,) ) is centered process for any (1,2..... d). With these construction, start from the following
20

---

Under review as a conference paper at ICLR 2022
decomposition.
[VF(u(t); - vf(((t))]
- - -11-:///-///0000000--00--------- 11
2 (F(((();))) - (VV - ((((())
(A)
(B)
Then we will bound the term (A) and (B), respectively.
Bounding (A): Note that
B
VF(w(t): - -)VE
=
B
X;
-
B
E(x,([F-1))4] 2
Σ
(X;
B
k=
i=1
Σ
Σ
YE
B
Then, we show that the process (Yi, satisfies the conditions of Lemma B.4.
Since E E[Y,,
= O, we conclude that { [Y a centered process.
o
Denote the k-th entry of X; as X2 We know that X & Ga- Hence, we conclude that 0 < (Y S 2G Then, we set b, 2G for all i.
o Lastly, we can bound the quantity q defined in Lemma B.4 as follows.
B 1-1
2G 3
Σ
JE S.A. ( F
+
3
1=
B
Hcli -1) 4 G +
S 4G Σ
Σ
3
J=1
< 4G B Σ
x C.B.
de( +
Now, we can apply Lemma B.4 and obtain that
X² 2 S exp (- IH 128G Σラ ve(1)
IP Σ Vi En
With a union bound, we obtain that
P Σ Yo. > 2) 2xxp
2 134 G34GBB+ + 128G 25(i)
33
Further applying the union bound over k= 1,2,,..... d, obtain that
Ü
Σ
Y2
x2] 2 Σ exp
X 134 G.B 128 B 8 E (c(1))
Let 7 = 2exp
we obtain that
-Tg 1280 , 2(()
134
2d log
\/
G.B + 128G B Σ eE(
8
21

---

Under review as a conference paper at ICLR 2022
Then conclude that,
n 1
d
134 G
128G
Σ
(c(1)
log 201 2 8.
5=1
It implies that with the probability at least 1 --
Σ Y =
134 G + 128B
Σ
Σ G
log
2d
3
8
By definition, G= v Ex probability at least
Finally, we have the following bound for term (A): with
8,
134
B
log 2d
- -VF))=)))))-((( <
G
128G
Σ pc(())
5
3
B
1=1
Bounding (B): Note that
( V[(w(t))| -1 |l / VF(w(():&{ DaP(! e-IFi-1) - VF(w(():))x(()
$ (VF((((t:) e-1Fi-1) dpl
$ G
Then bound the norm by triangle incquality,
[IVF((()) v 1 Σ [B( (f(F))
B
G
(1).
Finally, we obtain the bound for the term (B) as
EEande(1) de(1)
EVFF(w()) { G²
B
Combing the bounds (A) and (B) yields that with probability at least
[VF(w((;:)) v((((())) <
268 G² + 256 2
Σ
de (i)
log
+ 2G
Σi=l de(i)
B
B
1=1
High-Probability Regret Bound
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(:E): W + 1. is convex.
2. The objective functioonn W TP. is I-smooth.
22

---

Under review as a conference paper at ICLR 2022
Theorem C.3 Hligh-probability regret bound). Let {w(t)hex 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 8.
[1) ='l
268 1/T (13
2d7 log
11 Σ
2
Ri 5
+
G² + 256G
Σ
+ 2G2
211
B
B
1=1
+ 2 Σ (f(w(tt) f(w")).
Moreover, let rl - O(
). the optimized upper bound is in the order of
T- pc(5)
B T.
Ej= j=1
$E(J)
T
My = =
1T
Σ
-(ww))
B
t=1
Proof. For convenience, we define = 1 E V VF(w(();<))) (()). obtain that
By the algorithm update (6), we
2 w(t) w²) - [|w(t) - 1 - -l + 1) - w1 + nl9
17
[[t(t) w
11 1|2 w| + 1) - 101 w11
+ 2n|
Summing the above inequality over yields that
2 (gc wt) w²) 1=1
Iw(11 w01 ||w(T + 1) 11 + 2n
11 vf(((t))) 4nL (f(((t))- -
By convexity of the function, we further obtain that
2 2 (F(w(t); - F(w";[[w)) xx)) < [[w(1) "I? t=1
1lg. vf(w(t))]l + 4nL > (f(w(t)) f(w)))
+ 2m
1=1
t=1
Then, we apply Lemma C. to bound the second term Σ || union bound on over We conclude that, with probability least
V](((()) and then apply
Σ
(F(((t)) ((w);x)))
1=1
[[
11
[( [(260 G² 256G
268
B
log 2dT
E de(i) 2
+ o/T
2e (j)
+ 20
2m
B
B
j=1
2nL Σ (((w()))((w))
The proof is completed. Lastly, we set the learning rate 1). To minimize the obtained upper bound, 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( w0 112
[(
268 G² + 256G Σ <b(i))
log 2dr
EE= (e((i) B
1/f'
20
21
23

---

Under review as a conference paper at ICLR 2022
Then, is chosen
100(1) - =2113/2
T.
268 G2 + 256G2 Σ1=1 (E(1)
log 241
+ 2G
Lim
15
B
(v
B
o
T >g 4c(1)
D EXPERIMENT SETUP
Recall that we consider the following convex quadratic optimization problem:
min Ee (w E) A( <),
WERd
where A is fixed positive semi-definite matrix and j the uniform distribution on [0, 1] The data stream admitting such stationary distribution μ can be generated by certain Metropolis -aattins sampler provided in (Jarnr & Roberts, 2002). Specifically, is described follows.
Step 1: Let the "proposal" distribution (1x) have the density of Beta(r 1, 1); that is,
((x) = (r + 1)x"
[0,
0
$ [0, 1]
Define the acceptance probability axx, v) = min { q(=) ((g) 1}.
Step 2: If the current state εt, then we sample Ç ~ q. Define the next state Ex+1:
{ Er w.p. 1 - a(E,,))
E++1 = =L w.p. ().
Step 3: Go back to Step to generate the next state.
We repeatedly generate d independent sequences starting from the same initial state sp 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 oe (l) s O(k-1/r) in Proposition 5.2, (Jamnr & Roberts, 2002).
We consider the following bias term at the fixed point = 0
(Bias): [[F x;) = 0z] fw)).
It can be used to approximate the left-hand side of Lemma 4.1. Since E (f;; 0.] cannot be explicitly obtained, we use Monte Carlo method to estimate this conditional expectation. That 10, 000 independent trajectories starting from 2o Oz. At the step т, estimate the expected value as 1 > F(w; where x 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.
is, generate
24


Reviews:
[{"review_id": "sza0p_EktTG", "reviewer": "Reviewer_PELk", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper proves that the subsampling method can reduce the samples complexity of SGD when data are dependent. \n\nThis paper has some merits.\n\n1. Compared with existing works [1,2], the paper considers more general mixing time, that is, algebraic mixing time (fast and slow). The authors prove that under the algebraic mixing time case,   data-subsampling can improve the   sample complexity more efficient than the \ngeometric case.\n\n2. Due to the subsampling, the authors prove a more general regret result in Theorem 4.2.\n\nHowever, some weaknesses hurt this paper.\n\n1. The contribution is incremental due to existing works [1,2]. This paper does not present any novel method or solve theoretical problems. The subsampling method has been presented in [1,2]. And they also show how the samples are reduced by the subsampling method. The only novel part is about the proof in geometric case but is very easy by following existing proofs in [1,2].\n\n2. While the regret for data-dependent SGD is given in [3,4]. Although subsampling modifies the traditional sampling method. The proof is easy if we use the techniques from [3,4].\n\n\nMinor comments:\n[3] has been published in SIAM J. Optimization. The journal version contains more details. I suggest the authors update the reference in the future version.\n\n[1] Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms.\n[2] SIMPLE AND OPTIMAL METHODS FOR STOCHASTIC VARIATIONAL INEQUALITIES, II: MARKOVIAN NOISE AND POLICY EVALUATION IN REINFORCEMENT LEARNING \n[3] Ergodic subgradient descent.\n[4] The generalization ability of online algorithms for dependent data\n", "summary_of_the_paper": "This paper proves the subsampling method can reduce the samples complexity of SGD on dependent data when the mixing time follows more general distributions.", "summary_of_the_review": "Due to existing works in this area, I do not think the current version of this paper is beyond the publication bar.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "iG97scjLo99", "reviewer": "Reviewer_xaGe", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Convergence results\nThe paper is clearly written and provides a good summary of the existing work. It also elucidates many real-world examples, which motivate the setting of dependent noise structure in stochastic optimization. However, I feel that the paper doesn't have many new results and is unable to generalize existing results sufficiently. \n\nUntil section 3.2 no new result has been presented. And the result with sub-sampling in section 3.2 is a trivial extension of the existing high probability guarantee by Agrawal and Duchi. I agree that the current writing makes it very clear what the contribution of this paper is, but I feel like it is redundant and not appropriate for a 9-page submission. It would have made much more sense for the paper to actually focus on the new techniques developed for proving results for MB-SGD. These details are currently buried in the appendix, and only briefly mentioned at the end of section 4. Having said that, the convergence result for MB-SGD is novel, and the discussion leading up to it gives a good intuition for why mini-batching would reduce the bias.\n\n## Assumptions\n\nI am also concerned about the lipschitzness assumption in 2.1.1. This essentially implies a bounded stochastic gradient condition, which is not even satisfied for simple losses such as least squares. In fact, it is not even satisfied for the instantaneous loss in the experiments of this paper. It would have been a significant improvement if the results of Agrawal and Duchi were extended to smooth functions with bounded variance (at the optimal), which would cover a much larger class of functions. \n\n## Experiments\n\nThe experiments could have been done much more extensively as well. The paper mentions how different applications in reinforcement learning, etc. actually satisfy different $\\phi$-mixing assumptions. It would have been interesting to see some experiments on real-world data which elucidated this. Moreover, it seems in the current formulation only the global losses need to be convex and the instantaneous losses can be non-convex. I wonder if that opens avenues for more interesting experiments as well. In the current figure 2, the colors, as well as the scaling, are really bad. \n\n***\nOverall, I believe the fundamental question which the paper asks, \n> How does the structure of stochastic updates affect the convergence rate and sample complexity of stochastic algorithms over-dependent data? \n\nis very interesting. But the paper makes very small steps towards answering this satisfactorily. \n\n", "summary_of_the_paper": "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. \n\nOn 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. \n\nIn 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.", "summary_of_the_review": "I think the paper is well written, clear, and has technical novelty. However, there aren't enough new results, to justify acceptance. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "LSDuAj4W3oX", "reviewer": "Reviewer_RcE4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n\nAnalyzes minibatch SGD for phi-mixing data. \n\nWeakness:\n\nSince this is a theoretical paper I am basing my impression of the paper on its theoretical novelty.\n\nThe result related to periodically subsampled SGD is a minor modification of Theorem 2 of (Agarwal & Duchi, 2012). There is no novelty here. \n\nThe result related to minibatch SGD: For the proof of Theorem 4.2 there are three main components: Lemma 4.1,  applying Bernstein's inequality for phi-mixing, generalized Azuma's inequality to deal with the bias. Lemma 4.1  almost follows immediately from the definition of $\\phi$-mixing coefficients. The Bernstein's inequality for dependent sequence was obtained in Deylon et. al. 2009 and so it's not a contribution of this paper. The authors claim that they generalize Proposition 34 of Tao et.al. 2015 to get the generalized Azuma's inequality. It is not clear to me in which aspect it is generalized from Tao. If the authors could point out how it is more general that would be great. ", "summary_of_the_paper": "This work analyzes and provides high probability convergence guarantee for periodically subsampled and minibatch SGD for optimization of convex and Lipschitz continuous function when the data stream is $\\phi$-mixing.", "summary_of_the_review": "Overall, there is almost no theoretical novelty. So I am voting for reject. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "KaFF2hIJgoU", "reviewer": "Reviewer_J2CF", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength-\n\n* The analysis of SGD over dependent data, modeled by phi-mixing process, provides interesting insights on the performance of SGD for dependent data: the proposed framework provides theoretical evidence of how the convergence of SGD in the data-dependent setting is affected by the structure of the stochastic update scheme. \n\n* The paper is well-organized and the message is clearly conveyed: this paper clearly conveys the message of why mini-bath SGD and SGD with subsampling can provide better convergence rate compared to SGD for dependent data based on the concrete analysis of sample complexity. Also, both theoretical result and empirical result demonstrate that the bias of SGD decreases as the subsampling period r and bath size B increases, respectively. \n\n* Technical novelty compared to (Agarwal&Duchi 2012) is well summarized in the end of Sec. 4, even though the main framework to analyze the dependency structure, phi-mixing model, as well as the analysis for original SGD (Section 3.1) are directly addressed from (Agarwal&Duchi 2012).\n\n\nWeakness-\n\n* Tightness of the bound: Since the provided bounds are only upper bounds, it will be more interesting if the authors can provide any arguments or analysis about the tightness of the bounds, or lower bounds on sample complexity. \n\n* Empirical results: it will be interesting to compare the empirical convergence rate of variants of SGD with the theoretical bounds provided by the authors to see the tightness of the bounds in non-asymptotic regime. \n", "summary_of_the_paper": "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. ", "summary_of_the_review": "This paper provides a concrete framework to analyze the convergence rate of SGD over dependent data. By addressing the phi-mixing process to model the dependent data, the convergence rate of variants of SGD are compared and the benefits of mini-batch SGD over SGD for dependent data are clearly demonstrated from the analysis. This paper includes interesting insights and the addressed framework will be helpful to analyze SGD for other stochastic optimization problems using dependent data. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Dear Authors,

This paper eventually received mostly negative reviews (scores 5, 3, 5), with one mildly positive review (score 6). All reviews were particularly informative, offering detailed and expert feedback. I was hoping for author engagement, but unfortunately, no rebuttal was submitted. 

In general, the reviewers and me found the paper well written, on a timely topic, but of a very limited theoretical novelty. Well-articulated details of this can be found in the reviews and I would recommend the authors to consider them carefully in their revision. I have no option but to reject this work. 

The main reason for rejection in this case is therefore limited theoretical novelty. However, this is a solid paper that is of publishable quality, albeit perhaps in a somehow lesser venue, at least in its current form. 

Kind regards,

Area Chair
Decision: Reject