mlsanityData to 14 Oct 2026

Data Sampling Affects the Complexity of Online SGD over Dependent Data

arXiv 2204.00006 ↗First posted 31 Mar 2022cs.LG math.OCcited by 5

Not on the map. Why?

Abstract (arXiv)

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 stochastic data sampling schemes affect the sample complexity of online stochastic gradient descent (SGD) over highly dependent data. Specifically, with a φ-mixing model of data dependence, we show that online SGD with proper periodic data-subsampling achieves an improved sample complexity over the standard online SGD in the full spectrum of the data dependence level. Interestingly, even subsampling a subset of data samples can accelerate the convergence of online SGD over highly dependent data. Moreover, we show that online SGD with mini-batch sampling can further substantially improve the sample complexity over online SGD with periodic data-subsampling over highly dependent data. Numerical experiments validate our theoretical results.

Key facts. Cited by 5 papers in the map (data through 14 Oct 2026). Builds on 15 of its 42 references that are in the map. First posted on arXiv 31 Mar 2022.

Builds on

15 of 42 references.

References · 15

  1. 2013Playing Atari with Deep Reinforcement Learningcited by 3,274
  2. 2019Introduction to Online Convex Optimizationcited by 803
  3. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 159
  4. 2020A Finite Time Analysis of Two Time-Scale Actor Critic Methodscited by 122
  5. 2020Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learningcited by 96
  6. 2019Finite-Sample Analysis for SARSA with Linear Function Approximationcited by 85
  7. 2019Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learningcited by 67
  8. 2020Least Squares Regression with Markovian Data: Fundamental Limits and Algorithmscited by 56
  9. 2019On the Sample Complexity of Actor-Critic Method for Reinforcement Learning with Function Approximationcited by 54
  10. 2020Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noisecited by 53
  11. 2019A Finite-Time Analysis of Q-Learning with Neural Network Function Approximationcited by 47
  12. 2019Non-asymptotic Analysis of Biased Stochastic Approximation Schemecited by 45
3 more
  1. 2019Two Time-scale Off-Policy TD Learning: Non-asymptotic Analysis over Markovian Samplescited by 31
  2. 2020Simple and optimal methods for stochastic variational inequalities, II: Markovian noise and policy evaluation in reinforcement learningcited by 23
  3. 2021Non-Asymptotic Analysis of Stochastic Approximation Algorithms for Streaming Datacited by 5

Built on by

Cited by year

Citing papers per year: 2022: 1; 2023: 3; 2024: 0; 2025: 1.

5 papers.

  1. 2023Streaming PCA for Markovian Datacited by 9
  2. 2023Statistical Inference with Stochastic Gradient Methods under φ-mixing Datacited by 7
  3. 2023Online covariance estimation for stochastic gradient descent under Markovian samplingcited by 7
  4. 2022Learning from time-dependent streaming data with online stochastic algorithmscited by 2
  5. 2025On the Optimal Construction of Unbiased Gradient Estimators for Zeroth-Order Optimizationcited by 2