PaperlayerView exact revision on arXiv

Source-linked AI summary

Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality

Taiji Suzuki

arXiv:1810.08033v1stat.MLcs.LG

TL;DR

The paper asks whether deep ReLU networks can achieve adaptive, theoretically optimal learning rates for broad Besov classes and avoid dimensionality dependence under mixed smoothness. It develops approximation and estimation bounds using ReLU networks, showing minimax-optimal performance on Besov spaces, superiority to linear estimators, and dimensionality avoidance for mixed smooth Besov spaces.

  • Problem

    The paper studies whether ReLU neural networks can achieve optimal learning rates while adapting to spatially inhomogeneous smoothness and high dimensionality.

  • Method

    The paper develops approximation and estimation error bounds for deep ReLU networks on Besov and mixed smooth Besov spaces.

  • Results

    Deep ReLU learning achieves the minimax optimal rate on Besov spaces, outperforms linear estimators, and avoids the curse of dimensionality on mixed smooth Besov spaces.

  • Takeaways & Limitations

    The results support high adaptivity of deep learning to spatially inhomogeneous smoothness and dimensionality.

  • Takeaways & Limitations

    The paper does not address optimization or practical algorithms that efficiently achieve the derived optimal rates.

Abstract

from arXiv · show

Deep learning has shown high performances in various types of tasks from visual recognition to natural language processing, which indicates superior flexibility and adaptivity of deep learning. To understand this phenomenon theoretically, we develop a new approximation and estimation error analysis of deep learning with the ReLU activation for functions in a Besov space and its variant with mixed smoothness. The Besov space is a considerably general function space including the Holder space and Sobolev space, and especially can capture spatial inhomogeneity of smoothness. Through the analysis in the Besov space, it is shown that deep learning can achieve the minimax optimal rate and outperform any non-adaptive (linear) estimator such as kernel ridge regression, which shows that deep learning has higher adaptivity to the spatial inhomogeneity of the target function than other estimators such as linear ones. In addition to this, it is shown that deep learning can avoid the curse of dimensionality if the target function is in a mixed smooth Besov space. We also show that the dependency of the convergence rate on the dimensionality is tight due to its minimax optimality. These results support high adaptivity of deep learning and its superior ability as a feature extractor.

1 INTRODUCTION

The paper develops approximation and estimation analyses for deep ReLU networks on Besov and mixed smooth Besov spaces. It studies adaptivity to spatially inhomogeneous smoothness and dimensionality, showing optimal-rate performance and advantages over linear estimators.

  • Motivation: The paper positions these results as theoretical evidence for the adaptivity and flexibility of deep learning.Its motivation is to understand why deep learning performs well across applications.
  • Research scope: The paper analyzes deep ReLU networks for target functions in Besov spaces and mixed smooth Besov spaces.The analysis covers approximation and estimation error bounds.
  • Besov spaces: Deep learning achieves the minimax optimal rate on Besov spaces and outperforms linear estimators such as kernel ridge regression.The comparison concerns functions whose smoothness is spatially highly inhomogeneous.
  • Besov spaces: The Besov-space analysis targets settings where smoothness varies spatially, a property that distinguishes deep learning from non-adaptive linear methods.The paper frames this as adaptivity to spatial inhomogeneity of the target function.
  • Mixed smooth Besov spaces: Deep ReLU networks can avoid the curse of dimensionality for functions in mixed smooth Besov spaces.The analysis is based on the sparse grid technique and reports a near minimax optimal rate.

2 SET UP OF FUNCTION SPACES

The paper introduces Besov and mixed smooth Besov spaces as function classes for analyzing smoothness-dependent learning rates. It contrasts ordinary and mixed smoothness through their dimensionality dependence and included model classes.

  • Function-space setup: The section defines function classes used to derive approximation and estimation error bounds.These include Besov spaces and their mixed-smoothness variant.
  • Besov spaces: Besov spaces generalize Sobolev spaces and include Hölder spaces, Sobolev spaces, and functions with total variation as special cases.They can also represent spatially inhomogeneous smoothness with spikes and jumps.
  • Ordinary Besov spaces: For ordinary Besov spaces, the minimax estimation rate is lower bounded by n^-2s/(2s+d), so dimensionality dependence is unavoidable.The paper introduces mixed smoothness to seek bounds less heavily affected by dimension.
  • Included models and related classes: Mixed Besov spaces include additive and tensor models and can represent sums with R tending to infinity when the quasi-norm summation converges.The paper relates this framework to existing dimension-robust estimators and Barron-class analyses.
  • Mixed smoothness: Mixed smooth Besov spaces control coordinate-wise mixed derivatives differently from ordinary Besov spaces, affecting approximation convergence rates.The mixed-space derivative condition depends on the maximum derivative order across coordinates, whereas the ordinary condition uses their sum.

3 APPROXIMATION ERROR ANALYSIS

The paper analyzes ReLU-network approximation for Besov and mixed smooth Besov spaces, including broad smoothness regimes and spatially inhomogeneous functions. It establishes optimal approximation behavior and advantages over fixed linear methods, with milder dimensional dependence for mixed smoothness.

  • Network model: The ReLU network class is parameterized by height L, width W, sparsity S, and norm bound B.The analysis evaluates how these quantities should scale to approximate target functions in Lr-norm.
  • Besov approximation mechanism: ReLU networks approximate Besov functions through cardinal B-spline constructions represented by spatially localized basis functions.Resolution controls the scale, while location determines where each basis function is placed; these bases are closely related to wavelets.
  • Besov approximation mechanism: The approximation result applies when 0 < p, q, r ≤∞ and s > d(1/p −1/r)+, including non-continuous regimes where Lr-convergence remains guaranteed.The Holder space appears as the special case p = q = r = ∞.
  • Adaptivity: Fixed-basis linear or nonlinear approximators cannot attain N^-α/d in some regimes, whereas adaptive deep networks can reach the rate-optimal N^-α/d rate.The advantage is especially significant when p < r, because the network can identify where the function requires intensive approximation.
  • Mixed smoothness: The mixed-smoothness bound is better than linear approximation methods because the proof uses adaptive recovery rather than linear recovery.The result connects deep-network construction with adaptive approximation that selects an efficient basis for the target function.
  • Mixed smoothness: For mixed smooth Besov spaces, the network matches optimal linear-width rates in several parameter settings and improves on linear recovery when p < r.When r ≫q, the approximation error is O(N^-s log^s(d−1)(N)), making dimensional dependence milder than for ordinary Besov approximation.

4 ESTIMATION ERROR ANALYSIS

The paper connects ReLU approximation bounds to estimation-error rates for Besov and mixed smooth Besov spaces under a nonparametric regression model. It establishes minimax-optimal behavior, superiority over linear estimators in spatially inhomogeneous settings, and reduced dimensional dependence under mixed smoothness.

  • Statistical setting: The analysis assumes the regression model y_i = f_o(x_i) + ξ_i with bounded input density, Gaussian noise, and i.i.d. observations.The estimator is regularized through network sparsity and bounded parameters, with clipping used to control outputs.
  • Besov spaces: Theorem 2 gives estimation-error bounds for ReLU networks when f_o belongs to a Besov space under s > d(1/p − 1/2)+.The result also assumes bounded Besov and sup norms for the target function.
  • Besov spaces: The deep-learning rate is minimax optimal up to log(n)^2 order and cannot be improved by any estimator.The logarithmic factor could be reduced to log(n) using a construction from prior work, but that refinement is not pursued.
  • Besov spaces: For p < 2, deep learning achieves a rate unavailable to linear estimators, including kernel ridge regression, when target smoothness is spatially inhomogeneous.Linear estimators capture global properties but not local variation, whereas the network adapts to spatial inhomogeneity.
  • Mixed smooth Besov spaces: The mixed-smoothness result eases the curse of dimensionality compared with ordinary Besov analysis while retaining adaptivity to spatially inhomogeneous smoothness.The rate is derived using the paper’s mixed-space estimation theorem and is supported by a minimax lower bound.
  • Mixed smooth Besov spaces: Mixed smooth Besov analysis shows that dimensional dependence can be confined to poly-logarithmic factors and can disappear from the exponent when u = 0.The bound is minimax optimal in the stated parameter regime and nearly minimax elsewhere up to poly-logarithmic factors.

5 CONCLUSION

The paper studies deep ReLU learning for Besov and mixed smooth Besov targets. Its analysis supports minimax-optimal rates, adaptivity to spatial inhomogeneity, and reduced dimensional dependence, while leaving practical optimization for future work.

  • Conclusion: Deep ReLU networks achieve minimax-optimal rates for Besov targets and outperform linear methods when p < 2.The paper associates p < 2 with spatial inhomogeneity in the target function’s shape.
  • Conclusion: For mixed smooth Besov targets, deep learning can adaptively avoid the curse of dimensionality.The bounds use sparse-grid techniques, cardinal B-spline expansions, and adaptive nonlinear approximation.
  • Conclusion: The authors interpret these results as partial support for deep learning’s adaptivity and feature-extraction ability.
  • Conclusion: The paper does not analyze optimization or identify practical algorithms that efficiently attain the derived optimal rates.These questions are left for future work.

A PROOF OF LEMMA 1

The proof constructs ReLU networks that approximate cardinal B-spline products and then clips and combines them to obtain bounded, localized multivariate approximants.

  • A PROOF OF LEMMA 1: A ReLU multiplication network approximates products of inputs while controlling depth, width, sparsity, and parameter magnitude.The construction uses a network φ_mult with explicit architecture bounds.
  • A PROOF OF LEMMA 1: A single ReLU layer realizes the clipping map min{M, max{x, 0}}.This clipping operation is used to constrain intermediate and final network outputs.
  • A PROOF OF LEMMA 1: The proof applies multiplication and clipping networks to approximate the cardinal B-spline basis while preserving boundedness.The resulting function has sup norm at most one and vanishes outside [0, m + 1]^d.
  • A PROOF OF LEMMA 1: The final approximation error is bounded by 2dε′ + ε.The construction combines coordinatewise approximations with a final clipping step.

B PROOF OF PROPOSITION 1

The proof builds Besov approximants from adaptive cardinal B-spline decompositions and replaces the spline basis with ReLU approximations. It controls the retained scales, coefficients, and network complexity to obtain the stated approximation bound.

  • A PROOF OF PROPOSITION 1: Besov functions are decomposed into cardinal B-spline components indexed by resolution k and location j.The decomposition converges in the relevant Lp sense and relates component norms to coefficient magnitudes.
  • A PROOF OF PROPOSITION 1: The construction yields the desired approximation error for functions in the Besov unit ball under the proposition’s parameter conditions.The proof combines the decomposition and basis-approximation lemmas.
  • A PROOF OF PROPOSITION 1: The adaptive approximant retains scales through K and K∗ and allocates level-dependent terms n_k under a total complexity budget N.The scale and allocation schedules depend on the smoothness and integrability parameters.
  • A PROOF OF PROPOSITION 1: The proof substitutes ReLU-approximated B-spline bases into the Besov decomposition to construct f_N.This combines adaptive recovery with neural approximation of each basis function.
  • A PROOF OF PROPOSITION 1: Coefficient magnitudes are bounded using Besov norm equivalence and the maximal retained resolution.The resulting bounds control parameters hidden in the approximated multivariate basis.

C PROOF OF THEOREM 1

The proof constructs a ReLU approximation by replacing cardinal B-spline units with neural networks and controlling the resulting coefficient and parameter counts.

  • C PROOF OF THEOREM 1: The proof approximates the B-spline representation RK(f) using a neural network construction.The approximation is introduced through the index set EK and a ReLU realization of the component basis functions.
  • C PROOF OF THEOREM 1: The proof chooses ǫ to make the accumulated network approximation error at most 2^-Ks.The choice balances the approximation tolerance against the network depth, width, and coefficient factors.
  • C PROOF OF THEOREM 1: Each approximating B-spline unit requires width W0, so the complete network has width W = NW0.The total width is obtained by summing the widths of the N nonzero basis units.
  • C PROOF OF THEOREM 1: The coefficients satisfy |αj,k| ≲ N^(1+1/ν){1∨(1/p−s)+} after bounding the relevant scale factor.This follows from the maximum scale index bound 2^K* ≲ N^(1+1/ν).

D.1 PREPARATION: SPARSE GRID

The sparse-grid construction replaces the full tensor grid with a substantially smaller index set for mixed smooth Besov approximation, while adaptive coefficient selection improves convergence when p < r.

  • D.1 PREPARATION: SPARSE GRID: The sparse-grid approximation error decreases exponentially as M tends to infinity, with K controlling the resolution.The coefficient bound also preserves control by the mixed Besov norm.
  • D.1 PREPARATION: SPARSE GRID: The sparse-grid method uses indices with ∥k∥1 ≤ M rather than the full-grid condition ∥k∥∞ ≤ K* = O(K).This is the central Smolyak-style reduction used to approximate mixed smooth Besov functions.
  • D.1 PREPARATION: SPARSE GRID: O(2^K K^(d−1)) terms replace O(2^(Kd)) full-grid terms, easing the dimensionality dependence for mixed smoothness.The sparse grid is a subset of the regular grid with much smaller cardinality.

D.2 PROOF OF THEOREM 5

The proof of Theorem 5 establishes mixed Besov coefficient norm equivalences and derives adaptive approximation bounds by recursively decomposing coordinates and selecting coefficients.

  • D.2 PROOF OF THEOREM 5: The decomposition is built recursively over coordinate subsets by applying one-dimensional operators while holding the other coordinates fixed.This produces the multidimensional components indexed by k and the active-coordinate set e.
  • D.2 PROOF OF THEOREM 5: The mixed Besov norm is equivalent to the sequence norm of the decomposition coefficients.The proof obtains both inequalities linking the coefficient sequence to ∥f∥MBs^α_p,q.
  • D.2 PROOF OF THEOREM 5: The coefficient quasi-norm is likewise equivalent to the mixed Besov norm of f.This follows from the scale-dependent quasi-norm relation for the cardinal B-spline coefficients.
  • D.2 PROOF OF THEOREM 5: When p < r, the proof uses an adaptive approximation method that sorts coefficients by decreasing absolute value.The sorted coefficients determine which terms are retained in the adaptive construction.

E PROOFS OF THEOREMS 2 AND 3

The proofs derive generalization bounds by covering sparse ReLU network classes and combining those bounds with approximation estimates under boundedness and network-parameter constraints.

  • E PROOFS OF THEOREMS 2 AND 3: The estimator argument applies a general risk proposition to a clipped neural-network class under a uniform bound F.The class is clipped before its covering number is used in the statistical bound.
  • E PROOFS OF THEOREMS 2 AND 3: For mixed smoothness, the proof uses S = O(2^K D_K,d), L = O(K), and W = O(2^K D_K,d) in the covering-number calculation.The resulting bound depends on the sparse-grid cardinality D_K,d.
  • E PROOFS OF THEOREMS 2 AND 3: The proof bounds the covering number of Φ(L, W, S, B) using the network sparsity, depth, width, and parameter norm constraints.For fixed sparsity patterns, parameter perturbations are propagated through the composed network maps.
  • E PROOFS OF THEOREMS 2 AND 3: The proof notes technical flaws in the cited lemma’s uniform-bound risk argument and states that a slight modification fixes them, adding a −log(δ) term.The statement is retained after replacing δF with δF^2.
Loading 1810.08033v1…