The above definition naturally extends to multiple labels [1]}; we denote the multiclass Littlestone dimension by \(\mathrm {Ldim}_k(\cdot )\) . We next recall the well-known notion of VC dimension that characterizes PAC-learnability of binary
concept classes [2]}.
