New empirical PAC-Bayes bound for Markov chains with finite state space.
problem Lack of empirical bounds for Markov chains with temporal dependence.
method Proved a new PAC-Bayes bound for Markov chains, providing an empirical pseudo-spectral gap.
result First fully empirical PAC-Bayes bound for Markov chains with finite state space.
Meta-learning bounds derived using PAC-Bayes theory for improved generalization.
problem Uncertainty in generalization performance for meta-learning with new tasks.
method PAC-Bayes relative entropy bounds and empirical risk minimization (ERM) method.
result Competitive generalization performance and rapid convergence with data-dependent prior.
New PAC-Bayes training method improves model generalization for unbounded loss.
problem Improving generalization of complex models under unbounded loss.
method Established new PAC-Bayes bound for unbounded loss, jointly training prior and posterior.
result Outperforms existing PAC-Bayes training algorithms and matches ERM accuracy.
New inequality for ternary variables improves on existing measures.
problem Analyzing excess losses and weighted majority votes with ternary random variables.
method Developed a split-kl inequality and its PAC-Bayes extension.
result Outperforms existing inequalities in certain regimes.
New PAC-Bayes bounds derived using Legendre transform and f-divergences.
problem Deriving PAC-Bayes bounds under various assumptions.
method Combining Legendre transform and Fenchel--Young inequality to derive change-of-measure inequalities.
result Extended PAC-Bayesian guarantees under tailored assumptions.
New bound improves on weighted majority vote risk estimation.
problem Improving risk estimation for weighted majority vote.
method Novel Chebyshev-Cantelli inequality and PAC-Bayes-Bennett inequality.
result New bounds improve on existing methods.
This paper improves meta-learning by developing new PAC-Bayes bounds.
problem Meta-learning generalization gap across multiple tasks.
method Upper bounding convex functions linking environment and task-level losses.
result New PAC-Bayes bounds for meta-learning with improved algorithms.
New algorithm optimizes PAC-Bayes bound without surrogate loss.
problem Mismatch between optimisation objective and generalisation bound in stochastic neural networks.
method Proposes a novel training algorithm that optimizes the PAC-Bayesian bound directly.
result Empirical results show improved performance over existing PAC-Bayesian training methods.
New method optimises learning via surrogate PAC-Bayes bounds.
problem Computational intractability of optimising generalisation bounds.
method Iteratively optimising surrogate training objectives derived from PAC-Bayes bounds.
result Iteratively optimising surrogates implies optimising original generalisation bounds.
New data-dependent priors improve PAC-Bayes bounds.
problem Improving PAC-Bayes bounds for nonconvex learning.
method Using data to learn a conditional expectation of the posterior, given a subset of training data.
result Data-dependent oracle priors lead to stronger PAC-Bayes bounds.
The developments of Rademacher complexity and PAC-Bayesian theory have been largely independent. One exception is the PAC-Bayes theorem of Kakade, Sridharan, and Tewari (2008), which is established via Rademacher complexity theory by viewing Gibbs classifiers as linear operators. The goal of this paper is to extend thi…
New PAC-Bayes bound controls multiple error types simultaneously.
problem Current PAC-Bayes bounds are limited to scalar metrics.
method Bounding KL divergence between empirical and true probabilities of multiple error types.
result First PAC-Bayes bound for rich information-rich certificates.
The paper improves risk certificate tightness for neural networks using PAC-Bayes bounds.
problem Improving the usability of risk certificates for neural networks based on PAC-Bayes bounds.
method Theoretical contributions including KL divergence bounds, efficient methodology for optimization, and methods for optimizing non-differentiable objectives.
result First non-vacuous generalization bounds on CIFAR-10 for neural networks.
The VAE's reconstruction ability is studied using PAC-Bayes theory.
problem Understanding the performance of VAEs for unseen data.
method PAC-Bayes theory is applied to analyze VAE's reconstruction error.
result Generalization bounds on VAE's reconstruction error are provided.
Paper refines PAC-Bayes bounds for bandit problems.
problem Improving probabilistic bounds for off-policy learning.
method Optimizes PAC-Bayesian bounds using a new parameter optimization approach.
result Provides two parameter-free PAC-Bayes bounds that nearly match optimal rates.
The Probably Approximately Correct (PAC) Bayes framework (McAllester, 1999) can incorporate knowledge about the learning algorithm and (data) distribution through the use of distribution-dependent priors, yielding tighter generalization bounds on data-dependent posteriors. Using this flexibility, however, is difficult,…
PAC-Bayes bounds for Gibbs posteriors derived via singular learning theory.
problem Generalization bounds for overparameterized models with data-dependent priors.
method Explicit non-asymptotic PAC-Bayes bounds using singular learning theory.
result Explicit posterior-averaged risk bounds for overparameterized models.
New method certifies deep graph classifiers with tighter risk bounds.
problem Certifying the reliability of deep graph classifiers.
method Linearized deep assignment flows with random initial conditions, using PAC-Bayes risk certification.
result Computes tighter out-of-sample risk certificates efficiently.
Improved PAC-Bayesian bounds by considering example difficulty.
problem Improving generalization bounds in machine learning.
method Introducing a modified excess risk that leverages example difficulty to reduce variance and tighten PAC-Bayesian bounds.
result Tighter PAC-Bayesian generalization bounds for machine learning models.
The paper analyzes the generalizability of linear autoencoders and multivariate linear regression.
problem Limited theoretical understanding of linear autoencoders' performance.
method Proposes a PAC-Bayes bound for multivariate linear regression and shows LAEs as constrained models.
result The proposed PAC-Bayes bound is tight and correlates with practical metrics.
Logistic regression gets a new, simpler uniform bound.
problem Finding a uniform bound for logistic regression's empirical risk.
method PAC-Bayes approach with second-order expansion and Rademacher-complexity bounds.
result Provides a dimension-free uniform concentration bound.
Paper tightens PAC-Bayes bounds using coin-betting for better estimates.
problem Estimating mean of random elements with possibly S-dependent parameters.
method Refined PAC-Bayes proof strategy based on coin-betting framework.
result Derives tighter concentration inequalities for all sample sizes.
PAC-Bayesian framework for fairness in stochastic and deterministic classifiers.
problem Theoretical guarantees on fairness for balancing predictive risk and fairness constraints.
method PAC-Bayesian framework for both stochastic and deterministic classifiers, covering a broad class of fairness measures.
result Derives generalization bounds for fairness, demonstrating tightness with empirical evaluation.
This work extends PAC-Bayesian learning guarantees to non-compact symmetries and non-invariant data.
problem Lack of theoretical guarantees explaining the benefits of symmetries in machine learning models.
method Adapting and tightening PAC-Bayes bounds for non-compact symmetries and non-invariant data distributions.
result Theoretical evidence that symmetric models are preferable for symmetric data, beyond compact groups and invariant distributions.
This work analyzes benefits and limitations of data augmentation and feature averaging in deep learning models.
problem Theoretical understanding of incorporating invariance into deep learning models is lacking.
method Data augmentation and feature averaging are analyzed in the context of invariance in deep learning.
result Training with data augmentation leads to better estimates of risk and gradients, and feature averaging reduces generalization error with convex losses.
PAC-Bayes framework fails on simple 1D linear classification task.
problem Proving the learnability of simple 1D linear classification tasks using PAC-Bayes bounds.
method Demonstrated a specific 1D linear classification task that PAC-Bayes cannot analyze.
result PAC-Bayes framework cannot prove learnability of simple 1D linear classification tasks.
New PAC-Bayes method updates priors without losing confidence information.
problem Lack of sequential prior updates in PAC-Bayes without losing confidence information.
method Recursive PAC-Bayes decomposition of expected loss.
result Sequential prior updates with no information loss.
We show that Entropy-SGD (Chaudhari et al., 2017), when viewed as a learning algorithm, optimizes a PAC-Bayes bound on the risk of a Gibbs (posterior) classifier, i.e., a randomized classifier obtained by a risk-sensitive perturbation of the weights of a learned classifier. Entropy-SGD works by optimizing the bound's p…
PAC-Bayes bound requires prior to place mass on high-performing predictors.
problem Explaining generalization in machine learning.
method Analyzing necessary conditions for PAC-Bayes bounds to provide meaningful generalization guarantees.
result Achieving a target generalisation level requires the prior to place sufficient mass on high-performing predictors.
New method reduces computational cost for estimating PAC-Bayes bounds.
problem High computational cost in estimating PAC-Bayes bounds.
method General alternative method that makes computational savings.
result Reduces computational cost on the order of the dataset size.
PAC-Bayesian theory applied to learning optimization algorithms with generalization guarantees.
problem Learning optimization algorithms with provable generalization guarantees and explicit trade-offs.
method PAC-Bayes theory applied to learning-to-optimize, reformulating the learning procedure into a one-dimensional minimization problem.
result Learned optimization algorithms outperform deterministic worst-case analysis algorithms, even in the limit case of guaranteed convergence.
New online GP algorithm offers performance guarantees for streaming data.
problem Training and inference of GPs require all historic data, limiting online decision-making.
method Developed a new theoretical framework based on PAC-Bayes theory, optimizing empirical risk and parameter divergence.
result Offers both a guarantee of generalized performance and good accuracy.
Improves model accuracy for neural nets in stochastic dynamics with partial prior knowledge.
problem Stability and accuracy in neural nets modeling stochastic dynamics with many parameters.
method Three steps: probabilistic weights, partial knowledge incorporation, and PAC-Bayesian training.
result Improved model fit with partial and noisy prior knowledge.
New PAC-Bayes bounds use Wasserstein distances to improve generalization.
problem Lack of geometric properties in existing PAC-Bayes bounds.
method Developed new PAC-Bayes bounds with Wasserstein distances.
result Optimization guarantees translate to good generalization abilities.
Researchers estimate optimal PAC-Bayes bounds using Hamiltonian Monte Carlo.
problem Estimating tight PAC-Bayes bounds with restricted posterior families.
method Sampling from optimal Gibbs posterior using Hamiltonian Monte Carlo, estimating KL divergence, and proposing high-probability bounds.
result Significant tightness gaps in PAC-Bayes bounds, up to 5-6% in some cases.
Introduces PAC-Bayes bounds for understanding learning procedures.
problem Understanding the generalization ability of learning procedures.
method PAC-Bayesian bounds and their applications to neural networks.
result Simplified version of localization technique described.
The paper improves PAC-Bayes bounds for data-dependent predictors.
problem Guaranteeing the quality of predictions on unseen examples.
method Basic PAC-Bayes inequality for stochastic kernels, leading to various bounds.
result Validates PAC-Bayes bounds without fixed 'data-free' priors and bounded losses.
The paper improves PAC-Bayes bounds for losses with finite moments.
problem Bounding generalization for losses with heavy tails and finite moments.
method Truncation method and PAC-Bayes bounds for unbounded losses with heavy tails and bounded variance.
result Bounds interpolate between slow and fast rates depending on the moment.
Survey and compare PAC-Bayes bounds for bandit problems.
problem Designing and evaluating bandit algorithms with strong performance guarantees.
method PAC-Bayes bounds applied to bandit problems.
result PAC-Bayes bounds useful for offline bandit algorithms, but loose for online algorithms.
Unified derivation of PAC-Bayes and MI bounds for general VC classes with fast rates.
problem Generalization bounds for machine learning models with VC classes.
method Unified derivation of conditional PAC-Bayesian and mutual information bounds, including MAC-Bayesian bounds.
result Nontrivial bounds for general VC classes and faster rates for specific conditions.
New PAC-Bayes bounds for heavy-tailed losses using supermartingales.
problem Extending PAC-Bayes bounds to heavy-tailed losses.
method Using supermartingales and bounded variance assumption.
result PAC-Bayes generalization bounds for heavy-tailed losses.
We explore the family of methods "PAC-Bayes with Backprop" (PBB) to train probabilistic neural networks by minimizing PAC-Bayes bounds. We present two training objectives, one derived from a previously known PAC-Bayes bound, and a second one derived from a novel PAC-Bayes bound. Both training objectives are evaluated o…
The cold posterior effect is explored through PAC-Bayes bounds for small sample sizes.
problem The cold posterior effect in approximate Bayesian inference for small datasets.
method Investigation through PAC-Bayes generalization bounds, focusing on temperature parameter λ.
result The temperature parameter λ in PAC-Bayes bounds captures the cold posterior effect.
Investigates tight PAC-Bayes bounds for small datasets.
problem Tightening PAC-Bayes bounds for small data.
method Generic PAC-Bayes theorem, meta-learning, synthetic tasks.
result PAC-Bayes bounds are competitive with Chernoff bounds but not as tight.
This paper tackles non-vacuous generalization bounds in ReLU networks by resolving rescaling invariances.
problem Non-vacuous generalization guarantees for ReLU networks with rescaling invariances.
method Proposes a lifted representation to resolve rescaling invariances and studies KL-based rescaling-invariant PAC-Bayes bounds.
result KL-based rescaling-invariant PAC-Bayes bounds provide tighter guarantees and resolve discrepancies in network complexity.
Data structure affects deep learning performance, study finds.
problem Understanding why deep learning performs poorly on typical datasets.
method Analyzed input correlation matrices and network Hessians, developed PAC-Bayes bounds.
result Sloppy eigenspectra in input data correlate with poor deep learning performance.
Paper presents new training methods for neural networks with tighter risk certificates.
problem Training probabilistic neural networks with tighter risk certificates.
method Derived from PAC-Bayes bounds, two training objectives implemented for the first time in neural networks.
result Competitive test set errors and non-vacuous risk bounds with tighter values than previous results.
New method uses quotient predictor space for better PAC-Bayes bounds, reducing KL divergence and improving model performance.
problem Overparameterized models with continuous symmetries can lead to biased predictions.
method Perform PAC-Bayesian analysis on quotient predictor space, constructing a canonical prior that reflects model's implicit bias.
result The new prior reduces KL divergence and improves model performance in experiments.