Active Classification with Few Queries under Misspecification
Authors: Vasilis Kontonis
Mingchen Ma
Christos Tzamos
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Active Learning
Label Noise
Linear Separator
Primary area: learning_theory
TL;DR: We study active learning halfspaces under label noise using enriched queries and design the first query-efficient polynomial time algorithm for learning halfspaces under Massart noise model.

Abstract: We study pool-based active learning, where a learner has a large pool $S$ of unlabeled examples and can adaptively ask a labeler questions to learn these labels. The goal of the learner is to output a labeling for $S$ that can compete with the best hypothesis from a given hypothesis class $\mathcal{H}$. We focus on halfspace learning, one of the most important problems in active learning.

It is well known that in the standard active learning model, learning the labels of an arbitrary pool of examples labeled by some halfspace up to error $\epsilon$ requires at least $\Omega(1/\epsilon)$ queries. To overcome this difficulty, previous work designs simple but powerful query languages to achieve $O(\log(1/\epsilon))$ query complexity, but only focuses on the realizable setting where data are perfectly labeled by some halfspace.
However, when labels are noisy, such queries are too fragile and lead to high query complexity even under the simple random classification noise model.
  
In this work, we propose a new query language called threshold statistical queries and study their power for learning under various noise models. Our main algorithmic result is the first query-efficient algorithm for learning halfspaces under the popular Massart noise model. With an arbitrary dataset corrupted with Massart noise at noise rate $\eta$, our algorithm uses only $\mathrm{polylog(1/\epsilon)}$ threshold statistical queries and computes an $(\eta + \epsilon)$-accurate labeling in polynomial time. For the harder case of agnostic noise, we show that it is impossible to beat $O(1/\epsilon)$ query complexity even for the much simpler problem of learning singleton functions (and thus for learning halfspaces) using a reduction from agnostic distributed learning.

Active Classification with Few Queries under Misspecification
Vasilis Kontonis"
Mingchen Ma"
UT-Austin vasilis@es. utexas. edu
University of Wisconsin-Madises mingchen@cs wisc. edu
Christos Tzamos'
University of Athens and Archimedes Al ctzamos@gmail. com
Abstract
We study pool-based active learning, where learner has a large pool S of unlabeled examples and adaptively ask a labeler questions to learn these labels. The goal of the learner to output a labeling for S that can compete with the best hypothesis from given hypothesis class H. We focus halfspace learning, one of the most important problems in active learning.
It is well known that in the standard active learning model, learning the labels of an arbitrary pool of examples labeled by some halfspace up to error requires at least 2(1/E) queries. To overcome this difficulty, previous work designs simple but powerful query languages to achieve O Olog(11/ (1/c) query complexity. but only focuses the realizable setting where data are perfectly labeled by some halfspace. However, when labels are noisy, such queries are too fragile and lead to high query complexity even under the simple random classification noise model.
In this work, we propose new query language called threshold statistical queries and study their power for learning under various noise models. Our main algorith- mic result is the first query-efficient algorithm for learning halfspaces under the popular Massart noise model. With arbitrary dataset corrupted with Massart noise at noise rate 7), our algorithm uses only poly log(1/s (1//)) threshold statistical queries and computes harder case of agnostic noise, we show that it is impossible to beat (11/e) query complexity even for the much simpler problem of learning singletons (and thus for learning halfspaces) using a reduction from agnostic distributed learning.
(17 + -accuraee labeling in polynomial time. For the
Introduction
Obtaining labeled examples is often challenging in applications as querying either human annotators or powerful pre-trained models is cine-consuning and/or expensive. Active learning aims minimize the number of labeled examples required for a task by allowing the learner to adaptively select for which examples they want to obtain labels. More precisely, in pool-based active learning, the learner has to infer the labels of a pool S of n unlabeled examples, and can adaptively select an example S and ask for its label.
Even though is known that active learning can exponentially reduce the number of required labels, this is unfortunately only true in very idcalized settings such as datasets labeled by one-dimensional
Equal Contribution
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

thresholds or structured high- -igh-diinssional instances (e.g., Gaussian marginals) [17, 4, 6,7,3, 19, 23]. well-known that without such distributional assumptions, even for linear classification dimensions, active learning yields no improvement over passive learning [15, 16].
Active Learning with Queries To bypass the hardness results and establish learning without restrictive distributional assumptions [5, 33, 30, 31, 47, 10] introduce enriched queries, where the learner is allowed to make more complicated queries. Broadly speaking. there are two lines of work that study active learning with enriched queries. The first one designs queries based on the structure of the hypothesis class it aims to learn. For example, [33] design comparison queries for learning halfspaces in 2 dimensions, [3 design same-leaf queries for learning decision trees, and [8] design derivative queries to learn polynomial threshold functions. The success of these queries heavily depends on the relation between the hypothesis class and the properties of the queries and thus completely new query language has to be designed if the learning problem gets changed. The other line of work such [5, 10, 44] study mistake- based queries, asking questions like if positive example exists in a given set. These works break down a complicated learning problem into a small number of simple statistical tasks that require only very few rounds of interactions with a labeler who knows the hidden labels and can easily solve these tasks. These learning models can be formally summarized as follows.
Definition 1.1 (Active Learning with Enriched Queries), Given a (multi)set of n unlabeled examples S C X over a domain X, a learner A wants to output a hypothesis i X - {+1} by adaptively submitting binary queries to a labeler who knows the hidden labels of the examples S. Each query q: -2x + {0, } is a function that takes a subset of examples in S together with their unknown labels as input and outputs a number in {0, 13. If fxx) :s + {=1} is the unknown labeling function. the learner aims to make the error of S.
err(f)
[(f(())+ # f(x))
nI
ZES
as small as possible compared to a target class of binary hypotheses H over X.
In the realizable setting where the unknown labeling function belongs to the target hypothesis class H. several non-trivial hypothesis classes including the class of halfspaces have been proven efficiently learnable using only logarithmic number of rounds of interactions. For example, [10] shows for any set S of n examples satisfying 7-margin condition with respect to the underlying halfspace ht, one can use (d log(d/>) seed queries, which returns example with a specified label in given region, to perfectly learn labels of all examples in S efficiently. More recently, [44] shows that for an arbitrary set of examples labeled by an arbitrary halfspace, efficiently learning all the labels only requires Ö(d log(n)) region queries, which ask if an example with specified label exists in a given region.
While these results show that besstake-bssed queries are extremely powerful in the realizable case, they fail to capture most practical cases where there is typically model misspecification or errors in the data. In fact, it is not hard to see that even under tiny amounts of noise, these mistake- based queries become essentially unusable and can be simulated by label queries. For example, if the labels of the examples are flipped with probability 17, say 10% (random classification noise [2]), then region query over a region that contains more than 10 examples will return "yes" with extremely high probability, which provides
information to the learner. In fact, even for the more powerful seed query used in [10], where in addition an example with the specified label is returned, [5] shows that if an algorithm can learn the labels of set of examples S with error 7) + e, with ground truth in a given hypothesis class H corrupted by lelevel random classification noise using (e) queries, then one can simulate such an algorithm using M (e)/nn label queries. Such a result implies even for simple hypothesis classes such as the class of intervals in real line or the class of halfspaces in 2 dimensions, one needs least ((L/e) seed/region queries to learn the labels of examples in a given dataset to error + c. The gap between the realizable setting and the noise setting motivates the following natural questions:
Can we design a simple noise-tolerant query language, that allows learning non-trivial hypothesis classes efficiently with few queries?
Similar to [10, 35), in this work, we focus on the class of halfspaces, one of the most important hypothesis classes in active learning.
2

---

1.1 Learning Model And Our Contribution
We propose a new query language called Threshold Statistical Queries (TSQ), which generalizes the region queries used in [10, 35] and study its power for learning halfspaces under noise.
Definition 1.2 (Threshold Statistical Queries (TSQ)). Let S be a set of examples in domain X' with a corresponding labeling function f S + {+1}. A threshold SQ query g( T) takes as input function 6(x, y) over S x {=1} and a threshold 5 E R, and answers whether E ((z, fx)) 2 т.
TSQ is a simple generalization of region queries and vanilla label queries. For region U ç S and a [+ if 6(x, y) 1(z E U A f(x) a), then q( 1) is exactly the region query, where it checks if at least one example in U has label a E {=1}. Furthermore, if [0] = 1, then
target label
((6, 1) is exactly the classic label queries.
Our goal is to study the power of TSQ for active learning under different label noise models. We consider 3 progressively more challenging noise models commonly studied in the literature: Random, Massart and Adversarial.
Definition 1.3 (Active Learning under Label Noise). Let H be a hypothesis class over domain X. Let S X be a (multi)set of examples and h² E be ground truth function. For a parameter ") E [0, 1/2), the labeling function f() over S is generated in the following way under the three label noise models.
Random Classification Noise (RCN) [2]: For each x E S. f(x) is -hh (x) with probability 1) and h² (x) otherwise.
Massart Noise [41]: For each E S, f(x) = -h" (x) with some unknown probability π((²) S r and h² (z) otherwise.
Adversarial Label Noise: For an unknown subset S' containing 17 fraction of examples from S. [xx = -h" (a:) for all x E S' and [(x) (x:)))) for all x E ES S'.
Given the unlabeled examples S. and error parameter E (0, 1), the goal of the learner is to output a labeling ff over S such that with high probability err(f) S m +
We remark that in our model, after the labeling fxx is generated, the label of each example x e S will be fixed throughout the learning process, also known as persistent noise. This means if an algorithm keeps querying the label of the same example, it will receive the same answer. Furthermore, under the Random classification noise/Massart noise model, we will assume the size of the dataset S is large enough (poly(d, 1/c)), because n is small we have even no guarantee on the error of the ground truth hypothesis. Our main algorithmic result is the first distribution ffree halfspace learning algorithm that achieves both computational efficiency and query efficiency under the (persistent) Massart noise model and the Random Classification Noise model.
Theorem 1.4. Let H = (M(x) = sign(w =)) E 5d-13 be the class of halfspaces over Rd. Given parameters c, 5 E (0, 1), set S of n poly (d, 1/c, log(1/8)) examples in X and TSQ query access to an unknown labeling corresponding to a ground truth hypothesis h" E H corrupted with Massart noise 1) E [0, 1/2), we can compute in poly(n) time a labeling I such that err(f) S + with probability at least 1- - 8, making (dd log (1/c)) threshold SQ queries.
Importantly, unlike [10], make structure assumption over the dataset S, and the query com- plexity of our algorithm qualitatively matches the query complexity obtained by [35], which only holds in the realizable setting. Theorem 1.4 shows sharp separation between standard active learning/region queries which require poly(1/c) query complexity and threshold statistical queries where poly log(1/c) query complexity suffices under the Massart noise and Random classification noise models. Furthermore, we will discuss in Appendix A that the TSQs we use in the algorithm have very simple strictures. A natural question is whether TSQ tolerate more complex noise.
Our second main result is negative result showing that even using TSQ, it is still hard to achieve query efficiency under the adversarial label noise even for simpler hypothesis classes such as the class of singleton and the class of intervals and thus for the class of halfspaces. Formally, we have the following theorem.
Theorem 1.5. Let H be the class of singleton functions over the domain X = N. For every e E (0, and m > (11/e), there is set S of m examples over X and labeling function f for S such that
3

---

any learning algorithm A that makes less than ((1/c) TSQs must output, with probability at least 1/3, labeling function f with error err(f) > opt + where opt = minng err(h).
As can always embed an instance of learning singleton into instance of learning a 2-dimensional halfspace, Theorem 1.5 also implies (2(1/e) query complexity for agnostic learning half'spaces with TSQ. This shows a sharp separation of the performance of TSQ under different noise models and leaves designing more robust query languages as an important future direction. From a technical perspective, unlike usual approaches in the active learning literature which explicitly construct hard instances [16, 28), we obtain our result via reduction from the agnostic distributed learning problem studied by [32] for which communication complexity lower-bound has been established. To the best of our knowledge, this is the first result that connects distributed learning and active learning. two seemingly unrelated learning models.
Though, Theorem 1.5 shows that agnostic learning up to enror opt cannot be achieved in query efficient way, inspired by the work of [5], it is possible to use only O(d (og((/))) TSQ to learn the label of a dataset up to error 0 + e for every hypothesis class with finite VC dimension, though the running time of the algorithm is exponential. Such a result might be of independent interest as how to efficiently learn a hypothesis up to error (opt.) + + have already been studied in many agnostic learning literature such as [13, 14. 221. We leave the proof of Theorem 1.6 Appendix C due to the space limit.
Theorem 1.6. Let X be the space of examples and H. be a hypothesis class over X with VC-dimension
d there is an algorithm such that for every e, E (0, 1), for every set S of n examples, and for every labeling function fx)), it makes (ddogg(1/)) TSQs and outputs labeling f such that with probability 1- 8, err(f) S O(opt) where opt minkee err(h).
1.2 Related Works
Active Learning with Mistake-Based Queries Learning with mistake-based queries has a long history [1, 39, 5, 10]. A typical mistake-based query can be understood as follows. A learner selects subset of examples T X and proposes possible labeling for them a labeler. The labeler will return an example x E T labeled incorreetly by the learner or return nothing when every example in T labeled correctly. Beyond being quite successful theory, mistake-based queries also have wide applications in commercial systems [11, 25). In the realizable setting, it has been well-known that such queries can be used to implement the Halving algorithm [38] and achieve (d (1g(()))) 1c)) query complexity for hypothesis classes of VC dimension d. However, it is only until very recently [10, 35] that people know how to use these queries to design algorithms that achieve both computational efficiency and query efficiency. In the noisy setting, [5] shows that even under random classification noise, it is impossible to use such queries to do query-efficient learning even for very simple classes In this work, we propose TSQ robust generalization of these queries.
Statistical Query Learning Model Close to our threshold statistical learning model (TSQ) the classic statistical learning model (SQ) proposed by [34]. SQ was originally designed to overcome random classification noise but has numerous applications in learning theory literature as refinement of the PAC learning model which captures most algorithms used in practice. It has been used as a tool for obtaining efficient learning algorithms robust to noise [9] and as an evidence of computational difficulty of a statistical problems [21]. In the SQ model, the learner has no direct access to any example but can evaluate the expectation E(g.y)> (xx,, y) for an arbitrary bounded function Φ(x; y) within accuracy 5. This means in SQ model, a learning algorithm should consider both the time used for computing ((z.8) y) but also have to consider the final accuracy. On the other hand, a TSQ is a boolean function of the unlabeled examples and their hidden labels. No matter the complexity. any TSQ. (()) can be computed by the labeler accurately in time at most (n)). Furthermore, as in SQ model, learner has no access to individual examples, SQ learning does not naturally fit in the active learning model. One even cannot implement classic active learning algorithms such as CAL or Halving [27, 28] in the SQ model. As opposed to SQ, our TSQ model is more powerful it can isolate individual examples and thus fills such a gap. We remark that this more powerful type of access is not needed for Theorem 1.4 and can be implemented with SQ queries of poly(e) accuracy.
Learning Halfspaces with Massart Noise Active learning for halfspaces under Massart noise also has a long history. Many works [4, 46, 3, 48] design learning algorithms that achieve both

---

computational efficiency and query efficiency under structured distributions such as the uniform distribution over the unit sphere, the Gaussian distribution, and log-concave distributions. On the other hand, without distributional assumptions, learning under Massart noise is much more challenging. Computationally efficient learning algorithm for learning halfspaces under Massart noise [18, 12, 20] were only recently discovered for passive learning. Our algorithm is the first one that works in an active learning setting and achieves both computational efficiency and query efficiency.
2 Learning Halfspaces under Massart Noise
In this section, we present Theorem 1.4, our main algorithmic result. The full proof is left at Appendix A. To start with, we give a high-level overview of how our algorithm works. Similar to previous works on distribution-fiee free learning halfspaces [9, 18, 35], our learning algorithms recursively run two subroutines over the dataset S. The first subroutine is a weak learning algorithm that works under structured datasets S More specifically, we assume that all points in the dataset have unit norm and for every direction w E 5d there are at least (2(1/d) fraction of the examples x: in S such that |w- ø| 2 ((1/Vd). Intuitively, the regions {ar E S' | |w . x 2 ((1/Vd)) correspond to examples for which halfspacce with normal vector w is more confident about the label. If S contains a non-trivias fraction of examples in S and we can run a weak learning algorithm over S to learn a vector w that has a classification error 1J + over far E 5' I x 2 2(1/va)), we able to label non-trivial fraction of examples in S with a low error. In Section 2.1, will design such a learning algorithm that is robust to Massart noise and achieves query efficiency and computational efficiency simultaneously. However, in general, it is not always possible to find large enough subset from S that is in an approximate radially isotropic position. Forster's transform [26], a powerful preprocessing technique can be used to solve this issue. Given any set of examples in Rd we can always use Forster's 's transform to find a subset of kn/d examples that lie in & dimensional subspace such that after a non- non-linear transformation. the transformed examples are in an approximate radially isotropic position. This implies that if we can implement our weak learning algorithm over the transformed data, each round, we are able to label 1/d fraction of the whole dataset with small error and thus after d dlog((1) /c) rounds of weak learning, only fraction of the examples are unlabeled. In Section 2.2, we will show how to use Forster's transform to select a large fraction of the dataset for the weak learning algorithm and how to implement the weak learning algorithm over the transformed dataset using TSQ. Furthermore, we want to point out that the TSQs we use in our algorithms have very simple structures. We leave the discussion in detail in Appendix A.
2.1 A Weak Learning Oracle
In this section, we present our weak learning algorithm, Algorithm 1, which plays a central role in Theorem 1.4. Our main algorithmic result in this section is the following theorem, the proof of which can be found in Appendix A.
Theorem 2.1. Let V S Rd be a subspace of dimension k and S C V be a set of n poly log,lo (8)) examples with unit length. Let h (x)))) sign(w" . =x),"" E B be the ground truth hypothesis. for every unit vector E Bi, at least 1 1/4d fraction of examples e S satisfy |w x1 2 1/(2/)), and =" 2 1/(4V/), then under the Massart noise model. for every ground truth, with probability at least - 6, Algorithm I outputs ( such that |S') Z n/(4k) and far has error at most 17 + over S using Ó(d log²(1/e)) (1/c)) TSQ, in poly(n, m, k) time.
To understand why Algorithm is robust to Massart noise, we need understand why such problem is difficult. Let S be subset of n example in an approximate radially isotropic position. Take the algorithm in [35] as an example. Such an algorithm uses a modified perception algorithm to learn some w that can perfectly classify all examples that have a large margin with respect to it. Namely, in each round, either the current hypothesis w; perfectly classifies a large fraction of examples or seed/region queries are used to quickly find an example in that region that is misclassified by w;, which will be fed to the perception algorithm and improve w; In the noisy setting, however, every example has constant probability of being misclassified by w;- This implies we need to use queries to find a "point" where w" and w; disagree. To do this, we associate each example x in the region S, = (rr E S |w- x| 2 ((1/Vi)), with a variable Y, E (0, 1}, where Y, = sign(w;- I)) # y(z) and 0 otherwise. If the noise n7(r) 17 for every example i.c. Massart noise
5

---

Algorithm 1 WEAKLY LEARNING HALFSPACES (Labeling 1/d fraction of examples via TSQ)
Input: e, E (0, subspace V C Rd of dimension k, C V n examples with unit length, u,
unit vector in V
Output: S' _ S subset of examples, fs :' + {=1} a labeling for S
Let Po = {or & B u 1. 1/(4vR)), where B is the unit ball in V.
Compute mg Po using Vaidya's 's algorithm by Theorem 2.3.
for 0, .... Okk do
Let wi = / |x:l|
2VK wy has error larger than 77 + e via TSQ If wy has error less than + e over Sw,, return (S sign(w; wy x)) and stop the algorithm Draw a random set U from Sw, of size = (k22/22)
Check if over Sw: - (a ESI [0,
x|
For each Sw.. define
o(x, v) (Yz(v) 7)/(1; xx),
where == = if + sign(w; 2) and Y, = 0 otherwise.
Use ((d) TSQ to do binary searches along each coordinate and find some such that ||e - 1 ExEU Φ(z, y)zl I c/(8k²).
Feed Vaidya's 's algorithm by ((q eu/4)', 0) and compute (P141,
Report Fail if nothing has been returned
model degenerates the random classification noise model, then consider the following point
f Σ (Y - -)= Σ CYn 1) + Σ (Yz (Y,-1)),,
PES.
xES+
xES_
where S+ is the subset of examples in S; where agrees with w² and S_ = S; \ S+. For each 7.. This implies that in expectation, Ei= = (1 2n) ExEs_ After properly scaling, this gives a point in S; where w, and w" disagree due to the convexity of the problem and thus serves counter-example to run the perception algorithm. In particular, since the contribution of each example only depends on its true label, we can draw random samples from S; and use TSQ along each coordinate approximately find F up to high accuracy using very few queries via binary search.
E S+, EY, = 77, while for every I E S_, EY,
However, for Massart noise, this is not the correct way to design learning algorithm. This is because ((x)) is non-uniform over each æ. For simplicity, we assume w; - for each æ E S.. As 77()) S n- a simple calculation shows that Ez w² < O, where the randomness only comes from the Massart noise. The hope that if w; has an error 17 + over S,, then ø wy is larger than some positive number so that we find counter-example n(x) are different, even if the error is large, some of the examples with large margins could force T points to the opposite direction, making F w, I as well. To overcome this issue, we consider using a slightly more complicated statistic here, where we defin
This is unfortunately not true. Because w; x are different and
Σ ZES;
(Ya
1 W, 2
instead. Such point is still easy to approximate up to enror with only d dloo(1/c) TSQs, because it each compute wi x for each S.. But more importantly, when w; has an error larger than + e, in expectation wi and w" will always disagree on F because
1
Σ ZES;
(Ya
I
W.
Σ (Ye - 17 >c>
(I)
IS
S
W.
S
rES;
Furthermore, as w; is large for every z E S,, F has bounded norm and thus can serve counter-example. technical issue here is that the inequality Er w= < 0 is quite fragile, due to the randomness of the Massart noise, it is impossible to guarantee 7 w < 0 actually holds after the labeling being fixed. This issue can be fixed using the following trick. Before run the learning
algorithm, we will randomly sample unit vector We know from [45] that with constant probability

---

2 --=w"= > 1/vd d and thus by shifting T a little towards uu this will give us counter example and guarantee the whole algorithm succeeds with a constant probability.
Though, we find a counter-example and can use it to run a perception algorithm in a similar way to [35], this cannot give which requires to run the perception algorithm for (11/e²) rounds to converge to a good hypothesis. Thus, we will solve this problem using Vaidya's cutting plane method. We want remind the reader of the following convex feasibility problem, which is closely related to our halfspace learning problem.
good query complexity. This is because (1) can only guarantee F ws >> 6,
Definition 2.2 (Convex Feasibility Problem). Let K C Rd be a convex body. A separation oracle with respect to K is a function on Rd such that for any input æ E Rd if E K, then it reports "yes". otherwise it outputs some (c', b) E [ed+1 such that for every y E K, C. 2 b but e. S b. Assuming K S Bd, given a separation oracle with respect to K and e E (0.1), the convex feasibility problem asks to either find some x E K or prove that K does not contain a ball of radius c.
There exists a long line of research for solving the convex feasibility problem for example, [43, 40, 37]. We will use these algorithms as subroutine of our learning algorithm.
Theorem 2.3 (Vaidya's 's Algorithm). Let K C Po S B be an unknown convex body. Vaidya's 's algorithm solves the convex feasibility problem for K as follows. In round i, it maintains a convex body K C P. S Po and a point T4 E P. and sendy T4 to the separation oracle of K. If the oracle returns "yes", then it claims T; E K, otherwise it computes in poly log(1/e)) time pair of (1+1) based (ct, bi) the return of the separation oracle. In particular, after T T= (ddoog(/)) rounds, Pr does not contain ball of radius c.
Let the unknown convex body K that we want to solve for the convex feasibility problem be a ball of radius around w" and we want to run Vadidya's 's algorithm to find some w; close to w,. Consider the P. maintained by Vadiya's algorithm. As with constant probability w" 2 L/vd as mentioned earlier, we can guarantee that 0 & P. Let x; be the point used by Vadidya's algorithm. Then we will check the error of wt; x ||r:|] || over S; is large, which can be done with single TSQ. If the error is less than 1) + e, we are done. Otherwise, we use O( (og(e))) TSQ to approximately find counter example E for wt, Importantly, the halfspace F-- - w 2 0 separate 2; and any w E K. This will make possible to run the next round of Vadiya's algorithm. Since we only care about examples that have margin 12 V with respect to w,, when w, is within ball of radius 1 1/poly(d) centered at w", every example in S; is agreed by w; and w' and thus w; is guaranteed to have error at most 1 + c. Furthermore, in each round, Vadiya's 's algorithm shrinks the volume of P. by a constant factor, and after at most (olo////)) rounds, we are guaranteed to find a good hypothesis. This gives a weak learning algorithm with a desired query complexity.
2.2 From Weak Learning to Strong Learning
We leave the formal analysis of the algorithm Appendix A and discuss two technical issues raised in designing Algorithm 2. First, as required in Theorem 2. the dataset S should be large enough and satisfy the structured assumption. Thus, to run Algorithm 1, we need recursively select dataset of enough size that satisfies the structured assumption from the data we have not labeled. In fact, the structured assumption can be fulfilled by dataset that is in approximate radially isotropic position. Definition 2.4 (Approximate Radially Isotropic Position). Let S be a multiset of non-zero points in RRd, we say S is in e-approximate radially isotropic position, if for every x E S, ||x||| = 1 and for every u. E S Eves(u z)²/|S| 2 1/d-c.
Lemma 2.5. Let S be a multiset of non-zero points in Rd that is in 1/2d- radially isotropic position. Then for every u E 5d-1, we have Pra-s (Iu 2 1 1/2vd) 2 1/4d.
Recent results show that for any dataset S, one can efficiently find a non-trivial fraction of the data and a non-linear transformation such that after the transform, the data are in approximate radially isotropic position.
Theorem 2.6 (Approximate Forster's Transform [24]) There is an algorithm such that given any set of points S C Rd \ {0} and >> O, it runs in time poly (d, n, log 1/c) and returns subspace V of dd containing at least dim(V) d fraction of points in S and invertible matrix A E gdxd such
7

---

Algorithm 2 STRONG LEARNING HALFSPACES (Label S with few queries up to 17 + error)
Input: e, 8 e (0, (), S
Rd of n examples
Output: f5 + } a labeling for S
L < 0. n < ||]
while S) > e do
Apply Theorem 2.6 to S with 1/2d to obtain matrix A and k-dimensional subspace V Use a single TSQ to check if constant hypothesis +1(-1) has error 1/ + e over n
if constant hypothesis has error at most + e/2 over S n V then
Define / to be the constant over S' = SSV
S S
else
Run Algorithm over input parameter e/ e/2, log(L/)), V, fA(S n V) and random unit vector u E V until some (S", fsr) is output.
> Though Algorithm is run over the transformed dataset fA n V), each TSQ can be
simulated over the original data Fa(x) preserves the ground truth label.
Define f(x) = fs (F)()), Vx, Fx(x) S
S x-=b S \ S"
Define f == 1 for the rest of en/2 examples in S
return
that FA ()(S is in e-approximate radially isotropic position up to isomorphic to gddm(v), where FA(S = (Fa(x)
|| SnV).
Combine Theorem 2.6 and Lemma 2.5, we know that given any set of examples S C Rd, can find a subset of at least kn/d examples Sv := Sn C S that lies in some k-dimensional subspace V and some invertible matrix A such that F' (Sv) is in 1/2k-approximate radially isotropic position (up to isomorphic to R²*, Now, for convenience, we assume our transformed data FA (Sv) is exactly our original dataset and we focus on the transformed data. Notice that for each x E Sv, we have
sign(w' 2> Sign(A-Tus Ar) Sign(A-Tur Fa(x)) sign(proj (A- w=) fa(x)),
which implies that each transformed example (a is labeled by halfspacc V = (rojA(V) (A-T "w=) and has the same label æ. So, we use Algorithm I to learn their labels. However, as Algorithm 1 is run over the transformed data, we have to simulate every TSQ used by the algorithm via a TSQ over the original data. This issue can be overcome using the following argument. Since FA is bijection between x and (1)) and the outcome of the function ø(x, y) used in a TSQ for each example x can be uniquely represented by two numbers, we can rewrite of (1), y) as a function of for each (x such that for a TSQ as long as y (F)( = f(x), the result of the query will be the same. This gives us a way to simulate the TSQ over S.
3 Agnostic Learning with Threshold SQ
In this section, we study learning with TSQs under the more challenging adversarial label noise proving Theorem 1.5. In the previous section, we saw that using TSQ, learning halfspaces only requires polylog(1/) (1/)) /c) rounds of interactions. We show in this section that this is not the case for the adversarial label noise. We show that it is impossible to reduce the query complexity from poly (1/c) to polylog(1/c) even for very simple classes such the class of singletons (and thus the class of the halfspace in high dimensions). The classic method of proving query complexity lower bound [15, 16, 28] is construct hard instance directly. However, there are infinite types of TSQs be considered, it is impossible to construct a single hard instance that defeats all types of TSQs. Instead, we will build a reduction from a hardness result on agnostic distributed learning [32] that we define as follows.
Definition 3.1 (Agnostic Distributed Learning). Let X the space of examples. Let a, b be two learners and S =< Sa. Sa, > be a collection of labeled examples, where S. is the (multi)set of labeled examples owned by a and S, is the (multi)set of labeled examples owned by a, b only knows their own sample set. A learning protocol is communication strategy, where in each round of
8

---

communication a sends information by bits to b and after reviving information sent from a, b sends information by bits back to and finally the learning protocol outputs hypothesis f X - { {+1}. The error of f is
1 E1(((() + f(x)), err(f)== = [S| -ES
where (x) is the true label of s. Let S be collection of labeled examples, and H be a hypothesis class, Given an accurate parameter E E (0,1), the goal of the agnostic distributed learning problem is to design a learning protocol that oulputs some f such that err(f) S minune err(h) + while minimizing the number of bits communicated in the learning protocol.
In this paper, we will make use of the following slightly easier problem of agnostic distributed learning singleton functions, where the unlabeled examples owned by a, b are known to each other and they want output labeling with error at most opt.
Problem 3.2 (Distributed Learning Singleton). Consider the agnostic distributed problem. Let =< Sa. S. > be a collection of examples, where for u E {a, 6]. S. = {(i. y Vi where 3h E {=1} for [m]. Let H {h,(x) 21(z = - i NJ be the class of singleton
functions. The goal to design a (randomized) learning protocol that outputs hypothesis ff succh that err(f) S minne err(h) + for e = 1/An with probability at least 2/3.
[32] shows the following hardness result for Problem 3.2.
Theorem 3.3 (Lemma 3 in [32]). If there is (randomized) learning protocol that can solve Problem 3.2 using T(n) bits of communication, then there is (randomized) protocol that can solve the set-disjoinmess problem with T (n)) log(n) bits of communication.
According to [29], solving the set disjointness problem requires Q(n) bits of communication, and thus solving Problem 3.2 requires (()) (((1e) bits of communication. The central result we use to prove Theorem 1.5 is the following technical lemma, which means if one can agnostically learn the class of singleton functions with error opt using (n) queries, then one can design a learning protocol for Problem 3.2 with (olyoo)))))))) bits of communication. This enough to prove Theorem 1.5, because given the hardness of Lemma 3.4, we can create hard problem by making multiple copies of each example used in the proof of Lemma 3.4. This preserves the error of every hypothesis h : X' - [+1]. We leave more details to Appendix B and in the rest of this section, we give an overview of the proof of Lemma 3.4.
Lemma 3.4. Let S C N be a multiset of 2n examples and f(z) be hidden labeling function. Let H = (h,(x)= = 21 = i) - 1 E N} be the class of singleton functions. If there is an algorithum A that can make [')) TSQ and outputs some f such that err(f) I minneH err(h) + e, with e = 1/4n. then there is a learning protocol that can solve Problem 3.2 with ((T (olyyllog())) bits of communications.
Consider A to be a learning algorithm for singleton functions that can learn up to error opt with T(n) queries. Since both a, b know the unlabeled examples owned by each other and know the labels of examples owned by themselves, we will design a learning protocol for a, b to check the answer to each TSQ used by A together using only polylog(n) bits of communication. Recall that in the definition of TSQ. each answers if Exss Φ(x, y) 2 where o(x, y) given every x is two- two-value function. Thus, to check the answer of qú it is sufficient to check if Exes, Φ(I, v) 2 ----X - Exes, Φ(x, y). One possible way to check the answer is to let send the number Lmes, ő(I, 3) to b. However, if a TSQ very complicated, communicating such number would cost too many bits. Two arguments are made to address this problem. First, we claim that we can assume every outcome of Exes, Ø(x, v) and T - - o(z, y) is an integer with bit complexity n. Intuitively, this is because there are at most 2n different outcomes for Ezes. Φ(2, y) and r Exes, Φ(x y) and we can explicitly create a map from each outcome to such an integer. Second, we show that to compare pair of integers with bit complexity only polylog(n) bits of communication are required. To see why this is true, we can expand integers I, = Exes, Ø(z, y) and I, = T Enes, ((x, y) into binary strings. Then I, Ib if and only there exists some index i such that (Ta) = (Is) for each j > i but (Ta), > (Tb); for each j = i. Thus, to compare la. Lb only need to binary search the first index j such that the

---

partial binary strings of la. 1o are different. Since checking whether two binary strings are equal only requires (loog n) bits of communication, we only need Ollog² n) bits of communication to compare the two integers.
Acknowledgments
This work was supported by the NSF Award CCF-2144298 (CAREER).
References
[1] D. Angluin. Queries and concept learning. Machine learning, 2:319-342, 1988.
[2] D. Angluin and P. Laird. Learning from noisy examples. Machine learning, 2:343-370, 1988.
[3] Awasthi, M. Balcan, and P. M. Long. The power localization for efficiently learning linear separators with noise. Journal of the ACM (JACM), 63(6):1-27, 2017.
[4] M.-F. Balcan, A. Broder, and T. Zhang. Margin based active learning. In International Conference on Computational Learning Theory, pages 35-50. Springer, 2007.
[5] M. F. Balcan and S. Hanneke. Robust interactive learning. In Conference on Learning Theory, pages 20-1. JMLR Workshop and Conference Proceedings, 2012.
[6] M.-F. Balcan and P. Long. Active and passive learning of linear separators under log-concave distributions. In Conference on Learning Theory, pages 288-316. PMLR, 2013.
[7] M.-F. F. Balcan and H. Zhang. Sample and computationally efficient learning algorithms under s-concave distributions. Advances in Neural Information Processing Systems, 30, 2017.
[8] O. Ben-Eliezer, M. Hopkins, C. Yang, and H. Yu. Active learning polynomial threshold functions. Advances in Neural Information Processing Systems, 35:24199-24212, 2022.
[9] A. Blum, A. Frieze, R. Kannan, and S. Vempala. polynomial-time algorithm for learning noisy linear threshold functions. Algorithmica, 22:35-52, 1998.
[10] M. Bressan, N. Cesa-Bianchi, S. Lattanzi, A. Paudice, and M. Thiessen. Active learning of classifiers with label and seed queries. Advances in Neural Information Processing Systems, 15:30911-30922. 2022.
[11] E. Chang, S. Tong, K. Goh, and C. Chang- Support vector machine concept-dependent active learning for image retrieval. IEEE Transactions on Multimedia, 2:1-35, 2005.
[12] S. Chen, F, Koehler, A. Moitra, and M. Yau. Classification under misspecification: Halfspaces, generalized linear models, and connections to evolvability. arXiv preprint arXiv:2006.. 04787, 2020.
[13] A. Daniely. A ptas for agnostically learning halfspaces. Conference on Learning Theory, pages 484 502. PMLR, 2015.
[14] A. Daniely, Complexity theoretic limitations on learning halfspaces. In Proceedings of the firtt-eighth annual ACM symposium Theory of Computing, pages 105-117, 2016.
[15] S. Dasgupta. Analysis of greedy active learning strategy. Advances in neural information processing systems, 17, 2004.
[16] S. Dasgupta. Coarse sample complexity bounds for active learning. Advances in neural information processing systems, 18, 2005.
[17] S. Dasgupta, A. T. Kalai, and C. Monteleoni. Analysis of perceptron-based active learning. In Learning Theory: 18th Annual Conference on Learning Theory, (01.T'2005 Bertinoro, Italy, June 27-30, 2005. Proceedings 18, pages 249-263. Springer, 2005.
10

---

[18] I. Diakonikolas, T. Gouleakis, and C. Tzamos. ceeribution-indeeedden pac learning of halfspaces with massart noise. Advances in Neural Information Processing Systems, 32, 2019.
[19] I. Diakonikolas, D. Kane, and M. Ma. Active learning of general halfspaces: Label queries vs membership queries. In The Thihty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[20] I. Diakonikolas, D. Kane, and C. Tzamos. Forster decomposition and learning halfspaces with noise. Advances in Neural Information Processing Systems, 34:7732-7744, 2021.
[21] I. Diakonikolas, M.M. Kane, and A. Stewart. Statistical query lower bounds for robust estimation of high-dimensional gaussians and gaussian mixtures. In 2017 JEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 73-84. IEEE, 2017.
[22] I. Diakonikolas, D. M. Kane, and A. Stewart. Learning geometric concepts with nasty noise. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1061-1073, 2018
[23] I. Diakonikolas, M. Ma, L. Ren, and C. Tzamos. Fast co-training under weak dependence via stream-based active learning. In Forty-first International Conference on Machine Learning. 2024.
[24] I. Diakonikolas, C. Tzamos, and D. M. Kane. A strongly polynomial algorithm for approximate forster transforms and its application to halfspacc learning. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing. pages 1741-1754, 2023.
[25] S. Doyle, J. Monaco, M. Feldman, J. Tomaszewski, and A. Madabhushi. A class balanced active learning scheme that accounts for minority class problems: Applications to histopathology. In OPTIMHisE Workshop (MICCAI), pages 19-30, 2009.
[26] J. Forster. A linear lower bound on the unbounded error probabilistic communication complexity. Journal of Computer and System Sciences, 65(4))612-62 2002.
[27] S. Hanneke et al. Theory of disagreement-basse active learning. Foundations and Trends@ in Machine Learning, 7(2-3):131-309 2014.
[28] S. Hanneke and L. Yang. Minimax analysis of active learning. J. Mach. Learn. Res., 16(1):3487- 3602, 2015.
[29] J. Håstad and A. Wigderson. The randomized communication complexity of set disjointness. Theory of Computing, 3(1:2211-219 2007.
[30] M. Hopkins, D. Kane, S. Lovett, and G. Mahajan. Noise-tolerant, reliable active classification with comparison queries. In Conference Learning Theory, pages 2906. PMLR, 2020.
[31] M. Hopkins, D. Kane, S. Lovett, and M. Moshkovitz. Bounded memory active learning through enriched queries. In Conference on Learning Theory, pages 2358-2383 PMLR, 2021.
[32] D. Kane, R. Livni, S. Moran, and A. Yehudayoff. On communication complexity of classification problems. In Conference on Learning Theory, pages 1903-1943. PMLR, 2019.
[33] D. M. Kane, S. Lovett, S. Moran, and Zhang. Active classification with comparison queries. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 355-366. IEEE, 2017.
[34] M. Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM (JACM), 45(6):983-1006, 1998.
[35] V. Kontonis, M. Ma, and C. Tzamos. Active learning with simple questions. arXiv preprint arXiv:2455.07937, 2024.
[36] Lee, A. Shraibman, al. Lower bounds in communication complexity. Foundations and Trendy in Theoretical Computer Science, 3(4):263-399, 2009.

---

[37] Y. T. Lee, A. Sidford, and S. C.-w. Wong. A faster cutting plane method and its implications for combinatorial and convex optimization. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 1049-1065. IEFE, 2015.
[38] N. Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine learning, 2:285-318, -18, 1988.
[39] W. Maass and G. Turán. Lower bound methods and separation results for on-line learning models, Machine Learning, 9:107-145, 1992.
[40] W. Maass and G. Turán. How fast can threshold gate learn? In Proceedings of workshop on Computational learning theory and natural learning systems (vol. 1): constraints and prospects: constraints and prospects, pages 381-414, 1994.
[41] Massart and E. Nedelec. Risk bounds for statistical learning. Ann. Statist, 3465):2326-2266, Oct. 2006.
[42] T. Roughgarden et al. Communication complexity (for algorithm designers). Foundations and Trends in Theoretical Computer Science, 11(3-4):217-40 2016.
[43] M. Vaidya. A new algorithm for minimizing convex functions over convex sets. Mathematical programming. 2313)319,-341, 1996.
[44] K. Vasilis, M. Mingchen, and Christos. Active learning with simple questions. In Agrawal and A. Roth, editors, Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 3064-3098. PMLR, 30 Jun-03 Jul 2024.
[45] R. Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018
[46] S. Yan and C. Zhang. Revisiting perceptron: Efficient and label-optimal learning of halfspaccs. Advances in Neural Information Processing Systems, 30, 2017
[47] G. Yona, S. Moran, G. Elidan, and A. Globerson. Active learning with label comparisons. In Uncertainty in Artificial Intelligence, pages 2289-2298. PMLR, 2022.
[48] C. Zhang and Y. Li. Improved algorithms for efficient active learning halfspaces with massart and tsybakov noise. In Conference on Learning Theory, pages 4526-4527, PMLR, 2021.
12

---

Supplementary Material
A Omitted Proofs and Discussions in Section 2
A.1 Proof of Theorem 2.1
Proof of Theorem 2.1. Since u w² 2 1/(4/B), we know that w² E Po. furthermore, K p/ooyy((k)
Bk (e)oly(s)(w)) (w)) n Po contains ball in V with radius least c/poly(kk. In particular, 0 g Po. We will first show that every time Algorithm computes ((c: - =u/4),, 0), it separates 2; and K.
implies that wy misclassifies According to Algorithm 1, we know that when ((G: - u/4)', (0) is computed, must be the case where Ez-S., Y, 17 + We remark that
For given round in Algorithm 1, for every
S, Y2
single TSQ to check if EgwS.. Y2 2 n by querying if the number of mistakes made by w; over S.;; is larger than (n + w)
Since U is random subset of Sw: with size = =O(k/e²)) by Hoeffding's inequality we know that with probability at least 1 - poly()), 1 m ExEU Y, 2 rj + c/2. We first show that given this happens, 6 := J. ExEU Φ(z, y)æ must have large correlation with wg. We have
(Y,(y) - n)
G c. w. = 171
Σ o(r,y)x w. DEU
Σ DEU
(x (.:w)) m.
E(G(()) - 210)220 e/2,
m
(wi x)
ZEU
where in the last inequality we use the fat that 1 ExEU Y, 2 n c/2. On the other hand, we show that with high probability, 1 Ezev 6x y)v w² S <2/220/)). To see this, we first consider any fixed E S. If sign(w; x)) = Sigg(ww": .r), then under the Massart noise model, in expectation we have
me
(v) 11 (w- xx)
nTx)= (w- x) O. (wi x)
E plx v) w"
E v(*)
v(x)
(w; .T)
Similarly, if ( x) + sign(w" x)) then
E oa. - E (v) (w" x)) 1 - n[x) ((a))
(w² x:) 5..
((z) (w; x)
(wv x))
Thus, for any possible subset U S S, it always holds that 1 EvEU By(o) 6(x, y) w S O, where the randomness comes from the Massart noise model. In Algorithm each U satisfies lwl x 2
10,c
1/(4v/). This implies that always holds for each x U that 6(2; y)z ww/cee /CE (-AVk/e, 4Vk/c). Since U is random subset of k:2 e22 examples from Swp by Hoeffding's 's inequality, we have
Pr 1
Σ
((x,y)a w"
Σ ZEU
E Ólz, D) w v(a)
expl
ém
$ 1- poly(1))).
MI
me
20
12
ZEU
Thus, with high probability & w= S < (200/)).
Notice that for each coordinate j. |, S Av Along each coordinate j. we are able to use TSQ
of the type To.o EveU Φ(x, (x);; 2 T to binary search Gy up to error e/(8k²) in (llog(k/e)) s
Olog(dd/e) rounds of interactions. Since have found ||e alloc I c/(8k3) we know that
G w; 2 G. w; c/(8k) c/2 </(8k) 2 3c/8
G -.w== < & w" + </(kk) < e/(20Vk) + (/k)) <e((1V)))
However, & itself cannot separate z; from K as it could be the case that both q =" and c, wy positive. However, since =" > 1/(4vk) k) and ||ul| 1, G eu/4 can separate w; from K. This can be viewed as follows. On the one hand,
(c: eu/4) w; 2 4 - 4/4 2 e/8 O, which means (a: -ue/4) m; > 0. On the other hand, for every E K, we have
(c, cu/4) < (c: ccu44) "² + c/poly(kk) < </ 1 </(16Vk) + c/poly(k) < 0.
13

---

As long as Algorithm 1 computes (c: - particular, by Theorem 2.3, we know that after T = Ö log((/)))) rounds, any point in Pr must be at most e/poly(oog1//e close to w This implies that over Swn = {xr S |wrr- 2 (2(2))), wr and w" agrees every single example in Sey- Thus, after Ó lok(lo(11//) ((/oo((())))))) /c)) rounds, Algorithm 1 is guaranteed to output some ti such that we has an error at most v + c over the region Sw.- By our assumption, Sw: has size at least n4k)). This proves the correctness of the algorithm.
(Gs-cu/4) cu/4), with high probability it will separate from K. In
Finally, we compute the query complexity of the algorithm. In each round of Algorithm I, we use I TSQ to check if the current hypothesis is good enough and use Ö (odloo((//)) TSQ to find a good approximation of the separation hyperplane. Since there are at most O log(1/c) rounds, the query complexity of Algorithm 1 is (d log" (1/6))
A.2 Proof of Theorem 1.4
Proof of Theorem 1.4. We start by showing the correctness of Algorithm 2. We will show that in each round of Algorithm 2, |S') 2 |SI/d and f over S has error at most 1) + c/2. Given this to be correct, after at most log((/)) rounds, Algorithm 2 labels (1 </2) fraction of the examples with error of n + c/2, leaving at most c/2 fraction of the examples unlabeled. This means f has error at most + e.
By Lemma 2.5 and Theorem 2.6, we know that in each round of Algorithm 2, we can compute we find a subspace V that contains k/ d fraction of the unlabeled data in S and a matrix A that can make (S O V) in approximate radially isotropic position. If w" I V, then the ground truth labels of examples in S in V are the same and thus with high probability a constant hypothesis achieves an error of at most 7 + e over S E V.
Now we assume w" is not orthogonal to V and we will show that by running Algorithm 1 ((lg((10)) times, we are able to label S' C SS V, a subset of at least 1 //k-fraction of examples in S n V with етrоr at most + e. To see this, we first argue that labeling S n V is equivalent to labeling the transformed data (S V). We notice that for every I V. we have
sign(w" x) = sign A -T "w" Ar) = sign(A """"
-F())) sign(proixnv)(A" ww" -x)()))
which implies that we can view (V) to be labeled by halfspace o- = (r (A- w²) furthermore, and (x(x) have the same ground truth label. If we associate (x)) f(x) for each x E V. then the label ((F((z) of (z( can be seen as created by halfspace sign(o* x) under the Massart noise model such that (=))(=)) subset (S' n V) S FA n V) and label examples in FX(5" n VV) up to error 17 + c/2, then are able to label the labels of the corresponding examples in S' up to 17 + c/2. We will use Algorithm to do this. Since FA n V) are in approximate radially isotropic position, we know from that Lemma 2.5 that for every unit vector w V, at least 1/(4k) fraction of examples in (A n V) satisfied [x) w| 2 1/(2/K). Thus, once Algorithm 1 outputs a labeling fs: for S' S FA n V). the size of S' is at least (A n V)I/(4k) 2 [S)/(4d) and the error of fs must be most 77 + c/2. By Theorem 2.1, need some unit vector that has non norviaivial correlation with the target halfspace A for the transformed data. By randomly select a unit vector in V, with constant probability (see [45]), we can guarantee that u projA(vy (4- (A-Tui) w²) 2 1/(4V/). Thus by repeating Algorithm several times, with high probability, it will output some labeling function. However, to run Algorithm 1, we have to implement TSQ over the transformed data while we can only make TSQ over the original data. Such an issuc is easy to address. Since FA is a bijection between x and FA (x) and the outcome of the function Φ(z, y) for each example x can be uniquely represented by two numbers, we can rewrite oi (F))). y) as a function of x for each (x such that for TSQ as long as ((FA(a))
n7xx,, Vz. Thus, if we are able to find
f(),, the result of the query will be the same. As have mentioned that (FF (x)) = f(x holds for every example, we conclude that we can simulate each TSQ over the transformed data via TSQ over the original data. This finishes the proof of the correctness of Algorithm 2.
Finally, we calculate the query complexity of Algorithm 2. By Theorem 2.1, we know that every time we run Algorithm/ 1, we make Ō log" (L(e)) queries. Since every round of Algorithm 2, we run
14

---

Algorithm 2 (l)og()/e) rounds and there are at most O(dlog(1/e) rounds, we conclude the query complexity of Algorithm 2 is Od log"(1/<)) ) In particular, by Theorem 2.6 and Algorithm 1, each subroutine of the algorithm can be implemented in polynomial time, we conclude that Algorithm can be run in polynomial time.
A.3 On the TSQs Used by Algorithm 2
In this section, we want to discuss the TSQs used by Algorithm and argue that these TSQs have simple structures and are easy to communicate and implement. There two types of TSQs used by Algorithm 2.
First, the algorithm needs to check whether hypothesis h = sign(w x>) has an error larger than r over a given region U. In other words, we want to use TSQs to approximate the conditional expectation, E,, (siinn(w x) + f()) E U). To express this using TSQ, for each E U, we define Φ(x,)) y) = I/|U| if sign(w 2) A y and otherwise. For each x E S U, we define ((x, = O. In particular, in Algorithm each U we use is just some random samples drawn from sn fxr V [Fa( wel 2 (2(/vV))) To communicate such TSQ. learner only needs to communicate such query, a learner only needs to communicate to the labeler, (v, A), the parameters for Forster's transformation, w, the hypothesis maintained by the algorithm, t, the threshold used by the TSQ and a random seed to guide the labeler to do sampling. The labeler receives these parameters, computes the answer the TSQ, and returns binary answer the learner.
The second type of TSQ can be seen as a weighted sum of the mistakes made by the current hypothesis h over a region U. Recall the notation used in Algorithm 1, (Y, (v) 7) (wx 22), where (z) if makes a mistake at z. The algorithm wants to approximate the point E (FFFF (F))) - n)/(w, Fx(x)) x U), which is equivalent get approximation of the point from each coordinate. Similarly, every U used by the algorithm is a random set sample from $ n fxr E V FFx) w| 2 (0/v/)). To communicate such a query, a learner will communicate (v, A). the parameters for a Forster's s transformation, w. the hypothesis maintained by the algorithm, i, the coordinate the learner want to approximate, the threshold used by the TSQ and a random seed to guide the labeler to do sampling.
This shows that the TSQs used by Algorithm simple from both a computational view and a communication complexity view.
B Omitted Proofs in Section 3
B.1 Proof of Lemma 3.4
Proof of Lemma 3.4. Notice that the learning algorithm A can be described follows. In round i, A constructs a TSQ qi (possibly using randomness), submits di to the labeler, and receives the answer to qu Given A, we will design learning protocol as follows. In round the learner a, b will check the answer of together by sending bits to each other and construct the next TSQ qi+1 based on the answer and using A. If they use only K ((n) bits of communication check qi each round, then since A will output some h such that err(j S minseh err(h) e after T(n) rounds, the total bits of communication is at most 7 [(n)K( (n.)
We can without loss of generality assume the randomness used implement A is public so that in each round, both and b know exactly the TSQ 9:- Otherwise, by Newman's 's theorem [36], we only need to use another (log n) bits of communication by A. Recall that in the definition of TSQ, each 9i answers if Σres Φ(x y) 2 т, where o(x, v) two-value function. Thus, check the answer of 9;s is sufficient check if Exes, 6(x,1) v) 2 T Exes, d(0, v). Although can compute Exes. Φfxr, y) and sends the number to b, communicating single number ExEs, 6(x, y) might need lot of bits of communication. In
simulate the randomness used
given every
the rest of the proof, we will design protocol that use only O(log² n) bits of communication to check the answer of q:
15

---

First, we show that we can without loss of generality assume every outcome of Σ veS. ő(z, y) and Exes, Ö(æ, y) is an integer with bits complexity n. We observe that both Z Φ(x, v) and ErEs, o(x,,) v) have at most 2" outcomes. As and b all know all possible outcomes, they can explicitly construct a maps Fa, which maps each of the possible outcomes of > Exes, 6xx v) to an integer between O and 2 - and a map Fb. which maps each of the possible outcomes of Exes, 6(2, y) to an integer between 0 and 2 - 1. Given these two explicit maps, if and b can communication to learn Fa(Enes, ((2, y)) and Fo(T Ezes, 6(x,, y)), then they can reconstruct Exes, ((z, 8) and Exes, 6(x, y). In the rest of the proof, we prove based on this assumption.
Next, we design protocol that uses O(log" n) bits of communication. After a determine Eges, o(x.y) y), a know an integer La such that I, = -T--E Φ(2, y) > Exes. (xr y) if and only if Is > Ia- So remains to show that given two integers Las In with bit complexity n, we are able to compare these two integers with (llogn) n) bits of communication. To do this, we first represent Ja, Io by binary strings of length n. Notice that Ia > To if and only of there exists some index i such that (Ta); = (Tb) for j > but (Ta); > (Tb) for j = i. This implies that to compare T, and J it is sufficient to find the largest index 1" such that (T,), compare (La);- and (4)).. Such an index can be found via binary search. Specifically, given i we want to check if (La) = (lt), for each j < i. If the two partial binary strings are equal, then we decrease i, otherwise we increase i. After O n) rounds, we successfully find such an index i" It well-known that checking the equality of two binary strings of length n can be done via a simple randomized protocol by communicating Oloog n) bits [36, 42]. Thus, in total, with Ollgg* n) bits of communication, we are able to compare La, 1b and thus can check the answer of the TSQ
(J)), for each j > i" and
This gives a randomized learning protocol that uses ( log? (n)) bits of communication.
B.2 Proof of Theorem 1.5
Proof of Theorem 1.5. Let E 1). For simplicity, we write c 1/4n and let S be multiset of 2n examples over N. Given any labeling function f() over S and every m 2 22 such that m/ m²/2n) an integer, we create a multiset S' of size m in the following way. For each æ E S we create m/(2n) copies x' for x such that for each copy x' it has a hidden label equal to f()). Denote by f' the labeling function over S'. Notice that for every hypothesis h - {=1], the error of over S' and the error of h over S are the same. This implies that if we have a learning algorithm such that for every S' S N and every labeling function f', it can output a hypothesis f using T(1e)) = T(4n) TSQs such that with probability 2/3 f has an error opt + e. then f has an error at most opt + e over the original dataset S. By Lemma 3.4, we know that this implies a learning protocol that solve Problem 3.2 with O (c)) log (1)e)) = (T((4)) log2 (n)) bits of communication. By Theorem 3.3, this implies communication protocol that solves the set disjointness problem of size n using (1((1/) that to solve a set disjointness problem of size n. any (randomized) protocol has communication complexity of (n)). This implies that T(1/e) = ((1/c).
(T log" (n)) bits of communication. By [29], we know
C Proof of Theorem 1.6
In this section, we prove Theorem 1.6 by presenting the following Algorithm 3. Our algorithm is inspired by [5], where they design an algorithm that learns a hypothesis class H with finite VC dimension up to error O(opt) + using O(dlog(1/e) class-conditional queries, which returns an example with a specified label in a given region. Unlike their algorithm, our algorithm does not need such a strong query. Instead, our algorithm makes O(dlog log(1/e) (1/e)) TSQs to achieve the same guarantce. Furthermore, each TSQ used in Algorithm only checks if a given hypothesis has an error larger than some threshold over given region.
Proof of Theorem 1.6. If opt < the learning up to error ((ppt) + e is equivalent to learning up to error O(e) and v) = e can be used as an upper bound for opt. So, we assume that v = opt 2 c, because we can always guess some 77 such that 11/2 < opt S 77 via doubling trick, which will only
16

---

Algorithm 3 APPROXIMATE AGNOSTIC LEARNING(Learing a labeling up to ((opt) error)
Input: Dataset S of size hypothesis class H with VC dimension d, 17, upper bound of opt Output: f. a labeling of S
Let Ho be an c-cover of the hypothesis class H with respect to the uniform distribution over 5
Let J'H, be labeling over S. For each x E S, J (xr) agrees with the majority of Ho æ.
Use a single TSQ to check if the error 7/0 of [Ho over S is larger than (
If no < (n)) output JHo
while the error of fH, larger than (1)) do for j L. T (l(og(1/0)) do
This can be checked with single TSQ
Keep drawing random subsets S, of size 1/(50n) from S until Sj gets accepted
We accepted S; if we find least example S, are misclassified by fH, using a single
TSQ
if More than 1/6 fraction of the hypothesis in H, agrees with fH, over Sy then Mark all the hypothesis in H; that agrees with with fH. over Sj
else
Find subset of $; C S₁ such that (-fraction of the hypothesis in H; agrees with J', over Sy where [1/6, 2/3].
Use a single TSQ to check if over $,. fH, makes no mistake. If so, mark all hypotheses that disagree with fH, at any single example over Sj. otherwise mark the hypothesis in H; agrees with JH, over Sj
Remove all hypotheses in H; that are marked more than 0.1T times and H441 be the set of remaining hypothesis
return fH.
make the final guarantee worse up to a constant factor. Denote by ht E Ho the hypothesis that has the smallest error over S. By the definition of c-cover, we know that err(h") S +
We show that with high probability, in each round of Algorithm 3, either err(h is at most 250m or a constant fraction of the hypothesis in H; gets removed. In particular, we will show that ht" will always stay in H, and thus after (o ())) rounds, we are guaranteed to output some hypothesis with small error.
Assume that err(hw,) > 250y. We say a set Sj is good contains no example x such that ht (x) # probability is good.
(x). We first show that given a set Sj accepted by Appendix C, with non-trivial
Pr (Sy good and Sy is accepted)
Pr (S, is good S, is accepted)
Pr (S, is accepted)
2 Pr (S, is good and S, is accepted)
2 1 - Pr (S, is not good) - Pr (S, is not accepted).
Since the noise rate is y,, we know from the definition of e-cover that h has an error at most 2n,. This implies that in expectation, random Sy contains 1/25 example that is misclassified by h².
Pr (Sj is not good) Pr (S, contains example misclassified byh*) 1/25 0.04.
On the other hand, since err(h > 250%, random example has probability at most 1 1/ 1250m) not misclassified by hy; and this
(S, is not accepted) < (1 - 1/(25)))) <e- 0.01.
Thus, with probability of at least 95%, an accepted set Sj is good. In particular, h" misclassified no example S., This implies that h" will not get marked when Sy is good. And thus in expectation, h" will not get marked for more than T 7/20 times. By Hoeffding's inequality, this implies with high probability h² will not get removed from H,. On the other hand, for every S, that gets accepted more than 1/6 of the hypothesized in H,, must get marked, To show this, we consider two cases. In the first case, more than 1/6 fraction of the hypothesis in H, agrees with fH; over Sy. In this case, according to Algorithm 3, all hypothesizes in H, that agree with fH. over Sy will get marked and more than
17

---

1/6 fraction of the hypothesis in H; will be marked. In the second case, we show that there must be a subset of S, S, such that E-fraction of the hypothesis in H; agrees with fH, over Sj. where & E [1/6, 2/3]. We order S, in an arbitrary order æ1, ,,, where m = |S For each t [m]. we use H to denote the set of hypothesises in H; that agree with hı,, for 21, 21,..., Lt. From the above discussion, we know that | S |6 On the other hand, we know by the definition of ha, that |H(] 2 | If [ S //3, then we are done, Otherwise, there must be largest 1" such that | most //2 hypothesises in H; will disagree with hg, over D4+1 and will get deleted from H²(*) This implies that we can choose S, = {II..... Fc-11) Given this, whether hH, makes mistake over S, or not, least 1/6 fraction of the hypothesis will be marked.
1 2 /333 We claim that |H//6 & |H((**)) S / This is because at
We next use this fact to show that in each round, a constant fraction of the hypotheses in H, will be removed. Assuming that c-fraction of the hypotheses in H; gets removed from H,. On the one hand, for each accepted Sj. at least / hypotheses are marked. So the total number of marks we made is at least //H On the other hand, since only c-fraction of the hypotheses than 0.17 times. The total number of marks we made at most cl (T + 0.1 - c) HT. As the following inequality always holds
marked by more
cHH,TT - 2 1//6/
we conclude e 2 2/27. According to [28], the size of the c-cover of H is at most Odd/c) Since h" also included in H; after most Ödd (dlogg(/e)) rounds, he will the only hypothesis not removed. Since h' has error at most 21y. if Appendix C runs for k rounds, then h will be output. So, before the kth round, some hH, must be output and has error O(n) = O(ppt). This proves the correctness of Algorithm 3.
Finally, it remains prove the query complexity of Algorithm 3. We notice by Equation (2) that when h4, has an error larger than 250r,, random Sj has only probability less than 0.01 not getting accepted. This implies that to get accepted Sj. we only need to make Ó(1) TSQs to check whether hH, has zero error over Sj. Since checking the error of hHs and marking hypothesizes after some Sj gets accepted will only take us O(1) TSQs. In each round Algorithm 3, we will make at most Õ(1) TSQs. Since there are at most (d (og(/ /c)) rounds in Algorithm 3, we conclude the query complexity of Algorithm 3 is (l)))))))
18

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The abstract summarizes the results provided in Theorem 1.4 and Theorem 1.5. The introduction summarizes the motivations of this paper and describes prior work's contributions.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitations of this paper discussed in the introduction of the paper.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-texx system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
19

---

Answer: [Yes]
Justification: The statement of each theorem provides all the assumptions and we provide complete proofs for all statements that are either in the main body of the paper in the appendix.
Guidelines:
The answer NA means that the paper does include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: This paper is theoretical and does not contain experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
20

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
This paper is theoretical and does not contain experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
wtips.cc/ppblicc//eecccc geicc//gueee...e CoodeSummii www.nnoolicciooeooo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This paper is theoretical and does not contain experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This paper is theoretical and does not contain experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
21

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This paper is theoretical and does not contain experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: http///eerrrpppeeeee//ee wccppublic/tthicccuuiiiiii
Answer: [Yes]
Justification: Our research conforms in every respect with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This work theoretical and we not see any immediate implications on society.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
22

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper is theoretical.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: This work does not use any assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
23

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This work does not any assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
24


Reviews:
[{"review_id": "TK9CY25J1U", "reviewer": "Reviewer_VrwT", "summary": "This paper is concerned with active learning of halfspaces under persistent Massart noise, i.e., active learning under data $(X,Y)$ for which $\\exists w^* \\in \\mathbb{R}^d, \\eta \\in [0,1/2)$ such that $P(Y = \\mathrm{sign}(\\langle w^*, X\\rangle)) \\ge 1-\\eta$. \n\nThe paper proposes a new query language for this task, \"threshold statistical queries\" (TSQs). A TSQ consists of a set $S \\subset (\\mathcal{X}\\times \\mathcal{Y})^m,$ a map $\\phi$ from $\\mathcal{X} \\times \\mathcal{Y}$ to the reals, and a threshold, a real number, $\\tau$, such that in response to a query of the form $(\\phi, S,\\tau),$ the learner receives a feedback indicating if $\\sum_{(x_i, y_i) \\in S} \\phi(x_i, y_i) > \\tau$ or not.\n\nThe main contribution of this work is the design and analysis of a new algorithm that active learns halfspaces in the described setting to error $\\eta + \\varepsilon$ with $O((d \\log(1/\\varepsilon)^3)$ TSQs and in polynomial time, without the use of structural assumptions on the feature distribution of the data. This method relies on an insightful way to use a small number of (simple) TSQs to both check if a vector $w$ approximates $\\mathrm{sign}(\\langle w^*, x\\rangle)$ to $\\eta + \\varepsilon$-error _even under Massart noise_  over a set of $x$ that are isotropic and (near)-unit norm and satisfy $\\{ |\\langle w, x\\rangle \\ge 1/2\\sqrt{\\mathrm{dim}(x)} \\},$ and if not, to build a witness for the same. This core dea is exploited to construct a convex feasibility oracle using a small number of TSQs via an existing method (Vaidya's Algorithm), which in turn is used to find an $\\varepsilon$-neighbour of $w^*$ with a small number of TSQs and limited computation, at least over isotropic and near-unit-norm features. This is extended to general feature distributions by exploiting Forster's transform, as has appeared in recent work on learning halfspaces under noise.\n\nThis result is complemented by a negative result that asserts that in the stronger model of agnostic learning (wherein some arbitrary $\\eta$-fraction of the data can have labels that disagree with $\\mathrm{sign}(\\langlew^*, x\\rangle)$, without the stochastic structure imposed by Massart's condition). This result states that in such a setting, even learning a singleton out of a size-$n$ domain to excess error $1/4n$ requires $\\Omega(n)$ TSQs, and thus shows that in general, one cannot use fewer than $\\Omega(1/\\varepsilon)$ TSQs to learn such a class (which further has a natural implication for halfspaces). The proof uses a reduction to distributed learning that is quite interesting.", "questions": "-", "limitations": "I think this is fine viz the social impact stuff, but I suppose the contextualisation of TSQs I mentioned above can be viewed as a limitation that should be discussed a little more.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Active learning of halfspaces under Massart noise is a challenging problem and of deep interest to the theoretical ML community, and thus this paper is certainly pertinent to the audience of Neurips. To my reading, the results are correct. Prior work is discussed in impressive detail, and the investigation of the paper is well contextualised. \n\nBefore offering more subjective comments, I do want to say that I am not an expert in this subfield of active learning, and my adjudication, especially of the novelty of the work, must be treated thus with care.\n\nI find the results of this paper very interesting. I think that the TSQ setup does not appear to be _too_ powerful from the get go, and fits fairly well with some of the mistake-based query structures studied in prior work. The result captures the highly nontrivial setting of learning halfspaces without feature distribution assumptions, and the method proposed is elegant and clever. The writing of the paper is also excellent, and communicates subtle ideas in a clear manner, making the approach seem deceptively simple. \n\nOn the whole, I think this is a strong contribution to the literature.", "weaknesses": "I don't particularly see major weaknesses with the paper. However, I think that the main lacuna lies in the limited contextualisation of the a priori power of TSQs in the paper. While I appreciate the clear contextualiation of the investigation of query structures in active learning, I think the practicality of TSQs is not very clearly discussed in the paper. Mainly, the paper places discusses this in the context of mistake based queries, but clearly the TSQ setting is more onerous for a labeler, since they must compute $\\phi$ over all examples in $S$ (rather than, e.g., simply declaring the first  mistake they find). I think that a frank discussion of how the authors think this query structure may be executed in practice would strengthen the contribution.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for carefully reviewing our work and for the constructive feedbacks. Below is our response about the practicality of TSQs.\n\n> While I appreciate the clear contextualiation of the investigation of query structures in active learning, I think the practicality of TSQs is not very clearly discussed in the paper. Mainly, the paper places discusses this in the context of mistake based queries, but clearly the TSQ setting is more onerous for a labeler, since they must compute $\\phi$ over all examples in $S$ (rather than, e.g., simply declaring the first mistake they find).\n\n\nMistake-based query itself has already been useful in practice. For example, as mentioned in [BH12], mistake-based queries are used in Faces in Apple-iPhoto. \n\nFrom a theoretic perspective, TSQ is a natural generalization of previous query languages such as region queries, statistical queries, and label queries. In this paper, we did not focus on optimizing the structure of the queries we use in the algorithms. In fact, an efficient learning algorithm using TSQ may not exploit the full power of TSQ and thus depending on the application, one might be able to instead use other subclasses of TSQ that can be easily implemented. We believe that studying the tradeoff between the complexity of the query structure and the query complexity is very important and thus expect more future work done on designing simple and user-friendly TSQ for various learning problems. \n\nFrom an application perspective, we think learning with TSQ can also be used to formulate problems arising from practical applications as TSQ is a class of queries that can be computed in linear time. \nFor example, there are many application such as sloving complicated tasks by interacting with LLMs, where a learning problem could be in general very hard to solve by an LLM, but human experts can break down the problems into sequential simple queries/questions such as TSQ that can be computed and verified fast by powerful models and thus can use LLM as a tool to solve complicated tasks. We will add more detailed discussions about these in the future version of the manuscript.\n\n>Reference \n\n>[BH12]Balcan, Maria Florina, and Steve Hanneke. \"Robust interactive learning.\" Conference on Learning Theory. JMLR Workshop and Conference Proceedings, 2012.", "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": "", "extra_scores": {}}, {"review_id": "LrcUiDeR9h", "reviewer": "Reviewer_vqip", "summary": "This paper extends the work on pool-based active learning from the realizable case to non-realizable settings: where the observed labels (or answers to active learning queries) can have noise. The paper focuses on learning half-spaces, a fundamental learning theory problem. \n\nExisting works on pool-based active learning have designed several query languages that enable learning half-spaces up to $\\epsilon$ accuracy using $O(\\log(1/\\epsilon))$ queries. The algorithms in these works, however, break when there is noise in the responses – even due to benign noise models such as random classification noise. \n\nThis work designs a new query language – threshold statistical queries – and shows that it enables learning of half-spaces up to $\\epsilon$ accuracy with $\\mathrm{poly}\\log(1/\\epsilon)$ samples even when the underlying labels have been corrupted by certain the Massart noise model (which is a significant extension of the random classification noise model).\n\nTo complement this result, the authors show that threshold statistical queries are not sufficient to learn halfspaces (or even 1-d thresholds) up to $\\epsilon$ accuracy with fewer than $O(1/\\epsilon)$ samples in the stronger agnostic learning model.\n\nFinally, if instead of the usual $OPT+\\epsilon$ guarantee, one considers algorithms with $O(OPT)+\\epsilon$ guarantees, then the authors show that it is possible to learn halfspaces with $\\tilde{O}(\\log(1/\\epsilon))$ samples.", "questions": "**Question 1.** The related works section mentions that Theorem 1.4 (the main/first result) can be implemented with standard statistical queries, as opposed to the new, threshold statistical queries introduced in this work. This is a bit confusing to me: if statistical queries are sufficient, then why is the model of threshold statistical queries introduced for Theorems 1.4 and 1.5 – the first two results? (Since Theorem 1.5 shows an impossibility result for learning with $\\mathrm{poly}\\log(1/\\epsilon)$ threshold statistical queries and, further, since statistical queries are a special case of threshold statistical queries, this result should also hold for statistical queries.)\n\nIf both of these results do indeed work with statistical queries, then I think \n1. this should be emphasized and \n2. the definition of threshold statistical queries can be delayed till the last result.\n\n**Question 2.** The results in this paper work for origin-centered half-spaces, instead of all halfspaces. Is this correct? I do not think this is a major concern as studying origin-centered halfspaces is a standard first step toward developing algorithms for half-spaces. But I think, if my claim is correct, then this should be clarified early in the introduction.", "limitations": "Please see my comments in weakness and questions sections.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "Designing new types of queries that enable learning with exponentially fewer samples than necessary for PAC learning is an important area of active work. This paper studies a central problem in this area: learning halfspaces. As far as I understand, this is the first work to propose a type of query that enables learning halfspaces up to accuracy $\\epsilon$ with $\\mathrm{poly}\\log(1/\\epsilon)$ samples when there can be some noise in the answers. The types of noise models considered are also natural and widely studied in standard PAC learning settings. \n\nWhile I am familiar enough with this area, to comment on the novelty of the techniques, the approach and the tools used (e.g., Forster’s transform) seem natural.\n\nSomething that can potentially be an added strength is if there is hope to use threshold statistical queries (introduced in this work) for learning other hypothesis classes, even non-efficiently: for instance, instance intersections of halfspaces or (non-axis-aligned) boxes. It would be great to have some discussion on this.", "weaknesses": "One weakness of the paper is the presentation: while the paper was largely clear and not hard to follow, some sentences and notation are a bit weird, but I am sure the paper would read much better after another pass. \n\nSome specific notation-related suggestions/comments:\n1. The notation B_1^k used in Theorem 2.1 is non-standard but is used before it is defined. Perhaps, till this notation is introduced, it can be avoided or explained in a footnote.  \n2. Definition 1.1 is a bit confusing. Specifically the sentence “Each query q : 2S×{±1} → {0, 1} …number in {0, 1}.” I am not sure what “given unknown labels as input” means.\n3. I think using \\cdot for the inner product is non-standard. Maybe it is better to use the $x^\\top y$ notation?\n4. Definition 3.1 and some subsequent places use the notation “S =< Sa, Sb >” to denote a set $\\{S_a,S_b\\}. Perhaps using braces is better?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for appreciating our work and providing many constructive suggestions. We will improve the presentation in the future version of the manuscript. We think exploring the power of TSQ for other hypothesis classes such as the intersection of halfspaces or high dimensional boxes can be very promising directions and we will add more discussion on related directions in the future version of the manuscript. Below we respond to the comments and questions from the reviewer.\n\n>Question 1. The related works section mentions that Theorem 1.4 (the main/first result) can be implemented with standard statistical queries, as opposed to the new, threshold statistical queries introduced in this work. This is a bit confusing to me: if statistical queries are sufficient, then why is the model of threshold statistical queries introduced for Theorems 1.4 and 1.5 – the first two results? If both of these results do indeed work with statistical queries, then I think this should be emphasized and\nthe definition of threshold statistical queries can be delayed till the last result.\n\nWe want to remark that a high-level goal of this paper is to understand the power of queries for efficient learning with noise. Toward this goal, the query model studied should be simple but general enough to capture many existing query strategies. In this paper, we show that TSQ is an interesting general model that incorporates different query languages in the literature such as SQ with bounded precision, equivalence queries, region queries, label queries, etc.\n\nFor Theorem 1.5, we want to mention that the return of a classic statistical query is a real number and the number of bits of information passed by such a query depends on the precision of the query. A statistical query with polynomial small precision can be implemented with a logarithmic number of TSQs and thus Theorem 1.5 also holds for SQs with bounded precision. However, as TSQ also captures other types of query languages that operate directly over samples, our lower bound in Theorem 1.5 shows that agnostic learnings are indeed intricate and to achieve a low query complexity, even more powerful queries are needed to come up with.\n\nOn the other hand, TSQ is a very broad class of queries, and thus in some applications, the full generality of TSQs may not be feasible. An efficient learning algorithm using TSQs could in principle be optimized to use a subclass of TSQs with good structure that is easily implementable. For example, in Theorem 1.4, we use TSQs to find points $\\bar{x}$ to feed Vaidya’s algorithm. As these queries are sampled from regions with non-trivial probability mass and estimating $\\bar{x}$ up to a polynomial small error is enough, we can modify the algorithm by using the classic statistical queries with polynomial small precisions. On the other hand, in Theorem 1.6, the algorithm we use makes decisions based on both the statistical properties of the dataset and labels of individual examples, it cannot be implemented with solely SQ.\n\nWe will expand these discussions and add more explanations together with examples to emphasize the relation between TSQ with other types of queries. \n\n>Question 2. The results in this paper work for origin-centered half-spaces, instead of all halfspaces. Is this correct?\n\nAs our theorem is distributional-free(no distributional assumption is made), learning origin-centered halfspaces is equivalent to learning general halfspaces. This can be done by adding another dimension to the problem artificially.", "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": "", "extra_scores": {}}, {"review_id": "2QmpsiRT9w", "reviewer": "Reviewer_WAF8", "summary": "This paper focused on the problem of active learning from enriched queries.\nIn order to be abale to learn halfspaces without restrictive distribution assumptions, authors propose Threshold Statistical Query (TSQ) which genarizes the region query and the classic statistical learning model query.\nUsing the proposed from of query, authors propose an algorithm to learn halfspaces in polynomial time, using only poly log(1/$\\epsilon$) TSQ queries, under random classifcaiton noise and massart noise. Authors also proved the impossibility for the advasarial noise case.", "questions": "- On the noise format, authors considers the persistent form of noise which keeps same among different query trials.\n  - Is this the reason that existing methods cannot achieve the poly log(1/$\\epsilon$) query complexity?\n  - How the proposed algorithm would be influenced if changing the noise to give random answers at each query? How will it influence finding $\\bar{x}$?", "limitations": "The limitation on assumptions and adversarial noise is addressed in introduction.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The proposed query has motivations easy to understand, and successfully derives the learning algorithm with carefully designed steps.\n- The paper is self-containment. Essential background and definitions are clearly presented.\n- The discussion on algorithm design and theory deriviation is solid and clear.", "weaknesses": "- The manusciprt seems to be not complete. It is not proper concluded.\n  - An overal dicussion section on limitations may also improve the manuscript.\n- The presentation of algorithm design can be improved.\n  - Although already demonstrated in section 2.2, intuitive introduction on how the strong learning algorithm is designed and how it uses the weak learning algorithm can be added at the beginning of section 2.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the constructive feedback and thank the reviewer for carefully reviewing our manuscript. We will improve the presentation of the paper based on the suggestions and include a conclusion section with further discussion. Below is our response regarding the question on the noise format.\n\n>On the noise format, authors considers the persistent form of noise which keeps same among different query trials.\nIs this the reason that existing methods cannot achieve the $poly \\log(1/\\epsilon)$ query complexity?\nHow the proposed algorithm would be influenced if changing the noise to give random answers at each query? How will it influence finding $x$?\n\nThe same algorithm we developed works for the non-persistent setting where there is randomness in every query. This is because we construct queries using randomly selected examples. We will clarify this point in the manuscript.\nThe reason that existing methods cannot achieve low query complexity is the noise and not whether it is persistent or not. As we mentioned in the introduction, a small amount of label noise could make every large region query useless as it would produce the same answer with high probability. The same would hold even if the noise is persistent. In fact, persistent noise is even more challenging as it prevents a learner from making repeated queries over a single example to figure out its underlying label, which in some settings could make the problem trivial.", "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": "", "extra_scores": {}}, {"review_id": "G1rOag3zhg", "reviewer": "Reviewer_DNzP", "summary": "This paper considers active learning of halfspaces with noise that is both computationally efficient and query efficient without distributional assumption on X. Since it is known such problem is \"hard\" in the standard label query paradigm, it considers a new query model called \"threshold statistical queries\" (TSQ) where given a function $\\phi$, set $S=\\{ x_1, .., x_n \\} $, and threshold $\\tau$, the oracle answers if $\\sum_{x_i \\in S}\\phi(x_i, y_i) > \\tau$. Under Massart noise, it gives an active learning algorithm that is both computationally efficient and query efficient with this query model. On the other hand, it shows that under adversarial noise, this noise model cannot lead to query efficient learning.", "questions": "N/A", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- This paper considers a niche but still quite relevant theory problem of active learning for halfspaces. Its results are interesting: it shows that the newly proposed TSQ query model allows for efficient learning of halfspaces under Massart noise without distributional assumptions, while it is not strong enough to resolve the problem under the adversarial noise.\n\n- The proposed TSQ query model is a nice and novel generalization/modification of previous models (statistical queries, region queries). The techniques for both the upper bound and lower bound look non-trivial and novel to me.\n\n- The paper is written clearly. It provides a comprehensive review of related work and techniques, and clear high-level intuition behind the main results.\n\n- The paper is sound, though I did not check proofs in Appendix.", "weaknesses": "- The label complexity bound in Theorem 1.4 is cubic in both d and log(1/epsilon). It would be interesting to see if this can be improved, but this would be a very minor issue.\n\n- It would be more interesting if the authors could comment on how/whether the TSQ query model can make improvement in other noise models, or problems with a general (beyond linear) learning space.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for appreciating our work. Improving the cubic term in the label complexity is definitely an interesting open question. We will add a conclusion section in the future version of the work to introduce some potential future directions.", "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": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their time and effort in providing feedback. We are encouraged by the positive comments, and that all the reviewers appreciated the paper for the following (i) Novelty and interesting result (**VrwT,vqip,WAF8,DNzP**), (ii) technically clean and interesting (**VrwT, WAF8, DNzP**), (iii) clear presentation and well-motivated (**VrwT,vqip,WAF8,DNzP**) Below, we address the individual questions and comments by the reviewers separately.

Meta-review: The reviewers unanimously agreed that the model considered in the paper is natural and that the results are interesting.
Decision: Accept (spotlight)