PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Han Shen, Tianyi Chen

arXiv:2206.10414v1cs.LGmath.OCstat.ML

TL;DR

The paper studies whether nonlinear stochastic approximation with coupled sequences can have finite-time guarantees using a single timescale. It analyzes such updates by exploiting smoothness of fixed points, obtaining O(ε^-1) complexity when all increments are strongly monotone and O(ε^-2) when the main sequence is not. Applications to bilevel and compositional optimization and reinforcement learning yield reported rate improvements or relaxed assumptions.

  • Problem

    Nonlinear stochastic approximation with coupled sequences has a slower known two-timescale rate than linear SA, motivating the question of when a single-timescale analysis can give tight finite-time guarantees.

    Source: §1 · p. 2

  • Method

    The paper analyzes multi-sequence single-timescale updates by exploiting smoothness of their fixed points.

    Source: §1 · pp. 3–4

  • Results

    The analysis establishes O(ε^-1) complexity when all sequences have strongly monotone increments and O(ε^-2) when only the auxiliary sequences do.

    Source: §1 · p. 4

  • Takeaways & Limitations

    Applications report improved rates or relaxed assumptions for stochastic bilevel and compositional optimization and reinforcement-learning methods.

    Source: §1 · p. 4

    The analysis assumes each auxiliary fixed point exists uniquely and varies smoothly with its preceding sequence.

    Source: §2 · p. 4

Abstract

from arXiv · show

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.

1. Introduction

The introduction asks whether nonlinear stochastic approximation with coupled sequences can converge efficiently using one timescale, and presents an analysis based on smooth fixed points. It applies that analysis to stochastic bilevel and compositional optimization and reinforcement learning, reporting improved rates or relaxed assumptions.

1. Introduction

  • An introductory experiment suggests that the double-sequence nonlinear update can converge with single-timescale steps despite the existing theoretical O(ε^-1.5) two-timescale guarantee.The authors use this observation to motivate investigating faster nonlinear convergence.Source: §1 · p. 2
  • The motivation includes extending beyond double-sequence analyses, since multi-level optimization can involve more than two coupled sequences and prior multi-timescale complexity worsens with sequence count N.The paper identifies the exact multi-sequence update as more challenging to analyze because its sequences are coupled.Source: §1 · pp. 2–3
  • Smooth fixed points support single-timescale updates, with convergence-rate order independent of the number of sequences N.The paper’s intuition is that auxiliary updates converge fast enough for their fixed-point residual to match the fixed point’s drift.Source: §1 · pp. 3–4
  • When all sequences have strongly monotone increments, the analysis gives O(ε^-1) complexity, improving the prior O(ε^-1.5) multi-sequence two-timescale result; with only auxiliary sequences strongly monotone, it gives O(ε^-2).The paper frames these as results for its single-timescale analysis of multi-sequence stochastic approximation.Source: §1 · p. 4
  • For stochastic bilevel optimization, strongly concave objectives improve TTSA’s sample complexity from Õ(ε^-1.5) to Õ(ε^-1); for non-concave objectives, the result matches ALSET’s O(ε^-2) while relaxing the bounded upper-level-gradient assumption.Source: §1 · p. 4
  • For multi-level stochastic compositional optimization, the reported complexities become level-independent: Õ(ε^-1) for strongly concave objectives and O(ε^-2) for non-concave objectives.These improve on the level-dependent complexity of multi-sequence α-TSCGD.Source: §1 · p. 4
  • In reinforcement learning, the actor-critic application retains ALSET-AC’s O(ε^-2) sample complexity while relaxing its unverifiable stationary-distribution assumption.The meta policy gradient application improves SG-MRL’s sample complexity from O(ε^-4) to O(ε^-2).Source: §1 · p. 4

2. Main Results: Convergence of Single-timescale Multi-sequence SA

The analysis establishes finite-time convergence guarantees for multi-sequence single-timescale stochastic approximation under smoothness of the fixed points and assumptions on the increments and noise. It treats both strongly monotone and non-strongly-monotone main sequences, with convergence-rate order independent of the number of sequences.

2. Main Results: Convergence of Single-timescale Multi-sequence SA

  • Smooth fixed points and Lipschitz increments, together with the stated noise and monotonicity assumptions, underpin the finite-time results.The fixed point y_n,*(y_{n-1}) is unique for each preceding sequence value, and its zeroth- and first-order drifts are controlled as y_{n-1} changes.Source: §2 · pp. 4–5

2.1. The strongly-monotone case

  • Theorem 1's order of convergence rate is independent of N, unlike rates that worsen as N increases (Doan, 2021; Yang et al., 2018a).The comparison reports improvement over the O(k^-2/3) rate for double-sequence nonlinear SA under additional assumption (7b), and generalizes the O(1/k) double-sequence linear-SA rate to multi-sequence nonlinear SA (Kaledin et al., 2020).Source: §2.1 · p. 6

2.2. The non-strongly-monotone case

  • Theorem 2 gives an O(K^-2) finite-time rate for the gradient-norm error when the main sequence is not strongly monotone, independent of N.The result assumes a potential F with ∇F(x)=v(x) that is upper bounded along the iterates; its proof does not require x* to be unique or to exist.Source: §2.2 · pp. 6–7
  • The generic theorems apply to existing stochastic optimization and reinforcement-learning algorithms that satisfy the corresponding assumptions.The paper points to applications meeting either Assumptions 1–5 or Assumptions 1–4 and 6.Source: §2.2 · p. 7

3. Application to the stochastic bilevel optimization method

The section applies single-timescale stochastic approximation to stochastic bilevel optimization and advantage actor-critic. It reports improved or matched sample-complexity guarantees alongside relaxed assumptions, including an actor-critic analysis that proves the required fixed-point smoothness.

3.1. Reduction from the generic results

  • The bilevel update uses yk to approximate the generally unknown y∗(xk) while computing the gradient-based update.When yk reaches y∗(xk), the mapping v equals ∇F(xk).Source: §3.1 · pp. 7–8
  • Earlier analyses controlled lower-level drift using bounded gradients or projection; the bilevel application states neither is needed with the generic results.The paper connects these approaches to stronger Lipschitz assumptions or constraining xk to a compact set.Source: §3.1 · p. 8
  • Under Conditions (a)–(e), the bilevel iterates converge almost surely to x∗ and track y∗(xk).The section also states a Theorem 2 guarantee under Conditions (a)–(c), (e), and (f).Source: §3.1 · p. 9
  • O(ϵ−1log ϵ−1) improves on O(ϵ−1.5 log ϵ−1) for strongly concave F; for non-concave F, O(ϵ−2 log ϵ−1) matches the state of the art.The analysis also relaxes the Lipschitz assumption on f with respect to x and supports simultaneous updates.Source: §3.1 · p. 9

3.2. Application to advantage actor-critic

  • For actor-critic, the analysis justifies smoothness of y∗(x), a key condition for faster convergence, and its theorem holds without the projection used by Chen et al. (2021b).The actor-critic noise condition reduces to Assumption 3 as yk converges to y∗(xk).Source: §3.2 · p. 11

4. Application to the stochastic compositional optimization method

This section applies STSA to stochastic compositional optimization and model-agnostic meta policy gradients. It reduces the update schemes to STSA and states their convergence guarantees under specified conditions.

4.1. Reduction from the generic STSA results

  • The compositional-gradient estimator can be biased under nonlinear mappings, so the method tracks expectations with variables y_n.The section then identifies the y_n and x updates as special cases of the STSA update.Source: §4.1 · pp. 11–12
  • O(ϵ^-1) in the strongly monotone case and O(ϵ^-2) in the nonmonotone case are independent of N for multi-level SCO.The corollary obtains these guarantees under Conditions (g)–(j) and (g)–(i), (k), respectively.Source: §4.1 · pp. 12–13

4.2. Application to model-agnostic meta policy gradient

  • MAMPG seeks a shared initial policy parameter whose task-specific policies perform well after N gradient-ascent steps.Its updates are written as a special case of STSA, with sufficient conditions summarized in Lemma 4.Source: §4.2 · pp. 13–14
  • The MAMPG application achieves O(ϵ^-2) sample complexity, improving on O(ϵ^-4), and applies for any N ≥ 1.The compared method in Fallah et al. (2021) applies only when N = 1.Source: §4.2 · p. 14

5. Conclusions

The conclusion summarizes STSA rates for nonlinear coupled sequences and their applications. The appendix places the work alongside related bilevel, compositional, and actor-critic methods.

5. Conclusions

  • With strongly monotone increments for all sequences, STSA gives O(ϵ^-1) iteration complexity; when the main sequence is not strongly monotone, it gives O(ϵ^-2).The conclusion reports applications to stochastic bilevel and compositional optimization and to actor-critic and meta policy gradient methods.Source: §5 · p. 14

Appendix A. Additional related works

  • Some concurrent bilevel methods use variance reduction or avoid warm starts, while another removes Hessian inverses but requires bounded gradients.The authors distinguish these algorithms from the plain-vanilla SA update analyzed here.Source: Appendix A · p. 19
  • For SCO, prior methods matching the stated rates modify the basic SA update, while this work targets the update without diminishing variance.The cited concurrent variance-reduced method is not directly applicable to their SCO case because its update scheme differs.Source: Appendix A · p. 19
  • A concurrent single-loop actor-critic analysis attains the best-known condition-number dependence but still requires projection in the critic update.Source: Appendix A · p. 20

Appendix B. Proof of Theorem 1

The proof analyzes lower-level sequence errors by bounding their update terms and accounting for how those sequences depend on upper-level variables.

B.1. Analysis of the lower-level sequences

  • The lower-level bounds combine one-step contraction with strong monotonicity, Young’s inequality, and the bias of the increment.The proof invokes strong monotonicity of h in bounding the last term of the error expression.Source: §B.1 · p. 20
  • The proof obtains bounds by decomposing error terms, bounding them separately, and substituting the resulting inequalities into the recursion.Source: §B.1 · pp. 21, 22, 25
  • For n ≥ 2, the lower-level variable is correlated with its upper-level variable, and the upper-level update depends on all variables.The proof distinguishes this dependence from the update of y^(n-1), making the y^1 analysis different from that of deeper levels.Source: §B.1 · p. 23

B.2. Analysis of the main sequence

The main-sequence proof bounds the update error and then establishes convergence using step-size conditions. It also extends the convergence result to an alternative error metric.

B.2. Analysis of the main sequence

  • The main-sequence analysis bounds the terms in its update recursion using strong monotonicity and the stated assumptions.The bounds are collected into a recursion before the section establishes convergence.Source: §B.2 · p. 26
  • Applying Robbins–Siegmund’s theorem to the derived inequality yields almost-sure finiteness of the weighted error sum and convergence of J_k.The argument uses the specified step-size choice.Source: §B.2 · p. 27
  • The convergence theorem also holds for the alternative metric combining the main-sequence error with the lower-level errors.Source: §B.2 · p. 27

Appendix C. Proof of Theorem 2

The proof bounds the lower-level optimality gaps before analyzing the main sequence and establishing finite-time convergence. It handles the first lower-level sequence separately from later sequences and selects step sizes to control the convergence bound.

C.1. Analysis of the lower-level sequences

  • For n = 1, the proof uses the mean-value theorem to rewrite a term in the lower-level gap bound; for n ≥ 2, the update has no direct dependence on x_k.The n ≥ 2 analysis is stated to be identical to Theorem 1.Source: §C.1 · pp. 28–29
  • The lower-level gap analysis bounds terms in the gap recursion, combines those bounds, and imposes a step-size condition.The resulting bounds complete the lower-level sequence analysis.Source: §C.1 · pp. 28–29

C.2. Analysis of the main sequence

  • For the main sequence, the proof bounds the terms in its recursion and combines them before deriving a convergence bound.The derivation uses products of lower-level contraction factors.Source: §C.2 · p. 30
  • The convergence argument defines a series, selects step sizes, and applies the resulting bounds to the main-sequence inequality.The proof notes that the step-size equations admit solutions for sufficiently small α_1 and then for the lower-level step sizes.Source: §C.2 · p. 31
  • Taking expectations of the main-sequence inequality and summing over iterations completes the finite-time convergence argument.The proof sums over k = 1, …, K.Source: §C.2 · p. 32

Appendix D. Proof of Lemma 1 and Corollary 1

The appendix verifies assumptions used for the corollary and points to the refined drifting-optimality-gap bound behind the relaxed assumptions. It then begins the proof of Theorem 3.

Appendix D. Proof of Lemma 1 and Corollary 1

  • Strong convexity of g(x, y) in y gives a unique y*(x) satisfying h(x, y*(x)) = 0.This verifies the stated fixed-point property for the assumption check.Source: Appendix D · p. 32
  • The proof identifies refined bounds on the drifting optimality gaps as crucial to alleviating the assumptions of Chen et al. (2021b).It directs readers to the proofs of Theorems 1 and 2 for the refinement.Source: Appendix D · p. 32
  • The appendix maps conditions (a)–(f) to Assumptions 1–6, with conditions (a)–(c) establishing Assumption 2.For N = 1, the listed conditions directly imply the corresponding Assumption 3.Source: Appendix D · p. 32

Appendix E. Proof of Theorem 3

  • The following appendix section begins with a proof of Lemma 2 and then turns to Theorem 3.Theorem 3's proof is described as similar to Theorem 2, showing only steps changed by adapting Assumption 3 to AC.Source: Appendix E · p. 33

E.1. Proof of Lemma 2

The proof of Lemma 2 verifies regularity and assumption conditions for the AC setting. It uses boundedness and Lipschitz properties of the fixed point and related gradients in these checks.

E.1. Proof of Lemma 2

  • The proof establishes Lipschitz continuity of y*(x) by applying Lemma 12.The passage gives a modulus for this continuity.Source: §E.1 · p. 33
  • To establish Lipschitz continuity of ∇_i y*(x), the proof reduces the task to boundedness and Lipschitz continuity of ∇_i A_x, y*(x), ∇_i b_x, and A_x^-1.It then narrows the remaining task to ∇_i A_x and ∇_i b_x.Source: §E.1 · p. 33
  • The proof defines the state-action probability measure as (μ^{π_x} · π_x)(s, a) = μ^{π_x}(s)π_x(a|s) when bounding the gradient terms.The bound invokes Lemma 5 and Lemma 12 together with condition (p).Source: §E.1 · p. 34
  • In AC, v(x) equals ∇F(x), and the proof uses the stated conditions to verify Assumptions 2 and 4, Assumption 6, and the noise condition.It also notes that |F(x)| is bounded by 1/(1 − γ).Source: §E.1 · p. 34

E.2. Proof of Theorem 3

Theorem 3's proof adapts the convergence analysis to AC by bounding the critic gap and main-sequence terms, then applying a Lyapunov argument. The appendix also supplies supporting lemmas under conditions (p) and (q).

E.2. Proof of Theorem 3

  • Strong monotonicity of h(x, y) and the zero conditional mean of ψ_k support the critic optimality-gap contraction bound.The proof collects the resulting term bounds to control the drifting optimality gap.Source: §E.2 · p. 35
  • The proof bounds the main-sequence terms and uses a Lyapunov function involving −F(x_k) and the critic's distance from its fixed point.It sums the resulting inequality over iterations to establish convergence.Source: §E.2 · pp. 36–37
  • With the specified step-size condition, the proof concludes that Theorem 2 holds for the AC update.The convergence bound is described as having a similar form to the N = 1 bound.Source: §E.2 · p. 37

E.3. Supporting lemma

  • The supporting lemmas state bounds under conditions (p) and (q) for the state-action measure and define a bounded mapping used in the analysis.The mapping in Lemma 7 is defined from a function with norm bounded by C_r.Source: §E.3 · pp. 37–38

Appendix F. Proof of Lemma 3 and Corollary 2

The appendix proves Lemma 3 by checking that the stated conditions imply the generic assumptions used to obtain Corollary 2. The verification uses smoothness of the fixed-point compositions and properties of the stochastic estimators.

Appendix F. Proof of Lemma 3 and Corollary 2

  • Conditions (g)–(k) verify the generic assumptions, with Assumption 4 holding at λ_n = 1 for every n.The proof also uses conditional independence given F_k and bounded estimator second moments under condition (h).Source: Appendix F · p. 41
  • The fixed-point sequence is expressed through nested compositions f_0(x), f_1(f_0(x)), …, with its derivative given by the corresponding gradient product.The displayed composition and product specify the chain structure used in the smoothness argument.Source: §2 · p. 5, Appendix F · p. 41
  • Bounded, Lipschitz gradients ∇f_n make the composed fixed-point map v Lipschitz in x and in the coupled sequences.The proof also invokes condition (g) for Lipschitz continuity of h_n with respect to y_n.Source: Appendix F · p. 41

Appendix G. Proof of Lemma 4 and Theorem 4

The appendix verifies the assumptions needed for Theorem 4 and supplies technical lemmas for the analysis. The proof relies on smoothness checks for composed functions and policy estimators, alongside step-size and convergence results.

Appendix G. Proof of Lemma 4 and Theorem 4

  • Conditions (l), (m), and (n) verify the generic assumptions for Theorem 4, including Assumption 4 with λ_n = 1.The proof states that (m) and (n) imply the earlier conditions (h) and (i), and describes trajectory-based estimators under policy π_y.Source: Appendix G · pp. 42–44
  • The policy-Hessian smoothness check reduces to boundedness and Lipschitz properties of the score, trajectory return term g, and its gradient.Condition (l) directly supplies the score property; the proof uses Lemma 12 to infer Lipschitz continuity of H(x; ζ).Source: Appendix G · pp. 42–43

Appendix H. Technical lemmas

  • Lemma 8’s step-size inequality can be met when adjacent β step sizes share a scale and β_1,n−1 is small relative to β_1,n.Lemma 9 further states that when all step sizes share a time-scale, solutions exist for β_k,n−1 whenever α_k ≤ β_k,n−1 ≤ 1.Source: Appendix H · p. 45
  • The technical lemmas include a Robbins–Siegmund convergence condition and a product-Lipschitz result used to control composed maps.Lemma 10 states convergence of V_k to a finite limit with bounded expectations; Lemma 12 gives a continuity result for products of functions.Source: Appendix H · pp. 44–46
Loading 2206.10414v1…