We consider the problem of shared randomness-assisted multiple access channel (MAC) simulation for product inputs and characterize the one-shot communication cost region via almost-matching inner and outer bounds in terms of the smooth max-information of the channel, featuring auxiliary random variables of bounded size. The achievability relies on a rejection-sampling algorithm to simulate an auxiliary channel between each sender and the decoder, and producing the final output based on the output of these intermediate channels. The converse follows via information-spectrum based arguments. To bound the cardinality of the auxiliary random variables, we employ the perturbation method from [Anantharam <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">et al</i>., IEEE Trans. Inf. Theory (2019)] in the one-shot setting. For the asymptotic setting and vanishing errors, our result expands to a tight single-letter rate characterization and consequently extends a special case of the simulation results of [Kurri <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">et al</i>., IEEE Trans. Inf. Theory (2022)] for fixed, independent and identically distributed (iid) product inputs to universal simulation for any product inputs. We broaden our discussion into the quantum realm by studying feedback simulation of quantum-to-classical (QC) MACs with product measurements [Atif <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">et al</i>., IEEE Trans. Inf. Theory (2022)]. For fixed product inputs and with shared randomness assistance, we give a quasi tight one-shot communication cost region with corresponding single-letter asymptotic iid expansion.

The trade-offs between error probabilities in quantum hypothesis testing are by now well-understood in the centralized setting, but much less is known for distributed settings. Here, we study a distributed binary hypothesis testing problem to infer a bipartite quantum state shared between two remote parties, where one of these parties communicates to the tester at zero-rate, while the other party communicates to the tester at zero-rate or higher. As our main contribution, we derive an efficiently computable single-letter formula for the Stein's exponent of this problem, when the state under the alternative is product. As a key tool for proving the converse direction of our results, we develop a quantum version of the blowing-up lemma which may be of independent interest.

We propose an extension of the classical Rényi divergences to quantum states through an optimization over probability distributions induced by restricted sets of measurements. In particular, we define the notion of locally-measured Rényi divergences, where the set of allowed measurements originates from variants of locality constraints between (distant) partiesAandB. We then derive variational bounds on the locally-measured Rényi divergences and systematically discuss when these bounds become exact characterizations. As an application, we evaluate the locally-measured Rényi divergences on variants of highly symmetric data-hiding states, showcasing the reduced distinguishing power of locality-constrained measurements. For n-fold tensor powers, we further employ our variational formulae to derive corresponding additivity results, which gives the locally-measured Rényi divergences operational meaning as optimal rate exponents in asymptotic locally-measured hypothesis testing.

Estimation of quantum relative entropy and its Rényi generalizations is a fundamental statistical task in quantum information theory, physics, and beyond. While several estimators of these divergences have been proposed in the literature along with their computational complexities explored, a limit distribution theory which characterizes the asymptotic fluctuations of the estimation error is still premature. As our main contribution, we characterize these asymptotic distributions in terms of Fréchet derivatives of elementary operator-valued functions. We achieve this by leveraging an operator version of Taylor’s theorem and identifying the regularity conditions needed. As an application of our results, we consider an estimator of quantum relative entropy based on Pauli tomography of quantum states and show that the resulting asymptotic distribution is a centered normal, with its variance characterized in terms of the Pauli operators and states. We utilize the knowledge of the aforementioned limit distribution to obtain asymptotic performance guarantees for a multi-hypothesis testing problem.

We consider the problem of simulating a two-sender multiple access channel (MAC) for fixed product inputs, where each sender transmits a message to the decoder over a rate-limited noiseless link based on its input and unlimited randomness shared with the decoder. As our main contribution, we characterize the one-shot communication cost region via almost-matching inner and outer bounds phrased in terms of the smooth max-information of the channel. The achievability relies on a rejection-sampling algorithm to simulate a quantization channel between each sender and decoder, and producing the final output based on the output of these intermediate channels. The converse follows via information-spectrum based arguments relating operational quantities to information measures. Our one-shot results recover the single-letter asymptotic rate region for MAC simulation with fixed, independent and identically distributed product inputs, that was obtained in [Kurri et al., IEEE Transactions on Information Theory 68, 7575 (2022)]. We extend our result to quantum-to-classical channels with a separable decomposition [Atif et al., IEEE Transactions on Information Theory 68, 1085 (2022)], for which we obtain a similar characterization.

We propose an extension of the classical Rényi divergences to quantum states through an optimization over probability distributions induced by restricted sets of measurements. In particular, we define the notion of locally-measured Rényi divergences, where the set of allowed measurements orig-inates from locality constraints between (distant) parties$A$and$B$. As our main result, we derive variational characterizations of these locally-measured Rényi divergences. We then evaluate them for variants of data-hiding states, showcasing the reduced distinguishing power of locality-constrained measurements, and give corresponding applications in locally-measured hypothesis testing.

Estimation of quantum relative entropy is a fundamental statistical task in quantum information theory, physics, and beyond. While several estimators of the same have been proposed in the literature along with their computational complexities explored, a limit distribution theory which characterizes the asymptotic fluctuations of the estimation error is still premature. As our main contribution, we characterize these asymptotic distributions in terms of Fréchet derivatives of elementary operator-valued functions. We achieve this by leveraging an operator version of Taylor's theorem and identifying the regularity conditions needed. As an application of our results, we consider an estimator of quantum relative entropy based on Pauli tomography of quantum states and show that the resulting asymptotic distribution is a centered normal, with its variance characterized in terms of the Pauli operators and states. We utilize the knowledge of the aforementioned limit distribution to obtain asymptotic performance guarantees for a multi-hypothesis testing problem.

$f$-divergences, which quantify discrepancy between probability distributions, are ubiquitous in information theory, machine learning, and statistics. While there are numerous methods for estimating$f$-divergences from data, a limit distribution theory, which quantifies fluctuations of the estimation error, is largely obscure. As limit theorems are pivotal for valid statistical inference, to close this gap, we develop a general methodology for deriving distributional limits for$f$-divergences based on the functional delta method and Hadamard directional differentiability. Focusing on four prominent$f$-divergences—Kullback-Leibler divergence,$\chi ^{2}$divergence, squared Hellinger distance, and total variation distance—we identify sufficient conditions on the population distributions for the existence of distributional limits and characterize the limiting variables. These results are used to derive one- and two-sample limit theorems for Gaussian-smoothed$f$-divergences, both under the null and the alternative. Finally, an application of the limit distribution theory to auditing differential privacy is proposed and analyzed for significance level and power against local alternatives.

The Kullback-Leibler (KL) divergence is a discrepancy measure between probability distribution that plays a central role in information theory, statistics and machine learning. While there are numerous methods for estimating this quantity from data, a limit distribution theory which quantifies fluctuations of the estimation error is largely obscure. In this paper, we close this gap by identifying sufficient conditions on the population distributions for the existence of distributional limits and characterizing the limiting variables. These results are used to derive one- and two-sample limit theorems for Gaussian-smoothed KL divergence, both under the null and the alternative. Finally, an application of the limit distribution result to auditing differential privacy is proposed and analyzed for significance level and power against local alternatives.

Statistical divergences (SDs), which quantify the dissimilarity between probability distributions, are a basic constituent of statistical inference and machine learning. A modern method for estimating those divergences relies on parametrizing an empirical variational form by a neural network (NN) and optimizing over parameter space. Such neural estimators are abundantly used in practice, but corresponding performance guarantees are partial and call for further exploration. We establish non-asymptotic absolute error bounds for a neural estimator realized by a shallow NN, focusing on four popular $\mathsf{f}$-divergences---Kullback-Leibler, chi-squared, squared Hellinger, and total variation. Our analysis relies on non-asymptotic function approximation theorems and tools from empirical process theory to bound the two sources of error involved: function approximation and empirical estimation. The bounds characterize the effective error in terms of NN size and the number of samples, and reveal scaling rates that ensure consistency. For compactly supported distributions, we further show that neural estimators of the first three divergences above with appropriate NN growth-rate are minimax rate-optimal, achieving the parametric convergence rate.

Statistical distances (SDs), which quantify the dissimilarity between probability distributions, are central to machine learning and statistics. A modern method for estimating such distances from data relies on parametrizing a variational form by a neural network (NN) and optimizing it. These estimators are abundantly used in practice, but corresponding performance guarantees are partial and call for further exploration. In particular, there seems to be a fundamental tradeoff between the two sources of error involved: approximation and estimation. While the former needs the NN class to be rich and expressive, the latter relies on controlling complexity. This paper explores this tradeoff by means of non-asymptotic error bounds, focusing on three popular choices of SDs—Kullback-Leibler divergence, chi-squared divergence, and squared Hellinger distance. Our analysis relies on non-asymptotic function approximation theorems and tools from empirical process theory. Numerical results validating the theory are also provided.

In many information-theoretic channel coding problems, adding an input cost constraint to the operational setup amounts to restricting the optimization domain in the capacity formula. This paper shows that, in contrast to common belief, such a simple modification does not hold for the cost-constrained (CC) wiretap channel (WTC). The secrecy-capacity of the discrete memoryless (DM) WTC without cost constraints is described by a single auxiliary random variable. For the CC DM-WTC, however, we show that two auxiliaries are necessary to achieve capacity. Specifically, we first derive the secrecy-capacity formula, proving the direct part via superposition coding. Then, we provide an example of a CC DM-WTC whose secrecy-capacity cannot be achieved using a single auxiliary. This establishes the fundamental role of superposition coding over CC WTCs.

A distributed binary hypothesis testing (HT) problem over a noisy (discrete and memoryless) channel studied previously by the authors is investigated from the perspective of the strong converse property. It was shown by Ahlswede and Csiszar that a strong converse holds in the above setting when the channel is rate-limited and noiseless. Motivated by this observation, we show that the strong converse continues to hold in the noisy channel setting for a special case of HT known as testing against independence (TAI), under the assumption that the channel transition matrix has non-zero elements. The proof utilizes the blowing up lemma and the recent change of measure technique of Tyagi and Watanabe as the key tools.

A distributed binary hypothesis testing (HT) problem involving two parties, one referred to as the observer and the other as the detector is studied. The observer observes a discrete memoryless source (DMS) and communicates its observations to the detector over a discrete memoryless channel (DMC). The detector observes another DMS correlated with that at the observer, and performs a binary hypothesis test on the joint distribution of the two DMS's using its own observed data and the information received from the observer. The trade-off between the type I error probability and the type II error-exponent of the HT is explored. Single-letter lower bounds on the optimal type II error-exponent are obtained by using two different coding schemes, a separate HT and channel coding scheme and a joint HT and channel coding scheme based on hybrid coding for the matched bandwidth case. Exact single-letter characterization of the same is established for the special case of testing against conditional independence, and it is shown to be achieved by the separate HT and channel coding scheme. An example is provided where the joint scheme achieves a strictly better performance than the separation based scheme.

A point to point hypothesis testing problem involving two parties, one referred to as the observer and the other as the detector, is studied. The observer observes a discrete memoryless source and communicates its observations to the detector over a discrete memoryless channel. The detector performs a binary hypothesis test on the probability distribution of the observer's observation. The trade-off between the type 1 error probability and the type 2 error exponent is explored. We obtain a single-letter characterization of the optimal type 2 error exponent for a given constraint on the type 1 error probability. We also show that a strong converse holds, in the sense that, the optimal type 2 error exponent is independent of the constraint on the type 1 error probability.

We study the privacy-utility trade-off in data release under a rate constraint. An agent observes random variable X and reveals information U to the utility provider over a rate-constrained channel, such that I(X; U) ≤ R, in return for utility I(U; Y ), where Y denotes a latent random variable correlated with X. While the objective is to maximize the utility, the agent also wants to protect a private information S, also correlated with X and Y from the utility provider. The trade-off between rate, utility and private information leakage is studied. This problem can be thought of as a generalization of both the information bottleneck and privacy funnel problems, reducing to either of the two problems in special cases. A necessary and sufficient condition for the existence of positive utility under zero private information leakage (or perfect privacy) is established. Subsequently, the problem of maximizing the utility subject to perfect privacy constraint is shown to be a linear program when the rate constraint is inactive. Also, the maximum value of the ratio of utility to infinitesimal private information leakage for an arbitrary rate constraint is obtained.

A distributed binary hypothesis testing problem involving three parties, a remote node, called the observer, a legitimate decoder, called the detector, and an adversary, is studied. The remote node observes a discrete memoryless source, and communicates its observations over a rate-limited noiseless public channel to the detector, which tests for the conditional independence of its own observations from that of the remote node, conditioned on some additional side information. The adversary, in addition to observing the public message, has access to its own correlated side-information. Considering the type 2 error exponent for a given type 1 error probability constraint as the performance measure for the hypothesis test at the detector, and equivocation of the source at the adversary as the secrecy measure, a single-letter characterization of the rate-error exponent-equivocation trade-off is established. Additionally, for a general distortion measure, imposing the average distortion at the adversary as the measure of secrecy achieved, an inner bound on the trade-off between the rate, error exponent and average distortion is obtained. This bound is shown to be tight under the less noisy condition on the adversary's side information.

A distributed binary hypothesis testing problem involving two parties, a remote observer and a detector, is studied. The remote observer has access to a discrete memoryless source, and communicates its observations to the detector via a rate-limited noiseless channel. The detector tests for the independence of its own observations with that of the observer, conditioned on some additional side information. While the goal is to maximize the type 2 error exponent of the test for a given type 1 error probability constraint, it is also desired to keep a private part, which is correlated with the observer's observations, as oblivious to the detector as possible. Considering equivocation and average distortion as the metrics of privacy at the detector, a tight single-letter characterization of the rate-error exponent-equivocation and rate-error exponent-distortion tradeoff is obtained.

A time-slotted multiple access system with bursty data arrivals to the terminals is considered, where variable sized packets independently arrive in each slot at every transmitter. Each packet is required to be delivered to a common receiver within a certain number of slots specified by a maximum delay constraint. The terminals know only their own packet arrival process, i.e., the arrivals at the rest of the terminals are unknown to each transmitter, except for their probability distributions. For this interesting distributed multiple access model, we design novel online communication schemes which transport the arriving data without any outage, while respecting the delay constraint. In particular, the users choose their respective transmit powers in a distributed manner, ensuring at the same time that the joint power vector is sufficient to support the distributed choice of data rates employed in that slot. The proposed schemes are not only optimal in minimizing the average transmit sum power, but they also considerably outperform conventional orthogonal multiple access techniques like time-division multiple access. An optimal scheme for a multiple access channel with arrivals and time-varying fading is also presented, under a unit slot delay constraint.

A distributed binary hypothesis testing problem, in which multiple observers transmit their observations to a detector over noisy channels, is studied. Together with its own observations, the goal of the detector is to decide between two hypotheses for the joint distribution of the data. Single-letter upper and lower bounds on the optimal type 2 error exponent (T2-EE), when the type 1 error probability vanishes with the block-length are obtained. These bounds coincide and characterize the optimal T2-EE when only a single helper is involved. Our result shows that the optimal T2-EE depends on the marginal distributions of the data and the channels rather than their joint distribution. However, an operational separation between HT and channel coding does not hold, and the optimal T2-EE is achieved by generating channel inputs correlated with observed data.

Traditionally, the capacity region of a coherent fading multiple access channel (MAC) is analyzed in two popular contexts. In the first, a centralized system with full channel state information at the transmitters (CSITs) is assumed, and the transmit power and data-rate can be jointly chosen for every fading vector realization. On the other hand, in fast-fading links with distributed CSIT, the lack of full CSI is compensated by performing ergodic averaging over sufficiently many channel realizations. Notice that the distributed CSI may necessitate decentralized power-control for optimal data-transfer. Apart from these two models, the case of slow-fading links and distributed CSIT, though relevant to many systems, has received much less attention. In this paper, a block-fading additive white Gaussian noise MAC with full CSI at the receiver and distributed CSI at the transmitters is considered. The links undergo independent fading, but otherwise have arbitrary fading distributions. The channel statistics and respective long-term average transmit powers are known to all parties. We first consider the case where each encoder has knowledge only of its own link quality, and not of others. For this model, we compute the adaptive capacity region, i.e., the collection of average rate-tuples under blockwise coding/decoding such that the rate-tuple for every fading realization is inside the instantaneous MAC capacity region. The key step in our solution is an optimal rate allocation function for any given set of distributed power control laws at the transmitters. This also allows us to structurally characterize the optimal power control for a wide class of fading models. Further extensions are also proposed for the case where each encoder has additional partial CSI about the other links.

We consider a multiple access system (MAC) with bursty arrivals. The transmissions are grouped into slots and the users are frame-synchronized. At the start of each time slot, variable sized packets independently arrive at each of the transmitting terminals. The packets are to be delivered to a common receiver by the end of the slot. Each terminal knows only its own arrival process, i.e. the packet-sizes at the rest of the terminals are unknown to each transmitter. The respective link gains from the transmitters to the receiver are assumed to be fixed and known to all. In this random access system, we propose schemes which will deliver the arriving data without any outage, under strict delay constraints. Our schemes are optimal in minimizing the total average power spent in data transport.

We consider a block-fading Gaussian MAC under a local CSI model where the transmitters have access to their own fading states. The system requires that the joint transmission rate-vector should not be in outage in any block. The average rate-tuples that can be achieved in fading MAC under such local distributed CSI and outage-free transmission belong to the so called adaptive capacity region. We present the adaptive capacity region of MACs under fairly general fading distributions and local CSI. Our results considerably generalize the known sum-capacity solutions in literature, by evaluating the full capacity region. Our results also provide the adaptive capacity region for arbitrary given power allocation functions. We further extend our results to more general CSI models where each user has additional quantized CSI of the other links.

We consider a two-user block-fading MAC with distributed channel state information (CSI), where each user has access to only its own fading coefficients. The average rate-pairs of communication while employing within-block coding is known as the adaptive capacity region, where each user adapts the rate based on its perceived link gain. We evaluate the adaptive sum-capacity of MAC channels with general fading distributions, for discrete as well as continuous valued ones.