Annotation Efficiency: Identifying Hard Samples via Blocked Sparse Linear Bandits

In niche industrial applications such as Named Entity Recognition (Nguyen et al., 2023) and learning tasks on low-resource languages (Hedderich et al., 2021), obtaining high-quality labels is challenging due to the lack of expert annotators. However, high-quality labels are critical for effective model training (Li et al., 2023), and thus, expert annotators must provide ground truth labels. (Sorscher et al., 2022) demonstrated that selecting high-quality data can reduce the power-law association of test error with dataset size to an exponential law. In annotation-expensive tasks with large volumes of unlabeled data, the challenge is to select a representative subset of datapoints for labeling. In label-scarce tasks, where the number of expert annotators is extremely low, often only one, it is impractical to query the same datapoint multiple times. While crowd-sourcing literature reduces noise by aggregating labels from multiple annotators (Verroios & Garcia-Molina, 2015), the annotation from a single or aggregated expert is considered the final ground truth label in our setting. We term this restriction, where a datapoint cannot be re-queried after annotation, the blocking constraint. Additionally, the annotation budget is typically much smaller than the datapoint embedding dimension. An efficient annotation strategy should be sequential (instead of one-shot) in such cases, as each annotation informs future decisions and helps identify more informative datapoints.

In addition, data-pruning techniques like coreset selection emphasize selecting hard examples (Maharana et al., 2023), while (Sorscher et al., 2022) justifies this for perceptron learning. Curriculum learning (Bengio et al., 2009) also uses increasingly difficult examples, but defining the ‘hardness’ of unlabeled data is ambiguous. Hard examples identified by heuristics are often noisy, mislabeled, or outliers (Mindermann et al., 2022). To address this, we propose soliciting annotation difficulty feedback directly from expert annotators. This adds minimal annotation overhead and helps identify hard examples more reliably than heuristics. Additionally, leveraging expert feedback to learn and predict hardness (via an auxillary model) is simpler than addressing complex downstream task itself.

Thus, the primary problem we aim to solve is: “Given a small annotation budget $\mathsf{T}$, how should we sequentially identify unique and difficult unlabeled datapoints for annotation as we receive expert feedback on hardness of annotation?” Theoretically, we model this sequential decision-making process using sparse linear bandits with a blocking constraint. Specifically, suppose we have a large set $\mathcal{A}$ of $\mathsf{M}$ unlabeled datapoints, each associated with a $d$-dimensional embedding. With $\mathsf{T}$ rounds available, at each round $t\in[\mathsf{T}]$, a datapoint $\mathbf{a}_{t}$ is selected for annotation, and the expert provides noisy feedback $r_{t}$ on the difficulty of labeling that datapoint, along with the ground truth label. To address the limited annotation budget and the relevance of a few important features in high-dimensional spaces (Hao et al., 2020), we model the expected hardness as a sparse linear function of the embedding. We ensure robustness to sparsity - our theoretical guarantees degrade gracefully as the parameter vector becomes less sparse, i.e., as it deviates from sparsity due to an increasing tail.

Although our primary motivation comes from data selection for annotation in a label-scarce regime, our theoretical framework is broadly applicable. For example, resource-constrained edge devices, such as smartphones, consider the problem of recommendation of personalized products. In applications such as movie/book recommendations, typical users will hardly consume an item more than once - so any feedback provided is not subject to change. Furthermore, the user will provide feedback for every item (books/movies) in a large repository of items. Here, our theoretical framework (sparse linear bandits with blocking constraint) is directly applicable as it involves learning unknown user taste from sequential item recommendations based on user feedback. While existing literature addresses this by combining feedback from multiple users (Bresler et al., 2014; Pal et al., 2024), such algorithms compromise user privacy. Our framework will not have this limitation.

Our Contributions and Techniques: The sparse linear bandits framework in the data-sparse regime was first studied by Hao et al. (2020); Jang et al. (2022) - however, these works do not consider either the blocking constraint or robustness to sparsity - both of which pose novel technical challenges. We propose BSLB (Blocked Sparse Linear Bandits), an efficient algorithm in this setting which is primarily an Explore-Then-Commit algorithm. In the exploration period, we carefully choose a subset of arms from which we sample without replacement - the goal is to ensure that the expected covariance matrix has a large minimum eigenvalue. In the exploitation period, we use a lasso estimator to estimate the unknown model parameters while being robust to sparsity. The optimal exploration period depends on the correct sparsity level of the unknown parameter vector, which is difficult to set in practice. Therefore, we also present a meta-bandit algorithm based on corralling a set of base bandits algorithms (Agarwal et al., 2017) - obtaining the same order-wise regret guarantees but without needing the knowledge of hyperparameters. Below, we summarize our main contributions:

1. 1.

   We theoretically model the problem of identifying hard (informative) unlabeled datapoints by high dimensional sparse linear bandits framework with blocking constraint - the number of rounds or annotation budget is very small, even smaller than the ambient dimension. The hardness is modeled as a sparse linear function of the datapoint embedding - we allow for robustness to sparsity in the parameters where the tail magnitude is non-zero and unknown.

2. 2.

   We propose an efficient “explore then commit” (ETC) algorithm BSLB for regret minimization in our framework (Theorem 2) that achieves a regret guarantee of $O(k^{1/3}\mathsf{T}^{2/3}+k^{-1/12}\beta_{k}^{1/2}\mathsf{T}^{5/6})$ for a fixed sparsity $k$ and the corresponding tail magnitude $\beta_{k}$ - for the special case of hard sparsity (tail magnitude $\beta_{k}=0$), BSLB achieves a regret guarantee of $O(k^{1/3}\mathsf{T}^{2/3})$ (Corollary 2). The run-time of BSLB is polynomial in the number of datapoints and is therefore efficient.

3. 3.

   A novel ingredient (function GetGoodSubset()) in the proposed algorithm BSLB is to select a good set of representative datapoints from the large set of unlabelled datapoints. This objective entails solving a discrete non-convex optimization problem in Equation 2. We propose a convex relaxation of the objective and obtain a feasible solution via randomized rounding - Theorem 3 states that our computationally efficient algorithm has good approximation guarantees.

4. 4.

   BSLB requires knowledge of sparsity $k$ (which also controls the tail magnitude $\beta_{k}$) to set exploration period length. Since this is challenging to set in practice, we propose a meta-algorithm C-BSLB that combines base algorithms with different exploration periods. C-BSLB achieves same regret guarantees order-wise (Theorem 4) as BSTB but without knowledge of sparsity.

5. 5.

   To validate our hypothesis and theory, we present experiments on the public image classification dataset PASCAL VOC 2012. Additional experiments on text classification on SST-2 and personalized recommendation with MovieLens, Jester, and Goodbooks datasets are in Appendix A.2.

Technical Challenges: At a high level, our proof follows a similar structure as in the analysis of Algorithm ESTC proposed in (Hao et al., 2020). First of all, both in (Hao et al., 2020) and our setting, there are no assumptions on the datapoint embeddings - unlike most existing literature on sparsity where the Gram matrix is assumed to satisfy Restricted Isometry Property (RIP) (Boche et al., 2015). A much weaker condition (namely Restricted Eigenvalue (RE)) in characterizing nice statistical guarantees of the Lasso estimator for sparse linear regression was shown in (Bickel et al., 2009; Rudelson & Zhou, 2013) - it was shown that if the covariance matrix of a distribution satisfies RE, then a sufficient number of independent samples will also satisfy RE. However, in our setting, the additional blocking constraint and our desired robustness to sparsity present three significant technical challenges. (A) Sampling: While the above techniques can be used directly in the analysis of Algorithm ESTC, the blocking constraint in our setting entails that sampling of datapoints cannot be independent in the exploration phase. (B) Statistical guarantees: To the best of our knowledge, when the Gram matrix only satisfies RE, the statistical guarantees of the Lasso estimator hold only for hard sparse vectors - for these vectors, all but $k\ll d$ entries are zero. Existing guarantees for soft sparsity (non-zero tail) hold only for Gram matrices satisfying the stronger RIP condition (Wainwright, 2019). (C) Knowledge of hyper-parameters: Our first proposed algorithm BSLB (similar to ESTC) requires as input a fixed sparsity $k$ (corresponding tail magnitude $\beta_{k}$). If the input sparsity is too low or too high, then the regret guarantee will not be reasonable. However, it is challenging to set the sparsity parameter without having the knowledge of parameter vector itself. We resolve all technical challenges with novel techniques - in particular, the latter two might be of independent interest in other applications.

To resolve (A), we need to optimize for a probability distribution on datapoints (for sampling) with a well-conditioned expected covariance matrix under the constraint that it is uniform on a subset of datapoints and has zero mass on others. The related optimization problem is discrete and non-convex - we describe a convex relaxation of the objective and show a randomized rounding procedure to obtain a feasible solution with good approximation guarantees on the minimum eigenvalue of the expected covariance matrix. Subsequently, we show that subsampling from the recovered distribution in the exploration component ensures that the data covariance matrix satisfies RE with high probability. To resolve (B), we follow two steps 1) We extend guarantees in (Rudelson & Zhou, 2013) (Theorem 23) that demonstrates a variant of restricted isometry - the idea is that the data matrix acts as a near isometry on the image of all sparse vectors under a linear transformation. Such a technique, in turn, allows us to extend RE guarantees for design matrices whose rows are sampled without replacement 2) using the RE condition we derive guarantees for soft sparsity from the results on hard sparse vectors using an iterative approach to ensure robustness ((Boche et al., 2015) Theorem 1.6). For (C), we use a corralling algorithm based on the techniques of (Agarwal et al., 2017) that combines several base algorithms and provides guarantees with respect to the optimal one. However, a naive application leads to an additional corralling cost with a linear dependence on dimension $d$, making the regret vacuous ($\mathsf{T}\ll d$). We use a covering argument - we only choose a small representative subset (covering set) of base algorithms for input to corralling and show that for all remaining base algorithms, their regret is close enough to a base algorithm in the covering set.

Related Work: Conceptually our work is similar to active learning (Settles, 2009; Lesci & Vlachos, 2024) where unlabeled samples are annotated adaptively, based on the confidence of a trained model (Coleman et al., 2022). Active learning works well with good initialization and informative confidence intervals. However, in our label-scarce setting, active learning is particularly challenging with complex data due to the absence of a reliably trained model in the first place - this is more pronounced for difficult datapoints for which prediction is hard. Active Learning (AL) needs an initial set of high-quality labeled samples to reasonably train a model - also known as the cold-start problem - when labels are scarce, uncertainty based sampling techniques (AL) are unsuitable (Li et al., 2024). Our goal is to identify informative samples with the help of the expert annotator(s), whom the final model aims to emulate. Coreset selection (Guo et al., 2022; Albalak et al., 2024; Sener & Savarese, 2018) aims to select a subset of datapoints for training. However, coreset selection assumes that a large amount of labeled data already exists, and the focus is on reducing computational costs. In contrast, our setting deals with the lack of labeled data, making existing coreset selection approaches, which rely on the entire labeled dataset, inapplicable. Our work also aligns with curriculum learning (Bengio et al., 2009), where a model is trained on samples of increasing difficulty/complexity. Due to the ambiguity in hardness definition, often heuristics are used to infer the difficulty of samples (Soviany et al., 2022) and can turn out unreliable and not generalizable. For niche tasks where an expert annotator is available, the difficulty ratings from the annotator are more informative since the goal is to train a model to mimic the expert. In computer vision, there has been recent work regarding estimating the difficulty of a dataset for the model using implicit difficulty ratings of annotation (Ionescu et al., 2016; Mayo et al., 2023). For NLP tasks, Ethayarajh et al. (2022) constructs information theoretic metrics to estimate the difficulty of data points.

Notation: We denote vectors by bold small letters (say x), scalars by plain letters (say $x$ or $\mathsf{X}$), sets by curly capital letters (say $\mathcal{X}$) and matrices by bold capital letters (say $\mathbf{X}$). We use $[m]$ to denote the set $\{1,2,\dots,m\}$, $\|\mathbf{x}\|_{p}$ to denote the $p$-norm of vector x. For a set $\mathcal{T}$ of indices $\mathbf{v}_{\mathcal{T}}$ is used to denote the sub-vector of $\mathbf{v}$ restricted to the indices in $\mathcal{T}$. $\lambda_{\min}(\mathbf{A})$ denotes the minimum eigenvalue of the matrix $\mathbf{A}$ and $\mathsf{diag}(\textbf{x})$ denotes a diagonal matrix with entries as x. We use $\mathcal{B}^{d}$ and $\mathcal{S}^{d-1}$ to denote the unit ball and unit sphere in $d$ dimensions, respectively. We will write $\mathbb{E}X$ to denote the expectation of a random variable $X$. $\widetilde{O}(\cdot)$ notation hides logarithmic factors in $\mathsf{T},\mathsf{M},d$.

Our main contribution is to propose an Explore-Then-Commit (ETC) algorithm named BSLB which is summarized in Algorithm 1. BSLB takes as input a set of unlabeled datapoints (arms) $\mathcal{A}$, the annotation budget (time horizon) $\mathsf{T}$, the exploration budget $\mathsf{T}_{\text{explore}}$ and Subset selection parameter $\hat{g}$. Steps 2-8 of BSLB correspond to the exploration component in the algorithm. In Step 2, we first compute a good subset of arms $\mathcal{G}\subset\mathcal{A}$ (using function $\textsc{GetGoodSubset}(\mathcal{A},\hat{g})$) which comprises of representative arms that cover the $d$-dimensional space reasonably well. Subsequently, in Steps 4-8, we sample arms without replacement from the set of arms $\mathcal{G}$ for $\mathsf{T}_{\text{explore}}$ rounds. The goal in the exploration component is to select a subset of arms such that the image of sparse vectors under the linear transformation by the gram matrix of the selected set has a sufficiently large magnitude (see Definition 1). As we prove, such a result ensures nice statistical guarantees of the parameter (difficulty) estimation with the subset labeled (with difficulty scores) at the end of the exploration component. Since the set of arms, $\mathcal{A}$ can be arbitrary, note that sampling arms uniformly at random from the entire set might not have good coverage - especially when most arms are concentrated in a lower-dimensional subspace. Therefore, finding a good representative subset of arms leads to the following discrete optimization problem

The function $\textsc{GetGoodSubset}(\mathcal{A},\hat{g})$ approximates the solution to this computationally infeasible discrete optimization. We maximize a relaxed concave program in equation 6 efficiently for a chosen input parameter $\hat{g}$ to obtain a distribution $\hat{\bm{\mu}}$ on the set of arms $\mathcal{A}$ - subsequently, we construct the subset $\mathcal{G}$ using randomized rounding (Step 19) with $\hat{\bm{\mu}}$ to obtain a feasible solution to 2.

The second part of BSLB (Steps 9-14) corresponds to the exploitation component of the algorithm. In Step 9, we use the Lasso estimator to get an estimate $\widehat{\bm{\theta}}$ of the unknown parameter vector $\bm{\theta}\in\mathbb{R}^{d}$. Note that the number of samples used in obtaining the estimate $\widehat{\bm{\theta}}$ is much smaller than the ambient dimension $d$. Finally, in Steps 11-14, we choose datapoints that are predicted to be hard according to our recovered estimate $\widehat{\bm{\theta}}$ and submit them for annotation. At every round in BSLB, no arm is pulled more than once, thus respecting the blocking constraint. It is important to note that BSLB is two-shot. That is, we change our data acquisition strategy only once after the exploration component - thus making our algorithm easy to use in practice. Next, we move on to our main theoretical results.

Below, we demonstrate our methods for annotation in a label-scarce setting for image classification on the PASCAL VOC 2012 dataset. Additional experimental results on SST-2 (text dataset) can be found in Appendix A.2.3. Finally, experiments on the MovieLens, Netflix, and GoodBooks datasets in the context of personalized recommendation with few labeled data using our theoretical framework are in Appendix A.2.1. Finally, we provide detailed simulations in Appendix A.2.4.

We consider the setting where we have a total of $\mathsf{M}$ unlabelled samples (with $\mathsf{T}\ll\mathsf{M}$) and only $\mathsf{T}$ datapoints can be annotated (sequentially). For each unlabeled data point sent for annotation to the expert(s), we receive the ground truth label and the difficulty score $r_{t}$ corresponding to the difficulty in annotating the data point. We showcase the effectiveness of BSLB (Alg. 1) in our experimental set-up with real-world datasets. Given a model $\mathcal{M}$ to be trained on a downstream task, to benchmark BSLB, we consider the following set of baselines (to compare against) to choose subset of datapoints for annotation and subsequent training of the aforementioned model $\mathcal{M}$:

1. 1.

   Random: Subset of $\mathsf{T}$ unlabeled datapoints chosen uniformly at random

2. 2.

   All: All the samples in training data (except the validation fold)

3. 3.

   AnchorAL (Lesci & Vlachos, 2024): an anchoring based active learning baseline ($\mathsf{T}$ samples).

4. 4.

   SEALS (Coleman et al., 2022): a KNN based sub-sampling active learning baseline ($\mathsf{T}$ samples).

$\tau_{\text{easy}},\tau_{\text{hard}}$ (thresholds on difficulty score to determine easy/hard samples) and $\mathsf{T}_{\text{explore}}$ (exploration rounds) are relevant hyper-parameters specified for the corresponding experiments ²²2We consider the AL setup initialized with $\mathsf{T}_{\text{explore}}$ samples and $\mathsf{T}-\mathsf{T}_{\text{explore}}$ samples queried in a batch.. We benchmark learning performance on 2 datasets: a) $N_{\text{valid}}$ hard samples (samples with difficulty $>\tau_{\text{hard}}$) (hard-valid) b) $N_{\text{valid}}$ easy samples (samples with difficulty ratings $<\tau_{\text{easy}}$) (easy-valid).

AnchorAL and SEALS are state-of-the-art active learning (AL) algorithms. In general, for a label-scarce complex task, AL might not be immediately applicable (see cold-start problem in Li et al. (2024)) - especially for datapoints close to the decision boundary with noisy/less informative confidence intervals. This is because AL requires a reliably trained model on an even smaller subset of labeled datapoints - however, on datapoints far from the decision boundary (easy datapoints), noisy confidence signals are still useful. As we show in our experiment, this intuition holds, and the AL models, along with the random baseline, perform well on the easy-valid dataset. It is worth noting that complex (hard) datapoints often tend to be the main challenge in industrial applications. This is because it is easy to improve performance on easy data (cheaper to obtain) by simply increasing samples during training, but hard datapoints are difficult to generalize on (Pukowski & Lu, 2024).

Image Classification on PASCAL VOC 2012: Our main result is for the image classification task on the public image dataset, PASCAL VOC 2012 (Everingham et al., 2015). The dataset has $11,540$ unique images and comprises segmentations for $20$ objects. In addition to the image dataset, we use difficulty scores of annotations from (Ionescu et al., 2016) - the authors have provided the visual search difficulty by measuring the time taken to annotate in a controlled environment. The annotation task here was to identify if an image contains a particular object, e.g. “Does this image contain a car”. The authors derive a difficulty score between $0$ and $8$ by normalizing the time to annotate.

In our experiment, the goal is to train a learning model for image classification - $\mathcal{M}$ is a support vector machine (SVM) head attached to a frozen pre-trained vision transformer (ViT) model pre-trained on ImageNet-21k dataset (Wu et al., 2020). We present results on the classification task - given an input image, predict if the image has an object or not. We consider $4$ different objects, namely chair, car, bottle, and (bottle or chair). The last object is an OR conjunction of two labels. We consider the thresholds as $\tau_{\text{easy}}=3.1$ and $\tau_{\text{hard}}=3.9$ since the distribution of the difficulty scores in the dataset is heavy-tailed as shown in Figure 4(b). The (image, question) tuple with difficulty scores in the range $[3.1,3.8]$ are highly noisy and therefore have been excluded. Table 2 contains the hyperparameters $\mathsf{T}$, $\mathsf{T}_{\text{explore}}(\approx 0.6\mathsf{T})$ used and the number of samples in the all dataset for the different object classification tasks, along with the size of the validation datasets hard-valid and easy-valid and aggregaged accuracies. Table 3 contains results on the effect of varying $\mathsf{T}_{\text{explore}}$.

We present our results in Table 1 averaged over $5$ validation folds. For this classification task, our method (BSLB) efficiently selects datapoints (to be annotated) compared to baselines with an equal number of samples. Regarding the quality of the final trained model $\mathcal{M}$, the learning performance of BSLB on easy-valid is within $2\%$ of that obtained by the baseline random. However, there is an improvement of $5-14\%$ on the hard validation data hard-valid. When compared to the active learning baselines (AnchorAL and SEALS), BSLB performs better by $1-4\%$ on easy-valid and by $3.5-7\%$ on hard-valid. Finally, when compared to $\mathcal{M}$ trained on all datapoints (all baseline), which has $6\times$ to $12\times$ more samples, our method does better ($0.7\%$ to $8.6\%$) on the hard-valid and does decently on easy-valid ($<3\%$ difference). These results validate our theory - in particular, we find that performance on easy-valid improves if the model $\mathcal{M}$ is trained on more samples (randomly chosen to improve coverage). However, improving the performance on hard-valid dataset is the main challenge where our simple approach BSLB with theoretical guarantees does reasonably well.

This work formulates the problem of adaptive annotation with expert-provided difficulty feedback as regret minimization in blocked sparse linear bandits. The goal is to annotate difficult samples to improve generalization on hard datapoints, assuming difficulty ratings are linked to sample features by an unknown parameter. We consider the practical consideration when each sample can be annotated once and only a few rounds of annotations are available. We propose an explore-then-commit algorithm BSLB, a two-shot algorithm for unlabelled data-point selection (for annotation). We show theoretical results establishing the sub-linear regret of the proposed BSLB algorithm - we also ensure that our guarantees work with minimum assumptions on datapoints and are robust to sparsity. Finally, we present a meta-algorithm C-BSLB that corrals BSLB algorithms with different input parameters - the result is a bandit algorithm that suffers the same regret orders as BSLB without the knowledge of the optimal sparsity hyper-parameter. Numerical studies on real-life image and text datasets show the efficacy of our methods in the label-scarce regime. We demonstrate experiments in the appendix for recommendation and simulation setup using our theoretical framework and BSLB.

Future Work: Theoretically speaking, lower bounds on regret guarantees in the sparse linear bandits framework with blocking constraint is an open problem. Algorithmically, it will also be interesting future work to obtain an algorithm that achieves $O(\sqrt{\mathsf{T}})$ in our bandit setting. Our experimental results are done on classifying state-of-the-art embeddings; however, more extensive experimentation can be considered in future work, especially for creating datasets used for generative tasks.