PaperlayerView exact revision on arXiv

Source-linked AI summary

An Accuracy-Information Tradeoff for Loss-Difference Conditional Mutual Information

Hazar Yueksel

arXiv:2610.09206v2cs.LGcs.ITmath.ITstat.ML

TL;DR

The paper asks whether accuracy forces information into loss differences, although model-level lower bounds do not transfer to losses by data processing. It bounds three moments of the loss differences and proves a noisy-information tradeoff for accurate proper learners in the stated setting. At zero noise, worst-case information is of order n bits, and added Gaussian noise reduces it according to the theorem’s tradeoff.

  • Problem

    Prior results show accuracy can force model information, but data processing does not yield lower bounds for loss-difference information, leaving its behavior under observation noise open.

    Source: §1 · p. 1

  • Method

    The paper bounds three moments of loss differences and transfers those bounds to noisy loss-difference information for a family of product distributions.

    Source: §1 · p. 2

  • Results

    At τ=0, worst-case loss-difference information is of order n bits; at τ≫ε it is of order n(ε/τ)^2 bits.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Range-scaled ld-CMI bounds stay above a constant somewhere in the studied family, although every proper learner’s generalization gap is O(n^-1/2).

    Source: §1 · p. 2

    The result is for proper learners in the specified linear-predictor, link, regularizer, distribution-family, dimension, and optimal-sample-size setting; accuracy at one law alone cannot force information there.

    Source: §3 · p. 4, §9 · p. 8

Abstract

from arXiv · show

Loss-difference conditional mutual information (ld-CMI) uses the smallest of the standard observations in the supersample hierarchy of generalization bounds: it measures what a learner's loss differences reveal about which candidate of each pair it was trained on. Accuracy is known to force information into the model; data processing does not carry such lower bounds to losses. We show, by bounding three moments of the loss differences, that accuracy also forces ld-CMI. For linear predictors with a smooth convex loss of nonzero slope at zero, such as the logistic loss, plus a regularizer whose curvature and growth are both of power $r\ge2$, on product distributions over a scaled sign cube in dimension at least linear in $n$, every proper learner with expected excess risk at most $\varepsilon$ on these distributions at the optimal sample size $n\asymp\varepsilon^{-2+2/r}$ has worst-case ld-CMI of order $n$ bits, and $\Theta(n/(1+(\tau/\varepsilon)^2))$ bits under Gaussian noise of standard deviation $\tau$ on the loss differences. The same holds without a regularizer, at $n\asymp\varepsilon^{-2}$. Consequently, range-scaled ld-CMI bounds cannot vanish on these distributions, although every proper learner's generalization gap is $O(n^{-1/2})$. We also show that model-level information does not determine noisy loss-difference information, and that the growth, slope and dimension conditions are needed, the last up to a logarithm.

1 Introduction

The paper asks whether accuracy forces information into loss differences, the smallest observation in a supersample hierarchy, and how noise changes that information. It answers with a two-sided tradeoff for a specified class of learners and distributions.

1 Introduction

  • Accuracy is known to force model information, but data processing supplies no corresponding lower bound for losses; prior loss-level results concern narrower settings.Earlier results include evaluated-CMI bounds for gradient descent and a single-instance loss-difference example, both without noise.Source: §1 · p. 1

1.1 Related Work

  • Related work establishes accuracy-driven information or tracing results at the model level, while the cited information-based generalization bounds span individual-sample, conditional, evaluated, and loss-difference forms.The paper also situates its privacy witness alongside fingerprinting-based lower bounds and one-run auditing.Source: §1 · p. 1, §1.1 · pp. 2–3

1 Introduction

  • The result concerns linear predictors with a smooth convex link of nonzero slope at zero, matched power regularization, product distributions on a scaled sign cube, and dimension d ≳ n.The ridge-regularized logistic problem with balanced labels is included.Source: §1 · p. 1
  • At τ=0, the worst-case loss-difference information is of order n bits; noise at the excess-risk scale leaves a constant fraction of a bit per pair.The total falls to Θ(1) bits only at τ ≍ ε^1/r.Source: §1 · pp. 1–2
  • The proof bounds three moments of loss differences and transfers them to information without requiring independence among those differences.The moments control the signed mean, energy, and squared distance from a candidate-fixed reference.Source: §1 · p. 2
  • For the studied family, range-scaled ld-CMI bounds stay above a constant somewhere even though every proper learner’s generalization gap is O(n^-1/2).The loss differences have range of order one but root-mean-square size of order ε.Source: §1 · p. 2

2 Setting

The setting releases each pair’s training-minus-ghost loss difference and studies how much noisy releases reveal about the hidden selection bits. Learners are proper, and accuracy and information are evaluated over a product-distribution family on a scaled sign cube.

2 Setting

  • The data family consists of product laws over a scaled sign cube, and a proper learner outputs a parameter in the unit ball.Accuracy is defined across the family using expected excess risk.Source: §2 · p. 3
  • The supersample draws 2n candidates independently and uses n independent fair bits to select the learner’s training examples, leaving the other candidates as ghosts.The loss-difference release records one loss difference for each pair.Source: §2 · p. 3
  • The observer sees Y=X+τG, with independent standard Gaussian noise, and information is measured about the selection bits, optionally conditioned on all candidates.The three measures consider one noisy difference at a time, all differences jointly, or the differences together with the candidates.Source: §2 · p. 3
  • The summed ld-CMI lies between unconditional individual information and information conditioned on the candidates, while the noisy-release measures obey a data-processing hierarchy.That hierarchy also places information in the release below information in the learner’s model.Source: §2 · p. 3
  • The expected generalization gap is the expected signed loss difference divided by n.The sign convention identifies each pair’s release with ghost-minus-training loss.Source: §2 · p. 3
  • The loss is a regularizer plus a convex link applied to a linear predictor; the link has nonzero slope at zero and the regularizer’s curvature and growth share power r≥2.Examples include logistic links and power-norm regularizers; the regularizer may also be absent in a stated extension.Source: §2 · p. 3

3 Main result

For the stated link and regularizer assumptions, the main theorem bounds noisy loss-difference information from both sides for every accurate proper learner at optimal sample size and sufficiently large dimension. It establishes an order-n worst-case signal without noise and decreasing information as noise grows.

3 Main result

  • For conjugate q = r/(r−1) ∈ (1,2], the optimal sample size is nε = ε−2/q = ε−2+2/r (Proposition 4); without regularization, n ≍ ε−2.This gives ε−1 for ridge regularization (r = 2) and ε−3/2 for quartic regularization (r = 4).Source: §3 · pp. 3–4
  • For every Q in the theorem and every noise level, accurate proper learners have two-sided information bounds when n is within constant factors of nε and d is sufficiently large.The lower bound averages over a learner-independent prior on the family, while the upper bound holds at every distribution.Source: §3 · pp. 3–4
  • For τ ≫ ε, worst-case information is of order n(ε/τ)^2 bits; at fixed τ>0 it is Θ(ε^2/r).The theorem’s constants can be far apart, so its claim is about orders.Source: §3 · p. 4
  • Accuracy at a single law cannot force information there; the lower bound uses accuracy across the family to establish a worst-case result.A learner that always outputs that law’s population-risk minimizer is exactly accurate there and its release carries no information about the selection bits.Source: §3 · p. 4
  • The sample-size regime is attainable with epoch SGD using O(nε) samples, and accurate learners require Ω(nε) samples when dimension is sufficiently large.Thus the information tradeoff applies at an optimal sample size for learners satisfying the theorem’s hypotheses.Source: §3 · p. 4
  • In a ridge ERM example, each pair has a constant-fraction information signal when d≳n, while noise much larger than ε reduces that fraction to order (ε/τ)^2.Theorem 3 extends this behavior to every accurate learner in the class in the worst case over the family.Source: §3 · p. 4

4 What the tradeoff means for loss-difference CMI bounds and for privacy

Accuracy forces loss-difference information even though every proper learner has a small generalization gap. The resulting range-scaled ld-CMI bounds can remain bounded away from zero, and the paper also derives a privacy consequence.

Privacy

  • εDP = Ω(1) unless δ ≳ ε for learners satisfying the theorem’s hypotheses.The stated privacy conclusion follows from the privacy cap on signed loss differences and their accuracy-driven moment bounds.Source: §4 · p. 4

Loss-difference CMI bounds

  • At some law, every accurate learner has range-scaled ld-CMI bounds bounded below by a positive constant, while its generalization gap is at most 4L/√n.The loss-difference range is order one, but its root-mean-square size is order ε, so range normalization does not capture that scale.Source: §4 · pp. 4–5

Noise at the scale of the range

  • At τ = 2L, the noisy loss-difference bound is of the same order as the prior-average generalization gap.For ridge ERM, the resulting bound is at most 1.44 times the gap on prior average in the reported runs at d = 32n and d = 64n.Source: §4 · p. 5

Scope of the bounds

  • Theorem 3 does not bound binary Jensen–Shannon, stability-scaled, or projected-and-quantized bounds, which use other information observations or functionals.Fast-rate bounds using an information measure of a kind bounded by the theorem also do not vanish at some law.Source: §4 · p. 5

5 Proof of Theorem 3: three moments and one transfer theorem

The proof converts accuracy into three moment bounds on loss differences, then transfers those bounds into information bounds at every noise level. A beta prior, localization, and a final assembly establish the stated tradeoff.

5.1 Architecture and the Prior

  • The proof averages over a beta prior on product-distribution parameters, chosen so its mean-vector scale is tied to ε.The prior’s parameters are fixed for all learners, and its expectation averages over the prior, data, selection bits, and learner seed.Source: §5.1 · p. 5

5.2 The Transfer Theorem

  • The transfer theorem turns a signed-mean moment and a residual-distance moment into information bounds without assuming independent loss differences.For Gaussian noise, the residual bound uses Gaussian maximum entropy and is capped by n bits; the signed-mean bound also applies to independent centered noise of variance τ^2.Source: §5.2 · pp. 5–6

5.3 The Three Moment Bounds

  • Accuracy yields a prior-average signed loss-difference signal of order nε and a loss-difference energy and residual controlled at the scale needed for transfer.Localization keeps the training-dependent remainder below the signal; in dimension d ≳ n the loss differences have root-mean-square size of order ε on prior average.Source: §5.3 · p. 6

5.4 Assembly

  • The assembled bounds give order n/(1 + (τ/ε)^2) information for Iind, with matching bounds extending to Ijoint and Icand.The upper half holds for Icand at every law; the constants are independent of the learner and the bounds extend to the infimum over any nonempty class of eligible learners.Source: §5.4 · p. 7

6 The hypotheses are needed

The lower bound depends on matched regularizer growth, a nonzero loss slope at zero, and sufficiently large dimension. Examples show why these conditions matter, with the dimension requirement necessary up to a logarithm.

Matched growth

  • Without matched growth, the linear-order lower bound can fail: for a quadratic regularizer with only a quartic lower-curvature comparison, the least worst-case information is Θ(n^1/3) = o(n).In the example, ε = τ = n^-2/3, whereas the quadratic regularizer’s relevant sample scale is about ε^-1 = n^2/3.Source: §6 · p. 7

Zero slope

  • Without a nonzero slope at zero, the always-zero learner is exactly accurate and its release vanishes.Convexity and g ≥ 0 = g(0) make θ = 0 a minimizer at every law when ϕ′(0) = 0.Source: §6 · p. 7

Dimension

  • At τ = ε, no proper learner attains the lower half in dimension below c1n/(12 log2 n) for large n, so linear dimension is necessary up to a logarithm.The noiseless lower half also requires d ≳ n/log n by the stated rounding argument.Source: §6 · p. 7

7 Model information does not determine the tradeoff

Model-level information does not determine noisy loss-difference information. A bijective reparameterization can preserve model information while the corresponding noisy releases carry very different amounts of information.

7 Model information does not determine the tradeoff

  • At τ = n^-2/3, bijectively related mean and quartic-ERM releases have noisy information at most 3n^1/3 bits everywhere versus at least n/8 bits at the zero-mean law.The learners have the same model information and tracers with identical decisions, while their releases differ by a factor of about n^1/3 near zero mean.Source: §7 · p. 7

8 Measurements

At d = 64n, measured loss-difference information tracks the moment-based bounds across two learners and declines with added noise. The ridge ERM measurements also compare the prior-averaged generalization gap with information-free and range-scaled bounds.

The Tradeoff

  • Ridge ERM and logistic ridge ERM were compared using prior-averaged measurements at d = 64n, with 95% intervals and each learner’s own M, V and Vres.The information-per-pair estimate used a cross-fitted variational bound; the theorem’s moments were exact for ridge ERM and estimated for logistic ridge ERM.Source: §8 · pp. 7–8, Figure 2 · p. 8
  • 0.888–0.915 bits per pair were estimated without noise across nine runs, and for τ ≥5M/n the log–log slopes were −2.25 to −1.88.The estimates nearly followed the lower half of Theorem 6 across runs; 139 of 144 measured points lay within its bracket up to their 95% intervals.Source: §8 · p. 8

Generalization

  • At τ = 0, ridge ERM’s prior-averaged gap was exactly (1 −8/n)/n, while EΠVp/n exceeded it by only 12–13%.The range-scaled ld-CMI bounds were at least 2L on prior average.Source: §8 · p. 8
  • 2 ln 2 ι estimates stayed between 2.09 and 2.15, or 128 to 6290 times the gap, and above the uniform bound 4L/√n.Here L = 1.Source: §8 · p. 8

9 Limitations and outlook

The results are scoped to proper learners and specified linear-prediction settings, and several boundaries remain open. The appendices also record AI use, notation, and probability tools.

9 Limitations and outlook

  • The results cover proper learners, linear predictors, specified smooth convex links and matched power regularizers or none, product laws on a scaled sign cube, and optimal sample sizes.The lower bound uses dimension d ≳n, necessary up to a logarithm; bounds at a single law and informative constants at moderate n remain open.Source: §9 · p. 8

AI use statement

  • The authors report using generative AI for theoretical development, proofs, methodology, numerical methods, literature search, code, figures, and drafting, and say they reviewed AI-assisted work.They state that the main results are also machine-checked in Lean 4.Source: AI use statement · pp. 8–9

A Notation

  • The notation appendix collects paper-wide symbols and conventions, including the supersample, loss-difference release, and information quantities.Symbols used only in one proof or appendix are defined where used.Source: A Notation · pp. 12–13

Appendix C.1

  • Appendix C.1’s notation records the beta-prior variance and the moment budgets used in Theorem 6.The prior variance is v = EΠκ∥µp∥² = 1/(κ + 1).Source: Appendix C.1 · p. 13

B Probability tools

  • Appendix B collects probability tools, including beta-prior moments and tail bounds.It proves Lemmas 8–10 and derives beta-prior moments used in Appendix D’s proofs.Source: B Probability tools · p. 13

B.1 Beta-Prior Moments and Fingerprinting

The appendix derives beta-prior moment bounds and probability tools used in later proofs. It also gives operator-norm tails and a weighted-tail bound that permits dependence between a random weight and the tail variable.

B.1 Beta-Prior Moments and Fingerprinting

  • For the beta prior, E∥µp∥² = v and E∥µp∥⁴ ≤v²(1 + 2/d).The derivation uses an integration-by-parts identity valid for every polynomial when κ > 0.Source: §B.1 · pp. 14–15
  • The appendix presents the beta-prior fingerprinting lemma for every proper learner and identifies it as the lemma of Steinke & Ullman (2017).The proof assumes a bounded, jointly measurable learner output with a seed independent of the prior and data.Source: §B.1 · p. 14

B.2 Operator-Norm and Weighted Tails

  • For d ≥32n, the centered training matrix has an operator-norm tail bound with K0 < 2.031 and K1 = 2/(cnetd).The pair matrix satisfies the corresponding bound with 2K0 and 2K1.Source: §B.2 · p. 15
  • If P(N > K0 + K1t) ≤e−t and 0 ≤ω ≤¯ω with Eω ≤w, then E[Nω] ≤w{K0 + K1[1 + ln(¯ω/w)]}, regardless of their dependence.This bound handles learner errors or norms that depend on atypical matrices.Source: §B.2 · p. 16

C Proof of Theorem 6 and the information hierarchy

The appendix transfers moment information into bounds on information about the supersample’s selection bits, then relates those bounds across observation levels. It also gives a bit-decoding interpretation and compares noisy model information with noisy loss-difference information.

C Proof of Theorem 6 and the information hierarchy

  • Theorem 6 transfers moment bounds on a release into information bounds, and neither part requires independent coordinates of the release.The result applies to random vectors defined together with the supersample, not only to loss differences.Source: C Proof of Theorem 6 and the… · p. 16

C.1 The Fair-Bit Inequality and the Lower Bound

  • A fair-bit inequality lower-bounds information using the signed mean and second moment, and the proof applies it to noisy loss differences.The noise contribution to the second moment is bounded by nτ²; the same moment argument works for independent centered noise with variance τ² per coordinate.Source: §C.1 · p. 17

C.2 The Hierarchy and the Gaussian Upper Bound

  • Summed per-pair conditional information for a release lies below its joint information conditioned on candidates; for loss differences, that sum is ld-CMI.Conditional data processing also places noisy-release information below information in the model.Source: §C.2 · p. 18

C.3 The Clipped Decoder

  • A clipped decoder reads each loss difference separately and guesses the selection bits, with its scale set to λ = V/(2M).For learners of Theorem 3, the moment bounds make M²/(nV) a constant and λ depend only on ε and theorem constants.Source: §C.3 · pp. 18–19

C.4 Model Information with Noise

  • Noisy model information can have the order of the upper half of Theorem 3, but it does not imply that theorem’s loss-level upper bound by data processing.The loss-level bound instead uses a residual bound at every law, and the two noise scales τ ≍ε and τ ≍ε1/r require both theorem halves.Source: §C.4 · pp. 19–20

D Proof of Proposition 7 and Theorem 3

This section proves explicit bounds connecting accuracy to loss-difference information through controls on loss-difference moments, and establishes matching sample-size necessity. It also extends the results to classification constructions, broader regularizers, reflected links, and compact ranges of regularization strength, with numerical examples of how explicit constants depend on dimension and noise.

D.1 Calibration

  • Accuracy at Dp calibrates the population risk of the actual loss, not a linearized loss, and this step requires the upper growth condition on the regularizer.The passage identifies this as the only step using g ≤ a+∥·∥^r and notes that Proposition 11 shows the condition cannot be dropped.Source: §D.1 · p. 21

D.2 Localization

  • Localization controls the learner’s squared error at every p and bounds its prior-averaged norm moments, supporting the moment bounds used in the proof.The localization argument uses accuracy at Dp, properness, and uniform convexity of the risk.Source: §D.2 · p. 22

D.3 The Signed Mean

  • The signed-mean bound keeps its penalty terms one power of ε below the signal at the optimal sample size by using localized bounds on learner moments.Replacing those localized bounds with only ∥bθ∥ ≤ 1 would leave penalties of constant order for r = 2.Source: §D.3 · p. 23

D.4 Energy

  • V bounds the prior-averaged energy of the loss differences, and in the theorem regime V = Θ(nε^2).The energy bound is prior-averaged; the residual bound, by contrast, holds at every law.Source: §D.4 · p. 23, §D.6 · p. 24

D.5 The Residual at Every Law

  • The residual bound holds at every law, uses accuracy only at that law, and controls the loss differences without linearizing the link.In the theorem regime, Vres = Θ(nε^2).Source: §D.5 · p. 24, §D.6 · p. 24

D.6 Orders and Assembly

  • For 0 < ε ≤ ε0, M = Θ(nε), while V and Vres are Θ(nε²); under the dimension condition of Theorem 3, small ε makes M positive and gives these orders.Source: D Proof of Proposition 7 and Theorem 3 · p. 21, §D.6 · pp. 24–25
  • C1 n/(1 + (τ/ε)^2) upper-bounds each of Iind, Ijoint, and Icand; the theorem gives both bounds of (7) for their worst-case values and for the infimum over any nonempty class of accurate proper learners.The upper bound holds at every p, and the lower bound follows from a prior average; the maximizing law may depend on the learner, information measure, and τ.Source: §D.6 · p. 25

D.7 Explicit Constants

  • The explicit-constants analysis gives Cdim = 32 max{1, (β/4)^(2/q)} and states the two-sided information bound in normalized form whenever M > 0.The finite dimension condition (40) is the only dimension requirement used in this constants analysis.Source: §D.7 · pp. 25–26
  • For quartic logistic learning at c=1 and ρ=1/32, the limiting moments are (M̄,V̄,V̄res)=(0.050,29.2,15.6), with C1/c1≈2.0·10^5.At ε=6.0·10^-4 the threshold is admissible; the ratio rises to about 10^10 there, while smaller thresholds approach 2.1·10^5.Source: §D.7 · p. 27

E Proposition 4 and examples

  • The explicit proposition sets q=r/(r−1) and nε=ε^-2+2/r, with calibration constants t0=(b/(ra+ + b))^1/(r−1) and β=bt0/q.It states an explicit form under Assumption 2, with Lf=Lg+L and cv=(4/β)^2/q.Source: E Proposition 4 and examples · p. 27

E.1 Epoch SGD

  • Projected epoch SGD is proper and ε-accurate on every unit-ball distribution using O(nε) samples, with a schedule depending only on problem constants and ε.Its multistage schedule halves the target excess risk, and the summed epoch sample counts are O(ε^-2+2/r).Source: E Proposition 4 and examples · p. 27, §E.1 · p. 28

E.2 The Sample Size Is Necessary

  • For the problems of Theorem 3, the optimal sample size is nε = ε−2+2/r: ε−1 for ridge regularization (r = 2) and ε−3/2 for quartic regularization (r = 4).Source: §E.2 · p. 29

E.3 Links

  • Balanced random labels convert the margin-loss family into classification problems, so Theorem 3 applies to learners whose training labels provide additional independent randomness.Under the beta prior, E||μp||²=v=cvε^2/q, which is of order 1/n in the theorem’s sample-size range.Source: §E.3 · p. 29

E.4 Power Regularizers and Anisotropy

  • Power regularizers g(θ)=||Λθ||^r/r satisfy the required growth and curvature conditions when Λ’s singular values lie in a fixed positive bounded range.The examples include ridge and quartic regularization; regularizers with bounded Hessian near W satisfy the conditions for r=2.Source: §E.4 · pp. 29–30

E.5 Links with ϕ′(0) > 0

  • When ϕ′(0)>0, reflecting the link and negating the data preserves accuracy and the theorem’s information bounds, so the slope condition is |ϕ′(0)|>0.The reflected result retains the same threshold, dimension conditions, and constants; the zero-slope example shows that nonzero slope is necessary for the stated conclusion.Source: §E.5 · p. 30

E.6 Regularization Strength in a Compact Range

  • For regularizers αg with α in any fixed compact positive range, Theorem 3 holds uniformly with one threshold, dimension multiplier, and pair of constants.The uniform constants follow by bounding the curvature, growth, and gradient of αg using the range endpoints.Source: §E.6 · p. 31

E.7 Without a Regularizer

Without a regularizer, the two-sided information bound still holds at the optimal sample size n of order ε^-2. The accompanying bounds show that range-scaled ld-CMI can remain constant despite small generalization gaps, while loss-difference noise changes the information bound.

E.7 Without a Regularizer

  • The no-regularizer result uses properness in place of localization, because accuracy no longer localizes the learner's output.Without a regularizer the loss need not be uniformly convex, and the optimal sample size is of order ε^-2.Source: §E.7 · p. 31
  • At n of order ε^-2, accurate proper learners without a regularizer still satisfy a two-sided information bound, with noisy information scaling as n/(1 + (τ/ε)^2).The sample size is optimal: every such learner needs at least order ε^-2 samples, and projected SGD attains ε-accuracy with order ε^-2 samples.Source: Energy · p. 33

F.2 Proof of Corollary 5(i)

  • Every proper learner has generalization gap at most 4L/√n, even though some family law has an individual loss-difference information lower bound of order one.The range-scaled bounds therefore stay above a positive constant on some law of the family.Source: F Proofs for Section 4 · p. 34, §F.2 · p. 35

F.3 The Second-Moment Bound

  • Loss differences have range of order one but root-mean-square size of order ε, so range normalization—not a lack of information—explains the nonvanishing bound.The second-moment bound replaces the loss range by the root-mean-square loss difference.Source: §F.3 · p. 35

F.4 Noise at the Scale of the Range

  • For noise at the scale of the range, the information-based bound is at most twice the information-free limit; it decreases toward that limit as noise grows.For accurate learners, the residual bound makes the information-based bound at most a constant times ε, while the gap is at least a constant times ε on prior average.Source: §F.4 · p. 36

F.5 Differential Privacy, Proof of Corollary 5(ii)

The privacy argument audits signed loss differences rather than the model: accuracy forces their prior-averaged sum to be large, while differential privacy caps each pair's contribution. The surrounding results identify conditions under which accuracy does or does not force information.

F.5 Differential Privacy, Proof of Corollary 5(ii)

  • In the Theorem 3 regime, accuracy forces ε_DP = Ω(1) unless δ = Ω(ε).The audit statistic uses released loss differences and selection bits, never the model.Source: §F.5 · pp. 36–37

G.1 Every-Learner Lower Bound for Power-Linear Losses

  • For power-linear losses, every accurate proper learner has an information lower bound of order nε for n ≥ nε and d ≥ 32n, regardless of how large n is.The prior is fixed before the learner, and the transfer uses bounds on the signed mean and energy.Source: §G.1 · p. 39

G.2 Proof of Proposition 11

  • With mismatched growth, τ = ε = n^-2/3 and d ≥ 32n yield information between 0.007n^1/3 and 3n^1/3 for each measure, even for an accurate mean learner.The example has curvature of power 4 but growth of power 2.Source: §G.2 · p. 39

G.3 Zero Slope

  • When the link has zero slope at zero, the zero learner is accurate with zero excess risk and releases no information, at every noise level.Its loss-difference release is identically zero.Source: §G.3 · p. 40

G.4 Proof of Proposition 12

The dimension result bounds how much noisy loss-difference information a proper learner can release in low dimension, limiting where an order-n lower bound can hold. The following appendix also treats a model-level converse, but these passages do not state its details.

G.4 Proof of Proposition 12

  • If a proper learner releases information of order n at τ = ε, then dimension must be at least order n/log n under the stated sample-size conditions.In fixed dimension, every proper learner releases O(d log n) bits at τ of order ε.Source: §G.4 · pp. 41–42
  • The noisy information bound follows by covering the unit ball and using the Lipschitz loss-difference release map to bound information through the net size.The bound is capped by n and otherwise depends logarithmically on 1 + 4L√n/τ, multiplied by d.Source: §G.4 · p. 41

H Model information and the loss-difference release

  • Appendix H states and proves a model-level converse of Theorem 3, but this passage gives no further result details.It distinguishes model information from the loss-difference release.Source: H Model information and the… · p. 42

H.1 Data Processing and Tracers

This section examines how information about model outputs relates to loss-difference releases, including tracer-based training recall and release-to-model converses. It also covers measurements and analytical tools for power-linear learners, paired-sample geometry, ridge-ERM moments, and noisy release information.

H.1 Data Processing and Tracers

  • Loss-difference information obeys a data-processing hierarchy below model information, and a tracer’s low false-positive rate and high training recall imply a lower bound on loss-difference information.The hierarchy applies to noisy releases as well as noiseless ones; the tracer bound depends on its false-positive rate and expected training recall.Source: §H.1 · p. 42

H.2 What Transfers at Zero Noise

  • At zero noise, a strictly monotone score-based tracer with recall rec and false-positive rate ξ yields average bit-decoding success at least rec/n − ξ, and an information lower bound when this exceeds 1/2.The same tracing guarantees do not determine information after adding noise: they contain no information about margin sizes.Source: §H.2 · p. 43

H.3 Accuracy of Tr( ¯Z)

  • For the power-linear loss, Tr of the sample mean is a proper learner; at r=2 its expected excess risk is at most 1/(2n) on every law on the unit ball.The construction also gives a monotonicity-based stability bound for Tr, as stated in Lemma H.3(a).Source: §H.3 · pp. 43–44

H.4 The Pair Matrix Has Full Rank

  • For d≥32n under the zero-mean law, the pair matrix has rank n except with probability at most e^-225n/32; on full-rank supersamples, the noiseless release reveals all n selection bits.On every supersample, equal releases occur exactly when the training means are equal.Source: §H.4 · pp. 44–45

H.5 Model Information Does Not Determine the Tradeoff

  • At τ=n^-2/3, for each Q and every p, Q_Dp(X(2)+τG)≤3n^1/3, whereas Q_D0(X(4)+τG)≥n/8, separating the two smoothed quantities under these stated conditions.The learners’ noiseless information quantities I(X(2);U|eZ) and I(X(4);U|eZ) coincide and, at D0, are at least n(1−e^(-225n/32)).Source: §H.5 · p. 45
  • Each training point is flagged with probability at least 1−ξ, yielding expected training recall of at least n(1−ξ).Source: §H.5 · p. 47

H.6 The Model-Level Converse

  • c1n to n bits bound sup_p I_Dp(bθ; U | eZ) for learners of Theorem 3, showing that accuracy forces order-n model information on the family.The implication runs from release information to model information; model information does not determine information in noisy loss differences.Source: §H.6 · p. 47

I.1 Learners

  • 36 of 37 Monte Carlo comparisons fell within 95% intervals of exact ridge-ERM values, whose moment formulas cover signed loss-difference means and residual and total variance.The appendix describes Section 8 measurements and gives prior-averaged budgets for ridge ERM.Source: I Measurements · p. 47, §I.1 · p. 48

I.2 Setup

  • Runs used ε = 1/(2n), a rounded beta prior with v = 8/n, and noise levels from 0 to 100ε; dimensions included 32n and 64n.The 64n setting meets Theorem 3’s stated dimension condition, while 32n meets the proof condition specified for ridge ERM; Theorem 6 holds in every dimension.Source: §I.2 · p. 49

I.3 Estimators

  • ID_p(Y_i; U_i) ≥ (1−||μ_p||²)^2/[2 ln 2 n(V_p+nτ²)] gives an unfitted second-moment lower bound on per-pair information.The appendix also estimates a variational lower bound by cross-fitting an odd-cubic log-odds model, and uses a candidate-centered bound and a fitted noise-shape curve for comparisons.Source: §I.3 · p. 50

I.4 Results

For ridge ERM and logistic ridge ERM at d = 64n, total information grows approximately linearly at τ = 0 and τ = M/n, but remains roughly constant at τ = √n M/(2n). The quartic learner shows a similar noise tradeoff, while the measurements are prior averages and do not establish behavior at a single law.

I.4 Results

  • 139 of 144 estimates at d = 64n lie in Theorem 6's bracket up to their 95% intervals; the five exceptions are low-information tail estimates.The five exceptions occur at τ ≥ 13.5 M/n and have ι ≤ 0.0034.Source: §I.4 · p. 51
  • At τ = 0 and τ = M/n, total-information slopes are 0.993 and 1.009 for ridge ERM and 0.991 and 0.997 for logistic ridge ERM; at τ = √n M/(2n), they are −0.017 and −0.031.These slopes are for totals nι against n at d = 64n.Source: §I.4 · p. 51, Figure I.1 · p. 52

I.5 A Learner with Quartic Regularization

  • The quartic empirical risk minimizer has expected excess risk at most ε4 = 1.2 n^-2/3 at every law on the unit ball.Its regularizer has power r = 4, and the reported runs use d = 64n.Source: §I.5 · p. 52

Estimators.

  • The quartic release was computed from ridge runs because X(4) = ∥¯Z∥^-2/3 X(2), with ∥¯Z∥^2 recorded exactly in those runs.Its candidate-dependent residual reference is not the conditional mean, so its residual may exceed the smallest one.Source: §I.5 · p. 52

Results.

  • At τ = 0, quartic ι(0) is 0.888 to 0.913 bits per pair; its noise curve resembles ridge ERM's and 116 of 120 estimates lie in Theorem 6's bracket up to 95% intervals.The four exceptions are in the tail, with estimates at most 0.0014 bits per pair.Source: Results · p. 53
  • At τ = n^-2/3, quartic-release totals exceed ridge-release totals at all five tested sample sizes despite equal model information at every law.For n = 50, 100, 300, 1000, and 3000, the respective totals are 5.25, 12.4, 40.7, 141, and 428 bits for X(4), versus 1.76, 2.77, 4.39, 6.98, and 10.9 bits for X(2).Source: Results · p. 53

I.7 What the Measurements Do Not Show

  • Every reported value is a prior average that bounds the family worst case from below, not an estimate for any single law.The measurements also do not test the theorem's orders across all n, and no r = 4 learner with a nonlinear link was measured.Source: §I.7 · p. 54

J Related work in detail

The related-work discussion situates Theorem 3 among prior information, tracing, privacy, and membership-inference results, then details which proof ingredients are known and what the Lean 4 formalization covers. It distinguishes the theorem’s release-level conclusions from model-level information bounds and records formalization scope and differences from the text.

J Related work in detail

  • Table J.1 gives exact statements of results closest to Theorem 3, with notation and conventions clarified for comparing their conditions and implications.The table’s discussion also states what each result implies for the noisy release.Source: J Related work in detail · p. 54, Table J.1 · p. 55
  • Model-level lower bounds do not determine noisy-release information; Proposition H.5 gives learners with identical model information and tracer decisions but different release information at τ = n^-2/3.Theorem 3 instead provides matching lower and upper bounds for accurate proper learners across noise levels and yields order-n model information at τ = 0.Source: J Related work in detail · pp. 54, 56
  • For the affine case, earlier work contains the signed-mean and energy moment arguments; Theorem 3 adds nonlinear-link and matched-curvature bounds, an every-law residual upper bound, and two-sided noise dependence.The affine argument uses a beta-prior fingerprinting identity and accuracy through alignment with the population mean.Source: J Related work in detail · p. 56
  • The proof uses fingerprinting, uniform-convexity localization, a fair-bit inequality, Gaussian maximum entropy, symmetrization and contraction, and power-map inequalities.The listed tools support, respectively, information lower bounds, localization, information comparison, and the stated 4L/√n bound.Source: J Related work in detail · p. 56
  • The discussion distinguishes private-optimization and tracing results, practical membership-inference attacks, model-memorization limits, and alternative information bounds, noting that their settings or premises differ.The balanced-pair experiment neither gives nor contradicts guarantees for practical attacks on natural data; Theorem 3 also does not rule out several bounds based on other premises or observations.Source: J Related work in detail · pp. 56–57

K Lean 4 formalization

  • The Lean 4 project includes formal results beyond those used in the paper, and its verification script checks declaration dependencies against the three standard Lean and Mathlib axioms.The check also rules out proofs left incomplete with sorry.Source: K Lean 4 formalization · pp. 57–58
  • Table K.1 maps paper results to unique Lean declarations; “native” marks objects from Section 2, and the formal conventions specify information units, worst-case scope, and learner conditions.Information is measured in bits, and the formal statements include measurability and integrability conditions left implicit in the text.Source: K Lean 4 formalization · p. 58, Table K.1 · pp. 60–61
  • Formal statements use explicit thresholds and constants and differ from the text in several formulations; reported measurements, prior-work descriptions, and several identities or comparisons are not formalized.The appendix also records additional differences for the unregularized sample-size statements and the model-level converse.Source: K Lean 4 formalization · pp. 58–59
Loading 2610.09206v2…