Nonlinear approximation via compositions

Zuowei Shen, Haizhao Yang, Shijun Zhang

TL;DR

This paper proves that composing functions—the core mechanism of deep neural networks—significantly accelerates the rate at which we can approximate complex, non-smooth functions. By moving from a single-layer to a three-layer ReLU network, the approximation error drops twice as fast as width increases, though the authors find that adding even more layers eventually yields diminishing returns for this specific mathematical task.

What Problem Does This Paper Address?

In the world of numerical analysis, "nonlinear approximation" is the art of reconstructing a target function using a limited "budget" of $N$ terms chosen from a library (a dictionary). Traditionally, researchers used tools like wavelets or simple one-hidden-layer neural networks. However, while these tools work well for smooth functions, they often struggle with high-dimensional or non-smooth data (like H¨older continuous functions, which can be jagged).

The authors tackle a fundamental question: Does the "depth" of a composition (stacking functions on top of each other) actually improve the fundamental approximation rate? While deep learning is a massive empirical success, the theoretical "why" behind the power of composition—specifically how it relates to the number of parameters ($N$)—needed more rigorous quantification.

Methods

The researchers use a mix of constructive mathematical proofs and computational complexity analysis.

  1. Dictionary Construction: They define a dictionary $\mathcal{D}_L$ consisting of ReLU Feed-Forward Neural Networks (FNNs) with a fixed depth $L$ and width $N$.
  2. Constructive Proofs: They don't just say an approximation exists; they show how to build it. They use "break points" in ReLU functions to create continuous piecewise linear (CPL) functions that can fit any set of samples.
  3. VC-Dimension Analysis: To prove that their rates are "tight" (meaning you can't do better), they use Vapnik–Chervonenkis (VC) dimension bounds to show the unachievable limits of these networks.
  4. Parallel Computing Theory: They apply standard models of time and memory complexity to compare how different network architectures (wide vs. deep) perform on modern parallel hardware (like GPUs).

Datasets

As a theoretical paper, it primarily relies on mathematical abstractions. However, for the validation section, the authors generated:

  • Synthetic Smooth Functions: 50 random smooth functions created using a specific wavelength-based algorithm.
  • Sampling: These functions were sampled at 20,000 points in a $d$-dimensional cube $[0, 1]^d$ to create training and testing sets.

Key Insights and Ideas

  • The Power of Three: For multi-dimensional functions ($d > 1$), increasing the depth from $L=1$ to $L=3$ effectively doubles the exponent of the approximation rate. Specifically, the error rate improves from $O(N^{-\alpha/d})$ to $O(N^{-2\alpha/d})$.
  • The "L=2" Jump: For one-dimensional functions, just adding a second layer ($L=2$) is enough to double the approximation power.
  • Diminishing Returns of Depth: Interestingly, the analysis shows that for H¨older continuous functions, increasing depth beyond $L=3$ does not further improve the approximation rate in terms of $N$. Depth is powerful, but it has a "saturation point" for this class of problems.
  • Parallel Efficiency: The paper highlights a practical trade-off. While deep networks are mathematically elegant, they are sequential by nature. In a parallel computing environment with many cores, a wide and shallow network is often more efficient than a narrow and deep one because it can better utilize simultaneous processing.

Key Results

  • Explicit Error Bounds: The authors provide the first explicit formulas for the best $N$-term approximation error for ReLU networks with fixed depth.
  • Tightness: They proved that their derived rate $O(N^{-2\alpha/d})$ is essentially the best possible for any network with a fixed number of layers.
  • Numerical Validation: In experiments with $N$ ranging from 32 to 128, they observed that increasing width consistently reduced test error, and the "improvement ratio" aligned with their theoretical predictions. For example, in Table 3, a network with width 64 and depth 4 achieved a test error of $4.27 \times 10^{-5}$, significantly outperforming shallower versions.

Limitations and Future Work

  • Optimization Gap: The paper assumes we can find the optimal parameters for the network. In reality, training deep networks via ADAM or SGD is a non-convex optimization problem that may settle for local minima, meaning the practical error might be higher than the theoretical "best $N$-term" error.
  • Function Specificity: The results are tailored to H¨older continuous functions. While this is a broad class, future work could extend these proofs to even more complex function spaces or different activation functions (like Sigmoid or Tanh).
  • The Dimensionality Challenge: While they proved $L=2$ doubles the rate for $d=1$, extending that specific "doubling" proof to general $d$-dimensional functions remains a challenge for future research.

Summary updated

Abstract

Given a function dictionary D<math><mi mathvariant="script" is="true">D</mi></math> and an approximation budget N∈N<math><mrow is="true"><mi is="true">N</mi><mo linebreak="goodbreak" linebreakstyle="after" is="true">∈</mo><mi mathvariant="double-struck" is="true">N</mi></mrow></math>, nonlinear approximation seeks the linear combination of the best N<math><mi is="true">N</mi></math> terms {Tn}1≤n≤N⊆D<math><mrow is="true"><msub is="true"><mrow is="true"><mrow is="true"><mo is="true">{</mo><msub is="true"><mrow is="true"><mi is="true">T</mi></mrow><mrow is="true"><mi is="true">n</mi></mrow></msub><mo is="true">}</mo></mrow></mrow><mrow is="true"><mn is="true">1</mn><mo is="true">≤</mo><mi is="true">n</mi><mo is="true">≤</mo><mi is="true">N</mi></mrow></msub><mo linebreak="goodbreak" linebreakstyle="after" is="true">⊆</mo><mi mathvariant="script" is="true">D</mi></mrow></math> to approximate a given function f<math><mi is="true">f</mi></math> with the minimum approximation error εL,f≔min{gn}⊆R,{Tn}⊆D‖f(x)−∑n=1NgnTn(x)‖.<math><mrow is="true"><msub is="true"><mrow is="true"><mi is="true">ε</mi></mrow><mrow is="true"><mi is="true">L</mi><mo is="true">,</mo><mi is="true">f</mi></mrow></msub><mo linebreak="goodbreak" is="true">≔</mo><munder is="true"><mrow is="true"><mo class="qopname" is="true">min</mo></mrow><mrow is="true"><mrow is="true"><mo is="true">{</mo><msub is="true"><mrow is="true"><mi is="true">g</mi></mrow><mrow is="true"><mi is="true">n</mi></mrow></msub><mo is="true">}</mo></mrow><mo linebreak="badbreak" is="true">⊆</mo><mi mathvariant="double-struck" is="true">R</mi><mo is="true">,</mo><mrow is="true"><mo is="true">{</mo><msub is="true"><mrow is="true"><mi is="true">T</mi></mrow><mrow is="true"><mi is="true">n</mi></mrow></msub><mo is="true">}</mo></mrow><mo linebreak="badbreak" is="true">⊆</mo><mi mathvariant="script" is="true">D</mi></mrow></munder><mo is="true">‖</mo><mi is="true">f</mi><mrow is="true"><mo is="true">(</mo><mi mathvariant="bold-italic" is="true">x</mi><mo is="true">)</mo></mrow><mo linebreak="goodbreak" is="true">−</mo><munderover is="true"><mrow is="true"><mo linebreak="badbreak" is="true">∑</mo></mrow><mrow is="true"><mi is="true">n</mi><mo linebreak="badbreak" is="true">=</mo><mn is="true">1</mn></mrow><mrow is="true"><mi is="true">N</mi></mrow></munderover><msub is="true"><mrow is="true"><mi is="true">g</mi></mrow><mrow is="true"><mi is="true">n</mi></mrow></msub><msub is="true"><mrow is="true"><mi is="true">T</mi></mrow><mrow is="true"><mi is="true">n</mi></mrow></msub><mrow is="true"><mo is="true">(</mo><mi mathvariant="bold-italic" is="true">x</mi><mo is="true">)</mo></mrow><mo is="true">‖</mo><mo is="true">.</mo></mrow></math>Motivated by recent success of deep learning, we propose dictionaries with functions in a form of compositions, i.e., T(x)=T(L)∘T(L−1)∘⋯∘T(1)(x)<math><mrow is="true"><mi is="true">T</mi><mrow is="true"><mo is="true">(</mo><mi mathvariant="bold-italic" is="true">x</mi><mo is="true">)</mo></mrow><mo linebreak="goodbreak" is="true">=</mo><msup is="true"><mrow is="true"><mi is="true">T</mi></mrow><mrow is="true"><mrow is="true"><mo is="true">(</mo><mi is="true">L</mi><mo is="true">)</mo></mrow></mrow></msup><mo is="true">∘</mo><msup is="true"><mrow is="true"><mi is="true">T</mi></mrow><mrow is="true"><mrow is="true"><mo is="true">(</mo><mi is="true">L</mi><mo linebreak="badbreak" is="true">−</mo><mn is="true">1</mn><mo is="true">)</mo></mrow></mrow></msup><mo is="true">∘</mo><mo linebreak="goodbreak" is="true">⋯</mo><mo is="true">∘</mo><msup is="true"><mrow is="true"><mi is="true">T</mi></mrow><mrow is="true"><mrow is="true"><mo is="true">(</mo><mn is="true">1</mn><mo is="true">)</mo></mrow></mrow></msup><mrow is="true"><mo is="true">(</mo><mi mathvariant="bold-italic" is="true">x</mi><mo is="true">)</mo></mrow></mrow></math>for all T∈D<math><mrow is="true"><mi is="true">T</mi><mo linebreak="goodbreak" linebreakstyle="after" is="true">∈</mo><mi mathvariant="script" is="true">D</mi></mrow></math>, and implement T<math><mi is="true">T</mi></math> using ReLU feed-forward neural networks (FNNs) with L<math><mi is="true">L</mi></math> hidden layers. We further quantify the improvement of the best N<math><mi is="true">N</mi></math>-term approximation rate in terms of N<math><mi is="true">N</mi></math> when L<math><mi is="true">L</mi></math> is increased from 1 to 2 or 3 to show the power of compositions. In the case when L>3<math><mrow is="true"><mi is="true">L</mi><mo linebreak="goodbreak" linebreakstyle="after" is="true">&gt;</mo><mn is="true">3</mn></mrow></math>, our analysis shows that increasing L<math><mi is="true">L</mi></math> cannot improve the approximation rate in terms of N<math><mi is="true">N</mi></math>.In particular, for any function f<math><mi is="true">f</mi></math> on [0,1]<math><mrow is="true"><mo is="true">[</mo><mn is="true">0</mn><mo is="true">,</mo><mn is="true">1</mn><mo is="true">]</mo></mrow></math>, regardless of its smoothness and even the continuity, if f<math><mi is="true">f</mi></math> can be approximated using a dictionary when L=1<math><mrow is="true"><mi is="true">L</mi><mo linebreak="goodbreak" linebreakstyle="after" is="true">=</mo><mn is="true">1</mn></mrow></math> with the best N<math><mi is="true">N</mi></math>-term approximation rate εL,f=O(N−η)<math><mrow is="true"><msub is="true"><mrow is="true"><mi is="true">ε</mi></mrow><mrow is="true"><mi is="true">L</mi><mo is="true">,</mo><mi is="true">f</mi></mrow></msub><mo linebreak="goodbreak" linebreakstyle="after" is="true">=</mo><mi mathvariant="script" is="true">O</mi><mrow is="true"><mo is="true">(</mo><msup is="true"><mrow is="true"><mi is="true">N</mi></mrow><mrow is="true"><mo is="true">−</mo><mi is="true">η</mi></mrow></msup><mo is="true">)</mo></mrow></mrow></math>, we show that dictionaries with L=2<math><mrow is="true"><mi is="true">L</mi><mo linebreak="goodbreak" linebreakstyle="after" is="true">=</mo><mn is="true">2</mn></mrow></math> can improve the best N<math><mi is="true">N</mi></math>-term approximation rate to εL,f=O(N−2η)<math><mrow is="true"><msub is="true"><mrow is="true"><mi is="true">ε</mi></mrow><mrow is="true"><mi is="true">L</mi><mo is="true">,</mo><mi is="true">f</mi></mrow></msub><mo linebreak="goodbreak" linebreakstyle="after" is="true">=</mo><mi mathvariant="script" is="true">O</mi><mrow is="true"><mo is="true">(</mo><msup is="true"><mrow is="true"><mi is="true">N</mi></mrow><mrow is="true"><mo is="true">−</mo><mn is="true">2</mn><mi is="true">η</mi></mrow></msup><mo is="true">)</mo></mrow></mrow></math>. We also show that for Hölder continuous functions of order α<math><mi is="true">α</mi></math> on [0,1]d<math><msup is="true"><mrow is="true"><mrow is="true"><mo is="true">[</mo><mn is="true">0</mn><mo is="true">,</mo><mn is="true">1</mn><mo is="true">]</mo></mrow></mrow><mrow is="true"><mi is="true">d</mi></mrow></msup></math>, the application of a dictionary with L=3<math><mrow is="true"><mi is="true">L</mi><mo linebreak="goodbreak" linebreakstyle="after" is="true">=</mo><mn is="true">3</mn></mrow></math> in nonlinear approximation can achieve an essentially tight best N<math><mi is="true">N</mi></math>-term approximation rate εL,f=O(N−2α∕d)<math><mrow is="true"><msub is="true"><mrow is="true"><mi is="true">ε</mi></mrow><mrow is="true"><mi is="true">L</mi><mo is="true">,</mo><mi is="true">f</mi></mrow></msub><mo linebreak="goodbreak" linebreakstyle="after" is="true">=</mo><mi mathvariant="script" is="true">O</mi><mrow is="true"><mo is="true">(</mo><msup is="true"><mrow is="true"><mi is="true">N</mi></mrow><mrow is="true"><mo is="true">−</mo><mn is="true">2</mn><mi is="true">α</mi><mo is="true">∕</mo><mi is="true">d</mi></mrow></msup><mo is="true">)</mo></mrow></mrow></math>. Finally, we show that dictionaries consisting of wide FNNs with a few hidden layers are more attractive in terms of computational efficiency than dictionaries with narrow and very deep FNNs for approximating Hölder continuous functions if the number of computer cores is larger than N<math><mi is="true">N</mi></math> in parallel computing.
BibTeX
@inproceedings{shen2019nonlinear,
  author = {Zuowei Shen and Haizhao Yang and Shijun Zhang},
  title = {{Nonlinear approximation via compositions}},
  booktitle = {Neural Networks},
  year = {2019},
  url = {https://openreview.net/forum?id=1gIXjzidBy},
}
Figure