AB acknowledges support from the National Science Foundation Graduate Research Fellowship under Grant No. 1122374. We also would like to thank Sofiia Dubova for her help in translating [1]} and Michel Goemans for pointing to the closely related, English-language work of [2]}.


Contextual Bandits
In this section, we apply prop:kpieceregression and the approach of [3]} to the setting of contextual bandits with contexts drawn from a smooth distribution, considered in [4]}. Unlike in that work, however, we will realize regret bounds achievable by an oracle-efficient algorithm that are polynomially improved both in the horizon and the number of actions in the particular case of noiseless rewards that are piecewise linear.
We consider the following setting: the learner has access to the context set \(\mathcal {B}_1^d\)  and an action set \(\mathcal {A}\)  with \(\left| \mathcal {A} \right| = A < \infty \) . Let
\(\mathcal {G}_\mathcal {F}^{\mathcal {A}} = \left\lbrace \mathbf {g_f} = \left(\mathbf {g}_{\mathbf {f}}^a\right)_{a \in \mathcal {A}}| \mathbf {g}_{\mathbf {f}}^a \in \mathcal {G}_\mathcal {F}\right\rbrace \) 
where \(\mathcal {G}_\mathcal {F}\)  is as in prop:kpieceregression, be a class of functions \(\mathbf {g_f}: \mathcal {B}_1^d \times \mathcal {A}\rightarrow \mathbb {R}\) . Before the game begins, Nature selects some \(\ell ^\star \in \mathcal {G}_\mathcal {F}^\mathcal {A}\)  unknown to the learner. At each time \(t\) , Nature draws \(x_t\)  from a \(\sigma \) -smooth distribution on \(\mathcal {B}_1^d\) ; the learner then chooses \(a_t \in \mathcal {A}\) , observes \(\ell ^\star (x_t, a_t)\)  and suffers the same loss. Given \(\ell ^\star \in \mathcal {G}_\mathcal {F}^\mathcal {A}\) , it is clear that the best policy, given a context is greedy:
\(\pi _{\ell ^\star }(x) = \operatornamewithlimits{argmin}_{a \in \mathcal {A}} \ell ^\star (x, a).\) 
The goal of the learner is to minimize regret, \(\operatorname{Reg}_T\) , to the optimal policy \(\pi _{\ell ^\star }\) . The primary difference between our setting and that of [3]}, [4]}, other than the fact that we are considering a particular function class \(\mathcal {G}_\mathcal {F}^\mathcal {A}\) , is that our losses are noiseless, while the prior works allow for some noise that is mean zero conditional on the history. We have the following regret bound:
Corollary 13 
Suppose that we are in the contextual bandit setting outlined above with \(\mathcal {G}_\mathcal {F}\)  from (REF ) and \(\mathcal {X}\times \mathcal {A}\)  identified with some subset of \(\mathcal {B}_1^d\) . Then there is an oracle-efficient algorithm that, for all \(T\) , with probability at least \(1 - \delta \) , achieves
\(\operatorname{Reg}_T \le 80 \cdot A\sqrt{ T \left(K^2 d \log (d) + K^2 \log \left(ATK/(\sigma \delta )\right) \right)} + 8 \cdot \sqrt{A T \log \left(4/ \delta \right)}.\) 

We prove prop:conbandits in app:conbandits using the reduction of [3]} and prop:kpieceregression. Note that, in contradistinction to the corresponding bound proved as [4]}, we achieve the optimal \(\sqrt{T}\)  regret, albeit with stronger assumptions on the setting.
Proof of Corollary  REF
In this section, we prove prop:conbandits by applying the black box reduction of [3]} to our prop:kpieceregression. The key lemma is as follows:
[!t]
[1]
Init: \(A\)  instances of the Piecewise Regressor (alg:generalreg) \(\mathbf {\mathsf {regressor}}(a)\)  for \(a \in \mathcal {A}\) , learning rate \(\gamma > 0\) , exploration parameter \(\mu > 0\) .
each time \(t= 1,2,\dots \) 
recieve  \(x_t\) 
each action \(a \in \mathcal {A}\) 
 predict \(\hat{y}_t(a) = \mathbf {\mathsf {regressor}}(a)\mathbf {\mathsf {.predict}}(x_t)\)  blue!70!black% Prediction step of alg:generalreg
Assign \(b_t \leftarrow \operatornamewithlimits{argmin}_{a \in \mathcal {A}} \hat{y}_t(a)\) 
each \(a \ne b_t\) 
 Assign
\(p_{t,a} \leftarrow \frac{1}{\mu + \gamma (\hat{y}_t(a) - \hat{y}_t(b_t))} \) 

Assign
\(p_{t,b_t} \leftarrow 1 - \sum _{a \ne b_t} p_{t,a} \) 

 sample \(a_t \sim p_t\)  and play \(a_t\) 
 observe \(\ell _t(a_t)\) 
 update \(\mathbf {\mathsf {regressor}}(a)\mathbf {\mathsf {.update}}(x_t, a_t, \ell _t(a_t))\)  blue!70!black% Update step of alg:generalreg
Inverse Gap Weighting [3]} with Piecewise Regression
Lemma 14 
Suppose that we are in the setting of prop:conbandits and that we predict \(\hat{y}_t(a)\)  and sample \(a_t\)  according to alg:igw. Then, for all \(T\) , with probability at least \(1 - \delta \) , we have
\(\sum _{t = 1}^T \mathbb {I}[\hat{y}_t(a_t) \ne \ell _t(a_t)] \le A\left(136 K^2 d \log (d) + 91 K^2 \log \left(\frac{4 A T^2 K^2}{\sigma \delta }\right) + K^2 (\ell + 1)\right)\) 

We begin by noting that
\(\sum _{t =1}^T \mathbb {I}[\hat{y}_t(a_t) \ne \ell _t(a_t)] = \sum _{a \in \mathcal {A}} \sum _{t = 1}^T \mathbb {I}[\hat{y}_t(a) \ne \ell _t(a)] \mathbb {I}[a_t = a]\) 
let
\(\mathcal {U}= \left\lbrace \text{for all } 1 \le t \le T \text{ and } a \in \mathcal {A}\text{ if } p_{t,a} \le \frac{\delta }{2 A T} \text{ then } a_t \ne a\right\rbrace \) 
A union bound implies that \(\mathbb {P}(\mathcal {U}) \ge 1 - \frac{\delta }{2}\) . Restricting to \(\mathcal {U}\) , we note that for any \(B \subset \mathcal {B}_1^d\)  measurable,
\(\mathbb {P}_t\left(x_t \in B | a_t = a\right) \le \frac{\mathbb {P}_t(x_t \in B)}{p_{t, a_t}} \le \frac{2 A T \mu _d(B)}{\sigma \delta }\) 

thus after restricting to \(\mathcal {U}\) , the distribution of \(x_t\)  conditioned on \(a_t = a\)  is \(\left(\frac{\delta \sigma }{2 A T}\right)\) -smooth with respect to \(\mu _d\) . Thus for each \(a\) , we may apply the regret bound from prop:kpieceregression and, summing over \(a \in \mathcal {A}\)  concludes the proof.

We can now prove prop:conbandits:
[Proof of prop:conbandits]
Note that by Lipschitzness and boundedness, twice the mistake bound is larger than the square loss regret considered in [3]}. Applying [3]} concludes the proof.

Preliminaries
In this section, we provide some key definitions and results that come up in our analysis. We divide the section by theme, with the first part collection results on probability and concentration, the second part on geometric measure theory, and the third on convex geometry.
Probability and Concentration
We begin by stating the foundation of our regret bounds.
Lemma 15 (Ville's Inequality [13]}) 
Let \({F}_t\)  denote a filtration and suppose that the sequence of random variables \(A_t\)  is a supermartingale with respect to \({F}_t\) . Suppose that
\(\mathbb {P}\left(A_t > 0 \text{ for all } t > 0\right) = 1.\) 
Then for any \(x > 0\) , the following inequality holds:
\(\mathbb {P}\left(\sup _{t > 0} A_t \ge x \right) \le \frac{\mathbb {E}\left[A_0\right]}{x}.\) 

We will also require a standard Chernoff bound.
Lemma 16 (Chernoff Bound)  Let \(X_1,\dots ,X_t\)  be a sequence of binary random variables such that \(\operatorname{\mathbb {E}}[X_i \mid X_{1},\dots ,X_{i-1}] \ge \eta \) . Then,
\(\mathbb {P}\left[\sum _{i=1}^t X_i \le t\eta /2\right]\le \exp (-t\eta /8).\) 

Finally, we will clear up any confusion about which distribution is smooth: that of contexts \(x_t\)  or that of samples \((x_t, y_t)\) .
Lemma 17 Suppose that \(x \sim p\)  and \((x, y) \sim \widetilde{p}\)  where \(p, \widetilde{p}\)  are distributions. Suppose that \(y \in \lbrace \pm 1\rbrace \) . Then if \(p\)  is \(\sigma \) -smooth with respect to \(\mu \)  then \(\widetilde{p}\)  is \(\left(\frac{\sigma }{2}\right)\) -smooth with respect to \(\mu \otimes \mathrm {Unif}(\lbrace \pm 1\rbrace )\) . Conversely, if \(\widetilde{p}\)  is \(\sigma \) -smooth with respect to \(\mu \otimes \mathrm {Unif}(\lbrace \pm 1\rbrace )\)  then \(p\)  is \(\sigma \) -smooth with respect to \(\mu \) .

The converse follows immediately from lem:smoothnesspushforward, proved in app:affine. To prove the first statement, note that any distribution on \(\lbrace \pm 1\rbrace \)  is \(\frac{1}{2}\) -smooth with respect to \(\mathrm {Unif}(\lbrace \pm 1\rbrace )\) . Thus, decomposing \(\widetilde{p}(x,y) = p(x) \cdot \widetilde{p}(y | x)\)  concludes the proof.

Geometric Measure Theory
The key definition is that of Hausdorff measure, which formally generalizes our intuitive notion of volume and surface area.
Definition 18 (Hausdorff Measure [14]}) 
Let \(\mathcal {X}\)  be a metric space. For any \(k \in \mathbb {R}_+\) , we define the \(k\) -dimensional Hausdorff measure of a set \(A \subset \mathcal {X}\)  to be
\(2^{-k} \omega _k \lim _{\varepsilon \downarrow 0} \operatorname{vol}_k^\varepsilon (A),\) 
where
\(\operatorname{vol}_k^\varepsilon (A) := \inf \left\lbrace \sum _{i = 1}^\infty (\operatorname{diam}U_i)^k \bigg | A \subset \bigcup _{i = 1}^\infty U_i \text{ \emph {and} } \operatorname{diam}U_i < \varepsilon \right\rbrace \) 
and \(\operatorname{diam}U_i\)  is the diameter of the set \(U_i\) , i.e., the maximal distance between any two points contained in \(U_i\) . We define the Hausdorff dimension \(\dim (A) = \inf \lbrace k > 0 | \operatorname{vol}_k(A) > 0\rbrace \) . As is common, when we integrate with respect to the Hausdorff measure, we denote the measure in the integral as \(d \mathcal {H}^k\)  instead of \(d \operatorname{vol}_k\) .

Note that when \(\mathcal {X}= \mathbb {R}^d\)  then \(\operatorname{vol}_d\)  exactly coincides with the Lebesgue measure [14]}. The following is an immediate consequence of the definition:
Lemma 19 For a given set \(A \subset \mathcal {X}\) , let \(N(A, \varepsilon )\)  denote the minimal number of balls of radius \(\varepsilon \)  required to cover \(A\) . Then
\(\operatorname{vol}_k(A) \le \omega _k \varepsilon ^k N(A, \varepsilon ).\) 

It is immediate from the definition that \(\operatorname{vol}_k^\varepsilon \)  is monotone nonincreasing as \(\varepsilon \downarrow 0\) . The result follows by letting \(U_i\)  be the set of balls of radius \(\varepsilon \)  covering \(A\) .

We also use the co-area formula:
Theorem 20 (Co-area Formula [14]})  
Let \(\phi : \mathbb {R}^n \rightarrow \mathbb {R}^m\)  be a Lipschitz function with \(n \ge m\) . Then, for \(A \subset \mathbb {R}^m\) ,
\(\int _{\phi ^{-1}(A)} \sqrt{\det (D\phi (x) D \phi (x)^T)} d \mathcal {H}^m(x) = \int _{A} \operatorname{vol}_{n - m}(\phi ^{-1}(y)) d \mathcal {H}^m(y).\) 

This in turn implies the projection formula:
Corollary 21 ([14]}) 
Let \(\phi : \mathcal {X}\rightarrow \mathcal {Y}\)  denote a 1-Lipchitz map between \(m\) -dimensional sets \(\mathcal {X}, \mathcal {Y}\) . Then \(\operatorname{vol}_m(\phi (\mathcal {X})) \le \operatorname{vol}_m(\mathcal {X})\) .

By thm:coarea,
\(\operatorname{vol}_m(\phi (\mathcal {X})) = \int _{\phi (\mathcal {X})} d \mathcal {H}^m(y) \le \frac{\sup _{x} \sqrt{\det (D\phi (x) D \phi (x)^T)}}{\inf _y \operatorname{vol}_0(\phi ^{-1}(y))} \int _{\mathcal {X}} d \mathcal {H}^m(x) \le \operatorname{vol}_m(\mathcal {X}),\) 

where the last inequality holds because the Lipschitz assumption bounds the largest singular value of \(D \phi \)  and for any \(y \in \phi (\mathcal {X})\) , there is at least one point \(x \in \phi ^{-1}(y)\) .

Convex Geometry
We first define a polytope:
Definition 22 We say that a set \(A \subset \mathbb {R}^d\)  is a polytope if it is the intersection of a finite number of halfspaces. If \(A\)  is the intersection of \(K\)  halfspaces, we say that it has \(K\)  faces.

We now define an ellipsoid:
Definition 23 Let \(A \in \mathbb {R}^{d\times d}\)  be a positive definite matrix and let \(a \in \mathbb {R}^d\)  be a point. We define an ellipsoid to be
\(\mathcal {E}(A, a) = \left\lbrace w \in \mathbb {R}^d | (w - a)^T A^{-1} (w - a) \le 1 \right\rbrace .\) 
Note that the volume of an ellipsoid is given by \(\operatorname{vol}_d(\mathcal {E}(A, a)) = \omega _d \sqrt{\det (A)}\) .

We now define the John ellipsoid associated with a convex body:
Theorem 24 (John Ellipsoid [18]}, [19]}) 
Let \(A \subset \mathbb {R}^d\)  be a convex body, i.e., a convex set with nonempty interior. Then there is a unique ellispoid \(\mathcal {E}_A\)  that has maximal volume subject to the condition that the ellipsoid is contained in \(A\) . Furthermore, \(A \subset d \cdot \mathcal {E}_A\) .

We require the following general fact about ellipsoids:
Lemma 25 (Corollary 15 from [20]})  
Suppose \(\mathcal {E}= \mathcal {E}(A, a)\)  is an ellipsoid and \(A\)  has eigenvalues given by \(q = (q_1, \dots , q_d)\) . Then,
\(\operatorname{vol}_{d-1}(\partial \mathcal {E}) \le \left|\left| q \right|\right| \cdot \sqrt{d} \cdot \operatorname{vol}_d(\mathcal {E}).\) 

Finally, we have the following result about cutting planes through the center of the John ellipsoid:
Lemma 26 ([1]}, [2]}) 
Let \(A \subset \mathbb {R}^d\)  be a polytope with John ellipsoid \(\mathcal {E}_A\)  with center \(a\) . Let \(A^{\prime }\)  be the intersection of \(A\)  and a halfspace going through \(a\) , i.e., there is some \(w \in \mathbb {R}^d\)  such that
\(A^{\prime } = A \cap \left\lbrace w \in \mathbb {R}^d | \left\langle w , x \right\rangle  \ge \left\langle a , x \right\rangle  \right\rbrace .\) 
If \(\mathcal {E}_{A^{\prime }}\)  is the John ellipsoid of \(A^{\prime }\) , then
\(\operatorname{vol}_d(\mathcal {E}_{A^{\prime }}) \le \frac{8}{9} \operatorname{vol}_d(\mathcal {E}_A).\) 


Technical Workhorses
This appendix proves the technical workhorses, the abstract decay lemma (lem:masterreduction), and the main geometric lemma, lem:orthogonality.
Proof of Lemma REF : The Abstract Decay Lemma
We prove a slightly more general form of the lemma, with a weaker assumption on the sequence of \(z\) :
Lemma 27 
Suppose that a sequence \((\ell _t,z_t) \)  satisfies \((R, c)\) -geometric decay with respect to some a \(\mu \)  on \(\mathcal {Z}\) , and define a sequence of stopping times \(t_m\)  where \(t_m = t\)  if \(t\)  is the \(m^{th}\)  time that \(\ell _s(z_s) = 1\) . Let \(m_t\)  denote the maximal \(m\)  such that \(t_m < t\)  and thus \(t_{m_t}\)  is last time before \(t\)  that \(\ell _s = 1\) . Suppose that for all \(t\) , the distribution of \(z_t\)  conditional on \(t_{m_t}\)  is \(\sigma \) -smooth with respect to \(\mu \) . Then for all \(T \in \mathbb {N}\) , with probability at least \(1 - \delta \) ,
\(\sum _{t=1}^T \ell _t(z_t) \le 4 \frac{\log \left(\frac{2 T R}{\sigma \delta }\right)}{\log \left(\frac{1}{c}\right)} + \frac{e - 1}{1 - \@root  \of {c}}.\) 

Fix a sequence of positive integers \(h_k\)  for \(k \in \mathbb {N}\) , whose values we tune at the end of the proof. Let \(\tau _0 = 0\)  and for all \(m > 0\) , let
\(\tau _m &= \tau _{m-1} + \inf \left\lbrace k > 0 \bigg | \sum _{t = \tau _{m-1} + (k-1)h_m}^{\tau _{m-1} + k h_m } \ell _t(z_t) = 1 \right\rbrace \\&= \tau _{m-1} + \inf \left\lbrace k > 0 \bigg | \exists t \in \tau _{m-1} + [(k-1)h_m, k h_m-1] \text{ s.t. } \ell _t(z_t) = 1 \right\rbrace .\) 

Furthermore, let \(T(m) = \sum _{k = 1}^{m} (\tau _k - \tau _{k-1}) h_k\)  and
\(t_m = \inf \left\lbrace t > T(m-1) | \ell _t(z_t) = 1\right\rbrace .\) 
In words, we consider epochs of length \(h_m\) , whose length can change every time we make a mistake in an epoch. We have \(T(m)\)  the time of the \(m^{th}\)  change of epoch and \(\tau _m\)  the number of epochs of length \(h_m\)  we have to go before we make a mistake; we also have \(t_m\)  is the time of the first mistake after the \(m^{th}\)  change of epoch size. Let
\(A_m = \sum _{s = t_m + 1}^{T(m) - 1} \ell _s(z_s).\) 
be the number of mistakes in a given epoch other than the first mistake. Let \(\pi _m = \min \left(\frac{R_m}{\sigma }, 1\right)\) , where we abbreviate \(R_m = R_{t_m}\) . We first claim that with probability at least \(1 - \delta \) , for all \(m\)  it holds that:
\(A_m \le \log \left(\frac{1}{\delta }\right) + (e-1) \sum _{k = 1}^m \pi _k (h_k - 1) .\) 

To see this, let
\(B_m^\lambda = \exp \left(\lambda A_m - \left(e^\lambda - 1\right)\sum _{k = 1}^m \pi _k h_k \right).\) 
We show that \(B_m^\lambda \)  is a supermartingale for all \(\lambda > 0\) . To see this, we have
\(\mathbb {E}\left[B_m^\lambda | B_{m-1}^\lambda \right] = B_{m-1}^\lambda \mathbb {E}\left[\exp \left(\lambda \sum _{s = t_m + 1}^{T(m) - 1} \mathbb {I}[\hat{y}_s \ne y_s] -\left(e^\lambda - 1\right) \pi _m (h_m - 1)\right) \bigg | B_{m-1}^\lambda \right] \le B_{m-1}^\lambda ,\) 

where the inequality follows because the conditional probability of a mistake for \(t_m + 1 \le T(m) - 1 \le \pi _m\)  by the assumption of smoothness conditional on a sub-sigma algebra of that generated by \(t_{m-1}\)  and realizability and \(T(m) - 1 - (t_m + 1) \le h_m - 1\)  by construction. Thus we may apply Ville's inequality from lem:ville and recover (REF ).
Claim 1  With probability at least \(1 - \delta \) , it holds for all \(m\)  that
\(\tau _m - \tau _{m-1} \ge \max \left(1, \log \left(\frac{\delta }{\pi _m h_m T}\right)\right). \) 

[Proof of claim:tauseparataion]
For any \(\tau _{m-1} + (k-1) h_m \le t < \tau _{m-1} + k h_m\) , smoothness implies
\(\mathbb {P}\left(\ell _t(z_t) = 1 | \ell _s(z_s) = 0 \text{ for all } s < t\right) \le h_m \pi _m.\) 
where we note that the event that \(\ell _s(z_s) = 0\)  for \(s < t\)  is contained in the sigma-algebra generated by \(t_{m_t}\) . A union bound then implies that
\(\mathbb {P}\left[ \exists t \in \tau _{m-1} + [(k-1)h_m,~k h_m) \text{ s.t. } \ell _t(z_t) = 1 \bigg {|} \ell _s(z_s) = 0, \forall s \in [\tau _{m-1},(k-1)h_m)\right] \le h_m \pi _m.\) 

Hence, letting \(X_m\)  be a random variable distributed geometrically with parameter \(\widetilde{\pi }_m = \min (h_m \pi _m, 1)\) , \(\tau _{m} - \tau _{m-1}\)  stochastically dominates \(X_m\) . Thus, for any \(\lambda < - \log (1 - \pi _m)\) ,
\(\mathbb {E}\left[e^{\lambda (\tau _{m} - \tau _{m-1})}\right] \le \mathbb {E}\left[e^{\lambda X_m}\right] = \frac{\widetilde{\pi _m} e^\lambda }{1 - (1 - \widetilde{\pi _m})e^\lambda }.\) 
We further note that
\(\log \left(1 - (1 - \widetilde{\pi }_m)e^{-1}\right) &\ge 1 - \frac{1}{1 - (1 - \widetilde{\pi }_m)e^{-1}} = - \frac{(1 - \widetilde{\pi }_m)e^{-1}}{1 - (1 - \widetilde{\pi }_m)e^{-1}} \\&\ge - \frac{e^{-1}}{1 - e^{-1}}.\) 

Thus, setting \(\lambda = -1\) , we see that with probability at least \(\frac{\delta }{T}\) ,
\(\tau _m - \tau _{m-1} \ge 1 + \log \left(\frac{1}{ \widetilde{\pi _m}}\right) -\log \left(\frac{T}{\delta }\right) - \frac{e^{-1}}{1 - e^{-1}} \ge \log \left(\frac{\delta }{h \pi _m T}\right).\) 

Because \(\tau _m - \tau _{m-1} > 0\)  by construction, we may then take a union bound to conclude the proof of the claim.
Now we note that
\(T \ge T(m) = \sum _{k = 1}^m (\tau _k - \tau _{k-1}) h_k\) 
and, further, that if \(m_T\)  is the maximal \(m\)  such that the preceding display holds,
\(\operatorname{Reg}_T \le m_T + A_{m_T}.\) 
Thus, combining (REF ) and (REF ), along with the fact that \(\pi _k \le c^k R_0 / \sigma \) , with probability at least \(1 - 2 \delta \) , we have
\(T &\ge \sum _{k = 1}^{m_T} \log \left(\frac{\sigma \delta }{c^k R_0 h_k T}\right) h_k \\\operatorname{Reg}_T &\le m_T + \log \left(\frac{1}{\delta }\right) + (e - 1) \sum _{k =1}^m c^k \frac{R_0}{\sigma }(h_k - 1) \) 

Now, let \(h_k = 1\)  for \(k \le 2\log \left(\frac{ T R_0}{\sigma \delta }\right) / \log \left(\frac{1}{c}\right)\)  and let \(h_k = c^{- \frac{k}{2}}\)  otherwise. Then we see that if (REF ) and () hold, then
\(m_T \le 2\frac{\log T}{\log \left(\frac{1}{c}\right)} + \frac{2\log \left(\frac{ T R_0}{\sigma \delta }\right)}{\log \left(\frac{1}{c}\right)} \le - 4 \frac{\log \left(\frac{T R_0}{\sigma \delta }\right)}{\log c},\) 
and
\(\sum _{k = 1}^m c^k \frac{R_0}{\sigma }(h_k - 1) \le \sum _{j = 0}^\infty c^{\frac{j}{2}} = \frac{1}{1 - \sqrt{c}}.\) 
Thus we see that with probability at least \(1 - \delta \) .
\(\operatorname{Reg}_T \le 4 \frac{\log \left(\frac{2T R_0}{\sigma \delta }\right)}{\log \left(\frac{1}{c}\right)} + \frac{e - 1}{1 - \@root  \of {c}}.\) 
which proves the result.

We note that lem:masterreduction follows immediately because \(t_{m_t} < t\)  almost surely and so the sigma algebra generated by \(t_{m_t}\)  is contained in that generated by the history up to \(t-1\)  and so the smoothness assumption of lem:masterreduction implies that of lem:generalizedmasterreduction.

Proof of Lemma REF : The Key Geometric Lemma
We begin by proving the following technical geometric lemma, which, for simplicity, considers subsets of the sphere, rather than of the ball. This ultimately suffices due to positive homogeneity of linear classifiers.
Lemma 28 
Let \(\hat{\mathcal {F}}\subset S^{d-1}\)  be a measurable subset of the \((d-1)\) -dimensional sphere imbedded in \(\mathbb {R}^d\) . Let \(D(\hat{\mathcal {F}})\)  denote the set of points in \(S^{d-1}\)  orthogonal to at least one point in \(\hat{\mathcal {F}}\) , i.e.,
\(D(\hat{\mathcal {F}}) = \left\lbrace x \in S^{d-1} | \text{for some } w \in \hat{\mathcal {F}}, \quad \left\langle w , x \right\rangle  = 0 \right\rbrace .\) 
Then, if \(\operatorname{vol}_{k}\)  is the \(k\) -dimensional Hausdorff measure on the sphere, we have
\(\operatorname{vol}_{d-1}(D(\hat{\mathcal {F}})) \le 2 \cdot 4^{d-1} \operatorname{vol}_{d-1}(\hat{\mathcal {F}}) + 4^{d + 1} \operatorname{vol}_{d-2}(\partial \hat{\mathcal {F}}).\) 

For a given set \(A \subset S^{d-1}\) , denote by \(T(A, \varepsilon )\)  the “tube” of radius \(\varepsilon \)  around \(A\) , i.e., the set of points in \(S^{d-1}\)  with distance at most \(\varepsilon \)  from a point in \(A\) .
Note that for any fixed point \(w \in \hat{\mathcal {F}}\) , we have \(D(w)\)  is just the \((d-2)\) -sphere formed by intersection the linear space orthogonal to \(w\)  with \(S^{d-1}\) . If \(\hat{B}_\varepsilon (w)\)  denotes the \(\varepsilon \) -ball around \(w\)  in \(S^{d-1}\) , then we claim that \(D(\hat{B}_\varepsilon (w)) \subset T(D(w), \varepsilon )\) . Indeed, suppose that \(v \in \hat{B}_\varepsilon (w)\)  so that \(\left\langle w^{\prime } , v \right\rangle  = 0\)  for some \(w^{\prime } \in \hat{B}_\varepsilon (w)\) . Let \(\alpha \)  be a member of the orthogonal group such that \(\alpha w^{\prime } = v\)  and \(\left\langle \alpha w , w \right\rangle  = 0\) . Then \(\left\langle v + \alpha (w - w^{\prime }) , w \right\rangle  = 0\)  and \(\left|\left| \alpha (w - w^{\prime }) \right|\right| = \left|\left| w - w^{\prime } \right|\right| \le \varepsilon \) , proving the claim.
Let \(N(\widehat{\mathcal {F}}, \varepsilon )\)  denote the minimum size of an \(\varepsilon \) -net of \(\mathcal {F}\)  and let \(P(\widehat{\mathcal {F}}, \varepsilon )\)  denote the maximum size of an \(\varepsilon \) -packing. By abuse of notation, we will also use \(N(\widehat{\mathcal {F}}, \varepsilon )\)  to denote the minimal \(\varepsilon \) -net itself. The fact that \(D(\widehat{B}_\varepsilon (w)) \subset T(D(w), \varepsilon )\)  implies that
\(\operatorname{vol}_{d-1}(D(\hat{\mathcal {F}})) \le \operatorname{vol}_{d-1}\left(\bigcup _{w \in N(\mathcal {F}, \varepsilon )} T(D(w), \varepsilon )\right) \le N(\hat{\mathcal {F}}, \varepsilon ) \cdot \operatorname{vol}_{d-1}(T(D(w), \varepsilon ))\) 
By packing, covering duality, we have
\(N(\widehat{\mathcal {F}}, \varepsilon ) \le P\left(\widehat{\mathcal {F}}, \frac{\varepsilon }{2}\right) \le \frac{2^{d-1} \operatorname{vol}_{d-1}(T(\widehat{\mathcal {F}}, \varepsilon ))}{\operatorname{vol}_{d-1}(\widehat{B}_\varepsilon (w))}\) 
Now, we may apply [23]}, the generalization of Steiner's formula to submanifolds of a sphere, to get
\(\operatorname{vol}_{d-1}(T(\widehat{\mathcal {F}}, \varepsilon )) \le \operatorname{vol}_{d-1}(\widehat{\mathcal {F}}) + \operatorname{vol}_{d-2}(\partial \widehat{\mathcal {F}}) \left(2^{d-1} \varepsilon + 2^{d-1} \varepsilon ^d \right)\) 
Putting this together, we have
\(\operatorname{vol}_{d-1}(D(\hat{\mathcal {F}})) \le 2^{d-1} \frac{ \operatorname{vol}_{d-1}(T(D(w), \varepsilon ))}{ \operatorname{vol}_{d-1}(B_\varepsilon (w)))} \left(\operatorname{vol}_{d-1}(\hat{\mathcal {F}}) + \operatorname{vol}_{d-2}(\partial \hat{\mathcal {F}}) \left(2^{d-1} \varepsilon + 2^{d-1} \varepsilon ^d\right)\right).\) 
Now we may apply Weyl's tube formula [24]} (see [23]}, [26]} for a clear exposition on the topic) to \(S^{d-2}\)  imbedded as the equator of \(S^{d-1}\)  to get that for any \(\varepsilon < 1\) ,
\(\frac{\operatorname{vol}_{d-1}(T(D(w), \varepsilon ))}{\operatorname{vol}_{d-1}(\widehat{B}_\varepsilon (w))} \le \frac{2 \omega _{d-1} \left((1 + \varepsilon )^{d-1} - (1 - \varepsilon )^{d-1}\right)}{\varepsilon ^{d-1} \omega _{d-1}} =2 \frac{\left((1+\varepsilon )^{d-1} - (1 - \varepsilon )^{d-1}\right)}{\varepsilon ^{d-1}}.\) 
As \(\varepsilon \uparrow 1\) , the above expression tends to \(2^{d}\) . Putting everything together, we have
\(\operatorname{vol}_{d-1}(D(\hat{\mathcal {F}})) \le 2 \cdot 4^{d-1} \operatorname{vol}_{d-1}(\hat{\mathcal {F}}) + 2 \cdot 2^{2 d + 1} \operatorname{vol}_{d-2}(\partial \hat{\mathcal {F}}).\) 
as desired.

We now use the homogenity of the inner product to show that it suffices to consider the sphere:
Lemma 29 
Let \(\mathcal {F}\subset \mathcal {B}_1^d\)  and let \(\widehat{\mathcal {F}}_t\)  denote its projection to \(S^{d-1}\) . Suppose that \(\mathcal {F}\)  is such that
\(\mathcal {F}= \left\lbrace r \widehat{x} | 0\le r \le 1 \text{ and } \widehat{x} \in \widehat{\mathcal {F}}\right\rbrace .\) 
Then,
\(\frac{\operatorname{vol}_d(\mathcal {F})}{\operatorname{vol}_d(\mathcal {B}_1^d)} = \frac{\operatorname{vol}_{d-1}(\widehat{\mathcal {F}})}{\operatorname{vol}_{d-1}(S^{d-1})}.\) 

Let \(\widehat{\mathcal {F}}_r = r \widehat{\mathcal {F}}\) . Then we see from thm:coarea that \(\operatorname{vol}_{d-1}(\widehat{\mathcal {F}}_r) = r^{d-1} \operatorname{vol}_{d-1}(\widehat{\mathcal {F}})\) . Thus,
\(\operatorname{vol}_d(\mathcal {F}) = \int _0^1 \operatorname{vol}_{d-1}(\widehat{\mathcal {F}}_r) d r = \operatorname{vol}_{d-1}(\widehat{\mathcal {F}}) \int _0^1 r^{d - 1} d r.\) 
In particular, this holds for \(\mathcal {F}= \mathcal {B}_1^d\) . Thus, we have
\(\frac{\operatorname{vol}_d(\mathcal {F})}{\operatorname{vol}_d(\mathcal {B}_1^d)} &= \frac{\operatorname{vol}_{d-1}(\widehat{\mathcal {F}}) \int _0^1 r^{d - 1} d r}{\operatorname{vol}_{d-1}(\widehat{\mathcal {B}_1^d}) \int _0^1 r^{d - 1} d r} = \frac{\operatorname{vol}_{d-1}(\widehat{\mathcal {F}})}{\operatorname{vol}_{d-1}(S^{d-1})}.\) 

as desired.

We now put everything together:
[Proof of Lemma REF ]
Let \(\widehat{D}(\mathcal {F})\)  be the set of \(x \in D\)  such that \(\left|\left| x \right|\right| = 1\)  and let \(\widehat{\mathcal {F}}\)  be defined similarly. By the positive homogeneity of both \(D(\mathcal {F})\)  and \(\mathcal {F}\) , we have
\(\mu _d(D) &= \frac{\operatorname{vol}_d(D)}{\operatorname{vol}_d(\mathcal {B}_1)} = \frac{\operatorname{vol}_{d-1}(\widehat{D}(\mathcal {F}))}{\operatorname{vol}_{d-1}(\partial \mathcal {B}_1)} \\\mu _d(\mathcal {F}) &= \frac{\operatorname{vol}_d(\mathcal {F})}{\operatorname{vol}_d(\mathcal {B}_1)} = \frac{\operatorname{vol}_{d-1}(\widehat{\mathcal {F}})}{\operatorname{vol}_{d-1}(\partial \mathcal {B}_1)}\) 

where \(\operatorname{vol}_{d-1}(\cdot )\)  denotes the \((d-1)\) -dimensional Hausdorff measure. Thus, it suffices to compare \(\operatorname{vol}_{d-1}(\widehat{D}(\mathcal {F}))\)  with \(\operatorname{vol}_{d-1}(\widehat{\mathcal {F}})\) , which is the content of Lemma REF . The result follows.

Proofs From Section 
In this appendix, we provide proofs of prop:warmup and prop:warmuplowerbound.
Proof of Theorem  REF
In order to apply lem:masterreduction to prove prop:warmup, we need to show that the loss functions satisfy \((R, c)\) -geometric decay. We will show this for \(R = 4^{d + 1} d^{2d}\)  and \(c = \frac{8}{9}\)  using lem:orthogonality and some more convex geometry. We begin by proving the following characterization of the disagreement region, which will in turn allow us to apply lem:orthogonality:
Lemma 30 
Suppose that we are in the situation of prop:warmup. Then we have
\(D_t \subset \left\lbrace x \in \mathcal {B}_1^d | \left\langle w , x \right\rangle  = 0 \text{ for some } w \in \mathcal {F}_t\right\rbrace .\) 

Recall that the version space is defined as
\(\mathcal {F}_t = \left\lbrace w \in \mathcal {F}| \left\langle w , y_s x_s \right\rangle  \ge 0 \text{ for all } s < t \right\rbrace .\) 
If \(x \in D_t\) , then there are \(w, w^{\prime } \in \mathcal {F}_t\)  such that \(\operatorname{sign}(\left\langle w^{\prime } , x \right\rangle ) \ne \operatorname{sign}(\left\langle w^{\prime \prime } , x \right\rangle )\) . Consider the continuous function \(h(\lambda ) = \left\langle \lambda w^{\prime \prime } + (1 - \lambda ) w^{\prime } , x \right\rangle \) ; by the intermediate value theorem, there is some \(0 < \lambda ^\star < 1\)  and \(w = \lambda ^\star w^{\prime \prime } + (1 - \lambda ^\star ) w^{\prime }\)  such that \(\left\langle w , x \right\rangle  = 0\) . By convexity of \(\mathcal {F}_t\) , then \(w \in \mathcal {F}_t\)  and thus \(D_t\)  is contained within the set of points orthogonal to at least one point in \(\mathcal {F}_t\) .

With lem:inclusioninorthogonal in hand, we will be able to apply lem:orthogonality and it will suffice to control \(\mu (\mathcal {F}_t)\)  and \(\operatorname{vol}_{d-1}(\mathcal {F}_t)\) . The next result bounds these quantities in terms of their analogues in \(\mathcal {E}_t\) :
Lemma 31 
Let \(\mathcal {F}\subset \mathbb {R}^d\)  be a convex body with John ellipsoid \(\mathcal {E}\) . Then we have
\(\mu (\mathcal {F}) \le d^d \mu (\mathcal {E}) && \operatorname{vol}_{d-1}(\partial \mathcal {F}) \le 2 d^d \mu (\mathcal {E}).\) 

Note that it is a classical fact that \(\mathcal {F}\subset d \cdot \mathcal {E}\)  [18]} and thus \(\mu (\mathcal {F}) \le d^d \mu (\mathcal {E})\) . We thus only have to prove the second bound. To do this we first note that
\(\operatorname{vol}_{d-1}(\partial \mathcal {F}) \le \operatorname{vol}_{d-1}(\partial (d \cdot \mathcal {E})).\) 
To see that this is the case, consider \(\pi : \partial (d \cdot \mathcal {E}) \rightarrow \partial \mathcal {F}\)  be projection onto the convex \(\mathcal {F}\) . Then \(\pi \)  is a contraction and thus shrinks Hausdorff measure as per lem:projection. We now apply lem:rivin and note that because our ellipsoids are contained in the ball, \(\left|\left| q \right|\right| \le 2 \cdot \sqrt{d}\) , where \(q\)  is the vector of semi-axis lengths, i.e., the eigenvalues of the associated positive definite matrix. Thus we have
\(\operatorname{vol}_{d-1}(\partial (d \cdot \mathcal {E})) = d^{d-1} \operatorname{vol}_{d-1}(\partial \mathcal {E}) \le d^{d-1} \left(2 d \mu (\mathcal {E})\right),\) 
and the result follows.

We are now finally ready to apply the geometry that we have done so far to prove a slightly more general form of prop:warmup, which we will require to apply some of our reductions below.
Proposition 32 
Suppose we are in the situation of prop:warmup with the added complication that at any time \(t\) , the adversary can choose to censor round \(t\)  from the learner, so the learner does not observe \(y_t\)  and does not suffer loss at time \(t\) . We further allow \(x_t\)  to be drawn adversarially with the condition that if \(x_t\)  is drawn adversarially, then the adversary always censors time \(t\) . Then the conclusion of prop:warmup holds.

By lem:masterreduction, it suffices to show that with our choice of \(w_t\) , the sequence
\(\ell _t = \mathbb {I}\left[\operatorname{sign}(\left\langle w_t , x_t \right\rangle ) \ne y_t \text{ and round } t \text{ is not censored} \right]\) 
satisfies \((R, c)\)  geometric decay with respect to \(\mu \)  for come \(R, c\) . In particular, we need to find an \(R \ge \mu (D_1)\)  and a \(c < 1\)  such that if we make a mistake, then \(\mu (D_{t+1}) \le c \mu (D_t)\) . Note that if \(\ell _t = 1\)  then we must have \(x_t \in D_t\)  and \(y_t\)  is not censored. By Lemma REF  it suffices to control the size of the set of points orthogonal to at least one \(w \in \mathcal {F}_t\) ; by Lemma REF , it in turn suffices to control \(\mu (\mathcal {F}_t)\)  and \(\operatorname{vol}_{d-1}(\mathcal {F}_t)\) . Applying lem:surfacearea to the preceding logic, we have:
\(\mu (D_t) &\le 2 \cdot 4^{d-1} \mu (\mathcal {F}_t) + \frac{4^{d+1}}{\omega _d} \operatorname{vol}_{d-1}(\partial \mathcal {F}_t) \\&\le 2 \cdot 4^{d-1} \cdot d^d \mu (\mathcal {E}_t) + \frac{4^{d+1}}{\omega _d} \cdot 2 \cdot d^d \mu (\mathcal {E}_t) \\&\le 4^{d + 1} d^{2d} \mu (\mathcal {E}_t).\) 

As \(\mu (\mathcal {E}_t) \le 1\) , we may choose \(R = 4^{d+1} d^{2d}\)  and reduce to showing that every time we make a mistake, \(\mu (\mathcal {E}_{t+1}) \le c \mu (\mathcal {E}_t)\)  for some \(c\) .
Now, suppose that we make a mistake at time \(t\) , i.e., \(\left\langle w_t , y_t x_t \right\rangle  < 0\) . Then, we have
\(\mathcal {F}_{t+1} = \mathcal {F}_t \cap \left\lbrace w \in \mathcal {F}| \left\langle w , x_t y_t \right\rangle  > 0\right\rbrace  \subset \mathcal {F}_t \cap \left\lbrace w \in \mathcal {F}| \left\langle w , x_t y_t \right\rangle  \ge \left\langle w_t , x_t y_t \right\rangle \right\rbrace .\) 

by monotonicity. Thus \(\mathcal {F}_{t+1}\)  is a subset of the intersection of \(\mathcal {F}_t\)  and a halfspace through the center of \(\mathcal {E}_t\) . Thus, by lem:tarasov, \(\operatorname{vol}(\mathcal {E}_{t+1}) \le \frac{8}{9} \operatorname{vol}(\mathcal {E}_t)\) . Thus, we may choose \(c = \frac{8}{9}\)  and conclude the proof.

We remark that prop:warmup trivially follows from prop:warmupgeneralized by restricting the adversary to never censor a time \(t\) .

Proof of Theorem  REF
We construct separate adversaries which regret \(\mathbb {E}\left[ \operatorname{Reg}_T \right] \ge \Omega (d)\)  and \(\mathbb {E}\left[ \operatorname{Reg}_T \right] \ge \Omega \left( \log \left(\frac{T}{\sigma }\right) \right)\) . Randomizing between the two with probability one-half gives the lower bound.
We first note that any algorithm must experience \(\mathbb {E}\left[\operatorname{Reg}_T\right] \ge \frac{d+1}{2}\)  against some adversary; indeed, as a generic set of \(d + 1\)  points defines a hyperplane, a realizable adversary can choose \(y_t\)  as independent Rademachers for each \(1 \le d \le d + 1\)  and the learner will suffer expected regret \(\frac{d+1}{2}\) .
We now construct an adversary in one dimension that will force \(\mathbb {E}\left[\operatorname{Reg}_T\right] \ge \Omega \left(\log \left(\frac{T}{\sigma }\right)\right)\) ; by projecting onto some fixed direction, the higher dimensional case reduces to this setting. Thus, suppose that the \(x_t\)  are required to be sampled from a distribution that is \(\sigma \) -smooth with respect to the uniform measure on the unit interval. At each time \(t\) , let \(D_t\)  be the interval between the rightmost \(x_s\)  labelled \(-1\)  and the leftmost \(x_s\)  labelled 1, let \(R_t\)  be its length and \(w_t\)  its midpoint. Fix \(0 < \varepsilon < 1\)  to be tuned later and let
\(\widetilde{D}_t = \left\lbrace x \in D_t | \frac{1 - \varepsilon }{2} R_t \le \left| x - w_t \right| \le \frac{1}{2} R_t \right\rbrace \) 

be the set of points in the disagreement region close to its boundary. We let the adversary select the distribution that picks uniformly from \(\widetilde{D}_t\)  with probability \(\min \left(\frac{\mu (\widetilde{D}_t)}{\sigma }, 1\right)\)  and with remaining probability selects 0. If \(\left| x_t - w_t \right| \ge \frac{R_t}{2}\) , then \(y_t\)  is determined by realizability. Otherwise, let \(y_t\)  be an independent Rademacher random variable.
Let \(\pi _m = \min \left(\frac{\varepsilon R_m}{\sigma }, 1\right)\)  and \(t_m\)  be the \(m^{th}\)  time that \(x_t \in \widetilde{D}_t\) , we see that \(t_{m+1} - t_m\)  is geometrically distributed with parameter \(\pi _m\)  and thus
\(B_m^\lambda = \exp \left(\lambda t_m - m\lambda - \sum _{k = 1}^m \log \left(\frac{\pi _k}{1 - (1 - \pi _k) e^\lambda }\right)\right)\) 
is a supermartingale for \(\lambda < \min _{k \le m }\left(- \log (1 - \pi _k)\right) = - \log (1 - \pi _m)\) . Note that by construction, \(R_{m+1} \ge (1 - \varepsilon ) \mathcal {R}_m\)  and thus \(R_m \ge (1 - \varepsilon )^m\) . Setting \(\lambda = \pi _m \le - \log (1 - \pi _m)\)  and applying Ville's Inequality, lem:ville, we get that with probability at least \( 1- \delta \) , for all \(m\) ,
\(t_m \le m + \frac{\log \left(\frac{1}{\delta }\right)}{\pi _m} +\frac{1}{\pi _m} \sum _{k = 1}^m \log \left(\frac{\pi _k}{1 - (1 - \pi _k)e^{\pi _k}}\right).\) 

We now note that
\(\frac{1}{\pi _m} \log \left(\frac{\pi _k}{1 - (1 - \pi _k)e^{\pi _k}}\right) &\le \frac{1}{\pi _m}\left(\frac{\pi _m}{1 - (1 - \pi _m)e^{\pi _m}} - 1 \right) \\&= \frac{e^{\pi _m} - 1}{\pi _m} \frac{1 - \pi _m}{1 - (1 - \pi _m)e^{\pi _m}} \\&\le (e - 1) \frac{2}{\pi _m^2}\) 

using monotonicity, the fact that \(\pi _m \le 1\)  and the following computation:
\(1 - (1-x) e^x = 1 - (1-x) \sum _{k = 0}^\infty \frac{x^k}{k!} = \sum _{k =2}^\infty x^k \left(\frac{1}{(k-1)!} - \frac{1}{k!}\right) \ge \frac{x^2}{2}.\) 
Now, using the fact that \(\pi _m \ge \frac{\varepsilon }{\sigma }(1 - \varepsilon )^m\) , we have
\(t_m \le m + \frac{\sigma }{\varepsilon }(1 - \varepsilon )^{-m} \log \left(\frac{1}{\delta }\right) + 2 (e - 1)m\left(\frac{\varepsilon }{\sigma }\right)^{-2} (1 - \varepsilon )^{-2m} .\) 

Setting \(\varepsilon = 1 - e^{-1}\) , we see that there is some constant \(c > 0\)  such that with probability at least \(1 - \delta \) ,
\(t_m \le c \max \left(\sigma e^{m} \log \left(\frac{1}{\delta }\right), m \sigma ^2 e^{2m}\right).\) 

In particular, there is a universal constant \(C\)  such that if \(m = C \log \left(\frac{T}{\sigma \log \left(\frac{1}{\delta }\right)}\right)\) , then with probability at least \(1 - \delta \)  we have \(\operatorname{Reg}_T \ge m\)  because the probability of a mistake, given that \(x_t \in \widetilde{D}_t\)  is \(\frac{1}{2}\) . The result follows.

Lower bound against naive play. 
In this section, we show that it is necessary to choose the half-spaces \(w_t\)  intelligently in order to attain logarithmic-in-\(1/\sigma \)  regret.
Consider \(d = 1\) , so \(\mu _1\)  is the uniform measure on the interval \([-1,1]\) . We define \(\mathcal {F}^{\mathrm {thres}}:= \lbrace x \mapsto \operatorname{sign}(x -c) \rbrace \)  as the set of (monotone) threshold classifiers. Given a function class \(\mathcal {F}\) , we say that a learning strategy is consistent, if at each \(t \in [T]\) , it selects an \(f_t \in \mathcal {F}_{t}\)  in the version space \(\mathcal {F}_{t} := \lbrace f \in \mathcal {F}: f(x_s) = y_s, \quad 1 \le s \le t-1\rbrace \) . Define the left and right endpoints of the negative and positive regions
\(\tilde{x}_t := \max \left\lbrace -1,\max _{1 \le s \le t}\left\lbrace x_t : y_t = -1\right\rbrace \right\rbrace , \quad \bar{x}_t := \min \left\lbrace 1,\min _{1 \le s \le t}\left\lbrace x_t: y_t = 1\right\rbrace \right\rbrace .\) 

For a given \(\eta > 0\) , we consider the strategy
\(\hat{y}_t = {\left\lbrace \begin{array}{ll} \operatorname{sign}\left(x_t - \tilde{x}_{t-1} - \eta \right) & \tilde{x}_{t-1} + \eta < \bar{x}_t \\\operatorname{sign}\left(x_t - \frac{1}{2}\left(\tilde{x}_{t-1} + \bar{x}_{t-1}\right)\right) & \text{otherwise}.\end{array}\right.} \) 

This is consistent with \(\mathcal {F}^{\mathrm {thres}}\) , since the thresholds are always chosen strictly between \(\tilde{x}_{t-1}\)  and \(\bar{x}_{t-1}\) . However, the strategy is very naive, since it defaults to setting the threshold only slightly to the right of \(\tilde{x}_{t-1}\) . As a consequence, we show it suffers \(\Omega (1/\sigma )\)  regret when \(\eta \)  is small.
Proposition 33 Fix \(\eta > 0\) . For \(T \ge 1\)  and \(\sigma \in (1/T,1/4]\) , there exists an \(\mathcal {F}^{\mathrm {thres}}\) -realizable, \(\sigma \)  smooth adversary such that the strategy in eq:strategycons suffers expected regret linear in \(1/\sigma \)  for \(\eta \)  small:
\(\operatorname{\mathbb {E}}[\operatorname{Reg}_T] \ge \lfloor \frac{1}{\sigma } \rfloor \cdot \left(1-\frac{\eta }{2\sigma }\right).\) 

At each time \(1 \le t \le T_0 : = \lfloor 1/\sigma  \rfloor \) , the adversary selects
\(x_t = -1 + 2\sigma (t-1) + 2\sigma a_t, \quad a_t \sim \mathrm {Unif}([0,1]).\) 

For times \(t \ge T_0\) , the adversary selects \(x_t \sim \mathrm {Unif}([-1,1])\) . This adversary is clearly \(\sigma \)  smooth, satisfies \(x_t \in -1 + 2\sigma [t-1,t]\)  until \(T_0 \) , and then plays arbitrarily. Moreover, for \(\sigma \le 1/T\) , \(x_t \in [-1,1]\)  for all \(t\) .Fixing a ground-truth classifier \(f^{\star }(x) = \operatorname{sign}(x- 1)\) , we see \(y_s = f^{\star }(x_t) = -1\)  is realizable for all \(t\) .
Lastly, we analyze the regret of eq:strategycons; notice that under the above adversary, \(\bar{x}_t = 1\) , so we are always in the first case \(y_t = \operatorname{sign}(x_t - \max _{1 \le s \le t-1}x_s - \eta )\) . Then, for any \(t \le T_0\) ,
\(\mathbb {P}\left(\hat{y}_t = y_t | {F}_{t-1}\right) &= \mathbb {P}\left(x_t \le \eta + \max _{1 \le s \le t-1} x_s | {F}_{t-1}\right)\\&\le \mathbb {P}\left[x_t \le \eta + 2(t-1)\sigma - 1 \mid {F}_{t-1}\right]\\&= \mathbb {P}_{a_t \sim \mathrm {Unif}([0,1])}\left[-1 + 2\sigma (t-1) + 2\sigma a_t \le \eta + 2(t-1)\sigma - 1\right]\\&= \mathbb {P}_{a_t \sim \mathrm {Unif}([0,1])}\left[a_t \le \frac{\eta }{2\sigma }\right] = \frac{\eta }{2\sigma }.\) 

Hence,
\(\operatorname{\mathbb {E}}[\operatorname{Reg}_t] &= \sum _{t=1}^{T}\operatorname{\mathbb {E}}[\mathbb {P}[\hat{y}_t \ne y_t \mid {F}_{t-1}]]\\&\ge \sum _{t=1}^{T_0}\operatorname{\mathbb {E}}[\mathbb {P}[\hat{y}_t \ne y_t \mid {F}_{t-1}]]\\&= \sum _{t=1}^{T_0}1-\operatorname{\mathbb {E}}[\mathbb {P}[\hat{y}_t = y_t \mid {F}_{t-1}]]\\&\ge \sum _{t=1}^{T_0}\left(1-\frac{\eta }{2\sigma }\right) = T_0\left(1-\frac{\eta }{2\sigma }\right), \quad T_0 := \lfloor 1/\sigma  \rfloor .\) 

Proofs from Section 
Proof of Corollary  REF
The key technical result is contained in the following lemma, which says that we can lift a \(\sigma \) -smooth distribution on \(\mathcal {B}_1^d\)  to one on \(\mathcal {B}_1^{d+1}\)  and only lose a factor that is exponential in dimension. Because our regret guarantees are only logarithmic in \(\sigma \) , this will translate into a factor that is only linear in \(d\)  by reducing to the setting of prop:warmup. We have the following result:
Lemma 34 
There exist a probability kernel \(\mathcal {K}: \mathcal {B}_1^d \rightarrow \triangle (\mathcal {B}_1^{d+1})\)  that satisfies the following two properties: first,
\(\mathbb {P}_{\tilde{x} \sim \mathcal {K}(\cdot \mid x)}\left(\text{for all } \tilde{w} = (w,b) \in \mathbb {R}^d\times \mathbb {R}, ~\operatorname{sign}(\langle w,x \rangle + b) = \operatorname{sign}(\langle \tilde{w}, \tilde{x} \rangle )\right) = 1,\) 

and second, if \(p\)  is \(\sigma \) -smooth with respect to \(\mu _d\) , then \(\mathcal {K}\circ p\)  is \(\sigma ^{\prime }\) -smooth with respect to \(\mu _{d+1}\) , where \(\sigma ^{\prime } = \sigma /4^{d+2}\)  and \(\widetilde{x} \sim \mathcal {K}\circ p\)  if \(x \sim p\)  and \(\widetilde{x} \sim \mathcal {K}(\cdot | x)\) .

For general \(b\) , define \(\widetilde{w} := (w,b)\) , let \(\phi (x, z) = \frac{z(x, 1)}{4}\) , and let
\(\widetilde{x} = \phi (x_t, z_t) && z_t \sim \mathrm {Unif}(1,2) .\) 

Note that whenever \(x \in \mathcal {B}_1^d\) , \(\mathbb {P}[\widetilde{x}_t \in \mathcal {B}_1^{d+1} \mid x_t = x] = 1\) . Moreover,
\(\operatorname{sign}(\langle w,x_t \rangle + b) = \operatorname{sign}(\langle \widetilde{w},(x_t,1)\rangle ) = \operatorname{sign}(\langle \widetilde{w},z_t(x_t,1)\rangle ) = \operatorname{sign}(\langle \widetilde{w}, \widetilde{x}_t \rangle ).\) 

Since our proposed algorithm is a function only of the version space \(\mathcal {F}_t\) , and not the disagreement region, it follows that we can assume without loss of generality that the learner interacts with the distribution \(\widetilde{p}_t\)  induced by drawing \(x_t \sim p_t\) , \(z_t \sim \mathrm {Unif}[1,2]\) , and \(\widetilde{x}_t = \phi (x_t,z_t)\) .
To conclude, we must argue that if \(x_t \sim p_t\)  is \(\sigma \) -smooth with respect to the uniform measure \(\mu _d\)  on \(\mathcal {B}^d_1\) , then \(\tilde{x}_t \sim \tilde{p}_t\)  is \(\sigma ^{\prime }\) -smooth with respect to the uniform measure \(\mu _{d+1}\)  on \(\mathcal {B}^{d+1}_1\) , for an appropriate \(\sigma ^{\prime }\) .
Let \(\widetilde{\mu }_{d+1}\)  denote the density of \(\widetilde{x} = \phi (x,z)\) , where \(z \in \mathrm {Unif}[1,2]\)  when \(x \sim \mu _{d}\) . Then,
\(\frac{\mathrm {d}\widetilde{p}_t(\widetilde{x})}{\mathrm {d}\mu _{d+1}(\widetilde{x})} &= \frac{\mathrm {d}\tilde{p}_t(\tilde{x})}{\mathrm {d}\tilde{\mu }_{d+1}(\tilde{x})} \cdot \frac{\tilde{\mu }_{d+1}(\tilde{x})}{\mu _{d+1}(\tilde{x})}. \) 

To bound the first term, consider \(\phi ^{-1}\) , the inverse of \(\phi \)  from \(\mathcal {B}_{1/4}^d \times [\frac{1}{4},1/2] \rightarrow \mathcal {B}_{1/4}^d \times [1,2]\)  given by
\(\phi ^{-1}:\tilde{x} = (x,z) \mapsto ((x/z), 4z)\) 

Then, \(\tilde{p}_t\)  is the pushforward under \(\phi ^{-1}\)  of the measure \(p_t \otimes \mathrm {Unif}[\frac{1}{4},\frac{1}{2}]\) , and \(\tilde{\mu }_{d+1}\)  the pushforward of \(\mu _d \otimes \mathrm {Unif}[\frac{1}{4},\frac{1}{2}]\) . Thus, by lem:smoothnesspushforward, we have that \(\widetilde{p}_t\)  is \(\sigma \) -smooth with respect to \(\widetilde{\mu }_{d+1}\) .
Now, we compute \(\frac{\mathrm {d}\widetilde{\mu }_{d+1}(\widetilde{x})}{\mathrm {d}\mu _{d+1}(\widetilde{x})}\) . It suffices to show that for any set \(H \subset \mathcal {B}_{1/2}^d \times [\frac{1}{4},1/2]\) , we have
\(\widetilde{\mu }_{d+1}(H) \le C\mathrm {d}\mu _{d+1}(H),\) 

for some desirable constant \(C\) . Let \(J_{\phi ^{-1}}\)  denote the Jacobian of the map \(\phi ^{-1}: (x,u) \mapsto (x/z, 4z)\) . Then, \(J_{\phi ^{-1}}\)  is a triangular matrix with determinant \(4(1/z)^d\) . Thus, on \(H \subset \mathcal {B}_{1/2}^d \times [\frac{1}{4},1/2]\) , its determinant is at most \(|\det _{J_{\phi }}(x,z)| = 4^{d+1}\) . Hence,
\(\tilde{\mu }_{d+1}(H) &= \mathbb {P}_{(x,z) \sim \mathcal {B}_{1}^d \times \mathrm {Unif}[1,2]}[\phi (x,z) \in H]\\&= \mathbb {P}_{(x,z) \sim \mathcal {B}_{1}^d \times \mathrm {Unif}[1,2]}[(x,z) \in \phi ^{-1}(H) ]\\&= \frac{\int _{\phi ^{-1}(H)} \mathrm {d}x \mathrm {d}z}{\operatorname{vol}_{d+1}(\mathcal {B}_{1}^d \times \mathrm {Unif}[1,2])}\\&= \frac{\int _{H} |\det (J_{\phi ^{-1})(x,z)}| \mathrm {d}x \mathrm {d}z}{\operatorname{vol}_{d+1}(\mathcal {B}_{1}^d \times \mathrm {Unif}[1,2])}\\&\le \frac{ 4^{d+1}\operatorname{vol}(H) }{\operatorname{vol}_{d+1}(\mathcal {B}_{1}^d \times \mathrm {Unif}[1,2])}\\&=\mu _{d+1}(H) \cdot \frac{ 4^{d+1}\operatorname{vol}_{d+1}(\mathcal {B}_1^{d+1}) }{\operatorname{vol}_{d+1}(\mathcal {B}_{1}^d \times \mathrm {Unif}[1,2])}\\&=\mu _{d+1}(H) \cdot \frac{ 4^{d+1}\operatorname{vol}_{d+1}(\mathcal {B}_1^{d+1}) }{\operatorname{vol}_{d}(\mathcal {B}_{1}^d)}\\&= 4^{d+1}\frac{\sqrt{\pi }}{d+\frac{1}{2}} \le 4^{d+2}.\) 
Combining these computations with (REF ) yields
\(\frac{\mathrm {d}\tilde{p}_t(\tilde{x})}{\mathrm {d}\mu _{d+1}(\tilde{x})} &= \frac{\mathrm {d}\tilde{p}_t(\tilde{x})}{\mathrm {d}\tilde{\mu }_{d+1}(\tilde{x})} \cdot \frac{\tilde{\mu }_{d+1}(\tilde{x})}{\mu _{d+1}(\tilde{x})} \le \sigma ^{-1} 4^{d+2},\) 

which concludes the proof.
Lemma 35 
Suppose that \(f: \mathcal {X}\rightarrow \mathcal {Y}\)  is a measurable map and suppose that \(p,\mu \)  are measures on \(\mathcal {X}\)  and \(p\)  is \(\sigma \) -smooth with respect to \(\mu \) . Define the pushforward measure on \(\mathcal {Y}\)  by taking \(f_\star \mu (B) = \mu (f^{-1}(B))\)  for any measurable \(B \subset \mathcal {Y}\) . Then \(f_\star p\)  is \(\sigma \) -smooth with respect to \(f_\star \mu \) .

Let \(B \subset \mathcal {Y}\)  be measurable. Then
\(f_\star p(B) = p(f^{-1}(B)) \le \frac{\mu (f^{-1}(B))}{\sigma } \le \frac{f_\star \mu (B)}{\sigma }.\) 

As this holds for any \(B \subset \mathcal {Y}\) , the result follows.
[!t]
[1]
Initialize  \(\widetilde{\mathcal {W}}_1 = \mathcal {B}_1^{d+1}\) , \(\widetilde{w}_1 = \mathbf {e_1} \in \widetilde{\mathcal {W}}_1\) ,
\(t=1,2,\dots \) 
Recieve  \(x_t\) , draw \(z_t \sim \mathrm {Unif}(1,2)\) , and assign
\(\widetilde{x}_t \leftarrow \phi (x_t, z_t) = \frac{z_t (x_t, 1)}{4}\) 
predict
\(\hat{y}_t = \operatorname{sign}(\left\langle \widetilde{w}_t , \widetilde{x}_t \right\rangle ), \) 

Update \(\widetilde{\mathcal {W}}_{t+1} = \widetilde{\mathcal {W}}_t \cap \lbrace \widetilde{w} \in \mathcal {B}_1^{d+1}| \left\langle \widetilde{w} , \widetilde{x}_t y_t \right\rangle  \ge 0 \rbrace \) 
\(\hat{y}_t \ne y_t\)                                                           (blue!70!black% \(\mathbf {\mathsf {self}}.\mathbf {\mathsf {errorUpdate}}(x_t)\))
 \(\widetilde{w}_{t+1} \leftarrow \mathbf {\mathsf {JohnEllpsoidCenter}}(\widetilde{\mathcal {W}}_{t+1})\)
            blue!70!black% returns center of John Ellpsoid of given convex body

Binary Classification with Affine Thresholds


We now describe alg:affine. At each time \(t\) , we draw \(z_t \sim \mathrm {Unif}(1,2)\)  independently and form \(\widetilde{x}_t = \phi (x_t, z_t)\) , where \(\phi \)  is as in (REF ). We then run the classify and update subroutines of alg:warmup at each time step on the new data sequence \((\widetilde{x}_t, y_t)\) . We are now ready to prove prop:affinereduction:
[Proof of prop:affinereduction]
We use alg:affine to reduce the problem to the situation of prop:warmup. Indeed, by lem:affineconversaion, the data sequence \((\widetilde{x}_t, y_t)\)  satisfies the property that \(\widetilde{x}_t\)  is \(\left(4^{- d - 2} \sigma \right)\) -smooth with respect to \(\mu _{d+1}\)  and is realizable by the function class \(\mathcal {F}_{\mathrm {lin}}^{d+1}\) . The result then follows immediately from prop:warmup.

Proof of Theorem  REF
We now prove begin generalizing beyond linear function classes with prop:samedimensionfeatures. The key technical result shows that if \(\phi : \mathcal {B}_1^d \rightarrow \mathcal {B}_1^d\)  is well-behaved, then \(\phi _\star \mu _d\)  is \(\sigma \) -smooth with respect to \(\mu _d\) , which will then allow us to apply prop:warmup.
[!t]
[1]
Initialize  \(\widetilde{\mathcal {W}}_1 = \mathcal {B}_1^{d+1}\) , \(\widetilde{w}_1 = \mathbf {e_1} \in \mathcal {W}_1\) , \(\phi : \mathcal {B}_1^d \rightarrow \mathcal {B}_1^d\) 
\(t=1,2,\dots \) 
Recieve  \(x_t\) ,
predict
\(\hat{y}_t = \operatorname{sign}(\left\langle \widetilde{w}_t , \phi (x_t) \right\rangle ), \) 

Update \(\widetilde{\mathcal {W}}_{t+1} = \widetilde{\mathcal {W}}_t \cap \lbrace \widetilde{w} \in \mathcal {B}_1^{d+1}| \left\langle \widetilde{w} ,  \phi (x_t) y_t \right\rangle  \ge 0 \rbrace \) 
\(\hat{y}_t \ne y_t\)                                                           (blue!70!black% \(\mathbf {\mathsf {self}}.\mathbf {\mathsf {errorUpdate}}(x_t)\))
 \(\widetilde{w}_{t+1} \leftarrow \mathbf {\mathsf {JohnEllpsoidCenter}}(\widetilde{\mathcal {W}}_{t+1})\)
            blue!70!black% returns center of John Ellpsoid of given convex body

Binary Classification with Nonlinear Features
Lemma 36 
Suppose that \(p\)  is a measure on \(\mathcal {B}_1^d\)  that is \(\sigma \) -smooth with respect to \(\mu _d\)  and suppose that \(\phi : \mathcal {B}_1^d \rightarrow \mathcal {B}_1^d\)  is a function satisfying the following two properties:

There is some \(c > 0\)  such that \(\left| \det (D \phi (x)) \right| > c\)  for all \(x \in \mathcal {B}_1^d\) .

There is some \(N \in \mathbb {N}\)  such that for every \(x \in \mathcal {B}_1^d\) , it holds that \(\left| \phi ^{-1}(x) \right| \le N\) , where \(\phi ^{-1}(x) = \left\lbrace y \in \mathcal {B}_1^d | \phi (y) = x \right\rbrace \) .

Then, \(\phi _\star p\)  is \(\left(\frac{c}{N} \sigma \right)\) -smooth with respect to \(\mu _d\) .

By lem:smoothnesspushforward, we have that \(\phi _\star p\)  is \(\sigma \) -smooth with respect to \(\phi _\star \mu _d\) . Thus, as
\(\frac{\mathrm {d}\phi _\star p}{\mathrm {d}\mu _d} = \frac{\mathrm {d}\phi _\star p}{\mathrm {d}\phi _\star \mu _d} \cdot \frac{\mathrm {d}\phi _\star \mu _d}{\mu d}\) 
it suffices to bound the latter factor. By the area formula [14]}, we have for any \(B \subset \mathcal {B}_1^d\)  that
\(\phi _{\star }\mu _d(B) &= \int _{\phi ^{-1}(B)} \mathrm {d}\mu _d(x) \\&= \int _{\phi ^{-1}(B)} \frac{\left| \det (\mathrm {D}\phi (x)) \right|}{\left| \det (\mathrm {D}\phi (x)) \right|} \mathrm {d}\mu _d(x) \\&\le \frac{1}{c} \int _{\phi ^{-1}(B)} \left| \det (\mathrm {D}\phi (x)) \right| \mathrm {d}\mu _d(x) \\&= \frac{1}{c} \int _B \left| \phi ^{-1}(y) \right| \mathrm {d}\mu _d(y) \le \frac{N}{c} \mu _d(y)\) 

Thus we see that for any \(B\) ,
\(\frac{\phi _\star \mu _d(B)}{\mu _d(B)} \le \frac{N}{c}\) 
and so the result follows.

As a corollary, we generalize prop:warmup to adversaries that are now realizable to a class linear in some new set of features:
Corollary 37 
Let \(\phi \)  be a map as in lem:samedimensionfeatures and suppose that we are in the smoothed online learning setting with an adversary realizable with respecto to \(\mathcal {F}\circ \phi = \left\lbrace x \mapsto f(\phi (x)) | f \in \mathcal {F}\right\rbrace \) . If we run alg:samedim on the data \((\phi (x_t), y_t)\) , then for all \(T\) , with probability at least \(1 - \delta \) , it holds that
\(\operatorname{Reg}_T \le 136 d \log (d) + 34 \log \left(\frac{N}{c}\right) + 34 \log \left(\frac{T}{\sigma \delta }\right) + 56\) 

The statement follows immediately from applying prop:warmup to the data sequence \((\phi (x_t), y_t)\)  and using lem:samedimensionfeatures to bound the smoothness.

Finally, we prove the simpler result stated in sec:generalizations:
[Proof of prop:samedimensionfeatures]
By cor:samedimensionfeatures, it suffices to bound \(N\)  and \(c\)  in lem:samedimensionfeatures. Suppose that \(\phi (x) = (\phi _1(x_1), \dots , \phi _d(x_d))\)  as in the statement of the result. Then we see that \(\mathrm {D}\phi (x)\)  is diagonal with \(\phi _i^{\prime }(x_i)\)  as the \(i^{th}\)  element of the diagonal and thus
\(\det (\mathrm {D}\phi (x)) = \prod _{i = 1}^d \left| \phi _i^{\prime }(x_i) \right| \ge \alpha ^d\) 
where the final inequality follows from the assumption. Note that if \(\phi _i^{\prime } > 0\)  for all \(i\) , then \(\phi \)  is strictly increasing coordinate wise and thus we may take \(N = 1\) . The result follows.

Proof of Theorem  REF
In this section, we show that our techniques extend to polynomial decision boundaries. Morally, we proceed on similar lines as to the proof of prop:samedimensionfeatures outlined in the previous section, but there are a number of new technical subtleties that appear in this analysis that were not present before. The most salient difference between the maps considered above and that which is required for a polynomial decision boundary is that polynomial features require imbedding our problem into a higher dimensional space; while lem:smoothnesspushforward ensures that the pushforward of the law of each \(x_t\)  is smooth with respect to the pushforward of \(\mu _d\) , our analysis is very specific to the dominating measure being uniform on the ball, which can never happen if we are pushing \(\mu _d\)  forward into a higher dimensional space. In order to resolve this difficulty, we will present a reduction that allows us to combine multiple points into one `meta-point,' whose law will be smooth with respect to the uniform measure on the higher dimensional ball. We will then be able to reduce to a similar setting as considered in prop:warmup and deduce a similar regret bound. We prove the following result:
Proposition 38 
Suppose that \(\phi : \mathcal {B}_1^d \rightarrow \mathcal {B}_1^m\)  satisfies the following properties:

\(\phi \)  is \(L\) -Lipschitz.

\(\phi \)  is polynomial in the sense that each of the coordinates of \(\phi \)  is a polynomial in the coordinates of \(x \in \mathcal {B}_1^d\)  with degree at most \(\ell \) .

There is an \(\alpha > 0\)  such that the Jacobian \(\mathrm {D}\phi \)  satisfies:
\(\det \left(\mathbb {E}_{x \sim \mu _d}\left[\mathrm {D}\phi (x) \mathrm {D}\phi (x)^T\right]\right) \ge \alpha ^2\) 

Suppose further that the \(x_t \in \mathcal {B}_1^d\)  are generated in a \(\sigma \) -smooth manner and the \(y_t\)  are realizable with respect to \(\mathcal {F}_{\mathrm {lin}}^m \circ \phi \) . Then there is a universal constant \(C\)  such that for all \(T\) , if we set
\(p = C m \ell \log \left(\frac{L \ell T}{\delta }\right)\) 
and run alg:polynomials, then with probability at least \(1 - \delta \) ,
\(\operatorname{Reg}_T \le C \left(m \log (m) + \log \left(\frac{1}{\alpha }\right) + \ell ^2 m^2 d \log ^2\left(\frac{d \ell T L}{\sigma \delta }\right) \right).\) 

Consider the sequence of stopping times \(\rho _\tau \) , where \(\rho _0 = 0\)  and, for \(\tau >0\) ,
\(\rho _\tau = \inf \left\lbrace t > \rho _{\tau -1} | \max \left(\sum _{s= \rho _{\tau - 1}}^t \mathbb {I}[y_t = 1 \text{ and } \hat{y}_t = -1],\sum _{s= \rho _{\tau - 1}}^t \mathbb {I}[y_t = -1 \text{ and } \hat{y}_t = 1] \right) \ge p \right\rbrace .\) 
for some \(p\)  to be determined. Furthermore, let
\(\ell _t = \mathbb {I}\left[t \in (2 p + 1)\mathbb {N}\text{ and } t- 2p \le \rho _\tau \le t \text{ for some } \tau \right]\) 
We begin by claiming that the following inequality holds:
\(\operatorname{Reg}_T \le (2p + 1)\left(1 + \sum _{t = 1}^T \ell _t\right) \le (2p + 1)\left(1 + \sum _{t^{\prime } = 1}^{\left\lfloor \frac{T}{2p+1} \right\rfloor } \ell _{(2p+1)t^{\prime }}\right). \) 
Indeed, we note that the sum is equal to \(\tau _T\) , the maximal \(\tau \)  such that \(\rho _\tau \le T\)  and the pigeonhole principle tells us that we suffer at most \(2p + 1\)  mistakes in the interval \(\rho _{\tau - 1} \le t \le \rho _\tau \) . There are at most \(2p\)  mistakes in the interval \(\rho _{\tau _T} \le t \le T\)  and so the first inequality holds. The second inequality follows from noting that \(\ell _t = 1\)  implies that \(t = (2p + 1) t^{\prime }\)  for some \(t^{\prime }\) . For each \(1 \le \tau \le \tau _T\) , we let
\(\overline{x}_\tau = \frac{1}{p} \sum _{\begin{array}{c}\rho _{\tau - 1} < t \le \rho _\tau \\ y_t = y_\tau \text{ and } \hat{y}_t \ne y_t\end{array}} \phi (x_t)\) 
Now, fix \(\beta , \gamma > 0\)  to be set later and let
\(\mathcal {U}_1 &= \left\lbrace \text{for all } t \text{ such that } \mathbb {P}_t(\hat{y}_t \ne y_t) < \gamma , \text{ it holds that } \hat{y}_t = y_t \right\rbrace  \\\mathcal {U}_2 &= \left\lbrace \text{for all } t \text{ such that } \mathbb {P}_t(y_t = y) < \beta \text{ for some } y \text{, it holds that } y_t \ne y \right\rbrace .\) 

We claim that for some \(p\) , there is a sequence of \(\overline{x}_\tau ^{\prime } \in \mathcal {B}_1^m\)  such that if
\(\mathcal {U}&= \left\lbrace \widetilde{x}_\tau = \widetilde{x}_\tau ^{\prime } \text{ for all } \tau \right\rbrace  \\\mathcal {U}&= \mathcal {U}_1 \cap \mathcal {U}_2 \cap \mathcal {U}_3\) 

then first, \(\mathbb {P}(\mathcal {U}) \ge 1 - 2 T \beta - T \gamma - \frac{\delta }{4}\)  and second, the \(\overline{x}_\tau ^{\prime }\)  are \(\sigma ^{\prime }\) -smooth with respect to \(\mu _m\) . This claim, and the dependence of \(\sigma ^{\prime }\)  on the relevant parameters is the subject of prop:polynomialmasterprop below. For now, we will take it as given. Now, recalling the disagreement region and version space notation \(D_t, \mathcal {F}_t\) , as from app:warmup, we note that if \(\ell _{t^{\prime }} = 1\)  and \(\tau \)  is maximal subject to \(\rho _\tau \le (2p + 1) t^{\prime }\) , then we must have \(\overline{x}_\tau \in D_{\rho _{\tau - 1}}\) . To see this, note that \(w_t = w_{\rho _{\tau - 1}}\)  for \(\rho _{\tau - 1} < t \le \rho _\tau \)  and thus \(w_{\rho _{\tau - 1}}\)  is such that \(\left\langle w_{\rho _{\tau - 1}} , y_s \phi (x_s) \right\rangle  < 0\)  for each such \(s\) . By linearity, we have
\(\left\langle w_{\rho _{\tau - 1}} , \overline{y}_\tau \overline{x}_\tau  \right\rangle  = \frac{1}{p} \sum _{i = 1}^p \left\langle w_{\rho _{\tau - 1}} , y_{\tau _i}\phi (x_{\tau _i}) \right\rangle  < 0\) 
Realizabilty implies that there is some \(w\)  such that \(\left\langle w , y_s \phi (x_s) \right\rangle  \ge 0\)  for all \(s\) , and so linearity implies that, for that \(w\) ,
\(\left\langle w , \overline{y}_\tau \overline{x}_\tau  \right\rangle  = \frac{1}{p} \sum _{i = 1}^p \left\langle w , \overline{y}_\tau \overline{x}_\tau  \right\rangle  \ge 0\) 
Thus we see that \(\overline{x}_\tau \in D_{\rho _{\tau - 1}}\) . We now note that for any \(t^{\prime }\) ,
\(\mathbb {P}_{\rho _{\tau - 1}}(\ell _{(2p + 1)t^{\prime }} = 1) \le \frac{(2p + 1) \mu _m(D_{\rho _{\tau - 1}})}{\sigma ^{\prime }}\) 
where \(\sigma ^{\prime }\)  is as in prop:polynomialmasterprop. Applying now lem:inclusioninorthogonal,lem:orthogonality,lem:surfacearea in the same way as in the proof of prop:warmup, we place ourselves now into the situation of lem:generalizedmasterreduction, the generalized version of the master reduction lem:masterreduction. Thus, we have that for all \(T\) , with probability at least \(1 - \delta \) ,
\(\sum _{t^{\prime } = 1}^{\left\lfloor \frac{T}{2p+1} \right\rfloor } \ell _{(2p+1) t^{\prime }} &\le 4 \frac{\log \left(\frac{2 T (2p + 1) 4^{m+1} m^{2m}}{(2p + 1) \sigma ^{\prime } \delta }\right)}{\log \left(\frac{9}{8}\right)} + \frac{e -1}{1 - \sqrt{\frac{8}{9}}} \\&\le C\left(1 + m \log (m) + \log \left(\frac{T}{\delta }\right) + \log \left(\frac{1}{\sigma ^{\prime }}\right)\right)\) 

If we set
\(p = C m \ell \log \left(\frac{L \ell T}{\delta }\right)\) 
then plugging in the penultimate display into (REF ), taking \(\gamma = \frac{\delta }{4 T}\)  and \(\beta = \frac{\delta }{8 T}\) , and plugging in the bounds from prop:polynomialmasterprop concludes the proof.
[!t]
[1]
Initialize  \(\widetilde{\mathcal {W}}_1 = \mathcal {B}_1^{m}\) , \(\widetilde{w}_1 = \mathbf {e_1} \in \mathcal {W}_1\) , \(\phi : \mathcal {B}_1^d \rightarrow \mathcal {B}_1^m\) , \(\mathcal {M}_1, \mathcal {M}_{-1} = \lbrace \rbrace \) , \(p \in \mathbb {N}\) 
\(t=1,2,\dots \) 
Recieve  \(x_t\) ,
predict
\(\hat{y}_t = \operatorname{sign}(\left\langle \widetilde{w}_t , \phi (x_t) \right\rangle ), \) 

Update \(\widetilde{\mathcal {W}}_{t+1} = \widetilde{\mathcal {W}}_t \cap \lbrace \widetilde{w} \in \mathcal {B}_1^{d+1}| \left\langle \widetilde{w} ,  \phi (x_t) y_t \right\rangle  \ge 0 \rbrace \) 
\(\hat{y}_t \ne y_t\)                                                           (blue!70!black% \(\mathbf {\mathsf {self}}.\mathbf {\mathsf {errorUpdate}}(x_t)\))
Update \(\mathcal {M}_{y_t} \leftarrow \mathcal {M}_{y_t} \cup \lbrace x_t \rbrace \) 
\(\max \left(\left| \mathcal {M}_1 \right|, \left| \mathcal {M}_{-1} \right|\right) = p\) 
 Update
 \(\widetilde{w}_{t+1} \leftarrow \mathbf {\mathsf {JohnEllpsoidCenter}}(\widetilde{\mathcal {W}}_{t+1})\)
            blue!70!black% returns center of John Ellpsoid of given convex body
 Reset \(\mathcal {M}_1, \mathcal {M}_{-1} \leftarrow \lbrace \rbrace \) 

Binary Classification with Polynomial Features
We note that prop:featuremap follows immediately from prop:polynomialimbedding. The key difficulty in the proof of prop:polynomialimbedding, that we left until now, is the smoothness of the \(\overline{x}_\tau \) . We state this fact, and provide a quantitative bound on the smoothness parameter, in the next proposition:
Proposition 39 
Let \(\phi : \mathcal {B}_1^d \rightarrow \mathcal {B}_1^m\)  be an \(L\) -Lipschitz function whose coordinates are polynomials in the coordinates of \(x \in \mathcal {B}_1^d\) , with degree at most \(\ell \) . Suppose \(\phi \)  is such that
\(\det \left(\mathbb {E}_{x \sim \mu _d}\left[\mathrm {D}\phi (x) \mathrm {D}\phi (x)^T\right]\right) \ge \alpha ^2.\) 
Fix any \(p \in \mathbb {N}\)  such that \(p d \ge m\) . Suppose that \((x_1, y_1), \dots , (x_T, y_T)\)  is a data sequence satisfying the following four properties:

The distribution of \(x_t\)  conditional on the history is \(\sigma \) -smooth with respect to \(\mu _d\) .

For \(y \in \lbrace \pm 1\rbrace \) , for any \(t\) , \(\mathbb {P}_t(y_t = y) \ge \beta \) .

The \(y_t\)  are realizable with respect to \(\mathcal {F}_{\mathrm {lin}}^m \circ \phi \) .

For any \(t\) , and any choice of \(\hat{y}_t\)  by the learner, \(\mathbb {P}_t\left(\hat{y}_t \ne y_t\right) \ge \gamma \) .

where \(\mathbb {P}_t\)  is the conditional probability of the history up to time \(t\) . Now, consider the set of stopping times \(\rho _\tau \)  with \(\rho _0 = 0\)  and
\(\rho _\tau = \inf \left\lbrace t > \rho _{\tau -1} | \max \left(\sum _{s= \rho _{\tau - 1}}^t \mathbb {I}[y_t = 1 \text{ and } \hat{y}_t = -1],\sum _{s= \rho _{\tau - 1}}^t \mathbb {I}[y_t = -1 \text{ and } \hat{y}_t = 1] \right) \ge p \right\rbrace \) 
Let \(\overline{y}_\tau = y_{\rho _\tau }\)  and let
\(\overline{x}_\tau = \frac{1}{p} \sum _{k = 1}^p \phi \left(x_{\tau _k}\right)\) 
where \(\tau _1, \dots , \tau _p\)  are the \(p\)  times \(\rho _{\tau - 1} < t \le \rho _\tau \)  satifying \(y_t = \overline{y}_\tau \)  and \(\hat{y}_t \ne y_t\) . There is a universal constant \(C\)  such that if
\(p \ge C m \ell \log \left(\frac{L \ell T}{\delta }\right)\) 
then there is a data sequence a sequence \(\overline{x}_t^{\prime } \in \mathcal {B}_1^m\)  satisfying the following three properties. First, the sequence \((\overline{x}_t^{\prime }, \overline{y}_t)\)  is realizable with respect to \(\mathcal {F}_{\mathrm {lin}}^m\) . Second, with probability at least \(1 - \delta \) , for all \(t\) , \(\overline{x}_t = \overline{x}_t^{\prime }\) . Third, the \(\overline{x}_t^{\prime }\)  is \(\sigma ^{\prime }\) -smooth with respect to \(\mu _m\) , where
\(\sigma ^{\prime } = c \cdot \alpha \cdot p^{- \frac{m}{2}} \left(\frac{\beta \gamma \sigma }{T}\right)^{2 \ell m p} \ell ^{-m\left(\ell + pd\right)} d^{- pd} \) 
wisth \(c\)  a universal constant

Intuitively, we wait until we have misclassified a class \(p\)  times and then form a `meta-point' \((\widetilde{x}_\tau , \widetilde{y}_\tau )\)  that will allow us to reduce to the setting of prop:warmup. The meta-point will be constructed by averaging samples \(x_t\)  in order to ensure smoothness with respect to \(\mu _m\) .
We will show that prop:polynomialmasterprop follows from three results that we will prove below. First, we show that if \(\phi \)  is well-behaved, and the \(x_t\)  are \(\sigma \) -smooth with respect to \(\mu _d\) , then the \(\widetilde{x}_t\)  are \(\sigma ^{\prime }\) -smooth with respect to \(\mu _m\) .
Proposition 40 
Suppose that \(\phi : \mathcal {B}_1^d \rightarrow \mathcal {B}_1^m\)  is a smooth map between Euclidean balls of dimensions \(d\)  and \(m\)  with Jacobian \(\mathrm {D}\phi \) . Consider the function \(f: (\mathbb {R}^d)^p \rightarrow \mathbb {R}^m\)  defined as
\(\psi (x_1, \dots , x_p) = \frac{1}{p} \sum _{i = 1}^p \phi (x_i)\) 
Suppose that that the following three conditions are satisfied:

There is some \(V \subset (\mathcal {B}_1^d)^{\times p}\)  and \(c > 0\)  such that for \(\mu _d^{\otimes p}\) -almost every \(x \in V\) , \(\det (\mathrm {D}\psi (x) \mathrm {D}\psi (x)^T) \ge \alpha ^2\) .

For some \(\ell \ge 2\)
\(\sup _{x \in \mathcal {B}_1^d} \max _{\begin{array}{c}\left| \nu  \right| = \ell +1 \\ 1 \le i \le m \end{array}} \left| \partial ^\nu \phi _i(x) \right| \le 2^{- (1+\ell )}\) 
In particular, this holds if \(\phi (x)\)  is a polynomial of degree at most \(\ell \) .

Finally, suppose that the joint distribution of \((x_1, \dots , x_p)\)  is \(\sigma ^p\) -smooth with respect to \(\mu _{d}^{\otimes p}\) .

If \(pd \ge m\) , then the law of \(\psi (x_1, \dots , x_p)\) , conditioned on \((x_1, \dots , x_p) \in V\)  is \(\sigma ^{\prime }\) -smooth with respect to \(\mu _m\) , the uniform measure on \(\mathcal {B}_1^m\) , where
\(\sigma ^{\prime } = \frac{\alpha \sigma ^p \cdot \mathbb {P}\left((x_1, \dots , x_p) \in V\right) }{\ell ^{2 m + m p d} d^{pd}}\) 

Second, we show that if \(\phi \)  is a polynomial, then it is well-behaved in the sense of prop:imbeddingissmooth with high probability, by proving the more general small-ball type estimate below:
Proposition 41  There exists a univesal constant \(C\)  such that the following holds. Let \(\Psi :\mathcal {R}^d \rightarrow \mathbb {S}_{+}^D\)  be any function whose image is contained in the set of PSD matrices and whose entries are polynomials of degree at most \(\ell \) , and let \(x_1,\dots ,x_p\)  be a sequence of random-variables such that, for each \(t\) , \(x_t \mid x_{1},\dots ,x_{t-1}\)  is \(\sigma \) -smooth with respect to a common log-concave measure \(\mu \) , and \(\mathbb {P}_{x \sim \mu }[\lambda _{\max }(\Psi (x)) \le B] = 1\) . Define
\(\Lambda := \operatorname{\mathbb {E}}_{x \sim \mu }[\Psi (x)]\) 

Suppose that \(p \ge 16\log (1/\delta ) + \frac{D}{4}\log (24B) + \frac{1}{4}(\log \det (\Lambda ) + D\ell \log (C\ell ))\) . Then,
\(\mathbb {P}\left[\det \left(\frac{1}{p}\sum _{i=1}^p \Psi (x_i)\right)\le \left(\frac{\sigma }{C\ell }\right)^{\ell D}\det (\Lambda )\right] \le \delta .\) 

Finally, we will show that if the probabilities corresponding to each label are well-controlled, then the laws of \(x_{\tau _k}\)  are smooth with respect to \(\mu _d\) :
Proposition 42 
Let \((x_{\tau _1}, y_{\tau _1}), \dots , (x_{\tau _{p}}, y_{\tau _{p}})\)  be the sequence of points defined in prop:polynomialmasterprop, arising from a sequence of \((x_t, yt)\)  with the \(x_t\)  being \(\sigma \) -smooth conditional on the history and for each \(t\) , and \(y \in \lbrace \pm 1\rbrace \)  it holds that \(\mathbb {P}(y_t = y ) \ge \beta \)  and that \(\mathbb {P}(\hat{y}_t \ne y_t) \ge \gamma \) . Then, for each \(i\) , it holds that the law of \(x_{\tau _i}\)  conditional on the history up to time \(\tau _{i-1}\)  is \((\beta \gamma \sigma / T)\) -smooth with respect to \(\mu _d\) . In particular, the law of \((x_{\tau _1}, \dots , x_{\tau _p})\) , conditional on the sigma-algebra generated by \(\rho _{\tau -1}\) , is \((\beta \gamma \sigma / T)^{p}\) -smooth with respect to \(\mu _d^{\otimes p}\) .

Note that a peeling argument and induction show that the second statement follows immediately from the first. For any \(\tau , i\) , denote probability conditioned on the history up to time \(\tau _{i-1}\)  by \(\mathbb {P}_{\tau _{i-1}}\) . Let \(B \subset \mathcal {B}_1^d\)  be measurable. Then we compute that \(\mathbb {P}_{\tau _{i-1}}\left(x_{\tau _i} \in B\right)\)  can be given by:
\(&\sum _{1 \le t \le T} \mathbb {P}_{\tau _{i-1}}(t = \tau _i) \mathbb {P}_{\tau _{i-1}}\left(x_t \in B | \tau _i = t\right) \\&\le \sum _{1 \le t \le T} \mathbb {P}_{\tau _{i-1}}(\tau _i > t - 1) \mathbb {P}_{\tau _{i-1}}(x_t \in B | y_t \ne \hat{y}_t \text{ and } y_t = \widetilde{y}_\tau ) \\&\le \sum _{1 \le t \le T} \mathbb {P}_{\tau _{i-1}}(\tau _i > t - 1) \frac{\mathbb {P}_{\tau _{i-1}}(x_t \in B | y_t = \widetilde{y}_\tau ) }{\gamma } \\&\le \sum _{1 \le t \le T} \mathbb {P}_{\tau _{i-1}}(\tau _i > t - 1) \tfrac{\mathbb {P}_{\tau _{i-1}}(x_t \in B | y_t = 1, \, \widetilde{y}_\tau = 1)\mathbb {P}_{\tau _{i-1}}(\widetilde{y}_\tau = 1) + \mathbb {P}_{\tau _{i-1}}(x_t \in B | y_t = -1,\, \widetilde{y}_\tau = -1) \mathbb {P}_{\tau _{i-1}}(\widetilde{y}_\tau = 1)}{\gamma } \\&= \sum _{1 \le t \le T} \mathbb {P}_{\tau _{i-1}}(\tau _i > t - 1) \frac{\mathbb {P}_{\tau _{i-1}}(x_t \in B )}{\beta \gamma } \\&\le \frac{T \mu _d(B)}{\beta \gamma \sigma }\) 

Thus, the result follows.

prop:imbeddingissmooth,prop:anticonc will be shown below but for now we will take them as given. We can now prove the key proposition:
[Proof of prop:polynomialmasterprop]
Let
\(\mathcal {E}= \left\lbrace \det \left(\frac{1}{p} \sum _{i = 1}^p (\mathrm {D}\phi \mathrm {D}\phi ^T)(x_{\tau _i})\right) > \left(\frac{\beta \gamma \sigma }{T}\right)^{(2p + 1) \ell m} (C \ell )^{- \ell m} \alpha ^2 \text{ for all $\tau $}\right\rbrace \) 
and note that by the fact that \(\tau \le T\)
\(p \ge C m \log \left(\frac{\ell L \alpha T}{\delta }\right),\) 
applying a union bound to prop:anticonc and using prop:conditioningsmooth to ensure that the hypothesis holds, shows that \(\mathbb {P}(\mathcal {U}) \ge 1 - \delta \) . On \(\mathcal {U}\)  we will let \(\overline{x}_\tau ^{\prime } = \overline{x}_\tau \)  and on \(\mathcal {U}^c\) , we will draw \(\overline{x}_\tau ^{\prime }\)  from \(\mu _m\) , conditioned on \((\overline{x}_\tau ^{\prime }, \overline{y}_\tau )\)  being realizable with respect to \(\mathcal {F}_{\mathrm {lin}}^m\) . Note that we have realizability by construction on \(\mathcal {U}^c\) . On \(\mathcal {U}\) , we have that \(\overline{x}_\tau ^{\prime } = \overline{x}_\tau \)  and note that convexity implies that if \(y_{\tau _1} = \cdots = y_{\tau _p}\) , then any realizable adversary must classify \(\overline{x}_\tau \)  as \(\overline{y}_\tau \) . Indeed, if \(w \in \mathcal {F}_{\mathrm {lin}}^m\)  is in the version space, and \(\overline{y}_\tau = 1\) , then
\(\left\langle w , \frac{1}{p} \sum _{i = 1}^p \phi (x_{\tau _i}) \right\rangle  = \frac{1}{p} \sum _{i = 1}^p \left\langle w , \phi (x_{\tau _i}) \right\rangle  > 0\) 
and similarly if \(\overline{y}_\tau = -1\) . Thus, realizability holds. As we have already seen that
\(\left\lbrace \text{there exists } \tau \text{ such that } \widetilde{x}_\tau ^{\prime } \ne \overline{x}_\tau \right\rbrace  \subset \mathcal {E}^c\) 
and \(\mathbb {P}(\mathcal {U}^c) \le \delta \) , it suffices to show smoothness of \(\overline{x}_\tau ^{\prime }\) . On \(\mathcal {U}^c\) , the construction implies that \(\overline{x}_\tau ^{\prime }\)  are smooth, so we now restrict to the event \(\mathcal {E}\) . We first compute the Jacobian of \(\psi \) :
\(\mathrm {D}\psi (x_1, \dots , x_p) = \frac{1}{p}\begin{bmatrix}\mathrm {D}\phi (x_1) & \mathrm {D}\phi (x_2) & \cdots & \mathrm {D}\phi (x_p)\end{bmatrix}\) 
and thus
\(\mathrm {D}\psi \mathrm {D}\psi ^T = \frac{1}{p^2} \sum _{i = 1}^p D \psi (x_i) \mathrm {D}\psi (x_i)^T\) 
which in turn implies:
\(\det (\mathrm {D}\psi \mathrm {D}\psi ^T) = p^{- m} \det \left(\frac{1}{p} \sum _{i = 1}^p \mathrm {D}\psi (x_i) \mathrm {D}\psi (x_i)^T\right).\) 
Thus, under \(\mathcal {U}\) , we have that
\(\det ((\mathrm {D}\psi \mathrm {D}\psi ^T)(x_{\tau _1}, \dots , x_{\tau _p})) \ge p^{-m} \left(\frac{\beta \gamma \sigma }{T}\right)^{(2p + 1) \ell m} (C \ell )^{- \ell m} \alpha ^2 = \widetilde{\alpha }^2\) 
We may now use prop:conditioningsmooth to get that \((x_{\tau _1}, \dots , x_{\tau _p})\)  has a law that is \((\beta \gamma \sigma / T)^p\)  smooth with respect to \(\mu _d^{\otimes p}\)  and apply prop:imbeddingissmooth to get that, conditional on \(\mathcal {E}\) , the law of \(\psi (x_{\tau _1}, \dots , x_{\tau _p})\)  is \(\sigma ^{\prime }\) -smooth with respect to \(\mu _m\) , where
\(\sigma ^{\prime } = \frac{\alpha ^{\prime } \left(\frac{\beta \gamma \sigma }{2T}\right)^p}{\ell ^{2m + mpd} d^{pd}}\) 
where we let \(V = \mathcal {U}\)  and note that \(\mathbb {P}((x_{\tau _1}, \dots , x_{\tau _p}) \in \mathcal {U}) \ge \frac{1}{2}\) . The result follows.
Proof of Propossition  REF
We will proceed by using the co-area formula [14]}. For a given \(x \in (B_1^d)^n\) , let
\(J(\psi )(x) = \@root  \of {\det (\mathrm {D}\psi (x) \mathrm {D}\psi (x)^T)}\) 
and let \(\mathcal {H}^j\)  denote the \(j\) -dimensional Hausdorff measure. Then the co-area formula tells us that for any \(B \subset V\) , we have
\(\int _{\psi ^{-1}(B)} J(\psi )(x) \mathrm {d}\mathcal {H}^{dp}(x) = \int _B \mathcal {H}^{dp - m}(\psi ^{-1}(y)) \mathrm {d}\mathcal {H}^{m}(y)\) 
We make use of the following lemma:
Lemma 43 
Suppose that \(\phi \)  is as in prop:imbeddingissmooth. Then for all \(y\) ,
\(\mathcal {H}^{dp - m}(\psi ^{-1}(y)) \le \ell ^{2m + m pd}\) 

Before proving the lemma, we require a preliminary result from [30]}; we reprove it here in order to keep track of the constant.
Lemma 44 
Fix \(k \in \mathbb {N}\)  and suppose that \(Y \subset \mathcal {B}_1^{k}\)  is a hypersurface and let \(\mathcal {B}_r^k \subset \mathcal {B}_1^k\) . Suppose that any line passing through \(\mathcal {B}_r^d\)  intersects \(Y\)  in at most \(\ell \)  points. Then,
\(\operatorname{vol}_{k-1}(Y) \le \frac{\ell 2 \pi ^{\frac{k}{2}}}{\Lambda \left(\frac{k}{2}\right)} r^{-k}.\) 

Because \(\mathcal {B}_r^k\)  is convex, we may consider the map \(\pi : Y \rightarrow \partial \mathcal {B}_r\)  of projection to the boundary. Recentering so that \(\mathcal {B}_r^k\)  has center at the origin, we have \(\pi (y) = r\frac{y}{\left|\left| y \right|\right|}\) . By the co-area formula introduced as (REF ), we have
\(\int _Y J(\pi )(y) \mathrm {d}\mathcal {H}^{k-1}(y) = \int _{\partial \mathcal {B}_r^k} \mathcal {H}^0(\pi ^{-1}(z)) \mathrm {d}\mathcal {H}^{k-1}(z)\) 

Now, note that \(J(\pi (y)) \ge r^k\)  and thus we have
\(\operatorname{vol}_{k-1}(Y) = \int _Y \mathrm {d}\mathcal {H}^{k-1}(y) \le \frac{\int _{\partial \mathcal {B}_r^k} \mathcal {H}^0(\pi ^{-1}(z)) \mathrm {d}\mathcal {H}^{k-1}(z)}{r^k} \le \frac{\ell 2 \pi ^{\frac{k}{2}}}{\Lambda \left(\frac{k}{2}\right) r^k}\) 

where the last inequality comes from combining the fact that by assumption \(\operatorname{vol}_0(\psi ^{-1}(z)) \le \ell \)  and the expression for the surface area of \(S^{d-1}\) .

[Proof of lem:fibreupperbound]
We apply [30]} iteratively on the coordinates of \(\psi \) . In particular, we apply Lemma REF  in order to keep track of the explicit constant in [30]} and apply [30]} to show that we may choose \(r = (20 \cdot \ell ^2)^{-1}\)  in Lemma REF . Thus we have for any \(y \in \mathcal {B}_1^m\) ,
\(\operatorname{vol}_{pd - m}(f^{-1}(y)) &\le \prod _{j = 0}^{m-1} \left(\frac{\ell 2 \pi ^{\frac{pd - j}{2}}}{\Lambda \left(\frac{pd - j}{2}\right)} (20 \cdot \ell ^2)^{pd - j}\right) \\&\le \ell ^{2m + mpd}\) 

using the fact that \(pd \ge m\) . The result follows.

Returning now to the proof of prop:imbeddingissmooth, we see for a given set \(B \subset V\) , that
\(\mathbb {P}\left(\psi (x_1, \dots , x_p) \in B | (x_1, \dots , x_p) \in V\right) &\le \frac{\sigma ^{-p} \operatorname{vol}_{dp}(\psi ^{-1}(B))}{\omega _{d}^p \mathbb {P}(V)} \\&\le \frac{\sigma ^{-p} \ell ^{2m + mpd}}{\omega _d^p \mathbb {P}(V)} \operatorname{vol}_m(B) \\&\le \frac{\sigma ^{-p} \ell ^{2m + m pd} \omega _m}{\omega _p^d \mathbb {P}(V)} \mu _m(B)\) 

where the first inequality follows from the definition of smoothness, the second inequality follows by (REF ) and the above claims, and the last inequality follows by the definition of \(\mu _m\) . The result follows by using the fact that
\(\omega _m = \frac{\pi ^{\frac{m}{2}}}{\Lambda \left(\frac{m}{2} + 1\right)}\) 
and bounding \(\left(\frac{m}{4}\right)^{\frac{m}{4}} \le \Lambda \left(\frac{m}{2} + 1\right) \le \left(\frac{m}{2}\right)^{\frac{m}{2}}\) .

Proof of Proposition  REF
We first introduce a small-ball estimate for sums of PSD random variables, in the spirit of [34]}.
Lemma 45  Let \(X_1,X_2,\dots ,X_p \)  be i.i.d. of positive semi-definite, \(\mathbb {R}^{D \times D}\) -valued random variables, and suppose there exists \(B,\eta > 0\)  and \(\Lambda \in \mathbb {S}_{++}^{D}\)  for which, for all \(t \in [p]\) ,
\(&\mathbb {P}[\lambda _{\max }(X_t) > B] = 0\\&\mathbb {P}_{X_t}[ v^\top X v \ge v^\top \Lambda v \mid X_{1},\dots ,X_{t-1}] \ge \eta , \quad \forall v \in \mathbb {R}^D.\) 

Then, if \(p \ge 8\eta ^{-1}\log (1/\delta ) + \frac{D}{4}\log (\frac{12B}{\eta }) + \frac{1}{4}\log \det (\Lambda ^{-1})\) ,
\(\mathbb {P}\left[\frac{1}{p}\sum _{i=1}^p X_i \lnot \succeq \frac{\eta }{4}\cdot \Lambda \right] \le \delta .\) 

In particular,
\(\mathbb {P}\left[\det \left(\frac{1}{p}\sum _{i=1}^p X_i\right)\le \left(\frac{\eta }{4}\right)^{D}\det (\Lambda )\right] \le \delta .\) 

The proof follows along the lines of [34]}, sharpened slightly for the less general setting. Let \(\Sigma = \sum _{i=1}^p X_i\) . By a Chernoff bound (lem:chernoff), for any \(v \in \mathcal {S}^{D-1}\) , \( \mathbb {P}[v^\top \Sigma v \le \eta p v^\top \Lambda v/2] = \mathbb {P}[ \sum _{i=1}^p v^\top X_i v \le \eta p v^\top \Lambda v/2] \le \mathbb {P}[\sum _{i=1}^p I\lbrace v^\top X_i v \le \eta v^\top \Lambda v\rbrace  \le \eta p/2] \le \exp (-\eta p/8)\) , where we use that \(X_i \succeq 0\) . Hence, for any finite subset \(\mathcal {T}\subset \mathcal {S}^{D-1}\) ,
\(\mathbb {P}[v^\top \Sigma v \ge v^\top \Lambda v \cdot \frac{\eta p}{2}, \quad \forall v \in \mathcal {T}] \ge 1- \exp ( - \eta p/8 + \log |\mathcal {T}|).\) 

To conclude, we show that there exists a finite set \(\mathcal {T}\)  of size at most \(\exp (\frac{D}{2}\log (\frac{12B}{\eta }) + \frac{1}{2}\log \det (\Lambda ))\)  such that, if \(v^\top \Sigma v \ge v^\top \Lambda v \cdot \eta T/2\)  for all \(\mathcal {T}\) , then \(\Sigma \succeq \frac{\eta T}{4}\) .
We take \(\mathcal {T}\)  to be an \(\varepsilon = \sqrt{\eta /4B}\) -net of the set \(\mathcal {S}_{\Lambda } := \lbrace v \in \mathcal {R}^d: v^\top \Lambda v = 1\rbrace \) . Then, if \(v^\top \Sigma v \ge v^\top \Lambda v \cdot \eta p/2 = \eta p/2\)  for all \(\tilde{v} \in \mathcal {S}_{\Lambda }\) , it holds
\(\tilde{v}^\top \Sigma \tilde{v} &\ge \frac{1}{2}v^\top \Sigma v - (\tilde{v}-v)^\top \Sigma (\tilde{v} - v) \ge \frac{1}{2}\eta T - Bp\Vert \tilde{v} - v\Vert ^2 \ge \frac{\eta p}{4},\) 

which means that \(\Sigma \succeq \frac{\eta p }{4}\Lambda \) . Define the ellipsoid \(\mathcal {E}_{\Lambda } := \lbrace v \in \mathcal {R}^d: v^\top \Lambda v \le 1\rbrace \supset \mathcal {S}_{\Lambda }\) . Note that since \(\lambda _{\max }(\Lambda ) \le B\) , \(\mathcal {E}_{\Lambda } \supset \lbrace v:\Vert v\Vert ^2 \le 1/B\rbrace  \supset 2\varepsilon \mathcal {B}_1^D\) , since \(\varepsilon = \sqrt{\eta /4B} \le \frac{1}{2\sqrt{B}}\) .
\(|\mathcal {T}| &\le \frac{\operatorname{vol}(\frac{\varepsilon }{2}\mathcal {B}_1^D + \mathcal {S}_{\Lambda })}{\operatorname{vol}(\frac{\varepsilon }{2}\mathcal {B}_1^D)} \le \frac{\operatorname{vol}(\frac{\varepsilon }{2}\mathcal {B}_1^D + \mathcal {E}_{\Lambda })}{\operatorname{vol}(\frac{\varepsilon }{2}\mathcal {B}_1^D)} \le \frac{\operatorname{vol}(\frac{5}{4}\mathcal {E}_{\Lambda })}{\operatorname{vol}\left(\frac{\varepsilon }{2}\mathcal {B}_1^D\right)} = \left(\frac{8}{5\varepsilon }\right)^D \det (\Lambda ^{-1/2}).\) 

Hence, we can take
\(\log |\mathcal {T}| &\le \frac{D}{2}\log (\frac{64}{25\varepsilon ^2}) + \frac{1}{2}\log \det (\Lambda ) \le \frac{D}{2}\log (\frac{12B}{\eta }) + \frac{1}{2}\log \det (\Lambda ).\) 
Lemma 46  Let \(\Psi :\mathcal {R}^d \rightarrow \mathbb {S}_{+}^D\)  be any function whose image are PSD matrices whose entries are polynomials of degree at most \(\ell \) . Let \(\rho \)  be any distribution which is \(\sigma \) -smooth with respect to a log-concave measure \(\mu \) . Then, there exist a universal constant \(C\)  such that, for any \(v \in \mathcal {R}^D \setminus 0\) ,
\(\mathbb {P}_{x \sim \rho }[ v^\top \Psi (x) v \le \sigma ^{\ell }(C\ell )^{-\ell } v^\top \operatorname{\mathbb {E}}_{x \sim \mu } \Psi (x) v ] \le \frac{1}{2}.\) 

Consider the polynomial function \(f_v(x) = v^\top \Psi (x) v\) . This is a polynomial of degree \(\ell \)  in \(x\) , and nonnegative. By [36]}, with \(q = \ell \) , we have
\(\operatorname{\mathbb {E}}_{x \sim \mu }[f_v(x)]^{1/\ell }\cdot \alpha ^{-1/\ell } \cdot \mathbb {P}_{x \sim \mu }[ f_v(x) \le \alpha ] \le C^{\prime } \ell ,\) 

where \(C^{\prime }\)  is a universal constant. Reparametrizing \(\alpha \leftarrow \alpha \cdot \operatorname{\mathbb {E}}_{x \sim \mu }[f_v(x)] \) , we have
\(\mathbb {P}_{x \sim \mu }[ f_v(x) \le \alpha \operatorname{\mathbb {E}}_{x \sim \mu }[f_v(x)]] \le C^{\prime } \ell \alpha ^{1/\ell }.\) 

To conclude, take \(\alpha = (2C^{\prime }\ell /\sigma )^{-\ell }\) , we get
\(\mathbb {P}_{x \sim \mu }[ f_v(x) \le (2C^{\prime }\ell /\sigma )^{-\ell } \operatorname{\mathbb {E}}_{x \sim \mu }[f_v(x)]] \le \frac{\sigma }{2}\) 

Hence,
\(\mathbb {P}_{x \sim \rho }[ f_v(x) \le (2C^{\prime }\ell /\sigma )^{-\ell } \operatorname{\mathbb {E}}_{x \sim \mu }[f_v(x)]] \le \frac{1}{2}\) 

Taking \(C =2 C^{\prime }\)  and substituting \(f_v(x) = v^\top \Psi (x) v\)  concludes.
[Proof of prop:anticonc] Let \(\rho _t\)  denote the conditional distribution of \(x_t \mid x_{1},\dots ,x_{t-1}\) . By assumption, \(\rho _t\)  is \(\sigma \) -smooth with respect to the log-concave measure \(\mu \) , so
\(\mathbb {P}[ v^\top \Psi (x_t) v \le (C\ell )^{-\ell } v^\top \operatorname{\mathbb {E}}_{x \sim \mu } \Psi (x) v \mid x_1,\dots ,x_{t-1}] \le \frac{1}{2}\) 

Hence, we can apply lem:smallball with \(\eta \leftarrow 1/2\) , \(B \leftarrow B\) , and \(\Lambda \leftarrow (C\ell )^{-\ell } \Lambda \) . Using that \(\det ((C\ell )^{-\ell } \Lambda ) = (C\ell )^{-D\ell }\det (\Lambda )\)  concludes.

Proofs from Section 
In this section, we prove the extensions of our results to the multipiece setting.
Proof of Theorem  REF
Algorithm Description.
alg:Kclass gives our algorithm for \(K\) -class classification. We maintain \(\binom{K}{2}\)  instances of the binary classification algorithm, alg:warmup. That is, each \(\mathcal {A}_{\mathrm {bin}}\)  maintains a \(w_{t}^{(i,j)}\)  at each time \(t\) , and
\(\mathcal {A}_{\mathrm {bin}}^{(i,j)}.\mathbf {\mathsf {classify}}(x) = \operatorname{sign}(\langle w_t^{(i,j)},w \rangle ).\) 
To gain intuition, recall that we assume the ground-truth classifier to
\(f^{\star }(x) = \operatornamewithlimits{arg\,max}_{i \in [K]}\langle x,w_\star ^i\rangle , \) 

where the argmax is taken lexicographically. Hence, \(f^{\star }(x)\)  admits the following equivalent representation:
\(f^{\star }(x) &= \min _{i \in [K]}\lbrace i:\langle x,w_\star ^i\rangle \ge \max _{j > i}\langle x,w_\star ^j\rangle \rbrace  \nonumber \\&= \min _{i \in [K]}\lbrace i:\operatorname{sign}(\langle x,w_\star ^i- w_\star ^j\rangle \ge ,~ \forall i > i\rbrace  \) 

Hence, \(f^{\star }(x)\)  can be thought of running a lexicographic tournament, picking out the first index \(i\)  which `wins' over all lesser indices \(k\) . This is what motivates the selection of \(\hat{y}\)  in line:pred of alg:Kclass.
[Proof of prop:kpiececlassification]
We reduce to the generalized, “censored” variation of our linear classification setting, depicted in prop:warmupgeneralized. For pairs \(i < j\) , define
\(w_\star ^{(i,j)}:= w_\star ^i- w_\star ^j\quad y_t^{(i,j)} := \operatorname{sign}(\langle w_\star ^{(i,j)}, x_t\rangle ), \quad \hat{y}_t^{(i,j)} := \mathcal {A}_{\mathrm {bin}}^{(i,j)}.\mathbf {\mathsf {classify}}(x_t)\) 

Note that
\(y_t^{(i,j)} = 1 ~~\forall j > i \text{ whenever } i = y_t. \) 

For simplicty, lets assume that \(w^{\star ,(i,j)} \ne 0\)  for \(i < j\) . We address the edgecase where this term may be zero at the end.
Further, let \(i_t < j_t\)  denote the indices select in eq:ijKwise. Then, since the algorithm always selects such a pair \((i_t,j_t)\)  whenever a mistake is made (and defining, say \((i_t,j_t) = (0,0)\)  to indicate no mistake),
\(\sum _{t=1}^T I\lbrace \hat{y}_t \ne y\rbrace  = \sum _{i<j}\sum _{t=1}^T I\lbrace (i_t,j_t) = (i,j)\rbrace .\) 

The following claim reduces to binary-losses.
Claim 2  For the indices \(i_t < j_t\)  selected in eq:ijKwise, and any \(1 \le i < j \le K\) ,
\(I\lbrace (i_t,j_t) = (i,j)\rbrace  = I\lbrace y_t^{(i,j)} \ne \hat{y}_t^{(i,j)}\rbrace I\lbrace (i_t,j_t) = (i,j)\rbrace .\) 

Moreover, when \((i_t,j_t) = (i,j)\) , \(y_t^{(i,j)} = \operatorname{sign}(\hat{y}_t - y_t)\) , and thus can be determined by learner.

Indeed, at a round where \(I\lbrace (i_t,j_t) = (i,j)\rbrace \) , we have \(\hat{y}_t \ne y_t\) . We have two cases

When \(y_t < \hat{y}_t\) , then eq:ijKwise selects \(i = y_t\)  and \(j\)  as some index for which \(\hat{y}_t^{(i,j)} = -1\) , such an index must exist by the choice of \(\hat{y}_t\)  in line:pred (otherwise, either \( \hat{y}_t < y_t\) , or else \(y_t\)  would be correctly selected as the true class). On the other hand, \(y_t^{(i,j)} := \operatorname{sign}(\langle w_\star ^{(i,j)}, x_t\rangle ) = 1 = \operatorname{sign}(\hat{y}_t - y_t)\)  by eq:yteq. Thus, \(y_t^{(i,j)} \ne \hat{y}_t^{(i,j)}\)

If \(\hat{y}_t < y_t\) , then from line:pred it must be the case that \(\hat{y}_t^{(i,j)} = 1\)  for \(i = \hat{y}_t\)  and \(j = y_t\)  being the indices selected in eq:ijKwise. But by the reverse of eq:yteq, \(y_t^{(i,j)} = -1 = \operatorname{sign}(\hat{y}_t - y_t)\) . Hence, \(\hat{y}_t^{(i,j)} \ne y_t^{(i,j)}\) .

Hence, we may write
\(\sum _{t=1}^T I\lbrace \hat{y}_t \ne y\rbrace  = \sum _{i<j}\sum _{t=1}^T\ell _t^{(i,j)}, \quad \ell _t^{(i,j)} := I\lbrace y_t^{(i,j)} \ne \hat{y}_t^{(i,j)}\rbrace I\lbrace (i_t,j_t) = (i,j)\rbrace .\) 

We now claim that the losses \(\ell _t^{(i,j)} := I\lbrace y_t^{(i,j)} \ne \hat{y}_t^{(i,j)}\rbrace I\lbrace (i_t,j_t) = (i,j)\rbrace \)  precisely corresponding to the censored binary setting of prop:warmupgeneralized.Indeed, consider a setting where \(x_1,x_2,\dots \)  are selected by the \(\sigma \) -smooth adversary, and the label is \(\hat{y}_t^{(i,j)}\)  defined above. \(\mathcal {A}_{\mathrm {bin}}^{(i,j)}\)  does not always see \(\hat{y}_t^{(i,j)}\) , but whenever \(\ell _t^{(i,j)} = 1\) , claim:Ktobin shows that the learner does indeed observe the true value \(\hat{y}_t^{(i,j)}\) . Thus, by prop:warmupgeneralized, it holds for any fixed \(i < j\)  that with probability \(1 - \delta \) ,
\(\sum _{t=1}^T\ell _{t}^{(i,j)} \le 136 d \log (d) + 34 \log \left(\frac{T}{\sigma \delta }\right) + 56\) 

Union bounding over all \(\binom{K}{2} \le K^2\)  pairs \(i < j\)  and summing, we conclude that with probability \(1-\delta \) ,
\(\operatorname{Reg}_T = \sum _{i>j}\sum _{t=1}^T\ell _{t}^{(i,j)} &\le 136 K^2 d \log (d) + 34K^2 \log \left(\frac{TK^2}{\sigma \delta }\right) + 56K^2. \\&\le 136 K^2 d \log (d) + 90K^2 \log \left(\frac{TK^2}{\sigma \delta }\right)\) 

Modification for non-unique ground truth classifiers.
Here, we can modify \(\mathcal {A}_{\mathrm {bin}}^{(i,j)}\)  with the following rule: predict \(\hat{y}_t^{(i,j)} = 1\)  until there is an time \(t\)  for which \((i_t,j_t) = (i,j)\) , and then reinitalize \(\mathcal {A}_{\mathrm {bin}}^{(i,j)}\)  to have \(w_t^{(i,j)} = e_1\) , as in alg:warmup.
Consider an \(i < j\)  with \(w_\star ^i= w_\star ^j\) . We claim \((i_t,j_t) \ne (i,j)\)  for any \(t\) . Now, suppose there is a time \(t\)  that \((i_t,j_t) = (i,j)\) , let \(\tau \)  denote the first time \(t\)  for which this is true. Then, \(\hat{y}_t^{(i,j)} = 1\) .
But in addition \(y_t \ne j\)  for any \(t\)  because we assume the \(\operatornamewithlimits{arg\,max}\)  in eq:argmaxapp is broken lexicograophically. Thus, from eq:ijKwise, it must be that \(y_\tau = i\) , and that \(j\)  is such that \(\hat{y}_t^{(i,j)} = -1\) ; this gives a contradiction.
Now consider \(i < j\)  with \(w_\star ^i\ne w_\star ^j\) . Then our modification of \(\hat{y}_t^{(i,j)}\)  only increases \(\sum _{t=1}^T\ell _{t}^{(i,j)}\)  by at most 1. This adds at most \(\binom{K}{2} < K^2\)  to the total regret (modifying the constant of 90 to 91).
[!t]
[1]
Initialize  Binary classifiers \(\mathcal {A}_{\mathrm {bin}}^{(i,j)}\) , \(i < j\) 
\(t=1,2,\dots \) 
recieve  \(x_t\) 
\(i < j\)  \(\hat{y}_t^{(i,j)} = \mathcal {A}_{\mathrm {bin}}^{(i,j)}.\mathbf {\mathsf {classify}}(x_t) \) 
predict \(\hat{y}_t = \min \lbrace i \in [K]: \hat{y}_t^{(i,j)} = 1, ~ i < j \le K\rbrace \)                    (blue!70!black% \(\mathbf {\mathsf {self}}.\mathbf {\mathsf {classify}}(x_t)\)) 
\(\hat{y}_t \ne y_t\)                                                           (blue!70!black% \(\mathbf {\mathsf {self}}.\mathbf {\mathsf {errorUpdate}}(x_t)\))
 Define
\((i,j) = {\left\lbrace \begin{array}{ll} i = y_t, ~j \in \lbrace j > i: \hat{y}_t^{(i,j)} = -1 \rbrace  & \text{if } y_t < \hat{y}_j\\i = \hat{y}_t, ~ j = y_t & \text{if } \hat{y}_j < y_t\end{array}\right.} \) 

 Update \(\mathcal {A}_{\mathrm {bin}}^{(i,j)}.\mathbf {\mathsf {errorUpdate}}(x_t)\) 
\(K\) -class linear classification

Formal Guarantees for Piecewise Regression
We will prove a slightly more general version of prop:kpieceregression and then derive the result in sec:kpiece as a corollary. First, we will define what kinds of regression classes our result will apply to:
Definition 47 
Let \(\mathcal {G}: \mathcal {X}\rightarrow \mathbb {R}\)  be a function class. We say that \(\mathcal {G}\)  is \(\ell \) -determined with respect to some measure \(\mu \)  on \(\mathcal {X}\)  if the following two conditions hold:

The values on \(\ell \)  points in general position uniquely determine the function, i.e.,
\(\mathbb {P}\left(\text{there exist } g \ne g^{\prime } \in \mathcal {G}\text{ such that } g(x_i) = g^{\prime }(x_i) \text{ for } 1 \le i \le \ell \text{ and } x_i \sim \mu \right) = 0\) 

Two functions intersect only on measure zero sets, i.e., for all \(g, g^{\prime } \in \mathcal {G}\) ,
\(\mu \left(\left\lbrace x \in \mathcal {X}: g(x) = g^{\prime }(x)\right\rbrace \right) = 0\) 


Note that linear classes in \(\mathbb {R}^d\)  are trivially \(d\) -determined with respect to the Lebesgue measure, and thus with respect to any measure absolutely continuous with respect to the Lebesgue measure. Polynomial classes are also \(\ell \) -determined with respect to the Lebesgue measure for some \(\ell \)  depending on \(d\)  and the degree of the polynomials. We observe that our definition of an \(\ell \) -determined function class is an offline analogue to the notion of eluder dimension from [37]}.
Now, for a given function class \(\mathcal {G}: \mathcal {X}\rightarrow \mathbb {R}\) , we denote by
\(\mathcal {G}_\mathcal {F}= \left\lbrace x \mapsto \mathbf {g}_f(x) = \sum _{i = 1}^K g_i(x) \mathbb {I}[f(x) = i] \bigg | g_i \in \mathcal {G}\text{ and } f \in \mathcal {F}\right\rbrace  \) 
where \(\mathcal {F}\)  is the set of \(K\) -class linear classifiers from prop:kpiececlassification. We will continue to suppose that the \(x_t\)  are drawn from distributions that are \(\sigma \) -smooth with respect to \(\mu \)  and that the labels \(y_t\)  are realizable with respect to \(\mathcal {G}_\mathcal {F}\) .
Assumption 1 (Oblivious, realizable smoothed sequential setting)  We suppose smoothed online learning setting and the adversary is realizable with respect to \(\mathcal {G}_\mathcal {F}\)  and oblivious in the sense that before the learning process begins, the adversary chooses \(\mathbf {g}^\star = ({g}^\star _1, \dots , {g}^\star _K) \in \mathcal {G}^{K}\)  and \(f^{\star }\in \mathcal {F}\)  and lets \(y_t = (\mathbf {g}^\star )_{f^{\star }}(x_t)\)  for all \(t\) . We assume further that \(\mathbf {g}^\star \)  has unique entries: \({g}^\star _i \ne {g}^\star _j\)  for \(i \le j\) .

Lastly, we assume we have access to the following ERM oracle.
Definition 48 (ERM Oracle)  Given \(\mathcal {U}= \lbrace (x_1,y_1),\dots ,(x_n,y_m)\rbrace \) , where \((x_i,y_i) \in \mathcal {B}_1^d \times \mathcal {Y}\) , \(\mathbf {\mathsf {ERM}}(\mathcal {U},\mathcal {G},K)\)  returns a \(n \le K\) , and \(g_1,\dots ,g_n\)  and partition \(C_1,\dots ,C_n\)  of \(\mathcal {U}\)  such that, for all \((x,y) \in C_i\) , \(g_i(x) = y\) . By post-processing, we may also assume that \(g_i\)  are distinctNote that the ERM Oracle need not cluster with respect to the classifiers (even thought it can certainly be implemented this way). Hence, one can can merge cluster to ensure \(g_i\)  is distinct.

Proposition 49 (General \(\ell \) -Determined Regression)
Suppose that we are in the semi-oblivious, smoothed online learning setting, where the adversary begins by choosing \(g_{f^\star }^\star \mathcal {G}_\mathcal {F}\)  from (REF ), and, at each time \(t\) , draws \(x_t\)  from a distribution that is \(\sigma \) -smooth with respect to \(\mu \)  and sets \(y_t = g_{f^\star }^\star (x_t)\) . Suppose further that \(\mathcal {G}\)  is \(\ell \) -determined, in the sence of def:elldetermined. Then, alg:generalreg satisfies for all \(T\) , with probability at least \(1 - \delta \) ,
\(\operatorname{Reg}_T \le 136 K^2 d \log (d) + 91K^2 \log \left(\frac{TK^2}{\sigma \delta }\right) + K^2(\ell + 1)\) 
Moreover, the per-time step computational complexity of alg:generalreg is polynomial in \(d\)  and the complexity of the \(\mathbf {\mathsf {ERM}}\)  oracle defn:ermoracle, applied to a data set \(\mathcal {U}\)  of size no more that \(|\mathcal {U}| \le K(\ell +1)\) .


Algorithm for Piecewise Regression
alg:generalreg proceeeds at follows. We let \(N_t\)  denote the number of clusters about which we are certain, \(\mathcal {U}_t\)  denote the set of points which cannot be assigned to a cluster. We maintain a supervised \(K\) -class linear classifier, \(\mathcal {A}\) , described in alg:Ksupervisionalgorithm. It is similar in spirit to alg:Kclass, except it takes in “side information” \(M_t\)  on which it only predicts from the first \(M_t\)  classes. Lastly, we maintain a growing sequence of regressors \(\hat{g}_1,\hat{g}_2,\dots \in \mathcal {G}\)  such that \(\hat{g}_i\)  does not change once assigned, and \(\hat{g}_i\)  is defined for all \(i \le N_t\) .
At each time \(t\) , we call \(\hat{k}_t = \mathcal {A}.\mathbf {\mathsf {classify}}(x_t,N_t)\)  to guess the cluster of \(x_t\) , only among cluster \(i \le N_t\)  about which we are certain. Then, we predict \(\hat{y}_t = \hat{g}_{\hat{k}_t}(x_t)\) . The idea is that, for \(k = \hat{k}_t \le N_t\) , we are sure that \(\hat{g}_k\)  is the true predictor if \(x_t\)  is in cluster \(k\) .We then observe \(y_t\) . If \(y_t\)  was correctly predicted by one of that \(\hat{g}_i\)  for which \(i \le N_t\) , but not the \(\hat{k}_t\)  we guessed, then we update our classifier \(\mathcal {A}\) . Otherwise, we call the ERM oracle to determine if we can find new cluster(s) to add, appending to our sequence of predictors \(\hat{g}\) 's, and growing our number of certain clusters \(N_t\) . Note that we never maintain an explicit clustering of our points, but only cluster retroactively based on whether \(\hat{g}_i(x_t) = y_t\)  for some \(i\) , as a means to recover the classification label.
[!t]
[1]
Init: \(K\) -class supervised linear classifier \(\mathcal {A}\)  (instance of alg:Ksupervisionalgorithm)
      ERM-oracle \(\mathbf {\mathsf {ERM}}\)  (see )
each time \(t= 1,2,\dots \) 
recieve  \(x_t\) 
predict \(\hat{y}_t = \hat{g}_{k}(x_t)\)  for \(k = \hat{k}_t\) , where \(\hat{k}_t := \mathcal {A}.\mathbf {\mathsf {classify}}(x_t,N_t)\)  blue!70!black% \(\hat{y}_t = 0\)  if \(N_t = 0\)
observe \(y_t\) .
\(\exists k^\star _t \in [N_t]\)  with \(\hat{g}_k(x_t) = y_t\) 
 blue!70!black% update classification
\(\hat{k}_t \ne k^{\star }_t\) , \(\mathcal {A}.\mathbf {\mathsf {errorUpdate}}(x_t,N_t)\) 
maintain \(N_{t+1} \leftarrow N_t\) , \(\mathcal {U}_{t+1} \leftarrow \mathcal {U}_t\) 
blue!70!black% update clustering
 \((C_{1:n},g_{1:n}) \leftarrow \mathbf {\mathsf {ERM}}(\tilde{\mathcal {U}}_t,\mathcal {G},K)\)  , \(\tilde{\mathcal {U}}_t = \mathcal {U}_t \cup \lbrace (x_t,y_t)\rbrace \)  
blue!70!black% Initialize \(\tilde{N} = N_t\)
each \(i: |C_i| \ge \ell +1\) 
 \(\tilde{N} = \tilde{N} + 1\) , \(\hat{g}_{\tilde{N}} \leftarrow g_i\) ,
 \(N_{t+1} \leftarrow \tilde{N}\) ,   \(\mathcal {U}_{t+1} \leftarrow \tilde{\mathcal {U}}_t \setminus \bigcup _{i:|C_i| \ge \ell +1}\lbrace (x,y) \in \tilde{\mathcal {U}}_t: g_i(x) = y\rbrace \)  

General Piecewise Regression
[!t]
[1]
Initialize  Binary classifiers \(\mathcal {A}_{\mathrm {bin}}^{(i,j)}\) , \(i < j\) 
\(t=1,2,\dots \) 
blue!70!black% guarantee \(y_t \le M_t\)
Recieve  \((x_t,M_t)\)  and predict                               (blue!70!black% \(\mathbf {\mathsf {self}}.\mathbf {\mathsf {classify}}(x_t,M_t)\))
\(\hat{y}_t = \min \lbrace i \in [M_t]: \mathcal {A}_{\mathrm {bin}}^{(i,j)}.\mathbf {\mathsf {classify}}(x_t) = 1, ~ i < j \le M_t\rbrace ,\) 

Observe  \(y_t\) 
\(\hat{y}_t \ne y_t\)                                                  (blue!70!black% \(\mathbf {\mathsf {self}}.\mathbf {\mathsf {errorUpdate}}(x_t,M_t)\))
 Define
\((i,j) = {\left\lbrace \begin{array}{ll} i = y_t, ~j \in \lbrace k > i: \langle w_1^{(i,k)},x_t \rangle < 0\rbrace  & \text{if } y_t < \hat{y}_j\\i = \hat{y}_t, ~ j = y_t & \text{if } \hat{y}_j < y_t\end{array}\right.}\) 

 Update \(\mathcal {A}_{\mathrm {bin}}^{(i,j)}.\mathbf {\mathsf {errorUpdate}}(x_t)\) 
\(K\) -class linear classification with supervision

Proof of Proposition  REF
Guarantee for ERM procedure
Lemma 50  Let \(I \subset [T]\)  be any subset of time. Then with probability one, it holds that for any partition \(C_1,\dots ,C_n\)  of \((x_s,y_s)_{s \in [I]}\)  and any \(g_1,\dots ,g_n\)  distinct functions such that, for all \((x,y) \in C_n\) , \(\tilde{g}_i(x) = y\) , then for any index \(i\)  for which \(|C_i| \ge \ell +1\) ,

\(f^{\star }(x) = f^{\star }(x^{\prime })\)  for all \((x,y),(x^{\prime },y^{\prime }) \in C_i\)

\(\tilde{g}_i = {g}^\star _{f^{\star }(x)}\) , representative \(x \in C_i\)


Let \(I_1,\dots ,I_m\)  denote the times in each cluster \(C_1,\dots , C_n\) . Without loss of generality, suppose \(I_1\)  is a cluster for which \(|I_1| \ge \ell +1\)  (we may handle all simultaneously via a finite union bound.)
Item 1.
Suppose in fact that there exists \(s,s^{\prime } \in I_1\)  with \(f^{\star }(x_s) \ne f^{\star }(x_{s^{\prime }})\) . We first argue then that \({g}_1 \ne {g}^\star _k\)  for all \(k\in [K]\) . Indeed, by smoothness and the second condition of def:elldetermined, it holds that with probability 1, \({g}^\star _k(x_{\tilde{s}}) \ne {g}^\star _{k^{\prime }}(x_{\tilde{s}})\)  for all \(1 \le \tilde{s} \le T\)  and \(k \ne k^{\prime }\) . Set \(i_1 = f^{\star }(x_s)\)  and \(i_2 = f^{\star }(x_{s^{\prime }})\) . Thus, if \(g_i = {g}^\star _{k}\) , the fact \(g_i(x_s) = \mathbf {g}^\star _{f^{\star }}(x_s)\)  and \(g_i(x_{s^{\prime }}) = \mathbf {g}^\star _{f^{\star }}(x_{s^{\prime }})\)  would require both \({g}^\star _{k}(x_s) = \mathbf {g}^\star _{f^{\star }}(x_s) = {g}^\star _{i_1}(x_s)\)  and \({g}^\star _{k}(x_{s^{\prime }}) = \mathbf {g}^\star _{f^{\star }}(x_{s^{\prime }}) = {g}^\star _{i_2}(x_{s^{\prime }})\) . Thus, on the aforementioned probability one event, we would have both \(k = i_1\)  and \(k = i_2\) , which contradicts the supposition \(i_1 \ne i_2\) .
Next, let \(S \subset [T]\)  denote a set of indices. Denote \(s_{\max } = \max \lbrace s \in S\rbrace \) , and define the events
\(\mathcal {A}_{S}(g^{\prime }) := \lbrace \exists g \in \mathcal {G}\setminus \lbrace g^{\prime }\rbrace : g^{\prime }(x_{s_{\max }}) = y_{s_{\max }}, \quad \forall s \in S, g(x_{s}) = y_s\rbrace \rbrace .\) 

By the above observation that \(g_i \ne {g}^\star _{k}\)  for any \(k\) , we see that if there exists \(s,s^{\prime } \in I_1\)  with \(f^{\star }(s) \ne f^{\star }(s^{\prime })\)  with \(|I_1| \ge \ell +1\) , then one of the events \(\mathcal {A}_{S}({g}^\star _k)\)  must occur for some \(|S| \ge \ell +1\)  and \(k \in [K]\) . Since there are only finitely many such events, it suffices to show that for any fixed \(S\)  and \(k\) , \(\mathbb {P}[\mathcal {A}_{S}({g}^\star _k)] = 0\) .
Hence, fix \(S\)  and \(k\) . For a given \(S\)  with max element \(s_{\max }\) , let \({F}_{-1}\)  denote history generated by \((x_1,y_1),\dots ,(x_{s_{\max }-1},y_{s_{\max }-1})\) . Define the \(\mathcal {A}_{-1} := \lbrace \exists g \in \mathcal {G}\setminus \lbrace {g}^\star _k\rbrace : s \in S, g(x_{s}) = y_s, s \in S \setminus \lbrace s_{\max }\rbrace \rbrace \) . Then, \(\mathcal {A}_{-1}\)  is \({F}_{-1}\)  measurable and \(\mathcal {A}_{-1} \)  contains \(\mathcal {A}_{S}(g^{\prime }) \) . Hence,
\(\mathbb {P}[\mathcal {A}_{S}({g}^\star _k)] &= \operatorname{\mathbb {E}}[\mathbb {P}[\mathcal {A}_{S}({g}^\star _k) \mid {F}_{-1}]]\\&= \operatorname{\mathbb {E}}[I\lbrace \mathcal {A}_{-1}\rbrace  \cdot \mathbb {P}[\mathcal {A}_{S}({g}^\star _k) \mid {F}_{-1}]].\) 

By the first condition of def:elldetermined, \(\mathcal {A}_{-1} \)  coincides with the event \(\mathcal {A}_{-1}^{\prime } := \lbrace \exists \text{ a unique } g \in \mathcal {G}\setminus \lbrace {g}^\star _k\rbrace : s \in S, g(x_{s}) = y_s, s \in S \setminus \lbrace s_{\max }\rbrace \rbrace \)  almost surely. Hence,
\(\mathbb {P}[\mathcal {A}_{S}({g}^\star _k)] &= \operatorname{\mathbb {E}}[I\lbrace \mathcal {A}_{-1}^{\prime }\rbrace  \cdot \mathbb {P}[\mathcal {A}_{S}({g}^\star _k) \mid {F}_{S-1}]].\) 

Lastly, when \(\mathcal {A}_{-1}^{\prime }\)  holds, let \(\hat{g} \ne {g}^\star _k\)  denote the unique \(g \ne {g}^\star _k\)  consistent with examples \(s \in S \setminus \lbrace s_{\max }\rbrace \) . Since \(\hat{g}\)  is determined by \({F}_{S-1}\) , we have
\(\mathbb {P}[\mathcal {A}_{S}({g}^\star _k) \mid {F}_{S-1}] \le \mathbb {P}[\hat{g}(x_{s_{\max }}) \ne {g}^\star _k(s_{\max })] = 0,\) 

where we use that \(\hat{g}\)  is fixed, that \(\hat{g} \ne g^{\prime }\) , and the second condition of def:elldetermined. The bound follows.

Item 2.
For any fixed set of indices \(\tilde{I}\)  with \(|\tilde{I}| \ge \ell +1 \ge \ell \) , the first condition of \(\ell \) -determination (def:elldetermined) ensures then that \(\mathbb {P}[\exists g_1 \ne {g}^\star _j: g_1(x_s)= {g}^\star _j(x_s), \forall x \in \tilde{I}] = 0\) . The bound follows by union boundig over all \(\tilde{I} \subset [T]\)  and \(j \in [K]\) .

Distinctness of clustering
Claim 3 (\(\mathcal {U}_t\)  is Uncertain Set)  Fix a time \(t\) . Then, for any \((x,y) \in \mathcal {U}_t\)  and any \(i \le N_t\) , \(\hat{g}_i(x) \ne y\) .

This is true vacuously at time \(t = 1\) , when \(\mathcal {U}_t = \emptyset \) . Suppose it holds at time \(t\) , we prove it for time \(t+1\) . If \(x_t\)  is such that there exists an \(n \le N_t\)  with \(\hat{g}_i(x_t) = y_t\) , then \(\mathcal {U}_{t+1}\)  does not change from \(\mathcal {U}_t\) . Otherwise, if \(\hat{g}_n(x_t) \ne y_t\)  for all \(n \le N_t\) ,
\(\mathcal {U}_{t+1} \leftarrow \tilde{U}_t \setminus \bigcup _{i:|C_i| \ge \ell +1}\lbrace (x,y) \in \tilde{\mathcal {U}}_t: g_i(x) = y\rbrace , \quad \tilde{U}_t :=\mathcal {U}_t \cup \lbrace (x_t,y_t)\rbrace  \) 

where \(g_i\)  and \(C_i\)  are the clustering from the ERM oracle.
By the inductive hypothesis and fact that \(\hat{g}_n(x_t) \ne y_t\)  for all \(n \le N_t\) , it follows that \(\hat{g}_n(x) \ne y\)  for all \((x,y) \in \mathcal {U}_t \cup \lbrace (x_t,y_t)\rbrace  = \tilde{\mathcal {U}}_{t}\supseteq \mathcal {U}_{t+1}\) . Now, if there is some \(n: N_t < n \le N_t\)  for which \(\hat{g}_n(x) = y\) , then that \(\hat{g}_n\)  was added during the ERM step at round \(t\) : i.e. \(\hat{g}_n= g_i\)  for some \(i\)  such that \(|C_i| \ge \ell +1\) . But then \((x,y)\)  is removed form \(\mathcal {U}_{t+1}\)  by eq:Utremove.
Claim 4  Fix a time \(t\) . Then, for any \(i,j \le N_t\) , \(\hat{g}_i\ne \hat{g}_j\) .

This is trivially true at time \(t=1\) . Suppose this is true at time \(t\) , we establish the claim for time \(t+1\) . If \(x_t\)  is such that there exists an \(i \le N_t\)  with \(\hat{g}_i(x_t) = y_t\) , then \(N_{t+1} = N_t\)  and so the set of \(\hat{g}_i\) 's under consideration remains unchanged.
On the other hand, suppose there is no \(i \le N_t\)  with \(\hat{g}_i(x_t) = y_t\) . Then, all possible new \(\hat{g}_j\) 's for \(N_t < j \le N_{t+1}\)  are correct on some subset of points of \(\mathcal {U}_t \cup (x_t,y_t)\) . But by the previous claim (claim:Ut) and the assumption that, for \(i \le N_t\)  with \(\hat{g}_i(x_t) = y_t\) , no element of \(\mathcal {U}_t \cup (x_t,y_t)\)  is correctly predicted by any \(\hat{g}_i\)  for \(i \le N_t\) . Thus, none of the new \(\hat{g}_j\) 's can equal an \(\hat{g}_i\)  for \(i \le N_t\) . Moreover, by the definition the ERM oracle, defn:ermoracle, all newly added \(\hat{g}_j\) 's are distinct.

Key summary of Algorithm  REF
We now summarize the results with the following lemma.
Lemma 51  With probability 1, there exists a permutation \(\pi \)  such that

For each time \(t\)  and \(i \in [N_t]\) , \(\hat{g}_i = {g}^\star _{\pi (i)}\)

For each time \(t\)  and \(i \in [N_t]\) , \(\hat{g}_i(x) = y\)  if and only if \(f^{\star }(x) = \pi (i)\)

If \((x,y) \in \mathcal {U}_t\) , then \(\pi ^{-1}(f^{\star }(x)) > N_t\) .

Whenever \(\hat{y}_t \ne y_t\) , either \(\pi ^{-1}(f^{\star }(x)) > N_t\) , or \(\hat{k}_t := \mathcal {A}.\mathbf {\mathsf {classify}}(x_t,N_t)\)  has \(\pi (\hat{k}_t) \ne f^{\star }(x_t)\) .


For \(n = N_T\) , let \(\hat{g}_1,\dots ,\hat{g}_n \in \mathcal {G}\)  denote the functions constructed by our algorithm. Since each new \(\hat{g}_i\)  is added from a cluster with at least \(\ell +1\)  points, applying claim:rightclass (with a union bound over index sets \(I\)  ensures that \(\hat{g}_i = {g}^\star _j\) ) for some \(j \in [K]\) . This gives us a mapping \(\pi : [n] \rightarrow [K]\) . \(\pi \)  must be injective, since \({g}^\star _j\)  are distinct by assumption, and \(\hat{g}_i\)  are unique by claim:gunique (in particular, \(n \le K\) ). Thus, \(\pi \)  can be extednded to a permutation from \([K] \rightarrow [K]\) . By construction, the first item is satisfied.
The second item is a consequence of uniquenessof that the previous point, uniqueness of \(\hat{g}_i\) 's, and the second point of def:elldetermined , since we only need to union bound over finitely many times \(t \in [T]\)  and pairs \({g}^\star _i,{g}^\star _j\) 's. The third item follows similarly, by invoking claim:Ut.
For the last point, suppose \(\pi ^{-1}(f^{\star }(x_t)) \le N_t\) . Then, by the previous point, \((x_t,y_t) \notin \mathcal {U}_t\) . Thus, the algorithm classifies \(\hat{y}_t = \hat{g}_{\hat{k}_t}(x_t)\)  where \(\hat{k}_t \in [N_t]\) . But by the first point of the lemma, \(\hat{g}_{\hat{k}_t} = {g}^\star _{\pi (\hat{k}_t)}\) . So if \(\pi (\hat{k}_t) = f^{\star }(x_t)\) , then we woudl have \(\hat{g}_{\hat{k}_t}(x_t) = {g}^\star _{f^{\star }(x_t)}(x_t) = y_t\) , a contradiction.

Proof of Proposition  REF
Let \(\pi \)  denote the permutation ensured by lem:gcorrect. We may assume without loss of generality that \(\pi \)  is the identity permutation (by permuting \(\mathbf {g}^\star \) ).
Let \(k_t = f^{\star }(x_t)\) . Recalling also that \(\hat{k}_t \le N_t\) , the fourth point of lem:gcorrect ensures.
\(I\lbrace \hat{y}_t \le y_t\rbrace  &\le I\lbrace k_t > N_t\rbrace  + \sum _{t=1}^T I\lbrace \hat{k}_t \ne k_t, k_t \le N_t\rbrace \) 

First, we bound the contribution of \(I\lbrace k_t > N_t\rbrace \) :
Claim 5  \(\sum _{t=1}^T I\lbrace k_t = k,\quad k > N_t\rbrace  \le K(\ell +1)\) . Thus, \(\sum _{t=1}^TI\lbrace k_t > N_t\rbrace  \le K^2(\ell +1)\) .

Suppose \(k > N_t\) , and let \(S_{t,k} := \lbrace s \le t: f^{\star }(x_s) = k\rbrace \) , and define \(\tau _k = \max \lbrace t \in [T]: k_t > N_t, k_t = k\rbrace \) . Then
\(\sum _{t=1}^T I\lbrace k_t > N_t, k_t = k\rbrace  = |S_{\tau _k,k}|.\) 

We claim that \(|S_{\tau _k,k}| \le K(\ell +1)\) . Indeed, suppose \(|S_{\tau _k,k}| > K(\ell +1)\) . Then, for some \(t < \tau _k\) , \(|S_{t,k}| = K(\ell +1)\)  and \(k_t = k\)  and \(k > N_t\) . By lem:gcorrect, \({g}^\star _{k_t}(x_t) \ne \hat{g}_i(x_t)\)  for any \(i \le N_t\) . Hence, our algorithm executes line:erm. By the pidgeon-hole principle, there must be at least one cluster \(C_{i}: |C_i| \ge \ell +1 \)  which contains at least one \(s \in S_{t,k}\) . Hence, the update rule ensures that \(i \le N_{t+1}\)  for which \(\hat{g}_{i}(x_s) = y_s\) . But again, by lem:gcorrect (and taking the permutation to be the identity), we have \(f^{\star }(x_s) =i\) . In other words, \(i = k_s = k\) , i.e. \(k_s \le N_{t+1} \le N_{\tau _k}\) . This constradictions the definition of \(\tau _k\) .

Summarizing our argument thus far, the following holds with probability one
\(\sum _{t=1}^TI\lbrace \hat{y}_t \le y_t\rbrace  &\le K^2(\ell + 1) + \sum _{t=1}^T I\lbrace \hat{k}_t \ne k_t, k_t \le N_t\rbrace  \) 

Finally, by mirroring the proof of prop:kpiececlassification, we upper bound
\(\sum _{t=1}^T I\lbrace \hat{k}_t \ne k_t, k_t \le N_t\rbrace  \le 136 K^2 d \log (d) + 91K^2 \log \left(\frac{TK^2}{\sigma \delta }\right). \) 

The key difference between the above bound and that of prop:kpiececlassification is that we only see when get feedback \(k_t \le N_t\) , but at the same time, we only suffer a loss when \(k_t \le N_t\) . Hence, the bound follows from a near-identical argument, calling the general censored version of our binary classification prop:warmupgeneralized, modified to add the event \(\lbrace k_t \le N_t\rbrace \)  to the censoring. Combining Eq:firstbitreg,eq:secondbitreg concludes.
\(\Box \)

Non-realizable mistake bounds for the Perceptron.
For simplicity, we consider regret with respect to a fixed \(b^\star \in \mathcal {R}, w^\star \in \mathcal {B}_1^d\) , and define
\(y^\star _t = y^\star (x_t), \quad y^\star (x):= \operatorname{sign}(b^\star + \langle x_t, w^\star \rangle ).\) 

Again, we normalize \(x_t\)  that \(\max _t \Vert x_t\Vert  \le 1\) . We further assume that
\(\Vert b^\star \Vert ^2 +\Vert w^\star \Vert ^2 = 1, \quad \Vert w^\star \Vert  \ge 1/2.\) 

We show in lem:kapst at the end of this section that this is without loss of generality. We define
\(\hat{w}^\star = w^\star /\Vert w^\star \Vert .\) 

Unlike with our cutting-plane methods, we allow the adversary to deviate from a realizable clasiffier. Specifically, for each time \(t\) , the adversary selects \(x_t \sim p_t\) , and may instead choose to play some \(y_t \ne y^\star _t\) . We define,
\(N_{\mathrm {err}}:= 1+|\lbrace t:y_t \ne y^\star _t\rbrace |,\) 

and obtain non-vacuous mistake bounds provided \(N_{\mathrm {err}}\)  is sublinear in \(T\) .
Informally, our total mistake bound for the Perceptron is polynomial in the smoothness along the direction of the optimal classifier \(\hat{w}^\star \) . This is formalized in the following definition:
Definition 52 (Directional \(\sigma _{\mathrm {dir}}\) -smoothness)  We say that the adversary

is \((\sigma _{\mathrm {dir}},\hat{w}^\star )\)  directionally-smooth if \(\langle x_t,\hat{w}^\star \rangle \)  has density at most \(1/\sigma _{\mathrm {dir}}\)  with respect to the Lebesgue measure on the real line.

is, more generally, \((\sigma _{\mathrm {dir}},\alpha ,\hat{w}^\star )\)  directional-Tsybakov-smooth if \(\sup _{a \in \mathbb {R}} \mathbb {P}_{x_t \sim p_t} [\langle x_t,\hat{w}^\star \rangle \in [a,a+\eta ]] \le \eta ^{1-\alpha }/\sigma _{\mathrm {dir}}\) .

Note that a \((\sigma _{\mathrm {dir}},\alpha ,\hat{w}^\star )\) -Tsybakov adversary is is \((\sigma _{\mathrm {dir}},\hat{w}^\star )\) -smooth.

Note that defn:sigdir is a slightly weaker condition than the one consider in thm:Tsybbody in the body, as it only requires directional smoothness along \(\hat{w}^\star \)  (not uniformly).
As noted in the body, directional smoothness can differ substantially from general smoothness. We provide two examples.
Example 1 (Additive \(d\) -Ball Noise)  Suppore that at each time \(t\) , the adversary selects \(x_t = \hat{x}_t + e_t\) , where \(\Vert \hat{x}_t\Vert  \le 1/2 \) , and \(e_t \sim r\mathcal {B}_{1}^d\)  for \(r \le 1/2\)  (and, for simplicity, \(d > 1\) ). Then, the adversary is \(\sigma \) -smooth for \(\sigma = \operatorname{vol}_d(r\mathcal {B}_{1}^d)/\operatorname{vol}_d(\mathcal {B}_1^d) = r^d\) . However, if \(u \sim \mu _d\)  is drawn uniformly from the sphere, then the density \(p_1(\cdot )\)  of its first coordinate \(u_1\)  with respect to the Lebesgue measure is
\(p_1(u_1) &= \frac{\operatorname{vol}_{d-1}(\sqrt{1-u_1^2}\mathcal {B}_1^{d-1})}{\operatorname{vol}_d(\mathcal {B}_1^d)} \le \frac{\operatorname{vol}_{d-1}(\mathcal {B}_1^{d-1})}{\operatorname{vol}_d(\mathcal {B}_1^d)} = \frac{(d-1)}{2\sqrt{\pi }}.\) 

Hence, by rotational symmetry, we see that for any \(w^\star \) , the adversary is \((\sigma _{\mathrm {dir}},\hat{w}^\star )\)  directionally-smooth for \(\sigma _{\mathrm {dir}}=\frac{2\sqrt{\pi }r}{(d-1)}\) . Notice that the directional smoothness is now only polynomial in \(d\) , rather than exponential in it.

Example 2 (Additive Noise in a Random-Direction)  Again consider the additive noise setting where at each time \(t\) , the adversary selects \(x_t = \hat{x}_t + e_t\) , where \(\Vert \hat{x}_t\Vert  \le 1/2 \) . However, suppose \(e_t\)  is selected as follows: before the game, the adversary selects a direction \(\hat{e} \sim \mu _d\) , and plays \(e_t = a_t \hat{e}\) , where \(a_t\)  is drawn uniformly on the interval \([-r/2,r/2]\) . Note that this adversary need not be \(\sigma \) -smooth with respect to \(\mu _d\)  for any \(\sigma > 0\) , because after the adversary commits to \(\hat{e}\) , her smoothing is restricted to a line segment. Still, with constant probability, \(\langle \hat{e},\hat{w}^\star \rangle \ge c/d\)  for some constant \(c > 0\) . Hence, with constant probability, the adversary is \((\sigma _{\mathrm {dir}},\hat{w}^\star )\) -directionally smooth for \(\sigma _{\mathrm {dir}}= cr/d\) .

We now state our guarantee for the classical Perceptron algorithm [38]}
Theorem 53  Suppose that the adversary is \((\sigma _{\mathrm {dir}},\alpha ,\hat{w}^\star )\) -Tsybakov, and define \(\rho := \frac{2}{3-\alpha } \in [\frac{2}{3},1)\) . Then, with probability \(1-\delta \) , the Perceptron algorithm (alg:perceptron) satisfies
\(\sum _{t=1}^T I\lbrace \hat{y}_t \ne y_t\rbrace  \lesssim ( T/\sigma _{\mathrm {dir}})^{\rho } \cdot (N_{\mathrm {err}})^{1- \rho } + \log (\lceil \log T  \rceil /\delta ).\) 

Remark 4  Recall exm:dballnoise, which shows that directional smoothness \(\sigma _{\mathrm {dir}}\)  may scale as \(\sim r/d\)  when the (standard) smoothness scales as \(\sigma = r^{d}\) . Applying thm:Tsyb with \(\alpha = 0\)  and thus, \(\rho = 2/3\) , our \(( T/\sigma _{\mathrm {dir}})^{2/3} \sim (Td/r)^{2/3} \) -mistake bound interpolates between the \(\log (T/\sigma )\sim d \log (1/r) + \log (T)\)  bounds attained in this paper, and the \(\mathrm {poly}(1/\sigma ) \sim (1/r)^{\Omega (d)}\) -regret enjoyed by previous computationally efficient algorithms. In addition, we achieve a robustness to sublinearly-in-\(T\)  mistakes, which prior approaches do not.

In fact, a more general result holds, in terms of a direction-wise anti-concentration of the adversaries distributions.
Theorem 54 (Guarantee under Tsyabkov Smoothness) 
Define the anti-concentration function
\(\mathsf {p}_{\mu }(\eta ;v):= \sup _t\sup _{a \in \mathbb {R}} \mathbb {P}_{x_t \sim p_t} [\langle x_t,v \rangle \in [a,a+\eta ] \mid {F}_{t-1}] .\) 

For any fixed \(\gamma \in (0,R)\) , with least \(1-\delta \) , the number of mistakes made by the Perceptron (alg:perceptron) is at most
\(\sum _{t=1}^T I\lbrace \hat{y}_t \ne y_t\rbrace  \lesssim \frac{N_{\mathrm {err}}}{\gamma ^2} + T\mathsf {p}_{\mu }(R\gamma ,\hat{w}^\star ) + \log (1/\delta ),\) 

Proofs for the Perceptron
We begin by stating the standard guarantee for the Perceptron algorithm due to [39]}. To emphasizes its generality, we use \(\bar{x}_i\)  to denote its inputs, which we allow to have non-normalized radius \(R\) .
[!t]
[1]
Initialize  \(w_1 = \mathbf {e_1} \in \mathcal {B}_1^d\) 
\(t=1,2,\dots \) 
Recieve  \(x_t\)  and predict
\(\hat{y}_t = \operatorname{sign}(\left\langle w_t , x_t \right\rangle ), \) 

\(\hat{y}_t \ne y_t\)                                                           (blue!70!black% \(\mathbf {\mathsf {self}}.\mathbf {\mathsf {errorUpdate}}(x_t)\))
 \( w_{t+1} \leftarrow w_t + y_t x_t\)

Online Perceptron
Theorem 55 Let \((\bar{x}_i,y_i)_{i=1}^T \in \mathbb {R}^{n} \times \mathbb {R}\)  be a sequence of labeled exampled with \(\Vert \bar{x}_i\Vert  \le R\) . Fix \(\bar{w}\in \mathcal {S}^{n-1}\) , \(\gamma > 0\) , and define the margin errors
\(d_i := d_i(\bar{w},\gamma ) = \max \lbrace 0,\gamma - y_i\cdot \langle \bar{x}_i, \bar{w}\rangle \rbrace \) 

Then, the number of mistakes make by the online Perceptron is at most
\(\frac{(R+D)^2}{\gamma ^2}, \quad D = \sqrt{\sum _{i=1}^T d_i^2}\) 

The following corollary explicitly bounds the term \(D^2\) ,
Corollary 56  Fix a \(\bar{w}\in \mathcal {S}^{n-1},\gamma \in (0,R)\) . Let
\(N_{1} &:= |\lbrace i:\operatorname{sign}(y_i \cdot \langle \bar{x}_i, \bar{w}\rangle ) < 0\rbrace |\\N_{2} &:= |\lbrace 0 \le y_i\cdot \langle \bar{x}_i,\bar{w}\rangle \in [0,\gamma ]\rbrace |\) 

Then, the number of mistakes make by the online Perceptron is at most
\((8N_1 + 4)\frac{R^2}{\gamma ^2} + 2N_2\) 

[Proof of cor:mixmistakeserror] Let \(S_{1}:= \lbrace i:\operatorname{sign}(y_i \cdot \langle \bar{x}_i, \bar{w}\rangle ) \ne 1\rbrace \)  and \(S_2 := \lbrace i:\operatorname{sign}(y_i \cdot \langle \bar{x}_i, \bar{w}\rangle ) = 1, \quad y_i\cdot \langle \bar{x}_i,\bar{w}\rangle \le \gamma \rbrace \) . Note that \(N_1 := |S_1|\)  and \(N_2 := |S_2|\) . Moreover, \(S_1 \cap S_2 = \emptyset \) , and if \(i \notin (S_1 \cup S_2)\) , \(d_i := \max \lbrace 0,\gamma - y_i\cdot \langle \bar{x}_i,\bar{w}\rangle \rbrace  = 0\) . Hence,
\(D^2 &= \sum _{i \in S_1} d_i^2 + \sum _{j \in S_2} d_j^2\\&\le N_1 \max _{i \in S_1} d_i^2 + N_2 d_j^2.\) 

For \(i \in S_1\) , \(d_i^2 \le (\gamma + |\langle \bar{x}_i,\bar{w}\rangle | )^2 \le (\gamma + R)^2 \le 4R^2\) , where we used \(\gamma \le R\) . For \(j \in S_2\) , \(d_j \in [0,\gamma ]\) , so \(d_j^2 \le \gamma ^2\) . Thus, \(D^2 \le 4R^2N_1 + N_2\) . Thus,
\(\frac{(R+D)^2}{\gamma ^2} \le \frac{2R^2 +2 D^2}{\gamma ^2} \le (8N_1 + 4)\frac{R^2}{\gamma ^2} + 2N_2.\) 
We now return to our specific setting, re-adopting \(x_i\)  (not \(\bar{x}_i\) ) for features. We bound the probability that a given point \(x_i\)  does not lie within a margin \(\gamma \) .
Lemma 57  Consider the \(\mathsf {p}_{\mu }\)  function from eq:spread. Then, for any interval \(I_0 \subset \mathbb {R}\) ,
\(\mathbb {P}[y^\star _t\cdot (b^\star + \langle x_t,w^\star \rangle ) \rangle \in I_0 \mid \mathcal {F}_{t-1}] \le 2\mathsf {p}_{\mu }(2|I_0|,\hat{w}^\star ),\) 

In particular, \(\mathbb {P}[y^\star _t \cdot (b^\star + \langle x_t,w^\star \rangle ) \le \gamma \rbrace  \mid \mathcal {F}_{t-1}] \le 2\mathsf {p}_{\mu }(2\gamma ,\hat{w}^\star )\) .

[Proof of lem:smallmargin] Note that the ground truth label \(y_i\)  may depend on \(x_i\) . We circumvent this with a union bound. Let \(I_0\)  be any inverval.
\(\mathbb {P}[y^\star _t\cdot (b^\star + \langle x_t,w^\star \rangle ) \in I_0]&\le \sum _{y \in \lbrace -1,+1\rbrace } \mathbb {P}[\langle x_t,w^\star \rangle \in y I_0 ]\\&\le \sum _{y \in \lbrace -1,+1\rbrace } \mathbb {P}[b^\star + \langle x_t,\hat{w}^\star \rangle \in (b^\star + y I_0)/\Vert w^\star \Vert  ]\\&\le 2\mathsf {p}_{\mu }(\Vert w^\star \Vert ^{-1}|I_0|,\hat{w}^\star ) \le 2\mathsf {p}_{\mu }(2|I_0|,\hat{w}^\star ),\) 

where we recall our assumption \(\Vert w^\star \Vert  \ge 1/2\) .
We may now prove Proof of thm:general mistake.
[Proof of thm:general mistake] We apply cor:mixmistakeserror with \(\bar{w}= (w^\star ,b^\star )\)  and \(\bar{x}_i = (x_i,1)\) . Note then that \(\Vert \bar{x}_i\Vert ^2 = 1+\Vert x_i\Vert ^2 \le 2\) , so we may take \(R = \sqrt{2}\) . Define
\(N_{1} &:= |\lbrace i:\operatorname{sign}(y_i \cdot \langle \bar{x}_i, \Vert \bar{w}\Vert  \rangle ) < 0\rbrace |\\N_{2} &:= |\lbrace i:\operatorname{sign}(y_i \cdot \langle \bar{x}_i, \bar{w}\rangle ) = 1, y_i\cdot \langle \bar{x}_i,\bar{w}\rangle \in [0,\gamma ]\rbrace |\) 

it suffices to bound \(N_1\)  and \(N_2\) . Sice \(y^\star _t \cdot \langle \bar{x}_t, \bar{w}\rangle ) \ge 0\) , we see that each
\(N_2 = \sum _{t=1}^T Z_t, \quad Z_t := I\lbrace y_t\cdot (b^\star + \langle x_t,w^\star \rangle ) \in [0,\gamma ]\rbrace .\) 

Set \(t_{\gamma } := 2\mathsf {p}_{\mu }(2\gamma ,\hat{w}^\star ) + 8\log (1/\delta )/m\) . By lem:smallmargin,
\(\operatorname{\mathbb {E}}[Z_t \mid \mathcal {F}_{t-1}] \le 2\mathsf {p}_{\mu }(2\gamma ,\hat{w}^\star ) \le t_{\gamma }\) 

Hence, by lem:chernoff,
\(\mathbb {P}[N_2 \ge 2Tt_{\gamma }] = \mathbb {P}[\sum _{t=1}^TZ_t \ge 2Tt_{\gamma }] \le \exp (-Tt_{\gamma }/8) \le \delta .\) 

Thus, from cor:mixmistakeserror, applyied to the vectors \((x_t,1)\) , the number of mistakes is at most
\((8N_1 + 4)\frac{R^2}{\gamma ^2} + 2N_2 &\le \frac{16(N_1 + 1)}{\gamma ^2} + 2N_2 \\&\le \frac{16(N_1 + 1)}{\gamma ^2} + 4Tt_{\gamma } \\&= (8N_1 + 4)\frac{R^2}{\gamma ^2} + 8T\mathsf {p}_{\mu }(2\gamma ,\hat{w}^\star ) + 32\log (1/\delta ).\) 
[Proof of thm:Tsyb] Fix any \(N \in \mathbb {N}\) . Under the Tsybakov smoothness of the adversary,
\(\frac{N}{\gamma _N^2} + m\mathsf {p}_{\mu }(2\gamma _N,\hat{w}^\star ) \le \frac{N}{\gamma _N^2} + \sigma _{\mathrm {dir}}^{-1} T(2\gamma _N)^{1-\alpha } \lesssim \frac{N}{\gamma _N^2} + \sigma _{\mathrm {dir}}^{-1} T(\gamma _N)^{1-\alpha }\) 

Balance both terms by setting \(\gamma _N^{3-\alpha } = (N)/(\sigma _{\mathrm {dir}}^{-1} T)\) . Then, for \(\rho = \frac{2}{3-\alpha }\) , this choice of \(\gamma \)  ensures
\(\frac{N}{\gamma _N^2} &= (N)^{1-\rho }) (T/\sigma _{\mathrm {dir}})^{\rho }\) 

Since \(\gamma _N^{3-\alpha }\)  balanced the terms in eq:balance, we have
\(\frac{N}{\gamma _N^2} + T\mathsf {p}_{\mu }(2\gamma _N,\hat{w}^\star ) \lesssim (N)^{1-\rho } (T/\sigma _{\mathrm {dir}})^{\rho }\) 

For \(k \in \mathbb {N}\) , let \(\mathcal {E}_{k}:= \lbrace 2^{k-1} \le N_{\mathrm {err}}\le 2^k\rbrace \) . Then, \(\mathbb {P}[\bigcup _{k=1}^{\lceil \log T \rceil }] = 1\) . Moreover, by applying thm:general mistake with \(\gamma _{2^k}\)  for each \(k\) , we have with probability \(1-\delta \) , if \(\mathcal {E}_k\)  holds, then applying eq:gamchoice with \(N = 2^k\) ,
\(\# \text{mistakes} &\lesssim N_{\mathrm {err}}\frac{1}{\gamma _{2^k}^2} + T\mathsf {p}_{\mu }(2\gamma _{(2^k)},\hat{w}^\star ) + \log (1/\delta )\\&\lesssim (T/\sigma _{\mathrm {dir}})^{\rho } ((2^k))^{1- \rho } \cdot (\kappa ^{\star })^{\frac{2-2\alpha }{3-\alpha }} + \log (1/\delta )\\&\lesssim (T/\sigma _{\mathrm {dir}})^{\rho } (N_{\mathrm {err}})^{1- \rho } + \log (1/\delta ),\) 

where in the last line, we use \(N_{\mathrm {err}}\ge 2^k/2\)  on \(\mathcal {E}_k\) . Taking a union bound over \(k \in [\lceil \log T \rceil ]\) , with probability \(1-\delta \) ,
\(\# \text{mistakes} \lesssim (T/\sigma _{\mathrm {dir}})^{\rho } (N_{\mathrm {err}})^{1- \rho } + \log (\lceil \log T  \rceil /\delta ). \) 

Lower bound on \(1/\Vert w^\star \Vert \)
Lemma 58  There exists \((\tilde{w},\tilde{b})\)  for which \(\mathbb {P}[ y^\star (x_t) = \operatorname{sign}(\tilde{b} + \langle x_t, \tilde{w}\rangle ),~ \forall t \ge 1] = 1\) , and which satisfy \(|\tilde{b}|+|\tilde{w}|^2 = 1\) , and \(\Vert \tilde{w}\Vert  \ge 1/2\) .

We consider two cases.

Case 1: \(y^\star (x)\)  is not constant on \(\mathcal {B}^d_1\) . Let \((\tilde{b},\tilde{w})\)  be equal to \(\alpha (b^\star ,w^\star )\) , where \(\alpha \)  is chosen so that \(\tilde{b}^2 +\Vert \tilde{w}\Vert ^2 = 1\) . By positive homegenity of \(\operatorname{sign}\) , \(y^\star (x) = \operatorname{sign}(\tilde{b} + \langle x_t, \tilde{w}\rangle )\) . Since \(y^\star (x)\)  is not constant on \(\mathcal {B}^d_1\) , we must have \(\Vert \tilde{w}\Vert  \ge |\tilde{b}|\) . This means \(\Vert \tilde{w}\Vert ^2 \ge \tilde{b}^2 = 1-\Vert \tilde{w}\Vert ^2 \) . Hence, \(\Vert \tilde{w}\Vert ^2 \ge 1/2\) .

Case 2: Since \(y^\star (x) \equiv y^\star \)  is constant on \(\mathcal {B}^1_d\) . For some \(\varepsilon \)  small, set \( \tilde{b} = \sqrt{1/2+\varepsilon }y^\star \) , and set \(\tilde{w} = e_1 \sqrt{(1 - \tilde{b}^2)} = \sqrt{(1/2 - \varepsilon )}e_1\) , where \(e_1\)  is the first cannonical basis vector. By construction, \(\tilde{b}^2 + \Vert \tilde{w}\Vert ^2 = 1\) , and \(y^\star (\tilde{b} + \langle x, \tilde{w} \rangle ) \ge \sqrt{1/2+\varepsilon } - \sqrt{1/2+\varepsilon } > 0\) . To conclude, we take \(\varepsilon = 1/4\)  (though any \(\varepsilon \)  arbitrarily close to zero would work as well).

