REVIEW 1 major objections 6 minor 1 cited by
High-Dimensional Calibration from Swap Regret
T0 review · 1 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read TreeCal reduces high-dimensional calibration to swap regret, achieving epsilon-calibration for any convex set and any norm after (diam(P)/epsilon)^{O(rho/epsilon^2)} rounds.
desk verdict Strong general upper bound and lower bound for high-dimensional calibration, but the main theorem hinges on an unproved labeled TreeSwap claim that the authors acknowledge in a footnote. 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 Bregman divergence $D_R(y|p)=R(y)-R(p)-\langle\nabla R(p),y-p\rangle$ used as a loss in $p$; it is a proper scoring rule whose minimizer is the mean of the outcomes, and Lemma 2.2 turns $D_R$-calibration error into exactly the full swap regret of those losses. The carrying mechanism is TreeSwap, a tree of sub-algorithms that feed interval-average losses to their children, instantiated with Follow-the-Leader to produce TreeCal and with Be-the-Leader as an unimplementable analytic stand-in whose external regret is non-positive. Because Follow-the-Leader on Bregman losses selects empirical averages, the distance between the two trees is a sum over levels of differences between consecutive cumulative averages, bounded by $O(\mathrm{diam}(P)^2 T/H^2)$. The parameter $\rho$, the infimum range of a 1-strongly convex regularizer, enters only through the swap-regret bound $3\rho T/L$, and it matches the optimal-rate constant of online linear optimization, so the calibration rate is inherited from the regret rate.
What would settle it
Check the labeled extension first: if a loss sequence and a labeling can be exhibited for which labeled full swap regret exceeds the bound claimed in Theorem C.1, the main calibration guarantee collapses. A direct numerical test on a two- or three-dimensional set, comparing TreeCal's measured calibration error to $\epsilon T$ across growing $T$, would also suffice, since the promised threshold is explicit: $T \ge (\mathrm{diam}(P)/\sqrt{\epsilon})^{O(\rho/\epsilon)}$ for squared calibration.
Extended reading notes
Core claim
On the paper's own terms, the central discovery is an exact equivalence: for any convex $R$, the full swap regret of the loss sequence $\ell_t(p)=D_R(y_t|p)$ equals the $D_R$-calibration error of the forecasts, and if $R$ is 1-strongly convex with respect to a norm then $D_R(y|p) \ge \|y-p\|^2$, so squared-norm calibration reduces to swap regret. TreeCal is exactly TreeSwap with Follow-the-Leader as the base learner on these Bregman losses; because Bregman divergence is a proper scoring rule, each Follow-the-Leader action is an empirical average of outcomes, which is why the forecast rule is identical for every $P$ and norm. The proof bounds TreeSwap run with the unimplementable Be-the-Leader algorithm, whose external regret is non-positive, and controls the gap to the actual Follow-the-Leader tree by the drift of consecutive cumulative averages; a labeled action set lets different tree intervals that output the same forecast be swapped separately. Choosing arity $H=\mathrm{diam}(P)/\sqrt{\epsilon}$ and depth $L=12\rho/\epsilon$ yields the claimed bound. The lower bound then runs the classical calibration-to-swap-regret reduction in reverse: a too-good calibration algorithm would violate a known swap-regret lower bound.
Load-bearing premise
The load-bearing premise is that TreeSwap's swap-regret bound extends to the labeled action set, where identical forecasts produced by different tree intervals are treated as distinct; the paper states this extension in a footnote, asserting the original proof applies without change rather than giving the modified argument.
Editorial extensions
If this is right
- If the main theorem is correct, any pair $(P,\|\cdot\|)$ for which online linear optimization admits an $O(\sqrt{\rho T})$ regret guarantee gets an $\epsilon$-calibration guarantee in $T=(\mathrm{diam}(P)/\epsilon)^{O(\rho/\epsilon^2)}$ rounds, with the algorithm unchanged.
- For the simplex with the $\ell_1$ norm, the negative-entropy regularizer has $\rho=\log d$, giving the $d^{O(1/\epsilon^2)}$ round upper bound for multiclass calibration; the squared-norm version needs only singly exponential dependence on $1/\epsilon$.
- For the Euclidean ball with the $\ell_2$ norm, the quadratic regularizer gives $\rho=1$, so $\epsilon$-calibration is achieved after $\exp(O(1/\epsilon^2))$ rounds, independent of the dimension.
- The lower bound rules out polynomial dependence on $1/\epsilon$: no algorithm can $\epsilon$-calibrate the $d$-simplex in $\mathrm{poly}(d,1/\epsilon)$ rounds for all $\epsilon$.
- The pure-action variant that samples from TreeCal's distributions inherits the same kind of guarantee after repeating each tree step and feeding averaged outcomes, so the reduction covers both distributional and pure calibration.
Reading between the lines
- Editorial extension: up to the tree-shape parameters $H$ and $L$, the same executable can be deployed by a forecaster who does not know which norm the evaluator will use, and it will realize the best available rate for whichever geometry actually appears.
- Editorial extension: a natural extension would replace Follow-the-Leader inside TreeSwap with a different external-regret subroutine, which could yield calibration algorithms for other divergences or better constants for particular sets without changing the reduction.
- Editorial extension: the same swap-regret-to-calibration lower-bound template should transfer to other norms, such as $\ell_p$ balls, whenever a matching swap-regret lower bound is known, suggesting exponential-in-$1/\epsilon$ lower bounds are a general phenomenon rather than a special feature of $\ell_1$.
- Editorial extension: the proof technique of comparing a real Follow-the-Leader tree to an ideal Be-the-Leader tree is effectively a stability estimate; it could be sharpened to instance-dependent calibration bounds that depend on the actual drift of empirical averages rather than the worst-case diameter.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies online calibration of multi-dimensional forecasts in a bounded convex set P under an arbitrary norm. Its main upper-bound result (Theorem 3.1 and Corollary C.5) states that if there exists a 1-strongly convex regularizer on P with range at most ρ, then the TreeCal algorithm achieves squared-norm calibration error at most εT after T ≥ (diam(P)/√ε)^{O(ρ/ε)} rounds, and norm calibration error at most εT after T ≥ (diam(P)/ε)^{O(ρ/ε^2)} rounds. The analysis identifies TreeCal with the TreeSwap algorithm instantiated with Follow-the-Leader, bounds the swap regret of the unimplementable Be-the-Leader variant using the TreeSwap theorem, and controls the drift between FTL and BTL. This recovers Peng's recent simplex bound d^{O(1/ε^2)} for ℓ1 calibration and gives a dimension-independent rate for ℓ2 balls. The paper also proves a lower bound showing that for ℓ1 calibration on the d-simplex, T = exp(Ω(min{d^{1/14}, ε^{-1/6}})) rounds are necessary to guarantee εT calibration error, strengthening Peng's d^{Ω(log 1/ε)} lower bound, and it gives an analogous ℓ2 lower bound in Theorem D.2.
Significance. If the missing labeled TreeSwap proof is supplied, this is a clean and significant contribution: the algorithm is identical across different choices of P and the norm, the rates are governed by the single parameter Rate(P, ‖·‖), and the lower bound strengthens the best known dependence on 1/ε. The conceptual reduction from calibration to full swap regret via Bregman divergences is elegant, and the paper is transparent about which parts of the argument rely on prior results. The main caveat is that the central upper bound currently depends on an unproved labeled-action extension of the TreeSwap theorem of [DDFG24], which the authors assert without presenting the modified argument. Because that extension is load-bearing, the significance of the paper is conditional until the gap is closed.
major comments (1)
- [Appendix C.1, Theorem C.1 and accompanying footnote] The labeled-action version of the TreeSwap bound is load-bearing and is not proved in the manuscript. In the proof of Theorem 3.1, the calibration error of TreeCal is bounded by applying Theorem C.1 to the labeled distributions \tilde{x}_t of TreeSwap.BTL; the chain of inequalities after Eq. (9) would collapse if the labeled swap-regret bound failed, and Claim C.3 explicitly uses labels to separate identical actions at different tree nodes. Theorem C.1 is presented as a consequence of Theorem 3.1 of [DDFG24], but the footnote immediately below it states that the analysis of [DDFG24] 'does not analyse the labeled version' and asserts that 'the proof goes through as is.' The reference to Eq. (8) of [DDFG24] does not by itself verify that the labeled action set \bar{P} = P × {0,1}^* satisfies the required inequality, because the original argument treats the unlabeled action set and the behavior of swap functions on labels is exactly what changes. I request that the authors supply a complete proof of the labeled version, or cite an independently verifiable source that contains it, before the main upper bound of Theorem 3.1 can be considered established.
minor comments (6)
- [Proof of Theorem 3.1, parameter choice] With the displayed choices L = 12ρ/ε and H = diam(P)/√ε, the final bound is (6ρ/L + 2·diam(P)^2/H^2)·T = (1/2 + 2)·εT = 2.5εT, not εT. The theorem's O(·) notation absorbs constant factors, but the sentence claiming that these choices guarantee Cal ≤ εT should be corrected, for instance by taking H = 2·diam(P)/√ε and L = 24ρ/ε.
- [Appendix D.1, application of Lemma 4.2] The proof states that diam_{‖·‖_∞}([-1,1]^d) = 1, but this diameter is 2. This introduces an extra factor of 2 in the reduction from calibration to swap regret; the lower bound is unaffected because constants can be absorbed by rescaling ε and c, but the displayed value should be corrected.
- [Appendix E, Theorem E.1] The symbol L is used both for the number of tree levels and for the unit dual-norm ball L = {f : ‖f‖_⋆ ≤ 1}, which makes statements such as 'summing over the L values of p ∈ supp(x_i)' and 'Rate(L, ‖·‖_⋆)' ambiguous; please disambiguate the two uses.
- [Algorithm 1, line 2] The line 'Write the base-H representation of t − 1 as t = (h_1 ··· h_L)' should read 'as t − 1 = (h_1 ··· h_L)', since the subsequent notation is inconsistent with writing t itself as the base-H tuple.
- [Proof of Claim C.3, Eq. (10)] The definition of \tilde{ν}(p,σ) uses \sum_t x_t((p,σ)) in the denominator while the numerator uses \tilde{x}_t((p,σ)); the subsequent equality with νσ holds because the labeled masses agree, but the asymmetry is confusing and should either be explained or the denominator should be written with \tilde{x}_t.
- [Corollary C.5, proof] The phrase 'incurring an additional factor of 2 in the exponent constant, as desired' is cryptic; it would be clearer to state that Theorem 3.1 is applied with ε replaced by ε^2 and that constants are absorbed by the O(·) notation.
Circularity Check
No significant circularity: the calibration bound follows from an independent swap-regret theorem; the labeled-extension footnote is an omitted proof, not a reduction.
full rationale
The derivation is self-contained modulo an independent swap-regret theorem. Lemma 2.2 proves an algebraic identity between full swap regret for Bregman losses and DR-calibration error, with no fitted parameters. Theorem C.1 restates the TreeSwap bound of DDFG24, which is parameter-free and does not contain the calibration conclusion, so the author overlap does not make the citation circular. Lemma 3.2 and Claim C.3 supply the internal FTL/BTL comparison, and the final bound follows by explicit choices H = diam(P)/sqrt(epsilon) and L = 12*rho/epsilon, up to absorbed constants. The lower bound likewise uses the standard calibration-to-swap-regret reduction and the external swap-regret lower bound of DFG+24. The single flagged item is the footnote in Appendix C.1: it admits DDFG24 did not analyze the labeled TreeSwap variant and asserts 'the proof goes through as is' without proof. That is an omitted proof in a load-bearing step and a genuine correctness risk, but it is not a by-construction equivalence between an input and a prediction, so it does not constitute circularity.
Assumptions & free parameters
assumptions (5)
- ad hoc to paper The TreeSwap swap regret bound (Theorem C.1 of [DDFG24]) holds for the labeled action set; the original paper did not analyze this labeled version, and the present authors assert the proof goes through without presenting it.
- domain assumption For the problem instance, there exists a convex function R : P -> R that is 1-strongly convex with respect to the target norm and has Bregman divergence range at most rho, i.e., Rate(P, norm) is finite.
- standard math The universal FTRL/mirror descent theorems of [SST11] and [GSJ24] hold, giving RateOLO(P,L) = Theta(Rate(P, norm)) for centrally symmetric P.
- standard math The swap regret lower bound of [DFG+24, Theorem 4.1] is correct.
- standard math The sequential Rademacher complexity bound of [RST15, Theorem 2] correctly bounds the martingale deviation used in the pure calibration variant.
Cite this review
Pith. "Pith review of High-Dimensional Calibration from Swap Regret." pith.science (2026). https://pith.science/paper/7NEGOXCX
@misc{pith2026250521460,
author = {Pith},
title = {Pith review of: High-Dimensional Calibration from Swap Regret},
year = {2026},
howpublished = {\url{https://pith.science/paper/7NEGOXCX}},
note = {Machine review of arXiv:2505.21460}
}
abstract
We study the online calibration of multi-dimensional forecasts over an arbitrary convex set $\mathcal{P} \subset \mathbb{R}^d$ relative to an arbitrary norm $\Vert\cdot\Vert$. We connect this with the problem of external regret minimization for online linear optimization, showing that if it is possible to guarantee $O(\sqrt{\rho T})$ worst-case regret after $T$ rounds when actions are drawn from $\mathcal{P}$ and losses are drawn from the dual $\Vert \cdot \Vert_*$ unit norm ball, then it is also possible to obtain $\epsilon$-calibrated forecasts after $T = \exp(O(\rho /\epsilon^2))$ rounds. When $\mathcal{P}$ is the $d$-dimensional simplex and $\Vert \cdot \Vert$ is the $\ell_1$-norm, the existence of $O(\sqrt{T\log d})$-regret algorithms for learning with experts implies that it is possible to obtain $\epsilon$-calibrated forecasts after $T = \exp(O(\log{d}/\epsilon^2)) = d^{O(1/\epsilon^2)}$ rounds, recovering a recent result of Peng (2025). Interestingly, our algorithm obtains this guarantee without requiring access to any online linear optimization subroutine or knowledge of the optimal rate $\rho$ -- in fact, our algorithm is identical for every setting of $\mathcal{P}$ and $\Vert \cdot \Vert$. Instead, we show that the optimal regularizer for the above OLO problem can be used to upper bound the above calibration error by a swap regret, which we then minimize by running the recent TreeSwap algorithm with Follow-The-Leader as a subroutine. Finally, we prove that any online calibration algorithm that guarantees $\epsilon T$ $\ell_1$-calibration error over the $d$-dimensional simplex requires $T \geq \exp(\mathrm{poly}(1/\epsilon))$ (assuming $d \geq \mathrm{poly}(1/\epsilon)$). This strengthens the corresponding $d^{\Omega(\log{1/\epsilon})}$ lower bound of Peng, and shows that an exponential dependence on $1/\epsilon$ is necessary.
Figures
Forward citations
Cited by 1 Pith paper
-
Calibration through the Lens of Indistinguishability
A survey arguing that calibration error is best understood as the degree to which two worlds, the predictor's and nature's, can be distinguished, and that this view unifies ECE, smooth calibration, CDL, and distance t...
Reference graph
Works this paper leans on
-
[1]
An elementary predictor obtaining distance to calibration
[ACRS25] Eshwar Ram Arunachaleswaran, Natalie Collina, Aaron Roth , and Mirah Shi. An elementary predictor obtaining distance to calibration. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1366–1370. SIAM,
work page 2025
-
[11]
Simult aneous swap regret minimization via kl-calibration
[LSS25] Haipeng Luo, Spandan Senapati, and Vatsal Sharan. Simult aneous swap regret minimization via kl-calibration. arXiv preprint arXiv:2502.16387 ,
-
[13]
High dimensional online calibration in polynomial t ime
[Pen25] Binghui Peng. High dimensional online calibration in polynomial t ime. arXiv preprint arXiv:2504.09096,
-
[1982]
Breaking the $T^{2/3}$ Barrier for Sequential Calibration
[DDF+24] Yuval Dagan, Constantinos Daskalakis, Maxwell Fishelson, Noa h Golowich, Robert Kleinberg, and Princewill Okoroafor. Breaking the t2/3 barrier for sequential calibration. arXiv preprint arXiv:2406.13668,
-
[1998]
Oracle efficient online multicalibration and omniprediction
[GJRR24] Sumegha Garg, Christopher Jung, Omer Reingold, and Aar on Roth. Oracle efficient online multicalibration and omniprediction. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 2725–2792. SIAM,
work page 2024
-
[2007]
High-dimensional predic- tion for sequential decision making
[NRRX23] Georgy Noarov, Ramya Ramalingam, Aaron Roth, and Step han Xie. High-dimensional predic- tion for sequential decision making. arXiv preprint arXiv:2310.17651 ,
-
[2012]
Predict to minimize swap regret for all p ayoff-bounded tasks
[HW24] Lunjia Hu and Yifan Wu. Predict to minimize swap regret for all p ayoff-bounded tasks. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Scien ce (FOCS), pages 244–263. IEEE,
work page 2024
-
[2016]
Calibrated Forecasts: The Minimax Proof
[Har22] Sergiu Hart. Calibrated forecasts: The minimax proof. arXiv preprint arXiv:2209.05863 ,
Show all 13 references
-
[2017]
Computing optimal regularizers for online linear optimization
11 [GSJ24] Khashayar Gatmiry, Jon Schneider, and Stefanie Jegelka. Computing optimal regularizers for online linear optimization. arXiv preprint arXiv:2410.17336 ,
-
[2018]
Full swap regret and discretized calibration
[FKO+25] Maxwell Fishelson, Robert Kleinberg, Princewill Okoroafor, Ren ato Paes Leme, Jon Schneider, and Yifeng Teng. Full swap regret and discretized calibration. arXiv preprint arXiv:2502.09332,
-
[2022]
Kim, Omer Reingold, and Guy N.Rothblum
[HJKRR18] ´Ursula H´ ebert-Johnson, Michael P. Kim, Omer Reingold, and Guy N.Rothblum. Multicalibra- tion: Calibration for the (Computationally-identifiable) masses. In J ennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machin e Learni...
1939
-
[2023]
Optim al multiclass u-calibration error and beyond
[LSS24] Haipeng Luo, Spandan Senapati, and Vatsal Sharan. Optim al multiclass u-calibration error and beyond. arXiv preprint arXiv:2405.19374 ,
-
[2024]
A lower bound on swap regret in extensive-form games.arXiv preprint arXiv:2406.13116,
[DFG+24] Constantinos Daskalakis, Gabriele Farina, Noah Golowich, Tuoma s Sandholm, and Brian Hu Zhang. A lower bound on swap regret in extensive-form games.arXiv preprint arXiv:2406.13116,
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.