2022 Preprint 0

# ProtoBandit: Efficient Prototype Selection
via Multi-Armed Bandits

Arghya Roy Chaudhuri<EMAIL_ADDRESS>
Pratik Jawanpuria<EMAIL_ADDRESS>
Bamdev Mishra<EMAIL_ADDRESS>
Microsoft India

###### Abstract

In this work, we propose a multi-armed bandit-based framework for identifying
a compact set of informative data instances (i.e., the prototypes) from a
source dataset $\mathcal{S}$ that best represents a given target set
$\mathcal{T}$. Prototypical examples of a given dataset offer interpretable
insights into the underlying data distribution and assist in example-based
reasoning, thereby influencing every sphere of human decision-making. Current
state-of-the-art prototype selection approaches require
$O(|\mathcal{S}||\mathcal{T}|)$ similarity comparisons between source and
target data points, which becomes prohibitively expensive for large-scale
settings. We propose to mitigate this limitation by employing stochastic
greedy search in the space of prototypical examples and multi-armed bandits
for reducing the number of similarity comparisons. Our randomized algorithm,
ProtoBandit, identifies a set of $k$ prototypes incurring $O(k|\mathcal{S}|)$
similarity comparisons, which is independent of the size of the target set. An
interesting outcome of our analysis is for the $k$-medoids clustering problem
($\mathcal{T}=\mathcal{S}$ setting) in which we show that our algorithm
ProtoBandit approximates the BUILD step solution of the partitioning around
medoids (PAM) method in $O(k|\mathcal{S}|)$ complexity. Empirically, we
observe that ProtoBandit reduces the number of similarity computation calls by
several orders of magnitudes ($100-1000$ times) while obtaining solutions
similar in quality to those from state-of-the-art approaches.

##  1 Introduction

Prototypical examples are data instances that together summarizes a given
dataset or an underlying data distribution (Weiser, 1982; Bien and Tibshirani,
2011b, a; Koh and Liang, 2017; Yeh et al., 2018). Such compact representation
of a dataset is especially useful in this age of big-data, where the size of
datasets goes beyond the capability of manual checking. Hence, prototypical
samples help domain experts and data scientists by providing meaningful
insights in complex domains (Gurumoorthy et al., 2019). They also provide
example-based reasoning, thereby improving the interpretability of data
distributions (Kim et al., 2014, 2016; Gurumoorthy et al., 2021).

A popular use-case of prototype selection is to select a test group that best
represent the control group (or vice-versa). For product design (Leahy, 2013),
a designer needs to know the required features for a new product directly from
the targeted users. Therefore, it is important to select a small subset of
users that best represent the larger customer base. In the healthcare domain,
prototype selection has been employed for building training datasets (Suyal
and Singh, 2021). Another interesting application of prototype selection is in
explainable AI (Linardatos et al., 2021), where we need to analyze the cause
behind the output of an AI model.

Works such as (Olvera-López et al., 2008; Bien and Tibshirani, 2011b) have
proposed finding prototypical elements in supervised setting where both
features and label information of the data points are available. However,
recent works (Gurumoorthy et al., 2019, 2021; Kim et al., 2016) have focused
on the more general unsupervised setting where only feature information is
available. In this paper, we focus on unsupervised prototype selection. A key
challenge here is the big-data setting, where one may require to perform
similarity computations between huge number of data points pairs (Zukhba,
2010). This makes the existing algorithms (Kim et al., 2016; Gurumoorthy et
al., 2019, 2021) is impractical. Below, we concretize the prototype selection
problem setup and discuss our contributions.

#### Prototype selection problem setup.

Given two non-empty sets of points (source) $\mathcal{S}$ and (target)
$\mathcal{T}$, a dissimilarity measure
$d:\mathcal{T}\times\mathcal{S}\mapsto[0,1]$, and a positive integer
$k\leq|\mathcal{S}|$, our aim is to find a set
$\mathcal{M}\subseteq\mathcal{S}$ that best represents the target set
$\mathcal{T}$ such that $|\mathcal{M}|\leq k$. The set $\mathcal{M}$ is the
set of prototypical elements. We call the tuple
$(\mathcal{S},\mathcal{T},\mathbf{q},d,k)$ a instance of the prototype
selection problem, where $\mathbf{q}\in[0,1]^{|\mathcal{T}|}$ is the weight
vector associated with $T$. Such a weight vector can be useful in applications
where not every target sample is equally important and can also be used to
capture the underlying distribution of the target set (if available). For the
sake of convenience and interpretability, we assume
$\sum_{b\in\mathcal{T}}q_{b}=1$.

####  $k$-medoids clustering as a prototype selection problem.

Recently, Gurumoorthy et al. (2021) have shown that optimal transport based
prototype selection problem reduces to the $k$-medoids clustering problem when
the target set is same as the source set ($\mathcal{T}=\mathcal{S}$). Unlike
the more popular $k$-means clustering, the $k$-medoids clustering problem
requires the cluster centers to be actual data points in the given dataset
$\mathcal{S}$. Hence, $k$-medoids clustering is especially useful when
interpretable cluster centers are desired. For instance, $k$-means centers of
a group of images can visually be a random noise image (Leskovec et al., 2020;
Tiwari et al., 2020). Another benefit of the k-medoids set up is that it only
relies distances/similarities between data points. However, it should be noted
that $k$-medoids clustering is a NP-hard problem in general Schubert and
Rousseeuw (2019). Popular $k$-medoids algorithms include the partitioning
around medoids (PAM) method (Kaufman and Rousseeuw, 1990, 2009) and approaches
inspired by PAM such as FASTPAM1 (Schubert and Rousseeuw, 2019), CLARA
(Kaufman and Rousseeuw, 1990), and CLARANS (Ng and Han, 2002). Among them,
FASTPAM1 guarantees the same solution as PAM and has a computational
complexity of $O(|\mathcal{S}|^{2})$. CLARA and CLARANS, on the other hand,
output PAM-like solution. A recent randomized approach, BanditPAM (Tiwari et
al., 2020), guarantees the same results as PAM with a (expected) computational
complexity of $O(k|\mathcal{S}|\log(|\mathcal{S}|))$.

#### Our Contributions.

We first generalize the BUILD step of the PAM method (Kaufman and Rousseeuw,
1990) to allow for the scenarios when $\mathcal{S}\neq\mathcal{T}$. We next
prove that the BUILD step of the proposed generalized PAM algorithm is
equivalent to the existing optimal transport based SPOTgreedy (Gurumoorthy et
al., 2021) algorithm for prototype selection. This is interesting because the
PAM algorithm can now also be understood from the lens of the optimal
transport theory. Since the BUILD step of the proposed generalized PAM method
is based on a greedy search procedure, we use it as a stepping stone to
propose a sampling-based algorithm ProtoBandit for the prototype selection
problem. Specifically, we introduce the following novelties in the ProtoBandit
algorithm.

  1. 1.

We employ random subset selection for more efficient greedy search as it
reduces the search space (to find the next potential prototype) in the source
set $\mathcal{S}$.

  2. 2.

At each iteration, existing methods (Kim et al., 2016; Gurumoorthy et al.,
2019, 2021) require similarity computations for every element of the selected
subset $\mathcal{M}$ with every element in the target set $\mathcal{T}$. Thus,
if the target set $\mathcal{T}$ is large, or potentially infinite, then such
approaches become impractical. We circumvent this issue by employing the
multi-armed bandits (MAB) based sampling technique to estimate the similarity
of a source point with the target set $\mathcal{T}$.

Our key technical result is that the similarity computations required by the
proposed ProtoBandit is independent of the target set size $|\mathcal{T}|$.
Overall, ProtoBandit requires $O(k|S|)$ computations for obtaining $k$
prototypes from the source set $\mathcal{S}$ that represent the target set
$\mathcal{T}$. We also provide an approximation guarantee of the prototypical
set obtained by the proposed ProtoBandit algorithm. In particular, let
$f:2^{\mathcal{S}}\mapsto[0,1]$ denote the similarity function between an
input (candidate) set $\mathcal{M}$ and the target set $\mathcal{T}$ and
$\mathcal{M}^{*}$ be the optimal solution. Then, we prove that
$f(\mathcal{M}_{ALG})\geq\left(1-e^{-1}-\epsilon\right)f(\mathcal{M}^{*})-\nu$
with probability at least $1-\delta$, where
$\mathcal{M}_{ALG}\subset\mathcal{S}$ is output prototype set of our proposed
ProtoBandit, $\epsilon,\nu\in(0,1)$ are the approximation parameters, and
$\delta\in(0,0.05)$ is the error threshold. A corollary to our main result is
that ProtoBandit approximates the BUILD step solution of the PAM method for
the $k$-medoids clustering problem (i.e, the case when
$\mathcal{T}=\mathcal{S}$) in $O(k|\mathcal{S}|)$ complexity.

##  2 Related work

#### Prototype selection.

The problem of prototype selection has been mostly explored (Bien and
Tibshirani, 2011b; Crammer et al., 2002; Wohlhart et al., 2013; Wei et al.,
2015) in the supervised learning setups where the label of the data points are
available. Recent prototype selection approaches such as MMD-Critic (Kim et
al., 2016), ProtoDash (Gurumoorthy et al., 2019), and SPOTgreedy (Gurumoorthy
et al., 2021), aim at obtaining the set of prototypical elements
$\mathcal{M}\subset\mathcal{S}$ such that $\mathcal{M}$’s underlying
distribution is close to that of the target $\mathcal{T}$. Such approaches are
suitable in unsupervised settings as they assume availability of only the
similarity (or distance) between pairs $(a,b)$, where $a\in\mathcal{S}$ and
$b\in\mathcal{T}$. MMD-Critic and ProtoDash employ the MMD distance to capture
the similarity between two distributions while SPOTgreedy uses the Wasserstein
distance, i.e., the optimal transport framework. We describe the SPOTgreedy
algorithm in detail in Appendix B. The above three approaches are based on
greedy search and a common bottleneck in them is that, at every iteration of
greedy search, they require $\mathcal{O}(|\mathcal{T}|)$ similarity
computations, which becomes impractical as the target set $\mathcal{T}$
becomes large. To this end, we propose a multi-armed bandits based approach to
alleviate this concern.

#### PAM algorithm.

Prototype selection when the source and target sets are identical may
specifically be viewed as identifying important data points in the given set,
i.e., data summarisation. An intuitive way of unsupervised data summarisation
is to apply a centroid-based clustering technique and choose the cluster
centers as the representative of the whole dataset. A popular approach to
accomplish this is $k$-medoids clustering using the partition around medoids
(PAM) method (Kaufman and Rousseeuw, 1990). PAM applies an exhaustive greedy
search over the whole set through two main steps: BUILD and SWAP. During the
BUILD step, PAM selects the medoids, and during the SWAP step it improves upon
the already chosen medoids by replacing them with the new ones.

##  3 ProtoBandit: An Efficient Prototype Selection Algorithm

In this section, we first generalize the PAM algorithm (Kaufman and Rousseeuw,
1990) to the prototype selection problem (i.e., the sets $\mathcal{S}$ and
$\mathcal{T}$ are different). We then build on the generalized PAM algorithm
and propose ProtoBandit, which makes use of approximate greedy search and
multi-armed bandit frameworks.

###  3.1 Generalized PAM

We propose two modifications in the existing $k$-medoids clustering algorithm,
PAM, to generalize it to the prototype selection setting. We detail the BUILD
step of the generalized PAM algorithm in Algorithm 1. The full generalized PAM
algorithm is in Appendix A.

The first modification enables the algorithm to choose medoids from a set that
is different from the set of points to be clustered. Therefore, unlike the
original PAM algorithm, Algorithm 1 can choose set of medoids from
$\mathcal{S}$ to cluster the points in $\mathcal{T}$, even if
$\mathcal{S}\neq\mathcal{T}$. The second modification lies in choosing the
number of elements $r$ while updating the set of chosen points $\mathcal{M}$
during the BUILD step, which allows for additional flexibility and efficiency.
In our experiments, we consider $r=1$ setting unless specified otherwise. In
this setting the medoids from the source set $\mathcal{S}$ are selected in a
(strict) sequential manner, which has both theoretical and qualitative
benefits.

Algorithm 1 BUILD step for the generalized PAM algorithm

Input :

Problem instance given by $(\mathcal{S},\mathcal{T},\mathbf{q},d,k)$, and a
positive integers $r\in\\{1,\cdots,k\\}$.

Output :

A set $\mathcal{M}$, such that $|\mathcal{M}|=k$

Initialization: For each $j\in\mathcal{T}$, set $D_{j}=\infty$.

In this step we apply greedy strategy to choose an initial set of $k$
prototypes. $\mathcal{M}=\emptyset$

while  _$|\mathcal{M}| <k$_ do

Define gain vector $g$ with entries
$g_{i}=\sum_{j\in\mathcal{T}}q_{j}\max\\{D_{j}-d(j,i),0\\},\;\forall
i\in\mathcal{S}\setminus\mathcal{M}.$ (1) if  _$\forall
i\in\mathcal{S}\setminus\mathcal{M},g_{i}=0$_ then // no meaningful prototype
to add

$Q\stackrel{{\scriptstyle\mathclap{\mbox{\tiny{def}}}}}{{=}}$ Choose $r$
elements from $\mathcal{S}\setminus\mathcal{M}$ at random

else

$Q\stackrel{{\scriptstyle\mathclap{\mbox{\tiny{def}}}}}{{=}}$ Set of indices
of top $r$ largest _non-zero_ elements in
$g=\\{g_{i}\\}_{i=1}^{|\\{\mathcal{S}\setminus\mathcal{M}\\}|}$

end if

$\mathcal{M}=\mathcal{M}\cup Q$ and $\forall j\in\mathcal{T}$ update $D_{j}$.

end while

Below, we show the equivalence between the BUILD step of the proposed
generalized PAM algorithm (in Algorithm 1) and the SPOTgreedy algorithm
(Gurumoorthy et al., 2021). To this end, we define $D_{j}$ to be the
dissimilarity between a point $j$ and the closest object in $\mathcal{M}$,
i.e.,

$D_{j}=\min_{i\in\mathcal{M}}\\{d(j,i)\\}\;\left[\text{wherein dissimilarity
measure}\;d:\mathcal{T}\times\mathcal{S}\mapsto[0,1]\right].$ (2)

######  Lemma 3.1.

Given a problem instance $(\mathcal{S},\mathcal{T},\mathbf{q},d,k)$, for a
fixed value of the input parameter $r\in\\{1,\cdots,k\\}$, the $k$ points
identified by SPOTgreedy is identical with the set of selected point by
Algorithm 1.

The proof of Lemma 3.1 is given in Appendix B. The objective of this lemma is
to show that given a similarity matrix $Z\in[0,1]^{m\times n}$ at each
iteration Algorithm 1 chooses a prototype by maximizing the following
function:

$f(\mathcal{M})=\sum_{j\in\mathcal{T}}q_{j}\max_{i\in\mathcal{M}}Z_{ji}\;[\text{for
}\mathcal{M}\subset\mathcal{S}],$ (3)

where $Z$ is a $|\mathcal{T}|\times|\mathcal{S}|$ similarity matrix between
the target and the source sets, based on the given dissimilarity measure $d$.
We compute similarity between $j$-th data point in $\mathcal{T}$ and $i$-th
data point in $\mathcal{S}$ as

$Z_{ji}=C-d(j,i),$ (4)

where $C$ is a constant such that
$C\geq\max_{i\in\mathcal{S},j\in\mathcal{T}}\\{d(j,i)\\}$ and $C\geq 1$. Note
that $f$ in (3) is submodular (Gurumoorthy et al., 2021).

For choosing $k$ prototypes, Algorithm 1 incurs
$O(|\mathcal{S}||\mathcal{T}|k/r)$ similarity comparisons, which is a
computational bottleneck for large sets. We next propose an approximate
greedy-search for Algorithm 1 that scales independent of $|\mathcal{T}|$ and
linearly in $|\mathcal{S}|$.

###  3.2 Approximate Greedy Search

Due to simplicity and versatility of the greedy search framework, it has
attracted a lot of attentions (Minoux, 1978; Wei et al., 2014; Badanidiyuru
and Vondrák, 2014; Mirzasoleiman et al., 2015) for reducing the number of
similarity comparisons. We choose Stochastic-Greedy (Mirzasoleiman et al.,
2015) as it is one of the simplest and empirically fast (Mirzasoleiman et al.,
2015) algorithms for approximate greedy search. Without approximation, at
every step a greedy algorithm exhaustively searches through the set to find
next the potential solution. Instead, Stochastic-Greedy considers a random
subset for the same. The size of the subset is chosen depending on the
approximation parameter $\epsilon$, such that the outcome is optimal within a
$(1-e^{-1}-\epsilon)$ multiplicative factor.

Stochastic-Greedy (Mirzasoleiman et al., 2015) assumes that the objective
function evaluation can be done in $O(1)$. Also, for each point it examines,
the exact value of the objective function has to be computed. Let us
understand its effect on the problem of prototype selection through an
example. Assuming, $\mathcal{R}\subset\mathcal{S}\setminus\mathcal{M}$ be a
random subset chosen by Stochastic-Greedy at the $i$-th iteration, it modifies
Equation 1 to the following:

$g_{i}=\sum_{j\in\mathcal{T}}q_{j}\max\\{D_{j}-d(j,i),0\\},\;\forall
i\in\mathcal{R}.$ (5)

We note, for each point $i\in\mathcal{S}$ , it needs $O(|\mathcal{T}|)$
similarity comparisons to evaluate Equation 5 exactly. This might become
impractical for a large target set $\mathcal{T}$, and to get around, one can
estimate the value via the Monte-Carlo sampling on $\mathcal{T}$ (according to
the distribution $\mathbf{q}$). However, not all the elements in $\mathcal{R}$
are equally strong contenders for being the next prototype. Hence, it is
desired to allocate more similarity comparisons to differentiate between
contentious elements of $\mathcal{R}$ which are close to the local optimal,
while saving them on the easily distinguishable sub-optimal elements. We
mitigate this issue by identifying an approximate solution of Equation 5 via
multi-armed bandits (MAB) (Berry and Fristedt, 1985) that we discuss next.

###  3.3 Using Multi-Armed Bandits (MAB) in Prototype Selection

#### Background on Multi-Armed Bandits.

Multi-armed bandits (Berry and Fristedt, 1985) is a popular abstraction of
sequential decision making under the uncertainty. An _arm_ of a bandit
represents a decision, while _pull_ of an arm represents taking decision
corresponding to that arm. Further, we assume each arm has a probability
distribution associated with it, and when pulled, a real-valued reward is
generated in i.i.d. fashion from the underlying probability-distribution
called reward-distribution. This probability distribution is called reward
distribution of that particular arm, and is unknown to the experimenter. For
simplicity, we assume the reward-distribution for each arm is supported on the
interval $[0,1]$. Under this scenario, it is an interesting problem to
identify the best arm incurring minimal number of total samples.

To put formally, we assume $\mathcal{A}$ be the given set of $n$ arms with
$\mu_{a}$ being the expected mean reward of arm $a\in\mathcal{A}$. For
simplicity, we assume, $\mu_{a_{1}}\geq\mu_{a_{2}}\geq\cdots\mu_{a_{n}}\geq
0$. The problem of best arm identification is defined as identifying the arm
$a$ which has the highest expected reward $\mu_{a}$. As the underlying reward
distribution of the arms are unknown, the only way to compare the arms based
on their expected reward is to sample them sufficiently. Hence, we seek an
approximate probabilistic solution and modify the best-arm identification
problem as follows. For a given tolerance $\nu\in[0,1]$, we call an arm $a$ to
be _$(\nu,m)$ -optimal_ (for $m\leq n$) if $\mu_{a}\geq\mu_{a_{m}}-\nu$. For
$m=1$, it is called problem of best-arm identification to identify an
$(\nu,1)$-optimal arm. When $1\leq m\leq|\mathcal{A}|$, the problem
generalizes to identification of the best subset of size $m$ (Kalyanakrishnan
et al., 2012), wherein the objective is to identify any $m$ $(\nu,m)$-optimal
arms. Inheriting notations from Roy Chaudhuri and Kalyanakrishnan (2019), let
us denote the set of all $(\nu,m)$-optimal arms by
$\mathcal{TOP}_{m}(\nu)\stackrel{{\scriptstyle\mathclap{\mbox{\tiny{def}}}}}{{=}}\\{a:\mu_{a}\geq\mu_{a_{m}}-\nu\\}$111Given
a set of arms $\mathcal{A}$ and an $\nu\in(0,1]$, there might be more than $m$
arms in $\mathcal{TOP}_{m}(\nu)$.. Then, an algorithm is said to solve best-
subset identification problem if presented with a set of arms $\mathcal{A}$,
size of the output set $m$, a tolerance $\nu\in(0,1)$, and an error
probability bound $\delta\in(0,1)$, it stops with probability 1 after a finite
number of steps, and output an $m$-sized subset $Q_{(m)}\in\mathcal{A}$, such
that $\Pr\\{Q_{(m)}\subset\mathcal{TOP}_{m}(\nu)\\}\geq 1-\delta$. The
efficiency of solving a best-subset identification lies in incurring as low
number of samples as possible.

#### Applying MAB to Approximate Equation 5.

We have seen in Section 3.2 that evaluating Equation 5 is intensive in terms
of the number of similarity comparisons for a large target set $\mathcal{T}$.
During every iteration $\mathcal{M}$ remains fixed, so is the dissimilarity
$D_{j}$ between a point $j\in\mathcal{T}$ and the closest object in
$\mathcal{M}$. Therefore, if we sample from $\mathcal{T}$ using the
probability distribution $\mathbf{q}$, by normalization assumption of the
dissimilarity measure, for every element $i\in\mathcal{S}$ we shall get a
probability distribution over the $[0,1]$, with the true mean being given by
Equation 1. Hence, we can treat elements of the source set $\mathcal{S}$ as
arms of a MAB instance. Thus, at each round, after we select a random subset
$\mathcal{R}\subset\mathcal{S}$, the problem reduces to identification of the
best subset of size $r$. Based on this idea, next, we propose an algorithm,
and analyze its correctness, and upper bound the incurred number of similarity
comparisons in the worst-case. In this paper, we confine to $r=1$, i.e., we
select one element per iteration.

The best-arm identification has attracted a lot of attention over the years
(Even-Dar et al., 2002, 2006; Karnin et al., 2013; Jamieson et al., 2014).
Among an array of algorithms, Median Elimination (Even-Dar et al., 2002) is
well-known due to its simplicity, and for incurring a number of samples that
is within a constant factor of the lower bound (Mannor and Tsitsiklis, 2004).
Recently, Hassidim et al. (2020) have proposed the approximate best arm (ABA)
algorithm for identification of an $(\nu,1)$-optimal arm, and have proven its
efficiency in sample-complexity compared to the existing algorithms like
Median Elimination (Even-Dar et al., 2002). We restate Theorem 1 from Hassidim
et al. (2020) on upperbounding the sample-complexity of ABA.

######  Lemma 3.2 (Restatement of (Hassidim et al., 2020, Theorem 1)).

Suppose, given a set of arms $\mathcal{A}$, the underlying reward distribution
of its each arm is supported on $[0,1]$. Then, given an $\nu\in(0,1)$, and
$\delta\in(0,0.5)$, ABA initialized with $\alpha=1-e^{-1}$ returns an
$(\nu,1)$-optimal arm with probability at least $1-\delta$ incurring no more
than $18\frac{|\mathcal{A}|}{\nu^{2}}\ln\frac{1}{\delta}$ samples.

Now, we are ready to introduce an MAB-based prototype selection algorithm,
ProtoBandit, and present its analysis in the next section.

###  3.4 Efficient Prototype Selection by Stochastic Greedy Search and MAB

We propose a meta algorithm ProtoBandit in Algorithm 2 that at each iteration
selects a random subset $\mathcal{R}\subset\mathcal{S}$ (like Stochastic-
Greedy (Mirzasoleiman et al., 2015)) to reduce the search space, and then
applies ABA to identify the best element. We emulate pulling of an arm via
sampling the target set $\mathcal{T}$ according to the distribution
$\mathbf{q}$ specified by the problem instance. To this end, we define the
method Pull in Algorithm 3, that is internally used by the ABA inside
ProtoBandit. We note, due to normalization assumption, the objective function
$f(\cdot)$ defined in Equation 3 must lie in the range $[0,1]$. In other
words, if for all $i\in\mathcal{S}$, and $j\in\mathcal{T}$, then we can take
$C=1$ to make $Z_{i,j}\in[0,1]$. Therefore, for any
$\mathcal{M}\subseteq\mathcal{S}$, $f(\mathcal{M})\in[0,1]$. Subsequently, the
assumptions to apply ABA remain valid.

Algorithm 2 ProtoBandit: Randomized Greedy Prototype Selection with MAB

Input :

Problem instance $(\mathcal{S},\mathcal{T},\mathbf{q},d,k)$, tolerance
$\epsilon\in(0,1)$, $\nu\in(0,1-\epsilon-1/e)$, and acceptable error
probability $\delta\in(0,0.05)$.

Output :

Set of prototype $\mathcal{M}\subset\mathcal{S}$, such that $|\mathcal{M}|=k$

Assert :

$\forall(y,x)\in\mathcal{T}\times\mathcal{S},d(y,x)\in[0,1]$.

Define a similarity function $sim:\mathcal{T}\times\mathcal{S}\mapsto[0,1]$ as
$sim\stackrel{{\scriptstyle\mathclap{\mbox{\tiny{def}}}}}{{=}}1-d(y,x),\forall(y,x)\in\mathcal{T}\times\mathcal{S}$.

Set $\mathcal{M}=\emptyset$

while  _$|\mathcal{M}|\leq k$_ do

Select a subset $\mathcal{R}\subset\mathcal{S}\setminus\mathcal{M}$ of size
$|\mathcal{R}|=\left\lceil\frac{|\mathcal{S}|}{k}\log\frac{1}{\epsilon}\right\rceil$,
using uniform random sampling with replacement. Apply ABA on $\mathcal{R}$,
with tolerance $\frac{\nu}{1-1/e-\epsilon}$, error threshold
$\frac{\delta}{k}$, and return an arm $a_{\text{out}}$.
$\mathcal{M}=\mathcal{M}\cup\\{a_{\text{out}}\\}$.

end while

Algorithm 3 Pull

Input :

Sampling domain $\mathcal{T}$, sampling distribution $\mathbf{q}$, chosen set
of prototypes $\mathcal{M}\subset\mathcal{S}$, an element
$i\in\mathcal{S}\setminus\mathcal{M}$, similarity function
$sim:\mathcal{T}\times\mathcal{S}\mapsto[0,1]$,.

Output :

Contribution value of $i$.

Sample an element $j\in\mathcal{T}$ according to sampling distribution
$\mathbf{q}$.

Return $\max\\{D_{j}-d(j,i),0\\}$, wherein $D_{j}$ is defined in Equation 2.

To derive the approximation guarantee for ProtoBandit, we inherit the analysis
of Stochastic-Greedy from Mirzasoleiman et al. (2015, Theorem 1) and lower
bound the probability of choosing an element from the optimal set in Lemma
3.3. Then, we apply this result to prove the approximation ratio.

######  Lemma 3.3.

The expected gain of ProtoBandit is at least
$\frac{1-\epsilon}{k}\sum_{a\in\mathcal{M}^{*}\setminus\mathcal{M}}\left(\Delta(a|\mathcal{M})-\frac{\nu}{1-\epsilon-1/e}\right)$
per iteration, where $\mathcal{M}$ is a current solution.

######  Proof 3.4.

To prove the lemma, let us first lower bound the probability of
$\mathcal{R}\cap(\mathcal{M}^{*}\setminus\mathcal{M})\neq\emptyset$. We note,

$\displaystyle\Pr\\{\mathcal{R}\cap(\mathcal{M}^{*}\setminus\mathcal{M})=\emptyset\\}$
$\displaystyle=\left(1-\frac{|\mathcal{M}^{*}\setminus\mathcal{M}|}{|\mathcal{S}\setminus\mathcal{M}|}\right)^{|\mathcal{R}|}\leq\exp\left(-|\mathcal{R}|\frac{|\mathcal{M}^{*}\setminus\mathcal{M}|}{|\mathcal{S}\setminus\mathcal{M}|}\right)$
$\displaystyle\leq\exp\left(-\frac{|\mathcal{R}|}{|\mathcal{S}|}|\mathcal{M}^{*}\setminus\mathcal{M}|\right)=\exp\left(-k\frac{|\mathcal{R}|}{|\mathcal{S}|}\frac{|\mathcal{M}^{*}\setminus\mathcal{M}|}{k}\right).$
(6)

Now, using the concavity of $exp(-\frac{k|\mathcal{R}|}{|\mathcal{S}|}x)$ with
respect to $x$, and given that
$|\mathcal{M}^{*}\setminus\mathcal{M}|\in\\{0,1,\cdots,k\\}$, we can re-write
Equation 3.4 as

$\displaystyle\implies\Pr\\{\mathcal{R}\cap(\mathcal{M}^{*}\setminus\mathcal{M})\neq\emptyset\\}$
$\displaystyle\geq\left(1-\exp\left(-k\frac{|\mathcal{R}|}{|\mathcal{S}|}\right)\right)\frac{|\mathcal{M}^{*}\setminus\mathcal{M}|}{k},$
$\displaystyle=\left(1-\exp\left(-\left\lceil\frac{|\mathcal{S}|}{k}\log\frac{1}{\epsilon}\right\rceil\frac{k}{|\mathcal{S}|}\right)\right)\frac{|\mathcal{M}^{*}\setminus\mathcal{M}|}{k}\left[\because|\mathcal{R}|=\left\lceil\frac{|\mathcal{S}|}{k}\log\frac{1}{\epsilon}\right\rceil\;\text{in
Algorithm}\leavevmode\nobreak\ \ref{alg:our_algo}\right],$
$\displaystyle\geq\left(1-\log\frac{1}{\epsilon}\right)\frac{|\mathcal{M}^{*}\setminus\mathcal{M}|}{k}\geq(1-\epsilon)\frac{|\mathcal{M}^{*}\setminus\mathcal{M}|}{k}.$
(7)

Now, we lower bound the value of $\Delta(a|\mathcal{M})$ by lower-bounding the
approximation offered by ABA. Suppose, at some iteration, $\mathcal{M}$ be the
already chosen set of prototypes. Also, let
$\hat{a}\stackrel{{\scriptstyle\mathclap{\mbox{\tiny{def}}}}}{{=}}\operatorname*{arg\,max}_{a\in\mathcal{R}}\Delta(a|\mathcal{M})$
be the the locally optimal solution, and $a_{\text{out}}$ be the output of ABA
inside a single iteration of ProtoBandit. Assuming
$\mathcal{R}\cap(\mathcal{M}^{*}\setminus\mathcal{M})\neq\emptyset$, we note,
the marginal contribution of $\hat{a}$ is at least as the marginal
contribution of any element of
$\mathcal{R}\cap(\mathcal{M}^{*}\setminus\mathcal{M})$. Therefore,
$\Delta(\hat{a}|\mathcal{M})\geq\max_{\mathcal{R}\cap(\mathcal{M}^{*}\setminus\mathcal{M})}\Delta(\hat{a}|\mathcal{M})$
and

$\operatorname{\mathop{\mathbb{E}}}[\Delta(\hat{a}|\mathcal{M})|\mathcal{M}]\geq\Pr\\{\mathcal{R}\cap(\mathcal{M}^{*}\setminus\mathcal{M})\neq\emptyset\\}\cdot\max_{a\in\mathcal{R}\cap(\mathcal{M}^{*}\setminus\mathcal{M})}\Delta(\hat{a}|\mathcal{M}).$
(8)

We note, $\Delta(\hat{a}|\mathcal{M})$ is at least as much as the contribution
of an element uniformly chosen at random from
$\mathcal{R}\cap(\mathcal{M}^{*}\setminus\mathcal{M})$. Again as $\mathcal{R}$
is chosen uniformly at random from $|\mathcal{S}\setminus\mathcal{M}|$, each
element of $\mathcal{M}^{*}\setminus\mathcal{M}$ is equally likely to belong
to $\mathcal{R}$. Hence, choosing an element uniformly at random from
$\mathcal{R}\cap(\mathcal{M}^{*}\setminus\mathcal{M})$ is equivalent to
choosing it uniformly at random from $\mathcal{M}^{*}\setminus\mathcal{M}$.
Putting together, from Equation 8 we get

$\leavevmode\nobreak\
\operatorname{\mathop{\mathbb{E}}}[\Delta(\hat{a}|\mathcal{M})|\mathcal{M}]\geq\Pr\\{\mathcal{R}\cap(\mathcal{M}^{*}\setminus\mathcal{M})\neq\emptyset\\}\frac{1}{|\mathcal{M}^{*}\setminus\mathcal{M}|}\sum_{a\in\mathcal{M}^{*}\setminus\mathcal{M}}\Delta(a|\mathcal{M}).$
(9)

In ProtoBandit, the arm $a_{\text{out}}$ returned by the subroutine ABA is not
necessarily identical to $\hat{a}$, but
$\left(\frac{\nu}{1-\epsilon-1/e},1\right)$-optimal (in $\mathcal{R}$) with
probability at least $1-\delta/k$. Therefore, letting
$\nu_{0}\stackrel{{\scriptstyle\mathclap{\mbox{\tiny{def}}}}}{{=}}\frac{\nu}{1-1/e-\epsilon}$,
$\left(\Delta(\hat{a}|\mathcal{M})-\Delta(a_{\text{out}}|\mathcal{M})\right)\leq\nu_{0}$
holds with probability at least $1-\delta/k$. Now, assuming $a_{\text{out}}$
is $(\nu_{0},1)$-optimal, and following the argument we used to build
Equations 8 and 9, we can write

$\displaystyle\operatorname{\mathop{\mathbb{E}}}[\Delta(a_{\text{out}}|\mathcal{M})|\mathcal{M}]$
$\displaystyle\geq\Pr\\{\mathcal{R}\cap(\mathcal{M}^{*}\setminus\mathcal{M})\neq\emptyset\\}\left(\max_{a\in\mathcal{R}\cap(\mathcal{M}^{*}\setminus\mathcal{M})}\Delta(\hat{a}|\mathcal{M})-\nu_{0}\right)\;[\text{w.
p.}\geq 1-\frac{\delta}{k}],$ (10)
$\displaystyle\geq\Pr\\{\mathcal{R}\cap(\mathcal{M}^{*}\setminus\mathcal{M})\neq\emptyset\\}\left(\frac{1}{|\mathcal{M}^{*}\setminus\mathcal{M}|}\sum_{a\in\mathcal{M}^{*}\setminus\mathcal{M}}\Delta(a|\mathcal{M})-\nu_{0}\right),$
$\displaystyle\geq\Pr\\{\mathcal{R}\cap(\mathcal{M}^{*}\setminus\mathcal{M})\neq\emptyset\\}\frac{1}{|\mathcal{M}^{*}\setminus\mathcal{M}|}\sum_{a\in\mathcal{M}^{*}\setminus\mathcal{M}}\left(\Delta(a|\mathcal{M})-\nu_{0}\right),$
$\displaystyle\geq(1-\epsilon)\frac{|\mathcal{M}^{*}\setminus\mathcal{M}|}{k}\frac{1}{|\mathcal{M}^{*}\setminus\mathcal{M}|}\sum_{a\in\mathcal{M}^{*}\setminus\mathcal{M}}(\Delta(a|\mathcal{M})-\nu_{0})\;\;[\text{using
Equation\leavevmode\nobreak\ \ref{eq:prob_intersect_2}}],$
$\displaystyle=\frac{1-\epsilon}{k}\sum_{a\in\mathcal{M}^{*}\setminus\mathcal{M}}(\Delta(a|\mathcal{M})-\nu_{0}).$
(11)

######  Theorem 3.5 (Correctness of ProtoBandit).

Suppose, given a problem instace $(\mathcal{S},\mathcal{T},\mathbf{q},d,k)$,
$\mathcal{M}^{*}$ is the optimal solution, and for a tolerance
$\epsilon\in(0,1)$, $\nu\in(0,1-e^{-1}-\epsilon)$, and acceptable error
probability $\delta\in(0,0.05)$, let $\mathcal{M}_{ALG}$ be the output by
ProtoBandit. Then,
$f(\mathcal{M}_{ALG})\geq\left(1-e^{-1}-\epsilon\right)f(\mathcal{M}^{*})-\nu$
holds in expectation with probability at least $1-\delta$, where $f(\cdot)$ is
defined in Equation 3.

######  Proof 3.6.

We use Lemma 3.3 to prove Theorem 3.5. Let
$\mathcal{M}^{i}=\\{a_{\text{out}}^{1},\cdots,a_{\text{out}}^{i}\\}$ be the
solution obtained by ProtoBandit at the end of $i$-th iteration, and
$\nu_{0}=\frac{\nu}{1-\epsilon-1/e}$. Then,

$\displaystyle\operatorname{\mathop{\mathbb{E}}}[f(\mathcal{M}^{i+1})-f(\mathcal{M}^{i})|\mathcal{M}^{i}]$
$\displaystyle=\operatorname{\mathop{\mathbb{E}}}[\Delta(a_{\text{out}}^{i+1}|\mathcal{M}^{i})|\mathcal{M}^{i}],$
$\displaystyle\geq\frac{1-\epsilon}{k}\sum_{a\in\mathcal{M}^{*}\setminus\mathcal{M}}\left(\Delta(a|\mathcal{M}^{i})-\nu_{0}\right)\text{[using
Lemma\leavevmode\nobreak\ \ref{lem:sample_prob}]},$
$\displaystyle\geq\frac{1-\epsilon}{k}\left(\Delta(\mathcal{M}^{*}|\mathcal{M}^{i})-\nu_{0}\right)\;[\text{by
submodularity of }f(\cdot)],$
$\displaystyle\geq\frac{1-\epsilon}{k}(f(\mathcal{M}^{*})-f(\mathcal{M}^{i})-\nu_{0}).$

We note, $f(\mathcal{M}^{i})$ is a random variable, due to the randomness
introduced by random sampling in the source set $\mathcal{S}$ to select
$\mathcal{R}$, and also by the MAB subroutine ABA. By taking expectation over
$f(\mathcal{M}^{i})$,

$\operatorname{\mathop{\mathbb{E}}}[f(\mathcal{M}^{i+1})-f(\mathcal{M}^{i})]\geq\frac{1-\epsilon}{k}\operatorname{\mathop{\mathbb{E}}}[f(\mathcal{M}^{*})-f(\mathcal{M}^{i})-\nu_{0}].$

Now, by induction,

$\displaystyle\operatorname{\mathop{\mathbb{E}}}[f(\mathcal{M}^{k})]$
$\displaystyle\geq\left(1-\left(\frac{1-\epsilon}{k}\right)^{k}\right)(f(\mathcal{M}^{*})-\nu_{0}),$
$\displaystyle\geq\left(1-\left(\exp{(-(1-\epsilon))}\right)\right)(f(\mathcal{M}^{*})-\nu_{0}),$
$\displaystyle\geq\left(1-e^{-1}-\epsilon\right)(f(\mathcal{M}^{*})-\nu_{0})=\left(1-e^{-1}-\epsilon\right)f(\mathcal{M}^{*})-\nu.$
(12)

The last step to prove Theorem 3.5 is proving the correctness of Equation 3.6.
We note, Equation 3.6 is valid only if Equation 11 holds for every iteration
from $1$ to $k$. Further, the correctness of Equation 11 is dependent on the
Equation 10. Now, we note, the arm $a_{\text{out}}$ returned by ABA may not be
$(\nu_{0},1)$-optimal with probability at most $\delta/k$, and Equation 10
fails to hold. However, the probability at in any of the $k$ iterations,
$a_{\text{out}}$ is not $(\nu_{0},1)$-optimal is at most
$\sum_{i=1}^{k}(\delta/k)=\delta$. Hence, Equation 3.6 holds with probability
at least $1-\delta$. This completes the proof of Theorem 3.5.

We now present the computational complexity result of ProtoBandit.

######  Theorem 3.7 (Upper bound on the number of similarity comparisons).

Given a problem instance $(\mathcal{S},\mathcal{T},\mathbf{q},d,k)$,
$\mathcal{M}^{*}$ is the optimal solution, and for a tolerance
$\epsilon\in(0,1)$, $\nu\in(0,1-e^{-1}-\epsilon)$, and acceptable error
probability $\delta\in(0,0.05)$, the number of similarity comparisons incurred
by ProtoBandit is in
$O\left(k|\mathcal{S}|\left(\frac{\nu}{1-\epsilon-1/e}\right)^{-2}\log\frac{1}{\epsilon}\log\frac{k}{\delta}\right)$.

######  Proof 3.8.

As Lemma 3.2 presents, treating $\mathcal{R}$ as the set of arms, and letting
$\nu_{0}=\nu/(1-e^{-1}-\epsilon)$, ABA incurs at most
$\frac{18|\mathcal{R}|}{\nu_{0}^{2}}\log\frac{1}{\delta}$ samples to identify
an $(\nu_{0},1)$-optimal arm from $\mathcal{R}$. Further, at iteration $i$,
there are $(i-1)$ elements in the set $\mathcal{M}$. Hence, for each sampled
element from $\mathcal{T}$, it takes $O(|\mathcal{M}|)$ or $i-1$ similarity
comparison to compute $D_{j}$ (given by Equation 2). Since we pass
$\frac{\delta}{k}$ as the allowed error probability for each call to ABA, the
total number of similarity comparisons is given by

$\displaystyle\sum_{i=1}^{k}(i-1)|\mathcal{R}|\times
18\nu_{0}^{-2}\log\frac{k}{\delta}=\sum_{i=1}^{k}(i-1)\frac{|\mathcal{S}|}{k}\log\frac{1}{\epsilon}\times
18\nu_{0}^{-2}\log\frac{k}{\delta}\;\
\left[\because|\mathcal{R}|=\frac{|\mathcal{S}|}{k}\log\frac{1}{\epsilon}\right]$
$\displaystyle<9k|\mathcal{S}|\left(\frac{\nu}{1-\epsilon-1/e}\right)^{-2}\log\frac{1}{\epsilon}\log\frac{k}{\delta}.$

It should be noted that the above approximation guarantee and computational
complexity analysis of ProtoBandit also holds when $\mathcal{T}=\mathcal{S}$,
i.e., the $k$-medoids clustering setting. Hence, ProtoBandit scales linearly
in $k|\mathcal{S}|$ for the $k$-medoids clustering problem.

###  3.5 Practical Considerations for Implementing ProtoBandit

It is important to note that the number of samples incurred by ABA (Hassidim
et al., 2020) is problem-independent, that is given any fixed-sized set of
arms $\mathcal{A}$, for a fixed $\epsilon,\delta\in(0,0.05)$ the number of
samples incurred will be the same (as given by Lemma 3.2). Hence, it is a non-
adaptive algorithm as the number of incurred samples does not depend on the
means of the arms. However, in practice, it is common to handle set of arms
where not all arms have their mean very close to each other. Hence, it is more
efficient to use adaptive algorithms like KL-LUCB (Kaufmann and
Kalyanakrishnan, 2013) that optimizes the number of samples by taking
advantage of the difference between mean of the arms. At each iteration, KL-
LUCB judicially selects two arms to sample and the algorithm stops if the
confidence-intervals of the arms crosses a threshold that is adaptively
determined by the algorithm. We note that despite KL-LUCB being more sample-
efficient than non-adaptive algorithms, complying with it still requires a
number of samples that might be too high for a medium-sized datasets. However,
in practice, seldom we encounter such pathological cases, and hence, we can
use a heuristic to make the algorithm incur lesser number of similarity
comparisons by stopping early. We make use of the early-stop heuristic inside
KL-LUCB for our experiments. The early stopping makes use of an optimistic
threshold that is easier to meet than the stopping criterion set by KL-LUCB.

##  4 Experiments

In this section, we show the benefit of ProtoBandit over SPOTgreedy
(Gurumoorthy et al., 2021) in obtaining a good trade-off between the number of
distance queries needed and the generalization performance of the obtained
prototypes.

We consider the MNIST (LeCun et al., 1998) dataset, which is a collection of
60K images of hand-written digits from 0 to 9, each of size $28\times 28$
pixels. There are two subsets mnist_train, and mnist_test consisting of 50K
and 10K images, respectively. Following Gurumoorthy et al. (2021), we sample
5K points uniformly at random from mnist_test and create the source set
$\mathcal{S}$. We create the target set $\mathcal{T}$ from mnist_test as
follows. First we note, the population of label $5$ is 5421, and it is the
least among all the labels. Therefore, to create a target set with skew
$\theta\%$ we take all the elements of label 5 from mnist_train and we
uniformly sample its remaining elements leading to a $\mathcal{T}$ of size
$(542100/\theta)$. Thus, for $\theta=10$, the target set $\mathcal{T}$ is
completely balanced, while for $\theta=100$ it consists elements only from
label 5. We conduct different experiments by varying
$\theta\in\\{10,20,50,70,100\\}$, and $k\in\\{100,200,500\\}$. For
ProtoBandit, we have used $\epsilon\in\\{0.2,0.4\\}$, and
$\nu\in\\{0.05,0.09\\}$. The results are averaged over ten randomized runs. We
use the Euclidean distance as the pair-wise dissimilarity measure $d$ between
points and normalize the distances to be in $[0,1]$.

In our experiments, we consider the setting in which both SPOTgreedy and
ProtoBandit select only one element at each iteration, i.e., $r=1$. We also
ensure that both ProtoBandit and SPOTgreedy compute the similarity comparisons
on the fly (i.e., they do not memorize the computed similarity comparisons
between data points).

The results are shown in Figure 1. For $\mathcal{T}$ with 10% skew (i.e.,
$\theta=10$), Figure 1(a) shows that ProtoBandit (for $\epsilon=0.2$) incurs
as little as $1/100$-th of the number of similarity comparisons made by
SPOTgreedy; however as Figure 1(a) shows the drop in objective value is within
only 2%.

We note that the number of distance computations for SPOTgreedy is minimum if
it is allowed to memorize all the $|\mathcal{S}\times\mathcal{T}|$ pair-wise
similarity values. Let us call this implementation of SPOTgreedy where it is
allowed to memorize all these values as SPOT_M. We also compare ProtoBandit
with SPOT_M. Figure 1(a) shows the number of incurred distance queries by the
proposed ProtoBandit is far less as compared to SPOT_M.

In practice, it is very common that value of the objective is not the final
thing that an experimenter seeks. A more sensible way to compare the results
is via the accuracy of the selected prototypes. Thanks to Lemma 3.1, we can
now inherit the barycentric projection method from the theory of optimal
transport. Following Gurumoorthy et al. (2021), the accuracy of the selected
prototypes is measured by using the barycentric mapping for both SPOTgreedy
and ProtoBandit. As depicted by Figure 1(c), ProtoBandit achieves a very close
accuracy compared to SPOTgreedy. Detailed comparisons between these two
algorithms for different values of skew ($\theta$), $\epsilon$, and $\nu$ are
in Appendix C.

In Appendix D, we present experiments on an additional dataset.

Figure 1: Comparison of SPOTgreedy and ProtoBandit (with $\epsilon=0.2$) on
$\mathcal{T}$ with skew = 10% in terms of (a) number of similarity
comparisons; (b) objective value; and (c) generalization performance. SPOT_M
in Figure 1(a) is an implementation of SPOTgreedy with all the
$|\mathcal{S}\times\mathcal{T}|$ pairwise-similarity values memorized. Our
proposed ProtoBandit with different $\nu$ values obtain good accuracy at much
lower number of similarity comparisons for SPOTgreedy. Compared to SPOT_M,
which memorizes all the $|\mathcal{S}\times\mathcal{T}|$ pair-wise similarity
values, we see the benefit of ProtoBandit (that never memorizes the similarity
values).

##  5 Conclusion and Future Work

We have proposed a novel unsupervised algorithm ProtoBandit for the prototype
selection problem, which offers a good trade-off between the number of
similarity comparisons needed and the quality of prototypes obtained. The key
idea is to generalize the popular clustering method PAM (Kaufman and
Rousseeuw, 1987) for the prototype selection problem. We introduce two
strategies for solving the BUILD step of generalized PAM: first, use of random
subset selection (to reduce the search space), and second, using multi-armed
bandits based identification of an approximately best candidate. We also
provide an approximation guarantee of the prototypical set obtained by the
proposed ProtoBandit algorithm. This allows the proposed algorithm ProtoBandit
to have an upper bound on the number of similarity comparisons that is
independent of target set size $|\mathcal{T}|$ and that scales linearly in
source set size $|\mathcal{S}|$. For the case of $\mathcal{T}=\mathcal{S}$, a
salient observation is that ProtoBandit approximates the BUILD solution of PAM
for the $k$-medoids clustering problem in $O(k|\mathcal{S}|)$ complexity.

Currently, our analysis relies critically on the application of (Hassidim et
al., 2020, Theorem 1) for deriving the bounds. It would be interesting to see
whether we can tighten the analysis for better bounds. Another research
direction would be to analyze the SWAP step of generalized PAM within our
framework in order to refine the prototypes obtained. Equally intriguing would
be to explore distributed MAB approaches (Mahadik et al., 2020; Li et al.,
2016) for the prototype selection problem.

## Acknowledgment

We would like to thank Karthik Gurumoorthy for his insightful comments,
discussion, and suggestions, especially on highlighting our bounds for the
$k$-medoids problem. We would also like to thank the reviewers for their
feedback.

## References

  * Badanidiyuru and Vondrák (2014) Ashwinkumar Badanidiyuru and Jan Vondrák.  Fast algorithms for maximizing submodular functions.  In _ACM-SIAM Symposium on Discrete Algorithms_ , SODA ’14, page 1497–1514. Society for Industrial and Applied Mathematics, 2014.
  * Berry and Fristedt (1985) Donald A. Berry and Bert Fristedt.  _Bandit Problems: Sequential Allocation of Experiments_.  Chapman & Hall, 1985.
  * Bien and Tibshirani (2011a) Jacob Bien and Robert Tibshirani.  Hierarchical clustering with prototypes via minimax linkage.  _Journal of the American Statistical Association_ , 106(495):1075–1084, 2011a.
  * Bien and Tibshirani (2011b) Jacob Bien and Robert Tibshirani.  Prototype selection for interpretable classification.  _Ann. Appl. Stat._ , 5(4):2403–2424, 2011b.
  * Crammer et al. (2002) Koby Crammer, Ran Gilad-Bachrach, Amir Navot, and Naftali Tishby.  Margin analysis of the lvq algorithm.  In _NeurIPS_ , 2002.
  * Even-Dar et al. (2002) Eyal Even-Dar, Shie Mannor, and Yishay Mansour.  PAC bounds for multi-armed bandit and Markov Decision Processes.  In _Proc. COLT 2002_ , pages 255–270. Springer, 2002.
  * Even-Dar et al. (2006) Eyal Even-Dar, Shie Mannor, and Yishay Mansour.  Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems.  _J. Mach. Learn. Res._ , 7:1079–1105, 2006.
  * Gurumoorthy et al. (2019) Karthik S. Gurumoorthy, Amit Dhurandhar, Guillermo Cecchi, and Charu Aggarwal.  Efficient data representation by selecting prototypes with importance weights.  In _IEEE ICDM_ , pages 260–269, 2019.
  * Gurumoorthy et al. (2021) Karthik S. Gurumoorthy, Pratik Jawanpuria, and Bamdev Mishra.  SPOT: A framework for selection of prototypes using optimal transport.  In _Applied Data Science Track - European Conference, ECML PKDD 2021_ , volume 12978 of _Lecture Notes in Computer Science_ , pages 535–551. Springer, 2021.
  * Hassidim et al. (2020) Avinatan Hassidim, Ron Kupfer, and Yaron Singer.  An optimal elimination algorithm for learning a best arm.  In _Advances in Neural Information Processing Systems_ , volume 33, pages 10788–10798. Curran Associates, Inc., 2020.
  * Jamieson et al. (2014) Kevin G. Jamieson, Matthew Malloy, Robert Nowak, and Sébastien Bubeck.  lil’ UCB : An optimal exploration algorithm for multi-armed bandits.  In _Proc. COLT 2014_ , pages 423–439, 2014.
  * Kalyanakrishnan et al. (2012) Shivaram Kalyanakrishnan, Ambuj Tewari, Peter Auer, and Peter Stone.  PAC subset selection in stochastic multi-armed bandits.  In _Proc. ICML 2012_ , pages 655–662. Omnipress, 2012.
  * Karnin et al. (2013) Zohar Karnin, Tomer Koren, and Oren Somekh.  Almost optimal exploration in multi-armed bandits.  In _Proc. ICML 2013_ , volume 28, pages 1238–1246. PMLR, 2013.
  * Kaufman and Rousseeuw (1987) Leonard Kaufman and Peter J. Rousseeuw.  Clustering by means of medoids.  _Statistical Data Analysis Based on the $L1$ Norm and Related Methods_, pages 405–416, 1987.
  * Kaufman and Rousseeuw (1990) Leonard Kaufman and Peter J. Rousseeuw.  _Partitioning Around Medoids (Program PAM)_ , chapter 2, pages 68–125.  John Wiley & Sons, Ltd, 1990.  ISBN 9780470316801.
  * Kaufman and Rousseeuw (2009) Leonard Kaufman and Peter J. Rousseeuw.  _Finding Groups in Data: An Introduction to Cluster Analysis_.  John Wiley & Sons, Inc., 2009.
  * Kaufmann and Kalyanakrishnan (2013) Emilie Kaufmann and Shivaram Kalyanakrishnan.  Information complexity in bandit subset selection.  In _Proc. COLT 2013_ , volume 30, pages 228–251. JMLR, 2013.
  * Kim et al. (2014) Been Kim, Cynthia Rudin, and Julie Shah.  The Bayesian case model: A generative approach for case-based reasoning and prototype classification.  In _NeurIPS_ , 2014.
  * Kim et al. (2016) Been Kim, Rajiv Khanna, and Oluwasanmi O Koyejo.  Examples are not enough, learn to criticize! criticism for interpretability.  In _NeurIPS_ , 2016.
  * Koh and Liang (2017) Pang Wei Koh and Percy Liang.  Understanding black-box predictions via influence functions.  In _ICML_ , 2017.
  * Krizhevsky (2009) Alex Krizhevsky.  Learning multiple layers of features from tiny images.  Technical report, Univ. Toronto, 2009.
  * Leahy (2013) James Leahy.  Targeted consumer involvement: An integral part of successful new product development.  _Research-Technology Management_ , 56, 07 2013.
  * LeCun et al. (1998) Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner.  Gradient-based learning applied to document recognition.  _Proceedings of the IEEE_ , 86(11):2278–2324, November 1998.
  * Leskovec et al. (2020) Jure Leskovec, Anand Rajaraman, and Jeffrey D. Ullman.  _Mining of Massive Datasets_.  Cambridge University Press, 2020.
  * Li et al. (2016) Shuai Li, Alexandros Karatzoglou, and Claudio Gentile.  Collaborative filtering bandits.  In _Proceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval_ , pages 539–548, 2016.
  * Linardatos et al. (2021) Pantelis Linardatos, Vasilis Papastefanopoulos, and Sotiris Kotsiantis.  Explainable ai: A review of machine learning interpretability methods.  _Entropy_ , 23(1), 2021.  ISSN 1099-4300.
  * Mahadik et al. (2020) Kanak Mahadik, Qingyun Wu, Shuai Li, and Amit Sabne.  Fast distributed bandits for online recommendation systems.  In _Proceedings of the 34th ACM International Conference on Supercomputing_ , ICS ’20. Association for Computing Machinery, 2020.  ISBN 9781450379830.
  * Mannor and Tsitsiklis (2004) Shie Mannor and John N. Tsitsiklis.  The sample complexity of exploration in the multi-armed bandit problem.  _JMLR_ , 5:623–648, 2004.
  * Minoux (1978) Michel Minoux.  Accelerated greedy algorithms for maximizing submodular set functions.  In _Optimization techniques_ , pages 234–243. Springer, 1978.
  * Mirzasoleiman et al. (2015) Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, Amin Karbasi, Jan Vondrák, and Andreas Krause.  Lazier than lazy greedy.  In _Twenty-Ninth AAAI Conference on Artificial Intelligence_ , AAAI’15, page 1812–1818. AAAI Press, 2015.
  * Ng and Han (2002) R.T. Ng and Jiawei Han.  Clarans: a method for clustering objects for spatial data mining.  _IEEE Transactions on Knowledge and Data Engineering_ , 14(5):1003–1016, 2002.
  * Olvera-López et al. (2008) J Arturo Olvera-López, J Ariel Carrasco-Ochoa, and J Fco Martínez-Trinidad.  Prototype selection via prototype relevance.  In _Progress in Pattern Recognition, Image Analysis and Applications_ , pages 153–160. Springer Berlin Heidelberg, 2008.
  * Roy Chaudhuri and Kalyanakrishnan (2019) Arghya Roy Chaudhuri and Shivaram Kalyanakrishnan.  PAC identification of many good arms in stochastic multi-armed bandits.  In _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 991–1000. PMLR, 09–15 Jun 2019.
  * Schubert and Rousseeuw (2019) Erich Schubert and Peter J. Rousseeuw.  Faster k-Medoids clustering: Improving the PAM, CLARA, and CLARANS algorithms.  In _International Conference on Similarity Search and Applications_ , 2019.
  * Suyal and Singh (2021) Himanshu Suyal and Avtar Singh.  _Improving multi-label classification in prototype selection scenario_ , chapter 6, pages 103–119.  John Wiley & Sons, Ltd, 2021.  ISBN 9781119818717.
  * Tiwari et al. (2020) Mo Tiwari, Martin J Zhang, James Mayclin, Sebastian Thrun, Chris Piech, and Ilan Shomorony.  Banditpam: Almost linear time k-medoids clustering via multi-armed bandits.  In _Advances in Neural Information Processing Systems_ , 2020.
  * Wei et al. (2014) Kai Wei, Rishabh Iyer, and Jeff Bilmes.  Fast multi-stage submodular maximization.  In _Proceedings of the 31st International Conference on International Conference on Machine Learning - Volume 32_ , ICML’14, page II–1494–II–1502. JMLR.org, 2014.
  * Wei et al. (2015) Kai Wei, Rishabh Iyer, and Jeff Bilmes.  Submodularity in data subset selection and active learning.  In _ICML_ , 2015.
  * Weiser (1982) Mark Weiser.  Programmers use slices when debugging.  _Comm. ACM_ , 25(7):446–452, 1982.
  * Wohlhart et al. (2013) Paul Wohlhart, Martin Kostinger, Michael Donoser, Peter M Roth, and Horst Bischof.  Optimizing 1-nearest prototype classifiers.  In _CVPR_ , 2013.
  * Yeh et al. (2018) Chih-Kuan Yeh, Joon Kim, Ian En-Hsu Yen, and Pradeep K Ravikumar.  Representer point selection for explaining deep neural networks.  In _NeurIPS_ , 2018.
  * Zukhba (2010) A. V. Zukhba.  NP-completeness of the problem of prototype selection in the nearest neighbor method.  _Pattern Recognition and Image Analysis_ , 20:484–494, 12 2010.

##  Appendix A Generalized PAM Algorithm for Prototype Selection

  * •

As defined in Equation 2, let $D_{j}$ be the dissimilarity between a point $j$
and the closest object in $\mathcal{M}$, i.e.

$D_{j}=\min_{i\in\mathcal{M}}\\{d(j,i)\\}.$ (13)

  * •

Let, $E_{j}$ be the be the dissimilarity between a point $j$ and the _second_
closest object in $\mathcal{S}$, i.e.,
$E_{j}=\min_{s\in\mathcal{S}\setminus\\{\operatorname*{arg\,min}_{c\in\mathcal{M}}\\{d(j,c)\\}\\}}\\{d(j,s)\\}$.

Algorithm 4 Generalized PAM algorithm for prototype selection

Input :

Problem instance given by $(\mathcal{S},\mathcal{T},\mathbf{q},d,k)$, and a
pair of positive integers $r,l\in\\{1,\cdots,k\\}$.

Output :

A set $\mathcal{M}$, such that $\mathcal{M}=k$

Initialization: For each $j\in\mathcal{T}$, set $D_{j}=\infty$.

begin BUILD Step:

In this step we apply greedy strategy to choose an initial set of $k$ points,
in other words, an initial set of medoids. $\mathcal{M}=\emptyset$ while
_$|\mathcal{M}| <k$_ do

Define vector $g$ with entries
$g_{i}=\sum_{j\in\mathcal{T}}q_{j}\max\\{D_{j}-d(j,i),0\\},\;\forall
i\in\mathcal{S}\setminus\mathcal{M}.$ (14) if  _$\forall
i\in\mathcal{S},g_{i}=0$_ then // no meaningful medoid to add

$Q\stackrel{{\scriptstyle\mathclap{\mbox{\tiny{def}}}}}{{=}}$ Choose $r$
elements from $\mathcal{S}\setminus\mathcal{M}$ at random

else

$Q\stackrel{{\scriptstyle\mathclap{\mbox{\tiny{def}}}}}{{=}}$ Set of indices
of top $r$ largest _non-zero_ elements in
$g=\\{g_{i}\\}_{i=1}^{|\\{\mathcal{S}\setminus\mathcal{M}\\}|}$

end if

$\mathcal{M}=\mathcal{M}\cup Q$ Update $D_{j}$, and $E_{j}$ for all
$j\in\mathcal{T}$.

end while

end

begin SWAP Step: or refinement step

for  _$(i,h)\in\mathcal{S}\times\\{\mathcal{S}\setminus\mathcal{M}\\}$_ do

$\text{compute}\;K_{jih}=\begin{cases}\min\\{d(j,h)-D_{j},0)\\}\;\forall
j\in\mathcal{T},\text{where}\;d(j,i)>D_{j}\\\
\min\\{d(j,h)-E_{j},0)\\}\;\forall
j\in\mathcal{T},\text{where}\;d(j,i)=D_{j}\end{cases}$
$T_{ih}=\sum_{j\in\mathcal{T}}q_{j}K_{jih}$

end for

For $l$ different $h\in\\{\mathcal{S}\setminus\mathcal{M}\\}$, select pairs
$(i,h)\in\mathcal{S}\times\\{\mathcal{S}\setminus\mathcal{M}\\}$ that minimize
$T_{ih}$.

end

if  _$T_{ih} <0$_ then

Swap $i$ with $h$.

else // value of the objective cannot be decreased

return $\mathcal{M}$

end if

##  Appendix B Proof of Lemma 3.1

SPOTgreedy at its core chooses medoids by solving the following optimisation
problem given by Equation 3. Assuming $f(\emptyset)=0$, defined in Equation 3,
and noting that due to $d:\mathcal{T}\times\mathcal{S}\mapsto[0,1]$,
$\beta_{i}$ (in Algorithm 5) lies within $[0,1]$ we restate SPOTgreedy
(Gurumoorthy et al., 2021) in Algorithm 5.

Algorithm 5 SPOTgreedy (Gurumoorthy et al., 2021)

Input :

Problem instance given by $(\mathcal{S},\mathcal{T},\mathbf{q},d,k)$, and a
positive integer $r\leq k$.

Output :

A set $\mathcal{M}$, such that $|\mathcal{M}|=k$

while  _$|\mathcal{M}| <k$_ do

Define gain vector $\beta$ with entries
$\beta_{i}=f(\mathcal{M}\cup\\{i\\})-f(\mathcal{M}),\forall
i\in\mathcal{S}\setminus\mathcal{M},$ (15) where
$f:\mathcal{S}\mapsto[0,+\infty)$ is defined in Equation 3. if  _$\forall
i\in\mathcal{S},\beta_{i}=0$_ then // no potential prototype to add

$Q\stackrel{{\scriptstyle\mathclap{\mbox{\tiny{def}}}}}{{=}}$ Choose $r$
elements from $\mathcal{S}\setminus\mathcal{M}$ at random

else

$Q\stackrel{{\scriptstyle\mathclap{\mbox{\tiny{def}}}}}{{=}}$ Set of indices
of top $r$ largest _non-zero_ elements in
$\beta=\\{\beta_{i}\\}_{i=1}^{|\mathcal{S}\setminus\mathcal{M}|}$

end if

$\mathcal{M}=\mathcal{M}\cup Q$

end while

######  Proof B.1.

Let, at the beginning of some iteration $t$, the set of points already chosen
by SPOTgreedy (Algorithm 5) and Algorithm 1 be identical, and let it be
$\mathcal{M}_{t}$. We note, such $t$ exists; for example, at beginning of the
very first iteration ($t=1$), $\mathcal{M}_{t}=\\{\emptyset\\}$. Now, to prove
the lemma, it will suffice to prove that, $g_{i}$ on the LHS of Equation 1 is
identical to $\beta_{i}$ on the LHS of Equation 15.

We note, for all $i\in\mathcal{S}\setminus\mathcal{M}$, we have

$\displaystyle\beta_{i}$
$\displaystyle=f(\mathcal{M}_{t}\cup\\{i\\})-f(\mathcal{M}_{t})$
$\displaystyle=\sum\limits_{j\in\mathcal{T}}q_{j}\max\limits_{i\in\mathcal{M}_{t}\cup\\{i\\}}Z_{ji}-\sum\limits_{j\in\mathcal{T}}q_{j}\max\limits_{i\in\mathcal{M}_{t}}Z_{ji}$
$\displaystyle[\text{using Equation\leavevmode\nobreak\ \ref{eq:spot_eq10}}],$
$\displaystyle=\sum\limits_{j\in\mathcal{T}}q_{j}\max\limits_{i\in\mathcal{M}_{t}\cup\\{i\\}}(C-d(j,i))-\sum\limits_{j\in\mathcal{T}}q_{j}\max\limits_{i\in\mathcal{M}_{t}}(C-d(j,i))$
$\displaystyle[\text{using Equation\leavevmode\nobreak\ \ref{eq:spot_sim}}],$
$\displaystyle=\sum\limits_{j\in\mathcal{T}}q_{j}\left(\max\limits_{i\in\mathcal{M}_{t}\cup\\{i\\}}(C-d(j,i))-\max\limits_{i\in\mathcal{M}_{t}}(C-d(j,i))\right),$
[changing difference of sums to sum of differences],
$\displaystyle=\sum\limits_{j\in\mathcal{T}}q_{j}\left(C+\max\limits_{i\in\mathcal{M}_{t}\cup\\{i\\}}(-d(j,i))-C-\max\limits_{i\in\mathcal{M}_{t}}(-d(j,i))\right)$
$\displaystyle[\because\text{$C$ is a constant}],$
$\displaystyle=\sum\limits_{j\in\mathcal{T}}q_{j}\left(\max\limits_{i\in\mathcal{M}_{t}\cup\\{i\\}}(-d(j,i))-\max\limits_{i\in\mathcal{M}_{t}}(-d(j,i))\right)$
$\displaystyle[\because\text{$C$ is a constant}],$
$\displaystyle=\sum\limits_{j\in\mathcal{T}}q_{j}\left(-\min\limits_{i\in\mathcal{M}_{t}\cup\\{i\\}}(d(j,i))+\min\limits_{i\in\mathcal{M}_{t}}(d(j,i))\right)$
[exchanging order of $\max$ and ‘$-$’ sign],
$\displaystyle=\sum\limits_{j\in\mathcal{T}}q_{j}\left(\min\limits_{i\in\mathcal{M}_{t}}d(j,i)-\min\limits_{i\in\mathcal{M}_{t}\cup\\{i\\}}d(j,i)\right)$
$\displaystyle[\text{rearranging the terms}],$
$\displaystyle=\sum\limits_{j\in\mathcal{T}}q_{j}\left(D_{j}-\min\limits_{i\in\mathcal{M}_{t}\cup\\{i\\}}d(j,i)\right)$
[using $\mathcal{M}=\mathcal{M}_{t}$ at Equation 2],
$\displaystyle=\begin{dcases}\sum\limits_{j\in\mathcal{T}}q_{j}\left(D_{j}-d(j,i)\right)&\text{if}\;D_{j}>d(j,i),\\\
0&\text{otherwise,}\end{dcases}$
$\displaystyle=\sum\limits_{j\in\mathcal{T}}q_{j}\max\left(D_{j}-d(j,i),0\right),$
$\displaystyle=g_{i}$ $\displaystyle[\text{using Equation\leavevmode\nobreak\
\ref{eq:gain_genpam_build} in }]$ Algorithm 1].

Therefore, for any given problem instance
$(\mathcal{S},\mathcal{T},\mathbf{q},d,k)$, for the same value of the input
parameter $r$, the output of SPOTgreedy is identical to the output of
Algorithm 1.

##  Appendix C Additional Experiments on MNIST Dataset

###  C.1 Comparison of performance of ProtoBandit (with $\epsilon=0.2$)
against SPOTgreedy

Figure 2: Comparison of number of similarity comparisons, objective value, and
achieved accuracy by SPOTgreedy and ProtoBandit (with $\epsilon=0.2$) on
Target with skew = 20%. SPOT_M is an implementation of SPOTgreedy with all the
$|\mathcal{S}\times\mathcal{T}|$ pairwise-similarity values memorised. For
details, see Section 4.

Figure 3: Comparison of number of similarity comparisons, objective value, and
achieved accuracy by SPOTgreedy and ProtoBandit (with $\epsilon=0.2$) on
Target with skew = 50%. SPOT_M is an implementation of SPOTgreedy with all the
$|\mathcal{S}\times\mathcal{T}|$ pairwise-similarity values memorised. For
details, see Section 4.

Figure 4: Comparison of number of similarity comparisons, objective value, and
achieved accuracy by SPOTgreedy and ProtoBandit (with $\epsilon=0.2$) on
Target with skew = 70%. SPOT_M is an implementation of SPOTgreedy with all the
$|\mathcal{S}\times\mathcal{T}|$ pairwise-similarity values memorised. For
details, see Section 4.

Figure 5: Comparison of number of similarity comparisons, objective value, and
achieved accuracy by SPOTgreedy and ProtoBandit (with $\epsilon=0.2$) on
Target with skew = 100%. SPOT_M is an implementation of SPOTgreedy with all
the $|\mathcal{S}\times\mathcal{T}|$ pairwise-similarity values memorised. For
details, see Section 4.

###  C.2 Comparison of performance of ProtoBandit (with $\epsilon=0.4$)
against SPOTgreedy and SPOT_M

Figure 6: Comparison of number of similarity comparisons, objective value, and
achieved accuracy by SPOTgreedy and ProtoBandit (with $\epsilon=0.4$) on
Target with skew = 10%. SPOT_M is an implementation of SPOTgreedy with all the
$|\mathcal{S}\times\mathcal{T}|$ pairwise-similarity values memorised. For
details, see Section 4.

Figure 7: Comparison of number of similarity comparisons, objective value, and
achieved accuracy by SPOTgreedy and ProtoBandit (with $\epsilon=0.4$) on
Target with skew = 20%. SPOT_M is an implementation of SPOTgreedy with all the
$|\mathcal{S}\times\mathcal{T}|$ pairwise-similarity values memorised. For
details, see Section 4.

Figure 8: Comparison of number of similarity comparisons, objective value, and
achieved accuracy by SPOTgreedy and ProtoBandit (with $\epsilon=0.4$) on
Target with skew = 50%. SPOT_M is an implementation of SPOTgreedy with all the
$|\mathcal{S}\times\mathcal{T}|$ pairwise-similarity values memorised. For
details, see Section 4.

Figure 9: Comparison of number of similarity comparisons, objective value, and
achieved accuracy by SPOTgreedy and ProtoBandit (with $\epsilon=0.4$) on
Target with skew = 70%. SPOT_M is an implementation of SPOTgreedy with all the
$|\mathcal{S}\times\mathcal{T}|$ pairwise-similarity values memorised. For
details, see Section 4.

Figure 10: Comparison of number of similarity comparisons, objective value,
and achieved accuracy by SPOTgreedy and ProtoBandit (with $\epsilon=0.4$) on
Target with skew = 100%. SPOT_M is an implementation of SPOTgreedy with all
the $|\mathcal{S}\times\mathcal{T}|$ pairwise-similarity values memorised. For
details, see Section 4.

##  Appendix D Experiment on CIFAR-10 Dataset

We run experiments on the CIFAR-10 dataset (Krizhevsky, 2009). The dataset
consists 60000 color images from $10$classes. Each image is of size $32\times
32$ pixels, with $6000$ images per class. The dataset is split into training
and test sets consisting of $50\,000$ and $10\,000$ images, respectively. We
have assumed the training and the test set as the target and source sets,
respectively. For the sake of better representation, we convert these images
into gray-scale followed by PCA and choosing the first $161$ dimensions to
cover the $95\%$ variance. Just like the MNIST data, here too we use the
Euclidean distance (normalized within [0,1]) as the pair-wise dissimilarity
measure $d$..

We observe that ProtoBandit achieves a very close objective value as compared
to SPOTgreedy, but incurs only 1/100-th of the number of similarity queries.

Figure 11: Comparison of SPOTgreedy and ProtoBandit (with $\epsilon=0.2$) on
$\mathcal{T}$ on the CIFAR-10 dataset in terms of (a) number of similarity
comparisons; (b) objective value; and (c) generalization performance. SPOT_M
in Figure 11(a) is an implementation of SPOTgreedy with all the
$|\mathcal{S}\times\mathcal{T}|$ pairwise-similarity values memorized. Our
proposed ProtoBandit with different $\nu$ values obtain good accuracy at much
lower number of similarity comparisons for SPOTgreedy. Compared to SPOT_M,
which memorizes all the $|\mathcal{S}\times\mathcal{T}|$ pair-wise similarity
values, we see the benefit of ProtoBandit (that never memorizes the similarity
values).


# Polynomial Integrality Gap of Flow LP for Directed Steiner Tree

Shi Li 111The work is supported in part by NSF grant CCF-1844890.
Dept. of Comp. Sci. and Eng.
University at Buffalo, USA
<EMAIL_ADDRESS>Bundit Laekhanukit 222This work is supported by Science and
Technology Innovation 2030 –“New Generation of Artificial Intelligence” Major
Project No.(2018AAA0100903), NSFC grant 61932002, Program for Innovative
Research Team of Shanghai University of Finance and Economics (IRTSHUFE) and
the Fundamental Research Funds for the Central Universities. Bundit
Laekhanukit is also supported by the national 1000-talent award by the Chinese
government.
ITCS,
SUFE, China.
<EMAIL_ADDRESS>
###### Abstract

In the Directed Steiner Tree (DST) problem, we are given a directed graph
$G=(V,E)$ on $n$ vertices with edge-costs $c\in{\mathbb{R}}_{\geq 0}^{E}$, a
root vertex $r$, and a set $K$ of $k$ terminals. The goal is to find a
minimum-cost subgraph of $G$ that contains a path from $r$ to every terminal
$t\in K$. DST has been a notorious problem for decades as there is a large gap
between the best-known polynomial-time approximation ratio of
$O(k^{\epsilon})$ for any constant $\epsilon>0$, and the best quasi-
polynomial-time approximation ratio of $O\left(\frac{\log^{2}k}{\log\log
k}\right)$.

Towards understanding this gap, we study the integrality gap of the standard
flow LP relaxation for the problem. We show that the LP has an integrality gap
polynomial in $n$. Previously, the integrality gap LP is only known to be
$\Omega\left(\frac{\log^{2}n}{\log\log n}\right)$ [Halperin et al., SODA’03 &
SIAM J. Comput.] and $\Omega(\sqrt{k})$ [Zosin-Khuller, SODA’02] in some
instance with $\sqrt{k}=O\left(\frac{\log n}{\log\log n}\right)$. Our result
gives the first known lower bound on the integrality gap of this standard LP
that is polynomial in $n$, the number of vertices. Consequently, we rule out
the possibility of developing a poly-logarithmic approximation algorithm for
the problem based on the flow LP relaxation.

##  1 Introduction

Network design problems play an important role in the area of combinatorial
optimization both in theory and practice. Two most famous problems in the area
are the Minimum Spanning Tree problem, and its analogue in directed graphs,
the Minimum-Cost Arborescence problem. They play a fundamental role in
illustrating the powerful concept of greedy algorithms in standard textbooks.
While the two textbook problems ask to find a tree or an arborescence that
spans all the vertices, in most applications, it is more natural to connect
only a subset of vertices, called terminals, which models clients in the
network, while using some non-terminals or less-important nodes, called
Steiner vertices, as relay. This motivates the Steiner tree problems on both
undirected and directed graphs, which have become the central focus in the
area of network design for several decades. Since the problems are known to be
NP-hard, the algorithmic development has mainly been on finding good
approximation algorithms.

In contrast to the Minimum Steiner Tree problem (on undirected graphs), the
complexity status of the Directed Steiner Tree (DST) problem is much less-
understood. Formally, in the Directed Steiner Tree problem, we are given a
directed graph $G=(V,E)$ on $n=|V|$ vertices, with edge costs
$c\in{\mathbb{R}}_{\geq 0}^{E}$, a root $r\in V$ and a set $K\subseteq V$ of
$k=|K|$ terminals. The goal of the problem is to find a minimum cost subgraph
$T$ of $G$ that contains a path from $r$ to $t$, for every terminal $t\in K$.
By minimality, we may assume WLOG that the solution subgraph $T$ is a tree
(more precisely, an out-arborescence) rooted at $r$.

The best known polynomial-time approximation ratio for the problem is only
$O(k^{\epsilon})$ with a running time of $n^{O(1/\epsilon)}$ for any constant
$\epsilon>0$ [Zel97, CCC+99]. With quasi-polynomial time algorithms, one can
achieve an approximation ratio of $O\left(\frac{\log^{2}k}{\log\log k}\right)$
[GLL19, GN20]. It is known from the work of Halperin and Krauthgamer [HK03]
that unless $\text{NP}\subseteq\text{ZPTIME}(n^{{\mathrm{poly}}\log(n)})$,
there is no polynomial time $O(\log^{2-\epsilon}k)$-approximation for the
problem for any constant $\epsilon>0$. The long-standing open question on DST
is whether a poly-logarithmic approximation for the problem can be achieved in
polynomial time.

In this paper, we study the integrality gap of the standard flow-based
relaxation of DST, in the hope to shed some light on the approximability of
DST under polynomial-time algorithms. The interesting part on the flow LP is
that while its integrality gap is known to be lower bounded by
$\Omega(\sqrt{k})$ [ZK02], the parameter $k$ (i.e., the number of terminals)
in the construction is only $O\left(\frac{\log^{2}n}{\log^{2}\log n}\right)$.
Thus, the lower bound given by the instance of [ZK02] is only
$\Omega\left(\frac{\log n}{\log\log n}\right)$. Indeed, the hardness result of
[HKK+07] implies an integrality gap lower bound of
$\Omega\left(\frac{\log^{2}n}{\log\log n}\right)$, which is better than that
of [ZK02] when we concern the dependence on $n$.

###  1.1 Our Results

In this paper, we show that the integrality gap of the flow LP is indeed lower
bounded by $\Omega(n^{\delta})$ for some absolute constant $\delta\in(0,1)$.
Our construction resemblances the previous one by Zosin and Khuller [ZK02], in
the sense that our instance also has a 5-level structure. In the instance of
[ZK02], each vertex in the graph corresponds to some subset of $K$ (the set of
terminals) of size roughly $\sqrt{k}$. This leads to an exponential dependence
of $n$ on $k$. In our construction, both the terminals and Steiner vertices
correspond to subsets of some ground set, so $n$ and $k$ are polynomially
related. Crucially, we can still prove the useful properties that are needed
to show the integrality gap. The formal statement of our result is stated in
Theorem 1, after we formally defined the flow LP relaxation (FLP). As a
consequence of our result, we rule out poly-logarithmic approximation
algorithms for DST based on the flow LP.

###  1.2 Related Work

Compared to DST, the Minimum Steiner Tree problem (in undirected graphs) is
better-understood. Simply computing the minimum spanning tree over the metric
closure of the terminals leads to a 2-approximation algorithm for the problem.
The current best approximation ratio for the problem is $\ln(4)+\epsilon<1.39$
due to Byrka et al. [BGRS10]. On the negative side, the problem is known to be
APX-hard [BP89, CC08].

The DST problem has been a subject of studies for decades. The first non-
trivial approximation result on this problem is due to Zelikovsky [Zel97],
which gives an $O(k^{\epsilon})$-approximation in $n^{O(1/\epsilon)}$-time for
any constant $\epsilon>0$, which is designed for directed acyclic graphs. The
result is later extended in [CCC+99] to general graphs. Moreover, the
$\epsilon$ in [CCC+99] can be set to $1/\log k$, leading to an
$O(\log^{3}k)$-approximation algorithm for DST in $n^{O(\log k)}$ time; this
is the first poly-logarithmic approximation algorithm for the problem in
quasi-polynomial time. A similar result was obtained by Kortsarz and Peleg
[KP99]. The approximation ratio in the quasi-polynomial-time regime has been
improved to $O\left(\frac{\log^{2}k}{\log\log k}\right)$ in [GLL19, GN20].
Grandoni et al. [GLL19] also showed that this is the best approximation
guarantee for any quasi-polynomial-time algorithm unless
$\mathrm{NP}\subseteq\bigcup_{c>0}\mathrm{BPTIME}(2^{n^{c}})$ or the
Projection Game Conjecture [Mos15] is false.

There have been quite a few studies devoted to understand the power of LP/SDP
hierarchy for the problem. It was shown in [Rot11] and [FKK+14] that the
integrality gap of some basic LP relaxations can be brought down to
$O(L\log^{2}k)$ for DST on $L$-level graphs, if we lift them by $O(L)$ levels
using some well-known LP/SDP hierarchies such as Sherali-Adams,
Lovász–Schrijver and Lasserre hierarchies. The quasi-polynomial time
$O\left(\frac{\log^{2}k}{\log\log k}\right)$-approximation of [GLL19] is also
based on the Sherali-Adams hierarchy.

##  2 Flow LP Relaxation for Directed Steiner Tree

The standard flow LP relaxation is given in (FLP). In the correspondent
integer program, for every $e\in E$, we have a variable $x_{e}$ indicating
whether $e$ is in the output tree $T$. For every terminal $t\in K$, we let
${\mathcal{P}}_{t}$ be the set of simple paths in $G$ from $r$ to $t$. Then
for every $t\in K,P\in{\mathcal{P}}_{t}$, we have a variable $f^{t}_{P}$
indicating if the $r\rightarrow t$ path in $T$ is $P$. In the LP, we relax the
0/1-constraints on variables to non-negativity constraints (3) and (4).

$\displaystyle\min$ $\displaystyle\sum_{e\in E}c_{e}x_{e}$ (FLP) s.t.
$\displaystyle\sum_{P\in{\mathcal{P}}_{t}}f^{t}_{P}$ $\displaystyle=1$
$\displaystyle\forall t\in K$ (1)
$\displaystyle\sum_{P\in{\mathcal{P}}_{t}:e\in P}f^{t}_{P}$ $\displaystyle\leq
x_{e}$ $\displaystyle\forall e\in E,t\in K$ (2) $\displaystyle x_{e}$
$\displaystyle\geq 0$ $\displaystyle\forall e\in E$ (3) $\displaystyle
f^{t}_{P}$ $\displaystyle\geq 0$ $\displaystyle\forall t\in
K,P\in{\mathcal{P}}_{t}$ (4)

Equation 1 says that exactly one $r\to t$ path should exist in $T$, for every
$t\in K$. Equation 2 says that if the $r\to t$ path $P$ in the output tree $T$
uses an edge $e$, then $e$ must be in $T$. So, the constraints are valid. In
the LP, we can view $f^{t}_{P}$ as the amount of flow sending from $r$ to $t$
using a path $P$. Then Equation 1 and Equation 2 together are equivalent to
saying that the maximum flow from $r$ to $t$ in the graph $G$ with capacities
$(x_{e})_{e\in E}$ has value at least $1$, for every terminal $t\in K$. For
this reason, we call (FLP) the flow LP. It can be solved efficiently despite
the fact that it has exponential number of variables since the requirement for
every $t$ is just a maximum-flow problem, which is equivalent to a polynomial-
sized LP.

Zosin and Khuller [ZK02] showed that (FLP) has an integrality gap of
$\Omega(\sqrt{k})$, for a family of instances with $\sqrt{k}=O\left(\frac{\log
n}{\log\log n}\right)$. Therefore, the dependence of the integrality gap on
$k$ is only logarithmic. In this paper, we show the following theorem:

######  Theorem 1.

The integrality gap of (FLP) is $\Omega(n^{\delta})$ for some absolute
constant $\delta\in(0,1)$.

#### Organization.

The remainder of this paper is organized as follows. We first introduce the
5-level instance of Zosin and Khuller [ZK02] in Section 3, where we give some
necessary properties to prove an integrality gap. We give our construction
satisfying the properties in Section 4, which finishes the proof of Theorem 1.

##  3 Zosin-Khuller Type Gap Instance

In this section, we define the Zosin-Khuller type gap instance for the flow LP
of the directed Steiner tree problem. To define such an instance, we need to
specify the following objects.

  1. (P1)

$H=({\mathcal{A}}\uplus{\mathcal{B}},E_{H})$ is a bipartite graph with
$|{\mathcal{A}}|\leq|{\mathcal{B}}|$, where all vertices in ${\mathcal{A}}$
have the same degree $d$ and all vertices in ${\mathcal{B}}$ have the same
degree $d^{\prime}$.

  2. (P2)

$K$ is a set of $k$ terminals, and $\\{M_{t}\\}_{t\in K}$ is a partition of
$E_{H}$ into $k$ matchings of size $s$ each, one for each terminal $t\in K$.
Therefore, we have $s\leq|{\mathcal{A}}|\leq|{\mathcal{B}}|,k\geq d\geq
d^{\prime}$ and $sk=d|{\mathcal{A}}|=d^{\prime}|{\mathcal{B}}|=|E_{H}|$. For
convenience, we also treat each terminal $t\in K$ as a color and say all the
edges in $M_{t}$ have color $t$. So, the partition $\\{M_{t}\\}_{t\in K}$
gives a $k$-coloring of $E_{H}$.

  3. (P3)

For every vertex $v\in{\mathcal{B}}$, $K_{v}:={\left\\{t\in K:v\text{ is
matched in }M_{t}\right\\}}$ is the set of colors of the incident edges of
$v$. Notice that, for every $v\in{\mathcal{B}}$, we have $|K_{v}|=d^{\prime}$,
and that $K_{v}$’s are determined by (P1) and (P2).

Given the above objects, the Zosin-Khuller type gap instance is defined over a
$5$-level directed graph $G=(V=V_{0}\uplus V_{1}\uplus V_{2}\uplus V_{3}\uplus
V_{4},E=E_{1}\uplus E_{2}\uplus E_{3}\uplus E_{4})$, where edges in $E_{i}$,
$i\in\\{1,2,3,4\\}$ go from $V_{i-1}$ to $V_{i}$. The vertices and edges in
$G$ are defined as follows. (See Figure 1 for an illustration of the
instance.)

  * •

$V_{0}=\\{r\\},V_{1}={\mathcal{A}},V_{2}={\mathcal{B}},V_{3}={\mathcal{B}}^{\prime}$
and $V_{4}=K$, where ${\mathcal{B}}^{\prime}$ is a new set with the same
cardinality as ${\mathcal{B}}$. Let
$\pi:{\mathcal{B}}\to{\mathcal{B}}^{\prime}$ be a bijection from
${\mathcal{B}}$ to ${\mathcal{B}}^{\prime}$. We say that the vertex
$\pi(v)\in{\mathcal{B}}^{\prime}$ is the copy of the vertex
$v\in{\mathcal{B}}$, and thus, ${\mathcal{B}}^{\prime}$ is the copy of
${\mathcal{B}}$.

  * •

$E_{1}=\\{(r,u):u\in{\mathcal{A}}\\}$, $E_{2}=E_{H}$ (except that edges in
$E_{2}$ are directed),
$E_{3}={\left\\{(v,\pi(v)):v\in{\mathcal{B}}\right\\}}$, and
$E_{4}=\\{(\pi(v),t):v\in{\mathcal{B}},t\in K_{v}\\}$.

So, in the graph $G$, we have edges from $r$ to all vertices in
$V_{1}={\mathcal{A}}$, the graph $(V_{1}\cup V_{2},E_{2})$ is just the graph
$H$, and $(V_{2}\cup V_{3},E_{3})$ is the matching between ${\mathcal{B}}$ and
its copies. The only non-straightforward element is $E_{4}$: If the vertex
$v\in{\mathcal{B}}$ is incident to an edge with color $t\in K$ in $H$, then we
have an edge from $\pi(v)$ to $t$ in $E_{4}$. Therefore, the set of
$d^{\prime}$ colors incident to a vertex $v\in{\mathcal{B}}$ in $H$ is the
same as the set of $d^{\prime}$ out-neighbors of $\pi(v)$ in $G$. The in-
degree of a terminal $t\in K$ is $s$.

The root of the DST instance is $r$, and the terminals are $V_{4}=K$. To
complete the DST instance, it remains to define the costs of edges in $G$:
Edges in $E_{1},E_{2},E_{3}$ and $E_{4}$ have costs
$\frac{|{\mathcal{B}}|}{|{\mathcal{A}}|},0,1$ and $0$ respectively.

Figure 1: An illustration of the Zosin-Khuller type gap instance. All the
edges go downwards. We only show some representative edges in $E_{2}$ and
$E_{4}$. The set of colors of incoming edges of $v$ is precisely the set out-
neighbors of $\pi(v)$.

Given the Zosin-Khuller type instance, we can naturally define an LP solution
$x\in[0,1]^{E}$, where every edge $e\in E$ has $x_{e}=\frac{1}{s}$. The cost
of the LP solution is
$\frac{1}{s}\cdot\left(|E_{1}|\cdot\frac{|{\mathcal{B}}|}{|{\mathcal{A}}|}+|E_{3}|\cdot
1\right)=\frac{1}{s}\cdot\left(|{\mathcal{A}}|\cdot\frac{|{\mathcal{B}}|}{|{\mathcal{A}}|}+|{\mathcal{B}}|\cdot
1\right)=\frac{2|{\mathcal{B}}|}{s}$. For every terminal $t\in K$, we can find
$s$ disjoint paths from $r$ to $t$ in $G$: For each $(u,v)\in M_{t}$, we take
the path $r\to u\to v\to\pi(v)\to t$. Notice that the edge $(\pi(v),t)$ exists
since $t\in K_{v}$. Therefore, the $x$ induces a valid solution to (FLP).

The following lemma says that if the objects specified in (P1) to (P3) have a
good property, then the DST instance has a large integrality gap.

######  Lemma 2.

Let $\alpha\geq 1$ be a real number. Suppose for every $u\in{\mathcal{A}}$,
there exists some $J_{u}\subseteq K$ of terminals with
$|J_{u}|\leq\frac{d}{\alpha}$, such that for every $(u,v)\in E_{H}$, we have
$|K_{v}\setminus J_{u}|\leq\frac{d^{\prime}}{\alpha}$. Then the optimum
solution to the DST instance has cost at least
$\frac{\alpha|{\mathcal{B}}|}{s}$.

###### Proof.

We can break the optimum directed Steiner tree $T^{*}$ of $G$ into many sub-
trees, each containing exactly one edge in $E_{1}$. We show that any such sub-
tree $T^{\prime}$ has a small _density_ , which is defined as the number of
terminals in $T^{\prime}$ divided by the cost of the edges in $T^{\prime}$. In
particular, we show its density is at most $\frac{d^{\prime}}{\alpha}$. If
this holds, then the optimum tree has cost at least
$k/\frac{d^{\prime}}{\alpha}=\alpha\cdot\frac{k}{d^{\prime}}=\alpha\cdot\frac{|{\mathcal{B}}|}{s}$
as $ks=d^{\prime}|{\mathcal{B}}|=|E_{H}|$.

So, we fix a sub-tree $T^{\prime}$ that contains exactly one edge in $E_{1}$,
and it remains to show that the density of $T^{\prime}$ is at most
$\frac{d^{\prime}}{\alpha}$. Let $u$ be the unique vertex in
$V_{1}={\mathcal{A}}$ in the tree. Let $V^{\prime}$ be the set of vertices in
$V_{2}$ in the tree; without loss of generality we assume that, for every
$v\in V^{\prime}$, we have $(v,\pi(v))\in T^{\prime}$ since, otherwise, we can
remove $(u,v)$ from the solution. So, each vertex in $V^{\prime}$ is a
neighbor of $u$ in $H$. The set of terminals that can be reached from
$V^{\prime}$ is $\operatorname{\bigcup}_{v\in V^{\prime}}K_{v}$. Therefore,
the number of terminals in the tree $T^{\prime}$ is at most

$\displaystyle\left|\operatorname{\bigcup}_{v\in
V^{\prime}}K_{v}\right|=\left|J_{u}\cup\operatorname{\bigcup}_{v\in
V^{\prime}}(K_{v}\setminus
J_{u})\right|\leq\frac{d}{\alpha}+\frac{d^{\prime}}{\alpha}|V^{\prime}|.$

The cost of $T^{\prime}$ is exactly
$\frac{|{\mathcal{B}}|}{|{\mathcal{A}}|}+|V^{\prime}|=\frac{d}{d^{\prime}}+|V^{\prime}|$,
and the density of the tree is at most
$\displaystyle\frac{\frac{d}{\alpha}+\frac{d^{\prime}}{\alpha}|V^{\prime}|}{\frac{d}{d^{\prime}}+|V^{\prime}|}=\frac{d^{\prime}}{\alpha}$.
∎

Therefore, if the condition in Lemma 2 holds, then the DST instance has
integrality gap at least $\alpha/2$.

In the Zosin-Khuller gap instance in [ZK02], the objects from (P1) to (P3) are
defined as follows. Let $K$ be the set of $k$ terminals, and assume $\sqrt{k}$
is an integer. We have ${\mathcal{A}}={K\choose\sqrt{k}}$,
${\mathcal{B}}={K\choose\sqrt{k}+1}$, and there is an edge from
$A\in{\mathcal{A}}$ to $B\in{\mathcal{B}}$ in $H$ if and only if $A\subseteq
B$. The color of $(A,B)$ is the unique terminal in $B\setminus A$. Notice that
all the required properties are satisfied.
$d=k-\sqrt{k},d^{\prime}=\sqrt{k}+1$, and for a vertex $B\in{\mathcal{B}}$, we
have $K_{B}=B$.

To satisfy the condition in Lemma 2, we define $J_{A}=A$ for every
$A\in{\mathcal{A}}$. So, $|J_{A}|=\sqrt{k}$. Then, for every
$B\in{\mathcal{B}}$ that is adjacent to $A$, we have $K_{B}\setminus
J_{A}=B\setminus A$, which has size 1. Therefore, we can define
$\alpha=\min\\{\frac{d}{\sqrt{k}},\frac{d^{\prime}}{1}\\}=\min\\{\sqrt{k}-1,\sqrt{k}+1\\}=\sqrt{k}-1$
to make the condition of Lemma 2 holds. The instance gives a gap of
$\Omega(\sqrt{k})$. However, it has size exponential in $\sqrt{k}$.

##  4 Instance with Polynomial Integrality Gap

The construction of our gap instance is similar to that of [ZK02] in the sense
that our ${\mathcal{A}}$ and ${\mathcal{B}}$ correspond to subsets of a ground
set. However, in our construction, a terminal is also correspondent to a
subset of the ground set (as opposed to a single element). In the graph $H$,
we have an edge from some element $A\in{\mathcal{A}}$ to some element
$B\in{\mathcal{B}}$ if and only if $A\subseteq B$, and the color of the edge
is the set $B\setminus A$, which will be an element in $K$. Using this
construction, we make the number of terminals exponential in the size of the
ground set. This can lead to a polynomial integrality gap. We carefully design
the sizes of the subsets so that the conditions in Lemma 2 hold with a large
$\alpha$.

We formally define the objects specified in (P1) to (P3). Let
$\rho=\frac{1}{16}$ and $\theta=\frac{1}{64}$. So $\theta=4\rho^{2}$, and
$\theta=\frac{\rho}{4}$. Let $m$ be an integer multiply of 64 so that $\rho m$
and $\theta m$ are integers. $[m]$ will be the ground set. Though $\rho$ and
$\theta$ are fixed, most of the time it is more convenient for us to keep the
two notions, without replacing them with their values. The objects are defined
as follows:

  * •

${\mathcal{A}}=K={[m]\choose\rho m},{\mathcal{B}}={[m]\choose 2\rho m}$, there
is an edge from some $A\in{\mathcal{A}}$ to some $B\in{\mathcal{B}}$ in $H$ if
and only if $A\subseteq B$. The edge has color $B\setminus A\in K$.

  * •

Therefore, $d={(1-\rho)m\choose\rho m},d^{\prime}={2\rho m\choose\rho
m},k={m\choose\rho m}$ and $K_{B}={\left\\{C\subseteq B:|C|=\rho m\right\\}}$
for every $B\in{\mathcal{B}}$.

It is easy to check that all the required properties are satisfied:
$|{\mathcal{A}}|\leq|{\mathcal{B}}|$, the graph $H$ is bi-regular and all
matchings have the same size, as $H$ is highly symmetric.

Now we shall define the set $J_{A}$ for any $A\in{\mathcal{A}}$ to satisfy the
condition of Lemma 2. This is defined as follows:

$\displaystyle J_{A}=\\{C\in K:|C\cap A|>\theta m\\}.$

We then show that this definition satisfies the condition of Lemma 2 for some
$\alpha=e^{\Omega(m)}$. From now on, we fix any
$A\in{\mathcal{A}}={[m]\choose\rho m}$.

######  Lemma 3.

There is an absolute constant $c>1$ such that $|J_{A}|\leq\frac{d}{c^{m}}$.

###### Proof.

Let $C$ be a set that is uniformly at random chosen from $K={[m]\choose\rho
m}$. Then, $\frac{|J_{A}|}{k}=\Pr[|C\cap A|>\theta m]$. Define
$\mu:=\operatorname*{{\mathbb{E}}}[|C\cap A|]=\rho m\cdot\frac{\rho
m}{m}=\rho^{2}m<\theta m$. Notice that the events $\\{(i\in C)\\}_{i\in A}$
are negatively correlated. Then, applying Chernoff bound for negatively
correlated random variables (see Theorem 5), we have

$\displaystyle\Pr[|C\cap A|>\theta m]$ $\displaystyle=\Pr\left[|C\cap
A|>\Big{(}1+\frac{\theta m}{\mu}-1\Big{)}\mu\right]$
$\displaystyle\leq\exp\left(-\frac{\left(\theta
m/\mu-1\right)^{2}\mu}{2+\theta m/\mu-1}\right)=\exp\left(-\frac{\theta
m/\mu-1}{\theta m/\mu+1}\cdot(\theta m-\mu)\right)$
$\displaystyle=\exp\left(-\frac{\theta-\rho^{2}}{\theta+\rho^{2}}\cdot\big{(}\theta-\rho^{2}\big{)}m\right)=\exp\left(-\frac{9\rho^{2}m}{5}\right).$

The last equality used that $\theta=4\rho^{2}$. On the other hand, we have

$\displaystyle\frac{k}{d}={m\choose\rho m}\big{/}{(1-\rho)m\choose\rho m}$
$\displaystyle=\prod_{i=0}^{\rho
m-1}\frac{m-i}{(1-\rho)m-i}\leq\left(\frac{1-\rho}{1-2\rho}\right)^{\rho m}$
$\displaystyle\leq\exp\left(\frac{\rho}{1-2\rho}\cdot\rho
m\right)=\exp\left(\frac{\rho^{2}m}{1-2\rho}\right)=\exp\left(\frac{8\rho^{2}m}{7}\right).$

Therefore,

$\displaystyle\frac{|J_{A}|}{d}=\frac{k}{d}\cdot\Pr[|C\cap A|>\theta
m]\leq\exp\left(-\frac{9\rho^{2}m}{5}\right)\cdot\exp\left(\frac{8\rho^{2}m}{7}\right)=\exp\left(-\frac{23}{35}\rho^{2}m\right).$

The lemma then follows by letting
$c=\exp\left(\frac{23}{35}\rho^{2}\right)>1$. ∎

######  Lemma 4.

For any $B\in{\mathcal{B}}$ such that $A\subseteq B$, we have $|K_{B}\setminus
J_{A}|\leq\frac{d^{\prime}}{c^{\prime m}}$ for some absolute constant
$c^{\prime}>1$.

###### Proof.

Notice that $\frac{|K_{B}\setminus J_{A}|}{d^{\prime}}=\frac{|K_{B}\setminus
J_{A}|}{|K_{B}|}$, which is exactly the probability that a randomly chosen
element in $K_{B}$ is not in $J_{A}$. Let $C$ be a random subset of $B$ of
size $\rho m$. So, the quantity is the probability that $|C\cap A|\leq\theta
m$. Notice that we have $\mu:=\operatorname*{{\mathbb{E}}}[|C\cap A|]=\rho
m\cdot\frac{\rho m}{2\rho m}=\frac{\rho m}{2}>\theta m$. Applying the lower
tail Chernoff bound (see Theorem 5) on negatively correlated variables, we
obtain

$\displaystyle\Pr[|C\cap A|\leq\theta m]=\Pr\left[|C\cap
A|\leq(1-1/2)\mu\right]\leq\exp\left(-\frac{(1/2)^{2}}{2}\mu\right)=\exp\left(-\frac{\mu}{8}\right)=\exp\left(-\frac{\rho
m}{16}\right)=e^{-\frac{m}{256}}.$

The first equality follows because $\mu=\frac{\rho m}{2}=2\theta m$. Thus, the
lemma holds with $c^{\prime}=e^{\frac{1}{256}}$. ∎

Therefore, the condition of Lemma 2 holds with $\alpha=\min\\{c^{m},c^{\prime
m}\\}\geq e^{\Omega(m)}$. Let $n$ be the number of vertices in the constructed
DST instance. Then we have $n\leq e^{O(m)}$. Therefore, we have
$\alpha=n^{\Omega(1)}$. This finishes the proof of Theorem 1.

##  5 Future Directions

Our result rules out a polynomial-time poly-logarithmic approximation for DST
using the flow LP relaxation. Our instance is on a 5-level graph, and thus it
admits a poly-logarithmic approximation via recursive greedy [CCGG98] or LP
hierarchies [Rot11, FKK+14]. One interesting future direction is to understand
the power of $O(1)$-level lift of the flow LP using some hierarchy. That is,
whether the lifted LP still has a polynomial integrality gap. To show a lower
bound, we may need to lift our gap instance for the basic flow LP in some
manner.

#### Acknowledgment

We thank Jittat Fakcharoenphol for the useful discussions.

## References

  * [BGRS10] Jaroslaw Byrka, Fabrizio Grandoni, Thomas Rothvoß, and Laura Sanità.  An improved lp-based approximation for steiner tree.  In Proceedings of the Forty-Second ACM Symposium on Theory of Computing, STOC ’10, page 583–592, New York, NY, USA, 2010. Association for Computing Machinery.
  * [BP89] M. Bern and P. Plassmann.  The steiner problem with edge lengths 1 and 2.  Inf. Process. Lett., 32:171–176, 1989.
  * [CC08] Miroslav Chlebík and J. Chlebíková.  The steiner tree problem on graphs: Inapproximability results.  Theor. Comput. Sci., 406:207–214, 2008.
  * [CCC+99] Moses Charikar, Chandra Chekuri, To-Yat Cheung, Zuo Dai, Ashish Goel, Sudipto Guha, and Ming Li.  Approximation algorithms for directed steiner problems.  J. Algorithms, 33(1):73–91, 1999.
  * [CCGG98] Moses Charikar, Chandra Chekuri, Ashish Goel, and Sudipto Guha.  Rounding via trees: Deterministic approximation algorithms for group steiner trees and _k_ -median.  In Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, May 23-26, 1998, pages 114–123, 1998\.
  * [FKK+14] Zachary Friggstad, Jochen Könemann, Young Kun-Ko, Anand Louis, Mohammad Shadravan, and Madhur Tulsiani.  Linear programming hierarchies suffice for directed steiner tree.  In Integer Programming and Combinatorial Optimization - 17th International Conference, IPCO 2014, Bonn, Germany, June 23-25, 2014. Proceedings, pages 285–296, 2014.
  * [GLL19] Fabrizio Grandoni, Bundit Laekhanukit, and Shi Li.  _O_(log${}^{\mbox{2}}$ _k_ / log log _k_)-approximation algorithm for directed steiner tree: a tight quasi-polynomial-time algorithm.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 253–264, 2019.
  * [GN20] Rohan Ghuge and Viswanath Nagarajan.  Quasi-polynomial algorithms for submodular tree orienteering and other directed network design problems.  In To appear in SODA’20., 2020.
  * [HK03] Eran Halperin and Robert Krauthgamer.  Polylogarithmic inapproximability.  In Proceedings of the 35th Annual ACM Symposium on Theory of Computing, June 9-11, 2003, San Diego, CA, USA, pages 585–594, 2003.
  * [HKK+07] Eran Halperin, Guy Kortsarz, Robert Krauthgamer, Aravind Srinivasan, and Nan Wang.  Integrality ratio for group steiner trees and directed steiner trees.  SIAM J. Comput., 36(5):1494–1511, 2007.
  * [KP99] Guy Kortsarz and David Peleg.  Approximating the weight of shallow steiner trees.  Discrete Applied Mathematics, 93(2-3):265–285, 1999.
  * [Mos15] Dana Moshkovitz.  The projection games conjecture and the np-hardness of ln n-approximating set-cover.  Theory of Computing, 11:221–235, 2015.
  * [PS97] Alessandro Panconesi and Aravind Srinivasan.  Randomized distributed edge coloring via an extension of the chernoff-hoeffding bounds.  SIAM J. Comput., 26(2):350–368, 1997.
  * [Rot11] Thomas Rothvoß.  Directed steiner tree and the lasserre hierarchy.  CoRR, abs/1111.5473, 2011.
  * [Zel97] Alexander Zelikovsky.  A series of approximation algorithms for the acyclic directed steiner tree problem.  Algorithmica, 18(1):99–110, 1997.
  * [ZK02] Leonid Zosin and Samir Khuller.  On directed steiner trees.  In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 6-8, 2002, San Francisco, CA, USA., pages 59–63, 2002.

##  Appendix A Chernoff Bounds for Negatively Correlated Random Variables

A set of 0/1 random variables $\\{X_{1},X_{2},\cdots,X_{n}\\}$ are said to be
negatively correlated if for any subset $S\subseteq[n]$ and any
$b\in\\{0,1\\}$, it holds that

$\displaystyle\Pr\left[\bigwedge_{i\in S}(X_{i}=b)\right]\leq\prod_{i\in
S}\Pr[X_{i}=b].$

######  Theorem 5 (Theorem 3.2 in [PS97]).

Let $X_{1},X_{2},\cdots,X_{n}$ be a set of negatively correlated 0/1 random
variables. Let
$\mu=\operatorname*{{\mathbb{E}}}\Big{[}\sum_{i=1}^{n}X_{i}\Big{]}$. Then for
any $\delta\in(0,1)$, we have

$\displaystyle\Pr\left[\sum_{i=1}^{n}X_{i}\geq(1+\delta)\mu\right]\leq
e^{-\frac{\delta^{2}\mu}{2+\delta}},\text{ and
}\Pr\left[\sum_{i=1}^{n}X_{i}\leq(1-\delta)\mu\right]\leq
e^{-\frac{\delta^{2}\mu}{2}}.$