Testing Calibration in Nearly-Linear Time

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 * The $\epsilon$-calibration testing problem could be solved in time $O(n\log^2 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)$. The 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). The 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.

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.

Questions

A few questions: * 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. * 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? A few comments: * For LP solvers, consider citing the state-of-the-art result by Jiang, Song, Weinstein and Zhang, STOC'21.

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

Yes.

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.

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. **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. **Clarity:** Overall, the paper is straightforward to read and the necessary background is properly introduced. **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. [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. In 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. Minor Comments: - There seems to be some mixing up of directed/undirected throughout Lemma 2.

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.? - What is referred to as ConvECE in the paper was actually introduced as SmoothECE, correct? It would be useful to clarify this.

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Limitations were discussed throughout the paper, although there is no separate limitations section.

Summary

The paper studies the problem of *calibration testing*. Here, we are given a distribution $D$ over outcomes and the goal is to decide if the distribution is calibrated; specifically, the property testing problem they formulate distinguishes between perfectly calibrated distributions and those that are $\epsilon$-far from calibrated. A distribution $D$ over prediction-outcomes $[0, 1] \times \{0, 1\}$ is said to be perfectly calibrated if $E_{(v, y) \sim D}[y \mid v] = v$. The "distance to calibration" defined here is based on [BGHN23a] which is intuitively an optimal transport definition; they set $dCE(D)$ to be minimum of $E_{(u, v, y) \sim \Pi}[|u - v|]$ across all $\pi$ such that $(v, y)$ has marginal distribution $D$ and $(u, y)$ is a perfectly calibrated distribution. The authors design a dynamic-algorithm based solver for the problem. A key insight here is a novel algorithm for calculating the smooth calibration error by reformulating it as a min-cost flow linear program on specific graph. Utilizing the properties of the graph (which is a union of a star and a path), the authors obtain a dynamic programming based algorithm which has an update time of $O(n \log^2(n))$. This improves on the existing bounds that are $O(n^{\omega})$ where $\omega$ is the matrix multiplication exponent.

Strengths

Strengths: - The paper is studies an interesting problem, is generally well-written, and makes important contributions. - The techniques are interesting, in particular the algorithm for calculating the Smooth calibration error is of independent interest.

Weaknesses

Weakness: - Framing: it appears to me that the main contribution of the paper is a new algorithm for calculating smCE. Indeed, the main "property testing" part of the paper (excluding the appendix) seems to be Lemma 3 which is from prior work. While the implications for property testing are interesting, it seems to me that they are mostly known. Lemma 5 also seems standard for property testing and seems like it holds for a much more general class of testing problems, rather than being specific to calibration. - Proof of Lemma 2 should be better explained (especially since it is the central insight in the paper). For instance, what does each variable of the program correspond to in the flow? How does optimization problem (7) intuitively correspond to the min-flow problem of the graph specified in Lemma 2? What does the constraint $B^Tf=d$ mean here?

Questions

See weaknesses above. In addition, I think adding further motivation for the problem of testing calibration could improve the paper. - 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. - The theorem statements imply that $\epsilon_n=\Theta(n^{-1/2})$ is the range in which the problem can be information theoretically solved. Lemma 5 provides a lower bound; the upper bounds is Lemma 3; this should be noted in the intro.

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

N/A

Summary

This paper studies testing the calibration of predictors through joint distributions and contributes efficient methods using appropriate measures.

Strengths

Originality: There are new methods. The work can be considered a novel combination of well-known techniques. It is clarified how this work differs from previous contributions. Related work appears to be adequately cited. Quality: The submission appears to be technically sound. The claims are rather well supported with experimental results. The methods used are appropriate. This is a rather complete piece of work. Clarity: The submission is somewhat clearly written. Significance: The results seem important. Other researchers and practitioners will possibly use the ideas or build on them, owing to the code availability. The submission seems to address a difficult task in a better way than previous works. The work advances the state of the art as demonstrated via run-times. The work provides provide unique theoretical and experimental approaches with demonstrated run-time gains.

Weaknesses

Quality: The authors are not careful (and possibly honest) about evaluating their work, specifically weaknesses and limitations. Clarity: The work is not well organized, many parts (deferred to appendix) need to be in the paper. The work informs the reader in rather superficial level, with regards to exact implementations.

Questions

Major Questions: - Definition 1, clarify the empirical forms of dCE and ECE and the benefits dCE brings about. - "Page 3 Line 83" and Theorem 1 disagree about the information-theoretic possibility. - Page 8 Line 288: it is unclear how Lemma 4 is achieved, more explanations are needed. Minor Questions: - Page 5 Line 168: why 2(n 2) constraints? - Page 5 Line 175: the exact use of triangle inequality is needed here. - In (5), why did it switch from max to min? Suggestions: - Clarify if Theorem 1 solves with smCE and Theorem 2 solves with LDTC. It is not clear why Theorem 2 suffers additional complexity. - Deferred definitions (4 and 5) seem central and need to be included in the paper.

Rating

5

Confidence

2

Soundness

2

Presentation

2

Contribution

2

Limitations

The authors spread the limitations throughout the paper, so a summary section is suggested, possibly in the form of a conclusion.