Residual-Information Generalization Bounds Under Selective Privacy: Extended Version
Abstract
Information-theoretic generalization bounds usually control dependence on the task sample, whereas selective privacy may constrain only a different, private coordinate. We study i.i.d. pairs (X,Y), where a learner observes (Xn,Yn), leaks at most εn nats about Xn, and incurs loss on Y. A chain-rule transfer converts this mismatched constraint into the closed-form universal certificate I(W;Yn)≤min{nH(Y),nH(Y| X)+εn}. Combining the certificate with mutual-information generalization yields a bound governed by residual task uncertainty and normalized privacy leakage. We derive complementary task-compression and individual-sample refinements, identify a sharp obstruction showing why selective privacy alone need not give a vanishing certificate, and invert the bound to obtain the exact leakage allowance for a prescribed generalization tolerance. We prove exact information-level achievability for deterministic-task and independent-residual source families and show that the resulting √(εn/n) generalization rate is tight up to a universal constant. We also give a fixed-horizon adaptive application in which conditional leakage costs add.
Related
- From Privacy to Generalization: Linear Max-Information Bounds for Differentially Private Learning Algorithms
- An Extended Generalization of RSK Correspondence via A Type Quiver Representations
- Weak Private Information Retrieval for Graph-based Storage under ε-privacy
- Design of Privacy-Preserving Estimators Under Prior Information Exposure
- Unifying Privacy Accounting: Information Equivalence and Information Loss
BibTeX
@misc{zamani2026residualinformation,
title = {{Residual-Information Generalization Bounds Under Selective Privacy: Extended Version}},
author = {Amirreza Zamani and Parastoo Sadeghi and Mikael Skoglund},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.15847},
eprint = {2610.15847},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.15847},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Residual-Information Generalization Bounds Under Selective Privacy: Extended Version
AU - Amirreza Zamani
AU - Parastoo Sadeghi
AU - Mikael Skoglund
PY - 2026
DA - 2026/10/11
PB - arXiv
DO - 10.48550/arxiv.2610.15847
UR - https://arxiv.org/abs/2610.15847
AB - Information-theoretic generalization bounds usually control dependence on the task sample, whereas selective privacy may constrain only a different, private coordinate. We study i.i.d. pairs (X,Y), where a learner observes (X^n,Y^n), leaks at most ε_n nats about X^n, and incurs loss on Y. A chain-rule transfer converts this mismatched constraint into the closed-form universal certificate I(W;Y^n)≤min{nH(Y),nH(Y| X)+ε_n}. Combining the certificate with mutual-information generalization yields a bound governed by residual task uncertainty and normalized privacy leakage. We derive complementary task-compression and individual-sample refinements, identify a sharp obstruction showing why selective privacy alone need not give a vanishing certificate, and invert the bound to obtain the exact leakage allowance for a prescribed generalization tolerance. We prove exact information-level achievability for deterministic-task and independent-residual source families and show that the resulting √(ε_n/n) generalization rate is tight up to a universal constant. We also give a fixed-horizon adaptive application in which conditional leakage costs add.
ER -