Generalization Bounds for Meta-Learning via PAC-Bayes and Uniform Stability

We are motivated by the problem of providing strong generalization guarantees\nin the context of meta-learning. Existing generalization bounds are either\nchallenging to evaluate or provide vacuous guarantees in even relatively simple\nsettings. We derive a probably approximately correct (PAC) bound for\ngradient-based meta-learning using two different generalization frameworks in\norder to deal with the qualitatively different challenges of generalization at\nthe "base" and "meta" levels. We employ bounds for uniformly stable algorithms\nat the base level and bounds from the PAC-Bayes framework at the meta level.\nThe result of this approach is a novel PAC bound that is tighter when the base\nlearner adapts quickly, which is precisely the goal of meta-learning. We show\nthat our bound provides a tighter guarantee than other bounds on a toy\nnon-convex problem on the unit sphere and a text-based classification example.\nWe also present a practical regularization scheme motivated by the bound in\nsettings where the bound is loose and demonstrate improved performance over\nbaseline techniques.\n