Testing Calibration in Nearly-Linear Time

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.

Theorem 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.

Thank 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”).

We 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.

We will add a reference to [JSWZ21] in our revision; thank you for the reminder.

Thank you for your encouraging feedback.

We 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.

Thanks 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$.

Our 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.

We 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.

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.

We 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.

Re: 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.

You 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].

We 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.

Thank 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.

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.

We 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.

Similarly, 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.

We now address your more specific questions.

The 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.

Line 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)$.

Lemma 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.

Re: 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.

Re: 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.

Re: (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.

Theorem 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).

We hope these responses were clarifying, and that they elevate the merit of our paper in your eyes. Thank you again for your reviewing efforts.