Agnostic Multi-Group Active Learning
Authors: Nicholas Rittler
Kamalika Chaudhuri
Venue: NeurIPS 2023 poster (2023)
Keywords: learning theory
active learning
multi-group learning
TL;DR: We give active learning algorithms for the problem of picking a classifier that should perform well on all distributions in a collection.

Abstract: Inspired by the problem of improving classification accuracy on rare or hard subsets of a population, there has been recent interest in models of learning where the goal is to generalize to a collection of distributions, each representing a ``group''. We consider a variant of this problem from the perspective of active learning, where the learner is endowed with the power to decide which examples are labeled from each distribution in the collection, and the goal is to minimize the number of label queries while maintaining PAC-learning guarantees. Our main challenge is that standard active learning techniques such as disagreement-based active learning do not directly apply to the multi-group learning objective. We modify existing algorithms to provide a consistent active learning algorithm for an agnostic formulation of multi-group learning, which given a collection of $G$ distributions and a hypothesis class $\mathcal{H}$ with VC-dimension $d$, outputs an $\epsilon$-optimal hypothesis using $\tilde{O}\left( (\nu^2/\epsilon^2) G d  \theta_{\mathcal{G}}^2 \log^2(1/\epsilon) + G\log(1/\epsilon)/\epsilon^2 \right)$ label queries, where $\theta_{\mathcal{G}}$ is the worst-case disagreement coefficient over the collection. Roughly speaking, this guarantee improves upon the label complexity of standard multi-group learning in regimes where disagreement-based active learning algorithms may be expected to succeed, and the number of groups is not too large. We also consider the special case where each distribution in the collection is individually realizable with respect to $\mathcal{H}$, and demonstrate $\tilde{O}\left( G d \theta_{\mathcal{G}} \log(1/\epsilon) \right)$ label queries are sufficient for learning in this case. We further give an approximation result for the full agnostic case inspired by the group realizable strategy.

Agnostic Multi-Group Active Learning
Nick Rittler
Kamalika Chaudhuri
University of California San Diego nrittlerQucad.ed edu
University California San Diego kamal ikaccs. wwcelesssusdd.. edu
Abstract
Inspired by the problem of improving classification accuracy on rare hard subsets of population, there has been recent interest in models of learning where the goal to generalize to a collection of distributions, each representing "group". We consider variant of this problem from the perspective of active learning, where the learner is endowed with the power to decide which examples are labeled from each distribution in the collection, and the goal is minimize the number label queries while maintaining PAC-leaming guarantees. Our main challenge is that standard active learning techniques such as disagreemenntbasee active learning do not directly apply to the multi-group learning objective. We modify existing algorithms to provide consistent active learning algorithm for agnostic formulation of multi-group learning, which given a collection of G distributions and hypothesis class H with VC-dimension d, outputs c-optimal hypothesis using Ô ((>2 Gdff log" (1/c) + G 1og(1/c)/e3) label queries, where 6g is the worst-case disagreement coefficient over the collection. Roughly speaking, this guarantee improves upon the label complexity of standard multi-group learning regimes where disagreement-baseee active learning algorithms may be expected to succeed, and the number of groups is not too large. We also consider the special case where each distribution in the collection is individually realizable with respect to H. and demonstrate Ô (Gd0g (o(()))) label queries are sufficient for learning in this case. We further give an approximation result for the full agnostic case inspired by the group realizable strategy.
Introduction
There is growing theory literature concerned with choosing classifier that performs well multiple subpopulations or "groups" 2 7 4
5 6 3] In many cases, the motivation comes from perspective of fairness, where a typical requirement is that we classify with similar accuracy across groups 77 6, [4. In other cases, the motivation may simply be to train more reliable classifiers. For example, cancer detection models with good overall accuracy often suffer from poor ability detect rare subtypes of cancer that are not well-represented or identified in training. This suggests that naive ERM may be insufficient in practice [8.
In this work, we consider the following formulation of "multi "multi-group" learning. The learner is given (P |G g=1 each corresponding group, and hypothesis class H. and wants to pick a classifier that approximately minimizes the maximum classification error group distributions. We consider this problem from active learning perspective, where the learner has the power to choose which examples from each group it wants to label during training. design schemes for choosing which examples from each group should be labeled, where the goal is to minimize the number of label queries while retaining PAC-learning guarantees.
collection of distributions
In standard extension of the active learning literature, we set
major challenge harnessing the power of active algorithms even standard agnostic settings is making sure they consistent. In the case of active learning, this means that as the number
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

of number of labels requested approaches infinity, the learner outputs an optimal hypothesis. To complicate things further, the main algorithmic paradigm for consistent agnostic active learning over single distribution disagreement based active learning (DBAL.) fails to admit direct application in the multi-group learning objective. The fundamental idea in DBAL that the learner may safely spend its labeling budget in the "disagreement region", subset of instance space where empirically pelloperfonning hypotheses disagree about how new examples should be labeled. When the learner need only consider single distribution, error differences between classífiers are specified entirely through their performance on the disagreement region, and so spending the labeling budget here allows the learner to figure out which hypotheses are best while saving on labels. The problem is that when multiple group distributions must be considered, the absolute errors of classifiers on each group must be estimated to compare performance of two classifiers in their worst case over collection, and this property no longer holds.
We resolve this via the observation that, while we cannot spend all our labeling budget in the disagreement region, we can exploit the agreement in its complement to cheaply estimate absolute errors of classifiers on each group. In particular, we estimate the absolute errors by choosing representative classifier hay in the set of empirically well-performing classifiers H'' and estimating its error on the complement of the disagreement region on each group distribution. These error estimates can be used to construct estimates for the absolute errors on each group for each h E H'' at the statistical cost of estimating coin bias, leading to relatively cheap, consistent active strategy.
We analyze the number of label queries made by this scheme in terms of a standard complexity measure in the active learning literature called the "disagreement coefficient" [9] 10, and show an upper bound of Ô (1²² /22 Gdd6 log" (1/c) + G (l))))))) where 0g is the maximal disagree- ment coefficient over the collection of group distributions. We discuss some regimes where this label complexity can be expected to push below sample complexity lower bounds for learner that can request samples from each group distribution during training, but does not have power to abstain from labeling specific examples.
We also consider the special case of agnostic learning where each group distribution is individually realizable, but no single hypothesis separates all groups simultancously. In this case, we show that all dependence on 1/²² e22 in the label complexity can be replaced with log(1/e) when disagreement coefficients are bounded. It turns out that using the strategy we develop in this special case leads to an approximation algorithm for the general agnostic case, for which we give guarantees.
2 Related Work
2.1 Multi-Group Learning
The majority of the empirical work on multi-group learning has been through the lens of "Group- Distributionally Robust Optimization" (G-DRO) [I] 12 [3]. The goal in G-DRO is to choose a classifier that minimizes the maximal risk against unknown mixture over a collection of distri- G butions {Dgig- representing groups. One assumes a completely passive sampling setting all data is given the learner at the beginning of training, and the learner has no ability to draw ex- tra, fine-grained samples. The strategy is usually empirical risk minimization (ERM) or some regularized variant- on the empirical max loss over groups; for set of classifiers parameterized by & 4, letting S, denote the set of examples in the training set coming from Dg, one performs minge# [G] |& E ((..))) ((fo(z;), 34) for some loss L. It is important to note that the learner knows the group identity of each sample in the training set, but is not provided with group information at test time, precluding the possibility of training a separate classifiers for cach group.
"Multi-gruup PAC learning" consider the multi-group problem under the passive sampling assumption from a more classical learning-theoretie perspective 77 6). Here, one assumes there is a single distribution D from which one is given samples, but also a collection of subsets of instance space over which one wants to learn conditional distributions. Given a hypothesis class H. the learner tries to improperly learn a classifier ff that competes with the optimal hypothesis on each conditional distribution specified by a group g in the collection formally, one requires that for a given error tolerance e, ʃ has the property Vy E G. PD( # y|a E g) < înlлeи (D(())) + y/ı E g) + e with high probability. An interesting wrinkle this literature is that the group identity of samples is available at both training and test times. It has been shown that sample complexity of
2

---

Table 1:
Overview of the complexity of multi-group learning. The notation hide factors logarithmic in d, G, 1/6, and log(1/e). We reserve discussion of regimes in which algorithm improves
results in Collaborative Learning for Section 5.
Problem
Full Agnostic
Group-Realizable
Passive Multi-Group 6
Ô (log((1))/7e²)
Ô (log(1 ((()))())))
Collaborative Learning
3
Ô ((llog(/e)//++GGC)
Active Multi-Group (us)
Ô
Ô (Gdlog (1/e))
Ô (log((H()/7e") is sufficient for agnostic learning in this model, where is the minimal mass of a group y under D (6).
"Collaborative learning" studies the multi- group problem under an alternative sampling model []] 23. In this case,
given collection of distributions 1DDG each corresponding to group. Given some hypothesis class H. the goal is to learn a classifier f. possibly improperly, would like f to satisfy that is evaluated against its worst-case loss over D1..... De; formally, max PD, (f(z) # y) I inf ma PD, (h(x) + y) + c. In contrast with the learner may decide how many samples from each D, wants to collect during training, and group identity is hidden on test examples. This models the case where learner may want collect more data from particularly difficult group of instances, such rare or hard-to-diagnose type of cancer. It has been shown for finite hypothesis classes that @log ((log((H1)/e G/e²) total samples over all groups are necessary and sufficient to learn in this model; ((dlog(L))//++/// total samples are sufficient for VC-classes 33.
Our work extends the model of collaborative learning, and endows the learner with the ability to decide which samples from each group distribution Dg should be labeled. This is the standard framework of active learning, applied to the multi-group setting. As in collaborative learning, assume group identity is hidden at test time.
2.2 Active Learning
Active learning concerns itself with the development learning algorithms for training classifiers that have power over which training examples should be labeled [14 15]. The field has largely focused on uncovering settings in which algorithmic approaches reduce the amount of labels required for PAC-style learning guarantees beyond sample complexity lower bounds that apply to i.i.d. data collection from the underlying distribution [16] [7]. In the agnostic, 0-1 loss setting, the standard upper bounds for label complexity follow Ô (e log((/c)) + du² /2). Here, v is the "noise rate", i.e. the true error of the optimal hypothesis h" and 0 is distribution-dependee
parameter called the "disagreement coefficient". Thus, gains of active strategies over standard passive lower bounds of Ω (e)) depend on certain easiness conditions like small noise rates and bounded disagreement coefficients [15].
The vast majority of the work on active learning has been done in the 0-1 loss setting [8 10 19
20 21.. It has been significantly harder to push the design of active learning algorithms past the regime of accuracy a fixed distribution. While some work has attempted to generalize classical ideas of active learning to different losses [22], these are heavily outnumbered in the literature.
As previously mentioned, the most difficult part of designing agnostic active learning strategies is maintaining consistency. The issue comes down to phenomenon referred to as "sampling bias" : because active learners would like to target certain parts of space to save on labels, there is risk that the learner prematurely stops sampling on part of space in which there is some detail in the distribution that could not be detected at higher labeling resolution. This can easily lead to inconsistent strategies [5]. Thus, major contribution our work is exhibiting consistent active scheme for the multi-group problem.
3

---

3 Preliminaries
3.1 Learning Problem
We study a binary classification setting where examples fall in some instance space X, and labels lie in y = (-1,1). We suppose we are given some pre-specified, finite collection of distributions g = (Dg]==] g= over X' x y corresponding to groups. Given a hypothesis class H. of measurable classifiers with VC-dimension d, the goal of the leaner is to pick some h E H from finite data that performs well across all the distributions in & in the worst case. Let Lo g) == PD, (h(x) & y) be the error of a hypothesis h on group g. Formally speaking, the learner would like choose classifier approximately obtaining
inf max Lg(h g). NEH gE[G)
(h) as shorthand for maXge[(] Lg(h g). We use hnf ( (h) to denote the "noise rate" of H on the multi-distribution objective. The use of the term "agnostic" throughout reflects the fact that we make no assumption that v 0 in our algorithm design or analysis. We assume for simplicity that there is some it" E H attaining v.
using finite data. We often use Lg
3.2 Active Learning Model
We consider a standard active learning model specified as follows. Let supp(g) denote the support of the marginal over instance space of Dg. The active learner has access to two sampling oracles for each distribution specified by Dg. The first is (.).). which given a set S C Y measurable with respect to Dg, returns an unlabeled sample from Da conditioned on S; if Pp, (I E S) = 0. then U, (S) returns "None". The second (.).). which given point in supp(g). returns a sample from the conditional distribution over labels specified by z and g. More formally, querying Uy(S) for S such that Pp, (x E 5) * is equivalent to drawing i.i.d. samples according to marginal over instance space of Dg (independent of previous randomness), and returning the first example that falls in S; querying the oracle (x) for x E (gpp(g) is equivalent to receiving a sample from a Rademacher random variable with parameter FD, (Y 1|X v)).
As standard in active learning, the active learner is assumed to have functionally unlimited access to queries from (-). On the other hand, queries to oracles O₂(:) (-) are precious: the "label complexity" of strategy executed by the active learner is the sum of queries to oracles (-(-) over all g, and is to be minimized given desired generalization error guarantee.
4 Challenges in Multi-Group Active Learning
In this section, we give some background on classical disagreement- based methods on a single distribution, and discuss in more detail the challenge of designing consistent active learning strategies in the multi-group setting.
4.1 Background on Disagreement- Based Active Learning
Almost all agnostic active learning algorithms for accuracy over a single distribution boil down to disagreement-basse methods [8. 10 15| 16]. The fundamental idea in this school of algorithms is that one can learn the relative accuracy of two classifiers h and ht' by only requesting labels for examples in the part of instance space on which they disagree about how examples should be labeled. More generally, given a set of classifiers H' C H. one can consider the "disagreement region" of H', defined as
A(H') = (x E X 3h, H' E H' s.l. h(x)) + h'(x)}
As alluded to above, the difference in accuracy of classifiers h, hi H' is specified entirely through this inherently Sabel-independent notion. For a single distribution D, we may write
PD (1(x)) # v) FD (1'(x) + v) IPD (AH)))
(n((()) + A(H') - FD (1'(x) + v A(H'))
as by definition, h, h have the same conditional loss on AHH'). Inspired by this observation, the idea is to label examples in A A(H(), and ignore those outside of it. This allows the learner to learn about the relative performance of classifiers while saving the labels of examples falling in AHH').

---

In running a DBAL algorithm, one hopes certain classifiers quickly reveal themselves to be empirically so much worse on Á (HH)) than the current ERM hypothesis, that by standard concentration bounds, they can be inferred to be worse than 6-optimal on /) with high probability. Elimination of these classifiers shrinks the disagreement region, allowing the labeling to become further fineggrined. Given the above loss decomposition, this leads to consistent active learning strategies.
4.2 Labeling in the Disagreement Region: No Longer Enough
In the gulti-group setting, the strategy of comparing performance of classifiers solely on A(H') breaks down. Although the classifiers in H' still agree in A(H'), this is not enough to infer differences in the worst error over groups 1.g this is because differences in performance on A(H') are not generally representative of differences in absolute errors over group distributions. The following simple example makes this concrete.
Example 1. Consider the task of determining which of two classifiers h and h' has lower worst case error over distributions D1 and D2 with marginal supports S1 S X and S2 C. Let their disagreement region be denoted by A far X h(x)) * M(x)), and let ((f denote the conditional loss of classifier f on S; n A under D,. Suppose we only know their conditional losses
on A n S1 and A n S2 under D1 and D2, respectively. We see for h that
49/100
= = A S i i= 2,A = An
52/100
1hh,
?
i i= 1,A = A n
?
i= 2,A n
and for h that
51/100
i= 1,A AnS
48/100
= 2 A n
U(K' i, A)
i= 1, A ns
?
= 2, = A n
Consider ignoring the performance of classifiers in A and using surrogate for the multi-group objective
max ((,,i,,nA))
(E()
In this case, we would choose h has the better of the two hypotheses.
Suppose now that Ans, and AnSS, have mass under both Dj and D2. and that [(h, 1, (() 1(h', 1, A n S1) = 3/10. 10. Finally, suppose that ((h, 2, A n S2) = I(h', 2, A ( = 2/10. Then under the true multi-group objective, by decomposing the group losses, one can compute that h has lower worst case eтror over groups D1 and D2
Thus, to utilize the disagreement region in multi-grou group algorithms, we will need to at least label some samples on A(H') as H'' shrinks. The specification such a strategy is the content of the next section.
5
General Agnostic Multi-Group Learning
5.1 An Agnostic Algorithm
The basic idea in Algorithm|] D similar to classical DBAL approaches for single distribution. We start with the full hypothesis class H. and look iteratively eliminate hypotheses from contention as we learn about how to classify on each group through targeted labeling.
Our solution the problem posed DBAL above is to keep track of the errors of well-performing hypotheses on the complement of the disagreement region in a way that exploits the agreement property. To do this, we construct two-part estimate for the loss of a hypothesis on a given group. Denote the set of hypotheses still in contention at iteration i is H.. Let R; = A ((H.) and SR., be labeled sample from U (R,) and SR..g be a labeled sample from U UR.). We can now estimate the loss for some h E H, on group g via
LS.R. (h g) == (I E R.) Lsn, (h) + PPD (a E R,) LSgq (hH.).
5

---

Algorithm General Agnostic Algorithm
1: procedure WULTI_GRODE CAADUPPPAANNSTICHH.ccbb (0)
2:
H1 f H. I - [log(1/e)]
3: for i [4] do
4:
R; f ((H))
5:
m, <- max Pr, (x A(H.))
6:
for g E [G] do
7:
SRa.9 f 1024
(2d + In(8G)logg(/ee)00) ii.d. samples from Ug (R.)
8:
9:
RR;
128 (28
(<21-1)
i..d. samples from (g(R))
10:
"None" E RR.. then
P PD, (x E R₂) = in this case
11:
SR..9 + 0
12:
else
13:
Sn.99 + (g))) x (n..g)
14:
end
15:
if "Noee" E Rg then
SR +
17:
else
S1Ç,9 + (xI,0g(T)) x sg
end if
20:
end for
21:
h arg min [max (h)
22:
H4+11 + E Hi
SiR, (h) S LS.R, (h.) + +
max
23:
end for
24:
return h = arg min
S, (h)
25:
end procedure
where Ls(h) = 1/18/ E [1(x) o yl is standard empirical loss estimate T and hu, is an arbitrarily chosen hypothesis from Hi that is used in the loss estimate of every h E H. This leads to an unbiased estimator given that every Hi labels the sample from this part of space exactly the same way.
The utility of this estimator that by choosing an arbitrary representative hx,, we can estimate the loss of all hypotheses still in contention precision O(c) on R with Ó(1/²) samples, removing the usual dependence of the VC-dimension. On the other hand, as the disagreement region shrinks, Pn E R₂) shrinks as well, so while we will still need to invoke uniform convergence to get reliable loss estimates in R, the precision to which we need to estimate losses in this part of space decreases with every iteration, and eventually the overall dependence on the VC-dimension is diminished. This
later observation is the standard source of gains in DBAL [8 9 24].
After forming these loss estimates on each group, we construct unbiased loss estimates for the worst case over groups via
L
max S:Rt, (h) := max Ls.R, (h g).
gEG
These loss estimates inherit concentration properties from the two-part estimator above. We draw enough samples each iteration i such that we essentially learn the multi-group problem to precision 2 Tog(1/e)]_1<.
We note that Algorithm I assumes access to the underlying group marginals measures PD This is common in the active learning literature [T8 20 Probabilities of events in instance space can be estimated to arbitrary accuracy using only unlabeled data, so this assumption is not dangerous to our goal of lowering label complexities.
'taken to be arbitrary constant if S = 0: see the Appendix for details.

---

5.2 Guarantees
Vitally, the scheme given in Algorithm 1 is consistent. is lemma of ours that the number of samples drawn at each iteration is sufficiently large that the true error of any h Hi41 is no more than 2 [og((//))='e. Thus, after [log(1/e)] iterations, the ERM hypothesis on L S.R. (-) is then e-optimal with high probability.
We can bound the label complexity of the algorithm using standard techniques from DBAL. A ubiquitous quantity in the analysis of disagreeement-based schemes is that of the "disagreement coefficient" [9] [5]] The general idea that the disagreement coefficient bounds the rate of decrease in of the measure of the the disagreement region of a ball of radius around ht in the pseudo-metric Pg (h, R() == PD, (h(x)) o h (.))). Precisely, we use the following definition of the disagreement
coefficient in our analysis TO, 24
given a group Dy. the disagreement coefficient on g is
FD. (or ((,)
0g = sup sup hEH r'2te
r
where (b, (1),,')== (N' e H: (, M) S 3 is ball of radius r' about h in pseudo-metric Pg. We further notate the maximum disagreement coefficient over the groups G as 0g == max, Pg.
The disagreement coefficient is trivially bounded above by 1/c, but can be bounded independently of in many cases [10 25). For example, when is the class of linear separators in d dimensions and the underlying marginal distribution is uniform over the Euclidean unit sphere, the disagreement coefficient is O d) [9]
Theorem 1. For all e > 0, 8 E (0, 1), collections of groups G, and hypothesis classes H with d < co. with probability 2 1 8, the output h of Algorithm 1 satisfies
T. (h) S I.g
max (h²) + t,,
and its label complexity is bounded by
2 +1 (d)(ddoo(//))) log((/8)) log(1/e) G Glog(1/0) log(1/1/)))/// (l/( ò G
Here, the Ô notation hides factors of (og()og(1/e)) and log(G); we leave all proofs for the Appendix. Theorem 1 tell us that Algorithm eejooy the following upside over passive and collaborative learning approaches: the dependence on the standard interaction of the VC-dimension d and 1/e² is removed, and replaced with Gdo log" (1/e))) / which in settings with small disagreement coefficients and low noise rates, will be significant for small
5.3 Comparison to Lower Bounds in Collaborative Learning
We compare our label complexity guarantees to results in collaborative learning, where the learner has the power to ask for samples from specific group distributions, but not selectively label these samples. This is a strictly more demanding comparison than to pure passive settings, but fair one, given that active learners have the option of executing any collaborative learning strategy. In collaborative learning, for finite hypothesis classes H. it is known that
() 2
+ G Glog(min((H),, G))))
Ω
2²
total labels over all groups are necessary (3]. We consider comparing this lower bound to a simplified version of the label complexity guarantee in Theorem I
δ dGO' log (1/e) + Glog(1/6))
e²
thus implicitly assuming v is neglectably small, and making all comparisons up to factors logarithmic in G. 1/8 and log(1/<). This former assumption is standard assumption under which we may hope an agnostic active learner to succeed [15].
7

---

Algorithm 2 Group Realizable Algorithm
procedure GROUP_ REEPLRRRRREEEELLLLLL c, 6, active learner A, (0
for g E [G] do
hg - A(H, 6 (2),),
S - 144/c (2d/n(24/c) + (1(8//)) samples from oracle (2)
S, { (a, (x)())
5
end for
return h arg se max |š,1 [i.eES 1 [h(x) + 5)
end procedure
Even the simplified upper bound does not admit the cleanest comparison this lower bound, due to our excess factor of log(1/e) in the second term. However, it does showcase that while we pay slightly more per group than necessary. under conditions amenable to active learning, we pay significantly less per dimension d. Particularly for small e, one can see that's approximately sufficient that G (Lo(((())))
for the simplified upper bound beat the lower bound.
For more fine-gr line-grained comparison that in some sense underestimates the power of Algorithm assume that the following condition governs the relationship of G, d, and
G Glog(1/e) S d < (Oge² log (1/e))
Then the simplified bound is smaller order than the lower bound above.
6 Group Realizable Learning
A special case of the learning problem, where extreme active learning gains can be readily seen, comes when the hypothesis class achieves zero noise rate on each group Dg. This setting has been considered in the passive "multi- group learning" literature [6]. Formally speaking, in the group realizable setting, the following condition holds:
Vg E [G], BhG E H.s. lg)
Le. for all groups in the collection G, there is some hypothesis achieving error on that group. Note that this differs from the fully realizable setting where there is some ht H with L (h") O. While fully realizable implies group realizable, the converse is not true. Thus, group realizability represents intermediate regime between the realizable setting and the full agnostic settings.
6.1 Algorithm
In the group realizable case, it possible show a reduction of the problem of active learning over hypothesis classes with respect to single distribution.
This be accomplished as follows. For each Dg. call subroutine active learner that guaranteed to find an order e-optimal hypothesis h with high probability over it's queries. then gathers new unlabeled samples from each Dg. and instead of requesting labels from Oy(+),
labels each unlabeled point with iz. The final step is to do an empirical risk minimization on these artificially labeled samples with respect to the multi molti-group objective. See Algorithm 2 for formal specification of the strategy.
6.2
Guarantees
The strategy given in Algorithm 2 leads to a consistent active learning scheme, provided the active leamnrrs called as subroutines have standard guarantees that can be inherited.
Theorem 2 gives guarantee to this end. The proof follows from an argument similar to one used in
10 because the subroutine calls return hypotheses with near error on each group, the artificially
labeled training set used in the ERM step looks nearly identical to a counterfactual training set for the
FRM step constructed by querying labels (z(x) for each unlabeled æ. This is similar to the idea in
24
We present Theorem 2 assuming access to classical, realizable active learner due to (26).

---

Theorem 2. Suppose Algoritium2 is is run with the active learner ACAL of [26]. Then for all >> 0, 8 E (0, 1), hypothesis classes H. with d < oo, and collections of groups with the group realizability property under H. with probability 2 11- 6, the output h satisfies
Lg max (h) - Lgg max (h²) t
and the number of labels requested
ò dGDg log(Le))
(dGGo
Thus, when disagreement coefficients across the collection of groups are bounded independently of c, the usual, passive dependence 1/ 2 is replaced by log(1/e).
In the passive multi group setting of 77]. it has been shown that Ô for group realizable learning, where we recall 7/ a lower bound on the probability of getting sample in each group [6]
samples are sufficient
7 Full Agnostic Approximation
7.1 Inconsistency of the Reduction in the Full Agnostic Regime
Agorrthmmaadmin clean analysis, and nicely harnesses the power realizable active learners for single distribution. One might wonder if a similar strategy might provide consistent strategy in full agnostic regime. Unfortunately, the direct application of Algorithm ( using agnostic learners does not yield consistent active learning algorithm. In fact, consistency fails even when for each E (G). hn is the Bayes optimal classifier on Dy. and Vg == infReH (g(h g) is small. This lack of consistency comes down the fact that labeling with the Bayes optimal underestimates noise rates on each group, which in turn may bias the output of the ERM step.
7.2 A 3r-Appprxximation Algorithm
Although the strategy of creating an artificially labeled training set with near- cear-optimal hypotheses on each group fails outside of the group realizable case, it possesses nice approximation property.
We give a guarantee to this end Theorem It states that if we call an active learner with agnostic guarantees on each group D,, and then use the outputs iε to artificially label a new batch of unlabeled data from each group, using ERM on this artificially labeled data gives at worst a 2v + e-optimal hypothesis with high probability.
Theorem 3. Suppose Algorithm is run with the agnostic active learner ADHM of [TS]. Then for
all > 0, 8 E (0, 1). hypothesis classes H with d < 0o, and collections of groups G, with probability > 1 - 8, the output h satisfies
T.gax (h) T.gax + 2- max Vg + 5. 1. (h²) +
gEIG.
and the number of labels requested is
δ dG0g log (1/c) 22 22)) )
The proof is very similar to that of Theorem but notes addition that h mislabels on a roughly "g ug-fraction of the unlabeled samples from each group G. This allows to upper bound the distortion of the ERM step.
Conclusion
In this work, we have taken a first look at active multi-group learning. Though the design of general agnostic strategies in this setting is quite challenging, an interesting future direction may be the search for strategies that work in more specific cases, for exampling extending our work in the group realizable setting. In particular, the search for algorithms with small label complexities under specific low-noise conditions, such as Tsybakov noise each Dg. may prove fruitful 27

---

References
[1] Avrim Blum, Nika Haghtalab, Ariel D Procaccia, and Mingda Qiao. Collaborative pac learning. In Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[2] Huy L. Nguyen and Lydia Zakynthinou. Improved algorithms for collaborative pac learning, 2018.
[3] Nika Haghtalab, Michael I. Jordan, and Eric Zhao. On-demand sampling: Learning optimally from multiple distributions, 2023.
[4] Jacob Abernethy, Pranjal Awasthi, Matthäus Kleindessner, Jamie Morgenstern, Chris Russell, and Jie Zhang. Active sampling for min-max faimesss, 2022.
[5] Agnieszka Stowik and Léon Bottou. On distributionally robust optimization and data rebalanc- ing. In Proc. AlStats 2022, Feb 2022. to appear.
[6] Christopher Tosh and Daniel Hsu. Simple and near-optimal algorithms for hidden stratification and multi-group learning. CoRR, abs/2112.12181 2021.
[7] Guy N. Rothblum and Gal Yona. Multi-group agnostic PAC learnability, CoRR, abs/2105.00988) 2021.
[8] Luke Oakden Rayner, Jared Dunnmon, Gustavo Carneiro, and Christopher Ré. Hidden stratifi- cation causes clinically meaningful failures in machine learning for medical imaging. CoRR, abs/ 0bss/1909.1244 12475, 2019.
[9] Steve Hanneke. bound on the label complexity of agnostic active learning. In Proceedings of the 24th International Conference Machine Learning, page 353-360, 2007.
[10] Sanjoy Dasgupta, Daniel Hsu, and Claire Monteleoni. A general agnostic active learning algo- rithm. In Proceedings of the 20th International Conference on Neural Information Processing Systems, 2007.
[11] Weihua Hu, Gang Niu, Issei Sato, and Masashi Sugiyama. Does distributionally robust super- vised learning give robust classifiers?, 2018.
[12] Yonatan Oren, Shiori Sagawa, Tatsunori B. Hashimoto, and Percy Liang. language modeling. 2019.
Distributionally robust
[13] Shiori Sagawa, Pang Wei Koh, Tatsunori B. Hashimoto, and Percy Liang. Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generalization. CoRR, abs//911.08773 2019.
[14] Burr Settles. Active learning literature survey. 2009.
[15] Sanjoy Dasgupta. Two faces of active learning. Theoretical Computer Science, 41261 1781,201 2011.
[16] Steve Hanneke and Liu Yang. Minimax analysis of active learning. 2014.
[17] Maria-Florina Balcan and Ruth Umnr. Active learning- modern learning theory., 2016.
[18] Maria-Florina Balcan, Alina Beygelzimer, and John Langford. Agnostic active learning. In
Proceedings of the 23rd International Conference on Machine Learning, page 65-72, 2006.
[19] Rui M Castro and Robert D Nowak. Minimax bounds for active learning. IEEE Transactions on Information Theory, 54(5):2339-2) 2353, 2008.
[20] Stanislav Minsker. Plug-in approach to active learning. Journal of Machine Learning Research,
13(1), 2012.
[21] Chicheng Zhang and Kamalika Chaudhuri. Beyond disagreement-based agnostic active learning. CoRR, 407.2657, 2014.
[22] Alina Beygelzimer, Sanjoy Dasgupta, and John Langford. Importance weighted active learning. CoRR, abs/0812.44952, 2008
[23] Steve Hanneke and Liu Yang. Negative results for active learning with convex losses. Journal of Machine Learning Research Proceedings Track, 9:321-325, 01 2010.
[24] Chicheng Zhang and Kamalika Chaudhuri. Active learning from weak and strong labelers. CoRR, abs/1510.02847, 2015.
10

---

[25] Steve Hanneke. Theory of active learning. 2014.
[26] David A. Cohn, Les E. Atlas, and Richard E. Ladner. Improving generalization with active learning. Machine Learning, 15:201-221, 1994.
[27]
Jean-Yves Audibert and Alexandre B Tsybakov. Fast learning rates for plug-in classifiers under the margin condition. arXiv preprint math/0507180, 2005.
[28] Vladimir Vapnik. Statistical Learning Theory. Wiley, 1998.
[29] Wassily Hoeffding. Probability Inqqualities for sums of Bounded Random Variables. Springer New York, 1994.

---

9 Appendix
9.1 Guarantees for General Agnostic Algorithm
In this section, we give proofs for the guarantees of Algorithm 1. We begin with some definitions, starting with how empirical loss estimates are made.
Definition 1. Given a hypothesis h E H. and set of pairs { vi) :4 M D let
N
Ls(h): = N
Σ
1[((z)) # vil
the standard empirical loss of h on S. Let La 1
The convention to let (h) = 1 allows us to "collapse" the two-part loss estimates in the case the probability of drawing
unlabeled sample in specific region is O; under the specification of the algorithm, S = 9 if and only if the probability of sample falling in the disagreement region or its complement is 0 under Da- in which case we safely ignore estimation one of these regions.
Definition 2. Given set of classifiers H' C H. we say "H' agrees a subset S C X² for each x E and for each pair (h,h) E H' H', it holds that h(x) = (z)).
We now recall the two-part estimator for the loss of a hypothesis introduced above.
Definition 3. Fix group distribution Dg. some H' C H. hypothesis h E H'' and some R S X which is measurable with respect to each marginal of Dg and for which H' agrees on R Given sets of pairs SR.g and SR= g, and some arbitrarily chosen classifier bw E H², let
Ls ( = I (x R) LLa. (h) + PD, E R²) Lssss, (hze).
As mentioned in the main body, hx must be used in the estimate of the loss under Dg in the "agreement region" for all h H. The extent to which this estimator is useful can be captured by standard uniform convergence arguments. To this end, we first introduce a function that will prove to control its deviations nicely.
Definition 4. Given confidence parameter 5 E (0, 1), group distribution Dg G, some R X that is measurable with respect to each marginal Dg E 9, and sample sizes m, m > O, define the function
PD, (x R) m
(n(8/8) In (2em/ /d)
In(4/8) 2m
if PD R) O.P,D R9)
In(8/6) + In
(5 R, R,m.m') =
+
if FD, R) 0.P.,
1, (x E Rd) =0
In(4/8)
2m
if
0.
Lemma 1. Fix 8 E (0, 1), set of group distributions G, and a group distribution Dg E G arbitrarily. Further, fix subset R C X measurable with respect to each marginal of D, E G. and set of classifiers H' C with the property that agree on Rs. Suppose we query m. > unlabeled samples from UR).) and mć > O samples from Ug( (RE,)) Suppose further that we label the oulpul via calls to Og(.), forming the labeled samples SR.g and Sge g respectively; if either PD, (x E R)) = or PDD (x R.), then we set the corresponding sample be G. Then with probability holds for all h E H' that
Lg 9) - Ls.n(h 9)1 1 R.,,
Further, for all > 0, if m > I (6, R, m, m') 7.
16(P (#ER))²
(2d1n(8/7)) + In(8/8)) and m' > 2ln(4/6) then
12

---

Proof. We begin with the case where both PD, (x R) # 0 and PD, (x E Rd) & 0. In this case, we are able to draw unlabeled samples from both regions, and neither Sn.g nor Sn.9 is 0.
By lemma of Vapnik (28), we have that with probability 1-2/22 over the draw of m samples from (R) and their labeling via O,(+), that simultaneously for each / E H²'
Im(8/d) + d In In(2em/d)
LSR.. (h) D2 (h(z)= + y| x R)
m
m
In R all E Ht' agree, and so estimating the conditional loss for each h E Ht' in this region is as statistically hard as estimating single Bernoulli parameter, which we do by arbitrarily choosing classifier to use for the loss estimate in this part of space. Thus, by definition of the two-part estimator and Hoeffiding's inequality [29],
we have with probability 2 1 2--0 8/22 for all E H' simultaneously
In(4/6)
T. (lwr) PD, (h(x)= + yl x E R*)
S
2m'
By union bound, with probability 2 1 - 5, both of these events take place, and so for all h E H' simultaneously,
(g () = - (l((z) # y a R) PD, E
+ +PD, (h(x) $y x E R*) PD, (a R$)
< (LeRn (h) + 1/m+ (1m(8/0) + dIn(2em/d)) /m) FD, (+ E R)
+ [Ls (fre) + / // lm(44/)/22m) FD, (z E R*)
< Ls (g) +1+ (1 R, m, m').
The lower bound leading to the absolute value is analogous. Vapnik (28] also tells us that for any 7' > 0, sample of size m 2 a (2dIn(4/n)) + 1n(8/6) is sufficient to yield
1/m + (1n(8/)) + d dlI((mm/d)) /mm <n'
Let Let 7/2PP, (x E R). Thus, substituting for o and bounding the probability inside the natural log above by 1,
16
m ž PD, (x E R)² (nd/n()/)) + In(8/))
implies that
1
In(8/0) d (lne2mmdd)
7 2P D1, (a R)
m
m
As a corollary to Hoeffding, if m' 2 2l1(4/0)/72 then v log(4/0) 4/0)/2ml < 7/2. Thus, we may write
1 = In(8/8) + dln(2emm/d) I PD, (I R)
In (4/55) 2mn
< 7.
m
Now suppose that PD, (xx E Rº) 0. In this case, we have SRe. 0. Again, we have that with probability 8/2,
1 + <
In(8/0) In (n(2em/d)
Lsn. (h) IDD (1(x) + yl x R)
m
m
When ID,, (xr E R = 0. it holds that PD, (r E Rt) 1, and so
(h g) = PD, (h(x) + y x E R) PP
- PP, (h(x) # #y v R²) (x
PD, (h(x) + y
R)
< Lsnn (h) + 1/ m + (In((88) + d (n(2mm/d)) /
= Ls g) + T , (6, R, m'),
13

---

where the final equality comes from fact that FD, (2 E Rd) = 0 and PD, (z E R) = 1, as well as the definitions of Rs I g) and I 9 R, m, m,mmm, m'). Similarly to the above, if we let
y = 7/2/1P D2 R) 7/2, then
16 m Z
+ (1008///)+118/)00)
7
implies that
1 + In (n(8/0) (2lm/22mm// T 2
m
which by the definition of 96 R. m. m') when PD, (a E R = gives us r R. m, m') < 7/2 <. The case where PD, (ar E R) = O follows the previous argument for when D, (a E Rd) = 0.
Definition 5. Given a collection of group distributions G. some 't' C H, a hypothesis h E H', some subset R C X measurable with respect to each marginal of Dg 9, and labeled samples Sn, and Ste we define the empirical estimate of the multi-grrop loss of h parameterized by R via
L
max S:R (h) == max Ls g).
gE[G]
Having recalled the way in which we form empirical estimates for the group worst-case loss of given hypothesis, we can show a simple concentration lemma for this group worst-case loss estimator using the concentration property for individual groups proved in Lemma
Lemma 2. Fix (0, 1), a set of group distributions G, subset S X measurable with respect to each marginal of Dg G. and a set of classifiers Ht' C H that agree on R. Suppose for each g [G.. we query mg > unlabeled samples from (R), (R), and m²g > samples from (g(RR) Suppose further that we label the outputs via calls to Og(+). forming the labeled samples St.g and SRe.g . respectively, for euch E [G]; P (x E R) 0 or Pry (x E RF) = 0, then we set the corresponding sample to be 9. Then with probability 2 1 - 8, it holds for all h E H! that
| - (. < max I (6/G, m. mly)) g
Proof. By Lemma and union bound, it holds with probability 2 5 that all Dg, for all E H' simultaneously, that
LLgh g) - Ls. g)1 S (5/G. mg my).
Thus we may write
L max (h) L (h)
= max Lg(h g max Ls.R(h 1)) 9'E[G]
J'E[G]
max d'E(G]
Tag g') - -.s.((h g
max
g (5/G, my', my
g'E[G]
We now use Lemma 2 to show that Algorithm is conservative enough that the optimal hypothesis h never eliminated from contention throughout the run of the algorithm with high probability.
Lemma 3. Fix 8 (0, 1), a collection of group distributions G. and hypothesis class H. with d < so arbitrarily. With probability 2 1- 8, it holds after each iteration of Algoritium 7 that h H4+1.
Proof. By Lemmas T and 2 and a union bound over iterations, the number of samples labeled at each iteration is sufficient for us conclude that with probability - 6, for for every iteration i
14

---

and for each h E H4, it holds tha
S. (h) - (h)) - 2 e/8.
We give an inductive argument conditioned on this high probability event. When i = we have h" E Hi because H1 = H. and h' E HH by definition. If ht E H4 for i 2 1, then h" E M441 if and only if
I max R.
(h") S T. max
S; R. (h+) + 2! e//4.
When for each h E Hi, it holds that T. 1aax
S.R. (h) g. (1)) S 22 t//8, we may write
max (h") L max (h+) - L max (h") LG Imax (h") + LG Lgax (hi) L max (hs) Lgg (1axx(1)1| (h*)² + Lgxx((h)) - S. (hi)
1 max (h")
< 2' //8 + 22' 2e-88
2 e/4,
where the first inequality comes from the optimality of ht. Thus, we must have h E Hi+1-
Now, using the fact that the optimal hypothesis stays in contention throughout the run of the algorithm, we can give a guarantee on the true error of each hypothesis h E Hi-1. The idea is that using concentration and the small empirical error of each h E H4+1, we can say that the true errors of each E Hi+1 are similar to the true errors of the ERM hypothesis hús and then use the true error of h, as a reference point to which we can compare the true error of h E Hi++ and h"
Lemma 4. Fix d (0, 1). a collection of group distributions G. and hypothesis class H. with d < oo arbitrarily. Then with probability 2 1 6, after every iteration i of Algorithm ! it holds for all h H441 that
LB maxx (h) Lg max (h*)l s 2/-
Proof. If h E Hit1, then by the specification of the algorithm, it holds that
L max (h) L (h,) S 2/4
Because h, is the ERM hypothesis at iteration i, it holds that L L (h.) Lmax (h) 50 < 2e/4 and thus we may conclude
I. S.R. (h) I. S. (hs) s 2 i/4
By Lemma 2 and the number of samples labeled each iteration, with probability 2 21 5, it holds for all iterations and for all h E Hi that LSSR (h) - (h)) S 2'-8
Conditioned on this event, if h Hi+1, I, we have
1/ (h) T.g (h.))
1.g m.max (h) S,R, (h)
S. (h)
T.max R. (h.)
S.R. (fr.) -.g. (hi))
< Lg (h) max (f)) S.R. (h) Lmax (ha) + L.S. (ha) - L max (hi)
$ 2 - e/88+ + 2 - '/44 22 -22-1//3 c//8
2' E//2.
By Lemma 3 it holds that ht E H4-1 whenever | (h) (h)x S 2' for all h E Hi at
all iterations. Thus, this bound on the true error difference with the ERM h, applies to ht,, and we may write for arbitrary h H4+1 that
| (h) - LZ (h*) < LE max (h) L (hx) + 1g (ha)
LG max (h*) Lh)xx(h)) S 22"='e.
which is the desired result.
We do not directly apply Lemma with 7 = 22' 2///-//////// /8 here. We this quantity in the outer dependence on y of Lemma 1, but for the natural log dependence on y. we sub e/8 to simplify the analysis. Thus we take slightly more samples than Lemma I directly suggests. Because we take the largest probability of the disagreement region over groups as m. it holds that m. is at the smallest the sample size suggested by Lemma I for each g.
15

---

Definition 6. Given group distribution Dg E G, hypothesis h E H, and radius r 2 0, let the "Dg disagreement ball in 'H. of radius about h" be
ry( (N E H: (h sr)
where Pg Pg(h,h') := (h(x)) + (x)))
Definition 7. Given a group distribution Dg and a hypothesis class H. let the "disagreement coefficient" of y be defined as
PD, (x E ((,,
0g = sup sup heHr r22rte
We further define the disagreement coefficient over a collection of group distributions 9 as
0g
max 0g'
g'E[G]
Given these definitions, we are now ready to state the main theorem. The consistency comes from what showed in Lemma the error for each h E H4+1 decreases with each iteration, after enough iterations we will have each h E H441 having e-optimality.
The label complexity bound follows standard ideas in the DBAL literature; for example [ 24 Essentially, what we do is show that at each iteration i, because the true error any h E Hi on the multi-group objective can't be too large, the disagreement of h and h* any single group cannot be too large. This leads to bound on the size of the disagreement region for each g.
Theorem 1. For all > 0, E 1), collections of group distributions g, and hypothesis classes H. with d < oc, with probability 2 1 - 6, the output of Algorithm satisfies
Lg Lmax (h) S L33 (h") tc.
and label complexity is bounded by
o o( C og
v2 +1
(dlog(1/e) +1)
log(1/6)) log(1/e) + G Glog(1/e) log(1/0)
Proof. Lemma 4 says that the number of samples drawn at each iteration is sufficiently large that with probability 2 8. for all [4]. holds that for all h H4+1, that we have L (h) - L (h*)] < 2/-ie. Thus, after I [log(1/e)] iterations, the output h satisfies the consistency condition.
To see the label complexity, which the sum of the number of labels we query at each iteration, we note at iteration i, we label no more than
mi 2
64 2d log (
+ In (GG(logLL/e1) +
128 In (LG))))()/e))))
1024
samples for each group distribution Dg. where m, maxy PD, (x E A(H.)). The only term here that depends
that Lguxx (h) - Lg (h*) T. By Lemma 4 with probability 1 8, it holds for each 1 [log (1/c)]. [log(1/c)].
is
21-itle; this holds automatically at 1 by the setting of
Thus, arbitrary i and for arbitrary g E [G], may write
Pg(h,h") PD, (M(x)) hx)))
PD, (h(z) y, (x)= -
< PDD, (h(x) z + (h)
= Lig(h (h ()) + [h(h g)
Lg (h) + Lg max (h²)
Linax (h) L max
(h') ) + L max (1 + L max (
< 2/-1 2v,
16

---

where we recall // is the noise rate on the multi-group group objective. Thus, with probability 2 1 - 5, for each I and g E [G], holds that
H4 S B 2 2 ++ 22).
Given this observation, we may then write, for all g, that
FD, (z E A(H)) & PD, (r E A(By 2v + 2 2l
as if there are h, h E Hi that disagree on some x, we have h, h E By(h", 2v + 2 c). and so h, h also realize disagreement on for the larger set of classifiers. Recalling the definition of mi, this allows us to bound the sum of terms depending on i for each distribution Dg as
maxx PD2 (x E A (h" 2v + 2 22
m4 2
2/-²c
PD, (x E (B (h" 2v + 21-1-11)) E))) 2v + 22 27-i-1
2
max
2v + 2/-i+1e
21-
1=1
2
PD, (x (BB (h", 2v + 22-=++()))
2
4
max g'
2v + 1itite
2
PD, (x A (h,r)) 2
S
max sup sup lie +22044
2
4 [[og(11/))]
max Og o'
1/ V+
=[log(1/ee]
0g.
The label complexity bound then follows by noting the algorithm labels the same amount of samples for groups each iteration, and ignoring the factors of log(G') and log(log(1/e)).
9.2 Group-Realizable Guarantees
Theorem 2. Suppose Algorithm is run with the active learner ACAL of (26). Then for all >> O, 8 E (0, 1), hypothesis classes H with d < cc, and collections of group distributions that are group realizable with respect H. with probability -, ô, the output h satisfies
Lg (h) < LB
1 (h²) + t,,
and the number of labels requested is
ò ddce lo(le))
Proof. The label complexity follows directly from the guarantees given [5)] By a union bound, we with probability 2 1 6, have that for all g E [G]. that ACAL returns h, with the property that
Lg (h, g) s c/6.
Fix some E [G] arbitrarily. Consider a counterfactual training set Sy, unseen by the learner, constructed by labeling each example Sy via the oracle call (x(x). Then Vapnik (2 tells us that my : | sufficiently large that with probability 1- 8//2, for each H simultaneously, we have
[ 9) Ls, (h)l < e/6.
17

---

Again by the union bound, this uniform convergence on So and the guarantee on the runs of ACaL both hold for each [G]. Conditioned on this high probability event, we can first note that for some arbitrary h E H.
mg
Ls, (h) Ls, (hi)
[h(x;) + yvl 1[(x,,) + hy (2;))]
mg
[[h(at) + ml [(((ar) + (xiil
mg
m2
1ly * hg(x:))
mg
Ls, (hy)
< Lg(h +
c/6 c/6
e/3,
where the second to last inequality comes from the uniform convergence over Sg. and the final inequality comes from the success the runs of ACAL. Then for arbitrary h, combining Vapnik's guarantee and the inequality we just showed, we may write:
[. g) I.s, (h)
[i 9) Ls, (h) + [s, L (h))
W Lo(h [9) - L,, (h)l + Ls,(h) - Lg, (hi)
e/6 e/3 c/2.
Given this guarantee on the representativennss of the artificially labeled samples on each group g. have a guarantee for the representativeness over the worst case. For arbitrarily h E H. we may write
L Lmax(1 (h)
max Ls, (h) sE(G]
max Lo(h g) max Lg (h) [
sE[G]
S max gE[G]
Lg(h g) Ls, (h)
- e/2.
Thus, by the fact that i is the ERM on the artificially labeled dataset, we have
T.g .max (h)
max T.g, (f) + e/2 < max T.s, (h²) + c/2 s r. r.aax(h") +
ge G|
gE(G)
9.3 Approximation Guarantees
Theorem 3. Suppose Algorithm 3 is run with the active learner ADHM of [15]. Then for all 0,
E (0, 1), hypothesis classes H with < oc, and collections of groups D, with probability 2
the output h satisfies
L max (h) < L max (1²) + 2 max Mg + + 3 3. I,xx((h)) +
gE(G)
and the number of labels requested is
+ u²) +z ) ó dGBg log" [1/g(
18

---

Proof. The proof is almost identical to that of Theorem 2 The label complexity bound follows directly from [TO]. Similar to before, we have that for all g E [G], ADHM returns hy with the property that
Lg ( = Lo g) c
Fix some g E [G] arbitrarily. On counterfactual training set Sg. unseen by the learner, constructed by labeling each example E Syg via the oracle call Og (z), holds that my == |S/ is sufficiently large that with probability 2 6/2, for each h E simultaneously, we have
[Lg( g) L.s, (1)) < <</6.
By the union bound, this uniform convergence and the guarantee on the runs of ADHM both hold. Thus, we can first note that for some arbitrary h E H.
mg
T.s (h) - 1.g, (1))
[[(x)) + vd (M(ass + (x:i)
=
mg
[[(()))) + vd (1((as)) + (x:)]
1s: # hg(x:)]
mg
Lg (hg (g) + e/6
Lg lg) + e/3
V9 + c/3.
where the second to last incquality comes from uniform convergence over Sc, and the final equality comes from the correctness guarantee of ADнM- Then for arbitrary h, combining Vapnik's guarantee and the inequality we just showed, may write:
Lg(h 1)) Ls, (h)
Lg(h 9) Ls, (h) + Ls, (h) Lg, (1)
< Lg(h 9) (ss(()) Lss (1) Ls, (1i)
< c/6 + V/ + e/3
= Vg + e/2.
Then, as above, we have, for arbitrarily H,
m.aax (h)
max L, (h)
[ggh g) Tig, sE[G]
max
(1)
max V/ +c/2 gE(G]
gE(G]
where the the final inequality comes from the fact that if any hypothesis has less than 1/9 error all groups, would be optimal on group g. Thus, by the fact that h is the ERM on the artificially labeled dataset, we have
sE[G] ( I max Lg, (h)+ < max Lg, (h²) (h") +e/2 S (h") S 53- (h"++
gE(G
19


Reviews:
[{"review_id": "yzoV0D6tvK", "reviewer": "Reviewer_eXQR", "summary": "This paper studies multi-group learning from the active learning perspective. The authors first discuss why classical disagreement-based active learning methods cannot work and provide an example. Then, they propose a modified algorithm and provide theoretical guarantees. The label complexity bound is smaller in order than the lower bound in collaborative learning under certain condition. For the special case of group realizable setting, they also establish improved theoretical results.", "questions": "1. How about uncertainty-based methods? What if the learner just label the sample from the most uncertain group?\n2. Is the proposed algorithm computationally efficient? Are there any insights for the computational complexity?", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper is well-written and easy to follow.\n2. This paper clearly states why the classical disagreement-based active learning methods cannot work in the multi-group learning setting. The example in Section 4.2 is interesting.\n3. The authors compare their label complexity bound with the lower bound in collaborative learning setting and show that their bound is smaller in order under certain condition.\n4. Improved theoretical results are achieved for the group realizable setting.", "weaknesses": "1. This paper only discusses the drawback of disagreement-based methods in multi-group learning. How about uncertainty-based methods? What if the learner just label the sample from the most uncertain group?\n2. From line 22 in algorithm 1, the proposed method is computationally inefficient and cannot be implemented in practice.\n\nMinor:\nThe caption of table 1 states that $\\widetilde{\\mathcal{O}}$ hides $\\log(1/\\epsilon)$, it should be $\\log(\\log(1/\\epsilon))$?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the review and the comments. \n\n> How about uncertainty-based methods? What if the learner just labels the sample from the most uncertain group?\n\nIn general, one must be careful with uncertainty based approaches in the agnostic AL setting as they can easily lead to inconsistent strategies (the issue of consistency of active learning strategies is described concisely in [11]). \n\nFurther, not discriminating the labeling beyond the group-level will not yield better guarantees than the lower bounds of [1], as this is the sampling regime of so-called 'collaborative learning'. The issue with directly combining ideas in collaborative learning[1] with those given in our algorithm is that upper bounds in this literature are on an expected error rate over a draw from a distribution over the hypothesis class, which is a weaker sort of guarantee that isn’t easy to exploit when one wants to output a deterministic hypothesis.\n\n> From line 22 in algorithm 1, the proposed method is computationally inefficient and cannot be implemented in practice.... Is the proposed algorithm computationally efficient? \n\nAs we mention in the Author Rebuttal, one can always construct an epsilon cover of $\\mathcal{H}$ of near-optimal size using a polynomial number of unlabeled samples [2]. This will yield a finite class on which one can execute the algorithm while still maintaining guarantees. There are some techniques in the literature for making active strategies directly executable on infinite classes [4, 14], but we leave the application of such ideas to our problem for future work.\n\n>Minor: The caption of table 1 states that $\\tilde{O}$ hides $\\log(1/\\epsilon)$,  it should be $\\log(\\log(1/\\epsilon))$?\n\nThe caption in Table 1 is correct, if strangely worded. The $\\tilde{O}$ hides factors of $\\log(\\log(1/\\epsilon))$, i.e. which we write as 'factors logarithmic in $\\log(1/\\epsilon)$'. We will update this.  \n\n&nbsp; \n\n[1] On-Demand Sampling: Learning Optimally from Multiple Distributions. Haghtalab et al., 2022. \\\n[2] A Bound on the Label Complexity of Agnostic Active Learning. Hanneke 2007. \\\n[3] Agnostic Active Learning. Balcan et al., 2006. \\\n[4] A general agnostic active learning algorithm. Dasgupta et al., 2007\n[11] The two faces of active learning. Dasgupta, 2012. \n[14] Agnostic Active Learning Without Constraints, Beygelzimer et al., 2010.\n"}, {"review_id": "r3ghvMx7ci", "reviewer": "Reviewer_rZgu", "summary": "The paper considers an active binary classification setting where the feature space is partitioned into several groups. The performance of the learner is given as their worst case performance across all groups. The effect of considering such a multi-group setting is that, it is no longer efficient to sample exclusively in the disagreement region of said class. The authors propose an algorithm which iteratively eliminates hypothesis from the hypothesis class, while keeping track of the performance of hypothesis outside the disagreement area. The trick they use, is to split the loss of a classifier between the loss on the disagreement region and its complement. The later can be estimated by the loss of an arbitrary hypothesis from all remaining hypothesis. This removes dependence on the VC dimension from the estimation of the second term. They give PAC guarantees for their algorithm with an upper bound on expected sampling time.  \n\nThe authors also consider the problem of group realizable learning. In this setting a perfect classifier is assumed to exist for each group. Here, they propose an algorithm which first runs a sub routine to find an $\\epsilon$ good classifier on each group. They then use said classifiers to label points in each group and finally do ERM with respect to the multi group objective. They provide PAC guarantees for the algorithm with an upper bound on the sampling time. ", "questions": "Have the authors considered a setting where, instead of two oracles, the learner can only receive limited samples from the Rademacher random variable with parameter $\\mathbb{P}_{D_g}(Y=1 | x)$, for an $x$ of there choosing, where the partition of the feature space across the groups is known. In particular this should change the nature of group realizable learning.", "limitations": "The authors could address the lack of lower bounds for the active setting in more detail. Also Theorem 3 is presented in isolation, it would be nice to have some speculation on whether this result is optimal and also to view it in context of previous literature.   ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is well written and easy to read.The motivating example of section 4.2 gives good intuition as to why it is not sufficient to sample on in the disagreement region, which is in itself an interesting phenomenon. The mechanism of algorithm 1 is well described and the reader is given good intuition as to how it's sampling strategy leads to a reduction in VC dimension. ", "weaknesses": "The authors compare the result of theorem 1 to a lower bound from passive learning. It would be of more interest to consider lower bounds in the active setting, even in the form of conjectures. Discussion on the necessity of the $\\log(1/\\epsilon)$ term is also missing. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for a thorough reading of our submission. We try to address some questions/concerns below.\n\n>It would be of more interest to consider lower bounds in the active setting, even in the form of conjectures\n\nWe agree it would be nice to have active lower bounds. In general, tight lower bounds in a disagreement context can’t be expected, in that there is no literature saying that the relics of disagreement based methods are necessary (read: disagreement coefficient). Partially for this reason, it's fairly common in active learning that you see comparisons to passive lower bounds. That said, some lower bound is achievable. \n\n>Have the authors considered a setting where, instead of two oracles, the learner can only receive limited samples from the Rademacher random variable with parameter $\\mathbb{P}_{D_G}(Y= 1|x)$, for an $x$ of there choosing\n\nThe alternate oracle/sampling model suggested by the reviewer seems to be that of  ''membership query'' active learning [5]. There are some interesting results in this field [6], but in general, this query model has gone out of favor in the AL literature, because in practice the algorithms tend to ask for labels of $x$ that are unnaturally close to the decision boundary, e.g. strange mixtures of cat and dog. It might be an interesting problem to consider though, especially in combination with some minor modifications to make queries more realistic (see [7]). \n\n&nbsp; \n\n[5] Queries and Concept Learning, Angluin, 1988. \\\n[6] An Efficient Membership-Query Algorithm for Learning DNF with Respect to the Uniform Distribution, Jackson, 1996. \\\n[7] Learning using Local Membership Queries under Smooth Distributions, Awasthi et al., 2012. \n"}, {"review_id": "ClCQaAB1rk", "reviewer": "Reviewer_7xXY", "summary": "This paper looks at disagreement-based active learning (DBAL) where\nthe goal is to minimize the maximum error over a (known) set of G\ndistributions (\"groups\").  One could learn each group individually,\nbut the optimum for each group may be very bad on other groups.  By\ncombining the search, a decent sample complexity can be obtained.\n", "questions": "Is there any reason to expect the theta^2 or log^2 dependences in Theorem 1/3 to be right?\n\nIs it possible to have experimental evidence that this stuff ever works, even synthetically?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "It's an interesting problem, fairly well motivated and it's clearly\nexplained (Example 1) why standard DBAL won't quite cut it.  You\ndefinitely need to do something clever to handle having multiple\ngroups, and the bound they get is competent.\n\nI enjoyed reading the paper.", "weaknesses": "The main problem with Theorem 1 is that the result has theta^2 where\nstandard DBAL gets theta (here, theta is the disagreement\ncoefficient).  It really seems like theta should be possible here.\n\nIn the easier regime of getting error O(eta) [Theorem 3], the\ndependence is theta as one would expect.  But the bound there is d G\ntheta log^2(1/eps), and it seems like the log^2 should be log(1/eps):\nStandard DBAL only needs log(1/eps).  Something like:\n\n(1) get loss (eta + eps) within each class, using d G theta log\n(1/eps) samples.  This gives hypotheses h_1, ..., h_G such that each\nh_g has error at most (eta + eps) on class g.\n\n(2) output the hypothesis h^ that minimizes max_g Pr_{x ~ g} [ h^ != h_g].\n\nSince the optimum h* has error eta on each class relative to the truth on class g,\nit has error at most (2 eta + eps) relative to h_g\nso h^ has error at most (2 eta + eps) relative to h_g on g\nso h^ has error at most (4 eta + 2 eps) relative to h* on g.\n\nI guess this is a 4 eta approximation, not a 3 eta approximation, but\nthat doesn't seem very significant (also unsure if it's necessary).\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for reading our work with an eye for algorithmic detail.  \n\n> In the easier regime of getting error $O(\\epsilon)$ [Theorem 3], the dependence is theta as one would expect. But the bound there is $d G \\theta \\log^2(1/\\epsilon)$, and it seems like the $\\log^2(1/\\epsilon)$ should be $\\log(1/\\epsilon)$.\n\nThis label complexity is inherited directly from the choice of the 0-1 loss active learner due to [10] that we instantiated to simplify the theorem statement. In accordance with the algorithmic ideas outlined by the reviewer, the label complexity in Theorem 3 is G * ('pick your favorite 0-1 loss agnostic active learners label complexity'), and so by feeding a better active learner to Algorithm 2, you can automatically shave down the dependence on $\\epsilon$ to below $\\log(1/\\epsilon)^2$ without any extra analysis.\n\n> The main problem with Theorem 1 is that the result has $\\theta^2$ where standard DBAL gets theta (here, theta is the disagreement coefficient). It really seems like theta should be possible here.\n\nAs the reviewer points out, the dependence on $\\theta^2$ in Theorem 1 is likely unnecessary.  Our understanding of the history of the agnostic active learning literature is that the first general analysis of agnostic active strategies from Hanneke [2] showed this $\\theta^2$ factor, and that through better concentration bounds and more subtle analysis, the extra $\\theta$ was shown to be unnecessary [8]. Basically, we did not set out to fully optimize the bounds given the algorithmic idea of Algorithm 1, instead opting for a more straightforward analysis to show the algorithmic idea is viable. \n\nWe will take a closer look to see if we can improve the bounds. This usually comes from using concentration inequalities that take into account the variance of the estimator, as in Section 5 of [15].\n\n&nbsp; \n\n[2] A Bound on the Label Complexity of Agnostic Active Learning. Hanneke, 2007. \\\n[8] Theory of Active Learning. Hanneke, 2014. \\\n[9] Agnostic Active Learning Without Constraints. Beygelzimer et al., 2010. \\\n[10] A general agnostic active learning algorithm. Dasgupta et al., 2007. ' \\\n[15] Theory of Classification: A Survey of Some Recent Advances. Boucheron, 2005. \n"}, {"review_id": "VRK1Xy9bfU", "reviewer": "Reviewer_T3gQ", "summary": "This paper studies active learning in a multi-group setting, in which the learner performs adaptive sampling over groups of distributions for solving a binary classification task. The performance of the learner is measured by its maximal loss over the groups. The main goal is to extend the disagreement-based active learning approaches to the multi-group setting. To achieve this, the paper proposes a novel worst-case (over groups) loss estimator for the learner. The theoretical analyses on the sample complexity of the algorithms using this new loss estimator are provided.", "questions": "1. Can the authors comment on the computational complexity issue above regarding the computation of $R_i$ and $\\mathcal{H}_{i+1}$?\n2. How exactly is the bound in Theorem 1 better than the existing bounds in related settings?\n3. How can we compare the results in the paper with the sample complexity lower bound for adaptive sampling strategies in the Group-DRO setting [1]? I am aware that the two settings have different assumptions on the convexity and compactness of $\\mathcal{H}$ and  $\\ell$, so my question is restricted to compact convex $\\mathcal{H}$ and convex $\\ell$ only. In other words, would the lower bound in [1] apply if $\\mathcal{H}$ is compact convex and $\\ell$ is convex in your active learning setting?\n\n[1] Optimal algorithms for group distributionally robust optimization and beyond. Soma et al., 2022.", "limitations": "I suggest the authors to include more detailed discussion of the limitations of the proposed algorithms in the main text. These include any computational as well as theoretical issues raised above.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The paper considers the multi-group extension of the active learning problem, which is likely a hard problem of high interest for the active learning community. The setting considered in the problem can also be seen as a variant of the Group-DRO problem in which the set of hypotheses and the loss function are not assumed to be convex.\n- The paper shows rigorously why the traditional disagree-based active learning approaches in the multi-group setting, and proposes a novel multi-group loss estimator with reasonable theoretical guarantees.\n- For the most parts, the writing is clear and easy to follow.", "weaknesses": "Major: \n1. The main algorithm, Algorithm 1, seems computationally intractable. A thorough computational complexity analysis is lacking, especially in the most important steps in Algorithm 1 on line 4 (computing $R_i$), line 21 (computing $\\hat{h}_i$) and line 22. These steps involve filtering two sets ($\\mathcal{X}$ and $\\mathcal{H}_i$) that are possibly uncountably infinite, however no explanation is given on how these steps are done. This reduces the impact of the proposed approach to practical scenarios.\n2. It is not clear why the sample complexity bound given in Theorem 1 is an improvement over passive and collaborative learning. The bound in Theorem 1 still depends on $d/\\epsilon^2$, which is confusing since the text wrote ``the interaction between $d$ and $1/\\epsilon^2$ is removed\". In fact, the additional multiplicative factor $G\\theta_g^2\\log(1/\\epsilon)\\nu$ can be larger than 1, which makes the bound in Theorem 1 worse than the collaborative learning bound shown in Table 1.\n3. A lower bound is lacking, which makes it impossible to judge how tight the upper bounds are.\n4. Empirical evaluation is lacking. \n\nMinor:\n1. Throughout the paper, the references to various technical lemmas are missing. In Section 5.2, the paper wrote \"it is a lemma of ours that...\", with no references. Similarly, the proof of Lemma 1 in the Appendix (line 433) mentions \"a lemma of Vapnik [28]\", which is meaningless because Vapnik [28] is a 700-page book.\n2. One the same line 433 - 434, the $1/m$ term in the uniform convergence bound looks redundant. Mathematically it might be correct, but a tighter (and simpler) bound that only depends on $\\sqrt{\\frac{\\ln(8/\\delta) + d\\ln(2em/d)}{m}}$ (up to constants) are well-known and can be found in any standard machine learning texts (e.g. see [1], section 28.1, page 393).\n3. This factor of $1/m$ is missing in the second equation on line 440, the first term.\n4. In the main text: \"with the ability decide\" -> with the ability to decide; \"not enough infer\" -> not enough to infer; \"would chose\" -> would choose.\n5. Typo in the equations in Example 1: it should be $\\ell(h, i, A)$, not $\\ell(h, i, S)$.\n\n[1] Shai Shalev-Shwartz and Shai Ben-David. 2014. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, USA.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments, and the close reading even of parts of our Appendix. \n\n>Can the authors comment on the computational complexity issue above regarding the computation of $R_i$ and $\\mathcal{H}_{i+1}$?\n\nWith regard to computational considerations, one can always construct an epsilon cover of the hypothesis (of near-optimal size using a polynomial number of unlabeled examples [2]) and reduce to learning over a finite class, in which case one can directly execute the algorithm. \n\n> It is not clear why the sample complexity bound given in Theorem 1 is an improvement over passive and collaborative learning. The bound in Theorem 1 still depends on, which is confusing since the text wrote ``the interaction between and is removed\".....How exactly is the bound in Theorem 1 better than the existing bounds in related settings?\n\nThe reviewer is correct that the interaction between $d$ and $1/\\epsilon^2$ is not 'removed' unless the noise rate is 0; this is a writing error that we will fix in the next version. That said, as we discuss in Section 5.3, when the noise rate is small enough, it will be dominated by other terms. This is exactly the type of guarantee one finds in canonical 0-1 loss active learning literature [11]. As we also note in Section 5.3, we also need the number of groups to be small to improve over collaborative learning lower bounds. \n\nIt should further be mentioned that the upper bounds in collaborative learning are on the expectation over a draw from a distribution over the hypothesis class [1], which is a very different style of guarantee than what we present here.\n\n> How can we compare the results in the paper with the sample complexity lower bound for adaptive sampling strategies in the Group-DRO setting?\n\nThis is an interesting question that has pointed us to some cool related work by Soma et al. [12] that we will cite in the next version of our paper. While a complete mathematical comparison would require new algorithmic analysis on our part, the game-theoretic approach taken by [12] leads to a reduced dependence number of groups which we do not achieve in this paper; this, much like in the comparison to the collaborative learning lower bounds, leads us to the requirement that the number of groups be small for tighter guarantees. We do note that our algorithm is designed to work in a more general setting where convexity assumptions cannot be exploited, so it's not entirely unreasonable that our guarantees do not match theirs in this special case. \n\n&nbsp; \n\n[1] On-Demand Sampling: Learning Optimally from Multiple Distributions. Haghtalab et al., 2022.\n[2] A Bound on the Label Complexity of Agnostic Active Learning. Hanneke 2007. \\\n[3] Agnostic Active Learning. Balcan et al., 2006. \\\n[4] A general agnostic active learning algorithm. Dasgupta et al., 2007\n[11] The two faces of active learning. Dasgupta, 2012. \n[12] Optimal algorithms for group distributionally robust optimization and beyond. Soma et al., 2022.\n"}]

Author rebuttal:
We appreciate all the reviews. 

There were a few comments on the fact that the general agnostic algorithm (Algorithm 1), as stated, cannot be explicitly executed for infinite hypothesis classes.  

In the case that one wishes to run the algorithm, one can always construct an epsilon-cover of the hypothesis class $\mathcal{H}$ (of near-optimal size using a polynomial number of unlabeled samples [2]), and then execute the algorithm on the resulting finite class, while maintaining guarantees. 

Beyond this, prior work in active learning has come up with algorithmic techniques, such as leave-one-out training [14] and constrained optimization [4], for making active learning strategies directly computationally feasible on uncountable hypothesis classes. How to apply those for this specific problem is an interesting direction of future work, something we will discuss in an updated version of the paper. 

&nbsp; 

[2] A Bound on the Label Complexity of Agnostic Active Learning. Hanneke 2007. \
[4] A general agnostic active learning algorithm. Dasgupta et al., 2007 \
[14] Agnostic Active Learning Without Constraints, Beygelzimer et al., 2010.


Meta-review: The paper studies the classical setting of active learning but in the multi group setting. This is an important setting given applications to fairness and robustness. The authors show why standard disagreement based active learning approaches fail and propose modifications under which one can obtain label complexity upper bounds. Overall the reviewers are supportive of the paper. However, the authors are encouraged to take the reviewer comments into account in order to improve the paper especially connections to recent work on collaborative learning.
Decision: Accept (poster)