# Stochastic Gradient Descent with Adaptive Data

arXiv: https://arxiv.org/abs/2410.01195 · HTML: https://mlsanity.com/paper/2410.01195/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 13 of its 53 references that are in the map.
- First posted on arXiv 2 Oct 2024.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 13 of 13)

- [Monte Carlo Gradient Estimation in Machine Learning](https://mlsanity.com/paper/1906.10652/) (2019)
- [Neural Policy Gradient Methods: Global Optimality and Rates of Convergence](https://mlsanity.com/paper/1909.01150/) (2019)
- [On the Convergence Rates of Policy Gradient Methods](https://mlsanity.com/paper/2201.07443/) (2022)
- [A general sample complexity analysis of vanilla policy gradient](https://mlsanity.com/paper/2107.11433/) (2021)
- [On Markov Chain Gradient Descent](https://mlsanity.com/paper/1809.04216/) (2018)
- [Non-asymptotic Analysis of Biased Stochastic Approximation Scheme](https://mlsanity.com/paper/1902.00629/) (2019)
- [State Dependent Performative Prediction with Stochastic Approximation](https://mlsanity.com/paper/2110.00800/) (2021)
- [Switchback Experiments under Geometric Mixing](https://mlsanity.com/paper/2209.00197/) (2022)
- [Non-asymptotic Convergence of Adam-type Reinforcement Learning Algorithms under Markovian Sampling](https://mlsanity.com/paper/2002.06286/) (2020)
- [Adaptive Experimental Design with Temporal Interference: A Maximum Likelihood Approach](https://mlsanity.com/paper/2006.05591/) (2020)
- [Improving Sample Complexity Bounds for (Natural) Actor-Critic Algorithms](https://mlsanity.com/paper/2004.12956/) (2020)
- [Constrained Stochastic Nonconvex Optimization with State-dependent Markov Data](https://mlsanity.com/paper/2206.11346/) (2022)
- [Convergence and Inference of Stream SGD, with Applications to Queueing Systems and Inventory Control](https://mlsanity.com/paper/2309.09545/) (2023)

## Built on by (most cited first, 2 of 2)

- [Latent Autoencoder Ensemble Kalman Filter for Nonlinear Data assimilation](https://mlsanity.com/paper/2603.06752/) (2026)
- [Optimal low-rank stochastic gradient estimation for LLM training](https://mlsanity.com/paper/2603.20632/) (2026)

## Abstract (arXiv)

Stochastic gradient descent (SGD) is a powerful optimization technique that is particularly useful in online learning scenarios. Its convergence analysis is relatively well understood under the assumption that the data samples are independent and identically distributed (iid). However, applying SGD to policy optimization problems in operations research involves a distinct challenge: the policy changes the environment and thereby affects the data used to update the policy. The adaptively generated data stream involves samples that are non-stationary, no longer independent from each other, and affected by previous decisions. The influence of previous decisions on the data generated introduces bias in the gradient estimate, which presents a potential source of instability for online learning not present in the iid case. In this paper, we introduce simple criteria for the adaptively generated data stream to guarantee the convergence of SGD. We show that the convergence speed of SGD with adaptive data is largely similar to the classical iid setting, as long as the mixing time of the policy-induced dynamics is factored in. Our Lyapunov-function analysis allows one to translate existing stability analysis of stochastic systems studied in operations research into convergence rates for SGD, and we demonstrate this for queueing and inventory management problems. We also showcase how our result can be applied to study the sample complexity of an actor-critic policy gradient algorithm.