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
• Authors: Huizhen Yu, Yi Wan, Richard S. Sutton,
• 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

• 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.