Function approximation and nonparametric regression with binary and ternary ReLU networks

Technical Summary: Function Approximation and Nonparametric Regression with Binary and Ternary ReLU Networks

Problem Statement
Deep neural networks (DNNs) have become standard tools for classification, pattern recognition, and prediction. However, achieving high accuracy often necessitates models with significant parameter counts, leading to high computational costs and memory requirements. This poses challenges for deployment on low-capacity devices. To address this, researchers have explored restricting network weights to discrete sets, specifically binary weights $\{ \pm 1 \}$ and ternary weights $\{ 0, \pm 1 \}$. While such networks offer advantages in memory reduction and energy efficiency, a theoretical gap remains regarding their expressive power: specifically, whether deep binary and ternary ReLU networks can approximate complex smooth functions and achieve optimal statistical rates in nonparametric regression comparable to their real-valued counterparts.

Methodology
The paper investigates the approximation capabilities of deep sparse ReLU networks with restricted weight sets. The author builds upon existing results regarding the approximation of $\beta$-Hölder functions by deep sparse ReLU networks with weights in the interval $[-1, 1]$ and the specific set $\{0, \pm 1/2, \pm 1, 2\}$.

The core methodological contribution involves constructing explicit mappings to simulate networks with weights in $\{0, \pm 1/2, \pm 1, 2\}$ using networks with strictly binary $\{ \pm 1 \}$ or ternary $\{ 0, \pm 1 \}$ weights. This is achieved through:

1. Weight Scaling and Homogeneity: Leveraging the positive homogeneity of the ReLU activation function ($\sigma(ax) = a\sigma(x)$ for $a > 0$) to absorb scaling factors into the network architecture.
2. Layer Expansion: Introducing additional hidden layers to replicate specific linear combinations and scaling operations.
   • To simulate weights $\{0, \pm 1/2, \pm 1, 2\}$, the author constructs a network with ternary weights $\{0, \pm 1\}$ (scaled by $1/2^{L+3}$) using 2 additional hidden layers. This involves replicating input coordinates and using linear combinations of $\{0, \pm 1/2\}$ to represent the target weights.
   • To simulate ternary weights $\{0, \pm 1/2\}$, the author constructs a network with binary weights $\{ \pm 1 \}$ (scaled by $1/4^{L+6}$) using 3 additional hidden layers. This involves computing specific linear combinations of inputs using weights $\pm 1/4$ to reconstruct the necessary values.
3. Nonparametric Regression Analysis: Applying these approximation results to the empirical risk minimization problem for nonparametric regression. The author defines a class of sparse ternary ReLU networks with weights $\{0, \pm 1\}$ and analyze the prediction error of the empirical risk minimizer over this class.

Key Contributions and Results

1. Function Approximation (Theorem 2.2):
   The paper proves that any function $f_0$ belonging to the Hölder ball $C^\beta_d(K)$ on $[0, 1]^d$ can be $\epsilon$-approximated by:

   • Deep Sparse Ternary ReLU Networks: Networks with weights in $\{0, \pm 1\}$ (scaled by a factor of $1/2^{L+3}$).
   • Deep Binary ReLU Networks: Networks with weights in $\{ \pm 1 \}$ (scaled by a factor of $1/4^{L+6}$).

   The depth and width of these networks are shown to be comparable to those required for networks with weights in $\{0, \pm 1/2, \pm 1, 2\}$, with only a constant factor increase in width and a small additive increase in depth. The approximation error bound remains of the order $O(N^{-\beta/d} + N^{-m})$, where $N$ is a parameter related to the network size and sample complexity.

2. Nonparametric Regression (Theorem 3.1):
   The author applies the approximation results to the problem of recovering an unknown regression function $f_0$ from noisy observations $Y_i = f_0(X_i) + \epsilon_i$. They define a hypothesis space $\mathcal{F}_n$ consisting of deep sparse ternary ReLU networks with weights $\{0, \pm 1\}$.

   The main result establishes that the prediction error (mean squared error) of the empirical risk minimizer $\hat{f}_n$ over $\mathcal{F}_n$ satisfies:
   $$R(\hat{f}_n, f_0) \leq C n^{-\frac{2\beta}{2\beta+d}} \log^2 n$$
   where $n$ is the sample size, $\beta$ is the smoothness parameter, and $d$ is the dimension.

Significance and Claims
The paper claims that deep sparse ternary ReLU networks with weights $\{0, \pm 1\}$ are theoretically sufficient to achieve the minimax rate of prediction for $\beta$-smooth regression functions, up to a logarithmic factor. This demonstrates that the extreme quantization of weights to binary or ternary sets does not fundamentally degrade the statistical efficiency of the model for nonparametric regression tasks, provided the network depth and sparsity are appropriately adjusted.

The author emphasizes that their work extends previous findings on networks with weights $\{0, \pm 1/2, \pm 1, 2\}$ (from reference [3]) by showing these approximations can be realized with strictly binary and ternary weights. The results provide a theoretical justification for the use of binary and ternary networks in high-accuracy regression tasks, suggesting that the computational and memory benefits of such networks can be realized without sacrificing optimal convergence rates.