- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
This paper studies the rates at which contextual swap regret can be guaranteed. The setup is as follows: At every round a real valued label y_t is realized, and just before the realization, the algorithm must commit to a forecast p_t. The algorithm seeks to minimize squared error. The weakest regret benchmark, external regret, compares the algorithm's squared loss to that of the best single prediction p* in hindsight. Swap regret compares to a stronger comparator: each distinct prediction value v, it allows swapping out all predictions {p_t : p_t = v} with a different fixed value p*_v. External regret is the special case in which p*_v = p* for all v. Contextual swap regret goes one step further, and allows swapping out predictions in the set {p_t : p_t = v} with a function f_v(x) of the context. Swap regret is the special case of contextual swap regret where each f_v(x) = p*_v is a constant. This paper studies the case in which the functions f_v are affine in the context.
There is an important technical distinction in how we might measure swap regret. We could measure it in expectation over the randomness of the prediction distribution ("pseudo" swap regret), or with respect to the realizations? Prior work left a gap. *(Well, actually there is some more recent prior work that has been on arxiv for a few months that complicates the distinction --- see the related work discussion in weaknesses) It gave a T^{1/3} bound for pseudo-swap regret, but only T^{3/5} for realized. This paper closes the gap and gives upper and lower bounds of T^{1/3} for realized pseudo-swap regret.
Critical strengths
The theorem is correct and makes real progress on the problem of pinning down our understanding of contextual swap reget.
Critical weaknesses
This paper is quite hard to read; it is written in a noticable LLM voice. It could use a heavy human pass, both for language and organization. Other than writing, the biggest issue with the paper is its incomplete discussion of related work, of which there is a lot. I enumerate some of the missing related work below (with LLM assistance, although all connections are verified). Some is just missing historical context, but there is also a recent preprint that has been on arxiv for several months that obtains similar results and should be discussed/compared.
Missing related work
The related-work discussion needs a substantive revision. Below are some uncited papers and how they are related; some are just for completeness of the historical context, but others have direct relevance to the novelty of the results claimed in this paper:
1. “High-Dimensional Prediction for Sequential Decision Making”
Authors: Georgy Noarov, Ramya Ramalingam, Aaron Roth, and Stephan Xie. 2023 preprint; ICML 2025. https://arxiv.org/abs/2310.17651 https://proceedings.mlr.press/v267/noarov25b.html
This paper should be cited in the calibration history in Section 2 and in the discussion of Corollary 5. It gives the first efficient online multicalibration algorithm achieving cumulative O(T^{2/3}) ECE, equivalently normalized O(T^{-1/3}) ECE. Ghuge et al. later gave a different algorithm recovering this result and is cited, but the original paper is uncited.
2. “Simultaneous Swap Regret Minimization via KL-Calibration”
Authors: Haipeng Luo, Spandan Senapati, and Vatsal Sharan. 2025. https://arxiv.org/abs/2502.16387
This is a different paper from the currently cited “Improved Bounds for Swap Multicalibration and Swap Omniprediction,” despite having the same authors. It should be cited as a particularly close technical antecedent to Lemmas 2 and 3.
Its Theorem 3 gives an algorithm-independent, high-probability conversion from pseudo squared calibration error to realized squared calibration error: the latter is at most a constant multiple of the former plus an additive O(K log(K/delta)) term for K prediction values. Consequently, the conversion preserves the cube-root horizon exponent in the noncontextual setting.
This is structurally close to the present conversion, although is not written for contextual regret. The authors should explain what additional difficulty the affine class creates and how their localization/pullback argument addresses it. The relevant novelty is potentially this contextual extension, not the general observation that sampling need not worsen the cube-root exponent.
3. “Fast Rates for Swap-Agnostic Learning of Proper Losses”
Author: Princewill Okoroafor. 2026 preprint. https://arxiv.org/abs/2607.28856
This is a direct comparison for the main upper-bound claim. Theorem 4.5 gives high-probability realized hypothesis-swap regret of order \widetilde O(T^{1/3} (log |H|)^{2/3}) for a finite bounded hypothesis class H and a fixed Lipschitz proper loss, including squared loss. The benchmark permits a different hypothesis at each issued prediction value. The proof uses a second-order guarantee and a negative quadratic activity term to cancel the variance-related cost, making it relevant to the manuscript's technical narrative as well as its rate.
There is also a straightforward statistical implication for the present affine class. Take an epsilon-net of the affine parameter ball and clip the resulting functions to [0,1]. Its logarithmic size is O_R((d+1) log(1/epsilon)). Clipping can only improve a comparator's squared loss, and approximation adds O(T epsilon) to regret. Taking epsilon=T^{-2} therefore recovers the same \widetilde O_R(T^{1/3}d^{2/3}) dependence for binary outcomes.
This net construction is not computationally efficient, but it does preclude an unqualified claim that the statistical rate was previously unknown. The paper also gives an expected Omega(T^{1/3}) lower bound for a fixed three-hypothesis class in Theorem 4.7, using the recalibration lower bound discussed below.
4. “Optimal Recalibration of an Online Predictor”
Authors: Lunjia Hu, Kevin Tian, and Chutong Yang. 2026 preprint. https://arxiv.org/abs/2607.19689
This paper should be cited in Section 5 and Appendix B as a direct predecessor of the scalar lower bound. Its Theorem 13 proves that simultaneously achieving expected normalized calibration error epsilon and expected average squared-loss excess epsilon^2 relative to supplied forecasts requires T=Omega(epsilon^{-3}). Its hard instance cycles through evenly spaced forecast values in [1/4,3/4] and generates independent Bernoulli labels with those means. This is the same basic construction used in the present scalar lower bound, and it can be sampled before the learner's randomization.
The expected Omega(T^{1/3}) contextual swap-regret lower bound follows directly in the present dimension-one, radius-one setting. Take the supplied forecast q_t as the context. The affine class contains the identity comparator f(x)=x and every constant comparator. Thus contextual swap regret S_T dominates both the excess squared loss relative to q_t and the squared calibration error. In particular, E[ECE] <= sqrt(E[S_T]/T), while expected average excess loss is at most E[S_T]/T. An expected regret guarantee o(T^{1/3}) would contradict the recalibration lower bound.
The manuscript should distinguish the earlier expected lower bound and construction from its new probability guarantee, rather than presenting the entire scalar obstruction without attribution.
5. “Optimal Lower Bounds for Online Multicalibration”
Authors: Natalie Collina, Jiuyao Lu, Georgy Noarov, and Aaron Roth. FOCS 2026. https://arxiv.org/abs/2601.05245
This paper establishes optimal cube-root normalized multicalibration lower bounds.
It should be cited both in the discussion of optimal calibration rates and for the provenance of the lower-bound construction. Hu, Tian, and Yang explicitly identify their cyclic Bernoulli construction with the construction in this paper. The present manuscript uses the same basic arrangement of repeatedly visited, separated Bernoulli means and a tradeoff between staying near those means and correcting realized noise.
This is probably the originator of this kind of lower bound instance.
6. “Multicalibration as Boosting for Regression”
Authors: Ira Globus-Harris, Declan Harrison, Michael Kearns, Aaron Roth, and Jessica Sorrell. ICML 2023. https://arxiv.org/abs/2301.13767
This paper should be cited for the connection between multicalibration, regression within prediction level sets, and squared-loss swap-like optimality. It characterizes multicalibration through the absence of sufficiently useful squared-loss corrections and develops a regression-oracle boosting algorithm organized around prediction level sets.
This is a direct conceptual antecedent to the present interpretation of contextual replacements as an audit for correctable errors, as well as to the regret-to-multicalibration argument in Corollary 5. The underlying idea that a residual correlation can be turned into a squared-loss improvement is not new to the present paper. The discussion should explain whether its deterministic reduction is a specialization, a quantitative refinement, or a same-radius variant of earlier relationships.
7. “Efficient Swap Multicalibration of Elicitable Properties”
Authors: Lunjia Hu, Haipeng Luo, Spandan Senapati, and Vatsal Sharan. 2025 preprint. https://arxiv.org/abs/2511.04907
This paper should be included in the discussion of the calibration frontier and Corollary 5. It gives an oracle-efficient reduction from online agnostic learning to swap multicalibration for general elicitable properties and bounded hypothesis classes. For the mean and squared calibration-error convention, its guarantees include cumulative \widetilde O(T^{1/3}) error, yielding normalized squared error \widetilde O(T^{-2/3}) and normalized l1 error \widetilde O(T^{-1/3}).
The comparison is not only about matching the horizon exponent. Its linear-class corollary uses OGD and gives dimension-independent error bounds under its unit-norm assumptions, so the manuscript should explicitly compare test classes, normalization, dimension dependence, and computational assumptions.
Questions for authors
Please describe how you plan to revise the papers exposition to make it easier for a human being to follow, and describe how you will incorporate the missing related work. Do you agree that Okoroafor gives a comparable (albeit perhaps computationally inefficient) upper bound?
Comparable prior bounds, the new results, and a clearer exposition
Q(c). Does Okoroafor already give a comparable upper bound?
Yes. Okoroafor's Theorem 4.5 gives a comparable statistical upper bound for binary outcomes. Our advance is an efficient construction on the continuous affine class, together with probability and dimension lower bounds. The original learner updates directly on the coefficient ball; the revision explicitly compares it with the finite-class result.
Applying Õ(T^(1/3)(log|H|)^(2/3)) to a clipped ε-net of our ball gives log|H|=O_R((d+1)log(1/ε)) and approximation cost at most 2√2 Tε. Taking ε=T^(-2) recovers Õ_R(T^(1/3)d^(2/3)). Okoroafor also uses a negative quadratic term to cancel second-order cost. The revised Introduction and Related Work credit these connections.
Applying that algorithm directly to the cover maintains (N+1)|H| weights. Our ONS learner works on the continuous ball, with O(Nd²) updates plus projection and a stationary-distribution solve; the cover is used only in the proof. Our bound permits real outcomes in [0,1] on oblivious sequences; Okoroafor permits binary outcomes with adaptation before each fresh prediction draw. Table 1 and Appendix F.1 compare these protocols and costs.
W/Q(b). How are the seven missing works incorporated?
All seven are cited and compared in the revision. We distinguish continuous-class computation, uniform sampling control within prediction buckets, fixed-confidence lower bounds and the dimension–horizon expected minimax characterization.
Noarov–Ramalingam–Roth–Xie. We credit their efficient online multicalibration result before Ghuge: for finite events and discrete bins, expected cumulative Õ(T^(2/3)) error, or normalized Õ(T^(-1/3)), with its computational access stated.
Luo–Senapati–Sharan, KL-Calibration. Their Theorem 3 already gives Cal₂≤6 PCal₂+96K log(4K/δ) with probability at least 1−δ, preserving the scalar cube-root exponent. Our extension controls all permitted affine replacements in every bucket simultaneously: localize deviations by squared replacement distance, then absorb them by feasible mixing with the constant prediction. Lemmas 2–3 explain this continuous-class step.
Okoroafor. The cover recovers the same binary-outcome statistical rate, while direct enumeration maintains (N+1)|H| weights. Our continuous ONS updates avoid this enumeration. Table 1 and F.1 compare the rate, outcome protocol and computation as above.
Hu–Tian–Yang. Taking their supplied forecast as context makes identity and constant corrections available, yielding an expected scalar Ω(T^(1/3)) swap-regret obstruction; Okoroafor's Theorem 4.7 also gives an expectation bound. Our Theorem 6 proves P(S≥cδT^(1/3))≥1−δ, with absolute c under the stated δ-dependent horizon condition. The revision separates the prior expectation result from this probability guarantee.
Collina–Lu–Noarov–Roth. We credit the cyclic Bernoulli construction used by Hu–Tian–Yang. Our dimensional construction must also satisfy one joint coefficient-norm constraint, including at radius one. It yields expected Ω(T^(1/3)d^(2/3)) under the theorem's horizon condition. With the upper bounds, the expected minimax order is min{T^(1/3)d^(2/3),T^(3/5)} up to logarithms, for fixed R≥1.
Globus-Harris et al. Their regression–calibration connection uses level-set regression, residual correlation and squared-loss improvement. Our bounded coefficient ball makes arbitrary shifts or rescaling infeasible. Feasible mixing gives the quantitative same-radius form MC₁≤C_mc√(S/T), MC₂≤C_mc²S/T (A.5).
Hu–Luo–Senapati–Sharan. Their OGD reduction for unit-norm linear tests gives dimension-independent cumulative squared swap-calibration error Q=Õ(T^(1/3)), hence Q/T=Õ(T^(-2/3)) and normalized L1 error Õ(T^(-1/3)). Q measures residual/test correlations within buckets; our S measures the largest squared-loss reduction from permitted affine replacements. Their rates are not interchangeable. Our corollary derives MC₂=Õ(T^(-2/3)d^(2/3)) and MC₁=Õ(T^(-1/3)d^(1/3)) from S after radius scaling. Related Work compares metrics, test classes and oracle access; our main result directly controls replacement gain and characterizes its expected minimax order.
W/Q(a). How is the argument made easier to follow?
The revision defines realized and probability-weighted records before the theorem, explaining why optimizing corrections prevents identifying pseudo-regret with expected realized regret. It then connects the deviation term, squared replacement distance, feasible midpoint identity and finer grid. The original conceptual figure is integrated into the Introduction; the new proof figure distinguishes the exact identity from the high-probability bound. Table 1 and the lower-bound discussion identify prior rates and constructions alongside our computation, probability and dimension results.