Learning via Surrogate PAC-Bayes
This work addresses computational bottlenecks in PAC-Bayes learning for researchers and practitioners, offering a novel method to improve efficiency in algorithm design, though it is incremental in building upon existing PAC-Bayes frameworks.
The paper tackles the computational inefficiency of optimizing PAC-Bayes generalization bounds by introducing a strategy that replaces the empirical risk with low-dimensional projections, enabling more efficient iterative learning algorithms. It demonstrates this approach in meta-learning with theoretical guarantees and applies it to an industrial biochemical problem.
PAC-Bayes learning is a comprehensive setting for (i) studying the generalisation ability of learning algorithms and (ii) deriving new learning algorithms by optimising a generalisation bound. However, optimising generalisation bounds might not always be viable for tractable or computational reasons, or both. For example, iteratively querying the empirical risk might prove computationally expensive. In response, we introduce a novel principled strategy for building an iterative learning algorithm via the optimisation of a sequence of surrogate training objectives, inherited from PAC-Bayes generalisation bounds. The key argument is to replace the empirical risk (seen as a function of hypotheses) in the generalisation bound by its projection onto a constructible low dimensional functional space: these projections can be queried much more efficiently than the initial risk. On top of providing that generic recipe for learning via surrogate PAC-Bayes bounds, we (i) contribute theoretical results establishing that iteratively optimising our surrogates implies the optimisation of the original generalisation bounds, (ii) instantiate this strategy to the framework of meta-learning, introducing a meta-objective offering a closed form expression for meta-gradient, (iii) illustrate our approach with numerical experiments inspired by an industrial biochemical problem.