A Competitive Algorithm for Agnostic Active Learning

Eric Price; Yihan Zhou

cs.LGOct 28, 2023

A Competitive Algorithm for Agnostic Active Learning

Authors: Eric Price, Yihan Zhou

Organizations: Department of Computer Science, University of Texas at Austin

Abstract

For some hypothesis classes and input distributions, active agnostic learning needs exponentially fewer samples than passive learning; for other classes and distributions, it offers little to no improvement. The most popular algorithms for agnostic active learning express their performance in terms of a parameter called the disagreement coefficient, but it is known that these algorithms are inefficient on some inputs. We take a different approach to agnostic active learning, getting an algorithm that is competitive with the optimal algorithm for any binary hypothesis class $H$ and distribution $D_X$ over $X$ . In particular, if any algorithm can use $m^*$ queries to get $O(η)$ error, then our algorithm uses $O(m^* \log |H|)$ queries to get $O(η)$ error. Our algorithm lies in the vein of the splitting-based approach of Dasgupta [2004], which gets a similar result for the realizable ( $η= 0$ ) setting. We also show that it is NP-hard to do better than our algorithm's $O(\log |H|)$ overhead in general.

Figures & tables

	$\lambda(h)$	Values $h(x)$
$h_{1}$	0.9	1111 1111
$h_{2}$	$0.1-10^{-6}$	1111 0000
$h_{3}$	$10^{-6}$	0000 1110
$y$		0000 1111

Figure 1: An example demonstrating that the weight of the true hypothesis can decrease if

\lambda

is concentrated on the wrong ball. In this example, the true labels

y

are closest to

h_{3}

. But if the prior

\lambda

on hypotheses puts far more weight on

h_{1}

and

h_{2}

, the algorithm will query uniformly over where

h_{1}

and

h_{2}

disagree: the second half of points. Over this query distribution,

h_{1}

is more correct than

h_{3}

, so the weight of

h_{3}

can actually decrease if

\lambda(h_{1})

is very large.

Panel of Figure 2 — Algorithm 1 Competitive Algorithm for Active Agnostic Learning

Active Learning

Active learning selects the examples, labels, features, or experiments most useful for improving a model under limited budgets.

See all 296 papers

Near-Polynomially Competitive Active Logistic Regression
Mar 7, 2025Yihan Zhou, Eric Price, Trung NguyenActive Learning Logistic Regression
The University of Texas at Austin
On the Sample Complexity of Active Learning with Membership Queries
Sep 23, 2026Ganghua Wang, Shaddin DughmiActive Learning Statistical Learning Theory
Department of Mathematics, University of Arizona · Department of Computer Science, University of Southern California
REALITrees: Rashomon Ensemble Active Learning for Interpretable Trees
Mar 24, 2026Simon D. Nguyen, Hayden McTavish, Kentaro Hoffman +2PAC-Bayesian Theory Active Learning
Department of Statistics, University of Washington · Department of Computer Science, Duke University · Department of Sociology, University of Washington

Mar 7, 2025J/K move · Enter open · S save

Near-Polynomially Competitive Active Logistic Regression

Yihan Zhou, Eric Price, Trung Nguyen

The University of Texas at Austin

Active Learning Logistic Regression Statistical Learning Theory

Open paper AskPDF arXiv

We address the problem of active logistic regression in the realizable setting. It is well known that active learning can require exponentially fewer label queries compared to passive learning, in some cases using

\log \frac{1}{\eps}

rather than

\poly(1/\eps)

labels to get error

\eps

larger than the optimum. We present the first algorithm that is polynomially competitive with the optimal algorithm on every input instance, up to a factor

d^2

and factors polylogarithmic in the error and domain size. In particular, on a simple family of logistic threshold instances with a uniform distribution, our algorithm uses

\polylog(1/\eps)

labels, whereas every passive learner requires

Ω(1/\eps^2)

labels. Our algorithm is based on sampling and can be extended to learn more general class of functions. We further support our theoretical results with experiments demonstrating performance gains for logistic regression compared to existing active learning algorithms.

Abstract

Active Learning

Explore similar work

Near-Polynomially Competitive Active Logistic Regression

On the Sample Complexity of Active Learning with Membership Queries

REALITrees: Rashomon Ensemble Active Learning for Interpretable Trees