acceptodds
Under review as a conference paper at ICLR 2027

Instance-Adaptive Online Multiclass Multicalibration

Abstract

We study online multiclass multicalibration over rounds, and give an algorithm with beyond-worst-case guarantees. With possible outcomes, forecasts lie in a simplex of dimension . In the worst case, cumulative multicalibration error scales with , which becomes untenable once exceeds a small constant. Our algorithm adapts to the geometry of the realized sequence: if the sequence of adversarially selected outcome means lies in an affine subspace of dimension , it obtains error with high probability. The algorithm adapts to this structure without knowing the subspace or its dimension. This rate is minimax optimal up to polylogarithmic factors. For a stochastic instance with a fixed conditional mean, the bound specializes to , giving a square-root dependence on the horizon.

Primary area:
learning theory
Keywords:
Multiclass Multicalibration, Online Learning, Instance-Adaptive Algorithm

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 2 reviews, above 85% of the others.
Reviewer_SN6GOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper considers the online multiclass multicalibration problem, where at each step the learner produces a distribution over possible values of Y, and a version of ECE is studied. One main result of the paper is to provide an upper bound on ECE using the affine dimension of a set consisting of the conditional expectations of the observed outcomes y_t, ,t=1,2... They also provide a lower bound that matches the upper bound up to a factor of log(T)^2

Critical strengths

It is an interesting and problem to study, and the technical results seem correct to me. It is good to see a lower bound that matches the upper bound in terms of n and s.

Critical weaknesses

I don't get a good intuition/insight into the results. The writing could also be made clearer (for example, in the problem formulation part). I mention some of these in the question section.

Questions for authors
    • the affine dimension of the conditional means enters the bounds. What is the intuition behind this result? What significance does this quantity have, and why does it play a role for this problem?
  • the motivating question that appears in the paper is “Can an online algorithm make predictions that are guaranteed…., yet adapt to the structure of the realized sequence to obtain substantially better rates on easier instances?” I don’t quite understand the second sentence in the question, and furthermore, how the results shed light on this.

  • section 2.1 I’m a bit puzzled by the statement “an adversary generates y_t”. According to the displayed expression for \mu_t, there is an expectation w.r.t. y_t one can take. So it seems to suggest that y_t is generated according to a distribution (presumably unknown), conditioned on \mathcal F_t. What is this distribution on y_t and can it depend on what (i.e., adversarial in what sense)?

  • section 2.1 how are x_t's generated? Are they generated according to an (unknown) distribution, or is it assumed to be an adversarial deterministic sequence?

3 comments

Thank you for the feedback. We will make the paper easier to follow in revisions.

Q1. Affine dimension of the conditional means. The intuition is that if the conditional means lie in a low-dimensional affine subspace, the learner only needs enough forecasts to cover that region at a given resolution, not the entire simplex. The learner builds forecasts from weighted averages of outcomes; with enough data these are close to weighted averages of the conditional means, which remain in the same affine subspace. As a result, our bound on cumulative multicalibration error grows more slowly than in the full-dimensional case.

Q2. What adaptation means. The learner does not choose between a worst-case algorithm and a low-dimensional algorithm. It runs the same rule in both cases. On arbitrary sequences it retains the worst-case guarantee; when the conditional mean is fixed, for example, its cumulative error over TT rounds with nn classes is O~(nT)\widetilde O(\sqrt{nT}), without the learner being told that the mean is fixed.

Q3. How yty_t is generated. After observing the history, the current context xtx_t, and the announced forecast distribution πt\pi_t, nature may choose any conditional distribution for yty_t, but it cannot condition that distribution on the sampled forecast ptp_t. The vector μt\mu_t is the mean of this distribution; a deterministic outcome is the special case of a point mass, so our model is only more general.

Q4. How xtx_t is generated. xtx_t is the contextual information for round tt. We make no assumption about how the contexts are generated: they may be deterministic or random. We only require that the learner observes xtx_t before choosing its forecast distribution πt\pi_t. For example, when predicting tomorrow's weather, xtx_t might include the city and today's temperature.

Thanks for the clarification.

Re. the last point (how x_t is generated), I think in this case it is standard in the literature to make it explicit that x_t is an arbitrary deterministic sequence (in the sense that the result should hold in the worst case). On the other hand, if it is random (i.e., if there is a probability space and a measure behind it, potentially unknown), it should also be stated explicitly.

We study the online adversarial setting, and the x_t represent an arbitrary sequence. We'll emphasize this to avoid ambiguity --- thanks for pointing out a potential point of confusion.

Reviewer_QZnUOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies online multiclass multicalibration, where at each round the learner announces a probability vector over nn classes and, within each group of a given family, must keep the cumulative ℓ1\ell_1 distance between forecasts and empirical outcome frequencies small. Its main result is an algorithm whose error adapts to the affine dimension ss of the realized sequence of conditional outcome means: it guarantees error of order O~(n1/(s+2)T(s+1)/(s+2))\tilde O(n^{1/(s+2)} T^{(s+1)/(s+2)}) with high probability, without ever being told ss or the containing subspace, and a matching lower bound, up to polylog factors, shows the rate is minimax optimal. For the special case of a fixed conditional mean (s=0s = 0) the bound becomes O~(nT)\tilde O(\sqrt{nT}). The algorithm combines a second-order swap-regret forecaster under a logarithmic scoring rule with a block-based, multi-resolution discovery protocol, and the validation is entirely theoretical.

Critical strengths
  1. The algorithm provably attains the O~(n1/(s+2)T(s+1)/(s+2))\tilde O(n^{1/(s+2)} T^{(s+1)/(s+2)}) rate for any realized affine dimension ss, with no knowledge of ss or the subspace, while a lower bound on a fixed instance with only O(log⁡3T)O(\log^3 T) groups matches it up to polylog factors. The guarantee even degrades gracefully when the means only lie near a low-dimensional set, holding simultaneously for all such sets on a single high-probability event, which is a clean and strong way to close the problem.

  2. The heart of the analysis is a dimension-uniform packing argument that reduces Hellinger packing near an ss-dimensional set to Euclidean packing in dimension ss, which is what keeps the error's dependence on the number of classes at n1/(s+2)n^{1/(s+2)} instead of something polynomial in nn. Abstracting this into general global and local packing profiles in the appendix yields guarantees for any approximating family, not just affine subspaces, so the technical contribution stands on its own.

Critical weaknesses
  1. For a paper whose motivation leans on language prediction and downstream decision making, the complete absence of empirical validation is a real gap, and even a small synthetic check would help. The algorithm is also extremely heavy, the controller threshold is on the order of a million, and the runtime is polynomial with a large hidden degree, so it is not credible that the method runs at the scale of the motivating applications, and nothing demonstrates its practical usefulness.

  2. The proof is a long chain: the adaptive resolution argument is sketched in the main text and fully justified only in the appendix, and the lower bound leans on external to-appear results for its hashing construction and its noise lower bound. Since the whole contribution rides on this chain, I would want either those tools to be published or the relevant lemmas made self-contained before signing off on complete soundness.

Questions for authors
  1. (Clarification) Can you offer any evidence of empirical behavior, even on small synthetic instances, or comment on whether a simplified variant of the algorithm is implementable at realistic scale? The practical claims carry weight only insofar as the algorithm can actually run in the motivating settings.
  2. (Clarification) Which specific steps of the lower bound depend on results that are not yet published, namely the hashing lemma, the noise lower bound, and the ambient-dimension extension of the binary bound? It would help to state the dependency precisely or to make those lemmas self-contained.
  3. (Future work) The per-round cost of solving the stationarity equations over the discovered prediction set grows quickly with the number of predictions; is there a sparser or incremental way to structure the swap-regret comparisons?
3 comments

Thank you for your comments and suggestions. Our responses are as follows.

W1 / Q1. Empirical evidence and practical scope. We first highlight two points about the algorithm’s computational cost. The controller threshold determines when to switch resolutions, and its coefficient does not multiply the per-round computational cost. The runtime of our algorithm is polynomial with explicit parameters.

To address your questions about empirical behavior and computational cost, we implemented our method and two general online multicalibration frameworks, Noarov et al. and Farina–Perdomo, for the same group-conditioned multiclass problem. Our empirical configuration achieves lower mean exact multicalibration error in all 12 tested conditions than both baselines and their nonconstant-grid controls.

We cycle through 32 forest sites from the UCI Covertype dataset over 16,384 rounds, using each site’s recorded features as the context. We generate the class labels synthetically rather than using the original forest-cover labels, and evaluate calibration across 11 groups. We test n=16n=16 and n=64n=64 classes; the candidate class-probability vectors span an affine space of dimension s=1s=1 or s=4s=4. For each context, we choose the vector of class probabilities in one of three ways: on a fixed schedule; to maximize the learner’s expected cumulative multicalibration error after the current round; or by making a scheduled choice once per context in each 1,024-round block and using the maximizing rule otherwise. The adversary sees the learner’s past and the probabilities it assigns to possible forecasts, but not which forecast it actually draws this round. Thus two learners facing the same adaptive rule can receive different outcomes. Neither the candidate class-probability vectors nor the dimension of their affine span is given to the learners.

We instantiate Noarov's framework and Farina–Perdomo's finite-test Hedge construction with calibration tests for each group and prediction-grid cell. We select grid resolutions using separate development data, then fix them for three fresh evaluation seeds. For both baselines, the grid with the lowest error on development data always issued the uniform forecast. We also report results for each baseline's best validated grid among those that could issue more than one forecast.

The discovery coefficient controls how much weighted data the learner must accumulate before it proposes a new forecast. We compare the prescribed value of 10241024 with 0.20.2, selected on separate development data. Both runs keep Ctest=3×106C_{\mathrm{test}}=3\times10^6 fixed; this second coefficient sets the error threshold for switching to a coarser resolution. At this horizon, the prescribed discovery coefficient leaves the forecast uniform throughout, tying both development-selected baselines and outperforming their nonconstant alternatives. The improvement over uniform comes from allowing earlier discovery with coefficient 0.20.2.

Outcome rulennssOurs, mass 0.2Ours, mass 1024 / uniformNoarov, nonconstantFarina–Perdomo, nonconstant
Predetermined drift1610.1755 (4.46s)0.2236 (0.93s)0.4044 (12.63s)0.2737 (7.97s)
Predetermined drift1640.1654 (4.41s)0.2233 (0.93s)0.4042 (13.39s)0.2737 (7.86s)
Predetermined drift6410.2093 (3.22s)0.2352 (0.97s)0.3417 (17.34s)0.3640 (29.08s)
Predetermined drift6440.2098 (3.25s)0.2342 (1.03s)0.3410 (16.38s)0.3638 (28.92s)
Adaptive greedy1610.2507 (4.48s)0.3863 (0.94s)0.4121 (13.27s)0.4227 (7.86s)
Adaptive greedy1640.2785 (4.53s)0.4011 (0.95s)0.4378 (14.74s)0.4273 (7.90s)
Adaptive greedy6410.2536 (3.27s)0.3786 (1.00s)0.4698 (17.16s)0.4902 (29.74s)
Adaptive greedy6440.2832 (3.30s)0.3945 (1.00s)0.4808 (17.40s)0.4845 (29.20s)
Greedy + scheduled1610.2596 (4.55s)0.3442 (0.95s)0.4142 (12.90s)0.4082 (8.11s)
Greedy + scheduled1640.2643 (4.48s)0.3940 (0.95s)0.4372 (14.55s)0.4119 (7.88s)
Greedy + scheduled6410.2401 (3.27s)0.3645 (0.99s)0.4603 (16.56s)0.4877 (28.83s)
Greedy + scheduled6440.2658 (3.25s)0.3687 (0.99s)0.4745 (17.26s)0.4639 (29.13s)

Entries are mean exact multicalibration error/TT (mean online prediction-and-update seconds) over three seeds, with each (n,s)(n,s) reported separately. The uniform errors also equal those of both development-selected baselines; uniform-column times refer only to ours. Timing excludes initialization, adversary work, and offline evaluation; runs shared machine load.

The revised paper also reports a single-seed experiment with 1,024 classes and 65,536 rounds: the tuned implementation took 15.6 seconds for prediction and updates, with normalized error 0.3155 versus 0.3862 for uniform prediction.

W2 / Q2. Dependencies of the lower bound. We use two results from Collina et al., and both are already stated and proved in their current public arXiv version (v2). We use Lemma 11 to construct the context groups and Theorem 4 to bound the noise in adaptive prediction bins. We do not use the forthcoming ambient-dimensional extension; Appendix D derives our multiclass lower bound from these two public results. The rest of our lower-bound proof is self-contained in Appendix D.

Q3. Sparse or incremental comparisons. Updates are incremental but not sparse: the learner updates every pair of available forecasts using the current round, without revisiting past observations. For a faster per-round solve, we could use the almost-linear-time algorithm of Cohen et al. (STOC 2017) to approximate the stationary distribution of our comparison chain.

The reviewer thanks the authors for their response. The reviewer has no further questions.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.