A privacy-constrained information extraction problem is considered where for a pair of correlated discrete random variables (X,Y) governed by a given joint distribution, an agent observes Y and wants to convey to a potentially public user as much information about Y as possible while limiting the amount of information revealed about X. To this end, the so-called rate-privacy function is investigated to quantify the maximal amount of information (measured in terms of mutual information) that can be extracted from Y under a privacy constraint between X and the extracted information, where privacy is measured using either mutual information or maximal correlation. Properties of the rate-privacy function are analyzed and its information-theoretic and estimation-theoretic interpretations are presented for both the mutual information and maximal correlation privacy measures. It is also shown that the rate-privacy function admits a closed-form expression for a large family of joint distributions of (X,Y). Finally, the rate-privacy function under the mutual information privacy measure is considered for the case where (X,Y) has a joint probability density function by studying the problem where the extracted information is a uniform quantization of Y corrupted by additive Gaussian noise. The asymptotic behavior of the rate-privacy function is studied as the quantization resolution grows without bound and it is observed that not all of the properties of the rate-privacy function carry over from the discrete to the continuous case.
16 August 2018 in IEEE Transactions on Information Theory
We investigate the problem of estimating a random variable Y under a privacy constraint dictated by another correlated random variable X. When X and Y are discrete, we express the underlying privacy-utility tradeoff in terms of the privacy-constrained guessing probability h(PXY , ε), the maximum probability Pc(Y|Z) of correctly guessing Y given an auxiliary random variable Z, where the maximization is taken over all PZ|Y ensuring that Pc(X|Z) ≤ ε for a given privacy threshold ε ≥ 0. We prove that h(PXY , ·) is concave and piecewise linear, which allows us to derive its expression in closed form for any ε when X and Y are binary. In the non-binary case, we derive h(PXY , ε) in the high utility regime (i.e., for sufficiently large, but nontrivial, values of ε) under the assumption that Y and Z have the same alphabets. We also analyze the privacyconstrained guessing probability for two scenarios in which X, Y and Z are binary vectors. When X and Y are continuous random variables, we formulate the corresponding privacy-utility tradeoff in terms of sENSR(PXY , ε), the smallest normalized minimum mean squared-error (mmse) incurred in estimating Y from a Gaussian perturbation Z. Here the minimization is taken over a family of Gaussian perturbations Z for which the mmse of f(X) given Z is within a factor 1 – ε from the variance of f(X) for any non-constant real-valued function f. We derive tight upper and lower bounds for sENSR when Y is Gaussian. For general absolutely continuous random variables, we obtain a tight lower bound for sENSR(PXY , ε) in the high privacy regime, i.e., for small ε.
5 September 2019 in IEEE Transactions on Information Theory
Consider a data publishing setting for a dataset composed by both private and non-private features. The publisher uses an empirical distribution, estimated from $n$ i.i.d. samples, to design a privacy mechanism which is applied to new fresh samples afterward. In this paper, we study the discrepancy between the privacy-utility guarantees for the empirical distribution, used to design the privacy mechanism, and those for the true distribution, experienced by the privacy mechanism in practice. We first show that, for any privacy mechanism, these discrepancies vanish at speed $O(1/\sqrt {n})$ with high probability. These bounds follow from our main technical results regarding the Lipschitz continuity of the considered information leakage measures. Then we prove that the optimal privacy mechanisms for the empirical distribution approach the corresponding mechanisms for the true distribution as the sample size $n$ increases, thereby establishing the statistical consistency of the optimal privacy mechanisms. Finally, we introduce and study uniform privacy mechanisms which, by construction, provide privacy to all the distributions within a neighborhood of the estimated distribution and, thereby, guarantee privacy for the true distribution with high probability.
21 April 2022 in IEEE Transactions on Information Theory
We introduce a tunable loss function called $\alpha $ -loss, parameterized by $\alpha \in (0,\infty]$ , which interpolates between the exponential loss ( $\alpha = 1/2$ ), the log-loss ( $\alpha = 1$ ), and the 0–1 loss ( $\alpha = \infty $ ), for the machine learning setting of classification. Theoretically, we illustrate a fundamental connection between $\alpha $ -loss and Arimoto conditional entropy, verify the classification-calibration of $\alpha $ -loss in order to demonstrate asymptotic optimality via Rademacher complexity generalization techniques, and build-upon a notion called strictly local quasi-convexity in order to quantitatively characterize the optimization landscape of $\alpha $ -loss. Practically, we perform class imbalance, robustness, and classification experiments on benchmark image datasets using convolutional-neural-networks. Our main practical conclusion is that certain tasks may benefit from tuning $\alpha $ -loss away from log-loss ( $\alpha = 1$ ), and to this end we provide simple heuristics for the practitioner. In particular, navigating the $\alpha $ hyperparameter can readily provide superior model robustness to label flips ( $\alpha > 1$ ) and sensitivity to imbalanced classes ( $\alpha < 1$ ).
We capitalize on the Wasserstein distance to obtain two information-theoretic bounds on the generalization error of learning algorithms. First, we specialize the Wasserstein distance into total variation, by using the discrete metric. In this case we derive a generalization bound and, from a strong data-processing inequality, show how to narrow the bound by adding Gaussian noise to the output hypothesis. Second, we consider the Wasserstein distance under a generic metric. In this case we derive a generalization bound by exploiting the geometric nature of the Kantorovich-Rubinstein duality theorem. We illustrate the use of these bounds with examples. Our bounds can handle certain cases in which existing bounds via mutual information fail.
26 April 2021 in IEEE Transactions on Information Theory
Disparate treatment occurs when a machine learning model produces different decisions for individuals based on a legally protected or sensitive attribute (e.g., age, sex). In domains where prediction accuracy is paramount, it could potentially be acceptable to fit a model which exhibits disparate treatment. To evaluate the effect of disparate treatment, we compare the performance of split classifiers (i.e., classifiers trained and deployed separately on each group) with group-blind classifiers (i.e., classifiers which do not use a sensitive attribute). We introduce the benefit-of-splitting for quantifying the performance improvement by splitting classifiers. Computing the benefit-of-splitting directly from its definition could be intractable since it involves solving optimization problems over an infinite-dimensional functional space. Under different performance measures, we (i) prove an equivalent expression for the benefit-of-splitting which can be efficiently computed by solving small-scale convex programs; (ii) provide sharp upper and lower bounds for the benefit-of-splitting which reveal precise conditions where a group-blind classifier will always suffer from a non-trivial performance gap from the split classifiers. In the finite sample regime, splitting is not necessarily beneficial and we provide data-dependent bounds to understand this effect. Finally, we validate our theoretical results through numerical experiments on both synthetic and real-world datasets.