Generalization Bound of Gradient Flow through Training Trajectory and Data-dependent Kernel

2025/06/12 by Yilan Chen, Zhichao Wang, Chen, Yilan +8
Computer Science · Physics and Astronomy · #Artificial neural network #Convergence (economics) #Generalization #Gradient descent #Kernel (algebra) #Model Reduction and Neural Networks #Multiple kernel learning #Neural Networks and Applications #Norm (philosophy) #Reproducing kernel Hilbert space #Stability (learning theory) #Upper and lower bounds

paper · pdf · doi:10.48550/arxiv.2506.11357

published in arXiv (Cornell University) (Cornell University)

openalex publication_date 2025/06/12 · openalex created_date 2025/10/11 · openalex updated_date 2026/08/05

Abstract

Gradient-based optimization methods have shown remarkable empirical success, yet their theoretical generalization properties remain only partially understood. In this paper, we establish a generalization bound for gradient flow that aligns with the classical Rademacher complexity bounds for kernel methods-specifically those based on the RKHS norm and kernel trace-through a data-dependent kernel called the loss path kernel (LPK). Unlike static kernels such as NTK, the LPK captures the entire training trajectory, adapting to both data and optimization dynamics, leading to tighter and more informative generalization guarantees. Moreover, the bound highlights how the norm of the training loss gradients along the optimization trajectory influences the final generalization performance. The key technical ingredients in our proof combine stability analysis of gradient flow with uniform convergence via Rademacher complexity. Our bound recovers existing kernel regression bounds for overparameterized neural networks and shows the feature learning capability of neural networks compared to kernel methods. Numerical experiments on real-world datasets validate that our bounds correlate well with the true generalization gap.

Citations

• Dynamical Decoupling of Generalization and Overfitting in Large Two-Layer Networks
• Information-Theoretic Generalization Bounds for Deep Neural Networks
• Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Models
• SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics
• Learning Single-Index Models with Shallow Neural Networks
• Neural Networks can Learn Representations with Gradient Descent
• Beyond Lipschitz: Sharp Generalization and Excess Risk Bounds for Full-Batch GD
• Demystifying the Neural Tangent Kernel from a Practical Perspective: Can it be trusted for Neural Architecture Search without training?
• Thinking Outside the Ball: Optimal Learning with Gradient Descent for Generalized Linear Stochastic Convex Optimization
• Random Feature Amplification: Feature Learning and Generalization in Neural Networks
• Deformed semicircle law and concentration of nonlinear random matrices for ultra-wide neural networks
• Generalization Guarantees for Neural Architecture Search with Train-Validation Split
• Neural Architecture Search on ImageNet in Four GPU Hours: A Theoretically Inspired Perspective
• Understanding deep learning (still) requires rethinking generalization
• Generalization Bounds for Noisy Iterative Algorithms Using Properties of Additive Noise Channels
• Information-Theoretic Generalization Bounds for Stochastic Gradient Descent
• Tight Bounds on the Smallest Eigenvalue of the Neural Tangent Kernel for Deep ReLU Networks
• The Interpolation Phase Transition in Neural Networks: Memorization and Generalization under Lazy Training
• On the Rademacher Complexity of Linear Hypothesis Sets
• Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses
• Neural Architecture Search without Training
• PyTorch: An Imperative Style, High-Performance Deep Learning Library
• Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimates
• Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks
• On Exact Computation with an Infinitely Wide Neural Net
• How do infinite width bounded norm networks look in function space?
• On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learning
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• Reconciling modern machine learning practice and the bias-variance trade-off
• Gradient Descent Finds Global Minima of Deep Neural Networks
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• A Convergence Theory for Deep Learning via Over-Parameterization
• Just Interpolate: Kernel "Ridgeless" Regression Can Generalize
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Implicit Bias of Gradient Descent on Linear Convolutional Networks
• Stronger generalization bounds for deep nets via a compression approach
• Generalization Error Bounds for Noisy, Iterative Algorithms
• The Implicit Bias of Gradient Descent on Separable Data
• Stability and Generalization of Learning Algorithms that Converge to Global Optima
• A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks
• Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints
• Exploring Generalization in Deep Learning
• Spectrally-normalized margin bounds for neural networks
• Information-theoretic analysis of generalization capability of learning algorithms
• On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima
• Deep Residual Learning for Image Recognition
• Train faster, generalize better: Stability of stochastic gradient descent
• Norm-Based Capacity Control in Neural Networks
• In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning
• Suprema of Chaos Processes and the Restricted Isometry Property
• A Note on the PAC Bayesian Theorem

Related

• Gradient flow in the kernel learning problem
• Approximation and Gradient Descent Training with Neural Networks
• Training Linear Neural Networks: Non-Local Convergence and Complexity Results
• Gradient flow in parameter space is equivalent to linear interpolation in output space
• Beyond NTK with Vanilla Gradient Descent: A Mean-Field Analysis of Neural Networks with Polynomial Width, Samples, and Time