# Convergence of First-Order Methods for Constrained Nonconvex Optimization with Dependent Data

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 43 references that are in the map.
- First posted on arXiv 29 Mar 2022.

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

- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [AdaGrad stepsizes: Sharp convergence over nonconvex landscapes](https://mlsanity.com/paper/1806.01811/) (2018)
- [Stochastic model-based minimization of weakly convex functions](https://mlsanity.com/paper/1803.06523/) (2018)
- [On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes](https://mlsanity.com/paper/1805.08114/) (2018)
- [Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimization](https://mlsanity.com/paper/1308.6594/) (2013)
- [Stochastic subgradient method converges on tame functions](https://mlsanity.com/paper/1804.07795/) (2018)
- [On Markov Chain Gradient Descent](https://mlsanity.com/paper/1809.04216/) (2018)
- [Global convergence of the Heavy-ball method for convex optimization](https://mlsanity.com/paper/1412.7457/) (2014)
- [Error bounds, quadratic growth, and linear convergence of proximal methods](https://mlsanity.com/paper/1602.06661/) (2016)
- [Efficiency of minimizing compositions of convex functions and smooth maps](https://mlsanity.com/paper/1605.00125/) (2016)
- [Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms](https://mlsanity.com/paper/2006.08916/) (2020)
- [Non-asymptotic Analysis of Biased Stochastic Approximation Scheme](https://mlsanity.com/paper/1902.00629/) (2019)
- [Online to Offline Conversions, Universality and Adaptive Minibatch Sizes](https://mlsanity.com/paper/1705.10499/) (2017)
- [Adapting to Mixing Time in Stochastic Optimization with Markovian Data](https://mlsanity.com/paper/2202.04428/) (2022)
- [Convergence of a Stochastic Gradient Method with Momentum for Non-Smooth Non-Convex Optimization](https://mlsanity.com/paper/2002.05466/) (2020)
- [Stochastic Majorization-Minimization Algorithms for Large-Scale Optimization](https://mlsanity.com/paper/1306.4650/) (2013)
- [Asymptotic Bias of Stochastic Gradient Search](https://mlsanity.com/paper/1709.00291/) (2017)
- [Online matrix factorization for Markovian data and applications to Network Dictionary Learning](https://mlsanity.com/paper/1911.01931/) (2019)
- [Markov Chain Block Coordinate Descent](https://mlsanity.com/paper/1811.08990/) (2018)
- [Sampling random graph homomorphisms and applications to network data analysis](https://mlsanity.com/paper/1910.09483/) (2019)
- [Online Nonnegative Matrix Factorization with General Divergences](https://mlsanity.com/paper/1608.00075/) (2016)
- [Sample Average Approximation for Stochastic Optimization with Dependent Data: Performance Guarantees and Tractability](https://mlsanity.com/paper/2112.05368/) (2021)

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

- [Non-asymptotic Analysis of Biased Adaptive Stochastic Approximation](https://mlsanity.com/paper/2402.02857/) (2024)
- [Stochastic Approximation with Biased MCMC for Expectation Maximization](https://mlsanity.com/paper/2402.17870/) (2024)
- [A unified convergence theory for adaptive first-order methods in the nonconvex case, including AdaNorm, full and diagonal AdaGrad and Muon](https://mlsanity.com/paper/2604.17423/) (2026)
- [Stochastic optimization with arbitrary recurrent data sampling](https://mlsanity.com/paper/2401.07694/) (2024)
- [Quantitative Convergence Analysis of Projected Stochastic Gradient Descent for Non-Convex Losses via the Goldstein Subdifferential](https://mlsanity.com/paper/2510.02735/) (2025)
- [Variance-Reduced Conditional Gradient Methods under Markovian Sampling for Nonconvex Composite Optimization](https://mlsanity.com/paper/2607.25785/) (2026)
- [Retraction-Based Gradient Projection Algorithms on Manifolds](https://mlsanity.com/paper/2609.30885/) (2026)

## Abstract (arXiv)

We focus on analyzing the classical stochastic projected gradient methods under a general dependent data sampling scheme for constrained smooth nonconvex optimization. We show the worst-case rate of convergence tildeO(t-1/4) and complexity tildeO(varepsilon-4) for achieving an varepsilon-near stationary point in terms of the norm of the gradient of Moreau envelope and gradient mapping. While classical convergence guarantee requires i.i.d. data sampling from the target distribution, we only require a mild mixing condition of the conditional distribution, which holds for a wide class of Markov chain sampling algorithms. This improves the existing complexity for the constrained smooth nonconvex optimization with dependent data from tildeO(varepsilon-8) to tildeO(varepsilon-4) with a significantly simpler analysis. We illustrate the generality of our approach by deriving convergence results with dependent data for stochastic proximal gradient methods, adaptive stochastic gradient algorithm AdaGrad and stochastic gradient algorithm with heavy ball momentum. As an application, we obtain first online nonnegative matrix factorization algorithms for dependent data based on stochastic projected gradient methods with adaptive step sizes and optimal rate of convergence.