text:
\section{Introduction}
\label{sec:intro}
How can you best learn a classifier given a label budget?

Active learning approaches are known to yield exponential improvements
over supervised learning under strong assumptions~\citep{CohnAL94}.
Under much weaker assumptions, streaming-based agnostic active
learning~\citep{balcan2006agnostic,BeygelDL09,BeygelHLZ10,DasguptaHM07,zhang2014beyond}
is particularly appealing since it is known to work for \emph{any}
classifier representation and \emph{any} label noise distribution with
an i.i.d.~data source.\footnote{See the monograph
  of~\citet{Hanneke2014} for an overview of the existing literature,
  including alternative settings where additional assumptions are
  placed on the data source (e.g., \emph{separability}) as is common
  in other
  works~\citep{dasgupta2005coarse,balcan2007margin,balcan2013active}.%
} Here, a learning algorithm decides for each unlabeled example in
sequence whether or not to request a label, never revisiting this
decision.  Restated then: What is the best possible active learning
algorithm which works for \emph{any} classifier representation,
\emph{any} label noise distribution, and is computationally tractable?

Computational tractability is a critical concern, because most known
algorithms for this
setting~\citep[e.g.,][]{balcan2006agnostic,koltchinskii2010rademacher,zhang2014beyond}
require explicit enumeration of classifiers, implying
exponentially-worse computational complexity compared to typical
supervised learning algorithms.  Active learning algorithms based on
empirical risk minimization (ERM)
oracles~\citep{BeygelDL09,BeygelHLZ10,hsu2010algorithms} can overcome
this intractability by using passive classification algorithms as the
oracle to achieve a computationally acceptable solution.

Achieving generality, robustness, and acceptable computation has a
cost. For the above
methods~\citep{BeygelDL09,BeygelHLZ10,hsu2010algorithms}, a label is
requested on nearly \emph{every} unlabeled example where two
empirically good classifiers disagree.  This results in a poor label
complexity, well short of information-theoretic
limits~\citep{Castro2008} even for general robust
solutions~\citep{zhang2014beyond}.  Until now.

In Section~\ref{sec:algorithm}, we design a new algorithm \textsc{Active Cover}\xspace
(\textsc{AC}\xspace) for constructing query probability functions that minimize the
probability of querying inside the \emph{disagreement region}---the
set of points where good classifiers disagree---and never query
otherwise.  This requires a new algorithm that maintains a
parsimonious cover of the set of empirically good classifiers.  The
cover is a result of solving an optimization problem (in
Section~\ref{sec:optimization}) specifying the properties of a
desirable query probability function.  The cover size provides a
practical knob between computation and label complexity, as
demonstrated by the complexity analysis we present in
Section~\ref{sec:optimization}.

In Section~\ref{sec:results}, we provide our main results which
demonstrate that \textsc{AC}\xspace effectively maintains a set of good classifiers,
achieves good generalization error, and has a label complexity bound
tighter than previous approaches. The label complexity bound depends
on the disagreement coefficient~\citep{Hanneke09}, which does not
completely capture the advantage of the algorithm. In
Section~\ref{sec:example}, we provide an example of a hard active
learning problem where \textsc{AC}\xspace is substantially superior to previous
tractable approaches. Together, these results show that \textsc{AC}\xspace is better
and sometimes substantially better in theory. The key aspects in the
proof of our generalization results are presented in
Section~\ref{proofs-regret}, with more technical details and label
complexity analysis presented in the appendix.

\emph{Do agnostic active learning algorithms work in practice?}  No
previous works have addressed this question empirically. Doing so is
important because analysis cannot reveal the degree to which existing
classification algorithms effectively provide an ERM oracle.  We
conduct an extensive study in Section~\ref{sec:experiments} by
simulating the interaction of the active learning algorithm with a
streaming supervised dataset. Results on a wide array of datasets
show that agnostic active learning typically outperforms passive learning,
and the magnitude of improvement depends on how carefully the active learning hyper-parameters
are chosen.

\section{Preliminaries}

Let $\H \subseteq \{\pm1\}^{\dataspace}$ be a set of binary
classifiers, which we assume is finite for simplicity.\footnote{%
  The assumption that $\H$ is finite can be relaxed to VC-classes
  using standard arguments.%
}
Let $\ensuremath{\mathbb{E}}_X[\cdot]$ denote expectation with respect to $X \sim \distx$,
the marginal of $\dist$ over $\dataspace$.
The \emph{expected error} of a classifier $h \in \H$ is \mbox{$\ensuremath{\mathrm{err}}(h) :=
  \Pr_{(X,Y) \sim \dist}(h(X) \neq Y)$}, and the error minimizer is
denoted by $h^* := \argmin_{h \in \H} \ensuremath{\mathrm{err}}(h)$.
The \emph{(importance weighted) empirical error} of $h \in \H$ on a
multiset $S$ of importance weighted and labeled examples drawn from
$\dataspace \times \{\pm1\} \times \bbR_+$ is \mbox{$\ensuremath{\mathrm{err}}(h,S) := \sum_{(x,y,w) \in S} w \cdot
\ind{h(x) \neq y} / |S|$}.
The \emph{disagreement region} for a subset of classifiers $A \subseteq
\H$ is
  $\ensuremath{\mathrm{DIS}}(A)
  :=
  \braces{
    x \in \dataspace \mid
    \exists h,h' \in A \ \text{such that} \ h(x) \neq h'(x)
  }
  $.
The \emph{regret} of a classifier $h \in \H$ relative to another $h'
\in \H$ is $\ensuremath{\mathrm{reg}}(h,h') := \ensuremath{\mathrm{err}}(h) - \ensuremath{\mathrm{err}}(h')$, and the analogous
empirical regret on $S$ is $\ensuremath{\mathrm{reg}}(h,h',S) := \ensuremath{\mathrm{err}}(h,S) - \ensuremath{\mathrm{err}}(h',S)$.
When the second classifier $h'$ in (empirical) regret is omitted, it
is taken to be the (empirical) error minimizer in $\H$.

A streaming-based active learner receives i.i.d.~labeled examples
$(X_1,Y_1), (X_2,Y_2), \dotsc$ from $\dist$ one at a time; each label
$Y_i$ is hidden unless the learner decides on the spot to query it.
The goal is to produce a classifier $h \in \H$ with low error
$\ensuremath{\mathrm{err}}(h)$, while querying as few labels as possible.

In the IWAL framework~\citep{BeygelDL09}, a decision whether or not to
query a label is made \emph{randomly}: the learner picks a probability
$p \in [0,1]$, and queries the label with that probability. Whenever
$p>0$, an unbiased error estimate can be produced using inverse
probability weighting~\citep{horvitz1952generalization}.
Specifically, for any classifier $h$, an unbiased estimator $E$ of
$\ensuremath{\mathrm{err}}(h)$ based on $(X,Y) \sim \dist$ and $p$ is as follows: if $Y$ is
queried, then $E = \ind{h(X) \neq Y} / p$; else, $E = 0$.  It is easy
to check that $\ensuremath{\mathbb{E}}(E) = \ensuremath{\mathrm{err}}(h)$.
Thus, when the label is queried, we produce the importance weighted
labeled example $(X,Y,1/p)$.\footnote{%
  If the label is not queried, we produce an ignored example of weight
  zero; its only purpose is to maintain the correct count of querying
  opportunities.
  This ensures that $1/|S|$ is the correct normalization in
  $\ensuremath{\mathrm{err}}(h,S)$.%
  \label{footnote:noquery}%
}

\section{Algorithm}
\label{sec:algorithm}

\begin{algorithm}[t!]
  \caption{\textsc{Active Cover}\xspace (\textsc{AC}\xspace)}
  \label{alg:main}
  \begin{algorithmic}[1]
    \renewcommand{\algorithmicrequire}{\textbf{input:}}
    \REQUIRE Constants $c_1, c_2, c_3$, confidence $\delta$, error
    radius $\gamma$, parameters $\alpha, \beta, \ensuremath{\xi}$ for
    $(\optprob)$, epoch schedule $0 = \epend[0] < 3 = \epend[1] <
    \epend[2] < \epend[3] < \ldots < \epend[\ensuremath{M}]$ satisfying
    $\epend[\ensuremath{m}+1] \leq 2\epend[\ensuremath{m}]$ for $\ensuremath{m}\geq1$.
    \renewcommand{\algorithmicrequire}{\textbf{initialize:}}
    \REQUIRE epoch $m = 0$, $\tilde{Z}_0 := \emptyset$, $\Delta_0 := c_1
    \sqrt{\epsilon_1} + c_2 \epsilon_1 \log 3$, where
    \begin{equation*}
      \epsilon_\ensuremath{m} \;:=\; \frac{32(\log(|\mathcal{H}|/\delta) + \log \epend)}{\epend}.
    \end{equation*}
    \FOR{$i = 4,\ldots,n,$} \IF{$i = \epend+1$} \STATE Set
    $\ensuremath{\tilde{Z}}_\ensuremath{m} = \ensuremath{\tilde{Z}}_{\ensuremath{m}-1} \cup S$, and $S = \emptyset$.
    \STATE Let
    \begin{eqnarray}
      h_{\ensuremath{m}+1} &:=& \arg\min_{h \in \mathcal{H}} \; \mbox{err}(h,
      \tilde{Z}_{\ensuremath{m}}),\label{alg:main:erm_update}\\
      \Delta_{\ensuremath{m}} &:=& c_1 \sqrt{\epsilon_{\ensuremath{m}}
        \ensuremath{\mathrm{err}}(h_{\ensuremath{m}+1},\tilde{Z}_{\ensuremath{m}})} + c_2 \epsilon_{\ensuremath{m}} \log
      \epend, \label{eq:Delta}\\
      A_{\ensuremath{m}+1} &:=& \{h \mid \mbox{err}(h,\tilde{Z}_{\ensuremath{m}})  -
      \mbox{err}(h_{\ensuremath{m}+1},\tilde{Z}_{\ensuremath{m}}) \leq \gamma
      \Delta_{\ensuremath{m}}\}. \label{eq:A}
    \end{eqnarray}
    \STATE Compute the solution $P_{\ensuremath{m}+1}(\cdot)$ to the
    optimization  \label{alg:main:P_update}
    problem \eqref{eq:queryp}.
    \STATE $\ensuremath{m} := \ensuremath{m} + 1$.
    \ENDIF
    \STATE Receive unlabeled data point $X_i$.
    \IF{$X_i \in D_{\ensuremath{m}} := \mbox{DIS}(A_{\ensuremath{m}}$),} \label{alg:main:query}
      \STATE Draw $Q_i \sim \mbox{Bernoulli}(P_\ensuremath{m}(X_i))$.
      \STATE Update the set of examples:\footnotemark
      \begin{eqnarray*}
        S :=&
        \begin{cases}
          S \cup \{(X_i,Y_i, 1/P_\ensuremath{m}(X_i))\}, & Q_i = 1\\
          S \cup \{X_i, 1, 0\},  & \mbox{otherwise}.
        \end{cases}
      \end{eqnarray*}
      \ELSE
      \STATE
      \centerline{$S \;\;:=\;\; S \cup \{(X_i, h_\ensuremath{m}(X_i),1)\}.$}
      \ENDIF \label{alg:main:query_end}
      \ENDFOR
      \STATE $h_{\ensuremath{M}+1} := \arg \min_{h \in \mathcal{H}} \; \mbox{err}(h, \tilde{Z}_{\ensuremath{M}})$.
  \end{algorithmic}
\end{algorithm}
\footnotetext{%
  See Footnote~\ref{footnote:noquery}. Adding an example of importance
  weight zero simply increments $|S|$ without updating other state of
  the algorithm, hence the label used does not matter
}

Our new algorithm, shown in Algorithm~\ref{alg:main}, breaks the
example stream into epochs.
The algorithm admits any epoch schedule so
long as the epoch lengths satisfy $\epend[\ensuremath{m}-1] \leq 2\epend$. For
technical reasons, we always query the first 3 labels to kick-start
the algorithm.
At the start of epoch~$\ensuremath{m}$, \textsc{AC}\xspace\ computes a
\emph{query probability function} $P_\ensuremath{m} \colon \cX \to [0,1]$
which will be used for sampling the data points to query during the
epoch. This is done by maintaining a few objects of interest during
each epoch:

\begin{enumerate}
\item In step~\ref{alg:main:erm_update}, we compute the best
  classifier on the sample $\ensuremath{\tilde{Z}}_\ensuremath{m}$ that we have collected so
  far. Note that the sample consists of the queried, true labels on some
  examples, while predicted labels for the others.
\item A radius $\Delta_\ensuremath{m}$
is computed in step~\ref{eq:Delta}
based on the desired level of concentration
we want the various empirical quantities to satisfy.

\item The set $A_{\ensuremath{m}+1}$ in step~\ref{eq:A} consists of all the
  hypotheses which are good according to our sample $\ensuremath{\tilde{Z}}_\ensuremath{m}$,
  with the notion of good being measured as empirical regret being at
  most $\Delta_\ensuremath{m}$.
\end{enumerate}
Within the epoch, $P_\ensuremath{m}$ determines the probability of querying an
example in the disagreement region for this set $A_{\ensuremath{m}}$ of ``good''
classifiers; examples outside this region are not queried but given
labels predicted by $h_\ensuremath{m}$. Consequently, the sample is not
unbiased unlike some of the predecessors of our work. The various
constants in Algorithm~\ref{alg:main} must satisfy:

\begin{align}
  \alpha &\geq 1, ~~\ensuremath{\eta} \geq 864,~~ \ensuremath{\xi} \leq \frac{1}{8
    n\epsilon_{\ensuremath{M}}\log n}, ~~ \beta^2 \leq \frac{\eta}{864 \gamma
    n \epsilon_{\ensuremath{M}} \log n}, ~~ \gamma \geq
  \ensuremath{\eta}/4,\nonumber\\
  &\qquad c_1 \geq 2 \alpha \sqrt{6}, ~~ c_2
  \geq \ensuremath{\eta} c_1^2 / 4, ~~ c_3 \geq 1.
  \label{eqn:constants}
\end{align}

\paragraph{Epoch Schedules:} The algorithm as stated takes an arbitrary
epoch schedule subject to \mbox{$\epend[\ensuremath{m}] < \epend[\ensuremath{m}+1]
  \leq 2\epend[\ensuremath{m}]$}. Two natural extremes are unit-length epochs,
$\epend[\ensuremath{m}] = \ensuremath{m}$, and doubling epochs, $\epend[\ensuremath{m}+1] =
2\epend[\ensuremath{m}]$. The main difference comes in the number of times
$(\optprob)$ is solved, which is a substantial computational
consideration. Unless otherwise stated, we assume the doubling epoch
schedule so that the query probability and ERM classifier are
recomputed only $\ensuremath{\mathcal{O}}(\log n)$ times.

\paragraph{Optimization problem (\optprob) to obtain $P_\ensuremath{m}$:}
\textsc{AC}\xspace\ computes $P_\ensuremath{m}$ as the solution to the optimization problem
(\optprob). In essence, the problem encodes the properties of a query
probability function that are essential to ensure good generalization,
while maintaining a low label complexity. As we will discuss later,
some of the previous works can be seen as specific ways of
constructing feasible solutions to this optimization problem. The
objective function of $(\optprob)$ encourages small query
probabilities in order to minimize the label complexity. It might
appear odd that we do not use the more obvious choice for objective
which would be $\ensuremath{\mathbb{E}}_X[P(X)]$, however our choice simultaneously
encourages low query probabilities and also provides a barrier for the
constraint $P(X) \leq 1$--an important algorithmic aspect as we will
discuss in Section~\ref{sec:optimization}.

The constraints~\eqref{eq:queryp} in (\optprob) bound the variance in
our importance-weighted regret estimates for every $h \in \H$. This is
key to ensuring good generalization as we will later use Bernstein-style
bounds which rely on our random variables having a small variance. Let
us examine these constraints in more detail. The LHS of the
constraints measures the variance in our empirical regret estimates
for $h$, measured only on the examples in the disagreement region
$D_\ensuremath{m}$. This is because the importance weights in the form of
$1/P_\ensuremath{m}(X)$ are only applied to these examples; outside this
region we use the predicted labels with an importance weight of 1. The
RHS of the constraint consists of three terms. The first term ensures
the feasibility of the problem, as $P(X) \equiv 1/(2\alpha^2)$ for $X \in
D_\ensuremath{m}$ will always satisfy the constraints. The second empirical
regret term makes the constraints easy to satisfy for bad
hypotheses--this is crucial to rule out large label complexities in
case there are bad hypotheses that disagree very often with
$h_\ensuremath{m}$. A benefit of this is easily seen when $-h_\ensuremath{m} \in \H$,
which might have a terrible regret, but would force a near-constant query
probability on the disagreement region if $\beta = 0$. Finally, the
third term will be on the same order as the second one for hypotheses
in $A_\ensuremath{m}$, and is only included to capture the allowed level of
slack in our constraints which will be exploited for the efficient
implementation in Section~\ref{sec:optimization}.

Of course, variance alone is not adequate to ensure concentration, and
we also require the random variables of interest to be appropriately
bounded. This is ensured through the
constraints~\eqref{eq:minbndcons}, which impose a minimum query
probability on the disagreement region. Outside the disagreement
region, we use the predicted label with an importance weight of 1, so that our estimates
will always be bounded (albeit biased) in this region. Note that this
optimization problem is written with respect to the marginal
distribution of the data points $\dist_X$, meaning that we might have
infinite number of the latter constraints. In Section~\ref{sec:optimization},
we describe how to solve this optimization problem efficiently, and
using access to only unlabeled examples drawn from $\dist_X$.

Finally we verify that the choices for $P_\ensuremath{m}$ according to some of
the previous methods are indeed feasible in (\optprob). This is most
easily seen for Oracular CAL~\citep{hsu2010algorithms} which queries
with probability 1 if $X \in D_\ensuremath{m}$ and 0 otherwise. Since $\alpha
\geq 1$~\eqref{eqn:constants} in the variance
constraints~\eqref{eq:queryp}, the choice $P(X) \equiv 1$ for $X \in
D_\ensuremath{m}$ is feasible for (\optprob), and consequently Oracular CAL
always queries more often than the optimal distribution $P_\ensuremath{m}$ at
each epoch. A similar argument can also be made for the IWAL
method~\citep{BeygelHLZ10}, which also queries in the disagreement
region with probability 1, and hence suffers from the same
sub-optimality compared to our choice.

\begin{figure}[t]
\begin{center} \fbox{\begin{minipage}{0.95\columnwidth}
\centerline{%
  {\bf Optimization Problem} (\optprob) to compute $P_\ensuremath{m}$%
}

\begin{eqnarray}
  \min_{P} &&  \ensuremath{\mathbb{E}}_X \left[ \frac{1}
                                         {1 - P(X)}
                           \right]
\nonumber \\
  \mbox{s.t.} && \forall h \in \H\;\; \ensuremath{\mathbb{E}}_X \left[
    \frac{\mathds{1}(h(x) \neq h_\ensuremath{m}(x) \wedge x
  \in D_\ensuremath{m})}{P(X)}\right] \leq b_\ensuremath{m}(h),
\label{eq:queryp} \\
  && \forall x \in \dataspace \;\; 0 \leq P(x) \leq 1, \quad \mbox{and} \quad \forall x \in D_\ensuremath{m} \;\; P(x) \geq P_{\min,\ensuremath{m}}
\label{eq:minbndcons}
\end{eqnarray}

\begin{align}
  \mbox{where}\quad \disind{h}( X) &= \mathds{1}(h(x) \ne h_{\ensuremath{m}}(x)
  \wedge x \in D_\ensuremath{m}),\nonumber\\
  b_\ensuremath{m}(h) &= 2 \alpha^2  \ensuremath{\mathbb{E}}_X[\disind{h}( X)] + 2
  \beta^2 \gamma \ensuremath{\mathrm{reg}}(h,h_\ensuremath{m},\tilde{Z}_{\ensuremath{m}-1})\epend[\ensuremath{m}-1]
  \Delta_{\ensuremath{m}-1} + \ensuremath{\xi} \epend[\ensuremath{m}-1]\Delta_{\ensuremath{m}-1}^2
  ,~~\mbox{and}\nonumber \\
  P_{\min,\ensuremath{m}} &=
  \min\left(\frac{c_3}{\sqrt{\frac{\epend[\ensuremath{m}-1]\ensuremath{\mathrm{err}}(h_{\ensuremath{m}},\tilde{Z}_{\ensuremath{m}-1})}{n\epsilon_\ensuremath{M}}}
    + \log\epend[\ensuremath{m}-1]},\frac{1}{2}\right).
\label{eq:pmin}
\end{align}
\end{minipage}}
\end{center}
\end{figure}

\section{Generalization and Label Complexity}
\label{sec:results}
We now present guarantees on the generalization error and label
complexity of Algorithm~\ref{alg:main} assuming a solver for
$(\optprob)$, which we provide in the next section.

\subsection{Generalization guarantees}
\label{sec:regret-result}

Our first theorem provides a bound on generalization error.  Define
\begin{align*}
  \erravg{\ensuremath{m}}(h) &:= \frac{1}{\epend}
  \sum_{j=1}^\ensuremath{m}(\epend[j] - \epend[j-1])
  \ensuremath{\mathbb{E}}_{(X,Y)\sim\dist}[\mathds{1}(h(X) \neq Y \wedge X \in
    D_j)], \\
  \Delta^*_0 &:= \Delta_0 ~~\mbox{and}~~ \Delta_{\ensuremath{m}}^* :=
  c_1 \sqrt{\epsilon_\ensuremath{m} \erravg{\ensuremath{m}}(h^*) } + c_2
  \epsilon_\ensuremath{m} \log \epend ~~\mbox{for}~~ \ensuremath{m} \geq 1.
\end{align*}
Essentially $\Delta_{\ensuremath{m}}^*$ is a population counterpart of the
quantity $\Delta_{\ensuremath{m}}$ used in Algorithm~\ref{alg:main}, and
crucially relies on $\erravg{\ensuremath{m}}(h^*)$, the true error of $h^*$
restricted to the disagreement region instead of the empirical error
of the ERM at epoch $\ensuremath{m}$. This quantity captures the inherent
noisiness of the problem, and modulates the transition between
$\ensuremath{\mathcal{O}}(1/\sqrt{n})$ to $\ensuremath{\mathcal{O}}(1/n)$ type error bounds as we see
next.
\begin{theorem}
  Pick any $0 < \delta < 1/e$ such that $|\H|/\delta >
  \sqrt{192}$. Then recalling that $h^* = \argmin_{h \in \H} \ensuremath{\mathrm{err}}(h)$,
  we have for all epochs $\ensuremath{m} = 1,2,\ldots, \ensuremath{M}$, with
  probability at least $1 - \delta$
  \begin{align}
    \ensuremath{\mathrm{reg}}(h,h^*) & \ \leq\ 16 \gamma \Delta_\ensuremath{m}^* \quad \mbox{for all}~ h
    \in A_{\ensuremath{m}+1}, \quad \mbox{and}\label{eqn:regret}\\
    \ensuremath{\mathrm{reg}}(h^*, h_{\ensuremath{m}+1}, \ensuremath{\tilde{Z}}_\ensuremath{m}) & \ \leq\
    \ensuremath{\eta} \Delta_\ensuremath{m} / 4 . \label{eq:h_best}
  \end{align}
  \label{thm:regret}
\end{theorem}
The theorem is proved in Section~\ref{sec:proof-thm-regret}, using the
overall analysis framework described in Section~\ref{proofs-regret}.

Since we use $\gamma \geq \ensuremath{\eta}/4$, the bound \eqref{eq:h_best}
implies that $h^* \in A_\ensuremath{m}$ for all epochs $\ensuremath{m}$. This also
maintains that all the predicted labels used by our algorithm are
identical to those of $h^*$, since no disagreement amongst classifiers
in $A_\ensuremath{m}$ was observed on those examples.
This observation will be
critical to our proofs, where we will exploit the fact that using
labels predicted by $h^*$ instead of observed labels on certain
examples only introduces a bias in favor of $h^*$, thereby ensuring
that we never mistakenly drop the optimal classifier from our version
space $A_\ensuremath{m}$.

The bound~\eqref{eqn:regret} shows that every hypothesis in
$A_{\ensuremath{m}+1}$ has a small regret to $h^*$.
Since the ERM classifier
$h_{\ensuremath{m}+1}$ is always in $A_{\ensuremath{m}+1}$, this yields our main
generalization error bound on the classifier $h_{\epend+1}$ output by
Algorithm~\ref{alg:main}. Additionally, it also clarifies the
definition of the sets $A_\ensuremath{m}$ as the set of good classifiers: these
are classifiers which have small population regret relative to $h^*$
indeed. In the worst case, if $\erravg{\ensuremath{m}}(h^*)$ is a constant,
then the overall regret bound is $\ensuremath{\mathcal{O}}(1/\sqrt{n})$. The actual
rates implied by the theorem, however depend on the properties of the
distribution and below we illustrate this with two corollaries. We
start with a simple specialization to the realizable setting.

\begin{corollary}[Realizable case]
  Under the conditions of Theorem~\ref{thm:regret}, suppose further
  that $\ensuremath{\mathrm{err}}(h^*) = 0$. Then $\Delta_\ensuremath{m} = \Delta^*_\ensuremath{m} = c_2
  \epend \log\epend$ and hence $\ensuremath{\mathrm{reg}}(h, h^*) \leq
  16c_2\epend\log\epend$ for all hypotheses $h \in A_{\ensuremath{m}+1}$.
  \label{cor:regret-realizable}
\end{corollary}
In words, the corollary demonstrates a $\ensuremath{\tilde{\mathcal{O}}}(1/n)$ rate after seeing
$n$ unlabeled examples in the realizable setting. Of course the use of
$\erravg{\ensuremath{m}}(h^*)$ in defining $\Delta^*_\ensuremath{m}$ allows us to
retain the fast rates even when $h^*$ makes some errors but they do
not fall in the disagreement region of good classifiers. One intuitive
condition that controls the errors within the disagreement region is
the low-noise condition of~\citet{Tsybakov2004}, which
asserts that there exist constants $\ensuremath{\zeta} > 0$ and $0 < \ensuremath{\omega}
\leq 1$ such that

\begin{equation}
  \ensuremath{\mathrm{Pr}}(h(X) \ne h^*(X)) \leq \ensuremath{\zeta} \cdot (\ensuremath{\mathrm{err}}(h) -
  \ensuremath{\mathrm{err}}(h^*))^\ensuremath{\omega}, \quad \forall h \in \H~~\mbox{such
    that}~~\ensuremath{\mathrm{err}}(h) - \ensuremath{\mathrm{err}}(h^*) \leq \ensuremath{\varepsilon_0}.
  \label{eqn:tsybakov}
\end{equation}
Under this assumption, the extreme $\ensuremath{\omega} = 0$ corresponds to the
worst-case setting while $\ensuremath{\omega} = 1$ corresponds to $h^*$ having a
zero error on disagreement set of the classifiers with regret at most
$\ensuremath{\varepsilon_0}$. Under this assumption, we get the following corollary of
Theorem~\ref{thm:regret}.

\begin{corollary}[Tsybakov noise]
  Under conditions of Theorem~\ref{thm:regret}, suppose further that
  Tsybakov's low-noise condition~\eqref{eqn:tsybakov} is satisfied
  with some parameters $\ensuremath{\zeta}, \ensuremath{\omega}$, and $\ensuremath{\varepsilon_0} =
  1$. Then after $\ensuremath{m}$ epochs, we have \mbox{$\ensuremath{\mathrm{reg}}(h, h^*) =
    \ensuremath{\tilde{\mathcal{O}}}\left(\epend^{-\frac{1}{2-\ensuremath{\omega}}}
    \log(|\H|/\delta)\right)$.}
  \label{cor:regret-tsybakov}
\end{corollary}
The proof of this result is deferred to Appendix~\ref{sec:tsybakov}.
It is worth noting that the rates obtained here are known to be
unimprovable for even passive learning under the Tsybakov noise
condition~\citep{Castro2008}.\footnote{$\ensuremath{\omega}$ in our statement of
  the low-noise condition~\eqref{eqn:tsybakov} corresponds to
  $1/\kappa$ in the results of~\citet{Castro2008}.} Consequently,
there is no loss of statistical efficiency in using our active
learning approach. The result is easily extended for other values of
$\ensuremath{\varepsilon_0}$ by using the worst-case bound until the first epoch
$\ensuremath{m}_0$ when $16\gamma\Delta^*_{\ensuremath{m}_0}$ drops below $\ensuremath{\varepsilon_0}$
and then apply our analysis above from $\ensuremath{m}_0$ onwards. We leave
this development to the reader.

\subsection{Label complexity}
\label{sec:label-result}

Generalization alone does not convey the entire quality of an active
learning algorithm, since a trivial algorithm queries always with
probability 1, thereby matching the generalization guarantees of
passive learning. In this section, we show that our algorithm can
achieve the aforementioned generalization guarantees, despite having a
small label complexity in favorable situations. We begin with a
worst-case result in the agnostic setting, and then describe a
specific example which demonstrates some key differences of our
approach from its predecessors.

\subsubsection{Disagreement-based label complexity bounds}

In order to quantify the extent of gains over passive learning, we
measure the hardness of our problem using the disagreement
coefficient~\citep{Hanneke2014}, which is defined as

\begin{equation}
\theta = \theta(h^*) := \sup_{r > 0} \; \frac{\distx\braces{ x \mid
    \exists h \in \H \,\text{s.t.}\, h^*(x) \neq h(x) ,\,
    \distx\braces{ x' \mid h(x') \neq h^*(x') } \leq r }}{r}.
\label{eqn:dis-coeff}
\end{equation}
Intuitively, given a set of classifiers $\H$ and a data distribution
$\dist$, an active learning problem is easy if good classifiers
disagree on only a small fraction of the examples, so that the active
learning algorithm can increasingly restrict attention only to this
set. With this definition, we have the following result for the label
complexity of Algorithm~\ref{alg:main}.

\begin{theorem}
  Under conditions of Theorem~\ref{thm:regret}, with probability at
  least $1-\delta$, the number
  of label queries made by Algorithm~\ref{alg:main} after $n$ examples
  over $\ensuremath{M}$ epochs is at most
  \begin{equation*}
    4\theta \erravg{\ensuremath{M}}(h^*) n + \theta \cdot \ensuremath{\tilde{\mathcal{O}}}
    (\sqrt{n\overline{\ensuremath{\mathrm{err}}}_{\ensuremath{M}}(h^*) \log(|\mathcal{H}|/\delta)}
    + \log(|\mathcal{H}|/\delta)) + 4 \log(8(\log n) / \delta).
   \end{equation*}
\label{thm:label}
\end{theorem}
The proof is in Appendix \ref{appendix:proof_label_complexity}.
The dominant first term of the label complexity bound is linear in the
number of unlabeled examples, but can be quite small if $\theta$ is
small, or if $\erravg{\ensuremath{M}}(h^*) \approx 0$---it is indeed 0 in the
realizable setting. We illustrate this aspect of the theorem with a
corollary for the realizable setting.

\begin{corollary}[Realizable case]
  Under the conditions of Theorem~\ref{thm:label}, suppose further
  that $\ensuremath{\mathrm{err}}(h^*) = 0$. Then the expected number of label queries made
  by Algorithm~\ref{alg:main} is at most $\theta
  \ensuremath{\tilde{\mathcal{O}}}(\log(|\H|/\delta))$.
  \label{cor:label-realizable}
\end{corollary}
In words, we attain a logarithmic label complexity in the realizable
setting, so long as the disagreement coefficient is bounded. We
contrast this with the label complexity of IWAL~\citep{BeygelHLZ10},
which grows as $\theta\sqrt{n}$ independent of $\ensuremath{\mathrm{err}}(h^*)$. This leads
to an exponential difference in the label complexities of the two
methods in low-noise problems. A much closer comparison is with
respect to the Oracular CAL algorithm~\citep{hsu2010algorithms}, which
does have a dependence on $\sqrt{n\ensuremath{\mathrm{err}}(h^*)}$ in the second term, but
has a worse dependence on the disagreement coefficient $\theta$.

Just like Corollary~\ref{cor:regret-tsybakov}, we can also obtain
improved bounds on label complexity under the Tsybakov noise
condition.

\begin{corollary}[Tsybakov noise]
  Under conditions of Theorem~\ref{thm:label}, suppose further that
  the disagreement coefficient $\theta$ is bounded and Tsybakov's
  low-noise condition~\eqref{eqn:tsybakov} is satisfied with some
  parameters $\ensuremath{\zeta},\ensuremath{\omega}$, and $\ensuremath{\varepsilon_0} = 1$. Then after
  $\ensuremath{m}$ epochs, the expected number of label queries made by
  Algorithm~\ref{alg:main} is at most $ \ensuremath{\tilde{\mathcal{O}}}\left(\epend^{\frac{2(1 -
      \ensuremath{\omega})}{2-\ensuremath{\omega}}} \log(|\H|/\delta)\right)$.
  \label{cor:label-tsybakov}
\end{corollary}
The proof of this result is deferred to Appendix~\ref{sec:tsybakov}.
The label complexity obtained above is indeed optimal in terms of the
dependence on $n$, the number of unlabeled examples, matching known
information-theoretic rates of~\citet{Castro2008} when the
disagreement coefficient $\theta$ is bounded. This can be seen since
the regret from Corollary~\ref{cor:regret-tsybakov} falls as a
function of the number of queries at a rate of
$\ensuremath{\tilde{\mathcal{O}}}(q_\ensuremath{m}^{-\frac{1}{2(1-\ensuremath{\omega})}} \log(|\H|/\delta))$ after
$\ensuremath{m}$ epochs, where $q_\ensuremath{m}$ is the number of label queries. This
is indeed optimal according to the lower bounds of~\citet{Castro2008},
after recalling that $\ensuremath{\omega} = 1/\kappa$ in their results. Once
again, the corollary highlights our improvements on top of IWAL, which
does not attain this optimal label complexity.

These results, while strong, still do not completely capture the
performance of our method. Indeed the proofs of these results are
entirely based on the fact that we do not query outside the
disagreement region, a property shared by the previous Oracular CAL
algorithm~\citep{hsu2010algorithms}. Indeed we only improve upon that
result as we use more refined error bounds to define the disagreement
region. However, such analysis completely ignores the fact that we
construct a rather non-trivial query probability function on the
disagreement region, as opposed to using any constant probability of
querying over this entire region. This gives our algorithm the ability
to query much more rarely even over the disagreement region, if the
queries do not provide much information regarding the optimal
hypothesis $h^*$. The next section illustrates an example where this
gain can be quantified.

\subsubsection{Improved label complexity for a hard problem instance}
\label{sec:example}

We now present an example where the label complexity of
Algorithm~\ref{alg:main} is significantly smaller than both IWAL and
Oracular CAL by virtue of rarely querying in the disagreement
region. The example considers a distribution and a classifier space
with the following structure: (i) for most examples a single good
classifier predicts differently from the remaining classifiers (ii) on
a few examples half the classifiers predict one way and half the
other.  In the first case, little advantage is gained from a label
because it provides evidence against only a single classifier.
\textsc{Active Cover}\xspace queries over the disagreement region with a probability close
to $P_{\min}$ in case (i) and probability $1$ in case (ii), while
others query with probability $\Omega(1)$ everywhere implying
$\ensuremath{\mathcal{O}}(\sqrt{n})$ times more queries.

Concretely, we consider the following binary classification problem.
Let $\mathcal{H}$ denote the finite classifier space (defined later),
and distinguish some $h^* \in \mathcal{H}$.  Let $U\{-1,1\}$ denote
the uniform distribution on $\{-1,1\}$.  The data distribution
$\mathcal{D}(\mathcal{X},\mathcal{Y})$ and the classifiers are defined
jointly:
\begin{itemize}
\item With probability $\epsilon$,
\begin{eqnarray*}
&&y = h^*(x), \quad h(x) \sim U\{-1,1\}, \ \forall h \neq h^*.
\end{eqnarray*}
\item With probability $1-\epsilon$,
\begin{eqnarray*}
	&& y \sim U\{-1,1\}, \quad h^*(x) \sim U\{-1,1\}, \\
&& h_r(x) = -h^*(x) \mbox{ for some } h_r \mbox{ drawn uniformly at random from } \mathcal{H} \setminus h^*, \\
&& h(x) = h^*(x) \; \forall h \neq h^* \wedge h \neq h_r.
\end{eqnarray*}
\end{itemize}
Indeed, $h^*$ is the best classifier because $\mbox{err}(h^*) =
\epsilon \cdot 0 + (1 - \epsilon) (1/2) = (1 - \epsilon) / 2$, while
$\mbox{err}(h) = 1/2 \; \forall h \neq h^*$. This problem is hard
because only a small fraction of examples contain information about
$h^*$.  Ideally we want to focus label queries on those informative
examples while skipping the uninformative ones. However, algorithms
like IWAL, or more generally, active learning algorithms that
determine label query probabilities based on error differences between
a pair of classifiers, query frequently on the uninformative
examples. Let $u(h,h') := \mathbbm{1}(h(x) \neq y) - \mathbbm{1}(h'(x)
\neq y)$ denote the error difference between two different classifiers
$h$ and $h'$. Let $C$ be a random variable such that $C=1$ for the
$\epsilon$ case and $C=0$ for the $1-\epsilon$ case. Then it is easy
to see that
\begin{eqnarray*}
\ensuremath{\mathbb{E}}[u(h,h') \mid C = 1] &=&
\begin{cases}
	0, & h \neq h^*, h' \neq h^*,\\
	-1/2, & h =h^*, h' \neq h^*,\\
	1/2, & h \neq h^*, h' = h^*,
 \end{cases} \\
 \ensuremath{\mathbb{E}}[u(h,h') \mid C = 0] &=& 0, \; \forall h \neq h'.
\end{eqnarray*}
Therefore, IWAL queries all the time on uninformative examples ($C = 0$).

Now let us consider the label complexity of Algorithm~\ref{alg:main}
on this problem. Let us focus on the query probability inside the $1 -
\epsilon$ region, and fix it to some constant $p$. Let us also allow a
query probability of 1 on the $\epsilon$ region. Then the left hand
side in the constraint~(\ref{eq:queryp}) for any classifier $h$ is at
most $\epsilon + P(h(X) \ne h_m(X))/p \leq \epsilon + 2/(p(|\H|-1))$,
since $h$ and $h_m$ disagree only on those points in the $1-\epsilon$
region where one of them is picked as the disagreeing classifier $h_r$
in the random draw. On the other hand, the RHS of the constraints is
at least $\ensuremath{\xi} \epend[\ensuremath{m}-1]\Delta_{\ensuremath{m}-1}^2 \geq
\ensuremath{\xi} \ensuremath{\mathrm{err}}(h_m, \ensuremath{\tilde{Z}}_{m-1})$, which is at least $\ensuremath{\xi}/4$
as long as $\epsilon$ is small enough and $\epend[\ensuremath{m}]$ is large
enough for empirical error to be close to true error. Consequently,
assuming that $\epsilon \leq \ensuremath{\xi}/8$, we find that any $p \geq
16/(\ensuremath{\xi}(|\H| - 1))$ satisfies the constraints. Of course we
also have that $p \geq \pmin$, which is $\ensuremath{\mathcal{O}}(1/\sqrt{\epend})$ in
this case since $\erravg{m}(h^*)$ is a constant. Consequently, for
$|\H|$ large enough $p = \pmin$ is feasible and hence optimal for the
population $(\optprob)$. Since we find an approximately optimal
solution based on Theorem~\ref{thm:optprob-unlabeled}, the label
complexity at epoch $m$ is $\ensuremath{\mathcal{O}}(1/\sqrt{\epend})$. Summing things
up, it can then be checked easily that we make $\ensuremath{\mathcal{O}}(\sqrt{n})$
queries over $n$ examples, a factor of $\sqrt{n}$ smaller than
baselines such as IWAL and Oracular CAL on this example.

\section{Efficient implementation}
\label{sec:optimization}
In Algorithm \ref{alg:main},
the computation of $h_\ensuremath{m}$ is an ERM operation, which can be
performed efficiently whenever an efficient passive learner is
available.  However, several other hurdles remain.  Testing for $x \in
D_\ensuremath{m}$ in the algorithm, as well as finding a solution to
$(\optprob)$ are considerably more challenging. The epoch schedule
helps, but $(\optprob)$ is still solved $\ensuremath{\mathcal{O}}(\log n)$ times,
necessitating an extremely efficient solver.

Starting with the first issue, we follow~\citet{DasguptaHM07} who
cleverly observed that $x\in D_\ensuremath{m}$ can be efficiently determined
using a single call to an ERM oracle.  Specifically, to apply their
method, we use the oracle to find\footnote{We only have access to an
  \emph{unconstrained} oracle.  But that is adequate to solve with one
  constraint.  See Appendix F of~\citep{KLonline} for details.} $h' =
\arg\min \braces{ \ensuremath{\mathrm{err}}(h, \ensuremath{\tilde{Z}}_{\ensuremath{m}-1}) \mid h \in \H, h(x) \ne
  h_\ensuremath{m}(x) }$.  It can then be argued that $x \in D_\ensuremath{m} =
\ensuremath{\mathrm{DIS}}(A_\ensuremath{m})$ if and only if the easily-measured regret of $h'$
(that is, $\ensuremath{\mathrm{reg}}(h', h_\ensuremath{m}, \ensuremath{\tilde{Z}}_{\ensuremath{m}-1})$) is at most $\gamma
\Delta_{\ensuremath{m}-1}$.

Solving $(\optprob)$ efficiently is a much bigger challenge because,
as an optimization problem, it is enormous: There is one variable
$P(x)$ for every point $x \in \dataspace$, one
constraint~\eqref{eq:queryp} for each classifier $h$ and bound
constraints~\eqref{eq:minbndcons} on $P(x)$ for every $x$. This leads
to infinitely many variables and constraints, with an ERM oracle being
the only computational primitive available. Another difficulty is that
$(\optprob)$ is defined in terms of the true expectation with respect
to the example distribution $\distx$, which is unavailable.

In the following we first demonstrate how to efficiently solve
$(\optprob)$ assuming access to the true expectation $\ensuremath{\mathbb{E}}_X[\cdot]$,
and then discuss a relaxation that uses expectation over samples. For
the ease of exposition, we recall the shorthand $\disind{h}(x) =
\mathds{1}(h(x) \neq h_\ensuremath{m}(x) \wedge x \in D_\ensuremath{m})$ from earlier.

\subsection{Solving (\optprob) with the true expectation}
The main challenge here is that the optimization variable $P(x)$ is of
infinite dimension. We deal with this difficulty using Lagrange
duality, which leads to a dual representation of $P(x)$ in terms of a
set of classifiers found through successive calls to an ERM oracle. As
will become clear shortly, each of these classifiers corresponds to
the most violated variance constraint \eqref{eq:queryp} under some
intermediate query probability function. Thus at a high level, our
strategy is to expand the set of classifiers for representing $P(x)$
until the amount of constraint violation gets reduced to an acceptable
level.

We start by eliminating the bound constraints using barrier functions.
Notice that the objective $\ensuremath{\mathbb{E}}_X[1/(1-P(x))]$ is already a barrier at
$P(x) = 1$. To enforce the lower bound~\eqref{eq:minbndcons}, we
modify the objective to
\begin{equation} \label{eq:mod-obj}
  \ensuremath{\mathbb{E}}_X \left[ \frac{1}{1 -
      P(X)}\right] + \ensuremath{\mu}^2 \ensuremath{\mathbb{E}}_X\left[ \frac{\mathds{1}(X \in
    D_\ensuremath{m})}{P(X)}\right],
\end{equation}
where $\ensuremath{\mu}$ is a parameter chosen momentarily to ensure $P(x) \geq
\pmin$ for all $x \in D_\ensuremath{m}$.  Thus, the modified goal is to
minimize \eqref{eq:mod-obj} over non-negative $P$ subject only to
\eqref{eq:queryp}.

\begin{algorithm}[t]
  \caption{Coordinate ascent algorithm to solve $(\optprob)$}
  \label{alg:coord}
  \begin{algorithmic}[1]
    \renewcommand{\algorithmicrequire}{\textbf{input}}
    \REQUIRE Accuracy parameter $\varepsilon>0$.
    \textbf{initialize} $\boldsymbol{\lambda} \leftarrow \mathbf 0$.
    \LOOP
    \STATE Rescale:  $\boldsymbol{\lambda} \leftarrow s \cdot \boldsymbol{\lambda}$ where
                     $s = \arg \max_{s\in [0,1]} {\cal D}(s \cdot \boldsymbol{\lambda})$.
    \STATE Find $\displaystyle\bar{h} = \arg\max_{h \in \H}
      \ensuremath{\mathbb{E}}_X\left[\frac{\disind{h}(X)}{P_{\boldsymbol{\lambda}}(X)} \right] -
      b_\ensuremath{m}(h)$.
    \label{step:violated}

    \IF{$\ensuremath{\mathbb{E}}_X\left[\frac{\disind{\bar{h}}(X)}{P_{\boldsymbol{\lambda}}(X)} \right] -
      b_\ensuremath{m}(\bar{h}) \leq \varepsilon$}
    \RETURN $\boldsymbol{\lambda}$
    \ELSE
    \STATE Update $\lambda_{\bar{h}}$ as
    $\displaystyle
       \lambda_{\bar{h}} \leftarrow \lambda_{\bar{h}} +
       2\frac{\ensuremath{\mathbb{E}}_X[\disind{\bar{h}}(X)/P_{\boldsymbol{\lambda}}(X)] -
         b_\ensuremath{m}(\bar{h})}{\ensuremath{\mathbb{E}}_X[\disind{\bar{h}}(X)/q_{\boldsymbol{\lambda}}(X)^3]}
         $.
    \label{step:coord-update}
    \ENDIF
    \ENDLOOP
  \end{algorithmic}
\end{algorithm}
We solve the problem in the dual where we have a large but finite
number of optimization variables, and efficiently maximize the dual
using coordinate ascent with access to an ERM oracle over $\H$.  Let
$\lambda_h \geq 0$ denote the Lagrange multiplier for the
constraint~\eqref{eq:queryp} for classifier $h$.  Then for any
$\boldsymbol{\lambda}$, we can minimize the Lagrangian
\begin{equation}
\mathcal{L}(P,\boldsymbol{\lambda}) :=
  \ensuremath{\mathbb{E}}_X \left[ \frac{1}{1 -
      P(X)}\right] + \ensuremath{\mu}^2 \ensuremath{\mathbb{E}}_X\left[ \frac{\mathds{1}(X \in
    D_\ensuremath{m})}{P(X)}\right] - \sum_{h \in \H} \lambda_h \left(b_{\ensuremath{m}}(h) - \ensuremath{\mathbb{E}}_X\left[ \frac{\mathds{1}(h(X) \neq h_\ensuremath{m}(X) \wedge X \in D_\ensuremath{m})}{P(X)}\right] \right)
\label{eq:Lagrangian}
\end{equation}
over each primal variable
$P(x) \in [0,1]$ yielding the solution.
\begin{align}
  P_{\boldsymbol{\lambda}}(x) = \frac{\mathds{1}(x \in D_\ensuremath{m})q_{\boldsymbol{\lambda}}(x)}{1 +
    q_{\boldsymbol{\lambda}}(x)}, ~~ \mbox{where} ~~ q_{\boldsymbol{\lambda}}(x) =
  \sqrt{\ensuremath{\mu}^2 + \sum_{h \in \H} \lambda_h \disind{h}(x)}.
  \label{eqn:primal-dual}
\end{align}
To see this, pick any $\widetilde{P}$ satisfying $\widetilde{P}(x) \in [0,1]$ for all $x \in \dataspace$
and consider the difference in the Lagrangians evaluated at $\widetilde{P}$ and $P_{\boldsymbol{\lambda}}$:
\begin{eqnarray*}
\mathcal{L}(\widetilde{P},\boldsymbol{\lambda}) - \mathcal{L}(P_{\boldsymbol{\lambda}},\boldsymbol{\lambda})
&=&
\ensuremath{\mathbb{E}}_X\left[ \mathds{1}(X \notin D_\ensuremath{m}) \left(\frac{1}{1 - \widetilde{P}(X)}-1 \right)\right]  \nonumber \\
&& +\ensuremath{\mathbb{E}}_X\left[ \mathds{1}(X \in D_\ensuremath{m}) \left( \frac{1}{1-\widetilde{P}(X)} + \frac{\ensuremath{\mu}^2 + \sum_{h \in \H} \lambda_h \disind{h}(x)}{\widetilde{P}(X)} - (1 + q_{\boldsymbol{\lambda}}(X))^2\right)\right].
\end{eqnarray*}
The first term is non-negative because $\widetilde{P}(x) \in [0,1]$.
For the second term, notice that
\begin{equation*}
P_{\boldsymbol{\lambda}}(x) = \arg \min_{0 \leq v \leq 1} \quad \mathds{1}(x \in D_\ensuremath{m}) \left( \frac{1}{1-v} + \frac{\ensuremath{\mu}^2 + \sum_{h \in \H}\lambda_h \disind{h}(x)}{v} \right)
\end{equation*}
and that the minimum function value is exactly $\mathds{1}(x \in D_\ensuremath{m})(1 + q_{\boldsymbol{\lambda}}(x))^2$.
Hence the second term is also non-negative.

Clearly, $\ensuremath{\mu}/(1 + \ensuremath{\mu}) \leq P_{\boldsymbol{\lambda}}(x) \leq 1$
for all $x \in D_\ensuremath{m}$, so all the bound
constraints~\eqref{eq:minbndcons} in $(\optprob)$ are satisfied if we
choose $\ensuremath{\mu} = 2\pmin$. Plugging the solution $P_{\boldsymbol{\lambda}}$ into the
Lagrangian, we obtain the dual problem of maximizing the dual
objective
\begin{equation}  \label{eqn:dual-obj}
  {\cal D}(\boldsymbol{\lambda}) = \ensuremath{\mathbb{E}}_X\left[\mathds{1}(X \in D_\ensuremath{m}) (1 +
    q_{\boldsymbol{\lambda}}(X))^2 \right] - \sum_{h \in \H} \lambda_h b_\ensuremath{m}(h)
  + C_0
\end{equation}
over $\boldsymbol{\lambda}\geq 0$. The constant $C_0$ is equal to
$1-\ensuremath{\mathrm{Pr}}(D_\ensuremath{m})$ where $\ensuremath{\mathrm{Pr}}(D_\ensuremath{m})=\ensuremath{\mathrm{Pr}}(X \in D_\ensuremath{m})$.  An
algorithm to approximately solve this problem is presented in
Algorithm~\ref{alg:coord}.  The algorithm takes a parameter
$\varepsilon>0$ specifying the degree to which all of the constraints
\eqref{eq:queryp} are to be approximated.  Since ${\cal D}$ is
concave, the rescaling step can be solved using a straightforward
numerical line search.  The main implementation challenge is in
finding the most violated constraint (Step~\ref{step:violated}).
Fortunately, this step can be reduced to a single call to an ERM
oracle.  To see this, note that the constraint violation on classifier
$h$ can be written as
\begin{align*}
  \ensuremath{\mathbb{E}}_X\left[ \frac{\disind{h}(X)}{P(X)}\right] - b_\ensuremath{m}(h)
  &= \ensuremath{\mathbb{E}}_X\left[\mathds{1}(X \in D_\ensuremath{m})\left(\frac{1}{P(X)} -
    2\alpha^2\right) \mathds{1}(h(X) \ne h_\ensuremath{m}(X)) \right]\\ & -
  2\beta^2 \gamma\epend[\ensuremath{m}-1] \Delta_{\ensuremath{m}-1}(\ensuremath{\mathrm{err}}(h,
  \ensuremath{\tilde{Z}}_{\ensuremath{m}-1}) - \ensuremath{\mathrm{err}}(h_\ensuremath{m}, \ensuremath{\tilde{Z}}_{\ensuremath{m}-1})) - \ensuremath{\xi}
  \epend[\ensuremath{m}-1]\Delta_{\ensuremath{m}-1}^2.
\end{align*}
The first term of the right-hand expression is the risk (classification error) of $h$ in predicting samples
labeled according to $h_\ensuremath{m}$ with importance weights of $1/P(x) -
2\alpha^2$ if $x \in D_\ensuremath{m}$ and 0 otherwise; note that these
weights may be positive or negative.
The second term is simply the scaled risk
of $h$ with respect to the actual labels.
The last two terms do not depend
on $h$. Thus, given access to $\distx$ (or samples approximating
it, discussed shortly), the most violated constraint can be found by
solving an ERM problem defined on the labeled samples in $\ensuremath{\tilde{Z}}_{\ensuremath{m}-1}$
and
samples drawn from $\distx$ labeled by $h_\ensuremath{m}$, with appropriate importance weights detailed in Appendix \ref{appendix:most_violated_erm}.

When all primal constraints are approximately satisfied, the algorithm
stops. Consequently, we can execute each step of
Algorithm~\ref{alg:coord} with one call to an appropriately defined
ERM oracle, and approximate primal feasibility is guaranteed when the
algorithm stops.  More specifically, we can prove the following
guarantee on the convergence of the algorithm.

\begin{theorem}
\label{thm:opt_converge}
When run on the $\ensuremath{m}$-th epoch, Algorithm~\ref{alg:coord}
has the following guarantees.
\begin{enumerate}
\item It halts in at most $\frac{\ensuremath{\mathrm{Pr}}(D_\ensuremath{m})}{8 \pmin^3 \varepsilon^2}$ iterations.
\item The solution $\hat{\boldsymbol{\lambda}} \geq \mathbf 0$ it
outputs has bounded $\ell_1$ norm: $\lone{\hat{\boldsymbol{\lambda}}}\leq
\ensuremath{\mathrm{Pr}}(D_\ensuremath{m}) / \varepsilon$.
\item The query probability function $P_{\hat{\boldsymbol{\lambda}}}$ satisfies:
\begin{itemize}
\item The variance constraints
\eqref{eq:queryp} up to an additive factor of $\varepsilon$, i.e.,
\begin{equation*}
  \forall h \in \H\;\; \ensuremath{\mathbb{E}}_X \left[
    \frac{\mathds{1}(h(x) \neq h_\ensuremath{m}(x) \wedge x
  \in D_\ensuremath{m})}{P_{\hat{\boldsymbol{\lambda}}}(X)}\right] \leq b_\ensuremath{m}(h) + \varepsilon,
\end{equation*}
\item
The simple bound constraints
\eqref{eq:minbndcons} exactly,
\item Approximate primal optimality:
\begin{equation}  \label{eq:prim-obj-bnd}
	\ensuremath{\mathbb{E}}_X\left[ \frac{1} {1 - P_{\hat{\boldsymbol{\lambda}}}(X)} \right] \leq

        f^* + 4 \pmin
        \ensuremath{\mathrm{Pr}}(D_\ensuremath{m}),
\end{equation}
where $f^*$ denotes the optimal value of $(\optprob)$, i.e,
\begin{equation}
\begin{split}
 f^* \;:= \;& \inf_P \; \ensuremath{\mathbb{E}}_X \left[ \frac{1}{1-P(X)} \right] \\
\mbox{s.t.} \quad& P \mbox{ satisfying } \eqref{eq:queryp} \mbox{ and } \eqref{eq:minbndcons}
\end{split}
\label{eq:op_value}
\end{equation}
\end{itemize}
\end{enumerate}
\end{theorem}
That is, we find a solution with small constraint violation to ensure
generalization, and a small objective value to be label efficient.
If
$\varepsilon$ is set to $\ensuremath{\xi}
\epend[\ensuremath{m}-1]\Delta_{\ensuremath{m}-1}^2$, an amount of constraint
violation tolerable in our analysis, the number of iterations in
Theorem \ref{thm:opt_converge} varies between
$\ensuremath{\mathcal{O}}(\epend[\ensuremath{m}-1]^{3/2})$ and $\ensuremath{\mathcal{O}}(\epend[\ensuremath{m}-1]^2)$ as
the $\ensuremath{\mathrm{err}}(h_\ensuremath{m},\ensuremath{\tilde{Z}}_{\ensuremath{m}-1})$ varies between a constant and
$\ensuremath{\mathcal{O}}(1/\epend[\ensuremath{m}-1])$. The theorem is proved in
Appendix~\ref{sec:opt-pop}.

\subsection{Solving (\optprob) with expectation over samples}
So far we considered solving $(\optprob)$ defined on the unlabeled
data distribution $\distx$, which is not available in practice.
A simple and natural substitute for $\distx$ is an i.i.d. sample drawn from it.
Here we show that solving a properly-defined sample variant of (\optprob) leads to
a solution to the original $(\optprob)$ with similar guarantees
as in Theorem \ref{thm:opt_converge}.

More specifically, we define the following sample variant of $(\optprob)$.
Let $S$ be a large sample drawn i.i.d. from $\distx$,
and $(\optprob_S)$ be the
same as $(\optprob)$ except with all population expectations
replaced by empirical expectations taken with
respect to $S$. Now for any $\samperr\geq0$, define
$(\optprob_{S,\samperr})$ to be the same as $(\optprob_S)$ except
that the variance constraints~\eqref{eq:queryp} are relaxed by an additive slack of $\samperr$.

Every time \textsc{Active Cover}\xspace needs to solve $(\optprob)$ (Step \ref{alg:main:P_update} of Algorithm \ref{alg:main}),
it draws a fresh unlabeled i.i.d. sample $S$ of size $\ensuremath{u}$ from $\distx$, which can be done easily
in a streaming setting by collecting the next $u$ examples. It then
applies Algorithm~\ref{alg:coord} to solve $(\optprob_{S,\samperr})$
with accuracy parameter $\samperr$. Note that this is different from solving $(\optprob_S)$
with accuracy parameter $2\varepsilon$.
We establish the following convergence guarantees.
\begin{theorem}
  \label{thm:optprob-unlabeled}
  Let $S$ be an i.i.d.~sample of size $\ensuremath{u}$ from $\distx$.
When run on the $\ensuremath{m}$-th epoch for solving $(\optprob_{S,\samperr})$ with accuracy parameter
  $\samperr$, Algorithm~\ref{alg:coord} satisfies the following.
\begin{enumerate}
\item It halts in at most $\frac{\widehat{\ensuremath{\mathrm{Pr}}}(D_\ensuremath{m})}{8 \pmin^3 \varepsilon^2}$ iterations, where $\widehat{\ensuremath{\mathrm{Pr}}}(D_\ensuremath{m}) := \sum_{X \in S} \mathds{1}(X \in D_\ensuremath{m}) / \ensuremath{u}$.
\item The solution $\hat{\boldsymbol{\lambda}} \geq \mathbf 0$ it
outputs has bounded $\ell_1$ norm: $\lone{\hat{\boldsymbol{\lambda}}}\leq
\widehat{\ensuremath{\mathrm{Pr}}}(D_\ensuremath{m}) / \varepsilon$.
\item If $\ensuremath{u} \geq \ensuremath{\mathcal{O}} ((1/(\pmin\samperr)^4 +
  \alpha^4/\samperr^2) \log(|\H|/\delta))$, then with probability
  $\geq~1-\delta$, the query probability function $P_{\hat{\boldsymbol{\lambda}}}$ satisfies:
\begin{itemize}
\item All constraints of $(\optprob)$ except with an
  additive slack of $2.5\samperr$ in the variance constraints~\eqref{eq:queryp},
\item Approximate primal optimality:
  \begin{equation*}
    \ensuremath{\mathbb{E}}_X \Brackets{ \frac{1}{1 - P_{\hat{\boldsymbol{\lambda}}}(X)} } \ \leq
    \
    f^* + 8 \pmin
    \ensuremath{\mathrm{Pr}}(D_\ensuremath{m}) + \parens{ 2 + 4 \pmin} \samperr,
  \end{equation*}
where $f^*$ is the optimal value of $(\optprob)$ defined in \eqref{eq:op_value}.
\end{itemize}
\end{enumerate}
\end{theorem}
The proof is in Appendix \ref{sec:opt-samp}. Intuitively, the optimal
solution ${P^*}$ to $(\optprob)$ is also feasible in $(\optprob_{S,
  \samperr})$ since satisfying the population constraints leads to
approximate satisfaction of sample constraints. Since our solution
$P_{\hat{\boldsymbol{\lambda}}}$ is approximately optimal for $(\optprob_{S,
  \varepsilon})$ (this is essentially due to
Theorem~\ref{thm:opt_converge}), this means that the sample objective
at $P_{\hat{\boldsymbol{\lambda}}}$ is not much larger than ${P^*}$. We now use a
concentration argument to show that this guarantee holds also for the
population objective with slightly worse constants. The approximate
constraint satisfaction in $(\optprob)$ follows by a similar
concentration argument. Our proofs use standard concentration
inequalities along with Rademacher complexity to provide uniform
guarantees for all vectors $\boldsymbol{\lambda}$ with bounded $\ell_1$ norm.

The first two statements, finite convergence and boundedness of
$\lone{\hat{\boldsymbol{\lambda}}}$, are identical to Theorem
\ref{thm:opt_converge} except $\ensuremath{\mathrm{Pr}}(D_\ensuremath{m})$ is replaced by
$\widehat{\ensuremath{\mathrm{Pr}}}(D_\ensuremath{m})$.  When $\varepsilon$ is set properly, i.e,
to be $\ensuremath{\xi}^2 \epend[\ensuremath{m}-1]\Delta_{\ensuremath{m}-1}^2$, the number
of unlabeled examples $\ensuremath{u}$ in the third statement varies between
$\ensuremath{\mathcal{O}}(\epend[\ensuremath{m}-1]^{2})$ and $\ensuremath{\mathcal{O}}(\epend[\ensuremath{m}-1]^4)$ as the
$\ensuremath{\mathrm{err}}(h_\ensuremath{m},\ensuremath{\tilde{Z}}_{\ensuremath{m}-1})$ varies between a constant and
$\ensuremath{\mathcal{O}}(1/\epend[\ensuremath{m}-1])$. The third statement shows that with
enough unlabeled examples, we can get a query probability function
almost as good as the solution to the population problem $(\optprob)$.

\section{Experiments with Agnostic Active Learning}
\label{sec:experiments}
\begin{algorithm}
\caption{\textsc{Online Active Cover}\xspace}
\label{alg:cover}
\begin{algorithmic}[1]
\renewcommand{\algorithmicrequire}{\textbf{input:}}
\REQUIRE cover size $\ensuremath{l}$, parameters $c_0, \alpha$ and $\beta_{scale}$.
\STATE Initialize online importance weighted minimization oracles $\{O_t\}_{t=0}^\ensuremath{l}$, each controlling a classifier and some associated weights $\{(h_{t}, \lambda_{t},\nu_{t}, \omega_{t})\}_{t=1}^\ensuremath{l}$ with all
weights initialized to 0.
\STATE For the first three examples $\{X_i\}_{i=1}^3$, query the labels $\{Y_i\}_{i=1}^3$.
\STATE Let $h := O_0(\{(X_i,Y_i,1)\}_{i=1}^2)$.
\STATE Get error estimate $e_2$ from $O_0$ and compute $P_{\min,3}$.
\STATE Let $(X, Y^*, \tilde{Y}, W) := (X_3, Y_3, h(X_3), 1)$. Set $\beta := (\sqrt{\alpha/c_0})/ \beta_{scale}$.
\FOR{$i = 4,\ldots,n,$}
\STATE Update the ERM, the error estimate and the threshold \label{alg:cover:erm_update}
\begin{eqnarray*}
	h &:=& O_0((X,Y^*,W)),\\
	e_{i-1} &:=& \frac{(i-2) e_{i-2} + \mathds{1}(\tilde{Y} \neq Y^*)W}{i-1},\\
        \widehat{\Delta}_{i-1} &:=& \sqrt{c_0e_{i-1}/(i-1)} + \max(2\alpha,4)c_0 \log(i-1)/(i-1).
\end{eqnarray*}
\FOR{$t = 1,\ldots,\ensuremath{l}$} \label{alg:cover:update_begin}
\STATE Compute $p_t := q_t / (1 + q_t)$, where $q_t := \sqrt{(2P_{\min,i-1})^2 + \sum_{t' < t} \lambda_t \mathds{1}(h_t(X) \neq \tilde{Y}))}$.
\STATE Set up the cost of predicting $y \in \{1,-1\}$, the target label and the importance weight:
\begin{eqnarray}
\mathbf c_y &:=& 2 \beta^2 (i-2)\widehat{\Delta}_{i-2} \mathds{1}(y \neq Y^*)W + \left(2 \alpha^2 - \frac{1}{p_t}\right) \mathds{1}(X \in D_{i-1} \wedge y \neq \tilde{Y}),
\label{eq:cover_cost} \\
Y_{t} &:=& \arg \min_y \mathbf c_y, \nonumber \\
W_{t} &:=& |\mathbf c_{1} - \mathbf c_{-1}|.\nonumber
\end{eqnarray}
\STATE Update the $t$-th classifier in the cover and its associated weights:
\begin{eqnarray}
	h_{t} &:=& O_t((X,Y_{t},W_{t})),\nonumber \\

	\nu_{t} &:=& \max\left( \nu_{t} + 2 \Big( \mathbf c_{\tilde{Y}} - \mathbf c_{h_{t}(X)}\Big) , 0 \right), \label{eq:cover:update_num}\\
	\omega_{t}&:=& \omega_{t} + \mathds{1}(h_{t}(X) \neq \widetilde{Y} \wedge X \in D_{i-1}) / q_t^3, \label{eq:cover:update_den}\\
	\lambda_{t} &:=& \frac{\nu_{t}}{\omega_{t}} \mathds{1}\big((\nu_{t},\omega_{t}) \neq (0,0)\big). \label{eq:cover:update_lambda}
\end{eqnarray}
\ENDFOR \label{alg:cover:update_end}
\STATE Receive new data point $X_i$ and let $\tilde{Y} := h(X_i)$. \label{alg:cover:query}
\STATE Compute $P_{\min,i} := \min\big( (\sqrt{(i-1)e_{i-1}}+\log(i-1))^{-1}, 1/2\big)$.
\IF{$X_i \in D_i:= \mbox{DIS}(A_i)$,} \label{alg:cover:dis_test}
\STATE Compute $P_i := q /(1 + q)$, where $q := \sqrt{(2P_{\min,i})^2 + \sum_{t = 1}^l \lambda_t \mathds{1}(h_t(X_i) \neq \tilde{Y}))}$.
\STATE Draw $Q \sim \mbox{Bernoulli}(P)$.
\IF{$Q = 1$}
\STATE Query $Y_i$ and set $(X, Y^*,W) := (X_i, Y_i, 1/P_i)$.
\ELSE
\STATE Set $(X, Y^*,W) := (X_i, 1,0)$.
\ENDIF
\ELSE
\STATE
Set $(X, Y^*,W) := (X_i, h(X_i), 1)$.
\ENDIF \label{alg:cover:query_end}
\ENDFOR
\end{algorithmic}
\end{algorithm}
While \textsc{AC}\xspace is efficient in the number of ERM oracle calls, it needs to
store all past examples, resulting in large space complexity. As
Theorem \ref{thm:opt_converge} suggests, the query probability
function \eqref{eqn:primal-dual} may need as many as
$\ensuremath{\mathcal{O}}(\epend[i]^2)$ classifiers, further increasing storage
demand.  In Section \ref{sec:online_cover} we discuss
a scalable online approximation to \textsc{Active Cover}\xspace, \textsc{Online Active Cover}\xspace (\textsc{oac}\xspace),
which we implemented and tested empirically with the setup in Section \ref{sec:exp_setup}.
Experimental results and discussions are in Section \ref{sec:exp_results}.

\subsection{Online Active Cover (\textsc{oac}\xspace)}
\label{sec:online_cover}
Algorithm \ref{alg:cover} gives the online approximation that we implemented,
which uses an epoch schedule of $\epend[i] = i$, assigning every new example to a new epoch.

To explain the connections between Algorithms \ref{alg:main} (\textsc{AC}\xspace) and \ref{alg:cover} (\textsc{oac}\xspace), we start with
the update of the ERM classifier and thresholds, corresponding to Step \ref{alg:main:erm_update} of \textsc{AC}\xspace
and Step \ref{alg:cover:erm_update}  of \textsc{oac}\xspace.
Instead of batch ERM oracles, \textsc{oac}\xspace invokes online importance weighted ERM oracles that are stateful
and process examples in a streaming fashion without the need to store them.
The specific importance weighted oracle we use is a reduction to online importance-weighted logistic regression \citep{KLonline} implemented in Vowpal Wabbit (VW).
$Y^*$ denotes the actual label that is used to update the ERM classifier and, depending on the query decision (Steps \ref{alg:main:query} to \ref{alg:main:query_end}),
can be a queried label, a predicted label by the previous ERM classifier, or a dummy label of 1 associated with an importance weight of zero.
The error variable $e_{i-1}$ keeps track of the \emph{progressive validation loss}, which is a better estimate of the true classification error
than the training error \citep{blum1999beating,cesa2004generalization}.

Instead of computing the query probability function by solving a batch optimization problem as in Step \ref{alg:main:P_update} of \textsc{AC}\xspace,
\textsc{oac}\xspace maintains a fixed number $\ensuremath{l}$ of classifiers that are intended to be a cover of the set of good classifiers.
On every new example, this cover undergoes a sequence of online, importance weighted
updates (Steps \ref{alg:cover:update_begin} to \ref{alg:cover:update_end} of \textsc{oac}\xspace),
which are meant to approximate the coordinate ascent steps in Algorithm \ref{alg:coord}.
The importance structure \eqref{eq:cover_cost} is derived from \eqref{eq:cost},
accounting for the fact that
the algorithm simply uses the incoming stream of examples to estimate
$\bbE_X[\cdot]$ rather than a separate unlabeled sample.
The same approximation is also present in the updates \eqref{eq:cover:update_num} and  \eqref{eq:cover:update_den},
which are online estimates of the numerator and the denominator of the additive coordinate update
in Step \ref{step:coord-update} of Algorithm \ref{alg:coord}. Because \eqref{eq:cover:update_num}
is an online estimate, we need to explicitly enforce non-negativity. Note that \eqref{eq:cover:update_num}
has the following straightforward interpretation: if the prediction of $h_t$, the $t$-th classifier in the cover,
is the same as that of the ERM, the weight associated with $h_t$ will not change. Otherwise,
the weight of $h_t$ increases/decreases when its prediction has a smaller/larger cost than the prediction of the ERM.

To further clarify the effect of \eqref{eq:cover_cost}, we perform the following case analysis:
\begin{itemize}
\item If $X_{i-1} \notin D_{i-1}$, then for all $t \in \{1,\ldots,l\}$,
\begin{equation*}
(\mathbf c_{\tilde{Y}},\mathbf c_{-\tilde{Y}}) \;=\; (0, 2 \beta^2 (i-2) \widehat{\Delta}_{i-2}),
\end{equation*}
so $Y_t = \tilde{Y}$. This means that all the classifiers in the cover are trained with the predicted label when the example is outside of the disagreement region.
\item Otherwise, the costs for the $t$-th classifier in the cover are:
\begin{eqnarray*}
(\mathbf c_{\tilde{Y}},\mathbf c_{-\tilde{Y}}) &=&
\begin{cases}
(0,2\alpha^2 - 1 / p_t), & Q = 0, \mbox{i.e., the true label was not queried},\\
(0, 2\alpha^2 - 1 / p_t + 2 \beta^2 (i-2) \widehat{\Delta}_{i-2}/P_{i-1}), & Q = 1, \tilde{Y} = Y_{i-1},\\
(2 \beta^2 (i-2) \widehat{\Delta}_{i-2}/P_{i-1}, 2 \alpha^2 - 1/p_t), & Q = 1, \tilde{Y} \neq Y_{i-1}.
\end{cases}
\end{eqnarray*}
In the first case, if  $p_t > 1/(2 \alpha^2)$, i.e.,
the query probability based on the previous $t-1$ classifiers in the cover is large enough, then $\mathbf c_{-\tilde{Y}} > 0$ and the $t$-th classifier will be trained to agree with the predicted label.
Otherwise, the $t$-th classifier will be trained to disagree with the predicted label, thereby increasing
the query probability. In the second case, the true label $Y_{i-1}$ was queried and found to be the same as the predicted label, so unless
$p_t$ is very small, the $t$-th classifier will not be trained to disagree with the ERM $h$. In the third case, the cost associated with the predicted
label $\tilde{Y}$ is always positive, so the true label $Y_{i-1}$ will be preferred unless $p_t$ or $\alpha$ is fairly large.
\end{itemize}

Finally, Steps \ref{alg:main:query} to \ref{alg:main:query_end} of \textsc{AC}\xspace
and Steps \ref{alg:cover:query} to \ref{alg:cover:query_end} of \textsc{oac}\xspace
perform the querying of labels.
As pointed out in Section \ref{sec:optimization}, the test in Step \ref{alg:cover:dis_test} of \textsc{oac}\xspace
is done via an {\em online technique} detailed in Appendix F of \citet{KLonline}.

\subsection{Experiment Setting}
\label{sec:exp_setup}
We conduct an empirical comparison of $\textsc{oac}\xspace$ with the following active learning algorithms.
\begin{itemize}
\item \textsc{iwal}$_0$\xspace: Algorithm 1 of \citet{BeygelHLZ10}, which performs importance-weighted
sampling of labels and maintains an unbiased estimate of classification error. On every new example, it queries the true label with probability 1 if
the error difference $G_k$ (Step 2 in Algorithm 1 of \citet{BeygelHLZ10}) is smaller than the threshold
\begin{equation}
\sqrt{\frac{C_0 \log k}{k-1}} + \frac{C_0 \log k}{k-1},
\label{eq:iwal0_threshold}
\end{equation}
where $C_0$ is a hyper-parameter. Otherwise, the query probability is a decreasing function of $G_k$.

\item \textsc{iwal}$_1$\xspace: A slight modification of \textsc{iwal}$_0$\xspace that uses
a more aggressive, error-dependent threshold:
\begin{equation}
\sqrt{\frac{C_0 \log k}{k-1} e_{k-1}} + \frac{C_0 \log k}{k-1},
\label{eq:iwal_threshold}
\end{equation}
where $e_{k-1}$ is the importance-weighted error estimate after the algorithm processes $k-1$ examples.

\item \textsc{ora-iwal}$_0$\xspace: An Oracular-CAL \citep{hsu2010algorithms} style variant of \textsc{iwal}$_0$\xspace that queries the label
of a new example with probability 1 if the error difference $G_k$ (see \textsc{iwal}$_0$\xspace above) is smaller than the threshold
\eqref{eq:iwal0_threshold}. Otherwise, it uses the predicted label by the current ERM classifier.
\item \textsc{ora-iwal}$_1$\xspace: An Oracular-CAL \citep{hsu2010algorithms} style variant of \textsc{iwal}$_1$\xspace
that resembles \textsc{ora-iwal}$_0$\xspace except that it uses the error-dependent threshold \eqref{eq:iwal_threshold}.
Note that the error estimate $e_{k-1}$ now uses
both the queried labels and predicted labels, and is no longer unbiased.
We remark that a theoretical analysis of this algorithm has recently
been given by~\citet{zhang2015oracular}. In fact, it is almost identical to an Oracular-CAL \citep{hsu2010algorithms} style variant of Algorithm \ref{alg:cover}
that uses a query probability $P_i$ of 1 whenever the disagreement test in Step \ref{alg:cover:dis_test}
of Algorithm \ref{alg:cover} returns true, except that its threshold \eqref{eq:iwal_threshold} is slightly different from
the one used by Algorithm \ref{alg:cover} (Step \ref{alg:cover:erm_update}).
\item \textsc{passive}\xspace: Passive learning using all the labels of incoming examples up to some label budget.
\end{itemize}

We implemented these algorithms
in Vowpal Wabbit\footnote{\url{http://hunch.net/~vw/}.} (VW),
a fast learning system using online convex optimization, which
fits nicely with the streaming active learning setting.
We performed experiments on 22 binary classification datasets with
varying sizes ($10^3$ to $10^6$) and diverse feature
characteristics. Details about the datasets are in Appendix
\ref{appendix:datasets}. Our goals are:
\begin{enumerate}
\item Investigating the maximal test error improvement per label query achievable by different algorithms;
\item Comparing different algorithms when each uses the best fixed hyper-parameter setting.
\end{enumerate}
We thus consider the following experiment setting. To simulate the streaming setting,
we randomly permuted the datasets, ran the active learning algorithms
through the first 80$\%$ of data, and evaluated the learned classifiers
on the remaining 20$\%$. We repeated this process 9 times to reduce variance
due to random permutation.
For each active learning algorithm, we obtain the test error rates of classifiers trained at doubling numbers of label queries
starting from 10 to 10240. Formally, let $\ensuremath{\mathrm{error}}_{a,p}(d,j,q)$ denote the test error of the classifier returned by algorithm $a$
using hyper-parameter setting $p$ on the $j$-th permutation of dataset $d$ under a label budget of $10\cdot 2^{(q-1)}$, $1 \leq q \leq 11$,
and $\ensuremath{\mathrm{query}}_{a,p}(d,j,q)$ denote the actual number of label queries made.
Note that under the same label budget, \textsc{oac}\xspace and the Oracular-CAL variants may use more example-label pairs for learning
than \textsc{iwal}$_0$\xspace and \textsc{iwal}$_1$\xspace because the former algorithms use predicted labels.
Also note that $\ensuremath{\mathrm{query}}_{a,p}(d,j,q) < 10\cdot 2^{(q-1)}$ when algorithm $a$ reaches the end of the training data before
hitting the $q$-th label budget.
To evaluate the overall performance of an algorithm, we consider the area under its curve of test error against
$\log$ number of label queries:
\begin{equation}
\ensuremath{\mathrm{AUC}}_{a,p}(d,j) = \frac{1}{2} \sum_{q = 1}^{10} \Big(\ensuremath{\mathrm{error}}_{a,p}(d,j,q+1) +  \ensuremath{\mathrm{error}}_{a,p}(d,j,q)\Big) \cdot \left(\log_2 \frac{\ensuremath{\mathrm{query}}_{a,p}(d,j,q+1)}{\ensuremath{\mathrm{query}}_{a,p}(d,j,q)}\right).
\end{equation}
A good active learning algorithm has a small value of \ensuremath{\mathrm{AUC}}, which indicates that the test error decreases quickly as the number of label queries increases.
We use a logarithmic scale for the number of label queries to focus on the performance under few label queries where active learning
is the most relevant. More details about hyper-parameters are in
Appendix \ref{appendix:hyper-parameters}.

For the first goal, we compare the performances of different algorithms optimized on a per dataset basis.
More specifically, we
measure of the performance of algorithm $a$ by the following aggregated metric:
\begin{equation}
\displaystyle \ensuremath{\mathrm{AUC\mbox{-}GAIN}}^*(a) := \underset{d}{\ensuremath{\mathrm{mean}}} \max_{p} \underset{1 \leq j \leq 9}{\ensuremath{\mathrm{median}}} \left\{ \frac{\ensuremath{\mathrm{AUC}}_{base}(d,j) - \ensuremath{\mathrm{AUC}}_{a,p}(d,j)}{\ensuremath{\mathrm{AUC}}_{base}(d,j)} \right\},
\label{eq:auc-gain-per-data}
\end{equation}
where $\ensuremath{\mathrm{AUC}}_{base}$ denotes the \ensuremath{\mathrm{AUC}} \; of \textsc{passive}\xspace using a default hyper-parameter setting, corresponding to a learning rate of 0.4 (see Appendix \ref{appendix:hyper-parameters} for more details).
In this metric, we first take the median of the relative test error improvements over the \textsc{passive}\xspace baseline, which gives
a representative performance among the 9 random permutations, and then take the maximum of the medians over hyper-parameters, and finally
average over datasets. This metric shows the maximal gain each algorithm achieves with the best hyper-parameter setting for
each dataset.

In practice it is difficult to select active learning hyper-parameters on a per-dataset
basis because labeled validation data are not available. With
a variety of classification datasets, a reasonable alternative might be to
look for the single hyper-parameter setting that performs the best on
average across datasets, thereby reducing over-fitting to any
individual dataset, and compare different algorithms under such fixed
parameter settings. We thus consider the following metric:
\begin{equation}
\displaystyle \ensuremath{\mathrm{AUC\mbox{-}GAIN}}(a) := \max_{p} \underset{d}{\ensuremath{\mathrm{mean}}} \; \underset{1 \leq j \leq 9}{\ensuremath{\mathrm{median}}} \left\{ \frac{\ensuremath{\mathrm{AUC}}_{base}(d,j) - \ensuremath{\mathrm{AUC}}_{a,p}(d,j)}{\ensuremath{\mathrm{AUC}}_{base}(d,j)} \right\},
\label{eq:auc-gain}
\end{equation}
which first averages the median improvements over datasets and then maximizes over hyper-parameter settings.

\subsection{Results and Discussions}
\label{sec:exp_results}
Table \ref{tbl:summary} gives a
summary of the performances of different algorithms, measured
by the two metrics $\ensuremath{\mathrm{AUC\mbox{-}GAIN}}^*$ \eqref{eq:auc-gain-per-data} and $\ensuremath{\mathrm{AUC\mbox{-}GAIN}}$ \eqref{eq:auc-gain}.
When using hyper-parameters optimized on a per-dataset basis (top row in Table \ref{tbl:summary}), \textsc{oac}\xspace achieves the largest improvement over the \textsc{passive}\xspace baseline,
with \textsc{ora-iwal}$_0$\xspace achieving almost the same improvement and
other active learning algorithms improving slightly less.
When using the best fixed hyper-parameter setting across all datasets (bottom row in Table \ref{tbl:summary}), all active learning algorithms
achieve less improvement compared with \textsc{passive}\xspace, which achieves a $7$\% improvement with the best fixed learning rate.
\textsc{ora-iwal}$_0$\xspace performs the best, achieving a 9\% improvement, while \textsc{iwal}$_0$\xspace and \textsc{ora-iwal}$_1$\xspace
achieve more than 8\%. Both \textsc{iwal}$_1$\xspace and \textsc{oac}\xspace achieve around $7.5$\% improvements, slightly better than
\textsc{passive}\xspace. This suggests that careful tuning of hyper-parameters is critical for \textsc{oac}\xspace and an important direction for future work.

\begin{table}[t]
\centering
\caption{Summary of performance metrics}
\setlength{\tabcolsep}{1pt}
\begin{tabular}{l||C{50pt}|C{50pt}|C{50pt}|C{50pt}|C{50pt}|C{50pt}|C{50pt}}
  & \textsc{oac}\xspace & \textsc{iwal}$_0$\xspace & \textsc{iwal}$_1$\xspace & \textsc{ora-iwal}$_0$\xspace & \textsc{ora-iwal}$_1$\xspace & \textsc{passive}\xspace \\ \hline \hline
$\ensuremath{\mathrm{AUC\mbox{-}GAIN}}^*$ &\textbf{0.1611} & 0.1466 & 0.1552 & 0.1586 & 0.1549  & 0.0950\\ \hline
$\ensuremath{\mathrm{AUC\mbox{-}GAIN}}$   & 0.0722 & 0.0863 & 0.0755 & \textbf{0.0945} & 0.0807 & 0.0718
\end{tabular}
\label{tbl:summary}
\end{table}
\begin{figure}[t]
\centering
\subfigure[Median over permutations]{\label{fig:rel-err-gain-median}\includegraphics[width=0.33\textwidth,height=0.25\textwidth]{./fig/best_param_all_rel-err-gain_1.pdf}}
\subfigure[The first permutation]{\label{fig:rel-err-gain-single}\includegraphics[width=0.33\textwidth,height=0.25\textwidth]{./fig/best_param_all_rel-err-gain_2.pdf}}
\subfigure[Three quartiles over permutations]{\label{fig:rel-err-gain-quartiles}\includegraphics[width=0.33\textwidth,height=0.25\textwidth]{./fig/best_param_all_rel-err-gain_3.pdf}}
\caption{Relative improvement in test error v.s. number of label queries under the best fixed hyper-parameter setting across datasets. Results are averaged over all datasets.}
\label{fig:rel-err-gain}
\end{figure}
To describe the behaviors of different algorithms in more details, we plot the relative improvement in test error
against number of label queries.
In Figure \ref{fig:rel-err-gain-median}, for each algorithm $a$ we identify the best fixed hyper-parameter setting
\begin{equation}
p^* := \arg \max_{p} \underset{d}{\ensuremath{\mathrm{mean}}} \; \underset{1 \leq j \leq 9}{\ensuremath{\mathrm{median}}} \left\{ \frac{\ensuremath{\mathrm{AUC}}_{base}(d,j) - \ensuremath{\mathrm{AUC}}_{a,p}(d,j)}{\ensuremath{\mathrm{AUC}}_{base}(d,j)} \right\},
\end{equation}
and plot the relative test error improvement by $a$ using $p^*$ averaged across all datasets at the 11 label budgets:
\begin{equation}
\left \{\left(10 \cdot 2^{(q-1)}, \underset{d}{\ensuremath{\mathrm{mean}}} \; \underset{1 \leq j \leq 9} \ensuremath{\mathrm{median}} \left\{\frac{\ensuremath{\mathrm{error}}_{base}(d,j,q) - \ensuremath{\mathrm{error}}_{a,p^*}(d,j,q)}{\ensuremath{\mathrm{error}}_{base}(d,j,5)}\right\}\right)\right\}_{q=1}^{11}.
\label{eq:rel-err-gain}
\end{equation}
The two IWAL algorithms start off badly at small numbers of label queries, but
outperform other algorithms after 100-or-so label queries.
\textsc{oac}\xspace performs better than the two Oracular-CAL algorithms until a few hundred label queries,
but becomes worse afterwards.

To give a sense of the variation due to random permutation, we plot in Figure \ref{fig:rel-err-gain-single} average results on the first permutation
of each dataset, i.e., instead of taking the median in \eqref{eq:rel-err-gain}, we simply took results from the first permutation.
Figures \ref{fig:rel-err-gain} and \ref{fig:rel-err-gain-single} suggest that variation due to permuting the data is quite large,
especially for the two Oracular-CAL algorithms and \textsc{iwal}$_1$\xspace. Figure \ref{fig:rel-err-gain-quartiles} gives another view that shows variation for \textsc{oac}\xspace, \textsc{ora-iwal}$_0$\xspace, and \textsc{passive}\xspace:
in addition to the median improvement, we also plot error bars corresponding to the first and the third quartiles of the relative improvement over random permutations, i.e., \eqref{eq:rel-err-gain} with median replaced by the two quartiles, respectively.

\begin{figure}[t]
\centering
\subfigure[Median over permutations]{\label{fig:rel-err-gain-per-data-median}\includegraphics[width=0.33\textwidth,height=0.25\textwidth]{./fig/best_params_rel-err-gain_1.pdf}}
\subfigure[The first permutation]{\label{fig:rel-err-gain-per-data-single}\includegraphics[width=0.33\textwidth,height=0.25\textwidth]{./fig/best_params_rel-err-gain_2.pdf}}
\subfigure[Three quartiles over permutations]{\label{fig:rel-err-gain-per-data-quartiles}\includegraphics[width=0.33\textwidth,height=0.25\textwidth]{./fig/best_params_rel-err-gain_3.pdf}}
\caption{Relative improvement in test error v.s. number of label queries under the hyper-parameter settings optimized on a per dataset basis. Results are averaged over all datasets.}
\label{fig:rel-err-gain-per-data}
\end{figure}
In Figures \ref{fig:rel-err-gain-per-data-median} to \ref{fig:rel-err-gain-per-data-quartiles},
we plot results obtained by each algorithm $a$ using the best hyper-parameter setting for each dataset $d$:
\begin{equation}
p^*_d := \arg \max_{p} \; \underset{1 \leq j \leq 9}{\ensuremath{\mathrm{median}}} \left\{ \frac{\ensuremath{\mathrm{AUC}}_{base}(d,j) - \ensuremath{\mathrm{AUC}}_{a,p}(d,j)}{\ensuremath{\mathrm{AUC}}_{base}(d,j)} \right\}.
\end{equation}
As expected, all algorithms perform better by using the best hyper-parameter setting for each dataset.
Note that \textsc{oac}\xspace performs the best at small numbers of label queries, but
after a few hundred label queries all active learning algorithms perform quite similarly.
\begin{figure}[t]
\centering
\includegraphics[width=0.45\textwidth,height=0.34\textwidth]{./fig/titanic_best_params-rel-auc-gain_test_error_subset} \qquad
\includegraphics[width=0.45\textwidth,height=0.34\textwidth]{./fig/a9a_best_params-rel-auc-gain_test_error_subset}
\caption{Test error under the best hyper-parameter setting for each dataset v.s. number of label queries}
\label{fig:test-err-examples}
\end{figure}

Finally in Figure \ref{fig:test-err-examples}, we show the test error rates obtained by \textsc{oac}\xspace, \textsc{ora-iwal}$_0$\xspace, and \textsc{passive}\xspace
against number of label queries for 2 of the 22 datasets, using the best hyper-parameter setting for each dataset.
Results for all datasets and all algorithms are in Appendix \ref{appendix:results}.

In sum, when using the best fixed hyper-parameter setting, \textsc{ora-iwal}$_0$\xspace outperforms other active learning algorithms.
When using the best hyper-parameter setting tuned for each dataset, \textsc{oac}\xspace and \textsc{ora-iwal}$_0$\xspace
perform equally well and better than other algorithms.

\section{Analysis of generalization ability}
\label{proofs-regret}

In this section we present the main framework and analysis for the
results on the generalization properties of the \textsc{Active Cover}\xspace
algorithm. Our analysis is broken up into several steps. We start by
setting up some additional notation for the proofs. Our analysis
relies on two deviation bounds for the empirical regret and the
empirical error of the ERM classifier. These are obtained by
appropriately applying Freedman-style concentration bounds for
martingales. Both these bounds depend on the variance and range of our
error and regret estimates for all classifiers $h \in \H$, and these
quantities are controlled using the constraints~\eqref{eq:queryp}
and~(\ref{eq:minbndcons}) in the definition of the optimization
problem (\optprob). Since our data consists of examples from different
epochs, which use different query probabilities $P_\ensuremath{m}$, the above
steps with appropriate manipulations yield bounds for the epoch
$\ensuremath{m}$, in terms of various quantities involving the previous
epochs. Theorem~\ref{thm:regret} and its corollaries are then obtained
by setting up appropriate inductive claims. We make this intuition
precise in the following sections.

\subsection{Framework for generalization analysis}
\label{sec:regret-prelim}

Before we can prove our main results, we recall some notations and
introduce a few additional ones. We also prove some technical
lemmas in this section which are used to prove our main results.

Recall the notation $\mbox{reg}(h,h') := \mbox{err}(h) -
\mbox{err}(h'), h^* \in \arg \min_{h \in \mathcal{H}} \mbox{err}(h)$,
$\ensuremath{\mathrm{reg}}(h) := \ensuremath{\mathrm{reg}}(h,h^*)$. Let $Z_\ensuremath{m}$ denote the set of
importance-weighted examples in $\ensuremath{\tilde{Z}}_\ensuremath{m}$, and the corresponding
empirical error is denoted as:

\begin{equation}
\ensuremath{\mathrm{err}}(h,Z_\ensuremath{m}) := \frac{1}{\epend} \sum_{j=1}^\ensuremath{m}
\sum_{i=\epend[j-1]+1}^{\epend[j]} \Big(\frac{ Q_i
  \mathds{1}(h(X_i) \neq Y_i \wedge X_i \in D_j)}{P_j(X_i)}
\Big).
\label{eqn:labeled}
\end{equation}
Taking expectations, we define the following quantities with respect
to the sequence of regions $\{D_\ensuremath{m}\}$:

\begin{eqnarray}
  \ensuremath{\mathrm{err}}_\ensuremath{m}(h) &:=& \ensuremath{\mathbb{E}}_{X,Y}[\mathbbm{1}(h(X) \neq Y \wedge X \in
    D_\ensuremath{m})], \label{eq:err_epoch}\\
  \erravg{\ensuremath{m}}(h) &:=& \frac{1}{\epend}
  \sum_{j=1}^\ensuremath{m}(\epend[j] - \epend[j-1]) \ensuremath{\mathrm{err}}_j(h). \nonumber
\end{eqnarray}
Intuitively, $\ensuremath{\mathrm{err}}_\ensuremath{m}$ captures the population error of $h$,
restricted to only the examples in the disagreement region. This is
also the expectation of the sample error restricted to the
importance-weighted examples in epoch $\ensuremath{m}$. Averaging these
quantities, we obtain $\erravg{\ensuremath{m}}$ which is the expectation of
the sample error over $Z_\ensuremath{m}$. Centering around the corresponding
errors of $h^*$, we obtain the following regret terms:

\begin{eqnarray}
  \ensuremath{\mathrm{reg}}_\ensuremath{m}(h) &:=& \ensuremath{\mathrm{err}}_\ensuremath{m}(h) - \ensuremath{\mathrm{err}}_\ensuremath{m}(h^*), \nonumber\\
  \overline{\ensuremath{\mathrm{reg}}}_\ensuremath{m}(h) &:=& \frac{1}{\epend}
  \sum_{j=1}^\ensuremath{m} (\epend[j] - \epend[j-1]) \ensuremath{\mathrm{reg}}_j(h). \nonumber
\end{eqnarray}

While the above quantities only concern the importance-weighted
examples, it is also useful to measure error and regret terms over the
entire biased sample. We define the empirical error and regret on
$\tilde{Z}_\ensuremath{m}$ as follows:

\begin{align*}
\ensuremath{\mathrm{err}}(h,\tilde{Z}_\ensuremath{m})
& :=\frac{1}{\epend} \sum_{j=1}^\ensuremath{m}
\sum_{i=\epend[j-1]+1}^{\epend[j]} \Big(
\mathds{1}(h(X_i) \neq h_j(X_i) \wedge X_i \notin D_j)  + \frac{ Q_i
  \mathds{1}(h(X_i) \neq Y_i \wedge X_i \in D_j)}{P_j(X_i)}
\Big),\\
\ensuremath{\mathrm{reg}}(h,h',\tilde{Z}_\ensuremath{m}) & := \ensuremath{\mathrm{err}}(h,\tilde{Z}_\ensuremath{m}) -
\ensuremath{\mathrm{err}}(h',\tilde{Z}_\ensuremath{m}),
\end{align*}
and the associated expected regret:

\begin{eqnarray}
  \regbiasi{\ensuremath{m}}(h,h') & := & \mathbbm{E}_{X}[(\mathds{1}(h(X) \neq h_\ensuremath{m}(X)) -
    \mathds{1}(h'(X) \neq h_\ensuremath{m}(X)))\mathds{1}(X \notin D_\ensuremath{m})]
  +  \nonumber\\
  && \mathbbm{E}_{X,Y}[(\mathds{1}(h(X) \neq Y) - \mathds{1}(h'(X) \neq
    Y))\mathds{1}(X \in D_\ensuremath{m})], \label{eq:regbiasi}\\
  \regbias{\ensuremath{m}}(h,h') & := &  \frac{1}{\epend}\sum_{j=1}^\ensuremath{m}
  (\epend[j] - \epend[j-1]) \regbiasi{j}(h,h').
\label{eqn:regbias}
\end{eqnarray}
The
quantity $\regbias{\ensuremath{m}}(h,h')$ will play quite a central role in
our analysis as it is the expectation of the empirical regret of $h$
relative to $h'$ on our biased sample $\ensuremath{\tilde{Z}}_\ensuremath{m}$. We also recall
the earlier notations

\begin{eqnarray*}
  \Delta_{\ensuremath{m}} &:=& c_1 \sqrt{\epsilon_{\ensuremath{m}}
    \ensuremath{\mathrm{err}}(h_{\ensuremath{m}+1},\tilde{Z}_{\ensuremath{m}})} + c_2 \epsilon_{\ensuremath{m}} \log
  \epend, \nonumber\\
  A_{\ensuremath{m}+1} &:=& \{h \in \cH \mid \mbox{err}(h,\tilde{Z}_{\ensuremath{m}})  -
  \mbox{err}(h_{\ensuremath{m}+1},\tilde{Z}_{\ensuremath{m}}) \leq \gamma
  \Delta_{\ensuremath{m}}\}, \quad \mbox{and} \nonumber\\
    \Delta_{\ensuremath{m}}^* &:=&
  \begin{cases}
    \left( c_1 \sqrt{\epsilon_\ensuremath{m}
      \overline{\ensuremath{\mathrm{err}}}_\ensuremath{m}(h^*)} + c_2 \epsilon_\ensuremath{m}
    \log \epend \right), & \ensuremath{m} \geq 1. \nonumber\\
    \Delta_0, & m = 0.
  \end{cases}
\end{eqnarray*}

Unless stated otherwise, we adopt the convention that in the quantities
defined above, summations from $1$ to $m$
take the value of zero when $m = 0$.
We use the shorthand $\epochi$ to denote the epoch
containing example $i$.
We also sometimes use the shorthand $\ensuremath{\mathrm{reg}}(h,\ensuremath{\tilde{Z}}_{\ensuremath{m}}) :=
\ensuremath{\mathrm{reg}}(h,h_{\ensuremath{m}+1},\ensuremath{\tilde{Z}}_\ensuremath{m})$, $\regbiasi{\ensuremath{m}}(h) :=
\regbiasi{\ensuremath{m}}(h,h^*)$, and $\regbias{\ensuremath{m}}(h) :=
\regbias{\ensuremath{m}}(h,h^*)$.

With the notations in place, we start with an extremely important
lemma, which shows that the biased sample $\ensuremath{\tilde{Z}}$ which we create
introduces a bias in the favor of good hypotheses, overly penalizing
the bad hypotheses while favorably evaluating the optimal $h^*$.

\begin{lemma}[Favorable Bias]
\label{lemma:favorable_bias}
$\forall \ensuremath{m} \geq 1, \forall \bar{h} \in A_\ensuremath{m}, \forall h \in
\H$, the following holds:
\begin{equation*}
  \regbiasi{\ensuremath{m}}(h,\bar{h}) \geq \ensuremath{\mathrm{reg}}(h,\bar{h}).
\end{equation*}
\end{lemma}

The next key ingredient for our proofs is a deviation bound, which
will be appropriately used to control the deviation of the empirical
regret and error terms.

\begin{lemma}[Deviation Bounds]
  \label{lemma:reg_err_concen}
  Pick $0 < \delta < 1/e$ such that $|\mathcal{H}| / \delta > \sqrt{192}$.
  With probability at least $1 - \delta$ the following holds.
  For all $(h,h') \in \mathcal{H}^2$ and $\forall \ensuremath{m} \geq 1$,

  \begin{align}
    &|\regbias{\ensuremath{m}}(h,h') - \ensuremath{\mathrm{reg}}(h,h',\tilde{Z}_{\ensuremath{m}})| \nonumber\\
    &\qquad \leq \sqrt{\frac{\epsilon_{\ensuremath{m}}}{\epend} \sum_{i=1}^\ensuremath{m}
      (\epend[i] - \epend[i-1]) \ensuremath{\mathbb{E}}_X\left[ \left(\mathds{1}(X
        \notin D_i) + \frac{\mathbbm{1}(X \in D_i)}{P_i(X)}\right)
        \mathds{1}(h(X) \neq h'(X))\right]} \nonumber\\
    &\qquad \qquad +\frac{\epsilon_{\ensuremath{m}}}{P_{\min,\ensuremath{m}}},
    \label{eqn:dev-bias} \\
    &|\ensuremath{\mathrm{err}}(h,Z_\ensuremath{m}) - \erravg{\ensuremath{m}}(h)| \nonumber\\
    &\qquad \leq \sqrt{\frac{\epsilon_\ensuremath{m}}{\epend} \sum_{i=1}^\ensuremath{m}
      (\epend[i] - \epend[i-1]) \ensuremath{\mathbb{E}}_{X,Y}\left[
        \frac{\mathbbm{1}(X \in D_i \wedge h(X) \neq Y)}{P_i(X)}\right]}
  + \frac{\epsilon_\ensuremath{m}}{P_{\min,\ensuremath{m}}},
  \label{eq:dev-label}
  \end{align}
  where
  \begin{equation*}
    \epsilon_\ensuremath{m} \;:=\; 32 \left(\frac{\log(|\mathcal{H}|/\delta) +
      \log \epend}{\epend} \right).
  \end{equation*}
\end{lemma}

The lemma is obtained by applying a form of Freedman's inequality
presented in Appendix~\ref{sec:deviation}. Intuitively, the deviations
are small so long as the average importance weights over the
disagreement region and the minimum query probability over the
disagreement region are well-behaved. This lemma also highlights why
$\regbias{\ensuremath{m}}$ is a very natural quantity for our analysis, since
the empirical regret on our biased sample $\ensuremath{\tilde{Z}}$ concentrates around
it.

To keep the handling of probabilities simple, we assume for the bulk
of this section that the conclusions of
Lemma~\ref{lemma:reg_err_concen} hold deterministically. The failure
probability is handled once at the end to establish our main
results. Let $\ensuremath{\mathcal{E}}$ denote the event that the assertions of
Lemma~\ref{lemma:reg_err_concen} hold deterministically, and we know
that $\Pr(\ensuremath{\mathcal{E}}^C) \leq \delta$. Based on the above lemma, we obtain
the following propositions for the concentration of empirical regret
and error terms.

\begin{proposition}[Regret concentration]
  Fix an epoch $\ensuremath{m} \geq 1$. Suppose the event $\ensuremath{\mathcal{E}}$ holds and
  assume that $h^* \in A_j$ for all epochs $j \leq \ensuremath{m}$.
  \begin{align*}
    &|\ensuremath{\mathrm{reg}}(h, h^*, \ensuremath{\tilde{Z}}_\ensuremath{m}) - \regbias{\ensuremath{m}}(h, h^*)| \\
    &\qquad \leq
    \frac{1}{4} \regbias{\ensuremath{m}}(h) + 2\alpha
    \sqrt{\frac{\epsilon_\ensuremath{m}}{\epend} \sum_{i=1}^\ensuremath{m} (\epend[i]
      - \epend[i-1]) \regi{i}(h_i)} + 2\alpha
    \sqrt{3\erravg{\ensuremath{m}}(h^*) \epsilon_\ensuremath{m}}\\
    &\qquad \qquad + \beta \sqrt{2\gamma
      \epsilon_\ensuremath{m}\Delta_\ensuremath{m} \sum_{i=1}^\ensuremath{m} (\epend[i] -
      \epend[i-1]) (\ensuremath{\mathrm{reg}}(h, \ensuremath{\tilde{Z}}_{i-1}) + \ensuremath{\mathrm{reg}}(h^*, \ensuremath{\tilde{Z}}_{i-1}))} +
    4\Delta_\ensuremath{m}
  \end{align*}
  \label{prop:dev-regret-bias}
\end{proposition}

We need an analogous result for the empirical error of the ERM at each
epoch.

\begin{proposition}[Error concentration]
  Fix an epoch $\ensuremath{m} \geq 1$. Suppose the event $\ensuremath{\mathcal{E}}$ holds and
  assume that $h^* \in A_j$ for all epochs $j \leq \ensuremath{m}$.
  \begin{align*}
    |\erravg{\ensuremath{m}}(h^*) - \ensuremath{\mathrm{err}}(h_{\ensuremath{m}+1}, \ensuremath{\tilde{Z}}_\ensuremath{m})| \leq
    \frac{\erravg{\ensuremath{m}}(h^*)}{2} + \frac{3\Delta_\ensuremath{m}}{2} +
    \ensuremath{\mathrm{reg}}(h^*, h_{\ensuremath{m}+1}, \ensuremath{\tilde{Z}}_{\ensuremath{m}}).
  \end{align*}
  \label{prop:err-emp-best}
\end{proposition}

We now present the proofs of our main results based on these
propositions.

\subsection{Proofs of main results}
\label{sec:proofs-regret-main}

We prove a more general version of the
theorem. Theorem~\ref{thm:regret} and its corollaries follow as
consequences of this more general result.

\begin{theorem}
  For all epochs $\ensuremath{m} = 1, 2, \ldots, \ensuremath{M}$ and all $h \in \H$,
  the following holds with probability at least $1 - \delta$:
  \begin{eqnarray}
    |\ensuremath{\mathrm{reg}}(h, h^*, \ensuremath{\tilde{Z}}_\ensuremath{m}) - \regbias{\ensuremath{m}}(h, h^*)| &\leq&
    \frac{1}{2} \regbias{\ensuremath{m}}(h, h^*) +
    \frac{\ensuremath{\eta}}{4}\Delta_\ensuremath{m},
    \label{eqn:main-regret}\\
    \ensuremath{\mathrm{reg}}(h^*, h_{\ensuremath{m}+1}, \ensuremath{\tilde{Z}}_\ensuremath{m}) &\leq& \frac{\ensuremath{\eta}
      \Delta_\ensuremath{m}}{4}
      \quad \text{and} \quad h^* \in A_i,
    \label{eq:h_best-main}\\
|\erravg{\ensuremath{m}}(h^*) - \ensuremath{\mathrm{err}}(h_{\ensuremath{m}+1}, \ensuremath{\tilde{Z}}_\ensuremath{m})| &\leq&
\frac{\erravg{\ensuremath{m}}(h^*)}{2} + \frac{\ensuremath{\eta}}{2}\Delta_\ensuremath{m}.
\label{eq:err_dev}
  \end{eqnarray}
  \label{thm:main-regret}
\end{theorem}

The theorem is proved inductively. We first give the proof outline for
this theorem, and then show how Theorem~\ref{thm:regret} and its
corollaries follow.

\subsubsection{Proof of Theorem~\ref{thm:main-regret}}

The theorem is proved via induction. Let us start with the base
case for $\ensuremath{m}=1$. Clearly, $A_1 = \cH \ni h^*$, and
\begin{align*}
  |\ensuremath{\mathrm{reg}}(h, h^*, \ensuremath{\tilde{Z}}_1) - \regbias{1}(h,h^*)| \leq 1 \leq \ensuremath{\eta}
  \Delta_1 / 4,
\end{align*}
since $P_{\min,1} = 1$. The conclusions for the second and third
statements follow similarly. This establishes the base case. Let us
now assume that the hypothesis holds for $i = 1,2, \ldots, \ensuremath{m}-1$
and we establish it for the epoch $i = \ensuremath{m}$. We start from the
conclusion of Proposition~\ref{prop:dev-regret-bias}, which yields
\begin{align*}
 &|\ensuremath{\mathrm{reg}}(h, h^*, \ensuremath{\tilde{Z}}_\ensuremath{m}) - \regbias{\ensuremath{m}}(h, h^*)| \\
&\leq
  \frac{1}{4} \regbias{\ensuremath{m}}(h) + \underbrace{2\alpha
    \sqrt{\frac{\epsilon_\ensuremath{m}}{\epend} \sum_{i=1}^\ensuremath{m} (\epend[i]
      - \epend[i-1]) \regi{i}(h_i)}}_{\ensuremath{\mathcal{T}}_1} + \underbrace{2\alpha
      \sqrt{3\erravg{\ensuremath{m}}(h^*) \epsilon_\ensuremath{m}}}_{\ensuremath{\mathcal{T}}_2}\\
  & \qquad \qquad+ \underbrace{\beta
    \sqrt{2\gamma \epsilon_\ensuremath{m}\Delta_\ensuremath{m} \sum_{i=1}^\ensuremath{m}
      (\epend[i] - \epend[i-1]) (\ensuremath{\mathrm{reg}}(h, \ensuremath{\tilde{Z}}_{i-1}) + \ensuremath{\mathrm{reg}}(h^*,
      \ensuremath{\tilde{Z}}_{i-1}))}}_{\ensuremath{\mathcal{T}}_3} + 4\Delta_\ensuremath{m}
\end{align*}
We now control $\ensuremath{\mathcal{T}}_1$, $\ensuremath{\mathcal{T}}_2$ and $\ensuremath{\mathcal{T}}_3$ in the sum using our
inductive hypothesis and the propositions in a series of lemmas. To
state the lemmas cleanly, let $\ensuremath{\mathcal{E}}_\ensuremath{m}$ refer to the event where
the bounds~\eqref{eqn:main-regret}-\eqref{eq:err_dev} hold at epoch
$\ensuremath{m}$. Then we have the following lemmas. The first lemma gives a
bound on $\ensuremath{\mathcal{T}}_1$.

\begin{lemma}
  Suppose that the event $\ensuremath{\mathcal{E}}$ holds and that the events $\ensuremath{\mathcal{E}}_i$
  hold for all epochs $i = 1,2,\ldots, \ensuremath{m}-1$. Then we have

  \begin{align*}
    2\alpha \sqrt{\frac{\epsilon_\ensuremath{m}}{\epend} \sum_{i=1}^\ensuremath{m}
      (\epend[i] - \epend[i-1]) \regi{i}(h_i)} &\leq
    \frac{\ensuremath{\eta}\Delta_\ensuremath{m}}{12} + 24 \alpha^2 \epsilon_\ensuremath{m}
    \log \epend.
  \end{align*}
  \label{lemma:regret-t1}
\end{lemma}

Intuitively, the lemma holds since Lemma~\ref{lemma:favorable_bias}
allows us to bound $\regi{i}(h_i)$ with $\regbias{i-1}(h_i)$. The
latter is then controlled using the event $\ensuremath{\mathcal{E}}_i$. Some algebraic
manipulations then yield the lemma, with a detailed proofs in
Appendix~\ref{sec:regret-lemmas}. We next present a lemma that helps
us control $\ensuremath{\mathcal{T}}_2$.

\begin{lemma}
  Suppose that the event $\ensuremath{\mathcal{E}}$ holds and that the events $\ensuremath{\mathcal{E}}_i$
  hold for all epochs $i = 1,2,\ldots, \ensuremath{m}-1$. Then we have

  \begin{align*}
    2\alpha \sqrt{3\erravg{\ensuremath{m}}(h^*) \epsilon_\ensuremath{m}} &\leq 2\alpha
    \sqrt{6 \epsilon_\ensuremath{m} \ensuremath{\mathrm{err}}(h_{\ensuremath{m}+1}, \ensuremath{\tilde{Z}}_\ensuremath{m})} +
    \Delta_\ensuremath{m} + \frac{1}{4} \ensuremath{\mathrm{reg}}(h^*, h_{\ensuremath{m}+1}, \ensuremath{\tilde{Z}}_\ensuremath{m})
    + 33\alpha^2 \epsilon_\ensuremath{m}.
  \end{align*}
  \label{lemma:regret-t2}
\end{lemma}

The lemma follows more or less directly from
Proposition~\ref{prop:err-emp-best} combined with some
algebra. Finally, we present a lemma to bound $\ensuremath{\mathcal{T}}_3$.

\begin{lemma}
  Suppose that the event $\ensuremath{\mathcal{E}}$ holds and that the events $\ensuremath{\mathcal{E}}_i$
  hold for all epochs $i = 1,2,\ldots, \ensuremath{m}-1$. Then we have

  \begin{align*}
    \beta \sqrt{2\gamma \epsilon_\ensuremath{m}\Delta_\ensuremath{m} \sum_{i=1}^\ensuremath{m}
      (\epend[i] - \epend[i-1]) (\ensuremath{\mathrm{reg}}(h, \ensuremath{\tilde{Z}}_{i-1}) + \ensuremath{\mathrm{reg}}(h^*,
      \ensuremath{\tilde{Z}}_{i-1}))} &\leq \frac{1}{4} \regbias{\ensuremath{m}}(h,h^*) +
    \frac{7 \ensuremath{\eta} \Delta_\ensuremath{m} }{72} .
  \end{align*}
  \label{lemma:regret-t3}
\end{lemma}

The $\ensuremath{\mathrm{reg}}(h^*, h_i, \ensuremath{\tilde{Z}}_{i-1})$ terms in the lemma are bounded
directly due to the event $\ensuremath{\mathcal{E}}_i$. For the second term, we observe
that the empirical regret of $h$ relative to $h_i$ is not too
different from the empirical regret to $h^*$ (since $h^*$ has a small
empirical regret by $\ensuremath{\mathcal{E}}_i$). Furthermore, the empirical regret to
$h^*$ is close to $\regbias{i-1}(h, h^*)$ by the event
$\ensuremath{\mathcal{E}}_i$. These observations, along with some technical
manipulations yield the lemma.

Given these lemmas, we can now prove the theorem in a relatively
straightforward manner. Given our inductive hypothesis, the events
$\ensuremath{\mathcal{E}}_i$ indeed hold for all epochs $i = 1,2,\ldots, \ensuremath{m}-1$ which
allows us to invoke the lemmas. Substituting the above bounds on
$\ensuremath{\mathcal{T}}_1$ from Lemma~\ref{lemma:regret-t1}, $\ensuremath{\mathcal{T}}_2$ from
Lemma~\ref{lemma:regret-t2} and $\ensuremath{\mathcal{T}}_3$ from~\ref{lemma:regret-t3}
into Proposition~\ref{prop:dev-regret-bias} yields

\begin{align*}
  &|\ensuremath{\mathrm{reg}}(h, h^*, \ensuremath{\tilde{Z}}_\ensuremath{m}) - \regbias{\ensuremath{m}}(h, h^*)|\\
  &\leq \frac{1}{4} \regbias{\ensuremath{m}}(h) +
  \frac{\ensuremath{\eta}\Delta_\ensuremath{m}}{12} + 24 \alpha^2 \epsilon_\ensuremath{m} \log
  \epend + 2\alpha\sqrt{6\epsilon_\ensuremath{m} \ensuremath{\mathrm{err}}(h_{\ensuremath{m}+1},
    \ensuremath{\tilde{Z}}_\ensuremath{m})} + \Delta_\ensuremath{m} \\&\qquad \qquad + \frac{1}{4} \ensuremath{\mathrm{reg}}(h^*, h_{\ensuremath{m}+1},
  \ensuremath{\tilde{Z}}_\ensuremath{m}) + 33\alpha^2 \epsilon_\ensuremath{m} + \frac{1}{4}
  \regbias{\ensuremath{m}}(h, h^*) + \frac{7 \ensuremath{\eta} \Delta_\ensuremath{m}}{72} +
  4\Delta_\ensuremath{m}\\
  &\leq \frac{1}{2}\regbias{\ensuremath{m}}(h, h^*) +
  57\alpha^2\epsilon_\ensuremath{m}\log \epend +
  \frac{13 \ensuremath{\eta}}{72} \Delta_\ensuremath{m} +
  2\alpha\sqrt{6\epsilon_\ensuremath{m} \ensuremath{\mathrm{err}}(h_{\ensuremath{m}+1},
    \ensuremath{\tilde{Z}}_\ensuremath{m})} + 5\Delta_\ensuremath{m} \\&\qquad \qquad + \frac{1}{4} \ensuremath{\mathrm{reg}}(h^*,
  h_{\ensuremath{m}+1}, \ensuremath{\tilde{Z}}_\ensuremath{m})
\end{align*}
Further recalling that $c_1 \geq 2\alpha \sqrt{6}$ and $c_2 \geq
57\alpha^2$ by our assumptions on constants, we obtain

\begin{align}
  |\ensuremath{\mathrm{reg}}(h, h^*, \ensuremath{\tilde{Z}}_\ensuremath{m}) - \regbias{\ensuremath{m}}(h,h^*)| \leq
  \frac{1}{2}\regbias{\ensuremath{m}}(h, h^*) + \frac{13 \ensuremath{\eta}}{72}
  \Delta_\ensuremath{m} + 6\Delta_\ensuremath{m} + \frac{1}{4} \ensuremath{\mathrm{reg}}(h^*, h_{\ensuremath{m}+1},
  \ensuremath{\tilde{Z}}_\ensuremath{m}).
  \label{eqn:regret-dev-almost}
\end{align}
To complete the proof of the bound~(\ref{eqn:main-regret}), we now
substitute $h = h_{\ensuremath{m}+1}$ in the above bound, which yields

\begin{align*}
  \frac{1}{2}\regbias{\ensuremath{m}}(h_{\ensuremath{m}+1}, h^*) - \frac{5}{4}\ensuremath{\mathrm{reg}}(h,
  h^*, \ensuremath{\tilde{Z}}_\ensuremath{m}) \leq \frac{13 \ensuremath{\eta}}{72} \Delta_\ensuremath{m} +
  6\Delta_\ensuremath{m}.
\end{align*}
Since $h^* \in A_i$ for all epochs $i \leq \ensuremath{m}$, we have
$\regbias{\ensuremath{m}}(h, h^*) \geq \ensuremath{\mathrm{reg}}(h, h^*) \geq 0$ for all
classifiers $h \in \H$. Consequently, we see that

\begin{align}
  \ensuremath{\mathrm{reg}}(h^*, h_{\ensuremath{m}+1}, \ensuremath{\tilde{Z}}_m) = -\ensuremath{\mathrm{reg}}(h_{\ensuremath{m}+1}, h^*,
  \ensuremath{\tilde{Z}}_\ensuremath{m}) \leq \frac{52 \ensuremath{\eta}}{360} \Delta_\ensuremath{m} +
  \frac{24}{5}\Delta_\ensuremath{m} \leq \frac{\ensuremath{\eta}}{4} \Delta_\ensuremath{m},
  \label{eqn:emp-reg-opt}
\end{align}
where the last inequality uses the condition $38\ensuremath{\eta} \geq
1728$. We can now substitute this back into our earlier
bound~\eqref{eqn:regret-dev-almost} and obtain

\begin{align*}
  &|\ensuremath{\mathrm{reg}}(h, h^*, \ensuremath{\tilde{Z}}_\ensuremath{m}) - \regbias{\ensuremath{m}}(h,h^*)| \\
  &\qquad \qquad \leq
  \frac{1}{2}\regbias{\ensuremath{m}}(h, h^*) + \frac{13 \ensuremath{\eta}}{72}
  \Delta_\ensuremath{m} + 6\Delta_\ensuremath{m} + \frac{\ensuremath{\eta}}{16} \Delta_\ensuremath{m}
  \leq \frac{1}{2}\regbias{\ensuremath{m}}(h, h^*) + \frac{\ensuremath{\eta}}{4}
  \Delta_\ensuremath{m},
\end{align*}
where we use the condition $\ensuremath{\eta}/144 \geq 6$. This completes the
proof of the first part of our inductive claim.

For the second part, this is almost a by product of the first part
through Equation~\eqref{eqn:emp-reg-opt}. Recalling that $\gamma \geq
\ensuremath{\eta}/4$ by assumption, this ensures that $h^* \in A_{\ensuremath{m}+1}$.

We next establish the third part of the claim. This is obtained by
combining our bound~\eqref{eqn:emp-reg-opt} with
Proposition~\ref{prop:err-emp-best}. We have

\begin{align*}
  |\erravg{\ensuremath{m}}(h^*) - \ensuremath{\mathrm{err}}(h_{\ensuremath{m}+1}, \ensuremath{\tilde{Z}}_\ensuremath{m})| &\leq
  \frac{\erravg{\ensuremath{m}}(h^*)}{2} + \frac{3\Delta_\ensuremath{m}}{2} +
  \ensuremath{\mathrm{reg}}(h^*, h_{\ensuremath{m}+1}, \ensuremath{\tilde{Z}}_{\ensuremath{m}})\\
  &\leq \frac{\erravg{\ensuremath{m}}(h^*)}{2} + \frac{3\Delta_\ensuremath{m}}{2} +
  \frac{\ensuremath{\eta} \Delta_\ensuremath{m}}{4} \\
  &\leq \frac{\erravg{\ensuremath{m}}(h^*)}{2} + \frac{\ensuremath{\eta}
    \Delta_\ensuremath{m}}{2},
\end{align*}
since $\ensuremath{\eta} \geq 6$. This completes the third part.

Finally, note that our analysis has been conditioned on the event
$\ensuremath{\mathcal{E}}$ so far. By Lemma~\ref{lemma:reg_err_concen}, $\Pr(\ensuremath{\mathcal{E}}^C)
\leq \delta$, which completes the proof of the theorem.

We now provide a proof for Theorem~\ref{thm:regret}.

\subsubsection{Proof of Theorem~\ref{thm:regret}}
\label{sec:proof-thm-regret}

We only prove the first part of the theorem. The second part is simply
a restatement of the inequality~\eqref{eq:h_best-main} in
Theorem~\ref{thm:main-regret}. The first part is essentially a
restatement of~(\ref{eqn:main-regret}) in
Theorem~\ref{thm:main-regret}, except the bound uses $\Delta_\ensuremath{m}^*$
instead of $\Delta_\ensuremath{m}$. In order to prove the theorem, pick any
epoch $\ensuremath{m} \leq \ensuremath{M}$ and $h \in A_{\ensuremath{m}+1}$. Because $h^* \in
A_j, 1 \leq j \leq \ensuremath{m}+1$, we have by Lemma
\ref{lemma:favorable_bias} that
\begin{equation*}
  \ensuremath{\mathrm{reg}}(h) \leq \regbias{\ensuremath{m}}(h,h^*).
\end{equation*}
It then suffices to bound $\regbias{\ensuremath{m}}(h,h^*)$. By the deviation
bound \eqref{eqn:main-regret}, we have
\begin{align*}
  \regbias{\ensuremath{m}}(h, h^*) &\leq \ensuremath{\mathrm{reg}}(h, h^*, \ensuremath{\tilde{Z}}_\ensuremath{m}) +
  \frac{1}{2}\regbias{\ensuremath{m}}(h, h^*) +
  \frac{\ensuremath{\eta}}{4}\Delta_\ensuremath{m}\\
  &\leq \ensuremath{\mathrm{reg}}(h, h_{\ensuremath{m}+1}, \ensuremath{\tilde{Z}}_\ensuremath{m}) +
  \frac{1}{2}\regbias{\ensuremath{m}}(h, h^*) +
  \frac{\ensuremath{\eta}}{4}\Delta_\ensuremath{m} \\
  &\leq \frac{1}{2}\regbias{\ensuremath{m}}(h, h^*) + \left(\gamma +
  \frac{\ensuremath{\eta}}{4}\right)\Delta_\ensuremath{m}.
\end{align*}
Rearranging terms leads to
\begin{equation*}
  \regbias{\ensuremath{m}}(h,h^*) \leq 4 \gamma \Delta_\ensuremath{m}
\end{equation*}
because $ \gamma \geq \ensuremath{\eta} / 4$. Now we show that $\Delta_\ensuremath{m}
\leq 4 \Delta_\ensuremath{m}^*$, which leads to the desired result.  It is
trivially true for $\ensuremath{m} = 1$ because $\Delta_1^* = \Delta_1$. For
$\ensuremath{m} \geq 2$, by the deviation bound on the empirical error
\eqref{eq:err_dev} we have
\begin{eqnarray*}
  \Delta_\ensuremath{m} &\leq& c_1 \sqrt{\epsilon_\ensuremath{m} \left(\frac{3}{2}
    \erravg{\ensuremath{m}}(h^*) + \frac{\ensuremath{\eta}}{2} \Delta_\ensuremath{m}\right)} +
  c_2 \epsilon_\ensuremath{m} \log \epend\\
  &\leq& 2 c_1 \sqrt{\epsilon_\ensuremath{m} \erravg{\ensuremath{m}}(h^*)} +
  \sqrt{\frac{c_1^2 \epsilon_\ensuremath{m} \ensuremath{\eta}}{2}\Delta_\ensuremath{m}} + c_2
  \epsilon_\ensuremath{m} \log \epend\\
  &\leq& 2 c_1 \sqrt{\epsilon_\ensuremath{m} \erravg{\ensuremath{m}}(h^*)} +
  \frac{c_1^2 \epsilon_\ensuremath{m} \ensuremath{\eta}}{4} + \frac{\Delta_\ensuremath{m}}{2}
  + c_2 \epsilon_\ensuremath{m} \log \epend\\
  &\leq& 2 \Delta_\ensuremath{m}^* + \frac{\Delta_\ensuremath{m}}{2},
\end{eqnarray*}
where the last inequality uses our choice of constants $c_1^2
\ensuremath{\eta} / 4 \leq c_2$. Rearranging terms completes the proof.

\section{Conclusion}

In this paper, we proposed a new algorithm for agnostic active
learning in a streaming setting. The algorithm has strong theoretical
guarantees, maintaining good generalization properties while attaining
a low label complexity in favorable settings. Specifically, we show
that the algorithm has an optimal performance in a disagreement-based
analysis of label complexity, as well in special cases such as
realizable problems and under Tsybakov's low-noise
condition. Additionally, we present an interesting example that
highlights the structural difference between our algorithm and some
predecessors in terms of label complexities. Indeed a key improvement
of our algorithm is that we do not always need to query over the
entire disagreement region--a limitation of most computationally
efficient predecessors. This is achieved through a careful
construction of an optimization problem defining good query
probability functions, which relies on using refined data-dependent
error estimates.

We complement our theoretical analysis with an extensive empirical
evaluation of several approaches across a suite of 22 datasets. The
experiments show both the pros and cons of our proposed method, which
performs well when hyperparameter tuning is allowed, but suffers from
lack of robustness when we fix these hyperparameters across
datasets. Such a comprehensive empirical evaluation on a range of
diverse datasets has not been previously done for agnostic active
learning algorithms before to our knowledge, and is a key contribution
of this work.

We believe that our work naturally leads to several interesting
directions for future research. As the example in
Section~\ref{sec:example} reveals, the worst-case label complexity
analysis in Theorem~\ref{thm:label} is rather pessimistic. It would be
interesting to obtain sharper characterization of the label
complexity, by exploiting the structure of the query probability
function over the disagreement region. This would likely involve
understanding more fine-grained properties that make a problem easy or
hard for active learning beyond the disagreement coefficient, and such
a development might also lead to better algorithms. A limitation of
the current theory is the somewhat poor dependence in
Theorem~\ref{thm:optprob-unlabeled} on the number of unlabeled
examples needed to solve the optimization problem. Ideally, we would
like to be able to use $\ensuremath{\mathcal{O}}(\epend)$ unlabeled examples to solve
(\optprob) at epoch $\ensuremath{m}$, and improving this dependence is perhaps
the most important direction for future work. Finally, while \textsc{AC}\xspace is
extremely attractive from a theoretical standpoint, a direct
implementation still seems somewhat impractical. Obtaining theory for
an algorithm even closer to the practical variant \textsc{oac}\xspace would be an
important step in bringing the theory and implementation closer.

\section*{Acknowledgements}
The authors would like to thank Kamalika Chaudhuri for helpful
initial discussions.

\bibliographystyle{plainnat}

redpajama_set_name: RedPajamaArXiv