Annotation Efficiency: Identifying Hard Samples via Blocked Sparse Linear Bandits

Authors: Adit Jain, Soumyabrata Pal, Sunav Choudhary, Ramasuri Narayanam, Vikram Krishnamurthy
Primary area: reinforcement learning
Keywords: High Dimensional Linear Bandits, Annotation Efficiency, Sparse Recovery, Online Learning

Abstract:
This paper considers the problem of annotating datapoints using an expert with only a few annotation rounds in a _label-scarce_ setting. We propose soliciting reliable feedback on difficulty in annotating a datapoint from the expert in addition to ground truth label. Existing literature in active learning or coreset selection turns out to be less relevant to our setting since they presume the existence of a reliable trained model, which is absent in the label-scarce regime. However, the literature on coreset selection emphasizes the presence of difficult data points in the training set to perform supervised learning in downstream tasks (Mindermann
et al., 2022). Therefore, for a given fixed annotation budget of $\mathsf{T}$ rounds, we model the sequential decision-making problem of which (difficult) datapoints to choose for annotation in a sparse linear bandits framework with the constraint that no arm can be pulled more than once (_blocking constraint_). With mild assumptions on the datapoints, our (computationally efficient) Explore-Then-Commit algorithm _BSLB_ achieves a regret guarantee of $\widetilde{\mathsf{O}}(k^{\frac{1}{3}} \mathsf{T}^{\frac{2}{3}}   +k^{-\frac{1}{2}} \beta_k + k^{-\frac{1}{12}} \beta_k^{\frac{1}{2}}\mathsf{T}^{\frac{5}{6}})$ where the unknown parameter vector has tail magnitude $\beta_k$ at sparsity level $k$. To this end, we show offline statistical guarantees of Lasso estimator with mild Restricted Eigenvalue (RE) condition that is also robust to sparsity. Finally, we propose a meta-algorithm _C-BSLB_ that does not need knowledge of the optimal sparsity parameters at a no-regret cost.  We demonstrate the efficacy of our _BSLB_ algorithm for annotation in the label-scarce setting for an image classification task on the PASCAL-VOC dataset, where we use real-world annotation difficulty scores.

Decision: reject
Reviewer scores: 5, 3, 6, 6

Reviews and discussion:
<thread>
creation date:
1730648915134

thread_type:
official_review

<thread_object>
creator: reviewer_9l3c

<content>
summary:
This paper studies the sample selection problem in active learning when the label budget is limited. The main contribution is to model this problem as a sparse linear bandit with a blocking constraint. To address this challenge, the authors propose an explore-then-commit algorithm incorporating several novel ingredients. Theoretical analysis demonstrates that the proposed algorithm achieves an $O(k^{1/3} T^{2/3} + k^{-\frac{1}{12}} \beta_k^{1/2} T^{5/6})$ bound and experiments are conducted to validate the effectiveness of the proposed method.

strengths:
- The paper presents an interesting formulation of the sample selection problem in active learning as a sparse linear bandit problem. Several innovative techniques are introduced to derive an algorithm with theoretical guarantees.
- This paper is well-written, with the authors clearly explaining the motivation, technical challenges, and main contributions.
- Empirical studies are conducted to validate the theoretically oriented methods.

weaknesses:
Overall, I do not see any major weaknesses in this paper, though several points are worth discussing:

- **Tightness of the Bound**: As mentioned in lines 349-351, the proposed method achieves the same $T^{2/3}$ regret bound as previous work under the hard sparsity condition. However, the lower bound for the soft sparsity condition remains unclear, and it is uncertain whether the $T^{5/6}$ dependence is tight.
- **Model Assumptions**: The paper considers a scenario where the hardness of the sample is generated from a linear model, which may not always hold in practical settings.

=====post-rebuttal=====
I have reviewed the author's rebuttal and the other reviews. I think the paper introduces several interesting algorithmic components to address the blocking constraint. However, I agree with the other reviewers' concerns about the problem setting and the discrepancy between the paper's goal (training an effective classifier) and its actual focus (identifying hard examples). I have lowered my score to reflect this.

questions:
- Could you provide more discussion on the lower bound of the problem? While establishing a precise lower bound may be challenging, it would be helpful to explain why achieving better results is difficult.
- Could you discuss how to handle cases with model misspecification, where the hardness of the sample is not generated by a linear model?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730661498930

thread_type:
official_review

<thread_object>
creator: reviewer_mzn1

<content>
summary:
This paper considers the problem of minimizing the regret between the hardness of the $T$ selected points and the top $T$ data points that have the top hardness, where $T$ is the budget number of rounds for the human experts to label. The paper treats each data point in the dataset as an arm (using linear bandit) and assumes a blocking constraint that each arm can only be pulled at most once. When the human expert is asked to label the data point, he/she is also asked to provide the hardness of this data point, which is assumed to have noise. The paper proposes an algorithm similar to explore-then-commit to solve the above problem and theoretically prove the upper bound of the algorithm. It also proposes another meta-algorithm that assumes less knowledge of the sparsity of the bandits. Finally, it compares its algorithm with other baselines algorithms using various datasets.

strengths:
1. This paper has a strong theoritical guarantee for the algorithms it propose.
2. It compares its algorithm with various datasets, ranging from image, texts, and traditional ml datasets.

weaknesses:
1. The motivation and problem setting confuse me, especially for the paragraph from line 67 to line 76. Does the label-scarce regime only applies to the assumption that 'each arm can be pulled at most once'? What are other specialities about this regime. This regime is also kind of broad as many active learning framework is under the assumption that the label is scarce so we want to actively choose valuable data points to sample. Can the authors also elaborate on what the exact use cases of the setting considered in the paper can be applied to the recommendation of perconalized products as described in that paragraph?
2. The assumption that the human will provide noisy hardness is valid, but given this assumption, why do the authors not consider the labels provided by the human expert are also noisy? Can the authors provide more insights or explicit explanations on possible noisy labels?
3. It also feels that the labels provided by the human expert is irrelevant in the problem setting as both the problem formulation and algorithm 1 focuses on getting the human feedback for the hardness $r$ rather than mentioning about the labels. If that is the case, will it be possible to just asking the users for the hardness of the datapoint? How will this affect the algorithm?

questions:
1. What does a reliable trained model mean, does it mean the training data is 100% accurate or something else?
2. why this reliable trained model is absent in the label-scarce setting?
3. what kind of label does the human expert provide to the model? binary or multi-class?
4. Perhaps it is trivial, can the authors explain why the noise $\eta_t$ disappears from equation 1, is it due to condition 1 in line 191? But since equation 1 is not an expectation term, it confuses me. 
5. can the authors explain the technical difficulty in the lower bound, though it mentions that it is an open problem in the end. What is the "most likely" lower bound for this problem? As the authors mention that the upper bound could be improved to $T^{\frac{1}{2}}$.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730671526812

thread_type:
official_review

<thread_object>
creator: reviewer_bsgh

<content>
summary:
This paper studied a sparse linear bandit problem with an additional blocking constraints, i.e., no arm can be pulled more than once. The authors developed an explore-then-commit-type of algorithm which achieves a T^{2/3} regret guarantee with known sparsity level (and under certain assumptions). The authors also developed a corralling algorithm to deal with cases without knowing the sparsity level.

strengths:
It is nice to see that the authors develop their theoretical guarantees considering the effect of the tail magnitude $\beta_k$ at sparsity level $k$. The authors also provide a corralling algorithm to deal with cases without knowing the sparsity level.

weaknesses:
1. While the authors spend some efforts in trying to formulate their problem as a data labeling problem with a small labeling budget, I felt such setting is different from the problem the authors actually studied --- a sparse linear bandit problem with an additional blocking constraints. For instance, the objective of the proposed algorithm is to label data points that are hard to label to minimize the regret (covering the space was not the objective even though the proposed algorithm did that in order to minimize regret). But the objective of data labeling should be to learn a good classifier/regressor, which is inconsistent with your definition of the regret. Why not just formulating the problem as a sparse linear bandit problem?
2. The proposed algorithm only achieves a T^{2/3}-type of regret guarantee, which could be sub-optimal as a \sqrt{T}-type of guarantee is expected. Or the authors should provide a lower bound indicating that their guarantee is near-optimal in their setting.
3. In experiments, the proposed algorithm is completed in two rounds: exploration and exploitation. What about other active learning algorithms? Additionally, how do the other baselines incorporate the feedback on the hardness level? I'm also curious why the method of labeling all data points is outperformed by you algorithm in the hard-valid case.

questions:
See above.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730790246859

thread_type:
official_review

<thread_object>
creator: reviewer_dhzp

<content>
summary:
The paper addresses the challenge of efficiently annotating data points under the constraints of limited annotation rounds in a label-scarce environment. It proposes a novel methodology that integrates expert feedback on the difficulty of annotating specific data points, leveraging a sparse linear bandits framework. This approach focuses on selecting the most informative samples to annotate, which optimizes the use of scarce expert resources by prioritizing data points that are both challenging and representative. Theoretical results show the sub-linear regret of the proposed BSLB algorithm.

strengths:
1. The application of sparse linear bandits to annotation in a label-scarce environment addresses a significant practical problem in machine learning, particularly in situations where acquiring labeled data is expensive or logistically difficult. 
2. Introducing blocking constraints into the bandit problem formulation is novel and aligns well with practical scenarios where data points cannot be repeatedly annotated.
3. This paper provides a rigorous theoretical analysis on the regret which quantifies the efficiency of the BSLB algorithm. This analysis is backed by proofs that demonstrate how the algorithm effectively balances exploration and exploitation under sparsity and blocking constraints.

weaknesses:
1. It would be beneficial to make a more thorough comparison with the works that do not assume blocking constraints. Is there any instance where the blocking constraints would clearly fail for those existing algorithms like Hao et al. (2020)?
2. It would be good to move the definition and description of regret being concerned earlier in the paper. It might confuse the readers with the discussion on the regret without knowing what regret is being considered.

questions:
Is it possible to make some modifications to the existing sparse linear bandit algorithm to accommodate the blocking constraints? What are the key difficulties that the blocking constraints add to the problem?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731951308225

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Clarifications and Responses provided

comment:
We thank the reviewers for the considerable time and effort that they put into reviewing our work. We are glad that every reviewer has found our theoretical contributions to be strong. We have provided answers/clarifications to all the questions that were raised. in particular, several reviewers asked about a lower bound - we have also been able to prove that the lower bound in the data-scarce regime for blocked sparse linear bandits is $\Omega(\mathsf{T}^{2/3})$ (when parameter vector is hard sparse) just as in the case without blocking constraint (Hao et al.) Hence our algorithmic regret guarantees are order optimal.

We request the reviewers to kindly look at the responses and please let us know if their other questions asked have been answered. We will be happy to provide further clarifications if required. 

Thanks again
Authors
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper proposes a novel approach to the data annotation problem under a label-scarce environment using a sparse linear bandit with a blocking constraint. The Explore-Then-Commit (BSLB) algorithm aims to minimize regret by annotating the hardest data points, with theoretical guarantees and empirical validation showing its effectiveness.

Reviewers appreciated the novelty of applying sparse linear bandits to active learning but raised concerns about the weak connection between minimizing regret and the goal of data labeling. The focus on hardness feedback instead of labels was seen as misaligned with typical active learning objectives. The theoretical analysis was viewed as similar to existing work. There were also calls for a clearer problem objective, more comparisons with other active learning methods, and better handling of model misspecification and noisy labels.