Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: In this work, authors study the problem of finding size and depth efficient monotone neural networks that interpolates the monotone datasets. Among two popular choice of activation functions, i.e., ReLU and threshold activation function, authors proved that there are monotone functions that cannot be approximated within arbitrary small error by monotone neural networks with ReLU activation function. Thus, in this study monotone neural networks with threshold activations are considered. 

Firstly, authors showed that 2-layered monotone neural network with threshold activation cannot interpolate monotone dataset. Later on they showed that there exist 4 layered monotone neural network with threshold activation function that can interpolate monotone dataset with n points in Rd provided the size of neural network is O(nd). The direct implication of interpolation result is that 4 layered monotone neural networks can approximate arbitrary well any monotone function over [0,1]d.  This is significant improvement over best-known previous result, which states that monotone neural network with threshold activation can approximate any monotone function however depth of the approximating network will scale linearly with the dimension of the input data. 

The authors further investigated on the size required to approximate any monotone function arbitrarily close by the constant depth monotone neural network with threshold activation function. The authors showed that the inductive bias of having positive parameters can lead to a super-polynomial blow-up in the number of neurons when approximating monotone functions.

strengths_and_weaknesses: The paper discusses on the proof that there exist 4 layered monotone neural networks with threshold activation that can interpolate the monotone dataset with n points in Rd. Its direct implication proved that there exists the constant depth monotone network with threshold activation that can approximate the monotone functions arbitrary well. This result comes with the tradeoff over the size of the network. 
The paper is well written, and references are adequate.

questions: At surface level it appears that results might be dependent on the choice of activation function. Is it  possible to throw some light on this aspect? If in practice the threshold function is approximated by sigmoid, will the results still hold?
limitations: N/A
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: A monotonic relationship occurs when an increase (decrease) in an input value gives an increase (decrease) in the output value. Monotone ReLU neural networks preserve this structure in the data by ensuring that the network's weights are positive. There are fundamental questions regarding monotone neural networks and the manuscript investigates: (1) [universality] Can a monotone network of depth L approximate every monotone dataset? [The manuscript proves that L = 2 is not good enough, but L = 4 is.] (2) [Approximation power] Do monotone networks need to be much larger than standard networks? [The manuscript proves that there are maps such that the difference can be larger than any polynomial in d (where d is the number of input neurons). 
strengths_and_weaknesses: The manuscript presents a set of compelling universal approximation theory results for monotone neural networks. I particularly enjoyed Section 5, where the authors used ideas from monotone complexity theory of Boolean functions to construct a monotone function that are much harder (in terms of number of parameters in the neural network) to approximate with monotone neural networks. 

- There is quite a big gap between O(d) neurons required in Theorem 3 and the O(d(Lsqrt(d)/eps)^d) neurons in Theorem 2. Therefore, one expects that this manuscript is not the final word. 

- This manuscript only describes universal approximation theory results, which reveal that monotone neural networks can be far less expressive. There is the additional problem of training that is not discussed here. Therefore, it seems that monotone neural  networks are far from becoming a mainstream neural network model.  

- The problem of monotone approximation has been considered in approximation theory since the 1970s. In the multivariable setting, ideas such as: (1) Monotone tensor product regression splines (for dimension <=5), see [1], (2) Triangulation based monotone splines, e.g., see [2] and [4]. (3) Kernel regression, see [3]. While the results in this manuscript probably do not exist in this literature, it would be nice if the authors could reference the classical literature on monotone approximation 

[1] G. Beliakov, Shape preserving approximation using least squares splines, Approximation Theory Appl., 16 (2000), pp. 80–98.
[2] P. Costantini and C. Manni, A local shape-preserving interpolation scheme for scattered data, Comput. Aided Geom. Des., 16 (1999), pp. 385–405.
[3] P. Hall and L. Huang, Nonparametric kernel regression subject to monotonicity constraints, Ann. Stat., 29 (2001), pp. 624–647.
[4] K. Willemans and P. Dierckx, Smoothing scattered data with a monotone Powell-Sabin spline surface, Numer. Algorithms, 12 (1996), pp. 215–232.
 
WRITING 
The manuscript would benefit from another round of polishing. Though, I find that manuscript is clearly written. Here is a small subset of grammar mistakes that I marked while reading. (I imagine that there are many more.)

p1, line 25: "modeling monotonic relationship" should probably read "modeling the monotonic relationship"
p4, line 134: "requires much larger size" should read "requires a much larger size"
p4, line 154: "may result with negative" should read "may result in negative"
p4, line 161: "First, as using both min and max gates in the same architecture with positive parameters do not fall into the modern paradigm of an activation function." sounds better as "First, using both min and max gates in the same architecture with positive parameters does not fall into the modern paradigm of an activation function."
p5, line 175: "applies for arbitrary dimension larger than 1" should read "applies to arbitrary dimensions larger than 1"
p5, line 180: "One difference of our" should read "One difference between our"
p5, line 185: "require super polynomial" should read "require a super polynomial" 
p5, line 189: "function m, that requires" should read "function m, which requires"
p5, line 206: "Each layer is composed from" sounds better as "Each layer is composed of"
p6, line 229: "positive is indeed without" should be "positive holds without"
p9, line 342: "can can" should be "can" 
p9, line 344: "each gate by a" sounds better as "each gate with a"
p9, line 361: "theses copies" should read "these copies"
questions: - In Theorem 2, the authors prove that if the f is L-Lipschitz then there is a nearby 4-layer neural network with O(d(Lsqrt(d)/eps)^d) neurons. This is a super-exponential blow-up in d. Do the authors believe that O(d(Lsqrt(d)/eps)^d) is necessary? Usually, one expects that as d increases the approximation power of the network increases. 

- I do not understand the comment on line 125 that [8] also constructs a neural network with comparable number of neurons to Theorem 2. It sounds like it might only take O( (L/eps)^d ).
limitations: There are limited potential negative societal impact.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The authors consider interpolation of monotone data (Theorem 1) and approximation of monotone functions (Theorem 2) by neural networks of 4 layers induced by the threshold activation function. The required number of neurons for the approximation is analyzed in Theorem 3. 
strengths_and_weaknesses: The results in the paper verifies the role of depth in interpolation and approximation of monotone functions. These are interesting theoretical findings and help us understand the role of depth in deep learning. 

However, the results cannot be sued in practical applications. The threshold activation function is not continuous, which is difficult for implementations. The monotonicity of data or multivariate functions is often ruined by noise in practice. 



questions: The authors should comment on how noise could be taken into consideration in their study. Is it possible to derive similar results when a continuous activation function is used? 
limitations: No. It would be interesting to consider noisy data and continuous activation functions.
review_title: null

Meta-review: metareview: Surprisingly strong result about the expressive power of monotone networks 
confidence: Certain
Decision: Accept