Pith. sign in

REVIEW 2 major objections 3 minor 41 references

Improved and Oracle-Efficient Online $\ell_1$-Multicalibration

T0 review · 2 major / 3 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 Online $\ell_1$-multicalibration reduces to an online product-reward game, yielding improved $\widetilde{\mathcal{O}}(T^{-1/3})$ rates for finite group families and oracle-efficient $\widetilde{\mathcal{O}}(T^{-1/4})$ rates with one…

desk verdict Solid reduction-based paper with a real result under transductive contexts; the sufficiently-separated branch has a genuine gap in the admissibility proof. read the letter →

arxiv 2505.17365 v2 pith:TQYEGTUW submitted 2025-05-23 cs.LG cs.DS

Rohan Ghuge , Vidya Muthukumar , Sahil Singla This is my paper
classification cs.LGcs.DS MSC 68Q3268W27
keywords onlinemulticalibrationℓ1-multicalibrationoracleefficiencylearningcalibrationFollow-the-Perturbed-Leaderno-regretmultigroupfairness
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

The paper establishes that online $\ell_1$-multicalibration---keeping forecasts unbiased within every group of a large family, not just overall---can be solved directly in the $\ell_1$ norm, rather than by converting weaker $\ell_2$ or $\ell_\infty$ guarantees. Its central reduction turns the problem into an online game with product-based rewards that the paper calls $\mathtt{OLPO}$, and from that reduction follow two algorithms: an $\widetilde{\mathcal{O}}(T^{-1/3})$ bound for finite group families (and, by covering, for many infinite families), nearly matching the best known rate for plain online calibration, and an $\widetilde{\mathcal{O}}(T^{-1/4})$ oracle-efficient bound that needs only one call per round to an offline optimization oracle under transductive or sufficiently separated contexts with binary-valued groups. The oracle-efficient bound improves the previous $\widetilde{\mathcal{O}}(T^{-1/8})$ rate for oracle-efficient online multicalibration and replaces an online regression oracle with a simpler offline one. The authors note that a similar finite-class rate could be obtained from a concurrent high-dimensional sequential prediction result; the paper's direct reduction is what also yields the oracle-efficient extension. If correct, the work brings multicalibration for large group families closer to being as cheap as plain calibration, with direct consequences for online omniprediction.

What carries the argument

The load-bearing object is the reduction to $\mathtt{OLPO}$, an online game in which each round the learner chooses a group $h$ and a sign vector $\theta$, the adversary reveals a context and a reward vector $f$, and the learner collects $\langle \theta, h(x)\cdot f\rangle$. The linearized version $\mathrm{Lin}$-$\mathtt{OLPO}$ rewrites this product reward as a linear reward in a higher-dimensional mixed-norm ball, letting the paper combine per-group online gradient descent with multiplicative weights. For oracle efficiency, the key machinery is the generalized Follow-the-Perturbed-Leader template with a perturbation translation matrix $\Gamma$; the matrix must be $\delta$-admissible (rows distinct, column entries separated) and implementable (its perturbations expressible as a small number of oracle queries). Lemma 5.2 builds such a $\Gamma$ from entries $h(x_j)\theta_i$, which is why the binary and transductive/small-separator assumptions enter, and Theorem 5.1 converts this into a regret bound of $O(B^2 N\sqrt{T}/\delta)$, which becomes $\widetilde{\mathcal{O}}(D T^{-1/4})$ after the reduction.

What would settle it

Run the oracle-efficient algorithm on a transductive instance with, say, $D=10$ binary groups, $M=8$ forecast bins and $T=10^5$, and check whether the observed $\ell_1$-multicalibration error tracks $\widetilde{\mathcal{O}}(T^{-1/4})$; if it instead tracks the earlier $T^{-1/8}$ rate, the claimed oracle-efficient improvement would be contradicted.

Watch

Extended reading notes

Core claim

The paper's central claim is that online $\ell_1$-multicalibration reduces to $\mathtt{OLPO}$ with essentially no loss: any no-regret algorithm for $\mathtt{OLPO}$ yields a multicalibration algorithm whose error is bounded by the regret divided by $T$, plus discretization and fluctuation terms (Theorem 3.1). For the improved rate, the paper linearizes $\mathtt{OLPO}$ into $\mathrm{Lin}$-$\mathtt{OLPO}$ by embedding all hypotheses into a higher-dimensional action space constrained by a mixed norm, then combines online gradient descent per hypothesis with multiplicative weights over hypotheses to obtain a regret of order $\widetilde{\mathcal{O}}(\sqrt{T|H|})$, giving $E[K(\pi_T,H)]=\widetilde{\mathcal{O}}(B T^{-1/3})$ for finite $H$. For large or infinite $H$, the paper instead feeds $\mathtt{OLPO}$ to a generalized Follow-the-Perturbed-Leader algorithm whose perturbation matrix is $\delta$-admissible and implementable; under transductive or small-separator contexts and binary-valued $H$, this uses a single offline oracle call per round and yields $E[K(\pi_T,H)]=\widetilde{\mathcal{O}}(B D T^{-1/4})$. Infinite families are handled by a $1$-Lipschitz property of the $\ell_1$-multicalibration error with respect to $H$, so a $\beta$-cover reduces them to the finite case at additive cost $\beta$.

Load-bearing premise

The advertised oracle-efficient rate rests on binary group functions and on contexts that are either known in advance or separable by a small set, because the perturbation matrix can then be encoded by finitely many context evaluations; if either condition fails, the proof does not deliver the bound.

Editorial extensions

If this is right

  • Finite group families get $\widetilde{\mathcal{O}}(B T^{-1/3})$ $\ell_1$-multicalibration error, improving on the previous $\widetilde{\mathcal{O}}(T^{-1/4})$ bound that came by transferring $\ell_\infty$ guarantees.
  • Oracle-efficient online multicalibration improves from $\widetilde{\mathcal{O}}(T^{-1/8})$ to $\widetilde{\mathcal{O}}(T^{-1/4})$ while using one offline oracle call per round instead of an online regression oracle.
  • Infinite families with finite $\beta$-covers inherit the $T^{-1/3}$ rate up to additive $\beta$; bounded linear functions on $[0,1]^d$ get error $\widetilde{\mathcal{O}}(B d^{1/2} T^{-1/3})$ with runtime $O((B\sqrt{T})^d)$.
  • Because $\ell_1$-multicalibration implies online omniprediction, these rates transfer to omniprediction guarantees for Lipschitz convex losses.
  • The authors state that the oracle-efficiency analysis should extend to smoothed or $K$-hint data, weakening the transductive/small-separator assumptions.

Reading between the lines

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

  • A consequence the authors leave implicit: the $\widetilde{\mathcal{O}}(T^{-1/3})$ rate for finite families is unlikely to be improved without also improving plain online calibration, since multicalibration with a single trivial group is just calibration.
  • The gap between $\widetilde{\mathcal{O}}(T^{-1/3})$ and $\widetilde{\mathcal{O}}(T^{-1/4})$ in the oracle-efficient setting comes from the linear dependence on the discretization size $M$ in the generalized Follow-the-Perturbed-Leader regret; if that dependence were reduced to $\sqrt{M}$, the same framework would plausibly yield the faster rate oracle-efficiently.
  • The $1$-Lipschitz covering argument is a generic recipe: any group family with known covering numbers would inherit these multicalibration rates once a cover is supplied.
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

2 major / 3 minor

Summary. The paper studies online ℓ1-multicalibration over T rounds. It proposes a reduction (Theorem 3.1) from online multicalibration to an online linear-product optimization problem (OLPO), using a halfspace oracle to convert OLPO actions into prediction distributions. For finite hypothesis classes it designs a no-regret algorithm for a linearized version of OLPO and obtains E[K(π_T,H)] ≤ O(B T^{-1/3} sqrt(log(6T|H|))); an extension via β-covers handles infinite classes (Theorem 1.2). For oracle efficiency, the paper designs a generalized Follow-the-Perturbed-Leader algorithm for OLPO and, under transductive or small-separator contexts with binary-valued H, constructs a perturbation matrix claimed to be 1-admissible and implementable, yielding E[K(π_T,H)] ≤ O(B D T^{-1/4} sqrt(log(T|H|))) with a single offline-oracle call per round.

Significance. The OLPO reduction is a clean and potentially reusable lens: it avoids the indirect ℓ2/ℓ∞ transfer used in prior work and yields the best-known T^{-1/3} rate for finite classes, with a modular oracle-efficient extension. The halfspace-oracle construction is proved rather than assumed, the covering argument for infinite classes is carefully stated, and the paper explicitly compares with Noarov et al. (2025). If the oracle-efficient branch is repaired, the T^{-1/4} oracle-efficient result would improve over the T^{-1/8} bound of Garg et al. (2024) and would replace an online regression oracle with a weaker offline oracle. The two gaps identified below are local to the oracle-efficient branch, but they are load-bearing for Theorem 1.4 as stated.

major comments (2)
  1. [§5.2, Lemma 5.2; Theorem 1.4] The proof of 1-admissibility in Lemma 5.2 is incomplete in the small-separator setting. For the case h=h′ and θ≠θ′, the proof requires an index j with h(x_j)≠0 and says 'otherwise we can simply remove h from the hypothesis class without loss of generality.' This is valid in the transductive setting, where X is the full context set and h≡0 on X is the zero function, but it is not valid in the small-separator setting, where X is only a separator and contexts outside X are allowed. A binary group h0 with h0(x)=0 for all x∈X but h0(x)=1 for some context outside X can have nonzero ℓ1-multicalibration error and can even be the maximizer of K(π_T,H); for this h0 every row Γ_{(h0,θ)} is the zero vector, so the distinct-row requirement in Definition 5.2 fails. Lemma B.2 then cannot infer (h_t,θ_t)=(h_{t+1},θ_{t+1}) from equality of the corresponding Γ rows, so the stability bound and hence the regret bound of Theorem 5.1 do not follow for such H. The sufficiently-separated branch of Theorem 1.4 therefore requires an additional assumption (e.g., that X separates every h∈H from the zero function), or a different perturbation construction.
  2. [§5.1, Theorem 5.1 and Appendix B.1] There is an inconsistency in the range of Γ used in the regret proof. Theorem 5.1 and Definition 5.2 allow Γ∈[-B,B]^{(|H|×2M)×N}, but the final steps of the proof in Appendix B.1 use Γ∈[0,1] and α⪰0 to bound E[α·Γ(h_1,θ_1)]≤N√T and to drop the term −α·Γ(h,θ*). The matrix constructed in Lemma 5.2 has entries in {-1,0,1}, so those steps are not justified as written. This is fixable by working with a nonnegative Γ (e.g., by splitting columns according to sign) or by carrying absolute-value bounds, but the current proof does not establish (16) for the stated Γ.
minor comments (3)
  1. [§4.1, Lemma 4.1] The statement of Lemma 4.1 uses H^B and ilde B_{1,∞} in the regret expression, while the proof treats a finite enumeration h^(1),...,h^(|H|); the notation should be aligned with the finite hypothesis class setting.
  2. [§4.2, Application 2] The exponent in the text 'β:=T^{-1/(2+d/2)}' and the resulting additive term appear garbled; the displayed formula should be corrected so that the second term is T^{-1/(2+d/2)} rather than the ambiguous 'T^{-1/2+d/2}'.
  3. [§5.2, final paragraph] The sentence 'setting the allowable error in the optimization oracle to ϵ=1/M=1/T^{1/4}' conflicts with Theorem 5.1, whose proof sets ϵ=1/√T; please clarify whether ϵ is the oracle accuracy or the discretization parameter and show explicitly how the chosen ϵ enters the regret bound.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the derivation is a genuine reduction with proved components and an external optimization oracle.

full rationale

The derivation is self-contained. Theorem 3.1 does not define the multicalibration error K in terms of the OLPO regret; it upper-bounds K by a sum of a dual-norm term, a martingale concentration term (Lemma 3.3), and the halfspace-oracle error, and the halfspace oracle is constructed and proved in Lemma 3.2/Appendix A.2 rather than assumed. Lemma 4.1 is an algebraic scaling identity between OLPO and Lin-OLPO rewards, and Lemma 4.2 is a standard OGD-plus-multiplicative-weights regret bound; no target rate is inserted as an input. Theorem 1.2's additive beta term follows from the 1-Lipschitz property of K proved in Lemma 4.3 and Claim 4.4, not from assuming the conclusion. In Section 5, the offline oracle is an external computational primitive for an auxiliary product-reward maximization: although that maximization equals the deterministic part of the multicalibration expression, the oracle supplies an action (h,theta) for the FTPL update, and the final guarantee is a regret-bound reduction that would hold for any oracle satisfying Definition 5.1. The perturbation matrix Lema 5.2 is constructed and proved, not imported from prior work, and Theorem 5.1 is proved from delta-admissibility and implementability. The only reference with author overlap (Wang et al. 2022) appears in related work and is not load-bearing. The skeptical concern about Lemma 5.2's removal of a group that vanishes on the separator is a potential correctness gap in the sufficiently-separated branch, not a circularity: it would invalidate a proof step but does not make the theorem's conclusion equivalent to its inputs. Therefore the paper has no significant circularity, and the appropriate score is 0.

Assumptions & free parameters 3 free parameters · 6 assumptions · 0 invented entities

The paper introduces no new physical or model entities. The free parameters are algorithmic design choices, primarily the discretization step and the perturbation scale, neither of which is fitted to data. The assumptions are standard for the oracle-efficiency literature: concentration inequalities, known regret bounds, a black-box offline oracle, binary groups, and transductive or small-separator contexts.

free parameters (3)
  • Discretization granularity m = m = T^{1/3} for Theorem 1.1; m = T^{1/4} implicitly for Theorem 1.4
    The grid size m controls the tradeoff between the approximation error B/m, the martingale concentration term, and the oracle-efficient regret term. It is chosen analytically, not fitted to data, but it is a parameter the central bounds depend on.
  • Covering parameter beta = beta = T^{-1/3} for polynomials; beta = T^{-1/(2+d/2)} for Lipschitz convex functions
    In Theorem 1.2, beta is chosen to balance the covering-number term and the additive beta term. It is a design choice, not fitted to observations.
  • Perturbation scale sqrt(T) in FTPL = Unif[0, sqrt(T)]
    This is the standard perturbation range in Follow-the-Perturbed-Leader, chosen to balance stability and approximation in the regret bound.
assumptions (6)
  • standard math Vector Azuma-Hoeffding inequality for martingales in R^M (Theorem A.1, from Hayes 2005).
    Used in Lemma 3.3 to bound the deviation between empirical and expected prediction indicators. This is a standard concentration tool.
  • standard math No-regret guarantees for online gradient descent and multiplicative weights update (Hazan et al. 2016).
    Central to Lemma 4.2. The specific regret bounds are cited, not re-derived.
  • standard math Generalized Follow-the-Perturbed-Leader stability lemma (Lemma B.2 and B.1 from Dudik et al. 2020).
    The proof of Theorem 5.1 relies on the be-the-approximate-leader lemma and the stability bound, adapted to the OLPO decision set. The paper includes proofs for completeness but the framework is from prior work.
  • domain assumption Existence of the offline oracle as a black box (Definition 5.1).
    The oracle-efficient result assumes access to an optimizer that solves the offline product-optimization problem to additive error epsilon. This is an external computational primitive.
  • domain assumption Binary-valued hypothesis class H: X -> {0,1} for Theorem 1.4.
    The admissibility proof in Lemma 5.2 relies on entries h(x_j) theta_i taking values in {-1,0,1}. This is a restriction, not a general feature of the problem.
  • domain assumption Transductive or small-separator contexts (Section 5.2).
    These assumptions guarantee a finite set of contexts of size D and make the perturbation matrix implementable. They are inherited from oracle-efficient online learning literature, e.g., Dudik et al. 2020.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Improved and Oracle-Efficient Online $\ell_1$-Multicalibration." pith.science (2026). https://pith.science/paper/TQYEGTUW

@misc{pith2026250517365,
  author       = {Pith},
  title        = {Pith review of: Improved and Oracle-Efficient Online $\ell_1$-Multicalibration},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TQYEGTUW}},
  note         = {Machine review of arXiv:2505.17365}
}
abstract

We study \emph{online multicalibration}, a framework for ensuring calibrated predictions across multiple groups in adversarial settings, across $T$ rounds. Although online calibration is typically studied in the $\ell_1$ norm, prior approaches to online multicalibration have taken the indirect approach of obtaining rates in other norms (such as $\ell_2$ and $\ell_{\infty}$) and then transferred these guarantees to $\ell_1$ at additional loss. In contrast, we propose a direct method that achieves improved and oracle-efficient rates of $\widetilde{\mathcal{O}}(T^{-1/3})$ and $\widetilde{\mathcal{O}}(T^{-1/4})$ respectively, for online $\ell_1$-multicalibration. Our key insight is a novel reduction of online \(\ell_1\)-multicalibration to an online learning problem with product-based rewards, which we refer to as \emph{online linear-product optimization} ($\mathtt{OLPO}$). To obtain the improved rate of $\widetilde{\mathcal{O}}(T^{-1/3})$, we introduce a linearization of $\mathtt{OLPO}$ and design a no-regret algorithm for this linearized problem. Although this method guarantees the desired sublinear rate (nearly matching the best rate for online calibration), it is computationally expensive when the group family \(\mathcal{H}\) is large or infinite, since it enumerates all possible groups. To address scalability, we propose a second approach to $\mathtt{OLPO}$ that makes only a polynomial number of calls to an offline optimization (\emph{multicalibration evaluation}) oracle, resulting in \emph{oracle-efficient} online \(\ell_1\)-multicalibration with a rate of $\widetilde{\mathcal{O}}(T^{-1/4})$. Our framework also extends to certain infinite families of groups (e.g., all linear functions on the context space) by exploiting a $1$-Lipschitz property of the \(\ell_1\)-multicalibration error with respect to \(\mathcal{H}\).

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

41 extracted references · 38 canonical work pages

  1. [1]

    Blackwell approachability and no-regret learning are equivalent

    Jacob Abernethy, Peter L Bartlett, and Elad Hazan. Blackwell approachability and no-regret learning are equivalent. In Proceedings of the 24th Annual Conference on Learning Theory, pages 27--46, 2011

    work page 2011

  2. [2]

    Oracle efficient algorithms for groupwise regret

    Krishna Acharya, Eshwar Ram Arunachaleswaran, Sampath Kannan, Aaron Roth, and Juba Ziani. Oracle efficient algorithms for groupwise regret. In 12th International Conference on Learning Representations (ICLR 2024), 2024

    work page 2024

  3. [3]

    Taming the monster: A fast and simple algorithm for contextual bandits

    Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In International Conference on Machine Learning, pages 1638--1646. PMLR, 2014

    work page 2014

  4. [4]

    Relative loss bounds for on-line density estimation with the exponential family of distributions

    Katy S Azoury and Manfred K Warmuth. Relative loss bounds for on-line density estimation with the exponential family of distributions. Machine learning, 43: 0 211--246, 2001

    2001

  5. [5]

    Smoothed online learning is as easy as statistical learning

    Adam Block, Yuval Dagan, Noah Golowich, and Alexander Rakhlin. Smoothed online learning is as easy as statistical learning. In Conference on Learning Theory, pages 1716--1786. PMLR, 2022

    work page 2022

  6. [6]

    -entropy of convex sets and functions

    Efim Bronshtein. -entropy of convex sets and functions. Siberian Mathematical Journal, 17 0 (3): 0 393--398, 1976

    work page 1976

  7. [7]

    Breaking the T ^ 2/3 barrier for sequential calibration

    Yuval Dagan, Constantinos Daskalakis, Maxwell Fishelson, Noah Golowich, Robert Kleinberg, and Princewill Okoroafor. Breaking the T ^ 2/3 barrier for sequential calibration. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC'25, 2025

    work page 2025

  8. [8]

    Learning in auctions: Regret is hard, envy is easy

    Constantinos Daskalakis and Vasilis Syrgkanis. Learning in auctions: Regret is hard, envy is easy. In Proceedings of the 57th IEEE Symposium on Foundations of Computer Science, FOCS'16, pages 219--228. IEEE, 2016

    work page 2016

Show all 41 references
  1. [9]

    The well-calibrated bayesian

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

    1982

  2. [10]

    Group-wise oracle-efficient algorithms for online multi-group learning

    Samuel Deng, Daniel Hsu, and Jingwen Liu. Group-wise oracle-efficient algorithms for online multi-group learning. arXiv preprint arXiv:2406.05287, 2024

    2024 arXiv

  3. [11]

    Oracle-efficient online learning and auction design

    Miroslav Dud \' k, Nika Haghtalab, Haipeng Luo, Robert E Schapire, Vasilis Syrgkanis, and Jennifer Wortman Vaughan. Oracle-efficient online learning and auction design. Journal of the ACM (JACM), 67 0 (5): 0 1--57, 2020

    2020

  4. [12]

    A proof of calibration via blackwell's approachability theorem

    Dean P Foster. A proof of calibration via blackwell's approachability theorem. Games and Economic Behavior, 29 0 (1-2): 0 73--78, 1999

    1999

  5. [13]

    Calibration via regression

    Dean P Foster and Sham M Kakade. Calibration via regression. In 2006 IEEE Information Theory Workshop-ITW'06 Punta del Este, pages 82--86. IEEE, 2006

    2006

  6. [14]

    Asymptotic calibration

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

    1998

  7. [15]

    Beyond ucb: Optimal and efficient contextual bandits with regression oracles

    Dylan Foster and Alexander Rakhlin. Beyond ucb: Optimal and efficient contextual bandits with regression oracles. In International Conference on Machine Learning, pages 3199--3210. PMLR, 2020

    2020

  8. [16]

    An easier way to calibrate

    Drew Fudenberg and David K Levine. An easier way to calibrate. Games and economic behavior, 29 0 (1-2): 0 131--137, 1999

    1999

  9. [17]

    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 (SODA), pages 2725--2792. SIAM, 2024

    2024

  10. [18]

    Multicalibration as boosting for regression

    Ira Globus-Harris, Declan Harrison, Michael Kearns, Aaron Roth, and Jessica Sorrell. Multicalibration as boosting for regression. In Proceedings of the 40th International Conference on Machine Learning, ICML'23, 2023

    2023

  11. [19]

    Omnipredictors

    Parikshit Gopalan, Adam Tauman Kalai, Omer Reingold, Vatsal Sharan, and Udi Wieder. Omnipredictors . In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), pages 79:1--79:21, 2022

    2022

  12. [20]

    Swap agnostic learning, or characterizing omniprediction via multicalibration

    Parikshit Gopalan, Michael Kim, and Omer Reingold. Swap agnostic learning, or characterizing omniprediction via multicalibration. Advances in Neural Information Processing Systems, 36: 0 39936--39956, 2023

    2023

  13. [21]

    Covering numbers for convex functions

    Adityanand Guntuboyina and Bodhisattva Sen. Covering numbers for convex functions. IEEE Transactions on Information Theory, 59 0 (4): 0 1957--1965, 2012

    1957

  14. [22]

    Pai, and Aaron Roth

    Varun Gupta, Christopher Jung, Georgy Noarov, Mallesh M. Pai, and Aaron Roth. Online Multivalid Learning: Means, Moments, and Prediction Intervals . In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), pages 82:1--82:24, 2022

    2022

  15. [23]

    Oracle-efficient online learning for smoothed adversaries

    Nika Haghtalab, Yanjun Han, Abhishek Shetty, and Kunhe Yang. Oracle-efficient online learning for smoothed adversaries. Advances in Neural Information Processing Systems, 35: 0 4072--4084, 2022

    2022

  16. [24]

    Calibrated forecasts: The minimax proof

    Sergiu Hart. Calibrated forecasts: The minimax proof. arXiv preprint arXiv:2209.05863, 2022

    2022 arXiv

  17. [25]

    A simple adaptive procedure leading to correlated equilibrium

    Sergiu Hart and Andreu Mas-Colell. A simple adaptive procedure leading to correlated equilibrium. Econometrica, 68 0 (5): 0 1127--1150, 2000

    2000

  18. [26]

    A large-deviation inequality for vector-valued martingales

    Thomas P Hayes. A large-deviation inequality for vector-valued martingales. Combinatorics, Probability and Computing, 2005

    2005

  19. [27]

    The computational power of optimization in online learning

    Elad Hazan and Tomer Koren. The computational power of optimization in online learning. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 128--141, 2016

    2016

  20. [28]

    Introduction to online convex optimization

    Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends in Optimization , 2 0 (3-4): 0 157--325, 2016

    2016

  21. [29]

    Multicalibration: Calibration for the (computationally-identifiable) masses

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

    1939

  22. [30]

    Moment multicalibration for uncertainty estimation

    Christopher Jung, Changhwa Lee, Mallesh Pai, Aaron Roth, and Rakesh Vohra. Moment multicalibration for uncertainty estimation. In Conference on Learning Theory, pages 2634--2678. PMLR, 2021

    2021

  23. [31]

    Efficient algorithms for online decision problems

    Adam Kalai and Santosh Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71 0 (3): 0 291--307, 2005

    2005

  24. [32]

    Multiaccuracy: Black-box post-processing for fairness in classification

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

    2019

  25. [33]

    Universal adaptability: Target-independent inference that competes with propensity scoring

    Michael P Kim, Christoph Kern, Shafi Goldwasser, Frauke Kreuter, and Omer Reingold. Universal adaptability: Target-independent inference that competes with propensity scoring. Proceedings of the National Academy of Sciences, 119 0 (4): 0 e2108097119, 2022

    2022

  26. [34]

    Online minimax multiobjective optimization: Multicalibeating and other applications

    Daniel Lee, Georgy Noarov, Mallesh Pai, and Aaron Roth. Online minimax multiobjective optimization: Multicalibeating and other applications. Advances in Neural Information Processing Systems, 35: 0 29051--29063, 2022

    2022

  27. [35]

    High-dimensional prediction for sequential decision making

    Georgy Noarov, Ramya Ramalingam, Aaron Roth, and Stephan Xie. High-dimensional prediction for sequential decision making. In Proceedings of the 42nd International Conference on Machine Learning (To Appear), ICML'25, 2025

    2025

  28. [36]

    Calibration and internal no-regret with random signals

    Vianney Perchet. Calibration and internal no-regret with random signals. In International Conference on Algorithmic Learning Theory, pages 68--82. Springer, 2009

    2009

  29. [37]

    Stronger calibration lower bounds via sidestepping

    Mingda Qiao and Gregory Valiant. Stronger calibration lower bounds via sidestepping. In STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages 456--466. ACM , 2021

    2021

  30. [38]

    The reproducible properties of correct forecasts

    Alvaro Sandroni. The reproducible properties of correct forecasts. International Journal of Game Theory, 32 0 (1): 0 151--159, 2003

    2003

  31. [39]

    Calibration with many checking rules

    Alvaro Sandroni, Rann Smorodinsky, and Rakesh V Vohra. Calibration with many checking rules. Mathematics of operations Research, 28 0 (1): 0 141--153, 2003

    2003

  32. [40]

    Efficient algorithms for adversarial contextual learning

    Vasilis Syrgkanis, Akshay Krishnamurthy, and Robert Schapire. Efficient algorithms for adversarial contextual learning. In International Conference on Machine Learning, pages 2159--2168. PMLR, 2016

    2016

  33. [41]

    Adaptive oracle-efficient online learning

    Guanghui Wang, Zihao Hu, Vidya Muthukumar, and Jacob D Abernethy. Adaptive oracle-efficient online learning. Advances in Neural Information Processing Systems, 35: 0 23398--23411, 2022

    2022

Pith tools

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