Bounds on the Generalization Error in Active Learning

Venue: NLDL_org_2025_Conference
Published: 2024-09-03 19:57:57

Abstract: We establish empirical risk minimization principles for active learning by 
deriving a family of upper bounds on the generalization error. Aligning with empirical observations, the bounds suggest that superior query algorithms can be obtained by
combining both informativeness and representativeness query strategies, where the latter is assessed using integral probability metrics.
 To facilitate the use of these bounds in
application, we systematically link diverse active
learning scenarios, characterized by their loss functions and hypothesis
classes to their corresponding upper bounds. Our results show that
regularization techniques used to constraint the complexity of various hypothesis
classes are sufficient conditions to ensure the validity of the bounds.
The present work enables principled
construction and empirical quality-evaluation of query algorithms in active learning.

Main paper: 
 : 
 indeed, a very appealing setting for such problems and has been extensively applied for, e.g., parameteric Schrödinger equations [6] [7] [8] .The crucial task in all AL scenarios is to query the labels of the most useful datapoints while minimizing the number of queries [3] . The rationale behind the design of such query algorithms can be divided into two categories [3, 9] . The first category relies on the informativeness criterion [10, 11] , where the query algorithm aims at selecting the most informative samples, whereby shrinking the space of the candidate hypotheses as fast as possible. Such query algorithms indeed introduce a sampling bias [9] , as the selected training dataset is not necessarily i.i.d. sampled from the true distribution. This renders the query algorithm prone to oversampling outliers that are not very representative of the application domain, where the model would be employed [3, 12] . The second category is based on the representativeness criterion, where the query algorithm aims at selecting samples that are representative of the patterns present in the unlabeled data. Such methods tend to perform well when only a small labelled dataset is available, but their performance rather deteriorate with increasing labeled-dataset size. Numerous empirical and theoretical studies indeed point out that superior query algorithms can be obtained by combining both criteria [9, 12, 13] .AL algorithms are often heuristic in designing the specific query criterion or ad hoc in measuring and combining the informativeness and representativeness of the samples. For example, a common heuristic to combine both criteria is to query data points by a random-sample selection that gives higher weights to samples corresponding to large uncertainties. Since the selection of new points is random, the query algorithm ends up querying representative datapoints. While such heuristics are often successful in practice, they lack a principled approach and are often domain-specific [3] . Some first steps into a more principled approach to AL were taken in Wang and Ye [14] , where the authors derived an upper bound on the generalization error using the maximum mean discrepancy (MMD) as a measure of the representativeness of a sample. Later, a similar result was obtained using the Wasserstein distance as a measure of representativeness [15] . However, these results assumed rather harsh conditions on the loss function and the supervised-learning problem that restrict the applicability of these upper bounds.imposing constraints on the complexity of the hypothesis class, often using regularization techniques.Formally, this common practice in supervised learning can be understood as an inductive principle, where the minimization of the true risk is replaced by the minimization of an upper bound to it. Such upper bounds exist in a variety of forms, often involving different notions of complexity of the hypothesis class [1, 2, 16] . As an example, we cite the following celebrated result.Theorem 1. Assume that ℓ(y, h(x)) ≤ k for some k > 0, any h ∈ H and any (x, y) ∈ Z. Then, for any δ > 0 and any h ∈ H, with probability of at least 1 -δ over the choice of the training set D m it holds thatEQUATIONwhere Rad(K) is the Rademacher complexity defined byRad(K) := E σ sup k∈K 1 m m i=1 σ i k(x i ) ,where E σ denotes the expectation operator with respect to the distribution of σ.Proof. See Shalev-Shwartz and Ben-David [16, Theorem. 26.5].Minimizing the upper bound in (1) was shown to be equivalent to common supervised-learning practices across a variety of loss functions and hypothesis classes. Moreover, such upper bounds were shown to accommodate novel statistical behaviors, such as the generalization error of deep neural networks [17] .Similar to the standard supervised-learning setting, the goal in AL is to find a hypothesis of h ∈ H that minimizes the true risk. However, to achieve this goal, the oracle in AL is required to select a minimal set of observations. This often violates the passive-learning assumption that the training data is i.i.d. sampled from the true distribution. Generally, the training data D in AL follows the distribution P Ẑ := P Q P Y |X , i.e., it shares the same conditional distribution as the true distribution P Z , but has a different marginal distribution P Q . The choice of an optimal query algorithm can, thus, be framed as finding an optimal marginal distribution P Q .The representativeness criterion in AL can be understood as the requirement that P Q does not deviate too much from the true marginal P X . To quantify this deviation, we use the notion of IPM [18] . Definition 1 (Integral Probability Metrics). Consider the measure space (X, B(X)) where B(X) denotes the Borel σ-algebra generated by X ⊂ R n . Further let F ⊆ B C with B C the set of real-valued measurable functions on X, which are bounded by C > 0. Then, for two probability measures P X and P Q on (X, B(X)) we define the integral probability metric with respect to the generator F asEQUATIONChoosing different generators F in (2) leads to different statistical distances. We consider the following two generators:(1) The Total Variation metric (d FTV ) is obtained by consideringF TV := {f : X → R : ∥f ∥ ∞ ≤ 1},where ∥f ∥ ∞ denotes the supremum norm.(2) The Kantorovic metric (d F K ) is obtained by consideringF K := {f : X → R : ∥f ∥ L ≤ 1},where∥f ∥ L := sup |f (x) -f (y)| ∥x -y∥ 2 : x ̸ = y, x, y ∈ Sdenotes the Lipschitz semi-norm on a metric space (S, ρ).To establish the ERM principle for AL, we need the following concept.Definition 2 (Maximal Generator). Let F ⊆ B C be a generator. We define the set of maximal generators R F to be the set of functions f ∈ B C with the propertyX f (x)dP X (x) - X f (q)dP Q (q) ≤ d F (P X , P Q ),for all probability measures P X and P Q on (X, B(X)).In other words, R F describes the largest set inB C preserving the value of d F (•, •). It is clear that F ⊂ R F . Lemma 1. Let (Y, B(Y), P ) be a probability space, F ⊂ B C a generator and f : Y × X → R a B(Y × X)- measurable function with f (y, •) ∈ F ⊂ B C for all y ∈ Y. Then g(•) := Y f (y, •)dP (y)is a well-defined function on X and it holds thatg ∈ R F .Proof. See Müller [18, Theorem 3.4 ].Note that Lemma 1 also holds for any f ∈ R F .The stage is now ready to state our results. R P Z (h) ≤ R Dm∼P Ẑ (h) + d F (P X , P Q ) + 2 Rad(l • H • Dm ) + k 2 log( 4 δ ) m .(3) 257Proof. We note that the hypothesis of this theorem 258 satisfies the conditions of Theorem 1. Therefore, it 259 follows that 260 and note that ℓ(y, h(•)) = ℓ y satisfies all the hy-266 potheses of Lemma 1 and hence g ∈ R F . Thus, 267 using the definition of R F we can estimate to hold. We consider the learning setting to be de-R P Z (h) ≤R P Z (h) -R P Ẑ (h) + R Dm∼P Ẑ (h) + 2 Rad(l • H • Dm ) + k 2 log( 4 δ ) m . (4) 261 Set K(h) := R P Z (h) -R P Ẑ (h) and note that 262 K(h) = X Y l(y, h(x))dP Y |X (y)dP X (x) - X Y l(y, h(x))dP Y |X (y)dP Q (x) = X Y l(y, h(x))dP Y |X (y)dP X (x) - X Y l(y, h(x))dP Y |X (y)dP Q (x)268 D(h) = X g(x)dP X (x) - X g(x)dP Q (x) ≤ sup f ∈R F X f (x)dP X (x) - X f (x)dP Q (x) = sup f ∈F X f (x)dP X (x) - X f (x)dP Q (x) = d F (P X , P Q ).termined by a choice of the hypothesis class H, the domain X, the codomain Y and the loss function ℓ.In the following X ⊂ R n and Y ⊂ R unless otherwise specified.We consider first a regression task employing the linear hypothesis classH L := {h : X → Y : h(x) = w T x+b, w ∈ R n , b ∈ R},where w and b are the learnable parameters along with the loss ℓ 1 (y, h(x)) := |y -h(x)| defined for any y ∈ Y and h ∈ H L .Theorem 3 (Linear Hypothesis Classes). Consider a regression problem employing H L and the ℓ 1 -loss. Assume that w is such that ∥w∥ 2 ≤ 1. Then the true risk of a hypothesis h ∈ H L can be bounded as in Theorem 2 by choosing the generator F = F K .Proof. Analogous to our previous notation we set ℓ y 1 (x) := ℓ 1 (y, h(x)) for any y ∈ Y.Fix y ∈ Y and h ∈ H L . By Theorem 2, it suffices to show that ℓ y 1 ∈ F K . For any x 1 , x 2 ∈ X, it holds that|ℓ y 1 (x 1 ) -ℓ y 1 (x 2 )| = |h(x 1 ) -y| -|h(x 2 ) -y| ≤ (w T x 1 + b) -(w T x 2 + b) ≤ w T (x 1 -x 2 ) ≤ ∥w∥ 2 ∥x 1 -x 2 ∥ 2 ,where we used the reversed-triangle inequality and the Cauchy-Schwarz inequality. Setting ∥w∥ 2 ≤ 1 implies that ∥ℓ y 1 ∥ L ≤ 1 and hence ℓ 1 ∈ F K .Theorem 1 suggests that the natural regularization constraint ∥w∥ 2 ≤ 1, commonly used for mitigating overfitting, is sufficient to bound the true risk of a linear hypothesis class in an AL setting.We now look at an example of a binary classification problem, i.e., Y = {-1, 1}, using feed-forward neural networksH NN := {h : X → Y : h(x) = sign(o T f (x) + b)}with weight o ∈ R n and bias t ∈ R in the output layer and the neural network function f(x) = W (L) σ(W (L-1) • • • σ(W (1) x+b (1) ) • • •+b (L-1))+b (L) , where σ is the ReLU activation function, and W (l) , b (l) are the weight matrices and bias vectors, respectively. The learnable parameters are assumed to have arbitrary finite dimensions. We consider the hinge loss ℓ H (y, h(x)) = max (0, 1 -y(w T x + b)). Condition IPM 1 , can be used to guide the design of query strategies in AL. To this end, the user must first identify which setting in Table 1 matches their scenario. Once identified, the next step is to derive an algorithm that minimizes an empirical estimate of the relevant upper bound, as done, e.g., in the work of Wang and Ye [14] .H L ℓ 1 ∥w∥ 2 ≤ 1 d F K Regression ℓ 2 ∥w∥ 2 ≤ 1-M Y -|b| M X d FTV H g ℓ 1 2M X σ 2 ∥w∥ 2 1 ≤ 1 d F K H σ(L) ℓ log ∥w∥ 2 ≤ log(e-1)M X d FTV Classification H SVM ℓ H ∥w∥ 2 ≤ 1 d F K H NN ℓ H ∥o∥ 2 L i=1 ∥W ∥ 2 ≤ 1 d F KAdditionally, our results can be used to evaluate the quality of ad hoc query strategies in AL. A necessary step towards such an application is to derive upper bounds to the true risk that employ empirical estimates of the IPM, see, e.g., Sriperumbudur et al. [21] for general discussion on empirical estimates of IPMs.We note that the choice of the IPM as a measure of representativeness is not unique. Other choices of metrics to measure the representativeness of the samples, such as, e.g., ϕ-divergences, can be considered [22] . We leave this as an open question for future research. A More Learning Settings Theorem 3 and Theorem 4 are only two examples on how to constraint the hypothesis class for deriving a suitable generalization bound in an AL setting. In the following we provide the reader with further results, which are also summarized in Table 1 .We start by looking at the Gaussian hypothesis class defined asH g := h : X → Y : h(x) = n i=1 w i g(x, t i ) , where g(x, t i ) = e - ∥x-t i ∥ 2 2σ 2, for some fixed σ > 0, and learnable parameters w = (w 1 , . . . , w n ) ∈ R n and t i ∈ X for any i = 1, . . . , n.Theorem 5 (Gaussian Hypothesis Classes). Consider a regression problem employing H g and the ℓ 1 -loss. Assume X to be compact, with bound M X , and w to be such that 2M X σ 2 ∥w∥ 1 ≤ 1, then the true risk of a hypothesis h ∈ H g can be bounded as in Theorem 2 by choosing the generator F = F K .Proof. Set ℓ y 1 (x) := ℓ 1 (y, h(x)) for any y ∈ Y. Fix y ∈ Y and h ∈ H g . By Theorem 2, it suffices to show that ℓ y 1 ∈ F K . For arbitrary t i ∈ X observe that∂ ∂x g(x, t i ) = 1 σ 2 e - ∥x-t i ∥ 2 2σ 2 ∥x -t i ∥ 2 ≤ 2M X σ 2 .Thus, the function f (x) = g(x, t i ) is Lipschitz continuous on X with ∥f ∥ L ≤ 2M X σ 2 . Finally, for any x 1 , x 2 ∈ X we have|ℓ y 1 (x 1 ) -ℓ y 1 (x 2 )| = |h(x 1 ) -y| -|h(x 2 ) -y| ≤ n i=1 w i g(x 1 , t i ) - n i=1 w i g(x 2 , t i ) ≤ n i=1 |w i | |g(x 1 , t i ) -g(x 2 , t i )| ≤ n i=1 |w i | 2M X σ 2 ∥x 1 -x 2 ∥ 2 = ∥w∥ 1 2M X σ 2 ∥x 1 -x 2 ∥ 2 . Setting ∥w∥ 1 2M X σ 2 ≤ 1 implies that ∥ℓ y 1 ∥ L ≤ 1 and hence ℓ 1 ∈ F K .In contrast to Theorem 3 and Theorem 4, Theorem 5 requires the input space X to be compact. Such assumptions are not uncommon in practice. For example, in image classification, the input space is bounded by the pixel values. For example, considering grey images, it is valid to assume that the pixel Such bounded input domains also show up naturally in other applications, such as geographic locations or financial data. Additionally, in practice, one can preprocess the input data to fit within certain bounds. For example, feature scaling or normalization is commonly used to bound the input space to a fixed interval, see [23, 24] . In these scenarios, the constraints are inherent to the domain X, and they effectively regularize the learning process without being formalized as part of the algorithm. Furthermore, such constraints are useful assumptions in the context of kernel methods. For example, assuming the input data lies within a compact set helps in controlling the Rademacher complexity, which provides better generalization bounds, see [16] .This argumentation can also be applied to a-priori constraints on the codomain Y, which we will use in the following result for the linear hypothesis classes. M Y + ∥w∥ 2 M X + |b|, Thus, setting ∥w∥ 2 ≤ 1-M Y -|b| M X we get ℓ y 2 ∈ F TV .As previously mentioned, restrictions on the domain X and codomain Y are used in Theorem 6.Looking at an example of a learning setting, where We set Y = {0, 1} and denote by e the Euler number.X = [-Theorem 7 (Logistic Hypothesis Classes). Consider a binary classification problem employing H σ(L) and the logistic loss. Assume X to be compact, with 638 bound M X , and w to be such that ∥w∥ 2 ≤ log(e -639 1)M X , then the true risk of a hypothesis h ∈ H σ(L) 640 can be bounded as in Theorem 2 by choosing the 641 generator F = F TV .Proof. Set ℓ y log (x) := ℓ log (y, h(x)) for any y ∈ Y. 643 Fix y ∈ Y and h ∈ H σ(L) . By Theorem 2, it suffices 644 to show that ℓ y log ∈ F TV . We first consider y = 1 645 and observe that for any x ∈ X, we have |ℓ y log (x)| = 646 log (1 + e -w T x ). Similarly, for y = 0, we observe 647 that |ℓ y log (x)| = log (1 + e w T x ) for any x ∈ X. Thus, 648 setting ∥w∥ 2 ≤ log(e-1) M X implies ∥ℓ y log ∥ ∞ ≤ 1 and 649 hence ℓ y log ∈ F TV .Next we look at the hypothesis class of linear 651 support vector machines (SVM) given by  
 
 Appendix:  


Decision: The paper established ERM generalization bounds for active learning, based on Integral Probability Metrics. Some issues were raised by reviewers, mostly related to lack of direct applications of the proposed theoretical framework to concrete algorithms. Yet, the derivation of the proposed bound is meaningful and could lead to improvments in active learning algorithms. I believe it can be of interest for the audience of the conference, and therefore I recommend to accept it in the program.