Source-linked AI summary
Deep Neural Networks Learn Non-Smooth Functions Effectively
Masaaki Imaizumi, Kenji Fukumizu
TL;DR
Because smooth-function theory gives many methods minimax-optimal generalization rates, it has been difficult to establish a theoretical basis for DNNs’ empirical advantage. This paper analyzes DNN estimators for piecewise-smooth functions and finds their rates minimax optimal while some standard methods do not attain that rate; it also provides architecture guidance.
Problem
Under smoothness assumptions, many methods attain minimax-optimal generalization rates, making it difficult to establish a theoretical advantage for DNNs despite their empirical performance.
Source: §1 · pp. 1–2Method
The paper analyzes DNN generalization rates for piecewise-smooth functions and compares them with minimax lower bounds and rates for other methods.
Source: §1 · p. 2Results
DNN estimators attain minimax-optimal rates for piecewise-smooth functions, while kernel and orthogonal-series methods do not attain that rate.
Source: §1 · p. 2Takeaways & Limitations
The theoretical results provide guidance for selecting the number of DNN layers and parameters.
Source: §6 · p. 11The paper focuses on theory and does not discuss computational issues of the Bayesian approach.
Source: §3.3 · p. 7
Abstract
from arXiv · showhide
We theoretically discuss why deep neural networks (DNNs) performs better than other models in some cases by investigating statistical properties of DNNs for non-smooth functions. While DNNs have empirically shown higher performance than other standard methods, understanding its mechanism is still a challenging problem. From an aspect of the statistical theory, it is known many standard methods attain the optimal rate of generalization errors for smooth functions in large sample asymptotics, and thus it has not been straightforward to find theoretical advantages of DNNs. This paper fills this gap by considering learning of a certain class of non-smooth functions, which was not covered by the previous theory. We derive the generalization error of estimators by DNNs with a ReLU activation, and show that convergence rates of the generalization by DNNs are almost optimal to estimate the non-smooth functions, while some of the popular models do not attain the optimal rate. In addition, our theoretical result provides guidelines for selecting an appropriate number of layers and edges of DNNs. We provide numerical experiments to support the theoretical results.
1. Introduction
The paper studies whether DNNs have a theoretical advantage when data come from non-smooth, piecewise-smooth functions, a setting not covered by smoothness-based analyses. It shows that DNN estimators attain minimax-optimal generalization rates while some standard methods do not, and gives guidance on DNN architecture.
1. Introduction
- Smoothness-based analyses leave little theoretical basis for distinguishing DNNs because many standard methods also attain minimax-optimal generalization rates.Existing analyses assume smooth data-generating functions; piecewise-smooth functions may be non-smooth at the boundaries between pieces.Source: §1 · p. 2
- The paper derives generalization-error convergence rates for DNN estimators of piecewise-smooth functions, a generalization of smooth functions.The function class allows non-smoothness on boundaries between pieces in the domain.Source: §1 · p. 2
- DNN estimators attain minimax-optimal generalization rates for piecewise-smooth functions, while kernel and orthogonal-series methods do not attain that rate.The results apply to ReLU DNN least-squares and Bayes estimators, up to logarithmic factors.Source: §1 · p. 2
- The paper gives a practical guideline for the necessary number of DNN layers and parameters to achieve the convergence rate.Table 1 presents an architecture for achieving the optimal generalization rate.Source: §1 · p. 2, Table 1 · p. 3
2. Regression with Non-Smooth Functions
The paper frames regression as estimating an unknown function from noisy observations, then defines piecewise smooth functions to include functions that may be non-smooth at boundaries between regions.
2.1. Regression Problem.
- The regression setup assumes i.i.d. observations on a D-dimensional cube, Gaussian noise, and a positive bounded covariate density; estimation error is measured in L2(PX).The regression goal is to estimate the unknown function from the observations.Source: §2.1 · p. 3
2.2. Definition of Non-Smooth Function.
- Piecewise smooth functions are smooth within support pieces but may be non-differentiable or discontinuous at their boundaries.The paper presents a two-dimensional example with three pieces and discontinuities on their boundaries.Source: §2.2 · p. 3, Figure 1 · p. 4
- A basis piece lies on one side of a surface defined by a horizon function, with the paper restricting the pieces to transformed spheres.The horizon function is built from a smooth function, and the basis-piece construction extends the boundary-fragment class.Source: §2.2 · pp. 3–4
- Intersecting J basis pieces forms regions with piecewise α-smooth boundaries, allowing non-smooth boundaries; the function class includes smooth functions as the one-piece case.Functions in the class combine smooth functions on each region and can be discontinuous at region boundaries.Source: §2.2 · pp. 4–5
3. Estimators with DNNs and Theoretical Analysis
The paper defines sparse, bounded ReLU network models and analyzes least-squares and Bayesian estimators for piecewise smooth functions. The least-squares rate reflects both smooth-function and boundary estimation, while the Bayes estimator attains the same rate without optimization.
3.1. Models by Deep Neural Networks.
- ReLU DNNs are specified by layerwise weight and bias pairs, with bounds on layer count, nonzero parameters, and parameter magnitudes.The nonzero-parameter bound also limits the number of network edges.Source: §3.1 · p. 5
3.2. Least Square Estimator.
- The least-squares convergence rate combines smooth-function estimation with estimation of region indicators through their boundaries.The first term corresponds to the minimax rate for smooth functions, and the second matches a rate for estimating sets with smooth boundaries.Source: §3.2 · p. 6
- The analysis indicates that increasing depth decreases the required parameter-magnitude bound, which the authors relate to avoiding performance loss from large parameters.The stated interpretation draws on prior work reporting worse DNN performance with large parameter values.Source: §3.2 · p. 6
3.3. Bayes Estimator.
- The Bayesian estimator achieves the same convergence rate as the least-squares estimator and avoids non-convex optimization, although computing the posterior and its mean is not straightforward.The paper states that it does not address computational issues of the Bayesian approach.Source: §3.3 · p. 7
4. Discussion: Why DNNs work better?
For piecewise-smooth functions, DNN estimators achieve a minimax-optimal convergence rate, while linear estimators do not attain that rate. The authors relate this advantage to compact representation of non-smooth structure and limit the comparison to linear estimators.
4.1. Optimality of the DNN Estimators.
- The DNN estimators’ convergence rates match the minimax lower bound up to a log factor for the piecewise-smooth function class.The lower bound implies that no estimator can achieve a better rate for this class.Source: §4.1 · p. 8
4.2. Non-Optimality of Other Methods.
- Linear estimators, including kernel methods, Fourier estimators, and splines, do not attain the optimal rate for the class.The paper says this result implies larger generalization errors for a wide range of other methods.Source: §4.2 · p. 8
4.3. Interpretation and Discussion.
- ReLU combinations can express step functions, which layered compositions combine with smooth functions restricted to pieces using relatively few parameters.The paper contrasts this with other methods, which may need more parameters to approximate non-smooth structure; it links larger parameter counts to increased estimator variance.Source: §4.3 · p. 8
- The claimed inefficiency applies to linear estimators, not every statistical method other than DNNs.The authors describe the comparison as an advantage against linear estimators.Source: §4.3 · p. 9
- Earlier harmonic-analysis results cover piecewise-smooth functions with C2 boundaries, whereas the paper’s boundary-fragment setting is more general.The cited passage also notes that convergence rates are not known for those harmonic-based methods in the setting considered here.Source: §4.3 · p. 9
5. Experiments
In a simulated regression experiment, the least-squares DNN estimate recovers a piecewise-smooth function’s non-smooth structure, and DNNs outperform the compared estimators across the tested sample sizes.
5. Experiments
- The realization experiment uses a two-dimensional uniform input and an independent Gaussian noise variable with scale 0.5.The target is piecewise smooth, with its non-smooth structure illustrated in Figure 2.Source: §5.1 · p. 9, Figure 2 · p. 9
5.1. Non-smooth Realization by DNNs.
- With a sample size of 100, the least-squares DNN estimate approximates the non-smooth structure of the piecewise-smooth target.The estimate shown is the one with the minimum error among 100 trials using different initial points.Source: Figure 3 · p. 9, §5.1 · p. 10
5.2. Comparison with the Other Methods.
- The DNN comparison uses the Section 5.1 setting, while kernel and trigonometric-basis orthogonal-series parameters are selected by cross-validation.The kernel methods use Gaussian and polynomial kernels.Source: §5.2 · p. 10
- DNNs outperform the orthogonal-series and kernel estimators across sample sizes from 100 to 1500 in the reported expected-loss comparison.Figure 4 reports the mean and standard deviation of log loss over 100 replications.Source: §5.2 · p. 10, Figure 4 · p. 10
6. Conclusion
The paper derives generalization-error convergence rates for least-squares and Bayes DNN estimators in piecewise-smooth regression and shows these rates are minimax optimal. It also reports inefficiency of commonly used linear estimators for this setting and provides theory-based guidelines for DNN architecture choices.
6. Conclusion
- For piecewise-smooth regression, the paper derives generalization-error convergence rates for least-squares and Bayes DNN estimators and shows they are minimax optimal.The conclusion also describes commonly used linear estimators as inefficient for estimating these functions.Source: §6 · p. 11
- The conclusion’s claims concern estimation of piecewise-smooth functions in the regression setting considered by the paper.The authors frame their results around a regression problem with a piecewise-smooth true function.Source: §6 · p. 11
- The theoretical results provide guidelines for selecting the number of DNN layers and parameters.The conclusion says these guidelines are based on the paper’s theoretical results.Source: §6 · p. 11
Supplementary materials for “Deep Neural Network Learn Non-Smooth Functions Effectively.”
The supplementary material defines the smoothness spaces and geometric pieces used to describe the paper’s function class. It specifies both boundary regularity and an indicator-function representation for basic pieces.
Appendix A. Additional definitions
- The Hӧlder space Hβ(Ω̄) consists of functions with continuous derivatives up to order ⌊β⌋ whose derivatives of that order are Hӧlder continuous with exponent β − ⌊β⌋.The definition also introduces a norm for the space.Source: Appendix A · p. 14
- A basic piece is defined through an embedding of a D-dimensional ball whose boundary has Hӧlder regularity, together with a graph-based indicator condition.The definition situates the piece in the boundary fragment class.Source: Appendix A · p. 14
- The indicator condition represents a piece using the Heaviside function and an Hӧlder function over D−1 coordinates.The appendix introduces pieces as intersections of embeddings of D-dimensional balls.Source: Appendix A · p. 14
Appendix B. Proof of Theorem 1
Appendix B proves Theorem 1 by decomposing the estimator’s error into approximation and variance terms and bounding them using DNN approximation and entropy arguments. It also applies an inequality to (17) to derive an entropy bound with a stated probability guarantee.
Appendix B. Proof of Theorem 1
- The proof separates the error bound into approximation, variance, and estimation terms, addressing DNN approximation first and variance and the overall rate afterward.The appendix states this three-part roadmap before the subsections summarized here.Source: Appendix B · p. 15
B.1. Approximate piecewise functions by DNNs.
- The construction combines networks approximating piecewise-function components with multiplication and inner-product networks to approximate the target function.For the componentwise approximation, the text gives an error bound of CH(2J − 1)ε.Source: §B.1 · pp. 15, 17
B.2. Evaluate an entropy bound of the estimators by DNNs. ˇˇˇˇˇˇ
- The entropy argument uses empirical-process chaining and Gaussian concentration, bounding covering numbers of the DNN class to control the estimator’s variance term.The covering-number bound relates empirical-norm entropy to supremum-norm entropy for the network class.Source: §B.2 · pp. 19–20
B.2. Evaluate an entropy bound of the estimators by DNNs.
- The resulting bound holds with probability at least 1 - exp(-n u^2/(2σ^2δ^2)) for all u > 0.The proof obtains it by applying an additional inequality to (17).Source: §B.2 · p. 21
B.3. Combine the results.
The proof bounds the population L2 error using a bounded-density assumption, then applies concentration inequalities to establish the stated convergence bound and complete Theorem 1.
B.3. Combine the results.
- The population L2 error is bounded by the squared sup-norm error multiplied by the bounded density constant.The passage gives the inequality using sup_x pX(x) ≤ BP.Source: §B.3 · p. 21
- The approximation error and its variance term are bounded at the rate max{n^-2β/(2β+D), n^-2α/(2α+2D-2)}.The proof substitutes these bounds into concentration inequalities for the selected estimator.Source: §B.3 · p. 21
- With the number of nonzero parameters bounded as stated, the proof completes Theorem 1.The final passage says polynomial growth of Vn, V, L, and B in n completes the proof.Source: §B.3 · p. 22
Appendix C. Proof of Theorem 2
The proof establishes posterior contraction in two stages: first under an empirical norm, then under the population L2 norm, using a neural-network approximation and associated bounds.
Appendix C. Proof of Theorem 2
- The proof reuses a neural-network approximation to control approximation error, depth, and the number of nonzero parameters.It then bounds posterior contraction first empirically and subsequently in population L2.Source: Appendix C · p. 22
C.1. Bound with an empirical norm. Step 1. Preparation
- A test function distinguishes the true distribution, while entropy and prior-mass bounds contribute to control of posterior contraction.The proof decomposes the expected posterior distribution into terms and combines their bounds.Source: §C.1 · pp. 23–24
- The empirical norm is related to the population L2 norm through concentration and approximation bounds, yielding a bound for deviations between them.The lemma bounds the empirical error using the approximation's sup-norm error, its population L2 error, and a radius term.Source: §C.1 · p. 25
Appendix D. Proof of Theorem 3
The proof of Theorem 3 uses packing and entropy bounds with Fano’s inequality to lower-bound minimax estimation error over the target function class.
Appendix D. Proof of Theorem 3
- The minimax lower-bound argument uses a packing set and Fano’s inequality to bound the probability of misidentifying the selected function.The candidate functions are drawn uniformly from the packing set.Source: Appendix D · pp. 26–27
- The covering entropy of the function class is bounded by combining bounds for its smooth-function and boundary-set components.The class is described as sums of M functions, and each component's covering number is bounded separately.Source: Appendix D · p. 27
- Selecting δ and δ1 of order max{n^-2β/(2β+D), n^-α/(α+2D-2)} yields the statement of Theorem 3.The combined packing entropy is at least the maximum of the smooth-function and boundary-set packing entropies; the smooth-function packing entropy is at least c_l h δ^-D/β.Source: Appendix D · pp. 28–29
Appendix E. Specific Examples of Other Inefficient Methods
The orthogonal-series estimator is consistent for the piecewise-smooth class but has strictly worse-than-optimal order: many basis functions are needed to express its non-smooth structure, increasing variance.
Appendix E. Specific Examples of Other Inefficient Methods
- The orthogonal-series estimator represents functions using an orthonormal basis, with J serving as a hyperparameter.The estimator’s expected loss is decomposed using orthogonality and Parseval’s identity.Source: Appendix E · pp. 29–30
- For smooth functions, the orthogonal-series estimator is known to be minimax-optimal.Source: Appendix E · p. 29
- For D>1, α>2, β>1, and trigonometric or Fourier bases, Proposition 1 states that for sufficiently large n there exist f* in F(M,J,α,β), an input distribution PX, and a positive constant CF.Source: Appendix E · p. 29
- For piecewise-smooth functions, the orthogonal-series estimator’s order is strictly worse than optimal because many basis functions increase variance.The estimator remains consistent because an orthogonal basis in L2 can represent all square-integrable functions.Source: Appendix E · p. 31