A Direct Sum Result for the Information Complexity of Learning

1. Introduction

• Information complexity is the minimum information a consistent and proper learner must retain about its training sample.It is defined by minimizing the worst-case mutual information over such algorithms and input distributions.Source: §1 · p. 2
• VC dimension motivates the central question because it characterizes PAC learnability and determines sample complexity when learning is possible.The paper asks how this standard complexity measure relates to information complexity.Source: §1 · p. 2
• Theorem 1 gives VC-dimension-d classes for which consistent and proper learners must retain large information, including randomized algorithms.The result extends a weaker d = 1 bound of Bassily et al. (2018) and separates information complexity from sample compression schemes.Source: §1 · p. 3
• For product classes formed on disjoint domains, the paper proves that information complexity sums across component classes.This direct-sum phenomenon is the paper’s general framework for combining learning problems.Source: §1 · p. 3

Related work

• The related-work discussion distinguishes information complexity from sample compression while connecting it to Occam’s razor and differential privacy.The lower bound also transfers to Occam-style encoding complexity, and the authors suggest possible direct-sum extensions to differential privacy.Source: Related work · pp. 3–4

Proof Outline

• The proof improves the threshold lower bound, constructs direct sums of threshold classes with VC dimension d, and applies a minimax argument over distributions over distributions.The direct-sum theorem is the main technical contribution, with conditions verified for the threshold construction.Source: Proof Outline · p. 4

STANDARD NOTATION

• The notation introduces finite-support distributions and their i.i.d. sample distributions over a domain.The support of a probability function contains its positive-probability elements, while Δ(X) denotes finite-support probability mass functions.Source: STANDARD NOTATION · p. 4

INFORMATION THEORY

• Entropy and mutual information provide the information-theoretic quantities used to measure dependence between samples and learner outputs.Mutual information is defined as I(X;Y) = H(X)+H(Y)−H(X,Y).Source: INFORMATION THEORY · p. 5

LEARNING THEORY

• A learning algorithm maps realizable samples to hypotheses, is consistent when it matches every sample label, and is proper when its output belongs to the hypothesis class.A distribution is realizable when some hypothesis agrees with every point in its support.Source: LEARNING THEORY · p. 5
• VC dimension is the largest size of a set shattered by a binary hypothesis class.Shattering means the restricted class realizes every binary labeling on that set.Source: LEARNING THEORY · p. 5

INFORMATION COMPLEXITY

• Information complexity is the minimum worst-case mutual information retained by a consistent and proper learner over realizable input distributions.An algorithm retains at most d bits when the mutual information is at most d for every allowed distribution.Source: INFORMATION COMPLEXITY · pp. 5–6

Threshold class

• The analysis begins with thresholds T_n over a domain of size 2^n, consisting of monotone increasing Boolean functions.The class is written as T_n = {f_k} over X = [2^n].Source: §3 · p. 6

Threshold lower bound

• Theorem 11 states that for any possibly randomized proper and consistent learning algorithm A for Tn with sample size m ≥ 2, there exists a distribution p ∈ ∆Tn.Source: §3 · p. 6

Improvement over prior work

• The improvement removes the earlier dependence on conditioning on a low-probability event, which produced a quantitatively weaker bound.Bassily et al. (2018) used an event of probability O(1/m^2).Source: §3 · p. 6

Proof technique

• Randomly permuting the sample cannot increase mutual information, so information-minimizing learners need not exploit the order of examples.The symmetrized learner applies a uniformly random permutation independently of the sample and the learner’s random coins.Source: §3 · p. 6

Proof strategy

• A reduction from thresholds aims to show that d threshold components require d times the information needed for one threshold class.The first direct-sum theorem separates mutual information contributions from the summands.Source: §4 · p. 7

Product classes

• For disjoint domains, a product hypothesis outputs the component h_i on inputs belonging to X_i, and the learner’s output is A(S) = (h_1,...,h_d).Each S_i contains examples from X_i × Y, with M_i = |S_i| examples.Source: §4 · p. 7

Direct-sum theorem

• The product class’s information complexity is roughly the sum of the information complexities of its component classes.This is the section’s stated direct-sum contribution.Source: §4 · p. 7

Information decomposition

• Conditioning on examples from other components creates a family of implicitly sample-dependent algorithms, but the theorem shows that only the number of examples assigned to a component matters.This is the key simplification in applying the chain rule to the product learner.Source: §4 · p. 8

Minimax construction

• A direct product of individually hard distributions fails because no single distribution is hard for every algorithm; the construction instead uses a distribution over distributions.For thresholds, every algorithm has a hard distribution, but every fixed distribution also admits a low-information algorithm with O(1) information.Source: §4 · p. 8
• Sion’s minimax theorem supplies a single distribution on distributions that yields high expected information cost for every algorithm.This extension is needed because the minimax relation does not hold directly between distributions and algorithms in this setting.Source: §4 · p. 8

Random sample sizes

• The framework randomizes the sample size because each hard distribution is tailored to a particular m, and it formalizes learners as vectors of algorithms indexed by sample size.The resulting lemma supports direct-sum hypotheses under a fixed distribution over sample sizes.Source: §4 · pp. 8–9

• Tn,d is the d-fold product of Tn over a domain of size d · 2^n, with one threshold component assigned to each block.Source: §5 · p. 9
• VC(Tn,d) = d.Source: §5 · p. 9
• Lemma 21 supplies a stronger threshold lower bound for possibly randomized consistent and proper learners across a range of sample sizes.Source: §5 · p. 9
• For thresholds, the proof establishes a distribution under which the mutual information is at least Ω(log n), enabling the product-class lower bound.Source: §5 · p. 10
• Theorem 1 follows by applying Theorem 18 to the product class Tn,d after establishing the required condition for products of d thresholds.Source: §5 · pp. 9–10

• Extending the VC-class lower bound to learners that are not necessarily proper or consistent is proposed as a direct continuation.Source: §6 · p. 10
• For thresholds, a randomized consistent non-proper algorithm has mutual information O(m), showing that the lower bound does not extend under the same assumptions.Source: §6 · p. 10
• The paper proposes determining whether its lower bound is sharp and constructing algorithms that attain minimum information complexity through upper bounds.Source: §6 · p. 10
• It also asks whether low information complexity is necessary for learnability, potentially making the two concepts equivalent.Source: §6 · p. 11

• Data processing maps the selected sample event to an index, while disjoint output events yield the lower bound through Lemma 23.Source: §A.1 · pp. 12, 14
• The proof represents learner outputs on threshold samples using a symmetric matrix whose entries are probability distributions over hypotheses.Source: §A.1 · pp. 12–13
• A suitable row or column contains many output distributions supported on pairwise disjoint hypothesis sets, which creates distinguishable learner outputs.Source: §A.1 · p. 13
• A carefully chosen distribution over realizable samples and an event indicator decompose the mutual information through conditional mutual information and positivity.Source: §A.1 · pp. 13–14
• Consequently, every consistent learner for Tn admits a distribution p for which its input-output mutual information satisfies the desired lower bound, including randomized algorithms via Lemma 12.Source: §A.1 · pp. 13–14

• For a product class H, its VC dimension equals the sum of the component VC dimensions.Source: §A.2 · p. 15
• The chain rule expands the mutual information between the full sample and the vector of component hypotheses into componentwise terms.Source: §A.2 · p. 15
• Because each component sample is independent of the earlier components conditional on its associated distribution, the decomposition can be bounded component by component.Source: §A.2 · p. 15
• Taking expectations over the component distributions yields the summed lower bound, completing the direct-sum proof.Source: §A.2 · pp. 15–16
• In the component analysis, the other subsamples can be treated as random coins, reducing each hypothesis component to a randomized learner on its own subsample.Source: §A.2 · p. 16

Minimax setup

• The algorithm space is compact and convex because randomized algorithms correspond to conditional probabilities over finitely many realizable samples.It is viewed as a product of finite-dimensional simplices in R^k with the ℓ1 metric.Source: §A.3 · p. 17
• Mutual information is convex in the algorithm and linear, hence concave, in the distribution, supplying the relevant minimax properties.The argument invokes mutual-information convexity and linearity of expectation in the distribution.Source: §A.3 · p. 18
• The proof verifies continuity and applies Sion’s minimax theorem after choosing compatible topologies on the algorithm and distribution spaces.Uniform continuity follows from compactness, while the distribution space is treated with an ℓ1-induced metric.Source: §A.3 · pp. 17–18

Randomized construction

• For the sample-size-two construction, the algorithm randomizes over an integer and a permutation when the sample has one zero-labeled and one one-labeled example.Otherwise it returns an arbitrary hypothesis consistent with the sample; the proof tracks the hidden index, ordering, and position bit.Source: §A.3 · p. 18

Information bound

• The information inequalities use independence, data processing, bijectivity, conditional mutual information, and the chain rule before being combined into the final bound.The last step explicitly chains the preceding inequalities.Source: §A.3 · pp. 18–19

Sampling concentration

• Claim B.1 analyzes the number of times an integer is sampled under independent uniform draws from [d].Its proof introduces indicator variables and invokes Hoeffding’s inequality.Source: Appendix B · p. 20

Information theory

• The appendix records auxiliary identities and inequalities for random variables, including a log-sum-based bound on mutual information.The derivations also use assumptions and standard random-variable relations.Source: Appendix B · pp. 20–22

Minimax theorems

• The appendix states von Neumann’s and Sion’s minimax theorems, including compactness, convexity, quasi-convex-concavity, and semicontinuity conditions.These theorems provide the formal minimax tools used in the main proofs.Source: Appendix B · p. 22

Information theory

• Mutual information is concave in the input distribution and convex in the conditional distribution defining the channel.This is stated as a standard result attributed to Cover and Thomas (2006).Source: Appendix B · p. 22