Shifting, One-Inclusion Mistake Bounds and Tight Multiclass Expected Risk Bounds
Shifting, One-Inclusion Mistake Bounds and Tight Multiclass Expected Risk Bounds
Benjamin I. P. Rubinstein,P. Bartlett,J. Rubinstein
2006 · DOI: 10.7551/mitpress/7503.003.0154
Neural Information Processing Systems · 30 Citations
TLDR
A density bound of n (≦n-1d-1) / (≤nd) < d, which positively resolves a conjecture of Kuzmin & Warmuth relating to their unlabeled Peeling compression scheme and also leads to an improved mistake bound for the randomized (deterministic) one-inclusion strategy for all d.