Optimal Multiclass U-Calibration Error and Beyond

We sincerely thank you for your comments and evaluation of the manuscript. Regarding the weakness in originality and significance, we would like to highlight that our Theorem 4, an $\Omega(\log T)$ lower bound for any algorithm when learning with the squared loss, is the most technical part of our manuscript and requires substantially new ideas. As we point out after Theorem 4, while squared loss is known to admit $\Theta(\log T)$ regret in other online learning problems such as that from Abernethy et al. (2008), as far as we know there is no study on our setting where the decision set is the simplex and the adversary has only finite choices. We believe that this result is particularly original and significant.

Your other questions are addressed below:

Major Questions:

Page 2 Line 42: isn't p from a continuum, how is a sum over p defined?

Note that even though $p$ is from a continuum, there are at most $T$ non-zero summands in this summation since there are at most $T$ different forecasts ($p_{t}$). This is why the notation $\sum_{p\in \Delta_K}$ is well defined and in fact standard in the calibration literature.

Page 5 Line 208: how is (a) claimed? Explain.

The exact reasoning can be found in Lines 474-481, but the intuitive explanation is simply that by the properness of the V-shaped loss, it is straightforward to see that predicting a uniform distribution at each time $t$ is in expectation the optimal choice for the learner in this environment (where the outcome is also uniform over $\{e_1, \ldots, e_K\}$), and this optimal strategy has exactly 0 loss.

Minor Questions:

Page 2 Line 39: what do you insert instead of dropped notations?

As we mention in Lines 38 and 39, whenever the subscript is dropped, both UCal and PUCal are to be thought of with respect to the class of all proper losses, for which we use the notation $\mathcal{L}$. Whenever a different subscript $\mathcal{L}’$ appears, both quantities are defined with respect to that specific class of losses, which would be clear from the context.

Page 8 Line 322: why $2K$?

At every time when a new label is chosen by the adversary, we bound the regret trivially by $2$ since $\ell$ is bounded in $[-1, 1]$. Since the number of distinct labels is $K$, this contributes at most $2K$ to the overall regret.

Suggestions: Thank you for the suggestions. We shall do the needful in the subsequent revisions.

We sincerely thank you for your comments and evaluation of the manuscript.

We sincerely thank you for your comments and evaluation of the manuscript. About your comment on the technical perspective, we would like to highlight a result that seems to be overlooked by the reviewer (since it is not mentioned in the summary of the review): our Theorem 4, an $\Omega(\log T)$ lower bound for any algorithm when learning with the squared loss, is the most technical part of our manuscript and requires substantially new ideas. As we point out after Theorem 4, while squared loss is known to admit $\Theta(\log T)$ regret in other online learning problems such as that from Abernethy et al. (2008), as far as we know there is no study on our setting where the decision set is the simplex and the adversary has only finite choices. We believe that this result is particularly original and significant.

We sincerely thank you for your comments and evaluation of the manuscript. Your questions are addressed below:

L25: Based on the regret definition, it seems the it can be negative because the best prediction in hindsight is fixed for all time steps? For example, an oracle $p = \text{arg}\min_p\sum_{t = 1} ^ {T} \ell(p, y_{t})$ achieves 0 regret, and an oracle $p_{t} = y_{t}$ for all $t$ has negative regret.

Yes, you are correct. The regret can potentially be negative (which is true for most online learning problems), but that only happens when the adversary is very weak.

L124: is the condition "if and only if"? See the interpretation immediately after Theorem 2 Gneiting and Raftery (2007): "Phrased slightly differently, a regular scoring rule $S$ is proper if and only if the expected score function $G(p) = S(p,p)$ is convex on $\mathcal{P}_m$".

That’s right. The condition is “if and only if”. Although line 124 conveys one direction, the subsequent lines (125, 126) combined with 124 convey the “if and only if” part.

In Section 3.1, would it be nice to accompany the algorithm description and theoretical guarantees by some intuition why this randomized algorithm works? For readers not familiar with FTPL, a naive forecast would be to just predict the class frequency $\beta$ up to the current time step. Why is it worse than FTPL and what is the intuition behind the randomization in the algorithm?

The naive forecast you mentioned is exactly FTL, which we show suffers linear regret for a certain V-shaped loss in Theorem 6. From its proof, one can see that the intuition is that FTL is unstable in the sense that $\ell(p_t, y_t) - \ell(p_{t+1}, y_t)$ can be as bad as $\Omega(1)$. On the other hand, by introducing randomness, FTPL stabilizes the algorithm and avoids this issue.

In Section 3.1, is it better to use the notation system established in previous sections to translate the FTPL algorithm in Daskalakis and Syrgkanis (2016)? For example, I think both are fine, just curious which one is more accepted.

We are not sure what you meant, unfortunately. We have indeed followed the approach of introducing the FTPL algorithm in Daskalaskis and Syrgkanis (2016) using their notations and then mapping the notations to our context. Please let us know what is the other usage of notation that you want to compare this to.

L181: dose -> does

Thank you for pointing out the typo. We shall correct this in the subsequent revisions.