PaperlayerView exact revision on arXiv

Source-linked AI summary

Nonparametric regression using deep neural networks with ReLU activation function

Johannes Schmidt-Hieber

arXiv:1708.06633v5math.STcs.LGstat.ML

TL;DR

The paper addresses how deep neural networks can overcome slow high-dimensional nonparametric regression rates and how their architecture affects statistical performance. It analyzes sparse, overparameterized feedforward ReLU networks under hierarchical composition assumptions, showing near-minimax rates and a sample-size-scaled role for depth, while wavelet estimators can be polynomially suboptimal. The conclusions are bounded by assumptions on composition structure and weight magnitude, and by the focus on feedforward regression networks.

  • Problem

    High-dimensional nonparametric regression suffers from slow rates without structural assumptions, while the statistical reasons for deep networks' favorable performance remain insufficiently understood.

  • Method

    The paper studies sparsely connected, potentially overparameterized multilayer feedforward networks with ReLU activation under hierarchical composition assumptions.

  • Results

    Deep ReLU networks achieve near-minimax rates for arbitrary smoothness under composition assumptions, while wavelet estimators can be suboptimal by a polynomial factor in n.

  • Takeaways & Limitations

    The theory indicates that network depth should scale with sample size and that sparsity is a central complexity measure for achieving optimal convergence rates.

  • Takeaways & Limitations

    The analysis is restricted to feedforward regression networks, assumes hierarchical composition structure, and bounds network parameters in absolute value by one.

Abstract

from arXiv · show

Consider the multivariate nonparametric regression model. It is shown that estimators based on sparsely connected deep neural networks with ReLU activation function and properly chosen network architecture achieve the minimax rates of convergence (up to $\log n$-factors) under a general composition assumption on the regression function. The framework includes many well-studied structural constraints such as (generalized) additive models. While there is a lot of flexibility in the network architecture, the tuning parameter is the sparsity of the network. Specifically, we consider large networks with number of potential network parameters exceeding the sample size. The analysis gives some insights into why multilayer feedforward neural networks perform well in practice. Interestingly, for ReLU activation function the depth (number of layers) of the neural network architectures plays an important role and our theory suggests that for nonparametric regression, scaling the network depth with the sample size is natural. It is also shown that under the composition assumption wavelet estimators can only achieve suboptimal rates.

1. Introduction.

The paper develops statistical theory for deep feedforward ReLU networks in multivariate nonparametric regression, focusing on sparse, potentially overparameterized networks. It argues that composition structure, ReLU activation, and sample-size-dependent depth explain favorable rates and distinguish neural networks from wavelet estimators.

  • ReLU networks and smoothness: The theory shows that ReLU networks with sufficiently deep architectures attain near-minimax rates for arbitrary regression-function smoothness, despite producing piecewise-linear functions.This contrasts with typical piecewise-linear approximation methods, which are rate-optimal only up to smoothness index two.
  • Network depth: The analysis indicates that network depth should scale with sample size, suggesting that larger samples should be paired with additional hidden layers.This theoretical implication is consistent with the increasing depth of some state-of-the-art architectures.
  • Overparameterization and sparsity: The analysis allows the number of potential network parameters to exceed the sample size and treats sparsity as the key tuning parameter.For noisy regression, the paper argues that regularization or sparsity is essential for controlling overfitting and generalization.
  • Motivation and contribution: Deep ReLU networks can achieve faster nonparametric estimation rates under hierarchical composition assumptions, including generalized additive models.These assumptions help avoid the curse of dimensionality present without additional signal structure.
  • Comparison with wavelets: Wavelet series estimators cannot adapt to the underlying composition structure and have rates that are suboptimal by a polynomial factor in n.The paper presents this as a function class where fitting a neural network outperforms wavelet series estimators.
  • Scope: The paper studies multilayer feedforward networks for regression rather than classification and does not analyze convolutional or recurrent architectures.These choices delimit the connection between the theory and broader deep-learning applications.

3. Main results.

The main results show that sparse ReLU networks attain near-minimax convergence rates for regression functions with compositional structure, while network depth, sparsity, and optimization error determine the guarantee. The theory also establishes matching lower bounds in a key regime and identifies scope limitations for depth and sample size.

  • Main theorem: Compositionally structured regression functions admit sparse ReLU-network estimators with convergence rates governed by the intrinsic component dimensions and smoothness indices.The framework includes low-dimensional structures such as additive models, and the composition assumption is independent of whether neural networks are used.
  • Main theorem: Theorem 1 requires sparsity s ≍ n^φn log n and yields risk controlled by the empirical-risk gap Δn up to logarithmic factors.The risk satisfies a two-sided comparison with Δn, and Δn is zero for an empirical risk minimizer.
  • Architecture: Choosing depth L of order log_2 n minimizes the displayed rate factor, although increasing layers can worsen oracle upper bounds.The analysis also notes that residual networks fall outside the analyzed architecture.
  • Limitations: The stated theorem omits explicit constants, and large constants or remainder terms may make the theoretically fast behavior ineffective for small samples.The proofs are non-asymptotic, but the constants were not minimized.
  • ReLU properties: ReLU networks permit identity-based depth synchronization and parameter bounds of one, supporting approximation constructions without requiring large weights.This bounded-parameter property is contrasted with classical square-function approximation methods for other nonlinear activations, which may require diverging weights.
  • Optimality: The minimax lower bound matches the network upper rate φn up to a likely proof-artifact log_2 n factor when ti ≤ min(d0, …, d_i−1) for every composition level.Outside this regime, the minimax rate is difficult to determine and alternative composition representations may yield faster rates.

4. Examples of specific structural constraints.

The composition framework covers additive, generalized additive, and sparse tensor structures, allowing deep ReLU networks to exploit low-dimensional structure and attain fast rates up to logarithmic factors.

  • Additive models: Additive models decompose into univariate components followed by a smooth multivariate link, explaining rates that avoid the curse of dimensionality.Each component depends on one variable, while the link depends on all variables but is infinitely smooth.
  • Additive models: n^−2β/(2β+1) log^3 n is the resulting risk bound for additive models, matching the minimax rate up to the log^3 n factor.The bound holds for architectures with depth and sparsity scaled appropriately with n.
  • Generalized additive models: Generalized additive models are included in the composition framework through functions such as f0(x)=h(x1+...+xd).The supplied passages identify this as a general additive model, but do not provide its complete rate expression.
  • Sparse tensor decomposition: Sparse tensor decompositions require no fixed basis, and their component functions may be unknown and nonorthogonal.This distinguishes the neural-network condition from conventional series estimators.
  • Sparse tensor decomposition: For sparse tensor structures, networks with depth proportional to log n and sparsity of order n^1/(2β+1) log n achieve n^−2β/(2β+1) log^3 n risk.The exponent is independent of the input dimension d.

5. Suboptimality of wavelet series estimators.

The paper constructs generalized additive examples showing that wavelet estimators can retain dimension-dependent rates, whereas deep ReLU networks exploit the composition structure and achieve faster rates.

  • Comparison of rates: For generalized additive functions, neural-network reconstructions with depth L ≍log n have prediction error bounded by n^−2α/(2α+1) log^3 n.The model considered is f0(x)=h(x1+...+xd) with h in a Hölder class.
  • Comparison of rates: Wavelet estimators cannot converge faster than n^−2α/(2α+d) for the same class, which can be much slower when d is large.This lower bound is established for compactly supported wavelets and 0<α≤1.
  • Interpretation: The composition assumption is presented as natural and broad enough to include structural constraints such as additive models.The paper uses this structure to explain why neural networks avoid the wavelet estimator’s dimension-dependent rate in the example.
  • Proof strategy: The counterexample uses a uniform design and empirical wavelet coefficients, with series truncation balancing squared bias and variance.These ingredients support the lower-bound construction and estimator analysis.
  • Wavelet lower bound: The wavelet lower bound applies to arbitrary index sets I and Hölder radius K under the stated smoothness range.The construction uses compactly supported wavelets.

7. Proofs.

The proofs combine approximation constructions, network-composition rules, entropy control, and risk bounds to establish results for sparse deep ReLU network classes.

  • Network constructions: Parallelization combines subnetworks, while identity layers synchronize depths without changing signals.These operations support construction of a single network from subnetworks with different depths.
  • Sparsity: Removing inactive nodes yields networks whose widths can be reduced to the sparsity level without changing the represented function.The argument removes zero columns and corresponding rows associated with inactive units.
  • Approximation: Approximation begins with product networks and local Taylor expansions on small hypercubes, then composes approximations for the component functions.This converts the composition structure of f0 into a network approximation.
  • Architecture embedding: The proof chooses component approximations with depth proportional to log n and embeds their composition into the target architecture.The resulting depth, widths, and sparsity satisfy the theorem’s prescribed conditions.
  • Risk analysis: Covering-number bounds and a least-squares risk lemma control stochastic error for bounded network classes under Gaussian noise.The proof combines these ingredients with approximation bounds to obtain upper and lower risk bounds.
  • Risk analysis: The design-density assumption transfers L2 approximation error to prediction risk through lower and upper density bounds.The supplied proof passage states the lower-risk comparison explicitly.

1. Overparametrization and implicit regularization.

The analysis questions whether implicit regularization from overfitted neural networks is sufficient for nonparametric regression. It argues that additional smoothing-oriented regularization is needed, while sparsity provides a route to rate-optimal estimation.

  • Overparametrization and implicit regularization: Implicit regularization in the overfitted regime is conjectured to be insufficient even for consistency in additive-error regression models.The argument considers shallow one-dimensional networks and links SGD limits to spline interpolants.
  • Overparametrization and implicit regularization: For shallow ReLU networks with m ≥ n, placing breakpoints between consecutive sample order statistics ensures a perfectly interpolating network exists.This is a weak overparametrization assumption supporting exact interpolation.
  • Overparametrization and implicit regularization: The SGD limit approximates the natural cubic spline interpolant, which is inconsistent for estimating the regression function under additive noise.The spline minimizes the L2 norm of the second derivative among twice differentiable interpolants.
  • Overparametrization and implicit regularization: Because interpolation alone does not yield rate-optimal estimation, further regularization must force the network to smooth the data.The paper contrasts this with nonparametric estimators that can interpolate while converging quickly.
  • Overparametrization and implicit regularization: The proposed complexity measure is sparsity of network weights, used to obtain optimal convergence rates under a hierarchical composition assumption.The article treats sparsity as an explicit structural constraint rather than relying only on implicit regularization.

2. Network sparsity.

The discussion presents sparsity as a way to control highly overparameterized networks while preserving adaptive structure. It contrasts pruning and topology-design methods with extremely deep fully connected alternatives that avoid sparsity but differ from practical architectures.

  • Network sparsity: Pruning trained networks can reduce parameters, but fixing one sparse topology may lose flexibility to adapt to structure in the data.Alternative approaches vary sparsity across matrices or units, or evolve the topology while maintaining overall sparsity.
  • Network sparsity: Sparse topology methods include predefined sparse connections, evolutionary rewiring, and retaining units that transmit the most signal between layers.These methods modify connectivity rather than only zeroing small weights after training.
  • Network sparsity: Weight-agnostic neural networks fix initialized weights and learn only the network topology through iterative candidate-model scoring.Each iteration generates new candidates around models with the highest scores.
  • Network sparsity: Extremely deep fixed-width fully connected networks can achieve optimal estimation rates without sparsity, but their architectures differ substantially from those used in practice.The cited result uses depth increasing polynomially with sample size and may require discontinuous weight assignments for optimal approximation.

3. Classification and nonparametric regression.

The paper emphasizes that classification and noisy nonparametric regression involve different statistical regimes. In regression, additive noise changes constants rather than rates, while future theory must address settings beyond this model.

  • Classification and nonparametric regression: In many deep-learning classification tasks, correctly labeled and well-separated classes make reconstruction closer to interpolation than denoising.This helps explain why observed sample complexity can be lower than in nonparametric regression.
  • Classification and nonparametric regression: Gaussian perturbations increase the noise level in nonparametric regression but do not change the estimation rates for the considered estimators.The noise level enters the risk bounds through constants.
  • Classification and nonparametric regression: The theory concerns any estimator returning a sparsely connected neural network, rather than one fixed estimator or learning algorithm.Its estimation risk is tightly controlled by Δ_n(f̂_n, f_0), which depends on the estimator.

4. Algorithms.

The discussion identifies algorithm-dependent approximation terms, idealized training assumptions, and dimension-dependent constants as open issues. It also highlights additive-model rates, activation-function constraints, and empirical evidence relevant to the theory.

  • Algorithms: The approximation term Δ_n(f̂_n, f_0) may depend heavily on learning rate, initialization, and the energy landscape.Precise theoretical bounds for this term remain a subject for future work.
  • Algorithms: The analysis idealizes popular training procedures such as Adam because precise theoretical bounds for them remain difficult to obtain.The authors regard some simplification as unavoidable in statistical theory.
  • Algorithms: For additive models, a variation of the approximation argument yields linear dependence on dimension in the resulting rate bound.The construction uses d subnetworks with s ≍ dN log N parameters and approximation error O(dN^-β).
  • Algorithms: Future work should analyze neural networks with input dimension increasing with sample size and models beyond nonparametric regression.The authors stress that data structure is essential to deep-learning behavior and reconstruction properties.
  • Algorithms: Wavelet methods have slower convergence rates than sparsely connected deep ReLU networks for generalized additive models.The comparison illustrates why generic function spaces are useful for evaluating different estimation methods.
  • Algorithms: The network class bounds each parameter in absolute value by one, while more realistic weight-magnitude constraints could reflect norm control induced by SGD.The discussion also suggests studying neighborhoods of random initializers.
  • Algorithms: Simulation evidence suggests deep networks can approach theoretical performance, but careful initialization may be necessary to learn proof-specific constructions.Reinitialization may be needed when optimization becomes trapped at a local minimum with large training error.

APPENDIX A: NETWORK APPROXIMATION OF POLYNOMIALS

The appendix constructs ReLU networks that approximate products and multivariate monomials, using iterated multiplication networks and explicit error bounds. These constructions use bounded parameters and depths that grow with approximation degree and dimension.

  • Quadratic approximation: ReLU triangle-wave networks approximate x(1−x) exponentially fast in the depth parameter m.The construction proves piecewise-linear interpolation properties for the functions R_k and uses them to approximate the quadratic function.
  • Multiplication networks: A network with m + 4 hidden layers approximates xy on [0,1]^2 with sup-norm error at most 2^-m.The network outputs values in [0,1], and all network parameters are bounded by one.
  • Multivariate products: Iterating the multiplication construction yields an r-input product network with q(m + 5) hidden layers, where q = ⌈log2 r⌉.The construction pairs neighboring inputs repeatedly and keeps all parameters bounded by one.
  • Polynomial approximation: Networks approximate monomials of degree below γ in L∞, with width and depth determined by the number of monomials, γ, r, and m.The appendix emphasizes that the construction improves on earlier results by bounding parameters by one and providing an explicit approximation-error bound.

APPENDIX B: PROOF OF THEOREM 5

The proof of Theorem 5 builds a ReLU network from local Taylor approximations, localized hat functions, monomial approximators, and multiplication modules. It controls depth, width, active parameters, and approximation error through the network construction.

  • Local approximation: The proof uses local Taylor approximations on a grid D(M) with (M + 1)^r grid points.The grid supports localized polynomial approximations of the target function.
  • Localization: Hat-function networks localize the approximation, while parallel multiplication networks approximate products of hat functions and require at most 49r^2N(1 + L*) active parameters.The resulting supports are contained within the corresponding localized product supports.
  • Network assembly: The constructed network combines polynomial, localization, multiplication, scaling, and summation subnetworks into a single bounded-parameter network.The proof explicitly embeds parallel subnetworks and adds a final scaling and shifting stage.
  • Complexity control: The final active-parameter count is bounded by 141(r + β + 1)^(3+r)N(m + 6).The bound follows after combining the component networks and controlling the grid and monomial counts.

APPENDIX C: PROOFS FOR SECTION 7.2

The appendix proves empirical-risk and risk bounds by relating covering-number controls to empirical-process deviations. The argument separates the proof into upper and lower risk comparisons and handles the regime of large covering numbers separately.

  • Reduction: The proof begins by restricting attention to log N_n ≤ n because the risk is trivially bounded when log N_n ≥ n.This reduction is used before dividing the proof into parts (I)–(IV).
  • Conclusion: The proof combines the separate estimates to establish the asserted risk bound for empirical risk minimization.The final steps use the empirical-risk-minimizer property and conclude the lower and upper bounds from parts (I)–(IV).
  • Empirical-process control: Bernstein’s inequality and a union bound control deviations over a finite δ-cover of the function class.The resulting bounds depend on the covering number, sample size, envelope bound F, and approximation radius δ.
  • Risk comparison: A deterministic inequality converts bounds on empirical risk into corresponding upper and lower bounds for true risk.The proof applies the inequality with the empirical and population risks of the estimator and comparator functions.
Loading 1708.06633v5…