SGD converges exponentially fast in non-convex over-parametrized learning.
problem Convergence of SGD in non-convex, over-parametrized learning.
method Analysis of SGD with constant step size for non-convex functions satisfying the PL condition.
result Exponential convergence of SGD for non-convex functions satisfying the PL condition.
This paper shows linear over-parametrization suffices for shallow neural networks to fit training data.
problem Training shallow neural networks with optimal over-parametrization.
method Used a simple variant of stochastic gradient descent.
result Linear over-parametrization is sufficient for shallow neural networks to fit training data.
A phase transition affects loss landscape and generalization in neural networks.
problem Understanding the transition between under- and over-parametrization in neural networks.
method Analytical and empirical study of fully-connected networks with hinge loss.
result The generalization error shows three phases: initial decay, increase until a cusp, and slow decay.
Gradient descent can find better tensor decompositions than lazy training in over-parameterized settings.
problem Finding better tensor decompositions in over-parameterized settings.
method Gradient descent on over-parameterized tensor decomposition problems.
result Gradient descent can find an approximate tensor decomposition with rank m = O ∗ ( r 2.5 l log d ) m = O^*(r^{2.5l}\log d) m = O ∗ ( r 2.5 l log d ) , while lazy training requires m = Ω ( d l − 1 ) m = Ω(d^{l-1}) m = Ω ( d l − 1 ) . Estimates for neural network risk nearly match Monte Carlo error rates.
problem Understanding the performance of two-layer neural networks.
method Established a priori estimates for the population risk of two-layer neural networks.
result The new estimates are nearly optimal and depend only on function norms, not model parameters.
Study shows neural network parameters converge to ridgelet spectrum.
problem Characterization of local minima in over-parametrized neural networks.
method Developed ridgelet transform to analyze neural network parameters.
result Distribution of parameters converges to ridgelet spectrum.
Over-parametrization speeds up learning a single neuron model.
problem Understanding why over-parametrization accelerates learning in neural networks.
method Studied a simple model of a single teacher neuron with quadratic activation, showing how over-parametrization can lead to faster convergence.
result Over-parametrization helps gradient descent enter the neighborhood of a global optimal solution faster.
Improves deep learning theory by reducing over-parametrization size.
problem Deep learning theory over-parametrization issues.
method Used Matrix Chernoff Bound to improve over-parametrization size.
result Improved over-parametrization size over previous results.
In this paper we aim to formally explain the phenomenon of fast convergence of SGD observed in modern machine learning. The key observation is that most modern learning architectures are over-parametrized and are trained to interpolate the data by driving the empirical loss (classification and regression) close to zero…
New approach uncovers neural network performance beyond linearized models.
problem Empirical performance of neural networks exceeds linearized models.
method Randomizing neural networks to couple with quadratic and higher-order terms in Taylor expansion.
result Concrete generalization and expressivity results on randomized networks match NTK and can be better by a dimension factor.
Dr. of Crosswise reduces over-parametrization in neural networks.
problem Reduction of over-parametrization in neural networks.
method Introduces a new operand for rapid computation in neural networks framework.
result Reduces over-parametrization in neural networks.
Study bounds graph neural networks' over-parameterized error.
problem Understanding graph neural networks' performance in over-parameterized regimes.
method Developed mean-field regime bounds for graph convolutional and message passing neural networks.
result Established upper bounds with a convergence rate of O ( 1 / n ) O(1/n) O ( 1/ n ) for generalization error. Deep neural networks are often trained in the over-parametrized regime (i.e. with far more parameters than training examples), and understanding why the training converges to solutions that generalize remains an open problem. Several studies have highlighted the fact that the training procedure, i.e. mini-batch Stochas…
Minimum-norm solutions generalize well in over-parametrized neural networks.
problem Generalization error in over-parametrized neural networks.
method Analyzing three models: random feature model, two-layer neural network, and residual network.
result Generalization error for minimum-norm solutions is comparable to Monte Carlo rate, up to logarithmic terms.
Gradient descent trains shallow neural networks to approximate functions in 1D.
problem Approximating functions in 1D with shallow neural networks trained by gradient descent.
method Gradient descent optimization of non-convex weight space for finite width networks in 1D.
result Gradient descent can approximate functions in 1D with a minimal number of weights, balancing practical performance and theoretical capabilities.
The paper shows how gradient flow on over-parametrized tensor decomposition behaves like deflation.
problem Understanding the training dynamics of gradient flow on tensor decomposition.
method Empirical observation and mathematical proof of gradient flow dynamics for orthogonally decomposable tensors.
result Gradient flow dynamics for orthogonally decomposable tensors follows a tensor deflation process, recovering all tensor components.
New insights into overfitting peaks in generalization error for l 2 l_2 l 2 and l 1 l_1 l 1 penalized interpolation.
problem Understanding the phenomenon of overfitting peaks in generalization error for modern machine learning models.
method Introducing a generative and fitting model pair (MiSpaR) and deriving analytical risk curves for l 2 l_2 l 2 and l 1 l_1 l 1 penalties. result The overfitting peak can be dissociated from the point of model flexibility, complicating the interpretation of overfitting as a boundary between classical and modern regimes.
Lazy training and mean field regimes studied for TD learning with nonlinear function approximation.
problem Approximating value function for MRP with TD learning and nonlinear functions.
method Lazy training and mean field scaling of parameters analyzed for convergence.
result Lazy training leads to exponential convergence to local/global minimizers, while mean field scaling results in all fixed points being minimizers.
SMD outperforms SGD in over-parametrized linear models for certain data distributions.
problem Understanding the generalization performance of SMD in over-parametrized linear models.
method Analysis of SMD for over-parametrized linear models with binary classification.
result Empirical validation of SMD's generalization performance differing from SGD.
Study on neural networks with quadratic activation functions, focusing on optimization and generalization.
problem Understanding the dynamics and generalization of neural networks with quadratic activation in the over-parametrized regime.
method Teacher-student scenario, empirical loss landscape analysis, gradient descent dynamics, numerical experiments.
result Conditions for the neural network to recover the teacher and achieve small generalization error.
Deep ensembles don't necessarily improve calibration in low data regimes.
problem Calibration issues in deep learning models, especially in low data regimes.
method Examination of data-augmentation, ensembling, and post-processing calibration methods.
result Standard ensembling techniques can lead to less calibrated models in low data regimes.
Paper shows faster convergence to local-minimizers in over-parametrized models under interpolation-like conditions.
problem Escaping saddle-points in over-parametrized models.
method Stochastic and deterministic optimization algorithms under interpolation-like conditions.
result Oracle complexity of PSGD and SCRN algorithms to reach ε ε ε -local-minimizer matches or improves upon deterministic rates. The paper shows over-confidence in models isn't just due to over-parametrization.
problem Over-confidence in machine learning models, especially in binary classification.
method Theoretical analysis of logistic regression and other binary classification problems.
result Logistic regression is inherently over-confident in certain settings, but over-confidence is not always the case.
Despite existing work on ensuring generalization of neural networks in terms of scale sensitive complexity measures, such as norms, margin and sharpness, these complexity measures do not offer an explanation of why neural networks generalize better with over-parametrization. In this work we suggest a novel complexity m…
Investigates how SGD behaves in high-dimensional neural networks, distinguishing between global convergence and local minima.
problem Understanding the behavior of SGD in high-dimensional shallow neural networks.
method Extends statistical physics analysis to study SGD dynamics, focusing on mean-field/hydrodynamic regime and learning rate.
result Identifies the critical number of hidden units and learning rate for SGD to avoid local minima.
Gradient descent in neural networks analyzed using RKBS for broader applicability.
problem Analyzing neural network training in the over-parametrized limit.
method Constructing an exact power-series representation of neural networks in RKBS, proving replicability of gradient descent sequences.
result Gradient descent sequences can be exactly replicated by regularized sequential learning in RKBS, providing new theoretical insights.
New function class characterizes loss landscape of deep neural networks without over-parametrization.
problem Complex loss landscape of deep neural networks without over-parametrization.
method Proposed a novel class of functions to characterize loss landscape without over-parametrization.
result Gradient-based optimizers possess theoretical guarantees of convergence under the new function class assumption.
Gradient descent optimizes neural networks and random features similarly, achieving zero loss fast.
problem Optimizing two-layer neural networks and random feature models under gradient descent.
method Comprehensive analysis of gradient descent dynamics, considering various network widths and data sizes.
result Gradient descent achieves zero training loss exponentially fast in the over-parametrized regime.
We provide new theoretical insights on why over-parametrization is effective in learning neural networks. For a k k k hidden node shallow network with quadratic activation and n n n training data points, we show as long as k ≥ 2 n k \ge \sqrt{2n} k ≥ 2 n , over-parametrization enables local search algorithms to find a \emph{globally} op…
One-bit quantization and sparsification improve multiclass classification with strong regularization.
problem Overfitting mislabeled data in multiclass classification.
method Linear regression with regularization and one-bit quantization/sparsification.
result Sparse and one-bit solutions perform almost as well as the optimal solution with f ( ⋅ ) = ∥ ⋅ ∥ 2 2 f(\cdot) = \|\cdot\|_2^2 f ( ⋅ ) = ∥ ⋅ ∥ 2 2 . Gradient descent learns over-param neural nets better than NTK.
problem Learning over-parametrized neural networks with ReLU activations.
method Gradient descent from random initialization on a Gaussian input distribution.
result Gradient descent achieves population loss o ( 1 / d ) o(1/d) o ( 1/ d ) , while NTK achieves Ω ( 1 / d ) Ω(1/d) Ω ( 1/ d ) . Gradient descent dynamics in neural networks show quenching and activation phases.
problem Understanding training dynamics in neural networks.
method Numerical and phenomenological study of gradient descent algorithm for two-layer neural networks.
result Gradient descent dynamics exhibit quenching and activation phases in under-parametrized networks.
New method reduces over-parametrization in neural networks, ensuring sparsity and finite network size.
problem Over-parametrization leads to too many active neurons in neural networks, especially with large data.
method Investigates a nonconvex regularization method for shallow ReLU networks.
result Locally optimal networks are finite even with infinite data, maintaining approximation guarantees and network size bounds.
Convolutional neural networks converge quickly with gradient descent.
problem Learning efficient image classifiers with over-parameterized networks.
method Gradient descent for training over-parametrized CNNs with global average-pooling.
result Gradient descent quickly reduces the misclassification risk of CNNs.
The paper provides approximation guarantees for neural networks trained with gradient flow.
problem Approximating neural networks trained with gradient flow in continuous L 2 ( S d − 1 ) L_2(\mathbb{S}^{d-1}) L 2 ( S d − 1 ) -norm. method NTK argument for non-convex second but last layer, under-parametrized regime.
result Gradient flow convergence guarantees for neural networks under Sobolev smoothness assumptions.
Gradient descent achieves fast convergence for approximating functions with two-layer neural networks.
problem Approximating continuous functions with two-layer neural networks.
method Gradient descent combined with generic chaining technique from probability theory.
result Gradient descent yields an exponential convergence rate for two-layer neural networks without needing a large width relative to the number of data points.
Improved complexity for machine learning optimization methods.
problem Optimizing over-parametrized models in machine learning.
method Stochastic conditional gradient methods with interpolation-like conditions.
result Improved oracle complexities for finding optimal solutions.
ADA augments data using AR replicas for robust regression.
problem Improving robustness in nonlinear over-parametrized regression.
method Extends Anchor regression (AR) for data augmentation, using replicas of modified samples.
result ADA provides more robust regression predictions compared to state-of-the-art solutions.
Interpolation improves performance in nearest neighbor algorithms without over-parametrization.
problem Achieving zero training error in deep learning without over-parametrization.
method Introduced a class of interpolated weighting schemes in nearest neighbor algorithms.
result Mild data interpolation strictly improves prediction performance and statistical stability.
High-dimensional regression models struggle with resampling methods.
problem Estimating uncertainty in high-dimensional supervised regression tasks.
method Investigation of bootstrap, subsampling, and jackknife methods in high-dimensional generalized linear models.
result Resampling methods exhibit double-descent behavior and are inconsistent in high dimensions.
Gradient descent finds global minima in deep neural networks with skip-connections.
problem Finding global minima in deep neural networks with skip-connections.
method Analysis of the gradient descent algorithm in over-parametrized deep neural networks with skip-connections.
result Gradient descent can find global minima exponentially fast in the over-parametrized regime.
Stochastic Gradient Descent introduces noise in training, affecting model decision boundaries.
problem Understanding the impact of noise in SGD on model decision boundaries.
method Characterized SGD and persistent SGD dynamics in a neural network model, measuring noise magnitude in both under- and over-parametrized regimes.
result Noisier algorithms lead to wider decision boundaries in constraint satisfaction problems.
Noether's theorem clarifies how symmetries in neural networks influence learning.
problem Understanding how symmetries in neural networks affect learning.
method Systematic study of symmetry interactions with learning algorithms using Noether's theorem.
result Symmetries impose restrictions on the optimization path, leading to conserved quantities.
New method shows AdaGrad converges globally to neural network minima.
problem Convergence of adaptive gradient methods for neural networks.
method Proposed adaptive gradient method for over-parameterized neural networks.
result Converges to global minimum in polynomial time for two-layer networks.
Estimates how much samples inform neural network training and function.
problem Measuring informativeness of samples in neural networks.
method Linearized network approximations for efficient computation.
result Efficient approximations show good accuracy for real-world models.
Improved DNN calibration without sacrificing accuracy.
problem Poor calibration of over-parametrized DNNs in safety-critical applications.
method Decoupling feature extraction and classification layers, and applying Gaussian priors.
result Significant improvement in model calibration with minimal training cost.
Study how data structure impacts classification performance in overparametrized models.
problem Understanding the role of data structure in overparametrized models.
method Analytical and statistical physics methods applied to structured data.
result Data structure significantly affects the performance of overparametrized models, particularly for logistic loss.
Transfer learning offers little benefit in medical imaging tasks.
problem Understanding transfer learning's impact on medical imaging tasks.
method Evaluation of transfer learning on two large-scale medical imaging tasks.
result Simple, lightweight models perform comparably to ImageNet architectures.