Lower bounds over Boolean inputs for deep neural networks with ReLU gates

2017/11/08 by Anirbit Mukherjee, Mukherjee, Anirbit, Amitabh Basu +1 · 1 citation
Computer Science · Engineering · Mathematics · #Adversarial Robustness in Machine Learning #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Ferroelectric and Negative Capacitance Devices #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Neural and Evolutionary Computing (cs.NE) #Stochastic Gradient Optimization Techniques #cs.CC #cs.LG #cs.NE #stat.ML

paper · pdf · doi:10.48550/arxiv.1711.03073

openalex publication_date 2017/11/08 · arxiv created 2017/11/09 · arxiv updated 2017/11/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Motivated by the resurgence of neural networks in being able to solve complex learning tasks we undertake a study of high depth networks using ReLU gates which implement the function x ↦ max\0,x\. We try to understand the role of depth in such neural networks by showing size lowerbounds against such network architectures in parameter regimes hitherto unexplored. In particular we show the following two main results about neural nets computing Boolean functions of input dimension n, 1. We use the method of random restrictions to show almost linear, Ω(ε^2(1-δ)n^1-δ), lower bound for completely weight unrestricted LTF-of-ReLU circuits to match the Andreev function on at least (1)/(2) +ε fraction of the inputs for ε> √2\fraclog^\frac 22-δ(n)n for any δ∈ (0,\frac 1 2) 2. We use the method of sign-rank to show exponential in dimension lower bounds for ReLU circuits ending in a LTF gate and of depths upto O(n^ξ) with ξ< (1)/(8) with some restrictions on the weights in the bottom most layer. All other weights in these circuits are kept unrestricted. This in turns also implies the same lowerbounds for LTF circuits with the same architecture and the same weight restrictions on their bottom most layer. Along the way we also show that there exists a ℝ^ n→ ℝ Sum-of-ReLU-of-ReLU function which Sum-of-ReLU neural nets can never represent no matter how large they are allowed to be.

Cited by

• Better Neural Network Expressivity: Subdividing the Simplex

Related

• On the Expressiveness of Rational ReLU Neural Networks With Bounded Depth
• Neural Networks with Small Weights and Depth-Separation Barriers
• Exponential Lower Bounds for Threshold Circuits of Sub-Linear Depth and Energy
• Depth-Bounds for Neural Networks via the Braid Arrangement
• Approximating Continuous Functions by ReLU Nets of Minimal Width