PaperlayerView exact revision on arXiv

Source-linked AI summary

Active and passive learning of linear separators under log-concave distributions

Maria Florina Balcan, Philip M. Long

arXiv:1211.1082v3cs.LGmath.STstat.ML

TL;DR

The paper addresses whether linear separators can be learned efficiently with optimal sample complexity and whether active learning can substantially reduce label requirements. It develops structural and margin-based analyses for log-concave distributions, yielding exponentially lower active label complexity and tight efficient PAC bounds, with extensions to noisy and nearly log-concave settings.

  • Problem

    Polynomial-time learning of linear separators had not achieved the known optimal sample complexity, while the scope of exponential active-learning improvements remained limited.

  • Method

    The paper combines structural results on disagreement regions under log-concave measures with margin-based active learning and a related localized analysis of passive learning.

  • Results

    Polynomial-time active learning uses O((d+log(1/δ)+log log(1/ε)) log(1/ε)) label requests, while efficient PAC learning achieves a matching sample-complexity bound up to constants.

  • Takeaways & Limitations

    The results establish exponential active-over-passive label savings and resolve the efficient PAC sample-complexity question for the uniform distribution in the unit ball.

  • Takeaways & Limitations

    The analysis is developed for log-concave or nearly log-concave distributions and the paper identifies extension to arbitrary distributions and broader concept spaces as an open direction.

Abstract

from arXiv · show

We provide new results concerning label efficient, polynomial time, passive and active learning of linear separators. We prove that active learning provides an exponential improvement over PAC (passive) learning of homogeneous linear separators under nearly log-concave distributions. Building on this, we provide a computationally efficient PAC algorithm with optimal (up to a constant factor) sample complexity for such problems. This resolves an open question concerning the sample complexity of efficient PAC algorithms under the uniform distribution in the unit ball. Moreover, it provides the first bound for a polynomial-time PAC algorithm that is tight for an interesting infinite class of hypothesis functions under a general and natural class of data-distributions, providing significant progress towards a longstanding open question. We also provide new bounds for active and passive learning in the case that the data might not be linearly separable, both in the agnostic case and and under the Tsybakov low-noise condition. To derive our results, we provide new structural results for (nearly) log-concave distributions, which might be of independent interest as well.

1. Introduction

The paper addresses longstanding sample-complexity gaps for efficient learning of linear separators and develops label-efficient active and passive methods under log-concave distributions. It also extends the analysis to noisy, nearly log-concave, and nonseparable settings.

  • Motivation: Polynomial-time PAC learning of linear separators had not matched the information-theoretic sample-complexity lower bound, including under the uniform distribution.The known efficient upper bound contains extra logarithmic factors relative to the lower bound.
  • Extensions: The paper extends active and passive-learning results to nonseparable data, Tsybakov low-noise settings, agnostic noise, and nearly log-concave distributions.It also derives disagreement-coefficient bounds and reports an Ω(d)-factor improvement over prior bounds.
  • Passive learning: The paper proves a tight, up-to-constant-factors sample-complexity bound for polynomial-time learning under zero-mean log-concave distributions.The bound is computationally efficient and distribution-specific, and provides a tight result for an infinite hypothesis class.
  • Active learning: O((d+log(1/δ)+log log(1/ε)) log(1/ε)) label requests suffice for polynomial-time active learning of homogeneous separators under log-concave distributions.This yields an exponential improvement over passive learning without increasing dependence on dimension d.
  • Active learning: A margin-based algorithm exploits a structural disagreement property: disagreement outside a margin proportional to the separators’ angle has probability at most cα.The result supports querying points near the hypothesized decision boundary.

2. Preliminaries and Notation

The paper studies binary classification with homogeneous linear separators under passive and pool-based active learning protocols. In the realizable case, labels come from a target separator; otherwise, performance is measured against the best separator in the class.

  • Setting: The hypothesis class consists of unit-norm homogeneous linear separators sign(w · x) over R^d.The goal is to output a separator with small classification error.
  • Learning protocols: Passive learning uses i.i.d. labeled examples, while active learning permits querying labels for selected examples from an unlabeled pool.The active protocol is pool-based.
  • Noise models: In the realizable case, labels are deterministic and generated by a target separator; in the non-realizable case, the learner competes with the best separator in the class.
  • Notation: For vectors u and v, disagreement is the probability that their separators assign different signs under a distribution, while θ(u,v) denotes their angle.

3. Log-Concave Densities

The paper develops structural facts for log-concave distributions, including a refined characterization of separator disagreement away from a narrow margin region. These properties support the later active and passive learning analyses.

  • Definitions: Log-concavity requires log f to be concave, while isotropy means zero mean and identity covariance.The paper focuses on log-concave or nearly log-concave distributions.
  • Examples: Gaussian, Logistic, and uniform distributions over convex sets are examples of log-concave distributions.
  • Known properties: All marginals of a log-concave distribution are log-concave, and isotropic distributions have isotropic marginals.
  • Disagreement geometry: For isotropic log-concave D, disagreement probability between two homogeneous separators is at least a universal constant times their angle.
  • Disagreement geometry: If two unit normals have angle α < π/2, disagreement points satisfying |v · x| ≥ c2α have probability at most c1α.This refined bound controls disagreement outside a margin band.
  • Significance: The refined characterization is more general and tighter than an earlier result for the uniform distribution in the unit ball, enabling tight passive and improved active-learning bounds.

4. Active Learning

The active learner progressively narrows a margin region and requests labels only for sampled points inside it. Under isotropic log-concave distributions, this yields a polynomial-time separator with logarithmic dependence on target accuracy.

  • Algorithm: The algorithm is analyzed for log-concave distributions, extending an earlier analysis restricted to the uniform distribution in the unit ball.
  • Algorithm: The margin-based algorithm samples from D, labels an initial set, and then queries only points satisfying |ŵ_k · x| < b_k.
  • Guarantee: O((d + log(1/δ) + log log(1/ε)) log(1/ε)) labeled examples suffice to find error at most ε with probability 1 − δ.The guarantee assumes isotropic log-concavity, d ≥ 4, and ε < 1/4.
  • Analysis: At each iteration, the margin-region samples control conditional error while the disagreement outside that region is bounded using the structural theorem.

5. Passive Learning

An analysis inspired by active learning gives optimal-up-to-constants sample complexity for polynomial-time passive learning of separators under zero-mean log-concave distributions. The guarantee applies to any algorithm returning a consistent hypothesis.

  • Analysis: The proof tracks intermediate hypotheses from the active-learning analysis across O(log(1/ε)) progressively refined stages.
  • Guarantee: Theorem 6 guarantees error at most ε with probability at least 1 − δ from C3(d + log(1/δ))/ε correctly classified examples.The result assumes d ≥ 4 and ε < 1/4.
  • Scope: The result applies to any algorithm that outputs a hypothesis consistent with the training examples, not only to the analyzed active learner.
  • Computational efficiency: The separators in Theorems 5 and 6 can be found in polynomial time, for example using linear programming.
  • Label efficiency: The active learner needs O(d/ε + log(1/δ)/ε) unlabeled examples overall, while requesting far fewer labels.In round k, it needs 2^k(d + ln[(1 + s − k)/δ]) unlabeled examples with high probability.

6. More Distributions

The paper extends efficient active and passive learning guarantees from log-concave distributions to admissible and nearly log-concave classes. Structural approximation results establish admissibility and light tails, enabling the resulting learning bounds.

  • Admissible distributions: Admissibility is defined through angle-disagreement, margin-disagreement, and one-dimensional density conditions.These conditions are sufficient for efficient learning guarantees.
  • Learning guarantees: O((d+log(1/δ)+log log(1/ε)) log(1/ε)) labeled examples suffice for polynomial-time active learning over any admissible distribution class.The corresponding passive-learning bound is also provided in the theorem, though the supplied passage truncates it.
  • Nearly log-concave distributions: β-log-concavity generalizes log-concavity, with log-concavity recovered when β = 0.The paper also gives mixtures of two suitably separated log-concave distributions as an O(1)-log-concave example.
  • Structural results: A β-log-concave density can be approximated by a log-concave density within multiplicative factor C = e^(β⌈log_2(d+1)⌉).The approximation also preserves a directional second-moment bound, and the dependence on dimension is exponential only in log d.
  • Structural results: For sufficiently small constant β, isotropic β-log-concave distributions are admissible and have light tails.This structural result supports applying the general admissible-distribution learning theorem.
  • Structural results: The approximation and projection arguments transfer angle-disagreement and density properties from log-concave to nearly log-concave distributions.These arguments underpin admissibility for the nearly log-concave class.
  • Learning guarantees: O((d+log(1/δ)+log log(1/ε)) log(1/ε)) labeled examples suffice for polynomial-time active learning under isotropic β-log-concavity.This follows by combining the admissibility theorem with the structural result for sufficiently small β.

7. Lower Bounds

The paper establishes information-theoretic lower bounds for passive and active learning of homogeneous linear separators under sufficiently nearly log-concave distributions. The passive result applies broadly when the covariance has full rank, with effectively lower dimension otherwise.

  • Lower-bound scope: Information-theoretic lower bounds apply to any procedure, not only computationally efficient algorithms.The bounds concern passive and active learning under β-log-concave distributions for sufficiently small β.
  • Passive learning: For any full-rank covariance β-log-concave distribution, passive learning of origin-centered linear separators requires the lower bound stated in Theorem 13.The supplied theorem passage truncates the numerical expression.
  • Active learning: Active learning of linear separators under β-log-concave distributions also satisfies the information-theoretic lower bound stated in Theorem 13.The supplied theorem passage truncates the numerical expression.
  • Scope: If the covariance matrix is rank-deficient, the effective number of dimensions is smaller than d, so the lower bound essentially extends across log-concave distributions.The dimension reduction is stated as an interpretation of the rank condition.

8. The inseparable case: Disagreement-based active learning

For inseparable data, the paper studies disagreement-based active learning through distribution-dependent capacity notions. It bounds these notions for isotropic nearly log-concave distributions and derives an agnostic active-learning consequence.

  • Capacity notions: Alexander capacity and disagreement coefficient quantify disagreement regions around a target classifier.They are used to analyze non-aggressive active-learning algorithms.
  • Capacity bound: Theorem 14 bounds the Alexander capacity for isotropic β-log-concave distributions by the expression stated in the theorem.The supplied passages split the bound across theorem fragments and do not preserve the complete expression.
  • Consequences: The capacity bound yields concrete label-complexity guarantees for several active-learning algorithms.The paper obtains these results by composing Theorem 14 with prior algorithmic analyses.
  • Consequences: For agnostic active learning under isotropic log-concave distributions, the paper reports ˜O(d^3/2(log^2(1/ε) + (ν/ε)^2)) label requests.This bound is obtained by composing the capacity result with a result of Dasgupta et al. (2007).

9. The Tsybakov condition

The paper analyzes linear classification under a Tsybakov noise condition with isotropic log-concave marginals. It gives active and passive bounds, including optimal guarantees when α = 0 and improved dimension dependence for α ≥ 0.

  • Noise condition: The optimal classifier is assumed to be linear, with known Tsybakov parameters α and a governing excess error.The supplied passage introduces the condition but truncates its formal inequality.
  • Method: The analysis strengthens a margin bound and combines it with prior lemmas and techniques to derive the Tsybakov results.This is the proof strategy stated before Theorem 15.
  • Bounds: When α = 0, active learning achieves excess error ε using O(log(1/ε))(d + log(s/δ)) labeled examples.The theorem also states a passive-learning bound, but the supplied passage truncates its expression.
  • Bounds: When α > 0, active learning achieves excess error ε using O((1/ε)^2α log^2(1/ε))(d + log(s/δ)) labeled examples.The guarantee holds with probability 1 − δ.
  • Implications: For α = 0, the analysis gives optimal active and passive bounds while improving dependence on d over previous results.For α ≥ 0, the active-learning bounds also improve dependence on d over previous work.

10. Discussion and Open Questions

The paper gives an efficient active learner with exponentially lower label complexity and connects this analysis to tight passive-learning bounds under log-concave distributions. It also identifies extensions to noisy settings and open computational questions.

  • Active learning: O((d+log(1/δ)+log log(1/ε)) log(1/ε)) labels suffice for active learning homogeneous separators under isotropic log-concave distributions.The algorithm uses polynomially many unlabeled examples and runs in polynomial time.
  • Passive learning: The passive-learning analysis uses a more aggressive localization of ERM than earlier analyses under nearly log-concave distributions.The authors identify extending this analysis to arbitrary distributions and broader concept spaces as an open question.
  • Noisy learning: New bounds cover active and passive learning under Tsybakov low noise and provide disagreement-coefficient implications for arbitrary noise.These results address settings where the data may not be linearly separable.
  • Open questions: Existing active algorithms under Massart and Tsybakov noise are not known to run in time poly(d,1/ε), and comparable passive guarantees are also unavailable for general ε.This computational limitation remains even when optimal sample complexity is ignored.

Appendix B. Proof of Lemma 3

The appendix proves that disagreement probability under isotropic log-concave distributions is controlled by the angle between unit vectors. This geometric relationship supports iterative accuracy guarantees for consistent classifiers.

  • Geometric lemma: cθ(v,u) ≤ d_D(u,v) for unit vectors u and v under isotropic log-concave D.The proof reduces the problem to a two-dimensional projection and lower-bounds mass in a disagreement region.
  • Sample complexity: Theorem 6 guarantees that C3(d+log(1/δ))/ε examples find a separator of error at most ε with probability at least 1−δ.The proof first handles isotropic distributions and then extends the argument using whitening.
  • Iterative analysis: After O(log(1/ε)) iterations, every classifier consistent with the accumulated training data has error at most ε with probability at least 1−δ.Each iteration contracts the error scale geometrically through the working sets W(k).
  • Sampling argument: The analysis obtains the required examples by sampling points in projected intervals of width 2b_k, whose probability is lower-bounded by a constant multiple of b_k.Chernoff bounds control the number of unlabeled examples needed to obtain the required labeled points.

D.1. Isotropic Nearly Log-concave distributions

This section develops structural properties of nearly log-concave distributions, including approximation by log-concave densities and geometric control of disagreement under covariance normalization. These properties enable the paper’s active-learning results beyond the isotropic case.

  • Nearly log-concave approximation: Every isotropic β-log-concave density f admits a log-concave density f̃ with f(x)/C ≤ f̃(x) ≤ Cf(x).The construction yields C=e^{β⌈log_2(d+1)⌉}.
  • Moment control: For unit vectors u, isotropic nearly log-concave densities satisfy a bounded second moment, ∫(u·x)^2f̃(x)dx ≤ C.This concentration property is used in the two-dimensional structural analysis.
  • Two-dimensional structure: Theorem 16 provides local lower-density and tail upper bounds for centered two-dimensional log-concave distributions under near-isotropy assumptions.In particular, part (i)(a) lower-bounds density near the origin, while part (i)(b) gives exponential tail decay.
  • Covariance normalization: Whitening transforms reduce arbitrary covariance matrices to isotropic position while preserving the relevant separator geometry.The section uses covariance estimation from polynomially many samples before applying isotropic structural results.
  • Learning consequences: Theorem 17 applies the structural results to obtain polynomial-time active and passive learning guarantees for zero-mean log-concave distributions.Its active-learning bound is O((d+log(1/δ)+log log(1/ε)) log(1/ε)) labeled examples.
  • Disagreement geometry: For log-concave distributions, disagreement probability is bounded below by a constant times the angle between unit vectors.Lemma 19 extends the geometric relationship needed by the active-learning theorem.

Appendix E. Lower Bounds

The lower-bound analysis uses packing numbers to establish passive and active sample-complexity limits, while later results extend the framework to noisy learning. The section also records algorithmic assumptions and margin-based bounds.

  • Packing lower bounds: The packing number MD(C,ε) measures the largest set of classifiers separated by more than ε under D.Packing lower bounds drive both passive and active sample-complexity lower bounds.
  • Non-isotropic distributions: Whitening preserves disagreement distances between separators, allowing isotropic packing constructions to transfer to arbitrary full-rank covariance matrices.The identity d_D(v,w)=d_D′(vΣ^{1/2},wΣ^{1/2}) supplies the transfer.
  • Learning lower bounds: For β-log-concave distributions with full-rank covariance, Theorem 13 gives lower bounds for both passive and active learning of origin-centered separators.The proof combines packing constructions with standard reductions from packing size to sample or query complexity.
  • Noise assumptions: The noisy-learning results rely on a linear optimal classifier and known Tsybakov parameters α and a.The paper notes that the α=0 assumption is more general than the well-known Massart condition.
  • Noisy learning: Under Tsybakov noise, active learning uses O((1/ε)^(2α) log^2(1/ε))(d+log(s/δ)) labels when α>0.For α=0, the theorem gives a separate active-learning bound with O(log(1/ε))(d+log(s/δ)) labels.
  • Algorithm: The margin-based active-learning algorithm samples broadly but requests labels only for examples with small current margin.Its inputs include sample sizes, cutoff values, hypothesis radii, and precision values.
  • Margin geometry: For isotropic log-concave D, disagreement at margin at least b is bounded by C5η exp(−C6b/η) when b≥cη.This theorem formalizes the decay of high-margin disagreement between nearby separators.
Loading 1211.1082v3…