Active, anytime-valid risk controlling prediction sets

Summary

This paper proposes a probabilistic strategy for stream-based active learning which allows for construction of anytime valid prediction sets. The strategy stems from maximizing the variance process of an e-process, which is also used in designing the prediction sets. Relevant theoretical guarantees (validity and regret) and proof-of-concept experiments are presented.

Strengths

For me, the most interesting contribution of the paper, is that it brings the perspective of safe betting to active learning. The results are not written in the most flashy way, but the overall thought process is straightforward to follow and proofs are clear.

Weaknesses

- My assessment is that Section 2 lacks novelty, as in, very similar results have been proposed in earlier work under slightly different problem setting. Would be nice to make section 3 the main contribution of the paper, and present section 2 as a background/recipe section which leads to results of Section 3. - The proposed e-processes of Eq (5) and (6) are both from results of Waudby-Smith [2023 & 2024]. If i understand correctly, both of these processes are proposed for a more general frame-work, and the current paper applies it to its problem setting. - Proposition 1 and Theorem 1 are immediate corollaries by definition of the betting e-processes. - It is best that this is merged together and presented as a corollary for the specific choice of $M_t$. - Theorem 1 holds true for any $M_t$ is an e-process under the null. In the proof however, Proposition 1 is invoked. Would be good if the statement is updated and the assumption on $M_t$ is stated in it. - I am not widely aware of the literature. I just wanted to raise this flag that the related works section might be inadequate. I was expecting more work to have been done in this area. After reading the paper, I do not have a clear image of short history of results leading to this work, and I think this speaks of an incomplete literature review. There's no related work from active learning literature, while they aim to solve a relatively close problem (in cases identical). - The contributions section, particularly the second paragraph, is too technical given what it is already introduced. I would generally shorten the introduction and present a more thorough literature review in the main text. - I think parts of the problem setting are confusing, if not incorrect and lines 44-52 should be re-written. - Line 47 says $f$ outputs and action $A$ within a set $\mathcal A$. But later in Line 50, it is written that $f$ is a prediction set for $Y$. - Connection between $\mathcal A$ and $\mathcal Y$ is missing. I'm assuming $f$ output subsets of $\mathcal Y$ and I don't understand the auxiliary confusing notation of $A$ and $\mathcal A$. - If $f$ outputs a prediction set, then the notation $A$ and calling it an action is utterly confusing. Within active learning literature, $X$ is typically the action. - It is not evident in the notation of the risk that $\rho$ depends on $f$.

Questions

1) Why is assumption 1 in terms of $\rho$ and not just $r$? Is this needed? If possible, stating the assumption in terms of $r$ is cleaner in my opinion, since this way $\mathcal X$ and $\mathcal Y$ become assumption free. 2) The way section 2.2 is stated, what I collect from it is that the $M_t$ process is robust to adding a $\mathcal F_t$-adapted and bounded bias term. I can imagine that adding this bias may help with rapid increase of variance process of $M_t$. But I did not understand the motivation of this variance reduction, within the context of section 2. Could you please elaborate? 3) The proposed optimal labeling policy in Section 3 somewhat resembles a variance maximization techniques which are standard practice in stream-based active learning. Have you looked into the connections? How do these relate? 4) Doesn't the problem setting allow for comparison to standard active learning policies? Adding these would make the paper relevant to a considerable larger community.

Rating

6

Confidence

2

Soundness

4

Presentation

2

Contribution

2

Limitations

Limitations and assumptions are adequately stated.

Summary

The authors, in their work, extend the framework of Risk Controlling Prediction Sets (RCPS) to a sequential setting where data is collected adaptively, providing anytime-valid risk guarantees. Additionally, it proposes a framework for active labeling, which allows for selective querying of true labels within a predefined budget, enhancing the utility of RCPS by leveraging predictors to estimate expected risk based on covariates. Next, the authors extend the setting further and develop an active learning setting and optimal labeling policy and under a fixed label budget.

Strengths

- Extended setting of a risk-controlling prediction set setting. - Possibly rigorous in theoretical analysis.

Weaknesses

- The paper is notation-heavy, considers complex settings, and uses concepts that are not so commonly known. Unfortunately, the authors are doing nothing to help readers understand their work. - Many symbols (and there are many) are only introduced once. - The goal of the method is easy to miss in the body of the text. - The experimental section is hard to understand without reading the theory sections, and there are no meaningful conclusions. - There are no summaries, conclusions, schemas, pseudo-codes, or additional intuitions to help the reader understand the paper. - Experiments feel very limited. - I have doubts about the practicality of the introduced setting, as the paper needs better application examples. Due to very limited time, I was not able to read related works that were necessary to fully understand this paper, verify the theory, and possibly appreciate it fully. I would like to believe that all the theories presented in the paper are right, but even assuming that. I think the paper is below acceptance due to quite a poor presentation.

Questions

- What are other examples of applications for the proposed framework? - How in practise one should select $\theta$ and $\alpha$?

Rating

4

Confidence

1

Soundness

2

Presentation

2

Contribution

2

Limitations

I see no potential negative social impact of this work. Discussion on limitations is limited.

Summary

The setting extends the model of Bates et al.---which provide confidence-bound type guarantees on the performance of a trained ``black-box" predictor which are parametrised, and nested with respect to a monotonic parameter $\beta$---to the online setting. The goal of the original setting is to provide risk-controlling prediction sets (RCPS) mapping a feature $X$ to a set $\mathcal{T}(X)$ in the label space, which is judged on the basis of a predetermined safety criterion. The online extension is then well-justified by the observation that the calibration data itself is often limited without deploying the model in practice, particularly if training occurs in an online fashion. \\ The contributions of the paper are: 1. An extension of the RCPS notion to the online setting, and a derivation of guarantees that are anytime-valid. In other words, confidence sets are refined as data is accrued, nevertheless maintaining risk control over the entire stream. 2. An extension of the RCPS which is valid under active learning, where a learner may choose to obtain a label based on the covariates, and a fixed total query budget. In addition, the authors provide guarantees in the regret sense on the performance of derived methods in terms of the log-optimality criterion common for evaluating anytime-valid methods, which decouples into the regret of an exp-concave sequence dependent only on a quantity called the betting fraction, which due to log-concavity may be estimated sub-linearly in the number of rounds $T$ (due to exp-concavity of the log-optimality with respect to the betting fraction, this should be $O(\log(T))$) plus two concentration-type terms dependent on the convergence of two additional parameters derived from the risk, which may be estimated from the data. The convergence of such estimates will depend on the variance of the classifier's risk, and is determined on a case-by case basis. Experiments are included for verification of theoretical guarantees. Conclusion: While there are some weaknesses with regard to the communicability of the results for the intended audience, I believe on balance that the ideas in this paper will turn out to be of broad interest to the experimental community, and have clear practical relevance. From the theoretical perspective, although many of the ideas are directly generated from the theory of e-statistics, this is an encouraging example of tailoring theory to a clear practical need.

Strengths

1. The formalism is well developed, and demonstrates a high-degree of understanding of the use of e-variables as diagnostic tools of testing processes, and the derived confidence methods are a natural extension of the theory to a very practical setting. 2. The extension to label-efficient active learning further pushes the abstract theory into the realms of practicability, and the authors provide an example of a set of estimators for the various relevant quantities in the experiments. This gives an (somewhat implicit) recipe for practitioners looking to deploy the tools developed. 3. The regret bound derived gives an interpretable decomposition of the optimality of the regret of the growth-function (used to bound the log-optimality criterion), which decouples statistical quantities from the betting fraction, which is obtainable from standard online learning methods. 4. The experiments (although arguably non-extensive) provide minimal necessary examples and concrete estimators for the relevant quantities present in the regret bounds, and demonstrate empirically the convergence of the sum total of relevant components to their optimal values.

Weaknesses

1. A few more examples of the method being used in practice, along with the guarantees from the regret bound explicated, conditional upon the estimators idiosyncratic to the exact settings treated would be much more helpful than the abstract bound. Although for a theorist these results make sense, and keeping the general form due to the presence of the risk estimator variance and other empirical quantities does find some justification due to the variability of these quantities (which may alter the order of the regret bound), a few examples would really help illustrate the process + guarantees for a practitioner, which I guess would be the intended audience. I think this paper highlights the difficulty of the communicability of theoretical results in a digestible fashion, but does not constitute a weakness of the results themselves. 2. The experiments are not particularly extensive, and only encompass two examples; a contrived example of uniformly drawn features with Bernoulli labels (which is still a demonstrative diagnostic for the methods described, but have very well-behaved associated estimates), and a more realistic example based on the Imagenet dataset. Furthermore, as mentioned above, the comparison of online performance with respect to the regret bound would be even more helpful. 3. It would be nice to see some experiments illustrated with harder examples, for example in cases where the convergence of estimates would have a different than $O(\sqrt{T})$ rate.

Questions

1. To my understanding, the convergence rate of the estimation terms largely dominate the $O(\log(T))$ rate from the $G^{\beta}$-contribution. Are there any non-trivial examples where this isn't the case? 2. Is there any hope of obtaining an adaptive rate in the growth function---perhaps by means of a tailored variance-reduced estimator---which could yield an instance-dependent result, if the true risk-variance is low? The estimation of $q$ and $r$ seems like it might be particularly troublesome if one tries to derive something for a general case, but this might be a misunderstanding on my part.

Rating

7

Confidence

3

Soundness

4

Presentation

2

Contribution

3

Limitations

I have discussed limitations of the work above, and it seems that the authors have laid out the limitations of the degree of practicability due to the i.i.d. assumption (i.e., if training is coupled to the observed data stream). Nevertheless, I still think this is a solid contribution. With regard to the societal impact, the development of a robust theory of confidence in machine learning is undoubtedly a good thing.

Re: Rebuttal by Authors

Thank you for your detailed response to my rather short review. Other reviews also pointed out areas for improvement in terms of the presentation, so I hope you will address them in the next revision of your paper. Since the promised improvement in the presentation cannot be verified at the moment, I keep my score as it is. However, I'm okay with your work being accepted, since the other reviews recommended it.

Rebuttal recap

We thank the reviewers for reading our rebuttals and recommending or approving acceptance of our paper. We also appreciate the thoughtful feedback that we have received throughout the review process, and we will be sure to incorporate this in the ways we've described in our rebuttal.