mlsanityData to 7 Oct 2026

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

arXiv 2203.15797 ↗First posted 29 Mar 2022math.OC cs.LG stat.MLcited by 7

Not on the map. Why?

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.

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

Builds on

22 of 43 references.

References · 22

  1. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 225
  2. 2018AdaGrad stepsizes: Sharp convergence over nonconvex landscapescited by 182
  3. 2018Stochastic model-based minimization of weakly convex functionscited by 157
  4. 2018On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizescited by 155
  5. 2013Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimizationcited by 142
  6. 2018Stochastic subgradient method converges on tame functionscited by 120
  7. 2018On Markov Chain Gradient Descentcited by 63
  8. 2014Global convergence of the Heavy-ball method for convex optimizationcited by 60
  9. 2016Error bounds, quadratic growth, and linear convergence of proximal methodscited by 59
  10. 2016Efficiency of minimizing compositions of convex functions and smooth mapscited by 59
  11. 2020Least Squares Regression with Markovian Data: Fundamental Limits and Algorithmscited by 56
  12. 2019Non-asymptotic Analysis of Biased Stochastic Approximation Schemecited by 45
10 more
  1. 2017Online to Offline Conversions, Universality and Adaptive Minibatch Sizescited by 39
  2. 2022Adapting to Mixing Time in Stochastic Optimization with Markovian Datacited by 35
  3. 2020Convergence of a Stochastic Gradient Method with Momentum for Non-Smooth Non-Convex Optimizationcited by 32
  4. 2013Stochastic Majorization-Minimization Algorithms for Large-Scale Optimizationcited by 28
  5. 2017Asymptotic Bias of Stochastic Gradient Searchcited by 19
  6. 2019Online matrix factorization for Markovian data and applications to Network Dictionary Learningcited by 8
  7. 2018Markov Chain Block Coordinate Descentcited by 4
  8. 2019Sampling random graph homomorphisms and applications to network data analysiscited by 4
  9. 2016Online Nonnegative Matrix Factorization with General Divergencescited by 2
  10. 2021Sample Average Approximation for Stochastic Optimization with Dependent Data: Performance Guarantees and Tractabilitycited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 3; 2025: 1; 2026: 3.

7 papers.

  1. 2024Stochastic Approximation with Biased MCMC for Expectation Maximizationcited by 5
  2. 2024Non-asymptotic Analysis of Biased Adaptive Stochastic Approximationcited by 4
  3. 2026A unified convergence theory for adaptive first-order methods in the nonconvex case, including AdaNorm, full and diagonal AdaGrad and Muoncited by 2
  4. 2024Stochastic optimization with arbitrary recurrent data samplingcited by 0
  5. 2025Quantitative Convergence Analysis of Projected Stochastic Gradient Descent for Non-Convex Losses via the Goldstein Subdifferentialcited by 0
  6. 2026Variance-Reduced Conditional Gradient Methods under Markovian Sampling for Nonconvex Composite Optimizationcited by 0
  7. 2026Retraction-Based Gradient Projection Algorithms on Manifoldscited by 0