Monotone and Separable Set Functions: Characterizations and Neural Models
Authors: SOUTRIK SARANGI
Yonatan Sverdlov
Nadav Dym
Abir De
Venue: NeurIPS 2025 poster ()
Keywords: DeepSets
Monotone functions
Data Retrieval
separability
Primary area: other
TL;DR: We build a multi-set function that is monotone and separable

Abstract: Motivated by applications for set containment problems, we consider the following
fundamental problem: can we design set-to-vector functions so that the natural
partial order on sets is preserved, namely $S \subseteq T$ if and only if $F (S) \leq F (T )$.
We call functions satisfying this property Monotone and Separating (MAS) set
functions. We establish lower and upper bounds for the vector dimension necessary
to obtain MAS functions, as a function of the cardinality of the multisets and
the underlying ground set. In the important case of an infinite ground set, we
show that MAS functions do not exist, but provide a model called MASNET
which provably enjoys a relaxed MAS property we name “weakly MAS” and
is stable in the sense of Holder continuity. We also show that MAS functions
can be used to construct universal models that are monotone by construction
and can approximate all monotone set functions. Experimentally, we consider
a variety of set containment tasks. The experiments show the benefit of using
our MASNET model, in comparison with standard set models which do not
incorporate set containment as an inductive bias.

Monotone and Separable Set Functions: Characterizations and Neural Models
Soutrik Sarangi" IIT Bombay
Yonatan Sverdloy* Technion
Nadav Dym Technion
Abir De IIT Bombay
Abstract
Motivated by applications for set containment problems, we consider the following fundamental problem: can we design set-to-vector functions so that the natural partial order on sets is preserved, namely S S T if and only if F(S) S F(T). We call functions satisfying this property Monotone and Separating (MAS) set functions. We establish lower and upper bounds for the vector dimension necessary to obtain MAS functions, as a function of the cardinality the underlying ground set. In the important case of an infinite ground set, we show that MAS functions do not exist, but provide a model called MASNET which provably enjoys relaxed MAS property name "weakly MAS" and is stable in the sense of Holder continuity. We also show that MAS functions be used to construct universal models that monotone by construction and can approximate all monotone set functions. Experimentally. we consider variety of set containment tasks. The experiments show the benefit of using our MASNET model, in comparison with standard set models which do not inductive bias. Our implementation available
the multisets and
incorporate set containment in https::/// //t:://ggttutt github. com/
Introduction
A multiset ff11.-- ......... Fn is unordered collection of vectors, where order does not matter (like sets) and repetitions are allowed (unlike sets). In recent years, there has been increased interest in neural networks that map multisets to vectors, with applications for physical simulations [1], processing point clouds [2], and graph neural networks [3]. Another important application multiset-to- tociisstttt--ettor maps set-containment search [4, 5, 6]. Here the goal is check whether given multiset S is (approximately) subset of T, and this is often carried out by learning a multiset-to-vectt veetor mapping F, and then checking whether F(S) < F(T) (element-wiss) in which case, deduces that S is subset of T. In this paper, we look into this problem from a theoretical perspective.
Monotone and Separable functions We begin our analysis with some definitions: we say that a function F mapping sets to vectors is monotone if S C T C V implies that F(S) S FFT). and we will say that F is separable if F(S) < F(T) implies that S C T. When F is simultaneously monotone and separable, we call a MAS function. When
a MAS function, we can safely test whether F(S)= < (TT), and this will be fully equivalent to checking whether 5 C T.
Motivation for MAS functions It is natural ask why we're interested in functions that MAS instead of just being monotone or just separable. For this, we begin with a couple of real-life applications based on the set-containment task: (I) In recommendation system design, one problem is to recommend item having a particular set of features, S. Here, we represent each item as a set of corresponding features T, and the problem Text entailment where we are given a small query sentence y nd the goal is to find the set of corpus items e from a large corpus C, where q - e entails q. Here, q and are typically represented as sets of contextual embeddings (S for and T'' for e) and the entailment problem can be cast as the problem of checking if S T.
find all sets T such that approximately, S C T. (II
"Soutrik and Yonatan contributed equally. Contact emails of the authors: soutriksarangii400maaa y yonatans@campus technion ac. il, nadavdymttechm ac, il, abirêcse. ai,
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

In a neural network setting, such problems require us to design function F such that the "order" between F(S) and F(T) can serve as a boolean test for whether S a subset of T. For this, F needs to satisfy two conditions: (A) F(S) V F(T) implies S S T (B) F(S) I F(T) implies S g T. Here, we like to emphasize that, for high accuracy, needs to satisfy both conditions A and B as above. Monotone functions satisfy condition (B) without necessarily satisfying condition (A). As result, we predict S C T based on F(S) S F(T) when I' is monotone but not separable, will give large number of false positives. Similarly, if F is separable but not monotone, then F' satisfies condition (A) without satisfying condition (B). Thus, using such for checking S S ' results in a large number of false negatives. Hence, both monotonicity and separability are necessary to develop an accurate test for set-containment
Related works Monotone set functions have been widely studied in the theory of capacities [7],
fuzzy measures [8. 9], game theory and economics [10], combinatorial auctions [11, 12, 13), and learning theory [14, 15, 16, 17, 18, 19). These works primarily focus on scalar-valued set functions or vector-valued models without structural order constraints.
To the best of our knowledge, jointly monotone and separable multiset (MAS) functions, i.c., multiset-to- vector maps that preserve the partial order induced by multiset containment have not been previously formalized. Classical results on partially ordered sets, such as order dimension [20], provide relevant mathematical background but do not address learnable or differentiable constructions. Our goal is to characterize the existence of MAS functions and develop models that satisfy MAS constraints by construction for multiset containment tasks.
This work also related to injective multiset representations. Foundational results on permutation- invariant functions include [21, with subsequent work analyzing the latent dimension required for injectivity [22, 23, 24] and proposing differentiable injective or bi-Lipschitz embeddings [25, 26, 27]. In this work, we study MAS functions, which impose strictly stronger constraints than injectivity (see Subsection 2.1).
An additional goal of this work is stability: in most learning scenarios, we are looking for S, which only approximately a subset of T. Accordingly, we would like to design functions F that are not only MAS but also stable, in the sense that when S is approximately a subset of T, then F(S) is approximately dominated by F(T).
Summary of our goal In summary, in this work, we aim to characterize (MAS) set functions that output miite-dimensional set representations and subsequently design neural networks for such functions. At a high level, we seek to address the following questions: (1) What are the conditions for existence of finite dimensional MAS functions? (2) What are the permissible relaxations to monotonicity and separability if the existential conditions identified in (1) are not satisfied? (3) What the possible neural architectures for these functions? (4) Are these functions stable? We expect that the design of trainable models with built-in guarantees of monotonicity, separability, and stability will significantly enhance the inductive bias for set containment applications.
1.1 Main Results
We address the goal specified in the previous subsection by providing detailed characterization and neural architecture for monotone and separable set functions. Our main results are as follows:
Existential characterization of MAS functions Our first objective is to determine whether is possible to obtain a MAS set function with finite output dimension m. We begin our analysis in the case where set elements are assumed to be taken from a finite ground set V. and show that in this case MAS function exists if, and only if, m [V]. Next, we add the assumption that the cardinality of the input multisets is bounded by k, and provide lower and upper bounds for m in this case. When the ground set is infinite, we show that MAS set functions do not exist.
Weakly MAS functions In most applications, the ground set is V = VRD, and our analysis shows that in this case, MAS functions do not exist in general. To address this, we introduce the notion of weakly MAS functions by extending the set functions to parametric set functions F(S, w), where w is a parameter. Weakly MAS functions requires that (i) F(;, w) is monotone, for all w, and (ii) for any S & T. there exists at least one w E W such that F(,, w) separates and T. We explain how, by choosing suitable activations, it is possible to construct simple deep sets [21] models which are weakly MAS, and name the resulting model MASNET.
Stability We define the notion of stability as discussed above, separability notions are Boolean and fail to capture graded distance. We would like to guarantce that F(T) is "almost" larger than

---

F(S) when S is 'almost' a subset of T. To address this, we propose novel asymmetric set distance and present a Holder separability condition [28] which ensures stability in terms of this asymmetric distance.
Monotone Functions
Finally, we show that MAS functions can be used to provide universal models for computing set-to-vector functions. Thus, MAS functions may be a useful concept also outside of the set containment setting.
Experiments We provide number of experiments showing that for set containment problems, using our weakly MAS model leads to stronger results in comparison with standard multiset models like DeepSets and SelTransformer, which do not incorporate MAS considerations as an inductive bias.
Summary of contributions Our main contributions in this paper are: (1) We introduce the novel notion of monotone and separating (MAS) multiset functions. (2) We discuss lower and upper bounds for the embedding dimension for MAS functions, and suggest a model MASNET, which is weakly MAS. (3) We show the stability of MASNET. (4) Experimentally, we prove the effectiveness of MASNET for set containment tasks.
2 Existential characterization of MAS functions
We begin by stating the notation we will use for our paper.
Notation We denote by V to be the ground set and <<oo to be the collections of all multisets
from V with finite cardinality = fx1.-.. .x where 2; E V. We denote the space of all multisets with at most k elements by (V). We use [d] to denote the set (1.... .d). Given two vectors
V. U.UC E Rd, we say S u if ufi] S u|i] for all i [d]. Also, for an element v E V and multiset
E P (Vo)(V) we use cs(v) to denote the number times v occurs in S. We say S C T cs(v) S (v) for all v E V.
Proofs All proof' for the results stated in the paper provided in Appendix B.
In this section, our goal is to understand when an MAS function F Ps*(V) + Rm or F Pex (V) -> IIm exists, and if it does, what is the smallest m for which such mapping exists. We denote this minimal dimension as m (V, k)), and m (V, oo), respectively.
2.1 Prologue: Relation to injectivity Our inquiry is related to the notion of injective multiset functions, as every MAS function F is, in particular, injective. Indeed, suppose for two sets S, we have F(S)= = F()). Then, we have both F(S) < FT)) and F(T) S F(S). Hence, we have both S T and T S by separability, which implies S = T. Thus, injectivity follows from separability.
Injective multiset functions f (V) + R" are attainable even for 1, providing that V is finite or even infinite [21. 3, 22, 25]. As we will see, attaining the strong condition of MAS multiset functions requires high dimension, and in some cases (infinite V\, it does not even exist. This can be seen even in the following very simple example:
Example 1. Assume the ground set consists of only two elements V = =0, 1]. and we only look for multisets of cardinality I k = 1. In this case, there are only three multisets in the space P&i (V): the empty set, S = {0}, and T = {1}. As discussed previously. there exists a multiset function F: PPPs (V) -> R which is injective. However, such function can be separated. This is because neither S nor is a subset of the other. However, because real numbers are totally ordered, we have either F(S) < F(T) or F(T)= F(S), violating the separability condition.
We note that the monotonicity can be satisfied bu using functions of the form F(S) = Exes fx) non-negative f. Thus, achieving separation is harder than achieving monotonicity.
The key reason for the non-existence of a scalar MAS set function is that multisets (or sets) are not totally ordered, but scalars are. However, this issue does not arise for multidimensional set functions, where vectors, similar to sets, are partially ordered. So, when mapping to vectors, when and how can MAS functions be constructed? We will now discuss this.
2.2 Existence of MAS functions: finite ground set, unbounded cardinality
We study MAS functions F: (V) + R where input multisets may have an arbitrarily large finite cardinality, and the ground set is finite [V| = n. In this case, we can show that the smallest possible dimension m² (V, V.& k) of a MAS function is exactly
3

---

Theorem 1 (Dimension of MAS Function). For a finite ground set V of size a, there exists MAS function F <e + R.. In addition, any MAS function must have a dimension of at least n. In other words, m² m''V, (V, =
Proof Sketch The construction of a monotone embedding with n = [V] simply uses one-hot encoding, Namely, we identify V with [n]]. For every S E Po (V), we define
F(S) = EES
E R.
where e, E IR" is the vector with e, = 1 and c, = for all j + s. It's clear F satisfies all conditions. For the second part, assume have an embedding of dimension m. for every output dimension i E [m]] there is a "maximal singleton element" of E such that P((i))e 2 F(( Ve E V. The value of the set function F applied to T {vi ..., " will dominate any singleton, due to the monotonicity of F. However, if m < [V], then we can select a u E V \ T and then F(u))) & F(T). which contradicts separability.
2.3 Existence of MAS functions: finite ground set, finite cardinality
We now consider the case where the ground set V is finite, as before, but now the multisets have bounded cardinality < [V] Indeed, in many practical applications. input multiset cardinality is much smaller than VV., even when [V] is large. In this setting, we show that we can get lower embedding dimension m than in Theorem
In fact, we show the minimal output dimension m of a MAS function F: Ps& (V) - R' can scale logarithmically with the size of the ground set [V]. However, this comes at the price of an exponential dependence on k:
Theorem 2 (Upper Bound on m' (V, k)). Let k < n. be natural numbers, and let V be ground set with V = n. Then there exists a MAS function F PPsx - R with embedding dimension m = (A= + log(n).
Proof sketch We construct the MAS function by taking the one-hot embedding F: PVx(V) - R from (I), and then applying m random projections defined by vectors I2 with non-negative entries. The non-negativity ensures monotonicity, and we prove that for the stated value of m, the probability of achieving& a MAS function using this procedure is strictly positive.
The theorem shows that m (V, k) < (k + 2)*+² log(n). We now give two lower bounds on the embedding dimension: we show that m must depend least linearly on k, and at least double logarithmically on n:
Theorem 3 (Lower bounds on m² (V,k)) Let k: 2 2 and n be natural numbers, and let V be a
ground set with [V| n. Then the smallest possible dimension m (V, k) of a MAS function satisfied m" (V, k) 2 log2 (logs ni) Moreover, if k S - then m (V,k) k) 2 2k
Sketch To obtain the first lower bound, we consider the sequence of singleton-set embeddings M == (F(()),, FF.,,,)),.((n)). By the Erdös-Szekers theorem [29], every scalar sequence with n elements has a monotone subsequence of length n Applying this recursively to vectors of length m gets monotone subsequence in all m coordinates of the vector, of length ~ nzm. If this subsequence is of length > then we will have three distinct elements U1 02 03 E V such that F((v))) < F((va) Hij < F((aa or F((va)[ii] < F( < (((v))) Vi E
[m] Monotonicity implies that Fi is dominated by F((ui, (i]) for all E [m]. thus
contradicting separability. It follows that MAS existence can only happen when n < 2, which leads to the double logarithmic lower bound.
For the lower bound in terms of k; the argument is similar to the proof of Theorem 1, where we select
a "maximal singleton element" of for every dimension i E [m]]. Since < [ - 1, we can find elements {u1, ]2 disjoint from the collection U (u, ). and WLOG (((w))){b 2 ({(2u)))( for at least half of the indices in [m]. We then construct S = {ug) ) and T to be union of uu and all the of for all dimensions i, where F( I F( [[.] Then monotonicity implies F(S) S FTT). but S @ T. This implies k < [T] 2.4 Non-existence of MAS functions: for infinite ground set
m/2, as otherwise separability of F in P*x is violated.
For most practical applications, we deal with infinite (often uncountable) ground sets, for example V = R.d. Thus, we would like to analyze whether MAS functions exists when [V| = xc. The answer
to this question is negative:

---

Corollary 4. Given ground state V with [V] = oo, and k 2 2, there does not exist MAS function F: (V) R for any finite m E N.
This corollary is a simple consequence of the result in Theorem that the embedding dimension cannot be larger than log log [V] when V is finite. We note that this result makes the minimal assumption k: 2 2. In Appendix we show this assumption necessary, and that the degenerate case l = 1 there MAS function F (Vi(V) - R for V = [-
Summary In this section, we provided lower and upper bounds for the smallest value m² (V, for which an MAS function F: PPxx(M (V) - I exists. Our results are summarized in Table 1. We note that some of these results require weak assumptions, which are stated in the theorems but not in the table.
Ground set size:
V
n < 00
V n
00
Input multiset size 1: $50
== 00
k =
k 2
m" (V, < min n, (k + 2)x log(n)). m= (V"(Vk) Z max (2k, log, logs m
m² (V, =
m² (V, k) =
Not possible
Table I: This table summarizes the lower and upper bounds for the smallest value mn" mV(V k) for which an MAS function F; :PPs (V) ) Im exists, where is maximal set cardinality and n denotes the cardinality of the ground set V.
3 Relaxations of MAS functions Our definitions far did not address differential parameterized set functions F(S, w), which are the natural object of interest for set learning applications. One natural way to address this could be to require that there exists w such that F(,, w) is MAS function; however, since our theoretical results show that MAS functions do not exist when [V| co, this requirement is too restrictive. Instead, we retain monotonicity as hard constraint for every parameter w W, while treating separability as an existential condition over the parameter space.
3.1 The notion of weakly MAS functions
Formally, given a ground set V, and probability space (W,B, ()), we consider parametric set functions F Poo (V) W + Ih"", where F(S, o) is measurable for all S. We then define weakly
MAS functions as:
Definition 5 (weakly MAS function). The set function F Pcoc x W - R is weakly MAS function if the following two conditions are satisfied;
(I) Pointwise monotonicity For any w E W and S C T. we have that F(S, w) < F(T. w). (2) Weak separability S Z T, then there exists w E W such that F(S; w) > F(T;w).
Which condition, monotonicity or separability, should be relaxed? In our definition, we relax the separability requirement so that different multiset pairs can be separated by different parameters, while we maintain strict requirements of pointwise monotonicity. This because, as discussed in Example 1, constructing monotone set functions is straightforward, even in one dimension. In contrast, separability is a much stronger and more difficult condition to satisfy. This a key reason why MAS functions do not exist when [V] xc. Indeed, as shown in Appendix B, there can be no continuous separable set function even without the monotonicity assumption when the ground set is V IR D. Therefore, separability is the natural condition for relaxation. Moreover, monotonicity remains a useful and often necessary constraint in many applications.
Are scalar deep sets weakly MAS? Equipped with the new notion of weakly MAS functions, we ask the question of how to construct such class of functions. As first step to achieve this goal, look into simple instance of DeepSets [21]. DeepSets defines a set function by applying an 'inner' MLP M, each set element, summing the result, and then applying consider the case where M, is a shallow MIP M2 (x) = of Ar + b) which gives us models of the form
'outer' MLP M2. We
F(S; b))
M2 (Ax + b))
To ensure monotonicity for every parameter choice b, we will require that M2 is a monotone vector-to-vectt function, and the activation is non-negative. While these choices automatically ensure monotonicity, they may not lead to weak MAS functions as for many activations there will be no separation:
Proposition 6. the deep set model in (2) is implemented with a vector-to- monotonously increasing function M2 and non-negative activation o, then F( (A, b)) is monotone for every
5

---

Tanh
ReLU
TRI
Hat Function
F not monotone
Montone, MAS with 2 layers Monotone, MAS with layer Monotone, MAS with1 layer
Figure 2: Using multiset model in (2) with activations which are not always non-negative, like = Tanh will not be monotone. ReLU will be monotone, but to be weakly MAS, two layers are required. TRI and more general hat functions are weakly MAS even with a single layer.
(A.b). If in addition a is monotone (increasing or decreasing), then there exists S g T with F(S; (A. S FT;; (A, for all A, b.
Proof idea The monotonicity is rather straightforward. To prove lack of separation when o is monotone, choose + y, (x + y), S [=}, T fz. y). and then Az + b is the average of Ax + and Ay + b, which can be used to show that (T; (A, 2 F (S; for all A, b.
Are Set Transformers weakly MAS? Now we ask the quedtion Set Transformers [30] are weakly MAS. We notice in the following that Set Transformers not even monotone in the following re- sult. For this, we consider Set Transformer with sum-pooling, namely F(S; We, WK, Wv) Explicity, this is defined for give multiset X {x1,"* Xn) by first defining query, key, values per-point: qi = Wox;, k; = WxX,, V; = Wvx;, and then taking 4: ky
a weighted average, defined by weights: aij = Σ, E to obtain a permutation-invan -nnvaaiiinnnnnnii function
F(S; WQ. WK. Wv) Ei, Vs,ys
Proposition 7. Let V Ed and let F (V) + RD be Set Transformer defined by F(S; Wo. Wx. Wv) == SumPool(Atm(()) Then F is not a point-wise monotone function.
Proof Idea We consider full rank matrices We WK and any non-zero Wv. We choose
X1 E Id such that V1 Wyx, * O, and consider the sets S {x1}. T {xx, 0z) Then, F(S; Wo, WK, Wv) = V1 and F(T; Wo, WK, Wv) = (01.1 + +012) Note that, 01,1 + + > and thus, for any negative vi [i], we have F(T; Wo. Q: WK. Wr) F(S; Wx. Wy and thus, monotonicity violated.
Thus, unlike Deep Sets, it's not obvious how to make Set Transformers monotone, let alone weakly separable. Thus, the following sections, we shall focus on obtaining weakly-MAS functions from DeepSet-like models only.
3.2 The Hat activation class
Note that most commonly used non-negative activation functions, such as ReLU or sigmoid, are monotonically non-decreasing and therefore, from Proposition 6, using them above will fail weak separability. Here, we consider a novel class of activation functions we call 'Hat Activations", which will all make F' in Eq. (2) weakly MAS.
Definition (The Hat activation function). We call a function a : R + R a hat activation if it is (a) and (d) continuous.
non-negative (b) compactly supported (c) not identically Examples of hat functions
the third and fourth functions in Figure 2. When is hat function, Equation (2) is weakly MAS, even when the output of F' is taken to be scalar. For this result, we will need to require that Ma is strictly monotone. This be handled by simply setting M2 to be the identity.
Proposition 9. If M2 is strictly monotone increasing, and is a hat activation function, then M2 M2 (a x +-++0 b)) is weakly MAS function.
Proof idea If S not a subset of T, there is an element whose multiplicity in S is larger than its multiplicity in T. We can then choose b so that is in the support of ( + b) but the elements of are not.
3.3 Slightly larger ReLU networks
So far, we have considered simple models as in (2) which apply a single linear layer before applying activation and summation. In this case, that ReLU and other activations do not create weakly

---

MAS functions, and defined the notion of hat activations, which are weakly MAS functions. But what happens if we use ReLU activations but allow deeper networks?
We can use our previous analysis to show that very small ReLU networks with two lay- can already be MAS functions. To this, we consider candidate from the hat function class, namely the TRI function from Figure 2, and observe that: TRI(r) ReLU (ReLU(2x)++ + (eL - 2) ReLUU4z- 2)) We use this to deduce the following result:
Proposition 10. Given V C R4, consider affine transformations A R + R IR3 R. Thus, here A2(t) == A2t b2 and A1(z) = aj 2 bb, where A2 E Rxd by E R Ra E are the respective parameters. Then, the set functions of the form
RR,
bI E
F (V) + RR, AI, = M2 (Exes ReLU A ReLU A2(1))
are weakly MAS functions.
Our results so far are summarized in Figure 2. If a is not non-negative function, then F will not be monotone. We can attain weakly MAS functions with a two-layer ReLU network, or with a one-layer network with hat activations.
3.4 Asymmetric distance induced Holder separability
Why weak separability is not sufficient While weak separability is key relaxation for weakly MAS functions (Definition 5), it has two key limitations: (1) Separation should ideally hold over a not just a single point w: (2) treats separability as a boolean condition, ignoring approximate containment. We would like to guarantee that if S is almost subset of 7' then F(S, w) will be close dominated by F(T, w.) This motivates us create an asymmetric (pseudo) metric to quantify the size of set difference and create stronger notions of separability based on that.
non-negligible subset of W, not
Asymmetric set distance For ground set V C R2 and two sets S, E (V) such that [S] z (Ti. We define the asymmetric distance from to T as the Earth Mover Distance (EMD) between S and the subset of T that is closest to S with the same cardinality as S.
A(S,T)
min EMD(S,T")
-'C7:[S]=1T"
( captures graded set containment: if 5 g T. but is "very close" to a subset of T in EMD = S C T. Based on A, we propose
metric, then ASS, is small. Moreover, AS,, T) 0 newer separability notion for parametric functions.
Lower Hölder separability of set functions Davidson and Dym [28] introduced Hölder continuity through expectation over parameters. Unlike their symmetric EMD, we define Hölder separability using the asymmetric distance A(4).
Definition 11 (Lower Hölder separability). Let V S. Rd be the ground set and (W, μ)) be probability space, and a constani X >> O. A purametric set function F( PVx(V) + Rm with w ~ p(-)) is X lower Hölder separable if there exists e >> such that:
Ems [I::F( w) [[;:w)]] 2 A(S,T)A, for all S,T (V)
(5)
3.5 Hölder separable Set functions
Hölder separability using Hat activation Proposition 9 shows how to construct weakly MAS functions using Hat activations. We now show that these constructions are also lower Hölder, under additional weak assumptions on the hat functions and M2:
Theorem 12 (F lower Hölder). Let V R.d be a compact set, and a Hat activation function which is piecewise continuously differentiable supported in some interval (m,,,,,, and satisfying da
> 0. Let M2 : TK - R be a lower Lipschitz function. Consider the function F(S: (a,b,)) M₂ Eres a(" (aTT)))), where the multisets S come from PVv(V), and 1)),e c ~ Unif((0,2) 21). Then, F( (a, b,c) is Monotone Hölder a U ~ Unif([- (,,
the condition: lim, lim dt
separable with exponent x = 2.
Probability of successful separation Given S,T S V, we can consider [F(S; (a, b, c)) F(T: (a, b,c)] to be real-valued non-negative random variable, where the randomness is over the parameter space (a, b, c) E W Rd x RR x IR equipped with probability measure. The above result on lower Hölder stability gives us lower bound on the probability of a parameter tuple (a, b, c) separating two non-subsets S, proportional to the set distance A(S,T). Moreover, the
7

---

functions we have considered so far are scalar-valued set functions. By considering independent copies of the parameters across multiple dimensions, we can increase the probability of separation. since F(S), F(T) are not separated iff [i) S (()) across each embedding dimension i. We
formalize the above observations as follows:
Theorem 13 (Probability bounds on separation). Les V C C and a be as in Theorem 12, and let A E I b E RT , E 2 whose m columns (respectively entries) are drawn independently from the distribution on aj. Cg. described in Theorem 12, and consider the function
F,S; b, c) = Enes (c-1 @ (Ax + -)) Then there exists C' > 0, so that for all S P & F(T)) S (1 (1-C (1-)))
(6)
In Equation (6) c- stands for the elementwise inverse and @ stands for elementwise multiplication.
Note that the probability of failed separation goes to zero exponentially as m increases, and also becomes smaller as A(S, T) increases. This supports the idea that a larger measure of parameters separates sets with larger asymmetric distance and that separability becomes easier with larger embedding dimensions (which we saw previously in the existential results)
Hölder separable set functions using ReLU As seen in Proposition 10, can construct weakly MAS functions with a two layer neural network with ReLU activation. Our proof used that two layer ReLU networks can basically "simulate" Hat function. Under the light of the above results on Hölder separability, one can argue that two-layer ReLU networks would also have such guarantees. Also, we show in Appendix B that under certain structure the ground set V (for example, V being a hypersphere), even with one layer ReLU networks, functions of the form in Equation (2) will also have Lower Hölder separability guarantees.
Upper Lipschitz bounds In Appendix. B we complement our results on lower Holder stability by showing that the construction in Theorem 13 is also upper Lipschitz in an appropriate sense.
3.6 Monotone Universality and the role of M2
Besides set containment-base applications, there are other interesting scenarios where one would like construct monotone multiset-to-vecto functions. The following theorem shows that finite ground sets, the combination of MAS function and a universal monotone vector-to-vector (such as [31]) can approximate all monotone multiset-to-vectt functions.
Theorem 14 (Universality). Let V be a finite ground state, and let F; P&&k (V) R be MAS function. Then for every multiset-to-ved vector monotone function f Pev(V) + R', there exists
vector-to-vector monotone function M Rm - E such that F(S) = M o f(S).
4 MASNET: Neural Modeling of MAS functions
Now, our goal is to leverage our theoretical analysis to design neural network- multiset-to-vectte models that preserve monotonicity and weak separability. Motivated by the formulation in DeepSets and our analysis so far, we wish to design neural set functions of the form:
MASNET(S) Ma, (Eees (x)))
In our analysis, we required Ma, to be a monotone vector-to-vector function. In most of our experiments, enforce this simply by choosing M2(x)) x, but this can also be enforced by using monotone activations and non-negative parameters.
To enforce weakly MAS in Equation (7)r results from Prop. 9 and Theorem 12 suggests using a Hat activation a. In our experiment, we do it by not choosing to be a specific hat activation, but rather the parametric form:
MASNET-Ha.
+ ReL.U (#-(at2 (U->)-
(z(a+-y9) 7-11->)
(8) For all a, , 0, and E 1). oa.9.7 is a hat function (Definition 8) with support [a, a + 3 and peak at a + m3. Examples include the third and fourth functions in Figure 2. Applying this to an m-dimensional output with independent at 3, 7 per dimension yields 3m parameters total.
Ga,3,y (x) ReLU
ReLU
7-3
MASNET with ReLU Motivated by our theoretical results from Theorem 10 of 2-Layer ReLU networks being weakly MAS and from our discussion of ReLU networks being Hölder separable (under appropriate assumptions) in Section 3.5, we propose use ReLU in MASNET, which case Ma. will have to be a network with at least layers to ensure weakly MAS as in Theorem 10. This gives one more way to design MASNET and we refer to this option as MASNET-ReLL
8

---

Definition 8 establishes a general hat function class extending beyond the piecewise linear functions as in (8). We present MASNET-INT in Appendix C. which achieves universal approximation of the Hat class by modeling its derivative via neural networks and approximating the integral. Additionally, using the specific hat activation TRI (Figure 2) as a yields an alternative formulation called MASNET-TRI.
Other variants of MASNET
Which MASNET to choose and when? We have given multiple recipes of MASNET in the above discussion, and the question arises: which one to choose? We show via our experiments: For parametee--constrained scenarios requiring single-layer Ma, networks, MASNET-Hat provides optimal separability (both theoretically and empirically). For deeper Mg, 2 2 layers), both MAS- NET-ReLU and Hat-based variants perform similarly, with MASNET-ReLU often providing more stable training and better performance overall.
5 Experiments
We evaluate the MASNET variants (Section 4) on synthetic, text and point-cloud datasets character- ize monotonicity and separability. Specifically, we focus on (exact and approximate) set containment. Given sets S and T. with binary label ySS, T) E {0, indicating (exact or approximate) set containment, we evaluate how accurately MASNET predicts y(S,T).
5.1 Set Containment
We perform experiments on synthetically generated dataset, four text datasets, and one image dataset. In each case, we split the dataset into 5:2:2 train, test, and dev folds. We minimize the following fixed-margin hinge loss that enforces vector dominance, to train the parameters of MASNET.
Σ (())) S,T
T)) min [F(S)[] - F(T) + 41 + y(S, T) max [F(S) F(T) + 51+ (9)
(E(m)
IE m
Analysis on synthetic datasets To generate our
[S]
17
DS
ST
M-ReLU
M-Hat
1
0.98
0.98
0.99
0.99
synthetic dataset, we first sample target set T C Rd
1
0.59
0.99
0.99
where each element x T is drawn from N I). i..d. Given T, we compute S with a fixed size |8|
10
30
0.89
0.80
1.00
1.00
10 100
0.54
0.57
0.98
0.99
Table 3: Accuracy on synthetic data
as follows. We first obtain S with positive labels
v(S 7) 1 by drawing a subset from T, uniformly at random, without replacement. To generate S with y S, 7) = O, we sample s from (0, I) independently. We chose d and the set embeddings have 256 dimensions, the class-ratio of subsets to non-subsets was taken to be 1:1.
We compare two variants of MASNET- MASNET-ReLU (M-ReLU) and MASNET-Hat (M- Hat) against Deep Sets (DS) [21] and Set Transformer (ST) [30]. Table 3 summarizes the results for varying values of [S] and [T). We observe that: (1) Both
variants of our method outperform the baselines; (2) the base- lines degrade significantly as (T') increases (with fixed |(S), as
1.0
HayerM-HHtt Hayye-ReLU
1
0.9
predicting separability becomes harder as the gap between [7]
Test Acc
0.8
and |S| increases; (3) The performance of M- M-ReLU and M- Hat is comparable. We now compare 1-layer pointwise mod- els ending in ReLU and Hat activation respectively, followed by aggregation: we call them llaeerRReLU and IlayerM-Hat, We see in Fig. 4 that: (1) IlayerM-Hat performs significantly than Mayer-ReLLU validating the results from Propn. 6. (2) acc. declines for both as (T) increases, consistent with the intuition that larger [T's \ S| gaps make the task harder.
0.7
0.6
0.5
50
100
150
200
[T]
Figure 4: Acc vs [T' for I-layer MLP
Set containment on Text datasets We evaluate on MSWEB, MSNBC, and Amazon Registry datasets, which exhibit natural set containment from user behavior. Each datapoint is a wordbag; we compute BERT embeddings for all unique words to form the ground set. (S, pairs are sampled from these (Appendix D), and labeled via set containment. For inexact containment, small
Gaussian noise is added S without changing y(S, T). We now compare the variants of MASNET: MAS- RET- and MASNET-HE
Model
Bedding Feeding MSNEE
DeepSets
0.31
0.30
0.38
0.67
against several base- lines, DeepSets [21], Set Transformers [30], FlexSub-
SetTransformer
0.77
0.79
0.90
0.94
FlexSubNet
0.88
0.85
0.92
0.91
Neural SPE
0.52
0.53
0.88
0.66
Net [32], Neural SFE [33], for inexact set containment on the datasets: MSWEB, MSNBC, amazon-Feeding Amazon-Beddin Bedding. Gaussian noise with 0.01 std was
MASNET-HOLU
0.98
0.98
0.99
0.97
MASNET-Hat
0.94
0.93
0.97
0.95
Table 5: Ace in text datasets with 1:1 ratio
used to generate noisy pairs. The class ratio of subsets to non-subsets was taken to be 1:1. Here,

---

set embeddings have dim m = 50, and set elements have dim d = 768. The results in table 5 show: (I) MASNET-ReLU and MASNET-Har have similar acc., with MASNET- ReLU being marginally better (2) Both are generally better than baselines.
Set containment point clouds We use ModelNet40 [34], a dataset of 3D CAD models across 40 categories. For each object in category C1. we sample 1024 points to form T'. For true subsets, we sub-sample S S T and for non-subsets, S is sampled from a different category C2- Small white noise(std=0000m 0055 is added to S for the task of inexact containment. We use pointcloud encoder(such as pointnet) followed by a set-to-vector em- bedding model to produce m = 50 dimensional embed- dings, and each point in the dataset is 3D coordinate with
[
128
256
512
DeepSets
0.32
0.31
0.50
SetTransformer
0.62
0.51
0.50
FlexSubNet
0.84
0.75
0.60
Neural SFE
0.52
0.51
0.50
MASNET-
0.98
0.94
0.72
MASNET-Hat
0.87
0.81
0.65
Table 6: Performance on Point cloud for dif- ferent values of [S] with 1:1 class ratio.
= 3 dimensions. The class ratio of subsets to non-subsets was taken to be 1:1. Results are in table 6. We observe that: (1) MASNET-ReLU and MASNET-HLE are generally better than baselines, with MASNET-ReLL being slightly better. (2) The accuracy of MASNET decreases as |S| decreases, with the separability becoming hard for monotone models.
5.2 Monotone Set function approximation
Model
MAE
In this experiment, we examine a scalar variant of MAS- NET can approximate a monotone function F*, by getting trained from set, value pairs in the form of {S, F* (S))..
DvepSets
0.01024 1: 0,00030
SelTrasformer
0.01026 0.00033
MASNET-ReLU
0.01023 + 0.00107
MASNET-ILL Haat
0.00959 1 0.00016
Once trained, we measure [M (S) F+ (S)) for each
Table 7: Monotone function approximation
S and average over them compute MAE. We compare MASNET against baselines: DeepSets,
SetTransfommrr. We trained using MSE loss, and report test MAE results in Table 7 where we see: (I)
MASNET-Hat is best performing, followed by MASNET-RELU (2) Both are better than baselines.
Conclusion and Future Work
In this work, we study the design of set functions that are useful in set containment through Monotone and Separating (MAS) properties. We derive bounds the embedding dimensions required for MAS functions and show their nonexistence in infinite domains. To address this, we introduce a relaxed model, MASNET, which satisfies weak MAS property and is provably stable. Experiments demonstrate that MASNET outperforms standard models on set containment tasks by leveraging monotonicity as an inductive bias. It would be interesting to check if our method can be used for applications in graphs, e.g., subgraph matching. Another potential direction is to consider other possible relaxations of separability.
7 Limitations
Our work provides a theoretical analysis of monotonicity and separability for set functions in the context of set containment, and introduces neural models that outperform standard set-based architectures such as DeepSets and Set Transformers on set containment tasks. Our work has the following limitations, addressing which are interesting directions for future work:
After proving the impossibility of constructing MAS functions over infinite ground sets, we proposed parametric set functions defined with respect to a probability measure over the parameter space. We provided probabilistic guarantees: for non-subsets S, T. if their asymmetric distance ASS, T) is large, then randomly sampled function from the parameter space will separate them with high probability. However, these guarantees hold only in the randomized aattinn-analogou to guarantees for neural networks at random initialization and do not extend to models after training via gradient-
optimization.
Our universality result, which shows that MAS functions composed with monotone vector-to- vector mappings can approximate all monotone set-to-vector functions, was only established for finite ground sets. Extending this result to infinite ground sets remains an open problem.
We currently do not generalize our amalysis to the subgraph isomorphism problem, which is natural and strictly harder extension of the set-containment task.
A Acknowledgment
Nadav and Yonatan were supported by ISF grant 272/23, Soutrik and Abir were supported by Amazon and Google Research Grant, as well as Bhide Family Chair Endowment Fund.
10

---

References
[1] Hang Huang, Joseph M Landsberg, and Jianfeng Lu. Geometry of backflow transformation ansatze for quantum many-body fermonic wavefunctions. Communications in mathematical sciences, 2023.
[2] Charles R Qi, Hao Su, Kaichun Mo, and Leonidas Guibas. Pointnet: Deep learning on point sets for 3d classification and segmentation. In CVPR, 2017.
[3] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In ICLR, 2019.
[4] Indradyumna Roy, Rishi Agarwal, Soumen Chakrabarti, Anirban Dasgupta, and Abir De. Locality sensitive hashing in fourier frequency domain for soft set containment search. In NeurIPS, 2023.
[5] Abraham Gale and Amélie Marian. Explaining monotonic ranking functions. Proc. VLDB Endow, 2020.
[6] Joshua Engels, Benjamin Coleman, Vihan Lakshman, and Anshumali Shrivastava. DESSERT: An efficient algorithm for vector set search with vector set queries. In NeurIPS, 2023.
[7] Gustave Choquet. Theory of capacities. Annales de l'Institut Fourier, 1954.
[8] Hamzeh Agahi. Choquet functional and it's applications in information theory. Information Sciences, 2018.
[9] Ernest Czogala and Józef Drewniak. Associative monotonic operations in fuzzy set theory. Fuzzy sets and systems, 1984.
[10] Michel Grabisch. Set Functions, Games and Capacities Decision Making. Springer, 2016.
[11] Benny Lehmann, Daniel Lehmann, and Noam Nisan. Combinatorial auctions with decreasing marginal utilities. Proceedings of the 3rd ACM conference on Electronic Commerce, 2001.
[12] Shahar Dobzinski, Noam Nisan, and Michael Schapira. Approximation algorithms for combina- torial auctions with complement-fre bidders. In STOC, 2005.
[13] Uriel Feige. On maximizing welfare when utility functions are subadditive. SIAM Journal on Computing, 2009.
[14] Maria Florina Balcan, Florin Constantin, Satoru Iwata, and Lei Wang. Learning valuation functions. In COLT, 2012.
[15] Seungil You, David Ding, Kevin Canini, Jan Pfeifer, and Maya R. Gupta. Deep lattice networks and partial monotonic functions. In NeurlPS, 2017.
[16] Avrim Blum and Ronald Rivest. Training 3-node neural network is np-complete. NeurIPS, 1988.
[17] Ryan O'Donnell and Rocco A. Servedio. Learning monotone functions from random examples in polynomial time.
[18] Nader H. Bshouty. Exact learning boolean functions via the monotone theory. Information and Computation, 1995.
[19] Ming Li, Chenyi Zhang, and Qin Li. Monotonic learning in the pac framework: A new perspective. arXiv preprint arXh:22501005003 2025.
[20] Ben Dushnik and Edwin W Miller. Partially ordered sets. American journal of mathematics, 1941.
[21] Manzil Zaheer, Satwik Kottur, Siamak Ravanbhakhsh, Barnabás Póczos, Ruslan Salakhutdinov, and Alexander J Smola. Deep sets. In NeurIPS, 2017.

---

[22] Tal Amir, Steven Gortler, Ilai Avni, Ravina Ravina, and Nadav Dym. Neural injective functions for multisets, measures and graphs via finite witness theorem. NeurIPS, 2023.
[23] Edward Wagstaff, Fabian Fuchs, Martin Engelcke, Ingmar Posner, and Michael A Osborne. On the limitations of representing functions on sets. In ICML, 2019.
[24] Peihao Wang, Shenghao Yang, Shu Li, Zhangyang Wang, and Pan Li. Polynomial width is sufficient for set representation with high-dimensional features. ICLR, 2024.
[25] Tal Amir and Nadav Dym. Fourier sliced-wasserstein embedding for multisets and measures. In ICLR, 2025.
[26] Radu Balan, Naveed Haghani, and Maneesh Singh. Permutation invariant representations with applications to graph deep learning, arXiv preprint arXiv:2203.07546, 2022.
[27] Yonatan Sverdlov, Yair Davidson, Nadav Dym, and Tal Amir. FSW-GNN: A bi-lipschitz WL-equivalent graph neural network. In LoG, 2025.
[28]
Yair Davidson and Nadav Dym. On the hölder stability of multiset and graph neural networks.
In ICLR, 2025.
[29] Paul Erdös and George Szekeres. A combinatorial problem in geometry. Compositio mathemat- ica, 1935.
[30] Juho Lee. Yoonho Lee, Jungtack Kim, Adam Kosiorek, Seungjin Choi, and Yee Whye Teh. Set transformer: A framework for attention-baa based permutation-inveen neural networks. In ICML, 2019.
[31] Joseph Sill. Monotonic networks. In NeurlPS, 1997.
[32] Abir De and Soumen Chakrabarti. Neural estimation of submodular functions with applications to differentiable subset selection. NeurlPS, 2022.
[33] Nikolaos Karalias, Joshua David Robinson, Andreas Loukas, and Stefanie Jegelka. Neural set function extensions: Learning with discrete functions in high dimensions. In NeurIPS, 2022.
[34] Zhirong Wu, Shuran Song, Aditya Khosla, Fisher Yu, Linguang Zhang, Xiaoou Tang, and Jianxiong Xiao. 3d shapenets: A deep representation for volumetric shapes. In CVPR, 2015.
[35] James R. Munkres. Elementary differential topology, volume No. 54 of Annals of Mathematics Studies. Princeton University Press, Princeton, NJ, revised edition, 1966. Lectures given at Massachusetts Institute of Technology, Fall, 1961.
[36] Antoine Wehenkel and Gilles Louppe. Unconstrained monotonic neural networks. NeurIPS, 2019.
[37] Zhou Lu, Hongming Pu, Feicheng Wang, Zhiqiang Hu, and Liwei Wang. The expressive power of neural networks: view from the width. In NewrIPS, 2017.
[38] Andreis Bruno, Jeffrey Ryan Willette, Juho Lee, and Sung Ju Hwang. Mini-batch consistent slot set encoder for scalable set encoding. In NeurlPS, 2021.
[39] Jeffrey Willette, Seanie Lee, Bruno Andreis, Kenji Kawaguchi, Juho Lee, and Sung Ju Hwang. Scalable set encoding with universal mini-batch consistency and unbiased full set gradient approximation. In ICML, 2023.
[40] Lynton Ardizzone, Jakob Kruse, Carsten Rother, and Ullrich Köthe. Analyzing inverse problems with invertible neural networks. In ICLR, 2019.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: All claims were introduced were formally restated in the main text and proved formally in the appendix.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? [Yes]
Answer:
Justification:
In main paper, limitations are included.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms
and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess..
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proof's
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: In the appendix all claims and theorems were formally proved.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
13

---

The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We provide the link of the Github repository containing the code in the paper. Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results. 5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide the link of the Github repository containing the code in the paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr
wwwsssssooiiiyyoo.. for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
14

---

The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/ //nips. //nips.ccppbbll.. teliii/gguiissseee / /woodeeubbissiiiiic ceiiimisssooooiiiiiiii for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: In the appendix and in the README of our code repository, we added full implementation details and configurations.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: One table contains error bar, but other tables do not. Training stable. Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula,
call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification: In the appendix, we provide our machines, including CPUs, GPUs.
Guidelines:
The answer NA means that the paper does not include experiments.
15

---

The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't I make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: //nurri///erris..... cc pptblic/Ethicssuieeel.. Answer: [Yes]
Justification: We did everything as the rules.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there special consid-
eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: We do not see any significant social impact of our work.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following unintentional) misuse of the technology.
from (intentional
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (c.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA]
Justification: No danger in our code. Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
16

---

Datasets that have been scraped from the Internet could pose safety risks. The authors
should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: All we used is open source. Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: We have assets. Guidelines:
The answer NA means that the paper does not release assets. Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects. Guidelines:
The answer NA means that the paper does not involve crowdsoureing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
17

---

Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects. Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: We used LLM for editing and occassionally bibiliographic search. Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy https:////euripie /c///oofereccee/222//11111 for what should or should not be described.
18

---

APPENDIX
A More discussions on related work
This work lies the intersection of representation learning for sets and multisets, monotone and submodular set functions, and theoretical limits of learning under constraints on some partial order. Below we review related literature across several communities, such machine learning, optimiza- tion, theoretical computer science, fuzzy measures, and physics. We highlight how these threads connect our problem setting.
Multiset to vector functions, and permutation invariant functions (including symmetric and anti- symmetric polynomials) have been used in a bunch of real life modelling tasks. Anti symmetric polynomials in the context of quantum many-bodyy physics was used in [1]. For point cloud datasets, such set-to-vecte embeddings are widely used such as in [2]. In the context of search and retrieval, set-containment was directly used in [4]. On a somewhat related aspect. [5] deals with monotone ranking functions on a vector of This is specifically monotone function from multisets to reals if the vector P denotes the weight/frequency of each object in the set. Moreover, since this is a vector-to-real monotone function, composing set-to-vector monotone function with monotonic ranking function preserves monotonicity. These are relevant to the recent usage of set containment in the context of information retrieval. Another related usage is in vector search [6], where relevance based retrieval is done after converting objects into high-dimensional embeddings.
More specifically monotone (multi)set to vector functions have been of interest in the form of theory of capacities [7] which is a probability measure based on monotonicity. In fuzzy set theory, where partial membership is allowed, any set-to-vector monotone function is equivalent
vector-to- vector monotone function. Measures and integrals on such structures have been explored in the form of Choquet integrals [8, 9] etc. In the context of game theory and economics, monotone and submodular functions are used to model diminishing marginal utilities and in combinatorial auctions, such as in [11, 12, 13]. In learning theory, understanding PAC learning and hardness of vector-to- monotone functions have always received a lot of interest. And using the membership vector of multisets, this id bassically equivalent learning multiset-to-vector monotone functions. Some works such as [16] uses set contaionment and monotone set functions as a tool in the proof. Specifically, they perform a reduction of neural network training to the set splitting problem to prove the hardness result. This is the task of partitioning set S = S₁ U S2 such that for a collection of subsets {C+ : C, S S. Vi) we must have C, g S and C. L S2, Vi. This is basically preventing set containment for a subset family. More direct applications include [15] which discusses the challenges of learning vector to vector monotonic functions or [14] that discusses learning monotone valuation functions. Works like [18, 17] deal with learning monotone boolean functions to any constant accuracy, under the uniform distribution in polynomial time. Since any boolean vector is basically one-hot encoding of a set on fixed size vocabulary, this paper essentially describes learning monotone set functions. Works on monotone learning such as [19] describe learning processes in which expected performance consistently improves the amount of training data increases. Thus, a trained model is a monotone set function from the training dataset to reals, where the output is a valuation metric.
So far, we have discussed works that have used multiset to vector embeddings and analyzed them. We have taken special care to discuss works that have involved the structure of monotonicity and
applied it to various domains. However, to the best of our knowledge, there has been no previous work that specifically deals with partial order preserving set-to-vector maps. One related work is [20] which have studied order dimension of a partially ordered structure. Now, note that partial order preserving sets are injective as discussed before, and injectivity is in fact a weaker condition that the MAS property. Here, we discuss a number of works on injective functions on multisets. The paper [22] shows that moments of neural networks do define injective multiset functions, provided that an analytic non polyynomil activation is used. They also state and prove a finite witness theorem, which is of independent interest. There are series of works such as [25, 26, 27] that design bi- Lipschitz(hence, injective) embeddings on sets and graphs. On the other hand, works like [23, 24] investigate the impact of latent dimension on the expressive power of set functions such as DeepSets.
19

---

B Proofs of the technical results
B.1 Prool's of existential results on MAS functions
Theorem (Dimension of MAS Function). For a finite ground set of size n, there exists a MAS function F; ; 200 (V) R". In addition, any MAS function must have dimension of at least n. In other words, m² mV(V, 00) = n.
Proof. The construction of a monotone embedding with n [V] simply uses one-hot encoding. Namely, we identify V with [n]. For every S E (V), we define
F(S) = Σ e, E
(10)
SES
where e, E 12 the vector with [s]s]
and e, Li] for all j s. We now show satisfies all conditions: Be S C T, then by definition, Ve E V,es(v) I cr(v), then F(S) =
Exese Cx I EiEr et = F(T) thus F(S)= S F(T). On the other hand, if F(S) S F(T) then
Vu E cs( S CT(U), and thus S TT.
For every [m]] there is "maximal singleton element" of E V such that F((u;))( [)d] 2 V. The value of the set function over the union of such vf-s across i E [m] will dominate any singleton that is disjoint from this collection, thanks the monotonicity of F. As
For the second direction, assume there exists MAS F : V + R' for m S n output dimension i
(() Ve E
m < [V] then 7 == _ (u,) } does not cover V. Thus, we can select an element disjoint from this
collection named V, which gives disjoint sets S = {s); T with F(S) S F(T), which contradicts separability.
Theorem 2 (Upper Bound on m² k)). Let < n be natural numbers, and let V be a ground set with V Then there exists MAS function F (V)x(V) R with embedding dimension m (k 2)x++2 log(n).
Proof. For convenience of notation, in this proof we will assume without loss of generality that V [m]. As discussed in the main text, the function Fa, Fa........ will be weakly monotone for any choice of non-negative vectors. Our goal is to show that there exists a set of parameters ai,.... ..m E 1)", such that the obtained Fai....... is monotone embedding, which means that, S I T. then there exists some such that (S) > (T). or in other words (J(S),aj) > (J(T), az)- We note that to prove this, it is sufficient to consider pairs (S, T') which we will call extreme pairs. This means that S consists of single element x E V, and T consists of & elements in V but does not contain (but repetitions are allowed). Indeed, if the claim is true for such pairs, and S,T E Pex (V) such that S ạ T, then there exists element x which is in S more times than it's in T. First, remove all copies of x from T, and we know that at least one copy of x will be in S, note that the difference between the function values remains the same. Then, we will 'replace' S with a smaller set = {=}, and 7 from adding more elements to T from V \ {x) to obtain a new set T of maximal cardinality k. We then will have that (3,T) is an extreme pair, and so for some j we will have that h5() > h₂ Therefore, using the weak monotonicity of the function hj. we will have
h;;S) 2 hy(5)= (T) 2 (T)).
Given an extreme pair (S,T) we consider the set of all 'bad' a, namely Bs. = {a E [0. 1J" (f(S), a) > (f(
Our first goal will be to bound the Lebesgue measure of this set. Recall that S is a singleton S = {s}. and T' does not contain this singleton. Accordingly,
В5T {a E [0. 1]"1 a, S Eat ar)
SET
We will compute the probability of the complement of this set, namely vectors a such that o, > Eier oz. First denote by
EST = fa 1] T, < ag k
20

---

Note, that
Es,r S {a E [0,1]"
as >
Σ arj
1ET
So let's compute the measure of Es,r!
Leb( (B,T)) = Leb(fa e [0, 10, S 4.
{
{ ( ) ht . (I: + 1)
(I: + 1)h+1
So,
Leb(Bs,r) I Leb(Es,T) $ 11-
(k: + 1)kt1
Now, consider the
B {ai,..., , Om Bggr):
Then we have
Leb(B5.)
(k: + 1)A+1
The vectors 01,-.. will not define a monotone embedding, there exists an extreme pair S T be bounded by union bound. There
which is in S.r- The probability of this happening n ("x²) extreme pairs, and for simplicity we will replace this number with a larger but simpler expression n+ n ("**), The union bound will then give
(1
1
Leb(ar.... am do not define monotone embedding J S n k+2
(k: +1++1
It is sufficient to show that this expression is smaller than 1, for our m, which, by taking logarithm, equivalent to requiring that
(k + 2) In (n) + m In (1- (k: + 1)k+1
Using Taylor's expansion it can shown that In(1 x) < x for x E (0, 1), and as result sufficient to choose so that
m
(k + 2) (n)
(k + 1)6+I <0
or equivalently
> (k: + 1) (k- 2) In(n).
For convenience we slightly enlarge this lower bound to obtain m 2 (k - 2))++1ln(n)) In(n)
Theorem 3 (Lower bounds on m² (V, k)). Let k: 2 and n be natural numbers, and let V be ground set with [V| Then the smallest possible dimension m (V, k) of a MAS function satisfied mV, k) Z log, (log, Moreover, if k < 2-1 then m (V, k) 2 2k
Proof. The proof is partially inspired by the proof in [20].
Lower bound on k: We want to show the lower bound of m (V, k)) > min (2k; - 2). As in the proof of Theorem 1, we select a "maximal singleton element" of V for every dimension i (1,2. ... mV, (V, k)). Thus we must have:
for each i [m" (V, F((G))) 2 F(LU)),, Ve
Now, if mn (V, S |V] - 2, we can find two elements {u), 42n disjoint from the collection mm (VSk) {or). Without loss of generality, we can assume that F([u1 [ 2 F(fug))(1 for most indices in (V(Kk)) We can then construct set T containing in and all the ug for all indices i for which F F((n)) [i] < (F((w)))( thus we define:
: Um =
T [w,] U fuz F((U))D F(fu2)D1))
We then have that:
F({u2)){1 < max(F((u H]] F((E)))) S F(T) Vi (V,(V)))))
where the last inequality uses the monotonicity of F. This implies that F(S) < F(T) However, S not subset of T. It follows that S [T] S m² nV'(V, k2, as otherwise separability of F in Psx(V) is violated. Hence, we get that: m² (V, k) 2k
21

---

Lower bound on n: For this proof, we will use the Erdös-Szekeres theorem, which in particular states, for natural N 2 2, that sequence of real numbers with 2 N2 elements has a subsequence of cardinality N which is monotone (either monotonously increasing or monotonously decreasing). Assume we have F: (V) -> IR a monotone embedding, where V = [n). Assume by way of contradiction that:
log2(1og, n) > m or equivalently n 3
Consider the first coordinate and look at the sequence
F((1)) ..... [[
This is a real-valued sequence, and so there is a monotone subsequence a1 < 02 < .... ..... ag of the original sequence 1,...,n, n, with = v - = 32" such that:
F[a1)[1]]= I F(a2)(1) .... S. [1] F(a:)[1] 2 2(. F(a)([]
Next, we consider the second coordinate of this subsequence, namely obtain a new subsequence {az} such that both the sequences: {F(aj)[1}} and {F(a))(2)} are ordered
F(ar) [2] and
monotonically, and the size of the subsequence is the square root of the previous one, namely 3
After doing this m times, we have subsequence of size 3. Namely, we have three distinct elements U, U, w E such that for all i = I,....
either F( & F(())) s F( or F(()) 2 F(()) 2 F(1)))
It follows that for all i, we have:
F([ S max ((W)))) S F(fu, w) w)]
Thus, F((u)) S (((,,)))) which is contradiction since (v) is not contained in (u, w).
A refined lower bound: Now, we may extend the above proof idea to generalize the lower bound on m (V,Kk,, which is useful specially when [V] >> k. In such cases, the following gives tighter lower bound on m² (V, k) which is quadratic in k.
Lemma 15.
For all E [k)) we have m² (V, 1)) min (IV) e, 0k 28 1.). More specifically, if t= k+2 then m (V,k) 2 min {iV] - 2 {
21
Proof. Consider any L E [k]. Like in the proof just before, we consider a "maximal singleton element"
of V for every dimension
{1, 2, ... m (V, (V) and obtain the collection ;= U (Vik)
(V. {of}
Let us assume m (V, k) < [V] f. Thus, we can produce the collection Ut := {wi, U2 ... Uz} disjoint from V. i. Vnu 0. For each u, E U, let my be the number of co-ordinates j
[m* (V,k)] such that F(fug)D > F(fu,)) Vr E [4] \ {4). Clearly, EyEiq my I m (V,K),
thus, 360 E [C] such that me, ("(Va)), Like before, we consider the sets S = {ue,). We
construct T as follows: we select 21 \, {we,) and take union with all {w²) } for each dimension in which F(uue, }) > F(tu,)), Vr E [C] {Eo). Since {u² } is the maximal singleton for the dimension j. it follows that F((ue, Hb] < F([o) }b). Hence, if we define:
T (4 (uc 1) Up; F((uro }bb] > F([u)), Vr E [4] (6)}
By the choice of l. we have that K/ : F((m)))))))) > F(fu,)), Vr E [ (4)) < mV(A))) Now, E
we must have that, Vj E (V,K)). E T such that F({{) > F((u,,)i By monotonicity of F, we thus have that F((u,,)) 1)D1 S F(T) Vj E [m (V,A)) which implies F(S) S F(T). But by design, S S T 0. which contradicts separability of F. Thus, must have that, [T] > k.
Le [T] 2 k. But as stated before, [T] s m" (V.K) + 1. Combining these two, we get that:
2
m (V.A) > k + E, which implies m² (V, kl 2 8 thus proving our result.
Now, we already have sufficient upper bound on m² (V, k) from Theorem 2 that's O +1++2 log(n)). Now, when n >> we have that O (K++2 log(n)) < n O(k), in which case we may apply
{= & in the above lemma. And since we already know that O (A*+2 log(n)) < n - 0(k), we
thus get that m² (V, < n n--(k), Thus, in this case the above lemma gives us m (V,K) 2 (k22) which is tigher quadratic lower bound in k.
22

---

When A = 1 In the degenerate case where only single set element is allowed. A = 1, it is by defining
possible to construct a MAS function even for the uncountable ground set V = = 1] F: P (1-((111)))) 1J) 2 via
F(S) - (-1, (-1, 0 and F(S) = (-x,
{z),
(11)
Separable embeddings (even non monotone) don't exist: Now, as discussed in the main text, we give justification here on why we choose to relax separability and not monotonicity in the definition of wekaly MAS embeddings. Here, we show that, with the added assumptions of injectivity and continuity, even non non-monotone set-t-vector embeddings do not exist in any dimension for uncountable ground sets.
Theorem 16. There does not exist a continuous injective separable set function taking values R for any m when the ground set V is an open subset of R
Proof. We restrict ourselves to P=n (V), i.e, only subsets of size n. Since F is continuous and permutation-invariinn,, according to Theorem-7 of [21], ('(
p(Σn ó(x;)), where p. continuous and bijective(given in condition). Now, consider the space S [0, 10 { (ZI,...,,Ix)
< < 23 (to see this, let minggin- F S R." is an injective, continuous map. Thus, by Invariance of Domain The5rem((35), F(S) is open in R as well. Note that each element of S uniquely corresponds to an element of P=n (V). Thus, F(P_n(V) is open in R", Now, consider any A = {al,... ..... Since I' is an open map, we have that 36 > such that B(F(A), 8) C (V)=n(V)). Thus, 3B E P=n (V) such that
< Fn: 0 < < 1, E [n]]. Note that S is open in [0. 1 z2.. The ball of radius & is contained in the domain). Since
F(B); = F(A): + 2n Vi E [n]. But then, F(B) > F(A) implies A C B but |A| = [B] = n by construction. This gives a contradiction.
B.2 Proofs of results on on weakly MAS functions
Proposition 6. If the deep set model in (2) is implemented with a vector-to-vector monotonously
increasing function M2 and a non-negative activation o, then F(:; (A, 6)) is monotone for every b). If in addition is monotone (increasing or decreasing), then there exists S g T with F(S; (), S (T;; b)) for all A, b.
Proof. Let x < y and consider the two sets:
S = + 31 T, =
And we claim that for all A, b, although S I T, F(S, (A, S F(T, (A,)). Note that as x <
242 < y, then it must have been that
2
U 2
Ax
+ Ay b
Or
+ y 2
Ay+b A
+ b < Ar b
Then, by (weakly) monotonicity of the activation a and of M2, it must be that
I ササリ !
(AA
+ b) < (
2
Or that
2 + リ
(A
+ b) < (AA
2
In any case, it's true that
y
(A
< ((A x x (o
2
Then, by monotonicity of M2.
+ y
F(S, (A,b)) M2 (A
+ b)) < M2 (o(A x x+ + b+b)) = (A,,))
2
Thus,
F(S, (A,b)) S (AT))A
23

---

Proposition 17. Let V R and let F (V) + RD be Set Transformer defined by oo WK. Wv) SumPool(Arm(SS) Then F not a point-wise monotone function.
Proof. We need to cone up with class of tuple of parameters (Wq. WK. Wv) such that the function S F(;; Wo WK. Wv) is not monotone. Choose We W K W such that W full-rank. Choose any non-zero Wv. Now, choose some vector x such that Wy is non-zero. By swapping X1 with -x if necessary, we can choose some index j such that for V = Wvx,, the j-th index is negative, v. [5] < 0. By assumption
also have that qi kj is non-zero vector, and thus has a positive norm. Now let be the singleton set = {xi}. which is a subset of T = {xi, 0z} where Og is the d- dddimensional all-zero vector. Note that, F(S; Wo, WK. Wv) V1. And since q2: k2. V2 are all zero, we have: F(T; Wo, WK, Wv) = (01,1 + V1. Note that, an,t
tnd
.14112 elq + 2/2 1. Hence, it follows that F(T; Wo WK. Wv) F(S; Wo. WK. Wv)[i] and thus, the non-monotonicity follows
Proposition 8. If M2 strictly monotone increasing, and o is a hat activation function, then (a,bb, = 22 a(a x + b)) is weakly MAS function.
Proof. It's clear the function a set function. Be S C T, as positive, then for any a, b.
Σ FES
aa x +b - Eo(a" x +b) + Σ oa x +b = Lo(a"zs x(a"x++))
xES
FET
So
(a,
Denote by [81. S2] the support of and choose some point in it such that [21 (s) >
Now, be S E T, then there exists 2 E V Cs(z) > Cr(2). Now, remove 2 from both sets (2 times. This subtracts from both function values the same amount. Now, we have that Z E S, & T. Denote by m
Choose
- 81 b - 2a --8
We claim that Vt E T, Ta ++ b) = 0. Assume it's not zero, thus 81 <a.t+b< 82. Thus
82 81
81 <
t - a 2
Thus,
82 81
52 81 2 <
8 <
Thus,
81
82
< 1 2 < 6
82 81
82
But,
81
1
82 81
82
51
82 81
Thus,
- -e t S
A contradiction the definition of c. Thus, F(T, (a, b)) (0). But
(a + b) = (a . 81) = ((1)) >0
Thus
((,) M2 Σ o(a +)) > Mc(a(s:)) > M2(0) = ((T
S
And we are done.
Proposition 18. Given V C Rd., we consider affine transformations Ag .Rdd + R33
A
3
R
Thus, here Az(t) == Art + by and A1(2) a 2 by, where Ag 3xxd by E 3 b
24

---

are the respective parameters. Then, the set functions of the form : (V) +R, F(: = M2 (Exes ReLU A ReLU A2(x))
(3)
are weakly MAS functions.
Proof. Consider the function TRT as in the third plot of Fig. 2. We know that TRI belongs to the class of Hat functions. From 9 know that, for any S I 7 E <oo (V), Fa E Rd and b TK such
that Exes TRI(a' 6) E yer TRI(a + 6). Now, consider the following parameters.
A aa, a,
3 b [b + 1,b 1,4 E ER
(12)
0g 1, 1, 2 R² and b
Then, for the above values of parameters, we have:
ReLU o A2(x) = [RLLU ((a x + + 1). ReLU ((a b) - 1). ReLU (a + b)]
Thus, have:
al (ReLU o A2(x)) + bn
= ReLU ((a (aTx + b) + 1) + ReLU ((a x x 1) 2ReLU (a + b)
TRI(a
x (aTx
b)
Thus we have, RcLU o A1 o ReLU o A2(x) = RcLU TRI (a TRI (aJx + b). Hence, F(S)= = Exss TRI (a T x x b) > EyES TRI (a y + = F(T) and weak separability proved. Since M2 is monotone increasing and ReLU is non-negative, it follows that F is monotone as well, hence weakly MAS.
B.3 Hölder separability of MAS functions
Theorem 12 (F lower Hölder). Let V C RR be a compact set, and a a Hat activation function which is piecewise continuously differentiable supported in some interval [11, and satisfying the condition:
do
R be a lower function Consider the function F(S; (a, b, c)) = M2 Eres a ( a ~ Unif(5 ~ Unif([-1, 1)),e Unif((0,2) 2). Then, F(o, (a, c)) is Monotone Hölder separable with exponent =
lime+r7 dt
R > 0. Ler M2 :
a++)), where the multisets come from PVx(V), and
Proof. We consider V C ld to be compact set with maximum norm of 1. Also, note that, if (x) is a Hat function with support in 72]. then a "="1 ) is Hat function with support in (0, 1). For this proof, general norm bound of V. the distributions on b, c needs to be scaled and shifted to get same Lower Hölder results with the Hölder constants scaled appropriately.
thus consider to have support in [0, 1]. For support in general [n, and
We recall the definition of A(S, T)
... ................. .yv], where S,T C V. Clearly by the definition of A (SS, T", )), it is sufficient to consider |S| < [T), i. M S N k.
from equation 4. Let S = { M } and let T {
Using the definition of EMD gives us the following equivalent definition of A(S, 1fM.N = [M] + [N], is injective). then A(S,T) = min,en Σ |z v-(i 22 Let 7" be the optimal coupling between [M] and [N], i. T" arg eDMa Eiillz Fr(e) l12. which means A(S, T) ΣM 1| (1) l2- Now, Vi [M], define A; || (r)l2 For any I E Rdd r let B(x, r) denote the Euclidean ball centered x with radius r. We define Ω = [M] (1) B(x,, Ad) Vi [M]. With these notations, we make the following
observation:
Claim-1: Consider any E (0, k). Then, Bio E [M] such that EiEO De S Di, and
A A(S,T)
IIf Sf ||||||
B, and supp(a) C [m, 72] then distributions should be shifted by Y2 and lincarly B and to be: b Unif(-n 6, -71 8) and Unif(0, 28) respectively
scaled by 5 = 72-71
25

---

Proof. For the sake of contradiction, we assume otherwise, i. Vi E [M], we have: either A; S r
ge+1 A T) or Eten. A 2 Ar.. WLOG, assume the following order on A, 's: A 2 4 2
AM. We build the following directed graph G on [M]. Start with the node to 1 and add we add arg maxuER Au and add the edge (1--1, Us))
one node to G at time. At step I, we select to G along with the new node Ut.
ii=1 A. This, implies that: A.o 2 M as we take argmax over entire [M] .Thus, A, 2 A) 2 A(S, T)/k. Thus, by the contradictory assumption, we must have: EvEr... A. 2 Air. Since 11 = arg maxueR.o A.. thus follows that: A., 2 F 2 (S,, Following the similar argument, we thus have, Auz 2 {) and so on. Thus, VE E N we must have: Ever., Au A., Thus, for 12+1, defined by: arg maX Au, we must have: Aumt 2 Au. Since this holds for every t E N and since 2 (E) A.w.
Note that, by definition of A(S,T) T) we have that: AS, = Ex A(S.T),
r > 0 by hypothesis, we must have: D., 2 E 2 (9) A
As we work with finite M, N either 9 is a DAG and this process terminates; or G has a cycle. In former case, at termination step t, cannot add any more nodes, thus De, 0. Since all nodes
are unique in this case, we must have t, I k. So, D., 2 (E) Aea
T ($) * (SS, Since (S,,T), and hence done
ea k
T E (0, 1) by hypothesis and since t S k we thus have: A.. 2 (E) with this case.
For the second case, consider the smallest cycle in g. Let this cycle of length p be C
{ug + u-+1 - ... - 12+p-1 - f for some 8 2 0. Then, we have: B ++++le E 22z+i, Vi E
{0, {0....p 13, where addition of indices modulo p. Thus we have: || (r-(rg+i+1]ll <
|Ragts - (r [l, Vi E (0.... PP- 1011. Taking sum, we have the following: ||00g
(r*(us+1)lle 112 + ||
12 +....4. +1 +p- (u=)ll E
(r -
Hence, switching from the coupling i + r" to + r" 1) for i E {rg,... (2+--2) 2) and
from 03 + p 1 + T (Ug p 1) to 03 + - 1 1 strietly reduces the value of the sum
Σ= 1|, ()) 2|2. but we started with the optimal coupling r". This gives the reqd. contradic-
M
tion.
We also make the following observation regarding this "optimal coupling" T": Observation-2:
For any given i [M], if y3 E T n S2 for some [M. then 30 E [M] such that
j j=r"(() (2)
Proof. The proof follows from the following observation: if y E Ω. for any i E [M]. then must have: ||., - y5lla S A, = ||2, - Fr(e) l12. Thus, if yj was "free", i. if Bt E [M] : j = T (f), then
we can switch from i + r"(i) to i + j. and this would reduce the sum Σ Di ||= (r) ll2. but r" was the optimal coupling. This gives a contradiction
M
Now, as per the starting discussion, we consider supp(a) 10,1], 1). and the proof for general support of [n, 72] requires the scaling and shifting as mentioned before.
By assumption we have, lim, d'(t) > O. We define σı lim, lim o'()) Since is piecewise continuously differentiable per assumption, we must have d'(t) 2 KI, Vt E (0,w) for some w E (0, 1) by the continuity of a'. Note that, by Lagrange's Mean Value Theorem, we have that:
Vx,y (0, (o(z) a(v)l
x - yl d'(x), where (2, v)
Va, y E (0, (0, (o(x) a())l 2 xi |x vl, since E (0,w)
lim (x))) a1)) 2 11 |x| as a is cts.
y-0
(2) Z Kj Yo E (0,w), as as
Also, a upper Lipschitz with constant K2 > 0 per definition of Hat fn. Now, consider the in coming from the Claim as proved above. We define w/ := min(1"g. _ 1). Let P e N be such that 7 <
26

---

and xp < and w' > p. Note that, such a P E N exists, since taking P - oo satisfies all the 3 conditions.
Tu fa y: y T). Note that, since we have || ||uا|| S 1, vi E [M],] E [N] per earlier assumption, we get S,, Ta S (-1, 1). For given E S0-1, we define the "optimal coupling" between the real-valued sets Sa: Ta as: To = arg MiM, M |a zq a Dr(a) Based on this, define 4 := |a x; a (zz(
Now, for given 8t-1, consider the sets S.
and 2 fer E [M] (rg(e) E B(a z4, A.) We have: A(Sa, Ta) == E Af. Let in E [M] be the index that comes from applying the claim to the sets Sa, Ta. Now, we define the regions
Bu (a sa Big W T Big
A:
p and for given pair (a 80-1, b E R), we consider
Co.b = ( 0io -b a
T Dio + A. - b). Thus, we have:
(a Ita - -b) a Tin Fin
(1 w) (b a (Tooo) + +w
1 w-w w (b. (b-a) a rio) + w A
1-
w (b (a T Tig w ()) > 0, v4 > aT Tig
xix - w A
The above analysis shows that C..b # 0, vb E Ba, so the intervals are well defined. Now, if E B and y < a I's A then we have: y - < a Tio A - a Tio + +w' = (w' - 11 in S 0 by definition of w' On the other hand, if b B. and E C. for given any y a 2i + A g
a T -+4.
we have: yーb > aig -43
1. Combining these, we get that if yy a T Tio > A then
- & (0, 1). vb E B.. E C..b. Thus, conditioning on a given a S we can write the conditional expectation taken over b, as follows:
a x
a
b
Eb,c
DES
FET
a T x
b
a y b)
Σ RES
Σe
(bE CECo,))
using non-negative RV
c
c
yE
aa 2i0
T sio +
b
a
Nio
b
2 4
o
1=a
Jun
-w A
vin
(r -
(0
a
xt
- b)
0
dedb
c
c
aa Zi0
T Bio + +4
a T Tig -
K1 Ag
K1
R2 Pxz
dodb, from Lipschitz cts. a
b=a
Tzig
-w A
Fin
K1
Zig
a Nio - b
Aa
in
pa any + Aio de db, as ReLUUra)) = (ReLU(>))
4
b=a
w/ 2% Big
P
Tay-
A9
Zig
Ag
w(a" T Din + + - b)
T
Fig
-
b
In
db
h
T sig
p
a Dio b
Ki
4
Aa
2
A a
P
in
In
w(z + Ag,
dz, butting = a xin - b
TTx,
27

---

K1
)
-
In
w
+
dz.using non-negativity of integrand
P
2
K1
In1
w
(1+
1+
2
))
/
a 10
dz
w
Aa
P
w'
1
In (2
w)
(4 2, using w/ 1
P
20
K1
(A"(S.T))? where C was E (0 and P
2 w
by earlier choice
K2P)
Thus, we have shown that: Es,e
[ 2 ())) By law of total expectation,
we have:
Ba
F(S)
F(S)-F(T) [09-F((1)
= EEg [F(S) ((T)) |a
+
2C (S" T))² 2 C' (E,)"())T)* by Jensen's 's ineq.
Thus, to show Lower Hölder separability with exponent À = 2, it remains to show that, A AS, 2 a1 A(S,T), where e > 0 is constant. Now, make the following
observation:
Observation-3: Suppose we're given given l E N and l many non-zero vectors 11 U2,"" " Me Rdd If 8d-1, then (8) such that: {|a" usl 2 8(8) 1ll ví e [4] 2
Proof. Firstly, we note that, for fixed E [d] la T us is continuous non-negative real-valued random variable. Thus, 36, E R4 such that P {|a" T u.| 2 4 > 2. Now, Choosing 6; := To. 0
4
gives us: P{ usl 2 dl]|uel]} 2 1. Vi E [e]. Since 6, > 0, Vi E [f] and é is finite, we thus have: 5 = minjer 5, > O. For this particular choice of 8, we have that IP {a uzl 2 ]||uا]} 2 2 vi E [.] and the observation proved.
Now, consider all lo := (M) M! M! vectors (x; - Vr(a) E Rd, where t runs over all injective functions from [M] - [N]. For this particular choice of lo. we get from the last observation
that, 38,,, M) such that P {[a" T (I; Fー()) 2 8(N, M)][ Br(o |I] 2 3.2 for all possible
injective F : [M]] + [N], we call this set a E S to A S Sd-1, Now, given a fixed a E 8d-1,
we have a particular Ta : [M] + [N] that gives (S,T) = Σ la" (x, V+,( Also, let
r²: [M] + [N] be the "optimal coupling" such that A(S Em || y (o)ll) 1l- Now, we can
write:
Bo- A (S,T))
M
Ee-Uni((Ss-1)
Σ
(x; - -
M
> BooUnillSS 1)
T (x; von(0))
a A P. Pota A}
8(N,M) M)
E.
| Vr, 01ll
8(N, E,
M
Σ
V (0)l2
as 7" is optimal coupling
2
5(N, M))
AM
5(N,
Σ
||ara Vr ())l2)
A(S,T)
2
2
28

---

Hence, F is Hölder separable with constant C' and exponent À 2.
Theorem 13 (Probability bounds on separation). Let V C R and a be as in Theorem 12, and let A E Rmxd b E Rm E R whose m columns (respectively entries) are drawn independently from the distribution on aj, by,cj described in Theorem 12, and consider the function
A,, c) Eves (c-1 @ (Ax + +b))
(6)
Then there exists C > 0, so that for all S ((F(()
& F(T) - (1 - CAT
Proof. Denote by ʃ the scalar-valued set function for a co-ordinate of F; we proved it's lower Holder function. Let S g T, then by lower continuity we know that,
E ww [I] f(T; 14 2 C- T)², for all S, E (V)
(13)
We know that
2 2 ( [I w) f(T; (1::w)) SP([(S: w) 2 [[T;(())))))))) w)) sup [S w) 2 f(T;w))
c. 2
weW
Now, note that as f is bounded function, denote by M the supremum of f over all sets $ and weights w W. Thus by the triangle equality,
(S,, T)² < 2M P(S(S: 2 [(T;w))
Thus, we obtain that
c. (.))))))
S PP(((S:)) 2 f(T;w))
M-
Thus, the complement satisfies:
w) < f(T; w)) = c. (.A T)2
2 -M
Now, taking independeing copies of namely F, we have that
P(vi E F(S w); < F(T: < (1 c. A(S,T)
)m
2 M
Denoting by C= 2M yield the desired:
((F(S:w) F(T;W)) (I-C-A(S,T))
Lower Hölder separability of ReLU networks So far, have only given results about Lower Hölder separability of MAS functions with Hat activations. However, as seen in Proposition 10, we have seen that two layer linear network with ReLU activation is weakly MAS, and observed from the proof technique, such a layer ReLU net can "simulate" a hat activation. In our arguments, we have shown Lower Hölder separability of Hat Activation based parametric set functions by finding a separating parameter point w E W for given pair of sets (S, T',, and constructing an open set of non-zero measure, W C W around w. We lower bounded the expectation of the non-negative Random variable in the definition of Lower Hölder separability(in Equation (5)) by restricting the expectation only to W and showing that is proportional (S,,T)* One can extend this exact same idea to construct the open set of parameters for the two later ReLU networks from the separable parameter point that we get from proof of Proposition 10.
Also, as obtained from Proposition 6, we see that one layer ReLU networks are not even weakly MAS. But a key key step in that proof uses that can find 3 collinear elements in the ground set V and construct sets with them to obtain the necessary counter-example. Thus, a natural question is ask: whether shallow I-layer networks with ReLU activation are also weakly MAS with some additional assumptions on the domain. We show in the following result that, with the additional assumption of V being a hypersphere, we may guarantee Lower Hölder separability for even shallow ReLU networks.
Theorem 19. Given ground set V C s We define F : PCv(V) + R as F(S) = Exes ReLU (a=x * b). where a ~ Unif(Sd-ij and ~ Unif(-1,1) Then, for any S,T e Pcoo(V) we have: E.g (F(S)- depending only on k.
- F(T)) 2 C(K)A(S, (d++3)) for some constant C(k) >
29

---

Proof. Let S = fz1,-.. ,MM} and T = {v1, .. ...,,, where M < E k. And according to the equivalently write ((S min Σ || Ve(all2- Let π be the optimal solution the above problem, then we can define the map [M + [ as follows: T(i) = x =1)),, Vi E [M Essentially, I2 and Vr(() are coupled in the optimal alignment. Now, for any given E [M]. let A, == || (7 Then, consider the open Fuclidean ball B A.). Then if j [M] such that yJ E B(x;, A,) then, j r(E) for some l [M]. Otherwise switching from i + T() to + reduces the cost, which violates optimal alignment. Let
definition of A T) from Equation (4)
Ω = {e E [M] (r(()) E Bi }. Here, we make the following claim:
A: Claim 20. 3a E [M] such that EjE,, Ilu, - -1-10))22= - 16
and Da 2
16A2" (16k)ak
Proof. Suppose not. WLOG, assume the following order A 2 42 2 2 Av. We build the following directed graph G on [M]. Start with the node vo 1 and add one node at time. At step t. we select 84 == arg max A, and add the edge (V--1, vt). By the assumption,
( ((G8)) )² Since work with finite M, either G is a DAG and this process terminates or G has a cycle. In former case termination step T we cannot add any more nodes, thus
Au,
16k 2 A )a 2
16k
16k A² (S:T) 2 16. (8.T) and we're done. Otherwise, consider (164)=*
2r =0. 0. and T 1 kt So, Ar 2
(16A)2*
the smallest cycle in G. Let this cycle of length be = {ug + 2341 + ..... + Pp+p-1 + ug). Then, we have || Ur(va+i+1)llz < || Dr(vg+1) ll2, Vi E (0. (0..... P 1) and addition of sub-indices is modulo p. Thus, we have the following: || (r +))l2 || V 22) l12
+ || i + r(i) to + 7(i - 1) for E (ug.... Us+p-2) and to Uy + p + ug strictly reduces the cost, but we started with the optimal coupling. This gives a contradiction.
Br(es) l2 < 2
(r(v++s) 122 Hence, switching from the coupling
Consider a as the above claim. Then we define the region: A = {a E Sd-1, ||a - -x,l { }.
Then, Va E A, l|a
Tall2
< ||a
Vr(a) 112. Thus, a Fa > a Vr(a)- Also, consider the region A? < -1 8 J. For any given a E A, we have:
Ba == { R: - 16
A3
A3
|1e=
+
+
64
2
la=æll <
2
A2
32
thus -1 +
+
4
To
04
+
||a=
2
< -1 4 < -1 -1 8. Ba + 0. Also note
that, Ya E A, E Ba, we have:
ReLU (a (0a)))) ]
(F(S) - F(T)L+ 2
ReLU (aT +b
Σ
ReL.U (a To vn(0))
BEN
ReLU (aTxa +b
Σ
ReLU (a vr(os)) - ReLU (aTap))
BEN
ReLU (a za +b)
Σ
la (x v)
BEN
2
ReLU (a Ta +)
Σ
|| - 3r(83)|
BEl
A?
||a
x012
A
A2
T Fa b
1
16 ++
2
16
64
Thus, we have:
Eg,b [F(S) - F(T)]_ 2 Eo,b ((6)
A2
>
P fa E A,D Ba}
64
A
1/3 3
1
A2 -(a) - -1) da
64S
Jag 21
22
2
64
30

---

A
213 S JaES :01 21
32
1.3
A
(1
22)
4-1
dx
A
A
2
A
2
213
218
32
32
'2
A d+3
223
Now, using the bounds from 20, we get that, Aa 2 C(k) (S, Thus we have that, E [FF(S) F 2 (())))( and done
Upper Lipschitz property of weakly MAS functions We now show that, the MAS functions obtained by applying one layer neural network with Hat activation for each element of the set, followed by sum aggregation are also Upper Lipschitz continuous in expectation with respect to the augmented Wasserstein distance, following the framework of Davidson and Dym [28]. This shows stability of such MAS embeddings. We say that a parametric set function F Pg (V) x W - R Upper Lipschitz in expectation if 3C > 0 such that:
Fuew||F(S)) w) FT;; w)ll S C. C (S,T,, E
(14)
Where (.()). is the augmented- Wasserstein metric for sets in (V), where padding is added for k [S] times to any multiset of size less than We work with a compact ground set V. and we pick padding that has positive distance from V. For the following proofs, we work with V C I&d which norm bounded by 1, and we choose the padding element = E IRd such that ||=|| 2 For general V whose norm is bounded by B, we can scale the padding by B. With this, we
are Upper Lipschitz w.r.t W.. Now, if we take independent parameteric copies across m output dimensions and if M2 is a vector-to tenoo--to-vetorr Lipschitz function, then functions of the form M2 F, where F has the form in Equation (6) are Upper Lipschitz as well. This we state in the following theorem:
show that, real valued functions F PV) + R given by F(S) = Σzes a
Theorem 21 (F is upper Lipschitz). Let belongs to the class of Hat activations, and V C Rd be compact ground set such that sup.ev < 1. We consider Iz-h with the distributions a ~ Unif(S Unif(-1, 1), Unif(0, 2). Then
PVx(V) + R. F(S) =
Exes
a constant O, such that for any S, T (V)(V):
Ea, ((S)-F(C) - SC. (.())(
Proof. Consider S [II,,... AMM ), {y1,". yN). Since [F(S) F(T)) is symmetric in S, T, we consider WLOG that M S N. As in previous sections, we use T to denote an injective IN, denote the set of all injective functions from
function from [M] [N], and [M] + [N]. Thus, we can write the augmented Wasserstein distance on (V) with padding as:
wy(k) (S,T) arg min
Σ 10 U+(0
Σ 11 =1|
rElxx.M
jpt(()
Let 7" be the argmin of the above expression that gives the Wx(S, Now, we can write:
E. (F(S) F(T) E,,
Σ
0
xj
bb
a (r)
-b)
Σ
yj
b
c
c
1=1
(t)
M
(Tx;; x; b
TT yT*
- b)
(a yj
Babbe
o
Bable
c
jf
We now separately analyze coupled and un-coupled terms: ie terms of the form
and
the following analysis. For the proof that follows, we consider supp(o) S [0, 1]. For support in (11,72) the proof follows similarly by sifting the distributions of b, c by mi and scaling by 72 71.
0 2 - af - (.
31

---

n yj
Computing R2
c
Note that, d ys 0, v4 2 a a²zz yj. Also, for given b E (-1, (laTyy) yj) we have that:
E (0,a a T yj b), リ 21
yj
Thus, conditioned given 8d-1, we can write the conditional expectation over b, follows:
yj
Es.c
1
Dj
2
D1 -
b
-o(0) dodb, using (0) 0
4
T y)
c
62
V5
T 1/j -
de as a Hat activation, it's Lipschitz
1=-1
c= b
c
12
V
2
K2
( (- d2), == a aTy, -
2
(a
b)In In
db
In
4
b
Ja
v1+1
R2
vs+1
2 In
dz
R2
Vj
+ 1
(a
yj
+ (a yj + +1
4
4
2
2
a yj +
162 (a y, + a
T = 122
a (y)
+ a)) -
122
13 + all -
R2 18y - 2||
4
4
4
Now, taking an expectation over a ~ Unif(S 1) the inequality is preserved and we get that, for "isolated yj ', Eo
4 |ly - =|
Thus for "isolated" elements from the larger set that get coupled with the padded element while computing augmented-wy(s) we have shown that they are upper bounded by their diatcne from the padding Hence, it remains show similar Lipschitz upper bound for the elements Ii, Im E S) which have a corresponding U1(1)," :M((m)) E S2 in the optimal coupling
Computing E a (aa""x) a " bb)
Now, we have, for any i [M]. and given E Sd11 'he conditional expectation E, o (T)
a a v. is symmetric in in and ())(()) Thus, WLOG we can assume that, a Twy (r)
Note that we then have:
a o T (t) -
a ( Vb E (a vr 2i), Ve (aTx, - b)
o وطرير or (" vb E (-1,a (rTT)))))) Ve E (a (aT Vr- - b, 2)
0, otherwise
Hence, conditioned on a specific a E Sd-1, we can write the conditional expectation over b, as:
x;
yr(
- b
bia Tia (r Loaazz- σ x; b
Tx
Es
o
dc db
c
aa ()
T
b
o T
((*(()) -
+
dedb
b=-1
R2
a 81
2 db
Taxz - b) In
4
b0z ToaTyra (ra(()
x, - b
32

---

+
K2
Ta; - ---r(ii))
/ hm--
())(0)))
In
a yr- - -6) d6
2
4
12
( d2 + +|aa (or - --rr yr-(1)) ( 11
(2) dz
2
$
21n
4
122
(|a" T (Ii - (r)())) + 2|22 (is - yr (r)(1))) < ni la (x; vrr(1))]
4
Sxal|=; - Vr ll. by Cauchy Schwarz
Thus taking one more expectation over a S4-1, and summing over all E [M], we get:
rj o( a T (T (ー
M Σ b0 (+)(
E b
Thus, combining our computations for "isolated" y₁ and "coupled" (ai, V/ (5))'s )'s we get that:
M
B.,b,o ((5) F(T))
1ly - K2 Σ Σ
c (r) k
(+
And our proof of being upper Lipschitz is complete.
B.4 Universal approximators with MAS functions
Theorem 14 (Universality). Let V be a finite ground state, and let F P&& Rm be MAS function. Then for every multiset-to-veett veectorr monotone function f (cv(V) + R there exists
vector-to-vected monotone function M R -> R2 such that F(S) = M f(S).
Proof. A MAS function is in particular invertible, and therefore we can write f(S) = foF On the image of F' we define the function M =fo o F-1 which is vector-to- vector functions, and it is monotone on the image of F, because if = F(S), u = F(T) for some sets S, T, and < u. then by separability 5 T, and therefore
M(v) = f o (v) f(S) < f(T) f (u) Mu)
Finally, we need to show that M can be extended montone function on all of I". we accomplish this by defining M(e) max(M(M) U, u Image(F)
C Details about our model
C.1 Architecture details:
In all 4 of MASNET models, we use an elementwise neural network NN. Rd + RT where the ground set V C Rd and the output in in RT We follow that with sum aggregation, followed by monotone vector-to-vector neural netwrok M2 I - Th_ For the embedding Neural Network, use 1 hidden layer NN with ReLU activation in the hidden layers and ReLU Hat activation in the output, depending on whether we're using MASNET-Ree MASNET. To make M2 monotone, we use non-negative weights by taking the absolute value of parameters before applying the linear transformation, and use all monotonic activations like ReLU in the intermediate layers. Now, discussed before, give details of our model MASNET-INT.
or Hat activation based
C.2 MAS
In this appendix we design universal approximators for the class of Hat functions to learn We parametrize For that, we derive equivalent conditions on the derivatives of a (per embedding dimen- sion) and use the techniques of learning functions by modelling the derivatives using neural networks and then using a numerical integration as in Wehenkel and Louppe [36].
Lemma 22. Ifa + Roo belongs to the hat activation class then o' satisfies the following conditions for some positive constants C' > 0 and a E R, B > 0, 7 E (0, 1):
33

---

1. supp (a') _ [a, a 8
2. fatt dz) =
3. o
(x) (x)
C. V.
4. o'( 2 a (a,a+77
The above 4 conditions, along with o (aa) 0 are the neceesary-suffccientt conditions that character- izes the hat activation class.
Proof. We first prove that, if a belongs to the hat activation class defined in 8, then conditions
1 1- are satisfied. Note that, if a is a Hat activation, then has compact support in some (ax, a + 3 by deifnition, and it's piecewise continuously differentiable. Thus, outside (a, + S]. we have
= 0 = o' = O. Hence, supp(a') C [ar, a' + 3]. We also have that, 0 = o(a) = a(a + 3) = a(a + 3) (a)
0 = Sa+t o'(t) dt = 0. Finally, being Lipschitz is equivalent to (o'(t)) I C for some C O and by continuity of o' in (a, a + B) we must have that 2c := lim;-o+ (t) > = (t) 2 c, Vt E (a, a 7 (3) for some 7 E (0, 1). Thus, conditions 1-4 are implied by a belonging to the Hat activation class.
Moreover, if conditions 1-4 are satisfied, and (a) O, then condition-2 implies a(a + +3) = 0. This, along with condition-1 implies that (() = 0, VI & [ax, a + .3. Condition-4 immediately implies that (a 7 () 2 c. 7 0, thus 0. On the other hand, get that a' < C implies by LMVT that, (a(x) [g)) < C- | yl. Hence, belongs to the class of Hat activations following the
definition from 8.
Neural Parmetrization of MASNET-INT: Consider (g).), h2,()) to be non-negative bounded and bounded fully connected Neural Networks respectively of one hidden layer each. Also consider the trainable support parameters to be a E R," E IRT 7 E (0, 1) where m is the output dimension and a, y are the support parameters, aggregated for all output dimensions. Now, we define an integral based model of parametric hat functions. Let θ = (0, 0, a, B, m) be the parameter space.
aa(x)= = 1( h1(()) da
rat hb(2)dz
(I" 1 (ath8:::00
rats hz)2)
(15)
In the above formulation, addition to the support parameters we also learn the function itself rather than performing linear interpolation, this makes the above class a universal approximator of hat functions.
Lemma 23 (Universal Hat approximator). The family de defined in Equation (15) is an universal approximator of the class of Hat functions having support in [o,, a + 3] with of (t) > 0, vt E (ar, a +8))
Proof. We show that the given parametric model is an universal approximator of Hat functions using their equivalent formulation Lemma 22. Let 01 be restricted to the interval [a, a + 2,3] and 0g be bestricted to the interval [a + 7;,, a + 6]. Using Theorem-1 from Lu et al. [37], we can get ReLU neural network h/ - IR and h3 IR - F of width each such that approximates the derivatives of the restricted functions of and ozz. Thus, the following hold for any e > and any constant e E R:
t
[o((2) - n=)) dz S e and / Jatn (2((() + c- n²) dt Se
gats
(16)
We now observe that, if x E (-o0, a). both the indicator functions: ( and 1 (a+)85ago+3)
in the integrands of Equation (15) evaluate to 0, thus de exactly coincides with a. On the other hand, if I E (a + B, oo) then we would have the first integral of 15 evaluate to
fa pa+r0 hz)(z) dz (due to presence of the indicator 1 (as=sat7,9 and the second expression evaluates to
Jats (2, (=)dz (Iatt 122 (z)dd) = Jata h)(2).2. Thus, both the expressions sum to and ag coincides with a for (a 3, 3,00)= well.
[attrr (g(ads
Now we shall show that, for any x E (a, a + 3) we must also have (oe(x) - [xx) S 6, implying convergence in sup norm. We consider the following cases:
34

---

Case-I: When x E (a. + 788,, we have that:
(x - xx(r)
df(z) d2 J: dz
df(x) hb(z) dz, by traingle ineq.
[o](2) (+)) dz, by non-negativity of integrand
<c, by Equation (16)
. Case-II: When E (a + +8, a + 8) we have:
(xx) oe(2)]
d2))) patt hz(z)
f 1z(2)
Jaty0
Sa pati h/
(d](2) 11)(2)) de + L
d2(2)+
h2(() dz
Jatn
sa+t 1 (z)dd
1443
(0)(2) hb(2)l d2 1 02(2)
Sa pattl 1b(2)dz
h²(2))
d2, tri. ineq.
J (2(2) de
I 10788 J (2)
patti hb(2)dz
<e
+
d2(2) +
(2)())
dz,by 16 on 1st term & tri. ineq. 2nd
<2
Ja hi (x)ds in the universal approximator for o in Jo+s (z) dz Equation (16). Thus, just we see that, for any e > 0 and a E R, 1 0,800,, 0, E (0, 1) we can find universal approximator for the Hat function class
where last inequality is obtained
Parametrizing a, 3.77 We have provided an universal approximator for the Hat function class given a, 7 but we'd also want to have a, 8 as learnable parameters. This is valid for both MASNET-Hat and MASNET-INT, as in both cases we seek to learn the support parameters. Now, there is no constraint on a, so we can directly initialize a 3m and learn through gradient descent. However,
have constraint on 3 that / > 0. For this, first initialize Bo E 1 and we obtain / RT by appling co-ordinatewise positive transformation on Bo. This we do in two ways, depending
which works better given task: (I) by simply taking Bo + [.8]. where the absolute value is taken pointwise. (IIbby taking the pointwise transformation Po + ELU (Go; v) + u, where ELU (:: v) is the Exponential Linear Unit with hyperparameter > 0. Note that, the ELU
ar, if
function given by: ELU (LU(2;;)
(e" if, <0 For parametrizing 7 E (0, 1),
similarly initialize To E Imm and then apply pointwise transfprmation that takes each co-ordinate (0, 1). We use tempered sigmoid function: Yo + Sigmoid (7 7o) where t > 0 is a hyperparameter
Designing soft indicator functions: In the integrands for MASNET-INT, we have some indicator
functions of the form (os (x) = 11 e
We want these indicator functions to have
0.
non zero gradients we intend to learn the "support parameters" a, b of such indicator function. If we chose binary indicators, then that not differentiable everywhere and have gradient 0 in most places, making it difficult to learn a, b. Thus, we design a "soft" indicator function with the help of tempered sigmoid with hyperparameter Tş as follows:
(a5-56)(2) (z) = Sigmoid (Ts (a a)) Sigmoid (Ts (b x))
35

---

C.3 Making MASNET Mini Batch Consistent
There has been chain of works to make set-based neural models be mini batch consistent in [38. 39] which have applications in large scale machine learning. The goal of these Mini Batch Consistent (MBC) works is to design set function F, which, if applied on any subsets from partitions of set and pooled through an activation should return F(S). Thus, at high level, MBC functions analyse and design functions for the following batch consistency condition: (F..))).... FF(S))) = F(S). MBC methods achieve this by imposing certain restrictions on attention based set architectures. Similar to this, our work also puts restrictions on the inner embedding transformation and the outer vector-to-vectee transformations. It is thus natural question to ask, if MASNET can be made minibatch consistent. Since set containment the major theme of our work, with potential applications in retrieval and recommendation systems, processing huge sets at once can be key bottleneck, and it would nice to make MASNET process over mini-batcher and then design some aggregation mechanism to make the aggregated embedding equal to the embedding of the entire set.
If we consider partition of given set S joint, then MASNET(S,) < MASNET(S). by monotonicity. But, we can try to find an appropriate pooling mechanism over the subset embeddings to make the aggre- gated embedding same as that of the entire set. For example, mation Mo,, in Equation (7) was invertible, and then we may define a particular permutation-invarian pooling function 9 such that, 9(X1,"'' Xx) = Moz (Ee M (Xi). Me, (M (MASNET(S.))
U St, where Siss are all dis-
the outer transfor-
then we'd have: 9 (MASNET(S1). ".,ASS)),.,,MMNT(((SSS
Me, Exes, 0o oo (z) = Ma; (Exes a Mo, (x)) = MASNET(S). his is irrespective of how we partition S into S1, Sy. And this would enable process the subsets independently and aggregate them accordingly.
For our purposes, we have needed the outer transformation Me, be vector-to-vector monotone function Equation (7). But that doesn't 't guarantee injectivity or invertibility. Thus, we need to restrict the choice of Ma, to be monotone and invertible for MASNET to be MBC consistent. One possible choice is to use ideas from relevant works like [40, 36] to design monotone and invertible neural networks, and analyse the expressibility properties of the resulting set model. This forms an interesting direction for future work.
D
Additional details about experiments and more experiments
D.1 Hardware details:
All experiments were performed in compute server, rumning the OS of GNU Linux Version 12, equipped with a 16 core Intel()) Xeon(R) Gold 6130 CPU @ 2.10GHz CPU architecture and equipped with cluster of NVIDIA RTX A6000 GPUs with memory of 49GB each.
D.2 Dataset details and more experiments
We now give an account of preparation details of each dataset and accounts on more experiments on each.
Synthetic datasets and related experiments:
We begin with controlled synthetic setting where we generate pairs (S, such that kg < kr-
Each pair is labeled either positive or negative. For positive examples, we first sample by vectors in IRd from N/O, Ta), which form the set T. A subset of size kş is then uniformly sampled from T to obtain S. For negative examples, we again sample T as above, but then independently draw ks vectors from Rd to form S.
To simulate a real world scenerio of information loss, we inject gaussian noise into the vectors of to get S' but keep the boolean label unchanged.
On this, we provide two more plots: Figs. and that compares the accuracies of MASNET vs baselines, by varying the gap between target set size [T) and query set size [S]] Note that the more this gap is, the more it becomes challenging to separate two nub-sub.ets. In all cases, the embedding MIP Mo, from Equation (7) is comprising of > 2 layers.
Fast- datasets and related experiments:
36

---

Figure 8: Acc vs [T] for all models 2 2 layer MLP
Figure 9: Acc vs S for all models 2 2 layer MLP
We evaluate our models on three text based real-world datasets: MSWEB, MSNBC, and the Amazon Baby Registry datasets, of which reflect naturally occurring set containment structures coming out of user behavior in websites and recommendation engines.
These datasets consist of user activity logs from www.microsoff.com and www.msnbc.com, respectively. Each user session is treated as a bag of page identifiers, which are embedded into 768-dimensio vectors using pre-trained BERT model. We construct query-targer pairs (S, T) by sampling S from session V. and letting V S. A pair is labeled and otherwise. To simulate noisy real-world conditions, Gaussian noise is added each element in while preserving the label. The of labels to labels 0 in the entire dataset.
MSWEB and MSNBC:
S C T,
ratio was taken to be 0.1, which is the number
Amazon Baby Registry: This dataset contains subsets of products selected by customers, each tagged by category (e.g.. "toys" or "feeding"), ) Product descriptions are embedded using BERT. We 30, and for each valid subset S, we generate T 2 S of size 30 by
filter out sets of size sampling additional items from the same category. For negative samples, T is sampled randomly and
verified to satisfy /
Model
Bedding Feeding MSWEB MSNBC
Noise added to in both cases. This models scenarios such predicting whether a set of displayed products T includes customer's interest S. On these datasets, we provide three sets of additional experiments. In the first table, we perform the same set- containment task done in the main text, but with different eggative-to-positiv ratio of 90 10.
DeepSets SetTransformrr
0.91
0.90
0.93
0.97
0.91
0.90
0.94
0.96
FlexSubNet
0.90
0.91
0.94
0.94
Neural
0.93
MASNET- 0.95
0.93
0.97
0.97
MASNET-HA Hat
0.91
0.92
0.95
0.97
Table 10: Set containment in text datasets with 90:10 ratio
Note that, due to the inductive bias of monotonicity, all the positive examples are correctly classified by design is case of MASNET. Thus, it only has to learn to identify the separate the negative examples. Thus, if the test set has a higher proportion of negative examples, then it throws model toughter task learn. This shown the following Table 10. Other than the modified class ratio, we provide two additional tables: in the first one, we compare shallow(1 layer) vs deep (2 2 layers) embedding MLP Me, in MASNET, which shown in Table 11. White noise of std 0.1 added for inexact set containment.
Ablation studies on text datasets: MASNET
From the definition in Equation (7), we see that, the for- mulation os quite similar to Deepsets, which is of the form F(5) M, (Eres ReLU((" ReLU(aTM,(22 (x +b). As shown earlier, using ReLU in the last layer of an elementwise function with universally approximating M,
bedding
feeding
MSNBC
Shallow-ReLJ
0.69
0.36
0.92
0.93
Shallow MASNET TRI
0.83
0.76
0.94
0.95
Shallow-MAS MA-NET-HHa
0.89
0.77
0.97
0.96
MASTT---AASNTT-INT
0.91
0.92
0.95
(DoopIAANNCT-RLU
0.93
0.97
0.97
Dop-MMASNET-TRI
0.98
Deep-MASNEr-Hat
0.91
0.92
0.95
0.97
Doep-MASNEY-INT
0.93
0.92
0.96
0.97
an instance of MASNET.
Table 11: Comparison of shallow deep variants of MAS- NET across datasets.
37

---

But it is different from DeepSets in key points, namely: For set contain- ment tasks, we don't have an outer M2, which DeepSets have; for universal approximation tasks, we use monotonially increasing M₂ that we enforce by taking positive weights and increasing activation functions. Also, for Hat function based MASNET models, we use a re-parametrization in which we perform a division based scaling. We now show the effect of the outer monotonic M2 on DeepSets and division based re-parametrization on MASNET-Hal in the ablation study in table 12. White noise of std 0.1 added for inexact containment.
Pointcloud datasets and related ex- periments
Model
bedding
feeding
MSWEB
MSNBC
ModelNet40 [34] a benchmark dataset of 12,311 CAD models across 40 object categories, with each object represented as 3D point cloud. We frame our task as checking if a given pointcloud S is segmenet of target pointcloud
DeepSets
0.91
0.90
0.93
0.97
DeepSets, monotone Ma
0.90
0.91
0.94
0.93
MASNET- ReLU
0.95
MASNET-Hot
0.91
0.95
0.97
MASNET-Hat (No division)
0.87
0.92
0.92
0.94
Table 12: Ablation study
Firstly, we choose an object from an object category C₁ and randomly sample 1024 points from that object to get the target point cloud T. To obtain a positive sample (i.e true subset) from T, we first sample a random center point from T', and then extract S using hybrid approach: select- ing the nearest point to the center, a few local neighbors via k-NN, and the rest via importance-weighted sampling (inverse-distanns from center with noise). This makes sure that we' re selecting true local region from the point cloud, which is in-line with the actual task of detecting whether given segment of an object is contained in a target object. For a negative sample(non-subset) we sample S from object of different category C2.
[S]
128
256
512
DeepSets
0.90
0.90
0.91
SeaTrassformr
0.90
0.91
0.91
FlexSubNet
0.84
0.88
Neural SFE
0.89
0.89
0.90
MASNET-ReLL
0.91
0.93
0.98
MASNET-Hat
0.87
0.91
0.94
Table 13: Performance Point cloud for
different values of [S], for 90:10 class ratio
We first give the accuracy table for PointNet encoder, but with the modified negative-to-positvee class ratio of 90:10 to make the task harder for MASNET, which correctly classifies the actual subsets by the induictive bias of mono- tonicity. The numbers with the modified class-ratio are given in the following table of Tab Table 13:
[S]
128
256
512
DeepSets
0.89
0.90
0.90
SerTransformer
0.91
MASNET ReLU
0.87
0.91
0,93
MASNET-Hat
0.85
0.91
0.89
MASNET-TRI
0.83
0.93
0.87
MASNET-INT
0.87
0.90
0.92
Table 14; Point cloud with DGCNN for dif-
We also give the accuracy numbers for DGCNN encoder, in Table 14
ferent values of (S].
Details on Linear assignment problem In this problem, are given a positive matrix M E Raxm n S m, where Mr, represents the salary that a 'worker' will be paid to do a 'job' j. The goal of the task is maximize the average salary obtained by all workers. This is done by finding the optimal assignment т E Sp,m which maps a worker E [n] to a 'job' T(i) E [m]] where by construction each worker can be mapped to most one job, so t(i) {0,1), This gives us the following maximization problem:
F(M) = max E Mi.
Thinking of the matrix M as a set of m columns M [M Mn], we see that the function F is permutation invariant and monotone, Accordingly, our goal will be to evaluate our MASNET model and baselines.
38


Reviews:
[{"review_id": "P6IkH9mcL9", "reviewer": "Reviewer_z6Li", "summary": "The paper discusses embedding (finite) multisets into vectors that preserves monotonicity -- i.e. the embedding of a larger multiset should be a (coordinate-wise) larger vector and conversely that two multisets–each one not a subset of the other–should be mapped to incomparable vectors. The latter direction is termed \"separability\" in the paper.\n\nThe paper explores the minimal vector dimension of such embeddings. It is shown that the minimal dimension is the size of the ground set (the set from which the elements of the multiset are taken). When restricting the function to work on multisets of bounded-cardinality, the minimal dimension may be smaller, and upper and lower bounds for it are derived. It’s also shown that no such embedding exists when the ground set is infinite.\n\nTo allow building such embeddings over infinite ground sets, the paper proposes 2 relaxations of the separability condition:“weakly seperable”, and “lower Holder seperable”. It proves that the embeddings proposed in the DeepSets paper are in general not weakly separable, but claims that using a different activation function it terms a “hat function” or that using more than one-layer of the element embedding part would make the final embeddings weakly separable and lower Holder separable. \n\nFinally, the paper evaluates the benefit of the proposed embeddings to the task of determining set containment and approximating a monotonic set-to-scalar function. It compares with SetTransformer and DeepSet embeddings as the baselines and shows that the embedding proposed perform better.", "questions": "- It looks like Prop 8 contradicts Prop 6: As far as I can tell, a hat function can be monotone and non-negative, in which case by Prop 6, there exists an S not-subset of T for which F(S,(A,b)) <= F(T, (A,b)) for all A, b, so F is not weekly MAS. Am I missing something?\n- In Theorem 13, isn’t it True that for all injective functions F:P_{<=k}(V) → R^m there is an M such that F(S) =M (F(S) ).  Also you’re using ‘F’ to denote both the MAS and the desired function F. Can you change the notation for one of them to make the theorem statement clearer?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "I think the inductive bias that the paper proposes for “good” multiset embeddings is useful. Containment is a major and general property of set objects and good embeddings should preserve it. To my knowledge its novel.  I find that the paper provides good theoretical characterization of the embeddings and works around the limitations with reasonable weakening of the requirements. \nThe presentation is clear and motivations are provided throught the paper on the various assumptions being made.\n\nWeaknesses:\n- I’m not an expert on partial-ordered sets or lattices, but I’d imagine that the results of Theorem 1 follow pretty easily from standard elementary results in those fields. It’s nice that the proofs are self-contained but it would be good to mention any standard results this can be derived from if any.\n- I would have liked to see more end-to-end experiments of using MAS models to solve realistic modelling problems such as the examples in “Deep Sets”:  point-cloud classification, Text Concept Set retrieval, Sum of Digits, etc. The paper only provides experiments that predict containment which is a much easier task for these embeddings given their inductive bias.", "was_revised": true, "final_justification": "The authors have addressed my concrents. It's a solid paper suitable for the conference.", "rebuttal": "We thank the reviewer for their comments, which we will incorporate in the revised version, if accepted.\n\n> *I’m not an expert on partial-ordered sets or lattices, but I’d imagine that the results of Theorem 1 follow pretty easily from standard elementary results in those fields. It’s nice that the proofs are self-contained but it would be good to mention any standard results this can be derived from if any.*\n\n\nWe agree that this problem of designing set embeddings that captures the notion of set containment is a very fundamental question, and lots of our proof techniques-specially those related to existential characterization of MAS functions, boil down to combinatorial arguments. However, we did an extensive literature survey and were unable to find significant existing work that derives results related to set embeddings that preserve the partial order of monotonicity. \n\nWe note that for some of the theorems we did employ some standard techniques: In Theorem 2 we leveraged probabilistic methods based techniques similar to Alon’s text on probabilistic methods [1], for Theorem 3 we have leveraged standard combinatorial results like the  Erdos-Szekeres Theorem [2]. We have referenced [2] in the main text but accidently omitted [1], we will fix this in the final version. \n\n[1] The Probabilistic Method by Noga Alon and Joel Spencer\n\n[2] Erdős, P.; Szekeres, G. (1961), \"On some extremum problems in elementary geometry\", Ann. Univ. Sci. Budapest. Eötvös Sect. Math., 3–4: 53–62\n\n > *I would have liked to see more end-to-end experiments of using MAS models to solve realistic modelling problems such as the examples in “Deep Sets”: point-cloud classification, Text Concept Set retrieval, Sum of Digits, etc. The paper only provides experiments that predict containment which is a much easier task for these embeddings given their inductive bias.*\n\n\nDuring the rebuttal, we performed several experiments on realistic examples as per your suggestion. Here, we present results on image classification on MNIST dataset from given segment of an image and text retrieval from BEIR datasets (NF Corpus and Scifact). For both of these realistic tasks, we intuitively think that having set containment as an inductive bias along with the power of weak separability might be helpful, which is reflected in our experimental results as well. \n\nSpecifically, for image classification, we used a N-layer CNN $a  _N(a  _{N-1}(....(a  _1(x))))$, where we froze the first $N-1$ layers and modify the last layer to ensure that $a  _N (\\bullet)$ is a MAS function. Thereafter, we predict the boolean 0/1 label on which images of the MNIST dataset have the same digit(object) as the candidate segment image.\n\nFor BEIR dataset, we used BERT embedding as input to a  MAS function. Following table shows the results, which shows that we perform better than standard set based models at a similar scale of parameters.\n\nFor both the experiments, we report the accuracy numbers in the following table:\n\n|Model|MNIST|NFCorpus|SciFact|\n|-|-|-|-|\n|DeepSet|0.62|0.61|0.69|\n|SetTransformer|0.71|0.68|0.72|\n|MASNET|0.85|0.72|0.75|\n\n\n> *It looks like Prop 8 contradicts Prop 6: As far as I can tell, a hat function can be monotone and non-negative, in which case by Prop 6, there exists an S not-subset of T for which F(S,(A,b)) <= F(T, (A,b)) for all A, b, so F is not weekly MAS. Am I missing something?*\n\nThanks for raising the point, but we'd like to point out that, a hat function cannot be monotone. \n\nAccording to definition 7, a hat activation is a real-valued function that is   (a) non-negative (b) compactly supported  (c) not identically zero and (d) continuous. Hence, if $\\sigma: \\mathbb{R} \\to \\mathbb{R}$ is a hat activation, there exists $a,b\\in \\mathbb{R}$ such that $a < b$ and $\\sigma(x) = 0$ for  $x \\in (-\\infty, a] \\cup [b, \\infty)$. Thus, if $\\sigma$ was monotone, then $\\sigma(x)$ would be identically zero, for all $x\\in \\mathbb{R}$, which is in contradiction with (c). \n\nSince a hat function can never be monotone,  we cannot apply Prop-6 to hat activations (since it only applies to monotone activation functions such as Sigmoid or ReLU), and thus Prop-6 does not contradict Prop-8.\n\n\n> *In Theorem 13, isn’t it true that for all injective functions F:P _{<=k}(V) → R^m there is an M such that F(S) =M (F(S) ). Also you’re using ‘F’ to denote both the MAS and the desired function F. Can you change the notation for one of them to make the theorem statement clearer?*\n\nWe  agree with the reviewer  the notation for one of the functions should be changed. Theorem 13 should read as follows:\n\nLet $V$ be a finite ground state, and let $F: P _{\\leq k}(V) \\to \\mathbb{R}^m$  be a MAS function. Then for every multiset-to-vector monotone function $f: P _{\\leq k}(V) \\to \\mathbb{R}^s$, there exists a vector-to-vector monotone function $M:\\mathbb{R}^m \\to \\mathbb{R}^s$ such that $f(S)=M (F(S))$.\n\nWith this correction, the theorem statement is now clearer and implies a non-trivial result.\n\n> The actual definition of “weak separability” is missing due to a typo in the paper.\n\nSorry about this, we accidently commented out the definition just before sumbission, while doing some edits. The definition of weak-separability is as follows: \n\n“The parametric set function $F: P _{\\leq \\infty}(V) \\times \\mathcal{W} \\to \\mathbb{R}^m$ is weakly separable, if given $S, T \\subseteq V$ such that $S \\not \\subseteq T$, there exists a parameter $w \\in \\mathcal{W}$ such that $F(S; w) \\not \\le F(T; w)$”. \n\nThis essentially means that at least some point in the parameter space separates any given pair of non-subsets.\n\n\n>In Theorem 12, do you mean m rows instead of columns?\n\nYes, and the matrix A as in Theorem 12 has dimensions $m \\times d$. We meant $m$ rows only, and sampling them independently. \n\n>What does “m” refer to in line 331?\n\nInstead of $(\\alpha +m\\beta)$, it should read $\\alpha +\\gamma\\beta$, where $\\gamma \\in (0,1)$ is as defined in line 330. Thus, $\\alpha + \\gamma\\beta \\in (\\alpha, \\alpha + \\beta)$, which means it’s an interior point of the support. \n\nThanks for pointing out all these typos, we have fixed these in our current version of the manuscript, so that the final version of the paper will be corrected."}, {"review_id": "n1keHUJsoy", "reviewer": "Reviewer_b3Mt", "summary": "The authors completely characterize the dimensions needed for a “monotone and separating” embeddings (for sets/multisets) in finite settings and show they are impossible in infinite ones, then introduce a relaxed “weakly” version that admits practical neural implementations. They propose MASNET, a simple sum decomposable architecture, based on Deepsets, with specially chosen activations that provably enforces monotonicity and, with high probability, separability. Finally, experiments on synthetic, text, and point cloud tasks demonstrate that MASNET outperforms existing permutation-invariant models on set containment and monotone function approximation.", "questions": "- Sum decomposable functions like deepsets have been shown limited expressivity compared to attention based methods like Set Transformer. Given that the proposed architecture is based on deepsets, what would be required to propose an architecture based on the transformer like Set Transformer that is monotone and separable? A discussion is enough.\n  \n- How are MAS functions related to the MBC methods [2,4]? From my understanding, the restriction they impose on embeddings of subsets, together with the aggregation functions they utilize (similar to DeepSets) have some connection with the problem tackled in this work.\n  \n- What happens when the set sizes grow to millions? While from Table 6 it seems performance increases with increasing |S|, what happens when |T| is very large?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n  - The paper precisely establishes when exact monotone and separating embeddings exist for sets in the finite settings and shows their non existence in infinite ones.\n\n  - Weakly MAS functions are introduced to strikes a practical balance between theoretical rigor and real world feasibility.\n\n  - MASNET combines simple sum decomposable functions with tailored activations to guarantee monotonicity and separability (where possible), as well as introducing the notion of Hölder stability.\n\n  - MAS embeddings are shown to approximate any monotone set function and gives exponential‐decay bounds on separation failure.\n\n  - MASNET consistently outperforms standard permutation‐invariant models on containment and monotone function tasks.\n\n**Weaknesses**\n  \n  - A large portion of the set literature seem to be ignored in this work (see References).\n\n  - The set sizes in the experiments are smaller than what is normally used in the set literature.\n\n  [1] Fspool: Learning set representations with featurewise sort pooling\n  \n  [2] Scalable set encoding with universal mini-batch consistency and unbiased full set gradient approximation\n\n  [3] Enhancing neural subset selection: Integrating background information into set representations\n\n  [4] Mini-batch consistent slot set encoder for scalable set encoding\n\n  [5] HORSE: Hierarchical Representation for Large-Scale Neural Subset Selection", "was_revised": true, "final_justification": "Most of the queries/concerns I had have been addresed by the authors.", "rebuttal": "We thank the reviewer for their suggestions, which will improve our paper.\n\n> *A large portion of the set literature seem to be ignored in this work (see References).*\n\nMany thanks, we will incorporate and discuss them in the main paper if our paper gets accepted.\n\nFspool used a sort-based pooling strategy and introduced the responsibility problem. Both HORSE and INSET are designed specifically for subset selection. Specifically, HORSE is built on attention and to retrain information from both the input ground set and the optimal subset. In contrast, our method focuses on characterising and neural design for monotone and separable set functions, specifically for the set containment task.\n\n> *How are MAS functions related to the MBC methods... have some connection with the problem tackled in this work.*\n\n\n **Relation to MBC works**: The goal of the MBC works is to design a set function $F$, which, if applied on any subsets from partitions of a set $S$ and pooled through an activation $g$, should return $F(S)$. Thus, at a high level, MBC functions analyse and design functions for the following batch consistency condition: $g(F(S  _1),...,F(S  _n)) = F(S)$.  MBC methods achieve this by imposing certain restrictions on attention-based set architectures. Similar to this, our work also puts restrictions on the inner embedding transformation and the outer vector-to-vector transformations. However, the nature of restrictions for our method is very different. Our method offers neural restrictions to ensure monotonicity and weak separability, which would translate partial order of set containment to the partial order of coordinate-wise vector dominance. \n \n \n **MASNET can be made Mini Batch Consistent:** The reviewer's question triggered us to think if MASNET can be made minibatch consistent. Since set containment is the major theme of our work, with potential applications in retrieval and recommendation systems, processing huge sets at once can be a key bottleneck, and it would be nice to make MASNET process over mini-batches and then design some aggregation mechanism to make the aggregated embedding equal to the embedding of the entire set. If we consider a partition of a given set $S = \\bigcup _{i=1}^k S _i$, where $S _i$'s are all disjoint, then $MASNET(S _i) \\leq MASNET(S)$ by monotonicity. But, we can try to find an appropriate pooling mechanism over the subset embeddings to make the aggregated embedding same as that of the entire set. \n\nFor example, if the outer transformation $M _{\\theta _2}$ of MASNET as in eq(7) of the main text was invertible, and then we may define a particular permutation-invariant pooling function $g$ such that $g(X _1, X _2, \\cdots, X _k) = M _{\\theta _2}(\\sum _{i=1}^k M _{\\theta _2}^{-1}(X _i))$. \nThen we have that: \n$g(MASNET(S _1), \\cdots, MASNET(S _k))$ \n$= M _{\\theta _2}(\\sum _{i=1}^k M _{\\theta _2}^{-1}(MASNET(S _i)))$\n$= M _{\\theta _2}(\\sum _{i=1}^k \\sum _{x \\in S _i}\\sigma\\circ M _{\\theta _1}(x))$\n$= M _{\\theta _2}(\\sum _{x \\in S} \\sigma \\circ M _{\\theta _1}(x)) = MASNET(S)$\nThis is irrespective of how we partition $S$ into $S _1, \\cdots, S _k$. And this would enable us to process the subsets independently and aggregate them accordingly. \n\nFor our purposes, we have needed the outer transformation $M _{\\theta _2}$ to be a vector-to-vector monotone function. But that doesn't guarantee injectivity or invertibility. Thus, we need to restrict the choice of $M _{\\theta _2}$ to be monotone and invertible. One possible choice is to use ideas from relevant works like [A], [B] to design monotone and invertible neural networks, and analyse the expressibility properties of the resulting set model.\n\n[A] Unconstrained Monotonic Neural Networks by Wehenkel and Louppe\n\n[B] Analyzing Inverse Problems with Invertible Neural Networks by Ardizzone et. al.\n\n **Experimental comparison with MASNET:**  We compare the suggested methods against our method on BEIR datasets for text retrieval applications. The following table shows the results, which show that we perform better.\n \n|Model|NFCorpus|SciFact|\n|-|-|-|\n|DeepSet|0.61|0.69|\n|SetTransformer|0.68|0.72|\n|FSPool|0.65|0.70|\n|HORSE: Hierarchical Representation|0.60|0.65|\n|Slot Set Encoder|0.62|0.67|\n|UMBC Set Encoder|0.66|0.66|\n|MASNET|**0.72**|**0.75**|\n\n> *The set sizes are smaller... What happens when the set sizes grow to millions?*\n\n\nIn the following experiments on synthetic data (with 1:1 ratio of subsets to non-subsets), we keep $|S|$ fixed and increase $|T|$. \n\nFollowing are the results.\n\n|$S$-size|$T$-size|DeepSet|Set Transformer| MASNET|\n|-|-|-|-|-|\n|1000|3000|0.68|0.73|0.99|\n|1000|10000|0.66|0.69|0.97|\n|1000|50000|0.58|0.68|0.95|\n|1000|100000|0.61|0.63|0.92|\n|1000|500000|0.55|0.59|0.90|\n|1000|1000000|0.51|0.54|0.87|\n\nTable: Accuracy for set containment when $|T|$ goes large.\n\nWe observe that (1) Our method outperforms the baselines more and more significantly, as $|T|$ goes large.  (2) Accuracy of all methods worsens as $|T|$ goes large. But, the degradation of performance of the baselines is very large, whereas the degradation of our method is quite modest. Intuitively, the chances of wrongly predicting $S \\subseteq T$ increase as $|T| >> |S|$, but MAS functions still do better as they're equipped with provable separability.\n \n \n \n> *Sum decomposable functions like deepsets have been shown limited expressivity compared to attention-based methods.  what would be required to propose an architecture based on the transformer .. that is monotone and separable? A discussion is enough.*\n\nSet Transformers are not monotone. Attention makes the monotonicity challenging due to the normalising factor in the denominator. We give a constructive proof of the fact that, for a large class of weights for set transformer, we can find sets $S \\subseteq T$, such that $F(S) \\not \\le F(T)$. Thus, it's not pointwise monotone, unlike MASNET, as shown below:\n\n\n**Lemma:** Let $V=\\mathbb{R}^d$, and let  $F: \\mathcal{P} _{\\leq \\infty}(V) \\to \\mathbb{R}^D$ be a Set Transformer defined by $F(X;W _Q,W _V,W _K) = \\text{SumPool}(\\text{Attn}(X))$, then $F$ is not a pointwise monotone function.\n\n**Proof** We need to show that there exist some parameters $W _Q,W _V,W _K$ for which the function $X\\mapsto F(X;W _Q,W _V,W _K)$ is not monotone. Choose any matrix $W _Q=W _K$ which has no kernel, and any non-zero $W _V$. Choose some vector $x _1$ such that $W _Vx _1 $ is non-zero. By swapping $x _1$ with $-x _1$ if necessary, we can choose some index $j$ such that for $v _1=W _Vx _1$, the $j$-th index is negative $v _1[j]<0$. By assumption we also have that $q _1=k _1$ is a non-zero vector, and hence it has a positive norm. \n\nNow, let $S$ be the singleton set $S=(x _1)$, which is a subset of $T=(x _1,0 _d)$, where $0 _d$ denotes the all zero vector in $\\mathbb{R}^d$. We note that \n$$F(S;W _Q,W _V,W _K)=v _1 $$\nWhile, since $v _2,q _2,k _2$ are all zero, \n$$F(T;W _Q,W _V,W _K)=(\\alpha _{1,1}+\\alpha _{1,2})v _1.$$\nNote that \n$$\\alpha _{1,1}+\\alpha _{1,2}=\\frac{e^{\\|q _1\\|^2}}{e^{\\|q _1\\|^2}+1}+\\frac{1}{2}>1 ,$$\nand it follows that \n$$F(T;W _Q,W _V,W _K)[j]<F(S;W _Q,W _V,W _K)[j]$$\nwhich shows that this function is not monotone. This concludes the proof. \n\nTo achieve monotonicity in interaction based set models, one could extend the notion of attention without the normalization factor, i.e., to use functions of the form $F(S) = \\sum _{x, y \\in S} \\psi(x, y)\\phi(x) + \\sum _{z \\in S} \\gamma(z)$ where $\\psi : V \\times V \\to \\mathbb{R} _{\\geq 0}$ is a non-negative function to model the interaction between elements and $\\phi, \\gamma : V \\to \\mathbb{R} _{\\geq 0}^m$ are vector-valued functions with non-negative entries. Such set functions are monotone by design.  Obtaining separability results in such cases could be quite challenging and this seems like interesting direction for future work.\n\nFor separability, we first point out to Corollary-4(l-173) from the main text, where we show that one can't achieve both mononicity and separability for infinite ground sets. Thus, for a \"monotone version\" of a set transformer, achieving full separability is impossible, and we thus fall to the notion of weak separability: which requires every pair of non-subset $S \\not \\subseteq T$ to be separated by at least one set of parameters. The exact characterization of parameters that makes this \"monotone version\" of transformer separable too, is challenging. \n\n \n**Experimental evidence that set transformer is not MAS** \nMonotonicity means that  $S\\subseteq T \\implies F(S) \\le F(T)$, or in other words, that in the set containment problem, there can be no false negatives.  Hence, non-monotonicity ensures in large false negatives. Similarly, the absence of separability results in a large false positive rate.  To evaluate this experimentally, we perform experiments on synthetic data with a 1:1 ratio between the number of subset-pairs and non-subset pairs. Results are as follows:\n \n\n|Model|False neg rate| False Pos rate\n|-|-|-|\n|Set Transformer|0.13|0.25|\n|MASNET-ReLU|0.0|0.02|\n|MASNET-Hat|0.0|0.03|\n\nTable: Acc, FNR, FPR for synthetic data with 1:1 class ratio\n\nWe see that MASNET has no false negatives due to monotonicity, and a low false positive rate due to separability, as we expected. In contrast, the present implementation of Set Transformers has high rates of both false positives and false negatives. \n\n> *Appendix link missing*\n\n We sincerely apologize for the inadvertent errors in the current version of the manuscript. In our internal repository, the manuscript was in order; however, during the final stages of submission to OpenReview, a few hasty edits introduced these typos. In fact, during the original submission, we uploaded a version of the full paper in supplementary material, which has all broken Appendix references fixed.\n\nIn any case, all these errors have been fixed in our current version of our manuscript, and all will be in order for the final version of the paper."}, {"review_id": "0zbF6n2oz4", "reviewer": "Reviewer_7bQs", "summary": "This paper considers the problem of the existence of mapping f between multisets and vector spaces such that S is contained in T (in the multiset sense) if and only if f(S) \\leq f(T) pointwise. The authors consider what is the dimension needed for the existence of such a mapping, consider neural architectures of implementing these functions and test these in multiple experiments on real and synthetic datasets.", "questions": "1) in line 31 15 is cited as relevant to the paper. I do not see why it is relevant. Perhaps the authors can explain?\n\n2) Why introduce a new activation function if embedding can implemented by a simple architecture with two layers?\n\n3) The introduction of parameters in the denominators in (8) could lead to numerical instability while training. Can it be avoided?", "limitations": "1) Lack of completing motivation for the notion of MAS.\n2) Numerous new notions (MAS, stability, new activation function and more).", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 4, "strengths_and_weaknesses": "The paper suggests a new notion  of MAS set functions that leads to interesting mathematical analysis. It also provides interesting experiments. One issue is the lack of compelling motivation for MAS as opposed to monotone functions. The authors need to articulate in more detail the motivation for their new notion. I also find the abundance of notions and results a disadvantage making it harder for a reader to take away the important findings and use this paper in theory and practice. The authors may want to focus first on their most important 2-3 findings as opposed to talking about stability, infinite sets  (less relevant to ML) and new activation functions. \nFurthermore the paper is pepped with inaccuracies (line 376, an inaccurate reference to the appendix and more). My feeling is that this paper is not yet ready for publication in a prime conference such as NeurIPS.", "was_revised": true, "final_justification": "The authors addressed some of my concerns. Accordingly I am raising my rating the borderline accept.", "rebuttal": "We thank the reviewer for their comments, which we will incorporate in the revised version, if accepted.\n\n> *One issue is the lack of compelling motivation for MAS as opposed to monotone functions.*\n\n\nWe begin with two applications which are based on the set containment task:\n\n(1) In recommendation system design, one problem is to recommend item having a particular set of features $S$. Here, we represent each item as a set of corresponding features $T$ and the problem is to find all sets $T$ such that approximately, $S\\subseteq T$.\n(2) Text entailment where we are given a small query sentence $q$ and the goal is to find the set of corpus items $c$ from a large corpus $C$, where $q \\implies c$ or $c$ entails $q$. Here, $q$ and $c$ are typically represented as sets of contextual embeddings (S for q and T for c) and the entailment problem can be cast as the problem of checking if $S\\subset T$.\n\nIn a neural network setting, such problems require us to design a function\n$F$ such that the order between $F(S)$ and $F(T)$ can serve as boolean test for whether $S$ is a subset of $T$. For this $F$ needs to satisfy two conditions.\n\n(I)    $F(S)\\le F(T)$  implies $S\\subseteq T$ \n(II)   $F(S) \\not\\le F(T)$  implies $S\\not\\subseteq T$\n\nWe would like to emphasise that for high accuracy, $F$ needs to satisfy both conditions (I) and (II). Monotone function ensures that if $S \\subseteq T$, then we have $F(S) \\le F(T)$ or equivalently   $F(S) \\not\\le F(T)$  implies $S\\not\\subseteq T$ (i.e., condition (II) above). However, monotone-only condition does not ensure the condition (I). As a result, if we predict $S\\subseteq T$ based on $F(S) \\le F(T)$ when $F$ is monotone but not separable, it will give large number of false positives. Therefore, we need to define the notion of separable functions to ensure our function satisfies condition (I). \n\nHere, we run some additional experiments for the text entailment application on BEIR datasets: NFCorpus and SciFact. The following table reveals that MAS functions perform better than all baselines (including four new baselines, suggested by Rev b3Mt) as well as monotone (but not MAS) functions. As per Prop-6 from our paper, DeepSet with single layer ReLU network as the embedding model is not separable (even weakly), which we chose for the monotone (but not MAS) set model for our experiment. Accuracy is reported as follows:\n\n|Model|NFCorpus|SciFact|\n|-|-|-|\n|DeepSet|0.61|0.69|\n|SetTransformer|0.68|0.72|\n|FSPool|0.65|0.70|\n|HORSE: Hierarchical Representation|0.60|0.65|\n|Slot Set Encoder|0.62|0.67|\n|UMBC Set Encoder|0.66|0.66|\n|Monotone Only (shallow ReLU)|0.59|0.65|\n|MASNET|**0.72**|**0.75**|\n\nThis strengthens our argument that monotonicity alone is not sufficient for set containment.\n\n> *The authors may want to focus first on their most important 2-3 findings as opposed to talking about stability, infinite sets (less relevant to ML) and new activation functions.* \n\nWe did ponder on this, but realized that there are several cases where infinite sets and stability are crucial. Note that by infinite sets, we mean the ground set or the universal set is infinite. Such cases are applicable when dealing with continuous features or representations. For example, in case of point clouds and images, the features come from a continuous distribution; in the context of health records, some features (e.g., blood sugar) may be continuous. Even in text applications, where the vocabulary consists of discrete words, the contextual embeddings of a word in a sentence  (e.g., BERT embeddings or LLM encoder output) are effectively continuous vectors. Since the possible occurrences of a word across sentences can be really diverse, the set of token embeddings (with added positional encoding) can be roughly considered as an infinite set in practice, due to the very small resolution.\n\nStability or holder separability also has practical implications, especially for infinite sets. Typically, in applications, we encounter approximate set containment rather than exact set containment, labelled by human annotators. For example, if two images consist of A = (\"leopard\") and B = (\"tiger\", \"tree\"), then a human annotator is  likely to assign $A \\subset B$. Holder separability can better account for this than exact set containment.\n\n> *paper is pepped with inaccuracies*\n\n We sincerely apologise for the inadvertent errors in the current version of the manuscript. In our internal repository, the manuscript was in order; however, during the final stages of submission to OpenReview, a few hasty edits introduced these typos. In fact, during the original submission, we uploaded a version in supplementary material, which has all broken Appendix references fixed.\n\nWe would like to emphasise that these issues have already been resolved in our internal version. Unfortunately, OpenReview does not allow us to update the current submission version, but we will ensure that all such errors are fully corrected in the camera-ready version, if the paper is accepted.\n\nWe hope that these typos—already fixed on our end—do not detract from the technical strengths of the work, which you also recognised.\n\n> *in line 31 15 is cited as relevant to the paper.*\n\nThe paper considers a reduction to the set splitting problem to prove the hardness result. This is the task of partitioning a set $S = S_1 \\sqcup S_2$ such that for a collection of subsets $\\mathcal{C} = (C_i \\ |\\  i : C_i \\subset S )$, we must have $C_i \\not \\subset S_1 \\text{ and } C_i \\not \\subset S_2, \\forall i$. This is basically preventing set containment for a subset family. For some context, we intended to mention some of the relevance of set monotonicity to learning theory. But we understand the connection may appear quite remote, and we will clarify this more in final version, if our paper gets accepted.\n\n> *Why introduce a new activation function if embedding can implemented by a simple architecture with two layers?*\n\nWhen we fine-tune a large $N$ layer model for different tasks, sometimes the practice is to freeze the first N-1 layer and only train/fine tune the last layer. Thus, here we fine-tune only one layer rather than two layers. In such cases, the variant of our model with exactly one layer with a new activation function can be more easily plugged and played. \nMoreover, for such large models--- which require large memory to fit---\nadding more layers will make it difficult to train with available resources.\n\nTo elaborate more, we consider image retrieval applications, where we are given a segment of an image as the query: $q$ and the goal is to retrieve all images in the database which contain the object(s) in $q$.\nIn this task, we only fine-tune the last layer of CNN with our new activation function. Experiments were performed on the MNIST dataset, and the goal was to retrieve all the images with the same digit as the query image segment. The performance is measured in accuracy, where each image in the corpus was assigned a boolean label of 0/1 depending on whether the digit in the image is same as that of the query segment.\n\n|Model|Accuracy|\n|-|-|\n|DeepSet|0.62|\n|SetTransformer|0.71|\n|FSPool|0.84|\n|UMBC Encoder|0.82|\n|Slot Set Encoder|0.79|\n|MASNET|0.85|\n\nApart from the practical usage, the hat activation was introduced was firstly as a tool to develop the TRI function, which was a key step in theoretically justifying that two-layer neural nets can be used to develop a MAS function. Hence, to prove that a simple architecture with two layers can serve as MAS function, we had to develop this new activation function.\n\n>*The introduction of parameters in the denominators in (8) could lead to numerical instability while training. Can it be avoided?*\n\nWe didn't incur too much instability during training of MASNET-Hat, where the Hat function admits the particular form in (8). We have two learnable parameters in the denominator: the support width $\\beta$ (where $\\beta> 0$) and the peak $\\gamma$ (where $\\gamma \\in (0,1)$). The way we tackled this was in the particular form of parametrizing $\\beta$ and $\\gamma$ during our training. This was done as follows:\n1. For ensuring $\\beta > 0$, we introduced an unconstrained learnable parameter $\\hat{\\beta}$ and then tried several different parametrizations of $\\beta$, as follows: \n(i) $\\beta = \\left|\\hat{\\beta}\\right|$\n(ii) $\\beta = \\hat{\\beta}^2$\n(iii) $\\beta = \\text{ELU}(\\hat{\\beta}; \\nu) + \\nu$, where $\\nu > 0$ is a hyper-parameter and $\\text{ELU}(x, a) = \\begin{cases}x, \\text{ if } x > 0; \\ a(e^x - 1), \\text{ if } x \\leq 0\n\\end{cases}$\nAmongst these choices, the third one worked best. An intuitive explanation is: training instability comes to picture when $\\beta \\to 0$. But in the third parametrization, $\\beta \\to 0 \\iff \\hat{\\beta} \\to -\\infty$, thus for most values of $\\hat{\\beta}$, we have $\\beta >> 0$. The choice of the hyperparameter $\\nu$ slightly affected the accuracy, but with no significant impact.\n\n2. For ensuring $\\gamma \\in (0,1)$, we again chose a learnable unconstrained parameter $\\hat{\\gamma}$, a hyper-parameter $\\tau$, and used the tempered-sigomid based parametrization of $\\gamma = \\text{Sigmoid}(\\tau \\cdot \\hat{\\gamma})$. Since $\\gamma \\to 0 \\iff \\hat{\\gamma} \\to -\\infty$ like before, we had a stable training since $\\gamma >> 0$ for most values of $\\hat{\\gamma}$. As observed in our experiments, the temperature hyperparameter $\\tau$ didn't affect the accuracy a lot.\n\nHere, we give a table of the avg and std (across seeds) of accuracy for different parametrizations of $\\beta$.\n\n|Parametrization type of $\\beta$|Synthetic|MSWEB|MSNBC|\n|-|-|-|-|\n|Abs value|0.97($\\pm 0.02$)|0.95($\\pm 0.03$)|0.96($\\pm 0.02$)|\n|Square|0.96($\\pm 0.03$)|0.94($\\pm 0.02$)|0.94($\\pm 0.02$)|\n|ELU|0.99($\\pm$ 0.01)|0.95($\\pm 0.02$)|0.97($\\pm 0.01$)|"}, {"review_id": "0JGpgZuP7B", "reviewer": "Reviewer_McwL", "summary": "This paper discusses modelling functions on multisets for applications such as Set Containment, and proposes a definition of Monotone-and-Separable functions on such sets. The authors prove under which conditions such functions can exist, and generalize the definition to the case of models with learnable weights. They propose a class of activation functions called 'hat functions' which enforce separability, and define a model architecture which obeys the MAS conditions. They test this architecture on a number of applications related to set containment and demonstrate slightly improved performance compared to existing methods.", "questions": "1) Is there a reason to expect that existing set models fail to obey the separability condition in enough cases to make a model like this necessary? The incremental improvement over simple set baselines makes me suspect that these methods already at least approximately obey the separability condition most of the time in practice. \n2) Why is the condition of monotonicity necessary? The set containment problem only requires separability does it not?\n3) Do you observe significant difficulties in training networks with the 'hat' activation functions? Intuitively I would expect these activation functions to perform very poorly and have significant issues with gradient flow, particularly in deeper networks. It doesn't seem overly important since you show that ReLU-based networks with multiple layers still satisfy separability, but I would expect those activation functions to be almost entirely a non-starter for less trivial cases.\n4) Am I correct in concluding that existing DeepSet models are monotone if they simply enforce non-negativity in their parameters, and separable as long as they have at least 2 layers? This seems like a very minor/incremental change from existing models.\n5) Are Set Transformers with ReLU activations and >2 layers separable? The analysis was largely focused on Deep Sets, which are a much more limited architecture.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- Paper is clearly written and easy to follow (at least for the first half)\n- Theoretical contributions are very good\n\nWeaknesses:\n- Many editing/formatting issues - definition of weak separability on page 5 is missing, Appendix links are broken, tables on page 8 and 9 are small and hard to read and interfere with text. The paper is generally quite cramped near the end and many later sections are overly short and use frequent abbreviations. The paper should likely be reorganized to allow for more room for these final sections, rather than trying to cram them in in a small amount of space.\n- Experiments are limited in scope and results do not show significant improvement over existing baselines. Some of this is fine for a theoretical work, but the results show such little improvement over Set Transformers/Deepsets that it makes me wonder if the strict MAS condition is even necessary in practice.\n- Architecture of MASNet seems incremental, with only very minor differences from DeepSets.", "was_revised": true, "final_justification": "The author's rebuttal has clarified for me that the poor experimental performance is largely due to highly unbalanced classes, and that with balanced classes the proposed model does show much more significant gains. In addition, they have provided some compelling evidence for the strengths of their model compared to the Set Transformer architecture by showing that this architecture cannot satisfy the criteria of monotonicity.\n\nI do still have some remaining concerns about the fact that a basic Deep Set model with only very slight modifications essentially satisfies all of the proposed criteria, making the novelty of the MASNet architecture limited. That being said, the authors do provide a great deal of additional analysis about alternate architecture choices such as \"hat\" activation functions and neural integrals that can be used to design more sophisticated MASNet variants, so I think it is fine to move forward. I have changed my score accordingly.", "rebuttal": "We thank the reviewer for their comments, which will improve our paper.\n\n> Why is the condition of monotonicity necessary? The set containment problem only requires separability does it not?\n\nSeparabality alone does not suffice for set containment. In a neural network setting, such problems require us to design a function $F$ such that the order between $F(S)$ and $F(T)$ can serve as boolean test for whether $S$ is a subset of $T$. For this $F$ needs to satisfy two conditions.\n\n(I)    $F(S)\\le F(T) \\implies S\\subseteq T$ \n(II)   $F(S) \\not\\le F(T) \\implies S\\not\\subseteq T$\n\nWe would like to emphasize that for high accuracy, $F$ needs to satisfy both conditions (I) and (II). \n\nSeparability alone satisfies condition (I).  Monotnicity implies  $S\\subseteq T \\implies F(S)\\le F(T)$, which is equivalent to (II).\nHence, without monotonicity, confition (II) may not be satisfied. Here, we will have $F(S) \\not\\le F(T)$ (thus predicting $S\\not\\subseteq T$) but in reality, $S$ is a subset of $T$. Hence, non-monotonicity ensures in large false negatives. \n\n\n>  *Am I correct in concluding that existing DeepSet models are monotone if they simply enforce non-negativity in their parameters, and separable as long as they have at least 2 layers?*\n\nIndeed, MASNET-ReLU can be seen as a special case of the deep sets model as it is of the form $F(S) = M _\\psi(\\sum _{x \\in S} M _\\theta(x))$. \n\nBut it's not entirely correct that to attain monotonicity, all the parameters of MASNET need to be non-negative. We choose the inner MLP $M _\\theta$ to end with a non-negative activation like $ReLU$, but the weights can be negative as well. For the outer transformation $M _\\psi$, we have chosen a non-negative function such as a neural network with non-negative weights and ReLU activation, or simply the identity. To attain weak separability we require that  $M _\\theta$ has $\\geq 2$ layers.\n\n\nThe difference in architecture appears incremental. However this required a very detailed analysis, which we built up gradually starting from Section 2. Our key contribution involves three aspects: (1) characterization of existentence of MAS functions; (2) characterization of weakly MAS function, stability and more.\n\nIt is  useful for the community to know that set containment problems can be better addressed by implementing  deepsets in the correct way. Apart from deepset,  we also provided more expressive neural formulations, which learns the activation functions automatically by trainable neural integrator (we mentioned them in appendix. If the reviewer thinks that it would highlight the contribution better, we will put it in main.)\n\n\n\n\n> *results do not show significant improvement over existing baselines*\n \n\n\nThe incremental improvement of the baselines might be misleading. One of the key reason why DeepSet and Set Transformer does well for the text and point cloud datasets lies in the distribution of classes (subset vs non-subset) our datasets. \nThe non-subset to subset ratio in the datasets for our experiments with text and point cloud was taken to be 9:1. \nDue to this data imbalance, deepSets and Set Transformers are predicting almost all pairs as non-subsets (due to the data imbalance), resulting in high false negative rate.\n\n\nThis becomes more clear when we look at the False Negative rates of the models:\n\n|Model|Bedding|Feeding|MSWEB|MSNBC|\n|-----|--|--|--|--|\n|DeepSets|1.00|1.00|0.26|0.08|\n|Set Transformer|1.00|1.00|0.67|0.90|\n|MASNET-ReLU|0.00|0.00|0.00|0.00|\n|MASNET-Hat|0.00|0.00|0.00|0.00|\n\n \n\nThe  high false negative rate of baselines are due to lack inductive bias as they do not have a built-in design of monotonicity. \nSince MASNET is equipped with the inductive bias of monotonicity, it predicts the true subsets correctly most of the time (and, all the time) in case of noisy (respectively, exact) set containment tasks. \nBy design $MASNet(S) \\leq MASNet(T) \\implies S \\subseteq T$: hence, the true subsets are never misclassified and thus the False Negative Rate is zero.\n\n\n \n\n \nHere, we present the results on synthetic data with a balanced class ratio (1:1 ratio of subsets to non-subsets). We observe that we outperform them by a large margin.\n\n|$S$-size|$T$-size|DeepSets|Set Transformer|MASNET|\n|-|-|-|-|-|\n|1|10|0.59|0.59|$\\textbf{0.99}$|\n|10|20|0.89|0.80|$\\textbf{1.00}$|\n|10|100|0.54|0.57|$\\textbf{0.98}$|\n\n \n\nFor the text datasets as well, we sepeated the experiments during the rebuttal by taking 1:1 ratio of subsets to non-subsets and re-training the baselines and MASNET on this data. We present the results in the following table to demonstrate our point.\n\n|Model|Bedding|Feeding|MSWEB|MSNBC|\n|-----|--|--|--|--|\n|DeepSets|0.62|0.68|0.84|0.81|\n|Set Transformer|0.72|0.70|0.87|0.89|\n|MASNET|$0.97$|0.96|$0.99$|$0.99$|\n\nWe observe that we outperform the baselines by a large margin.\n \n\n \n\n\n\n\n \n\n\n\n> *Are Set Transformers with ReLU activations and >2 layers separable? The analysis was largely focused on Deep Sets, which are a much more limited architecture*\n\nThe exact characaterization of conditions of separability for set transformer is extremely challenging; but we can prove it is not monotone. Therefore, it can be effectively used for set containment, as it will show high false negative rate (as shown in previous discussion too too)\n\nWe consider a set transformer model with sum pooling, namely $F(X;W _Q,W _V,W _K) = \\text{SumPool}(\\text{Attn}(X))$. Explicity, this is defined for a give multiset $X=(x _1,\\ldots,x _n)$ by first defining query, keys and values per point\n$$q _i=W _Qx _i, k _i=W _Kx _i, v _i=W _Vx _i, \\quad \\forall i=1,\\ldots,n$$\nand then taking a weighted average, defined by weights \n$$\\alpha _{i,j}=\\frac{e^{q _i\\cdot k _j}}{\\sum _s e^{q _i\\cdot k _s}} $$\nto obtain a permutation invariant function \n$$F(X;W _Q,W _V,W _K)=\\sum _{i,j}\\alpha _{i,j}v _i .$$\n\n**Lemma:** Let $V=\\mathbb{R}^d$, and let  $F: \\mathcal{P} _{\\leq \\infty}(V) \\to \\mathbb{R}^D$ be a Set Transformer defined by $F(X;W _Q,W _V,W _K) = \\text{SumPool}(\\text{Attn}(X)$, then $F$ is not a pointwise monotone function.\n\n**Proof** We need to show that there exist some parameters $W _Q,W _V,W _K$ for which the function $X\\mapsto F(X;W _Q,W _V,W _K)$ is not monotone. Choose any matrix $W _Q=W _K$ which has no kernel, and any non zero $W _V$. Choose some vector $x _1$ such that $W _Vx _1$ is non zero. By swapping $x _1$ with $-x _1$ if necessary, we can choose some index $j$ such that for $v _1=W _Vx _1$, the $j$-th index is negative $v _1[j]<0$. By assumption we also have that $q _1=k _1$ is a non-zero vector, and hence it has a positive norm. \n\nNow, let $S$ be the singleton set $S=(x _1)$, which is a subset of $T=(x _1,0 _d)$, where $0 _d$ denotes the all zero vector in $\\mathbb{R}^d$. We note that \n$$F(S;W _Q,W _V,W _K)=v _1 $$\nWhile, since $v _2,q _2,k _2$ are all zero, \n$$F(T;W _Q,W _V,W _K)=(\\alpha _{1,1}+\\alpha _{1,2})v _1.$$\nNote that \n$$\\alpha _{1,1}+\\alpha _{1,2}=\\frac{e^{\\|q _1\\|^2}}{e^{\\|q _1\\|^2}+1}+\\frac{1}{2}>1 ,$$\nand it follows that \n$$F(T;W _Q,W _V,W _K)[j]<F(S;W _Q,W _V,W _K)[j]$$\nwhich shows that this function is not monotone. This concludes the proof. \n\nIt is plausible that the set transformer model could be modified in some way,  so that it is monotone. We believe this is a good direction for future work, and we thank the reviewer for pointing it out. \n\n> *Do you observe significant difficulties in training networks with the 'hat' activation functions?*\n\nTraining  MASNET-Hat was not very difficult. For example, we refer to eq (8) of the paper, where we used a parametric version of Hat function, given by \n$$\\sigma _{\\alpha,\\beta,\\gamma}(x)=ReLU \\left( \\frac{x-\\alpha}{\\gamma \\cdot \\beta}\\right)\n+ReLU \\left( \\frac{x-(\\alpha+\\beta)}{(1-\\gamma) \\cdot \\beta}\\right)\n-ReLU \\left( \\frac{x-(\\alpha+\\gamma \\cdot \\beta)}{\\gamma \\cdot (1-\\gamma) \\cdot \\beta}\\right)$$ With appropriate parametrizations of $\\beta > 0$ such as $\\beta = ELU(\\hat{\\beta}, \\nu) + \\nu$ (ELU is the Exponential Linear Unit function, $\\hat{\\beta}$ is learnable param eter and $\\nu$ is a hyperparameter) and $\\gamma \\in (0,1)$ as $\\gamma = Sigmoid(\\hat{\\gamma} \\cdot \\tau)$, (where $\\tau$ is hyperparameter and $\\hat{\\gamma}$ is learnable) we were able to have a large enough support for our hat activations and mitigate the difficulties in training (due to poor gradient flow) to a good extent. We've made a discussion of that in lines 967-984 (Page 27) of our full paper (attached in the supplement) which we could elaborate more in the final version in case of acceptance.\n\n\n> *Editing/formatting issues*\n\n We sincerely apologize for the inadvertent errors in the current version of the manuscript. In our internal repository, the manuscript was in order; however, during the final stages of submission to OpenReview, a few hasty edits introduced these typos. In fact, during the original submission, we uploaded a version in supplementary material, which has all broken Appendix references fixed.\n\nWe would like to emphasize that these issues have already been resolved in our internal version. Unfortunately, OpenReview does not allow us to update the current submission version, but we will ensure that all such errors are fully corrected in the camera-ready version, if the paper is accepted.\n\n\nThe definition of weak-separability, which was accidentally ommitted,  is as follows:  “The parametric set function $F: P _{\\leq \\infty}(V) \\times \\mathcal{W} \\to \\mathbb{R}^m$ is weakly separable if, given any $S, T \\subseteq V$ such that $S \\not \\subseteq T$, there exists a parameter $w \\in \\mathcal{W}$ such that $F(S; w) \\not \\le F(T; w)$”. This essentially means that at least some point in the parameter space separates two non-subsets."}]

Author rebuttal:

Meta-review: This work focuses on developing neural network models suited for multiset containment tasks. The paper first defines a class of set functions that the authors refer to as 'monotone and separable' (MAS). The paper then provides bounds on the embedding dimensions required for MAS functions, as a function of the cardinality of the multisets and the underlying ground set. No such functions exist in the case of an infinite ground set. The paper then proposes MASNET, a model which satisfies a weak MAS property and is stable. Experiments demonstrate that the MASNET model outperforms standard baseline models on set containment tasks.

The reviewers agreed that the paper's main strength is its theoretical contributions. In particular, the theoretical results presented in the paper appear to be non-trivial and potentially impactful. Incorporating set containment as an inductive bias can be useful for various set learning tasks. The reviewers raised concerns about the empirical evaluation of the proposed models which only focuses on multiset containment tasks and ignores other common tasks such as point cloud classification and text concept set retrieval, about the marginal improvements offered by the proposed models, about the lack of motivation for MAS, and about missing related works. The reviewers also complained about various formatting issues. Moreover, one reviewer raised concerns about the novelty of the proposed architecture since a MASNET-ReLU model can be seen as a special case of DeepSets.

The authors claimed in the response that the formatting issues have already been resolved in their internal version of the manuscript. They also argued that it is useful to know how to implement DeepSets in the context of set containment problems. In addition, the authors attributed the marginal improvements to the distribution of classes in the considered datasets. Moreover, during the rebuttal, the authors conducted additional experiments on image classification and text retrieval. The reported results seem promising. The authors also experimented with larger set sizes and conducted experiments to highlight the need for Hat activation functions.

It is also my view that the theoretical contributions presented in the paper are original and solid. However, I also believe that the paper would benefit from a more extensive empirical evaluation of the proposed method. The additional experiments conducted during the rebuttal go in the right direction and should be incorporated into the manuscript. I also suggest the authors provide explanations regarding the marginal improvements and discuss whether the MAS condition is even necessary in practical applications. To summarize, even though the empirical results are somewhat limited, the theoretical contributions are sufficient to recommend acceptance. I strongly encourage the authors to revise the paper and improve the writing taking into account the detailed comments in the reviews.
Decision: Accept (poster)