Localized Adaptive Risk Control

Summary

This paper proposed a novel localized adaptive risk control algorithm that provides not only average case risk guarantees but also worst-case guarantees. Simulations in several different applications are provided, demonstrating the improved performance when compared with adaptive risk control.

Strengths

The paper is very well written. The illustration figures are very helpful in explaining the localization effects of difference choices of $w(x)$. The problem is also well motivated: the worst case risk guarantee is indeed very important in applications such as medical imaging. The proposed algorithm is novel.

Weaknesses

1. My major concern is on the simulation results. Though I appreciate the improved performance compared with ARC in different settings, the paper does not provide any comparisons with the state-of-the-art approaches in these applications. For example, for electricity demand prediction, the SOTA method is based on quantile regression and there are many papers published trying to provide better predictions on demand. How does the proposed LARC compare with these SOTA methods? If LARC does not outperform the existing methods, what are the benefits of using LARC? Similarly, tumor image segmentation is also a standard task in medical imaging, so it will be interesting to compare LARC with the SOTA methods in that field too. 2. It seems that the worst-case guarantee is only provided for i.i.d. data, is that correct? If so, what's the challenge of obtaining a worst-case guarantee for arbitrary data sequence? In addition, the paper mentioned that the major improvement of this paper compared with [Angelopoulos et al., 2024b] is the online setting. However, usually, i.i.d. data is obtained by sampling uniformly from an offline data set. So what is the significance of the theoretical results if the worst-case guarantee can only be provided for i.i.d. cases?

Questions

See above

Rating

5

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

NA

Summary

This paper addresses the design and analysis of the localized version of adaptive risk control (L-ARC). In the first section, the problem of classical ARC is nicely introduced, showing the threshold updating mechanism and the convergence analysis of the resulting loss. Then, the problem setting, design, and analysis of ARC are naturally generalized to those of L-ARC. Finally, L-ARC is applied to three practical problems of electricity demand forecasting, tumor segmentation, and beam selection. The result of the experiments supports the usefulness of L-ARC.

Strengths

The application scope of L-ARC is broad, and it can be utilized in various application examples. The reviewer believes L-ARC has a high potential for broad impacts. The update model (17) and (18) developed for L-ARC in this paper is novel. The theoretical guarantee, in particular, the convergence analysis of the localized loss is also given under standard assumptions.

Weaknesses

Both Theorems 1 and 2 state that the localized loss is bounded by \kappa * B, meaning the maximum value of the kernel and an upper bound of the loss. In the reviewer's understanding, the theorems are technically correct, but he/she cannot find their value. They seem to be just deriving an obvious upper bound from the assumptions.

Questions

Related to Theorems 1 and 2, could the author comment on their value of the upper bound of the localized loss? L-ARC updates the threshold function, denoted by $g_t()$. The setting seems to be restrictive. Could the authors extend the setting to the case of multiple prediction sets? In other words, multiple scoring functions s_1, s_2, ... are considered and their thresholds are adaptively updated in a similar manner to (17) and (18).

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

The limitation of L-ARC is stated in Section 5, saying that it requires a memory function of storing the input data.

Summary

The paper introduces Localized Adaptive Risk Control (L-ARC), an enhancement of Adaptive Risk Control (ARC). L-ARC updates a threshold function within a Reproducing Kernel Hilbert Space (RKHS) to provide localized risk guarantees while maintaining ARC's worst-case performance. Experiments show that L-ARC improves fairness across different data subpopulations in tasks like image segmentation.

Strengths

The introduction of Localized Adaptive Risk Control (L-ARC) is a significant advancement over traditional ARC. By focusing on localized risk guarantees, L-ARC addresses the critical issue of uneven risk distribution across different data subpopulations, which is a well-known limitation of ARC.

Weaknesses

1. The introduction of a threshold function within an RKHS and the associated online adaptation process may complicate the implementation. Practitioners might find it challenging to understand and apply the method without a significant background in RKHS and online learning algorithms. 2. The paper primarily compares L-ARC with traditional ARC. Including comparisons with other state-of-the-art risk control or calibration methods would provide a more comprehensive evaluation of L-ARC's strengths and weaknesses.

Questions

Refer to Weaknesses.

Rating

5

Confidence

3

Soundness

2

Presentation

2

Contribution

2

Limitations

N/A

Summary

This paper introduces an online calibration method to enhance the Adaptive Risk Control (ARC) framework. ARC traditionally adjusts prediction sets based on a scalar threshold to ensure long-term risk control and marginal coverage guarantees. However, as mentioned in the paper, it may unevenly distribute risk guarantees across different subpopulations. L-ARC addresses this by updating a threshold function within a reproducing kernel Hilbert space (RKHS) to provide localized statistical risk guarantees, ranging from conditional to marginal risk, while preserving the worst-case performance. My additional comments are as follows.

Strengths

- The paper is easy to read. It could have been better structured, but it is okay. - The authors have proposed a new technique for calibration and provided theoretical and experimental results.

Weaknesses

- The concept of input space is not clear in the introduction. - Is the pre-trained model trained on all the data sources that will be used during the calibration process if they are different? - Is the loss function convex in (2) convex? And what the intuitive explanation that (6) should hold is. Does it somehow follow from the regret analysis of the online gradient descent algorithm, which converges at the same rate? - What is the crucial reason for using the RKHS function instead of a scalar? How is this useful? - Ideally, the introduction of RKHS should have helped with the rates, but it looks like the rates in (12) and (13) are worse than the rates in (9) and (6), so then in what terms localized ARS is better? - On the other hand, keeping track of a function g_t in RKHS for each t is way more expensive than just keeping track of a scalar in practice. Why the proposed method makes sense is not clear. - What is the reason to consider the functional form in (15) - How are the updates in (17)-(21) derived? Equation (19) is fine, which is the standard representation of a function in RKHS - As mentioned before, the additional challenge with RKHS is that we need to now store a^i_t from i =1 to t because we need to update them, and for large T, this could be problematic in practice. And if you make the dictionary size of storing them constantly, then it would incur additional regret in the final terms. - The experimental results are weak. They are not descriptive enough to make sense of the advantages of the proposed techniques over the advantages of existing methods. The long-term coverage plots look almost similar, so why is the benefit coming in other figures? Also, authors should report the downside of the proposed RKHS-based approach, which would require more memory access to implement the proposed method, which is not required for ARS. So, comparisons are also not fair.

Questions

Please check the weaknesses.

Rating

4

Confidence

4

Soundness

2

Presentation

2

Contribution

2

Limitations

N/A

Summary

This paper proposes the Localized Adaptive Risk Control (L-ARC) scheme for learning to perform conformal prediction from online data. In the setting under consideration, the data is potentially non-i.i.d. and the scalar threshold parameter typically used by existing methods in the construction of the prediction set is replaced by a function learned online from the data stream via functional stochastic gradient descent over a reproducing kernel Hilbert space (RKHS). It is shown that the selection of the RKHS -- i.e., the properties of the associated kernel, such as the scale parameter of a radial basis function (RBF) kernel -- yields "localization" of the resulting conformal predictor to the data set in the sense that prediction performance (miscoverage error) remains consistent across distinct subpopulations within the data. This is demonstrated through experiments on electricity forecasting, medical image segmentation, and beam selection problems that illustrate the localization property, while theoretical results characterize the price paid for this localization in terms of looser bounds on suboptimality and convergence rate. The key algorithmic contribution of the paper is the use of *online* kernel learning, which is well-studied (compare eqs. (19)-(21) in the present submission with (10)-(12) in [Kivinen et al., 2004]), to learn a *function* to replace the scalar threshold typically used in conformal prediction. Existing methods for online conformal prediction [Gibbs and Candès, 2021; Bhatnagar et al., 2023; Feldman et al., 2023; Angelopoulos et al., 2024] consider either a fixed scalar threshold in the construction of the prediction set, while recent work on conformal prediction with a threshold function [Gibbs et al., 2023] does not directly apply to the online setting. The primary theoretical contributions are the establishment of upper bounds characterizing the localization effects of the choice of RKHS kernel in terms of a certain notion of suboptimality and the rate of convergence to a neighborhood of optimality, where the size of the neighborhood is shown to depend on the choice of kernel. The experimental results illustrate that L-ARC outperforms the existing, non-localized ARC method [Gibbs and Candès, 2021; Feldman et al., 2022] at achieving the desired level of miscoverage error across distinct subpopulations.

Strengths

While the existence of an online method for conformal prediction over non-i.i.d. data that uses threshold functions appears to be an open problem in the recent conformal prediction literature, the significance and potential utility of using a threshold *function* taken from a RKHS instead of a scalar or another class of function are not immediately obvious. However, the theoretical and experimental results of this paper indicate that a useful notion of "localization", where the choice RKHS kernel allows reliable conformal prediction on data with distinct subpopulations, results from considering this class of threshold functions -- this is a very interesting and original insight that is likely to draw attention in the conformal prediction community, and is a major strength of the paper. The theoretical results also provide some useful insight into the effect of kernel choice in L-ARC, and the main steps in the analysis appear to be sound (I read but did not thoroughly check all details in the appendix). Finally, the experimental results provide strong support to the utility of the localization effect of the choice of kernel, without which the theoretical results would lose much of their force and the significance and potential utility of L-ARC would remain unclear.

Weaknesses

The primary weaknesses of this work arise from lack of context with previous work and lack of motivation and discussion of the technical results. These issues make it difficult to accurately judge its significance and contribution. Specifically: 1. Important context with previous work is missing. First, the L-ARC method proposed in Sec. 2.2 is essentially an adaptation of online kernel learning (see [Kivinen et al., 2004] and its many citers) to the conformal prediction setting (as mentioned in the summary above, eqs. (19)-(21) in the present submission are very similar to (10)-(12) in [Kivinen et al., 2004]), yet this connection is not mentioned. This information is important for clarifying the limits of the present paper's contribution. 2. The relationship between the technical results presented and previous analyses is unclear. In particular, it is unclear from the text (including the proofs in the appendix) what parts of the analysis draw on previous analyses of conformal prediction methods -- if the results are entirely independent and original, this can be highlighted -- and what key technical innovations were required in the theoretical analysis. 3. Motivation of the technical results and discussion and clarification of their meaning is generally lacking. As a result, the technical meaning and effect of "localization" characterized in Sec. 2.3, especially in the Assumptions and Theorem 1, remain unclear. Specific questions regarding these issues are included in **Questions** 3, 4, and 5 below.

Questions

1. What are the main technical innovations in the proofs of the main results? 2. What parts of the analysis draw on previous work? 3. How reasonable are the assumptions presented in Sec. 2.3 and when do they hold (especially Assumptions 4 and 5)? 4. What is significance of the weighting inside the expectation on the LHS of eq. (22) and why is this relaxed, reweighted expectation meaningful? 5. What is the role and importance of the weighting function $w(\cdot)$ and the corresponding terms containing $f_w(\cdot)$ in eq. (22)? The presence of $w(\cdot)$ seems like an artifact arising from considering the covariate shift $w(\cdot)$ in lines 418-419 in the appendix, which might be expected to go away when $max_w$ is taken in the proof of Lemma 1 in Sec. A; why do $w(\cdot)$ and $f_w(\cdot)$ persist in the statement of Theorem 1 and how do we interpret them? 6. The present paper uses the term Adaptive Risk Control (ARC) to refer to the methods proposed in [Gibbs and Candès, 2021] and [Feldman et al., 2022] on lines 18-19, but these works call their methods Adaptive Conformal Inference (ACI) and Rolling Risk Control (Rolling RC), respectively; which of these does ARC refer to, and which is implemented in the experiments?

Rating

6

Confidence

4

Soundness

3

Presentation

2

Contribution

3

Limitations

Aside from the issues raised above, the limitations have been adequately addressed.