Submodular Learning and Covering\\ with Response-Dependent Costs
Sivan Sabato
We consider interactive learning and covering problems, in a setting where actions may incur different costs, depending on the response to the action. We propose a natural greedy algorithm for response-dependent costs. We bound the approximation factor of this greedy algorithm in active learning settings as well as in the general setting. We show that a different property of the cost function controls the approximation factor in each of these scenarios. We further show that in both settings, the approximation factor of this greedy algorithm is near-optimal among all greedy algorithms. Experiments demonstrate the advantages of the proposed algorithm in the response-dependent cost setting. \keywords{Interactive learning, submodular functions, outcome costs
arxiv.tex

















\documentclass{llncs}

\usepackage{amssymb}
\setcounter{tocdepth}{3}


\usepackage{url}



\newcommand{\keywords}[1]{\par\addvspace\baselineskip
\noindent\keywordname\enspace\ignorespaces#1}


\usepackage{amsmath,amsfonts,stmaryrd,amssymb}
\usepackage{algorithm,enumitem}

\usepackage{algorithmic}
\renewcommand{\algorithmicrequire}{\textbf{input}}
\renewcommand{\algorithmicensure}{\textbf{output}}

\usepackage{booktabs}
\usepackage{pifont}


\usepackage{tikz}
\usetikzlibrary{arrows}
\usetikzlibrary{calc}












\spnewtheorem{assumption}{Assumption}{\bfseries}{\itshape} 


\renewcommand{\eqref}[1]{Eq.~(\ref{eq:#1})}
\newcommand{\figref}[1]{Figure \ref{fig:#1}}
\newcommand{\tabref}[1]{Table \ref{tab:#1}}        
\newcommand{\secref}[1]{Section \ref{sec:#1}}
\newcommand{\thmref}[1]{Theorem \ref{thm:#1}}
\newcommand{\lemref}[1]{Lemma \ref{lem:#1}}
\newcommand{\conref}[1]{Conjecture \ref{con:#1}}
\newcommand{\corref}[1]{Cor.~\ref{cor:#1}}
\newcommand{\appref}[1]{Appendix \ref{ap:#1}}
\newcommand{\propref}[1]{Proposition \ref{prop:#1}}
\newcommand{\algref}[1]{Alg.~\ref{alg:#1}}
\newcommand{\factref}[1]{Fact \ref{fact:#1}}
\newcommand{\asref}[1]{Assumption \ref{as:#1}}

\newenvironment{myproof}{\begin{proof}}{\hfill$\square$\end{proof}}


\renewcommand{\P}{\mathbb{P}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\Var}{\mathrm{Var}}
\newcommand{\loss}{\ell}
\newcommand{\binlab}{\{\pm 1\}}

\newcommand{\reals}{\mathbb{R}}
\newcommand{\nats}{\mathbb{N}}
\newcommand{\half}{{\frac12}}
\newcommand{\ceil}[1]{{\lceil #1\rceil}}
\newcommand{\floor}[1]{\lfloor #1\rfloor}

\newcommand{\sign}{\textrm{sign}}
\newcommand{\one}{\mathbb{I}}
\newcommand{\norm}[1]{\|#1\|}
\newcommand{\dotprod}[1]{\langle #1 \rangle}
\newcommand{\diag}{\mathrm{diag}}
\newcommand{\grad}{\triangledown}


\DeclareMathOperator*{\argmin}{argmin}
\DeclareMathOperator*{\argmax}{argmax}

\newcommand{\err}{\mathrm{err}}
\newcommand{\cmark}{\ding{51}}
\newcommand{\xmark}{\ding{55}}
\newcommand{\st}{\text{ s.t. }}




\renewcommand{\vec}[1]{\mathbf{#1}}
\newcommand{\vw}{\vec{w}}
\newcommand{\vb}{\vec{b}}
\newcommand{\vx}{\vec{x}}
\newcommand{\vp}{\vec{p}}
\newcommand{\vy}{\vec{y}}
\newcommand{\vv}{\vec{v}}
\newcommand{\va}{\vec{a}}
\newcommand{\vu}{\vec{u}}
\newcommand{\vz}{\vec{z}}
\newcommand{\vX}{\vec{X}}
\newcommand{\mt}[1]{\mathbb{#1}}

\renewcommand\t{\ensuremath{{\scriptscriptstyle{\top}}}}




\newcommand{\todo}[1]{{\textcolor{red}{\textbf{todo: #1}}}}



\newcommand{\cA}{\mathcal{A}}
\newcommand{\cB}{\mathcal{B}}
\newcommand{\cC}{\mathcal{C}}
\newcommand{\cD}{\mathcal{D}}
\newcommand{\cE}{\mathcal{E}}
\newcommand{\cF}{\mathcal{F}}
\newcommand{\cG}{\mathcal{G}}
\newcommand{\cH}{\mathcal{H}}
\newcommand{\cI}{\mathcal{I}}
\newcommand{\cJ}{\mathcal{J}}
\newcommand{\cK}{\mathcal{K}}
\newcommand{\cL}{\mathcal{L}}
\newcommand{\cM}{\mathcal{M}}
\newcommand{\cN}{\mathcal{N}}
\newcommand{\cO}{\mathcal{O}}
\newcommand{\cP}{\mathcal{P}}
\newcommand{\cQ}{\mathcal{Q}}
\newcommand{\cR}{\mathcal{R}}
\newcommand{\cS}{\mathcal{S}}
\newcommand{\cT}{\mathcal{T}}
\newcommand{\cU}{\mathcal{U}}
\newcommand{\cV}{\mathcal{V}}
\newcommand{\cW}{\mathcal{W}}
\newcommand{\cX}{\mathcal{X}}
\newcommand{\cY}{\mathcal{Y}}
\newcommand{\cZ}{\mathcal{Z}}







\usepackage{multirow}



\newcommand{\citet}{\cite}
\newcommand{\citep}{\cite}


\newcommand{\OPT}{\mathrm{OPT}}
\DeclareMathOperator{\minsec}{\phi}
\newcommand{\cost}{\mathfrak{cost}}
\newcommand{\vs}{\mathrm{VS}}
\newcommand{\wc}{\mathrm{wc}}
\newcommand{\ac}{\mathrm{avg}}
\newcommand{\pairs}{{\cX \times \cY}}
\newcommand{\nil}{\bot}
\newcommand{\val}{\mathrm{val}}
\newcommand{\cmax}{\cost_{\max}}
\newcommand{\cmin}{\cost_{\min}}

\newcommand{\bcost}{{\cost'}}
\newcommand{\crr}{r} 
\newcommand{\sscr}{r^{[2]}} 
\newcommand{\gsscr}{gr^{[2]}} 



\newcommand{\tableresults}
{

\begin{tabular}{|l|l|l||l|l|l|}
\hline
\multicolumn{3}{|c|}{Test parameters} & \multicolumn{3}{|c|}{Results: $\cost(\cA)$}\\
\hline
Test & $\sscr_\cost$ & $\gsscr_\cost$ & $u^f$ & $u_2^f$ & $u_3^f$ \\
\hline
\hline
\multirow{3}{*}{\parbox{2cm}{\scriptsize $f$=edge users,\\3 communities}} & 5 & 5 & \textbf{52} & 255 & 157 \\\cline{2-6}
 & 100 & 100 & \textbf{148} & 5100 & 2722 \\\cline{2-6}
  &  1 & 100 & \textbf{49} & 52 & 2821 \\\hline

\multirow{3}{*}{\parbox{2cm}{\scriptsize$f$=edge users,\\10 communities}}& 5 & 5 & \textbf{231} & 256 & 242  \\\cline{2-6}
 & 100 & 100  & \textbf{4601} & 5101 & 4802  \\\cline{2-6}
 & 1 & 100 & \textbf{50} & 52 & 2915\\\hline


\multirow{3}{*}{\parbox{2cm}{\scriptsize$f$=v.~reduction,\\3 communities}}& 5 & 5 & \textbf{13} & 20 & 15 \\\cline{2-6}
 & 100 & 100 & \textbf{203} & 400 & 300 \\\cline{2-6}
& 1 & 100 & \textbf{3} & 4 & 201 \\
\hline
\multirow{3}{*}{\parbox{2cm}{\scriptsize$f$=v.~reduction,\\10 communities}} & 5 & 5 & \textbf{8} & 20 & 15   \\\cline{2-6}
 & 100 & 100  & \textbf{105} & 400 & 300  \\\cline{2-6}
 & 1 & 100 & \textbf{101} & 103 & 201\\
\hline
\end{tabular}
\quad
\begin{tabular}{|l|l|l||l|l|l|}
\hline
\multicolumn{3}{|c|}{Test parameters} & \multicolumn{3}{|c|}{Results: $\cost(\cA)$}\\
\hline
Test & $\sscr_\cost$ & $\gsscr_\cost$ & $u^f$ & $u_2^f$ & $u_3^f$ \\
\hline
\hline
\multirow{3}{*}{\parbox{2cm}{\scriptsize$f$=edge users,\\3 communities}}  & 5 & 5 & \textbf{51} &181 & 123\\\cline{2-6}
  & 100 & 100 & \textbf{147} &3503 & 1833\\\cline{2-6}
 & 1 & 100 & \textbf{51} & 53 & 2526\\
\hline
\multirow{3}{*}{\parbox{2cm}{\scriptsize$f$=edge users,\\10 communities}}& 5 & 5 & 246 & 260 & \textbf{245}\\\cline{2-6}
&  100 & 100  & 4901 & 5200& \textbf{4900} \\\cline{2-6}
& 1 & 100 & \textbf{49} & 52 & 3217 \\
\hline
\multirow{3}{*}{\parbox{2cm}{\scriptsize$f$=v.~reduction,\\3 communities}}& 5 & 5 & \textbf{10}& 20 & 15 \\\cline{2-6}
 & 100 & 100 & \textbf{106} & 400 & 300  \\\cline{2-6}
 & 1 & 100 & \textbf{3} & 400 & 300  \\
\hline

\multirow{3}{*}{\parbox{2cm}{\scriptsize$f$=v.~reduction,\\10 communities}} & 5 & 5 & \textbf{15}& 16& \textbf{15} \\\cline{2-6}
 & 100 & 100 & \textbf{300} & 301 & \textbf{300}  \\\cline{2-6}
 & 1 & 100 & \textbf{3} &201 & 300 \\
\hline
\end{tabular}



}


\sloppy
\begin{document}

\mainmatter  


\title{Submodular Learning and Covering\\ with Response-Dependent Costs}










\author{Sivan Sabato}






\institute{Ben-Gurion University of the Negev}















\maketitle


\begin{abstract}
We consider interactive learning and covering problems, in a setting where actions may incur different costs, depending on the response to the action. 
We propose a natural greedy algorithm for response-dependent costs. We bound the approximation factor of this greedy algorithm in active learning settings as well as in the general setting. We show that a different property of the cost function controls the approximation factor in each of these scenarios.
We further show that in both settings, the approximation factor of this greedy algorithm is near-optimal among all greedy algorithms. Experiments demonstrate the advantages of the proposed algorithm in the response-dependent cost setting.
\keywords{Interactive learning, submodular functions, outcome costs}
\end{abstract}


\section{Introduction}


We consider interactive learning and covering problems, a term introduced in \citet{GuilloryBi10}. In these problems, there is an algorithm that interactively selects actions and receives a response for each action. Its goal is to achieve an objective, whose value depends on the actions it selected, their responses, and the state of the world. The state of the world, which is unknown to the algorithm, also determines the response to each action. The algorithm incurs a cost for every action it performs. The goal is to have the total cost incurred by the algorithm as low as possible.

Many real-world problems can be formulated as interactive learning and covering problems. These include pool-based active learning problems \citep{MccallumNi98short,Dasgupta04short}, maximizing the influence of marketing in a social network \citep{GuilloryBi10}, interactive sensor placement \cite{GolovinKr11} and document summarization \cite{LinBi11} with interactive user feedback.

Interactive learning and covering problems cannot be solved efficiently in general \citep{NemhauserWoFi78,Wolsey82}. Nevertheless, many such problems can be solved near-optimally by efficient algorithms, when the functions that map the sets of actions to the total reward are \emph{submodular}.

It has been shown in several settings, that a simple greedy algorithm pays a near-optimal cost when the objective function is submodular (e.g.,~\cite{GuilloryBi10,GolovinKr11,CuongLeYe14}). Many problems naturally lend themselves to a submodular formulation. These include covering objectives, objectives promoting diversity \cite{MirzasoleimanKaSaKr13short} and active learning \cite{Dasgupta04short,GolovinKr11,GuilloryBi10,GonenSaSh13b}.

Interactive learning and covering problems have so far been studied mainly under the assumption that the cost of the action is known to the algorithm before the action is taken. In this work we study the setting in which the costs of actions depend on the outcome of the action, which is only revealed by the observed response. This is the case in many real-world scenarios. For instance, consider an active learning problem, where the goal is to learn a classifier that predicts which patients should be administered a specific drug. Each action in the process of learning involves administering the drug to a patient and observing the effect. In this case, the cost (poorer patient health) is higher if the patient suffers adverse effects. Similarly, when marketing in a social network, an action involves sending an ad to a user. If the user does not like the ad, this incurs a higher cost (user dissatisfaction) than if they like the ad. 

We study the achievable approximation guarantees in the setting of
response-dependence costs, and characterize the dependence of this
approximation factor on the properties of the cost function.  We propose a
natural generalization of the greedy algorithm of \citet{GuilloryBi10} to the
response-dependent setting, and provide two approximation guarantees. The
first guarantee holds whenever the algorithm's objective describes an active
learning problem. We term such objectives \emph{learning objectives}. The
second guarantee holds for general objectives, under a mild condition. In each
case, the approximation guarantees depend on a property of the cost function,
and we show that this dependence is necessary for any greedy algorithm. Thus,
this fully characterizes the relationship between the cost function
and the approximation guarantee achievable by a greedy algorithm.
We further report experiments that demonstrate the achieved cost improvement.

Response-dependent costs has been previously studied in specific cases of
active learning, assuming there are only two possible labels
\citep{SabatoSaSr13,SabatoSaSr15,SaettlerLaCi14,SaettlerLaCi15}.  In
\citet{KapoorHoBa07} this setting is also mentioned in the context of active
learning. Our work is more general: First, it addresses general objective
functions and not only specific active learning settings. Our results indicate that the active learning setting and the general setting are inherently different. Second, it is not limited to
settings with two possible responses. 
As we show below, previous guarantees for two responses do not generalize to tight guarantees for cases with more than two responses. 
 We thus develop new proof techniques that allow deriving these tighter bounds.




\section{Definitions and Preliminaries}\label{sec:setting}
For an integer $n$, denote $[n] := \{1,\ldots,n\}$. A set function $f:2^\cZ \rightarrow \reals$ is \emph{monotone} (non-decreasing) if $\forall A\subseteq B \subseteq \cZ$, $f(A) \leq f(B)$. 
Let $\cZ$ be a domain, and let $f:2^\cZ \rightarrow \reals_+$ be a set function. Define, for any $z\in\cZ,A\subseteq \cZ$, $\delta_f(z\mid A) := f(A\cup \{z\}) - f(A)$. $f$ is \emph{submodular} if $\forall z \in \cZ, A\subseteq B \subseteq \cZ,\, \delta_f(z \mid A) \geq \delta_f(z \mid B).$

Assume a finite domain of actions $\cX$ and a finite domain of responses $\cY$.
For simplicity of presentation, we assume that there is a one-to-one mapping between world states and mappings from actions to their responses. Thus the states of the world are represented by the class of possible mappings $\cH \subseteq \cY^\cX$.
Let $h^* \in \cH$ be the true, unknown, mapping from actions to responses.
Let $S \subseteq \pairs$ be a set of action-response pairs. 


We consider algorithms that iteratively select a action $x \in \cX$ and get the response $h^*(x)$, where $h^* \in \cH$ is the true state of the world, which is unknown to the algorithm. For an algorithm $\cA$, let $S^h[\cA]$ be the set of pairs collected by $\cA$ until termination if $h^* = h$. Let $S^h_t[\cA]$ be the set of pairs collected by $\cA$ in the first $t$ iterations if $h^* = h$. In each iteration, $\cA$ decides on the next action to select based on responses to previous actions, or it decides to terminate. $\cA(S) \in \cX \cup \{\nil\}$ denotes the action that $\cA$ selects after observing the set of pairs $S$, where $\cA(S) = \nil$ if $\cA$ terminates after observing $S$. 

Each time the algorithm selects an action and receives a response, it incurs a cost, captured by a cost function 
$\cost:\cX \times \cY \rightarrow \reals_+$. If $x \in \cX$ is selected and the response $y \in \cY$ is received, the algorithm pays $\cost(x,y)$. Denote $\cost(S) = \sum_{(x,y) \in S} \cost(x,y)$. The total cost of a run of the algorithm when the state of the world is $h^*$, is thus $\cost(S^{h^*}[\cA])$. For a given $\cH$, define the \emph{worst-case cost} of $\cA$ by $\cost(\cA) := \max_{h \in \cH} \cost(S^h[\cA])$. Let $Q > 0$ be a threshold, and let $f:2^\pairs \rightarrow \reals_+$ be a monotone non-decreasing submodular objective function. We assume that the goal of the interactive algorithm is to collect pairs $S$ such that $f(S) \geq Q$, while minimizing $\cost(\cA)$. 



Guillory and Bilmes \cite{GuilloryBi10} consider a setting 
 in which instead of a single global $f$, there is a set of monotone non-decreasing objective functions
$\cF_{\cH} = \{f_h:2^\pairs \rightarrow \reals_+ \mid h \in \cH\}$, and the value $f_h(S)$, for $S \subseteq \pairs$, represents the reward obtained by the algorithm if $h^* = h$. They show that obtaining $f_{h^*}(S) \geq Q$ is equivalent to obtaining $\bar{F}(S) \geq Q$, where 
$\bar{F}:2^\pairs \rightarrow \reals_+$ is defined by
\begin{equation}\label{eq:fbar}
\bar{F}(S) := \frac{1}{|\cH|}\Big(Q|\cH \setminus \vs(S)| + \sum_{h \in \vs(S)}\min(Q,f_h(S))\Big).
\end{equation}
Here $\vs(S)$ is the \emph{version space} induced by $S$ on $\cH$, defined by \mbox{$\vs_\cH(S) = \{ h \in \cH \mid \forall (x,y) \in S, y = h(x)\}$}. 
It is shown in \cite{GuilloryBi10} that if all the functions in $\cF_\cH$ are monotone and submodular then so is $\bar{F}$. Thus our setting of a single objective function can be applied to the setting of \cite{GuilloryBi10} as well.

Let $\alpha \geq 1$. An interactive algorithm $\cA$ is an \emph{$\alpha$-approximate} \emph{greedy algorithm} for \emph{utility function} \mbox{$u:\cX \times 2^\pairs \rightarrow \reals_+$}, if the following holds: For all $S \subseteq \pairs$, if $f(S) \geq Q$ then $\cA(S) = \nil$, and otherwise, $\cA(S) \in \cX$ and $u(\cA(S),S) \geq \frac{1}{\alpha}\max_{x \in \cX} u(x,S)$. As shown below, consistently with previous works, (e.g. \cite{GolovinKr11}), competitive guarantees are better for $\alpha$-approximate-greedy algorithms with $\alpha=1$ or $\alpha$ close to $1$. However, due to efficiency of computation or other practical considerations, it is not always feasible to implement a $1$-greedy algorithm. Thus, for full generality, we analyze  also $\alpha$-greedy algorithms for $\alpha > 1$. Let $\OPT := \min_{\cA} \cost(\cA)$, where the minimum is taken over all interactive $\cA$ that obtain $f(S) \geq Q$ at termination, for all for all possible $h^* \in \cH$. If no such $\cA$ exist, define $\OPT = \infty$.

In \cite{GuilloryBi10} it is assumed that costs are not response-dependent, 
thus $\cost(x,y) \equiv \cost(x)$, and a greedy algorithm is proposed, based on the following utility function:
\begin{equation}
u(x,S) :=\frac{\delta_{\bar{F}}((x,h(x)) \mid S)}{\cost(x)}.
\end{equation}
It is shown that for integral functions , this algorithm obtains an integer $Q$ with a worst-case cost of at most $\textrm{GCC}(\ln(Q|\cH|)+1)\cdot \OPT$, 
where $\textrm{GCC}$ is a lower bound on $\OPT$.
In \citet{GolovinKr11}, a different greedy algorithm and analysis guarantees a worst-case cost of $\alpha (\ln(Q) +1 )\cdot \OPT$ for adaptive submodular objectives and $\alpha$-approximate greedy algorithms. It is well known that the factor of $\ln(Q)$ cannot be substantially improved by an efficient algorithm, even for non-interactive problems \citep{Wolsey82,Feige98}.




The results of \cite{GuilloryBi10} can be trivially generalized to the response-dependent cost setting using the \emph{cost ratio} of the problem:
\[
\crr_\cost:= \max_{x \in \cX} \frac{\max_{y \in \cY} \cost(x,y)}{\min_{y \in \cY} \cost(x,y)}.
\]
Consider a generalized version of $u$:
\begin{equation}\label{eq:utilitygb}
u(x,S) :=\frac{\delta_{\bar{F}}((x,h(x)) \mid S)}{\min_{y \in \cY} \cost(x,y)}.
\end{equation}
Setting $\overline{\cost}(x) := \min_{y \in \cY} \cost(x,y)$, we have $\cost \leq \crr_\cost \cdot \overline{\cost}$. Using this fact, it is easy to derive an approximation guarantee of $\crr_{\cost}\cdot \OPT(\ln(Q|\cH|)+1)$, for a greedy algorithm which uses the utility function in \eqref{utilitygb} with a response-dependent cost, or $\crr_\cost\cdot \alpha (\ln(Q) + 1) \OPT $ when applied to the setting of \cite{GolovinKr11}. However, in this work we show that this trivial derivation is loose, since our new approximation bounds can be finite even if $\crr_\cost$ is infinite.


\section{A greedy algorithm for response-dependent costs}
We provide approximation guarantee for two types of objective functions. The first type captures active learning settings, while the second type is more general. Our results show that objective functions for active learning have better approximation guarantees than general objective functions. For both types of objective functions, we analyze a greedy algorithm that selects an element maximizing (or approximately maximizing) the following utility function:
\[
u^f(x,S) := \min_{h \in \vs(S)}\frac{\delta_{\min(f,Q)}((x,h(x)) \mid S)}{\cost(x,h(x))}.
\]
Note that $u^{\bar{F}}$ is equal to the function $u$ defined in \eqref{utilitygb}. 
We employ the following standard assumption in our results (see e.g.~\cite{GolovinKrRa10short}):
\begin{assumption}\label{as:fterms}
Let $f:2^\pairs \rightarrow \reals_+$, $Q >0$, $\eta > 0$. Assume that $f$ is submodular and monotone, $f(\emptyset) = 0$, and that for any $S \subseteq \pairs$, if $f(S) \geq Q -\eta$ then $f(S) \geq Q$.
\end{assumption}

In \secref{learningobj} we show an approximation guarantee for objectives meant for active learning, which we term \emph{learning objectives}. 
In \secref{generalobj} we consider general monotone submodular objective functions. 
Our guarantees hold for objective functions $f$ that satisfy the following property, which we term \emph{consistency-aware}. This property requires that the function gives at least $Q$ to any set of action-response pairs that are inconsistent with $\cH$. 
\begin{definition}\label{def:inconsistentweak}
A function $f:2^\pairs \rightarrow \reals_+$ is \emph{consistency-aware} for threshold $Q > 0$ if for all $S \subseteq \pairs$ such that $\vs_\cH(S) = \emptyset$, $f(S) \geq Q$.
\end{definition}
Note that the definition is concerned with the value of $f$ only on inconsistent sets $S$, which the algorithm never encounters. Therefore, it suffices that there exist an extension of $f$ to these sets that is consistent with all the other requirements from $f$. The function $\bar{F}$ defined in \eqref{fbar} is consistency-aware. In addition, a similar construction to $\bar{F}$ with non-uniform weights for mappings is also consistency-aware. Such
a construction is sometimes more efficient to compute than the uniform-weight construction. For instance, as shown in  \citep{GonenSaSh13b}, non-uniform weights allow a more efficient computation when the mappings
represent linear classifiers with a margin. In general, any objective $f$ can be made consistency aware using a simple transformation such as $\bar{F}$. Thus our results are relevant to a diverse class of problems.





\subsection{Guarantees for learning objectives}\label{sec:learningobj}
Active learning is an important special case of interactive learning. In active learning, the only goal is to discover information on the identity of $h^*$. We term functions that represent such a goal \emph{learning objectives}. 
\begin{definition}\label{def:learning}
A function $f:2^\pairs \rightarrow \reals_+$ is a \emph{learning objective}  for $\cH$ if $f(S) = g(\vs_\cH(S))$ where $g$ is a monotone non-increasing function.
\end{definition}
It is easy to see that all learning objectives $S \mapsto f(S)$ are monotone non-decreasing in $S$. In many useful cases, they are also submodular. In noise-free active learning, where the objective is to exactly identify the correct mapping $h^*$, one can use the learning objective $f(S) := 1 - |\vs(S)|/|\cH|$, with $Q = 1-1/|\cH|$.
This is the \emph{version space reduction} objective function \citep{GolovinKr11,GuilloryBi10}. 
In
\citet{GolovinKrRa10short} noise-aware active learning and its generalization to
the problem of Equivalence Class Determination is considered. In this generalization, there is some partition of $\cH$, and the goal is to identify
the class to which $h^*$ belongs. The objective function proposed by
\citet{GolovinKrRa10short} measures the weight of pairs in $\vs(S)$ in which each
mapping belongs to a different class. This function is also a learning
objective. In \citet{CuongLeYe14} the \emph{total generalized version
  space reduction} function is proposed. This function is also a learning objective. More generally, consider a set of structures $\cG \subseteq 2^\cH$, where the goal is to disqualify these structures from the version space, by proving  that at least one of the mappings in this structure cannot be the true $h^*$. In this case one can define the submodular learning objective $f(S) := w(\cG) - w(\cG \cap 2^{\vs(S)})$, where $w$ is a modular weight function on $\cG$, and $Q = w(\cG)$. For instance, if $\cG$ is the set of pairs from different equivalence classes in $\cH$, this is the Equivalence Class Determination objective. If $\cG$ is a set of triplets from different equivalence classes, this encodes an objective of reducing the uncertainty on the identity of $h^*$ to at most two equivalence classes. 







We show that for learning objectives, the approximation factor for a greedy algorithm that uses $u^f$ depends on a new property of the cost function, which we term the \emph{second-smallest cost ratio}, denoted by $\sscr_\cost$. 
For $x \in \cX$, let $\minsec(x)$ be the second-smallest value in the multiset \mbox{$\{ \cost(x,y) \mid y \in \cY\}$}. Define
\[
\sscr_\cost := \max_{x\in \cX,y \in \cY}\frac{\cost(x,y)}{\minsec(x)}.
\]

\begin{theorem}\label{thm:worstcase}
Let $f:2^\pairs \rightarrow \reals_+,Q >0,\eta > 0$ such that \asref{fterms} holds.
Let $\cA$ be an $\alpha$-approximate greedy algorithm for the utility function $u^f$. If $f$ is a learning objective, then $\cost(\cA) \leq \sscr_\cost \cdot \alpha   (\ln(Q/\eta)+1)\OPT.$
\end{theorem}

The ratio between the trivial bound that depends on the cost ratio
$\crr_\cost$, mentioned in \secref{setting}, and this new bound, is
$\crr_\cost/\sscr_\cost$, which is unbounded in the general case: for
instance, if each action has one response which costs $1$ and the other
responses cost $M \gg 1$, then $\crr_\cost = M$ but $\sscr_\cost = 1$.  Whenever $|\cY| = 2$, $\sscr_\cost =1$.
Thus, the approximation factor of the greedy algorithm for any binary active
learning problem is independent of the cost function. This coincides with the
results of \cite{SaettlerLaCi14,SaettlerLaCi15} for active learning with
binary labels. If $|\cY| > 2$, then the bound is smallest when
$\sscr_\cost = 1$, which would be the case if for each action there is one
preferred response which has a low cost, while all other responses have the
same high cost. For instance, consider a marketing application, in which the
action is to recommend a product to a user, and the response is either buying
the product (a preferred response), or not buying it, in which case additional
feedback could be provided from the user, but the cost (user dissatisfaction)
remains the same regardlesss of that feedback.

To prove \thmref{worstcase}, we use the following property of learning objectives: For such objectives, there exists an optimal algorithm (that is, one that obtains $\OPT$) that only selects actions for which at least two responses are possible given the action-response pairs observed so far. Formally, we define \emph{bifurcating} algorithms.
Denote the set of possible responses for $x$ given the history $S$ by \mbox{$\cY_\cH(x,S) := \{ h(x) \mid h \in \vs_\cH(S)\}.$} We omit the subscript $\cH$ when clear from context.
\begin{definition}
An interactive algorithm $\cA$ is \emph{bifurcating} for $\cH$ if for all $t$ and $h \in \cH$, $|\cY_\cH(\cA(S^h_{t}[\cA]),S^h_{t}[\cA])| \geq 2$.
\end{definition}

\begin{lemma}\label{lem:bifurcating}
For any learning objective $f$ for $\cH$ with an optimal algorithm, then there exists a bifurcating optimal algorithm for $f,\cH$.
\end{lemma}

\begin{myproof}
Let $\cA$ be an optimal algorithm for $f$. Suppose there exists some $t,h$ such that \mbox{$\cY(x_0,S^h_{t-1}[\cA]) = \{y_0\}$} for some $y_0 \in \cY$, where $x_0 := \cA(S^h_{t-1}[\cA])$. Let $\cA'$ be an algorithm that selects the same actions as $\cA$, except that it skips the action $x_0$ it if has collected the pairs $S_{t-1}^h[\cA]$. That is, $\cA'(S) = \cA(S)$ for $S \nsupseteq S^h_{t-1}[\cA]$, and $\cA'(S) = \cA(S\cup \{(x_0,y_0)\})$ for $S \supseteq S^h_{t-1}$.
Since \mbox{$\vs(S) = \vs(S\cup \{(x_0,y_0)\})$}, and $\cA$ is a learning objective, $\cA'$ obtains $Q$ as well, at the same cost of $\cA$ or less. By repeating this process a finite number of steps, we can obtain an optimal algorithm for $\cH$ which is bifurcating.
\end{myproof}



The following lemma is the crucial step in proving \thmref{worstcase}, and will also be used in the proof for the more general case below. 
The lemma applies to general consistency-aware functions. It can be used for learning objectives, because all learning objectives with a finite $\OPT$ are consistency-aware: Suppose that $f$ is a learning objective, and let $S \subseteq \pairs$ such that $\vs_\cH(S) = \emptyset$. For any $h \in \cH$, denote $S^h_* := \{(x,h(x)) \mid x \in \cX\}$. We have $\vs(S^h_*) \supseteq \vs(S)$, therefore, since $f$ is a learning objective, $f(S) \geq f(S^h_*)$. Since $\OPT$ is finite, $f(S^h_*) \geq Q$. Therefore $f(S) \geq Q$. Thus $f$ is consistency-aware. 




\begin{lemma}\label{lem:onestep}
Let $f,Q,\eta$ which satisfy \asref{fterms} such that $f$ is consistency-aware.
Let $\cA$ be an interactive algorithm that obtains $f(S) \geq Q$ at termination. Let $\gamma = \sscr_\cost$ if $\cA$ is bifurcating, and let $\gamma = \crr_\cost$ otherwise.
then
\[
\exists x\in \cX \st u^f(x,\emptyset) \geq \frac{Q}{\gamma\cdot \cost(\cA)}. 
\]
\end{lemma}




\begin{myproof}
Denote for brevity $\delta \equiv \delta_{\min(f,Q)}$.
Define $\bar{\cH} := \cY^\cX$.
Consider an algorithm $\bar{\cA}$ such that for any $S$ that is consistent with some $h\in \cH$ (that is $\vs_\cH(S) \neq \emptyset$), $\bar{\cA}(S) = \cA(S)$, and $\bar{\cA}(S) = \nil$ otherwise. 
Since $f$ is consistency-aware, we have $f(S^h[\bar\cA]) \geq Q$ for all $h \in \bar{\cH}$.

Consider a run of $\bar \cA$, and denote the pair in iteration $t$ of this run by $(x_t,y_t)$. Denote $S_{t} = \{(x_i,y_i) \mid i \leq t\}$. Choose the run such that in each iteration $t$, the response $y_t$ is in $\argmin_{y \in \cY}\delta(x_t,y\mid S_{t-1})/\cost(x_t,y)$. Let $T$ be the length of the run until termination.

Denote $\psi := \max_{ h \in \bar{\cH}} \cost(S^h[\bar \cA])$, the worst-case cost of $\bar \cA$ over $\bar \cH$.
We have
\begin{align*}
Q/\psi &\leq f(S_T)/\cost(S_T) = \frac{\sum_{t\in[T]} (f(S_t) - f(S_{t-1}))}{\sum_{t\in [T]} \cost(x_t,y_t)}\\
&= \frac{\sum_{t\in [T]} \delta((x_t,y_t)\mid S_{t-1})}{\sum_{t \in [T]} \cost(x_t,y_t)} \leq \max _{t\in [T]} \left(\delta((x_t,y_t)\mid S_{t-1})/\cost(x_t,y_t)\right),
\end{align*}
where we used $f(\emptyset) = 0$ in the second line.
Thus there exists some $t\in [T]$ such that 
$
Q/\psi \leq \delta((x_t,y_t)\mid S_{t-1})/\cost(x_t,y_t).
$

Therefore
\begin{align}
u(x_t,\emptyset) &= \min_{y \in \cY} \delta((x_t,y)\mid \emptyset)/\cost(x_t,y) \notag \geq \min_{y \in \cY} \delta((x_t,y)\mid S_{t-1})/\cost(x_t,y) \notag\\
&= \delta((x_t,y_t)\mid S_{t-1})/\cost(x_t,y_t) \geq Q/\psi.\label{eq:costbar}
\end{align}
The second line follows from the submodularity of $f$. The third line follows from the definition of $y_t$.




To prove the claim, we have left to show that \mbox{$\psi \leq \sscr \cdot \cost(\cA)$}.  
Consider again a run of $\bar \cA$. If all observed pairs are consistent with some $h \in \cH$, $\bar \cA$ and $\cA$ behave the same. Hence $\cost(S^h[\bar \cA]) = \cost(S^h[\cA])$. 
Now, consider $h \in \bar{\cH} \setminus \cH$. By the definition of $\bar \cA$, $S^h[\bar \cA]$ is a prefix of $S^h[\cA]$. Let $T = |S^h[\bar \cA]|$ be the number of iterations until $\bar \cA$ terminates. Then $S_{T-1}^h[\bar \cA]$ is consistent with some $h' \in \cH$. 


Let $x_T$ be the action that $\cA$ and $\bar \cA$ select at iteration $T$, and let $h' \in \cH$ which is consistent with $S_{T-1}^h[\bar \cA]$, and incurs the maximal possible cost in iteration $T$. Formally, $h'$ satisfies $h'(x_T) \in \argmax_{y \in \cY_\cH(x_T,S_{T-1}^h[\cA])}  \cost(x_T,y)$. 
Now, compare the run of $\bar \cA$ on $h$ to the run of $\cA$ on $h'$. 
In the first $T-1$ iterations, the algorithms observe the same pairs.
In iteration $T$, they both select $x_T$. $\bar \cA$ observes $h(x_T)$, while $\cA$ observes $h'(x_T)$. $\bar \cA$ terminates after iteration $T$. Hence

$\cost(S^h[\bar \cA]) = \cost(S_{T-1}^h[\cA]) + \cost(x_T,h(x_T))
= \cost(S_T^{h'}[\cA]) - \cost(x_T,h'(x_T)) + \cost(x_T,h(x_T)).$

Consider two cases: (a) $\cA$ is not bifurcating. Then $\gamma = \crr$, and so $\cost(x_T,h(x_T)) \leq \gamma \cost(x_T,h'(x_T))$. (b) $\cA$ is bifurcating. Then there are at least two possible responses in $\cY_\cH(x_T,S^h_{T-1}[\cA])$. Therefore $\cost(x_T,h'(x_T)) \geq \phi(x_T)$. By the definition of $\sscr_\cost$, $\cost(x_T,h(x_T)) \leq \sscr_\cost \cdot \phi(x_T)$. Therefore $\cost(x_T,h(x_T)) \leq r_\cost \cost(x_T,h'(x_T))) = \gamma \cost(x_T,h'(x_T)))$. 

In both cases, 

$\cost(x_T,h(x_T)) - \cost(x_T,h'(x_T)) \leq (\gamma - 1)\cost(x_T,h'(x_T)).$

Therefore 

$\cost(S^h[\bar \cA]) \leq \cost(S_T^{h'}[\cA]) + (\gamma - 1)\cost(x_T,h'(x_T)) \leq \gamma\cost(S_T^{h'}[\cA]),$

where the last inequality follows since $\cost(S_T^{h'}[\cA])\leq \cost(S_T^{h'}[\cA])$. 
Thus for all $h \in \bar{\cH}$, $\cost(S^h[\bar \cA]) \leq \gamma \cdot \cost(\cA)$, hence $\psi \leq \gamma \cdot \cost(\cA)$. Combining this with \eqref{costbar}, the proof is concluded.




\end{myproof}


In the proof of \thmref{worstcase} we further use the following lemmas, which can be proved using standard techniques (see e.g.~\cite{GuilloryBi10,GolovinKr11}). The proofs are omitted due to lack of space, 
\begin{lemma}\label{lem:greedylem}
Let $\beta,\alpha \geq 1$. Let $f,Q,\eta$ such that \asref{fterms} holds.
If for all $S \subseteq \pairs$, $\max_{x \in \cX} u^f(x,S) \geq \frac{Q- f(S)}{\beta\OPT}$, then for any $\alpha$-approximate greedy algorithm with $u^f$,
$\cost(\cA) \leq \alpha \beta (\log(Q/\eta) + 1)\OPT.$
\end{lemma}

\begin{lemma}\label{lem:fprime}
Let $f,Q,\eta$ such that \asref{fterms} holds and $f$ is consistency-aware. 
Let $S \subseteq \pairs$. Define $f':2^\pairs \rightarrow \reals_+$ by
$f'(T) := f(T\cup S) - f(S)$. Let $Q' = Q -  f(S)$.
Then 
\begin{enumerate}
\item $f'$ is submodular, monotone and consistency-aware, with $f'(\emptyset) = 0$. 
\item Let $\cA$ be an interactive algorithm for $f',Q'$. Let $\beta \geq 1$.
If 
$\max_{x\in \cX} u^{f'}(x,\emptyset) \geq \frac{Q'}{\beta \OPT'}$, where $\OPT'$ is the optimal cost for $f',Q'$, then for any $S \subseteq \pairs$, $\max_{x\in \cX} u^f(x,S) \geq \frac{Q-f(S)}{\beta\OPT}.$
\end{enumerate}
\end{lemma}


\begin{myproof}[of \thmref{worstcase}]

Let $f',Q',\OPT'$ as in \lemref{fprime}, and let $\cA^*$ be an optimal algorithm for $f',Q'$. Let $\cA^*$ be an optimal algorithm for $f',Q'$. Since $f$ is a learning objective, then so is $f'$, and by \lemref{bifurcating} we can choose $\cA^*$ to be bifurcating. Combining this with the first part of \lemref{fprime}, the conditions of \lemref{onestep} hold. Therefore
$u^{f'}(x,\emptyset) \geq Q'/\cost(\cA^*) \geq Q'/(\sscr_\cost\cdot\OPT').$
By the second part of \lemref{fprime}, 

$\forall S \subseteq \pairs, u^{f}(x,S) \geq \frac{Q-f(S)}{\sscr_\cost\cdot\OPT}.$

Therefore, by \lemref{greedylem}, $\cost(\cA) \leq \alpha (\log(Q/\eta) + 1)\cdot \sscr_\cost \cdot \OPT.$
\end{myproof}





Next, we show that a linear dependence of the approximation guarantee on $\sscr_\cost$ is necessary for any greedy algorithm. To show the lower bound,
we must exclude greedy algorithms that choose the utility function according to  the set of available actions $\cX$. Formally, define \emph{local} greedy algorithms as follows. Assume there is a super-domain of all possible actions $\bar{\cX}$, and consider an algorithm which receives as input a subset $\cX \subseteq \bar{\cX}$ of available actions. We say that such an algorithm is \emph{local} greedy if it greedily selects the next action out of $\cX$ using a fixed utility function $u: \bar{\cX} \times 2^{\bar{\cX}\times \cY} \rightarrow \reals_+$, which does not depend on $\cX$.
The following lower bound shows that there exists a learning objective such that the approximation guarantee of any local greedy algorithm grows with $\sscr_\cost$ or is trivially bad. 
\begin{theorem}\label{thm:lowerboundlearning}
Let $f$ be the version-space reduction objective function with the corresponding $Q = 1-1/|\cH|$ and $\eta = 1/|\cH|$. 
For any value of $\OPT$, $\sscr_\cost > 1$, and integer size of $Q/\eta$, there exist $\bar{\cX},\cH$, and $\cost$ such that $\cost(x,y)$ depends only on $y$, and such that for any local greedy algorithm $\cA$, there exists an input domain $\cX\subseteq \bar{\cX}$ such that, for $\eta$ as in \thmref{worstcase},
\[
\cost(\cA) \geq \min\left(\frac{\sscr_\cost}{\log_2(Q/\eta)},\frac{Q/\eta}{\log_2(Q/\eta)}\right) \cdot \OPT.
\]
Here $\cost(\cA)$ and $\OPT$ refer to the costs for the domain $\cX$.
\end{theorem}

\begin{myproof}
Define $\cY = \{1,2,3\}$.
Let $\bar{\cX} = \{a_i \mid i \in [k]\} \cup \{b_j^t \mid j\in [k], t \in [\ceil{\log_2(k-2)}]\}$. Let $\cost(x,y) = c_y$ for all $x \in \cX$, where $c_3 \geq c_2 > c_1 = 0$. Set $c_2,c_3$ such that $\sscr_\cost = c_3/c_2$. Let $\cH = \{ h_i \mid i \in [k]\}$, where $h_i$ is defined as follows: for $a_j$,
\[
h_i(a_j) := \begin{cases}
1 & i = j \\
2 & i \neq j.
\end{cases} 
\]
For $b^t_j$ and $i \neq j$, let $l_{i,j}$ be the location of $i$ in $(1,\ldots,j-1,j+1,\ldots,k)$, where the locations range from $0$ to $k-2$. Denote by $l^t_{i,j}$ the $t$'th most significant bit in the binary expansion of $l_{i,j}$ to $\ceil{\log_2(k-2)}$ bits. Define
\[
h_i(b^t_j) := \begin{cases}
1 & i \neq j \wedge l_{i,j}^t = 0\\
2 & i \neq j \wedge l_{i,j}^t = 1\\
3 & i = j
\end{cases} 
\]

Fix an index $n \in [k]$. Let $\cX_n = \{a_i \mid i \in [k]\} \cup \{ b^t_n \mid t \in [\ceil{\log_2(k-2)}]\}$.
We now show an interactive algorithm for $\cX_n$ and bound its worst-case cost. 
On the first iteration, the algorithm selects action $a_n$. If the result is $1$, then $\vs(S) = \{h_n\}$, hence $f(S) \geq Q$. In this case the cost is $c_1 = 0$. Otherwise, the algorithm selects all actions in $\{b^t_n \mid  t \in [\ceil{\log_2(k-2)}\}$. The responses reveal the binary expansion of $l_{j,n}$, thus limiting the version space to the a single $h_i$, hence $f(S) \geq Q$. In this case the total cost is at most $c_2 \ceil{\log_2(k-2)}$.


Now, consider a local greedy algorithm. 
Let $\sigma:[k] \rightarrow [k]$ be a permutation that represents the order in which $a_1,\ldots,a_k$ would be selected by the utility function if only $a_i$ were available, and their response was always $2$. Formally, $\sigma(i) = \argmax_{i \in [k]} u(a_{\sigma(i)},\{(a_{\sigma(i')},2) \mid i' \in [i-1] \})$.\footnote{We may assume without loss of generality that $u(x,S) = 0$ whenever $(x,y) \in S$}

Suppose the input to the algorithm is $\cX_{\sigma(k)}$.
Denote $S_i = \{(a_{\sigma(i')},2) \mid i' \in [i-1] \}$, and suppose $h^* = h_{\sigma(k)}$. First, assume that $\max_t u(b^t_{\sigma(k)},S_{i'-1}) < u(a_{\sigma(k)},S_{k-1})$. Then all of $a_{\sigma(1)},\ldots,a_{\sigma(k-1)}$ are selected before any of $b^t_{\sigma(k)}$, and the version space is reduced to a singleton only after these $k-1$ actions. Therefore the cost of the run is at least $c_2(k-1)$. 
Second, assume that this assumption does not hold. Then there exists an integer $i'$ such that $\max_t u(b^t_{\sigma(k)},S_{i'-1}) > u(a_{\sigma(i)},S_{i'-1})$. Let $i'$ be the smallest such integer. Then, the algorithm receives $2$ on each of the actions $a_{\sigma(1)},\ldots,a_{\sigma(i'-1)}$, and its next action is $b^t_{\sigma(k)}$ for some $t$. Hence the cost of the run is at least $c_3.$

To summarize, the worst-case cost of every local greedy algorithm is at least $\min\{c_3, c_2(k-1)\}$ for at least one of the inputs $\cX_n$. The worst-case cost of the optimal algorithm for each $\cX_n$ is at most $c_2 \ceil{\log_2(k-2)}$. The statement of the theorem follows.
\end{myproof}





\subsection{Guarantees for general objectives}\label{sec:generalobj}







In the previous section we showed that for learning objectives, the achievable approximation guarantee for greedy algorithms is characterized by $\sscr_\cost$. We now turn to general consistency-aware objective functions. We show that the factor of approximation for this class depends on a different property of the cost function, which is lower bounded by $\sscr_\cost$. Define $\cmax := \max_{(x,y) \in \cX\times \cY} \cost(x,y)$, and let
\[
\phi_{\min} := \min_{x \in \cX} \phi(x), \qquad \gsscr_\cost := \frac{\cmax}{\phi_{\min}}.
\]
We term the ratio $\gsscr_\cost$ the \emph{Global second smallest cost ratio}.
As we show below, the approximation factor is best when $\gsscr_\cost$ is equal to $1$. This is the case if there is at most one preferred response for every action, and in addition, all the non-preferred responses for all actions have the same cost. 

\begin{theorem}\label{thm:nonlearning}
Let $f:2^\pairs \rightarrow \reals_+,Q >0,\eta > 0$ such that \asref{fterms} holds and $f$ is consistency-aware. 
Let $\cA$ be an $\alpha$-approximate greedy algorithm for the utility function $u^f$. Then
$
\cost(\cA) \leq 2\min(\gsscr_\cost,\crr_\cost) \cdot \alpha \cdot (\log(Q/\eta)+1) \cdot \OPT. 
$
\end{theorem}
Like \thmref{worstcase} for learning objectives, this result for general objectives is a significant improvement over the trivial bound, mentioned in \secref{setting}, which depends on the cost ratio, since the ratio $\gsscr_\cost/\crr_\cost$ can be unbounded. For instance, consider a case where each action has one response with a cost of $1$ and all other responses have a cost of $M \gg 1$. Then $\crr_\cost = M$ but $\gsscr_\cost = 1$.



The proof of \thmref{nonlearning} hinges on two main observations: First, any interactive algorithm may be ``reordered'' without increasing its cost, so that all actions with only one possible response (given the history so far) are last. Second, there are two distinct cases for the optimal algorithm: In one case, for all $h \in \cH$, the optimal algorithm obtains a value of at least $Q/2$ before performing actions with a single possible response. In the other case, there exists at least one mapping $h$ for which actions with a single possible response obtain at least $Q/2$ of the value. We start with the following lemma, which handles the case where $\OPT < \phi_{\min}$. 

\newcommand{\withone}[1]{{#1}^{[y(x)]}}
\begin{lemma}\label{lem:smallopt}
Let $f:2^\pairs \rightarrow \reals_+$, $Q > 0$. Suppose that $f$ is submodular, and $f(0) = \emptyset$.
If $\OPT < \phi_{\min}$, then $\max_{x \in \cX}u^f(x,\emptyset) \geq Q/OPT$.
\end{lemma}
\begin{myproof}
For every action $x \in \cX$ there is at most a single $y$ with $\cost(x,y) < \phi_{\min}$. Denote this response by $y(x)$. 
Let $\cA$ be an optimal algorithm for $f,Q$. For any value of $h^* \in \cH$, $\cA$ only receives responses with costs less than $\phi_{\min}$. Therefore for any $x$ that $\cA$ selects, it receives the response $y(x)$, regardless of the identity of $h^*$. In other words, for all $h \in \cH$, in every iteration $t$, $\cA$ selects an action $x$ such that $\cY(x,S^h_{t-1}[\cA]) = \{y(x)\}$. It follows that for all $t$, $S^h_{t}[\cA]$ is the same for all $h \in \cH$.
Therefore, there is a fixed set of actions that $\cA$ selects during its run, regardless of $h^*$. Let $\cX' \subseteq \cX$ be that set. Then for all $h \in \cH,x\in X'$, $h(x) = y(x)$. 
For a set $A \subseteq \cX$, denote $\withone{A} = \{(x,y(x)) \mid x \in A\}$. 
We have $f(\withone{\cX'}) \geq Q$ and $\cost(\withone{\cX'}) = \OPT$.
By the submodulrity of $f$, and since $f(\emptyset) = 0$, we have

$Q/\OPT \leq f(\withone{\cX'})/\OPT \leq \sum_{x \in \cX'} f((x,y(x)))/\sum_{x \in \cX'}\cost(x,y(x)).$

Therefore there exists some $x \in \cX'$ with $f((x,y(x)))/\cost(x,y(x)) \geq Q/\OPT$.
Moreover, for this $x$ we have $\cY(x,\emptyset) = \{y(x)\}$. Therefore 
$u^f(x,\emptyset) = f((x,y(x)))/\cost(x,y(x)) \geq Q/\OPT.$
\end{myproof}

We now turn to the main lemma, to address the two cases described above.
\begin{lemma}\label{lem:optc2}
Let $f:2^\pairs \rightarrow \reals_+$, $Q > 0$. Suppose that $f$ is submodular, and $f(0) = \emptyset$. Assume that $f$ is consistency-aware.
There exists $x \in \cX$ such that $u^f(x,\emptyset) \geq \frac{Q}{2\min(\gsscr_\cost, \crr_\cost) \OPT}$.
\end{lemma}

\begin{myproof}
If $\OPT < \phi_{\min}$, the statement holds by \lemref{smallopt}. 
Suppose that $\OPT \geq \phi_{\min}$. Let $\cA^*$ be an optimal algorithm for $f,Q$. We may assume without loss of generality, that for any $h^* \in \cH$, if $\cA^*$ selects an action that has only one possible response (given the current version space) at some iteration $t$, then all actions selected after iteration $t$ also have only one possible response.
This does not lose generality: let $t$ be the first iteration such that the action at iteration $t$ has one possible response, and the action at iteration $t+1$ has two possible responses. Consider an algorithm which behaves the same as $\cA^*$, except that at iteration $t$ it selects the second action, and at iteration $t+1$ it selects the first action (regardless of the response to the first action).  This algorithm has the same cost as $\cA^*$.

For $h \in \cH$, define $\val(h) := f(S_{t_h}^h[\cA^*])$, where $t_h$ is the last iteration in which an action with more than one possible response (given the current version space) is selected, if $h^* = h$. 
Consider two cases: (a) $\min_{h \in \cH} \val(h) \geq Q/2$ and (b) $\exists h \in \cH, \val(h) < Q/2$. 
In case (a), there is a bifurcating algorithm that obtains  $f(S) \geq Q/2$ at cost at most $\OPT$: This is the algorithm that selects the same actions as $\cA^*$, but terminates before selecting the first action that has a single response given the current version space. We also have $\sscr_\cost \leq \min(\gsscr_\cost,\crr_\cost)$. By \lemref{onestep}, there exists some $x \in \cX$ such that $u^f(x,\emptyset) \geq \frac{Q}{2\min(\gsscr_\cost,\crr_\cost)\OPT}$.

In case (b), let $h \in \cH$ such that $\val(h) < Q/2$. Denote $S_t := S_t^h[\cA^*]$. Let $(x_t,h(x_t))$ be the action and the response received in iteration $t$ if $h^* = h$. Then $f(S_{t_h}) < Q/2$. 
Let $S' = \{(x_t,h(x_t)) \mid t > t_h\}$. Then $f(S_{t_h}\cup S') \geq Q$. Since $f(\emptyset) = 0$ and $f$ is submodular,

$f(S') = f(S') - f(\emptyset) \geq f(S_{t_h}\cup S') - f(S_{t_h}) \geq Q - \val(h) \geq Q/2.$

In addition, $f(S') \leq \sum_{t> t_h} f(\{(x_t,h(x_t))\})$. Hence 
$
\frac{Q}{2\OPT} \leq \frac{f(S')}{\OPT} \leq \frac{\sum_{t> t_h} f(\{(x_t,h(x_t))\})}{\sum_{t> t_h}\cost(x_t,y_t)}.
$ 
Therefore there is some $t'$ such that 

$\frac{f(\{(x_{t'},h(x_{t'}))\})}{\cost(x_{t'},h(x_{t'}))} \geq \frac{Q}{2\OPT}.$


Therefore,
\begin{align*}
&u^f(x_{t'},\emptyset) = \min_{y \in \cY(x_{t'},\emptyset)} \min\{f(\{(x_{t'},y)\}),Q\}/\cost(x_{t'},y) \\
&\quad\geq \min\{Q/\cmax,\min_{y \in \cY}f(\{(x_{t'},y)\})/\cost(x_{t'},y)\}\\
  &\quad\geq \min\{ Q/\cmax, \frac{Q}{2\OPT}, \min_{y \in \cY\setminus \{h(x_{t'})\}} f(\{(x_{t'},y)\})/\cost(x_{t'},y)\}.
\end{align*}

Now, $\cmax \leq \gsscr_\cost \cdot \phi_{\min} \leq \gsscr_\cost\cdot \OPT, $
from our assumption that $\OPT \geq \phi_{\min}$, and $\cmax \leq \crr_\cost \cost(x_{t'},h(x_{t'})) \leq \crr_\cost \cdot \OPT.$
Therefore
\begin{align*}
u^f(x_{t'},\emptyset) \geq \min\Bigg\{&\frac{Q}{2\min(\gsscr_\cost,\crr_\cost)\OPT}, \min_{y \in \cY\setminus \{h(x_{t'})\}} \frac{f(\{(x_{t'},y)\})}{\cost(x_{t'},y)}\Bigg\}.
\end{align*}

We have left to show a lower bound on $\min_{y \in \cY\setminus \{h(x_{t'})\}} \frac{f(\{(x_{t'},y)\})}{\cost(x_{t'},y)}$. 
By the choice of $t'$, $x_{t'}$ has only one possible response given the current version space, that is $|\cY(x_{t'},S_{{t'}-1})| = 1$. Since the same holds for all $t > t_h$, we have $\vs(S_{t'-1}) = \vs(S_{t_h})$, hence also $\cY(x_{t'},S_{t_h}) = \{h(x_{t'})\}$. It follows that for $y \in \cY\setminus \{h(x_{t'})\}$, the set $S_{t_h} \cup \{(x_{t'},y)\}$  is not consistent with any $h \in \cH$.
Since $f$ is consistency-aware, it follows that $f(S_{t_h} \cup \{(x_{t'},y)\}) \geq Q$. Therefore 

$f(\{(x_{t'}, y)\}) = f(\{(x_{t'}, y)\}) - f(\emptyset) \geq f(S_{t_h} \cup \{(x_{t'},y)\}) - f(S_{t_h}) \geq Q - \val(h) \geq Q/2. $

Hence $
\frac{f(\{(x_{t'}, y)\})}{\cost(x_{t'}, y)} \geq \frac{Q}{2c_{\max}} \geq \frac{Q}{2\min(\gsscr_\cost,\crr_\cost)\OPT}.$
It follows that $u^f(x_t,\emptyset) \geq \frac{Q}{2c_{\max}} \geq \frac{Q}{2\min(\gsscr_\cost,\crr_\cost)\OPT}$ also in case (b).
\end{myproof}

Using the lemmas above, the proof of \thmref{nonlearning} is straight forward.

\begin{myproof}[of \thmref{nonlearning}]

Let $f',Q',\OPT'$ as in \lemref{fprime}, and let $\cA^*$ be an optimal algorithm for $f',Q'$. Let $\cA^*$ be an optimal algorithm for $f',Q'$. 
From the first part of \lemref{fprime}, the conditions of \lemref{optc2} hold for $f',Q'$. Therefore
$u^{f'}(x,\emptyset) \geq \frac{Q'}{2\min(\gsscr_\cost,\crr_\cost)\OPT'}.$
By the second part of \lemref{fprime},
$\forall S \subseteq \pairs, \quad u^{f}(x,S)  \geq \frac{Q-f(S)}{2\min(\gsscr_\cost,\crr_\cost)\OPT}.$
Therefore, by \lemref{greedylem},

$\cost(\cA) \leq 2 \alpha \min(\gsscr_\cost,\crr_\cost) (\log(Q/\eta) + 1)\cdot \OPT.$
\end{myproof}




The guarantee of \thmref{nonlearning} for general objectives is weaker than the guarantee for learning objectives given in \thmref{worstcase}: The ratio $\min(\gsscr_\cost,\crr_\cost)/\sscr_\cost$ is always at least $1$, and can be unbounded. For instance, if there are two actions that have two responses each, and all action-response pairs cost $1$, except for one action-response pair which costs $M \gg 1$, then $\crr_\cost = 1$ but $\gsscr_\cost = M$. Nonetheless, the following theorem shows that for general functions, a dependence on $\min(\gsscr_\cost,\crr_\cost)$ is essential in any greedy algorithm. 




\begin{theorem}\label{thm:lowerboundgeneral}
For any values of $\gsscr_\cost,\crr_\cost > 0$, there exist $\bar{\cX},\cY,\cH,\cost$ with $|\cY| = 2$ and $\sscr_\cost = 1$, and a submodular monotone $f$ which is consistency-aware, with $Q/\eta = 1$, such that for any local greedy algorithm $\cA$, there exists an input domain $\cX\subseteq \bar{\cX}$ such that
$
\cost(\cA) \geq \half \min(\gsscr_\cost,\crr_\cost)\cdot \OPT,
$
where $\cost(\cA)$ and $\OPT$ refer to the costs of an algorithm running on the domain $\cX$.
\end{theorem}


\begin{myproof}
Define $\cY := \{0,1\}$. Let $g,r >0$ be the desired values for $\gsscr_\cost, \crr_\cost$. Let $c_1 > 0$, $c_2 := c_1\min(g,r)$. If $g < r$, define $c_3 := c_1/r$, $c_4 := c_1$. Otherwise, set $c_4 := c_3 := c_2/g$.
Define $k := \ceil{c_2/c_1} + 1$. 
Let $\bar{\cX} = \{a_i \mid i \in [k]\} \cup \{b_i \mid i \in [k]\} \cup \{c\}$. Let $\bar{\cH} = \{h_i \mid i \in [k]\}$ where $h_i$ is defined as follows:
$\forall i,j \in [k], h_i(a_j) = h_i(b_j)$, and equal to $1$ if and only if $i = j$, and zero otherwise, and $\forall i \in [k], h_i(c) = i \bmod 2.$
Let the cost function be as follows, where $c_2 \geq c_1 > 0$, and $c_3,c_4 > 0$: $\cost(a_i,y) = c_1$, $\cost(b_i,y) = c_{y+1}$, and $\cost(c, y) = c_{y+3}.$
Then $\gsscr_\cost = g$, $\crr_\cost = r$ as desired.

Define $f$ such that $\forall S \subseteq \pairs$, $f(S) = Q$ if there exists in $S$ at least one of $(a_i,1)$ for some $i \in [k]$ or $(b_i,y)$ for some $i \in [k],y\in \cY$. Otherwise, $f(S) = 0$. Note that $(f,Q)$ is consistency-aware.

Fix an index $n \in [k]$. Let $\cX_n = \{a_i \mid i \in [k]\} \cup \{b_n\}$.
We have $\OPT = 2c_1$: An interactive algorithm can first select $a_n$, and then, only if the response is $y=0$, select $b_n$. 
Now, consider a local greedy algorithm with a utility function $u$.
 Let $\sigma:[k] \rightarrow [k]$ be a permutation that represents the order in which $a_1,\ldots,a_k$ would be selected by the utility function if only $a_i$ were considered, and their response was always $y=0$. Formally, $\sigma(i) = \argmax_{i \in [k]} u(a_{\sigma(i)},\{(a_{\sigma(i')},0) \mid i' \in [i-1] \})$.\footnote{We may assume without loss of generality that $u(x,S) = 0$ whenever $(x,y) \in S$}

Now, suppose the input to the algorithm is $\cX_{\sigma(k)}$.
Denote $S_i = \{(a_{\sigma(i')},0) \mid i' \in [i-1] \}$, and 
suppose that there exists an integer $i'$ such that $u(b_{\sigma(k)},S_{i'-1}) > u(a_{\sigma(i)},S_{i'-1})$, and let $i'$ be the smallest such integer. Then, if the algorithm receives $0$ on each of the actions $a_{\sigma(1)},\ldots,a_{\sigma(i'-1)}$, its next action will be $b_{\sigma(k)}$. 
In this case, if $h^* = h_{\sigma(k)}$, then $b_{\sigma(k)}$ is queried before $a_{\sigma(k)}$ is queried and the response $y=1$ is received. Thus the algorithm pays at least $c_2$ in the worst-case. On the other hand, if such an integer $i'$ does not exist, then if $h^* = h_{\sigma(k)}$, the algorithm selects actions $a_{\sigma(1)},\ldots,a_{\sigma(k-1)}$ before terminating. In this case the algorithm receives $k-1$ responses $0$, thus its cost is at least $c_1(k-1)$. 
To summarize, every local greedy algorithm pays at least $\min\{c_2, c_1(k-1)\}$ for at least one of the inputs $\cX_n$, while $\OPT = 2c_1$. By the definition of $k$,  $\min\{c_2, c_1(k-1)\} \geq c_2$. 
Hence the cost of the local greedy algorithm is at least $\frac{c_2}{2c_1}\OPT$. 
\end{myproof}


To summarize, for both learning objectives and general objectives, we have shown that the factors $\sscr_\cost$ and $\gsscr_\cost$, respectively, characterize the approximation factors obtainable by a greedy algorithm. 


\section{Experiments}\label{sec:exp}

\begin{table}[h]
\scriptsize
\tableresults
\vspace{0.2em}
\caption{Results of experiments. Left: Facebook dataset, Right: GR-QC dataset}
\label{tab:results}
\end{table}


We performed experiments to compare the worst-case costs of a greedy algorithm that uses the proposed $u^f$, to a greedy algorithm that ignores response-dependent costs, and uses instead variant of $u^f$, notated $u_2^f$, that assumes that responses for the same action have the same cost, which was set to be the maximal response cost for this action. We also compared to $u_3^f$, a utility function which gives the same approximation guarantees as given in \thmref{nonlearning} for $u^f$.
Formally, $u_2^f(x,S) := \min_{h \in \vs(S)}\frac{\delta_{\min(f,Q)}((x,h(x)) \mid S)}{\max_{y \in \cY}\cost(x,y)}$ and $u_3^f(x,S) := \min_{h \in \vs(S)}\frac{\delta_{\min(f,Q)}((x,h(x)) \mid S)}{\min\{\cost(x,h(x)), \phi_{\min}\}}.$

We tested these algorithms on a social network marketing objective, where users in a social network are partitioned into communities.
Actions are users, and a response identifies the community the user belongs to. 
We tested two objective functions: ``edge users'' counts how many of the actions are users who have friends not from their community, assuming that these users can be valuable promoters across communities. The target value $Q$ was set to $50$.
The second objective function was the version-reduction objective function, and the goal was to identify the true partition into communities out of the set of possible partitions, which was generated by considering several possible sets of ``center users'', which were selected randomly.


We compared the worst-case costs of the algorithms under several configurations of number of communities and the values of $\sscr_\cost$, $\gsscr_\cost$. The cost ratio $\crr_\cost$ was infinity in all experiments, obtained by always setting a single response to have a cost of zero for each action. Social network graphs were taken from a friend graph from Facebook\footnote{\url{http://snap.stanford.edu/data/egonets-Facebook.html}} \citep{LeskovecMc12}, and a collaboration graph from Arxiv GR-QC community\footnote{\url{http://snap.stanford.edu/data/ca-GrQc.html}}~\mbox{\citep{LeskovecKlFa07}}. The results are reported in \tabref{results}. We had $|\cH| = 100$ for all tests with 3 communities, and $|\cH| = 500$ for all tests with 10 communities. 

The results show an overall preference to the proposed $u^f$. 


\subsubsection*{Acknowledgements}
This work was supported in part by the Israel Science Foundation (grant No. 555/15).

\bibliographystyle{splncs03}

\begin{thebibliography}{10}
\providecommand{\url}[1]{\texttt{#1}}
\providecommand{\urlprefix}{URL }

\bibitem{CuongLeYe14}
Cuong, N., Lee, W., Ye, N.: Near-optimal adaptive pool-based active learning
  with general loss. In: 30th conference on Uncertainty in Artificial
  Intelligence (2014)

\bibitem{Dasgupta04short}
Dasgupta, S.: Analysis of a greedy active learning strategy. NIPS  17,
  337--344 (2004)

\bibitem{Feige98}
Feige, U.: A threshold of ln(n) for approximating set cover. Journal of the ACM
  (JACM)  45(4),  634--652 (1998)

\bibitem{GolovinKr11}
Golovin, D., Krause, A.: Adaptive submodularity: Theory and applications in
  active learning and stochastic optimization. Journal of Artificial
  Intelligence Research  42,  427--486 (2011)

\bibitem{GolovinKrRa10short}
Golovin, D., Krause, A., Ray, D.: Near-optimal bayesian active learning with
  noisy observations. In: NIPS. pp. 766--774 (2010)

\bibitem{GonenSaSh13b}
Gonen, A., Sabato, S., Shalev-Shwartz, S.: Efficient active learning of
  halfspaces: an aggressive approach. Journal of Machine Learning Research  14,
   2487--2519 (2013)

\bibitem{GuilloryBi10}
Guillory, A., Bilmes, J.A.: Interactive submodular set cover. In: Proceedings
  of the 27th International Conference on Machine Learning {(ICML)}. pp.
  415--422 (2010)

\bibitem{KapoorHoBa07}
Kapoor, A., Horvitz, E., Basu, S.: Selective supervision: Guiding supervised
  learning with decision-theoretic active learning. In: Proceedings of IJCAI
  (2007)

\bibitem{LeskovecKlFa07}
Leskovec, J., Kleinberg, J., Faloutsos, C.: Graph evolution: Densification and
  shrinking diameters. ACM Transactions on Knowledge Discovery from Data (TKDD)
   1(1), ~2 (2007)

\bibitem{LeskovecMc12}
Leskovec, J., Mcauley, J.J.: Learning to discover social circles in ego
  networks. In: Advances in neural information processing systems. pp. 539--547
  (2012)

\bibitem{LinBi11}
Lin, H., Bilmes, J.: A class of submodular functions for document
  summarization. In: Proceedings of the 49th Annual Meeting of the Association
  for Computational Linguistics: Human Language Technologies - Volume 1. pp.
  510--520. HLT '11 (2011)

\bibitem{MccallumNi98short}
McCallum, A.K., Nigam, K.: Employing em and pool-based active learning for text
  classification. In: ICML (1998)

\bibitem{MirzasoleimanKaSaKr13short}
Mirzasoleiman, B., Karbasi, A., Sarkar, R., Krause, A.: Distributed submodular
  maximization: Identifying representative elements in massive data. In: NIPS.
  pp. 2049--2057 (2013)

\bibitem{NemhauserWoFi78}
Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for
  maximizing submodular set functions—i. Mathematical Programming  14(1),
  265--294 (1978)

\bibitem{SabatoSaSr13}
Sabato, S., Sarwate, A.D., Srebro, N.: Auditing: Active learning with
  outcome-dependent query costs. In: Advances in Neural Information Processing
  Systems 26 {(NIPS)} (2013)

\bibitem{SabatoSaSr15}
Sabato, S., Sarwate, A.D., Srebro, N.: Auditing: Active learning with
  outcome-dependent query costs. arxiv preprint ArXiv:1306.2347v4  (2015)

\bibitem{SaettlerLaCi14}
Saettler, A., Laber, E., Cicalese, F.: Trading off worst and expected cost in
  decision tree problems and a value dependent model. arXiv preprint
  arXiv:1406.3655  (2014)

\bibitem{SaettlerLaCi15}
Saettler, A., Laber, E., Cicalese, F.: Approximating decision trees with value
  dependent testing costs. Information Processing Letters  115(6–8),  594 --
  599 (2015)

\bibitem{Wolsey82}
Wolsey, L.: An analysis of the greedy algorithm for the submodular set covering
  problem. Combinatorica  2(4),  385--393 (1982)

\end{thebibliography}





























































\end{document}

1602.07120.extracted_bib
{CuongLeYe14 Cuong, N., Lee, W., Ye, N.: Near-optimal adaptive pool-based active learning with general loss. In: 30th conference on Uncertainty in Artificial Intelligence (2014)
1602.07120.extracted_bib
{Dasgupta04short Dasgupta, S.: Analysis of a greedy active learning strategy. NIPS 17, 337--344 (2004)
1602.07120.extracted_bib
{Feige98 Feige, U.: A threshold of ln(n) for approximating set cover. Journal of the ACM (JACM) 45(4), 634--652 (1998)
1602.07120.extracted_bib
{GolovinKr11 Golovin, D., Krause, A.: Adaptive submodularity: Theory and applications in active learning and stochastic optimization. Journal of Artificial Intelligence Research 42, 427--486 (2011)
1602.07120.extracted_bib
{GolovinKrRa10short Golovin, D., Krause, A., Ray, D.: Near-optimal bayesian active learning with noisy observations. In: NIPS. pp. 766--774 (2010)
1602.07120.extracted_bib
{GonenSaSh13b Gonen, A., Sabato, S., Shalev-Shwartz, S.: Efficient active learning of halfspaces: an aggressive approach. Journal of Machine Learning Research 14, 2487--2519 (2013)
1602.07120.extracted_bib
{GuilloryBi10 Guillory, A., Bilmes, J.A.: Interactive submodular set cover. In: Proceedings of the 27th International Conference on Machine Learning {(ICML). pp. 415--422 (2010)
1602.07120.extracted_bib
{KapoorHoBa07 Kapoor, A., Horvitz, E., Basu, S.: Selective supervision: Guiding supervised learning with decision-theoretic active learning. In: Proceedings of IJCAI (2007)
1602.07120.extracted_bib
{LeskovecKlFa07 Leskovec, J., Kleinberg, J., Faloutsos, C.: Graph evolution: Densification and shrinking diameters. ACM Transactions on Knowledge Discovery from Data (TKDD) 1(1), ~2 (2007)
1602.07120.extracted_bib
{LeskovecMc12 Leskovec, J., Mcauley, J.J.: Learning to discover social circles in ego networks. In: Advances in neural information processing systems. pp. 539--547 (2012)
1602.07120.extracted_bib
{LinBi11 Lin, H., Bilmes, J.: A class of submodular functions for document summarization. In: Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies - Volume 1. pp. 510--520. HLT '11 (2011)
1602.07120.extracted_bib
{MccallumNi98short McCallum, A.K., Nigam, K.: Employing em and pool-based active learning for text classification. In: ICML (1998)
1602.07120.extracted_bib
{MirzasoleimanKaSaKr13short Mirzasoleiman, B., Karbasi, A., Sarkar, R., Krause, A.: Distributed submodular maximization: Identifying representative elements in massive data. In: NIPS. pp. 2049--2057 (2013)
1602.07120.extracted_bib
{NemhauserWoFi78 Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions—i. Mathematical Programming 14(1), 265--294 (1978)
1602.07120.extracted_bib
{SabatoSaSr13 Sabato, S., Sarwate, A.D., Srebro, N.: Auditing: Active learning with outcome-dependent query costs. In: Advances in Neural Information Processing Systems 26 {(NIPS) (2013)
1602.07120.extracted_bib
{SabatoSaSr15 Sabato, S., Sarwate, A.D., Srebro, N.: Auditing: Active learning with outcome-dependent query costs. arxiv preprint ArXiv:1306.2347v4 (2015)
1602.07120.extracted_bib
{SaettlerLaCi14 Saettler, A., Laber, E., Cicalese, F.: Trading off worst and expected cost in decision tree problems and a value dependent model. arXiv preprint arXiv:1406.3655 (2014)
1602.07120.extracted_bib
{SaettlerLaCi15 Saettler, A., Laber, E., Cicalese, F.: Approximating decision trees with value dependent testing costs. Information Processing Letters 115(6–8), 594 -- 599 (2015)
1602.07120.extracted_bib
{Wolsey82 Wolsey, L.: An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica 2(4), 385--393 (1982)