TL;DR
This paper reveals that the boundary geometry of a convex domain fundamentally dictates how efficiently shallow ReLU networks can approximate functions. By introducing domain-dependent weights on network coefficients, the authors prove that the optimal approximation rate is determined by a single geometric growth exponent related to how many small "caps" are needed to cover the boundary.
What Problem Does This Paper Address?
In the world of neural network theory, we often ask: "How many neurons ($n$) do I need to achieve a certain approximation error?" For shallow ReLU networks, a classical result is that for functions in a "variation unit ball" (where the sum of absolute coefficients is $\le 1$), the error in $L^2$ norm typically decays at a rate related to $n^{-1/2}$ or slightly better depending on the dimension.
However, this classical view treats all neurons equally. In reality, a ReLU neuron might be active across the entire domain, or it might only "fire" in a tiny sliver near the boundary. Intuitively, a neuron that only affects a small region should "cost" less in our coefficient budget than one that affects the whole space.
The authors address a critical gap: How does the specific shape of the domain's boundary affect approximation rates when we account for these geometric differences? They move beyond simple cubes or balls to study general convex bodies, asking how the "curviness" or "flatness" of the boundary changes the fundamental limits of what a network can learn.
Methods
The researchers introduce a framework of weighted variation spaces. They assign a weight to each neuron based on its activation cap—the specific region of the convex body $K$ where the neuron's output is non-zero.
Key methodological steps include:
- Geometric Parameterization: They define a weight $w(z) = h_z \theta_z^\eta$, where $h_z$ is the maximum amplitude of the neuron and $\theta_z$ is its relative volume. The parameter $\eta$ allows them to "relax" the constraint on neurons with small activation regions.
- The "Wet Part" and Effective Cap Count: To capture the boundary's complexity, they use the concept of the "wet part"—the union of all small activation caps.
- Growth Exponent $\kappa(K)$: They define a single geometric value, $\kappa(K)$, which measures how quickly the number of required caps grows as the caps get smaller. This turns out to be the "master key" for the approximation rate.
- Randomized Compression: They prove that a large network can be "compressed" into a smaller one with $n$ neurons by randomly sampling from the original neurons, ensuring the weighted coefficient sum does not increase.
Datasets
As a theoretical mathematical study, this paper does not use empirical datasets. Instead, it evaluates approximation performance on various convex bodies in $\mathbb{R}^d$, including:
- Planar bodies: Disks, polygons, and general 2D convex sets.
- Polytopes: High-dimensional cubes and simplexes.
- Smooth bodies: $C^2$ convex bodies with positive curvature (like Euclidean balls).
- Product domains: Cylinders (a disk cross an interval) and other combinations.
Key Insights and Ideas
- Boundary Geometry is a Bottleneck: The "curvier" a boundary is, the harder it is to approximate functions near it. For a fixed dimension, a ball is "harder" to approximate on than a cube because the ball has an infinite number of "corners" (points of high curvature) that require many small neurons to cover.
- The $\kappa(K)$ Classification: The authors show that for many shapes, the optimal approximation exponent is simply the minimum of the classical rate and a boundary-limited rate determined by $\kappa(K)$.
- Sharp Thresholds for "Fast" Learning: There is a specific threshold for the weight parameter $\eta$. If you don't penalize small neurons enough, the boundary geometry takes over and slows down the approximation rate. If you stay below this threshold, you can achieve the "classical" fast rate even with a more relaxed budget.
- Pruning without Penalty: A surprising result is that if your target function is already a finite ReLU network, you can approximate it with a smaller network using a subset of the exact same neurons without increasing the total weighted cost.
Key Results
The paper provides a definitive table of optimal polynomial approximation exponents ($r_*$) for different geometries.
- For Polytopes (Cubes): The geometric exponent is 0, meaning the boundary doesn't slow down approximation. The rate is the classical $(d+3)/2d$.
- For Euclidean Balls: The boundary is at its most complex ($\kappa(K)$ is maximized). The rate is significantly affected by the weight parameter $\eta$.
- Dimensional Independence: In 2D, the results apply to all convex bodies regardless of smoothness.
- Curvature Matters: For $C^2$ bodies, even a single "patch" of positive curvature on the boundary is enough to dictate the approximation rate for the entire domain.
Limitations and Future Work
- General Convex Bodies: While the authors provide bounds for all convex bodies, they haven't yet proven that $\kappa(K)$ alone determines the rate for every possible convex shape in high dimensions (specifically for very large $q$ values in $L^q$ norms).
- Vanishing Curvature: For $C^2$ bodies where the curvature might vanish at certain points (like a "flat" spot on a mostly round pebble), the classification is still incomplete for dimensions $d \ge 3$.
- Computational Complexity: The paper proves that optimal compressed networks exist, but it does not provide an efficient algorithm to find them in a practical training scenario. Future work could bridge this gap between approximation theory and optimization.
Summary updated