Spectrally-normalized margin bounds for neural networks

This paper presents a margin-based multiclass generalization bound for neural networks that scales with their margin-normalized "spectral complexity": their Lipschitz constant, meaning the product of the spectral norms of the weight matrices, times a certain correction factor. This bound is empirically investigated for a standard AlexNet network trained with SGD on the mnist and cifar10 datasets, with both original and random labels; the bound, the Lipschitz constants, and the excess risks are all in direct correlation, suggesting both that SGD selects predictors whose complexity scales with the difficulty of the learning task, and secondly that the presented bound is sensitive to this complexity.

• Publication year

  2017

• Venue

  Neural Information Processing Systems

• Publication date

  2017-06-26

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1706.08498
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Foundations of Machine Learning

  2021influential reference
• SPECTRALLY-NORMALIZED MARGIN BOUNDS FOR NEURAL NETWORKS

  2018cited by this paper
• A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks

  2017cited by this paper
• Implicit Regularization in Deep Learning

  2017cited by this paper
• Parseval Networks: Improving Robustness to Adversarial Examples

  2017cited by this paper
• Understanding deep learning requires rethinking generalization

  2016influential reference
• Identity Mappings in Deep Residual Networks

  2016influential reference
• Norm-Based Capacity Control in Neural Networks

  2015cited by this paper
• Explaining and Harnessing Adversarial Examples

  2014cited by this paper
• ImageNet classification with deep convolutional neural networks

  2012influential reference
• On the equivalence of weak learnability and linear separability: new relaxations and efficient boosting algorithms

  2010cited by this paper
• On the Consistency of Multiclass Classification Methods

  2007cited by this paper
• Theory of classification : a survey of some recent advances

  2005influential reference
• Statistical Analysis of Some Multi-Category Large Margin Classification Methods

  2004cited by this paper
• Rademacher and Gaussian Complexities: Risk Bounds and Structural Results

  2003cited by this paper
• Covering Number Bounds of Certain Regularized Linear Function Classes

  2002influential reference
• Neural Network Learning: Theoretical Foundations

  1999influential reference
• Structural Risk Minimization Over Data-Dependent Hierarchies

  1998cited by this paper
• Boosting the margin: A new explanation for the effectiveness of voting methods

  1997cited by this paper
• For Valid Generalization the Size of the Weights is More Important than the Size of the Network

  1996influential reference
• The Nature of Statistical Learning

  1995cited by this paper
• A training algorithm for optimal margin classifiers

  1992cited by this paper
• Remarques sur un résultat non publié de B. Maurey

  1981influential reference

• Generalization Bounds for Transformer Channel Decoders

  2026influential citation
• Theoretical Analysis of Measure Consistency Regularization for Partially Observed Data

  2026cites this paper
• Takeuchi's Information Criteria as Generalization Measures for DNNs Close to NTK Regime

  2026cites this paper
• Generalization Bound for a Shallow Transformer Trained Using Gradient Descent

  2026cites this paper
• Revisiting Generalization Measures Beyond IID: An Empirical Study under Distributional Shift

  2026influential citation
• Training A Foundation Model to Represent Graphs as Vectors

  2026influential citation
• Understanding Generalization from Embedding Dimension and Distributional Convergence

  2026cites this paper
• Beyond NNGP: Large Deviations and Feature Learning in Bayesian Neural Networks

  2026cites this paper
• A large deviation theory analysis on the implicit bias of SGD

  2026cites this paper
• Penalizing Localized Dirichlet Energies in Low Rank Tensor Products

  2026cites this paper
• Multi-Period Martingale Optimal Transport: Classical Theory, Neural Acceleration, and Financial Applications

  2026cites this paper
• Transfer Learning Through Conditional Quantile Matching

  2026influential citation
• Multi-Domain Riemannian Graph Gluing for Building Graph Foundation Models

  2026cites this paper
• On the Generalization Behavior of Deep Residual Networks From a Dynamical System Perspective

  2026cites this paper
• Towards A Unified PAC-Bayesian Framework for Norm-based Generalization Bounds

  2026cites this paper
• Reconciling grokking with statistical learning theory through the lens of norm- and stability-based generalization bounds

  2026cites this paper
• Sufficient Conditions for Stability of Minimum-Norm Interpolating Deep ReLU Networks

  2026cites this paper
• Generalization Bounds of Stochastic Gradient Descent in Homogeneous Neural Networks

  2026cites this paper
• Exploring 3D Dataset Pruning

  2026cites this paper
• PRISM: Parallel Reward Integration with Symmetry for MORL

  2026cites this paper
• Optimization, Generalization and Differential Privacy Bounds for Gradient Descent on Kolmogorov-Arnold Networks

  2026cites this paper
• Rethinking Intelligence: Brain-like Neuron Network

  2026cites this paper
• Deep learning and the geometry of compactness in stability and generalization

  2026cites this paper
• A Gap Between Decision Trees and Neural Networks

  2026cites this paper
• Minimax Rates for Hyperbolic Hierarchical Learning

  2026cites this paper
• Margin-Based Generalisation Bounds for Quantum Kernel Methods under Local Depolarising Noise

  2026cites this paper
• Data-Driven Deep MIMO Detection:Network Architectures and Generalization Analysis

  2026cites this paper
• Compact Circulant Layers with Spectral Priors

  2026cites this paper
• The Price of Robustness: Stable Classifiers Need Overparameterization

  2026cites this paper
• Bound to Disagree: Generalization Bounds via Certifiable Surrogates

  2026cites this paper
• Spectral Manifold Regularization for Stable and Modular Routing in Deep MoE Architectures

  2026cites this paper
• Supervised learning for robust predictive control: Safe and tunable approach

  2026cites this paper
• Bi-directional distillation enabling progressive lightweight model training in edge computing-based federated learning

  2026cites this paper
• Operator ℓ∞→ℓ∞ norm of products of random matrices with iid entries

  2026cites this paper
• Approximation, Estimation and Optimization Errors for a Deep Neural Network

  2025cites this paper
• Generalization Bound for a General Class of Neural Ordinary Differential Equations

  2025influential citation
• Learning on the Fly: Rapid Policy Adaptation via Differentiable Simulation

  2025cites this paper
• Frozen in Time: Parameter-Efficient Time Series Transformers via Reservoir-Induced Feature Expansion and Fixed Random Dynamics

  2025cites this paper
• The Docking Game: Loop Self-Play for Fast, Dynamic, and Accurate Prediction of Flexible Protein-Ligand Binding

  2025cites this paper
• Algebraic Approach to Ridge-Regularized Mean Squared Error Minimization in Minimal ReLU Neural Network

  2025cites this paper
• Beyond Universal Approximation Theorems: Algorithmic Uniform Approximation by Neural Networks Trained with Noisy Data

  2025cites this paper
• Training Transformers with Enforced Lipschitz Constants

  2025cites this paper
• Learning Beyond Euclid: Curvature-Adaptive Generalization for Neural Networks on Manifolds

  2025cites this paper
• The Serial Scaling Hypothesis

  2025cites this paper
• Optimization-Induced Dynamics of Lipschitz Continuity in Neural Networks

  2025cites this paper
• Probabilistic Variational Contrastive Learning

  2025cites this paper
• Sparse Autoencoders, Again?

  2025cites this paper
• Generalization Bound of Gradient Flow through Training Trajectory and Data-dependent Kernel

  2025influential citation
• ODD: Overlap-aware Estimation of Model Performance under Distribution Shift

  2025cites this paper
• Cross-regularization: Adaptive Model Complexity through Validation Gradients

  2025cites this paper
• A Scalable Approach for Safe and Robust Learning via Lipschitz-Constrained Networks

  2025cites this paper
• TITAN: Query-Token based Domain Adaptive Adversarial Learning

  2025cites this paper
• Understanding Generalization in Node and Link Prediction

  2025cites this paper
• Deep Neural Network-Based Detection of Modulated Jamming in Free-Space Optical Systems: Theory and Performance Under Atmospheric Fading

  2025cites this paper
• Decoupled Latent Diffusion Model for Enhancing Image Generation

  2025cites this paper
• Where and How to Enhance: Discovering Bit-Width Contribution for Mixed Precision Quantization

  2025cites this paper
• Effective Sample Size and Generalization Bounds for Temporal Networks

  2025cites this paper
• On Task Vectors and Gradients

  2025cites this paper
• Offline-to-Online Learning Enabled Robust Control for Uncertain Robotic Systems Pursuing Constraint-Following

  2025cites this paper
• Calibrated Uncertainty Estimation for Trustworthy Deep IoT Attack Detection

  2025cites this paper
• Dyna-ESN: Efficient Deep Reinforcement Learning for Partially Observable Dynamic Spectrum Access

  2025cites this paper
• Quantum latent distributions in deep generative models

  2025cites this paper
• Data Can Speak for Itself: Quality-guided Utilization of Wireless Synthetic Data

  2025cites this paper
• GWSC-SegMamba: Gate Wavelet Spatial Convolution Enhanced State Space Model for Multi-Temporal Agricultural Land Segmentation

  2025cites this paper
• Discrete Functional Geometry of ReLU Networks via ReLU Transition Graphs

  2025cites this paper
• Deep Copula Classifier: Theory, Consistency, and Empirical Evaluation

  2025cites this paper
• Rock and a Hard Place: Attack Hardness in Neural Network-assisted Side Channel Analysis

  2025cites this paper
• Scalable Complexity Control Facilitates Reasoning Ability of LLMs

  2025cites this paper
• Rethinking Predictive Modeling for LLM Routing: When Simple kNN Beats Complex Learned Routers

  2025cites this paper
• TAROT: Towards Essentially Domain-Invariant Robustness with Theoretical Justification

  2025cites this paper
• Implicit bias produces neural scaling laws in learning curves, from perceptrons to deep networks

  2025cites this paper
• LIFT the Veil for the Truth: Principal Weights Emerge after Rank Reduction for Reasoning-Focused Supervised Fine-Tuning

  2025cites this paper
• Generalization Bounds in Hybrid Quantum-Classical Machine Learning Models

  2025cites this paper
• Practical Robust Formation Control for Nonlinear Multiagent Systems via Generative Adversarial Learning Framework: Theory and Experiment

  2025cites this paper
• Reasoning without Regret

  2025cites this paper
• Improved Scalable Lipschitz Bounds for Deep Neural Networks

  2025cites this paper
• Non-vacuous Generalization Bounds for Deep Neural Networks without any modification to the trained models

  2025influential citation
• Efficient and Accurate Estimation of Lipschitz Constants for Hybrid Quantum-Classical Decision Models

  2025cites this paper
• Representation Retrieval Learning for Heterogeneous Data Integration

  2025cites this paper
• HiQ-Lip: A Hierarchical Quantum-Classical Method for Global Lipschitz Constant Estimation of ReLU Networks

  2025influential citation
• APECS: Adaptive Personalized Control System Architecture

  2025cites this paper
• When Do Transformers Outperform Feedforward and Recurrent Networks? A Statistical Perspective

  2025influential citation
• Principal Eigenvalue Regularization for Improved Worst-Class Certified Robustness of Smoothed Classifiers

  2025cites this paper
• AutoUAD: Hyper-parameter Optimization for Unsupervised Anomaly Detection

  2025cites this paper
• Adaptive Classification of Interval-Valued Time Series

  2025influential citation
• Architecture independent generalization bounds for overparametrized deep ReLU networks

  2025cites this paper
• Generalization memorization machine for regression

  2025cites this paper
• Generalization Analysis for Supervised Contrastive Representation Learning under Non-IID Settings

  2025cites this paper
• Learning Guarantee of Reward Modeling Using Deep Neural Networks

  2025cites this paper
• Demystifying Topological Message-Passing with Relational Structures: A Case Study on Oversquashing in Simplicial Message-Passing

  2025cites this paper
• Why and When Deep is Better than Shallow: An Implementation-Agnostic State-Transition View of Depth Supremacy

  2025cites this paper
• Enhancing Certified Robustness via Block Reflector Orthogonal Layers and Logit Annealing Loss

  2025influential citation
• Temperature is All You Need for Generalization in Langevin Dynamics and other Markov Processes

  2025cites this paper
• Learnable Kernel Density Estimation for Graphs

  2025cites this paper
• On The Statistical Complexity of Offline Decision-Making

  2025cites this paper
• S<inline-formula><tex-math notation="LaTeX">$^{2}$</tex-math><alternatives><mml:math><mml:msup><mml:mrow/><mml:mn>2</mml:mn></mml:msup></mml:math><inline-graphic xlink:href="jin-ieq1-3577384.gif"/></alternatives></inline-formula>O: Enhancing Adversarial Training With Second-Order Statistics of Weigh

  2025influential citation
• Reparameterized LLM Training via Orthogonal Equivalence Transformation

  2025cites this paper
• On the Generalization of Data-Assisted Control in port-Hamiltonian Systems (DAC-pH)

  2025cites this paper
• EarlyBirdFL: Leveraging Early Bird Ticket Networks for Enhanced Personalized Learning

  2025cites this paper
• An Effective Gram Matrix Characterizes Generalization in Deep Networks

  2025cites this paper