We study gradient methods for optimizing $(L_0, L_1)$-smooth functions, a class that generalizes Lipschitz-smooth functions and has gained attention for its relevance in machine learning. We provide new insights into the structure of this function class and develop a principled framework for analyzing optimization methods in this setting. While our convergence rate estimates recover existing results for minimizing the gradient norm in nonconvex problems, our approach significantly improves the best-known complexity bounds for convex objectives. Moreover, we show that the gradient method with Polyak stepsizes and the normalized gradient method achieve nearly the same complexity guarantees as methods that rely on explicit knowledge of $(L_0, L_1)$. Finally, we demonstrate that a carefully designed accelerated gradient method can be applied to $(L_0, L_1)$-smooth functions, further improving all previous results.

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.

We propose a privacy auditing framework using minimum mean-squared error (MMSE) estimation and linear auditing models. Our approach provides theoretical lower bounds on the true MMSE of inferring sensitive features from noisy observations of other correlated features. The bounds are in terms of the empirical MMSE under a restricted hypothesis class and a decomposable error term capturing finite sample and approximation effects. For linear auditing models, we derive order-optimal closed-form bounds for classes of relationships between the private and non-private features, including linear mappings, binary symmetric channels, and class-conditional Gaussian models. Through empirical evaluation, we demonstrate that our linear model-based auditing framework serves as a powerful yet tractable tool for MMSE-based privacy auditing that balances theoretical guarantees with practical efficiency.

We introduce a differentially private (DP) algorithm called reveal-or-obscure (ROO) to generate a single representative sample from a dataset of n observations drawn i.i.d. from an unknown discrete distribution P. Unlike methods that add explicit noise to the estimated empirical distribution, ROO achieves ϵ-differential privacy by randomly choosing whether to "reveal" or "obscure" the empirical distribution. While ROO is structurally identical to the algorithm in a recent work by Cheu and Nayak, we prove a strictly better bound on the sampling complexity than that established by them. To further improve the privacy-utility tradeoff, we propose a novel generalized sampling algorithm called Data-Specific ROO (DS-ROO), where the probability of obscuring the empirical distribution of the dataset is chosen adaptively. We prove that DS-ROO satisfies ϵ-DP, and provide empirical evidence that DS-ROO can achieve better utility under the same privacy budget of vanilla ROO.

Differentially private stochastic gradient descent (DP-SGD) is the most widely used method for training machine learning models with provable privacy guarantees. A key challenge in DP-SGD is setting the per-sample gradient clipping threshold, which significantly affects the trade-off between privacy and utility. While recent adaptive methods improve performance by adjusting this threshold during training, they operate in the standard coordinate system and fail to account for correlations across the coordinates of the gradient. We propose GeoClip, a geometry-aware framework that clips and perturbs gradients in a transformed basis aligned with the geometry of the gradient distribution. GeoClip adaptively estimates this transformation using only previously released noisy gradients, incurring no additional privacy cost. We provide convergence guarantees for GeoClip and derive a closed-form solution for the optimal transformation that minimizes the amount of noise added while keeping the probability of gradient clipping under control. Experiments on both tabular and image datasets demonstrate that GeoClip consistently outperforms existing adaptive clipping methods under the same privacy budget.

Diffusion models have achieved impressive performance in generating high-quality and diverse synthetic data. However, their success typically assumes a class-balanced training distribution. In real-world settings, multi-class data often follow a long-tailed distribution, where standard diffusion models struggle—producing low-diversity and lower-quality samples for underrepresented (tail) classes. While this degradation is well-documented, its underlying cause remains poorly understood. In this work, we investigate the behavior of diffusion models trained on long-tailed datasets and identify a key issue: the latent representations (from the bottleneck layer of the U-Net) for tail class subspaces exhibit significant overlap with those of head classes, leading to feature borrowing and poor generation quality. Importantly, we show that this is not merely due to limited data per class, but that the relative class imbalance significantly contributes to this phenomenon. To address this, we propose **CO**ntrastive **R**egularization for **A**ligning **L**atents (CORAL), a contrastive latent alignment framework that leverages supervised contrastive losses to encourage well-separated latent class representations. Experiments demonstrate that CORAL significantly improves both the diversity and visual quality of samples generated for tail classes relative to state-of-the-art methods.

While machine learning models become more capable in discriminative tasks at scale, their ability to overcome biases introduced by training data has come under increasing scrutiny. Previous results suggest that there are two extremes of parameterization with very different behaviors: the population (underparameterized) setting where loss weighting is optimal and the separable overparameterized setting where loss weighting is ineffective at ensuring equal performance across classes. This work explores the regime of last layer retraining (LLR) in which the unseen limited (retraining) data is frequently inseparable and the model proportionately sized, falling between the two aforementioned extremes. We show, in theory and practice, that loss weighting is still effective in this regime, but that these weights _must_ take into account the relative overparameterization of the model.

Variational Inequality (VI) problems have attracted great interest in the machine learning (ML) community due to their application in adversarial and multi-agent training. Despite its relevance in ML, the oft-used strong-monotonicity and Lipschitz continuity assumptions on VI problems are restrictive and do not hold in many machine learning problems. To address this, we relax smoothness and monotonicity assumptions and study structured non-monotone generalized smoothness. The key idea of our results is in adaptive stepsizes. We prove the first-known convergence results for solving generalized smooth VIs for the three popular methods, namely, projection, Korpelevich, and Popov methods. Our convergence rate results for generalized smooth VIs match or improve existing results on smooth VIs. We present numerical experiments that support our theoretical guarantees and highlight the efficiency of proposed adaptive stepsizes.

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.

Ensuring fair predictions across many distinct sub-populations in the training data can be prohibitive for large models. Recently, simple linear last layer retraining strategies, in combination with data augmentation methods such as upweighting, downsampling and mixup, have been shown to achieve state-of-the-art performance for worst-group accuracy, which quanti-fies accuracy for the least prevalent subpopulation. For linear last layer retraining and the abovementioned augmentations, we present the optimal worst-group accuracy when modeling the distribution of the latent representations (input to the last layer) as Gaussian for each subpopulation. We evaluate and verify our results for both synthetic and large publicly available datasets.

Last-layer retraining methods have emerged as an efficient framework for correcting existing base models. Within this framework, several methods have been proposed to deal with correcting models for subgroup fairness with and without group membership information. Importantly, prior work has demonstrated that many methods are susceptible to noisy labels. To this end, we propose a drop-in correction for label noise in last-layer retraining, and demonstrate that it achieves state-of-the-art worst-group accuracy for a broad range of symmetric label noise and across a wide variety of datasets exhibiting spurious correlations. Our proposed approach uses label spreading on a latent nearest neighbors graph and has minimal computational overhead compared to existing methods.

We introduce a family of information leakage measures calledmaximal(α, β)-leakage(MαbeL), parameterized by real numbers α and β greater than or equal to 1. The measure is formalized via an operational definition involving an adversary guessing an unknown (randomized) function of the data given the released data. We obtain a simplified computable expression for the measure and show that it satisfies several basic properties such as monotonicity in β for a fixed α, non-negativity, data processing inequalities, and additivity over independent releases. We highlight the relevance of this family by showing that it bridges several known leakage measures, including maximal α-leakage (β = 1), maximal leakage (α = ∞, β = 1), local differential privacy (LDP) (α = ∞, β = ∞), and local Rényi differential privacy (LRDP) (α = β), thereby giving an operational interpretation to local Rényi differential privacy. We also study a conditional version of MαbeL on leveraging which we recover differential privacy and Rényi differential privacy. A new variant of LRDP, which we callmaximal Rényi leakage, appears as a special case of MαbeL for α = ∞ that smoothly tunes between maximal leakage (β = 1) and LDP (β = ∞). Finally, we show that a vector form of the maximal Rényi leakage relaxes differential privacy under Gaussian and Laplacian mechanisms.

We introduce a gain function viewpoint of information leakage by proposing maximal$g$-leakage, a rich class of operationally meaningful leakage measures that subsumes recently introduced leakage measures — maximal leakage and maximal$\alpha $-leakage. In maximal$g$-leakage, the gain of an adversary in guessing an unknown random variable is measured using a gain function applied to the probability of correctly guessing. In particular, maximal$g$-leakage captures the multiplicative increase, upon observing$Y$, in the expected gain of an adversary in guessing a randomized function of$X$, maximized over all such randomized functions. We also consider the scenario where an adversary can make multiple attempts to guess the randomized function of interest. We show that maximal leakage is an upper bound on maximal$g$-leakage under multiple guesses, for any non-negative gain function$g$. We obtain a closed-form expression for maximal$g$-leakage under multiple guesses for a class of concave gain functions. We also study maximal$g$-leakage measure for a specific class of gain functions related to the$\alpha $-loss, that interpolates log-loss ($\alpha =1$) and (soft) 0–1 loss ($\alpha =\infty $). In particular, we first completely characterize the minimal expected$\alpha $-loss under multiple guesses and analyze how the corresponding leakage measure is affected with the number of guesses. We show that a new measure of divergence that belongs to the class of Bregman divergences captures the relative performance of an arbitrary adversarial strategy with respect to an optimal strategy in minimizing the expected$\alpha $-loss. Finally, we study two variants of maximal$g$-leakage depending on the type of adversary and obtain closed-form expressions for them, which do not depend on the particular gain function considered as long as it satisfies some mild regularity conditions. We do this by developing a variational characterization for the Rényi divergence of order infinity which naturally generalizes the definition of pointwise maximal leakage to incorporate arbitrary gain functions.

There is a growing need for models that are interpretable and have reduced energy/computational cost (e.g., in health care analytics and federated learning). Examples of algorithms to train such models include logistic regression and boosting. However, one challenge facing these algorithms is that they provably suffer from label noise; this has been attributed to the joint interaction between oft-used convex loss functions and simpler hypothesis classes, resulting in too much emphasis being placed on outliers. In this work, we use the margin-based $\alpha$-loss, which continuously tunes between canonical convex and quasi-convex losses, to robustly train simple models. We show that the $\alpha$ hyperparameter smoothly introduces non-convexity and offers the benefit of “giving up” on noisy training examples. We also provide results on the Long-Servedio dataset for boosting and a COVID-19 survey dataset for logistic regression, highlighting the efficacy of our approach across multiple relevant domains.

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

In an effort to address the training instabilities of GANs, we introduce a class of dual-objective GANs with different value functions (objectives) for the generator (G) and discriminator (D). In particular, we model each objective using α-loss, a tunable classification loss, to obtain (αD, αG)-GANs, parameterized by (αD, αG) ∈ (0, ∞]2. For sufficiently large number of samples and capacities for G and D, we show that the resulting non-zero sum game simplifies to minimizing an f-divergence under appropriate conditions on (αD, αG). In the finite sample and capacity setting, we define estimation error to quantify the gap in the generator’s performance relative to the optimal setting with infinite samples and obtain upper bounds on this error, showing it to be order optimal under certain conditions. Finally, we highlight the value of tuning (αD, αG) in alleviating training instabilities for the synthetic 2D Gaussian mixture ring and the Stacked MNIST datasets.

The electrical power grid is a critical infrastructure, with disruptions in transmission having severe repercussions on daily activities, across multiple sectors. To identify, prevent, and mitigate such events, power grids are being refurbished as 'smart' systems that include the widespread deployment of GPS-enabled phasor measurement units (PMUs). PMUs provide fast, precise, and time-synchronized measurements of voltage and current, enabling real-time wide-area monitoring and control. However, the potential benefits of PMUs, for analyzing grid events like abnormal power oscillations and load fluctuations, are hindered by the fact that these sensors produce large, concurrent volumes of noisy data. In this paper, we describe working with power grid engineers to investigate how this problem can be addressed from a visual analytics perspective. As a result, we have developed PMU Tracker, an event localization tool that supports power grid operators in visually analyzing and identifying power grid events and tracking their propagation through the power grid's network. As a part of the PMU Tracker interface, we develop a novel visualization technique which we term an epicentric cluster dendrogram, which allows operators to analyze the effects of an event as it propagates outwards from a source location. We robustly validate PMU Tracker with: (1) a usage scenario demonstrating how PMU Tracker can be used to analyze anomalous grid events, and (2) case studies with power grid operators using a real-world interconnection dataset. Our results indicate that PMU Tracker effectively supports the analysis of power grid events; we also demonstrate and discuss how PMU Tracker's visual analytics approach can be generalized to other domains composed of time-varying networks with epicentric event characteristics.

Properness for supervised losses stipulates that the loss function shapes the learning algorithm towards the true posterior of the data generating distribution. Unfortunately, data in modern machine learning can be corrupted or twisted in many ways. Hence, optimizing a proper loss function on twisted data could perilously lead the learning algorithm towards the twisted posterior, rather than to the desired clean posterior. Many papers cope with specific twists (e.g., label/feature/adversarial noise), but there is a growing need for a unified and actionable understanding atop properness. Our chief theoretical contribution is a generalization of the properness framework with a notion called twist-properness, which delineates loss functions with the ability to "untwist" the twisted posterior into the clean posterior. Notably, we show that a nontrivial extension of a loss function called alpha-loss, which was first introduced in information theory, is twist-proper. We study the twist-proper alpha-loss under a novel boosting algorithm, called PILBoost, and provide formal and experimental results for this algorithm. Our overarching practical conclusion is that the twist-proper alpha-loss outperforms the proper log-loss on several variants of twisted data.

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].

We present a variational characterization for the Rényi divergence of order infinity. Our characterization is related´ to guessing: the objective functional is a ratio of maximal expected values of a gain function applied to the probability of correctly guessing an unknown random variable. An important aspect of our variational characterization is that it remains agnostic to the particular gain function considered, as long as it satisfies some regularity conditions. Also, we define two variants of a tunable measure of information leakage, the maximal αleakage, and obtain closed-form expressions for these information measures by leveraging our variational characterization.

We prove a two-way correspondence between the min-max optimization of general CPE loss function GANs and the minimization of associated f-divergences. We then focus on α-GAN, defined via the α-loss, which interpolates several GANs (Hellinger, vanilla, Total Variation) and corresponds to the minimization of the Arimoto divergence. We show that the Arimoto divergences induced by α-GAN equivalently converge, for all α∈ℝ>0∪{∞}. However, under restricted learning models and finite samples, we provide estimation bounds which indicate diverse GAN behavior as a function of α. Finally, we present empirical results on a toy dataset that highlight the practical utility of tuning the α hyperparameter.

We introduce a family of information leakage measures called maximal α, β-leakage, parameterized by real numbers α and β. The measure is formalized via an operational definition involving an adversary guessing an unknown function of the data given the released data. We obtain a simple, computable expression for the measure and show that it satisfies several basic properties such as monotonicity in β for a fixed α, non-negativity, data processing inequalities, and additivity over independent releases. Finally, we highlight the relevance of this family by showing that it bridges several known leakage measures, including maximal α-leakage (β = 1), maximal leakage (α = ∞, β = 1), local differential privacy (α = ∞, β = ∞), and local Rényi differential privacy (α = β).

We present a data-driven framework for learning fair universal representations (FUR) that guarantee statistical fairness for any learning task that may not be known a priori. Our framework leverages recent advances in adversarial learning to allow a data holder to learn representations in which a set of sensitive attributes are decoupled from the rest of the dataset. We formulate this as a constrained minimax game between an encoder and an adversary where the constraint ensures a measure of usefulness (utility) of the representation. The resulting problem is that of censoring, i.e., finding a representation that is least informative about the sensitive attributes given a utility constraint. For appropriately chosen adversarial loss functions, our censoring framework precisely clarifies the optimal adversarial strategy against strong information-theoretic adversaries; it also achieves the fairness measure of demographic parity for the resulting constrained representations. We evaluate the performance of our proposed framework on both synthetic and publicly available datasets. For these datasets, we use two tradeoff measures: censoring vs. representation fidelity and fairness vs. utility for downstream tasks, to amply demonstrate that multiple sensitive features can be effectively censored even as the resulting fair representations ensure accuracy for multiple downstream tasks.

We introduce a tunable loss function called$\alpha $-loss, parameterized by$\alpha \in (0,\infty]$, which interpolates between the exponential loss ($\alpha = 1/2$), the log-loss ($\alpha = 1$), and the 0–1 loss ($\alpha = \infty $), for the machine learning setting of classification. Theoretically, we illustrate a fundamental connection between$\alpha $-loss and Arimoto conditional entropy, verify the classification-calibration of$\alpha $-loss in order to demonstrate asymptotic optimality via Rademacher complexity generalization techniques, and build-upon a notion called strictly local quasi-convexity in order to quantitatively characterize the optimization landscape of$\alpha $-loss. Practically, we perform class imbalance, robustness, and classification experiments on benchmark image datasets using convolutional-neural-networks. Our main practical conclusion is that certain tasks may benefit from tuning$\alpha $-loss away from log-loss ($\alpha = 1$), and to this end we provide simple heuristics for the practitioner. In particular, navigating the$\alpha $hyperparameter can readily provide superior model robustness to label flips ($\alpha > 1$) and sensitivity to imbalanced classes ($\alpha < 1$).

The minimum mean-square error (MMSE) achievable by optimal estimation of a random variable$S$given another random variable$T$is of much interest in a variety of statistical contexts. Motivated by a growing interest in auditing machine learning models for unintended information leakage, we propose a neural network-based estimator of this MMSE. We derive a lower bound for the MMSE based on the proposed estimator and the Barron constant associated with the conditional expectation of$S$given$T$. Since the latter is typically unknown in practice, we derive a general bound for the Barron constant that produces order optimal estimates for canonical distribution models.

We consider a problem of guessing, wherein an adversary is interested in knowing the value of the realization of a discrete random variable$X$on observing another correlated random variable Y. The adversary can make multiple (say, k) guesses. The adversary's guessing strategy is assumed to minimize a-loss, a class of tunable loss functions parameterized by a. It has been shown before that this loss function captures well known loss functions including the exponential loss (a = 1/2), the log-loss (a = 1) and the 0–1 loss (a = ∞). We completely characterize the optimal adversarial strategy and the resulting expected α-loss, thereby recovering known results for a = ∞. We define an information leakage measure from the k-guesses setup and derive a condition under which the leakage is unchanged from a single guess.

We introduce a tunable GAN, called $\alpha$-GAN, parameterized by $\alpha\in$(0, $\infty$], which interpolates between various f-GANs and Integral Probability Metric based GANs (under constrained discriminator set). We construct $\alpha-$ GAN using a supervised loss function, namely, $\alpha-$ loss, which is a tunable loss function capturing several canonical losses. We show that $\alpha-$ GAN is intimately related to the Arimoto divergence, which was first proposed by Österriecher (1996), and later studied by Liese and Vajda (2006). We posit that the holistic understanding that $\alpha-$ GAN introduces will have practical benefits of addressing both the issues of vanishing gradients and mode collapses.

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.

We analyze the optimization landscape of a recently introduced tunable class of loss functions called α-loss, α ∈ (0, ∞], in the logistic model. This family encapsulates the exponential loss (α = 1/2), the log-loss (α = 1), and the 0-1 loss (α = ∞) and contains compelling properties that enable the practitioner to discern among a host of operating conditions relevant to emerging learning methods. Specifically, we study the evolution of the optimization landscape of α-loss with respect to α using tools drawn from the study of strictly-locally-quasi-convex functions in addition to geometric techniques. We interpret these results in terms of optimization complexity via normalized gradient descent.

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.

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 present α-loss, α ∈ [1, ∞], a tunable loss function for binary classification that bridges log-loss (α = 1) and 0-1 loss (α = ∞). We prove that α-loss has an equivalent margin-based form and is classification-calibrated, two desirable properties for a good surrogate loss function for the ideal yet intractable 0-1 loss. For logistic regression-based classification, we provide an upper bound on the difference between the empirical and expected risk for α-loss at the critical points of the empirical risk by exploiting its Lipschitzianity along with recent results on the landscape features of empirical risk functions. Finally, we show that α-loss with α = 2 performs better than log-loss on MNIST for logistic regression.

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.

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.

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 α = ∞.

A privacy-utility tradeoff is developed for an arbitrary set of finite-alphabet source distributions. Privacy is quantified using differential privacy (DP), and utility is quantified using expected Hamming distortion maximized over the set of distributions. The family of source distribution sets (source sets) is categorized into three classes, based on different levels of prior knowledge they capture. For source sets whose convex hull includes the uniform distribution, symmetric DP mechanisms are optimal. For source sets whose probability values have a fixed monotonic ordering, asymmetric DP mechanisms are optimal. For all other source sets, general upper and lower bounds on the optimal privacy leakage are developed and necessary and sufficient conditions for tightness are established. Differentially private leakage is an upper bound on mutual information leakage: the two criteria are compared analytically and numerically to illustrate the effect of adopting a stronger privacy criterion.

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.

The privacy-utility tradeoff problem is formulated as determining the privacy mechanism (random mapping) that minimizes the mutual information (a metric for privacy leakage) between the private features of the original dataset and a released version. The minimization is subject to a constraint on the average distortion cost defined as a function f evaluated for every distortion d between the public features and the released version of dataset. The asymptotic optimal leakage is derived both for general and stationary memoryless privacy mechanisms. It is shown that for convex cost functions there is no asymptotic loss in using stationary memoryless mechanisms. Of independent interest are the proof techniques developed here for arbitrary cost functions.

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.

This paper introduces a multi-round interaction problem with privacy constraints between two agents that observe correlated data. The data are assumed to have both public and private features, and the goal of the interaction is to share the public data subject to utility constraints (bounds on the distortion of public feature) while ensuring bounds on the information leakage of the private data at the other agent. The agents alternately share data with one another for a total of K rounds such that each agent initiates sharing over K/2 rounds. The interactions are modeled as a collection of K random mechanisms (mappings), one for each round. The goal is to jointly design the K private mechanisms to determine the set of all achievable distortion-leakage pairs at each agent. Arguing that a mutual information-based leakage metric can be appropriate for streaming data settings, this paper: 1) determines the set of all achievable distortion-leakage tuples; 2) shows that the K mechanisms allow for precisely composing the total privacy budget over K rounds without loss; and 3) develops conditions under which interaction reduces the net leakage at both agents and illustrates it for a specific class of sources. The paper then focuses on log-loss distortion to better understand the effect on leakage of using a commonly used utility metric in learning theory. The resulting interaction problem leads to a non-convex sum-leakage-distortion optimization problem that can be viewed as an interactive version of the information bottleneck problem. A new merge-and-search algorithm that extends the classical agglomerative information bottleneck algorithm to the interactive setting is introduced to determine a provable locally optimal solution. Finally, the benefit of interaction under log-loss is illustrated for specific source classes, and the optimality of one-shot is proved for Gaussian sources under both mean-square and log-loss distortions constraints.

Universal fixed-to-variable lossless source coding for memoryless sources is studied in the finite blocklength and higher order asymptotic regimes. Optimal three-term fixed-error asymptotic expressions are derived for general fixed-to-variable codes and for prefix codes. It is shown that the non-prefix Type Size code, in which codeword lengths are chosen in ascending order of type class size, achieves the optimal third-order term, and outperforms classical two-stage codes. Converse results are proved making use of a result on the distribution of the empirical entropy and Laplace's approximation. Finally, the fixed-to-variable coding problem without a prefix constraint is shown to be essentially the same as the universal guessing problem.

We examine a tradeoff between privacy and utility in terms of local differential privacy (L-DP) and Hamming distortion for certain classes of finite-alphabet sources under Hamming distortion. We define two classes: permutation-invariant, and ordered statistics (whose probability mass functions are monotonic). We obtain the optimal L-DP mechanism for permutation-invariant sources and derive upper and lower bounds on the achievable local differential privacy for ordered statistics for a range of target distortion values.

Converse and achievable results on the third-order coding rate for universal fixed-to-variable source coding are presented. The authors previously introduced a new universal non-prefix Type Size code for memoryless sources in which codewords lengths are chosen in ascending order of type class sizes. This paper presents a converse on the third-order coding rate for general class of fixed-to-variable codes and proves the optimality of Type Size codes for memoryless sources. The third-order coding rate for a two-stage code is also developed and is shown to be strictly larger than achieved by the Type Size code.

A universal source coding problem is considered in the finite blocklength regime for stationary memoryless sources. A new coding scheme is presented that encodes based on the type class size and the empirical support set of the sequence. It is shown that there is no loss in dispersion relative to the case when the source distribution is known. A new bound is obtained on the third order asymptotic coding rate. Numerical results are presented for finite blocklengths comparing the proposed coding scheme with a variety of coding schemes including Lempel-Ziv.

Ensuring the usefulness of electronic data sources while providing necessary privacy guarantees is an important unsolved problem. This problem drives the need for an analytical framework that can quantify the privacy of personally identifiable information while still providing a quantifiable benefit (utility) to multiple legitimate information consumers. This paper presents an information-theoretic framework that promises an analytical model guaranteeing tight bounds of how much utility is possible for a given level of privacy and vice-versa. Specific contributions include: 1) stochastic data models for both categorical and numerical data; 2) utility-privacy tradeoff regions and the encoding (sanization) schemes achieving them for both classes and their practical relevance; and 3) modeling of prior knowledge at the user and/or data source and optimal encoding schemes for both cases.

A lossy source coding problem is studied in which a source encoder communicates with two decoders, one with and one without correlated side information with an additional constraint on the privacy of the side information at the uninformed decoder. Two cases of this problem arise depending on the availability of the side information at the encoder. The set of all feasible rate-distortion-equivocation tuples is characterized for each case. The difference between the informed and uninformed cases and the advantages of encoder side information for enhancing privacy are highlighted for a binary symmetric source with erasure side information and Hamming distortion.

The popular social networking and microblogging service Twitter contains language that is very different from what is considered proper. This paper quantifies those linguistic differences between printed English and Tweetspeak using information-theoretic concepts. Letter-based n-gram entropies are calculated and compared to analagous data from two corpora of printed English to demonstrate that 1) Twitter's entropy is overall higher than that of printed English, and 2) individual users' entropies are on average higher the less conventional their language use is. The implications for digitally-mediated communication in general are also discussed.

A problem of distributed state estimation at multiple agents that are physically connected and have competitive interests is mapped to a distributed source coding problem with additional privacy constraints. The agents interact to estimate their own states to a desired fidelity from their (sensor) measurements which are functions of both the local state and the states at the other agents. For a Gaussian state and measurement model, it is shown that the sum-rate achieved by a distributed protocol in which the agents broadcast to one another is a lower bound on that of a centralized protocol in which the agents broadcast as if to a virtual CEO converging only in the limit of a large number of agents. The sufficiency of encoding using local measurements is also proved for both protocols.

The Heegard-Berger problem models a case in which encoding at a source has to account for two decoders, one with and one without correlated side information when the same information is not available at the encoder. The Heegard-Berger encoding scheme is proved to be rate-optimal even when an additional constraint on the privacy of side information is imposed at the uninformed decoder. The results are illustrated for a binary source with erasure side information and Hamming distortion, a result which is also of independent interest.

The problem of preserving privacy when a multi-variate source is required to be revealed partially to multiple users is modeled as a Gray-Wyner source coding problem with K correlated sources at the encoder and K decoders in which the kthdecoder, k = 1, 2, ..., K, losslessly reconstructs the kthsource via a common link of rate R0and a private link of rate Rk. The privacy requirement of keeping each decoder oblivious of all sources other than the one intended for it is introduced via an equivocation constraint Ekat decoder k such that the total equivocation summed over all decoders E ≥ Δ. The set of achievable ({Rk}Kk=1,R0,Δ) rates-equivocation (K + 2)-tuples is completely characterized. Using this characterization, two different definitions of common information are presented and are shown to be equivalent.

The problem of optimal resource allocation is studied for ergodic fading orthogonal multi-access relay channels (MARCs) in which the users (sources) communicate with a destination with the aid of a half-duplex relay that transmits and receives on orthogonal channels. Under the assumption that the instantaneous fading state information is available at all nodes, the maximum sum-rate and the optimal user and relay power allocations (policies) are developed for a decode-and-forward (DF) relay. A known lemma on the sum-rate of two intersecting polymatroids is used to determine the DF sum-rate and the optimal user and relay policies, and to classify fading MARCs into one of three types: (i) partially clustered MARCs in which a user is clustered either with the relay or with the destination, (ii) clustered MARCs in which all users are either proximal to the relay or to the destination, and (iii) arbitrarily clustered MARCs which are a combination of the first two types. Cutset outer bounds are used to show that DF achieves the capacity region for a sub-class of clustered orthogonal MARCs.

The sum-capacity for specific sub-classes of ergodic fading Gaussian two-user interference channels (IFCs) is developed under the assumption of perfect channel state information at all transmitters and receivers. For the sub-classes of uniformly strong (every fading state is strong) and ergodic very strong two-sided IFCs (a mix of strong and weak fading states satisfying specific fading averaged conditions) the optimality of completely decoding the interference, i.e., converting the IFC to a compound multiple access channel (C-MAC), is proved. It is also shown that this capacity-achieving scheme requires encoding and decoding jointly across all fading states. As an achievable scheme and also as a topic of independent interest, the capacity region and the corresponding optimal power policies for an ergodic fading C-MAC are developed. For the sub-class of uniformly weak IFCs (every fading state is weak), genie-aided outer bounds are developed. The bounds are shown to be achieved by treating interference as noise and by separable coding for one-sided fading IFCs. Finally, for the sub-class of one-sided hybrid IFCs (a mix of weak and strong states that do not satisfy ergodic very strong conditions), an achievable scheme involving rate splitting and joint coding across all fading states is developed and is shown to perform at least as well as a separable coding scheme.

The problem of frequent private information “leakage” from the myriad large centralized searchable data repositories in use today drives the need for an analytical framework that quantifies unequivocally how safe private data can be (privacy) while still providing measurable benefit (utility) to multiple legitimate information consumers. Rate distortion theory is shown to be a natural choice to develop such a framework which includes modeling of data sources, developing application independent utility and privacy metrics, quantifying utility-privacy tradeoffs irrespective of the type of data sources or the methods of providing privacy, and developing a side-information model for dealing with questions of external knowledge.

The secrecy capacity of relay channels with orthogonal components is studied in the presence of additional passive eavesdropper nodes. The relay and destination receive signals from the source on two orthogonal channels such that the destination also receives transmissions from the relay on its channel. The eavesdropper(s) can overhear either one or both of the orthogonal channels. For a single eavesdropper node, the secrecy capacity is shown to be achieved by apartial decode-and-forward(PDF) scheme when the eavesdropper can overhear only one of the two orthogonal channels. For the case of two eavesdropper nodes, secrecy capacity is shown to be achieved by PDF for a sub-class of channels.

The sum-capacity is studied for a$K$-user physically degraded Gaussian multiple-access relay channel (MARC). Decode-and-forward (DF) is shown to achieve the sum-capacity and capacity region for a subclass of degraded Gaussian MARCs in which the multiple-access link from the sources to the relay is the bottleneck link. For the remaining subclass, DF is shown to achieve the$K$-user sum-capacity when the sources are symmetric, i.e., they transmit with the same transmit power. The optimality of DF is conjectured for the case of asymmetric sources.

The problem of resource allocation is studied for two-sender two-receiver fading Gaussian interference channels (IPCs) and compound multiaccess channels (C-MACs). The senders in an IFC communicate with their own receiver (unicast) while those in a C-MAC communicate with both receivers (multicast). The instantaneous fading state between every transmit- receive pair in this network is assumed to be known at all transmitters and receivers. Under an average power constraint at each source, the sum-capacity of the C-MAC and the power policy that achieves this capacity is developed. The conditions defining the classes of strong and very strong ergodic IPCs are presented and the multicast sum-capacity is shown to be tight for both classes.

Cooperation between rational users in wireless networks is studied using coalitional game theory. Using the rate achieved by a user as its utility, it is shown that the stable coalition structure, i.e., set of coalitions from which users have no incentives to defect, depends on the manner in which the rate gains are apportioned among the cooperating users. Specifically, the stability of the grand coalition (GC), i.e., the coalition of all users, is studied. Transmitter and receiver cooperation in an interference channel (IC) are studied as illustrative cooperative models to determine the stable coalitions for both flexible (transferable) and fixed (non-transferable) apportioning schemes. It is shown that the stable sum-rate optimal coalition when only receivers cooperate by jointly decoding (transferable) is the GC. The stability of the GC depends on the detector when receivers cooperate using linear multiuser detectors (non-transferable). Transmitter cooperation is studied assuming that all receivers cooperate perfectly and that users outside a coalition act as jammers. The stability of the GC is studied for both the case of perfectly cooperating transmitters (transferrable) and under a partial decode-and-forward strategy (non-transferable). In both cases, the stability is shown to depend on the channel gains and the transmitter jamming strengths.

The problem of resource allocation is studied for a two-user fading orthogonal multiaccess relay channel (MARC) where both users (sources) communicate with a destination in the presence of a relay. A half-duplex relay is considered that transmits on a channel orthogonal to that used by the sources. The instantaneous fading state between every transmit-receive pair in this network is assumed to be known at both the transmitter and receiver. Under an average power constraint at each source and the relay, the sum-rate for the achievable strategy of decode-and-forward (DF) is maximized over all power allocations (policies) at the sources and relay. It is shown that the sum-rate maximizing policy exploits the multiuser fading diversity to reveal the optimality of opportunistic channel use by each user. A geometric interpretation of the optimal power policy is also presented.

An offset encoding technique is presented that improves sliding-window decoding with decode-and-forward for K-user multiple-access relay channels. The technique offsets user transmissions by one block per user and achieves the corner points of the destination's backward decoding rate regions but with a smaller delay. As a result, one achieves boundary points of the best known decode-and-forward rate regions with a smaller delay than with backward decoding.

The formation of coalitions in a Gaussian interference channel where the receivers are allowed to cooperate is studied under the framework of coalitional game theory. Allowing any arbitrary sharing of the total rate achieved by a coalition between its member links, it is shown that the grand coalition (coalition of all links) maximizes spectrum utilization and is also stable, that is, the links in this coalition have no incentives to leave and form other coalitions. The issue of fairness in allocating rates to members of a grand coalition is addressed via a Nash bargaining solution where each link utility is modeled as the rate gained by being in a coalition relative to the rate achieved in the interference channel. Further, a rate allocation solution using proportional fairness is also presented and the results are illustrated with examples

The performance of source-cooperation in a multi-access network is compared to that of using a wireless relay. The former network is modeled as a multi-access channel with generalized feedback and the latter as a multi-access relay channel. Using power as the cost metric, achievable rates and outage probabilities for the two networks are compared under a total transmit power constraint and a specified geometry. The use of a relay is shown to be advantageous for a variety of wireless fading channels

A three-tier hierarchical wireless sensor network is considered that consists of a cluster of sensors, an intermediate relay with better computing and communication capabilities than the sensors, and a central server or access point. Such a network can be modeled as a multiple-access relay channel (MARC) with additive white Gaussian noise and fading. Capacity bounds for this network are presented with and without constraints on simultaneous reception and transmission by the relay. The results identify cooperative strategies between the relay and sensors for increasing network capacity. These strategies also preserve limited battery resources by eliminating the need for cooperation between sensors.