We consider the problem of selecting an optimal subset of information sources for a hypothesis testing/classification task where the goal is to identify the true state of the world from a finite set of hypotheses, based on finite observation samples from the sources. In order to characterize the learning performance, we propose a misclassification penalty framework, which enables non-uniform treatment of different misclassification errors. In a centralized Bayesian learning setting, we study two variants of the subset selection problem: (i) selecting a minimum cost information set to ensure that the maximum penalty of misclassifying the true hypothesis remains bounded and (ii) selecting an optimal information set under a limited budget to minimize the maximum penalty of misclassifying the true hypothesis. Under mild assumptions, we prove that the objective (or constraints) of these combinatorial optimization problems are weak (or approximate) submodular, and establish high-probability performance guarantees for greedy algorithms. Further, we propose an alternate metric for information set selection which is based on the total penalty of misclassification. We prove that this metric is submodular and establish near-optimal guarantees for the greedy algorithms for both the information set selection problems. Finally, we present numerical simulations to validate our theoretical results over several randomly generated instances.

Combinatorial Optimization, Bayesian Classification, Submodularity, Greedy Algorithms, Finite Sample Convergence

§ INTRODUCTION

In many autonomous systems, agents depend on predictions made by classifiers for making decisions (or taking actions), and may have to pay a high cost for acting on erroneous predictions. An example of this is an incident of an autonomous vehicle crash caused due to the vision system misclassifying a white truck as a bright sky (<cit.>). In such scenarios, one needs to ensure minimal risk associated with misclassification. In order to improve the quality of predictions, one may need to select an optimal set of features (or observations), often provided by information sources (or sensors), that can best describe the true state. In many practical scenarios, due to limitations on communication or compute resources, one can only query data from a small subset of information sources (<cit.>). Moreover, one may also need to pay a certain cost in order to obtain measurements from information sources (<cit.>). Thus, a fundamental problem that arises in such scenarios is to select a subset of information sources with minimal cost or under a limited budget, while ensuring certain learning performance using the observations provided by the selected sources. In order to characterize the quality of an information set, we propose a framework based on misclassification penalties, specified by a penalty matrix. The goal is to select an information set that minimizes the maximum penalty of misclassifying the true state. As a motivating example, consider a  surveillance task, where identifying a target of interest is of importance. One many have to pay a penalty for misclassifying the true state, for instance, misclassifying a drone (an intruder) as a bird. However, the event of misclassifying a bird as a drone may have a different penalty associated with it. The penalty matrix captures the fact that different misclassification errors incur different penalties.

§.§ Related Work

Misclassification risk and uncertainty quantification for various types of classifiers have been very well studied in the literature (<cit.>). In <cit.>, the authors propose a risk-calibrated classifier to reduce the costs associated with misclassification errors, and empirically show the effectiveness of their algorithm, in a  deep learning framework. In <cit.>, the authors study cost-sensitive learning for class balancing in order to improve the quality of predictions in decision tree learning methods. In our work, we consider a hypothesis testing (or classification) task in a Bayesian learning framework.

A subset of the literature has addressed the problem of sequential information gathering within a limited budget (<cit.>). The authors of  <cit.> study data source selection for a monitoring application, where the sources are selected sequentially in order to estimate certain parameters of an environment. In <cit.>, the authors study sequential information gathering under a limited budget for a robotic navigation task.  In contrast, we consider the scenario where the information set is selected a priori.

A substantial body of work focuses on the study of submodularity (and/or weak submodularity) and greedy techniques with provable guarantees for feature selection in sparse learning (<cit.>); sensor selection for estimation (<cit.>),  Kalman filtering  (<cit.>), and mixed-observable Markov decision processes (<cit.>). Along the lines of these works, we leverage the weak submodularity property of the performance metric and present greedy algorithms with performance guarantees.

The closest paper to our work is <cit.>, in which the authors studied data source selection for Bayesian learning, where the learning performance was characterized by a total variation error metric based on the asymptotic belief. However, we consider a non-asymptotic setting, where the learning performance is characterized by misclassification penalties. Building upon the results in <cit.> and <cit.>, we establish theoretical guarantees for greedy information selection algorithms presented in this paper.

§.§ Contributions
We consider two variants of information subset selection problem for a hypothesis testing task (i) selecting a minimum cost information set to ensure the maximum penalty for misclassifying the true hypothesis remains bounded and (ii) optimal information set selection under a limited budget to minimize the maximum penalty of misclassifying the true hypothesis. First, we prove that the maximum penalty metric is weak submodular by characterizing its submodularity ratio, and establish high-probability guarantees for greedy algorithms for both the problems, along with the associated finite sample convergence rates for the Bayesian beliefs. Next, we propose an alternate metric based on the total penalty of misclassification. We prove that this metric is submodular, and establish  near-optimal guarantees for the greedy algorithms. Finally, we evaluate the empirical performance of the proposed greedy algorithms over several randomly generated problem instances.

§ MINIMUM-COST INFORMATION SET SELECTION PROBLEM

In this section, we formulate the minimum-cost information set selection problem. Let $\Theta = \{ \theta_1, \theta_2, \hdots, \theta_m \}$, where $m = |\Theta| $, be a finite set of possible hypotheses (also referred to as classes or states), of which one of them is the true state of the world. We consider a set $\mathcal{D} = \{1,2, \hdots, n \}$ of information sources (or data streams) from which we need to select a subset $\mathcal{I} \subseteq \mathcal{D}$. At each time step $t \in \mathbb{Z}_{\geq 1}$, the observation provided by the information source $i \in \mathcal{D}$ is denoted as $o_{i,t} \in O_i$, where $O_i$ is the observation space of the source $i$. Each information source $i \in \mathcal{D}$ is associated with an observation likelihood function $\ell_i(\cdot | \theta)$, which is conditioned on the state of the world $\theta \in \Theta$. At any time $t$, conditioned on the true state of the world $\theta \in \Theta$, a joint observation profile of $n$ information sources, denoted as $o_t = (o_{1,t}, \hdots, o_{n,t}) \in \mathcal{O}$ where $\mathcal{O} = O_1 \times \hdots \times O_n$, is generated by the joint likelihood function $\ell(\cdot|\theta)$. We make the following assumption on the observation model (e.g., see <cit.>; <cit.>; <cit.> for detailed discussions).

Assumption 1: The observation space $O_i$ associated with each information source $i \in \mathcal{D}$ is finite, and the likelihood function $\ell_i(\cdot | \theta)$ satisfies $\ell_i(\cdot | \theta) > 0$ for all $o_i \in O_i$ and for all $\theta \in \Theta$. We assume that the designer knows $\ell_i(\cdot | \theta)$ for all $\theta \in \Theta$ and all $i \in \mathcal{D}$. For all $\theta \in \Theta$, conditioned on the true state, the observations are independent of each other over time, i.e., $\{ o_{i,1}, o_{i,2}, \hdots \}$ is a sequence of independent identically distributed (i.i.d.) random variables, given a true state $\theta \in \Theta$.

Consider the scenario where a designer at a central node needs to select a subset of information sources in order to identify the true state of the world. Each source $i \in \mathcal{D}$ has a selection cost $c_i \in \mathbb{R}_{> 0}$. For any subset $\mathcal{I} \subseteq \mathcal{D}$ with $|\mathcal{I}| = k$, let $\{s_1, s_2, \hdots, s_k\}$ denote the set of information sources. The cost of the information set $\mathcal{I}$ is given by $c(\mathcal{I}) = \sum_{s_i \in \mathcal{I}} c_{s_i}$. The joint observation conditioned on the $\theta \in \Theta$ of this information set at time $t$ is defined as $o_{\mathcal{I},t} = \{ o_{s_1,t}, \hdots, o_{s_k,t} \} \in O_{s_1} \times \hdots \times O_{s_k} $, and is generated by the joint likelihood function $\ell_{\mathcal{I}}(\cdot | \theta) = \Pi_{i = 1}^{k} \ell_{s_i}(\cdot | \theta)$ (by Assumption 1), and the central designer knows $\ell_{\mathcal{I}} (\cdot | \theta)$ for all $\mathcal{I} \subseteq \mathcal{D}$ and for all $\theta \in \Theta$.

Assumption 1 also implies the existence of a constant $L \footnote{The constant $L$ is an upper bound on the maximum difference between the  log-likelihood of an observation from an information source under any two hypotheses, which we will use later in our analyses.} \in(0, \infty)$ such that:

\begin{equation}
\label{eq:kld_ratio}
\max _{i \in \mathcal{D}} \max _{o_i \in O_i} \max _{\theta_p, \theta_q \in \Theta}\left|\log \frac{\ell_i\left(o_i \mid \theta_p\right)}{\ell_i\left(o_i \mid \theta_q\right)}\right| \leq L.
\end{equation}

For a true state $\theta_p \in \Theta$, we define $\mathbb{P}^{\theta_p} = \prod_{t=1}^{\infty}\ell(\cdot|\theta_p)$ to be the probability measure. For the sake of brevity, we will say that an event occurs almost surely to mean that it occurs almost surely w.r.t. the probability measure $\mathbb{P}^{\theta_p}.$
As the data comes in, the central node updates its belief over the set of possible hypotheses using the standard Bayes' rule. Let $\mu_{t}^{\mathcal{I}}(\theta)$ denote the belief of the central designer (or node) that $\theta$ is the true hypothesis  at time step $t$ based on the information sources in $\mathcal{I}$, and let $\mu_0(\theta)$ denote the initial belief (or prior) of the central node that $\theta$ is the true state of the world, with $\sum_{\theta \in \Theta} \mu_0(\theta) = 1$. The Bayesian update rule is given by

\begin{equation}
\label{eq:bayes_full}
\mu_{t+1}^{\mathcal{I}}(\theta) = \frac{\mu_0(\theta)  \prod_{j=0}^{t} \ell_{\mathcal{I}} (o_{\mathcal{I}, j+1} | \theta) }{\sum_{\theta_i \in \Theta} \mu_0(\theta_i)
\prod_{j=0}^{t} \ell_{\mathcal{I}} (o_{\mathcal{I}, j+1} | \theta_i) } \quad \forall \theta \in \Theta.
\end{equation}

For a hypothesis $\theta \in \Theta$ and an information set $\mathcal{I} \subseteq \mathcal{D}$, we have the following.
(<cit.>) For a given hypothesis (or class) $\theta \in \Theta$ and a given $\mathcal{I} \subseteq \mathcal{D}$, the observationally equivalent set of classes to $\theta$ is defined as

\begin{equation}
F_{\theta}(\mathcal{I}) = \{ \theta_i \in \Theta \mid D_{KL} (\ell_\mathcal{I}(\cdot | \theta_i) || \ell_\mathcal{I}(\cdot | \theta) ) = 0 \},
\end{equation}

where $D_{KL}(\ell_\mathcal{I}(\cdot | \theta_i) || \ell_\mathcal{I}(\cdot | \theta) )$ is the Kullback-Leibler divergence measure $\ell_\mathcal{I}(\cdot | \theta_i)$ and $ \ell_\mathcal{I}(\cdot | \theta) $.

From the definition above, we have $\theta \in F_{\theta}(\mathcal{I})$ for all $\theta \in \Theta$ and all for $\mathcal{I} \subseteq \mathcal{D}$. We can write the set $F_{\theta}(\mathcal{I})$ equivalently as

\begin{equation}
\label{eq:obs_eq_set}
F_{\theta}(\mathcal{I}) = \{ \theta_i \in \Theta : \ell_{\mathcal{I}}(o_{\mathcal{I}} | \theta_i) = \ell_{\mathcal{I}}(o_{\mathcal{I}} | \theta), \forall o_{\mathcal{I}} \in \mathcal{O}_{\mathcal{I}}   \},
\end{equation}

where $\mathcal{O}_{\mathcal{I}}  = O_{s_1} \times \hdots \times O_{s_k}$ is the joint observation space of the information set $\mathcal{I}$. In other words, $F_{\theta}(\mathcal{I})$ is the set of hypotheses (or classes) that cannot be distinguished from $\theta$ based on the observations obtained by the information sources in $\mathcal{I}$. Furthermore, by Assumption 1 and Equation (<ref>), we have the following (see Section 2 in <cit.>):

\begin{equation}
\label{eq: obs_eq_intersect}
F_{\theta}(\mathcal{I}) = \bigcap_{s_i \in \mathcal{I}} F_{\theta} (s_i), \forall \mathcal{I} \in \mathcal{D}, \forall \theta \in \Theta.
\end{equation}

Define $F_{\theta}(\emptyset) = \Theta$, i.e.,  when there is no information set, all classes are observationally equivalent.

At time $t$, the central designer predicts the state of the world based on the belief  $\mu_{t}^{\mathcal{I}}$ generated by the information set $\mathcal{I}$. In order to characterize the learning performance, we consider a penalty-based classification framework. Let  $\Xi = [\xi_{ij}] \in \mathbb{R}^{m \times m}$ denote the penalty matrix, where $ 0 \leq \xi_{ij} \leq 1$ is the penalty associated with predicting the class to be $\theta_j$, given that the true class  is $\theta_i$. The penalty matrix is assumed to be row stochastic, i.e., $\sum_{j = 1}^{m} \xi_{ij} = 1$. We have $\xi_{ii} = 0, \hspace{4pt} \forall i \in \{1,2, \hdots, m\}$, i.e., there is no penalty when the predicted hypothesis is the true hypothesis.  Similar to analyses presented in <cit.> and <cit.>, we present finite sample convergence rates for the Bayesian belief over the set of hypotheses. In this paper, we consider the case of uniform prior, but the results can be extended to non-uniform priors (using similar arguments as in Lemma 1 of <cit.>). We defer all the proofs to the Appendix (see Appendix <ref>).

Let the true state of the world be $\theta_p$ and let $\mu_0 (\theta) = \frac{1}{m} \hspace{5pt} \forall \theta \in \Theta$ (i.e., uniform prior). Under Assumption 1, for any $\delta, \epsilon \in [0,1]$, and L as defined in Equation (<ref>), and for an information set $\mathcal{I} \subseteq \mathcal{D}$, the Bayesian update rule in Equation (<ref>) has the following property: there is an integer $N(\delta, \epsilon, L)$, such that with probability at least $1-\delta$, for all $t > N(\delta, \epsilon, L)$ we have:

* $\mu_t^{\mathcal{I}}(\theta_q) =  \mu_t^{\mathcal{I}}(\theta_p)  \hspace{5pt} \forall \theta_q \in F_{\theta_p}(\mathcal{I})$, and

* $\mu_t^{\mathcal{I}}(\theta_q) \leq \exp{(-t(|K(\theta_p, \theta_q)-\epsilon|))} \hspace{5pt} \forall \theta_q \notin F_{\theta_p}(\mathcal{I})$;

where $K(\theta_p, \theta_q) = D_{KL}(\ell_{\mathcal{I}}(\cdot | \theta_p) || \ell_{\mathcal{I}}(\cdot | \theta_q) )$ is the Kullback-Leibler divergence measure between the likelihood functions $\ell_{\mathcal{I}}(\cdot | \theta_p)$ and $ \ell_{\mathcal{I}}(\cdot | \theta_q) $, $F_{\theta_p}(\mathcal{I})$ is defined in (<ref>), and
$N(\delta, \epsilon,L) = \left\lceil \frac{2L^2}{\epsilon^2 } \log \frac{2}{\delta} \right\rceil.$

We consider a belief threshold rule in order to rule out hypotheses that do not have a high likelihood of being predicted as the true hypothesis. Let $\mu_{th}$ be the threshold chosen by the central designer. Corollary <ref> presents the sample complexity for the observations in order to ensure that the beliefs over the states $\theta_q \notin F_{\theta_p}(\mathcal{I})$ remain bounded under the specified threshold.

Instate the hypothesis and notation of Theorem <ref>. For a specified threshold $\mu_{th}\in    (0,1)$ for the belief over any class $\theta_q \notin F_{\theta_p}(\mathcal{I}) $, there exists $\delta, \epsilon \in [0,1]$, for which one can guarantee with probability at least $1-\delta$ that $\mu_t^{\mathcal{I}}(\theta_q) \leq \mu_{th}$  for all $\theta_q \notin F_{\theta_p}$ and for all $t > \Tilde{N}$, where

\begin{equation}
\label{eq:nbar}
\Tilde{N} = \left\lceil  \max \left\{ \frac{2L^2}{\epsilon^2 } \log \frac{2}{\delta} , \frac{1}{ \displaystyle\min_{\theta_p,\theta_q \in \Theta} |K(\theta_p, \theta_q)-\epsilon| } \log \frac{1}{\mu_{th}}   \right\} \right\rceil.
\end{equation}

From Corollary <ref>, we have the following: With probability at least $1-\delta$, after any $t> \Tilde{N}$, the central node will predict one of  $\theta_q \in F_{\theta_p}(\mathcal{I})$ to be the true hypothesis. Therefore, it is sufficient to consider the penalties associated with the states $\theta_q \in F_{\theta_p}(\mathcal{I})$ for finding the maximum penalty. We now formalize the Minimum-Cost Information Set Selection (MCIS) Problem as follows:

Consider a set $\Theta=\left\{\theta_1, \ldots, \theta_m\right\}$ of possible states of the world, a set $\mathcal{D}$ of information sources, a selection cost $c_i \in \mathbb{R}_{>0}$ of each source $i \in \mathcal{D}$, a row-stochastic penalty matrix $\Xi = [\xi_{ij}] \in \mathbb{R}^{m \times m}$, and prescribed penalty bounds $0 \leq R_{\theta_p} \leq 1$ for all $\theta_p \in \Theta$. The MCIS Problem is to find a set of selected information sources $\mathcal{I} \subseteq \mathcal{D}$ that solves

\begin{equation}
\label{eq:dsrc}
\begin{aligned}
\min _{\mathcal{I} \subseteq \mathcal{D}} & \hspace{5pt} c(\mathcal{I}) ; \hspace{2pt}
\text { s.t. } \displaystyle \max_{\theta_i \in F_{\theta_p}(\mathcal{I})} \xi_{pi}  \leq R_{\theta_p} \quad \forall \theta_p \in \Theta.
\end{aligned}
\end{equation}

§.§ Weak Submodularity and Greedy Algorithm

The combinatorial optimization in (<ref>) can be shown to be NP-hard (based on similar arguments as in Theorem 3  of <cit.>). In this section, we propose a greedy algorithm with performance guarantees to efficiently approximate the solution to the MCIS Problem. We first begin by transforming the MCIS problem into the minimum cost set cover problem studied in <cit.>.

A set function $f:2^{\Omega }\to\mathbb{R}$ is monotone non-decreasing if $f(X) \leq f(Y) $ for all $X \subseteq Y \subseteq \Omega$ and monotone non-increasing if $f(X) \geq f(Y) $ for all $X \subseteq Y \subseteq \Omega$.

[There are several notions of submodularity ratio. We consider $\gamma_{U,k}$ as defined in <cit.>, where $U$ is the universal set and $k\ge 1$ is a parameter, and drop the dependence on $k$ by defining $\gamma = \min_{k} \gamma_{U,k}$. ]

Given a set  $\Omega$, the submodularity ratio of a non-negative function $f: 2^{\Omega} \to \mathbb{R}_{\ge 0}$ is the largest $\gamma \in \mathbb{R}$ that satisfies  for all $A, B \subseteq \Omega$, the following:

\begin{equation*}
\label{eq:submod_ratio_def}
\sum_{a \in A \setminus B} (f(\{a\} \cup B) - f(B)) \ge \gamma (f(A \cup B) - f(B)).
\end{equation*}

For a non-negative and non-decreasing function $f(\cdot)$ with submodularity ratio $\gamma$, we have $\gamma \in [0,1]$. If $\gamma$ is closer to 1, the function is closer to being submodular. $f(\cdot)$ is submodular if and only if $\gamma \ge 1$. <cit.> provide guarantees for greedy optimization of weak submodular functions, which depend on the submodularity ratio $\gamma$. Thus, in order to characterize the performance of greedy, one has to give a (non-zero) lower bound on $\gamma$.

The constraint in (<ref>) can be equivalently written as: $1- \max_{\theta_i \in F_{\theta_p}(\mathcal{I})} \xi_{pi} \geq 1-R_{\theta_p}, \hspace{4pt} \forall \theta_p \in \Theta.$ For all $\mathcal{I} \subseteq \mathcal{D}$ and for a true state $\theta_p \in \Theta$, let us define $f_{\theta_p}(\mathcal{I}) =1- \max_{\theta_j\in F_{\theta_p}(\mathcal{I})} \xi_{pj}$. It follows from  (<ref>) that $f_{\theta_p}(\cdot)$ is a monotone non-decreasing set function with $f_{\theta_p}(\emptyset) = 1-\max_{\theta_j\in \Theta} \xi_{pj}$.

In order to establish the approximate (or weak) submodularity property, we make the following assumption on the misclassification penalties.

Assumption 2: The misclassification penalties are unique, i.e., $\xi_{pi} \neq \xi_{pj}$ for all $i \neq j, \forall \theta_p \in \Theta$.
Under Assumption 2, the function $f_{\theta_p}(\mathcal{I}) :2^{\mathcal{D} }\to\mathbb{R}_{\geq0} $ is approximately submodular for all $\theta_p \in \Theta$, with a submodularity ratio $\gamma = \underline{\xi}/ \Bar{\xi} $, where

\begin{align}
\label{eq:xifloor}
\displaystyle \underline{\xi} = \min_{\theta_p \in \Theta} \left(\min_{\theta_i,\theta_j \in \Theta}  |\xi_{pi} - \xi_{pj}|\right) ; \quad \hspace{2pt}
\Bar{\xi} = \max_{\theta_p \in \Theta} \left(\max_{\theta_i,\theta_j \in \Theta}  |\xi_{pi} - \xi_{pj}|\right).
\end{align}

In order to ensure that there exists a feasible solution $\mathcal{I} \subseteq \mathcal{D}$ that satisfies the constraints, we assume that $f_{\theta_p} (\mathcal{D}) \geq 1- R_{\theta_p}$ for all $\theta_p \in \Theta$.  For any $\mathcal{I} \subseteq \mathcal{D}$, we define
$f_{\theta_p}^{'}(\mathcal{I}) = \text{min} \{ f_{\theta_p}(\mathcal{I}), 1- R_{\theta_p}\} \quad \forall \theta_p \in \Theta.$
The function $f_{\theta_p}^{'}(\mathcal{I})$ captures the sufficient condition for satisfying the penalty constraints corresponding to each state. We now define, for all $\mathcal{I} \subseteq \mathcal{D}$,

\begin{equation}
\label{eq:zofn}
z(\mathcal{I}) = \sum_{\theta_p \in \Theta} f_{\theta_p}^{\prime}(\mathcal{I})=\sum_{\theta_p \in \Theta} \min \left\{f_{\theta_p}(\mathcal{I}), 1-R_{\theta_p}\right\}.
\end{equation}

The expression $z(\mathcal{I})$ combines all the constraints (corresponding to each hypothesis $\theta \in \Theta$), which we wish to satisfy, while selecting the information set. In other words, $z(\cdot)$ is used to find the optimal set $\mathcal{I}$, i.e., a set $\mathcal{I} \subseteq \mathcal{D}$ with minimal $c(\mathcal{I})$,  satisfying $z(\mathcal{I}) = z(\mathcal{D})$. Since $F_{\theta_p}(\emptyset) = \Theta$, we have $ z(\emptyset) = m - \sum_{\theta_p \in \Theta} \max_{\theta_i \in \Theta} \xi_{pi}$. Since $f_{\theta_p}(\mathcal{I})$ is approximately submodular and non-decreasing, we have that $f'_{\theta_p}(\mathcal{I})$ is also approximately submodular and non-decreasing. Noting that the non-negative sum of approximately submodular functions is approximately submodular (Lemma 3.12 of <cit.>), we have that $z(\cdot)$ is also approximately submodular. We have the following result, which follows from the existence of a feasible solution for Problem <ref>.

For any $\mathcal{I} \subseteq\mathcal{D}$, the constraint $1-\max_{\theta_i \in F_{\theta_p}(\mathcal{I})} \xi_{pi} \geq 1-R_{\theta_p}$ holds for all $\theta_p \in \Theta$ if and only if $\sum_{\theta_p \in \Theta} f_{\theta_p}^{\prime}(\mathcal{I})=\sum_{\theta_p \in \Theta} f_{\theta_p}^{\prime}(\mathcal{D})$.

We now have from Lemma <ref> that the constraint (<ref>) in Problem <ref> can be equivalently written as

\begin{equation}
\label{eq:submod_opt}
\begin{aligned}
\hspace{18pt} \min _{\mathcal{I} \subseteq\mathcal{D}} c(\mathcal{I}); \hspace{2pt} \textit { s.t. } z(\mathcal{I})=z(\mathcal{D}).
\end{aligned}
\end{equation}

Problem (<ref>) can then be viewed as the set covering problem studied in <cit.>. In <cit.>, the authors present performance guarantees for the weak submodular version of the set covering problem studied in <cit.>. Based on Theorem 9 in <cit.>, we have the following performance guarantees for Algorithm <ref> when applied to the MCIS problem.
Greedy Algorithm for MCIS
Input: ${\mathcal{D}}, z:2^{{\mathcal{D}}}\to\mathbb{R}_{\geq 0}, c_i \in \mathbb{R}_{>0}$ $\forall i\in{\mathcal{D}}$

Output: $\mathcal{I}_g$
[1]
$k\gets 0, \mathcal{I}_g^0\gets\emptyset$
$z(\mathcal{I}_g^t)< z({\mathcal{D}})$
$\mathcal{I}_g^{t+1}\gets \mathcal{I}_g^t\cup\{j_t\}, k\gets k+1$
$T\gets k$, $\mathcal{I}_g\gets\mathcal{I}_g^T$
return $\mathcal{I}_g$

Let $\mathcal{I}^*$ be an optimal solution to the MCIS problem having a submodularity ratio $\gamma$. For a specified threshold $\mu_{th} \in (0,1)$ and $0\leq\delta\leq1$, with probability at least $1-\delta$, Algorithm 1 under $\Tilde{N}$ observation samples  returns a solution $\mathcal{I}_g$ to the MCIS problem (i.e., (<ref>)) that satisfies the following:

$$c\left(\mathcal{I}_g\right) \leq\left(1+\frac{1}{\gamma}\log \frac{z(\mathcal{D})-z(\emptyset)}{z(\mathcal{D})-z\left(\mathcal{I}_g^{T-1}\right)}\right) c\left(\mathcal{I}^*\right)$$

where $\Tilde{N}$ is specified in (<ref>), and $\mathcal{I}_g^1, \ldots, \mathcal{I}_g^{T-1}$ are specified in Algorithm <ref>

We have the following result characterizing the asymptotic performance of the greedy algorithm.

Instate the hypothesis and notation of Theorem <ref>. As $t \to \infty$, we have the following: (a) $\mu_{\infty}^{\mathcal{I}}(\theta_q) = 0 \quad \forall \theta_q \notin F_{\theta_p}(\mathcal{I})$, and  (b) $\mu_{\infty}^{\mathcal{I}}(\theta_q) = \frac{1}{|F_{\theta_p}(\mathcal{I})|} \quad \forall \theta_q \in F_{\theta_p}(\mathcal{I})$. The near-optimal guarantees provided in Theorem <ref> for Problem <ref> hold with probability 1 (a.s.).

§ MINIMUM-PENALTY INFORMATION SET SELECTION

In this section, we consider the problem where the central node has a fixed budget for selecting information sources and seeks to minimize the maximum penalty of misclassifying the true state. Since the true state is not known a priori, the central designer has to minimize the maximum penalty for each possible true state, which is a multi-objective optimization problem under a budget constraint. We scalarize the multi-objective optimization into a single-objective optimization problem. The optimal solution to this single-objective problem is a Pareto optimal solution to the multi-objective problem (<cit.>). We now formalize the Minimum-Penalty Information Set Selection (MPIS) Problem as follows.

Consider a set $\Theta=\left\{\theta_1, \ldots, \theta_m\right\}$ of possible states of the world; a set $\mathcal{D}$ of information sources, with each source $i \in \mathcal{D}$ having a cost $c_i \in \mathbb{R}_{\geq0}$; a row-stochastic penalty matrix $ \Xi = [\xi_{ij}] \in \mathbb{R}^{m \times m}$ ; and a selection budget $K \in \mathbb{R}_{\geq0}$. The MPIS Problem is to find a set of selected information sources $\mathcal{I} \subseteq \mathcal{D}$ that solves

\begin{equation}
\label{eq:mpis}
\begin{aligned}
\min _{\mathcal{I} \subseteq \mathcal{D}} & \hspace{5pt} \displaystyle \sum_{\theta_p \in \Theta} \left(\max_{\theta_j \in F_{\theta_p}(\mathcal{I})} \xi_{pj} \right) ;
\hspace{2pt} \text { s.t. } \sum_{i \in \mathcal{I}} c_i \leq K.
\end{aligned}
\end{equation}

Consider the following equivalent optimization problem:

\begin{equation}
\label{eq:mpis_max}
\begin{aligned}
\max _{\mathcal{I} \subseteq \mathcal{D}} & \hspace{5pt} \displaystyle \sum_{\theta_p \in \Theta} \left(1-\max_{\theta_j \in F_{\theta_p}(\mathcal{I})} \xi_{pj} \right);
\hspace{2pt} \textit { s.t. } \sum_{i \in \mathcal{I}} c_i \leq K.
\end{aligned}
\end{equation}

It is easy to verify that the problem defined in (<ref>) is equivalent to the problem defined in (<ref>), i.e., the information set $\mathcal{I} \subseteq \mathcal{D}$ that optimizes the problem in Equation (<ref>) is also the optimal solution to the Problem <ref>.
We note that $f_{\theta_p}(\mathcal{I}) = 1-\max_{\theta_j \in F_{\theta_p}(\mathcal{I})} \xi_{pj}$. We denote $\Lambda(\mathcal{I}) = \sum_{\theta_p \in \Theta} f_{\theta_p}(\mathcal{I})$.

From Lemma <ref> and Lemma 3.12 in <cit.>, it follows that the objective function in (<ref>) is approximately submodular with the submodularity ratio $\gamma$. Based on the guarantees for greedy maximization of monotone, non-decreasing, approximately submodular functions subject to Knapsack constraints in Theorem 6 of <cit.>, we have the following result.
Greedy Algorithm for MPIS
Input: $\text{Data sources: }\mathcal{D},\text{Penalties: }  \Xi \in \mathbb{R}^{m \times m}, \text{Selection costs: }  c_i \hspace{2pt} \forall i \in \mathcal{D} , \text{Budget: } K \in \mathbb{R}_{>0}$

Output: $\mathcal{I}_K$
[1]
$t\gets 0, \mathcal{I}_K\gets\emptyset$
$t \leq K$
$j\gets\mathop{\arg\max}_{i\in{\mathcal{D}}\setminus\mathcal{I}_K} \frac{ \Lambda(\mathcal{I}_K \cup \{i\}) - \Lambda(\mathcal{I}_K)}{c_i}$
$\mathcal{I}_K\gets \mathcal{I}_K\cup\{j\}, t\gets t+c_j$
return $\mathcal{I}_K$

Let $\mathcal{I}_K \subseteq \mathcal{D}$ denote the information set selected by Algorithm <ref> and let $\mathcal{I}^*_K \subseteq \mathcal{D}$ denote the optimal information set for the MPIS Problem with submodularity ratio $\gamma$. For a specified threshold $\mu_{th} \in (0,1)$ and $0\leq\delta\leq1$, with probability at least $1-\delta$, Algorithm <ref> under $\Tilde{N}$ observation samples  returns a solution $\mathcal{I}_K$ to the MPIS problem (i.e., (<ref>)) that satisfies
$\Lambda(\mathcal{I}_K)  \geq \left(1 - e^{-\gamma} \right) \Lambda(\mathcal{I}^*_K) + c$ ,
where $c = \Lambda(\emptyset)/e^{\gamma}$ and $\Tilde{N}$ is specified in (<ref>).

We have the following result characterizing the asymptotic performance of the greedy algorithm.

Instate the hypothesis and notation of Theorem <ref>. As $t \to \infty$, we have the following: (a) $\mu_{\infty}^{\mathcal{I}}(\theta_q)= 0 \quad \forall \theta_q \notin F_{\theta_p}(\mathcal{I})$, and  (b) $\mu_{\infty}^{\mathcal{I}}(\theta_q) = \frac{1}{|F_{\theta_p}(\mathcal{I})|} \quad \forall \theta_q \in F_{\theta_p}(\mathcal{I})$. The near-optimal guarantees provided in Theorem <ref> for Problem <ref> hold with probability 1 (a.s.).

§ ALTERNATE PENALTY METRIC FOR INFORMATION SET SELECTION

In many practical scenarios, the submodularity ratio of the maximum penalty metric may be arbitrarily small (or zero) when misclassification penalties for two hypotheses are very close to each other (or equal) (see Appendix <ref> for a detailed discussion). It is also easy to verify that the submodularity ratio $\gamma$ decreases as the number of hypotheses increase. As a result, the performance bounds for the greedy algorithms become weaker. In such scenarios, one can turn to an alternate metric for optimization, which can provide non-trivial guarantees for the performance of the greedy algorithm. To this end, we present an alternate metric to characterize the quality of an information set, based on the total penalty of misclassification, defined as follows:

\begin{equation}
\label{eq:tot_pen}
\rho_{\theta_p}(\mathcal{I}) = \sum_{\theta_i \in F_{\theta_p}(\mathcal{I})} \xi_{pi}.
\end{equation}

Intuitively, in order to minimize the total penalty of misclassification ($\rho_{\theta_p}(\mathcal{I})$) (or ensure that it is bounded), one has to select a subset  $ \mathcal{I} \subseteq \mathcal{D}$ that ensures that the number of hypotheses which are observationally equivalent to the true hypothesis $\theta_p$, i.e., $|F_{\theta_p}(\mathcal{I})|$, is small and/or the hypotheses that are observationally equivalent to the true hypothesis have lower misclassification penalties. Effectively, this results in lower penalty associated with misclassifying the true hypothesis.

We define the Modified Minimum Cost Information Set Selection (M-MCIS) and Modified Minimum Penalty Information Set Selection (M-MPIS) Problems based on this metric as follows.

Consider a set $\Theta=\left\{\theta_1, \ldots, \theta_m\right\}$ of possible states of the world, a set $\mathcal{D}$ of information sources, a selection cost $c_i \in \mathbb{R}_{>0}$ of each source $i \in \mathcal{D}$, a row-stochastic penalty matrix $\Xi = [\xi_{ij}] \in \mathbb{R}^{m \times m}$, and prescribed penalty bounds $0 \leq R'_{\theta_p} \leq 1$ for all $\theta_p \in \Theta$. The M-MCIS Problem is to find a set of selected information sources $\mathcal{I} \subseteq \mathcal{D}$ that solves

\begin{equation}
\label{eq:mmcis}
\begin{aligned}
\min _{\mathcal{I} \subseteq \mathcal{D}} & \hspace{5pt} c(\mathcal{I}) ; \hspace{2pt}
\text { s.t. } \displaystyle \rho_{\theta_p} (\mathcal{I})  \leq R'_{\theta_p} \quad \forall \theta_p \in \Theta.
\end{aligned}
\end{equation}

Note that the penalty bounds $R_{\theta_p}$ of the MCIS Problem differ from the bounds $R'_{\theta_p}$ of M-MCIS Problem, as the former is a bound on the maximum penalty, while the latter is a bound on the total penalty. The designer can choose the bounds $R'_{\theta_p}$ in order to achieve the desired classification performance.

Consider a set $\Theta=\left\{\theta_1, \ldots, \theta_m\right\}$ of possible states of the world; a set $\mathcal{D}$ of information sources, with each source $i \in \mathcal{D}$ having a cost $c_i \in \mathbb{R}_{\geq0}$; a row-stochastic penalty matrix $ \Xi = [\xi_{ij}] \in \mathbb{R}^{m \times m}$ ; and a selection budget $K \in \mathbb{R}_{\geq0}$. The M-MPIS Problem is to find a set of selected information sources $\mathcal{I} \subseteq \mathcal{D}$ that solves

\begin{equation}
\label{eq:mmpis}
\begin{aligned}
\min _{\mathcal{I} \subseteq \mathcal{D}} & \hspace{5pt} \displaystyle \sum_{\theta_p \in \Theta} \rho_{\theta_p}(\mathcal{I}) ;
\hspace{2pt} \text { s.t. } \sum_{i \in \mathcal{I}} c_i \leq K.
\end{aligned}
\end{equation}

The function $g_{\theta_p}(\mathcal{I})= 1 -\rho_{\theta_p}(\mathcal{I}):2^{\mathcal{D}}\to \mathbb{R}_{\ge 0}$ is submodular for all $\theta_p \in \Theta$.

By Lemma <ref>, we have the following result characterizing the performance of the greedy algorithms for the modified information set selection problems.

For Algorithm <ref> (respectively Algorithm <ref>) applied to M-MCIS (respectively M-MPIS) Problem, the high-probability near-optimal guarantees provided in Theorem <ref> (respectively Theorem <ref>) hold with $\gamma=1$.

From Corollary <ref>, we have that the total penalty metric enjoys stronger near-optimal guarantees (due to submodularity) compared to that of the maximum penalty metric (which is weak submodular) for greedy optimization. Moreover, the near-optimal guarantees for the M-MCIS and M-MPIS problems are independent of the misclassification penalties and the number of hypotheses.

§ EMPIRICAL EVALUATION

In this section, we validate the theoretical results through numerical simulations. We present simulations for varying submodularity ratios, finite sample convergence of the beliefs and the modified information selection problems in Appendix <ref>.

We consider a hypothesis testing task where one has to identify (or classify) an aerial vehicle into one of the following $10$ classes: $\Theta =$  {cargo, passenger, freight, heavy fighter, interceptor, sailplane, hang glider, paraglider, surveillance UAV, quadrotor}. We will refer to this as the Aerial Vehicle Classification task (AVC task). The penalty matrix is as shown in Figure <ref> (a). Each row of the penalty matrix is normalized.  We set $|\mathcal{D}| = 10$, the costs $c_i$ for $i \in \mathcal{D}$ are sampled uniformly from $\{1,\hdots, 10\}$. We consider the infinite-observation case and randomly generate the observationally equivalent sets $F_{\theta_p}(i)$ for each $\theta_p \in \Theta$ and $i \in \mathcal{D}$. We first consider the minimum cost information set selection problem for the AVC task. The thresholds $R_{\theta_p}$ for $\theta_p \in \{ \textit{cargo, passenger, freight, sailplane, hang glider, paraglider}\}$ are randomly sampled from $[0.7,1]$ and for $\theta_p \in \{ \textit{heavy fighter, interceptor, surveillance UAV, quadrotor}\}$ are randomly sampled from $[0.1,0.4]$.
For 100 randomly generated instances, we run Algorithm <ref> to find the greedy information set $\mathcal{I}_g$ and find the optimal information set $\mathcal{I}^*$ using brute-force search. We plot the ratio of cost of the greedy information set to that of the optimal, i.e.,   $c(\mathcal{I}_g) / c(\mathcal{I^*}) $ in Figure <ref> (b).

(a) Penalty Matrix of AVC Problem, (b) Performance of Algorithm <ref> (for Problem <ref>), (c) Performance of Algorithm <ref> (for Problem <ref>).

Next, we consider the minimum penalty information set selection problem for the AVC task. We generate 100 random instances with varying information source costs and selection budgets. We run Algorithm <ref> to find the greedy information set $\mathcal{I}_g$ and find the optimal information set $\mathcal{I}^*$ using brute-force search. We plot the ratio of greedy utility to that of the optimal, i.e., $\Lambda(\mathcal{I}_g)/\Lambda(\mathcal{I^*})$ in Figure <ref>(c). These plots show the near-optimal performance of the greedy algorithm. Note that the penalty matrix for these instances does not satisfy Assumption 2 (uniqueness of misclassification penalties). Thus, these problem instances are not guaranteed to exhibit the weak submodularity property. Despite this, we observe that the greedy algorithms provide near-optimal performance.

§ CONCLUSION

In this work, we studied two variants of information set selection problem for hypothesis testing: (i) selecting a minimum cost information set to ensure the maximum penalty for misclassifying the true hypothesis remains bounded and (ii) optimal information set selection under a limited budget to minimize the maximum penalty of misclassifying the true hypothesis. Leveraging the weak submodularity property of the performance metric, we established high-probability guarantees for greedy algorithms for both the problems, along with the associated finite sample convergence rates for the Bayesian beliefs. Next, we proposed an alternate metric based on the total penalty of misclassification for information set selection, which enjoys (stronger) near-optimal performance guarantees with high-probability for the greedy algorithms. Finally, we evaluated the empirical performance of the proposed greedy algorithms over several randomly generated problem instances.
This material is based upon work supported by the Office of Naval Research (ONR) and Saab, Inc. under the Threat and Situational Understanding of Networked Online Machine Intelligence (TSUNOMI) program (grant no. N00014-23-C-1016). Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the ONR and/or Saab, Inc.

§ PROOFS

§.§ Proof of Theorem <ref>

Let the true state of the world be $\theta_p$ and let $\mu_0 (\theta) = \frac{1}{m} \hspace{5pt} \forall \theta \in \Theta$ (i.e., uniform prior). Under Assumption 1, for $\delta, \epsilon \in [0,1]$, and L as defined in Equation (<ref>), and for an information set $\mathcal{I} \subseteq \mathcal{D}$, the Bayesian update rule in Equation (<ref>) has the following property: there is an integer $N(\delta, \epsilon, L)$, such that with probability at least $1-\delta$, for all $t > N(\delta, \epsilon, L)$ we have the following:

* $\mu_t^{\mathcal{I}}(\theta_q) =  \mu_t^{\mathcal{I}}(\theta_p)  \hspace{5pt} \forall \theta_q \in F_{\theta_p}(\mathcal{I})$, and

* $\mu_t^{\mathcal{I}}(\theta_q) \leq \exp{(-t(|K(\theta_p, \theta_q)-\epsilon|))} \hspace{5pt} \forall \theta_q \notin F_{\theta_p}(\mathcal{I})$;

where $K(\theta_p, \theta_q) = D_{KL}(\ell_{\mathcal{I}}(\cdot | \theta_p) || \ell_{\mathcal{I}}(\cdot | \theta_q) )$ is the Kullback-Leibler divergence measure between the likelihood functions $\ell_{\mathcal{I}}(\cdot | \theta_p)$ and $ \ell_{\mathcal{I}}(\cdot | \theta_q) $, $F_{\theta_p}(\mathcal{I})$ is defined in (<ref>), and

\begin{equation}
N(\delta, \epsilon,L) = \left\lceil \frac{2L^2}{\epsilon^2 } \log \frac{2}{\delta} \right\rceil.
% N(\delta, \epsilon) = \left\lceil \frac{\sigma^2}{\epsilon^2 \delta} \right\rceil.
% \\
% \sigma^2 = \text{Var} \left[\log \frac{\ell(\cdot | \theta_q)}{\ell(\cdot | \theta_p)}\right].
\end{equation}

The arguments presented in this proof are similar to Lemma 1 in <cit.>. Consider a class $\theta_q = \Theta \setminus \theta_p$, which is not the true state of the world. We now define, for all $\theta_q \in \Theta \setminus \theta_p$ and for all $k \in \mathbb{N}_+$,  the following:

\begin{equation}
\label{eq:alpha}
\phi_k^{\mathcal{I}}(\theta_q) = \log \frac{\mu_k^{\mathcal{I}}(\theta_q)}{\mu_k^{\mathcal{I}}(\theta_p)} \hspace{4pt}\text{and}\hspace{4pt} \eta_k^{\mathcal{I}}(\theta_q) = \log \frac{\ell_{\mathcal{I}}(o_k^{\mathcal{I}}|\theta_q)}{\ell_{\mathcal{I}}(o_k^{\mathcal{I}}|\theta_p)},
\end{equation}

where $o_k^{\mathcal{I}} \in \mathcal{O}_{\mathcal{I}}$ is the joint observation  and $\ell_{\mathcal{I}}(\cdot)$ is the joint likelihood function of the information set $\mathcal{I} \subseteq \mathcal{D}$. From the Bayesian update rule in Equation (<ref>), we have:

\begin{equation}
\label{eq:alpha_beta}
\phi_{t}^{\mathcal{I}}(\theta_q) = \phi_0^{\mathcal{I}}(\theta_q) + \sum_{k=1}^{t}\eta_k^{\mathcal{I}}(\theta_q).
\end{equation}

Since we assume a uniform prior, i.e., $\mu_0 (\theta) = \frac{1}{m} \hspace{5pt} \forall \theta \in \Theta$, we have that $\phi_0^{\mathcal{I}}(\theta_q) =0 \hspace{4pt} \forall \theta_q \in \Theta \setminus \theta_p$ and thus $ \phi_{t}^{\mathcal{I}}(\theta_q) =  \sum_{k=1}^{t}\eta_k^{\mathcal{I}}(\theta_q), \hspace{4pt} \forall t \in \mathbb{N}_+$. Note that $\{ \eta_k^{\mathcal{I}}(\theta_q) \}$ is a sequence of i.i.d. random variables which are bounded and have a finite mean (by Equation <ref>). Each random variable $\eta_k^{\mathcal{I}}(\theta_q)$ has a mean given by $-K(\theta_p, \theta_q)$, where the mean is obtained by using the expectation operator $\mathbb{E}^{\theta_p}[\cdot]$ associated with the probability measure $\mathbb{P}^{\theta_p}$ as defined in Section <ref>. By the strong law of large numbers, we have that $\frac{1}{t} \sum_{k=1}^{t}\eta_k^{\mathcal{I}}(\theta_q) \to -K(\theta_p, \theta_q) $ asymptotically almost surely (a.a.s.).

If $\theta_q \in F_{\theta_p}(\mathcal{I})$, we know from (<ref>) that $\eta_k^{\mathcal{I}}(\theta_q) = 0$ for all $k \in \{1,\hdots, t\}$, and thus we have $\phi_{t}^{\mathcal{I}}(\theta_q) = 0$ for all $t \in \mathbb{N}_+$. This directly implies that $\mu_t^{\mathcal{I}}(\theta_q) =  \mu_t^{\mathcal{I}}(\theta_p)  \hspace{5pt} \forall \theta_q \in F_{\theta_p}(\mathcal{I})$, establishing part (a) of the result. Let $\hat{K}(\theta_p, \theta_q) = - \frac{1}{t} \sum_{k=1}^{t}\eta_k^{\mathcal{I}}(\theta_q)$ denote the sample mean (estimated KL divergence). Now consider a state $\theta_q \notin F_{\theta_p}(\mathcal{I})$, Equation (<ref>) can be equivalently written as

\begin{equation}
\label{eq:bel_eq}
\mu_t^{\mathcal{I}}(\theta_q) = \mu_t^{\mathcal{I}}(\theta_p) \exp{\left( t. \frac{1}{t}\sum_{k=1}^{t}\eta_k^{\mathcal{I}}(\theta_q)\right)} = \mu_t^{\mathcal{I}}(\theta_p) \exp{( -t \hat{K}(\theta_p,\theta_q) )}.
\end{equation}

By Equation (<ref>) and Hoeffding's Inequality (<cit.>), for all $\epsilon>0$, we have the following:

\begin{equation}
\mathbb{P} \left( \left| \frac{1}{t} \sum_{k=1}^{t}\eta_k^{\mathcal{I}}(\theta_q) - (-K(\theta_p, \theta_q)) \right| \geq \epsilon  \right) \leq 2 \exp{\left( -\frac{ \epsilon^2 t}{2L^2} \right)}.
\end{equation}

This condition is equivalent to:

\begin{equation}
\label{eq:hoeffding}
\mathbb{P} \left( \left| \frac{1}{t} \sum_{k=1}^{t}\eta_k^{\mathcal{I}}(\theta_q) - (-K(\theta_p, \theta_q)) \right| \leq \epsilon  \right) \geq 1- 2\exp{\left( -\frac{ \epsilon^2 t}{2L^2} \right)}.
\end{equation}

Now let $\delta = 2\exp{\left( -\frac{ \epsilon^2 t}{2L^2}\right)}$ which yields $t =  \frac{2L^2}{\epsilon^2 } \log \frac{2}{\delta}$. The condition in Equation (<ref>) means that, with probability at least $1-\delta$, we have that $\left|-\hat{K}(\theta_p, \theta_q)  - (-K(\theta_p, \theta_q)) \right| \leq \epsilon$, for all $t \geq \frac{2L^2}{\epsilon^2 } \log \frac{2}{\delta}$. We know that $\mu_t^{\mathcal{I}}(\theta_p) \leq 1$ for any $t \in \mathbb{N}_+$. Now, by combining Equations (<ref>) and (<ref>), with probability at least $1-\delta$, for all $t > N(\delta,\epsilon,L)$, we have

\begin{equation}
\label{eq:bel_bound}
\mu_t^{\mathcal{I}}(\theta_q) \leq \exp{(-t(|K(\theta_p, \theta_q)-\epsilon|))} \hspace{5pt} \quad \forall \theta_q \notin F_{\theta_p}(\mathcal{I}),
\end{equation}

where $N(\delta,\epsilon,L) = \left\lceil \frac{2L^2}{\epsilon^2 } \log \frac{2}{\delta} \right\rceil$, establishing part (b) of the result.

§.§ Proof of Corollary <ref>

Instate the hypothesis and notation of Theorem <ref>. For a specified threshold $\mu_{th}\in    (0,1)$ for the belief over any class $\theta_q \notin F_{\theta_p}(\mathcal{I}) $, there exists $\delta, \epsilon \in [0,1]$, for which one can guarantee with probability at least $1-\delta$ that $\mu_t^{\mathcal{I}}(\theta_q) \leq \mu_{th}$  for all $\theta_q \notin F_{\theta_p}$ and for all $t > \Tilde{N}$, where

\begin{equation}
\Tilde{N} = \left\lceil  \max \left\{ \frac{2L^2}{\epsilon^2 } \log \frac{2}{\delta} , \frac{1}{ \displaystyle\min_{\theta_p,\theta_q \in \Theta} |K(\theta_p,\theta_q) -\epsilon| } \log \frac{1}{\mu_{th}}   \right\} \right\rceil.
\end{equation}

From Theorem <ref>, we know that with probability at least $1-\delta$, for all $t > N(\delta,\epsilon,L)$, we have

\begin{equation}
\mu_t^{\mathcal{I}}(\theta_q) \leq \exp{(-t(|K(\theta_p, \theta_q)-\epsilon|))} \hspace{5pt} \quad \forall \theta_q \notin F_{\theta_p}(\mathcal{I}),
\end{equation}

where $N(\delta,\epsilon,L) = \left\lceil \frac{2L^2}{\epsilon^2 } \log \frac{2}{\delta} \right\rceil$. Since we require $\mu_t^{\mathcal{I}}(\theta_q) \leq \mu_{th}$  for all $\theta_q \notin F_{\theta_p}$, we let

\begin{equation}
\exp{(-t(|K(\theta_p, \theta_q)-\epsilon|))}  <  \mu_{th}\hspace{5pt} \quad \forall \theta_q \notin F_{\theta_p}(\mathcal{I}) .
\end{equation}

Re-arranging the terms in the above equation, we get

\begin{equation}
t > \frac{1}{|K(\theta_p, \theta_q)-\epsilon|} \log \frac{1}{\mu_{th}}
\end{equation}

In order to ensure $\mu_t^{\mathcal{I}}(\theta_q) \leq \mu_{th} \quad \forall \theta_q \notin F_{\theta_p}(\mathcal{I}) $ is satisfied for any true hypothesis $\theta_p \in \Theta$, we need the following condition to be satisfied.

\begin{equation}
\label{eq:ts}
t >   \frac{1}{\displaystyle\min_{\theta_p, \theta_q \in \Theta}|K(\theta_p, \theta_q)-\epsilon|} \log \frac{1}{\mu_{th}}
\end{equation}

In other words, the number of samples required for the beliefs over the hypotheses $\theta_q \notin F_{\theta_p}(\mathcal{I})$ to be bounded under the specified threshold $\mu_{th}$ depends on the least KL divergence measure between the likelihood functions of any $\theta_q \notin F_{\theta_p}(\mathcal{I})$ and $\theta_p$, over all possible true hypotheses $\theta_p \in \Theta$.
From Equation (<ref>) and the fact that $t>N(\delta,\epsilon,L)$, we obtain $\Tilde{N}$.

§.§ Proof of Lemma <ref>

Under Assumption 2, the function $f_{\theta_p}(\mathcal{I}) :2^{\mathcal{D} }\to\mathbb{R}_{\geq0} $ is approximately submodular for all $\theta_p \in \Theta$, with a submodularity ratio $\gamma = \underline{\xi}/ \Bar{\xi} $, where

\begin{align}
\label{eq:xifloor_1}
\displaystyle \underline{\xi} &= \min_{\theta_p \in \Theta} \left(\min_{\theta_i,\theta_j \in \Theta}  |\xi_{pi} - \xi_{pj}|\right); \\
\label{eq:xibar}
\Bar{\xi} &= \max_{\theta_p \in \Theta} \left(\max_{\theta_i,\theta_j \in \Theta}  |\xi_{pi} - \xi_{pj}|\right).
\end{align}

Recall that $f_{\theta_p}(\mathcal{I}) =1- \max_{\theta_j\in F_{\theta_p}(\mathcal{I})} \xi_{pj}.$  We begin by proving the following statement:

\begin{equation}
\sum_{a \in A \setminus B} (\ef(\{a\} \cup B) - \ef(B)) = 0 \implies  \ef(A \cup B) - \ef(B) = 0.
\end{equation}

Now let $\sum_{a \in A \setminus B} (\ef(\{a\} \cup B) - \ef(B)) = 0.$ This implies

\begin{align}
\ef(\{a\} \cup B) - \ef(B) &= 0 \quad \forall a \in A \setminus B \\
\max_{\theta_i \in F_{\theta_p}(B)} \xi_{pi} - \max_{\theta_i \in F_{\theta_p}(\{a\} \cup B)} \xi_{pi} &= 0 \quad \forall a \in A \setminus B \\
\max_{\theta_i \in F_{\theta_p}(B)} \xi_{pi} - \max_{\theta_i \in F_{\theta_p}(a) \cap F_{\theta_p}( B)} \xi_{pi} &= 0 \quad \forall a \in A \setminus B \\ \label{eq:lhs_bound}
\max_{\theta_i \in F_{\theta_p}(B)}  \xi_{pi} = \max_{\theta_i \in F_{\theta_p}(a) \cap F_{\theta_p}( B)} \xi_{pi}   & \quad \quad \forall a \in A \setminus B.
\end{align}

Let $\displaystyle\max_{ \theta_i \in F_{\theta_p}(B)} \xi_{pi} = \xi_{pq}$ for $\theta_q \in F_{\theta_p}(B)$. From Equation (<ref>) and Assumption 2, we have

\begin{equation}
\displaystyle \max_{\theta_i \in F_{\theta_p}(a) \cap F_{\theta_p}( B)} \xi_{pi} = \xi_{pq} \quad \forall a \in A \setminus B,
\end{equation}

and it follows that $\theta_q \in F_{\theta_p}(a) \cap F_{\theta_p}( B), \forall a \in A \setminus B$.

We have the following: $\displaystyle \ef(A \cup B) - \ef(B)= \max_{\theta_i \in F_{\theta_p}(B)} \xi_{pi} - \max_{\theta_i \in F_{\theta_p}(A \cup B)} \xi_{pi}$.

Using the fact that $A \cup B = (A \setminus B) \cup B$, we have $F_{\theta_p}(A \cup B) = F_{\theta_p}(A\setminus B) \cap F_{\theta_p}(B).$

Thus, we have

\begin{align}
\label{eq:rhs_exp}
\displaystyle \ef(A \cup B) - \ef(B)= & \max_{\theta_i \in F_{\theta_p}(B)} \xi_{pi} - \max_{\theta_i \in F_{\theta_p}(A\setminus B) \cap F_{\theta_p}(B)} \xi_{pi}.
\end{align}

From the previous argument, we have $\theta_q \in F_{\theta_p}(a) \cap F_{\theta_p}( B), \forall a \in A \setminus B$ and $\displaystyle\max_{ \theta_i \in F_{\theta_p}(B)} \xi_{pi} = \xi_{pq}$ for $\theta_q \in F_{\theta_p}(B).$ Since $F_{\theta_p}(A \setminus B) = \displaystyle \bigcap_{a \in A \setminus B} F_{\theta_p}(a)$, we have
$$F_{\theta_p}(A\setminus B) \cap F_{\theta_p}(B) = \left( \displaystyle \bigcap_{a \in A \setminus B} F_{\theta_p}(a) \right) \bigcap F_{\theta_p}(B).$$
This implies $\theta_q \in F_{\theta_p}(A\setminus B) \cap F_{\theta_p}( B).$ It directly follows that

\begin{equation}
\max_{\theta_i \in F_{\theta_p}(B)} \xi_{pi} = \max_{\theta_i \in F_{\theta_p}(A\setminus B) \cap F_{\theta_p}(B)} \xi_{pi} = \xi_{pq}.
\end{equation}

Thus, we have $\ef(A \cup B) - \ef(B) = 0$. This gives the trivial bound of $\gamma \le 1$ (since we define $0/0=1$ for characterizing $\gamma$ (see <cit.>)). Therefore, in order to establish a non-trivial lower bound on $\gamma$, we consider $\sum_{a \in A \setminus B} (\ef(\{a\} \cup B) - \ef(B)) > 0.$

We now proceed to establish a non-trivial lower bound on $\sum_{a \in A \setminus B} (\ef(\{a\} \cup B) - \ef(B)).$

\begin{align}
\sum_{a \in A \setminus B} (\ef(\{a\} \cup B) - \ef(B)) &= \sum_{a \in A \setminus B} \left(\max_{\theta_i \in F_{\theta_p}(B)} \xi_{pi} - \max_{\theta_i \in F_{\theta_p}(\{a\} \cup B)} \xi_{pi}\right);\\
& \geq \min_{\theta_i, \theta_j \in \Theta} |\xi_{pi} - \xi_{pj}|.
\end{align}

For all $\theta_p \in \Theta$ and for all $A, B \subseteq \mathcal{D}$, we have

\begin{equation}
\label{eq:lb}
\sum_{a \in A \setminus B} (\ef(\{a\} \cup B) - \ef(B)) \ge \min_{\theta_p  \in \Theta} \left( \min_{\theta_i, \theta_j \in \Theta} |\xi_{pi} - \xi_{pj}| \right) = \underline{\xi}. \quad \text{(Equation (\ref{eq:xifloor_1}))}
\end{equation}

Next, we provide an upper bound on $\displaystyle \ef(A \cup B) - \ef(B).$

\begin{align}
\ef(A \cup B) - \ef(B) &=  \max_{\theta_i \in F_{\theta_p}(B)} \xi_{pi} - \max_{\theta_i \in F_{\theta_p}(A \cup B)} \xi_{pi} \\
& \leq \max_{\theta_i, \theta_j \in \Theta} |\xi_{pi} - \xi_{pj} |.
\end{align}

For all $\theta_p \in \Theta$ and for all $A, B \subseteq \mathcal{D}$, we have

\begin{equation}
\label{eq:ub}
\ef(A \cup B) - \ef(B) \le \max_{\theta_p  \in \Theta} \left( \max_{\theta_i, \theta_j \in \Theta} |\xi_{pi} - \xi_{pj}| \right) = \Bar{\xi}. \quad \text{(Equation (\ref{eq:xibar}))}
\end{equation}

Due to Assumption 2, we have $0< \underline{\xi}<1$ and $0< \Bar{\xi} < 1$.
Combining inequalities (<ref>), (<ref>) and (<ref>), we have that the function $f_{\theta_p}(\mathcal{I})$ is approximately submodular with a submodularity ratio $\gamma = \underline{\xi}/\Bar{\xi}$, for all $\theta_p \in \Theta$.

§.§ Proof of Lemma <ref>

For any $\mathcal{I} \subseteq\mathcal{D}$, the constraint $1-\max_{\theta_i \in F_{\theta_p}(\mathcal{I})} \xi_{pi} \geq 1-R_{\theta_p}$ holds for all $\theta_p \in \Theta$ if and only if $\sum_{\theta_p \in \Theta} f_{\theta_p}^{\prime}(\mathcal{I})=\sum_{\theta_p \in \Theta} f_{\theta_p}^{\prime}(\mathcal{D})$.

Suppose the constraints $1-\max_{\theta_i \in F_{\theta_p}(\mathcal{I})} \xi_{pi} \geq 1-R_{\theta_p}$ hold for all $\theta_p \in \Theta$. It follows that $f_{\theta_p}^{\prime}(\mathcal{I})= 1-R_{\theta_p}$ for all $\theta_p \in \Theta$. Noting that, $f_{\theta_p}(\mathcal{D}) \geq 1-R_{\theta_p}$, we have $f_{\theta_p}^{\prime}(\mathcal{D})=1-R_{\theta_p}$ for all $\theta_p \in \Theta$, which implies $\sum_{\theta_p \in \Theta} f_{\theta_p}^{\prime}(\mathcal{I})=\sum_{\theta_p \in \Theta} f_{\theta_p}^{\prime}(\mathcal{D})$. Conversely, suppose $\sum_{\theta_p \in \Theta} f_{\theta_p}^{\prime}(\mathcal{I})=\sum_{\theta_p \in \Theta} f_{\theta_p}^{\prime}(\mathcal{D})$, i.e., $\sum_{\theta_p \in \Theta}\left(f_{\theta_p}^{\prime}(\mathcal{I})-\left(1-R_{\theta_p}\right)\right)=0$. Noting that $f_{\theta_p}^{\prime}(\mathcal{I}) \leq 1-R_{\theta_p}$ for all $\mathcal{I} \subseteq\mathcal{D}$, we have $f_{\theta_p}^{\prime}(\mathcal{I})=1-R_{\theta_p}$ for all $\theta_p \in \Theta$, i.e., $f_{\theta_p}(\mathcal{I}) \geq 1-R_{\theta_p}$ for all $\theta_p \in \Theta$. This completes the proof of the lemma.

§.§ Proof of Theorem <ref>

The performance guarantees presented in this result are that of the approximate submodular set covering problem in Theorem 9 of <cit.>, where

\begin{align}
\gamma_{S^{NG},k^*(C)}(f) &= \gamma;\\
C &= z(\mathcal{D}) - z(\mathcal{\emptyset}) ;\\
k &= c(\mathcal{I}_g);\\
k^*(C) &= c(\mathcal{I}^*);\\
f(S_{k-1}^{NG}) &= z(\mathcal{I}_g^{T-1}) - z(\mathcal{\emptyset}).
\end{align}

With probability at least $1-\delta$, Algorithm <ref>, under $\Tilde{N}(\epsilon, \delta, L)$ observation samples, enjoys the same performance guarantees, where $\delta, \epsilon$ are specified by the central designer.

§.§ Proof of Corollary <ref>

Instate the hypothesis and notation of Theorem <ref>. As $t \to \infty$, we have the following: (a) $\mu_{\infty}^{\mathcal{I}}(\theta_q) = 0 \quad \forall \theta_q \notin F_{\theta_p}(\mathcal{I})$, and  (b) $\mu_{\infty}^{\mathcal{I}}(\theta_q) = \frac{1}{|F_{\theta_p}(\mathcal{I})|} \quad \forall \theta_q \in F_{\theta_p}(\mathcal{I})$. The near-optimal guarantees provided in Theorem <ref> for Problem <ref> hold with probability 1 (a.a.s.).

From Theorem <ref>, the following hold for $t \to \infty$:

* $\mu_t^{\mathcal{I}}(\theta_q) =  \mu_t^{\mathcal{I}}(\theta_p)  \hspace{5pt} \forall \theta_q \in F_{\theta_p}(\mathcal{I})$, and

* $\mu_t^{\mathcal{I}}(\theta_q) \leq \exp{(-t(|K(\theta_p, \theta_q)-\epsilon|))} \hspace{5pt} \forall \theta_q \notin F_{\theta_p}(\mathcal{I})$;

We have $\lim_{t \to \infty} \mu_t^{\mathcal{I}}(\theta_q) = 0 \quad \forall \theta_q \notin F_{\theta_p}(\mathcal{I}) $ and $\mu_t^{\mathcal{I}}(\theta_q) =  \mu_t^{\mathcal{I}}(\theta_p)  \hspace{5pt} \forall \theta_q \in F_{\theta_p}(\mathcal{I})$. Since $\sum_{\theta \in \Theta} \mu_t^{\mathcal{I}}(\theta) = 1$ for all $t$, we have $\lim_{t \to \infty}  \mu_{t}^{\mathcal{I}}(\theta_q)= \frac{1}{|F_{\theta_p}(\mathcal{I})|} \quad \forall \theta_q \in F_{\theta_p}(\mathcal{I})$.
Since we have $\lim_{t \to \infty} \mu_t^{\mathcal{I}}(\theta_q) = 0 \quad \forall \theta_q \notin F_{\theta_p}(\mathcal{I}) $, the central designer will predict one of the hypotheses $\theta_q \in F_{\theta_p}(\mathcal{I})$ as the true state of the world, with probability 1. Therefore, the guarantees provided in Theorem <ref> for Problem <ref> hold with probability 1.

§.§ Proof of Theorem <ref>

The performance guarantees presented in this result are that of the approximate submodular maximization under Knapsack constraints in Theorem 6 of <cit.>, where

\begin{align}
\gamma_{S^{NG},k}(f) &= \gamma;\\
f(S^{NG}) &= \Lambda(\mathcal{I}_g) - \Lambda(\mathcal{\emptyset});\\
OPT &= \Lambda(\mathcal{I}^*) - \Lambda(\mathcal{\emptyset}).
\end{align}

With probability at least $1-\delta$, Algorithm <ref>, under $\Tilde{N}(\epsilon, \delta, L)$ observation samples, enjoys the same performance guarantees, where $\delta, \epsilon$ are specified by the central designer.

§.§ Proof of Corollary <ref>

The construction of the proof and arguments are similar to those presented in Corollary <ref>.

§.§ Proof of Lemma <ref>

We first begin by defining a submodular set function.

A set function $f:2^{\Omega }\to\mathbb{R}$ is submodular if it satisfies $f(X\cup\{j\})-f(X)\ge f(Y\cup\{j\})-f(Y)$, $\forall X\subseteq Y\subseteq \Omega $ and  $ \forall j\in \Omega \setminus Y$.

We now establish the following result.
The function $ g_{\theta_p}(\mathcal{I}):2^{\mathcal{D} }\to\mathbb{R}_{\geq0} $ is submodular for all $\theta_p \in \Theta$.

Recall that $g_{\theta_p}(\mathcal{I}) = 1 - \sum_{\theta_i \in F_{\theta_p}(\mathcal{I})} \xi_{pi}.$ Consider any $\mathcal{I}_1 \subseteq \mathcal{I}_2 \subseteq\mathcal{D}$ and any $j \in \mathcal{D} \backslash \mathcal{I}_2$. We have the following:

\begin{aligned}
g_{\theta_p}\left(\mathcal{I}_1 \cup\{j\}\right) - g_{\theta_p}\left(\mathcal{I}_1\right)
= & \sum_{\theta_i \in F_{\theta_p}\left(\mathcal{I}_1\right)} \xi_{pi} - \sum_{\theta_i \in F_{\theta_p}\left(\mathcal{I}_1 \cup\{j\}\right)}  \xi_{pi}  \\
= & \sum_{\theta_i \in F_{\theta_p}\left(\mathcal{I}_1\right)} \xi_{pi} -\sum_{\theta_i \in F_{\theta_p}\left(\mathcal{I}_1\right) \cap F_{\theta_p}(j)} \xi_{pi} \\
= & \sum_{\theta_i \in  F_{\theta_p}\left(\mathcal{I}_1\right) \backslash \left(F_{\theta_p}\left(\mathcal{I}_1\right) \cap F_{\theta_p}(j)\right)} \xi_{pi}\\
=&\sum_{\theta_i \in F_{\theta_p}(\mathcal{I}_1) \backslash F_{\theta_p}\left(j\right)} \xi_{pi} .
\end{aligned}

Note that the above arguments follow from  De Morgan's laws. Similarly, we  have

g_{\theta_p}\left(\mathcal{I}_2 \cup\{j\}\right)- g_{\theta_p}\left(\mathcal{I}_2\right)=\sum_{\theta_i \in F_{\theta_p}(\mathcal{I}_2) \backslash F_{\theta_p}\left(j\right)} \xi_{pi} .

Since $\mathcal{I}_1 \subseteq \mathcal{I}_2$, we have $F_{\theta_p}(\mathcal{I}_2) \backslash F_{\theta_p}\left(j\right) \subseteq F_{\theta_p}(\mathcal{I}_1) \backslash F_{\theta_p}\left(j\right)$. Thus,

g_{\theta_p}\left(\mathcal{I}_1 \cup\{j\}\right) - g_{\theta_p}\left(\mathcal{I}_1\right) \geq g_{\theta_p}\left(\mathcal{I}_2 \cup\{j\}\right)-g_{\theta_p}\left(\mathcal{I}_2\right) .

Since the above arguments hold for all $\theta_p \in \Theta$, the function $g_{\theta_p}(\cdot)$ is submodular for all $\theta_p \in \Theta$.

§.§ Proof of Corollary <ref>

For Algorithm <ref> (respectively Algorithm <ref>) applied to M-MCIS (respectively M-MPIS) Problem, the high-probability near-optimal guarantees provided in Theorem <ref> (respectively Theorem <ref>) hold with $\gamma=1$.

Consider the M-MCIS problem defined in (<ref>). Based on similar arguments as in Section <ref>, we can transform the M-MCIS Problem into the set covering problem defined in (<ref>), where the constraints $z(\cdot)$ are expressed in terms of $g_{\theta_p}(\cdot)$ and $R'_{\theta_p}$ instead of $f_{\theta_p}(\cdot)$ and $R_{\theta_p}$, as follows.

\begin{equation}
z(\mathcal{I}) = \sum_{\theta_p \in \Theta} \min \{ g_{\theta_p}(\mathcal{I}), 1-R'_{\theta_p}\}.
\end{equation}

It follows from Lemma <ref> that  $z(\cdot)$ is submodular. Since we have $\gamma \ge 1$ for submodular functions (<cit.>), the guarantees presented in Theorem <ref> for Algorithm <ref> hold with $\gamma=1$ for the M-MCIS problem.

Now consider the M-MPIS problem. We now define the following optimization problem.

\begin{equation}
\label{eq:mmpis_max}
\begin{aligned}
\max _{\mathcal{I} \subseteq \mathcal{D}} & \hspace{5pt} \displaystyle \sum_{\theta_p \in \Theta} \left(1- \rho_{\theta_p}(\mathcal{I}) \right);
\hspace{2pt} \textit { s.t. } \sum_{i \in \mathcal{I}} c_i \leq K.
\end{aligned}
\end{equation}

It is easy to verify that the problem defined in (<ref>) is equivalent to the problem defined in (<ref>), i.e., the information set $\mathcal{I} \subseteq \mathcal{D}$ that optimizes the problem in Equation (<ref>) is also the optimal solution to the Problem <ref>. It follows from Lemma <ref> that the objective function of the Problem (<ref>) is submodular. Since we have $\gamma \ge 1$ for submodular functions (<cit.>), the guarantees presented in Theorem <ref> for Algorithm <ref> hold with $\gamma=1$ for the M-MPIS problem.

§ LIMITATIONS OF APPROXIMATE SUBMODULARITY

In this section, we present insights into the effect of the penalty values on the submodularity ratio and the performance bounds of greedy algorithms. We recall that the submodularity ratio is given by $\gamma = \underline{\xi}/ \Bar{\xi} $, where

\begin{align}
\displaystyle \underline{\xi} &= \min_{\theta_p \in \Theta} \left(\min_{\theta_i,\theta_j \in \Theta}  |\xi_{pi} - \xi_{pj}|\right); \\
\Bar{\xi} &= \max_{\theta_p \in \Theta} \left(\max_{\theta_i,\theta_j \in \Theta}  |\xi_{pi} - \xi_{pj}|\right).
\end{align}

Assumption 2 requires that the misclassification penalties are unique, i.e., $\xi_{pi} \neq \xi_{pj}$ for $i \neq j$, for all $\theta_p \in \Theta$. However, in many practical scenarios, one may have equal (or arbitrarily close) misclassification penalties, as in the Aerial Vehicle Classification task considered in this paper. This leads to a trivial lower bound on the submodularity ratio, i.e., $\gamma \geq 0$. In such cases, one may attempt to provide an improved lower bound on the submodularity ratio $\gamma$ using problem specific insights, which is strictly bounded away from 0. Now consider the following example.

Example 1:  Consider an instance of the MPIS Problem with $\Theta = \{\theta_1, \theta_2, \theta_3 \}$ and the penalty matrix given by

\begin{equation*}
\Xi = \begin{bmatrix}
0 & 0.5 & 0.5\\
0.5 & 0 & 0.5\\
0.5 & 0.5 &0
\end{bmatrix}.
\end{equation*}
Let the set of available information sources be $\mathcal{D} = \{ i_1, i_2 \}$, with $c_1=c_2=1.$ Let the true hypothesis be $\theta_p = \theta_1$. Without loss of generality, the arguments below hold true for the cases with $\theta_p=\theta_2$ and $\theta_p = \theta_3$. Let $F_{\theta_1}(i_1) = \{\theta_1,\theta_2\}$ and $F_{\theta_1}(i_2) = \{\theta_1, \theta_3\}$. We will now characterize the submodularity ratio for this problem instance. We need to provide a lower bound on $\gamma$, which is given by

\begin{equation}
\gamma \leq \frac{\sum_{a \in A \setminus B} (f(\{a\} \cup B) - f(B))}{f(A \cup B) - f(B)},
\end{equation}

for all $A,B \subseteq \mathcal{D}$, where $0/0$ is defined as 1. In order to provide non-trivial bounds on the performance of greedy algorithm, $\gamma$ should be strictly bounded away from 0. However, consider the following: $A = \{i_1, i_2\}$ and $B = \emptyset$. It is easy to see that $\sum_{a \in A \setminus B} (f(\{a\} \cup B) - f(B)) = 0$ and $f(A \cup B) - f(B) = 0.5$, where $f(\mathcal{I}) = 1 - \max_{\theta_i \in F_{\theta_1}(\mathcal{I})} \xi_{1i}.$ Thus, it follows that the lower bound on $\gamma$ is zero, which is trivial. Therefore, there exist many instances of these problems where one may not be able to provide meaningful (and non-trivial) guarantees for the near-optimality of the greedy algorithms.

Instead, one can turn to an alternate optimization metric, which can provide non-trivial and near-optimal bounds for approximating the optimal solution (see Section <ref>). However, establishing  performance guarantees for optimizing the alternate metric (i.e., total penalty of misclassification) in place of the actual metric (i.e., maximum penalty of misclassification) is still an open question.

§ ADDITIONAL EXPERIMENTS

§.§ Finite Sample Convergence of Bayesian beliefs

We consider an instance of Problem <ref> with number of states $\Theta = 10$ and show the finite sample convergence of beliefs. We randomly sample the observationally equivalent set $F_{\theta_p}(\mathcal{I})$ for an information set $\mathcal{I} \in \mathcal{D}$. We start with a uniform prior and apply the Bayesian update rule as in (<ref>). Figure <ref> shows convergence of beliefs under $50$ observation samples. It can be verified that the beliefs over the states not in the observationally equivalent set of the true state $\theta_p = 0$ get arbitrarily close to zero and the beliefs over the states which are observationally equivalent to the true state $\theta_p = 0$,  i.e., $\{1,5,7,8\}$ are all equal to $0.2$, validating the results presented in Theorem <ref>.

Finite Sample Convergence of Bayesian Beliefs

§.§ Performance of Greedy Algorithm for Varying Submodularity Ratios

In this section, we present numerical simulations to evaluate the performance of Algorithm <ref> (for MCIS Problem) and Algorithm <ref> (for MPIS problem) with varying submodularity ratios of the problem instances. Note that the submodularity ratio only depends on the penalty matrix entries.  We generate a set of 5 penalty matrices $\mathcal{P} = \{ \Xi_1, \Xi_2, \Xi_3, \Xi_4, \Xi_5 \}$, corresponding to submodularity ratio bounds $\gamma \in \{0.1, 0.2, 0.3, 0.4, 0.5 \}$, respectively. In other words, these penalty matrices ensure that the submodularity ratio for these instances are at least $\gamma$. We set  $|\mathcal{D}| = 10$. We consider the scenario with infinite observation samples, where the constraints in (<ref>) can be completely specified by $F_{\theta_p}(i)$ for all $\theta_p \in \Theta$ and for all $i \in \mathcal{D}$, which capture the underlying likelihood functions $\ell_i(\cdot|\theta_p)$. We randomly generate the set $F_{\theta_p}(i)$ for all $i \in \mathcal{D}$ and for all $\theta_p \in \Theta$. For each penalty matrix $\Xi_i \in \mathcal{P}$, we generate 20 random instances of the MCIS problem with varying penalty thresholds and information set costs. We run Algorithm <ref> to generate the greedy information set and find the optimal set through brute-force search. We plot the distributions of the ratio of cost of information set generated by greedy to that of the optimal in Figure <ref>(a). Similarly, for each penalty matrix $\Xi_i \in \mathcal{P}$ we generate 20 random instances of the MPIS problem with varying budgets and information set costs. We run Algorithm <ref> to generate the greedy information set and find the optimal set through brute-force search. We plot the distributions of the ratio of maximum penalty of information set generated by greedy to that of the optimal in Figure <ref>(b). We observe that as the submodularity ratio increases (i.e., the objective function is closer to being submodular) the performance of greedy improves, i.e., the utility achieved by greedy is closer to optimal.

Performance of greedy algorithm for information set selection for varying submodularity ratios (a) Algorithm <ref> (Problem <ref>), (b) Algorithm <ref> (Problem <ref>).

§.§ Modified Information Set Selection Problems

We evaluate the performance of the greedy algorithms over random instances of the M-MCIS and M-MPIS problems. For M-MCIS problem, we generate 50 random instances, where for each instance, we set the total number of data sources $\mathcal{D}$ to be 10 and for each source $i \in \mathcal{D}$, the selection cost $c_i$ is drawn uniformly from $\{1,2,\hdots,10\}$. We generate a random row-stochastic penalty matrix $\Xi \in \mathbb{R}^{|\Theta| \times |\Theta|}$ with $|\Theta| = 20$. We consider a uniform prior $\mu_0(\theta) = 1/|\Theta|$ and set a penalty threshold of $R'/|\Theta|$, where $R$ is drawn randomly from  $\{1, \hdots, |\Theta|-1\}$ for all $\theta_p \in \Theta$. We consider the scenario with infinite observation samples, where the constraints can be completely specified by $F_{\theta_p}(i)$ for all $\theta_p \in \Theta$ and for all $i \in \mathcal{D}$, which capture the underlying likelihood functions $\ell_i(\cdot|\theta_p)$. We randomly generate the set $F_{\theta_p}(i)$ for all $i \in \mathcal{D}$ and for all $\theta_p \in \Theta$. In Figure <ref>(a), we plot the ratio of cost of the greedy information set to that of the optimal information set. Similarly, we generate 50 random instances of the M-MPIS problem. Here, we set uniform costs for the data sources.  For each instance, we set $|\mathcal{D}|=10$ and the randomly sample the selection budget from $\{1,2, \hdots,10\}$. In Figure <ref>(b), we plot the ratio of total penalty of the greedy information set to that of the optimal information set. We observe from Figure <ref> that the greedy algorithms exhibit near-optimal performance, which aligns with the theoretical guarantees provided by Corollary <ref>.

Histogram of ratio of greedy to optimal (a) Algorithm <ref> (Problem <ref>), (b) Algorithm <ref> (Problem <ref>).


Holographic drag force in non-conformal plasma
Tolga<EMAIL_ADDRESS>and Razieh
<EMAIL_ADDRESS>
a Department of Physics, Boğaziçi University, Istanbul, Turkey
b School of Particles and Accelerators, Institute for Research in Fundamental
Sciences (IPM), Tehran, Iran

In this study, the gauge/string duality is used to investigate the dynamics of
a moving heavy quark in a strongly coupled, non-conformal plasma. The drag
force in this non-conformal model is smaller than that of $\mathcal{N}=4$
supersymmetric Yang-Mills (SYM) plasma and decreases as the level of non-
conformality is increased. At intermediate temperatures, the world-sheet
temperature, which is derived numerically by calculating the world-sheet
horizon, deviates from its conformal value, but at high temperatures, it tends
to its conformal value.

###### Contents

  1. 1 Introduction
  2. 2 Non-conformal holographic model
  3. 3 Classical trailing string
    1. 3.1 Drag force
    2. 3.2 World-sheet temperature
  4. 4 Summary

##  1 Introduction

Heavy-ion collisions at the Relativistic Heavy Ion Collider (RHIC) and the
Large Hadron Collider (LHC) have provided strong evidence indicating the
formation of the strongly coupled quark-gluon plasma (QGP), a deconfined state
of hadronic matter whose dynamics after the collision is dominated by non-
perturbative effects Adams:2005dq ; Adcox:2004mh ; Arsene:2004fa ; Back:2004je
; Policastro:2001yc ; Kovtun:2004de ; Baier:1996kr ; Eskola:2004cr . While the
perturbative QCD works only in the weak coupling regime, the string/gauge
duality can be used as the powerful tool fo study the strongly coupled plasma
Maldacena:1997re ; Witten:1998qj ; Gubser:1998bc ; Aharony:1999ti ;
CasalderreySolana:2011us  .

However, there is no known gravity dual to QCD, the duality between the
$\mathcal{N}=4\,SU(N_{c})$ super-Yang-Mills theory and type IIB string theory
on $AdS_{5}\times S^{5}$ is the most studied example in the context of AdS/CFT
correspondence Shuryak:2008eq ; Shuryak:2004cy ; Baier:1996kr  which provided
promising results. For example, the ratio of shear viscosity over entropy
density obtained from this duality, $\eta/s=1/4\pi$ Policastro:2001yc ;
Kovtun:2003wp ; Buchel:2003tz  is consistent with the experimental data
Teaney:2003kp .

Lattice data suggests that the QGP formed at high-energy heavy-ion collisions
is not a fully conformal fluid, and bulk viscosity, which is a purely non-
conformal effect, is needed for the precise extraction of the shear viscosity
of the QGP Ryu:2015vwa . Hydrodynamics including non-conformal effects
successfully describes the smaller system such as p-Pb Bozek:2011if  and p-p
Schenke:2014zha ; Habich:2015rtj  collisions Jeon:2015dfa . The original
duality can be extended to the theories more similar to QCD or QGP using the
well-known top-down Polchinski:2000uf ; Karch:2002sh ; Sakai:2004cn  or a
bottom-up Gursoy:2007cb ; Galow:2009kw  approaches.

One example of the latter approach is a five-dimensional gravity model coupled
to a scalar field with a non-trivial potential Attems:2016ugt . In this model,
the conformal invariance breaks even at zero temperature by coupling a scalar
field at pure gravity in AdS, which duals to a CFT deformed by a source
$\Lambda$ for a dimension-three operator. This source breaks the scale
invariance of the resulting four-dimensional strongly coupled gauge theory
explicitly and triggers a non-trivial renormalization Group (RG) flow from an
ultraviolet (UV) fixed point to an infrared (IR) fixed point. The UV fixed
point assured that we are in the regime where the holographic duality is best
understood and the bulk metric is asymptotically AdS. The IR fixed point is
needed to guarantees that the solutions are regular in the interior and the
zero-temperature solution is smooth in the deep IR. This simple model has been
used to study different properties such as thermodynamics and relaxation
channels Attems:2016ugt , jet energy lost Heshmatian:2018wlv , and
entanglement entropy Rahimi:2016bbv .

One of the most important quantities of QGP is the energy loss of a quark
moving through the plasma. An external quark was introduced in the context of
AdS/CFT correspondence by adding a fundamental string attached to a flavor
brane in the AdS space Herzog:2006gh ; Gubser:2006bz ;
CasalderreySolana:2006rq . The string endpoint specifies the heavy quark,
while the string itself can be considered as a gluonic cloud around the quark.
It is straightforward to show that the mass of quark is proportional to the
inverse distance of the string endpoint from the boundary Herzog:2006gh . The
light quark or massless quark is mapped into a string attached to a flavor
brane which is extended from the boundary to the horizon, and its dynamic in
different holographic backgrounds have been studied in Chesler:2008uy ;
Morad:2014xla ; BitaghsirFadafan:2017tci ; Heshmatian:2018wlv . On the other
hand, a string attached to the boundary of AdS space is dual to an infinite
mass quark. Since the first attempts to study the holographic heavy quark in
$\mathcal{N}=4$ super-Yang-Mills theory Herzog:2006gh ; Gubser:2006bz , the
heavy quark dynamics have been studied in various gauge theories with
gravitational duals Reiten:2019fta ; Gursoy:2009kk ; Horowitz:2007su ;
Horowitz:2015dta ; Chakraborty:2014kfa ; Lekaveckas:2013lha ; Talavera:2006tj
; Fadafan:2008uv ; Giecold:2009wi ; Panigrahi:2010cm ; Sadeghi:2009hh ;
Sadeghi:2009mp ; Sadeghi:2013zma ; Zhang:2019cxu ; Caceres:2006as ;
Bena:2019wcn ; Atashi:2019mlo ; Nakano:2006js ; Matsuo:2006ws ;
Rougemont:2015wca ; Zhang:2018rff ; Zhang:2018mqt ; Cheng:2014fza ;
NataAtmaja:2010hd .

This paper is organised as follows: In section 2 we briefly review the non-
conformal background introduced in Attems:2016ugt . In section 3 we discuss
the string solution dual to a heavy quark in this non-conformal background.
The numerical results of drag force and worldsheet temperature are presented
in 3.1 and 3.2. Section 4 is devoted to a summary.

##  2 Non-conformal holographic model

The action of 5-dimensional Einstein gravity coupled to a scalar field is
given by

$\displaystyle S=\frac{2}{\kappa_{5}^{2}}\int
d^{5}x\sqrt{-g}\left[\frac{1}{4}\mathcal{R}-\frac{1}{2}\left(\nabla\phi\right)^{2}-V(\phi)\right]\,,$
(1)

where $\kappa_{5}$ is the five-dimensional Newton constant and $V(\phi)$ is a
potential encoding the details of the dual gauge theory. In Attems:2016ugt ,
the following potential has been considered

$\displaystyle
L^{2}V=-3-\frac{3}{2}\phi^{2}-\frac{1}{3}\phi^{4}+\left(\frac{1}{3\phi_{M}^{2}}+\frac{1}{2\phi_{M}^{4}}\right)\phi^{6}-\frac{1}{12\phi_{M}^{4}}\phi^{8}\,.$
(2)

which is characterized by a single parameter, $\phi_{M}$. This non-trivial
relatively simple potential has a maximum at $\phi=0$ and a minimum at
$\phi=\phi_{M}$ corresponding to two AdS solutions at UV and IR fixed points.
The radii of these two solutions are related as

$L_{\rm IR}=\frac{1}{1+\frac{1}{6}\phi_{M}^{2}}L\,.$ (3)

Since $L_{\rm IR}<L$, the number of degrees of freedom is smaller at IR.

By parametrizing the vacuum metric as

$ds^{2}=e^{2A(r)}\left(-dt^{2}+d{\bf x}^{2}\right)+dr^{2}\,,$ (4)

the vacuum solution can be analytically obtained for arbitrary $\phi_{M}$

$\displaystyle e^{2A}$ $\displaystyle=$
$\displaystyle\frac{\Lambda^{2}L^{2}}{\phi^{2}}\,\left(1-\frac{\phi^{2}}{\phi_{M}^{2}}\right)^{\frac{\phi_{M}^{2}}{6}+1}\,e^{-\frac{\phi^{2}}{6}}\,,$
(5) $\displaystyle\phi(r)$ $\displaystyle=$ $\displaystyle\frac{\Lambda
L\,e^{-r/L}}{\sqrt{1+\frac{\Lambda^{2}L^{2}}{\phi_{M}^{2}}e^{-2r/L}}}\,.$ (6)

It is shown that the arbitrary parameter $\Lambda$ is responsible for breaking
the conformal invariance explicitly Attems:2016ugt .

The black brane solution of action 1 can be calculated numerically by the
following ansatz in the Eddington-Finkelstein coordinate

$ds^{2}=e^{2A}\left(-h(\phi)d\tilde{t}\,^{2}+d{\bf
x}^{2}\right)-2e^{A+B}L\,d\tilde{t}\,d\phi\,,$ (7)

where $\phi$ considered being the radial coordinate such that the boundary and
the horizon are located at $\phi=0$ and $\phi=\phi_{H}$, respectively. In
fact, the value of the scalar field at the horizon, $\phi_{H}$ characterizes
the black-brane solution and its thermodynamic properties explicitly. The dual
gauge theory is conformal both at the UV and at the IR. Therefore the high and
low temperature behavior of thermodynamical variables must match with the
relativistic conformal theory. The entropy ratio to its conformal value,
$s/s_{con}$, and the ratio of speed of sound for different values of
$\phi_{M}$ is plotted in Fig. 1(a) and Fig. 1(b), respectively. The entropy
ratio approaches one at high temperatures and $(L_{IR}/L)^{3}$ at low
temperatures. The speed of sound reaches its conformal value both at high and
low temperatures while deviating from its conformal value at intermediate
temperatures, which can be interpreted as a measure of the non-conformality of
the gauge theory. The detail of the numerical procedure is presented in
Attems:2016ugt .

(a)

(b)

Figure 1: (Color online) (1(a)) The ratio of non-conformal to the conformal
entropy,(1(b)) the ratio of speed of sound square to its conformal limit as a
function of temperature for different values of $\phi_{M}$.

##  3 Classical trailing string

This section studied a heavy quark moving through an infinite volume of quark-
gluon plasma with a fixed velocity $v$ at a finite temperature $T$. The heavy
quark feels a drag force and consequently losses energy. In the dual theory,
the dynamic of this quark can be described by an open string whose endpoint is
attached to the UV boundary of AdS space and moves at the constant speed of
$v$ with a string tail into the AdS bulk Herzog:2006gh ; Gubser:2006bz .

The dynamics of the string is described by the Nambu-Goto action

$S_{NG}=\,{1\over 2\pi\alpha^{\prime}}\int d\sigma
d\tau\,\sqrt{-\det\gamma_{\alpha\beta}},$ (8)

where $\alpha^{\prime}=l_{s}^{2}$ is the square of string’s fundamental length
and $\gamma_{\alpha\beta}$ is the induced metric of the world-sheet defined as

$\gamma_{\alpha\beta}=\,G_{MN}\,\partial_{\alpha}X^{M}\,\partial_{\beta}X^{M}\,,$
(9)

where $G_{MN}$ are the metric component of Eq. (7) in the Poincare coordinate

$G_{tt}(\phi)=-\,h(\phi)\,e^{2A(\phi)}\,\,\,,G_{xx}(\phi)=e^{2A(\phi)}\,\,\,,G_{\phi\phi}(\phi)=\frac{L^{2}}{h(\phi)}e^{2B(\phi)}\,.$
(10)

Henceforward we assume $L=1$ for simplicity. By considering the following
ansatz for the string embedding function in the static gauge
$(\tau=t\,,\sigma=\phi)$

$X^{M}(\tau,\sigma)=(t,x=vt+\xi(\phi),0,0,\phi)\,,$ (11)

the induced metric on the world-sheet becomes

$\gamma_{\alpha\beta}=e^{2A}\left(\begin{array}[]{cc}-(h-v^{2})&v\,\xi^{\prime}\\\
v\,\xi^{\prime}&\frac{e^{2(B-A)}}{h}+\xi^{\prime 2}\\\ \end{array}\right)\,,$
(12)

leads to the corresponding Lagrangian

$\mathcal{L}=-\frac{e^{A(\phi)}}{2\pi\alpha^{\prime}}\sqrt{e^{2A(\phi)}h(\phi)\xi^{\prime}(\phi)^{2}-\frac{v^{2}e^{2B(\phi)}}{h(\phi)}+e^{2B(\phi)}}\,.$
(13)

Since the Lagrangian does not depend on the $\xi$ explicitly, the string
equation of motion simplifies as

$\frac{1}{2\pi\alpha^{\prime}}\frac{e^{2A(\phi)}h(\phi)\xi^{\prime}(\phi)}{\sqrt{e^{2(B(\phi)-A(\phi))}-v^{2}\,\frac{e^{2(B(\phi)-A(\phi))}}{h(\phi)}+h(\phi)\xi^{\prime}(\phi)^{2}}}\,=\,const\equiv\pi_{\xi}\,,$
(14)

where $\pi_{\xi}$ is the constant of motion. From above, the equation for
$\xi^{\prime}$ can be obtained as

$\xi^{\prime}(\phi)=\pm\frac{2\pi\alpha^{\prime}\pi_{\xi}e^{B(\phi)-A(\phi)}}{h(\phi)}\,\sqrt{\frac{h(\phi)-v^{2}}{e^{4A(\phi)}h(\phi)-\left(2\pi\alpha^{\prime}\pi_{\xi}\right)^{2}}}\,.$
(15)

The numerator and denominator inside the square root are positive near the
boundary and negative around the horizon. Requiring the real values for the
string profile, $\xi^{\prime}$ means that the numerator and the denominator
have to change their sign at the same point denoted by $\phi_{s}$

$\displaystyle h(\phi_{s})-v^{2}=0\,,$ $\displaystyle
e^{4A(\phi_{s})}h(\phi_{s})-\left(2\pi\alpha^{\prime}\pi_{\xi}\right)^{2}=0\,.$
(16)

From the above equations, the constant of the equation of motion can be
determined as

$\displaystyle\pi_{\xi}=\frac{1}{2\pi\alpha^{\prime}}\,v\,e^{2A(\phi_{s})}\,.$
(17)

Substituting the $\pi_{\xi}$ into Eq. (15) yields to

$\xi^{\prime}(\phi)=\pm\frac{ve^{2A(\phi_{s})}e^{B(\phi)-A(\phi)}}{h(\phi)}\,\sqrt{\frac{h(\phi)-h(\phi_{s})}{e^{4A(\phi)}h(\phi)-e^{4A(\phi_{s})}h(\phi_{s})}}\,.$
(18)

The square root is now well-defined for the region outside the horizon
$(0<\phi<\phi_{H})$, and this equation can be solved numerically to obtain the
string profile.

###  3.1 Drag force

The drag force, which indicates the dissipation of quark momentum into the
plasma, is given by

$F_{drag}=-\pi^{1}_{x}\,,$ (19)

where $\pi^{1}_{x}$ is the momentum that is lost by flowing from the string to
the horizon. The canonical momentum densities associated with the string can
be obtained from varying the action with respect to the derivatives of the
embedding functions

$\displaystyle\left(\begin{array}[]{c}\pi^{0}_{t}\\\
\pi^{0}_{x}\end{array}\right)$ $\displaystyle=$
$\displaystyle\frac{1}{2\pi\alpha^{\prime}}\frac{e^{4A(\phi)}}{\sqrt{-\det\gamma_{\alpha\beta}}}\,\left(\begin{array}[]{c}-e^{2\left(B(\phi)-A(\phi)\right)}-h(\phi)\,\xi^{\prime}(\phi)^{2}\\\
e^{2\left(B(\phi)-A(\phi)\right)}\,v\,/\,h(\phi)\end{array}\right),$ (24)
$\displaystyle\left(\begin{array}[]{c}\pi^{1}_{t}\\\
\pi^{1}_{x}\end{array}\right)$ $\displaystyle=$
$\displaystyle\frac{1}{2\pi\alpha^{\prime}}\frac{e^{4A(\phi)}}{\sqrt{-\det\gamma_{\alpha\beta}}}\,\left(\begin{array}[]{c}v\,\xi^{\prime}(\phi)\,h(\phi)\\\
-\xi^{\prime}(\phi)\,h(\phi)\end{array}\right).$ (29)

Integrating the $\pi^{0}_{t}$ and $\pi^{0}_{x}$ along the string gives us the
total energy and the total momentum in the direction of motion of the string,
respectively. While, $\pi^{1}_{t}$ and $\pi^{1}_{x}$ are the energy and
momentum flow along the string and similar to the case of $\mathcal{N}=4$ SYM
plasma, $\pi^{1}_{t}=-v\,\pi^{1}_{x}$. By substituting the string solution,
Eq. (18) in the Eq. (29), it is evident that the $\pi^{1}_{x}$ equals the
constant of the equation of motion, $\pi_{\xi}$. This means that if we pull
the quark with a constant velocity, the fraction of energy flows at a given
point along the string, $\pi^{1}_{t}$ is constant. Using the Eq. (17), and Eq.
(19) the drag force is

$F_{drag}=-\frac{1}{2\pi\alpha^{\prime}}\,v\,e^{2A(\phi_{s})}\,,$ (30)

which is the momentum flow along the string at point $\phi_{s}$. If we use the
metric of AdS-Sch, the drag force for $\mathcal{N}=4$ SYM plasma can be
obtained as Herzog:2006gh ; Gubser:2006bz ; CasalderreySolana:2006rq

$F_{drag}^{SYM}=-\frac{\pi\,T^{2}\,\sqrt{\lambda}}{2}\frac{v}{\sqrt{1-v^{2}}}\,,$
(31)

where we have used the relation $L^{4}=\lambda\,\alpha^{\prime 2}$. In the
case of non-conformal background, the first equation of Eq. (3) should be
solved numerically to obtain the $\phi_{s}$ and then the drag force can be
calculated using Eq. (30).

Our numerical results for the drag force as a function of temperature for two
values of quark velocity are plotted in Fig. 2. The drag force in this non-
conformal plasma is smaller than the drag force in $\mathcal{N}=4$ SYM plasma
with the same temperature and decreases by increasing the degree of non-
conformality, $\phi_{M}$. Also, the drag force increases by increasing the
quark velocity. In Fig. 3(a), the drag force ratio to its conformal limit is
plotted for different values of $\phi_{M}$ as a function of temperature. The
solid and dashed lines represent the drag force for $v=0.9$, and $v=0.5$
respectively. As is evident from this figure, at high temperatures, where the
background reaches its conformal limit, the ratio of drag force tends to one.

In addition, the ratio of drag force to its conformal value vs velocity is
presented for different values of $\phi_{M}$ in Fig. 3(b) to explore the
velocity dependency. The temperature in both $\mathcal{N}=4$ SYM plasma and
non-conformal plasma was set to 350 MeV. We find that for all values of
$\phi_{M}$ the ratio is less than one at the fixed temperature but increases
slowly by increasing the velocity of quark.

(a)

(b)

Figure 2: (Color online) Drag force as a function of temperature for different
values of $\phi_{M}$ compared with the drag force in $\mathcal{N}=4$ SYM.

(a)

(b)

Figure 3: (Color Online) The ratio of drag force to its conformal value for
different values of $\phi_{M}$ as a function of (3(a)) temperature, (3(b))
velocity. The solid and dashed lines in (a) represent $v=0.9$ and $v=0.5$,
respectively. The temperature of both plasma in (b) sets to 350 MeV.

###  3.2 World-sheet temperature

One can reparametrize the world-sheet coordinate, Eq. (11) as follows

$\displaystyle\tau$ $\displaystyle=$ $\displaystyle t+K(\phi)\,,$
$\displaystyle x$ $\displaystyle=$ $\displaystyle vt+vK(\phi)+\xi(\phi)\,.$
(32)

Therefore, the background induced metric, Eq. (12) becomes

$\gamma_{\alpha\beta}=e^{2A}\left(\begin{array}[]{cc}-(h-v^{2})&v\,(\xi^{\prime}+v\,K^{\prime})-h\,K^{\prime}\\\
v\,(\xi^{\prime}+v\,K^{\prime})-h\,K^{\prime}&\,\,\,\frac{e^{2(B-A)}}{h}+(\xi^{\prime}+v\,K^{\prime})^{2}-h\,K^{\prime
2}\\\ \end{array}\right)\,.$ (33)

By choosing a particular ansatz of the form of

$\displaystyle K^{\prime}(\phi)=\frac{v\,\xi^{\prime}}{h-v^{2}}\,,$ (34)

and using Eq. (17), and Eq. (18), the induced metric diagonalizes as

$\gamma_{\alpha\beta}=e^{2A(\phi)}\left(\begin{array}[]{cc}-(h(\phi)-v^{2})&0\\\
0&\frac{e^{2(B(\phi)+A(\phi))}}{e^{4A(\phi)}\,h(\phi)-e^{4A(\phi_{s})}\,v^{2}}\\\
\end{array}\right)\,,$ (35)

which describe the metric of a two-dimensional world-sheet blackhole with a
horizon radius of $\phi_{s}$. The Hawking temperature of the world-sheet
blackhole indicated as $T_{wsh}$ is

$\displaystyle
T_{wsh}=\frac{1}{4\pi}\sqrt{e^{2A(\phi_{s})-2B(\phi_{s})}\,h^{\prime}(\phi_{s})(4\,v^{2}\,A^{\prime}(\phi_{s})+h^{\prime}(\phi_{s}))}\,.$
(36)

In the conformal limit, AdS-Schwarzschild metric, the world-sheet temperature
depends on the blackhole temperature and the velocity of quark as

$\displaystyle T_{wsh}^{conf}=\frac{T}{\sqrt{\gamma}}\,.$ (37)

In Fig. 4, the ratio of world-sheet temperature to its conformal value is
plotted in terms of the plasma temperature for different values of $\phi_{M}$.
The world-sheet temperature decreases by increasing the value of $\phi_{M}$.
The deviation from conformal behaviour is dominant at intermediate
temperature. At high temperatures, the ratio tends to one, as expected.

Figure 4: (Color Online) The ratio of world-sheet temperature to its conformal
value in terms of the plasma temperature for different values of $\phi_{M}$.

##  4 Summary

This paper studied the dynamics of a heavy quark moving through a strongly
coupled plasma with broken conformal symmetry using the gauge/gravity duality.
We considered a holographic five-dimensional model consisting of Einstein
gravity coupled to a scalar field with a non-trivial potential corresponding
to a dual four-dimensional non-conformal gauge theory that exhibits a
renormalization group flow between two different types of fixed points
(located at UV and IR) at zero temperature Attems:2016ugt . The parameter
$\phi_{M}$ indicates the deviation from conformality, as shown in Fig. 1.
According to the AdS/CFT dictionary, the heavy quark is associated with a
string attached to the boundary of the AdS space. The string equation of
motion was solved numerically for different values of parameter $\phi_{M}$,
and then the drag force was computed by obtaining the corresponding conjugate
momenta. Our results indicate that the drag force in this non-conformal plasma
is smaller than $\mathcal{N}=4$ super-Yang-Mills plasma. By increasing the
level of non-conformality (the value of parameter $\phi_{M}$), the drag force
decreases, see Fig. 2. The ratio of drag force to its conformal limit reaches
one at high temperatures. At finite temperature, this ratio is smaller than
one for different values of $\phi_{M}$ but increases slowly by increasing the
velocity of quark, see Fig. 3.

The world-sheet horizon was also calculated, and it was shown that the drag
force is equivalent to the energy flow at the world-sheet horizon. The
corresponding world-sheet temperature has been calculated and compared with
its conformal limit. Results confirm that the deviation from the conformal
limit is dominated at the intermediate plasma temperature.

###### Acknowledgements.

R. Morad would like to thank the Scientific and Technological Research Council
of Turkey (Tübitak), the Department of Science Fellowships and Grant Programs
(BIDEB) for the fellowship program for visiting scientists (2221).

## References

  * (1) J. Adams et al. [STAR], Nucl. Phys. A 757 (2005), 102-183 doi:10.1016/j.nuclphysa.2005.03.085 [arXiv:nucl-ex/0501009 [nucl-ex]].
  * (2) K. Adcox et al. [PHENIX], Nucl. Phys. A 757 (2005), 184-283 doi:10.1016/j.nuclphysa.2005.03.086 [arXiv:nucl-ex/0410003 [nucl-ex]].
  * (3) I. Arsene et al. [BRAHMS], Nucl. Phys. A 757 (2005), 1-27 doi:10.1016/j.nuclphysa.2005.02.130 [arXiv:nucl-ex/0410020 [nucl-ex]].
  * (4) B. B. Back et al. [PHOBOS], Nucl. Phys. A 757 (2005), 28-101 doi:10.1016/j.nuclphysa.2005.03.084 [arXiv:nucl-ex/0410022 [nucl-ex]].
  * (5) G. Policastro, D. T. Son and A. O. Starinets, Phys. Rev. Lett. 87 (2001), 081601 doi:10.1103/PhysRevLett.87.081601 [arXiv:hep-th/0104066 [hep-th]].
  * (6) P. Kovtun, D. T. Son and A. O. Starinets, Phys. Rev. Lett. 94 (2005), 111601 doi:10.1103/PhysRevLett.94.111601 [arXiv:hep-th/0405231 [hep-th]].
  * (7) R. Baier, Y. L. Dokshitzer, A. H. Mueller, S. Peigne and D. Schiff, Nucl. Phys. B 483 (1997), 291-320 doi:10.1016/S0550-3213(96)00553-6 [arXiv:hep-ph/9607355 [hep-ph]].
  * (8) K. J. Eskola, H. Honkanen, C. A. Salgado and U. A. Wiedemann, Nucl. Phys. A 747 (2005), 511-529 doi:10.1016/j.nuclphysa.2004.09.070 [arXiv:hep-ph/0406319 [hep-ph]].
  * (9) J. M. Maldacena, Adv. Theor. Math. Phys. 2 (1998), 231-252 doi:10.1023/A:1026654312961 [arXiv:hep-th/9711200 [hep-th]].
  * (10) E. Witten, Adv. Theor. Math. Phys. 2 (1998), 253-291 doi:10.4310/ATMP.1998.v2.n2.a2 [arXiv:hep-th/9802150 [hep-th]].
  * (11) S. S. Gubser, I. R. Klebanov and A. M. Polyakov, Phys. Lett. B 428 (1998), 105-114 doi:10.1016/S0370-2693(98)00377-3 [arXiv:hep-th/9802109 [hep-th]].
  * (12) O. Aharony, S. S. Gubser, J. M. Maldacena, H. Ooguri and Y. Oz, Phys. Rept. 323 (2000), 183-386 doi:10.1016/S0370-1573(99)00083-6 [arXiv:hep-th/9905111 [hep-th]].
  * (13) J. Casalderrey-Solana, H. Liu, D. Mateos, K. Rajagopal and U. A. Wiedemann, doi:10.1017/CBO9781139136747 [arXiv:1101.0618 [hep-th]].
  * (14) E. Shuryak, Prog. Part. Nucl. Phys. 62 (2009), 48-101 doi:10.1016/j.ppnp.2008.09.001 [arXiv:0807.3033 [hep-ph]].
  * (15) E. V. Shuryak, Nucl. Phys. A 750 (2005), 64-83 doi:10.1016/j.nuclphysa.2004.10.022 [arXiv:hep-ph/0405066 [hep-ph]].
  * (16) P. Kovtun, D. T. Son and A. O. Starinets, JHEP 10 (2003), 064 doi:10.1088/1126-6708/2003/10/064 [arXiv:hep-th/0309213 [hep-th]].
  * (17) A. Buchel and J. T. Liu, Phys. Rev. Lett. 93 (2004), 090602 doi:10.1103/PhysRevLett.93.090602 [arXiv:hep-th/0311175 [hep-th]].
  * (18) D. Teaney, Phys. Rev. C 68 (2003), 034913 doi:10.1103/PhysRevC.68.034913 [arXiv:nucl-th/0301099 [nucl-th]].
  * (19) S. Ryu, J. F. Paquet, C. Shen, G. S. Denicol, B. Schenke, S. Jeon and C. Gale, Phys. Rev. Lett. 115 (2015) no.13, 132301 doi:10.1103/PhysRevLett.115.132301 [arXiv:1502.01675 [nucl-th]].
  * (20) P. Bozek, Phys. Rev. C 85 (2012), 014911 doi:10.1103/PhysRevC.85.014911 [arXiv:1112.0915 [hep-ph]].
  * (21) B. Schenke and R. Venugopalan, Phys. Rev. Lett. 113 (2014), 102301 doi:10.1103/PhysRevLett.113.102301 [arXiv:1405.3605 [nucl-th]].
  * (22) M. Habich, G. A. Miller, P. Romatschke and W. Xiang, Eur. Phys. J. C 76 (2016) no.7, 408 doi:10.1140/epjc/s10052-016-4237-z [arXiv:1512.05354 [nucl-th]].
  * (23) S. Jeon and U. Heinz, Int. J. Mod. Phys. E 24 (2015) no.10, 1530010 doi:10.1142/S0218301315300106 [arXiv:1503.03931 [hep-ph]].
  * (24) J. Polchinski and M. J. Strassler, [arXiv:hep-th/0003136 [hep-th]].
  * (25) A. Karch and E. Katz, JHEP 06 (2002), 043 doi:10.1088/1126-6708/2002/06/043 [arXiv:hep-th/0205236 [hep-th]].
  * (26) T. Sakai and S. Sugimoto, Prog. Theor. Phys. 113 (2005), 843-882 doi:10.1143/PTP.113.843 [arXiv:hep-th/0412141 [hep-th]].
  * (27) U. Gursoy and E. Kiritsis, JHEP 02 (2008), 032 doi:10.1088/1126-6708/2008/02/032 [arXiv:0707.1324 [hep-th]].
  * (28) B. Galow, E. Megias, J. Nian and H. J. Pirner, Nucl. Phys. B 834 (2010), 330-362 doi:10.1016/j.nuclphysb.2010.03.022 [arXiv:0911.0627 [hep-ph]].
  * (29) M. Attems, J. Casalderrey-Solana, D. Mateos, I. Papadimitriou, D. Santos-Oliván, C. F. Sopuerta, M. Triana and M. Zilhão, JHEP 10 (2016), 155 doi:10.1007/JHEP10(2016)155 [arXiv:1603.01254 [hep-th]].
  * (30) S. Heshmatian, and R. Morad, JHEP 03 (2019), 045 doi:10.1007/JHEP03(2019)045 [arXiv:1812.09374 [hep-th]].
  * (31) M. Rahimi, M. Ali-Akbari and M. Lezgi, Phys. Lett. B 771 (2017), 583-587 doi:10.1016/j.physletb.2017.05.055 [arXiv:1610.01835 [hep-th]].
  * (32) C. P. Herzog, A. Karch, P. Kovtun, C. Kozcaz and L. G. Yaffe, JHEP 07 (2006), 013 doi:10.1088/1126-6708/2006/07/013 [arXiv:hep-th/0605158 [hep-th]].
  * (33) S. S. Gubser, Phys. Rev. D 74 (2006), 126005 doi:10.1103/PhysRevD.74.126005 [arXiv:hep-th/0605182 [hep-th]].
  * (34) J. Casalderrey-Solana and D. Teaney, Phys. Rev. D 74 (2006), 085012 doi:10.1103/PhysRevD.74.085012 [arXiv:hep-ph/0605199 [hep-ph]].
  * (35) P. M. Chesler, K. Jensen, A. Karch and L. G. Yaffe, Phys. Rev. D 79 (2009), 125015 doi:10.1103/PhysRevD.79.125015 [arXiv:0810.1985 [hep-th]].
  * (36) R. Morad and W. A. Horowitz, JHEP 11 (2014), 017 doi:10.1007/JHEP11(2014)017 [arXiv:1409.7545 [hep-th]].
  * (37) K. Bitaghsir Fadafan and R. Morad, Eur. Phys. J. C 78 (2018) no.1, 16 doi:10.1140/epjc/s10052-018-5520-y [arXiv:1710.06417 [hep-th]].
  * (38) J. Reiten and A. V. Sadofyev, JHEP 07 (2020), 146 doi:10.1007/JHEP07(2020)146 [arXiv:1912.08816 [hep-th]].
  * (39) U. Gursoy, E. Kiritsis, G. Michalogiorgakis and F. Nitti, JHEP 12 (2009), 056 doi:10.1088/1126-6708/2009/12/056 [arXiv:0906.1890 [hep-ph]].
  * (40) W. A. Horowitz and M. Gyulassy, Phys. Lett. B 666 (2008), 320-323 doi:10.1016/j.physletb.2008.04.065 [arXiv:0706.2336 [nucl-th]].
  * (41) W. A. Horowitz, Phys. Rev. D 91 (2015) no.8, 085019 doi:10.1103/PhysRevD.91.085019 [arXiv:1501.04693 [hep-ph]].
  * (42) S. Chakraborty and N. Haque, JHEP 12 (2014), 175 doi:10.1007/JHEP12(2014)175 [arXiv:1410.7040 [hep-th]].
  * (43) M. Lekaveckas and K. Rajagopal, JHEP 02 (2014), 068 doi:10.1007/JHEP02(2014)068 [arXiv:1311.5577 [hep-th]].
  * (44) P. Talavera, JHEP 01 (2007), 086 doi:10.1088/1126-6708/2007/01/086 [arXiv:hep-th/0610179 [hep-th]].
  * (45) K. Bitaghsir Fadafan, Eur. Phys. J. C 68 (2010), 505-511 doi:10.1140/epjc/s10052-010-1375-6 [arXiv:0809.1336 [hep-th]].
  * (46) G. C. Giecold, JHEP 06 (2009), 002 doi:10.1088/1126-6708/2009/06/002 [arXiv:0904.1874 [hep-th]].
  * (47) K. L. Panigrahi and S. Roy, JHEP 04 (2010), 003 doi:10.1007/JHEP04(2010)003 [arXiv:1001.2904 [hep-th]].
  * (48) J. Sadeghi, M. R. Setare and B. Pourhassan, J. Phys. G 36 (2009), 115005 doi:10.1088/0954-3899/36/11/115005 [arXiv:0905.1466 [hep-th]].
  * (49) J. Sadeghi, M. R. Setare, B. Pourhassan and S. Hashmatian, Eur. Phys. J. C 61 (2009), 527-533 doi:10.1140/epjc/s10052-009-1011-5 [arXiv:0901.0217 [hep-th]].
  * (50) J. Sadeghi, B. Pourhassan and S. Heshmatian, Adv. High Energy Phys. 2013 (2013), 759804 doi:10.1155/2013/759804
  * (51) Z. q. Zhang and X. Zhu, Eur. Phys. J. C 79 (2019) no.2, 107 doi:10.1140/epjc/s10052-019-6579-9
  * (52) E. Caceres and A. Guijosa, JHEP 12 (2006), 068 doi:10.1088/1126-6708/2006/12/068 [arXiv:hep-th/0606134 [hep-th]].
  * (53) I. Bena and A. Tyukov, JHEP 04 (2020), 046 doi:10.1007/JHEP04(2020)046 [arXiv:1911.12821 [hep-th]].
  * (54) M. Atashi and K. Bitaghsir Fadafan, Phys. Lett. B 800 (2020), 135090 doi:10.1016/j.physletb.2019.135090 [arXiv:1906.11621 [hep-th]].
  * (55) E. Nakano, S. Teraguchi and W. Y. Wen, Phys. Rev. D 75 (2007), 085016 doi:10.1103/PhysRevD.75.085016 [arXiv:hep-ph/0608274 [hep-ph]].
  * (56) T. Matsuo, D. Tomino and W. Y. Wen, JHEP 10 (2006), 055 doi:10.1088/1126-6708/2006/10/055 [arXiv:hep-th/0607178 [hep-th]].
  * (57) R. Rougemont, A. Ficnar, S. Finazzo and J. Noronha, JHEP 04 (2016), 102 doi:10.1007/JHEP04(2016)102 [arXiv:1507.06556 [hep-th]].
  * (58) Z. q. Zhang, Z. j. Luo and D. f. Hou, Nucl. Phys. A 974 (2018), 1-8 doi:10.1016/j.nuclphysa.2018.03.004 [arXiv:1804.05517 [hep-th]].
  * (59) Z. q. Zhang, K. Ma and D. f. Hou, J. Phys. G 45 (2018) no.2, 025003 doi:10.1088/1361-6471/aaa097 [arXiv:1802.01912 [hep-th]].
  * (60) L. Cheng, X. H. Ge and S. Y. Wu, Eur. Phys. J. C 76 (2016) no.5, 256 doi:10.1140/epjc/s10052-016-4096-7 [arXiv:1412.8433 [hep-th]].
  * (61) A. Nata Atmaja and K. Schalm, JHEP 04 (2011), 070 doi:10.1007/JHEP04(2011)070 [arXiv:1012.3800 [hep-th]].