Localized Adaptive Risk Control
Authors: Matteo Zecchin
Osvaldo Simeone
Venue: NeurIPS 2024 poster (2024)
Keywords: online conformal risk control
uncertainty quantification
conformal predictions
Primary area: online_learning
TL;DR: A novel scheme for online calibration that offers both worst-case deterministic long-term risk control and statistical localized risk guarantees.

Abstract: Adaptive Risk Control (ARC) is an online calibration strategy based on set prediction that offers worst-case deterministic long-term risk control, as well as statistical marginal coverage guarantees. ARC adjusts the size of the prediction set by varying a single scalar threshold based on feedback from past decisions. In this work, we introduce Localized Adaptive Risk Control (L-ARC), an online calibration scheme that targets statistical localized risk guarantees ranging from conditional risk to marginal risk, while preserving the worst-case performance of ARC. L-ARC updates a threshold function within a reproducing kernel Hilbert space (RKHS), with the kernel determining the level of localization of the statistical risk guarantee. The theoretical results highlight a trade-off between localization of the statistical risk and convergence speed to the long-term risk target. Thanks to localization, L-ARC is demonstrated via experiments to produce prediction sets with risk guarantees across different data subpopulations, significantly improving the fairness of the calibrated model for tasks such as image segmentation and beam selection in wireless networks.

Localized Adaptive Risk Control
Matteo Zecchin Osvaldo Simeone
Centre for Intelligent Information Processing Systems
Department of Engineering
King's College London
London, United Kingdom
(matteo. 1. zecchin, osvaldo.
osvaldo wtt..i...smmmmee0....... ac uk
Abstract
Adaptive Risk Control (ARC) is an online calibration strategy based on set predie- tion that offers worst-case deterministic long-term risk control, as well as statistical marginal coverage guarantees. ARC adjusts the size the prediction set by vary- ing single scalar threshold based on feedback from past decisions. In this work, we introduce Localized Adaptive Risk Control (L-ARC), an online calibration scheme that targets statistical localized risk guarantees ranging from conditional risk to marginal risk, while preserving the worst-case performance ARC. L-ARC updates threshold function within a reproducing kernel Hilbert space (RKHS), with the kernel determining the level localization of the statistical risk guarantee. The theoretical results highlight trade-off between localization of the statistical risk and convergence speed to the long-term risk target. Thanks to localization, L-ARC is demonstrated via experiments to produce prediction with risk guar- antees across different data subpopulations, significantly improving the fairness the calibrated model for tasks such image segmentation and beam selection in wireless networks.
Introduction
Adaptive risk control (ARC), also known as online risk control, is a powerful tool for reliable decision-making in online settings where feedback is obtained after each decision [Gibbs and Candes 2021 Feldman et al., 2022). ARC finds applications
domains, such as finance, robotics, and health, in which it is important ensure reliability in forecasting, optimization,
control of complex systems [Wisniewski et al. 2020 Lekeufack et al.) 2003) Zhang et (023) |Zecchnn et al. 2024]. While providing worst-case deterministic guarantees of reliability, ARC may distribute such guarantees unevenly in the input space, favoring a subpopulation of inputs at the detriment of another subpopulation.
As an example, consider the tumor segmentation task illustrated in Figure objective is to calibrate pre-trained segmentation model to generate masks that accurately identify tumor areas according to a user-defined reliability level (Yu et al. 2016). The calibration process typically involves combining data from various datasets, such as those collected from different hospitals. For an online setting, as visualized in the figure, ARC achieves the desired long-term reliability in terms of false negative ratio. However, does so by prioritizing certain datasets, resulting in unsatisfactory performance on other data sources. Such behavior is particularly dangerous, as may result in some subpopulations being poorly diagnosed. This paper addresses this shortcoming of ARC by proposing a novel localized variant of ARC.
this setting, the
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Prodiction Seta
Longe
Ouline Calibention
Pre-irsined
Sepmentation Model
0.25
0.01
Lanb Dataset
Datasct- condittoned FNR
Aecuta
Froeet
LARC
Lacbs
Figure I: Calibration of tumor segmentation model via ARC (Angllopoulos et al. 2024a] and the proposed localized ARC, L-ARC. Calibration data comprises images from multiple sources, namely, the Kvasir data set (Jha et al. 2020] and the ETIS-LaribPoly LaribPolypDB data set (Silva et al. 2014]. Both ARC and L-ARC achieve worst-case deterministic long term risk control in terms of false negative rate (FNR). However, ARC does so by prioritizing Kvasir samples at the detriment of the Larib data source, for which the model has poor FNR performance. In contrast, L-ARC can yield uniformly satisfactory performance for both data subpopulations.
1.1 Adaptive Risk Control
To elaborate, consider an online decision -making scenario in which inputs are provided sequentially pre-traines model. At each time step 2 the model observes a feature vector X,, and based on a bounded non-conformity scoring function X x y + [0, Smax] and threshold X E R, it outputs a prediction
C = C(X, Ax) {y E y: : s(x,, v) S dr).
(1)
where y is the domain of the target variable Y. After each time step t, the model receives feedback in the form of a loss function
I L(C,, Y2)
that is assumedd to be non non-negan non-negaevve, upper bounded by B < oc and non-increasing in the predicted size |Ct]. A notable example is the miscoverage loss
[(C, y) = 1y & C).
Accordingly, for an input-output sequence ((X,, Yo) the performance of the set predictions (C.)T. can be gauged via the cumulative risk
1 - T I(T)
1 T
((C,,)))
Σ L.
(4)
For user-specified loss level a and learning rate sequence {ne 1T ARC updates the threshold A in as [Feldman et 2022
A411 Ao + me(Le - a),
(5)
where L, measures the discrepancy between the current loss (2) and the target a. For step size decreasing as 1)t 1/2 for 10 and an arbitrary m > the results in [Angelopoulos et al. 2024b) imply that the update rule (5) guarantees that the cumulative risk (4) for the miscoverage loss (3) converges target level a for any data sequence {(X,, Y:) as
(((T) - aa < Smax + B/B
VT
thus offering worst-case deterministic long-term guarantee. Furthermore when data are generated i..d. as (X,, Y ~ Pxy for all 2 1, in the special case of the miscoverage loss the set predictor produced by enjoys the asymptotic marginal coverage guarantee
lim Pr & Crl - T'
where the probability computed with respect to the test sample (X, Y) ~ Pxy, which is indepen- dent of the sequence of samples ((X,, Y.)) and the convergence is in probability with respect to
the sequence ((X,, Y2) Note that AAgellopouoss et al. 2024b), stronger version of (7)
provided, in which the limit holds almost surely.

---

Degree of Localiaaioon
Localization
Maximun Localiaation
Localized Guarantee
Marginal Guarantec
Conditional Guarantee
Ma(a)
Ma(s)
ux(x))
( soylr) myle))
wyfx)
ms(x)
The degree of localization in L-ARC dictated by the choice of the reweighting function class W via the irngginal-t-condition guarantee (9). At the leftmost extreme, illustrate constant reweighting functions, for which marginal guarantees are recovered. At the rightmost extreme. reweighting with maximal localization given by Dirac delta functions for which the criterion ( corresponds to a conditional guarantee. In between the two extremes lie function sets W with an intermediate level of localization yielding localized guarantees.
Figure 2:
1.2 Conditional and Localized Risk
The convergence guarantee 7 for ARC is marginalized over the covariate X. Therefore, there guarantee that the conditional miscoverage Pr Pr CT|X æ| is smaller than the target o. This problem is particularly relevant for high-stakes applications in which it is important to ensure homogeneous level of reliability across different regions of the input space, such as across subpopulations. That said, even when the set predictor C(( (eal) is obtained based on an offline calibration data set Deal with i.i.d. data (X,Y) Pxy, it is generally impossible to control the conditional miscoverage probability as
Pr [Y & C(X)Pea) = x] S a for all E
(8)
without making further assumptions about the distribution Pxy or producing uninformative prediction sets [Vovk] 2012 Foygel Barber et al. 202T].
A relaxed marginal-to-condiiioon condiiitiln guarantee considered by Gibbs et al. 2023 which relaxed
the marginal miscoverage requirement 8 as
1(Y & C(X(Dea)) I a for all w(+) e W, Ex[w(X)]
w (X)
Ex,YD
(9)
where W a of non-negative reweighting functions, and the expectation is taken over the joint distribution of the calibration data Deal and the test pair (X,Y). Y). Note that with a singleton set W encompassing a single constant function, e.g., w(x) 1, the criterion coverage. Furthermore, as illustrated in Figure 2 depending on the degree of localization of the functions set W, the criterion D interpolates between marginal and conditional guarantees.
reduces marginal
At the one extreme, a marginal guarantee like 7 is recovered when the reweighting functions constant. Conversely, at the other extreme, conditional guarantees as in
(8) emerge when the reweighting functions are maximally localized, i.c., when W = {w(xx) = 6(x p)) X'), where ((x) denotes the Dirac delta function. In between these two extremes, one obtains an intermediate degree of localization. For example, this can be done by considering reweighting functions such as
kexp (- || - 11ll2 + +1):
W w(xx==
Σ
Bi
Ex Ex(w((X) > 0, and w(()) 2 0 Vo E X
(10)
where 2 0 is a fixed length scale, & 2 0 is a fixed scaling parameter, and ||:|| denotes the Euclidean norm. Furthermore, function w(x) may also depend on the output of the pre-trained model, supporting calibration requirements via constraints the form ( [hhng et al. 2024].
In Gibbs et al. 2023 the authors demonstrated that it is possible to design offline set predictors C C(X)Daa) that approximately control risk (9), with an approximation gap that depends on the degree of localization of the family W of weighting functions.
3

---

1.3 Localized Risk Control
Motivated by the importance conditional risk guarantees, we propose Localized ARC (L-ARC), novel online calibration algorithm that produces prediction sets with localized statistical risk control guarantees as in (9. while also retaining the worst-case deterministic long-term guarantees (6) of ARC. Unlike Gibbs et al. [2023), our work focuses on online settings in which calibration is carried out sequentially based on feedback received on past decisions.
The key technical innovation of L-ARC lies in the way set predictions are constructed. As detailed in Section 2 L-ARC prediction sets replace the single threshold in (I with threshold function g(-) mapping covariate X to a localized threshold value gXX). The threshold function is adapted in an online fashion within a reproducing kernel Hilbert space (RKHS) family & based on an input data stream and loss feedback. The choice of the RKHS family determines the family W of weighting functions in the statistical guarantee of the form 9 thus dictating the desired level of localization.
The main technical results, presented in Section are as follows.
In the case of i.i.d. sequences, (X,, Yt) Pxy for all / 2 L-ARC provides localized statistical risk guarantees where the reweighting class W corresponds to all non-negative functions E G with a positive mean under distribution Pxy. More precisely, given target loss value a, the time-averaged threshold function
1 Σ gc()), T
Ør()
(11)
ensures that for any function w E W, the limit
lim sup Exy
Ex[w(X)] C(C(X,
w(X)
- a A(G,w)
(12)
T
holds, where convergence is in probability with respect to the sequence {(2, Y2) and the average is over the test pair (X, Y). The gap AGG, w) depends on both the RKHS G and function w; it increases with the level of localization of the functions in the RKHS G; and it equals zero in the case of constant threshold functions, recovering for the special case of the miscoverage loss.
Furthermore, for an arbitrary sequence {(x,, 12) L-ARC has a cumulative loss that converges to neighborhood of the nominal reliability level as
T
B(g) CC()), VT
Σ L(C(X,, V2) - a
(13)
T
where BGG) and C(g) are terms that increase with the level of localization of the function in the RKHS G. The quantity C(G) equals zero in the case of constant threshold functions, recovering the guarantee (6) of ARC.
In Section we showease the superior conditional risk control properties of L-ARC as compared to ARC for the task of electricity demand forecasting, tumor segmentation, and beam selection in wireless networks.
2 Localized Adaptive Risk Control
2.1 Setting
Unlike the ARC prediction set (I L-ARC adopts prediction sets that are defined based on a threshold function 9t : X + R. Specifically, at each time t > 1 the L-ARC prediction set is obtained based on a non-conformity scoring function X' - IR as
C C(X,, 9t) == {y E y: s s(X,, v) S (X.))
(14)
By 14), the threshold ge is localized, i.e., it selected as function of the current input X In this paper, we consider threshold functions of the form
ge(-) f-(-) + Ce:
(15)

---

where O R is a constant and function ft(-) belongs to reproducing kernel Hilbert space (RKHS) H. associated kernel k(:,)) : X x X + R with inner product " and norm
the threshold function se(-) belongs to the RKHS G determined by the kernel k' k((:-) |1-11 2 Note that
+(++))++ +
We focus the online learning setting, in which at every time set & 2 1, the model observes input feature Xt, produces a set Cr, and receives as feedback the loss L, = L(C,, Yz). Note that label Y may not be directly observed, and only the loss [(C,, Y:) may be recorded. Based on the observed sequence of features X, and feedback Lr, we are interested in producing prediction sets as in (14) that satisfy the reliability guarantees (12) and (3)). with a reweighting function set W encompassing all non non-negative functions wx()) G with positive mean Ex [x( under distribution Px. i.e.,
W {w(-)) g Ex [x[=(X)] > O, and w(z) 0 for all X}.
(16)
Importantly, as detailed below, the level of localization in guarantee 12 depends on the choice of the kernel -.--)).
2.2 L-ARC
Given regularization parameter À O and learning rate The S 1/A,, L-ARC updates the threshold function gc(-) = f((-) + a in (14) based on the recursive formulas
c++1 = C (7 L2)
(17)
f241()) = (nn-)()) ne Le)k(Xx,)))
(18)
with f1(-) = 0 and C₁ = 0. In order to implement the update (17-118). it is useful to rewrite the
function gr+ 1 (-) as
(.+1()) Σ a ((,,,) + C1+1
(19)
where the coefficients
{a|+1 Di=1 are recursively defined as
a/_1 - Ls) d'_1 (1-11 A)a for 1,2,..,,
(20)
(21)
Accordingly, if the loss L. larger than the long-term target a, the update rule 20)- the function (-) around the current input X,, while decreasing it around the previous inputs X Intuitively, this change enhances the reliability for inputs in the neighborhood of X,.
21 increases
It is important to note that, at any time f, computing the threshold function 19 requires storing the coefficients {a;) and o, as well as the input data (X, Consequently. L-ARC has a linear memory requirement in which is a known limitation of non-parametric learning in online settings [Koppel et al. 22000). Previous research has explored methods that trade memory efficiency for accuracy Kiiiinen al. 2004]. In Appendix
C.3 we build on these approaches to present memory efficient variant of L-ARC that allows for a trade-off between localized risk control and memory requirements.
2.3 Theoretical Guarantees
In this section, we formalize the theoretical guarantees L-ARC, which were informally stated in Section 1.3 as 12) and (3).
Assumption (Stationary and bounded kernel). The kernel function is stationary, i.e., k(r, x') = k[[22 - ='Il), for some non-negative function k(-), which is p-Lipschitz for some p > 0, upper bounded by K < oc, and coercive, i.e., lim k(2) = O.
Many well-known stationary kernels, such the radial basis function (RBF), Cauchy, and triangular kernels, satisfy Assumption I The smoothness parameter p and the maximum value of the kernel function determine the localization of the threshold function ge(-) -)) G. For example, the set of functions W defined in (1O) corresponds to the function class (6)) associated with the RKHS defined
by the raised RBF kernel k(x,=')= k exp( ||x =/112/1) 1, with length scale I = 2e(k/ 2)² As illustrated in Figure 2 by increasing x and p. we obtain functions with an increasing level of localization, ranging from constant functions maximally localized functions.
5

---

Assumption 2 (Bounded non-conformity scores). The non-confornity scoring function is non- negative and bounded, i.e., s(z, y) I Smax 30 for any pair (x.y) E X x y.
Assumption 3 (Bounded and monotone loss). The loss function is non-negative; bounded, i.e. L(C,Y) < B < oo for any C' S y and Y E y; and monotonic, in the sense that for prediction sets C and C such that C' C C the inequality L(C,Y) L(C", Y) holds for any Y E Ey.
2.3.1 Statistical Localized Risk Control
To prove the localized statistical guarantee
12 we will make the following assumption.
Assumption 4 (Strictly decreasing loss). For any fixed threshold function g(.) E G. the loss By (C(C(X, 9), Y) X = is strictly decreasing in the threshold (xx) for any x E X.
Assumption 5 (Left-continuous loss). For any fixed threshold fanction g()) E 9, the loss L(C(x.9 h),y) v) is left-continuout in h E R. for any (I. v) E X x y.
Theorem 1. Fix a user-defined target reliability a. For any regularization parameter X >> 0 and any learning rate sequence Ttt mnt <1/>, for some in O, given a sequence {(X,, Y.)) of L... samples from Pxy, the time-averaged threshold function (17) satisfies the limit
w(X) Ex [x)) ((C(X,9T),)) Y2
~ kB
1l
lim sup Ex,y T-+00
(22)
Ex [w (X)
for any weighting function w() f.) + cw W where the expectation is with respect to the test sample (X,Y) Y).
Proof. See Appendix A
By 22). the average localized loss converges in probability a quantity that can be bounded by the target with gap A(G, w) that increases with the level of localization k.
2.3.2 Worst-Case Deterministic Long-Term Risk Control
Theorem Fix a user-defined target reliability a. For any regularization parameter > and any
learning rate sequence ')t m/t-1/2 < 1/A with n > O, given any sequence {(X,, Y:) [=)]]]] with bounded input ||X,l| s D < oo, L-ARC produces a sequence of threshold functions {g((-) in 19 that satisfy the inequality
T ((C(Xx..)),)))
1 VT
Smar
4B Mn
S
22B(xx xB.
(23)
Proof. We defer the proof to Appendix
B
Formalizing the upper bound in 13 Theorem 2 states that the difference between the long- -tem cumulative risk and the target reliability level decreases with rate B(G)T-1/2 to value C(g) =B that is increasing with the maximum value of the kernel k. the special case, н. which corresponds to no localization, the right-hand side of (23) vanishes in T, recovering ARC long-term guarantee (6)
3 Experiments
In this section, we explore the worst-case long-term and statistical localized risk control performance of L-ARC as compared to ARC. Firstly, we address the task of electricity demand forecasting, utilizing data from the Elec2 dataset [Harries al. [999]. Next, we present an experiment focusing on tumor segmentation. where the data comprises i.i.d. samples drawn from various image datasets [Jha et al.) 2020, [Bernal et al., 2015 2012 Silva et al. 2014 Vázquez et al., 2017]. Finally, we study a problem in the domain of communication engineering by focusing on beam selection, key task in wireless systems (Ali et al. 2017]. further example concerning applications with calibration constraints
can be found in Appendix C.2 Unless stated otherwise, we instantiate L-ARC with the RBF kernel

---

0.92
0.25
Longtenn Coeerigg
ARC
LARRCI -1.0
Margina
LARCC 7 -00
LARC!! 1 -0.5
Aperage Miseeeeang
0.20
Mar Fri
0.13
Sat Sun
0.90
0.05
0.83
10000
3.00
90000
4000
0.00
Timeslep (0)
ARC
[=2
1-055
Figure 3: Long-term coverage (left) and average miscoverage (right), marginalized and con- ditioned on weekdays and weekends. for ARC and L-ARC with varying values of the localization parameter the Elec2 dataset.
06225
ABC
L-ABC [m1.))
Marginil CVC-450
CVC-ClmB8
Margiull CVC-360
CVC-CluD
0.4
0.4
ETB-Lazis
Logg-tm FSn
Axcrage ENR
003
0,0m0
0.2
6.00
.000
1.00
2003
Time Aup (1)
ATCC
2--2
1-11
2-05
400
2-22
2..55
Figure 4: Long-term FNR (left), average FNR across different data sources (center), and average mask size across different data sources (right) for ARC and L-ARC with varying values of the localization parameter for the task of tumor segmentation [Fan et al. 2020].
k(x,, x') -exp(-1|a-2) 2²112 /t) with x = 1, length scale = and regularization parameter = 10-4 With a smaller length scale I, we obtain increasingly localized weighting functions. All the experiments are conducted on a consumer grade Mac Mini with an MI chip. The simulation code available at httttt:: httpthub.coooocllp////aaiieaaeee wtwpoeaaaaeedddapiiieeeeeeeeeeee risk control.
3.1 Electricity Demand
The Elec2 dataset comprises T 45312 hourly recordings of electricity demands New South Wales, Australia. The data sequence (Y,)T=, is subject to distribution shifts due fluctuations in demand over time, such as between day and night or between weekdays and weekends. We adopt setup akin that of Anggelopoluss et al. [2024b), wherein the even-time data samples used for online calibration while odd-time data samples are used to evaluate coverage after calibration. At time f, the observed covariate X, corresponds the past time series Yi:-11, and the forecasted electricity demand Y, is obtained based on moving average computed from demand data collected within the preceding 24 to 48 hours. We produce prediction sets C, based on the non-conformity score sXx,, Y2) Y Y,l and we target a miscoverage rate 0.1 using the miscoverage loss Both ARC and L-ARC use the learning rate L 1-1/2, L-ARC is instantiated with the RBF kernel k(x, _x) exp(- []ő(z) 6(x')l /t), where of is 7-dimensional feature vector corresponding to the daily average electricity demand during the past 7 days.
In the left panel of Figure 3 we report the cumulative miscoverage enror of ARC and L-ARC for different values of the localization parameter 1. All algorithms converge the desired coverage level of 0.9 in the long-term. The right panel of Figure 3 displays the average miscoverage error on the hold-out dataset at convergence. We specifically evaluate both the marginalized miscoverage rate and the conditional miscoverage rate separately over weekdays and weekends. L-ARC is shown to reduce the weekend coverage error rate as compared to ARC providing balanced coverage as the length scale I decreases.
7

---

3.2 Tumor Image Segmentation
In this section, we focus on the task calibrating a predictive model for tumor segmentation. Here, the feature vector X, represents du x dw image, while the label Y, S P identifies subset of the image pixels p- = {(1, 1)............... (du, dw)} that encompasses the tumor region. As in Angelopoulos et al. [2022] the dataset is compilation of samples from several open-source online repositories: Kvasir, CVC-300, CVC-ColonDB. CVC-ClinieDB, and ETIS-LaribDB. We reserve 50 samples from each repository for testing the performance post-calibration, while the remaining T = 2098 samples are used for online calibration. Predicted sets are obtained by applying a threshold g g(X;)) to the pixel-wise logits fPH, Pw) generated by the PraNet segmentation model [Fan et al. 2020 with the objective of controlling the false negative ratio (FNR) L(C,, Y2) = 1- CyTT/ Both ARC and L-ARC are run using the same decaying learning rate 7) = 0.1f 1/2 L-ARC is instantiated with the RBF kernel b(z,z') = A exp( ( [z)((=) - (xx')l )12 /l), where Φ(x) is a 5-dimensional feature vector obtained via the principal component analysis (PCA) from the last hidden layer of the ResNet model used in PraNet.
In the leftmost panel of Figure 4 report the long-term FNR for varying values of the localization parameter I, targeting an FNR level a = 0.1. All methods converge rapidly to the desired FNR level, ensuring long- tergttemmmt risk control. The calibrated models are then tested on the hold-out data, and the FNR and average predicted set size are separately evaluated across different repositories. In the middle and right panels of Figure 4 report the average FNR and average prediction set size averaged over 10 trials.
The model calibrated via ARC has marginalized FNR error larger than the target value Moreover, the FNR error is unevenly distributed across the different data repositories, ranging from FNR = 0.08 for CVC-300 to FNR- 0.32 for CTIS-LaribPolypDDD In contrast, L-ARC can equalize performance across repositories, while also achieving a test FNR closer to the target level. In particular, as illustrated in the rightmost panel. L-ARC improves the FNR for the most challenging subpopulation in the data by increasing the associated prediction set size, while maintaining a similar size for subpopulations that already have satisfactory performance.
3.3 Beam Selection
Lasgleus ttbk
8.000
AIEO
Micdrian ARC
LARe
ARC
50:1
30091
15/60)
20001
Tiee step
Jog. Bon
1.
Tramuiler
Transsit ber
LE7)
Figure 5: Long-term risk (left-top), average beam set size (left-bottom), and SNR level across the deployment area (right) for ARC, Mondrian ARC, and L-ARC. The transmitter is denoted as a green circle and obstacles to propagation are shown as grey rectangles.
Motivated by the importance of reliable uncertainty quantification in engineering applications, address the task of selecting location -epation-ppecffic beams for the initial access procedure in sixth-generate wireless networks [Ali et al. 2017]. Further details regarding the engineering aspects of the problem and the simulation scenario are provided in Appendix C.I.II In the beam selection task, at each time t. the observed covariate corresponds to the location X, [Px. of receiver within the network deployment, where P> and Py represent the geographical coordinates. Based on the observed covariate, the transmitter chooses set, denoted C. [1.... B, consisting of subset of the Buax available communication beams.
Each communication beam i is associated with wireless link characterized by signal-to-noie ratio Yr,, which follows an unknown distribution depending on the user's location X,. We represent the vector of signal-to-noise ratios as Y, = [V,,,.... Yr,ana E Bue, For set Cr, the transmitter sweeps over the beam set Ct, and the performance is measured by the ratio between the SNR obtained
8

---

on the best beam in set C₁ and the best SNR on all the beams, i.e.,
maxiec, Y1,
C(C,, Yi) I, = (I..., Y1,5
(24)
Given an SNR predictor P; = foNR((sss (Xt) for all beams at location X,, we consider sets that include only beams with predicted SNR exceeding threshold gr (Xx)
g(x,, = {i E [l,..., Buax] Y2, > (X,))
(25)
In this setting, localization refers to the fair provision of service across the entire deployment area. As benchmark, we thus also consider an additional calibration strategy that divides the deployment area into two regions: one encompassing all locations near the transmitter, which are more likely to experience high SNR levels, and the other including locations far from the transmitter. For each of these regions, we run two separate instances of ARC algorithmss Inspired by the method introduced in Boström et al.
2021 for offline settings, we refer to this baseline approach Mondrian ARC.
In the left panels of Figure 5 we compare the performance of ARC, Mondrian ARC, and L-ARC with an RBF kernel with = 10, using calibration data sequence of length T = 25000. All methods achieve the target long-term SNR regret, but L-ARC achieves this result while selecting sets with smaller sizes, thus requiring less time for beam sweeping. Additionally, as illustrated on the right panel, thanks to the localization of the threshold function, L-ARC ensures a satisfactory communication SNR level across the entire deployment area. In contrast, both ARC and Mondrian ARC produce beam-sweep sets with uneven guarantees over the network deployment area.
4 Related Work
Our work contributes to the field of adaptive conformal prediction (CP), originally introduced by Gibbs and Candes [002]]. Adaptive CP extends traditional CP (Vovk et al. 2005 to online
settings, where data is non-exchangeable and may be affected by distribution shifts. This extension
has found applications in reliable time-series forecasting [Xu and Xie 2021 Zaltran et al. 2022).
control [Lekeufack al., 2023 Angelopoulos al.) 2024a], and optimization [Zhang al. 2023
Deshpande et al. [2024]. Adaptive CP ensures that prediction sets generated by the algorithm contain the response variable with user-defined coverage level on average across the entire time horizon. [Bhatnagar Recennly.,Bhatnagar et al. [023] proposed a variant of adaptive CP based on strongly adaptive online learning, providing coverage guarantees for any subsequence of the data stream. While their approach offers localized guarantees in time, L-ARC provides localized guarantees in the covariate space. More similar to our work (Bastani al., 2022), which studies group-conditional coverage. Our work extends beyond coverage guarantees to more general risk definition, akin to Feldman et al. 2022 |Angelopoulos et al. [2024a] studied the asymptotic coverage properties of adaptive conformal predictions in the i.idd setting; and our work extends these results to encompass covariate shifts. Finally, the guarantee provided by L-ARC similar to that of Gibbs et al. [2023). albeit for an offline conformal prediction setting.
Conclusion and Limitations
We have presented and analyzed L-ARC,, a variant of adaptive risk control that produces prediction sets based on threshold function mapping covariate information to localized threshold values. L-ARC can guarantee both worst-case deterministic long-term risk control and statistical localized risk control. Empirical analysis demonstrates L-ARC's ability effectively control risk for different tasks while providing prediction sets that exhibit consistent performance across various data sub- populations. The effectiveness of L-ARC is contingent upon selecting an appropriate kernel function. Furthermore, L-ARC has memory requirements that grow with time due to the need to store the input data {X and coefficients 2 These limitations of L-ARC motivate future work aimed at optimizing online the kernel function based on hold-out data Kiyani et al. 2024 or in an online manner [Angelopoulos et al.] 2024a] and at studying the statistical guarantees of memory-efficient
variants of L-ARC Kivinen al. 2004

---

6 Acknowledgments
This work was supported by the European Union's Horizon Europe project CENTRIC (101096379). The work of Osvaldo Simeone was also supported by the Open Fellowships of the EPSRC (EP/W024101/) by the EPSRC project (EP/X011852/1) and by Project REASON, UK Gov- emmment funded project under the Future Open Networks Research Challenge (FONRC) sponsored by the Department of Science Innovation and Technology (DSIT). We would also like to express our gratitude to Anastasios Angelopoulos for valuable insights on the technical content of the paper.
References
Anum Ali, Nuria Prnzcie and Robert W Heath. Millimeter wave beam-selection using out- of-band spatial information. IEEE Transactions on Wireless Communications, 17(2):103--106 2017.
Anastasios Angelopoulos, Emmanuel Candes, and Ryan J Tibshirani. Conformal PID control for time series prediction. Advances in Neural Information Processing Systems, 36, 2024a.
Anastasios N Angelopoulos, Stephen Bates, Adam Fisch, Lihua Lei, and Tal Schuster. Conformal risk control. arXiv preprint arXiv:2008.02811, 2022.
Anastasios N Angelopoulos, Rina Foygel Barber, and Stephen Bates. Online conformal prediction with decaying step sizes. arXiv preprint arXivv2402.01 2024b.
Osbert Bastani, Varun Gupta, Christopher Jung, Georgy Noarov, Ramya Ramalingam, and Aaron Roth. Practical adversarial multivalid conformal prediction. Advances in Neural Information Processing Systems, 15:29362-293777 2022.
Jorge Bernal, Javier Sánchez, and Fernando Vilarino. Towards automatic polyp detection with polyp appearance model. Pattern Recognition, (5(9)331663318) 2012.
Jorge Bernal, F Javier Sánchez, Gloria Esmaandez--sparrrch, Debora Gil, Cristina Rodríguez, and Fernando Vilariño. WM-DOVA maps for accurate polyp highlighting in colonoscopy: Validation saliency maps from physicians. Computerized medical imaging and graphics, 43:99-111, 2015.
Aadyot Bhatnagar, Huan Wang, Caiming Xiong, and Yu Bai. Improved online conformal prediction via strongly adaptive online learning. In International Conference Machine Learning, pages 2337-2363. PMLR, 2023.
Henrik Boström, Ulf Johansson, and Tuwe Löfström. Mondrian conformal predictive distributions. In Conformal and Probabilistic Prediction and Applications, pages 24-38, PMLR, 2021.
Nicolo Cesa-Bianchi, Alex Conconi, and Claudio Gentile. On the generalization ability of on-line learning algorithms. IEEE Transactions on Information Theory, 2059022050 2004.
Shachi Deshpande, Charles Marx, and Volodymyr Kuleshov. Online calibrated and conformal prediction improves bayesian optimization. In International Conference Artificial Intelligence and Statistics, pages 1450-1458. PMLR, 2024.
Deng-Ping Fan, Ge-Peng Ji, Tao Zhou, Geng Chen, Huazhu Fu, Jianbing Shen, and Ling Shao. Pranet: Parallel reverse attention network for polyp segmentation. International conference on medical image computing and computer-assise intervention, pages 263-273. Springer, 2020.
Shai Feldman, Liran Ringel. Stephen Bates, and Yaniv Romano. Achieving risk control in online learning settings. arXiv preprint wrXxi22205000093 2022.
Rina Foygel Barber, Emmanuel J Candes, Aaditya Ramdas, and Ryan J Tibshirani. The limits of distribution- conditional predictive inference. Information and Inference: A Journal of the IMA, 10(2):455-49) 2021.
Isaac Gibbs and Emmanuel Candes. Adaptive conformal inference under distribution shift, Advances in Neural Information Processing Systems, 34:1660-1672, 2021.
10

---

Isaac Gibbs, John J Cherian, and Emmanuel J Candès. Conformal prediction with conditional guarantees. arXiv preprint arXiv:2305.12611: 2023.
Andrea Goldsmith, Wireless communications. Cambridge university press, 2005.
Michael Harries, New South Wales, et al. Splice-2 comparative evaluation: Electricity pricing. 1999.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
Jakob Hoydis, Fayçal Ait Aoudia, Sebastian Cammerer, Merlin Nimier-David, Nikolaus Binder, Guillermo Marcus, and Alexander Keller. Sionna RT: Differentiable ray tracing for radio propaga- tion modeling. arXiv preprint arXiv:2303./1103, 2023.
Debesh Jha, Pia H Smedsrud, Michael A Riegler, Päl Halvorsen, Thomas De Lange, Dag Johansen, and Hävard D Johansen. Kvasir-seg: seg: A segmented polyp dataset. In MultiMedia Modeling: 26th International Conference, MMM 2020, Daejeon, South Korea, January 5-8, 2020, Proceedings, Part II 26, pages 451-462. Springer, 2020.
Jyrki Kivinen, Alexander J Smola, and Robert C Williamson. Online learning with kernels. IEEE transactions on signal processing, 52(8):2165-2) 2004.
Shayan Kiyani, George Pappas, and Hamed Hassani. Conformal prediction with learned features. arXiv preprint arXiv:2404. 17487, 2024.
Alec Koppel, Amrit Singh Bedi, Ketan Rajawat, and Brian M Sadler. Optimally compressed non- parametric online learning: Tradeoffs between memory and consistency. IEEE Signal Processing Magazine, 37(3):61-70, 2020.
Jordan Lekeufack, Anastasios A Angelopoulos, Andrea Bajesy, Michael I Jordan, and Jitendra Malik. Conformal decision theory: Safe autonomous decisions from imperfect predictions. arXiv preprint arXiv:2310.05921, 2023.
Horea Muresan and Mihai Oltean. Fruit recognition from images using deep learning. Acta Universi- tatis Sapientiae, Informatica, 10(1):26 42, 2018.
Juan Silva, Aymeric Histace, Olivier Romain, Xavier Dray, and Bertrand Granado. Toward embedded detection of polyps in wee images for early diagnosis of colorectal cancer. International journal of computer assisted radiology and surgery, 9:283-293, 2014.
David Vázquez, Jorge Bernal, F Javier Sánchez, Gloria Fernández Esprarach Antonio M López, Adriana Romero, Michal Drozdzal, and Aaron Courville. A benchmark for endoluminal scene segmentation of colonoscopy images. Journal of healthcare engineering. 2017, 2017.
Vladimir Vovk. Conditional validity of inductive conformal predictors. In Asian conference on machine learning, pages 475-490. PMLR, 2012.
Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithmic learning in random world, volume 29, Springer, 2005.
Wojeiech Wisniewski, David Lindsay, and Sian Lindsay. Application of conformal prediction interval estimations to market makers' net positions. In Conformal and probabilistic prediction and applications, pages 285-301. PMLR, 2020.
Chen Xu and Yao Xie. Conformal prediction interval for dynamic time-series. In International Conference Machine Learning, pages 11559-11569 PMLR, 2021.
Lequan Yu, Hao Chen, Qi Dou, Jing Qin, and Pheng Ann Heng. Integrating online and offline three-dimensional deep learning for automated polyp detection in colonoscopy videos. IEEE journal of biomedical and health informatics, 21(1):65-75, 2016.
Margaux Zaffran, Olivier Féron, Yannig Goude, Julie Josse, and Aymeric Dieuleveut. Adaptive conformal predictions for time series. In International Conference on Machine Learning, pages 25834-25866 PMLR, 2022.

---

Matteo Zecchin, Sangwoo Park, and Osvaldo Simeone. Forking uncertainties: Reliable prediction and model predictive control with sequence models via conformal risk control. IEEE Journal on Selected Areas in Information Theory, 2024.
Lujing Zhang, Aaron Roth, and Linjun Zhang. Fair risk control: A generalized framework for calibrating multi multi-group group fairness risks. arXiv preprint arXiv:2405.022 02225, 2024.
Yunchuan Zhang, Sangwoo Park, and Osvaldo Simeone. Bayesian optimization with formal safety guarantees via online conformal prediction. arXiv preprint arXiv: /7815, 2023.
12

---

A Proof of Theorem 1
We are interested in bounding the localized risk in (2 of the threshold function (TT for all weighting functions in set W defined in [16]. To study the limit 22) first note that L-ARC update rule (T8) corresponds to an online gradient descent step for a loss function E(g. x, y), with respect to function f()) and constant in function g(+) = f() as in (5). In particular, interpreting the update rule
(17 - 18 as gradient descent step, we obtain that the partial derivatives of the loss function {(g x, y)
evaluated g(-) ʃ()) +
V [و] dl(g. 2. v) (1 = (a ((C(x,))) V/()) E H.,
(26)
0f
Vellg) 0f(g. (a ((C((r,g).u)) ER,
(27)
de
so that the first order approximation of the loss E(g, x. y) around g(-) is given by
{gg + -0 ~ ((g. + c(a [(C( (K,, 55) + (ff
(28)
{(g x.,, ((g.2.)) + c(a (()().)).))))))))
(29)
In order to study the convexity the loss big æ, y) in g(.), we compute the the derivatives of 26 27 with respect to ((+) and c. The derivative of (66 with respect to is the operator A H H
satisfying
V eōi) - -V(((g)
Aōş = lim c0
L(C(I, 9).1)
lim
K2 + A5,
(C(CC(,))))) 9).) Ög(z)
0g(z) 0f .89 K2 2d5
OC(C(z,g),)) Og(x)
(K (220d))n. + 2ōg.
(30)
It follows that
(f, = aL(C(z, (),9) f(x)² + 111
(31)
Ög(z)
Similarly, the derivative of 26 with respect to is the operator B R + H is given by
(C(C(z,)).u) K.C, 0g(x)
Bc
(32)
which satisfies
aL(C(r,g): f(x)c. 0g(x)
(f. Bc)
(33)
The derivative of 27 with respect to c is given by
De ()(C(19)),)))
(34)
0g(x)
and the derivative with respect to to f is the operator C. H. R given by
C8, aC(C(z,g).)) (Kr, 0g(x)
(35)
so that
(c. Cf.Cf) aC(C(z,g).u) f(z)c. Ög(x)
(36)
13

---

From Assumption 4 the inequality ='= -By @C((C(z.g).)) 0g(2))
X = 2 7 0 holds. Thus, the
second-order term of the approximation of Tyy (e(g, X, X) X =x] around g(+) o 0 satisfies
A
B f D
Ey
If
c
x -By Br,,, + (f, + (f) Dc -
C
=I'((x} + 21' f(x)c I'e² + AlfI =I'((()) + c) - 11ll >0 We then conclude that the loss function By ((0. X, Y) = - is strongly convex in 9(-), and that the population loss minimizer
(37)
g -(=- arg min Ex,y [L x, Y)] sEG
(38)
is unique. For any covariate shift w(.) & W denote its components far(-) E H and Gw E R such that w()) (-) + Cu. From the first order optimality conditions, it holds that the directional derivatives with respect to (-) and Cu must satisfy
Ex,y [Vel(g" + cfu l-=o =Ex, 1(a -
+ A(Fw, f")nl = O,
(39)
Ex,y [Vllg" + eCw, X, o) Exx [(a [IC)((
(40)
which implies that for the optimal solution 9²())
w(X) Ex [xx] ((C((, = - Ex (wx()(())
fw
Exy
(41)
Equality (41)
amounts localized risk control guarantee for the threshold (-) for covariate shift
in wo(-) E W. The following lemma states that the time-average L-ARC threshold function (r(() defined in converges to the population risk minimizer g" (.).
Lemma 1. For any regularization parameter
and any learning rate sequence n = nit 1/2 1/A for some m > 0. given sequence {(G,, Y.) of i.dd. samples from Pxy, the tine-averaged
threshold function
77 satisfies for any >
lim Pr[llg" ØT 2()=0 =0 T T0
(42)
Proof. To prove convergence in probability, we need to show that the loss function E(g, X, Y) is bounded. To this end, first show that ((g, X,Y) Lipschitz in g(-) by studying the norm of the derivatives (26) (27). For g-(-) = fe(-) + returned by the update rule (18). the gradient with respect
fe()) satishies
Ol(g x, v)
(1)
= 11a -
+ Af(()lx
05
H
S &BV++A1AA011 S 2B
(43)
where the first inequality follows from the boundedness on the kernel (Assumption and the boundedness on the loss (Assumption 3) while the last follows from Proposition The gradient with respect to c can be similarly bounded as
Ölige, x. v) ()) I(aa= 91) s B.
(44)
dc
From the mean value theorem it follows that for g(.) = f(:) + c and f())=(()) +d
(k X,Y X,Y) (2BVk B) |l 11x
(45)
Since L-ARC returns functions fe(-) with bounded RKHS norm and infinity norm (Proposition)
and thresholds function (-)-) with bounded in infinity norm (Proposition 3). we conclude that there exists a finite Laa such that [eg X, Y)l Lmar- Given that the loss is bounded we apply
14

---

Kivinen et al. 2004 Theorem 4] and obtain that for the threshold (9((-) returned by L-ARC and the population loss minimizer g (-) holds
[g X,, 1)) T
1
1 T Σ
Egg Xt, Yi) + B2 + +12
(
2 VT
2m +
771 17
x2
A²T
(46)
By Hoeffding's inequality the empirical average the right-hand side of (46) converges to its expected value. Formally, we have that with probability at least - ô with respect to the sequence Y:)
1 T E llg' Xx. X)) -xxyx((((" . x,,Y)] S l Emaz
2 T
(
log
(47)
Similarly, by [Cesa- Baaa-Bianchi al. 2004 Theorem 2] the empirical risk on the left-hand side of (46)
converges to the population risk of the time-averaged solution (T1). With probability at least 1 with respect to the sequence of samples {(X,, Y)) it holds
Ex,y [K(rr, X, Y)] S Egg, X1, Yi) + l max
log
(48)
Combining the two inequalities, with probability at least 28 with respect to {X,, YO
Ex,y (((rr, E(g". (,,)) xB2 + +1²
2m +
+
VT
2m:
2 log
+ 2m
(49)
Since the Ex X, Y)] is strongly convex there exists a value 7 >> 0 such that the second order approximation of Ex, (g) X, Y)] at gtg"" g') satisfies
7 (1)5 Fr|1 (c' oT))² 2 s Ex,y X,Y) ((g' X,Y)
(50)
2
Combining (50) and (49). and leveraging |l S v |lfll which follows from the Assumption
we conclude that with probability
222 + 1)2
1
1
4l
2
1 (
llg" - 1er--rll loc S\
7
2mh
71 A2
+
21/1 X2T
+
7(x + 1) 1/ T
log
(51)
Choosing = 1. for any > holds Th
lim Prillg" T-x
Ir 2 2 0.
(52)
By itself, the convergence of the threshold function 9r(.) to the population risk minimizer g*(() is not sufficient to provide localized risk control guarantees for L-ARC time-averaged solution. However, under the additional loss regularity assumption in Assumption 5 we can show that set predictor C(X,9r) enjoys conditional risk control for T co.
Having assumed that the loss L(C(x, g). v) is left-continuous and decreasing for larger prediction sets (Assumption) 3 and 5) for any 8' there exists e such that for g(.) such that I|g" - gll S e holds
C (C Y) ())
(53)
For such g(-) the following inequality holds
w(X)
w(X)
max WEW
E
E
[[w(X)]
C (CC(X,))
< max E wEW
E E[w(X)]
C ((C(X,))) +8.
(54)
15

---

As stated in Lemma [ we can always find T' large enough, such that 1 - Trllx S E with arbitrary large probability. This implies, that for any 8' > 0 and W.
w(X) C (C (X,
w(X) E (X)
lim E T-000
E
L (C(X,9)))
+
(55)
E
fw
a A S"
+ 8
(56)
Ex Ex(1o(X7 (x)] llfulll +
S a + KB Ex [x((x(X)]
(57)
where the inequality (55) follows from 54 the inequality (56) follows from 41 and the inequality
57 from Proposition
B Proof of Theorem 2
We are interested bounding the absolute difference between the cumulative loss value incurred by the set predictors {C(g,, X,))²= produced by L-ARC (18)
and the target reliability level a, i.e.
T Σ 1=1
1
Yi) a)
(58)
T
Le
From Assumption and having assumed || S D for t 2 1, it follows that
=)),, 0. ||=||->>
lim
(59)
bound on the cumulative risk can then be obtained by bounding
T - (k
(60)
where for a function x + R. the infinity norm ||/ is defined maxzex [f()).. In fact, from (60) we directly obtain a bound on the cumulative risk
Σ (L - a²)
T
1 T
T
T
lim ||
T
E4 (L. - a))
T
Σ (L. - (()(())))))))))))))))))))))))))) +1)
(61)
To this end, we first note that functions {J+()))EN generated by 18 have bounded RKHS norm and are smooth.
Proposition For every & 2 1, we have the inequalities fe S B and |elll S xB
X
Proof. The proof is by induction, with the base case ())l S B/R// being satisfied as fi(-)
The induction step is given as
fl I = [1(1 An.) n.(a - Lo) lll
(62)
< [[1 An.)fell + 11me (,),
(63)
< (1 And) llfell + BVB
(64)
B X
(65)
where the equality 622 follows from the update rule 18): the inequality (63) from the properties of
the norm, the inequality (64) from Assumption T and 3 and the inequality (65) from the induction
hypothesis |lfall < BVK
A
Proposition 2. For t 2 and any (æ, x') E X x X we have
1f(x) f(x')1 s B
(66)
16

---

Proof. Denote the evaluation function at as K₂ = k(z,)), From Proposition 1 and the Lipschitz
continuity assumed Assumption
| it follows that
[f(z) - f(y)
Kf,, Ka)H (f, Ky)Hl
I(, K2 - Ky/Hl
|| Ill I|K Kyllæ
= IlllH v /k(az, xx) + k(y. - 2k(2, v)
S Illl 22p ||x0 - vl
2BypKD
(67)
where the first inequality follows from Bauchy-Schwarr inequality, the second from the Lipschitz continuity of the kernel, and the last one from Proposition together with ||=||| I D for E X. O
Leveraging the above characterization of the function fe(-) returned by L-ARC, we now show that the threshold function ge(-) has maximum and minimum values that are uniformly bounded.
Proposition 3. For every and X we have (xx) [Gmin: Gmax] with
2BV ppD
G Gmar Smax +
+ + B(xx
(68)
X
and
Gmin 2BypRL
111 B2x + 1).
(69)
Proof. We now prove the upper bound (68) The proof is by contradiction and it start by assuming
that there exists a and x E X such that ge (x) Gmax while g- < Gmax all L' From the update rule (18) we have that
0o- (x) = (x()) + - [ (
2 Gmax B(x + \nlf(-1(z)
G 771 B (2x +1)
(70)
From Proposition 2 we also have
9: 9x-1(X,-1) 2 (z) 2B PRd
Gmax B2xk 2B 2B
S Smaxy
(71)
where the last inequality follows from Guux being defined as (68 From Assumption 2 for all x E X,
-h- ( 2 Smax - a 2 L--1 = gx(x) S
1 (x) S Gmax,
(72)
which contradicts with the original assumption that there exists v such that g (x) 2 G Gmax.
The proof of the lower bound 69 follows similarly. Assume there exists t > and E X such that ge (xx S Gmin while (-) > Gmin for t' < From the update rule (18) we have that
0t-1(2) go gx(x) + 1--1(a (x),,,)), 1) (
< Gmin + m ([K + 1) (m)
Gmin + m (2x 1)
(73)
From Proposition 2 we also have
It- 9t-1(X,-1) < (x) 2B pBD
< Gmin + m/ B(xx 1) 2B
(74)
where the last inequality follows from Gmin being defined as 69 From Assumption 2 for all
X.
(X 5 L 2 (x) (1 Xm-1)9--122 2 G
(75)
which contradicts the assumption that there exists min (xx < Gmin-
17

---

Having established an upper and lower bound on the maximum value of the function (-) generated by 18 we can now bound (60). Define A
Th-1 and A = mn and note that
1 a)
S mmxx ZE
(L+ - (k)-a)((( +1)
T
Σ A
nel4, - (k) +
T
Σ 1=f
meL, - (k)((()) +1)
T
Σ fut + c++1 - (1 >x)) -
T
T
A
9T+1 + A
T
t=
Ar (gT+1 - -gr)
A
A
Σ
T
100
A T
119T+1
gr
felloo
(76)
T
The first term can be bounded based on Proposition as
E S T max |1 gell Σ
A.
Smax
4B DBDD
+ 2m 2m B(2
(77)
T
and similarly, for the second term, we have
RB
Fgg
X KB.
(78)
Fix decreasing learning rate = 1nt - and regularization parameter À = A then the E becomes
Smax
4B 2B(2k +1) T
E
1- +
(79)
m T
For any w 1, follows
T
lim T-
La a
= =BB
(80)
T
1=1
18

---

C Additional Experiments
C.1 Beam Selection
C.1.1 Simulation Details
60
40
-20
Transsiitter
50
50
Figure Network deployment assumed in the simulations. A single transmitter (green circle) communicates with receivers that are uniformly distributed in a scene containing multiple buildings (grey rectangles).
For the beam selection experiment, we consider the network deployment depicted in Figure 6 in which a transmitter (green circle) communicates with users in an urban environment with multiple buildings (grey rectangles). We assume that communication occurs at a frequency fo = 2.14 GHz and that the transmitter is equipped with N, 8 transmitting antennas while receiving users have single- antenna equipment. The transmitter adopts a discrete Fourier transform beamforming codebook of size Bmax 11, with each beam b, given by
1 VN.
[1, e Bmax
(N.
C., for i {O..... Bmax 1}.
(81)
where j = III. The wireless channel response n NN between the transmitter and receiver located at X, [Px: IR,, is modeled using Sionna ray-tracer [Hoydis et al. [2023), and we account for small scale fading using a Rayleigh noise model [Goldsmith 20055. The resulting channel vector is distributed as
h h (X()) + Rayleigh(o).
(82)
where 1 (X,) the ray tracer output and (ayleigh(()) a Rayleigh distributed random variable with parameter 10-1, Assuming unit power transmit symbols and receiver noise, for a channel vector it the communication signal-to-noiss ratio (SNR) obtained using the beamformer b; given by
Yr, = 1 by.
(83)
Beam sets obtained calibrating an SNR predictor Y, fSNR(Xs realized using 3-layer fully connected neural network that is trained on 2500 samples with the user location generated uniformly random within the deployment area.
C.1.2 Effect of the Length Scale
In Figure 7 we study the effect of the length scale of the kernel function on the time-averaged threshold function Tr (X) returned by L-ARC. We report the value of the L-ARC time-averaged
threshold, Ør (X). in (11), for the same experimental set-up as in Section 3.3 and for increasing localization of kernel function. As the length scale parameter | decreases, corresponding to more localized kernel, the value of the threshold is allowed to vary more across the deployment area. In particular, the threshold function reduces its value around areas where beam selection problem becomes more challenging, such building clusters, in order to create larger beam selection sets.
19

---

T-ARCI
L-ARCI 25
L-ARC/ 10
-10
4
0
-20
Transmister
I' Dransmitter
Transmitter
-50
-25
26
50
-00
-25
25
-50
-2h
25
500
Figure 7: Time-averaged threshold function Ør for different values of localization parameter l.
1.0
Loug Choorage
3.7
ARC zalf
I-A REC Ju
LARC
ARR!
Doverge
0.6
Set Stee
L-ARC Iw0:25
0.74
6.4
L-ABU Imi
2w0.25
0.72
4000
5000
0.0
0.5
0.2
Contidene (CooltX1)
Model's Coolidance (Uoa
Figure 8: Long-term coverage (left), coverage rate (center), and prediction set size (right) versus model's confidence for ARC and L-ARC for different values of the localization parameter l.
C.2 Image Classification with Calibration Requirements
In this section, consider image classification task under calibration requirements based on the fruit-360 dataset [Muresan and Oltean 2018). For this problem, the feature vector X₃ an image of size 100 100, and the corresponding label Y, E y = (1, 130) is one of 130 types of fruit, vegetable, or nut in image X₃- We study the online calibration of a pre-trained ResNet18 model [He al. [016). For an input image X,, the prediction set obtained from the model's predictive distribution p(y) X,) as
C(X,, = fy E V ply)x,) > (X.)),
(84)
and we target the miscoverage loss 3 with target miscoverage rate 0.25. In order to capture calibration requirements, we impose coverage constraints that are localized in the model's confidence. The model's 's confidence indicator is given by the maximum value of the model's 's predictive distribution p(yl X.), i.e.
Conf(XX) = max p(y Xc). Xt).
(85)
vEy
Accordingly, we rum ARC and L-ARC calibration with a sequence of T 8000 samples and instantiate L-ARC using the exponential kernel k(2,, x²) = x eex(( [(o(x) - 6(x')l 12 /t), where the feature vector is given by the model's uncertainty, i.c., ((z) Conf(x).
In the left-most panel of Figure we report the long-term coverage of ARC and L-ARC for an increasing level of localization obtained by decreasing the length scale I. All methods guarantee long-term coverage. the middle panel, we use hold-out data to evaluate the coverage of the calibrated model conditioned on the model's confidence level. For small length scale I, L-ARC yields prediction sets that satisfy the coverage requirement across different levels of the model's confidence. In contrast, ARC, due to its inability to adapt the threshold function, has large miscoverage rate for small model confidence levels. As illustrated in the right panel, this achieved by producing larger set size when the model's confidence is low.
20

---

Mariiall
ClaakDD
0.1
CVVC 200
ETIS Larl-LailP
Antuge PSHI Senor
Decrewrogg mennay Warbet
0.3
AICC
Maac--001
Masc-1008
Mens-1900
L-ARC
L-ANC with momorry buiger Mase
Figure 9: FNR obtained by ARC, L-ARC, and L-ARC with limited memory budget Miax {500, 1000, 1500]. As the memory budget increases, the localized risk control performance of L-ARC interpolates between ARC and L-ARC.
Decrensing memory budget
LARRC Mew =500
LACC Mas 1000
LARC
40
-0
3: 30
-20
Transm Rtne
Tratsmiltier
45
-00
Figure 10: SNR across the deployment attained by L-ARC with limited memory budget M
C.3 On the memory efficiency of L-ARC
In manner similar to (Kivinen et al. 2004 it is possible obtain memory-efficient version of L-ARC that adopts truncated version of L-ARC threshold (19) given by
(++1(-)
Σ a c++1-
(86)
i=max(1,t-Mm..
Unlike the threshold (19). which has linear memory requirement, the truncated version 86 requires a constant memory and computational load that are proportional the number coefficients Mm It is known that in online non-parametric learning, there exists trade-off between memory efficiency and performance. the following, we empirically study the trade-off between the localized risk control of L-ARC and its memory requirements by varying the parameteR Mmax.
C.3.1 Tumor Segmentation
Using the setup described in Section 3.2 we now consider calibrating the image segmentation model using L-ARC with truncated threshold (86). In Figure 9 we report the average FNR conditioned on different data sources for Mmux E (500, TO00, 1500). As benchmark, we also compare against ARC and L-ARC without truncation. By adjusting the value of Mmax. it is possible to trade off localized risk control for memory efficiency. is minimal when the number of coefficients in the truncation is large (A = 1500). However, for greater memory savings (Amax = 500), L-ARC's performance becomes similar to that of ARC. In all cases, L-ARC provides better localized risk control than ARC.
fact, the effect of truncation on L-ARC"s performance
C.3.2 Beam Selection
We consider the beam selection problem discussed in Section 3.3 In Figure 10 we report the SNR levels across the deployment attained by ARC, L-ARC, and L-ARC with truncated threshold with a maximum number of coefficients Mmax E {500, 1000). As the number of coefficients Mnax and the memory requirement reduce, the localized risk control performance of L-ARC also decreases. Nonetheless, even for small Mm L-ARC delivers more consistent SNR level across the deployment compared to ARC.
21

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The theoretical claims about the proposed calibration algorithm are supported by Theorem [ and Theorem 2 while experimental results in Section [ demonstrate its
capability to control long-term risk and to improve fairness across data subpopulations.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: In Section we highlight primary limitations of L-ARC: its memory requirements and the necessity of specifying a suitable kernel. Additionally, we suggest potential directions for future research address these issues. A memory-efficient version of L-ARC is given in the Appendix.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
22

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Both theorems are preceded by a necessary set of assumptions. In the proofs, provided the appendix, we reference these assumptions when using them.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in the appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: In the main text, we provide details of all the experiments, including factors influencing the proposed solution, such as datasets and algorithm parameters like the choice of kernel, localization parameters, and learning rate.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibilityy can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the partieular way they provide for reproducibiliity In the case of closed-source models, it may be that access to the model is limited in
23

---

reproducible, they some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: In the supplementary material, we include the source code of the experiments along with a concise guide containing all the necessary information to replicate the results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https::/niis.cc.
Sttpi///giides//odeSubbee oow.esuubbissiioooooooooooo for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https for more details.
7 //nips. //nips.cc/publee cwtpppblcc/guudee.a.oo.plpep /ewedddddd//oddmmmmeccc
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All the information, such as the type of datasets, the learning rate, the type of kernel function, and localization parameters, is reported in the main text. In the appendix, we provide additional details about the data generation for the beam selection experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Where possible we report 95% confidence intervals in the form of error bars or shaded areas.
Guidelines:
The answer NA means that the paper does not include experiments.

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We indicate that the experiments are rum on a Mac Mini
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics httpp//////eeapppp.cccccpccc/c//
Answer: [Yes]
Justification:
We carefully read and comply with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper provides a new calibration scheme that offers long-term risk control and statistical localized risk guarantees. We do not see any negative societal impacts associated with the proposed algorithm.
25

---

Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This work does not pose such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All datasets and models used in the experiments are properly credited by citing the corresponding papers.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
26

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the datasets.paperssiii paperswi thcode. www.coo//aaaaa datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
We do not use crowdsourcing or human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
We do use crowdsourcing or human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
27

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
28


Reviews:
[{"review_id": "8g0GYSKPq4", "reviewer": "Reviewer_LXXA", "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.\n\nThe 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&#232;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&#232;s, 2021; Feldman et al., 2022] at achieving the desired level of miscoverage error across distinct subpopulations.", "questions": "1. What are the main technical innovations in the proofs of the main results?\n2. What parts of the analysis draw on previous work?\n3. How reasonable are the assumptions presented in Sec. 2.3 and when do they hold (especially Assumptions 4 and 5)?\n4. What is significance of the weighting inside the expectation on the LHS of eq. (22) and why is this relaxed, reweighted expectation meaningful?\n5. 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?\n6. The present paper uses the term Adaptive Risk Control (ARC) to refer to the methods proposed in [Gibbs and Cand&#232;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?", "limitations": "Aside from the issues raised above, the limitations have been adequately addressed.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "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:\n1. 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.\n2. 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. \n3. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful comments. Below, we address each comment point by point:\n- 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.\n- 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.\n- 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.\n- 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.\n- 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1gLf0OaW9E", "reviewer": "Reviewer_tGoZ", "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.", "questions": "Please check the weaknesses.", "limitations": "N/A", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The paper is easy to read. It could have been better structured, but it is okay. \n\n- 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. \n\n- Is the pre-trained model trained on all the data sources that will be used during the calibration process if they are different? \n\n- 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? \n\n- What is the crucial reason for using the RKHS function instead of a scalar? How is this useful? \n\n- 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?\n\n- 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. \n\n- What is the reason to consider the functional form in (15)\n\n- How are the updates in (17)-(21) derived?  Equation (19) is fine, which is the standard representation of a function in RKHS\n\n- 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. \n\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewers for their insightful comments. Below, we address each comment point by point:\n- 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.\n- 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.\n- 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.\n- 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.\n- 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.\n- 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.\n- 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.\n- 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.\n- See the previous point and the attached pdf for a solution to this problem that has **constant**, not linear, memory requirements.\n- 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YDiM9uIkB0", "reviewer": "Reviewer_ydRn", "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.", "questions": "Refer to Weaknesses.", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "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.\n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful comments. Below, we address each comment point by point:\n- 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.\n- 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DxjEhaJM39", "reviewer": "Reviewer_nFrT", "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.", "questions": "Related to Theorems 1 and 2, could the author comment on their value of the upper bound of the localized loss?\n\nL-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).", "limitations": "The limitation of L-ARC is stated in Section 5, saying that it requires a memory function of storing the input data.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful comments. Below, we address each comment point by point:\n- 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.\n- 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "c6WMGlSab1", "reviewer": "Reviewer_gQ5F", "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.", "questions": "See above", "limitations": "NA", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is very well written. The illustration figures are very helpful in explaining the localization effects of difference choices of $w(x)$.\n\nThe problem is also well motivated: the worst case risk guarantee is indeed very important in applications such as medical imaging.\n\nThe 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.\n\n2. 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? \n\nIn 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful comments. Below, we address each comment point by point:\n- 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.\n- 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].\n- 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their insightful comments. Multiple reviewers raised concerns about the linear memory requirement of L-ARC. In the original submission, we acknowledged this limitation and planned to leave the derivation and analysis of memory-efficient variants for future work. Nonetheless, in response to these comments, we have decided to include a PDF document that presents a variant of L-ARC with **constant memory requirements**  and provides empirical results demonstrating how this scheme balances memory efficiency with localized risk control. We hope this addresses the reviewers’ concerns and plan to include these new results as part of the supplementary material.

Meta-review: The paper develops a Localized Adaptive Risk Control (L-ARC) scheme for learning an online conformal predictor.  Here a reproducing kernel Hilbert space (RKHS) is used to learn (via stochastic gradient descent) a function for an adaptive threshold, enhancing baseline fixed-threshold ARC.  The threshold is used to determine the prediction set. 

The RKHS kernel choice enables reliable conformal prediction on data with distinct subpopulations, an open problem prior to this paper and important in some applications.  The reviewers noted that this is an interesting and original insight that is likely to draw attention in the conformal prediction community and is a major strength of the paper.  

The authors show theoretically that the stationary point of their learning algorithm satisfies the localized risk guarantee, and connections are made with kernel learning theory. It seems likely that the use of a functional form for the threshold with applicability to online use will lead to further interest in the community as the adaptive risk control methods are further studied and developed.

The reviewers also emphasized that the experimental results provide strong evidence and validate the utility of the localization effect of the choice of kernel. The experiments in different applications show improvement in comparison to online risk control method benchmarks.  The paper emphasizes the improvement over fixed threshold ARC algorithms. (It may be true that other ML methods will be superior in any given application.)

Any online method may have tradeoffs. Online kernel methods have linearly growing memory requirements unless some (typically ad hoc) method is used to control the memory. In rebuttal the authors have acknowledged the issue and shown such a method on a simulation example.  The reviewers have noted that the analysis in the paper is useful and provides insight, while also emphasizing the importance of the theoretical characterization of tradeoffs due to finite memory requirements in their RKHS based approach (reserved for future work).  

The reviewers have emphasized that the insights regarding the connection between kernel choice and localization effect provided by the existing analysis are of primary interest. The truncated version of the algorithm and associated experiments furnished during the discussion phase also help mitigate the memory issue.  Perhaps of interest to the authors are theories that consider balancing the memory use (the model size) and performance, e.g., Koppel, IEEE SP Magazine May 2020.

Reviewers have also emphasized that the presentation of the paper would benefit from additional discussion of context as well as improved motivation and interpretation of the technical results, and recommend these issues be addressed in the final version.
Decision: Accept (poster)