Text-to-image (T2I) generative models can create vivid, realistic images from textual descriptions. As these models proliferate, they expose new concerns about their ability to represent diverse demographic groups, propagate stereo-types, and efface minority populations. Despite growing attention to the "safe" and "responsible" design of artificial intelligence (AI), there is no established methodology to systematically measure and control representational harms in image generation. This paper introduces a novel frame-work to measure the representation of intersectional groups in images generated by T2I models by applying the Multi-Group Proportional Representation (MPR) metric. MPR evaluates the worst-case deviation of representation statistics across given population groups in images produced by a generative model, allowing for flexible and context-specific measurements based on user requirements. We also develop an algorithm to optimize T2I models for this metric. Through experiments, we demonstrate that MPR can effectively mea-sure representation statistics across multiple intersectional groups and, when used as a training objective, can guide models toward a more balanced generation across demo-graphic groups while maintaining generation quality.1

Machine learning models are routinely used to support decisions that affect individuals -- be it to screen a patient for a serious illness or to gauge their response to treatment. In these tasks, we are limited to learning models from datasets with noisy labels. In this paper, we study the instance-level impact of learning under label noise. We introduce a notion of regret for this regime, which measures the number of unforeseen mistakes due to noisy labels. We show that standard approaches to learning under label noise can return models that perform well at a population-level while subjecting individuals to a lottery of mistakes. We present a versatile approach to estimate the likelihood of mistakes at the individual-level from a noisy dataset by training models over plausible realizations of datasets without label noise. This is supported by a comprehensive empirical study of label noise in clinical prediction tasks. Our results reveal how failure to anticipate mistakes can compromise model reliability and adoption -- we demonstrate how we can address these challenges by anticipating and avoiding regretful decisions.

We propose a unified optimization framework for designing continuous and discrete noise distributions that ensure differential privacy (DP) by minimizing Rényi DP, a variant of DP, under a cost constraint. Rényi DP has the advantage that by considering different values of the Rényi parameter $\alpha$, we can tailor our optimization for any number of compositions. To solve the optimization problem, we reduce it to a finite-dimensional convex formulation and perform preconditioned gradient descent. The resulting noise distributions are then compared to their Gaussian and Laplace counterparts. Numerical results demonstrate that our optimized distributions are consistently better, with significant improvements in $(\varepsilon, \delta)$-DP guarantees in the moderate composition regimes, compared to Gaussian and Laplace distributions with the same variance.

In many applications across statistics, differential privacy, and machine learning, it is necessary to evaluate or bound an$f$-divergence between distributions of random vectors with independent components. Even for relatively simple distributions, such computations can become intractable unless the chosen$f$-divergence tensorizes. In this work, we introduce a formal definition of tensorization for$f$-divergences and present a necessary condition under which such tensorization can occur. Moreover, we demonstrate—under certain assumptions—that the only$f$-divergences admitting a polynomial tensorization formula of degree at most two are, essentially, the KL divergence, cross-entropy, and Hellinger divergences of order$\alpha$. Taken together, our findings represent an initial step toward a complete characterization of$f$-divergences that tensorize.

Large-language models (LLMs) are now able to produce text that is indistinguishable from human-generated content. This has fueled the development of watermarks that imprint a “signal” in LLM-generated text with minimal perturbation of an LLM's output. This paper provides an analysis of text watermarking in a one-shot setting. Through the lens of hypothesis testing with side information, we formulate and analyze the fundamental trade-off between watermark detection power and distortion in generated textual quality. We argue that a key component in watermark design is generating a coupling between the side information shared with the watermark detector and a random partition of the LLM vocabulary. Our analysis identifies the optimal coupling and randomization strategy under the worst-case LLM next-token distribution that satisfies a minentropy constraint. We provide a closed-form expression of the resulting detection rate under the proposed scheme and quantify the cost in a max-min sense. Finally, we numerically compare the proposed scheme with the theoretical optimum.

Best-of-$n$(BoN) sampling is a practical approach for aligning language model outputs with human preferences without expensive fine-tuning. BoN sampling is performed by generating$n$responses to a prompt and then selecting the sample that maximizes a reward function. BoN yields high reward values in practice at a distortion cost, as measured by the KL-divergence between the sampled and original distribution. This distortion is coarsely controlled by varying the number of samples: larger$n$yields a higher reward at a higher distortion cost. We introduce Soft Best-of-$n$sampling, a generalization of BoN that allows for smooth interpolation between the original distribution and reward-maximizing distribution through a temperature parameter A. We establish theoretical guarantees showing that Soft Best-of-n sampling converges sharply to the optimal tilted distribution at a rate of$O(1/n)$in KL and the expected (relative) reward. For sequences of discrete outputs, we analyze an additive reward model that reveals the fundamental limitations of blockwise sampling.

In differentially private distributed mean estimation (DP-DME), a central server computes the mean of vectors distributed across$n$users while preserving differential privacy (DP). DP-DME has been studied under various DP models, with distributed DP with secure aggregation and local DP (LDP) being the main models that do not rely on a trusted third party. Distributed DP-based schemes leverage correlated noise among users to achieve higher accuracy than LDP-based schemes, where users operate independently. However, the accuracy of distributed DP comes at the cost of higher communication overhead for generating correlated noise and complex multiround protocols to handle dropouts. In this work, we analyze the communication-accuracy trade-off in distributed DP-DME under arbitrary communication constraints, and propose a method to generate correlated noise strategically within these constraints to enable single-round dropout handling. Our results show that the communication costs of existing distributed DP-DME approaches can be substantially reduced with minimal impact on accuracy.

A common paradigm to improve the performance of large language models is optimizing for a reward model. Reward models assign a numerical score to an LLM’s output that indicates, for example, how likely it is to align with user preferences or safety goals. However, reward models are never perfect. They inevitably function as proxies for complex desiderata such as correctness, helpfulness, and safety. By overoptimizing for a misspecified reward, we can subvert intended alignment goals and reduce overall performance -- a phenomenon commonly referred to as reward hacking. In this work, we characterize reward hacking in inference-time alignment and demonstrate when and how we can mitigate it by hedging on the proxy reward. We study this phenomenon under Best-of-$n$ (BoN) and Soft Best-of-$n$ (SBoN), and we introduce Best-of-Poisson (BoP) that provides an efficient, near-exact approximation of the optimal reward-KL divergence policy at inference time. We show that the characteristic pattern of hacking as observed in practice (where the true reward first increases before declining) is an inevitable property of a broad class of inference-time mechanisms, including BoN and BoP. To counter this effect, we introduce $\texttt{HedgeTune}$, an efficient algorithm to find the optimal inference-time parameter. We demonstrate that hedging mitigates reward hacking and achieves superior reward-distortion tradeoffs on math, reasoning, and human-preference setups.

Differentially private (DP) mechanisms are difficult to interpret and calibrate because existing methods for mapping standard privacy parameters to concrete privacy risks—re-identification, attribute inference, and data reconstruction—are both overly pessimistic and inconsistent. In this work, we use the hypothesis-testing interpretation of DP ($f$-DP), and determine that bounds on attack success can take the same unified form across re-identification, attribute inference, and data reconstruction risks. Our unified bounds are (1) consistent across a multitude of attack settings, and (2) tunable, enabling practitioners to evaluate risk with respect to arbitrary, including worst-case, levels of baseline risk. Empirically, our results are tighter than prior methods using $\varepsilon$-DP, R\'enyi DP, and concentrated DP. As a result, calibrating noise using our bounds can reduce the required noise by 20% at the same risk level, which yields, e.g., an accuracy increase from 52% to 70% in a text classification task. Overall, this unifying perspective provides a principled framework for interpreting and calibrating the degree of protection in DP against specific levels of re-identification, attribute inference, or data reconstruction risk.

In AI research and practice, rigor remains largely understood in terms of methodological rigor---such as whether mathematical, statistical, or computational methods are correctly applied. We argue that this narrow conception of rigor has contributed to the concerns raised by the responsible AI community, including overblown claims about the capabilities of AI systems. Our position is that a broader conception of what rigorous AI research and practice should entail is needed. We believe such a conception---in addition to a more expansive understanding of 1) methodological rigor---should include aspects related to 2) what background knowledge informs what to work on (epistemic rigor); 3) how disciplinary, community, or personal norms, standards, or beliefs influence the work (normative rigor); 4) how clearly articulated the theoretical constructs under use are (conceptual rigor); 5) what is reported and how (reporting rigor); and 6) how well-supported the inferences from existing evidence are (interpretative rigor). In doing so, we also provide useful language and a framework for much needed dialogue about the AI community's work by researchers, policymakers, journalists, and other stakeholders.

Large language model (LLM) watermarks enable authentication of text provenance, curb misuse of machine-generated text, and promote trust in AI systems. Current watermarks operate by changing the next-token predictions output by an LLM. The updated (i.e., watermarked) predictions depend on random side information produced, for example, by hashing previously generated tokens. LLM watermarking is particularly challenging in low-entropy generation tasks -- such as coding -- where next-token predictions are near-deterministic. In this paper, we propose an optimization framework for watermark design. Our goal is to understand how to most effectively use random side information in order to maximize the likelihood of watermark detection and minimize the distortion of generated text. Our analysis informs the design of two new watermarks: HeavyWater and SimplexWater. Both watermarks are tunable, gracefully trading-off between detection accuracy and text distortion. They can also be applied to any LLM and are agnostic to side information generation. We examine the performance of HeavyWater and SimplexWater through several benchmarks, demonstrating that they can achieve high watermark detection accuracy with minimal compromise of text generation quality, particularly in the low-entropy regime. Our theoretical analysis also reveals surprising new connections between LLM watermarking and coding theory.

The aim of this paper is threefold: 1) we introduce a unified statistical characterization for the instantaneous power of a plethora of Gaussian-based fading models; 2) we propose a general framework for the power sum of either independent and identically distributed (i.i.d.) or independent and non-identically distributed (i.non-i.d.) fading distributions; and 3) we provide a unified performance assessment of wireless communications systems in the presence of small-scale fading channels. To accomplish these three goals, we first show that the instantaneous power of a broad Gaussian class of fading models is governed by a mixture of gamma (MG) distribution. Later, we propose novel, tractable, and efficient solutions for the exact sum statistics of i.i.d. and i.non-i.d. MG variates. Lastly, we show that two key performance indicators—namely, the average bit-error rate and the outage probability—of a maximal-ratio combining (MRC) diversity receiver subject to a wide variety of Gaussian-based fading channels can be expressed, in a unified fashion, as a weighted sum of the performance indicators of a single-branch wireless system subject to independent Nakagami-m fading channels. Extensive numerical simulations reveal the outstanding improvement in computational efficiency and mathematical tractability of our derived expressions when compared with state-of-the-art solutions.

The Right to be Forgotten is a core principle outlined by regulatory frameworks such as the EU’s General Data Protection Regulation (GDPR). This principle allows individuals to request that their personal data be deleted from deployed machine learning models. While "forgetting" can be naively achieved by retraining on the remaining dataset, it is computationally expensive to do to so with each new request. As such, several machine unlearning methods have been proposed as efficient alternatives to retraining. These methods aim to approximate the predictive performance of retraining, but fail to consider how unlearning impacts other properties critical to real-world applications such as fairness. In this work, we demonstrate that most efficient unlearning methods cannot accommodate popular fairness interventions, and we propose the first fair machine unlearning method that can efficiently unlearn data instances from a fair objective. We derive theoretical results which demonstrate that our method can provably unlearn data and provably maintain fairness performance. Extensive experimentation with real-world datasets highlight the efficacy of our method at unlearning data instances while preserving fairness. Code is provided at https://github.com/AI4LIFE-GROUP/fair-unlearning.

We formulate a fundamental limit in differential privacy under growing composition. We introduce the universal composition curve: the best privacy guarantee under repeated composition of a given privacy mechanism given only the sensitivity of the query. We define privacy capacity as the slowest growth rate of this universal composition curve among all privacy mechanisms. We show that, in the limit of large compositions, privacy capacity “single-letterizes” as a minimax KL-divergence term. Our privacy capacity formula extends previous literature results that connect differential privacy and KL-divergence via concentration theorems.

We consider the problem of private approximate nearest neighbor (ANN) search. A user seeks the closest vector to a target query$q$among$M$vectors stored in a system of$N$non-colluding databases. The user aims to retrieve the ANN without revealing information about$q$to any of the$N$databases. We provide an information-theoretic formulation of the problem and propose a scheme based on a tree-structured ANN search mechanism. The proposed scheme uses a coding-theoretic approach to traverse the branch in the tree structure that leads to the approximately closest vector to$q$while guaran-teeing perfect information-theoretic privacy. We prove that our approach achieves a communication cost of$O(N^{2}M^{\frac{1}{N-1})}$for$N$databases. For large$M$, this communication cost is lower than competing cryptographic ANN search protocols.

We investigate the mixing times of Markov kernels under$\mathsf{E}_{\gamma}-\mathbf{divergence}$. We demonstrate that the zero-error$\mathsf{E}_{\gamma}- \mathbf{mixing}$time, for any$\gamma > 1$, of irreducible and aperiodic Markov chains, is bounded, a property that is not shared by the TV-mixing time. We further obtain upper bounds on the$\mathsf{E}_{\gamma}-\mathbf{mixing}$times for a broad family of contractive Markov kernels via a new non-linear strong data processing inequality for the$\mathsf{E}_{\gamma}- \mathbf{divergence}$. We apply our results to derive new bounds for the local differential privacy guarantees offered by the sequential application of a privacy mechanism to data.

CLIP embeddings have demonstrated remarkable performance across a wide range of multimodal applications. However, these high-dimensional, dense vector representations are not easily interpretable, limiting our understanding of the rich structure of CLIP and its use in downstream applications that require transparency. In this work, we show that the semantic structure of CLIP's latent space can be leveraged to provide interpretability, allowing for the decomposition of representations into semantic concepts. We formulate this problem as one of sparse recovery and propose a novel method, Sparse Linear Concept Embeddings (SpLiCE), for transforming CLIP representations into sparse linear combinations of human-interpretable concepts. Distinct from previous work, \method is task-agnostic and can be used, without training, to explain and even replace traditional dense CLIP representations, maintaining high downstream performance while significantly improving their interpretability. We also demonstrate significant use cases of \method representations including detecting spurious correlations and model editing. Code is provided at https://github.com/AI4LIFE-GROUP/SpLiCE.

Differential privacy (DP) is a widely used approach for mitigating privacy risks when training machine learning models on sensitive data. DP mechanisms add noise during training to limit the risk of information leakage. The scale of the added noise is critical, as it determines the trade-off between privacy and utility. The standard practice is to select the noise scale to satisfy a given privacy budget ε. This privacy budget is in turn interpreted in terms of operational attack risks, such as accuracy, sensitivity, and specificity of inference attacks aimed to recover information about the training data records. We show that first calibrating the noise scale to a privacy budget ε, and then translating ε to attack risk leads to overly conservative risk assessments and unnecessarily low utility. Instead, we propose methods to directly calibrate the noise scale to a desired attack risk level, bypassing the step of choosing ε. For a given notion of attack risk, our approach significantly decreases noise scale, leading to increased utility at the same level of privacy. We empirically demonstrate that calibrating noise to attack sensitivity/specificity, rather than ε, when training privacy-preserving ML models substantially improves model accuracy for the same risk level. Our work provides a principled and practical way to improve the utility of privacy-preserving ML without compromising on privacy.

Image search and retrieval tasks can perpetuate harmful stereotypes, erase cultural identities, and amplify social disparities. Current approaches to mitigate these representational harms balance the number of retrieved items across population groups defined by a small number of (often binary) attributes. However, most existing methods overlook intersectional groups determined by combinations of group attributes, such as gender, race, and ethnicity. We introduce Multi-Group Proportional Representation (MPR), a novel metric that measures representation across intersectional groups. We develop practical methods for estimating MPR, provide theoretical guarantees, and propose optimization algorithms to ensure MPR in retrieval. We demonstrate that existing methods optimizing for equal and proportional representation metrics may fail to promote MPR. Crucially, our work shows that optimizing MPR yields more proportional representation across multiple intersectional groups specified by a rich function class, often with minimal compromise in retrieval accuracy. Code is provided at https://github.com/alex-oesterling/multigroup-proportional-representation.

Feature attribution methods explain black-box machine learning (ML) models by assigning importance scores to input features. These methods can be computationally expensive for large ML models. To address this challenge, there have been increasing efforts to develop amortized explainers, where a ML model is trained to efficiently approximate computationally expensive feature attribution scores. Despite their efficiency, amortized explainers can produce misleading explanations. In this paper, we propose selective explanations to (i) detect when amortized explainers generate inaccurate explanations and (ii) improve the approximation of the explanation using a technique we call explanations with initial guess. Selective explanations allow practitioners to specify the fraction of samples that receive explanations with initial guess, offering a principled way to bridge the gap between amortized explainers (one inference) and more computationally costly approximations (multiple inferences). Our experiments on various models and datasets demonstrate that feature attributions via selective explanations strike a favorable balance between explanation quality and computational efficiency.

We investigate the problem of representing information measures in terms of the moments of the underlying random variables. First, we derive polynomial approximations of the conditional expectation operator. We then apply these approximations to bound the best mean-square error achieved by a polynomial estimator—referred to here as the PMMSE. In Gaussian channels, the PMMSE coincides with the minimum mean-square error (MMSE) if and only if the input is either Gaussian or constant, i.e., if and only if the conditional expectation of the input of the channel given the output is a polynomial of degree at most 1. By combining the PMMSE with the I-MMSE relationship, we derive new formulas for information measures (e.g., differential entropy, mutual information) that are given in terms of the moments of the underlying random variables. As an application, we introduce estimators for information measures from data via approximating the moments in our formulas by sample moments. These estimators are shown to be asymptotically consistent and possess desirable properties, e.g., invariance to affine transformations when used to estimate mutual information.

We characterize the differential privacy guarantees of privacy mechanisms in the large-composition regime, i.e., when a privacy mechanism is sequentially applied a large number of times to sensitive data. Via exponentially tilting the privacy loss random variable, we derive a new formula for the privacy curve expressing it as a contour integral over an integration path that runs parallel to the imaginary axis with a free real-axis intercept. Then, using the method of steepest descent from mathematical physics, we demonstrate that the choice of saddle-point as the real-axis intercept yields closed-form accurate approximations of the desired contour integral. This procedure---dubbed the saddle-point accountant (SPA)---yields a constant-time accurate approximation of the privacy curve. Theoretically, our results can be viewed as a refinement of both Gaussian Differential Privacy and the moments accountant method found in Rényi Differential Privacy. In practice, we demonstrate through numerical experiments that the SPA provides a precise approximation of privacy guarantees competitive with purely numerical-based methods (such as FFT-based accountants), while enjoying closed-form mathematical expressions.

We study the multi-agent Bayesian optimization (BO) problem, where multiple agents maximize a black-box function via iterative queries. We focus on Entropy Search (ES), a sample-efficient BO algorithm that selects queries to maximize the mutual information about the maximum of the black-box function. One of the main challenges of ES is that calculating the mutual information requires computationallycostly approximation techniques. For multi-agent BO problems, the computational cost of ES is exponential in the number of agents. To address this challenge, we propose the Gaussian Max-value Entropy Search, a multi-agent BO algorithm with favorable sample and computational efficiency. The key to our idea is to use a normal distribution to approximate the function maximum and calculate its mutual information accordingly. The resulting approximation allows queries to be cast as the solution of a closed-form optimization problem which, in turn, can be solved via a modified gradient ascent algorithm and scaled to a large number of agents. We demonstrate the effectiveness of Gaussian max-value Entropy Search through numerical experiments on standard test functions and real-robot experiments on the source seeking problem. Results show that the proposed algorithm outperforms the multi-agent BO baselines in the numerical experiments and can stably seek the source with a limited number of noisy observations on real robots.

We construct vector differentially-private (DP) mechanisms that are asymptotically optimal in the limit of the number of compositions growing without bound. First, we derive via the central limit theorem a reduction from DP to a KL-divergence minimization problem. Second, we formulate the general theory of spherically-symmetric DP mechanisms in the large-composition regime. Specifically, we show that additive, continuous, spherically-symmetric DP mechanisms are optimal if one considers a spherically-symmetric cost (e.g., bounded noise variance) and an ℓ2sensitivity metric. We then formulate a finite-dimensional problem that produces noise distributions that can get arbitrarily close to optimal among monotone mechanisms. Finally, we demonstrate numerically that our proposed mechanism achieves better DP parameters than the vector Gaussian mechanism for the same variance constraint.

We consider the problem of designing optimal differential privacy mechanisms with a favorable privacy-utility tradeoff in the limit of a large number n of compositions (i.e., sequential queries). Here, utility is measured by the average distance between the mechanism's input and output, evaluated by a cost function c. We show that if n is sufficiently large and the sensitivities of all queries are small, then the optimal additive noise mechanism has probability density function fully characterized by the ground-state eigenfunction of the Schrödinger operator with potential c. This leads to a family of optimal mechanisms, dubbed the Schrödinger mechanisms, depending on the choice of the cost function. Instantiating this result, we demonstrate that for c(x) = x2the Gaussian mechanism is optimal, and for c(x) = |x|, the optimal mechanism is obtained by the Airy function, thereby leading to the Airy mechanism.

We consider the problem of private distributed multiparty computation. It is well-established that coding strategies can enable perfect information-theoretic privacy in distributed computation (e.g., the BGW protocol). However, perfect privacy comes at a high computational overhead cost, requiring 2t + 1 compute nodes to ensure privacy against any t colluding nodes. By allowing for approximate computation and operations over the real numbers, we demonstrate that noise can be added to data shared with computing nodes in order to ensure differential privacy instead of perfect privacy. Specifically, the signal-to-noise ratio of the data received by colluding nodes can be mapped to differential privacy guarantees. We precisely characterize the trade-off between differential privacy and accuracy in this setting, and prove that a degree of differential privacy against t colluding nodes can always be ensured whenever there are more than t+1 computing node—a reduction of t nodes compared to perfect privacy. A particularly novel technical aspect is an achievable scheme that carefully encodes the data and noise at different magnitude levels. This coding scheme ensures that the adversary’s input appears to be layers of noise, whereas the legitimate decoder is able to uncover the desired computation by "peeling" off the noise layers.

The Rashomon effect in machine learning (ML) occurs when multiple distinct models achieve similar average loss on a given learning task. The set of all models with expected loss smaller than ϵ is called the Rashomon set. The characterization of this set for a given learning task allows searching for models that satisfy additional constraints (e.g., interpretability, fairness) without compromising accuracy. Though folklore treats the Rashomon set as the collection of all indistinguishable "good" models, there are no established theoretical guarantees that models in this set are statistically indistinguishable. We fill this gap by proposing a hypothesis test framework to choose the best-performing model between two elements in the Rashomon set and derive lower and upper bounds for its probability of error. Specifically, we prove that for any ϵ > 0 if the data set has less than $O\left( {{{[\varepsilon {\text{log}}\left( {\varepsilon /\left( {1 - \varepsilon } \right)} \right)]}^{ - 1}}} \right)$ instances, models in the Rashomon set are statistically indistinguishable and the Rashomon effect is inevitable. Additionally, our bounds can guide data scientists to choose an ϵ that generates a Rashomon set so that any two models in it are indistinguishable.

Missing values in real-world data pose a significant and unique challenge to algorithmic fairness. Different demographic groups may be unequally affected by missing data, and the standard procedure for handling missing values where first data is imputed, then the imputed data is used for classification—a procedure referred to as "impute-then-classify"—can exacerbate discrimination. In this paper, we analyze how missing values affect algorithmic fairness. We first prove that training a classifier from imputed data can significantly worsen the achievable values of group fairness and average accuracy. This is because imputing data results in the loss of the missing pattern of the data, which often conveys information about the predictive label. We present scalable and adaptive algorithms for fair classification with missing values. These algorithms can be combined with any preexisting fairness-intervention algorithm to handle all possible missing patterns while preserving information encoded within the missing patterns. Numerical experiments with state-of-the-art fairness interventions demonstrate that our adaptive algorithms consistently achieve higher fairness and accuracy than impute-then-classify across different datasets.

Machine learning tasks may admit multiple competing models that achieve similar performance yet produce conflicting outputs for individual samples---a phenomenon known as predictive multiplicity. We demonstrate that fairness interventions in machine learning optimized solely for group fairness and accuracy can exacerbate predictive multiplicity. Consequently, state-of-the-art fairness interventions can mask high predictive multiplicity behind favorable group fairness and accuracy metrics. We argue that a third axis of ``arbitrariness'' should be considered when deploying models to aid decision-making in applications of individual-level impact. To address this challenge, we propose an ensemble algorithm applicable to any fairness intervention that provably ensures more consistent predictions.

Machine learning (ML) models can underperform on certain population groups due to choices made during model development and bias inherent in the data. We categorize sources of discrimination in the ML pipeline into two classes: aleatoric discrimination, which is inherent in the data distribution, and epistemic discrimination, which is due to decisions made during model development. We quantify aleatoric discrimination by determining the performance limits of a model under fairness constraints, assuming perfect knowledge of the data distribution. We demonstrate how to characterize aleatoric discrimination by applying Blackwell's results on comparing statistical experiments. We then quantify epistemic discrimination as the gap between a model's accuracy when fairness constraints are applied and the limit posed by aleatoric discrimination. We apply this approach to benchmark existing fairness interventions and investigate fairness risks in data with missing values. Our results indicate that state-of-the-art fairness interventions are effective at removing epistemic discrimination on standard (overused) tabular datasets. However, when data has missing values, there is still significant room for improvement in handling aleatoric discrimination.

Machine learning models trained by different optimization algorithms under different data distributions can exhibit distinct generalization behaviors. In this paper, we analyze the generalization of models trained by noisy iterative algorithms. We derive distribution-dependent generalization bounds by connecting noisy iterative algorithms to additive noise channels found in communication and information theory. Our generalization bounds shed light on several applications, including differentially private stochastic gradient descent (DP-SGD), federated learning, and stochastic gradient Langevin dynamics (SGLD). We demonstrate our bounds through numerical experiments, showing that they can help understand recent empirical observations of the generalization phenomena of neural networks.

Bottleneck problems are an important class of optimization problems that have recently gained increasing attention in the domain of machine learning and information theory. They are widely used in generative models, fair machine learning algorithms, design of privacy-assuring mechanisms, and appear as information-theoretic performance bounds in various multi-user communication problems. In this work, we propose a general family of optimization problems, termed ascomplexity-leakage-utility bottleneck (CLUB)model, which (i) provides a unified theoretical framework that generalizes most of the state-of-the-art literature for the information-theoretic privacy models, (ii) establishes a new interpretation of the popular generative and discriminative models, (iii) constructs new insights for the generative compression models, and (iv) can be used to obtain fair generative models. We first formulate the CLUB model as a complexity-constrained privacy-utility optimization problem. We then connect it with the closely related bottleneck problems, namely information bottleneck (IB), privacy funnel (PF), deterministic IB (DIB), conditional entropy bottleneck (CEB), and conditional PF (CPF). We show that the CLUB model generalizes all these problems as well as most other information-theoretic privacy models. Then, we construct the deep variational CLUB (DVCLUB) models by employing neural networks to parameterize variational approximations of the associated information quantities. Building upon these information quantities, we present unified objectives of thesupervisedandunsupervisedDVCLUB models. Leveraging the DVCLUB model in an unsupervised setup, we then connect it with state-of-the-art generative models, such as variational auto-encoders (VAEs), generative adversarial networks (GANs), as well as the Wasserstein GAN (WGAN), Wasserstein auto-encoder (WAE), and adversarial auto-encoder (AAE) models through the optimal transport (OT) problem. We then show that the DVCLUB model can also be used in fair representation learning problems, where the goal is to mitigate the undesired bias during the training phase of a machine learning model. We conduct extensive quantitative experiments on colored-MNIST and CelebA datasets.

We investigate the fairness concerns of training a machine learning model using data with missing values. Even though there are a number of fairness intervention methods in the literature, most of them require a complete training set as input. In practice, data can have missing values, and data missing patterns can depend on group attributes (e.g. gender or race). Simply applying off-the-shelf fair learning algorithms to an imputed dataset may lead to an unfair model. In this paper, we first theoretically analyze different sources of discrimination risks when training with an imputed dataset. Then, we propose an integrated approach based on decision trees that does not require a separate process of imputation and learning. Instead, we train a tree with missing incorporated as attribute (MIA), which does not require explicit imputation, and we optimize a fairness-regularized objective function. We demonstrate that our approach outperforms existing fairness intervention methods applied to an imputed dataset, through several experiments on real-world datasets.

Most differential privacy mechanisms are applied (i.e., composed) numerous times on sensitive data. We study the design of optimal differential privacy mechanisms in the limit of a large number of compositions. As a consequence of the law of large numbers, in this regime the best privacy mechanism is the one that minimizes the Kullback-Leibler divergence between the conditional output distributions of the mechanism given two different inputs. We formulate an optimization problem to minimize this divergence subject to a cost constraint on the noise. We first prove that additive mechanisms are optimal. Since the optimization problem is infinite dimensional, it cannot be solved directly; nevertheless, we quantize the problem to derive nearoptimal additive mechanisms that we call "cactus mechanisms" due to their shape. We show that our quantization approach can be arbitrarily close to an optimal mechanism. Surprisingly, for quadratic cost, the Gaussian mechanism is strictly suboptimal compared to this cactus mechanism. Finally, we provide numerical results which indicate that cactus mechanisms outperform Gaussian and Laplace mechanisms for a finite number of compositions.The full proofs can be found in the extended version at [1]. This paper is Part I in a pair of papers, where Part II is [2].

The classic BGW algorithm of Ben Or, Goldwasser and Wigderson for secure multiparty computing demonstrates that secure distributed matrix multiplication over finite fields is possible over 2t+1 computation nodes, while keeping the input matrices private from every t colluding computation nodes. In this paper, we develop and study a novel coding formulation to explore the trade-offs between computation accuracy and privacy in secure multiparty computing for real-valued data, even with fewer than 2t+1 nodes, through a differential privacy perspective. For the case of t = 1, we develop achievable schemes and converse arguments that bound ϵ — the differential privacy parameter that measures the privacy loss — for a given accuracy level. Our achievable coding schemes are specializations of Shamir secret sharing applied to real-valued data, coupled with appropriate choice of evaluation points. We develop converse arguments that apply for general additive noise based schemes.

We consider the problem of producing fair probabilistic classifiers for multi-class classification tasks. We formulate this problem in terms of ``projecting'' a pre-trained (and potentially unfair) classifier onto the set of models that satisfy target group-fairness requirements. The new, projected model is given by post-processing the outputs of the pre-trained classifier by a multiplicative factor. We provide a parallelizable, iterative algorithm for computing the projected classifier and derive both sample complexity and convergence guarantees. Comprehensive numerical comparisons with state-of-the-art benchmarks demonstrate that our approach maintains competitive performance in terms of accuracy-fairness trade-off curves, while achieving favorable runtime on large datasets. We also evaluate our method at scale on an open dataset with multiple classes, multiple intersectional groups, and over 1M samples.

Predictive multiplicity occurs when classification models with statistically indistinguishable performances assign conflicting predictions to individual samples. When used for decision-making in applications of consequence (e.g., lending, education, criminal justice), models developed without regard for predictive multiplicity may result in unjustified and arbitrary decisions for specific individuals. We introduce a new metric, called Rashomon Capacity, to measure predictive multiplicity in probabilistic classification. Prior metrics for predictive multiplicity focus on classifiers that output thresholded (i.e., 0-1) predicted classes. In contrast, Rashomon Capacity applies to probabilistic classifiers, capturing more nuanced score variations for individual samples. We provide a rigorous derivation for Rashomon Capacity, argue its intuitive appeal, and demonstrate how to estimate it in practice. We show that Rashomon Capacity yields principled strategies for disclosing conflicting models to stakeholders. Our numerical experiments illustrate how Rashomon Capacity captures predictive multiplicity in various datasets and learning models, including neural networks. The tools introduced in this paper can help data scientists measure and report predictive multiplicity prior to model deployment.

Machine learning models are often personalized by using group attributes that encode personal characteristics (e.g., sex, age group, HIV status). In such settings, individuals expect to receive more accurate predictions in return for disclosing group attributes to the personalized model. We study when we can tell that a personalized model upholds this principle for every group who provides personal data. We introduce a metric called the benefit of personalization (BoP) to measure the smallest gain in accuracy that any group expects to receive from a personalized model. We describe how the BoP can be used to carry out basic routines to audit a personalized model, including: (i) hypothesis tests to check that a personalized model improves performance for every group; (ii) estimation procedures to bound the minimum gain in personalization. We characterize the reliability of these routines in a finite-sample regime and present minimax bounds on both the probability of error for BoP hypothesis tests and the mean-squared error of BoP estimates. Our results show that we can only claim that personalization improves performance for each group who provides data when we explicitly limit the number of group attributes used by a personalized model. In particular, we show that it is impossible to reliably verify that a personalized classifier with $k \geq 19$ binary group attributes will benefit every group who provides personal data using a dataset of $n = 8\times10^9$ samples -- one for each person in the world.

Correspondence analysis (CA) is a multivariate statistical tool used to visualize and interpret data dependencies by finding maximally correlated embeddings of pairs of random variables. CA has found applications in fields ranging from epidemiology to social sciences. However, current methods for CA do not scale to large, high-dimensional datasets. In this paper, we provide a novel interpretation of CA in terms of an information-theoretic quantity called the principal inertia components. We show that estimating the principal inertia components, which consists in solving a functional optimization problem over the space of finite variance functions of two random variable, is equivalent to performing CA. We then leverage this insight to design algorithms to perform CA at scale. Specifically, we demonstrate how the principal inertia components can be reliably approximated from data using deep neural networks. Finally, we show how the maximally correlated embeddings of pairs of random variables in CA further play a central role in several learning problems including multi-view and multi-modal learning methods and visualization of classification boundaries.

Lossless compression of datasets is a problem of significant theoretical and practical interest. It appears naturally in the task of storing, sending, or archiving large collections of information for scientific research. We can greatly improve encoding bitrate if we allow the compression of the original dataset to decompress to a permutation of the data. We prove the equivalence of dataset compression to compressing a permutation-invariant structure of the data and implement such a scheme via predictive coding. We benchmark our compression procedure against state-of-the-art compression utilities on the popular machine-learning datasets MNIST and CIFAR-10 and outperform for multiple parameter sets.

In this paper, we propose a framework for privacy-preserving approximate near neighbor search via stochastic sparsifying encoding. The core of the framework relies on sparse coding with ambiguation (SCA) mechanism that introduces the notion of inherent shared secrecy based on the support intersection of sparse codes. This approach is ‘fairness-aware’, in the sense that any point in the neighborhood has an equiprobable chance to be chosen. Our approach can be applied to raw data, latent representation of autoencoders, and aggregated local descriptors. The proposed method is tested on both synthetic i.i.d data and real image databases.

Disparate treatment occurs when a machine learning model produces different decisions for groups of individuals based on a 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 when the underlying data distribution is known. Computing the benefit-of-splitting directly from its definition 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. A full version of this paper is accessible at [1].

We consider a channel$Y=X+N$where$X$is a random variable satisfying$\mathbb{E}[\vert X\vert] < \infty$and$N$is an independent standard normal random variable. We show that the minimum mean-square estimator of$X$from$Y$, which is given by the conditional expectation$\mathbb{E}[X\vert Y]$, is a polynomial in$Y$if and only if it is linear or constant; these two cases correspond to$X$being Gaussian or a constant, respectively. We also prove that the higher-order derivatives of$y\rightarrow \mathbb{E}[X\vert Y=y]$are expressible as multivariate polynomials in the functions$y\rightarrow \mathbb{E}[(X-\mathbb{E}[X\vert Y])^{k}-\vert Y=y]$for$k\in \mathbb{N}$. These expressions yield bounds on the 2-norm of the derivatives of the conditional expectation. These bounds imply that, if$X$has a compactly-supported density that is even and decreasing on the positive half-line, then the error in approximating the conditional expectation$\mathbb{E}[X\vert Y]$by polynomials in$Y$of degree at most$n$decays faster than any polynomial in$n$.

We investigate the local differential privacy (LDP) guarantees of a randomized privacy mechanism via its contraction properties. We first show that LDP constraints can be equivalently cast in terms of the contraction coefficient of the$\mathsf{E}_{\gamma}$-divergence. We then use this equivalent formula to express LDP guarantees of privacy mechanisms in terms of contraction coefficients of arbitrary$f$-divergences. When combined with standard estimation-theoretic tools (such as Le Cam's and Fano's converse methods), this result allows us to study the trade-off between privacy and utility in several testing and minimax and Bayesian estimation problems.

We propose a new technique for deriving the differential privacy parameters in federated learning (FL). We consider the setting where a machine learning model is iteratively trained using stochastic gradient descent (SGD) and only the last update is publicly released. In this approach, we interpret each training iteration as a Markov kernel. We then quantify the impact of the kernel on privacy parameters via the contraction coefficient of the$E_{\gamma}$-divergence that underlies differential privacy. To do so, we generalize the well-known Dobrushin's ergodicity coefficient, originally defined in terms of total variation distance, to a family of$f$-divergences. We then analyze the convergence rate of SGD under the proposed private FL framework.

We study coded distributed matrix multiplication from an approximate recovery viewpoint. We consider a system of$P$computation nodes where each node stores 1/m of each multiplicand via linear encoding. Our main result shows that the matrix product can be recovered with ∊ relative error from any$m$of the$P$nodes for any ∊ >0. We obtain this result through a careful specialization of MatDot codes-a class of matrix multiplication code previously developed in the context of exact recovery (∊ = 0). Since previous results showed that the MatDot code is tight for a class of linear coding schemes for exact recovery, our result shows that allowing for mild approximations leads to a system that is nearly twice as efficient as exact reconstruction. Moreover, we develop an optimization framework based on alternating minimization that enables the discovery of new codes for approximate matrix multiplication.

Optimization is a key component for training machine learning models and has a strong impact on their generalization. In this paper, we consider a particular optimization method---the stochastic gradient Langevin dynamics (SGLD) algorithm---and investigate the generalization of models trained by SGLD. We derive a new generalization bound by connecting SGLD with Gaussian channels found in information and communication theory. Our bound can be computed from the training data and incorporates the variance of gradients for quantifying a particular kind of "sharpness" of the loss landscape. We also consider a closely related algorithm with SGLD, namely differentially private SGD (DP-SGD). We prove that the generalization capability of DP-SGD can be amplified by iteration. Specifically, our bound can be sharpened by including a time-decaying factor if the DP-SGD algorithm outputs the last iterate while keeping other iterates hidden. This decay factor enables the contribution of early iterations to our bound to reduce with time and is established by strong data processing inequalities---a fundamental tool in information theory. We demonstrate our bound through numerical experiments, showing that it can predict the behavior of the true generalization gap.

This paper considers fair probabilistic binary classification where the outputs of primary interest are predicted probabilities, commonly referred to as scores. We formulate the problem of transforming scores to satisfy fairness constraints that are linear in conditional means of scores while minimizing a cross-entropy objective. The formulation can be applied directly to post-process classifier outputs and we also explore a pre-processing extension, thus allowing maximum freedom in selecting a classification algorithm. We derive a closed-form expression for the optimal transformed scores and a convex optimization problem for the transformation parameters. In the population limit, the transformed score function is the fairness-constrained minimizer of cross-entropy with respect to the true conditional probability of the outcome. In the finite sample setting, we propose a method called FairScoreTransformer to approach this solution using a combination of standard probabilistic classifiers and ADMM. We provide several consistency and finite-sample guarantees for FairScoreTransformer, relating to the transformation parameters and transformed score function that it obtains. Comprehensive experiments comparing to 10 existing methods show that FairScoreTransformer has advantages for score-based metrics such as Brier score and AUC while remaining competitive for binary label-based metrics such as accuracy.

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.

Identifying features that leak information about sensitive attributes is a key challenge in the design of information obfuscation mechanisms. In this paper, we propose a framework to identify information-leaking features via information density estimation. Here, features whose information densities exceed a pre-defined threshold are deemed information-leaking features. Once these features are identified, we sequentially pass them through a targeted obfuscation mechanism with a provable leakage guarantee in terms of $\mathsf{E}_\gamma$-divergence. The core of this mechanism relies on a data-driven estimate of the trimmed information density for which we propose a novel estimator, named the \textit{trimmed information density estimator} (TIDE). We then use TIDE to implement our mechanism on three real-world datasets. Our approach can be used as a data-driven pipeline for designing obfuscation mechanisms targeting specific features.

This paper considers fair probabilistic classification where the outputs of primary interest are predicted probabilities, commonly referred to as scores. We formulate the problem of transforming scores to satisfy fairness constraints while minimizing the loss in utility. The formulation can be applied either to post-process classifier outputs or to pre-process training data, thus allowing maximum freedom in selecting a classification algorithm. We derive a closed-form expression for the optimal transformed scores and a convex optimization problem for the transformation parameters. In the population limit, the transformed score function is the fairness-constrained minimizer of cross-entropy with respect to the optimal unconstrained scores. In the finite sample setting, we propose to approach this solution using a combination of standard probabilistic classifiers and ADMM. Comprehensive experiments comparing to 10 existing methods show that the proposed FairScoreTransformer has advantages for score-based metrics such as Brier score and AUC while remaining competitive for binary label-based metrics such as accuracy.

We propose a practical framework to address the problem of privacy-aware image sharing in large-scale setups. We argue that, while compactness is always desired at scale, this need is more severe when trying to furthermore protect the privacy-sensitive content. We therefore encode images, such that, from one hand, representations are stored in the public domain without paying the huge cost of privacy protection, but ambiguated and hence leaking no discernible content from the images, unless a combinatorially-expensive guessing mechanism is available for the attacker. From the other hand, authorized users are provided with very compact keys that can easily be kept secure. This can be used to disambiguate and reconstruct faithfully the corresponding access-granted images. We achieve this with a convolutional autoencoder of our design, where feature maps are passed independently through sparsifying transformations, providing multiple compact codes, each responsible for reconstructing different attributes of the image. The framework is tested on a large-scale database of images with public implementation available.

Wireless communications are affected by several aspects of the multipath fading channel, including clustering, nonlinearity, correlation, scattered waves, and specular components. These aspects have been incorporated into many existing probabilistic fading models. The more aspects are covered, the more complicated is the resulting model. In many cases, the model or the associated system performance or both cannot be obtained in a closed form. As a result, little insight is gained into how each aspect of fading ultimately impacts key metrics such as symbol error rate and outage probability. In this work, we provide a novel asymptotic analysis at high signal-to-noise ratio that yields simple, general, and unified closed-form expressions for the diversity and coding gains of the symbol error rate and outage probability. We cover generalized fading scenarios and all the referred fading aspects. Our results give a handy, yet thorough, characterization of the system performance as impacted by multiple physical aspects of the multipath fading phenomenon. We provide further insights to reveal that all the addressed fading aspects affect the coding gain, whereas only the clustering and nonlinearity affect the diversity gain.

Prediction problems often admit competing models that perform almost equally well. This effect challenges key assumptions in machine learning when competing models assign conflicting predictions. In this paper, we define predictive multiplicity as the ability of a prediction problem to admit competing models with conflicting predictions. We introduce measures to evaluate the severity of predictive multiplicity, and develop integer programming tools to compute these measures exactly for linear classification problems. We apply our tools to measure predictive multiplicity in recidivism prediction problems. Our results show that real-world datasets may admit competing models that assign wildly conflicting predictions, and motivate the need to report predictive multiplicity in model development.

We study the problem of finding the element within a convex set of conditional distributions with the smallest f-divergence to a reference distribution. Motivated by applications in machine learning, we refer to this problem as model projection since any probabilistic classification model can be viewed as a conditional distribution. We provide conditions under which the existence and uniqueness of the optimal model can be guaranteed and establish strong duality results. Strong duality, in turn, allows the model projection problem to be reduced to a tractable finite-dimensional optimization. Our application of interest is fair machine learning: the model projection formulation can be directly used to design fair models according to different group fairness metrics. Moreover, this information-theoretic formulation generalizes existing approaches within the fair machine learning literature. We give explicit formulas for the optimal fair model and a systematic procedure for computing it.

We investigate the framework of privacy amplification by iteration, recently proposed by Feldman et al., from an information-theoretic lens. We demonstrate that differential privacy guarantees of iterative mappings can be determined by a direct application of contraction coefficients derived from strong data processing inequalities for f-divergences. In particular, by generalizing the Dobrushin's contraction coefficient for total variation distance to an f-divergence known as Eγ-divergence, we derive tighter bounds on the differential privacy parameters of the projected noisy stochastic gradient descent algorithm with hidden intermediate updates.

We derive the optimal differential privacy (DP) parameters of a mechanism that satisfies a given level of Renyí differential privacy (RDP). Our result is based on the joint range of two f-divergences that underlie the approximate and the Renyi variations of differential privacy. We apply our result tó the moments accountant framework for characterizing privacy guarantees of stochastic gradient descent. When compared to the state-of-the-art, our bounds may lead to about 100 more stochastic gradient descent iterations for training deep learning models for the same privacy budget.

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/√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.

Correspondence analysis (CA) is a multivariate statistical tool used to visualize and interpret data dependencies. CA has found applications in fields ranging from epidemiology to social sciences. However, current methods used to perform CA do not scale to large, high-dimensional datasets. By re-interpreting the objective in CA using an information-theoretic tool called the principal inertia components, we demonstrate that performing CA is equivalent to solving a functional optimization problem over the space of finite variance functions of two random variable. We show that this optimization problem, in turn, can be efficiently approximated by neural networks. The resulting formulation, called the correspondence analysis neural network (CA-NN), enables CA to be performed at an unprecedented scale. We validate the CA-NN on synthetic data, and demonstrate how it can be used to perform CA on a variety of datasets, including food recipes, wine compositions, and images. Our results outperform traditional methods used in CA, indicating that CA-NN can serve as a new, scalable tool for interpretability and visualization of complex dependencies between random variables.

When the performance of a machine learning model varies over groups defined by sensitive attributes (e.g., gender or ethnicity), the performance disparity can be expressed in terms of the probability distributions of the input and output variables over each group. In this paper, we exploit this fact to reduce the disparate impact of a fixed classification model over a population of interest. Given a black-box classifier, we aim to eliminate the performance gap by perturbing the distribution of input variables for the disadvantaged group. We refer to the perturbed distribution as a counterfactual distribution, and characterize its properties for common fairness criteria. We introduce a descent algorithm to learn a counterfactual distribution from data. We then discuss how the estimated distribution can be used to build a data preprocessor that can reduce disparate impact without training a new model. We validate our approach through experiments on real-world datasets, showing that it can repair different forms of disparity without a significant drop in accuracy.

We introduce a mutual information estimator based on the connection between estimation theory and information theory. By combining a polynomial approximation of the minimum mean-squared error estimator with the I-MMSE relationship, we derive a new formula for the mutual information I(X; Y) that is a function of only the marginal distribution of X, the moments of Y, and the conditional moments of Y given X. Estimating the moments in this new formula by sample moments provides an estimator of mutual information that captures desirable properties, such as being invariant under affine transformations.

Given a dataset comprised of individual-level data, we consider the problem of identifying samples that may be disclosed without incurring a privacy risk. We address this challenge by designing a mapping that assigns a "privacy-risk score" to each sample. This mapping, called the privacy watchdog, is based on a sample-wise information leakage measure called the information density, deemed here lift privacy. We show that lift privacy is closely related to well-known information-theoretic privacy metrics. Moreover, we demonstrate how the privacy watchdog can be implemented using the Donsker-Varadhan representation of KL-divergence. Finally, we illustrate this approach on a real-world dataset.

Maximal α-leakage is a tunable measure of information leakage based on the accuracy of guessing an arbitrary function of private data based on public data. The parameter α determines the loss function used to measure the accuracy of a belief, ranging from log-loss at α = 1 to the probability of error at α = ∞. To study the effect of side information on this measure, we introduce and define conditional maximal α-leakage. We show that, for a chosen mapping (channel) from the actual (viewed as private) data to the released (public) data and some side information, the conditional maximal α-leakage is the supremum (over all side information) of the conditional Arimoto channel capacity where the conditioning is on the side information. We prove that if the side information is conditionally independent of the public data given the private data, the side information cannot increase the information leakage.

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.

We introduce a tunable measure for information leakage calledmaximal$\alpha $-leakage. This measure quantifies the maximal gain of an adversary in inferring any (potentially random) function of a dataset from a release of the data. The inferential capability of the adversary is, in turn, quantified by a class of adversarial loss functions that we introduce as$\alpha $-loss,$\alpha \in [1,\infty) \cup \{\infty \}$. The choice of$\alpha $determines the specific adversarial action and ranges from refining a belief (about any function of the data) for$\alpha =1$to guessing the most likely value for$\alpha = \infty $while refining the$\alpha ^{\text {th}}$moment of the belief for$\alpha $in between. Maximal$\alpha $-leakage then quantifies the adversarial gain under$\alpha $-loss over all possible functions of the data. In particular, for the extremal values of$\alpha =1$and$\alpha =\infty $, maximal$\alpha $-leakage simplifies to mutual information and maximal leakage, respectively. For$\alpha \in (1,\infty)$this measure is shown to be the Arimoto channel capacity of order$\alpha $. We show that maximal$\alpha $-leakage satisfies data processing inequalities and a sub-additivity property thereby allowing for a weak composition result. Building upon these properties, we use maximal$\alpha $-leakage as the privacy measure and study the problem of data publishing with privacy guarantees, wherein the utility of the released data is ensured via ahard distortionconstraint. Unlike average distortion, hard distortion provides a deterministic guarantee of fidelity. We show that under a hard distortion constraint, for$\alpha >1$the optimal mechanism is independent of$\alpha $, and therefore, the resulting optimal tradeoff is the same for all values of$\alpha >1$. Finally, the tunability of maximal$\alpha $-leakage as a privacy measure is also illustrated for binary data with average Hamming distortion as the utility measure.

We study the central problem in data privacy: how to share data with an analyst while providing both privacy and utility guarantees to the user that owns the data. In this setting, we present an estimation-theoretic analysis of the privacy-utility trade-off (PUT). Here, an analyst is allowed to reconstruct (in a mean-squared error sense) certain functions of the data (utility), while other private functions should not be reconstructed with distortion below a certain threshold (privacy). We demonstrate how chi-square information captures the fundamental PUT in this case and provide bounds for the best PUT. We propose a convex program to compute privacy-assuring mappings when the functions to be disclosed and hidden are known a priori and the data distribution is known. We derive lower bounds on the minimum mean-squared error of estimating a target function from the disclosed data and evaluate the robustness of our approach when an empirical distribution is used to compute the privacy-assuring mappings instead of the true data distribution. We illustrate the proposed approach through two numerical experiments.

Given a pair of random variables (X, Y) ~ PXYand two convex functions f1and f2, we introduce two bottleneck functionals as the lower and upper boundaries of the two-dimensional convex set that consists of the pairs (If1(W;X), If2(W;Y)), where If denotes f-information and W varies over the set of all discrete random variables satisfying the Markov condition W → X → Y. Applying Witsenhausen and Wyner's approach, we provide an algorithm for computing boundaries of this set for f1, f2, and discrete PXY. In the binary symmetric case, we fully characterize the set when (i) f1(t)=f2(t)=tlogt, (ii) f1(t)=-f2(t)=t2- 1, and (iii) f1and f2are both lβnorm function for β ≥ 2. We then argue that upper and lower boundaries in (i) correspond to Mrs. Gerber's Lemma and its inverse (which we call Mr. Gerber's Lemma), in (ii) correspond to estimation-theoretic variants of Information Bottleneck and Privacy Funnel, and in (iii) correspond to Arimoto Information Bottleneck and Privacy Funnel.

A tunable measure for information leakage called maximal a-leakage is introduced. This measure quantifies the maximal gain of an adversary in refining a tilted version of its prior belief of any (potentially random) function of a dataset conditioning on a disclosed dataset. The choice of α determines the specific adversarial action ranging from refining a belief for α = 1 to guessing the best posterior for α = ∞, and for these extremal values this measure simplifies to mutual information (MI) and maximal leakage (MaxL), respectively. For all other α this measure is shown to be the Arimoto channel capacity. Several properties of this measure are proven including: (i) quasi-convexity in the mapping between the original and disclosed datasets; (ii) data processing inequalities; and (iii) a composition property. A full version of this paper is in [1].

Consider a data publishing setting for a data set with public and private features. The objective of the publisher is to maximize the amount of information about the public features in a revealed data set, while keeping the information leaked about the private features bounded. The goal of this paper is to analyze the performance of privacy mechanisms that are constructed to match the distribution learned from the data set. Two distinct scenarios are considered: (i) mechanisms are designed to provide a privacy guarantee for the learned distribution; and (ii) mechanisms are designed to provide a privacy guarantee for every distribution in a given neighborhood of the learned distribution. For the first scenario, given any privacy mechanism, upper bounds on the difference between the privacy-utility guarantees for the learned and true distributions are presented. In the second scenario, upper bounds on the reduction in utility incurred by providing a uniform privacy guarantee are developed.

In the context of machine learning, disparate impact refers to a form of systematic discrimination whereby the output distribution of a model depends on the value of a sensitive attribute (e.g., race or gender). In this paper, we propose an information-theoretic framework to analyze the disparate impact of a binary classification model. We view the model as a fixed channel, and quantify disparate impact as the divergence in output distributions over two groups. Our aim is to find a correction function that can perturb the input distributions of each group to align their output distributions. We present an optimization problem that can be solved to obtain a correction function that will make the output distributions statistically indistinguishable. We derive closed-form expressions to efficiently compute the correction function, and demonstrate the benefits of our framework on a recidivism prediction problem based on the ProPublica COMPAS dataset.

We study the problem of data disclosure with privacy guarantees, wherein the utility of the disclosed data is ensured via a hard distortion constraint. Unlike average distortion, hard distortion provides a deterministic guarantee of fidelity. For the privacy measure, we use a tunable information leakage measure, namely maximal α-leakage (α ∈ [1, ∞]), and formulate the privacy-utility tradeoff problem. The resulting solution highlights that under a hard distortion constraint, the nature of the solution remains unchanged for both local and nonlocal privacy requirements. More precisely, we show that both the optimal mechanism and the optimal tradeoff are invariant for any α > 1; i.e., the tunable leakage measure only behaves as either of the two extrema, i.e., mutual information for α = 1 and maximal leakage for α = ∞.

Hypothesis testing is a statistical inference framework for determining the true distribution among a set of possible distributions for a given data set. Privacy restrictions may require the curator of the data or the respondents themselves to share data with the test only after applying a randomizing privacy mechanism. This work considers mutual information (MI) as the privacy metric for measuring leakage. In addition, motivated by the Chernoff-Stein lemma, the relative entropy between pairs of distributions of the output (generated by the privacy mechanism) is chosen as the utility metric. For these metrics, the goal is to find the optimal privacy-utility tradeoff (PUT) and the corresponding optimal privacy mechanism for both binary and m-ary hypothesis testing. Focusing on the high privacy regime, Euclidean information-theoretic approximations of the binary and m-ary PUT problems are developed. The solutions for the approximation problems clarify that an MI-based privacy metric preserves the privacy of the source symbols in inverse proportion to their likelihoods.

This paper quantifies the intuitive observation that adding noise reduces available information by means of nonlinear strong data processing inequalities. Consider the random variables W → X → Y forming a Markov chain, where Y = X+Z with X and Z real valued, independent and X bounded in Li-norm. It is shown that I(W; Y) ≤ FI(I(W; X)) with FI(t)0, if and only if Z has a density whose support is not disjoint from any translate of itself. A related question is to characterize for what couplings (W, X) the mutual information I(W; Y) is close to maximum possible. To that end we show that in order to saturate the channel, i.e., for I(W; Y) to approach capacity, it is mandatory that I(W; X) → ∞ (under suitable conditions on the channel). A key ingredient for this result is a deconvolution lemma which shows that postconvolution total variation distance bounds the preconvolution Kolmogorov- Smirnov distance. Explicit bounds are provided for the special case of the additive Gaussian noise channel with quadratic cost constraint. These bounds are shown to be order optimal. For this case, simplified proofs are provided leveraging Gaussianspecific tools such as the connection between information and estimation (I-MMSE) and Talagrand's information-transportation inequality.

The problem of publishing privacy-guaranteed data for hypothesis testing is studied using the maximal leakage (ML) as a metric for privacy and the type-II error exponent as the utility metric. The optimal mechanism (random mapping) that maximizes utility for a bounded leakage guarantee is determined for the entire leakage range for binary datasets. For non-binary datasets, approximations in the high privacy and high utility regimes are developed. The results show that, for any desired leakage level, maximizing utility forces the ML privacy mechanism to reveal partial to complete knowledge about a subset of the source alphabet. The results developed on maximizing a convex function over a polytope may also of an independent interest.

Non-discrimination is a recognized objective in algorithmic decision making. In this paper, we introduce a novel probabilistic formulation of data pre-processing for reducing discrimination. We propose a convex optimization for learning a data transformation with three goals: controlling discrimination, limiting distortion in individual data samples, and preserving utility. We characterize the impact of limited sample size in accomplishing this objective. Two instances of the proposed optimization are applied to datasets, including one on real-world criminal recidivism. Results show that discrimination can be greatly reduced at a small cost in classification accuracy.

We explore properties and applications of the principal inertia components (PICs) between two discrete random variables X and Y. The PICs lie in the intersection of information and estimation theory, and provide a fine-grained decomposition of the dependence between X and Y. Moreover, the PICs describe which functions of X can or cannot be reliably inferred (in terms of MMSE), given an observation of Y. We demonstrate that the PICs play an important role in information theory, and they can be used to characterize information-theoretic limits of certain estimation problems. In privacy settings, we prove that the PICs are related to the fundamental limits of perfect privacy.

The performance of any multiuser wireless communications system is strongly affected by interference. Consequently, the design of such systems must comply with some outage probability criteria. Although interference occurs in a mutual entangled basis, with wireless devices interfering with each other, outage is commonly considered on an individual per-device basis. This approach, however, is a simplified solution to a more intricate multidimensional and system-wide problem, in which several mutually interfering devices may be experiencing an outage simultaneously. The true outage probability across several devices is given by a set of mutual entangled boundary conditions to be fulfilled. This paper presents useful novel formulations for outage probability in multiuser wireless settings, here named mutual outage probability (MOP), for the interference-limited environment. Several scenarios are envisaged, in which some signals are in outage, whereas others are not and still for some others these conditions are irrelevant, all at the same time. We introduce a general framework for calculating the MOP, and present closed-form formulas for the Rayleigh case. Finally, we illustrate the practical use of these formulations in a call admission control application.

Automatic forecasting of time series data is a challenging problem in many industries. Current forecast models adopted by businesses do not provide adequate means for including data representing external factors that may have a significant impact on the time series, such as weather, national events, local events, social media trends, promotions, etc. This paper introduces a novel neural network attention mechanism that naturally incorporates data from multiple external sources without the feature engineering needed to get other techniques to work. We demonstrate empirically that the proposed model achieves superior performance for predicting the demand of 20 commodities across 107 stores of one of America’s largest retailers when compared to other baseline models, including neural networks, linear models, certain kernel methods, Bayesian regression, and decision trees. Our method ultimately accounts for a 23.9% relative improvement as a result of the incorporation of external data sources, and provides an unprecedented level of descriptive ability for a neural network forecasting model.

We investigate the problem of intentionally disclosing information about a set of measurement points X (useful information), while guaranteeing that little or no information is revealed about a private variable S (private information). Given that S and X are drawn from a finite set with joint distribution pS,X, we prove that a non-trivial amount of useful information can be disclosed while not disclosing any private information if and only if the smallest principal inertia component of the joint distribution of S and X is 0. This fundamental result characterizes when useful information can be privately disclosed for any privacy metric based on statistical dependence. We derive sharp bounds for the tradeoff between disclosure of useful and private information, and provide explicit constructions of privacy-assuring mappings that achieve these bounds.

This work presents strong data processing results for the power-constrained additive Gaussian channel. Explicit bounds on the amount of decrease of mutual information under convolution with Gaussian noise are shown. The analysis leverages the connection between information and estimation (I-MMSE) and the following estimation-theoretic result of independent interest. It is proved that any random variable for which there exists an almost optimal (in terms of the mean-squared error) linear estimator operating on the Gaussian-corrupted measurement must necessarily be almost Gaussian (in terms of the Kolmogorov-Smirnov distance).

We consider the problem of diluting common randomness from correlated observations by separated agents. This problem creates a new framework to study statistical privacy, in which a legitimate party, Alice, has access to a random variable X, whereas an attacker, Bob, has access to a random variable Y dependent on X drawn from a joint distribution pX,Y. Alice's goal is to produce a non-trivial function of her available information that is uncorrelated with (has small correlation with) any function that Bob can produce based on his available information. This problem naturally admits a minimax formulation where Alice plays first and Bob follows her. We define dilution coefficient as the smallest value of correlation achieved by the best strategy available to Alice, and characterize it in terms of the minimum principal inertia components of the joint probability distribution pX,Y. We then explicitly find the optimal function that Alice must choose to achieve this limit. We also establish a connection between differential privacy and dilution coefficient and show that if Y is ε-differentially private from X, then dilution coefficient can be upper bounded in terms of ε. Finally, we extend to the setting where Alice and Bob have access to i.i.d. copies of (Xi, Yi), i = 1, ..., n and show that the dilution coefficient vanishes exponentially with n. In other words, Alice can achieve better privacy as the number of her observations grows.

The guesswork problem was originally motivated by a desire to quantify computational security for single user systems. Leveraging recent results from its analysis, we extend the remit and utility of the framework to the quantification of the computational security of multi-user systems. In particular, assume that V users independently select strings stochastically from a finite, but potentially large, list. An inquisitor who does not know which strings have been selected wishes to identify U of them. The inquisitor knows the selection probabilities of each user and is equipped with a method that enables the testing of each (user, string) pair, one at a time, for whether that string had been selected by that user. Here, we establish that, unless U=V, there is no general strategy that minimizes the distribution of the number of guesses, but in the asymptote as the strings become long we prove the following: by construction, there is an asymptotically optimal class of strategies; the number of guesses required in an asymptotically optimal strategy satisfies a large deviation principle with a rate function, which is not necessarily convex, that can be determined from the rate functions of optimally guessing individual users' strings; if all users' selection statistics are identical, the exponential growth rate of the average guesswork as the string-length increases is determined by the specific Rényi entropy of the string-source with parameter (V-U+1)/(V-U+2), generalizing the known V=U=1 case; and that the Shannon entropy of the source is a lower bound on the average guesswork growth rate for all U and V, thus providing a bound on computational security for multi-user systems. Examples are presented to illustrate these results and their ramifications for systems design.

The principal inertia components of the joint distribution of two random variables X and Y are inherently connected to how an observation of Y is statistically related to a hidden variable X. In this paper, we explore this connection within an information theoretic framework. We show that, under certain symmetry conditions, the principal inertia components play an important role in estimating one-bit functions of X, namely f(X), given an observation of Y. In particular, the principal inertia components bear an interpretation as filter coefficients in the linear transformation of pf(X)|Xinto pf(X)|Y. This interpretation naturally leads to the conjecture that the mutual information between f(X) and Y is maximized when all the principal inertia components have equal value. We also study the role of the principal inertia components in the Markov chain B → X → Y → B̂, where B and B̂ are binary random variables. We illustrate our results for the setting where X and Y are binary strings and Y is the result of sending X through an additive noise binary channel.

Consider the situation where a word is chosen probabilistically from a finite list. If an attacker knows the list and can inquire about each word in turn, then selecting the word via the uniform distribution maximizes the attacker's difficulty, its Guesswork, in identifying the chosen word. It is tempting to use this property in cryptanalysis of computationally secure ciphers by assuming coded words are drawn from a source's typical set and so, for all intents and purposes, uniformly distributed within it. By applying recent results on Guesswork, for i.i.d. sources it is this equipartition ansatz that we investigate here. In particular, we demonstrate that the expected Guesswork for a source conditioned to create words in the typical set grows, with word length, at a lower exponential rate than that of the uniform approximation, suggesting use of the approximation is ill-advised.

Existing mobile devices have the capability to use multiple network technologies simultaneously to help increase performance; but they rarely, if at all, effectively use these technologies in parallel. We first present empirical data to help understand the mobile environment when three heterogeneous networks are available to the mobile device (i.e., a WiFi network, WiMax network, and an Iridium satellite network). We then propose a reliable, multi-path protocol called Multi-Path TCP with Network Coding (MPTCP/NC) that utilizes each of these networks in parallel. An analytical model is developed and a mean-field approximation is derived that gives an estimate of the protocol's achievable throughput. Finally, a comparison between MPTCP and MPTCP/NC is presented using both the empirical data and mean-field approximation. Our results show that network coding can provide users in mobile environments a higher quality of service by enabling the use of multiple network technologies and the capability to overcome packet losses due to lossy, wireless network connections.

We introduce a novel feedback protocol, called SMART, for wireless broadcast networks that use linear network coding. We consider transmission of packets from a single source to many receivers over a single-hop broadcast erasure channel with heterogeneous links. We propose a predictive model to minimize feedback as well as extraneous data transmissions by the source. In addition, we use the method of types to provide a lower bound for the expected total transmission time, and use simulations to show that our protocol operates close to this lower bound. We show that with SMART, counter to conventional wisdom, the average user's QoE improves slightly as the number of users increases. We demonstrate that SMART's algorithmic simplicity enables multicast transmissions that on average take fewer than 2 feedback rounds to complete. We show the favorable scalability of our technique with the number of users, which enables reliable quality of experience. We also show the robustness of this scheme to uncertainty in the number of receiving nodes, and packet erasure probability, as well as to partial loss of the feedback. Furthermore, we show that SMART performs nearly as well as an omniscient transmitter that requires no feedback.

The recently introduced network equivalence results are used to create bit-pipe models that can replace multi-terminal channels within a discrete memoryless network. The goal is to create a set of simple “components” or “blocks” that can be substituted for the channel in such a way that the resulting network is capable of emulating the operation of the original one. We develop general upper and lower bounding models for the multiple access channel and for a class of broadcast channels. These bounds are sharp in the sense that there exists networks where the original channel can achieve the maximum sum rate permissible through the upper or lower bounding models. This approach provides a simple method for analyzing the capacity of large networks, which we illustrate with an example.

This paper presents and investigates a general diversity combining scheme, here named MRCS, in which maximal-ratio combined signals are chosen on a selection combining basis. This combining method has a simple implementation and a tractable analytical formulation that can be directly applied to situations in which site selection exists. A general analysis of the probability distribution (reliability), level crossing rate, and average fade duration at the output of the combiner is provided, along with examples for a Nakagami-m fading environment. The main result of the present work, however, is the derivation of an exact, easy-to-evaluate closed-form expression for the mean signal-to-noise ratio at the output of the combiner. Such an expression is applicable for conditions in which the product of the number of maximal-ratio combining branches and the Nakagami-m parameter is an integer and it generalizes a result presented elsewhere in the literature. The formulations derived here find a direct applicability in the dimensioning of practical wireless networks.

This paper presents a useful, novel formulation for the outage probability in interference-limited communication systems, here namedJointOutageProbability(JOP). Given a set of SIR restrictions for mutually interfering signals, the JOP corresponds to the probability that at least one of the restrictions is not satisfied. A general exact solution for the joint outage probability is derived, along with a necessary and sufficient condition for a non-null JOP. Furthermore, a closed- form expression for the joint outage probability in a non- identically distributed Rayleigh scenario with independent signals is obtained. The results presented here can be directly applied in a wide range of practical scenarios.