Skip to content
Preprint

Residual-Information Generalization Bounds Under Selective Privacy: Extended Version

Oct 2026 · 0 citations · 8 references
Computer Science Mathematics

TL;DR

This work derives complementary task-compression and individual-sample refinements, identifies 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.

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 $(X^n,Y^n)$, leaks at most $\epsilon_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)\leq\min\{nH(Y),nH(Y\mid X)+\epsilon_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 $\sqrt{\epsilon_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.

View source

Similar papers

Review Oct 2026

Learning Sparse Support under Differential Privacy: Adaptive Algorithms and Minimax Limits

Saturated Propose-test-release, a general mechanism that privately releases the output of a discrete selector with probability one once its stability certificate reaches a finite threshold, is introduced and a computable support-stability score is constructed.

Jian-Zhong Gu, T. Cai · 1 citation
Preprint Oct 2026

Generalization Bounds via Vector-Valued $L_p$ Correlation $V_\alpha$

Understanding generalization of randomized learning algorithms remains a central challenge. Mutual-information and total-variation bounds provide complementary ways to quantify data--hypothesis dependence, but they can behave quite differently in high-dimensional regimes. We study a one-parameter family of dependence m...

Mohammad Hossein Momeni Hamaneh, M. M. Mojahedian, M. Yassaee · 0 citations
Preprint Oct 2026

Finite-Query Coherent Projection of Black-Box Conditional Predictions

This work examines directional fidelity in a computable hard-marginal formulation that preserves direct black-box marginals in a computable hard-marginal formulation that preserves direct black-box marginals.

Yu-Yang Wu, Fan-Yu Zhou, Jin-Feng Zhou et al. · 0 citations
Preprint Oct 2026

On Privacy Mechanism Design Under a Bounded $\alpha$-Lift Leakage Constraint with $\chi^2$-Utility

We study the design of a statistical privacy mechanism under a bounded $\alpha$-lift leakage constraint. An agent observes useful data $Y$, which is arbitrarily correlated with private data $X$, and releases $U$. The goal is to maximize Pearson $\chi^2$-information $\chi^2(Y;U)$ while satisfying the point-wise privacy...

A. Zamani, Mohammad Amin Zarrabian, Parastoo Sadeghi et al. · 0 citations
#machine learning Preprint Oct 2026

On the Limits of Sparse Linear Model with Shuffled Differential Privacy

By extending the score attack framework to user-level data, a new lower bound of $\Omega$ is established for any user-level $(\epsilon,\delta)$-DP, showing that the proposed algorithm is near-optimal with only a gap of the factor $\log(d/k)$.

Yan Zhang, Jiong Tuo, Meng Ding et al. · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.