74. Evidence from dependent observations
On this page · Permalink · Source line 3038
Let \(\mathcal F_{t-1}\) denote the available information immediately before observing the next measurement, including the chosen action, current model and any test selected using past data. A predictable test is a measurable function \(\phi_{t,j}\) of the upcoming measurement, chosen from this information, with values in \([0,1]\). Put
The model prediction is also predictable. It may change as the model learns. The true conditional mean \(m_{t,j}\) may depend on the entire past. No independence, stationarity or known reset state is assumed in this paragraph.
Choose budgets \(\alpha_j>0\) for a finite or countable prospectively specified family of test rules, with \(\sum_j\alpha_j\leq\delta\). Define
Proposition 66: Time-uniform predictable-residual certificate
With probability at least \(1-\delta\), for every time \(t\geq1\) and every registered rule \(j\),
For variables taking values in an interval of width \(c\), multiply the boundary by \(c\). The simultaneous guarantee remains valid when the observation time is chosen from the data.
Read proof · Recorded Lean scope · Visual guide: A confidence set can meet an exact certificate · Permalink · Source line 3057
Proof
For a random variable \(X\in[0,1]\) with conditional mean \(m\), its conditional centered logarithmic moment-generating function has value and first derivative zero at the origin. Its second derivative is the variance under exponential tilting. A variable supported on \([0,1]\) has variance at most \(1/4\), because its squared distance from \(1/2\) is at most \(1/4\). Integrating twice gives
Iterating this conditional inequality gives the same exponential bound for the martingale sum \(\sum_{s\leq t}(X_{s,j}-m_{s,j})\). Optimizing the exponential Markov inequality gives the two-sided bound \(2\exp(-2b^2/t)\). At the displayed \(b_{t,j}\) this is \(\alpha_j/[t(t+1)]\). Sum over \(t\), using \(\sum_{t\geq1}1/[t(t+1)]=1\), and then over \(j\). The resulting event holds at every time, so it also holds at a data-selected time. Scaling the variable proves the range version. \(\square\)
This elementary boundary pays a logarithmic time-union cost. It is not claimed to be optimal. Stronger confidence-sequence constructions are available in the literature [R20]. The proof here is supplied because the exact assumptions and the estimated object matter more than a sharp constant in this foundation.
The certificate estimates accumulated conditional predictive drift, not one fixed unconditional population probability. A prospectively chosen rule may use history, but an analyst cannot inspect an entire data sequence and then retroactively choose an unrestricted test with the same budget. New rules can be registered with fresh budgets and applied to future observations, using elapsed time after registration.