mlsanityData to 7 Oct 2026

Stochastic optimization with arbitrary recurrent data sampling

arXiv 2401.07694 ↗First posted 15 Jan 2024math.OC cs.LG stat.MLcited by 0

Not on the map. Why?

Abstract (arXiv)

For obtaining optimal first-order convergence guarantee for stochastic optimization, it is necessary to use a recurrent data sampling algorithm that samples every data point with sufficient frequency. Most commonly used data sampling algorithms (e.g., i.i.d., MCMC, random reshuffling) are indeed recurrent under mild assumptions. In this work, we show that for a particular class of stochastic optimization algorithms, we do not need any other property (e.g., independence, exponential mixing, and reshuffling) than recurrence in data sampling algorithms to guarantee the optimal rate of first-order convergence. Namely, using regularized versions of Minimization by Incremental Surrogate Optimization (MISO), we show that for non-convex and possibly non-smooth objective functions, the expected optimality gap converges at an optimal rate O(n-1/2) under general recurrent sampling schemes. Furthermore, the implied constant depends explicitly on the `speed of recurrence', measured by the expected amount of time to visit a given data point either averaged (`target time') or supremized (`hitting time') over the current location. We demonstrate theoretically and empirically that convergence can be accelerated by selecting sampling algorithms that cover the data set most effectively. We discuss applications of our general framework to decentralized optimization and distributed non-negative matrix factorization.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 37 of its 64 references that are in the map. First posted on arXiv 15 Jan 2024.

Builds on

37 of 64 references.

References · 37

  1. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  2. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 225
  3. 2013Minimizing Finite Sums with the Stochastic Average Gradientcited by 164
  4. 2018Stochastic model-based minimization of weakly convex functionscited by 157
  5. 2013Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithmcited by 132
  6. 2020Random Reshuffling: Simple Analysis with Vast Improvementscited by 112
  7. 2015Why Random Reshuffling Beats Stochastic Gradient Descentcited by 78
  8. 2018On Markov Chain Gradient Descentcited by 63
  9. 2020Least Squares Regression with Markovian Data: Fundamental Limits and Algorithmscited by 56
  10. 2019Non-asymptotic Analysis of Biased Stochastic Approximation Schemecited by 45
  11. 2015Incremental Gradient, Subgradient, and Proximal Methods for Convex Optimization: A Surveycited by 44
  12. 2023Stochastic Gradient Descent under Markovian Sampling Schemescited by 37
25 more
  1. 2014Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learningcited by 35
  2. 2021Proximal and Federated Random Reshufflingcited by 33
  3. 2018Walkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimizationcited by 30
  4. 2013Stochastic Majorization-Minimization Algorithms for Large-Scale Optimizationcited by 28
  5. 2022Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizescited by 28
  6. 2021Random Reshuffling with Variance Reduction: New Analysis and Better Ratescited by 19
  7. 2022FedShuffle: Recipes for Better Use of Local Work in Federated Learningcited by 19
  8. 2022GraB: Finding Provably Better Data Permutations than Random Reshufflingcited by 18
  9. 2021Permutation-Based SGD: Is Random Optimal?cited by 16
  10. 2022Characterizing & Finding Good Data Orderings for Fast Convergence of Sequential Gradient Methodscited by 15
  11. 2022Stability and Generalization for Markov Chain Stochastic Gradient Methodscited by 14
  12. 2023First Order Methods with Markovian Noise: from Acceleration to Variational Inequalitiescited by 14
  13. 2021Improved Analysis and Rates for Variance Reduction under Without-replacement Sampling Orderscited by 13
  14. 2021Imbalanced Adversarial Training with Reweightingcited by 11
  15. 2020Block majorization-minimization with diminishing radius for constrained nonsmooth nonconvex optimizationcited by 9
  16. 2019Online matrix factorization for Markovian data and applications to Network Dictionary Learningcited by 8
  17. 2021Random-reshuffled SARAH does not need a full gradient computationscited by 7
  18. 2022Convergence of First-Order Methods for Constrained Nonconvex Optimization with Dependent Datacited by 7
  19. 2023Online covariance estimation for stochastic gradient descent under Markovian samplingcited by 7
  20. 2015Non-Uniform Stochastic Average Gradient Method for Training Conditional Random Fieldscited by 6
  21. 2019MISO is Making a Comeback With Better Proofs and Ratescited by 5
  22. 2020Online nonnegative CP-dictionary learning for Markovian datacited by 3
  23. 2022Stochastic regularized majorization-minimization with weakly convex and multi-convex surrogatescited by 2
  24. 2023Complexity of Block Coordinate Descent with Proximal Regularization and Applications to Wasserstein CP-dictionary Learningcited by 2
  25. 2023Doubly Robust Instance-Reweighted Adversarial Trainingcited by 2

Built on by

Not cited yet.