Size and depth of monotone neural networks: interpolation and approximation
Authors: Dan Mikulincer
Daniel Reichman
Venue: NeurIPS 2022 Accept (2022)
Keywords: Monotone neural networks
interpolation
expressivity
benefit of depth

Abstract: 	Monotone functions and data sets arise in a variety of applications. We study the interpolation problem for monotone data sets: The input is a monotone data set with $n$ points, and the goal is to find a size and depth efficient monotone neural network with \emph{non negative parameters} and threshold units that interpolates the data set. We show that there are monotone data sets that cannot be interpolated by a monotone network of depth $2$. On the other hand, we prove that for every monotone data set with $n$ points in $\mathbb{R}^d$, there exists an interpolating monotone network of depth $4$ and size $O(nd)$. Our interpolation result implies that every monotone function over $[0,1]^d$ can be approximated arbitrarily well by a depth-4 monotone network, improving the previous best-known construction of depth $d+1$. Finally, building on results from Boolean circuit complexity, we show 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.  

Size and depth of monotone neural networks: interpolation and approximation
Dan Mikulincer
Daniel Reichman Worcester Polytechnic Institute
Massachusetts Institute of Technology
Abstract
Monotone functions and data sets arise variety of applications. We study the interpolation problem for monotone data sets: The input is monotone data set with n points, and the goal is to find a size and depth efficient monotone neural network with non negative parameters and threshold units that interpolates the data set. We show that there are monotone data sets that cannot be interpolated by a monotone network of depth On the other hand, we prove that for every monotone data set with n points in Rd, there exists an interpolating monotone network of depth and size (nd)). Our interpolation result implies that every monotone function over [0, 1]d can be approximated arbitrarily well by a depth- 4 monotone network, improving the previous best-known construction of depth d+ 1. Finally, building on results from Boolean circuit complexity, we show that the inductive bias of having positive parameters can lead to super-pol super-polynomial blow-up in the number of neurons when approximating monotone functions.
Introduction
The recent successes neural networks are owed, at least in part, to their great approximation and interpolation power. However, some prediction tasks require their predictors to possess specific properties. This work focuses on monotonicity and studies the effect on overall expressive power when restricting attention to monotone neural networks.
Given x. y E Fd we consider the partial ordering.
for every i I....d. d, [x] [y]+
Here, and throughout the paper, we use [or]: for the 5th coordinate of æ. A function f: [0.1] 1] B is monotone' if for every two vectors x, y E [0, 1]
f(x) f(y).
Monotone functions arise in several fields such as economics, operations research, statistics, health- care, and engineering. For example, larger houses typically result in larger prices, and certain fea- tures are monotonically related to option pricing [12] and bond rating [9]. As monotonicity con- straints abound, there are specialized statistical methods aimed at fitting and modeling monotonic functions such Isotonic Regression [1, 22, 24] well many other works related to monotone approximation [7, 17, 71. Neural networks are no exception: Several works are devoted to the study of approximating monotone functions using neural networks [9.35,38].
When using a network to approximate monotone function, one might try to "force" the network to be monotone. A natural way to achieve this is to consider only networks where every parameter
As will only be dealing with monotone increasing functions, we shall refer to monotone increasing functions monotone.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

(other than the biases) non-negative'. Towards this aim, we introduce the following class of monotone networks.
Recall that the building blocks of a neural network are the single one dieeeesiiionll neurons (w,b(x)) = (ww 2) + b) where E R$ is an input of the neuron, w E R is weight parametrizing - IR is the activation function, and E RR is a bias term. Two popular choices for activation functions, that we shall also consider, are the ReLU activation function ( = max(0, 2) and the threshold activation function ((2) 1(2 2 0), which equals if = 2 and zero otherwise. We slightly abuse the term and say that network is monotone if every single neuron is a monotone function. Since both ReL.U and threshold are monotone, this requirement, of having every neuron a monotone function, translates to w having all positive entries.
the neuron,
Such restriction on the weights can be seen as an inductive bias reflecting prior knowledge that the functions we wish to approximate are monotone. One advantage of having such "positivity bias" is that it guarantees the monotonicity of the network. Ensuring that a machine learning model approx- imating a monotone function is indeed monotone is often desirable [15, 25, 26]. Current learning methods such as stochastic gradient descent and proppapopagttion for training a network are not guaranteed (when applied to monotone training set) to return a network computing monotone function. Furthermore, while there are methods for certifying that given neural network imple- ments monotone function [25,38], the task of certifying monotonicity remains a non-trivial task.
Restricting the weights raises several questions on the behavior of monotone neural networks com- pared to their more general, unconstrained, counterparts. For example, should we still expect mono- tone networks to be able approximate arbitrary monotone functions within an arbitrarily small error?
Continuing line of work monotone networks, [9,35], we further elucidate the above comparison and uncover some similarities (a universal approximation theorem) and some surprising differences (the interplay of depth and monotonicity) between monotone and general networks. We will mainly be interested expressiveness, the ability to approximate monotone functions and to interpolate monotone data sets using monotone neural networks of constant depth.
1.1 Our contributions
First, is not a priori clear that monotone networks can approximate every possible monotone function even fit any monotone data set. Here monotone data is set of labeled points (14,,i) E (TR x IR)" with the properties
i x, +
and I2 S
- y: Bi-
In the monotone interpolation problem we seek find monotone network N such that for every i E [n], (x.) = yı.
On expressive power and interpolation: While it well-known that general networks with ReLU activation are universal approximators (can approximate any continuous function on bounded domain), perhaps surprisingly, the same is not true for monotone networks and monotone functions. Namely, there are monotone functions that cannot be approximated within an arbitrary small additive error by a monotone network with ReLU gates regardless of the size and depth of the network. This fact was mentioned in [25]: We provide a proof for completeness.
There exists monotone function f [0, 1] + IR and constant > 0, such that for any monotone network N with ReLU gates, there exists œ E [0, 1], such that
Lemma 1.
[N(x) f(x))
Proof. It known that a sum of convex functions ft. Easi is convex provided that for every i, aq 2 It also known that the maximum of convex functions gi, max is convex function. It follows from the definition of the ReLU gate (in particular, ReLU is a convex function) that a neural network with positive weights at all neurons is convex. As there are monotone functions that are not convex, the result follows.
We restrict our attention to non negative prediction problems: The domain of the function we seek to approximate does not contain vectors with negative coordinate.

---

For a concrete example one may take the function f(z) = vz for which the result holds with c =
In light of the above, we shall henceforth only consider monotone networks with a threshold activa- tion function and discuss, for now, the problem of interpolation. For general networks (no restriction on the weights) with threshold activation, it has been established, in the work of Baum [3], that even with 2 layers, for any labeled data set in Red there exists an interpolating network.
Our next result is another negative result, which shows that there is an inherent loss of expressive power, when transitioning to 2-layered monotone threshold networks, provided that the dimension is at least two. When the input is real-valued there always exists an interpolating monotone network.
This is simple fact whose proof is omitted: It can be proved using similar ideas to those in [9].
Lemma 2. Let d 2 2. There exists a monotone data set (I,, ys ve)e E (IR" x R)). such that any 2epth-2 monotone network N, with threshold activation must satisfy.
(xx) # y::
for some i [n]-
Given the limitation of depth-2 monotone networks, it may seem that, like the case of ReLUs, the class of monotone networks with threshold activation is too limited, in the sense that it cannot approximate any monotone function, with constant depth (allowing the depth scale with the input dimension was considered in [9], see below). One reason for such a belief is that, for non-monotone networks, depth 2 suffices ensure universality: any continuous function over a bounded domain can be approximated by a depth-2 network [2, 8, 19] and this universality result holds for networks with threshold or ReLUs as activation functions. Our first main result supports the contrary this belief. We establish a depth separation result for monotone threshold networks, and show that, by slightly increasing the number of layers. monotone networks can interpolate arbitrary monotone data sets. Thereafter a simple argument shows that monotone networks of bounded depth become universal approximators of monotone functions. As noted, this is in sharp contrast to general neural networks, where adding extra layers can affect the efficiency of the representation [13], but does not change the expressive power.
Theorem 1.
Let (zi, 9:) st)se(n] E (IE" x R)" be monotone data set. There exists monotone threshold network N, with 4 layers and ((dd) neurons such that,
N(a;)= = y
for every E [n].
Moreover, if the set (az)ie(m) is totally-ordered, in the sense that, for every i,j E [n], either S Jj or æj 2 Tú, then one may take N to have 3 layers and (n) neurons.
We also complement Theorem with lower bound that shows that the number of neurons use is essentially tight, up to the dependence on the dimension.
Lemma 3. There exists monotone data set (xt, y))e C (IR" R)" such that, if N is an interpolating monotone threshold network, the first layer of N must contain n units. Moreover, this lower bound holds when the set (Zz)se(m] is ooddely-
The lower bound of Lemma 3 demonstrates another important distinction between monotone and general neural networks. According to [3], higher- dimeessodssssonss allow general networks, with 2 layers, to be more compact. Since the number of parameters in the networks increase with the dimension, one can interpolate labeled data sets in general position with only O (*) neurons. Moreover, for deeper networks, a recent line of work, initiated in [40], shows that O( neurons suffice. Lemma 3 shows that monotone networks cannot enjoy the same speed-up, either dimensional or from depth, in efficiency.
Since dealing with monotone functions, our interpolation results immediately imply uni- versal approximation theorem for monotone networks of depth 4.
Theorem 2. Let f [0, R be continuous monotone function and let > 0. Then, there exists monotone threshold network N, with 4 layers, such that, for every [0, 1]a.
[x()) f(x)) S
3

---

(
(a (Lxaa)
If the function f is L-Lipschitz, for some > O, one can take N to have O
neurons.
While it was previously proven, in [9], that monotone networks with threshold activation can approx- imate any monotone function, the depth in the approximating network given by [9] scales linearly with the input dimension. Our result is thus a significant improvement which only requires constant depth. When looking at the size of the network, the linear depth construction, in [9], iteratively evaluates Riemann sums, and builds a network which is piccewise-constant on a grid. Hence, for T--Lipschitz functions, it would require a similar amount of neurons. Again, see that comparable results can be obtained while maintaining constant depth. Whether one can achieve similar results to Theorems 1 and 2 with only 3 layers is interesting question which we leave for future research.
Efficiency when compared to general networks: We have shown that, with layers, monotone networks can serve as universal approximates. However, even if a monotone network can approx- imate a monotone function arbitrarily well it might be that it requires a much larger size, when compared to unconstrained networks. In this case, the cost of having much larger network might outweigh the benefit of having a network that is guaranteed to be monotone.
In our second main result we verify that this can sometimes be the case. We show that using mono- tone networks to approximate, in the -nomm, monotone function [0, 1] - R can lead to a super-poly super-polynomial blow-up in the number of neurons. Namely, we demonstrate smooth monotone function h [o, 1] + R with poly(d) Lipschitz constant such that can be approximated within an additive error of > 0 by general neural network with poly(d) neurons. Yet any monotone network approximating within error smaller than 2 requires super-polynomial size in
Theorem 3. There exists a monotone function h : [0, 1j + R. such that:
Any monotone threshold network N which satisfies,
[N) h(x)) 2- for every x E [0,
must have elloo" d) neurons.
For every E > O, there exists general threshold network N, which has poly(d) neurons and such that,
[N(x) hxxx)) < e, for every 10.
2
Related work
We not aware of previous work studying the interpolation problem for monotone data sets ing monotone networks. For general data sets and interpolation using networks with no positivity requirement there is extensive research regarding the size and depth needed to achieve interpo- lation [5, 10, 40, 44] starting with the seminal work of Baum studying this problem for networks with threshold units [3]. Known constructions of neural networks achieving interpolations are non- monotone: they may result in negative parameters even for monotone data sets.
Several works have studied approximating monotone (real) functions over a bounded domain using monotone network. Sill [35] provides a construction of a monotone network (all parameters are non- negative) with depth 3 where the first layer consists of linear units divided into groups, the second layer consists of max gates where each group of linear units of the first layer is fed to a different gate and final gate computing the minimum of all outputs from the second layer. It is proven in [35] that this class of networks can approximate every monotone function over [0, 1]d. We remark that this is very different than the setting considered in this present work. 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. Moreover, we are not aware of works prior Theorem 2, that show how to implement or approximate min and max gates, with arbitrary fan-ins, using constant depth monotone networks. Finally. the results from [35] focus on approximating arbitrary monotone functions and do not consider the monotone interpolation problem studied here.
'There are constructions of depth-3 threshold circuits with discrete inputs that are given m numbers each represented by bits and compute the maximum of these numbers [37] This setting is different from ours where the inputs are real numbers.

---

Later, the problem of approximating arbitrary monotone functions with networks having non- negative parameters using more standard activation functions such thresholds or sigmoids has been studied in [9]. In particular [9] gives a recursive construction showing how to approximate in the 6o norm arbitrary monotone function using network of depth d + 1 (d-hidden layers) with threshold units and non-negative parameters. In addition [9] provides a construction of a monotone function g [0, 1]2 - E that cannot be approximated in the &oo norm with error smaller than 1 1/8 by a network of depth 2 with sigmoid activation and non-negative parameters, regardless of the number of neurons in the network. Our Lemma 2 concerns networks with threshold gates and applies to arbitrary dimension larger than 1. It can also be extended to provide monotone functions that cannot be approximated by monotone networks with thresholds of depth 2.
Lower bounds for monotone models of computation have been proven for a variety of models [11], including monotone De Morgan" circuits [14, 3830,,3 31J, monotone arithmetic circuits and compu- tations 16,21,43), which correspond to polynomials with non non-negative coefficients, and circuits with monotone real gates [20, 28] whose inputs and outputs
Boolean. One difference between separation result regarding monotone and non-monotone networks and these works is that we con- sider real differentiable functions opposed to Boolean functions. Furthermore we need functions that can be computed by an unconstrained neural network of polynomial size. In contrast, known lower bounds for circuits with real monotone gates apply to Boolean functions that are believed to be intractable (require a super polynomial number of gates) to compute even with non-monotone circuits (e.g., deciding if' graph contains a clique of a given size). Finally our model of compu- tation of neural networks with threshold gates differs from arithmetic circuits [34] which use gates that compute polynomial functions.
To achieve our separation result we begin with a Boolean function m, which requires a super- polynomial size to compute by any Boolean circuit with monotone threshold gates, but can be computed efficiently with arbitrary threshold circuits: the existence of m follows from [31]. There- after show how to smoothly extend Proving lower bounds for neural networks with a continuous domain by extending a Boolean func- tion for which lower bounds known function I' whose domain is (0, 1 d has been done before 42]. However the extension method in these works do not yield a function that is mono- tone. Therefore, we use different method based on the multi-linear extension.
have domain [0, 1]4 while preserving monotonicity.
3 Preliminaries and notation
We work on Rd, with the Euclidean inner product (,,-). For k E N, we denote [k] = {1, k}
and use {eiheed for standard unit vectors in Rdd, That is, for i E [d]. e,
(0, (0...., 0,1, 1,0,0...... 0..0.....
i- 1 times
d- times
For Rd and E [d]. we write [o)] == (x, e,), the 7th coordinate of æc
With slight abuse of notation, when the dimension of the input changes to, say, R$ will also use {e, Nel to stand for standard unit vectors in R* To avoid confusion, we will always make sure to make the dimension explicit.
neural network of depth is a function Rdd + RR which can be written as a composition,
N(x)
where for é E [L]. N₂ Rd + Rd++ is a layer. We set dp = d, dr+1 = and term de+1 as the width of layer E. Each layer is composed of single neurons in the following way: for E [de+1]. [Ne(=)), = ((w x) + bf) where o R + R is the activation function, wf E Rd is the weight vector, and bf E R is the bias. The only exception is the last layer which is an affine functional of the previous layers, (z = (w=, x)) + b4. For a weight vector w E Rd and bias b' E TR.
Suppose that the activation function is monotone. We say that network N is monotone, if, for every E [L] and i E 1. the weights vector of has all positive coordinates. In other words, [wf]] 2 0, for every E [d.].
'Circuits with AND well OR gates without negations.
5

---

counter-example to expressibility
We outline the ideas behind Lemma 2. We find it instructive to consider the case d = 2. Lemma follows via a simple generalization of this case: a proof of the Lemma can be found in supplementary material. Recall that (xx) 1(x 0) is the threshold function and consider the monotone set,
31 (2, 0), 31 0
(0, 2), = 0
I3 (1, 1), y3
Assume towards a contradiction that there exists a network (xx) = Σ amd ((x, wm) bm), which interpolates the set. Set
1 = {m E (23, wm) 2 bm3 ) = {m E [r]][um]] + [um]2 2 bml}.
The set is the set of all neurons which are active on æg. and, since (2xz) = 1, I is non-empty. We also define,
I = {m I| [[]]] 1 2 [wm]2]
= {m E 7| [/]] 2 [wm]1]-
It is clear that Ii 12 I. Observe that for
It. by monotonicity, we have (m), wm) 2 [wm]] 2 [um]i + [mm]2 (1z3, Wm). Since the same also holds for m E 12 and 12. we have,
N(x) N(x2) z Σ amd ((11, wm) .bm) + Σ and ((x2, wm) - bm)
meh
mE12
2
Σ
amd ( (103, Wm) bm)) +
Σ
and ((23, Wm) - bm)
mET
mETz
Σ
amo ((Is, wm) - bm) N(11) =
(1)
mEr
Hence, either N(x1) 2 or ((x2)
5 Four layers suffice with threshold activation
Let (:) E (RR x IR)" be a monotone data set, and assume, with no loss of generality,
S y1 S U2 S y/n-
If, for some i, [n]] with i of i' we have yı yeu and x; S xy, will assume i. Other ties are resolved arbitrarily. Note that the assumption that the yi 's are positive holds without loss of generality, as one can always add a constant to the output of the network handle negative labels.
This section is dedicated to the proof of Theorem 1, and we will show that one can interpolate the above using monotone network with hidden layers. The first hidden layer is of width dn and the second and third of width n.
Throughout shall use att) 1(t 0). for the threshold function. For l E {1, 3} will also write (wf, b() for the weights of the ęth neuron in level t. We shall also use the shorthand, (x) = a wf) - b().
We first describe the first two layers. The second layer serves monotone embedding into R". We emphasize this fact by denoting the second layer as E Rd + RR"", with ith coordinate is given by, [Exx)], (x)),, where (N)), (r). for 1...., nd, are the outputs of the first layer.
'The 2D example here as well its generalization for higher dimensions can be easily adapted to give an example of monotone function that cannot be approximated in fa depth-two monotone threshold network.

---

First hidden layer: The first hidden layer has units. For j = I,.... dn. We let e, be the zth standard basis vector in R and define,
(x)x) = ((r, el mod d)+1) ( 1 eG mod d)+1))
In other words, w] E(j med d)+11 and bj (1
: eij mod d)+1) (the addition of offsets the fact that mod operations can result 0). To get a feeling of what the layer does, suppose that j mod d, then unit j is activated on input iff the (r + 1)th entry of æ is at least the (r + 1)th entry of 2 211
Second hidden layer: The second layer has units. For j ,,..., nd, with slight abuse of notation we now use ej for the jth standard basis vector in Rnd and define unit i ,,..., o Rnd + R. by.
d Σ (y, ed(i- 1)+r) -d) )
oz()) =
Explicitly, w/ = >n= Ed(i-1)+r and by d. With this construction in hand, the following is the main property of the first two layers.
Lemma 4, Let = I, Then, [E(x)]; = if and only if 2 xs. Otherwise, [E(x)]; = 0.
Proof. By construction, we have [F(x));
and only if Er= 1 (d( 2 d. For each
[d]. 0) (( E 10, Thus, [B(x)]; 1 if and only if, for every r E [d]. d2 1. But a d(1-1)+ (I) = equivalent to [z], 2 [rs]r. Since this must hold for every E [d], we conclude x z;
The following corollary is now immediate.
Corollary 4. Fix E [n] and let E [n]. Ifj < then [R(z;)] = 0. If 2 i, then there exists such that [E(x))le =1
Proof. For the first item, if j < i, by the ordering of the labels (2), we know that 2j E 24. By Lemma 4, [E(x,)l: O.
For the second item, by construction, [E(x,)], 1. Since j 2 é, the claim concludes.
The third hidden layer: The third layer contains units with weights given by w D Cr and 6 = 1. Thus,
[E((())))))
(F(((()))
Lemma 5. Fix E [n] and let i E [n]. of (F(ar)) i 2 i and (F((z)) = otherwise.
Proof. By Corollary 4, [Exz)], 0. for every > j. In particular, if i > j. by (3), we get, of (E(;)) (-1) = 0. On the other hand, if 2 i, then by Corollary 4, there exists i' 2 i such that [(x,)) Ir = 1. and, (E(()) = o(E((r))) 1) =1
The final layer: The fourth and final layer is linear functional of the output of the third layer. Formally, for Rd. the output of the network is, N(x) Σ (E())), for some weights
vector 3 E To complete the construction we now define the entries of wd as [wr]s J = ys Wi-1 with yo = 0. We are now ready to prove Theorem 1.
7

---

Proof of Theorem 1. Consider the function (x)
Σ [ [ (B(x)) described above. Clearly,
it is a network with 3 hidden layers, by construction. To see that it is monotone, observe that for l E {1, 2,, each wf is sum of standard basis vectors, and thus has non-negative entries. The weight vector w also has non-negative entries, since, by assumption, yi 2 fi-1-
We now show that N interpolates the data set (2z, 1=) Indeed, fix j E [n]. By Lemma 5, we
have, (2², = Σ [o)))o) = Σ [w" = Σ (v= yi-1) = y5 yo = Vy- The proof is complete, for the general case.
To handle the case of totally- (e()) we slightly alter the construction of the first two layers, and compress them into a single layer satisfying Lemma 4, and hence Lemma 5.
The total-order of (az))e(m) implies the following: For every i E [n)]. there exists r(t) E [d]. such that for any j E [m], (zi]+6) < (Tylr(e) if and only if < j. In words, for every point in the set, there exists coordinate which separates it from all the smaller points. We thus define wi ex(1) and =
{ ifi 10 ifi> j
From the above it is clear that -
((25)1(0) 1) As in the general case, we define E(x) Rd + R" by [E(x)]; = of (x), and note that Lemma
4 holds for this construction of E as well. The next two layers are constructed exactly like in the general case and the same proof holds.
O
We conclude this section with two comments. First, as noted, our interpolation scheme can be used to prove that any continuous monotone function can be approximated by monotone threshold network which is Theorem 2. A proof can be found in the supplementary. Second, interpolating monotone networks are wide: It turns out, (n)) neurons may be needed for monotone interpola- tion. A proof of this (Lemma 3) can be found in the supplementary as well. For general threshold networks (no restriction on the weights) one can interpolates n points using O(v + f())) neu- rons where f depends the minimal distance between any two of the data points [29,40]. Hence Lemma 3 shows that there exist monotone data sets such that interpolating them with a monotone network entails quadratic blowup in the size of the network even if the data set is well separated.
6
A super polynomial separation between the size of monotone and arbitrary threshold networks
By the universal approximation result for monotone threshold networks, Theorem 2, we can ap- proximate monotone functions by monotone networks. Are there functions such that monotone networks approximating them provably require much larger size than networks which are allowed to have negative parameters as well? We show that the answer positive when seeking an foo- approximation smaller than for any E E 1/2).
Our proof of this fact builds on findings from monotone complexity theory of Boolean functions.
Given an undirected graph G = (V, E) with 2n vertices a matching M is a set of pairwise disjoint edges. A perfect matching is matching of size n (which is largest possible). There are efficient algorithms for deciding if a bipartite graph has a perfect matching [23]. Furthermore, by standard results that convert Turing machines that decide an algorithmic problem with inputs of size n in time t(n) to threshold circuits with O(t(n)²) gates, [32, 36), it follows that there is a network of size polynomial in n that decides, given the incidence matrix of graph, whether it has a perfect matching. A seminal result by Rzaborov [31] shows that the monotone complexity of the matching function is not polynomial.
Theorem S. Let be the Boolean function that receives the adjacency matrix of a 2n-vertex graph G and decides if has a perfect matching. Then, any Boolean circuit with AND and OR gates that computes g has size n Mlog v). Furthermore, the same lower bound applies if the graph is restricted be bipartite graph G(A, B, E) where |A] - [B] Definition (Matching probabilities in non-homogeneous random bipartite graphs). Let p = (p E 1, and define G(p) to be random bipartite graph on vertex set [n] x [n].
is the bi-partition of the graph.
8

---

such that each edge (i.j) appears independently with probability Pij. for every 1 i S n. Define m : [0, 1j + [0, 1] as m(p) P (G(p) contains a perfect matching).
When p E {0, 1j m(p) reduces to the indicator function of a perfect matching in given bipartite graph. Thus mpp) should be thought of as the harmonic (or multi-linear) extension of the indicator function to the solid cube [0, 1|mxn.
Theorem 3 is an immediate consequence of the following more specific theorem, which is our main result for this section.
Theorem 7. The function defined above is smooth monotone function with Lipschitz constant S n, which satisfies the following: If N is a monotone threshold network of size co((lon =)², there exists E [0, 101m, such that, [N(p) m(p) 2 z Furthermore, for every fixed E > 0 there exist general threshold network N of polynomial size in n, such that for all E [0, 1)=x,, (N(p)
m(p) S E.
Our proof of Theorem 7 is divided into three parts. We first establish the relevant properties of m. We then show that m cannot be approximated by a monotone network of polynomial size. Finally, we show that m can be approximated, arbitrarily well, by a general network with polynomial size. We begin by collecting several simple facts about the function m. All missing proofs can be found in the supplementary. A standard coupling argument (omitted) shows that m is monotone.
S This is simple consequence of the fact that is the harmonic extension of a bounded function. The fact that m is smooth can again be seen from the multi-linear extension. Proofs that m has these properties can be found in the supplementary. The proof (whose details can be found in the supplementary) that the function m cannot be approximated by monotone network of polynomial size uses the fact [4] that a threshold gate with s inputs, non negative parameters and Boolean inputs can be computed by a monotone De Morgan circuit of size poly(s). Therefore, if there was monotone network of size e)(()og)))) approximating m(x) we could replace each gate with monotone De Morgan circuit entailing a polynomial blowup to the size of the network. This in turn would imply the existence of a monotone De Morgan circuit of size (((gg))))) computing m over Boolean inputs which would contradict? Theorem 5. Summarizing:
We have that m is Lipschitz continuous: Let p. p' E [o, 1]mX", Then, (m(p)-m(p
p'll-
Lemma 6. I is monotone threshold network of size eo((logn))) there exists p E [0, 1jmXn, such that, (p)) mpp) 2 1
2-
Finally, we show how to approximate m with a network (without weight restrictions) of polynomial size. To estimate the probability a graph G(p) drawn according to a probability vector has perfect matching we can realize independently (polynomially) many copies of graphs distributed as G(p) and estimate the number of times a perfect matching is detected. In order to implement this idea two issues need to be addressed: the use of randomness by the algorithm (our neural networks do not use randomness) and the algorithm dealing with probability vectors in [0, 1]nXa that may need infinitely many bits to be represented in binary expansion.
We first present a randomized polynomial-time algorithm, denoted A, for approximating m(p). We then show how to implement it with (deterministic) threshold network. Algorithm works as follows. Let q0. r() be polynomials to be defined later. First, the algorithm (with input p) only considers the q(z)) most significant bits the binary representation of every coordinate in p. Next realizes r (n) independent copies of G(p). It checks for each one of these copies whether it contains a perfect matching of size n. Let i. be the number of times a perfect matching is detected (1 depends on p: We omit this dependency to lighten up notation). The algorithm outputs A(p) (()) Clearly the running time of this algorithm is polynomial.
Let P be the vector obtained from p when considering the g(n) most significant bits in each coor- dinate, and observe A(p) law A(P). We next show how to implement this algorithm by neural network of polynomial size that does not use randomness. For proof please see the supplementary.
The function depends also but omit this dependency it is always clear from the context. 7 This shows that the size of such a monotone network cannot polynomial n.
We use the based poly-time algorithm decide if a bipartite graph has a perfect matching.
9

---

Lemma 7. Let 8 E (0, 1) be a fixed constant. Then, i E [0, 1jnx is such that every coordinate Py can be represented by most ((n) bits there exists neural network of polynomial size N such that for every E [0, 10,1) [m(p) - (P)) 2 /2
We can now prove the following Lemma concluding the proof of Theorem 7.
Lemma 8. For every fixed > 0 there exist general threshold network N of polynomial size in n, such that for all E [0, 1j (N(p) m(p) S E.
Proof. Set 8 and let N be the network constructed in Lemma 7 with aceuracy parameter 6.
2
Choose (n) which satisfies q(n) log( x²). Thus, Lemma implies, for every p [0, 1)mxx:
(m(p) - N(P)) 88+
2
S
E + = E.
8
V29(n)
2 2
7
Conclusion
We studied neural networks with nonnegative weights and examined their power and limitation in approximating monotone functions.
Our results reveal that for the ReLU activation, restricting the weights to be nonnegative severally limits the ability of the model to express monotone functions. For threshold activation have shown that the restriction to positive parameters is less severe and that universality can be achieved constant depth. addition, we have shown that monotone neural networks can be much more resource consuming, in terms of the number of neurons needed to approximate monotone functions.
We focused the threshold activation function. It is interesting direction extend our results for other activation functions such as sigmoids. For the universality result of depth monotone function it seems plausible could approximate thresholds by sigmoids to prove that monotone networks of depth with sigmoids are universal approximators of monotone functions. For our lower bounds based on the matching function m appears that new ideas are needed to show super polynomial separation between the size needed for monotone as opposed to arbitrary networks with sigmoids to approximate m.
The field of Boolean circuit complexity has been used before to address theoretical questions related to neural networks (e.g., [6, 16, 27, 33]) and we believe that additional insights could be found by studying the intersection of circuit complexity and deep learning. With regard to monotone neural networks it is likely that stronger lower bounds can be proved when the depth of the network is bounded. Proving separation between monotone and non monotone networks with respect to the square loss is another avenue for further research.
One aspect we did not consider here is learning neural networks with positive parameters using gra- dient descent. It would be interesting to examine the efficacy of gradient methods both empirically and theoretically. Such study could lead to further insights regarding methods that ensure that a neu- ral network approximating monotone function is indeed monotone. Finally, did not deal with generalization properties of monotone networks: Devising tight generalization bounds for monotone networks is left for future study.
References
[1] Richard E. Barlow, Daniel J. Bartholomew, James M. Bremner, and Hugh D. Brunk. Statistical inference under order restrictions: the theory and application of isotonic regression. Wiley, 1972.
[2] Andrew R Barron. Universal approximation bounds for superpositions of a sigmoidal function. IEEE Transactions on Information theory, 39(3):930-945, 1993.
[3] Fric Baum. On the capabilities of multilayer perceptrons. J. Complexity 403):193-215, 1988.
10

---

[4] Amos Beimel and Enav Weinreb. Monotone circuits for monotone weighted threshold func- tions. Inform. Process. Lett., 97(():12-18, 2006.
[5] Sebastien Bubeck, Ronen Eldan, Yin Tat Lee, and Dan Mikulincer. Network size and size of the weights in memorization with two-layers neural networks, Advances in Neural Information Processing Systems, 33:4977-4988 2020.
[6] Arkadev Chattopadhyay, Rajit Datta, and Partha Mukhopadhyay. Lower bounds for monotone arithmetic circuits via communication complexity. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 786-799, 2021.
[7] Paolo Costantini and Carla Manni. A local phepe-pre interpolation scheme for scattered data. Computer Aided Geometric Design, (665):3854405 1999.
[8] George Cybenko. Approximation by superpositions of sigmoidal function. Mathematics of control, signals and systems, 303):303-3,,, 1989.
[9] Hennie Daniels and Marina Velikova. Monotone and partially monotone neural networks.
IEEE Transactions Neural Networks, 21(6):90-9917, 2010.
[10] Amit Daniely. Neural networks learning and memorization with (almost) no over- parameterization. Advances in Neural Information Processing Systems, 33:9007-9016, 2020.
[11] SF de Rezende, M Göös, and R Robere. Guest column: Proofs, circuits, and communication. ACM SIGACT News, 53(1):59-B8) 82,99882224 2022.
[12] Charles Dugas, Yoshua Bengio, François Bélisle, Claude Nadeau, and René Garcia. Incor- porating second-order functional knowledge for better option pricing. Advances in neural information processing systems, 13, 2000.
[13] Ronen Eldan and Ohad Shamir. The power of depth for feedforward neural networks. In Conference on learning theory, pages 907-940. PMLR, 2016.
[14] Ankit Garg, Mika Göös, Pritish Kamath, and Dmitry Sokolov. Monotone circuit lower bounds from resolution. In Proceedings of the 50th Anmual ACM SIGACT Symposium on Theory of Computing. pages 902-911, 2018.
[15] Maya Gupta, Andrew Cotter, Jan Pfeifer, Konstantin Voevodski, Kevin Canini, Alexander Mangylov, Wojeiech Moczydlowski, and Alexander Van Esbroeck. Monotonic calibrated interpolated look-up tables. The Journal of Machine Learning Research, 17(1):37903383) 2016.
[16] András Hajnal, Wolfgang Maass, Pavel Pudlák, Mario Szegedy, and György Turán. Threshold circuits bounded depth. Journal of Computer and System Sciences, (662)::129115) 1993.
[17] Peter Hall and Li-Shan Huang. Nonparametric kernel regression subject to monotonicity con- straints. The Annals of Statistics, 29(3):62 647, 2001.
[18) Danny Harnik and Ran Raz. Higher lower bounds monotone size. In Proceedings of the thirty-second annual ACM symposium on Theory of computing, pages 378-387, 2000.
[19] Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural networks, 2(5):359-366, 1989.
[20] Pavel Hrubeš and Pavel Pudlák. note on monotone real circuits. Inform. Process. Lett., 131:15-19, 2018.
[21] Mark Jerrum and Mare Snir. Some exact complexity results for straight-line computations over semirings. Assoc. Comput. Mach., 29(3)87748877 1982.
[22] Adam Tauman Kalai and Ravi Sastry. The isotron algorithm: High-dimensional isotonic re- gression. In COLT 2009 The 22nd Conference Learning Theory, Montreal, Quebec, Canada, 2009.
[23] Jon Kleinberg and Eva Tardos. Algorithm design. Pearson Education India, 2006.
[24] Rasmus Kyng, Anup Rao, and Sushant Sachdeva. Fast, provable algorithms for isotonic re-
gression in all I,-norms. Advances neural information processing systems, 28. 2015.
[25] Xingchao Liu, Xing Han, Na Zhang, and Qiang Liu. Certified monotonic neural networks. Advances in Neural Information Processing Systems, 33:15427-15438, 2020.

---

[26]
Mahdi Milani Fard, Kevin Canini, Andrew Cotter, Jan Pfeifer, and Maya Gupta. Fast and flexible monotonic functions with ensembles of lattices. Advances in neural information pro- cessing systems, 29, 2016.
[27] Ian Parberry. Circuit complexity and neural networks. MIT press, 1994.
[28]
Pavel Pudlák. Lower bounds for resolution and cutting plane proofs and monotone computa- tions. The Journal of Symbolic Logic, 22(3):981-99)) 1997.
[29] Shashank Rajput, Kartik Sreenivasan, Dimitris Papailiopoulos, and Amin Karbasi. An expo- nential improvement on the memorization capacity of deep threshold networks. Advances in Neural Information Processing Systems, 34, 2021.
[30] Ran Raz and Pierre McKenzie. Separation of the monotone NC hierarchy. In Proceedings 38th Annual Symposium on Foundations of Computer Science, pages 234-243, IEEE, 1997.
[31] Alexander A Razborov. Lower bounds monotone complexity of the logical permanent. Mathematical Notes of the Academy of Sciences of the USSR, 37(6):485 493, 1985.
[32] Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning; From theory to algorithms. Cambridge university press, 2014.
[33] John S Shawe-Tayles Taylor, Martin HG Anthony, and Walter Kern. Classes of feedforward neural networks and their circuit complexity. Neural networks, 5(6):971-977, 1992.
[34] Amir Shpilka and Amir Yehudayoff. Arithmetic circuits: survey of recent results and open questions. Now Publishers Inc, 2010.
[35] Joseph Sill. Monotonic networks. Advances in neural information processing systems, 10, 1997.
[36] Michael Sipser. Introduction to the theory of computation. ACM Sigact News, 27(1):27-29, 1996.
[37] Kai- Yeung Siu and Jehoshua Bruck. On the power of threshold circuits with small weights. SIAM Journal Discrete Mathematics, 4(3):423-44 435, 1991.
[38] Aishwarya Sivaraman, Golnoosh Farnadi, Todd Millstein, and Guy Van den Broeck. Counterexample-guidee learning of monotonic neural networks. Advances in Neural Infor- mation Processing Systems, 33:11936-11948 2020.
[39] Gal Vardi, Daniel Reichman, Toniann Pitassi, and Ohad Shamir. Size and depth separation in approximating benign functions with neural networks. In Conference on Learning Theory, pages 4195-4223. PMLR, 2021.
[40] Roman Vershynin. Memory capacity of neural networks with threshold and rectified linear unit activations. SIAM Journal on Mathematics of Data Science, 1003 2020.
[41] Karin Willemans and Paul Dierckx. Smoothing scattered data with monotone powell-sabin spline surface. Numerical Algorithums, 12(1):215-231, 1996.
[42] Dmitry Yarotsky. Error bounds for approximations with deep ReLU networks. Neural Net- works, 94:103-114 2017.
[43] Amir Ychudayoff. Separating monotone VP and VNP. In Proceedings of the 51st Annual ACM SIGACT' Symposium on Theory of Computing, pages 425-429, 2019.
[44] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Under- standing deep learning (still) requires rethinking generalization. Communications of the ACM, 6473):107-115, 2021.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
12

---

(a) Did you state the full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you re using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "RmE8svGi4XX", "reviewer": "Reviewer_CbVM", "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. ", "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. ", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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. \n\nHowever, 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. \n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "2kvDTAJPaA", "reviewer": "Reviewer_uFX9", "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). ", "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. \n\n- 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.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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. \n\n- 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. \n\n- 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.  \n\n- 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 \n\n[1] G. Beliakov, Shape preserving approximation using least squares splines, Approximation Theory Appl., 16 (2000), pp. 80–98.\n[2] P. Costantini and C. Manni, A local shape-preserving interpolation scheme for scattered data, Comput. Aided Geom. Des., 16 (1999), pp. 385–405.\n[3] P. Hall and L. Huang, Nonparametric kernel regression subject to monotonicity constraints, Ann. Stat., 29 (2001), pp. 624–647.\n[4] K. Willemans and P. Dierckx, Smoothing scattered data with a monotone Powell-Sabin spline surface, Numer. Algorithms, 12 (1996), pp. 215–232.\n \nWRITING \nThe 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.)\n\np1, line 25: \"modeling monotonic relationship\" should probably read \"modeling the monotonic relationship\"\np4, line 134: \"requires much larger size\" should read \"requires a much larger size\"\np4, line 154: \"may result with negative\" should read \"may result in negative\"\np4, 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.\"\np5, line 175: \"applies for arbitrary dimension larger than 1\" should read \"applies to arbitrary dimensions larger than 1\"\np5, line 180: \"One difference of our\" should read \"One difference between our\"\np5, line 185: \"require super polynomial\" should read \"require a super polynomial\" \np5, line 189: \"function m, that requires\" should read \"function m, which requires\"\np5, line 206: \"Each layer is composed from\" sounds better as \"Each layer is composed of\"\np6, line 229: \"positive is indeed without\" should be \"positive holds without\"\np9, line 342: \"can can\" should be \"can\" \np9, line 344: \"each gate by a\" sounds better as \"each gate with a\"\np9, line 361: \"theses copies\" should read \"these copies\"", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "0QLCnqjAE91", "reviewer": "Reviewer_G2N7", "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. \n\nFirstly, 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. \n\nThe 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.\n", "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", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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. \nThe paper is well written, and references are adequate.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept