Letting the Trajectory Choose Its Own Averaging Window

Stochastic gradient methods run with a large constant step size move quickly away from a bad starting point, but then keep bouncing around the solution. A classic remedy is Polyak-Ruppert averaging: report the average of the visited parameters instead of the last one, so that the random bouncing cancels out. It works only if the average leaves out the early iterates, which are still far from the solution. Today that cut-off is set by hand, either as a fixed fraction of training such as "average the second half" or as a tuned epoch. The one published attempt to detect it automatically performs worse than hand tuning. We propose to choose the averaging window from the trajectory itself, with a rule taken from nonparametric statistics called Lepski's method. The rule compares nested tail averages and keeps the longest window whose average is statistically consistent with every shorter one. It needs no validation set, no known training horizon, and memory that grows only logarithmically with the number of steps.

The reason this matters is that the averaging window is precisely the parameter that the bias-variance analysis of averaged SGD says should adapt to the run. The early transient is a bias that decays geometrically, the late noise is a variance that decays as one over the window length, and the best cut-off depends on conditioning and noise level that nobody knows in advance. A selection rule that provably tracks the best cut-off in hindsight, and whose single knob is a statistical confidence constant rather than an epoch number, would remove one of the most persistent hand-tuned choices in constant-step-size training. That covers least-squares, temporal-difference (TD) learning in reinforcement learning, and deep network training.

Core Claim

Maintain a geometric grid of candidate start times $s_1 < s_2 < \dots < s_K$ with $K = O(\log t)$, using the tiered accumulators of anytime tail averaging. Let $\hat\theta_j$ be the average of iterates from $s_j$ to the current step $t$. Let $\hat v_j$ be an estimate of its variance, computed as the trace of the long-run covariance of the iterates divided by the window length $t - s_j$, using means of sub-blocks so that correlation between consecutive iterates is accounted for. The selected estimator is $\hat\theta_{\hat j}$, where

$$ \hat j = \min\{\, j : \|\hat\theta_j - \hat\theta_i\|^2 \le \kappa\, \hat v_i \ \text{ for all } i > j \,\}, $$

and $\kappa$ is a confidence constant of order $\log K$. In words, we extend the window backward as long as doing so never moves the average further from any shorter, less biased average than noise alone would explain.

This differs from a trigger in two ways. A trigger fires once and irreversibly. Our window can also shrink again when the trajectory drifts, for example after a learning-rate change or a move into a new basin. The theoretical target is an oracle inequality in the quadratic and linear stochastic-approximation setting: the error of the selected average is within a logarithmic factor of the best fixed start time chosen in hindsight. The rate form follows from the constant-step bias-variance split, with bias of order $1/(\gamma^2 n^2)$ and variance of order $1/n$ for step size $\gamma$ and $n$ averaged steps. That split is exactly the structure Lepski's method is designed to balance.

What Prior Work Establishes and Leaves Open

Several papers motivate the gap by showing that the window matters and that nobody sets it automatically. Averaged Least-Mean-Squares derives the bias and variance terms for constant-step averaged least squares. It adapts the sampling distribution to whichever term dominates, but it schedules that switch using prior knowledge of the horizon rather than online. We instead adapt the window, and we do it online. Patil et al. prove an $O(1/t)$ rate for tail-averaged TD(0) with universal step sizes, but fix the split at $T/2$ and leave adaptive cut-offs open. The same is true of the $\omega$-free TD(0) analyses in Fast and Robust Convergence Rate for TD(0) and its companion version, where $\omega$ is the smallest eigenvalue of the feature covariance.

Closest to us, Iterate Averaging in the Quest for Best Test Error and Gadam show that averaging with AdamW and large learning rates beats step-decay SGD. They also introduce GadamAuto, an automatic averaging trigger, and report that it underperforms manually tuned Gadam. Our rule differs from GadamAuto in three ways. It is a nested multiple-comparison test rather than a single progress threshold. It corrects its noise estimate for correlation between iterates. And its window can contract after it has started growing.

Two papers constrain the design. EMA Without the Lag removes the lag of an exponential moving average (EMA) by adding a multiple of the displacement $\theta_t - \theta_0$. Its coefficients follow fixed power laws derived under a locally quadratic Ornstein-Uhlenbeck model (a noisy mean-reverting process), and the authors say this model fails early in training. That warns us against relying on a single global quadratic model. Our test is local: it only compares recent averages with each other. The Granziol papers find that strided averaging, taken once per epoch, generalizes better than averaging every step. This suggests that the sub-block means we already compute should also serve as the averaged units.

Two papers supply methods we reuse. Le Roux's anytime tail averaging provides the constant-memory tiered accumulators that make the geometric candidate grid cheap. From the adaptive-parameter literature, the TCP-style work-balancing rules of Karimireddy et al. name the obstacle we address directly: adaptive rules misfire under noisy progress signals and bring in fragile meta-parameters. Krichene et al. adapt averaging weights in deterministic accelerated dynamics using a Lyapunov energy. Their setting has no stochastic noise to cancel, whereas ours is entirely about noise. Finally, Samsonov et al. show that averaged linear stochastic approximation becomes Gaussian only at rate $n^{-1/4}$. This warns that naive Gaussian thresholds will be miscalibrated for short windows. It is why we calibrate $\kappa$ with sub-block (batch-means) variance estimates and check empirically how often the test falsely rejects.

Research Program

The theory part proves the oracle inequality for constant-step averaged least squares and for linear stochastic approximation with independent samples. It then extends the result to Markovian sampling under the condition that the sub-block length exceeds the mixing time, and asks whether that length can be chosen adaptively. This speaks directly to the unknown-mixing-time gap left by Patil et al.

The algorithm part adds a per-layer variant for deep networks, since norms of whole-network parameter vectors mix layers with very different scales. It also adds strided sub-block means as the averaged units and a reset path that allows the window to contract.

The empirical part tests whether the rule matches the best hand-tuned start time without any held-out evaluation, and whether it is robust to $\kappa$. The meta-parameter question ("who tunes the tuner") is answered only if one value of $\kappa$ derived from theory works across all testbeds.

Baselines

The naive reference is the last iterate of constant-step SGD or AdamW, together with plain uniform averaging from step zero. Beating the first shows that averaging helps at all. Beating the second shows that choosing a window matters.

The standard hand-crafted baseline is fixed-fraction tail averaging at $T/2$, as in Patil et al.. It is the strongest parameter-free competitor in linear and TD settings. We run it on the same trajectories as our method, so the only difference is the choice of window. Beating it means lower error at the final step and, unlike $T/2$, valid estimates at every intermediate step.

The strongest existing deep-learning method is manually tuned Gadam and GadamX from Iterate Averaging in the Quest for Best Test Error. The file reports ResNet-50 ImageNet top-1 error of 22.69% for GadamX against 23.85% for SGD, and Penn Treebank LSTM test perplexity of 58.77 for Gadam. We give the hand-tuned start time a grid search of five values on a validation split. Our method gets no search: one run at the theory-derived $\kappa$. Success means matching the tuned result within seed noise while using a fifth of the tuning compute. We also run GadamAuto itself on the same trajectories, because its reported deficit is the gap we claim to close; no reported result for GadamAuto's scalar error was found on Lacuna.

On LLM fine-tuning, the competitor is BEMA with its published power-law schedules, plus a standard EMA with decay tuned over three values. For BEMA on GSM8K, no reported scalar accuracy was found on Lacuna. The file states only that BEMA reached peak performance in about half the steps others needed to plateau, so we will reproduce BEMA ourselves.

On convex benchmarks, we compare against Averaged Implicit SGD from Toulis et al.. No scalar test errors for it were found on Lacuna.

Three ablations isolate the key ingredient. The first replaces the correlation-corrected variance with a naive independent-sample variance. The second replaces the nested Lepski comparison with a single irreversible threshold, which reconstructs a GadamAuto-style trigger inside our code. The third forbids the window from contracting.

Why not just…?

Why not just pick the start time by validation loss, using Le Roux's accumulators to hold several candidate averages at once? This is the most serious threat. Where validation is cheap, it may match us. We include it as an upper-reference baseline that selects among the same $K$ candidate windows by held-out loss. Our claim is narrower: the trajectory-only rule reaches the validation-selected window without evaluating $K$ models. That matters where validation is expensive, as in LLM generation benchmarks, or where no validation loss exists, as in TD policy evaluation, whose target values are unknown. If validation selection clearly wins even in those settings, our contribution reduces to the TD and streaming cases, and we will report it that way.

Why not just use cosine or step learning-rate decay? Iterate Averaging in the Quest for Best Test Error and EMA Without the Lag both report that constant-step training with averaging matches or beats decay schedules. Decay schedules also need a known horizon and milestone choices. We still include tuned cosine decay as a baseline on every deep-learning testbed.

Why not just use EMA or BEMA with a tuned decay? An EMA sets an implicit window through its decay rate, which is the same hand-set parameter under another name, and it lags when the trajectory drifts. BEMA's schedules are fixed functions of the step count. The drift experiment described below, a learning-rate change in the middle of training, is where a fixed-decay average should visibly lag and our contracting window should not. If tuned EMA matches us there, the adaptive window adds little.

Proposed Experiments

The first stage is controlled and checks the theory. We run constant-step averaged least squares on synthetic problems with the minimum eigenvalue swept over three orders of magnitude, and on Yahoo Ad-Click and Sido. Yahoo Ad-Click is informative because the best step size under bias-optimal sampling is reported as 0.105, against 0.005 under uniform sampling, so the transient length varies sharply with configuration. We measure excess risk of the selected average against the best fixed start in hindsight, computed by exhaustive search over stored trajectories. The decisive check is whether this ratio stays bounded by a small constant across the conditioning sweep. $T/2$ should fail this check when the transient is long relative to $T$.

The second stage is TD(0) with linear features, run on the two-state chain and on Garnet MDPs (randomly generated Markov decision processes) under Markovian sampling with tunable mixing. We measure the error of the value parameters relative to the true fixed point. The decisive check is behaviour as mixing slows: the correlation-corrected rule should keep its false-shrink rate controlled, while the naive-variance ablation should shrink the window spuriously.

The third stage is deep learning. We train VGG-16 and ResNeXt on CIFAR-100 and ImageNet-32 with AdamW and SGD, and an LSTM on Penn Treebank, measuring test error, test perplexity, and total tuning compute over three seeds. A single ResNet-50 ImageNet run compares directly against the 22.69% GadamX figure. We also add a drift stress test: the learning rate is doubled at 60% of training, and we check whether the window contracts and recovers.

The fourth stage fine-tunes Qwen2.5-1.5B on Tulu-3-SFT and evaluates on GSM8K and BoolQ against BEMA and EMA, measuring accuracy against steps.

Across all stages, the outcome that settles the proposal is whether one fixed $\kappa$ matches or beats the hand-tuned start time and the $T/2$ rule on every testbed. If it does, the averaging window has stopped being a hyperparameter. If $\kappa$ needs retuning for each domain, we have only moved the meta-parameter problem, and we will report that.