We sincerely thank the reviewer for their positive evaluation of our work. We shall carefully incorporate your writing suggestions in the subsequent revisions.

We sincerely thank the reviewer for their positive comments and time in evaluating our paper. We shall carefully incorporate your writing suggestions in the subsequent revisions. Below, we provide responses to all your questions.

The paper focuses on binary outcomes; is there any hope to extend the concept of KL Calibration to multiclass outcomes?

It is not immediately trivial to extend the concept of KL-Calibration to multiclass outcomes, as we are not familiar with a generalization of the non-uniform discretization to the multiclass setting that still ensures desirable properties. Even more, we are not familiar with an extension of the randomizing rounding procedure for the log loss (utilized to obtain an explicit algorithm for minimizing pseudo KL-Calibration) to the multiclass setting. Moreover, a reason we did not seriously consider the possibility of such an extension to the multiclass setting is that several implications of KL-Calibration towards minimizing swap regret do not necessarily hold. In particular, in the binary setting, the implication $\text{SReg}^\ell = \mathcal{O}(\text{KCal})$ for each $\ell \in \mathcal{L}_2 \cup \mathcal{L}_G$ is derived via Lemma 2, which states that for a proper loss $\ell$, we have \text{BREG}(\hat{p}, p) =\int_p^\hat{p} |\ell''(\mu)| \cdot (\hat{p} - \mu) d\mu; the proof of the above result is based on a basis characterization of proper losses over binary outcomes in terms of V-shaped losses $\ell_v(p, y) = (v - y) \cdot \text{sign}(p - v)$ --- for each proper loss $\ell$, there exists a non-negative function (specific to $\ell$) $\mu: [0, 1] \to [0, 1]$ satisfying $\int_0 ^ 1 \mu(v) dv \le 2$ and $\ell (p, y) = \int_0^1 \mu(v) \ell_v (p, y) dv$ (ref. Theorem 8 in Kleinberg et al.). However, a similar characterization of proper losses is not known in the multiclass setting, and in fact cannot exist via the impossibility result in Theorem 20 in Kleinberg et al.

Kleinberg, B., Leme, R. P., Schneider, J., & Teng, Y. (2023, July). U-calibration: Forecasting for an unknown agent. In The Thirty Sixth Annual Conference on Learning Theory (pp. 5143-5145). PMLR.

An oblivious adversary is assumed, but it is claimed that the results generalize to an adaptive adversary. What needs to change in the analysis? Is it significantly more complicated, despite being technically possible?

The only result for which the analysis becomes simpler with an oblivious adversary is the high probability bound $\text{Cal}_2 \le 6 \text{PCal}_2 + 96 |\mathcal{Z}| \log \frac{4 |\mathcal{Z}|}{\delta}$ (Theorem 4 in Appendix E); we use Theorem 4 to derive a high probability bound on the classical $\ell_2$-Calibration ($\text{Cal}_2$). Extending the above result for an adaptive adversary is simple, but requires a more involved application of Freedman's inequality, which is outlined below. All other results in our paper apply as is for an adaptive adversary.

In more detail, Freedman's inequality states that for a martingale difference sequence $X_1, \dots, X_T$, where $|X_t| \le B$ for all $t \in [T]$, we have $|\sum_{t = 1} ^ {T} X_t| \le \mu V_X + \frac{1}{\mu} \log \frac{2}{\delta}$ with probability at least $1 - \delta$, where $V_X = \sum_{t = 1} ^ {T} \mathbb{E}_t[X_t ^ {2}]$, $\mu \in [0, \frac{1}{B}]$ is a fixed constant, and $\delta \in (0, 1)$. When $V_X$ is a deterministic quantity, the upper bound in the display above can be minimized with respect to $\mu \in [0, \frac{1}{B}]$; the optimal $\mu^\star = \min\left(\frac{1}{B}, \sqrt{\frac{\log \frac{2}{\delta}}{V_X}}\right)$. For the considered martingale difference sequences in Theorem 4 (e.g., one such sequence is $X_t \coloneqq y_t(\mathcal{P}_t(i) - \mathbb{I}[i_t = i]$), the corresponding $V_X$ is deterministic since the adversary is oblivious (note also that our algorithm outputs $\mathcal{P}_t$ in a deterministic manner). However, when $V_X$ is random (which is indeed the case in Lemma 9), we cannot merely substitute $\mu^\star$ in the bound above since $\mu^\star$ is random. To circumvent this difficulty, we can partition the feasible interval for $\mu$ geometrically (e.g., when $B = 2$, we partition to intervals of the form $[\frac{1}{2^{k + 1}}, \frac{1}{2^{k}}]$), apply Freedman's inequality within each interval, and subsequently take a union bound over all intervals. Notably, each interval corresponds to a condition on $V_X$ for which the optimal $\mu$ falls within that interval, and for that interval substituting $\mu = \frac{1}{2^{k}}$ or $\mu = \frac{1}{2^{k + 1}}$ leads to only a lower-order blow-up in the quantity $\mu V_X + \frac{1}{\mu} \log \frac{2}{\delta}$ compared to substituting $\mu^\star$.

We hope that our responses answer your questions. If you have any further questions, please don't hesitate to reach out.

We sincerely thank the reviewer for their positive evaluation of the paper. We shall incorporate your suggestions in the subsequent revisions of our paper.

I think having some additional discussion of the sorts of problems that give rise to losses covered by their new results would great improve my ability to contextualize the contribution. Log loss and squared error are familiar, but spherical error not as much, and understanding what we can get from generalizing prior results beyond psuedo $\ell_{2}$-calibration error to these other losses would be helpful.

We agree that the spherical loss $\ell(p, y) = -\frac{y p + (1 - y) (1 - p)}{\sqrt{p ^ {2} + (1 - p) ^ {2}}}$ is less familiar than the log loss and the squared loss. However, it has been previously studied in the literature to evaluate the quality of predictions made by a forecaster (ref. Gneiting and Raftery). Furthermore, the spherical loss has a nice geometric interpretation in terms of a cosine similarity (specifically, $\ell(p, y) = \cos(\pi - \theta)$, where $\theta$ is the angle between the vectors $[p, 1 - p]$ and $[y, 1 - y]$), therefore may be useful in problems where angular separation is meaningful. Similarly, other losses mentioned in our paper, e.g., losses induced by the Tsallis entropy have been previously studied in online learning and been used as regularizers in the classical Follow-the-Regularized Leader (FTRL) algorithm (ref. Abernethy et al.).

Gneiting, T. and Raftery, A. E. (2007). Strictly proper scoring rules, prediction, and estimation. Journal of the American statistical Association, 102(477):359–378.

Abernethy, J. D., Lee, C., & Tewari, A. (2015). Fighting bandits with a new kind of smoothness. Advances in Neural Information Processing Systems, 28.

I’d also be interested in seeing some discussion of lower bounds for pseudo swap regret (if there’s anything of note in the literature to discuss).

Regarding lower bounds, we would like to mention that the section on related work (line 109 onwards) does mention some lower bounds for $\text{Cal}_1, \text{Cal}_2$ (and thus swap regret of the squared loss). In summary, proving lower bounds for online calibration, swap regret is a significantly challenging problem and obtaining the minimax bound is still open, with recent breakthroughs establishing that $\tilde{\Omega}(T^{0.54389}) \le \mathbb{E}[\text{Cal}_1] \le \tilde{\mathcal{O}}(T^{\frac{2}{3} - \varepsilon})$ (for a sufficiently small $\varepsilon > 0$) and $\tilde{\Omega}(T^{0.08778}) \le \mathbb{E}[\text{Cal}_2] \le \tilde{\mathcal{O}}(T^{\frac{1}{3}})$ (Dagan et al., Fishelson et al.).

We hope that our responses answer your questions. If you have any further questions, please don't hesitate to reach out.

Thank you to the authors for their helpful rebuttal, I will maintain my score.

We sincerely thank the reviewer for their positive comments and time in evaluating our paper. In the subsequent revisions, we shall make sure to make the presentation of our paper more appealing to the general audience. Below, we answer the question that you raised in the weaknesses section.

I think another thing is that for readers that haven't read the Fishelson et al. (2025) paper to define pseudo-calibration more formally (specifically $\text{PCal}$) and give a more gentle explanation for what intuition one should walk in with about why relaxing to pseudo-notions of calibration allows for the $\sqrt{T}$ - $T^{1/3}$ gap (does the noise in realizing the forecasting's predictions in non-pseudo calibration cause one to naively pay some variance term of order $\sqrt{T}$? Why does such a variance term exist, especially if the forecaster only needs to randomized over two very close probabilities?).}

Great question. As you correctly figured out, the intuition behind the improved bound in $\text{PCal}_{2}$ is that by not taking into account the variance due to the randomness in the predictions, pseudo calibration is often easier to minimize.

For the other part of the question, the forecasting algorithm of Fishelson et al. or our Algorithm 3 (both of which achieve $\text{Cal}_2 = \tilde{\mathcal{O}}(T^{\frac{1}{3}})$) do not randomize over only two adjacent probabilities. Both the algorithms are based on the BM-reduction, which requires computing the stationary distribution of a matrix $Q_t$, i.e., $p_t \in \Delta(K + 1)$ such that $Q_t p_t = p_t$ (subsequently, the forecaster outputs conditional distribution $\mathcal{P}_t$ with $\mathcal{P}_t(z_i) = p_t(i)$); the columns of $Q_t$ correspond to the probability distributions output by the $K + 1$ external regret algorithms invoked by the BM-reduction. While each external regret algorithm outputs a probability distribution that is supported on two adjacent probabilities in the discretization ${\mathcal{Z}}$, the stationary distribution $p_t$ need not necessarily be so. As shown in Fishelson et al. (or our Theorem 2), the resulting algorithm achieves $\text{PCal}_2 = \tilde{\mathcal{O}}(T^{\frac{1}{3}})$. Accounting for the variance in the predictions naively would incur a $\sqrt{T}$ variance term. However, as we show in Appendix E (Theorem 4), by applying Freedman's inequality this variance term is of the order $\tilde{\mathcal{O}}(|\mathcal{Z}|)$; particularly, we show that $\text{Cal}_2 \le 6\text{PCal}_2 + 96 |\mathcal{Z}| \log \frac{4|\mathcal{Z}|}{\delta}$ with probability at least $1 - \delta$. Substituting $|\mathcal{Z}| = \tilde{\Theta}(T^{\frac{1}{3}})$, we obtain an improved $\tilde{\mathcal{O}}(T^{\frac{1}{3}})$ variance bound and $\text{Cal}_2 = \tilde{\mathcal{O}}(T^{\frac{1}{3}})$.

In summary, relaxing to pseudo calibration does enable achieving the $T^{\frac{1}{3}}$ rate, however, as we show this does not lead to a $\sqrt{T}-T^{\frac{1}{3}}$ ($\text{Cal}_2$ vs $\text{PCal}_2$) gap, since the variance term can be carefully controlled by a sophisticated analysis.

PS: In light of you mentioning randomization over two very close probabilities, that is certainly true for some calibration algorithms, e.g., the forecaster by Foster (1999), or the forecaster in the expository note by Roth (2022) (ref. Section 3.4 in Chapter 3). However, the former results in $\text{Cal}_1 = \tilde{\mathcal{O}}(T^{\frac{2}{3}})$ and the latter implies $\text{Cal}_2 = \tilde{\mathcal{O}}(\sqrt{T})$, both of which do not imply the desired ${T}^{\frac{1}{3}}$ bound for $\text{Cal}_2$.

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

Roth, A. (2022). Uncertain: Modern topics in uncertainty estimation. Unpublished Lecture Notes, 11, 30-31.

We hope that our response answers your questions. Should you have any more questions, do not hesitate to reach out.

We sincerely thank the reviewer for their positive evaluation of the paper. Below, we provide responses to all your questions.

I am a bit uncomfortable with the notation (e.g. in line 31 at page 1, but repeated several times afterwards), which looks like a sum over uncountably many elements. Is it really a standard notation from past work?

Yes, it is a standard notation from past work. The summation over $p \in [0, 1]$ is really just over the predictions $p_{1}, \dots, p_{T}$, since the interaction between the forecaster and the adversary lasts for $T$ rounds.

What's the total computational complexity of the algorithm proposed in Section 5, based on the BM reduction?

The cost of the algorithm proposed in Section 5 at every time step is at most $\mathcal{O}(K ^ {2} + \text{INT} + \text{ST})$, where $\text{ST}$ is the time required to compute the stationary distribution of $Q_{t}$ (ref. Algorithm 3 in Appendix D) and $\text{INT}$ denotes the computation required for evaluating the integral $\frac{\int_{0} ^ {1} w \mu_{t, i}(w) dw}{\int_{0} ^ {1} \mu_{t, i}(w) dw}$ in line 3 of Algorithm 4 (Appendix D); the $\mathcal{O}(K^{2})$ cost is incurred in forming the matrix $Q_{t}$, and all other operations in Algorithm 3 can be carried out in time that is no worse than $\mathcal{O}(K^{2})$. For $\text{ST}$, the stationary distribution of $Q_{t}$ can be computed by the method of power iteration; notably, each iteration shall incur cost $\mathcal{O}(\text{nnz}(Q_{t}))$, where $\text{nnz}(Q_{t})$ represents the number of non-zero entries in $Q_{t}$. Since each column of $Q_{t}$ has at most two non-zero entries (Algorithm 2 randomizes over two adjacent points in the discretization), $\text{nnz}(Q_{t}) = \Theta(K)$. For $\text{INT}$, the integral is over $[0, 1]$ and has a closed-form expression in terms of the gamma function $\Gamma(z) \coloneqq \int_{0} ^ {1} \exp(-t) t^{z - 1} dt$ as derived below. Recall that $f_{\tau, i}(w) = p_{\tau, i} \ell(w, y_{\tau}) = -p_{\tau, i} (y_{\tau} \log w + (1 - y_{\tau}) \log (1 - w)) = \log (w ^ {-y_{\tau} p_{\tau, i}} (1 - w) ^ {-p_{\tau, i} (1 - y_{\tau})}).$

Therefore, $\mu_{t, i}(w) = \exp\left(-\sum_{\tau = 1} ^ {t - 1} f_{\tau, i}(w)\right) = w^{\sum_{\tau = 1} ^ {t - 1} y_{\tau} p_{\tau, i}} (1 - w) ^ {\sum_{\tau = 1} ^ {t - 1} p_{\tau, i} (1 - y_{\tau})}$. For convenience, let $\gamma \coloneqq \sum_{\tau = 1} ^ {t - 1} y_{\tau} p_{\tau, i}, \delta \coloneqq \sum_{\tau = 1} ^ {t - 1} p_{\tau, i} (1 - y_{\tau})$. Then, $\int_{0} ^ {1} \mu_{t, i} (w) dw = \int_{0} ^ {1} w ^ {\gamma} (1 - w) ^ {\delta} dw = \text{B}(\gamma + 1, \delta + 1),$ where $\text{B}(z_{1}, z_{2})$ denotes the beta function, defined as $\text{B}(z_{1}, z_{2}) \coloneqq \int_{0} ^ {1} t ^ {z_{1} - 1} (1 - t) ^ {z_{2} - 1} dt$. Since $\text{B}(z_{1}, z_{2}) = \frac{\Gamma(z_{1}) \Gamma(z_{2})}{\Gamma(z_{1} + z_{2})}$ for all $z_{1}, z_{2} > 0$, we have $\int_{0} ^ {1} \mu_{t, i}(w) dw = \frac{\Gamma(\gamma + 1) \Gamma(\delta + 1)}{\Gamma(\gamma + \delta + 2)}.$ Similarly, $\int_{0} ^ {1} w \mu_{t, i}(w) dw = \int_{0} ^ {1} w ^ {\gamma + 1} (1 - w) ^ {\delta} dw = \text{B}(\gamma + 2, \delta + 1) = \frac{\Gamma(\gamma + 2) \Gamma(\delta + 1)}{\Gamma (\gamma + \delta + 3)}.$ Taking ratio of the two integrals above and using the identity $\Gamma(z + 1) = z \Gamma (z)$, which holds for all $z > 0$, we obtain $

\frac{\int_{0} ^ {1} w \mu_{t, i}(w) dw}{\int_{0} ^ {1} \mu_{t, i}(w) dw} = \frac{\Gamma (\gamma + 2)}{\Gamma (\gamma + 1)} \cdot \frac{\Gamma (\gamma + \delta + 2)}{\Gamma (\gamma + \delta + 3)} = \frac{\gamma + 1}{\gamma + \delta + 2} = \left(1 + \frac{\delta + 1}{\gamma + 1}\right) ^ {-1}.

$

Clearly, at each time $t$, both $\gamma$ and $\delta$ can be computed in $\mathcal{O}(1)$ time using the previously memorized values corresponding to time $t - 1$. Therefore, $\text{INT} = \mathcal{O}(1)$. Since $K = \tilde{\Theta}(T^{\frac{1}{3}})$, the overall computation cost over $T$ rounds is $\tilde{\mathcal{O}}(T^{\frac{5}{3}} + T \cdot \text{ST})$.

We thank the reviewer for the question and shall update our manuscript accordingly to incorporate the above discussion.

Your algorithm requires knowledge of the time horizon to select an appropriate discretization level. Is there a straightforward method (such as a doubling trick or similar approach) to avoid this requirement?

Yes, the doubling trick can be utilized to avoid this requirement. Since KL-Calibration is equivalent to swap regret of the log loss, we can use the doubling trick to avoid the requirement of knowing the time horizon $T$. The analysis of doubling trick for swap regret is exactly identical to that for external regret.

We hope that our responses answer your questions. If you have any further questions, please do not hesitate to reach out.