Data Reuse in Non-Stationary Learning

Tomer Gafni; Garud Iyengar; Assaf Zeevi

Source-linked AI summary

Data Reuse in Non-Stationary Learning

Tomer Gafni, Garud Iyengar, Assaf Zeevi

arXiv:2610.10340v1Oct 7, 2026stat.MLcs.LG

TL;DR

Recurring values make past observations reusable, but online change detection and uncertain class attribution create contamination risk. ECR combines segmentation, compatibility tests, and exposure control; empirically, its regret slope (0.540) is close to perfect reuse (0.490).

Problem
In recurrent non-stationary learning, the learner must detect regime changes and decide which historical observations can be safely reused, since misclassified data can bias estimates.
Source: §1.1 · pp. 1–2
Method
ECR is an anytime algorithm combining online segmentation, compatibility testing, and exposure control to reuse historical blocks while limiting their cumulative influence.
Source: §3 · p. 4, §3.3 · p. 6
Results
0.540 (ECR’s slope) is close to 0.490 (perfect-reuse benchmark slope); the no-reuse algorithm’s slope is 0.725.
Source: §5 · p. 9
Takeaways & Limitations
The paper’s principles concerning repeated bias accumulation may be useful beyond its formulation; extending them to sequential decision-making remains future work.
Source: §6 · p. 10
Retrospective segmentation refinement cannot guarantee exact change-point recovery, leaving contamination near estimated boundaries (alarms).
Source: §4.3 · p. 9

Abstract

from arXiv · show

We consider online learning in non-stationary environments, where the goal is to track an unknown parameter that switches abruptly between a finite set of recurring values. Recurrence opens the possibility of judiciously reusing past observations to improve algorithm performance. However, the changing nature of the underlying signal and lack of information on these dynamics may limit the ability to "safely" reuse data. In this paper we quantify some of the fundamental tradeoffs in this class of problems, and show that they bear a certain resemblance to the classical bias-variance dilemma. Specifically, we propose a class of anytime algorithms, dubbed Exposure-Capped Reuse (ECR), that combine online change detection, compatibility testing, and "contamination" control. We characterize the regime in which ECR's regret scales with the number of distinct values rather than the number of changes, and derive a novel information-theoretic lower bound that establishes the near-minimax optimality of ECR. This provides rigorous quantification of the statistical "value" of data reuse.

1. Introduction

Recurrence can reduce regret by pooling observations across recurring classes, but unknown changes make reuse vulnerable to contamination and bias. The introduction presents ECR as an online approach to manage this tradeoff and establishes when reuse can attain the perfect-reuse rate.

1.1. Background and Overview

With known change points, no-reuse regret scales as O(σST), while known recurrent-class identities enable pooling at the O(σMT) scale.When M ≪ S, recurrence replaces dependence on the number of changes with dependence on the smaller number of classes.Source: §1.1 · p. 2
Reusing more history reduces estimation variance but can increase bias when missed or delayed changes contaminate stored observations.The exposure budget limits each historical block’s cumulative bias influence while preserving enough reuse to reduce variance.Source: §1.1 · p. 2, §1.2 · p. 3

1.2. Main contributions

ECR combines online segmentation, compatibility testing, and exposure control without knowing the horizon, change points, or recurrent parameters.Its analysis accounts for both estimation variance and contamination bias.Source: §1.2 · p. 2
Under the stated switching regime, ECR matches the perfect-reuse O(σMT) regret scale up to polylogarithmic factors and essentially matches an information-theoretic lower bound.The lower bound also identifies the switching condition needed to attain the ideal recurrent rate as necessary up to logarithmic factors.Source: §1.2 · pp. 2–3
Repeated reuse can compound contamination bias into downstream errors beyond the ideal recurrent scale.The introduction identifies repeated bias accumulation as a central difficulty in exploiting recurrence online.Source: §1.2 · p. 3

1.3. Related literature

Prior recurrent-learning and distribution-shift approaches differ in their guarantees; this paper explicitly accounts for contaminated stored data and proves gains from recurrence.The introduction contrasts ECR with Re et al. (2021), whose guarantee remains change-dependent, and Li et al. (2021), whose analysis does not account for unavoidable stored-block bias.Source: §1.3 · p. 3

2. Problem formulation

The problem is to predict a piecewise-constant mean that switches among recurrent values, using only past observations. The formulation evaluates prediction error in the worst case over admissible environments.

Problem setup

The learner observes noisy samples whose mean switches among M distinct values across S changes over horizon T, with no minimum spacing between changes.The parameters are separated by minimum and maximum gaps, and the noise is i.i.d., zero-mean, and sub-Gaussian.Source: §2 · pp. 3–4

Information available to the learner

The learner knows only the noise proxy σ, while the horizon, class values, change points, and ordered segment labels are unknown.Predictions are adapted to the observations available before each round.Source: §2 · p. 4

Evaluation criterion

Performance is expected cumulative L1 prediction error, and the minimax criterion takes the worst case over admissible environments.The worst case ranges over change-point locations, recurrent values, segment labels, and noise laws.Source: §2 · p. 4

3. The Exposure-Capped Reuse (ECR) Algorithm

ECR is an anytime online algorithm that requires only the noise proxy σ. It separates decisions from estimation, segments history, tests blocks for compatibility, and limits exposure to reused data.

3.1. Decision/estimation split

Separating decision and estimation streams makes selected estimation samples conditionally independent of selection decisions, at the cost of a constant-factor regret increase.The decision stream supports change detection and compatibility decisions; the estimation stream supports prediction.Source: §3.1 · p. 5

3.2. Change detection test

The detector partitions history into blocks with well-separated class anchors when a block contains a long interval from a class.A long class-m interval uniquely associates the block with class m.Source: §3.2 · p. 5

3.3. Compatibility test

With probability at least 1−2α, safe same-class blocks are compatible when the active prefix is safe, while blocks with different anchors are rejected when it contains a long class interval.These are the acceptance and rejection guarantees of the compatibility test.Source: §3.3 · p. 6
Accepted blocks may still be contaminated, so repeated reuse can accumulate residual bias and motivates exposure control.The compatibility test may reject same-anchor blocks when their contamination is large.Source: §3.3 · p. 6

3.4. Exposure-capped reuse

Retiring blocks and replacing them with new blocks from recurring classes limits contamination bias while preserving variance reduction.A fixed block’s cumulative bias contribution remains bounded under the exposure mechanism.Source: §3.4 · p. 7

4. Regret analysis

ECR attains a regret rate that depends on the number of recurring classes rather than changes when changes are sufficiently infrequent. A matching lower bound shows this change-frequency condition is necessary up to logarithmic factors, while extensions and limitations are also discussed.

4.1. Upper bound

When changes are sufficiently infrequent, ECR's regret scales with the number of classes M rather than the number of changes S.The stated change-frequency condition is necessary up to logarithmic factors for attaining this recurrent rate.Source: §4.1 · p. 8
The upper-bound proof controls contamination through an exposure cap and obtains recurrent variance reduction by pooling capacity across returns to each class.Detector and compatibility deviations are handled separately before the regret decomposition is completed.Source: §4.1 · p. 8

4.2. Lower bound

The minimax lower bound separates the unavoidable cost of adapting to unknown change points from the recurrent estimation cost.For fixed M, σ, ∆min, and ∆max, the lower-bound conditions hold for sufficiently large T whenever T/S →∞.Source: §4.2 · p. 9

4.3. Discussion and extensions

For Lp loss with 1 < p < 2, recurrent pooling improves the estimation scale, but an ECR regret guarantee remains open.For vector-valued observations under Euclidean loss, the outlined extension retains the recurrent rate under the same sparsity regime for fixed dimension.Source: §4.3 · p. 9

5. Numerical results

ECR's synthetic regret slope is close to the perfect-reuse benchmark, and experiments illustrate how contamination changes the value of reuse. On the electronic-nose replay, ECR benefits from recurrence and outperforms the three baselines.

Synthetic experiments

ECR's empirical slope is 0.540, close to the perfect-reuse benchmark's 0.490 and the theoretical recurrent-rate exponent.The no-reuse algorithm's empirical slope is 0.725, close to its theoretical exponent of 3/4.Source: §5 · p. 9, Figure 5 · p. 10

Contamination and exposure control

With contaminated history, regret becomes U-shaped as reuse increases, and the best-performing budgets shrink as contamination rises.With clean history, regret decreases as more reuse is allowed.Source: §5 · pp. 9–10, Figure 5 · p. 10

Real-world data: electronic-nose assay

On the electronic-nose replay, ECR benefits from recurrence and outperforms all three baselines.The comparison includes EWMA, no reuse, and an adaptation of CONDOR.Source: §5 · p. 10, Figure 5 · p. 10

6. Conclusions

The paper characterizes online data reuse under recurrent non-stationarity and presents ECR as a nearly minimax-optimal algorithm. Its discussion distinguishes this cumulative tracking problem from prior guarantees, and its extended simulations examine contamination and related settings.

6. Conclusions

The paper characterizes online data-reuse complexity and presents ECR as a nearly minimax-optimal algorithm for realizing recurrence's statistical benefit.It identifies repeated bias accumulation as a central difficulty and points to sequential decision-making as a direction for future work.Source: §6 · p. 10

A. Extended related literature

Unlike global guarantees that do not distinguish returning concepts from new ones, this analysis gives a recurrence-dependent cumulative tracking rate without knowing non-stationarity parameters.The setting also requires estimating recurrent means from noisy observations and deciding which potentially contaminated historical data to reuse.Source: A. Extended related literature · p. 13

B. Extended simulations

The extended simulations examine contamination accumulation, CPU traces, vector-valued observations, different loss powers, and detector split selection.Unless stated otherwise, synthetic observations use independent Gaussian noise and error bars denote pointwise 95% Monte Carlo intervals.Source: B. Extended simulations · p. 14

B.1. Exposure capping under persistent contamination

These experiments examine ECR under persistent contamination, recorded traces, vector-valued recurrence, different loss powers, and a computationally cheaper detector. They show both the benefits of reuse and the conditions under which capping or faster split scanning matters.

B.1. Exposure capping under persistent contamination

ECR retires a mixed historical block at its exposure limit, while uncapped reuse continues propagating its bias as recurrences accumulate.The experiment contrasts persistent contamination with a benign version where additional reuse remains beneficial.Source: §B.1 · p. 14

B.2. Trace-driven NAB replay

16.9% lower mean terminal regret than no reuse; ECR also finishes below EWMA on all 100 evaluation paths in the trace-driven replay.The replay uses an imposed recurrence schedule because NAB has no ground-truth recurrent workload labels.Source: §B.2 · pp. 14–15, Figure 7 · p. 15

B.3. Vector-valued recurrence

0.040 versus 0.204 are the fitted log–log slopes of normalized regret for ECR and no reuse, respectively, in the vector-valued experiment.ECR’s regret remains close to a fixed multiple of the recurrent benchmark’s loss as the horizon grows.Source: §B.3 · p. 15, Figure 8 · p. 15

B.4. Dependence on the loss power

The relative improvement of ECR over no reuse decreases monotonically as loss power p rises from 1 to 2, but remains positive at p = 2.The authors relate the declining gain to adaptation costs under unknown changes.Source: §B.4 · p. 16

B.5. Computationally efficient ECR

At T = 262,144, geometric-grid ECR evaluates 4.41 million rather than 67.2 million splits per path, with regret increasing by 3.84%.The two implementations have similar normalized regret curves across tested horizons.Source: §B.5 · p. 16, Figure 9 · p. 16

B.6. Implementation details for the main-paper experiments

This section records the main-paper experiment settings and additional exposure-control and electronic-nose evaluations. Its results show that the best tested exposure budget depends on the amount of contamination.

Benchmark comparison and online recovery

The benchmark and online-recovery experiments use four Gaussian class means, reflected class paths, and horizons from 4,096 to 1,048,576.The no-reuse benchmark knows change points, while the perfect-reuse benchmark additionally knows the active class and pools its observations.Source: §B.6 · p. 17

Exposure-control experiment

The exposure experiment uses missed short shifts to create stored-history contamination, then compares exposure budgets over a shared sequence of recurring mean-64 and mean-zero segments.Positive excursion durations produce three classes and 88 changes; the clean control has two classes and 64 changes.Source: §B.6 · p. 17

Contamination and exposure budget

At 40% contamination, Bexp = 4 reduces regret by 241.0, while with clean history it increases regret by 13.6.At 30% and 40% contamination, Bexp = 2 has the lowest mean regret among tested settings; for clean history, Bexp = 8 and uncapped reuse give identical predictions.Source: §B.6 · p. 17

Electronic-nose replay

The electronic-nose replay uses recorded sensor vectors but a semi-synthetic recurrence order and durations, evaluating held-out days across 500 randomized schedules.Mean absolute errors averaged over schedules are 0.091 ppm for ECR, 0.112 ppm for EWMA, 0.117 ppm without reuse, and 0.1185 ppm for CONDOR.Source: §B.6 · pp. 17–18

C. Proof of the upper bound

The proof bounds regret by separating estimation noise, population bias, and initialization, then establishing the detector and segmentation properties needed to control those terms. It handles deviations from the detector’s good event before combining the bounds unconditionally.

C.1. Proof outline

The proof outline bounds population bias and estimation noise on the detector good event, localizes prefixes affected by detector deviations, then combines unconditional bounds.The final guarantee is expressed in terms of T, S, M, Δmin, Δmax, σ, and α.Source: §C.1 · p. 18

C.2. Regret decomposition

Regret is bounded by σEν[VT] + Eν[PT] + (σ + Δmax)Eν[K], separating estimation noise, population bias, and a block-initialization term.Conditioning on the decision stream freezes adaptive selection while leaving estimation-stream noise centered and independent.Source: §C.2 · p. 19

C.3. Detection and segmentation

Without a minimum segment length, the detector need not find every change or produce pure blocks; the proof instead uses anchors and bounds off-anchor and unanchored mass.The stated total mass is of order (S + K)ℓid, and the exposure cap controls bias from reusing contaminated blocks.Source: §C.3 · p. 20

Step 1 - Detector concentration

On the detector good event, no alarm implies every population CUSUM remains below twice the detection threshold.The local detector concentration event has probability at least 1 − α.Source: Step 1 - Detector concentration · pp. 20–21

Step 2 - Total number of blocks

False alarms are summably controlled, and each non-false alarm corresponds to a distinct change point, so there are at most S non-false alarms.The initial block adds one to the total block count.Source: Step 2 - Total number of blocks · p. 21

Step 3 - Proof of Proposition 3.1: anchor segmentation

The proof develops anchor-based bias and variance bounds for reuse, identifying pure or deviation-free suffixes and charging affected prefixes, contamination, and bad intervals. It also uses shared recurrent-class capacity and exposure control to bound variance and leakage without dependence on the number of changes in the variance scale.

Step 3 - Proof of Proposition 3.1: anchor segmentation

The first long pure interval forms a unique anchor; a different-class interval triggers an alarm before ℓid observations can enter the old block.On no-alarm rounds after anchor formation, the population mean stays within ∆min/4 of its class mean, and the stored block mean satisfies the same bound.Source: Step 3 - Proof of Proposition 3.1:… · pp. 21–22

Step 4 - Aggregate contamination control

On Gdet, contamination is confined to at most S + K + 1 segment-block intersections, each with fewer than ℓid decision-stream observations.With no false alarms, K ≤ S + 1; the lemma gives the resulting aggregate segmentation and block-bias budget for both streams.Source: Step 4 - Aggregate contamination control · p. 23

C.4. Compatibility guarantees

A long active prefix centered within ∆min/4 of class m rejects differently anchored blocks, while a safe prefix accepts safe blocks anchored at m.Actual reuse remains subject to the exposure budget.Source: §C.4 · p. 23

Step 1 - Compatibility concentration

A union bound over interval pairs and block indices makes the compatibility concentration guarantees simultaneous for data-dependent active prefixes and completed blocks.The proof first controls the empirical-to-population deviation for fixed deterministic interval pairs, then sums over rounds.Source: Step 1 - Compatibility concentration · p. 24

Step 2 - Proof of Proposition 3.2

When the active prefix is safe for m, safe m-anchored blocks are accepted; once it is anchored at m, differently anchored blocks are rejected.The local argument applies simultaneously at every round on Gdet ∩ Gcmp, an event with probability at least 1 − 2α.Source: Step 2 - Proof of Proposition 3.2 · p. 24

C.5. Control of the population bias

Population bias has current-block and reused-block sources, with current-block bias handled by harmonic charging and reused-block contamination controlled by exposure.Wrong-anchor reuse is possible only before the active prefix is long and centered within ∆min/4 of the current class, or when the compatibility statistic deviates from its population counterpart.Source: §C.5 · p. 25

Step 1 - Current-block bias

Current-block bias comes from detection-delay samples and short missed regimes; fixed contamination in anchored blocks is diluted as the prefix grows.The dilution yields a harmonic factor, while unanchored-block contributions are bounded per round and summed using the aggregate segmentation bound.Source: Step 1 - Current-block bias · pp. 25–26

Step 2 - Reused blocks’ bias

The exposure cap bounds a reused block’s cumulative per-sample influence regardless of how often it is reused.Correct-anchor bias comes from within-block contamination, while wrong-anchor reuse is controlled before the active prefix becomes long and centered.Source: Step 2 - Reused blocks’ bias · pp. 26–27
Only the first 2ℓid + 1 rounds per true-segment/detector interval can trigger the bias indicator, yielding an O((S + K)ℓid) bound.After the suffix accumulates ℓid decision-stream samples, its mean is within ∆min/8 of the current mean; a wrong-anchor block can otherwise be reused only under specified short-prefix, distance, or compatibility-deviation conditions.Source: Step 2 - Reused blocks’ bias · p. 27

C.6. Upper bound of the variance term

Anchored long-safe completed blocks preserve statistical progress across occurrences of the same class, establishing the recurrent-class argument for the variance upper bound.This analysis is pathwise on the detector good event; rare detector deviations are treated separately.Source: §C.6 · p. 28

Step 1 - Decomposition into three types of rounds

The variance proof decomposes prediction rounds into long-safe active prefixes, long-unsafe prefixes within ∆min/4 of the current class, and bad rounds.The decomposition separates the long-unsafe contribution, the recurrent-capacity contribution, and the contribution from bad intervals.Source: Step 1 - Decomposition into three… · p. 28

Step 3 - Long-safe active prefixes and recurrent capacity

Recurrent occurrences advance a shared class counter, removing dependence on the number of changes S and yielding an O(σ MT) variance scale before leakage correction.Completed anchored long-safe blocks preserve capacity exactly; each estimation observation increases it by Bexp, while two prediction updates consume at most 2. The leaky telescope accounts for capacity spent during bad intervals.Source: Step 3 - Long-safe active prefixes and… · pp. 30–32

Step 4 - Bad rounds

Unanchored blocks contribute O((S + K)√ℓid) to bad-interval complexity.True segments and detector blocks create O(S + K) stationary intervals, each containing O(ℓid) observations in an unanchored block.Source: Step 4 - Bad rounds · p. 33
Bad-round contributions from initial and mismatch intervals total O((S + K)√ℓid), while compatibility-deviation rounds contribute at most Ncmp.Source: Step 4 - Bad rounds · p. 33

C.7. Localization of detector deviations

After a detector deviation, the proof charges the prefix through the last deviation, then uses the remaining suffix to identify an anchor or charges its short stationary intervals.A long interval from a class in the suffix either triggers an alarm or establishes an anchor; without an alarm, the suffix cannot contain long intervals from two distinct classes.Source: §C.7 · p. 34

Step 1 - Post-deviation structure

Each deviation-free suffix contains a long interval from at most one class, and a pure suffix with ℓid decision-stream observations anchors the full stored block.Affected prefixes are charged separately; across O(S + K) stationary intervals, off-anchor and locally unanchored intervals contain O(ℓid) decision-stream observations.Source: Step 1 - Post-deviation structure · p. 35

Step 2 - Returning to the bias and variance bounds

The bias and variance bounds are extended without detector conditioning, preserving the exposure and capacity arguments and establishing Eqs. (103)–(106).The proof uses local anchors; remaining suffix intervals in locally unanchored blocks have length O(ℓid).Source: Step 2 - Returning to the bias and… · pp. 36–37

C.8. Combining the bounds

The upper-bound proof combines its regret components to establish Eq. (16); the lower-bound proof isolates two unavoidable sources of regret using oracle-aided problems.

C.8. Combining the bounds

Combining the established bounds and absorbing the initialization term proves Eq. (16) with a universal constant.The result holds uniformly over ν in E.Source: §C.8 · p. 37

D. Proof of the lower bound

Two oracle-aided problems isolate unavoidable regret from locating changes and estimating recurrent means, and their maximum lower-bounds R⋆_T(E).Each oracle gives the learner additional information, so either oracle lower bound also lower-bounds the original problem.Source: D. Proof of the lower bound · p. 37
The lower-bound argument fixes Δ_min and Δ_max as environment parameters, with Δ_max > (M − 1)Δ_min.Source: D. Proof of the lower bound · p. 37

D.1. Cost of unknown change points

The appendix separates the oracle regret costs of unknown change locations and unknown recurrent class means. It uses information-theoretic reductions to show how each uncertainty imposes an estimation cost.

D.1. Cost of unknown change points

For every admissible window length, some change location incurs at least ℓ∆/16 regret; the chosen length yields a cost of order (σ²/∆) log H.The construction embeds this single-macroblock uncertainty in a recurrent environment while revealing class means, labels, and macroblocks, leaving only each change location unknown.Source: §D.1 · pp. 37, 39, 40

D.2. Cost of unknown class means

The unknown-class-means argument reveals change points and class labels, then reduces the oracle problem to binary estimation for each class before summing the costs.The two candidate means for each class are separated around a class-dependent center, with the sign vector left unknown.Source: §D.2 · p. 40, Step 1 - Reduction to coordinate-wise… · p. 41

Step 1 - Reduction to coordinate-wise two-point problems

Conditioning on the other classes’ signs turns each class’s mean estimation into a two-point problem.The product prior permits treating one class at a time while averaging over the remaining signs.Source: Step 1 - Reduction to coordinate-wise… · p. 41

Step 2 - Solving the two-point problem

With δ = σ/(4√n), sequential two-point estimation has cumulative cost of order σ√n across a class’s n appearances.The proof sums the per-round estimation costs; its final rate applies under the stated condition on T.Source: Step 2 - Solving the two-point problem · pp. 42–43

E. Necessity of the exposure cap for ECR

The construction shows that uncapped ECR can repeatedly reuse contaminated historical data and exceed the recurrent benchmark scale. The exposure cap limits this repeated influence without changing detection or compatibility decisions.

E. Necessity of the exposure cap for ECR

In the construction, source blocks are accepted and repeatedly reused, while completed blocks from earlier reuse intervals and class-A segments are rejected.The source blocks are unanchored; blocks from reuse intervals are unsafe despite being anchored at class 0.Source: E. Necessity of the exposure cap for ECR · pp. 43, 46, 47, Figure 10 · p. 44
On zero-mean rounds in the latter half of reuse intervals, nonnegative population means prevent cancellation of positive source-block contribution; across J intervals, each zero-cell yields one round with population error at least 1/64.On G0, for M = 3, the resulting lower bound exceeds the recurrent benchmark scale.Source: E. Necessity of the exposure cap for ECR · pp. 47–48
Uncapped reuse exceeds the recurrent benchmark scale by a factor of order T^(1/8)/(log T)^(1/4) in the constructed environment.The construction uses M = 3 classes; the failure proposition establishes an environment where uncapped ECR incurs this excess.Source: E. Necessity of the exposure cap for ECR · pp. 43, 48
The exposure cap limits cumulative block influence while leaving detector blocks and compatibility decisions unchanged; capped reuse avoids the additional factor J.The source-block contribution is bounded by 4L(Bexp + 1).Source: E. Necessity of the exposure cap for ECR · p. 48

F. Retrospective limits

The retrospective lower bound uses two nearby change locations whose observation laws are hard to distinguish. It establishes a localization-error limit but does not show an additional logarithmic dependence on T.

F. Retrospective limits

Two change locations separated by 2h differ only on 2h observations, making their laws difficult to distinguish while confusion incurs at least h localization error.The proof applies a two-point testing argument to any estimator based on the full sample.Source: F. Retrospective limits · pp. 48–49
For any hard split, some change location yields at least h misassigned observations with probability at least e^-2/4 under the stated conditions.The lower bound gives the estimator both adjacent means and the entire observation sequence, so it also applies to online detection followed by retrospective post-processing.Source: F. Retrospective limits · p. 49
This two-point argument does not establish an additional logarithmic dependence on T; obtaining that dependence is beyond the paper’s scope.Source: F. Retrospective limits · p. 49

G. Extension to Lp

The Lp extension compares no-reuse and recurrent-pooling estimation scales and discusses how change localization affects the minimax picture. It does not provide an Lp regret guarantee for ECR.

Extension to Lp

This section is only a high-level discussion; the paper does not claim an Lp regret guarantee for ECR.Source: G. Extension to Lp · p. 50

The value of recurrence

When M < S + 1, recurrent pooling improves on the no-reuse benchmark for every fixed p > 0; for p < 2, the improvement factor is of order ((S + 1)/M)^(p/2).For 0 < p < 2, the respective scales are σ^p(S + 1)^(p/2)T^(1 − p/2) and σ^pM^(p/2)T^(1 − p/2).Source: G. Extension to Lp · p. 50

The cost of unknown change times

For p < 2, the change-time lower-bound heuristic accumulates order-∆^p loss over windows of order σ²∆^-2 log(T/S) across S changes.For p > 2, larger admissible jumps may produce a stronger worst-case dependence than the display based on ∆min.Source: G. Extension to Lp · p. 50

Implications for the minimax rate

The admissible growth of S becomes more restrictive as p approaches 2; for p = 1, 3/2, and 1.8, the stated powers are 1/2, 1/4, and 0.1.Source: G. Extension to Lp · p. 51

The value of recurrence

At p = 2, stationary estimation loss is logarithmic, while for 0 < p < 1 small residual biases are amplified relative to L1, so linear exposure accounting does not directly apply.The stated stationary loss is polynomial for p < 2 and bounded for p > 2.Source: G. Extension to Lp · p. 51

H. Extension to vector-valued observations

The paper extends ECR to vector-valued observations, with compatibility, exposure, and recurrent-capacity arguments retaining their scalar structure. It gives a vector regret bound and identifies when recurrence retains the scalar case’s improvement over relearning on every segment.

H. Extension to vector-valued observations

Dimension enters through concentration and Euclidean sample-mean error, while compatibility, exposure, and recurrent-capacity arguments retain their scalar structure.Each detector candidate and completed-block compatibility comparison costs O(d) operations.Source: H. Extension to vector-valued… · pp. 51–52
Vector compatibility preserves acceptance for safe same-class objects and rejection for long objects with different anchors.The safety definition uses Euclidean distance and reduces to the scalar definition when d = 1.Source: H. Extension to vector-valued… · p. 53
Repeated bias from a reused block is controlled by its fixed contamination mass times its exposure.The exposure calculation is unchanged from the scalar proof.Source: H. Extension to vector-valued… · p. 54
The vector extension derives a regret bound up to universal numerical constants.The authors note that a formal theorem would require restating and checking constants in Lemmas C.2–C.16.Source: H. Extension to vector-valued… · p. 55
Vectorization preserves the scalar case’s recurrence improvement factor, while dimension multiplies both benchmark scales.The benchmarks compare relearning on every segment with pooling observations from each recurrent class.Source: H. Extension to vector-valued… · p. 56
For fixed d, M, σ, ∆min, and ∆max, the sufficient recurrence-dominance condition reduces up to logarithmic factors to S = eO(T).Under this condition, the recurrent term dominates the displayed change-dependent terms up to lower-order α terms.Source: H. Extension to vector-valued… · p. 56
The vector lower bound embeds the scalar change-time construction in one coordinate when ∆max ≥ (M − 1)∆min, but no matching recurrent-estimation lower bound is established.That bound would require a separate d-dimensional packing argument and sufficient geometric slack.Source: H. Extension to vector-valued… · p. 56