A private information retrieval protocol (PIR) scheme under an arbitrary collusion pattern $\mathcal{P}$ enables a client to retrieve one message from a library of $K$ equal-sized messages duplicated in $N$ servers, while keeping the index of the desired message private from any colluding set in $\mathcal{P}$. Although achieving high rates typically requires sufficiently large message sizes, smaller message sizes also desirable due to reduced implementation complexity and fewer constraints. By characterizing the capacity-achieving schemes, Tian, Sun, and Chen (2019) showed that the optimal message size for uniformly decomposable PIR schemes under no-collusion setting is $N-1$. However, comparable results are not yet available for more general collusion settings. In this work, we present a complete characterization of the properties of capacity-achieving decomposable PIR schemes under arbitrary collusion patterns. Building on this characterization, we derive a general lower bound on the optimal message size for capacity-achieving uniformly decomposable PIR schemes under an arbitrary collusion pattern $\mathcal{P}$, expressed in terms of the hitting number of a newly defined family of subsets of servers determined by the collusion pattern $\mathcal{P}$. Finally, we specialize the lower bound to several important classes of collusion patterns, including $T$-collusion, disjoint collections of colluding sets, cyclically $T$-contiguous collusion, and disjoint collections of cyclically contiguous colluding sets. For the last two collusion patterns, we present matching achievable schemes that attain the corresponding bounds, thereby providing a complete characterization of the optimal message size.

In information-theoretic private information retrieval (PIR), a client wants to retrieve one desired file out of$M$files, stored across$N$servers, while keeping the index of the desired file private from each$T$-sized subset of servers. A PIR protocol must ideally maximize the rate, which is the ratio of the file size to the total quantum of the download from the servers, while ensuring such privacy. In Weak-PIR (WPIR), the criterion of perfect information-theoretic privacy is relaxed. This enables higher rates to be achieved, while some information about the desired file index leaks to the servers. This leakage is captured by various known privacy metrics. By leveraging the well-established capacity-achieving schemes of Sun and Jafar under non-colluding ($T=1$) and colluding ($1

Submodular functions are known to satisfy various forms of fractional subadditivity. This work investigates the conditions for equality to hold exactly or approximately in the fractional sub additivity of sub modular functions. We establish that a small gap in the inequality implies that the function is close to being modular, and that the gap is zero if and only if the function is modular. We then present natural implications of these results for special cases of sub modular functions, such as entropy, relative entropy, and matroid rank. As a consequence, we characterize the necessary and sufficient conditions for equality to hold in Shearer's lemma, recovering a result of Ellis et al. (2016) as a special case. We leverage our results to propose a new multivariate mutual information, which generalizes Watanabe's total correlation (1960), Han's dual total correlation (1975), and Csiszar and Narayan's shared information (2004), and analyze its properties. Among these properties, we extend Watanabe's characterization of total correlation as the maximum correlation over partitions to fractional partitions. When applied to matrix determinantal inequalities for positive definite matrices, our results recover the equality conditions of the classical determinantal inequalities of Hadamard, Szász, and Fischer as special cases.

Dual discriminator generative adversarial networks (D2 GANs) were introduced to mitigate the problem of mode collapse in generative adversarial networks. In D2 GANs, two discriminators are employed alongside a generator: one discriminator rewards high scores for samples from the true data distribution, while the other favors samples from the generator. In this work, we first introduce dual discriminator α-GANs (D2 α-GANs), which combines the strengths of dual discriminators with the flexibility of a tunable loss function, α-loss. We further generalize this approach to arbitrary functions defined on positive reals, leading to a broader class of models we refer to as generalized dual discriminator generative adversarial networks. For each of these proposed models, we provide theoretical analysis and show that the associated min-max optimization reduces to the minimization of a linear combination of an f-divergence and a reverse f-divergence. This generalizes the known simplification for D2-GANs, where the objective reduces to a linear combination of the KL-divergence and the reverse KL-divergence. Finally, we perform experiments on 2D synthetic data and use multiple performance metrics to capture various advantages of our GANs.

We study information leakage through guesswork, the minimum expected number of guesses required to guess a random variable. In particular, we define maximal guesswork leakage as the multiplicative decrease, upon observing$Y$, of the guesswork of a randomized function of$X$, maximized over all such randomized functions. We also study a pointwise form of the leakage which captures the leakage due to the release of a single realization of$Y$. We also study these two notions of leakage with oblivious (or memoryless) guessing. We obtain closed-form expressions for all these leakage measures, with the exception of one. Specifically, we are able to obtain closed-form expression for maximal guesswork leakage for the binary erasure source only; deriving expressions for arbitrary sources appears challenging. Some of the consequences of our results are - a connection between guesswork and differential privacy and a new operational interpretation to maximal$\alpha$-leakage in terms of guesswork.

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.

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.

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 study the problem of simulating a two-user multiple-access channel (MAC) over a multiple access network of noiseless links. Two encoders observe independent and identically distributed (i.i.d.) copies of a source random variable each, while a decoder observes i.i.d. copies of a side-information random variable. There are rate-limited noiseless communication links between each encoder and the decoder, and there is independent pairwise shared randomness between all the three possible pairs of nodes. The decoder has to output approximately i.i.d. copies of another random variable jointly distributed with the two sources and the side information. We are interested in the rate tuples which permit this simulation. This setting can be thought of as a multi-terminal generalization of the point-to-point channel simulation problem studied by Bennett et al. (2002) and Cuff (2013). When the pairwise shared randomness between the encoders is absent, the setting reduces to a special case of MAC simulation using another MAC studied by Haddadpour et al. (2013). We establish that the presence of encoder shared randomness can strictly improve the communication rate requirements. We first show that the inner bound derived from Haddadpour et al. (2013) is tight when the sources at the encoders are conditionally independent given the side-information at the decoder. This result recovers the existing results on point-to-point channel simulation and function computation over such multi-terminal networks. We then explicitly compute the communication rate regions for an example both with and without the encoder shared randomness and demonstrate that its presence strictly reduces the communication rates. Inner and outer bounds for the general case are also obtained.

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 study the problem of simulating a multiple access channel over a network of noiseless links. Two encoders observe independent and identically distributed (i.i.d.) copies of a source random variable each, while a decoder observes i.i.d. copies of a side-information random variable. There are rate-limited noiseless communication links and independent pairwise shared randomness resources between each encoder and the decoder. The decoder has to output approximately i.i.d. copies of another random variable jointly distributed with the observed random variables. This setting can be thought of as a multi-terminal generalization of the point-to-point channel simulation problem studied by Bennett et al. (2002) and Cuff (2013). General inner and outer bounds on the rate region are derived. For the special case when the sources at the encoders are conditionally independent given the side-information at the decoder, we completely characterize the rate region. Our bounds recover the existing results on deterministic function computation over such multi-terminal networks. We then show through an example that an additional independent source of shared randomness between the encoders that is not available to the decoder strictly improves the communication rates.

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 study common randomness generation problems where$n$players aim to generatesamesequences of random coin flips where some subsets of the players share an independent common coin which can be tossed multiple times, and there is a publicly seen blackboard through which the players communicate with each other. We provide a tight representation of the optimal communication rates via linear programming, and more importantly, propose explicit algorithms for the optimal distributed simulation for a wide class of hypergraphs. In particular, the optimal communication rate in complete hypergraphs is still achievable in sparser hypergraphs containing a path-connected cycle-free cluster of topologically connected components. Some key steps in analyzing the upper bounds rely on two different definitions of connectivity in hypergraphs, which may be of independent interest.

We study a distributed sampling problem where a set of processors want to output (approximately) independent and identically distributed samples from a given joint distribution with the help of a common message from a coordinator. Each processor has access to a subset of sources from a set of independent sources of “shared” randomness. We consider two cases - in the “omniscient coordinator setting”, the coordinator has access to all these sources of shared randomness, while in the “oblivious coordinator setting,” it has access to none. In addition, all processors and the coordinator may privately randomize. In the omniscient coordinator setting, when the subsets at the processors are disjoint (individually shared randomness model), we characterize the rate of communication required from the coordinator to the processors over a multicast link. For the two-processor case, the optimal rate matches a special case of relaxed Wyner's common information proposed by Gastpar and Sula (2019), thereby providing an operational meaning to the latter. We also give an upper bound on the communication rate for the “randomness-on-the-forehead” model where each processor observes all but one source of randomness and present an achievable strategy for the general case where the processors have access to arbitrary subsets of sources of randomness. Also, we consider a more general model where the processors observe components of correlated sources (with the coordinator observing all the components), where we characterize the communication rate when all the processors wish to output the same random sequence. In the oblivious coordinator setting, we completely characterize the trade-off region between the communication and shared randomness rates for the general case where the processors have access to arbitrary subsets of sources of randomness.

We consider a two-user secure computation problem in which Alice and Bob communicate interactively in order to compute some deterministic functions of the inputs. The privacy requirement is that each user should not learn any additional information about a function of the inputs other than what can be inferred from its own input and output. For the distribution-free setting, i.e., when the protocol must be correct and private for any joint input distribution, we completely characterize the set of all securely computable functions. When privacy is required only against Bob who computes a function based on a single transmission from Alice, we show that asymptotically secure computability is equivalent to perfectly secure computability. Separately, we consider an eavesdropper who has access to all the communication and should not learn any information about some function of the inputs (possibly different from the functions to be computed by the users) and show that interaction may be necessary for secure computation.

We consider interactive computation of randomized functions between two users with the following privacy requirement: the interaction should not reveal to either user any extra information about the other user's input and output other than what can be inferred from the user's own input and output. We also consider the case where privacy is required against only one of the users. For both cases, we give single-letter expressions for feasibility and optimal rates of communication. Then we discuss the role of common randomness and interaction in both privacy settings. We also study perfectly secure non-interactive computation when only one of the users computes a randomized function based on a single transmission from the other user. We characterize randomized functions which can be perfectly securely computed in this model and obtain tight bounds on the optimal message lengths in all the privacy settings.

We study a distributed sampling problem where a set of processors want to output correlated sequences of random variables with the help of a coordinator which has access to several independent sources of randomness. Each processor has access to a subset of these sources. When these subsets are pairwise disjoint (individually shared randomness model), we characterize the rate of communication required from the coordinator to the processors over a multicast link. We also give an upper bound on the communication rate for the randomness-on-the-forehead model where each processor observes all but one source of randomness. For the general model, we completely characterize the trade-off region between communication and shared randomness rates when all the processors wish to output the same random sequence.

We consider interactive computation of randomized functions between two users with the following privacy requirement: the interactive communication should not reveal to either user any extra information about the other user's input and output other than what can be inferred from the user's own input and output. We also consider the case where privacy is required against only one of the users. For both cases, we give single-letter expressions for feasibility and optimal rates of communication. Then we discuss the role of common randomness and interaction in both privacy settings.

Two processors output correlated sequences using the help of a coordinator with whom they individually share independent randomness. For the case of unlimited shared randomness, we characterize the rate of communication required from the coordinator to the processors over a broadcast link. We also give an achievable trade-off between the communication and shared randomness rates.