Risk Bounds for Learning via Hilbert Coresets

Abstract

We develop a formalism for constructing stochastic upper bounds on the expected full sample risk for supervised classification tasks via the Hilbert coresets approach within a transductive framework. We explicitly compute tight and meaningful bounds for complex datasets and complex hypothesis classes such as state-of-the-art deep neural network architectures. The bounds we develop exhibit nice properties: i) the bounds are non-uniform in the hypothesis space, ii) in many practical examples, the bounds become effectively deterministic by appropriate choice of prior and training data-dependent posterior distributions on the hypothesis space, and iii) the bounds become significantly better with increase in the size of the training set. We also lay out some ideas to explore for future research.

arXiv comment16 pages, 2 figures

References in corpus (7)

• Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data
• Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networks
• Uniform convergence may be unable to explain generalization in deep learning
• Automated Scalable Bayesian Inference via Hilbert Coresets
• Explicit Learning Curves for Transduction and Application to Clustering and Compression Algorithms
• De-randomized PAC-Bayes Margin Bounds: Applications to Non-convex and Non-smooth Predictors
• MUSCLE: Strengthening Semi-Supervised Learning Via Concurrent Unsupervised Learning Using Mutual Information Maximization