This work presents several expected generalization error bounds based on the Wasserstein distance. More specifically, it introduces full-dataset, single-letter, and random-subset bounds, and their analogous in the randomized subsample setting from Steinke and Zakynthinou [1]. Moreover, when the loss function is bounded and the geometry of the space is ignored by the choice of the metric in the Wasserstein distance, these bounds recover from below (and thus, are tighter than) current bounds based on the relative entropy. In particular, they generate new, non-vacuous bounds based on the relative entropy. Therefore, these results can be seen as a bridge between works that account for the geometry of the hypothesis space and those based on the relative entropy, which is agnostic to such geometry. Furthermore, it is shown how to produce various new bounds based on different information measures (e.g., the lautum information or several $f$-divergences) based on these bounds and how to derive similar bounds with respect to the backward channel using the presented proof techniques.

In this work, we study the generalization capability of algorithms from an information-theoretic perspective. It has been shown that the expected generalization error of an algorithm is bounded from above by a function of the relative entropy between the conditional probability distribution of the algorithm’s output hypothesis, given the dataset with which it was trained, and its marginal probability distribution. We build upon this fact and introduce a mathematical formulation to obtain upper bounds on this relative entropy. Assuming that the data is discrete, we then develop a strategy using this formulation, based on the method of types and typicality, to find explicit upper bounds on the generalization error of stable algorithms, i.e., algorithms that produce similar output hypotheses given similar input datasets. In particular, we show the bounds obtained with this strategy for the case of$\epsilon $-DP and$\mu $-GDP algorithms.

Several recent works in communication systems have proposed to leverage the power of neural networks in the design of encoders and decoders. In this approach, these blocks can be tailored to maximize the transmission rate based on aggregated samples from the channel. Motivated by the fact that, in many communication schemes, the achievable transmission rate is determined by a conditional mutual information term, this paper focuses on neural-based estimators for this information-theoretic quantity. Our results are based on variational bounds for the KL-divergence and, in contrast to some previous works, we provide a mathematically rigorous lower bound. However, additional challenges with respect to the un-conditional mutual information emerge due to the presence of a conditional density function which we address here.

In this work, we unify several expected generalization error bounds based on random subsets using the framework developed by Hellström and Durisi. First, we recover the bounds based on the individual sample mutual information from Bu et al. and on a random subset of the dataset from Negrea et al. Then, we introduce their new, analogous bounds in the randomized subsample setting from Steinke and Zakynthinou, and we identify some limitations of the framework. Finally, we extend the bounds from Haghifam et al. for Langevin dynamics to stochastic gradient Langevin dynamics and we refine them for loss functions with potentially large gradient norms.

We investigate the behavior of the mutual information between two Boolean functions of correlated binary strings. The covariance of these functions is found to be a crucial parameter in the aforementioned mutual information. We then apply this result in the analysis of a specific privacy problem where a user observes a random binary string. Under particular conditions, we characterize the optimal strategy for communicating the outcomes of a function of said string while preventing to leak any information about a different function.

It is a well-known fact that feedback does not increase the capacity of point-to-point memoryless channels, however, its effect in secure communications is not fully understood yet. In this paper, an achievable scheme for the wiretap channel with generalized feedback is presented. This scheme, which uses the feedback signal to generate a shared secret key between the legitimate users, encrypts the message to be sent at the bit level. New capacity results for a class of channels are provided, as well as some new insights into the secret key agreement problem. Moreover, this scheme recovers previously reported rate regions from the literature, and thus it can be seen as a generalization that unifies several results in the field.

We investigate the problem of sharing (communi-cating) the outcomes of a memoryless source when some of its statistical parameters must be kept private. Privacy is measured in terms of the Bayesian statistical risk according to a desired loss function while the quality of the reconstruction is measured by the average per-letter distortion. We first bound -uniformly over all possible estimators- the expected risk from below. This information-theoretic bound depends on the mutual information between the parameters and the disclosed (noisy) samples. We then present an achievable scheme that guarantees an upper bound on the average distortion while keeping the risk above a desired threshold, even when the length of the sample increases.

This paper investigates the problem of secret key generation over a wiretap channel when the terminals have access to correlated sources. These sources are independent of the main channel and the users observe them before the transmission takes place. A novel achievable scheme for this model is proposed and is shown to be optimal under certain less noisy conditions. This result improves upon the existing literature where the more stringent condition of degradedness was needed.

It is well-known that feedback does not increase the capacity of point-to-point memoryless channels, however, its effect in secure communications is not fully understood yet. In this work, an achievable scheme for the wiretap channel with generalized feedback -based on joint source-channel coding- is presented. This scheme recovers previous results, thus it can be seen as a generalization and unification of several results in the field. Additionally, the Gaussian wiretap channel with noisy feedback is analyzed, and the scheme achieves positive secrecy rates even in unfavorable situations where the eavesdropper experiences a much better channel than the legitimate user.

The capacity of a class of interference relay channels (IRCs)-the injective semideterministic IRC where the relay can only observe one of the sources-is investigated. We first derive a novel outer bound and two inner bounds which are based on a careful use of each of the available cooperative strategies together with the adequate interference decoding technique. The outer bound extends Telatar and Tse's work, whereas the inner bounds contain several known results in the literature. Our main result is the characterization of the capacity region of the Gaussian class of IRCs studied within a fixed number of bits per dimension, constant gap. The proof relies on the use of the different cooperative strategies in specific SNR regimes due to their complexity. As a matter of fact, this issue reveals the complex nature of the Gaussian IRC where the combination of a single coding scheme for the Gaussian relay and interference channel may not lead to a good coding scheme for this problem, even when the focus is only on capacity within a constant gap over all possible fading statistics.

The capacity of a class of Interference Relay Channels (IRC) is investigated. We derive a novel outer and three inner bounds which are based on a careful use of all existing cooperative strategies together with the adequate interference decoding technique. Our main result is the necessity of three different cooperative strategies to achieve a constant gap to the capacity for each SNR regime of the Gaussian IRC. Surprisingly enough, this outcome appears to be in contrast with that of the standard Gaussian RC (Relay Channel) where several cooperative strategies yield constant-gap results in all regimes.

The broadcast nature of wireless transmissions is an advantage that has been exploited in the past to improve performance. Nodes belonging to a sensor network could listen to messages sent from other nodes and participate in this communication for the benefit of the entire network. In this paper, we present a novel communication protocol using cooperation among nodes. In particular, we use the Alamouti space-time coding in the cooperative phase of the transmission with a single relay. As a result, our approach obtains high throughput with low complexity and low energy consumption.