Pith. sign in

REVIEW 2 major objections 4 minor 32 references

This paper proves that swap-agnostic learning for a fixed proper loss can be reduced to a joint second-order multicalibration guarantee, yielding fast rates that pay only the log-size of the hypothesis class, not the number of prediction bu

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-03 01:30 UTC pith:Y63WNCEM

load-bearing objection The single-loss T^{1/3} swap-regret result is real and worth engaging; the bounded-loss family headline is oversold because Theorem 5.2 needs a finite-range assumption the abstract hides. the 2 major comments →

arxiv 2607.28856 v1 pith:Y63WNCEM submitted 2026-07-30 cs.LG

Fast Rates for Swap-Agnostic Learning of Proper Losses

Princewill Okoroafor This is my paper
classification cs.LG MSC 68Q3268W27
keywords swap-agnostic learningproper lossessecond-order multicalibrationonline learningregret boundsomnipredictiononline-to-batch conversionLipschitz losses
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper asks whether a predictor competing against a different hypothesis at each prediction level must pay a separate statistical price for every prediction bucket. It answers no for proper losses: the loss's own geometry supplies a 'drift' penalty that cancels the bucket-wise cost, and one joint guarantee—second-order multicalibration—controls all buckets at once. For a finite hypothesis class, this yields offline excess risk O~((log|H|/m)^{2/3}) and online swap regret O~(T^{1/3}(log|H|)^{2/3}) for any fixed Lipschitz proper loss, and similar simultaneous guarantees for entire families of bounded and convex Lipschitz proper losses. The rates match lower bounds up to logarithms and improve on the previous T^{2/3} route via bucket-wise multicalibration.

Core claim

The central claim is that swap-agnostic learning for a fixed proper loss reduces to a second-order form of multicalibration: controlling, for every selector test g, Bias_T(g) ≤ c·Mass_T(g) + a, where Bias is the cumulative (y-p)g and Mass is the cumulative g^2. Because the proper-loss identity splits any loss difference into a bias term proportional to y-p and a nonnegative drift term that grows like the square of the comparator's slope difference, tuning c to match the drift constant makes the quadratic terms cancel, leaving an additive cost that grows only with log|H|, not with the number of prediction buckets. The paper proves this via an approachability-based online algorithm with a Bern

What carries the argument

The load-bearing identity is the proper-loss split ℓ(p,y)-ℓ(q,y) = (y-p)(Δℓ(p)-Δℓ(q)) - [L_p(q)-L_p(p)], with the drift term always nonnegative. A quadratic-growth inequality (for L-Lipschitz proper losses, drift ≥ (Δℓ(p)-Δℓ(q))^2/(4L)) makes the drift control the square of the bias coefficient. The algorithm is a multiplicative-weights implementation of vector-valued approachability run on tests induced by swap rules, with a Bernstein-style variance correction that yields the realized bound Bias≤c·Mass+a; an online-to-batch conversion and finite covers pass this to offline learning and to loss families.

Load-bearing premise

For the entire-family guarantees over bounded proper losses, the load-bearing assumption is that every hypothesis in H outputs values from one fixed finite set; the paper states it does not know how to remove this, and without it the threshold-continuum argument fails.

What would settle it

Run the online algorithm on the half-Brier loss against the three-hypothesis class of Theorem 4.7 under an adversarial label sequence. If the realized swap regret can be held below c T^{1/3} for all large T (or, conversely, the regret exceeds C T^{1/3} for an adversarially chosen sequence when the algorithm's grid is tuned as specified), the claimed tight exponent is wrong.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • For any fixed L-Lipschitz proper loss and finite hypothesis class, offline swap-agnostic excess risk is O~(L (log|H|/m)^{2/3}) and online swap regret is O~(L T^{1/3}(log|H|)^{2/3}), with matching lower bounds for the half-Brier loss.
  • A single predictor can be swap-agnostic simultaneously for all proper losses bounded in [-1,1] at O~(sqrt(T log|H|)) online and O~(sqrt(log|H|/m)) offline, provided the comparator values lie in a fixed finite set.
  • For all convex 1-Lipschitz proper losses, the sharper 2/3-exponent rates hold simultaneously, via a new clipped-ReLU decomposition.
  • The second-order multicalibration guarantee transfers beyond proper losses: any bounded binary loss evaluated after best-response postprocessing inherits the same rates, with the relevant comparator class being the loss's slope class.
  • The 2/3 exponents are tight up to logarithms, improving on the T^{2/3} rates implied by prior swap-omniprediction routes.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the finite-range assumption for bounded losses can be replaced by a sample-dependent or distribution-dependent complexity measure, the same techniques would likely yield uniform swap-agnostic rates for real-valued hypothesis classes without quantization.
  • The convex-Lipschitz decomposition into clipped-ReLU primitives suggests that omniprediction algorithms for convex losses can be built from interval-indexed weak learners, which may lead to oracle-efficient implementations.
  • A natural testbed is cost-sensitive classification with a continuum of thresholds: the paper's rates predict that a single recalibrated score can be near-optimal for every downstream threshold simultaneously, which could be verified empirically on clinical or credit-scoring data.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper develops a second-order multicalibration guarantee — for every test g, Bias_T(g) ≤ c·Mass_T(g) + a — proved by a Blackwell-approachability algorithm with a Bernstein-corrected exponential potential. Using the proper-loss identity (Lemma 2.1), the authors show that the nonnegative drift term quadratically controls the bias coefficient (Lemma 4.2), so the mass term cancels. This yields the central Theorem 4.5: for a fixed L-Lipschitz proper loss and finite H, online swap regret is O~(L T^{1/3}(log|H|)^{2/3}) and offline swap-agnostic excess risk is O~(L((log|H|)/m)^{2/3}). The machinery is extended to finite loss families, to all bounded proper losses (square-root rates, under a finite-range condition on H), to convex 1-Lipschitz proper losses (fast rates, via a clipped-ReLU decomposition), and to arbitrary bounded binary losses via canonical properization. Lower bounds show the T^{1/3} exponent is tight for the half-Brier loss against a three-hypothesis class.

Significance. The main conceptual contribution — replacing bucket-by-bucket statistical costs with a single second-order multicalibration bound whose mass term is absorbed by the loss's own drift — is elegant and appears to be the right explanation for why swap-agnostic learning need not cost a factor of the prediction-grid size. The proof of Theorem 4.5 is self-contained, the factorization in Proposition 3.2 gives a practical algorithm, and the lower bound (Theorem 4.7) is a valuable complement. If the two issues below are fixed, the paper substantially improves on the prior O~(T^{2/3}) route via swap omniprediction and gives a clean answer to Question 1. The paper is careful in many places (explicit constants, high-probability statements, online-to-batch conversion), which increases confidence in the central argument.

major comments (2)
  1. [Abstract; §5.3, Theorem 5.2] The abstract claims simultaneous swap-agnostic rates for 'all proper losses bounded in [-1,1]' without stating the finite-range hypothesis h(X) ⊆ Γ_H for a fixed finite Γ_H that Theorem 5.2 requires. The proof of Corollary 5.7 uses the representative-threshold argument only for realized values z ∈ S_N = Γ_N ∪ Γ_H; for a general finite H with continuous output range, no fixed finite S_N exists and the exact extension from finitely many thresholds to every threshold fails. Remark 5.10 explicitly acknowledges that the assumption is substantive and that no removal is known. The abstract and Section 1.1 must be revised to state this assumption, or the theorem must be extended.
  2. [§3.3, Theorem 3.7, Eq. (20)] The proof of Theorem 3.7 concludes by claiming '4ηλ + λ/(2η) + 4λ/3 ≤ 2λ/η', but the preceding display also carries the term log(3|G|/δ)/η arising from applying Theorem 3.3 with failure probability δ/3. For η = 1/4 and log(12|G|/δ) sufficiently large (roughly > 16.6), the full sum exceeds 2λ/η, so the displayed bound (20) is not established in the stated regime. Since Corollary 3.9 invokes Theorem 3.7 with η = 1/4 and is used in the bounded-loss offline proof, this needs a repair — either a larger additive constant or a restricted range of η. The rates are unaffected, but the proof as written does not imply (20).
minor comments (4)
  1. [§5.3] The sentence 'Only in this section, assume that there is a finite set Γ_H...' is inaccurate: the assumption is also used in the statement of Theorem 5.2 and in the proof in §5.4. Please adjust the scope marker.
  2. [§1.1 / Abstract] The abstract uses 'smooth proper loss' for the fixed-loss result, while Section 4 defines only Lipschitz partial losses and proves equivalence with smoothness of the negative Bayes risk (Corollary 4.3). Unify the terminology to avoid the impression that two separate assumptions are needed.
  3. [§7, Corollary 7.7] Corollary 7.7's finite slope-range assumption is analogous to Theorem 5.2's finite-range condition but is not mentioned in the Section 7 overview or the abstract. The prose summary should carry this caveat explicitly, since the simultaneous-family transfer depends on it.
  4. [§3.3, Eq. (20)] In the statement of Theorem 3.7, the additive term is written with log(12|G|/δ); the proof defines λ = log(12|G|/δ). Please verify that all constants are consistent after any repair of the final inequality, as the current proof and statement may differ by a logarithmic factor for large |G|/δ.

Circularity Check

0 steps flagged

No significant circularity; core rates are derived from a self-contained approachability guarantee.

full rationale

The main derivation is self-contained. Section 3 proves Theorem 3.3 from a Blackwell-approachability potential (Lemmas 3.4, 3.5), and Theorem 4.5 combines the proper-loss identity (Lemma 2.1) with the quadratic-growth inequality (Lemma 4.2): the Mass term cancels algebraically after choosing eta=1/4 online and eta=1/10 offline, with the grid optimized as N ~ (T/log|H|)^{1/3} or N ~ (m/log|H|)^{1/3}. No fitted parameter is relabeled as a prediction. The bounded-loss and convex-Lipschitz results rest on new decomposition lemmas (Lemmas 5.1, 5.3, 5.5; Proposition 6.1) and on the exact finite-range extension Corollary 5.7, which is proved by comparing thresholds on S_N = Γ_N ∪ Γ_H rather than by importing an external result. Author self-citations (Okoroafor et al. 2024, 2025) are historical/architectural and load-bearing nowhere; the lower bound uses an external black-box recalibration lower bound (Hu et al. 2026b). The one real caveat—Theorem 5.2 requires a finite Γ_H with h(X) ⊆ Γ_H—is explicitly acknowledged in Remark 5.10 ('the finite-range assumption of Theorem 5.2 is not a without-loss-of-generality discretization... we do not know a substitute argument') and is a narrowing of the family result, not a circularity. The abstract's omission of this caveat is an accuracy/scope concern, not a definitional or fitted-input reduction. No equation reduces to its own input by construction.

Axiom & Free-Parameter Ledger

3 free parameters · 3 axioms · 0 invented entities

No free parameter is fitted to data; all algorithm constants are analytical choices. The main substantive input beyond standard assumptions is the finite-range comparator-output condition required for the bounded-loss family and the arbitrary-loss transfer.

free parameters (3)
  • prediction grid resolution N = N ≍ (T/log|H|)^{1/3} online; (m/log|H|)^{1/3} offline; N ≍ sqrt(T/Λ_T) for bounded losses
    Analytically optimized to balance discretization error and test-class log-size; not fitted to data.
  • learning rate η = 1/4 online; 1/10–1/20 offline
    Algorithmic constant chosen so that 2η cancels the Mass coefficient in the proper-loss identity; no data-fitting.
  • cover radius ρ = m^{-1/2} in Theorem 4.10; m^{-1} and T^{-2/3} in Theorem 6.2
    Analytically chosen for loss-family covers; only affects logarithmic and lower-order terms.
axioms (3)
  • domain assumption For every h ∈ H and x ∈ X, h(x) lies in a fixed finite set Γ_H (Theorem 5.2, Corollary 5.7).
    Load-bearing for the exact threshold extension: it lets Corollary 5.7 identify every threshold v with vrep ∈ Γ_N ∪ Γ_H. Remark 5.10 calls the assumption substantive and says no substitute is known; the abstract omits it.
  • domain assumption Predictions lie on a finite grid Γ_N and outcomes are binary; the environment is nonanticipating and cannot depend on the learner's fresh private draw p_t (Section 2.2).
    The grid oracle and the Bernstein-corrected potential proof rely on this protocol. It is standard in online calibration and swap-regret work.
  • standard math Standard Blackwell approachability, Freedman/Bernstein exponential inequalities, and convex-analysis facts (smooth Bregman lower bound, BV layer-cake representation) hold as invoked.
    Used in Lemmas 3.5, 3.8, 4.1, 6.4 and 6.5. The paper provides proofs or citations for these tools.

pith-pipeline@v1.3.0-alltime-deepseek · 32055 in / 25897 out tokens · 270448 ms · 2026-08-03T01:30:27.930366+00:00 · methodology

0 comments
read the original abstract

Swap-agnostic learning strengthens classical agnostic learning by allowing the comparator to select a different hypothesis on each level set of the learner's predictions. This benchmark captures prediction-dependent postprocessing, but appears to require solving a separate agnostic-learning problem for every possible prediction value. We show that, for proper losses, these prediction-level comparisons can instead be controlled jointly. Our main result is an offline swap-agnostic learner for any fixed proper loss. For a finite hypothesis class $H$ and any fixed smooth proper loss, the excess risk from $m$ i.i.d. samples is $\widetilde{O}((\log |H|/m)^{2/3})$, with a corresponding online swap-regret bound of $\widetilde{O}(T^{1/3}(\log |H|)^{2/3})$. We also give algorithms whose predictions are simultaneously swap-agnostic for entire families of losses. For all proper losses bounded in $[-1,1]$, we obtain online and offline rates of $\widetilde{O}(\sqrt{T\log |H|})$ and $\widetilde{O}(\sqrt{\log |H|/m})$, respectively. For convex, $1$-Lipschitz proper losses, these rates improve to $\widetilde{O}(T^{1/3}(\log |H|)^{2/3})$ online and $\widetilde{O}((\log |H|/m)^{2/3})$ offline. These bounds are tight up to logarithmic factors and improve upon the $\widetilde{O}(T^{2/3}(\log |H|)^{1/3})$ rate implied by the swap-omniprediction guarantee of Luo et al. (2025). Our main technical contribution is a reduction from swap-agnostic learning to a second-order form of multicalibration, obtained via Blackwell approachability with a Bernstein-style variance correction.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

32 extracted references · 2 linked inside Pith

  1. [1]

    An analog of the minimax theorem for vector payoffs

    David Blackwell. An analog of the minimax theorem for vector payoffs. Pacific Journal of Mathematics, 6(1):1--8, 1956

    1956

  2. [2]

    BayesCNS: A unified Bayesian approach to address cold start and non-stationarity in search systems at scale

    Randy Ardywibowo, Rakesh Sunki, Shin Tsz Lucy Kuo, and Sankalp Nayak. BayesCNS: A unified Bayesian approach to address cold start and non-stationarity in search systems at scale. In Proceedings of the AAAI Conference on Artificial Intelligence, 39(1):12--20, 2025

    2025

  3. [3]

    Bartlett, Michael I

    Peter L. Bartlett, Michael I. Jordan, and Jon D. McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473):138--156, 2006

    2006

  4. [4]

    Prediction, Learning, and Games

    Nicol\`o Cesa-Bianchi and G\'abor Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006

    2006

  5. [5]

    The sample complexity of multicalibration

    Natalie Collina, Jiuyao Lu, Georgy Noarov, and Aaron Roth. The sample complexity of multicalibration. arXiv preprint arXiv:2604.21923, 2026

    Pith/arXiv arXiv 2026

  6. [6]

    What is risk-based pricing? Consumer Financial Protection Bureau, January 30, 2024

    Consumer Financial Protection Bureau. What is risk-based pricing? Consumer Financial Protection Bureau, January 30, 2024

    2024

  7. [7]

    Philip Dawid

    A. Philip Dawid. The well-calibrated Bayesian. Journal of the American Statistical Association, 77(379):605--610, 1982

    1982

  8. [8]

    The foundations of cost-sensitive learning

    Charles Elkan. The foundations of cost-sensitive learning. In International Joint Conference on Artificial Intelligence, 2001

    2001

  9. [9]

    Full swap regret and discretized calibration

    Maxwell Fishelson, Robert Kleinberg, Princewill Okoroafor, Renato Paes Leme, Jon Schneider, and Yifeng Teng. Full swap regret and discretized calibration. In Proceedings of the 36th International Conference on Algorithmic Learning Theory, volume 272 of Proceedings of Machine Learning Research, pages 444--480, 2025

    2025

  10. [10]

    Foster and Rakesh V

    Dean P. Foster and Rakesh V. Vohra. Asymptotic calibration. Biometrika, 85(2):379--390, 1998

    1998

  11. [11]

    Oracle efficient online multicalibration and omniprediction

    Sumegha Garg, Christopher Jung, Omer Reingold, and Aaron Roth. Oracle efficient online multicalibration and omniprediction. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2725--2792, 2024

    2024

  12. [12]

    Tibshirani

    Isaac Gibbs and Ryan J. Tibshirani. Sample-efficient omniprediction for proper losses. In Proceedings of the 39th Annual Conference on Learning Theory, volume 336 of Proceedings of Machine Learning Research, pages 2679--2719, 2026

    2026

  13. [13]

    Tilmann Gneiting and Adrian E. Raftery. Strictly proper scoring rules, prediction, and estimation. Journal of the American Statistical Association, 102(477):359--378, 2007

    2007

  14. [14]

    Omnipredictors

    Parikshit Gopalan, Adam Tauman Kalai, Omer Reingold, Vatsal Sharan, and Udi Wieder. Omnipredictors. In Innovations in Theoretical Computer Science, 2022

    2022

  15. [15]

    Kim, and Omer Reingold

    Parikshit Gopalan, Michael P. Kim, and Omer Reingold. Swap agnostic learning, or characterizing omniprediction via multicalibration. In Advances in Neural Information Processing Systems, 2023

    2023

  16. [16]

    Kim, Omer Reingold, and Guy N

    \'Ursula H\'ebert-Johnson, Michael P. Kim, Omer Reingold, and Guy N. Rothblum. Multicalibration: Calibration for the (computationally-identifiable) masses. In International Conference on Machine Learning, 2018

    2018

  17. [17]

    Grundy et al

    Scott M. Grundy et al. 2018 guideline on the management of blood cholesterol. Journal of the American College of Cardiology, 73(24):e285--e350, 2019

    2018

  18. [18]

    Predict to minimize swap regret for all payoff-bounded tasks

    Lunjia Hu and Yifan Wu. Predict to minimize swap regret for all payoff-bounded tasks. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 244--263, 2024. doi:10.1109/FOCS61266.2024.00024

    arXiv 2024

  19. [19]

    Near-optimal swap regret minimization for convex losses

    Lunjia Hu, Jon Schneider, and Yifan Wu. Near-optimal swap regret minimization for convex losses. In Proceedings of the 39th Annual Conference on Learning Theory, volume 336 of Proceedings of Machine Learning Research, pages 3285--3313, 2026

    2026

  20. [20]

    Simultaneous Blackwell approachability and applications to multiclass omniprediction

    Lunjia Hu, Kevin Tian, and Chutong Yang. Simultaneous Blackwell approachability and applications to multiclass omniprediction. In Proceedings of the 39th Annual Conference on Learning Theory, volume 336 of Proceedings of Machine Learning Research, pages 3593--3634, 2026

    2026

  21. [21]

    Optimal recalibration of an online predictor

    Lunjia Hu, Kevin Tian, and Chutong Yang. Optimal recalibration of an online predictor. arXiv preprint arXiv:2607.19689, 2026

    Pith/arXiv arXiv 2026

  22. [22]

    Kim, Amirata Ghorbani, and James Zou

    Michael P. Kim, Amirata Ghorbani, and James Zou. Multiaccuracy: Black-box post-processing for fairness in classification. In AAAI/ACM Conference on AI, Ethics, and Society, 2019

    2019

  23. [23]

    U-calibration: Forecasting for an unknown agent

    Robert Kleinberg, Renato Paes Leme, Jon Schneider, and Yifeng Teng. U-calibration: Forecasting for an unknown agent. In Conference on Learning Theory, 2023

    2023

  24. [24]

    Hartline, Liren Shan, and Yifan Wu

    Yingkai Li, Jason D. Hartline, Liren Shan, and Yifan Wu. Optimization of scoring rules. In Proceedings of the 23rd ACM Conference on Economics and Computation, 2022

    2022

  25. [25]

    Optimal multiclass U-calibration error and beyond

    Haipeng Luo, Spandan Senapati, and Vatsal Sharan. Optimal multiclass U-calibration error and beyond. In Advances in Neural Information Processing Systems, 2024

    2024

  26. [26]

    Improved bounds for swap multicalibration and swap omniprediction

    Haipeng Luo, Spandan Senapati, and Vatsal Sharan. Improved bounds for swap multicalibration and swap omniprediction. In Advances in Neural Information Processing Systems, 2025

    2025

  27. [27]

    Simultaneous swap regret minimization via KL-calibration

    Haipeng Luo, Spandan Senapati, and Vatsal Sharan. Simultaneous swap regret minimization via KL-calibration. In Advances in Neural Information Processing Systems, 2025

    2025

  28. [28]

    Faster recalibration of an online predictor via approachability

    Princewill Okoroafor, Robert Kleinberg, and Wen Sun. Faster recalibration of an online predictor via approachability. In Proceedings of the 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, 2024

    2024

  29. [29]

    Princewill Okoroafor, Robert Kleinberg, and Michael P. Kim. Near-optimal algorithms for omniprediction. In 2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS), pages 1595--1609, 2025. doi:10.1109/FOCS63196.2025.00084

    arXiv 2025

  30. [30]

    Reid and Robert C

    Mark D. Reid and Robert C. Williamson. Composite binary losses. Journal of Machine Learning Research, 11:2387--2422, 2010

    2010

  31. [31]

    Understanding Machine Learning: From Theory to Algorithms

    Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014

    2014

  32. [32]

    Vladimir N. Vapnik. Statistical Learning Theory. Wiley, 1998

    1998