summaries: This paper studies the problem of multi-armed bandits under the shuffled model of DP. The authors provide two algorithms, one of which almost matches the regret of the best known algorithms for the centralized model. To do so, they give a variant of the arm elimination algorithm that leverages the private summation algorithm by Cheu et al. [9] and uses exponentially growing batches.

summaries: The paper proposes a shuffle model of DP for multi-armed bandits. The paper proposes two algorithms, SDP-AE and VB-SDP-AE, for bandits with shuffle DP and Bernoulli rewards. Distribution-dependent and independent regret bounds are derived for both the algorithms. VB-SDP-AE achieves additive regret due to privacy which has same order of dependence on $\epsilon$ but logarithmically worse dependence on $T$ than centralised DP.

summaries: This paper studies the multi-armed bandit problem under the constraint of approximate differential privacy. Previously, multi-armed bandits have been studied in other models of privacy such as the centralized pure DP model, the centralized approximate DP model, and the local pure DP model. However, this is the first work to consider the multi-armed bandit problem under the shuffle model of privacy.  To be clear, the model that the authors consider is as follows. At each round $t$, a batch of $m$ random users are selected. An action (e.g. an ad) is then selected for each user. The reward for each user is then presented to a shuffle DP mechanism.  In terms of results, the authors prove a regret bound which is slightly weaker than the result one can obtain in the central DP model but significantly stronger than the result one can obtain the local DP model. In particular, it removes a multiplicative $1/\epsilon^2$ dependence that appears in the regret bound for the local DP model.  In terms of techniques, the authors combine some ideas from the bandit literature and the differential privacy literature. In particular, their algorithms are based on the non-private arm elimination algorithm and they show how one can use private binary summation from the shuffle DP literature to obtain a shuffle DP algorithm for MAB. The authors also give two differential algorithms. The first algorithm uses static batch sizes in each round. The second algorithm uses dynamic batch sizes and they show that this improves the regret.

summaries: This paper adapts the shuffle model of differential privacy to the multi-armed bandit setting, and aims to design a bandit algorithm which has privacy guarantees similar to that in the local model, while simultaneously having regret guarantees similar to the central DP model. The authors propose two arm-elimination style algorithms, which uses a private binary summation mechanism with optimal error guarantees as a subroutine, in order to obtain improved regret guarantees over the local model. In particular, they show how a simple, constant batch size policy already gets rid of the multiplicative dependence on $1/\epsilon^2$. Then, they show how to adapt this policy to exponentially increasing batch sizes, improving the additive dependence from $\approx k/\epsilon^2$ to $\approx k/\epsilon$.

summaries: The paper studies the classic multi-armed bandit problem in the shuffled model of differential privacy. Paper's first contribution is the definition of shuffled differential privacy (SDP) in the multi-armed bandit setting.  The paper's main contribution is an SDP algorithm with the same regret guarantees as the best-known multi-armed bandit algorithm in the central privacy model.

abstractText: We give an (ε, δ)-differentially private algorithm for the multi-armed bandit (MAB) problem in the shuffle model with a distribution-dependent regret of O ((∑ a∈[k]:∆a>0 log T ∆a ) + k √ log 1 δ log T ε ) , and a distribution-independent regret of O (√ kT log T + k √ log 1 δ log T ε ) , where T is the number of rounds, ∆a is the suboptimality gap of the arm a, and k is the total number of arms. Our upper bound almost matches the regret of the best known algorithms for the centralized model, and significantly outperforms the best known algorithm in the local model.

authors:
B. Balle
J. Bell
A. Gascon
K. Nissim

title: Differentially private summation with multimessage shuffling

venue: arXiv preprint arXiv:1906.09116

authors:
B. Balle
J. Bell
A. Gascón
K. Nissim

title: The privacy blanket of the shuffle model

venue: Annual International Cryptology Conference, pages 638–667. Springer

title: Private summation in the multi-message shuffle model

venue: Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pages 657–676

authors:
A. Beimel
I. Haitner
K. Nissim
U. Stemmer

title: On the round complexity of the shuffle model

venue: Theory of Cryptography Conference, pages 683–712. Springer

authors:
A. Beimel
K. Nissim
E. Omri

title: Distributed private data analysis: Simultaneously solving how and what

venue: Annual International Cryptology Conference, pages 451–468. Springer

authors:
A. Bittau
Ú. Erlingsson
P. Maniatis
I. Mironov
A. Raghunathan
D. Lie
M. Rudominer
U. Kode
J. Tinnes
B. Seefeld

title: Prochlo: Strong privacy for analytics in the crowd

venue: Proceedings of the 26th Symposium on Operating Systems Principles, pages 441–459

authors:
M. Bun
J. Nelson
U. Stemmer

title: Heavy hitters and the structure of local privacy

venue: ACM Transactions on Algorithms (TALG), 15(4):1–40

authors:
T.H. Chan
E. Shi
D. Song

title: Optimal lower bound for differentially private multi-party aggregation

venue: European Symposium on Algorithms, pages 277–288. Springer

authors:
A. Cheu
A. Smith
J. Ullman
D. Zeber
M. Zhilyaev

title: Distributed differential privacy via shuffling

venue: Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 375–403. Springer

authors:
A. Dubey
A. Pentland

title: Differentially-private federated linear bandits

venue: arXiv preprint arXiv:2010.11425

authors:
C. Dwork
F. McSherry
K. Nissim
A. Smith

title: Calibrating noise to sensitivity in private data analysis

venue: Theory of cryptography conference, pages 265–284. Springer

authors:
Ú. Erlingsson
V. Feldman
I. Mironov
A. Raghunathan
S. Song
K. Talwar
A. Thakurta

title: Encode

venue: shuffle, analyze privacy revisited: Formalizations and empirical evaluation. arXiv preprint arXiv:2001.03618

authors:
Ú. Erlingsson
V. Feldman
I. Mironov
A. Raghunathan
K. Talwar
A. Thakurta

title: Amplification by shuffling: From local to central differential privacy via anonymity

venue: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2468–2479. SIAM

authors:
H. Esfandiari
A. Karbasi
A. Mehrabian
V. Mirrokni

title: Regret bounds for batched bandits

venue: arXiv preprint arXiv:1910.04959

authors:
Z. Gao
Y. Han
Z. Ren
Z. Zhou

title: Batched multi-armed bandits problem

venue: arXiv preprint arXiv:1904.01763

authors:
B. Ghazi
R. Pagh
A. Velingker

title: Scalable and differentially private distributed aggregation in the shuffled model

venue: arXiv preprint arXiv:1906.08320

authors:
A. Guha Thakurta
A. Smith

title: nearly) optimal algorithms for private online learning in full-information and bandit settings

venue: Advances in Neural Information Processing Systems, 26:2733–2741

title: Probability inequalities for sums of bounded random variables

venue: The Collected Works of Wassily Hoeffding, pages 409–426. Springer

authors:
P. Jain
P. Kothari
A. Thakurta

title: Differentially private online learning

venue: Conference on Learning Theory, pages 24–1. JMLR Workshop and Conference Proceedings

authors:
E. Kaufmann
O. Cappé
A. Garivier

title: On the complexity of best-arm identification in multi-armed bandit models

venue: The Journal of Machine Learning Research, 17(1):1–42

authors:
N. Mishra
A. Thakurta

title: nearly) optimal differentially private stochastic multi-arm bandits

venue: Proceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence, pages 592–601

authors:
W. Ren
X. Zhou
J. Liu
N.B. Shroff

title: Multi-armed bandits with local differential privacy

venue: arXiv preprint arXiv:2007.03121

title: Some aspects of the sequential design of experiments

venue: Bulletin of the American Mathematical Society, 58(5):527–535

authors:
T. Sajed
O. Sheffet

title: An optimal private stochastic-mab algorithm based on optimal private stopping rule

venue: International Conference on Machine Learning, pages 5579–5588. PMLR

authors:
R. Shariff
O. Sheffet

title: Differentially private contextual linear bandits

venue: arXiv preprint arXiv:1810.00068

authors:
C. Shi
C. Shen

title: Federated multi-armed bandits

venue: arXiv preprint arXiv:2101.12204

title: On the likelihood that one unknown probability exceeds another in view of the evidence of two samples

authors:
A. Tossou
C. Dimitrakakis

title: Algorithms for differentially private multi-armed bandits

venue: Proceedings of the AAAI Conference on Artificial Intelligence, volume 30

authors:
K. Zheng
T. Cai
W. Huang
Z. Li

title: and L

venue: Wang. Locally differentially private

text:
O ((∑ a∈[k]:∆a>0 log T ∆a ) + k √ log 1δ log T ε ) , and a distribution-independent regret
of O (√ kT log T + k √ log 1δ log T
ε
) , where T is the number of rounds, ∆a is the
suboptimality gap of the arm a, and k is the total number of arms. Our upper bound almost matches the regret of the best known algorithms for the centralized model, and significantly outperforms the best known algorithm in the local model.

heading: 1 Introduction

text:
The multi-armed bandit (MAB) problem is a classical sequential decision-making problem in which an agent tries to maximize a cumulative stochastic reward [27, 23] under uncertainty. This problem, which is applicable to various areas such as recommender systems, online advertising and clinical trials, embodies the well known exploration-exploitation trade-off between learning the environment and acting optimally based on our current knowledge about the environment.
More formally, in the MAB problem at each time t = 1, . . . , T an agent chooses an arm i from the set [k] = {1, . . . , k} of k arms, and obtains an iid reward rt drawn from the unknown distribution Ri over {0, 1} with expectation µi = E [Ri]. Let a∗ = arg maxa µa be an arm with the largest expected reward, and denote this reward by µ∗ = µa∗ . Let the (suboptimality) gap of an arm a to be the gap between its expected reward and that of a∗, i.e., ∆a = µ∗ − µa. The agent’s goal is to maximize the total expected reward, or rather to minimize the expected regret R(T ) = T · µ∗ − E [∑T i=1 r t ] defined to be the expected gap between the algorithm and the optimal algorithm that knows the distributions Ri.
In this work we address the privacy in such a setting. As a motivating example, consider an advertisement system in which the server presents to each user an advertisement a ∈ [k]. The user then decides whether to click on the advertisement or not. This click decision depends on different private characteristic of the user. The user then reports to the server whether it clicked on the advertisement (in which case its reward is r = 1) or not (r = 0). From this example, it is clear that r is private information of the user, and using traditional algorithms for the MAB problem incautiously might leak user-private data.
In order to mathematically alleviate privacy concerns, Dwork et al. [11] defined the notion of differential privacy (DP), which requires that the output of the computation has a limited dependency ∗Google Research. jayten@google.com. †Blavatnik School of Computer Science, Tel Aviv University and Google Research. haimk@tau.ac.il. ‡Blavatnik School of Computer Science, Tel Aviv University and Google Research. mansour.yishay@gmail.com. §Blavatnik School of Computer Science, Tel Aviv University and Google Research. u@uri.co.il.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
on any single user’s data. Formally, a mechanism (ε, δ)-DP if for any pair of neighboring inputs (differing by a single user’s data), the probability that the mechanism outputs a value in any set B is not different by more than a multiplicative factor of eε and an additive factor of δ. Differential privacy has been extensively studied under many different sub-models of privacy. On one end of the spectrum lies the centralized model of differential privacy, where the users trust the server with their data, and the liability to protect user privacy lies on the server, who must make sure that any data published externally (e.g., aggregated statistics) respects the privacy constraints. On the other end of the spectrum lies the (strictly stronger) local model of differentialy privacy (LDP), where the user privatizes its own data prior to sending it to the server.5
Differentially private versions of the MAB problem have been considered in various previous works, where the private information are users’ rewards (two neighboring inputs differ by the reward value of a single user), and the algorithm’s output is the subsequent arm(s) it selects. Table 1 summarizes the best known distribution-dependent regret bounds for the various privacy models, together with our new result in the shuffle model which we soon define formally.
With real-world algorithms gradually moving away from the centralized model of privacy, the immediate question is “can we design a private algorithm for MAB with privacy guarantees which are similar to local DP, but with similar regret to centralized DP (without a multiplicative 1/ε2 factor)?”.
To address the inevitable gap between the local and centralized models, which is in fact common in the literature of differential privacy, the alternative shuffle model [6, 9, 13] explores the space in between the local and centralized models by introducing a trusted shuffler that receives user messages and permutes them (i.e., disassociates a message from its sender) before they are delivered to the server. For privacy analysis, we assume that the shuffle is perfectly secure, i.e., its output contains no information about which user generated each of the messages. This is traditionally achieved by the shuffler stripping implicit metadata from the messages (e.g., timestamps, routing information), and frequently forwarding this data to remove time and order information. The shuffle model ensures that sufficiently many reports are collected in each round so that any one report can hide in a shuffled batch. In order to apply the shuffle model to the MAB problem in the context of advertisements, we divide the algorithm into batches, where before each batch we decide on the fly its size m, and then present the m next users the same advertisement a, and finally apply a private shuffle model mechanism to their rewards to communicate reward aggregate information to the server.8
A constantly growing body of work presents new and improved mechanisms in the shuffle model for basic statistical tasks [16, 13, 12, 2], such as private binary summation, in which the server must privately approximate the sum of a collection of values x1, ..., xm ∈ {0, 1} held by the m users in
5Formally, in the non-interactive setting, a mechanism is (ε, δ)-LDP if for any two user inputs, the probability that the privatizer sends the server a value in any set B is not different by more than a multiplicative factor of eε and an additive factor of δ. 6The corresponding distribution-independent regret bounds usually simply replace the ∑ a∈[k]:∆a>0 log T ∆a
term with √ kT log T .
7This lower bound can be extended from (ε, 0)-LDP to (ε, δ)-LDP using arguments from Bun et al. [7] and Cheu et al. [9] since we focus on single-round (non-interactive) mechanisms in which the user can only send information to another party once.
8We remark that a given user does not know in advance the size of the batch in which it participates, since this size depends on the algorithm’s run.
the shuffle. For private binary summation, the optimal achievable errors in the central, local and shuffle model are Θ̃(1/ε) [11], Θ̃( √ m/ε) [5, 8] and Θ̃(1/ε) [9] respectively, where the Θ̃(·) hides poly-logarithmic terms. Similar errors hold for the private summation problem which approximates the sum of real values in [0, 1].

heading: 1.1 Our contributions

text:
To the best of our knowledge, our work is the first to consider the MAB problem under the shuffle model of differential privacy. In order to support the online nature of the MAB problem, we consider a variant of the shuffle model. As opposed to the classical shuffle model, in which the shuffle size is unbounded and the mechanism runs only once, we continuously run shuffle mechanisms for many disjoint batches of users who can only afford a single round of communication.9
We consider the paradigm where the server controls the different users who are cooperative and communicate only with the server. We give a rigorous definition of shuffle differential privacy (SDP) for the multi-armed bandit problem (assuming binary rewards), and give and prove the first two such algorithms. Our algorithms Shuffle Differentially Private Arm Elimination (SDP-AE) and Variable Batch Shuffle Differentially Private Arm Elimination (VB-SDP-AE) are both based on the well-known arm elimination (AE) algorithm, using consecutive batches of users and together with an SDP private binary summation mechanism.
We show that the simpler but weaker SDP-AE achieves a distribution-dependent regret of O ((∑
a∈[k]:∆a>0 log T ∆a
) +
k log 1δ ε2
) , and a distribution-independent regret of
O (√
kT log T + k log 1δ ε2
) .10
We then describe VB-SDP-AE, a generalization of SDP-AE to exponentially growing batch sizes, and prove it has a distribution-dependent regret of O ((∑
a∈[k]:∆a>0 log T ∆a
) + k √ log 1δ log T
ε
) , and
a distribution-independent regret of O (√ kT log T + k √ log 1δ log T
ε
) .
Note that, compared to the local model (Ren et al [22]), the regret of both SDP-AE and VB-SDP-AE is improved, by having the dependency on 1/ε be additive rather than multiplicative. In addition, VB-SDP-AE almost matches the regret of the best known algorithms for the centralized model,
that is the distribution-dependent regret of O ((∑
a∈[k]:∆a>0 log T ∆a ) + kε ) of Tossou and Dimi-
trakakis [28].

heading: 1.2 Related work

text:
The differentially private MAB problem has been considered in many previous works [19, 17, 21]. Shi and Shen [26] and Dubey and Pentland [10] studied MAB and linear bandits respectively in the federated setting. Zheng et al. [29] studied contextual bandits with LDP. Batched MAB with a predetermined number of batches was studied in [14, 15].
For the private summation problem, Cheu et al. [9] gave unbiased (ε, δ)-SDP mechanisms over binary inputs and real inputs in [0, 1], with error roughly √ log(1/δ)/ε and log(1/δ)/ε, respectively. In several works of Balle et al. [2, 3, 1], they gave a biased (ε, δ)-SDP mechanism for real inputs in [0, 1] with similar error and a constant number of messages, and a single-message (ε, δ)-SDP mechanism with optimal error.
9Beimel et al. [4] showed that every centralized-DP mechanism can be emulated in the shuffle model in two (communication-intensive) rounds of communication, however these results are not applicable to our setting since we assume that each online user participates only in one shuffle and then disappears.
10In this paper, we assume that T is known apriori. Otherwise, we can apply standard doubling arguments to get roughly the same results.

heading: 2 Background and preliminaries

heading: 2.1 Shuffle-model privacy

text:
In the well-studied setting of shuffle model privacy, there are m users, each with data xi ∈ X . Each user applies some encoder E : X → Y ∗ to their data and sends the messages (yi,1, ..., yi,p) = E(xi) to a shuffler S : Y ∗ → Y ∗. The shuffler then shuffles all the messages yi,j from all the users, and outputs them in a uniformly random order to an analyzer A : Y ∗ → Z to estimate some function f(x1, ..., xm). Thus, the mechanism M consists of the tuple (E,S,A). We say that such a mechanism M is (ε, δ)-shuffle differentially private (or (ε, δ)-SDP for short) if the output of S is (ε, δ)-differentially private, or more formally: A mechanism M = (E,S,A) is (ε, δ)-SDP if for any pair of inputs {xi}mi=1 and {x′i}mi=1 which differ in at most one value, we have for all B ⊆ Y ∗:
P (S(∪mi=1E(xi)) ∈ B) ≤ eε · P (S(∪mi=1E(x′i)) ∈ B) + δ.
In the mechanism used in this paper, E outputs the user’s reward bit together with a set of random bits, and A sums all these bits and debiases the result to get an unbiased estimate of the sum of the users’ rewards.

heading: 2.2 Shuffle-model MAB

text:
Algorithms which are private in the shuffle model typically apply the mechanism M once over a set of m users. Here we study the MAB problem which is an online problem, often deployed in real-world applications and with users which are end-devices such as cellphones with a possibly limited or unreliable internet connection. Hence, to adapt the MAB problem to the shuffle model, we batch sequences of consecutive users, and assume that each user can afford a single round of communication, and is never selected more than once.
Model and objective The shuffle-model MAB setting involves repeating the following process until the T ’th player pulls its arm:
1. The server selects a batch size m, a batch of m random fresh new users, and an m-user single-round SDP mechanism M .11 It then picks an arm a ∈ [k] that all m users of the batch pull. (For concreteness think that the server picks an ad a ∈ [k] and sends it to the a random batch of m users.)
2. Each user i determines binary reward from pulling the arm a.12 (For concreteness think that each user decides whether to click on the ad or not. This defines the reward related to user i, which is ri = 1 if it clicks the ad and ri = 0 otherwise.) Since our m users are random, these rewards are a sample of m independent rewards from the distribution Ra associated with arm a.
3. The server computes M({ri}i∈batch) using the rewards ri.
The objective is to minimize the (pseudo) regret, which is the expected difference between the sum of the rewards accumulated (over all the users) by the algorithm and the sum of the rewards of the optimal algorithm that apriori knows an arm with the largest expected reward a∗. Let µa = E [Ra] be the expected reward (or simply mean) of the arm a, let µ∗ denote the expected reward of a∗, let ∆a = µ
∗ − µa be the (suboptimality) gap of the arm a which quantifies the gap between its expected reward and that of a∗, and let Na be the random variable which counts the total number of times the arm a was pulled during the run of the algorithm.
Formally, the (pseudo) regret of the algorithm for T ∈ N users is defined to be
R(T ) = T · µ∗ − E  T∑ i=1 ri  = E ∑ a∈[k] Na∆a  . 11Note that always selecting m = 1 reduces this setting to the Local model MAB. 12For simplicity, we assume that the rewards are binary. However, our algorithms and proofs naturally extend to the real [0, 1] reward setting, by replacing our private binary summation mechanism (defined later, see Appendix C) with a private summation mechanism for real numbers in [0, 1] with similar guarantees.
Privacy Since the private data of each user is its reward, the appropriate adaptation of shuffle model privacy for the multi-armed bandit problem is as follows. An algorithm for the multi-armed bandits problem is (ε, δ)-shuffle differentially private (SDP) if for any batch of users, the shuffle mechanism that we apply over them in step 3 is (ε, δ)-SDP with respect to the rewards of the users (as we recall, the reward of a user – whether it clicked on an ad or not – depends on its private features). Formally, for every batch we run a shuffle mechanism where the m users are the users of the current batch, and the data xi of each user is its reward ri, and we require that each such mechanism is (ε, δ)-SDP.

heading: 2.3 Concentration bounds

text:
We use the following standard definitions of Sub-Gaussian random variables and Hoeffding’s inequality. Definition 1 (Sub-Gaussian random variable). A random variable X with mean µ is called subGaussian with variance σ2, i.e., X ∼ SG(σ2) if:
∀λ ∈ R, E [ exp(λ(X − µ)) ] ≤ eλ 2σ2/2.
An equivalent definition shows that if ∀t > 0,max ( P (X − µ ≥ t), P (X − µ ≤ −t) ) ≤
exp ( −t2 2σ2 ) , then X is sub-Gaussian with variance σ2 (up to constant factor). It is well known that if
Xi ∼ SG(σ2i ) are independent random variables for i = 1, . . . , n, then ∑n i=1Xn ∼ SG( ∑n i=1 σ 2 i ) and for any a, b > 0, a · X1 + b ∼ SG(a2 · σ21). A bounded random variable X ∈ [a, b] is SG((b− a)2/4). Sub-Gaussian random variables satisfy the following concentration bound, Lemma 2.1 (Hoeffding’s inequality [18]). Let {Xi}ni=1 be independent SG(σ2) random variables,
then P (∣∣∣∑ni=1Xi − E [∑ni=1Xi]∣∣∣ ≥ t) ≤ 2 exp( −t22nσ2) .

heading: 3 Differentially private MAB in the shuffle model

text: In this paper, we use the shuffle model to give a private solution to the multi-armed bandit problem, attaining similar privacy guarantees to that of the local privacy model (LDP), without sacrificing the regret. That is, our algorithm almost matches the best known regret in the centralized model of differential privacy. Our algorithms rely on the fact that algorithms for the multi-armed bandit problem take decisions based on sums of rewards received from the users. Hence, we rely on a particularly efficient and accurate mechanism for private binary summation in the shuffle model as a building block in our algorithms. Specifically, for any ε, δ ∈ (0, 1), let Msum be a private binary summation mechanism, which for any number of users (batch size) m ∈ N, is (ε, δ)-SDP, unbiased, and has an error distribution which is independent of the input, and is sub-Gaussian with variance σ2ε,δ = O ( log 1δ ε2 ) .13 Note that our notation of Msum does not include ε and δ which will always be clear from context or inherited from the algorithm which runs Msum. The challenge is to combine Msum with the well studied arm elimination (AE) MAB algorithm to get an SDP algorithm for the MAB problem with almost optimal regret.14

heading: 3.1 SDP-AE: Shuffle Differentially Private Arm Elimination

text:
We base our algorithm on the (non-private) arm elimination (AE) algorithm for the MAB problem, which informally maintains a set of viable arms (initially set to be [k]), and each phase pulls the set of viable arms sequentially. Once a phase ends, we search for arms which are noticeably suboptimal in comparison to some other arm, and we eliminate them from the set of viable arms.
To adapt AE to the shuffle model, in each phase t each arm is pulled not once, but rather by a whole batch of users. Once all the users in the batch pull the arm and receive their reward, we apply
13Note that our methods and algorithms should work similarly if they were built over other common algorithms for the MAB problem in which batching makes sense, such as the UCB algorithm.
14For completeness, in Appendix C we give a complete description and a proof of such a mechanism Msum.
the private binary summation mechanism Msum to the batch’s rewards, which gives the server an unbiased but noisy estimate of the sum of rewards in the batch. This estimate has two sources of error, which we account for when we compute the upper confidence bound – the empirical error due to sampling the reward function of the arm, and the error due to the private binary summation mechanism Msum.

heading: 3.1.1 Algorithm outline

text:
In the algorithm below which we call Shuffle Differentially Private Arm Elimination (SDP-AE), we update the estimate of the mean reward of each arm a after every batch of users who sample a. The algorithm works in phases, and maintains a set of viable arms initially set to be [k]. In each phase, for every viable arm we have a single batch of users sampling it. At the end of phase t, we denote by Ŝta the noisy estimate of the cumulative sum of the rewards from all previous samples of a in the phases 1, . . . , t, and denote by N ta the total number of previous samples of arm a in the phases 1, . . . , t. The natural estimate for the mean reward of the arm a (denoted by µ̂ta) is therefore µ̂ t a = Ŝ t a/N t a. We then calculate the upper and lower confidence bounds UCBta and LCB t a respectively of each viable arm a after each phase t using a specific bound which takes into account both sources of error. We finally eliminate any remaining arm with an upper confidence bound which is strictly smaller than the lower confidence bound of some other arm. Algorithm 1 consolidates the algorithm presentation above.
Algorithm 1: SDP-AE (Shuffle Differentially Private Arm Elimination) 1 Input: privacy parameters ε and δ, batch size m and horizon T . 2 Initialize: Ŝ0a = 0, N0a = 0 and µ̂0a = 0 for every a ∈ [k]; 3 Let σ2ε,δ = O ( log 1δ ε2 ) be the sub-Gaussian variance of the error distribution of Msum;
4 Let V = [k] denote the set of viable arms; 5 for phase t← 1, 2, . . . do 6 for arm a ∈ V do 7 for each new user i← 1 to m do 8 User i pulls the arm a and observes reward rta,i; 9 If total arm samples in current algorithm run is T , exit;
10 end 11 Communication: Perform private binary summation Zta ←Msum ( {rta,i}mi=1 ) ;
12 Server update: Update Ŝta ← Ŝt−1a + Zta, N ta ← N t−1a +m, and finally µ̂ta ← Ŝta/N ta; 13 end
14 Confidence bounds: For each arm a, calculate Ita ← ( 2 √ tσε,δ Nta + 1√ Nta ) · √ 2 log T , and the upper and lower confidence bounds UCBta ← µ̂ta + Ita and LCBta ← µ̂ta − Ita; 15 Elimination: remove all arms a from V such that UCBta < maxa′∈S LCBta′ ; 16 end

heading: 3.1.2 Analysis

text:
The privacy is trivial, since each batch we use the (ε, δ)-SDP mechanism Msum. We now focus on regret.
Theorem 3.1 gives a bound on the regret of SDP-AE as a function of the batch size m. We follow a somewhat standard regret bound analysis for arm elimination, comprising two parts. The first part uses Hoeffding’s inequality to derive a high probability bound on ∣∣µ̂ta − µa∣∣, the error between the empirical average reward and the true mean reward of the arm a at a given phase t. The second part uses this bound to bound the expected number of times we sample each suboptimal arm a, and summing over all suboptimal arms we get a bound on the regret.
Theorem 3.1. The algorithm SDP-AE is (ε, δ)-SDP, and has a distribution-dependent re-
gret of O (∑ a∈[k]:∆a>0 ( log T ∆a + σ2ε,δ log T m∆a +m∆a )) , and a distribution-independent regret of
O √(1 + σ2ε,δm ) kT log T +mk .
Proof sketch. Fix a phase t. For any arm a, we have µ̂ta = ∑t s=1Msum({r s a,i} m i=1)
Nta , where N ta = m · t.
We apply Hoeffding’s inequality (Lemma 2.1) once on the sequence of actual rewards of the users, and once on the sequence of errors that Msum introduces into the approximated sum of rewards. We conclude that with high probability, ∀a ∈ [k],∀t ∈ [T ], we have ∣∣µ̂ta − µa∣∣ ≤ ( 2√tσε,δNta + 1√Nta ) · √ 2 log T .
Assuming this high probability event, each arm a is necessarily eliminated after the phase t0 where ∣∣µ̂t0a − µa∣∣ becomes at most roughly ∆a/4. We show that this occurs after at most O ( log T ∆2a + σ2ε,δ·log T m∆2a ) pulls of the arm a, and since we must complete the batch of size m, the
total regret of the arm a is at most Ra = O (
log T ∆a + σ2ε,δ·log T m∆a +m∆a
) . To get the distribution-
dependent regret we sum the regret above over all arms. For the distribution-independent regret, we split this sum based on if the arm a has ∆a < β where β = Θ (√ (1+σ2ε,δ/m)k log T
T
) or not, and
bound each sum separately. Namely, bound the contribution of arms with ∆a < β by βT .
Recall that the private binary summation mechanism Msum’s error distribution is sub-Gaussian with variance σ2ε,δ = O ( log 1δ ε2 ) . We fix a concrete batch size m in SDP-AE, and apply Theorem 3.1 to get the following corollary.
Corollary 3.2. SDP-AE with a batch size of m = ⌈ σε,δ ⌉ = Θ ( log 1δ ε2 ) is (ε, δ)-SDP and has a distribution-dependent regret of
O  ∑ a∈[k]:∆a>0 ( log T ∆a + ∆a log 1 δ ε2 ) = O   ∑ a∈[k]:∆a>0 log T ∆a + k log 1δ ε2  , and a distribution-independent regret of O (√ kT log T +
k log 1δ ε2
) .

heading: 3.2 VB-SDP-AE: Variable Batch Shuffle Differentially Private Arm Elimination

text:
In this section we modify SDP-AE to give an (ε, δ)-SDP algorithm for the MAB problem with improved additional regret. Recall that SDP-AE has a distribution-dependent regret of
O ((∑ a∈[k]:∆a>0 log T ∆a ) + k log 1δ ε2 ) , whereas the best known regret for (ε, δ) centralized-DP is
due to Tossou and Dimitrakakis [28], and is O ((∑
a∈[k]:∆a>0 log T ∆a ) + kε ) . Since any SDP algo-
rithm can be emulated by a centralized-DP mechanism, we can only wish to match the regret of Tossou and Dimitrakakis [28]. Hence, the natural question is: “Can we reduce the dependence in ε of the additive (second) regret term from 1ε2 to 1 ε?” 15
15Note that a Naive attempt to convert the algorithm of Tossou and Dimitrakakis [28] from the centralized model to the shuffle model fails. This is since in the centralized model they can decrease the relative noise as the number of iteration increases by keeping the raw data from the users and reusing it in later iterations. However, in our setting, the noise per shuffle batch has to remain constant for privacy, and we do not have access to the raw data of the users.
Before presenting our solution, we first indicate two intuitive approaches that fail. The first is to continue using batches of constant size m = Ω(1/ε2). This idea fails since intuitively in the worst case we can expect a first batch regret of m = Ω(1/ε2) which already surpasses O(1/ε). The second is to try to directly adapt the algorithm of Tossou and Dimitrakakis [28], which can be interpreted as AE with batches of size ⌈ 1/ε ⌉ . Unfortunately, this adaptation fails since it requires that the added noise to the empirical mean of each arm decreases with time, whereas in the shuffle model, we must ensure privacy with respect to each batch equally and independently, so the total noise cannot decrease with time.
Now for our improved algorithm, observe that using a large batch size increases the regret a lot for arms which are very suboptimal. This is since rather than pulling these arms only a few times until we detect that they are suboptimal, we commit ourselves to pulling them throughout a large batch. On the other hand, fixing the batch size to be small increases the overall estimation error, since every application of the SDP summation algorithm Msum introduces an error of the same magnitude (specifically, the error is sub-Gaussian with variance σ2ε,δ = O ( log 1δ ε2 ) ) independently of the batch size. Hence, more executions of Msum translates to more noise due to privacy. We therefore extend SDP-AE to support variable size batches, which start small and gradually increase. Intuitively, the smaller batches initially, allow us to quickly eliminate very suboptimal arms with only a small number of pulls. We gradually increase the batch size to reduce the per-user error introduced by the private binary summation mechanism. Specifically, we double the batch size after each phase.

heading: 3.2.1 Algorithm outline

text:
We consolidate the idea above into Algorithm 2 below, which we call Variable Batch Shuffle Differentially Private Arm Elimination (VB-SDP-AE), which uses a different batch size mt = 2t for each phase t:
Algorithm 2: VB-SDP-AE (Variable Batch Shuffle Differentially Private Arm Elimination) 1 Input: privacy parameters ε and δ and horizon T . 2 Initialize: Ŝ0a = 0, N0a = 0 and µ̂0a = 0 for every a ∈ [k]; 3 Let σ2ε,δ = O ( log 1δ ε2 ) be the sub-Gaussian variance of the error distribution of Msum;
4 Let V = [k] denote the set of viable arms; 5 for phase t← 1, 2, . . . do 6 Let mt ← 2t; 7 for arm a ∈ V do 8 for each new user i← 1 to mt do 9 User i pulls the arm a and observes reward rta,i;
10 If total number of arm samples is T , exit; 11 end 12 Communication: Perform private binary summation Zta ←Msum ( {rta,i}m t i=1 ) ;
13 Server update: Update Ŝta ← Ŝt−1a +Zta, N ta ← N t−1a +mt, and finally µ̂ta ← Ŝta/N ta; 14 end
15 Confidence bounds: For each arm a, calculate Ita ← ( 2 √ tσε,δ Nta + 1√ Nta ) · √ 2 log T , and the upper and lower confidence bounds UCBta ← µ̂ta + Ita and LCBta ← µ̂ta − Ita; 16 Elimination: remove all arms a from V such that UCBta < maxa′∈S LCBta′ ; 17 end

heading: 3.2.2 Analysis

text:
The privacy is trivial, since in each batch we use the (ε, δ)-SDP mechanism Msum. We now focus on regret.
To give a regret bound on VB-SDP-AE, we follow a similar proof to that of Theorem 3.1.
Theorem 3.3. The algorithm VB-SDP-AE is (ε, δ)-SDP, and has a distribution-dependent regret of O ((∑
a∈[k]:∆a>0 log T ∆a
) + kσε,δ log T ) , and a distribution-independent regret of
O (√ kT log T + kσε,δ log T ) .
Proof sketch. A slight modification of the proof of Theorem 3.1 lets us recover that with high probability, ∀a ∈ [k],∀t ∈ [T ], we have that ∣∣µ̂ta − µa∣∣ ≤ ( 2√tσε,δNta + 1√Nta ) · √ 2 log T . Assuming this high probability event, adapting the proof of Theorem 3.1 to our exponentially growing batch sizes gives that each arm a is necessarily eliminated after we have already performedO ( log T ∆2a + σε,δ·log T ∆a ) pulls of the arm a. Unlike the proof of Theorem 3.1, since the batch sizes grow as 2t, the additional pulls of the arm a required to complete the last batch before elimination, adds only a factor of 2 to the total number of pulls to the arm. Hence, the regret of the arm a is at most Ra = O ( log T ∆a + σε,δ · log T ) .
To get the distribution-dependent regret we sum the regret above over all arms. For the distributionindependent regret, we split this sum based on if the arm a has ∆a < β where β = Θ (√ k log T T ) or
not, and bound each sum separately. Namely, bound the regret over arms with ∆a < β by βT .
We recall that the private binary summation mechanism Msum’s error distribution is sub-Gaussian with variance σ2ε,δ = O ( log 1δ ε2 ) , i.e., σε,δ = O (√ log 1δ ε ) , and apply Theorem 3.3 to get the
following corollary. Corollary 3.4. VB-SDP-AE is (ε, δ)-SDP and has a distribution-dependent regret of
O ((∑ a∈[k]:∆a>0 log T ∆a ) + k √ log 1δ log T ε ) , and a distribution-independent regret of
O (√ kT log T + k √ log 1δ log T
ε
) .

heading: 4 Conclusion and future work

text:
In this paper, we gave and analyzed differentially private algorithms for the MAB problem, closing the inevitable multiplicative Ω(1/ε2) regret gap between the local model and the centralized model, by considering the (intermediate) shuffle model. Our algorithms are batched variants of AE, which use a private binary summation mechanism for the shuffle model as a building block. Compared to the non-private AE algorithm’s regret, our first algorithm SDP-AE has an additive factor of k log 1δ ε2 using constant size batches, and our second algorithm VB-SDP-AE improves the additive
factor to k √ log 1δ log T
ε by using exponentially growing batches, which enable the early detection and elimination of very suboptimal arms.
A natural future work is to extend our results (i.e., the usage of a private binary summation mechanism for the shuffle model) to more general RL settings such as linear/contextual bandits or Markov decision processes. It would also be interesting to study whether our log T term in the additional additive regret factor can be shaved through a more sophisticated algorithm, or an alternative analysis. Finally, it is interesting to study whether there are more refined distribution-dependent regret bounds that depend on the KL-divergence as in Kaufmann et al. [20].
Disclosure of Funding
This work is partially supported by Israel Science Foundation (grants 993/17,1595/19,1871/19), German-Israeli Foundation (grant 1367/2017), Len Blavatnik and the Blavatnik Family Foundation, the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation program (grant agreement 882396), the Yandex Initiative for Machine Learning at Tel Aviv University.

title: Differentially Private Multi-Armed Bandits in the Shuffle Model


summaries: This work applies the concept of calibrated regression into a decision making framework where the decision is confined to threshold decisions. The Bayes optimal decision w.r.t. the predicted distribution is derived, and the concept of threshold calibration is defined. Threshold calibration is a sufficient and necessary condition for the reliability gap to be 0, meaning the absolute difference between the predicted expected loss and the true expected loss is 0 for a given decision rule. Further, a simple algorithm is proposed which threshold recalibrates a distributional prediction.

summaries: As pointed out by the paper, threshold calibration is related with practical hospital scheduling problem, in which hospital needs to make the decision to acquire new patients based on predicted length-of-stay to the existing patients. The paper proposed an efficient and practical threshold calibration method, which calibrated the non-calibrated results based on CDF prediction, and is shown to have better calibration results as compared to average calibration and distribution calibration.  Additionally, the paper proposed an algorithm to do threshold calibration, and empirical results on real data sets shows reduced reliability gap and true decision loss.

summaries: This paper considers the problem of calibrating the conditional CDFs from a regression model.    The authors propose a new definition of threshold calibration, which requires the conditional CDFs to have calibrated quantiles when these CDFs have a $\alpha$-quantile that are all on the same side regarding a given $y_0$ (either above or below).    The proposed definition is a stronger notion of quantile calibration in regression (called averaged calibration in this paper), and a weaker notion of distribution calibration in regression. To further justify the proposed definition, the authors consider measuring the so-called reliability gap, which is based on a given loss function and the corresponding decision rule. The authors then show that having threshold-calibrated results can ensure a 0 reliability gap. The necessity and sufficiency among different calibration definitions are later demonstrated.  On the method level, the proposed approach is hence to iteratively search for quantile levels and thresholds with large calibration errors and applies isotonic regression to calibrate the corresponding quantiles. The final calibrated model will include the uncalibrated models and a sequence of calibration maps.  Experiments are performed with real datasets with a cost-sensitive setup. The proposed method is compared with uncalibrated model, quantile calibrated model and distribution calibrated model.

summaries: This paper discusses calibrated regression from a decision-making perspective, by introducing the concept of 'threshold calibration'. The popular notion of calibrated regression, average calibration, is insufficient for decision-making. On the other hand, the notion of distribution calibration is sufficient for decision-making, but may be difficult to achieve. In practice, decisions based on regression predictions are often made on the basis of whether the prediction is smaller or larger than some threshold. Thus, a decision-oriented goal is to ensure calibration with respect to such a threshold, called threshold calibration. The paper proposes an algorithm to achieve threshold calibration.

summaries: This paper focuses on the task of "calibrating" forecasts used in downstream decision-making tasks to ensure accurate estimation of the loss or "cost" of using each decision rule (i.e. the decision loss). The paper is specifically focused on forecasts of real-valued quantities (regression) and binary decisions (or actions) made by thresholding the forecast (for example, deciding whether to accept or reject a new patient based on the forecasted length of stay of a current patient being above or below some threshold).  In this setting, the paper shows that average calibration -- a common type of calibration -- does not ensure accurate estimation of the decision loss. The paper then introduces threshold calibration, proves that threshold-calibrated forecasts maximize the accuracy of decision loss estimates (and, moreover, that threshold-calibration is necessary and sufficient to maximize this accuracy), and provides an efficient algorithm to generate threshold-calibrated forecasts from a finite data sample. The paper validates the performance of their algorithm on real-world data (although with a synthetic downstream decision-making setup), and demonstrates more accurate decision loss estimates than those obtained by average and distribution calibration. The paper also derives the relationship between distribution, threshold, and average calibration in Proposition 1, which may be of independent interest.

abstractText: Decision makers rely on probabilistic forecasts to predict the loss of different decision rules before deployment. When the forecasted probabilities match the true frequencies, predicted losses will be accurate. Although perfect forecasts are typically impossible, probabilities can be calibrated to match the true frequencies on average. However, we find that this average notion of calibration, which is typically used in practice, does not necessarily guarantee accurate decision loss prediction. Specifically in the regression setting, the loss of threshold decisions, which are decisions based on whether the forecasted outcome falls above or below a cutoff, might not be predicted accurately. We propose a stronger notion of calibration called threshold calibration, which is exactly the condition required to ensure that decision loss is predicted accurately for threshold decisions. We provide an efficient algorithm which takes an uncalibrated forecaster as input and provably outputs a threshold-calibrated forecaster. Our procedure allows downstream decision makers to confidently estimate the loss of any threshold decision under any threshold loss function. Empirically, threshold calibration improves decision loss prediction without compromising on the quality of the decisions in two real-world settings: hospital scheduling decisions and resource allocation decisions.

title: economic forecasts and policy. assisted by j.s. cramer, h. moerman, a. russchen. contributions to economic analysis, nr xv

venue: amsterdam, north-holland publishing company,

authors:
Alexander Amini
Wilko Schwarting
Ava Soleimany
Daniela Rus

title: Deep evidential regression

venue: Advances in Neural Information Processing Systems,

authors:
S. Barnes
Eric Hamrock
Matthew F. Toerper
S. Siddiqui
S. Levin

title: Real-time prediction of inpatient length of stay for discharge prioritization

venue: Journal of the American Medical Informatics Association : JAMIA,

title: Statistical decision theory and Bayesian analysis

title: Verification of forecasts expressed in terms of probability

venue: Monthly Weather Review,

authors:
Nicolo Cesa-Bianchi
Gabor Lugosi

title: Prediction, Learning, and Games

title: Econometrics and decision theory

venue: Journal of Econometrics,

authors:
Peng Cui
Wenbo Hu
Jun Zhu

title: Calibrated reliable regression using maximum mean discrepancy

authors:
Murray Dale
Jon Wicks
Ken Mylne
Florian Pappenberger
Stefan Laeger
Steve Taylor

title: Probabilistic flood forecasting and decision-making: An innovative risk-based approach

venue: Natural Hazards, 70,

title: Optimal statistical decisions. McGraw-Hill, New York, NY [u.a], 1970. ISBN 0070162425

authors:
Dheeru Dua
Casey Graff

title: UCI machine learning repository, 2017

venue: URL http://archive. ics.uci.edu/ml

authors:
Tilmann Gneiting
Fadoua Balabdaoui
Adrian E. Raftery

title: Probabilistic forecasts, calibration and sharpness

venue: Journal of the Royal Statistical Society Series B,

authors:
Ary L Goldberger
Luis AN Amaral
Leon Glass
Jeffrey M Hausdorff
Plamen Ch Ivanov
Roger G Mark
Joseph E Mietus
George B Moody
Chung-Kang Peng
H Eugene Stanley

title: Physiobank, physiotoolkit, and physionet: components of a new research resource for complex physiologic

venue: signals. Circulation,

authors:
Clive W.J. Granger
Mark J. Machina

title: Forecasting and decision theory

venue: Handbook of Economic Forecasting,

authors:
Margaret Grosh
Carlo del Ninno
Emil Tesliuc
Azedine Ouerghi

title: For Protection and Promotion: The Design and Implementation of Effective Safety Nets

venue: The World Bank,

authors:
Humza Haider
Bret Hoehn
Sarah Davis
Russell Greiner

title: Effective ways to build and evaluate individual survival distributions

venue: Journal of Machine Learning Research,

authors:
H. Harutyunyan
Hrant Khachatrian
David C. Kale
A. Galstyan

title: Multitask learning and benchmarking with clinical time series data

venue: Scientific Data,

authors:
Ursula Hebert-Johnson
Michael Kim
Omer Reingold
Guy Rothblum

title: Multicalibration: Calibration for the (Computationally-identifiable) masses

title: Probabilistic reframing for cost-sensitive regression

venue: ACM Trans. Knowl. Discov. Data,

authors:
Alistair EW Johnson
Tom J Pollard
Lu Shen
Li-wei H Lehman
Mengling Feng
Mohammad Ghassemi
Benjamin Moody
Peter Szolovits
Leo Anthony Celi
Roger G Mark

title: Mimic-iii, a freely accessible critical care database

venue: Scientific data,

authors:
Christopher Jung
Changhwa Lee
Mallesh M. Pai
Aaron Roth
Rakesh Vohra

title: Moment multicalibration for uncertainty estimation, 2020

authors:
Ranganath Krishnan
Omesh Tickoo

title: Improving model calibration with accuracy versus uncertainty optimization

authors:
Volodymyr Kuleshov
Nathan Fenner
Stefano Ermon

title: Accurate uncertainties for deep learning using calibrated regression

venue: Proceedings of the 35th International Conference on Machine Learning, ICML 2018,

authors:
Meelis Kull
Telmo de Menezes e Silva Filho
Peter A. Flach

title: Beta calibration: a wellfounded and easily implemented improvement on logistic calibration for binary classifiers

venue: Proceedings of the 20th International Conference on Artificial Intelligence and Statistics,

authors:
Ali Malik
Volodymyr Kuleshov
Jiaming Song
Danny Nemer
Harlan Seymour
Stefano Ermon

title: Calibrated model-based deep reinforcement learning

title: A new vector partition of the probability score

venue: Journal of Applied Meteorology and Climatology,

authors:
Juan Perdomo
Tijana Zrnic
Celestine Mendler-Dünner
Moritz Hardt

title: Performative prediction

venue: Proceedings of the 37th International Conference on Machine Learning,

authors:
Geoff Pleiss
Manish Raghavan
Felix Wu
Jon Kleinberg
Kilian Q Weinberger

title: On fairness and calibration

title: henri, applied economic forecasting, chicago, rand mcnally

venue: xxv +

authors:
Evan Sheehan
Chenlin Meng
Matthew Tan
Burak Uzkent
Neal Jean
Marshall Burke
David Lobell
Stefano Ermon

title: Predicting economic development using geolocated wikipedia articles

venue: In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD

authors:
Hao Song
Tom Diethe
Meelis Kull
Peter A. Flach

title: Distribution calibration for regression

venue: In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning,

authors:
Christopher Yeh
Anthony Perez
Anne Driscoll
George Azzari
Zhongyi Tang
David Lobell
Stefano Ermon
Marshall Burke

title: Using publicly available satellite imagery and deep learning to understand economic well-being in africa

venue: Nature Communications,

authors:
Weiran Yuchi
Jiayun Yao
Kathleen E. McLean
Roland Stull
Radenko Pavlovic
Didier Davignon
Michael D. Moran
Sarah B. Henderson

title: Blending forest fire smoke forecasts with observed data can improve their utility for public health applications

venue: Atmospheric Environment,

heading: 1 Introduction

text:
Decision makers need to understand the consequences of their decisions prior to making them. When decisions are based on predictions from a machine learning model, the decision loss – the loss incurred under a decision rule based on the predictions – summarizes the consequences of these decisions. As an example, suppose a machine learning practitioner develops a model to predict patient length-of-stay in the hospital [17, 3]. A hospital decides whether they have capacity to admit new patients based on the model’s predictions of current patients’ length-of-stay (e.g. for each current patient who is predicted to have a length-of-stay that is less than k days, the hospital schedules a new patient). Incorrect decisions due to the model’s predictions cause the hospital to accrue costs from under-utilizing resources or overbooking procedures. The decision loss is an aggregation of the costs incurred from incorrect decisions. To determine whether a decision rule is safe to use, the hospital would like to have an accurate estimate of the decision loss under different choices of k and different costs associated with errors. This type of decision-making scenario occurs in many high-stakes settings such as designing interventions for adverse weather events [33, 9] and resource allocation decisions using economic estimates [15, 32].
Probabilistic predictions (probabilistic forecasts) can be used to estimate decision loss prior to deployment. In this work, we consider the regression setup, where a forecast is represented by a cumulative distribution function over the possible outcomes. If the forecasted probabilities of
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
incorrect decisions match the true frequencies of these events, then the average decision loss can be accurately predicted from the forecasts. However, forecasted probabilities of incorrect decisions do not typically match the true ones, yielding inaccurate decision loss predictions. We refer to the absolute difference between the average loss predicted by forecaster and the true average loss as the reliability gap.
Many previous works in calibration and uncertainty quantification are motivated by the assumption that calibrated uncertainty estimates will yield safer or more reliable downstream decisions [31, 2, 22, 24, 25]. However, we find that the standard notion of calibration, average calibration, does not guarantee zero reliability gap for even a simple class of decision rules: threshold decision rules (left, Figure 1). In a threshold decision, a decision maker takes one of two possible actions depending on whether an outcome falls above or below a cutoff (e.g. the hospital schedules a new patient if a current patient’s length-of-stay is less than 3 days, otherwise the hospital does not schedule a new patient). Stronger calibration properties, such as distribution calibration [31], are theoretically guaranteed to yield zero reliability gap but are difficult to achieve in practice. In particular, flexible distribution families can better approximate the true distribution than simple ones and yield lower decision loss, but applying distribution calibration to such forecasters can increase the decision loss and enlarge the reliability gap compared to the uncalibrated forecaster. Thus, existing calibration definitions are either insufficient or impractical for minimizing the reliability gap under threshold decision rules.
To address these shortcomings, we propose a new notion of calibration called threshold calibration. Threshold calibration strikes a balance between average and distribution calibration; it is exactly the condition required to guarantee zero reliability gap under threshold decisions and is practical to enforce (Figure 1, Right). First, we establish that threshold calibration is the necessary and sufficient condition to guarantee zero reliability gap for any threshold decision under any threshold loss. Second, we design an efficient algorithm that takes an uncalibrated forecaster as input and provably outputs a threshold-calibrated forecaster. Third, we show that empirically, threshold calibration is a practical solution; in two real-world settings and a suite of benchmark regression tasks, we find that threshold calibration minimizes the reliability gap across decision makers with different threshold loss functions while achieving similar or improved decision loss compared to the baselines.

heading: 2 Preliminaries

heading: 2.1 Notation and Forecasting Setup

text:
We consider the regression setup with a feature space X and a label space Y ⊂ R. The input is a random variable X ∈ X and the label is a random variable Y ∈ Y. We use capital letters to denote random variables X,Y and lower case letters to denote their values x, y.
Let F(Y) be the space of cumulative distribution functions (CDFs) over Y. A forecaster h : X → F(Y) is a function that maps an input from the feature space to a CDF on Y . In other
words, given a fixed input x ∈ X , the forecaster outputs the predicted CDF h[x] ∈ F(Y). Ideally, the forecaster aims to predict the CDF of Y given X .
To further clarify the notation, for a fixed input-label pair (x, y) ∈ X × Y , h[x] is a CDF over the predicted label values and h[x](y) ∈ [0, 1] is the value of the CDF h[x] at the point y. We note that h[X] is a random variable that takes values in F(Y) and h[X](Y ) is a random variable that takes values in [0, 1].
Let h∗[X] be the true conditional CDF of Y given X . We use ∼ to denote the distribution of a random variable. We have that Y ∼ h∗[X]. We introduce a new random variable Ỹ to represent a label distributed according to the h[X], the forecasted conditional distribution, so Ỹ ∼ h[X].

heading: 2.2 Decision-Making

text:
Let A be a countable action space. A decision rule δ : X → A is any map from an input x (e.g. a current patient’s attributes) to an action a (e.g. admit a new patient). We assume that a decision maker has a loss function ` : X ×Y ×A → R, describing the loss incurred when choosing an action a on an input-label pair (x, y). Because the labels y are unobserved, the decision maker often wants to minimize their expected loss assuming that the labels are distributed according to the forecasted distribution. As a result, they use the Bayes decision rule with respect to h.
Definition 1 (Bayes Decision Rule). Given a space of decision rules ∆, the Bayes decision rule with respect to the forecaster h is the decision rule in ∆ that minimizes the expected loss under the forecasted distribution
δ∗h = arg inf δ∈∆ EXEỸ∼h[X][`(X, Ỹ , δ(X))]]

heading: 2.3 Threshold Decisions

text:
We focus on the setting where the decision maker aims to minimize a threshold loss function. The action space A consists of two actions so A = {0, 1}. A threshold loss function ` is defined as follows
`(x, y, a) = ∑
i∈{0,1}
c1,iI(y ≤ y0, a = i) + ∑
i∈{0,1}
c0,iI(y > y0, a = i),
where ci,j ∈ R. The ci,j’s denote decision costs, costs associated with different outcome-action pairs, and y0 is a decision threshold. Let L be the space of threshold loss functions, which are all losses of this form with any ci,j ∈ R and y0 ∈ R. Given a threshold loss function `, the decision maker can use the Bayes decision rule δ∗h in Definition 1 to select which action to take. We show that the resulting decision rules always take the form of
δ∗h(x) = I(h[x](y0) ≥ α) or δ∗h(x) = I(h[x](y0) ≤ α)
for some parameters α ∈ [0, 1] and y0 ∈ Y that depends on the loss function (proved in Appendix B). We call such decision rules threshold decision rules because intuitively, they choose the action based on whether h[x](y0) is greater (or less) than a threshold α. We denote the space of such decision rules as ∆h. Since the decision maker’s loss function is a threshold loss function, the decision maker can restrict the space of decision rules they consider to threshold decision rules on the forecasted CDFs.

heading: 3 Reliable Decision-Making with Threshold Calibration

heading: 3.1 Problem Setup

text:
Forecasts are often produced by one group, such as machine learning practitioners or scientists, and consumed by another, such as policy makers or private agents [14]. Motivated by this paradigm, we model these two entities separately:
1. A forecaster h takes inputs x ∈ X and produces CDFs h[x] over the possible outcomes in Y. The provider of h does not know the specific downstream tasks for which h is used.
2. A decision maker has a dataset of unlabeled inputs D = {xi}ni=1, binary action space A = {0, 1}, and a threshold loss function ` ∈ L of interest. The decision maker must take an action ai ∈ A for each unlabeled input xi. The decision maker uses the forecaster h to select {ai}ni=1 because (1) the decision maker does not have enough labeled data to build their own model locally or (2) building the model requires a domain expert.
Multiple decision makers may rely on the same forecaster but have different loss functions. Further, a decision maker’s loss function can change if their decision costs or decision threshold change. In this setting, we identify the conditions on h that the provider can enforce to ensure reliable decision-making under threshold decisions.

heading: 3.2 Reliability Gap

text:
Decision makers often need to accurately estimate the average decision loss incurred under a decision rule prior to deployment. To quantify the accuracy of these decision loss predictions, we define the reliability gap. Definition 2 (Reliability Gap). Given a forecaster h, we define the the reliability gap γ(δ, `) of a particular decision rule δ under a loss function ` as
γ(δ, `) = |EXEỸ∼h[X][`(X, Ỹ , δ(X))]− EXEY∼h∗[X][`(X,Y, δ(X))]|.
The first term in the equation is the average decision loss predicted by the forecaster. Under the forecasted distribution, the labels Ỹ are distributed according to h[X]. As a result, the first term does not depend on the true labels and can be computed by the decision maker using the unlabeled data prior to deployment. The second term is the true average decision loss. Under the true conditional distribution, the labels Y are distributed according to h∗[X]. So, the second term can be thought of as the loss that is incurred at test-time. One caveat is that the reliability gap quantifies the reliability of average decision loss prediction and obtaining zero reliability gap does not imply any instance-based guarantees for individual decisions.
When the forecaster perfectly matches the true distribution (i.e. h = h∗), we have γ(δ, `) = 0 for any decision rule δ and any loss function `. However, in practice, we cannot assume that the forecaster predicts the true distribution. In addition, we would like the forecaster to be applicable for different downstream decision makers. As a result, we study the necessary and sufficient conditions on the forecaster that guarantee zero reliability gap for any threshold decision on the forecasted CDFs and any threshold loss function.

heading: 3.3 Threshold Calibration

text:
We define the property of threshold calibration and show that it is necessary and sufficient to ensure zero reliability gap under any threshold decision on the forecasted CDFs and any threshold loss function. The lemma and theorem in this section are proven in Appendix B.
We define the property of threshold calibration below. Definition 3 (Threshold Calibration). A forecaster h satisfies threshold calibration if
Pr[h[X](Y ) ≤ c | h[X](y0) ≤ α] = c ∀y0 ∈ Y, α ∈ [0, 1],∀c ∈ [0, 1]. (1)
A threshold-calibrated forecaster is average-calibrated on subsets of the predicted CDFs that satisfy h[X](y0) ≤ α.We make the following observation about conditioning on the complementary predicted CDFs. Lemma 1. Given a forecaster h that satisfies Definition 3, then we have that ∀y0 ∈ Y, α ∈ [0, 1],∀c ∈ [0, 1],Pr[h[X](Y ) ≤ c | h[X](y0) > α] = c.
In a threshold decision task, a decision maker will take action a given inputs with predicted CDFs satisfying h[X](y0) ≤ α (and take a complementary action given inputs with predicted CDFs satisfying h[X](y0) > α). Intuitively, threshold calibration ensures that the forecaster satisfies average calibration on the subsets of predicted CDFs where the decision maker chooses a = 0 and a = 1.
Threshold calibration is a specific type of group calibration [28], where calibration across the collection of groups G = {(X,Y ) ∈ X ×Y | h[X](y0) ≤ α}y0∈Y,α∈[0,1] is desired. Since threshold calibration requires achieving calibration on intersecting groups, it is also related to the notion of multicalibration [18]. In Section 4, we give an efficient algorithm for achieving threshold calibration that is inspired by previous work on multicalibration.
Using Definition 3 and Lemma 1, we define the threshold calibration error (TCE) to measure deviation from threshold calibration at a threshold y0 ∈ Y and quantile α ∈ [0, 1]. Definition 4 (Threshold Calibration Error).
TCE(h, y0, α) = ∫ 1
0
|Pr[h[X](Y ) ≤ c | h[X](y0) ≤ α]− c| dc
+ ∫ 1 0 |Pr[h[X](Y ) ≤ c | h[X](y0) > α]− c| dc.
Threshold calibration is a desirable property due to its connection to achieving zero reliability gap.
Theorem 1. Let L be the space of threshold loss functions. Given a forecaster h, let ∆h be the space of threshold decision rules on the forecasted CDFs of h. A forecaster h satisfies threshold calibration if and only if γ(δ, `) = 0 ∀δ ∈ ∆h,∀` ∈ L.
We obtain this result by observing that the expected decision loss under the true distribution can be decomposed into two terms. The first term corresponds to the cost incurred from “false positive” errors and the second term corresponds to the cost incurred from “false negative” errors. Under threshold calibration, the forecaster’s predicted error rates match the true error rates. Since the decision loss (with any choice of costs) is a linear combination of these error rates, the expected decision loss predicted by the forecaster matches the expected decision loss under the true distribution. Thus, under a threshold-calibrated forecaster, we achieve zero reliability gap under any threshold decision on the forecasted CDFs and any threshold loss function.

heading: 3.4 Comparison to Existing Calibration Definitions

text:
We compare threshold calibration to other methods for calibrating probabilistic forecasts. Average calibration is the standard definition of calibration for regression [23, 12].
Definition 5 (Average Calibration). A forecaster h satisfies average calibration if
Pr[h[X](Y ) ≤ c] = c ∀c ∈ [0, 1].
In other words, a forecaster is average-calibrated if the true label Y is below the c-th quantile of the forecasted CDF h[x] exactly c percent of the time.
In contrast, distribution calibration is a much stronger definition of calibration [31]. Intuitively, distribution calibration requires a forecaster to be calibrated for every distribution in the forecaster’s model family.
Definition 6 (Distribution Calibration). A forecaster h satisfies distribution calibration if
Pr[h[X](Y ) ≤ c | h[X] = g] = c ∀g ∈ F(Y),
where F is space of CDFs corresponding to the forecaster’s model family.
We outline the relationship between average, threshold, and distribution calibration in the following proposition.
Proposition 1. If a forecaster satisfies distribution calibration, then it satisfies threshold calibration. If a forecaster satisfies threshold calibration, then it satisfies average calibration.
We note that the converses of the statements in Proposition 1 are not necessarily true. A thresholdcalibrated forecaster does not necessarily satisfy distribution calibration. An average-calibrated forecaster does not necessarily satisfy threshold calibration or distribution calibration (see Appendix C). This implies that an average-calibrated forecaster does not satisfy the necessary condition of Theorem 1, meaning that the reliability gap under threshold decisions may not be zero. So, decision
makers who rely on a forecaster that only satisfies average calibration (but not threshold calibration) are not guaranteed to accurately estimate their decision loss under threshold decisions.
From Proposition 1, we have that a distribution-calibrated forecaster satisfies the necessary condition of Theorem 1. However, distribution calibration can be challenging to achieve in practice because the same CDF is rarely predicted more than one time on the training samples, making it difficult to guarantee calibration without compromising the sharpness of the forecasts. Sharpness corresponds to the width of the prediction intervals generated from the forecasts, and sharp forecasts yield short prediction intervals. Although distribution calibration is theoretically guaranteed to yield zero reliability gap, we observe that achieving distribution calibration is challenging when the model family is complex (Section 5).
Finally, we emphasize the threshold calibration is exactly the condition needed to guarantee the reliability gap is zero in Theorem 1.

heading: 4 Achieving Threshold Calibration

text:
We design a recalibration algorithm that takes an uncalibrated forecaster as input and provably outputs a threshold-calibrated forecaster. Our algorithm is an iterative procedure that terminates when the maximum TCE is less than a user specified threshold . Our key result is that the algorithm must terminate after O(1/ 2) iterations.
Pseudo-code for the algorithm is shown in Algorithm 1. Intuitively, at each iteration of the algorithm, we find the yt0 and α
t where the TCE in Definition 4 is maximized. This partitions the input X into two parts: those where h[x](yt0) ≤ αt and those where h[x](yt0) > αt. For each partition, we use a standard recalibration algorithm (Isotonic regression [23]) to achieve average calibration. Intuitively, after the recalibration step, the forecaster should satisfy average calibration for each partition, and hence the TCE in Definition 4 must be (close to) 0 for yt0 and α
t. We repeat this procedure until the TCE is less than for every possible y0 and α.
Algorithm 1: Threshold Recalibration 1 Input: Forecaster h : X → F(Y), maximum error > 0 2 Output: A threshold-calibrated forecaster 3 Set h0 ← h 4 for t = 1, 2, · · · until maximum threshold calibration error supy0,α TCE(h
t−1, y0, α) ≤ do 5 Find the y0 and α that maximize threshold calibration error.
yt0, α t ← arg sup (y0,α)∈Y×[0,1] TCE(ht−1, y0, α)
6 Partition input features X into X0 ← {x ∈ X | ht−1[x][yt0] ≤ αt} and X1 = X \ X0. 7 Use Isotonic regression to learn recalibration maps φt0, φ t 1 : F(Y)→ F(Y) on X0 and X1 respectively. 8 Apply the recalibration map to obtain new prediction functions.
ht[x]← { φt0(h
t−1[x]) if x ∈ X0 φt1(h
t−1[x]) otherwise 9 end
10 return hT where T is the final iteration count.
The following theorem shows that our iterative threshold calibration procedure converges in a small number of iterations. The intuition of the proof is that after each iteration, the L2 distance between the prediction functions h and the true CDF h∗ must decrease by at least 2. Therefore, the algorithm must terminate before the L2 distance decreases below 0 (which is impossible). A full proof is provided in Appendix B. Theorem 2. Algorithm 1 converges after at most O(1/ 2) iterations and outputs a forecaster with threshold calibration error at most .
For simplicity, we do not consider finite sample approximation of the TCE in line 5 of Algorithm 1. Line 5 can be interpreted in two ways: line 5 estimates the TCE on the true distribution (which we can only do with infinite samples), or on the empirical distribution (i.e. the uniform distribution on
the recalibration data). Under the former interpretation, Theorem 2 holds assuming that line 5 can estimate the true TCE (which is the ideal scenario with infinite data). Under the latter interpretation, Theorem 2 holds for the empirical distribution, i.e. it guarantees that Algorithm 1 will output a forecaster with threshold calibration error at most on the empirical distribution rather than the true distribution. We will instead use experiments to show that Algorithm 1 can generalize to the true distribution. Note that under both interpretations, Algorithm 1 will converge after at most O(1/ 2) iterations. For completeness, we describe the finite sample version of the algorithm in Appendix A.

heading: 5 Experiments

text: In the following experiments, we demonstrate that threshold calibration can minimize the reliability gap (1) across a range of decision costs, (2) across a range of decision thresholds, and (3) in simple and complex model families. Across all datasets and forecaster model families that we consider, we find that threshold calibration outperforms the baselines in reducing the size of the reliability gap while attaining similar or improved decision loss compared to the baselines.

heading: 5.1 Datasets

text:
We consider datasets that relate to real-world decision-making tasks and standard benchmarks. In the main paper, we show results on the UCI Protein and the MIMIC-III datasets. All remaining results can be found in Appendix A.
MIMIC-III. Patient length-of-stay predictions are used for hospital scheduling and resource management [17]. We consider a patient length-of-stay forecaster trained on patient admission laboratory values from the MIMIC-III dataset [20]. In our decision task, the hospital decides to schedule a new patient for an elective procedure if a current patient is predicted to have a short length of stay.
Demographic and Health Survey (DHS). Local wealth measurements are used to inform resource allocation decisions. We use the DHS data from Sheehan et al. [30] to predict asset wealth from satellite images as done in Yeh et al. [32] and Sheehan et al. [30]. Our experimental setup is motivated by the decision task defined in Yeh et al. [32], where aid is allocated to regions where the predicted asset wealth falls below a particular threshold.
UCI Regression Datasets. We evaluate on a suite of UCI regression datasets (Naval, Protein, Energy, Crime) [11]. They are common benchmarks in the uncertainty quantification literature [31, 2, 8, 23].

heading: 5.2 Experimental Setup and Baselines

text:
Experimental Setup. We consider a forecaster that outputs Gaussian distributions and a forecaster that outputs Gaussian-Laplace mixture distributions. We use a train/validation/test split. The uncalibrated forecaster is a neural network trained on the training set with the validation set used for early stopping. For large datasets (Protein, Energy, Naval, MIMIC-III), the recalibration transform is trained on the validation set. For small datasets (Crime, DHS), the recalibration transform is trained on the training and validation set. On the test set, we evaluate our method and the baselines using decision-making metrics (Section 5.3). Calibration metrics are also measured and results are provided in Appendix A.
Baselines. We compare the uncalibrated forecaster to the forecaster after enforcing average, threshold, or distribution calibration through a posthoc recalibration procedure. Methods for achieving these properties are described in Appendix A.

heading: 5.3 Decision-Making Metrics

text:
We simulate decision makers enumerated i = 1, 2 . . .M who use a probabilistic forecaster h for their threshold decision tasks. We assume that there is no cost associated with true positives or true negatives, and the total cost of a false positive plus a false negative is equal to 10 for all decision makers. As a result, decision maker i’s task is determined by a decision threshold yi0 and decision cost ratio ci. Each decision maker has a loss function `i(x, y, a) = 10ciI(a = 1, y ≥ yi0) + 10(1− ci)I(a = 0, y < yi0) and a decision rule
δih,α(x) = 1(h[x](y i 0) ≥ α). We consider decision makers with (yi0, ci) ∈ Y0 × C where Y0 and C each consist of 50 uniformly spaced points that span the label space and [0.05, 0.95], respectively.
For each decision maker i, we compute the decision loss (the loss incurred by the Bayes decision rule δ∗,ih (X)) and the reliability gap (averaged over the possible threshold decision rules).
Decision Loss = EXEY∼h∗[X][`i(X,Y, δ∗,ih (X))] Reliability Gap = 1 |C| ∑ α∈C |γ(δih,α, `i)|.
Aggregate statistics can be obtained by averaging over all M decision makers, all decision makers who share the same threshold y0, or all decision makers who share the same cost ratio c.

heading: 5.4 Results

text:
Using the MIMIC-III and UCI Protein datasets, we study the effect of recalibration on the reliability gap and the decision loss achieved by decision makers with different decision thresholds and cost ratios. Furthermore, we examine the effect of recalibration on forecasters that output CDFs from simple (Gaussian) and complex (Gaussian-Laplace mixture) model families.
Threshold Calibration Minimizes Reliability Gap Across Decision Thresholds. We evaluate the effect of recalibrating the Gaussian forecaster on decision makers with different decision thresholds. On both datasets, threshold calibration yields the largest decrease in the reliability gap (left plots, Figure 2). Distribution calibration also decreases the reliability gap across decision thresholds, relative to the uncalibrated Gaussian forecaster. Average calibration does not consistently reduce the reliability gap; on the UCI Protein dataset, the reliability gap of the average-calibrated forecaster enjoys a slight decrease at some decision thresholds but is increased at others, relative to the uncalibrated Gaussian forecaster (middle left, Figure 2). Lastly, these calibration methods achieve similar decision loss to the uncalibrated forecaster (right plots, Figure 2). These trends are consistent with the results obtained on the other datasets under the Gaussian forecaster. Threshold calibration outperforms baselines across different decision thresholds under the Gaussian-Laplace forecaster, as well (Appendix A).
Threshold Calibration Minimizes Reliability Gap Across Decision Cost Ratios. Across decision makers with different cost ratios, distribution and threshold calibration reduce the reliability gap relative to the uncalibrated forecaster, with threshold calibration yielding the largest decreases in the reliability gap (left plots, Figure 3). Meanwhile, average calibration does not consistently reduce the reliability gap; on the UCI Protein dataset, it achieves similar reliability gap to the uncalibrated forecaster (middle left, Figure 3). As before, these calibration methods achieve similar decision loss to the uncalibrated forecaster (right plots, Figure 3). These trends are consistent with results obtained on the other datasets under the Gaussian forecaster. Threshold calibration outperforms baselines across different decision cost ratios under the Gaussian-Laplace forecaster, as well (Figure 4).
Distribution Calibration Degrades Performance under Complex Model Families. Forecasters that can output CDFs from more flexible model families (e.g. Gaussian-Laplace mixture distributions)
0.25 0.50 0.75 Decision Cost Ratio
0.025
0.050
0.075
0.100
0.125
0.150
Re lia
bi lit
y Ga
p
MIMIC-III Patient Length-of-Stay
None Average Threshold Distribution
0.25 0.50 0.75 Decision Cost Ratio
0.05
0.10
0.15
0.20
0.25
Re lia
bi lit
y Ga
p
UCI Protein
0.25 0.50 0.75 Decision Cost Ratio
0.1
0.2
0.3
Tr ue
D ec
isi on
L os
s
MIMIC-III Patient Length-of-Stay
0.25 0.50 0.75 Decision Cost Ratio
0.2
0.4
0.6
Tr ue
D ec
isi on
L os
s
UCI Protein
Figure 3: Under the Gaussian forecaster and across different decision cost ratios, threshold calibration reduces the reliability gap on both datasets while average calibration does not reduce the reliability gap on the Protein dataset (Left, Middle Left), and all calibration methods yield improved or comparable decision loss compared to the uncalibrated forecaster (Middle Right, Right). Error bars represent 95% confidence intervals and are generated over 6 random trials.
0.25 0.50 0.75 Decision Cost Ratio
0.025
0.050
0.075
0.100
0.125
Re lia
bi lit
y Ga
p MIMIC-III Patient Length-of-Stay None Average Threshold Distribution
0.25 0.50 0.75 Decision Cost Ratio
0.05
0.10
0.15
0.20
Re lia
bi lit
y Ga
p
UCI Protein
0.25 0.50 0.75 Decision Cost Ratio
0.1
0.2
0.3
Tr ue
D ec
isi on
L os
s
MIMIC-III Patient Length-of-Stay
0.25 0.50 0.75 Decision Cost Ratio
0.2
0.4
0.6
Tr ue
D ec
isi on
L os
s
UCI Protein
Figure 4: We consider the effect of recalibrating the Gaussian-Laplace forecaster under a range of decision cost ratios. Threshold calibration reduces the reliability gap while distribution calibration can enlarge the reliability gap (Left, Middle Left). Average and threshold calibration achieve comparable or lower decision loss as the baseline forecaster, while distribution calibration increases the decision loss. Error bars represent 95% confidence intervals and are generated over 6 random trials.
may be able to better capture the true conditional distribution of Y given x compared to Gaussian forecasters. As a result, we examine the effect of the recalibration procedures when the uncalibrated forecasts follow a more flexible distribution. The uncalibrated Gaussian-Laplace forecaster (Figure 4) yields a smaller reliability gap and smaller decision loss compared to the uncalibrated Gaussian forecaster (Figure 3). Applying threshold calibration to the Gaussian-Laplace forecaster further reduces the reliability gap. However, under the Gaussian-Laplace forecaster, distribution calibration enlarges the size of the reliability gap and increases the decision loss. Although distribution calibration is theoretically guaranteed to minimize the reliability gap, it is challenging to achieve in finite samples without compromising the sharpness of the forecasts (in our case, decision loss). So, we find that decision loss and reliability gap increase. We hypothesize that the recalibration dataset may not contain many instances that yield similar distribution parameters, so the recalibration transform does not generalize well to unseen data. We also observe these trends the UCI Crime, UCI Energy, and DHS datasets.

heading: 6 Related Work

text:
Forecasting and Decision Making. The connection between forecasts and decision making was first studied in economics [1, 29]. The development of Bayesian decision analysis connected topics of forecasts and decision-based loss functions [10, 4]. Decision-making under uncertainty with probabilistic forecasts was then studied in econometrics [7]. [19] also considers learning regression functions that minimize a decision loss. While [19] focuses on transforming the predicted CDF to a point prediction, our method focuses on transforming the predicted CDF into a new CDF. [19] also requires knowing the loss function to learn the transformation, while our method assumes that the loss function belongs to a commonly used function family (threshold loss functions).
Calibration. Calibration definitions have been studied in the statistics literature [5, 6, 26]. For the regression setting, methods for ensuring that machine learning models satisfy average calibration
have been studied in [23, 8]. In addition, methods for achieving stronger calibration notions have also been introduced such as distribution calibration [31] and individual calibration [34]. Calibration and trustworthy predictions in the medical domain are also studied in [16]. [16] introduces the notion of D-calibration, which is related to our average calibration baseline, but is tailored to the survival analysis task. A perfectly average calibrated prediction function is also D-calibrated, and vice versa.
Multicalibration. Our definition of threshold calibration is most related to the line of work on multicalibration [18, 21]. Given a large collection G of potentially intersecting groups of the data, a predictor is multicalibrated on G if it is simultaneously calibrated on every sufficiently large group in G [18]. Previous works give methods for achieving mean and moment multicalibration for predictor functions. Our iterative procedure for achieving threshold calibration is inspired by methods for achieving multicalibration.

heading: 7 Limitations and Societal Impact

text:
Our work demonstrates that certain types of calibration enable decision makers to estimate decision loss before deployment, which should not be confused with enabling decision makers to make optimal decisions. For example, a forecaster that always outputs the marginal distribution of Y is threshold-calibrated but likely incurs high decision loss. Furthermore, posthoc recalibration is limited by the quality of the baseline model. If the baseline model outputs the marginal distribution of Y , then it is already threshold-calibrated but likely is not useful for decision making. Applying our threshold calibration method will not offer any benefit in this case.
Also, our work assumes that predictions of Y do not affect the true label Y . However, when predictions are used to make decisions, they can often influence the outcome they aim to predict [27]. Our work does not account for these performative effects, so the decision loss may not be accurately estimated in these settings. Future work could focus on developing calibration procedures that enable forecasters to be robust to such distribution shifts. In addition, we specifically focus on binary-action threshold decisions. Future work may generalize our results to the setting where decision makers have loss functions involving multiple thresholds and multiple actions.
There is a potential for negative societal impact if threshold calibration is incompatible with fairness criteria. Nevertheless, we note that the perfect predictor (that predicts the true conditional probability) satisfies our calibration definition. Consequently, if the perfect predictor satisfies some fairness notion (such as group calibration), then our calibration definition is also compatible with that fairness notion. Note that the perfect predictor does not satisfy a fairness notion called demographic parity, hence our calibration definition is not compatible with demographic parity either.

heading: 8 Conclusion

text: We show that a threshold-calibrated forecaster theoretically guarantees accurate decision loss estimation under threshold decision losses and threshold decision rules. We provide an iterative procedure for achieving threshold calibration and show that in practice it minimizes the reliability gap relative to baselines without compromising the forecaster’s decision loss. Such estimates permit decision makers to reason about the consequences of their decisions prior to deployment.

heading: Acknowledgements

text: RS is supported in part by a NSF GRFP under grant number DGE-1656518. SZ is supported in part by a JP Morgan fellowship and a Qualcomm innovation fellowship. SE is supported in part by NSF(#1651565, #1522054, #1733686), ONR (N000141912145), AFOSR (FA95501910024), ARO (W911NF-21-1-0125) and Sloan Fellowship. We are grateful for Rishi Bommasani, Kristy Choi, Matthew Jörke, Judy Shen, Rui Shu, Fan-Yun Sun, Rohan Taori, Ke Alexander Wang, Rose Wang, and Henry Zhu for insightful discussions.

title: Reliable Decisions with Threshold Calibration