Extended Deep Submodular Functions
Authors: Seyed Mohammad Hosseini
Arash Jamshidi
Seyed Mahdi Noormousavi
Mahdi Siavoshani
Naeimeh Omidvar
Venue: Accepted by TMLR ()

Abstract: We introduce a novel representation of monotone set functions called Extended Deep Submodular functions (EDSFs), which are neural network-representable. EDSFs serve as an extension of Deep Submodular Functions (DSFs), inheriting crucial properties from DSFs while addressing innate limitations. It is known that DSFs can represent a limiting subset of submodular functions. In contrast, we establish that EDSFs possess the capability to represent all monotone submodular functions, a notable enhancement compared to DSFs. Furthermore, our findings demonstrate that EDSFs can represent any monotone set function, indicating the family of EDSFs is equivalent to the family of all monotone set functions. Additionally, we prove that EDSFs maintain the concavity inherent in DSFs when the components of the input vector are non-negative real numbers—an essential feature in certain combinatorial optimization problems. Through extensive experiments, we demonstrate that EDSFs exhibit significantly lower empirical generalization error in representing and learning coverage and cut functions compared to existing baselines, such as DSFs, Deep Sets, and Set Transformers.

Extended Deep Submodular Functions
Scyed Mohammad Hosscini*
semo.hosseeiiissaarii.eee
Deportment of Computer Engineering
Sharif University of Technology
Arash Jamshidi*
aruskjjmshhiidishaafff..
Department of Computer Engineering
Sharif University of Technology
Seyed Mahdi Noormousavi
Deportment of Computer Engineering
Shorif University of Technology
Mahdi Jafari Siavoshani
mjjafari@shariff.de
Deportment of Computer Engineering Shorif University of Technology
Nacimeh Omidvar
n. w...o.oiivarre @wwidvr@@gmaalllcommmmmmmmmmmmom com
Tehran Institute for Advonced Studies (TEIASS) Khatam Universily, Tehran, Iran
Reviewed on OpenReview: https: openreview. net/ forum? id= qozuusn9922
Equal contribution
Abstract
We introduce a novel representation of monotone functions called Extended Deep Sub- modular functions (EDSFs), which neural network-representable. EDSFs serve extension of Deep Submodular Functions (DSFs), inheriting crucial properties from DSFs while addressing innate limitations. It is known that DSFs can represent limiting subset of submodular functions. In contrast, we establish that EDSFs possess the capability to represent all monotone submodular functions, a notable enhancement compared to DSFs. Furthermore, our findings demonstrate that EDSIs can represent any monotone set function, indicating the family of EDSFF is equivalent the family of all monotone set functions, Additionally, prove that EDSFs maintain the concavity inherent in DSFs when the com- ponents of the input vector non-negative real numbers- an essential feature in certain combinatorial optimization problems. Through extensive experiments, EDSFs exhibit significantly lower empirical generalization error in representing and learning coverage and cut functions compared to cxisting basclines, such as DSFs, Deep Sets, and Set Transformers.
demonstrate that
1 Introduction
Submodular functions have found extensive applications in various fields of study, including modeling influence in social networks Kempe et al. 22003). energy functions in probabilistic models Gillenwater al. (2012),
and clustering Narasimhan et al. (2005) In particular in economics, a wide range of scenarios incorporate
the concept of diminishing marginal return, where acquiring more goods results in diminishing the overall
satisfaction or the so-called "utility" McLaughlin & Chernew (2001) Kimball et al. (2024).
There are several challenges associated with the widespread use of these functions recent machine learning applications. To improve the modeling of submodular functions in these applications, efforts have been made to represent submodular functions using differentiable functions, such neural networks. This representation

---

enables the solution of key submodular optimization problems through the utilization of gradient-based methods and convex optimization. To illustrate this, suppose we want to maximize submodular function f under certain constraints. In the exhaustive-search approach, we would have to check all 2" subsets, which is exponential in the size of the ground set S. However, with a differentiable representation of f. we can utilize first-order information of the function, such as gradients, and project onto the constraint set. to solve the optimization problem more efficiently.
There have been previous efforts represent submodular functions using neural networks. For instance, in Bilmes & Bai (0017), the authors introduced a neural network architecture called Deep Submodular Functions (DSFs), consisting of feedforward layers with non-negative weights and normalized non-decreasing concave activation functions. Functions in this class exhibit interesting properties, such as the concavity of the function when the components of the input vector are all non-negative real numbers. By increasing the number of layers in the DSFs architecture, the family expands, indicating that there are functions in DSFs with n n+11 1 layers that are not present in DSFs with layers. However, as stated by the authors, DSFs cannot represent all monotone submodular functions, which highly restricts their applicability to many machine learning problems.
In this paper, we introduce a novel neural network architecture, called Extended Deep Submodular Functions (EDSFss, which not only have the capability to represent any monotone submodular functions but can also represent any monotone set functions. Moreover, same as in DSFs, when the components of the input vector are all non-negative real numbers, EDSF' are concave, an important feature applicable in various combinatorial optimization settings. In addition, our experiments demonstrate that EDSFs are able to learn one of the most complicated monotone submodular functions, i.e., coverage functions, with signíficantly lower empirical generalization error compared to DSFs, We define EDSFs as the minimun of r DSFs. Although in our proofs, exponential number of DSFs are needed to represent any monotone submodular function, in our experiments we observed that we can learn coverage functions and monotone cut functions using much fewer D The rest of the paper is organized as follows: In Section 2, we formally define DSFs and state some of their important properties. In Section 3, we introduce our augmented architecture to represent all monotone (submodular) set functions and provide proof. In Scction 4, we demonstrate the superior performance of EDSF's in learning coverage functions through numerical evaluations.
1.1
Related Works
The exploration of neural networks for modeling submodular functions is relatively sparse in the existing literature. A notable contribution is the introduction of DSFs Bilmes & Bai (017): Dolhansky & Bilmes (2016). Building on this work, the authors in Bai et al. (2018) address the maximization of DSFs under matroid constraints, using gradient-based methods to solve the optimization problem. Their work provides theoretical guarantees, establishing a suitable approximation factor given the problem's constraints. More recently, a novel architectural approach has been proposed in De & Chakrabarti (2022), which not only preserves submodularity but also exlends its applicability to more generalized Torm, accommodating a-submodular functions. This signifies notable vancemeett in the landscape of neural network-based modeling of submodular functions, expanding the scope of potential applications and providing a platform for exploring more muanced and versatile representations within this domain. There are other works that attempt to represent monotone set functions using neural networks. For example, in Weissteiner et al. 2021 the authors introduce a neural network architecture that represents all monotone set functions and explore their use in designing auctions.
Authors in Zaheer et al. (017)) introduces Deepsets, method for learning permutation-invarinn set functions, offering a flexible architecture that can handle set-based tasks. While their work provides a powerful way to model general set functions, they do not explicitly address the estimation of submodular functions, which require handling the diminishing returns property. This limits its direct applicability to submodular function estimation, as their focus is more on tasks like point cloud classification and set expansion rather than optimizing or estimating submodular structures. Inspired by this work, Lee et al. 2019 introduces the Set. All of the codes associated with experiments are available at
2

---

Transformer, an attention-based neural network architecture designed for processing set-structured data. While the authors demonstrate its effectiveness on various set-input tasks, its performance was not specifically evaluated on estimating set functions such as submodular functions. [Wagstaff et al. (2019) talks more about the thcorctical side of works like Deepsets and Set Transformer, providing insights into the limitations of representing permulalion-invarian functions on sets. While their work doesn't 'l. specifically address submodular functions, provides a general framework for understanding the representational power of neural networks on set-structured data. However, their focus is primarily on theoretical limitations rather than practical algorithms for learning specific classes of set functions, leaving open questions about how these insights translate to the efficient learning of submodular functions in particular.
One of the works related to learning general submodular functions is Feldman & Vondrák (2016). The authors prove tight bounds on approximating submodular functions by juntas, showing that any submodular function can be e-approximated by an ( log ) Although their work gives a good insight. into learning submodular functions, it mainly focuses on the thcoretical existence of these estimators and doesn't fully provide a practical way of learning them. The authors in Balcan & Harvey (2018) investigate submodular functions from learning theory perspective, developing algorithms for learning these functions and establishing lower bounds on their learnability. Morcover, the authors in Feldman & Kothari (014)
attempt to approximate and learn coverage functions in polynomial time.
There are some works that talk about the combinatorial and submodular optimization. For example, Sakaue (202)) introduces a differentiable version of the greedy algorithm for monotone submodular maximization called Smoothed Greedy. One of the strengths of this work is that it maintains theoretical guarantees similar to the original greedy algorithm Vondrak (2008) while enabling gradient-based learning. However, they work doesn't directly address the estimation of submodular functions and only focusing maximizing (given) single submodular function. In our work we aim to estimate any given submodular function and use this estimation for downstream tasks related to submodular maximization such as social welfare maximization, in anothor work, Wilder et al. (2019) introduces a framework called 'decision-focused learning' that aims to bridge the gap between predictive models and combinatorial oplimization. Their approach involves end-to-end training of machine learning models to directly optimize decision quality, rather than prediction accuracy. However, in their work, the target function can be described by an unknown parameter and the aim is to perform optimization and learning together, whereas work aims to learn the submodular function itself from data.
Lin & Bilmes 2012 introduces the concept of submodular shell mixtures for learning submodular functions in a structured prediction setting. While proposed method achieves strong results in document summarization, it reliance on predefined shell and approximate inference may restrict the class of learnable functions. These limitations highlight the ongoing challenges in developing versatile methods for learning submodular functions.
2
Background
For a ground set S, any function 25 R is referred to as set function. Below, we present the definitions of essential concepts needed for the remainder of the discussion.
Definition 2.1. (Monotone Set Function) A set function f 2 - RR+ called monotone set function if for any A C B C we have,
f(A) S fB).
(1)
Definition 2.2. (Normalized Set Function) A set function f: 2 - I is called a normalized set function if we have,
f(0) =
(2)
Definition 2.3. (Modular Function) A function m 2 + RR+ is called a modular function if we have,
VACS: :A() Σ m(a).
(3)
Now, we can formally define submodular functions follows.
3

---

Definition 2.4. (Submodular Function) A function f : R, where S is a finite set, is submodular if for any A _ B g S and u $ B, we have,
f(Aue) - f(A) f(BU))-
(4)
In the remainder of the paper, without loss of gencrality, we will focus on normalizod monotone set act/subooullar functions. If the function is not normalized, we can simply subtract the value of f(0) from the function so as to make normalized. Note that this transformation also maintains the submodularity of the function.
Definition 2.5. (Sum of Concave Composed with Modular Functions Bilmes Bai (017 Assume a finite
set S (nodes or input features) with cardinality n. Given set of m, m.g..... my (m, 2 + +)+) modular functions and Φ1, 022 ..., ... du (oi: R+ + R being their corresponding non-negative, non-decreasing, normalized (i.e., (0) 0, vi), concave functions, and arbitrary modular function m :25 - R, the
SCMM, : 2 - IR, derived by these functions is defined as,
k
2(A) = Σ (m(m((A)) + (A).
55)
In the rest of the paper, since we only consider the monotone set functions, we pull our attention into "monotone" SCMMs, which the range of modular functions is only the positive real values, namely, my : 25 + R+
Basod upon recent developments, has been discovered that the aforementioned functions given in Equation exhibit inherent submodular characteristies Bilmes & Bail (017)). Looking ahead, we can view these functions single-layer neural networks equipped with nonlinear activation functions that exhibit concavity properties, similar to linear mixture of inputs followed by stepwise activation function such ReLU (Rectified Linear Unit) after computing the overall output values.
By employing this insight, we can expand the horizons of submodular functions by leveraging them across multiple tiers. We now introduce a pivotal concept that facilitates the utilization of advanced artificial intelligence tools, specifically deep learning.
Definition 2.6. (Deep Submodular Function Bilmes & Bai 2017 P. Assume we intend to define L (i.e., depth of the network) layer DSF. If L 1 we use an SCMM (without last summation). Therefore, in this case we have single-layer x & network (with non-negative weights) with submodular outputs. For -=1> 1 we first assune the output of / layers a given n x k DSF. Let's denote the output nodes of the given DSF by B = {41, ....... ppk).
Now we want to add one layer at the end of the given DSF. We append a k X m fully connected layer with non-negative weights and corresponding normalized non-decreasing concave functions Φ1, 02.02.... .......,. &m for each newly added node. Then we define the outputs of the network as C (v/1, 8/2, ..., (m)
Vo E C. the = dv
Σ WuriPa ME(M]
bw:
and by E R is a bias parameter of the node. In this scheme, we have new layer added to the DSF. Therefore, we introduced a n x m DSF with L = layers. As an example, a 3-layer DSF is shown in Figure
With this understanding, one can guarantee that the outcome of this architecture forms a submodular function, as it is shown in Bilmes & Bai (2017). An established finding rogarding SCMMs states that any SCMM employing an arbitrary activation function can be represented as a two-layer SCMM with only the min activation function Bilmes & Bai 2017
Despite these findings, there cxist notable limitations when it comes to DSFs. While DSFs possess a range of capabilities, they are unable to encompass all submodular functions. This implies that there will always be submodular functions that cannot be represented using any number of layers in DSFs Bilmes & Bai (017)) To address this limitation, in Section 3 we extend DSH's by adding limited number of components in the network architecture to represent all submodular functions.
Here, only focus the monotone DSFs so we have omitted the modular in the original definition of DSFs
4

---

s
me
d2
mk
Figure 1: SCMM Architecture. Input vector of the network is a 0-1 vector representing the corresponding subset of the ground set S.
27'
Figure 2: Polymatroid corresponding to the example function with a ground set of size 2.
In the following, we point out certain fundamental concepts in combinatorial optimization that will be employed throughout the remainder of the paper. We commence with an exploration of polymatroids.
Definition 2.7. (Polymatroid) Consider a finite set S with |.|] = and a submodular function f: - E defined on S. A polymatroid corresponding to denoted by Py, defined as,
Py (x E R AAC x(AA) $ f(4) x 0}.
(7)
where x(A) EiEA Zz.
Example 2.8. As an example of polymatroids, we can consider the set function f 2(1,) - I where [((1)) = 10, f((2)) = 8, and /([1,2)) 12. which the corresponding polymatroid is shown in Figure
The following lemma describes an important property of the polymatroids corresponding submodular functions.
5

---

1
2
3
4
Figure 3: Example of coverage function with universe size 10, ground set of size 4, and with uniform weight of 1.
Lemma 2.9. (Goemans el al. (2009) For polymatroid Py corresponding to monolone submodular function f, we have
VACS:fOM
sup x(A). xEP,
(8)
We also define the following important submodular problem which we need later in our experiments.
Definition 2.10. (Submodular Welfare Maximization) For a collection of n users with U1 ......, Un 2 R their (estimated) submodular valuation functions on each subset of the finite set S with |S| 8, the submodular welfare maximization problem aims to maximize the social welfare function, i.e., the sum of all valuation functions when we partitioned set of items S and assigned to the users, and is formally defined
n
Σ vsS)),
maxx
S
s.t. S, S.
(9)
US.=S. S, Vi 0..
Moreover, for any partition (Si, S2, .,..... Sn) of the ground to users, define its efficiency as,
Ef((A) E.v(S))
(10)
where OPT = (Si, S 3 the optimal partition.
Furthermore, in experimental results, we will employ Coverage Functions, defined as follows.
Definition 2.11. (Coverage Function) A function e: 2(x) - R is a coverage function, if there exists a universe with non-negative weights w(u) for each u E U and subsets A,, A2...., U such that for any B [n] we have c(B) Eveuien,, w(u).
Erample 2.12. As example of the coverage function, for ground set of size 4, we illustrate the coverage function with universe size 10 and with uniform weight of 1 for all of the elements in the Figure In this example we have f(11,3)) = 7 and f(3,4)) 8.
Alternatively, coverage functions can be described as non-nogative linear combinations monotone disjunc- tions. There are a natural subclass of submodular functions and arise in number of applications Feldman & Kothari (0044.

---

3 Extended Deep Submodular Functions
3.1 Architecture Definition
Formally, we define Extended Deep Submodular Function as follows. Definition 3.1. A set function an EDSF if it can be represented as the minimum of Deep Submodular Functions f1, f where is an arbitary number, namely, A
h(A) min
(11)
....
In the rest of this section, we aim to demonstrate that we can represent any monotone submodular function I using some 9 E EDSFs. The idea behind the proof to leverage the relationship between the minimum of submodular functions and the intersection of their polymatroids. The main result of this paper summarized in the following theorem.
Theorem 3.2. Family of monotone set functions is exactly equal to the family of Extended Deep Submodular functions (EDSFs).
In the following, we will go to prove this result step by step. First, we assume that submodular function f 2 R is given. For convenience, use these notations to simplify discussion. Definition 3.3. We define:
1. CΛ = f(A), and for all E S we denote Cj f((i)).
2. polytope LA for all A C S
LA fx R" : 2 0, x(A) S CA, Vj & A: S 5h..
(12)
3. for any A C S and B C S the submodular function
gA(B) min
Σ
Wjs CA
Σ
Wk:
(13)
JEAnB
REBYA
where wy = ca for any j E A and wy ej for any j & A, and wy represents the corresponding weight of some neural network.
Using these definitions, in the first step, we will show that each IΛ can be represented using simply two-layer DSF.
Lemma 3.4. For any A S, we can design a two-lager DSF that represents the gA function, therefore the 9A function a submodular function.
Proof. To represent the function d4 using DSF, we have constructed a network architecture as illustrated in Figure 4 This architecture comprises only two layers. The first layer contains two nodes, one of which employs the minimum function its activation layer. The second layer consists of single output node responsible for computing the sum of the inputs.
All edges connected to the lower node possess a weight of ca. Conversely, each edge linked to the upper node bears a weight corresponding to the value cj specifically f()) according to the definition.
In this manner, we have introduced the network as two-layer DSF
(B) min
Σ JEAnB
WjsCA
+ Σ Wk
(14)
KEBYA
With this, we conclude our proof.
We next introduce useful lemma.
7

---

Cj1
s
CAA
+
mint..eal
A
AA
Figure The simple architecture for the representation gA as a DSF. The imput of the network is a 0-1 vector corresponding to the subset B. The subset B could have non-emply intersection with subset. A = {a....., } and S A (
Lemma 3.5. For any A C S, have
Pa* LA-
(15)
Proof. To show the equality of two aforementioned sets, we first show Pas S LAs then we show LA S PgA which completes the proof.
For the first part, for any E PAAA have for all B S, x(B) S (B),, therefore, for any B C A, we have x(B) S CA. in fact in this scenario (BB 0 or CA, that implies x(A) S ca. Furthermore, for any & A we have Iÿ I f()) Cj- Therefore, cach point in the polymatroid has the conditions to be in the LA. that means, x E LA-
For the reverse part, for any x E LA, we have x(A) I CA. which implies that YB S A, 0, x(B) CA = gA (B). For any onc-member subset of S, for example {f).j & A we have 2j S cg = (B). Furthermore, for any arbitrary B C S, could write = (An B) U (B A). We have two cases,
1. (An
x(B)
Σ
Σ JEBIA
9 9
JEBYA
2. (AnB) # 0
x(B) CA Σ
24 CAt Σ c; gA(B).
JEBIA
JEBIA
It shows that for all B C S we have: x(B) S (A = X Pox- Therefore, the second part is now obvious, namely, LA C P Hence,
Pas C CLA
P
(16)
(LAS C
8

---

which completes the proof.
For the next step, we introduce the next lemma. Lemma 3.6. For a given submodular function f, we have:
n AÇS
LA = Ps-
(17)
Proof. Similar to the proof of Lemma 3.5
we first show that Nags LA S Py, then we will prove Py S
Nags LA-
For the first part, for any Naçs LA we have VACS:XEL,
((A XEPs.
(18)
Therefore, we have shown that NAcS LA _ Py. For the reverse direction, for any x E Py, we can write
x(A) S f(A) = CA
VACS =
XELA.
(19)
Vij & A : [((i) =
Therefore, we have shown that Py S Nags LA- Combining these two parts completes our proof, namely, we have shown that Nags LA LA= = Py.
For the next step, we need to present the following lemma.
Lemma 3.7. For given set f2..2.... fr of submodular functions, if the function h = min(f1, f2..... ... f is submodulor, for the polymalroid of the function h we have
Ph
n Pjr
(20)
1...
Proof. To prove the lemma we proceed as follows.
x E + AA C S: x(A) S $M(A)
YASS vi: x(A) & f((A)
Vi:XE Ps = x
Pko
In the next step, we introduce new component the DSF architecture to maintain the polymatroid corresponding to the output function to be the intersection of the polymatroids corresponding to the input functions. The proposed component is called Min- Cii--Component, as defined below.
Definition 3.8. it brings the minimum of the inputs as the output of the node.
A Min- Min-Component in the neural network, is component (node) in which
Incorporating this component into DSF, enhances its capability of representing submodular functions effectively.
In general, note that the min operator does not maintain the submodularity of the input functions. However, during the proof of the Theorem 3.9 we have used some techniques to assure that the output function would be submodular, as it can be seen in the following.
Moving towards the last stage, we present an architecture that is built upon the provided submodular function. In the initial layers, for any subset A, S S, we have crafted the functions IA. using the architecture outlined in Figure 4 Subsequently, we applied min-component all of these constructed gA, functions, resulting in composite function denoted as g. Therefore, the corresponding EDSF is generated.
9

---

In the following theoren function f.
establish that the function can preciscly represents the original submodular
Theorem 3.9. Let M (A1, (A1,A2; A2,... ...... A2" = 2 represents all of the subsels of ground set S. The function 9 min(gA, .............. 9A2m exactly represents the function f. In other words
VACS: :(A)) f(A).
(21)
Proof. Utilizing lemmas 3.5 is precisely identical to the polymatroid of the function f: Pg = Py- However, it's worth noting that the function may belong to a broader category of functions than just submodular functions.
3.6 and 3.7
deduce that the polymatroid associated with the function g
Based on lemma 2.9 we know that there exists some x* such that x" = argmax x(A) and x" (A) = f(A).
xEP,
Now suppose that J(A) > ((A). We can write
x XPEP=PP = P x*(A) = f(A)
x" (A) f(A) g(A)
= x Pg = x* $ Ps.
(22)
That a contradiction, so for any set. C S we have g 2 S(A).
Furthermore, write
((A)) min (gn(A)}
g(A) - f(A).
(23)
(A(AA = CA = f(A)
Combining these two results, is clear that for any A S have g(A) f(A).
Up to here, we have proved that all the monotone submodular functions can be represented by EDSF function. In the remaining of this section, we will prove that this result also holds for the family of all monotone set functions.
Lemma 3.10. For any EDSF function f, f is monotone.
Proof. The proof is straightforward, as all the weights used in construction of any EDSF is non-negative (all the constructing DSFs are monotone). All other functions that used in the construction any EDSF such as min function are all monotone functions.
Next prove the final result.
Theorem 3.11. For any monotone set function f, there erists an EDSF g, such that f g.
Proof. Consider any monotone set function f. For any B BCS. S we define ga follows
gn(A) = min
Σ
f(B).
+ Σ w"
(24)
JEABB
REAAB
where w² = F(S), which is the maximum value function f can take (because f is monotone). Now we define function g as follows:
0(4) = min [gb(A)}
(25)
BCS
Moreover, in the review process, simpler proof was also suggested by the anonymous reviewer, which for the sake completeness have been presented in Appendix
Refer Remark 5.2 more discussion about Theorem 3.9
10

---

that (D(A) f(A) if = A. Now suppose B F A. If A B 0, (B) f(S) 2 ((A), because of monotonicity. On the other hand if A B = 0 we know that A C B. In this case we have (B(A) = f(B)= 2 f(A) because of monotonicity. Hence we can see that (A) S (B(A) for any B S S. Therefore, g(A) = f(A) for all A S.
For any A S S we
Based on the above results, we can conclude Theorem 3.2
Although in our proofs we use exponential (number of DSFs), we observe in our experiments that in practice using much fewer DSFs is sufficient to learn coverage and monotone cut functions effectively.
3.2 Concavity of EDSFs
We can also show that any E EDSF's is concave, if the input vector components are all non-negative real numbers, as stated in the following theorem.
Theorem 3.12.
Given g E EDSFs,, g is a concave function with respect to the inpua vector, if the inpul vector components are all non-negative real numbers.
Proof. Since all the DSF functions are concave in this sctting Bai et al. (2018) (See Corollary 1), and g is the minimum of a number of DSFs and we know that minimum of concave functions are concave, we can conclude that g is also concave.
We can exploit the above-mentioned property to solve certain combinatorial optimization problems, such the social welfare maximization problem, using gradient-based methods in an efficient manner. This provides a powerful tool to handle some combinatorial problems. Applications in this context are discussed in Section
4 Experimental Results
In the following section, showcase series of experiments aimed to demonstrating the positive outcomes and advantages derived from the application of Extended Deep Submodular Functions (EDSFF) in the modcling of submodular functions. Additionally, we highlight their efficacy in efficiently addressing and solving various combinatorial optimization problems. Through these experiments, we aim to provide a clear and comprehensive understanding of how EDSFs contribute to improved outcomes in the domain of submodular function modeling and the optimization of complex combinatorial scenarios.
4.1 Learning Coverage Functions
As outlined in Section 2 coverage functions constitute crucial and intricate subset of monotone submodular functions, posing challenges in accurate learning from their instances.
Our experimental findings indicate that, in contrast to Deep Submodular Functions (DSFs), Extended Deep Submodular Functions (EDSFs) shown to be effective in efficiently learning these complex functions, exhibiting much lower empirical generalization error, compared to DSFs.
To perform our experiments, from each coverage function (defined in Definition 2.11 we generate random dataset D = (X,, y where X, is a random subset from the ground set S. and yi is the value of the coverage function. To create a coverage function for our experiments, we define the universe size, the number of items (subsets), and the probability that each element in the universe independently belongs to each subset. Additionally, the weights in the coverage function are kept constant with value of 1. For each experiment generate dataset, allocating 80% for training and 20% for testing.
The learning setup for all experiments in this section is the same. The optimizer used is Adam with a learning rate of 0.01. Each model is trained on a dataset of 1024 samples for 10,000 epochs. The employed
Note that in all the problems described later the paper, set function involved where the input determined by binary vector. Therefore, Theorem 3.12 can be applied.
11

---

cost function is the L1-loss function. Additionally, the weights for all EDSF and DSF neural networks are initialized using a Gaussian distribution with mean of 0 and a variance of 0.01
In our first experiment, both an EDSF and DSF were trained to learn coverage function with universe size 100, 16 subsets (items), and probability of 0.2. The architectures of the EDSF and DSF are quite similar, with the main difference being the min-component at the end of the EDSF. Fach model consists of three fully-connected layers with 64 neurons, using 6(x) min(a, x)) (a minimum linear unit) the activation function, where baselines, including the methods of Zaheer et al. (2017) and Lee et al. (2019), in learning the target coverage function. The neural networks were trained using the sctup described above. Table 1 presents the train and test losses for each model, showing the mean and standard deviation across 20 runs. As shown, the EDSF demonstrates a significant improvement over the other baselines.
95. Additionally,
compared the performance of EDSF against other
Learning Coverage Function Experiment
EDSF
DSF
Train
Test
Train
Test
mcan
std
mcan
std
mcan
std
mcan
std
1.239
0.162
1.344
0.192
34.108
0.786
34.252
1.156
Deep Sets
Set Transformer
Train
Test
Train
Test
mean
std
mean
std
std
mean
std
17.916
0.717
17.525
1.429
18.045
0.590
17.617
1.273
Table 1: Learning coverage function with universe size of 100, probability 0.2, and 16 items. The optimizer is Adam and learning rate is 0.01, using L1-Loss function to optimize. Experiments conducted on EDSF, DSF, Deep Sets, and Set Transformers. The value of L1-Loss function at the end of training and testing reported.
Additionally, the loss functions and outputs of the EDSF's and DSFs in learning coverage functions are shown in Appendix A Figures 5 10 As observed, the DSI' were unsuccessful in these scenarios, with outputs remaining constant-likee likely due to the complexity of the coverage function. In contrast, the EDSFs demonstrated robust generalization, closely following the pattern of the target coverage function with low error, thus showcasing their superior performance in this experimental context.
Building on our first experiment, we tested various architectures for DSFs, and the training results were significantly worse than the above EDSF's results, as shown below:
1. 5 hidden layers with 64 neurons each, alpha set to 95: test loss is 84.3058
4 hidden layers with 64 neurons each, alpha set 125: test loss is 84.7727
5 hidden layers with respectively 32, 64, 128, 64, and 32 neurons, alpha set to 400: test loss is 81.4188
These experimental results demonstrate the superiority of EDSF compared to DSF in learning the coverage functions. Additional DSF architectures (including larger ones) were also tested, and the corresponding plots are presented in Appendix A Figures and
At the end of our first set of experiments, we conducted additional tests to examine the effects of various activation functions on the performance of DSF' during training. We tested three activation functions:
1. a(x) = log(1 + x)
2. a(x) tanh(x:)
3. a(x) σ (x) 0.5
The resulting plots for the loss functions, training, and testing performance are provided in Appendix A
Figures 13 15 As shown, none of these activation functions improved DSF performance in learning the
12

---

coverage function. Additionally, as discussed in Section 5 Remark 5.4 the only effective activation function for training EDSFs is MiL.U, while none of these activation functions performed well when learning the coverage function with EDSEs.
In our second experiment, we tested different values of r, the number of DSFs used before the min function, to examine the effect of the EDSF network size on the generalization error of the training. The target function is a coverage function with a universe size of 500, 16 items, and a probability of 0.2. All experimental setups are the same in our first experiment, with the only difference being the last layer, which now reflects the value of meaning that EDSF has 4 layers with 64, 64, 64, and neurons, respectively, Table 2 presents the test loss for various values of r, showing the mean and standard deviation across 20 runs.
Further details about all the experiments can be found in Appendix
Test
Loss
mean
std
88.587
7.308
86.664
4.614
88.499
5.915
87.759
5.305
16
87.236
6.02
32
3.693
0.539
64
4.332
0.695
128
4.633
1.136
256
4.899
2.091
512
7.674
3. 3.708
1024
10.291
6.826
Table 2: Experiments for various size of EDSF in learning coverage functions. Here, r is the number of DSF functions used in constructing the EDSF. The ground truth is coverage function with universe size 500, 16 items, and probability 0.2. The architecure of this experiment is same Table ! with only difference in the last layer, showing value of r. The optimizer and learning rate used for each experience was, Adam and 0.01 respectively.
4.2 Learning Cut Functions
We conducted several experiments to learn modified graph cut functions (we choose modified version to maintain the monotonicity), which is a well-known submodular function. Firstly, we generated the random graph using Erdos-Renge model (with probability 0.2 and 50 vertices), then, for any set of vertices X, we considered the function f(X) jeut(X)] + E,ex deg(a) which is monotone submodular function.
The architecture used to train the EDSF on the data is identical to the one used for learning coverage functions. It consists of three fully-comnected layers with 64 neurons, each using Φ(z) = min(a, x) (a minimum linear unit) as the activation function, where a 95. In the last layer, we incorporated a min-component with r= 64.
Similar to the coverage function experiment, we employed DSF, Deep Scts, and Set Transformer to learn the cut function and compare their performance with our proposed EDSF. The DSF used in this experiment is identical to that used for learning coverage functions, consisting of three layers with 64 neurons each, except for the alpha parameter, which is set to 450. For training our network, we used the Adam optimizer with a learning rate of 0.01, employed the L1-loss function as our cost function, and trained each network for 10,000 epochs. Additionally, the weights for the neural networks were initialized using a Gaussian distribution with a mean of 0 and a variance of 0.01. Table 3 presents the train and test losses for each model, showing the mean and standard deviation across 20 runs
Further figures and details about the experiments can be found in Appendix B
13

---

Learning Cut Function Experiment
EDSF
DSF
Train
Test
Train
Test
mcan
std
mcan
std
mcan
std
mcan
std
4.783
0.720
4.912
0.704
121.319
6. 6.187
121.309
9.853
Deep
Sets
Set Transformer
Train
Test
Train
Test
mean
std
mean
std
mean
std
mean
std
121.352
6.191
121.123
9.888
142.616
64.956
157.843
109.829
Table 3: Learning a cut function generated by the Brdos-Reny' model with probability 0.2 and having 50 verticos. The optimizer is Adam and learning rate is 0.01, using L1-Loss function to optimize. Experiments conducted on EDSF, DSF, Deep Sets, and Set Transformers. The value of L1-Loss function at the end of training and testing reported.
4.3 Social Welfare Maximization
In these experiments, we leveraged the previously discussed concave property inherent in EDSF's to address the widely recognized combinatorial optimization problem of maximizing social welfare, as delineated in Section 2 In this specific context, each of the valuation functions, denoted vn; -2,--.. Uny is assumed to be EDSF or DSF, acquired through learning from samples collected from users. Our optimization problem, expressed in Equation g can be reformulated as follows,
max SW Σ v((a)),
8.l.
Σ
dij 1, for all jE S,
im1
0ij 10.1}.
(26)
where is m matrix, such that dij E 10, meaning if item j assigned to user i and ag represents the i'th row of a, which is the items that were assigned to user i.
To solve this optimization problem, first we relax it to the following form,
SW(a) Σ va(a))
max
s.f. Σ Gij
for all jE S,
iml
E 10.
(27)
As we mentioned, each of the us's are EDSF or DSF, so they are concave, hence, the relaxed problem is clearly a convex problem, e.g., maximizing a concave function with convex constraints, and can be solved using convex optimization techniques such as projected gradient ascent. The projection step consists m distinct. projections on probability simplex for each item. The algorithm pseudo-code is shown in Algorithm [
In this set of experiments, assume there are users (bidders), each with coverage function their true submodular valuation function. Subsequently, our network is trained to learn each bidder's valuation function. Based on these learned networks, gradient ascent is then used to find semi-optimal allocation that maximizes social welfare. Finally, the estimated social welfare is calculated based on this maximizing allocation with the true valuation functions.
The learning setup for all the experiments in this section the same. The optimizer is Adam with a learning rate of 0.01. Each model is trained with dataset of size 64 for 10,000 epochs. The employed cost function
14

---

Algorithm 1 Gradient Ascent
Input: valuation functions v1, .2..... Un, set of items S (IS) s), learning rate 1 Initialize = (0), Project each column of on the probability simplex
repeat
Compute gradient of SW function in the point a = E: asw.
a a= a 7-9 Project each column of on the probability simplex
until convergence
for i in 8 do
Select the user assigned to item by sampling from i'th column of (corresponding distribution for item i). end for
is the Li-loss function. Additionally, the weights for all neural networks are initialized with a Gaussian distribution with mean of and variance of 0.01. Finally, for the gradient ascent part, the learning rate (n) is 0.001.
For our first experiment, we assume that the coverage function for each bidder has universe size of 60 and 8 items. However, the coverage probabilities are 0.1, 0.3, and 0.5 for the three bidders, respectively. The learning model is an EDSF with layers of 64 neurons, using MiLU with a = 95 as its activation function. Three neural networks are trained, one for each bidder, following the learning setup described above. Table shows the predicted social welfare and the optimal social welfare (calculated using brute force on the true valuation functions) for 10 different experiments.
Exp. No.
Predicted Social Welfare
Optimal Social Welfare
Efficiency
%
124
127
97.63 97.6378
2
114
123
92.6829
3
84
129
65.11
4
118
128
92.1875
5
114
127
8937638
6
126
128
98.4375
7
110
122
90.1639
8
123
132
93.1818
9
123
128
96.0938
10
120
129
93.0233
Average
115.6
127.3
90.8288
Table 4: Experiments when value functions coverage functions, with 60 universe size, and 8 itemss, with coverage probabilities
(5) 0.1, 0.3, and 0.5 for three bidders respectively, and the learning model is EDSF. In the phase of learning EDSFs we have used the same setting as mentioned in the Table I The number of bidders (n) is 3 and the learning rate for the gradient ascent (17) is 0.001.
The second experiment is the same the first experiment, except that learning model is DSF with 3 layers of 64 neurons, using the MILU activation function with 95. The corresponding results can be seen in Table 5 As observed, the average efficiency in this experiment is significantly lower than in the experiment with the EDSF model.
Furthermore, we conducted an experiment compare the performance of vanilla neural networks versus EDSFs in estimating the optimal allocation for maximizing social welfare. By "vanilla neural network, we mean that weights can be negative, and activation functions may be non-concave. In this experiment,
15

---

Exp.
Predicted Social Welfare
Optimal Social Welfare
Efficiency
No.
98
127
77.1654
2
98
121
80.9917
3
63
130
48.4615
4
50
124
40.3226
5
94
120
78.3333
6
92
131
70.2290
7
92
126
73.0159
8
99
129
76.7442
94
127
74.0157
10
60
125
48,0000
Average
84
126
66.7279
Table 5: Experiments when value functions are coverage functions, with 60 universe size, and items, with coverage probabilities (p) 0.1, 0.3, and 0.5 for three bidders respectively, and the learning model is DSF. In the phase of learning DSFs we have used the same sctting as mentioned in the Table The number of bidders (n) is 3 and the learning rate for the gradient ascent (1)) is 0.001.
fully-connected neural network with 3 layers, each having 64 neurons and using the ReLU activation function, was employed to learn the bidders' valuation functions. The networks were trained using the setup described above, and the results are shown in Table G We observe that the mean efficiency is about 77%, which is much lower than the EDSF efficiency of (90%).
Exp. No.
Predicted Social Welfare
Optimal Social Welfare
Efficiency
%
56.0
98.0
57.14
2
79.0
101.0
78.28
3
89.0
93.0
95.70
4
81.0
94.0
86.17
5
70.0
99.0
70.71
6
52.0
94.0
55.32
7
84.0
100.0
84.00
8
62.0
101.0
61.39
9
88.0
99.0
88.89
10
81.0
96.0
84.37
11
77.0
93.0
82.80
12
92.0
108.0
85.19
13
77.0
104.0
74.04
14
85.0
99.0
85.86
15
69.0
94.0
73.40
Average
76.13
98.2
77.55
Table 6: Experiments when value functions are coverage functions, with 50 universe size, and items, with probablities 0.1, 0.3, and 0.5 for three bidders respectively, and the learning model vanilla neural network. The number of bidders (n) is 3 and the learning rate for the gradient ascent (1) 0.001
Additionally, experiments with larger universe sizes of 500 and 1000 were conducted, and the corresponding results, comparing the performance EDSF and DSF in predicting optimal social welfare, are shown Tables and respectively. Other settings for these experiments the same those in Tables and 5
16

---

Exp. No.
EDSF Prodicted
DSF Prodicted Social Welfare
Optimal Social Welfare
EDSF
DSF
Social Welfare
Eff. %
ETT. %
892.0
653.0
902.0
98.89
72.39
907.0
634.0
917.0
98.91
69.14
887.0
636.0
892.0
99.44
71.30
4
882.0
500.0
900.0
98.00
55.56
5
909.0
670.0
913.0
99.56
73.38
Average
894.0
618.0
904.0
98.96
68.35
Table 7: Experiments comparing EDSF and DSF efficiency in the maximizing social welfare problem, with coverage function as value function, 500 universe size, with probabilities 0.1, 0.3, and 0.5 for three bidders, respectively. In the phase of learning EDSFs and DSF we have used the same setting as mentioned in the Table The number of bidders (n) is 3 and the learning rate for the gradient ascent (17) is 0.001
Exp. No.
EDSF Predicted
DSF Predicted Social Welfare
Optimal Social Welfare
EDSF
DSF
Social Welfare
Eff. %
E.f.. %
1737.0
1527.0
1782.0
97.47
85.69
1742.0
1730.0
1789.0
97.37
96.70
1744.0
1547.0
1778.0
98.09
87.01
4
1784.0
1739.0
1790.0
99.66
97.15
1755.0
1699.0
1776.0
98.82
95.66
Average
1752.4
1648.4
1783.0
98.2
92.60
Table 8: Experiments comparing EDSF and DSF efficiency in the maximizing social welfare problem, with coverage function as value function, 1000 universe size, with probabilities 0.1, 0.3, and 0.5 for three bidders, respectively. In the phase of learning EDSFs and DSF we have used the same setting as mentioned in the Table The number of bidders (n) and the learning rate for the gradient ascent (17) is 0.001.
Finally, conducted set of experiments to demonstrate the optimal learned social welfare based on the trained EDSFs and DSFs. All details of this experiment are the same as in Tables 4 and 5 except for the universe size, which is set to 1000. Results are presented in Table g As obscrved, the optimal learned social welfare for EDSTs close to the optimal social welfare, indicating a good estimation of the true valuation functions. However, the optimal learned social welfare for DSFs is significantly lower than the optimal value. Additionally, it is worth noting that the gradient ascent algorithm, when using EDSF networks, achieves reasonably good performance and shows only slight difference from the optimal learned social welfare for EDSFs.
Observing the results, it becomes apparent that the utilization of Extended Deep Submodular Functions (EDSFs) in the context of the social welfare maximization problem yields significantly higher efficiency when compared Deep Submodular Functions (DSFs) and also vanilla neural networks. This stark difference in efficiency underscores the potential advantages and superior performance that our proposed framework, leveraging EDSFs, can bring to the modeling of user valuations within the realm of this NP-hard combinatorial optimization problem.
5 Discussion and Remarks
In this paper, we introduced an architecture to represent all monotone set/submodular functions using neural networks. Here are some points about the proposed architecture that are worth-noting.
Remark 5.1 (Computational Efficiency). The most important shortcoming of this architecture the exponen- tial size of the network to represent all monotone set setsubmodular functions. However, would like to note
17

---

Exp.
EDSF Predicted
DSF Predicted
Optimal Learned
Optimal Learned
Optimal SW
EDSF
DSF
No.
SW
SW
EDSF SW
DSP SW
EfT. %
Eff. %
2340.0
1965.0
2390.0
2159.0
2390.0
97.91
82.22
2
2274.0
2024.0
2373.0
2016.0
2373.0
95.83
85.29
3
2348.0
2239.0
2382.0
2059.0
2387.0
98.37
93.8
2306.0 4
2187.0
2392.0
2037.0
2392.0
96.4
91.43
5
2300.0
1464.0
2366.0
2130.0
2372.0
96.96
61.72
6
2369.0
2268.0
2372.0
2051.0
2383.0
99.41
95.17
7
2262.0
1771.0
2375.0
2050.0
2387.0
94.76
74.19
8
2306.0
1977.0
2344.0
2309.0
2363.0
97.59
83.66
9 2360.0
2087.0
2360.0
2024.0
2378.0
99.24
87.76
10
2321.0
2075.0
2370.0
2008.0
2383.0
97.4
87.08
Avg
2318.6
2005.7
2372.4
2084.3
2380.8
97.7
84.5
Table 9: Experiments comparing EDSF and DSF efficiency in the maximizing social welfare problem, with coverage function as value function, 1000 universe size, with probabilities 0.1, 0.3, and 0.5 for three bidders, respectively. In the phase of learning EDSFs and DSF have used the same setting mentioned in the Table The number of bidders (n) is 3 and the learning rate for the gradient ascent (1)) is 0.001.
that the assumption on the exponentiality the number of DSFs just used as a sufficient. condition for our proofs. In our experiments, esspecialy Table 2 with different numbers of DSFs tested, we observed that using much fewer number of DSFs than exponential order is enough attain good generalization in practice. For example, in the problem of learning coverage functions, 16 and 50 items as input (note that 64 < 216 and 64 < 250). We have also used 64 DSFs in learning cut functions of graphs with 50 vertices (64 << 25
used 64 DSFs represent a function with
Remark 5.2. Regarding Theorem 3.9 we would like to note that the architecture of EDSFs was derived through an analysis of polymatroids, which also forms the basis proving Theorem 3.9 We believe that including Theorem 3.9. along with its proof based on polymatroid theory, essential for deeper understanding of EDSFs. Additionally, during the review process, simpler proof of Theorem 3.9 was suggested by one of the reviewers, which we have included in Appendix for completeness.
Remark 5.3. There exists some approximation algorithm to find the near-optimal social welfare in the problem setting mentioned above, like the one proposed in Vondrak (2008), namely, Continuous Greedy. We have conducted multiple experiments in order to compare the Continuous Greedy and Gradient Ascent algorithm as shown in Table 10
As can be seen from the results, the "average" performance of both methods (Gradient Ascent and Contimuous Greedy) is very similar, leading us conclude that there may be shared intuition underlying both algorithms. The intuition behind the contimuous greedy algorithm is that the current distribution will shift towards the most increasing direction to find the optimal distribution for sampling. This concept is reminiscent of moving in the direction of the gradient in concave functions to maximize them. Overall, it appears that the Gradient Ascent algorithm closely resembles the continuous dual of the continuous greedy algorithm. Exploring the theoretical connection between Gradient Ascent and Contimoous Greedy can be an interesting direction for future work.
However, in the following, we would like to mention that the continuous greedy algorithm has major limitation.
As it can be seen in the Table 10 the rumning time of the Contimoous Greedy algorithm is much larger than the Gradient Ascent in practice. It seems the reason behind this large difference that the CG algorithm requires to sample from the function in order of ((mm))) times to estimate the expectations in the algorithm. It makes so computationally complex in practice. However, since the size of the neural network for the proposed method in practice is much smaller than the theoretical requirements, using GA much faster than the CG algorithm, it be seen in the Table 10
18

---

Continuous Greody Social Welfare
Gradient Ascent Social Welfare
Continuous Groedy Wall-Clock Time (s)
Gradcint Ascent Wall-Clock Time(s)
Universe Size
mean
std
mean
std
mean
std
mean
std
200
599.666
0.471
598.
1.632
585. 385.943
1.857
99.404
0.076
500
1499.
0.816
1500.
0.000
601.558
0.425
101.290
0.060
1000
2998.
1.788
2997.8
1.326
625.598
3.089
103.320
0.446
Table 10: Experiments comparing Continuous Greedy and Gradient Ascent algorithms to maximize social welfare after training EDSFs on coverage function with different universe sizes. It shows that the CG algorithm in practice is much slower than the GA algorithm.
It is also worth noting that, there are some algorithms based on continuous greedy idea to find the maximizing input for submodular functions under different kinds of constraints Mokhtari et al. (2020); Badanidiyuru & Vondrák (0144) which are much faster than the original version of the algorithm in Vondrak (2008). But note that while these methods are faster than continuous greedy, their approximation factor bounded by 1 1- However, we know that the approximation factor for maximizing monotone DSFs with a matroid constraint
of rank k using gradient ascent is max0<<<1 (1- - 8 e- -(((())) Bai et al. (2018), which is significantly
better than 1 1-2 1 for large k. Note that the proof of the approximation factor for maximizing DSFs using gradient ascent (including pipage rounding as the last step) is exactly applicable to EDSFs The intuition is that since for each input x E [0, 1]", only one of the DSI's is active, then for functions that can be represented by an EDSF using the minimum over a finite number of DSFs, we can achieve a better approximation factor than 1 1- .. Note that this is only interesting for EDSFs that we can represent using minimum over polynomial number of DSFs.
Remark 5.4. As shown in Appendix A the loss function for EDSF exhibits significant fluctuations and spikes when learning coverage functions. We hypothesized that this was due to the MiLU activation function, which has sharp edges that could complicate backpropagation and hinder the learning process. To test this conjecture, we conducted additional experiments with EDSF using different, smoother activation functions, such as log(1 + 2²). As seen in Figures 16 these loss functions became much smoother, with no visible fluctuations. However, these smoother activation functions did not generalize effectively as MiLU and were unable to learn the coverage function as well.
Remark 5.5. Finally, we conclude our discussion by analyzing why DSFs produce constant outputs after training, particularly when learning coverage functions, as shown in Figures 9 10 To test the expressive power of DSFs, especially for coverage functions,
additional experiments with much larger DSFs The results, presented in Figures 11 indicate that DSFs still output constant values. We hypothesize that this issue arises when neurons in layer reach the saturation point of their activation function a limitation observed across common concave activation functions. Beyond this saturation point, DSFs produce a constant output. Using larger DSFs exacerbates this issue, while smaller DSFs, as seen in Figure S can sometimes avoid it.
6 Conclusions
In this research, we introduce a novel concept called Extended Deep Submodular Functions (EDSFs), building upon the foundation of Deep Submodular Functions (DSFs). DSFs, a subset of monotone submodular functions, provide structured framework for representing specific types (a subset) of submodular functions. However, the scope of DSFs is limited to strict subset of monotone submodular functions. EDSFs, on the other hand, serve as natural extension, expanding the family of DSFs to encompass all monotone set/submodular functions. Our proofs are rooted in the properties of polymatroids, offering insights into the relationship between polymatroids and submodular functions. Additionally, we highlight the concave nature of EDSFs, a charactcristic that is provod to be valuable in addressing and efficiently solving various combinatorial optimization problems. To validate the efficacy of EDSFs, we conducted experiments in three distinct settings, namely, learning coverage functions, learning modified cut functions, and maximizing social
19

---

welfare. The results consistently demonstrated the superior performance of EDSFs compared to DSFs in these experimental scenarios. In conclusion, our findings suggest. that EDSFs provide a more comprehensive and effective solution for modeling monotone set rotsuumooullar functions using neural networks. The extended scope and enhanced performance make EDSFs a promising direction for further exploration in various machine learning and optimization domains.
Broader Impact
This paper presents work whose goal is to advance the field of Machine Learning. There aren't many straight potential societal consequences of our work, none which we feel must be specifically highlighted here.
References
Ashwinkumar Badanidiyuru and Jan Vondrák. Fast algorithms for maximizing submodular functions. In Proceedings of the Twenty-Fifth Annual ACM-SIAM M Symposium on Discrete Algorithmss, pp. 1497 1514. Society for Industrria and Applied Mathematios, Jamuary 2014. ISBN 978 0788-1-11197-338---- 978-19-1197----71-13
2. doi: 10.1137/19781111193342... URL attps::/eputee siam. wttt....oo...////.11111///////// httpm/..r...oo//....1//////71110
Wenruo Bai, William Stafford Noble, and Jeff A Bilmes. Submodular Maximization via Gradient Ascent: The Case of Deep Submodular Functions. In Advances in Neural Information Processing Systems, vol- ume 31. Curran Associates, Inc., 2018. URL httpss//proceedddgg http:h/as//haaallaar00000/000002
Maria-Florina Balcan and Nicholas A. Harvey. Submodular Functions: Learnability, Structure, and Optimization. SIAM Journal on Computing, 47(3):703 754, January 2018. ISSN 0097-5397, 1095-7111.
doi: 10.1137/12088880 URL htttss//eppbs.. siam..ssiammmm.........m...aaa.. wwtp:oogg///oo.oo.ooo.//. 113711188111/2
Jeffrey Bilmes and Wenruo Bai. Deep Submodular Functions, January 2017. URL http://arxiv.org /bs/
1701. 1701.08939 arXiv:1701.0893) [cs].
Abir De and Soumen Chakrabarti. Neural Estimation of Submodular Functions with Applications Differentiable Subset Selection. 2022.
Brian Dolhansky and Jeff A Bilmes. Deep submodular functions: Definitions and learning. Advances in Neural Information Processing Systems, 29, 2016.
Vitaly Feldman and Pravesh Kothari. Learning coverage functions and private release marginals. Conference on Learning Theory, pp. 679-702. PMLR, 2014. URL /ttpp::/proceeedngg. mlr.
htt.r/eeednnnss.....reesss///s press/v35/
Vitaly Feldman and Jan Vondrák. Optimal bounds on approximation of submodular and xos functions by juntas. STAM Journal on Computing, 45(3):1129-1170, 2016.
Marshall L Fisher, George L Nemhausor, and Laurence A Wolscy. An analysis of approzimations for mazimizzng submodular sel funclions II. Springer, 1978.
Jennifer Gillenwater, Alex Kulesza, and Ben Taskar. Near-optimal map inference for determinantal point processes. Advances in Neural Information Processing Systems, 25, 2012.
Michel X. Goemans, Nicholas J. A. Harvey, Satoru Iwata, and Vahab Mirrokni. Approximating Submodular Functions Everywhere. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 535-544. Society for Industrial and Applied Mathematics, January 2009. ISBN 978-0- doi: 10.1137/1.9711611978800
89871-680-1 978- 806-8.
URL https: fttps://epubs: siam. org/doi/
10. 11111771198816119773555
20

---

David Kempe, Jon Kleinberg, and Eva Tardos. Maximizing the spread of influence through social network. In Proceedings of the ninth ACM STGKDD international conference on Knowledge discovery and dala mining, pp. 137 146, 2003.
Miles Kimball, Daniel Reck, Fudong Zhang, Fumio Ohtake, and Yoshiro Tsutsui. Diminishing marginal utility revisited. Technical report, National Bureau of Economic Research, 2024.
Juho Lee, Yoonho Lee, Jungtaek Kim, Adam Kosiorek, Seungjin Choi, and Yee Whye Teh. Set. (ransformer: A framework for attention- based permutation-invariant neural networks. In International conference machine learning, pp. 3744-3753. PMLR, 2019.
Hui Lin and Jeff A Bilmes. Learning mixtures of submodular shells with application to document summariza- tion. arXiv preprint orXiw:1210.48771 2012.
CG McLaughlin and ME Chernew. Health insurance: economic and risk aspects. 2001.
Aryan Mokhtari, Hamed Hassani, and Amin Karbasi. Stochastic conditional gradient methods: From convex minimization to submodular maximization. Journal of machine learning research, 21(105):1-49, 2020.
Mukund Narasimhan, Nebojsa Jojic, and Jeff A Bilmes. Q-clustering, Advances in Neural Information Processing Systems, 18, 2005.
Shinsaku Sakauc. Differentiable groody algorithm for monotone submodular maximization: Guarantocs, gradient estimators, and applications. In International Conference on Artificial Intelligence and Statistics, pp. 28 36. PMLR, 2021.
Jan Vondrak. Optimal approxination for the submodular welfare problem in the value oracle model. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pp. 67 74, Victoria British Columbia Canada, May 2008 ACM. ISBN 978-1-60558-047. doi: 10.1145/1374976.1277 1374388. URL
attps://dl. hwwp://ddlccccc.eccccm/mm acm. httg//00//00.115/3374/3/33 1374389
Edward Wagstaff, Fabian Fuchs, Martin Engelcke, Ingmar Posner, and Michael A Osborne. On the limitations of representing functions sets. In International Conference Machine Learning, pp. 6487-6494. PMLR, 2019.
Jakob Weissteiner, Jakob Heiss, Julien Siems, and Sven Seuken. Monotone-valne neural networks: Exploiting preference monotonicity in combinatorial assignment. arXiv preprint arXiv:2109.1511 2021.
Bryan Wilder, Bistra Dilkina, and Milind Tambe. Melding the data-docisions pipeline: Decision-focused learning for combinatorial optimization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 1668, 2019.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poezos, Russ R Salakhutdinov, and Alexan- der J Smola. Deep sets. In 1. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vish- wanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Cur- ran Associates, Inc., 2017. URL
wwweddiinnnnnuuipsp. wtt..iips../ppppprrfflle.ee..... /
A Details of Experiments on Learning Coverage Functions
To set the hyperparameters-Sine an exhaustive search across a defined parameter space. The search space included varying the number of layers from to 6, the number of neurons per layer from 32 to 2048 (in powers of 2), and testing different values of alpha, starting from small values around up to larger values the order of 1000. While many different hyperparameter configurations worked well for the EDSF architecture, none of the candidates yielded promising results for DSFs in terms of output or loss. Additionally, for all weight. initialization in our DSF
as the number of layers, neurons, and the value of alpha-wo performed
21

---

and EDSF networks across all experiments in the paper, used Gaussian distribution with mean of 0 and a variance of 0.1.
For our first experiment (see Table D. the architecture for the Deep Set model consists of three layers with 64 neurons each for Φ and three layers with 64 neurons each for p. The architecture used for the Set Transformer model includes attention heads and a hidden dimension of 128.
To demonstrate the loss function and outputs of EDSFs and DSFs in learning coverage functions, we tested three different coverage functions with probabilities of 0.1, 0.3, and 0.5. All three coverage functions had a universe size of 100 and 16 items. The DSF and EDSF used for these experiments had the same architecture as described in Table ! For each experiment, our network was trained for 10,000 epochs using the Adam optimizer with a learning rate of 0.01. The employed cost, function, consistent with all other experiments, was the Li-loss function. As shown in Figures 5 [0 the DSF fails to learn the patterns of the target coverage functions and outputs a constant value. In contrast, the EDSF can closcly follow the patterns of the target. functions.
To demonstrate the expressive power of DSFs, we employed larger architectures for DSFss in learning the coverage function. The DSFs used in these experiments had 4 and 6 layers, cach with 2048 neurons, and utilized the MiLU activation function with a = 95. The target function was a coverage function with a universe size of 100, 16 items, and a probability of 0.5. Consistent with all other experiments, the network was trained for 10,000 epochs using the Adam optimizer with a learning rate 0.01 and the L1-loss function as the cost function. As shown in Figures and 12 the DSF still failed to learn the target coverage function, producing constant output instead. Additional experiments using various concave activation functions for DSFs were also conducted to learn the aforementioned coverage function, with results presented in Figures The learning setup for these experiments was consistent with the other experiments. Moreover, the DSF used for these experiments had 3 layers with 64 neurons each.
13 15
Finally, to test our conjecture described in Remark 5.4 regarding the loss function for EDSEs when lcarning coverage functions with many spikes and fluctuations, we experimented with smoother concave activation functions. As shown in the corresponding plots in Figures 16 18
the loss functions exhibit no visible spikes fluctuations. For these experiments, the target coverage function had universe size of 100, 31 items, and probability of 0.2. Morcover, The EDSF used for these experiments had 4 layers with 64 neurons each, similar to Table 1 and learning setup was consistent with other experiments.
B Details of Experiments on Learning Cut Functions
For setting hyperparameters in learning the cut function, similar to learning the coverage function, we conducted an exhaustive search and tried different values for the mumber of layers, neurons, and values of alpha. The search space for these parameters was the same as that used in learning coverage functions, as mentioned in Appendix A Many different candidates for the DSF encountered the same problem of outputting a constant value; however, a few of them could approximately identify the pattern of the target. cut function. It is worth mentioning that they could not learn the cut function as well as the EDSF, and most of the hyperparamctors worked well for the EDSF.
For our first experiment in Section 4.2 (see Table 3), the architecture for the Deep Set model consists of three layers with 64 neurons each for ó and three layers with 64 neurons each for p. The architecture used for the Set. Transformer model includes attention heads and a hidden dimension of 128.
We can observe the loss function and the true vs. predicted values for the train and test samples for the EDSF and DSF in Figurcs 19 and 20 respectively. The setup for these experiments is the same the setup described in Section
Table
3
C Alternative proof for the main result of the paper
22

---

Loss Function
20.35
27.23
25.75
21.35
19.75
1059
27.00
15.35
0.35
7.05
5.00
2.25
iteration number
Thun Prodicted Vallun
MMM
Tan Samblos
Thee vs Prodicted Volue
Figure Learning coverage function with probability 0.1, universe size 100, and 16 items. We have used EDSF and shown Training loss, Truth vs. Predicted values for train and test samples. Other settings are same as Section 4.1 Table
There is another much simpler proof to establish the main result of the paper without using polymatroid analysis. M If we define the function 9A(B) B) as:
(B = EgEB(() f(A) Ejen
ifA n B
(28)
ifAr B 0
Then, since we have ga (B) = fBB,, we conclude that f(B) = min 9A (B) for all B C S. This proof much simpler than the provided proof
hence, we can conclude that f(B) < minA A (B Fisher et al.
1978
5rthis proof provided kindly by the reviewers during the review process.
23

---

the paper, however, without using the analysis of polymatroids there is intuition at hand about how we constructed the architecture of the EDSFs to respresent all of the monotone submodular functions, which makes is possible to generalize the archieectre to all monotone set functions as a more powerful result.
24

---

Loss Function
36.86
35.85
30.85
27.8
24.85
1055
21.85
10.86
0.86
4000 iteration number
Predicted
100
1M
Value Thain Samples
Train Samples
True vs Predicted Value
Vakte of that Samples
DRRdICt
Samples
Figure 6: Learning coverage function with probability 0.3, universe size 100, and 16 items. We have used EDSF and shown Training loss, Truth vs. Predicted values for train and test samples. Other settings are same as Section
4.1 Table
25

---

Loss Function
40.56
32.56
28.56
1055
20.56
16.56
12.56
0.56
4000 iteration number
Predicted
Value Thain Samples
Train Samples
True vs Predicted Value
Vakue of that Samples
Samples
Figure 7: Learning coverage function with probability 0.5, universe size 100, and 16 items. We have used EDSF and shown Training loss, Truth vs. Predicted values for train and test samples. Other settings are same as Section 4.1 Table
26

---

Loss Function
57.2
54.23
5123
48.23
45.23
1055
21.33
4000
edn0
iteration number
Predicted
Samples
True vs Predicted Value
Samples
Figure 8: Learning coverage function with probability 0.1, universe size 100, and 16 items. We have used DSF and shown Training loss, Truth vs. Predicted values for train and test samples. Other settings are same as Section 4.1 Table
27

---

Loss Function
39.05
35.08
31.00
29.0
27.08
25.08
21.09
17.08
1308
4000 iteration number
edno
Predicted
Valuee Thain Samples
Train Samples
True vs Predicted Value
Vakte of that Samples
DRRdICt
Samples
Figure 9: Learning coverage function with probability 0.3, universe size 100, and 16 items. We have used DSF and shown Training loss, Truth vs. Predicted values for train and test samples. Other settings are same as Section 4.1 Table I
28

---

Loss Function
46.50
42.50
38.50
36.60
30.66
1055
26.66
22.66
18.66
14.66
10.65
6.66
4000 iteration number
edno
Predicted
Value Thain Samples
Train Samples
True vs Predicted Value
Vikue of that Samples
Samples
Figure 10: Learning coverage function with probability 0.5, universe size 100, and 16 items. We have used DSF and shown Training loss, Truth vs. Predicted values for train and test samples. Other settings are same as Section 4.1 Table
29

---

Loss Function
258
230
202
174
lose
146
118
500
1000
1500
2000
2500
3000
3500
4000
iteration number
True vs Predicted Value
303
Value of Train Samples
predict truch
Train Samples
True v5 Predicted Value
332
37-
Vallue Test Samples
predict trush
Test Samples
Figure 11: Learning coverage function with DSF having more number of neurons. The used DSF has layers each having 2048 neurons and MiLU activation function with a 95. we can see that it still outputs constant when learning coverage function with universe size of 100 and probability of 0.5.
30

---

Loss Function
13931
12384
loss
7743
6196
4649
3102
1555
500
1000
1500
2000
2500
3000
3500
4000
iteration number
True VS Predicted Value
Valuee of Train Samples
pradic: truth
Train Samples
True vs Predicted Value
Value of Test Samples
89
pradict
Test Samples
Figure 12: Learning coverage function with DSF having more number of neurons. The used DSF has layers each having 2048 neurons and MiLU activation function with a = 95. we can see that it still outputs constant. when learning coverage function with universe size of 100 and probability of 0.5.
31

---

Loss Function
56.94
52.94
loss
40.94
34.84
22.94
16.94
500
1000
1500
2000
2500
3000
3500
4000
iteration number
True vs Predicted Value
102
Valuee of Train Samples
8
predict
10
Samples
True v5 Predicted Value
108
Value of Test Sampples
predict
30
Samples
Figure 13: Learning coverage function with DSF having log(1 + x) as activation function. The used DSF has layers each having 64 ncurons and log(1 + x) as activation function. We can see that still outputs constant when learning coverage function with universe size 100 and probability of 0.5.
32

---

Loss Function
67.08
61.06
loss
37.06
31.06
25.06
19.08
500
1000
1500
2000
2500
3000
3500
4000
iteration number
True vs Predicted Value
M N
43-
Valuee of Train Samples
30
predict
20
10
Samples True vs Predicted Value
Value of Test Samples
23
predict
30
50
Samples
Figure 14: Learning coverage function with DSF having tanh(x) as activation function. The used DSF has 3 layers each having 64 neurons and tanh(x) as activation function. We can see that it still outputs constant when learning coverage function with universe size of 100 and probability of 0.5.
33

---

Loss Function
59.14
53.14
loss
47.14
35.14
29.14
23.14
2500
iteration number
True Predicted Value
Value of Train Samples
predict
Samples True vs Predicted Value
AMIMN
Value of Test Samples
20
truth
Test Samples
Figure 15: Learning coverage function with DSF having oxx) 0.5 activation function. The used DSF has 3 layers each having 64 neurons and (x) 0.5 as activation function. We can that it still outputs constant when learning coverage function with universe size of 100 and probability of 0.5.
34

---

Loss Function
02.503
1055
01.00
1350 2000 Iteraion number
Figure 16: Loss function of EDSF with log(1 + x) as activation function. The target functions is a coverage function with 100 universe size, probability of 0.2, and 31 items.
Function
10S5
042266277
1000 1400
2000
2:0
9030
9:30
Figure 17: Loss function of EDSF with tanh(x) as activation function. The target functions is a coverage function with 100 universe size, probability of 0.2, and 31 items.
Loss Function
2004
Peratton number
Figure 18: Loss function of EDSF with (xx) 0.5 activation function. The target functions is coverage function with 100 universe size, probability of 0.2, and 31 items.
35

---

Loss Function
111.0
99.6
87.8
75.6
loss
63.6
51.6
39.6
27.6
15.8
3.6
500
1000
1500
2000
2500
3000
3500
4000
iteration number
True vs Predicted Value
HMMMMM
Vallue of Train Samples
200
predict
10
Semples True vs Predicted Value
MMM
M
Vallue of "lsst Samples
300
302
predict
Samples
Figure 19: Learning a cut function generated by the Erdos-Reny' model with probability 0.2 and having 50 vertices, using the EDSF architecture same as Table showing Training loss, Truth vs. Prodicted values for train and test samples.
36

---

Loss Function
194.1
191.1
1055
185.3
192.1
179.1
176.1
2006
iteration number
Predicted
W
500
Value Thain Samples
12h
Irain Samples
True vs Predicted Value
MPMMNN
400
Vakre of That Samples
160
Samples
Erdos-Renyi Figure 20: Learning cut function generated by the Erdos Renyi model with probability 0.2 and having 50 vertices, using the DSF architecture same as Table 3, showing Training loss, Truth vs. Predicted values for train and test samples.
37


Reviews:
[{"review_id": "p7WeZhC0fP", "reviewer": "Reviewer_Ythe", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**strength:**\n\n1. EDSFs can represent all monotone submodular and set functions. This addresses a major limitation of DSFs, enhancing the modeling of submodular functions in ML.\n\n2. Experiments provide clear evidence that EDSFs outperform DSFs, (empirical generalization error).\n\n**weakness:**\n\nOne significant drawback is the potential exponential growth in the network size needed for the expressiveness. Although fewer DSFs can work in practice, this complexity might limit scalability and hinder practical implementation for larger datasets (or say, real-world problems). But the paper also noted this in the conclusion.\n\nI have some questions regarding the empirical results. Please refer to the requested changes.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces a novel class of set functions called Extended Deep Submodular Functions (EDSFs). The idea is super simple yet nice, the min function over a set of DSFs, which significantly extend Deep Submodular Functions (DSFs) by being capable of representing all monotone submodular functions. The authors demonstrate through theoretical analysis and experiments that EDSFs generalize much better than DSFs in learning complex submodular functions.\n\nThe paper is well written and inspiring. Overall, I enjoy reading the submitted manuscript.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Here I have some questions regarding the empirical experiments:\n\n1. Learning coverage functions: It seems that DSFs are always outputting constants. I’m interested in the expressive power of DSFs when representing the coverage functions. It would be great if two following experiments are conducted:\n\n1.1 For fairness use the same number of neurons as EDSF (e.g. like 64*3*3).\n\n1.2 Try the boundary of DSF (e.g. a super larger DSF), see its capability in representing coverage functions.\n\n2. Learning cut functions: I went throught appendix. B, but found no results of DSFs in learning the cut functions. Even though the DSF performs reasonably good, the authors should give details of such result and explain the potential reason.\n\n3. Learning social welfare maximization: \n\n3.1 It’s shown that DSFs could not probably learn coverage functions well, yet here the authors presume the true submodular functions are coverage functions. I suggest that the authors may change another presumption for fairness.\n\n3.2 Does Vanilla NN have same size (number of neurons) as EDSF? \n\n\n[minor] it would be rigorous to add std in Table. 1.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "IVCzun7zFU", "reviewer": "Reviewer_2jd5", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Paper introduces a novel representation of monotone set functions as neural networks.\n- The provided limited empirical results show that learning coverage functions with EDSFs seem to yield significantly better performance compared to DSFs.\n- The paper is written clearly.\n\nWeaknesses:\n- The proposed neural network representation has exponential width. So it is not possible to provably learn it in polynomial time. \n- The theoretical results provided are straightforward observations (see requested changes for more details).\n- Experimental results are very limited:\n\t- the datasets used are very small (largest ground set size considered is 50 for the learning experiments, and 8 for the submodular welfare maximization) and synthetic.\n\t- only coverage and cut functions are considered, which are both monotone submodular. Since the introduced class can represent any monotone set function, it would be good to test performance on a non-submodular function. \n\t- they only compare their approach with the DSF approach from [Bilmes & Bai, 2017]. And they only consider one type of activation function (minimum linear unit), which might be more suitable for EDSF.\n\n- A lot of details related to their experimental setup are missing (see requested changes).\n\n- Several related work are not discussed, such as:\n\t- Theoretical work on learning general submodular functions:\n\t\n\tVitaly Feldman and Jan Vondrak. Optimal bounds on approximation of submodular and xos functions by juntas. SIAM Journal on Computing, 45(3):1129–1170, 2016. \n\n\t- learning mixture of fixed submodular functions:\n\n\tH. Lin and J. Bilmes. Learning mixtures of submodular shells with application to document summarization. In Uncertainty in Artificial Intelligence (UAI), Catalina Island, USA, July 2012. AUAI.\n\n\tR. Sipos, P. Shivaswamy, and T. Joachims. Large-margin learning of submodular summarization models. In Proceedings of the 13th Conference of the European Chapter of the Association for Computational Linguistics, pages 224–233. Association for Computational Linguistics, 2012.\n\n\t- deep set functions:\n\n        Juho Lee, Yoonho Lee, Jungtaek Kim, Adam Kosiorek, Seungjin Choi, and Yee Whye Teh. Set transformer: A framework for attention-based permutation-invariant neural networks. In ICML, 2019.\n\n\tEdward Wagstaff, Fabian Fuchs, Martin Engelcke, Ingmar Posner, and Michael A. Osborne. On the limitations of representing functions on sets. In Proceedings of the 36th International Conference on Machine Learning, 2019.\n\n\t- decision-focused learning:\n\n\tSakaue, Shinsaku. \"Differentiable greedy algorithm for monotone submodular maximization: Guarantees, gradient estimators, and applications.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2021.\n\n\tB. Wilder, B. Dilkina, and M. Tambe. Melding the data-decisions pipeline: Decision-focused learning for combinatorial optimization. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence, pages 1658–1665. AAAI Press, 2019.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces a class of set functions representable as neural networks: Extended Deep Submodular functions (EDSFs). This class is an extension of the Deep Submodular Functions (DSFs), which is a class of submodular functions representable as neural networks that were introduced by (Bilmes & Bai, 2017). An EDSF is defined as the minimum of r DSFs. The authors show that the class of EDSFs is equal to the class of monotone set functions. In particular, \nthey show that any monotone set function can be represented by an EDSF with 3 layers and exponentially many nodes in the first hidden layer. They provide some very small scale empirical results on learning coverage functions on synthetic datasets showing better performance when using EDSFs compared to DSFs.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Questions: \n- What does it mean to vary r (Table 2) in terms of the architecture used? In appendix A, you state that you use three fully-connected layers with 64 neurons. I am guessing that means $r = 64$ in this case. When you vary r, do you only vary the number of neurons in the last hidden layer, or in all layers?\n- What is the coverage probability used in Table 2? Shouldn't the test loss for $r = 64$ match one of the test losses in Table 1?\n- Did you test using non-uniform $\\alpha$ values? I would expect this to perform better.\n\nCritical requested changes:\n- Add missing related work\n- To support the claim that EDSFs outperform DSFs, other architecture choices for DSFs should be explored, for example different choices of concave functions.\n- Either adjust/remove claims like \"EDSFs present a promising advancement in the representation and learning of set functions with improved generalization capabilities\", or add large scale non-synthetic experiments and compare with other related work to properly support this claim (see non-critical requested changes below).\n- Since the result that any monotone function can be represented as a EDSF (Theorem 3.11) implies the result for monotone submodular function (Theorem 3.9). Either remove that result, or explain why it is interesting.\n- Theorem 3.9 can be proved in the following much simpler way, which does not require going through polymatroids: \nThe submodular function $g_A(B)$ corresponds to $F(A) + \\sum_\\{j \\in B \\setminus A\\} F(j)$ if $A$ intersects $B$, and $\\sum_\\{j \\in B\\} F(j)$ otherwise. Hence, any monotone submodular function $F$ satisfies $F(B) \\leq \\min_A g_A(B)$ (see NemhauserAnalysisApproxSubMax-II Prop 1.1-(iii)). It directly follows then that $F(B) = \\min_A g_A(B)$, since $g_B(B) = F(B)$.\nIf you decide to keep this theorem, replace its overly lengthy proof by this simpler proof, and remove claims that this result requires \"an analysis of polymatroid properties\".\n- In Theorem 3.2, remove \"(submodular)\" from the statement, it is confusing. \n- In the definition of SCMM (Definition 2.5), the arbitrary modular function m± should take any real value, not just non-negative. If you want to consider only monotone SCMM, this should be explicitly stated.\n- In the definition of DSF (Definition 2.6), there should be an arbitrary modular m± added at the end. DSFs are not necessarily monotone! If you want to consider only monotone DSFs, this should be explicitly stated.\n- Include experimental setup details such as: optimization method and parameters used for training, how the number of neurons and $\\alpha$ parameters were chosen, how the coverage functions for valuation functions are generated in section 4.3., what values of $n$ and $\\eta$ you use? \n- Include variance values for all results (these are missing in Table 1 and 2)\n- In tables 4-8, include both the optimal solutions for both the learned functions and the true underlying ones.\n- Modify the claim that you \"introduce a novel category of set functions\" to say \"novel representation of monotone set functions\", since EDSFs corresponds to monotone set functions. \n- In the discussion section, the complexity of computing the gradient in GA is incorrect; it's not a constant! Note also that faster variants of continuous greedy are given in [Mokhtari et al, 2020] and [Badanidiyuru et al, 2014].\n\nMokhtari, A.; Hassani, H. & Karbasi, A.\nStochastic conditional gradient methods: From convex minimization to submodular maximization \nThe Journal of Machine Learning Research, JMLRORG, 2020\n\nBadanidiyuru, A.; Mirzasoleiman, B.; Karbasi, A. & Krause, A.\nStreaming submodular maximization: Massive data summarization on the fly \nProceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, 2014\n\nNon-critical requested changes:\n- Adding more large scale non-synthetic experiments and comparing with other related work is needed to really demonstrate the feasibility and advantage of EDSFs. In particular, I suggest to compare with the approach of (De & Chakrabarti, 2022), Deep sets (Zaheer et al, 2017), and Set Transformer (Lee et al, 2019).\n- the name \"extended deep submodular functions\" is confusing since the functions in this class are *not* necessarily submodular!\n- release the code for reproducibility \nTypos:\n- In the proof of Lemma 3.5, the first equality in the 2nd case should be an inequality.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "awqUhlRHvG", "reviewer": "Reviewer_vKkt", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\n* The paper is well-motivated, both in terms of what's missing in DSFs and in terms of why submodular functions are important to be modelled.\n* While it can be a double-edged sword, cf. below, the paper is heavily grounded in theory, and the proposed approach is proven to be able to represent any monotone set function.\n* Real-world experiments with combinatorial optimisation problems are presented.\n* The paper, especially if more technical details and code are provided, would be interesting to the ML/DL community.\n\n## Weaknesses\n* The paper and its proofs are too hard to follow, at least for someone not familiar with submodular set theory. Any visualisations present are... useless. Figure 1 is more or less an MLP (something there are plenty of images on the web), and no emphasis in the figure is put on what is the difference to an MLP. Similarly, in Figure 2 -- the concepts visualised are fairly straightforward for a non-mathematical person like me... In Figure 3, I think a min-component is something obvious to people who do machine learning/deep learning, which are the readers of TMLR.\n   \n   $ $\n\n  At the same time, definitions like \"Polymatroid\", \"Coverage function\", or Lemmas and Theorems from 3.5 onwards (3.5-3.11) are thrown in with little to no intuition/visualisation/small concrete examples. I cannot say for other readers, but improving on this would make it more readable from my POV.\n* A lot of technical details are missing, limiting the reproducibility/reusability of the work. I list those that I immediately notice and I aim to publish my review as early as possible so that we can work together on detailing the paper enough so that it is reproducible\n  * I could not find what the learning the learning rates are.\n  * What are the dimensionalities of the hidden layers in the DSF modules and what is $r$ in Table 1?\n  * For min-cut how is the neural model trained (loss functions, etc.)? Also, while the reviewer is referred to Appendix B, I couldn't immediately notice what DSFs performance is.\n  * The same goes for social welfare maximisation:\n     *  I understand we assume that the value functions from (27) are coverage functions, but do we use a trained EDSF model from section 4.1 to predict their values, or do we use (27) as an unsupervised loss function?\n     * Table 4 states, in the caption, that the universe size is 50 and the number of items are 8, but is that 1 social welfare maximisation per experiment?\n     * If the above is true, apart from it, are there any other details between experiments? (Weight initialisation seed, etc.)\n     * Why, in Tables 4 and 5 (and 6 as well), do we have different optimal social welfare? Do the test instances differ? While the performance improvement will most likely remain, a scientifically rigorous experiment should test two models on the *same* data, so as to claim that one is superior to the other\n     * Table 6 reports the performance of a vanilla neural network -- what is a vanilla neural network? MLP? DeepSet? \n     * What is the average in Table 6 -- is it better than DSFs?\n     * Weirdly, why is the optimal social welfare rarely exceeding 105, whereas in Tables 4-5 (which, according to the caption, is the same data distribution), it is always above 120. Even if datasets are different, I find this odd, given they should be the same distribution.\n  * In the appendix, the loss curves, including for EDSFs are far from smooth and are formed of spikes and plateaus. Take, for example, Figure 4, top left. The loss function does not drop below 7 up until epoch 4000, then a spike occurs, and the loss drops below 7, plateauing at around 1 but never reaching 0. I cannot help but wonder why this happens -- vanishing/missing gradients due to the usage of `min`? Poor hyperparameter choice/implementation of the experiments? Or something else altogether -- I do observe that the loss of DSFs, while it plateaus at different values, suffers from the same issues. A discussion on what is going on may be useful here.\n* A baseline that I believe should be present for all experiments, is the DeepSet architecture. \n\n* No code is provided. I do not have access to a model that I could potentially reuse or code that would help me understand the experimental setting.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper presents Extended Deep Submodular Functions (ESDFs), which, as the name suggests, extend on the previous research on Deep Submodular Functions (DSFs). The paper is motivated by the fact that DSFs can not represent all possible submodular set functions and the suggested changes are heavily grounded in set theory -- EDSFs can provably represent any monotone set function. In short, an EDSF is the minimum of $r$ (a hyperparameter) DSFs.\n\nEDSFs are evaluated on modelling coverage functions, modified graph cut functions and social welfare maximisation and the main baseline is DSFs. For all three tasks, across several settings, the proposed approach seems to outperform the baseline. Note, however, that (if I understand correctly) a separate training/optimisation is needed for each of the social welfare maximisation instances. For social welfare also a vanilla neural network is used as a baseline, but no details of what a vanilla neural network is is given.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* Improve readability -- consider adding more examples/visualisations for non-straightforward mathematical concepts. (Feel free to drop figures 1-3) Note, that while this would certainly improve the paper, it is not my key issue with this work. If this part is improved, in addition to the point below, the paper may be leaning towards [\"Featured certification\"](https://jmlr.org/tmlr/editorial-policies.html#certifications)\n* Add more technical details/discussions, as per the weaknesses outlined above. As TMLR puts an emphasis on accurate claims/rigorous evidence, this is a key aspect that has to be improved, so that I can lean for acceptance of the paper.\n* Consider adding more baselines, e.g. DeepSets\n* Consider open-sourcing the paper's code -- this is something I will not penalise for, if not done, but something that would aid the claims of the paper.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewer 2jd5 has pointed out that the discussion on continuous greedy still needs revising, as pointed out in their follow-up response.  Please do so, and enter (on OpenReview) a summary of the edits.

Reviewers 2jd5 and Ythe both pointed out the strong limitation of exponential width.  I see that this is discussed in Section 5, but given how significant of a limitation it is, it should also be mentioned earlier -- probably Section 3, and maybe even in the first paragraph of Page 2.
Decision: Accept (poster)