Stochastic Submodular Probing with State-Dependent Costs

Shaojie Tang University of Texas at Dallas

In this paper, we study a new stochastic submodular maximization problem with
state-dependent costs and rejections. The input of our problem is a budget
constraint $B$, and a set of items whose states (i.e., the marginal
contribution and the cost of an item) are drawn from a known probability
distribution. The only way to know the realized state of an item is to probe
the item. We allow rejections, i.e., after probing an item and knowing its
actual state, we must decide immediately and irrevocably whether to add that
item to our solution or not. Our objective is to maximize the objective
function subject to a budget constraint on the total cost of the selected
items. We present a constant approximate solution to this problem. We show
that our solution is also applied to an online setting.

##  1 Introduction

In this paper, we study a new stochastic submodular maximization problem. We
introduce the state-dependent item costs and rejections into the classic
stochastic submodular maximization problem. The input of our problem is a
budget constraint $B$, and a set of items whose states are drawn from a known
probability distribution. The marginal contribution and the cost of an item is
dependent on its actual state. We must probe an item in order to reveal its
actual state. Our model allows rejections, i.e., after probing an item and
knowing its actual state, we must decide immediately and irrevocably whether
to add that item to our solution or not. Our objective is to select a group of
items that maximize the objective function subject to a budget constraint on
the total cost of the selected items. We present a constant approximate
solution to this problem. Perhaps surprisingly, we show that our algorithm can
also be applied to an online setting described as follows: Suppose there is a
sequence of items arriving with different states, on the arrival of an item,
we must decide immediately and irrevocably whether to select it or not subject
to a budget constraint, and the objective is to maximize the objective
function. For this online decision problem, our algorithm achieves the same
approximation ratio as obtained under the offline setting.

_Related works._ Stochastic submodular maximization has been extensively
studied recently (Golovin and Krause 2011, Chen and Krause 2013, Fujii and
Kashima 2016). However, most of existing works assume that the cost of an item
is deterministic and pre-known. We relax this assumption by introducing the
state-dependent item costs to our setting. In particular, we assume that the
actual cost of an item is decided by its realized state. We must probe an item
in order to know its state. When considering linear objective function, our
problem reduces to the stochastic knapsack problem with rejections (Gupta et
al. 2011). Gupta et al. (2011) gave a constant approximate algorithm for this
problem. Recently, (Fukunaga et al. 2019) studied the stochastic submodular
maximization problem with performance-dependent costs, however, their model
does not allow rejections. Therefore, our problem does not coincide with their
work. Moreover, it is not immediately clear how to extend their algorithm to
online setting. Our work is also closely related to submodular probing problem
(Adamczyk et al. 2016), however, they assume each item has only two states,
i.e., active or inactive, we relax this assumption by allowing each item to
have multiple states and the item cost is dependent on its state. Furthermore,
their model does not allow rejections, i.e., one can not reject an active item
after it has been probed.

##  2 Preliminaries and Problem Formulation

### Lattice-submodular functions

Let $[I]=\\{1,2,\cdots,I\\}$ be a set of items and $[S]=\\{1,2,\cdots,S\\}$ be
a set of states. Given two vectors $u,v\in[S]^{[I]}$, $u\leq v$ means that
$u(i)\leq v(i)$ for all $i\in[I]$. Define $(u\vee v)(i)=\max\\{u(i),v(i)\\}$
and $(u\wedge v)(i)=\min\\{u(i),v(i)\\}$. For $i\in[I]$, define
$\mathbf{1}_{i}$ as the vector that has a $1$ in the $i$-th coordinate and $0$
in all other coordinates. A function $f:[S]^{[I]}\rightarrow\mathbb{R}_{+}$ is
called _monotone_ if $f(u)\leq f(v)$ holds for any $u,v\in[S]^{[I]}$ such that
$u\leq v$, and $f$ is called _lattice submodular_ if $f(u\vee
s\mathbf{1}_{i})-f(u)\geq f(v\vee s\mathbf{1}_{i})-f(v)$ holding for any
$u,v\in[S]^{[I]}$, $s\in[S]$, $i\in[I]$.

### Items and States

We let vector $\phi\in[S]^{[I]}$ denote the states of all items. For each item
$i\in[I]$, let $\phi(i)\in[S]$ denote the state of $i$. We assume there is a
known prior probability distribution $\mathcal{D}_{i}$ over realizations for
each item $i$, i.e., $\mathcal{D}_{i}=\\{\Pr[\phi(i)=s]:s\in[S]\\}$. The
states of all items are decided independently at random, i.e., $\phi$ is drawn
randomly from the product distribution $\mathcal{D}=\prod_{i\in
I}\mathcal{D}_{e}$. We use $c_{i}(s)$ to denote the cost of an item $i$ when
its state is $s$.

###### Assumption 1

We further assume that $c_{i}(s)\geq c_{i}(s^{\prime})$ for any $i\in I$ and
$s,s^{\prime}\in[S]$ such that $s\geq s^{\prime}$, i.e., the cost of an item
is larger if it is in a “better” state.

For ease of analysis, we next introduce a set function $h$ over a new ground
set $[I]\times[S]$: consider an arbitrary set of item-state pairs
$U\subseteq[I]\times[S]$, define $h(U)=f(u)$ where $u(i)=0$ if $(i,s)\notin
U$, otherwise $u(i)=\max\\{s\mid(i,s)\in U\\}$. It is easy to verify that if
$f$ is monotone and lattice-submodular, then $h$ is monotone and submodular.
Given an $I\times S$ matrix $\mathbf{x}$, we define the multilinear extension
$H$ of $h$ as:

$H(\mathbf{x})=\sum_{U\subseteq[I]\times[S]}\prod_{(i,s)\in
U}x_{is}\prod_{(i,s)\notin U}(1-x_{is})$

The value $H(\mathbf{x})$ is the expected value of $h(R)$ where $R$ is a
random set obtained by picking each element $(i,s)$ independently with
probability $x_{is}$.

### Adaptive Policy and Problem Formulation

The input of our problem is a budget constraint $B$, and a set of items. The
only way to know the state of an item is to probe the item. We allow
rejections, i.e., after probing an item and knowing its state, we must decide
immediately and irrevocably whether to pick that item or not. We model the
adaptive strategy of probing/picking items through a policy $\pi$. Formally, a
policy $\pi$ is a function that specifies which item to probe/pick next based
on the observations made so far. Consider an arbitrary policy $\pi$, assume
that conditioned on $\phi=\zeta$, $\pi$ picks a set of items (and
corresponding states) $G(\pi,\zeta)\subseteq[I]\times[S]$111For simplicity, we
only consider deterministic policy. However, all results can be easily
extended to random policies.. The expected utility of $\pi$ is
$f(\pi)=\sum_{\zeta}\Pr[\phi=\zeta]h(G(\pi,\zeta))$. We say a policy $\pi$ is
_feasible_ if for any $\zeta$, $\sum_{(i,s)\in G(\pi,\zeta)}c_{i}(s)\leq B$.
Our goal is to identify the best feasible policy that maximizes its expected
utility.

$\max_{\pi}f(\pi)\mbox{ subject to $\pi$ is feasible.}$

##  3 Algorithm Design

We next describe our algorithm and analyze its performance. Our algorithm is
based on the contention resolution scheme (Chekuri et al. 2014), which is
proposed in the context of submodular maximization with deterministic item
cost. We extend their design by considering state-dependent item cost and
rejections. Our algorithm, called StoCan, is composed of two phases.

The first phase is done offline, we use the continuous greedy algorithm
(Algorithm 1) to compute a fractional solution over a down monotone polytope.
The framework of continuous greedy algorithm is first proposed by Calinescu et
al. (2011) in the context of submodular maximization subject to a matroid
constraint. In particular, Algorithm 1 maintains an $I\times S$ matrix
$\mathbf{y}(t)$, starting with $\mathbf{y}(0)=\mathbf{0}$. Let $R(t)$ contain
each $(i,s)$ independently with probability $y_{is}(t)$. For each
$(i,s)\in[I]\times[S]$, estimate its weight $\omega_{is}$ as follows

$\omega_{is}=\mathbb{E}[h(R(t)\cup\\{(i,s)\\})]-\mathbb{E}[h(R(t))]$

Solve the following linear programming problem LP and obtain the optimal
solution $\mathbf{x}^{LP}$, then update the fractional solution at round $t$
as $\forall(i,s)\in[I]\times[S],y_{is}(t+\delta)=y_{is}(t)+x^{LP}_{is}$.

LP: _Maximize $\sum_{(i,s)\in[I]\times[S]}\omega_{is}x_{is}$_
subject to: $\begin{cases}\forall(i,s)\in[I]\times[S]:x_{is}\leq p_{i}(s)\\\
\sum_{(i,s)\in[I]\times[S]}x_{is}c_{i}(s)\leq B\\\ \end{cases}$

After $1/\delta$ rounds, $\mathbf{y}(1/\delta)$ is returned as the final
solution. In the rest of this paper, let $\mathbf{y}$ denote
$\mathbf{y}(1/\delta)$ for short.

In the second phase, we implement a simple randomized policy based on
$\mathbf{y}$. Our policy randomly picks a policy from $\pi^{small}$ (Algorithm
2) and $\pi^{large}$ (Algorithm 3) with equal probability to execute. If
$\pi^{small}$ is picked, we discard all _large_ items whose cost is larger
than $B/2$ (Line 5 in Algorithm 2), and add the rest of items according to the
corresponding distribution in (scaled) $\mathbf{y}$ (Line 8 in Algorithm 2) .
If Algorithm $\pi^{large}$ is picked, we discard all _small_ items whose cost
is no larger than $B/2$ (Line 5 in Algorithm 2), and add the rest of items
according to the corresponding distribution in (scaled) $\mathbf{y}$ (Line 8
in Algorithm 3).

Algorithm 1 Continuous Greedy

1: Set $\delta=1/(IS)^{2},t=0,f(\emptyset)=0,\mathbf{y}(0)=\mathbf{0}$.

2: while $t<1$ do

3: Let $R(t)$ contain each $(i,s)$ independently with probability $y_{is}(t)$.

4: For each $(i,s)\in[I]\times[S]$, estimate
$\omega_{is}=\mathbb{E}[h(R(t)\cup\\{(i,s)\\})]-\mathbb{E}[h(R(t))]$;

5: Solve the following linear programming problem and obtain the optimal
solution $\mathbf{x}^{LP}$

6: LP: _Maximize $\sum_{(i,s)\in[I]\times[S]}\omega_{is}x_{is}$_ subject to:
$\begin{cases}\forall(i,s)\in[I]\times[S]:x_{is}\leq p_{i}(s)\\\
\sum_{(i,s)\in[I]\times[S]}x_{is}c_{i}(s)\leq B\\\ \end{cases}$

7: Let $y_{is}(t+\delta)=y_{is}(t)+x^{LP}_{is}$;

8: Increment $t=t+\delta$;

9: return $\mathbf{y}(1/\delta)$;

Algorithm 2 $\pi^{small}$

1: Set $G=\emptyset$, $i=1$.

2: while $i\leq n$ do

3: probe item $i$ and observe its state $s$

4: if $c_{i}(s)>B/2$ then

5: $i=i+1$; {discard all large items}

6: else

7: if the remaining budget is no less than $c_{i}(s)$ then

8: add $(i,s)$ to $G$ with probability $y_{is}/4p_{i}(s)$;

9: $i=i+1$;

10: return $G$;

Algorithm 3 $\pi^{large}$

1: Set $G=\emptyset$, $i=1$.

2: while $i\leq n$ do

3: probe item $i$ and observe its state $s$

4: if $c_{i}(s)\leq B/2$ then

5: $i=i+1$; {discard all small items}

6: else

7: if the remaining budget is no less than $c_{i}(s)$ then

8: add $(i,s)$ to $G$ with probability $y_{is}/4p_{i}(s)$;

9: $i=i+1$;

10: return $G$;

We next provide the main theorem of this paper.

###### Theorem 1

Let $\pi^{*}$ denote the optimal policy, the expected utility achieved by
StoCan is at lest $\frac{1-1/e}{16}f(\pi^{*})$.

Theorem 1 follows from Lemma 1, 2, 3, and 4, which will be proved later. Based
on Lemma 3 and 4, we have
$f(\pi^{small})+f(\pi^{large})\geq\frac{H(\mathbf{\underline{y}})+H(\mathbf{\overline{y}})}{8}$.
Together with Lemma 2, we have
$f(\pi^{small})+f(\pi^{large})\geq\frac{H(\mathbf{y})}{8}$. Because
$H(\mathbf{y})\geq(1-1/e)f(\pi^{*})$ as proved in Lemma 1, we have
$f(\pi^{small})+f(\pi^{large})\geq\frac{1-1/e}{8}f(\pi^{*})$. Since StoCan
randomly picks one policy from $\pi^{small}$ and $\pi^{large}$ to execute, the
expected utility of StoCan is at least $\frac{1-1/e}{16}f(\pi^{*})$.

Next we focus on proving the above four lemmas.

###### Lemma 1

Let $\mathbf{y}$ denote the fractional solution returned from Algorithm 1,
$H(\mathbf{y})\geq(1-1/e)f(\pi^{*})$.

###### Proof.

Given $\pi^{*}$, for each item-state pair $(i,s)$, let $y^{*}_{is}$ denote the
probability that $\phi(i)=s$ and $i$ is picked by $\pi^{*}$. Clearly,
$\forall(i,s)\in[I]\times[S]:y^{*}_{is}\leq p_{i}(s)$. Moreover, let
$\mathbf{e}_{i,s}$ denote the event that $\phi(i)=s$ and $i$ is picked by
$\pi^{*}$, we have $\sum_{(i,s)\in[I]\times[S]}\mathbf{e}_{i,s}c_{i}(s)\leq
B$, Thus,
$\mathbb{E}[\sum_{(i,s)\in[I]\times[S]}\mathbf{e}_{i,s}c_{i}(s)]=\sum_{(i,s)\in[I]\times[S]}\mathbb{E}[\mathbf{e}_{i,s}]c_{i}(s)=\sum_{(i,s)\in[I]\times[S]}y^{*}_{is}c_{i}(s)\leq
B$ where the expectation is taken over $\mathcal{D}$. It follows that
$\mathbf{y}^{*}$ is a feasible solution to LP. Define $\mathbf{1}_{is}$ as the
matrix that has a $1$ in the $(i,s)$-th entry and $0$ in all other entries.
Let $h_{V}((i,s))=h(V\cup\\{(i,s)\\})-h(V)$ and
$H_{\mathbf{y}(t)}((i,s))=H(\mathbf{y}(t)\vee\mathbf{1}_{is})-H(\mathbf{y}(t))$
denote the marginal utility of $(i,s)$ with respect to $V$ and
$\mathbf{y}(t)$, respectively. We next bound the increment of
$H(\mathbf{y}(t))$ during one step of Algorithm 1.

$\displaystyle f(\pi^{*})$ $\displaystyle\leq$
$\displaystyle\min_{V\subseteq[I]\times[S]}(h(V)+\sum_{(i,s)\in[I]\times[S]}y^{*}_{is}h_{V}((i,s)))$
(1) $\displaystyle\leq$ $\displaystyle
H(\mathbf{y}(t))+\sum_{(i,s)\in[I]\times[S]}y^{*}_{is}H_{\mathbf{y}(t)}((i,s))$
(2) $\displaystyle\leq$ $\displaystyle
H(\mathbf{y}(t))+\sum_{(i,s)\in[I]\times[S]}x^{LP}_{is}H_{\mathbf{y}(t)}((i,s))$
(3)

The first inequality is proved in (Calinescu et al. 2011). The third
inequality is due to $\mathbf{x}^{LP}$ is an optimal solution to LP. Then this
lemma follows from the standard analysis on submodular maximization. ∎

Given the fractional solution $\mathbf{y}$ returned from Algorithm 1, we next
introduce two new fractional solutions $\overline{\mathbf{y}}$ and
$\mathbf{\underline{y}}$. Define $\overline{y}_{is}=y_{is}$ if $c_{i}(s)\leq
B/2$, otherwise, $\overline{y}_{is}=0$. Define $\underline{y}_{is}=y_{is}$ if
$c_{i}(s)>B/2$, otherwise, $\underline{y}_{is}=0$. Due to the submodularity of
$h$, we have the following lemma.

###### Lemma 2

$H(\mathbf{\underline{y}})+H(\mathbf{\overline{y}})\geq H(\mathbf{y})$

We next bound the expected utility achieved by $\pi^{small}$.

###### Lemma 3

$f(\pi^{small})\geq H(\mathbf{\underline{y}})/8$

###### Proof.

Consider a modified version of $\pi^{small}$ by removing Line 8, i.e., after
probing an item $i$ and observing its state $s$, if $c_{i}(s)\leq B/2$, select
$i$ with probability $y_{is}/4p_{i}(s)$ regardless of the remaining budget,
otherwise, discard $i$. Denote by $G^{\prime}$ the returned solution from the
modified $\pi^{small}$. It is easy to verify that for each $(i,s)$ with
$c_{i}(s)\leq B/2$, the probability that $(i,s)$ is included in $G^{\prime}$
is $p_{i}(s)y_{is}/4p_{i}(s)=y_{is}/4$. Notice that since each item $i$ can
only have one state, the event that $(i,s)$ is included in $G^{\prime}$ is not
independent from the event that $(i,s^{\prime})$ is included in $G^{\prime}$
where $s^{\prime}$ is a different state from $s$ and $c_{i}(s^{\prime})\leq
B/2$. However, as shown in Lemma 3.7 in (Calinescu et al. 2011), this
dependency does not degrade the expected utility, i.e.,
$\mathbb{E}[h(G^{\prime})]\geq H(\mathbf{\underline{y}}/4)$. Due to $H$ is
concave along any nonnegative direction (Calinescu et al. 2011), we have
$H(\mathbf{\underline{y}}/4)\geq H(\mathbf{\underline{y}})/4$. It follows that

$\mathbb{E}[h(G^{\prime})]\geq H(\mathbf{\underline{y}}/4)\geq
H(\mathbf{\underline{y}})/4$ (4)

Next we focus on proving that

$f(\pi^{small})=\mathbb{E}[h(G)]\geq\mathbb{E}[h(G^{\prime})]/2$ (5)

This lemma follows from (4) and (5).

Recall that if the remaining budget is no less than $c_{i}(s)$, $\pi^{small}$
adds $(i,s)$ to $G$. Because $\mathbf{y}$ is a feasible solution to LP,
$\mathbf{\underline{y}}$ is also a feasible solution to LP, it implies that
$\sum_{(i,s)\in[I]\times[S]}\underline{y}_{is}c_{i}(s)/4\leq B/4$. According
to Markov’s inequality, the probability that the remaining budget is less than
$B/2$ is at most $1/2$. Because we assume $c_{i}(s)\leq B/2$, the probability
that the remaining budget is less than $c_{i}(s)$ is at most $1/2$. Thus, the
probability that $(i,s)$ is included in $G$ is at least $y_{is}/8$.

Let $G[i]$ (resp. $G^{\prime}[i]$) denote all item-state pairs in $G$ (resp.
$G^{\prime}$) that involve items in $[i]$, i.e., $G[i]=G\cap\\{(j,s)\mid
j\in[i],s\in[S]\\}$ and $G^{\prime}[i]=G^{\prime}\cap\\{(j,s)\mid
j\in[i],s\in[S]\\}$. We next prove that for any $i\in[I]$,

$\mathbb{E}[h(G[i])-h(G[i-1])]\geq\frac{1}{2}\mathbb{E}[h(G^{\prime}[i])-h(G^{\prime}[i-1])]$
(6)

Notice that (6) implies (5) due to
$\mathbb{E}[h(G)]=h(\emptyset)+\sum_{i=1}^{n}\mathbb{E}[h(G[i])-h(G[i-1])]\geq
f(\emptyset)+\sum_{i=1}^{n}\frac{1}{2}\mathbb{E}[h(G^{\prime}[i])-h(G^{\prime}[i-1])]=\mathbb{E}[h(G^{\prime})]/2$.

We first give an lower bound on $\mathbb{E}[h(G[i])-h(G[i-1])]$. Let
$\mathbf{e}_{(i,s)\in G^{\prime}}$ denote the event that $(i,s)$ is included
in $G^{\prime}$ and $\mathbf{e}_{(i,s)\in G}$ denote the event that $(i,s)$ is
included in $G$.

$\displaystyle\mathbb{E}[h(G[i])-h(G[i-1])]$
$\displaystyle=\sum_{(i,s)\in[I]\times[S]}\mathbb{E}[\mathbf{e}_{(i,s)\in
G}(h(G[i-1]\cup(i,s))-h(G[i-1]))]$
$\displaystyle\geq\sum_{(i,s)\in[I]\times[S]}\mathbb{E}[\mathbf{e}_{(i,s)\in
G}(h(G^{\prime}[i-1]\cup(i,s))-h(G^{\prime}[i-1]))]$
$\displaystyle\geq\sum_{(i,s)\in[I]\times[S]}\mathbb{E}[\mathbf{e}_{(i,s)\in
G}]\mathbb{E}[h(G^{\prime}[i-1]\cup(i,s))-h(G^{\prime}[i-1])\mid(i,s)\in
G^{\prime}]$
$\displaystyle\geq\sum_{(i,s)\in[I]\times[S]}\frac{y_{is}}{8}\mathbb{E}[h(G^{\prime}[i-1]\cup(i,s))-h(G^{\prime}[i-1])\mid(i,s)\in
G^{\prime}]$

The first inequality is due the submodularity of $f$. The second inequality is
due to the assumption that $c_{i}(s)\geq c_{i}(s^{\prime})$ for any $i\in I$
and $s,s^{\prime}\in[S]$ such that $s\leq s^{\prime}$, and KFG inequality.

We next given an upper bound on
$\mathbb{E}[h(G^{\prime}[i])-h(G^{\prime}[i-1])$.

$\displaystyle\mathbb{E}[h(G^{\prime}[i])-h(G^{\prime}[i-1])]$
$\displaystyle=\sum_{(i,s)\in[I]\times[S]}\mathbb{E}[\mathbf{e}_{(i,s)\in
G}(h(G^{\prime}[i-1]\cup(i,s))-h(G^{\prime}[i-1]))]$
$\displaystyle=\sum_{(i,s)\in[I]\times[S]}\frac{y_{is}}{4}\mathbb{E}[h(G^{\prime}[i-1]\cup(i,s))-h(G^{\prime}[i-1])\mid(i,s)\in
G^{\prime}]$

It follows that
$\mathbb{E}[h(G[i])-h(G[i-1])]\geq\frac{1}{2}\mathbb{E}[h(G^{\prime}[i])-h(G^{\prime}[i-1])]$.
∎

Now consider the second option $\pi^{large}$. In the following lemma, we prove
that the expected utility achieved by $\pi^{large}$ is at least
$H(\mathbf{\overline{y}})/8$.

###### Lemma 4

$f(\pi^{large})\geq H(\mathbf{\overline{y}})/8$.

###### Proof.

Because $\mathbf{y}$ is a feasible solution to LP, $\mathbf{\overline{y}}$ is
also a feasible solution to LP, it implies that
$\sum_{(i,s)\in[I]\times[S]}\overline{y}_{is}c_{i}(s)/4\leq B/4$. Since we
only consider those $(i,s)$ whose cost is larger than $B/2$, the probability
that $G=\emptyset$ is at least $1/2$. Consider any $(i,s)$, conditioned on
$G[i-1]=\emptyset$, the probability that $(i,s)$ is included in $G$ is at
least $\overline{y}_{is}/4$. Thus, the probability that $(i,s)$ is included in
$G$ is at least $\overline{y}_{is}/8$. Recall that $\pi^{large}$ only picks
large items, $G$ contains at most one item (and its state) due to budget
constraint. Thus, the expected utility of $\pi^{large}$ is at least
$f(\pi^{large})\geq\sum_{(i,s)\in[I]\times[S]}\frac{\overline{y}_{is}h((i,s))}{8}$.
Due to the submodularity of $h$ and Lemma 3.7 in (Calinescu et al. 2011), we
have $\sum_{(i,s)\in[I]\times[S]}\overline{y}_{is}h((i,s))/8\geq
H(\mathbf{\overline{y}}/8)$. Since $H$ is concave along any nonnegative
direction (Calinescu et al. 2011), we have $H(\mathbf{\overline{y}}/8)\geq
H(\mathbf{\overline{y}})/8$, thus $f(\pi^{large})\geq
H(\mathbf{\overline{y}})/8$. ∎

##  4 Discussion on Online Setting

One nice feature about StoCan is that the implementation of $\pi^{small}$ and
$\pi^{large}$ does not require any specific order of items. Therefore, StoCan
can also be applied to an online setting described as follows: Suppose there
is a sequence of items arriving with different states, on the arrival of an
item, we observe its state and decide immediately and irrevocably whether to
select it or not subject to a budget constraint. Similar to the offline
setting, StoCan first computes $\mathbf{y}$ using Algorithm 1 in advance, then
randomly picks one policy from $\pi^{small}$ and $\pi^{large}$ to execute.
Notice that the online version of $\pi^{small}$ and $\pi^{large}$ probes the
items in order of their arrival. It is easy to verify that this does not
affect the performance analysis of StoCan, i.e., our analysis does not rely on
any specific order of items, thus StoCan achieves the same approximation ratio
as obtained under the offline setting.

##  5 Conclusion

In this paper, we study the stochastic submodular maximization problem with
state-dependent costs and rejections. We present a constant approximate
solution to this problem. We show that our solution is also applied to an
online setting.

## References

  * Adamczyk et al. (2016) Adamczyk, Marek, Maxim Sviridenko, Justin Ward. 2016.  Submodular stochastic probing on matroids.  Mathematics of Operations Research 41(3) 1022–1038.
  * Calinescu et al. (2011) Calinescu, Gruia, Chandra Chekuri, Martin Pál, Jan Vondrák. 2011.  Maximizing a monotone submodular function subject to a matroid constraint.  SIAM Journal on Computing 40(6) 1740–1766.
  * Chekuri et al. (2014) Chekuri, Chandra, Jan Vondrák, Rico Zenklusen. 2014.  Submodular function maximization via the multilinear relaxation and contention resolution schemes.  SIAM Journal on Computing 43(6) 1831–1879.
  * Chen and Krause (2013) Chen, Yuxin, Andreas Krause. 2013.  Near-optimal batch mode active learning and adaptive submodular optimization.  ICML (1) 28(160-168) 8–1.
  * Fujii and Kashima (2016) Fujii, Kaito, Hisashi Kashima. 2016.  Budgeted stream-based active learning via adaptive submodular maximization.  Advances in Neural Information Processing Systems. 514–522.
  * Fukunaga et al. (2019) Fukunaga, Takuro, Takuya Konishi, Sumio Fujita, Ken-ichi Kawarabayashi. 2019.  Stochastic submodular maximization with performance-dependent item costs.  Proceedings of the AAAI Conference on Artificial Intelligence, vol. 33. 1485–1494.
  * Golovin and Krause (2011) Golovin, Daniel, Andreas Krause. 2011.  Adaptive submodularity: Theory and applications in active learning and stochastic optimization.  Journal of Artificial Intelligence Research 42 427–486.
  * Gupta et al. (2011) Gupta, Anupam, Ravishankar Krishnaswamy, Marco Molinaro, R Ravi. 2011.  Approximation algorithms for correlated knapsacks and non-martingale bandits.  2011 IEEE 52nd Annual Symposium on Foundations of Computer Science. IEEE, 827–836.


#  SecFL: Confidential Federated Learning using TEEs

Demo paper

Do Le Quoc  Huawei Munich Research Center Germany and  Christof Fetzer  TU
Dresden Germany

###### Abstract.

Federated Learning (FL) is an emerging machine learning paradigm that enables
multiple clients to jointly train a model to take benefits from diverse
datasets from the clients without sharing their local training datasets. FL
helps reduce data privacy risks. Unfortunately, FL still exist several issues
regarding privacy and security. First, it is possible to leak sensitive
information from the shared training parameters. Second, malicious clients can
collude with each other to steal data, models from regular clients or corrupt
the global training model. To tackle these challenges, we propose SecFL\- a
confidential federated learning framework that leverages Trusted Execution
Environments (TEEs). SecFL performs the global and local training inside TEE
enclaves to ensure the confidentiality and integrity of the computations
against powerful adversaries with privileged access. SecFL provides a
transparent remote attestation mechanism, relying on the remote attestation
provided by TEEs, to allow clients to attest the global training computation
as well as the local training computation of each other. Thus, all malicious
clients can be detected using the remote attestation mechanisms.

##  1\. Introduction

FL (Konečnỳ et al., 2016) is an emerging machine learning technique which
allows participating clients to collaboratively train a joint global machine
learning model without sharing their local training data. FL reduces privacy
risks for the local training data which may be highly sensitive relating to
personal finances, political views, health, etc. Thus, it has been used widely
in the industry since it helps companies comply with regulations on issues
regarding the way in which personal data is handled and processed - such as
EU’s General Data Protection Regulation (GDPR) (Voigt and Von dem Bussche,
2017). The core idea of FL is that each client trains a local model, rather
than sharing training data to a centralized training system which is deployed
in an untrusted environment, e.g., a public cloud. For each iteration, the
clients send their local training parameters to the central system to train a
global model which takes benefits from all local training data from clients.
Typically, the central system aggregates the local training parameters from
the clients and sends the aggregated parameters back to them. This training
process is repeated until it converges or the global model reaches a certain
desired accuracy. An example of FL in real-life deployment is that several
hospitals collaborate to develop a shared machine learning model based on
their patient data to detect a disease at an early stage. Each hospital trains
its data locally, shares the local model with the central training system, and
receives the global model in each iteration.

While promising at first glance, FL paradigm suffers several vulnerabilities.
First, an attacker with privileged/root accesses can easily obtain the
training models (➊). The attacker can also compromise the privacy of
individuals in the training data by inferring it from parameters of the global
model (Abadi et al., 2016). Therefore, the training models need to be
protected at rest, in transit, and in use. Second, a large number of malicious
clients may collude with each other to reveal local data and local models of
the remaining clients (Mugunthan et al., 2020) (➋). Last but not least, these
malicious clients can tamper their local training data or parameters updates
forwarded to the central training system to corrupt the global model (Xie et
al., 2020; Fang et al., 2020) (➌).

To handle the issues ➊ ➋, state-of-the-art solutions rely on a privacy-
preserving mechanism such as differential privacy or secure multiparty
computation (MPC). The disadvantage of the differential privacy mechanism is
that it reduces the performance of the global training model regarding utility
or accuracy. Meanwhile, the solutions based on secure multiparty computation
incur significant overhead (Le Quoc et al., 2020; Kunkel et al., 2019). To
cope with issue ➌, several Byzantine-robust federated learning mechanisms have
been proposed (Blanchard et al., 2017; Xie et al., 2020; Fang et al., 2020;
Bhagoji et al., 2019). The core idea behind these mechanisms is to reduce the
impact of statistical outliers during model updates in the federated learning
system. However, recent works (Xie et al., 2020; Fang et al., 2020; Bhagoji et
al., 2019) show that the mitigation of the impact is still not enough to
protect the utility of the global model. The malicious clients can still
affect the accuracy of the global model trained by a Byzantine-robust
mechanism by carefully tampering with their model parameters sent to the
central training system (Cao et al., 2021).

In this work, we overcome these limitations by building a confidential
federated learning system called SecFL using TEEs, e.g., Intel SGX. Trusted
Execution Environment (TEE) technologies, such as Intel Software Guard
eXtensions (SGX), have gained much attention in the industry (Gordon, [n.d.];
Karnati, 2018; Singh et al., 2021) as well as in academia (Arnautov et al.,
2016; Costan and Devadas, 2016; Tsai et al., 2017; Le Quoc et al., 2019; Ozga
et al., 2021a, b; Le Quoc et al., 2020; Singh et al., 2020; Krahn et al.,
2020; Ozga et al., 2020; Bailleu et al., 2021; Ozga et al., 2021c). To ensure
confidentiality and integrity of applications, TEEs execute their code and
data inside an encrypted memory region called _enclave_. Adversaries with
privileged access cannot read or interfere with the memory region and only the
processor can decrypt and execute the application inside an enclave. In
addition, TEEs such as Intel SGX also provide a mechanism for users to verify
that the TEE is genuine and that an adversary did not alter their application
running inside TEE enclaves. The verification process is called _Remote
Attestation_ (Costan and Devadas, 2016) and allows users to establish trust in
their application running inside an enclave on a remote host.

We leverage TEEs to handle issue ➊, by providing end-to-end encryption in
SecFL. SecFL encrypts input training data and code (e.g., Python code) and
performs all training computations including local training and global
training insides TEE enclaves. SecFL enables all model updates via TLS
connections between the enclave of clients and the enclaves of the central
training computation. Thus attackers with privileged accesses cannot violate
the integrity and confidentiality of the input training data, code, and
models. SecFL also ensures the freshness of the input training data, models,
and, by applying an advanced asynchronous monotonic counter service (Martin et
al., 2021). We tackle issues ➋ ➌ by developing in SecFL a Security Policy
Manager component based on the remote attestation mechanism supported by TEEs
(Gregor et al., 2020; Scarlata et al., 2018). The component ensures the
integrity of input data and training code, i.e., it makes sure that training
computations are running with correct code, correct input data and not
modified by anyone, e.g., an attacker or malicious client. This component also
monitors and attests to the compliance of participated clients with the pre-
defined agreement before collaborating to train the global machine learning
model. In addition, SecFL can clone the global training computation and
randomly take a sample of clients for the training computation. This helps to
detect outliers regarding the utility which helps to solve issue ➌. Our
preliminary evaluation shows that SecFL can ensure the confidentiality and
integrity of federated learning computations while maintaining the same
utility/accuracy of the training computations.

##  2\. Confidential Federated Learning

Figure 1. SecFL Architecture for Federated Learning.

Figure 1 shows the architecture of SecFL. The main goal of SecFL is not only
to ensure the confidentiality, integrity and freshness of input data, code,
and machine learning models but also to enable multiple clients (who do not
necessarily trust each other) to get the benefits of collaborative training
without revealing their local training data. In SecFL, each client performs
the local training also inside TEE enclaves to make sure that no one tamper
input data or training code during the computations. To govern and coordinate
the collaborative machine learning training computation between clients, we
design in SecFL a trusted management component, called Security Policy Manager
which maintains security policies based on the agreement among all clients to
define the access control over global training computation, the global
training model, also the code and input data used for local training at each
client. Security Policy Manager automatically and transparently performs
remote attestation to make sure the local computations are running correct
code, correct input data, and on correct platforms as the agreement. It only
allows clients to participate in the global training after successfully
performing the remote attestation process. It also conducts the remote
attestation on the enclaves that execute the global training in a cloud, to
ensure that no one at the cloud provider side modify the global training
aggregation computation. SecFL encrypts the training code, and Security Policy
Manager only provides the key to decrypt it inside enclaves after the remote
attestation. Secrets including keys for encryption/decryption in each policy
are generated by the Security Policy Manager also running inside Intel SGX
enclaves and cannot be seen by any human or client. Examples of the policies
can be found in (Team, [n.d.]; Gregor et al., 2020).

After receiving the agreed security policies from clients, Security Policy
Manager strictly enforces them. It only passes secrets and configuration to
applications (i.e., training computations), after attesting them. The training
computations are executed inside Intel SGX enclaves and associated with
policies provided and pre-agreed by clients. The training computations are
identified by a secure hash and the content of the files (input data) they can
access. Secrets can be passed to applications as command-line arguments,
environment variables, or can be injected into files. The files can contain
environment variables referring to the names of secrets defined in the
security policy. The variables are transparently replaced by the value of the
secret when an application that is permitted to access the secrets reads the
file. We design the component Security Policy Manager in the way that we can
delegate the management of it to an untrusted party, e.g., a cloud provider,
while clients can still trust that their security policies for protecting
their properties are safely maintained and well protected. In SecFL, clients
can attest Security Policy Manager component, i.e., they can verify that it
runs the expected unmodified code, in a correct platform before uploading
security policies. We implement SecFL using Intel OpenFL (Reina et al., 2021)
— a distributed federated machine learning framework We run the local and
global training computations inside SGX enclaves using SCONE (Arnautov et al.,
2016) — a shielded execution framework to enable unmodified applications to
run inside SGX enclaves. In the SCONE platform, the source code of an
application is recompiled against a modified standard C library (SCONE libc)
to facilitate the execution of system calls. The address space of the
application stays within an enclave. In SecFL, the input training data and
code are encrypted using the file system shield of SCONE, and then decrypted
and processed inside SGX enclaves which cannot be accessed even by strong
attackers with root access. We rely on our previous works (Gregor et al.,
2020; Team, [n.d.]) to implement Security Policy Manager. A demo of SecFL is
publicly available in (Quoc, 2021).

## References

  * (1)
  * Abadi et al. (2016) Martin Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. 2016.  Deep Learning with Differential Privacy. In _Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (CCS)_.
  * Arnautov et al. (2016) Sergei Arnautov, Bohdan Trach, Franz Gregor, Thomas Knauth, Andre Martin, Christian Priebe, Joshua Lind, Divya Muthukumaran, Dan O’Keeffe, Mark L. Stillwell, David Goltzsche, Dave Eyers, Rüdiger Kapitza, Peter Pietzuch, and Christof Fetzer. 2016.  SCONE: Secure Linux Containers with Intel SGX. In _12th USENIX Symposium on Operating Systems Design and Implementation (OSDI)_.
  * Bailleu et al. (2021) Maurice Bailleu, Dimitra Giantsidi, Vasilis Gavrielatos, Do Le Quoc, Vijay Nagarajan, and Pramod Bhatotia. 2021.  Avocado: A Secure In-Memory Distributed Storage System. In _2021 $\\{$USENIX$\\}$ Annual Technical Conference ($\\{$USENIX$\\}$$\\{$ATC$\\}$ 21)_.
  * Bhagoji et al. (2019) Arjun Nitin Bhagoji, Supriyo Chakraborty, Prateek Mittal, and Seraphin Calo. 2019.  Analyzing federated learning through an adversarial lens. In _International Conference on Machine Learning_. PMLR.
  * Blanchard et al. (2017) Peva Blanchard, El Mahdi El Mhamdi, Rachid Guerraoui, and Julien Stainer. 2017.  Machine learning with adversaries: Byzantine tolerant gradient descent. In _Proceedings of the 31st International Conference on Neural Information Processing Systems_. 118–128.
  * Cao et al. (2021) Xiaoyu Cao, Jinyuan Jia, and Neil Zhenqiang Gong. 2021\.  Provably Secure Federated Learning against Malicious Clients. In _Proceedings of the AAAI Conference on Artificial Intelligence_.
  * Costan and Devadas (2016) Victor Costan and Srinivas Devadas. 2016.  Intel SGX Explained.  _IACR Cryptol. ePrint Arch._ (2016).
  * Fang et al. (2020) Minghong Fang, Xiaoyu Cao, Jinyuan Jia, and Neil Gong. 2020\.  Local model poisoning attacks to byzantine-robust federated learning. In _29th $\\{$USENIX$\\}$ Security Symposium ($\\{$USENIX$\\}$ Security 20)_.
  * Gordon ([n.d.]) James C Gordon. [n.d.].  Microsoft Azure Confidential Computing with Intel SGX.  https://software.intel.com/content/www/us/en/develop/blogs/microsoft-azure-confidential-computing-with-intel-sgx.html.  Accessed: Sept 2021.
  * Gregor et al. (2020) Franz Gregor, Wojciech Ozga, Sébastien Vaucher, Rafael Pires, Sergei Arnautov, André Martin, Valerio Schiavoni, Pascal Felber, Christof Fetzer, et al. 2020\.  Trust management as a service: Enabling trusted execution in the face of byzantine stakeholders. In _2020 50th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN)_.
  * Karnati (2018) Pratheek Karnati. 2018\.  Data-in-use protection on IBM Cloud using Intel SGX.  https://www.ibm.com/cloud/blog/data-use-protection-ibm-cloud-using-intel-sgx.  Accessed: Sept 2021.
  * Konečnỳ et al. (2016) Jakub Konečnỳ, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. 2016\.  Federated learning: Strategies for improving communication efficiency.  _arXiv preprint arXiv:1610.05492_ (2016).
  * Krahn et al. (2020) Robert Krahn, Donald Dragoti, Franz Gregor, Do Le Quoc, Valerio Schiavoni, Pascal Felber, Clenimar Souza, Andrey Brito, and Christof Fetzer. 2020.  TEEMon: A continuous performance monitoring framework for TEEs. In _Proceedings of the 21th International Middleware Conference (Middleware)_.
  * Kunkel et al. (2019) Roland Kunkel, Do Le Quoc, Franz Gregor, Sergei Arnautov, Pramod Bhatotia, and Christof Fetzer. 2019\.  Tensorscone: A secure tensorflow framework using intel sgx.  _arXiv preprint arXiv:1902.04413_ (2019).
  * Le Quoc et al. (2020) Do Le Quoc, Franz Gregor, Sergei Arnautov, Roland Kunkeland, Pramod Bhatotia, and Christof Fetzer. 2020\.  secureTF: A Secure TensorFlow Framework. In _Proceedings of the 21th International Middleware Conference (Middleware)_.
  * Le Quoc et al. (2019) Do Le Quoc, Franz Gregor, Jatinder Singh, and Christof Fetzer. 2019\.  SGX-PySpark: Secure Distributed Data Analytics. In _Proceedings of the World Wide Web Conference (WWW)_.
  * Martin et al. (2021) André Martin, Cong Lian, Franz Gregor, Robert Krahn, Valerio Schiavoni, Pascal Felber, and Christof Fetzer. 2021.  ADAM-CS: Advanced Asynchronous Monotonic Counter Service. In _2021 51st Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN)_.
  * Mugunthan et al. (2020) Vaikkunth Mugunthan, Anton Peraire-Bueno, and Lalana Kagal. 2020\.  PrivacyFL: A simulator for privacy-preserving and secure federated learning. In _Proceedings of the 29th ACM International Conference on Information & Knowledge Management (CIKM)_.
  * Ozga et al. (2021a) Wojciech Ozga, Christof Fetzer, et al. 2021a.  Perun: Confidential Multi-stakeholder Machine Learning Framework with Hardware Acceleration Support. In _IFIP Annual Conference on Data and Applications Security and Privacy_. Springer, 189–208.
  * Ozga et al. (2020) Wojciech Ozga, Do Le Quoc, and Christof Fetzer. 2020\.  A practical approach for updating an integrity-enforced operating system. In _Proceedings of the 21th International Middleware Conference (Middleware)_.
  * Ozga et al. (2021b) Wojciech Ozga, Do Le Quoc, and Christof Fetzer. 2021b.  Perun: Secure Multi-Stakeholder Machine Learning Framework with GPU Support.  _arXiv preprint arXiv:2103.16898_ (2021).
  * Ozga et al. (2021c) Wojciech Ozga, Do Le Quoc, and Christof Fetzer. 2021c.  WELES: Policy-driven Runtime Integrity Enforcement of Virtual Machines.  _arXiv preprint arXiv:2104.14862_ (2021).
  * Quoc (2021) Do Le Quoc. 2021\.  Secure Federate Learning using SCONE and Intel-OpenFL.  https://youtu.be/J3tQcjrX3Jk.  Accessed: Sept 2021.
  * Reina et al. (2021) G Anthony Reina, Alexey Gruzdev, Patrick Foley, Olga Perepelkina, Mansi Sharma, Igor Davidyuk, Ilya Trushkin, Maksim Radionov, Aleksandr Mokrov, Dmitry Agapov, Jason Martin, Brandon Edwards, Micah J. Sheller, Sarthak Pati, Prakash Narayana Moorthy, Shih han Wang, Prashant Shah, and Spyridon Bakas. 2021\.  OpenFL: An open-source framework for Federated Learning.  arXiv:2105.06413 [cs.LG]
  * Scarlata et al. (2018) Vinnie Scarlata, Simon Johnson, James Beaney, and Piotr Zmijewski. 2018.  Supporting third party attestation for Intel SGX with Intel data center attestation primitives.  _White paper_ (2018).
  * Singh et al. (2020) Jatinder Singh, Jennifer Cobbe, Do Le Quoc, and Zahra Tarkhani. 2020.  Enclaves in the Clouds: Legal considerations and broader implications.  _Queue_ (2020).
  * Singh et al. (2021) Jatinder Singh, Jennifer Cobbe, Do Le Quoc, and Zahra Tarkhani. 2021.  Enclaves in the Clouds.  _Commun. ACM_ 64, 5 (2021), 42–51.
  * Team ([n.d.]) Scontain Team. [n.d.].  CAS policy language v0.3.  https://sconedocs.github.io/CAS_session_lang_0_3/.  Accessed: Sept 2021.
  * Tsai et al. (2017) Chia-Che Tsai, Donald E Porter, and Mona Vij. 2017.  Graphene-SGX: A Practical Library OS for Unmodified Applications on SGX. In _USENIX Annual Technical Conference (USENIXATC 17)_.
  * Voigt and Von dem Bussche (2017) Paul Voigt and Axel Von dem Bussche. 2017.  The eu general data protection regulation (gdpr).  _A Practical Guide, 1st Ed., Cham: Springer International Publishing_ (2017).
  * Xie et al. (2020) Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta. 2020\.  Fall of empires: Breaking Byzantine-tolerant SGD by inner product manipulation. In _Uncertainty in Artificial Intelligence_. PMLR.