A New Proof Gives ML Engineers More Freedom Tuning Two-Speed Optimizers
A new proof shows that in nonlinear two-time-scale stochastic approximation, each iterate's error can depend only on its own step size given a local linearity condition.
ProTakeaways
- First finite-time proof of decoupled convergence for nonlinear two-time-scale stochastic approximation.
- Under nested local linearity, slow iterate converges at rate O(beta_t) independent of fast step size.
- Optimal O(1/t) rate for the slow iterate allows fast step-size exponent in the range 2/3 to 1.
- Proof uses matrix cross term tracking plus fourth-moment analysis to control nonlinear residuals.
- Counter-example proves local linearity is essentially necessary, even when only G is nonlinear.
- Applies directly to Polyak-Ruppert averaging, momentum SGD, bilevel optimization, and actor-critic.
If you have ever trained a model with Polyak-Ruppert averaging, used SGD with momentum, or coded up an actor-critic reinforcement learning agent, you have used two-time-scale stochastic approximation without necessarily calling it that. A new theoretical paper closes a long-standing gap in how fast these methods actually converge when the underlying operators are nonlinear.
Under a reasonable local linearity condition, the slow variable's convergence rate no longer gets dragged down by whatever step size you picked for the fast variable. That gives practitioners meaningfully more freedom in tuning learning rates.
The two-speed setup you already use
Two-time-scale stochastic approximation (SA) generalizes classical stochastic approximation by updating two iterates at different rates with different step sizes, where each update influences the other. The method shows up concretely in stochastic bilevel optimization, temporal difference learning, and actor-critic methods.
The canonical form has two updates:
x_{t+1} = x_t - alpha_t * (F(x_t, y_t) + noise) # fast iterate
y_{t+1} = y_t - beta_t * (G(x_t, y_t) + noise) # slow iterate
The step size beta_t is chosen much smaller than alpha_t, so y_t looks nearly frozen while x_t races to track it. Think of Polyak-Ruppert averaging: the SGD iterate is the fast x, and the running average is the slow y.
What decoupled convergence actually means
For the linear case, prior work established a clean property: the mean-square errors of the two updates converge at rates that depend solely on their respective step sizes, a phenomenon termed decoupled convergence. The error of the fast iterate scales like