r_{\mathcal{A}}(T,\mathcal{F}).$

Because the pinball loss with target quantile $q$ is
$q^{\prime}=\max(q,1-q)$-Lipschitz, we can round $\mathcal{A}$’s output to
$[\frac{1}{m}]$ and suffer at most an additional $\frac{q^{\prime}}{m}$ loss
from rounding. As before, we also choose a prediction from $[\frac{1}{m}]$ at
random with probability $1-\frac{1}{\sqrt{T}}$. In other words, this rounded
and randomized oracle, which we denote by $\tilde{\mathcal{A}}^{m}$ as before,
has an expected regret guarantee of
$r_{\mathcal{A}}(T,\mathcal{F})+\frac{q^{\prime}T}{m}+\sqrt{T}$.

Finally, similarly as in Section 3.1, we can borrow ideas from [7, 27] to
construct a conformal learner such that its contextual swap regret is bounded
with high probability against any
$\\{f_{p}\\}_{p\in\mathcal{P}_{\text{quantile}}}$ in terms of
$r_{\tilde{\mathcal{A}}^{m}}(T,\mathcal{F})$:

$\displaystyle\sum_{t=1}^{T}\mathop{\mathbb{E}}_{\hat{p}_{t}\sim\mathbf{\hat{p}}_{t}}\left[PB_{q}(p,s_{t})-PB_{q}(f_{\hat{p}_{t}}(x_{t}),s_{t})|\pi_{1:t-1}\right]$
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\leq\left(mr_{\mathcal{A}}\left(\frac{T}{m},\mathcal{F}\right)+\frac{q^{\prime}T}{m}+1\right)+\max(8B,2\sqrt{B})mC_{\mathcal{F}_{B}}\sqrt{\frac{\log(\frac{4m}{\rho})}{T}}.$

Here we simply observe that our algorithmic construction in Section 3.1 was
agnostic as to the form of the loss function, and so it carries over unchanged
when we replace squared loss with pinball loss.

The final piece to our argument is the connection between contextual swap
regret with respect to pinball loss and $L_{2}$-swap-quantile-multivalidity
error. Using similar ideas as in Lemma 3.4 and borrowing some ideas from [29],
we can show that if there exists $f\in\mathcal{F}$ and
$p\in\mathcal{P}_{\text{quantile}}$ such that $Q(\pi_{1:T},p,f)\geq\alpha$,
then there must exist $f^{\prime}\in\mathcal{F}$ such that

$\sum_{t\in S(\pi_{1:T},p)}PB_{q}(p,s_{t})-PB_{q}(f^{\prime}(p),s_{t})$

also scales linearly with $\alpha$.

While deferring the actual details to Appendix E, here we go over the overall
argument that shows their connection while highlighting the additional
arguments needed compared to Lemma 3.4.

We first need to argue that if the multivalidity error with respect to $f$ and
$p$ under the uniform distribution over realized (feature, conformal score)
pairs $\\{(x_{t},s_{t})\\}_{t=1}^{T}$ is big, then the multivalidity error
with respect to $\\{(x_{t},\mathbf{s}_{t})\\}_{t=1}^{T}$ must be big as well;
we can appeal to [3] to show this concentration over all $f\in\mathcal{F}$. By
taking the randomness over $s_{t}$ into account through $\mathbf{s}_{t}$, we
now have the conformal score distribution over
$\\{(x_{t},\mathbf{s}_{t})\\}_{t=1}^{T}$ is now continuous and smooth.

Now, we need to modify Lemma 3.1 of [29] — the lemma states that fixing the
multivalidity error with respect to some group function
$g:\mathcal{X}\to\\{0,1\\}$ and level set $p$ by swapping $p$ with $p+\eta$
for the points that belong to group $g$ and are given the prediction $p$
decreases the pinball loss over these points by an amount that depends on the
multivalidity error and the smoothness of the distribution.

We note that they choose $\eta$ such that $p+\eta$ is the exact $q$-quantile
for these points, which requires the conformal score distribution to be
continuous, and they show the decrease in pinball loss depends on the
smoothness of the distribution over the conformal score distribution. Both of
these issues of continuity and smoothness of the conformal distribution are
taken care of by dealing with the uniform distribution over
$\\{(x_{t},\mathbf{s}_{t})\\}_{t=1}^{T}$ as opposed to uniform distribution
over the realized (feature, conformal score) pairs
$\\{(x_{t},s_{t})\\}_{t=1}^{T}$.

Note that swapping above corresponds to predicting with $p+\eta\cdot g(x)$ for
the points who are given prediction $p$. However, their argument only works
for Boolean functions $g:\mathcal{X}\to\\{0,1\\}$, but we have soft-membership
determined by some $f:\mathcal{X}\to\mathbb{R}$ which simply reweights the
points according to $f(x_{t})$:

$\mathop{\mathbb{E}}_{s_{t}\sim\mathbf{s}_{t}\forall
t\in[T]}\left[\frac{1}{n(p)}\sum_{t\in S(p)}f(x_{t})\cdot\left(q-1[s_{t}\leq
p]\right)\right].$

Even under this re-weighting under $f$, it’s easy to see that there exists
some $b\in\mathbb{R}$ such that

$\displaystyle\mathop{\mathbb{E}}_{s_{t}\sim\mathbf{s}_{t}\forall
t\in[T]}\left[\frac{1}{n(p)}\sum_{t\in S(p)}f(x_{t})\cdot\left(q-1[s_{t}\leq
p+b\cdot f(x_{t})]\right)\right]$

is exactly 0 as the above value is monotonic in $b$. Swapping $p$ to $p+b\cdot
f(x)$ will decrease the pinball loss with respect to this $f$-reweighted
distribution over the points whose prediction was $p$ via the same argument as
in Lemma 3.1 of [29]. The actual argument presented in the appendix doesn’t
choose $b$ to set the quantile error to be exactly 0 so as to avoid having $b$
be too big as in Lemma 3.4.

By our assumption that $\mathcal{F}$ is closed under affine transformation, we
have $p+b\cdot f\in\mathcal{F}$. Therefore, if the multivalidity error under
uniform distribution over $\\{(x_{t},\mathbf{s}_{t})\\}_{t=1}^{T}$ with
respect to $f$ and $p$ is big, then $f^{\prime}=p+b\cdot f$ witnesses to the
fact that contextual swap regret under the same distribution must be big as
well. Finally, we can once again appeal to [3] to argue that contextual swap
regret under to the empirical distribution over
$\\{(x_{t},s_{t})\\}_{t=1}^{T}$ must be close to that under the uniform
distribution over $\\{x_{t},\mathbf{s}_{t}\\}_{t=1}^{T}$ to conclude that
contextual swap regret with respect to $\\{(x_{t},s_{t})\\}_{t=1}^{T}$ must be
big as well. This concludes the connection between multivalidity error with
respect to $f$ and $p$ and contextual swap regret for the pinball loss.

##  7 Discussion and Conclusion

We have given the first oracle efficient algorithms for online
multicalibration, online omniprediction, and online multivalid conformal
prediction. Our algorithms do not, however, obtain the rates that we would
ideally like: $O(T^{-1/2})$. Are these rates obtainable in an oracle efficient
way? We leave this as our main open question.

Achieving these rates seemingly requires new techniques: our current
techniques give algorithms that obtain the stronger guarantee of _swap_
-omniprediction for which we have proven that obtaining an $O(T^{-1/2})$ rate
is impossible. On the other hand, at least for finite binary benchmark
classes, we have shown that using different techniques, $O(T^{-1/2})$ rates
are obtainable for (vanilla) omniprediction — so the lower bound is not
inherent to the goal of omniprediction; but the techniques we use to obtain
these stronger omniprediction bounds seem to require enumerating over the
benchmark class $\mathcal{F}$, and it is not clear how one would implement
this same algorithm by reducing to solving an (online) learning problem over
$\mathcal{F}$.

##  8 Acknowledgements

We thank Jon Schneider for helpful discussions and pointing us to [32].

## References

  * AKCV [12] Dmitry Adamskiy, Wouter M Koolen, Alexey Chernov, and Vladimir Vovk.  A closer look at adaptive regret.  In International Conference on Algorithmic Learning Theory, pages 290–304. Springer, 2012.
  * AW [01] Katy S Azoury and Manfred K Warmuth.  Relative loss bounds for on-line density estimation with the exponential family of distributions.  Machine learning, 43:211–246, 2001.
  * BDR [21] Adam Block, Yuval Dagan, and Alexander Rakhlin.  Majorizing measures, sequential complexities, and online learning.  In Conference on Learning Theory, pages 587–590. PMLR, 2021.
  * BGJ+ [22] Osbert Bastani, Varun Gupta, Christopher Jung, Georgy Noarov, Ramya Ramalingam, and Aaron Roth.  Practical adversarial multivalid conformal prediction.  In Neural Information Processing Systems (NeurIPS), 2022.
  * BL [20] Avrim Blum and Thodoris Lykouris.  Advancing subgroup fairness via sleeping experts.  In Innovations in Theoretical Computer Science Conference (ITCS), volume 11, 2020.
  * Blu [97] Avrim Blum.  Empirical support for winnow and weighted-majority algorithms: Results on a calendar scheduling domain.  Machine Learning, 26(1):5–23, 1997.
  * BM [07] Avrim Blum and Yishay Mansour.  From external to internal regret.  Journal of Machine Learning Research, 8(6), 2007.
  * Daw [85] A Philip Dawid.  Calibration-based empirical probability.  The Annals of Statistics, 13(4):1251–1274, 1985.
  * DHL+ [20] Miroslav Dudík, Nika Haghtalab, Haipeng Luo, Robert E Schapire, Vasilis Syrgkanis, and Jennifer Wortman Vaughan.  Oracle-efficient online learning and auction design.  Journal of the ACM (JACM), 67(5):1–57, 2020.
  * FAD+ [18] Dylan Foster, Alekh Agarwal, Miroslav Dudík, Haipeng Luo, and Robert Schapire.  Practical contextual bandits with regression oracles.  In International Conference on Machine Learning, pages 1539–1548. PMLR, 2018.
  * FK [06] Dean P Foster and Sham M Kakade.  Calibration via regression.  In 2006 IEEE Information Theory Workshop-ITW’06 Punta del Este, pages 82–86. IEEE, 2006.
  * Fos [91] Dean P Foster.  Prediction in the worst case.  The Annals of Statistics, pages 1084–1090, 1991.
  * FR [20] Dylan Foster and Alexander Rakhlin.  Beyond ucb: Optimal and efficient contextual bandits with regression oracles.  In International Conference on Machine Learning, pages 3199–3210. PMLR, 2020.
  * FSSW [97] Yoav Freund, Robert E Schapire, Yoram Singer, and Manfred K Warmuth.  Using and combining predictors that specialize.  In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pages 334–343, 1997.
  * FV [98] Dean P Foster and Rakesh V Vohra.  Asymptotic calibration.  Biometrika, 85(2):379–390, 1998.
  * FV [99] Dean P Foster and Rakesh Vohra.  Regret in the on-line decision problem.  Games and Economic Behavior, 29(1-2):7–35, 1999.
  * FV [09] Lance Fortnow and Rakesh V Vohra.  The complexity of forecast testing.  Econometrica, 77(1):93–105, 2009.
  * GHHK+ [23] Ira Globus-Harris, Declan Harrison, Michael Kearns, Aaron Roth, and Jessica Sorrell.  Multicalibration as boosting for regression.  arXiv preprint arXiv:2301.13767, 2023.
  * GHK+ [23] Parikshit Gopalan, Lunjia Hu, Michael P. Kim, Omer Reingold, and Udi Wieder.  Loss minimization through the lens of outcome indistinguishability.  In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, USA, volume 251 of LIPIcs, pages 60:1–60:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.
  * GJ [03] Amy Greenwald and Amir Jafari.  A general class of no-regret learning algorithms and game-theoretic equilibria.  In Learning theory and kernel machines, pages 2–12. Springer, 2003\.
  * GJN+ [22] Varun Gupta, Christopher Jung, Georgy Noarov, Mallesh M. Pai, and Aaron Roth.  Online multivalid learning: Means, moments, and prediction intervals.  In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 2022, Berkeley, CA, USA, volume 215 of LIPIcs, pages 82:1–82:24. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
  * GKR+ [22] Parikshit Gopalan, Adam Tauman Kalai, Omer Reingold, Vatsal Sharan, and Udi Wieder.  Omnipredictors.  In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 2022, Berkeley, CA, USA, volume 215 of LIPIcs, pages 79:1–79:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
  * GKR [23] Parikshit Gopalan, Michael P Kim, and Omer Reingold.  Characterizing notions of omniprediction via multicalibration.  arXiv preprint arXiv:2302.06726, 2023.
  * HJKRR [18] Ursula Hébert-Johnson, Michael Kim, Omer Reingold, and Guy Rothblum.  Multicalibration: Calibration for the (computationally-identifiable) masses.  In International Conference on Machine Learning, pages 1939–1948. PMLR, 2018.
  * HK [16] Elad Hazan and Tomer Koren.  The computational power of optimization in online learning.  In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 128–141, 2016.
  * HS [09] Elad Hazan and Comandur Seshadhri.  Efficient learning algorithms for changing environments.  In Proceedings of the 26th Annual International Conference on Machine Learning, pages 393–400, 2009.
  * Ito [20] Shinji Ito.  A tight lower bound and efficient reduction for swap regret.  Advances in Neural Information Processing Systems, 33:18550–18559, 2020.
  * JLP+ [21] Christopher Jung, Changhwa Lee, Mallesh Pai, Aaron Roth, and Rakesh Vohra.  Moment multicalibration for uncertainty estimation.  In Conference on Learning Theory, pages 2634–2678. PMLR, 2021.
  * JNRR [23] Christopher Jung, Georgy Noarov, Ramya Ramalingam, and Aaron Roth.  Batch multivalid conformal prediction.  In International Conference on Learning Representations (ICLR), 2023\.
  * KGZ [19] Michael P Kim, Amirata Ghorbani, and James Zou.  Multiaccuracy: Black-box post-processing for fairness in classification.  In Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society, pages 247–254, 2019.
  * KKG+ [22] Michael P Kim, Christoph Kern, Shafi Goldwasser, Frauke Kreuter, and Omer Reingold.  Universal adaptability: Target-independent inference that competes with propensity scoring.  Proceedings of the National Academy of Sciences, 119(4):e2108097119, 2022.
  * KLST [23] Robert Kleinberg, Renato Paes Leme, Jon Schneider, and Yifeng Teng.  U-calibration: Forecasting for an unknown agent.  arXiv preprint arXiv:2307.00168, 2023.
  * KNMS [10] Robert Kleinberg, Alexandru Niculescu-Mizil, and Yogeshwer Sharma.  Regret bounds for sleeping experts and bandits.  Machine Learning, 80(2):245–272, 2010.
  * LNPR [22] Daniel Lee, Georgy Noarov, Mallesh Pai, and Aaron Roth.  Online minimax multiobjective optimization: Multicalibeating and other applications.  Advances in Neural Information Processing Systems, 35:29051–29063, 2022.
  * LP [17] David A Levin and Yuval Peres.  Markov chains and mixing times, volume 107.  American Mathematical Soc., 2017.
  * NR [23] Georgy Noarov and Aaron Roth.  The scope of multicalibration: Characterizing multicalibration via property elicitation.  arXiv preprint arXiv:2302.08507, 2023.
  * Ols [15] Wojciech Olszewski.  Calibration and expert testing.  In Handbook of Game Theory with Economic Applications, volume 4, pages 949–984. Elsevier, 2015.
  * QV [21] Mingda Qiao and Gregory Valiant.  Stronger calibration lower bounds via sidestepping.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 456–466, 2021.
  * Rot [22] Aaron Roth.  Uncertain: Modern topics in uncertainty estimation.  https://www.cis.upenn.edu/ aaroth/uncertainty-notes.pdf, 2022.
  * RST [15] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari.  Online learning via sequential complexities.  J. Mach. Learn. Res., 16(1):155–186, 2015.
  * RY [21] Guy N Rothblum and Gal Yona.  Multi-group agnostic pac learnability.  arXiv preprint arXiv:2105.09989, 2021.
  * San [03] Alvaro Sandroni.  The reproducible properties of correct forecasts.  International Journal of Game Theory, 32(1), 2003.
  * SKS [16] Vasilis Syrgkanis, Akshay Krishnamurthy, and Robert Schapire.  Efficient algorithms for adversarial contextual learning.  In International Conference on Machine Learning, pages 2159–2168. PMLR, 2016.
  * SSV [03] Alvaro Sandroni, Rann Smorodinsky, and Rakesh V Vohra.  Calibration with many checking rules.  Mathematics of operations Research, 28(1):141–153, 2003.
  * Vov [01] Volodya Vovk.  Competitive on-line statistics.  International Statistical Review, 69(2):213–248, 2001.
  * Zin [03] Martin Zinkevich.  Online convex programming and generalized infinitesimal gradient ascent.  In Proceedings of the 20th international conference on machine learning (icml-03), pages 928–936, 2003.

##  Appendix A Missing Details from Section 2

See 2.1

###### Proof.

This results follows directly from Cauchy-Schwartz inequality:
$\mathop{\mathbb{E}}[XY]^{2}\leq\mathop{\mathbb{E}}[X^{2}]\mathop{\mathbb{E}}[Y^{2}]$.
For any $\\{f_{p}\\}_{p\in\mathcal{P}}$,

$\displaystyle\left(\sum_{p\in\mathcal{P}}\frac{n(\pi_{1:T},p)}{T}\cdot
1\cdot\left|K(\pi_{1:T},p,f_{p})\right|\right)^{2}$
$\displaystyle\leq\sum_{p\in\mathcal{P}}\left(\frac{n(\pi_{1:T},p)}{T}\cdot
1^{2}\right)\left(\sum_{p\in\mathcal{P}}\frac{n(\pi_{1:T},p)}{T}\left|K(\pi_{1:T},p,f_{p})\right|^{2}\right)$
$\displaystyle\leq\overline{sK}_{2}(\pi_{1:T},\mathcal{F}).$

The same argument can be used to show
$\overline{K}_{1}(\pi_{1:T},\mathcal{F})\leq\sqrt{\overline{K}_{2}(\pi_{1:T},\mathcal{F})}$.
∎

##  Appendix B Missing Details from Section 3

See 3.1

###### Proof.

For any $y,y^{\prime}\in[0,1]$ and $m\geq 1$, we have

$\displaystyle\left(\text{Round}\left(y^{\prime},\frac{1}{m}\right)-y\right)^{2}-(y^{\prime}-y)^{2}$
$\displaystyle\leq\left(\left|y-y^{\prime}\right|+\frac{1}{m}\right)^{2}-|y-y^{\prime}|^{2}$
$\displaystyle=\left|\frac{2|y-y^{\prime}|}{m}+\frac{1}{m^{2}}\right|$
$\displaystyle\leq\frac{3}{m}.$

We can then show that for any sequence $\\{(x_{t},y_{t})\\}_{t=1}^{T}$ that is
chosen adversarially and adaptively against $\mathcal{A}^{m}$,

$\displaystyle\text{regret}\left(\\{(x_{t},y_{t},\hat{y}_{t})\\}_{t=1}^{T},f\right)$
$\displaystyle=\sum_{t=1}^{T}\left(\hat{y}_{t}-y_{t}\right)^{2}-\sum_{t=1}^{T}(f(x_{t})-y_{t})^{2}$
$\displaystyle=\sum_{t=1}^{T}\left(\text{Round}\left(\mathcal{A}(\\{x_{\tau},y_{\tau}\\}_{\tau=1}^{t-1},x_{t}),\frac{1}{m}\right)-y_{t}\right)^{2}-\sum_{t=1}^{T}(f(x_{t})-y_{t})^{2}$
$\displaystyle\leq\sum_{t=1}^{T}(\text{Project}_{[0,1]}(\mathcal{A}(\\{x_{\tau},y_{\tau}\\}_{\tau=1}^{t-1},x_{t}))-y_{t})^{2}+\frac{3}{m}-(f(x_{t})-y_{t})^{2}$
$\displaystyle\leq\sum_{t=1}^{T}(\mathcal{A}(\\{x_{\tau},y_{\tau}\\}_{\tau=1}^{t-1},x_{t})-y_{t})^{2}+\frac{3}{m}-(f(x_{t})-y_{t})^{2}$
$\displaystyle\leq r_{\mathcal{A}}(T)+\frac{3T}{m}.$

∎

See 3.2

###### Proof.

Fix any $f\in\mathcal{F}$. For convenience, write
$s_{t}=\\{(x_{\tau},y_{\tau})\\}_{\tau=1}^{t-1}$

$\displaystyle\sum_{t=1}^{T}\mathop{\mathbb{E}}_{\hat{y}^{\prime}_{t}\sim\tilde{\mathcal{A}}^{m}(s_{t},x_{t})}[(y^{\prime}_{t}-\hat{y}_{t})-(y^{\prime}_{t}-f(x_{t}))^{2}|\pi_{1:t-1}]$
$\displaystyle\leq\sum_{t=1}^{T}\Pr[\tilde{\mathcal{A}}^{m}(s_{t},x_{t})=\mathcal{A}^{m}(s_{t},x_{t})|\pi_{1:t-1}]\cdot\left((\tilde{\mathcal{A}}^{m}(s_{t},x_{t})-y_{t})^{2}-(y_{t}-f(x_{t}))^{2}\right)$
$\displaystyle\;\;\;\;\;\;+\Pr[\tilde{\mathcal{A}}^{m}(s_{t},x_{t})\neq\mathcal{A}^{m}(s_{t},x_{t})|\pi_{1:t-1}]$
$\displaystyle\leq\sum_{t=1}^{T}(\tilde{\mathcal{A}}^{m}(s_{t},x_{t})-y_{t})^{2}-(y_{t}-f(x_{t}))^{2}+\frac{1}{T}$
$\displaystyle\leq\text{regret}_{\mathcal{A}}(T,\mathcal{F})+\frac{3T}{m}+1.$

where the last inequality comes from Lemma 3.1. ∎

##  Appendix C Missing Details from Section 4

See 4.1

###### Proof.

Fix $\pi_{1:T}$, $y\in\mathcal{Y}$, and $\\{f_{p}\\}_{p\in\mathcal{P}}$. We
can show that

$\displaystyle\sum_{p\in\mathcal{P}}\frac{n(p)}{T}\left|\frac{1}{n(p)}\sum_{t\in
S(p)}f_{p}(x_{t})y_{t}-\left(\frac{1}{n(p)}\sum_{t\in
S(p)}y_{t}\right)\left(\frac{1}{n(p)}\sum_{t\in
S(p)}f_{p}(x_{t})\right)\right|$
$\displaystyle\leq\sum_{p\in\mathcal{P}}\frac{n(p)}{T}\left(\left|\frac{1}{n(p)}\sum_{t\in
S(p)}f_{p}(x_{t})y_{t}-\left(\frac{1}{n(p)}\sum_{t\in
S(p)}f_{p}(x_{t})p\right)\right|+\left|p-\frac{\sum_{t\in
S(p)}y_{t}}{n(p)}\right|\right)$
$\displaystyle=\sum_{p\in\mathcal{P}}\frac{n(p)}{T}\left|\frac{\sum_{t\in
S(p)}f_{p}(x_{t})(y_{t}-\hat{p}_{t})}{n(p)}\right|+\sum_{p\in\mathcal{P}}\frac{n(p)}{T}\left|p-\frac{\sum_{t\in
S(p)}y_{t}}{n(p)}\right|$ $\displaystyle\leq 2\alpha$

where the last inequality follows from
$\overline{sK}_{1}(\pi_{1:T},\mathcal{F})\leq\alpha$ and Assumption 2.1.

Note that for any $p\in\mathcal{P}$

$\displaystyle\left|\frac{1}{n(p)}\sum_{t\in
S(p)}f_{p}(x_{t})y_{t}-\left(\frac{1}{n(p)}\sum_{t\in
S(p)}y_{t}\right)\left(\frac{1}{n(p)}\sum_{t\in
S(p)}f_{p}(x_{t})\right)\right|$
$\displaystyle=\left|\frac{|S(p,1)|}{n(p)}\left(\frac{1}{|S(p,1)|}\sum_{t\in
S(p,1)}f_{p}(x_{t})-\frac{1}{n(p)}\sum_{t\in S(p)}f_{p}(x_{t})\right)\right|$
$\displaystyle=\left|\frac{|S(p,0)|}{n(p)}\left(\frac{1}{|S(p,0)|}\sum_{t\in
S(p,0)}f_{p}(x_{t})-\frac{1}{n(p)}\sum_{t\in S(p)}f_{p}(x_{t})\right)\right|$

where the second equality follows from
$\Pr[y=1](\mathop{\mathbb{E}}[z|y=1]-\mathop{\mathbb{E}}[z])=\Pr[y=0](\mathop{\mathbb{E}}[z]-\mathop{\mathbb{E}}[z|y=0])$.

In other words, we have

$\displaystyle\sum_{p\in\mathcal{P}}\frac{n(p)}{T}\left|\frac{|S(p,1)|}{n(p)}\left(\bar{f}_{p}(p,1)-\bar{f}_{p}(p)\right)\right|=\sum_{p\in\mathcal{P}}\frac{n(p)}{T}\left|\frac{|S(p,0)|}{n(p)}\left(\bar{f}_{p}(p,0)-\bar{f}_{p}(p)\right)\right|\leq
2\alpha.$

The same argument works for the non-swap version as well. ∎

See 4.2

###### Proof.

Fix $\pi_{1:T}$ and loss function $\ell$. For any post-processing function
$k:\mathcal{P}\to[0,1]$, we have

$\displaystyle\frac{1}{n(p)}\sum_{t\in S(p)}\ell(y_{t},k(p))$
$\displaystyle=\left(1-\frac{|S(p,1)|}{n(p)}\right)\ell(0,k(p))+\frac{|S(p,1)|}{n(p)}\ell(1,k(p))$
$\displaystyle=\left(1-\frac{\sum_{t\in
S(p)}y_{t}}{|S(p)|}\right)\ell(0,k(p))+\frac{\sum_{t\in
S(p)}y_{t}}{|S(p)|}\ell(1,k(p))$
$\displaystyle\geq\left(1-p\right)\ell(0,k(p))+p\ell(1,k(p))-|K(I,p)|\left|\ell(0,k(p))-\ell(1,k(p))\right|$

where the last inequality follows from

$\displaystyle\frac{1}{n(p)}\left|\sum_{t\in S(p)}y_{t}-p\right|=|K(I,p)|$

and that the image of loss function $\ell$ is a non-negative real number.

Recalling the definition of $k^{\ell}$, we have

$\displaystyle\frac{1}{n(p)}\sum_{t\in S(p)}\ell(y_{t},k(p))$
$\displaystyle\geq\left(1-p\right)\ell(0,k(p))+p\ell(1,k(p))-|K(I,p)|\left|\ell(0,k(p))-\ell(1,k(p))\right|$
$\displaystyle\geq\frac{1}{|S(p)|}\sum_{t\in
S(p)}\ell(y_{t},k^{\ell}(p))-|K(I,p)|\left|\ell(0,k(p))-\ell(1,k(p))\right|.$

∎

See 4.1

###### Proof.

Fix $\pi_{1:T}$, $\\{f_{p}\\}_{p\in\mathcal{P}}$ and
$\\{\ell_{p}\\}_{p\in\mathcal{P}}\in\mathcal{L}_{convex}^{m}$. For now, fix
$p\in\mathcal{P}$. Consider the following post-processing function:

$\hat{k}^{f_{p}}(p)=\bar{f}(p)=\frac{1}{n(p)}\sum_{t\in S(p)}f_{p}(x_{t}).$

Using the convexity of $\ell_{p}(y,\cdot)$ and Jensen’s inequality, we get

$\displaystyle\frac{1}{n(p)}\sum_{t\in
S(p)}\ell(y_{t},k^{\ell_{p}}(\hat{p}_{t}))-\frac{1}{n(p)}\sum_{t\in
S(p)}{\ell_{p}}(y_{t},f_{p}(x_{t}))$
$\displaystyle\leq\frac{1}{n(p)}\sum_{t\in
S(p)}{\ell_{p}}\left(y_{t},\hat{k}^{f_{p}}(p)\right)-\frac{1}{n(p)}\sum_{t\in
S(p)}\ell_{p}(y_{t},f_{p}(x_{t}))+C_{\ell_{p}}|K(I,p)|$ (Lemma 4.2)
$\displaystyle=C_{\ell_{p}}|K(I,p)|+\sum_{y\in\\{0,1\\}}\frac{|S(p,y)|}{n(p)}\left(\frac{1}{|S(p,y)|}\sum_{t\in
S(p):y_{t}=y}\ell_{p}(y,\hat{k}^{f_{p}}(p))-\ell_{p}(y,f_{p}(x_{t}))\right)$
$\displaystyle\leq
C_{\ell_{p}}|K(I,p)|+\sum_{y\in\\{0,1\\}}\frac{|S(p,y)|}{n(p)}\left(\ell_{p}(y,\hat{k}^{f_{p}}(p))-\ell_{p}\left(y,\frac{\sum_{t\in
S(p,y)}f_{p}(x_{t})}{|\\{t\in S(p):y_{t}=0\\}|}\right)\right)$ (Jensen’s
inequality) $\displaystyle\leq
C_{\ell_{p}}|K(I,p)|+D_{\ell_{p}}\sum_{y\in\\{0,1\\}}\frac{|S(p,y)|}{n(p)}\left(\bar{f}_{p}(p)-\bar{f}_{p}(p,y)\right)$
$\displaystyle\text{($D_{\ell_{p}}$-Lipschitzness of $\ell$)}.$

Averaging over each forecast $p\in\mathcal{P}$, we have the final result:

$\displaystyle\sum_{p\in\mathcal{P}}\frac{n(p)}{T}\left(\frac{1}{|S(p)|}\sum_{t\in
S(p)}\ell_{p}(y_{t},k_{\ell_{p}}(\hat{p}_{t}))-\frac{1}{n(p)}\sum_{t\in
S(p)}\ell_{p}(y_{t},f_{p}(x_{t}))\right)$
$\displaystyle\leq\sum_{p\in\mathcal{P}}\frac{n(p)}{T}\left(C_{\ell_{p}}|K(I,p)|+D_{\ell_{p}}\sum_{y\in\\{0,1\\}}\frac{|S(p,y)|}{n(p)}\left(\bar{f}_{p}(p)-\bar{f}_{p}(p,y)\right)\right)$
$\displaystyle\leq\left(\max_{p\in\mathcal{P}}C_{\ell_{p}}\right)\sum_{p\in\mathcal{P}}\frac{n(p)}{T}|K(I,p)|+\left(\max_{p\in\mathcal{P}}D_{\ell_{p}}\right)\sum_{y\in\\{0,1\\}}\sum_{p\in\mathcal{P}}\frac{|S(p,y)|}{T}\left(\bar{f}_{p}(p)-\bar{f}_{p}(p,y)\right)$
$\displaystyle\leq\left(\max_{p\in\mathcal{P}}C_{\ell_{p}}\right)\overline{sK}_{1}(I)+4\left(\max_{p\in\mathcal{P}}D_{\ell_{p}}\right)\overline{sK}_{1}(\\{f_{p}\\}_{p\in\mathcal{P}})$
$\displaystyle\leq\left(\max_{p\in\mathcal{P}}C_{\ell_{p}}+4D_{\ell_{p}}\right)\overline{sK}_{1}(\mathcal{F}).$

where the second to last inequality comes from Lemma 4.1.

The same argument works for the non-swap version as well. ∎

##  Appendix D Concentration Lemmas

As we need to borrow some tools from [3] and modify some of them, let us
quickly go through some notations. Given any set $\mathcal{Z}$, we write
$z\in\mathcal{Z}$ to denote its element and capital $Z$ to denote a complete
binary tree. Given a path $\epsilon=(\epsilon_{1},\dots,\epsilon_{n})\in\\{\pm
1\\}^{n}$ where $-1$ means ‘left’ and $+1$ ‘right’, we write $Z(\epsilon)$ to
denote the path along the tree $Z$ and $Z_{t}(\epsilon)$ or
$Z(\epsilon_{1},\dots,\epsilon_{t-1})$ to denote the $t$th element along the
path $Z(\epsilon)$ — note that $Z_{1}(\epsilon)$ is the root node that is the
same no matter which path $\epsilon$ is given. Given a function
$f:\mathcal{Z}\to\mathbb{R}$ and $\mathcal{Z}$-tree $Z$, we write $f(Z)$ to
refer to $\mathbb{R}$-valued tree induced by $Z$ and $f$.

######  Definition D.1 (Sequential Fat Shattering Dimension).

A tree $Z$ of depth $d$ is $\alpha$-shattered by a function class
$\mathcal{G}$ if there exists a tree $V$ such that

$\forall\ \epsilon\in\\{\pm 1\\}^{d},\exists g\in\mathcal{G}\quad\text{s.t.
}\epsilon_{t}(f(Z_{t}(\epsilon))-V_{t}(\epsilon))\geq\alpha/2.$

In words, given any path $\epsilon\in\\{\pm 1\\}$ along the tree $Z$, there
must exist some $f\in\mathcal{F}$ that matches the sign of the path in terms
of overestimating or underestimating the example
$Z_{t}(\epsilon)=Z(\epsilon_{1},\dots,\epsilon_{t-1})$.

Tree $V$ is a witness to $\alpha$-shattering. The sequential fat shattering
dimesnion $\text{fat}_{\alpha}(\mathcal{G},\mathcal{Z})$ at scale $\alpha$ for
the function class $\mathcal{G}$ is the largest $d$ such that $\mathcal{G}$
$\alpha$-shatters a $\mathcal{Z}$-valued tree of depth $d$.

######  Definition D.2 (Sequential Majorizing Measure [3]).

$I^{\alpha}_{\mathcal{G},Z}=\inf_{supp\ \mu\subseteq\mathcal{G}(Z)}\sup_{v\in
V,\epsilon\in\\{\pm
1\\}^{n}}\alpha+\frac{1}{\sqrt{n}}\int_{\alpha}^{1}\sqrt{\log\left(\frac{1}{\mu(B_{\delta}(V,\epsilon))}\right)}.$

where $B_{\delta}(V,\epsilon)$ is the set of all trees $V^{\prime}$ in the
support of measure $\mu$ such that

$||V^{\prime}(\epsilon)-V(\epsilon)||^{2}:=\sum_{t=1}^{n}(V^{\prime}_{t}(\epsilon)-V_{t}(\epsilon))^{2}\leq
n\delta.$

We write $I^{\alpha}_{\mathcal{G}}=\sup_{Z}I^{\alpha}_{\mathcal{G},Z}$.

Now, let us re-write the main tools that we will borrow from [3].

######  Lemma D.1 (Corollary 11 of [3]).

Let $z_{1},\dots,z_{t},\dots$ be a sequence of $\mathcal{Z}$-valued random
variables adapted to the filtration $\mathcal{A}_{t}$ and let $\mathcal{G}$ be
a $[0,1]$-valued function class on $\mathcal{Z}$. Then with probability at
least $1-4\rho$ over the randomness of $\\{\mathbf{s}_{t}\\}_{t\in n(p)}$,

$\displaystyle\sup_{g\in\mathcal{G}}\left|\frac{1}{n}\sum_{t=1}^{n}g(z_{t})-\mathop{\mathbb{E}}[g(z_{t})|\mathcal{A}_{t}]\right|$
$\displaystyle\leq
C_{1}\left(I^{\alpha}_{\mathcal{G}}+\sqrt{\frac{\log(\frac{1}{\rho})}{n}}\right)$
$\displaystyle\leq
C_{2}\cdot\left(\alpha+\frac{1}{\sqrt{n}}\int_{\alpha}^{1}\sqrt{\log(N^{\prime}(\mathcal{F},\delta))}d\delta+\sqrt{\frac{\log(\frac{1}{\rho})}{n}}\right)$

for any $\alpha\in(0,1)$, some universal constants $(C_{1},C_{2})$, and
$N^{\prime}(\mathcal{F},\delta)$ is a fractional covering number defined in
[3].

######  Theorem D.1 (Theorem 13 of [3]).

Let $\mathcal{G}:\mathcal{Z}\to[0,1]$ be a function class. There exists
universal constants $c,C_{3}$ such that for all $\delta>0$, and all trees $Z$

$N^{\prime}(\mathcal{G},\delta,Z)\leq\left(\frac{C_{3}}{\delta}\right)^{3\text{fat}_{c\delta}(\mathcal{G})}$

.

###  D.1 Mean Case

See 3.3 The proof for Lemma 3.3 is essentially identical to the proof for
Lemma 3.5, so we only present the proof for Lemma 3.5 below.

See 3.5

###### Proof.

Consider a sequence

$\mathbf{z}_{t}=(x_{t},y_{t},\mathbf{\hat{p}}_{t})$

adapted to the filtration $\pi_{1:t}$ for all $t\in[T]$. We write the domain
of $\mathbf{z}$ as
$\mathcal{Z}=\mathcal{X}\times\mathcal{Y}\times\mathcal{P}$. For each
$p\in\mathcal{P}$, define

$\mathcal{G}_{p}=\left\\{g((x,y,\hat{p}))=\frac{1}{2}\left(D_{1}f(x)+1\right):f\in\mathcal{F}_{B}\right\\}$

where $D_{1}=\min(1,\frac{1}{\sqrt{B}})$. Also, we define a post-processing
function

$d_{p}(v,\hat{p},y)=D_{2}\cdot\mathbbm{1}[\hat{p}=p]\cdot\left((p-y)^{2}-\left(\frac{1}{D_{1}}(2v-1)-y\right)^{2}\right)$

where $D_{2}=\max(\frac{D^{2}_{1}}{8},\frac{D_{1}}{2})$ and we assume
$v\in[0,1]$. Note that for any $g\in\mathcal{G}_{p}$ and
$z=(x,y,\hat{p})\in\mathcal{Z}$

$d_{p}(g(x),\hat{p},y)=D_{2}\cdot\mathbbm{1}[\hat{p}=p]\cdot\left((p-y)^{2}-(f(x)-y)^{2}\right)\in[0,1]$

and $d(v,\hat{p},y)$ is 1-Lipschitz in $v\in[0,1]$:

$\displaystyle|d_{p}(v,\hat{p},y)-d_{p}(v^{\prime},\hat{p},y)|$
$\displaystyle=\mathbbm{1}[\hat{p}=p]D_{2}\left|\left(\frac{1}{D_{1}}(2v-1)-y\right)^{2}-\left(\frac{1}{D_{1}}(2v^{\prime}-1)-y\right)^{2}\right|$
$\displaystyle=D_{2}\left|\left(\frac{4}{D^{2}_{1}}(v+v^{\prime})-\frac{2y}{D_{1}}\right)(v-v^{\prime})\right|$
$\displaystyle\leq
D_{2}\left|\left(\frac{8}{D^{2}_{1}}-\frac{2y}{D_{1}}\right)(v-v^{\prime})\right|$
$\displaystyle\leq|v-v^{\prime}|.$

Now, we can re-write the contextual swap regret’s deviation from its
expectation in each round as

$\displaystyle\frac{D_{2}}{T}\sup_{\\{f_{p}\\}_{p\in\mathcal{P}}}\sum_{t=1}^{T}(\hat{p}_{t}-y_{t})^{2}-(f_{\hat{p}_{t}}(x_{t})-y_{t})^{2}-\mathop{\mathbb{E}}_{\hat{p}^{\prime}_{t}}\left[(\hat{p}^{\prime}_{t}-y^{\prime}_{t})^{2}-(f_{\hat{p}^{\prime}_{t}}(x^{\prime}_{t})-y^{\prime}_{t})^{2}|\pi_{1:t-1}\right]$
$\displaystyle=\frac{D_{2}}{T}\sum_{p\in\mathcal{P}}\sup_{f_{p}\in\mathcal{F}_{B}}\sum_{t=1}^{T}\mathbbm{1}[\hat{p}_{t}=p]\left((\hat{p}-y)^{2}-(f_{p}(x)-y)^{2}\right)-\left((p-y)^{2}-(f_{p}(x)-y)^{2}\right)\Pr_{\hat{p}^{\prime}\sim\mathbf{\hat{p}}_{t}}[\hat{p}^{\prime}=p|\pi_{1:t-1}]$
$\displaystyle=\sum_{p\in\mathcal{P}}\sup_{g_{p}\in\mathcal{G}_{p}}\frac{1}{T}\sum_{t=1}^{T}d_{p}(g_{p}(x_{t}),\hat{p}_{t},y_{t})-\mathop{\mathbb{E}}_{\hat{p}^{\prime}\sim\mathbf{\hat{p}}_{t}}[d(g_{p}(x_{t}),\hat{p}_{t},y_{t})|\pi_{1:t-1}].$

In other words, it suffices to bound the deviation from its expectation for
every $p$.

######  Lemma D.2.

$I^{\alpha}_{d_{p}\circ\mathcal{G}_{p},Z}\leq
I^{\alpha}_{\mathcal{F}_{B},X^{Z}}.$

In other words, we have $I^{\alpha}_{d\circ\mathcal{G}_{p}}\leq
I^{\alpha}_{\mathcal{F}_{B}}$

###### Proof.

#### 1\. $I^{\alpha}_{d_{p}\circ\mathcal{G},Z}\leq
I^{\alpha}_{\mathcal{G},X^{Z}}$:

Fix any tree $Z$. Similarly to the proof of Lemma D.4, we write $X^{Z}$,
$Y^{Z}$, $P^{Z}$ to denote the $\mathcal{X}$, $\mathcal{Y}$, and
$\mathcal{P}$-trees induced by $Z$: for any $\epsilon\in\\{\pm 1\\}^{n}$ and
$\tau\in[n]$,
$Z_{\tau}(\epsilon)=(X^{Z}_{\tau}(\epsilon),Y^{Z}_{\tau}(\epsilon),P^{Z}_{\tau}(\epsilon))$.

Note that it is sufficient to show that for any measure $\mu$ over the
$\mathbb{R}$-trees whose support is over $g(X^{Z})$ for every
$g\in\mathcal{G}_{p}$, there exists a measure $\tilde{\mu}$ over
$\mathbb{R}$-trees such that the following is true: for every
$g\in\mathcal{G}_{p}$, we have

$\log\left(\frac{1}{\tilde{\mu}(B_{\delta}(d_{p}(g(X^{Z}),P^{Z},Y^{Z}),\epsilon))}\right)\leq\log\left(\frac{1}{\mu(B_{\delta}(g(X^{Z}),\epsilon))}\right).$

We can construct such $\tilde{\mu}$ over $\mathbb{R}$-valued trees via
pushforward operation with the following transformation function $Q$: given a
$\mathbb{R}$-valued-tree $R$, $Q$ outputs a new $\mathbb{R}$-valued tree
$R^{\prime}=Q(R)$ such that for every $\epsilon\in\\{\pm 1\\}^{n}$

$R^{\prime}(\epsilon):=d_{p}(R(\epsilon),P^{Z}(\epsilon),Y^{Z}(\epsilon))$

and $\tilde{\mu}=Q\\#\mu$ is the resulting pushforward measure via $Q$. Then,
because of the $1$-Lipschitzness of $d_{p}(\cdot,\hat{p},y)$, we have for any
tree $R$,

$\displaystyle||g(X^{Z}(\epsilon))-R(\epsilon)||\leq
n\delta^{2}\implies||d_{p}(g(X^{Z}(\epsilon)),P^{Z}(\epsilon),Y^{Z}(\epsilon))-R^{\prime}(\epsilon)||\leq
n\delta^{2}$

where $R^{\prime}=Q(R)$. Hence, we have

$\left\\{Q(R):R\in B_{\delta}(g(X^{Z}),\epsilon)\right\\}\subseteq
B_{\delta}(d(g(X^{Z}),P^{Z},Y^{Z}),\epsilon).$

Therefore, we can show that for any $\epsilon\in\\{\pm 1\\}^{n}$

$\mu(B_{\delta}(g(X^{Z}),\epsilon))=\tilde{\mu}(\left\\{Q(R):R\in
B_{\delta}(g(X^{Z}),\epsilon)\right\\})\leq\tilde{\mu}\left(B_{\delta}(d_{p}(g(X^{Z}),P^{Z},Y^{Z}),\epsilon)\right).$

#### 2\. $I^{\alpha}_{\mathcal{G}_{p},X}=I^{\alpha}_{\mathcal{F},X}$:

Note that $\mathcal{G}=h\circ\mathcal{F}_{B}$ where $h(v)=\frac{1}{2}(D\cdot
v+1)$, which is $1$-Lipschitz as $\frac{D}{2}\leq 1$. Therefore, by
Proposition 5 of [3], we have
$I^{\alpha}_{\mathcal{G}_{p},X}=I^{\alpha}_{\mathcal{F}_{B},X}$.

∎

Invoking Lemma D.1 gives us that with probability $1-4m$ over the randomness
of $\\{\hat{p}_{t}\\}_{t=1}^{T}$,

$\displaystyle\sup_{g_{p}\in\mathcal{G}_{p}}\sum_{t=1}^{T}d_{p}(g_{p}(x_{t}),\hat{p}_{t},y_{t})-\mathop{\mathbb{E}}_{\hat{p}^{\prime}\sim\mathbf{\hat{p}}_{t}}[d_{p}(g_{p}(x_{t}),\hat{p}_{t},y_{t})|\pi_{1:t-1}]$
$\displaystyle\leq
C_{1}\left(I^{\alpha}_{d_{p}\circ\mathcal{G}_{p}}+\sqrt{\frac{\log(\frac{1}{\rho})}{T}}\right)$
$\displaystyle\leq
C_{1}\left(I^{\alpha}_{\mathcal{F}_{B}}+\sqrt{\frac{\log(\frac{1}{\rho})}{T}}\right)$
$\displaystyle\leq
2C_{1}\cdot\left(\inf_{\alpha\in(0,1)}\alpha+\frac{1}{\sqrt{T}}\int_{\alpha}^{1}\sqrt{\log(N^{\prime}(\mathcal{F}_{B},\delta))}d\delta+\sqrt{\frac{\log(\frac{1}{\rho})}{T}}\right)$
$\displaystyle\leq
2C_{1}\cdot\left(\inf_{\alpha\in(0,1)}\alpha+\frac{1}{\sqrt{T}}\int_{\alpha}^{1}\sqrt{\log\left(\left(\frac{C_{3}}{\delta}\right)^{3\text{fat}_{c\delta}(\mathcal{F}_{B})}\right)}d\delta+\sqrt{\frac{\log(\frac{1}{\rho})}{T}}\right)$
$\displaystyle\leq
2C_{1}\cdot\left(\inf_{\alpha\in(0,1)}\alpha+\frac{1}{\sqrt{T}}\int_{\alpha}^{1}\sqrt{3\text{fat}_{c\delta}(\mathcal{F}_{B})\log\left(\left(\frac{C_{3}}{\delta}\right)\right)}d\delta+\sqrt{\frac{\log(\frac{1}{\rho})}{T}}\right)$
$\displaystyle\leq C_{\mathcal{F}_{B}}\sqrt{\frac{\log(\frac{1}{\rho})}{T}}$

for some finite constant $C_{\mathcal{F}_{B}}$ that depends on the complexity
of $\mathcal{F}_{B}$ via its fat shattering dimension. The third inequality
from Lemma D.2, and the fourth inequality follows from Theorem D.1, and the
very last inequality follows from plugging in $\alpha=\frac{1}{\sqrt{T}}$ and
noting that the sequential fat dimension of $\mathcal{F}_{B}$ is finite at any
scale $\delta>0$.

Summing over all $p\in\mathcal{P}$, we have with probability $1-4m\rho$,

$\displaystyle\frac{D_{2}}{T}\sup_{\\{f_{p}\\}_{p\in\mathcal{P}}}\sum_{t=1}^{T}(\hat{p}_{t}-y_{t})^{2}-(f_{\hat{p}_{t}}(x_{t})-y_{t})^{2}-\mathop{\mathbb{E}}_{\hat{p}^{\prime}_{t}}\left[(\hat{p}^{\prime}_{t}-y^{\prime}_{t})^{2}-(f_{\hat{p}^{\prime}_{t}}(x^{\prime}_{t})-y^{\prime}_{t})^{2}|\pi_{1:t-1}\right]$
$\displaystyle=\sum_{p\in\mathcal{P}}\sup_{g_{p}\in\mathcal{G}_{p}}\frac{1}{T}\sum_{t=1}^{T}d_{p}(g_{p}(x_{t}),\hat{p}_{t},y_{t})-\mathop{\mathbb{E}}_{\hat{p}^{\prime}\sim\mathbf{\hat{p}}_{t}}[d_{p}(g_{p}(x_{t}),\hat{p}_{t},y_{t})|\pi_{1:t-1}]$
$\displaystyle\leq mC_{\mathcal{F}_{B}}\sqrt{\frac{\log(\frac{1}{\rho})}{T}}$

∎

###  D.2 Quantile Case

######  Lemma D.3 (Concentration of Quantile Error).

Fix any $\tilde{\pi}_{1:T}$, $p\in\mathcal{P}_{\text{quantile}}$, and
$\mathcal{F}_{B}$. Suppose the sequential shattering dimension of
$\mathcal{F}_{B}$ is finite at any scale $\delta$:
$\text{fat}_{\delta}(\mathcal{F}_{B})<\infty$. With probability $1-4\rho$,

$\sup_{f\in\mathcal{F}_{B}}\left|\frac{1}{n(p)}\sum_{t\in
S(p)}f(x_{t})\mathbbm{1}[s_{t}\leq
p]-f(x_{t})\Pr_{s_{t}\sim\mathbf{s}_{t}}[s_{t}\leq
p]\right|\leq\max\left(1,\sqrt{B}\right)C_{\mathcal{F}_{B}}\sqrt{\frac{\log(\frac{1}{\rho})}{n(p)}}$

where $C_{\mathcal{F}_{B}}$ is some finite constant that depends on the
complexity of $\mathcal{F}_{B}$.

###### Proof.

For each round $\tau\in[n]$, define $\mathcal{Z}=[0,1]\times\mathcal{X}$ and
$D=\min(1,1/\sqrt{B})$. Now, for each $f\in\mathcal{F}_{B}$ and any
$z=(x,s)\in\mathcal{Z}$, define

$g_{f}(z)=\frac{1}{2}\left(D\cdot f(x)\cdot M_{p}(s)+1\right)$

where $M_{p}(s)=\mathbbm{1}[s\leq p]$. We denote the induced family of
functions $\mathcal{G}=\\{g_{f}:f\in\mathcal{F}_{B}\\}$. Note that
$\mathcal{G}\subseteq[0,1]^{\mathcal{Z}}$ as $D\cdot f(x)\leq[-1,1]$ for any
$f\in\mathcal{F}_{B}$.

######  Lemma D.4.

The fat shattering dimension of $\mathcal{G}$ matches that of
$\mathcal{F}_{B}$:

$\text{fat}_{\alpha}(\mathcal{G},\mathcal{Z})\leq\text{fat}_{\alpha^{\prime}}(\mathcal{F}_{B},\mathcal{X})$

where $\alpha^{\prime}=2\sqrt{B}\alpha$.

###### Proof.

For convenience, write
$\text{fat}_{\alpha}(\mathcal{F}_{\mathcal{A}},\mathcal{X})=d$ and
$\text{fat}_{\alpha}(\mathcal{G},\mathcal{Z})=d^{\prime}$. For the sake of
contradiction, suppose the fat shattering dimension of $\mathcal{G}$ is
strictly greater than $d$, meaning there exists a $\mathcal{Z}$-valued tree
$Z$ and $\mathbb{R}$-valued tree $R$ that witness to its fat shattering
dimension being $d^{\prime}>d$. We write $X^{Z}$ and $S^{Z}$ to denote the
$\mathcal{X}$-tree and $\mathbb{R}$-tree induced by $Z$: i.e.
$Z_{\tau}(\epsilon)=(X^{Z}_{\tau}(\epsilon),S^{Z}_{\tau}(\epsilon))$.

First, we argue that there must exist $\epsilon\in\\{\pm 1\\}^{d^{\prime}}$
and $\tau\in[d^{\prime}]$ such that

$M_{p}(S^{Z}_{\tau}(\epsilon))=0.$

If not, then we have for every $\epsilon\in\\{\pm 1\\}^{d^{\prime}}$

$g_{f}(Z_{\tau}(\epsilon))=\frac{1}{2}\left(Df(X^{Z}_{\tau}(\epsilon))+1\right).$

Then, we have a $\mathcal{X}$-tree $X^{Z}$ with depth $d^{\prime}$ and an
$\mathbb{R}$-tree $R^{\prime}$ where $R^{\prime}=1/D\cdot(2\cdot R^{Z}-1)$
which together serve as a witness for $\alpha^{\prime}$-shattering where
$\alpha^{\prime}=2\sqrt{B}\alpha$: for every $\epsilon\in\\{\pm
1\\}^{d^{\prime}}$ and $\tau\in[d^{\prime}]$,

$\epsilon_{\tau}\cdot(f(X_{\tau}^{Z}(\epsilon))-R^{\prime}_{\tau}(\epsilon))\geq\alpha^{\prime}/2:$

i.e. we would have
$\text{fat}_{\alpha^{\prime}}(\mathcal{F}_{B},\mathcal{X})=d^{\prime}>d$,
which leads to a contradiction that $d$ is the maximum depth for which
$\mathcal{F}_{B}$ is shattered at scale $\alpha^{\prime}$.

Hence, suppose there exists some $\tau^{*}\in[d^{\prime}]$ and
$(\epsilon_{1},\dots,\epsilon_{\tau^{*}-1})\in\\{\pm 1\\}^{\tau^{*}}$ such
that

$M_{p}(S^{Z}(\epsilon_{1},\dots,\epsilon_{\tau^{*}-1}))=0.$

Then, for any $g_{f}\in\mathcal{G}$, we have

$g_{f}(Z(\epsilon_{1},\dots,\epsilon_{\tau^{*}-1}))-R(\epsilon_{1},\dots,\epsilon_{\tau^{*}-1})=-R(\epsilon_{1},\dots,\epsilon_{\tau^{*}-1}).$

Hence, either there doesn’t exist any $g_{f}\in\mathcal{G}$ such that

$+1\left(g_{f}(Z(\epsilon_{1},\dots,\epsilon_{\tau^{*}-1}))-R(\epsilon_{1},\dots,\epsilon_{\tau^{*}-1})\right)=-R(\epsilon_{1},\dots,\epsilon_{\tau^{*}-1})\geq\alpha/2$

or there’s no $g_{f}\in\mathcal{G}$ such that

$-1\left(g_{f}(Z(\epsilon_{1},\dots,\epsilon_{\tau^{*}-1}))-R(\epsilon_{1},\dots,\epsilon_{\tau^{*}-1})\right)=R(\epsilon_{1},\dots,\epsilon_{\tau^{*}-1})\geq\alpha/2.$

This contradicts the assumption that $Z$ and $R$ is a witness to
$\alpha$-shattering for $\mathcal{G}$. This concludes the proof that
$d^{\prime}\leq d$. ∎

Now, fix $\tilde{\pi}_{1:T}$. And instead of iterating the entire time horizon
$[T]$, we only iterate over $S(\tilde{\pi}_{1:T},p)$. For convenience, we
overload the notation and define the new rounds
$\tau\in[n(\tilde{\pi}_{1:T},p)]$ such that the corresponding random variable
$z_{\tau}$ matches the $(x_{t},s_{t})$: define

$z_{\tau}=(s_{t_{\tau}},x_{t_{\tau}})$

where $t_{\tau}=S(\tilde{\pi}_{1:T},p)[\tau]$ — i.e. the round at which
prediction $p$ is made for the $\tau$-th time.

Invoking Lemma D.1 gives us that with probability $1-4\rho$ over the
randomness of $\\{\mathbf{s}_{t}\\}_{t\in S(\tilde{\pi}_{1:T},p)}$,

$\displaystyle D\cdot\sup_{f\in\mathcal{F}_{B}}\left|\frac{1}{n(p)}\sum_{t\in
S(p)}f(x_{t})\mathbbm{1}[s_{t}\leq
p]-f(x_{t})\Pr_{s_{t}\sim\mathbf{s}_{t}}[s_{t}\leq p]\right|$
$\displaystyle=2\sup_{g\in\mathcal{G}}\left|\frac{1}{n(p)}\sum_{\tau=1}^{n(p)}g_{f}(z_{\tau})-\mathop{\mathbb{E}}_{\tau-1}[g(z_{\tau})]\right|$
$\displaystyle\leq
2C_{1}\cdot\left(\inf_{\alpha\in(0,1)}\alpha+\frac{1}{\sqrt{n(p)}}\int_{\alpha}^{1}\sqrt{\log(N^{\prime}(\mathcal{G},\delta))}d\delta+\sqrt{\frac{\log(\frac{1}{\rho})}{n(p)}}\right)$
$\displaystyle\leq
2C_{1}\cdot\left(\inf_{\alpha\in(0,1)}\alpha+\frac{1}{\sqrt{n(p)}}\int_{\alpha}^{1}\sqrt{\log\left(\left(\frac{C_{3}}{\delta}\right)^{3\text{fat}_{c\delta}(\mathcal{G})}\right)}d\delta+\sqrt{\frac{\log(\frac{1}{\rho})}{n(p)}}\right)$
$\displaystyle\leq
2C_{1}\cdot\left(\inf_{\alpha\in(0,1)}\alpha+\frac{1}{\sqrt{n(p)}}\int_{\alpha}^{1}\sqrt{3\text{fat}_{2c\sqrt{B}\delta}(\mathcal{F}_{B})\log\left(\left(\frac{C_{3}}{\delta}\right)\right)}d\delta+\sqrt{\frac{\log(\frac{1}{\rho})}{n(p)}}\right)$
$\displaystyle\leq
C_{\mathcal{F}_{B}}\sqrt{\frac{\log(\frac{1}{\rho})}{n(p)}}$

for some finite constant $C_{\mathcal{F}_{B}}$ that depends on the complexity
of $\mathcal{F}_{B}$ via its fat shattering dimension. The second inequality
follows from Theorem D.1, the third inequality from Lemma D.4, and the fourth
inequality follows by plugging in $\alpha=\frac{1}{\sqrt{n(p)}}$ and noting
that the sequential fat dimension of $\mathcal{F}_{B}$ is finite at any scale
$\delta>0$. ∎

######  Lemma D.5 (Concentration of Pinball Loss).

Fix $\tilde{\pi}_{1:T}$, $p\in\mathcal{P}_{\text{quantile}}$, and
$\mathcal{F}_{B}$. Suppose the sequential shattering dimension of
$\mathcal{F}_{B}$ is finite at any scale $\delta$:
$\text{fat}_{\delta}(\mathcal{F}_{B})<\infty$. We have that with probability
$1-4\rho$ over the randomness of $\\{\mathbf{s}_{t}\\}_{t\in S(p)}$,

$\displaystyle\sup_{f\in\mathcal{F}_{B}}\left|\frac{1}{n(p)}\sum_{t\in
S(p)}PB_{q}(s_{t},p)-PB_{q}(s_{t},f(x_{t}))-\mathop{\mathbb{E}}_{s\sim\mathbf{s}_{t}}[PB_{q}(s,p)-PB_{q}(s,f(x_{t})]\right|\leq\max\left(1,\sqrt{B}\right)C^{\prime}_{\mathcal{F}_{B}}\sqrt{\frac{\log(\frac{1}{\rho})}{n(p)}}$

###### Proof.

We proceed with a similar argument as the proof of Proposition 5 of [3].
First, define $\mathcal{Z}=\mathcal{X}\times[0,1]$ and
$D=\min(1,\frac{1}{\sqrt{B}})$. In order to enforce the range of the function
values to be $[0,1]$, we define the function class

$\mathcal{G}=\left\\{g_{f}=\frac{1}{2}\left(D\cdot
f(\cdot)+1\right):f\in\mathcal{F}_{B}\right\\}.$

Define $d:[0,1]\times[0,1]\to[0,1]$ as

$d(s,v)=\frac{1}{2}\left(D\cdot\left(PB_{q}(s,p)-PB_{q}\left(s,\frac{2v-1}{D}\right)\right)+1\right).$

Note that $d(s,\cdot)$ is $1$-Lipschitz:

$\displaystyle|d(s,v)-d(s,v^{\prime})|$
$\displaystyle=\frac{D}{2}\left|PB_{q}\left(s,\frac{2v-1}{D}\right)-PB_{q}\left(s,\frac{2v^{\prime}-1}{D}\right)\right|$
$\displaystyle\leq\frac{D}{2}\left|\frac{2v-1}{D}-\frac{2v^{\prime}-1}{D}\right|$
$\displaystyle\leq|v-v^{\prime}|$

as $PB_{q}(s,\cdot)$ is $\max(q,1-q)$-Lipschitz and $\max(q,1-q)\leq 1$.

Also, note that $d(s,v)\in[0,1]$ and for any $g_{f}\in\mathcal{G}$,

$d(s,g_{f}(x))=\frac{1}{2}\left(D\cdot\left(PB_{q}\left(s,f(x)\right)-PB_{q}(s,p)\right)+1\right)$

where $f\in\mathcal{F}_{B}$ is such that $g_{f}(x)=\frac{1}{2}\left(D\cdot
f(x)+1\right)$.

Using the same argument as in Proposition 5 of [3], we can show the following
claim.

######  Lemma D.6.

For any tree $Z$,

$\displaystyle I^{\alpha}_{d\circ\mathcal{G},Z}\leq
I^{\alpha}_{\mathcal{G},X^{Z}}=I^{\alpha}_{\mathcal{F}_{B},X^{Z}}$

where $X^{Z}$ is the tree induced by the $Z$: i.e. for every
$\epsilon\in\\{\pm 1\\}^{n}$, $Z_{t}(\epsilon)=(X^{Z}_{t}(\epsilon),s_{t})$.
In other words, $I^{\alpha}_{d\circ\mathcal{G}}\leq
I^{\alpha}_{\mathcal{F}_{B}}$.

###### Proof.

#### 1\. $I^{\alpha}_{d\circ\mathcal{G},Z}\leq
I^{\alpha}_{\mathcal{G},X^{Z}}$:

Fix any tree $Z$. As in the proof of Lemma D.4, we write $X^{Z}$ and $S^{Z}$
to denote the $\mathcal{X}$ and $\mathbb{R}$-trees induced by $Z$: for any
$\epsilon\in\\{\pm 1\\}^{n}$ and $\tau\in[n]$,
$Z_{\tau}(\epsilon)=(S^{Z}_{\tau}(\epsilon),X^{Z}_{\tau}(\epsilon))$.

Note that it is sufficient to show that for any measure $\mu$ over the
$\mathbb{R}$-trees whose support is over $g_{f}(X^{Z})$ for every
$g_{f}\in\mathcal{G}$, there exists a measure $\tilde{\mu}$ over
$\mathbb{R}$-trees such that the following is true:

$\log\left(\frac{1}{\tilde{\mu}(B_{\delta}(d(S^{Z},g_{f}(Z)),\epsilon))}\right)\leq\log\left(\frac{1}{\mu(B_{\delta}(g_{f}(X^{Z}),\epsilon))}\right).$

We can construct such $\tilde{\mu}$ over $\mathbb{R}$-valued trees via
pushforward operation with the following transformation function $Q$: given a
$\mathbb{R}$-valued-tree $R$, $Q$ outputs a new $\mathbb{R}$-valued tree
$R^{\prime}=Q(R)$ such that for every $\epsilon\in\\{\pm 1\\}^{n}$

$R^{\prime}(\epsilon):=d(S^{Z}(\epsilon),R(\epsilon))$

and $\tilde{\mu}=Q\\#\mu$ is the resulting pushforward measure via $Q$. Then,
because of the $1$-Lipschitzness of $d(s,\cdot)$, we have for any tree $R$,

$\displaystyle||g_{f}(X^{Z}(\epsilon))-R(\epsilon)||\leq
n\delta^{2}\implies||d(S^{Z}(\epsilon),g_{f}(X^{Z}(\epsilon)))-R^{\prime}(\epsilon)||\leq
n\delta^{2}$

where $R^{\prime}=Q(R)$. Hence, we have

$\left\\{Q(R):R\in B_{\delta}(g_{f}(X^{Z}),\epsilon)\right\\}\subseteq
B_{\delta}(d(S^{Z},g_{f}(X^{Z})),\epsilon)$

Therefore, we can show that for any $\epsilon\in\\{\pm 1\\}^{n}$

$\mu(B_{\delta}(g_{f}(X^{Z}),\epsilon))=\tilde{\mu}(\left\\{Q(R):R\in
B_{\delta}(g_{f}(X^{Z}),\epsilon)\right\\})\leq\tilde{\mu}\left(B_{\delta}(d(S^{Z},g_{f}(X^{Z})),\epsilon)\right).$

#### 2\. $I^{\alpha}_{\mathcal{G},X}=I^{\alpha}_{\mathcal{F},X}$:

Note that $\mathcal{G}=h\circ\mathcal{F}_{B}$ where $h(v)=\frac{1}{2}(D\cdot
v+1)$, which is $1$-Lipschitz. Therefore, by Proposition 5 of [3], we have
$I^{\alpha}_{\mathcal{G},X}=I^{\alpha}_{\mathcal{F},X}$.

∎

Fix any $\tilde{\pi}_{1:T}$. Combining Lemma D.6 and Lemma D.1, we have with
probability $1-4\rho$ over the randomness of $\\{\mathbf{s}_{t}\\}_{t\in
n(p)}$,

$\displaystyle D\sup_{f\in\mathcal{F}_{B}}\left|\frac{1}{n(p)}\sum_{t\in
S(p)}PB_{q}(s_{t},p)-PB_{q}(s_{t},f(x_{t}))-\mathop{\mathbb{E}}_{s\sim\mathbf{s}_{t}}[PB_{q}(s,p)-PB_{q}(s,f(x_{t})]\right|$
$\displaystyle=2\sup_{g\in\mathcal{G}}\left|\frac{1}{n(p)}\sum_{t\in
S(p)}d(s_{t},g_{f}(x_{t}))-\mathop{\mathbb{E}}_{s_{t}\sim\mathbf{s}_{t}}[d(s_{t},g_{f}(x_{t}))|\pi_{1:t-1}]\right|$
$\displaystyle\leq
2C_{1}\left(I^{\alpha}_{d\circ\mathcal{G}}+\sqrt{\frac{\log(\frac{1}{\rho})}{n(p)}}\right)$
$\displaystyle\leq
2C_{1}\left(I^{\alpha}_{\mathcal{F}_{B}}+\sqrt{\frac{\log(\frac{1}{\rho})}{n(p)}}\right)$
$\displaystyle\leq
2C_{1}\cdot\left(\inf_{\alpha\in(0,1)}\alpha+\frac{1}{\sqrt{n(p)}}\int_{\alpha}^{1}\sqrt{\log\left(\left(\frac{C_{3}}{\delta}\right)^{3\text{fat}_{c\delta}(\mathcal{F}_{B})}\right)}d\delta+\sqrt{\frac{\log(\frac{1}{\rho})}{n(p)}}\right)$
$\displaystyle\leq
2C_{1}\cdot\left(\inf_{\alpha\in(0,1)}\alpha+\frac{1}{\sqrt{n(p)}}\int_{\alpha}^{1}\sqrt{3\text{fat}_{c\delta}(\mathcal{F}_{B})\log\left(\left(\frac{C_{3}}{\delta}\right)\right)}d\delta+\sqrt{\frac{\log(\frac{1}{\rho})}{n(p)}}\right)$
$\displaystyle\leq
C^{\prime}_{\mathcal{F}_{B}}\sqrt{\frac{\log(\frac{1}{\rho})}{n(p)}}$

where $C^{\prime}_{\mathcal{F}_{B}}$ is a finite constant that depends on the
complexity of $\mathcal{F}_{B}$. ∎

##  Appendix E An Extension: Online Oracle-efficient Quantile Multicalibration
and Multivalid Conformal Prediction

###  E.1 Connection between Multivalidity and Quantile Errors

Here we leverage a similar technique as in [29]. We show that if there exists
some $f$ and level set $p$ that witnesses to the quantile error being $\alpha$
with respect to the conformal score distribution $\mathbf{s}_{t}$’s, an affine
transformation of $f$ also serves as a witness to the pinball loss regret
being large with respect to $\mathbf{s}_{t}$’s. For the same reasons discussed
in [29], this argument needs to happen with respect to the conformal score
distributions $\mathbf{s}_{t}$’s not the realized scores $s_{t}$’s. However,
because our contextual swap regret algorithm’s guarantee is with respect to
realized scores $s_{t}$’s, we will use concentration arguments proved in
Appendix D to show that multivalidity error and pinball loss regret under
$\mathbf{s}_{t}$’s and $s_{t}$’s must be very close with high probability.

######  Lemma E.1.

Fix some distribution of (features, conformal score)
$\mathcal{D}\sim\Delta(\mathcal{X}\times[0,1])$ and write its corresponding
marginal distribution over $\mathcal{X}$ as $\mathcal{D}_{\mathcal{X}}$. The
expected value of the derivative of the pinball loss with respect to the shift
scaled by $f(x)$ is

$\displaystyle\mathop{\mathbb{E}}_{(x,s)\sim\mathcal{D}}\left[\frac{dPB_{q}(p+\tau\cdot
f(x),s)}{d\tau}\Big{|}\tau=b\right]=\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{\mathcal{X}}}\left[f(x)\cdot\left(\Pr_{s\sim\mathcal{D}_{\mathcal{S}}(x)}[s\leq
p+b\cdot f(x)]-q\right)\right]$

###### Proof.

Define the function $H_{(x,s)}(b)=PB_{q}(p+b\cdot f(x),s)$ and its derivative

$\displaystyle H^{\prime}_{(x,s)}(b)$ $\displaystyle=\frac{dPB_{q}(p+\tau\cdot
f(x),s)}{d\tau}\Big{|}\tau=b$
$\displaystyle=\begin{cases}f(x)\cdot(1-q)\quad\text{if $s\leq p+b\cdot
f(x)$}\\\ -f(x)\cdot q\quad\text{otherwise}\end{cases}.$

Taking the expectation of $H^{\prime}_{(x,s)}(b)$ with respect to
$\mathcal{D}$ yields

$\displaystyle\mathop{\mathbb{E}}_{(x,s)\sim\mathcal{D}}\left[\frac{dPB_{q}(p+\tau\cdot
f(x),s)}{d\tau}\Big{|}\tau=b\right]$
$\displaystyle=\mathop{\mathbb{E}}_{(x,s)\sim\mathcal{D}}[H^{\prime}_{(x,s)}(b)]$
$\displaystyle=\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{\mathcal{X}}}\left[\int_{0}^{b}H^{\prime}_{(x,s)}(b)\mathcal{D}_{\mathcal{S}}(x)(ds)\right]$
$\displaystyle=\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{\mathcal{X}}}\left[\int_{0}^{p+b\cdot
f(x)}H^{\prime}_{(x,s)}(b)\mathcal{D}_{\mathcal{S}}(x)(ds)+\int_{p+b\cdot
f(x)}^{1}H^{\prime}_{(x,s)}(b)\mathcal{D}_{\mathcal{S}}(x)(ds)\right]$
$\displaystyle=\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{\mathcal{X}}}\left[f(x)\cdot\left(\int_{0}^{p+b\cdot
f(x)}(1-q)\mathcal{D}_{\mathcal{S}}(x)(ds)-\int_{p+b\cdot
f(x)}^{1}q\mathcal{D}_{\mathcal{S}}(x)(ds)\right)\right]$
$\displaystyle=\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{\mathcal{X}}}\left[f(x)\cdot\left(\Pr_{s\sim\mathcal{D}_{\mathcal{S}}(x)}[s\leq
p+b\cdot f(x)]-q\right)\right].$

∎

######  Lemma E.2.

Fix $\tilde{\pi}_{1:T}$. Suppose for every $t\in[T]$, $\mathbf{s}_{t}$ is
$\rho$-Lipschitz and continuous. If there exists
$p\in\mathcal{P}_{\text{quantile}}$ and $f\in\mathcal{F}_{B}$ such that

$Q(\tilde{\pi}_{1:T},p,f)\geq\alpha$

then there exists $f^{\prime}\in\mathcal{F}_{(1+\sqrt{B})^{2}}$ such that

$\sum_{t\in
S(\tilde{\pi}_{1:T},p)}\mathop{\mathbb{E}}_{s_{t}\sim\mathbf{s}_{t}}\left[PB(\hat{p}_{t},s_{t})-PB(f^{\prime}(x_{t}),s_{t})\right]\geq\frac{\alpha^{2}}{\max(2,8B\rho)}$

###### Proof.

Fix $p\in\mathcal{P}_{\text{quantile}}$ and
$\tilde{\pi}_{1:T}=\\{(x_{t},\mathbf{s}_{t},\hat{p}_{t})\\}_{t=1}^{T}$. Write

$H(\tau)=\frac{1}{n(p)}\sum_{t\in
S(p)}f(x_{t})\cdot(q-\Pr_{s_{t}\sim\mathbf{s}_{t}}[s_{t}\leq p+\tau\cdot
f(x_{t})])$

and $H^{-1}$ is the corresponding inverse function. Define
$f^{\prime}(x)=p+b\cdot f(x)$ where $b$ is chosen to be

$b=\min\left(1,H^{-1}\left(\frac{\alpha}{2}\right)\right).$

Note because $b\leq 1$, $f^{\prime}\in\mathcal{F}_{(1+\sqrt{B})^{2}}$.

We can re-write the difference in pinball loss under $p$ and
$f^{\prime}(x_{t})$ in terms of $H$:

$\displaystyle\mathop{\mathbb{E}}_{(x,s)\sim\mathcal{D}^{p}}[PB_{q}(p,s)-PB_{q}(p+b\cdot
f(x),s)]$
$\displaystyle=-\int_{\mathcal{X}\times[0,1]}\left(\int_{0}^{b}\frac{dPB_{q}(p+\tau\cdot
f(x),s)}{d\tau}d\tau\right)\mathcal{D}^{p}(dx,ds)$
$\displaystyle=-\int_{0}^{b}\left(\int_{\mathcal{X}\times[0,1]}\frac{dPB_{q}(p+\tau\cdot
f(x),s)}{d\tau}\mathcal{D}^{p}(dx,ds)\right)d\tau$
$\displaystyle=\int_{0}^{b}\mathop{\mathbb{E}}_{x\sim\mathcal{D}^{p}_{\mathcal{X}}}\left[f(x)\cdot\left(q-\Pr_{s\sim\mathcal{D}^{p}_{\mathcal{S}}(x)}[s\leq
p+\tau\cdot f(x)]\right)\right]d\tau$
$\displaystyle=\int_{0}^{b}H(\tau)d\tau.$

######  Lemma E.3.

Fix $\tilde{\pi}_{1:T}$. Suppose $\mathcal{D}(\tilde{\pi}_{1:T})$ is
$\rho$-Lipschitz. If there exists $p\in\mathcal{P}_{\text{quantile}}$ and
$f\in\mathcal{F}_{B}$ such that

$H(0)=\mathop{\mathbb{E}}_{x\sim\mathcal{D}^{p}_{\mathcal{X}}(\tilde{\pi}_{1:T})}\left[f(x)\cdot\left(q-\Pr_{s\sim\mathcal{D}^{p}_{\mathcal{S}}(\tilde{\pi}_{1:T},x)}[s\leq
p]\right)\right]\geq\alpha.$

Then we have

$\int_{0}^{b}H(\tau)d\tau=\int_{0}^{b}\mathop{\mathbb{E}}_{x\sim\mathcal{D}^{p}_{\mathcal{X}}(\tilde{\pi}_{1:T})}\left[f(x)\cdot\left(q-\Pr_{s\sim\mathcal{D}^{p}_{\mathcal{S}}(\tilde{\pi}_{1:T},x)}[s\leq
p+\tau\cdot f(x)]\right)\right]d\tau\geq\frac{\alpha^{2}}{2B\rho}.$

###### Proof.

Note that for any $\tau^{\prime}>\tau$,

$\displaystyle H(\tau^{\prime})-H(\tau)$
$\displaystyle=\mathop{\mathbb{E}}_{x\sim\mathcal{D}^{p}_{\mathcal{X}}}\left[f(x)\cdot\left(\Pr_{s\sim\mathbf{s}|x}[s\leq
p+\tau\cdot f(x)]-\Pr_{s\sim\mathbf{s}|x}[s\leq p+\tau^{\prime}\cdot
f(x)]\right)\right]$
$\displaystyle\geq\rho(\tau-\tau^{\prime})\mathop{\mathbb{E}}_{x\sim\mathcal{D}^{p}_{\mathcal{X}}}[f^{2}(x)]$
$\displaystyle\geq\rho B(\tau-\tau^{\prime})$

because $f\leq\mathcal{F}_{B}$. Using the same argument as in [29], we can
show that the area under the curve is at least

$\displaystyle\int_{0}^{b}H(\tau)d\tau$ $\displaystyle\geq
bH(b)+\frac{(H(0)-H(b))^{2}}{2\rho B}$

where $bH(b)$ is the area of the rectangle and $\frac{(H(0)-H(b))^{2}}{2\rho
B}$ the area of the triangle is where the slope cannot be steeper than $\rho
B$ due to $H$’s $(\rho B)$-Lipschitzness.

#### Case (i) $1\leq H^{-1}(\alpha/2)$:

Because $H(\tau)$ is a non-increasing function in $\tau$,
$H(b)=H(1)\geq\alpha/2$. Therefore, we can lower bound the integral as

$\displaystyle\int_{0}^{b}H(\tau)d\tau$ $\displaystyle\geq
bH(b)+\frac{(H(0)-H(b))^{2}}{2\rho B}$ $\displaystyle\geq bH(b)$
$\displaystyle\geq\frac{\alpha}{2}\geq\frac{\alpha^{2}}{2}.$

#### Case (ii) $1>H^{-1}(\alpha/2)$:

Simply plugging in $b=H^{-1}(\alpha/2)$ yields

$\displaystyle\int_{0}^{b}H(\tau)d\tau$
$\displaystyle\geq\frac{(H(0)-H(b))^{2}}{2\rho B}$
$\displaystyle\geq\frac{1}{2\rho
B}\left(\frac{\alpha}{2}\right)^{2}=\frac{\alpha^{2}}{8\rho B}.$

∎

Lemma E.3 gives us the final result:

$\displaystyle\mathop{\mathbb{E}}_{(x,s)\sim\mathcal{D}^{p}}[PB_{q}(p,s)-PB_{q}(p+b\cdot
f(x),s)]=\int_{0}^{b}H(\tau)d\tau\geq\frac{\alpha^{2}}{\max(2,8\rho B)}.$

∎

######  Corollary E.1.

Fix any $B>0$, $\tilde{\pi}_{1:T}$, and $\mathcal{F}$ that is closed under
affine transformation. Suppose for every $t\in[T]$, $\mathbf{s}_{t}$ is
$\rho$-Lipschitz and continuous, and assume the conformal learner’s contextual
swap regret for pinball loss with respect to any
$\\{f_{p}\\}_{p\in\mathcal{P}_{\text{quantile}}}\in\mathcal{F}_{(1+\sqrt{B})^{2}}^{m}$
is bounded in expectation: for any
$\\{f_{p}\\}_{p\in\mathcal{P}_{\text{quantile}}}\in\mathcal{F}_{(1+\sqrt{B})^{2}}^{m}$,

$\frac{1}{T}\sum_{p\in\mathcal{P}_{\text{quantile}}}\sum_{t\in
S(\tilde{\pi}_{1:T},p)}\mathop{\mathbb{E}}_{s_{t}\sim\mathbf{s}_{t}}[PB_{q}(\hat{p}_{t},s_{t})-PB_{q}(f_{p}(x_{t}),s_{t})]\leq\frac{\alpha}{\max(2B,8\rho
B^{2})}.$

Then its $L_{2}$-swap-multivalidity error with respect to $\mathcal{F}_{B}$ is
bounded as

$\overline{sQ}_{2}(\tilde{\pi}_{1:T},\mathcal{F}_{B})\leq\alpha.$

###### Proof.

For the sake of contradiction, suppose there exists
$\\{f_{p}\\}_{p\in\mathcal{P}_{\text{quantile}}}\in\mathcal{F}_{B}^{m}$ such
that its $L_{2}$-multivalidity error is more than $\alpha$. For each
$p\in\mathcal{P}_{\text{quantile}}$, write

$\alpha_{p}=\frac{n(p)}{T}Q(\tilde{\pi}_{1:T},p,f_{p})^{2}.$

We have

$Q(\tilde{\pi}_{1:T},p,f^{*}_{p})=\sqrt{\frac{T}{n(p)}\alpha_{p}}$

where $f^{*}_{p}=f_{p}$ or $-f_{p}$. Note that

$\displaystyle Q(\tilde{\pi}_{1:T},p,f^{*}_{p})=\frac{1}{n(p)}\sum_{t\in
S(p)}f(x_{t})\cdot(q-\Pr_{s\sim\mathbf{s}_{t}}[s\leq p])\leq\sqrt{B}$

In other words,
$Q(\tilde{\pi}_{1:T},p,f^{*}_{p})\leq\frac{1}{\sqrt{B}}\sqrt{\frac{T}{n(p)}\alpha_{p}}$
and $\frac{1}{\sqrt{B}}\sqrt{\frac{T}{n(p)}\alpha_{p}}\leq 1$.

Lemma E.2 then tells us that for each $p\in\mathcal{P}_{\text{quantile}}$,
there exists $f^{\prime}_{p}\in\mathcal{F}_{(1+\sqrt{B})^{2}}$ such that

$\frac{1}{n(p)}\sum_{t\in
S(\tilde{\pi}_{1:T},p)}\mathop{\mathbb{E}}_{s_{t}\sim\mathbf{s}_{t}}\left[PB(\hat{p}_{t},s_{t})-PB(f^{\prime}_{p}(x_{t}),s_{t})\right]\geq\frac{1}{\max(2,8\rho
B)}\frac{1}{B}\frac{T}{n(p)}\alpha_{p}$

Averaging over each $p\in\mathcal{P}_{\text{quantile}}$ gives us

$\displaystyle\sum_{p\in\mathcal{P}_{\text{quantile}}}\sum_{t\in
S(\tilde{\pi}_{1:T},p)}\mathop{\mathbb{E}}_{s_{t}\sim\mathbf{s}_{t}}\left[PB(\hat{p}_{t},s_{t})-PB(f^{\prime}_{p}(x_{t}),s_{t})\right]$
$\displaystyle\geq\sum_{p\in\mathcal{P}_{\text{quantile}}}\frac{1}{\max(2,8\rho
B)}\frac{1}{B}\frac{T}{n(p)}\alpha_{p}$ $\displaystyle>\frac{\alpha
T}{\max(2B,8\rho B^{2})}$

This is a contradiction to our contextual-swap-regret guarantee with respect
to pinball loss. ∎

As noted in Section 6, there was nothing specific about the squared loss in
Theorem 3.1 and it can be generalized to any other loss as well. We state this
more formally in the following claim:

######  Claim E.1.

Fix some $B>0$. Suppose the sequential shattering dimension of
$\mathcal{F}_{B}$ is finite at any scale $\delta$:
$\text{fat}_{\delta}(\mathcal{F}_{B})<\infty$. Suppose oracle $\mathcal{A}$’s
regret bound $r_{\mathcal{A}}(T,\mathcal{F}_{B})$ is concave in time horizon
$T$. Fix any adversary Adv that forms $(x_{t},y_{t})$ as a function of
$\psi_{1:t-1}=\\{(x_{\tau},s_{\tau},\hat{p}_{\tau})\\}_{\tau=1}^{t-1}$. With
probability $1-\delta$ over the randomness of
$\\{i_{t}\sim\mathbf{i}_{t}\\}_{t=1}^{T}$, Forecaster
$\mathscr{F}_{\text{ContextualSwap}}(\mathcal{F}_{B},\mathcal{A},m,T)$ results
in $\pi_{1:T}=\\{(x_{t},s_{t},\hat{p}_{t},(i_{t},j_{t}))\\}_{t=1}^{T}$ such
that

$\displaystyle\sup_{\\{f_{p}\\}_{p\in\mathcal{P}}\in\mathcal{F}_{B}^{m}}\sum_{t=1}^{T}\mathop{\mathbb{E}}_{\hat{p}^{\prime}_{t}}\left[PB_{q}(\hat{p}^{\prime}_{t}/m,s_{t})-PB_{q}(f_{\hat{p}^{\prime}_{t}}(x_{t}),s_{t})|\pi_{1:t-1}\right]$
$\displaystyle\leq\left(mr_{\mathcal{A}}\left(\frac{T}{m},\mathcal{F}_{B}\right)+\frac{T}{m}+m\right)+\max(8B,2\sqrt{B})mC_{\mathcal{F}_{B}}\sqrt{\frac{\log(\frac{4m}{\delta})}{T}}.$

For the sake of clarity and brevity, we skip the proof for the above claim or
have a separate meta theorem from which both Theorem 3.1 and the above claim
can be obtained as corollaries.

###  E.2 Final Bounds

Combining concentration bounds in Appendix D and Corollary E.1, we can finally
show that the connection between the contextual swap regret with pinball loss
and the quantile $\ell_{2}$-multivalidity error:

######  Corollary E.2.

Fix any $B>0$, $\tilde{\pi}_{1:T}$, and $\mathcal{F}$ that is closed under
affine transformation. Suppose for every $t\in[T]$, $\mathbf{s}_{t}$ is
$\rho$-Lipschitz and continuous and that the sequential shattering dimension
of $\mathcal{F}_{B}$ is finite at any scale $\delta$:
$\text{fat}_{\delta}(\mathcal{F}_{B})<\infty$. With probability $1-\rho$, the
forecaster’s $L_{2}$-swap-multivalidity error with respect to
$\mathcal{F}_{B}$ is bounded as

$\displaystyle\overline{sQ}_{2}(\pi_{1:T},\mathcal{F}_{B})$
$\displaystyle\leq\max(2B,8\rho
B^{2})\left(\frac{1}{T}\sum_{p\in\mathcal{P}_{\text{quantile}}}\sum_{t\in
S(p)}PB_{q}(\hat{p}_{t},s_{t})-PB_{q}(f_{p}(x_{t}),s_{t})+\frac{mB^{\prime}C^{\prime}_{\mathcal{F}_{B}}\sqrt{\log(8m/\rho)}}{\sqrt{T}}\right)$
$\displaystyle+\frac{2m\sqrt{B}B^{\prime}C_{\mathcal{F}_{B}}\sqrt{\log(\frac{8m}{\rho})}}{\sqrt{T}}+\frac{m(B^{\prime}C_{\mathcal{F}_{B}})^{2}\log(\frac{8m}{\rho})}{T}$

where $(C_{\mathcal{F}_{B}},C^{\prime}_{\mathcal{F}_{B}})$ are the same as in
Lemma D.3 and D.5.

###### Proof.

Write $B^{\prime}=\max(1,\sqrt{B})$. By union-bounding Lemma D.5 over all
$p\in\mathcal{P}_{\text{quantile}}$, we have that with probability $1-4m\rho$,
for any
$\\{f_{p}\\}_{p\in\mathcal{P}_{\text{quantile}}}\in\mathcal{F}_{(1+\sqrt{B})^{2}}^{m}$,

$\displaystyle\frac{1}{T}\sum_{p\in\mathcal{P}_{\text{quantile}}}\sum_{t\in
S(p)}\mathop{\mathbb{E}}_{s_{t}\sim\mathbf{s}_{t}}\left[PB_{q}(\hat{p}_{t},s_{t})-PB_{q}(f_{p}(x_{t}),s_{t})\right]$
$\displaystyle=\sum_{p\in\mathcal{P}_{\text{quantile}}}\frac{n(p)}{T}\left(\frac{1}{n(p)}\sum_{t\in
S(p)}\mathop{\mathbb{E}}_{s_{t}\sim\mathbf{s}_{t}}\left[PB_{q}(\hat{p}_{t},s_{t})-PB_{q}(f_{p}(x_{t}),s_{t})\right]\right)$
$\displaystyle\leq\sum_{p\in\mathcal{P}_{\text{quantile}}}\frac{n(p)}{T}\left(\frac{1}{n(p)}\sum_{t\in
S(p)}PB_{q}(\hat{p}_{t},s_{t})-PB_{q}(f_{p}(x_{t}),s_{t})+B^{\prime}C^{\prime}_{\mathcal{F}_{B}}\sqrt{\frac{\log(\frac{1}{\rho})}{n(p)}}\right)$
$\displaystyle=\frac{1}{T}\sum_{p\in\mathcal{P}_{\text{quantile}}}\sum_{t\in
S(p)}PB_{q}(\hat{p}_{t},s_{t})-PB_{q}(f_{p}(x_{t}),s_{t})+\frac{B^{\prime}C^{\prime}_{\mathcal{F}_{B}}\sqrt{\log(1/\rho)}}{T}\sum_{p\in\mathcal{P}_{\text{quantile}}}\sqrt{n(p)}$
$\displaystyle\leq\frac{1}{T}\sum_{p\in\mathcal{P}_{\text{quantile}}}\sum_{t\in
S(p)}PB_{q}(\hat{p}_{t},s_{t})-PB_{q}(f_{p}(x_{t}),s_{t})+\frac{mB^{\prime}C^{\prime}_{\mathcal{F}_{B}}\sqrt{\log(1/\rho)}}{\sqrt{T}}.$

Similarly, we have with probability $1-4m\rho$

$\displaystyle\overline{sQ}_{2}(\pi_{1:T},\mathcal{F}_{B})$
$\displaystyle=\sup_{\\{f_{p}\\}_{p\in\mathcal{P}_{\text{quantile}}}\in\mathcal{F}_{B}^{m}}\sum_{p\in\mathcal{P}_{\text{quantile}}}\frac{n(p)}{T}(Q(\pi_{1:T},p,f_{p}))^{2}$
$\displaystyle\leq\sup_{\\{f_{p}\\}_{p\in\mathcal{P}_{\text{quantile}}}\in\mathcal{F}_{B}^{m}}\sum_{p\in\mathcal{P}_{\text{quantile}}}\frac{n(p)}{T}\left(Q(\tilde{\pi}_{1:T},p,f_{p})+B^{\prime}C_{\mathcal{F}_{B}}\sqrt{\frac{\log(\frac{1}{\rho})}{n(p)}}\right)^{2}$
$\displaystyle=\sup_{\\{f_{p}\\}_{p\in\mathcal{P}_{\text{quantile}}}\in\mathcal{F}_{B}^{m}}\sum_{p\in\mathcal{P}_{\text{quantile}}}\frac{n(p)}{T}\left(Q(\tilde{\pi}_{1:T},p,f_{p})^{2}+2Q(\tilde{\pi}_{1:T},p,f_{p})B^{\prime}C_{\mathcal{F}_{B}}\sqrt{\frac{\log(\frac{1}{\rho})}{n(p)}}+(B^{\prime}C_{\mathcal{F}_{B}})^{2}\frac{\log(\frac{1}{\rho})}{n(p)}\right)$
$\displaystyle\leq\sup_{\\{f_{p}\\}_{p\in\mathcal{P}_{\text{quantile}}}\in\mathcal{F}_{B}^{m}}\sum_{p\in\mathcal{P}_{\text{quantile}}}\frac{n(p)}{T}\left(Q(\tilde{\pi}_{1:T},p,f_{p})^{2}+2\sqrt{B^{\prime}}B^{\prime}C_{\mathcal{F}_{B}}\sqrt{\frac{\log(\frac{1}{\rho})}{n(p)}}+(B^{\prime}C_{\mathcal{F}_{B}})^{2}\frac{\log(\frac{1}{\rho})}{n(p)}\right)$
$\displaystyle\leq\overline{sQ}_{2}(\tilde{\pi}_{1:T},\mathcal{F}_{B})+\frac{2m\sqrt{B^{\prime}}B^{\prime}C_{\mathcal{F}_{B}}\sqrt{\log(\frac{1}{\rho})}}{\sqrt{T}}+\frac{m(B^{\prime}C_{\mathcal{F}_{B}})^{2}\log(\frac{1}{\rho})}{T}.$

The second to last inequality follows from $f_{p}\in\mathcal{F}_{B}$, so
$Q(\tilde{\pi}_{1:T},p,f_{p})\leq\sqrt{B}$. The last inequality follows from
$\sum_{p\in\mathcal{P}_{\text{quantile}}}\sqrt{n(p)}\leq m\sqrt{T}$.

Combining them together via Corollary E.1, we have with probability
$1-8m\rho$,

$\displaystyle\overline{sQ}_{2}(\pi_{1:T},\mathcal{F}_{B})$
$\displaystyle\leq\max(2B,8\rho
B^{2})\left(\frac{1}{T}\sum_{p\in\mathcal{P}_{\text{quantile}}}\sum_{t\in
S(p)}PB_{q}(\hat{p}_{t},s_{t})-PB_{q}(f_{p}(x_{t}),s_{t})+\frac{mB^{\prime}C^{\prime}_{\mathcal{F}_{B}}\sqrt{\log(1/\rho)}}{\sqrt{T}}\right)$
$\displaystyle+\frac{2m\sqrt{B}B^{\prime}C_{\mathcal{F}_{B}}\sqrt{\log(\frac{1}{\rho})}}{\sqrt{T}}+\frac{m(B^{\prime}C_{\mathcal{F}_{B}})^{2}\log(\frac{1}{\rho})}{T}$

∎

[40] shows that any function that is online learnable has a finite sequential
fat shattering dimension at any $\alpha$. As we are already assuming an online
quantile regression oracle for $\mathcal{A}$, we can assume that
$\mathcal{F}$’s sequential fat shattering dimension is finite at any $\alpha$.

When we plug the above bound to the contextual swap regret guarantee of
$\mathscr{F}_{\text{ContextualSwap}}$ in Claim E.1, we get the following
$\ell_{2}$-multivalidity error rate:

######  Corollary E.3.

Fix $\mathcal{F}$ and suppose its fat shattering dimension is finite at any
scale $\alpha$ (e.g. it is online learnable). Suppose for every $t\in[T]$,
$\mathbf{s}_{t}$ is $\rho$-Lipschitz and continuous. Then, the conformal
learner that makes predictions according to
$\mathscr{F}_{\text{ContextualSwap}}(\mathcal{F}_{(1+\sqrt{B})^{2}},\mathcal{A},m,T)$
will guarantee that with probability $1-\delta$

$\displaystyle\overline{sQ}_{2}(\pi_{1:T},\mathcal{F}_{B})$
$\displaystyle\leq\max(2B,8\rho
B^{2})\bigg{(}\frac{1}{T}\left(mr_{\mathcal{A}}\left(\frac{T}{m},\mathcal{F}_{B}\right)+\frac{T}{m}+m\right)$
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;+\max(8B,2\sqrt{B})mC_{\mathcal{F}_{B}}\sqrt{\frac{\log(\frac{16m}{\delta})}{T}}+\frac{mB^{\prime}C^{\prime}_{\mathcal{F}_{B}}\sqrt{\log(16m/\delta)}}{\sqrt{T}}\bigg{)}$
$\displaystyle\;\;\;\;+\frac{2m\sqrt{B}B^{\prime}C_{\mathcal{F}_{B}}\sqrt{\log(\frac{16m}{\delta})}}{\sqrt{T}}+\frac{m(B^{\prime}C_{\mathcal{F}_{B}})^{2}\log(\frac{16m}{\delta})}{T}.$

In other words, for oracles whose regret is $\sqrt{T}$, setting
$m=\frac{1}{T^{1/4}}$ yields
$\overline{sQ}_{2}(\pi_{1:T},\mathcal{F}_{B})=O(T^{-1/4})$.

###  E.3 Conformal Learner’s Multivalidity Error Against Linear Functions

######  Theorem E.1.

Suppose $||x_{t}||_{2}\leq 1$ for every round $t\in[T]$. Online projected
gradient descent $\mathcal{A}_{PGD}$ is defined as

$\theta_{t+1}=\text{Project}_{||\theta_{t}||\leq
A}\left(\theta_{t}-\eta\cdot\nabla\ell_{t}(\theta_{t})\right)$

where $\ell_{t}(\theta)=PB(s_{t},\theta\cdot x_{t})$. $\mathcal{A}_{PGD}$
guarantees that

$\sum_{t=1}^{T}PB_{q}(s_{t},\theta_{t}\cdot
x_{t})-\min_{\theta^{*}:||\theta^{*}||\leq
B}\sum_{t=1}^{T}PB_{q}(s_{t},\theta^{*}\cdot
x_{t})\leq\frac{B^{2}}{2\eta}+\frac{\eta T}{2}.$

Setting $\eta=\frac{B}{\sqrt{T}}$ gives us

$\sum_{t=1}^{T}PB_{q}(s_{t},\theta_{t}\cdot
x_{t})-\min_{\theta^{*}:||\theta^{*}||\leq
B}\sum_{t=1}^{T}PB_{q}(s_{t},\theta^{*}\cdot x_{t})\leq B\sqrt{T}.$

###### Proof.

It’s easy to see that the loss function $\ell_{t}(\theta)$ is convex in
$\theta$. Then, following [46], we get

$\sum_{t=1}^{T}PB(s_{t},\theta_{t}\cdot
x_{t})-\min_{\theta^{*}:||\theta^{*}||\leq
A}\sum_{t=1}^{T}PB(s_{t},\theta^{*}\cdot
x_{t})\leq\frac{A}{2\eta}+\frac{\eta}{2}\sum_{t=1}^{T}||\nabla\ell_{t}(\theta_{t})||^{2}_{2}.$

So it suffices to bound $||\nabla\ell_{t}(\theta_{t})||^{2}_{2}$ for every
$t\in[T]$:

$\displaystyle||\nabla\ell_{t}(\theta_{t})||^{2}_{2}$ $\displaystyle=||\nabla
PB_{q}(s_{t},\theta\cdot x_{t})||^{2}_{2}$
$\displaystyle\leq\max(q,1-q)||x_{t}||^{2}_{2}$ $\displaystyle\leq 1$

∎

######  Corollary E.4.

Suppose the adversary creates feature vectors such that $||x_{t}||_{2}\leq 1$
and . Let
$\mathcal{F}^{lin}=\\{\langle\theta,x\rangle:\theta\in\mathbb{R}^{d}\\}$ be
all linear functions and for every $t\in[T]$, $\mathbf{s}_{t}$ is
$\rho$-Lipschitz and continuous. Then,
$\mathscr{F}_{\text{ContextualSwap}}(\mathcal{F}^{lin}_{(1+\sqrt{B})^{2}},\mathcal{A}_{PGD},m,T)$
and setting $m=T^{1/4}$ guarantees that

$\overline{sQ}_{2}(\pi_{1:T},\mathcal{F}_{B})\leq
O\left(\sqrt{\ln\left(\frac{T^{1/4}}{\delta}\right)}T^{-1/4}\right).$

###### Proof.

Because $||x_{t}||_{2}\leq 1$, all linear functions whose range is bounded
corresponds exactly to all linear functions whose norm of the slope is
bounded:

$\mathcal{F}^{lin}_{(1+\sqrt{B}^{2})}=\\{\langle\theta,x\rangle:||\theta||^{2}_{2}\leq(1+\sqrt{B})^{2}\\}.$

Theorem E.1 tells us that $\mathcal{A}_{PGD}$ with the learning rate set to be
$\eta=\frac{1+\sqrt{B}}{\sqrt{T}}$ achieves

$\sum_{t=1}^{T}PB_{q}(s_{t},\hat{p}_{t})-\min_{f\in\mathcal{F}^{lin}_{(1+\sqrt{B})^{2}}}\sum_{t=1}^{T}PB_{q}(s_{t},f(x_{t}))\leq(1+\sqrt{B})\sqrt{T}$

where $\hat{p}_{t}=\langle\theta_{t},x_{t}\rangle$. In other words, plugging
in $r_{\mathcal{A}}(T)=(1+\sqrt{B})\sqrt{T}$ into Corollary E.3 gives us that
with probability $1-\delta$,

$\overline{sQ}_{2}(\pi_{1:T},\mathcal{F}_{B})\leq
O\left(\rho\sqrt{\ln\left(\frac{T^{1/4}}{\delta}\right)}T^{-1/4}\right).$

∎

##  Appendix F Better Online $L_{2}$-multicalibration for Finite $\mathcal{F}$

In this section, we show how to leverage the Online Minimax Optimization
Framework introduced by [34] to obtain $L_{2}$-multicalibration bounds for
finite classes $\mathcal{F}$ that obtain multicalibration error tending to
zero at the optimal $\tilde{O}\left(\frac{1}{\sqrt{T}}\right)$ rate. The
algorithm has running time scaling polynomially with $|\mathcal{F}|$, and so
is not oracle efficient.

Recall that we introduced the AMF framework in Section 5.1; we do not repeat
the preliminaries here.

Now, we describe how to cast our problem into the AMF framework. We refer to
the Learner and the Adversary in the AMF framework as AMF Learner and AMF
adversary.

Fix some finite set of predictors $\mathcal{F}$. At each round $t\in[T]$, the
AMF Learner’s strategy space is $\Theta_{t}=\mathcal{P}=[\frac{1}{m}]$, the
AMF Adversary’s strategy space is $\mathcal{Z}_{t}=\Delta(\mathcal{Y})$, and
the dimension of the loss vectors we will construct is $d=|\mathcal{F}|$. For
convenience, we equivalently write the adversary’s strategy space as
$\mathcal{Z}_{t}=[0,1]$ and write $z_{t}$ for the probability with which
$y\sim z_{t}$ is 1. Once the forecaster observes the feature vector $x_{t}$,
we construct the loss vector at round $t$ as follows: For each
$f\in\mathcal{F}$, we assign $f$ a coordinate $i$ in the loss vector and
define $\ell^{i}_{t}$ as:

$\displaystyle\ell^{i}_{t}(\theta_{t},z_{t})=\ell^{f}_{t}(\theta_{t},z_{t})=\mathop{\mathbb{E}}_{y_{t}\sim
z_{t}}\left[(f(x_{t})\cdot(y_{t}-\theta_{t}))K(\pi_{1:t-1},\theta_{t},f)\right]$
(9)

The loss function $\ell$ defined above in (9) is defined in terms of an upper
bound on the increase in the unnormalized $L_{2}$-multicalibration error that
we show in Lemma F.1 below, whose proof can be found in Appendix
LABEL:app:miss-amf. For convenience, to denote the unnormalized version of the
$L2$-multicalibration error, we write.

$u\overline{K}_{2}(\pi_{1:T},f)=T\cdot\overline{K}_{2}(\pi_{1:T})$

######  Lemma F.1.

Suppose $B=\max_{f\in\mathcal{F},x\in\mathcal{X}}(f(x))^{2}$. Fix $t\in[T]$,
$\pi_{1:t-1}$, $(x_{t},y_{t},\hat{p})$ and $f\in\mathcal{F}$. We can bound the
increase in the unnormalized $L_{2}$-multicalibration error for $f$ in the
case in which the interaction between the Forecaster and the Adversary results
in $(x_{t},y_{t},\hat{p})$ in round $t$ as follows: if
$n(\pi_{1:t-1},\hat{p})\geq 1$, then

$\displaystyle
u\overline{K}_{2}(\pi_{1:t-1}\circ(x_{t},y_{t},\hat{p}),f)-u\overline{K}_{2}(\pi_{1:t-1},f)\leq\frac{B}{n(\pi_{1:t-1},\hat{p})}+2(f(x_{t})\cdot(y_{t}-\hat{p}))K(\pi_{1:t-1},\hat{p},f)$

Otherwise,

$u\overline{K}_{2}(\pi_{1:t-1}\circ(x_{t},y_{t},\hat{p}),f)-u\overline{K}_{2}(\pi_{1:t-1},f)\leq
B$

###### Proof.

Fix any $f\in\mathcal{F}$. The latter case when $n(\pi_{1:t-1})=0$, it’s easy
to see that

$u\overline{K}_{2}(\pi_{1:t-1}\circ(x_{t},y_{t},\hat{p}),f)-u\overline{K}_{2}(\pi_{1:t-1},f)=(f(x_{t})\cdot(y_{t}-\hat{p}))^{2}\leq
B.$

Now consider the other case.

$\displaystyle
u\overline{K}_{2}(\pi_{1:t-1}\circ(x_{t},y_{t},\hat{p}),f)-u\overline{K}_{2}(\pi_{1:t-1},f)$
$\displaystyle=(n(\pi_{1:t-1},\hat{p})+1)\cdot(K(\pi_{1:t-1}\circ(x_{t},y_{t},\hat{p}),\hat{p},f))^{2}-n(\pi_{1:t-1},\hat{p})\cdot(K(\pi_{1:t-1},\hat{p},f))^{2}$
$\displaystyle=\frac{1}{n(\pi_{1:t-1},\hat{p})+1}\left(f(x_{t})\cdot(y_{t}-\hat{p})+\sum_{\tau\in
S(\pi_{1:t-1},\hat{p})}f(x_{\tau})\cdot(y_{\tau}-\hat{p}_{\tau})\right)^{2}$
$\displaystyle-\frac{1}{n(\pi_{1:t-1},\hat{p})}\left(\sum_{\tau\in
S(\pi_{1:t-1},\hat{p})}f(x_{\tau})\cdot(y_{\tau}-\hat{p}_{\tau})\right)^{2}$
$\displaystyle\leq\frac{1}{n(\pi_{1:t-1},\hat{p})}\left(f(x_{t})\cdot(y_{t}-\hat{p})+\sum_{\tau\in
S(\pi_{1:t-1},\hat{p})}f(x_{\tau})\cdot(y_{\tau}-\hat{p}_{\tau})\right)^{2}$
$\displaystyle-\frac{1}{n(\pi_{1:t-1},\hat{p})}\left(\sum_{\tau\in
S(\pi_{1:t-1},\hat{p})}f(x_{\tau})\cdot(y_{\tau}-\hat{p}_{\tau})\right)^{2}$
$\displaystyle=\frac{1}{n(\pi_{1:t-1},\hat{p})}\left((f(x_{t})\cdot(y_{t}-\hat{p}))^{2}+2(f(x_{t})\cdot(y_{t}-\hat{p}))\sum_{t\in
S(\pi_{1:t-1},\hat{p})}f_{\tau}(x_{\tau})\cdot(y_{\tau}-\hat{p}_{\tau})\right)$
$\displaystyle\leq\frac{B}{n(\pi_{1:t-1},\hat{p})}+2(f(x_{t})\cdot(y_{t}-\hat{p}))K(\pi_{1:t-1},\hat{p},f)$

where the last inequality follows from the fact that $f(x_{t})^{2}\leq B$. ∎

1: for $t=1,\dots,T$ do

2: Forecaster $\mathscr{F}_{AMF}$ observes the feature vector
$x_{t}\in\mathcal{X}$.

3: Construct the AMF-Learner’s environment as $\Theta_{t}=\mathcal{P}$,
$\mathcal{Z}_{t}=\Delta(\mathcal{Y})s$, and $\ell_{t}$ as defined in (9).

4: After observing the environment $(\Theta_{t},\mathcal{Z}_{t},\ell_{t})$,
AMF-Learner chooses a random strategy $\tilde{\theta}_{t}$ according to
Algorithm 2 of [34].

5: Adversary Adv chooses $p_{t}\in[0,1]$ which is the the probability with
which $y_{t}=1$.

6: AMF Learner chooses $\theta_{t}\in\mathcal{P}$ by sampling from
$\tilde{\theta}_{t}\in\Delta(\mathcal{P})$.

7: Forecaster $\mathscr{F}_{AMF}$ makes the forecast $\hat{p}_{t}=\theta_{t}$
and observes $y_{t}\sim p_{t}$.

8: Set the action played by the AMF Adversary’s strategy as $z_{t}=y_{t}$ and
have AMF Learner suffer $\ell_{t}(\theta_{t},z_{t})$.

Algorithm 4 Forecaster $\mathscr{F}_{AMF}(\mathcal{F})$

######  Theorem F.1.

Suppose $\max_{f\in\mathcal{F},x\in\mathcal{X}}(f(x))^{2}\leq B$ and
$|\mathcal{F}|<\infty$. Against any adaptive adversary, the
$L_{2}$-multicalibration error of Forecaster $\mathcal{F}_{AMF}(\mathcal{F})$
is always bounded in expectation over the forecaster’s randomness as:

$\mathop{\mathbb{E}}_{\pi_{1:T}}[\overline{K}_{2}(\pi_{1:T},\mathcal{F}_{B})]\leq\frac{1}{T}\left(3Bm\log(T)+4\sqrt{BT\ln(|\mathcal{F}|)}+\frac{\sqrt{B}T}{m}\right).$

Setting $m=\sqrt{T}$, we have

$\mathop{\mathbb{E}}_{\pi_{1:T}}[\overline{K}_{2}(\pi_{1:T},\mathcal{F}_{B})]\leq\frac{3B\log(T)+4\sqrt{B\ln(|\mathcal{F}|)}+\sqrt{B}}{\sqrt{T}}=\tilde{O}\left(\frac{1}{T^{1/2}}\right).$

###### Proof.

First, note that the constructed loss function $\ell^{f}_{t}$ is linear in
terms of the adversary’s strategy $z_{t}$ because of the linearity of
expectation. Also, note that

$\displaystyle|\ell^{f}_{t}(\theta_{t},z_{t})|$
$\displaystyle\leq|(f(x_{t})\cdot(y_{t}-\hat{p}))K(\pi_{1:t-1},\hat{p}_{t},f)|$
$\displaystyle\leq|f(x_{t})||y_{t}-\hat{p}_{t}||K(\pi_{1:t-1},\hat{p}_{t},f)|$
$\displaystyle\leq\sqrt{B}$

as $f(x)^{2}\leq B$.

We can calculate the Adversary-Moves-First value. Whenever the adversary
chooses $z_{t}\in[0,1]$ which corresponds to the probability of $y_{t}$ is 1,
we can always deterministically set
$\theta_{t}=\text{Round}(z_{t},\frac{1}{m})$ and suffer $\frac{1}{m}$
discretization error.

$\displaystyle w^{A}_{t}$
$\displaystyle=\sup_{z_{t}\in\Delta(\mathcal{Y})}\min_{\tilde{\theta}_{t}\in\Delta(\mathcal{P})}\max_{f\in\mathcal{F}}\mathop{\mathbb{E}}_{\theta_{t}\sim\tilde{\theta}_{t},y_{t}\sim
z_{t}}\left[\ell^{f}_{t}(\theta_{t},y_{t})\right]$
$\displaystyle\leq\frac{\sqrt{B}}{m}.$

Finally, it remains to upper bound our cumulative calibration error using
Lemma F.1 to telescope over our per-round _increase_ in multicalibration
error, and use the upper bound on the algorithm’s AMF regret from Theorem 5.1
to bound the sum of these terms in the worst case over $f\in\mathcal{F}_{B}$.

$\displaystyle\mathop{\mathbb{E}}_{\pi_{1:T}}\left[\max_{f\in\mathcal{F}}u\overline{K}_{2}(\pi_{1:T},f)\right]$
$\displaystyle=\mathop{\mathbb{E}}_{\pi_{1:T}}\left[\max_{f\in\mathcal{F}}\sum_{t=1}^{T}u\overline{K}_{2}(\pi_{1:t},f)-u\overline{K}_{2}(\pi_{1:t-1},f)\right]$
$\displaystyle\leq\mathop{\mathbb{E}}_{\pi_{1:T}}\left[\max_{f\in\mathcal{F}}\sum_{t\in[T]:n(\pi_{1:t-1},\hat{p}_{t})=0}B+\sum_{t\in[T]:n(\pi_{1:t-1},\hat{p}_{t})\geq
1}\frac{B}{n(\pi_{1:t-1},\hat{p}_{t})}+2\ell^{f}_{t}(\theta_{t},z_{t})\right]\quad$
Lemma F.1
$\displaystyle\leq\mathop{\mathbb{E}}_{\pi_{1:T}}\left[Bm+\max_{f\in\mathcal{F}}\sum_{t\in[T]:n(\pi_{1:t-1},\hat{p}_{t})\geq
1}\frac{B}{n(\pi_{1:t-1},\hat{p}_{t})}+2\ell^{f}_{t}(\theta_{t},z_{t})\right]$
$\displaystyle\leq\mathop{\mathbb{E}}_{\pi_{1:T}}\left[Bm+\sum_{t\in[T]:n(\pi_{1:t-1},\hat{p}_{t})\geq
1}\frac{B}{n(\pi_{1:t-1},\hat{p}_{t})}+2\max_{f\in\mathcal{F}}\sum_{t=1}^{T}\ell^{f}_{t}(\theta_{t},z_{t})\right]$
$\displaystyle\leq
Bm+2Bm\log(T)+\mathop{\mathbb{E}}_{\pi_{1:T}}\left[R_{T}+\sum_{t=1}^{T}w^{A}_{t}\right]$
$\displaystyle\leq
3Bm\log(T)+4\sqrt{BT\ln(|\mathcal{F}|)}+\frac{T\sqrt{B}}{m}\quad$ Theorem 5.1

The third inequality follows because when $n(\pi_{1:t-1,\hat{p}_{t}})=0$ for
round $t\in[T]$, then $\ell^{f}_{t}(\theta_{t},z_{t})=0$ as
$K(\pi_{1:t-1},p,f)=0$. The fourth inequality follows because for any
$\pi_{1:T}$

$\displaystyle\sum_{t\in[T]:n(\pi_{1:t-1},\hat{p}_{t})\geq
1}\frac{1}{n(\pi_{1:t-1},\hat{p}_{t})}$
$\displaystyle=\sum_{p\in\mathcal{P}}\sum_{\tau=1}^{|n(\pi_{1:T},p)|}\frac{1}{\tau}$
$\displaystyle\leq\sum_{p\in\mathcal{P}}\sum_{\tau=1}^{T}\frac{1}{\tau}$
$\displaystyle\leq 2m\log(T).$

∎

We remark that this bound is instantiated by Algorithm 2, which needs at each
round to compute a numeric value $\chi_{t}^{j}$ for each $f\in\mathcal{F}$
(each of which is a sum over at most $T$ terms) and to solve a minmax problem
which can be expressed as a linear program with $m=\sqrt{T}$ variables and
$|\mathcal{F}|$ many constraints. Hence the running time of the algorithm is
polynomial in $T$ and $|\mathcal{F}|$.