We study the evolution of the generalization Error of Federated Learning with the number of communication rounds between the clients and a parameter server (PS). We establish stability-based and rate-distortion theoretic-based bounds on the generalization error that account explicitly for the effect of the number of roundsR, in addition to the number of participating clientsKand individual datasets sizen. For distinct communication rounds, these bounds involve conditional mutual information terms that are coupled through the aggregated model; and, partly for this reason, their computation is not easy, especially in the one-shot regime,i.e., using only one training dataset. In this paper, we also develop algorithms that allow to estimate the established bounds using only one training dataset. In some cases, the bounds are more explicit, such as for FL-type Support Vector Machines (FSVM). In this case, we show that the bound increases withR, suggesting that more frequent communication with PS diminishes the generalization power. This implies that the population risk of FSVM decreases less rapidly withRthan does the empirical risk, a finding which we also validate experimentally. Finally, we provide experimental results obtained using neural networks (ResNet-56) which show that not only may our observations for FSVM hold more generally but also that more communication with PS (beyond some valueR‹ ofR) may even hurt the population risk.

We establish in-expectation and tail bounds on the generalization error of representation learning type algorithms. The bounds are in terms of the relative entropy between the distribution of the representations extracted from the training and "test'' datasets and a data-dependent symmetric prior, i.e., the Minimum Description Length (MDL) of the latent variables for the training and test datasets. Our bounds are shown to reflect the "structure" and "simplicity'' of the encoder and significantly improve upon the few existing ones for the studied model. We then use our in-expectation bound to devise a suitable data-dependent regularizer; and we investigate thoroughly the important question of the selection of the prior. We propose a systematic approach to simultaneously learning a data-dependent Gaussian mixture prior and using it as a regularizer. Interestingly, we show that a weighted attention mechanism emerges naturally in this procedure. Our experiments show that our approach outperforms the now popular Variational Information Bottleneck (VIB) method as well as the recent Category-Dependent VIB (CDVIB).

We study the problem of distributed multi-view representation learning. In this problem, two agents observe each one distinct, but possibly statistically correlated, view and independently extract from it a suitable representation so that a decoder that gets both representations correctly estimates the hidden label. In the absence of any explicit coordination between the agents, a central question is: what should each agent extract from its view that is necessary and sufficient for a correct estimation at the decoder? In this paper, we investigate this question from a generalization error perspective. First, we establish generalization bounds in terms of the relative entropy between the distribution of the representations extracted from training and “test” datasets and a data-dependent symmetric prior, i.e., the joint Minimum Description Length (MDL) of the extracted representations. Then, we use the obtained bound to devise a regularizer; and investigate in depth the question of the selection of a suitable prior. In particular, we show that the selection of the joint prior as Gaussian-product mixture, which induces Gaussian mixture marginal prior for each marginal view, implicitly encourages the agents to extract and output redundant features; a finding which is somewhat counter-intuitive. Interestingly, we show that a joint weighted attention mechanism emerges naturally in our approach. Finally, we conduct several experiments that validate the efficiency of our proposed method.

In this paper, we leverage stochastic projection and lossy compression to establish new conditional mutual information (CMI) bounds on the generalization error of statistical learning algorithms. It is shown that these bounds are generally tighter than the existing ones. In particular, we prove that for certain problem instances for which existing MI and CMI bounds were recently shown in Attias et al. [2024] and Livni [2023] to become vacuous or fail to describe the right generalization behavior, our bounds yield suitable generalization guarantees of the order of $\mathcal{O}(1/\sqrt{n})$, where $n$ is the size of the training dataset. Furthermore, we use our bounds to investigate the problem of data "memorization" raised in those works, and which asserts that there are learning problem instances for which any learning algorithm that has good prediction there exist distributions under which the algorithm must "memorize'' a big fraction of the training dataset. We show that for every learning algorithm, there exists an auxiliary algorithm that does not memorize and which yields comparable generalization error for any data distribution. In part, this shows that memorization is not necessary for good generalization.

We investigate the generalization error of statistical learning models in a Federated Learning (FL) setting. Specifically, we study the evolution of the generalization error with the number of communication rounds $R$ between $K$ clients and a parameter server (PS), i.e. the effect on the generalization error of how often the clients' local models are aggregated at PS. In our setup, the more the clients communicate with PS the less data they use for local training in each round, such that the amount of training data per client is identical for distinct values of $R$. We establish PAC-Bayes and rate-distortion theoretic bounds on the generalization error that account explicitly for the effect of the number of rounds $R$, in addition to the number of participating devices $K$ and individual datasets size $n$. The bounds, which apply to a large class of loss functions and learning algorithms, appear to be the first of their kind for the FL setting. Furthermore, we apply our bounds to FL-type Support Vector Machines (FSVM); and derive (more) explicit bounds in this case. In particular, we show that the generalization bound of FSVM increases with $R$, suggesting that more frequent communication with PS diminishes the generalization power. This implies that the population risk decreases less fast with $R$ than does the empirical risk. Moreover, our bound suggests that the generalization error of FSVM decreases faster than that of centralized learning by a factor of $\mathcal{O}(\sqrt{\log(K)/K})$. Finally, we provide experimental results obtained using neural networks (ResNet-56) which show evidence that not only may our observations for FSVM hold more generally but also that the population risk may even start to increase beyond some value of $R$.

In this paper, we establish novel data-dependent upper bounds on the generalization error through the lens of a “variable-size compressibility” framework that we introduce newly here. In this framework, the generalization error of an algorithm is linked to a variable-size ‘compression rate’ of its input data. This is shown to yield bounds that depend on the value of the input training data sample at hand, rather than on its unknown distribution. Our new generalization bounds that we establish are tail bounds, tail bounds on the expectation, and in-expectations bounds. Moreover, it is shown that our framework also allows to derive general bounds on any function of the input data and output hypothesis random variables. In particular, these general bounds are shown to subsume and possibly improve over several existing PAC-Bayes and data-dependent intrinsic dimension-based bounds that are recovered as special cases, thus unveiling a unifying character of our approach.

A client device which has access to$n$training data samples needs to obtain a statistical hypothesis or model W and then to send it to a remote server. The client and the server devices share some common randomness sequence as well as a prior on the hypothesis space. In this problem a suitable hypothesis or model$W$should meet two distinct design criteria simultaneously: (i) small (population) risk during the inference phase and (ii) small ‘complexity’ for it to be conveyed to the server with minimum communication cost. In this paper, we propose a joint training and source coding scheme with provable in-expectation guarantees, where the expectation is over the encoder's output message. Specifically, we show that by imposing a constraint on a suitable Kullback-Leibler divergence between the conditional distribution induced by a compressed learning model$\hat{W}$given$W$and the prior, one guarantees simultaneously small average empirical risk (aka training loss), small average generalization error and small average communication cost. We also consider a one-shot scenario in which the guarantees on the empirical risk and generalization error are obtained for every encoder's output message.

In this paper, we establish novel data-dependent upper bounds on the generalization error through the lens of a “variable-size compressibility” framework that we introduce newly here. In this framework, the generalization error of an algorithm is linked to a variable-size ‘compression rate’ of its input data. This is shown to yield bounds that depend on the empirical measure of the given input data at hand, rather than its unknown distribution. Our new generalization bounds that we establish are tail bounds, tail bounds on the expectation, and in-expectations bounds. Moreover, it is shown that our framework also allows to derive general bounds on any function of the input data and output hypothesis random variables. In particular, these general bounds are shown to subsume and possibly improve over several existing PAC-Bayes and data-dependent intrinsic dimension-based bounds that are recovered as special cases, thus unveiling a unifying character of our approach. For instance, a new data-dependent intrinsic dimension-based bound is established, which connects the generalization error to the optimization trajectories and reveals various interesting connections with the rate-distortion dimension of a process, the Rényi information dimension of a process, and the metric mean dimension.

We study the generalization error of statistical learning models in a Federated Learning (FL) setting. Specifically, there are K devices or clients, each holding an independent own dataset of size n. Individual models, learned locally via Stochastic Gradient Descent, are aggregated (averaged) by a central server into a global model and then sent back to the devices. We consider multiple (say $ \in {{\mathbb{N}}^{\text{*}}}$ ) rounds of model aggregation and study the effect of R on the generalization error of the final aggregated model. We establish an upper bound on the generalization error that accounts explicitly for the effect of R (in addition to the number of participating devices K and dataset size ). It is observed that, for fixed $\left({n,K}\right)$, the bound increases with R, suggesting that the generalization of such learning algorithms is negatively affected by more frequent communication with the parameter server. Combined with the fact that the empirical risk, however, generally decreases for larger values of R, this indicates that R might be a parameter to optimize to reduce the population risk of FL algorithms. The results of this paper, which extend straightforwardly to the heterogeneous (non-i.i.d.) data setting, are also illustrated through numerical examples.

A major challenge in designing efficient statistical supervised learning algorithms is finding representations that perform well not only on available training samples but also on unseen data. While the study of representation learning has spurred much interest, most existing such approaches are heuristic; and very little is known about theoretical generalization guarantees. For example, the information bottleneck method seeks a good generalization by finding a minimal description of the input that is maximally informative about the label variable, where minimality and informativeness are both measured by Shannon’s mutual information. In this paper, we establish a compressibility framework that allows us to derive upper bounds on the generalization error of a representation learning algorithm in terms of the ``Minimum Description Length'' (MDL) of the labels or the latent variables (representations). Rather than the mutual information between the encoder’s input and the representation, which is often believed to reflect the algorithm’s generalization capability in the related literature but in fact, falls short of doing so, our new bounds involve the "multi-letter" relative entropy between the distribution of the representations (or labels) of the training and test sets and a fixed prior. In particular, these new bounds reflect the structure of the encoder and are not vacuous for deterministic algorithms. Our compressibility approach, which is information-theoretic in nature, builds upon that of Blum-Langford for PAC-MDL bounds and introduces two essential ingredients: block-coding and lossy-compression. The latter allows our approach to subsume the so-called geometrical compressibility as a special case. To the best knowledge of the authors, the established generalization bounds are the first of their kind for Information Bottleneck type encoders and representation learning. Finally, we partly exploit the theoretical results by introducing a new data-dependent prior. Numerical simulations illustrate the advantages of well-chosen such priors over classical priors used in IB.

Understanding generalization in modern machine learning settings has been one of the major challenges in statistical learning theory. In this context, recent years have witnessed the development of various generalization bounds suggesting different complexity notions such as the mutual information between the data sample and the algorithm output, compressibility of the hypothesis space, and the fractal dimension of the hypothesis space. While these bounds have illuminated the problem at hand from different angles, their suggested complexity notions might appear seemingly unrelated, thereby restricting their high-level impact. In this study, we prove novel generalization bounds through the lens of rate-distortion theory, and explicitly relate the concepts of mutual information, compressibility, and fractal dimensions in a single mathematical framework. Our approach consists of (i) defining a generalized notion of compressibility by using source coding concepts, and (ii) showing that the ’compression error rate’ can be linked to the generalization error both in expectation and with high probability. We show that in the ’lossless compression’ setting, we recover and improve existing mutual information-based bounds, whereas a ’lossy compression’ scheme allows us to link generalization to the rate-distortion dimension - a particular notion of fractal dimension. Our results bring a more unified perspective on generalization and open up several future research directions.

In this paper, we use tools from rate-distortion theory to establish new upper bounds on the generalization error of statistical distributed learning algorithms. Specifically, there are $K$ clients whose individually chosen models are aggregated by a central server. The bounds depend on the compressibility of each client's algorithm while keeping other clients' algorithms un-compressed, and leveraging the fact that small changes in each local model change the aggregated model by a factor of only $1/K$. Adopting a recently proposed approach by Sefidgaran et al., and extending it suitably to the distributed setting, enables smaller rate-distortion terms which are shown to translate into tighter generalization bounds. The bounds are then applied to the distributed support vector machines (SVM), suggesting that the generalization error of the distributed setting decays faster than that of the centralized one with a factor of $\mathcal{O}(\sqrt{\log(K)/K})$. This finding is validated also experimentally. A similar conclusion is obtained for a multiple-round federated learning setup where each client uses stochastic gradient Langevin dynamics (SGLD).

The capacity of a discrete-time model of optical fiber described by the split-step Fourier method (SSFM) as a function of the signal-to-noise ratio SNR and the number of segments in distance$K$is considered. It is shown that if$K\geq \text {SNR} ^{2/3}$and$\text {SNR} \rightarrow \infty $, the capacity of the resulting continuous-space lossless model is lower bounded by$\frac {1}{2}\log _{2}(1+ \text {SNR}) - \frac {1}{2}+ o(1)$, where$o(1)$tends to zero with SNR. As$K \rightarrow \infty $, the inter-symbol interference (ISI) averages out to zero due to the law of large numbers and the SSFM model tends to a diagonal phase noise model. It follows that, in contrast to the discrete-space model where there is only one signal degree-of-freedom (DoF) at high powers, the number of DoFs in the continuous-space model is at least half of the input dimension$n$. Intensity-modulation and direct detection achieves this rate. The pre-log in the lower bound when$K= \sqrt [\delta]{ \text {SNR}}$is generally characterized in terms of$\delta $. It is shown that if the nonlinearity parameter$\gamma \rightarrow \infty $, the capacity of the continuous-space model is$\frac {1}{2}\log _{2}(1+ \text {SNR})+ o(1)$. The SSFM model when the dispersion matrix does not depend on$K$is considered. It is shown that the capacity of this model when$K= \sqrt [\delta]{ \text {SNR}}$,$\delta >3$, and$\text {SNR} \rightarrow \infty $is$\frac {1}{2n}\log _{2}(1+ \text {SNR})+ O(1)$. Thus, there is only one DoF in this model. Finally, it is found that the maximum achievable information rates (AIRs) of the SSFM model with back-propagation equalization obtained using numerical simulation follows a double-ascent curve. The AIR characteristically increases with SNR, reaching a peak at a certain optimal power, and then decreases as SNR is further increased. The peak is attributed to a balance between noise and stochastic ISI. However, if the power is further increased, the AIR will increase again, approaching the lower bound$\frac {1}{2}\log (1+ \text {SNR})- \frac {1}{2} + o(1)$. The second ascent is because the ISI averages out to zero with$K \rightarrow \infty $sufficiently fast.

Neural network compression techniques have become increasingly popular as they can drastically reduce the storage and computation requirements for very large networks. Recent empirical studies have illustrated that even simple pruning strategies can be surprisingly effective, and several theoretical studies have shown that compressible networks (in specific senses) should achieve a low generalization error. Yet, a theoretical characterization of the underlying causes that make the networks amenable to such simple compression schemes is still missing. In this study, focusing our attention on stochastic gradient descent (SGD), our main contribution is to link compressibility to two recently established properties of SGD: (i) as the network size goes to infinity, the system can converge to a mean-field limit, where the network weights behave independently [DBDFŞ20], (ii) for a large step-size/batch-size ratio, the SGD iterates can converge to a heavy-tailed stationary distribution [HM20, GŞZ21]. Assuming that both of these phenomena occur simultaneously, we prove that the networks are guaranteed to be '$\ell_p$-compressible', and the compression errors of different pruning techniques (magnitude, singular value, or node pruning) become arbitrarily small as the network size increases. We further prove generalization bounds adapted to our theoretical framework, which are consistent with the observation that the generalization error will be lower for more compressible networks. Our theory and numerical study on various neural networks show that large step-size/batch-size ratios introduce heavy tails, which, in combination with overparametrization, result in compressibility.

This paper investigates the classical modulo two sum problem in source coding, but with a common observation: a transmitter observes (X,Z), the other transmitter observes (Y,Z), and the receiver wants to compute X ⊕Y without error. Through a coupling argument, this paper establishes a new lower bound on the sum-rate when X -Z -Y forms a Markov chain.

The limit of a discrete-time model of the optical fiber described by the split-step Fourier method (SSFM) when the number of segments in distance K tends to infinity is considered. It is shown that if $K \geq {\mathcal{P}^{2/3}}$ and $\mathcal{P} \to \infty $, where $\mathcal{P}$ is the average input power, the capacity of the resulting continuous-space lossless model is lower bounded by $\frac{1}{2}{\log _2}\left( {1 + {\text{SNR}}} \right) - \frac{1}{2} + o\left( 1 \right)$, where o(1) tends to zero with the signal-to-noise ratio SNR. This implies that at least half of the signal degrees-of-freedom remain asymptotically in this model.

This paper establishes the capacity region for a class of source coding function computation setups, where sources of information are available at the nodes of a tree and where a function of these sources must be computed at its root. The capacity region holds for any function as long as the sources' joint distribution satisfies a certain Markov criterion. This criterion is met, in particular, when the sources are independent. This result recovers the capacity regions of several function computation setups. These include the point-to-point communication setting with arbitrary sources, the noiseless multiple access network with conditionally independent sources, and the cascade network with Markovian sources.

This paper investigates a distributed function computation setting where the underlying network is a rooted directed tree and where the root wants to compute a function of the sources of information available at the nodes of the network. The main result provides the rate region for an arbitrary function under the assumption that the sources satisfy a general criterion. This criterion is satisfied, in particular, when the sources are independent.

A receiver wants to compute a function of two correlated sources separately observed by two transmitters. One of the transmitters is allowed to cooperate with the other transmitter by sending it some data before both transmitters convey information to the receiver. Assuming noiseless communication, what is the minimum number of bits that needs to be communicated by each transmitter to the receiver for a given number of cooperation bits? In this paper, first a general inner bound to the above three dimensional rate region is provided and shown to be tight in a number of interesting settings: the function is partially invertible, full cooperation, one-round point-to-point communication, two-round point-to-point communication, and cascade. Second, the related Kaspi-Berger rate distortion problem is investigated where the receiver now wants to recover the sources within some distortion. By using ideas developed for establishing the above inner bound, a new rate distortion inner bound is proposed. This bound always includes the time sharing of Kaspi-Berger's inner bounds and inclusion is strict in certain cases.

A transmitter has access to X, a relay has access to Y, and a receiver has access to Z and wants to compute a given function f(X, Y, Z). How many bits must be transmitted from the transmitter to the relay and from the relay to the receiver so that the latter can reliably recover f(X, Y, Z)? The main result is an inner bound to the rate region of this problem which is tight when X - Y - Z forms a Markov chain.

A receiver wants to compute a function f of two correlated sources X and Y and side information Z. What is the minimum number of bits that needs to be communicated by each transmitter? In this paper, we derive inner and outer bounds to the rate region which coincide in the cases where f is partially invertible and where one of the sources is constant. From the former case we recover the Slepian-Wolf rate region.

In this paper, we consider reliable transmission of a discrete memoryless source over multi-relay networks with correlated Side Information (SI) available at the relay nodes and the final receiver. We obtain a necessary condition for reliable source transmission over a multi-terminal network with SI, which results in a necessary condition for a multi-relay network with SI, as a special case. We also propose a separate source-channel coding scheme, and based on it, a sufficient condition for a multi-relay network with SI is derived. Based on a partitioning method and the nature of a degraded relay network, we propose another coding scheme which results in a sufficient condition for a degraded relay network with SI. We show that these proposed schemes which are based on operational separation, achieve the same rates as the joint source-channel codes and these sufficient conditions are indeed necessary conditions for the degraded relay networks with degraded SI.