Tight Bounds for the Expected Risk of Linear Classifiers and PAC-Bayes Finite-Sample Guarantees
Jean Honorio, Tommi Jaakkola · 2014
We analyze the expected risk of linear classi-fiers for a fixed weight vector in the “min-imax ” setting. That is, we analyze the worst-case risk among all data distribu-tions with a given mean and covariance. We provide a simpler proof of the tight polynomial-tail bound for general random variables. For sub-Gaussian random vari-ables, we derive a novel tight exponential-tail bound. We also provide new PAC-Bayes finite-sample guarantees when training data is available. Our “minimax ” generalization bounds are dimensionality-independent and O(√1/m) for m samples. 1