Pith. sign in

REVIEW 3 major objections 5 minor 1 cited by

Improved Bounds for Swap Multicalibration and Swap Omniprediction

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read An efficient algorithm achieves O~(T^{1/3}) ℓ2-swap multicalibration error against bounded linear functions, improving the previous best-known rate and settling an open problem.

desk verdict Very strong paper: the T^{1/3} swap multicalibration bound is real and the proof chain is coherent; send it to review. read the letter →

arxiv 2505.20885 v2 pith:FITLT7GY submitted 2025-05-27 cs.LG stat.ML

Haipeng Luo , Spandan Senapati , Vatsal Sharan This is my paper
classification cs.LGstat.ML
keywords swapmulticalibrationomnipredictiononlinelearningcontextualregretsamplecomplexityconvexLipschitzlosses
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

Multicalibration asks that a predictor be calibrated not just overall but on every subpopulation picked out by a class of test functions; swap multicalibration strengthens this so the test functions may depend on the predicted value. This paper shows that, in the online setting, an efficient forecaster can keep the ℓ2-swap multicalibration error against bounded linear functions as low as O~($T^{{1/3}}$ $d^{{2/3}}$) after T rounds, improving the previous best-known O~($T^{{3/4}}$) and answering an open problem from the preceding literature. Because swap omniprediction, swap agnostic learning, and ℓ1-swap multicalibration all reduce to ℓ2-swap multicalibration, the improved rate propagates into faster convergence and smaller sample complexity in the distributional setting. If the results are right, swap multicalibration matches the best known rate for plain calibration, and several sample requirements drop from $ε^{{-5}}$ or $ε^{{-10}}$ to $ε^{{-2.5}}$ or $ε^{{-3}}$.

What carries the argument

The load-bearing machinery is the pseudo-vs-real error decomposition. The paper introduces pseudo swap multicalibration and pseudo contextual swap regret, in which the forecaster's random predictions are replaced by their conditional distributions, and shows that these pseudo quantities are much easier to minimize; a reduction then converts a pseudo swap multicalibration violation into a pseudo contextual swap regret violation, using the assumption that the linear class is closed under affine transformations. The pseudo contextual swap regret is bounded through the Blum-Mansour reduction: maintain N+1 external-regret algorithms, mix them according to the stationary distribution of the transition matrix they define, feed each one the scaled squared loss, and randomize each continuous prediction to two neighboring grid points; the rounding cost is O(1/$N^{2}$) and each Online Newton Step subroutine has O(d log T) regret. Freedman's inequality converts the pseudo guarantee into a guarantee on the actual swap multicalibration error, paying only O~(N), which is absorbed by choosing N ~ (T/d)^{1/3}.

What would settle it

Check the reduction's load-bearing step on a small finite cover of the linear class: for each grid value p and each bounded linear f with pseudo correlation at least α, verify that the affine recombination p + η f used to construct the squared-loss comparator remains inside the level-4 linear class; a single counterexample with p + η f outside the class would break the chain from pseudo swap multicalibration to pseudo contextual swap regret. Running the same search on a domain whose features have no constant coordinate should reveal such a counterexample if the affine-closure assumption is essential.

Watch

Extended reading notes

Core claim

The central claim is that there is an efficient deterministic online algorithm whose ℓ2-swap multicalibration error against bounded linear functions on a unit-ball domain with a constant feature coordinate is O~($T^{{1/3}}$ $d^{{2/3}}$), both with high probability and in expectation, for a predictor whose values lie on a uniform grid of size N chosen as roughly (T/d)^{1/3}. The algorithm replaces realized predictions by their conditional distributions, bounding a new pseudo swap multicalibration error via pseudo contextual swap regret, then bounds that regret by running N+1 external-regret algorithms through the Blum-Mansour reduction, each instantiated with Online Newton Step on the scaled squared loss and a randomized rounding step whose loss is O(1/$N^{2}$). A martingale concentration argument using Freedman's inequality converts the pseudo guarantee back into a guarantee on the true swap multicalibration error at an additional O~(N) cost that does not change the leading rate. The same machinery yields O~($T^{{2/3}}$) bounds for ℓ1-swap multicalibration and swap omniprediction for convex Lipschitz losses, an O~($T^{{3/5}}$) bound for contextual swap regret, and improved distributional sample complexities through online-to-batch conversion.

Load-bearing premise

The whole chain relies on the linear class being closed under affine transformations, which the setup guarantees by forcing every feature vector to have a constant coordinate; without that coordinate, a swap multicalibration violation need not produce a squared-loss swap regret violation, and the proof stops.

Editorial extensions

If this is right

  • Online ℓ2-swap multicalibration against bounded linear functions is achievable at O~(T^{1/3} d^{2/3}), matching the best known rate for plain ℓ2-calibration while holding a strictly stronger fairness condition.
  • Online ℓ1-swap multicalibration and swap omniprediction for convex 1-Lipschitz losses both improve to O~(T^{2/3}), down from the previous O~(T^{7/8}).
  • Contextual swap regret for the squared loss improves to O~(T^{3/5} d^{2/5}), down from O~(T^{3/4} d), which strengthens the online-to-batch conversion.
  • In the distributional setting, O~(ε^{-3}) samples suffice for an ε-swap omnipredictor, O~(ε^{-2.5}) samples suffice for ε-swap agnostic learning of the squared loss and for ε-ℓ2-swap multicalibration, and O~(ε^{-5}) samples suffice for ε-ℓ1-swap multicalibration.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The pseudo-vs-real concentration framework should transfer to any hypothesis class that is closed under affine transformations and admits a small covering, not just linear functions; classes of polynomials or kernel models with a constant feature would plausibly inherit the same T^{1/3}-type rates.
  • Because the swap-to-external reduction is deterministic and each subroutine is an online convex optimizer, the algorithm is amenable to practical implementation; a concrete testable prediction is that empirical ℓ2-swap multicalibration error on real tabular data should track T^{-1/3} up to logarithmic factors.
  • The paper's own pseudo contextual swap regret bound is T^{1/3} while the true contextual swap regret bound is T^{3/5}, a gap the authors attribute to their concentration analysis; a sharper martingale argument would directly improve swap agnostic learning and swap multicalibration sample complexity beyond ε^{-2.5}.
  • The improved contextual swap regret bound also lowers the regret of online collaborative prediction protocols that previously used the older O~(T^{3/4}) guarantee as a subroutine, a downstream consequence the paper mentions only in passing.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 5 minor

Summary. The paper studies online and distributional swap multicalibration, swap omniprediction, and swap agnostic learning against linear and affine-linear hypothesis classes. The main technical contribution is an efficient deterministic algorithm for pseudo contextual swap regret based on the Blum-Mansour reduction with Online Newton Step experts, together with a Freedman-based concentration step that converts pseudo swap multicalibration guarantees into actual swap multicalibration guarantees. This yields Theorem 1, an O(T^{1/3} d^{2/3} (log T)^{2/3}) bound on l2-swap multicalibration error against F_1^lin, improving on the previous O(T^{3/4}) bound of Garg et al. (2024) and answering their open problem. The authors propagate this bound to obtain O(T^{2/3}) rates for l1-swap multicalibration and swap omniprediction, an O(T^{3/5}) bound for contextual swap regret, and improved distributional sample complexities, including O(epsilon^{-3}) for swap omniprediction, O(epsilon^{-2.5}) for squared-loss swap agnostic learning and l2-swap multicalibration, and O(epsilon^{-5}) for l1-swap multicalibration.

Significance. If the results hold as stated, they represent a substantial quantitative improvement for swap multicalibration and swap omniprediction, matching the best known l2-calibration rates in the linear setting. The paper introduces pseudo swap multicalibration and pseudo contextual swap regret as useful analytical devices, and the main reduction chain is presented with detailed proofs in the appendices, including explicit Freedman-based concentration arguments and a deterministic BM-ONS algorithm with polynomial per-round cost. The main caveats are that several secondary extensions -- notably the F_aff_res variant used in Theorem 2 and the online-to-batch concentration in Section 4 -- are sketched rather than fully proven, and at least one displayed proof is incomplete as written. These issues are local and appear fixable, but they currently leave parts of the claimed contributions without a complete proof.

major comments (3)
  1. [Section 4.1, proof of Theorem 4] The displayed chain bounding the swap omniprediction error as Delta + SMCal_{F_lin_1,1}/T <= Delta + sqrt(SMCal_{F_lin_1,2}/T) = O(1/N + sqrt(Nd/T log N/delta)) is incomplete: the equality drops the second term, and the bound uses the class F_lin_1 rather than the class F_aff_res that appears in the theorem statement. As written, the displayed argument only bounds the deviation Delta and does not include the online swap omniprediction error divided by T, so the stated high-probability O((d/T)^{1/3}) guarantee does not follow. The proof should be rewritten to include the online term from Theorem 2 (or from the F_aff_res analogue of Corollary 1) and to track the dependence on delta consistently.
  2. [Section 3.1, Theorem 2] Theorem 2 is stated for the comparator class F_aff_res, but its proof depends on an extension of the entire Section 2 analysis from F_lin_1 to F_aff_res that is not carried out; the text says 'We skip the exact derivations for the sake of brevity'. In particular, no analogue of Lemma 2, Lemma 4, or Corollary 1 is stated for F_aff_res, and the cover-size and closure arguments are only asserted. Since Theorem 2 is one of the paper's main online results, this is a load-bearing gap; the authors should provide a formal corollary or a detailed proof of the claimed extension.
  3. [Section 2.1, Eq. (20) in proof of Lemma 8] In the proof of Lemma 8, the equality |ell_v(p,y) - ell_{v'}(p,y)| = |(v-v')*sign(p-v)| relies on the assertion that sign(p-v)=sign(p-v') for all p in Z. Under the standard convention sign(0)=0, this fails at p=v' when v<v', where the difference is |v-y| rather than |v-v'|. The bound can likely be repaired by specifying sign(0)=1 or by an integrated-error argument over the measure mu, but as written the proof of the O(T/N) term in Lemma 8 is not valid. Since Lemma 8 feeds directly into the sample complexity bound for swap omniprediction in Theorem 4, this gap should be fixed.
minor comments (5)
  1. [Section 1.2] The remark that the results 'readily generalize to an adaptive adversary' is not proven; all stated theorems assume an oblivious adversary. Please either add a proof or qualify the remark so that it is not read as a formal claim.
  2. [Section 2.2] The claim that the constant-coordinate restriction X={x in B_2^d : x_1=1/2} is without loss of generality would benefit from the explicit dimension-increasing embedding, for example x mapped to (1/2, sqrt(3/4) x), along with a description of how the linear class F_lin is rescaled in the embedded space.
  3. [Appendix B.3] There is a typo: 'convinience' should be 'convenience'.
  4. [Section 3.1] The algebra showing that F_aff is closed under affine transformations is correct, but the derivation is terse; expanding the computation of theta'_1 in a displayed equation would improve readability and prevent the reader from having to reverse-engineer the constants.
  5. [Section 4.2, Lemma 13] The statement says 'we bound T2', but the lemma actually bounds the deviation Delta for the squared loss; the wording should be corrected for consistency with equations (8) and the surrounding text.

Circularity Check

0 steps flagged · score 2.0 of 10

No load-bearing circularity: Theorem 1's O(T^{1/3}) bound is derived from a genuine pseudo-regret optimization plus Freedman-based concentration, not from fitted parameters or a self-citation chain.

full rationale

I walked the derivation chain for the central claim, Theorem 1, which asserts SMCal_{F_lin^1,2} = O(T^{1/3} d^{2/3} (log T)^{2/3}). The proof is self-contained: Lemma 1 converts SMCal to PSMCal via Freedman's inequality on three martingale difference sequences; Lemma 2 handles the infinite class by a standard epsilon-cover of size O((1/epsilon)^d); Lemma 4 converts PSMCal to PSReg via the explicit construction f'(x) = p + eta f(x) with eta = min(1, alpha/mu); Proposition 2 bounds PSReg by the sum of external regrets using the stationary distribution of the BM reduction; and Lemma 5 gives the O(d log T) ONS regret for the scaled squared loss. At no point is the target bound substituted into an input, and no parameter is fitted to the quantity being predicted. The pseudo notions are intermediate analytical constructs, not renamed versions of the final error. The self-citations to Luo et al. (2025) and Fishelson et al. (2025) are explicitly described as motivation and technique sources, and the needed lemmas are proven inside the paper; these citations are not load-bearing. The constant-coordinate assumption X = {x in B_2^d : x_1 = 1/2} is a stated scope condition used to ensure F_lin is closed under affine transformations, and the paper's WLOG claim is plausible, but even if one doubted it, that would be an assumption-coverage issue, not circularity. The paper itself flags the O(T^{3/5}) contextual swap regret bound as an analysis limitation and the adaptive-adversary remark in Section 1.2 is unproven, but these are correctness or presentation concerns, not circular steps. Overall, I find no specific reduction in which the conclusion is equivalent to an input by construction.

Assumptions & free parameters 0 free parameters · 8 assumptions · 0 invented entities

The central claim rests on standard results in online learning and probability (Freedman's inequality, ONS regret, BM reduction, covering numbers) and on domain assumptions about the instance space (constant coordinate) and the adversary (oblivious). No free parameters are fitted to data; the algorithm's parameters (N, epsilon) are chosen to optimize the theoretical rates. No new physical entities are introduced; the pseudo notions are mathematical definitions.

assumptions (8)
  • standard math Freedman's inequality (Beygelzimer et al., 2011, Theorem 1)
    Used in Lemma 1, Lemma 7, Lemma 8, Lemma 10, and Lemma 12 to bound deviations between pseudo and actual quantities.
  • standard math Regret bound for Online Newton Step (Hazan et al., 2007)
    Used to bound external regret of each ALG_i for linear functions (Lemma 5, Section 2.3).
  • standard math Blum-Mansour reduction from swap regret to external regret (Blum and Mansour, 2007)
    Used in Algorithm 1 and Proposition 2 to bound pseudo contextual swap regret by the sum of external regrets.
  • standard math Covering number bound for linear functions: |C_epsilon| = O((1/epsilon)^d) (Proposition 1)
    Used to extend finite-class results to F_lin_1 (Lemma 2, Theorem 3).
  • domain assumption Approximate basis for convex Lipschitz losses (Gopalan et al., 2024, Lemma 9)
    Used in Lemma 10 to bound T2 for the loss class L_cvx.
  • domain assumption Instance space X has a constant coordinate, and the hypothesis class is closed under affine transformations (Assumption 1)
    Required for Lemma 3 and 4, which convert a multicalibration violation into a swap regret violation.
  • domain assumption Oblivious adversary assumption (stated in Section 1.2)
    All theorem proofs assume the data sequence is fixed in advance; the adaptive-adversary generalization is claimed but not proven.
  • domain assumption Loss class L_cvx consists of bounded convex 1-Lipschitz functions (defined in Section 3.1)
    Used for the approximate basis decomposition and for Lemma 6.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Improved Bounds for Swap Multicalibration and Swap Omniprediction." pith.science (2026). https://pith.science/paper/FITLT7GY

@misc{pith2026250520885,
  author       = {Pith},
  title        = {Pith review of: Improved Bounds for Swap Multicalibration and Swap Omniprediction},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FITLT7GY}},
  note         = {Machine review of arXiv:2505.20885}
}
abstract

In this paper, we consider the related problems of multicalibration -- a multigroup fairness notion and omniprediction -- a simultaneous loss minimization paradigm, both in the distributional and online settings. The recent work of Garg et al. (2024) raised the open problem of whether it is possible to efficiently achieve $O(\sqrt{T})$ $\ell_{2}$-multicalibration error against bounded linear functions. In this paper, we answer this question in a strongly affirmative sense. We propose an efficient algorithm that achieves $O(T^{\frac{1}{3}})$ $\ell_{2}$-swap multicalibration error (both in high probability and expectation). On propagating this bound onward, we obtain significantly improved rates for $\ell_{1}$-swap multicalibration and swap omniprediction for a loss class of convex Lipschitz functions. In particular, we show that our algorithm achieves $O(T^{\frac{2}{3}})$ $\ell_{1}$-swap multicalibration and swap omniprediction errors, thereby improving upon the previous best-known bound of $O(T^{\frac{7}{8}})$. As a consequence of our improved online results, we further obtain several improved sample complexity rates in the distributional setting. In particular, we establish a $O(\varepsilon ^ {-3})$ sample complexity of efficiently learning an $\varepsilon$-swap omnipredictor for the class of convex and Lipschitz functions, $O(\varepsilon ^{-2.5})$ sample complexity of efficiently learning an $\varepsilon$-swap agnostic learner for the squared loss, and $O(\varepsilon ^ {-5}), O(\varepsilon ^ {-2.5})$ sample complexities of learning $\ell_{1}, \ell_{2}$-swap multicalibrated predictors against linear functions, all of which significantly improve on the previous best-known bounds.

Figures

Figures reproduced from arXiv: 2505.20885 by the authors.

Figure 1
Figure 1. Path A → B → C → D represents the sequence of reductions followed by Garg et al. (2024), whereas path E → F → B → C → D represents our road-map. To derive an improved guarantee for B, we establish: (i) a O˜(T 1 3 ) bound for E; (ii) a reduction from E to F; and (c) a concentration bound from F to B. The improved guarantees for C and D follow as a consequence of the improvement in B. The improved guarantee for A foll… view at source ↗

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Optimal Recalibration of an Online Predictor

    stat.ML 2026-07 accept novelty 8.0 of 10

    (ε, ε²)-recalibration is achievable in Θ(ε⁻³) rounds and this is optimal; the same rate gives simultaneous calibration and calibeating.

Reference graph

Works this paper leans on

49 extracted references · 39 canonical work pages · cited by 1 Pith paper

  1. [1]

    L., and Hazan, E

    Abernethy, J., Bartlett, P. L., and Hazan, E. (2011). Blackwell approachability and no-regret learning are equivalent. In Proceedings of the 24th Annual Conference on Learning Theory , pages 27--46. JMLR Workshop and Conference Proceedings

    work page 2011

  2. [2]

    R., Collina, N., Roth, A., and Shi, M

    Arunachaleswaran, E. R., Collina, N., Roth, A., and Shi, M. (2025). 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

  3. [3]

    Bastani, O., Gupta, V., Jung, C., Noarov, G., Ramalingam, R., and Roth, A. (2022). Practical adversarial multivalid conformal prediction. Advances in neural information processing systems , 35:29362--29373

    work page 2022

  4. [4]

    Beygelzimer, A., Langford, J., Li, L., Reyzin, L., and Schapire, R. (2011). Contextual bandit algorithms with supervised learning guarantees. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics , pages 19--26. JMLR Workshop and Conference Proceedings

    work page 2011

  5. [5]

    Blackwell, D. (1956). An analog of the minimax theorem for vector payoffs

    work page 1956

  6. [6]

    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

    work page 2023

  7. [7]

    and Mansour, Y

    Blum, A. and Mansour, Y. (2007). From external to internal regret. Journal of Machine Learning Research , 8(6)

    work page 2007

  8. [8]

    Casacuberta, S., Dwork, C., and Vadhan, S. (2024). Complexity-theoretic implications of multicalibration. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages 1071--1082

    work page 2024

Show all 49 references
  1. [9]

    Cesa-Bianchi, N., Conconi, A., and Gentile, C. (2004). On the generalization ability of on-line learning algorithms. IEEE Transactions on Information Theory , 50(9):2050--2057

    2004

  2. [10]

    Collina, N., Globus-Harris, I., Goel, S., Gupta, V., Roth, A., and Shi, M. (2025). Collaborative prediction: Tractable information aggregation via agreement. arXiv preprint arXiv:2504.06075

    2025 arXiv

  3. [11]

    Collina, N., Goel, S., Gupta, V., and Roth, A. (2024). Tractable agreement protocols. arXiv preprint arXiv:2411.19791

    2024 arXiv

  4. [12]

    Dagan, Y., Daskalakis, C., Fishelson, M., Golowich, N., Kleinberg, R., and Okoroafor, P. (2024). Improved bounds for calibration via stronger sign preservation games. arXiv preprint arXiv:2406.13668

    2024 arXiv

  5. [13]

    Devic, S., Korolova, A., Kempe, D., and Sharan, V. (2024). Stability and multigroup fairness in ranking with uncertain predictions. In Proceedings of the 41st International Conference on Machine Learning , pages 10661--10686

    2024

  6. [14]

    Dwork, C., Lee, D., Lin, H., and Tankala, P. (2023). From pseudorandomness to multi-group fairness and back. In The Thirty Sixth Annual Conference on Learning Theory , pages 3566--3614. PMLR

    2023

  7. [15]

    P., Schneider, J., and Teng, Y

    Fishelson, M., Kleinberg, R., Okoroafor, P., Leme, R. P., Schneider, J., and Teng, Y. (2025). Full swap regret and discretized calibration. In 36th International Conference on Algorithmic Learning Theory

    2025

  8. [16]

    Foster, D. P. and Hart, S. (2021). Forecast hedging and calibration. Journal of Political Economy , 129(12):3447--3490

    2021

  9. [17]

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

    1998

  10. [18]

    Garg, S., Jung, C., Reingold, O., and Roth, A. (2024). Oracle efficient online multicalibration and omniprediction. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 2725--2792. SIAM

    2024

  11. [19]

    Ghuge, R., Muthukumar, V., and Singla, S. (2025). Improved and oracle-efficient online _1 -multicalibration

    2025

  12. [20]

    Globus-Harris, I., Harrison, D., Kearns, M., Roth, A., and Sorrell, J. (2023). Multicalibration as boosting for regression. In International Conference on Machine Learning , pages 11459--11492. PMLR

    2023

  13. [21]

    Gollakota, A., Gopalan, P., Klivans, A., and Stavropoulos, K. (2023). Agnostically learning single-index models using omnipredictors. Advances in Neural Information Processing Systems , 36:14685--14704

    2023

  14. [22]

    P., Reingold, O., and Wieder, U

    Gopalan, P., Hu, L., Kim, M. P., Reingold, O., and Wieder, U. (2023a). Loss Minimization Through the Lens Of Outcome Indistinguishability . In Tauman Kalai, Y., editor, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) , volume 251 of Leibniz Internationa...

    2023

  15. [23]

    T., Reingold, O., Sharan, V., and Wieder, U

    Gopalan, P., Kalai, A. T., Reingold, O., Sharan, V., and Wieder, U. (2022a). Omnipredictors . In Braverman, M., editor, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) , volume 215 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 79:...

    2022

  16. [24]

    P., and Reingold, O

    Gopalan, P., Kim, M. P., and Reingold, O. (2023b). Swap agnostic learning, or characterizing omniprediction via multicalibration. In Thirty-seventh Conference on Neural Information Processing Systems

    2023

  17. [25]

    P., Singhal, M

    Gopalan, P., Kim, M. P., Singhal, M. A., and Zhao, S. (2022b). Low-degree multicalibration. In Conference on Learning Theory , pages 3193--3234. PMLR

    2022

  18. [26]

    Gopalan, P., Okoroafor, P., Raghavendra, P., Sherry, A., and Singhal, M. (2024). Omnipredictors for regression and the approximate rank of convex functions. In The Thirty Seventh Annual Conference on Learning Theory , pages 2027--2070. PMLR

    2024

  19. [27]

    M., and Roth, A

    Gupta, V., Jung, C., Noarov, G., Pai, M. M., and Roth, A. (2022). Online multivalid learning: Means, moments, and prediction intervals. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) , pages 82--1. Schloss Dagstuhl--Leibniz-Zentrum f \"u r Informatik

    2022

  20. [28]

    Haghtalab, N., Jordan, M., and Zhao, E. (2023). A unifying perspective on multi-calibration: Game dynamics for multi-objective learning. Advances in Neural Information Processing Systems , 36:72464--72506

    2023

  21. [29]

    Haghtalab, N., Qiao, M., Yang, K., and Zhao, E. (2024). Truthfulness of calibration measures. In The Thirty-eighth Annual Conference on Neural Information Processing Systems

    2024

  22. [30]

    Haussler, D. (1992). Decision theoretic generalizations of the pac model for neural net and other learning applications. Information and computation , 100(1):78--150

    1992

  23. [31]

    Hazan, E., Agarwal, A., and Kale, S. (2007). Logarithmic regret algorithms for online convex optimization. Machine Learning , 69(2):169--192

    2007

  24. [32]

    H \'e bert-Johnson, U., Kim, M., Reingold, O., and Rothblum, G. (2018). Multicalibration: Calibration for the (computationally-identifiable) masses. In International Conference on Machine Learning , pages 1939--1948. PMLR

    2018

  25. [33]

    Hu, L., Tian, K., and Yang, C. (2024). Omnipredicting single-index models with multi-index models. arXiv preprint arXiv:2411.13083

    2024 arXiv

  26. [34]

    and Wu, Y

    Hu, L. and Wu, Y. (2024). 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. IEEE

    2024

  27. [35]

    Ito, S. (2020). A tight lower bound and efficient reduction for swap regret. Advances in Neural Information Processing Systems , 33:18550--18559

    2020

  28. [36]

    Jung, C., Lee, C., Pai, M., Roth, A., and Vohra, R. (2021). Moment multicalibration for uncertainty estimation. In Conference on Learning Theory , pages 2634--2678. PMLR

    2021

  29. [37]

    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

  30. [38]

    D., Shan, L., and Wu, Y

    Li, Y., Hartline, J. D., Shan, L., and Wu, Y. (2022). Optimization of scoring rules. In Proceedings of the 23rd ACM Conference on Economics and Computation , pages 988--989

    2022

  31. [39]

    Lu, J., Roth, A., and Shi, M. (2025). Sample efficient omniprediction and downstream swap regret for non-linear losses. arXiv preprint arXiv:2502.12564

    2025 arXiv

  32. [40]

    Luo, H. (2024). Csci 678: Theoretical machine learning lecture 3. https://haipeng-luo.net/courses/CSCI678/2024_fall/lectures/lecture3.pdf

    2024

  33. [41]

    Luo, H., Senapati, S., and Sharan, V. (2024). Optimal multiclass u-calibration error and beyond. In The Thirty-eighth Annual Conference on Neural Information Processing Systems (NeurIPS)

    2024

  34. [42]

    Luo, H., Senapati, S., and Sharan, V. (2025). Simultaneous swap regret minimization via kl-calibration. arXiv preprint arXiv:2502.16387

    2025

  35. [43]

    Noarov, G., Ramalingam, R., Roth, A., and Xie, S. (2023). High-dimensional prediction for sequential decision making. arXiv preprint arXiv:2310.17651

    2023 arXiv

  36. [44]

    Okoroafor, P., Kleinberg, R., and Kim, M. P. (2025). Near-optimal algorithms for omniprediction. arXiv preprint arXiv:2501.17205

    2025

  37. [45]

    and Valiant, G

    Qiao, M. and Valiant, G. (2021). Stronger calibration lower bounds via sidestepping. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages 456--466

    2021

  38. [46]

    and Zheng, L

    Qiao, M. and Zheng, L. (2024). On the distance from calibration in sequential prediction. In The Thirty Seventh Annual Conference on Learning Theory , pages 4307--4357. PMLR

    2024

  39. [47]

    and Shi, M

    Roth, A. and Shi, M. (2024). Forecasting for swap regret for all downstream agents. In Proceedings of the 25th ACM Conference on Economics and Computation , pages 466--488

    2024

  40. [48]

    S., and Zhang, J

    Tang, J., Wu, J., Wu, Z. S., and Zhang, J. (2025). Dimension-free decision calibration for nonlinear loss functions. arXiv preprint arXiv:2504.15615

    2025 arXiv

  41. [49]

    Zhao, S., Kim, M., Sahoo, R., Ma, T., and Ermon, S. (2021). Calibrating predictions to decisions: A novel approach to multi-class calibration. Advances in Neural Information Processing Systems , 34:22313--22324

    2021

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.