The Comparative Power of ReLU Networks and Polynomial Kernels in the Presence of Sparse Latent Structure

Frederic Koehler, Andrej RisteskiICLR 2019 · OpenReview

Introduction

This paper challenges traditional "worst-case" approximation theory by demonstrating that for data with sparse latent structure, small 2-layer ReLU networks are exponentially more efficient than low-degree polynomials. While classical theory suggests polynomials require massive degrees to mimic ReLUs, the authors prove that in structured settings, "polylogarithmic" degree polynomials can actually close the theoretical gap. However, they remain computationally impractical compared to neural networks.

The Problem: Beyond Worst-Case Analysis

In classical approximation theory, researchers often ask how well one function class (like polynomials) can approximate another (like neural networks) over an entire box or interval. This represents a worst-case analysis. However, real-world data rarely reflects worst-case scenarios; it is typically high-dimensional but highly structured. For example, images are not composed of random pixels but rather lie on low-dimensional manifolds.

The authors address the disconnect between theoretical "worst-case" pessimism and empirical success. Specifically, they investigate a regression task where the data possesses a sparse latent structure. In this setting, the observed data $X$ is a noisy, linear transformation of a hidden sparse vector $Z$, and the goal is to predict a label $Y$ that depends linearly on that hidden $Z$. The core question is whether neural networks are fundamentally better equipped to capture this structure than traditional polynomial kernels.

Methodology: Modeling Sparse Latent Structure

The authors employ a combination of statistical learning theory, complex analysis, and synthetic simulations to explore this question.

  1. Generative Model: They define a "latent-variable" process where they first sample a sparse vector $Z$. They then produce observations $X = AZ + \text{noise}$ (where $A$ is a dictionary matrix) and labels $Y = \langle w, Z \rangle$.
  2. ReLU Analysis: The study demonstrates that a 2-layer ReLU network can implement a "soft-thresholding" operation, which is a standard and highly effective method for recovering sparse signals from noise.
  3. Polynomial Analysis: To establish lower bounds for polynomials, the authors use Fourier analysis in the Hermite basis. To prove upper bounds—showing that polynomials can succeed if the degree is sufficiently high—they utilize complex-analytic techniques (specifically Bernstein’s Theorem on the polynomial approximation of analytic functions) to construct a polynomial that mimics the "denoising" behavior of a ReLU.

To verify their theoretical bounds as the problem scales, the authors rely on synthetic datasets generated according to this model, testing dimensions up to $n=4096$. This allows for precise control over parameters like dimensionality ($n$), latent vector sparsity ($k$), and noise level ($\sigma$).

Key Insights: Denoising and the Computational Gap

  • The Power of Denoising: The primary advantage of a ReLU network in this structured setting is its ability to "zero out" small, noisy coordinates. This non-linearity acts as a natural, highly effective filter for sparse data.
  • Worst-Case vs. Average-Case: Classical results dictate that a polynomial of degree $\Omega(1/\epsilon)$ is needed to approximate a ReLU. In high dimensions, this implies a required degree of $\sqrt{n}$. However, the authors show that if the focus is restricted to the "relevant" parts of the data (the sparse structure), a much lower polylogarithmic degree ($O(\log^2 n)$) is sufficient.
  • The Computational Gap: Even though a sufficiently high-degree polynomial can represent the target function, the number of terms in such a polynomial grows super-polynomially ($n^{\log n}$). This starkly illustrates why neural networks are practically superior: they achieve the same "denoising" power with drastically fewer parameters and significantly less computation.

Key Results and Experimental Verification

The theoretical and empirical findings highlight a clear divergence in efficiency:

  • ReLU Efficiency: Small 2-layer ReLU networks achieve an error rate of $O(\sigma^2 k \log m)$, which is nearly information-theoretically optimal.
  • Polynomial Failure: Polynomials with a degree less than $\log m$ perform poorly, proving essentially no better than a "trivial" predictor that always outputs zero.
  • The "Matching" Degree: To match the performance of a ReLU network, a polynomial requires a degree of at least $\Omega(\log m / \log \log m)$.

Simulations confirmed these theoretical insights. As the polynomial degree increases, the error drops, but the ReLU network consistently maintains a significant lead in efficiency and accuracy across various dimensions.

Comparison of error rates between a 2-Layer ReLU Network and a Degree 17 Polynomial across varying dimensions.

Limitations and Future Directions

While the paper provides a robust framework for understanding structured data, it notes several limitations:

  • Linear Latent Structure: The current model assumes a linear relationship between the latent variables $Z$ and the observations $X$ (and labels $Y$). Real-world data frequently involves complex, non-linear latent mappings.
  • Network Depth: The study focuses exclusively on 2-layer networks. Exploring how depth facilitates learning in even more complex structured settings (such as hierarchical sparsity) remains a promising avenue for future research.
  • Classification Tasks: The present work is constrained to regression. Extending these "structural" insights to classification tasks—where approximation only needs to be highly accurate near the decision boundary—is an important open challenge.

Summary updated

Abstract

There has been a large amount of interest, both in the past and particularly recently, into the relative advantage of different families of universal function approximators, for instance neural networks, polynomials, rational functions, etc. However, current research has focused almost exclusively on understanding this problem in a worst case setting: e.g. characterizing the best L1 or L_{infty} approximation in a box (or sometimes, even under an adversarially constructed data distribution.) In this setting many classical tools from approximation theory can be effectively used. However, in typical applications we expect data to be high dimensional, but structured -- so, it would only be important to approximate the desired function well on the relevant part of its domain, e.g. a small manifold on which real input data actually lies. Moreover, even within this domain the desired quality of approximation may not be uniform; for instance in classification problems, the approximation needs to be more accurate near the decision boundary. These issues, to the best of our knowledge, have remain unexplored until now. With this in mind, we analyze the performance of neural networks and polynomial kernels in a natural regression setting where the data enjoys sparse latent structure, and the labels depend in a simple way on the latent variables. We give an almost-tight theoretical analysis of the performance of both neural networks and polynomials for this problem, as well as verify our theory with simulations. Our results both involve new (complex-analytic) techniques, which may be of independent interest, and show substantial qualitative differences with what is known in the worst-case setting.
BibTeX
@inproceedings{koehler2019comparative,
  author = {Frederic Koehler and Andrej Risteski},
  title = {{The Comparative Power of ReLU Networks and Polynomial Kernels in the Presence of Sparse Latent Structure}},
  booktitle = {International Conference on Learning Representations},
  year = {2019},
  url = {https://openreview.net/forum?id=Cu-QtXsGDZM},
}

Loading related content...

Figure