PaperlayerView exact revision on arXiv

Source-linked AI summary

Learners that Use Little Information

Raef Bassily, Shay Moran, Ido Nachum, Jonathan Shafer, Amir Yehudayoff

arXiv:1710.05233v3cs.LGcs.AIcs.CRcs.ITmath.IT

TL;DR

The paper asks how learning is affected when algorithms use only a small amount of information from their samples. It defines d-bit information learners and proves that low mutual information supports generalization, while deriving sharp bounds and contrasting proper consistent, generic, and distribution-dependent learners. The results also expose limits for threshold ERMs and connections with privacy and compression.

  • Problem

    The paper studies whether learning algorithms that use little information from their input samples can still generalize and what learning capacity such restrictions permit.

    Source: §1 · p. 2

  • Method

    It measures sample–output dependence with mutual information, defines d-bit information learners, and analyzes them through multiple proofs plus upper- and lower-bound constructions.

    Source: §1 · p. 2, §1.1 · p. 3, §4 · p. 9

  • Results

    Low information yields generalization with sharp confidence and error dependencies, while threshold proper consistent ERMs require Ω(log log N) information and distribution-dependent VC learning needs O(d log(m)).

    Source: §1.1 · pp. 2–3

  • Takeaways & Limitations

    Information limits can control generalization, but their feasibility depends on learner requirements and the distribution-dependent setting.

    Source: §1.1 · p. 3

    The paper leaves open whether bounded-information learners can be both non-consistent or non-proper in the threshold setting.

    Source: §1.1 · p. 3, §6.4 · p. 23

Abstract

from arXiv · show

We study learning algorithms that are restricted to using a small amount of information from their input sample. We introduce a category of learning algorithms we term $d$-bit information learners, which are algorithms whose output conveys at most $d$ bits of information of their input. A central theme in this work is that such algorithms generalize. We focus on the learning capacity of these algorithms, and prove sample complexity bounds with tight dependencies on the confidence and error parameters. We also observe connections with well studied notions such as sample compression schemes, Occam's razor, PAC-Bayes and differential privacy. We discuss an approach that allows us to prove upper bounds on the amount of information that algorithms reveal about their inputs, and also provide a lower bound by showing a simple concept class for which every (possibly randomized) empirical risk minimizer must reveal a lot of information. On the other hand, we show that in the distribution-dependent setting every VC class has empirical risk minimizers that do not reveal a lot of information.

1. Introduction

The paper defines d-bit information learners through mutual information and studies why limiting information from the sample can promote generalization. It establishes sharp sample-complexity behavior, information lower and upper bounds, distribution-dependent results, and connections to compression, Occam’s razor, and privacy.

1. Introduction

  • Algorithms with at most d bits of mutual information about their samples form the paper’s class of d-bit information learners.The definition connects information-theoretic dependence between output and sample with learning-theoretic compression and privacy.Source: §1 · p. 2

1.1 Results

  • Low mutual information yields generalization, with four proofs emphasizing information theory, PAC-Bayes, decorrelation, and stability.The proofs use a KL-divergence argument, a decorrelation method, and additional perspectives on why low information limits overfitting.Source: §1.1 · p. 2
  • The sample-complexity dependence on confidence is sharp: an O(1)-bit learner can still have true error at least 1/2 with probability at least 1/m.This contrasts with finite-VC learning, where sample size grows only logarithmically with 1/δ.Source: §1.1 · p. 2
  • For thresholds over a domain of size N, every randomized or deterministic proper consistent ERM must reveal Ω(log log N) bits, leaving bounded-information proper consistent learning impossible on infinite domains.The paper explicitly leaves open whether bounded-information learners can exist when they are non-consistent or non-proper.Source: §1.1 · p. 3, §1.2 · p. 5
  • The generic consistent ERM can be information-optimal in some cases but unnecessarily revealing in others, while point functions separate bounded mutual information from pure differential privacy.For point functions, the generic ERM leaks at most 2 bits and achieves optimal PAC-learning sample complexity, whereas proper pure-private learning requires samples growing with domain size.Source: §1.1 · p. 3, The distribution-dependent setting · p. 3

The distribution-dependent setting.

  • In the distribution-dependent setting, every finite-VC class admits an approximately correct learner with mutual information O(d log(m)), independent of domain size.This contrasts with the threshold lower bound and shows that knowing the data distribution changes the information requirement.Source: The distribution-dependent setting · p. 3

1.2 Related Work

  • Information learners share limited dependence with sample compression schemes, but constant-size compression does not guarantee constant information leakage.Thresholds have an O(1)-size compression-based ERM even though no ERM for them is an O(1)-bit information learner.Source: §1.2 · pp. 3–4
  • The framework connects to Occam’s razor, PAC-Bayes, adaptive-data-analysis bias, and differential privacy, while the relation to approximate differential privacy remains incomplete.The paper also relates its threshold lower bound to prior approximate-private learning results and notes that approximate differential privacy need not imply bounded mutual information.Source: §1.2 · pp. 4–5

2. Preliminaries

This section defines the realizable learning setting, the information-theoretic quantities used to measure algorithm–sample dependence, and differential privacy. It also situates privacy’s generalization guarantees within existing learning theory.

2.1 Learning

  • A learner maps a sample to a possibly randomized hypothesis, and learning requires finite sample bounds for every realizable distribution at error ε and confidence δ.Proper learners output hypotheses in the class, while consistent learners have zero empirical error on realizable samples.Source: §2.1 · p. 6, §2.2 · p. 6

2.2 Information Theoretic Measures

  • Entropy measures the average number of bits needed to encode a discrete random variable.The section uses base-2 logarithms for this information measure.Source: §2.2 · p. 6
  • Mutual information measures the average shared random bits between variables and equals zero exactly when they are independent.It is represented through the joint distribution and the product of the marginals.Source: §2.2 · p. 6
  • KL-divergence measures a distance-like discrepancy between two measures, although it is not a metric and may be infinite.The paper uses KL-divergence as a foundational information-theoretic quantity.Source: §2.2 · p. 6

2.3 Differential Privacy

  • Differential privacy is a distributional-stability condition requiring similar output probabilities on datasets differing in one entry.The definition uses parameters α and β; β=0 is pure privacy, while β>0 is approximate privacy.Source: §2.3 · p. 7
  • Differential privacy has generalization guarantees and an extensive private-learning literature, but its learning-theoretic characterization remains incomplete.The section highlights open questions about private learning and distinguishes pure from approximate privacy in their relationship to mutual information.Source: §2.3 · p. 7

3. d-Bit Information Learners

The paper defines d-bit information learners by bounding mutual information between a learner’s output and its input sample, and shows that bounded information yields generalization. The resulting guarantees imply PAC learnability under sublinear information and improve in the realizable case.

3. d-Bit Information Learners

  • A d-bit information learner has mutual information at most d bits with its sample for every realizable distribution.The definition applies to possibly randomized learning algorithms and permits d to depend on sample size.Source: §3 · p. 8

3.1 Bounded Information Implies Generalization

  • Theorem 8 bounds the probability that empirical and true errors differ by more than ε in terms of d, ε, and sample size.The probability includes randomness from both the sample and the learner.Source: §3.1 · p. 8
  • Any concept class with a d-bit information learner using o(m) information is PAC learnable, with related arguments extending to multiclass classification and bounded losses.Source: §3.1 · p. 8
  • The sample-complexity dependence on ε is improvable in the realizable case when the learner always outputs a hypothesis with zero empirical error.Source: §3.1 · p. 8

Proof Sketch for Deterministic Algorithms

  • For deterministic learners, the proof concentrates on likely output hypotheses and applies Chernoff’s inequality with a union bound.Markov’s inequality first identifies a high-probability set of outputs of controlled size.Source: Proof Sketch for Deterministic… · p. 8

4. Proofs that Bounded Information Implies Generalization

The paper gives four proof perspectives for why bounded mutual information implies generalization, including KL control, decorrelation, stability, and PAC-Bayes. It also proves that the resulting sample-complexity bound is sharp.

4. Proofs that Bounded Information Implies Generalization

  • Four proofs establish bounded-information generalization through information-theoretic KL control, decorrelation, algorithmic stability, and PAC-Bayes.The first proof uses a KL-divergence event bound, while the others emphasize distinct conceptual connections.Source: §4 · p. 9

4.1 Proof I: Mutual Information and Independence

  • The KL-based proof transfers small event probabilities between distributions when their KL divergence is not too large.The argument generalizes independence: when mutual information is zero, fiber bounds directly control event probability.Source: §4.1 · pp. 9–10
  • The event-probability bound is tight when variables are highly dependent, as shown by the diagonal event for X = Y uniformly distributed over [n].Source: §4.1 · p. 10

4.2 The Sample Complexity Bound is Sharp

  • The generalization sample-complexity bound is sharp in its dependence on d and ε, and also in its dependence on confidence δ.The paper constructs an O(1)-information learner with zero empirical error that nevertheless has true error at least 1/2 with probability between 1/m and 4/m.Source: §4.2 · pp. 11–13
  • The sharpness construction uses subsets of a finite domain to define hypotheses and a learner that selects a consistent hypothesis from those sets.Source: §4.2 · pp. 12–13

5. A Lower Bound on Information

The paper proves that every proper consistent learner for thresholds can reveal substantial information on some realizable distribution, including randomized learners. It develops matrix and mutual-information tools to construct that hard distribution.

5. A Lower Bound on Information

  • For every proper consistent threshold learner, there is a realizable distribution under which the learner’s mutual information with the sample is large.The result applies to possibly randomized algorithms and therefore rules out uniformly low information for this learner class.Source: §5 · p. 13
  • The hard distribution is constructed from the matrix structure rather than chosen adaptively after observing samples.The paper identifies this nonadaptive construction as a central difficulty of the argument.Source: §5 · p. 13, §5.3 · p. 19

5.1 Warm Up

  • The warm-up identifies a row or column with many distinct algorithm outputs by analyzing a structured matrix summarizing learner behavior.A matrix lemma guarantees at least n + 1 distinct values in a suitable row or column.Source: §5.1 · p. 14

5.2 Framework for Lower Bounding Mutual Information

5.3 Proof for General Case

  • The randomized proof represents learner outputs as probability distributions in a symmetric matrix and finds a row with distributions concentrated on pairwise disjoint sets.This extends the deterministic warm-up to the general case.Source: §5.3 · pp. 18–19

6. Approaches for Proving Upper Bounds on Information

This section develops generic ways to upper-bound the information revealed by learners and applies them to thresholds, point functions, and privacy comparisons.

6. Approaches for Proving Upper Bounds on Information

  • A generic learner uniformly samples from hypotheses consistent with a realizable sample, yielding a proper and consistent ERM for finite hypothesis classes.For finite-VC classes, it PAC-learns with the standard unconstrained VC sample complexity.Source: §6 · p. 19

6.1 A Method for Upper Bounding Information

  • A mutual-information upper-bound lemma compares the learner’s conditional output distribution with an arbitrary reference distribution over hypotheses.The lemma is stated for algorithms mapping m labeled examples to hypotheses and uses the output marginal induced by the input distribution.Source: §6.1 · p. 20

Thresholds

  • For thresholds over [N], the generic learner uses log log(N) + O(1) bits for every sample size, matching the lower bound from Section 5.The proof applies the upper-bound lemma with a specially chosen reference distribution and the uniform consistent-hypothesis output distribution.Source: Thresholds · pp. 20–21

Point Functions

  • For point functions over [N], the generic learner uses at most 2 bits of mutual information whenever the sample size satisfies m ≤N/2.This yields a proper 2-bit information learner for the class under the stated realizable-distribution condition.Source: Point Functions · p. 21

Separtion between Differential Privacy and Bounded Information

  • The point-function result separates bounded-information learning from pure differential privacy: proper 2-bit learning is possible, whereas proper α-differentially private learning requires a larger sample complexity.The separation follows from known properties of VC classes and the cited differential-privacy result.Source: Separtion between Differential Privacy… · pp. 21–22

examples.

The generic learner can reveal substantially more information than necessary in some simple distributions, while distribution-dependent knowledge enables low-information proper consistent learning for every VC class.

6.3 The Generic Learner is Far from Optimal

  • The generic learner is therefore not always information-optimal, despite providing sharp upper bounds for some concept classes.The comparison is between the generic algorithm and a deterministic ERM designed for the same distributional setting.Source: §6.3 · pp. 22–23
  • In a simple threshold setting, the generic learner reveals roughly one to three bits of information, while a deterministic ERM for the same class uses at most 1 + log(m + 2) bits.The generic learner’s substantial information gain occurs when the sample contains exactly one non-special input, an event with probability approximately 1/e.Source: §6.3 · pp. 22–23

6.4 The Distribution-Dependent Setting

  • When the learner knows the input marginal distribution, every VC class of dimension d has a deterministic, proper, consistent learner using O(d log(m+1)) bits on realizable samples.The construction tests increasingly fine distribution-dependent nets until finding a consistent hypothesis; it stops with probability one.Source: §6.4 · pp. 23–24
  • The distribution-dependent theorem does not imply a single randomized learner with small information for every distribution.The threshold example shows that exchanging the order of the distribution and learner choices through a minimax argument is invalid here.Source: §6.4 · p. 23

A.1 Proof II: De-correlating

A de-correlation lemma replaces algorithmic randomness with a variable sampled independently of the input while preserving the joint output behavior and controlling residual entropy.

A.1 Proof II: De-correlating

  • The lemma constructs Z independent of X such that Y is a deterministic function of (X, Z).This represents Z as random coins sampled before observing the input while preserving the algorithm’s functionality.Source: §A.1 · p. 26
  • The construction bounds the conditional entropy by H(Y|Z) ≤ I(X,Y) + log(I(X,Y) + 1) + O(1).Conditioned on Z, the algorithm has only a small number of possible outputs on average, which supports the generalization proof.Source: §A.1 · p. 26

A.2 Proof III: Stability

The stability-based proof connects bounded mutual information to generalization by comparing errors on fresh examples with errors on individual training examples.

A.2 Proof III: Stability

  • The stability approach proves a generalization relation for d-bit information learners using parameters slightly different from those in Theorem 8.Its setup assumes an i.i.d. sample and compares the algorithm’s output after sample-coordinate replacements and fresh draws.Source: §A.2 · pp. 26–27
  • The argument uses independence, conditioning, distributional identities, and Cauchy-Schwarz to derive the stability bound.The proof explicitly invokes independence of sample coordinates and total-variation/KL notation for the distributional comparisons.Source: §A.2 · pp. 26–27
  • The proof analyzes the expected difference between fresh-sample error and training-example error, averaged over the sample, learner, and fresh example.The target quantity is E S,z,A[c err (A(S); z) − c err (A(S); Si)].Source: §A.2 · pp. 26–28

A.3 Proof IV: PAC-Bayes

The proof connects information learners to PAC-Bayes by treating the learner’s marginal output as a prior and its sample-conditional output as a posterior. This yields a generalization bound through their KL-divergence, with the information-theoretic step relating mutual information to KL-divergence.

A.3 Proof IV: PAC-Bayes

  • PAC-Bayes bounds the generalization error of every randomized hypothesis distribution using its KL-divergence from a fixed prior.The theorem applies simultaneously to all posterior distributions with high probability over the sample.Source: §A.3 · p. 28
  • The learner’s marginal output distribution serves as the prior, while its sample-conditioned output distribution serves as the posterior.This Bayesian interpretation makes the prior sample-independent and allows the posterior to depend on the observed sample.Source: §A.3 · pp. 28–29
  • The proof converts the mutual information of a d-bit information learner into a KL-divergence expression and applies PAC-Bayes to bound expected generalization error.The resulting bound holds with probability at least 1 −δ over the sample and takes expectation over hypotheses drawn from the conditional output distribution.Source: §A.3 · pp. 28–29

Appendix B. Confidence Amplification

The appendix shows that standard confidence amplification extends to information learners at modest information cost. Repeated subsampling, independent learning, and validation produce high-confidence hypotheses while controlling the learner’s information usage.

Appendix B. Confidence Amplification

  • Confidence amplification converts a learner succeeding with probability 1/2 into one succeeding with probability at least 1 −δ at error ε.The amplified algorithm uses a number of examples and information bits specified by the theorem’s bound.Source: Appendix B · p. 29
  • The procedure sets k = ⌈log(2/δ)⌉, runs the learner independently on k subsamples, and validates the resulting hypotheses on a separate set.It outputs the candidate with minimal empirical error on the validation set.Source: Appendix B · p. 29
  • The validation set is independent of the subsamples and learned hypotheses, enabling the standard Chernoff-plus-union-bound analysis.This independence is used to establish the theorem’s first claim and support the information analysis for the second.Source: Appendix B · pp. 29–30
  • The information accounting includes the learners’ mutual information on their subsamples and the conditional entropy of the selected hypothesis.The displayed decomposition tracks the information revealed by the amplified procedure.Source: Appendix B · p. 30

Related papers

Loading 1710.05233v3…