Research map / Optimization / Nonconvex and smooth optimization
Stochastic Optimization with Arbitrary Recurrent Data Sampling
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that regularized MISO (RMISO) with incremental majorizing surrogates attains O(n^{-1/2}) nonconvex stationarity rates under arbitrary recurrent data sampling, with constants depending on target time and hitting time.
Problem
Stochastic optimization of non-convex, possibly non-smooth weighted finite-sum objectives with convex constraints when the data sampling sequence is arbitrary, not i.i.d. or Markovian; prior first-order guarantees required independence, mixing, or reshuffling.
Approach
Extends MISO with a proximal (or diminishing-radius) regularization on the iterate step so that only recurrence of the sampling process (bounded expected return time) is needed; convergence constants depend on the target time t_odot (averaged) rather than the worst-case hitting time, achieving O(n^{-1/2}) rates.
Key results
- Constant proximal regularization achieves min E[O_f(theta_n)] = O(N^{-1/2}) depending on target time t_odot, improving on SAG's hitting-time dependence under Markovian sampling.
- RMISO outperforms ONMF and is competitive with AdaGrad on distributed NMF over MNIST under both random walk and cyclic sampling; cyclic sampling performs dramatically better than random walk.
- On the lonely graph, RMISO-DPR and MCSAG degrade as hitting time grows, while RMISO-CPR, RMISO-DR and MISO are unchanged since they depend only on t_odot.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use cyclic sampling instead of random-walk sampling | RMISO on MNIST distributed NMF · MNIST distributed NMF | reconstruction error | Helped |
| Use RMISO instead of ONMF | distributed NMF · MNIST distributed NMF | reconstruction error | Helped |
| Use RMISO instead of AdaGrad | distributed NMF · MNIST distributed NMF | reconstruction error | Mixed |
| Change from a complete graph to the lonely graph | RMISO-DPR · a9a logistic regression | test objective loss | Hurt |
| Change from a complete graph to the lonely graph | RMISO-CPR · a9a logistic regression | test objective loss | No clear effect |
| Change from a complete graph to the lonely graph | RMISO-DR · a9a logistic regression | test objective loss | No clear effect |
| Change from a complete graph to the lonely graph | MISO · a9a logistic regression | test objective loss | No clear effect |
| Add constant proximal regularization | MISO · a9a logistic regression | test objective loss | Mixed |
| Use SGD-HB or AdaGrad instead of RMISO | optimization on a9a · a9a logistic regression | trajectory stability | Hurt |
| Add dynamic proximal regularization (ablation) | RMISO · general recurrent sampling | expected optimality gap: O(n^{-1/2}) | Helped |
| Use diminishing radius restriction (ablation) | RMISO · general recurrent sampling | expected optimality gap: O(n^{-1/2}\log n) | Mixed |
| Add proximal regularization to strongly convex surrogates (ablation) | MISO · general recurrent sampling | dependence of convergence rate on recurrence | Helped |
Surprising findings
- Under cyclic sampling and uniform weights, the averaged target time t_odot equals (|V|-1)/2, so the rate can be better than i.i.d. sampling's |V| constant.
- AdaGrad and SGD-HB converge quickly but have unstable trajectories compared to RMISO.
Limitations
- Asymptotic almost-sure convergence is proven only for the diminishing-radius variant; constant and dynamic regularization variants have weaker asymptotic guarantees.
- Dynamic proximal regularization depends on hitting time t_hit, not just target time.
- Experiments are limited to NMF and logistic regression on small graphs.
Experimental setup
Datasets: MNIST a9a
Benchmarks: MNIST NMF reconstruction error a9a logistic regression test loss
Metrics: reconstruction error objective loss on test data expected optimality gap / stationarity measure
Baselines: MISO AdaGrad ONMF MCSAG SGD Adam SGD-HB
Builds on: MISO SAG stochastic majorization-minimization
Closest papers by meaning
- Faster Stochastic Optimization with Arbitrary Delays via Adaptive Asynchronous Mini-Batching (ICML 2025 · similarity 0.88)
- Accelerating Distributed Stochastic Optimization via Self-Repellent Random Walks (ICLR 2024 · similarity 0.88)
- An Online Adaptive Sampling Algorithm for Stochastic Difference-of-convex Optimization with Time-varying Distributions (ICML 2025 · similarity 0.88)
- The Sample Complexity of Gradient Descent in Stochastic Convex Optimization (NeurIPS 2024 · similarity 0.87)
- Improved Lower Bounds for First-order Stochastic Non-convex Optimization under Markov Sampling (ICML 2025 · similarity 0.87)
- Stochastic Optimization with Random Search (NeurIPS 2026 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.