We introduce a two-parameter family of discrepancy measures, termed \emph{$(G,f)$-divergences}, obtained by applying a non-decreasing function $G$ to an $f$-divergence $D_f$. Building on Csiszár's formulation of mutual $f$-information, we define a corresponding $(G,f)$-information measure $ I_{G,f}(X;Y)$. A central theme of the paper is subadditivity over product distributions and product channels. We develop reduction principles showing that, for broad classes of $G$, it suffices to verify divergence subadditivity on binary alphabets. Specializing to the functions $G(x)\in\{x,\log(1+x),-\log(1-x)\}$, we derive tractable sufficient conditions on $f$ that guarantee subadditivity, covering many standard $f$-divergences. Finally, we present applications to finite-blocklength converses for channel coding, bounds in binary hypothesis testing, and an extension of the Shannon--Gallager--Berlekamp sphere-packing exponent framework to subadditive $(G,f)$-divergences.

Random binning is a widely used technique in information theory with diverse applications. In this paper, we focus on the output statistics of random binning (OSRB) using the Tsallis divergenceTα. We analyze all values of α ∈ (0,∞)∪{∞} and consider three scenarios: (i) the binned sequence is generated i.i.d., (ii) the sequence is randomly chosen from an ϵ-typical set, and (iii) the sequence originates from an ϵ-typical set and is passed through a non-memoryless virtual channel. Our proofs cover both achievability and converse results. To address the unbounded nature ofT∞, we extend the OSRB framework via Rényi’s divergence with order infinity, denotedD∞. As part of our exploration, we analyze a specific form of Rényi’s conditional entropy and its properties. Additionally, we demonstrate the application of this framework in deriving achievability results for the wiretap channel, where Tsallis divergence serves as a security measure. The secure rate we obtain through the OSRB analysis matches the secure capacity for α ∈ (0, 2] ∪ {∞} and serves as a potential candidate for the secure capacity when α ∈ (2,∞).

Counterfactual explanations enhance interpretability by identifying alternative inputs that produce different outputs, offering localized insights into model decisions. However, traditional methods often neglect causal relationships, leading to unrealistic examples. While newer approaches integrate causality, they are computationally expensive. To address these challenges, we propose an efficient method called BRACE based on backtracking counterfactuals that incorporates causal reasoning to generate actionable explanations. We first examine the limitations of existing methods and then introduce our novel approach and its features. We also explore the relationship between our method and previous techniques, demonstrating that it generalizes them in specific scenarios. Finally, experiments show that our method provides deeper insights into model outputs.

Estimating high-dimensional covariance matrices is crucial in various domains. This work considers a scenario where two collaborating agents access disjoint dimensions of $m$ samples from a high–dimensional random vector, and they can only communicate a limited number of bits to a central server, which wants to accurately approximate the covariance matrix. We analyze the fundamental trade–off between communication cost, number of samples, and estimation accuracy. We prove a lower bound on the error achievable by any estimator, highlighting the impact of dimensions, number of samples, and communication budget. Furthermore, we present an algorithm that achieves this lower bound up to a logarithmic factor, demonstrating its near-optimality in practical settings.

This paper investigates a range of empirical risk functions and regularization methods suitable for self-training methods in semi-supervised learning. These approaches draw inspiration from various divergence measures, such as f- di-vergences and$\alpha$- Renyi divergences. Inspired by the theoretical foundations rooted in divergences, i.e.,$f$-divergences and$\alpha$- Renyi divergence, we also provide valuable insights to enhance the understanding of our empirical risk functions and regularization techniques. In the pseudo-labeling and entropy minimization techniques as self-training methods for effective semi-supervised learning, the self-training process has some inherent mismatch between the true label and pseudo-label (noisy pseudo-labels) and some of our empirical risk functions are robust, concerning noisy pseudo-labels. Under some conditions, our empirical risk functions demonstrate better performance when compared to traditional self-training methods.

Random binning is a widely utilized tool in information theory, particularly for proving achievability bounds. In this paper, we investigate the output statistics of random binning (OSRB) for two cases: where the binned sequence is i.i.d. generated, and randomly chosen from an$\epsilon$-typical set using the Tsallis divergence$T_{\alpha}$measure for all values of$\alpha\in(0, \infty)$. For$\alpha=\infty$, due to the unbounded nature of$T_{\infty}$, we analyze the OSRB framework using Rényi's divergence criterion with the order of infinity, denoted as$D_{\infty}$. While exploring OSRB, we encounter a specific form of Renyi's conditional entropy and delve into its properties. Additionally, we demonstrate the effectiveness of this framework in establishing achievability results for wiretap channels, where Tsallis divergence serves as a security measure. The secure rate we obtain is equal to the capacity for$\alpha\in(0.2]$.

In this paper, we provide three applications for$ {\mathsf {f}}$-divergences: (i) we introduce Sanov’s upper bound on the tail probability of the sum of independent random variables based on super-modular$ {\mathsf {f}}$-divergence and show that our generalized Sanov’s bound strictly improves over ordinary one, (ii) we consider the lossy compression problem which studies the set of achievable rates for a given distortion and code length. We extend the rate-distortion function using mutual$ {\mathsf {f}}$-information and provide new and strictly better bounds on achievable rates in the finite blocklength regime using super-modular$ {\mathsf {f}}$-divergences, and (iii) we provide a connection between the generalization error of algorithms with bounded input/output mutual$ {\mathsf {f}}$-information and a generalized rate-distortion problem. This connection allows us to bound the generalization error of learning algorithms using lower bounds on the$ {\mathsf {f}}$-rate -distortion function. Our bound is based on a new lower bound on the rate-distortion function that (for some examples) strictly improves over previously best-known bounds.

We study learning algorithms when there is a mismatch between the distributions of the training and test datasets of a learning algorithm. The effect of this mismatch on the generalization error and model misspecification are quantified. Moreover, we provide a connection between the generalization error and the rate-distortion theory, which allows one to utilize bounds from the rate-distortion theory to derive new bounds on the generalization error and vice versa. In particular, the rate-distortion-based bound strictly improves over the earlier bound by Xu and Raginsky even when there is no mismatch. We also discuss how “auxiliary loss functions” can be utilized to obtain upper bounds on the generalization error. A full version of this paper is accessible at [1].

We consider the fundamental limits of reliable communication over a two-state compound channel when the state of the channel needs to be masked. Our model is closely related to an area of study known as covert communication, a setting in which the transmitter wishes to communicate to legitimate receiver(s) while ensuring that the communication is not detected by an adversary. Our main contribution is the establishment of upper and lower bounds on the throughput-key length region when the constraint that quantifies how much the states are masked is defined to be the total variation distance between the channel output distributions of the two states. When length of the key is sufficiently large, we provide sufficient conditions for the bounds to coincide. Our results follow the so-called square-root law and hence are reminiscent of results in covert communications. Numerical examples, including that of a Gaussian channel, are provided to illustrate our results.

In this paper, we study covert communication over a compound discrete memoryless channel (DMC). There are two channel states in which one of them is arbitrarily chosen and remains fixed during the transmission. The objective is to reliably send a message from the transmitter to the receiver. An adversary who is observing the channel output should not be able to infer the channel state. Two covertness metrics are considered. In the first metric, covertness is measured using the KL-divergence of the channel output marginal of each state with a fixed distribution. Different cases where such a distribution can be specified, are studied. The optimal transmission rate of each case is established. In the second metric, the covertness is measured by using the total variation distance of the channel output marginals of the two states. Upper and lower bounds on the optimal transmission covert rate are derived. The bounds match for a special case and characterize the optimal throughput.

In this paper, a new measure of correlation is introduced. This measure depends on a parameter α, and is defined in terms of vector-valued Lpnorms. The measure is within a constant of the exponential of α-Rényi mutual information, and reduces to the trace norm (total variation distance) for α = 1. We provide some properties and applications of this measure of correlation. In particular, we establish a bound on the secrecy exponent of the wiretap channel (under the total variation metric) in terms of the α-Rényi mutual information according to Csiszár's proposal.

This paper investigates the soft covering lemma under both the relative entropy and the total variation distance as the measures of deviation. The exact order of the expected deviation of the random i.i.d. code for the soft covering problem problem, is determined. The proof technique used in this paper significantly differs from the previous techniques for deriving exact exponent of the soft covering lemma. The achievability of the exact order follows from applying the change of measure trick (which has been broadly used in the large deviation) to the known one-shot bounds in the literature. For the ensemble converse, some new inequalities of independent interest derived and then the change of measure trick is applied again. The exact order of the total variation distance is similar to the exact order of the error probability, thus it adds another duality between the channel coding and soft covering. Finally, The results of this paper are valid for any memoryless channels, not only channels with finite alphabets.

A fundamental tool in network information theory is the covering lemma, which lower bounds the probability that there exists a pair of random variables; among a given number of independently generated candidates, falling within a given set. We use a weighted sum trick and Talagrand’s concentration inequality to prove new mutual covering bounds. We identify two interesting applications: 1) when the probability of the set under the given joint distribution is bounded away from 0 and 1, the covering probability converges to 1doublyexponentially fast in the blocklength, which implies that the covering lemma does not induce penalties on the error exponents in the applications to coding theorems; and 2) using Hall’s marriage lemma, we show that the maximum difference between the probability of the set under the joint distribution and the covering probability equals half the minimum total variation distance between the joint distribution and any distribution that can be simulated by selecting a pair from the candidates. Thus we use the mutual covering bound to derive the exact error exponent in the joint distribution simulation problem. In both applications, the determination of the exact exponential (or double exponential) behavior relies crucially on the sharp concentration inequality used in the proof of the mutual covering lemma.

In this paper, we introduce a new measure of correlation for bipartite quantum states. This measure depends on a parameter$\alpha $, and is defined in terms of vector-valued$\textit {L}_{\textit {p}}$-norms. The measure is within a constant of the exponential of$\alpha $-Rényi mutual information, and reduces to the trace norm (total variation distance) for$\alpha =1$. We will prove some decoupling type theorems in terms of this measure of correlation, and present some applications in privacy amplification as well as in bounding the random coding exponents. In particular, we establish a bound on the secrecy exponent of the wiretap channel (under the total variation metric) in terms of the$\alpha $-Rényi mutual information according toCsiszár’s proposal.

New one-shot bounds for multivariate covering are derived via a weighted sum technique and a one-sided concentration inequality which is stronger than the McDiarmid inequality. The new bounds are more compact and sharper than known bounds in the literature. In particular, the covering error can be shown to decay doubly exponentially in the blocklength. Implications for the error exponent in broadcast channels are discussed.

In this paper, we study the problem of simulating a discrete memoryless channel (DMC) from another DMC under an average-case and an exact model. We present several achievability and infeasibility results, with tight characterizations in special cases. In particular, for the exact model, we fully characterize when a binary symmetric channel can be simulated from a binary erasure channel when there is no shared randomness. We also provide infeasibility and achievability results for the simulation of a binary channel from another binary channel in the case of no shared randomness. To do this, we use the properties of Rényi capacity of a given order. We also introduce a notion of “channel diameter” which is shown to be additive and satisfy a data processing inequality.

This paper provides a universal framework for establishing one-shot achievability results for coordination and secrecy problems. The framework is built on our previous framework [Yassaee et al. 13] for proving one-shot achievability results in the context of source and channel coding problems. In the coordination and secrecy problems, one needs to compare an induced distribution by encoding/decoding with an ideal distribution (satisfying some desirable properties) using a suitable criterion. In this paper, we use fidelity as a criterion for measuring the closeness of induced distribution with the ideal distribution. The framework exploits the stochastic mutual information coders at the encoders and decoders and uses Jensen's inequality to find a lower bound on the expected fidelity. Moreover, the framework employs Cauchy-Schwarz inequality to simplify the relations prior to applying Jensen's inequality. We illustrate the framework via channel synthesis problem and wiretap channel. Furthermore, a novel one-shot generalization of multivariate covering lemma and soft covering lemma (cf. Cuff'13) is established.

In this paper, we study the problem of channel simulation via interactive communication, known as the coordination capacity, in a two-terminal network. We assume that two terminals observe independent identically distributed (i.i.d.) copies of two random variables and would like to generate i.i.d. copies of two other random variables jointly distributed with the observed random variables. The terminals are provided with two-way communication links, and shared common randomness, all at limited rates. Two special cases of this problem are the interactive function computation studied by Ma and Ishwar, and the tradeoff curve between one-way communication and shared randomness studied by Cuff. The latter work had inspired Gohari and Anantharam to study the general problem of channel simulation via interactive communication stated above. However, only inner and outer bounds for the special case of no shared randomness were obtained in their work. In this paper, we settle this problem by providing an exact computable characterization of the multiround problem. To show this we employ the technique of output statistics of random binning that has been recently developed by the authors.

This paper introduces a new and ubiquitous framework for establishing achievability results in network information theory problems. The framework uses random binning arguments and is based on a duality between channel and source coding problems. Furthermore, the framework uses pmf approximation arguments instead of counting and typicality. This allows for proving coordination and strong secrecy problems, where certain statistical conditions on the distribution of random variables need to be satisfied. These statistical conditions include independence between messages and eavesdropper's observations in secrecy problems and closeness to a certain distribution (usually, i.i.d. distribution) in coordination problems. One important feature of the framework is to enable one to add an eavesdropper and obtain a result on the secrecy rates for free. We make a case for generality of the framework by studying examples in a variety of settings including channel coding, lossy source coding, joint source-channel coding, coordination, strong secrecy, feedback, and relaying. In particular, by investigating the framework for the lossy source coding problem over broadcast channel, it is shown that the new framework provides a simple alternative scheme to the hybrid coding scheme. In addition, new results on secrecy rate region (under strong secrecy criterion) of wiretap broadcast channel and wiretap relay channel are derived. In a set of accompanied papers, we have shown the usefulness of the framework to establish achievability results for coordination problems, including interactive channel simulation, coordination via relay and channel simulation via another channel.

This paper proposes a novel technique to prove a one-shot version of achievability results in network information theory. The technique is not based on covering and packing lemmas. In this technique, we use a stochastic encoder and decoder with a particular structure for coding that resembles both the ML and the joint-typicality coders. Although stochastic encoders and decoders do not usually enhance the capacity region, their use simplifies the analysis. The Jensen inequality lies at the heart of error analysis, which enables us to deal with the expectation of many terms coming from stochastic encoders and decoders at once. The technique is illustrated via four examples: point-to-point channel coding, Gelfand-Pinsker, broadcast channel and Berger-Tung problem of distributed lossy compression. Applying the one-shot result for the memoryless broadcast channel in the asymptotic case, we get the entire region of Marton's inner bound without any need for time-sharing. Also, these results are employed in conjunction with multi-dimensional berry-esseen CLT to derive new regions for finite-blocklength regime of Gelfand-Pinsker.

In this paper we develop a finite blocklength version of the Output Statistics of Random Binning (OSRB) framework. This framework is shown to be optimal in the point-to-point case. New second order regions for broadcast channel and wiretap channel with strong secrecy criterion are derived.

In this paper, we study the problem of simulating a DMC channel from another DMC channel. We assume that the input to the channel we are simulating is i.i.d. and that the transmitter and receivers are provided with common randomness at limited rates. We prove bounds for simulating point-to-point, MAC and broadcast channels. As a special case, we recover the achievability part of the result of Cuff for point-to-point channel simulation via a noiseless link and shared randomness.

In this paper, we study the problem of coordinating two nodes which can only exchange information via a relay at limited rates. The nodes are allowed to do a two-round interactive two-way communication with the relay, after which they should be able to generate i.i.d. copies of two random variables with a given joint distribution within a vanishing total variation distance. We prove inner and outer bounds on the coordination capacity region for this problem. Our inner bound is proved using the technique of “output statistics of random binning" that has recently been developed by Yassaee, et al.

This paper presents a new and ubiquitous framework for establishing achievability results in network information theory (NIT) problems. The framework is used to prove various new results. To express the main tool, consider a set of discrete memoryless correlated sources (DMCS). Assume that each source (except one, Zn) is randomly binned at a finite rate. We find sufficient conditions on these rates such that the bin indices are nearly mutually independent of each other and of Zn. This is used in conjunction with the Slepian-Wolf (S-W) result to set up the framework. We begin by illustrating this method via examples from channel coding and rate-distortion (or covering problems). Next, we use the framework to prove a new result on the lossy transmission of a source over a broadcast channel. We also prove a new lower bound to a three receiver wiretap broadcast channel under a strong secrecy criterion. We observe that we can directly prove the strong notion of secrecy without resorting to the common techniques, e.g., the leftover hash lemma. We have also used our technique to solve the problem of two-node interactive channel simulation and the problem of coordination via a relay.

In this paper, we study the problem of channel simulation via interactive communication, known as the coordination capacity, in a two-terminal network. We assume that two terminals observe i.i.d. copies of two random variables and would like to generate i.i.d. copies of two other random variables jointly distributed with the observed random variables. The terminals are provided with two-way communication links, and shared common randomness, all at limited rates. Two special cases of this problem are the interactive function computation studied by Ma and Ishwar, and the tradeoff curve between one-way communication and shared randomness studied by Cuff. The latter work had inspired Gohari and Anantharam to study the general problem of channel simulation via interactive communication stated above. However only inner and outer bounds for the special case of no shared randomness were obtained in their work. In this paper we settle this problem by providing an exact computable characterization of the multi-round problem. To show this we employ the technique of “output statistics of random binning” that has been recently developed by the authors.

In this paper the Output Statistics of Random Binning (OSRB) framework is used to prove a new inner bound for the problem of secure channel simulation. Our results subsume some recent results on the secure function computation. We also provide an achievability result for the problem of simultaneously simulating a channel and creating a shared secret key. A special case of this result generalizes the lower bound of Gohari and Anantharam on the source model to include constraints on the rates of the public discussion.

This paper deals with the problem of multicasting a set of discrete memoryless correlated sources (DMCS) over a cooperative relay network. Necessary conditions with cut-set interpretation are presented. A Joint source-Wyner–Ziv encoding/sliding window decoding scheme is proposed, in which decoding at each receiver is done with respect to an ordered partition of other nodes. For each ordered partition a set of feasibility constraints is derived. Then, utilizing the submodular property of the entropy function and a novel geometrical approach, the results of different ordered partitions are consolidated, which lead to sufficient conditions for our problem. The proposed scheme achieves operational separation between source coding and channel coding. It is shown that sufficient conditions are indeed necessary conditions in two special cooperative networks, namely, Aref network and finite-field deterministic network. Also, in Gaussian cooperative networks, it is shown that reliable transmission of all DMCS whose Slepian–Wolf region intersects the cut-set bound region within a constant number of bits, is feasible. In particular, all results of the paper are specialized to obtain an achievable rate region for cooperative relay networks which includes relay networks and two-way relay networks.

The problem of secure communication over Multiple-Access Wiretap channel (MAC-WTC) under strong secrecy criterion is investigated. A new technique based on channel output statistics approximation is developed for establishing the strong security over multi-user channels. In particular, this technique shows that how simple wiretap coding results in secure communication under strong secrecy criterion instead of weak secrecy criterion. As a side result of the paper, two results on the output statistics of MAC are provided. Such results can be used to approximate the mutual information between input and output of MAC with respect to a given codebook of arbitrary rate.

We present sufficient conditions for multicasting a set of correlated sources over cooperative networks. We propose a joint source-Wyner-Ziv encoding/sliding-window decoding scheme, in which each receiver considers an ordered partition of the other nodes. For each ordered partition, we obtain a set of feasibility constraints. We consolidate the results of the different ordered partitions by utilizing a result of geometrical approach to obtain the sufficient conditions. We observe that these sufficient conditions are indeed necessary conditions for Aref networks. As a consequence of the main result, we obtain an achievable rate region for networks with multicast demands. Also, we deduce an achievability result for two-way relay networks, where two nodes want to communicate over a relay network.

In this paper, we present a new generalization of the well- known Compress-and-Forward strategy for relay networks. We propose an offset decoding at destination, where destination considers an ordered partition of relays and decodes information of any partition with the help of information from prior partitions. We show that when we do not partition the set of relays, our result improves the result of Kramer, et al. A geometrical method is utilized to unify results of different ordered partitioning. Also, the unified result has a celebrated source-channel coding separation interpretation.