Minimizing Human Intervention in Online Classification

1. Problem Definition

The paper addresses the challenge of training or fine-tuning Large Language Model (LLM) based classification systems (e.g., for question answering or customer support) where human expert feedback is costly. The goal is to design an online learning agent that minimizes the cumulative cost of interacting with an expert while maintaining high accuracy.

Formal Setting:

• Input: At each round $t$, an agent receives a query embedding $q_t \in \mathbb{R}^d$ drawn i.i.d. from an unknown distribution $\mu$.
• Labels: There are $N$ latent labels. The expert labeling policy is defined by a partition of the embedding space into regions $C_1, \dots, C_N$ (often modeled as a Voronoi tessellation based on unknown "seed" points).
• Actions: The agent must assign a label to $q_t$. It has two choices:
  1. Guess: Predict a label immediately. If correct, it gains a reward; if incorrect, it incurs a penalty. Crucially, no ground truth is revealed if the agent guesses.
  2. Consult Expert: Ask for the true label. This incurs a cost (negative reward) but reveals the ground truth, which is added to the agent's dataset.
• Objective: Minimize Regret, defined as the difference between the cumulative reward of an Oracle (who knows the true partition and never makes mistakes) and the agent's cumulative reward. Regret accumulates from both expert calls and incorrect guesses.

2. Methodology

The authors propose three algorithms tailored to different regimes of the time horizon $T$ (total queries) and the embedding dimension $d$.

A. Conservative Hull-based Classifier (CHC)

• Target Regime: Large horizons ($T \geq e^d$).
• Mechanism: The agent maintains a set of "expert-labeled" queries for each class. It constructs the convex hull (or spherical convex hull for unit spheres) of these points for each class.
• Decision Rule:
  • If a new query $q_t$ falls inside the convex hull of class $i$, the agent predicts label $i$.
  • If $q_t$ falls outside all known hulls, the agent calls the expert.
• Key Property: CHC is "conservative"; it never makes an incorrect prediction because the convex hull of points labeled $i$ is guaranteed to be a subset of the true region $C_i$ (assuming convex regions).
• Complexity: Checking if a point is in a convex hull is formulated as a linear program, solvable in polynomial time.

B. Center-based Classifier (CC)

• Target Regime: Short horizons ($T \leq e^d$) with specific distributional assumptions (Subgaussian mixtures with well-separated centers).
• Mechanism:
  • Phase 1 (Explore): Query the expert until every label has been observed sufficiently to estimate the "seed" (center) of each class accurately.
  • Phase 2 (Commit): Stop querying the expert. Predict the label of the nearest estimated center.
• Assumption: Requires the true class centers to be sufficiently separated relative to the noise variance and dimension.

C. Generalized Hull-based Classifier (GHC)

• Target Regime: Practical, high-dimensional settings (bridging the gap between CHC and CC).
• Mechanism: An extension of CHC that introduces a tunable threshold parameter $\tau \in [0, 1]$.
• Decision Rule: Instead of strictly waiting for a query to be inside a hull, the agent guesses label $i$ if the distance from $q_t$ to the hull of class $i$ is significantly smaller than the distance to any other hull (specifically, $d(q_t, \hat{C}_i) \leq \tau \cdot \min_{j \neq i} d(q_t, \hat{C}_j)$).
• Trade-off:
  • $\tau = 0$: Equivalent to CHC (conservative, no mistakes).
  • $\tau = 1$: Aggressive guessing (never calls expert once hulls are non-empty).
  • Tuning $\tau$ allows balancing the cost of expert calls against the risk of incorrect guesses, particularly effective when the data distribution is concentrated around class seeds.

3. Key Contributions

Theoretical Guarantees

• CHC Regret Bounds: The authors prove that CHC achieves a regret of $O(\log^d T)$ for arbitrary convex polytope partitions. This bound is distribution-free and robust.
  • For $d=1$, CHC is proven to be minimax optimal, matching the lower bound of $\Omega(\log T)$.
• CC Regret Bounds: For subgaussian mixtures with $T \leq e^d$, CC achieves regret proportional to $N \log N$ (where $N$ is the number of labels), provided the centers are well-separated.
• Lower Bounds: The paper establishes that in adversarial settings, linear regret is unavoidable, justifying the i.i.d. assumption.

Algorithmic Innovations

• Geometric Approach: The work leverages convex geometry (convex hulls, flags of polytopes, gnomonic projections) to derive distribution-free bounds, a novel approach in online classification with partial feedback.
• Practical Extension (GHC): GHC bridges the theoretical gap between the "safe but slow" CHC and the "fast but risky" CC, offering a practical solution for high-dimensional LLM embeddings where $T$ may not be exponentially large relative to $d$.

Empirical Validation

• Datasets: Evaluated on synthetic data and real-world question-answering datasets (Quora Question Groups, ComQA, CQADupStack).
• Embeddings: Used state-of-the-art text embedding models (Nomic, E5, Mistral_E5) with dimensions ranging from 784 to 4,096.
• Results:
  • GHC outperforms baselines (Sequential k-Means, Active Multiclass Perceptron, and standard CC) across all settings.
  • High-dimensional benefit: Counter-intuitively, higher-dimensional embeddings (e.g., Mistral_E5) led to lower regret, likely due to better separation of class regions in high dimensions.
  • Threshold Tuning: Optimal performance was achieved with high thresholds ($\tau \approx 0.9$), indicating that in high-dimensional spaces, the geometry allows for aggressive guessing with minimal error.

4. Significance and Impact

• Cost Reduction: The framework provides a principled method to drastically reduce the reliance on expensive human annotators during the deployment of LLM-based systems.
• Theoretical Rigor: It moves beyond heuristic active learning by providing rigorous, distribution-free regret bounds that account for the geometric structure of embedding spaces.
• Scalability: The proposed algorithms are computationally efficient (polynomial time) and scalable to high-dimensional spaces typical of modern NLP, making them viable for real-world deployment.
• Future Directions: The work opens avenues for minimizing human intervention in other areas of foundation model adaptation, such as Reinforcement Learning from Human Feedback (RLHF) and continuous fine-tuning.

In summary, the paper successfully demonstrates that by exploiting the geometric properties of embedding spaces, one can design online classifiers that learn effectively from limited expert feedback, achieving near-optimal regret guarantees while significantly reducing human intervention costs.