acceptodds
Under review as a conference paper at ICLR 2027

StreamLTT: Risk Certification for Policy Selection under Stream Dependence

Abstract

Learn-then-Test (LTT) provides a general framework for certifying deployment policies against a prescribed risk target, but its standard formulation targets a fixed population risk estimated from calibration losses. In sequential deployment, losses may instead be dependent and nonstationary, so the risk of a fixed policy can evolve with the observed history. We introduce StreamLTT, which replaces this fixed population risk with average predictable risk, defined by conditioning each decision’s loss on the information available before its outcome is revealed. Conditional centering turns empirical deviations from this target into a martingale sum, enabling both a test that adapts to predictable variance and a finite-sample Hoeffding alternative. Combined with family-wise error rate control, StreamLTT yields a simultaneously certified policy region that supports subsequent deployment selection. Across seven forecasting datasets and seven deployment risks, StreamLTT places the certified frontier substantially closer to the prescribed risk target than IID, robust-variance, block-bootstrap, and concentration-based alternatives, while empirical family-wise error closely follows the prescribed level. A finite-sample ablation further shows that the predictable-risk formulation drives the tighter risk frontier, while adaptation to predictable variance makes more effective use of the available family-wise error budget. StreamLTT therefore extends risk-certified policy selection to dependent deployment streams by addressing both what risk should be certified and how it should be tested.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Risk Control, Learn Then Test, Dependent Data, Simultaneous Risk Certification

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_hMkqOpenReview ↗
Rating
3(+1)
Confidence
1
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

The paper tackles the stream-level certification problem. It proposes an averaging of the conditional risks faced along the deployment stream. This allows for martingale fluctuations and enables finite-sampela dn variance-adaptive policy tests.

Critical strengths
  • The paper is equipped with sound theoretical results. The assumptions are outlined, and the theoretical results are listed. However, there are no visible key insights from those results.

  • The paper proposes a detailed algorithm, and the results discuss it thoroughly.

Critical weaknesses
  • The paper is very difficult to read and follow. The terms used are very niche and not recognized by the general ML reader. An illustrative figure at the beginning can help a lot. Furthermore, I recommend a human-written write-up that allows for better understanding, storytelling and flow.

  • Despite providing theoretical results, we would prefer to have some key insights outlined.

  • The results only tackle forecasting-based domains.

Questions for authors
  • How is this work related to the policy design of risk adaptation at test-time in [1]?

  • The method seems to apply to any type of policy at test time, but the experiments tackle time-series forecasting. Can we then say that the emthod is restricted to such applications?

[1] https://arxiv.org/abs/2408.08812

2 comments
AuthorsOpenReview ↗

Response to Reviewer hMkq: Key insights, presentation, and generality

We thank the reviewer for the feedback. In summary, we (1) state the two key insights of the paper (W2); (2) revise the presentation, including an overview figure in the introduction (W1); (3) clarify the relation to [1] (Q1); and (4) explain that the framework is not restricted to forecasting, with a new streaming classification experiment (W3, Q2).

W2: key insights. The paper answers two questions that arise when LTT is taken from IID calibration data to a deployment stream.

  1. What risk should be certified? On a dependent, nonstationary stream the risk of a fixed policy evolves with the history, so there is no single population risk. The average predictable risk in Eq. (5) averages the risks the policy faced at each decision time, using only the information available before each outcome. It is always well defined and reduces to the usual risk under IID data (Corollary 3.5).
  2. How can it be tested? By Eq. (6), the empirical risk deviates from this target by a martingale average, whatever the dependence in the losses. Valid tests therefore follow without stationarity or mixing assumptions: a finite-sample test (Theorem 3.2) and a variance-adaptive test (Theorem 3.4), combined into a simultaneously certified region (Theorem 3.7).

We will state these explicitly in the introduction and after the corresponding results.

W1: readability. We will revise the presentation for a general ML audience. As the reviewer suggests, we will add an overview figure to the introduction that shows the full pipeline (deployment stream → what to certify → why it is testable → policy-level tests → certified region). We will also add a notation table, plain-language explanations of the specialized terms where they first appear, and a one-sentence takeaway after each theorem. The paper was written by the authors; as disclosed in the AI Use Statement, generative AI was used only for language polishing.

Q1: relation to [1]. The two works sit at different stages of deployment and are complementary. TRAM [1] composes a fixed library of risk-neutral source policies under a reward–risk tradeoff specified at deployment; it constructs a policy in a reinforcement-learning setting. StreamLTT does not construct policies. Given any finite set of candidate policies, it certifies which of them satisfy a risk constraint over a dependent stream, with family-wise error control (Eq. (11)). Policies produced by a method such as TRAM under different risk weights could serve as the candidate family Θ\Theta for StreamLTT. We will add this discussion to the related work.

W3 / Q2: is the method restricted to forecasting? No. The framework is defined for any policy applied to a frozen model on an ordered stream with bounded losses revealed after each decision (Section 2); nothing in Definition 3.1 or Theorems 3.2–3.7 is specific to forecasting. We chose forecasting for the main experiments because temporal dependence arises naturally there.

To confirm this empirically, we added a streaming classification task with a reject option on the Airlines dataset (flight-delay prediction, ordered by time). We use a histogram-based gradient-boosted tree classifier (100 boosting iterations, at most 20 leaves per tree), trained on the initial 20% of the stream and then frozen. The classifier predicts when its confidence exceeds a threshold and abstains otherwise; the candidate policies are the thresholds. We certify two risks: selective error (a prediction is issued and is wrong, α=0.10\alpha=0.10) and false alarm (the positive class is predicted and the label is negative, α=0.05\alpha=0.05). The rest of the protocol is identical to the main experiments. Each entry reports Rˉmax⁡\bar R_{\max} / empirical FWER (mean maximum certified risk / family-wise error rate).

MethodSelective error (α=.10\alpha=.10), δ=.10\delta=.10Selective error (α=.10\alpha=.10), δ=.20\delta=.20False alarm (α=.05\alpha=.05), δ=.10\delta=.10False alarm (α=.05\alpha=.05), δ=.20\delta=.20
IID-LTT.043/.022.044/.041.023/.033.024/.065
LTT-HB-Holm.042/.006.043/.014.023/.010.023/.021
HAC-CLT-Holm.043/.026.045/.048.023/.035.024/.068
BlockBootstrap-Holm.043/.026.045/.047.023/.035.024/.067
EB-Howard-Bonf..042/.000.042/.000.023/.000.023/.000
StreamLTT-A.092/.083.093/.182.047/.094.048/.194
StreamLTT-H.092/.000.092/.002.043/.000.044/.000

The pattern matches the forecasting results: StreamLTT-A certifies up to risk 0.092–0.093 against a target of 0.10 and 0.047–0.048 against a target of 0.05, with empirical FWER below δ\delta in all four settings. We will add this experiment to the appendix.

AuthorsOpenReview ↗

Revised PDF uploaded

Dear Reviewer hMkq,

Thank you again for your review. We have uploaded the revised PDF, with changes marked in blue. The points you raised are addressed in the following places: the overview figure in Sec. 1 (Figure 1), the two key insights in Sec. 1 and Sec. 3.1, the plain-language explanations of specialized terms and the takeaway after each theorem in Secs. 1–3, the notation table in the appendix, the relation to [1] in Appendix A.1, and the streaming classification experiment beyond forecasting in Appendix D.6. Since generative AI was used to assist in drawing the new Figure 1, we have updated the AI Use Statement accordingly. We would appreciate it if you could let us know whether these address your concerns.

Reviewer_6U6SOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes StreamLTT, a framework for policy certification under dependent and nonstationary data. It replaces fixed population risk with average predictable risk and combines martingale-based tests with multiple-testing correction to certify candidate policies. The method is evaluated on seven real-world forecasting datasets in terms of the certified risk frontier and family-wise error rate.

Critical strengths
  1. I think this paper is trying to address an interesting problem with an interpretable risk formulation. The finite-sample Hoeffding test and variance-adaptive test formulation also offers a clear and interpretable trade-offs.
Critical weaknesses
  1. The experiments section are insufficient to fully validate the improvement from the proposed method. The exact experiment setting would need further clarification, and the presented evaluation are not sufficient evidence of better deployment performance.
  2. I think there should be more discussion on the connection between the theoretical guarantee and deployment safety. The theoretical results focus on the risk over observed horizon, while the safety on future rounds are not quantified.
Questions for authors
  1. Line 108: Can authors define policies explicitly here? What are the input and output of a policy defined here? Will the policy affect the output YnY_n?
  2. Definition 3.1: The proposed risk refers to the first N observed rounds, and the selected policy also preserves the guarantee for the same target. However, there is no guarantee on future rounds would satisfy the risk constraints, especially under distribution shifts. Can authors provide discussion on this point?
  3. Line 363: I was wondering how the ground truths is obtained to get empirical FWER? What are the exact experiment setting here, and how are the 2000 independent repetitions conducted?
  4. Line 367: Could authors clarify the purpose of using risk gap as primary evaluation metric? FWER is the upper bound for false certification, while it did imply full usage of risk, it does necessarily leads to improvement in policy selection. Can author provide additional discussion on this point?
2 comments
AuthorsOpenReview ↗

Response to Reviewer 6U6S

We thank the reviewer for the comments. In summary, we (1) define a policy explicitly (Line 108); (2) clarify the scope of the guarantee and how certification extends along the stream (W2, Definition 3.1); (3) describe how the ground truth and the 2,000 repetitions are obtained (W1, Line 363); and (4) explain the role of the risk gap, with a new table on the utility of the selected policies (W1, Line 367).

Line 108: definition of a policy. As in LTT, the object being certified is an operating rule applied to a frozen predictor. A policy θ\theta maps the information available before round nn (the covariates XnX_n, the model output, and previously revealed outcomes, i.e. Fn−1\mathcal F_{n-1}) to a decision an(θ)a_n(\theta), such as an interval width or an alarm. Its loss is Ln(θ)=ℓ(an(θ),Yn)L_n(\theta)=\ell(a_n(\theta),Y_n), observed once YnY_n is revealed. The policy does not affect YnY_n: all MM candidates are evaluated on the same stream, with no feedback from decisions to outcomes. We will add this definition to Section 2.

W2 / Definition 3.1: future rounds. We define the risk along the deployment stream precisely because, under shift, the risk measured on one segment need not describe another. Two consequences follow.

Under IID data, Rpred,NR_{\mathrm{pred},N} in Eq. (5) equals the population risk (Corollary 3.5), so StreamLTT recovers the same forward-looking guarantee as LTT.

Under shift, certification tracks the stream. Eq. (5) is defined for any horizon NN, and the guarantee in Eq. (11) of Theorem 3.7 holds for any fixed NN. Certification can therefore be repeated at a later pre-specified horizon N′>NN'>N on all data observed so far, and Eq. (11) then holds for Rpred,N′R_{\mathrm{pred},N'}. The certified region is updated as the stream evolves: a policy that deteriorates under shift drops out at a later horizon, and the deployed policy can be replaced. A guarantee about rounds not yet observed would require assumptions on how the stream evolves, which our setting deliberately avoids (Section 2). We will state this scope explicitly.

W1 / Line 363: experimental setting, ground truth and repetitions. The conditional risks in Eq. (5) are unobservable on real series, so FWER is evaluated on a semi-synthetic replay that keeps real loss vectors while making these risks exact. We compute the loss vectors of all candidate policies on the calibration set and split them into two pools, P0\mathcal P_0 and P1\mathcal P_1, by whether a reference policy fails. At round tt the generator selects P1\mathcal P_1 with a known probability wtw_t, set by a state visible before the loss, and draws one loss vector from that pool with replacement. Hence pt(θ)=(1−wt)μ0(θ)+wtμ1(θ)p_t(\theta)=(1-w_t)\mu_0(\theta)+w_t\mu_1(\theta) and Rpred,N(θ)=μ0(θ)+wˉ[μ1(θ)−μ0(θ)]R_{\mathrm{pred},N}(\theta)=\mu_0(\theta)+\bar w[\mu_1(\theta)-\mu_0(\theta)], with μk(θ)\mu_k(\theta) the mean loss of θ\theta in pool kk. Each of the 2,000 repetitions is an independent stream of N=50,000N=50{,}000 rounds, shared by all methods. We will add this protocol to Section 4.1 and Appendix C.4.

W1 / Line 367: why the risk gap, and deployment performance. The purpose of LTT is policy selection: the certified region is the set from which the operating point is chosen. FWER ≤δ\le\delta only establishes validity, and a procedure that certifies nothing is also valid. α−Rˉmax⁡\alpha-\bar R_{\max} measures how much of the admissible region is left uncertified, and hence how restricted the selection is. To show the effect on deployment directly, we report the utility of the policy selected from each certified region. All methods select from the same candidate family. Results at δ=0.10\delta=0.10, averaged over the seven datasets (widths relative to IID-LTT):

Risk / utilityIID-LTTLTT-HBHAC-CLTBlockBootEB-HowardStreamLTT-AStreamLTT-H
Interval: width ↓1.0001.004.999.9991.006.767.778
Lower tail: width ↓1.0001.005.999.9991.008.820.833
Severe: width ↓1.0001.030.997.9971.044.9721.013
Task regime: width ↓1.0001.012.9991.0001.017.819.842
Opposite: action rate ↑90.8%90.2%90.9%90.9%87.8%97.1%95.2%
Missed reversal: false-alarm rate ↓4.18%4.21%4.17%4.17%4.23%2.02%2.10%
False reversal: recall ↑74.5%74.3%74.6%74.6%74.2%81.9%81.4%

Relative to IID-LTT, StreamLTT-A selects intervals 23% narrower for interval miss and halves the false-alarm rate. The ordering is the same at δ=0.20\delta=0.20. Full tables will be added to the appendix.

AuthorsOpenReview ↗

Revised PDF uploaded

Dear Reviewer 6U6S,

Thank you again for your review. We have uploaded the revised PDF, with changes marked in blue. The points you raised are addressed in the following places: the explicit definition of a policy in Sec. 2, the scope of the guarantee and certification at later horizons in Sec. 3.3 and Appendix B.5, the replay protocol with the ground truth and the 2,000 repetitions in Sec. 4.1 and Appendix C.4, and the utility of the selected policies at both family-wise levels in Appendix D.4. We would appreciate it if you could let us know whether these address your concerns.

Reviewer_4FEdOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes StreamLTT, an extension of the traditional Learn-then-Test (LTT) framework, which assumes independent and identically distributed (IID) data, to temporally dependent and nonstationary data streams.

  1. It introduces average predictable risk, defined as the average of the expected losses conditioned on the information available at each time point, replacing the conventional notion of fixed population risk.
  2. It constructs a martingale difference sequence by subtracting the conditional expectation from each loss, and derives both a finite-sample-valid Hoeffding-type test and an asymptotic test that adapts to predictable variance.
  3. It develops a framework that applies family-wise error rate (FWER) control to the test results for individual candidates, allowing multiple operational policies to be certified simultaneously and enabling subsequent policy selection from among the certified candidates.

The experiments use seven time-series datasets and seven types of loss functions.

Critical strengths
  • S1 The problem setting is of practical importance

In real-world prediction systems, the assumptions of independence and stationarity are often violated. Therefore, the research objective of certifying the risks associated with actual decision-making, rather than merely evaluating model predictive accuracy, is meaningful.

  • S2 The paper provides both finite-sample and asymptotic guarantees

The finite-sample test in Theorem 3.2 relies on bounded losses and concentration inequalities for martingale differences, and Theorem 3.4 uses predictable variance to reduce conservativeness. The explicit consideration of the trade-off between theoretical robustness and practical statistical power is a valuable aspect of the work.

  • S3 The experiments attempt to disentangle the sources of improvement

By comparing StreamLTT-H and StreamLTT-A, the authors attempt to separate the effects of changing the risk definition from those of variance adaptation.

Critical weaknesses
  • W1 FWER control under history-dependent null hypotheses is not sufficiently established (Section 3.3, Theorem 3.7, and Appendix B.4)

The most important issue requiring careful examination in this paper is that the set of safe policies is itself random. The authors define the set of unsafe policies as

H0,N={j:Rpred,N(θj)>α}.\mathcal H_{0,N} = \{j:R_{\mathrm{pred},N}(\theta_j)>\alpha\}.

However, because Rpred,N(θj)R_{\mathrm{pred},N}(\theta_j) depends on the observed history, H0,N\mathcal H_{0,N} is generally a random set. The standard Holm procedure establishes FWER control in settings where the set of true null hypotheses is fixed. In this paper, the truth values of the null hypotheses may vary across sample paths. Therefore, the standard proof of the Holm procedure may not be directly applicable.

  • W2 The method for computing the “true average predictable risk” in the experiments is unclear (Section 4.1 and Appendix C.4)

In the experiments, the authors use the event

Rpred,N(θ)>αR_{\mathrm{pred},N}(\theta)>\alpha

to determine whether a policy has been incorrectly certified.

However, the conditional expectations appearing in

Rpred,N(θ)=1N∑n=1NE[Ln(θ)∣Fn−1]R_{\mathrm{pred},N}(\theta) = \frac{1}{N}\sum_{n=1}^{N} \mathbb{E}[L_n(\theta)\mid\mathcal{F}_{n-1}]

are generally not directly observable from real-world data.

  • W3 The baseline methods certify different risk quantities, raising concerns about the fairness of the comparison (Sections 4.1–4.2 and Appendix C.3)

The authors compare their method against several baselines, including IID-LTT, HAC-CLT-Holm, and block bootstrap methods. However, Appendix C.3 explains that conventional methods certify the standard population risk, whereas StreamLTT certifies the average predictable risk. In this case, the different methods may be estimating or certifying different statistical targets.

Questions for authors
  • Q1 Random null hypotheses and the Holm procedure

When the average predictable risk is a history-dependent random variable, is there a proof that the Holm procedure controls the FWER? Please explicitly explain the theoretical justification for extending the Bonferroni-based argument in Appendix B.4 to the Holm procedure.

  • Q2 Computation of the true risk

For the seven real-world datasets, how exactly was Rpred,NR_{\mathrm{pred},N} computed when evaluating the empirical FWER? Did you construct data-generating models that provide access to the true conditional risks, or did you use estimated values?

  • Q3 Implementation of the risk estimator

For the estimator p^n(θ)\widehat p_n(\theta) used in StreamLTT-A, please provide specific details about its model architecture, training procedure, update frequency, input features, and hyperparameters.

  • Q4 Finite-sample variance adaptation

To what extent is the FWER of StreamLTT-A affected by systematic errors in variance estimation or instability in the predictable variance? Could you demonstrate these effects through simulation?

4 comments
AuthorsOpenReview ↗

Response to Reviewer 4FEd (1/2): FWER control with a random null set (W1, Q1)

We thank the reviewer for the careful reading. On a dependent stream the risk of a fixed policy evolves with the history, so we define the risk along the information flow of deployment (Eq. (5)) and build tests on the martingale structure this target induces (Eq. (6)). Our answers follow this logic.

W1 / Q1: random null set and Holm. The randomness of H0,N={j:Rpred,N(θj)>α}\mathcal H_{0,N}=\lbrace j:R_{\mathrm{pred},N}(\theta_j)>\alpha\rbrace is the defining feature of the setting: because Rpred,NR_{\mathrm{pred},N} follows the realized history, whether a policy is safe is itself path-dependent. Our policy-level tests were constructed for this situation. The complete argument is below and will replace Appendix B.4. RN\mathcal R_N denotes the rejection set.

Step 1: joint validity. For each jj and z∈(0,1)z\in(0,1): (i) P(j∈H0,N,,pjH≤z)≤zP(j\in\mathcal H_{0,N},\\,p_j^H\le z)\le z under Theorem 3.2; (ii) lim sup⁡NP(j∈H0,N,,pjSL≤z)≤z\limsup_N P(j\in\mathcal H_{0,N},\\,p_j^{SL}\le z)\le z under Theorem 3.4.

Proof. (i) Let tz=Bjlog⁡(1/z)/(2N)t_z=B_j\sqrt{\log(1/z)/(2N)}. By Eq. (7), pjH≤zp_j^H\le z implies R^N(θj)≤α−tz\hat R_N(\theta_j)\le\alpha-t_z, and on {j∈H0,N}\lbrace j\in\mathcal H_{0,N}\rbrace we have Rpred,N(θj)>αR_{\mathrm{pred},N}(\theta_j)>\alpha. So the event is contained in {R^N−Rpred,N≤−tz}\lbrace \hat R_N-R_{\mathrm{pred},N}\le-t_z\rbrace, whose probability is at most exp⁡(−2Ntz2/Bj2)=z\exp(-2Nt_z^2/B_j^2)=z by Eq. (13), an unconditional bound. (ii) With TNT_N as in Eq. (14), on {j∈H0,N}\lbrace j\in\mathcal H_{0,N}\rbrace we have pjSL≥Φ(TN)p_j^{SL}\ge\Phi(T_N), so the event is contained in {TN≤Φ−1(z)}\lbrace T_N\le\Phi^{-1}(z)\rbrace, whose probability tends to zz.

No fixed null is assumed: the bound is on the joint event that the hypothesis is true and rejected.

Step 2: Bonferroni, with no condition on H0,N\mathcal H_{0,N}. With RN={j:pj≤δ/M}\mathcal R_N=\lbrace j:p_j\le\delta/M\rbrace,

P(RN∩H0,N≠∅)≤∑j=1MP(j∈H0,N,,pj≤δ/M)≤δP(\mathcal R_N\cap\mathcal H_{0,N}\ne\emptyset)\le\sum_{j=1}^M P(j\in\mathcal H_{0,N},\\,p_j\le\delta/M)\le\delta

by Step 1(i); for the adaptive test take lim sup⁡\limsup and use Step 1(ii) with MM fixed.

Step 3: Holm. Holm's thresholds depend on ∣H0,N∣|\mathcal H_{0,N}|, which is random, so Step 2 does not extend directly. On every sample path, however,

{RN∩H0,N≠∅}⊆{H0,N≠∅,min⁡j∈H0,Npj≤δ/∣H0,N∣}.(∗)\lbrace \mathcal R_N\cap\mathcal H_{0,N}\ne\emptyset\rbrace\subseteq\Big\lbrace \mathcal H_{0,N}\ne\emptyset,\\ \min_{j\in\mathcal H_{0,N}}p_j\le\delta/|\mathcal H_{0,N}|\Big\rbrace.\quad(\ast)

Indeed, when the first index of H0,N\mathcal H_{0,N} is rejected, only indices outside H0,N\mathcal H_{0,N} were rejected before, so at most M−∣H0,N∣M-|\mathcal H_{0,N}| steps have passed and the threshold in force is at most δ/∣H0,N∣\delta/|\mathcal H_{0,N}|. Holm controls FWER under either condition below.

(a) Exogenous risks (finite sample). Suppose pn(θj)p_n(\theta_j) is G\mathcal G-measurable and E[Ln(θj)∣Fn−1∨G]=pn(θj)E[L_n(\theta_j)\mid\mathcal F_{n-1}\vee\mathcal G]=p_n(\theta_j) for a σ\sigma-field G\mathcal G and all j,nj,n. This allows arbitrary nonstationarity.

Proof. Let Fn′=Fn∨G\mathcal{F}^{\prime}_n=\mathcal{F}_n\vee\mathcal{G}. Then ZnZ_n is a martingale difference with respect to {Fn′}\lbrace\mathcal{F}^{\prime}_n\rbrace, and the proof of Theorem 3.2 goes through with Fn′\mathcal{F}^{\prime}_n in place of Fn\mathcal{F}_n: MkM_k is a nonnegative supermartingale with M0=1M_0=1, so E[MN∣G]≤1E[M_N\mid\mathcal{G}]\le1 since G⊆F0′\mathcal{G}\subseteq\mathcal{F}^{\prime}_0. Hence Eq. (13) holds conditionally on G\mathcal{G}, and because {j∈H0,N}∈G\lbrace j\in\mathcal{H}_{0,N}\rbrace\in\mathcal{G}, Step 1 gives 1{j∈H0,N},P(pjH≤z∣G)≤z\mathbf{1}\lbrace j\in\mathcal{H}_{0,N}\rbrace\\,P(p_j^H\le z\mid\mathcal{G})\le z. Let m=∣H0,N∣m=|\mathcal{H}_{0,N}|, which is G\mathcal{G}-measurable. By (∗)(\ast), on {m≥1}\lbrace m\ge1\rbrace,

P(RN∩H0,N≠∅∣G)≤∑j1{j∈H0,N},P(pjH≤δ/m∣G)≤m⋅δ/m=δ.P(\mathcal R_N\cap\mathcal H_{0,N}\ne\emptyset\mid\mathcal G)\le\sum_{j}\mathbf 1\lbrace j\in\mathcal H_{0,N}\rbrace\\,P(p_j^H\le\delta/m\mid\mathcal G)\le m\cdot\delta/m=\delta.

Take expectations.

(b) Stable null set (asymptotic). Suppose P(H0,N=H∗)→1P(\mathcal H_{0,N}=\mathcal H^\ast)\to1 for a deterministic H∗\mathcal H^\ast. The result applies to either p-value.

Proof. For j∈H∗j\in\mathcal H^\ast, P(pj≤z)≤P(j∈H0,N,,pj≤z)+P(H0,N≠H∗)P(p_j\le z)\le P(j\in\mathcal H_{0,N},\\,p_j\le z)+P(\mathcal H_{0,N}\ne\mathcal H^\ast), so lim sup⁡NP(pj≤z)≤z\limsup_N P(p_j\le z)\le z by Step 1. Next, P(RN∩H0,N≠∅)≤P(H0,N≠H∗)+P(RN∩H∗≠∅)P(\mathcal R_N\cap\mathcal H_{0,N}\ne\emptyset)\le P(\mathcal H_{0,N}\ne\mathcal H^\ast)+P(\mathcal R_N\cap\mathcal H^\ast\ne\emptyset). The first term vanishes. By (∗)(\ast) with the fixed set H∗\mathcal H^\ast, the second is at most ∑j∈H∗P(pj≤δ/∣H∗∣)\sum_{j\in\mathcal H^\ast}P(p_j\le\delta/|\mathcal H^\ast|), whose lim sup⁡\limsup is at most δ\delta.

In the revised PDF, Theorem 3.7 will state the Bonferroni guarantee in general (Step 2) and the Holm guarantee under (a) or (b).

AuthorsOpenReview ↗

Response to Reviewer 4FEd (2/2): Evaluation protocol, comparison with baselines, and variance estimation (W2, W3, Q2–Q4)

W2 / Q2: computing the true average predictable risk. The conditional risks pn(θ)p_n(\theta) are unobservable on any real series, for every method. We therefore evaluate FWER on a semi-synthetic replay that keeps real loss vectors while making these risks exact. We compute the loss vectors of all candidate policies on the calibration set and partition them into two pools, P0\mathcal P_0 and P1\mathcal P_1, by whether a reference policy fails. At round tt the generator selects P1\mathcal P_1 with a known probability wtw_t, set by a state visible before the loss, and draws one loss vector from that pool with replacement. Hence

pt(θ)=(1−wt),μ0(θ)+wt,μ1(θ),Rpred,N(θ)=μ0(θ)+wˉ,[μ1(θ)−μ0(θ)],p_t(\theta)=(1-w_t)\\,\mu_0(\theta)+w_t\\,\mu_1(\theta),\qquad R_{\mathrm{pred},N}(\theta)=\mu_0(\theta)+\bar w\\,[\mu_1(\theta)-\mu_0(\theta)],

where μk(θ)\mu_k(\theta) is the mean loss of θ\theta in pool kk. No estimate enters the truth. Each of the 2,000 repetitions is an independent stream of N=50,000N=50{,}000 rounds, shared by all methods. These results thus evaluate FWER under the replay generator, not on the original series.

W3: do the baselines certify a different quantity?

The target. R(θ)=E[L(θ)]R(\theta)=E[L(\theta)] presumes one loss distribution. On a dependent stream the risk at round nn depends on the history, and Eq. (5) averages these conditional risks. This extends the population risk: under IID data the two coincide (Corollary 3.5).

The tests. Conditioning on the past is what makes certification possible under dependence. By Eq. (6), the empirical risk deviates from Rpred,NR_{\mathrm{pred},N} by a martingale average. StreamLTT-H (Theorem 3.2) and StreamLTT-A (Theorem 3.4) are built on this structure and need no independence, stationarity or mixing assumption (StreamLTT-A requires only Assumption 3.3), whereas IID-LTT and LTT-HB assume independent losses and HAC and block-bootstrap tests require stationarity and mixing. This is why we introduce the two StreamLTT tests.

The evaluation. All methods are scored against the same quantity, the generator's Rpred,N(θ)R_{\mathrm{pred},N}(\theta). In the main tables wˉ\bar w is the same in every repetition, so Rpred,N(θ)R_{\mathrm{pred},N}(\theta) is non-random and equals the long-run risk of the generator.

Q3: the estimator p^n(θ)\hat p_n(\theta). p^n\hat p_n is used only for the variance normalization in Eq. (10); it does not enter the risk target, the empirical risk, or StreamLTT-H. The one requirement (Section 2) is that it uses only outcomes revealed before round nn. We therefore use a simple predictable estimator, not a trained model:

p^n(θ)=∑i∈Hn(θ)Li(θ)+c,Lˉcal(θ)∣Hn(θ)∣+c,\hat p_n(\theta)=\frac{\sum_{i\in H_n(\theta)}L_i(\theta)+c\\,\bar L_{\mathrm{cal}}(\theta)}{|H_n(\theta)|+c},

where Hn(θ)H_n(\theta) is the set of rounds within the last WW rounds whose outcomes have been revealed and whose state matches the current one.

ItemValue
Architecture / trainingNone; Lˉcal(θ)\bar L_{\mathrm{cal}}(\theta) is computed once on the calibration set and then fixed
Input features (state)As in Appendix C.3: pointwise risks use the current forecasting information and policy quantities; regime and history-dependent risks add the corresponding information available in Fn−1\mathcal F_{n-1}
HyperparametersWindow W=⌈N0.65⌉=1134W=\lceil N^{0.65}\rceil=1134; shrinkage pseudo-count c=4c=4
Update frequencyEvery round, before the current outcome is revealed

Q4: sensitivity of FWER to the variance estimate. StreamLTT-H uses no variance estimate; StreamLTT-A adapts to the predictable variance and so relies on it (the trade-off noted in S2). We quantify this on four dataset–risk combinations (Electricity, PEMS04; interval miss, missed reversal; α=0.10\alpha=0.10; 2,000 repetitions). Entries are ranges of empirical FWER.

(i) Systematic error. We rescale V^N2\hat V_N^2 in Eq. (9) by cc.

cc0.500.700.851.001.151.50
δ=0.10\delta=0.10.160–.174.124–.135.104–.111.084–.094.069–.080.048–.054
δ=0.20\delta=0.20.253–.276.218–.238.188–.210.173–.187.160–.174.133–.145

The effect is smooth and follows Φ(c,zδ)\Phi(\sqrt c\\,z_\delta). A 15% underestimate brings FWER to about the nominal level; overestimation only adds conservatism.

(ii) Sample size, with W=⌈N0.65⌉W=\lceil N^{0.65}\rceil.

NN2,00010,00050,000
δ=0.10\delta=0.10.098–.101.083–.101.084–.094
δ=0.20\delta=0.20.199–.209.178–.198.173–.187

No value exceeds δ\delta by more than two Monte Carlo standard errors. For much shorter streams, StreamLTT-H provides finite-sample validity.

(iii) Unstable predictable variance. In each repetition we draw the stationary share of the high-risk state, π∈{0.2,0.5,0.8}\pi\in\lbrace 0.2,0.5,0.8\rbrace, once; the state follows P(St=1∣St−1)=0.98,St−1+0.02,πP(S_t=1\mid S_{t-1})=0.98\\,S_{t-1}+0.02\\,\pi. VN2/NV_N^2/N in Eq. (8) then has no deterministic limit. FWER is .009–.015 at δ=0.10\delta=0.10 and .019–.034 at δ=0.20\delta=0.20: no inflation.

These clarifications and results will be added to the revised PDF.

I thank the authors for their thorough response, which resolved my concerns. I changed my score from 2 to 3 accordingly.

AuthorsOpenReview ↗

Thanks to Reviewer 4FEd for the positive feedback and the score increase to 3

We sincerely thank the reviewer for the careful reading of our response and for raising the score. We are glad that the proof and the additional results and clarifications addressed your questions and concerns. All the revisions and additional results discussed in the rebuttal have been incorporated into the revised PDF, with changes marked in blue.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of the discussion and revisions for the Area Chair

Dear Area Chair,

Thank you for handling our submission. We also thank all reviewers for their careful reading and constructive feedback. A revised PDF has been uploaded, with all changes marked in blue and the main text within 10 pages. Below we first summarize the paper, and then how each reviewer's concerns are addressed.

Summary of the paper

Learn-then-Test (LTT) selects the operating parameter of a pretrained model, such as a confidence threshold, so that a risk stays below a prescribed level with high probability. Its guarantee requires IID calibration data, which fails on dependent, nonstationary deployment streams. StreamLTT extends LTT to this setting. In theory, it certifies the average of the conditional risks along the stream, which equals the population risk under IID data, and tests it with martingale-based tests that need no stationarity or mixing assumptions. In experiments on seven datasets and seven risks, we find that making the test dependence-aware is not enough: HAC and block-bootstrap tests leave the same risk gap as IID-LTT (0.030), whereas StreamLTT-A reduces it to 0.009 while its empirical FWER (0.090) stays at the prescribed 0.10 level. Prompted by the reviewers, the revision adds four results: a proof of family-wise error control when the set of safe policies is itself random, the robustness of StreamLTT-A to errors in the variance estimate, the utility of the selected policies (e.g., prediction intervals 23% narrower than IID-LTT), and a streaming classification task showing that the gain is not specific to forecasting.

Reviewer 4FEd

Reviewer 4FEd confirmed that our response resolved the concerns and increased the score from 2 to 3. The concerns were resolved as follows.

  • FWER control with a random null set. Theorem 3.7 now states the Bonferroni guarantee in general and the Holm guarantee under two conditions (exogenous risks, or an asymptotically stable null set). The complete proof replaces Appendix B.4.
  • Ground truth for the empirical FWER. Sec. 4.1 and Appendix C.4 describe the semi-synthetic replay, which resamples real loss vectors so that the conditional risks are known in closed form.
  • Comparison with the baselines. Appendices C.3 and C.4 state that all methods are evaluated against the same average predictable risk, which equals the population risk under IID data (Corollary 3.5).
  • Risk estimator. Appendix C.3 gives the estimator in closed form together with its configuration.
  • Sensitivity to the variance estimate. Appendix D.5 reports three simulations: FWER varies smoothly under systematic rescaling of the variance, remains at the nominal level up to Monte Carlo error for stream lengths from 2,000 to 50,000, and does not inflate when the predictable variance is unstable.

Reviewer 6U6S

Reviewer 6U6S gave a rating of 2. All points raised are addressed in the revision as follows.

  • Definition of a policy. Sec. 2 now defines a policy formally and states that decisions do not affect the outcomes.
  • Guarantee on future rounds. Sec. 3.3 and Appendix B.5 state the scope of the guarantee: it holds for any fixed horizon, coincides with that of LTT under IID data, and can be renewed by repeating certification at a later pre-specified horizon.
  • Experimental setting, ground truth, and repetitions. Sec. 4.1 and Appendix C.4 describe the replay protocol above; each of the 2,000 repetitions is an independent stream of 50,000 rounds shared by all methods.
  • Risk gap and deployment performance. Appendix D.4 reports the utility of the policy selected from each certified region. StreamLTT-A attains the best utility for all seven risks at both family-wise levels; relative to IID-LTT, its intervals are 23% narrower for interval miss and its false-alarm rate is about half.

Reviewer hMkq

Reviewer hMkq gave a rating of 2. All points raised are addressed in the revision as follows.

  • Readability. The introduction has a new overview figure (Figure 1). We also added a notation table, plain-language explanations of specialized terms where they first appear, and a takeaway after each theorem. The paper was written by the authors; generative AI was used for language polishing and, in the revision, to assist in drawing Figure 1, as disclosed in the updated AI Use Statement.
  • Key insights. Stated explicitly in Sec. 1 and Sec. 3.1.
  • Relation to [1]. Discussed in the related work (Appendix A.1).
  • Beyond forecasting. Appendix D.6 adds a streaming classification task with a reject option on the Airlines dataset. StreamLTT-A certifies up to risk 0.092–0.093 against a target of 0.10 and 0.047–0.048 against a target of 0.05, with empirical FWER below the prescribed level in all four settings.

We are grateful to Reviewer 4FEd for acknowledging our response and raising the score. We thank the Area Chair and all reviewers again for their time and effort.

Best regards, The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.