Skip to main content
Back

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.

Pro

Paper, Full Access

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