Source-linked AI summary
Near-Optimal Active Learning of Halfspaces via Query Synthesis in the Noisy Setting
Lin Chen, Hamed Hassani, Amin Karbasi
TL;DR
The paper addresses active learning of linear classifiers through synthetic queries, especially when query responses are noisy. It introduces Dimension Coupling, which combines low-dimensional subproblems into a d-dimensional classifier. DC has linear computational scaling, near-optimal query complexity, and strong empirical performance against prior methods.
Problem
Active learning through query synthesis must estimate a linear decision boundary from artificial membership queries, including noisy responses, in settings such as automated science and adversarial reverse engineering.
Method
Dimension Coupling reduces the d-dimensional problem to d−1 low-dimensional subproblems, solves them efficiently, aggregates their results, and outputs a linear classifier.
Results
DC has computational complexity that scales linearly with dimension, near-optimal query complexity, and empirical speed advantages over existing methods.
Takeaways & Limitations
DC provides a theoretically supported and empirically effective approach for learning halfspaces through noisy synthetic membership queries.
Takeaways & Limitations
The related work notes that the effect of noise in active learning remains not very well understood.
Abstract
from arXiv · showhide
In this paper, we consider the problem of actively learning a linear classifier through query synthesis where the learner can construct artificial queries in order to estimate the true decision boundaries. This problem has recently gained a lot of interest in automated science and adversarial reverse engineering for which only heuristic algorithms are known. In such applications, queries can be constructed de novo to elicit information (e.g., automated science) or to evade detection with minimal cost (e.g., adversarial reverse engineering). We develop a general framework, called dimension coupling (DC), that 1) reduces a d-dimensional learning problem to d-1 low dimensional sub-problems, 2) solves each sub-problem efficiently, 3) appropriately aggregates the results and outputs a linear classifier, and 4) provides a theoretical guarantee for all possible schemes of aggregation. The proposed method is proved resilient to noise. We show that the DC framework avoids the curse of dimensionality: its computational complexity scales linearly with the dimension. Moreover, we show that the query complexity of DC is near optimal (within a constant factor of the optimum algorithm). To further support our theoretical analysis, we compare the performance of DC with the existing work. We observe that DC consistently outperforms the prior arts in terms of query complexity while often running orders of magnitude faster.
1 Introduction
The paper studies active learning of an unknown halfspace through synthetic membership queries, including noisy responses, and proposes Dimension Coupling (DC) as a noise-resilient solution. DC decomposes the d-dimensional problem into lower-dimensional subproblems, achieves linear computational scaling and near-optimal query complexity, and outperforms existing methods empirically.
- Query model: The active-learning setting permits arbitrary synthetic queries, so the learner receives only the sign of the queried inner product rather than its magnitude.Queries may be restricted to the unit sphere because scaling a query does not change its outcome.
- Problem and contribution: DC is a noise-resilient active-learning framework that estimates an unknown halfspace normal vector from adaptively chosen membership queries.The learner seeks an estimate within ǫ of the true unit normal with probability at least 1 −δ, despite independent label flips with probability ρ < 1/2.
- Method: The framework reduces the d-dimensional learning problem to d−1 low-dimensional subproblems, solves them efficiently, and aggregates their outputs into a linear classifier.The paper presents this decomposition and aggregation as the core Dimension Coupling design.
- Empirical comparison: DC is reported to outperform prior methods in theory and practice, including naive repetition and spectral heuristics [Alabdulmohsin, Gao, and Zhang 2015].The empirical discussion also reports orders-of-magnitude speed advantages over existing methods.
- Theoretical guarantees: Computational complexity scales linearly with dimension in both noiseless and noisy settings, while query complexity remains near-optimal.The introduction states these guarantees for DC; the supplied complexity display is incomplete, so no exact asymptotic expression is reported here.
2 DC2: Solving the 2-Dimensional Problem
DC2 learns the normalized projection of the target normal onto a two-dimensional subspace by adaptively querying the unit circle and updating a Bayesian posterior. Its noise-resilient procedure achieves logarithmic query complexity while maintaining an efficient piecewise-constant representation.
- Problem setup: DC2 estimates the normalized projection of h∗ onto span{e1,e2} using noisy membership queries on a two-dimensional subspace.The ambient space remains d-dimensional, but the subproblem is represented on the unit circle S1.
- Motivation: Repetitive querying increases the binary-search query complexity to O(log(1/ε)(loglog(1/ε)+log(1/δ))), making it theoretically and empirically suboptimal.The method repeats each query and uses majority voting to tolerate independent label flips.
- Guarantees: DC2 achieves query complexity O(log(1/ε) + log(1/δ)) under noise and reduces to binary search when ρ=0.The theorem guarantees an ε-accurate estimate with probability at least 1−δ; in the noiseless case, the guarantee holds with probability one.
- Algorithm: DC2 uses a Bayesian posterior initialized uniformly on S1, selects queries that split posterior mass equally, and returns the posterior maximizer.The posterior is updated after each noisy response according to Bayes’ theorem.
- Algorithm: The posterior remains piecewise constant over at most 2m sectors after m rounds, enabling query selection and updates through a compact representation.Each new query bisects the current posterior mass, and the noisy response rescales the two half-circles by factors determined by ρ.
3 Dimension Coupling Based Framework
Dimension Coupling reduces d-dimensional halfspace learning to at most d−1 two-dimensional projection problems arranged by a full binary tree. Aggregating these estimates yields a noise-resilient approximation whose error and confidence degrade predictably with dimension, while query and computational costs scale near-linearly.
- Scope: The construction applies to arbitrary orthonormal bases and estimates the coefficients of h∗ by partitioning the original task into smaller coupled problems.The 4-dimensional examples illustrate both balanced and sequential binary-tree schemes.
- Framework: DC breaks the d-dimensional problem into at most d−1 two-dimensional subproblems, each solved by DC2 and combined through a divide-and-conquer scheme.Each scheme corresponds to a full binary tree with d leaf nodes, and different tree shapes represent different aggregation orders.
- Framework: The framework repeatedly replaces two orthonormal vectors with their estimated normalized projection, reducing the effective representation dimension by one at each step.After d−1 replacements, the sole remaining vector is returned as the estimate of h∗.
- Guarantees: For any full-binary-tree aggregation scheme, DC calls DC2 d−1 times and guarantees estimation error at most 5ε(d−1) with probability at least 1−δ(d−1), when ε≤5/18.The bound assumes each DC2 call is within ε with probability at least 1−δ.
- Complexity: In the noiseless setting, DC has query and time complexity O(dlog(1/ε)), while the noisy query complexity scales as O(d(log(1/ε)+log(1/δ))).The computational cost inherits the repeated DC2 calls and depends on the selected implementation of the two-dimensional solver.
4 Empirical Results
DC achieves lower estimation error and faster execution than the evaluated baselines in noiseless and noisy query-synthesis experiments, including at dimension 1000.
- Experimental setup: The experiments evaluate estimation error, query complexity, and execution time using synthetically generated queries and fastest available MATLAB implementations for the baselines.Average errors and execution times are reported with 90% confidence intervals.
- Noiseless setting: Three orders of magnitude faster execution than other baselines in the noiseless setting, while also achieving lower estimation error.The comparison includes RANDOM-SAMPLING, UNCERTAINTY-SAMPLING, QUERY-BY-BAGGING, and SPECTRAL.
- Noisy setting: Two orders of magnitude smaller estimation error than other baselines at equal query budgets, while remaining around 100 times faster than three sampling methods.This comparison covers d = 25 and 50 with noise level ρ = 0.1.
- Noisy setting: At d = 1000, DC’s estimation error is one to three orders of magnitude smaller than REPETITIVE-DC at equal query counts as noise increases to ρ = 0.2.The reported range is one order at very small noise and three orders at ρ = 0.2.
5 Related Work
Related work contrasts passive and pool-based learning with query synthesis, which removes pool-size limits and supports applications requiring de novo queries. The paper positions DC as a near-optimal noise-resilient method addressing computational and noisy-learning challenges.
- Active learning: Classical PAC learning uses iid examples, whereas active learning seeks exponentially smaller sample complexity, ideally ˜O(dlog(1/ǫ)) for halfspaces.A sphere-packing argument gives a lower bound of Ω(dlog(1/ǫ)).
- Pool-based learning: Pool-based noisy learning of linear separators has been much less studied, and its dependence on noise remains poorly understood.The cited discussion contrasts this gap with limited exceptions in prior work.
- Query synthesis: Query synthesis lets learners request arbitrary unlabeled instances, eliminating pool-size limitations in applications such as automated science, robotics, and adversarial reverse engineering.Adversaries can use synthesized queries to identify linear separators and evade deployed classifiers.
- Paper contribution: The paper develops a noise-resilient active learner with a near-optimal algorithm that outperforms naive repetition and spectral heuristic methods in theory and practice.The comparison identifies Alabdulmohsin, Gao, and Zhang (2015) as the cited spectral heuristic work.
A Proof of Theorem 1
The proof analyzes DC2’s posterior updates under independent label flips by tracking preferred and unpreferred regions on the unit circle. It bounds the probability that a region away from the target retains excessive posterior mass after the prescribed number of queries.
- Noisy updates: Under noise, the posterior update has separate rules for correct and flipped responses, with independent flip probability ρ.The proof models flips using iid Bernoulli(ρ) variables and updates the posterior after each observed sign.
- Query geometry: Each query partitions the unit circle into preferred and unpreferred halves, and DC2 selects queries making their posterior measures equal.The preferred part contains hypotheses agreeing with the target query sign; the unpreferred part contains those disagreeing.
- Theorem conclusion: With T_ǫ,δ queries, the analysis targets the event that some y farther than the accuracy threshold has posterior at least that of h⊥, and bounds its probability by δ.The theorem’s proof concludes by substituting the bounds into the required inequality.
- Probability bounds: The proof tracks logarithmic posterior mass and bounds events where an uncut region is insufficiently preferred or retains large posterior probability.Chernoff bounds and a union bound control these events over the query sequence.
- Noiseless case: In the noiseless case, DC2 halves the admissible sector containing h⊥ after each round, producing the binary-search behavior illustrated by Figure 6.The posterior remains uniform on the surviving sector, and the next query is orthogonal to its midpoint.
B DC2 in the Noiseless Case
In the noiseless case, DC2 repeatedly halves the admissible sector for h⊥ on the unit circle, then returns an ǫ-accurate estimate. This yields linear-in-dimension query and computational complexity for DC.
- DC2 in the Noiseless Case: Each noiseless DC2 query halves the admissible sector containing h⊥, reducing the region from a semicircle to progressively smaller sectors.The query is orthogonal to the sector midpoint, and the observed sign selects the compatible half.
- DC2 in the Noiseless Case: With T_ǫ,δ = ⌈log2(1/ǫ)⌉ rounds, DC2 returns a vector within distance ǫ of h⊥.In the noiseless setting, the guarantee holds with probability one, so δ is irrelevant.
- DC2 in the Noiseless Case: DC2 can be implemented efficiently because its posterior is represented by the sector endpoints and each query is the orthogonal vector to the sector midpoint.This gives DC2 computational complexity O(log(1/ǫ)) when queries count as unit-cost operations.
- DC2 in the Noiseless Case: The resulting DC algorithm uses O(dlog 1/ǫ) queries and has computational complexity O(dlog 1/ǫ).
C Analysis of Repetitive Querying
Repetitive querying makes binary search noise-tolerant by replacing each query with R repetitions and using majority vote. A union-bound analysis determines the repetition cost needed for reliable answers.
- Analysis of Repetitive Querying: Majority voting repeats each binary-search query R times and uses the most frequent noisy response as the estimated outcome.Each individual response is correct with probability 1−ρ, where ρ<1/2.
- Analysis of Repetitive Querying: To make all n0 binary-search decisions correct with probability at least 1−δ, the analysis applies a union bound over the n0 majority votes.The resulting failure probability is bounded by n0e−2(1/2−ρ)2R.
- Analysis of Repetitive Querying: Because noiseless binary search uses n0=O(log(1/ǫ)) queries, repetitive querying requires O(log(1/ǫ)(loglog(1/ǫ)+log(1/δ))) total queries.
D Proof of Theorem 2
Theorem 2 analyzes DC by repeatedly merging orthonormal vectors with DC2 and tracking approximation error and success probability through the resulting d−1 calls.
- Proof of Theorem 2: DC begins with d vectors and performs exactly d−1 DC2 calls, because each call replaces two vectors with one and reduces the set size by one.
- Proof of Theorem 2: For an orthonormal input set, DC approximates the normalized orthogonal projection of h∗ onto the span of those vectors.This generalized statement underlies the induction used in the theorem proof.
- Proof of Theorem 2: If every DC2 call is within distance ǫ and ǫ≤5/18, DC achieves error at most 5ǫ(d−1) with probability at least 1−δ(d−1).
- Proof of Theorem 2: The induction combines the error from the recursive DC call with the projection error introduced when replacing two vectors by their DC2 output.The proof bounds the intermediate discrepancy by 5ǫ before propagating it through later rounds.