Online, Offline, and Continual Learning › Worked Example: Tracking a Drifting Coefficient

Let us make the tradeoffs quantitative with a scalar example we can solve on paper. Suppose the true relationship is

$$y_t = \theta^\star x_t + \epsilon_t,$$

where:

• $y_t$: the observed target at step $t$
• $\theta^\star$: the true coefficient in the drifting-coefficient example
• $x_t$: the scalar input at step $t$
• $\epsilon_t$: zero-mean observation noise at step $t$
• $\sigma^2$: the variance of the observation noise $\epsilon_t$

with $x_t \sim \mathcal{N}(0, 1)$ and $\epsilon_t \sim \mathcal{N}(0, \sigma^2)$, and suppose $\theta^\star$ changes at some point from one value to another. We want to know how fast SGD tracks the change and how precisely it can localize the new value.

From the derivation above, the bias decays geometrically:

$$\mathbb{E}\big[\theta_t - \theta^\star\big] = \big(1 - \eta \sigma_x^2\big)^t \big(\theta_0 - \theta^\star\big).$$

where:

• $\mathbb{E}[\theta_t - \theta^\star]$: the expected deviation of the estimate from the true parameter after $t$ steps
• $\theta_t$: the parameter estimate after $t$ steps
• $\theta_0$: the initial parameter value
• $\theta^\star$: the true parameter
• $\eta$: the fixed learning rate
• $\sigma_x^2$: the variance of the inputs $x_t$
• $t$: the number of steps elapsed, so $\eta \sigma_x^2$ is the per-step contraction factor

With $\sigma_x^2 = 1$ and $\eta = 0.02$, the decay rate is $0.98$ per step. To reduce the initial error by a factor of $e$ takes about $1/0.02 = 50$ steps. Here is where that number comes from. We want the smallest $t$ with $(1 - \eta\sigma_x^2)^t \le e^{-1}$. Taking logarithms,

$$\begin{aligned} t \ln(1 - \eta\sigma_x^2) &\le -1 && \text{(apply } \ln \text{)} \\ t &\ge \frac{-1}{\ln(1 - \eta\sigma_x^2)} && \text{(divide by the negative log)} \\ &\approx \frac{1}{\eta\sigma_x^2} && \text{(use } \ln(1-z) \approx -z \text{ for small } z\text{)} \end{aligned}$$

where:

• $t$: the number of steps
• $\eta$: the learning rate
• $\sigma_x^2$: the variance of the inputs $x_t$
• $z$: a small positive quantity, here $z = \eta\sigma_x^2$

With $\eta\sigma_x^2 = 0.02$ this gives $t \approx 50$ steps. That is the adaptation time.

The adaptation time is the first half of the tradeoff. It tells us how long the estimator takes to forget an old value after the world changes. The second half is the noise ball, which tells us how precisely the estimator can settle on the new value once it has arrived.

Now the noise. At stationarity, the variance satisfies

$$\mathrm{Var}(\theta_\infty) = \frac{\eta^2 \sigma_x^2 \sigma^2}{1 - \mathbb{E}\big[(1 - \eta x_t^2)^2\big]}.$$

where:

• $\mathrm{Var}(\theta_\infty)$: the stationary variance of the estimate around the true parameter
• $\theta_\infty$: the stationary parameter estimate around which the variance is measured
• $\eta$: the learning rate
• $\sigma_x^2$: the variance of the inputs $x_t$
• $x_t$: the scalar input at step $t$
• $\sigma^2$: the variance of the observation noise $\epsilon_t$
• $\mathbb{E}\big[(1 - \eta x_t^2)^2\big]$: the expected squared contraction factor, which appears in the denominator

Replacing the random contraction by its mean gives the moment-closure approximation $\mathbb{E}\big[(1 - \eta x_t^2)^2\big] \approx (1 - \eta\sigma_x^2)^2$. Under that approximation,

$$\begin{aligned} \mathrm{Var}(\theta_\infty) &= \frac{\eta^2 \sigma_x^2 \sigma^2}{1 - (1 - \eta\sigma_x^2)^2} \\ &= \frac{\eta\,\sigma^2}{2 - \eta\,\sigma_x^2} && \text{(expand the denominator)} \\ &\approx \frac{\eta\,\sigma^2}{2} && \text{(small } \eta \text{)} \end{aligned}$$

where:

• $\mathrm{Var}(\theta_\infty)$: the stationary variance of the estimate around the true parameter
• $\theta_\infty$: the stationary parameter estimate around which the variance is measured
• $\eta$: the learning rate
• $\sigma_x^2$: the variance of the inputs
• $\sigma^2$: the variance of the observation noise $\epsilon_t$

This is the noise ball: the residual fluctuation of the estimate around the true value. Its radius is

$$\sqrt{\mathrm{Var}(\theta_\infty)} \approx \sqrt{\frac{\eta\,\sigma^2}{2}}.$$

where:

• $\sqrt{\mathrm{Var}(\theta_\infty)}$: the standard deviation of the stationary estimate fluctuation, also called the noise ball radius
• $\mathrm{Var}(\theta_\infty)$: the stationary variance of the estimate around the true parameter
• $\theta_\infty$: the stationary parameter estimate around which the variance is measured
• $\eta$: the learning rate
• $\sigma^2$: the observation noise variance

With $\eta = 0.02$ and $\sigma = 0.05$, the approximate stationary standard deviation is about $0.005$. That is the scale of an instantaneous stationary fluctuation, not a hard detection limit: averaging or sequential tests can detect smaller persistent shifts. A change of $0.3$ is much larger, and the roughly 50-step e-folding time means the estimate moves substantially toward it over tens of steps rather than settling immediately.

The tradeoff is now explicit. Increasing $\eta$ shortens the adaptation time and enlarges the noise ball. Decreasing $\eta$ does the reverse. There is no setting that makes both small; you are choosing where on the curve to sit. This is the same tradeoff that a replay buffer expresses in sample units, and the same tradeoff that a forgetting factor expresses as a discount rate. All three are parametrizations of a single decision about how much history to retain.

The figure below makes that frontier visible. Each point on the curve corresponds to one learning rate, with the adaptation time on the horizontal axis and the noise ball radius on the vertical axis.

One more observation from the variance formula. The noise ball shrinks only as $\sqrt{\eta}$, so halving the residual fluctuation requires quartering the learning rate, which quadruples the adaptation time. The returns to precision are poor. If you need a precise estimate, gradient descent with a fixed learning rate is the wrong tool; you want a method that reduces its effective step size as evidence accumulates, which is exactly what RLS does until it is given a forgetting factor.

The worked example also shows why the choice of learning rate depends on the scale of the change you expect. If the true coefficient changes by 0.3, a learning rate of 0.02 tracks it quickly. If the true coefficient changes by 0.003, that same learning rate cannot distinguish the change from noise. A practical system should therefore relate its learning rate to the smallest change it needs to detect and the fastest change it needs to track. Those two requirements pull in opposite directions, and the resolution is usually to use a larger learning rate for adaptation and a smaller one for fine-tuning, or to use a method that adapts the learning rate itself.