PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Poisson Binomial Distributions

Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio

arXiv:1107.2702v4cs.DScs.LGmath.STstat.TH

TL;DR

Learning an unknown Poisson Binomial Distribution was poorly understood despite the class's basic structure. The paper uses structural properties of PBDs to construct learners, including one with sample complexity independent of n. Its sample bound is essentially optimal, while the paper leaves open whether the efficiency of its non-proper learner can be combined with the sample bound of its proper learner.

  • Problem

    Learning an unknown PBD was poorly understood, despite PBDs being a basic class of discrete distributions.

    Source: §1 · p. 2

  • Method

    The approach uses PBD structure, including unimodality and a sparse-versus-heavy-Binomial cover, to build learning hypotheses.

    Source: §2.1 · p. 7, §2.2 · p. 10

  • Results

    ˜O(1/ε^2) samples independent of n suffice, and Ω(1/ε^2) samples are necessary, making the second algorithm essentially sample-optimal.

    Source: §1.1 · pp. 2–3

  • Takeaways & Limitations

    The results essentially settle sample complexity for learning PBDs, while the paper identifies combining the non-proper algorithm's efficiency with the proper algorithm's sample bound as an open goal.

    Source: §4 · p. 24

    The non-proper learner is more computationally efficient but uses a factor of 1/ε more samples than the proper learner.

    Source: §4 · p. 24

Abstract

from arXiv · show

We consider a basic problem in unsupervised learning: learning an unknown \emph{Poisson Binomial Distribution}. A Poisson Binomial Distribution (PBD) over $\{0,1,\dots,n\}$ is the distribution of a sum of $n$ independent Bernoulli random variables which may have arbitrary, potentially non-equal, expectations. These distributions were first studied by S. Poisson in 1837 \cite{Poisson:37} and are a natural $n$-parameter generalization of the familiar Binomial Distribution. Surprisingly, prior to our work this basic learning problem was poorly understood, and known results for it were far from optimal. We essentially settle the complexity of the learning problem for this basic class of distributions. As our first main result we give a highly efficient algorithm which learns to $\eps$-accuracy (with respect to the total variation distance) using $\tilde{O}(1/\eps^3)$ samples \emph{independent of $n$}. The running time of the algorithm is \emph{quasilinear} in the size of its input data, i.e., $\tilde{O}(\log(n)/\eps^3)$ bit-operations. (Observe that each draw from the distribution is a $\log(n)$-bit string.) Our second main result is a {\em proper} learning algorithm that learns to $\eps$-accuracy using $\tilde{O}(1/\eps^2)$ samples, and runs in time $(1/\eps)^{\poly (\log (1/\eps))} \cdot \log n$. This is nearly optimal, since any algorithm {for this problem} must use $\Omega(1/\eps^2)$ samples. We also give positive and negative results for some extensions of this learning problem to weighted sums of independent Bernoulli random variables.

1 Introduction

The paper studies learning unknown Poisson Binomial Distributions (PBDs), a basic but previously poorly understood class, and gives algorithms whose sample complexity can be independent of the number of Bernoulli variables. It also relates these results to prior approximations and develops a cover-based learning approach.

1 Introduction.

  • PBD learning had been poorly understood despite the class's basic structure and applications, motivating the question of whether accurate estimation can use samples independent of population size.The introduction frames this question through weekly newspaper readership counts.Source: §1 · pp. 1–2

1.4 Preliminaries.

  • The paper formalizes learning as PAC-style estimation from independent samples, requiring total variation error at most ε, and defines PBDs as sums of independent Bernoulli variables.A proper learner outputs a hypothesis that is itself a PBD.Source: §1 · p. 2, §1.4 · p. 5

1.1 Our results.

  • The paper gives a PBD learner using ˜O(1/ε^2) samples independent of n, and argues this is essentially sample-optimal because Ω(1/ε^2) samples are necessary.For constant confidence, the first algorithm's bit-operation count is quasilinear in its input length.Source: §1.1 · pp. 2–3

1.2 Related work.

  • Prior Poisson, Normal, and Binomial approximations capture structural information but do not achieve arbitrary-accuracy approximation of an unknown PBD.The paper contrasts these approaches with learning the full distribution from samples.Source: §1.2 · pp. 3–4

1.3 Our approach.

  • The learning approach uses a structural cover: it learns a sparse-form case with a unimodal learner and uses a translated Poisson hypothesis for the heavy-Binomial case.It then uses hypothesis testing to select between the two hypotheses.Source: §1.3 · p. 4

2 Learning a sum of Bernoulli random variables from poly(1/ǫ) samples

This section develops PBD learning methods using a cover of sparse and heavy-binomial cases and competition-based hypothesis testing to establish non-proper and proper learning guarantees. The proper learner combines sparse-PBD hypotheses with translated-Poisson and nearby binomial hypotheses.

2 Learning a sum of Bernoulli random variables from poly(1/ǫ) samples

  • The cover divides candidate PBDs into sparse and k-heavy Binomial forms, and if no sparse-form neighbor exists, a heavy-form neighbor has mean error O(1) and variance error O(1 + ε′(1 + σ²)).Here k ≤ C/ε′; the authors extend the earlier cover statement to establish the mean-and-variance guarantee.Source: §2 · pp. 6–7
  • Learn-PBD runs sparse and translated-Poisson learners, then chooses one hypothesis; both learners and the chooser use succinct descriptions to keep running time logarithmic in n.The sparse learner is intended for targets close to a sparse-form cover member, while the Poisson learner handles targets not close to one.Source: §2 · p. 7

2.1 Learning when X is close to a sparse form PBD.

  • When X is ε′-close to a sparse-form cover member, Learn-SparseX returns, with probability at least 1−δ′, a hypothesis within c1ε′ TV whose support lies within that member’s support.It truncates tail mass to obtain a unimodal conditional distribution and applies Birgé’s learner when the resulting interval has length O(1/ε′³).Source: §2.1 · pp. 8–10

2.2 Learning when X is close to a k-heavy Binomial Form PBD.

  • With O(log(1/δ′)/ε′²) samples, Learn-PoissonX returns a translated-Poisson hypothesis within c2ε′ TV with probability at least 1−δ′ when X is not sparse-close, using mean and variance estimates accurate to ε′σ and ε′σ².The hypothesis uses the estimated mean and variance as its parameters.Source: §2.2 · pp. 10, 13

2.3 Hypothesis testing.

  • If one candidate is within ε′ of X, Choose-Hypothesis returns a candidate within 6ε′ with probability at least 1 − δ′.The routine compares two hypotheses using samples from X.Source: §2.3 · p. 14
  • With probability at least 1 − δ, a tournament over an ε-cover returns a cover distribution within 6ε of X.The tournament runs pairwise competitions and returns a distribution that was never defeated.Source: §2.3 · p. 15

2.4 Proof of Theorem 1.

  • The non-proper algorithm runs in ˜O(1/ε^3 · log n · log^2(1/δ)) time.It compares a sparse hypothesis with an efficiently evaluated approximation to the translated Poisson hypothesis.Source: §2.4 · pp. 16–17
  • Proper-Learn-Sparse uses ˜O(1/ε^2) · log(1/δ) samples and, when X is ε-close to a covered sparse PBD, outputs a sparse PBD within 6ε with probability at least 1 − δ.The procedure uses a tournament over shifted sparse-PBD candidates.Source: §2.4 · pp. 17–18
  • Locate-Binomial converts the translated Poisson hypothesis into a Binomial distribution with at most n trials that is O(ε)-close to X under its working assumptions.Its guarantee applies when X is not ε-close to a sparse-form distribution in the cover; the procedure uses the learned mean and variance without additional samples.Source: §2.4 · pp. 18–19
  • The algorithm runs Proper-Learn-Sparse and Learn-Poisson, then chooses between their hypotheses; if it selects the translated-Poisson hypothesis, it converts it to a close binomial.The analyses tune ε and δ so that, with probability at least 1 − δ, the output is ε-close to the unknown distribution.Source: §2.4 · p. 21
  • Õ(1/ε²) samples multiplied by log(1/δ) suffice for the proper learner, which runs in time specified in the theorem.The supplied running-time expression is truncated across passages, so its form cannot be reliably stated.Source: §2.4 · p. 21

3 Learning weighted sums of independent Bernoullis

The section studies weighted sums of independent Bernoulli variables, finding efficient learning when weights take few distinct values and a linear-sample lower bound for a simple many-weight case.

3.1 Learning sums of weighted independent Bernoulli random variables with few distinct weights

  • With at most k distinct weights, a weighted sum can be learned using O(log n) samples in time poly(n).The learner receives n, the weights, and independent draws from the target; its hypothesis is a vector defining independent Bernoulli variables within ε total variation distance.Source: §3 · p. 21, §3.1 · pp. 21–22
  • The few-weight algorithm constructs an ε-cover of candidate distributions and runs pairwise hypothesis tests to select a close candidate.The proof groups variables by distinct weight and forms candidate sums from covers for each group.Source: §3.1 · p. 22

3.2 Sample complexity lower bound for learning sums of weighted independent Bernoulli random variables

  • With n distinct weights i, learning the weighted sum to constant accuracy requires Ω(n) samples.The lower bound holds even when the i-th weight is simply i.Source: §3.2 · p. 23

4 Conclusion and open problems

The paper places its PBD results alongside later work on related distribution classes and identifies open problems in efficiency and sample-complexity bounds.

4 Conclusion and open problems

  • For sums of independent integer-valued variables supported on {0, …, k−1}, gives an n-independent sample bound polynomial in k and 1/ε.The k=2 case corresponds to Poisson Binomial Distributions.Source: §4 · p. 24
  • The non-proper PBD learner is more computationally efficient than the proper learner but uses a factor of 1/ε more samples; achieving both advantages remains open.The proposed goal is an O(1/ε^2)-sample algorithm with Õ(log(n)/ε^2) bit operations, ideally proper.Source: §4 · p. 24
  • A further open problem is determining the correct polynomial dependence on k and 1/ε for that generalized learning problem.Source: §4 · p. 24

A Extension of the Cover Theorem: Proof of Theorem 4

This appendix establishes an additional property of the PBD cover by tracing its construction through two filtering stages and bounding changes to mean and variance.

A Extension of the Cover Theorem: Proof of Theorem 4

  • The large cover contains sparse and heavy Binomial-form PBDs, and the small cover retains a close sparse representative for each sparse candidate.The small ε-cover is a subset of the large ε/2-cover; the argument transfers the desired cover property from the larger cover to the smaller one.Source: A Extension of the Cover Theorem:… · p. 28
  • The proof states an O(1 + ε · (1 + σ²)) bound and concludes the proof of Theorem 4.Source: A Extension of the Cover Theorem:… · pp. 28, 30
  • Stage 1 rounds probabilities near 0 or 1 while limiting each change to 1/k and the total change in their sums to 1/k.The rounding maps probabilities near 0 to 0 or 1/k, and those near 1 to 1−1/k or 1.Source: A Extension of the Cover Theorem:… · p. 28
  • Stage 2 returns heavy Binomial form when more than k^3 intermediate probabilities remain, and sparse form otherwise.The proof of the added guarantee focuses on the heavy Binomial case.Source: A Extension of the Cover Theorem:… · p. 30

B Birg´e’s theorem: Learning unimodal distributions

This appendix explains how Birgé’s method yields an efficient learner for unimodal distributions, from error guarantees to locating the mode and constructing the hypothesis.

B Birgé’s theorem: Learning unimodal distributions

  • With m = O(log(n)/ε^3) samples, Birgé’s algorithm has expected variation error O(ε); repetition and hypothesis testing raise the success probability to at least 1−δ.The resulting sample complexity also contains a second 1/δ term, and the running time depends quadratically on log(1/δ).Source: B Birg´e’s theorem: Learning unimodal… · p. 30
  • The algorithm locates an approximate mode using binary searches over sorted samples, computing convex-minorant differences in Õ((log n)m) bit operations.A second search uses at most log(1/ε) stages to minimize the mode-guessing function to additive ε.Source: B Birg´e’s theorem: Learning unimodal… · pp. 30–31
  • Once the mode estimate is found, the hypothesis is the derivative of a curve built from the empirical CDF’s convex minorant on one side and convex majorant on the other.The resulting hypothesis is a collection of uniform distributions.Source: B Birg´e’s theorem: Learning unimodal… · p. 31

C Efficient Evaluation of the Poisson Distribution

This section presents an efficient algorithm for additively approximating the Poisson probability mass function. Its approach rewrites the target probability and approximates its exponent rather than computing its factors separately.

C Efficient Evaluation of the Poisson Distribution

  • Theorem 6 gives an algorithm to estimate a Poisson probability, with running time ˜O(⟨t⟩3 + ⟨k⟩·⟨t⟩ + ⟨λ⟩·⟨t⟩).The input includes rational λ > 0 and integers k ≥ 0 and t > 0.Source: C Efficient Evaluation of the Poisson… · p. 31
  • The algorithm avoids separately computing e^-λ, λ^k, and k!, which would take time exponential in the description complexity of k and λ.Instead, it rewrites the target probability and approximates the exponent.Source: C Efficient Evaluation of the Poisson… · p. 31
  • The exponent approximation uses a truncated Stirling series for ln(k!) and approximates its terms, logarithms, and 2π.The resulting exponent estimate has bit complexity ˜O(⟨k⟩ + ⟨λ⟩ + ⟨t⟩) and is computable in time ˜O(⟨k⟩·⟨t⟩ + ⟨λ⟩ + ⟨t⟩3).Source: C Efficient Evaluation of the Poisson… · pp. 31, 33, 34

Related papers

Loading 1107.2702v4…