  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.
