The Agnostic Case
**General Answer 2: The Agnostic Case**
A number of reviewers have asked for our thoughts concerning the agnostic case. Let us briefly review what is known, and summarize our initial observations:
In the _standard_ (non-transductive) agnostic online setting, Ben-David et al. [1] showed that $R_T(\mathcal{H})$, the agnostic online regret for a hypothesis class $\mathcal{H}$ with Littlestone dimension $d_L$ for horizon size $T$ satisfies
$\Omega(\sqrt{d_L \cdot T}) \leq R_T(\mathcal{H}) \leq O(\sqrt{d_L \cdot T \log T}).$
Later, Alon et al. [2] showed that the precise regret is $R_T(\mathcal{H}) = \Theta(\sqrt{d_L \cdot T})$.
For the _transductive_ agnostic online setting, we make the following novel observation:
**Claim.** _Let $\mathcal{H}$ be a hypothesis class with VC dimension $d_V > 0$. Then the agnostic transductive regret for $\mathcal{H}$ with horizon $T$ is $R_T(\mathcal{H}) = \tilde{\Theta}(\sqrt{d_V\cdot T})$._
An upper bound of $O(\sqrt{d_{V}\cdot T\log(T/d_{V})})$ follows from the Perles–Sauer–Shelah lemma + the multiplicative weights algorithm.
**Proof sketch for lower bound.**
Let $d=d_{V}$, and let $x_1,\dots,x_d$ be VC shattered by $\mathcal{H}$. Assume for simplicity that $T = kd$ for some $k \in \mathbb{N}$. The transductive adversary selects the sequence $x_1^1,\dots,x_1^k,x_2^1,\dots,x_2^k,\dots,x_d^1,\dots,x_d^k$, where $x_i^j = x_i$ for all $j \in [k]$ and $i \in [d]$. The adversary chooses all labels to be i.i.d. uniform random bits. By Khinchine’s Inequality (See Lemma 8.2 in [3]), for each $i \in [d]$ the expected gap between the majority label and the minority label in the subsequence $x_i^1,\dots,x_i^k$ is of order $\Omega(\sqrt{k})$. Hence, by an averaging argument, any learner will have excess error of order $\Omega(\sqrt{k})$ on roughly half of the $d$ subsequences $x_i^1,\dots,x_i^k$. This implies the desired lower bound of $\Omega(\sqrt{k} \cdot d) = \Omega(\sqrt{d\cdot T})$.
Additionally:
* For trivial classes (e.g., a class that contains a single function), the regret is $0$.
* For classes with finite VC and finite Littlestone dimension, the regret is $\Theta(\sqrt{d_L \cdot T})$ (by [2]), namely, the $\log(T)$ factor from the upper bound for VC classes is removed.
* For classes with infinite VC, the regret is $T$.
Hence, for non-trivial classes, finiteness of the VC dimension determines the asymptotic dependence of the regret on $T$ up to logarithmic factors.
However, the regret for VC classes remains open because there is a gap of a $\sqrt{\log(T)}$ multiplicative factor between the best known upper and lower bounds. In other words, we don’t know whether there is just one case or several cases.
_____
[1] Shai Ben-David, Dávid Pál, and Shai Shalev-Shwartz. Agnostic Online Learning. COLT 2009.
[2] Alon, N., Ben-Eliezer, O., Dagan, Y., Moran, S., Naor, M. and Yogev, E. Adversarial laws of large numbers and optimal regret in online classification. STOC 2021.
[3] N. Cesa-Bianchi and G. Lugosi. Prediction, learning, and games. Cambridge University Press, 2006.