REVIEW 2 major objections 5 minor 23 references
An analysis of binary isotonic regression: degrees of freedom and implications for calibration
T0 review · 2 major / 5 minor · reviewed 2026-08-01 · deepseek-v4-flash
Pith's one-line read The paper proves the exact worst-case number of distinct fitted values of isotonic regression on binary sequences, with leading constant 3/(4π²)^{1/3} n^{2/3}, and uses it to obtain a distribution-free bound on the expected calibration erro
desk verdict Sharp dof constant for binary isotonic regression with a clean ECE payoff; one real but easily fixable ordering mistake in the lower-bound construction. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the level-set averaging property of isotonic regression, which forces each fitted value to equal the mean of the binary labels in its block and therefore to be a rational number a/b. The worst-case analysis then reduces to a number-theoretic optimization: choose as many distinct reduced fractions as possible whose denominators sum to at most n. This optimization is solved using the Farey sequence and Euler's totient function φ(b); the leading constant emerges from the asymptotic Σ_{j≤K} φ(j) = 3/π² K² + O(K log K). The minmax formulation of isotonic projection verifies that the constructed binary sequence realizes the bound. For the calibration application, a Berns
What would settle it
Compute the exact maximum in Eq. (5) for n up to 10^9 and compare to c n^{2/3}; a faster-growing error term would invalidate the leading constant. For the ECE claim, construct the extremal distribution from the Farey-block sequence (X supported on the blocks, Y equal to the block mean) and measure the ECE for increasing n; if it fails to decay at roughly n^{-1/6} (or fails to decay at all), Theorem 2 is falsified.
Extended reading notes
Core claim
The central claim is that the number of unique fitted values of the isotonic regression of a binary sequence of length n is exactly the largest integer of the form 1 + Σ_{j=1}^{K-1} φ(j) + ℓ subject to 1 + Σ_{j=1}^{K-1} jφ(j) + ℓK ≤ n, where φ is Euler's totient function; this equals 3/(4π²)^{1/3} n^{2/3} + O(n^{1/3} log n). The proof works by exploiting isotonic regression's level-set averaging property: every fitted block has as its value the average of the binary labels in that block, so the block values are distinct rational numbers a/b. To maximize the number of blocks one uses reduced fractions with the smallest possible denominators, namely the Farey sequence, and the totient function
Load-bearing premise
For the calibration theorem, the covariate X must be univariate real-valued so that the blocks of isotonic regression correspond to intervals; the proof and stated Remark 4 indicate this assumption is necessary for the empirical-process bound over intervals.
Editorial extensions
If this is right
- Isotonic regression on binary labels deterministically has sublinear degrees of freedom (O(n^{2/3})), so its fitted values are a low-complexity representation of the data even without any noise or smoothness assumptions.
- Isotonic calibration is guaranteed to reduce expected calibration error to zero at rate n^{-1/6}√log n for any joint distribution with Y∈{0,1} and univariate X, with no model assumptions.
- The deterministic bound also applies to any level-set averaging method, such as histogram binning and unimodal regression; for methods whose preimages are low-complexity sets, analogous calibration guarantees can be derived.
- The extremal binary sequence is explicit, so the bound is tight at every n; one can construct data that achieve the maximal degrees of freedom.
- The results hold for any preordering of the samples (including partial orders and ties) as an upper bound, generalizing the usual total-order isotonic regression.
Reading between the lines
- The appearance of the Farey series and the constant 3/(4π²)^{1/3} suggests the problem is equivalent to counting lattice points on convex curves (via Jarník's theorem), which may open connections to other shape-restricted estimators that produce rational fitted values.
- Because the authors conjecture that the expected degrees of freedom under i.i.d. sampling is O(n^{1/3}) rather than n^{2/3}, the ECE rate for real data may be substantially faster (possibly n^{-1/3}); the worst-case bound would then be conservative for typical applications.
- The restriction to univariate X is essential to the proof technique; a multivariate extension would require controlling the complexity of PAVA-block preimages in R^d, which are connected but not intervals, so a genuinely different argument would be needed.
- The explicit worst-case construction provides a natural adversarial distribution for benchmarking calibration estimators: one can test whether a proposed ECE estimator or calibration method fails on the Farey-block data.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the worst-case degrees of freedom, measured by the number of distinct fitted values, of isotonic regression on binary sequences. Theorem 1 claims a sharp leading constant 3/(4π^2)^{1/3} n^{2/3} for the maximum number of fitted levels, using a Farey-fraction construction and classical totient-sum estimates. Theorem 2 applies this bound to prove a distribution-free O_p(n^{-1/6} sqrt(log n)) bound on the expected calibration error (ECE) of isotonic calibration when Y is binary and X is univariate. The proof of Theorem 2 combines the degree-of-freedom bound with an empirical-process inequality for intervals. The paper also discusses extensions to preorders and level-set-averaging algorithms, and includes a numerical conjecture about the lower-order error term.
Significance. If the proof issues are corrected, this is a substantial contribution. The sharp leading constant for the degrees of freedom of binary isotonic regression improves on the earlier 3 n^{2/3} bound of Dimitriadis et al., and the number-theoretic argument is elegant and independent of distributional assumptions. The ECE result appears to be the first nontrivial distribution-free guarantee for isotonic calibration, and the proof strategy is clean: it reduces calibration to controlling the number of fitted levels and applying a uniform interval empirical-process bound. The paper is also honest about limitations, especially in Remark 4 and the Discussion. However, the lower-bound construction in Theorem 1 is written with the wrong ordering, and the numerical verification in Proposition 9 is invalid because of integer overflow; both are fixable locally.
major comments (2)
- [§2.1, Eq. (4) and lower-bound construction] The sequence in Eq. (4) is ordered by denominator, not by value: for example, 1/3 and 2/3 appear before 1/4 and 3/4. The lower-bound proof says that y* is designed to output 'the first khat(y*) elements in the sequence Eq. (4)', but concatenating blocks in this order would produce non-monotone fitted values, so PAVA would merge blocks and the construction would not achieve the claimed count. The n=18 and n=19 examples in the same section actually use the value-sorted order (0, 1/4, 1/3, 1/2, 2/3, 3/4, 1). The proof should define the set of fractions counted in Eq. (5), sort that set by value, and then concatenate the corresponding blocks. The count is order-independent, so Eq. (5) is unaffected, but the proof as written is internally inconsistent and must be corrected.
- [Appendix D, Proposition 9] The Python code for the numerical verification uses dtype=np.uint64 for computing nK = 1 + np.cumsum(Ks*phi). For K = 10^8, nK is approximately 2 * 10^23, which exceeds the uint64 maximum of about 1.84 * 10^19. The cumsum therefore silently wraps around modulo 2^64, so the computed values of nK, RK, and the claimed bound δn ≤ 0.63 n^{1/6} are not valid. This does not affect Theorem 1 or Theorem 2, but it invalidates Proposition 9 and the numerical support for Remark 3. The code should use Python big integers (e.g., object dtype) or restrict the verification to K values for which nK does not overflow.
minor comments (5)
- [Eq. (5)] The leading '1' in the expression 1 + Σ_{j=1}^{K-1} φ(j) + ℓ is not explained. Please clarify that this accounts for the block with value 1/1 and that φ(1)=1 is being used in the summation, or define the counting convention explicitly.
- [Theorem 2 statement] The notation P( Δ(fhat) ≥ O( sqrt(log(n/δ)/n^{1/3}) ) ) ≤ δ is informal. It would be clearer to state the bound with explicit universal constants, even if the constants are not optimized.
- [Abstract and Introduction] The phrase 'fully sharp finite-sample characterization' is a little strong: Theorem 1 gives the sharp leading constant with an O(n^{1/3} log n) error term, not a closed-form finite-sample expression. Consider rephrasing to 'sharp up to the leading term'.
- [References and formatting] There are several encoding/formatting glitches in the references: 'B lasiok' should be 'Błasiok', 'Fris´ en' should be 'Frisén', and 'Jarn ´ ık' should be 'Jarník'. Please clean these up.
- [Lower-bound proof wording] The phrase 'the first khat(y*) elements in the sequence Eq. (4)' should be replaced by a description of the set of fractions counted in Eq. (5), sorted by value. This would prevent the contradiction with the examples.
Circularity Check
No significant circularity: the DoF bound is a standalone counting construction and the ECE bound applies it honestly.
full rationale
The derivation chain is self-contained and does not reduce any claimed prediction to its inputs. Theorem 1 upper-bounds the number of fitted values by arguing that each PAVA block of a binary sequence must have a distinct reduced fraction a/b as its mean, so the maximal number of blocks is governed by the totient summatory function; the proof then uses standard external number-theory facts (Hardy–Wright Theorem 330, Abel summation in Apostol) to obtain the leading constant. The lower bound explicitly constructs a binary sequence from Farey fractions and verifies the fit via the minmax characterization from Robertson et al. (1988). No fitted parameter is renamed as a prediction, and no quantity that appears in the target (e.g., the ECE) is used as an input to the proof. Theorem 2 is a genuine distribution-free guarantee: it decomposes ECE into two empirical-process deviation terms over intervals, bounds those uniformly via Lemma 3, and then invokes the deterministic DoF bound from Theorem 1. The population ECE is only the left-hand side to be bounded; it is never fit or assumed. The proof explicitly notes the univariate-X assumption is needed for interval preimages (Remark 4), which further confirms the bound is not hiding distributional assumptions. The self-citations (Rossellini et al. 2025) are contextual and non-load-bearing; the in-sample calibration claim they support also follows directly from level-set averaging and is not needed for the main theorems. No uniqueness theorem from the same authors is invoked, and no ansatz is smuggled in via citation. The only notable flaw in the manuscript is an expositional inconsistency in the lower-bound construction: Eq. (4) orders fractions by denominator, whereas the n=18/n=19 examples use value-sorted order. This affects the literal reading of the construction but is order-independent for the counting in Eq. (5), so it is a fixable exposition/correctness issue rather than circularity. Overall, the central claims have independent mathematical content and are not circular.
Assumptions & free parameters
assumptions (6)
- domain assumption Level-set averaging property of isotonic regression (Eq. 3) holds for all y (Lee 1983).
- domain assumption Minmax representation of isotonic projection (Robertson et al. 1988).
- standard math Asymptotic estimate Σ_{j≤K} φ(j) = 3/π² K² + O(K log K) (Hardy & Wright, Theorem 330).
- standard math Abel's summation identity (Apostol).
- standard math Bernstein's inequality and the uniform empirical-process bound over intervals (Lemma 3).
- standard math Existence of a monotone quantile transformation X = h(U) with U uniform.
Cite this review
Pith. "Pith review of An analysis of binary isotonic regression: degrees of freedom and implications for calibration." pith.science (2026). https://pith.science/paper/XRRHXJ2Y
@misc{pith2026260727301,
author = {Pith},
title = {Pith review of: An analysis of binary isotonic regression: degrees of freedom and implications for calibration},
year = {2026},
howpublished = {\url{https://pith.science/paper/XRRHXJ2Y}},
note = {Machine review of arXiv:2607.27301}
}
abstract
Isotonic regression is a canonical tool for estimating monotone functions and calibrating probabilistic predictors. We provide a fully sharp finite-sample characterization of its worst-case degrees of freedom on binary samples. Specifically, we identify the binary sequences that maximize the number of distinct fitted values produced by isotonic regression. We develop a sharp bound on the degrees of freedom with a leading term of $\frac{3}{(4\pi^2)^{1/3}} n^{2/3}$ using analytic number theory, improving on previous bounds. We then apply this result to calibration. Calibration is a central requirement for probabilistic prediction, and isotonic regression is a widely used post-processing method for improving calibration. Building on deterministic degrees-of-freedom bounds, we derive, to our knowledge, the first nontrivial distribution-free guarantee on the Expected Calibration Error (ECE) of isotonic regression. This ECE bound is fully model-free and distribution-free, only assuming $Y \in \{0,1\}$.
Reference graph
Works this paper leans on
-
[1]
Allen, S., Gavrilopoulos, G., Henzi, A., Kleger, G.-R., and Ziegel, J. (2025). In-sample calibration yields conformal calibration guarantees. arXiv preprint arXiv:2503.03841
arXiv 2025
-
[2]
Apostol, T. M. (2013). Introduction to analytic number theory . Springer Science & Business Media
2013
-
[3]
Berta, E., Bach, F., and Jordan, M. (2024). Classifier calibration with roc-regularized isotonic regression. In International Conference on Artificial Intelligence and Statistics , pages 1972--1980. PMLR
2024
-
[4]
B asiok, J., Gopalan, P., Hu, L., and Nakkiran, P. (2023). A unifying theory of distance from calibration. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages 1727--1740
2023
-
[5]
Dimitriadis, T., D \"u mbgen, L., Henzi, A., Puke, M., and Ziegel, J. (2023). Honest calibration assessment for binary outcome predictions. Biometrika , 110(3):663--680
2023
-
[6]
Fris \'e n, M. (1986). Unimodal regression. Journal of the Royal Statistical Society Series D: The Statistician , 35(4):479--485
1986
-
[7]
Ghosh, D., Banerjee, M., and Biswas, P. (2004). Binary isotonic regression procedures, with application to cancer biomarkers. The University of Michigan Department of Biostatistics Working Paper Series 1037, Berkeley Electronic Press
2004
-
[8]
Groeneboom, P. (2011). Vertices of the least concave majorant of brownian motion with parabolic drift
2011
Show all 23 references
-
[9]
Gupta, C., Podkopaev, A., and Ramdas, A. (2020). Distribution-free binary classification: prediction sets, confidence intervals and calibration. Advances in Neural Information Processing Systems , 33:3711--3723
2020
-
[10]
Hardy, G. H. and Wright, E. M. (1979). An introduction to the theory of numbers . Oxford university press
1979
-
[11]
and Wu, Y
Hu, L. and Wu, Y. (2024). Calibration error for decision making
2024
-
[12]
Jarn \' k, V. (1926). \"U ber die gitterpunkte auf konvexen kurven
1926
-
[13]
P., Schneider, J., and Teng, Y
Kleinberg, B., Leme, R. P., Schneider, J., and Teng, Y. (2023). U-calibration: Forecasting for an unknown agent. In The Thirty Sixth Annual Conference on Learning Theory , pages 5143--5145. PMLR
2023
-
[14]
Lee, C.-I. C. (1983). The min-max algorithm and isotonic regression. The Annals of Statistics , pages 467--477
1983
-
[15]
and Woodroofe, M
Meyer, M. and Woodroofe, M. (2000). On the degrees of freedom in shape-restricted regression. The annals of Statistics , 28(4):1083--1104
2000
-
[16]
Platt, J. et al. (1999). Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods. Advances in large margin classifiers , 10(3):61--74
1999
-
[17]
T., and Dykstra, R
Robertson, T., Wright, F. T., and Dykstra, R. L. (1988). Order Restricted Statistical Inference . Wiley, Chichester
1988
-
[18]
A., Barber, R
Rossellini, R., Soloff, J. A., Barber, R. F., Ren, Z., and Willett, R. (2025). Can a calibration metric be both testable and actionable? arXiv preprint arXiv:2502.19851
2025 arXiv
-
[19]
Soundararajan, K. (2009). Partial sums of the möbius function. Journal für die reine und angewandte Mathematik , 2009(631):141--152
2009
-
[20]
Sparre Andersen, E. (1954). On the fluctuations of sums of random variables ii. Mathematica Scandinavica , pages 195--223
1954
-
[21]
Van Der Laan, L., Ulloa-P \'e rez, E., Carone, M., and Luedtke, A. (2023). Causal isotonic calibration for heterogeneous treatment effects. In International Conference on Machine Learning , pages 34831--34854. PMLR
2023
-
[22]
and Elkan, C
Zadrozny, B. and Elkan, C. (2001). Obtaining calibrated probability estimates from decision trees and naive bayesian classifiers. In Icml , volume 1, pages 609--616
2001
-
[23]
and Elkan, C
Zadrozny, B. and Elkan, C. (2002). Transforming classifier scores into accurate multiclass probability estimates. In Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining , pages 694--699
2002
Reviewed August 1, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.