PAC-Bayesian Bounds on Rate-Efficient Classifiers

We derive analytic bounds on the noise invariance of majority vote classifiers operating on compressed inputs. Specifically, starting from recent bounds on the true risk of majority vote classifiers, we extend the applicability of PAC-Bayesian theory to quantify the resilience of majority votes to input noise stemming from compression. The derived bounds are intuitive in binary classification settings, where they can be measured as expressions of voter differentials and voter pair agreement. By combining measures of input distortion with analytic guarantees on noise invariance, we prescribe rate-efficient machines to compress inputs without affecting subsequent classification. Our validation shows how bounding noise invariance can inform the compression stage for any majority vote classifier such that worst-case implications of bad input reconstructions are known, and inputs can be compressed to the minimum amount of information needed prior to inference. 1. We introduce the notion of rate-efficient classifiers to PAC-Bayesian theory, and derive relevant expressions of noise-invariance to define such classifiers. 2. We derive unsupervised general bounds on noiseinvariance, and specialize them to binary majority vote classifiers comprising linear kernels. 3. We combine noise-invariance bounds with measures of reconstruction loss to realize rate-efficient machines that bound errors resulting from lossy compression.