N ONLINEAR T WO -T IME -S CALE S TOCHASTIC A PPROXIMATION : A S HARP P HASE T RANSITION AND H OW TO B EAT I T
Dhruv Sarkar1,2 Vaneet Aggarwal3 Indian Institute of Technology Kharagpur 2 Mohamed bin Zayed University of Artificial Intelligence 3 Purdue University [email protected] [email protected]
arXiv:2606.14488v1 [cs.IT] 12 Jun 2026
1
June 15, 2026
A BSTRACT Recent finite-time analyses of nonlinear two-time-scale stochastic approximation show that under contractive assumptions the slow iterate Yk with stepsizes βk = Θ(k −1 ) and αk = Θ(k −a ), a ∈ (1/2, 1), generally satisfies a mean-square rate of order k −a ; decoupled k −1 rates require strong local linearity. We identify a sharp regularity-dependent boundary. In a rate-determining normal form where the slow drift contains a locally linear leakage and a nonlinear remainder of order 1 + ρ (ρ ∈ [0, 1]), the uncorrected recursion satisfies E∥Yk ∥2 ≤ C k −1 + k −a(1+ρ) , and a matching scalar Gaussian lower bound shows that the slower term is unavoidable without modifying the update. Thus the decoupled k −1 rate is guaranteed for the uncorrected recursion exactly when a(1 + ρ) ≥ 1. This lower bound concerns only the naive update; it is not an informationtheoretic obstruction. We demonstrate this by equipping the normal-form recursion with an auxiliary online bias estimator Mk+1 = Mk + γk (R(Xk ) − Mk ),
βk ≪ γk ≪ αk ,
and subtracting Mk from the slow update. Under the same stability, moment, and remainder assumptions, the corrected recursion achieves E∥Yek ∥2 = O(k −1 ) for every ρ ∈ [0, 1], including regimes where the uncorrected update provably suffers the slower rate. Finally, we prove localized transfer theorems that extend the phase-transition mechanism to general nonlinear TTSA in fast-manifold coordinates. The proofs are non-asymptotic and rely on two Abel-transform cancellations: one for the locally linear fast-error leakage, and one for the tracked nonlinear bias. Keywords stochastic approximation · two-time-scale stochastic approximation · finite-time analysis · local linearity · lower bounds · bias tracking
1
Introduction
Two-time-scale stochastic approximation (TTSA) studies coupled recursions in which a fast iterate is updated with stepsize αk and a slow iterate is updated with a smaller stepsize βk . In its fixed-point form, the recursion is often written as xk+1 = xk + αk f (xk , yk ) − xk + Mk+1 , ′ yk+1 = yk + βk g(xk , yk ) − yk + Mk+1 , where βk /αk → 0 in the truly two-time-scale regime. TTSA is a central tool in reinforcement learning, stochastic optimization, stochastic control, saddle-point learning, and game control; see, for example, the classical monographs and early analyses [1, 2, 3, 4].
A PREPRINT - J UNE 15, 2026
For linear TTSA, the slow iterate may enjoy a decoupled O(k −1 ) mean-square rate under βk = Θ(k −1 ) even when αk = Θ(k −a ) with a < 1 [4, 5, 6]. For nonlinear contractive TTSA the situation is more delicate. Doan [7] established finite-time guarantees for nonlinear TTSA, and a recent averaged-noise analysis of Chandak [8] improved the truly separated nonlinear rate to O(k −a ) under standard contractive assumptions. Meanwhile, Han, Li, and Zhang [9] proved that the decoupled O(k −1 ) rate is recovered under nested local linearity assumptions, and provided empirical evidence that local linearity may be necessary. Chandak [8] explicitly posed it as an open problem whether O(k −1 ) is possible for nonlinear TTSA without additional assumptions, conjecturing that O(k −a ) is the best achievable rate in general. This leaves a structural question: What feature of the slow drift determines whether the slow iterate converges at the decoupled k −1 rate or at the fast-tracking rate k −a ? It also raises an algorithmic open problem: if the slow rate is limited by nonlinear bias, can a change in the update rule remove that bias and recover the decoupled rate without adding simulator access or oracle debiasing? We answer both questions using a local normal-form model that isolates the rate-determining terms from the otherwise involved mechanics of the general TTSA recursion. Let Xk denote the fast tracking error and Yk the slow error. After linearizing the fast dynamics and expanding the slow drift in the fast error, the leading model is Xk+1 = (I − αk A)Xk + αk ξk+1 ,
(1)
Yk+1 = (I − βk B)Yk + βk HXk + R(Xk ) + ζk+1 .
(2)
Here HXk is the locally linear leakage of fast error into the slow recursion, and R(Xk ) is the genuinely nonlinear remainder. We assume 1+ρ ∥R(x)∥ ≤ LR ∥x∥ , ρ ∈ [0, 1], where ρ measures local regularity: ρ = 0 is a Lipschitz remainder, ρ = 1 a second-order remainder. Prior work [8, 9] suggested that decoupled O(k −1 ) slow convergence requires local linearity, and that without local linearity the best possible rate is O(k −a ). Our results show that this binary picture is incomplete. The determining quantity is the local regularity and predictable bias of the nonlinear remainder. For an order-(1 + ρ) remainder, the sharp uncorrected rate is O(k −1 + k −a(1+ρ) ), with a matching lower bound. Thus local linearity is sufficient but not necessary: sufficiently regular nonlinear remainders still recover the decoupled rate. Sharp rate for the uncorrected recursion. For αk = α0 (k + k0 )−a and βk = β0 (k + k0 )−1 , a ∈ (1/2, 1), our first main theorem proves 2 E ∥Yk ∥ ≤ C (k + k0 )−1 + (k + k0 )−a(1+ρ) . (3) The term (k + k0 )−1 is the usual stochastic approximation noise floor for the slow recursion. The term (k + k0 )−a(1+ρ) is the squared nonlinear bias induced by the fast tracking fluctuations. Thus the uncorrected slow recursion exhibits the phase transition O(k −a(1+ρ) ), a(1 + ρ) < 1, 2 E ∥Yk ∥ = O(k −1 ), a(1 + ρ) ≥ 1. The following table summarizes the regimes. Slow-drift structure in fast error
Regularity
Uniform rate for uncorrected recursion
Exactly locally linear, R ≡ 0 no nonlinear bias O(k −1 ) Merely Lipschitz remainder ρ=0 O(k −a ) C 1,ρ -type remainder ρ ∈ (0, 1) O(k − min{1,a(1+ρ)} ) Second-order Taylor remainder ρ = 1 O(k −1 ) for all a > 1/2 Table 1: Regularity regimes for the uncorrected normal-form recursion. The decoupled slow rate is guaranteed uniformly exactly when a(1 + ρ) ≥ 1.
2
Why the linear leakage does not hurt. The fast variable has E ∥Xk ∥ = Θ(αk ) = Θ(k −a ). A direct input-to-state bound on the term HXk would therefore lose the desired k −1 rate. The key observation, also underlying averaged-noise analyses of nonlinear TTSA, is that Xk itself satisfies a stable stochastic approximation recursion. Consequently, AXk = αk−1 (Xk − Xk+1 ) + ξk+1 . 2
A PREPRINT - J UNE 15, 2026
After substituting this identity into the slow convolution, the contribution of HXk splits into a martingale term with variance O(k −1 ) and a telescoping Abel-transform term that is also O(k −1 ). This is the precise mechanism by which local linearity restores decoupling. Why the nonlinear remainder is rate-limiting.
1+ρ
In contrast, if R(x) is of order ∥x∥
, then
(1+ρ)/2 E ∥R(Xk )∥ ≍ αk ≍ k −a(1+ρ)/2
in Gaussian normal-form examples. This contribution is not a martingale fluctuation and therefore does not average down to k −1 ; it appears as a slowly varying bias in the slow recursion. We prove that this obstruction is not an artifact of the proof by constructing a one-dimensional Gaussian instance for which E[Yk2 ] ≥ c1 k −a(1+ρ) + c2 k −1 .
(4)
The lower bound uses H = 0, so it is caused solely by nonlinear curvature, not by linear leakage. It is a lower bound for the uncorrected update rule (2); it does not preclude algorithms that estimate and subtract the predictable nonlinear bias. Online bias tracking resolves the algorithmic question in the normal form. The lower bound identifies what must be removed. We introduce an auxiliary bias tracker Mk+1 = Mk + γk R(Xk ) − Mk , γk = γ0 (k + k0 )−c , (5) with an intermediate time scale βk ≪ γk ≪ αk . The corrected slow update is Yek+1 = (I − βk B)Yek + βk HXk + R(Xk ) − Mk + ζk+1 .
(6)
This is a fully online correction for the normal-form recursion: it uses only the observed nonlinear term R(Xk ), adds no inner fast loops, and assumes no simulator or oracle access. The theorem proves 2
E Yek
≤ Ck −1
for every ρ ∈ [0, 1], including the regimes a(1 + ρ) < 1 where the uncorrected recursion has the lower bound (4). The proof uses a second Abel transform. Since R(Xk ) − Mk = γk−1 (Mk+1 − Mk ), the slow convolution of the corrected nonlinear input telescopes with coefficient βk /γk ; the intermediate time scale is chosen so that the resulting boundary and variation terms are below the k −1 noise floor. Technical novelty. The paper has two related technical messages. First, the same Abel-transform idea that averages locally linear fast-error leakage also gives a sharp diagnostic for nonlinear curvature: only the predictable part of the nonlinear input survives slow averaging. Second, once this predictable part is explicitly tracked on an intermediate time scale, it can be removed by another Abel-transform cancellation. This proves that the lower bound is an obstruction for the raw recursion, not an information-theoretic limitation of the normal-form problem class. Contributions.
The paper makes five technical contributions.
1. We formulate a normal-form TTSA model that separates the locally linear fast-error leakage from the genuinely nonlinear slow-drift remainder. 2. We prove a finite-time upper bound with the regularity-dependent rate O(k −1 + k −a(1+ρ) ). The proof is nonasymptotic and relies on an Abel-transform form of averaged-noise cancellation. 3. We prove a matching lower bound in a scalar Gaussian subclass. Hence, for the uncorrected normal-form recursion, the exponent min{1, a(1 + ρ)} cannot be improved uniformly. 4. We introduce an online three-time-scale bias-tracking recursion that subtracts a running estimate of the nonlinear predictable bias. Under the same normal-form stability, moment, and regularity assumptions, the corrected slow 2 iterate satisfies E Yek = O(k −1 ) for all ρ ∈ [0, 1]. 5. We transfer the normal-form phase transition to nonlinear TTSA and clarify its mechanism. A centering/debiasing result shows that nonlinear fluctuations of the same instantaneous size recover the decoupled k −1 rate when they are martingale-centered. Localized transfer and verification theorems in fast-manifold coordinates then show that the same phase transition persists under moving fast equilibria, induced slow-noise perturbations, variable local linearizations, and both separable and mixed higher-order Taylor terms, whenever the required finite-time localized moment estimates hold. 3
A PREPRINT - J UNE 15, 2026
2
Local normal form
We work on a filtered probability space (Ω, F, {Fk }k≥0 , P). All random variables below are assumed to be adapted to this filtration. For a positive integer d, ∥·∥ denotes the Euclidean norm on Rd and the induced operator norm on matrices. Fix a ∈ (1/2, 1) and define α0 β0 , βk = , k ≥ 0, (7) a (k + k0 ) k + k0 where α0 , β0 > 0. The offset k0 ≥ 2 is chosen once and for all large enough so that all contraction inequalities below hold and so that every small-step comparison used in the proofs is valid. In particular, we require λαk ≤ 1/4, bβk ≤ 1/2, 2a/k̄ ≤ (λ/2)αk , and the fourth-moment comparison (69). Such a finite choice exists because a < 1 and k̄ −1 = o(αk ). If a smaller offset is used, the same rates hold after a finite burn-in. We write αk =
k̄ := k + k0 . The normal form is the coupled recursion Xk+1 = (I − αk A)Xk + αk ξk+1 ,
(8)
Yk+1 = (I − βk B)Yk + βk HXk + R(Xk ) + ζk+1 ,
(9)
where Xk ∈ Rdx is the fast tracking error and Yk ∈ Rdy is the slow error. The matrices A ∈ Rdx ×dx and B ∈ Rdy ×dy describe the local stable linearizations of the fast and slow dynamics. The matrix H ∈ Rdy ×dx is the first-order dependence of the slow drift on the fast tracking error. The map R : Rdx → Rdy is the nonlinear remainder. Assumption 2.1 (Stability and noise). There exist constants λ, b > 0 such that, for all k ≥ 0, ∥I − αk A∥ ≤ 1 − λαk ,
∥I − βk B∥ ≤ 1 − bβk .
(10)
The matrix A is invertible. The noise sequences are martingale differences: E[ξk+1 | Fk ] = 0,
E[ζk+1 | Fk ] = 0.
(11)
2
(12)
Moreover, for a finite constant σ4 , 4
E[∥ξk+1 ∥ | Fk ] ≤ σ44 ,
E[∥ζk+1 ∥ | Fk ] ≤ σ42 .
The initial conditions X0 , Y0 are deterministic. Assumption 2.2 (Remainder regularity). For some ρ ∈ [0, 1] and LR < ∞, 1+ρ
∥R(x)∥ ≤ LR ∥x∥
,
x ∈ Rdx .
(13)
The quantity r := bβ0 , s := a(1 + ρ) (14) will appear throughout the paper. The exponent r is the polynomial strength of the slow linear contraction, while s is the exponent generated by the nonlinear remainder. Assumption 2.3 (Slow contraction strength). The slow contraction exponent satisfies r>
1 . 2
(15)
This is the standard finite-time requirement that the linear part of the slow recursion be strong enough to wash out the initial condition and to make the slow stochastic convolution square summable at rate k −1 . No additional condition involving the nonlinear exponent s = a(1 + ρ) is needed. When s > 1, the nonlinear convolution need only be controlled at the k −1 noise floor; the more flexible weighted-convolution estimate in the appendix handles this regime. Remark 2.4 (Relation to nonlinear TTSA). For a nonlinear TTSA recursion, set Xk = xk − x∗ (yk ) and Yk = yk − y ∗ . A local expansion of the slow drift around (x∗ (y), y) has the form g(x, y) − y ∗ = g(x∗ (y), y) − y ∗ + H(y)(x − x∗ (y)) + R(x − x∗ (y), y). The normal form (8)–(9) freezes the stable linear parts at the fixed point and isolates the two fast-error mechanisms that matter for rates: the locally linear term and the nonlinear remainder. The normal-form theorem is a sharp analysis of the leading local mechanism. Section 4 gives perturbation conditions under which this mechanism transfers to nonlinear TTSA in fast-manifold coordinates, while global stability or localization is handled separately. 4
A PREPRINT - J UNE 15, 2026
3
Main results
Theorem 3.1 (Regularity-dependent upper bound). Suppose Assumptions 2.1, 2.2, and 2.3 hold. Then there exists a finite constant C depending only on A, B, H, LR , λ, b, α0 , β0 , k0 , a, ρ, σ4 , X0 , Y0 such that, for every k ≥ 1, 2 E ∥Yk ∥ ≤ C k̄ −1 + k̄ −s , Moreover,
2
E ∥Xk ∥ ≤ Cαk ,
s = a(1 + ρ). 2+2ρ
E ∥Xk ∥
(16)
≤ Cαk1+ρ .
(17)
The proof is given in Appendix B. Theorem 3.1 separates the two contributions to the slow error. The locally linear leakage HXk contributes only O(k̄ −1 ). The nonlinear remainder contributes at most O(k̄ −1 + k̄ −s ); it can dominate the slow noise floor exactly when s < 1. Corollary 3.2 (Phase transition). Under the assumptions of Theorem 3.1, ( −a(1+ρ) C k̄ , a(1 + ρ) < 1, 2 E ∥Yk ∥ ≤ (18) C k̄ −1 , a(1 + ρ) ≥ 1. In particular, the slow iterate has the decoupled O(k −1 ) rate whenever ρ≥
1 − 1. a
(19)
2
2
For ρ = 0, the theorem gives E ∥Yk ∥ = O(k −a ). For ρ = 1 and a > 1/2, it gives E ∥Yk ∥ = O(k −1 ). Remark 3.3 (Uniform interpretation of the threshold). The word “threshold” is used in a uniform worst-case sense over the normal-form class. Special instances below the threshold can converge faster, for example when R ≡ 0 or when the nonlinear remainder has a symmetry that cancels its leading mean. The lower bound below shows that no rate better than k̄ − min{1,a(1+ρ)} can be guaranteed uniformly from Assumptions 2.1–2.3 alone. The next theorem shows that the exponent in Corollary 3.2 is intrinsic to the normal-form class. Theorem 3.4 (Matching scalar lower bound). Let dx = dy = 1, H = 0, and consider Xk+1 = (1 − λαk )Xk + αk ξk+1 ,
(20) 1+ρ
Yk+1 = (1 − bβk )Yk + βk γ|Xk |
+ τ ηk+1 ,
(21)
where X0 = Y0 = 0, λ, b, γ > 0, τ ≥ 0, and {ξk } and {ηk } are mutually independent i.i.d. standard Gaussian sequences. Choose k0 large enough that 0 < λαk < 1/4 and 0 < bβk < 1/2 for every k ≥ 0. Then there exist constants c > 0 and k1 ≥ 1, depending on the fixed parameters but not on k, such that for all k ≥ k1 , E[Yk2 ] ≥ cγ 2 k̄ −a(1+ρ) + cτ 2 k̄ −1 .
(22)
Consequently, the rate in Theorem 3.1 is unimprovable uniformly over the normal-form class whenever γ > 0 and, for the k −1 noise floor, τ > 0. If in addition bβ0 > 1/2, the lower-bound instance belongs to the same slow-contraction regime as Theorem 3.1. The proof is given in Appendix F. Remark 3.5 (Interpretation). The lower bound uses H = 0. Thus the obstruction to k −1 for a(1 + ρ) < 1 is not imperfect averaging of the √ locally linear term. It is the nonzero mean of the nonlinear remainder generated by the fast fluctuation scale ∥Xk ∥ ≈ αk . The statement is not that every nonlinear remainder creates this obstruction; odd or otherwise cancelling remainders may behave like centered noise. The result is a minimax sharpness statement. The next proposition makes the last sentence precise in a form that is useful for bias correction. It separates the size of a (1+ρ)/2 nonlinear fluctuation from its predictable component. A nonlinear term of size αk causes the slower k −a(1+ρ) rate only when it has a persistent predictable part of that size. Proposition 3.6 (Centering and debiasing principle). Consider the same fast recursion (8). Replace the slow recursion (9) by Yk+1 = (I − βk B)Yk + βk HXk + mk + νk+1 + ζk+1 , (23) 5
A PREPRINT - J UNE 15, 2026
where mk is Fk -measurable and νk+1 is a martingale difference satisfying 2
(24)
≤ Km k̄ −q .
(25)
E[∥νk+1 ∥ | Fk ] ≤ Kν αk1+ρ .
E[νk+1 | Fk ] = 0, Assume also that, for some q > 0 and Km < ∞,
2 1/2
E ∥mk ∥ Let
−q q < r, k̄ , −r Ψq (k) = k̄ log(k̄), q = r, −r k̄ , q > r. Under Assumptions 2.1 and 2.3, there is a finite constant C such that, for all k ≥ 1, 2 E ∥Yk ∥ ≤ C k̄ −1 + Ψq (k)2 . 2
In particular, if mk ≡ 0, then E ∥Yk ∥ ≤ C k̄ 3.1
−1
(26)
(27)
.
Online bias tracking in the normal form
Proposition 3.6 shows that a nonlinear input of the same instantaneous size as R(Xk ) is harmless when it is centered. We now give an online update that performs this centering in the normal-form model itself. The update does not require an independent simulator, a batch of fast loops, or an oracle for E[R(Xk )]. It simply tracks the observed nonlinear term on an intermediate time scale. Let γk =
γ0 , k̄ c
γ0 > 0,
(28)
where the exponent c satisfies 1+s a < c < min 1, , s = a(1 + ρ). (29) 2 The interval is non-empty for every a ∈ (1/2, 1) and ρ ∈ [0, 1]. Indeed, if s ≥ 1, then a < 1 gives a < min{1, (1 + s)/2} = 1; if s < 1, then 1+s 1 − a + aρ −a= > 0. 2 2 Increasing k0 if necessary, assume also that γk ≤ 1 for all k. The bias-tracked normal-form recursion is Xk+1 = (I − αk A)Xk + αk ξk+1 , Mk+1 = (1 − γk )Mk + γk R(Xk ), Yek+1 = (I − βk B)Yek + βk HXk + R(Xk ) − Mk + ζk+1 .
(30) (31) (32)
dy
The variable Mk ∈ R
is a running estimate of the predictable nonlinear bias. The time-scale ordering βk γk → 0, →0 γk αk means that Mk evolves faster than the slow recursion but slower than the fast tracking recursion. Theorem 3.7 (Online bias tracking averts the lower bound). Suppose Assumptions 2.1, 2.2, and 2.3 hold. Let γk satisfy (28)–(29), and let (Xk , Mk , Yek ) follow (30)–(32) with deterministic initial conditions. Then there is a finite constant C such that, for every k ≥ 1, 2 2 E ∥Mk ∥ ≤ C k̄ −s , E Yek ≤ C k̄ −1 . (33) Consequently, in the local normal form, the slower term k̄ −a(1+ρ) is unavoidable for the uncorrected recursion but is removed by the online bias-tracking update. The proof is given in Appendix D. Remark 3.8 (What the theorem does and does not require). The theorem uses no additional statistical assumptions beyond those already imposed for Theorem 3.1. The new ingredient is algorithmic: the normal form exposes R(Xk ), and the update (31) tracks this observed quantity. In a general nonlinear TTSA recursion, the analogous coupling error is hidden inside g(xk , yk ) − g(x∗ (yk ), yk ), and x∗ (yk ) is typically unknown. Extending the online bias tracker to that setting therefore requires additional structure, such as a local Taylor control variate, an estimator of the reduced drift, or a frozen slow iterate batching construction. The present theorem resolves the algorithmic bias question in the local normal form without such additional access. 6
A PREPRINT - J UNE 15, 2026
4
Localized transfer to nonlinear TTSA
The normal-form analysis isolates the mechanism by which local regularity of the slow drift controls the slow rate. We now show how the same mechanism transfers to nonlinear two-time-scale stochastic approximation near a stable equilibrium. The result is local in nature: it applies on time horizons where the iterates remain in a neighborhood in which fast-manifold coordinates and the displayed local error recursions are valid. This includes projected, truncated, or otherwise localized algorithms, as well as analyses combined with an independent stability argument. Any correction terms introduced by the chosen localization mechanism may be included in the perturbations below, provided they satisfy the bounds in Assumption 4.1. Consider the nonlinear two-time-scale recursion x xk+1 = xk + αk h(xk , yk ) + Mk+1 , y yk+1 = yk + βk g(xk , yk ) + Mk+1 ,
(34) (35)
where h : Rdx × Rdy → Rdx and g : Rdx × Rdy → Rdy . Suppose that, in a neighborhood U of the target slow equilibrium y ∗ , there is a map λ : U → Rdx satisfying h(λ(y), y) = 0,
y ∈ U.
The map λ is the fast equilibrium manifold. For a fixed value of the slow variable y, the fast mean field x 7→ h(x, y) has equilibrium λ(y). Thus, if y were frozen, the fast recursion would be expected to track λ(y). In the two-timescale recursion, however, yk changes slowly over time, so the fast iterate tracks a moving target. This motivates the fast-manifold coordinates Xk = xk − λ(yk ), Yk = yk − y ∗ . Here Xk is the genuine fast tracking error, while Yk is the slow error. The reduced slow drift is the map G(y) = g(λ(y), y), and the point y ∗ is a stable zero of this reduced drift in the local model below. The movement of the manifold λ(yk ) is the main new feature relative to the normal form. Since Xk+1 = xk+1 − λ(yk+1 ), y increments of yk feed back into the fast tracking recursion. In particular, the slow noise Mk+1 produces a perturbation of size βk in the X-recursion. The transfer theorem below treats the nonlinear recursion in fast-manifold coordinates as a perturbation of the normal form. The term pk+1 represents fast-recursion residuals at the αk scale, dk represents predictable perturbations entering through the moving manifold at the βk scale, and ek represents higher-order slow-drift terms beyond the components HXk + R(Xk ). The assumption is designed so that these perturbations remain below the phase-transition rate after the same Abel-transform cancellation used in the normal-form analysis. Assumption 4.1 (Localized nonlinear reduction). There are matrices A, B, H, a matrix Cζ , a map R : Rdx → Rdy , and adapted perturbation processes pk+1 , dk , and ek such that the local error process satisfies
Xk+1 = (I − αk A)Xk + αk ξk+1 + αk pk+1 + βk Cζ ζk+1 + βk dk , Yk+1 = (I − βk B)Yk + βk HXk + R(Xk ) + ζk+1 + ek ,
(36) (37)
where ξk+1 and ζk+1 are martingale differences with respect to Fk . The perturbation terms pk+1 , dk , and ek are not required to be martingale differences. Assumption 2.1 holds for A, B, ξ, ζ, and Assumption 2.2 holds for R. With s = a(1 + ρ),
δ = min{1, s},
there are finite constants KX , Kp , Kd , Ke and an exponent µp > δ/2 such that, for every k ≥ 0, 2
E ∥Xk ∥ ≤ KX αk , 2 1/2 E ∥pk+1 ∥ ≤ Kp k̄ −µp , 2 1/2 E ∥dk ∥ ≤ Kd k̄ −a/2 + k̄ −δ/2 , 2 1/2 E ∥ek ∥ ≤ Ke k̄ −δ/2 . Finally, Assumption 2.3 holds. 7
E ∥Xk ∥
2+2ρ
≤ KX αk1+ρ ,
(38) (39) (40) (41)
A PREPRINT - J UNE 15, 2026
Theorem 4.2 (Localized nonlinear transfer). Under Assumption 4.1, there is a finite constant C, depending only on the constants in the assumption and on the fixed problem parameters, such that, for every k ≥ 1, 2 E ∥Yk ∥ ≤ C k̄ −1 + k̄ −a(1+ρ) . (42) Consequently, the phase transition from Corollary 3.2 holds for every localized nonlinear recursion satisfying the reduction above. The next two propositions verify Assumption 4.1 from local Taylor structure. They are intended to be combined with any mechanism that supplies the required localized moment bounds, such as projection, truncation, a Lyapunov stability argument, or an existing finite-time nonlinear TTSA estimate. Proposition 4.3 covers a separable local structure in which the leading slow remainder depends only on the fast tracking error. Proposition 4.4 covers generic mixed local terms, at the cost of a fourth-moment bound on the slow error. Proposition 4.3 (Verification from separable local C 1,ρ structure). Consider a localized version of (34)–(35) on a time horizon where yk ∈ U and the iterates remain in a bounded neighborhood of (λ(y ∗ ), y ∗ ). Suppose that the following properties hold on this neighborhood. 1. The fast equilibrium manifold λ is twice continuously differentiable with bounded first and second derivatives. 2. There are matrices A, B, H and a map R satisfying Assumption 2.2 such that, for all local u and y, 2
h(λ(y) + u, y) = −Au + P (u, y),
∥P (u, y)∥ ≤ Lh ∥u∥ ,
∗
g(λ(y) + u, y) = −B(y − y ) + Hu + R(u) + E(u, y),
1+ρ
∥E(u, y)∥ ≤ Lg ∥u∥
(43) .
(44)
The matrices A and B satisfy the contraction inequalities in Assumption 2.1, and the stepsize constants satisfy Assumption 2.3. y x 3. The noises Mk+1 and Mk+1 are martingale differences with uniformly bounded fourth conditional moments. Set y ζk+1 = Mk+1 .
x ξk+1 = Mk+1 ,
4. A baseline localized moment estimate is available: for finite constants K0 , K1 , 4
E ∥Xk ∥ ≤ K0 αk2 ,
2
E ∥Yk ∥ ≤ K1 k̄ −a ,
k ≥ 0.
(45)
Then the localized recursion satisfies Assumption 4.1. Consequently, the conclusion of Theorem 4.2 holds. Proposition 4.4 (Verification with generic mixed local terms). Consider a localized version of (34)–(35) on a time horizon where yk ∈ U and the iterates remain in a bounded neighborhood of (λ(y ∗ ), y ∗ ). Suppose that the following properties hold on this neighborhood. 1. The fast equilibrium manifold λ is twice continuously differentiable with bounded first and second derivatives. 2. There are matrices A, B, H and a map R satisfying Assumption 2.2 such that, for all local u and y with Y = y − y ∗ , 2 h(λ(y) + u, y) = −Au + P (u, y), ∥P (u, y)∥ ≤ Lh ∥u∥ + ∥u∥ ∥Y ∥ , (46) 1+ρ 2 g(λ(y) + u, y) = −BY + Hu + R(u) + E(u, y), ∥E(u, y)∥ ≤ Lg ∥u∥ + ∥u∥ ∥Y ∥ + ∥Y ∥ . (47) The matrices A and B satisfy the contraction inequalities in Assumption 2.1, and the stepsize constants satisfy Assumption 2.3. y x 3. The noises Mk+1 and Mk+1 are martingale differences with uniformly bounded fourth conditional moments. Set y ζk+1 = Mk+1 .
x ξk+1 = Mk+1 ,
4. A fourth-moment localized estimate is available: for finite constants K0 , K1 , 4
E ∥Xk ∥ ≤ K0 αk2 ,
4
E ∥Yk ∥ ≤ K1 k̄ −2a ,
k ≥ 0.
Then the localized recursion satisfies Assumption 4.1. Consequently, the conclusion of Theorem 4.2 holds. 8
(48)
A PREPRINT - J UNE 15, 2026
5
Proof ideas
All proofs are given in full detail in the appendix. We summarize the main mechanisms here. Throughout this discussion, write k̄ = k + k0 , s = a(1 + ρ). The proof separates three effects in the slow recursion: ordinary slow noise, locally linear leakage from the fast tracking error, and nonlinear predictable bias. Fast fluctuation scale. The fast recursion is stable and is driven by noise through the stepsize αk . A standard Lyapunov calculation therefore gives 2
4
E ∥Xk ∥ = O(αk2 ).
E ∥Xk ∥ = O(αk ), By interpolation, 2+2ρ
E ∥Xk ∥ Thus the natural size of the fast tracking error is
∥Xk ∥ ≈ Consequently, a nonlinear remainder satisfying
√
= O(αk1+ρ ).
αk ≍ k̄ −a/2 .
∥R(x)∥ ≲ ∥x∥
1+ρ
has typical magnitude (1+ρ)/2
∥R(Xk )∥ ≈ αk This is the source of the phase-transition exponent. Unrolling the slow recursion.
≍ k̄ −a(1+ρ)/2 .
Let ΠB i,k =
k−1 Y
ΠB i,k
(I − βℓ B),
≤C
ℓ=i
i + k0 k + k0
r .
Unrolling the slow recursion gives Yk = ΠB 0,k Y0 +
X
β j ΠB j+1,k HXj +
j<k
X
β j ΠB j+1,k R(Xj ) +
j<k
X
β j ΠB j+1,k ζj+1 .
j<k
The initial-condition term decays faster than the rates of interest once the slow contraction is chosen sufficiently strong. The slow-noise term is standard. Since ζj+1 is a martingale difference, 2
E
X
β j ΠB j+1,k ζj+1
≤C
j<k
This is the intrinsic k
−1
X j<k
βj2
j + k0 k + k0
2r
= O(k̄ −1 ).
noise floor of the slow stochastic approximation.
The nonlinear remainder. The nonlinear term is bounded directly. By Minkowski’s inequality and the fast moment estimate, 2 1/2 1/2 X j + k0 r X 2+2ρ β j ΠB R(X ) ≤ C β E ∥X ∥ E j j j j+1,k k + k0 j<k
j<k
≤C
X j<k
1 j + k0
j + k0 k + k0
r
(j + k0 )−a(1+ρ)/2 .
A weighted-convolution estimate gives an L2 bound of order O k̄ − min{r,a(1+ρ)/2} up to a logarithm in the borderline case. After squaring, this is always bounded by O k̄ −1 + k̄ −a(1+ρ) , because r > 1/2. This term is not improved by averaging because it is a predictable drift input rather than a martingale-centered fluctuation. 9
A PREPRINT - J UNE 15, 2026
Locally linear leakage and Abel cancellation. The locally linear term HXj is subtler. A direct estimate using 2 E ∥Xj ∥ = O(αj ) would only give the slower O(k −a ) rate. The key point is that Xj is not an arbitrary error sequence; it is generated by a stable fast recursion. From Xj+1 = (I − αj A)Xj + αj ξj+1 , we obtain the identity AXj = αj−1 (Xj − Xj+1 ) + ξj+1 . With CH = HA−1 , X
β j ΠB j+1,k HXj =
j<k
X
β j ΠB j+1,k CH ξj+1
j<k
+
X βj j<k
αj
ΠB j+1,k CH (Xj − Xj+1 ).
The first term is again a martingale convolution and has mean square O(k̄ −1 ). The second term is handled by summation by parts. The boundary coefficients are of order βk ≍ k̄ a−1 . αk 2
Since E ∥Xk ∥ = O(k̄ −a ), the terminal boundary term contributes 2 βk 2 E ∥Xk ∥ = O(k̄ a−2 ) ≤ O(k̄ −1 ). αk The initial boundary is negligible by contraction, and the interior coefficient differences are small enough to give the same rate. This summation-by-parts step is the Abel-transform form of averaged-noise cancellation: locally linear leakage from the fast recursion averages down to the slow k −1 noise floor. Combining the three contributions yields 2 E ∥Yk ∥ ≤ C k̄ −1 + k̄ −a(1+ρ) . Why the lower bound matches. The lower bound uses a scalar Gaussian normal form. In that example, the fast variable is Gaussian with variance EXk2 = Θ(αk ). Therefore (1+ρ)/2 E|Xk |1+ρ = Θ αk = Θ k̄ −a(1+ρ)/2 . The slow recursion contains the positive predictable drift input γ|Xk |1+ρ . Summing the slow recursion over the window j ∈ [k/2, k], where the slow transition weights remain uniformly comparable to constants and the input varies only polynomially, gives EYk ≥ ck̄ −a(1+ρ)/2 . Hence
EYk2 ≥ (EYk )2 ≥ ck̄ −a(1+ρ) . If the slow Gaussian noise level is nonzero, the usual martingale variance calculation gives the additional lower bound ck̄ −1 . Thus the upper bound is sharp uniformly over the normal-form class. Centering and debiasing. The centering result explains why the obstruction is not the size of the nonlinear term ek+1 satisfying alone. Suppose the nonlinear input is replaced by a martingale-centered fluctuation R 2
ek+1 | Fk ] = 0, E[R
ek+1 E R
≲ αk1+ρ .
Then its slow convolution satisfies 2
E
X j<k
e β j ΠB j+1,k Rj+1
≤C
X j<k
βj2
j + k0 k + k0
2r
αj1+ρ ≤ C k̄ −1 .
Thus a nonlinear term of the same instantaneous magnitude does not slow the slow iterate when it is martingale-centered. The rate loss comes from persistent predictable bias. 10
A PREPRINT - J UNE 15, 2026
Online bias tracking.
The bias-tracking recursion removes the predictable component without an oracle. Since Mk+1 − Mk = γk R(Xk ) − Mk ,
the corrected nonlinear input satisfies R(Xk ) − Mk = γk−1 (Mk+1 − Mk ). Therefore its slow convolution is X X βj B β j ΠB Π (Mj+1 − Mj ). j+1,k R(Xj ) − Mj = γj j+1,k j<k
j<k
This is another Abel-transform term. The tracker itself satisfies ∥Mk ∥L2 = O(k̄ −s/2 ), because it is an exponentially weighted average of inputs R(Xj ) of L2 size O(j̄ −s/2 ). The coefficient βj /γj ≍ j̄ c−1 is small because the tracking time scale is faster than the slow time scale. The condition c < min{1, (1 + s)/2} ensures that the boundary and coefficient-variation terms in this Abel transform have L2 size O(k̄ −1/2 ). Thus the tracked nonlinear residual contributes only O(k̄ −1 ) to the slow mean-square error. Localized nonlinear transfer. fast-manifold error
For nonlinear TTSA, the same argument is applied after changing coordinates to the
Xk = xk − λ(yk ), Yk = yk − y ∗ . Here λ(y) is the equilibrium of the fast mean field with the slow variable frozen. Because this target moves with yk , the X-recursion contains additional perturbations beyond the normal form. Assumption 4.1 collects these perturbations as pk+1 , dk , and ek . The proof of the transfer theorem repeats the normal-form decomposition. The slow error is unrolled into the same three main terms, plus perturbation convolutions. The direct slow perturbation ek is controlled by the same convolution estimate used for R(Xk ). The perturbations in the fast recursion are handled through the Abel transform for the locally linear term HXk . Terms entering the fast recursion at the βk scale acquire an additional factor βk /αk after the transform; since βk /αk ≍ k̄ a−1 and a < 1, these terms remain below the phase-transition rate under the stated moment bounds. The verification propositions show that the required perturbation bounds follow from local Taylor expansions of h and g, bounded derivatives of the manifold λ, and the corresponding localized moment estimates.
6
Conclusion and Discussion
This paper identifies a regularity-dependent boundary for the uncorrected normal-form recursion in nonlinear two-timescale stochastic approximation. Locally linear fast-error leakage averages down to the intrinsic O(k −1 ) slow noise floor, while a nonlinear remainder of order 1 + ρ creates a predictable bias at the fast fluctuation scale. This yields the sharp rate 2 E ∥Yk ∥ ≤ C k −1 + k −a(1+ρ) , with a matching scalar lower bound. Thus, for the uncorrected normal-form recursion, the decoupled O(k −1 ) rate is guaranteed uniformly precisely when a(1 + ρ) ≥ 1. The lower bound also identifies how to beat it. It is not an information-theoretic impossibility result for the normal-form problem class; it is the bias of a particular update rule. The online tracker Mk+1 = Mk + γk R(Xk ) − Mk estimates the predictable nonlinear component on an intermediate time scale, and subtracting Mk from the slow update restores 2 E Yek = O(k −1 ) for every ρ ∈ [0, 1]. The proof uses a second Abel transform, now applied to R(Xk ) − Mk = γk−1 (Mk+1 − Mk ). The localized transfer results show that the same phase-transition mechanism persists for nonlinear TTSA in fastmanifold coordinates under the stated localized moment estimates. Extending the online bias tracker beyond the normal form is a natural next step, but it requires a way to observe or estimate the hidden coupling error g(xk , yk ) − g(x∗ (yk ), yk ). Other directions include simulator-based batching or multilevel debiasing for general TTSA, highprobability analogues, and non-asymptotic central limit theorems with the nonlinear bias explicitly centered. 11
A PREPRINT - J UNE 15, 2026
References [1] H. Robbins and S. Monro. A stochastic approximation method. The Annals of Mathematical Statistics, 22(3):400– 407, 1951. [2] H. J. Kushner and G. G. Yin. Stochastic Approximation and Recursive Algorithms and Applications. Springer, 2003. [3] V. S. Borkar. Stochastic Approximation: A Dynamical Systems Viewpoint. Cambridge University Press, 2008. [4] V. R. Konda and J. N. Tsitsiklis. Convergence rate of linear two-time-scale stochastic approximation. The Annals of Applied Probability, 14(2):796–819, 2004. [5] M. Kaledin, E. Moulines, A. Naumov, V. Tadic, and H.-T. Wai. Finite time analysis of linear two-timescale stochastic approximation with markovian noise. In Conference on Learning Theory, pages 2144–2203. PMLR, 2020. [6] Shaan Ul Haque, Sajad Khodadadian, and Siva Theja Maguluri. Tight finite time bounds of two-time-scale linear stochastic approximation with markovian noise. arXiv preprint arXiv:2401.00364, 2023. [7] T. T. Doan. Nonlinear two-time-scale stochastic approximation: convergence and finite-time performance. IEEE Transactions on Automatic Control, 68(8):4695–4705, 2023. [8] Siddharth Chandak. o(1/k) finite-time bound for non-linear two-time-scale stochastic approximation. IEEE Transactions on Automatic Control, 2026. [9] Yuze Han, Xiang Li, and Zhihua Zhang. Finite-time decoupled convergence in nonlinear two-time-scale stochastic approximation. arXiv preprint arXiv:2401.03893, 2024.
12
A PREPRINT - J UNE 15, 2026
A
Deterministic estimates
Throughout the appendix, C denotes a finite positive constant whose value may change from line to line but depends only on the fixed problem parameters. It never depends on k or on summation indices. Recall that k̄ = k + k0 . For 0 ≤ i ≤ k, define the slow transition matrix (I − βk−1 B)(I − βk−2 B) · · · (I − βi B), B Πi,k := I,
i < k, i = k.
(49)
The order of multiplication is irrelevant for the estimates because every factor is a polynomial in the same matrix B, but the displayed convention matches the recursion. Lemma A.1 (Polynomial decay of the slow transition). Under Assumption 2.1, for all 0 ≤ i ≤ k, r ī B Πi,k ≤ , r = bβ0 . (50) k̄ Proof. If i = k, then (50) is equality. Assume i < k. By (10), ΠB i,k
≤
k−1 Y
(1 − bβℓ ) ≤ exp −b
ℓ=i
k−1 X
! βℓ
,
ℓ=i
where we used 1 − u ≤ e−u for u ≥ 0. Since βℓ = β0 /(ℓ + k0 ), k−1 X
βℓ = β0
ℓ=i
k−1 X ℓ=i
1 ≥ β0 ℓ + k0
Z k i
dt = β0 log t + k0
k̄ . ī
Combining the two inequalities gives ΠB i,k
bβ0 ī k̄ = . ≤ exp −bβ0 log ī k̄
This proves the lemma. Lemma A.2 (Weighted convolution estimates). Let u ≥ 0 and r > 0. Then, for all k ≥ 1, −u u < r, k−1 k̄ , X −u −r β j ΠB j̄ ≤ C k̄ log( k̄), u = r, j+1,k −r j=0 k̄ , u > r.
(51)
Consequently, if r > 1/2, then 2
k−1 X
−u β j ΠB ≤ C k̄ −1 + k̄ −2u . j+1,k j̄
(52)
j=0
If r > 1/2, then, for all k ≥ 1, k−1 X
βj2 ΠB j+1,k
2
≤ C k̄ −1 .
(53)
j=0
Proof. For (51), Lemma A.1 gives k−1 X
−u β j ΠB ≤ β0 j+1,k j̄
j=0
Because k0 ≥ 2, j + 1 = j̄ + 1 ≤ 2j̄. Therefore
k−1 X j=0
j+1 k̄
r
j̄ −1
j+1 k̄
≤ 2r k̄ −r j̄ r ,
13
r
j̄ −u .
A PREPRINT - J UNE 15, 2026
and hence
k−1 X
−u β j ΠB ≤ C k̄ −r j+1,k j̄
j=0
k−1 X
j̄ r−u−1 .
(54)
j=0
If r − u > 0, the sum in (54) is at most C k̄ r−u . If r − u = 0, it is at most C log(k̄). If r − u < 0, it is bounded by a constant. These three cases prove (51). We next prove (52). If u < r, then (51) gives C k̄ −2u . If u > r, then it gives C k̄ −2r ≤ C k̄ −1 because r > 1/2. If u = r, then 2u = 2r > 1, and k̄ −2r (log k̄)2 ≤ C k̄ −1 . Thus (52) holds in all cases. For (53), again by Lemma A.1, k−1 X
βj2 ΠB j+1,k
2
≤ C k̄ −2r
j=0
k−1 X
j̄ 2r−2 .
j=0 2r−1
Since 2r − 2 > −1 is equivalent to r > 1/2, the sum is at most C k̄ C k̄ −1 .
. Therefore the last display is bounded by
Lemma A.3 (Abel coefficient bounds). Let CH = HA−1 and define, for 0 ≤ j ≤ k − 1, βj B Qj,k := Π CH . αj j+1,k Then ∥Qj,k ∥ ≤ C k̄ −r j̄ r+a−1 , ∥Qj,k − Qj−1,k ∥ ≤ C k̄
−r r+a−2
j̄
1 ≤ j ≤ k − 1.
,
(55)
(56) (57)
Proof. First, βj β0 a−1 = j̄ . αj α0 Using Lemma A.1, β0 ∥Qj,k ∥ ≤ ∥CH ∥ j̄ a−1 α0
j+1 k̄
r
≤ C k̄ −r j̄ r+a−1 ,
which proves (56). For the variation bound, write qj :=
βj β0 a−1 = j̄ . αj α0
Then B Qj,k − Qj−1,k = qj ΠB j+1,k − qj−1 Πj,k CH B B = (qj − qj−1 )ΠB j+1,k CH + qj−1 Πj+1,k − Πj,k CH . Because a − 1 < 0, the map t 7→ (t + k0 )a−1 is differentiable with derivative of magnitude (1 − a)(t + k0 )a−2 . The mean-value theorem gives |qj − qj−1 | ≤ C j̄ a−2 . (58) Moreover, from the definition of the transition matrix, B ΠB j,k = Πj+1,k (I − βj B), so B B ΠB (59) j+1,k − Πj,k = βj Πj+1,k B. Combining (58), (59), Lemma A.1, and qj−1 ≤ C j̄ a−1 yields r r j+1 j+1 ∥Qj,k − Qj−1,k ∥ ≤ C j̄ a−2 + C j̄ a−1 βj k̄ k̄ a−2 −r r a−1 −1 −r r ≤ C j̄ k̄ j̄ + C j̄ j̄ k̄ j̄ ≤ C k̄ −r j̄ r+a−2 . This proves (57). 14
A PREPRINT - J UNE 15, 2026
B
Proof of the upper bound
We now prove Theorem 3.1. The proof is divided into three lemmas and then assembled. Lemma B.1 (Fast moments). Under Assumption 2.1, there exists C < ∞ such that, for every k ≥ 0, 2
E ∥Xk ∥ ≤ Cαk2 .
4
(60)
≤ Cαk1+ρ .
(61)
E ∥Xk ∥ ≤ Cαk , Consequently, for every ρ ∈ [0, 1], E ∥Xk ∥
2+2ρ
Proof. Let Dk = I − αk A. By Assumption 2.1, ∥Dk ∥ ≤ 1 − λαk . Second moment.
Conditioning on Fk and using E[ξk+1 | Fk ] = 0, 2
2
E[∥Xk+1 ∥ | Fk ] = E[∥Dk Xk + αk ξk+1 ∥ | Fk ] 2
2
= ∥Dk Xk ∥ + 2αk ⟨Dk Xk , E[ξk+1 | Fk ]⟩ + αk2 E[∥ξk+1 ∥ | Fk ] 2
≤ (1 − λαk )2 ∥Xk ∥ + σ42 αk2 . Since λαk ≤ 1 after increasing k0 if necessary, (1 − λαk )2 ≤ 1 − λαk . Thus 2
mk+1 ≤ (1 − λαk )mk + σ42 αk2 ,
mk := E ∥Xk ∥ .
(62)
We prove mk ≤ C2 αk by induction. Since X0 is deterministic and α0 in the display below denotes the fixed numerator in the stepsize formula, choose C2 so large that m0 ≤ C2 α0 k0−a . Because αk = α0 k̄ −a , a −a αk+1 k̄ 1 = = 1+ . αk k̄ + 1 k̄ The inequality (1 + t)−a ≥ 1 − at for t ≥ 0 gives a αk+1 ≥ αk 1 − . k̄
(63)
Since a < 1, we have k̄ −1 = o(αk ) because αk = α0 k̄ −a . Hence, after increasing k0 if necessary, λ a ≤ αk , 2 k̄
k ≥ 0.
(64)
λ 1 − αk . 2
(65)
Combining (63) and (64), αk+1 ≥ αk Assume mk ≤ C2 αk . From (62), mk+1 ≤ C2 αk (1 − λαk ) + σ42 αk2 = C2 αk
σ42 1 − λαk + αk . C2
Choose C2 ≥ 2σ42 /λ. Then λ mk+1 ≤ C2 αk 1 − αk ≤ C2 αk+1 , 2 where the last inequality uses (65). This completes the induction and proves mk ≤ C2 αk . Fourth moment.
Let u = Dk Xk and v = αk ξk+1 . The identity 4
2
2
∥u + v∥ = (∥u∥ + 2 ⟨u, v⟩ + ∥v∥ )2 expands as 4
4
2
2
2
∥u + v∥ = ∥u∥ + 4 ∥u∥ ⟨u, v⟩ + 2 ∥u∥ ∥v∥ + 4 ⟨u, v⟩ 2
4
+ 4 ⟨u, v⟩ ∥v∥ + ∥v∥ . 15
2
A PREPRINT - J UNE 15, 2026
2
Taking conditional expectation, the term 4 ∥u∥ ⟨u, v⟩ vanishes because E[v | Fk ] = 0. For the remaining terms, using ∥u∥ ≤ ∥Xk ∥ and (12), 2
2
2
E[2 ∥u∥ ∥v∥ | Fk ] ≤ 2σ42 αk2 ∥Xk ∥ , 2
2
2
2
E[4 ⟨u, v⟩ | Fk ] ≤ 4 ∥u∥ E[∥v∥ | Fk ] ≤ 4σ42 αk2 ∥Xk ∥ , 4
E[∥v∥ | Fk ] ≤ σ44 αk4 . For the mixed cubic term, first use Cauchy’s inequality and Jensen’s inequality: 2
3
E[4 ⟨u, v⟩ ∥v∥ | Fk ] ≤ 4 ∥u∥ E[∥v∥ | Fk ] ≤ 4σ43 αk3 ∥Xk ∥ . We now apply Young’s inequality in the form c1 αk3 t ≤
λ 11/3 αk t4 + Cαk , 4
t ≥ 0, 11/3
which follows from ab ≤ εa4 + Cε−1/3 b4/3 by taking a = t, b = c1 αk3 , and ε = (λ/4)αk . Since αk ≤ 1, αk Therefore λ 2 4 E[4 ⟨u, v⟩ ∥v∥ | Fk ] ≤ αk ∥Xk ∥ + Cαk3 . 4 Finally, 4 4 ∥u∥ ≤ (1 − λαk )4 ∥Xk ∥ .
≤ αk3 . (66)
For λαk ≤ 1/4, the elementary inequality (1 − x)4 ≤ 1 −
15 x, 8
0≤x≤
1 , 4
with x = λαk gives 15λ 4 1− αk ∥Xk ∥ . 8 Combining this estimate with (66) and the remaining second- and fourth-order noise terms gives 13λ 4 4 2 E[∥Xk+1 ∥ | Fk ] ≤ 1 − αk ∥Xk ∥ + Cαk2 ∥Xk ∥ + Cαk3 . 8 4
∥u∥ ≤
Absorbing constants and taking expectation, nk+1 ≤ (1 − c4 αk )nk + Cαk2 mk + Cαk3 ,
4
nk := E ∥Xk ∥ ,
(67)
for c4 = 13λ/8 replaced by any smaller positive constant. The already-proved second moment bound gives mk ≤ Cαk , hence nk+1 ≤ (1 − c4 αk )nk + Cαk3 . (68) We prove nk ≤ C4 αk2 by induction. Choose C4 so large that n0 ≤ C4 (α0 k0−a )2 . Since −2a 2 αk+1 2a 1 ≥1− , = 1+ αk2 k̄ k̄ and since k̄ −1 = o(αk ), after increasing k0 if necessary, c4 2 αk+1 ≥ αk2 1 − αk . 2 Assume nk ≤ C4 αk2 . From (68), nk+1 ≤ C4 αk2 (1 − c4 αk ) + Cαk3 = C4 αk2 Choosing C4 ≥ 2C/c4 gives
C 1 − c4 αk + αk . C4
c4 2 nk+1 ≤ C4 αk2 1 − αk ≤ C4 αk+1 . 2 This completes the induction and proves the fourth moment bound. 16
(69)
A PREPRINT - J UNE 15, 2026
Interpolation.
Let p = 2 + 2ρ ∈ [2, 4]. By Lyapunov’s inequality, p/4 p/4 p/2 p 4 = Cαk = Cαk1+ρ . E ∥Xk ∥ ≤ E ∥Xk ∥ ≤ C αk2
This proves (61) and the lemma. Lemma B.2 (Averaging of the locally linear fast leakage). Under Assumptions 2.1 and 2.3, k−1 X
E
2
≤ C k̄ −1 .
β j ΠB j+1,k HXj
(70)
j=0
Proof. Let CH = HA−1 . From the fast recursion, Xj+1 = Xj − αj AXj + αj ξj+1 . Rearranging, Multiplying by HA
−1
AXj = αj−1 (Xj − Xj+1 ) + ξj+1 .
(71)
HXj = CH αj−1 (Xj − Xj+1 ) + CH ξj+1 .
(72)
= CH gives
Therefore k−1 X
β j ΠB j+1,k HXj = Mk + Tk ,
(73)
j=0
Mk :=
k−1 X
β j ΠB j+1,k CH ξj+1 ,
(74)
Qj,k (Xj − Xj+1 ),
(75)
j=0
Tk :=
k−1 X j=0
where Qj,k is defined in (55). We first bound Mk . For i < j, the random vector ξi+1 is Fj -measurable and E[ξj+1 | Fj ] = 0. Hence cross terms vanish. Thus k−1 X 2 2 E ∥Mk ∥ = βj2 E ΠB j+1,k CH ξj+1 j=0 2
≤ ∥CH ∥
σ42
k−1 X
βj2 ΠB j+1,k
2
≤ C k̄ −1 ,
j=0
where the last step uses Lemma A.2 and r > 1/2. We now bound Tk . Abel summation gives Tk = Q0,k X0 − Qk−1,k Xk +
k−1 X
(Qj,k − Qj−1,k )Xj .
j=1
Indeed, expanding the right-hand side produces Q0,k X0 +
k−1 X
Qj,k Xj −
j=1
k−1 X
Qj−1,k Xj − Qk−1,k Xk =
j=1
k−1 X j=0
We treat the three terms in (76) separately. By Lemma A.3, 2
2
∥Q0,k X0 ∥ ≤ C k̄ −2r ∥X0 ∥ ≤ C k̄ −1 , 17
Qj,k (Xj − Xj+1 ).
(76)
A PREPRINT - J UNE 15, 2026
because r > 1/2. For the terminal boundary term, Lemma A.3 and Lemma B.1 imply 2
2
E ∥Qk−1,k Xk ∥ ≤ C k̄ 2a−2 E ∥Xk ∥ ≤ C k̄ 2a−2 αk ≤ C k̄ a−2 . Since a < 1, k̄ a−2 ≤ C k̄ −1 . It remains to bound the interior sum. By the triangle inequality in L2 , 2 1/2 k−1 k−1 1/2 X X 2 ≤ (Qj,k − Qj−1,k )Xj ∥Qj,k − Qj−1,k ∥ E ∥Xj ∥ E j=1
j=1
≤ C k̄ −r
k−1 X
1/2
j̄ r+a−2 αj
j=1
≤ C k̄ −r
k−1 X
j̄ r+a−2−a/2
j=1
= C k̄ −r
k−1 X
j̄ r+a/2−2 .
j=1
If r + a/2 − 2 < −1, then the sum is bounded by a constant, and the squared expression is at most C k̄ −2r ≤ C k̄ −1 . If r + a/2 − 2 = −1, then the sum is at most C log(k̄), and the squared expression is at most C k̄ −2r (log k̄)2 ≤ C k̄ −1 because r > 1/2. If r + a/2 − 2 > −1, then the sum is at most C k̄ r+a/2−1 , and the squared expression is at most C k̄ −2r k̄ 2r+a−2 = C k̄ a−2 ≤ C k̄ −1 . Thus the interior term also has second moment at most C k̄ −1 . Using (u + v)2 ≤ 2u2 + 2v 2 in (73), and using the bounds for Mk and Tk , proves (70). Lemma B.3 (Nonlinear and slow-noise convolutions). Under Assumptions 2.1, 2.2, and 2.3,
E
k−1 X
2
β j ΠB j+1,k R(Xj )
≤ C k̄ −1 + k̄ −s ,
(77)
≤ C k̄ −1 .
(78)
j=0
E
k−1 X
2
β j ΠB j+1,k ζj+1
j=0
Proof. For the nonlinear term, the triangle inequality in L2 , Assumption 2.2, and Lemma B.1 give 2 1/2 k−1 X β j ΠB E j+1,k R(Xj ) j=0
≤
k−1 X
β j ΠB j+1,k
E ∥R(Xj )∥
2
1/2
j=0
≤ LR
k−1 X
β j ΠB j+1,k
j=0
≤C
k−1 X
(1+ρ)/2
β j ΠB j+1,k αj
j=0
≤C
k−1 X
−s/2 β j ΠB . j+1,k j̄
j=0
18
2+2ρ
E ∥Xj ∥
1/2
A PREPRINT - J UNE 15, 2026
By (52) with u = s/2, E
k−1 X
2
≤ C k̄ −1 + k̄ −s .
β j ΠB j+1,k R(Xj )
j=0
This proves (77). For the slow-noise convolution, martingale cross terms vanish exactly as in the proof of Lemma B.2. Hence E
k−1 X
2
β j ΠB j+1,k ζj+1
=
j=0
k−1 X
2
βj2 E ΠB j+1,k ζj+1
j=0
≤ σ42
k−1 X
βj2 ΠB j+1,k
2
≤ C k̄ −1 ,
j=0
where the last inequality is (53). This proves (78). Proof of Theorem 3.1. Unroll the slow recursion (9) to obtain Yk = ΠB 0,k Y0 +
k−1 X
β j ΠB j+1,k HXj +
j=0
k−1 X
β j ΠB j+1,k R(Xj ) +
j=0
k−1 X
β j ΠB j+1,k ζj+1 .
j=0
2
Using (a1 + a2 + a3 + a4 ) ≤ 4(a21 + a22 + a23 + a24 ) for nonnegative scalars, 2 k−1 X 2 2 + 4E E ∥Yk ∥ ≤ 4 ΠB β j ΠB 0,k Y0 j+1,k HXj j=0 k−1 X
+ 4E
2
β j ΠB j+1,k R(Xj )
k−1 X
+ 4E
2
β j ΠB j+1,k ζj+1
.
j=0
j=0
The initial term satisfies, by Lemma A.1, ΠB 0,k Y0
2
2
≤ C k̄ −2r ∥Y0 ∥ .
Because r > 1/2, we have 2r > 1, and therefore k̄ −2r ≤ C k̄ −1 ≤ C(k̄ −1 + k̄ −s ). The locally linear term is bounded by Lemma B.2; the nonlinear term and slow-noise term are bounded by Lemma B.3. Combining these estimates gives 2 E ∥Yk ∥ ≤ C k̄ −1 + k̄ −s . The moment estimates for Xk are exactly Lemma B.1. This completes the proof.
C
Proof of the centering principle
Proof of Proposition 3.6. Unrolling (23) gives Yk = ΠB 0,k Y0 +
k−1 X
β j ΠB j+1,k HXj +
j=0
+
k−1 X
The initial term satisfies ΠB 0,k Y0
β j ΠB j+1,k mj
j=0
β j ΠB j+1,k νj+1 +
j=0 2
k−1 X
k−1 X
β j ΠB j+1,k ζj+1 .
j=0
≤ C k̄ −2r ≤ C k̄ −1 because r > 1/2. Lemma B.2 gives
E
k−1 X
2
β j ΠB j+1,k HXj
j=0
19
≤ C k̄ −1 .
A PREPRINT - J UNE 15, 2026
The slow martingale noise is bounded as in Lemma B.3:
E
k−1 X
2
≤ C k̄ −1 .
β j ΠB j+1,k ζj+1
j=0
We next treat the predictable component mj . By the L2 triangle inequality, (25), and Lemma A.1, 2 1/2 k−1 k−1 X X 2 1/2 −r ≤ C k̄ j̄ r−1 E ∥mj ∥ β j ΠB m E j+1,k j j=0
j=0
k−1 X
≤ C k̄ −r
j̄ r−q−1 .
j=0
If q < r, the last sum is at most C k̄ r−q ; if q = r, it is at most C log(k̄); if q > r, it is bounded by a constant. Therefore
E
k−1 X
2
β j ΠB j+1,k mj
≤ CΨq (k)2 .
(79)
j=0
It remains to control the martingale-centered nonlinear fluctuation. Since νj+1 is a martingale difference and the matrices βj ΠB j+1,k are Fj -measurable deterministic coefficients, cross terms vanish. Hence, using (24),
E
k−1 X
2
β j ΠB j+1,k νj+1
≤C
j=0
k−1 X
βj2 ΠB j+1,k
2
αj1+ρ
j=0 k−1 X
≤ C k̄ −2r
j̄ 2r−2−s ,
j=0
where s = a(1 + ρ). If 2r − 2 − s < −1, the sum is bounded, and the display is at most C k̄ −2r ≤ C k̄ −1 . If 2r − 2 − s = −1, the display is at most C k̄ −2r log(k̄), which is O(k̄ −1 ) because 2r = s + 1 > 1. If 2r − 2 − s > −1, the sum is at most C k̄ 2r−1−s , and the display is at most C k̄ −1−s ≤ C k̄ −1 . Thus
E
k−1 X
2
β j ΠB j+1,k νj+1
≤ C k̄ −1 .
(80)
j=0
Combining the five displayed bounds and using ∥z1 + · · · + z5 ∥2 ≤ 5 is absent, and the rate is C k̄ −1 .
D
P
i ∥zi ∥
2
proves (27). If mk ≡ 0, the term (79)
Proof of online bias tracking
This appendix proves Theorem 3.7. The argument has two steps. First, the tracker Mk inherits the L2 decay of the nonlinear input R(Xk ). Second, the corrected residual R(Xk ) − Mk is written as a scaled difference of consecutive tracker values, so its slow convolution is controlled by Abel summation. For 0 ≤ i ≤ k, define the scalar tracking transition (Q k−1 γ ℓ=i (1 − γℓ ), Πi,k = 1,
i < k, i = k.
Lemma D.1 (Moment bound for the bias tracker). Under the assumptions of Theorem 3.7, 2 1/2 E ∥Mk ∥ ≤ C k̄ −s/2 , k ≥ 1. 2
Consequently, E ∥Mk ∥ ≤ C k̄ −s . 20
A PREPRINT - J UNE 15, 2026
Proof. Unrolling (31) gives Mk = Πγ0,k M0 +
k−1 X
γi Πγi+1,k R(Xi ).
i=0
By Assumption 2.2 and Lemma B.1, E ∥R(Xi )∥
2 1/2
2+2ρ 1/2
(1+ρ)/2
≤ LR E ∥Xi ∥
≤ Cαi
≤ C ī−s/2 .
Thus, by the L2 triangle inequality, ∥Mk ∥L2 ≤ Πγ0,k ∥M0 ∥ + C
k−1 X
γi Πγi+1,k ī−s/2 .
(81)
i=0
We bound the two terms on the right. Because c < 1 and γi = γ0 ī−c , k−1 X
γi ≥ c0 k̄ 1−c
i=0
for all k and a constant c0 > 0 after changing constants for small k. Hence ! k−1 X γ γi ≤ exp(−c0 k̄ 1−c ) ≤ C k̄ −s/2 . Π0,k ≤ exp − i=0
This controls the initial term. For the convolution term, split the sum in (81) at ⌊k/2⌋. If i ≤ k/2, then k−1 X
γℓ ≥ c1 k̄ 1−c
ℓ=i+1
for some c1 > 0, and therefore γi Πγi+1,k ī−s/2 ≤ C ī−c−s/2 e−c1 k̄
1−c
.
Summing over i ≤ k/2 gives at most C k̄ −s/2 , because the stretched-exponential factor dominates every polynomial. If i > k/2, then ī−s/2 ≤ C k̄ −s/2 , and k−1 X
γi Πγi+1,k ≤
k−1 X
γi Πγi+1,k = 1 − Πγ0,k ≤ 1.
i=0
i=⌊k/2⌋+1
Therefore the recent half of the sum is also at most C k̄ −s/2 . Combining the initial, early, and recent bounds proves the lemma. Lemma D.2 (Abel bound for the tracked residual). Under the assumptions of Theorem 3.7,
E
k−1 X
2
β j ΠB j+1,k
R(Xj ) − Mj
≤ C k̄ −1 .
j=0
Proof. From (31),
R(Xj ) − Mj = γj−1 (Mj+1 − Mj ).
Define qj =
βj β0 c−1 = j̄ , γj γ0
Qj,k = qj ΠB j+1,k ,
0 ≤ j ≤ k − 1.
Then Sk :=
k−1 X
X k−1 β j ΠB R(X ) − M Qj,k (Mj+1 − Mj ). j j = j+1,k
j=0
j=0
21
(82)
A PREPRINT - J UNE 15, 2026
Abel summation gives Sk = −Q0,k M0 + Qk−1,k Mk +
k−1 X
(Qj−1,k − Qj,k )Mj .
(83)
j=1
We first record coefficient bounds. Lemma A.1 gives ∥Qj,k ∥ ≤ C k̄ −r j̄ r+c−1 .
(84)
Moreover, the same calculation as in Lemma A.3, with a replaced by c, yields ∥Qj,k − Qj−1,k ∥ ≤ C k̄ −r j̄ r+c−2 ,
1 ≤ j ≤ k − 1.
(85)
Indeed, |qj − qj−1 | ≤ C j̄ c−2 and qj−1 βj ≤ C j̄ c−2 . We now bound the three terms in (83). The initial boundary satisfies 2
2
∥Q0,k M0 ∥ ≤ C k̄ −2r ∥M0 ∥ ≤ C k̄ −1 , because r > 1/2. For the terminal boundary, (84) and Lemma D.1 give 2
2
E ∥Qk−1,k Mk ∥ ≤ C k̄ 2c−2 E ∥Mk ∥ ≤ C k̄ 2c−2−s . The condition c < (1 + s)/2 implies 2c − 2 − s < −1, and hence this term is at most C k̄ −1 . For the interior term, the L2 triangle inequality, (85), and Lemma D.1 imply k−1 X
≤ C k̄ −r
(Qj−1,k − Qj,k )Mj
j=1
k−1 X
j̄ r+c−2 j̄ −s/2
j=1
L2
= C k̄ −r
k−1 X
j̄ r+c−2−s/2 .
j=1
If r+c−2−s/2 < −1, the sum is bounded, so the squared expression is at most C k̄ −2r ≤ C k̄ −1 . If r+c−2−s/2 = −1, the sum is logarithmic, and C k̄ −2r (log k̄)2 ≤ C k̄ −1 because r > 1/2. If r + c − 2 − s/2 > −1, the sum is at most C k̄ r+c−1−s/2 , and the square is at most C k̄ −2r k̄ 2r+2c−2−s = C k̄ 2c−2−s ≤ C k̄ −1 , again by c < (1 + s)/2. Combining the three terms in (83) proves (82). Proof of Theorem 3.7. The estimate for Mk is Lemma D.1. It remains to prove the slow-rate estimate. Unrolling (32) gives e Yek = ΠB 0,k Y0 +
k−1 X
β j ΠB j+1,k HXj
j=0
+
k−1 X
X k−1 β j ΠB R(X ) − M β j ΠB j j + j+1,k j+1,k ζj+1 .
j=0
j=0
The initial term satisfies e ΠB 0,k Y0
2
≤ C k̄ −2r ≤ C k̄ −1
because r > 1/2. Lemma B.2 bounds the locally linear leakage by C k̄ −1 in mean square. Lemma D.2 bounds the corrected nonlinear residual by C k̄ −1 in mean square. Finally, Lemma B.3 bounds the slow martingale noise by C k̄ −1 P 2 2 in mean square. Using ∥z1 + z2 + z3 + z4 ∥ ≤ 4 i ∥zi ∥ proves 2
E Yek
≤ C k̄ −1 .
This proves the theorem. 22
A PREPRINT - J UNE 15, 2026
E
Proof of the localized nonlinear transfer theorem
This appendix proves Theorem 4.2 and Propositions 4.3 and 4.4. We first record a weighted-sum estimate that allows borderline logarithms. Lemma E.1 (General weighted convolution). Let u ≥ 0 and r > 0. Then, for all k ≥ 1, −u u < r, k−1 k̄ , X B −u −r βj Πj+1,k j̄ ≤ C k̄ log(k̄), u = r, (86) −r j=0 k̄ , u > r. In particular, if min{u, r} > v, then the square of the left-hand side is at most C k̄ −2v . Proof. By Lemma A.1 and the inequality j + 1 ≤ 2j̄, k−1 X
−u ≤ C k̄ −r β j ΠB j+1,k j̄
k−1 X
j̄ r−u−1 .
j=0
j=0
If r − u > 0, the sum is at most C k̄ r−u . If r − u = 0, the sum is at most C log(k̄). If r − u < 0, the sum is bounded by a constant because k0 ≥ 2 and the exponent r − u − 1 is strictly less than −1. These three cases give (86). If min{u, r} > v, the first and third cases give C k̄ −2v after squaring, while the borderline case gives C k̄ −2r (log k̄)2 ≤ C k̄ −2v because r > v. Lemma E.2 (Perturbed linear leakage). Under Assumption 4.1, E
k−1 X
2
≤ C k̄ −1 + k̄ −s .
β j ΠB j+1,k HXj
(87)
j=0
Proof. Let CH = HA−1 . Rearranging the perturbed fast recursion (36) gives AXj = αj−1 (Xj − Xj+1 ) + ξj+1 + pj+1 +
βj βj Cζ ζj+1 + dj . αj αj
(88)
Multiplying by HA−1 = CH and summing against the slow weights yields k−1 X
ξ ζ β j ΠB j+1,k HXj = Tk + Mk + Pk + Mk + Dk ,
(89)
j=0
Tk :=
k−1 X
Qj,k (Xj − Xj+1 ),
(90)
β j ΠB j+1,k CH ξj+1 ,
(91)
β j ΠB j+1,k CH pj+1 ,
(92)
j=0
Mkξ :=
k−1 X j=0
Pk :=
k−1 X j=0
Mkζ :=
k−1 X
β j ΠB j+1,k CH
βj Cζ ζj+1 , αj
(93)
β j ΠB j+1,k CH
βj dj , αj
(94)
j=0
Dk :=
k−1 X j=0
where Qj,k is defined in (55). The term Tk is the same Abel boundary term as in Lemma B.2. Its proof used only the coefficient bounds in Lemma A.3 2 and the moment estimate E ∥Xj ∥ ≤ Cαj . Therefore 2
E ∥Tk ∥ ≤ C k̄ −1 . 23
(95)
A PREPRINT - J UNE 15, 2026
The martingale term Mkξ is also the same as before, hence E Mkξ
2
≤ C k̄ −1 .
(96)
For Pk , the triangle inequality in L2 and (39) give E ∥Pk ∥
2 1/2
≤C
k−1 X
−µp β j ΠB . j+1,k j̄
j=0
By Lemma E.1, this is at most C k̄ we have νp > δ/2. Therefore
−νp
up to a logarithm, where νp = min{µp , r}. Since µp > δ/2 and r > 1/2 ≥ δ/2, 2 E ∥Pk ∥ ≤ C k̄ −δ ≤ C k̄ −1 + k̄ −s .
(97)
For Mkζ , martingale cross terms vanish. Since βj /αj = C j̄ a−1 , E Mkζ
2
≤C
k−1 X
βj2 ΠB j+1,k
2
j=0
≤ C k̄ −2r
k−1 X
βj αj
2
j̄ 2r+2a−4 .
j=0
If 2r+2a−4 < −1, the last sum is bounded by a constant and the result is at most C k̄ −2r ≤ C k̄ −1 . If 2r+2a−4 = −1, the sum is at most C log(k̄) and the result is at most C k̄ −2r log(k̄) ≤ C k̄ −1 because r > 1/2. If 2r + 2a − 4 > −1, the sum is at most C k̄ 2r+2a−3 , so the result is at most C k̄ 2a−3 . Since a < 1, 3 − 2a > 1, and again the term is O(k̄ −1 ). Thus E Mkζ
2
≤ C k̄ −1 .
(98)
It remains to bound Dk . By (40), 2 1/2
E ∥Dk ∥
≤C
k−1 X
a−1 −a/2 j̄ + j̄ −δ/2 β j ΠB j+1,k j̄
j=0
=C
k−1 X
−(1−a/2) β j ΠB +C j+1,k j̄
j=0
k−1 X
−(1−a+δ/2) β j ΠB . j+1,k j̄
j=0
The first exponent is u1 = 1 − a/2, and 2u1 = 2 − a ≥ 1 ≥ δ. The second exponent is u2 = 1 − a + δ/2, and u2 > δ/2 because a < 1. Since r > 1/2 ≥ δ/2, Lemma E.1 implies that both sums have squares bounded by C k̄ −δ . Hence 2 E ∥Dk ∥ ≤ C k̄ −δ ≤ C k̄ −1 + k̄ −s . (99) Combining (89)–(99) and using the elementary inequality ∥z1 + · · · + z5 ∥2 ≤ 5
P5
i=1 ∥zi ∥
2
proves (87).
Proof of Theorem 4.2. Unroll (37): Yk = ΠB 0,k Y0 +
k−1 X
β j ΠB j+1,k HXj +
j=0
+
k−1 X
k−1 X
β j ΠB j+1,k R(Xj )
j=0
β j ΠB j+1,k ζj+1 +
j=0
k−1 X
β j ΠB j+1,k ej .
j=0
2
The initial term satisfies ΠB ≤ C k̄ −2r ≤ C k̄ −1 because r > 1/2. The locally linear leakage term is bounded 0,k Y0 by Lemma E.2. The nonlinear remainder and slow martingale noise are bounded exactly as in Lemma B.3, using (38) in place of Lemma B.1. Thus they contribute C(k̄ −1 + k̄ −s ) and C k̄ −1 , respectively. 24
A PREPRINT - J UNE 15, 2026
For the additional slow perturbation, the L2 triangle inequality and (41) give 2 1/2 k−1 k−1 X X −δ/2 ≤C . β j ΠB β j ΠB E j+1,k ej j+1,k j̄ j=0
j=0
Since r > 1/2 ≥ δ/2, Lemma E.1 implies that the square of this term is at most C k̄ −δ . Because k̄ −δ ≤ C(k̄ −1 + k̄ −s ), all terms are bounded by the right-hand side of (42). This proves the theorem. Proof of Proposition 4.3. We verify Assumption 4.1 under the displayed local error recursions. Let Yk = yk − y ∗ ,
Xk = xk − λ(yk ),
x ξk+1 = Mk+1 ,
y ζk+1 = Mk+1 .
The slow recursion follows immediately from (44): Yk+1 = Yk + βk − BYk + HXk + R(Xk ) + E(Xk , yk ) + ζk+1 . Thus (37) holds with ek = E(Xk , yk ). By (44), (45), and Lyapunov’s inequality, (1+ρ)/2 2 1/2 2+2ρ 1/2 4 (1+ρ)/4 ≤ Lg E ∥Xk ∥ ≤ Lg E ∥Xk ∥ ≤ Cαk = C k̄ −s/2 ≤ C k̄ −δ/2 . E ∥ek ∥ This is (41). The first estimate in (38) follows from (45) by Jensen’s inequality: 2
4
E ∥Xk ∥ ≤ (E ∥Xk ∥ )1/2 ≤ Cαk . The second estimate in (38) is the same interpolation calculation: 2+2ρ
E ∥Xk ∥
4
≤ (E ∥Xk ∥ )(1+ρ)/2 ≤ Cαk1+ρ .
It remains to derive the perturbed fast recursion and the bounds on pk+1 and dk . By Taylor’s theorem applied to λ between yk and yk+1 , λ λ(yk+1 ) = λ(yk ) + Dλ(yk )(yk+1 − yk ) + rk+1 ,
2
λ rk+1 ≤ C ∥yk+1 − yk ∥ ,
(100)
where the constant C is the local bound on the Hessian of λ. Since yk+1 − yk = βk g(xk , yk ) + ζk+1 , and since (43) gives h(xk , yk ) = −AXk + P (Xk , yk ), we obtain Xk+1 = xk+1 − λ(yk+1 ) λ = xk + αk h(xk , yk ) + ξk+1 − λ(yk ) − Dλ(yk )βk g(xk , yk ) + ζk+1 − rk+1 = (I − αk A)Xk + αk ξk+1 + αk P (Xk , yk ) − βk Dλ(y ∗ )ζk+1 + βk dk , where
λ dk = −Dλ(yk )g(xk , yk ) − Dλ(yk ) − Dλ(y ∗ ) ζk+1 − βk−1 rk+1 .
(101)
Thus (36) holds with
pk+1 = P (Xk , yk ), Cζ = −Dλ(y ∗ ). The bound on pk+1 follows from (43) and (45): 2 1/2 4 1/2 E ∥pk+1 ∥ ≤ Lh E ∥Xk ∥ ≤ Cαk = C k̄ −a . Because δ ≤ 1 and a > 1/2, we have a > δ/2. Hence (39) holds with µp = a. We next bound dk . First, (44), Assumption 2.2, the already-proved fast moment bounds, and the baseline estimate for Yk imply 2 1/2 2 1/2 2 1/2 2+2ρ 1/2 E ∥g(xk , yk )∥ ≤ C E ∥Yk ∥ + C E ∥Xk ∥ + C E ∥Xk ∥ ≤ C k̄ −a/2 + C k̄ −s/2 ≤ C k̄ −a/2 + k̄ −δ/2 . Since Dλ is locally bounded, the first term in (101) satisfies the same bound. For the second term in (101), the local Lipschitz continuity of Dλ gives ∥Dλ(yk ) − Dλ(y ∗ )∥ ≤ C ∥Yk ∥ . 25
A PREPRINT - J UNE 15, 2026
Using the conditional second-moment bound on ζk+1 , 2 2 2 2 E ∥(Dλ(yk ) − Dλ(y ∗ ))ζk+1 ∥ ≤ CE ∥Yk ∥ E(∥ζk+1 ∥ | Fk ) ≤ CE ∥Yk ∥ ≤ C k̄ −a . Thus this term has L2 norm at most C k̄ −a/2 . For the Taylor remainder term, (100) gives 2
λ ≤ Cβk ∥g(xk , yk ) + ζk+1 ∥ . βk−1 rk+1
By the localization hypothesis, the process stays in the neighborhood where (44) holds. Hence g is locally bounded there, and ζk+1 has a uniformly bounded fourth conditional moment. Therefore 2 1/2 λ E βk−1 rk+1 ≤ Cβk ≤ C k̄ −1 ≤ C k̄ −a/2 , because a < 1. Combining the three estimates proves (40). Therefore Assumption 4.1 holds, and Theorem 4.2 gives the claimed rate. Proof of Proposition 4.4. The proof follows the same coordinate calculation as Proposition 4.3, but we spell out the estimates because the mixed terms are the point of the result. Define Yk = yk − y ∗ ,
Xk = xk − λ(yk ),
x ξk+1 = Mk+1 ,
y ζk+1 = Mk+1 .
By Jensen’s inequality and (48), 2
2
E ∥Yk ∥ ≤ C k̄ −a .
E ∥Xk ∥ ≤ Cαk ,
(102)
By Lyapunov’s inequality, 2+2ρ
E ∥Xk ∥ Thus the fast moment requirements (38) hold.
≤ E ∥Xk ∥
4 (1+ρ)/2
≤ Cαk1+ρ .
(103)
The slow equation follows directly from (47): Yk+1 = (I − βk B)Yk + βk HXk + R(Xk ) + ζk+1 + ek ,
ek = E(Xk , yk ).
We bound ek in L2 . By (47), Cauchy’s inequality, (48), and (103), 2 1/2 2+2ρ 1/2 2 2 1/2 4 1/2 E ∥ek ∥ ≤ C E ∥Xk ∥ + C E ∥Xk ∥ ∥Yk ∥ + C E ∥Yk ∥ 4 1/4 4 1/4 E ∥Yk ∥ + C k̄ −a ≤ C k̄ −s/2 + C E ∥Xk ∥ ≤ C k̄ −s/2 + C k̄ −a + C k̄ −a . Let δ = min{1, s}. Since a > 1/2 ≥ δ/2 and s/2 ≥ δ/2, the last line is at most C k̄ −δ/2 . Hence (41) holds. We next derive the fast equation. Taylor’s theorem for λ gives λ λ(yk+1 ) = λ(yk ) + Dλ(yk )(yk+1 − yk ) + rk+1 ,
2
λ rk+1 ≤ C ∥yk+1 − yk ∥ .
(104)
Using (46) and yk+1 − yk = βk (g(xk , yk ) + ζk+1 ), we get Xk+1 = xk+1 − λ(yk+1 ) λ = xk + αk h(xk , yk ) + ξk+1 − λ(yk ) − Dλ(yk )βk g(xk , yk ) + ζk+1 − rk+1 = (I − αk A)Xk + αk ξk+1 + αk P (Xk , yk ) − βk Dλ(y ∗ )ζk+1 + βk dk , where
λ dk = −Dλ(yk )g(xk , yk ) − Dλ(yk ) − Dλ(y ∗ ) ζk+1 − βk−1 rk+1 .
Thus (36) holds with
pk+1 = P (Xk , yk ), Cζ = −Dλ(y ∗ ). For pk+1 , (46), Cauchy’s inequality, and (48) imply 2 1/2 4 1/2 2 2 1/2 E ∥pk+1 ∥ ≤ C E ∥Xk ∥ + C E ∥Xk ∥ ∥Yk ∥ 4 1/4 4 1/4 ≤ Cαk + C E ∥Xk ∥ E ∥Yk ∥ ≤ C k̄ −a .
Because a > 1/2 ≥ δ/2, (39) holds with µp = a. 26
(105)
A PREPRINT - J UNE 15, 2026
It remains to prove (40). First, by (47), Assumption 2.2, (102), (103), and the bound just proved for ek , 2 1/2 2+2ρ 1/2 2 1/2 2 1/2 2 1/2 + C E ∥ek ∥ + C E ∥Xk ∥ + C E ∥Xk ∥ ≤ C E ∥Yk ∥ E ∥g(xk , yk )∥ ≤ C k̄ −a/2 + C k̄ −δ/2 . The derivative Dλ is locally bounded, so the first term in (105) has this same L2 bound. For the second term in (105), boundedness of the Hessian of λ gives ∥Dλ(yk ) − Dλ(y ∗ )∥ ≤ C ∥Yk ∥ . Using the conditional second-moment bound on ζk+1 , 2 2 2 2 E ∥(Dλ(yk ) − Dλ(y ∗ ))ζk+1 ∥ ≤ CE ∥Yk ∥ E(∥ζk+1 ∥ | Fk ) ≤ CE ∥Yk ∥ ≤ C k̄ −a . Therefore this term has L2 norm at most C k̄ −a/2 . For the Taylor remainder term, (104) gives 2
λ βk−1 rk+1 ≤ Cβk ∥g(xk , yk ) + ζk+1 ∥ .
The localized process remains in the neighborhood on which g is bounded, and ζk+1 has a uniformly bounded fourth conditional moment. Hence 2 1/2 λ E βk−1 rk+1 ≤ Cβk ≤ C k̄ −1 ≤ C k̄ −a/2 , because a < 1. Combining the three bounds for the terms in (105) yields 2 1/2 E ∥dk ∥ ≤ C k̄ −a/2 + k̄ −δ/2 , which is (40). All parts of Assumption 4.1 have now been verified, and Theorem 4.2 gives the claimed rate.
F
Proof of the lower bound
We prove Theorem 3.4. The proof uses elementary properties of the scalar Gaussian fast recursion. Lemma F.1 (Fast variance lower bound). Consider the scalar recursion Xk+1 = (1 − λαk )Xk + αk ξk+1 ,
X0 = 0,
where ξk are i.i.d. standard Gaussian random variables and 0 < λαk ≤ 1/2. Then there are constants cv , Cv > 0 and kv ≥ 1 such that, for all k ≥ kv , cv αk ≤ E[Xk2 ] ≤ Cv αk . (106) Consequently, for every p > 0 there exists cp > 0 such that, for all k ≥ kv , p/2
E|Xk |p ≥ cp αk .
(107)
Proof. Because the recursion is linear and the driving noises are Gaussian, Xk is a centered Gaussian random variable. Let vk = E[Xk2 ]. Then vk+1 = (1 − λαk )2 vk + αk2 . (108) The upper bound vk ≤ Cv αk follows from the same second-moment induction used in Lemma B.1; we repeat the one-line argument. Since (1 − λαk )2 ≤ 1 − λαk and αk+1 ≥ αk (1 − (λ/2)αk ) for all large k, choosing Cv ≥ 2/λ yields vk ≤ Cv αk ⇒ vk+1 ≤ Cv αk (1 − λαk ) + αk2 ≤ Cv αk+1 . Increasing Cv handles finitely many initial indices. For the lower bound, unroll (108): vk =
k−1 X i=0
αi2
k−1 Y
(1 − λαℓ )2 .
ℓ=i+1
Fix a small constant δ ∈ (0, 1) to be chosen below and define δ mk := . αk 27
(109)
A PREPRINT - J UNE 15, 2026
Because a < 1, mk = o(k), so for all large k we have mk ≤ k/2. For i ∈ {k − mk , . . . , k − 1} and all large k, monotonicity of αj and mk = o(k) imply 1 αk ≤ αi ≤ 2αk . (110) 2 Also, since λαℓ ≤ 1/2, the inequality log(1 − u) ≥ −2u for u ∈ [0, 1/2] gives ! k−1 k−1 Y X 2 (1 − λαℓ ) = exp 2 log(1 − λαℓ ) ℓ=i+1
ℓ=i+1
!
k−1 X
≥ exp −4λ
αℓ
.
ℓ=i+1
For i ≥ k − mk , (110) gives k−1 X
αℓ ≤ 2mk αk ≤ 2δ.
ℓ=i+1
Therefore every product in the last mk terms is at least e−8λδ . Restricting the sum (109) to these terms, 2 k−1 X 1 2 −8λδ αk e−8λδ . αi e ≥ mk vk ≥ 2 i=k−mk
For all large k, mk ≥ δ/(2αk ), so vk ≥
δe−8λδ αk . 8
This proves the lower variance bound. Finally, if Xk ∼ N (0, vk ), then for any p > 0, p/2
E|Xk |p = vk E|Z|p ,
Z ∼ N (0, 1).
Using vk ≥ cv αk proves (107). Proof of Theorem 3.4. Let ϕi,k :=
k−1 Y
(1 − bβℓ ),
0 ≤ i ≤ k,
ℓ=i
with the empty product ϕk,k = 1. Unrolling (21) gives Yk = γ
k−1 X
βj ϕj+1,k |Xj |1+ρ + τ
k−1 X
βj ϕj+1,k ηj+1 .
(111)
j=0
j=0
Denote the two sums by Pk and Nk , respectively, so that Yk = γPk + τ Nk . The process Pk is a measurable function of ξ1 , . . . , ξk , whereas Nk is a linear function of η1 , . . . , ηk . The two noise sequences are independent, so Pk and Nk are independent. Moreover, ENk = 0. Hence E[Yk2 ] = γ 2 E[Pk2 ] + τ 2 E[Nk2 ] ≥ γ 2 (EPk )2 + τ 2 E[Nk2 ].
(112)
We lower bound the two terms separately. Nonlinear bias term. For j ∈ {⌊k/2⌋, . . . , k − 1} and all large k, the product ϕj+1,k is bounded below by a positive constant. To see this, use log(1 − u) ≥ −2u for u ∈ [0, 1/2]: k−1 X ϕj+1,k = exp log(1 − bβℓ ) ℓ=j+1
≥ exp −2b
k−1 X
βℓ ≥ exp −2bβ0
ℓ=j+1
k−1 X ℓ=⌊k/2⌋
≥ exp(−Cb ) =: cϕ > 0. 28
1 ℓ + k0
A PREPRINT - J UNE 15, 2026
Also, for these j, βj ≥ c/k and αj ≥ cαk . Lemma F.1 with p = 1 + ρ gives (1+ρ)/2
E|Xj |1+ρ ≥ cαj Therefore EPk =
k−1 X
(1+ρ)/2
≥ cαk
.
βj ϕj+1,k E|Xj |1+ρ
j=0 k−1 X
≥
βj ϕj+1,k E|Xj |1+ρ
j=⌊k/2⌋ k−1 X
≥c
j=⌊k/2⌋
Since αk = α0 k̄
−a
1 (1+ρ)/2 (1+ρ)/2 α ≥ cαk . k k
, this implies (EPk )2 ≥ ck̄ −a(1+ρ) .
Slow-noise term.
(113)
Because the ηj are independent standard Gaussians, E[Nk2 ] =
k−1 X
βj2 ϕ2j+1,k .
j=0
Restricting again to j ∈ {⌊k/2⌋, . . . , k − 1} and using ϕj+1,k ≥ cϕ and βj ≥ c/k, E[Nk2 ] ≥
k−1 X j=⌊k/2⌋
c ≥ ck −1 ≥ ck̄ −1 . k2
(114)
Substituting (113) and (114) into (112) proves E[Yk2 ] ≥ cγ 2 k̄ −a(1+ρ) + cτ 2 k̄ −1 for all sufficiently large k. This is (22).
G
Additional comments on the threshold
The upper and lower bounds together show that the exponent min{1, a(1 + ρ)} is sharp for the normal-form class. This section records two simple consequences. Proposition G.1 (Merely Lipschitz remainders cannot decouple). Set ρ = 0. In the scalar lower-bound instance with γ > 0, there exists c > 0 such that E[Yk2 ] ≥ ck̄ −a for all large k. Hence no theorem that assumes only a Lipschitz nonlinear remainder can guarantee the decoupled k −1 rate uniformly over the normal-form class when a < 1. Proof. This is Theorem 3.4 with ρ = 0 and with the nonnegative τ 2 k̄ −1 term discarded. Proposition G.2 (Second-order remainders decouple for a > 1/2). Set ρ = 1. Under Assumptions 2.1–2.3, Theorem 3.1 gives 2 E ∥Yk ∥ ≤ C k̄ −1 . Proof. When ρ = 1, s = 2a. Since a > 1/2, s > 1. Thus k̄ −s ≤ k̄ −1 , and Theorem 3.1 gives the result.
29