Nonlinear two-speed learning method shows finite-time error limits
The Bias of Nonlinear Two-Time-scale Stochastic Approximation under Constant Step-Sizes
Machine Learning
Summary
Many computer algorithms learn by adjusting two linked parts at different speeds. This paper studies how errors behave when these parts update at constant rates, focusing on nonlinear cases that are common but hard to analyze. The authors identify how various factors, such as starting conditions and the interaction between parts, contribute to bias and error. They provide formulas that precisely describe these errors and show differences from simpler linear cases. Their work helps explain the limits of accuracy for these learning methods in practical use.
What this means in practice
- •For machine learning engineers: Design iterative training algorithms with improved understanding of error bounds when running at fixed learning rates and interacting speeds.
- •For control systems designers: Develop control algorithms that rely on nonlinear coupled updates with predictable performance guarantees under constant tuning parameters.
Authors
Djamel Rassem Lamouri, Dorian Baudry, Nicolas Gast
Abstract
Two-timescale stochastic approximation (TTSA) is a fundamental tool for analyzing coupled iterative algorithms in reinforcement learning, optimization, and stochastic control. However, finite-time guarantees for nonlinear two-timescale schemes remain difficult to obtain, especially under constant step-sizes. In this paper, we study nonlinear TTSA with step-sizes $α\ggβ$. Under standard stability, regularity, and Markovian noise assumptions, we upper bound the mean-squared error and the bias of both iterates around their limiting equilibria. Our bounds scale as $O(α+β^2/α^2)$, which we prove to be tight when $β\leα^{3/2}$. The analysis separates the contributions of initial conditions, fast-timescale tracking error, Markovian dependence, and timescale coupling, thereby clarifying the origin of the $β^2/α^2$ term. Our results reveal qualitative differences from the linear TTSA setting previously studied, showing that nonlinear dynamics introduce additional finite-time effects that are absent in the linear case.