Deep Submodular Peripteral Networks
Authors: Gantavya Bhatt
Arnav Mohanty Das
Jeff Bilmes
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Submodular Optimization
Learning Set Functions
Experimental Design
Streaming Summarization
Data subset selection
Knowledge Distillation
Primary area: active_learning
TL;DR: This work proposes a new expressive parametric family of submodular functions and new graded-pairwise comparison (GPC) loss functions for their learning from expensive teachers.

Abstract: Submodular functions, crucial for various applications, often lack practical learning methods for their acquisition.  Seemingly unrelated, learning a scaling from oracles offering graded pairwise preferences (GPC) is underexplored, despite a rich history in psychometrics. In this paper, we introduce deep submodular peripteral networks (DSPNs), a novel parametric family of submodular functions, and methods for their training using a GPC-based strategy to connect and then tackle both of the above challenges.  We introduce newly devised GPC-style ``peripteral'' loss which leverages numerically graded relationships between pairs of objects (sets in our case). Unlike traditional contrastive learning, or RHLF preference ranking, our method utilizes graded comparisons, extracting more nuanced information than just binary-outcome comparisons, and contrasts sets of any size (not just two). We also define a novel suite of automatic sampling strategies for training, including active-learning inspired submodular feedback.  We demonstrate DSPNs' efficacy in learning submodularity from a costly target submodular function and demonstrate its superiority both for experimental design and online streaming applications.

Deep Submodular Peripteral Networks
Gantavya Bhatt" Arnav M. Das"
Jeffrey A. Bilmes
University of Washington, Seattle, WA 98195 {gbhatt2, arnavmd2, bilmes}@ux edu
Abstract
Submodular functions, crucial for various applications, often lack practical learning methods for their acquisition. Seemingly unrelated, learning scaling from oracles offering graded pairwise preferences (GPC) is underexplored. despite a rich history in psychometries. In this paper, introduce deep submodular peripteral networks (DSPNs), a novel parametric family of submodular functions, and methods for their training using GPC-based strategy connect and then tackle both of the above challenges. We introduce newly devised GPC-style "peripteral" loss which leverages numerically graded relationships between pairs of objects (sets in case). Unlike traditional contrastive learning, or RHLF preference ranking, our method utilizes graded comparisons, extracting more nuanced information than just binary-outcome comparisons, and contrasts sets of any size (not just two). We also define novel suite of automatic sampling strategies for training, including active-learning inspired submodular feedback. We demonstrate DSPNs' efficacy in learning submodularity from costly target submodular function and demonstrate its superiority both for experimental design and online streaming applications.
1 Introduction and Background
This paper jointly addresses two seemingly disparate problems presently open in the machine learning community.
The first is that of identifying useful practical scalable submodular function that can be used for real-world data science tasks. Submodular functions, set functions that exhibit a diminishing returns property (see Appendix B). have received considerable attention in the field of machine learning. This has fostered new algorithms that offer near-optimal solutions for various applications. These applications include detecting disease outbreaks [56], modeling fine structure in computer vision [41],
summarizing images [102] 72
26 37). active learning [34] 32 255, compressed sensing, struc-
tured convex norms, and sparsity 4 24 fairness [17 43), efficient model training (57]
58 70 69)
recommendation systems (7I), causal structure 114, 97.. and brain parcellating [85] (see also the re-
Despite these myriad applications, most research on submodularity has been on the algorithmic and theoretical side which assumes the submodular function needing to be optimized is al- ready hand. While there has been work showing the theoretical challenges associated with learning submodularity (5 7 6, there is relatively little work on practical methods to produce a useful submod- ular function in the first place (a few exceptions include 660 92 103)). Often, because works well, one uses the nan-parametric submodular facility location (FI.) function, i.e., for A C V with [V| f(A) = Σn max,eA 8,, where 8a.i 2 is similarity between items a and i. On the other hand, the FL function's 's computational and memory costs grow quadratically with dataset size n and FL can become infeasible for large data or online streaming applications. There a need for practical strategies to obtain useful, scalable, general-purpose, and widely applicable submodular functions.
views 101 [2]
'Equal Contribution
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

The second problem we address in this paper is the following: how best, in modern machine-learning context, can one learn a scaling from oracles that, for a given query, each provide numerically graded pairwise comparisons between two choices? That is, given two choices, A and B, an oracle provides a score Score(A, B) E IR which is positive if A is preferred to B, negative if B is preferred to A, zero if indifferent, and where the absolute value provides the degree of preference A or B has over the other. The oracle could be an individual human annotator, or could be a combinatorially expensive desired target function - in either case we assume that it is infeasible to optimize over the oracle but it is feasible to query. Learning a "scaling" means learning a scalar-valued function f that respects these graded pairwise scores in that f(A) (B) x Score (, B).
A special case of such preference elicitation from human oracles have been studied going back many decades. For example, the psychometric "Law of comparative judgment" [99] focuses on establishing numeric interval scales based on knowing preferences between pairs of choices (e.g.. A vs B). The Bradley-Terrry [14] model (generalized to ranking elicitations in the Luce-Shephard model 65 (0]) also involves preferences among elements of pairs. These preferences, however, are not graded and rather are either only binary (A < B or B < A), ternary (allowing also for indifference), or quaternary (allowing also for incomparability). Thus, each oracle query provides minimal information about pair. Therefore, multiple preference ratings are often aggregated where a collection of (presumed random i.i.d.) oracles vote on the preference between items of the same pair. This produces a histogram of preference ratings Ciy (a count of how many times i is preferred to j [9I] and this can be used in modern reinforcement learning with human feedback (RLHF) 105 for reward learning (i.c., inverse reinforcement learning B I.. Overall, the above modeling strategies are known in the field of psychometric theory [33 as "paired comparisons" where it is said that "paired comparison methods generally give much more reliable results" [74) for models of human preference expression and elicitation.
systems 109 76,
There are other models of preference elicitation besides paired comparisons. We explore "graded pairwise comparisons" (GPC) which also have been studied for quite some time [87 [0] Quite recently, it was found that "GPCs are expected to reduce faking compared with Likert-type scales and to produce more reliable, less ipsative trait scores than raditiinnll-iiar forced-choice formats" [61] such as paired comparisons. An intuitive reason for this is that, once get to the point that an oracle is asked only if A < B or B- < A, this does not elicit as much information out of the oracle as would asking for Score A, B) even though the incremental oracle effort for the latter is often negligible. As far as we know, despite GPC's potential information extraction efficiency advantages, GPC has not been addressed in the modern machine learning community. Also, while histograms Cij are appropriate for maximum likelihood estimation (MLE) of non-linear logistic and softmax style regression [9 76 IIII MLE with Bradley-Terry style model is suboptimal learn scoring from graded preferences Score(A, B) E R which can be an arbitrary signed real number.
In the present paper simultancously address both of the above concerns via the introduction and training of deep submodular peripteral networks (DSPNs). In a nutshell, DSPNs are an expressive theoretically interesting parametrie family of submodular functions that can be successfully learnt using a new GPC-style loss that we introduce below. In our work, since the teacher will be an expensive FL function and the learner is DSPN set function, we can view this knowledge distillation. Our offering, therefore, is very far from incremental - rather, we introduce a new provably more expressive model family (DSPNs), and a new learning paradigm (GPC-style learning) for distilling an expensive FL set function down to an expressive parametric learner.
form of
An outline of our paper follows. In 2 we define the class of DSPN functions, motivating the name "peripteral", and offering theoretical comparisons with the class of deep sets [[O]. Next, S describes new GPC-style "peripteral" loss that is appropriate to train a DSPN but can be used in any GPC-based preference elicitation learning task. For DSPN learning, this happens by producing list of pairs of subsets F, M that can be used to transfer information from the oracle target the DSPN being learnt. describes several E, M pair sampling strategy including an active-learning inspired submodular feedback approach. $55 emppriiilylyy evaluates DSPN learning based how effectively information is transferred from the target oracle and performance on downstream tasks such as experimental design. We find that the peripteral loss outperforms other losses for training DSPNs, and show that the DSPN architecture is more effective at learning from the target function than baseline methods such Deep Sets and SerTransformers. We also find that the grading in GPC indeed improves performance over binary-only comparisons.
2

---

While the above introduction situates our research and establishes the setting of our paper in the context of previous related work, our relation to and advancement over other related work fully explored in our Appendix in {A The appendices continue (starting at B offering further details of DSPN novelty ($C) and learning via the GPC-style peripteral loss.
2 Deep Submodular Peripteral Networks
Before starting this section, may assist the reader to consider our brief overview of submodularity. matroids, and weighted matroid rank in SB and a brief review of deep submodular functions in C both provided in the appendix.
A deep submodular peripteral network (DSPN) is a new expressive trainable parametric nons- mooth subdifferentiable submodular function. A DSPN has three stages: (1) a "pillar" stage; (2) permutation-innanne invariant aggregation stage; and (3) a "roof" stage. When consid- ered together. these three stages resemble an ancient Greek or Roman "peripteral" temple as shown in Figures [ |and [ [0] In this paper, all DSPNs are also monotone non-decreasing and normalized (see B As a set function f 22" + R. a DSPN maps any subset A S V to a non-negative real number. We consider sets object indices so A might be set of image indices while {2;: i E A} are the objects being referred to. Hence, w.l.o.g.. V [n]]
cemmodulla-preserviin
The first stage of DSPN consists of a set of |A| pillars one for each element in a set A that is being evaluated. The number of pillars changes depending on |A| the size of the A being evaluated. Each pillar is many mayy-layered deep neural structure 0w, Dx + F4, parameterized by the vector wp of real values, that maps from an object (from domain Dx which could be an image, string, etc.) to non-negative embedded representation of that object. For any u V and object Tv, then Dw, (x+) is d-dimensional non-negative real-valued vector (de, (Ir)), Dia, (z:)):.... &w (Iw)d) E R The parameters Wp are shared for all objects. Also, Pup (1:)) E IRT refers, for any [d]. to the n-dimensional vector of the j"h pillar outputs for all V.
The second stage of a DSPN is a submodular preserving and cermutation-invariann aggregation. Before describing this generally, we start with a simple example. Each element Φu, (za)j of (n,((Fa) (2a) is score for Ta along dimension and so non-negative modular set function can be constructed via mA(A) = Enea Pw, (xa)y- Such a summation is an aggregator that, along dimension j simply sums up the jHh contribution for every object in A. A simple way to convert this to a monotone non-decreasing submodular function composes it with a non-decreasing concave function v yielding hy((A = (/(m (A)) performing this for all j yields a d-dimensional vector of submodular functions. More generally, any aggregation function + that preserves the submodularity of h, = ('@.eAm, (a)) would suffice so long as it is also permutation invariant (110) (see Def. 7. For example, with @ = max (i.e., max pooling), the function (mmax.EA (a)) is again submodular. We show that there is expressive infinitely large family of submodular preserving permutation-invarian aggregation operators, taking the form of the weighted matroid rank functions (Def. which are defined based on a matroid M ZV and non-negative vector E IR!
Lemma (Permutation Invariance of Weighted Matroid Rank). The weighted matroid rank functinn (V.I) with any non-negative vector E R is permutation
rank (-) for matroid M invariant.
A proof is in Appendix B We identify the aggregator @ as Bog = M, (A) and produce new submodular functions V/j hi (A) (rank (z (A)), where the n-dimensional vector éu, (z:), constitute the weights for the matroid. Depending on the matroid, this yields summation (using a uniform matroid), max-pooling (using partition matroid), and an unbounded number of others thanks to the flexibility of matroids [77]. In theory, this means that the aggregator could also be trained via discrete optimization over the space of discrete matroid structures (in $5) however, our aggregators are fixed). The second stage of the DSPN thus aggregates the modular outputs of the first stage into a resulting d-dimensional vector for any set A C V. namely hw, (A) (h"") (A), hn (A), 1 (A)) E TRQ. This can also be viewed as a vector of submodular functions. We presume in this work that each aggregator uses the same matroid and each pillar dimension is used with exactly one matroid, but this can be relaxed leading to a d' > d dimensional space - in other words, many different discrete matroid structures can be used at the same time if so desired.
3

---

The third and final "roof" stage of DSPN is a deep submodular function (DSF) 123] Deep submodular functions are a nested series of vectors of monotone non-decreasing concave functions composed with each other, layer-after-layer, leading to a final single scalar outpur. Each layer contained in a DSF has non-negative weight values which assures the DSF is submodular. was shown in [13 that the family of submodular functions expressible by DSFs strictly increase with
depth. DSFs are also trainable using gradient-based methods analogous to how any deep neural network can be trained. A DSF is defined as set function, but we utilize the "root" 2 [13 multivariate multi-layered concave function Vn., : R² - R4, of DSF in this work. That DSPNs significantly extend DSFs, as well as DSF primer, is further described in $C The final stage of the DSPN composes the output of the second stage with this final DSF via fw (A) = Vu, (hu, (4)) where w = (Wip We) constitute all the learnable continuous parameters of the DSPN (assuming the discrete parameters, such as the matroid structure, is fixed). While the roof parameters Wir must be positive, the pillar parameters Wp are free, but the pillar must produce non-negative outputs.
Theorem 2 (A DSPN is monotone non con-eeceasing submodular). Any DSPN fw = vw., (hw, (A)) so defined is guaranteed to be monotone non- non- decceaceg submodular for all valid values of w.
The proof of Theorem 2 is found in Appendix $D We immediately have the following corollary.
Corollary 3 (Submodular Preservation of Weighted Matroid Rank Aggregators). Any weighted
matroid rank function for matroid M = (V,I) with any non-negative vector m E RR when used as an aggregator in a DSPN, will be submodularity preserving.
Clearly there is a strong relationship between DSPNs and Deep Sets 110. In fact any DSPNs is a special case of Deep Set, but there is an important distinction, namely that a DSPN is assuredly submodular. It may seem like this would restrict the family of aggregation functions available but, as shown above, there in theory an unbounded number of aggregators to study. Training DSPN also preserves submodularity simply by ensuring Wy remains positive which can be achieved using projected gradient descent (the positive orthant is one of the casiest of the constraints to maintain). deep set, when trained, can easily lose the submodular property, something we demonstrate in $ rendering the deep set inapplicable when submodularity is required. Also, as was shown in [3]. DSFs are already quite expressive, the only known limitation being their inability to express certain matroid rank functions. With a DSPN, however, the aggregator functions immediately eliminate this inability.
Corollary 4 (DSPN Family). Let FDSPN (resp. FDSF) be the family of DSPN (resp. DSF) submodular functions. Then FOSPN 3 FDSF.
It is an open theoretical problem if a DSPN, by varying in parameter w and combinatorial space M, can represent all possible monotone non-decreasing submodular functions.
3 Peripteral Loss
We next describe a new "peripteral" loss to train a DSPN and simultaneously address how to learn from numerically graded pairwise comparisons (GPCs) queryable from a target oracle.
We are given two objects E and M and we assume access to an oracle that when queried provides Score F,, M). We do
numerical score Score( M) E RR. As shorthand, we define A MEE not presume it is always possible to optimize over MM) This score, as mentioned above, could come from human annotators giving graded preferences for E vs. M, or could be an expensive process of training a machine learning system separately on data subsets E and M and returning the difference in accuracy on development set. In the context of DSPN learning, our score comes from the difference of a computationally challenging target submodular function fi. As an example, fi could be a facility location function that requires (n²) time and memory and not streaming friendly, where we have A = f((E) - (AM), this being a positive if E' is more diverse than M and negative otherwise. Given a collection of E, M pairs ($4). we wish to efficiently transfer knowledge from the oracle target's isssi graded preferences A (EEMM to the learners graded preferences ,, (EIM) = (E) f.. by adjusting the parameters w of the learner fw.
We are inspired by simple binary linear SVMs that learn a binary label E [+1,-1) using a linear model (0, .) for input and hinge loss hinge(z) = max(1 2, 0). We express the loss of given
""root" here is distinct from "roof".

---

prediction for as hinge(y(O, 2)) where y(O,2) z) is positive for correct prediction and negative otherwise, regardless of the sign of y.
Addressing how to measure of., [E] M)'s divergence from A M), multiplying the two (as above) would have the same sign benefit as the linear hinge SVM positive product indicates the prefer- ence for E vs. MM is aligned between the oracle and learner. We want more than this, however, since we wish learn from GPC. Instead, therefore, we measure mismatch via the ratio , (E' M)/A(E) M). Immediately, we again have a positive quantity if preferences between oracle and target are aligned, but here grading also matters. A good match makes 5..m (E) (EJM)AAA A [E] M) not only positive but also large. If A is large and positive, 5,,. (E|M) must also be large and positive to make the ratio large and positive, while if A (E)M) is small and positive, ,,,, (E) M) must also be positive but need not be too large to make the ratio large. A similar property holds when A M) is negative. That is, if A (
M) is large and negative, then so would 6,,, (F) need to be to make the ratio large and positive, while A M(F being small and negative allows for 8 (E|M) to be small and negative while ensuring the ratio is large and positive.
On the other hand, a ratio alone is not a good objective to maximize, one big reason being that small changes in the denominator can have disproportionately large effects on the value of the ratio, which can amplify noise and lead to erratic optimization behavior Ideally. we could find a hinge-like loss that will penalize small ratios and reward large ratios. Consider the following:
(8) = log(1 + exp(1 ))
(I)
Here, if A is (very) positive, then ō must also be (very) positive to produce a small loss. If A is (very) negative then ö also must be small to produce a small loss. The absolute value of A determines how non-smooth the ratio is so we include an outer pre-multiplication by A to ensure the slope of the loss, as a function of 6, asymptotes to negative one (or one when A is negative) in the penalty region, analogous to hinge loss, and thus produces numerically stable gradients. Also analogous to hinge, add an extra "1" within the exp() function as a form of margin confidence, analogous to hinge loss that, as with SVMs, expresses distance between the decision boundary and the support vectors. Plots of (8) are shown in Fig. 7 in Appendix F this appendix also discusses the smoothness of L (6) via its gradients, describes a few additional useful hyperparameters, and provides numerically stable solution to the case when A = 0 (thereby solving any 8/0 issues).
Comparing with standard contrastive losses and deep metric learning S a peripteral loss on 5r (EJM) = (E) [nn(M) can be seen as a high-order self-normalizing by A generaliza- tion of triplet loss [108] if E is a heterogeneous and M a homogeneous set of objects. We recover aspects of a triplet loss we set E {v, e and M = {o, wt} where M is the positive pair (close and homogencous) while E is the negative pair (distant from each other and thus diverse pair). With |E| > 2 and |M > 2, we naturally represent high order relationships amongst both the positive group M and the disperse group E (which is apparently rare, S.e We remind the reader that while our peripteral loss could be used for GPC-style contrastive training for representation learning or for RLHF- based transformer alignment, experiments in this paper in 5J on the submodular learning problem.
3.1 Augmented Loss for Augmented Data
Data augmentation is frequently used to improve the generalization of neural networks. Since augmented images represent the same knowledge in principle, they should have the same submodular valuation and also should be considered redundant by any learnt submodular function. Given set E of images, let E' represent a same-size set of augmented images generated after augmenting each image E E. This means any learnt model fa should have (E) = (E') and Ve E E. (c) = (c'). To ensure this is the case, we use an augmentation regularizer Lang E, E') defined as follows:
A2 [E
Lang CangsSmi (
Since augmented images represent the same information, the submodular gain of augmented images relative to non-augmented images should be small or zero meaning (E' (E) 0
In the sequel, use A and where the E, M pair is implicit.
5

---

and Ve E E. fuleee) = fe(eele)
0. To encourage this, we use a redundancy regularizer
Crean (fwi E.E defined as follows:
Crdd E, = > (uu + ( Ef + fuo(elle)))
(3)
In the above, square all quantities to provide extra penalty to larger values, while as quantities such as (E) approach zero, we diminish the penalty.
3.2
Final Loss
With all of the above individual loss components now well described, our final total loss (F) for an E,, M pair becomes:
Swi
(wi A M), (B)M)
LA(EIM) (Ō (EI + Camg (Sri E E, + -reen E, E') + ( M, M')
With a dataset D = {(Ei, M of pairs, the total risk is:
R(w; w: D)
Σ
(E.M)))
(5)
VE(N]
Fig. 1 shows the structure of a DSPN and its learning control flow. Please see appendix G for more details.
AIRW
w +- w V Con (.EM).6.... (E(M))
Orade Targe
(E)
(M)
Mutrodi to goanty Nuppon
DGPN for on set panometeriod
for on
mine (LA1 par www.
mi
The structure of a DSPN and the control flow of how DSPN is trained; parameters are shared between the DSPNs processing E and M sets.
Figure 1:
4 Sampling (E,M) Pairs
DSPN training via the peripteral loss requires a dataset = {(E,, MJ) of pairs of sets where each F,, M; C V. Since the DSPN starts with the pillar stage, the learnt model can then be tested on samples that are outside V as we do in $ Still, cxhaustively training on all pairs of subsets from V infcasible. Therefore, the pairing strategy used to incorporate the sampled sets is a critical compo- nent in our dataset construction. We thus propose several practical, both passive and active, strategies to efficiently sample from this combinatorial space. The passive strategies are heuristic-based, while the active strategies are dependent on either the DSPN as it is being learnt or optionally the target function if it is possible to optimize (fortunately, Table shows target sampling is not necessary). Our description here of these strategies is augmented with further discussion and analysis appendix E
Passive Sampling: If we assume the maximum set size to be K so that |E| < K and |M| < K and a training dataset to have C' classes or clusters, we may generate F,, M pairs two ways. In Style-I, sample homogeneous set of size K from randomly chosen single class and a heterogencous

---

Typel
Typesi Homo
DSPN Feecbark
Tirpell Haterr
Typo Homo.
Type Il Heter.
Type-1 <ote'
Type Horme
Typo-l Heter.
Type-il Heter.
Fewelbaak
Pussire Sets, We consider a simple 2D ground set with clusters/llases, as indicated by the colors. The various types of passively sampled sets depicted (discussed in section [] Type- homogenecus sets are randomll sampled from a single class, while Type-I heterogeneous sets sumpled from the full groud set. Mcanwhile, Type II restricts the ground set to subset classes and samples "clumps" from each of the sampled classes construct the homogeneous and diverse sets from each class to create the heteroge- neous sets, Intuitively, using Type-I/II allows the leart DSPN medel intraclassiinterclass respectively.
Figure 2:
Pairing. actively sample sets by optimizing the DSPN is heing learn option- ally the target function. The depicted graph demon- strates how the actively sampled sets are integrated into D ((E,, M.)]. (. Th red/blue vertices refer pas- sively/actively sampled sets. An edge between two ver- tices indicates that sets from the categories denoted by the vertices used
Figure
(E, M) puirs truin the DSPN. Dashed edges represent non critical pairs.
set of size K randomly over the full dataset. In Style-II, we first choose a random set of C' S C classes, where C' is chosen uniformly at random over [C], and (if C' C) subselect from the ground set a set Vor C V containing only those samples corresponding to those C" classes. To choose an E set, we perform K-Means clustering on Ver. and pick the sample closest each cluster mean to construct our set. To build an .M set, we choose one sample for each class/cluster in Vor and then add nearest neighbors. Importantly, the E and M sets in each pair sampled with Style-II are much more difficult to distinguish than Style-1. We also note that these sampling strategies are imperfect, so the supposedly heterogeneous set may not truly be heterogeneous in relation to its homogeneous counterpart M. However, as discussed in $E the peripteral loss allows us to train DSPN even if the set pairs are imperfectly labeled since the oracle just flips the sign of its preference. Simplified passive 2D sets are shown in Fig. and set-pairing illustration is seen in Fig. 3
its [K/C"=
Sets selected by the passive strategies independent of both the learner and the target function. Thus, due to the combinatorial nature of the problem, there may be discrepancy between what sets are valued highly by the DSPN and/or the target. This leads us to employ actively sampled sets obtained through two approaches. We refer to the first approach as DSPN Feedback, which obtains sets by maximizing or minimizing the DSPN as submodular, we may optimize it over either full ground set V or a class-restricts ground set to get high-valued subsets, where the greedy algorithm can be used for maximization [73 and submodular minimization (28) can be used to find the homogeneous sets (although in practice, submodular minimization heuristics suffice). We refer to the second approach as Target Feedback, where we obtain sets by optimizing the target. The latter approach is only applicable when the target is optimizable (e.g., submodular), which would not the case with a human oracle. While we test "Target Feedback" below, experiments in $5.3 show that it is not necessary for good performance, which portends well for our framework to be used in other GPC contexts (c.g., RLHF learning via human feedback). Thus, while the E, MM pair generation strategies mentioned here are specific to DSPN learning, our peripteral loss could be used to train any deep set or other neural network given access to graded oracle preferences, thus yielding general purpose GPC-style learning procedure.
Active Sampling:
being learnt. As DSPN is
5 Experiments
evaluate the effectiveness our framework by training DSPN to emulate a costly target oracle FL. function. We assert that DSPN training is deemed successful if the subsets recovered by maximizing the learnt DSPN are (1) assigned high values by the target function ($5.1) and (2) are usable for real downstream task such training predictive model 5.5
7

---

Datasets: We consider four image classification datasets: Imagenette, Imagewoof, CIFARI00, and Imagenet100. Imagenette, Imagewoof, and Imagenet100 are subsets of Imagenet- 1k 84 where a subset of the original classes is used. Imagenet100 (resp. CIFAR 100) have 100 classes and 130,000 (resp. 60,000) images, while Imagenette and Imagewoof have 10 classes (and 13,000 images).
DSPN Architecture: We use CLIP ViT encoder [82] for all datasets to get the embeddings that are used as inputs the DSPN which can be seen fixed part of the pillar. We use an additional 2-layer network as the trainable part of the pillar (dw,)): ); for DSPN roof (1w.)) we use a 2-layered We use multiple concave activation functions, i.e., all of (xx E {zr, 0.5 In(1 + 2), tanh (z). 1 - e e= in every layer of the roof (ensuring w. 2 0 during training) and thus allow the training procedure to decide between them. See H for hyperparameter details.
DSF for mmagenette/Imageweer
and I-layered DSF for CIFAR100/maageee//00
Target: We use Facility Location (FI.) as a target whose construction is rather expensive (quadratic) and also does not generalize to held-out data, but this is a key point. That is, we show how we distill from this expensive larget FL cheaper and generalizable DSPN. Each target FL is created by computing real-valued feature vector for each sample and then computing a non-negative similarity between each such vector. We used a CLIP ViT encoder to encode input images, and tuned RBF kernel to construct similarities for our target FLs.
Training and Evaluation: We train up to sets of size | < 100 for all datasets. We show that we generalize beyond this size not just on held-out subsets but even on held-out data. Given ground set V, we construct pairs (F, .)) both passively and actively, as discussed earlier. Please refer G
for the details on training. For the target oracle, we use a facility location function with similarity instantiated using a radial basis function kernel with tuned kernel width. During the evaluation, both learned set functions and target oracle use a held-out ground set V of images, that is, V n V = 0.
5.1 Transfer from Target to Learner
We demonstrate that the target FL assigns high values to summaries that are generated
by the DSPN in Figure 4 Specifically, we determine S is a good quality set if
(((9) has high normalized FL evaluation T([FLT where ft is the target FL and S. is the
set generated by applying cardinality constrained greedy maximization to the target FL. Therefore, we compare different DSPN models based on the normal- ized FL evaluation that their maximiz- attain. We compare DSPN mod- els trained with three different losses: the peripteral loss, the contrastive max- max-margin style structured predic- tion loss 1981. and a regression loss (shown as DSPN (peripteral), DSPN (margin) and DSPN (regression) re- spectively in Figure 4.. Please refer appendix for the definition of base- line losses (Equations 30 and BT). We also compare against randomly gener- ated sets, which are denoted as Ran- dom. From this set of experiments, we find that the DSPN trained with the peripteral loss consistently outper- forms all other baselines across differ- ent summary sizes (budgets) and datasets. Interestingly, the DSPN outperforms random even on budgets greater than 100, despite never having encountered such subsets during training. This provides evidence that our based peripteral loss is the loss of choice for training DSPNs.
Peripteril Loss (surs)
Eegression loss
Mergin Loke
Fondon ection
We evikate four diliount los
Aanddaaa Isee (gen)) based on elfccio ctyechoe ISSN by oifirel meeeeas The dadencee cwtier (ia ratiue corms Ened Jt prann--iuth Barge' surmary sctioion Burger botter p pdoced DSPN hicl was bulted with of the losoos patiotucal bustill. (cmei--oii) astaction llnn dettt-dtt
us
Imagevoot
Imagenae100
Imsganette
CIFAR100
Acres mumrary sine imariced
dotssets we find our proposed pocistual loss nl most fancsoons marggin and regrossion unoherpertom and often are selection
100
130 May daaan Sanaaag Sapaooa
%
furt
Figure 4: Transfer. We compare different loss functions in terms of their effectiveness at training a DSPN.
5.2 Application to Experimental Design
Experimental design involves selecting subset of unlabeled examples from large pool for labeling to create a training set [0) In this section, we evaluate the performance of learnt DSPN based on how well simple linear model generalizes when trained on training set that was chosen by DSPN.
8

---

Imagenette
Imagewoof
CIFAR100
Imagenet100
120
93
DSPN (sunn) [basalin))
Accuracy
CRAiG (oaseling Random (tavelloo)
40
22
50
130 150
52
200
150
200
400
200 000
Size of Training Dataset
Figure 5: Offfine Experimental Design. We compare different summarization procedures, and assess them based on the test accuracy that linear model attains upon being trained on the summary. We find that maximizing the learnt DSPN generates high quality datasets, outperforming existing summarization techniques such as CRAIG and k-centers. In many cases, the DSPN approaches the Target FL even though the latter is aware of the duplicates present in the data. Takeaway: DSPN effectively chooses training samples for labeling from an unlabeled pool.
Imagenette
Imagewoof
CIFAR100
Imagenet
100
Accurccy
60
62
Crfico E0a% tugarr Drandl
Wisse [iace ind.
42
1.0
200 102
250
1.00
202
302
102
505
200
200
Size Training Dataset
Figure 6: Online Experimental Design. The performance of a linear probe, trained based on a subset selected by an algorithm that does not use labels, is reported at varying budgets. DSPN-online achieves far higher performance than other streaming algorithms such as reservoir sampling and VeSSAL and is performs comparably to offlin algorithms. Takeaway: DSPN can effectively select training samples for labeling from a stream of unlabeled data.
We consider an offline setting where we assume the full unlabeled pool is available and an online setting where the unlabeled pool is presented to the model in a non-iid stream. To test the robustness of our framework real-world challenges, we add duplicates such that the ground set is heavily class- imbalanced (the procedure to generate the class-imbalanced set is shown in Appendix (H). Importantly, in these experiments we train with one set V and test on completely held-out set V with Vnv' = 0: that is, the testing DSPN is on an entirely different ground set than the training DSPN.
The offline setting assumes that the full unlabeled pool is accessible by the summa- rization procedure. The results of these experiments are presented in Figure 5 Our approach, denoted as DSPN in the figure, applies greedy maximization to the learnt DSPN to generate the summary. We also consider a cheating experiment by applying greedy to the target FL after removing duplicates from the ground set; we refer to this approach Target FL. Finally, we consider three baseline summarization procedures CRAIG [69], K-centers [89]. and random subset selection 75). The learnt DSPN achieves performance comparable to the target FL in all datasets up budget of 100. Beyond that, the difference between DSPN and the Target FL grows but the DSPN continues to generate higher quality than any of the baselines, showing DSPNs generalize to set sizes beyond the training set sizes.
Offline Setting:
We consider an online setting where the data is presented to the model a non- iid, innsemnncte stream, done in the continual learning literature [63] [8] 2 113]. Unlike the facility location function which requires the full ground set for evaluation, the DSPN can be maximized in streaming manner. Thus, we employ the streaming maximization algorithm proposed by (52) to maximize the DSPN, due to its effectiveness in real-world settings and its lack of additional memory requirements. This approach is referred to as DSPN-online in Figure 6
Online Setting:
We compare our approach against two streaming summarization baselines. The first approach, reservoir sampling [104), is algorithm that enables random sampling of fixed number of items from a data stream as if the sample was drawn from the entire population at once, The second approach, VeSSAL (86). seeks to select samples such that the summary maximizes the determinant of the gram matrix constructed from the model embeddings. We also apply (offline) greedy maximization to the target facility location (Target FL-offline) and the learned DSPN (DSPN-offline), which serve as upper bounds to what is attainable by streaming DSPN maximization.
In Figure 6,
we present quantitative results where a linear model is trained on given streaming summary after labels have been obtained. We find that DSPN-online significantly outperforms the other streaming basclines all datasets. Surprisingly, DfPN-offline and DSPN-online achieve similar

---

performance, demonstrating the flexibility of DSPNs. FL-offtine tends to generate the highest quality summaries, but requires access to the full ground set and assumes duplicates are manually removed.
5.3 Ablations
Table provides Imagenet1 (0 results on sets of size 100 that explore the importance of various components of the DSPN, We
Method
Eval
Offline Ace
Online Acc
DSPN
0.92
67.8
65.9
report three numbers for each ablation: (I)
w/o target feedback
0.93
67.7
66.9
FL Eval which corresponds to the normal- ized FL evaluation discussed in $ 5. (2) Offline Acc which denotes the final accu- racy of a linear model in the offline exper- imental design setting and (3) Online Acc denotes the final accuracy of linear model in the online experimental design setting.
w/o feedback
0.83
47.7
30.1
w/o type-Il sampling
0.64
13.1
10.7
PC rather than GPC
0.90
62.8
63.4
w/o learnt pillar
0.71
39.1
38.0
Deep Set Set Transformer
0.56
9.2
3.5
0.34
13.8
Table Ablations on Imagenet100. The importance of feedback, learnt features, enforcing submodularity, and GPC (in each column, bold best, underline is 2nd best). "w/o feedback" indicates a DSPN model trained without feedback, while "w/o target feedback" is when the oracle is only queried. For Set Transformer, streaming maximization fails to produce summary of the required size (therefore it is omitted). "PC rather than GPC" uses non-graded pairwise comparisons, showing the benefits of grading, consistent with [61]. All results are for a size-100 set.
Removing (FL) Feedback: Active selec- tion is obtained by maximizing the DSPN or Target FL during training (denoted DSPN feedback and Target feedbackk respec- tively). We find that only removing the sets obtained from target feedback has little to no impact on the final performance of the DSPN, suggesting that it is not necessary to optimize the target function. This shows that our framework can be applied to GPC learning even when is not possible to opti- mize the larget, such as with humun oracles. However, we find that completely removing Active selection significantly hurts the final DSPN
We assess the utility of a learnable pillar, by training a DSPN with fully frozen pillar. In this case, we attempt to learn the weights of DSF on random projections of CLIP features. We discover that the DSPN without learnable pillars significantly underperforms its counterpart. We discuss this further in appendix D-
Removing Learnable Pillar:
We study the utility of submodular constraints to learn the target. To this end, we compare DSPN against Deep Set [110] and SelTransformer (55) architecture in the third sec- tion of table I we discover that the absence of submodularity significantly hampers the performance for all the metrics, since the greedy algorithm has no guarantees on an arbitrary set function.
Removing Submodularity:
6 Conclusion and Future Work
We have proposed DSPNs and methods for training/distilling them. Since the computational cost for querying a DSPN independent of dataset size, and the training scheme leverages automatically generated (E, M) pairs, our methods learn practical submodular functions scalably. It may ultimately be possible to scale our training framework to massive heterogeneous datasets to develop foundation DSPNs having strong zero-shot summarization capabilities on wide array of domains. We also propose the peripteral loss which leverages numerically graded relationships between pairs of objects. The graded pairwise preferences are provided from an oracle and are used to learn submodular function that captures these relationships. However, the scope of the peripteral loss extends far beyond training DSPNs and has many applications such as new contrastive representation learning procedures, and learning a reward model in the context of RLHF with real human oracles.
7 Acknowledgments
We thank Suraj Kothawade, Krishnateja Killamsetty and Rishabh Iyer for several early discussions. This work is supported in part by the CONIX Research Center, one of six centers in JUMP, Semiconductor Research Corporation (SRC) program sponsored by DARPA and by NSF Grant Nos. 100-27 and 114367.
10

---

Bibliography
[1] Stephen Adams, Tyler Cody, and Peter A Beling. A survey of inverse reinforcement learning. Artificial Intelligence Review, 55(6):4307-4346 2022.
[2] Rahaf Aljundi, Min Lin, Baptiste Goujaud, and Yoshua Bengio. Gradient based sample selection for online continual learning. arXiv preprint 1rXiv:/903.08671, 2019.
[3] Saurabh Arora and Prashant Doshi. A survey of inverse reinforcement learning: Challenges, methods and progress. Artificial Intelligence, 297:103500, 2021.
[4] F. Bach. Structured
norms through submodular functions, In NIPS, 2010.
[5] Maria Florina Balcan, Florin Constantin, Satoru Iwata, and Lei Wang. Learning valuation functions. COLT, 2011.
[6] Maria-Florina Balcan and Nicholas JA Harvey. Submodular functions: Learnability, structure, and optimization. SIAM Journal on Computing, 47(3):703-754, 2018.
Maria-Florina Balcan, Ellen Vitercik, and Colin White. Learning combinatorial functions from pairwise comparisons. In Conference on Learning Theory, pages 310-335. PMLR, 2016.
[8] Randall Balestriero, Mark Ibrahim, Vlad Sobal, Ari Morcos, Shashank Shekhar, Tom Goldstein, Florian Bordes, Adrien Bardes, Gregoire Mialon, Yuandong Tian, et al. A cookbook of self- supervised learning. arXiv preprint arXiv:2304.122100 2023.
[9] Gordon G Bechtel. The analysis of variance and pairwise scaling. Psychometrika, 32(1))47-65, 1967.
[10] Gordon G Bechtel. A covariance analysis of multiple paired comparisons. Psychometrika, 36(1):35-55, 1971.
[11] Gantavya Bhatt, Yifang Chen, Arnav M. Das, Jifan Zhang, Sang T. Truong, Stephen Mussmann, Yinglun Zhu, Jeffrey Bilmes, Simon S. Du, Kevin Jamieson, Jordan T. Ash, and Robert D. Nowak. An experimental design framework for label-efficient supervised finetuning of large language models, 2024.
[12] Jeff Bilmes. Submodularity in machine learning and artificial intelligence, 2022.
[13] Jeffrey Bilmes and Wenruo Bai. Deep submodular functions. arXiv preprint 17X1:17011,8939, 2017.
[14] Ralph Allan Bradley and Milton E Terry. Rank analysis of incomplete block designs: the method of paired comparisons. Biometrika, 39(3/4):324-345, 1952.
[15] Niv Buchbinder, Moran Feldman, Joseph Naor, and Roy Schwartz. Submodular maximization with cardinality constraints. In Proceedings of the twenty-fitth annual ACM-SIAM symposium Discrete algorithms,, pages 1433-1452. SIAM, 2014.
[16] Gruia Calinescu, Chandra Chekuri, Martin Pal. and Jan Vondrák. Maximizing monotone submodular function subject to matroid constraint. SIAM Journal on Computing, 40(6):1740- 1766, 2011.
[17] L Elisa Celis, Amit Deshpande, Tarun Kathuria, and Nisheeth Vishnoi. How be fair and diverse? arXiv preprint arXiv: 2016.
[18] Arslan Chaudhry, Marc' Aurelio Ranzato, Marcus Rohrbach, and Mohamed Elhoseiny. Effi- cient lifelong learning with a-gem. In /CLR, 2019.
[19] Paul Christiano, Jan Leike, Tom B. Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences, 2023.
[20] William H Cunningham. Decomposition of submodular functions. Combinatorica, (
1983,

---

[21] William H Cunningham. Optimal attack and reinforcement of network. Journal of the ACM (JACM). 52,,),54--561, 1985.
[22] Abir De and Soumen Chakrabarti. Neural estimation of submodular functions with applica- tions to differentiable subset selection. Advances Neural Information Processing Systems, 35:19537-19552, 2022.
[23] Brian Dolhansky and Jeff Bilmes. Deep submodular functions: Definitions and learning. Advances in Neural Information Processing Systems, 29, 2016.
[24] Ethan Elenberg. Rajiv Khanna, Alexandros G Dimakis, and Sahand Negahban. Restricted strong convexity implies weak submodularity. The Annals of Statistics, 46(6B):3539- -3668, 2018.
[25] Hossein Esfandiari, Amin Karbasi, and Vahab Mirrokni. Adaptivity in adaptive submodularity. In Conference on Learning Theory, pages 1823-1846. PMLR, 2021.
[26] Moran Feldman, Amin Karbasi, and Ehsan Kazemi. Do less, get more: Streaming submodular maximization with subsampling. Advances in Neural Information Processing Systems, 31, 2018.
[27] Pierre Foret, Ariel Kleiner, Hossein Mobahi, and Behnam Neyshabur. Sharpness-aware minimization for efficiently improving generalization. In International Conference Learning Representations, 2021.
[28] Satoru Fujishige. Submodular functions and optimization. Elsevier, 2005.
[29] Alireza Ghadimi and Hamid Beigy. Deep submodular network: An application to multi-
document summarization. Expert Systems with Applications, 152:1 13392, 2020.
[30] Justin Gilmer, Behrooz Ghorbani, Ankush Garg, Sneha Kudugunta, Behnam Neyshabur, David Cardoze, George Dahl, Zachary Nado, and Orhan Firat. A loss curvature perspective on training instability in deep learning. arXiv preprint 10.0046,,, 2021.
[31] Michel Goemans, Nicholas JA Harvey, Satoru Iwata, and Vahab Mirrokni. Approximat- ing submodular functions everywhere. In Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms, pages 535-544. SIAM, 2009.
[32] Daniel Golovin and Andreas Krause. Adaptive submodularity: A new approach to active learning and stochastic optimization. In Proceedings of the 23rd Annual Conference on Learning Theory (COLT), 2010.
[33] Joy Paul Guilford. Psychometric methods. 1954.
[34] Andrew Guillory and Jeff A Bilmes. Online submodular set cover, ranking, and repeated active learning. Advances in neural information processing systems, 24, 2011.
[35] Michael U Gutmann and Aapo Hyvärinen. Noise-contrastive estimation of unnormalized statistical models, with applications to natural image statistics. Journal of machine learning research, 13(2). 2012.
[36] Michael Gygli, Helmut Grabner, and Luc Van Gool. Video summarization by learning submodular mixtures of objectives. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2015.
[37] Christopher Harshaw, Ehsan Kazemi, Moran Feldman, and Amin Karbasi. The power of subsampling in submodular maximization. Mathematics of Operations Research, 47(2):
1393, 2022.
[38] Max Horn, Michael Moor, Christian Bock, Bastian Rieck, and Karsten Borgwardt. Set functions for time series. International Conference on Machine Learning, pages 4363-4363. PMLR, 2020.
12

---

[39] Rishabh Iyer, Stefanie Jegelka, and Jeff Bilmes. Fast semidifferential-uun -based submodular function optimization. In International Conference on Machine Learning, pages 855-863. PMLR, 2013.
[40] Rishabh K lyer and Jeff Bilmes. Submodular optimization with submodular cover and submodular knapsack constraints. Advances in neural information processing systems, 26, 2013.
[41] Stefanie Jegelka and Jeff Bilmes. Submodularity beyond submodular energies: coupling edges in graph cuts. In CVPR 20/ pages 1897-1904. IHEE, 2011.
[42] Zhongyu Jiang, Wenhao Chai, Lei Li, Zhuoran Zhou, Cheng- Yen Yang, and Jenq-Neng Hwang. Unihpe: Towards unified human pose estimation via contrastive learning. arXiv preprint arXiv:2311.16477 2023.
[43] Ehsan Kazemi, Shervin Minaee, Moran Feldman, and Amin Karbasi. Regularized submodular maximization at scale. In International Conference Machine Learning, pages 5356-5366.
PMLR, 2021.
[44] Krishnateja Killamsetty, Sivasubramanian Durga, Ganesh Ramakrishnan, Abir De, and Rishabh Iyer. Grad-match: Gradient matching based data subset selection for efficient deep model training. In International Conference Machine Learning, pages 5464 5474. PMLR, 2021.
[45] Krishnateja Killamsetty, Durga Sivasubramanian, Ganesh Ramakrishnan, and Rishabh Iyer. Glister: Generalization based data subset selection for efficient and robust learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 8110-8118, 2021.
[46] Minyoung Kim. Differentiable expectation-mmxxiizzzin for set representation learning. In International Conference on Learning Representations, 2022.
[47] Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 411iv:1412.6900 2014.
[48] Pang Wei Koh, Thao Nguyen, Yew Siang Tang, Stephen Mussmann, Emma Pierson, Been Kim, and Percy Liang. Concept bottleneck models. In International conference on machine learming, pages 5338-5348. PMLR, 2020.
[49] Suraj Kothawade, Nathan Beck, Krishnateja Killamsetty, and Rishabh Iyer. Similar: Submod- ular information measures based active learning in realistic scenarios, 2021.
[50] Alex Kulesza, Ben Taskar, al. Determinantal point processes for machine learning. Founda- tions and Trends@ in Machine Learning.
226, 2012.
[51] Chandrashekhar Lavania and Jeff Bilmes. Auto-Summarizatin:: Step Towards Unsupervised Learning of a Submodular Mixture, pages 396-404 SIAM International Conference on Data Mining, 2019.
[52] Chandrashekhar Lavania, Kai Wei, Rishabh Iyer, and Jeff Bilmes. A Practical Online Frame- work for Extracting Running Video Summaries under a Fixed Memory Budget, pages 226 234.. SIAM International Conference on Data Mining (SDM), 2020.
[53] Eugene Lawler. Combinatorial optimization: networks and matroids. Holt, Rinehart, and Winston, 1976.
[54] Jon Lee, Vahab S Mirrokni, Viswanath Nagarajan, and Maxim Sviridenko. Non-monotone submodular maximization under matroid and knapsack constraints. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 323-332, 2009.
[55] Juho Lee, Yoonho Lee, Jungtaek Kim, Adam Kosiorek, Seungjin Choi, and Yee Whye Teh. Set transformer: A framework for attention-based permutation-invarian neural networks, In International conference machine learning, pages 3744-3753, PMLR, 2019.
13

---

[56] Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne VanBriesen, and Natalie Glance. Cost-effective outbreak detection in networks. In Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 420 429, 2007.
[57] H. Lin and J. Bilmes. How to select good training-data subset for transcription: Submodular active selection for sequences. In "Proc. Annual Conference of the International Speech Communication Association (INTERSPEECH)" 20099.
[58] H. Lin and J. Bilmes, An application of the submodular principal partition to training data subset selection. In NIPS workshop on Discrete Optimization in Machine Learning, 2010.
[59] Hui Lin and Jeff Bilmes. A class of submodular functions for document summarization. In Proceedings of the 49th annual meeting of the association for computational linguistics: human language technologies, pages 510-520, 2011.
[60] Hui Lin and Jeff A Bilmes. Learning mixtures of submodular shells with application to document summarization. arXiv preprint arXiv:1210. 2012.
[61] Harriet Lingel, Paul Bürkner, Klaus Melchers, and Niklas Schulte. Measuring personality when stakes are high: Are graded paired comparisons a more reliable alternative to traditional forced-choice methods? 12 2022. PsyArXiv Preprints, Manuscript in press.
[62] Yuzong Liu, Kai Wei, Katrin Kirchhoff, Yisong Song, and Jeff Bilmes. Submodular feature selection for high-dimensional acoustic score spaces. In 2013 IEEE International Conference on Acoustics, Speech and Signal Processing, pages 7184-7188 IEEE, 2013.
[63] David Lopez-Paz and Marc' Aurelio Ranzato. Gradient episodic memory for continual learning. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[64] László Lovász. Matroid matching and some applications. Journal of Combinatorial Theory, Series B, 28(2):208-22 1980.
[65] R Duncan Luce. Individual choice behavior: A theoretical analysis. Wiley, 1959.
[66] Zelda Mariet, Mike Gartrell, and Suvrit Sra. Learning determinantal point processes by corrective negative sampling. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 2251 2251-2 PMLR, 2019.
[67] Grégoire Mialon, Dexiong Chen, Alexandre d' Aspremont, and Julien Mairal. A trainable optimal transport embedding for feature aggregation and its relationship to attention. arXiv preprint arXiv:2006. 102.000...00... 22065, 2020.
[68] Michel Minoux. Accelerated greedy algorithms for maximizing submodular set functions. In Optimization Techniques: Proceedings of the 8th IFIP Conference on Optimization Techniques Würrzuurg. September 5-9, 1977, pages 234 243.243..5 Springer, 2005.
[69] Baharan Mirzasoleiman, Jeff Bilmes, and Jure Leskovee. Coresets for data-efficient training of machine learning models. In International Conference on Machine Learning, pages 6950 6960. PMLR, 2020.
[70] Baharan Mirzasoleiman, Amin Karbasi, Rik Sarkar, and Andreas Krause. Distributed submod- ular maximization. The Journal of Machine Learning Research, 17(1):830-8373,, 2016.
[71] Marko Mitrovic, Ehsan Kazemi, Moran Feldman, Andreas Krause, and Amin Karbasi. Adap- tive sequence submodularity. Advances in Neural Information Processing Systems, 32, 2019.
[72] Marko Mitrovic, Ehsan Kazemi, Morteza Zadimoghaddam, and Amin Karbasi. Data summa- rization at scale: A two-stage submodular approach. In International Conference on Machine Learning, pages 3596-3605. PMLR, 2018.
14

---

[73] George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. An analysis of approxima- tions for maximizing submodular functions Mathematical programming, 14:265-294 1978.
[74] JC Nunnally and IH Bernstein. Psychometric theory third edition. megraw- hili. Inc. https://doi. org/34567890 DOCmoC, 998765, 1994.
[75] Patrik Okanovic, Roger Waleffe, Vasilis Mageirakos, Konstantinos E Nikolakakis, Amin Karbasi, Dionysis Kalogerias, Nezihe Merve Gürel, and Theodoros Rekatsinas. Repeated random sampling for minimizing the time-lo-accuracy of learning. Openreview, 2024.
[76] Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models follow instructions with human feedback. Advances in Neural Information Processing Systems, 35:27730-27744, 2022.
[77] J.G. Oxley. Matroid Theory: Second Edition. Oxford University Press, 2011.
[78] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019.
[79] Manish Prajapat, Mojmír Mutný, Melanie N Zeilinger, and Andreas Krause. Submodular reinforcement learning. arXiv preprint arXiv:2307.13377 2023.
[80] Lue Pronzato and Andrej Pázman. Design of experiments in nonlinear models. Lecture notes in statistics, 21 212(1), 2013.
[81] Charles R Qi, Hao Su, Kaichun Mo, and Leonidas J Guibas. Pointnet: Deep learning on point sets for classification and segmentation. In Proceedings of the IEEE conference on computer vision and paltern recognition, pages 652-660, 2017.
[82] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever. Learning transferable visual models from natural language supervision, 2021.
[83] Siamak Ravanbakhsh, Jeff Schneider, and Barnabas Poczos. Equivariance through parameter- sharing. In International conference on machine learning, pages 2892-2901. PMLR, 2017.
[84] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma. Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei- Fei. ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (LJCV), 115(3):211-252, 2015.
[85] Mehraveh Salehi, Amin Karbasi, Dustin Scheinost, and R Todd Constable. A submodular ap- proach create individualized parcellations of the human brain. In Medical Image Computing and Computer Assisted Intervention- MICCAI 2017: 20th International Conference, Quebec City, QC. Canada, September 11-13, 2017, Proceedings, Part I 20, pages 478 485. Springer, 2017.
[86] Akanksha Saran, Safoora Yousefi, Akshay Krishnamurthy, John Langford, and Jordan T. Ash. Streaming active learning with deep neural networks, 2023.
[87] Henry Scheffe. An analysis of variance for paired comparisons. Journal of the American Statistical Association, 47(259):381-424 4000, 1952.
[88] Alexander Schrijver. Combinatorial optimization: polyhedra and efficiency, volume 24. Springer Verlag, 2003.
[89] Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. arXiv preprint arXiv:1708.0044: 2017.
[90] Roger N Shepard. Stimulus and response generalization: stochastic model relating general- ization to distance in psychological space. Psychometrika, 22(4):325-345, 1957.
15

---

[91] D Amnon Silverstein and Joyce E Farrell. Efficient method for paired comparison. Journal of Electronic Imaging, 10(2):394-333 2001.
[92] R. Sipos, P. Shivaswamy, and T. Joachims. Large-margin learning of submodular summariza- tion methods. arXiv preprint arXiv: 10.2 2011.
[93] Ruben Sipos, Pannaga Shivaswamy, and Thorsten Joachims. Large-margin learning of submod- ular summarization models. In Walter Daelemans, editor, Proceedings of the 13th Conference of the European Chapter of the Association for Computational Linguistics, pages 224-233, Avignon, France, April 2012. Association for Computational Linguistics.
[94] Leslie N Smith. Cyclical learning rates for training neural networks, In 2017 IEEE winter conference on applications of computer vision (WACV), pages 464-472. IEEE, 2017.
[95] Suraj Srinivas, Kyle Matoba, Himabindu Lakkaraju, and François Fleuret. Efficient training low-curvature neural networks. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
[96] Peter Stobbe and Andreas Krause. Efficient minimization of decomposable submodular functions. Advances in Neural Information Processing Systems, 23, 2010.
[97] Scott Sussex, Caroline Uhler, and Andreas Krause. Near-optimal multi perturbation exper- imental design for causal structure learning. Advances in Neural Information Processing Systems, 34:777-788, 2021.
[98] Ben Taskar, Vassil Chatalbashev, Daphne Koller, and Carlos Guestrin. Learning structured prediction models: A large margin approach. In Proceedings of the 22nd international conference on Machine learning, pages 896-999 906-903,222 2005.
[99] Louis L. Thurstone. A law of comparative judgment. Psychological Review, 34:273-2786, 1927.
[100] Yonglong Tian, Dilip Krishnan, and Phillip Isola. Contrastive multiview coding. In Com- puter Vision-ECCV 2020: 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part XI 16, pages 776-794. Springer, 2020.
[101] Ehsan Tohidi, Rouhollah Amiri, Mario Coutino, David Gesbert, Geert Leus, and Amin Karbasi. Submodularity in action: From machine learning to signal processing applications. IEEE Signal Processing Magazine, 37(5):120-133)) 2020.
[102] Sebastian Tschiatschek, Rishabh K Iyer, Haochen Wei, and Jeff A Bilmes. Learning mixtures of submodular functions for image collection summarization. Advances in neural information processing systems, 27, 2014.
[103] Sebastian Tschiatschek, Aytunc Sahin, and Andreas Krause. Differentiable submodular maximization. arXiv preprint arXiv: arXiv:1803.011 1803.0/785 2018
[104] Jeffrey S. Vitter. Random sampling with a reservoir. ACM Trans. Math. Softw, 11(1):37-57, 1985.
[105] Yuanhao Wang. Qinghua Liu, and Chi Jin. Is rlhf more difficult than standard rI? theoretical perspective. In thiirty-sventth Conference on Neural Information Processing Systems, 2023.
[106] Kai Wei, Rishabh Iyer, and Jeff Bilmes. Submodularity in data subset selection and active learning. In International conference on machine learning. pages 1954-1963. PMLR, 2015.
[107] Kai Wei, Yuzong Liu, Katrin Kirchhoff, and Jeff Bilmes. Unsupervised submodular subset selection for speech data. 2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 4107-4111, IEEE, 2014.
[108] Kilian Q Weinberger and Lawrence Saul. Distance metric learning for large margin nearest neighbor classification. Journal of machine learning research, 10(2), 2009.
16

---

[109] Christian Wirth, Riad Akrour, Gerhard Neumann, Johannes Fürnkranz, et al. A survey of preference-based reinforcement learning methods. Journal of Machine Learning Research, 18(136):1-46, 2017.
[110] Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander Smola. Deep sets. Advances in neural information processing systems, 30, 2017.
[111] Wenhao Zhan, Masatoshi Uchara, Nathan Kallus, Jason D Lee, and Wen Sun. Provable offline reinforcement learning with human feedback. arXiv preprini arXiv:2305. 14816, 2023.
[112] Yan Zhang, Jonathon Hare, and Adam Prugel-Bennett. Deep set prediction networks. Advances in Neural Information Processing Systems, 32, 2019.
[113] DeiWei Zhou, Qi-Wei Wang, Zhi-Hong Qi, Han-Jia Ye, De-Chuan Zhan, and Ziwei Liu. Deep class-incremental learning: A survey, 2023.
[114] Yuxun Zhou and Costas Spanos. Causal meets submodular: Subset selection with directed information. Advances Neural Information Processing Systems, 29, 2016.
[115] Banghua Zhu, Jiantao Jiao, and Michael Jordan. Principled reinforcement learning with human feedback from pairwise k-wise comparisons. arXiv preprint arXiv:230..11270. 2023.
[116] George Kingsley Zipf. The psycho-biology of language: An introduction to dynamic philology. Routledge, 2013.
17

---

A Other Related Work
In addition to the previously discussed literature in $ that addresses learning through pairwise com- parison, human preference elicitation, and contrastive learning, this section provides a comprehensive review of both theoretical and empirical studies related to the learning of set functions.
A.1 Relationship to contrastive learning
We are inspired by contrastive learning R, which has pushed the boundaries of deep learning by leveraging the massive information in unlabeled data. Unlike standard supervised learning which teaches models to associate samples to human-supplied labels, contrastive learning encourages models to capture relationships between pairs, groups, or sections of unlabeled samples. It does this by "contrasting" positive pairs (i.e., similar data points) against negative pairs (dissimilar data points), Mathematically, this approach uses loss functions that encourage the model to learn embeddings where positive pairs become "close" (according to some distance measure), while negative pairs become "far." A common setting is the contrastive loss, such as the triplet loss or the Siamese network loss. For instance, in the triplet loss framework, the model is trained on triplets of data points consisting of anchor x, positive example x+ (similar to the anchor), and negative example x (dissimilar from the anchor). Optimizing a model with such a loss function encourages a representation that respects these positive/negative pairwise preferences.
On the other hand, such contrastive approaches are analogous to binary-only pairwise comparison elicitations. That is, existing contrastive losses neither utilize information regarding how positive the pair x, nor how negative the pair x; x is. A more nuanced graded comparison, available, would be improvement. In fact, the benefit of graded comparisons is analogous to the benefits of using soft over hard labels in supervised training (say from model distillation) which has benefits in uncertainty representation, regularization, noise mitigation, adjustable smoothness via softmax temperature, and more efficient knowledge transfer. Another limitation of previous contrastive learning is that it operates only with positive negative groups of size two (pairs) rather than larger groups. While it is often the case that the anchor æ is contrasted with many negative examples, is always done so pairwise, considering each x= with x together in sum of pairwise terms. Also, while [100] [42 is the only work we are aware of that considers more than two positive examples at time, each of these positive samples is again considered only paired up with a negative sample, leading (+) pairings with k positive examples. Sums of pairwise terms do not allow for the consideration of higher order relationships, c.g., a given pair might be measured differently in the context of a third sample. In addition to addressing the two aforementioned problems, DSPNs and our GPC-style loss addresses this issue as well, although our learning goal in this paper is learning submodularity not in representation learning (the latter of which we leave to future work).
A.2 Learning Non-submodular Set functions
Recently, there has been a growing focus on leveraging data-driven neural methods for estimating set functions, with practical applications spanning anomaly detection, amortized clustering of mix- ture models, and point cloud classification [81]. Common to these applications is the fundamental approach of embedding each element within a set into dense embeddings, followed by permutation- invariant aggregation (set-to-vector transformation), and subsequent integration into a deep neural network [10 38 83 The significance of incorporating interaction among set elements has been emphasized by (55] who argue that conventional aggregations, such as average-pooling can be interpreted as a specialized form of attention. Consequently, they propose an attention-basee architec- ture known as the set-trans eet-transformer. Building upon this, [67] have made computational enhancements architecture. Lastly, there has been a recent exploration into a probabilistic
to the attention- interpretation of set-to-vector transformations [113] (6),, further refining the methodology.
The works mentioned above diverge from our approach for several reasons. Firstly, they primarily focus on supervised learning oracles utilizing static datasets to learn neural parameters, whereas our method draws inspiration from max-margen contrastive learning and employs dynamically updated dataset. Secondly, these existing works lack architectural and/or optimization constraints ensuring the submodularity of the learned set function, in contrast to our work on learning deep submodular functions, where submodularity is explicitly guaranteed. However, for comprehensive evaluation against existing literature, we include Deep Sets and Tea-Transfrrmrr as baseline for comparison. Thirdly, the set sizes used in these works are much smaller (30 in many experiments)
18

---

compared to ours which go up to 500. Lastly, the learned set function in these works lacks clear interpretation associated with extremal sets that (locally) maximize or minimize the set function. In contrast, our Deep Submodular Function (DSF) yields maximizatioo//iniiiratiii
sets upon
It noteworthy that the choice of submodular function as the inductive bias may not be essential for certain tasks, such point-cloud classification and amortized clustering of mixture models. However, it proves to be a plausible inductive bias in scenarios where the objective is to count unique characters [100] 113 46 (55, since it can be exactly be expressed as partition matroid rank function, which lies in the family of deep submodular function.
Beyond neural approaches, one of the previous works [66] has also considered learning Determinantal Point Process, or DPPs [50), by learning the (n²) similarity matrix by noise contrastive estimation B51. However, their learning procedure is different from ours, and sampling from DPP is much more computationally expensive than maximizing submodular function.
A.3 Theoretical Work on Learning Submodular Functions
Numerous works have investigated strategies for understanding submodular functions from the- oretical perspective. [31] examined the approximation of an oracle for every subset, utilizing a multiplicative approximation approach to approximate the submodular polyhedron of the oracle using Löwner ellipsoids. In contrast, [3 6 focused on approximating the oracle with high probability on sets sampled from specific distributions (often referred as Probably Mostly Approximately Correct (PMAC) learning) by transforming the problem into the identification of linear separators. Notably, 66 demonstrated the impracticality of approximating any arbitrary monotone non-decreasing sub- modular function to arbitrary closeness under PMAC learning in polynomial queries. Subsequently, 7 proposed an algorithm for learning the oracle through pairwise comparisons in polynomial queries. While this work shares theoretical commonalities with ours, it is important to highlight that [ examined set pairs sampled from a static distribution, contrasting with our approach, which involves a dynamically changing distribution of set pairs due to our submodular feedback. Remarkably, across the aforementioned works, the learned functions exhibit a form that can be represented easily using a Deep Submodular Function (DSF), facet that our work incorporates and explores further.
A.4 Neural Estimation of Submodular Functions
Since submodular functions have 2 degrees of freedom, empirical approaches of learning submod- ular functions restrict the search space to parametric subclass such as feature-based functions or DSFs. Early fata-driven learning techniques use the max-margin structured prediction framework introduced in (98). which requires human annotators to manually construct summaries/sets that should
93 36 29]. These approaches have consistently demonstrated that learned coefficients, opposed to handcrafted ones, result in submodular functions that can generate much higher quality summaries. However, these approaches depend
be assigned high values by the learnt submodular function [60, 102
summaries which can be prohibitively expensive to procure at scale. Furthermore, that the features suitable for the feature-based function are not learned, unlike our work where we jointly learn features and associated parameters for the submodular function. Despite the empirical success of this framework, these approaches all require sets chosen by humans which are difficult to procure scale.
More recently. 22 proposed to estimate submodular function using recursive composition with learned concave function, arguing that the lack of a "good" concave function is weakness of DSF (and only used one concave function in their experiments). In our work, we alleviate this by showing that one can learn good DSF by training with multiple concave functions simultaneously with varying degrees of saturation. It should also be noted that there is no theoretical discussion if the representation capacity of the function class strictly increases with more recursive steps, unlike DSF, where the capacity strictly increases with additional layers. Furthermore, they learn the parameters in supervised manner, given the annotated high-valued summaries, unlike our work which does so in self supervisdd fashion. Lastly, the learned modular function for DSF has the interpretation of capturing concepts (appendix [] H which is not in their case. Remarkably, it is interesting extension where one combines the technique proposed in 22 to learn the concave function jointly with our technique for learning the parameters.
[T proposes an unsupervised framework to learn submodular functions, similar to our work. Their approach involves the maximization of a handcrafted objective function, evaluating the quality of
19

---

weights through measurements of submodular function properties like curvature and sharpness. Notably, they do not engage the simultaneous joint learning of features alongside parameters and instead they first train an auto-encoder to get the features. To the best of our knowledge, no existing studies have effectively undertaken the joint learning of submodular function parameters and features, a key aspect of our proposed methodology.
Finally, we note the existence of related work using the same nomenclature, DSPN, introduced by [122, which stands for Deep Set Prediction Network. The primary objective of 122 is to predict a set based on dense features. In contrast, our research focuses on the development of a deep submodular function (DSF) capable of generating sets through optimization.
B Submodular Functions and Weighted Matroid Rank
Submodular set functions effectively capture notions of diversity and representativeness. Continuing on from ST it known that they are useful in machine learning in the context of data subset selection | 45 106), feature selection [62], summarization [59]. active learning [16]] 49), experimental design more recently in reinforcement learning [7 and several other areas that involve some
form of discrete optimization. Submodular functions also appear naturally in many other areas, such
as theoretical computer science and statistical physics [00 12]
Submodular functions are also of interest since they enjoy properties sufficient for efficient opti- mization. For a ground set of size n, they lie in a cone of dimension 2" in R²"", but can still be minimized exactly without constraints in polynomial time (28). Even though submodular function maximization is NP-hard, it offers a fast constant factor approximation algorithm, for instance in the aurdinality-constranne case, greedy results in 1/c guarantee for polymatroid functions [73 68 Similarly one can give guarantees for other constrained cases such as knapsack constraint or more complicated independence or matroid constraints [15 16 40 39].
In this section, we offer a brief primer on submodularity and their relationship to matroid rank.
Any function f 2 + IR that maps from subsets of some underlying ground set V of size [V] = n called a discrete set function. For a set function to be submodular, it must satisfy the property of diminishing returns. This means that for any X C Y C V and any e E V \ Y the gain of adding v to the smaller set is larger than the gain of adding to the larger set, meaning:
f(e[X) & f(X - f(x) 2
& f(ulY)
(6)
We use the (conditional) gain notation f(e(X) f(XU f regularly in the paper. We also assume also that all submodular functions are monotone non-decreaiing (or just monotone). which means that for any X C Y we have that S(X) S J(Y) and non-negative, meaning that S f(X) for any X C V. We also assume ʃ is normalized so that at the emptyset f(0)) = 0. Such normalized monotone non-decreasing submodular functions necessarily are always non-negative, and
are commonly referred to as polymatroid functions 12 20 21 64).
If Eqn (6) holds with equality for all sets, then the function is referred to as modular function which implies that f can be equated with length n vector, that is for all X C V, f(X) - Exex fx), which means the vector associated with f is (J(v): E V) E R", We often use simplified notation for modular functions - that is, given a length n vector m E IR"" we can define the modular function m. 2 RR as m(A) A) Eaea m(a).
If the incquality in Eqn (6) holds in the reverse, meaning
f(x|X)
- s(x) - u s(ol))
then the function is known as a supermodular function.
For completeness, we note that an equivalent definition of submodularity would say that for any two sets A, B C V, we have that (A) + f(B) 2 (Au B) f(An B). It is not hard to show that this
and Inequality 6 are identical 12 28
Given finite V and set of subsets I (7,, I2.... }. the pair (V,T) is known as a system.
Matroids
553
are useful algebraic structures that are strongly related to submodular func- Given a finite ground set V of size [V| n, matroid M is set system that consists of
77 88
tions 28
20

---

the pair (V,Z) where V is said ground set and I = 12.12..... } is a set of subsets of V, meaning 1, S V for all i. To define matroid M we say M (V.I). The subsets I are known as the indepen- dent sets (meaning, for any 1 E T. is said to be independent) and they have certain properties that make this the set system interesting and useful. Formally, a matroid is defined as follows:
Definition 5 (Matroid). Given ground set V of size [V] = n, matroid M (V, is a system where the set of subsets I = (I1. .2.....) have the following properties:
1. II
2. If I and I' I, then l' E E
3. For any I, I with [T] < (T", there exists a 1' \ I such that I [v EI.
Matroids generalize the algebraic properties of vectors in a vector space, where independence of set corresponds to sets of vectors that are linearly independent. If we think V as set of indices of vectors, and A = {{11 a...... J S V. then the A being independent corresponds to the vectors associated with A being linearly independent. Matroids however capture the algebraic properties of independence and there are valid matroids that can not be representable by any vector space. Note also that the algebraic structure is similar to that of collections of random variables that might or might not be statistically independent.
While there many types and useful properties of matroids, the rank of matroid measures the independence of a set based on the largest independent set that it contains, namely
rank (A)
max
An IEZ
max : S A and B I}
(8)
For any matroid, the rank function is submodular, meaning for any A, B S V. ( + rank (B) rank (AUB)++ +rank) (A For example, the function f(A) min([A], a) with integral valued is a classic concave-compose with modular function (which is thus submodular) but is also the rank function for partition matroid with one partition block and limit of a. matroid rank function is also a polymatroid function since rank (0) 0 and M I ra whenever A C B.
A matroid rank functions can be significantly extended when it is associated with a non-negative vector m R of length [V| n. With such vector, can define weighted matroid rank function that returns the maximum weight of any base of a set A:
Definition (Weighted Matroid Rank Function). Given a matroid M = (V,I) and a non-negative vector m. E TR, the weighted matroid rank function for this matroid and vector is defined as:
Ma (A) = max m I)
TEZ
A weighted matroid rank function still submodular and is still a polymatroid function. In fact, weighted matroid rank functions generalize many much more recognizable functions. Here several examples.
1. Consider free matroid M I) where I = 2V. This means that all 2n subsets of V are independent in the matroid. Then given non-negative vector m E R the weighted matroid rank function has the form rank Mnn (A) EaEA m(a). thus the weighted matroid rank function is just the modular function m.
-hiss
2. Consider one-partition matroid rank function with limit 1. This is a matroid M (V,I) where I {A C V |A| 1}, meaning all sets of size one are independent but no other set is independent in the matroid. Given nen-negative vector m E IR!V the weighted matroid rank function has the form rank,,m (A) max m(()).
3. The facility location function can be seen as the sum of a weighted matroid rank functions using the same matroid as the previous example but using different weights for each term in the sum. That is, given a similarity matrix [S] of non non-negative entries, the facility location function has form f(A) Ei= max Sai- Hence, using the same matroid as
the previous case, the facility location takes the form f(A) = EM rank (A) where 5. is the th column of the matrix.
21

---

Another interesting (and apparently previously unreported) property of weighted matroid rank functions is that they are always permutation invariant the same sense deep set function [T0]] is permutation invariant. Firstly, we restate the definition of permutation invariance from [100]
Definition 7 (Permutation Invariance (TO)). A function f -2V + R acting on seis said to be permutation invariant if the function is invariant the order of objects in the set. That is for any
CCV V with = (01, 02,, amm. and for any permutation π A + A, we have that for any set f((a1, (2.1,00,.--.. 02,-0-; 0.m) ({ (a2))....7 ((m)))
Thus, permutation invariance means that the order in which elements are considered or arranged does affect the outcome of the function that applied to set. For the weighted matroid rank function, this means that if we take a subset A C V and permute its elements, the rank m. (A) stays the same. The reason is because the rank function is concerned only with the elements present in the subset, not the order in which they are listed. Thus, permutation invariance aligns with the properties of matroids as we formalize in the next lemma.
Lemma (Permutation Invariance of Weighted Matroid Rank). The weighted matroid rank rank function m. for matroid M (V,I) with any non-negative vector m. E TR. is permutation
invariant.
Proof. The weighted matroid rank function for matroid M = (V,Z) is defined as
rank.. (A) maxx m (AAn)) IET
max
Σ
m(a)
(10)
IEI
aEAnn
and since nowhere in this definition are the order of the elements in A used, but rather only sum over some of the elements as shown on the right hand side of the above, the function is permutation invariant. This also immediately follows given Proposition
In fact, this property true for any submodular function. Proposition 8. Submodularity and Permutation Invariance. Any submodular set function f 2V IR is permutation invariant.
C Primer on and Novelty over Deep Submodular Functions
In this section, we offer a brief background on deep submodular functions (DSFs) and demonstrate how our results in the present paper are not just incremental over this previous work rather the present paper offers significant novelty over, as far as we can tell from an extensive literature search, previously published papers.
(96] proposed scalable algorithm for minimizing a class of submodular functions known as de- composable functions. In general, given collection of modular functions, {m.)a where each m. V + R4 and Φ, a monotone non-decreasing, normalized ((0) = 0 and non-negative concave function,
N
f(A) = Σ Φ (A:(
is said to be a "decomposable" function.
In machine learning, objects of interest are often represented by featurizing them into finite- dimensional vector space. If U (u1, u2, (nnin indexes the dimensions, then for any example
E V the modular function my (v) (m (v), muy (u)...., .., Majer (v))² represents the features of
2. (v) can be interpreted in several ways such as the degree of presence of th concept
similar to concept bottleneck models (48] or even the count of an n- n-gram feature [107] 59 60]. With
this nomenclature, we re-define decomposable submodular functions as feature-based functions that
has the form:
S(A)
Σ waDa (A)) weU
(11)
where w represents a non-negative weight for each feature. The gain of adding examples with more of the property represented by feature u diminishes the set gets larger due to concave composition and
22

---

the diminishing returns of the concave function. Therefore, intuitively the set X S V that maximizes the feature-based function would comprise examples that produce a diverse set of features according to the features' properties.
One issue with the feature-based function happens when there is redundancy between two features u4 and uj. For instance, if the features are count of n-grams, and since higher-order n-grams encompass lower-order n-grams, having too many of certain high-order n-gram would also mean having many of its lower-order n-grams, leading to redundancy (or correlation) in what the features represent. As eq. (11) suggests, feature-bass based functions treat each feature independently. This motivates flexible class of submodular functions, known as Deep submodular functions or DSFs [13] which mitigates the problem of redundancy by an additional concave composition followed by weighted aggregation which allows for interaction between sets of redundant features as follows:
S(A) Σ was Σ MEEU
Cus (mu((A)
(12)
Here, Was and w, are non-negative mixture weights. This naturally leads to representation resem- bling neural networks when we iteratively apply a concave function followed by linear aggregation, giving rise Deep Submodular Functions. Vs S, [3] define Eueo Ws,u (m,((A) as meta- features, and in general one can stack more layers of concave composition followed by affine transformations, leading to meta-meta features, and so on. Let L be the total number of layers in DSF; each meta-feature at layer e of this network is a submodular function, we index them using U00), which means in the example in equation 12 U (0)) and S =())
1 be the mixture weights at layer E, where for the last layer L we have (
W(() TR+
uniform weight, which means WL E R Concave functions applied the j-th submodular function of layer is represented by (E) To write concave functions in vector form, define By : |RU|| - U such that for any E RIUl we define ( (a)
L (a) - (0] (a1). (2(2))..... ..... Q10 ()))
(13)
With the notation above, for X C V. DSF f(A) is defined following
f(A) w(() Pya-- (wrl--1) Pycc-2) (...Wl) Prro (moro (A)). (A))..))
(14)
or recursively as follows
f²( -W(1). Dyaan (A)))(A))
(15)
where,
- = F (mgroo) (4))
(16)
here, "." denotes matrix multiplication. To maintain submodularity, all weight matrices must be non-negative. A DSF can incorporate skip connections, and in general, directed acyclic graph topology can be used to represent the DSF architecture with the help of recursive definitions (refer to section 4.1 of [l3).
Lastly, [33 showed that DSFs strictly generalize feature-based functions, and adding additional layers strictly increases the representation capacity, therefore suggesting the utility of additional layers.
It is important to realize that our present work on DSPNs and GPC-based learning is not just an incremental improvement to DSFs, but rather offers new class of submodular function and an entirely new way to learn the submodular function. There are two pre-existing papers on DSFs, this paper 23 from 2016 as well as more theoretical paper [33 from 2017. The first paper (33 introduces DSFs and uses max- max-margin based learning algorithm that was introduced by [60] in their "Submodular Shells" paper but applies that learning algorithm to DSFs. Max- max-maagin learning of submodular functions requires a dataset of highly valued subsets according to some unknown submodular function to learnt (e.g., each subset can be thought of as good summary) and the goal of max-margin learning in this case is to learn a submodular function so that it scores those subsets highly relative to other subsets. Max-margin learning does not care at all about the rest of the valuations of the submodular function (c.g., max-margin learnt submodular function is under
23

---

no obligation to perform well for problems other than submodular maximization, and is under no obligations to preserve the rank valuations of a given teacher submodular function).
Our present paper is entirely different from these two papers. While our DSPN "roof" structure uses the deep concave function from DSFs, there is no commonality beyond this. In the present (DSPN) paper, we have introduced a new parametric submodular function class (DSPNs) that overcomes the only known weakness of DSFs (namely, DSFs inability express certain graphic matroid rank functions, as proven in 13) ). DSPNs do not have this weakness thanks to the submodularity- preserving germutation-ivvariant aggregation stage (see Lemma [ and Corollaries 3 and which immediate means that DSPNs can represent any graphic matroid rank function. The expressivity improvement of DSPNs over DSFs means that now an open theoretical problem if DSPNs can represent all polymatroid functions or not. Considering the narrow range of submodular functions that DSFs cannot represent, we believe that it likely that DSPNs indeed can represent any polymatroid function, but we do not have proof of this at the present time.
We have also, in the present paper, introduced a new learning paradigm (the peripteral loss) for learning DSPNs that does not suffer from the issues that the max-margin learning approach suffers from. In essence, our learning a form of distillation from an expensive (possibly unoptimizable) target oracle down to parametric and computationally efficient student (a DSPN). That is, with a peripteral loss, the graded comparison signal A can be any positive/negative value, which could come from a difference in submodular valuations, or could come from a -ubsouuoo function, or could come from human evaluator (we explain this in detail in Section I I.c., the learnt submodular function can, via minimizing the peripteral loss, scale well for all values of any target function (e.g.. low valued sets should be given a low value by the learnt function, and high valued set should be given a high value by the learnt function, in order for the peripteral loss to be small). In the present study, we choose A as the difference between appensive-t--pttmizz facility location function evaluations since it is widely and successfully used submodular function but that suffers from computational scalability issues when used for optimization (e.g., submodular max) over large datasets.
Another critical novel component of our paper over (23 13 is that, to the best of our knowledge, our peripteral loss approach is the first to establish connection between: (I) contrastive learning approaches in representation learning (see Section A.T: (II) pairwise comparison scaling methods widely used in RLHF (and L.LM learning, as discussed in the paper, lines 55 55-81); and (III submodular learning. We establish connections between these three approaches while at the same time extending regular pairwise comparison approaches to the graded pairwise comparison approach (GPC), which is further novelty. While we do not study contrastive learning or RLHF in our paper, we believe that a broad impact of our work is that our peripteral loss for GPC will be useful for both higher-order contrastive learning methods and for RLHE, but we leave that to future studies the submodular learning problem in the present paper (and, as we discuss in our introduction, we believe there is too little attention in the community paid to practical strategies for identifying good submodular functions for a problem).
we focus on
Lastly, the experimental results in 2 consider only very small-scale (and entirely offline) sum- marization experiments (summarizing 100 images down to 10) or synthetic data experiments. By contrast, we consider experiments on a much larger scale (130K images) and apply it towards both offline and online summarization problems in the context of choosing good set of training data subset points that have not been previously explored - in other words, we instantiate the resulting DSPNs on entirely held-out data, so not only do DSPNs generalize to different sets and set sizes of a given ground set V but DSPNs generalize to entirely different ground sets V' (meaning V ' = 0).
So in sum, the present paper offers enormous novelty and difference over the two previous DSF papers 23
D Weighted Matroid Rank Aggregation for DSFs
Vanilla DSFs use modular functions (sum operator) for permutation invariant aggregation. However, as we show in appendix B and definition 6 given matroid M = (V,T) a modular function is indeed just a special case of weighted matroid rank function. Moreover, another common permutation invariant aggregation technique- max-pooling is yet another special case of the weighted matroid rank function. Therefore, with the same notations in appendix C we define DSF via weighted
24

---

matroid rank as follows:
(M(A) - W((). P (w(L-1), Pra-2 (...W()) W(1)
(17)
where define mäx as applying maximum operator every index as follows:
måxrerMMgo (AnI)=
m. maaxm..Ann IEZ
u
(18)
In theorem 13 we show that fM is a permutation invariant submodular set function. To show that fM is submodular we first state some properties that will be useful. We re-visit the definitions from 13 for superdifferential and antitone superdiiferential of a concave function which we will use to provide sufficient conditions that will help to show is submodular.
Definition 9 (Superdiffereniicn
Let R + R be concave function; a superdifferential of concave function is a set defined as follows
0Φ(x) {s E RR ER": f(U) f(x) S (8. x)) Vy E R
Definition (Antitone Superdifferential))
concave function 6 Rd + is said to have antitone
superdifferential if for every S y (where ordering is defined for each dimension) we have superdifferential hz 2 hy for all h E Övb(x) and for all hy E @ub(y))
Using the definitions above, have the following-
Lemma 11. Given for every layer i in DSF the list of monotone non-decreasing normalized concave functions o = (ou uu ) W be matrix of non-negative mixture weights. Define vb R as follows
(xx) & WiL). PyL-- (W(L-1), -poe-2 (... $ Pro (7) (f)...)
(19)
Then & concave and has antitone superdifferential.
Proof. The proof can be done following the similar steps in Lemma 5.13, Corollary 5.13.1 and Lemma 5,14 from 13
We now re-state Theorem 5.12 in 13 the follows.
Lemma 12. Let sb : TR= + TR be a monotone non-decreasing concave function and let g(A) & (gr (A))) ... (A)) be vector of monotone non-decreasing and normalized submodular (polymatroid)
fontymatooddduunctoonn functions. Then if up has an antitone super differential, then the set function f 2 R defined as fA) 2 (G(A)) submodular for every A ASV.
Proof. The proof is the same as for Theorem 5.12 in 13
Using the theorem above, we have the following corollary that shows the submodularity of the Deep Submodular Function defined using the weighted matroid rank (JM(A)) as the aggregation function.
Theorem 13 (Submodularity of fM). Given matroid M
(V,I), ((A)
(maxrez (.(AnT) u U'0)² and di as in lemma 11 fM(A) v(T((A) is submodular A A V. Moreover, (A) is permutation invariant on the elements of set A.
Proof. This an application of lemma into lemma 12 usiin the knowledge that weighed matroid rank are polymatroid functions. Permutation invariance of fM it can be inferred from the permutation invariance of weighted matroid rank function from lemma
This leads to the fact that any DSPN, assuming that (wps we) are valid (specifically, that W. 2 0) is submodular.
Theorem 2 (A DSPN monotone non-decreasing submodular). Any DSPN (e) w/e,, (hro (A)) defined is guaranteed to be monotone non-decreasing submodular for all valid values w.
25

---

Proof. The output of each pillar is d-dimensional -engetetvve vector. The aggregation via any weighted matroid rank of the pillar outputs for any set S V is also a d-dimensional non-negative vector and moreover, each element of this resulting aggregated vector is itself a polymatroid function thanks to the fact that a weighted matroid rank function is polymatroid function. When we compose a vector of polymatroid functions with a DSF, this preserves polymatroidality by Theorem 5.12
in [13], and thus submodularity. The theorem is hence proven.
Corollary 3 (Submodular Preservation of Weighted Matroid Rank Aggregators). Any weighted matroid rank function for matroid M = (V,I) with any non-negative vector m E RR when used as an aggregator in DSPN, will be submodularity preserving.
Proof. This follows immediately from Theorem
E Further discussion on (E,M) pair sampling and dataset construction strategies
Training a DSPN via the peripteral loss requires transferring information from an expensive oracle tar- get function a learnt DSPN. As mentioned in $section this requires dataset D {EE, M,) ==1 of pairs of sets to be contrasted with each other where each E,, M; C V. The target function in our work is an expensive facility location function, but in general it can be any oracle to provide infor- mation in a GPC context to a learner. This means that A M) fi (E) (A As submodular functions are set functions that tend to produce higher score for a diverse set and low score for a homogeneous set, the oracle evaluation will be positive if E is considered more diverse than M and will be negative if M is considered more diverse than E. For this reason, even we design sampling strategies that attempt to produce pairs E, M where E is more diverse than M, the peripteral loss Eqn. (23) allows for mistakes to made in the selection of these pairs since the sign of the oracle GPC can switch within the peripheral loss. Hence, our approach is robust to E, M pair label noise in this sense. This also means that our E, MM sampling strategy can be done in an automated manner.
Moreover, a set E might be seen as diverse in some cases and homogeneous in other cases. For instance, set E containing elements from two distinct classes is heterogeneous compared M containing all elements from one class. However, the same set E' is homogeneous when compared against a set E' containing all distinct classes, so in this latter case the (E, .M) pair would be (E", E). The oracle query offers a GPC of the pair (E, M) providing a score Score( (tore(A,,) B) E I depending on which of E and M more diverse. The pairwise comparison aspect of GPC is one of its powers since we are not asking for absolute scores from the oracle but for comparisons between pairs. This one of the benefits of pairwise comparison models when querying humans as well (as discussed in the field of psychometrics (74) and this benefit extends to the GPC case as well 61]
set
For learning a DSPN, an oracle evaluation will require evaluations with an expensive FL function. but in general the oracle need not be submodular at all, and can even be a non-submodular arbitrary dispersion function. Furthermore, as mentioned above, our framework only requires query access to the oracle, we do not need to optimize over it. When the target is non-submodular and we are learning a DSPN, our approach can be seen as finding a projection of submoouud function onto the space of DSPNs. A compelling example of this is in the context of dataset pruning, where a target function could be a mapping from pairs of subsets of training data the difference in validation accuracies that a deep model achieves after being trained on each of the subsets and evaluated validation set (we do not test this case in this paper however, but plan to do so in future work). An alternate target function could capture a human's is assessment of diversity of a summary, incorporating human feedback into the process of learning a submodular function. Crucially, in both of these examples, the target functions are not directly optimized but are only queried. Our framework may allow us to distill them onto casy-to-optimize functions such as DSPNs that can still exhibit essential and relevant properties of the target.
In general, how the (E, M)) pair of subsets are chosen in the learning procedure absolutely critical, and this is why we have introduced a suite of novel automatic sampling strategies. One of the strategies involves passive sampling of sets via random subsetting and clustering. The other strategy is new "submodular feedback method that can be seen as combinatorial active learning since it optimizes over the DSPN as it is being learnt to produce the (F., M) sets, something greatly facilitates learning.
26

---

F Analysis and Further Description of Peripteral Loss
In addition to the motivation for our loss function provided in section B heeee we provide a discussion on its gradient and curvature and how the hyperparameters govern the curvature of the provided loss. First, we re-state the mother loss, plot its value for different values of margin, and then follow by equation for its gradient and nouble-derivativy (2)) I+e- and sg)( refers to the sign of x.
In the below (xx refers to sigmoid function, that is,
The mother loss has the form
8
( A| + exp(1
(20)
A
and the corresponding gradient becomes
(C) sgn (A)o (1- (1-0) (1-2) as
8
(21)
We first plot the loss and the gradients in Fig. From the plots in Fig. and gradient in Fig. 21
clear that if A is (very) positive, then 5 must also be (very) positive produce small loss. If A is (very) negative then so also must be to produce a small loss. The absolute value A determines how non-smooth loss is so include an outer pre- multiplicaaionn by | ensures gradient of loss, as a function of 8, asymptotes to negative one (or one when A is negative) in the penalty region, analogous hinge loss, and thus produces numerically stable gradients.
Having established the "mother" loss (a we can see that A controls its curvature (the smaller the | the higher the curvature). Still, we augment the mother loss with additional hyperparameters in way that produces smoother and more stable and convergent optimization. Firstly, rather than a requiring margin of one, we introduce hyperparameter to express this margin whose default value
r 1. Second, since the units of the oracle target might be different than the units of the learner, introduce unit adjustment parameter и. that scales A. We also introduce parameter 3 > 0 (smaller 3 means smoother loss) to further optionally smooth the transition between the linearly increasing loss region and the zero-loss region of 6. That is, since in general the margin could be different from sample to sample, the ,3 hyperparameter provides global control over the curvature of the loss in way that produces smoother, more stable, and convergent optimization. Lastly, if A gets small, to avoid finite-pre mniee-rreissio numerical problems, we add a small signed value e sgn( A) for ε 2 0 which slightly pushes the denominator away from zero depending on the sign of A. This yields LA (6) which is defined as:
motossmoothness
KA + sgn A
6
CAIBBT.N
log(1 exp(3(T KA + s sggn )))
(22)
There is one last issue with the above we must address, namely when A becomes extremely small or zero. This is perfectly reasonable since expresses the oracle's indifference to vs. M. We address this with tanh-based "gating" function that detects when A is very small and gates towards a secondary loss that penalizes the absolute value of 6. The final peripteral loss LA..,,,T. thus has the form:
C..K. (8) tanh
αx
|8] + (1- [t-aanh +11-(anii tanh a
|K ) CA.....ne())
(23)
The rate of the gating is determined by a and since [<a] 0, the gate switches to the absolute value 6) whenever A gets very small. Thus if the oracle target is indifferent to E vs. M this encourages the Iearner also to be indifferent. Despite these hyperparameters, the loss gradient is still independent of the margin and making it useful for fine-tuning a learning rate
Considering only following term (which does not have the gating term),
KA + sgn A
5
LA T.
log(1 + exp(3(T RA +Esgn
(24)
the corresponding gradient will be:
ÖL n.e (8)
sgn(A)o (3 (3(7- K. + sgn
(25)
06
27

---

We plot the gradients in appendix F for two offsets, namely T = and T = 5. From these plots, it clear that 3 provides control over the smoothness of La.83,,...00)) where the smaller the the smaller the curvature (without impacting the gradient magnitudes). The importance of low curvature of the loss objective has been studied from the optimization stability [30] as well as from the lens of robustness in deep learning [95, 27]. Similarly, we can also see that 7 merely provides an offset in the gradient, which, however, can nevertheless be important for the gradient magnitude while we are optimizing.
Bringing back the gating term (again, account for corner cases where A is very small), we have
a )[8| + (1
a |m
L.,, = tanh |K
tanh
)
(26)
and the corresponding gradient will be:
3. tanh
(LA (6)
sgn(6) + +1 tanh
(27)
06
06
Note that for the function is indeed non-differentiable, however, we can have any subgradient
between [-1, 1]. Similar to PyTorch [78] we choose have the subgradient be 0, as |ō] is also at
that point. In practice, we do not encounter any instabilities due to this, and gate value throughout experiments remains very small.
afr Wilsp el negative values
Pict f (5500]1
poeiiive values
350
150
100
00
30
100
110
Plot of al.(6) for p 1
1.0
20
0.8
-15
10
0.6
Figure Peripteral loss of for different values and sign of margin A and the corresponding gradient.
F1 Final Extended Loss
Building and extending Section 3.2 using the peripteral loss along with its hyperparameters,
and with all of the individual loss components described from Section 3.1 the final total loss (mo ((E) 8 (E) MM) for an E, M pair becomes:
Lia (fw: A ( M), 5,. (EIM)) = (a (6),, (EI + Lang (fu; RUM,E' M')
+ (fo: E, E') + Credn (sw; M')
(28)
28

---

Mkaltt B.
10
1022
.08
80
-10
-308
-100
390
Pit of dly.i A. 1,1=1
Pot-d S. A. 1,
1.0
1.2
-108
50
-156
Figure 8: 1.
Plr of 44.8.
aL.if: far
E- 0.11
6-5
M.ja A1
2-
2-
-10
Figure 9: T 5
With a dataset {(E,, M,) of pairs, the total risk is:
R(w: w D)
Σ
Cwilfw: O,,
(29)
N
KE[N]
G Peripteral Networks and Training Flow
Figure T in the main paper depicts the DSPN architecture. In fact, we see two copies of DSPN presented in Figure [. the left one instantiated for the set and the right one instantiated for the M set. Each DSPN consists of of pillars which transform number of objects (e.g., images corresponding to a set) into a non-negative embedding space. The reason for the space to non- negative is ensure that the subsequent transformations can preserve submodularity, the same way that a concave composed with a modular function requires the modular function to be non-negative preserve submodularity. The figure above shows that object space has dimension nine (the number of red nodes on the bottom of each pillar) and embedding space having dimension seven (the seven orange nodes the top of each pillar). This DSPN has five pillars which means that is appropriate for an E or M set of size five. The outputs of the pillars are aggregated using a submodular submoduuar--reseevvigg permutation invariant aggregator (such in this paper, we use simple uniform matroid which corresponds to summation aggregator. Note that each scalar output of each pillar is aggregated separately and after aggregation we get resulting seven-ding sveenddimensionll vector which is input to deep submodular function (DSF). We consider the aggregation step and the final DSF to the "roof model.", highlighted with the blue triangle above. The word peripteral is an adjective (applicable typically to building) which means having single row of pillars on all sides in the style the temples of ancient Greece. This reminiscent of the above DSPN structures which is the reason for this name (see 10gurq10).
weighted matroid rank function) but in the experiments
29

---

Figure 10: "peripteral neural temple" showing Greek/Roman style peripteral structure with many pillars rendered as a form of neural temple, where each of the pillars, the submodular preserving and -ivvariran aggregation, and the roof are seen as having an underlying neural network graphical structure. This figure was generated using GPT-4 after an enormous amount of trial and error including many seed images, and then was further edited in Adobe Photoshop.
To train a DSPN, we need two sets, an E (hEterogeneous) set and an M (hoMogeneous) set. Each of the E and M sets of the (E, .)) pair is presented to DSPN instantiation being learnt and which is governed, overall by the parameters w. Note that w consists both of the parameters for the DSPN pillars well the parameters for the DSPN roof. The parameters for all instances of the pillar shared over all pillars, similar to how Siamese networks share (or tied) parameters between the two transformations. Here, however the number of pillars in the DSPN grows shrinks depending the sizes FE) and JM] of the sets and M respectively, but regardless of the size of EE| or [M] the number of the parameters of the pillars stays fixed. These sets acquired in variety of different ways, and this includes heuristics on the data (e.g., clusterings, random sets) as well as submodular feedback strategy which optimizes the DSPN is being learnt to ensure that what the DSPN thinks has high or low value agrees with the target oracle.
H Additional Experimental Details
Baseline Loss Functions To assess the efficacy of our peripteral loss, we consider two popular baselines to learn from pairwise comparisons. Note that we only replace our peripteral loss function with the baseline and we do not remove any necessary regularizers such as Lrean and Lang- Using the same notations as the main paper, we define the regression loss Lregr and Lmarg in equations 30
and
(fe: 5f. (8,z, (EIM) A(E)M))
(30)
Coarg of max max(A(EEAA) 6,., (EIM)),
(31)
30

---

Given the dataset D = { M,) of pairs, we have the following empirical risks for regression (Eq. 32) and margin (Eq. 33
Riegr( (w; D)
1 N
E
(Cogg(fu: 8y. (E.M) + (fu
iE[N]
(32)
+hrodo (f E") + Gredn (fus M, M')
Rman (w; D)
Σ dE[N]
mmarg (fu: ((E) (EIM) + Loug(fui EUM
N
(33)
+ +Lro (fwi E, E") + Crodo M, M')
Hyperparameters and Sensitivity Analysis We train every DSPN on 2 NVIDIA-AIOO GPUs with a cyclic learning rate scheduler [44, using Adam optimizer 47.. To ensure non-negative parameters in DSF, we perform projected gradient descent, where we apply projection on the to the non-negative orthant after every gradient descent step.
We list the hyperparameters we use for the peripteral loss in table 2 and table 3 and are the most salient hyperparameters since they control the curvature and hinge of the loss respectively. The benefits of smaller loss curvature have been widely studied from optimization stability in deep learning [30 95 27 and our low value
We observed that
supports previous work. a parameter controls the tanh gate, the smaller the value of alpha the more weight is given to the main part of our objective function. Since we did not encounter corner cases where A is very small, neither e nor a were found to be particularly influential.
Imagenette
le 5
0.5
1
10
le - 15
Imagewoof
le 5
0.5
1
10
le 15
CIFARIOO
le 5
0.01
10
le 15
Imagenet100
le 5
0.01
10
le
15
Table 2: Peripteral loss hyperparameters used for each dataset. Aι and A2 correspond to the coeffi- cients used in the augmentation regularizer (Bq. while Xa and Aa are the coefficents in (Eq. 3)
A1
A2
A
A
Imagenette
0.25
0.01
0
Imagewoof
0.25
0.01
0
0
CIFARTO0
0.25
0.01
le -
5e
4
Imagenet100
0.25
0.01
0
Table 3: Loss coefficients used for each dataset.
We search over 3 E {0.01, 0.1, 0.1,
and r E 51 10} and report the normalized target evaluation for Imagenet results in Table [ and Table 5 We select which hyperparameter configuration to use based on normalized FL evaluation which is described reasonably well even without tuning 3 and r, but hyperparameter search should be done for peak performance. Regarding the loss coefficients, we fix the \ = 0.25 and d2 = .01 respectively across all datasets, where the range is chosen such that each loss value is commensurate with the other. This way, none of the loss/regularizattoon terms solely drive the optimization. For Xg and X we decided the range be 0, 1e le 3 and 0, 5e 5e - 2. For imagnett//magewwof//mggggg
Figure We find that DSPN can work
100 did not see significant changes in performance by including non-zero X3 and A4. In fact, even for CIFAR-100 100 not having these does not imply DSPN will fail produce good summaries, it only results in a marginal drop.
Dataset Construction We compute the passive (E, M) pairs offline to improve computational efficiency. For the actively sampled pairs, we generate (E, .)) pairs every K epochs where an epoch is defined as full pass over all of the offline pairs. For all the datasets we consider, K 15.
31

---

k=10
k=20
k=30
k=40
k=50
k=60
k=70
k=80
k=90
k=100
3 = 0.01
0.88
0.89
0.92
0.91
0.91
0.91
0.92
0.92
0.92
0.92
B = 0.1
0.88
0.88
0.90
0.90
0.90
0.92
0.91
0.92
0.92
0.92
8 = 0.5
0.90
0.89
0.90
0.92
0.92
0.92
0.92
0.93
0.92
0.92
Table 4: Sensitivity of 3 based on normalized FL evaluation.
k=10
k=20
k=30
k=40
k=50
k=60
k=70
k=80
k=90
k= 100
7 =
1
0.84
0.84
0.85
0.87
0.88
0.88
0.88
0.89
0.90
0.90
7
5
0.90
0.88
0.88
0.89
0.90
0,90
0.90
0.91
0.91
0.92
7=
10
0.90
0.89
0.90
0.92
0.92
0.92
0.92
0.93
0.92
0.92
Table 5: Sensitivity of'r based on normalized FL evaluation.
Long-tailed Dataset Construction For the results presented in Sections 5.2 we create patholog- ically imbalanced datasets from sets of images that the DSPN never encountered during training. Specifically, we add duplicates for each image in a class: the number of duplicates varies per class and is drawn from Zipf distribution [166]. We show the final distributions of the imbalanced dataset in Figure
Figure 11: Imbalanced dataset distributions
I Qualitative Analysis of Learnt Features
In Table [ we show that imparting DSPNs the ability to learn features crucial for successful training. Feature-based functions and DSFs work best when features correspond to some bag-of-words or count like attribute. For example, c0 62 both use TF-IDF based feature extractors to instantiate feature-based functions. More recently, [5I] learns "additively contributive" (AC) features with an autoencoder by restricting all weights in the initial layer of the decoder the positive orthant. Unfortunately, universal features for images procured from modern pretrained models such as CLIP do not necessarily have this property.
We show that DSPNs learn bag-of-words features in Figure 12 individual DSPN/CLIP features. For visualization purposes, we randomly select 10 features from the model in consideration and use each feature to rank the images from a completely held out set. The top 10 images selected by any of the DSPN features appear very homogeneous and are strongly correlated to class, while images with the lowest feature values (typically with feature value 0) are practically indistinguishable from a random subset of images. In other words, high value indicates the presence of some attribute while a low value indicates its absence. When we perform a similar qualitative analysis upon CLIP features, we find that both the high valued sets and low valued sets have some weak correlation to class. CLIP features cannot be interpreted in the same way as DSPN because each feature corresponds a coordinate in some higher dimensional space. Our results show that features that encapsulate count-like attributes are essential for learning good DSF.
by exploring the preferences of
32

---

Top images
mages
Top 10 Images Based CLIP
Bottom 10 Images Based on CLIP
Higher Feature Value
Figure 12: Qualitative Assessment of Learnt Features on Imagenet100. For each row, we use a randomly selected feature of either DSPN or CLIP to rank all images in the held out set and visualize the highest and lowest ranked samples. Each DSPN feature corresponds some count-like property that is correlated class, evident from the fact that very few distinct classes are present the highly ranked images.
33

---

DSPN
DSPN (No Redun)
Random
10
0.91
0.88
0.65 + 0.04
20
0.93
0.89
0.67 + 0.03
30
0.91
0.89
0.67 = 0.02
0.90
0.88
0.68 + 0.02
50
0.90
0.88
0.68 = 0.02
60
0.89
0.88
0.68 + 0.02
70
0.88
0.88
0.68 + 0.02
80
0.88
0.87
0.69 + 0.02
90
0.88
0.87
0.69 + 0.02
100
0.88
0.87
0.70 = 0.02
Table Effect of setting λ 21 normalized FL evaluations on CIFAR100
J Limitations
A limitation of DSPNs is that they may not be able to produce effective summaries that are significantly larger than the largest sets that they were trained on. In our experiments, we do observe that the learnt DSPN produces high quality summaries of size 500 though they not trained sets larger than 100. However, further investigation is needed to determine DSPNs can continue to produce high quality summaries with significantly larger cardinalities.
34

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Our claims from the abstract and introduction are justified throughout the
paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Limitations of our paper is discussed in Appendix J
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We do not make any assumptions in our theoretical results.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We provide all the details required for reproducibility in Appendix and Table
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We plan to release the codebase in separate GitHub repository under the name
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All the details are provided in Appendix H and Table 2
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We provide standard error for the results of all experiments that are non- deterministic in section
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
35

---

Justification: We provide the details in Section and Table 2
9. Code Of Ethies
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: We reviewed NeurIPS Code of Ethics and abide by it in our work.
Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Our work proposes a new approach to learn submodular functions from an oracle. We do not anticipate any negative social impact of our work.
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: We do release any dataset model.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: All datasets we use are cited.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: We do release any new assets in this work.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: We do not have any experiments with human subjects.
Institutional Review Board (IRB) Approvals or Equivalent for Research with Human
Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: No human subjects were used on our work.
36


Reviews:
[{"review_id": "eEFxKcDXY0", "reviewer": "Reviewer_fthD", "summary": "The paper introduces deep submodular peripteral networks (DSPNs) and a graded pairwise preferences (GPC)-style peripteral loss. It shows that DSPNs are effective in learning submodularity from a target function.", "questions": "1. I understand that due to page limits, a large portion of the content is included in the appendix. However, I suggest providing a short sentence with informal definitions or references to the definition locations for important concepts so that readers can quickly grasp their meanings and follow the text more naturally. For example, on line 61, what are graded pairwise preferences? Additionally, where is the formal definition of a submodular function? What are the definitions of a matroid and a matroid rank function?\n2. I recommend adding some motivation and detailed applications about how submodular functions are used in machine learning and why they are important. Explicitly explaining where and how submodular functions can be applied in the introduction would be beneficial, instead of generally stating that they have been used in several areas and studied in several papers.\n3. Could the output of the function be a vector of a few dimensions instead of a scalar, where each dimension represents different aspects of comparison, or can be scores judged by different people? Can you provide some insights on whether this scenario is reasonable and if so, whether your framework can be applied to this setting?\n4. In Section 5, what is the target FL and how is it labeled/created? I suggest state explicitly on the task (e.g., image summarization) in the main text.", "limitations": "The authors have adequately addressed the limitations.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 4, "strengths": "- The construction of the submodular function, i.e. DSPNs are interesting as they assure the submodularity.\n- The loss function’s construction using contrastive sets is also interesting and reasonable.\n- The experiments demonstrate that DSPNs combined with the peripteral loss are effective.", "weaknesses": "The paper’s organization needs improvement. Many important concepts, such as submodular functions, FC functions, and GPC, lack definitions (even informal) when they first appear. Additionally, there is no motivation or detailed application of submodular functions in machine learning, making it difficult for readers to understand at the beginning.\n\nMinor: Page 5, line 209, “then so also must”.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback and questions, and are glad that they found our work to be convincing. We address each question in turn.\n\n**More definitions in the main body**\n- Yes, in the next version of the paper we will add more such definitions in the main body. According to the Neurips2024 call for papers, if the paper is accepted, we will be granted an additional content page that we can use for this purpose, including as you suggest GPC, and the basic definitions of and motivations for submodularity and matroids.\n\n**Output a vector rather than a scalar**\n- This is an interesting question that we didn't pursue in the present paper, but there is no reason that our approach would not generalize to vector outputs, assuming an oracle queryable teacher is available. Given the opportunity, we will discuss this possibility in the next version.\n\n**What is target FL?**\n- While the oracle need not be an FL (facility location) function or even a submodular function, in the present work we use an expensive to optimize but easy to query target FL function as the oracle, and we transfer from this target FL to the learnt DSPN model. In our present work, each target FL is created by computing a real-valued feature vector for each sample and then computing a non-negative similarity between each such vector. We used a CLIP ViT encoder to encode input images, and a tuned RBF kernel to construct similarities for our target FL. Note that the target FL construction is rather expensive (quadratic) and also does not generalize to held-out data, but this is a key point. That is, the paper shows how we distill from this expensive target FL to a cheaper and generalizable DSPN.\n\n\n**Main Task**\n- Yes, we will do this in the revised version.\n\nAgain, thanks for your review and comments!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "92HV6ynEMO", "reviewer": "Reviewer_YWZB", "summary": "The paper introduces Deep Submodular Peripteral Networks (DSPNs), a novel parametric family of submodular functions designed to address practical learning methods for submodular functions and graded pairwise comparisons (GPC). To learn DSPNs, the paper also introduces a new GPC-style “peripteral” loss, which leverages numerically graded relationships between pairs of objects, extracting more nuanced information than binary comparisons. Finally, the authors demonstrate DSPNs’ efficacy in learning submodularity from a\ncostly target submodular function showing superiority both for experimental design and online streaming applications.", "questions": "- Can the authors explain intuitively how the peripteral loss is used to learn a reward model in RLHF?", "limitations": "Yes", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper introduced Deep Submodular Peripteral Networks (DSPNs), a new parametric family of submodular functions. Since the computational cost for querying a DSPN is independent of dataset size, their approach can learn practical submodular functions scalably.\n\n- The paper also proposed a new GPC-style “peripteral” loss to successfully learn DSPNs. As introduced, this loss has many applications such as learning a reward model in the context of RLHF.", "weaknesses": "- It lacks a theoretical guarantee for the proposed peripteral loss. What happens if the target oracle does not exist?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and time. We address your questions below.\n\n\n**Theoretical guarantee for the proposed peripteral loss**\n- In our submission, we have included theoretical results regarding the guarantee that submodularity is retained by the use of the permutation invariant stage of a DSPN via the use of weighted matroid rank functions. There is still an open theoretical problem if a DSPN can perfectly represent (or arbitrarily closely approximate) *any* submodular function which currently is a conjecture. There is also the following conjecture: If the resulting peripteral loss, once trained, falls below a given threshold, then for each pair E,M with \\Delta(E|M) > 0 (respectively \\Delta(E|M) < 0), the volume in embedding space of the convex hull of the points in E will be greater (resp. smaller) than the volume in embedding space of the convex hull of the points in M. \n\n**Target oracle does not exist**\n- In such case, if an approximate oracle exists than we should still be able to train. Note that the oracle only needs to be able to be queried, we do not need to optimize over the oracle which means that non-submodular oracles (such as non-submodular functions or humans) can be the oracle. This segways to your third comment.\n\n**Peripteral loss is used to learn a reward model in RLHF**\n- This is briefly outlined on lines 45-59. The key idea is that RLHF could be used as normal via, say, PPO (proximal policy optimization) but the key difference is that the human providing the feedback would need to provide more than just a binary value of if A is better than B or B is better than A, rather a \"graded\" preference would need to be given by the computer saying how much is A better than B (or B better than A). This feedback is then represented via our $\\Delta(E|M)$ score except here rather than scoring the preference for an $E$-set over an $M$ set (which would not be present), it would instead score two LLM-responses $A$ and $B$ relative to each other and the error (which is the peripteral discrepancy between the human's preference score and the model's difference score) would then propagate back to an LLM as in PPO via the peripteral loss. We hope to be able to pursue this research direction in the future.\n\nAgain, thanks very much for your review and comments.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5YUBLLxW7n", "reviewer": "Reviewer_W4dW", "summary": "This paper proposes a new framework to learn submodular functions.  Specifically, the paper proposes a new parametric family of submodular functions using neural networks. Then, the paper proposes training such networks with a new loss function that is based on graded pairwise comparisons.", "questions": "None.", "limitations": "Yes.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I think the paper addresses an important problem of learning/distilling submodular functions in a scalable way. The paper also conducts thorough experiments comparing their approach with baselines.\n\nThe paper is well-written and easy to follow. The paper does a good job discussing related and prior work.", "weaknesses": "This paper is outside my area of expertise, and as such I don't think I can offer constructive feedback.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We nonetheless wish to thank you for your review and time. We are glad that you found the paper well-written and easy to follow.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8FlJEKgKG6", "reviewer": "Reviewer_Ltg4", "summary": "The authors identify two open problems in machine learning and provide novel solutions to them. The first problem is that even though the submodular functions show up in numerous applications, learning submodular functions through DNNs remain unpractical. Their proposed solution to this issue is their new architecture called Deep Submodular Peripteral Networks (abbreviated as DSPNs). The other identified problem is the lack of graded pairwise preferences (GPCs) oracles. In its essence, it is the type of oracle where given two sets of elements, a score with a scalar value is returned. The sign of this score denotes which set is preferred over the other set and the absolute value of the score denotes the magnitude of this preference. To reflect the effects of this oracle better, they introduce a new loss function called peripteral loss. They evaluate DSPNs ability to learn a target function (a facility location function in the case of their experiments) against different baseline algorithms. They also demonstrate the effects of using different losses when training DSPNs.", "questions": "- For my understanding, can we interpret DSPNs as enhanced versions of DSFs with permutation invariance?\n- Where do weighted matroid rank functions stand in relation to threshold potentials (Stobbe and Krause [95])?\n- Isn't Proposition 8 a bit obsolete? Aren't all set functions characterized by their permutation-invariance hence the submodular set functions as well?", "limitations": "Yes, the authors discuss the limitations of their work in Appendix J.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Considering the success of supervised learning from comparisons in domains such as healthcare etc., it is no surprise that learning from graded pairwise comparisons is a significant oracle selection. I can see it being very useful in team selection problems where we want to predict the outcome of a competition. The DSPN structure is original. Majority of the ideas conveyed clearly.", "weaknesses": "- I have some concerns related to the organization of the paper. I am aware the page limitations can be annoying sometimes. Still, I do think that Figure 13 should be included in the main body of the paper. I think it would help readers understand the paper better and the main body of the paper would be more standalone that way. Maybe just a 2+1+1 or 2+1+2 layer version of Fig. 13 as you describe in your experiments.\n\n- The introduction mentions E, M sets but we don't know what they stand for until later. You may consider mentioning them as heterogeneous and homogeneous sets before your main contributions.\n\nMinor editorial comments:\n- Appendix or Figure names are not properly capitalized at some places e.g. Line 810.\n- Some figures refer the reader to the appendix without denoting they are in the appendix.\n- On line 96-97, the adjectives need commas in between.\n- Line 844, multiple \"also\"s", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Firstly, thank you for your review and your comments. We will attempt in the next version of the paper to address all of them. Detailed comments follow.\n\n\n**Organization**\n- We agree that Figure 13 ideally belongs in the main body. If the paper is accepted, for the final camera ready we are allotted one additional page that can fit Figure 13 as well as other motivating and other material.\n\n\n**Descriptions of E,M**\n- Yes, we can describe them as the heterogeneous and homogeneous sets right when the notation is first introduced.\n\n**editorial comments**\n- These typos will all be fixed in the next version. Thank you for pointing them out.\n\n**DSPNs as enhanced versions of DSFs with permutation invariance**\n- DSPNs are actually even more than this since DSPNs correspond to a larger sub-family of submodular functions than DSFs, as we prove in our paper. It may be that DSPNs can represent any submodular function, but we do not yet have a proof for that, but it is currently a conjecture.\n\n\n**DSPNs vs threshold potentials (Stobbe and Krause [95])**\n- This is a good question. In the DSF theory paper (Bilmes & Bai 2017), it was shown that DSFs extend the family of sums of concave composed with modular functions (SCCMs). The threshold potential functions of Stobbe & Krause are instances of SCCMs and hence DSFs correspond to a larger family than threshold potentials. DSPNs, moreover, correspond to a still larger sub-family of submodular functions than SCCMs as mentioned above. Hence, DSPNs are a larger family than those of Stobbe and Krause. Incidentally, Stobbe and Krause refer to SCCMs as \"decomposable submodular functions\" but we prefer the name \"SCCMs\" or \"feature based functions\" in order to avoid the overloading of and potential confusion between that and the notion of \"decomposable graphs\" in graphical models and chordal graph theory. The reason for this potential confusion is that the graph notion of decomposability can apply to a submodular function as well separately from if the submodular function is representable as an SCCM or not. \n\n**Proposition 8**\n- We consider a main theoretical result of the paper that the weighted matroid rank functions in the middle of the DSPN preserve submodularity and permutation invariance of the DSPN. We include proposition 8 only to be complete in case there is any question, but in the next version of the paper we can clarify this.\n\nAgain, thank you very much for your review and your time!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We wish to thank all of the reviewers for their reviews and comments. We are quite happy that the reviewers all fairly unanimously found our work to be interesting and worthwhile. We address each of the reviewers questions and comments in the below.

Meta-review: The reviewers were uniformly positive in their assessment of this paper. However, there were consistent concerns with its organization–I encourage the authors to make an effort to organize and polish their paper further, to make it more approachable to readers.
Decision: Accept (spotlight)