Active Minimax Forecasting

This is a continuation of my previous post where I noted that the Minimax Forecaster is tantalizing from an active learning perspective. Fortunately I noticed a paper by Abernethy et. al. called A Stochastic View of Optimal Regret through Minimax Duality. In this paper the authors unwrap online convex optimization in a general fashion by leveraging von Neumann's minimax theorem. By doing this they derive a general formula for the value of an online game to the adversary. The intuition of the previous post is that differences in game value between observing and not observing a particular outcome will be key to making active learning decisions in an adversarial setting, so this formula is very interesting.

Abernethy et. al. start out with a more general setup than the previous post, but I'll adapt their conventions to the previous post where there are differences. There is a game with $T$ rounds in it. There is a set $\mathcal{F}$ of experts. On each round, each expert $f$ produces a prediction $f_t$, player produces a prediction $p_t$, adversary simultaneously produces an outcome $y_t$, and player suffers an instantaneous loss $l (p_t, y_t)$. The experts are static (their predictions to do not depend upon previously observed outcomes), so essentially each expert is an sequence $f_{1:T}$. The player wants to generate a sequence of predictions $p_{1:T}$ which minimizes worst-case regret \[
\sup_{y_{1:T} \in \mathcal{Y}^T} L (p_{1:T}, y_{1:T}) - \inf_{f \in \mathcal{F}} L (f_{1:T}, y_{1:T}),
\] where $L (p_{1:T}, y_{1:T}) = \sum_s l (p_s, y_s)$ is the total loss. (To ease notation supremums and infimums will capture the entire rest of the expression unless explicitly limited by parenthesis.) The Minimax Forecaster of the previous post is an explicit solution to a specific case of this problem, whereas Abernethy et. al. are concerned with characterizing such games in general. They consider the value of the game to the adversary under optimal play, \[
\begin{aligned}
R^* (\mathcal{F}) &= \inf_{p_1 \in \mathcal{P}} \sup_{y_1 \in \mathcal{Y}} \ldots \inf_{p_T \in \mathcal{P}} \sup_{y_T \in \mathcal{Y}} \sum_{t=1}^T l (p_t, y_t) - \inf_{f \in \mathcal{F}} \sum_{t=1}^T l (f_t, y_t).
\end{aligned}
\] The amazing result is that this is the same as \[
\begin{aligned}
R^* (\mathcal{F}) &= \sup_{Y \in \mathbb{P} (\mathcal{Y}^T)} \mathbb{E}_{y_{1:T} \sim Y} \left[ \sum_{t=1}^T \inf_{p_t \in \mathcal{P}} \biggl( \mathbb{E}_{\tilde y_t} \left[ l (p_t, \tilde y_t) | y_{1:t-1} \right] \biggr) - \inf_{f \in \mathcal{F}} \sum_{t=1}^T l (f_t, y_t) \right],
\end{aligned}
\] where the supremum is over distributions of outcome sequences $\mathbb{P} (\mathcal{Y}^T)$. In other words, this looks like a game played with an oblivious (non-stationary) environment, but played in the worst possible environment. This is a nifty result, and leads in subsequent work to interpolating between the IID and adversarial settings by constraining the supremum over sequence distributions.

Now with active learning, we make the adversary more powerful by choosing not to observe some of the outcomes (represented by the variable $z_s \in \{ 0, 1 \}$). I can upper bound the game value to the adversary as \[
\begin{aligned}
R^* (\mathcal{F} | z_{1:T}) &\leq \sup_{Y \in \mathbb{P} (\mathcal{Y}^T)} \mathbb{E}_{y_{1:T} \sim Y} \left[ \sum_{t=1}^T \inf_{p_t \in \mathcal{P}} \biggl( \mathbb{E}_{\tilde y_t} \left[ l (p_t, \tilde y_t) | \Omega_{t-1} \right] \biggr) - \inf_{f \in \mathcal{F}} \sum_{t=1}^T l (f_t, y_t) \right],
\end{aligned}
\] where $\Omega_t = \{ y_s | s \leq t, z_s = 1 \}$ denotes observed outcomes. This is intuitively pleasing because the inner conditional expectation represents the player's knowledge. To derive the upper bound follow the procedure in Appendix A of the paper, after transforming the game value expression whenever $z_s = 0$ from \[
\inf_{p_1 \in \mathcal{P}} \sup_{y_1 \in \mathcal{Y}} \cdots \inf_{p_s \in \mathcal{P}} \sup_{y_s \in \mathcal{Y}} \cdots \inf_{p_T \in \mathcal{P}} \sup_{y_T \in \mathcal{Y}} \sum_{t=1}^T l (p_t, y_t) - \inf_{f \in \mathcal{F}} \sum_{t=1}^T l (f_t, y_t),
\] to \[
\inf_{p_1 \in \mathcal{P}} \sup_{y_1 \in \mathcal{Y}} \cdots \inf_{p_s \in \mathcal{P}} \cdots \inf_{p_T \in \mathcal{P}} \sup_{y_T \in \mathcal{Y}} \sup_{y_s \in \mathcal{Y}} \sum_{t=1}^T l (p_t, y_t) - \inf_{f \in \mathcal{F}} \sum_{t=1}^T l (f_t, y_t),
\] i.e., by letting the adversary defer selection of the unobserved values until the end of the game. This is just an upper bound because in reality the adversary has to chose the outcome for round $s$ on round $s$ so possibly I'm being too generous to the adversary.

Minimax Forecasting

If we design a Minimax Forecaster on the extensive form game associated with the bound, we get an algorithm which optimizes the bound. Consider the case where all outcomes are observed except for round $s$. Repeating the backward induction steps from the original minimax forecaster paper yields the expressions, \[
\begin{aligned}
p_t^* &= \frac{1}{2} \biggl( 1 - R^* (\mathcal{F}, y_{1:t-1}0 | z_s = 0) + R^* (\mathcal{F}, y_{1:t-1}1 | z_s = 0) \biggr). & (t > s)
\end{aligned}
\] and \[
\begin{aligned}
&R^* (\mathcal{F}, y_{1:t} | z_s = 0) \\
&= \frac{T - t}{2} + \mathbb{E}_{\sigma_{t+1:T}}\left[ \sup_{y_s \in \mathcal{Y}} |p_s - y_s| - \inf_{f \in \mathcal{F}} L (f_{1:T}, y_{1:t} \sigma_{t+1:T}) \right] & (t > s) \\
&= R^* (\mathcal{F}, y_{1:t}) \\
&\quad + \mathbb{E}_{\sigma_{t+1:T}}\left[ \left| p_s - \frac{1}{2} \left(1 + \inf_{f \in \mathcal{F}} \left( L (f_{1:T}, y_{1:s-1} 0 \sigma_{s+1:T}) \right) - \inf_{f \in \mathcal{F}} \left( L (f_{1:T}, y_{1:s-1} 1 \sigma_{s+1:T}) \right) \right) \right| \right].
\end{aligned}
\] Thus the residual game value having played $p_s$ and not observed outcome $s$ is equal to the fully observed residual game value plus a penalty related to expected absolute loss averaged over all Rademacher distributed playouts. This implies the optimal choice of $p_s$ is a median \[
\begin{aligned}
p_s^* &= \mathop{\operatorname{median}} \left( \frac{1}{2} \left( 1 + \inf_{f \in \mathcal{F}} \left( L (f_{1:T}, y_{1:s-1} 0 \sigma_{s+1:T}) \right) - \inf_{f \in \mathcal{F}} \left( L (f_{1:T}, y_{1:s-1} 1 \sigma_{s+1:T}) \right) \right) \right).
\end{aligned}
\] In the case where there are no additional rounds of play between $s$ and $T$, there is only one point in the distribution so the median is that point, so the optimal play $p_s^*$ is the same as in the fully observed case. In the case where there is one additional round of play between $s$ and $T$, there are two points in the distribution so the mean is a median, and again the optimal play $p_s^*$ is the same as in the fully observed game (consistent with the previous blog post). In the case of more than one additional round of play between $s$ and $T$, the mean is not necessarily a median (i.e., does not necessary minimize expected absolute loss) so optimal play $p_s^*$ is different. Maybe this is why Mathematica ``pooped out'' when I tried to solve a longer version of the unobserved game.

Once we've ``hopped over'' the unobserved point and determined $p_s^*$, we can continue the backwards induction; but I think the interesting bit is the penalty term, which says what the value of observing the outcome on round $s$ given all previous and subsequent rounds will be observed, \[
\mathbb{E}_{\sigma_{t+1:T}}\left[ \left| p_s - \frac{1}{2} \left(1 + \inf_{f \in \mathcal{F}} \left( L (f_{1:T}, y_{1:s-1} 0 \sigma_{s+1:T}) \right) - \inf_{f \in \mathcal{F}} \left( L (f_{1:T}, y_{1:s-1} 1 \sigma_{s+1:T}) \right) \right) \right| \right].
\] This penalty term would be important for deciding whether or not to query the outcome on round $s$. It'd be nice to generalize it to the case where some of the previous outcomes are not observed and also with respect to potentially unobserved future outcomes. Of course, planning the latter might be exponentially difficult.

For this to be practical, it would be nice if medians and expected absolute losses could be cheaply and accurately estimated, e.g., using random playouts. Also perhaps deciding whether to query the outcome needs to be done on a game value bound, e.g., assuming all subsequent observations will be observed rather than taking into account future decisions to observe the outcome. Furthermore, the technique is still fundamentally transductive since the expert predictions for the planning horizon $f_{1:T}$ need to be known. Even with all those caveats, however, there might be an interesting application for this, e.g., in recommendation systems.

The Minimax Forecaster and Transductive Active Learning

I've been making my way down the NIPS 2011 paper list, and found this nice paper Efficient Online Learning via Randomized Rounding by Cesa-Bianchi and Shamir. This paper is about improving and extending the Minimax Forecaster which is described in Prediction, Learning, and Games. (I own a copy but I confess to not having made it very far into that book.) The Minimax Forecaster uses a different strategy for online learning than mirror descent which is essentially what I (and everybody else?) use everyday. This different setting provides an opportunity to think about adversarial active learning.

Here's the basic setup. There is a game with $T$ rounds in it. There is a set $\mathcal{F}$ of experts. On each round, each expert $f$ produces a prediction $f_t$, player produces a prediction $p_t$, adversary simultaneously produces an outcome $y_t$, and player suffers an instantaneous loss $l (p_t, y_t)$. The experts are static (their predictions to do not depend upon previously observed outcomes), so essentially each expert is an sequence $f_{1:T}$. The player wants to generate a sequence of predictions $p_{1:T}$ which minimizes worst-case regret \[
\sup_{y_{1:T} \in \mathcal{Y}^T} \biggl( L (p_{1:T}, y_{1:T}) - \inf_{f \in \mathcal{F}} L (f_{1:T}, y_{1:T}) \biggr),
\] where $L (p_{1:T}, y_{1:T}) = \sum_s l (p_s, y_s)$ is the total loss. When the observations are binary $\mathcal{Y} = \{ 0, 1 \}$, then an instantaneous loss of $|p_t - y_t|$ corresponds to expected 0-1 loss when the player is randomizing decisions. Amazingly this case yields a closed-form expression for the optimal prediction \[
\begin{aligned}
p^*_t &= \frac{1}{2} \biggl( 1 + R^* (\mathcal{F}, y_{1:t-1}1) - R^* (\mathcal{F}, y_{1:t-1}0) \biggr) \\
&= \frac{1}{2} \biggl( 1 + \mathbb{E}_{\sigma_{t+1:T}} \left[ \inf_{f \in \mathcal{F}} L (f_{1:T}, y_{1:t-1} 0 \sigma_{t+1:T}) - \inf_{f \in \mathcal{F}} L (f_{1:T}, y_{1:t-1} 1 \sigma_{t+1:T}) \right] \biggr),
\end{aligned}
\] where temporal sequence concatenation is denoted lexically, $\sigma_t$ is $\mathrm{Bournelli}(1/2)$ distributed a la Rademacher averages, and $R^* (\mathcal{F}, y_{1:t})$ is the residual game value after some rounds of play, \[
\begin{aligned}
R^* (\mathcal{F}, y_{1:t}) &= \frac{1}{2} \biggl( 1 + R^* (\mathcal{F}, y_{1:t-1}0) + R^* (\mathcal{F}, y_{1:t-1}1) \biggr) \\
&= \frac{T - t}{2} - \mathbb{E}_{\sigma_{t+1:T}}\left[ \inf_{f \in \mathcal{F}} L (f_{1:T}, y_{1:t} \sigma_{t+1:T}) \right].
\end{aligned}
\] Essentially what's happening here is that player is able to make adversary indifferent to playing either option on each round by playing a constant plus the difference between the residual game values associated with playing each option; this causes the residual game value to be a constant plus the average value of continuing after playing each option. Unwrapping the game value recursively leads to the Rademacher style averages. One observation of the paper is that such expectations can be approximated by sampling to achieve a high probability regret bound, aka random playout.

In practice even to do random playout you need to know $f_{1:T}$ for the various experts. When mapping this to a contextual prediction setting, this corresponds to knowing the sequence of features in advance (but not the labels). Thus this is essentially a transductive technique. Some recommendation problems are naturally transductive, and the paper discusses an application to collaborative filtering.

Active Learning?

In principle the setup can be modified to consider active learning. Each round, in addition to generating a prediction, player must make a decision $z_t \in \{ 0, 1 \}$ whether or not to observe $y_t$. If $z_t = 0$, player cannot use the value of $y_t$ in subsequent predictions. Since it is always better for the player to observe $y_t$, there has to be some penalty for doing so, thus consider a constant penalty $\alpha$ per observation. The player wants to generate a sequence of predictions $p_{1:T}$ and queries $z_{1:T}$ which minimizes worst-case regret \[\sup_{y_{1:T} \in \mathcal{Y}^T} \biggl( \sum_s \alpha z_s + L (p_{1:T}, y_{1:T}) - \inf_{f \in \mathcal{F}} L (f_{1:T}, y_{1:T}) \biggr).
\] Concise general closed-form expressions have eluded me thus far, but there is a non-trivial case which yields nice answers: the two-round game.

It never makes sense to observe the final outcome $y_T$, so $z_T = 0$. In the two-round game, then, the question is whether to observe $y_1$. If $y_1$ is not observed (i.e., $z_1 = 0$), player must ballistically plan both predictions without intermediate feedback, \[
\begin{aligned}
(p_1^*, p_2^*) &= \mathop{\operatorname{arg\,inf}}\limits_{p_{1:2} \in \mathcal{P}^2} \sup_{y_{1:2} \in \mathcal{Y}^2} \left( |p_1 - y_1| + |p_2 - y_2| - \inf_{f \in \mathcal{F}} L (f_{1:2}, y_{1:2}) \right).
\end{aligned}
\] This can be solved with Mathematica: here's the incantation.

Minimize[{ z, 
           p1 + p2 - inf00 <= z, 
           p1 + (1 - p2) - inf01 <= z, 
           (1 - p1) + p2 - inf10 <= z, 
           (1 - p1) + (1 - p2) - inf11 <= z }, 
           { p1, p2, z }] // Simplify

This has solution \[
\begin{aligned}
p_1^* &= \frac{1}{2} \left( 1 + \frac{1}{2} \sum_{y_2=0}^1 \left( \inf_{f \in \mathcal{F}} L (f_{1:2}, 0y_2) - \inf_{f \in \mathcal{F}} L (f_{1:2}, 1y_2) \right) \right) & (z_1 = 0), \\
p_2^* &= \frac{1}{2} \left(1 + \frac{1}{2} \sum_{y_1=0}^1 \left( \inf_{f \in \mathcal{F}} L (f_{1:2}, y_10) - \inf_{f \in \mathcal{F}} L (f_{1:2}, y_11) \right) \right) & (z_1 = 0),
\end{aligned}
\] with game value \[
\begin{aligned}
&R (\mathcal{F}, \emptyset | z_1 = 0) \\
&= 1 - \frac{1}{2} \min\left\{ \inf_{f \in \mathcal{F}} L (f_{1:2}, 00) + \inf_{f \in \mathcal{F}} L (f_{1:2}, 11), \inf_{f \in \mathcal{F}} L (f_{1:2}, 01) + \inf_{f \in \mathcal{F}} L (f_{1:2}, 10) \right\}. \\
\end{aligned}
\] Now compare this to the case of $z_1 = 1$, which is the same as the fully observed Minimax Forecaster. \[
\begin{aligned}
p_1^* &= \frac{1}{2} \left( 1 + \frac{1}{2} \sum_{y_2=0}^1 \left( \inf_{f \in \mathcal{F}} L (f_{1:2}, 0y_2) - \inf_{f \in \mathcal{F}} L (f_{1:2}, 1y_2) \right) \right) & (z_1 = 1), \\
p_2^* &= \frac{1}{2} \left(1 + \inf_{f \in \mathcal{F}} L (f_{1:2}, y_10) - \inf_{f \in \mathcal{F}} L (f_{1:2}, y_11) \right) & (z_1 = 1).
\end{aligned}
\] The first round prediction $p_1^*$ is the same whether or not $z_1 = 0$ or $z_1 = 1$, but the second round prediction $p_2^*$ is different. If $z_1 = 0$, then $p_2^*$ is computed by averaging over possible histories; whereas if $z_1 = 1$, then $p_2^*$ is computing using the actual observed history. (Aside: perhaps constant-time Radacher averages will be quantum computing's killer app.)

To decide whether to observe $y_1$ or not, we need to know how much better it is to do so, i.e., the difference in game values. When $z_1=1$ this is the same as the fully observed Minimax Forecaster, \[
\begin{aligned}
&R (\mathcal{F}, \emptyset | z_1 = 1) \\
&= 1 - \frac{1}{4} \left( \inf_{f \in \mathcal{F}} L (f_{1:T}, 00) + \inf_{f \in \mathcal{F}} L (f_{1:T}, 01) + \inf_{f \in \mathcal{F}} L (f_{1:T}, 10) + \inf_{f \in \mathcal{F}} L (f_{1:T}, 11) \right),
\end{aligned}
\] therefore the difference in game value is \[
\begin{aligned}
&R^* (\mathcal{F}, \emptyset | z_t = 0) - R^* (\mathcal{F}, \emptyset | z_t = 1) \\
&= \frac{1}{4} \left| \inf_{f \in \mathcal{F}} L (f_{1:2}, 00) - \inf_{f \in \mathcal{F}} L (f_{1:2}, 01) - \left( \inf_{f \in \mathcal{F}} L (f_{1:2}, 10) - \inf_{f \in \mathcal{F}} L (f_{1:2}, 11) \right) \right|. \\
\end{aligned}
\] This looks like a difference of future differences. If the game value difference exceeds $\alpha$, then we should decide $z_1 = 1$, otherwise not. So, for instance, if every expert predicts the same value on the first round, then the difference of future differences will be zero and we should not observe $y_1$. That certainly sounds like active learning.

So what should a general case $T$ round solution look like? Intuitively, one would hope that if all the experts that have done well in the past predict the same thing on the current instance, that the value of observing $y_t$ for that instance would go down. That is roughly what agnostic active learning does in the IID setting. Here the future is also important, but analogously if all the experts that are in the running for the infimum at the end of the horizon agree on a value, it should be that observing $y_t$ has less value. As we near to the end of the planning horizon, that will be driven mostly by having done well in the past.

Selective Classification and Active Learning

There's a gem of a paper by El-Yaniv and Wiener called Agnostic Selective Classification. The punchline of this paper is that selective classification is the test-time analog to active learning.

In selective classification, a classifier has the option of rejecting the input and abstaining from predicting. The idea is reject rarely while achieving high classification accuracy. This is multi-objective optimization, so the concept of a Pareto frontier arises, known as the risk-coverage curve in this context.

This can be formalized as follows: a selective classifier is a pair $(h, g)$ of functions $g: X \to \{ 0, 1 \}$ and $h: X \to Y$, where $g$ indicates whether or not to reject the input and $h$ is the classification rule if the input is accepted, \[
(h, g) (x) = \begin{cases} \mathrm{reject} & \mathrm{if}\; g (x) = 0, \\ h (x) & \mathrm{otherwise} \end{cases}.
\] The hypotheses $h$ come from a set $\mathcal{H}$; the paper is less clear on what set we are competing with for $g$, but they end up with a weaker notion of optimality so it doesn't matter. The features $X$ and labels $Y = \{ 0, 1 \}$ are jointly distributed according to $D$. In the passive batch setting, somebody hands us a bag of data sampled i.i.d. from $D$ and a rejection budget $b$, and then we have to produce a pair $(h, g)$ which is ideally near the Pareto frontier, \[
\begin{aligned}
\mathop{\operatorname{arg\,min\,}}\limits_{h \in \mathcal{H}} \mathbb{E}_{(x, y) \sim D}&[ 1_{g (x) = 1} 1_{h (x) \neq y}] \\
&\mathrm{s.t.} \\
E_{(x ,y) \sim D}&[1_{g (x) = 1}] \leq b.
\end{aligned}
\] This is really hard so El-Yaniv and Wiener consider a different problem. Let $h^* = \mathop{\operatorname{arg\,min\,}}_{h \in \mathcal{H}} \mathbb{E}_{(x, y) \sim D}[ 1_{h (x) \neq y}]$ be an optimal classifier. A pair $(h, g)$ is called a weakly optimal if \[
\mathbb{E}_{(x, y) \sim D}[ 1_{g (x) = 1} 1_{h (x) \neq y}] \leq \mathbb{E}_{(x, y) \sim D}[ 1_{g (x) = 1} 1_{h^* (x) \neq y}],
\] i.e., in the region of the input space where the selective classifier accepts, it does at least as well as an optimal hypothesis. This is not as good as the being on the Pareto frontier, but it's better than a sharp stick in the eye!

Now for the nifty part. The authors show that a weakly optimal selective classifier can (with high probability) be constructed as follows. Let $\tilde h$ be the minimizer of empirical risk $R (h)$, and define the empirically disagreeing hypothesis at $x$ via \[
h'_x \doteq \mathop{\operatorname{arg\,min\,}}\limits_{\substack{h \in \mathcal{H}, h (x) \neq \tilde h (x)}} R (h).
\] Then the disbelief index is the difference in empirical risk $R (h'_x) - R (\tilde h)$, and the selective classifier $(g, \tilde h)$ defined by \[
g (x) = 0 \iff R (\tilde h_x) - R (\tilde h) \leq \Delta
\] is weakly optimal, where $\Delta$ is a function of the training set size, VC dimension of $\mathcal{H}$, and probability bound $\delta$. In other words, refuse to classify the input if it is not empirically expensive to disagree with the empirical minimizer at the current input, otherwise classify according to the empirical minimizer.

If this looks familiar, it's because the disbelief index is the same quantity that arises in AALwC when deciding the probability of querying the label. This establishes a pleasant correspondence between ``asking for the label'' when training and ``refusing to predict'' when testing.

It also indicates that Vowpal Wabbit can easily be used as a selective classifier, since it already computes a fast approximation to the disbelief index for active learning purposes.

Active Learning with a Drifting Distribution

We now have a good idea how to do agnostic active learning in the IID setting.  In between the IID setting and the fully adversarial setting, there is the situation where the environment is changing over time but is oblivious to our learning algorithm.   This is the topic of a recent paper by Liu Yang called Active Learning with a Drifting Distribution.

Passive Learning with a Drifting Distribution

I wasn't sufficiently familiar with passive learning with a drifting distribution, so I had to spend some time with one of the citations: On the Complexity of Learning from Drifting Distributions by Barve and Long.

In passive learning in the IID setting we can get arbitrarily good estimates of true expectations via empirical averages. This means for hypothesis sets of finite VC dimension that with high probability we can get arbitrarily close to optimal with enough data.

Once the world is allowed to start changing over time, we may or may not have enough information to track the changes.  There are multiple modeling choices here to formally characterize how the world drifts, including infrequent large changes, and possibly large changes with a slowly changing direction and rate.  Barve and Long study the case that the world changes slowly.  In particular, the world generates a countable sequence of training data consisting of feature label pairs $(X \times Y)^{\mathbb{N}}$.  These samples are independent but not identically distributed, and $D_t$ denotes the distribution of $(x_t, y_t)$.  The $D_t$ are constrained via the total variation distance \[
\sup_U |D_t (U) - D_{t+1} (U)| \leq \gamma,
\] where $U$ ranges over all measurable events, i.e., for anything to which you can assign a probability, consecutive distributions $D_t$ and $D_{t+1}$ will differ in the probability they assign by at most $\gamma$.   In this scenario, if the world wants to change significantly it has to supply us with training data associated with intermediate states, so the learning algorithm can succeed. Barve and Long show a sufficient condition for agnostic learning is \[
\gamma = O \bigl( \frac{\epsilon^3}{d \ln (1 / \epsilon)} \bigr).
\] where $d$ is the VC dimension of the hypothesis set and $\epsilon$ is our target regret.  This is achieved by doing ERM on a window of the most recent examples, where the window size is determined by $\epsilon$ and $\gamma$.  Since regret at time $t$ is relative to $D_t$, this is a really cool result.  Note the joint distribution of $X$ and $Y$ is allowed to change over time, so both the distribution of input features and the  conditional label density (``concept'') are changing.

Unfortunately this result says that we cannot get arbitrarily accurate with unlimited data.  In hindsight this is not surprising since we only use recent history for our ERM even with unlimited data.  An accompanying necessary condition without the $\ln (1 / \epsilon)$ term in the denominator indicates this limitation is fundamental, and not merely an artifact of the ``windowed ERM'' strategy.

Back to Active Learning

Returning to Liu Yang, the first observation is that the above assumption of ``slow drift'' is not powerful enough for active learning.  In active learning, we want to throw away some (most!) of the labels, which is equivalent to speeding up the world (scaling $\gamma$).  In particular, if we want to get invited to the VIP section of the Active Learning Club, we'd really like a sub-linear label complexity, which would be like passive learning with $\gamma \to \infty$, and we've seen above that means essentially no accuracy.  (However, since linear label complexity is the worst-case lower bound for agnostic active learning in the IID case, the above ``slow drift'' condition might still be worth investigating.)

Yang instead assumes that the various $D_t$ are drawn from a set of distributions $\mathbb{D}$ that are all close to each other.  This is formalized via the minimal $\epsilon$-cover $\mathbb{D}_{\epsilon}$ of $\mathbb{D}$, defined as the smallest subset of $\mathbb{D}$ which is within $\epsilon$ of any member of $\mathbb{D}$, as measured by the total variation distance.  In particular Yang assumes $\forall \epsilon > 0, |\mathbb{D}_{\epsilon}| < \infty$, and gets more precise bounds by assuming $\forall \epsilon > 0, |\mathbb{D}_\epsilon| < c \cdot \epsilon^{-m}$ for some constants $c, m \in [0, \infty)$.

Essentially, instead of being allowed to change arbitrarily over time, Yang confines the world to bounce around inside a region of distribution space characterized by a finite set of prototype distributions.  To achieve a certain level of accuracy, we need only consider the world shifting between the prototype distributions, which in turn suggests that under suitable conditions we will eventually have accumulated enough information that we can forgo looking at some of the labels.

Yang further restricts the conditional distribution of labels given features to be fixed, and only allows the distribution of features to change over time.  This second assumption means that it is meaningful to talk about the realizable case, and in the realizable case an algorithm called CAL achieves a sublinear mistake bound and label complexity in this kind of drifting environment, if the (largest) disagreement coefficient is sufficiently small.  The quick summary of CAL is that it only queries the label if there is a empirically perfect hypothesis which predicts each label; otherwise it infers the unobserved label is the label that is associated with the remaining empirically perfect hypotheses.  CAL uses the entire history, but leverages realizability to succeed, and note the conditional distribution (and therefore realizability) is constant here.

Extending the realizable analysis, Yang next considers the strictly benign noise case, defined as there being an optimal hypothesis which is always conditionally more likely to be correct than incorrect (for all distributions in $\mathbb{D}$).  In this case an agnostic variant of CAL called ACAL achieves a sub-linear mistake bound and label complexity.  Like CAL, ACAL will infer labels, but does so via an error difference instead of demanding empirical perfection.  In Yang's paper ACAL uses windowed data where periodically all history is discarded and the window size is increased geometrically, but this is not due to drift; rather is it due to the online setting with an unbounded stream, because standard specifications of ACAL assume a particular label budget.  Therefore ACAL is effectively using ``all the data''.

Some Takeaways

This paper (and the discussed citation) helped me appreciate that active learning in changing environments will only be ``efficient'' (from a label complexity standpoint) if the environment is somehow globally constrained in how it can change.

One research strategy, exemplified by this paper, is to take an existing active learning algorithm for the IID case and adapt it to some model of world drift.  Of course I'd like to see AALwC manhandled in this fashion: easier said than done!  A mashup of AALwC with Barve and Long would suggest running AALwC over the most recent window of data and not incrementing the label counter once the window is full.  This would have linear label complexity but sometimes constant factors matter (like on my Mechanical Turk invoices!).  It's less clear to me what should happen if AALwC is to be used under the stricter Yang assumptions of world drift.  The fact that ACAL is essentially using all the historical data suggests that AALwC might work under these conditions by merely slowing the schedule associated with decreasing the query probability.

A different research strategy would be to understand active learning in the adversarial setting and then apply different online to batch scenarios to convert a retrospective guarantee into multiple prospective guarantees.  That approach holds the promise of yielding a single algorithm that does as well as possible under a variety of different world drift scenarios.  If somebody achieves that, they will be justifiably famous!

Active Learning and Contextual Bandits

Now that active learning is increasingly well understood, contextual bandits (CB) are a natural next focus of attention. My understanding of the current state of the art for stochastic CB is the following:

1. We have computationally viable algorithms that can empirically perform well (e.g., Thompson sampling), but which do not provide strong agnostic theoretical guarantees. (That's a nice way of saying YMMV).
2. We have algorithms that provide strong agnostic theoretical guarantees (e.g., Policy Elimination), but which are not computationally viable.

Progress here would be of more than theoretical interest: the stochastic CB setting describes a large number of problems I've attempted to solve over the years.

So I recently (naively?) thought ``hey, active learning algorithms are really good, and they are making a decision akin to explore/exploit, so maybe I can leverage that for a stochastic CB solution.'' It turns out this is not a good idea, but understanding why is interesting.

For illustration, consider a 2-armed contextual bandit with binary rewards (note: expected reward conditioned on the context is not necessarily binary; merely any particular realization of rewards is binary). In this case there is a natural correspondence between binary classifiers and stochastic CB policies. That suggests the following reduction of 2-armed stochastic CB to binary active learning.

Algorithm:Active Learning Stochastic Bandit

Two-armed contextual bandit algorithm leveraging active learning binary oracle $\mathcal{O}$.

1. Obtain context $X_k$.
2. Pass context $X_k$ as unlabeled data to $\mathcal{O}$, and receive the decision $Q_k \in \{ 0, 1 \}$ to query the label and predicted class $\hat Y_k \in \{ 0, 1 \}$.
3. If $Q_k = 0$, pull arm $\hat Y_k$ and receive reward $R_{\hat Y_k} \in \{ 0, 1 \}$.
4. If $Q_k = 1$,
1. Choose $A_k \in \{ 0, 1 \}$ with equal probability (i.e., 50-50).
2. Pull arm $A_k$ and observe reward $R_{A_k} \in \{ 0, 1 \}$.
3. Let \[
   Y_k := \begin{cases} A_k & R_{A_k} = 1 \\ 1 - A_k & R_{A_k} = 0 \end{cases}.
   \]
4. Pass $(X_k, Y_k)$ to $\mathcal{O}$ as is expected when $Q_k=1$.

The basic idea is the following: when the active learning algorithm requests the label, ``explore'' by randomizing the action; when the active learning algorithm does not request the label, ``exploit'' by performing the action that the underlying classifier wants. Problem solved!

Of course, not really. Let's analyze the algorithm. First, convince yourself that 0-1 classification loss on the data presented to the underlying oracle is proportional to the loss of the policy defined by the underlying classifier. Since active learning algorithms learn at essentially the same rate as passive learning algorithms (but without consuming all the labels), this means the ``exploitation policy'' will have an instantaneous regret of $O (\sqrt{\log(T) / T})$. However, in contextual bandits, it's the regret of the policy induced by the learning algorithm that matters. When the active learning algorithm requests the label, the regret is $O (1)$, and due to label complexity lower bounds for agnostic active learning, the label can be requested a constant fraction of the time; this implies the worst-case instantaneous regret of the policy induced by the learning algorithm is $O (1)$. That kind of regret bound is not going to you make you popular at the kind of parties where contextual bandit theory buffs hang out.

Now maybe in practice leveraging active learning for stochastic CB actually works well; certainly, if a suitable low-noise assumption is made, the label complexity of the active learning algorithm can be bounded and the overall regret can be made to look respectable. However this puts us back into the ``computationally viable heuristic'' zone, not the ``holy grail of agnostic stochastic CB algorithms'' zone.

Here's what's extra interesting: active learning appears fundamentally more difficult than stochastic CB. I say this because the label complexity lower bound problem does not plague direct solutions to stochastic CB. The amazing result from Dudik et. al. is that it is always possible to achieve $O (\sqrt{\log (T) / T})$ regret for the policy induced by the learning algorithm. Currently it is an open question how to do this in a computationally efficient manner, but already we can say the following: there is a big difference between having to choose whether to receive any reward information (active learning) versus being forced to only receive reward information about the action chosen (contextual bandits). In terms of the algorithm presented above, the problem is that anytime $Q_k = 0$, we ``throw away'' information; and leveraging that information is the difference between a constant worst-case instantaneous regret versus a worst-case instantaneous regret that decays over time.

Much thanks to John Langford for patiently explaining this to me. Now, I'm obsessed with contextual bandits! So far, naturally, my attempts to achieve $O (\sqrt{\log (T) / T})$ regret in the agnostic setting have not panned out, but it is really great fun.

Cost-Sensitive Binary Classification and Active Learning

Now that there are multiple active learning algorithms for binary classification popping up, it's a good time to ask what machine learning reductions can say about active learning for other types of learning problems. Right now I'll focus on cost-sensitive binary classification, for which the goal is to compete with \[
h^* = \mathop{\operatorname{arg\,min\;}}_{h \in H} E_{(X, Y, \Upsilon) \sim D}[ \Upsilon 1_{h (X) \neq Y}],
\] where $X$ are features, $Y \in \{ 0,1 \}$ are labels, $\Upsilon \in [0, c_{max}]$ are costs, and $D$ is some unknown distribution.

Costs are visible

First I'll assume that we can see the costs in unlabeled data, i.e., without querying the label. This is not typical in practice, since the cost often depends upon the label (e.g., false positives are more expensive than false negatives). However this will provide some intuition about what is possible.

I can use rejection sampling to reduce cost-sensitive classification to binary classification and then apply an active learning binary classifier. Specifically, I can rejection sample the input stream with acceptance probability $\Upsilon_k / c_{max}$, and if the sample is accepted it discards the cost and uses binary classification. This is a regret transform, which scales the induced binary regret by $E[\Upsilon]$. Therefore if we have a high probability regret bound $r_b (n)$ in the underlying active binary classifier given $n$ examples, then presumably replacing $n \rightarrow (E[\Upsilon] / c_{max}) n + O (\frac{1}{n} \log \frac{1}{\delta})$ and scaling by $E[\Upsilon]$ will give us a high probability bound $r_c (n)$ on the regret in the original problem, \[
r_c (n) = E[\Upsilon] r_b \left( \frac{E[\Upsilon]}{c_{max}} n + O (\frac{1}{n} \log \frac{1}{\delta}) \right).
\]
Meanwhile, in the case of a rejection we definitely do not query the label $Y_k$. In the case of a non-rejection we might query the label $Y_k$ depending upon the probability of using the label in the induced active binary classifier. If we have a high probability bound on the label complexity of the induced binary classifier $l_b (n)$ given $n$ examples, then presumably replacing $n \rightarrow (E[\Upsilon] / c_{max}) n + O (\frac{1}{n} \log \frac{1}{\delta})$ will give a high probability bound on the label complexity $l_c (n)$ on the original cost-sensitive problem, \[
l_c (n) = l_b \left( \frac{E[\Upsilon]}{c_{max}} n + O (\frac{1}{n} \log \frac{1}{\delta}) \right).
\] Here's a meta-algorithm for active learning with cost-sensitive binary classification with visible costs.

Algorithm:Visible costs case

Rejection sampling for active cost-sensitive binary classification with visible costs and active learning binary oracle $\mathcal{O}$.

1. Obtain unlabeled data point $X_k$ with cost $\Upsilon_k$.
2. Toss a biased coin with $\mathrm{Pr} (\mathrm{heads}) = (\Upsilon_k / c_{max})$.
1. If heads, pass unlabeled features $X_k$ to $\mathcal{O}$.
2. If tails, discard unlabeled data point.

If the binary oracle uses Agnostic Active Learning without Constraints, this reasoning suggests a regret bound like \[
\mathrm{err}_c (h_n) \leq \mathrm{err}_c (h^*) + O \left(\sqrt{c_{max} E[\Upsilon] \frac{\log n}{n}}\right)
\] is possible, where \[
\mathrm{err}_c (h) = E_{(X, Y, \Upsilon) \sim D}[ \Upsilon 1_{h (X) \neq Y}],
\] and a label complexity like \[
\mbox{labels requested} \leq 1 + \theta \cdot \frac{2}{c_{max}} \mathrm{err}_c (h^*) n + O\left( \theta \sqrt{\frac{E[\Upsilon]}{c_{max}} n \log n} \right)
\] is possible. $\theta$ here is the disagreement coefficient for the induced binary subproblem.

Costs are not visible

Now I'll assume that the cost is only available if the label is queried. Suppose we decided to implement the above rejection sampling procedure by first accepting or rejecting according to the underlying active learning algorithm, and then if the label is queried and the cost $\Upsilon_k$ observed, flipping another coin and accepting with probability $(\Upsilon_k / c_{max})$. This would be consistent with the invisible costs constraint, but identical in terms of outcome. While this would be silly if the costs were visible, it is a feasible strategy if the costs are not visible. The regret bound would still be the same but now unfortunately the label complexity of the induced binary problem passes through unmodified, $l_c (n) = l_b (n)$. Of course, label complexity is the game in active learning, otherwise we would query every label and get the gold-standard passive learning regret bound. So having a worse label complexity for a particular regret bound is highly undesirable.

Algorithm:Invisible costs case

Rejection sampling for active cost-sensitive binary classification with invisible costs and active learning binary oracle $\mathcal{O}$.

1. Obtain unlabeled data point $X_k$.
2. Pass unlabeled data point $X_k$ to $\mathcal{O}$ and intercept the decision $Q_k \in \{ 0, 1 \}$ to query the label.
1. If $Q_k = 0$, do nothing.
2. If $Q_k = 1$,
1. Query the label and observe $\Upsilon_k$ and $Y_k$.
2. Toss a biased coin with $\mathrm{Pr} (\mathrm{heads}) = (\Upsilon_k / c_{max})$.
1. If heads, pass label $Y_k$ to $\mathcal{O}$ as is expected when $Q_k=1$.
2. If tails, discard label and ``undo'' the presentation of $X_k$ to $\mathcal{O}$.

In particular for a base learner utilizing Agnostic Active Learning without Constraints, this reasoning suggests when costs are not visible, \[
\mbox{labels requested} \leq 1 + \theta \cdot \frac{2}{E[\Upsilon]} \mathrm{err}_c (h^*) n+ O \left(\theta \sqrt{n \log n} \right).
\] Comparison of the two label complexities suggests we might gain something like a $(E[\Upsilon] / c_{max})$ improvement in the non-realizable case between a ``smart'' cost-sensitive active learning algorithm and the ``dumb'' one sketched here.

Agnostic Active Learning Without Constraints, Explained

Over the holidays I really dug into Agnostic Active Learning without Constraints by Beygelzimer et. al., and I've developed an intuition about this approach that I feel like sharing.

The nice thing about this approach is that it works with any classifier which can be said to be doing empirical risk minimization: linear predictors, neural networks, decision trees, etc. The consistency guarantees even hold for multiclass 0-1 loss (although the label complexity guarantees do not); and in fact due to the importance-weighting the consistency guarantees hold even if you don't exactly compute the sampling probabilities in the manner described (for example, Vowpal Wabbit computes an approximation). It is therefore an eminently practical technique.

Optimal Sequential Label Censorship

Imagine we have some function $f: \mathcal{X} \times \mathcal{Y} \to [-1, 1]$ that we want to estimate $E_D [f (X, Y)]$, and we don't know $D$ but we can sample from it. Think of $X$ as features, $Y$ as labels, and $f$ as something telling us how good a hypothesis is. So we grab $n$ samples $Z_k = (X_k, Y_k)$ and compute \[
\hat f_p (Z_{1:n}) = \frac{1}{n} \sum_{k=1}^n f (X_k, Y_k),
\] i.e., the empirical sample mean which converges to the true mean with high probability, e.g., via Hoeffding's inequality since $f$ is bounded. That's great, but it takes $n$ samples and we want to use less. The above estimator is analogous to a passive learner and by using less samples we get an active learner. If we can get close to $\hat f_p$ with high probability by using less samples then by the triangle inequality we'll be close to $E_D[f (X, Y)]$ with high probability.

Let $Q_k \in \{ 0, 1 \}$ be an indicator variable which says whether or not we censor a particular data point from the set. We're going to be shown the $n$ samples that the passive learner utilized above one at a time: after seeing the $k^\mathrm{th}$ features $X_k$, we're going to look at all the previous $X_{1:k-1}$ and also any previous $Y_i$ such that $Q_i=1$. Using all that information we're going to choose a $P_k$. Once we have $P_k$ we'll sample from $Q_k$ by flipping a coin with bias $P_k$. If $Q_k = 1$ then we use $Y_k$, otherwise it not revealed. Note looking at the features is free so we can always do that on the current instance, but looking at a label has a cost. Our active estimator is \[
\hat f_a (Z_{1:n}) = \frac{1}{n} \sum_{k=1}^n \frac{Q_k}{P_k} f (X_k, Y_k).
\] We have to scale the values we use by $1 / P_k$ to be unbiased. Hopefully it is intuitive that, if the $P_k$ are very small, $\hat f_a$ is more likely to differ from $\hat f_p$ by a large amount, because whether or not we censor the data point makes a large difference in the estimate (of course proving this is a cool trick, because the $Q_k$ are not i.i.d.). However there is one important caveat. If $f (X_k, Y_k) = 0$, it doesn't matter if we censor the data point or not, and it doesn't matter what the $P_k$ is, because the estimate is unchanged.

Exploiting that loophole is key, because it turns out the function whose expectation we want to estimate is the instantaneous regret \[
1_{h (X_k) \neq Y_k} - 1_{h^* (X_k) \neq Y_k},
\] between the current empirical risk minimizer \[
\begin{aligned}
h_n &= \mathop{\operatorname{arg\,min\;}}_{h \in H} \hat r_a (Z_{1:n}; h) \\
&= \mathop{\operatorname{arg\,min\;}}_{h \in H} \frac{1}{n} \sum_{k=1}^n \frac{Q_k}{P_k} 1_{h (X_k) \neq Y_k},
\end{aligned}
\] and the true optimal hypothesis $h^* = \operatorname{arg\,min}_{h \in H} E_D[ 1_{h^* (X) = Y} ]$. If our error in estimating this expected regret is small, then that means our empirical minimizer will be almost as good as the true minimizer. Note this function has a zero on any input where the empirical minimizer and the true minimizer agree. So ideally we would have a scheme such that

1. whenever $h_k (X_k) \neq h^* (X_k)$, $P_k$ is ``large'', and
2. whenever $h_k (X_k) = h^* (X_k)$, $P_k$ is ``small''.

The first condition ensures our estimator is accurate and the second condition ensures we are censoring unnecessary data points.

(Understand this before continuing)

The Sampling Scheme

Suppose we consumed $k - 1$ samples, censoring some of the labels according to some scheme as yet undefined, and we are now looking at the next set of features $X_k$. The current empirical risk minimizer is $h_k$. Clearly the true risk minimizer $h^*$ either does or not does not agree with $h_k$ on $X_k$. Suppose the latter: intuitively, since empirical averages are converging to their true means, we would expect \[
\begin{aligned}
h_k (X_k) \neq h^* (X_k) &\implies h^* \in \{ h \in H | h (X_k) \neq h_k (X_k) \} \\
&\mathop{\implies}_{\mathrm{Pr} > 1 - \delta} \hat r_a (Z_{1:k-1}; h^\prime_k) - \hat r_a (Z_{1:k-1}; h_k) < O (\frac{1}{\sqrt{k}} \log \frac{1}{\delta}), \\
h^\prime_k &= \mathop{\operatorname{arg\,min\;}}_{h \in H | h (X_k) \neq h_k (X_k)} \hat r_a (Z_{1:n}; h),
\end{aligned}
\] i.e., the best hypothesis $h^\prime_k$ that disagrees with $h_k$ on $X_k$ will have an empirical risk estimate that is almost as good as $h_k$ with high probability. This is because

1. $h^*$ is a candidate for $h^\prime_k$, so $h^\prime_k$ has an empirical risk which is at most the empirical risk of $h^*$, and
2. the empirical risk of $h_k$ is converging to the empirical risk of $h^*$ with high probability.

Conversely, if the empirical risk of $h^\prime_k$ is much worse than the empirical risk of $h_k$, it indicates $h_k (X_k) = h^* (X_k)$ with high probability. Recall points where $h_k (X_k) = h^* (X_k)$ are precisely the points we can safely aggressively censor, so the basic idea is to more aggressively censor instances when $h^\prime_k$ is sufficiently empirically worse than $h_k$. Of course, the exact formula for $P_k$ depends upon the details of the deviation bound, and working out the details is the impressive part, but as intuition suggests $P_k$ is monotonically decreasing in $\hat r_a (Z_{1:k-1}; h^\prime_k) - \hat r_a (Z_{1:k-1}; h_k)$.

(Understand this before continuing)

Now this scheme has no ``false negatives'', in the sense that whenever $h_k (X_k) \neq h^* (X_k)$, Beygelzimer et. al. arrange for $P_k \geq 1/2$ with high probability. So we are including the ``important points'' from an estimation perspective and our active learner will have an error bound comparable to a passive learner on the same set of data, except that the active learner might use significantly less labels.

Label Complexity

On the surface there are two ways for the active learner to frequently query labels.

1. (``Many important points''): If the empirical minimizer $h_k$ frequently disagrees with $h^*$, the active learner will frequently query labels, because there are many non-zeroes in the expected regret function for the empirical minimizer.
2. (``Many false positives''): If the empirical risk difference between $h^\prime_k$ and $h_k$ is small even when $h_k (X_k) = h^* (X_k)$, the active learner will fail to detect that a point can be safely censored.

Upon some reflection these can be seen to be two symptoms of the same underlying cause: the existence of many near-optimal hypothesis that frequently disagree with the optimal hypothesis.

To explore this insight further[1], consider that the probability that we utilize the $k^\mathrm{th}$ data point is some function $g$ of $k$ and the empirical error difference between the empirical risk minimizer $h_k$ and the empirical disagreeing risk minimizer $h^\prime_k$, \[
\begin{aligned}
P_k &= g \bigl(\hat r_a (Z_{1:k-1}, h^\prime_k) - \hat r_a (Z_{1:k-1}, h_k), k \bigr).
\end{aligned}
\] If we can bound $P_k$, then by the linearity of expectation we can bound the expected number of samples that we will use by iteration $k$ by the sum of $P_k$.

If we knew the cumulative distribution $F_k$ of $\hat r_a (Z_{1:k-1}, h^\prime_k) - \hat r_a (Z_{1:k-1}, h_k)$, then we could say \[
P_k = \int_0^1 d\gamma\; \frac{d F_k (\gamma)}{d\gamma} g (\gamma, k).
\] Alas this cumulative distribution $F_k$ is a bit difficult to pin down directly. It is more convenient to talk about the true regret between a hypothesis and the true optimum, and leverage the disagreement coefficient. Therefore the strategy will be to lower bound the first argument to $g$ as an function of $\mathrm{err} (\tilde h) - \mathrm{err} (h^*)$ for a suitably chosen $\tilde h$, and leverage the fact that $g$ is decreasing in the first argument to get an upper bound on $P_k$.

If $h_k (X_k) = h^* (X_k)$ then the empirical optimality of $h_k$ would allow us to lower bound the first argument to $g$ with $\hat r_a (Z_{1:k-1}, h^\prime_k) - \hat r_a (Z_{1:k-1}, h^*)$, after which we could subtract something $O (\frac{1}{\sqrt{k}} \log \frac{1}{\delta})$ to the empirical error difference to get a high probability lower bound based upon the true error difference $\mathrm{err} (h^\prime_k) - \mathrm{err} (h^*)$, and therefore get an upper bound on $g$ since $g$ decreases with both arguments. If $h^\prime_k (X_k) = h^* (X_k)$ the reasoning is more complicated but analogous, and the net result is that by choosing \[
\tilde h_k =
\begin{cases}
h_k &\mathrm{if}\; h_k (X_k) \neq h^* (X_k) \\
h^\prime_k &\mathrm{if}\; h^\prime_k (X_k) \neq h^* (X_k)
\end{cases},
\] then $P_k$ can be bounded by \[
P_k \leq \tilde g \bigl(\mathrm{err} (\tilde h_k) - \mathrm{err} (h^*), k \bigl),
\] for a slightly different $\tilde g$ which is also decreasing in both arguments.

Now the cumulative distribution we care about is $\mathrm{Pr} (\mathrm{err} (\tilde h_k) - \mathrm{err} (h) \leq \gamma)$, and the upper bound looks like \[
\begin{aligned}
P_k &\leq \int_0^1 d\gamma\; \frac{d \mathrm{Pr} (\mathrm{err} (\tilde h_k) - \mathrm{err} (h) \leq \gamma)}{d\gamma} \tilde g (\gamma, k) \\
&= \tilde g (1, k) - \int_0^1 d\gamma\; \mathrm{Pr} (\mathrm{err} (\tilde h_k) - \mathrm{err} (h) \leq \gamma) \frac{d \tilde g (\gamma, k)}{d \gamma} \\
&= \tilde g (1, k) + \int_0^1 d\gamma\; \mathrm{Pr} (\mathrm{err} (\tilde h_k) - \mathrm{err} (h) \leq \gamma) \left| \frac{d \tilde g (\gamma, k)}{d \gamma} \right| \\
\end{aligned}
\] The second line is integration by parts (!!) and the third line is using the fact that $\tilde g$ is decreasing in the first argument.

The next step is to bound $\mathrm{Pr} (\mathrm{err} (\tilde h_k) - \mathrm{err} (h) \leq \gamma)$. If $\mathrm{err} (\tilde h_k) - \mathrm{err} (h^*) \leq \gamma$, then in the worst case $\tilde h_k$ could be correct on all cases where $h^*$ makes an error, and could make another $\mathrm{err} (h^*) + \gamma$ errors additionally, and still have a regret of $\gamma$, i.e., \[
\mathrm{Pr} (\tilde h_k (X_k) \neq h_k^* (X_k)) \leq 2 \mathrm{err} (h^*) + \gamma.
\] However for our $\tilde h_k$ this condition actually did happen (go back and look at the definition!). At this point we can leverage the disagreement coefficient $\theta$ which bounds the probability of picking an input for which there is any hypothesis that has a certain regret, \[
\mathrm{Pr} (X \in \{ x \mid \exists h \:\mathrm{s.t.}\; h (x) \neq h^* (x) \land \mathrm{err} (h) - \mathrm{err}(h^*) \leq r \}) \leq \theta r.
\] Therefore, \[
\mathrm{Pr} (\mathrm{err} (\tilde h_k) - \mathrm{err} (h) \leq \gamma) \leq \theta (2 \mathrm{err} (h^*) + \gamma),
\] which substituting into the bound gives \[
P_k \leq \tilde g (1, k) + 2 \theta \; \mathrm{err} (h^*) \left( \int_0^1 d\gamma\; \left| \frac{d \tilde g (\gamma, k)}{d \gamma} \right| \right) + \theta \int_0^1 d\gamma\; \gamma \left| \frac{d \tilde g (\gamma; k)}{d \gamma} \right|.
\] Now it's completely unclear from my exposition, but it turns out for the $\tilde g$ utilized, \[
\begin{aligned}
\left( \int_0^1 d\gamma\; \left| \frac{d \tilde g (\gamma, k)}{d \gamma} \right| \right) &\leq 1 + O \left( \sqrt{\frac{\log k}{k - 1}} \right), \\
\int_0^1 d\gamma\; \gamma \left| \frac{d \tilde g (\gamma; k)}{d \gamma} \right| &\leq O \left( \frac{\log^2 k}{k - 1} \right).
\end{aligned}
\] So good news and bad news:

1. Bad news (non-realizable): if $\mathrm{err} (h^*) > 0$, worst case we will equilibrate at a sampling rate proportional to $\mathrm{err} (h^*)$. While disappointing, this limitation appears fundamental.
2. Good news: if $\mathrm{err} (h^*) = 0$ we utilize roughly $(\sqrt{n / \log n})$ the number of data points as the passive learner. Not an exponential speedup, but better than a sharp stick in the eye.

Even better label complexity bounds are possible if further assumptions about the structure of the hypothesis space is made.

[1] Past this point the explanation gets a bit less ``intuitive''. I take this as a sign that I don't understand it as well. I'll try my best to maintain intelligibility.

Subsampling: An Interesting Fail

Suppose I have a large data set $\{ (X_i, Y_i) \}$ sampled i.i.d. from a distribution $D$ on $\mathcal{X} \times \mathcal{Y}$, where $\mathcal{X}$ are features and $\mathcal{Y}$ are labels. The data set $\{ (X_i, Y_i) \}$ is a random variable but for the moment consider it fixed (i.e., condition on it). I could use my large data set to compute empirical means of functions $f: \mathcal{X} \times \mathcal{Y} \to [-1, 1]$, where $f$ is something like the regret of a hypothesis, \[
\frac{1}{n} \sum_{i=1}^n f (X_i, Y_i).
\] However this data set doesn't fit on my laptop so I don't want to use all of it; instead I'm going to censor some of the data points to construct an alternate estimator, \[
\frac{1}{n} \sum_{i=1}^n \frac{Q_i}{P_i} f (X_i, Y_i).
\] Here $Q_i$ is an indicator variable which says whether I use the $i^\mathrm{th}$ data point and $P_i = E[Q_i | \{ (X_i, Y_i) \}]$ is the probability of using the $i^\mathrm{th}$ data point, which I have to scale the values by in order to remain unbiased.

So far I've just described the importance-weighted active learning framework. However suppose I'm lazy and instead of using a real active learning algorithm I'm going to consider two strategies for shrinking my data set: the first is uniform subsampling, and the second is subsampling data associated with the more prevalent label (which I'll just assume is label 0). I want my estimates to be good, so I'll try to minimize a bound on \[
\mathrm{Pr} \left( \left| \frac{1}{n} \sum_{i=1}^n \frac{Q_i}{P_i} f (X_i, Y_i) - \frac{1}{n} \sum_{i=1}^n f (X_i, Y_i) \right| \geq \delta \right).
\] Hoeffding's inequality on uniform subsampling $P_i = p_u$ applies to the sequence \[
\begin{aligned}
A_i &= \frac{Q_i}{P_i} f (X_i, Y_i) - f (X_i, Y_i), \\
\max (A_i) - \min (A_i) &= \left( \frac{1}{p_u} - 1 \right) |f (X_i, Y_i)| \leq \left( \frac{1}{p_u} - 1 \right),
\end{aligned}
\] and yields the bound, \[
\mathrm{Pr} \left( \left| \frac{1}{n} \sum_{i=1}^n \frac{Q_i}{P_i} f (X_i, Y_i) - \frac{1}{n} \sum_{i=1}^n f (X_i, Y_i) \right| \geq \delta \right) \leq 2 \exp \left( -\frac{2 \delta^2 n}{\left(\frac{1}{p_u} - 1\right)^2} \right).
\] Similarly for one-label subsampling $P_i = p_o 1_{Y_i=0} + 1_{Y_i=1}$, \[
\begin{aligned}
A_i &= \frac{Q_i}{P_i} f (X_i, Y_i) - f (X_i, Y_i), \\
\max (A_i) - \min (A_i) &= \left( \frac{1}{p_o} - 1 \right) |f (X_i, Y_i)| 1_{Y_i=0} \leq \left( \frac{1}{p_o} - 1 \right) 1_{Y_i=0},
\end{aligned}
\] yielding \[
\mathrm{Pr} \left( \left| \frac{1}{n} \sum_{i=1}^n \frac{Q_i}{P_i} f (X_i, Y_i) - \frac{1}{n} \sum_{i=1}^n f (X_i, Y_i) \right| \geq \delta \right) \leq 2 \exp \left( -\frac{2 \delta^2 n^2}{\left( \frac{1}{p_o} - 1 \right)^2 \sum_{i=1}^n 1_{Y_i=0}}\right).
\] Both bounds are minimized at $p \to 1$, which is just a fancy way of saying ``not subsampling is the most accurate.'' To get a more interesting statement I'll compare them by equating their expected data set sizes, \[
p_u = p_o \sum_{i=1}^n I_{Y_i=0} + (1 - \sum_{i=1}^n I_{Y_i=0}),
\] and then I'll take the strategy with the better bound, \[
\begin{aligned}
\log \left( \frac{\mathrm{uniform}}{\mathrm{onelabel}} \right) &= -2 \delta^2 n \left(n - \sum_{i=1}^n I_{Y_i = 0} \right) \frac{n - (1 - p_o)^2 \sum_{i=1}^n I_{Y_i=0}}{(1 - p_o)^2 (\sum_{i=1}^n I_{Y_i=0})^2} \\
&\leq 0.
\end{aligned}
\] Yikes! The uniform subsampling bound is always better.

I don't think this means subsampling the more prevalent label is a bad idea, after all, I've seen it work in practice. However what I think this does mean is that the details of the $f$ being evaluated matters. In the above bounds I just used $|f| \leq 1$ but the result is too pessimistic. In particular the $f$ I really care about is the instantaneous regret between an empirical risk minimizing hypothesis and a true risk minimizing hypothesis, so I'll have to step up my game and understand some concepts like the disagreement coefficient. I suspect incorporating that will allow me to leverage the assumption that one label is far more prevalent than the other in the above analysis, which I presume is critical.