Deep ReLU networks can be simplified to a three-layer model.
problem Understanding the behavior of deep neural networks.
method Constructive proof and algorithm to transform deep networks into shallow ones.
result Deep ReLU networks can be represented by a simpler three-layer structure.
Modified ReLU networks improve regression estimation rates.
problem Regression estimation with smooth functions.
method Using modified ReLU neural networks with specific weight modifications.
result Empirical risk minimizers achieve minimax rate of prediction.
ReLU networks implicitly favor low-rank solutions, but not as strongly as linear networks.
problem Understanding implicit regularization in ReLU networks for rank minimization.
method Analysis of gradient flow on ReLU networks, empirical testing.
result Gradient flow on ReLU networks does not necessarily minimize ranks, unlike in linear networks.
The study examines Fisher information matrices and neural tangent kernels for simple ReLU networks with random weights.
problem Understanding the relationship between Fisher information matrices and neural tangent kernels for 2-layer ReLU networks.
method Analyzes Fisher information matrices and neural tangent kernels for 2-layer ReLU networks with random hidden weights, focusing on spectral decomposition and eigenfunctions.
result Obtained an approximation formula for functions represented by 2-layer neural networks.
Improved bounds on neural network expressivity.
problem Understanding neural network expressivity and approximation capabilities.
method Improved bounds on the maximal number of linear regions of ReLU-networks.
result New insights into the expressivity of neural networks.
Neural networks with REctified Linear Unit (ReLU) activation functions (a.k.a. ReLU networks) have achieved great empirical success in various domains. Nonetheless, existing results for learning ReLU networks either pose assumptions on the underlying data distribution being e.g. Gaussian, or require the network size an…
Single ReLU neuron's gradient dynamics reveal support vectors as key to generalization.
problem Understanding the generalization capability of ReLU networks.
method Examined gradient flow dynamics and support vectors in single ReLU neuron training.
result Support vectors play a crucial role in the generalization of ReLU networks.
New insights into how linear classifiers and leaky ReLU networks can overfit without harming generalization.
problem Understanding conditions for benign overfitting in linear classifiers and leaky ReLU networks.
method Utilizing Karush--Kuhn--Tucker (KKT) conditions for margin maximization.
result Satisfaction of KKT conditions leads to benign overfitting in linear classifiers and leaky ReLU networks.
Bayesian approach fixes overconfidence in ReLU networks, even slightly.
problem Overconfidence in ReLU networks far from training data.
method Theoretical analysis of approximate Gaussian distributions on ReLU weights, and empirical validation.
result Even a simplistic Bayesian approximation fixes overconfidence issues.
Real world data often exhibit low-dimensional geometric structures, and can be viewed as samples near a low-dimensional manifold. This paper studies nonparametric regression of Hölder functions on low-dimensional manifolds using deep ReLU networks. Suppose n n n training data are sampled from a Hölder function in $\mathc…
Study reveals properties of local minima in ReLU networks.
problem Understanding the loss landscape of neural networks.
method Theoretical analysis of one-hidden-layer ReLU networks.
result All differentiable local minima are global within certain regions.
Most random ReLU networks are vulnerable to small, Euclidean adversarial perturbations.
problem Vulnerability of ReLU networks to adversarial attacks.
method Analysis of random ReLU networks with decreasing dimensions, using gradient flow and descent.
result Most examples can be perturbed by small Euclidean distances via gradient methods.
Gradient flow in ReLU networks biases towards generalization but makes them vulnerable to adversarial attacks.
problem Generalization vs. Adversarial Robustness in ReLU Networks
method Analysis of gradient flow in two-layer ReLU networks with clustered data.
result Gradient flow biases towards generalization but also makes networks vulnerable to adversarial attacks.
Deep ReLU networks escape from the origin via saddle points with a low-rank bias.
problem Understanding the dynamics of gradient descent in deep ReLU networks.
method Analysis of escape directions and singular values of weight matrices.
result The first singular value of the ℓ \ell ℓ -th layer weight matrix is at least ℓ 1 4 \ell^{\frac{1}{4}} ℓ 4 1 larger than any other singular value. Deep neural networks can approximate complex functions through repeated compositions of a fixed-size ReLU network.
problem Understanding the expressive power of deep neural networks through function compositions.
method Demonstrated the surprising expressive power of repeated compositions of a single fixed-size ReLU network.
result Repeated compositions of a single fixed-size ReLU network can approximate 1-Lipschitz continuous functions on [ 0 , 1 ] d [0,1]^d [ 0 , 1 ] d with an error O ( r − 1 / d ) \mathcal{O}(r^{-1/d}) O ( r − 1/ d ) . Deep ReLU networks can approximate smooth functions nearly optimally.
problem Approximating smooth functions with deep neural networks.
method Using Taylor expansions and deep ReLU network approximations, the paper establishes optimal approximation error bounds.
result Deep ReLU networks of width and depth O ( N ln N ) \mathcal{O}(N\ln N) O ( N ln N ) and O ( L ln L ) \mathcal{O}(L\ln L) O ( L ln L ) can approximate f ∈ C s ( [ 0 , 1 ] d ) f\in C^s([0,1]^d) f ∈ C s ([ 0 , 1 ] d ) with an error O ( ∥ f ∥ C s ( [ 0 , 1 ] d ) N − 2 s / d L − 2 s / d ) \mathcal{O}(\|f\|_{C^s([0,1]^d)}N^{-2s/d}L^{-2s/d}) O ( ∥ f ∥ C s ([ 0 , 1 ] d ) N − 2 s / d L − 2 s / d ) . Gradient descent methods for deep ReLU networks achieve optimal generalization rates.
problem Generalization of gradient descent methods for deep neural networks
method Establishing minimax-optimal rates for GD and SGD with deep ReLU networks
result Gradient descent methods for deep ReLU networks achieve optimal generalization rates
Paper identifies key function spaces for ReLU networks based on Fisher information.
problem Understanding the structure of Fisher information matrices in ReLU networks.
method Spectral decomposition of Fisher information matrices, focusing on the first three eigenspaces.
result The first three eigenspaces account for 97.7% of the trace of the Fisher information matrix, corresponding to spherical harmonic functions of order ≤2.
It has been noted in existing literature that over-parameterization in ReLU networks generally improves performance. While there could be several factors involved behind this, we prove some desirable theoretical properties at initialization which may be enjoyed by ReLU networks. Specifically, it is known that He initia…
Gradient descent converges to minimum Bayes risk for two-layer ReLU networks in mean field regime.
problem Training two-layer ReLU networks using gradient descent in the mean field regime.
method Describes a condition for convergence to minimum Bayes risk, extending previous results to ReLU-activated networks.
result The condition for convergence does not depend on initialization and concerns weak convergence of network realization.
New bounds on ReLU networks for low-regular functions.
problem Bounding approximation error for ReLU networks on low-regular functions.
method Complexity analysis of Fourier features residual networks to ReLU networks.
result Approximation error bound proportional to target function norm and inversely proportional to network width and depth.
SGD trains ReLU networks to implement piecewise linear maps with at most 3 knot points.
problem Understanding the training dynamics of neural networks trained via SGD.
method Mean-field analysis of a two-layer ReLU network trained via SGD for a univariate regression problem.
result At convergence, SGD-trained ReLU networks implement piecewise linear maps with at most 3 knot points.
This work connects neural network training to convex optimization via the NTK.
problem Understanding and optimizing neural network training via convex programs.
method Interpreting gated ReLU network as MKL, showing NTK equivalence, and improving weights.
result The NTK cannot perform better than the optimal MKL kernel on the training set.
This paper simplifies deep ReLU networks into local linear models for better interpretability.
problem Limited transparency and interpretability of deep neural networks, especially ReLU networks.
method Local linear representation and equivalent set of local linear models (LLMs).
result Simplified deep ReLU networks for better interpretability and diagnostics.
Novel approach analyzes ReLU networks' training dynamics and proposes GmP for improved optimization.
problem Stochastic optimization instability in ReLU networks impedes convergence and generalization.
method Characteristic activation boundaries analysis and Geometric Parameterization (GmP) technique.
result GmP resolves instability, leading to better optimization, convergence, and generalization.
We compute the local Lipschitz constant of ReLU networks precisely.
problem Estimating the local Lipschitz constant of ReLU networks is hard.
method We use a novel approach involving the generalized Jacobian and backpropagation.
result We provide an algorithm to compute the exact Lipschitz constant of ReLU networks.
New algorithm for learning ReLU networks with Gaussian noise, improving previous results.
problem PAC learning one-hidden-layer ReLU networks with Gaussian marginals and label noise.
method First polynomial-time algorithm for k k k up to i l d e O ( log d ) ilde{O}(\sqrt{\log d}) i l d e O ( log d ) for positive coefficients, no assumptions on rank or condition number. result Proves a Statistical Query lower bound of d Ω ( k ) d^{Ω(k)} d Ω ( k ) for arbitrary real coefficients, separating learnability classes. Quantile regression with ReLU networks achieves minimax rates for various function types.
problem Estimating quantiles from covariates with neural networks.
method Quantile regression with rectified linear unit (ReLU) neural networks.
result ReLU networks achieve minimax rates for broad collections of function types.
Path regularization reveals convex optimization in deep ReLU networks.
problem Understanding the optimization landscape of deep neural networks.
method Introducing path regularization to make the training problem convex and sparsity-inducing.
result Path regularized parallel ReLU networks are a parsimonious convex model in high dimensions.
ReLU networks learn simple models even with many parameters, overcoming traditional wisdom.
problem Generalization of overparameterized neural networks.
method Convex optimization and sparse recovery perspective applied to two-layer ReLU networks with standard weight decay.
result ReLU networks learn simple models that explain the data, analogous to sparse recovery in compressed sensing.
Adam achieves optimal convergence in deep ReLU networks via novel Kakeya bounds.
problem Training deep ReLU networks using Adam in non-smooth settings.
method Stratified Morse theory and Kakeya bounds to analyze region crossings and convergence.
result First global-optimal convergence for Adam in non-smooth, non-convex ReLU landscapes.
Researchers create integral representations for two-layer ReLU networks with quantitative bounds.
problem Approximating functions with two-layer ReLU networks using explicit integral representations.
method Developed integral representations involving harmonic extension and projection, providing L 2 L^{2} L 2 bounds. result Functions can be approximated with L 2 L^{2} L 2 errors independent of dimension or degree, depending on coefficients and distribution. ReLU networks don't exponentially distort curve lengths as previously thought.
problem Understanding how neural networks distort curve lengths with depth.
method Analyzing expected length distortion of ReLU networks with random initialization.
result Expected length distortion does not grow with depth, and shrinks slightly.
Study approximates nonlinear functionals using deep ReLU networks.
problem Approximating nonlinear continuous functionals with neural networks.
method Constructs continuous piecewise linear interpolation under simple triangulation, analyzes rates of approximation.
result Established rates of approximation for functional deep ReLU networks.
Proves SQ lower bounds for learning two-hidden-layer neural networks.
problem Learning two-hidden-layer ReLU networks with Gaussian inputs.
method Refined lifting procedure to reduce Boolean PAC learning to Gaussian.
result Superpolynomial SQ lower bounds for Gaussian inputs.
Deep ReLU networks generalize well with few parameters.
problem Generalization of overparametrized deep neural networks.
method Explicit bounds on test error independent of overparametrization and VC dimension.
result Generalization error is independent of network architecture and overparametrization.
Improved sample complexity for ReLU networks with norm constraints.
problem Estimating sample complexity for ReLU networks under norm constraints.
method Refined Rademacher complexity analysis for function class.
result Often no explicit depth-dependence in sample complexity bound.
New findings on depth vs. width in neural networks, showing depth can improve learnability.
problem Understanding the role of depth in neural networks, especially when width is unbounded.
method Analyzing sample complexity for learnability in norm-controlled depth-2 and depth-3 ReLU networks.
result Depth can improve learnability of functions that are otherwise unlearnable with depth-2 networks.
New polynomial-time solutions found for training ReLU networks, mirroring Max-Cut complexity.
problem Training two-layer ReLU neural networks with weight decay regularization.
method Developed a convex formulation and randomized algorithm to find approximate global optimizers.
result First polynomial-time approximation guarantees and hardness of approximation results for regularized ReLU networks.
This paper optimizes ReLU networks for approximating Hölder continuous functions.
problem Optimizing the approximation rate of ReLU networks in terms of width and depth.
method Constructive proof of ReLU networks' approximation power with specific width and depth constraints.
result Optimal approximation rate of ReLU networks with width and depth constraints.
We study algebraic varieties of ReLU networks to understand their representable functions.
problem Understanding the functions that ReLU neural networks can represent.
method We introduce algebraic varieties associated with ReLU networks and derive polynomial equations to characterize representable functions.
result Conditions under which ReLU networks attain their expected dimension, providing insight into their structural properties.
Randomly initialized ReLU networks of depth two can approximate smooth functions well.
problem Approximation power of two-layer networks of random ReLUs.
method Harmonic analysis and ridgelet representation theory for upper bounds, dimensionality arguments for lower bounds.
result Near-matching upper and lower bounds for L 2 L_2 L 2 -approximation and Sobolev norms. Study analyzes error in ReLU networks with local connections.
problem Improving neural network performance and understanding approximation errors.
method Analyzed approximation error of ReLU networks with local connections.
result Error estimate depends on depth and width of hidden layers.
Gradient flow of ReLU networks converges in low-correlation high-dimensional data.
problem Convergence of shallow ReLU networks trained on weakly interacting data.
method Gradient flow analysis with Polyak-Łojasiewicz viewpoint.
result Network width of order log(n) neurons suffices for global convergence with high probability.
Gradient descent fails to train two-layer ReLU networks, leading to poor performance.
problem Gradient descent training of two-layer ReLU networks initialized by He et al. (2015) fails to find optimal solutions.
method Gradient descent on a least-squares loss for training two-layer (Leaky)ReLU networks.
result Gradient descent only finds bad local minima, leading to linear regression for non-linear target functions.
Neural networks and rational functions efficiently approximate each other. In more detail, it is shown here that for any ReLU network, there exists a rational function of degree O ( polylog ( 1 / ε ) ) O(\text{polylog}(1/ε)) O ( polylog ( 1/ ε )) which is ε ε ε -close, and similarly for any rational function there exists a ReLU network of size $O(\text{polylog}(1/ε…
Paper improves confidence intervals and variance estimation for deep learning models.
problem Improving confidence intervals and variance estimation in deep learning models.
method Residual-based framework for conditional variance estimation; robust bootstrap procedure for confidence intervals.
result First non-asymptotic bounds for variance estimation using ReLU networks.
It has been widely assumed that a neural network cannot be recovered from its outputs, as the network depends on its parameters in a highly nonlinear way. Here, we prove that in fact it is often possible to identify the architecture, weights, and biases of an unknown deep ReLU network by observing only its output. Ever…