We propose a power-controlled differentially private decentralized learning algorithm designed for a set of clients aiming to collaboratively train a common learning model. The network is characterized by a row-stochastic adjacency matrix, which reflects different channel gains between the clients. In our privacy-preserving approach, both the transmit power for model updates and the level of injected Gaussian noise are jointly controlled to satisfy a given privacy and energy budget. We show that our proposed algorithm achieves a convergence rate of$O(\log T)$, where$T$is the horizon bound in the regret function. Furthermore, our numerical results confirm that our proposed algorithm outperforms existing works.

This paper introduces and analyzes a search and retrieval model that adopts key semantic communication principles from retrieval-augmented generation. We specifically present an information-theoretic analysis of a remote document retrieval system operating over a symbol erasure channel. The proposed model encodes the feature vector of a query, derived from term-frequency weights of a language corpus by using a repetition code with an adaptive rate dependent on the contextual importance of the terms. At the decoder, we select between two documents based on the contextual closeness of the recovered query. By leveraging a jointly Gaussian approximation for both the true and reconstructed similarity scores, we derive an explicit expression for the retrieval error probability, i.e., the probability under which the less similar document is selected. Numerical simulations on synthetic and real-world data (Google NQ) confirm the validity of the analysis. They further demonstrate that assigning greater redundancy to critical features effectively reduces the error rate, highlighting the effectiveness of semantic-aware feature encoding in error-prone communication settings.

We study a privacy-preserving data-sharing setting where a privatizer transforms private data into a sanitized version observed by an authorized reconstructor and two unauthorized adversaries, each with access to side information correlated with the private data.The reconstructor is evaluated under a distortion function, while each adversary is evaluated using a separate loss function. The privatizer ensures the reconstructor distortion remains below a fixed threshold while maximizing the minimum loss across the two adversaries. This two-adversary setting models cases where individual users cannot reconstruct the data accurately, but their combined side information enables estimation within the distortion threshold. The privatizer maximizes individual loss while permitting accurate reconstruction only through collaboration. This echoes secret-sharing principles, but with lossy rather than perfect recovery. We frame this as a constrained data-driven minimax optimization problem and propose a data-driven training procedure that alternately updates the privatizer, reconstructor, and adversaries. We also analyze the Gaussian and binary cases as special scenarios where optimal solutions can be obtained. These theoretical optimal results are benchmarks for evaluating the proposed minimax training approach.

We consider the problem of communication-constrained collaborative personalized mean estimation under a privacy constraint in an environment of several agents continuously receiving data according to arbitrary unknown agent-specific distributions. A consensus-based algorithm is studied under the framework of differential privacy in order to protect each agent’s data. We give a theoretical convergence analysis of the proposed consensus-based algorithm for any bounded unknown distributions on the agents’ data, showing that collaboration provides faster convergence than a fully local approach where agents do not share data, under an oracle decision rule and under some restrictions on the privacy level and the agents’ connectivity, which illustrates the benefit of private collaboration in an online setting under a communication restriction on the agents. The theoretical faster-than-local convergence guarantee is backed up by several numerical results.

Distributed computations, such as distributed matrix multiplication, can be vulnerable to significant security issues, notably Byzantine attacks. These attacks may target either worker nodes or servers, potentially leading to faulty results that can significantly degrade the overall performance. Therefore, detecting Byzantine attackers and mitigating their effects are crucial in such systems. Motivated by the goal of establishing a secure decentralized matrix-multiplication system, we first introduce a verification method named Common Tag, inspired by the well-known Freivalds’ algorithm, able to verify the multiplication results independent of their associated input matrices. Then, we propose two schemes for sparse matrix multiplication where a group of nodes collaboratively performs a computation task over a logical ring. We consider a subset of Byzantine nodes in the system that may arbitrarily corrupt either their result or any other result passing through them. In Scheme I considering the highly sparse nature of input matrices, we assume that each node has sufficient capacity to store the entire input matrices, and the nodes forward the read-only versions of their computed blocks so that other nodes cannot corrupt them. In Scheme II, we relax the above assumptions, firstly, by considering a limited storage capacity for each node. Secondly, we introduce more powerful adversaries capable of corrupting other nodes’ results by relaxing the read-only assumption. The results demonstrate the feasibility of both schemes and show a significant improvement in terms of distortion over the case where no detection happens. The results also provide a trade-off between the computational complexity required at each node and the reconstruction distortion in both schemes.

We consider the problem of collaborative personalized mean estimation under a privacy constraint in an environment of several agents continuously receiving data according to arbitrary unknown agent-specific distributions. In particular, we provide a method based on hypothesis testing coupled with differential privacy and data variance estimation. Two differential privacy mechanisms protecting the releases of each agent’s current sample mean and two data variance estimation schemes are proposed, and we provide a theoretical convergence analysis of the proposed algorithm for any bounded unknown distributions on the agents’ data, showing that collaboration provides faster convergence than a fully local approach where agents do not share data. Moreover, we provide analytical performance curves for the case with an oracle class estimator, i.e., the class structure of the agents, where agents receiving data from distributions with the same mean are considered to be in the same class, is known. The theoreticalfaster-than-localconvergence guarantee is backed up by extensive numerical results showing that for a considered scenario with 200 agents from two or three classes the proposed approach indeed converges much faster than a fully local approach, and performs comparably to the ideal (all-data-public) case. This illustrates the benefit of private collaboration in an online setting.

We introduce the paradigm of validated decentralized learning for undirected networks with heterogeneous data and possible adversarial infiltration. We require ($a$) convergence to a global empirical loss minimizer when adversaries are absent, and$(\boldsymbol{b})$either detection of adversarial presence or convergence to an admissible consensus model in their presence. This contrasts sharply with the traditional byzantine-robustness requirement of convergence to an admissible consensus irrespective of the adversarial configuration. To this end, we propose the Valid protocol which, to the best of our knowledge, is the first to achieve a validated learning guarantee. Moreover, Valid offers an$O(1/T)$convergence rate (under pertinent regularity assumptions), and computational and communication complexities comparable to non-adversarial distributed stochastic gradient descent. Remarkably, Valid retains optimal performance metrics in adversary-free environments, sidestepping the robustness penalties observed in prior byzantine-robust methods. A distinctive aspect of our study is a heterogeneity metric based on the norms of individual agents' gradients computed at the global empirical loss minimizer. This not only provides a natural statistic for detecting significant byzantine disruptions but also allows us to prove the optimality of Valid in wide generality. Lastly, our numerical results reveal that, in the absence of adversaries, Validcon-verges faster than state-of-the-art byzantine robust algorithms, while when adversaries are present, Valid terminates with each honest agent either converging to an admissible consensus or declaring adversarial presence in the network.

In this paper, we propose a sparse matrix multiplication in a decentralized setting, where a set of worker nodes wishes to compute a task collaboratively over a logical ring. We consider a subset of Byzantine nodes in the system who want to maliciously corrupt the result by corrupting their own computed blocks. In particular, the main focus of this paper is to compute the result with the least possible distortion by identifying the Byzantine nodes and re-assigning their tasks to the benign nodes. Our results demonstrate the feasibility of our proposed decentralized scheme and provide a trade-off between the computational complexity required at each worker node and the reconstruction distortion.

We consider the problem of collaborative personalized mean estimation under a privacy constraint in an environment of several agents continuously receiving data according to arbitrary unknown agent-specific distributions. In particular, we provide a method based on hypothesis testing coupled with differential privacy. Two privacy mechanisms are proposed and we provide a theoretical convergence analysis of the proposed algorithm for any bounded unknown distributions on the agents’ data. Numerical results show that for a considered scenario the proposed approach converges much faster than a fully local approach where agents do not share data, and performs comparably to ideal performance where all data is public. This illustrates the benefit of private collaboration in an online setting.

We consider straggler resiliency in decentralized learning using stochastic gradient descent under the notion of network differential privacy (DP). In particular, we extend the recently proposed framework of privacy amplification by decentralization by Cyffers and Bellet to include training latency—comprising both computation and communication latency. Analytical results on both the convergence speed and the DP level are derived for training over a logical ring for both a skipping scheme (which ignores the stragglers after a timeout) and a baseline scheme that waits for each node to finish before the training continues. Our results show a trade-off between training latency, accuracy, and privacy, parameterized by the timeout of the skipping scheme. Finally, results when training a logistic regression model on a real-world dataset are presented.

Private information retrieval protocols guarantee that a user canprivatelyandlosslesslyretrieve a single file from a database stored across multiple servers. In this work, we propose to simultaneously relax the conditions of perfect retrievability and privacy in order to obtain improved download rates when all files are stored uncoded on a single server. Information leakage is measured in terms of the average success probability for the server of correctly guessing the identity of the desired file. The main findings are: i) The derivation of the optimal tradeoff between download rate, distortion, and information leakage when the file size isinfinite. Closed-form expressions of the optimal tradeoff for the special cases of “no-leakage” and “no-privacy” are also given. ii) A novel approach based on linear programming (LP) to construct schemes for a finite file size and an arbitrary number of files. The proposed LP approach can be leveraged to find provably optimal schemes with corresponding closed-form expressions for the rate-distortion-leakage tradeoff when the database contains at most four bits. Finally, for a database that contains 320 bits, we compare two construction methods based on the LP approach with a nonconstructive scheme downloading subsets of files using a finite-length lossy compressor based on random coding.

We propose to extend the concept of private information retrieval by allowing for distortion in the retrieval process and relaxing the perfect privacy requirement at the same time. In particular, we study the tradeoff between download rate, distortion, and user privacy leakage, and show that in the limit of large file sizes this tradeoff can be captured via a novel information-theoretical formulation for datasets with a known distribution. Moreover, for scenarios where the statistics of the dataset is unknown, we propose a new deep learning framework by leveraging a generative adversarial network approach, which allows the user to learn efficient schemes from the data itself, minimizing the download cost. We evaluate the performance of the scheme on a synthetic Gaussian dataset as well as on the MNIST, CIFAR-10, and LSUN datasets. For the MNIST, CIFAR-10, and LSUN datasets, the data-driven approach significantly outperforms a nonlearning-based scheme which combines source coding with multiple file download.

Private information retrieval protocols guarantee that a user can privately and losslessly retrieve a single file from a database stored across multiple servers. In this work, we propose to simultaneously relax the conditions of perfect retrievability and privacy in order to obtain improved download rates in the single server scenario, i.e., all files are stored uncoded on a single server. In particular, we derive the optimal tradeoff between download rate, distortion, and information leakage when the file size is infinite and the information leakage is measured in terms of the average success probability for the server of correctly guessing the identity of the requested file. Moreover, we present a novel approach based on linear programming to construct schemes for a finite file size and an arbitrary number of files. When the database contains at most four bits, this approach can be leveraged to find provably optimal schemes.

In this work, we perform a complete failure analysis of the interval-passing algorithm (IPA) for compressed sensing. The IPA is an efficient iterative algorithm for reconstructing a k-sparse nonnegative n-dimensional real signal x from a small number of linear measurements y . In particular, we show that the IPA fails to recover x from y if and only if it fails to recover a corresponding binary vector of the same support, and also that only positions of nonzero values in the measurement matrix are of importance to the success of recovery. Based on this observation, we introduce termatiko sets and show that the IPA fails to fully recover x if and only if the support of x contains a nonempty termatiko set, thus giving a complete (graph-theoretic) description of the failing sets of the IPA. Two heuristics to locate small-size termatiko sets are presented. For binary column-regular measurement matrices with no 4-cycles, we provide a lower bound on the termatiko distance, defined as the smallest size of a nonempty termatiko set. For measurement matrices constructed from the parity-check matrices of array low-density parity-check codes, upper bounds on the termatiko distance equal to half the best known upper bound on the minimum distance are provided for column-weight at most 7, while for column-weight 3, the exact termatiko distance and its corresponding multiplicity are provided. Next, we show that adding redundant rows to the measurement matrix does not create new termatiko sets, but rather potentially removes termatiko sets and thus improves performance. An algorithm is provided to efficiently search for such redundant rows. Finally, we present numerical results for different specific measurement matrices and also for protograph-based ensembles of measurement matrices, as well as simulation results of IPA performance, showing the influence of small-size termatiko sets.

A new method is presented for low-complexity near-maximum-likelihood (ML) decoding of low-density parity-check (LDPC) codes over the additive white Gaussian noise channel. The proposed method termed belief-propagation-list erasure decoding (BP-LED) is based on erasing carefully chosen unreliable bits performed in case of BP decoding failure. A strategy of introducing erasures into the received vector and a new erasure decoding algorithm are proposed. The new erasure decoding algorithm, called list erasure decoding, combines ML decoding over the BEC with list decoding applied if the ML decoder fails to find a unique solution. The asymptotic exponent of the average list size for random regular LDPC codes from the Gallager ensemble is analyzed. Furthermore, a few examples of irregular quasi-cyclic LDPC as well as randomly constructed regular LDPC codes of short and moderate lengths are studied by simulations and their performance is compared to the tightened upper bound on the LDPC ensemble-average performance and the upper bound on the average performance of random linear codes under ML decoding. A comparison of the BP decoding and BP-LED performance of the WiMAX standard codes and performance of the near-ML BEAST decoding are presented. The new algorithm is applied to decoding a short nonbinary (NB) LDPC code over extensions of the binary Galois field. The obtained simulation results are compared to the tightened upper bound on the ensemble-average performance of the binary image of regular NB LDPC codes.

Stopping sets play a crucial role in failure events of iterative decoders over a binary erasure channel (BEC). The ℓth stopping redundancy is the minimum number of rows in the parity-check matrix of a code, which contains no stopping sets of size up to ℓ. In this paper, a notion of coverable stopping sets is defined. In order to achieve maximum-likelihood performance under iterative decoding over the BEC, the parity-check matrix should contain no coverable stopping sets of size ℓ, for 1 ≤ ℓ ≤ n-k, where n is the code length, k is the code dimension. By estimating the number of coverable stopping sets, we obtain upper bounds on the ℓth stopping redundancy, 1 ≤ ℓ ≤ n-k. The bounds are derived for both specific codes and code ensembles. In the range 1 ≤ ℓ ≤ d-1, for specific codes, the new bounds improve on the results in the literature. Numerical calculations are also presented.

A new decoding algorithm for LDPC codes on the AWGN channel is proposed. The algorithm is based on the idea of using redundant parity checks and additional variable nodes. The new key element in the proposed algorithm is the use of the orthogonal subsets of parity checks for computing soft decisions for different variable nodes. This allows for significant improvement in the decoding error performance of the algorithm compared to the known counterparts. Furthermore, new bounds on the error performance of the BP decoding applied to the parity-check matrices with redundant parity-checks are obtained.

The exact values of finite length average weight distributions for both binary ensembles and binary images of nonbinary ensembles of regular LDPC codes are computed. The exact average stopping set size distribution for the binary ensemble is also obtained. The computed spectra are applied in order to bound from above the average stopping redundancy of the ensemble of binary regular LDPC codes. The asymptotic typical normalized minimum distances for the binary image of the ensemble of nonbinary regular LDPC codes and the typical minimum stopping distances for the binary regular LDPC codes are also presented.

A novel method for decoding of low-density parity-check codes on the AWGN channel is presented. In the proposed method, first, a standard belief-propagation decoder is applied, then a certain number of positions is erased using a combination of a reliability criterion and a set of masks. A list erasure decoder is then applied to the resulting word. The performance of the proposed method is analyzed mathematically and demonstrated by simulations.

The l-th stopping redundancy ρι(C) of the binary [n, k, d] code C, 1 ≤ l ≤ d, is defined as the minimum number of rows in the parity-check matrix of C, such that the smallest stopping set is of size at least l. The stopping redundancy ρ(C) is defined as ρd(C). In this work, we improve on the probabilistic analysis of stopping redundancy, proposed by Han, Siegel and Vardy, which yields the best bounds known today. In our approach, we judiciously select the first few rows in the parity-check matrix, and then continue with the probabilistic method. By using similar techniques, we improve also on the best known bounds on ρι(C), for 1 ≤ l ≤ d. Our approach is compared to the existing methods by numerical computations.