Learning Policies for Contextual Submodular Prediction

Introduction

Many problem domains, ranging from web applications such as ad placement or content recommendation to identifying successful robotic grasp trajectories require predicting lists of items. Such applications are often budget-limited and the goal is to choose the best list of items, from a large set of possible items, with maximal utility. In ad placement, we must pick a small set of ads with high click-through rate. For robotic manipulation, we must pick a small set of initial grasp trajectories to maximize the chance of finding a successful trajectory via more extensive evaluation or simulation.

In all of these problems, the predicted list of items should be both relevant and diverse. For example, recommending a diverse set of news articles increases the chance that a user would like at least one article (Radlinski et al., 2008). As such, recommending multiple redundant articles on the same topic would do little to increase this chance. This notion of diminishing returns due to redundancy is often captured formally using submodularity (Guestrin & Krause, ).

Exact submodular function optimization is intractable, but simple greedy selection is known to have strong near-optimal performance guarantees and typically works very well in practice (Guestrin & Krause, ). Given access to the submodular reward function, one could simply employ greedy to construct good lists.

In this paper, we study the general supervised learning problem of training a policy to maximize a submodular reward function. We assume that the submodular reward function is only directly measured on a finite training set, and our goal is to learn to make good predictions on new test examples where the reward function is not directly measurable.

We develop a novel agnostic learning approach based on new analysis showing that a single no-regret learner can produce a near-optimal list of predictions.This result may seem surprising given that previous approaches (Streeter & Golovin, 2008) require a sequence of online learners – one for each position in the list. We use a reduction approach to “lift” this result to contextual hypothesis classes that map features to predictions, and bound performance relative to the optimal sequence of hypotheses in the class. In contrast to previous work, our approach ensures both data-efficiency as well as performance guarantees in the fully agnostic setting. Moreover, our approach is simple to implement and easily integrates with conventional off-the-shelf learning algorithms. Empirical evaluations show our approach to be competitive with or exceed the state-of-the-art performance on a variety of problems, ranging from trajectory prediction in robotics to extractive document summarization.

Related Work

The problem of learning to optimize submodular reward functions from data, both with and without contextual features, has become increasingly important in machine learning due to its diverse application areas. Broadly speaking, there are two main approaches for this setting. The first aims to identify a model within a parametric family of submodular functions and then use the resulting model for new predictions. The second attempts to learn a strategy to directly predict a list of elements by decomposing the overall problem into multiple simpler learning tasks.

The first approach (Yue & Joachims, 2008; Yue & Guestrin, 2011; Lin & Bilmes, 2012; Raman et al., 2012) involves identifying the parameterization that best matches the submodular rewards of the training instances. These methods are largely limited to learning non-negative linear combinations of features that are themselves submodular, which often restricts their expressiveness. Furthermore, while good sample complexity results are known, these guarantees only hold under strong realizability assumptions where submodular rewards can be modeled exactly by such linear combinations (Yue & Guestrin, 2011; Raman et al., 2012). Recent work on Determinental Point Processes (DPPs) (Kulesza & Taskar, 2011) provide a probabilistic model of sets, which can be useful for the tasks that we consider. These approaches, while appealing, solve a potentially unnecessarily hard problem in first learning a holistic list evaluation model, and thus may compound errors by first approximating the submodular function and then approximately optimizing it.

The second, a learning reduction approach, by contrast, decomposes list prediction into a sequence of simpler learning tasks that attempts to mimic the greedy strategy (Streeter & Golovin, 2008; Radlinski et al., 2008; Streeter et al., 2009; Dey et al., 2012). In (Dey et al., 2012), this strategy was extended to the contextual setting by a reduction to cost-sensitive classification. Essentially, each learning problem aims to best predict an item to add to the list, given features, so as to maximize the expected marginal utility. This approach is flexible, in that it can be used with most common hypothesis classes and arbitrary features. Because of this decomposition, the full model class (all possible sequences of predictors) is often quite expressive, and allows for agnostic learning guarantees.This first strategy of learning the parameters of a submodular function can be seen as a special case of this second approach (see section 5.1). This generality comes at the expense of being significantly less data-efficient than methods that make realizability assumptions such as (Yue & Guestrin, 2011; Raman et al., 2012), as the existing approach learns a different classifier for each position in the list.

Compared with related work, our approach enjoys the benefits of being both data-efficient while ensuring strong agnostic performance guarantees. We do so by developing new analysis for online submodular optimization which yields agnostic learning guarantees while learning a single data-efficient policy.

Background

Let $\mathcal{S}$ denote the set of possible items to choose from (e.g. ads, sentences, grasps). Our objective is to pick a list of items $L\subseteq\mathcal{S}$ to maximize a reward function $f$ that obeys the following properties:“Lists” generalize the notion of “set” more commonly used in submodular optimization, and enables reasoning about item order and repeated items (Streeter & Golovin, 2008). One may consider sets where appropriate.

Monotonicity: For any lists $L_{1},L_{2}$, $f(L_{1})\leq f(L_{1}\oplus L_{2})$ and $f(L_{2})\leq f(L_{1}\oplus L_{2})$

Submodularity: For any lists $L_{1},L_{2}$ and item $s\in\mathcal{S}$, $f(L_{1}\oplus s)-f(L_{1})\geq f(L_{1}\oplus L_{2}\oplus s)-f(L_{1}\oplus L_{2})$.

Here, $\oplus$ denotes the concatenation operator. Intuitively, monotonicity implies that adding more elements never hurts, and submodularity captures the notion of diminishing returns (i.e. adding an item to a long list increases the objective less than when adding it to a shorter sublist). We further assume for simplicity that $f$ takes values in $$, and that$f(\emptyset)=0$where$\emptyset$denotes the empty list. We will also use the shorthand$b(s|L)=f(L\oplus s)-f(L)$to denote the marginal benefit of adding the item$s$to list$L$.

A simple example submodular function that repeatedly arises in many domains is one that takes value until a suitable instance is found, and then takes on value $1$ thereafter. Examples include the notion of “multiple choice” learning as in (Dey et al., 2012; Guzman-Rivera et al., 2012) where a predicted set of options is considered successful if any predicted item is deemed correct, and abandonment in ad placement (Radlinski et al., 2008) where success is measured by whether any predicted advertisement is clicked on.

We consider reward functions that may depend on some underlying state $x\in\mathcal{X}$ (e.g. a user, environment of the robot, a document, etc.). Let $f_{x}$ denote the reward function for state $x$, and assume that $f_{x}$ is monotone submodular for all $x$.

Our task consists in learning to construct good lists of pre-specified length $k$ under some unknown distribution of states $D$ (e.g. distribution of users or documents we have to summarize). We consider two cases: context-free and contextual.

Context-Free. In the context-free case, we have no side-information about the current state (i.e. we do not observe anything about $x$). We quantify the performance of any list $L$ by its expected value:

Note that $F(L)$ is also monotone submodular. Thus the clairvoyant greedy algorithm with perfect knowledge of $D$ can find a list $\hat{L}_{k}$ such that $F(\hat{L}_{k})\geq(1-1/e)F(L^{*}_{k})$, were $L^{*}_{k}=\operatorname*{argmax}_{L:|L|=k}F(L)$. Although $D$ is unknown, we assume that we observe samples of the objective $f_{x}$ during training. Our goal is thus to develop a learning approach that efficiently converges, both computationally and statistically, to the performance of the clairvoyant greedy algorithm.

Contextual. In the contextual case, we observe side-information in the form of features regarding the state of the world. We “lift” this problem to a hypothesis space of policies (i.e. multi-class predictors) that map features to items.

Let $\Pi$ denote our policy class, and let $\pi(x)$ denote the prediction of policy $\pi\in\Pi$ given side-information describing state $x$. Let $L_{\pi,k}=(\pi_{1},\pi_{2},\dots,\pi_{k})$ denote a list of policies. In state $x$, this list of policies will predict $L_{\pi,k}(x)=(\pi_{1}(x),\pi_{2}(x),\dots,\pi_{k}(x))$. We quantify performance using the expected value:

It can be shown that $F$ obeys both monotonicity and submodularity with respect to appending policies (Dey et al., 2012). Thus, a clairvoyant greedy algorithm that sequentially picks the policy with highest expected benefit will construct a list $\hat{L}_{\pi,k}$ such that $F(\hat{L}_{\pi,k})\geq(1-1/e)F(L^{*}_{\pi,k})$, where $L^{*}_{\pi,k}=\operatorname*{argmax}_{L_{\pi}:|L_{\pi}|=k}F(L_{\pi})$. As before, our goal is to develop a learning approach (for learning a list of policies) that efficiently competes with the performance of the clairvoyant greedy algorithm.

Context-free List Optimization

We first consider the context-free setting. Our algorithm, called Submodular Contextual Policy (SCP), is described in Algorithm 1. SCP requires an online learning algorithm subroutine (denoted by Update) that is no-regret with respect to a bounded positive loss function,See Section 4.1 and (3) for a definition of no-regret. maintains an internal distribution over items for prediction, and can be queried for multiple predictions (i.e. multiple samples).Algorithms that meet these requirements include Randomized Weighted Majority (Littlestone & Warmuth, 1994), Follow the Leader (Kalai & Vempala, 2005), EXP3 (Auer et al., 2003), and many others. In contrast to prior work (Streeter & Golovin, 2008), SCP employs only a single online learning in the inner loop.

SCP proceeds by training over a sequence of states $x_{1},x_{2},\dots,x_{T}$. At each iteration, SCP queries the online learner to generate a list of $m$ items (via Predict, e.g. by sampling from its internal distribution over items), evaluates a weighted cumulative benefit of each item on the sampled list to define a loss related to each item, and then uses the online learner (via Update) to update its internal distribution.

During training, we allow the algorithm to construct lists of length $m$, rather than $k$. In its simplest form, one may simply choose $m=k$. However, it may be beneficial to choose $m$ differently than $k$, as is shown later in the theoretical analysis.

Perhaps the most unusual aspect is how loss is defined using the weighted cumulative benefits of each item:

where $L_{t,i-1}$ denotes the first $i-1$ items in $L_{t}$, and

Intuitively, (1) represents the weighted sum of benefits of item $s$ in state $x_{t}$ had we added it at any intermediate stage in $L_{t}$. The benefits at different positions are weighed differently, where position $i$ is adjusted by a factor $(1-1/k)^{m-i}$. These weights are derived via our theoretical analysis, and indicate that benefits in early positions should be more discounted than benefits in later positions. Intuitively, this weighting has the effect of rebalancing the benefits so that each position contributes more equally to the overall loss.We also consider a similar algorithm in the min-sum cover setting, where the theory also requires reweighting benefits, but instead weights earlier benefits more highly (by a factor $m-i$, rather than $(1-1/k)^{m-i}$). We omit discussing this variant for brevity.

In principle, SCP can also be applied in partial feedback settings, e.g. ad placement where the value $f_{x_{t}}$ is only observed for some items (e.g. only the displayed ads), by using bandit learning algorithms instead (e.g. EXP3 (Auer et al., 2003)).Partial information settings arise, e.g., when $f$ is derived using real-world trials that preclude the ability to evaluate $b(s|L,x)$ (2) for every possible $s\in\mathcal{S}$. As this is an orthogonal issue, most of our focus is on the full information case.

We now show that Algorithm 1 is no-regret with respect to the clairvoyant greedy algorithm’s expected performance over the training instances. Our main theoretical result provides a reduction to an online learning problem and directly relates the performance of our algorithm on the submodular list optimization problem to the standard online learning regret incurred by the subroutine.

Although Algorithm 1 uses only a single instance of an online learner subroutine, it achieves the same performance guarantee as prior work (Streeter & Golovin, 2008; Dey et al., 2012) that employ $k$ separate instances of an online learner. This leads to a surprising fact: it is possible to sample from a stationary distribution over items to construct a list that achieves the same guarantee as the clairvoyant greedy algorithm. This fact can also be seen as a special case of a more general result proven in prior related work that analyzed randomized set selection strategies to optimize submodular functions (Feige et al., 2011).

where $p_{t}$ is the internal distribution of the online learner used to construct list $L_{t}$. Note that an online learner is called no-regret if $R$ is sublinear in $T$.

We define a mixture distribution $\overline{p}$ over lists that constructs a list as follows: sample an index $t$ uniformly in $\{1,2,\dots,T\}$, then sample $m$ elements (with replacement) from $p_{t}$. Note that $F(\overline{p},m)=\frac{1}{T}\sum_{t=1}^{T}F(p_{t},m)$ and $F(\hat{p},m)\geq F(\overline{p},m)$. Thus it suffices to show that $F(\overline{p},m)$ has good guarantees. We show that in expectation $\overline{p}$ (and thus $\hat{p}$) constructs lists with performance guarantees close to the clairvoyant greedy algorithm:Additionally, if the distributions $p_{t}$ converge, then the last distribution $p_{T+1}$ must have performance arbitrarily close to $\overline{p}$ as $T\rightarrow\infty$. In particular, we can expect this to occur when the examples are randomly drawn from a fixed distribution that does not change over time.

Let $\alpha=\exp(-m/k)$ and $k^{\prime}=\min(m,k)$. For any $\delta\in(0,1)$, with probability $\geq 1-\delta$:

Theorem 1 provides a general approximation ratio to the best list of size $k$ when constructing a list of a different size $m$. For $m=k$, we obtain the typical $(1-1/e)$ approximation ratio (Guestrin & Krause, ). As $m$ increases, this provides approximation ratios that converge exponentially closer to 1.

Using weighted majority with the optimal learning rate guarantees with probability $\geq 1-\delta$:

Contextual List Optimization with Stationary Policies

We now consider the contextual setting where features of each state $x_{t}$ are observed before choosing the list. As mentioned, our goal here is to compete with the best list of policies $(\pi_{1},\pi_{2},\dots,\pi_{k})$ from a hypothesis class $\Pi$. Each of these policies are assumed to choose an item solely based on features of the state $x_{t}$.

We present an extension of SCP to the contextual setting (Algorithm 2). At each iteration, SCP constructs a list $L_{t}$ for the state $x_{t}$ (using its current policy or by sampling policies from its distribution over policies).

Analogous to the context-free setting, we define a loss function for the learner subroutine (Update). We represent the loss using weighted cost-sensitive classification examples $\{(v_{ti},c_{ti},w_{ti})\}_{i=1}^{m}$, where $v_{ti}$ denotes features of the state $x_{t}$ and list $L_{t,i-1}$, $w_{ti}=(1-1/k)^{m-i}$ is the weight associated to this example, and $c_{ti}$ is the cost vector specifying the cost of each item $s\in\mathcal{S}$

The loss incurred by any policy $\pi$ is defined by its loss on this set of cost-sensitive classification examples, i.e.

These new examples are then used to update the policy (or distribution over policies) using a no-regret algorithm (Update). This reduction effectively transforms the task of learning a policy for this submodular list optimization problem into a standard online cost-sensitive classification problem.This is similar to DAgger (Ross et al., 2011a, b; Ross & Bagnell, 2012) developed for sequential prediction problems like imitation learning. Our work can be seen as a specialization of DAgger for submodular list optimization, and ensures that we learn policies that pick good items under the lists they construct. Unlike prior work, our analysis leverages submodularity, leading to several modifications, and improved global optimality guarantees. Analogous to the context-free setting, we can also extend to partial feedback settings where $f$ is only partially measurable by using contextual bandit algorithms such as EXP4 (Auer et al., 2003) as the online learner (Update).Analogous to the context-free setting, partial information arises when $c_{ti}$ (4) is not measurable for every $s\in\mathcal{S}$.

However, achieving no-regret for infinite policy classes is in general not tractable. A more practical approach is to employ existing reductions of cost-sensitive classification problems to convex optimization problems, for which we can efficiently run no-regret convex optimization (e.g. gradient descent). These reductions effectively upper bound the cost-sensitive loss by a convex loss, and thus bound the original loss of the list prediction problem. We briefly describe two such reductions from (Beygelzimer et al., 2005):

We transform cost-sensitive classification into a regression problem of predicting the costs of each item $s\in\mathcal{S}$. Afterwards, the policy chooses the item with lowest predicted cost. We convert each weighted cost-sensitive example $(v,c,w)$ into $|\mathcal{S}|$ weighted regression examples.

For example, if we use least-squares linear regression, the weighted squared loss for a particular example $(v,c,w)$ and policy $h$ would be:

Reduction to Ranking

Another useful reduction transforms the problem into a ”ranking” problem that penalizes ranking an item $s$ above another better item $s^{\prime}$. In our experiments, we employ a weighted hinge loss, and so the penalty is proportional to the difference in cost of the misranked pair. For each cost-sensitive example $(v,c,w)$, we generate $\mathcal{|S|}(\mathcal{|S|}-1)/2$ ranking examples for every distinct pair of items $(s,s^{\prime})$, where we must predict the best item among $(s,s^{\prime})$ (potentially by a margin), with a weight of $w|c(s)-c(s^{\prime})|$.

For example, if we train a linear SVM (Joachims, 2005), we obtain a weighted hinge loss of the form:

where $\delta_{s,s^{\prime}}=c(s)-c(s^{\prime})$ and $h$ is the linear policy. At prediction time, we simply predict the item $s^{*}$ with highest score, $s^{*}=\operatorname*{argmax}_{s\in\mathcal{S}}h^{\top}v(s)$. This reduction proves advantageous whenever it is easier to predict pairwise rankings rather than the actual cost.

2 Theoretical Guarantees

For a deterministic online algorithm that picks the sequence of policies $\{\pi_{t}\}_{t=1}^{T}$, the regret is

For a randomized online learner, let $\pi_{t}$ be the distribution over policies at iteration $t$, with expected regret

We use a mixture distribution $\overline{\pi}$ over policies to construct a list as follows: sample an index $t$ uniformly in $\{1,2,\dots,T\}$, then sample $m$ policies from $\pi_{t}$ to construct the list. As before, we note that $F(\overline{\pi},m)=\frac{1}{T}\sum_{t=1}^{T}F(\pi_{t},m)$, and $F(\hat{\pi},m)\geq F(\overline{\pi},m)$. As such, we again focus on proving good guarantees for $F(\overline{\pi},m)$, as shown by the following theorem.

Let $\alpha=\exp(-m/k)$, $k^{\prime}=\min(m,k)$ and pick any $\delta\in(0,1)$. After $T$ iterations, for deterministic online algorithms, we have that with probability at least $1-\delta$:

Similarly, for randomized online algorithms, with probability at least $1-\delta$:

Thus, as in the previous section, a no-regret algorithm must achieve $F(\overline{\pi},m)\geq(1-\alpha)F(L^{*}_{\pi,k})$ with high probability as $T\rightarrow\infty$. This matches similar guarantees provided in (Dey et al., 2012). Despite having similar guarantees, we intuitively expect SCP to outperform (Dey et al., 2012) in practice because SCP can use all data to train a single predictor, instead of being split to train $k$ separate ones. We empirically verify this intuition in Section 6.

When using surrogate convex loss functions (such as regression or ranking loss), we provide a general result that applies if the online learner uses any convex upper bound of the cost-sensitive loss. An extra penalty term is introduced that relates the gap between the convex upper bound and the original cost-sensitive loss:

This result implies that using a good surrogate convex loss for no-regret convex optimization will lead to a policy that has a good performance relative to the optimal list of policies. Note that the gap $\mathcal{G}$ often may be small or non-existent. For instance, in the case of the reduction to regression or ranking, $\mathcal{G}=0$ in realizable settings where there exists a “perfect” predictor in the class. Similarly, in cases where the problem is near-realizable we would expect $\mathcal{G}$ to be small.We conjecture that this gap term $\mathcal{G}$ is not specific to our particular scenario, but rather is (implicitly) always present whenever one attempts to optimize classification accuracy via surrogate convex optimization.

Experimental Results

We applied SCP to a manipulation planning task for a $7$ degree-of-freedom robot manipulator. The goal is to predict a set of initial trajectories so as to maximize the chance that one of them leads to a collision-free trajectory. We use local trajectory optimization techniques such as CHOMP (Ratliff et al., 2009), which have proven effective in quickly finding collision-free trajectories using local perturbations of an initial trajectory. Note that selecting a diverse set of initial trajectories is important since local techniques such as CHOMP often get stuck in local optima.I.e., similar or redundant inital trajectories will lead to the same local optima.

We use the dataset from (Dey et al., 2012). It consists of $310$ training and $212$ test environments of random obstacle configurations around a target object, and $30$ initial seed trajectories. In each environment, each seed trajectory has $17$ features describing the spatial properties of the trajectory relative to obstacles.In addition to the base features, we add features of the current list w.r.t. each initial trajectory. We use the per feature minimum absolute distance and average absolute value of the distance to the features of initial trajectories in the list. We also use a bias feature always set to $1$, and an indicator feature which is $1$ when selecting the element in the first position, otherwise.

Following (Dey et al., 2012), we employ a reduction of cost-sensitive classification to regression as explained in Section 5.1. We compare SCP to ConSeqOpt (Dey et al., 2012) (which learns $k$ separate predictors), and Regression (regress success rate from features to sort seeds; this accounts for relevance but not diversity).

Figure 1 (left) shows the failure probability over the test environments versus the number of training environments. ConSeqOpt employs a reduction to $k$ classifiers. As a consequence, ConSeqOpt faces data starvation issues for small training sizes, as there is little data available for training predictors lower in the list.When a successful seed is found, benefits at later positions are 0. This effectively discards training environments for training classifiers lower in the list in ConSeqOpt. In contrast, SCP has no data starvation issue and outperforms both ConSeqOpt and Regression.

2 Personalized News Recommendation

We built a stochastic user simulation based on $75$ user preferences derived from a user study in (Yue & Guestrin, 2011). Using this simulation as a training oracle, our goal is to learn to recommend articles to any user (depending on their contextual features) to minimize the failure case where the user does not like any of the recommendations.Also known as abandonment (Radlinski et al., 2008).

Articles are represented by features, and user preferences by linear weights. We derived user contexts by soft-clustering users into groups, and using corrupted group memberships as contexts.

We perform five-fold cross validation. In each fold, we train SCP and ConSeqOpt on $40$ users’ preferences, use $20$ users for validation, and then test on the held-out $15$ users. Training, validation and testing are all performed via simulation. Figure 1 (middle) shows the results, where we see the recommendations made by SCP achieves significantly lower failure rate as the number of recommendations is increased from $1$ to $5$.

3 Document Summarization

In the extractive multi-document summarization task, the goal is to extract sentences (with character budget $B$) to maximize coverage of human-annotated summaries. Following the experimental setup from (Lin & Bilmes, 2010) and (Kulesza & Taskar, 2011), we use data from the Document Understanding Conference (DUC) 2003 and 2004 (Task 2) (Dang, 2005). Each training or test instance corresponds to a cluster of documents, and contains approximately $10$ documents belonging to the same topic and four human reference summaries. We train on the 2003 data (30 clusters) and test on the 2004 data (50 clusters). The budget is $B=665$ bytes, including spaces.

We use the ROUGE (Lin, 2004) unigram statistics (ROUGE-1R, ROUGE-1P, ROUGE-1F) for performance evaluation. Our method directly attempts to optimize the ROUGE-1R objective with respect to the reference summaries, which can be easily shown to be monotone submodular (Lin & Bilmes, 2011).

We aim to predict sentences that are both short and informative. Therefore we maximize the normalized marginal benefit,

where $l(s)$ is the length of the sentence $s$.This results in a knapsack constrained optimization problem. We expect our approach to perform well in this setting, but defer a formal analysis for future work. We use a reduction to ranking as described in Section 5.1 using (5). While not performance-optimized, our approach takes less than $15$ minutes to train.

Following (Kulesza & Taskar, 2011), we consider features $f_{i}$ for each sentence consisting of quality features $q_{i}$ and similarity features $\phi_{i}$ ($f_{i}=[q_{i}^{T},\phi_{i}^{T}]^{T}$). The quality features, attempt to capture the representativeness for a single sentence. Similarity features $q_{i}$ for sentence $s_{i}$ as we construct the list $L_{t}$ measure a notion of distance of a proposed sentence to sentences already included in the set. A variety of similarity features were considered, with the simplest being average squared distance of tf-idf vectors. Performance was very stable across different features. The experiments presented use three types: 1) following the idea in (Kulesza & Taskar, 2011) of similarity as a volume metric, we compute the squared volume of the parallelopiped spanned by the TF-IDF vectors of sentences in the set $L_{t,k}\cup{s_{i}}$; 2) the product between $\mbox{det}(G_{L_{t,k}\cup{s_{i}}})$ and the quality features; 3) the minimum absolute distance of quality features between $s_{i}$ and each element in $L_{t,k}$.

Table 1 shows the performance (Rouge unigram statistics) comparing SCP with existing algorithms. We observe that SCP outperforms existing state-of-the-art approaches, which we denote SubMod (Lin & Bilmes, 2010) and DPP (Kulesza & Taskar, 2011). “Greedy (Oracle)” corresponds to the clairvoyant oracle that directly optimizes the test Rouge score and thus serves as an upper bound on this class of techniques. Figure 1 (right) plots Rouge-1R performance as a function of the size of training data, suggesting SCP’s superior data-efficiency compared to ConSeqOpt.

Acknowledgements

This research was supported in part by NSF NRI Purposeful Prediction project and ONR MURIs Decentralized Reasoning in Reduced Information Spaces and Provably Stable Vision-Based Control. Yisong Yue was also supported in part by ONR (PECASE) N000141010672 and ONR Young Investigator Program N00014-08-1-0752. We gratefully thank Martial Hebert for valuable discussions and support.

Appendix A Proofs of Theoretical Results

This appendix contains the proofs of the various theoretical results presented in this paper.

We begin by proving a number of lemmas about monotone submodular functions, which will be useful to prove our main results.

Let $\mathcal{S}$ be a set and $f$ be a monotone submodular function defined on list of items from $\mathcal{S}$. For any lists $A,B$, we have that:

for $U(B)$ the uniform distribution on items in $B$.

For any list $A$ and $B$, let $B_{i}$ denote the list of the first $i$ items in $B$, and $b_{i}$ the $i^{th}$ item in $B$. We have that:

where the inequality follows from the submodularity property of $f$. ∎

and for $\alpha=\exp(-|A|/|B|)$ (i.e. $|A|=|B|\log(1/\alpha)$):

Now let $\Delta_{j}=f(B)-f(A_{j})$. By the above we have that

Rearranging terms, this implies that $\Delta_{j+1}\leq(1-1/|B|)\Delta_{j}+\epsilon_{j+1}$. Recursively expanding this recurrence from $\Delta_{|A|}$, we obtain:

Using the definition of $\Delta_{|A|}$ and rearranging terms, we obtain $f(A)\geq(1-(1-1/|B|)^{|A|})f(B)-\sum_{i=1}^{|A|}(1-1/|B|)^{|A|-i}\epsilon_{i}$. This proves the first statement of the theorem. The following two statements follow from the observations that $(1-1/|B|)^{|A|}=\exp(|A|\log(1-1/|B|))\leq\exp(-|A|/|B|)=\alpha$. Hence $(1-(1-1/|B|)^{|A|})f(B)\geq(1-\alpha)f(B)$. When $|A|=|B|$, $\alpha=1/e$ and this proves the special case where $|A|=|B|$. ∎

For the greedy list construction strategy, the $\epsilon_{j}$ in the last lemma are always $\leq 0$, such that Lemma 2 implies that if we construct a list of size $k$ with greedy, it must achieve at least 63% of the value of the optimal list of size $k$, but also that it must achieve at least 95% of the value of the optimal list of size $\lfloor k/3\rfloor$, and at least 99.9% of the value of the optimal list of size $\lfloor k/7\rfloor$.

A more surprising fact that follows from the last lemma is that constructing a list stochastically, by sampling items from a particular fixed distribution, can provide the same guarantee as greedy:

Let $\mathcal{S}$ be a set, and $f$ a monotone submodular function defined on lists of items in $\mathcal{S}$. Let $B$ be any list of items from $\mathcal{S}$ and $U(B)$ the uniform distribution on elements in $B$. Suppose we construct the list $A$ by sampling $k$ items randomly from $U(B)$ (with replacement). Denote $A_{j}$ the list obtained after $j$ samples, and $P_{j}$ the distribution over lists obtained after $j$ samples. Then:

In particular, for $\alpha=\exp(-k/|B|)$:

Rearranging terms, this implies that $\Delta_{j+1}\leq(1-1/|B|)\Delta_{j}$. Recursively expanding this recurrence from $\Delta_{k}$, we obtain:

Using the definition of $\Delta_{k}$ and rearranging terms we obtain $E_{A\sim P_{k}}[f(A)]\geq(1-(1-1/|B|)^{k})f(B)$. The second statement follows again from the fact that $(1-(1-1/|B|)^{k})f(B)\geq(1-\alpha)f(B)$ ∎

There exists a distribution that when sampled $k$ times to construct a list, achieves an approximation ratio of $(1-1/e)$ of the optimal list of size $k$ in expectation. In particular, if $A^{*}$ is an optimal list of size $k$, sampling $k$ times from $U(A^{*})$ achieves this approximation ratio. Additionally, for any $\alpha\in(0,1]$, sampling $\lceil k\log(1/\alpha)\rceil$ times must construct a list that achieves an approximation ratio of $(1-\alpha)$ in expectation.

Follows from the last lemma using $B=A^{*}$. ∎

This surprising result can also be seen as a special case of a more general result proven in prior related work that analyzed randomized set selection strategies to optimize submodular functions (lemma 2.2 in (Feige et al., 2011)).

A.2 Proofs of Main Results

We refer the reader to the notation defined in section LABEL:sec:background and 5 for the definitions of the various terms used.

Let $\alpha=\exp(-m/k)$ and $k^{\prime}=\min(m,k)$. After $T$ iterations, for any $\delta,\delta^{\prime}\in(0,1)$, we have that with probability at least $1-\delta$:

and similarly, with probability at least $1-\delta-\delta^{\prime}$:

Let $w_{i}=(1-1/k)^{m-i}$. From Lemma 2, we have:

Hence combining with the previous result proves the first part of the theorem.

Using this additional fact, and combining with previous results we must have that with probability at least $1-\delta-\delta^{\prime}$:

We now show that the expected regret must grow with $\sqrt{k^{\prime}}$ and not $k^{\prime}$, hen using Weighted Majority with the optimal learning rate (or with the doubling trick).

References