Active Learning of Classifiers with Label and Seed Queries
Authors: Marco Bressan
Nicolò Cesa-Bianchi
Silvio Lattanzi
Andrea Paudice
Maximilian Thiessen
Venue: NeurIPS 2022 Accept (2022)
Keywords: Active learning
Clustering
Multiclass classification

Abstract: We study exact active learning of binary and multiclass classifiers with margin. Given an $n$-point set $X \subset \mathbb{R}^m$, we want to learn an unknown classifier on $X$ whose classes have finite strong convex hull margin, a new notion extending the SVM margin. In the standard active learning setting, where only label queries are allowed, learning a classifier with strong convex hull margin $\gamma$ requires in the worst case $\Omega\big(1+\frac{1}{\gamma}\big)^{\frac{m-1}{2}}$ queries.  On the other hand, using the more powerful \emph{seed} queries (a variant of equivalence queries), the target classifier could be learned in $O(m \log n)$ queries via Littlestone's Halving algorithm; however, Halving is computationally inefficient. In this work we show that, by carefully combining the two types of queries, a binary classifier can be learned in time $\operatorname{poly}(n+m)$ using only $O(m^2 \log n)$ label queries and $O\big(m \log \frac{m}{\gamma}\big)$ seed queries; the result extends to $k$-class classifiers at the price of a $k!k^2$ multiplicative overhead. Similar results hold when the input points have bounded bit complexity, or when only one class has strong convex hull margin against the rest. We complement the upper bounds by showing that in the worst case any algorithm needs $\Omega\big(k m \log \frac{1}{\gamma}\big)$ seed and label queries to learn a $k$-class classifier with strong convex hull margin $\gamma$.

Active Learning of Classifiers with Label and Seed Queries
Marco Bressan
Nicolò Cesa-Bianchi
Dept. of CS, Univ. of Milan, Italy marco.bressan @ unimi.it
DSRC & Dept. of CS, Univ. of Milan, Italy aecolo.cesa-bianche @ unnim..it
Silvio Lattanzi
Andrea Paudice
Google silviol google..om
Dept. of CS, Univ. of Milan, Italy & Istituto Italiano di Tecnologia, Italy
andrea. andrea.paudice
paudice @ unimi.it
Maximilian Thiessen
Research Unit ML, TU Wien, Austria
maximilian thillsanntiieeeeneee @ @uwieen.cc.a
Abstract
We study exact active learning of binary and multiclass classifiers with margin. Given n-point set X IRm want to learn an unknown classifier on X whose classes have finite strong corvex hull margin, a new notion extending the SVM margin. In the standard active learning setting, where only label queries are allowed, learning a classifier with strong convex hull margin requires in the
queries. On the other hand, using the more powerful seed queries (a variant of equivalence queries), the target classifier could be learned in O (m log n) queries via Littlestone's Halving algorithm; however, Halving computationally inefficient. In this work we show that, by carefully combining the two types of queries, a binary classifier can learned in time poly (n + m) using only Omm? logn) n) label queries and O O log m) seed queries; the result extends to k-class classifiers at the price of a k! multiplicative overhead. Similar results hold when the input points have bounded bit complexity, or when only one class has strong convex hull margin against the rest. We complement the upper bounds by showing that in the worst case any algorithm needs 9 (km log 2) seed and label queries learn k-class classifier with strong convex hull margin 7
worst case 22(1 +
Introduction
This work investigates efficient algorithms for exact active learning of binary and multiclass classifiers in the transductive setting. Given a set X of n points in Ih our goal is to learn a function h X - [k] belonging to some class H. In the classic active learning framework, h identifies subset of X. and the algorithm learns h via queries LABEL(()) that return h(x)) for any given x E X. In that case, it is well-known that finite [annekee and Yang 2015). Unfortunately, even simple families such as linear classifiers have unbounded star number, which case 2(n) LABEL queries are needed in the worst case. To bypass this lower bound, it has become increasingly common to introduce enriched queries, that reveal additional information on and are plausible in practice. One notable example that of comparison queries for linear separators in Inm which, given any pair of points E X, reveal which one is
be learned with O n) LABEL queries the star number of H is
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

closer to the decision boundary. As proven by Kane et al. [2017], under some margin assumptions the combination of LABEL and comparisons yields exponential savings, allowing one to learn linear separators with only Oloog n) queries.
In this work we combine L.BEL queries with seed queries. For any U C X and any i E [R), query SEED(U, i) returns an abitrary point I in U n C, where C; = h (1), or NIL if no such x exists. SEED queries are natural in certain settings like crowdsoureing- finding the image of a car, see also Beygelzimer et al. [2016] and have been used implicitly or explicitly in several
works [Hanneke] [009 Balcan and Hanneke 2012 Attenberg and Provost 2010 Tong and Chang Bressan et al., 2021b]. It is not hard to see that, using SEED alone, one can implement Littlestone's ss Halving algorithm and learn any h E HH with Olog (H() querie For instance, linear separators in I' can be learned with (m log n.) SEED queries. The catch is that, save for special cases, is not known how to run the Halving algorithm in polynomial time. Therefore, using SERD to obtain computationally efficient active learning algorithm is less trivial than it seems at first glance.
2001] Doyle et al. 2011 |
The goal of this work is understanding whether one can actively learn binary and multiclass classifiers efficiently by using LABEL and SEED queries together. In line with Kane et al. [0117] and other previous works, we make assumptions on H. Our main assumption is that every class C2 has strong convex hull margin ? > O. This means that, for any j ن i, C, and Cj are linearly separable with a margin that is at least times the diameter of C, Moreover, it is sufficient that this hold under some pseudometric d,, unknown to the learner, that homogeneous and invariant under translation (i.e.. induced by a seminorm). This gives to every class its own personalized notion of distance that can be sensitive to the "scale" of the class. This assumption strietly generalizes the classical SVM margin; and, when suitably generalized, it captures stability properties of center-based clusterings Awasthi ctt al. 2012]. Bilu and Linial 2012].
Using LABEL alone, Bressan et al. 2021a showed that learning a multiclass classifier with (strong) convex hull margin y > requires between 22 + 1) (m 1)/2 and 01 1) log m) queries. This exponential dependence on implies that, unless m < log n/ log J. one needs O(n) LABEL queries in the worst case. On the other hand our margin implies linear separability and thus, as noted above, a (m log n) SEED query bound for the binary case, but with a running time that can be superpolynomial. This leaves open the following problem, which is the subject of this work:
Can one learn a multiclass classifier ht with strong convex hull margin y > 0 on X C Rm in time poly(n+m) using a number of queries that grows polynomially with m??
We solve the above question in the affirmative by proving that, with careful combination of LABEL and SEED queries, one can do much better than using either query in isolation. For binary classification (k: 2), we show:
Theorem 1. Any binary classifier h with strong convex hull margin ? >> 0 over X R Th can be learned in time poly(n+mm) using in expectation O(m² logn) LABEL queries and O 0(m log m)
SEED queriex
Note that, unless y is exceedingly small, Theorem Sareeemmuseee Juses far fewer SEED than L. queries, which is a strength since SEED is arguably more expensive to implement. For instance, if (11 poly(m)) then we use O(m² lo LABEL queries but only Om log m)) SEED queries. To prove Theorem we design a novel algorithm that works in two phases. The first phase learns what we call a-rounding of X w.r.t. h. Loosely speaking, this is a partition (X1, X2) of X such that each X; lies inside conv(C,) where (C,) is the convex hull of C, (see below for the formal definition). We show that, in polynomial time and using Om? log n) LABEL queries, one can compute an a-rounding of X; for
to put X, in near-isotropic position so that X, has radius 1 and to separate C1 O X; from C2 n X, with margin d = 0(7/m²). In the second phase, the algorithm uses SEED to implement cutting plane algorithm that learns C1 O X, and C2 n X, using (m log ;)) = O m log m queries in time poly(n + m).
O(m²). ). This allows
'Halving uses equivalence queries (testing if given subset of X coincides with the target concept) each of which can be simulated using two SEED queries. 'This running time as well as those of Theorem 2 and 3 are actually in high probability as implied by
Theorem 10, we have omitted this fact to keep the statements light.

---

Using recursive approach, Theorem can be extended to k > 2 at the price of a k!k? multiplicative overhead:
Theorem 2. Any k-class classifier h with strong convex hull margin y > over X C R can be learned in time poly(n + m) using in expectation Okk! h2 m² log LABEL queries and Ok! k2 m log () SEED queries.
We also consider the case where only one class has strong convex hull margin against the rest of the points w.r.t. metric d induced by a norm - In this case we obtain bound parameterized by the distortion Ka of d (see Section I.I:
Theorem Suppose C has strong convex hull margin y E (0, 1] w.t.t metric with distortion Rd < cc. Given only X, one can learn C in time poly(n + m) using Oloo n)) LABEL queries and (m log *+4 SEED queries in expectation.
As an application of our cutting-plans algorithm we also show that one can learn k-class classifier whose classes are pairwise linearly separable in time poly(n + m) using, in expectation, (1.2 m² B) SEED queries if every x E X has rational coordinates that can be encoded in B bits, and (k3 B m m)) SEED queries if every I E X lies on the grid over [-1, 1 with stepsize 2 B/m, It should be noted that, unlike most previous algorithms, all our algorithms do not need knowledge of Moreover, all the bounds above can be turned from expectation to high probability
Finally, we show that the algorithms of Theorem and and are nearly optimal:
Theorem For all m 2 2, all k 2 2, and all y S m 3/2 /16 there exists a distribution of instances with k classes in Rn with strong convex hull margin 7 where any randomized algorithm using SEED
and LABEL queries that returns C with probability at least 2 makes at least 2 24
log 27
total
queries in expectation.
1.1 Preliminaries and notation
The input to our problem is a pair kX, where X C I and & E N with 2 < k I n == |X| The algorithm has access to oracles OLABEL and OSEED which provide respectively LABEL and SEED queries. The oracles OLABEL, SEED behave consistently with some target classifier h: X - [kt]. For any x X, LABEL(x) returns h(z)). For any U S X and any i E [k], SE, returns an abitrary element x E U n C. if n C2 A 0, and NIL otherwise, where C, 1= We often think of h as of the partition C (Ci, Ck) and we call each C, class or cluster.
pseudometric is a symmetric and subadditive function d' RT x F. - R2o such that d(x, x) for all I e R", unlike metrie, d(x, y) can be 0 for # y. In this work d is always induced by seminorm and thus homogencous and invariant under translation: d(u + az, u u- ay) = |a| d(z y) for all 2. y, u I and all E R. For pseudometric d and set A C RmM we let da(A) supfd(<x y) : x, y E A} denote the diameter of A under d. For x E R and r 2 0 we denote by BT (z. r) and 5mm-1 (I., r) respectively the closed ball and the hypersphere with center x and radius in TM under d. When d is omitted assume d = deuc where deuc is the Euclidean metric. We may also omit the superscript if clear from the context. The distortion of a (pseudometric) d is Ki = SuPu, 1(0.1) [u]la/||v|]a
For any set A C RT any μ E I and any À >> 0, let let a + A(A (1) be the scaling of about μ by a factor of X. For two sets A, B C R", we write A < AB if A C (B A) for in place of A if A {x}. If is bounded, then MVE(A) A) denotes the enclosing ellipsoid (MVEE, or Löwner-John ellipsoid) of A. Our proofs repeatedly use John's 's theorem; that is, aEE, p, 1/m) C conv(A) where μ is the center of E MVE ((A) and conv(A) (A) is the convex hull of A. Given A, B C Rmm we say that A and B are linearly separable with margin if there exist u E 5m (0, 1) and b IR such that (u, x) b < for all A and (u, . + b 2 r for all x E B.
some R m. We may minimum-volie
We consider classifiers satisfying the following property
Forrmally for universal constant > 0, each one of our bounds in the form E[Q] S g. where is the number of queries, implies Pr(Q= 2 q + eq) I exp(-acc for c 2 O.
"Actually, all our upper bounds hold under weaker condition: that for every i and every E [A] \ {i) there is dij giving the margin.
3

---

Definition 5. A class C₁ has strong convex hull margin 7 > 0 if there exists a pseudometric d; induced by a seminorm over R. such that di (conn(CC) co)v(C.)) > 7 Qd, (C.) all j E [k]] {i). If this holds for all i E [k) then we say C has strong convex hull margin 7/-
Remarks. The margin of Definition 5 captures natural scenarios that SVM margin does not. For instance, suppose we are clustering fruits on the basis of weight and colour. First, fruit weighting more than, say, 1.5 times the typical weight of a species probably does not belong to it; but the typical weight varies greatly across species. Our margin captures this scenario, as it is expressed as a fraction of the class' diameter. Second, different fruit species have different separating features; for instance, weight does not separate well oranges from bananas, but colour does. Our margin captures this aspect, too, by allowing the metric that determines the margin to be a function the class. is also known that the SVM margin "isvM can be arbitrarily smaller than Y; for instance there are simple cases with y > but 7svM < e (see Bressan et al. (221aa). Hence a large 7 does not imply good bounds for standard algorithms based on SVM margin (e.g., the Perceptron).
Related work
It is well known that active learning may achieve exponential savings in label complexity. That is, there are natural concept classes that can be learned with a number of LABEL queries exponentially smaller than that of passive learning. [Hanneke and Yang (2015) characterize the label complexity of concept classes in terms of their star number. However, the star number of many natural classes such as linear classifiers is unbounded, implying strong lower bound of (2()) LABEL queries.
This and other negative results motivated research on enriched queries. Kane et al. [2077] prove that active learnability is characterized by the inference dimension of the concept class H under the set of allowed queries Q. as long as those queries are local (i.e., are a function of a constant number of instances). This yields exponential savings when H is the class of linear separators and Q contains label queries and comparison queries (which, given two points, reveal which one is closer to the decision boundary), provided the classes have SVM margin or bounded bit complexity. Hopkins et al. (2020) give similar results under distributional assumptions. Unfortunately, bounded inference dimension does not automatically yield efficient algorithms, although it implies active learning algorithms with bounded memory (Hopkins et al. 202T].
SEED and their variants are motivated and used by Hanneke [2009] as positive example queries, by |Balcan and Hanneke [2012] as conditional class queries, and by [Beygelzimer et al. (2016).
Attenberg and Provost| [2010] as search queries. They are also used implicitly by Tong and Chang
[2001]. Doyle et al. 2011], J, and Vikram and Dasgupta (2016). SEED queries have been used in cluster recovery [Bressan et al. 2021b) and yield exponential savings in non-realizable learning settings [Balcan and Hanneke| 2012]. It also easy to see that SEED queries are equivalent to partial equivalence queries of Maass and Turán [1992] and subset plus superset queries of Annllii [9888] To the best of our knowledge, no work combines LABEL and SEED as we do here.
Little is known about the SEED complexity of learning a concept class H actively in polynomial time. On the one hand, the inference dimension lower bounds of Kane al.] 2017] are inapplicable, as SEED queries are not local. On the other hand the Littlestone dimension of H. yields an upper bound, but not necessarily an efficient algorithm; in fact, it is well known that (some sub-problem solved by) Halving is hard in general, see Gonen et al.] (2013). For k = 2, we can use SEED to emulate equivalence queries, for which polynomial-time algorithms are known in some special cases. In particular, the algorithm of Maass and Turán (1994) could replace our cutting-planes subroutine under an implicit discretization of the space through grid with step-size O(7/m²). However, this gives polynomial-time algorithm that uses O Om2 log "*/n) SEED queries, which is O(m) times bound. Moreover, Maass and Turán [1994] use proper equivalence queries (i.c., the queried concept must be in the class), for which they show a lower bound of 2(m² log m//)). Finally, these techniques do not seem to extend to the case k > 2.
Our notion of margin strengthens the convex hull margin of Bressan et al. [2021a] by requiring (C,onv(C,), (Cn)(C.)) > 7o(C,) rather than d(C;, C.) > (C.C.) It not hard to see that the convex hull margin can be arbitrarily smaller than our strong convex hull margin. Finally, the polytope margin of Gottlieb et al. [2018) assumes that each class is in the intersection of a finite number of halfspaces with margin. It is casy to see that this condition is strictly stronger than ours.

---

3
Upper Bounds
This section gives the proofs of Theorem | and Theorem 2
The algorithm behind both theorems has two phases which are described in the next subsections. The case k >> 2 is essentially the same as for k 2, except for an adaptation in the second phase.
3.1 The First Phase: Rounding the Classes
The first phase of our algorithms learns what we call an o-rounding of X.
Definition 6. An a-rounding of X (w.rz. h) is sequence of pairs ((X,, (e)) where (Xi) a partition of X, and where Fi for E [k] is an ellipsoid such that X; Fg and E, S a conv(C.).
The idea is that, if ((X;, FE]))E(R) is an a-rounding of X, then Eş gives an approximation of the pseudometric de witnessing the strong convex hull margin of C. Indeed, let p; be the pseudometric induced by E, the one such that E, = Bp. (pi, 1) where μa is the center of E5; we prove:
Lemma 7. If ((X;, P.)))E(M) is an o-rounding of X then pe p:(conv( (X; n Ct), conv (X n (C)))))))))))))) 2 for all distinct j.j [k:].
Proof. If is the center of E,, then E, = By, (15. 1). Let de be any pseudometric witnessing that C2 has strong convex hull margin y >> As the margin is invariant under scaling, we can assume dd. (C:) = 1 and conv (C,) C Ba, (2;, 1) for some 2; E m Therefore:
Bp, (p,, 1) = E, I a conv S aBa, (2;,
As p. and d, are homogeneous and invariant under translation this implies p, 2 d. and thus p; (cony (X; n C2), conv(X; (X; n C:)) 2 d (conv (X; n Cj), conv(X;nC.) Moreover, by mono- tonicity under taking subsets and by the margin assumption d, (conv(X, nC2), conv(X, (C))) > d, (.(onv((C) conv(C.)) 2 you, (C,) 7. Combining the two inequalities yields the thesis.
O
We will use Lemma| 7 in the second phase. First, we show how to compute an a-rounding of X efficiently. We sample points independently and uniformly at random from X until we find (mm)) points S; with the same label i. As the VC dimension of ellipsoids in R is Omm)), ), by standard generalization eтror bounds with constant probability the MVE of S; contains at least half of C. We then store that MVE together with the index remove S, from X, and repeat until becomes empty. At that point for each i [k] we "merge" together all points in the MVEs that were computed for class i, and compute the MVE of this merged set. We show that this produces an a-rounding X The resulting algorithm Round is listed below; Figure
after Olk log n) rounds in expectation
! depicts its behaviour on a toy example.
Lemma 8. Round(X, k) returns an m² (m 1)-rounding of X in time poly(n m) using Olk2m² logn) LABEL queries in expectation.
Proof sketch. First we show that E, mmmmm + 1) conv(C.) for all i E [K]. This is trivial if Eg 0. so let E, * 0 and let & 2 1 be the value of h, at return time. For every h 1, 1.... ly let E MVE(S;) and let ut be the center of E,, Using John's theorem one can show that o (Ei, p4, 1) C conv Uh af conv(S))) pd, m) and conv(S))) n4, (.f.m)) m) S acconv (C.), n. m(m + 1)). By tak- ing the union over all h E [6,]] we conclude that o EE,, Pá. 2) C (coovv(C.), μ. m(m + 1)), that is, E, < m² (m - 1) conv (C.). It is also easy so see that (X.)E is partition of X, hence ((,,, E.)) is m² (m+ 1)-runnding of X.
For the running time, the for loops perform A: S n iterations, and the while loop performs at most iterations as each iteration strictly decreases the size of X. The running time of any iteration dominated by the computation of MVE(S,) or MVE(X;), which takes time poly(n + m). see above. Hence Round X, k) runs in time poly + m). For the query bounds, the while loop makes Ommkk) LABEL queries per iteration. By standard generalization bounds, since the VC dimension of
A 'hhtt we actually want is, given a finite set C R", an ellipsoid & such that (L+eja C conv(S) C This can be computed in (1SS) In((S)/c) operations in the real number model of computation, see Khachiyan 1996) For simplicity however we just assume that can compute & MVE(S) in polytime.
5

---

Algorithm 1: RXund(X,A)
for i E k] do h4 +
while X do
draw points independently u.a.r. from X and LABEL them until for some E [A]] we draw (multi)set of em points from C;
h4 f h4 +
shh the sample of em& points from C
x + -
X + x
for i E k| do
X; & X U... . U X (set to if h; = 0)
E, M)E(X;) (set to 9 if X; 0)
return ((x,, kE)
E
E2
Figure 1: A toy example in R² with k: 2: black points are in C1. blue points in C2. Round 2) computes first the ellipsoids E E (dotted black, from left right), and then the ellipsoids El ET, E (dotted blue, from left to right). Finally it computes Ei (solid blue) and E2 (solid black). X1 and X2 consist of the points the blue and white areas respectively. Note that X2 contains point of Ci.
ellipsoids in R is (m²)), ENt contains at least half of X n n'C, with probability at least A. and thus the expected number rounds before becomes empty is in O lgn). see Bressan et [2021a] We conclude that Round(X. X, k) uses Omm2k² Ign) LABEL queries in expectation.
3.2 The Second Phase: Finding a Separator via Cutting Planes
Let ((X,, E.)) ae be the output of Round [X, k), and fix i E [k]. For each j E [A]] \ {i}, we want to separate X, C2 from X, n To this end, first we use E, to perform a change of coordinates; this puts X; inside the unit ball and ensures that X; n C, and X; nC are linearly separated with margin 7SVM 2(ym -3). Next, by calling C, the positive class (+1) and C, the negative class (-1), and letting X = X; for simplicity, one can reduce the task to the following problem. Consider a partial classifier : X - {+1,- -1, 11,+1 *}. The algorithm has access to an oracle answering queries {+1, - 1}. and its goal is to compute separator of X:
SEED(U, y) where U X and
Definition 9. Let X C n and h X + {+1, -1 A separator of X (w.rt. h)) is partition such that, for every x E X, if h(x) +1 then E X4 and if h(x) = -1 then
of (-+,X-) X_.
A separator of X can be learned, for instance, by the Perceptron (using SEED to find counterexamples). However, this would yield query and running time bound of (11 O(m") //2). We provide CPLearn, a cutting-plane algorithm based SEED that is much more query-efficient (in fact, near-optimal):
Theorem 10. Let C T and h X (+1,-1,*) and suppose h h-1(+1) and --11) are linearly separable with margin Given X and access to SEED for labels {+1, -1}, CPLearn(X)

---

computes a separator of X w.t.t h using Ommlog () SEED queries in expectation, where R maxxex || and running with high probability in time poly(m + [X]
6
Proof. (Sketch) First, we lift X to Rm+1, This reduces the problem to finding homogeneous linear separator. To this end we let X' = f æ E ] where x' is obtained by appending to æ an (m + 1)-th coordinate that is equal to R. and we extend h X' in the obvious way. is easy prove that X' has radius at most 2 and that in X' the two classes are linearly separable with margin 2-
Next, learn separator of X' w.r.t. via cutting planes-see, e.g., Mitchell [2003] Let Vo- Bm++ (0, 1). Every point E Vo identifies the halfspace (u) {2 E Rmm1" {u, 2) 2 0). For i 1, .., V3 will be our version space, and we compute V4+1 from V; follows. Let 14; be the center of mass of Vú, and let X = X'n (14). By issuing SEED(XX, - and SEED(X") x +1) we learn whether (X,, X' \ X() is separator of X' w.r.t. h, in which case we return the corresponding partition of X, we obtain point wy, In the second case. we let V = Vi n U, where U; = {x Rm++1 h(s)) (uss x) 2 0}. By [Gilad- Bachrach et al. 2004 Theorem 2] this procedure returns a 37C O (m ! queries.
separator of X' w.r.t. using at most log -
log
r/2
Unfortunately, computing μr is hard in general [Rademacher] 2007]. We instead compute an estimate i, that, used in place of μ4, ensures vol(V441) is bounded away from with high probability; the expected query bound follows by adapting the proof of (Gilad-Bachrach al.) 2004). Assume for the moment that VÚ is well-rounded- that is, it contains ball of radius r poly (m) and is contained in a ball of radius 1. To compute A, we average over poly(r + m) independent uniform points from Vi. which can be draw efficiently thanks to the rounding condition. At this point we use Pas in place of μ4y to invoke SEED and obtain a violated constraint U.. Howewer, setting V4+1 V2 n U4 could make V far from rounded (too "thin")) making sampling inefficient at the next round. Therefore we rotate U, so to obtain a weaker constraint U7. one that still contains Vi n U2 but that has fú; on its boundary, and let Vi+1 V; n U.. By the assumption on üú; this implies that vol (o(+V)1) 2 1/4 vol((V)) therefore by sampling uniform points from V; we can obtain a large sample in V4+1, from which we can put Vi+1 1 in a rounding position. See the full proof for all the details.
To the best of our knowledge, CPLearn is the first efficient algorithm that achieves the query upper bound of Theorem 1O even for the special case of SVM margin.
3.3 Wrap-Up
We wrap up our algorithms, starting with the case k = 2; the case A 2 2 is slightly more involved.
Algorithm 2: BinLearn(X))
((11, E1), (X2, E2) +
Round(X)
for i + 1, 2 do
change system of coordinates so that E, becomes the unit ball (X++, + CPLearn(N) X,)) with h X₁ + {1,2}
return (X1+ U , X2+ UX1-)
Theorem 11. Suppose hs = 2. Then BinLearn(X) returns C = (C1, C2) in time poly(n + m) using in expectation O(m² log LABEL queries and (m log m2
SEED queries.
7
Proof. By Lemma 8 Round (X) runs in time poly(n + m)) makes O(m² log LABEL queries in expectation, and returns ((mm))-roundinn coordinates, X; has radius R < 1, while C1 n X2 and C22 n X, are separated linearly with margin 2(ym 3). By Theorem 10 then, CPLearn (X,) returns the partition of X; induced by h in time poly([X,| + m) poly(n + m)) using (m log R Om log /) expected SEED queries.
of X. It is immediate to see that, after the change of
'This means that the running time be brought in poly (m + (X() with probability 1 1- -exp(-(m [X))).
7

---

For h 2 2 we proceed as follows. Let k [k. We take X; for each E k in turn, and for each j E k é i. we use CPLearn to compute a separator for j X,. By intersecting the left side of all those separators we obtain X; n C.. Then we recurse on X; \ C2 updating k to k i. The resulting algorithm KClassTearn listed below and yields:
Theorem 12. KClassLearn(X, (X, [k]) returns C in time poly(n + m) using in expectation OlAR2 m² log n) LABEL queries and O Ok:I? mlog ") SEED queries.
Observe that KClassLearn(X, [k]) makes at most min(k!, n) recursive calls; the n in the min comes from the fact that any given (recursive) call learns the label of at least one unlabeled point. Now, every (recursive) call makes one invocation to Round(X) (X), which by Lemma uses time poly (n + m) and O(k2m² log n) LABEL queries, and
Proof. We adapt the proof of Theorem
(12) invocations to CPLearn(X:)) each of which by Theorem 10 uses poly(n h + m) time and O (m log )) SEED queries.
Algorithm 3: KClassLearn(X,
k - kk
k = then query any point of and label all of X accordingly else
((X,, (E) + (Xund(X)
for i E k do
change system of coordinates so that E, becomes the unit ball
for j E ' do
(Cij, Cit) + CPLearn(X.) with h X, - {i.j}
- Cis
mark all of Cj with label
X; Õ f then KClassLearn(X; \ C, k ())
4 Lower Bounds
This section gives a detailed sketch of the proof of Theorem 4 recalled here for convenience:
Theorem 4. For all m 2 2, all k 2 2, and all y S m m-33//11 /16 there exists a distribution of instances with k classes in Rm with strong convex hull margin 7 where any randomized algorithm using SEED and LABEL queries that returns C with probability at least 7 makes at least queries in expectation.
k
m
log total
2
24
We first give the sketch for 1: 2, and then extend it k 2. For a full proof see Appendix B Set- up. The construction is adapted from Proposition 2 of Thiessen and Gärtner [2021). Let cI....s Cr
16 and m 2 2 ensure f 2 4. Let = m 1, and for each E [p] and j E [C] define xf = e, + 6m Finally, let X = {x}
be the canonical basis of 1. and let e = L2//2//l note that ? S 37-
i E [pl.j E [ and define the concept class H = [ a (E1,..., e,)
[(]] Let
C = (2) be any partition X such that C₁ E H. One can easily verify that C has strong convex hull margin 28 pm 2 7. See Figure 2 for reference.
f
Query bound. Let Vo= ((C1, C2): H). This is the initial version space. We let the target concept C= (C1, C2) be drawn uniformly at random from V.. Note that for l: = 2, any lower bound on the number of SEED queries alone, also holds for any combination of SEED and LABEL queries, as LABEL(x) can be simulated by SEED(I, 1). Thus, without loss of generality, we can assume that the algorithm is only using SEED queries. For all / 0, 1, .,... we denote by V,, the version space after the first / SEED queries made by the algorithm. Now fix any > 1 and let SEED(U, y) be the 1-th such query. Without loss of generality we assume y = 1; a symmetric argument applies to y = 2. U n C₁ contains point whose label can be inferred from the first t 1 queries, then we return
8

---

Z
+
Si
S
Z/
Figure 2: X for p 2 and 10. Filled points represent the agreement region. The maximum point of S1 C (resp. S2 n C1) can be any point Z1 (resp. Z2). U is a possible query.
I. Therefore we can continue under the assumption that does not contain any such point (doing otherwise cannot reduce the probability that the algorithm learns nothing). The oracle answers so to described below.
maximize [Vi [V-1l*
For each E [p] let S; = (=] E [q]. We consider S; as sorted by the index j. Let Z; be the subset of S; in the disagreement region of V together with the point in S; preceding this region; observe that this point always exists, as ot C1 is in the agreement region. Note that Z; is necessarily an interval of S, We let U, = Zj n U for each E [p] and P(U) = fi E [p] U * 0}. For every i E P(U), we let be the fraction of points of Z; that precede the first point in U,. Let a arg max(j a!f E C, Observe that |V--1 Ilee |Ze] Indeed, x is uniformly distributed over Z;; either at a point in the disagreement region of St the disagreement region of S; is fully contained in C2 and x is the point preceding the disagreement region of S,
Now show that
Let be the event that SEED
NIL. Write:
V
Ve-1
V--1 [V
E
Pr(E) E
+ Pr(E)
3
V
bound each one of the two terms in the right- side.
For the first term, note that & holds if and only if D = 0 for all P(U). Since x is uniformly distributed over Z, for all e P(U) we have Pr(C1 N. 0) ai and since the distributions of those points are independent, then Pr(E)= = Ihe r(t) ag. If Pr(E) > and & holds, then is uniformly distributed over the first 0: Zz| points of Zí, the rest of Z₃ belongs to Cz. This holds independently for all i, thus:
II as
II
|
II (EP(U)
II AEEP
7
IV-1l II as (3) #EP(U)
iEP(U)
sE(P)(P(U)
follows that Pr(E)
M [
1
Let us turn to the second term. If & does not hold, then SEED(U, 1) returns the smallest point E U; for any i E P(U) such that Ci nU + (note that necessarily C1). For any fixed i P(U), the probability of returning the smallest point of U, is bounded by Pr(C, nU, # 0), which is ag
and if this is the case, then we have [Vg = (1 V--)- Thus:
V
Pr(E)
3
< Pr(EE
max (1 05))
Pr(E) <
(4)
M
SEP(U)
(1 -1-ay as)
So the two terms of (2) are both bounded by 1; we conclude that E
<
[V
Next, fix any > 1 and let log
logg- By the concavity of log and by Jensen's inequality:
Vo
V--l
Vz-1
V
E
log
= E
log
Σ
E
log
log
E
(5)
Vi
V
V
V

---

Since IV 1 [el
s the right-hand hantt-hnddha side is at most f. Now, since [Vo]
10 pm=1
by Markov's
inequality, and since (m 1) log log
(m- logt
me log
Vo Vi
IE
log
Vol Vil
4
Pr([Vi 2) = Pr log
2 (m - log é log
1
(6)
m72 log
m log
Now let I' be the random variable counting the number of queries spent by the algorithm, and let Vr be the version space at return time. Since C' is uniform over Vi and is returned with probability at least 2. then Pr([Vr] I 2) By (6) and linearity of expectation.
4
S Pr 2) S Σ
Pr(T =
E[T
2
m log
mi log E
P20
Therefore E 2 m log Now, since 2 then 5/24//
which since m I (16y) yields,
after calculations, l 1//7-
4/3
0.89 1/7. This shows that T
log 1 24 24 concluding the
5v2
proof for k: 2.
Extension to k > 2. For each E and each pair of classes C2a-1 C2., use the construction above shifted along the m-th dimension by (s 1)e. One can easily verify that learning C is as hard as learning & independent binary classifiers, for each of which the bound above holds.
5 Conclusions and Future Work
We have shown that, with a careful combination of LABEL and SEED queries, one can overcome the limitations of each query alone and get the "best of both worlds": an algorithm that achieves exponential savings and, simultaneously, has running time polynomial in the dimension of the space. Our work leaves open few problems. The first problem is to understand the tradeoff between the two query types: how many LABEL does one need if one is allowed only Q SEED? The second problem is whether, for the one-sided case, one achieve query rate that is independent of the distortion ri-- as we did for the multiclass case. The third problem whether one can improve the dependence of bounds the number k of classes, ideally bounding it by polynomial.
Acknowledgments and Disclosure of Funding
The authors gratefully acknowledge partial support by the Google Focused Award "Algorithms and Learning for AI" (ALL4AI). Nicolò Cesa- Besa-Bianchi also supported by the MIUR PRIN grant Algorithms,, Games, and Digital Markets (ALGADIMAR) and by the EU Horizon 2020 ICT-48 research and innovation action under grant agreement 951847, project ELISE (European Learning and Intelligent Systems Excellence).
References
Dana Angluin. Queries and concept learning. Machine Learning, 2(4):319-34,, 1988. doi: 1023/A// 10228211222 128753.
Josh Attenberg and Foster Provost. Why label when you can search? Altemativess active learning for applying human resources to build classification models under extreme class imbalance. In Proc. of ACM KDD, page 423-432, 2010. doi: 10.1144/1338804.185553
Pranjal Awasthi, Avrim Blum, and Or Sheffet. baste clustering under perturbation stability. Information Processing Letters, 112(()::9-55) -4,4,44447754 2012. doi: 10.0016f....2001110.000
Maria Florina Balcan and Steve Hanneke, Robust interactive learning. In Proc. of COLT, volume 23, pages 20. 10..44, 2012.
Alina Beygelzimer, Daniel Hsu, John Langford, and Chicheng Zhang. Search improves label for active learning. In Advances in Neural Information Processing Systems, volume 29, 2016.
10

---

Yonatan Bilu and Nathan Linial. Are stable instances easy? Comb. Probab. Comput., 21(5):643-66) September 2012. doi: 10.1017/000035541220009999
Marco Bressan, Nicolò Cesa-Bianchi, Silvio Lattanzi, and Andrea Paudice. On margin-based cluster recovery with oracle queries. In Advances in Neural Information Processing Systems, volume 34, 2021a.
Marco Bressan, Nicolò Cesa-Bianche Silvio Lattanzi, and Andrea Paudice. Exact recovery of clusters in finite metric spaces using oracle queries. In Proc. of COLT, volume 134, pages 775-803, 2021b.
Scott Doyle, James Monaco, Michael Feldman, John Tomaszewski, and Anant Madabhushi. An active learning based classification strategy for the minority class problem: application to histopathology annotation. BMC Bioinformatics, 12(1), 2011. doi: 10.
Ran
Amir Navot, and Naftali Tishby. Bayes and Tukey meet at the center point. In Proc. of COLT, pages 549-563, 2004.
Alon Gonen, Sivan Sabato, and Shai Shalev-Shward Efficient active learning of halfspaces: an aggressive approach. Journal of Machine Learning Research, 14(1):2583-2115, 2013.
Lee-Ad Gottlieb, Eran Kaufman, Aryeh Kontorovich, and Gabriel Nivasch. Learning convex polytopes with margin. In Advances in Neural Information Processing Systems, volume 31, 2018.
Steve Hanneke. Theoretical Foundations of Active Learning. PhD thesis, USA, 2009. AA13362265.
Steve Hanneke and Liu Yang. Minimax analysis of active learning. Journal of Machine Learning Research, 16(12)3487-3602, 2015.
Max Hopkins, Daniel Kane, and Shachar Lovett. The power of comparisons for actively learning linear classifiers. In Advances in Neural Information Processing Systems, volume 33, pages
2020.
Max Hopkins, Daniel Kane, Shachar Lovett, and Michal Moshkovitz. Bounded memory active learning through enriched queries. In Proc. of COLT, pages 2358-2387, 2021.
D. M. Kane, S. Lovett, S. Moran, and Zhang. Active classification with comparison queries. In Proc. of IEEE FOCS, pages 355-366, 2017. doi: D0.100/FOCS.2217..4
Leonid G Khachiyan. Rounding of polytopes in the real number model of computation. Mathematics of Operations Research, 21 21(2)330-330, 1996. doi: 10. 20.122/mmr..11.2.3000 21.2.07..
Bernhard Korte and Jens Vygen. Combinatorial Optimization. Springer, Berlin, Heidelberg, 2018. doi: 111007/978-3-662-560000
Stephen Kwek and Leonard Pitt. PAC learning intersections of halfspaces with membership queries. Algorithumica, 22(1):53-77 1998. doi: 10.1007/PL000138344
Iászłó Lovász and Santosh Vempala. Hit-and-run from a corner. SIAM Journal on Computing, 35(4): 985-1005, 2006. doi: 10. 1377/50097733377577777
Wolfgang Maass and György Turán. Lower bound methods and separation results for on- on-line learning models. Machine Learning, 9()): 1992. doi: 10.1007/BF00992274
Wolfgang Maass and György Turán. How fast can threshold gate learn? In Proceedings of workshop on Compulational learning theory and natural learning systems (vol. 1): constraints and proxpects, pages 381-414 1994.
John E Mitchell. Polynomial interior point cutting plane methods. Optimization Methods and Software, 18(5):507-534, 2003. doi: 00.1080/105567888 055578801000010777555
Luis A. Rademacher. Approximating the centroid is hard. In Proc. of ACM SoCG, page 302-305, 2007. doi: 10.1145/1247099.12444 1247123.
Maximilian Thiessen and Thomas Gärtner. Active learning of convex halfspaces on graphs. In
Advances in Neural Information Processing Systems, volume 34, 2021.
11

---

Simon Tong and Edward Chang. Support vector machine active learning for image retrieval. In Proc. of ACM ICM, page 107-118, 2001. doi: 10.1145550014..500155..
Santosh Vempala. Recent progress and open problems algorithmic convex geometry. In Proc. of FSTTCS, volume 8, pages 42-64, 2010. doi:
Sharad Vikram and Sanjoy Dasgupta. Interactive bayesian hierarchical clustering. In Proc. ICML, volume 48, pages 2081-2090, 2016.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We clearly state the assumptions under which our results hold.
(c) Did you díscuss any potential negative societal impacts of your work? [Yes] This is purely theoretical work with no direct societal impact, neither positive nor negative.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) or curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "YB8u6J-Hsb", "reviewer": "Reviewer_TPhg", "summary": "This paper tackles the problem of active learning on classifiers with strong convex hull margin classes. In this framework that generalizes SVM margins, it is known that the query complexity of learning with only label queries is exponential in the dimension and that learning with seed queries is computationally inefficient. Is designed in this paper an approach that combines label and seed queries to learn such classifiers with a low query complexity in polynomial time. In addition to the upper bound on the query complexity of the provided algorithm, is established here a worst case lower bound on the query complexity of learning a k-class classifier with strong convex hull margin.", "questions": "For the query complexities, it seems like the lower bound is linear in the dimension while the upper bound for the label query is quadratic. \n- Which of the two could be improved?\n- Are there interesting cases where the upper and lower bounds match?\n- Is there a problem dependent quantity that characterizes the problem? \n\nAre the algorithms BinLearn and KClassLearn implementable in practice?\n", "limitations": "The assumptions made are adequately stated. It would be nice to more clearly address the limitations of the work: without empirical support the algorithms provided in this work seem more like proofs of concept and it feels like there are still some open problems on the query complexity upper bounds. The authors state that the potential negative societal impacts of their work is N/A due to its theoretical nature. It might still be valuable to mention what could go wrong if the suggested algorithms were actually deployed. ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Presentation: the problem is well introduced and the main results are clearly presented\n- Impact: some of the results established seem to be of general interest (in particular CPLearn’s guarantees) in addition to solving the problem of learning through label and seed queries with a computationally efficient algorithm whose total query complexity is polynomial in the dimension of the space.\n- The paper is technically sound.\n\nWeaknesses: \n- No experimental results limit the impact of the work.\n- It would be nice to see some mentions of future work and remaining open problems\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "T-lSaR1PRD8", "reviewer": "Reviewer_Z1n9", "summary": "This paper studies active learning of classifiers with margin (assumption of strong convex hull margin), by combining label and seed queries. Using seed queries only, the target classifier can be learned in $\\mathcal{O}(m\\text{log}n)$ -- for a set of n points in $\\mathbb{R}^m$ -- but the algorithm has superpolynomial time complexity. The paper shows that using both label and seed queries, a binary classifier can be learned in $\\text{poly}(n+m)$ time, using $\\mathcal{O}(m \\frac{\\text{log}m}{\\gamma})$ seed queries, where $\\gamma$ is the strong convex hull margin and $\\mathcal{O}(m^2 \\text{log}n)$ label queries. These results are extended for multi-class classifiers with $k! k^2$ multiplicative overhead. The authors also show that the results hold even when only one class has strong convex hull margin, or when input points have bounded bit complexity.", "questions": "The results and some algorithms seem novel, however I am not familiar with the area, so I cannot assess the significance fully. ", "limitations": "The assumptions are stated clearly and there are no negative direct negative societal impacts.  ", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is written and presented well, the assumptions are stated well, and it solves a well motivated issue of efficiently leveraging seed queries, by combining with label queries. It also provides a novel efficient algorithm (CPLearn) for seed which provides the upper bound on seed queries.  \n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Sgzra-umxeN", "reviewer": "Reviewer_4ffc", "summary": "This paper considers learning of k-class classifiers using label and seed queries, where seed queries are special ones that ask for some labeled examples in the specified region. The paper proposes an algorithm which learns the concepts in polynomial time, where the complexity involves convex-hull margin, an extension of margin in linear classes. The paper also shows a lower bound of necessary queries which shows the tightness of the analysis. \n", "questions": "Are there any practical scenarios where seed queries are realizable? ", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n- strong theory paper with a lower bound\n\n\n\nWeakness:\n- no experiments is done", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept