Localized Adaptive Risk Control

We thank the reviewer for the insightful comments. Below, we address each comment point by point:

• The focus of this work is on producing calibrated predictions, i.e., predictions with risk control guarantees, rather than on providing more accurate predictions. To this end, we compare standard L-ARC against ARC with decaying step sizes [Angelopolous et al. 2024] (presented at ICML 2024), which, to the best of our knowledge, is the state-of-the-art online calibration scheme that offers statistical guarantees.
• The worst-case guarantee in 2.3.2. is valid for any sequence, not necessarily i.i.d. The statistical localized guarantee in Section 2.3.1. is obtained under the same data model considered in [Angelopoulous et al. 2024b].
• The worst-case deterministic guarantee (Theorem 2) is valid for any choice of data sequence, even if adversarial. Moreover, if the data is generated in an i.i.d. fashion—such as by sampling without replacement from a dataset or through online interaction with a stationary environment—L-ARC also provides the statistical guarantee stated in Theorem 1.

Thank you for considering our responses and for your prompt reply! Given the overall positive assessment of the paper and the comments, we would appreciate it if you could elaborate on what would have been necessary to achieve a higher score.

We thank the reviewer for the insightful comments. Below, we address each comment point by point:

• The terms in the bound incorporate factors that relate the algorithm's guarantees to domain-dependent quantities, such as the maximum value of the loss $B$ and the maximum value of the kernel $\kappa$. These quantities naturally appear in kernel-based algorithms [Kivinen et al. 2004, Gibbs et al 2023]. The values of these terms depend on the specific problem. For example, we have $B=1$ for the miscoverage loss and the FNR loss (experiment in Section 3.2); for the SNR regret in the experiment in Section 3.3, $B=1$; and for the electricity forecast, $B$ is given by the maximum value of the label variable $Y_t$. The value of $\kappa$ is a positive quantity controlled by the designer; it can be chosen arbitrarily, and it determines the level of localization of L-ARC.
• L-ARC can be generalized to multiple prediction sets and experts. We thank the reviewer for this suggestion, and note that this direction can be pursued by combining the results of L-ARC with those from the recent work “Improved Online Conformal Prediction via Strongly Adaptive Online Learning” by Bhatnagar et al. This paper focuses on localization in time using multiple experts active at different time instants. Combining this approach with L-ARC would provide a calibration method with localized guarantees both in the input space and in time. We will include this interesting research direction in our future work.

We thank the reviewer for the insightful comments. Below, we address each comment point by point:

• We aim to ease the implementation of the algorithm by providing code to reproduce the experiments. In the revised manuscript, we will also clarify the connection with online learning algorithms, enabling practitioners to leverage this connection when implementing L-ARC.
• We compare L-ARC against ARC with decaying step sizes [Angelopolous et al. 2024] (presented at ICML 2024), which, to the best of our knowledge, is the only online calibration scheme that offers statistical guarantees. Another recent algorithm, “Improved Online Conformal Prediction via Strongly Adaptive Online Learning” by Bhatnagar et al., proposes localizing predictions in time rather than in the input space. Since these two approaches are complementary and orthogonal, a direct comparison may not be particularly insightful. Nonetheless, L-ARC can be combined with this approach to achieve both time and input space localization. We consider this an interesting research direction for future work.

We thank the reviewers for their insightful comments. Below, we address each comment point by point:

• The input space of the prediction model is commonly referred to as the feature space in the machine learning literature. We will be happy to clarify the terminology in the revised manuscript.
• As typically assumed in the conformal prediction literature [Angelopolous et al. 2022, Angelopolous et al. 2024, Feldman et al. 2022], L-ARC is agnostic to the data distribution used to pre-train the prediction model. This means that L-ARC does not assume that the model is trained on the same population used for calibration and testing. We will clarify this point in the revised manuscript.
• The loss function in (2) is not necessarily convex; for example, it could be the miscoverage loss, which is non-convex. The assumptions about the properties of the loss function used to prove Theorems 1 and 2 are stated in Assumptions 3, 4, and 5. As referenced in the main text, the result reviewed in (6) is known from conformal inference [Angelopolous et al. 2024 and Gibbs and Candes 2021]. We will specify that the loss in (2) is not necessarily convex in the revised manuscript.
• As mentioned in the introduction and shown in Figure 1, using a single scalar threshold, “ARC may distribute such guarantees unevenly in the input space, favoring a subpopulation of inputs at the detriment of another subpopulation.” In contrast, as described in Section 1.3, L-ARC uses a threshold function in an RKHS, allowing it to “produce prediction sets with localized statistical risk control guarantees as in (9), while also retaining the worst-case deterministic long-term guarantees (6) of ARC.” As demonstrated in the experiments, which encompass both standard [Angelopolous et al. 2022, Angelopolous et al. 2024] and new benchmarks, L-ARC not only retains the long-term coverage of ARC but it also provides fairer and more homogeneous risk control across different subpopulations of the input space, which is an essential requirement for many applications.
• As mentioned at the beginning of Section 1.2, ARC does not offer any form of localized risk guarantee. As elaborated in Section 1.3, by replacing the scalar threshold with a member of the RKHS, L-ARC can instead provide localized risk control, a more general statistical guarantee. As stated in the bullet points in Section 1.3, the convergence results are the same as those for ARC, with an additional term that depends on the level of localization of the kernel function. This function dictates the degree of localization of the guarantee, as explained in Figure 2. These guarantees recover (6)-(7) when a non-localized threshold is used.
• As mentioned in the conclusion, memory efficiency is the main drawback of using localized thresholds, which motivates future work. However, the benefit of localized risk control may justify the increased computational and memory cost in some applications for which fairness is critical. While we have decided to leave the derivation and analysis of a memory-efficient version of L-ARC for future work, the attached PDF file demonstrates how to obtain a simple variant of L-ARC with constant memory requirements that still exhibits improved localized risk control. We plan to include these new empirical results in the supplementary material for the revised manuscript.
• The functional form (15) highlights how the current approach generalizes ARC. The proposed threshold function combines a scalar component $c_t$, like ARC, plus a varying component $f_t$ from an RKHS which allows to localize the risk control guarantee. We will elucidate the relation to ARC and the functional representation in the revised text.
• Equation (17)-(21) can be interpreted as the updates rule of (regularized) online gradient descent. In the revised manuscript we will refer to the work of [Kivinen et al., 2004] for a derivation.
• See the previous point and the attached pdf for a solution to this problem that has constant, not linear, memory requirements.
• In our paper, we provide experimental results that include standard and recent benchmarks [Angelopoulos et al. [2024b], Angelopoulos et al. [2022b]], as well as a new beam selection problem with engineering significance. Across this variety of experiments, as the reviewer notes, L-ARC not only guarantees the same worst-case deterministic guarantees as ARC (the curves overlap), but it also substantially improves coverage across different subpopulations of the data, as shown in the right panels of Figures 3, 4, and 5. The price to pay for localized risk control and increased fairness is an increased memory requirement. This cost is justified in all applications for which fairness and conditional coverage are necessary, as in the proposed examples. To address the memory requirement issue, in the attached PDF we provide a variant of L-ARC that allows control and reduction of memory and computational requirements. We will be happy to include these additional experiments in the supplementary material of the paper.

We thank the reviewer for the insightful comments. Below, we address each comment point by point:

• From a methodological point of view, the main innovation lies in using functions from an RKHS to define prediction sets that are calibrated online and that ensure localized risk control. The RKHS function is optimized online using gradient descent steps applied to kernels. As the reviewers noted, the optimization with kernel was originally studied in [Kivinen et al., 2004] and we apply this framework to online calibration. To this end, we had to develop several technical innovations. In Theorem 1, we analyze the functional derivative of the update and show that the stationary point satisfies the localized risk guarantee (41). This allows us to prove that, under Assumptions 4 and 5, we asymptotically achieve localized coverage. In Theorem 2, we prove that, for the problem of online calibration, the threshold function defined by the RKHS has a bounded infinity norm across all iterations (Proposition 3). This allows us to bound the first term in (76) and prove the worst-case guarantees. All these intermediate results as well as final theorems are novel contributions. In the revised manuscript we will clarify the connection between L-ARC update rules and [Kivinen et al., 2004], and emphasize the technical novelties introduced by the proof.
• The parts of the proof that are drawn from previous work are in Theorem 1, which leverages, as intermediate steps, the regret bounds (47) and (49) from [Kivinen et al. 2024] and [Cesa-Bianchi et al. 2004, Theorem 2], respectively. These works are referenced in the Appendix.
• Assumptions 2 and 3 are standard in the conformal risk control literature (see [Angelopolous et al. 2022, Angelopolous et al. 2024, Feldman et al. 2022]). These are reasonable and easily met in practice, as they state that the risk functional is bounded and that it decreases if the set grows larger, which is true for typical losses. Assumption 4 is a stronger version of Assumption 3, similar to (6) in [Angelopolous et al. 2024]. Like the previous assumption, it states that if the set size increases, the expected risk is strictly decreasing. Finally, Assumption 5 states that the loss function is left-continuous in the threshold value, and it is automatically satisfied for many popular losses. For all other losses, we note that this assumption can be easily satisfied by replacing ≤ with < in the definition of the set in (14). We plan to make this modification in the definition of the set predictor to remove this assumption.
• As discussed in Section 1.2, the weighting term in the localized risk equation amounts to a shift in the covariate distribution. By proving that the inequality is guaranteed for every shift $w\in \mathcal{W}$, we prove that the L-ARC provides risk control for all potential distributions shift in set $\mathcal{W}$. Specifically, inequality (22) states that for any shift $w\in \mathcal{W}$ it is possible to bound the shifted average risk averaged by a quantity that is shift dependent, hence the presence of $f_w(\cdot)$ and $w(\cdot)$. For example, if there is no shift, $w(\cdot)=1$, and this quantity equals zero. We thank the reviewer for carefully reading the Appendix and spotting the typo in lines 418-419. In fact, the $\max$ is a left over from a previous proof attempt, and it should be removed in the current version. We plan to correct this typo in the revised manuscript.
• Adaptive Risk Control refers to a generalization of ACI from conformal prediction to risk control, and is instantiated in our experiments with a decaying step size [Angelopolous et al. 2024] to guarantee statistical coverage. We chose [Angelopolous et al. 2024] as a benchmark because it is the state-of-the-art for online calibration, and, at the time of writing, it is the only online calibration scheme with statistical guarantees.