Research map / Optimization / Optimizers
Accelerating Distributed Stochastic Optimization via Self-Repellent Random Walks
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.
Replaces the i.i.d. or Markovian token in distributed stochastic approximation with a self-repellent random walk (SRRW) and proves a.s. convergence and CLTs showing the optimization error's asymptotic variance decreases at rate O(1/alpha^2) in the slow-timescale case.
Problem
Distributed stochastic optimization with token algorithms driven by Markov chains: standard random walks sample gradients suboptimally, and finite-time bounds don't capture the effect of the walk on asymptotic efficiency.
Approach
Drive the token with a generalized non-linear self-repellent random walk (SRRW) built on a time-reversible base chain, analyze the coupled SA-SRRW system via a CLT (including two-timescale controlled Markov noise), and show that the asymptotic covariance of optimization error shrinks as alpha grows, faster than the sampling covariance.
Key results
- Under case (i) (beta_n = o(gamma_n)), the asymptotic covariance V^(1)_theta(alpha) decreases to zero in Loewner order at rate O(1/alpha^2), faster than the O(1/alpha) decay of the sampling covariance.
- Simulations on wikiVote with ijcnn1 show curves for alpha >= 5 outperform the i.i.d. sampling baseline for SGD-SRRW and SHB-SRRW, averaged over 100 runs.
- For case (iii), the asymptotic covariance equals that of the base Markov chain for all alpha, so SRRW gives no asymptotic benefit there.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SRRW with increasing α and βₙ = o(γₙ) (case i), instead of the base Markov chain | SA-SRRW · Distributed stochastic optimization | asymptotic covariance of optimization error: O(1/α²) | Helped |
| Use case i instead of case iii (γₙ = o(βₙ)) | SA-SRRW · Distributed stochastic optimization | asymptotic covariance of optimization error | Helped |
| Use SRRW with γₙ = o(βₙ) (case iii), instead of the base Markov chain | SA-SRRW · Distributed stochastic optimization | asymptotic covariance of optimization error | No clear effect |
| Use SRRW with α ≥ 5 instead of i.i.d. sampling | SGD-SRRW and SHB-SRRW · wikiVote graph, ijcnn1 | MSE | Helped |
| Use case i instead of cases ii and iii at identical α | SGD-SRRW and SHB-SRRW · wikiVote graph, ijcnn1 | MSE | Helped |
| Increase α in case i | SGD-SRRW · Dolphins graph, ijcnn1, n = 10^7 | MSE: O(1/α²) | Helped |
| Increase α in the SRRW sampling process | SRRW weighted empirical measure · Target-distribution sampling | asymptotic sampling covariance: O(1/α) | Helped |
Surprising findings
- The asymptotic optimization-error variance can fall below that of i.i.d. sampling for large alpha, even under graph constraints.
- Case (iii) (faster-timescale iterates) gives no asymptotic benefit from SRRW, performing worse than case (i).
Limitations
- Case (iii) analysis requires a stronger assumption (A3') and yields no benefit from SRRW.
- Results are asymptotic; finite-time bounds are not provided because the SRRW mean-field is only locally Lipschitz.
- Empirical validation is limited to a logistic-regression-type problem and small graphs.
Experimental setup
Datasets: ijcnn1 (LIBSVM) wikiVote graph Dolphins graph
Benchmarks: ijcnn1 binary classification with L2 regularization
Metrics: mean squared error of SA iterates
Baselines: i.i.d. sampling SGD Metropolis-Hastings random walk (MHRW) driven SGD SHB with MHRW
Builds on: Self-Repellent Random Walk Metropolis-Hastings random walk stochastic heavy ball
Closest papers by meaning
- Improved Lower Bounds for First-order Stochastic Non-convex Optimization under Markov Sampling (ICML 2025 · similarity 0.88)
- Stochastic Optimization with Arbitrary Recurrent Data Sampling (ICML 2024 · similarity 0.88)
- Beyond Self-Repellent Kernels: History-Driven Target Towards Efficient Nonlinear MCMC on General Graphs (ICML 2025 · similarity 0.87)
- Faster Stochastic Optimization with Arbitrary Delays via Adaptive Asynchronous Mini-Batching (ICML 2025 · similarity 0.87)
- Rescaled Asynchronous SGD: Optimal Distributed Optimization under Data and System Heterogeneity (NeurIPS 2026 · similarity 0.87)
- Double Stochasticity Gazes Faster: Snap-Shot Decentralized Stochastic Gradient Tracking Methods (ICML 2024 · similarity 0.86)
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.