Learning to Make Decisions via Submodular Regularization
Authors: Ayya Alieva
Aiden Aceves
Jialin Song
Stephen Mayo
Yisong Yue
Yuxin Chen
Venue: ICLR 2021 Poster (2021)

Abstract: Many sequential decision making tasks can be viewed as combinatorial optimization problems over a large number of actions. When the cost of evaluating an action is high, even a greedy algorithm, which iteratively picks the best action given the history, is prohibitive to run. In this paper, we aim to learn a greedy heuristic for sequentially selecting actions as a surrogate for invoking the expensive oracle when evaluating an action. In particular, we focus on a class of combinatorial problems that can be solved via submodular maximization (either directly on the objective function or via submodular surrogates). We introduce a data-driven optimization framework based on the submodular-norm loss, a novel loss function that encourages the resulting objective to exhibit diminishing returns. Our framework outputs a surrogate objective that is efficient to train, approximately submodular, and can be made permutation-invariant. The latter two properties allow us to prove strong approximation guarantees for the learned greedy heuristic. Furthermore, we show that our model can be easily integrated with modern deep imitation learning pipelines for sequential prediction tasks. We demonstrate the performance of our algorithm on a variety of batched and sequential optimization tasks, including set cover, active learning, and Bayesian optimization for protein engineering.

Published as a conference paper at ICLR 2021
LEARNING TO MAKE DECISIONS VIA SUBMODULAR REGULARIZATION
Ayya Alieva Stanford University ayya@staafordd.edu
Aiden Aceves
Jialin Song
Caltech aaceves tech, edu
Caltech
jssong tech. edu
Stephen Mayo
Yisong Yue
Yuxin Chen
Caltech steve@caltech.ed
Caltech yyue@caltech.
University of Chicago
chenyuxin@uchiccggo.co
ABSTRACT
Many sequential decision making tasks can be viewed as combinatorial optimiza- tion problems a large number of actions. When the cost of evaluating tion is high, even greedy algorithm, which iteratively picks the best action given the history, is prohibitive to run. In this paper, we aim to learn greedy heuris- tic for sequentially selecting actions as a surrogate for invoking the expensive oracle when evaluating an action. In particular, we focus on a class of combinato- rial problems that can be solved via submodular maximization (either directly on the objective function via submodular surrogates). We introduce data-driven optimization framework based on the submodular-norm loss, a novel loss func- tion that encourages the resulting objective to exhibit diminishing returns. Our framework outputs surrogate objective that is efficient to train, approximately submodular, and can be made permutation-invariie
The latter two properties al- low us prove strong approximation guarantees for the learned greedy heuristic. Furthermore, our model is casily integrated with modern deep imitation learning pipelines for sequential prediction tasks. We demonstrate the performance of our algorithm on a variety of batched and sequential optimization tasks, including set cover, active learning, and data-driven protein engineering.
INTRODUCTION
In real-world automated decision making tasks we seek the optimal set of actions that jointly achieve maximal utility. Many of such tasks either eeterminisiicnoo--aaaiiv or stochastic/adaptive can be viewed as combinatorial optimization problems over large number of actions. As an example, consider the active learning problem where a learner seeks the could be measured by
set
of training examples for learning a classifier. The utility of training the mutual information (Lindley 1956) between the training set and the remaining (unlabeled) data points, by the expected reduction in generation error if the model is trained on the candidate training set. Similar problems arise in number of other domains, such as experimental design (Chaloner and Verdinelli, (995), document summarization (Lin and Bilmes 2012), recommender system Javdani et al. 2014). and policy making (Runge et al. 2011).
Identifying the optimal set of actions (c.g., optimal training sets, most informative experiments) amounts to evaluating the expected utility over a combinatorial number of candidate sets. When the underlying model class complex and the evaluation of the utility function expensive, these tasks are notoriously difficult to optimize (Krause and Guestrin 2009). For a broad class of deci- sion making problems whose optimization criterion is to maximize the Decision-theoretie value of information (e.g., active learning and experimental design), it has been shown that is possible to design surrogate objective functions that are (approximately) submodular while being aligned with the original objective at the optimal solutions (Javdani et al. 2014 Chen et al., 2015b; Choudhury (et al. 2017). Here, the information gathering policies no longer aim to directly optimize the target objective value, but rather choose to follow greedy trajectory governed by the surrogate function

---

Published as a conference paper at ICLR 2021
that is much cheaper to evaluate. These insights have led principled algorithms that enable sig- nificant gains in the efficiency of the decision making process, while enjoying strong performance guarantees that competitive with the optimal policy.
Despite the promising performance, a caveat for these "submodular surrogate" barrogate--based based approaches is that it is often challenging engineer such surrogate objective without an ad-hoc design and analysis that requires trial-and-error (Chen et al., 2015b; Satsangi et al.] 2018). Furthermore, for certain classes of surrogate functions, is NP-hard to compute/evaluate the function value (Jav-] dani et al. 2014). In such cases, even a greedy policy, which iteratively picks the best action given the (observed) history, can be prohibitively costly to design or run. Addressing this limitation re- quires more automated or systematic ways of designing (efficient) surrogate objective functions for decision making.
Overview of main results. Inspired by contemporary work in data-driven decision making, we aim to learn a greedy heuristic for sequentially selecting actions. This heuristic acts as a surrogate for invoking the expensive oracle when evaluating action. Our key insight is that many practical algorithms can be interpreted as greedy approaches that follow an (approximate) submodular surro- gate objective. In particular, we focus on the class of combinatorial problems that can be solved via submodular maximization (either directly on the objective function or via a submodular surrogate). We highlight some of the key results below:
Focusing on utie greedy policies, we introduce a data-driven optimization framework based on the "submodular-norm" loss, which is novel loss function that encourages learning functions that exhibit "diminishing returns". Our framework, called LEASURE (Learning with Submodular Regularization), outputs surrogate objective that is efficient to train, approximately submodular, and can be made permutation-invariinn. The latter two properties allow us to prove approximation guarantees for the resulting greedy heuristic.
We show that our approach can be easily integrated with modern imitation learning pipelines for sequential prediction tasks. We provide rigorous analysis of the proposed algorithm and prove strong performance guarantees for the learned objective.
We demonstrate the performance of our approach on a variety of decision making tasks, including set cover, active learning for classification, and data-driven protein design. Our results suggest that, compared to standard learning-baad based baselines: (a) at training time, LEASURE requires significantly fewer oracle calls to learn the target objective (i.e., to minimize the approximation error against the oracle objective); and (b) at test time, LEASURE achieves superior performance on the corresponding optimization task (i.e., minimize the regret for the original combinatorial optimization task). In particular, LEASURE has shown promising performance in the protein design task and will be incorporated into real-world protein design workflow.
2 RELATED WORK
Near-optimal decision making via submodular optimization. Submodularity is property of a set function that has a strong relationship with diminishing returns, and the use of submodular- ity has wide applications from information gathering to document summarization (Leskovec al.) 2007 Krause et af.] 2008: Lin and Bilmes| 2011 Krause and Golovin| 2014). The maximization of a submodular function has been an active area of study in various settings such as centralized Nemmaaserr et al., 1978; Buchbinder et al. 2014 Mitrovic et al. 2017). streaming (Badanidiyuri) [019 Feldman al. (2020), continuous (Bian et al. 2017b; [Bch] 2019) and approximate (Horel and Singer, 2016 Bian et al.) 2017a). Variants of the greedy algorithm, which iteratively selects an element that maximizes the marginal gain, feature prominently in the
al. | Kazemi
algorithm design process. For example, in the case of maximizing monotone submodular function subject to a cardinality constraint, it is shown that the greedy algorithm achieves an approximation ratio of (1 1/e) of the optimal solution (Nembauser et al. 1978).
In applications where we need to make a sequence decisions, such as information gathering, we usually need to adapt our future decisions based on past outcomes. Adaptive submodularity is the corresponding property where an adaptive greedy algorithm enjoys a similar guarantee for maxi- mizing an adaptive submodular function (Golovin and Krause, 2011). Recent works have explored optimizing the value of information (Chen et al.] al.] 2015b) and Bayesian active learning (Javdani et al.) 2014 Chen et al. 2017a) with this property. Another line of related work is online setting (typically
2

---

Published as a conference paper at ICLR 2021
bandits), which is grounded in minimizing cumulative regret (Radlinski et al. 2008 Streeter et al.
2009
Yue and Guestrin 2011 Ross et al. 2013; Yu et al. 2016 Hiranandani et al. 2020).
Learning submodular functions. Early work focused learning non con-negative linear combinations of submodular basis functions (Yue and Joachims, 2008 [El-Arini et al. 2009) Yue and Guestrin Sipos et al. 2012), which was later generalized to mixtures of "submodular shells" (Lin and
2011
Bilmes 2012). Deep submodular functions @Dolhansky and Bilmes, (0166 extend these ideas to
more expressive compositional function classes by using sums of concave composed with modular functions. The theoretical question of the learnability of general submodular functions is analyzed Balaan and Harvey (2018). Our goal is to encourage submodularity via regularization, rather than via hard constraints on the function class design.
Learning to optimize via imitation learning. Rather than first learning a submodular function and then optimizing it, one can instead learn to directly make decisions (e.g., imitate the oracle greedy algorithm). This area builds upon imitation learning, which learns policy (i.e., a mapping from states to actions) directly from examples provided by an expert (e.g., expensive computational oracle, or a human instructor) (Chernova and Thomaz 2014). Classic work on imitation learning (e.g., the Dataset Aggregation (DAgger) algorithm (Ross et al. 201T)) reduce the policy learning problem to the supervised learning setting, which has been extended to submodular optimization by imitating the greedy oracle method (Ross al. 2013). More generally, learning to optimize has been applied generically to improve combinatorial optimization solvers for focused distributions of optimization problems (He et al. 2014. [Song et al., 2018 Khalil al.. 2016 [allunvvic al.] 2018 Gasse et al. 2219)) [Song et al. 2020). Our approach bridges learning to optimize and learning submodular functions, with focus on learning surrogate utilities using submodular regularization.
Learning active learning. Our approach is applicable to active learning, and so is related to work on learning active learning. The closest line of work learns utility function as surrogate for improvement in classifier accuracy (Konyushkova et al. 2017: Liu et al., 2018), which is then used as the decision criterion. However, prior work either used restricted function classes (Konyushkoval eet al. (017), or very expressive function classes that can be hard to fit well (Liu et al., (0188). Our work can be viewed as a direct extension of this design philosophy. where we aim to reliably learn over expressive function classes using submodular regularization. Other related work do not directly learn an active learning criterion, instead encouraging sample diversity using submodularity (Wei et al. 2015) or the gradient signal from the classifier (Ash et al. 2020).
BACKGROUND AND PROBLEM STATEMENT
3.1 DECISION MAKING VIA SUBMODULAR SURROGATES
Given a ground set of items V to pick from, let u 2 + E be set function that measures the value of any given subse J C V. For example, for experimental design, u(4) captures the utility of the output of the best experiment; for active learning u(A) captures the generalization error after training with set A. We denote a policy क 2 + V to be a partial mapping from the set/sequence of items already selected, to the next item to be picked. We use 11 to denote our policy class. Each time a policy picks an item e E V, it incurs a unit cost. Given the ground set V. the utility function u, and a budget & for selecting items, we seek the optimal policy that achieves the maximal utility:
π E arg max ul u(Sr,))) mell
(1)
ST. is the sequence of items picked by æ: ST,1 S (S.,,.))) for i >> 0 and S = 0. As we have discussed in the previous sections, many sequential decision making problems can be characterized as constrained monotone submodular maximization problem. In those scenarios u is:
Monotone: For any A C V and E V A. u(A) S u(Au
Submodular: For any A C B C V and e E V B, uuAu u(A) 2 ((B u(B).
For simplicity, we focus deterministic set functions in this section. Note that many of our results can casily extent to the stochastic, by leveraging the theory of adaptive submodularity (Golovin and Krause 2011
3

---

Published as a conference paper at ICLR 2021
In such cases, mypopic algorithm following the greedy trajectory of u admits near-optimal policy. However, in many real- world applications, u is not monotone submodular. Then one strategy is to design surrogate function f :22 + R which is:
Globally aligning with u: For instance, ff lies within factor of u: f(A) E [cr =(A)), C2 =(A))] for some constants C1, C2 and any set A _ V; or within a small margin with u: f(A) E [u(A) and any set A _ V;
c, (,(()) + c] for fixed
Monotone submodular: Intuitively, a submodular surrogate function encourages selecting items that are beneficial in the long run, while ensuring that the decision maker does not miss out any actions that are "surprisingly good" by following a myopic policy (i.c., future gains for any item are diminishing). Examples that fall into this category include machine teaching (Singla et al. 2014), active learning (Chen et al. 2015a), etc.
We argue that in real-world decision making scenarios- as validated later in Section maker is following a surrogate objective that aligns with the above characterization. In the following context, we will assume that such surrogate function exists. Our goal is thus to learn from an expert policy that behaves greedily according to such surrogate functions.
6 the decision
3.2 LEARNING TO MAKE DECISIONS
We focus on the regime where the expert policy is expensive to evaluate. Let g 2" + I be the score function that quantifies the benefit of adding a new item to an existing subset of V. For the expert policy and submodular surrogate f discussed in Section 3.1 AA C V and E V:
(A, = f(AU(ct) - f(A).
For example, in the active learning case, (A, e) could be the expert acquisition function that ranks the importance of labelling each unlabelled point, given the currently labelled subset. In the set cover case, ( E) could be the function that gives the score to each vertex and determines the next best vertex to add to the cover set. Given loss function L, our goal is to learn a score function 9 that incurs the minimal expected loss when evaluated against the expert policy: = arg min, E,,el<(g(AA (A, (()((((,)))))) ( e))] Subsequently, the utility by the learned policy is u(S+,k), where for any given history A C V, (AA E arg max.ev ((A, e).
4 LEARNING WITH SUBMODULAR REGULARIZATION
To capture our intuition that a greedy expert policy tends to choose the most useful items, we intro- duce LEASURE, a novel regularizer that encourages the learned score function (and hence surrogate objective) to be submodular. We describe the algorithm below.
Given the groundset V, let f: 2 + IR be any approximately submodular surrogate such that f(A) captures the "usefulness" of the set A. The goal of trained policy is to learn score function : 2" x V - IR that mimics (A, x) = f(A U {a}) f(A), which is often prohibitively expensive evaluate exactly. Then, given any such g. we can define a greedy policy (A) (enmaxxev9((,,. (A, r). With LEASURE, we aim to learn such function g that approximates goap well while being inexpensive evaluate at test time. Let Dreat {(A,, yep = g x))) hm be the gathered tuple of expert scores for each set-element pair. If the set 2 x V was not too large, the LEASURE could be trained on the randomly collected tuples Dreat- However, 2" tends to be too large to explore, and generating ground truth labels could be very expensive. To leverage that, for subset of set-element pairs in Dreat we generate set of random supersets to form an unsupervised < A', (A,x) E Dreathn where A' denote
synthetic dataset of tuples D aynth = {((A,)), a randomly selected superset of A. Define:
Loss(g, g =
Σ
TN - s(A, +
Σ
((s(A',x)) x)),
(A.)) E
where À > 0 is the regularization parameter and o is the sigmoid function. Intuitively, such regu- larization term will force the learned function g to be close to submodular, as it will lead to larger losses every time ((A,.)) > g(A, If we expect ff to be monotonic, we also introduce a second regularizer ReLu(- 9( A', x)) which pushes the learned function be positive. Combined, the loss
4

---

Published as a conference paper at ICLR 2021
function becomes (used in Line 11 in Algorithm
Loss(g.g gpp)
Σ
(v-P-1 ((,
+
Σ
x) - s(A,x))
(f Dreat
(A (E Santh
+7
E
ReLu(-g(A',
(Al,
where 7 is another regularization strength parameter. Such loss should push to explore set of approximately submodular, approximately monotonic functions. Thus, if f exhibits the submodular and monotonic behavior, y trained on this loss function should achieve good local minima.
We next note that since 2 is too large to explore, instead of sampling random tuples for Dreat= we modified DAgger. Then g can learn not only from the expert selections of (A,z). but it can also see the labels of the tuples the expert would not have chosen.
Algorithm Learning make decisions via Submodular Regularization (LEASURE)
1: Input: Ground set V, expert score function ges,,
2: regularization parameters X, >, DAgger constant 3, the length of trajectories T.
3: initialize Dreal <-
4: initialize to any function.
5: for = 1 to N do
6: Let 9i = g with probability 3.
7: Sample a batch of T step trajectories using TH = x, aggax_eeyl (A,
8: Get dataset D; = (AA,, 9 xA), of labeled tuples on actions taken by n,
9:
Dreat f Dreat Di. D;.
10:
Generate synthetic dataset D Syynth from Dreat-
11:
Train gi+1 on Dreat and Deynth using the loss function above.
12:
Output: 9N+1
Algorithm D above describes our approach. A trajectory in Line 7 is sequence of iteratively chosen tuples, ((0, ) (fx1) x2), ((x1, ].)) zz)...,
-1 TT)), collected using a mixed policy TH In Line 8, expert feedback of selected actions is collected to form D,. Note that in some settings, even collecting exact expert labels gd at train time could be too expensive. that case, gdd can be replaced with a less expensive, noisy approximate expert gep = grd, In fact, all three of our experiments use noisy experts in one form or another.
5 ANALYSIS
Estimating the expert's policy. We first consider the bound the loss of the learned policy mea- sured against the expert's policy. Since LEASURE can be viewed as a specialization of DAGGeR (Ross et al.) 2011) for learning submodular function, it naturally inherits the performance guaran- tees from DAGGER, which show that the learned policy efficiently converges to the expert's policy. Concretely, the following result, which is adapted from the original DAgger analysis, shows that the learned policy is consistent with the expert policy and thus is no-regret algorithm:
Theorem (Theorem 3.3. Ross et al. (201I).. Denote the loss of î at history state H as I(H (H, = (( & (H)), ght (H, x (H)). Let dz be the average distribution of states if we follow è for finite number of steps. Furthermore, let D; be a sel of m. random trajectories sampled with n; at round E (1...., NN, and čN = min N EN EH.,D,, #)] be the training loss of the best policy on the sampled trajectories. If N is O (T2 1og(1/8)) and m is O (1) then with probubility at least 1 - 8 there exists ât among the N policies, with Ee [I(H, +)] EN + O (+).
Approximating the optimal policy. Note that the previous notion of regret corresponds to the average difference in score function between the learned policy and the expert policy. While this result shows that LEASURE is consistent with the expert, it does not directly address how well the learned policy performs in terms of the gained utility. We then provide a bound on the expected value of the leamned policy, measured against the value of the optimal policy. For specific decision making tasks where the oracle follows an approximately submodular objective, our next result, which is proved in the appendix, shows that the learned policy behaves near-optimally.
5

---

Published as a conference paper at ICLR 2021
Theorem 2. Assume that the utility function is monotone submodular. Furthermore, assume the expert policy Th follows a surrogate objective f such that for all A S V. If(A) u(A)l < eg where c > O. Let ÊN = min, N Ei=1 [H; ft) be the training loss of the best policy on the sampled traeectories. I is O (I log(1/6)) then with probability at least 1 - 8, the expected utility achieved by running ft for ho steps is
E[u(S+,A)] 2 (1 1/e)Elu(S k(CE + m O(1).
A closely related work in approximate policy learning is by Ross al. (013), which also builds upon DAGGER to tackle policy learning for submodular optimization, via directly imitating the greedy oracle decision rather than learning surrogate utility. One key difference is that their ap- proach can only yield guarantees against an artificial benchmark (a set or list of simpler policies that each independently selects an item add the action set), whereas our theoretical guarantees are with respect to the optimal policy in our class.
6 EXPERIMENTS
In this section, we demostrate the performance of LEASURE three diverse sequential decision making tasks, namely set cover (SC), learning active learning (LAL) and protein engineering (PE).
Baselines. We compare our approach to the Deep Submodular Function (DSF (Dolhansky and Bilmes| 2016)) and Deep Batch Active Learning by Diverse, Uncertain Gradient Lower Bounds (BADGE (Ash et al. (020)). The DSF approach learns submodular surrogate function f 2 IR that produces a score for each set A C V. The architecture of the DSF forces the function f to be exactly submodular, as opposed LEASURE, which is only encouraged be submodular through a regularizer. However, the architecture and the training procedure of the DSF are quite restrictive, which does not allow the DSF to explore large domain during training and restricts how expressive it can be compared to a standard neural network. Moreover, DSF are restricted to small V, and the number of parameters increases with the cardinality of V. That not true for LEASURE, which number of parameters grows with the dimensionality of elements in V. This makes DSF useful for small datasets, but makes it prohibitively expensive to use on larger problems. In fact, we could not compare LEASURE to DSF on LAL or PE tasks, as it was not feasible to train DSF on these sets. For LAL experiment, we also compare with a recent deep active learning approach (Ash et al.) 2020). Finally, we want to add that LEASURE can be seamlessly integrated with any standard Machine Learning library, and since the architecture of the learned policy in LEASURE is not restrictive, any available optimization trick can be used achieve better performance. In fact, existing 'imitation learning' baaming'-based approaches for LAL, such as Liu et al. (2018), can be viewed as special cases of LEASURE (i.e. without regularization). On the other hand, DSF cannot be as easily implemented. and the standard libraries are not optimized for the DSF architecture.
6.1 SET COVER
Before testing our approach on a real-world scenario, we showcase its performance on a simple submodular and monotonic maximization problem. Set cover is classical example: given set of elements U = 21.2...., n} (called the universe) and a collection of m sets S = {s1,.., Sm whose union equals the universe, the set cover problem union equals the universe. Formulated as a policy learning problem, the goal is to learn the score E such that for any S₁ S, E S,
identify the smallest sub-collection of S whose
function g : 2 S
g(St,z) R 9 (S,, = UsES, 8 8U2l - Usess 8/.
Given we can then define a policy π 2 + S as ((i) = argmax,esg(S (S,,), ing, tuples (Stt, gxpg are collected, and then g trained on this set. We trained four different policies: a function parametrized by neural network with MSE(g. tion g with the same MSE loss and just a monotonicity regularizer, a function g trained using both monotonicity and submodular regularizers (LEASURE), well as the Deep Submodular Function baseline (Dolhansky and Bilmes| 2016). We use a modified Deepset architecture (Zaheer et al. 2017) for modeling the permutation invariant score networks g in both the SC and the LAL tasks, and provide the details in Appendix B Our dataset the subset of the Mushroom dataset (Lim) 2015), consisting of 1000 sets. Fach set contains 23 mushroom species, and there a total of 119
During train-
as the loss, func-

---

Published as a conference paper at ICLR 2021
Natey see cmvor
Foae set couer
sugemen
220
110
100
100
0o)
sumber or dlemenee the
80
70
70-
60
60
50:
regularizer
LEASURE
regularizar
LEASURE
monotonicity regullarzerr
Deep submodular functions
monotoricity regularizer
Deep submiduular functions
100
30
20
80
100
number sets
number
(a)
(b)
Figure 1: Evaluating LEASURE against baselines on set cover instances
species. The goal is train a policy to select the largest superset of these sets. We evaluate in two settings: Exact Set Cover, where we collect tuples ()),, god) for training, and Noisy Set Cover, where we have access only {(), x)) gc J. where ge is a noisy score. The networks are trained on rollouts of length 20 (i.e. on sets {S) |Si] S 20}), and tested on rollout of length up to 100.
Figure [ show the value of set cover as a function of the size of the superset. LEASURE significantly outperforms other learned policies, although Deep Submodular Function generalizes better to larger rollout lengths LEASURE gets most of its set cover gains in the first 10-20 selected points, while Deep Submodular Function continues to noticeably improve past the training rollout length. Note that Figures Ta & Tb the competing baselines all exhibit a "diminishing returns" effect, result- ing in a concave-shaped value function. With submodular-nowe regularizer, LEASURE quickly identified the sets with large marginal gains. This observation aligns with our analysis in Section
6.2 LEARNING ACTIVE LEARNING ON FASHION MNIST
In this section we demonstrate the performance of LEASURE on a real-world task that is not sub- modular monotonie, but usually exhibits submodular and monotonic behaviour.
In active learning, there is a partially labelled dataset S {St S. where St is labelled and S, is un- labelled, and a policy π 2 - S. The labelled subset St can be used infer from data (learn the image classifier, predict unlabelled protein fitness, etc). The goal of the policy to select the smallest subset S, C Su to label such that the accuracy of su- pervised learning from S, St maximized. Since selecting subset is prohibitively expensive combi- natorial task, the policy is usually sequential. In par- ticular, it selects points to add to S one by one (or in batches) using some score function g(S, U S),,) S, + R to score each point E Sa and then the policy labels the point with the largest score. If g were to be the first order difference of a submodu- lar function f, i.c. 9(A,)) e) = f(A U [e)) f(A). then the policy would be near-optimal. Moreover, as discussed above, intuitively we expect g to have this property in most cases, since adding an extra point to larger set usually has less effect than adding the same point to a smaller subset of the set.
0.500
random unce tainty
LEASURE
BADGE
0.475
no roguriar
0.440
80375
0.350
0.375
50
75
100
125
150
175
200
lSbelled
Figure 2: Combining submodular regularization with learned active learning policy for 10-class MASIST classification. The figure sum- marizes the classification error neural net- work trained on labelled images, as a function of the number of labelled images. Originally, ran- dom set of 20 images is selected, and then each policy greedily chooses the next image to label. The learned policies were trained on rollouts of length up to 30, and tested on rollouts of length 200. The "no regularizer" policy corresponds to Konyushkova al. (2017) only in this case the features are parametrized by the neural network instead of being hand engineeeeee "BADGE" cor- responds to a sequential modification of (Ash) et al. 2020). The results averaged between 500 experiments, with standard error reported.
The above motivates the use of LEASURE in active learning (Figure 2). In this experiment, the set is the Fashion-MNiSi dataset consisting of greyscale images from one of 10 clothes classes (Xiao et al.] 2)17)) The goal was to learn policy that greedily seleets "the best" point x" S. label, such that a neural network classifier trained on the labelled set S, U {o*} produces the most accurate classification of the unlabelled images. In particular, we trained the above function g predict the
7

---

Published as a conference paper at ICLR 2021
0000000
0006000
0X0X4
Lavitca
Laviic
X2
30c
150
L200lcd nts
Lateld PORt:
(a) Comparison to baseline methods
(b) Effect of scaling parameter lambda
Figure 3: Combining submodular regularization with learned active learning policy for protein engineering task. In (b), Lambda 0 corresponds to the unregularized case. Error bars are plotted standard error of the mean across 50 replicates.
accuracy gain gop from labelling point. The accuracy gain geap was measured by training the neural network classifier on both S₁ and S U {ar) and then recording the difference in validation set classification accuracy. Since obtaining exact SP for each datapoint very expensive, we instead collected noisy labels exp x gdt, obtained by training the classifier for only 10 epochs. The tuples ()),, ge } were collected using DAgger with rollouts of length 30 (starting from random batch of 20 images). For training, we used an initially unlabelled dataset with 60000 images, 2000 of which were set aside use for evaluating validation accuracy. We trained two neural networks to approximate g- an unregularized one, and one with a monotonicity and submodularity regularizer (i.e. LEASURE). See Appendix for details on architecture and training procedure.
The trained policies were tested on set of 8000 images, with additional 2000 set aside for vali- dation. At test time, we again started with a random batch of size 20 and then used each policy to sequentially select additional 200 images label (Figure 2 The recorded test error rate was collected using real gxTp, i.e. a classifier trained until training loss reaches a certain threshold. The experiment was benchmarked against the "random" policy that randomly picked the next point, the "uncertainty" policy that selected the next point by maximizing uncertainty, the "no regularizer" policy that used DAgger with MSE loss, and "BADGE" from Ash al.] (2020). See Appendix B for details. Even though LEASURE was trained on much shorter rollouts using very noisy labels, still outperformed all other baselines. This confirms our intuition that the submodular regularizer allowed the learned score function to find a local minima that generalizes well to out of sample.
6.3 PROTEIN ENGINEERING
By employing a large protein engineering database containing mutation-function data (Wang et al, 2019), we demonstrate that LEASURE enables the learning of an optimal policy for imitating expert design of protein sequences (see Appendix for detailed discussion of datasets). As in Liu et al. (2018) construct fully data-driven expert which evaluates via 1-step roll-out the effect of labeling each candidate data (in our case a protein mutant) with the objective of minimizing loss on a downstream regression task (predicting protein fitness).
When training the policy to emulate the algorithmic expert via imitation learning, we represent each state as two merged representations: (I) a fixed dimensional representation of the protein being considered (as the last dense layer of the network described in Appendix C), and (2) similar fixed dimensional representation of the data already included in the training (as sum of their embeddings), including their average label value. At each step a random pool of data is drawn from the state space and the expert policy greedily selects a protein to label, which minimizes the expected regression loss on the downstream regression task (prediction of protein fitness). Once the complete pool of data has been evaluated, the states are stored along with their associated preference score, taken their ability to reduce the loss in the I-step roll out. Using these scores, the expert selects protein sequence to add into the training set, and we retrain the model and use the updated model to predict a protein with the maximum fitness. This paired state action data is used train the policy model at the end of each episode, as described in Liu et al. (2018). As we observe in Figure 3al this method trains policy which performs nearly identically this I-step oracle expert.
The use of submodular regularization enables the learning of a policy which generalizes to a fun- damentally different protein engineering task. In experiments, LEASURE is trained to emulate
8

---

Published as a conference paper at ICLR 2021
greedy oracle for maximizing the stability of protein G. small bacterial protein used across range of biotechnology applications (Sibring et al. 1991p. We evaluate our results by applying the trained policy to select data for the task of predicting antibody binding to a small molecule. As is the case with all protein fitness landscapes, the evaluation dataset is highly imbalanced, with the vast majority of mutants conferring ical settings (proteins must be synthesized, purified and tested), we are often limited in how many labels can feasibly be generated, and the discriminative power among the best results is often more important than among the worst. To construct a metric with real- real-world applicability we assess each model by systemically examining the median Kd of the next ten data points selected at each budget, from 10 to 110 total labels. This method is utilized in recognisance of the extreme ruggedness of protein engineering landscapes, wherein the vast majority of labels are of null fitness, and the ability to select rare useful labels for the next experimental cycle is of key importance.
improvement at all. Because data is expensive label in biolog-
We observe that LEASURE outperforms all evaluated baselines, and that the inclusion of submodular optimization is mandatory to its success (Figure 3a A greedy active learner which labels the anti- body mutation with the best predicted Kd (the smallest) preforms approximately equivalently with selecting random labels. Use of dropout as an approximation of model uncertainty as in Gal and Ghahramani (2016) improves upon these baselines, although significant betterment is not achieved until approximately 35 labels are added. In comparison, the results from LEASURE diverge from all others nearly immediately, and the best model, which uses a lambda of 0.1, achieves a notable improvement in Kd, 5.81 pM, vs 7.27 μM achieved by entropy sampling. In support of methods success, we note that the learned policy preforms approximately as well as the greedy oracle which emulates (Appendix Figure 7 We observe that the results are robust within a range of possible lambda values (Figure Figure 3b and Appendix Figure Ti). and that without the use of submodular regularization the trained policy fails to learn a policy better than the selection of random labels. This is an important finding, as the method proposed by Liu et al. (2018) without LEASURE, has been shown to be a state-of-the-art method for imitation learning.
Based on these empirical results, LEASURE demonstrates significant potential as computational tool for real-worid automated experimental design tasks: In particular, in the protein engincering task, LEASURE achieves the SOTA on the benchmark data-sets considered in this work. While LEASURE does involve repeated retraining of the protein engineering network, we observe that it returns strong results even with single step of training. Additionally, the networks that are employed are very simple (Appendix C). This allows for reasonable training time (36 hours) and nearly instantaneous inference. Given the considerable time and cost of protein engineering, these computational budgets are quite modest. Protein engineering is a time consuming (months to years) and expensive undertaking (10's of thousands to millions of dollars). These projects usually strive to achieve the best possible results given a fixed budget. We have demonstrated in our work the ability deliver significant improvements in protein potency for the modest fixed budgets. Although the cost savings of engineering and testing an individual protein (or label) vary significantly based on the system, ranging tens to hundreds of dollars, we observe that to achieve a Kd of 8e-6 M LEASURE delivers an approximate cost savings of 65%, or 40 fewer labels than the next best method. The sequential synthesis and evaluation of each of these labels would likely span several months and additionally incur several thousands of dollars of materials costs.
CONCLUSION
In this paper, we introduce LEASURE, data-driven decision making framework based novel submodular-regulliized loss function. The algorithm was inspired by the recent developments of aaammodular-surrgggtt-baeeee near-optimal algorithms for sequential decision making. We have demonstrated LEASURE on several diverse set of decision making tasks. Our results suggest that LEASURE can be easily integrated with modern deep imitation learning pipelines, and that it is efficient to run, while still reaching the best performance among the competing baselines. In addition to demonstrating the strong empirical performance on several use cases, we believe our work also provides useful insights in the design and analysis of novel information acquisition heuristics where traditional ad-hoc approaches are not feasible.
Acknowledgements. This research was supported in part by funding from NSF #1645832, NIH ST32GGM112922 The Rosen Bioengineering Center, Raytheon, Beyond Limits, JPL, and UChicago CDAC via a JTFI AI + Science Grant. This work was additionally supported by NVIDIA corporation through the donation of the GPU hardware used in experiments.
9

---

Published as a conference paper at ICLR 2021
REFERENCES
E. C. Alley, G. Khimulya, S. Biswas, M. AlQuraishi, and G. M. Church. Unified rational protein engineering with sequence-based deep representation learning. Nat. Methods, 16112):315-1122, 12 2019.
Jordan T. Ash, Chicheng Zhang, Akshay Krishnamurthy, John Langford, and Alekh Agarwal. Deep batch active learning by diverse, uncertain gradient lower bounds. In International Conference on Learning Rep- net/ n wtr.moormmmmmm w
resentations, 2020. /
Francis Bach. Submodular functions: from discrete continuous domains. Mathematical Programming, 175 (1-2):419 459, 2019.
Ashwinkumar Badanidiyuru, Baharan Mirzasoleiman, Amin Karbasi, and Andreas Krause. Streaming sub- modular maximization: Massive data summarization the fly. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 671-680, 2014.
Maria-Florina Balcan and Nicholas JA Harvey. Submodular functions: Learnabliity, structure, and optimiza- tion. SIAM Journal on Compuring, 47(3):703-754, 2018.
Mislav Balunovic, Pavol Bielik, and Martin T Vechev. Learning solve smt formulas. In NeurlPS, pages 10338-1000 10349, 2018.
Andrew An Bian, Joachim M Buhmann, Andreas Krause, and Sebastian Tschiatschek. Guarantees for greedy maximization of non-submodular functions with applications. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 498 507.55772400 2017a.
Andrew An Bian, Baharan Mirzasoleiman, Joachim Buhmann, and Andreas Krause, Guaranteed non-convex optimization: Submodular maximization over continuous domains. In Artificial Intelligence and Statistics, pages 11 1-000, 20.7b.
Niv Buchbinder, Moran Feldman, Joseph Naor, and Roy Schwartz. Submodular maximization with cardinality constraints. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 1433-1452. SIAM, 2014.
K. Chaloner and 1. Verdinelli. Bayesian experimental design: A review. Statistical Science, 10(3):273-304, 1995.
Yuxin Chen, S Hamed Hassani, Amin Karbasi, and Andreas Krause. Sequential information maximization: When is greedy near-optimal? In Conference Learning Theory, pages 338-363, 2015a.
Yuxin Chen, Shervin Javdani, Amin Karbasi, James Andrew Bagnell, Siddhartha Srinivasa, and Andreas Krause. Submodular surrogates for value of information. In Proc. Conference on Artificial Intelligence (AAAI), January 2015b.
Yuxin Chen, S. Hamed Hassani, and Andreas Krause. Near-optimal bayesian active learning with correlated and noisy tests. In Proc. International Conference Artificial Intelligence and Statistics (AISTATS), April 2017a.
Yuxin Chen, Jean-Michel Renders, Morteza Haghir Chehreghani, and Andreas Krause. Efficient online learning for optimizing value of information: Theory and application to interactive troubleshooting. In Proceedings of the 33rd Conference Uncertainty in Artificial Intelligence (UAI 2017). volume pages 966-983. Curran Associates, Inc., 2017b.
Sonia Chernova and Andrea I. Thomaz. Robot learning from human teachers. Synthesis Lectures on Artificial Intelligence and Machine Learning, 8(3)11121, 2014.
Sanjiban Choudhury, Ashish Kapoor, Gireeja Ranade, and Debadeepta Dey. Learning to gather information via imitation. In 2017 IEEE International Conference on Robotics and Automation (ICRA), pages 908 915.
IEEE, 2017.
Brian W Dolhansky and Jeff A Bilmes. Deep submodular functions: Definitions and learning. In Advances in Neural Information Processing Systems, pages 3404-3410 2016.
Khalid El-Arini, Gaurav Veda, Dafna Shahaf, and Carlos Guestrin. Turning down the noise in the blogosphere. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data min- ing, pages 289-298, 2009.
Moran Feldman, Ashkan Norouzi- Fard, Ola Svensson, and Rico Zenklusen. The one-way communication complexity of submodular maximization with applications to streaming and rohustness. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 1363-1374, 2020.
10

---

Published as a conference paper at ICLR 2021
Yarin Gal and Zoubin Chahramani. Dropout bayesian approximation: Representing model uncertainty in deep leamnin. In Maria Florina Balcan and Kilian Q. Weinberger, editors, Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 1050-1059, New York, New York, USA, 20-22 22 Jun 2016. PMLR. htl/tttp:/pprccodiiii
m1 r. wwwps/eesee... wwwpp//wws/...eeeepe.ppppep vttp/v88/gg/ wa..l...ii.. html
Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combinatorial opti- mization with graph convolutional neural networks. In Advances in Neural Information Processing Systems, pages 15580-15592, 2019.
Daniel Golovin and Andreas Krause. Adaptive submodularity: Theory and applications in active learning and stochastic optimization. Journal of Artificial Intelligence Research, 42:427-453 2011.
He He, Hal Daume III, and Jason M Eisner. Learning to search in branch and bound algorithms. In Advances in neural information processing systems, pages 3293-3301, 2014.
Gaurush Hiranandani, Harvineet Singh, Prakhar Gupta, Iftikhar Ahamath Burhanuddin, Zheng Wen. and Branislav Kveton. Cascading linear submodular bandits: Accounting for position bias and diversity in online learning to rank. In Uncertainty Artificial Intelligence, pages 722-732. PMLR, 2020.
Thibaut Horel and Yaron Singer. Maximization of approximately submodular functions. In Advances in Neural Information Processing Systems, pages 3045-3053 2016.
Shervin Javdani, Yuxin Chen, Amin Karbasi, Andreas Krause, James Andrew Bagnell, and Siddhartha Srini- vasa. Near-optimal bayesian active learning for decision making. In In Proc. International Conference on Artificial Intelligence and Statistics (AISTATS), April 2014.
Ehsan Kazemi, Marko Mitrovic, Morteza Zadimoghaddam, Silvio Lattanzi, and Amin Karbasi. Submodular streaming in all its glory: Tight approximation, minimum memory and low adaptive complexity. In Interna- tional Conference on Machine Learning, pages 331 1-3320, 2019.
Elias Boutros Khalil, Pierre Le Bodic, Le Song, George Nemhauser, and Bistra Dilkina. Learning to branch in mixed integer programming. In Thirtieth AAAI Conference on Artificial Intelligence, 2016.
Ksenia Konyushkova, Raphael Sznitman, and Pascal Fua. Learning active learning from data. In Advances in Neural Information Processing Syxtems, pages 4225-4235, 2017.
Andreas Krause and Daniel Golovin. Submodular function maximization. Tractabiliry, 3:71-104, 2014.
Andreas Krause and Carlos Guestrin. Optimal value of information in graphical models. JAIR, 35:557-591, 2009.
Andreas Krause, Ajit Singh, and Carlos Guestrin. Near-optimal sensor placements in gaussian processes: Theory, efficient algorithms and empirical studies. Journal of Machine Learning Research, 9(2), 2008
Jure Leskovee, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne VanBriesen, and Natalie Glance. Cost-effective outhreak detection in networks. In Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 420-429. 2007.
Ching Lih Lim. suite of greedy methods for set cover computation. 2015.
Hui Lin and Jeff Bilmes. A class of submodular functions for document summarizztion. In Proceedings of 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pages 510-520, 2011.
Hui Lin and Jeff Bilmes. Learning mixtures of submodular shells with application document summarization. In Proceedings of the eventy-Eightl Conference on Uncertainty in Artificial Intelligence, UAI' 12, page 479490, Arlington. Virginia, USA, 2012. AUAI Press. ISBN 9780974903989,
Dennis Lindley. On a measure of the information provided by an experiment. The Annals of Mathematical Statistics, pages 986-1005, 1956.
Ming Liu, Wray Buntine, and Gholamreza Haffari. Learning how to actively learn: deep imitation learning approach. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1874-1883 2018
Marko Mitrovic, Mark Bun, Andreas Krause, and Amin Karbasi. Differentially private submodular maximiza- tion: data summarization in disguise. In International Conference on Machine Learning, pages 2478-2487, 2017.
11

---

Published as a conference paper at ICLR 2021
George Nemhauser. Laurence A Wolsey, and Marshall L Fisher. An analysis of approximations for maximiz- ing submodular set functionsi. Mathematical programming, 14(1):265 294,, 1978.
Filip Radlinski, Robert Kleinberg, and Thorsten Joachims. Learning diverse rankings with armed bandits. In Proceedings of the 25th international conference Machine learning, pages 784-791, 2008.
2008
Roshan Rao, Nicholas Bhattacharya, Neil Thomas, Yan Duan, Xi Chen, John Canny, Pieter Abbeel, and Yun S. Song. Evaluating protein transfer learning with tape. Advances in neural information processing systems, 32: 9689-9701, Dec 2019. ISSN 1049-5258. htt.hhtps://pple 33390682[pmid).
ncbi n m1mm ni wwt..ho./333900e.mm
Stéphane Ross, Geoffrey Gordon, and Drew Bagnell. A reduction of imitation learning and structured pre- diction no-regret online learning. In Proceedings of the fourteenth international conference on artificial intelligence and statistics, pages 627-635, 2011.
Stephane Ross, Jiaji Zhou, Yisong Yue, Debadcepta Dey, and Drew Bagnell. Learning policies for contextual submodular prediction. In International Conference on Machine Learning, pages 1364-1372, 2013.
M. C. Runge. S. J. Converse, and J. E. Lyons. Which uncertainty? using expert elicitation and expected value of information to design an adaptive program. Biological Conservation, 2011.
Yash Satsangi, Shimon Whiteson, Frans A Oliehoek, and Matthijs TJ Spaan. Exploiting submodular value functions for scaling up active perception. Autonomous Robots, 42(2):209-233 2018.
Adish Singla, lija Bogunovic, Gábor Bartók, Amin Karbasi, and Andreas Krause, Near-optimally teaching the crowd to classify. In ICML, volume 1, page 3, 2014.
Ruben Sipos, Pannaga Shivaswamy, and Thorsten Joachims. LLarg--aargn learning of submodular summa- rization models. In Proceedings of the 13th Conference of the European Chapter of the Association for Computational Linguistics, pages 224-233, 2012.
U. Sjhring, L.. Bjrck, and W. Kastemn Streptococcal protein G. Gene structure and protein binding properties. Biol. Chem., 266(1) 39: -05, Jan 1991.
Jialin Song. Ravi Lanka, Albert Zhao, Aadyot Bhatnagar, Yisong Yue, and Masahiro Ono. Learning to search via retrospective imitation. arXiv preprint arXiv:1804.00880 2018.
Jialin Song, Ravi Lanka, Yisong Yue, and Bistra Dilkina. A general large neighborhood search framework for solving integer linear programs. In Advances in Neural Information Processing Systems, 2020.
Matthew Streeter, Daniel Golovin, and Andreas Krause. Online learning of assignments. In Y. Bengio, D. Schuurmans, J. Lafferty, C. Williams, and A. Culotta, editors, Advances in Neural Information Pro- cessing Systems, volume 22. Curran Associates, Inc., 2009. cc/papex:2009/Fi1ee 20t111eeeee0111111 (e1e441155227442522 25044444500000665533332222222229
www.inngg....ss...meem.m neurips. ppf
C. Y. Wang, P. M. Chang, M. L. Ary, B. D. Allen, R. A. Chica, S. L. Mayo, and B. D. Olafson. ProtaBank: A repository for protein design and engineering data. Protein Sci., 28(3):672, Mar 2019.
Kai Wei. Rishabh Iyer, and Jeff Bilmes. Submodularity in data subset selection and active learning. In Inter- national Conference Machine Learning, pages 1954-1963, 2015.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms, 2017.
Baosheng Yu, Meng Fang, and Dacheng Tao. Linear submodular bandits with a knapsack constraint. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
Yisong Yue and Carlos Guestrin. Linear submodular bandits and their application diversified retrieval. In Shawe- Shawe-Taylor, R. Zemel, P. Bartlett, F. Percira, and K. Q. Weinberger, editors, Advances in Neural Infor- mation Processing Systems, volume 24, Curran Associates, Inc., 201 URL wwt.httpst.. /tpp:///d/oooceeeeeee/ooo Fi 1ttp////eeee/333e5be0edeeeed
neurips. Swarriss.cc/aperr//ee
.dd
Yisong Yue and Thorsten Joachims. Predicting diverse subsets using structural svms. In Proceedings of the 25th international conference on Machine learning, pages 1224-1231, 2008
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexan- der J Smola. Deep sets. In I. Guyon, U. V. Luxburg. S. Bengio, H. Wallach, R. Fergus, S. Vish- wanathan, and R. Garnett, editors. Advances in Neural Information Processing Systems, volume 30. Cur- Associates, Inc., 2017. URL. https: /ttptps:://rroro proceed i ngs. neur ps. wwtpppppp//////////e// 1e/ Paper.
12

---

Published as a conference paper at ICLR 2021
A PROOF FOR SECTION 5
A. PROOF OF THEOREM 2
Proof. The high-level idea is first connect the total expected utility of the learned policy ğ with the expected utility of the expert policy л following the analysis in DAgger (Ross et al.) 2011). Then, we will use the fact that x0 greedy with respect f. an approximation the submodular utility function
bound the one gain of the π*x against the l step gain of running the optimal policy, and subsequently bound total utility of expert policy against the optimal policy. We would eventually obtain similar result as Theorem 2, detailed follows.
More concretely, following Theorem 3.4 in DAgger, we obtain that
Elu(S#,,)) 2 Elu(S, ,k)l maxkkr O(1)
Here Amax is the largest one-step deviation from TP that á can suffer. It is equivalent to the term u the DAgger paper. Since f is c-close to monotone submodular function u, we know that
Amax S ACx/A/V ((A) maxAcV]]4]=4 u(4) cg. which is constant once is given.
Next, since Rx greedily optimizing an ag=approximation to a monotone submodular function u, know that
ESu(Srexp,ai x.)] 2 (1
x)]] kez
following the proof from Theorem in Chen et al. 2017b)
Combining both steps, have that E[u(S=,,)] 2 (1
.+]l - k(EE + AmaxeN) - 0(1)
which completes the proof.
13

---

Published as a conference paper at ICLR 2021
B SUPPELEMENTAL DETAILS FOR THE SET COVER AND MNIST ACTIVE LEARNING EXPERIMENTS
We provide additional results for set cover experiments, under the same experimental setup as Figure Ia and [b] The subplots 4a and 4b show the mean square emror of learned policy g function of the size of St. We provide a zoomed-in version of 44b in Figure (4c In Figure [4c] we show it is clear that training the neural network the monotonicity regularizer only does not help learn out of sample the error rapidly increases as soon as the test rollout length becomes larger than the training rollout length.
In Noisy Set Cover experiment (Figure 4a each label of the element added to the superset was perturbed with (0, 1) noise. As result, the variance of the total noise linear in the number of sets. So, it is reasonable that the MSE error grows with number of sets the policies cannot learn to predict random noise. While stochastic MSE of LEASURE and the no-regularizer policy are similar, LEASURE outperforms in the number of elements added, which is what matters in practice (Fig- ure D. These two figures confirm our intuition that when the problem is not exactly submodular, Leasure will still generalize better than no regularizer by learning to ignore small deviations from submodularity. Finally,
also expected that DSF has lower MSE than Leasure when the label noise is too large Deep Submodular Functions are required to be submodular. When the stochastic- ity in the MSE becomes overwhelmingly large, that restrictive requirement becomes an advantage. However, when the MSE variance is not too large, the lack of expressiveness and the difficulty of optimization of DSF make lose its advantage compared to Leasure.
set
40
Exact
regularizer
LEASURE
regulbrizer
LEASURE
monotonicity
submodular Functions
monotonicily
submocular functions
30
MER
15
5-
20
number sets in the superset
number of sets the superset
(a)
(b)
4.0
Exact set cover
no requiarize"
LEASURE
3.5
monotonicity reqularizer
3.0
2.0
1.5
1.0
0.5
0.0
20
40
60
80
100
number sets in supersec
(c)
Figure 4: Supplemental results: Set cover
For completion, we also provide our architecture and parameter choices for both set cover and Learning Active Learning (LAL) on MNIST experiments. For set cover, the problem is too simple to require DAGGER (Ross et al. 2011). Instead, the tuples are generated randomly. For active learning on MNIST, the tuples are indeed generated using Algorithm 1. For MNIST, we first preprocessed our dataset with PCA, leaving the number of vectors necessary achieve 80% covariance on the training set (24 vectors). That was necessary to allow the comparison with DSF. For set cover, each element was set containing 23 elements v u? 23 where yf to the label of the species. As neural network input, v was simply represented as a vector of (ut.....??? 233
integer corresponding
14

---

Published as a conference paper at ICLR 2021
Both set cover and MNIST used modified Deepset architecture (Zaheer et al. 2017) for net- works as follows: Given a set A = { (oo .... 2 C V and a datapoint v E V, the score network first preprocesses all inputs to. ..., 2k: to obtain learned embeddings Vo ... Ug U. (See Figure (5) Then, the elements in A are combined using Deepsets architecture to produce a learned set embedding A. Finally, A and are concatenated and then learned linear layer and Leaky ReLu nonlinearity applied to produce 9(A,e) u). (See Figure O All dense layers have 64 neurons and bias term. Using this Deepsets-like framework, we achieve permutation invariance of elements in set A while also keeping the network expressive enough to learn a wide range of functions.
Learning element representation
Dense Layer
Dense Layer
Input V
Embedding 7
+ Tanh
Tanh
Figure 5: Score neural network architecture illustration
Combining element representation using DeepSets
Bo
Σ 02
Dense Layer
Set em- bedding A
+ Tanh
Up
Dense Layer + Leaky ReLu
0(A,
Figure 6: Score neural network architecture illustration.
For both tasks, the score networks are trained using ADAM with a learning rate of 1e-3. Beta parameter from Line in LEASURE value of the parameter did not matter as long as it starts with at least and degrades towards almost 0 after N iterations. The À and y parameters were picked using a hyperparameter sweep in log space. As per our intuition, have found that the strength of the parameters should reflect your certainty that the task is submodular and/or monotone. For set cover, À = 0.1, y = 0.5, while for active learning À= 0.001 and 7 0.001. Notice that the values are not comparable between different experiments: for MNIST Learning Active Learning (LAL.), g v) [0. outputs the accuracy gain of adding v to A and training a supervised model on it; for set cover, g ( v) E {0, 1] outputs the number of new elements added to the set by adding to A. For LAL., the values of go are usually much smaller than 1, particularly for larger sets. Thus, the values for the two regularizers had to be smaller so that the model learns not just the regularizer.
picked randomly to be 5. From experiments, the exact
Finally, we wanted to discuss our baselines in Fashion MNIST experiments. Figure 2 we have four baselines: random, uncertainty, BADGE Ash et al. 2020), and regularizer. The no regu- larizer baseline was trained identically to LEASURE, except for the absense of submodularity and monotonicity regularizers. The regularizer baseline performed well the sets with up 30 additional points corresponding exactly to the length of the training rollouts. However, it failed to generalize. On the other hand, the submodular regularizer allowed the learned score function find a local minima that generalized well to out of sample. Finally, BADGE did not seem to perform well when the number of datapoints in the was large, likely because the gradient signal from adding any one additional datapoint was too weak and thus the selection of the next best datapoint was too noisy.
Some more details regarding BADGE (Ash et al. 2020). The authors do not learn policy, instead, they use gradients of the classifier (gradient embedding) to select a useful, diverse batch. Although BADGE was originally made for a batch setting, the authors' main idea is still applicable to our case: they argued that the next datapoint(s) can selected by looking at which fictitious labels would produce the largest gradients in the classifier network. Therefore, we replaced the kmeans++ algorithm the authors suggested with simply selecting the datapoint that corresponds to the largest gradient norm. This algorithm has advantage that it does not require trained policy network. However, provides no guarantees about submodularity of the resulting policy, and, in our exper- iments, the performance degrades with the size of the set likely because the gradient signal from
15

---

Published as a conference paper at ICLR 2021
adding any one additional datapoint too weak and thus the selection of the next best datapoint was too noisy. Since BADGE requires a neural network classifier/rgrressor, we could not use it as baseline for Set Cover (Set Cover regression function is simply adding all elements in the superset).
The no-regularizer baseline is similar to that of Konyushkoaa et al. (017)) However, the problem considered in Konyushkova et al. (2017) is not compatible with most of the tasks considered here (for MNIST, yes we use random forest classifiers; but for others not). Furthermore, Konyuskkovaa (017)) treated the problem under classical supervised learning setting this is often desirable, given that we are learning policy from non i...d data samples.
16

---

Published as a conference paper at ICLR 2021
C SUPPLEMENTL DETAILS FOR THE PROTEIN ENGINEERING EXPERIMENTS
Dataset Our datasets were identified in Protabank (Wang al. 2019) for training of active learn- ing policies and benchmarking of performance. In selecting datasets upon which to train our active learning models several factors were considered. As the state space of possible protein variants for typical engineering application is very large, size is our foremost criteria. Additionally it will be ad- vantageous to use datasets which characterize mutations scans), and those which include epistatic interactions. We also desire to identify datasets which have a high quality, quantitative readout, such as calorimetry, fluorescence, or SPR data.
all amino acids (as opposed to Alanine
Protein Engineering Methods Embeddings of protein sequences were created using the TAPE
repository (Rao et al. 2019) according to the UniRep system as first proposed in Alley et al. (2019).
UniRep produces protein embeddings matrix of shape (length protein sequence, 1900), although we average together the embeddings only of positions being engineered to produce a consistent embedding of shape (1900.). We have implemented the active learning imitation learning algorithm proposed in Liu et al. (2018) to work with the protein embedding representations described above. Pseudocode for this method is presented Algorithms 1 and 2 from the original work. As in Liu et al. (2018), our policy network consists of single dense unit which acts sequentially on the pool of samples being considered to produce preference score. Our downstream protein engineering network (which was used to compute the preference score of the expert policy) acts on the protein embeddings prepared using TAPE. The network consists of an attention layer, followed by a 1- dimensional convolution layer (128 filters, kernel size 3), before being flattened and applying two fully connected layers of 128 units each. When predicting protein fitmess, dropout is applied with a probability of 0.5 and an additional dense layer is applied with one unit and linear activation. Both networks are trained using ADAM with a learning rate of 1e-3. The implementation of this part of the project is nearly identical to Liu al. (2018), only changing the data representation, protein fitness network structure, and values of K (30), B (100) and T (20) as listed in the appendix of our work. Beta fixed at 0.5, although the method was shown to be robust to a range of values. At training time, 100 labels are randomly selected for evaluating the effect of the greedy oracle, and 10 data are randomly selected to form the initial data set for learning. The superset appended each step of training the policy to maintain a size of 2x the labeled dataset. The training of a policy using these settings takes 36 hours on modern multiprocessor computer equipped with an NVIDIA Titan V GPU.
00800000
LEGGUE
Grada
008369
00600075
0083060
640
Paints
Scaline Roqubreerr Lawbde Value
(a) Comparison of policy to greedy oracle which it em- ulates
(b) Effect of scaling parameter lambda and empirical evidence for selecting value
Figure 7: Supplemental results for the protein engineering experiments of Section 6.3 (a) We ob-
serve that the policy learned by LEASURE preforms approximately as well as the greedy oracle which it emulates. In this experiment the policy was derived from the training set, but the greedy oracle is operating on the test set. (b) Lambda linearly scales the value of the regularizer term. When lambda takes value 0.01, the magnitude of the (scaled) regularizer term (represented by the blue bar) aligns the best with the magnitude of the cross entropy loss (represented by the orange bar). This consistent with what we observed in Figure 3h where À 0.01 leads to well-regularized model behavior.
17


Reviews:
[{"review_id": "_m1PUbmeUz7", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper combines combines submodular surrogates for sequential decision making with imitation learning. Specifically, it proposes to learn an acquisition function g by imitating an expert which is assumed to be following a greedy policy wrt a general submodular surrogate f. This is accomplished by regularizing g to encourage diminishing returns and monotonicity. The learning algorithm is a modified version of DAgger which is consistent with the expert and provably near-optimal utility. Results outperform baselines on various sequential decision making tasks.\n\n\nNovelty/Impact\n- Elegant, novel combination of DAgger with submodular regularization\n- Potentially impactful idea (comparison to additional baselines would confirm this)\n- Theoretical contribution is a straightforward combination of (Ross, 2011) and (Golovin and Krause, 2011). On its own this is not very impactful\n\nExperiments:\n- Good, concise experiments across a range of applications. \n- The expert's utility function is shown to exhibit submodularity, strengthening the validity of the proposed approach\n- Baselines are illustrative, but the paper would benefit from having additional baselines (for example [1-2] for active learning)\n\nClarity/Correctness:\n- In the proof of Theorem 2, can you explain the first inequality when bounding the one-step gain of $\\hat{\\pi}$? What if $\\pi^{exp}$ is not along the learned trajectory?\n- Do the baselines in section 6.1 use Algorithm 1 (i.e. DAgger) with different loss functions?\n- typo: \"groundset\" should be \"ground set\"\n\nPros\n- Good organization\n- Potentially high impact\n- Thorough experimental methodology\n\nCons\n- Some statements unclear\n- Somewhat weak baselines\n- Limited theoretical contribution\n\nQuestions:\n- Is the bound in Theorem 2 tight?\n- How does the algorithm perform when the surrogate is non-monotone?\n- Is the poor performance on noisy set cover due to noisy data or submodularity being violated?\n\n\n[1] Wei, Iyer, and Bilmes. Submodularity in Data Subset Selection and Active Learning, ICML 2015. http://proceedings.mlr.press/v37/wei15.html\n\n[2] BADGE Ash et al. Deep Batch Active Learning by Diverse, Uncertain Gradient Lower Bounds, ICLR 2020. https://arxiv.org/abs/1906.03671\n\n\nEDIT: The authors addressed my main concerns, fixed a crucial bug in the claim/proof of Theorem 2, and added many more clarifying details to a revised submission. Therefore I will keep my rating the same\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "JL8xBOOlfvB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Authors propose to approximate the marginal gain of the submodular function (also called discrete derivative) with a neural network. The data for training the model is collected with DAgger, and therefore the proposed method inherits guarantees of DAgger.\n\nClarity: My main concern is that some of the important details are not discussed in the paper. Authors only mention that $g$, the marginal gain approximator, is a neural network; I couldn't find any discussions on what kind of neural network was used. Since the input of the neural network includes a power set, the input representation of the data as well as the neural network architecture would be of interest. Also, the description of protein engineering experiment is a bit confusing. It mentions that the expert is trained on a downstream regression task, but it is also mentioned that 'LeaSure is trained to emulate a greedy oracle for maximizing the stability of protein G', which is inconsistent. Even in the Appendix C, details on the experiments such as the description of parameters or the pseudocode of the algorithm are deferred to references.\n\nQuality: The main claim of the paper is that the cost of evaluating the expert policy can be reduced by approximating it as a neural network. However, there are many factors contributing the cost of employing the proposed method, as a potentially large neural network would need to be trained, and data points for training the network should be acquired. A larger neural network would make it more expensive to evaluate $g$, diminishing the value of approximating the expert. Also, a larger neural network may be less sample-efficient. It would be interesting to discuss how these other cost factors should be considered in order to optimize the total cost. \n\nOriginality, Significance: The idea of approximating the marginal gain with a neural network seems new, and also broadly applicable across applications of submodular optimization.\n\nPros:\n* The idea is original and creative\n* The proposed method is widely applicable\n\nCons:\n* The practical utility is quite uncertain and questionable\n* The paper lacks important details, even the architecture of neural networks used\n\n---\n\nIn the revision, authors provided detailed clarifications on their approach and practical utility of the proposed method. Therefore, I am changing the rating of my review.", "extra_scores": {}, "extra_text": {}}, {"review_id": "G4gzy1xo3D7", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "1. Summary of the paper contributions\n    (1) This paper proposes a 'submodular-norm' based regularization term when learning a score function based on data-driven optimization, which encourages the underlying utility function to exhibit \"diminishing return\". The learned scoring function can be used as a greedy heuristic in combinatorial sequential decision making tasks, in which expert policy is expensive to evaluate.\n    (2) The proposed approach can be easily integrated with other imitation learning pipelines when the considered problems fall into the (approximate) submodular set. This is shown in the experiment section by examples including set cover, learning active learning,  and learning to imitate expert design in protein engineering.\n\n2. Strong and weak points of the paper\n    (1) Strong points: The considered problem is interesting and meaningful. This paper provides a new 'submodular-norm' when learning the scoring function, which seems to be effective in the shown examples. Since the proposed algorithm is a specialization of  the DAgger algorithm (Ross et al., 2011), the performance guarantee for the learned scoring function is established.\n    (2) Weak points: Although the proposed algorithm can achieve the desired performance guarantees in Theorem 1 and 2, these results are a natural extension (or direct result) of prior work Ross et al., 2011. The proposed 'submodular-norm' seems to be effective in the shown 3 examples, but many details are omitted. This makes it hard to tell the proposed algorithm's effectiveness and efficiency in practice.\n\n3. My recommendation\n    I tend to reject this paper, but am open to change my score after rebuttal. My main concern is on the experiment part, which lack many details and baseline methods. \n\n4. Supporting arguments for your recommendation\n    The paper's theoretical results are a natural extension or direct result of prior work, so I focus more on the empirical performance part such as whether the propose algorithm is efficient to train and the effectiveness compared to baseline methods. Although the results shown in the paper seem to be effective, many details and baseline methods are not shown. Also, the second example of learning active learning policy seems to be not very efficient. Because it needs a (noisy) expert scoring function value for every evaluated data point. This 'expert' scoring function is trained for every data point encountered in training. Although it uses only 10 epochs to obtain this value, it is still very time-consuming considering the rollout length and the total number of rounds.\n\n5. Questions\n    (1) For the m shown in Theorem 1, is it the T in Algorithm 1 step 7?\n    (2) What does the k stand for in Theorem 2?\n    (3) For the 3 examples, can the author/s provide details on how the labeled tuples are generated? Is it by following Algorithm 1? If so, what's the \\beta and N values for these examples?\n    (4) For set cover example, the compared DSF generalizes better to larger rollout lengths as shown in Fig. 1. Does it mean the DSF may achieve the total of 119 species with least number of rollout sets in the superset? Any result in this metric?\n    (5) For the 3 examples, the estimated scoring function g is parametrized by neural network. Can the author/s provide details on how the parametrization is constructed? \n    (6) Why does the author/s not include other imitation learning methods as baseline like Liu et al., 2018 discussed in Section 2?\n    (7) How to determine the regularization parameters \\lambda and \\gamma? For other compared methods, did the author/s tune their hyper-parameters?\n    (8) The 'no regularizer' policy in Fig. 2 is adapted from Konyushkova et al., 2017 without hand-engineered features. Will this lower the method of Konyushkova et al., 2017's performance in general?", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers the problem of sequential decision making through the lens of submodular maximization. I read the paper myself and found the idea quite appealing and interesting. The authors also make a very effective rebuttal and brought a borderline paper into a clear accept. 
Decision: Accept (Poster)