mlsanityData to 14 Oct 2026

Constrained Stochastic Nonconvex Optimization with State-dependent Markov Data

arXiv 2206.11346 ↗First posted 22 Jun 2022math.OC cs.LG stat.MLcited by 6

Not on the map. Why?

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.

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

36 of 68 references.

References · 36

  1. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
  2. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 307
  3. 2015Strategic Classificationcited by 257
  4. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 229
  5. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 166
  6. 2020Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learningcited by 96
  7. 2020Stochastic Optimization for Performative Predictioncited by 93
  8. 2015On the Global Linear Convergence of Frank-Wolfe Optimization Variantscited by 77
  9. 2020Stochastic optimization with decision-dependent distributionscited by 65
  10. 2018On Markov Chain Gradient Descentcited by 63
  11. 2018A Single Time-Scale Stochastic Approximation Method for Nested Stochastic Optimizationcited by 53
  12. 2020Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noisecited by 53
24 more
  1. 2018Stochastic Conditional Gradient Methods: From Convex Minimization to Submodular Maximizationcited by 47
  2. 2019Non-asymptotic Analysis of Biased Stochastic Approximation Schemecited by 45
  3. 2016Stochastic Frank-Wolfe Methods for Nonconvex Optimizationcited by 41
  4. 2016Variance-Reduced and Projection-Free Stochastic Optimizationcited by 40
  5. 2021Statistical Inference with M-Estimators on Adaptively Collected Datacited by 40
  6. 2021State Dependent Performative Prediction with Stochastic Approximationcited by 39
  7. 2022Adapting to Mixing Time in Stochastic Optimization with Markovian Datacited by 36
  8. 2019One Sample Stochastic Frank-Wolfecited by 32
  9. 2019Two Time-scale Off-Policy TD Learning: Non-asymptotic Analysis over Markovian Samplescited by 31
  10. 2014Optimum Statistical Estimation with Strategic Data Sourcescited by 28
  11. 2021On the Stability of Random Matrix Product with Markovian Noise: Application to Linear Stochastic Approximation and TD Learningcited by 23
  12. 2017Asymptotic Bias of Stochastic Gradient Searchcited by 19
  13. 2018Autoregressive Models for Matrix-Valued Time Seriescited by 18
  14. 2021On Empirical Risk Minimization with Dependent and Heavy-Tailed Datacited by 16
  15. 2020Convergence Rates of Accelerated Markov Gradient Descent with Applications in Reinforcement Learningcited by 15
  16. 2020Non-asymptotic Convergence of Adam-type Reinforcement Learning Algorithms under Markovian Samplingcited by 15
  17. 2013Conditional Gradient Algorithms for Norm-Regularized Smooth Convex Optimizationcited by 13
  18. 2019Learning from weakly dependent data under Dobrushin's conditioncited by 13
  19. 2015Linearly Convergent Away-Step Conditional Gradient for Non-strongly Convex Functionscited by 12
  20. 2017Non-convex Conditional Gradient Slidingcited by 12
  21. 2022A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimizationcited by 8
  22. 2018Improved Complexities of Conditional Gradient-Type Methods with Applications to Robust Matrix Recovery Problemscited by 6
  23. 2018Markov Chain Block Coordinate Descentcited by 4
  24. 2021Sample Average Approximation for Stochastic Optimization with Dependent Data: Performance Guarantees and Tractabilitycited by 2

Built on by

Cited by year

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

6 papers.

  1. 2023Online covariance estimation for stochastic gradient descent under Markovian samplingcited by 7
  2. 2024Stochastic Approximation with Biased MCMC for Expectation Maximizationcited by 5
  3. 2024Stochastic Optimization Algorithms for Instrumental Variable Regression with Streaming Datacited by 4
  4. 2024Stochastic Gradient Descent with Adaptive Datacited by 2
  5. 2025Achieve Performatively Optimal Policy for Performative Reinforcement Learningcited by 2
  6. 2023Markov Chain Mirror Descent On Data Federationcited by 1