Minimizing Human Intervention in Online Classification

AI summary

Overview

• Research area: Online/active learning, learning-to-defer, statistical learning theory, and the geometry of high-dimensional embeddings produced by language models.
• Technical level: Advanced. The paper leans heavily on convex geometry (convex polytopes, flags, spherical convex hulls, gnomonic projection) and regret analysis.
• Scope: The paper proposes three algorithms (CHC, GHC, and CC) for an online classification setting where an agent must decide, query by query, whether to answer using a language-model embedding or pay a costly human expert, and it derives regret guarantees for each.

What This Paper Is About

Question-answering and customer-support systems often begin with no knowledge at all: a human expert answers queries until the system has learned enough to handle them itself. Every expert call is expensive, so the system should make as few of them as possible. The paper formalizes this cold-start problem as active learning over embedding vectors, where at each round the agent either guesses a label (and receives no feedback) or calls an expert (and pays a cost), and the goal is to minimize cumulative regret relative to an oracle that has free expert access.

Key Contributions

1. Three algorithms. The Conservative Hull-based Classifier (CHC) builds convex hulls (or spherical convex hulls, on the unit sphere) of expert-labeled queries per label and calls the expert whenever a query falls outside all hulls. The Center-based Classifier (CC) queries the expert in an exploration phase, estimates the cluster centers, then predicts the nearest estimated center. The Generalized Hull-based Classifier GHC(τ) extends CHC with a tunable threshold τ ∈ [0, 1] that permits more frequent guessing.

2. Regret guarantees. CHC achieves regret 𝒪(log^d T) on the hypercube ℐ^d (d ≥ 2) and 𝒪(log^(d−1) T) on the unit sphere 𝒮^(d−1) (d ≥ 3). In dimension d = 1, CHC is shown to be minimax optimal. For queries from a subgaussian mixture and T ≤ e^d, CC attains regret proportional to N log N for equal mixture weights, where N is the number of labels.

3. A tunable bridge between regimes. GHC(τ) is designed for high-dimensional LLM embeddings, where CHC is too conservative because the number of expert-labeled queries must be at least linear in d for the hulls to have non-zero volume and exponential in d to cover a substantial portion of the space. Setting τ = 0 recovers CHC; setting τ = 1 means the expert is essentially never called once all hulls are non-empty.

4. Empirical validation. CHC, CC and GHC are evaluated on synthetic data and on real-world question-answering tasks using embeddings from various text embedding models. The paper reports that higher-dimensional embeddings significantly reduce overall regret, and that GHC outperforms CC and literature baselines in all settings.

Main Findings

• CHC never errs. By construction, each estimated set satisfies Ĉ_{i,t} ⊆ C_i, so CHC always returns the correct label; its regret therefore equals (β − α) times the expected number of expert calls, where β is the reward for a correct guess and α ≤ 0 the expert-call cost.
• Distribution-free bounds via flags. For a convex-polytope partition, the CHC bound scales with Σ_i F(C_i), the sum over cells of the number of flags F(P) of a polytope P. On the hypercube the bound is (β − α)(C/c)(Σ_i F(C_i)/((d+1)^{d−1} d!)) log^d(T) plus 𝒪(log^{d−1}(T) log log(T)); on the sphere it is (β − α)(KC/c)(Σ_i F(C_i)/(d^{d−2}(d−1)!)) log^{d−1}(T) plus 𝒪(log^{d−2}(T) log log(T)), where K = max_i (max_{y ∈ C_i} yᵀe_i / min_{y ∈ C_i} yᵀe_i)^d.
• Voronoi corollary. When the partition is a Voronoi tessellation, the total number of flags is controlled; the constant then includes (2e(N + 2d)/(d−1))^{d/2} on the hypercube and (2eN/(d−2))^{(d−1)/2} on the sphere, using the fact that each cell has at most N − 1 + 2d facets on the hypercube and at most N − 1 on the sphere.
• Minimax optimality in dimension one. Assuming ℰ = [0,1] and a non-atomic μ, R_CHC(T) ≤ 2(β − α)N log(T + 1) for all T ≥ 1. A matching lower bound holds for any algorithm: inf_π max_θ R_π(T, θ) ≥ (β − α)((N − 1)/(64√2)) log((T + 1)/2) = Ω((β − α)(N − 1) log T).
• CC in the short-horizon regime. Under the subgaussian-mixture assumption with separation δ_min² ≥ 80σ²d, and for T ≤ e^d, R_CC(T) ≤ (41/5)(β − α)(log N + 1)/p_min + 2(β − γ)(N + 1), where γ ≤ α is the reward for an incorrect guess and p_min the smallest mixture weight. With equal weights this is proportional to N log N.
• Why exploration is truncated. CC's exploration phase stops at the first round T₁ where every label i has been observed at least (108σ²/δ̂²_min(t))(d + 2 log T) times; this ensures the center-estimation error is at most δ_min/4 with high probability, which in turn makes the probability of a wrong guess in the commit phase exponentially small in d.
• The i.i.d. assumption is essential. The paper states that under an adversarial query distribution any algorithm must incur linear regret; in dimension one an oblivious adversary can binary-search the label boundary.
• Cost of raising dimension. The constant preceding the leading log^d T term actually decreases with d, which the authors attribute to a hidden, unresolved dimension dependence. They note that these bounds are most informative when T exceeds a threshold growing exponentially with d, consistent with results showing the expected volume of a convex hull of random points stays negligible until the sample count is exponential in d.
• CHC is not tuned to concentrated distributions. An asymptotic distribution-free lower bound, matching Theorem 3.1 when μ is uniform, suggests CHC does not exploit favorable cases where μ is highly concentrated around the seed queries.
• Computational feasibility. Convex hulls need never be computed (QuickHull-type algorithms have worst-case complexity exponential in d/2). Only hull membership must be checked, which is a linear program with n variables and n + d + 1 constraints on the hypercube, or n + d on the sphere, solvable in polynomial time by interior-point methods.

Methodology in Plain English

The authors imagine an agent that sees one query at a time, each represented by a d-dimensional vector (an embedding) drawn independently from an unknown distribution. There are N possible answer labels, and the true label of a query is determined by a hidden partition of the embedding space — in the concrete example, a Voronoi tessellation generated by one "seed" vector per label, so that a query is labeled by the nearest (or, on the sphere, the highest-cosine-similarity) seed. The agent either calls an expert, which reveals the true label and adds the query to its memory, or guesses, which yields no feedback at all. Performance is measured as regret against an oracle that always knows the answer.

The core idea is geometric. When the agent labels a query by calling the expert, that query lies inside its label's region. Because the regions are assumed to be convex polytopes, the convex hull of all previously labeled queries of a given label is guaranteed to sit inside that label's true region. So if a new query falls inside one of these hulls, the agent knows the answer for certain and can answer for free. Otherwise it calls the expert. This makes CHC a computationally cheap approximation of the classical CAL disagreement-based querying rule, restricted to convex partitions.

Because hulls in high dimensions stay tiny until the agent has an exponential number of samples, the authors add GHC(τ): instead of asking whether the query is inside a hull, it compares the query's distance to each hull's nearest point and guesses if one hull is within a factor τ of the closest competitor — a tunable risk knob. For the regime where T is at most e^d, they instead analyze CC, which simply calls the expert until every label has been seen enough times to estimate each cluster center accurately, then commits to nearest-estimated-center predictions. The theory is built by adapting known results on the expected volume of a convex hull of random points to bounded-density distributions and to the sphere via the gnomonic projection.

Why This Matters

The work gives the first regret-style treatment of the expert-deferral trade-off that is distribution-free over convex partitions, and it characterizes when learning the geometry is even possible: only once the horizon T grows exponentially in the embedding dimension d. This reframes a practical dilemma — bigger, better embeddings versus the massive query budget needed to exploit them — as a precise statistical statement.

Real-world applications:

• Customer support and question-answering systems that start cold and gradually reduce the number of tickets routed to human agents.
• LLM-based classification pipelines where fine-tuning or labeling requires costly human feedback and the system must decide when feedback is worth requesting.
• Interactive search and retrieval, where the system must decide whether to answer a query with a known label or escalate it.
• Streaming or news-feed labeling, where content arrives continuously and no labeled dataset exists at the outset.

Industry relevance: the algorithms are directly implementable (only linear programs, no hull computation) and the tunable threshold in GHC gives practitioners a single knob for trading accuracy against expert load, which is attractive for deployments where embedding dimension is large and annotation budgets are fixed.

Future Directions

• Remove the C/c dependence in the regret bounds. The authors conjecture this factor, which arises from the rejection-sampling step of the proof, is an artifact of the analysis and could be eliminated with a tighter argument.
• Extend the density-free bound from d = 1 to d ≥ 2. Whether the atom-free bound of Theorem 3.3 generalizes beyond one dimension is left explicitly open (Appendix E.4).
• Characterize the hidden dimension dependence. The counterintuitive decay of the leading constants with d touches on unresolved questions in convex geometry (Appendix E.3).
• Build and validate a single algorithm that works in all regimes. The authors suggest a hybrid that runs CC early and switches to CHC once T exceeds e^d, but present GHC(τ) as the more practical route; choosing τ automatically, and testing on further datasets and embedding models, remains open.

Target Audience

Researchers in statistical learning theory, active learning, and online learning who work on label-efficient or learning-to-defer systems; practitioners building cold-start question-answering or support systems on top of LLM embeddings; and readers with a background in convex geometry, probability, and regret analysis who want to understand the fundamental sample-size limits of geometry-based expert deferral. Specific dataset names, dataset sizes, embedding model names, and numerical experimental results are not reported in the provided content.

Authors’ abstract

Training or fine-tuning large language model (LLM)-based systems often requires costly human feedback, yet there is limited understanding of how to minimize such intervention while maintaining strong error guarantees. We study this problem for LLM-based classification systems in an active learning framework: an agent sequentially labels $d$-dimensional query embeddings drawn i.i.d. from an unknown distribution by either calling a costly expert or guessing with no feedback, with the goal of minimizing regret relative to an oracle with free expert access. When the horizon $T$ is at least exponential in the embedding dimension $d$, the geometry of the class regions can be learned. In this regime, we propose the Conservative Hull-based Classifier (CHC), which maintains convex hulls of expert-labeled queries and calls the expert when a query lands outside all known hulls. CHC attains $\mathcal{O}(\log^d T)$ regret in $T$ and is minimax optimal for $d=1$. Otherwise, the geometry cannot be reliably learned in general. We show that for queries drawn from a subgaussian mixture and $T \le e^d$, a Center-based Classifier (CC) achieves regret proportional to $N\log{N}$ where $N$ is the number of labels. To bridge these regimes, we introduce the Generalized Hull-based Classifier (GHC), a practical extension of CHC that enables more aggressive guessing via a tunable parameter. Our approach is validated on real-world question-answering datasets using state-of-the-art text embedding models.