ADWIN: Adaptive Windowing for Drift Detection
ADWIN (ADaptive WINdowing; Bifet & Gavaldà, 2007) solves two problems at once on a stream of real values — typically a model's error signal. It detects change (concept drift), and it maintains a window of exactly the right length: as long as the data looks stationary the window grows; the moment the mean shifts, it shrinks to just the recent, homogeneous part. That recovered window length is itself an estimate of "how far back the current concept extends."
The core idea: test every split of the window
ADWIN keeps a window of the most recent stream values. On each new element it asks:
Is there a way to cut into an older sub-window and a newer sub-window such that their sample means are distinguishably different?
If yes, the older data belongs to a stale concept, so ADWIN drops and reports drift. Formally, it declares a change at a split when
where is the harmonic mean of the two sub-window sizes and is the confidence parameter. The inside the log is a union bound over the (many) possible cut points; the harmonic mean makes the threshold large when either side is small (little evidence) and small only when both sides are big.
Hoeffding vs Bernstein cut
The bound above is the Hoeffding form used in the lesson. The published ADWIN uses a slightly tighter Bernstein-style cut that folds in the observed variance :
For low-variance error streams this detects a bit sooner; the qualitative behaviour is identical.
Why the window length is the payoff
Most detectors only raise a boolean alarm. ADWIN additionally rightsizes its window: after a cut it retains only , so downstream statistics (a running mean, a model refit on "the current window") automatically use only in-distribution data. There is no separate window-length hyperparameter to tune — the data sets it. This is why ADWIN is often wired directly into learners (e.g. as the change detector inside a Hoeffding Adaptive Tree, which grows an alternate subtree when a node's ADWIN fires).
Making it cheap: exponential histograms
Re-scanning every possible split of a length- window on every element would cost per step and memory. ADWIN2 compresses into an exponential histogram of buckets (the same power-of-two bucket structure as DGIM) storing per-bucket sums and counts with relative accuracy. This gives:
- Memory: instead of .
- Time: only candidate split points (the bucket boundaries) are tested per update, not all .
The approximation of using bucket boundaries as the only cut points costs a controllable constant factor and preserves the guarantees below.
Guarantees
For a suitable choice of the confidence , ADWIN comes with two-sided rigor:
- Few false positives. If the mean is truly constant across , the probability that ADWIN wrongly shrinks the window is at most .
- Reliable detection. If the mean changes by more than roughly , ADWIN detects it and shrinks the window, with high probability, within a delay that scales with how large the change is (bigger jumps are caught faster).
The knob is : larger ⟹ smaller ⟹ faster detection but more false alarms; smaller is conservative. This is the universal detection-delay / false-alarm trade-off.
Worked cut calculation
Suppose the current window has error bits, and we test the balanced split . Recent history shifted, so the older half averages and the newer half . With :
The observed gap , so the test fires: ADWIN drops and reports drift. Had the gap been the stationary-noise level (say ), no split would exceed and the window would keep growing. Note the threshold falls as the window grows ( rises), so a change too subtle to catch now becomes detectable once more post-change data accumulates.
Watch it run
The trace reproduces the arithmetic above, then runs ADWIN on a stream with two changes of different sizes.
ADWIN — the window length is the output
The whole algorithm is one inequality, so start where the page does. A window of |W| = 200 error bits split evenly: m = 1/(1/100 + 1/100) = 50, and ε_cut = √( ln(4·200/0.05) / (2·50) ) = √(ln 16000 / 100) = 0.3111. A gap of |0.08 − 0.42| = 0.34 clears it, so the test fires. Two things do the work: **m is a harmonic mean**, so the threshold blows up whenever *either* side is small, and the |W| inside the log is a union bound over every cut point about to be tried. Note what ε_cut does *not* contain: any notion of how large a change you care about. ADWIN has no magnitude parameter, only δ.
The page's own cut arithmetic (m = 50, ε_cut = 0.3111) reproduced exactly, then run on a stream with two changes of different sizes. Watch the threshold's U-shape across candidate splits, the delay while post-change evidence accumulates, and the bigger jump getting caught faster than the smaller one. Two payoffs, both of which contradicted the first draft and were rewritten from the measurements: ADWIN does not beat the best fixed window, it comes within 4% of it without being told what it is, while a wrong fixed choice costs 2x. And the famous delta trade-off is entirely one-sided here — delay grows 2.4x across the sweep while false alarms stay at zero across 300,000 stationary steps, because delta sits inside a logarithm inside a square root.
What to notice:
- Frame 2: the threshold is a U. Plotting against every candidate split shows why the harmonic mean matters: the threshold is enormous at both ends, where one sub-window is a handful of bits, and lowest in the middle. A change near the edge of the window is structurally harder to see than one in the middle.
- Frames 3–4: delay is evidence accumulation, not sluggishness. ADWIN cannot fire right after the change because the newer sub-window is small, so is small and its threshold is huge. The larger jump (0.10 → 0.45) is caught in 56 steps and the smaller one (0.45 → 0.18) in 66.
- Frame 5: the honest version of "no hyperparameter". ADWIN does not beat every fixed window: a fixed scores marginally better on this stream. What ADWIN does is land within 4% of the best fixed width without being told what it is, while the spread across plausible widths is 2×. On a live stream you cannot identify the best width — that requires the ground truth you are estimating.
- Frame 6: the δ trade-off is one-sided. Sweeping δ over five orders of magnitude, detection delay grows 2.4× while false alarms stay at zero across 300,000 stationary steps, even at δ = 0.5. δ sits inside a logarithm inside a square root, so the Hoeffding threshold is far more conservative than the nominal δ implies.
That last point qualifies the "larger δ ⟹ faster detection but more false alarms" rule above. The direction is right, but on streams of this length the false-alarm half is unobservable, so the practical advice inverts: pick δ loose, because tightening it buys a reduction you cannot measure and costs detection delay you can. δ is an upper bound on the false-alarm probability, and nothing promises it is tight.
Gotchas
- δ is a rate, not a magnitude. It controls false-alarm probability, not the size of change you care about; pick it for your tolerance to spurious resets.
- It monitors a scalar. ADWIN watches one real-valued signal (an error rate, a residual). For multivariate drift, run one detector per signal or feed it a scalar summary.
- Recurring concepts. After a reset ADWIN forgets the old window, so genuinely recurring concepts are re-learned rather than recalled — pair it with an ensemble if recurrence matters.
See also
- Concept Drift & Adaptation: the lesson this expands
- DGIM: the exponential-histogram bucket structure ADWIN reuses