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

Abstract: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.

61 pages, of which 8 pages main text. Code, data and the Lean 4 formalization are in the ancillary files

Machine Learning (cs.LG); Information Theory (cs.IT); Machine Learning (stat.ML)

arXiv:2610.09206 [cs.LG]

(or arXiv:2610.09206v1 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2610.09206 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

experiments/code/analyze.py

experiments/code/analyze_budgets.py

experiments/code/bounds.py

experiments/code/check_logistic.py

experiments/code/check_logistic_fullsize.py

experiments/code/check_sim.py

experiments/code/estimator_direction_paper.py

experiments/code/make_outputs.py

experiments/code/make_paper_figure.py

experiments/code/merge_runs.py

experiments/code/regen_logistic_d64.sh

experiments/code/run_d64.sh

experiments/code/sgd_check.py

experiments/code/sim.py

experiments/code/sim_logistic.py

experiments/code/summarize_paper.py

experiments/code/summarize_quartic.py

experiments/data/paper/budgets.csv

experiments/data/paper/fig1a_band.csv

experiments/data/paper/fig1a_points.csv

experiments/data/paper/fig1b_generalization.csv

experiments/data/paper/info.csv

experiments/data/paper/lowdim.csv

experiments/data/paper/per_run.csv

experiments/data/paper/quartic_budgets.csv

experiments/data/paper/quartic_info.csv

experiments/data/paper/quartic_per_run.csv

experiments/data/paper/quartic_separation.csv

experiments/data/paper/runs.csv

experiments/data/paper/totals.csv

experiments/data/ridge/E1_info_adv.csv

experiments/data/ridge/E3_lowdim.csv

experiments/data/ridge/checks.csv

experiments/data/ridge/runs.csv

experiments/data/runs/L1000_budgets.json

experiments/data/runs/L1000_meas.csv

experiments/data/runs/L100_budgets.json

experiments/data/runs/L100_meas.csv

experiments/data/runs/L300_budgets.json

experiments/data/runs/L300_meas.csv

experiments/data/runs/L50_budgets.json

experiments/data/runs/L50_meas.csv

experiments/data/runs/R100.csv

experiments/data/runs/R1000.csv

experiments/data/runs/R1000_budgets.json

experiments/data/runs/R1000_checks.json

experiments/data/runs/R100_budgets.json

experiments/data/runs/R3000.csv

experiments/data/runs/R3000_budgets.json

experiments/data/runs/R3000_checks.json

experiments/data/runs/R50.csv

experiments/data/runs/R50_budgets.json

experiments/data/runs/runs.csv

experiments/quartic/explicit_constants.py

experiments/raw/E1d64_n300/meta.json

experiments/raw/E1d64_n300/trials.csv

experiments/raw/L1000/meta.json

experiments/raw/L1000/trials.csv

experiments/raw/L1000_c0/meta.json

experiments/raw/L1000_c1/meta.json

experiments/raw/L1000_c2/meta.json

experiments/raw/L1000_c3/meta.json

experiments/raw/L300/meta.json

experiments/raw/L300/trials.csv

experiments/raw/R100/meta.json

experiments/raw/R100/trials.csv

experiments/raw/R1000/meta.json

experiments/raw/R1000/trials.csv

experiments/raw/R3000/meta.json

experiments/raw/R3000/trials.csv

experiments/raw/R50/meta.json

experiments/raw/R50/trials.csv

experiments/raw/logistic_n100_d64/meta.json

experiments/raw/logistic_n100_d64/trials.csv

experiments/raw/logistic_n50_d64/meta.json

experiments/raw/logistic_n50_d64/trials.csv

lean/CheckAxioms.lean

lean/LossOnlyTraceability.lean

lean/LossOnlyTraceability/Dimension/Helpers.lean

lean/LossOnlyTraceability/Dimension/Necessity.lean

lean/LossOnlyTraceability/Fingerprint.lean

lean/LossOnlyTraceability/Privacy/DPBasic.lean

lean/LossOnlyTraceability/Privacy/DPImpossibility.lean

lean/LossOnlyTraceability/Privacy/DPSupersample.lean

lean/LossOnlyTraceability/Quartic.lean

lean/LossOnlyTraceability/Residual.lean

lean/LossOnlyTraceability/Sphere/Basic.lean

lean/LossOnlyTraceability/Sphere/Budgets.lean

lean/LossOnlyTraceability/Sphere/Constants.lean

lean/LossOnlyTraceability/Sphere/Family.lean

lean/LossOnlyTraceability/Sphere/Instances/Hexagon.lean

lean/LossOnlyTraceability/Sphere/Prior.lean

lean/LossOnlyTraceability/Sphere/Proper.lean

lean/LossOnlyTraceability/Sphere/Stein.lean

lean/LossOnlyTraceability/Sphere/Theorem.lean

lean/LossOnlyTraceability/Tracing/Conformal.lean

lean/LossOnlyTraceability/Tracing/Necessity.lean

lean/LossOnlyTraceability/Unsaturated/Certificate.lean

lean/LossOnlyTraceability/Unsaturated/Tightness.lean

lean/lake-manifest.json

lean/lakefile.toml

lean/scripts/audit_inventory.py

lean/scripts/test_theorem_inventory.py

lean/scripts/theorem_inventory.py

lean/scripts/verify.sh

lean/verification.log

(685 additional files not shown) You must enabled JavaScript to view entire file list.

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.