Learning with Gradient Descent and Weakly Convex Losses
arXiv:2101.04968
Abstract
We study the learning performance of gradient descent when the empirical risk is weakly convex, namely, the smallest negative eigenvalue of the empirical risk's Hessian is bounded in magnitude. By showing that this eigenvalue can control the stability of gradient descent, generalisation error bounds are proven that hold under a wider range of step sizes compared to previous work. Out of sample guarantees are then achieved by decomposing the test error into generalisation, optimisation and approximation errors, each of which can be bounded and traded off with respect to algorithmic parameters, sample size and magnitude of this eigenvalue. In the case of a two layer neural network, we demonstrate that the empirical risk can satisfy a notion of local weak convexity, specifically, the Hessian's smallest eigenvalue during training can be controlled by the normalisation of the layers, i.e., network scaling. This allows test error guarantees to then be achieved when the population risk minimiser satisfies a complexity assumption. By trading off the network complexity and scaling, insights are gained into the implicit bias of neural network scaling, which are further supported by experimental findings.
arXiv commentUpdated References
References in corpus (20)
- Neural Tangent Kernel: Convergence and Generalization in Neural Networks
- Searching for Exotic Particles in High-Energy Physics with Deep Learning
- A Convergence Theory for Deep Learning via Over-Parameterization
- A Mean Field View of the Landscape of Two-Layers Neural Networks
- On Exact Computation with an Infinitely Wide Neural Net
- On Lazy Training in Differentiable Programming
- Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks
- Empirical Analysis of the Hessian of Over-Parametrized Neural Networks
- Eigenvalues of the Hessian in Deep Learning: Singularity and Beyond
- An Investigation into Neural Net Optimization via Hessian Eigenvalue Density
- Hessian-based Analysis of Large Batch Training and Robustness to Adversaries
- Norm-Based Capacity Control in Neural Networks
- Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks
- Data-Dependent Stability of Stochastic Gradient Descent
- Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints
- Generalization Properties and Implicit Regularization for Multiple Passes SGM
- Stability and Convergence Trade-off of Iterative Optimization Algorithms
- Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passes
- Loss landscapes and optimization in over-parameterized non-linear systems and neural networks
- Implicit Regularization of Accelerated Methods in Hilbert Spaces