{"id":"e157b607-8661-4672-bf67-262916c4a33e","arxiv_id":"2501.00508","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"General halfspaces under Gaussian marginals cannot be actively learned with poly(d/ε) unlabeled data unless exponentially many samples are available, but membership queries achieve O~(min{1/p,1/ε}+d polylog(1/ε)) complexity.","lead":"This paper proves that active learning with label queries cannot significantly beat passive learning for general halfspaces under Gaussian data, unless the unlabeled pool is exponentially large. It then shows that giving the learner membership queries bypasses this barrier, yielding a computationally efficient agnostic learner with near-linear-in-dimension query complexity.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Appendix D algorithms query y(A z - s w) but all localization analysis assumes the query is y(A^{1/2} z - s w); for covariance A, the distribution is N(-s w, A), so the extreme-threshold branch of Theorem 1.2 is not proved as written.","rationale":"The reader's weakest assumption (Lemma 3.5's union bound) is a real but minor issue: the union bound gives a success probability of roughly 0.43 rather than 1/2, yet the needed constant probability still holds for the initialization and the polylog repetition in Algorithm 1. In contrast, the A versus A^{1/2} discrepancy in Appendix D is a structural inconsistency: the algorithm queries a distribution with covariance A^2, while all analysis, including the localization fact (Fact 3.2) and the rejection-procedure lemma (Lemma B.1), is for covariance A. If the queries do not follow the intended rejection distribution, the noise-rate bound in Lemma D.2 and the angle-test threshold in Algorithm 4 are unjustified, so the extreme-threshold branch of Theorem 1.2 is not proved as written. This is the most load-bearing concern because it affects the correctness of the main algorithmic result for a whole parameter regime, not just the tightness of a constant. The fix is likely to insert A^{1/2} in the pseudocode and in Lemma D.2, which is why the verdict remains conditional rather than reject.","tokens_in":801,"tokens_out":870,"duration_ms":249161,"concrete_test":"In the proof of Lemma D.2, replace every occurrence of A z - s w with A^{1/2} z - s w and re-derive the noise bound eta <= 6 epsilon exp(s^2/2)/b under the correct distribution N(-s w, A). Separately, simulate Algorithm 4 with both A z and A^{1/2} z for a fixed halfspace and check whether the empirical probability p_hat(s) matches p(b,s) within the claimed error; if it only matches with A^{1/2}, the algorithm must be corrected.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"In Algorithms 4 and 5 (Appendix D), the localization step defines A = I - (1 - sigma^2) w w^T and then queries y(A z - s w). However, the (v,s,sigma)-rejection procedure (Def. B.2, Lemma B.1) yields samples distributed as A^{1/2} z - s v, i.e., N(-s v, A). Using A z - s w gives covariance A^2 instead of A, so the query distribution has variance sigma^4 along w rather than sigma^2. The analysis of Lemma D.2 relies on the rejection-procedure distribution to bound the noise rate eta <= 6 epsilon exp(s^2/2)/b and to relate the empirical bias to p(b,s). Those bounds are invalid for the stated queries. Since Theorem 1.2 depends on Algorithm 5 for extreme thresholds (when eta log(1/eta) > 1/t), this inconsistency directly threatens the central MQ upper bound for small p. The issue is likely a missing square root in the pseudocode, but it is systematic: the same A z appears in Algorithm 4, Algorithm 5, and the proof of Lemma D.2, so it cannot be dismissed as a one-off typo in an algorithm box.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies active learning of general (not necessarily homogeneous) halfspaces under the standard Gaussian distribution, comparing pool-based label queries with membership queries. The main negative result (Theorem 1.1) is an information-theoretic lower bound stating that any active learner over a pool of m unlabeled examples needs ~Omega(d/(p log m)) label queries to learn a p-biased halfspace to error p/2, so nontrivial improvements over passive learning require exponentially large pools. The main positive result (Theorem 1.2) is a computationally efficient agnostic membership-query learner with query complexity ~O(min{1/p, 1/eps} + d polylog(1/eps)) and error O(opt)+eps. The upper bound is built from a randomized localization / gradient-descent refinement of a warm start, together with a smoothed-label initialization procedure; the extreme-threshold case is deferred to Appendix D. The paper also claims near-optimality of the membership-query complexity via an informal reduction to HKL20.","tokens_in":34793,"tokens_out":7201,"duration_ms":74868,"significance":"If the results are correct, the paper resolves a natural open question by showing a strong separation between label-query and membership-query models for general halfspheres under Gaussian marginals, and it provides an essentially optimal agnostic MQ learner with polynomial time. The lower-bound argument via decision trees and Yao's principle is a genuine information-theoretic contribution, and the upper-bound machinery adapts known localization and smoothed-label techniques in a nontrivial way. The paper is also careful to rely on prior work (DKS18, DKTZ22, DKK+23) rather than assuming its own conclusions, so I see no circularity. However, as written the extreme-threshold branch of the MQ upper bound contains a systematic query-distribution inconsistency, and one key probability lemma is stated with an unsupported constant; these issues must be repaired before the main claims are established. The informal optimality claim for the MQ lower bound is also not proved in the manuscript.","major_comments":[{"comment":"The pseudocode queries y(A z - s w) (Algorithm 4 line 9; Algorithm 5 lines 10-12), but all localization analysis, including Lemma D.2 and the use of Lemma B.1, is for samples of the form A^{1/2} z - s v, whose marginal is N(-s v, A). With A = I - (1-sigma^2) w w^T, querying A z - s w produces covariance A^2, i.e., variance sigma^4 along w instead of sigma^2. Consequently the proof that the noise rate is at most 6 eps exp(s^2/2)/b and the comparisons with p(b,s) do not apply to the distribution actually queried. Because Theorem 1.2 relies on Algorithm 5 for the extreme-threshold branch (when eta log(1/eta) > 1/t), the membership-query upper bound is not proved as written. The fix appears to be replacing A by A^{1/2} in the query points, but the change must be made consistently in both algorithms and the proof.","section":"Appendix D, Algorithms 4-5 and Lemma D.2"},{"comment":"The lemma asserts that a random negative example is simultaneously eta(x) <= 5 eps/p and near the decision boundary with probability at least 1/2. The proof obtains P(eta(x)<=5 eps/p) >= 3/4 by Markov's inequality and P(w* . x in (-t*-1/t*,-t*)) >= 1 - e^{-1} - 2/C; the union bound gives only about 0.38 for large C, not 1/2. The quantitative statement as written is false. Since Algorithm 1 repeats the initialization polylog(1/eps) times, a constant success probability would still suffice, but the lemma and its uses in Theorems 3.4 and D.1 need to be restated with the correct constant and the repetition count adjusted accordingly.","section":"Lemma 3.5 and Appendix C.1"},{"comment":"The paper claims the MQ query complexity in Theorem 1.2 is essentially optimal and gives an Omega((1/p)^{1-o(1)}) lower bound 'deduced' from HKL20 by an argument 'essentially identical' to the unit-ball case. This is only a sketch; no formal lower-bound theorem for the Gaussian setting is stated or proved, and the approximation of the Gaussian by the sphere is not quantified. If the near-optimality claim is to be part of the paper's contribution, it should be stated as a theorem with a proof; otherwise the wording should be weakened.","section":"Section 1, 'Optimality of Query Complexity'"}],"minor_comments":[{"comment":"The theorem says a learner making 'less than ~O(d/(p log m))' queries cannot succeed; this should be 'less than ~Omega(d/(p log m))' or equivalently 'at most O(d/(p log m))'. The proof's final display gives the correct threshold r <= O(k/p log(1/p)), so this appears to be a typographical slip in the theorem statement.","section":"Theorem 1.1 statement"},{"comment":"The two clauses in Lemma D.2 are asymmetric: the first says 'the probability that ps > p(b,s)/4 is at most 1/2', while the second says 'the probability that ps > p(b,s)/2 is at least 29/30'. The first condition should presumably be 'ps < p(b,s)/4' or the thresholds should be aligned. Please clarify.","section":"Lemma D.2 statement"},{"comment":"In the second case of the proof of Theorem 3.4, the sentence 'Since u0 is close to E_{z~N(0,I)} z' is missing the subscript: it should be 'u0 is close to E_{z~N(0,I)} z \\tilde{h}(z)'.","section":"Appendix C.2"},{"comment":"Definition F.1 says the small-class oracle draws (x,y) ~ D restricted to y=1 and returns x, but the surrounding text and the name EX^{(-)} indicate the oracle should return negative examples (y=-1). This sign inconsistency should be fixed, as it matters for the implementation claims.","section":"Appendix F, Definition F.1"},{"comment":"There are several typographical errors, e.g., 'Unfortinately' at the end of Section 3.2 and the garbled inequality display near Equation (5) in Appendix F with repeated terms. A careful proofreading pass is needed.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The Appendix D covariance mismatch is the most serious issue, but it looks like a systematic typo (using A instead of A^{1/2}) that the authors can fix within the scope of the paper. The Lemma 3.5 probability error is also quantitative and repairable. I would not reject, but the manuscript should not be accepted until the extreme-threshold branch of Theorem 1.2 is proved for the queries actually made, and the near-optimality claim is either proved or downgraded. The paper is otherwise well within the scope of the journal and, once repaired, would be a strong contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First, the lower bound (Theorem 1.1) is the real thing. The Yao/decision-tree argument with the beta-distribution tail bound is clean, and it closes the natural route of beating passive learning with polynomial pools. The MQ result is also a substantial technical achievement—if the proof holds—combining the smoothed-label trick from DKK+23b with the DKS18 localization framework.\n\nThe soft spot is Appendix D. Algorithm 4 and 5 query y(A z - s w) with A = I - (1-σ²) w wᵀ, but the whole analysis—Definition B.2, Lemma B.1, Lemma 3.3, Lemma D.2—is built on queries y(A^{1/2} z - s w), whose distribution is N(-s w, A). Using A z instead gives covariance A², so the rejection-procedure bound on the noise rate does not apply. This is systematic: the same A z appears in the pseudocode, the proof of Lemma D.2, and Algorithm 5. As written, the extreme-threshold branch of Theorem 1.2 (the case η√log(1/η) > 1/t, i.e. small p) is unproved. I expect a missing square root, but it is load-bearing and needs a careful fix.\n\nTwo smaller points. The claimed near-optimality of the MQ bound is only a sketch of a reduction to HKL20; fine as a remark, but it should be labeled informal. Lemma 3.5 says a random negative example is near the boundary and has small smoothed-label noise with probability ≥ 1/2, but the proof's union bound gives roughly 0.36; that's a constants issue, not structural.\n\nBottom line: the lower bound looks solid, the MQ framing is right, and the upper bound is plausible once Appendix D is repaired. The active-learning theory community should engage with this paper. I'd send it to a serious referee and expect a conditional accept after the appendix is fixed.","headline":"Strong lower bound, promising MQ algorithm, but the extreme-threshold branch of the proof has a systematic square-root error that needs fixing.","tokens_in":35376,"tokens_out":6142,"would_cite":true,"duration_ms":56424,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","68T05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Pool-based active label queries give no advantage over passive learning for halfspaces unless the pool is exponentially large; membership queries then achieve near-optimal query complexity.","keywords":["active learning","membership queries","halfspaces","Gaussian marginals","agnostic learning","label complexity","query complexity","Chow parameters"],"falsifier":"Run the initialization on a synthetic halfspace with a known $\\epsilon$-noisy labeling, and measure how often a random negative example is both near the boundary and has smoothed-label disagreement at most $5\\epsilon/p$; Lemma 3.5 says at least half, and a sub-constant rate would break the repetition guarantee. For the lower bound, simulate a proposed active learner on $m=\\mathrm{poly}(d/\\epsilon)$ Gaussian examples and count label queries required to reach error below $p/2$ on a random $p$-biased halfspace; the theorem predicts $\\tilde{\\Omega}(d/(p\\log m))$ is necessary.","tokens_in":34320,"feed_emoji":"🎯","tokens_out":18649,"duration_ms":154357,"temperature":0.7,"pith_summary":"This paper asks how much query access helps when learning general (potentially biased) halfspaces—signed linear classifiers $\\mathrm{sign}(w\\cdot x+t)$—under the standard Gaussian distribution, allowing arbitrary label noise. It establishes a sharp divide between two query models. In the classical pool-based active model, where the learner may only request labels of previously sampled points, no algorithm can do substantially better than passive learning unless the unlabeled pool is exponentially large: any learner needs $\\tilde{\\Omega}(d/(p\\log m))$ label queries to achieve error $p/2$ on a $p$-biased halfspace, where $m$ is the pool size. With membership queries, where the learner can ask the label of any point in space, a computationally efficient algorithm achieves error $O(\\mathrm{opt})+\\epsilon$ using only $\\tilde{O}(\\min\\{1/p,1/\\epsilon\\}+d\\,\\mathrm{polylog}(1/\\epsilon))$ membership queries, even in the agnostic setting. Together these results show that the type of interaction—choosing arbitrary points versus choosing from a finite unlabeled sample—changes the query complexity of learning halfspaces qualitatively.","feed_headline":"Active label queries can't beat passive learning for halfspaces","feed_subtitle":"Membership queries, which can ask any point, get error O(opt)+ε with only Õ(d polylog(1/ε)) queries.","key_machinery":"The lower bound is carried by a decision-tree counting argument combined with the near-orthogonality of high-dimensional Gaussian sample points. For any $k$-tuple of pool points, with high probability their normalized Gram matrix is close to $dI$ when $k=O(d/(\\log m)(t^*)^4)$; a random halfspace of bias $p$ labels all $k$ points negative with probability at most $(O(p\\log(1/p)))^k$. Since an algorithm that finds $k$ negative examples in $r$ label queries has at most $\\binom{r}{k}$ successful decision-tree paths, $r$ must be $\\tilde{\\Omega}(k/p)$ before success is possible, which yields the label-complexity lower bound. The upper bound runs on a different mechanism: estimate the bias $p$, grid-search the offset $t^*$, find a warm-start direction $w_0$ by querying one random negative example and using smoothed labels, then refine $(w,t)$ by projected gradient descent on a localized estimate of the Chow parameter vector $\\mathbb{E}_{z\\sim N(0,I)}[z\\,h(z)]$, with a $(v,s,\\sigma)$-rejection procedure keeping noise below the signal; candidate hypotheses are combined by a tournament. The workhorse identity (Fact 3.3) is that a Gaussian halfspace $h(x)=\\mathrm{sign}(w\\cdot x+t)$ has Chow parameter $\\sqrt{2/\\pi}\\exp(-t^2/2)\\,w$, so direction estimates can be read off from label queries whose cost depends on the threshold.","core_discovery":"The paper's central claim is that pool-based active label queries provide essentially no asymptotic advantage over passive learning for general halfspaces under Gaussian marginals, while membership queries provide near-optimal query efficiency even in the agnostic (nasty-noise) setting. Theorem 1.1 states that any active learner making fewer than $\\tilde{\\Omega}(d/(p\\log m))$ label queries over $m$ i.i.d. Gaussian examples fails, with constant probability, to reach error $p/2$ for a $p$-biased halfspace; in particular, beating the passive label complexity $\\tilde{O}(d/\\epsilon)$ requires a pool of $2^{\\mathrm{poly}(d)}$ unlabeled examples. Theorem 1.2 gives a polynomial-time membership-query algorithm that, with $M=\\tilde{O}(\\min\\{1/p,1/\\epsilon\\}+d\\,\\mathrm{polylog}(1/\\epsilon))$ queries, outputs a halfspace of error $O(\\mathrm{opt})+\\epsilon$ for every labeling function, where $\\mathrm{opt}$ is the 0-1 loss of the optimal halfspace. The lower bound is information-theoretic and applies to every algorithm; the upper bound is constructive, agnostic, and runs in polynomial time. The two results together constitute a strong separation between the label-query and membership-query models for this class.","pith_inferences":["A plausible broader lesson is that for high-dimensional Gaussian problems the value of interactivity lies in synthesizing new query points, not in selectively labeling an existing pool; replacing pool access with membership access changes the query complexity by an exponential factor in the pool size needed.","The lower bound's near-orthogonality mechanism suggests the same $\\tilde{\\Omega}(d/(p\\log m))$ barrier should hold for any isotropic high-dimensional distribution whose samples are nearly pairwise orthogonal with high probability, while low-dimensional or strongly correlated data may restore the advantage of active label selection.","The paper leaves open whether the $\\min\\{1/p,1/\\epsilon\\}$ term can be removed without a small-class oracle under intermediate noise models such as bounded noise or margin conditions, and whether the upper bound can be tightened to the information-theoretic $d\\log(1/\\epsilon)$.","A practical testable corollary is that on Gaussian-like data with heavy label noise, algorithms that query labels at smoothed perturbations of one informative negative example should require far fewer labels than algorithms restricted to labeling points from the observed pool."],"forward_implications":["If the lower bound is right, no pool-based active learner—regardless of computation—can avoid the passive $\\tilde{\\Omega}(d/\\epsilon)$ label complexity for general halfspaces unless its unlabeled pool has size exponential in $d$.","If the upper bound is right, membership queries yield the first computationally efficient agnostic learner for general Gaussian halfspaces with query complexity $\\tilde{O}(d\\,\\mathrm{polylog}(1/\\epsilon))$ up to the unavoidable $\\min\\{1/p,1/\\epsilon\\}$ exploration term.","A direct corollary is a strong separation between query models: membership queries achieve $\\tilde{O}(\\min\\{1/p,1/\\epsilon\\}+d\\,\\mathrm{polylog}(1/\\epsilon))$, while label queries over an $m$-point pool require $\\tilde{\\Omega}(d/(p\\log m))$.","If a small-class oracle supplies a random negative example, the same algorithm runs with only $\\tilde{O}(d\\,\\mathrm{polylog}(1/\\epsilon))$ membership queries, showing the $1/p$ term is an exploration cost rather than a learning cost.","The query complexity is nearly optimal in the agnostic setting, matching the $\\Omega(d\\log(1/\\epsilon))$ information bound and the $\\Omega((1/p)^{1-o(1)})$ small-class exploration bound."],"supporting_citations":[{"why":"Supplies the localization machinery—the Chow-parameter identity, the $(v,s,\\sigma)$-rejection procedure, and the randomized threshold method—used by the refinement algorithm to keep noise below the gradient signal.","marker":"[DKS18]"},{"why":"Gives the lower bound that finding a first small-class example needs $\\Omega((1/p)^{1-o(1)})$ membership queries, used to argue the $\\min\\{1/p,1/\\epsilon\\}$ term is unavoidable.","marker":"[HKL20]"},{"why":"Provides the earlier information-theoretic lower bound $\\Omega(\\min\\{1/p,1/\\epsilon\\}+d\\log(1/\\epsilon))$ for general halfspaces that this paper strengthens and places in context.","marker":"[Das05]"},{"why":"Gives the $O(d\\log(1/\\epsilon))$ active-learning result for homogeneous halfspaces whose failure to extend to biased halfspaces motivates the separation.","marker":"[BBZ07]"},{"why":"Supplies the prior information-theoretic upper bound $\\tilde{O}((1/p)d^{3/2}\\log(1/\\epsilon))$ for general halfspaces that the membership-query algorithm improves and makes computationally efficient.","marker":"[BHV10]"},{"why":"Yields the $\\Omega(d\\log(1/\\epsilon))$ information-theoretic query lower bound used to establish near-optimality of the upper bound.","marker":"[KMT93]"},{"why":"Supplies the net and concentration inequalities used in Lemma 2.3 to show every $k$-tuple of Gaussian pool points has Gram matrix close to $dI$.","marker":"[Ver18]"},{"why":"Provides the tournament lemma (Lemma A.1) used to select the best candidate hypothesis with only polylog queries.","marker":"[DKK+23a]"},{"why":"Supplies Fact B.4, the noise-contamination bound used to control the error in the localized gradient estimates.","marker":"[DKTZ22]"}],"fun_headline_variants":["Membership queries beat active label queries for halfspaces","Active label queries no better than passive for halfspaces","Halfspaces: membership queries win, label queries don't","Membership queries give near-optimal halfspace learning, label queries don't","Pool-based active learning can't help halfspaces, membership queries can"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that a random negative example is, with at least constant probability, simultaneously close to the decision boundary and only mildly corrupted by label noise (Lemma 3.5), because the initialization's success and the polylog repetition in Algorithm 1 collapse if this event is sub-constant.","fun_headline_variants_meta":{"raw":{"variants":["Membership queries beat active label queries for halfspaces","Active label queries no better than passive for halfspaces","Halfspaces: membership queries win, label queries don't","Membership queries give near-optimal halfspace learning, label queries don't","Pool-based active learning can't help halfspaces, membership queries can"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001148,"raw_usage":{"total_tokens":4846,"prompt_tokens":1113,"completion_tokens":3733,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":729,"completion_tokens_details":{"reasoning_tokens":3644}},"tokens_in":729,"tokens_out":3733,"duration_ms":23014,"temperature":1.0,"reasoning_tokens":3644,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T22:51:14.793359+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the initialization on a synthetic halfspace with a known $\\epsilon$-noisy labeling, and measure how often a random negative example is both near the boundary and has smoothed-label disagreement at most $5\\epsilon/p$; Lemma 3.5 says at least half, and a sub-constant rate would break the repetition guarantee. For the lower bound, simulate a proposed active learner on $m=\\mathrm{poly}(d/\\epsilon)$ Gaussian examples and count label queries required to reach error below $p/2$ on a random $p$-biased halfspace; the theorem predicts $\\tilde{\\Omega}(d/(p\\log m))$ is necessary.","supporting_citations":[],"review_version":1}