A Note on Stability in Asynchronous Stochastic Approximation without Communication Delays

• URL: http://arxiv.org/abs/2312.15091v2
• Date: Tue, 13 Aug 2024 23:17:57 GMT
• Title: A Note on Stability in Asynchronous Stochastic Approximation without Communication Delays
• Abstract summary: We study asynchronous approximation algorithms without communication delays. Our main contribution is a stability proof for these algorithms. We discuss their application in important average-reward reinforcement learning problems.
• Score: 11.868402302316131
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we study asynchronous stochastic approximation algorithms without communication delays. Our main contribution is a stability proof for these algorithms that extends a method of Borkar and Meyn by accommodating more general noise conditions. We also derive convergence results from this stability result and discuss their application in important average-reward reinforcement learning problems.

Related papers

• Algorithmic stability via ensembling [4.404496835736175]
  Algorithmic stability refers to the property of an algorithm being insensitive to perturbations of the input data.<n>We develop a general framework to quantify the extent to which any ensembling strategy defined via averaging can yield stability guarantees for any type of data perturbation.
  arXiv  Detail & Related papers  (2026-09-09T16:39:35Z)
• Robust $Q$-learning for mean-field control under Wasserstein uncertainty in common noise [5.5004369279667396]
  We present a robust $Q$-learning algorithm for discrete-time mean-field control problems under Wasserstein uncertainty in the common noise law.<n>We establish its convergence together with finite-time iteration bounds for both synchronous and asynchronous learning schemes.
  arXiv  Detail & Related papers  (2026-06-18T15:20:00Z)
• Stabilizing Recurrent Dynamics for Test-Time Scalable Latent Reasoning in Looped Language Models [24.301295080069476]
  Looped Language Models (LoopLMs) enable efficient latent reasoning through depth recurrence, yet exhibit unreliable test-time scaling behavior.<n>We propose STARS (ST-driven Recurrent Scaling), a training framework that constrains latent states to approach reductionally stable fixed points.
  arXiv  Detail & Related papers  (2026-05-26T09:11:12Z)
• Asynchronous Heavy-Tailed Optimization [23.148100548141983]
  We propose two communication schemes that handle stragglers with asynchronous updates in the presence of heavy-tailed gradient noise.<n>Our convergence guarantees under heavy-tailed noise match the rate of the synchronous counterparts and improve delay tolerance compared with existing asynchronous approaches.
  arXiv  Detail & Related papers  (2026-02-20T05:28:48Z)
• Stabilizing Diffusion Posterior Sampling by Noise--Frequency Continuation [52.736416985173776]
  At high noise, data-consistency gradients computed from inaccurate estimates can be geometrically incongruent with the posterior geometry.<n>We propose a noise--frequency Continuation framework that constructs a continuous family of intermediate posteriors whose likelihood enforces measurement consistency only within a noise-dependent frequency band.<n>Our method achieves state-of-the-art performance and improves motion deblurring PSNR by up to 5 dB over strong baselines.
  arXiv  Detail & Related papers  (2026-01-30T03:14:01Z)
• Average-reward reinforcement learning in semi-Markov decision processes via relative value iteration [7.465862205471524]
  We show that the RVI Q-learning algorithm converges almost surely to a compact, connected subset of solutions to the average-reward optimality equation.<n>To make full use of the SA framework, we introduce new monotonicity conditions for estimating the optimal reward rate.
  arXiv  Detail & Related papers  (2025-12-05T23:49:07Z)
• Optimal sparse phase retrieval via a quasi-Bayesian approach [0.0]
  A signal need to be reconstructed using only the magnitude of its transformation while phase information remains inaccessible. We introduce a novel sparse quasi-Bayesian approach and provide the first theoretical guarantees for such an approach. Our results establish that the proposed Bayesian estimator achieves minimax-optimal convergence rates under sub-exponential noise.
  arXiv  Detail & Related papers  (2025-04-13T10:21:35Z)
• Asynchronous Stochastic Approximation and Average-Reward Reinforcement Learning [11.868402302316131]
  We extend Borkar and Meyn's stability proof method to accommodate more general noise conditions. We establish the convergence of an asynchronous SA analogue of Schweitzer's classical relative value algorithm, RVI Q-learning. We introduce new monotonicity conditions for estimating the optimal reward rate in RVI Q-learning.
  arXiv  Detail & Related papers  (2024-09-05T21:23:51Z)
• Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling [73.5602474095954]
  We study the non-asymptotic performance of approximation schemes with delayed updates under Markovian sampling. Our theoretical findings shed light on the finite-time effects of delays for a broad class of algorithms.
  arXiv  Detail & Related papers  (2024-02-19T03:08:02Z)
• The ODE Method for Stochastic Approximation and Reinforcement Learning with Markovian Noise [17.493808856903303]
  One fundamental challenge in analyzing an approximation algorithm is to establish its stability. In this paper, we extend the celebrated Borkar-Meyn theorem for stability bounded from the Martingale difference noise setting to the Markovian noise setting. Central to our analysis is the diminishing rate of change of a few functions, which is implied by both a form of strong law of large numbers and a commonly used V4 Lynov drift condition.
  arXiv  Detail & Related papers  (2024-01-15T17:20:17Z)
• Stability and Generalization of Stochastic Compositional Gradient Descent Algorithms [61.59448949684493]
  We provide the stability and generalization analysis of compositional descent algorithms built from training examples. We establish the uniform stability results for two popular compositional gradient descent algorithms, namely SCGD and SCSC. We derive-independent excess risk bounds for SCGD and SCSC by trade-offing their stability results and optimization errors.
  arXiv  Detail & Related papers  (2023-07-07T02:40:09Z)
• First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities [91.46841922915418]
  We present a unified approach for the theoretical analysis of first-order variation methods. Our approach covers both non-linear gradient and strongly Monte Carlo problems. We provide bounds that match the oracle strongly in the case of convex method optimization problems.
  arXiv  Detail & Related papers  (2023-05-25T11:11:31Z)
• Learning to Optimize with Stochastic Dominance Constraints [103.26714928625582]
  In this paper, we develop a simple yet efficient approach for the problem of comparing uncertain quantities. We recast inner optimization in the Lagrangian as a learning problem for surrogate approximation, which bypasses apparent intractability. The proposed light-SD demonstrates superior performance on several representative problems ranging from finance to supply chain management.
  arXiv  Detail & Related papers  (2022-11-14T21:54:31Z)
• STRONG: Synchronous and asynchronous RObust Network localization, under Non-Gaussian noise [0.0]
  Real-world network applications must cope with failing nodes, malicious attacks and data classified as outliers. Our work addresses these concerns in the scope of the sensor network localization algorithms. A major highlight of our contribution lies on the fact that we pay no price for provable distributed neither in accuracy, nor in communication cost or speed.
  arXiv  Detail & Related papers  (2021-10-01T18:01:28Z)
• Asynchronous Iterations in Optimization: New Sequence Results and Sharper Algorithmic Guarantees [10.984101749941471]
  We introduce novel convergence results for asynchronous iterations that appear in the analysis of parallel and distributed optimization algorithms. Results are simple to apply and give explicit estimates for how the degree of asynchrony impacts the convergence rates of the iterates.
  arXiv  Detail & Related papers  (2021-09-09T19:08:56Z)
• Exact solution to the random sequential dynamics of a message passing algorithm [4.066211670342284]
  We analyze the random sequential dynamics of a message passing algorithm for Ising models with random interactions in the large system limit. The em de Almedia-Thouless stability criterion of the static problem is found to be necessary and sufficient for the global convergence of the random sequential dynamics.
  arXiv  Detail & Related papers  (2021-01-05T15:03:54Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  This paper focuses on methods for solving smooth non-concave min-max problems, which have received increasing attention due to deep learning (e.g., deep AUC)
  arXiv  Detail & Related papers  (2020-06-12T00:32:21Z)
• Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping [69.9674326582747]
  We propose a new accelerated first-order method called clipped-SSTM for smooth convex optimization with heavy-tailed distributed noise in gradients. We prove new complexity that outperform state-of-the-art results in this case. We derive the first non-trivial high-probability complexity bounds for SGD with clipping without light-tails assumption on the noise.
  arXiv  Detail & Related papers  (2020-05-21T17:05:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.