PaperlayerView exact revision on arXiv

Source-linked AI summary

Chaining Mutual Information and Tightening Generalization Bounds

Amir R. Asadi, Emmanuel Abbe, Sergio Verdú

arXiv:1806.03803v2cs.LGcs.ITmath.ITmath.PRstat.ML

TL;DR

Classical generalization bounds do not fully explain learning successes, and existing approaches separately address hypothesis dependencies and algorithm input-output dependence. The paper combines chaining with mutual information to bound generalization error using both. It reports an example where the bound significantly outperforms both earlier bounds and a corollary tightening Dudley’s inequality for algorithms that choose from a small subset with high probability.

  • Problem

    Classical bounds leave some learning successes unexplained, while chaining and mutual information address hypothesis dependencies and algorithm input-output dependence separately.

    Source: §1.1 · pp. 1–2

  • Method

    The paper combines chaining with mutual information to derive a generalization bound that accounts for both hypothesis dependencies and algorithm input-output dependence.

    Source: §2 · p. 5

  • Results

    The chained mutual information bound significantly outperforms previous bounds in an example, and a corollary tightens Dudley’s inequality when the output lies in a small subset with high probability.

    Source: §5 · p. 9

  • Takeaways & Limitations

    The bound combines algorithm dependence with hypothesis-dependency information, and the small-subset property yields a tightened Dudley inequality.

    Source: §5 · p. 9

    The results assume a separable process, which the paper describes as a technical assumption holding in almost all cases of interest.

    Source: §2 · p. 4

Abstract

from arXiv · show

Bounding the generalization error of learning algorithms has a long history, which yet falls short in explaining various generalization successes including those of deep learning. Two important difficulties are (i) exploiting the dependencies between the hypotheses, (ii) exploiting the dependence between the algorithm's input and output. Progress on the first point was made with the chaining method, originating from the work of Kolmogorov, and used in the VC-dimension bound. More recently, progress on the second point was made with the mutual information method by Russo and Zou '15. Yet, these two methods are currently disjoint. In this paper, we introduce a technique to combine the chaining and mutual information methods, to obtain a generalization bound that is both algorithm-dependent and that exploits the dependencies between the hypotheses. We provide an example in which our bound significantly outperforms both the chaining and the mutual information bounds. As a corollary, we tighten Dudley's inequality when the learning algorithm chooses its output from a small subset of hypotheses with high probability.

1 Introduction

The introduction motivates tighter generalization bounds by highlighting two gaps: many bounds ignore dependencies among hypotheses or the algorithm’s input-output dependence. The paper combines chaining and mutual information to address both, and positions the result alongside related work and its learning framework.

1.1 Motivation

  • Classical bounds can be too pessimistic because they bound errors uniformly over hypotheses rather than the error of the algorithm-selected hypothesis.Chaining exploits dependence among hypotheses, while mutual information can tighten bounds when the output depends on the data.Source: §1.1 · pp. 2–3

1.2 This paper

  • The chained mutual information bound captures both dependencies among hypotheses and the dependence between algorithm input and output, and can outperform both classical bounds.The paper also presents a case where its bound tends toward zero while chaining gives a relatively large constant and the mutual information bound blows up.Source: §1.2 · p. 3

1.3 Further related literature

  • Unlike Fernique’s Gaussian-process selection bounds, this work uses input-output dependence and algorithm stochasticity for more general processes, but obtains upper bounds only.The introduction also contrasts its approach with PAC-Bayesian chaining bounds, which target high-probability results and exploit hypothesis variance.Source: §1.3 · pp. 3–4

1.4 Notation

  • The paper models supervised learning with i.i.d. training examples and randomized hypothesis selection, and seeks bounds on expected generalization error and its expected absolute value.It specifies the instance, label, and example domains and fixes natural logarithms and nats for information measures.Source: §1.4 · p. 4

2 Main results

The paper combines chaining over metric-indexed hypotheses with mutual information about a learning algorithm’s discretized output, yielding bounds that capture both kinds of dependence. A Gaussian-process example illustrates the bounds’ behavior when the classical mutual-information bound diverges.

2 Main results

  • The bounds use mutual information between the training set and discretized algorithm output at successive scales, weighted by exponentially decreasing 2^-k factors.The output is discretized through increasing partitions of a bounded metric space.Source: §2 · p. 5
  • The random-process counterpart assumes a separable subgaussian process on a bounded metric space with an increasing sequence of progressively finer partitions.The statistical-learning theorem follows from this counterpart by taking the index set to be the hypothesis space and applying data processing.Source: §2 · p. 5
  • The bounds capture hypothesis dependencies through a metric and algorithm dependence through mutual information between the discretized output and input.For generalization error, the input is the training set and the output is the learned hypothesis.Source: §2 · pp. 5–6
  • In the circular Gaussian example, the output is selected using noise with an atom at zero, and the classical chaining bound ignores the algorithm.The noise has a degenerate part, while the chaining comparison upper-bounds the selected process value using its supremum.Source: §2 · p. 6
  • As ϵ → 0, the chained mutual-information bound tends to 0 even though I(W; XT) is infinite, while the classical mutual-information bound blows up.The passage attributes the chained bound’s finiteness and small size to the slow convergence of discretized mutual information and the 2^-k weights.Source: §2 · pp. 6–7
  • The example’s chaining partitions approximate covering numbers, so the stated classical chaining bound is slightly larger than the exact bound.At scale 2^-(-1), the covering number is 1, whereas the construction uses a partition with 2 sets.Source: §2 · p. 7

3 Proof outline

The proof builds scale-wise nets from partitions of the hypothesis space and bounds the selected process value through chained increments. Nested partitions yield a chain of mutual-information terms, with separability completing the argument.

3 Proof outline

  • Theorem 3 follows from Theorem 4; for each k ≥ k1(T), there is a 2^-k-net Nk with an associated mapping πNk such that d(t, πNk(t)) ≤ 2^-k.Source: §3 · p. 8
  • The proof starts from a fixed base point with zero expected process value, then applies the triangle inequality to increments between consecutive net approximations.At each scale, the increment process has at most |N_k||N_{k-1}| distinct terms.Source: §3 · p. 8
  • The mutual-information terms form a chain because each finer partition determines the preceding partition, and the proof sums the scale-wise bounds.The argument uses Theorem 2, data processing, and separability to complete the bound.Source: §3 · pp. 8–9

4 Additional result: small subset property

The small-subset result adapts chaining to algorithm-selected outputs: when the output lies in a low-covering-number subset with high probability, the resulting bound can be tighter than Dudley’s.

4 Additional result: small subset property

  • The chained mutual-information method incorporates information about the learning algorithm into the chaining bound.The section presents this as a way for algorithm information to make the bound much tighter.Source: §4 · p. 9
  • The motivating regularization condition is that the algorithm chooses its output from a small-covering-number subset with high probability.The discussion notes that linear-model SGD converges to a solution with small norm.Source: §4 · p. 9
  • Theorem 5 bounds the selected process value using the partition probabilities and a scale-wise weighted sum of the subsets’ log covering numbers plus H(α).Its stated setting is a separable subgaussian process on a bounded metric space, with P[W ∈ T1] = α.Source: §4 · p. 9
  • When α is near 1 and T1 has much smaller covering numbers than T2, the bound can be much smaller than Dudley’s.The T2 covering number may be replaced by that of T when bounding the latter is easier.Source: §4 · p. 9

5 Conclusion

The paper combines information theory and high-dimensional probability to bound generalization while accounting for both hypothesis dependencies and algorithm input-output dependence. It reports that the bound outperforms previous bounds on an example and tightens Dudley’s inequality under a small-subset condition.

5 Conclusion

  • The chained mutual-information bound accounts for both dependencies among hypotheses and dependence between a learning algorithm’s input and output.The paper describes it as combining information theory with high-dimensional probability.Source: §5 · p. 9
  • On an example, the bound significantly outperforms previous bounds and gets close to the true generalization error.The conclusion compares the chained mutual-information bound with previous bounds.Source: §5 · p. 9
  • Under a natural regularization property, the corollary tightens Dudley’s inequality when the algorithm chooses its output from a small subset with high probability.Source: §5 · p. 9

A Preliminaries

The preliminaries define cumulant generating functions, subgaussian variables, and Legendre duals, then state properties used in the bounds.

A Preliminaries

  • The cumulant generating function is ΛX(λ) = log E[e^(λX)] for real λ.Source: A Preliminaries · p. 11
  • The preliminaries also state that the cumulant generating function is convex and equals zero at zero.Source: A Preliminaries · p. 11
  • A variable is σ^2-subgaussian when its centered exponential moment is bounded by the corresponding Gaussian expression; for a centered variable, this bounds its cumulant generating function.The constant σ^2 is called the variance proxy.Source: A Preliminaries · p. 11
  • For a convex function ψ, its Legendre dual ψ* is introduced, and under the stated convexity and zero-at-origin conditions, ψ* is nonnegative, strictly increasing, convex, and unbounded on x ≥ 0.These properties ensure that its inverse is well defined for y ≥ 0.Source: A Preliminaries · p. 11

B Finite processes (random vectors)

For finite random processes, the section bounds the expected value and tails of an algorithm-selected process value using mutual information between the selection and the process. With an additional two-sided moment-generating-function condition, it also gives lower and absolute-value expectation bounds.

B Finite processes (random vectors)

  • Theorem 7 bounds E[XW] by ψ*^-1(I(W; XT)) under a uniform moment-generating-function condition.The result specializes to centered σ²-subgaussian variables.Source: B Finite processes (random vectors) · p. 12
  • Replacing mutual information by H(W) yields a bound no larger than the classical bound based on log |T|.The section notes that W's entropy is at most log |T|.Source: B Finite processes (random vectors) · p. 12
  • With a two-sided moment-generating-function assumption, Proposition 3 gives upper and lower bounds for E[XW] and an upper bound for E[|XW|].The added assumption controls ΛXt(−λ) as well as ΛXt(λ).Source: B Finite processes (random vectors) · pp. 12–13
  • Theorem 8 gives a tail-probability bound for XW under uniform moment-generating-function control, with a centered subgaussian specialization.The theorem concerns P(XW exceeding a threshold).Source: B Finite processes (random vectors) · p. 14

C Lipschitz processes and the ϵ-net argument

For Lipschitz processes, the section replaces an unhelpful infinite-index maximal bound with an ϵ-net approach and tightens that approach using mutual information. The resulting bound is no larger than the finite-process bound of Theorem 7.

C Lipschitz processes and the ϵ-net argument

D Chaining mutual information

The section combines chaining with mutual information to bound selected values of subgaussian processes while accounting for both metric dependence and data-dependent selection. It also extends the approach to processes with more general increment-tail control.

D Chaining mutual information

  • The approach relaxes an almost-sure Lipschitz condition on process dependencies to an in-probability condition via subgaussian processes.The section defines the centered subgaussian-process setting.Source: D Chaining mutual information · p. 17
  • Theorem 11 combines chaining and mutual information for separable subgaussian processes on bounded metric spaces.The result uses a sequence of nets and a random selected index W.Source: D Chaining mutual information · p. 17
  • The chaining bound replaces Dudley's Hartley-entropy terms with Shannon entropy and further with mutual information.This replacement is stated for minimal 2^-k-nets.Source: D Chaining mutual information · p. 19
  • A further small-subset result gives a scale-wise expression with α-weighted covering-number terms for T1 and T2 and an H(α) term.The cited expression combines the two covering-number contributions at each scale.Source: D Chaining mutual information · p. 19
  • Theorem 12 extends the result to centered separable processes on bounded metric spaces whose increments have tails controlled by ψ.The theorem specifies convex ψ with ψ(0) = ψ′(0) = 0.Source: D Chaining mutual information · p. 19
Loading 1806.03803v2…