# Select representative samples: a short survey on statistical divergence minimization for active learning

Ferdinand Equilbey

► To cite this version:

Ferdinand Equilbey. Select representative samples: a short survey on statistical divergence minimization for active learning. 2026. hal-05510954v3

HAL Id: hal-05510954

https://hal.science/hal-05510954v3

Preprint submitted on 17 Feb 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Select representative samples: a short survey on statistical divergence minimization for active learning

Ferdinand Equilbey¹*

¹ Université de Poitiers, Univ. Limoges, CNRS, XLIM, Poitiers, France

email: ferdinand.equilbey@univ-poitiers.fr

February 17, 2026

## Abstract

This paper investigates the formalization of representativeness for manually selected samples in supervised learning. Instead of using independent and identically distributed (iid) samples to train a black-box model, active learning looks for informative samples, often using a proxy for the uncertainty of the current model on unlabeled data points, to maximize it. A problem arises in the distribution of the constructed subset, which we call *representative* if it is close enough to those of an *iid* sample, where the distribution is uniform over the indices and supposed to mimic the true unknown marginal. Several measures to quantify the gap have then been used — from the traditional Wasserstein distance to general integral probability metrics. We review these methods with (1) specifying algorithms when provided and (2) exploring the associated generalization bounds. Our first goal is to show their connections and pave the ground for developing more general methods.

## Contents

<table><tr><td>1</td><td>Introduction</td><td>2</td></tr><tr><td>1.1</td><td>Motivation</td><td>2</td></tr><tr><td>1.2</td><td>Setting and notations: the ERM principle</td><td>2</td></tr><tr><td>1.3</td><td>Related works</td><td>3</td></tr><tr><td>2</td><td>Representativeness via discrepancy minimization</td><td>5</td></tr><tr><td>2.1</td><td>Rademacher complexity generalization bounds</td><td>5</td></tr><tr><td>3</td><td>Existing algorithms</td><td>10</td></tr><tr><td>3.1</td><td>Implicit realization with convex regularization and ADMM</td><td>10</td></tr><tr><td>3.2</td><td>Matrix Partition</td><td>11</td></tr><tr><td>3.3</td><td>Wasserstein distance minimization via GroupSort</td><td>11</td></tr><tr><td>3.4</td><td>Wasserstein distance minimization via MILP</td><td>11</td></tr><tr><td>3.5</td><td>Discriminative Active Learning</td><td>12</td></tr><tr><td>4</td><td>Discussion</td><td>12</td></tr></table>

<footnote>*PhD student under the supervision from P. Carre and F. Enikeeva.</footnote>
# 1 Introduction

After setting the context, we briefly review specific questions in active learning. Next the general question of *representativeness* is formulated, and specified for statistical divergences. A separate section presents the algorithms that tackle some of these strategies.

## 1.1 Motivation

Active Learning (AL) is one of the solutions to reduce the costs of labeling data. Given a large pool of unlabeled examples, such as images, documents or structured data, several criteria can be optimized to select the next batch. The uncertainty of the model (which can be considered as black-box) change after training and the criterion is updated: this is the classical *pool-based* setting. When we face instead a data stream, a decision for the label to be queried or not has to be made. Probabilistic scenarios for instance construct a probability for this event, then draws the decision, so via a biased Bernoulli random variable.

We restrict this work on the pool-based setting, within which there is a lot of existing strategies in the AL literature. The reader should distinguish between diversity and representativeness, as these concepts are often conflated but fundamentally different. We explain these concepts in the related work. Others select next examples with respect to the model's uncertainty, which can be assessed or estimated, for instance, with the classifier margin or likelihood. Finally, combination of criteria is possible using reformulations of optimization problems.

Generalization refers to the convergence of the empirical estimator of the model risk to its true unknown value. We will recall the quantity named generalization error, for which small values indicate, theoretically, good performance of the model on previously unseen data. This term should not be confused with the population error; further details are given below. As is, upper bounding the generalization error is an interesting guarantee (as long as the upper bound is not too coarse) and as one of its component cannot be computed, the upper bound allows to get worst-case or average-case results. The RHS often depends on a measure of capacity for the class of models involved, and can be data-dependent. We review in this paper how generalization bounds have been used to guarantee specific active learning methods: the empirical risk, which estimates the population error, is no longer taken on a typical i.i.d. sample, but rather on a manually constructed subset, where examples are chosen, for instance, regarding their informativity - their capacity to reduce the model uncertainty. An important remark is then that a (formal) dependence is introduced between the samples and that numerous results from statistical learning theory, as initially stated, no longer hold.

## 1.2 Setting and notations: the ERM principle

Suppose the marginal distribution of the data $X \sim \mathbb{P}_X$, and labels $Y \sim \mathbb{P}_{Y|X}$ are unknown. When selecting a subset as with AL, We will denote by $\ell: \mathcal{Y} \times \mathcal{Y} \to \mathbb{R}_+$ as the loss function. For a collection of samples $Z := \{z_i\}_{i=1,...,n} := \{(x_i, y_i)\}_{i=1,...,n}$ and a model $h: \mathcal{X} \to \mathcal{Y}$, the empirical risk $\hat{R}$ is the average of the loss on $\{(y_i, h(x_i))\}_{i=1,...,n}$, and is thus a function both of the sample $Z$ and of the given model $h$. Here, $h$ denotes a hypothesis within the space $\mathcal{H}$, chosen based on the underlying assumptions regarding the relationship between targets to variables, e.g. linearity or degree $k$ polynomial relationship. Here are some typical examples:

* $\mathcal{H}_{\text{linear}} = \{h: \mathcal{X} \to \mathcal{Y} \mid h(\mathbf{x}) = \mathbf{w} \cdot \mathbf{x}, \mathbf{w} \in \mathbb{R}^d\}$. Linear classes, and even threshold classifiers on the real line, are commonly introduced for theoretical analysis of AL algorithms, as the reader can see in [2].

* $\mathcal{H}_{\text{gaussian}} = \{h: \mathcal{X} \to \mathcal{Y} \mid h(\mathbf{x}) = \mathbf{w} \cdot \exp\left(-\frac{\|\mathbf{x} - \mathbf{t}\|^2}{2\sigma^2}\right), \mathbf{w}, \mathbf{t} \in \mathbb{R}^d\}$. This class em- beds the data into a reproducing kernel Hilbert space (RKHS), here via $k$ for which a prior hyperparameter $\sigma > 0$ has to be chosen.
• $\mathcal{H}_{\text{NN}} = \{h: \mathcal{X} \to \mathcal{Y} \mid h(\mathbf{x}) = \mathbf{o} \cdot f(\mathbf{x}) + \mathbf{t}, \mathbf{o}, \mathbf{t} \in \mathbb{R}^d\}$, where

$$f(\mathbf{x}) = \mathbf{W}^{(L)} \sigma \left( \mathbf{W}^{(L-1)} \cdots \sigma(\mathbf{W}^{(1)}\mathbf{x} + \mathbf{b}^{(1)}) \cdots + \mathbf{b}^{(L-1)} + \mathbf{b}^{(L)} \right),$$

$\sigma$ being a component-wise activation function. We refer the reader for instance to [11] for more details on the construction of neural networks.

It is common in AL no to specify $\mathcal{H}$ explicitly and to work in a *model-agnostic* fashion. Some works in the other hand focus on the active training of specific models (e.g. [13], [17], [20], [24]). A poor choice of $\mathcal{H}$ (missing non-linear or complex relationships), or a rich one (overparametrization) belongs to *inductive bias*. In the rest of the paper, when dealing with a parametrized black-box model without detail on the structure, we will use $\theta \in \mathbb{R}^d$. $\theta$ is the vectorization of the collection of learnable parameters and can be expressed by rearranging the concatenation of the coefficients. If $\{\mathbf{W}^{(1)}, \dots, \mathbf{W}^{(L)}, \mathbf{b}^{(1)}, \dots, \mathbf{b}^{(L)}, \mathbf{o}, \mathbf{t}\}$ are those of a NN the following rearranging

$$\theta = (\operatorname{vec}(\mathbf{W}^{(1)}) | \dots | \operatorname{vec}(\mathbf{W}^{(L)}) | \mathbf{b}^{(1)} | \dots | \mathbf{b}^{(L)} | \mathbf{o} | \mathbf{t})$$

## 1.3 Related works

**Statistical discrepancies** The main idea of so-called representative sampling is to select a subset of the data that best reflects the unlabeled pool, in terms of their (possibly empirical) distributions, using a probability metric or distance. The active sampling method is usually based on the uncertainty of the model or other heuristic and can thus induce a bias. In this section we recall more precisely this distribution matching setting and the discrepancy measures that have been used, notably integral probability metrics (IPMs), for active learning. The following works explicitly address the problem of distribution matching in this context.

<table><caption>Table 1: Overview of papers dealing with distribution representativeness in active learning. The distance can come from a two-sample adequation test, in which case we write its name in the second column. In the Algorithm column, the dagger corresponds to strategies for which we found an implementation.</caption><thead><tr><th>Measure of distance</th><th>Algorithm</th><th>Bound</th><th>Paper</th></tr></thead><tbody><tr><td>MMD</td><td>✓<sup>†</sup></td><td>✓</td><td>[23]</td></tr><tr><td>Nuclear discrepancy</td><td>✓</td><td>✓</td><td>[21]</td></tr><tr><td>α-Pearson relative divergence</td><td>✓</td><td>✗</td><td>[22]</td></tr><tr><td>Wasserstein</td><td>✓</td><td>✓</td><td>[14]</td></tr><tr><td>Wasserstein</td><td>✓</td><td>✓</td><td>[19]</td></tr><tr><td>Wasserstein</td><td>✓</td><td>✗</td><td>[1]</td></tr><tr><td>Fisher information matrices ratio</td><td>✓</td><td>✗</td><td>[10]</td></tr><tr><td>IPMs</td><td>✗</td><td>✓</td><td>[16]</td></tr><tr><td>Mutual information<sup>*</sup></td><td>✓</td><td>✗</td><td>[8]</td></tr><tr><td>\H-divergence (2)</td><td>✓<sup>†</sup></td><td>✗</td><td>[6]</td></tr></tbody></table>

**Uncertainty sampling** The first historical heuristics rely on the optimization of some uncertainty measure computed either on the unlabeled pool $\mathbf{X}$ or on the model confidence, using for instance the scores $\mathbb{P}_{\theta}(y|\mathbf{x})$. For instance,

• $\Phi(\mathbf{x}) = -h(\mathbf{x}) \log(h(\mathbf{x})) - (1 - h(\mathbf{x})) \log(1 - \mathbf{x})$ (entropy sampling),

• $\Phi(\mathbf{x}) = \mathbb{P}_{\theta}(y|\mathbf{x})$ (least-confident sampling)

• $\Phi(\mathbf{x}) = \mathbb{P}_{\theta}(y_1|\mathbf{x}) - \mathbb{P}_{\theta}(y_2|\mathbf{x})$ (margin sampling, where $y_1$ and $y_2$ are the most probable labels in decreasing order),
are plugged in the sampling rule

$$ \mathbf{x}^* = \arg \max_{x \in \mathcal{X}} \Phi(\mathbf{x}). $$

This kind of procedure can outperform random sampling in some cases, but struggle to perform in the case of deep learning. [18] is probably the most cited survey of active strategies; we recommend [9] for a complementary text on these methods for classification problems.

**Bayesian acquisition functions** The softmax scores of deep learners are not interpretable enough in terms of the confidence of the model in its predictions, and at least for recent architectures, poorly calibrated ([7]). Instead, works of [5] study the link between Dropout and bayesian learning.

**Sampling bias** The seminal AL theory paper [2] explained a proper example where the sampling procedure implies a bias. The diagram in Figure 1 illustrates how sampling bias arises in active learning when data selection is driven by model uncertainty. Imagine an input space split into four regions: two large ones (45% each) and two narrow ones (5% each). The hatched areas mark zones of uncertainty, which active learning algorithms typically prioritize. Yet, this focus on uncertain regions (e.g., near the decision boundary, indicated by arrows $w^*$ and $w$) tends to oversample the small 5% segments. Because the model's confidence is lower there, these rare regions become overrepresented, while the dominant 45% areas—where the model is confident—remain under-sampled. Over time, this skews the training set toward edge cases, reducing performance on the majority of real-world data. The example highlights a central tension in active learning: refining decision boundaries through uncertainty sampling versus staying faithful to the underlying distribution. Without correction mechanisms (e.g., reweighting or stratified sampling), active selection risks reinforcing misalignment between training and test distributions. Within the next sections, we will discuss how representative sampling, when

<figure><img src="image_2.png" /><figcaption>Figure 1: Sampling bias (figure from [2])</figcaption></figure>

the true distribution on the whole pool $\mathbf{X}$ is mimicked by minimizing a discrepancy between the manually selected sample to $\mathbf{X}$, is designed to alleviate this problem.

**Disagreement-based learning** An important guarantee have arisen to qualify some active algorithms. It captures in how many steps the process needs at least to beat up the passive scenario, regarding the batch size. Bounds on this sample or label complexity are achieved sometimes with a passive exploration of $\mathcal{H}$, or by empirical risk minimization. We can build a pseudo-metric structure on the set of hypotheses compatible with data received at time $t$, $\mathcal{H}_t = \{h \in \mathcal{H} : h(x_i) = y_i, i = 1, \dots, t\}$, using the disagreement metric:

$$ d(h_1, h_2) = \mathbb{P}_{X \sim \mu}[h_1(X) \neq h_2(X)], $$

or partition $\mathcal{H}_t$ in $\mathcal{H}_t^{x,+} = \{h : h(\mathbf{x}) = +1\}$ and $\mathcal{H}_t^{x,-} = \{h : h(\mathbf{x}) = -1\}$ to efficiently shrink the final set of accepted models, in terms of the radius with $d_{\mathcal{H}}$. On the other hand, the region where models disagree,

$$ \mathrm{DIS}(\mathcal{H}_t) := \{\mathbf{x} \in \mathcal{X} : h_1(\mathbf{x}) \neq h_2(\mathbf{x}), h_1, h_2 \in \mathcal{H}_t\} \subset \mathcal{X} $$

appears to be a good region to sample new instances.
**Implicit solving: the discriminative approach.** Finally, domain adaptation and GANs training were shown connected to our problem in [6]. For two distributions $\mu$ and $\nu$, let us recall the $\mathcal{H}$-divergence,

$$d_{\mathcal{H}}(\mu, \nu) = 2 \sup_{h \in \mathcal{H}} |\mathbb{P}_{\mu}(h(x) = 1) - \mathbb{P}_{\nu}(h(x) = 1)|. \qquad (1)$$

$\nu$ is referred to the target distribution in domain adaptation, and associated to the unlabeled data pool. The source distribution $\mu$ is obtained on the training set, $\mu = \sum_{\mathbf{x} \in L} \delta_{\mathbf{x}}$. Then,

$$d_{\mathcal{H}}(\mu, \nu) = 2 \sup_{h \in \mathcal{H}} \left| \frac{1}{|L|} \sum_{\mathbf{x} \in L} h(\mathbf{x}) - \frac{1}{|U|} \sum_{\mathbf{x} \in U} h(\mathbf{x}) \right|. \qquad (2)$$

The problem is considered equivalent to train a classifier to distinguish between $L$ and $U$, which is called discriminative approach.

**Domain adaptation** We are very close to the domain adaptation framework. Recall that the goal is to train a model that can perform well on new data, specifically a new distribution $\nu \neq \mu$. Divergences have been used and defined in that field, such as the $\mathcal{H}$-divergence in [6] as well as the Bregman divergence. When there is distribution drift, the formulation is advantageous and we can perform bias correction.

# 2 Representativeness via discrepancy minimization

The ERM principle for active learning with sampling representative examples in terms of disc is stated as

$$R(h) \leq \hat{R}(h, Z) + \text{disc}(p_X, p_S) + \Delta_n. \qquad (3)$$

In essence, the problem (3) is combinatorial in $\binom{N-|L|}{b}$. Next the distributions $\mathbb{P}_X$ and $\mathbb{P}_{L \cup S}$ can be tricky to estimate, especially in high dimension with nearest-neighbors or classical approaches. More recent approaches proposed Normalizing Flows to approximate the densities ([3]).

## 2.1 Rademacher complexity generalization bounds

One of the most cited result when dealing with generalization is the following Rademacher complexity based bound<fnref n="1" />. Recall that the Rademacher complexity of a composition $\mathcal{E} \circ E$ is given by

$$\text{Rad}(\mathcal{E} \circ E) := \mathbb{E} \left[ \sup_{e \in E} \frac{1}{|E|} \sum_{i=1}^{|E|} \sigma_i e(x_i) \right],$$

that is, the maximal average of sign-permuted outputs from functions in $E$, taken in expectation

$$R(h) \leq \hat{R}(h, X) + 2 \cdot \text{Rad}(\mathcal{K}) + c \sqrt{\frac{2 \log(4/\delta)}{n}} \qquad (4)$$

This kind of measure have been extended to Gaussian families by replacing the law of $\sigma$ by a normal draw. For instance in [12], Shatten norm regularization and covering numbers are used for SVM learners generalization analysis.

<footnote n="1">¹In [23], the RHS is slightly different, with the last term being $\sqrt{\frac{\ln 1/\delta}{n}}$</footnote>
<figure><img src="image_3.png" /><figcaption>(a) Citation statistic for [18].</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>(b) Citation statistic for [23].</figcaption></figure>

**Maximum mean and nuclear discrepancies.** The seminal paper [23] is the first work to present proper representative sampling, to our knowledge. The distributions are compared under their Maximal Mean Discrepancy (MMD). For two probability density functions p and q, this quantity is given by

$$MMD(p, q) = \sup_{g \in \mathcal{K}(\Lambda)} \int g(x)p(x)dx - \int g(x)q(x)dx. \qquad (5)$$

To move to an empirical formula, it has been proposed in two-sample tests literature to use a reproducing kernel. If we denote by $\phi$ the feature mapping and $\mathcal{F}$ the classifier function class, for two samples S and Q not necessarily of the same size, we define

$$MMD(S, Q; \phi) = \left\| \frac{1}{|S|} \sum_{x \in S} \phi(x) - \frac{1}{|Q|} \sum_{x \in Q} \phi(x) \right\|_{\mathcal{F}}. \qquad (6)$$

The authors give an empirical risk minimization principle for active learning. Starting from the bound (4), we replace Z by Q (and n by $|Q|$) which adds the value of the MMD(S, Q; $\phi$) in the RHS. This due to original concentration results between MMD and MMD(·, ·; $\phi$) and to the fact that Q, the query set, is included in the pool S. In words, the bound we obtain states that reducing the distribution gap between the query and the unalabeled pool will lead to better generalization. Note that we also have the natural empirical version of the discrepancy:

$$\widehat{MMD}(S, Q) = \sup_{g \in \mathcal{K}(\Lambda)} \left( \frac{1}{|S|} \sum_{x \in S} g(x) - \frac{1}{|Q|} \sum_{x \in Q} g(x) \right) \qquad (7)$$

for two samples $S_1, S_2 \subset X$ whose empirical distributions are compared over the functions (embeddings) $g \in \mathcal{K}(\Lambda)$. For this latter function class notation, say that every element $g \in \mathcal{K}(\Lambda)$ is upper-bounded by $\Lambda > 0$. This formula places us in the representativeness problem for active learning where $S_1$ is a passive random sample, $S_2$ is actively selected and g is precisely the empirical risk $\hat{R}$ (still as a function of the model h, which is later fixed, and a subset, here $S_1$ and $S_2$) for each sample, $\hat{R}(h, S_1)$ and $\hat{R}(h, S_2)$. Then, the goal is to minimize the MMD and transfer performance guarantees from the passive regime to the active one with a generalization bound.

Significant improvement and analysis under the criterion (7) has been introduced in [21]. First, if we denote by **S** and **Q** the data matrices of (concatenation of points in) S and Q, let us define the following *Gram difference matrix*

$$\mathbf{G}_{S,Q} := \frac{1}{|S|} \mathbf{S}^{\top} \mathbf{S} - \frac{1}{|Q|} \mathbf{Q}^{\top} \mathbf{Q}. \qquad (8)$$

The authors, using arguments from [15], importantly note (Theorem 4 in [21]) that

$$MMD(S, Q) = 4\Lambda^2 \|\mathrm{Spec}(\mathbf{G}_{S,Q})\|_2, \qquad (9)$$
that is, we can compute the discrepancy using the data matrices and the spectrum of $G_{S,Q}$. From there, changing the norm on it get us another natural discrepancy measure:

$$ \mathrm{disc}(S, Q) = 4\Lambda^2 \rho(\mathbf{G}_{S,Q}) = \max_{h_1,h_2} |\hat{R}(h_2, h_1; \mathbf{S}) - \hat{R}(h_2, h_1; \mathbf{Q})|, \quad (10) $$

with $\rho$ being the spectral radius and

$$ \hat{R}_p(h_1, h_2; \mathbf{U}) := \frac{1}{|\mathbf{U}|} \sum_{\mathbf{x} \in \mathbf{U}} \ell(h_1(\mathbf{x}), h_2(\mathbf{x})). $$

The previous equation implies that a representative sample minimizes the maximum eigenvalue of $G_{1,2}$. Indeed, the Theorem 5 from [21] roughly states that

$$ \hat{R}(h, S_1) \approx 0 \implies \hat{R}(h, S_2) \approx \mathbf{u}^\top G_{1,2} \mathbf{u} \quad (11) $$

where $u$ is the difference between the estimated and the true models.

Using (9), the authors show the following probabilistic result (Theorem 6).

**Theorem 2.1 (Probabilistic generalization bound).** With $G_{S,Q}$ as defined in (8), for any loss function $\ell$ and any $h \in \mathcal{H}$,

$$ \mathbb{E}[\hat{R}(h, X)] \le \mathbb{E}[\hat{R}(h, S)] + \frac{4}{3}\Lambda^2 \|\mathrm{Spec}(G_{1,2})\|_1 $$

Here are the main steps of the proof. First, they use the triangular inequality on $|\sum_{i=1}^d u_i^2 \lambda_i|$. The argument that the function $u \mapsto \sum u_i^2 |\lambda_i|$ is increasing allows the rewriting of the inequality. Then with linearity of the integral, and the final direct computation of the obtained integral, gives $\frac{4}{3}\Lambda^2 \sum_i |\lambda_i|$.

**Theorem 2.2 (Deterministic generalization bound).** With the above notations,

$$ \hat{R}(h, X) \le \hat{R}(h, S) + \mathrm{disc} \left( \hat{\mathbb{P}}_X, \hat{\mathbb{P}}_S \right) + \eta_{\mathrm{disc}}. \quad (12) $$

**Integral Probability Metrics.** [16] show how this method can be extended to general integral probability metrics. Recall that

$$ \mathrm{IPM}_{\mathcal{F}}(\mu, \nu) = \sup_{f \in \mathcal{F}} |\mathbb{E}_{X \sim \mu}[f(X)] - \mathbb{E}_{Y \sim \nu}[f(Y)]|, $$

is an integral probability metric<fnref n="2" /> between distributions $\mu$ and $\nu$. The choice of the functional generator class $\mathcal{F}$ can lead to the total variation metric (TV), the Kantorovic metric, and to the MMD with the choice $\mathcal{F}$ being bounded-norm functions in some reproducing kernel Hilbert space (RKHS). The authors start from bound (4) to extend to the following version.

**Theorem 2.3 (Generalization bound for IPMs).** With the above notation,

$$ R(h) \le \hat{R}(h, X) + \mathrm{IPM}_{\mathcal{F}}(\mathbb{P}_X, \mathbb{P}_S) + 2 \cdot \mathrm{Rad}(\ell \circ \mathcal{H}) + c \sqrt{\frac{2 \log(4/\delta)}{n}}. \quad (13) $$

**Definition 2.4.** For any generator function class $\mathcal{F}$, its maximal generator $\mathcal{R}_{\mathcal{F}}$ the set of all functions $f \in \mathcal{F}$ such that $|\mathbb{E}_{\mathbf{X}}[f(\cdot)] - \mathbb{E}_{\mathbf{S}}[f(\cdot)]|$ is upper bounded by $\mathrm{IPM}_{\mathcal{F}}(\mathbb{P}_{\mathbf{X}}, \mathbb{P}_{\mathbf{S}})$.

To show this result, the maximal generator property defined above is proven for the functional

$$ g := \mathbb{E}_{y|X}[\ell(y | h(\cdot))]. \quad (14) $$

Then by definition of the maximal generator, the conclusion follows.

A consequence for linear models $\mathcal{H}_{\mathrm{linear}}$ is also proven for the special case of the Kantorovic metric as the discrepancy. The authors also construct some results for the hypotheses classes mentioned in the introduction.

<footnote n="2">²This is not a proper distance function, as $\mathrm{IPM}_{\mathcal{F}}(\mu, \nu)$ does not imply $\mu = \nu$.</footnote>
<figure><img src="image_5.png" /><figcaption>(a) Schematic view of the approaches studied in this paper. The red samples are supposed to minimize a discrepancy between the (empirical) distributions of X and L ∪ Q .</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>(b) Representation of different known φ -divergences. Figure by Cosmia Nebula.</figcaption></figure>

**Wasserstein distances and optimal transport problems.** We now move to another cru- cial family of metric in machine learning, namely the Wasserstein metrics (including the Earth Mover Distance). The classical p-Wasserstein distance, which comes from optimal transport problems, is defined as

$$
W_p(\mathbb{P}_X, \mathbb{P}_Q) := \inf_{\gamma \in \Pi(X,Q)} \int_{\mathcal{X} \times \mathcal{X}} c(x_X, x_Q)^p d\gamma(x_X, x_Q) \quad (15)
$$

where c : X × X → R + is a cost with unit mass. W$_{p}$ is solving the optimal joint pdf P (Ω × Ω) (in the set of all such couplings Π( X, Q )) in terms of the cost function c . The interest compared to the H -divergence is in the fact that the support for Q is necessarily included in the support for X .

In [19], the authors use this distance to give the following oracle bound.

**Theorem 2.5.** With the above notation and if the loss function is bounded by some M > 0, it holds that

$$
\mathbb{E} \left[ \hat{R}(h, \mathbf{X}) \right] \leq \mathbb{E} \left[ \hat{R}(h, \mathbf{S}) \right] + M \cdot (H + \lambda) \cdot W_1(\mathbb{P}_X, \mathbb{P}_S) + M \cdot \phi(\lambda) \quad (16)
$$

Then, it allows to give the following estimate for the rhs:

$$
\hat{R}(h, \mathbf{S}) + M \cdot (H + \lambda) \cdot W_1(\hat{\mathbb{P}}_X, \hat{\mathbb{P}}_S) + M \cdot \phi(\lambda) + 2LR\mathrm{Rad}_{N_q}(h) + \kappa(\delta, N, N_q),
$$

where

$$
\kappa(\delta, N, N_q) = O \left( N^{-1/s_d} + N_q^{-1/s_q} + \sqrt{\frac{\log 1/\delta}{N}} + \sqrt{\frac{\log 1/\delta}{N_q}} \right)
$$

and constants s$_{d}$, s$_{q}$ > 0. From these upper bounds, the problem is stated as a regularized ERM:

$$
\min_{B,h} \hat{R}(h, L \cup B) + \mu \cdot W_1(\hat{\mathbb{P}}_X, \hat{\mathbb{P}}_{L \cup B}) \quad (17)
$$

This problem can be reformulated using the Kantorovic-Rubinstein duality. We detail the steps we obtain in Section 3.4.

The following deviation bound, proposed in [4], allows to prove another guarantee.

**Proposition 2.6 (Deviation in Wasserstein distance).** There exists positive constants α and β which do not depend on n and such that for any ε ∈ (0 , 1),

$$
\mathbb{P}(W_1(\mathbb{P}_X, \mathbb{P}_S) > \varepsilon) \le \alpha e^{-\beta n \varepsilon^d} + \alpha \frac{\varepsilon^{1-d/2}}{n^{d/2}} \quad (18)
$$
[1] shows a generalization bound, in the same form of Theorem 2.5 (with an additive constant) by use of the triangular inequality on $W_1$, then with the above deviation bound.

**Mutual information.** The representativeness of the selected sampled can also be assessed with the mutual information between $S$ and $U$, which we recall being equal to the sum of the true entropies of the respective densities minus the joint entropy between them. The following problem for gaussian processes has been proposed by [8]:

$$S^{(t)} = \arg \max_{|S|=b, S \subseteq U} I(S^{(t)} \cup S^{(0, \dots, t-1)}, U \setminus S) \quad (19)$$

$$= \arg \max_{|S|=b, S \subseteq U} \ln \det(\Sigma) + \ln \det(\Sigma) \quad (20)$$

Note that, we have by definition

$$I(X, Y) = d_{\mathrm{KL}}(\mathbb{P}_{(X,Y)}, \mathbb{P}_X \otimes \mathbb{P}_Y) \quad (21)$$

where $\mathbb{P}_{(X,Y)}$ is the joint pdf of the labeled data, and $\mathbb{P}_X \otimes \mathbb{P}_Y$ the product of the marginals. This way, the mutual information is an application of a specific $\phi$-divergence (with $f: t \mapsto t \ln t$) that we take between labeled sample $S^{(t)} \cup S^{(0, \dots, t-1)}$ and current unlabeled pool $U \setminus S$. The mutual information is the only divergence that belongs to both families.

Contrary to mutual information, where $P_X \otimes P_Y$ is a product distribution, here $\hat{\mathbb{P}}_{\mathcal{L}_t}$ (or $\hat{\mathbb{P}}_U$) is a "sub-distribution" of $\hat{\mathbb{P}}_n$. Our problem is thus fundamentally distinct than those of mutual information, because we are working with discrete empirical distributions, and the relationship between $\hat{\mathbb{P}}_n$ and $\hat{\mathbb{P}}_{\mathcal{L}_t}$ is a subset, not of product.

**Likelihood ratio, relative divergence and matrix partition.** Another method applies the $\alpha$-relative Pearson divergence. As often when trying to compensate the dependence between samples, we express the variation of the new/test distribution with respect to the previous/train distribution. The notion of Radon-Nikodym derivative extends the variation rate to probability measures.

$$\frac{d\mathbb{P}_Q}{d\mathbb{P}_X} = \frac{dq}{dp}, \quad (22)$$

where $p$ and $q$ are the pdfs of distribution for $X$ and $Q$ respectively.

Let the following parametrized variation of the density ratio:

$$r_{\alpha}(x) = \frac{p(x)}{\alpha p(x) + (1 - \alpha)q(x)}.$$

We can define the $\alpha$-relative Pearson divergence measure by

$$\mathrm{PE}(\mathbb{P}_X, \mathbb{P}_S) = \frac{1}{2} \mathrm{E} \left[ (r_{\alpha}(x) - 1)^2 \right], \quad (23)$$

$p$ and $q$ being the probability density functions (pdf) of $X$ and $S$. for which we recall empirical estimators in the next section. The work in [22] sets representative active learning as minimizing (23), through a convex reformulation of the problem.

Given $\mathbb{P}_X$ and $\mathbb{P}_Q$, it is possible to describe a more information-geometric method, namely with the Fisher metric. Suppose we also have our model's parameters (as described with $\mathbf{w}$ in Section 1.2), and denote, following the notation from [10] $\mathbf{I}_p(\mathbf{w})$ and $\mathbf{I}_q(\mathbf{w})$ the Fisher information matrices of the parameter $\mathbf{w}$ with respect to the global pool and the selected subset, respectively. It is then wished to reduce the uncertainty by optimizing the Fisher information ratio, given by

$$Q^* = \arg \min_{Q} \mathrm{tr}(\mathbf{I}_q(\mathbf{w})^{-1} \mathbf{I}_p(\mathbf{w})). \quad (24)$$
For a logistic regression model, with

$$ \pi_i = p(\cdot | \mathbf{x}_i) = \frac{1}{1 + \exp(\mathbf{w}^\top \mathbf{x}_i)}, $$

the following solution is

$$ \mathbf{I}_p(\hat{\mathbf{w}}) = \sum_i \pi_i (1 - \pi_i) \mathbf{x}_i^\top \mathbf{x}_i q_i + \delta \mathbf{I}_d. \qquad (25) $$

Note that the term $\pi_i(1 - \pi_i)$ is maximal at $\pi_i = 1/2$, which means high uncertainty for the classification model; but it is important to dispose of a well calibrated, i.e. reliable $\pi$, which is not evident for deep learning models softmax outputs [5]. A semi-definite program is formulated, and solved with standard convex optimization tools. However, the computation can be costly, so an eigenspace simplification is made. We give the obtained update equations in the next section.

# 3 Existing algorithms

Not every work present a concrete way to get $\mathbb{P}_S$ matching the given bound, although the computation is not always straightforward and tractable. The first heuristic one may think about is when using a plug-in estimator of the discrepancy. Then the following steps give a greedy approach:

1. Estimate disc($\mathbb{P}_X$, $\mathbb{P}_S$) for all possible subsets (say of given size $b \in \mathbb{N}$) in $\mathcal{P}_b(\mathbf{X})$

2. Select $\mathbf{S}^* = \arg\min_{\mathbf{S}} \mathrm{disc}(\mathbb{P}_X, \mathbb{P}_S)$ for the computed values.

Of course, step 1. is potentially computationally costly. An approximated algorithm would draw $r$ possible subsets and iterate over the divergence values for these samples. We see two main problems for this kind of method; first, it is tricky to know a priori the quality of the approximation, or in other words, how close we are to the actual lower bound. Second is on the quality of the estimator we use. A lot of literature proposed such computations for gaussian or iid cases.

## 3.1 Implicit realization with convex regularization and ADMM

In [23], the authors propose to rewrite $\mathbf{S}^* = \arg\min_{\mathbf{S}} \mathrm{disc}(\mathbb{P}_X, \mathbb{P}_{L \cup Q})$ where $Q$ is the query sample of size $b$, and $L$ is the available labeled instances at the current time. First, by splitting the kernel matrix, a convex relaxation is formulated, and the Alternate Direction Multiplier Method (ADMM) is next employed to get the optimal query.

Let us define the objects the authors used to formulate their implicit algorithm for the MMD. Fixing the kernel matrix $\mathbf{K} = (k(\mathbf{x}_i, \mathbf{x}_j))_{i,j} = (\Phi(\mathbf{x}_i)^\top \Phi(\mathbf{x}_j))_{i,j}$, with feature map $\Phi$, and following the notations from the paper, let

$$ \mathbf{K}_1 = \frac{1}{2}\mathbf{K}_{UU}, \quad \mathbf{K}_2 = \frac{l+b}{n}\sum_{\mathbf{x}_j \in U} \mathbf{K}_{ij}, \quad \mathbf{K}_3 = \frac{u-b}{n}\sum_{\mathbf{x}_j \in S} \mathbf{K}_{ij}, \quad \mathbf{k} = \mathbf{K}_3 - \mathbf{K}_2. \qquad (26) $$

Consider

$$ \min_{\alpha^\top \mathbf{1}_u = b} \beta \alpha^\top \mathbf{K}_1 \alpha + (\beta \mathbf{k} + \mathbf{a}) \alpha \\ \mathbf{a}_j := \|\mathbf{w}^\top \Phi(\mathbf{x}_j)\|_2^2 + 2 \left| \mathbf{w}^\top \Phi(\mathbf{x}_j) \right|; $$

this is a quadratic programming (QP) problem for the vector $\alpha \in \{0, 1\}^u$ containing whether data point with index $j$ is queried or not (and thus with $\|\alpha\|_1 = b$). This problem can be relaxed
for $\alpha$ to be compactly-supported. The first step of the full algorithm computes a solution for $\mathbf{w}$ with fixed $\alpha$. The second step relies in the following standard QP problem:

$$ \min_{\alpha^\top \mathbf{1}_u = b} \alpha^\top (\beta \mathbf{K}_1) \alpha + (\beta \alpha + \mathbf{k}) \alpha, $$

Recall that the MMD is a specific type of IPM, when we take $\mathcal{F}$ as the unit ball in a reproducing kernel Hilbert space.<fnref n="3" />

## 3.2 Matrix Partition

We now briefly presents how the selection is implemented for the $\alpha$-Pearson relative divergence. Consider the following optimization problem

$$ \min_{\mathbf{M}} \log |\mathbf{M}\Sigma\mathbf{M}^\top| + \log |\mathbf{T}\Sigma\mathbf{T}^\top|, \quad \text{s.t.} \quad 0 \le \mathbf{M} \le 1, \mathbf{M}\mathbf{1} = \mathbf{1}, \mathbf{M}^\top\mathbf{1} = \mathbf{1}. \quad (27) $$

The function $\log |\cdot|$ is concave, and the quadratic form is matrix convex, but the composition is only known differentiable. A first-order local optimization technique is employed.

## 3.3 Wasserstein distance minimization via GroupSort

**Algorithm 1 GroupSort**

**Training:** update $\theta_h = \theta_h - \eta_h \nabla_{\theta_h}$ (gradient descent, with Adam algorithm)

Set $B \leftarrow \emptyset$

**while** $|B| \neq n_B$ **do**

Update $\theta_\phi \leftarrow \theta_\phi + \eta_\phi$ on $K \cup B$ (gradient descent)

Compute $S(\mathbf{x})$ for all $\mathbf{x} \in U$

Add $\arg\max_{\mathbf{x}} S(\mathbf{x})$

Update sets $U \leftarrow K \cup B$ and $U = U \setminus B$

Algorithm 1 displays the implementation of GroupSort neural network for the Wasserstein minimization problem.

## 3.4 Wasserstein distance minimization via MILP

Consider the following problem.

$$ \min_{\pi \in \{0,1\}^n, \Gamma \ge 0} \langle \mathbf{D}_x, \Gamma \rangle, \quad \text{s. t.} \quad \Gamma \mathbf{1} = \frac{1}{n} \mathbf{1}, \quad \Gamma^\top \mathbf{1} = \frac{1}{B}\pi, \quad \pi^\top \mathbf{1} = B, \quad (28) $$

which the authors reformulate in

$$ \min_{\eta, \pi \in \mathcal{P}} \eta \quad \text{s. t.} \quad \eta \ge \inf_{\Gamma \in \mathcal{G}} \left\{ \langle \mathbf{D}_x, \Gamma \rangle + \hat{\lambda}^{\top} \left( \frac{1}{B}\pi - \Gamma^{\top} \mathbf{1} \right) \right\}, \quad \forall \hat{\lambda} \in \Lambda. \quad (29) $$

In other words, the approach consists in minimizing a Wasserstein distance, hence called Wasserstein Relaxed Master Problem (WRMP($\Lambda$)), that comes from the Lagrangian of the original problem. The global procedure is given in the paper as follows:

1. Given a solution $(\hat{\eta}^t, \hat{\pi}^t)$, solve the Lagrangian $L(\hat{\pi}^t)$ to obtain a primal-dual transport $(\hat{\Gamma}^t, \hat{\lambda}^t)$.

2. Update $\Lambda \leftarrow \Lambda \cup \hat{\Lambda}^t$ and solve W-RMP($\Lambda$) to obtain a solution $(\hat{\eta}^t + 1, \hat{\pi}^t + 1)$.

The method is then accelerated and guaranteed.

<footnote n="3">³In the BMDR paper [21],</footnote>
## 3.5 Discriminative Active Learning

The idea from [6] is to use a discriminator between the unlabeled pool and the global data, in an adversarial fashion. The training of the model helps selecting points indistinguishable from the true distribution, hence minimizing the distribution gap with the pool, which is precisely our goal.

Their algorithm is implemented in the Python library scikit-activeml, we give the pseudo-code hereafter.

**Algorithm 2** The discriminative approach to H-divergence minimization.

**Training:** Train model to discriminate L and X \ L.

**for** i = 1, ..., n **do**

**for** j = 1, ..., K/n **do**

$$ \hat{\mathbf{x}} = \arg \max_{\mathbf{x} \in U} \mathbb{P}(y = u | \Psi(\mathbf{x})) $$

$$ \text{Label } L \leftarrow L \cup \hat{\mathbf{x}}, U \leftarrow U \setminus \hat{\mathbf{x}}. $$

Return U, L.

We now formulate more precisely the link between the discriminative approach and the goal of minimizing the divergence. Note in particular that the model $\Psi$ is trained to discriminate L from U and not from the global pool X.

$$ P_{L \cup S} = \eta P_L + (1 - \eta) P_S, \quad \eta = \frac{|L|}{|L| + k}, $$

where $P_S$ refers to the empirical distribution induced by S.

The H-divergence can be considered as

$$ d_{\mathcal{H}}(P, Q) = 2 \sup_{h \in \mathcal{H}} \left| \Pr_{x \sim P}[h(x) = 1] - \Pr_{x \sim Q}[h(x) = 1] \right|. $$

Then for any discriminator $h \in \mathcal{H}$, we have

$$ \mathbb{E}_{P_{L \cup S}}[ht] = \eta \mathbb{E}_{P_L}[ht] + (1 - \eta) \mathbb{E}_{P_S}[ht]. $$

By linearity and applying the triangular inequality, we get:

$$ \begin{align*} d_{\mathcal{H}}(P_{L \cup S}, P_U) &= 2 \sup_{h \in \mathcal{H}} \left| \eta \mathbb{E}_{P_L}[ht] + (1 - \eta) \mathbb{E}_{P_S}[ht] - \mathbb{E}_{P_U}[ht] \right| \\ &= 2 \sup_{h \in \mathcal{H}} \left| \eta (\mathbb{E}_{P_L}[ht] - \mathbb{E}_{P_U}[ht]) + (1 - \eta) (\mathbb{E}_{P_S}[ht] - \mathbb{E}_{P_U}[ht]) \right| \\ &\le \eta d_{\mathcal{H}}(P_L, P_U) + (1 - \eta) d_{\mathcal{H}}(P_S, P_U). \end{align*} $$

## 4 Discussion

There is almost an active learning method, accompanied with a generalization bound, for every discrepancy between two probability distributions. To address the combinatorial obstacle of minimizing over plug-in estimates, convex relaxation or integer programming OT techniques were shown promising. Despite their theoretical appeal in providing explicit generalization bounds, methods based on discrepancy minimization often rely on computationally intensive convex relaxations or greedy approximations, which may hinder scalability to very large datasets. Furthermore, while these approaches effectively mitigate sampling bias by remaining faithful to the underlying distribution, their robustness remains an open question regarding data characteristics such as label noise, multimodality, or the presence of outliers.
The first improvement of this work would be an extended benchmark of the discussed discrepancies, and we see two directions to document the framework empirically: (i) on parameterized distributions, study the impact of label noise, separability, inductive bias and multimodality on performance, for the different divergences (maybe with specific interest in IPMs for smooth- *ing varying* support function class *F*), and (ii) try to connect the approach with two-sample comparison tests, with empirically tract the type-I and type-II errors of such tests, w.r.t. the divergence and the discussed data parameters. On a more theoretical side, we think as pointed out by [16], that extend to a general *Φ*-divergence framework, could generalize the method. Then, probably using Csiszar *φ*-divergence variational representation, generalized Pinsker inequalities, and other tools, it would be desirable to match the generalization results, with properly chosen *φ*.

References

[1] BOBBIA, B., AND PICARD, M. Active learning for regression based on wasserstein distance and groupsort neural networks, 2024.

[2] DASGUPTA, S. Two faces of active learning. *Theoretical Computer Science* **412**, 19 (2011), 1767–1781. Algorithmic Learning Theory (ALT 2009).

[3] DINH, L., SOHL-DICKSTEIN, J., AND BENGIO, S. Density estimation using real nvp, 2017.

[4] FOURNIER, AND GUILLIN. On the rate of convergence in wasserstein distance of the empirical measure. *Probab. Theory Relat. Fields* **162** (2015), 707–738.

[5] GAL, Y., ISLAM, R., AND GHAHRAMANI, Z. Deep Bayesian active learning with image data. In *Proceedings of the 34th International Conference on Machine Learning* (06–11 Aug 2017), D. Precup and Y. W. Teh, Eds., vol. 70 of *Proceedings of Machine Learning Research*, PMLR, pp. 1183–1192.

[6] GISSIN, D., AND SHALEV-SHWARTZ, S. Discriminative active learning, 2019.

[7] GUO, C., PLEISS, G., SUN, Y., AND WEINBERGER, K. Q. On calibration of modern neural networks. In *Proceedings of the 34th International Conference on Machine Learning* (06–11 Aug 2017), D. Precup and Y. W. Teh, Eds., vol. 70 of *Proceedings of Machine Learning Research*, PMLR, pp. 1321–1330.

[8] GUO, Y. Active instance sampling via matrix partition. In *Advances in Neural Information Processing Systems* (2010), J. Lafferty, C. Williams, J. Shawe-Taylor, R. Zemel, and A. Culotta, Eds., vol. 23, Curran Associates, Inc.

[9] HERDE, M., HUSELJIC, D., SICK, B., AND CALMA, A. A survey on cost types, interaction schemes, and annotator performance models in selection algorithms for active learning in classification. *IEEE Access* **9** (2021), 166970–166989.

[10] HOI, S. C. H., JIN, R., AND LYU, M. R. Large-scale text categorization by batch mode active learning. In *Proceedings of the 15th International Conference on World Wide Web* (New York, NY, USA, 2006), WWW ’06, Association for Computing Machinery, p. 633–642.

[11] JENTZEN, A., KUCKUCK, B., AND VON WURSTEMBERGER, P. Mathematical introduction to deep learning: Methods, implementations, and theory, 2025.

[12] LEI, Y., DOGAN, U., ZHOU, D.-X., AND KLOFT, M. Data-dependent generalization bounds for multi-class classification. *IEEE Transactions on Information Theory* **65**, 5 (2019), 2995–3021.
[13] LEWI, J., BUTERA, R., AND PANINSKI, L. Efficient active learning with generalized linear models. In *Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics* (San Juan, Puerto Rico, 21–24 Mar 2007), M. Meila and X. Shen, Eds., vol. 2 of *Proceedings of Machine Learning Research*, PMLR, pp. 267–274.

[14] MAHMOOD, R., FIDLER, S., AND LAW, M. T. Low-budget active learning via wasserstein distance: An integer programming approach. In *International Conference on Learning Representations* (2022).

[15] MANSOUR, Y., MOHRI, M., AND ROSTAMIZADEH, A. Domain adaptation: Learning bounds and algorithms, 2023.

[16] MENDEN, V., SALEH, Y., AND ISKE, A. Bounds on the generalization error in active learning, 2024.

[17] RITTLER, N., AND CHAUDHURI, K. A two-stage active learning algorithm for $k$-nearest neighbors, 2023.

[18] SETTLES, B. Active learning literature survey. Computer Sciences Technical Report 1648, University of Wisconsin–Madison, 2009.

[19] SHUI, C., ZHOU, F., GAGNÉ, C., AND WANG, B. Deep active learning: Unified and principled method for query and training. In *Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics* (26–28 Aug 2020), S. Chiappa and R. Calandra, Eds., vol. 108 of *Proceedings of Machine Learning Research*, PMLR, pp. 1308–1318.

[20] TONG, S., AND KOLLER, D. Support vector machine active learning with applications to text classification. *J. Mach. Learn. Res.* 2 (Mar. 2002), 45–66.

[21] VIERING, T. J., KRIJTHE, J. H., AND LOOG, M. Nuclear discrepancy for single-shot batch active learning. *Mach. Learn.* 108, 8–9 (sep 2019), 1561–1599.

[22] WANG, H., DU, L., ZHOU, P., SHI, L., AND SHEN, Y.-D. Convex batch mode active sampling via alpha-relative pearson divergence. *Proceedings of the AAAI Conference on Artificial Intelligence* 29, 1 (Feb. 2015).

[23] WANG, Z., AND YE, J. Querying discriminative and representative samples for batch mode active learning. In *Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining* (New York, NY, USA, 2013), KDD '13, Association for Computing Machinery, p. 158–166.

[24] YANG, Y., AND LOOG, M. A benchmark and comparison of active learning for logistic regression. *Pattern Recognition* 83 (nov 2018), 401–415.