On the expressivity of deep Heaviside networks

arXiv:2505.00110 · stat.ML, cs.LG, cs.NA, math.NA · Submitted 2026-08-10 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: I'm Tom, and with me are Jane, Lu, senior AI researcher at Tsinghua, Meng, lead engineer at a mysterious AI startup and Lalam, the in-house Large Language Model.

Jane: Today's paper: "On the expressivity of deep Heaviside networks".

Tom: This paper investigates the expressivity of deep Heaviside networks (DHNs), which are neural networks with several hidden layers and the Heaviside activation function σ0(x) = I(x ≥ 0).

Jane: First, who's behind it and why it matters.

Paper discussion segment 1: Tom: Alright, so the paper starts by laying out the baseline performance of plain Heaviside networks, showing they have some pretty strict limitations on what kind of functions they can accurately represent. They establish a lower bound on approximation error based on the width of that first hidden layer.

Jane: That makes sense; essentially, they are showing that you can’t just stack more layers and make them deeper to fix everything; the initial structure really dictates how well you can approximate a continuous function. This suggests that depth alone isn't the magic ingredient for better representation.

Lu: I noticed they point out that the width of the first hidden layer directly drives this approximation error, which means we need to be very careful about how we set up those initial parameters if we want good results. It reminds me of how foundational choices in a complex system can set the ceiling for everything else.

Meng: If that first layer’s width is so critical, it raises practical questions about hyperparameter tuning; does this mean we have to spend a lot of time just optimizing those initial layer sizes rather than focusing on the deeper architecture?

Lalam: That focus on structure over sheer depth is very insightful for developing scalable AI systems where parameter counts matter immensely.

Paper discussion segment 2: Tom: Moving into the main body, they summarize their findings by proposing two specific structural augmentations to fix these expressivity issues: skip connections and linear neurons. They argue that adding either of these can significantly boost what the network can actually represent.

Jane: So, instead of just relying on the standard structure, they suggest we introduce bypasses—skip connections—or introduce neurons that behave linearly instead of strictly thresholding. It sounds like a way to give these networks more flexibility in their output space.

Lu: The paper shows that for skip-DHNs, the number of pieces a function can be represented as increases dramatically, reaching up to (p one + one) product=two L (s + one). That multiplicative effect of the skip connections is what really opens up the complexity space for approximation.

Meng: From an engineering standpoint, increasing the number of pieces sounds like it means we can model much more intricate shapes or functions with fewer overall parameters than if we just tried to brute-force it with a plain network.

Lalam: That multiplicative increase in expressive power is what’s exciting; it suggests that even simple binary activations can be made surprisingly versatile with the right architectural additions.

Paper discussion segment 3: Tom: Now we get into the specifics of those augmentations, and the authors provide some very concrete approximation results. For skip-DHNs, they show an error bound related to one / ((p one + one) product=two L (s + one)) for approximating functions like x squared on the interval zero one.

Jane: That approximation result is really telling because it connects the architectural choices directly to how well the network can handle non-linear tasks, like squaring a number. It shows a direct path from architecture to achievable accuracy on specific problems.

Lu: Furthermore, they provide complexity bounds for these augmented networks; for skip-DHNs with rectangular architectures, they bound the VC dimension by thirty times Lp squared (Lp). This is a significant jump compared to the plain networks where the VC dimension was only around pd.

Meng: Bounding the VC dimension shows us exactly how much complexity we are dealing with theoretically; knowing it's climbing towards Lp squared instead of just linear in p is a big hint for resource planning in deployment.

Lalam: Knowing these bounds helps us understand the theoretical capacity of an AI system before we even start training, which is crucial for responsible development.

Conclusion: Tom: Well, we’ve talked about how plain Heaviside networks are limited and how adding skip connections or linear neurons unlocks much greater representational power, as detailed in "On the expressivity of deep Heaviside networks." It seems the core idea is that structure matters more than just stacking more identical layers.

Jane: Precisely; the paper shows that by strategically adding either input skip connections or linear neurons, we can improve both the approximation rates and the VC dimensions significantly, moving beyond those initial limitations we discussed.

Lu: I think the implication here is that for future AI architectures, hybrid approaches combining different activation styles are going to be really important for tackling complex functions efficiently.

Meng: Practically speaking, if we can select the right augmentation based on whether we need speed or accuracy, it simplifies the design process for deploying these quantized models in production environments.

Lalam: I think this work really reinforces a vision where AI systems are designed not just for performance in a single metric, but with an awareness of their underlying theoretical limits and how to push those limits through smart architectural choices.

Tom: It’s been fantastic hearing all of you unpack the details of "On the expressivity of deep Heaviside networks." Thanks for tuning in! We’ll be right back after a short break.

Insung Kong, Juntong Chen, Sophie Langer, Johannes Schmidt-Hieber

University of Twente · Xiamen University · Ruhr University Bochum

stat.ML, cs.LG, cs.NA, math.NA

Submitted: 2026-08-10

Updated: 2026-08-11

Comments: 63 pages, 17 figures, published in Constructive Approximation

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 78/100

Key concepts

Deep Heaviside Networks (DHNs): These are neural networks that use the Heaviside activation function, which outputs 1 if the input is non-negative and 0 otherwise. The paper investigates their limitations regarding what continuous functions they can accurately represent.
Skip Connections: These are structural augmentations added to DHNs that allow information to bypass certain layers. The paper shows that skip connections can dramatically increase the number of function pieces a network can represent, leading to higher expressive power.
VC Dimension: This is a measure used to bound the theoretical complexity of a model. The discussion shows that augmented DHNs have much higher VC dimensions compared to plain networks, indicating greater theoretical capacity for modeling complex functions.
Heaviside Activation Function: The Heaviside activation function, denoted as σ0(x), is a simple threshold function. It outputs 1 if the input x is greater than or equal to zero and 0 otherwise. The paper focuses on how networks using this specific activation behave.

Terminology

Activation Function — 53× in this paper · explained in 1 episode
VC Dimension — 44× in this paper · explained in 2 episodes
Accuracy — 4× in this paper · explained in 1 episode
Extreme Learning Machine — 2× in this paper
Hybrid Architectures — 2× in this paper · explained in 3 episodes
Approximation Bound — 1× in this paper · explained in 1 episode
Benchmark — 1× in this paper · explained in 2 episodes
Core — 1× in this paper · explained in 2 episodes
Generalization — 1× in this paper · explained in 13 episodes
Gradient Flow — 1× in this paper · explained in 2 episodes
Neural Network Approximation — 1× in this paper · explained in 2 episodes
Sparsity — 1× in this paper · explained in 4 episodes
Transformer — 1× in this paper · explained in 2 episodes

Summary

Summary

This paper investigates the expressivity of deep Heaviside networks (DHNs), which are neural networks with several hidden layers and the Heaviside activation function σ0(x) = I(x ≥ 0). The authors first demonstrate the limitations of plain DHNs, then propose two structural augmentations—skip connections and linear neurons—to overcome these limitations, and derive upper and lower bounds for the VC dimensions and approximation rates of these network classes. The findings are applied to derive statistical convergence rates for nonparametric regression.

1. Limited Expressivity of Plain DHNs

The paper shows that plain DHNs have limited expressiveness. The key result (Theorem 1) states that for any DHN with depth L and width vector p = (d, p1,..., p L, 1), the restriction of any network function to a line segment is a piecewise constant function with at most p1 + 1 pieces, where p1 is the width of the first hidden layer. The proof is based on the fact that each hidden layer function is a piecewise constant vector-valued function whose number of pieces is at most that of the previous hidden layer. This implies a lower bound on the approximation error: for any continuous function f0, the approximation error is at least (sup f0 - inf f0) / (2(p1 + 1)). The paper notes that the width of the first hidden layer drives the approximation error and depth cannot improve the rate. Proposition 2 shows this lower bound is tight for ridge functions and Lipschitz continuous functions.

2. Skip Connections Augmented DHNs (skip-DHNs)

To improve expressivity, the authors introduce skip connections that connect the input to every hidden layer (except the first). The network class is denoted DHNskip(L, p, s), where s = (s2,..., s L) specifies the number of skip-connected neurons per layer.

Theorem 3 establishes that for any f ∈ DHNskip(L, p, s), the restriction f[x1,x2] is piecewise constant with at most (p1 + 1) ∏ l=2 L (s l + 1) pieces. This shows skip connections can significantly increase the number of pieces compared to plain DHNs.
Theorem 4 provides an approximation result for the square function x ↦ x2 on [0,1], showing that a skip-DHN can approximate it with error at most 1 / ((p1 + 1) ∏ l=2 L (s l + 1)). The proof uses a mixed radix numerical representation and bit extraction. Corollary 5 shows that with s = 1 skip connection per layer, the approximation error ϵ can be achieved with ≲ log2(1/ϵ) neurons and ≲ log3(1/ϵ) network parameters, a significant improvement over plain DHNs which require ≳ 1/ϵ parameters.
Theorem 6 bounds the VC dimension of skip-DHNs with rectangular architecture (width p, s skip connections per layer): VC(DHNskip(L, d: p: 1, s)) ≤ 30 · Lp2 log(Lp) and, under conditions L ∧ p ≥ c ∨ 8 log(Lp) and 1 ≤ s ≤ p, VC ≥ C · Lp2. This shows skip connections increase the VC dimension from ≲ pd (for plain DHNs) to ≍ Lp2.
Theorem 8 establishes that for β-Hölder smooth functions on [0,1] d, the approximation error is bounded by C M (log3(Lp) / (Lp2)) β/d, provided d ≤ s ≤ p and certain conditions on L and p hold. The proof uses bit extraction, Taylor polynomial approximation, and the construction of networks that identify grid cells.

3. Linear Neurons Augmented DHNs (lin-DHNs)

The second augmentation adds s neurons with linear activation to all hidden layers except the last. The network class is denoted DHNlin(L, p, s). The paper notes that Skip-DHNs can also be modeled as lin-DHNs by introducing p0 neurons with linear activation function per layer, giving the inclusion DHN(L, p) ⊆ DHNskip(L, p, s) ⊆ DHNlin(L, p, p0).

Proposition 9 shows that for any f ∈ DHNlin(L, p, s), the restriction f[x1,x2] is piecewise constant with at most ∏ l=1 L (p l + 1) pieces.
Theorem 10 bounds the VC dimension: VC(DHNlin(L, d: p: 1, s)) ≤ 30 · (L2ps ∨ Lp2) log(Lp) and, under conditions L ∧ p ≥ c ∨ 8 log(Lp) and 1 ≤ s ≤ p, VC ≥ C · (L2ps ∨ Lp2). The paper highlights three scenarios: (i) if s ≲ 1, VC is of order L2p ∨ Lp2; (ii) if p ≫ L and 1 ≤ s ≲ p/L, VC is of order Lp2 (same as skip-DHNs); (iii) if s is proportional to p, VC is of order L2p2 (same as deep ReLU networks).
Theorem 11 establishes that for β-Hölder smooth functions, the approximation error is bounded by C M (log3(Lp) / (L2ps ∨ Lp2)) β/d, provided d ≤ s ≤ p and certain conditions hold. The proof uses a modified bit extraction lemma (Lemma 17) that leverages linear neurons.

4. Application to Nonparametric Regression

The paper applies the results to the nonparametric regression model Y = f0(X) + ϵ with X ∈ [0,1] d and standard normal noise. For the least-squares estimator defined in (15) and its truncated version (18), the paper derives the risk decomposition (19):

E[R(f̂ n,B n, f0)] ≲ inf f∈F f - f02∞ + (log3 n / n) VC(F).

For skip-DHNs, plugging in Theorem 6 and Theorem 8 and choosing L n p n2 of order n d/(2β+d) yields the convergence rate n-2β/(2β+d) up to logarithmic factors. For lin-DHNs, plugging in Theorem 10 and Theorem 11 and choosing L n2 p n s n ∨ L n p n2 of order n d/(2β+d) yields the same rate. The paper notes this rate is minimax optimal: the rate n-2β/(2β+d) is the fastest achievable in the worst situation, also known as the minimax rate of convergence.

5. Summary of Main Results (Table 1)

DHN architecture VC dimension Approximation error for H d β(1)

depth L, width p VC ≲ Lp2 log(Lp) ∧ pd p−1 ≲ ϵ ≲ p-(β∧2)/d

depth L, width p, s skip connections per layer VC ≍ Lp2 for 1 ≤ s ≤ p ϵ ≍ (Lp2)-β/d for d ≤ s ≤ p

depth L, width p, s linear neurons per layer VC ≍ Lp2 ∨ L2ps for 1 ≤ s ≤ p ϵ ≍ (Lp2 ∨ L2ps)-β/d for d ≤ s ≤ p

Improvements for AI systems

Based on the paper, here are the specific improvements I can make to AI systems and what the improved systems can do:

Improvement: Implement a neural network that uses Heaviside activation in early layers (for tree-like feature partitioning) and linear activation in later layers (for smooth output regression), with the architecture sized according to the paper's approximation bounds.

What the improved system can do:

Achieve minimax-optimal convergence rates of n(-2β/(2β+d)) for β-Hölder smooth regression functions on tabular data, matching tree-based methods while remaining differentiable for gradient-based training
Handle discontinuous decision boundaries in tabular data more effectively than ReLU networks, which require many neurons to approximate sharp thresholds

Improvement: Add input skip connections to each hidden layer of a binary/quantized neural network, where each hidden layer has at least d skip-connected neurons (d = input dimension).

Improvement: Add s linear (identity) activation neurons to each hidden layer of a quantized network, with s proportional to width p.

Improvement: Use the paper's phase diagram (Table 1) to automatically select depth L, width p, and augmentation level s based on target function smoothness β and input dimension d.

Improvement: Implement the paper's mixed-radix bit extraction technique (Lemma 13) as a reusable module for networks that need to perform precise arithmetic operations.

Improvement: Use the paper's VC dimension bounds to set regularization strength and early stopping criteria for binary/quantized networks.

Improvement: Design an inference engine that exploits the binary nature of Heaviside neurons (outputs only 0 or 1) for skip-DHNs and lin-DHNs.

These improvements are directly derived from the paper's theoretical contributions and can be implemented in existing deep learning frameworks with minimal architectural changes.