# Size and depth of monotone neural networks: interpolation and approximation

arXiv: https://arxiv.org/abs/2207.05275 · HTML: https://mlsanity.com/paper/2207.05275/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 61 references that are in the map.
- First posted on arXiv 12 Jul 2022.

## Builds on (most cited first, 8 of 8)

- [Error bounds for approximations with deep ReLU networks](https://mlsanity.com/paper/1610.01145/) (2016)
- [The Power of Depth for Feedforward Neural Networks](https://mlsanity.com/paper/1512.03965/) (2015)
- [Certified Monotonic Neural Networks](https://mlsanity.com/paper/2011.10219/) (2020)
- [Monotonic Calibrated Interpolated Look-Up Tables](https://mlsanity.com/paper/1505.06378/) (2015)
- [Counterexample-Guided Learning of Monotonic Neural Networks](https://mlsanity.com/paper/2006.08852/) (2020)
- [Neural Networks Learning and Memorization with (almost) no Over-Parameterization](https://mlsanity.com/paper/1911.09873/) (2019)
- [An Exponential Improvement on the Memorization Capacity of Deep Threshold Networks](https://mlsanity.com/paper/2106.07724/) (2021)
- [Fast, Provable Algorithms for Isotonic Regression in all ℓp-norms](https://mlsanity.com/paper/1507.00710/) (2015)

## Built on by (most cited first, 10 of 10)

- [On the Depth of Monotone ReLU Neural Networks and ICNNs](https://mlsanity.com/paper/2505.06169/) (2025)
- [Neural Networks and (Virtual) Extended Formulations](https://mlsanity.com/paper/2411.03006/) (2024)
- [Advancing Constrained Monotonic Neural Networks: Achieving Universal Approximation Beyond Bounded Activations](https://mlsanity.com/paper/2505.02537/) (2025)
- [MORSE-500: A Programmatically Controllable Video Benchmark to Stress-Test Multimodal Reasoning](https://mlsanity.com/paper/2506.05523/) (2025)
- [Smooth Min-Max Monotonic Networks](https://mlsanity.com/paper/2306.01147/) (2023)
- [Robust Reinforcement Learning with Dynamic Distortion Risk Measures](https://mlsanity.com/paper/2409.10096/) (2024)
- [A mathematical certification for positivity conditions in Neural Networks with applications to partial monotonicity and Trustworthy AI](https://mlsanity.com/paper/2406.08525/) (2024)
- [Approximation Depth of Convex Polytopes](https://mlsanity.com/paper/2507.07779/) (2025)
- [Tropical Circuits with Scalar Multiplication Gates](https://mlsanity.com/paper/2607.11540/) (2026)
- [Constrained Hebbian Learning Supports Efficient Representational Allocation under Structural Constraints](https://mlsanity.com/paper/2607.16027/) (2026)

## Abstract (arXiv)

We study monotone neural networks with threshold gates where all the weights (other than the biases) are non-negative. We focus on the expressive power and efficiency of representation of such networks. Our first result establishes that every monotone function over [0,1]d can be approximated within arbitrarily small additive error by a depth-4 monotone network. When d > 3, we improve upon the previous best-known construction which has depth d+1. Our proof goes by solving the monotone interpolation problem for monotone datasets using a depth-4 monotone threshold network. In our second main result we compare size bounds between monotone and arbitrary neural networks with threshold gates. We find that there are monotone real functions that can be computed efficiently by networks with no restriction on the gates whereas monotone networks approximating these functions need exponential size in the dimension.