A Single-Timescale Analysis For Stochastic Approximation With Multiple Coupled Sequences

• URL: http://arxiv.org/abs/2206.10414v1
• Date: Tue, 21 Jun 2022 14:13:20 GMT
• Title: A Single-Timescale Analysis For Stochastic Approximation With Multiple Coupled Sequences
• Authors: Han Shen and Tianyi Chen
• Abstract summary: We study the finite-time convergence of nonlinear approximation with multiple coupled sequences. At the heart of our analysis is the smoothness property of the fixed points in multi-sequence SA that holds in many applications.
• Score: 21.50207156675195
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Stochastic approximation (SA) with multiple coupled sequences has found broad applications in machine learning such as bilevel learning and reinforcement learning (RL). In this paper, we study the finite-time convergence of nonlinear SA with multiple coupled sequences. Different from existing multi-timescale analysis, we seek for scenarios where a fine-grained analysis can provide the tight performance guarantee for multi-sequence single-timescale SA (STSA). At the heart of our analysis is the smoothness property of the fixed points in multi-sequence SA that holds in many applications. When all sequences have strongly monotone increments, we establish the iteration complexity of $\mathcal{O}(\epsilon^{-1})$ to achieve $\epsilon$-accuracy, which improves the existing $\mathcal{O}(\epsilon^{-1.5})$ complexity for two coupled sequences. When all but the main sequence have strongly monotone increments, we establish the iteration complexity of $\mathcal{O}(\epsilon^{-2})$. The merit of our results lies in that applying them to stochastic bilevel and compositional optimization problems, as well as RL problems leads to either relaxed assumptions or improvements over their existing performance guarantees.

Related papers

• Single-Timescale Multi-Sequence Stochastic Approximation Without Fixed Point Smoothness: Theories and Applications [33.21958331056391]
  Multi-sequence approximation (SA) that involves multiple coupled sequences, known as multiple-sequence SA (MSSA), finds diverse applications in the fields of signal processing and machine learning. This paper establishes tighter single-timescale analysis for MSSA, without assuming smoothness of the fixed points. Applying these theoretical findings to bilevel optimization and communication-efficient distributed learning offers relaxed assumptions and/or simpler algorithms with performance guarantees.
  arXiv  Detail & Related papers  (2024-10-17T16:39:53Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  We consider the problem of learning an $varepsilon$-optimal policy in a general class of continuous-space Markov decision processes (MDPs) having smooth Bellman operators. Key to our solution is a novel projection technique based on ideas from harmonic analysis. Our result bridges the gap between two popular but conflicting perspectives on continuous-space MDPs.
  arXiv  Detail & Related papers  (2024-05-10T09:58:47Z)
• Tight Finite Time Bounds of Two-Time-Scale Linear Stochastic Approximation with Markovian Noise [9.82187447690297]
  We characterize a tight convergence bound for the iterations of linear two-time-scale approximation (SA) with Markovian noise. Our results can be applied to establish the convergence behavior of a variety of RL algorithms, such as TD-learning with Polyak averaging, GTD, and GTD2.
  arXiv  Detail & Related papers  (2023-12-31T01:30:14Z)
• Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
  We consider clipped optimization problems with heavy-tailed noise with structured density. We show that it is possible to get faster rates of convergence than $mathcalO(K-(alpha - 1)/alpha)$, when the gradients have finite moments of order. We prove that the resulting estimates have negligible bias and controllable variance.
  arXiv  Detail & Related papers  (2023-11-07T17:39:17Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  We propose a novel method named Multi-block-probe Variance Reduced (MSVR) to alleviate the complexity of compositional problems. Our results improve upon prior ones in several aspects, including the order of sample complexities and dependence on strongity.
  arXiv  Detail & Related papers  (2022-07-18T12:03:26Z)
• Tighter Analysis of Alternating Stochastic Gradient Method for Stochastic Nested Problems [31.02472517086767]
  This paper unifies SGD-type updates for nested problems into a single approach that we term ALternating dEscenT (ALSET) method. Under the new analysis, to achieve an $epsilon$-stationary point of the nested problem, it requires $cal O(epsilon-2)$ samples. Applying our results to compositional, min-max and reinforcement learning problems either improves or matches the best-known sample complexity in the respective cases.
  arXiv  Detail & Related papers  (2021-06-25T17:33:51Z)
• Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel Optimization [62.87181271021217]
  We consider non-SBO problems that have many applications in machine learning. This paper proposes fast randomized algorithms for non-SBO problems.
  arXiv  Detail & Related papers  (2021-05-05T18:28:42Z)
• Adaptive Sequential SAA for Solving Two-stage Stochastic Linear Programs [1.6181085766811525]
  We present adaptive sequential SAA (sample average approximation) algorithms to solve large-scale two-stage linear programs. The proposed algorithm can be stopped in finite-time to return a solution endowed with a probabilistic guarantee on quality.
  arXiv  Detail & Related papers  (2020-12-07T14:58:16Z)
• Sample Complexity Bounds for Two Timescale Value-based Reinforcement Learning Algorithms [65.09383385484007]
  Two timescale approximation (SA) has been widely used in value-based reinforcement learning algorithms. We study the non-asymptotic convergence rate of two timescale linear and nonlinear TDC and Greedy-GQ algorithms.
  arXiv  Detail & Related papers  (2020-11-10T11:36:30Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  We propose two single-timescale single-loop algorithms that require only one data point each step. Our results are expressed in a form of simultaneous primal and dual side convergence.
  arXiv  Detail & Related papers  (2020-08-23T20:36:49Z)

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.