Active Learning for Cost-Sensitive Classification

Introduction

The field of active learning studies how to efficiently elicit relevant information so learning algorithms can make good decisions. Almost all active learning algorithms are designed for binary classification problems, leading to the natural question: How can active learning address more complex prediction problems? Multiclass and importance-weighted classification require only minor modifications but we know of no active learning algorithms that enjoy theoretical guarantees for more complex problems.

In this setup, we develop a new active learning algorithm for CSMC called Cost Overlapped Active Learning (COAL). COAL assumes access to a set of regression functions, and, when processing an example $x$, it uses the functions with good past performance to compute the range of possible costs that each label might take. Naturally, COAL only queries labels with large cost range, akin to uncertainty-based approaches in active regression , but furthermore, it only queries labels that could possibly have the smallest cost, avoiding the uncertain, but surely suboptimal labels. The key algorithmic innovation is an efficient way to compute the cost range realized by good regressors. This computation, and COAL as a whole, only requires that the regression functions admit efficient squared loss optimization, in contrast with prior algorithms that require 0/1 loss optimization .

Among our results, we prove that when processing $n$ (unlabeled) examples with $K$ classes and a regression class with pseudo-dimension $d$ (See Definition 1),

The algorithm needs to solve $\mathcal{O}(Kn^{5})$ regression problems over the function class (Corollary 2). Thus COAL runs in polynomial time for convex regression sets.

We also derive generalization and label complexity bounds under a milder Tsybakov-type noise condition (Assumption 4). Existing lower bounds from binary classification suggest that our results are optimal in their dependence on $n$, although these lower bounds do not directly apply to our setting. We also discuss some intuitive examples highlighting the benefits of using COAL.

CSMC provides a more expressive language for success and failure than multiclass classification, which allows learning algorithms to make the trade-offs necessary for good performance and broadens potential applications. For example, CSMC can naturally express partial failure in hierarchical classification . Experimentally, we show that COAL substantially outperforms the passive learning baseline with orders of magnitude savings in the labeling effort on a number of hierarchical classification datasets (see Figure 1 for comparison between passive learning and COAL on Reuters text categorization).

CSMC also forms the basis of learning to avoid cascading failures in joint prediction tasks like structured prediction and reinforcement learning . As our second application, we consider learning to search algorithms for joint or structured prediction, which operate by a reduction to CSMC. In this reduction, evaluating the cost of a class often involves a computationally expensive “roll-out,” so using an active learning algorithm inside such a passive joint prediction method can lead to significant computational savings. We show that using COAL within the Aggravate algorithm reduces the number of roll-outs by a factor of $\frac{1}{4}$ to $\frac{3}{4}$ on several joint prediction tasks.

Our code is publicly available as part of the Vowpal Wabbit machine learning library.http://hunch.net/~vw

Related Work

Active learning is a thriving research area with many theoretical and empirical studies. We recommend the survey of Settles for an overview of more empirical research. We focus here on theoretical results.

Our work falls into the framework of disagreement-based active learning, which studies general hypothesis spaces typically in an agnostic setup (see Hanneke for an excellent survey). Existing results study binary classification, while our work generalizes to CSMC, assuming that we can accurately predict costs using regression functions from our class. One difference that is natural for CSMC is that our query rule checks the range of predicted costs for a label.

The other main difference is that we use a square loss oracle to search the version space. In contrast, prior work either explicitly enumerates the version space or uses a 0/1 loss classification oracle for the search . In most instantiations, the oracle solves an NP-hard problem and so does not directly lead to an efficient algorithm, although practical implementations using heuristics are still quite effective. Our approach instead uses a squared-loss regression oracle, which can be implemented efficiently via convex optimization and leads to a polynomial time algorithm.

In addition to disagreement-based approaches, much research has focused on plug-in rules for active learning in binary classification, where one estimates the class-conditional regression function . Apart from Hanneke and Yang , these works make smoothness assumptions and have a nonparametric flavor. Instead, Hanneke and Yang assume a calibrated surrogate loss and abstract realizable function class, which is more similar to our setting. While the details vary, our work and these prior results employ the same algorithmic recipe of maintaining an implicit version space and querying in a suitably-defined disagreement region. Our work has two notable differences: (1) our algorithm operates in an oracle computational model, only accessing the function class through square loss minimization problems, (2) our results apply to general CSMC, which exhibit significant differences from binary classification. See Subsection 6.1 for further discussion.

Focusing on linear representations, Balcan et al. , Balcan and Long study active learning with distributional assumptions, while the selective sampling framework from the online learning community considers adversarial assumptions . These methods use query strategies that are specialized to linear representations and do not naturally generalize to other hypothesis classes.

Supervised learning oracles that solve NP-hard optimization problems in the worst case have been used in other problems including contextual bandits and structured prediction . Thus we hope that our work can inspire new algorithms for these settings as well.

Lastly, we mention that square loss regression has been used to estimate costs for passive CSMC , but, to our knowledge, using a square loss oracle for active CSMC is new.

Active learning for CSMC was introduced recently in Krishnamurthy et al. with an algorithm that also uses cost ranges to decide where to query. They compute cost ranges by using the regression oracle to perform a binary search for the maximum and minimum costs, but this computation results in a sub-optimal label complexity bound. We resolve this sub-optimality with a novel cost range computation that is inspired by the multiplicative weights technique for solving linear programs. This algorithmic improvement also requires a significantly more sophisticated statistical analysis for which we derive a novel uniform Freedman-type inequality for classes with bounded pseudo-dimension. This result may be of independent interest.

Krishnamurthy et al. also introduce an online approximation for additional scalability and use this algorithm for their experiments. Our empirical results use this same online approximation and are slightly more comprehensive. Finally, we also derive generalization and label complexity bounds for our algorithm in a setting inspired by Tsybakov’s low noise condition .

Comparison with Foster et al. [18].

In a follow-up to the present paper, Foster et al. build on our work with a regression-based approach for contextual bandit learning, a problem that bears some similarities to active learning for CSMC. The results are incomparable due to the differences in setting, but it is worth discussing their techniques. As in our paper, Foster et al. maintain an implicit version space and compute maximum and minimum costs for each label, which they use to make predictions. They resolve the sub-optimality in Krishnamurthy et al. with epoching, which enables a simpler cost range computation than our multiplicative weights approach. However, epoching incurs an additional $\log(n)$ factor in the label complexity, and under low-noise conditions where the overall bound is $\mathcal{O}(\textrm{polylog}(n))$, this yields a polynomially worse guarantee than ours.

Problem Setting and Notation

Let $\mathcal{G}\triangleq\{g:\mathcal{X}\mapsto\}$ denote a set of base regressors and let $\mathcal{F}\triangleq\mathcal{G}^{K}$ denote a set of vector regressors where the $y^{\textrm{th}}$ coordinate of $f\in\mathcal{F}$ is written as $f(\cdot;y)$. The set of classifiers under consideration is $\mathcal{H}\triangleq\{h_{f}\mid f\in\mathcal{F}\}$ where each $f$ defines a classifier $h_{f}:\mathcal{X}\mapsto\mathcal{Y}$ by

When using a set of regression functions for a classification task, it is natural to assume that the expected costs under $\mathcal{D}$ can be predicted by some function in the set. This motivates the following realizability assumption.

While $f^{\star}$ is always well defined, note that the cost itself may be noisy. In comparison with our assumption, the existence of a zero-cost classifier in $\mathcal{H}$ (which is often assumed in active learning) is stronger, while the existence of $h_{f^{\star}}$ in $\mathcal{H}$ is weaker but has not been leveraged in active learning.

We also require assumptions on the complexity of the class $\mathcal{G}$ for our statistical analysis. To this end, we assume that $\mathcal{G}$ is a compact convex subset of $L_{\infty}(\mathcal{X})$ with finite pseudo-dimension, which is a natural extension of VC-dimension for real-valued predictors.

As an example, linear functions in some basis representation, e.g., $g(x)=\sum_{i=1}^{d}w_{i}\phi_{i}(x)$, where weights $w_{i}$ are bounded in some norm, have pseudodimension $d$. In fact, our result can be stated entirely in terms of covering numbers, and we translate to pseudo-dimension using the fact that such classes have “parametric" covering numbers of the form $(1/\varepsilon)^{d}$. Thus, our results extend to classes with “nonparametric" growth rates as well (e.g., Holder-smooth functions), although we focus on the parametric case for simplicity. Note that this is a significant departure from Krishnamurthy et al. , which assumed that $\mathcal{G}$ was finite.

Since we assume that $\mathcal{G}$ is a compact convex set it is amenable to standard convex optimization techniques, so this imposes no additional restriction. However, in the special case of linear functions, this optimization is just least squares and can be computed in closed form. Note that this is fundamentally different from prior works that use a 0/1-loss minimization oracle , which involves an NP-hard optimization in most cases of interest.

Our assumption that $\mathcal{G}$ is convex is only for computational tractability, as it is crucial in the efficient implementation of our query strategy, but is not required for our generalization and label complexity bounds. Unfortunately recent guarantees for learning with non-convex classes do not immediately yield efficient active learning strategies. Note also that Krishnamurthy et al. obtain an efficient algorithm without convexity, but this yields a suboptimal label complexity guarantee.

Given a set of examples and queried costs, we often restrict attention to regression functions that predict these costs well and assess the uncertainty in their predictions given a new example $x$. For a subset of regressors $G\subset\mathcal{G}$, we measure uncertainty over possible cost values for $x$ with

To measure the labeling effort, we track the number of examples for which even a single cost is queried as well as the total number of queries. This bookkeeping captures settings where the editorial effort for inspecting an example is high but each cost requires minimal further effort, as well as those where each cost requires substantial effort. Formally, we define $Q_{i}(y)\in\{0,1\}$ to be the indicator that the algorithm queries label $y$ on the $i^{\textrm{th}}$ example and measure

Cost Overlapped Active Learning

The pseudocode for our algorithm, Cost Overlapped Active Learning (COAL), is given in Algorithm 1. Given an example $x$, COAL queries the costs of some of the labels $y$ for $x$. These costs are chosen by (1) computing a set of good regression functions based on the past data (i.e., the version space), (2) computing the range of predictions achievable by these functions for each $y$, and (3) querying each $y$ that could be the best label and has substantial uncertainty. We now detail each step.

To compute an approximate version space we first find the regression function that minimizes the empirical risk for each label $y$, which at round $i$ is:

COAL then computes the maximum and minimum costs predicted by the version space $\mathcal{G}_{i}(y)$ on the new example $x$. Since the true expected cost is $f^{\star}(x;y)$ and, as we will see, $f^{\star}(\cdot;y)\in\mathcal{G}_{i}(y)$, these quantities serve as a confidence bound for this value. The computation is done by the MaxCost and MinCost subroutines which produce approximations to $c_{+}(x,\mathcal{G}_{i}(y))$ and $c_{-}(x,\mathcal{G}_{i}(y))$ respectively (See (3)).

Finally, using the predicted costs, COAL issues (possibly zero) queries. The algorithm queries any non-dominated label that has a large cost range, where a label is non-dominated if its estimated minimum cost is smaller than the smallest maximum cost (among all other labels) and the cost range is the difference between the label’s estimated maximum and minimum costs.

Intuitively, COAL queries the cost of every label which cannot be ruled out as having the smallest cost on $x$, but only if there is sufficient ambiguity about the actual value of the cost. The idea is that labels with little disagreement do not provide much information for further reducing the version space, since by construction all regressors would suffer similar square loss. Moreover, only the labels that could be the best need to be queried at all, since the cost-sensitive performance of a hypothesis $h_{f}$ depends only on the label that it predicts. Hence, labels that are dominated or have small cost range need not be queried.

Similar query strategies have been used in prior works on binary and multiclass classification , but specialized to linear representations. The key advantage of the linear case is that the set $\mathcal{G}_{i}(y)$ (formally, a different set with similar properties) along with the maximum and minimum costs have closed form expressions, so that the algorithms are easily implemented. However, with a general set $\mathcal{G}$ and a regression oracle, computing these confidence intervals is less straightforward. We use the MaxCost and MinCost subroutines, and discuss this aspect of our algorithm next.

In this section, we describe the MaxCost subroutine which uses the regression oracle to approximate the maximum cost on label $y$ realized by $\mathcal{G}_{i}(y)$, as defined in (3). The minimum cost computation requires only minor modifications that we discuss at the end of the section.

Given this observation, our strategy will be to find an approximate solution to the problem (7) and it is not difficult to see that this also yields an approximate value for the maximum predicted cost on $x$ for the label $y$.

In Algorithm 2, we show how to efficiently solve this program using the regression oracle. We begin by exploiting the convexity of the set $\mathcal{G}$, meaning that we can further rewrite the optimization problem (7) as

The above rewriting is effectively cosmetic as $\mathcal{G}=\Delta(\mathcal{G})$ by the definition of convexity, but the upshot is that our rewriting results in both the objective and constraints being linear in the optimization variable $P$. Thus, we effectively wish to solve a linear program in $P$, with our computational tool being a regression oracle over the set $\mathcal{G}$. To do this, we create a series of feasibility problems, where we repeatedly guess the optimal objective value for the problem (8) and then check whether there is indeed a distribution $P$ which satisfies all the constraints and gives the posited objective value. That is, we check

If we find such a solution, we increase our guess, and otherwise we reduce the guess and proceed until we localize the optimal value to a small enough interval.

It remains to specify how to solve the feasibility problem (9). Noting that this is a linear feasibility problem, we jointly invoke the Multiplicative Weights (MW) algorithm and the regression oracle in order to either find an approximately feasible solution or certify the problem as infeasible. MW is an iterative algorithm that maintains weights $\mu$ over the constraints. At each iteration it (1) collapses the constraints into one, by taking a linear combination weighted by $\mu$, (2) checks feasibility of the simpler problem with a single constraint, and (3) if the simpler problem is feasible, it updates the weights using the slack of the proposed solution. Details of steps (1) and (3) are described in Algorithm 2.

For step (2), the simpler problem that we must solve takes the form

This program can be solved by a single call to the regression oracle, since all terms on the left-hand-side involve square losses while the right hand side is a constant. Thus we can efficiently implement the MW algorithm using the regression oracle. Finally, recalling that the above description is for a fixed value of objective $c$, and recalling that the maximum can be approximated by a binary search over $c$ leads to an oracle-based algorithm for computing the maximum cost. For this procedure, we have the following computational guarantee.

Algorithm 2 returns an estimate $\widehat{c_{+}}(x;y)$ such that $c_{+}(x;y)\leq\widehat{c_{+}}(x;y)\leq c_{+}(x;y)+\textsc{tol}$ and runs in polynomial time with $\mathcal{O}(\max\{1,i^{2}/\nu_{n}^{2}\}\log(i)\log(1/\textsc{tol})/\textsc{tol}^{4})$ calls to the regression oracle.

Thus COAL can be implemented in polynomial time for any set $\mathcal{G}$ that admits efficient square loss optimization. Compared to Krishnamurthy et al. which required $\mathcal{O}(n^{2})$ oracle calls, the guarantee here is, at face value, worse, since the algorithm is slower. However, the algorithm enforces a much stronger constraint on the version space which leads to a much better statistical analysis, as we will discuss next. Nevertheless, these algorithms that use batch square loss optimization in an iterative or sequential fashion are too computational demanding to scale to larger problems. Our implementation alleviates this with an alternative heuristic approximation based on a sensitivity analysis of the oracle, which we detail in Section 7.

Generalization Analysis

In this section, we derive generalization guarantees for COAL. We study three settings: one with minimal assumptions and two low-noise settings.

Our first low-noise assumption is related to the Massart noise condition , which in binary classification posits that the Bayes optimal predictor is bounded away from $1/2$ for all $x$. Our condition generalizes this to CSMC and posits that the expected cost of the best label is separated from the expected cost of all other labels.

A distribution $\mathcal{D}$ supported over $(x,c)$ pairs satisfies the Massart noise condition with parameter $\tau>0$, if for all $x$ (with $\mathcal{D}(x)>0$),

where $y^{\star}(x)\triangleq\mathop{\textrm{argmin}}_{y}f^{\star}(x;y)$ is the true best label for $x$.

The Massart noise condition describes favorable prediction problems that lead to sharper generalization and label complexity bounds for COAL. We also study a milder noise assumption, inspired by the Tsybakov condition , again generalized to CSMC. See also Agarwal .

A distribution $\mathcal{D}$ supported over $(x,c)$ pairs satisfies the Tsbyakov noise condition with parameters $(\tau_{0},\alpha,\beta)$ if for all $0\leq\tau\leq\tau_{0}$,

where $y^{\star}(x)\triangleq\mathop{\textrm{argmin}}_{y}f^{\star}(x;y)$.

Observe that the Massart noise condition in Assumption 3 is a limiting case of the Tsybakov condition, with $\tau=\tau_{0}$ and $\alpha\rightarrow\infty$. The Tsybakov condition states that it is polynomially unlikely for the cost of the best label to be close to the cost of the other labels. This condition has been used in previous work on cost-sensitive active learning and is also related to the condition studied by Castro and Nowak with the translation that $\alpha=\frac{1}{\kappa-1}$, where $\kappa\in$ is their noise level.

Our generalization bound is stated in terms of the noise level in the problem so that they can be readily adapted to the favorable assumptions. We define the noise level using the following quantity, given any $\zeta>0$.

$P_{\zeta}$ describes the probability that the expected cost of the best label is close to the expected cost of the second best label. When $P_{\zeta}$ is small for large $\zeta$ the labels are well-separated so learning is easier. For instance, under a Massart condition $P_{\zeta}=0$ for all $\zeta\leq\tau$.

We now state our generalization guarantee.

For any $\delta<1/e$, for all $i\in[n]$, with probability at least $1-\delta$, we have

where $\nu_{n}$, $f_{i}$ are defined in Algorithm 1, and $h_{f_{i}}$ is defined in (1).

Under Assumption 3, for any $\delta<1/e$, with probability at least $1-\delta$, for all $i\in[n]$, we have

Under Assumption 4, for any $\delta<1/e$, with probability at least $1-\delta$, for all $\frac{32K\nu_{n}}{\beta\tau_{0}^{\alpha+2}}\leq i\leq n$, we have

Label Complexity Analysis

Without distributional assumptions, the label complexity of COAL can be $\mathcal{O}(n)$, just as in the binary classification case, since there may always be confusing labels that force querying. In line with prior work, we introduce two disagreement coefficients that characterize favorable distributional properties. We first define a set of good classifiers, the cost-sensitive regret ball:

We also recall our earlier notation $\gamma(x,y,F)$ (see (3) and the subsequent discussion) for a subset $F\subseteq\mathcal{F}$ which indicates the range of expected costs for $(x,y)$ as predicted by the regressors corresponding to the classifiers in $F$. We now define the disagreement coefficients.

Then the disagreement coefficients are defined as:

Intuitively, the conditions in both coefficients correspond to the checks on the domination and cost range of a label in Lines 12 and 14 of Algorithm 1. Specifically, when $x\in\textrm{DIS}(r,y)$, there is confusion about whether $y$ is the optimal label or not, and hence $y$ is not dominated. The condition on $\gamma(x,y,\mathcal{F}_{\textrm{csr}}(r))$ additionally captures the fact that a small cost range provides little information, even when $y$ is non-dominated. Collectively, the coefficients capture the probability of an example $x$ where the good classifiers disagree on $x$ in both predicted costs and labels. Importantly, the notion of good classifiers is via the algorithm-independent set $\mathcal{F}_{\textrm{csr}}(r)$, and is only a property of $\mathcal{F}$ and the data distribution.

The definitions are a natural adaptation from binary classification , where a similar disagreement region to $\textrm{DIS}(r,y)$ is used. Our definition asks for confusion about the optimality of a specific label $y$, which provides more detailed information about the cost-structure than simply asking for any confusion among the good classifiers. The $1/r$ scaling is in agreement with previous related definitions , and we also scale by the cost range parameter $\psi$, so that the favorable settings for active learning can be concisely expressed as having $\theta_{1},\theta_{2}$ bounded, as opposed to a complex function of $\psi$.

The next three results bound the labeling effort (4), in the high noise and low noise cases respectively. The low noise assumptions enable significantly sharper bounds. Before stating the bounds, we recall that $L_{1}$ corresponds to the number of examples where at least one cost is queried, while $L_{2}$ is the total number of costs queried across all examples.

With probability at least $1-\delta$, the label complexity of the algorithm over $n$ examples is at most

Assume the Massart noise condition holds. With probability at least $1-\delta$ the label complexity of the algorithm over $n$ examples is at most

Assume the Tsybakov noise condition holds. With probability at least $1-\delta$ the label complexity of the algorithm over $n$ examples is at most

On the other hand, in both low noise cases the label complexity scales sublinearly with $n$. With bounded disagreement coefficients, this improves over the standard passive learning analysis where all labels are queried on $n$ examples to achieve the generalization guarantees in Theorem 3, Corollary 4, and Corollary 5 respectively. In particular, under the Massart condition, both $L_{1}$ and $L_{2}$ bounds scale with $\theta\log(n)$ for the respective disagreement coefficients, which is an exponential improvement over the passive learning analysis. Under the milder Tsybakov condition, the bounds scale with $\theta^{\frac{\alpha}{\alpha+1}}n^{\frac{2}{\alpha+2}}$, which improves polynomially over passive learning. These label complexity bounds agree with analogous results from binary classification in their dependence on $n$.

Note that $\theta_{2}\leq K\theta_{1}$ always and it can be much smaller, as demonstrated through an example in the next section. In such cases, only a few labels are ever queried and the $L_{2}$ bound in the high noise case reflects this additional savings over passive learning. Unfortunately, in low noise conditions, we do not benefit when $\theta_{2}\ll K\theta_{1}$. This can be resolved by letting $\psi_{i}$ in the algorithm depend on the noise level $\tau$, but we prefer to use the more robust choice $\psi_{i}=1/\sqrt{i}$ which still allows COAL to partially adapt to low noise and achieve low label complexity.

The main improvement over Krishnamurthy et al. is demonstrated in the label complexity bounds under low noise assumptions. For example, under Massart noise, our bound has the optimal $\log(n)/\tau^{2}$ rate, while the bound in Krishnamurthy et al. is exponentially worse, scaling with $n^{\beta}/\tau^{2}$ for $\beta\in(0,1)$. This improvement comes from explicitly enforcing monotonicity of the version space, so that once a regressor is eliminated it can never force COAL to query again. Algorithmically, computing the maximum and minimum costs with the monotonicity constraint is much more challenging and requires the new subroutine using MW.

In this subsection we show that in many cases we can obtain guarantees in terms of Hanneke’s disagreement coefficient , which has been used extensively in active learning for binary classification. We also show that, for multiclass classification, the label complexity scales with the error of the optimal classifier $h^{\star}$, a refinement on Theorem 6. The guarantees require no modifications to the algorithm and enable a precise comparison with prior results. Unfortunately, they do not apply to the general CSMC setting, so they have not been incorporated into our main theorems.

This coefficient is known to be $O(1)$ in many cases, for example when the hypothesis class consists of linear separators and the marginal distribution is uniform over the unit sphere [19, Chapter 7]. In comparison with Definition 2, the two differences are that $\theta_{1},\theta_{2}$ include the cost-range condition and involve the cost-sensitive regret ball $\mathcal{F}_{\textrm{csr}}(r)$ rather than $\widetilde{\mathcal{F}}(r)$. As $\widetilde{\mathcal{F}}(r)\subset\mathcal{F}_{\textrm{csr}}(r)$, we expect that $\theta_{1}$ and $\theta_{2}$ are typically larger than $\theta_{0}$, so bounds in terms of $\theta_{0}$ are more desirable. We now show that such guarantees are possible in many cases.

For general CSMC, low noise conditions admit the following:

Under Massart noise, with probability at least $1-\delta$ the label complexity of the algorithm over $n$ examples is at most $L_{1}=\mathcal{O}\left(\frac{\log(n)\nu_{n}}{\tau^{2}}\theta_{0}+\log(1/\delta)\right)$. Under Tsybakov noise, the label complexity is at most $L_{1}=\mathcal{O}\left(\theta_{0}n^{\frac{2}{\alpha+2}}\left(\log(n)\nu_{n}\right)^{\frac{\alpha}{\alpha+2}}+\log(1/\delta)\right)$. In both cases we have $L_{2}=O(KL_{1})$.

That is, for any low noise CSMC problem, COAL obtains a label complexity bound in terms of Hanneke’s disagreement coefficient $\theta_{0}$ directly. Note that this adaptivity requires no change to the algorithm. Proposition 1 enables a precise comparison with disagreement-based active learning for binary classification. In particular, this bound matches the guarantee for CAL [19, Theorem 5.4] with the caveat that our measure of statistical complexity is the pseudodimension of the $\mathcal{F}$ instead of the VC-dimension of the hypothesis class. As a consequence, under low noise assumptions, COAL has favorable label complexity in all examples where $\theta_{0}$ is small.

The high noise case.

For multiclass classification, with probability at least $1-\delta$, the label complexity of the algorithm over $n$ examples is at most

This result exploits two properties of the multiclass cost structure. First we can relate $\mathcal{F}_{\textrm{csr}}(r)$ to the disagreement ball $\widetilde{\mathcal{F}}(r)$, which lets us introduce Hanneke’s disagreement coefficient $\theta_{0}$. Second, we can bound $P_{\zeta}$ in Theorem 3 in terms of $\textrm{error}(h_{f^{\star}})$. Together the bound is comparable to prior results for active learning in binary classification , with a slight generalization to the multiclass setting. Unfortunately, both of these refinements do not apply for general CSMC.

Summary.

In important special cases, COAL achieves label complexity bounds directly comparable with results for active learning in binary classification, scaling with $\theta_{0}$ and $\textrm{error}(h_{f^{\star}})$. In such cases, whenever $\theta_{0}$ is bounded — for which many examples are known — COAL has favorable label complexity. However, in general CSMC without low-noise assumptions, we are not able to obtain a bound in terms of these quantities, and we believe a bound involving $\theta_{0}$ does not hold for COAL. We leave understanding natural settings where $\theta_{1}$ and $\theta_{2}$ are small, or obtaining sharper guarantees as intriguing future directions.

2 Three Examples

We now describe three examples to give more intuition for COAL and our label complexity bounds. Even in the low noise case, our label complexity analysis does not demonstrate all of the potential benefits of our query rule. In this section we give three examples to further demonstrate these advantages.

Our first example shows the benefits of using the domination criterion in querying, in addition to the cost range condition. Consider a problem under Assumption 3, where the optimal cost is predicted perfectly, the second best cost is $\tau$ worse and all the other costs are substantially worse, but with variability in the predictions. Since all classifiers predict the correct label, we get $\theta_{1}=\theta_{2}=0$, so our label complexity bound is $\mathcal{O}(1)$. Intuitively, since every regressor is certain of the optimal label and its cost, we actually make zero queries. On the other hand, all of the suboptimal labels have large cost ranges, so querying based solely on a cost range criteria, as would happen with an active regression algorithm , leads to a large label complexity.

A related example demonstrates the improvement in our query rule over more naïve approaches where we query either no label or all labels, which is the natural generalization of query rules from multiclass classification . In the above example, if the best and second best labels are confused occasionally $\theta_{1}$ may be large, but we expect $\theta_{2}\ll K\theta_{1}$ since no other label can be confused with the best. Thus, the $L_{2}$ bound in Theorem 6 is a factor of $K$ smaller than with a naïve query rule since COAL only queries the best and second best labels. Unfortunately, without setting $\psi_{i}$ as a function of the noise parameters, the bounds in the low noise cases do not reflect this behavior.

Let $\mathcal{X}\triangleq\{x_{1},\ldots,x_{M}\}$, $\mathcal{Y}\triangleq\{0,1\}$, and consider functions $\mathcal{F}\triangleq\{f^{\star},f_{1},\ldots,f_{M}\}$. We have $f^{\star}(x)\triangleq(1/4,1/2),\forall x\in\mathcal{X}$ and $f_{i}(x_{i})\triangleq(1/4,0)$ and $f_{i}(x_{j})\triangleq(1/4,1)$ for $i\neq j$. The marginal distribution is uniform and the true expected costs are given by $f^{\star}$ so that the problem satisfies the Massart noise condition with $\tau=1/4$. The key to the construction is that $f_{i}$s have high square loss on labels that they do not predict.

Experiments

We now turn to an empirical evaluation of COAL. For further computational efficiency, we implemented an approximate version of COAL using: 1) a relaxed version space $\mathcal{G}_{i}(y)\leftarrow\{g\in\mathcal{G}\mid\widehat{R}_{i}(g;y)\leq\widehat{R}_{i}(g_{i,y};y)+\Delta_{i}\}$, which does not enforce monotonicity, and 2) online optimization, based on online linear least-squares regression. The algorithm processes the data in one pass, and the idea is to (1) replace $g_{i,y}$, the ERM, with an approximation $g_{i,y}^{o}$ obtained by online updates, and (2) compute the minimum and maximum costs via a sensitivity analysis of the online update. We describe this algorithm in detail in Subsection 7.1. Then, we present our experimental results, first for simulated active learning (Subsection 7.2) and then for learning to search for joint prediction (Subsection 7.3).

Consider the maximum and minimum costs for a fixed example $x$ and label $y$ at round $i$, all of which may be suppressed. We ignore all the constraints on the empirical square losses for the past rounds. First, define $\widehat{R}(g,w,c;y)\triangleq\widehat{R}(g;y)+w(g(x)-c)^{2}$, which is the risk functional augmented with a fake example with weight $w$ and cost $c$. Also define

and recall that $g_{i,y}$ is the ERM given in Algorithm 1. The functional $\widehat{R}(g,w,c;y)$ has a monotonicity property that we exploit here, proved in Appendix C.

As a result, an alternative to MinCost and MaxCost is to find

and return $\underline{g}_{\underline{w}}(x)$ and $\overline{g}_{\overline{w}}(x)$ as the minimum and maximum costs. We use two steps of approximation here. Using the definition of $\overline{g}_{w}$ and $\underline{g}_{w}$ as the minimizers of $\widehat{R}(g,w,1;y)$ and $\widehat{R}(g,w,0;y)$ respectively, we have

We use this upper bound in place of $\widehat{R}(g_{w})-\widehat{R}(g_{i,y})$ in (12) and (13). Second, we replace $g_{i,y}$, $\underline{g}_{w}$, and $\overline{g}_{w}$ with approximations obtained by online updates. More specifically, we replace $g_{i,y}$ with $g_{i,y}^{o}$, the current regressor produced by all online linear least squares updates so far, and approximate the others by

where $s(x,y,g_{i,y}^{o})\geq 0$ is a sensitivity value that approximates the change in prediction on $x$ resulting from an online update to $g_{i,y}^{o}$ with features $x$ and label $y$. The computation of this sensitivity value is governed by the actual online update where we compute the derivative of the change in the prediction as a function of the importance weight $w$ for a hypothetical example with cost or cost $1$ and the same features. This is possible for essentially all online update rules on importance weighted examples, and it corresponds to taking the limit as $w\rightarrow 0$ of the change in prediction due to an update, divided by $w$. Since we are using linear representations, this requires only $\mathcal{O}(s)$ time per example, where $s$ is the average number of non-zero features. With these two steps, we obtain approximate minimum and maximum costs using

The online update guarantees that $g_{i,y}^{o}(x)\in$. Since the minimum cost is lower bounded by 0, we have $\underline{w}^{o}\in\left(0,\frac{g_{i,y}^{o}(x)}{s(x,0,g_{i,y}^{o})}\right]$. Finally, because the objective $w(g_{i,y}^{o}(x))^{2}-w(g_{i,y}^{o}(x)-w\cdot s(x,0,g_{i,y}^{o}))^{2}$ is increasing in $w$ within this range (which can be seen by inspecting the derivative), we can find $\underline{w}^{o}$ with binary search. Using the same techniques, we also obtain an approximate maximum cost.

2 Simulated Active Learning

We performed simulated active learning experiments with three datasets. ImageNet 20 and 40 are sub-trees of the ImageNet hierarchy covering the 20 and 40 most frequent classes, where each example has a single zero-cost label, and the cost for an incorrect label is the tree-distance to the correct one. The feature vectors are the top layer of the Inception neural network . The third, RCV1-v2 , is a multilabel text-categorization dataset, which has 103 labels, organized as a tree with a similar tree-distance cost structure as the ImageNet data. Some dataset statistics are in Table 1.

We compare our online version of COAL to passive online learning. We use the cost-sensitive one-against-all (csoaa) implementation in Vowpal Wabbithttp://hunch.net/~vw, which performs online linear regression for each label separately. There are two tuning parameters in our implementation. First, instead of $\Delta_{i}$, we set the radius of the version space to $\Delta_{i}^{\prime}=\frac{\kappa\nu_{i-1}}{i-1}$ (i.e. the $\log(n)$ term in the definition of $\nu_{n}$ is replaced with $\log(i)$) and instead tune the constant $\kappa$. This alternate “mellowness" parameter controls how aggressive the query strategy is. The second parameter is the learning rate used by online linear regressionWe use the default online learning algorithm in Vowpal Wabbit, which is a scale-free importance weight invariant form of AdaGrad ..

where $q_{\max}$ is the minimum $q$ such that $2^{(q-1)}\cdot 10$ is larger than the size of the training data. This performance measure is the area under the curve of test performance against number of queries in $\log_{2}$ scale. A large value means the test performance quickly improves with the number of queries. The best learning rate for mellowness $mel$ is then chosen as

The best learning rates for different datasets and mellowness settings are in Table 2.

In the top row of Figure 2, we plot, for each dataset and mellowness, the number of queries against the median test cost along with bars extending from the $15^{\textrm{th}}$ to $85^{\textrm{th}}$ quantile. Overall, COAL achieves a better trade-off between performance and queries. With proper mellowness parameter, active learning achieves similar test cost as passive learning with a factor of 8 to 32 fewer queries. On ImageNet 40 and RCV1-v2 (reproduced in Figure 1), active learning achieves better test cost with a factor of 16 fewer queries. On RCV1-v2, COAL queries like passive up to around $256k$ queries, since the data is very sparse, and linear regression has the property that the cost range is maximal when an example has a new unseen feature. Once COAL sees all features a few times, it queries much more efficiently than passive. These plots correspond to the label complexity $L_{2}$.

In the bottom row, we plot the test error as a function of the number of examples for which at least one query was requested, for each dataset and mellowness, which experimentally corresponds to the $L_{1}$ label complexity. In comparison to the top row, the improvements offered by active learning are slightly less dramatic here. This suggests that our algorithm queries just a few labels for each example, but does end up issuing at least one query on most of the examples. Nevertheless, one can still achieve test cost competitive with passive learning using a factor of 2-16 less labeling effort, as measured by $L_{1}$.

We also compare COAL with two active learning baselines. Both algorithms differ from COAL only in their query rule. AllOrNone queries either all labels or no labels using both domination and cost-range conditions and is an adaptation of existing multiclass active learners . NoDom just uses the cost-range condition, inspired by active regression . The results for ImageNet 40 and RCV1-v2 are displayed in Figure 3, where we use the AUC strategy to choose the learning rate. We choose the mellowness by visual inspection for the baselines and use $0.01$ for COAL We use $0.01$ for AllOrNone and $10^{-3}$ for NoDom.. On ImageNet 40, the ablations provide minimal improvement over passive learning, while on RCV1-v2, AllOrNone does provide marginal improvement. However, on both datasets, COAL substantially outperforms both baselines and passive learning.

While not always the best, we recommend a mellowness setting of $0.01$ as it achieves reasonable performance on all three datasets. This is also confirmed by the learning-to-search experiments, which we discuss next.

3 Learning to Search

We also experiment with COAL as the base leaner in learning-to-search , which reduces joint prediction problems to CSMC. A joint prediction example defines a search space, where a sequence of decisions are made to generate the structured label. We focus here on sequence labeling tasks, where the input is a sentence and the output is a sequence of labels, specifically, parts of speech or named entities.

Learning-to-search solves such problems by generating the output one label at a time, conditioning on all past decisions. Since mistakes may lead to compounding errors, it is natural to represent the decision space as a CSMC problem, where the classes are the “actions” available (e.g., possible labels for a word) and the costs reflect the long term loss of each choice. Intuitively, we should be able to avoid expensive computation of long term loss on decisions like “is ‘the’ a determiner?” once we are quite sure of the answer. Similar ideas motivate adaptive sampling for structured prediction .

We specifically use Aggravate , which runs a learned policy to produce a backbone sequence of labels. For each position in the input, it then considers all possible deviation actions and executes an oracle for the rest of the sequence. The loss on this complete output is used as the cost for the deviating action. Run in this way, Aggravate requires $len\times K$ roll-outs when the input sentence has $len$ words and each word can take one of $K$ possible labels.

Since each roll-out takes $\mathcal{O}(len)$ time, this can be computationally prohibitive, so we use active learning to reduce the number of roll-outs. We use COAL and a passive learning baseline inside Aggravate on three joint prediction datasets (statistics are in Table 1). As above, we use several mellowness values and the same AUC criteria to select the best learning rate (see Table 2). The results are in Figure 4, and again our recommended mellowness is $0.01$.

Overall, active learning reduces the number of roll-outs required, but the improvements vary on the three datasets. On the Wikipedia data, COAL performs a factor of 4 fewer rollouts to achieve similar performance to passive learning and achieves substantially better test performance. A similar, but less dramatic, behavior arises on the NER task. On the other hand, COAL offers minimal improvement over passive learning on the POS-tagging task. This agrees with our theory and prior empirical results , which show that active learning may not always improve upon passive learning.

Proofs

In this section we provide proofs for the main results, the oracle-complexity guarantee and the generalization and label complexity bounds. We start with some supporting results, including a new uniform freedman-type inequality that may be of independent interest. The proof of this inequality, and the proofs for several other supporting lemmata are deferred to the appendices.

For both the computational and statistical analysis of COAL, we require concentration of the square loss functional $\widehat{R}_{j}(\cdot;y)$, uniformly over the class $\mathcal{G}$. To describe the result, we introduce the central random variable in the analysis:

The Multiplicative Weights Algorithm.

We also use the standard analysis of multiplicative weights for solving linear feasibility problems. We state the result here and, for completeness, provide a proof in Appendix B. See also Arora et al. , Plotkin et al. for more details.

Here $\eta$ is a parameter of the algorithm. The intuition is that if $v_{t}$ satisfies the $i^{\textrm{th}}$ constraint, then we down-weight the constraint, and conversely, we up-weight every constraint that is violated. Running the algorithm with appropriate choice of $\eta$ and for enough iterations is guaranteed to approximately solve the feasibility problem.

Consider running the MW algorithm with parameter $\eta=\sqrt{\log(m)/T}$ for $T$ iterations on a linear feasibility problem where oracle responses satisfy $\langle a_{i},v\rangle-b_{i}\in[-\rho_{i},\rho_{i}]$. If the oracle fails to find a feasible point in some iteration, then the linear program is infeasible. Otherwise the point $\bar{v}\triangleq\frac{1}{T}\sum_{t=1}^{T}v_{t}$ satisfies $\langle a_{i},\bar{v}\rangle\leq b_{i}+2\rho_{i}\sqrt{\log(m)/T}$ for all $i\in[m]$.

Other Lemmata.

Our first lemma evaluates the conditional expectation and variance of $M_{j}$, defined in (15), which we will use heavily in the proofs. Proofs of the results stated here are deferred to Appendix C.

We have for all $(g,y)\in\mathcal{G}\times\mathcal{Y}$,

The next lemma relates the cost-sensitive error to the random variables $M_{j}$. Define

which is the version space of vector regressors at round $i$. Additionally, recall that $P_{\zeta}$ captures the noise level in the problem, defined in (10) and that $\psi_{i}=1/\sqrt{i}$ is defined in the algorithm pseudocode.

For all $i>0$, if $f^{\star}\in\mathcal{F}_{i}$, then for all $f\in\mathcal{F}_{i}$

Note that the lemma requires that both $f^{\star}$ and $f$ belong to the version space $\mathcal{F}_{i}$.

For the label complexity analysis, we will need to understand the cost-sensitive performance of all $f\in\mathcal{F}_{i}$, which requires a different generalization bound. Since the proof is similar to that of Theorem 3, we defer the argument to appendix.

Assuming the bounds in Theorem 9 hold, then for all $i$, $\mathcal{F}_{i}\subset\mathcal{F}_{\textrm{csr}}(r_{i})$ where $r_{i}\triangleq\min_{\zeta>0}\left\{\zeta P_{\zeta}+\frac{44K\Delta_{i}}{\zeta}\right\}.$

The final lemma relates the query rule of COAL to a hypothetical query strategy driven by $\mathcal{F}_{\textrm{csr}}(r_{i})$, which we will subsequently bound by the disagreement coefficients. Let us fix the round $i$ and introduce the shorthand $\widehat{\gamma}(x_{i},y)=\widehat{c}_{+}(x_{i},y)-\widehat{c}_{-}(x_{i},y)$, where $\widehat{c}_{+}(x_{i},y)$ and $\widehat{c}_{-}(x_{i},y)$ are the approximate maximum and minimum costs computed in Algorithm 1 on the $i^{\textrm{th}}$ example, which we now call $x_{i}$. Moreover, let $Y_{i}$ be the set of non-dominated labels at round $i$ of the algorithm, which in the pseudocode we call $Y^{\prime}$. Formally, $Y_{i}=\{y\mid\widehat{c}_{-}(x_{i},y)\leq\min_{y^{\prime}}\widehat{c}_{+}(x_{i},y^{\prime})\}$. Finally recall that for a set of vector regressors $F\subset\mathcal{F}$, we use $\gamma(x,y,F)$ to denote the cost range for label $y$ on example $x$ witnessed by the regressors in $F$.

Suppose that the conclusion of Lemma 4 holds. Then for any example $x_{i}$ and any label $y$ at round $i$, we have

2 Proof of Theorem 1

The proof is based on expressing the optimization problem (7) as a linear optimization in the space of distributions over $\mathcal{G}$. Then, we use binary search to re-formulate this as a series of feasibility problems and apply Theorem 10 to each of these.

Recall that the problem of finding the maximum cost for an $(x,y)$ pair is equivalent to solving the program (7) in terms of the optimal $g$. For the problem (7), we further notice that since $\mathcal{G}$ is a convex set, we can instead write the minimization over $g$ as a minimization over $P\in\Delta(\mathcal{G})$ without changing the optimum, leading to the modified problem (8).

Thus we have a linear program in variable $P$, and Algorithm 2 turns this into a feasibility problem by guessing the optimal objective value and refining the guess using binary search. For each induced feasibility problem, we use MW to certify feasibility. Let $c\in$ be some guessed upper bound on the objective, and let us first turn to the MW component of the algorithm. The program in consideration is

This is a linear feasibility problem in the infinite dimensional variable $P$, with $i+1$ constraints. Given a particular set of weights $\mu$ over the constraints, it is clear that we can use the regression oracle over $g$ to compute

At this point, we would like to invoke the MW algorithm, and specifically Theorem 10, in order to find a feasible solution to (18) or to certify infeasibility. Invoking the theorem requires the $\rho_{j}$ parameters which specify how badly $g_{\mu}$ might violate the $j^{\textrm{th}}$ constraint. For us, $\rho_{j}\triangleq\kappa$ suffices since $\hat{R}_{j}(g;y)-\hat{R}_{j}(g_{j,y};y)\in$ (since $g_{j,y}$ is the ERM) and $\Delta_{j}\leq\kappa$. Since $\kappa\geq 2$ this also suffices for the cost constraint.

If at any iteration, MW detects infeasibility, then our guessed value $c$ for the objective is too small since no function satisfies both $(g(x_{i})-1)^{2}\leq c$ and the empirical risk constraints in (18) simultaneously. In this case, in Line 10 of Algorithm 2, our binary search procedure increases our guess for $c$. On the other hand, if we apply MW for $T$ iterations and find a feasible point in every round, then, while we do not have a point that is feasible for the original constraints in (18), we will have a distribution $P_{T}$ such that

We will set $T$ toward the end of the proof.

Let $\bar{P}$ be the approximately feasible point found when running MW with the final value of $c_{h}$. By Jensen’s inequality and convexity of $\mathcal{G}$, there exists a single regressor that is also approximately feasible, which we denote $\bar{g}$. Observe that $g^{\star}$ satisfies all constraints with strict inequality, since by (20) we know that $\widehat{R}_{j}(g^{\star};y)-\widehat{R}_{j}(g_{j,y};y)\leq\Delta_{j}/\kappa<\Delta_{j}$. We create a strictly feasible point $g_{\zeta}$ by mixing $\bar{g}$ with $g^{\star}$ with proportion $1-\zeta$ and $\zeta$ for

which will be in $$when we set$T$. Combining inequalities, we get that for any$j\in[i]$

and hence this mixture regressor $g_{\zeta}$ is exactly feasible. Here we use that $\kappa\geq 2$ and that $\Delta_{i}$ is monotonically decreasing. With the pessimistic choice $g^{\star}(x_{i})=0$, the objective value for $g_{\zeta}$ is at most

3 Proof of the Generalization Bound

Recall the central random variable $M_{j}(g;y)$, defined in (15), which is the excess square loss for function $g$ on label $y$ for the $j^{\textrm{th}}$ example, if we issued a query. The idea behind the proof is to first apply Theorem 9 to argue that all the random variables $M_{j}(g;y)$ concentrate uniformly over the function class $\mathcal{G}$. Next for a vector regressor $f$, we relate the cost-sensitive risk to the excess square loss via Lemma 3. Finally, using the fact that $g_{i,y}$ minimizes the empirical square loss at round $i$, this implies a cost-sensitive risk bound for the vector regressor $f_{i}=(g_{i,y})$ at round $i$.

First, condition on the high probability event in Theorem 9, which ensures that the empirical square losses concentrate. We first prove that $f^{\star}\in\mathcal{F}_{i}$ for all $i\in[n]$. At round $i$, by (17), for each $y$ and for any $g$ we have

Since this bound applies to all $g\in\mathcal{G}$ it proves that $f^{\star}\in\mathcal{F}_{i+1}$ for all $i$, using the definition of $\Delta_{i}$ and $\kappa$. Trivially, we know that $f^{\star}\in\mathcal{F}_{1}$. Together with the fact that the losses are in $$and the definition of$\Delta_{i}$, the above analysis yields

This implies that $f^{\star}(\cdot;y)$ strictly satisfies the inequalities defining the version space, which we used in the MW proof.

We next prove that $f_{i+1}\in\mathcal{F}_{j}$ for all $j\in[i]$. Fix some label $y$ and to simplify notation, we drop dependence on $y$. If $g_{i+1}\notin\mathcal{G}_{t+1}$ for some $t\in\{0,\ldots,i\}$ then, first observe that we must have $t$ large enough so that $\nu_{n}/t\leq 1$. In particular, since $\Delta_{t+1}=\kappa\min\{1,\nu_{n}/t\}$ and we always have $\hat{R}_{t+1}(g_{i+1};y)\leq\hat{R}_{t+1}(g_{t+1};y)+1$ due to boundedness, we do not evict any functions until $\nu_{n}/t\leq 1$. For $t\geq\nu_{n}$, we get

The inequality uses the radius of the version space and the fact that by assumption $g_{i+1}\notin\mathcal{G}_{t+1}$, so the excess empirical risk is at least $\Delta_{t+1}=\kappa\nu_{n}/t$ since we are considering large $t$. We also use (20) on the second term. Moreover, we know that since $g_{i+1}$ is the empirical square loss minimizer for label $y$ after round $i$, we have $\sum_{j=1}^{i}M_{j}(g_{i+1};y)\leq 0$. These two facts together establish that

However, by Theorem 9 on this intermediary sum, we know that

using the definition of $\kappa$. This is a contradiction, so we must have that $g_{i+1}\in\mathcal{G}_{j}$ for all $j\in\{1,\ldots,i\}$. The same argument applies for all $y$ and hence we can apply Lemma 3 on all rounds to obtain

We study the four terms separately. The first one is straightforward and contributes $\zeta P_{\zeta}$ to the instantaneous cost sensitive regret. Using our definition of $\psi_{j}=1/\sqrt{j}$ the second term can be bounded as

The inequality above, $\sum_{i=1}^{n}\frac{1}{\sqrt{i}}\leq 2\sqrt{n}$, is well known. For the third term, using our definition of $\psi_{j}$ gives

Finally, the fourth term can be bounded using (17), which reveals

Since for each $y$, $\sum_{j=1}^{i}M_{j}(f_{i+1};y)\leq 0$ for the empirical square loss minimizer (which is what we are considering now), we get

And hence, we obtain the generalization bound

Under the Massart noise condition, set $\zeta=\tau$ so that $P_{\zeta}=0$ and we immediately get the result.

Proof of Corollary 5.

Set $\zeta=\min\left\{\tau_{0},\left(\frac{32K\nu_{n}}{i\beta}\right)^{\frac{1}{\alpha+2}}\right\}$, so that for $i$ sufficiently large the second term is selected and we obtain the bound.

4 Proof of the Label Complexity bounds

The proof for the label complexity bounds is based on first relating the version space $\mathcal{F}_{i}$ at round $i$ to the cost-sensitive regret ball $\mathcal{F}_{\textrm{csr}}$ with radius $r_{i}$. In particular, the containment $\mathcal{F}_{i}\subset\mathcal{F}_{\textrm{csr}}(r_{i})$ in Lemma 4 implies that our query strategy is more aggressive than the query strategy induced by $\mathcal{F}_{\textrm{csr}}(r_{i})$, except for a small error introduced when computing the maximum and minimum costs. This error is accounted for by Lemma 5. Since the probability that $\mathcal{F}_{\textrm{csr}}$ will issue a query is intimately related to the disagreement coefficient, this argument leads to the label complexity bounds for our algorithm.

For the former indicator, observe that $y\in Y_{i}$ implies that there exists a vector regressor $f\in\mathcal{F}_{i}\subset\mathcal{F}_{\textrm{csr}}(r_{i})$ such that $h_{f}(x_{i})=y$. This follows since the domination condition means that there exists $g\in\mathcal{G}_{i}(y)$ such that $g(x_{i})\leq\min_{y^{\prime}}\max_{g^{\prime}\in\mathcal{G}_{i}(y^{\prime})}g^{\prime}(x_{i})$. Since we are using a factored representation, we can take $f$ to use $g$ on the $y^{\textrm{th}}$ coordinate and use the maximizers for all the other coordinates. Similarly, there exists another regressor $f^{\prime}\in\mathcal{F}_{i}$ such that $h_{f^{\prime}}(x_{i})\neq y$. Thus this indicator can be bounded by the disagreement coefficient

We will now apply Freedman’s inequality on the sequence $\{\sum_{y}Q_{i}(y)\}_{i=1}^{n}$, which is a martingale with range $K$. Moreover, due to non-negativity, the conditional variance is at most $K$ times the conditional mean, and in such cases, Freedman’s inequality reveals that with probability at least $1-\delta$

For us, Freedman’s inequality implies that with probability at least $1-\delta/2$

The last step here uses the definition of the disagreement coefficient $\theta_{2}$. To wrap up the proof we just need to upper bound the sequence, using our choices of $\psi_{i}=1/\sqrt{i}$, $r_{i}=2\sqrt{44K\Delta_{i}}$, and $\Delta_{i}=\kappa\min\{1,\frac{\nu_{n}}{i-1}\}$. With simple calculations this is easily seen to be at most

Similarly for $L_{1}$ we can derive the bound

and then apply Freedman’s inequality to obtain that with probability at least $1-\delta/2$

Proof of Theorem 7.

Using the same notations as in the bound for the high noise case we first express the $L_{2}$ label complexity as

We need to do two things with the first part of the query indicator, so we have duplicated it here. For the second, we will use the derivation above to relate the query rule to the disagreement region. For the first, by Lemma 5, for $y\neq y_{i}^{\star}$, we can derive the bound

where for shorthand we have defined $D_{i}(y)\triangleq{\bf 1}\{\tau/4\leq\gamma(x_{i},y,\mathcal{F}_{\textrm{csr}}(r_{i}))\wedge x_{i}\in\textrm{DIS}(r_{i},y)\}$. The derivation for the first term is straightforward. We obtain the disagreement region for $y_{i}^{\star}$ since the fact that we query $y$ (i.e. $Q_{i}(y)$) implies there is $f$ such that $h_{f}(x_{i})=y$, so this function witnesses disagreement to $y_{i}^{\star}$.

For the earlier rounds, we simply upper bound the label complexity by $K$. Since the range of this random variable is at most $3K$, using Freedman’s inequality just as in the high noise case, we get that with probability at least $1-\delta/2$

The first line here is the application of Freedman’s inequality. In the second, we evaluate the expectation, which we can relate to the disagreement coefficients $\theta_{1},\theta_{2}$. Moreover, we use the setting $\psi_{i}=1/\sqrt{i}$ to evaluate the first term. As a technicality, we remove the index $i=1$ from the second summation, since we are already accounting for queries on the first round in the first term. The last step is to evaluate the series, for which we use the definition of $r_{i}=\min_{\zeta>0}\left\{\zeta P_{\zeta}+44K\Delta_{i}/\zeta\right\}$ and set $\zeta=\tau$, the Massart noise level. This gives $r_{i}=44K\Delta_{i}/\tau$. In total, we get

As $\theta_{2}\leq K\theta_{1}$ always, we drop $\theta_{2}$ from the above expression to obtain the stated bound.

For $L_{1}$ we use a very similar argument. First, by Lemmas 4 and 5

Moreover, one of the two classifiers can be $f^{\star}$, and so, when $\tau\geq\psi_{i}$, we can deduce

Combining this argument, we bound the $L_{1}$ label complexity as

Applying Freedman’s inequality just as before gives

Proof of Theorem 8.

For the Tsybakov case, the same argument as in the Massart case gives that with probability at least $1-\delta/2$

The main difference here is the term scaling with $n\tau^{\alpha}$ which arises since we do not have the deterministic bound $f^{\star}(x_{i},y)-f^{\star}(x_{i},y_{i}^{\star})\geq\tau$ as we used in the Massart case, but rather this happens except with probability $\beta\tau^{\alpha}$ (provided $\tau\leq\tau_{0}$). Now we must optimize $\zeta$ in the definition of $r_{i}$ and then $\tau$.

For $\zeta$ the optimal setting is $(44K\Delta_{i}/\beta)^{\frac{1}{\alpha+2}}$ which gives $r_{i}\leq 2\beta^{\frac{1}{\alpha+2}}(44K\Delta_{i})^{\frac{\alpha+1}{\alpha+2}}$. Since we want to set $\zeta\leq\tau_{0}$, this requires $i\geq 1+\frac{44K\kappa\nu_{n}}{\beta\tau_{0}^{\alpha+2}}$. For these early rounds we will simply pay $K$ in the label complexity, but this will be dominated by other higher order terms. For the later rounds, we get

This bound uses the integral approximation $\sum_{i=2}^{n}(i-1)^{-\frac{\alpha+1}{\alpha+2}}\leq 1+\int_{1}^{n-1}x^{-\frac{\alpha+1}{\alpha+2}}dx\leq(\alpha+2)n^{\frac{1}{\alpha+2}}$. At this point, the terms involving $\tau$ in our bound are

We set $\tau=(8(\alpha+2)(K\theta_{1}+\theta_{2}))^{\frac{1}{\alpha+1}}\left(44K\kappa\nu_{n}\right)^{\frac{1}{\alpha+2}}(\beta n)^{\frac{-1}{\alpha+2}}$ by optimizing the second two terms which gives a final bound of

This follows since the $1/\tau^{2}$ term agrees in the $n$ dependence and is lower order in other parameters, while the unaccounted for querying in the early rounds is independent of $n$. The bound of course requires that $\tau\leq\tau_{0}$, which again requires $n$ large enough. Note we are treating $\alpha$ and $\beta$ as constants and we drop $\theta_{2}$ from the final statement.

The $L_{1}$ bound requires only slightly different calculations. Following the derivation for the Massart case, we get

not counting the lower order term for the querying in the early rounds. Here we set $\tau=(8(\alpha+2)\theta_{1})^{\frac{1}{\alpha+1}}\left(44K\kappa\nu_{n}\right)^{\frac{1}{\alpha+2}}(\beta n)^{\frac{-1}{\alpha+2}}$ to obtain

Proof of Proposition 1: Massart Case.

Observe that with Massart noise, we have $\mathcal{F}_{\textrm{csr}}(r)\subset\widetilde{\mathcal{F}}(r/\tau)$, which implies that

Thus we may replace $\theta_{1}$ with $\theta_{0}$ in the proof of the $L_{1}$ label complexity bound above.

Proof of Proposition 1: Tsybakov Case.

We use this fact to prove that $\mathcal{F}_{\textrm{csr}}(r)\subset\widetilde{\mathcal{F}}(2r/\tau)$ for $\tau$ sufficiently small. This can be seen from above by noting that if $f\in\mathcal{F}_{\textrm{csr}}(r)$ then the right hand side is $\frac{r}{\tau}+\beta\tau^{\alpha}$, and if $\tau\leq(r/\beta)^{\frac{1}{1+\alpha}}$ the containment holds. Therefore, we have

Thus, provided $\tau\leq(r_{n}/\beta)^{\frac{1}{\alpha+1}}$, we can replace $\theta_{1}$ with $\theta_{0}$ in the above argument. This gives

As above, we have taken $r_{i}=2\beta^{\frac{1}{\alpha+2}}(44K\Delta_{i})^{\frac{\alpha+1}{\alpha+2}}$ and approximated the sum by an integral. Since $\Delta_{n}=\kappa\nu_{n}/(n-1)$, we can set $\tau=2^{\frac{\alpha+1}{\alpha+2}}(44K\kappa\nu_{n})^{\frac{1}{\alpha+2}}(\beta n)^{-\frac{1}{\alpha+2}}$. This is a similar choice to what we used in the proof of Theorem 8 except that we are not incorporating $\theta_{0}$ into the choice of $\tau$, and it yields a final bound of $\mathcal{O}\left(\theta_{0}n^{\frac{2}{\alpha+2}}\nu_{n}^{\frac{\alpha}{\alpha+2}}+\log(1/\delta)\right)$.

Proof of Proposition 2.

First we relate $\theta_{1}$ to $\theta_{0}$ in the multiclass case. For $f\in\mathcal{F}_{\textrm{csr}}(r)$, we have

Applying this argument in the $L_{1}$ derivation above, we obtain

We now bound $r_{i}$ via Lemma 4. In multiclass classification, the fact that $c={\bf 1}-e_{y}$ for some $y$ implies that $f^{\star}(x,y)$ is one minus the probability that the true label is $y$. Thus $f^{\star}(x,y)\in$, $\sum_{y}f^{\star}(x,y)=K-1$, and for any $x$ we always have

Hence, we may bound $P_{\zeta}$, for $\zeta\leq 1/2$, as follows

Now apply Lemma 4 with $\zeta=\min\{1/2,\sqrt{44K\Delta_{i}/\textrm{error}(h_{f^{\star}})}\}$, and we obtain

Using the definition of $\Delta_{i}$ the final $L_{1}$ label complexity bound is

Discussion

This paper presents a new active learning algorithm for cost-sensitive multiclass classification. The algorithm enjoys strong theoretical guarantees on running time, generalization error, and label complexity. The main algorithmic innovation is a new way to compute the maximum and minimum costs predicted by a regression function in the version space. We also design an online algorithm inspired by our theoretical analysis that outperforms passive baselines both in CSMC and structured prediction.

On a technical level, our algorithm uses a square loss oracle to search the version space and drive the query strategy. This contrasts with many recent results using argmax or 0/1-loss minimization oracles for information acquisition problems like contextual bandits . As these involve NP-hard optimizations in general, an intriguing question is whether we can use a square loss oracle for other information acquisition problems. We hope to answer this question in future work.

Acknowledgements

Part of this research was completed while TKH was at Microsoft Research and AK was at University of Massachusetts, Amherst. AK thanks Chicheng Zhang for insightful conversations. AK is supported in part by NSF Award IIS-1763618.

Appendix A Proof of Theorem 9

Fixing $i$ and $y$, and working toward (16) we seek to bound

The bound on the other tail is similar. In this section, we sometimes treat the query rule as a function which maps an $x$ to a query decision. We use the notation $\textbf{Q}_{j}:\mathcal{X}\rightarrow\{0,1\}$ to denote the query function used after seeing the first $j-1$ examples. Thus, our query indicator $Q_{j}$ is simply the instantiation $\textbf{Q}_{j}(x_{j})$. In this section, we work with an individual label $y$ and omit the explicit dependence in all our arguments and notation. For notational convenience, we use $z_{j}=(x_{j},c_{j},Q_{j})$ and with $g^{\star}(\cdot)=f^{\star}(\cdot;y)$, we define

Note that $\xi_{j}$ is a centered random variable, independent of everything else. We now introduce some standard concepts from martingale theory for the proof of Theorem 9.

For a dependent sequence $z_{1},\ldots,z_{i}$ we use $z_{1}^{\prime},\ldots,z_{i}^{\prime}$ to denote a tangent sequence, where $z_{j}^{\prime}|z_{1:j-1}\overset{d}{=}z_{j}|z_{1:j-1}$, and, conditioned on $z_{1},\ldots,z_{i}$, the random variables $z_{1}^{\prime},\ldots,z_{i}^{\prime}$ are independent.

A tree process $\mathcal{Q}$ is a binary tree of depth $i$ where each node is decorated with a value from $\{0,1\}$. For a Rademacher sequence $\epsilon\in\{-1,1\}^{i}$ we use $\mathcal{Q}_{i}(\epsilon)$ to denote the value at the node reached when applying the actions $\epsilon_{1},\ldots,\epsilon_{i-1}$ from the root, where $+1$ denotes left and $-1$ denotes right.

The proof follows a fairly standard recipe for proving uniform convergence bounds, but has many steps that all require minor modifications from standard arguments. We compartmentalize each step in various lemmata:

In Lemma 8, we perform symmetrization and introduce Rademacher random variables and the associated tree process.

In Lemma 9 we control the symmetrized process for finite $\mathcal{G}$.

In Lemma 10, we use the covering number to discretize $\mathcal{G}$.

We now state and prove the intermediate results.

Let $Z=(z_{1},\ldots,z_{i})$ be the sequence of $(x,c,Q)$ triples and let $Z^{\prime}=(z_{1}^{\prime},\ldots,z_{i}^{\prime})$ be a tangent sequence. Then for $\beta_{0}\geq\beta_{1}>0$ if $\tau\geq\frac{4(1+\beta_{1})^{2}}{(\beta_{0}-\beta_{1})}$, then

We derive the first inequality, beginning with the right hand side and working toward a lower bound. The main idea is to condition on $Z$ and just work with the randomness in $Z^{\prime}$. To this end, let $\hat{g}$ achieve the supremum on the left hand side, and define the events

Since we have defined $\hat{g}$ to achieve the supremum, we know that

Since we are working conditional on $Z$, we can leverage the independence of $Z^{\prime}$ (recall Definition 4) to bound the variance term.

where the last step uses the requirement on $\tau$. This establishes the first inequality.

For the second inequality the steps are nearly identical. Let $\hat{g}$ achieve the supremum on the left hand side and define

Using the same argument, we can lower bound the right hand side by

Applying Chebyshev’s inequality yields the same expression as for the other tail. ∎

Using the same notation as in Lemma 7, we have

the same bound holds on the lower tail with $(1-\beta_{1})$ replacing $(1+\beta_{1})$.

For this proof, we think of $Q_{j}$ as a binary variable that is dependent on $z_{1},\ldots,z_{j-1}$ and $x_{j}$. Similarly $Q_{j}^{\prime}$ depends on $z_{1},\ldots,z_{j-1}$ and $x_{j}^{\prime}$. Using this notation, and decomposing the square loss, we get

Here we have introduce the short forms $T_{1,j},T_{2,j}$ and the primed version just to condense the derivations. Overall we must bound

Observe that in the final term $T_{1,i},T_{1,i}^{\prime}$ are random variables with identical conditional distribution, since there are no further dependencies and $(x_{i},\xi_{i},Q_{i})$ are identically distributed to $(x_{i}^{\prime},\xi_{i}^{\prime},Q_{i}^{\prime})$. As such, we can symmetrize the $i^{\textrm{th}}$ term by introducing the Rademacher random variable $\epsilon_{i}\in\{-1,+1\}$ to obtain

Here in the final expression the outer expectation is just over the variables $x_{j},x_{j}^{\prime},\xi_{j},\xi_{j}^{\prime}$ and the bracket notation denotes interleaved supremum and expectation. Expanding the definitions of $T_{1,i},T_{2,i}$, we currently have

Next we use the standard trick of splitting the supremum over $g$ into a supremum over two functions $g,g^{\prime}$, where $g^{\prime}$ optimizes the primed terms. This provides an upper bound, but moreover if we replace $\tau$ with $\tau/2$ we can split the indicator into two and this becomes

The tree process $\mathcal{Q}$ arises here because the interleaved supremum and expectation is equivalent to choosing a binary tree decorated with values from $\{0,1\}$ and then navigating the tree using the Rademacher random variables $\epsilon$. The bound for the other tail is proved in the same way, except $(1+\beta_{1})$ is replaced by $(1-\beta_{1})$. ∎

The next lemma is more standard, and follows from the union bound and the bound on the Rademacher moment generating function.

For any $x_{1:i},\xi_{1:i},\mathcal{Q}$, and for finite $\mathcal{G}$, we have

The same bound applies for the lower tail.

Applying the union bound and the Chernoff trick, we get that for any $\lambda>0$ the LHS is bounded by

Let us examine the $i^{\textrm{th}}$ term conditional on $\epsilon_{1:i-1}$. Conditionally on $\epsilon_{1:i-1}$, $\mathcal{Q}_{i}(\epsilon)$ is no longer random, so we can apply the MGF bound for Rademacher random variables to get

Observe first that if $v$ is the covering element for $g$, then we are guaranteed that

since $g,v,g^{\star}\in$. Thus, adding and subtracting the corresponding terms for $v$, and applying these bounds, we get a residual term of $i\alpha(2(1+\beta_{1})+2+2\beta_{1})=4i\alpha(1+\beta_{1})$. ∎

Now let $V(X)$ be the cover for $\mathcal{G}$ at scale $\alpha=\frac{\tau}{32i(9/8)}=\frac{\tau}{36i}$, which makes $\tau/4-4i(1+\beta_{1})\alpha=\frac{\tau}{8}$. Thus we get the bound

This entire derivation requires that $\tau\geq\frac{4(9/8)^{2}}{(1/8)^{2}}=324$.