Testing Calibration in Nearly-Linear Time
Authors: Lunjia Hu
Arun Jambulapati
Kevin Tian
Chutong Yang
Venue: NeurIPS 2024 poster (2024)
Keywords: Calibration
Property testing
Linear programming
Primary area: interpretability_and_explainability
TL;DR: We propose a property testing problem associated with measuring calibration of a predictor, and give a near-linear time algorithm for it based on minimum-cost flow.

Abstract: In the recent literature on machine learning and decision making, calibration has emerged as a desirable and widely-studied statistical property of the outputs of binary prediction models. However, the algorithmic aspects of measuring model calibration have remained relatively less well-explored. Motivated by Blasiok et al '23, which proposed a rigorous framework for measuring distances to calibration, we initiate the algorithmic study of calibration through the lens of property testing. We define the problem of calibration testing from samples where given $n$ draws from a distribution $\mathcal{D}$ on $(\text{predictions}, \text{binary outcomes})$, our goal is to distinguish between the cases where $\mathcal{D}$ is perfectly calibrated or $\epsilon$-far from calibration. We make the simple observation that the empirical smooth calibration linear program can be reformulated as an instance of minimum-cost flow on a highly-structured graph, and design an exact dynamic programming-based solver for it which runs in time $O(n\log^2(n))$, and solves the calibration testing problem information-theoretically optimally in the same time. This improves upon state-of-the-art black-box linear program solvers requiring $\Omega(n^\omega)$ time, where $\omega > 2$ is the exponent of matrix multiplication. We also develop algorithms for tolerant variants of our testing problem improving upon black-box linear program solvers, and give sample complexity lower bounds for alternative calibration measures to the one considered in this work. Finally, we present experiments showing the testing problem we define faithfully captures standard notions of calibration, and that our algorithms scale efficiently to accommodate large sample sizes.

Testing Calibration in Nearly-Linear Time
Lunjia Hu Harvard University lunjiačaluma ummii stanford.cm edu
Arun Jambulapati University Michigan jmblpati @gmail com
Kevin Tian
Chutong Yang University Texas at Austin cyang96@utexas. edu
University of Texas at Austin kjtian utexas edu
Abstract
In the recent literature on machine learning and decision making, calibration has emerged as desirable and widely-studied statistical property of the outputs of binary prediction models. However, the algorithmic aspects of measuring model calibration have remained relatively less well-explored. Motivated by [BGHN23a], which proposed a rigorous framework for measuring distances calibration, we initiate the algorithmic study of calibration through the lens of property testing. We define the problem of calibration testing from samples where given n draws from a distribution D on (predictions, binary outcomes), our goal is to distinguish between the cases where 'D is perfectly calibrated or E-far from calibration. We make the simple observation that the empirical smooth calibration lincar program can be reformulated as an instance of minimum-cost flow on a highly-structun solver for it which runs
graph, and design exact dynamic programming- in time (n log"(n)) and solves the calibration testing problem information- theoretically optimally the same time. This improves upon state-of-the-art black-box linear program solvers requiring 2(n") time, where exponent of matrix multiplication. We also develop algorithms for tolerant variants of our testing problem improving upon black- -ox linear program solvers, and give sample complexity lower bounds for alternative calibration measures to the considered in this work. Finally, present experiments showing the testing problem we define faithfully captures standard notions of calibration, and that our algorithms scale efficiently to accommodate large sample sizes.
2 is the
Introduction
Probabilistic predictions are at the heart of modern data science. In domains as wide-ranging as forecasting (e.g. predicting the chance of rain from meteorological data [MW84, Mur98]), medicine (e.g. assessing the likelihood disease [Doi07]), computer vision (e-g. assigning confidence values for categorizing images [VDDP17]). and more (e.g. speech recognition [AAA+ + 16] and recommender systems [RRSK11]), prediction models have by now become essential components of the decision- making pipeline. Particularly in the context of critical, high-risk cases, the interpretability of prediction models is therefore paramount in downstream applications. That is, how do we assign meaning to the predictions our model gives us, especially when the model is uncertain?
We focus on perhaps the most ubiquitous form prediction modeling: binary predictions, represented as tuples (v, y) in [0, 1] x {0, 1} (where the coordinate is our prediction of the likelihood of an event, and the y coordinate the observed outcome). We model prediction-outcome prediction setting by joint distribution 'D over [0, 1] (0, 1), fixed in the following discussion. In
pairs in the binary
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

this context, calibration of a predictor has emerged as basic desideratum. A prediction-outcome distribution D said be calibrated if
E(r.))>Dyy
t] t for all & E [0, 1/.
(I)
That is, calibration asks that the outcome is 1 exactly 60% of the time, when the model returns prediction v = 0.6. While calibration (or approximate variants thereof) is a relatively weak require- ment meaningful predictor, as it can be achieved by simple models," it can still be significantly violated in practice. For example, interest in calibration spurred by [GPSW17], 17], which observed that many modern deep learning models are far from cali- brated. Moreover, variants of calibration have been shown to have strong postprocessing properties for fairness constraints and loss minimization [HKRRI8, 18, DKR 21, GKR 22], which has garnered renewed interest in calibration by the theoretical computer science and statistics communities.
the machine learning community was
The question of measuring the calibration of distribution is subtle; incurs measurement error due to sampling. For example, consider the expected calibration error, used in e.g. [NCH15, GPSW17, MDR 21a, RT21b] as a ground-truth measure of calibration:
a calibrated distribution
ECE(D) := (v.a))> (v w)~D ly v' = =-==]] =/|
Unfortunately, the empirical ECE we will almost surely only observe single sample with each e value. Further, [KF08] observed that ECE is discontinuous in v. In practice, binned variants of ECE are often used as a proxy, where a range of is lumped together in the conditioning event. However, hyperparameter choices (c.g. the number of bins) can significantly affect the quality of binned ECE variants as a distance measure [KLM19, NDZ 19, MDR + 21 Moreover, as we explore in this paper, binned calibration measures inherently suffer from larger sample complexity-Be toay--tt-ccuracy tradeoffs, and are less faithful to ground truth calibration notions experiments than the calibration measures we consider.
is typically meaningless; if the marginal density of is continuous,
Recently, [BGHN23a] undertook a systematic study of various measures of distance to calibration proposed in the literature. They proposed information-theoretii tractability in the prediction-only access (PA) model, where the calibration measure definition can only depend on the joint prediction- outcome distribution (rather than the features of training examples), as desirable criterion for calibration measures. Correspondingly, [BGHN23a] introduced Definition as a ground notion for measuring calibration in the PA model, which also adopt in this work." 4
Definition (Lower distance to calibration). Let 'D be distribution over [0, x (0, distance to calibration (LDTC) of D, denoted dCE(D), is defined by
1). The lower
dCE(D) : inf [LEex((D)
(( |u vl,
where ext(D) is all distributions II over (u, v.y) E (0, 1] [0,1] x (0,1) satisfying the following.
The marginal distribution of (v. v) is D.
The marginal distribution (u, y) is perfectly calibrated. i.e. Enfy|uu = u.
Definition 1 has various beneficial aspects: it is convex in v, computable in the PA model, and (as shown by [BGHN23a]) polynomially-related to various other calibration measures, including some which require feature access, e.g. the distance calibration (DTC, Eq. (1), [BGHN23al). Roughly, the DTC of a distribution is the tightest lower bound on the E distance between v and any calibrated function of the features, after taking features into account. The LDTC the analog of this feature-aware measure of calibration when limited to the PA model, so it does not depend on features. We focus on Definition as our ground-truth measure in the remainder of the paper.
'The predictor which ignores features and always return the population mean calibrated, for example. Forr example, [NDZ* 19] observed that, in their words, "dramatic differences in bin sensitivity" can occur "depending properties of the (distribution) hand," sentiment echoed by Section 5 of [MDR* 21a].
"This access model is practically desirable hecause abstracts away the feature space, which can lead to significant memory savings when our goal is only to test the calibration of model predictions. Moreover, this matches conventions in the machine learning literature, e.g. loss functions are typically defined in the PA model.
*We note that [BGHN23a] introduced an upper distance to calibration, also defined in the PA model, which they showed is quadratically basic properties such continuity, making it less amenable estimation and algorithm design.
to the dCE in Definition 1. However, the upper distance does not satisfy

---

1.1 Our results
We initiate the algorithmic study of the calibration testing problem, defined as follows.
Definition (Calibration testing). Let 10, 1]. We say algorithm A solves the e-calibration testing problem with n samples, given n i..d. draws from a distribution over [0, 1] x {0, 1). A returns either "yes" or "no" and satisfies the following with probability 2.5 3'
.A returns "no" (D) 2 E.
retuurs "yes" (D) =
In this case, also call A an E-calibration tester.
To our knowledge, we are the first to formalize the calibration testing problem in Definition 2, which is natural from the perspective of property testing, an influential paradigm in statistical learning [Ron08, Ron09, Gol17]. J. In particular, there is an En (n-1/22 so that it is information- theoretically impossible to solve the E, ca-caiiiattoon testing problem from n samples (see Lemma 5), so variant of Definition 2 with exact distinguishing threshold between rcalibrated/uuealiibrteed is not tractable. Hence, Definition 2 only requires distinguishing distributions D which are "clearly uncalibrated" (parameterized by threshold E) from those which are perfectly calibrated.
We note that a variant of Definition 2 where dCE is replaced by variants of the ECE was recently proposed by [LHHD223.. However, due to the aforementioned discontinuity and binning choice issues which plague the ECE, [LHHD23] posed as an explicit open question whether an alternative calibration metric makes for more appropriate calibration testing problem, motivating our Defini- tion 2. Indeed, Proposition of [LHHD23] shows that without smoothness assumptions on the data distribution, it is impossible to solve the ECE calibration testing problem from finite samples. 6
Our first algorithmic contribution is a nearly- time algorithm for calibration testing.
Theorem Let n E N, and e = (en), where e. = On -1/2) is minimal such that is information- theoretically possible to solve the en -calibration testing problem (Definition 2) with samples. There an algorithm which solves the E-calibration testing problem with n samples, running in time O(n log (n)).
The lower bound on the acceptable range of e. in Theorem is well-known, and recalled in Lemma 5 for completeness. Our main contribution is to prove the upper bound (i.e., achieving ((ex)-calibration testing) in Theorem by designing new algorithm for computing smCE(D,,). the smooth calibration error (Definition 3), an alternative calibration measure, of an empirical distribution D',.
functiis Definition (Smooth calibration error). Let W be the set of Lipschitz functions w [0, 1] + 1-
The smooth calibration error of distribution DD over [o, 1] {0, 1}, denoted smCE(D), is
smCE(D)
sup [((ey)) (1 v)w(vi]l- wEW
It was shown in [BGHN23a] that smCE(D) is constant-factor approximation to dCE(D) for all D on [o, 1] x {0. 1} (see Lemma 4). Additionally, the empirical smCE admits a representation as a linear program with an (n)) (nn)-sized constraint matrix encoding Lipschitz constraints." Thus, [BGHN23a] proposed a simple procedure for estimating smCE(D): draw n samples from D, and solve the associated linear program the empirical distribution. While there have been significant recent runtime advances in the linear programming literature [LS14, CLS21, vdBLSS20, vdBLL+21] all state-of-the-art black-box linear programming algorithms solve linear systems involving the constraint matrix, which takes 2(n²)) time, where w > 2.371 [WXXZ23] is the current exponent of
As is standard in property testing problems, the success probability of either calibration tester or tolerant calibration tester he boosted 1 8 for any 8 E (0. 1) at k O(lg(( +)) overhead in the sample complexity. This because we can independently call & copies of the tester and output the majority vote, which succeeds with probability 2 1 - 5 by Chernoff bounds, so we focus on = 3-
focus on binary classification = 2), which we believe an exciting future direction. However. their Proposition holds even when 2. FFrmaally the number of constraints in the smCE linear program is O but we show that in the hard- constrained setting, requiring that "adjacent" constraints are met suffices (see Lemma 1).
'The work [LHHD23] considered k-class prediction tasks, extending
3

---

matrix multiplication. Even under the best-possible assumption that w = 2. the strategy of exactly solving linear program represents an ((2") quadratic runtime barrier for calibration testing.
We bypass this barrier by noting that the smCE linear program is highly-structtred. and can be reformulated as minimum-cost flow a planar graph. We believe this observation is already independently interesting, as it opens the door to using powerful software packages designed for efficiently solving flow problems measure calibration in practice. Moreover, using recent theoretical breakthroughs in graph algorithms 22, CKL*22] as a black box, this observation readily implies an (n polylog(n)) --tme time algorithm for solving the smooth calibration linear program.
However, these aforementioned algorithms are quite complicated, and implementations in practice are not available, leaving their relevance to empirical calibration testing unclear at the moment. Motivated by this, in Section we develop a custom solver for the minimum-cost flow reformulation of empirical smooth calibration, based on dynamic programming. Our theoretical runtime improvement upon [DGG+22, 22, CKL,+22] is by at least a large polylogarithmic factor, and moreover our algorithm simple enough to implement in practice, where attains faster runtimes than general- purpose commercial solvers on moderate or large dataset sizes, evaluated in Section 3.
We further define tolerant variant of Definition 2 (see Definition 4), where we allow for error thresholds in both the "yes" and "no" cases; "yes" is the required answer when dCE(D) I E2, and "no" is required when dCE(DD 2 E1. Our algorithm in Theorem 1 continues to serve as efficient tolerant calibration tester when E1 2 4E2, formally stated in Theorem 3. This constant-factor loss comes from similar loss in the relationship between smCE and dCE, see Lemma 4. We make the observation that a constant factor loss in the tolerant testing parameters is inherent following this strategy, via lower bound in Lemma 13. Thus, even given infinite samples, computing the smooth calibration error cannot solve tolerant calibration testing all the way down to the iofommation-thooreee threshold ě 2 82. To develop an improved tolerant calibration tester, we directly show how to approximate the LDTC of an empirical distribution, our second main algorithmic contribution.
Theorem 2 (Informal, see Theorem 4, Corollary 3). Letn E N, and let &1 C2 = (EE)), where en, (n21 is minimal such that it is testing problem (Definition 4) with n samples. There is an algorithm which solves the (2),,a))tlleann
possible to solve the En En-calibration
calibration testing problem with n samples, rumning in time O Alg(nn) = O log(n)).
While Theorem 2 slower than Theorem 1, it directly approximates the LDTC, making it applicable to tolerant calibration testing. We mention that state-of-ther ohetthe-rt black-box linear programming based solvers, while still applicable to (a discretizeation of) the empirical LDTC, require 2(n2.) time [vdBLL+21], even if w = 2. This is because the constraint matrix for the s-approximate empirical LDTC linear program has dimensions ( x O(z), resulting in an R 1 = (VV))) overhead in the dimension of the decision variable. We prove Theorem 2 in Appendix C, where we use recent advances in minimax optimization [JT23] and a custom combinatorial rounding procedure to develop a faster algorithm, improving state-of-the-an linear programming runtimes by an (((n) factor.
In Appendix D, we complement our algorithmic results with lower bounds (Theorems 5, 6) on the sample complexity required to solve variants of the testing problem in Definition 2, when dCE replaced with different calibration measures. For several widely-used distances in the machine learning literature, including binned and convolved variants of ECE [NCH15, BN23], we show that O(= 2.5) samples are required to the associated e-calibration testing problem. This demonstrates statistical advantage of our focus on dCE as our ground- trrtt notion for calibration testing.
We corroborate our theoretical findings with experimental evidence on real and synthetic data in Section 3. First, on a simple Bernoulli example, we show that dCE and smCE testers are more reliable measures of calibration than recently-proposee binned ECE variant. We then apply our SmCE tester to postprocessed neural network predictions to test their calibration levels, validating against the findings in PPPSW17.. Finally, we implement our method from Theorem I on our Bernoulli dataset, showing that scales to high dimensions and runs faster than both a linear program solver from CVXPY for computing the empirical smCE, as well as a commercial minimum-cosi flow solver from Gurobi Optimization (combined with our reformulation in Lemma 2).*
*Our code is included in the supplementary material.
4

---

1.2 Our techniques
Theorems and 2 follow from designing custom algorithms for approximating empirical linear programs associated with the smCE and dCE of a sampled dataset D, := {(v,, y1) HejM) Riid. D. In both cases, generalization bounds from [BGHN23a] show it suffices to approximate the value of the empirical calibration measures error (2n=)//), though our solver in Theorem will be exact.
We begin by explaining our strategy for estimating SmCE(D,,) (Definition 3). By definition, the smooth calibration error of D,, can be formulated a linear program,
min x -E[-1.1| (E(m)
Σ (; y;), where [z; - xzن S l0 u,l for all (i, [n]] X [n].
(2)
Here, 34 E [-],1] corresponds to the weight on Vg and there are 2(x) constraints on the decision variable each of which corresponds to Lipschitz constraint. We make the simple observation that every Lipschitz inequality constraint can be replaced by two constraints of the form x; -x; S |0, - (with i,j swapped). Moreover, the box constraints x E [-1,1]" can be handled by introducing a dummy variable In+1 and writing max(æ; xn+1 1, #n++1 m:) S 1, after penalizing In+1 appropriately in the objective. Notably, this substitution makes every constraint the difference of two decision variables, which is enforceable using the edge-vertex incidence matrix of a graph. Finally, the triangle inequality implies that we only need to enforce Lipschitz constraints in (2) corresponding to adjacent j. After making these simplifications, the result is the dual of a minimum-cosi flow problem graph which is the union of a star and a path; this argument is carried out in Lemma 2.
Because of the sequential structure of the induced graph, we show in Appendix B.2 that a dynamic programming- based approach, which maintains the minimum-cost flow value after committing to the first flow variables in the graph recursively, succeeds in computing the value (2). To implement each iteration of our dynamic program in polylogarithmic time, we rely on a generalization of the classical segment tree data structure that we develop in Appendix B.3; combining gives Theorem
On the other hand, the linear program corresponding to the empirical dCE is more complex (with two types of constraints), and our knowledge lacks the graphical structure be compatible with the aforementioned approach. Moreover, it is not obvious how to use first-order methods, an alternative linear programming framework suitable when only approximate answers are needed, to solve this problem more quickly. This is because the empirical dCE linear program enforces hard constraints to a set that is difficult to project to under standard distance metrics. To develop our faster algorithm in Theorem 2, we instead follow an "augmented Lagrangian" method where we lift the constraints directly into the objective as a soft-constrained penalty term. To prove correctness of this lifting, we follow a line of results in combinatorial optimization [She13, JST19]. These works develop "proof-by-rowe bouuddigg algorithm" framework to show that the hard-constrained and soft-constrained linear programs have equal values, summarized in Appendix C. (see Lemma 14).
To use this augmented Lagrangian framework. it remains to develop an appropriate rounding algorithm to the feasible polytope for the empirical dCE linear program, which enforces two types of constraints: marginal satisfaction of (v, 3), and calibration of (u, y) (using notation from Definition 1). In Appendix C.3, we design a two-step rounding procedure, which first fixes the marginals on the (v, v) coordinates, and then calibrates the coordinates without affecting any (v, y) marginal.
1.3 Related work
The calibration performance of deep neural networks has been studied extensively in the literature (e.g. [GPSW17] 17, MDR MDR+211, 21b, R121a, BGHN23bJ). Mcasuring the calibration error in a meaningful way can be challenging, especially when the predictions are not naturally discretized (c.g. in neural networks). Recently, [BGHN23a] addresses this challenge using the distance to calibration as a central notion. the distance to
They consider calibration measure be consistent if it is polynomiall--reattee calibration. Consistent calibration measures include the smooth calibration error [KF04), Laplace kernel calibration error [KSJ18], interval calibration error [BGHN23a], and convolved ECE [BN23].
"The calibration measure we call the convolved ECE in our work was originally called the smooth ECE in [BN23]. We change the name slightly to reduce overlap with the smooth calibration error (Definition 3), central object throughout the paper.
5

---

On the algorithmic front, substantial observations were made by [BGHN23a] on linear programming characterizations of calibration measures such as the LDTC and smooth calibration. While there have been significant advances on the runtime frontier of linear programming solvers, current runtimes for handling an n x d linear program constraint matrix with 2 d remain Q(min((d + d n²)) [CLS21, vdBLL++21 JSW721J. Our constraint matrix is roughly-son -uuurrr- and highly-sparse, so it is plausible that e.g. the recent research on sparse linear system solvers [PV21, Nie22] could apply to the relevant Newton's 's method subproblems and improve upon these rates. Moreover, while efficient estimation algorithms have been proposed by [BGHN23a] for (surrogate) interval calibration error and by [BN23] for convolved ECE, these algorithms require suboptimal sample complexity for solving our testing task in Definition 2 (see Appendix D). To compute their respective distances to error from samples, these algorithms require S2(= 92(=-)) and Q( 9) time. As comparison, under this parameterization Theorems and 2 require Ō and O time, but can solve stronger testing problems with the same sample complexity, experimentally validated in Section 3.
Notation. Throughout, D denotes a distribution over [0, x {0, 1}. When D is clear from context, we let D. = {(v,, y4) [ie) denote a dataset of n independent samples from D and, in a slight abuse of notation, the distribution with probability for each (v:, Vs). We say d is calibration measure if it takes distributions on [0, 1] x {0. to the nonnegative reals R2o. dCE (Definition 1) and smCE (Definition 3) are both calibration measures, We use Ô and to hide polylogarithmic factors in the i i S n1. We denote matrices in boldface throughout, For any A E |R we refer to its 7th row by A; and its jth column by A.g. For a set S identified with rows of matrix A, we let A,: denote the row indexed by E S. and use similar notation for columns. For directed graph G = (V, E"), we define its edge-vertex incidence matrix B E {-1,0, 0, E which has a row corresponding each (u,v) v) E E' with Bed. = 1 and Be = -1. When G is undirected, we similarly define B E (-1,0, Ex with arbitrary edge orientations.
argument. We denote [m] == {i E N
2 Smooth calibration
In this section, we overview our main result on approximating the smooth calibration of distribution on [0, 1] x {0, 1j. deferring some aspects of the proof to Appendix B. We first show that the linear program corresponding to the smooth calibration of an empirical distribution can be reformulated as an instance of minimum-cost flow a highly- structured graph. We then explain our dynamic programming approach to solving this minimum-cos flow problem and state a runtime guarantee. Finally, we give our main result near-linear time calibration testing. Theorem 1.
Throughout this section, we fix a dataset under consideration, D., := ())ee C x 10, and the corresponding empirical distribution (which, in abuse of notation, we also denote D,,) iee. we use (v. y) D, to mean that (v. y) (vi, y:) with probability for each i [n]. We also assume without loss of generality that the {vx Jse[n] are in sorted order, so 0 S in -... S 0n & 1. Recalling Definition 3, the associated empirical smooth calibration linear program is
smCE(D,)) = max 6T =E[-1,11"
where [r, 2z5 S 03 - U2 for all (i. [m] x [m] with <
(3)
1
and b, == - (v. v)) for all i [n]]
We first make a simplifying observation, which shows that it suffices to replace the Lipschitz constraints in (3) with only the Lipschitz constraints corresponding to adjacent indices (i,j). R", where has monotonically nondecreasing coordinates, and |z x+41l= S U/41 - for all i E [n - 1], then [z, I, $ U,- - ut all (i,j) [n] x [n] with < j.
Lemma 1. If
We now reformulate (3) a (variant of a) minimum-cost flow problem.
Lemma 2. Consider an instance of (3). Let G = (V. F) be an undirected graph n + 1 vertices labeled by V := [n+ + 1), and with 2n directed edges E. defined and with edge costs as follows.
For all i E In 1), there is an edge between vertices (i, i + 1) with edge cost u441 Ui.

---

For all i E [n], there is an edge between vertices (i,++1) 1) with edge cost 1.
Let c R be the vector of all edge costs, let d E Ru+1
I be the demand vector which concatenates
-b in (3) with a last coordinate set to EiE(o) by and let B E (-1,0,13
R ExV be the edge-vertex
incidence matrix of G. Then the problem
min cflfl== Ecelfa
(4)
SER
/=d
has the same value as the empirical smooth calibration linear program (3).
5
Figure 1: Example graph G for n 5 with 1 6 vertices and 1 9 edges.
Proof. By Lemma 1, solving (3) is equivalent to solving
min -b x, where I -i++1 & dit1 - v for all i E [n 1],
(5)
We create dummy variable 1, and rewrite (5)
min
Σ
bb, In+1), where |x, - x=-1 || S U111 iy for all i [n 1],
2ERmI1 iE(M)
(6)
and 2; In+1 for all i [n]].
Next, consider directed graph Ō EV) with 4n - 2 edges which duplicate the undirected edges described in the lemma statement in both directions. Let B 13 ExV be the edge-vertex incidence matrix of G. and let E E the edge cost vector so that both edges in E corresponding to E have the same cost ce. Then (6) is equivalent to the linear program max d such that Br S c, where is described in the lemma statement. The dual of this linear program
min E f, SER B f=d
minimum-cost flow problem on G. In particular, based on the way we defined B, we can check that B / encodes the net flow at each vertex of G, which is set according to the demand vector d in the above optimization problem. Next, for each pair of directed edges (c', e") in G corresponding to some e E E, note that an optimal solution to (7) will only put nonzero flow on one of e' or c", else can achieve smaller cost by canceling out redundant flow. Therefore,
collapse each pair of directed edges into a single undirected edge, where we allow the flow variable f to be negative but charge its magnitude | in cost, proving equivalence of (7) and (4) claimed.
We believe this observation in Lemma 2 is already interesting, as it lets us to use specialized graph algorithms to achieve faster runtimes in both theory and practice for solving (3). By using the special structure of the graph (the union of a star and path), we show in Appendix B that we can develop more efficient custom algorithm for this problem. Specifically, we show how replace the constrained problem (4) with an unconstrained problem on only the path edges, of the form
A(F) (1 + fil (d, fo-1l+ fER
min
Σ iE(n-2]
ffz f4t dst1l+
Σ
alfil.
(8)
(ER-1]
We prove the following result Appendix B.2.
Proposition 1. There is algorithm which computes minimizer f f Rn-1 to A in (8), as well as the minimizing value A(f), in time O(n (n)).
7

---

Our algorithm for establishing Proposition 1 is based on dynamic programming, and recursively represents partial solutions to as piecewise- function. We implement updates to this representation via a segment free data structure in polylogarithmic time, giving our overall solution.
Corollary 1. There is algorithm which computes the value of (3) in time On log" (n)).
Proof. This immediate from Lemma 2, the equivalence between the constrained problem (4) and the unconstrained problem (8) established in Appendix B.2, and Proposition 1.
We now describe how to build upon Corollary to give an algorithm for proving Theorem 1, using result from [BGHN23a] which bounds how well the smooth calibration of an empirical distribution approximates the smooth calibration of the population.
Lemma (Corollary 9.9, [BGHN23a]). For e (0,1), there an n ( such that if Df n is the empirical distribution over ii.d. draws from D, with probability |smCE(D) -mmC((D,)
Further, we recall the smooth calibration error is constant-facto related to the LDTC.
Lemma (Theorem 7.3, [BGHN23a]). For any distribution D over [0,1] x {0, we have dC) smCE(D) 2dCE(D).
Proof of Theorem 1. We take ( samples so Lemma 3 ensures (smCE(D)
S
with probability 2 3' We then compute 3 smCE(D,,) using Corollary 1, and return "yes" iff < 4. which distinguishes between the two cases in Definition 2 via Lemma 4.
Experiments
In this section, we present experiments on synthetic data and CIFAR-I00 supporting our argument that dCE and smCE are reliable measures of calibration for use in defining a testing problem. We then evaluate our custom algorithms from Section 2 and Appendix B, showing promising results on their runtimes outperforming standard packages for linear programming and minimum-coo cost flow. The experiments in the first and third part of this section are run on a 2018 laptop with 2.2 GHz 6-Core Intel Core 17 processor. The experiments in the second part are run on a cluster using 2x AMD EPYC 7763 64-Core Processor and single NVIDIA A100 PCIE 40GB.
Synthetic dataset. In our first experiment, considered the ability of e-d-testrrs (Definition 5) to detect the miscalibration of synthetic dataset, for various levels E {0.01, 0.03, 0.05, 0.07, 0.1}, and various choices of d E (smCE, dCE, ConvECE). 10 The synthetic dataset dent draws from D, where a draw (t. y) ~ first draws v uuiif. [0, 1 - E*) and ~ Bern(e + E*), e* 0.01, by the proof in Lemma 13. In Table 1, where the
used is indepen-
for s* := 0.01."! Note that dCE(D) columns index (the number of samples), for each choice of d we report the smallest value of E such ConvECE, we implemented our
that a majority of 100 runs of s-d-tester report "yes." For tester by running code in [BN23] to compute ConvECE and thresholding at 5. For d E {smCE, dCE), we used the standard linear program solver from CVXPY [DB 16, AVDBI 88 and again thresholded 5. We remark that the CVXPY solver, when run on the dCE linear program, fails to produce stable results for > 2 due to the size of the constraint matrix. As seen from Table 1, both smCE and dCE testers are more reliable estimators of the ground truth calibration error E* than ConvECE.
Table Calibration testing thresholds (smallest passed on half of 100 runs).
26
2
2 2+1
2 +
2
+
2
SmCE
0.07
0.05
0.03
0.03
0.01
0.01
dCE
0.03
0.01
0.01
cECE
0.1
0.1
0.07
0.07
0.05
0.03
Ground Truth
0.01
0.01
0.01
0.01
0.01
0.01
JeWe implemented ConvECE using code from [BN23], which automatically conducts a search for a. This is slight variation the synthetic dataset used in [BGHN23a].

---

Table 2: Empirical sm on postprocessed DenseNet40 predictions (median over 20 runs)
D
Drase
Diso
Dremp
Empirical smCE
0.2269
0.2150
0.1522
In Figure 2, we plot the median error with error bars for each calibration measure, where the axis denotes log2(n - 1), and results are reported over 100 runs.
CONVBLE
010
LOTC
SIICE
0.02
0.22
090
Figure 2: The 25% quantile, median, and 75% quantile (over 100 runs) for smCE, dCE and cECE respectively. The r-axis is for dataset with size 2 + 1.
Postprocessed neural networks. In [GPSW17], which observed modern deep neural networks may be very miscalibrated, various strategies were proposed for postprocessing network predictions to calibrate them. We evaluate two of these strategies using our testing algorithms. We trained a DenseNet40 model [HLvdMW11]]
the CIFAR-100 dataset [Kri09], producing distribution D Drase- where draw (v. y) Drase selects a random example from the test dataset, sets to be its label, and to be the prediction of the neural network. We also learned calibrating postprocessing functions fiso and fremp from the training dataset, the former via isotonic regression and the latter via temperature scaling. These induce (ideally, calibrated) distributions Diso, Dump, where draw from Dio samples (v. y) Drsse and returns (fiso (1). 8), and Diemp is defined analogously. The neural network and postprocessing functions were all trained by adapting code from [GPSW17].
We computed the median smooth calibration error of 20 runs of the following experiment. In each run, for each D E (Druse Dis. Dump) ) drew 256 random examples from D, and computed the average smooth calibration error smCE of the empirical dataset using a linear program solver from CVXPY We report our findings in Table 2. We also compared computing smCE using the CVXPY solver and a commercial minimum-cost flow solver from Gurobi Optimization [Opt23] (on the objective from Lemma 2) in this setting. The absolute difference between outputs is smaller than 10-5 5 in all cases, verifying that minimum-cost flow solvers accurately measure smooth calibration.
Qualitatively, our results (based smCE) agree with findings in [GPSWI7] 17] (based on binned variants of ECE), in that temperature scaling appears to be the most effective postprocessing technique.
SmCE tester. Finally, we evaluated the efficiency of our proposed approaches to computing the empirical smCE. Specifically, we measure the runtime of four solvers for computing (3): a linear program solver from CVXPY, a commercial minimum-cost flow solver from Gurobi Optimization, a naive implementation our algorithm from Corollary using Python, and a slightly-optimized implementation using the PyPy package [PyP19]. We use the same experimental setup as in Table 1, ie. measuring calibration of uniform predictor on a miscalibrated synthetic dataset, with e* 0.01. 12 In Table 3, report the average runtimes for each trial (across 10 runs), varying the sample size. Again, the absolute difference between the outputs of all methods is negligible (w 10 10-9 in all cases). As seen in Table 3, our custom algorithm (optimized with PyPy) outperforms standard packages from CVXPY and Gurobi Optimization starting from moderate sample sizes. We believe that Table 3 demonstrates that our algorithms scalable, reliable way of testing calibration, and that these performance gains may be significantly improvable by further optimizing our code.
We found similar runtime trends when using our algorithms to test calibration on the postprocessed neural network dataset, but the runtime gains were not drastic as the sample size = 2 was smaller in that case.

---

Acknowledgements
We thank Edgar Dobriban for pointing to the reference [LHHDD23], and Yang P. Liu and Richard Peng for helpful discussions on the segment tree data structure in Section B.3. We also thank Yue Zhao for advice running experiments.
Table 3: Runtimes (in seconds) for computing the value of (3), using various solvers
12
2
2
2
2
2
2
CVXPY L.P solver
0.105
0.370
1.58
6.51
45.7
245
Gurobi minimum-cost flow solver
0.063
0.179
0.238
0.539
1.45
3.19
Solver from Corollary
0.177
0.389
0.899
2.01
4.66
10.6
Solver from Corollary with PyPy
0.079
0.115
0.176
0.307
0.621
2.05
References
[AAA* + 16] Dario Amodei, Sundaram Ananthanarayanan, Rishita Anubhai, Jingliang Bai, Eric Battenberg, Carl Case, Jared Casper, Bryan Catanzaro, Jingdong Chen, Mike Chrzanowski, Adam Coates, Greg Diamos, Erich Elsen, Jesse H. Engel, Linxi Fan, Christopher Fougner, Awni Y. Hannun, Billy Jun, Tony Han, Patrick LeGresley, Xiangang Li, Libby Lin, Sharan Narang, Andrew Y. Ng, Sherjil Ozair, Ryan Prenger, Sheng Qian, Jonathan Raiman, Sanjeev Satheesh, David Scetapun, Shubho Sengupta, Chong Wang. Yi Wang, Zhiqian Wang. Bo Xiao, Yan Xie, Dani Yogatama, Jun Zhan, and Zhenyao Zhu. Deep speech 2 End-to-end speech recognition in english and mandarin. In Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, volume 48 of JMLR Workshop and Conference Proceedings, pages 173-182, JMLR.org. 2016.
[AVDB18] Akshay Agrawal, Robin Verschueren, Steven Diamond, and Stephen Boyd. rewriting system for convex optimization problems. Journal of Control and Decision, 5(1):42-60, 2018
[BGHN23a] Jarostaw Blasiok, Parikshit Gopalan, Lunjia Hu, and Preetum Nakkiran. A unify- ing theory of distance from calibration. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1727-1740, 2023.
[BGHN23b) Jaroslaw Blasiok, Parikshit Gopalan, Lunjia Hu, and Preetum Nakkiran. When does optimizing a proper loss yield calibration? arXiv preprint arXiv:2305.1876. 2023.
[BN23] Jaroslaw Blasiok and Preetum Nakkiran. Smooth ECE: Principled reliability diagrams via kernel smoothing. arXiv preprinl arXiv:2309. 12236, 2023.
[Can22] Clément L. Canonne. Topics and techniques in distribution testing: biased but representative sample. Foundations and Trends in Communications and Information Theory, 193)):032--199, 2022.
[CKL,+22] Li Chen, Rasmus Kyng, Yang P Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 612-623, IEEE, 2022.
[CLS21] Michael B. Cohen, Yin Tat Lee, and Zhao Song. Solving linear programs in the current matrix multiplication time. J. ACM, (8(1))3:113339,200
[CST21] Michael B. Cohen, Aaron Sidford, and Kevin Tian. Relative lipschitzness extragra- dient methods and direct recipe for acceleration. In /2th Innovations in Theoretical Computer Science Conference, ITCS 2021, volume 185 of L/PIcs, pages 62:1-62:18 Schloss Dagstuhl- Leibniz-Zentruu für Informatik, 2021.
[DB16] Steven Diamond and Stephen Boyd. CVXPY: A Python-embedded modeling lan- guage for convex optimization. Journal of Machine Learning Research, 17(83):1-5, 2016.
10

---

[DGG [2] Sally Dong, Yu Gao, Gramoz Goranci, Yin Tat Lee, Richard Peng, Sushant Sachdeva, and Guanghao Ye. Nested dissection meets ipms: Planar min-cost flow in nearly- linear time. In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algo- rithms, SODA 2022, pages 124-153. SIAM, 2022.
[DKR 21] Cynthia Dwork, Michael P. Kim, Omer Reingold, Guy N. Rothblum, and Gal Yona. Outcome indistinguishabiity. In STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 202/, pages 1095-1108. ACM, 2021.
[Doi07] Kunio Doi. Computer-aided diagnosis in medical imaging: historical review, current status and future potential. Computerized medical imaging and graphics, 31(4- 5):198-218 111988111111 2007.
[GKR + 22] Parikshit Gopalan, Adam Tauman Kalai, Omer Reingold, Vatsal Sharan, and Udi Wieder. Omnipredictors. In 13th Innovations Theoretical Computer Science Conference, ITCS 2022, volume 215 of LIPlcs, pages 79:1-79:21. Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2022.
[Gol17] Oded Goldreich. Introduction to Property Testing. Cambridge University Press, 2017.
[GPSW17] Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. In International conference on machine learning, pages 1321-1330. PMLR, 2017.
[HKRR18] Ürsula Héhert-Johnson, Michael P. Kim, Omer Reingold, and Guy N. Rothblum. Multicalibration: Calibration for the Crompuationally-idnniffaa ceedings of the 35th International Conference on Machine Learning, ICML 2018, volume 80 of Proceedings of Machine Learning Research, pages 1944-1953, PMLR, 2018.
masses. In Pro-
[HLvdMW17] Gao Huang, Zhuang Liu, Laurens van der Maaten, and Kilian Q. Weinberger. Densely connected convolutional networks. In 2017 IEEE Conference on Computer Vision and Puttern Recognition, CVPR 2017, pages 2261- IEEE Computer Society, 2017.
[IS03] Y. I. Ingster and I. A. Suslina. Nonparametric Goodness-of-Fit Testing under Gaus- sian Models, volume 169 of Lecture Notes in Statistics. Ppringer-Verlage New York, 2003.
[JTT19] Arun Jambulapati, Aaron Sidford, and Kevin Tian. A direct Õ(1/E) iteration parallel algorithm for optimal transport. Advances in Neural Information Processing Systems, 32, 2019.
JSWZ21] Shunhua Jiang, Zhao Song, Omri Weinstein, and Hengjie Zhang. A faster algorithm for solving general lps. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 823-832, 2021.
[JT23] Arun Jambulapati and Kevin Tian. Revisiting area convexity: Faster box-simplex games and spectrahedral generalizations. arXiv preprint arXiv:2303.15627 2023.
[KF04] Sham M. Kakade and Dean P. Foster. Deterministic calibration and nash equilibrium. In John Shawe- Taylor and Yoram Singer, editors, Learning Theory, pages 33-48, Berlin, Heidelberg, 2004. Springer Berlin Heidelberg.
[KF08] Sham M. Kakade and Dean Foster. Deterministic calibration and nash equilibrium.
J. Comput. Syst. Sci., 74(1):115-130, 2008
[KLM19] Ananya Kumar, Percy Liang, and Tengyu Ma. Verified uncertainty calibration. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, pages 3787-3798. 2019.
11

---

[Kri09] Alex Krizhevsky.
Learning multiple layers of features from tiny images. feature-sttuutr209--9-
wwtp://w.......ooo..u..... 2024-01-31.
2009. Accessed:
[KSJ18] Aviral Kumar, Sunita Sarawagi, and Ujjwal Jain. Trainable calibration measures for neural networks from kernel mean embeddings. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 2805-2814, PMIR, 10-15 Jul 2018.
[LHHD23] Donghwan Lee, Xinmeng Huang, Hamed Hassani, and Edgar Dobriban. T-cal: An optimal test for the calibration of predictive models. Journal of Machine Learning Research, 24:1-72, 2023.
[LS14] Yin Tat Lee and Aaron Sidford. Path finding methods for linear programming: Solving linear programs in ō(vrank) iterations and faster algorithms for maximum flow. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, pages 424 433. IEEE Computer Society, 2014.
[MDR+21a] Matthias Minderer, Josip Djolonga, Rob Romijnders, Frances Hubis, Xiaohua Zhai, Neil Houlsby, Dustin Tran, and Mario Lucic. Revisiting the calibration of modern neural networks. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, pages 15682-15694, 2021.
[MDR+21b] Matthias Minderer, Josip Djolonga, Rob Romijnders, Frances Hubis, Xiaohua Zhai, Neil Houlsby, Dustin Tran, and Mario Lucic. Revisiting the calibration of modern neural networks. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 15682-15694. Curran Associates, Inc., 2021.
[Mur98] Allan H. Murphy. The early history of probability forecasts: Some extensions and clarifications. Weather and forecasting, 13(1):5-15, 1998.
[MW84] Allan H. Murphy and Robert L. Winkler. Probability forecasting meteorology. Journal of the American Statistical Association, 79(387):489- -00, 1984.
[NCHI5] Mahdi Pakdaman Naeini, Gregory F. Cooper, and Milos Hauskrecht. Obtaining well calibrated probabilities using bayesian binning. In Proceedings of the TwentyNinth AAAI Conference on Artificial Intelligence, January 25-30, 2015, pages 2901-2907. AAAI Press, 2015.
[NDZ 19] Jeremy Nixon, Michael W. Dusenberry, Linchuan Zhang, Ghassen Jerfel, and Dustin Tran. Measuring calibration deep learning. IEEE Conference on Computer Vision and Puttern Recognition Workshops, CVPR Workshops 2019, pages 38-41. Computer Vision Foundation IEEE, 2019.
[Nie22] Zipei Nie. Matrix anti-concentration inequalities with applications. In STOC '22: 54th Annual ACM SIGACT Symposium Theory of Computing, pages 568-581. ACM, 2022.
[Opt23] Gurobi Optimization. Minimum-cost flow. http://gurobi-pppimzzaooon -aaiiiiaaaaoonuooo----- optimods. cessed: 2024-05-21.
cow.-n.--oootooohtm.... 2023. Ac-
[PV21] Richard Peng and Santosh S. Vempala. Solving sparse linear systems faster than matrix multiplication. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, pages 621-521. SIAM, 2021.
[PyP19] PyPy. Pypy. https:/wwww.pypy.org// 2019. Accessed: 2024-05-21.
[QM22] Benjamin Qi and Dustin Miao. Segment tree beats. https://saaco.uudde/aaa///ees beats?lang=-ppp 2022. Accessed: 2024-05-20.
12

---

[Ron08] Dana Ron. Property testing: A learning theory perspective. Found. Trends Mach. Learn., 13)):307-42,, 2008.
[Ron09] Dana Ron. Algorithmic and analysis techniques in property testing. Found. Trends Theor. Comput. Sci., 5(2):73-205, 2009.
[RRSK11] Francesco Ricci, Lior Rokach, Bracha Shapira, and Paul B. Kantor. Recommender Systems Handbook. Springer New York, 2011.
[R(21a] Rahul Rahaman and alexandre thiery. Uncertainty quantification and deep ensembles. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 20063-20075. Curran Associates, Inc., 2021.
[RT21b] Rahul Rahaman and Alexandre H. Thiéry. Uncertainty quantification and deep ensembles. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, pages 20063-20075, 2021.
[She 13] Jonah Sherman. Nearly maximum flows in nearly linear time. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, pages 263-269. IEEE Computer Society, 2013.
[She17] Jonah Sherman. Area-convexity, loo regularization, and undirected multicommodity flow. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 452-460. ACM, 2017.
[vdBLL*21] Jan van den Brand, Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang. Minimum cost flows, mdps, and fn-regression in nearly linear time for dense instances. In STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021, pages 859-869 869. ACM, 2021.
[vdBLSS20] Jan van den Brand, Yin Tat Lee, Aaron Sidford, and Zhao Song. Solving tall dense linear programs in nearly linear time. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pages 775-788. ACM, 2020.
[VDDP17] Athanasios Voulodimos, Nikolaos Doulamis, Anastasios Doulamis, and Eftychios Protopapadakis. Deep learning for computer vision: A brief review. Computational Intelligence and Neuroscience, 2018, 2017.
[WXXZ23] Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. New bounds for matrix multiplication: from alpha omega. CoRR, abs/2307.0790 2023.
13

---

A Additional preliminaries
We first introduce some notation used in Appendices B, C. and D. When applied vector, let I|-l,p denote the Ep norm for 2 1. We let O₂ and La denote the all-zeroes and all-ones vectors in dimension d. We let A {i R || 1} denote the probability simplex in dimension d. The 1t coordinate basis vector is denoted e;. We say E IR is an e-additive approximation
E IR if - 2| I E. For set S C R, we say another set T IR is an E-cover of 5 if for all S, there is t with s Σ e. For a, E R with a $ b, we let clip o. (t) == min(b, max(a, t)) denote the result of projecting E IR onto [a, b].
We next formally define tolerant variant of the calibration testing problem in Definition 2.
Definition& 4 (Tolerant calibration testing). Let 0 S E2 S E1 S 1. We say algorithm A solves the (c1, (21, -tolerant calibration testing problem with n samples, if given n i.i.d. draws from a distribution D over [0, 1] x {0, 1}, A returns either "yes" or "no" and satisfies the following with probability 2 2
3'
. A returns "no" ifdCE(D 2 51.
A "yes" if dCE(D) S E2.
In this case, we also call A an (#1, 52) tolerannt calibration tester.
Note that an algorithm which solves the (E1,52) #2)-tolerant calibration testing problem with n samples also solves the E caalibration testing problem with the same sample complexity. Moreover, we give simple impossibility result on parameter ranges for calibration testing.
Lemma 5. Let < E2 S E1 S satisfy E E2 = E. There is a universal constant Cooin such Cau samples from distribution on [0. 1] x 10,1), it is informattiontheorrticallyl impossible to solve the (E1, (51,82)-t00 ttoeernnt calibration testing problem.
that, given n S e²
Proof. Suppose S To else we can choose Cavin small enough such that < 1. We consider two distributions over [0, 1] x {0, 1}. D and D', with dCE(D) 2 E1 but dCE(D') < E2, so if A succeeds tolerant calibration testing for both 2 and D', we must have drv (D (D') @*) N 3. where we denote the n-fold product of distribution with _nn Else, A cannot return different answers from samples with probability 2 3 as required by Definition 4. Specifically, we define D, D' as follows.
To draw (v, 3) ~ D, let u =
2 + E1 and y ~ Bern(
To draw (v, 1) D', let = e and y (ern ( + +))
We claim that dCE(D) E1. To see this, let 11 E ext(D) and (u, v,)) 11, so [(a,.))nlul]
because u is calibrated. By Jensen's inequality, we have:
(1 + =EI.
E( [|u v|] 2 E(u,aa)= [u]
The equality case is realized when u = 1/ with probability 1, proving the claim. Similarly, dCE(D') = E2. Finally, let ग == Bern( ()), n' == Bern(H + E). and π 7 (=")(=") denote their n-fold product distributions. Pinsker's inequality shows that it suffices to show that (xI (7')) < g to
contradict our earlier claim drv((D) (D)) 2 1 To this end, we have
3.
1
( [[ n dRL (π|[>²) =
log
log
7
+
3 -
n log
1
n
55 <
2
4s2
5'
where the first line used tensorization of dkL,, and the last chose Cooin small enough.
We also generalize Definitions 2 and 4 to apply to an arbitrary calibration measure.
14

---

Definition 5 (d testing). Let d be a calibration measure. E E Rzo. we say algorithm A solves the e-d-testing problem (or, A is an E-d tester) with n samples, given i.i.d. draws from a distribution 'D over [0,1] x {0, }. A returns either "yes" or "no" and satisfies the following with probability 2 2.
3'
1. A returns "no" ifd(D)
2. A returns "yes" ifd
For 0 S E2 E,, we say algorithm A solves the (E1,E2)-toleran d testing problem (or, A is an ((1,82)-toleranl d tester) with n samples, if given n Lidd draws from distribution D over [0, 1] x {0, }}. A returns either "yes" or "no" and satisfies the following with probability 2 3
2
1. A returns "no" ifd(D) 2 11.
2. A returns "yes" if (D) S 82.
B Appendix for Section 2
B.1 Deferred lemma proofs
Proof of Lemma
This follows from the triangle inequality:
j-1
x - xz5 5
I
Ix+1l
S
Σ
uk+1
= Dj U.-
R=
1m
B.2 Dynamic programming
In this section, we give our dynamic programming approach to solving (4), which establishes Proposition 1. The graph G in (4) is the union of a path P vertices and S to the (n 11th vertex. Let us identify the edges in with [n 1] (where edge corresponds to vertices (v, + 1)), and the edges in S with [2n 1 [n 1]. We first make a simplifying observation, which that given the coordinates of flow variable f Rº on the edges in the path P, there is unique way to are satisfied. Concretely,
the values of f on the edges the star S so that the demands B we require
fn-14: = d, + ft f:- for all 2 < i < n 1, fu = d2 f1, and fen d, fn--1-
Hence, minimizing the constrained problem in (4) is equivalent to minimizing the following uncon- strained problem on the first n flow variables, stated in (8) and reproduced here:
min A(F) = di + All - fn-1l+ + Σ f
1/= fut ditil +
Σ cilfil-
2E|n-2]
VE EEn-1]
We now solve (8). We first define a sequence of partial functions {A, : R - R) R)je(n-1] by
(1) |d + + c1/2/
A2(2) min d1 + fil+ Σ
life fu1 d41l+ Σ
alfil for all 2 2 n-2,
FRR
f;=2
sEL--1]
1E/-1]
An-1(2) = min A(f).
FER
f,=0
(9)
In other words, (2) asks to minimize the partial function in (8) over the first j flow variables {.f, Hej]. corresponding to all terms in which these flow variables participate, subject fixing f, We make some preliminary observations about the partial functions (Aj) je(n-1]
15

---

Lemma 6. For all j E [n - 2). A3 is convex. continuous, piecewise linear function with at most j + 2 pieces, and A is convex, continuous, piecewise linear function with at most n + pieces.
Proof. We first establish convexity by induction; the base case j 1 is clear. We next observe that
A,(=) = 0j|2| + min w 2 d,1 + A (w) for all 2 S j S 2, WER
(10)
12)1(2) = dn - z| + 1|11 + min WER
v - dn + An 2
In other words, each partial function A, can be recursively defined by first minimizing the first j 2 flow variables for a fixed value fz-1 = w. and then taking the optimal choice of w. Moreover, supposing inductively Aイ-1 is convex, Aj is the sum of a convex function and a partial minimization over a jointly convex function of (w, 2), so is also convex, completing the induction.
To see that A, is continuous (assuming continuity of A5-1 inductively). it suffices to note A, is the sum of continuous function and partial minimization over continuous function in two variables.
We now prove the claims about piecewise linearity, and the number of pieces. Clearly, A is continuous and piecewise linear with at most 3 pieces. Next, for some 2 S S 2, suppose A piecewise linear with vertices (*etet nondecreasing order (possibly with repetition) and slopes
{4:)_or so 4 is the slope of the segment of Aj-1 between and 1 and to and Lj are the leftmost and rightmost slopes. For convenience we define vi == -00 and 0j41 == 0c. Consider the function
min ww d,1 + A WER
(11)
For all values 2 satisfying 0 S 2 $ d, 1/41 where 0 s j, the function - +1 is piecewise linear with vertices U1 , 0/ + dj. Uš-1:.... Uj. and correspondingly ordered slopes 1,44 + 1, ,,..., (ux)ee)) U {= dz} where the slope switches from nonpositive to nonnegative, which is either a fixed vertex v = Uk for the entire range 2 S 2 + dj S 1/41, or the new vertex + dg for this entire range.
lo 1,4 1,...,4,
1. The minimizing w in (11) corresponds any v
In the former case, we have
min
(w 2 - dg} + A--1(w))) = =luk - 2 - -dyl+ AA--((w)) WER
(12)
which up to a constant additive shift is |= - (vk d,) ). a linear function in z in the range na S 2 + dy S. U141 because the sign of (Uk d,) does not change. In the latter case, we have
min I 2 =dyl + 1)-1(w) = 1 +,), WER
133)
which again is a linear function in = in the range U; S dj S U141 by induction. In conclusion, (11) is linear in each range [0; (u-djj, u++1 dj}, so it piecewise linear with at most j + pieces; adding cy /2]. which introduces at most 1 more piece, completes the induction. An analogous argument holds for j n but we potentially introduce two more pieces due to adding [d, - 2| + c/1
For convenience, we now describe how to update the slopes and vertices going from the piecewise linear function AJ-1 to Aj- Also, above suppose the vertices of AJ-1 are {0; (e))))) and the corresponding slopes are [t,)/_-- Then because we argued (11) is linear in each range E [.y - 0/41 0441
d,, 0 d it has vertices ( d, } If [1; d
d,] and f, [-1,1], then are in the case of (13) and the corresponding slope in this range is f,. Otherwise, if t; v -1 we are in the case of (12) with slope 1, and if f, 2 1 the slope of the piece is similarly 1. We then add |2|
(and Idn - =| if j = n - 1). In summary, the new slopes and vertices are as follows.
If j S n 2, 2, the new vertices are {u, - -ddy U (0). If o dj 5 Uk+1 d, for some S j. using our convention Up = 00 and 1/+1 = xo, the new slopes are
(t)) - csbosic u (clip - c U(clip(-u.n(ta) + og) u (clipp + czJacijj
(14)
16

---

If - 1, the new vertices are fe; - dj hebl U (0) {dn) 1f -
l S uk+1 dj
and Un d2 I dn vh+1 d, for some S h l S j. the new slopes are
1..) ciluctidd + cj4m2d, Usisi (K(h,))
ccliip- oj U cclipt cj
(15)
u ((llip-aa)((1)) 1} u c + 1
where we let ig denote the 0-1 indicator variable of an event E
The ordering of these vertices and their slopes are uniquely determined, because they are sorted similarly due to convexity, which implies nondecreasing slopes as z increases. Finally, note that assuming the invariant that at least one {tz [t=]<_ is nonnegative and at least one is nonpositive (which holds in the first iteration), in either of the cases (14) or (15) this invariant is preserved, since clipping preserves signs, the smallest slope decreases, and the largest slope increases.
We require one additional property of the slope updates (14).
Lemma 7. For j E [n 1], let (tr)= be the nondecreasing slopes of A₁- Then to S -1 and 1
Proof. By observation, the smallest and largest slopes of A (9) are -1 ci and Ci. Hence, assuming inductively the lemma statement is true for 1 the slope updates (14) result in smallest and largest slopes -1 Cj and -1 + Cj in Aj. completing the induction.
We next observe that, by storing constant amount of information in each iteration, we can work backwards from an optimal solution to A,-1 and recover all flow variables which realized this value.
Lemma 8. Let fusheb and {ta be the nondecreasing vertices and slopes of Aj-1 for some 2 ك Sn n - 1. Suppose we know et and u, for f,r E [j], defined such that t S -1 but te 2 - 1,, and similarly 1 S but t, 1. Then given a value of 2. we can compute (1) time
wrgmin ww - - d,1 A
Proof. Note that existence of Uz, Ur is guaranteed by Lemma 7. We consider three cases.
First, if 2 + dj E (uy, 0yl, we claim w + d,. To see this, recall that if 2 + d, E [0 U:- 1). we proved in Lemma 6 that the slopes of |w- 2 --dd dd +A)-1((1 (w)) (in w) are to - 1,, - -l....
1.
1.....ty +ty+ 1. 1. Hence, the assumptions imply t, [-1, 1], so a vertex of |w- 2- d A5 where
the slope changes from nonpositive to nonnegative (i.e. the minimizing argument w)) is w + dj. as claimed.
To handle the other two cases, 2 + d, S ity then the above calculation shows the new optimal vertex is w = uy; similarly, if dj U, the new optimal vertex is w Vr.
We now describe an interface for a data structure that we use to efficiently implement the updates (14) and (15), whose existence we prove in the following Appendix B.3.
Lemma 9. There a data structure, Segment Tree, which initializes a vector & RR t x- On, and supports the following operations each in O(log n) time.
Query(i): Return 4:-
Add(E, r, c): Update t; t + cfror all Sigr.
Set(e,r,,); Update 1; t- cfrr all e < S r.
Given access to Segment we now describe how to solve (8) in nearly- time, proving Proposition 1.
17

---

Proof of Proposition 1. We first describe how to compute all of the vertices and slopes {iy fei {4:)20 of 2 in time (n log (n)): The proof of Lemma 6 shows that the vertices are
n-2
n カ-2
dp
(16)
Am
==0
where we treat the empty sum as O. Moreover, the vertex 2k=++1 de is the new vertex which was inserted (as 0) when computing Aj. and then advanced through the remaining iterations. We sort the vertices (16) into nondecreasing order, keeping track of the resulting permutation x In 1 2] (0) -> [n- - 1], i.. if the vertex - -1==++1 dy is the 7th smallest in (16), then x(j) = i. This step takes time (n log n1) and does not dominate.
We next initialize a Segment (Lemma 9) with n vertices. We update it through the first 2 recursive computations of slopes, via (14), keeping track of a time counter j. i.e. after we are done updating the slopes of A, the time counter increments. The state of Segment Tree at the end of time j is as follows. For all & E [j]. letting x (h) be the next largest value after т TAk amongst { (r(k)))e wejj] require that t, equals the slope of the segment to the right of the vertex inserted at time k in Aj for all the coordinates π (A) + 1 - (h). In other words, Segment stores all of the slopes of Aj in its coordinates (with redundancies due vertices which will be inserted after time j), and maps the times vertices are inserted to their coordinate values in Segment Tree.
We next show how to maintain this state in Ollgg((n) time per time increment. In iteration j. the update (14) requires us to clip all previous slopes to the range [-1, 1, 1], subtract oj from all slopes in the range [1, π ( and add ej to all slopes in the range [x(]) + 1, n]. We first use Query to perform binary searches for the values f, r as defined in Lemma 7. We then sequentially apply
Set(1, 6,1,,,,11 -1), Set(r + n, 1), Add T()), -cy), Add(T(j) + m,),
The dominant runtime term is the cost of (log(n)) calls to Query perform the binary search, giving the claimed Olog"((n) (n)) runtime per time increment. We can now call Query times to compute all slopes and vertices of An-2. We will also store the values of ey and v, at time j. which takes (1) time given E, r, n, and partial sums which can be precomputed in time O(n).
Given these slopes and vertices, it is straightforward to apply (15) to compute all slopes and vertices of A in time (n), at which point can find 2 : argmin -e stored values of ny and v, in every iteration, we can then use Lemma 8 to compute all the optimal flow values realizing A 11). Finally, we compute the optimal value (8) in time (n)).
Next, by using
B.3 Implementation of Segment Tree
In this section, we develop a data structure known as a segment tree which plays a vital role in our main algorithm. In particular, it allows to prove Lemma 9. While this data structure is well-known folklore in the competitive programming community (see e.g. an overview of this technique in (QM22)), we provide full description and proof for completeness.
For integers and r satisfying e r, we use [e: r] to denote the set [e,e+I....,r)
Lemma 10 (Segment tree). Ler G' be semigroup with an identity element where the semigroup product of a. E G denoted by a b or ab and is not necessarily commutative. Let be an array of length n, where each element of v is initialized to he the identity element of G. There is a data structure D. called a segment tree, that can perform each of the following operations in Ologn) time (assuming semigroup product can be computed in constant time).
1. Access(i): given i [1 nl). return the 1th element in v.
2. Apply(g, l): given f,r E [1 ra] satisfying e << r, and given a semigroup element g E G. for each index E [E : r). replace w/il] with g =[().
Before proving Lemma 10, we first use it to prove Lemma 9.
Proof of Lemma 9. We apply the data structure in Lemma to a specific semigroup G defined as follows. The elements of G are functions 7 RR + R, where the identity element e is the identity
18

---

function e(u) = for every E RR and the semigroup product is defined as function composition: (a b)) (b(())) for every a, G and u R. The semigroup G consists of the following functions: add, and set, for every
R. These functions are defined as follows:
add,(u) = u + e, set,(u) = c, for every u E R.
It is easy to check that these functions are closed under composition:
add, add2 = adde+c'>
set, set setc:
add, - set,' = seta+e's
set, add, set..
Therefore, G is valid semigroup. We can now implement the operations Query, Add, Set in Lemma 9 using the operations Access and Apply in Lemma 10 follows.
To implement Query(i), we run Access(i) obtain its output g = v(i] E G. and return g(0).
To implement Add(E,r, c), we run Apply(add.; E.).
To implement Set(E, c), run Apply(set,,
The correctness of this implementation can be shown inductively. At initialization, uf[]] = e, and thus Query(i) returns e(0) 0, which is the correct value of t; at initialization. It remains to show inductively that after each Add and Set operation, the output of Query(i), i.e., [0]] the intended value of f,. Indeed, after Add operation, for any i [E: r). the element vfi] is updated to vlii (add. o(i)), and thus
v (0) = (add. (0) = (d)(( = v0] + +c=4
which is the intended new value of t, For é [e r]. the element oft] remains unchanged, and thus (0) remains unchanged. This is desired because the value of t, is intended to be the same as the old value. Combining these two cases, we have shown that the Add operation maintains that (O) is the intended value of for every E n). We can similarly show that the Set operation also has this property, and thus our implementation is correct. The running time guarantee of the implementation follows directly from the running time guarantee in Lemma 10.
Li
We prove Lemma 10 by describing the construction of the segment tree data structure and analyzing
its correctness (Lemma 11) and efficiency (Lemma 12). By appending to the array an appropriate number of auxiliary entries, we can assume without loss of generality that the array length n is a power of 2, i.e., 2" for positive integer r. The data structure is implemented using complete binary tree T with depth r, where the 2" leaves correspond to the n = 2" entries in the array.
use seg(r) C [1 n] denote the set of indices that node E T is associated with. For the root To of the tree T, we set seg = [1 n] [1: 2" and for its two children TI, 72 we set seg(7)) = [1 n/22 = 2 and seg(72) = 2 + n [2- + 1: 2n]. In general, for any non-leaf node 7 and its two children 71, 72, we set seg( as the first half of seg(r) (T) and set seg( (T2) the second half. In particular, for every leaf seg(r) is singleton set consisting of unique index E [1 n], and we say T is the (unique) leaf corresponding to index i. See Figure 3 for example with depth 3.
More specifically,
TO
Layer
5
Layer
Layer
f2}
(2)
(3]
(4)
(5)
(6}
(7}
{8}
Layer
Figure3 3: Example of segment tree with depth r = 3.
At every node the tree, we maintain a semigroup element 9- E initialized to be the identity element
19

---

Access. We implement (ccess(i) as follows, Let To - be the directed path from the root To the leaf 7, corresponding to index i. Return the semigroup product 97a9r.
9r.-
Apply. We implement Apply(g, f, recursively. That is, implement Apply(g, F, in Al- gorithm which takes a node T E ' as an additional input. We then define Apply(g, 2,r) to be Apply(g, & to), where the additional input is set the root To of the tree T.
Algorithm (,,,,
1: if (seg(r) [[:r]= = then
2: return
3: end if
4: if seg(()
S [|: then
5: Or 4- 9
6: return
7: end if
8: Let T2.72 be the two children of r
9: On
f - 9r
10: On + 9r2
0r EE
12: Apply(g. T1) Apply(g,
Correctness. At initialization, each array element v[i] is initialized to be the identity element The semigroup element 9r stored each tree node T also initialized be e, so Access(i) returns the correct value It remains to show that Access(i) still returns the correct value of v/e] after each Apply operation. This is established in the following lemma:
n). let To - - Tr be the directed path from the root To to the leaf Ty corresponding index Let ir...... 9r. G denote the current states of the semigroup elements 9r, stored in the data structure. Then after we call Apply(g, L, T), we have
Lemma 11. For E {l....,.y
9Ta -
if [e: r): if $ [f: r].
9ro gr.
970 ... 97.3
Proof. is clear that [1 n]] = seg( To) 2 seg(T,) = (i). If E [f: rl,, let t, be the first node among .o..... such that seg(T,) S r), We can inductively show that for every j ..... right before we make the recursive call Apply(g, Ty), we have
e,
if < j', if - j', if > jr.
9r:
gr ... Orys
Ir.
When we call Apply(g, l, Ty), since seg (Tj) S [e: r., Line is executed and the function returns after that. Now we have
c,
if < j. if = j, if >
9r.
9T. ... Ir,
This implies 9ro ". 9r, = g. 97. ... 9r,, as desired.
Similarly, if & re, let Tr be the first node among To show that
Tr such that seg (Ty) O [E:r]
We
c,
if < j; if = j; if > j.
9r.
9ro
Iry1
This implics Iro '..r. -r. 9r.. desired.
20

---

Efficiency. The following result establishes the running time guarantee in Lemma 10. Lemma 12. Both Access and Apply run in Ollog n.) rime.
Proof. It is clear that Access runs in time ( Ologn). When recursive calls at Lines 12-13 are made only when [e: r]] intersects but does not contain seg(r) i.e., 0 S seg(r) [ & seg(r). There are at most 2 such nodes each level of the binary tree, so the total number of such nodes is Ol) This implies that Apply runs in time (log.).
Apply(g, 4, r; r), the
B.4 Tolerant testing via smooth calibration
For completeness, we first make the simple (but to our knowledge, new) observation that, while the constants in Lemma 4 not necessarily tight, there is constant gap between dCE and smCE.
Lemma 13. Suppose for constants B > A > O, it is the case that A AdCE(D) s smCE(D) s
B B-d -DCEE(D) for all distributions 'D over [0, 1] x {0. Then, B 3 A
2
Proof. First, we claim that A < 1. To see this, let (v, D be distributed where = with probability 1, and Bern( + +) for some [0, $.. Clearly, smCE(D) = = (1 +
Moreover, dDE(D) = E, which follows from the same Jensen's 's inequality argument as in Lemma this shows that A Σ 1. Next, claim that B 2 3 concluding the proof. Consider the joint
distribution over (u, U, y) in Table B.4, and let be the marginal of (u, y). It is straightforward
Probability mass u V
y w(v)
1-6
check (u, y) is calibrated and EE|u- - 0l 5. so dCE(D) S 5. Moreover, smCE(u, y) 2 as
witnessed by the Lipschitz weight function w(()) in Table B.4, finishing our proof that B
3.
2"
smCE(v, v) 2 E[(y v)w(()) = (6 + 1
((-2) (1 (1)
3e
Using these claims, we now give our tolerant calibration tester in the regime E1 >> 4
Theorem 3. Let O S 82 S 8ı S satisfy E1 482, and let 2 Cie Te, - for universal constant Cus- There is an algorithm A which solves the (E1, tolerann calibration testing problem with n samples, which runs time
O log)))n)))
Proof. Throughout the proof, let : & -2e 0. Consider the following algorithm.
1. Sample 2 Cg samples to form empirical distribution D.,, where Cia is chosen large a enough so that Lemma 3 guarantees |smCE(D) -smE((D,)) S 2 with probability 2 2
3"
2. Call Corollary 1 to obtain 8, the value of smCE(D.).
3. Return "yes" if B S 28a + 2, and return "no" otherwise.
Conditioned on the event (SmCC(D)-SMCE SmCC(D.) 2 we show that the algorithm succeeds in tolerant calibration testing. First, if dCE(DD S 82, then smCE(D) S 28a by Lemma and therefore by the assumed success of Lemma 3, the algorithm will return "yes." Second, if dCE(D) 2 E1, then smCE(D) 2 EL by Lemma 4, and similarly the algorithm returns "no" in this case. Finally, the 2
runtime is immediate from Corollary 1; all other steps take O(1) time.
D
21

---

C Lower distance to calibration
In this section, we provide our main result on approximating the lower distance to calibration of distribution [0, IJ {0, 1]. We provide details on framework for lifting constrained linear programs to equivalent unconstrained counterparts in Appendix C.I. In Appendix C.2, we next state preliminary definitions and results from [BGHN23a] used in our algorithm. In Appendix C.3, we then develop a rounding procedure compatible with a linear program which closely approximates the empirical lower distance to calibration. Finally, in Appendix C.4, we design an algorithm for calibration testing, which solves the problem for larger range of parameters than Theorem 4 (i.e. the entire relevant parameter range), at quadratic runtime overhead.
rounding procedure to
C.1 Rounding linear programs
In this section, we give a general framework for approximately solving linear programs, following similar developments the recent combinatorial optimization literature [She13, JST19J. Roughly speaking, this framework is a technique for losslessly converting a constrained convex program to an unconstrained one, provided we can show existence of a rounding procedure compatible with the constrained program in appropriate sense. We begin with our definition of a rounding procedure.
Definition 6 (Rounding procedure). Consider a convex program defined on the intersection of convex set X with linear equality constraints Ax b:
min C X.
(17)
ZEN
Az
We say Round is (A, eqqualiiyy rounding procedure for (A,b,c, X) 2 1, and any E X, there exists x' = (z) X such that Ax! Ax' b, and
C S C.a x +
Ar 8/1
(18)
Intuitively, rounding procedures replace the hard-constrained problem (17) with its soft-constrained variants, i.e. the soft equality-constraine
min T =E
x
Ax
(19)
for some (A, b. p) constructed from the corresponding hard-constrained problem instance (parame- terized by A, c, 2). Leveraging the assumptions on our rounding procedure, we now show how to relate approximate solutions to these problems, generalizing Lemma of [JST19].
Lemma 14. Let x be an s-approximate minimizer to (19), and lel Round be a (Ā, (..)--quality rounding procedure for (A, b, c, X).. Then x' == (ound(x)) is an E-approximate minimizer (17).
Proof. We first claim that a minimizing solution to (19) satisfies the constraints A.r To see this, given any E X, we can produce x' E & with Ax' = and such that x' has smaller objective value in (19). Indeed, letting x' Round(a'). (18) guarantees
c T x' Ax' -6 öl|, s x
x
| A
Ar
as claimed. Now let x' E satisfying Art b minimize (19). Then, x is an e-approximate minimizer to (19) and x' = (ound( we have the desired claim from Ar' = b, and
T = - cTa' + An' - b1| <cTx Ar - bl <caar xt + Ar - öl| =cT +
In the remainder of the section, we apply our rounding framework to a hard-constrained linear program, in the p = geometry. To aid in approximately solving the soft-constrained linear programs arising from framework, we use the following procedure from [JT23], building upon the recent
22

---

literature for solving box box-simplex games at accelerated rates [She 17, JST19, CST21]. In the statement of Proposition we use the notation
| p-2
max Am
Notice that in particular, || is the largest & norm of any column of A.
Proposition (Theorem 1, [TT23]. A E Rexd b E R4, e E R", and & > 0. There is an algorithm which computes an e-approximate saddle point to the box-simplex game
min max x Ay b" + c x. 1,11 yEAR
(20)
time
o (mnz(A)-
| log d
We also require standard claim converting minimax optimization error to error on an induced minimization objective. To introduce our notation, we say that x E X an e-approximate minimizer of f X - R if ((x) min (xx) I We call (x, y) X x ) an e-approximate saddle point to convex-concave function f : y - Rf its duality gap at most 6, i.e.
max fa. min f(a v) S. y'E)
Ø'E
Lemma 15. Let f : X y + R be convex-concave for compact X.Y, and let g(x) == maxyey f(z v) for x E X. If (z, y) is e-approximate saddle point to f. is E-approximate minimizer to
Proof. Let y' argmaxyyyyJ (x, and x' rex ( (x', v). The conclusion follows from
min g(x))
min max f(x", y²) max min f(x", fx'. ,y" min f(x', v). x E'EX EY
rex
y'Eyx
xex
where we used strong duality (via Sion's minimax theorem), so that
g(x) min sed g(x*) S g(x) [(x,,) ((, ((d.v) se
The following corollary of Proposition 2 will be particularly useful in our development, which is immediate using Lemma 15, upon negating the box-simplex game (20), exchanging the names of the variables (z, y), (b, c). and explicitly maximizing over y E 1-1, 1|", " i.c.
min (c,x) + ||r bll1 = min max. (c, x) + (Ax- b). 2EAd
zEA" vεl-1,11"
Corollary 2. Let A E Raxd b E R", CE Rdd and 0. There is an algorithm which computes E-approximate minimizer to min x + Ax b112
time
|All log d
nnz(A))
C.2 LDTC preliminaries
In this section, we collect preliminaries for our testing algorithm based estimating the LDTC. First, analogously to Lemma 3, we recall bound from [BGHN23a] on the deviation of the empirical estimate of dDE(DD from the population truth which holds with constant probability.
Lemma 16 (Theorem 9.10, (BGHN23a])- For any e E (0, 1), there is an n 0(+)) such that, if
D,, the empirical distribution over i.i.d. draws from D, with probability 2 2/2
dCE(D) dCE(D.)) Se.
Next, given set U [0, provide analog of Definition I which is restricted to U.
23

---

Definition 7 (U-LDTC), Let U C. [0.1], 1], and let D be distribution over [0. 1] x {0. 1). Define
(D) to be all joint distributions II over (u, v. E x [0, 1] x {0, 1}, with the following properties.
The marginal distribution of (v. y) is D.
The marginal distribution (u, v) is perfectly calibrated, i.e. Enryyuy = u.
The U-lower distance to calibration (U-LDTCC) Df denoted dCE is defined by
dCE (D) := inf ITeex (D) ((.na)) |u - vl.
Note that if we require {0, 1} U. then ext" (D) is always nonempty, because can let u with probability 1. We also state helper claim from [BGHN23a], which relates dCE to dCE. Lemma 17 (Lemma 7.11, (BGHN23al). Let D be distribution over [0, 1] {0, 1}. and let U be finite 5-covering of [0, 1] satisfying {0, 1} U. Then, dCE(D) < dCE (D) z dCE(D) +
To this end, in the rest of the section we define, for any E (0, 1),
ie
U. = (0.1)U
i
(21)
which is an 5-cover of [0, 1] satisfying 1 = O(2). Finally, we state a linear program, derived in [BGHN23a], whose value equals dCE (D), when the first marginal of D is discretely supported.
Lemma 18 (Lemma 7.6, [BGHN23a]). Let U, [0, 1] be discrete sets, where {0. 13 C U, and let D be a distribution over V x {0, 1}, where for (v,y) E V x {0, 13 we denote the probability of (v.y) D by D(v,)) y)- The following linear program with 2/ variables I[u, v, y) for all (u, v. y) E X {0, 1}, is feasible, and its optimal value equals dCE" dC):
min IERVICIVV
Σ (u. V((
1-2/ II, u.
such that
EI(,, v,9) D(v, v). for all (v,8) EV x (0.1),
WEU
and (1 u)
Σ M(,, Σ
N(u,v, v 0), for all E U.
VEV
AEV
C.3 Rounding for empirical U-LDTC
In this section we fix dataset under consideration,
D. = ((1.,,:)) C [0, x (0,1},
and the corresponding empirical distribution, also denoted D.,, where (v, y) ~ D,, means (v.y) = (v,, 94) with probability 1 for each E [n]] We let V (et be identified with [n] in the natural way. Moreover, for fixed parameter E (0, 1) throughout, we let := U, defined in (21). Finally, we denote
T2
|U| = O ), and let U E [o. 1 1|mxm be the diagonal matrix whose diagonal entries correspond to U. We also identify elements of U with j [m in an arbitrary but consistent way, writing Vj E [0, 1] to mean the jdh element of U according to this identification.
We next rewrite the linear program in Lemma 18 into more convenient reformulation. Lemma 19. The linear program in Lemma 18 can equivalently be written as:
Jin Rmn
dCE" (f.):= :=
min ZEX
c x, where X = A 2mn and we denote
Rmn
M -
(22)
24

---

where we define c E R2mn, M E Rux2mm, and Bo. B1 E Rmxmn by
2mn
((.j..) ==
| - vil for all (i, E [n] x [m] x {0,1), 1),
1
y/ = k, i' = for all i' E (m). (i.j, E [n] [m] x {0,1),
My (...A)
10 else
j j=j', h = 0
and Bolgy.0...
for all j' E im]. (i.j.k) k) E [n] x [m] x {0,1),
(0 else
[1
j = j', k
(Blly,66.. (0 else
for all j' e [m]. (i.j. E [n] x [m] x {0,1}.
Proof. This is clear from observation, but we give a brief explanation of the notation. First, a E X represents the density function of our joint distribution II over U x V x {0, 1]. and has 2nn coordinates identified with elements (i.j. k) E V U x {0.1] = [n] x [m] x {0. We let the subset of coordinates with k 0 be denoted 2o E Rm" defining æ1 similarly. Recalling the definition of the linear program in Lemma 18, (i.j.k) is indeed reweighted by c(cj.k) = My vi/-
Next, M represents the marginal constraints Lemma 18, and enforeing Mr = I is equivalent to the statement that, for each E [n)]. the sum of all entries (i, k) of x with i = /' and k = yi is A since that is the probability density assigned to (vy, ye) by the distribution Din-
Lastly, the 7th calibration constraint in Lemma 18 is enforced by the 7th row of the equation U =
(Im 1 which reads uj (Bol) 2o) (1 (1-u,) uz) ([B]): z1). We can check by the definitions
of [Bolj- [Bı];: that this is consistent with our earlier calibration constraints.
We give a convenient way of visualizing the marginal and calibration constraints described in Lemma 19. For convenience, we identify each x E A 2 with an m x 2n matrix
mat(x:) = X = (Xo E Rmxn X1 E R=xx)
(23)
where X, consists of entries of zo arranged in matrix fashion (with rows corresponding to [m] = U
and columns corresponding to [n] V). and similarly X, is a rearrangement of 21, recalling (22).
When explaining how we design our rounding procedures to modify X to satisfy constraints, it will be helpful view entries of X as denoting an amount of physical mass which we can move around.
There are 2n columns in X, corresponding to pairs (i. k)) E V x f0, 1}; among these, we say n columns are "active," " where column (i, k) is active iff y/ ki and we say the other n columns are "inactive." Following notation (23), the marginal constraints X = n 11,, simply ask that the total amount of mass in each active column is n. so there is no mass in any inactive column since E 2mm
Moreover, there are rows in X, each corresponding to some j E U. If we let Ej denote the amount of mass [ and ry the amount of mass on {1]j: the jth calibration constraint simply asks that nzly = (1 My )r i.e. it enforces balance on the amount of mass in each row's 's two halves.
Finally, for consistency with Definition 6, the linear program in (22) can be concisely written
M B
[ 11,
min c Tx, where A == ZEx
B = (UB, -(Im U)B1), b:
12
O.
(24)
Az=b
and c, X' are defined in (22). In the rest of the section, following Definition 6, we develop an equality rounding procedure for the equality-constriieed linear program in (24) in two steps.
1. In Lemma 20, first show how to take x E X' with |Ma- 1 1 : = A, and produce x' X such that Mr 1 n 1, (i.e. x' now satisfies the marginal constraints) and || x'1l1
(A)).
2. In Lemma 22, we then consider x E X' such that, following the notation (22), || UB = A. We show how to produce x' E X' such that Ma = Mr (i.e. the marginals of x' are unchanged), UB = (Im - - (i.e, xf is calibrated), and
(Im - U)B
(c, x' - z) = O(A).
25

---

Our rounding procedure uses Lemma 20 to satisfy the marginal constraints in (22), and then applies Lemma 22 the result to satisfy the calibration constraints (22) without affecting the marginal constraints. By leveraging the stability guarantees on these steps, we can show this is indeed valid rounding procedure in the sense of (18). We now give our first step for marginal satisfication.
Lemma 20 (Marginal satisfaction). Following notation in (22), let x E satisfy ||a - A.
There an algorithm which runs in time (mn), and returns x' with
Mr 1m ||x 2'111 S 2A.
n
Proof. Recall for i E [rt], we say column i of X, is active if y: O, and similarly column of X1 is active if y/ 1. We call the set of inactive columns, and partition A, which we call the set of active columns, into three sets ^², AA, and AS, where A are the columns whose sums are > / A are the columns whose sums are <. 3, and A are the remaining columns. Hence, every column of X belongs I, .AAA, A A Note that until |A n, we can never have A 0, since this means all column sums in A are 2 1. (with at least strict inequality), contradicting x E X.
We first take columns A² one at a time, and pair them with an arbitrary column in i' E A moving mass from column arbitrarily to column i' until either column i or column i' enters A= We charge this movement to the marginal constraints corresponding to i and i', since the constraints were violated by the same amount as the mass being moved. After this process is complete, A² is empty, and we only moved mass from columns originally in A to columns originally A=.
Next, we take columns i E / one at a time, and pair them with an arbitrary column i' E AS, moving mass until either column i is Om column i' enters A= We can charge half this movement to the marginal constraint corresponding to i', since the sign of the marginal violation stays the same throughout. Hence, the overall movement S 2A. After this is complete, all columns in I are On and all columns in A are in A= so we can return x' E A 2mm corresponding to the new matrix.
It is clear both steps of this marginal satisfaction procedure take O(m)) time, since we can sequen- tially process columns in A until they enter A=, and will never be considered again.
We next describe a procedure which takes x E A 2mn and modifies it to satisfy the calibration constraints UBar (In. U)B without changing the marginals Mr. We first provide helper lemma used in our rounding procedure, which describes how to fix the jth marginal constraint.
Lemma 21. Let x E A 2mn and X == mat(x) as defined in (23). Let j E [mm] correspond to an
element uj E U, let := ||[ools:ll II1. ry := [|X,]]= 111 and let A, == |u,ly- (1-u,))) There exists j' E [m] such that we can move mass from only X y: to Xj resulting in Rmx X' x' A 2mn
such that Ma' = MMr, uy ||I||,,b = =1 22)i X 11b::111 and (c, x' x) < Aj.
Proof. Without loss of generality, suppose that the row j = corresponds to új = 0, and j = m corresponds új = 1. We split the proof into two cases, depending on the sign of uzl (1 Uty )r--
Case 1: u > (1 u,)ry. We j = 1, i.e. we only move mass from the 5th row to the first row. Specifically, we leave [x1| unchanged, and move mass from [Xuly: to [Xo]1s, making sure to only move mass in the same column. The total amount of mass we must delete from [Xolj: is
Uj Uj
u,C; (1 ug)ra
A Mly
Uj
Our strategy is to arbitrarily move mass within columns until we have deleted A total mass. If we denote the mass moved in column i e [n] as ōej, and let x' be the result after the move,
my
(c. x' - x) < REim]
(c(,1.0) - 10:5 = Σ 11u - u/l lui -oll--llee 8ez S Σ Uno = Aj-
MEIM
aE|m]
Here, the first inequality was the triangle inequality, the first equality used the definition of c in (22), the second inequality used 41 = 0 and the triangle incquality, and the last used Σie(n) diz = A
26

---

Case 2: uzlz < (1 - uy)ry. This case is entirely analogous; we move mass arbitrarily from row j to row m, i.e. the last row with Um The amount of mass we must move is
U Ej - u, u,,, -u
A
Uj Again denoting the amount of mass moved from column E [n] as dej, the claim follows:
Uj
Uj
(c, 2) -
Σ iE(x)
val (lm
2s 24l1d - > (1 uz)o.s A
sc(m]
By iteratively applying Lemma 21, we have our marginal-preserving calibration procedure. calibration). Following the notation (24), given x E A 2mm with
Lemma 22 [Bx | = A, we can compute x' with Mr' Mr, Br' -m. and (c, x' - x) S A in O(m)) time.
Proof. It suffices to apply Lemma 21 to each row i [m]. All of the movement in the rows i E [2, m - 1] are independent of each other, and do not affect the imbalance the rows i {1,m) m} when we have finished applying Lemma 21, since e.g. unl1 0 regardless of how much mass is moved to [X and a similar property holds for the m row. The total change in (c, x) is thus boundable by Ej Aj A, and applying Lemma 21 each takes ((n) time. Finally, Mæ Mr' follows because we only move mass within the same column, so no marginal changes.
By combining Lemma 20 with Lemma 22, we can complete our rounding procedure.
Lemma 23. Let (A, c, X) be defined as in (22), (24), and let (A, (4A,4b). There exists Round, (A, b, -)-qualyyy rounding procedure for (A, b, c, X), running in Omm) time.
Proof. Throughout the proof, let AM (24). We also denote the total violation by
Mr 11 and AB |Brll following the notation
b|| 4AM + 4AB.
A
We first apply Lemma 20 to x to produce ã satisfying ||ا - =|| I 2 and Mi = 1, in (mm)
time. Note that, because |B| 1-11-11 I since all columns of B are 1-sparse, have
B S [Bx||, + [B || - =|| S AB + 24M
Next, we apply Lemma 22 to I, resulting in x' with Mr' = Ln. Br' = Dm, and (c, x' - 2) S AB + 2AM. in ((m)) time. Recalling the definition (19), we have the conclusion from ||c|loo S 1, so
c c x) Sc (5 - a)) + T(x -i)
S ||cl || æ|l1 + T. -x'-5) 2AM + AB + 2 S A.
We conclude by applying the solver from Corollary 2 to our resulting unconstrained linear program Proposition Let 2 0. We can compute x E X, an e e-apprxximate minimizer (22), in time n log(n)
Further, the objective value of x (22) is 20 2ddadiitive approximation of dCE.
Proof. Observe that for Ā = 4A, we have | < and nnz(A) = ((m)), since no column more than 2-sparse and all entries of A are in 1-1, Further, recalling the definition of U from (21), we have m = ! ). So, Corollary shows we can compute an s-approximate minimizer to
min c. Fx+ A
within the stated runtime. The rest of the proof follows using Round from Lemma 23, where we recall (dCE(D.) dCE (D,)) < E due to definition of U and Lemma 17.
D
27

---

C.4 Testing via LDTC
We now give analogs of Theorems and 3, using our solver in Proposition 3.
Theorem 4. Let 0 1 E2 S E1 I 1 satissfy E2, and let Cua (éI- for universal constant Cgr There an algorithm A which solves the (21,ea)-t calibration testing problem with n samples, which runs in time
o
n log(n))
(c1 82)²
Proof. Throughout the proof, let a = E1 Eg > 0. Consider the following algorithm.
1. For [U] = m 2 a' sample n 2
Cy samples to form an empirical distribution D.,, where o²
Cia is chosen so Lemma 3 guarantees dCE((D) (..) S & with probability 2 3.
2. Call Proposition 2 with <- to obtain B, an -additive approximation to |dCE
3. Return "yes" if S E2
+ 2 and return "no" otherwise.
Conditioned on the event that (dCE(D) dCE(D.)) S E.. we show that the algorithm succeeds. First, if dCE(D) S E2, then dCE(D,)) < E2 + 8 by assumption, and so 3 S E2 + 2 by Proposition 2, so the tester will return "yes." Second, if dCE(D) 2 E1, then dCE(D,) 2 &1
by assumption, so B 2 E1 2 by Proposition 2 and similarly the tester will return "no" in this case. Finally, the runtime immediate from Proposition 3 and the definition of a.
Theorem has the following implication for (standard) calibration testing, by letting E2 0. Corollary 3. Let E N and let En E (0, 1) be minimal such that it is iifomnation-theorttiele possible to solve the calibbbbatio testing problem with n samples. For some (E,,), there an algorithm A which solves the e-calibration testing problem with n samples, which runs in time
O (n² log(n)).
D Sample complexity lower bounds for calibration measures
Recent works [BN23, BGHN23a] have introduced other calibration measures (e.g. the convolved ECE and interval CE), given efficient estimation algorithms for them, and showed that they are polynomially related to the lower distance to calibration dCE. Therefore, an alternative approach to the (non-tolerant) testing problem for dCE is by reducing to testing problems for these measures. The main result of this section that this approach leads to suboptimal sample complexity: the testing problems for these measures cannot be solved given only ( data points {(,,, y1) he(m)
To establish this sample complexity lower bound, we construct a perfectly calibrated distribution Do and family of miscalibrated distributions D, parameterized by 0 belonging to finite set. We use DSn (and DØ to denote the joint distribution of n independent examples from Dy (and Do). In Lemma 24, we show that the total variation distance between D and the mixture E[D of D small unless is large, and thus distinguishing them requires large sample complexity. Consequently, the testing problem for a calibration measure has large sample complexity it assigns every Dn large calibration error. Finally, show every De indeed has large convolved ECE and interval CE, establishing sample complexity lower bounds for these measures in Theorems and 6.
To construct D, and Do, we consider ł values {urheet E 13 where = } उे for i E [t]. We will determine the value of N later. We also define the following distribution, a perfectly calibrated distribution which is related to the miscalibrated synthetic dataset used in Section 3.
Definition 8. The distribution Do of (v.y) E [0, 1] x {0,1} is defined such that the marginal distribution is uniform over {ui)eeq and [vo =
Fix a E (0, 1). For 0 & 1),, we define distribution D, of (v,y) v) E [0, 1] {0, 1) such that the marginal distribution of is uniform over (u.hee and [yle u.] u, + 0.a. In other words.
28

---

each conditional distribution given v is miscalibrated by but the bias takes random direction. We now follow standard approach by [IS03] bound the total variation between our distributions. Lemma 24. For any t N and E (0, 3).
2\ exp 11a4n2
1
drv Eo Eo(D
"D S
Here, construct the mixture distribution Eo ")", first draw 0 unit. {-1, and then draw independent examples from Da. We denote the distribution of the examples by Eo
Proof. By standard inequality between the total variation distance and the x2 distance, we have
dDv ()) 2
(F II
(25)
By Ingster's 's method [IS03] (see also Section 3.1 of [Can22]).
x (I
= E,,,
Σ
Σ
Do(u,, (lun,))2 (u,,
1,
(26)
Do(u;,5)
JE(U,1}
where the expectation is over 0, O' drawn i.dd unnif.
{-1,13A.
For every [t] we have
uutbaa
Do(u;, 1)Do (u;,1)
(0; + 0g)
0,0,0²
Do(u, 1)
Mi
u,l
and similarly
(1-u.-8aa)
(1-u;-0'on 0(a))
Do(u, O), Do(u; 0)
(0, 6 +
0,8,a²
t
uz))
Adding up the two equations, we get
(ut, Dolus:5)
0.
(1
00
Σ
S $77 21
jEfO,11
where the last inequality uses the fact that us E la 21. Plugging this into (26), we get
9a
x <Eo ( 20 " ") s Eg.0r
1+
0.6%
-
2f
im
9a n
< Eg 0'
exp
0,0%
21
9a2n
Eo.0r
exp
0:0,
28
1=1
Eg
exp
0?
-
(by Hoeffding's lemma)
812
i=1
88aa"12
exp
1.
8t.
Plugging this into (25) completes the proof.
D.I Lower bound for convolved ECE
We now introduce the definition of convolved ECE from [BN23], and show that for every 0 1)1,1) D, has large convolved ECE in Lemma 26. This allows us to prove our sample complexity lower bound for convolved ECE in Theorem 5, by applying Lemma 24.
29

---

Definition 9 (Convolved ECE [BN23]). Let : [0.1] be the periodic function with period 2 satisfying TT(v) if [0.1], 11, and TR(²) - if E [1 2]. Consider a distribution 'D over [0, 1] x 10, For (v.y) ~ D, define random variable ú π + 11), where n is drawn independentyy from (0, ) a parameter a 2 The a-convolved ECE defined as follows:
CECE, =- -|E[[y 1)|6
where the outer expectation is over the marginal distribution of é. and the inner expectation is over the conditional distribution of (y; v) given ú. It has been shown in (BN23] that cECE,, (D) E [0,
is a nonincreasing function of a 2 O and there exists a unique o² 2 0 satisfying cECE,, (D) = =
The convolved ECE cECE(D) is defined to be CECE.-
We also mention that the following relationship is known between cECE and dCE.
Lemma (Theorem [BN23]) For any distribution over [0, 1] x {0, 1}, it holds that
dCE(D) S cECE(D) - 2 dCE(D).
We have the following lower bound on cECE(D,):
Lemma 26. For integer t 2 3, choose a wiint' Then for every 0 (-1,1)
1
cECE(Do) 2
1001vInt
Proof. It suffices to show that cECE, 2 100tw/mt whenever o S 1008
Consider (v, 3) D and (u 17), where 17 drawn independently from NNO0, o²). By
standard Gaussian tail bounds, we have
Pr
m
(27)
6t
Next, consider function E j0, 1] > [4] such that E()) E argmin [u; 6|. Let & denote the event that u Me(e)- Let lg and I.g be the indicators of & and its complement, respectively. We have
[[(y v)le 0, o] 1 6 v]
(I is fully determined by and 0) (y independent of given v)
Ey | m] ue( = 1e0e
Taking expectation over v conditioned on 6, we have
E((y 0)0s
6||
Pr[E ū]0
Pr[E úla.
We also have
| ( v)1=
< E (v العااا 8]
s Pr[-E 0].
Therefore,
- i1| > Pr(E Pr|-E [].
Taking expectations over 0, we have
cEcE,((o) El[Ely v i|]| 2 Pr Pr(-E].
(28)
Whenever E does not occur, it must hold that | +1 Z which can only hold when |y/ > 57- Therefore, by plugging (27) into (28), we get
cECE, Z
12
1001
Theorem 5. If an c-CECE tester with n samples (Definition 5), for e E (0, }), then
n
Ω
2.5 In
0.25
30

---

Proof.
Without loss of generality, assume that S 10-3. Let t 2 be the largest integer satisfying
E E 100rvInt
We choose a tv/nt"
By Lemma 26, we have cECE(Da) 2 e for every 0 E (-1,1]. By the guarantee of the tester, we have
drv (D [ 1
Combining this with Lemma 24, we get Q(aa (v) -2( .5 In t), the claim holds.
D.2 Lower bound for (surrogate) interval CE
The interval calibration error was introduced in [BGHN23a] as modified version of the popular binned ECE to obtain a polynomial relationship the lower distance calibration (dCE). To give an efficient estimation algorithm, [BGHN23a] considered a slight variant of the interval calibration error, called the surrogate interval calibration error, which preserves the polynomial relationship. Below we include the definition of the surrogate interval calibration error, and its polynomial relationship with dCE. We then establish our sample complexity lower bound (Theorem 6) for surrogate interval CE by showing that every Do has a large surrogate interval CE (Lemma 28).
Definition 10 (BBGHN23a)) For a distribution D over [0, 1] x {0, 1} and an interval width parameter > O, the random interval calibration error is defined be
w)) L. Σ JEZ
ILo u)l(U E [21]]
(29)
where the outer expectation is over r drawn uniformly from [0, w) and I the interval [r je, r (j 4 1)e). Note that although the summation is over j E Z, there are only finitely many j that can
contribute to the sum (which are the that satisfy 17.5 n | 1] + 0). The surrogate interval calibration ervor defined as follows:
SintCE(D) == inf (RintCE(D,22*)+222) - kEZ
Lemma 27 (Theorem 6.11, (BGHN23al). For any distribution DD over [0, 1] x {0. 1), it holds that dCE(D) S SintCE(D) S <6vdCE(D),
1. Lemma 28, Fort E N, let a
Then for every 0 E 1-1, 13,, it holds that SintCE(D,) 2 1 3t
3
Proof. It suffices to prove that RintCE(Ds, w) 2 32 whenever w < 1. where we recall the definition 32 (29). Fix some E (0, 1]. Every u, belongs to the interval 1"), for unique j: Z. Since the interval width is smaller than the gap between u, and uy for distinct f, we have j. je. Therefore,
Σ JEZ
[(uu)~o[(y - v)l(u E r3)l
[E(o.a) - w)0(v E r.,, kE(()
Σ
[Dw v)0(c = wz)]]
<E(C)
Σ
Pr[u u.[Ely a/e u.]
(E((]
3t
Plugging this into (29), we get RintCE w)
1
Theorem 6. If A is e e-SinCEE tester with samples (Definition 5), for e (0, f)), then
n = Ω
2.5
31

---

Proof. Choose t 2 1 to be the largest integer satisfying 1 2 E, and choose By Lemma 28,
3: SintCE(Do)) 2 = for every 0 E 1-1,1}* By the guarantee of the tester, we have
1
dTv(D) ")) 3
Combining this with Lemma 24, get ((P)) 2((=-2.0)
32

---

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: We claimed a novel testing problem for measuring calibration, faster algorithms for solving it, and lower bounds for altemative measures. This is precisely what we provide.
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.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We explain that our basic tester does not solve the tolerant testing problem in regimes, and that our more powerful tolerant tester has a slower runtimes. We also state that our practical implementation is preliminary and could be optimized.
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 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 used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
33

---

Answer:
[Yes]
Justification:
We give full, detailed proofs of all theoretical claims.
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 proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in 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 the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We provide a complete description of our experimental setups, and all of the relevant code in the supplementary material for reproducibility.
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 be 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 to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e-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-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 particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
34

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
As previously mentioned, we give full descriptions and provide our code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a 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:
wttps.cc/ppblccc//eccccccpcppppp gewic//guuee...eee CoodeSummii agionPolicy for more details.
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. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, 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/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: See above.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or 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:
We replicated our experiments across multiple runs and provide error bars.
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, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
35

---

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.
OK to report 1-sigma error bars, but one should state 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 are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We describe all our computing environments and provide runtime metrics.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as 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 into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
We read the ethics guidelines and believe we meet them.
Guidelines:
The answer NA means that the authors have not 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., there a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: We provide new tool for assessing calibration, a measure of interpretability of models, which is not tied to any particular societal application, and do not foresee pathway to use this tool for negative societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or 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.
36

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is 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 out 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 being used 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 monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We only use simple synthetic or public datasets for our experiments.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have 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 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. Lieenses for existing assets
Question: 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?
Answer: [Yes]
Justification: We made sure to cite all relevant code and data used in our experiments.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/dataseta 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.
37

---

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 assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was 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 to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing 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 as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, 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: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
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 NeurlPS 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.
38


Reviews:
[{"review_id": "s0UH7d4tic", "reviewer": "Reviewer_q4wr", "summary": "This paper studies testing the calibration of predictors through joint distributions and contributes efficient methods using appropriate measures.", "questions": "Major Questions:\n- Definition 1, clarify the empirical forms of dCE and ECE and the benefits dCE brings about.\n- \"Page 3 Line 83\" and Theorem 1 disagree about the information-theoretic possibility.\n- Page 8 Line 288: it is unclear how Lemma 4 is achieved, more explanations are needed.\n\nMinor Questions:\n- Page 5 Line 168: why 2(n 2) constraints?\n- Page 5 Line 175: the exact use of triangle inequality is needed here.\n- In (5), why did it switch from max to min?\n\nSuggestions:\n- Clarify if Theorem 1 solves with smCE and Theorem 2 solves with LDTC. It is not clear why Theorem 2 suffers additional complexity.\n- Deferred definitions (4 and 5) seem central and need to be included in the paper.", "limitations": "The authors spread the limitations throughout the paper, so a summary section is suggested, possibly in the form of a conclusion.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "Originality: \nThere are new methods.\nThe work can be considered a novel combination of well-known techniques. \nIt is clarified how this work differs from previous contributions. \nRelated work appears to be adequately cited.\n\nQuality: \nThe submission appears to be technically sound. \nThe claims are rather well supported with experimental results. \nThe methods used are appropriate.\nThis is a rather complete piece of work.\n\nClarity: \nThe submission is somewhat clearly written. \n\nSignificance: \nThe results seem important. \nOther researchers and practitioners will possibly use the ideas or build on them, owing to the code availability.\nThe submission seems to address a difficult task in a better way than previous works. \nThe work advances the state of the art as demonstrated via run-times. \nThe work provides provide unique theoretical and experimental approaches with demonstrated run-time gains.", "weaknesses": "Quality:\nThe authors are not careful (and possibly honest) about evaluating their work, specifically weaknesses and limitations.\n\nClarity:\nThe work is not well organized, many parts (deferred to appendix) need to be in the paper. \nThe work informs the reader in rather superficial level, with regards to exact implementations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for your careful reading – we are glad that you found our work to be complete, and that you found the results important. \n\nWe were confused by the reviewer’s comment about the lack of care or honesty in evaluating our work – we take such concerns very seriously, and would very much like to address any potential shortcomings that the reviewer found. We aimed to provide a thorough comparison between our work and prior calibration testers (see e.g., Section 1.3), and stated all runtimes and error rates explicitly for our algorithms. We would like to request: could the reviewer be more specific about what specific sections they found lacking? In particular, this comment did not seem to be brought up again in the reviewer’s more detailed questions. \n\nSimilarly, we regret that the reviewer found our organization lacking. We did our best to communicate the main takeaways from our paper, within the 9-page space constraints of the conference format, but will do our best to keep our main body more self-contained in the revision, e.g. move Definitions 4 and 5 to the body. Thank you for this suggestion.\n\nWe now address your more specific questions.\n\nThe empirical form of ECE and dCE are both the standard definitions (Lines 47, 63), but where the distribution D is the uniform distribution over samples (the empirical distribution). We will clarify this in our revision. In terms of benefits of dCE, the empirical ECE definition is meaningless for continuous distributions; simple counterexamples show that the empirical ECE cannot nontrivially approximate the ECE, e.g. $y$ is uniform in $\\{0, 1\\}$ and $v$ is independent and uniform in $[0.49, 0.51]$. We will include this counterexample in our paper, to augment Lines 48-50. In practice, binned variants of the empirical ECE are used instead (with the bin size as a hyperparameter); as discussed in Line 53, this has repeatedly been reported to cause stability issues in practice. Conversely, the empirical dCE has been observed in both theory and practice to not suffer from such stability issues, and also has no binning hyperparameter tuning required.\n\nLine 83 is a sample complexity lower bound which states we need at least $c/\\epsilon^2$ samples from some constant $c$. Our Theorem 1 uses $c’/\\epsilon^2$ samples for some $c’ > c$, so there is no contradiction. Note that a sample size can be simultaneously $\\Omega(1/\\epsilon^2)$ and $O(1/\\epsilon^2)$.\n\nLemma 4 is Theorem 7.3 in the prior work [BGHN23a]. To avoid redundancy, we refer to [BGHN23a] for the full proof, but at a high level, the side $\\text{smCE}<=2\\text{LDTC}$ follows from the definitions and $\\frac 1 2 \\text{LDTC} \\le \\text{smCE}$ is by LP duality. We actually prove a strengthening of this lemma holds in our Lemma 13. We will make sure this explanation is in the revision.\n\nRe: Line 168, here, we are referring to the linear constraints, so each absolute value corresponds to $2$ linear constraints. We have $\\binom{n}{2}$ absolute value constraints between coordinate pairs, and therefore $2\\binom{n}{2}$ when they are converted to linear constraints.\n\nRe: Line 175, we showed the exact use of the triangle inequality in the proof of Lemma 1 (Appendix B). We will add an appropriate forward reference to this.\n\nRe: (5), this was a typo, good catch. We can redefine $b := -b$, as the maximizing argument for $f$ is the minimizing argument for $-f$, and our algorithm uses no structure of $b$. We will clarify this.\n\nTheorem 2 suffers from additional complexity because it solves a more complicated problem of $\\text{LDTC}$, rather than $\\text{smCE}$. The constraints in $\\text{LDTC}$ do not correspond to a graph-structured linear program (e.g. min-cost flow), and therefore we are not able to give a combinatorial algorithm, relying on a new custom LP solver we develop. However, Theorem 2 is able to achieve stronger testing guarantees (i.e. it applies to tolerant testing).\n\nWe hope these responses were clarifying, and that they elevate the merit of our paper in your eyes. Thank you again for your reviewing efforts.", "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": "hHERxw02oR", "reviewer": "Reviewer_F42r", "summary": "The paper studies the problem of *calibration testing*.\nHere, we are given a distribution $D$ over outcomes and the goal\nis to decide if the distribution is calibrated; specifically,\nthe property testing problem they formulate distinguishes\nbetween perfectly calibrated distributions and those that\nare $\\epsilon$-far from calibrated.\nA distribution $D$ over prediction-outcomes\n$[0, 1] \\times \\{0, 1\\}$ is said to be perfectly calibrated\nif $E_{(v, y) \\sim D}[y \\mid v] = v$. The \"distance to calibration\" defined here\nis based on [BGHN23a] which is intuitively an optimal transport\ndefinition;\nthey set $dCE(D)$ to be minimum of $E_{(u, v, y) \\sim \\Pi}[|u - v|]$\nacross all $\\pi$ such that $(v, y)$ has marginal distribution $D$\nand $(u, y)$ is a perfectly calibrated distribution.\n\nThe authors design a dynamic-algorithm based solver for the problem.\nA key insight here is a novel algorithm\nfor calculating the smooth calibration error\nby reformulating it as a min-cost flow linear program on specific graph.\nUtilizing the properties of the graph (which is a union of a star and a path),\nthe authors obtain a dynamic programming based algorithm which has an update time of $O(n \\log^2(n))$.\nThis improves on the existing bounds that are $O(n^{\\omega})$ where $\\omega$ is the matrix multiplication exponent.", "questions": "See weaknesses above. \nIn addition, I think adding further motivation for the problem of testing calibration could improve the paper.\n\n- The linear program (2) seems to be already provided in [BGHN23a]; see Theorem 7.14. If this is the case, it should be noted more clearly.\n- The theorem statements imply that $\\epsilon_n=\\Theta(n^{-1/2})$ is the range in which\n  the problem can be information theoretically solved. Lemma 5 provides a lower bound;\n  the upper bounds is Lemma 3; this should be noted in the intro.", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Strengths:\n- The paper is studies an interesting problem, is generally well-written, and makes important contributions.\n- The techniques are interesting, in particular the algorithm for calculating\n  the Smooth calibration error is of independent interest.", "weaknesses": "Weakness:\n- Framing: it appears to me that the main contribution of the paper is a new algorithm for calculating smCE.\n  Indeed, the main \"property testing\" part of the paper (excluding the appendix) seems to be Lemma 3 which is from\n  prior work. While the implications for property testing are interesting, it seems to me that they are\n  mostly known. Lemma 5 also seems standard for property testing and seems like it holds for a much more general\n  class of testing problems, rather than being specific to calibration.\n- Proof of Lemma 2 should be better explained (especially since it is the central insight in the paper).\n  For instance, what does each variable of the program correspond to in the flow?\n  How does optimization problem (7) intuitively correspond to the min-flow problem of the graph specified\n  in Lemma 2? What does the constraint $B^Tf=d$ mean here?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your encouraging review. We are glad that you found the problem we study interesting, and that our paper makes important contributions to it.\n\nWe apologize for any confusion in framing. We agree that our Theorem 1 is really just a fast solver for the empirical smCE. However, we presented our paper through the lens of calibration testing, a problem of significant practical and theoretical interest, because it is the main overall problem we address. The reason we designed a nearly-linear time smCE algorithm is exactly because of its implications for calibration testing (building upon results from [BGHN23a], who relied on black-box LP solvers and did not give a fast algorithm). We also provide a suite of additional results on calibration testing, e.g. a tolerant tester in Appendix C which does not go through smCE, and sample complexity lower bounds in Appendix D which use other calibration metrics. We will clarify the organization of the paper so that the framing is more clear.\n\nRe: Lemma 2, our claim in (7) is that for any matrix $B$ and vectors $d, c$, the linear program $\\max d^T x$ s.t. $Bx \\leq c$ has an equivalent dual $\\min c^T f$ s.t. $f \\geq 0$, $B^T f = d$. This statement uses nothing about the graph structure of our LP. We chose the letters $f$ for the dual LP variable (the Lagrange multipliers for the primal Lipschitz constraints $Bx \\leq c$) because it happens to be that our constraint matrix does have graph structure, so $f$ is naturally interpreted as a flow. In particular, our matrix $B$ is the adjacency matrix of a graph. In particular, the way we defined $B$ (in 6) means every row of $B$ has one $1$ and one $-1$. Thus, $B^T f = d$ is just specifying the net amount of flow going into each vertex (d is the vertex demands); each entry of $B^T f$ sums all the flows leaving a vertex, and subtracts all the flows coming in. We will make sure to add more explanation of this intuition in the revision; you are right that it is rather terse at present.\n\nYou are correct that the linear program formulations of smooth calibration (2) and lower distance to calibration (Lemma 18) are both from [BGHN23a]. Our main contribution is a new efficient algorithm for exactly solving (2) via solving a structured min-cost flow problem. We also provide a faster approximation algorithm for the LP formulation in Lemma 18. We will make sure it is more clearly stated that both the LPs corresponding to smCE and LDTC are from [BGHN23a].\n\nWe will also make sure to add a paragraph in the revision pointing out the sample complexity bounds you mention, and explaining their implications more clearly.\n\nThank you for your careful reading and valuable feedback once again; we hope this discussion was clarifying, and elevates the merits of our paper in your view.", "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": "mpS4EqSedt", "reviewer": "Reviewer_rwaD", "summary": "This paper introduces a property testing formulation of verifying calibration, along with efficient algorithms for solving this problem as well as a relaxed/tolerant version. The empirical results support the theory and justify the efficacy of the proposed algorithms.", "questions": "- The DenseNet experiments rely on heavily subsampling the test data; this should not be necessary for the proposed approach correct? It seems to me that even the compared-to approaches should be fine on CIFAR-10-scale data without subsampling? Additionally, the subsampling setup seems somewhat arbitrary - would it be possible to provide more justification on the chosen sample size, the number of samples, etc.?\n\n- What is referred to as ConvECE in the paper was actually introduced as SmoothECE, correct? It would be useful to clarify this.", "limitations": "Limitations were discussed throughout the paper, although there is no separate limitations section.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**Originality:** The calibration testing formulation is new (although a natural extension of prior work [1]), and consequently the algorithm for solving the problem is also new.\n\n**Quality:** The paper is technically sound. I did not check the main proof details in the appendix, but I did check the in-lined proofs in the main body and I saw no issues.\n\n**Clarity:** Overall, the paper is straightforward to read and the necessary background is properly introduced.\n\n**Significance:** There has been a significant amount of recent theoretical work on how to properly measure calibration, and this paper makes a nontrivial contribution both in terms of perspective and methodology.\n\n[1] https://arxiv.org/abs/2203.01850", "weaknesses": "Overall, I find the paper strong in what it sets out to achieve (and thus recommend accept); the main weakness in my view is proper contextualization and how to apply the ideas to larger scale calibration settings.\n\nIn particular, while the authors emphasize how different calibration metrics such as smoothECE perform worse for property testing, it would be interesting to have more concrete applications to model comparison in practice. For example, are there instances where comparing models using directly computed calibration metric values (i.e. ranking by smoothECE) leads to spurious rankings that would have been detected by testing with dCE? The results in Table 1 suggest this should be the case, but I think more clearly demonstrating how the proposed framework can be used as a better comparison method in practical settings would be very useful. Relatedly, I have some questions regarding the DenseNet experimental setup that I outline below under Questions.\n\nMinor Comments:\n- There seems to be some mixing up of directed/undirected throughout Lemma 2.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your encouraging feedback. \n\nWe agree with you that applications of our results to model selection in more concrete settings is an exciting potential implication of our paper, and believe that this is a natural further direction to take our techniques. Because the algorithmic theory of efficient calibration testing was relatively less-studied prior to our work, we chose to make this topic the focus of our paper. As you suggested, in light of the difficulties in practice encountered when using binned ECE variants (Line 53), it is very interesting to see if we can provide practical criteria for settings where dCE succeeds at measuring calibration but binned alternatives such as smoothECE are less reliable. We believe this question is highly-related to the questions we study, but outside our intended scope, and defer a more thorough investigation to future work.\n\nThanks for pointing out consistency issues in Lemma 2. We will do a thorough pass to clarify this in our revision; it is intended that $G$ (as in the lemma statement) is undirected, and $\\widetilde{G}$ (as in the proof) is a directed graph, constructed from splitting edges in $G$.\n\nOur method indeed works for the dataset without subsampling. We aimed to make our experimental design decisions consistent with those used in the paper “On Calibration of Modern Neural Networks,” to show that smooth calibration is a reliable calibration measure. However, our method works fine without subsampling; indeed, our experiments suggest that our algorithm should scale better to large dataset sizes than alternative LP-based approaches.\n\nWe renamed smECE to convECE because smECE and smCE are different, and we thought this similar naming might confuse readers, as smCE is central to our paper. We will clarify this point.", "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": "Hs4Cxw1WjS", "reviewer": "Reviewer_nmkM", "summary": "This paper considers the property testing of calibration, under the lower distance to calibration metric. By property testing, the authors adapt the standard definition in the TCS literature, where if the distance is at least $\\epsilon$ then the algorithm will reject, and accept if the distance is 0. The main contributions are algorithms for solving the aforementioned testing problem in nearly linear time, in particular, authors show that\n\n* The $\\epsilon$-calibration testing problem could be solved in time $O(n\\log^2 n)$;\n\n* For a tolerant version of calibration testing, where the algorithm accepts if the distance $\\leq \\epsilon_1$ and rejects if the distance $\\geq \\epsilon_2$, there is an algorithm that solves it in $O((\\epsilon_1-\\epsilon_2)^{-2} n\\log n)$ time. If one chooses $\\epsilon_1-\\epsilon_2=1/\\sqrt n$, which is the information-theoretically smallest possible choice, then the runtime is nearly quadratic: $O(n^2 \\log n)$.\n\nThe first result relies on solving the LP associated to the smooth calibration error, formulating it as a min-cost flow on a path graph adjoint by a single vertex. They show this structured LP could be solved with simple dynamic programming plus segment trees, without resorting the heavy machinery of IPMs and they empirically verify their algorithm outperforms commercial solvers (which is not very surprising, since the graph is so simple).\n\nThe second result solves a harder LP, using the rounding framework for combinatorial optimization, particularly solvers that could utilize area convexity well due to Sherman and extended by Jambulapati, Sidford and Tian. This improves upon using the state-of-the-art LP solver in a black-box way.", "questions": "A few questions:\n\n* For smooth calibration, the runtime seems not depending on $\\epsilon$. Is that because $\\epsilon$ is chosen as $1/\\sqrt n$, or smooth calibration is a constant factor approximation to lower dCE hence $\\epsilon$ is a constant? I think it's important to clarify what role does $\\epsilon$ play in the smooth calibration program.\n\n* Do you think the method of transforming smooth calibration to computing a min-cost flow on a path adjoint with a vertex could be generalized to other programs where the constraints are encoding Lipschitzness among the data points? Or is the definition of vector $b$ crucial here?\n\nA few comments:\n\n* For LP solvers, consider citing the state-of-the-art result by Jiang, Song, Weinstein and Zhang, STOC'21.", "limitations": "Yes.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The theoretical results in this paper are quite interesting. This seems to be the first paper to formalize calibration as a property testing problem, and they give fast algorithms under the lower distance to calibration error. Techniques are not complicated but neat. In particular, authors show that the smooth calibration error LP could be cast into a min-cost flow problem on a simple, planar graph. Utilizing the graph structure, they develop combinatorial, dynamic programming-based approach that runs in nearly linear time. This is in drastic difference from most endeavors in algorithmic optimization community, where most works focus on developing complicated data structures and machinery to solve an IPM. This also enables authors to implement their algorithm and compares with CVXPY / commercial solvers in terms of efficiency, which is not known for most theoretically-efficient LP solvers since 2019.", "weaknesses": "The paper is overall well-written with solid results, however the paper format of NeurIPS is not particularly suitable for this paper. Theoretically, it also contains an algorithm for tolerant calibration testing, and a sample complexity lower bound. However, these results are only roughly conveyed in the main body of the paper. I wonder whether journals (JMLR, TMLR) or conferences such as COLT might be a better fit.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive review and careful reading. We are also encouraged that we were able to develop a practical solver for our LP of interest by using its structure, which uses less sophisticated tools than the recent LP solvers from the TCS community.\n\nTheorem 1’s runtime does not depend on $\\epsilon$ because our method exactly solves the empirical smCE problem. This is made possible by designing an exact solver for the corresponding LP, a structured min-cost flow instance. The $\\epsilon \\approx 1/\\sqrt{n}$ error in the tester is entirely due to the inaccuracy from the sampling process, see Lemma 3. On the other hand, the LP solver we designed in Theorem 2 is only approximate, leading to two sources of error in the final guarantee. We will clarify these distinctions in our revision.\n\nThank you for your insightful question about generalizations of our approach in Appendix B.2. Indeed, we are optimistic that our approach generalizes to other settings; in follow up work, we extended our algorithm to handle structured quadratic programs with Lipschitz constraints, a common problem formulation in isotonic regression (see e.g. the LPAV subproblem in “Efficient Learning of Generalized Linear and Single Index Models with Isotonic Regression”). \n\nWe believe you can convert Lipschhtiz encoding constraints for linear programs to a min-cost flow problem problem with the structure you mentioned. The value of $b$ is not important here; it can range $[-1,1]$. This question is exactly what we are considering for the next step. We are working on a problem called LPAV, which involves solving quadratic programs with Lipschtiz constraints, and we are also looking for other problems with Lipschtiz constraints.\n\nWe will add a reference to [JSWZ21] in our revision; thank you for the reminder.", "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:

Meta-review: This paper proposes a new method to test calibration, based on several types of optimization approaches. All reviewers were in agreement that this is a rigorous and well executed paper.
Decision: Accept (poster)