- 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
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.
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 T rounds with n classes is O(nT), without the learner being told that the mean is fixed.
Q3. How yt is generated. After observing the history, the current context xt, and the announced forecast distribution πt, nature may choose any conditional distribution for yt, but it cannot condition that distribution on the sampled forecast pt. The vector μ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 xt is generated. xt is the contextual information for round t. We make no assumption about how the contexts are generated: they may be deterministic or random. We only require that the learner observes xt before choosing its forecast distribution πt. For example, when predicting tomorrow's weather, xt might include the city and today's temperature.