Entanglement raises the Fisher effective dimension of parameterized quantum circuits, producing a PAC-Bayes generalization bound that correctly ranks circuits of identical parameter count by their train-test gap.
hub
Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data
23 Pith papers cite this work. Polarity classification is still indexing.
23
Pith papers citing it
abstract
One of the defining properties of deep learning is that models are chosen to have many more parameters than available training data. In light of this capacity for overfitting, it is remarkable that simple algorithms like SGD reliably return solutions with low test error. One roadblock to explaining these phenomena in terms of implicit regularization, structural properties of the solution, and/or easiness of the data is that many learning bounds are quantitatively vacuous when applied to networks learned by SGD in this "deep learning" regime. Logically, in order to explain generalization, we need nonvacuous bounds. We return to an idea by Langford and Caruana (2001), who used PAC-Bayes bounds to compute nonvacuous numerical bounds on generalization error for stochastic two-layer two-hidden-unit neural networks via a sensitivity analysis. By optimizing the PAC-Bayes bound directly, we are able to extend their approach and obtain nonvacuous generalization bounds for deep stochastic neural network classifiers with millions of parameters trained on only tens of thousands of examples. We connect our findings to recent and old work on flat minima and MDL-based explanations of generalization.
hub tools
citation-role summary
background 2
method 1
citation-polarity summary
representative citing papers
Proves that Rademacher complexity of depth-d compositional trees over finite operator vocabulary is controlled by (K b L)^{d} / sqrt(n) under Lipschitz conditions on operators.
FisherAdapTune uses temporal drift in Fisher geometry, measured by scale-invariant Jensen-Shannon distance, to progressively freeze stabilized parameter groups during fine-tuning, reporting gains on segmentation and zero-shot transfer.
Proposes pointwise Riemannian Dimension from feature eigenvalues to derive tighter, representation-aware generalization bounds for deep networks in the nonlinear regime.
Sharper information-theoretic generalization bounds for differentially private algorithms obtained via typicality arguments that improve prior mutual-information results and add new maximal-leakage bounds.
LE-SAM inverts SAM by fixing the loss budget instead of the parameter-space radius, yielding better generalization across benchmarks.
ConquerNet smooths quantile ReLU networks with convolution for easier training and establishes minimax-optimal nonasymptotic risk bounds over Besov function classes.
A new PAC-Bayesian framework for GCNs derives a family of generalization bounds that embed graph topology via structured sensitivity matrices from spatial and spectral perspectives, recovering prior bounds as special cases while claiming tighter results.
Compositionality emerges in neural networks only in a narrow depth-connectivity regime, with gradient descent converging to fractured solutions outside it.
Derives second-order path-kernel interpolation formulas for gradient descent, SGD, and momentum training, adding curvature terms and a concentration estimate around the expected prediction.
CRAFT is a Pareto-front prompt optimizer that allocates scarce LLM validation calls to candidates near the current front using accuracy- and cost-oriented generators plus NSGA-II retention.
SAM solves a min-max problem to locate flat low-loss regions, improving generalization on CIFAR, ImageNet and label-noise tasks.
Derives algorithm-dependent generalization bounds for neural nets using multilevel entropic regularization and proposes a Metropolis-simulated multi-scale Gibbs training procedure tested on a two-layer net for MNIST.
Derives a generalization bound for GP-based symbolic regression that decomposes the gap into structure-selection complexity and constant-fitting complexity under tree constraints.
Path-norm initialization-dependent bounds with a new peeling technique give non-vacuous generalization guarantees for overparameterized shallow networks with Lipschitz activations.
SAMPLe adds dual gradient constraints (ERM alignment plus full-batch orthogonality) to SAM-style prompt learning and raises harmonic-mean base-to-new accuracy across CoOp, CoCoOp, MaPLe, TCP and CoPrompt.
Experiments show low mutual information does not reliably correspond to geometric compression via class-wise clustering in CEB and dropout networks; the negative nonlinear link can reverse with training changes, suggesting generalization confounds the connection.
A gradient-similarity complexity measure that generalizes polynomial degree, kernel length scale, neighbor count, tree splits, and forest size while offering insights into double descent.
Learning a margin-based confidence ranker for LLM judges improves agreement-target success in cascaded selective evaluation compared to heuristic confidence scores.
The paper argues flat minima are an illusion and that a reparameterization-invariant 'weakness' score predicts generalization where raw sharpness fails.
Sparse MLPs trained via SET plus neuron pruning achieve competitive performance on 15 datasets while pruning ~50% of hidden neurons and keeping parameter count linear in neuron count.
Generalization error bounds of order O(n^{-1/2}) (dimension-free) are derived for two-layer neural networks with Lipschitz losses under independent test data, and O(n^{-1/(d_in + d_out)}) without independence, using Wasserstein distances and SGD moment bounds.
Review of neural scaling laws and their relation to constraints and inductive biases when applying machine learning to physics problems.
citing papers explorer
-
Entanglement as a Structural Complexity Axis: A PAC-Bayesian View of Generalization in Quantum Policies and Value Functions
Entanglement raises the Fisher effective dimension of parameterized quantum circuits, producing a PAC-Bayes generalization bound that correctly ranks circuits of identical parameter count by their train-test gap.
-
Sample Complexity of Scientific Discovery: PAC Learnability of Compositional Function Trees
Proves that Rademacher complexity of depth-d compositional trees over finite operator vocabulary is controlled by (K b L)^{d} / sqrt(n) under Lipschitz conditions on operators.
-
Fisher-Guided Progressive Parameter Selection for Adaptive Fine-Tuning
FisherAdapTune uses temporal drift in Fisher geometry, measured by scale-invariant Jensen-Shannon distance, to progressively freeze stabilized parameter groups during fine-tuning, reporting gains on segmentation and zero-shot transfer.
-
Pointwise Generalization in Deep Neural Networks
Proposes pointwise Riemannian Dimension from feature eigenvalues to derive tighter, representation-aware generalization bounds for deep networks in the nonlinear regime.
-
On the Generalization Error of Differentially Private Algorithms via Typicality
Sharper information-theoretic generalization bounds for differentially private algorithms obtained via typicality arguments that improve prior mutual-information results and add new maximal-leakage bounds.
-
Fix the Loss, Not the Radius: Rethinking the Adversarial Perturbation of Sharpness-Aware Minimization
LE-SAM inverts SAM by fixing the loss budget instead of the parameter-space radius, yielding better generalization across benchmarks.
-
ConquerNet: Convolution-Smoothed Quantile ReLU Neural Networks with Minimax Guarantees
ConquerNet smooths quantile ReLU networks with convolution for easier training and establishes minimax-optimal nonasymptotic risk bounds over Besov function classes.
-
Topology-Aware PAC-Bayesian Generalization Analysis for Graph Neural Networks
A new PAC-Bayesian framework for GCNs derives a family of generalization bounds that embed graph topology via structured sensitivity matrices from spatial and spectral perspectives, recovering prior bounds as special cases while claiming tighter results.
-
Compositionality Emerges in a Narrow Depth-Connectivity Regime: Architecture Constraints and Solution Manifolds
Compositionality emerges in neural networks only in a narrow depth-connectivity regime, with gradient descent converging to fractured solutions outside it.
-
Second-Order Path Kernel Interpolation Formulas in Machine Learning
Derives second-order path-kernel interpolation formulas for gradient descent, SGD, and momentum training, adding curvature terms and a concentration estimate around the expected prediction.
-
CRAFT: Cost-aware Refinement And Front-aware Tuning of Prompts
CRAFT is a Pareto-front prompt optimizer that allocates scarce LLM validation calls to candidates near the current front using accuracy- and cost-oriented generators plus NSGA-II retention.
-
Sharpness-Aware Minimization for Efficiently Improving Generalization
SAM solves a min-max problem to locate flat low-loss regions, improving generalization on CIFAR, ImageNet and label-noise tasks.
-
Chaining Meets Chain Rule: Multilevel Entropic Regularization and Training of Neural Nets
Derives algorithm-dependent generalization bounds for neural nets using multilevel entropic regularization and proposes a Metropolis-simulated multi-scale Gibbs training procedure tested on a two-layer net for MNIST.
-
On the Generalization Bounds of Symbolic Regression with Genetic Programming
Derives a generalization bound for GP-based symbolic regression that decomposes the gap into structure-selection complexity and constant-fitting complexity under tree constraints.
-
Towards Initialization-dependent and Non-vacuous Generalization Bounds for Overparameterized Shallow Neural Networks
Path-norm initialization-dependent bounds with a new peeling technique give non-vacuous generalization guarantees for overparameterized shallow networks with Lipschitz activations.
-
SAMPLe: SAM-based Optimizer for Prompt Learning in VLMs
SAMPLe adds dual gradient constraints (ERM alignment plus full-batch orthogonality) to SAM-style prompt learning and raises harmonic-mean base-to-new accuracy across CoOp, CoCoOp, MaPLe, TCP and CoPrompt.
-
Geometric and Information Compression of Representations in Deep Learning
Experiments show low mutual information does not reliably correspond to geometric compression via class-wise clustering in CEB and dropout networks; the negative nonlinear link can reverse with training changes, suggesting generalization confounds the connection.
-
A Rigorous, Tractable Measure of Model Complexity
A gradient-similarity complexity measure that generalizes polynomial degree, kernel length scale, neighbor count, tree splits, and forest size while offering insights into double descent.
-
Margin-Adaptive Confidence Ranking for Reliable LLM Judgement
Learning a margin-based confidence ranker for LLM judges improves agreement-target success in cascaded selective evaluation compared to heuristic confidence scores.
-
Are Flat Minima an Illusion?
The paper argues flat minima are an illusion and that a reparameterization-invariant 'weakness' score predicts generalization where raw sharpness fails.
-
On improving deep learning generalization with adaptive sparse connectivity
Sparse MLPs trained via SET plus neuron pruning achieve competitive performance on 15 datasets while pruning ~50% of hidden neurons and keeping parameter count linear in neuron count.
-
Generalization error bounds for two-layer neural networks with Lipschitz loss function
Generalization error bounds of order O(n^{-1/2}) (dimension-free) are derived for two-layer neural networks with Lipschitz losses under independent test data, and O(n^{-1/(d_in + d_out)}) without independence, using Wasserstein distances and SGD moment bounds.
-
Statistical Properties of Training & Generalization
Review of neural scaling laws and their relation to constraints and inductive biases when applying machine learning to physics problems.