Information Theory for ML12 / 16

Module 12. Information-theoretic generalization bounds: PAC-Bayes and mutual information

Choose your answers and select “Check”. Numbers accept a decimal point, comma, or simple fraction. Answers and drafts are saved in this browser and shared between RU/EN.

Checked: 0 / 25 · Correct: 0

Question 12.2.1

12.2. From a fixed model to adaptive selection

Why can a concentration bound for a pre-specified model not be applied directly to $W=A(S)$ ?

One correct optionABecause neural networks are not measurable functionsBBecause the trained model depends on the same sample on which empirical risk is measuredCBecause the loss is always unboundedDBecause PAC learning forbids optimization

A) Because neural networks are not measurable functions

B) Because the trained model depends on the same sample on which empirical risk is measured

C) Because the loss is always unbounded

D) Because PAC learning forbids optimization

Answer and explanation

Correct answer: B. Adaptive selection creates selection bias: the output has already adapted to fluctuations of the particular sample.

Question 12.2.2

12.2. From a fixed model to adaptive selection

What is the most accurate statement about classical uniform-convergence bounds for very large networks?

One correct optionAThey are mathematically falseBThey apply only to linear modelsCThey are always tighter than PAC-BayesDThey are valid worst-case bounds but can be numerically vacuous with coarse complexity measures

A) They are mathematically false

B) They apply only to linear models

C) They are always tighter than PAC-Bayes

D) They are valid worst-case bounds but can be numerically vacuous with coarse complexity measures

Answer and explanation

Correct answer: D. The problem is usually not validity but the coarse global complexity of the class.

Question 12.3.1

12.3. PAC-Bayes: prior, posterior, and the Gibbs classifier

What does $D_{\mathrm{KL}}(Q\|P)$ measure in the standard PAC-Bayes setup?

One correct optionAThe cost of moving a data-dependent posterior away from a pre-chosen priorBThe number of network parametersCThe distance between train and test distributionsDThe entropy of the labels

A) The cost of moving a data-dependent posterior away from a pre-chosen prior

B) The number of network parameters

C) The distance between train and test distributions

D) The entropy of the labels

Answer and explanation

Correct answer: A. The KL term charges for posterior adaptation to the sample relative to a valid reference distribution.

Question 12.3.2

12.3. PAC-Bayes: prior, posterior, and the Gibbs classifier

Why must the prior in a basic PAC-Bayes theorem be independent of the certification sample?

One correct optionATo make the posterior uniformBTo force the KL to zeroCOtherwise the data could be used to shrink the complexity term without being chargedDTo make the Gibbs classifier deterministic

A) To make the posterior uniform

B) To force the KL to zero

C) Otherwise the data could be used to shrink the complexity term without being charged

D) To make the Gibbs classifier deterministic

Answer and explanation

Correct answer: C. The posterior may depend on data because the bound is simultaneous over Q; an uncorrected prior may not.

Question 12.3.3

12.3. PAC-Bayes: prior, posterior, and the Gibbs classifier

Which predictor is directly described by the basic PAC-Bayes risk $L(Q)$ ?

One correct optionAThe network with mean weightsBThe Gibbs classifier that randomly draws

W\sim Q

CA majority vote without additional argumentsDThe best model in the posterior support

A) The network with mean weights

B) The Gibbs classifier that randomly draws $W\sim Q$

C) A majority vote without additional arguments

D) The best model in the posterior support

Answer and explanation

Correct answer: B. L(Q)=E_(W~Q)L(W) is the risk of the randomized Gibbs predictor.

Question 12.4.1

12.4. PAC-Bayes-kl: the main high-probability bound

What is the PAC-Bayes-kl inequality used in the module?

One correct optionA

\operatorname{kl}(\widehat L_S(Q)\|L(Q))\le [D_{\mathrm{KL}}(Q\|P)+\ln(2\sqrt n/\delta)]/n

L(Q)\le D_{\mathrm{KL}}(Q\|P)

I(W;S)\le\widehat L_S(Q)

L(Q)=\widehat L_S(Q)

A) $\operatorname{kl}(\widehat L_S(Q)\|L(Q))\le [D_{\mathrm{KL}}(Q\|P)+\ln(2\sqrt n/\delta)]/n$

B) $L(Q)\le D_{\mathrm{KL}}(Q\|P)$

C) $I(W;S)\le\widehat L_S(Q)$

D) $L(Q)=\widehat L_S(Q)$

Answer and explanation

Correct answer: A. It is a high-probability statement holding simultaneously for all posteriors Q.

Question 12.4.2

12.4. PAC-Bayes-kl: the main high-probability bound

If $\widehat L_S(Q)=0$ and $\operatorname{kl}(0\|L(Q))\le c$ , what exact upper bound follows?

One correct optionA

L(Q)\le c^2

L(Q)\le e^{-c}

L(Q)\le\sqrt{2c}

L(Q)\le1-e^{-c}

A) $\operatorname{kl}(\widehat L_S(Q)\|L(Q))\le [D_{\mathrm{KL}}(Q\|P)+\ln(2\sqrt n/\delta)]/n$

B) $L(Q)\le e^{-c}$

C) $L(Q)\le\sqrt{2c}$

D) $L(Q)\le1-e^{-c}$

Answer and explanation

Correct answer: D. Because kl(0‖L)=-ln(1-L).

Question 12.4.3

12.4. PAC-Bayes-kl: the main high-probability bound

How does the Pinsker corollary compare with exact binary-KL inversion?

One correct optionAIt is always identicalBIt is always tighterCIt is simpler but usually weaker, especially near zero empirical riskDIt applies only when

n=1

A) It is always identical

B) It is always tighter

C) It is simpler but usually weaker, especially near zero empirical risk

D) It applies only when $n=1$

Answer and explanation

Correct answer: C. Pinsker replaces the binary-KL geometry by a quadratic inequality and loses information.

Question 12.4.4

12.4. PAC-Bayes-kl: the main high-probability bound

Which tool transfers a fixed-hypothesis exponential-moment bound from prior $P$ to an arbitrary posterior $Q$ ?

One correct optionAThe Pythagorean theoremBDonsker–Varadhan change of measureCThe central limit theoremDKraft inequality

A) The Pythagorean theorem

B) Donsker–Varadhan change of measure

C) The central limit theorem

D) Kraft inequality

Answer and explanation

Correct answer: B. Change of measure adds the cost D_KL(Q‖P).

Question 12.5.1

12.5. Turning the bound into a trainable objective

What does the Gibbs posterior $Q_\lambda\propto P\exp[-\lambda n\widehat L_S]$ minimize?

One correct optionAEmpirical risk aloneB

I(X;T)-\beta I(T;Y)

CPosterior entropy aloneD

\widehat L_S(Q)+D_{\mathrm{KL}}(Q\|P)/(\lambda n)

A) Empirical risk alone

B) $W\sim Q$

C) Posterior entropy alone

D) $\widehat L_S(Q)+D_{\mathrm{KL}}(Q\|P)/(\lambda n)$

Answer and explanation

Correct answer: D. This follows directly from the Gibbs variational principle.

Question 12.5.2

12.5. Turning the bound into a trainable objective

When does a Gibbs posterior literally coincide with an ordinary Bayesian posterior?

One correct optionAAlwaysBOnly for linear modelsCNeverDWhen the loss and scale match a negative log-likelihood and the chosen prior

A) Always

B) Only for linear models

C) Never

D) When the loss and scale match a negative log-likelihood and the chosen prior

Answer and explanation

Correct answer: D. Algebraic similarity does not replace a likelihood model.

Question 12.5.3

12.5. Turning the bound into a trainable objective

Why is deterministic weight decay not equivalent to a full PAC-Bayes training objective?

One correct optionABecause KL contains no mean-weight termBBecause PAC-Bayes forbids Gaussian distributionsCPAC-Bayes optimizes a distribution, includes variance terms, and certifies a Gibbs predictorDBecause weight decay always increases loss

A) Because KL contains no mean-weight term

B) Because PAC-Bayes forbids Gaussian distributions

C) PAC-Bayes optimizes a distribution, includes variance terms, and certifies a Gibbs predictor

D) Because weight decay always increases loss

Answer and explanation

Correct answer: C. The quadratic mean term is only one part of the Gaussian KL.

Question 12.5.4

12.5. Turning the bound into a trainable objective

What happens to $D_{\mathrm{KL}}(\delta_{w_*}\|P)$ when $P$ has a continuous density?

One correct optionAIt is infiniteBIt equals

\|w_*\|^2

CIt is always zeroDIt equals the prior entropy

A) It is infinite

B) It equals $W\sim Q$

C) It is always zero

D) It equals the prior entropy

Answer and explanation

Correct answer: A. A point mass is not absolutely continuous with respect to a continuous prior.

Question 12.6.1

12.6. MI bounds: learning as a channel from sample to model

What type of guarantee is usually provided by the basic Xu–Raginsky MI generalization bound?

One correct optionAA high-probability certificate for one runBAn expectation bound over the sample and algorithmic randomnessCAn adversarial-robustness guaranteeDThe exact test risk

A) A high-probability certificate for one run

B) An expectation bound over the sample and algorithmic randomness

C) An adversarial-robustness guarantee

D) The exact test risk

Answer and explanation

Correct answer: B. It controls |E[L(W)-L̂_S(W)]|.

Question 12.6.2

12.6. MI bounds: learning as a channel from sample to model

For a loss in $[0,1]$ , which sub-Gaussian variance proxy follows from Hoeffding’s lemma?

One correct optionA

1

1/2

1/4

n

A) $\operatorname{kl}(\widehat L_S(Q)\|L(Q))\le [D_{\mathrm{KL}}(Q\|P)+\ln(2\sqrt n/\delta)]/n$

B) $1/2$

C) $1/4$

D) $n$

Answer and explanation

Correct answer: C. This yields |Egen|≤√(I(W;S)/(2n)).

Question 12.6.3

12.6. MI bounds: learning as a channel from sample to model

What is true for a deterministic algorithm with an exact continuous output $W$ ?

One correct optionAMI is always zeroBMI always equals the number of parametersCMI is necessarily finiteDMI is often infinite, making the basic MI bound vacuous

A) MI is always zero

B) MI always equals the number of parameters

C) MI is necessarily finite

D) MI is often infinite, making the basic MI bound vacuous

Answer and explanation

Correct answer: D. Determinism alone does not ensure finite mutual information in the continuous case.

Question 12.7.1

12.7. The exact decomposition connecting PAC-Bayes and MI

Why are individual-sample MI bounds used?

One correct optionATo prove a causal effectBTo replace loss by accuracyCTo make the prior depend on the test setDTo account for dependence on individual examples and sometimes obtain a tighter bound

A) To prove a causal effect

B) To replace loss by accuracy

C) To make the prior depend on the test set

D) To account for dependence on individual examples and sometimes obtain a tighter bound

Answer and explanation

Correct answer: D. They aggregate local I(W;Z_i) contributions rather than placing one square root over a global quantity.

Question 12.7.2

12.7. The exact decomposition connecting PAC-Bayes and MI

Which exact identity connects average posterior-to-prior KL and mutual information?

One correct optionA

\mathbb E_S D_{\mathrm{KL}}(Q_S\|P)=I(W;S)+D_{\mathrm{KL}}(P_W\|P)

I(W;S)=H(S)

D_{\mathrm{KL}}(Q_S\|P)=I(X;T)

I(W;S)=\widehat L_S(W)

A) $\operatorname{kl}(\widehat L_S(Q)\|L(Q))\le [D_{\mathrm{KL}}(Q\|P)+\ln(2\sqrt n/\delta)]/n$

B) $I(W;S)=H(S)$

C) $D_{\mathrm{KL}}(Q_S\|P)=I(X;T)$

D) $I(W;S)=\widehat L_S(W)$

Answer and explanation

Correct answer: A. The second term is the mismatch between the marginal output distribution and the chosen prior.

Question 12.7.3

12.7. The exact decomposition connecting PAC-Bayes and MI

Which prior minimizes $\mathbb E_S D_{\mathrm{KL}}(Q_S\|P)$ ?

One correct optionA

P=P_W

, the marginal distribution of the algorithm outputBA point mass at the trained weightsCA uniform priorDAny Gaussian prior

A) $\operatorname{kl}(\widehat L_S(Q)\|L(Q))\le [D_{\mathrm{KL}}(Q\|P)+\ln(2\sqrt n/\delta)]/n$ , the marginal distribution of the algorithm output

B) A point mass at the trained weights

C) A uniform prior

D) Any Gaussian prior

Answer and explanation

Correct answer: A. This is the oracle prior; it makes the mismatch term vanish.

Question 12.7.4

12.7. The exact decomposition connecting PAC-Bayes and MI

What is the precise status of the oracle prior $P_W$ in a standard high-probability PAC-Bayes bound?

One correct optionAIt is always invalid because it depends on the learning algorithmBThe exact

P_W

, fixed before the realized sample, is admissible, but it usually requires knowledge of the unknown data distribution; estimating it from the same sample creates dependence that must be paid forCIt may be estimated from the certification sample and inserted without a correctionDIt always has infinite entropy

A) It is always invalid because it depends on the learning algorithm

B) The exact $W\sim Q$ , fixed before the realized sample, is admissible, but it usually requires knowledge of the unknown data distribution; estimating it from the same sample creates dependence that must be paid for

C) It may be estimated from the certification sample and inserted without a correction

D) It always has infinite entropy

Answer and explanation

Correct answer: B. “Oracle” means unavailable, not automatically invalid. If the marginal law of the algorithm output is known independently of the realized sample, it is a fixed prior; a same-sample estimate is instead a data-dependent prior and needs a separate theorem.

Question 12.8.1

12.8. Connections to MDL, Information Bottleneck, and KL-regularized policies

When does the PAC-Bayes complexity term have a literal MDL code-length interpretation?

One correct optionAOnly for Wasserstein distanceBFor discrete

Q=\delta_w

with prior mass

P(w)>0

, where KL equals

-\ln P(w)

COnly if

I(X;T)=0

DNever

A) Only for Wasserstein distance

B) For discrete $W\sim Q$ with prior mass $P(w)>0$ , where KL equals $-\ln P(w)$

C) Only if $I(X;T)=0$

D) Never

Answer and explanation

Correct answer: B. In bits, -log₂P(w) is the ideal prior-code length of the hypothesis.

Question 12.8.2

12.8. Connections to MDL, Information Bottleneck, and KL-regularized policies

Why should $I(W;S)$ in generalization theory not be identified with $I(X;T)$ in the Information Bottleneck?

One correct optionAThey involve different random objects and appear in different theoremsBThey always use different log basesCIB forbids stochastic encodersDPAC-Bayes does not use KL

A) They involve different random objects and appear in different theorems

B) They always use different log bases

C) IB forbids stochastic encoders

D) PAC-Bayes does not use KL

Answer and explanation

Correct answer: A. W,S describe an algorithm and dataset; X,T describe an individual input and representation.

Question 12.8.3

12.8. Connections to MDL, Information Bottleneck, and KL-regularized policies

Why is the KL anchor in RLHF not the same object as the PAC-Bayes KL?

One correct optionARLHF compares output policies at a context, whereas PAC-Bayes compares distributions over models or weightsBPAC-Bayes KL is always symmetricCRLHF never uses probabilitiesDThey differ only in log base

A) RLHF compares output policies at a context, whereas PAC-Bayes compares distributions over models or weights

B) PAC-Bayes KL is always symmetric

C) RLHF never uses probabilities

D) They differ only in log base

Answer and explanation

Correct answer: A. Using the same KL notation does not make the random objects identical.

Question 12.9.1

12.9. Building a practical PAC-Bayes certificate

What else must be accounted for when empirical Gibbs risk is estimated from a finite Monte Carlo sample from $Q$ ?

One correct optionAThe KL term may be droppedBOne may automatically replace the Gibbs predictor by the mean networkCMonte Carlo estimation error must be included in the certificateDTest risk becomes part of the bound

A) The KL term may be dropped

B) One may automatically replace the Gibbs predictor by the mean network

C) Monte Carlo estimation error must be included in the certificate

D) Test risk becomes part of the bound

Answer and explanation

Correct answer: C. Otherwise a noisy random estimate is inserted into the theorem without an additional guarantee.

Question 12.10.1

12.10. Mathematical deepening: more local information costs

How can a data-dependent prior be used validly through sample splitting?

One correct optionATrain prior and posterior on the test setBIgnore prior dependence on dataCBuild the prior on

S_0

and conditionally apply the bound to an independent subset

S_1

DAlways set prior equal to posterior

A) Train prior and posterior on the test set

B) Ignore prior dependence on data

C) Build the prior on $S_0$ and conditionally apply the bound to an independent subset $S_1$

D) Always set prior equal to posterior

Answer and explanation

Correct answer: C. The cost is a smaller effective certification sample.