Risk Bounds for Learning via Hilbert Coresets
This provides theoretical risk bounds for practitioners using complex models like deep neural networks, though it appears incremental in extending coreset methods to transductive settings.
The paper tackles the problem of providing theoretical guarantees for machine learning models by developing stochastic upper bounds on expected risk using Hilbert coresets within a transductive framework, achieving tight bounds for complex datasets and deep neural networks that improve with larger training sets.
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.