# Constrained Stochastic Nonconvex Optimization with State-dependent Markov Data

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 68 references that are in the map.
- First posted on arXiv 22 Jun 2022.

## Builds on (most cited first, 30 of 36)

- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [Strategic Classification](https://mlsanity.com/paper/1506.06980/) (2015)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learning](https://mlsanity.com/paper/2002.00260/) (2020)
- [Stochastic Optimization for Performative Prediction](https://mlsanity.com/paper/2006.06887/) (2020)
- [On the Global Linear Convergence of Frank-Wolfe Optimization Variants](https://mlsanity.com/paper/1511.05932/) (2015)
- [Stochastic optimization with decision-dependent distributions](https://mlsanity.com/paper/2011.11173/) (2020)
- [On Markov Chain Gradient Descent](https://mlsanity.com/paper/1809.04216/) (2018)
- [A Single Time-Scale Stochastic Approximation Method for Nested Stochastic Optimization](https://mlsanity.com/paper/1812.01094/) (2018)
- [Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise](https://mlsanity.com/paper/2002.01268/) (2020)
- [Stochastic Conditional Gradient Methods: From Convex Minimization to Submodular Maximization](https://mlsanity.com/paper/1804.09554/) (2018)
- [Non-asymptotic Analysis of Biased Stochastic Approximation Scheme](https://mlsanity.com/paper/1902.00629/) (2019)
- [Stochastic Frank-Wolfe Methods for Nonconvex Optimization](https://mlsanity.com/paper/1607.08254/) (2016)
- [Variance-Reduced and Projection-Free Stochastic Optimization](https://mlsanity.com/paper/1602.02101/) (2016)
- [Statistical Inference with M-Estimators on Adaptively Collected Data](https://mlsanity.com/paper/2104.14074/) (2021)
- [State Dependent Performative Prediction with Stochastic Approximation](https://mlsanity.com/paper/2110.00800/) (2021)
- [Adapting to Mixing Time in Stochastic Optimization with Markovian Data](https://mlsanity.com/paper/2202.04428/) (2022)
- [One Sample Stochastic Frank-Wolfe](https://mlsanity.com/paper/1910.04322/) (2019)
- [Two Time-scale Off-Policy TD Learning: Non-asymptotic Analysis over Markovian Samples](https://mlsanity.com/paper/1909.11907/) (2019)
- [Optimum Statistical Estimation with Strategic Data Sources](https://mlsanity.com/paper/1408.2539/) (2014)
- [On the Stability of Random Matrix Product with Markovian Noise: Application to Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/2102.00185/) (2021)
- [Asymptotic Bias of Stochastic Gradient Search](https://mlsanity.com/paper/1709.00291/) (2017)
- [Autoregressive Models for Matrix-Valued Time Series](https://mlsanity.com/paper/1812.08916/) (2018)
- [On Empirical Risk Minimization with Dependent and Heavy-Tailed Data](https://mlsanity.com/paper/2109.02224/) (2021)
- [Convergence Rates of Accelerated Markov Gradient Descent with Applications in Reinforcement Learning](https://mlsanity.com/paper/2002.02873/) (2020)
- [Non-asymptotic Convergence of Adam-type Reinforcement Learning Algorithms under Markovian Sampling](https://mlsanity.com/paper/2002.06286/) (2020)
- [Conditional Gradient Algorithms for Norm-Regularized Smooth Convex Optimization](https://mlsanity.com/paper/1302.2325/) (2013)
- [Learning from weakly dependent data under Dobrushin's condition](https://mlsanity.com/paper/1906.09247/) (2019)

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

- [Online covariance estimation for stochastic gradient descent under Markovian sampling](https://mlsanity.com/paper/2308.01481/) (2023)
- [Stochastic Approximation with Biased MCMC for Expectation Maximization](https://mlsanity.com/paper/2402.17870/) (2024)
- [Stochastic Optimization Algorithms for Instrumental Variable Regression with Streaming Data](https://mlsanity.com/paper/2405.19463/) (2024)
- [Stochastic Gradient Descent with Adaptive Data](https://mlsanity.com/paper/2410.01195/) (2024)
- [Achieve Performatively Optimal Policy for Performative Reinforcement Learning](https://mlsanity.com/paper/2510.04430/) (2025)
- [Markov Chain Mirror Descent On Data Federation](https://mlsanity.com/paper/2309.14775/) (2023)

## Abstract (arXiv)

We study stochastic optimization algorithms for constrained nonconvex stochastic optimization problems with Markovian data. In particular, we focus on the case when the transition kernel of the Markov chain is state-dependent. Such stochastic optimization problems arise in various machine learning problems including strategic classification and reinforcement learning. For this problem, we study both projection-based and projection-free algorithms. In both cases, we establish that the number of calls to the stochastic first-order oracle to obtain an appropriately defined ε-stationary point is of the order O(1/ε2.5). In the projection-free setting we additionally establish that the number of calls to the linear minimization oracle is of order O(1/ε5.5). We also empirically demonstrate the performance of our algorithm on the problem of strategic classification with neural networks.