Parameter-efficient fine-tuning (PEFT) has become a popular way to adapt large pre-trained models to new tasks. Most PEFT methods update only a small subset of parameters while freezing the rest, avoiding redundant computation. As they maximize the absolute size of the updates without regard to the parameters’ original scale, the resulting changes in model behavior can be minimal. In contrast, we maximize updates relative to each parameter’s scale, yielding more meaningful downstream adaptation. We propose Gradient-to-Weight Ratio and Entropy-guided Masking (GEM), a parameter scale-aware, distribution-sensitive sparse fine-tuning framework. GEM prioritizes parameters whose updates are significant in proportion to their initial pre-trained values. It also adaptively determines how many parameters to tune at each layer based on the entropy of parameter values, thereby making the most effective use of the computational budget in PEFT. Our empirical study demonstrates the efficacy of GEM on both general-domain tasks (GLUE and SuperGLUE) and domain-specific tasks (GSM8k and MBPP), achieving up to a 1.6% improvement in fine-tuning accuracy over full fine-tuning while updating only 0.1% of model parameters.

Yavuz Faruk Bakman, Duygu Nur Yaldiz, Sungmin Kang, Tuo Zhang, Baturalp Buyukates, Salman Avestimehr, Sai Praneeth Karimireddy. Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2025.

Large Language Models (LLMs) are currently pre-trained and fine-tuned on large cloud servers.The next frontier is LLM personalization, where a foundation model can be finetuned with user/task-specific data.Given the sensitive nature of such private data, it is desirable to fine-tune these models on edge devices to improve user trust.However, finetuning on resource-constrained edge devices presents significant challenges due to substantial memory and computational demands, as well as limited infrastructure support.We observe that inference engines (e.g., ExecuTorch) can be repurposed for fine-tuning by leveraging zeroth-order (ZO) optimization, which uses multiple forward passes to approximate gradients.While promising, direct application of ZO methods on edge devices is inefficient due to the high computational cost of multiple forward passes required for accurate gradient estimation, and their deployment has been largely unexplored in practice.We introduce MobiZO, a resource-efficient fine-tuning framework for LLMs specifically designed for edge devices.MobiZO combines three key innovations: (1) a parallelized randomized gradient estimator that employs both outer-loop and innerloop parallelism to eliminate sequential forward passes, (2) a specialized Multi-Perturbed LoRA (MP-LoRA) module that enables efficient realization of both inner and outer loop parallelism, and (3) a seamless integration with ExecuTorch for on-device training, requiring no modifications to the runtime.Experiments demonstrate that MobiZO achieves substantial runtime speedups and memory savings while improving fine-tuning accuracy, paving the way for practical deployment of LLMs in realtime, on-device applications.Code available at

Image geolocalization-the task of determining an image's geographic origin-poses significant challenges, largely due to visual similarities across disparate locations and the large search space. To address these issues, we propose a hierarchical sequence prediction approach inspired by how humans narrow down locations from broad regions (e.g., country) to specific addresses (e.g., street name and house number). Analogously, our model predicts geographic tokens hierarchically, first identifying a general region and then sequentially refining predictions to increasingly precise locations. Rather than relying on explicit semantic partitions (e.g., country, city), our method uses S2 cells, a nested, multiresolution global grid, and sequentially predicts finer-level cells conditioned on visual inputs and previous predictions. This procedure mirrors autoregressive text generation in large language models. Much like in language modeling, final performance depends not only on training but also on inference-time strategy. We investigate multiple top-down traversal methods for autoregressive sampling, incorporating techniques from test-time compute scaling used in language models. Specifically, we integrate beam search and multi-sample inference while exploring various selection strategies to determine the final output. This approach enables the model to manage uncertainty by exploring multiple plausible paths through the hierarchy. We evaluate our method on the Im2GPS3k and YFCC4k datasets against two distinct sets of baselines: those that operate without a Multimodal Large Language Model (MLLM) and those that leverage one. In the MLLM-free setting, our model surpasses other comparable baselines on nearly all metrics, achieving state-of-the-art performance with accuracy gains of up to 13.9%. When augmented with an MLLM, our model again outperforms all baselines, setting a new state of the art across every metric. The source code is available at https://github.com/NNargesNN/GeoToken.

Deep Learning has facilitated various high-stakes applications such as crime detection, urban planning, drug discovery, and healthcare. Its continuous success hinges on learning from massive data in miscellaneous sources, ranging from data with independent distributions to graph-structured data capturing intricate inter-sample relationships. Scaling up the data access requires global collaboration from distributed data owners. Yet, centralizing all data sources to an untrustworthy centralized server will put users' data at risk of privacy leakage or regulation violation. Federated Learning (FL) is a de facto decentralized learning framework that enables knowledge aggregation from distributed users without exposing private data. Though promising advances are witnessed for FL, new challenges are emerging when integrating FL with the rising needs and opportunities in data mining, graph analytics, foundation models, generative AI, and new interdisciplinary applications in science. By hosting this workshop, we aim to attract a broad range of audiences, including researchers and practitioners from academia and industry interested in the emergent challenges in FL. As an effort to advance the fundamental development of FL, this workshop will encourage ideas exchange on the trustworthiness, scalability, and robustness of distributed data mining and graph analytics and their emergent challenges.

Designing analog circuits from performance specifications is a complex, multi-stage process encompassing topology selection, parameter inference, and layout feasibility. We introduce FALCON, a unified machine learning framework that enables fully automated, specification-driven analog circuit synthesis through topology selection and layout-constrained optimization. Given a target performance, FALCON first selects an appropriate circuit topology using a performance-driven classifier guided by human design heuristics. Next, it employs a custom, edge-centric graph neural network trained to map circuit topology and parameters to performance, enabling gradient-based parameter inference through the learned forward model. This inference is guided by a differentiable layout cost, derived from analytical equations capturing parasitic and frequency-dependent effects, and constrained by design rules. We train and evaluate FALCON on a large-scale custom dataset of 1M analog mm-wave circuits, generated and simulated using Cadence Spectre across 20 expert-designed topologies. Through this evaluation, FALCON demonstrates >99\% accuracy in topology inference, <10\% relative error in performance prediction, and efficient layout-aware design that completes in under 1 second per instance. Together, these results position FALCON as a practical and extensible foundation model for end-to-end analog circuit design automation.

Multimodal Federated Learning frequently encounters challenges of client modality heterogeneity, leading to undesired performances for secondary modality in multimodal learning. It is particularly prevalent in audiovisual learning, with audio is often assumed to be the weaker modality in recognition tasks. To address this challenge, we introduce ModalityMirror to improve audio model performance by leveraging knowledge distillation from an audiovisual federated learning model. ModalityMirror involves two phases: a modality-wise FL stage to aggregate unimodal encoders; and a federated knowledge distillation stage on multimodality clients to train a unimodal student model. Our results demonstrate that ModalityMirror significantly improves the audio classification compared to the state-of-the-art FL methods such as Harmony, particularly in audiovisual FL facing video missing. Our approach unlocks the potential for exploiting the diverse modality spectrum inherent in multimodal FL.

Graphs are crucial for modeling relational and biological data. As datasets grow larger in real-world scenarios, the risk of exposing sensitive information increases, making privacy-preserving training methods like federated learning (FL) essential to ensure data security and compliance with privacy regulations. Recently proposed personalized subgraph FL methods have become the de-facto standard for training personalized Graph Neural Networks (GNNs) in a federated manner while dealing with the missing links across clients’ subgraphs due to privacy restrictions. However, personalized subgraph FL faces significant challenges due to the heterogeneity in client subgraphs, such as degree distributions among the nodes, which complicate federated training of graph models. To address these challenges, we propose FedGrAINS, a novel data-adaptive and sampling-based regularization method for subgraph FL. FedGrAINS leverages generative flow networks (GFlowNets) to evaluate node importance concerning clients’ tasks, dynamically adjusting the message-passing step in clients’ GNNs. This adaptation reflects task-optimized sampling aligned with a trajectory balance objective. Experimental results demonstrate that the inclusion of FedGrAINS as a regularizer consistently improves the FL performance compared to baselines that do not leverage such regularization.

Yavuz Faruk Bakman, Duygu Nur Yaldiz, Baturalp Buyukates, Chenyang Tao, Dimitrios Dimitriadis, Salman Avestimehr. Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2024.

Data privacy is of great concern in cloud machine-learning service platforms, when sensitive data are exposed to service providers. While private computing environments (e.g., secure enclaves), and cryptographic approaches (e.g., homomorphic encryption) provide strong privacy protection, their computing performance still falls short compared to cloud GPUs. To achieve privacy protection with high computing performance, we propose Delta, a new private training and inference framework, with comparable model performance as non-private centralized training. Delta features two asymmetric data flows: the main information-sensitive flow and the residual flow. The main part flows into a small model while the residuals are offloaded to a large model. Specifically, Delta embeds the information-sensitive representations into a low-dimensional space while pushing the information-insensitive part into high-dimension residuals. To ensure privacy protection, the low-dimensional information-sensitive part is secured and fed to a small model in a private environment. On the other hand, the residual part is sent to fast cloud GPUs, and processed by a large model. To further enhance privacy and reduce the communication cost, Delta applies a random binary quantization technique along with a DP-based technique to the residuals before sharing them with the public platform. We theoretically show that Delta guarantees differential privacy in the public environment and greatly reduces the complexity in the private environment. We conduct empirical analyses on CIFAR-10, CIFAR-100 and ImageNet datasets and ResNet-18 and ResNet-34, showing that Delta achieves strong privacy protection, fast training, and inference without significantly compromising the model utility.

Federated Learning (FL) has gained significant attraction due to its ability to enable privacy-preserving training over decentralized data. Current literature in FL mostly focuses on single-task learning. However, over time, new tasks may appear in the clients and the global model should learn these tasks without forgetting previous tasks. This real-world scenario is known as Continual Federated Learning (CFL). The main challenge of CFL is \textit{Global Catastrophic Forgetting}, which corresponds to the fact that when the global model is trained on new tasks, its performance on old tasks decreases. There have been a few recent works on CFL to propose methods that aim to address the global catastrophic forgetting problem. However, these works either have unrealistic assumptions on the availability of past data samples or violate the privacy principles of FL. We propose a novel method, Federated Orthogonal Training (FOT), to overcome these drawbacks and address the global catastrophic forgetting in CFL. Our algorithm extracts the global input subspace of each layer for old tasks and modifies the aggregated updates of new tasks such that they are orthogonal to the global principal subspace of old tasks for each layer. This decreases the interference between tasks, which is the main cause for forgetting. Our method is almost computation-free on the client side and has negligible communication cost. We empirically show that FOT outperforms state-of-the-art continual learning methods in the CFL setting, achieving an average accuracy gain of up to 15% with 27% lower forgetting while only incurring a minimal computation and communication cost. Code can be found [here ](https://github.com/duygunuryldz/Federated_Orthogonal_Training)

Generative Large Language Models (LLMs) have recently been widely utilized for their unprecedented capabil-ities across many tasks. Considering their use in high-stakes environments and for mission-critical applications, the fact that LLMs often can generate inaccurate or misleading results can be potentially harmful, which motivates us to study the correctness of generative LLM outputs. Uncertainty Estimation (UE) in generative LLMs is a developing area, with state-of-the-art probability-based techniques frequently using length-normalized scoring. As an alternative to length-normalized scoring in UE, in this work, we propose Meaning-Aware Response Scoring (MARS). The key idea of MARS is to consider the semantic contribution of each token of the generated sequence to the context of the question during UE. Through extensive experiments on three question-answering datasets across five pretrained LLMs, we show that utilizing MARS during UE results in a universal and significant improvement in UE performance.

Diffusion models have played a crucial role in the recent advancements in generative image modeling. These models are characterized by a forward process that incrementally corrupts images. The modeling objective is to develop a reverse process capable of reconstructing the original image from degraded inputs so that the trained model can then be leveraged to generate natural images from pure noise. In this work, we introduce a novel diffusion process that operates in the frequency domain. Typically, the frequency domain representation of an image exhibits a sparse structure, with energy predominantly concentrated in low frequency components. This inherent sparsity aids us in the effective separation of signal and noise during the reverse process. We utilize this property to introduce a scale-dependent noise schedule, offering precise control over various image scales. Working in the frequency domain allows us to modify the training protocol, resulting in significant computation enhancements, achieving a speedup of 2.7-8.5 x without a significant drop in generated image quality, compared to the image domain models, which operate with fixed noise schedules.

This paper introduces FedSecurity, an end-to-end benchmark that serves as a supplementary component of the FedML library for simulating adversarial attacks and corresponding defense mechanisms in Federated Learning (FL). FedSecurity eliminates the need for implementing the fundamental FL procedures, e.g., FL training and data loading, from scratch, thus enables users to focus on developing their own attack and defense strategies. It contains two key components, including FedAttacker that conducts a variety of attacks during FL training, and FedDefender that implements defensive mechanisms to counteract these attacks. FedSecurity has the following features: i) It offers extensive customization options to accommodate a broad range of machine learning models (e.g., Logistic Regression, ResNet, and GAN) and FL optimizers (e.g., FedAVG, FedOPT, and FedNOVA); ii) it enables exploring the effectiveness of attacks and defenses across different datasets and models; and iii) it supports flexible configuration and customization through a configuration file and some APIs. We further demonstrate FedSecurity's utility and adaptability through federated training of Large Language Models (LLMs) to showcase its potential on a wide range of complex applications.

Deep Learning has facilitated various high-stakes applications such as crime detection, urban planning, drug discovery, and healthcare. Its continuous success hinges on learning from massive data in miscellaneous sources, ranging from data with independent distributions to graph-structured data capturing intricate inter-sample relationships. Scaling up the data access requires global collaboration from distributed data owners. Yet, centralizing all data sources to an untrustworthy centralized server will put users' data at risk of privacy leakage or regulation violation. Federated Learning (FL) is a de facto decentralized learning framework that enables knowledge aggregation from distributed users without exposing private data. Though promising advances are witnessed for FL, new challenges are emerging when integrating FL with the rising needs and opportunities in data mining, graph analytics, foundation models, generative AI, and new interdisciplinary applications in science. By hosting this workshop, we aim to attract a broad range of audiences, including researchers and practitioners from academia and industry interested in the emergent challenges in FL. As an effort to advance the fundamental development of FL, this workshop will encourage ideas exchange on the trustworthiness, scalability, and robustness of distributed data mining and graph analytics and their emergent challenges.

Federated learning was introduced to enable machine learning over large decentralized datasets while promising privacy by eliminating the need for data sharing. Despite this, prior work has shown that shared gradients often contain private information and attackers can gain knowledge either through malicious modification of the architecture and parameters or by using optimization to approximate user data from the shared gradients.However, prior data reconstruction attacks have been limited in setting and scale, as most works target FedSGD and limit the attack to single-client gradients. Many of these attacks fail in the more practical setting of FedAVG or if updates are aggregated together using secure aggregation. Data reconstruction becomes significantly more difficult, resulting in limited attack scale and/or decreased reconstruction quality. When both FedAVG and secure aggregation are used, there is no current method that is able to attack multiple clients concurrently in a federated learning setting.In this work we introduce Loki, an attack that overcomes previous limitations and also breaks the anonymity of aggregation as the leaked data is identifiable and directly tied back to the clients they come from. Our design sends clients customized convolutional parameters, and the weight gradients of data points between clients remain separate even through aggregation. With FedAVG and aggregation across 100 clients, prior work can leak less than 1% of images on MNIST, CIFAR-100, and Tiny ImageNet. Using only a single training round, Loki is able to leak 76-86% of all data samples.

Training machine learning models on data from multiple entities without direct data sharing can unlock applications otherwise hindered by business, legal, or ethical constraints. In this work, we design and implement new privacy-preserving machine learning protocols for logistic regression and neural network models. We adopt a two-server model where data owners secret-share their data between two servers that train and evaluate the model on the joint data. A significant source of inefficiency and inaccuracy in existing methods arises from using Yao’s garbled circuits to compute non-linear activation functions. We propose new methods for computing non-linear functions based on secret-shared lookup tables, offering both computational efficiency and improved accuracy. Beyond introducing leakage-free techniques, we initiate the exploration of relaxed security measures for privacy-preserving machine learning. Instead of claiming that the servers gain no knowledge during the computation, we contend that while some information is revealed about access patterns to lookup tables, it maintains epsilon-dX-privacy. Leveraging this relaxation significantly reduces the computational resources needed for training. We present new cryptographic protocols tailored to this relaxed security paradigm and define and analyze the leakage. Our evaluations show that our logistic regression protocol is up to 9x faster, and the neural network training is up to 688x faster than SecureML. Notably, our neural network achieves an accuracy of 96.6% on MNIST in 15 epochs, outperforming prior benchmarks that capped at 93.4% using the same architecture.

Graph neural networks (GNNs) play a key role in learning representations from graph-structured data and are demonstrated to be useful in many applications. However, the GNN training pipeline has been shown to be vulnerable to node feature leakage and edge extraction attacks. This paper investigates a scenario where an attacker aims to recover private edge information from a trained GNN model. Previous studies have employed differential privacy (DP) to add noise directly to the adjacency matrix or a compact graph representation. The added perturbations cause the graph structure to be substantially morphed, reducing the model utility. We propose a new privacy-preserving GNN training algorithm, Eclipse, that maintains good model utility while providing strong privacy protection on edges. Eclipse is based on two key observations. First, adjacency matrices in graph structures exhibit low-rank behavior. Thus, Eclipse trains GNNs with a low-rank format of the graph via singular values decomposition (SVD), rather than the original graph. Using the low-rank format, Eclipse preserves the primary graph topology and removes the remaining residual edges. Eclipse adds noise to the low-rank singular values instead of the entire graph, thereby preserving the graph privacy while still maintaining enough of the graph structure to maintain model utility. We theoretically show Eclipse provide formal DP guarantee on edges. Experiments on benchmark graph datasets show that Eclipse achieves significantly better privacy-utility tradeoff compared to existing privacy-preserving GNN training methods. In particular, under strong privacy constraints (𝜖 < 4), Eclipse shows significant gains in the model utility by up to 46%. We further demonstrate that Eclipse also has better resilience against common edge attacks (e.g., LPA), lowering the attack AUC by up to 5% compared to other state-of-the-art baselines.

In Federated Learning (FL), clients may have weak devices that cannot train the full model or even hold it in their memory space. To implement large-scale FL applications, thus, it is crucial to develop a distributed learning method that enables the participation of such weak clients. We proposeEmbracingFL, a general FL framework that allows all available clients to join the distributed training regardless of their system resource capacity. The framework is built upon a novel form of partial model training method in which each client trains as many consecutive output-side layers as its system resources allow. Our study demonstrates thatEmbracingFLencourages each layer to have similar data representations across clients, improving FL efficiency. The proposed partial model training method guarantees convergence to a neighbor of stationary points for non-convex and smooth problems. We evaluate the efficacy ofEmbracingFLunder a variety of settings with a mixed number of strong, moderate ($\sim 40\%$memory), and weak ($\sim 15\%$memory) clients, datasets (CIFAR-10, FEMNIST, and IMDB), and models (ResNet20, CNN, and LSTM). Our empirical study shows thatEmbracingFLconsistently achieves high accuracy as like all clients are strong, outperforming the state-of-the-art width reduction methods (i.e. HeteroFL and FjORD).

Training ML models which are fair across different demographic groups is of critical importance due to the increased integration of ML in crucial decision-making scenarios such as healthcare and recruitment. Federated learning has been viewed as a promising solution for collaboratively training machine learning models among multiple parties while maintaining their local data privacy. However, federated learning also poses new challenges in mitigating the potential bias against certain populations (e.g., demographic groups), as this typically requires centralized access to the sensitive information (e.g., race, gender) of each datapoint. Motivated by the importance and challenges of group fairness in federated learning, in this work, we propose FairFed, a novel algorithm for fairness-aware aggregation to enhance group fairness in federated learning. Our proposed approach is server-side and agnostic to the applied local debiasing thus allowing for flexible use of different local debiasing methods across clients. We evaluate FairFed empirically versus common baselines for fair ML and federated learning and demonstrate that it provides fairer models, particularly under highly heterogeneous data distributions across clients. We also demonstrate the benefits of FairFed in scenarios involving naturally distributed real-life data collected from different geographical locations or departments within an organization.

In Federated Learning (FL), a common approach for aggregating local solutions across clients is periodic full model averaging. It is, however, known that different layers of neural networks can have a different degree of model discrepancy across the clients. The conventional full aggregation scheme does not consider such a difference and synchronizes the whole model parameters at once, resulting in inefficient network bandwidth consumption. Aggregating the parameters that are similar across the clients does not make meaningful training progress while increasing the communication cost. We propose FedLAMA, a layer-wise adaptive model aggregation scheme for scalable FL. FedLAMA adjusts the aggregation interval in a layer-wise manner, jointly considering the model discrepancy and the communication cost. This fine-grained aggregation strategy enables to reduce the communication cost without significantly harming the model accuracy. Our extensive empirical study shows that, as the aggregation interval increases, FedLAMA shows a remarkably smaller accuracy drop than the periodic full aggregation, while achieving comparable communication efficiency.

Secure aggregation is a critical component in federated learning (FL), which enables the server to learn the aggregate model of the users without observing their local models. Conventionally, secure aggregation algorithms focus only on ensuring the privacy of individual users in a single training round. We contend that such designs can lead to significant privacy leakages over multiple training rounds, due to partial user selection/participation at each round of FL. In fact, we show that the conventional random user selection strategies in FL lead to leaking users' individual models within number of rounds that is linear in the number of users. To address this challenge, we introduce a secure aggregation framework, Multi-RoundSecAgg, with multi-round privacy guarantees. In particular, we introduce a new metric to quantify the privacy guarantees of FL over multiple training rounds, and develop a structured user selection strategy that guarantees the long-term privacy of each user (over any number of training rounds). Our framework also carefully accounts for the fairness and the average number of participating users at each round. Our experiments on MNIST, CIFAR-10 and CIFAR-100 datasets in the IID and the non-IID settings demonstrate the performance improvement over the baselines, both in terms of privacy protection and test accuracy.

Secure aggregation promises a heightened level of privacy in federated learning, maintaining that a server only has access to a decrypted aggregate update. Within this setting, linear layer leakage methods are the only data reconstruction attacks able to scale and achieve a high leakage rate regardless of the number of clients or batch size. This is done through increasing the size of an injected fully-connected (FC) layer. However, this results in a resource overhead which grows larger with an increasing number of clients. We show that this resource overhead is caused by an incorrect perspective in all prior work that treats an attack on an aggregate update in the same way as an individual update with a larger batch size. Instead, by attacking the update from the perspective that aggregation is combining multiple individual updates, this allows the application of sparsity to alleviate resource overhead. We show that the use of sparsity can decrease the model size overhead by over 327x and the computation time by 3.34x compared to SOTA while maintaining equivalent total leakage rate, 77% even with 1000 clients in aggregation.

The deployment of Federated Learning (FL) systems poses various challenges such as data heterogeneity and communication efficiency. We focus on a practical FL setup that has recently drawn attention, where the data distribution on each device is not static but dynamically evolves over time. This setup, referred to as Continual Federated Learning (CFL), suffers from catastrophic forgetting, i.e., the undesired forgetting of previous knowledge after learning on new data, an issue not encountered with vanilla FL. In this work, we formally quantify catastrophic forgetting in a CFL setup, establish links to training optimization and evaluate different episodic replay approaches for CFL on a large scale real-world NLP dataset. To the best of our knowledge, this is the first such study of episodic replay for CFL. We show that storing a small set of past data boosts performance and significantly reduce forgetting, providing evidence that carefully designed sampling strategies can lead to further improvements.

Federated learning (FL) has gained substantial attention in recent years due to data privacy concerns related to the pervasiveness of consumer devices that continuously collect data from users. While a number of FL benchmarks have been developed to facilitate FL research, none of them include audio data and audio-related tasks. In this paper, we fill this critical gap by introducing a new FL benchmark for audio tasks which we refer to as FedAudio. FedAudio includes four representative and commonly used audio datasets from three important audio tasks that are well aligned with FL use cases. In particular, a unique contribution of FedAudio is the introduction of data noises and label errors to the datasets to emulate challenges when deploying FL systems in real-world settings. FedAudio also includes the benchmark results of the datasets and a PyTorch library with the objective of facilitating researchers to fairly compare their algorithms. We hope FedAudio could act as a catalyst to inspire new FL research for audio tasks and thus benefit the acoustic and speech research community. The datasets and benchmark results can be accessed at https://github.com/zhang-tuo-pdf/FedAudio.

Over the past few years, Federated Learning (FL) has become an emerging machine learning technique to tackle data privacy challenges through collaborative training. In the Federated Learning algorithm, the clients submit a locally trained model, and the server aggregates these parameters until convergence. Despite significant efforts that have been made to FL in fields like computer vision, audio, and natural language processing, the FL applications utilizing multimodal data streams remain largely unexplored. It is known that multimodal learning has broad real-world applications in emotion recognition, healthcare, multimedia, and social media, while user privacy persists as a critical concern. Specifically, there are no existing FL benchmarks targeting multimodal applications or related tasks. In order to facilitate the research in multimodal FL, we introduce FedMultimodal, the first FL benchmark for multimodal learning covering five representative multimodal applications from ten commonly used datasets with a total of eight unique modalities. FedMultimodal offers a systematic FL pipeline, enabling end-to-end modeling framework ranging from data partition and feature extraction to FL benchmark algorithms and model evaluation. Unlike existing FL benchmarks, FedMultimodal provides a standardized approach to assess the robustness of FL against three common data corruptions in real-life multimodal applications: missing modalities, missing labels, and erroneous labels. We hope that FedMultimodal can accelerate numerous future research directions, including designing multimodal FL algorithms toward extreme data heterogeneity, robustness multimodal FL, and efficient multimodal FL. The datasets and benchmark results can be accessed at: https://github.com/usc-sail/fed-multimodal.

Deep learning models often suffer from forgetting previously learned information when trained on new data. This problem is exacerbated in federated learning (FL), where the data is distributed and can change independently for each user. Many solutions are proposed to resolve this catastrophic forgetting in a centralized setting. However, they do not apply directly to FL because of its unique complexities, such as privacy concerns and resource limitations. To overcome these challenges, this paper presents a framework for \textbf{federated class incremental learning} that utilizes a generative model to synthesize samples from past distributions. This data can be later exploited alongside the training data to mitigate catastrophic forgetting. To preserve privacy, the generative model is trained on the server using data-free methods at the end of each task without requesting data from clients. Moreover, our solution does not demand the users to store old data or models, which gives them the freedom to join/leave the training at any time. Additionally, we introduce SuperImageNet, a new regrouping of the ImageNet dataset specifically tailored for federated continual learning. We demonstrate significant improvements compared to existing baselines through extensive experiments on multiple datasets.

Federated learning (FL) has attracted growing interest for enabling privacy-preserving machine learning on data stored at multiple users while avoiding moving the data off-device. However, while data never leaves users’ devices, privacy still cannot be guaranteed since significant computations on users’ training data are shared in the form of trained local models. These local models have recently been shown to pose a substantial privacy threat through different privacy attacks such as model inversion attacks. As a remedy, Secure Aggregation (SA) has been developed as a framework to preserve privacy in FL, by guaranteeing the server can only learn the global aggregated model update but not the individual model updates.While SA ensures no additional information is leaked about the individual model update beyond the aggregated model update, there are no formal guarantees on how much privacy FL with SA can actually offer; as information about the individual dataset can still potentially leak through the aggregated model computed at the server. In this work, we perform a first analysis of the formal privacy guarantees for FL with SA. Specifically, we use Mutual Information (MI) as a quantification metric and derive upper bounds on how much information about each user's dataset can leak through the aggregated model update. When using the FedSGD aggregation algorithm, our theoretical bounds show that the amount of privacy leakage reduces linearly with the number of users participating in FL with SA. To validate our theoretical bounds, we use an MI Neural Estimator to empirically evaluate the privacy leakage under different FL setups on both the MNIST and CIFAR10 datasets. Our experiments verify our theoretical bounds for FedSGD, which show a reduction in privacy leakage as the number of users and local batch size grow, and an increase in privacy leakage as the number of training rounds increases. We also observe similar dependencies for the FedAvg and FedProx protocol.

Multi-institutional efforts can facilitate training of deep MRI reconstruction models, albeit privacy risks arise during cross-site sharing of imaging data. Federated learning (FL) has recently been introduced to address privacy concerns by enabling distributed training without transfer of imaging data. Existing FL methods employ conditional reconstruction models to map from undersampled to fully-sampled acquisitions via explicit knowledge of the accelerated imaging operator. Since conditional models generalize poorly across different acceleration rates or sampling densities, imaging operators must be fixed between training and testing, and they are typically matched across sites. To improve patient privacy, performance and flexibility in multi-site collaborations, here we introduce Federated learning of Generative IMage Priors (FedGIMP) for MRI reconstruction. FedGIMP leverages a two-stage approach: cross-site learning of a generative MRI prior, and prior adaptation following injection of the imaging operator. The global MRI prior is learned via an unconditional adversarial model that synthesizes high-quality MR images based on latent variables. A novel mapper subnetwork produces site-specific latents to maintain specificity in the prior. During inference, the prior is first combined with subject-specific imaging operators to enable reconstruction, and it is then adapted to individual cross-sections by minimizing a data-consistency loss. Comprehensive experiments on multi-institutional datasets clearly demonstrate enhanced performance of FedGIMP against both centralized and FL methods based on conditional models.

Graph Neural Networks (GNNs) are the first choice methods for graph machine learning problems thanks to their ability to learn state-of-the-art level representations from graph-structured data. However, centralizing a massive amount of real-world graph data for GNN training is prohibitive due to user-side privacy concerns, regulation restrictions, and commercial competition. Federated Learning is the de-facto standard for collaborative training of machine learning models over many distributed edge devices without the need for centralization. Nevertheless, training graph neural networks in a federated setting is vaguely defined and brings statistical and systems challenges. This work proposes SpreadGNN, a novel multi-task federated training framework capable of operating in the presence of partial labels and absence of a central server for the first time in the literature. We provide convergence guarantees and empirically demonstrate the efficacy of our framework on a variety of non-I.I.D. distributed graph-level molecular property prediction datasets with partial labels. Our results show that SpreadGNN outperforms GNN models trained over a central server-dependent federated learning system, even in constrained topologies.

Due to the surge of cloud-assisted AI services, the problem of designing resilient prediction serving systems that can effectively cope with stragglers and minimize response delays has attracted much interest. The common approach for tackling this problem is replication which assigns the same prediction task to multiple workers. This approach, however, is inefficient and incurs significant resource overheads. Hence, a learning-based approach known as parity model (ParM) has been recently proposed which learns models that can generate ``parities’’ for a group of predictions to reconstruct the predictions of the slow/failed workers. While this learning-based approach is more resource-efficient than replication, it is tailored to the specific model hosted by the cloud and is particularly suitable for a small number of queries (typically less than four) and tolerating very few stragglers (mostly one). Moreover, ParM does not handle Byzantine adversarial workers. We propose a different approach, named Approximate Coded Inference (ApproxIFER), that does not require training any parity models, hence it is agnostic to the model hosted by the cloud and can be readily applied to different data domains and model architectures. Compared with earlier works, ApproxIFER can handle a general number of stragglers and scales significantly better with the number of queries. Furthermore, ApproxIFER is robust against Byzantine workers. Our extensive experiments on a large number of datasets and model architectures show significant degraded mode accuracy improvement by up to 58% over ParM.

Private set intersection (PSI) is a popular protocol that allows multiple parties to evaluate the intersection of their sets without revealing them to each other. PSI has numerous practical applications, including privacy preserving data mining and location-based services. In this work, we develop a new approach for the PSI problem within the federated analytics framework. In particular, we consider a setting where a server wants to determine (query) which among its local set of data identifiers appears coupled with the same value in at least K of the N parties. Applications for this framework include but are not limited to: double-filing insurance verification, credit scoring and password checkup on an institutional level. To address the proposed setting, we propose a new protocol Fed-K-PSI that allows the server to answer this query while being oblivious to the data of identifiers that do not satisfy the distributed query at the parties. In addition, Fed-K-PSI also maintains the anonymity of the parties by hiding which K parties satisfied the query, or which value associated with the identifier which caused the query to be successful. Our proposed setting does not lend itself directly to state-of-the-art approaches in PSI based on Oblivious Transfer, since the server does not have a complete representation of a datapoint (only the identifier, but no value). Our proposed approach tackles this problem by constructing a distributed function at the parties, which encodes the datapoints and returns a deterministic known property if and only if the value for a given identifier is the same in at least K of the N parties. We show that Fed-K-PSI achieves a strong information-theoretic privacy guarantee and is resilient to collusion scenarios among honest-but-curious parties. We also evaluate Fed-K-PSI via extensive experiments to study the effect of the different system parameters.

The field of graph data mining, one of the most important AI research areas, has been revolutionized by graph neural networks (GNNs), which benefit from training on real-world graph data with millions to billions of nodes and links. Unfortunately, the training data and process of GNNs involving graphs beyond millions of nodes are extremely costly on a centralized server, if not impossible. Moreover, due to the increasing concerns about data privacy, emerging data from realistic applications are naturally fragmented, forming distributed private graphs of multiple ''data silos", among which direct transferring of data is forbidden. The nascent field of federated learning (FL), which aims to enable individual clients to jointly train their models while keeping their local data decentralized and completely private, is a promising paradigm for large-scale distributed and private training of GNNs. øurs aims to bring together researchers from different backgrounds with a common interest in how to extend current FL algorithms to operate with graph data models such as GNNs. FL is an extremely hot topic of large commercial interest and has been intensively explored for machine learning with visual and textual data. The exploration from graph mining researchers and industrial practitioners is timely catching up just recently. There are many unexplored challenges and opportunities, which urges the establishment of an organized and open community to collaboratively advance the science behind it. The prospective participants of this workshop will include researchers and practitioners from both graph mining and federated learning communities, whose interests include, but are not limited to: graph analysis and mining, heterogeneous network modeling, complex data mining, large-scale machine learning, distributed systems, optimization, meta-learning, reinforcement learning, privacy, robustness, explainability, fairness, ethics, and trustworthiness.

Federated learning (FL) has been developed as a promising framework to leverage the resources of edge devices, enhance customers’ privacy, comply with regulations, and reduce development costs. Although many methods and applications have been developed for FL, several critical challenges for practical FL systems remain unaddressed. This paper provides an outlook on FL development as part of the ICASSP 2022 special session entitled "Frontiers of Federated Learning: Applications, Challenges, and Opportunities." The outlook is categorized into five emerging directions of FL, namely algorithm foundation, personalization, hardware and security constraints, lifelong learning, and nonstandard data. Our unique perspectives are backed by practical observations from large-scale federated systems for edge devices.

Federated Learning (FL) applied to real world data may suffer from several idiosyncrasies. One such idiosyncrasy is the data distribution across devices. Data across devices could be distributed such that there are some "heavy devices" with large amounts of data while there are many "light users" with only a handful of data points. There also exists heterogeneity of data across devices. In this study, we evaluate the impact of such idiosyncrasies on Natural Language Understanding (NLU) models trained using FL. We conduct experiments on data obtained from a large scale NLU system serving thousands of devices and show that simple non-uniform device selection based on the number of interactions at each round of FL training boosts the performance of the model. This benefit is further amplified in continual FL on consecutive time periods, where non-uniform sampling manages to swiftly catch up with FL methods using all data at once.

Active learning aims to reduce the cost of labeling through selective sampling. Despite reported empirical success over passive learning, many popular active learning heuristics such as uncertainty sampling still lack satisfying theoretical guarantees. Towards closing the gap between practical use and theoretical understanding in active learning, we propose to characterize the exact behavior of uncertainty sampling for high-dimensional Gaussian mixture data, in a modern regime of big data where the numbers of samples and features are commensurately large. Through a sharp characterization of the learning results, our analysis sheds light on the important question of when uncertainty sampling works better than passive learning. Our results show that the effectiveness of uncertainty sampling is not always ensured. In fact it depends crucially on the choice of i) an adequate initial classifier used to start the active sampling process and ii) a proper loss function that allows an adaptive treatment of samples queried at various steps.

Federated Learning (FL) is an efficient distributed machine learning algorithm that promises to reduce data migration costs to a centralized repository, alleviate regulatory data restrictions and maintain data privacy. However, it suffers from data heterogeneity, i.e., data distribution across silos is often non-identical and independent (non-iid), making optimization difficult. Further, a significant but rarely studied challenge in FL is the lack of annotated data for training. This challenge is more pronounced in the medical field since data annotations require precision and are highly labor-intensive and time-consuming. That is why a few sites have minimal or no annotated data, which wastes valuable data resources for ML training. In this work, we investigate these two challenges of Federated Learning on a publicly available realistic federated medical dataset, KiTS19. First, we explore Federated Learning for Tumor Segmentation task on the Federated version of the KiTS19 dataset for the first time. We show that FL can maintain 96% of model accuracy compared to the centralized model accuracy with ten institution collaboration. In addition, we investigate the benefits of transfer learning to address the challenge of data heterogeneity and show that 5% accuracy improvement is achieved by using a pre-trained model in FL. Moreover, we propose a Federated semi-supervised learning (FSSL) framework to address the challenge of the lack of annotations at some silos. We show that unlabelled silos add 11% to the model’s efficiency compared with the model trained on labeled silos alone.

Stragglers, Byzantine workers, and data privacy are the main bottlenecks in distributed cloud computing. Some prior works proposed coded computing strategies to jointly address all three challenges. They require either a large number of workers, a significant communication cost or a significant computational complexity to tolerate Byzantine workers. Much of the overhead in prior schemes comes from the fact that they tightly couple coding for all three problems into a single framework. In this paper, we propose Adaptive Verifiable Coded Computing (AVCC) framework that decouples the Byzantine node detection challenge from the straggler tolerance. AVCC leverages coded computing just for handling stragglers and privacy, and then uses an orthogonal approach that leverages verifiable computing to mitigate Byzantine workers. Furthermore, AVCC dynamically adapts its coding scheme to trade-off straggler tolerance with Byzantine protection. We evaluate AVCC on a compute-intensive distributed logistic regression application. Our experiments show that AVCC achieves up to 4.2× speedup and up to 5.1% accuracy improvement over the state-of-the-art Lagrange coded computing approach (LCC). AVCC also speeds up the conventional uncoded implementation of distributed logistic regression by up to 7.6×, and improves the test accuracy by up to 12.1%.

Modern machine learning models require a large amount of labeled data for training to perform well. A recently emerging paradigm for reducing the reliance of large model training on massive labeled data is to take advantage of abundantly available labeled data from a related source task to boost the performance of the model in a desired target task where there may not be a lot of data available. This approach, which is called transfer learning, has been applied successfully in many application domains. However, despite the fact that many transfer learning algorithms have been developed, the fundamental understanding of "when" and "to what extent" transfer learning can reduce sample complexity is still limited. In this work, we take a step towards foundational understanding of transfer learning by focusing on binary classification with linear models and Gaussian features and develop statistical minimax lower bounds in terms of the number of source and target samples and an appropriate notion of similarity between source and target tasks. To derive this bound, we reduce the transfer learning problem to hypothesis testing via constructing a packing set of source and target parameters by exploiting Gilbert-Varshamov bound, which in turn leads to a lower bound on sample complexity. We also evaluate our theoretical results by experiments on real data sets.

Rahul Sharma, Anil Ramakrishna, Ansel MacLaughlin, Anna Rumshisky, Jimit Majmudar, Clement Chung, Salman Avestimehr, Rahul Gupta. Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. 2022.

In the context of personalized federated learning (FL), the critical challenge is to balance local model improvement and global model tuning when the personal and global objectives may not be exactly aligned. Inspired by Bayesian hierarchical models, we develop a self-aware personalized FL method where each client can automatically balance the training of its local personal model and the global model that implicitly contributes to other clients' training. Such a balance is derived from the inter-client and intra-client uncertainty quantification. A larger inter-client variation implies more personalization is needed. Correspondingly, our method uses uncertainty-driven local training steps an aggregation rule instead of conventional local fine-tuning and sample size-based aggregation. With experimental studies on synthetic data, Amazon Alexa audio data, and public datasets such as MNIST, FEMNIST, CIFAR10, and Sent140, we show that our proposed method can achieve significantly improved personalization performance compared with the existing counterparts.

Federated Learning (FL) is a novel approach enabling several clients holding sensitive data to collaboratively train machine learning models, without centralizing data. The cross-silo FL setting corresponds to the case of few ($2$--$50$) reliable clients, each holding medium to large datasets, and is typically found in applications such as healthcare, finance, or industry. While previous works have proposed representative datasets for cross-device FL, few realistic healthcare cross-silo FL datasets exist, thereby slowing algorithmic research in this critical application. In this work, we propose a novel cross-silo dataset suite focused on healthcare, FLamby (Federated Learning AMple Benchmark of Your cross-silo strategies), to bridge the gap between theory and practice of cross-silo FL.FLamby encompasses 7 healthcare datasets with natural splits, covering multiple tasks, modalities, and data volumes, each accompanied with baseline training code. As an illustration, we additionally benchmark standard FL algorithms on all datasets.Our flexible and modular suite allows researchers to easily download datasets, reproduce results and re-use the different components for their research. FLamby is available at~\url{www.github.com/owkin/flamby}.

Decentralized (i.e., serverless) training across edge nodes can suffer substantially from potential Byzantine nodes that can degrade the training performance. However, detection and mitigation of Byzantine behaviors in a decentralized learning setting is a daunting task, especially when the data distribution at the users is heterogeneous. As our main contribution, we proposeBasil, a fast and computationally efficient Byzantine-robust algorithm for decentralized training systems, which leverages a novel sequential, memory-assisted and performance-based criteria for training over a logical ring while filtering the Byzantine users. In the IID dataset setting, we provide the theoretical convergence guarantees ofBasil, demonstrating its linear convergence rate. Furthermore, for the IID setting, we experimentally demonstrate thatBasilis robust to various Byzantine attacks, including the strong Hidden attack, while providing up to absolute ~16% higher test accuracy over the state-of-the-art Byzantine-resilient decentralized learning approach. Additionally, we generalizeBasilto the non-IID setting by proposing Anonymous Cyclic Data Sharing (ACDS), a technique that allows each node to anonymously share a random fraction of its local non-sensitive dataset (e.g., landmarks images) with all other nodes. Finally, to reduce the overall latency ofBasilresulting from its sequential implementation over the logical ring, we proposeBasil+that enables Byzantine-robust parallel training across groups of logical rings, and at the same time, it retains the performance gains ofBasildue to sequential training within each group. Furthermore, we experimentally demonstrate the scalability gains ofBasil+through different sets of experiments.

The increasing prevalence of massive datasets makes the outsourcing of storage and computation tasks to distributed servers a necessity. This raises a number of concerns regarding the security and integrity of stored information, the privacy of accessing desired information, the communication overhead of distributed systems, the latency, reliability, and complexity of distributed computing, and privacy in distributed training and learning systems. Recent breakthroughs from coding, communication, and information-theoretic perspectives have opened up exciting new research avenues for these topics. There are many theoretical and practical open problems. This Special Issue is dedicated to communication theory, coding theory, information theory, signal processing, and networking aspects of privacy in information retrieval, privacy in coded computing over distributed servers, and privacy in distributed learning.

Most of our lives are conducted in the cyberspace. The human notion of privacy translates into a cyber notion of privacy on many functions that take place in the cyberspace. This article focuses on three such functions: how to privately retrieve information from cyberspace (privacy in information retrieval), how to privately leverage large-scale distributed/parallel processing (privacy in distributed computing), and how to learn/train machine learning models from private data spread across multiple users (privacy in distributed (federated) learning). The article motivates each privacy setting, describes the problem formulation, summarizes breakthrough results in the history of each problem, and gives recent results and discusses some of the major ideas that emerged in each field. In addition, the cross-cutting techniques and interconnections between the three topics are discussed along with a set of open problems and challenges.

Leveraging parallel hardware (e.g. GPUs) for deep neural network (DNN) training brings high computing performance. However, it raises data privacy concerns as GPUs lack a trusted environment to protect the data. Trusted execution environments (TEEs) have emerged as a promising solution to achieve privacypreserving learning. Unfortunately, TEEs’ limited computing power renders them not comparable to GPUs in performance. To improve the trade-off among privacy, computing performance, and model accuracy, we propose an asymmetric model decomposition framework, AsymML, to (1) accelerate training using parallel hardware; and (2) achieve a strong privacy guarantee using TEEs and differential privacy (DP) with much less accuracy compromised compared to DP-only methods. By exploiting the low-rank characteristics in training data and intermediate features, AsymML asymmetrically decomposes inputs and intermediate activations into low-rank and residual parts. With the decomposed data, the target DNN model is accordingly split into a trusted and an untrusted part. The trusted part performs computations on low-rank data, with low compute and memory costs. The untrusted part is fed with residuals perturbed by very small noise. Privacy, computing performance, and model accuracy are well managed by respectively delegating the trusted and the untrusted part to TEEs and GPUs. We provide a formal DP guarantee that demonstrates that, for the same privacy guarantee, combining asymmetric data decomposition and DP requires much smaller noise compared to solely using DP without decomposition. This improves the privacy-utility trade-off significantly compared to using only DP methods without decomposition. Furthermore, we present a rank bound analysis showing that the low-rank structure is preserved after each layer across the entire model. Our extensive evaluations on DNN models show that AsymML delivers 7.6× speedup in training compared to the TEE-only executions while ensuring privacy. We also demonstrate that AsymML is effective in protecting data under common attacks such as model inversion and gradient attacks.

Secure model aggregation across many users is a key component of federated learning systems. The state-of-the-art protocols for secure model aggregation, which are based on additive masking, require all users to quantize their model updates to the same level of quantization. This severely degrades their performance due to lack of adaptation to available communication resources, e.g., bandwidth, at different users. As the main contribution of our paper, we proposeHeteroSAg, a scheme that allows secure model aggregation while using heterogeneous quantization. HeteroSAg enables the edge users to adjust their quantization proportional to their available communication resources, which can provide a substantially better trade-off between the accuracy of training and the communication time. Our proposed scheme is based on a grouping strategy by partitioning the network into groups, and partitioning the local model updates of users into segments. Instead of applying aggregation protocol to the entire local model update vector, it is applied on segments with specific coordination between users. We further demonstrate how HeteroSAg can enable Byzantine robustness while achieving secure aggregation simultaneously. Finally, we prove the convergence guarantees of HeteroSAg under heterogeneous quantization in the non-Byzantine scenario.

We introduceInfo-Commit, an information-theoretic protocol for polynomial commitment and verification. With the help of a trusted initializer, a succinct commitment to a private polynomial$f$is provided to the user. The user then queries the server to obtain evaluations of$f$at several inputs chosen by the user. The server provides the evaluations along with proofs of correctness which the user can verify against the initial commitment.Info-Commithas four main features. Firstly, the user is able to detect, with high probability, if the server has responded with evaluations of the same polynomial initially committed to. Secondly,Info-Commitprovides rigorous privacy guarantees for the server: upon observing the initial commitment and the response provided by the server to$m$evaluation queries, the user only learns$O(m^{2})$symbols about the coefficients of$f$. Thirdly, the verifiability and the privacy guarantees are unconditional regardless of the computational power of the two parties. Lastly,Info-Commitis doubly-efficient in the sense that in the evaluation phase, the user runs in$O(\sqrt {d})$time and the server runs in$O(d)$time, where$d-1$is the degree of the polynomial$f$.

single,double We consider the critical problems of distributed computing and learning over data while keeping it private from the computational servers. The state-of-the-art approaches to this problem rely on quantizing the data into a finite field, so that the cryptographic approaches for secure multiparty computing can then be employed. These approaches, however, can result in substantial accuracy losses due to fixed-point representation of the data and computation overflows. To address these critical issues, we propose a novel algorithm to solve the privacy-preserving distributed computing problem when data is in the analog domain, e.g., the field of real/complex numbers. We characterize the privacy of the data from both information-theoretic and cryptographic perspectives, while establishing a connection between the two notions in the analog domain. More specifically, the well-known connection between the distinguishing security (DS) and the mutual information security (MIS) metrics is extended from the discrete domain to the analog domain. This is then utilized to bound the amount of information about the data leaked to the servers in our protocol, in terms of the DS metric, using well-known results on the capacity of single-input multiple-output (SIMO) channel with correlated noise. It is shown how the proposed framework can be adopted to do computation tasks when data is represented using floating-point numbers. We then show that this leads to a fundamental trade-off between the privacy level of data and accuracy of the result. By extending the setup to distributed learning, we show how to train a machine learning model using the proposed algorithm while keeping the data as well as the trained model private. Then numerical results are shown for experiments on several datasets. Furthermore, experimental advantages are shown comparing to fixed-point implementations over finite fields.

We focus on the commonly used synchronous Gradient Descent paradigm for large-scale distributed learning, for which there has been a growing interest to develop efficient and robust gradient aggregation strategies that overcome two key system bottlenecks: communication bandwidth and stragglers’ delays. In particular, Ring-AllReduce (RAR) design has been proposed to avoid bandwidth bottleneck at any particular node by allowing each worker to only communicate with its neighbors that are arranged in a logical ring. On the other hand, Gradient Coding (GC) has been recently proposed to mitigate stragglers in a master-worker topology by allowing carefully designed redundant allocation of the data set to the workers. We propose a joint communication topology design and data set allocation strategy, named CodedReduce (CR), that combines the best of bothRARandGC. That is, it parallelizes the communications over a tree topology leading to efficient bandwidth utilization, and carefully designs a redundant data set allocation and coding strategy at the nodes to make the proposed gradient aggregation scheme robust to stragglers. In particular, we quantify the communication parallelization gain and resiliency of the proposedCRscheme, and prove its optimality when the communication topology is a regular tree. Moreover, we characterize the expected run-time ofCRand show order-wise speedups compared to the benchmark schemes. Finally, we empirically evaluate the performance of our proposedCRdesign over Amazon EC2 and demonstrate that it achieves speedups of up to$27.2\times $and$7.0\times $, respectively over the benchmarksGCandRAR.

The size of Transformer models is growing at an unprecedented rate. It has taken less than one year to reach trillion-level parameters since the release of GPT-3 (175B). Training such models requires both substantial engineering efforts and enormous computing resources, which are luxuries most research teams cannot afford. In this paper, we propose PipeTransformer, which leverages automated elastic pipelining for efficient distributed training of Transformer models. In PipeTransformer, we design an adaptive on the fly freeze algorithm that can identify and freeze some layers gradually during training, and an elastic pipelining system that can dynamically allocate resources to train the remaining active layers. More specifically, PipeTransformer automatically excludes frozen layers from the pipeline, packs active layers into fewer GPUs, and forks more replicas to increase data-parallel width. We evaluate PipeTransformer using Vision Transformer (ViT) on ImageNet and BERT on SQuAD and GLUE datasets. Our results show that compared to the state-of-the-art baseline, PipeTransformer attains up to 2.83-fold speedup without losing accuracy. We also provide various performance analyses for a more comprehensive understanding of our algorithmic and system-wise design. Finally, we have modularized our training system with flexible APIs and made the source code publicly available at https://DistML.ai.

We consider the problem of coded computing, where a computational task is performed in a distributed fashion in the presence of adversarial workers. We propose techniques to break the adversarial toleration threshold barrier previously known in coded computing. More specifically, we leverage list-decoding techniques for folded Reed-Solomon codes and propose novel algorithms to recover the correct codeword using side information. In the coded computing setting, we show how the master node can perform certain carefully designed extra computations to obtain the side information. This side information is then utilized to prune the output of the list decoder and uniquely recover the true outcome. We further propose folded Lagrange coded computing (FLCC) to incorporate the developed techniques into a specific coded computing setting. Our results show that FLCC outperforms LCC by breaking the barrier on the number of adversaries that can be tolerated. In particular, the corresponding threshold in FLCC is improved by a factor of two compared to that of LCC.

The state-of-the-art approaches to privacy-preserving coded computing rely on quantizing the data into a finite field, so that Shamir's secret sharing can be employed. Such coded computing solutions, however, are not properly scalable with the size of dataset, mainly due to computation overflows. To address such a critical issue, we propose a novel extension of certain coded computing schemes to the analog domain. This includes distributed polynomial evaluation and Lagrange coded computing (LCC) that are widely used in the literature. All the operations in the proposed protocols are done over the infinite fields of R/C but for practical implementations floating-point numbers are used. We characterize the privacy of data in our proposed protocols, against any subset of colluding servers up to a certain size, in terms of the distinguishing security (DS) and the mutual information security (MIS) metrics. Also, the accuracy of outcome is characterized in a practical setting assuming operations are performed using floating-point numbers. Consequently, fundamental trade-offs between the accuracy of the outcome and their privacy level are observed in the analog domain and are numerically evaluated. Moreover, we implement analog LCC (ALCC) to perform matrix-matrix multiplication over a batch of matrices. It is observed that ALCC is superior compared to LCC, implemented using fixed-point numbers, assuming both schemes use an equal number of bits to represent data symbols.

Federated learning can be a promising solution for enabling IoT cybersecurity (i.e., anomaly detection in the IoT environment) while preserving data privacy and mitigating the high communication/storage overhead (e.g., high-frequency data from time-series sensors) of centralized over-the-cloud approaches. In this paper, to further push forward this direction with a comprehensive study in both algorithm and system design, we build FedIoT platform that contains FedDetect algorithm for on-device anomaly data detection and a system design for realistic evaluation of federated learning on IoT devices. Furthermore, the proposed FedDetect learning framework improves the performance by utilizing a local adaptive optimizer (e.g., Adam) and a cross-round learning rate scheduler. In a network of realistic IoT devices (Raspberry PI), we evaluate FedIoT platform and FedDetect algorithm in both model and system performance. Our results demonstrate the efficacy of federated learning in detecting a wider range of attack types occurred at multiple devices. The system efficiency analysis indicates that both end-to-end training time and memory cost are affordable and promising for resource-constrained IoT devices. The source code is publicly available at https://github.com/FedML-AI/FedIoT.

Federated learning enables training a global model from data located at the client nodes, without data sharing and moving client data to a centralized server. Performance of federated learning in a multi-access edge computing (MEC) network suffers from slow convergence due to heterogeneity and stochastic fluctuations in compute power and communication link qualities across clients. We propose a novel coded computing framework, CodedFedL, that injects structured coding redundancy into federated learning for mitigating stragglers and speeding up the training procedure. CodedFedL enables coded computing for non-linear federated learning by efficiently exploiting distributed kernel embedding via random Fourier features that transforms the training task into computationally favourable distributed linear regression. Furthermore, clients generate local parity datasets by coding over their local datasets, while the server combines them to obtain the global parity dataset. Gradient from the global parity dataset compensates for straggling gradients during training, and thereby speeds up convergence. For minimizing the epoch deadline time at the MEC server, we provide a tractable approach for finding the amount of coding redundancy and the number of local data points that a client processes during training, by exploiting the statistical properties of compute as well as communication delays. We also characterize the leakage in data privacy when clients share their local parity datasets with the server. Additionally, we analyze the convergence rate and iteration complexity of CodedFedL under simplifying assumptions, by treating CodedFedL as a stochastic gradient descent algorithm. Finally, for demonstrating gains that CodedFedL can achieve in practice, we conduct numerical experiments using practical network parameters and benchmark datasets, in which CodedFedL speeds up the overall training time by up to 15× in comparison to the benchmark schemes.

Secure federated learning is a privacy-preserving framework to improve machine learning models by training over large volumes of data collected by mobile users. This is achieved through an iterative process where, at each iteration, users update a global model using their local datasets. Each user then masks its local update via random keys, and the masked models are aggregated at a central server to compute the global model for the next iteration. As the local updates are protected by random masks, the server cannot observe their true values. This presents a major challenge for the resilience of the model against adversarial (Byzantine) users, who can manipulate the global model by modifying their local updates or datasets. Towards addressing this challenge, this paper presents the first single-server Byzantine-resilient secure aggregation framework (BREA) for secure federated learning. BREA is based on an integrated stochastic quantization, verifiable outlier detection, and secure model aggregation approach to guarantee Byzantine-resilience, privacy, and convergence simultaneously. We provide theoretical convergence and privacy guarantees and characterize the fundamental trade-offs in terms of the network size, user dropouts, and privacy protection. Our experiments demonstrate convergence in the presence of Byzantine users, and comparable accuracy to conventional federated learning benchmarks.

Communication overhead is one of the major performance bottlenecks in large-scale distributed computing systems, in particular for machine learning applications. Conventionally, compression techniques are used to reduce the load of communication by combining intermediate results of the same computation task as much as possible. Recently, via the development of coded distributed computing (CDC), it has been shown that it is possible to enable coding opportunities across intermediate results of different computation tasks to further reduce the communication load. We propose a new scheme, named compressed coded distributed computing (in short, compressed CDC), which jointly exploits the above two techniques (i.e., combining the intermediate results of the same computation and coding across the intermediate results of different computations) to significantly reduce the communication load for computations with linear aggregation (reduction) of intermediate results in the final stage that are prevalent in machine learning (e.g., distributed training algorithms where partial gradients are computed distributedly and then averaged in the final stage). In particular, compressed CDC first compresses/combines several intermediate results for a single computation, and then utilizes multiple such combined packets to create a coded multicast packet that is simultaneously useful for multiple computations. We characterize the achievable communication load of compressed CDC and show that it substantially outperforms both combining methods and CDC scheme. Based on the compressed CDC technique, we then study a distributed training problem as one of its application. We characterize the communication load for this distributed training problem and show that it is asymptotically optimal.

Coded computing is a new framework to address fundamental issues in large scale distributed computing, by injecting structured randomness and redundancy. We first provide an overview of coded computing and summarize some recent advances. Then we focus on distributed matrix multiplication and consider a common scenario where each worker is assigned a fraction of the multiplication task. In particular, by partitioning two input matrices into m-by-p and p-by-n subblocks, a single multiplication task can be viewed as computing linear combinations of pmn submatrix products, which can be assigned to pmn workers. Such block-partitioning-based designs have been widely studied under the topics of secure, private, and batch computation, where the state of the arts all require computing at least “cubic” (pmn) number of submatrix multiplications. Entangled polynomial codes, first presented for straggler mitigation, provides a powerful method for breaking the cubic barrier. It achieves a subcubic recovery threshold, i.e., recovering the final product from any subset of multiplication results with a size order-wise smaller than pmn. We show that entangled polynomial codes can be further extended to also include these three important settings, providing unified frameworks that order-wise reduce the total computational costs by achieving subcubic recovery thresholds.

With recent advancements in edge computing capabilities, there has been a significant increase in utilizing the edge cloud for event-driven and time-sensitive computations. However, large-scale edge computing networks can suffer substantially from unpredictable and unreliable computing resources which can result in high variability of service quality. We consider the problem of computation offloading over unknown edge cloud networks with a sequence of timely computation jobs. Motivated by the MapReduce computation paradigm, we assume that each computation job can be partitioned to smaller Map functions which are processed at the edge, and the Reduce function is computed at the user after the Map results are collected from the edge nodes. We model the service quality of each edge device as function of context. The user decides the computations to offload to each device with the goal of receiving a recoverable set of computation results in the given deadline. By leveraging the coded computing framework in order to tackle failures or stragglers in computation, we formulate this problem using contextual-combinatorial multi-armed bandits (CC-MAB), and aim to maximize the cumulative expected reward. We propose an online learning policy called online coded edge computing policy, which provably achieves asymptotically-optimal performance in terms of regret loss compared with the optimal offline policy for the proposed CC-MAB problem. In terms of the cumulative reward, it is shown that the online coded edge computing policy significantly outperforms other benchmarks via numerical studies.

MLaaS (ML-as-a-Service) offerings by cloud computing platforms are becoming increasingly popular. Hosting pre-trained machine learning models in the cloud enables elastic scalability as the demand grows. But providing low latency and reducing the latency variance is a key requirement. Variance is harder to control in a cloud deployment due to uncertain-ties in resource allocations across many virtual instances. We propose the collage inference technique, which uses a novel convolutional neural network model, collage-cnn, to provide low-cost redundancy. A collage-cnn model takes a collage image formed by combining multiple images and performs multi-image classification in one shot, albeit at slightly lower accuracy. We augment a collection of traditional single image classifier models with a single collage-cnn classifier, which acts as their low-cost redundant backup. Collage-cnn provides backup classification results if any single image classification requests experience a slowdown. Deploying the collage-cnn models in the cloud, we demonstrate that the 99th percentile tail latency of inference can be reduced by 1.2x to 2x compared to replication-based approaches while providing high accuracy. Variation in inference latency can be reduced by 1.8x to 15x.

Today's blockchain designs suffer from a trilemma claiming that no blockchain system can simultaneously achieve decentralization, security, and performance scalability. For current blockchain systems, as more nodes join the network, the efficiency of the system (computation, communication, and storage) stays constant at best. A leading idea for enabling blockchains to scale efficiency is the notion of sharding: different subsets of nodes handle different portions of the blockchain, thereby reducing the load for each individual node. However, existing sharding proposals achieve efficiency scaling by compromising on trust - corrupting the nodes in a given shard will lead to the permanent loss of the corresponding portion of data. In this paper, we settle the trilemma by demonstrating a new protocol for coded storage and computation in blockchains. In particular, we propose PolyShard: “polynomially coded sharding” scheme that achieves information-theoretic upper bounds on the efficiency of the storage, system throughput, as well as on trust, thus enabling a truly scalable system. We provide simulation results that numerically demonstrate the performance improvement over state of the arts, and the scalability of the PolyShard system. Finally, we discuss potential enhancements, and highlight practical considerations in building such a system.

Client devices at the edge are generating increasingly large amounts of rich data suitable for learning powerful statistical models. However, privacy concerns and heavy communication load make it infeasible to move the client data to a centralized location for training. In many distributed learning setups, client nodes carry out gradient computations on their local data while the central master server receives the local gradients and aggregates them to take the global model update step. To guarantee robustness against straggling communication links, we consider a hierarchical setup with neclients and nhreliable helper nodes that are available to aid in gradient aggregation at the master. To achieve resiliency against straggling client-to-helpers links, we propose two approaches leveraging coded redundancy. First is the Aligned Repetition Coding (ARC) that repeats gradient components on the helper links, allowing significant partial aggregations at the helpers, resulting in a helpers-to-master communication load (CHM) of O(nh). ARC however results in a client-to-helpers communication load (CEH) of Θ(nh), which is prohibitive for client nodes due to limited and costly bandwidth. We thus propose Aligned Minimum Distance Separable Coding (AMC) that achieves optimal CEHof Θ(1) for a given resiliency threshold by using MDS code over the gradient components, while achieving a CHMof O(ne).

Cloud computing platforms have created the possibility for computationally limited users to delegate demanding tasks to strong but untrusted servers. Verifiable computing algorithms help build trust in such interactions by enabling the server to provide a proof of correctness of his results which the user can check very efficiently. In this article, we present a doubly-efficient interactive algorithm for verifiable polynomial evaluation. Unlike the mainstream literature on verifiable computing, the soundness of our algorithm is information-theoretic and cannot be broken by a computationally unbounded server. By relying on basic properties of error correcting codes, our algorithm enforces a dishonest server to provide false results to problems which become progressively easier to verify. After roughly logd rounds, the user can verify the response of the server against a look-up table that has been pre-computed during an initialization phase. For a polynomial of degree d, we achieve a user complexity of O(dϵ), a server complexity of O(d1+ϵ), a round complexity of O(logd) and an initialization complexity of O(d1+ϵ).

Recently, there has been a significant increase in utilizing the cloud networks for event-driven and time-sensitive computations. However, large-scale distributed computing networks can suffer substantially from unpredictable and unreliable computing resources which can result in high variability of service quality. Thus, it is crucial to design efficient task scheduling policies that guarantee quality of service and the timeliness of computation queries. In this paper, we study the problem of computation offloading over unknown cloud networks with a sequence of timely computation jobs. We model the service quality (success probability of returning result back to the user within deadline) of each worker as function of context (collection of factors that affect workers). The user decides the computations to offload to each worker with the goal of receiving a recoverable set of computation results in the given deadline. Our goal is to design an efficient computing policy in the dark without the knowledge of the context or computation capabilities of each worker. By leveraging the coded computing framework in order to tackle failures or stragglers in computation, we formulate this problem using contextual-combinatorial multi-armed bandits (CC-MAB), and aim to maximize the cumulative expected reward. We propose an online learning policy called online coded computing policy, which provably achieves asymptotically-optimal performance in terms of regret loss compared with the optimal offline policy.

In distributed matrix multiplication, a common scenario is to assign each worker a fraction of the multiplication task, by partitioning the input matrices into smaller submatrices. In particular, by dividing two input matrices into m-by-p and p-by-n subblocks, a single multiplication task can be viewed as computing linear combinations of pmn submatrix products, which can be assigned to pmn workers. Such block-partitioning based designs have been widely studied under the topics of secure, private, and batch computation, where the state of the arts all require computing at least "cubic" (pmn) number of submatrix multiplications. Entangled polynomial codes, first presented for straggler mitigation, provides a powerful method for breaking the cubic barrier. It achieves a subcubic recovery threshold, meaning that the final product can be recovered from any subset of multiplication results with a size order-wise smaller than pmn. In this work, we show that entangled polynomial codes can be further extended to also include these three important settings, and provide a unified framework that order-wise reduces the total computational costs upon the state of the arts by achieving subcubic recovery thresholds.

Scaling up the convolutional neural network (CNN) size (e.g., width, depth, etc.) is known to effectively improve model accuracy. However, the large model size impedes training on resource-constrained edge devices. For instance, federated learning (FL) may place undue burden on the compute capability of edge nodes, even though there is a strong practical need for FL due to its privacy and confidentiality properties. To address the resource-constrained reality of edge devices, we reformulate FL as a group knowledge transfer training algorithm, called FedGKT. FedGKT designs a variant of the alternating minimization approach to train small CNNs on edge nodes and periodically transfer their knowledge by knowledge distillation to a large server-side CNN. FedGKT consolidates several advantages into a single framework: reduced demand for edge computation, lower communication bandwidth for large CNNs, and asynchronous training, all while maintaining model accuracy comparable to FedAvg. We train CNNs designed based on ResNet-56 and ResNet-110 using three distinct datasets (CIFAR-10, CIFAR-100, and CINIC-10) and their non-IID variants. Our results show that FedGKT can obtain comparable or even slightly higher accuracy than FedAvg. More importantly, FedGKT makes edge training affordable. Compared to the edge training using FedAvg, FedGKT demands 9 to 17 times less computational power (FLOPs) on edge devices and requires 54 to 105 times fewer parameters in the edge CNN. Our source code is released at FedML (https://fedml.ai).

Transfer learning has emerged as a powerful technique for improving the performance of machine learning models on new domains where labeled training data may be scarce. In this approach a model trained for a source task, where plenty of labeled training data is available, is used as a starting point for training a model on a related target task with only few labeled training data. Despite recent empirical success of transfer learning approaches, the benefits and fundamental limits of transfer learning are poorly understood. In this paper we develop a statistical minimax framework to characterize the fundamental limits of transfer learning in the context of regression with linear and one-hidden layer neural network models. Specifically, we derive a lower-bound for the target generalization error achievable by any algorithm as a function of the number of labeled source and target data as well as appropriate notions of similarity between the source and target tasks. Our lower bound provides new insights into the benefits and limitations of transfer learning. We further corroborate our theoretical finding with various experiments.

We consider a collaborative learning scenario in which multiple data-owners wish to jointly train a logistic regression model, while keeping their individual datasets private from the other parties. We propose COPML, a fully-decentralized training framework that achieves scalability and privacy-protection simultaneously. The key idea of COPML is to securely encode the individual datasets to distribute the computation load effectively across many parties and to perform the training computations as well as the model updates in a distributed manner on the securely encoded data. We provide the privacy analysis of COPML and prove its convergence. Furthermore, we experimentally demonstrate that COPML can achieve significant speedup in training over the benchmark protocols. Our protocol provides strong statistical privacy guarantees against colluding parties (adversaries) with unbounded computational power, while achieving up to $16\times$ speedup in the training time against the benchmark protocols.

Many distributed computing systems have been developed recently for implementing graph based algorithms such as PageRank over large-scale graph-structured datasets such as social networks. Performance of these systems significantly suffers from communication bottleneck as a large number of messages are exchanged among servers at each step of the computation. Motivated by graph based MapReduce, we propose a coded computing framework that leverages computation redundancy to alleviate the communication bottleneck in distributed graph processing. As a key contribution of this work, we develop a novel coding scheme that systematically injects structured redundancy in the computation phase to enable coded multicasting opportunities during message exchange between servers, reducing the communication load substantially in large-scale graph processing. For theoretical analysis, we consider random graph models, and focus on schemes in which subgraph allocation and Reduce allocation are only dependent on vertex ID while the Shuffle design varies with graph connectivity. Specifically, we prove that our proposed scheme enables an (asymptotically) inverse-linear trade-off between computation load and average communication load for two popular random graph models - Erdös-Rényi model, and power law model. Particularly, for a given computation load r, (i.e. when each graph vertex is carefully stored at r servers), the proposed scheme slashes the average communication load by (nearly) a multiplicative factor of r. Furthermore, for the Erdös-Rényi model, we prove that our proposed scheme is optimal asymptotically as the graph size increases by providing an information-theoretic converse. To illustrate the benefits of our scheme in practice, we implement PageRank over Amazon EC2, using artificial as well as real-world datasets, demonstrating gains of up to 50.8% in comparison to the conventional PageRank implementation. Additionally, we specialize our coded scheme and extend our theoretical results to two other random graph models - random bi-partite model, and stochastic block model. Our specialized schemes asymptotically enable inverse-linear trade-offs between computation and communication loads in distributed graph processing for these popular random graph models as well. We complement the achievability results with converse bounds for both of these models.

We consider the problem of massive matrix multiplication, which underlies many data analytic applications, in a large-scale distributed system comprising a group of worker nodes. We target the stragglers' delay performance bottleneck, which is due to the unpredictable latency in waiting for slowest nodes (or stragglers) to finish their tasks. We propose a novel coding strategy, named entangled polynomial code, for designing the intermediate computations at the worker nodes in order to minimize the recovery threshold (i.e., the number of workers that we need to wait for in order to compute the final output). We demonstrate the optimality of entangled polynomial code in several cases, and show that it provides orderwise improvement over the conventional schemes for straggler mitigation. Furthermore, we characterize the optimal recovery threshold among all linear coding strategies within a factor of 2 using bilinear complexity, by developing an improved version of the entangled polynomial code. In particular, while evaluating bilinear complexity is a well-known challenging problem, we show that optimal recovery threshold for linear coding strategies can be approximated within a factor of 2 of this fundamental quantity. On the other hand, the improved version of the entangled polynomial code enables further and orderwise reduction in the recovery threshold, compared to its basic version. Finally, we show that the techniques developed in this paper can also be extended to several other problems such as coded convolution and fault-tolerant computing, leading to tight characterizations.

We consider a scenario involving computations over a massive dataset stored distributedly across multiple workers, which is at the core of distributed learning algorithms. We propose Lagrange Coded Computing (LCC), a new framework to simultaneously provide (1) resiliency against stragglers that may prolong computations; (2) security against Byzantine (or malicious) workers that deliberately modify the computation for their benefit; and (3) (information-theoretic) privacy of the dataset amidst possible collusion of workers. LCC, which leverages the well-known Lagrange polynomial to create computation redundancy in a novel coded form across workers, can be applied to any computation scenario in which the function of interest is an arbitrary multivariate polynomial of the input dataset, hence covering many computations of interest in machine learning. LCC significantly generalizes prior works to go beyond linear computations. It also enables secure and private computing in distributed settings, improving the computation and communication efficiency of the state-of-the-art. Furthermore, we prove the optimality of LCC by showing that it achieves the optimal tradeoff between resiliency, security, and privacy, i.e., in terms of tolerating the maximum number of stragglers and adversaries, and providing data privacy against the maximum number of colluding workers. Finally, we show via experiments on Amazon EC2 that LCC speeds up the conventional uncoded implementation of distributed least-squares linear regression by up to $13.43\times$, and also achieves a $2.36\times$-$12.65\times$ speedup over the state-of-the-art straggler mitigation strategies.

This paper proposes a coded distributed graph processing framework to alleviate the communication bottleneck in large-scale distributed graph processing. In particular, we propose a topology-aware coded computing (TACC) algorithm that has two salient features. First, we propose a topology-aware graph allocation strategy. Second, we propose a coded aggregation scheme that combines the intermediate computations for graph processes while constructing coded messages. The proposed setup builds on a trade-off between computation and communication, in that increasing the computation load at the distributed parties can in turn reduce the communication load. We demonstrate the effectiveness of the TACC algorithm by comparing the communication load with existing setups on a Google web graph for PageRank computations. In particular, we show that the proposed coding strategy can lead up to 82% improvement in reducing the communication load when compared to the state-of-the-art.

This paper considers the graph signal sampling problem when some of the selected samples are lost or unavailable due to sensor failures or adversarial erasures. We formulate a robust graph signal sampling problem where only a subset of selected samples are received, and the goal is to maximize the worst-case performance. We propose a novel greedy robust sample selection algorithm and study its performance guarantees. Our numerical results demonstrate the performance improvement of the proposed algorithm over the existing schemes.

In this paper we focus on the problem of finding the optimal weights of the shallowest of neural networks consisting of a single Rectified Linear Unit (ReLU). These functions are of the form x → max(0, 〈w, x〉) with w ∈ ℝddenoting the weight vector. We focus on a planted i model where the inputs are chosen i.i.d. from a Gaussian distribution and the labels are generated according to a planted weight vector. We first show that mini-batch stochastic gradient descent when suitably initialized, converges at a geometric rate to the planted model with a number of samples that is optimal up to numerical constants. Next we focus on a parallel implementation where in each iteration the mini-batch gradient is calculated in a distributed manner across multiple processors and then broadcast to a master or all other processors. To reduce the communication cost in this setting we utilize a Quanitzed Stochastic Gradient Scheme (QSGD) where the partial gradients are quantized. Perhaps unexpectedly, we show that QSGD maintains the fast convergence of SGD to a globally optimal model while significantly reducing the communication cost. We further corroborate our numerical findings via various experiments including distributed implementations over Amazon EC2.

Lagrange Coded Computing (LCC) is a recently proposed technique for resilient, secure, and private computation of arbitrary polynomials in distributed environments. By mapping such computations to composition of polynomials, LCC allows the master node to complete the computation by accessing a minimal number of workers and downloading all of their content, thus providing resiliency to the remaining stragglers. However, in the most common case in which the number of stragglers is less than in the worst case scenario, much of the computational power of the system remains unexploited. To amend this issue, in this paper we expand LCC by studying a fundamental trade-off between download and access, and present two contributions. In the first contribution, it is shown that without any modification to the encoding process, the master can decode the computations by accessing a larger number of nodes, however downloading less information from each node in comparison with LCC (i.e., trading access for download). This scheme relies on decoding a particular polynomial in the ideal that is generated by the polynomials of interest, a technique we call Ideal Decoding. This new scheme also improves LCC in the sense that for systems with adversaries, the overall downloaded bandwidth is smaller than in LCC. In the second contribution we study a real-time model of this trade-off, in which the data from the workers is downloaded sequentially. By clustering nodes of similar delays and encoding the function with Universally Decodable Matrices, the master can decode once sufficient data is downloaded from every cluster, regardless of the internal delays within that cluster. This allows the master to utilize the partial work that is done by stragglers, rather than to ignore it, a feature that most past works in coded computing are lacking.

Scaling up distributed machine learning systems face two major bottlenecks - delays due to stragglers and limited communication bandwidth. Recently, a number of coding theoretic strategies have been proposed for mitigating these bottlenecks. In particular, the Gradient Coding (GC) scheme was proposed to speed up distributed gradient descent algorithm in a synchronous master-worker setting by providing robustness to stragglers. A major drawback of the master-worker architecture for distributed learning is however, the bandwidth contention at the master, which can significantly deteriorate the performance as the cluster size increases. In this paper, we propose a new framework named Tree Gradient Coding (TGC) for distributed gradient aggregation, which parallelizes communication over a tree topology while providing straggler robustness. As our main contribution, we characterize the minimum computation load for TGC for a given tree topology and straggler resiliency, and design a tree gradient coding algorithm that achieves this optimal computation load. Furthermore, we provide results from experiments over Amazon EC2, where TGC speeds up the training time by up to 18.8× in comparison to GC.

We study the problem of verifiable polynomial evaluation in the user-server and multi-party setups. We propose INTERPOL, an information-theoretically verifiable algorithm that allows a user to delegate the evaluation of a polynomial to a server, and verify the correctness of the results with high probability and in sublinear complexity. Compared to the existing approaches which typically rely on cryptographic assumptions, INTERPOL stands out in that it does not assume any computational limitation on the server. INTERPOL relies on decomposition of polynomial evaluation into two matrix multiplications, and injection of computation redundancy in the form of locally computed parities with secret coefficients for verification. Furthermore, by generalizing INTERPOL to a multiparty setting consisting of a network of n untrusted nodes, where each node is interested in evaluating the same polynomial, we demonstrate that we can achieve an overall computational complexity comparable to a trusted setup, while guaranteeing information-theoretic verification at each node.

In modern distributed computing systems, unpredictable and unreliable infrastructures result in high variability of computing resources. Meanwhile, there is significantly increasing demand for timely and event-driven services with deadline constraints. Motivated by measurements over Amazon EC2 clusters, we consider a two-state Markov model for variability of computing speed in cloud networks. In this model, each worker can be either in a good state or a bad state in terms of the computation speed, and the transition between these states is modeled as a Markov chain which is unknown to the scheduler. We then consider a Coded Computing framework, in which the data is possibly encoded and stored at the worker nodes in order to provide robustness against nodes that may be in a bad state. Our goal is to design the optimal computation-load allocation strategy that maximizes the timely computation throughput (i.e, the average number of computation tasks accomplished before their deadline). Our main result is the development of a dynamic computation strategy called Estimate-and-Allocate (EA) strategy, which achieves the optimal timely computation throughput. Compared with the static allocation strategy, EA improves the timely computation throughput by 1.44 ×4.6 in experiments over Amazon EC2 clusters.

We consider the problem of distributedly computing a general class of functions, referred to as gradient-type computation, while maintaining the privacy of the input dataset. Gradient-type computation evaluates the sum of some "partial gradients", defined as polynomials of subsets of the input. It underlies many algorithms in machine learning and data analytics. We propose Harmonic Coding, which universally computes any gradient-type function, while requiring the minimum possible number of workers. Harmonic Coding strictly improves computing schemes developed based on prior works, such as Shamir's secret sharing and Lagrange Coded Computing, by injecting coded redundancy using harmonic progression. It enables the computing results of the workers to be interpreted as the sum of partial gradients and some redundant results, which then allows the cancellation of non-gradient terms in the decoding process. By proving a matching converse, we demonstrate the optimality of Harmonic Coding, even compared to the schemes that are non-universal (i.e., can be designed based on a specific gradient-type function).

In modern distributed computing systems, unpredictable and unreliable infrastructures result in high variability of computing resources. Meanwhile, there is significantly increasing demand for timely and event-driven services with deadline constraints. Motivated by measurements over Amazon EC2 clusters, we consider a two-state Markov model for variability of computing speed in cloud networks. In this model, each worker can be either in a good state or a bad state in terms of the computation speed, and the transition between these states is modeled as a Markov chain which is unknown to the scheduler. We then consider a Coded Computing framework, in which the data is possibly encoded and stored at the worker nodes in order to provide robustness against nodes that may be in a bad state. With timely computation requests submitted to the system with computation deadlines, our goal is to design the optimal computation-load allocation scheme and the optimal data encoding scheme that maximize the timely computation throughput (i.e, the average number of computation tasks that are accomplished before their deadline). Our main result is the development of a dynamic computation strategy called Lagrange Estimate-and-Allocate (LEA) strategy, which achieves the optimal timely computation throughput. It is shown that compared to the static allocation strategy, LEA improves the timely computation throughput by 1.4x ~ 17.5x in various scenarios via simulations and by 1.27x ~ 6.5x in experiments over Amazon EC2 clusters.

We introduce Coded State Machine (CSM), an information-theoretic framework to securely and efficiently execute multiple state machines on Byzantine nodes. The standard method of solving this problem is using State Machine Replication, which achieves high security at the cost of low efficiency. CSM simultaneously achieves the optimal linear scaling in storage, throughput, and security with increasing network size. The storage is scaled via the design of Lagrange coded states and coded input commands that require the same storage size as their origins. The computational efficiency is scaled using a novel delegation algorithm, called INTERMIX, which is an information-theoretically verifiable matrix-vector multiplication algorithm of independent interest.

While performing distributed computations in today's cloud-based platforms, execution speed variations among compute nodes can significantly reduce the performance and create bottlenecks like stragglers. Coded computation techniques leverage coding theory to inject computational redundancy and mitigate stragglers in distributed computations. In this paper, we propose a dynamic workload distribution strategy for coded computation called Slack Squeeze Coded Computation (S2C2). S2C2 squeezes the compute slack (i.e., overhead) that is built into the coded computing frameworks by efficiently assigning work for all fast and slow nodes according to their speeds and without needing to re-distribute data. We implement an LSTM-based speed prediction algorithm to predict speeds of compute nodes. We evaluate S2C2 on linear algebraic algorithms, gradient descent, graph ranking, and graph filtering algorithms. We demonstrate 19% to 39% reduction in total computation latency using S2C2 compared to job replication and coded computation. We further show how S2C2 can be applied beyond matrix-vector multiplication.

Coded caching can significantly reduce the communication bandwidth requirement for satisfying users' demands by utilizing the multicasting gain among multiple users. Most existing works assume that the users follow the prescriptions for content placement made by the system. However, users may prefer to decide what files to cache. To address this issue, we consider a network consisting of a file server connected through a shared link to K users, each equipped with a cache which has been already filled arbitrarily. Given an arbitrary content placement, the goal is to find a delivery strategy for the server that minimizes the load of the shared link. In this paper, we focus on a specific class of coded multicasting delivery schemes known as the “clique cover delivery scheme.” We first formulate the optimal clique cover delivery problem as a combinatorial optimization problem. Using a connection with the weighted set cover problem, we propose an approximation algorithm and show that it provides an approximation ratio of (1 + log K), while the approximation ratio for the existing coded delivery schemes is linear in K. Numerical simulations show that our proposed algorithm provides a considerable bandwidth reduction over the existing coded delivery schemes for almost all content placement schemes.

We consider the problem of interference management in wireless cellular networks with caches at both base stations and receivers, and we characterize the degrees of freedom (DoFs) per cell to within an additive gap of (1/3) and a multiplicative gap of 2 for all system parameters, under one-shot linear schemes. Our result indicates that the one-shot linear DoF per cell scales linearly with the total amount of cache available in the cell, i.e., the sum of the caches at the central base station and all the receivers within the cell, resembling a similar phenomenon previously observed for the case of fully connected wireless networks. To establish the result, we propose a decentralized and randomized cache placement and a delivery scheme, which, on one hand, utilizes the overlap of contents at the base station caches to zero-force part of their outgoing interference and, on the other hand, uses the receiver cache contents to create coded multicasting opportunities, so that the receivers can eliminate the remaining interference due to undesired packets. We also provide a converse argument, which shows that our achievable one-shot linear DoF per cell is within a constant additive gap of (1/3) and a multiplicative gap of 2 of its optimum.

Graph-based methods have been quite successful in solving unsupervised and semi-supervised learning problems, as they provide a means to capture the underlying geometry of the dataset. It is often desirable for the constructed graph to satisfy two properties: first, data points that are similar in the feature space should be strongly connected on the graph, and second, the class label information should vary smoothly with respect to the graph, where smoothness is measured using the spectral properties of the graph Laplacian matrix. Recent works have justified some of these smoothness conditions by showing that they are strongly linked to the semi-supervised smoothness assumption and its variants. In this work, we reinforce this connection by viewing the problem from a graph sampling theoretic perspective, where class indicator functions are treated as bandlimited graph signals (in the eigenvector basis of the graph Laplacian) and label prediction as a bandlimited reconstruction problem. Our approach involves analyzing the bandwidth of class indicator signals generated from statistical data models with separable and nonseparable classes. These models are quite general and mimic the nature of most real-world datasets. Our results show that in the asymptotic limit, the bandwidth of any class indicator is also closely related to the geometry of the dataset. This allows one to theoretically justify the assumption of bandlimitedness of class indicator signals, thereby providing a sampling theoretic interpretation of graph-based semi-supervised classification.

We consider a basic caching system, where a single server with a database of N files (e.g., movies) is connected to a set of K users through a shared bottleneck link. Each user has a local cache memory with a size of M files. The system operates in two phases: a placement phase, where each cache memory is populated up to its size from the database, and a following delivery phase, where each user requests a file from the database, and the server is responsible for delivering the requested contents. The objective is to design the two phases to minimize the load (peak or average) of the bottleneck link. We characterize the rate-memory tradeoff of the above caching system within a factor of 2.00884 for both the peak rate and the average rate (under uniform file popularity), improving the state of the arts that are within a factor of 4 and 4.7, respectively. Moreover, in a practically important case where the number of files (N) is large, we exactly characterize the tradeoff for systems with no more than five users and characterize the tradeoff within a factor of 2 otherwise. To establish these results, we develop two new converse bounds that improve over the state of the art.

There is a growing interest in the development of in-network dispersed computing paradigms that leverage the computing capabilities of heterogeneous resources dispersed across the network for processing a massive amount of data collected at the edge of the network. We consider the problem of task scheduling for such networks, in a dynamic setting in which arriving computation jobs are modeled as chains, with nodes representing tasks, and edges representing precedence constraints among tasks. In our proposed model, motivated by significant communication costs in dispersed computing environments, the communication times are taken into account. More specifically, we consider a network where servers can serve all task types, and sending the outputs of processed tasks from one server to another server results in some communication delay. We first characterize the capacity region of the network, then propose a novel virtual queueing network encoding the state of the network. Finally, we propose a Max-Weight type scheduling policy, and considering the stochastic network in the fluid limit, we use a Lyapunov argument to show that the policy is throughput-optimal. Beyond the model of chains, we extend the scheduling problem to the model of the directed acyclic graph (DAG) which imposes a new challenge, namely logic dependency difficulty, requiring the data of processed parents tasks to be sent to the same server for processing the child task. We propose a virtual queueing network for DAG scheduling over broadcast networks, where servers always broadcast the data of processed tasks to other servers, and prove that Max-Weight policy is throughput-optimal.

Solving a large-scale system of linear equations is a key step at the heart of many algorithms in scientific computing, machine learning, and beyond. When the problem dimension is large, computational and/or memory constraints make it desirable, or even necessary, to perform the task in a distributed fashion. In this paper, we consider a common scenario in which a taskmaster intends to solve a large-scale system of linear equations by distributing subsets of the equations among a number of computing machines/cores. We propose a new algorithm called Accelerated Projection-based Consensus, in which at each iteration every machine updates its solution by adding a scaled version of the projection of an error signal onto the nullspace of its system of equations, and the taskmaster conducts an averaging over the solutions with momentum. The convergence behavior of the proposed algorithm is analyzed in detail and analytically shown to compare favorably with the convergence rate of alternative distributed methods, namely distributed gradient descent, distributed versions of Nesterov's accelerated gradient descent and heavy-ball method, the block Cimmino method, and Alternating Direction Method of Multipliers. On randomly chosen linear systems, as well as on real-world data sets, the proposed method offers significant speed-up relative to all the aforementioned methods. Finally, our analysis suggests a novel variation of the distributed heavy-ball method, which employs a particular distributed preconditioning and achieves the same theoretical convergence rate as that in the proposed consensus-based method.

A new class of caching schemes, called coded caching, can significantly reduce the communication bandwidth requirement for satisfying users' demands by utilizing the multicasting gain among multiple users. Most existing works assume that the users follow the prescriptions for content placement made by the system. However, users may prefer to decide what files to cache or discard some part of their caches due to lack of space. In order to address this issue, we study a caching system where the content placement phase has been already carried out by the users arbitrarily. More specifically, we consider a network consisting of a file server connected through a shared link to $K$ users, each equipped with a cache. Given arbitrary content placement by the users, the goal is to find a coded multicast strategy for the server that minimizes the load of the shared link. We first formulate the optimal coded multicast design problem as an Integer Linear Program (ILP). Using a connection with the weighted set cover problem, we propose an approximation algorithm for solving this problem. We show that our proposed algorithm provides $(1 + \log K)$-approximation for the optimal coded multicast design problem, while the approximation ratio for the existing coded delivery schemes is linear in $K$. Numerical simulations show that our proposed algorithm provides a considerable bandwidth reduction over the existing coded delivery schemes for uniformly-random generated content placement.

Communication overhead is one of the major performance bottlenecks in large-scale distributed computing systems, especially for machine learning applications. Conventionally, compression techniques are used to reduce the load of communication by combining intermediate results of the same computation task as much as possible. Recently, via the development of coded distributed computing (CDC), it has been shown that it is possible to code across intermediate results of different tasks to further reduce communication. We propose a new scheme, named compressed coded distributed computing (in short, compressed CDC), which jointly exploits these two techniques (i.e., combining intermediate results of the same computation and coding across intermediate results of different computations) to significantly reduce the communication load for computations with linear aggregation of intermediate results in the final stage that are prevalent in machine learning (e.g., distributed training where partial gradients are computed distributedly and then averaged in the final stage). In particular, compressed CDC first compresses/combines several intermediate results for a single computation, and then utilizes multiple such combined packets to create a coded multicast packet that is simultaneously useful for multiple computations. We characterize the achievable communication load of compressed CDC and show that it substantially outperforms both combining methods and CDC scheme.

Many distributed graph computing systems have been developed recently for efficient processing of massive graphs. These systems require many messages to be exchanged among computing machines at each step of the computation, making communication bandwidth a major performance bottleneck. We present a coded computing framework that systematically injects redundancy in the computation phase to enable coding opportunities in the communication phase thus reducing the communication load substantially. Specifically, we propose coded schemes that enable an inverse-linear trade-off (asymptotically) between computation load and average communication load for Erdös-Rényi (ER) random graph. The proposed scheme for ER graph is shown to be optimal asymptotically as the graph size n → ∞. For finite n, we demonstrate via numerical analysis that for a given computation load r, i.e. when each graph vertex is carefully stored at r servers, the proposed scheme slashes the average communication load by (nearly) r.

There is a growing interest in development of in-network dispersed computing paradigms that leverage the computing capabilities of heterogeneous resources dispersed across the network for processing massive amount of data is collected at the edge of the network. We consider the problem of task scheduling for such networks, in a dynamic setting in which arriving computation jobs are modeled as chains, with nodes representing tasks, and edges representing precedence constraints among tasks. In our proposed model, motivated by significant communication costs in dispersed computing environments, the communication times are taken into account. More specifically, we consider a network where servers are capable of serving all task types, and sending the results of processed tasks from one server to another server results in some communication delay that makes the design of optimal scheduling policy significantly more challenging than classical queueing networks. As the main contributions of the paper, we first characterize the capacity region of the network, then propose a novel virtual queueing network encoding the state of the network. Finally, we propose a Max- Weight type scheduling policy, and considering the virtual queueing network in the fluid limit, we use a Lyapunov argument to show that the policy is throughput-optimal.

Consider massive matrix multiplication, a problem that underlies many data analytic applications, in a large-scale distributed system comprising a group of workers. We target the stragglers' delay performance bottleneck, which is due to the unpredictable latency in waiting for slowest nodes (or stragglers) to finish their tasks. We propose a novel coding strategy, named entangled polynomial code, designing intermediate computations at the workers in order to minimize the recovery threshold (i.e., the number of workers that we need to wait for in order to compute the final output). We prove the optimality of entangled polynomial code in several cases, and show that it provides order-wise improvement over the conventional schemes for straggler mitigation. Furthermore, we characterize the optimal recovery threshold among all linear coding strategies within a factor of 2 using bilinear complexity, by developing an improved version of the entangled polynomial code.

We consider the problem of secure and private multiparty computation (MPC), in which the goal is to compute a general polynomial function distributedly over several workers, while keeping them oblivious to the content of the dataset, and preventing them from maliciously affecting the computation result. We demonstrate the role of Lagrange Coded Computing (LCC), a recently proposed coded computing technique that can be applied to general polynomial computations, on enabling secure and private MPC. We show that LCC offers both private and secure computation simultaneously, and is universal in the sense that all polynomials up to a certain degree can be computed on the same encoding. We also demonstrate that LCC achieves an optimal tradeoff between privacy and security, and requires a minimal amount of added randomness for privacy. Compared to prevalent algorithms in MPC (in particular the celebrated BGW scheme), we show that LCC significantly improves the storage, communication, and secret-sharing overhead needed for MPC.

Distributed training of deep nets is an important technique to address some of the present day computing challenges like memory consumption and computational demands. Classical distributed approaches, synchronous or asynchronous, are based on the parameter server architecture, i.e., worker nodes compute gradients which are communicated to the parameter server while updated parameters are returned. Recently, distributed training with AllReduce operations gained popularity as well. While many of those operations seem appealing, little is reported about wall-clock training time improvements. In this paper, we carefully analyze the AllReduce based setup, propose timing models which include network latency, bandwidth, cluster size and compute time, and demonstrate that a pipelined training with a width of two combines the best of both synchronous and asynchronous training. Specifically, for a setup consisting of a four-node GPU cluster we show wall-clock time training improvements of up to 5.4x compared to conventional approaches.

Data parallelism can boost the training speed of convolutional neural networks (CNN), but could suffer from significant communication costs caused by gradient aggregation. To alleviate this problem, several scalar quantization techniques have been developed to compress the gradients. But these techniques could perform poorly when used together with decentralized aggregation protocols like ring all-reduce (RAR), mainly due to their inability to directly aggregate compressed gradients. In this paper, we empirically demonstrate the strong linear correlations between CNN gradients, and propose a gradient vector quantization technique, named GradiVeQ, to exploit these correlations through principal component analysis (PCA) for substantial gradient dimension reduction. GradiveQ enables direct aggregation of compressed gradients, hence allows us to build a distributed learning system that parallelizes GradiveQ gradient compression and RAR communications. Extensive experiments on popular CNNs demonstrate that applying GradiveQ slashes the wall-clock gradient aggregation time of the original RAR by more than 5x without noticeable accuracy loss, and reduce the end-to-end training time by almost 50%. The results also show that \GradiveQ is compatible with scalar quantization techniques such as QSGD (Quantized SGD), and achieves a much higher speed-up gain under the same compression ratio.

We study the Gaussian multiple-input multiple-output multiple-eavesdropper wiretap channel where a transmitter wishes to communicate a confidential message to a legitimate receiver in the presence of eavesdroppers. Each node in the network is equipped with an arbitrary number of antennas. Furthermore, channels are time varying, and there is no channel state information available at the transmitter (CSIT) with respect to eavesdroppers' channels; and transmitter only has access to delayed CSIT of the channel to the legitimate receiver. The secure degrees of freedom (SDoF) for such a network has only been characterized for special cases, and is unknown in general. We completely characterize the SDoF of this network for all antenna configurations. In particular, we strictly improve the state-of-the-art achievable scheme for this network by proposing more efficient artificial noise alignment at the receivers. Furthermore, we develop a tight upper bound by utilizing three important inequalities that provide lower bounds on the received signal dimensions at receivers which supply delayed CSIT or no CSIT. These inequalities together allow for analysis of signal dimensions in networks with heterogeneous CSIT; and as a result, we present a converse proof that leads to characterization of SDoF for all possible antenna configurations.

How can we optimally trade extra computing power to reduce the communication load in distributed computing? We answer this question by characterizing a fundamental tradeoff between computation and communication in distributed computing, i.e., the two are inversely proportional to each other. More specifically, a general distributed computing framework, motivated by commonly used structures like MapReduce, is considered, where the overall computation is decomposed into computing a set of “Map” and “Reduce” functions distributedly across multiple computing nodes. A coded scheme, named “coded distributed computing” (CDC), is proposed to demonstrate that increasing the computation load of the Map functions by a factor of r (i.e., evaluating each function at r carefully chosen nodes) can create novel coding opportunities that reduce the communication load by the same factor. An information-theoretic lower bound on the communication load is also provided, which matches the communication load achieved by the CDC scheme. As a result, the optimal computation-communication tradeoff in distributed computing is exactly characterized. Finally, the coding techniques of CDC is applied to the Hadoop TeraSort benchmark to develop a novel CodedTeraSort algorithm, which is empirically demonstrated to speed up the overall job execution by 1.97× -3.39×, for typical settings of interest.

We consider a basic cache network, in which a single server is connected to multiple users via a shared bottleneck link. The server has a database of files (content). Each user has an isolated memory that can be used to cache content in a prefetching phase. In a following delivery phase, each user requests a file from the database, and the server needs to deliver users' demands as efficiently as possible by taking into account their cache contents. We focus on an important and commonly used class of prefetching schemes, where the caches are filled with uncoded data. We provide the exact characterization of the rate-memory tradeoff for this problem, by deriving both the minimum average rate (for a uniform file popularity) and the minimum peak rate required on the bottleneck link for a given cache size available at each user. In particular, we propose a novel caching scheme, which strictly improves the state of the art by exploiting commonality among user demands. We then demonstrate the exact optimality of our proposed scheme through a matching converse, by dividing the set of all demands into types, and showing that the placement phase in the proposed caching scheme is universally optimal for all types. Using these techniques, we also fully characterize the rate-memory tradeoff for a decentralized setting, in which users fill out their cache content without any coordination.

We consider the recently proposed Coded Distributed Computing (CDC) framework [1]-[3] that leverages carefully designed redundant computations to enable coding opportunities that substantially reduce the communication load of distributed computing. We generalize this framework to heterogeneous systems where different nodes in the computing cluster can have different storage (or processing) capabilities. We provide the information-theoretically optimal data set placement and coded data shuffling scheme that minimizes the communication load in a cluster with 3 nodes. For clusters with K > 3 nodes, we provide an algorithm description to generalize our coding ideas to larger networks.

In this paper, we consider a device-to-device communication network in which K transmitter-receiver pairs are sharing spectrum with each other. We propose a novel but simple binary scheduling scheme for this network to maximize the average sum rate of the pairs. According to the scheme, each receiver predicts its Signal-to-Interference-plus-Noise Ratio (SINR), assuming all other user pairs are active, and compares it to a preassigned threshold to decide whether its corresponding transmitter to be activated or not. For our proposed scheme, the optimal threshold that maximizes the expected sum rate is obtained analytically for the two user-pair case and empirically in the general K user-pair case. Simulation results reveal that our proposed SINR-threshold scheduling scheme outperforms ITLinQ [1], FlashLinQ [2] and the method presented in [3] in terms of the expected sum rate (network throughput). In addition, the computational complexity of the proposed scheme is O(K), outperforming both ITLinQ and FlashLinQ that have O(K^2) complexity requirements. Moreover, we also discuss the application of our proposed new scheme into an operator-assisted cellular D2D heterogeneous network.

We consider the problem of interference management in wireless cellular networks with caches at both base stations and receivers and we characterize the degrees-of-freedom (DoF) per cell to within an additive gap of 1 and a multiplicative gap of 2 for all system parameters, under one-shot linear schemes. Our result indicates that the one-shot linear DoF per cell scales linearly with the total amount of cache that is available within each cell. A similar phenomenon had been previously observed for the case of fully-connected wireless networks. Hence, our result demonstrates that it also holds in cellular networks, despite the presence of path loss and fading which results in partial connectivity of the network topology. To establish the result, we propose a randomized and decentralized cache placement and a delivery scheme which, on one hand, utilizes the overlap of contents at base station caches to zero-force part of their outgoing interference, and on the other hand, uses the receiver caches to create coded multicasting opportunities, so that the receivers can eliminate the remaining interference due to undesired packets. We also provide a converse argument to show that our achievable one-shot linear DoF per cell is within an additive gap of 1 and a multiplicative gap of 2 of its optimal value.

To execute cloud computing tasks over a data center hosting hundreds of thousands of server nodes, it is natural to distribute computations across the nodes to take advantage of parallel processing. However, as we allocate more computing resources and further distribute the computations, a large amount of intermediate data must be moved between consecutive computation stages among the nodes, causing the communication load to become the bottleneck. In this paper, we study the optimal resource allocation in distributed computing, in order to minimize the total execution time accounting for the durations of both computation and communication phases. Particularly, we consider a general MapReduce-type framework, and focus on a recently proposed Coded Distributed Computing approach. For all values of problem parameters, we characterize the optimal number of servers that should be used for computing, provide the optimal placements of the Map and Reduce tasks, and propose an optimal coded data shuffling scheme. To prove the optimality of the proposed scheme, we first derive a matching information-theoretic converse on the execution time, then we prove that among all resource allocation schemes that achieve the minimum execution time, our proposed scheme uses the exactly least number of servers.

We characterize the capacity region of the symmetric injective K-user deterministic interference channel for all channel parameters. The achievable rate region is derived by first projecting the achievable rate region of Han-Kobayashi (HK) scheme, which is in terms of common and private rates for each user, along the direction of aggregate rates for each user (i.e., the sum of common and private rates). We then show that the projected region is characterized by only the projection of those facets in the HK region for which the coefficient of common rate and private rate are the same for all users, hence simplifying the region. Furthermore, we derive a tight converse for each facet of the simplified achievable rate region.

We consider a mobile edge computing problem, in which mobile users offload their computation tasks to computing nodes (e.g., base stations) at the network edge. The edge nodes compute the requested functions and communicate the computed results to the users via wireless links. For this problem, we propose a Universal Coded Edge Computing (UCEC) scheme for linear functions to simultaneously minimize the load of computation at the edge nodes, and maximize the physical-layer communication efficiency towards the mobile users. In the proposed UCEC scheme, edge nodes create coded inputs of the users, from which they compute coded output results. Then, the edge nodes utilize the computed coded results to create communication messages that zero-force all the interference signals over the air at each user. Specifically, the proposed scheme is universal since the coded computations performed at the edge nodes are oblivious of the channel states during the communication process from the edge nodes to the users.

We consider a system, containing a library of multiple files and a general memoryless communication network through which a server is connected to multiple users, each equipped with a local isolated cache of certain size that can be used to store part of the library. Each user will ask for one of the files in the library, which needs to be delivered by the server through the intermediate communication network. The objective is to design the cache placement (without prior knowledge of users' future requests) and the delivery phase in order to minimize the (normalized) delivery delay. We assume that the delivery phase consists of two steps: (1) generation of a set of multicast messages at the server, one for each subset of users, and (2) delivery of the multicast messages to the users. In this setting, we show that there exists a universal scheme for cache placement and multicast message generation, which is independent of the underlying communication network between the server and the users, and achieves the optimal delivery delay to within a constant factor for all memoryless networks. We prove this result, even though the capacity region of the underlying communication network is not known, even approximately. This result shows that in the aforementioned setting, a separation between caching and multicast message generation on one hand, and delivering the multicast messages to the users on the other hand is approximately optimal. This result has the important practical implication that the prefetching can be done independent of network structure in the upcoming delivery phase.

In large-scale distributed computing clusters, such as Amazon EC2, there are several types of “system noise” that can result in major degradation of performance: system failures, bottlenecks due to limited communication bandwidth, latency due to straggler nodes, and so on. There have been recent results that demonstrate the impact of coding for efficient utilization of computation and storage redundancy to alleviate the effect of stragglers and communication bottlenecks in homogeneous clusters. In this paper, we focus on general heterogeneous distributed computing clusters consist of a variety of computing machines with different capabilities. We propose a coding framework for speeding up distributed computing in heterogeneous clusters by trading redundancy for reducing the latency of computation. In particular, we propose heterogeneous coded matrix multiplication (HCMM) algorithm for performing distributed matrix multiplication over heterogeneous clusters that are provably asymptotically optimal for a broad class of processing time distributions. Moreover, we show that HCMM is unboundedly faster than any uncoded scheme that partitions the total workload among the workers. To demonstrate how the proposed HCMM scheme can be applied in practice, we provide results from numerical studies and Amazon EC2 experiments comparing HCMM with three benchmark load allocation schemes-uniform uncoded, load-balanced uncoded, and uniform coded. In particular, in our numerical studies, HCMM achieves speedups of up to 73%, 56%, and 42%, respectively, over the three benchmark schemes mentioned earlier. Furthermore, we carry out experiments over Amazon EC2 clusters and demonstrate how HCMM can be combined with rateless codes with nearly linear decoding complexity. In particular, we show that HCMM combined with the Luby transform codes can significantly reduce the overall execution time. HCMM is found to be up to 61%, 46%, and 36% faster than the aforementioned three benchmark schemes, respectively. Additionally, we provide a generalization to the problem of optimal load allocation in heterogeneous settings, where we take into account the monetary costs associated with distributed computing clusters. We argue that HCMM is asymptotically optimal for budget-constrained scenarios as well. In particular, we characterize the minimum possible expected cost associated with a computation task over a given cluster of machines. Furthermore, we develop a heuristic algorithm for (HCMM) load allocation for the distributed implementation of budget-limited computation tasks.

We consider a basic caching system, where a single server with a database of N files (e.g. movies) is connected to a set of K users through a shared bottleneck link. Each user has a local cache memory with a size of M files. The system operates in two phases: a placement phase, where each cache memory is populated up to its size from the database, and a following delivery phase, where each user requests a file from the database, and the server is responsible for delivering the requested contents. The objective is to design the two phases to minimize the load (peak or average) of the bottleneck link. We characterize the rate-memory tradeoff of the above caching system within a factor of 2.00884 for both the peak rate and the average rate (under uniform file popularity), where the best proved characterization in the current literature gives a factor of 4 and 4.7 respectively. Moreover, in the practically important case where the number of files (N) is large, we exactly characterize the tradeoff for systems with no more than 5 users, and characterize the tradeoff within a factor of 2 otherwise. We establish these results by developing novel information theoretic outer-bounds for the caching problem, which improves the state of the art and gives tight characterization in various cases.

We consider a cache network, where a single server is connected to multiple users via a shared bottleneck link. The server has a set of files, which can be cached by each user in a prefetching phase. In a following delivery phase, each user requests a file and the server delivers user demands as efficiently as possible by taking into account their cache contents. We focus on an important and commonly used class of prefetching schemes, where the caches are filled with uncoded data. We provide the exact characterization of rate-memory tradeoff for this problem, by deriving both the minimum average rate (for a uniform file popularity) and the minimum peak rate required on the bottleneck link for a given cache size available at each user. We propose a novel caching scheme, which strictly improves the state of the art by exploiting commonality among user demands. We then demonstrate the exact optimality of our proposed scheme through a matching converse, by dividing the set of all demands into types, and showing that the placement phase in the proposed caching scheme is universally optimal for all types. Using these techniques, we can also fully characterize the rate-memory tradeoff for a decentralized setting, in which users fill out their cache content without coordination.

In this survey paper, we review three recent main results on cache networks, which not only considerably sharpen the approximate characterization of the rate-memory trade off, but also extend those results to more general networks. In these systems, a server with a database of some files (e.g. movies) is connected to multiple users via a communication network. Each user has an isolated memory of limited size that can be used for caching. The system operates in two phases: a placement phase where users each store a portion of the files in their local cache, and a delivery phase, where the users each request a file and the server delivers coded messages to the users, fulfilling their file requests. We start by considering the shared bottleneck network in two flavors of the system, with uncoded prefetching and with coded prefetching. First, for uncoded prefetching, an optimal design is proposed, under both centralized and decentralized settings, for both peak rate and average rate. The exact optimality is proven through a matching converse. Second, for caching with coded prefetching, we present a design that is optimal within a factor of approximately 2, which strictly improves the state of the art. Lastly, we move the focus to more general network topologies, and present an order-wise optimal scheme that is independent of the underlying communication network between the server and the users. This scheme is shown to achieve the minimum delivery delay with a constant factor for all memoryless networks.

We consider a large-scale matrix multiplication problem where the computation is carried out using a distributed system with a master node and multiple worker nodes, where each worker can store parts of the input matrices. We propose a computation strategy that leverages ideas from coding theory to design intermediate computations at the worker nodes, in order to optimally deal with straggling workers. The proposed strategy, named as \emph{polynomial codes}, achieves the optimum recovery threshold, defined as the minimum number of workers that the master needs to wait for in order to compute the output. This is the first code that achieves the optimal utilization of redundancy for tolerating stragglers or failures in distributed matrix multiplication. Furthermore, by leveraging the algebraic structure of polynomial codes, we can map the reconstruction problem of the final output to a polynomial interpolation problem, which can be solved efficiently. Polynomial codes provide order-wise improvement over the state of the art in terms of recovery threshold, and are also optimal in terms of several other metrics including computation latency and communication load. Moreover, we extend this code to distributed convolution and show its order-wise optimality.

We study the symmetric degrees-of-freedom (DoF) of partially connected interference networks under linear coding strategies without channel state information at the transmitters beyond topology. We assume that the receivers are equipped with reconfigurable antennas that can switch among their preset modes. In such a network setting, we characterize the class of network topologies in which half linear symmetric DoF is achievable. Moreover, we derive two general upper bounds on the linear symmetric DoF for arbitrary network topologies. We also demonstrate the tightness of our bounds for the class of network topologies in which all the transmitters in the network have at most two co-interferers.

We study the degrees of freedom (DoFs) of the multiple-input multiple-output X-channel (MIMO XC) with delayed channel state information at the transmitters (delayed CSITs), assuming linear coding strategies at the transmitters. We present two results: 1) the linear sum DoF for MIMO XC with general antenna configurations and 2) the linear DoF region for MIMO XC with symmetric antennas. The converse for each result is based on developing a novel rank-ratio inequality that characterizes the maximum ratio between the dimensions of received linear subspaces at the two multiple-antenna receivers. The achievability of the linear sum DoF is based on a three-phase strategy, in which during the first two phases only the transmitter with fewer antennas exploits delayed CSIT in order to minimize the dimension of its signal at the unintended receiver. During the third phase, both transmitters use delayed CSIT to send linear combinations of past transmissions, such that each receiver receives a superposition of desired message data and known interference, thus simultaneously serving both receivers. We also derive other linear DoF outer bounds for the MIMO XC that, in addition to the outer bounds from the sum DoF converse and the proposed transmission strategy, allow us to characterize the linear DoF region for symmetric antenna configurations.

We introduce the blind index coding (BIC) problem, in which a single sender communicates distinct messages to multiple users over a shared channel. Each user has partial knowledge of each message as side information. However, unlike classical index coding, in BIC, the sender is uncertain of what side information is available to each user. In particular, the sender only knows the amount of bits in each user's side information but not its content. This problem can arise naturally in caching and wireless networks. In order to blindly exploit side information in the BIC problem, we develop a hybrid coding scheme that XORs uncoded bits of a subset of messages with random combinations of bits from other messages. This scheme allows us to strike the right balance between maximizing the transmission rate to each user and minimizing the interference leakage to others. We also develop a general outer bound, which relies on a strong data processing inequality to effectively capture the senders uncertainty about the users' side information. Additionally, we consider the case where communication takes place over a shared wireless medium, modeled by an erasure broadcast channel, and show that surprisingly, combining repetition coding with hybrid coding improves the achievable rate region and outperforms alternative strategies of coping with channel erasure and while blindly exploiting side information.

We consider the problem of non-coherent interference alignment, in which the goal is to align the signals of multiple interfering transmitters at a single receiver where the transmitters are not aware of the channel state information. We cast this problem as a problem of determining rank loss conditions for a column concatenation of full-rank matrices, such that each row of the composing matrices is scaled by a random coefficient. We determine necessary and sufficient conditions for the design of each matrix, such that the random ensemble will almost surely lose rank by a certain amount. The result is proved by converting the problem to determining rank loss conditions for the union of some specific matroids, and then using tools from matroid and graph theories to derive the necessary and sufficient conditions. As an application, we discuss how this result can be applied to the problem of topological interference management, and characterize the linear symmetric degrees of freedom for a class of network topologies.

We consider a system, comprising a library of N files (e.g., movies) and a wireless network with a KTtransmitters, each equipped with a local cache of size of MTfiles and a KRreceivers, each equipped with a local cache of size of MRfiles. Each receiver will ask for one of the N files in the library, which needs to be delivered. The objective is to design the cache placement (without prior knowledge of receivers' future requests) and the communication scheme to maximize the throughput of the delivery. In this setting, we show that the sum degrees-of-freedom (sum-DoF) of {(KTMT+KRMR)/N, KR} is achievable, and this is within a factor of 2 of the optimum, under uncoded prefetching and one-shot linear delivery schemes. This result shows that (i) the one-shot sum-DoF scales linearly with the aggregate cache size in the network (i.e., the cumulative memory available at all nodes), (ii) the transmitters' caches and receivers' caches contribute equally in the one-shot sum-DoF, and (iii) caching can offer a throughput gain that scales linearly with the size of the network. To prove the result, we propose an achievable scheme that exploits the redundancy of the content at transmitter's caches to cooperatively zero-force some outgoing interference, and availability of the unintended content at the receiver's caches to cancel (subtract) some of the incoming interference. We develop a particular pattern for cache placement that maximizes the overall gains of cache-aided transmit and receive interference cancellations. For the converse, we present an integer optimization problem which minimizes the number of communication blocks needed to deliver any set of requested files to the receivers. We then provide a lower bound on the value of this optimization problem, hence leading to an upper bound on the linear one-shot sum-DoF of the network, which is within a factor of 2 of the achievable sum-DoF.

We study the capacity region of the two-user binary fading (or erasure) interference channel, where the transmitters have no knowledge of the channel state information. We develop new inner bounds and outer bounds for this problem. We identify three regimes based on the channel parameters: weak, moderate, and strong interference regimes. Interestingly, this is similar to the generalized degrees of freedom of the two-user Gaussian interference channel, where transmitters have perfect channel knowledge. We show that for the weak interference regime, treating interference as erasure is optimal while for the strong interference regime, decoding interference is optimal. For the moderate interference regime, we provide new inner and outer bounds. The inner bound is based on a modification of the Han-Kobayashi scheme for the erasure channel, enhanced by time-sharing. We study the gap between our inner bound and our outer bounds for the moderate interference regime and compare our results to that of the Gaussian interference channel. Deriving our new outer bounds has three main steps. We first create a contracted channel that has fewer states compared with the original channel, in order to make the analysis tractable. We then prove the correlation lemma that shows an outer bound on the capacity region of the contracted channel and also serves as an outer bound for the original channel. Finally, using the conditional entropy leakage lemma, we derive our outer bound on the capacity region of the contracted channel.

We consider a wireless distributed computing system, in which multiple mobile users, connected wirelessly through an access point, collaborate to perform a computation task. In particular, users communicate with each other via the access point to exchange their locally computed intermediate computation results, which is known as data shuffling. We propose a scalable framework for this system, in which the required communication bandwidth for data shuffling does not increase with the number of users in the network. The key idea is to utilize a particular repetitive pattern of placing the data set (thus a particular repetitive pattern of intermediate computations), in order to provide the coding opportunities at both the users and the access point, which reduce the required uplink communication bandwidth from users to the access point and the downlink communication bandwidth from access point to users by factors that grow linearly with the number of users. We also demonstrate that the proposed data set placement and coded shuffling schemes are optimal (i.e., achieve the minimum required shuffling load) for both a centralized setting and a decentralized setting, by developing tight information-theoretic lower bounds.

We propose a framework for edge-facilitated wireless distributed computing, in which several mobile users connected to an access point collaborate for a distributed computing task. We characterize the minimum communication load, both in uplink (from users to the access point) and downlink (from access point to the users), required for distributed computing. In particular, we develop a communication scheme and a dataset placement strategy that induces a particular overlap of computations at the users, which can then be exploited for coding at both users and the access point to significantly reduce the communication load. We demonstrate that the reduction in communication load (compared to uncoded solutions) can scale linearly with the size of the network (i.e., the number of users), hence our proposed scheme can result in a "scalable" design for edge- facilitated wireless distributed computing (i.e., accommodating any number of users without incurring extra communication load). Furthermore, we establish the optimality of the proposed scheme by developing a tight information theoretic outer- bound, and demonstrate that the proposed scheme achieves the minimum uplink and downlink communication load simultaneously. We also generalize the results to a decentralized setting, in which a random and a priori unknown subset of users may participate in distributed computing at each time, and characterize the minimum communication load for uniformly random dataset placement at users.

This paper studies graph-based active learning, where the goal is to reconstruct a binary signal defined on the nodes of a weighted graph, by sampling it on a small subset of the nodes. A new sampling algorithm is proposed, which sequentially selects the graph nodes to be sampled, based on an aggressive search for the boundary of the signal over the graph. The algorithm generalizes a recent method for sampling nodes in unweighted graphs. The generalization improves the sampling performance using the information gained from the available graph weights. An analysis of the number of samples required by the proposed algorithm is provided, and the gain over the unweighted method is further demonstrated in simulations. Additionally, the proposed method is compared with an alternative state-of-the-art method, which is based on the graph's spectral properties. It is shown that the proposed method significantly outperforms the spectral sampling method, if the signal needs to be predicted with high accuracy. On the other hand, if a higher level of inaccuracy is tolerable, then the spectral method outperforms the proposed aggressive search method. Consequently, we propose a hybrid method, which is shown to combine the advantages of both approaches.

The stochastic block model (SBM) is an important generative model for random graphs in network science and machine learning, useful for benchmarking community detection (or clustering) algorithms. The symmetric SBM generates a graph with 2n nodes which cluster into two equally sized communities. Nodes connect with probability p within a community and q across different communities. We consider the case of p = a ln(n)/n and q = b ln(n)/n. In this case, it was recently shown that recovering the community membership (or label) of every node with high probability (w.h.p.) using only the graph is possible if and only if the Chernoff-Hellinger (CH) divergence D(a; b) = (√a - √a)2≥ 1. In this work, we study if, and by how much, community detection below the clustering threshold (i.e. D(a; b)1-D(a;b). The validity of our results is demonstrated through numerical experiments.

We introduce a general distributed computing framework, motivated by commonly used structures like MapReduce, and formulate an information-theoretic tradeoff between computation and communication in such a framework. We characterize the optimal tradeoff to within a constant factor, for all system parameters. In particular, we propose a coded scheme, namely “Coded MapReduce” (CMR), which creates and exploits coding opportunities in data shuffling for distributed computing, reducing the communication load by a factor that is linearly proportional to the computation load. We then prove a lower bound on the minimum communication load, and demonstrate that CMR achieves this lower bound to within a constant factor. This result reveals a fundamental connection between computation and communication in distributed computing - the two are inverse-linearly proportional to each other.

We consider a system, comprising a library of files (e.g., movies) and a wireless network with an arbitrary number of transmitters and receivers, where each node is equipped with a local cache memory. The system operates in two phases, the prefetching phase, where each cache is pre-populated from the contents of the library, up to its limited size, and then the delivery phase, where each receiver reveals its request for a file from the library, and the system needs to deliver the requested files. The objective is to design the cache placement and the communication scheme to maximize the rate of delivery for arbitrary set of requested files. We characterize the sum degrees-of-freedom (sum-DoF) of this network to within a factor of 2 for all system parameters, under one-shot linear schemes. In particular, we show that the linear sum-DoF scales linearly with the aggregate cache size in the network (i.e., the cumulative memory available at all nodes). The proposed achievable scheme exploits the redundancy of the content at transmitters' caches to cooperatively zero-force some outgoing interference, and availability of the unintended content at the receivers' caches to cancel (subtract) some of the incoming interference. The outer bound is derived by an optimization argument which bounds the number of communication blocks needed to deliver any requested contents to the receivers. This result demonstrates that in this setting, caches at the transmitters' side are equally valuable as the caches at the receivers' side. In addition, it shows that caching can offer a throughput gain that scales linearly with the size of the network.

We study the symmetric degrees-of-freedom (DoF) of partially connected interference networks under linear coding strategies without channel state information at the transmitters beyond topology. We assume that the receivers are equipped with reconfigurable antennas that can switch among their preset modes. In such a network setting, we characterize the class of network topologies in which half linear symmetric DoF is achievable. Moreover, we derive a general upper bound on the linear symmetric DoF for arbitrary network topologies. We also show that this upper bound is tight if the transmitters have at most two co-interferers.

In this paper, we study the communication problem from rovers on Mars' surface to Mars-orbiting satellites. We first justify that, to a good extent, the rover-to-orbiter communication problem can be modeled as communication over a 2 × 2 X-channel with the network topology varying over time. For such a fading X-channel where transmitters are only aware of the time-varying topology but not the time-varying channel state (i.e., no CSIT), we propose coding strategies that code across topologies, and develop upper bounds on the sum degrees-of-freedom (DoF) that is shown to be tight under certain pattern of the topology variation. Furthermore, we demonstrate that the proposed scheme approximately achieves the ergodic sum-capacity of the network. Using the proposed coding scheme, we numerically evaluate the ergodic rate gain over a time-division-multiple-access (TDMA) scheme for Rayleigh and Rice fading channels. We also numerically demonstrate that with practical orbital parameters, a 9.6% DoF gain, as well as more than 11.6% throughput gain can be achieved for a rover-to-orbiter communication network.

We consider the problem of multiple-input single-output broadcast channels with Rayleigh fading where the transmitter has access to delayed knowledge of the channel state information. We first characterize the capacity region of this channel with two users to within constant number of bits for all values of the transmit power. The proposed signaling strategy utilizes the delayed knowledge of the channel state information and the previously transmitted signals, in order to create a signal of common interest for both receivers. This signal would be the quantized version of the summation of the previously transmitted signals. A challenge that arises in deriving the result for finite signal-to-noise ratio regimes is the correlation that exists between the quantization noise and the signal. To guarantee the independence of quantization noise and signal, we extend the framework of lattice quantizers with dither together with an interleaving step. For converse, we use the fact that the capacity region of this problem is upper bounded by the capacity region of a physically degraded broadcast channel with no channel state information where one receiver has two antennas. Then, we derive an outer bound on the capacity region of this degraded broadcast channel. Finally, we show how to extend our results to obtain the approximate capacity of the $K$ -user multiple-input single-output broadcast channel with delayed knowledge of the channel state information at the transmitter to within $2 \log _{2} ( K \,\, + 2 )$ bits/s/Hz.

We study the impact of heterogeneity of channel-state-information available at the transmitters (CSIT) on the capacity of broadcast channels with a multiple-antenna transmitter and k single-antenna receivers (MISO BC). In particular, we consider the k-user MISO BC, where the CSIT with respect to each receiver can be either instantaneous/perfect, delayed, or not available; and we study the impact of this heterogeneity of CSIT on the degrees-of-freedom (DoFs) of such network. We first focus on the three-user MISO BC, and we completely characterize the DoF region for all possible heterogeneous CSIT configurations, assuming linear encoding strategies at the transmitters. The result shows that the state-of-the-art achievable schemes in the literature are indeed sum-DoF optimal, when restricted to linear encoding schemes. To prove the result, we develop a novel bound, called interference decomposition bound, which provides a lower bound on the interference dimension at a receiver which supplies delayed CSIT based on the average dimension of constituents of that interference, thereby decomposing the interference into its individual components. Furthermore, we extend our outer bound on the DoF region to the general k-user MISO BC, and demonstrate that it leads to an approximate characterization of linear sum-DoF to within an additive gap of 0.5 for a broad range of CSIT configurations. Moreover, for the special case where only one receiver supplies delayed CSIT, we completely characterize the linear sum-DoF.

Graph-based methods play an important role in unsupervised and semi-supervised learning tasks by taking into account the underlying geometry of the data set. In this paper, we consider a statistical setting for semi-supervised learning and provide a formal justification of the recently introduced framework of bandlimited interpolation of graph signals. Our analysis leads to the interpretation that, given enough labeled data, this method is very closely related to a constrained low density separation problem as the number of data points tends to infinity. We demonstrate the practical utility of our results through simple experiments.

We introduce an index coding problem over wireless channels where a transmitter broadcasts to multiple receivers through an erasure channel, and receivers have access to some side-information unknown to the transmitter. Such scenarios can arise naturally, for example, in caching networks where users locally store popular files as side-information or in relay networks where users opportunistically overhear transmissions from multiple relays. For this problem, we present a coding scheme based on repetition coding combined with random linear coding, that allows us to send a message to one receiver while blindly exploiting side-information to control interference at the other. Within this class of coding schemes, we identify a tension between number of repetitions and random linear coding, characterize the achievable rate region, and compare the performance of our scheme against that of conventional methods.

We study the impact of heterogeneity of channel state information available to the transmitters (CSIT) on the performance of multi-antenna multi-user wireless networks. More specifically, we consider the 3-user multiple-input single-output (MISO) broadcast channel, where the available CSIT with respect to each receiver can be instantaneous (P), delayed (D), or none (N); and we characterize the extent to which such heterogeneity of CSIT impacts its linear degrees of freedom (LDoF). In particular, we completely characterize the DoF region for all possible CSIT configurations, assuming linear encoding strategies at the transmitters. The converse, which is the main contribution of the paper, is based on a novel lemma, called Interference Decomposition Bound, which provides a lower bound on the interference dimension at a receiver with delayed CSIT, based on the dimension of constituents of that interference, thereby decomposing the interference into its individual components.

We study the problem of interference management in fast fading wireless networks, in which the transmitters are only aware of network topology. We consider a class of retransmission-based schemes, where transmitters in the network are only allowed to resend their symbols in order to assist with the neutralization of interference at the receivers. We introduce a necessary and sufficient condition on the network topology, under which half symmetric degrees-of-freedom (DoF) is achievable through the considered retransmission-based schemes. This corresponds to the “best” topologies since half symmetric DoF is the highest possible value for the symmetric DoF in the presence of interference. We show that when the condition is satisfied, there always exists a set of carefully chosen transmitters in the network, such that by retransmission of their symbols at an appropriate time slot, we can neutralize all the interfering signals at the receivers. Quite surprisingly, we also show that for any given network topology, if we cannot achieve half symmetric DoF by retransmission-based schemes, then there does not exist any linear scheme that can do so. We also consider a practical network scenario that models cell edge users in a heterogeneous network, and show that the characterized condition on the network topology occurs frequently. Furthermore, we numerically evaluate the achievable rates of the DoF-optimal retransmission-based scheme in such network scenario, and show that its throughput gain is not restricted to the asymptotic DoF analysis.

We consider the problem of determining rank loss conditions for a concatenation of full-rank matrices, such that each row of the composing matrices is scaled by a random coefficient. This problem has applications in wireless interference management and recommendation systems. We determine necessary and sufficient conditions for the design of each matrix, such that the random ensemble will almost surely lose rank by a certain amount. The result is proved by converting the problem to determining rank loss conditions for the union of some specific matroids, and then using tools from matroid and graph theories to derive the necessary and sufficient conditions. As an application, we discuss how this result can be applied to the problem of topological interference management, and characterize the linear symmetric degrees of freedom for a class of network topologies.

We introduce the “blind index coding” (BIC) problem, which generalizes the classic index coding problem by considering a sender that has some uncertainty about the side information that is available at each receiver. This problem naturally arises in wireless networks in which users obtain their side information through wireless channels with errors that may be unknown to the sender. For the proposed BIC problem, we develop a new general outer bound by first proving it for the 3-user case and then generalizing its construction to K users. The proof of the outer bound relies on developing a key lemma that uses a strong data processing inequality to account for the sender's uncertainty. We also propose a hybrid coding scheme that XORs random combinations of bits from a subset of messages with uncoded bits of other messages in order to blindly exploit side information, and illustrate its gain.

We study the impact of heterogeneity of channel-state-information available at the transmitters (CSIT) on the capacity of broadcast channels with a multiple-antenna transmitter and k single-antenna receivers (MISO BC). In particular, we consider the k-user MISO BC, where the CSIT with respect to each receiver can be either instantaneous/perfect (P), delayed (D), or not available (N); and we study the impact of this heterogeneity of CSIT on the degrees-of-freedom (DoF) of such network. We develop a general outer bound on the DoF region of k-user MISO BC for all possible heterogeneous CSIT configurations, assuming linear encoding strategies at the transmitter. The outer bound leads to an approximate linear sum-DoF characterization to within 0.5 for a broad range of CSIT configurations. It also leads to an exact characterization of linear sum-DoF for some specific CSIT configurations. Our proof of the outer bound relies on the development of a novel lemma, called Interference Decomposition Bound, which lower bounds the interference dimension at a receiver which supplies delayed CSIT based on the average dimension of constituents of that interference, thereby decomposing it into its components.

In this paper, we study the problem of communication from rovers on Mars' surface to Mars-orbiting satellites (orbiters). We first justify that, to a good extent, the problem can be modelled as communication over a 2×2 Gaussian Xchannel with varying topologies. We then study the capacity of such a channel under the assumption that no channel state information is provided to the transmitters (i.e., no CSIT) other than the network topology. By proposing a strategy that takes advantage of coding across topologies and developing novel upper bounds, we characterize the sum degree-of-freedom (DoF) and the ergodic sum capacity to within a constant gap for the 2×2 X-channel with varying topologies. In addition, we demonstrate the performance gain of the proposed scheme over the baseline time-division-multiple-access (TDMA) scheme currently in use.

We study the problem of communicating a distributed correlated memoryless source over a memoryless network, from source nodes to destination nodes, under quadratic distortion constraints. We establish the following two complementary results: 1) for an arbitrary memoryless network, among all distributed memoryless sources of a given correlation, Gaussian sources are least compressible, that is, they admit the smallest set of achievable distortion tuples and 2) for any memoryless source to be communicated over a memoryless additive-noise network, among all noise processes of a given correlation, Gaussian noise admits the smallest achievable set of distortion tuples. We establish these results constructively by showing how schemes for the corresponding Gaussian problems can be applied to achieve similar performance for (source or noise) distributions that are not necessarily Gaussian but have the same covariance.

It is shown that in the K-user interference channel, if for each user the desired signal strength is no less than the sum of the strengths of the strongest interference from this user and the strongest interference to this user (all values in decibel scale), then the simple scheme of using point-to-point Gaussian codebooks with appropriate power levels at each transmitter and treating interference as noise (TIN) at every receiver (in short, TIN scheme) achieves all points in the capacity region to within a constant gap. The generalized degrees of freedom (GDoF) region under this condition is a polyhedron, which is shown to be fully achieved by the same scheme, without the need for time-sharing. The results are proved by first deriving a polyhedral relaxation of the GDoF region achieved by TIN, and then providing a dual characterization of this polyhedral region via the use of potential functions, and finally proving the optimality of this region in the desired regime.

We consider the two-hop interference channel (IC), which consists of two source-destination pairs communicating with each other via two relays. We analyze the degrees of freedom (DoF) of this network when the relays are restricted to perform linear schemes, and the channel gains are constant (i.e., slow fading). We show that, somewhat surprisingly, by using vector-linear strategies at the relays, it is possible to achieve 4/3 sum-DoF when the channel gains are real. The key achievability idea is to alternate relaying coefficients across time, to create different end-to-end interference structures (or topologies) at different times. Although each of these topologies has only 1 sum-DoF, we manage to achieve 4/3 by coding across them. Furthermore, we develop a novel outer bound that matches our achievability, hence characterizing the sum-DoF of two-hop ICs with linear schemes. We also generalize the result to the multi-antenna setting, where each node has M antennas, and the relays are restricted to one-shot linear schemes. We further extend the result to the case of complex channel gains, by intuitively viewing each complex node with M antennas as a real node with 2M antennas, and characterize the sum-DoF to be 2M - 1/3.

It is well known that ℓ1minimization can be used to recover sufficiently sparse unknown signals from compressed linear measurements. Exact thresholds on the sparsity, as a function of the ratio between the system dimensions, so that with high probability almost all sparse signals can be recovered from independent identically distributed (i.i.d.) Gaussian measurements, have been computed and are referred to as weak thresholds. In this paper, we introduce a reweighted ℓ1recovery algorithm composed of two steps: 1) a standard ℓ1minimization step to identify a set of entries where the signal is likely to reside and 2) a weighted ℓ1minimization step where entries outside this set are penalized. For signals where the nonsparse component entries are independent and identically drawn from certain classes of distributions, (including most well-known continuous distributions), we prove a strict improvement in the weak recovery threshold. Our analysis suggests that the level of improvement in the weak threshold depends on the behavior of the distribution at the origin. Numerical simulations verify the distribution dependence of the threshold improvement very well, and suggest that in the case of i.i.d. Gaussian nonzero entries, the improvement can be quite impressive-over 20% in the example we consider.

We consider partially connected K -user interference networks, where the transmitters have no knowledge about the channel gain values, but they are aware of network topology. We introduce several linear algebraic and graph theoretic concepts to derive new topology-based outer bounds and inner bounds on the symmetric degrees-of-freedom of these networks. We evaluate our bounds for two classes of networks to demonstrate their tightness for most networks in these classes, quantify the gain of our inner bounds over benchmark interference management strategies, and illustrate the effect of network topology on these gains.

When several wireless users are sharing the spectrum, packet collision is a simple, yet widely used model for interference. Under this model, when transmitters cause interference at any of the receivers, their collided packets are discarded and need to be retransmitted. However, in reality, that receiver can still store its analog received signal and utilize it for decoding the packets in the future (for example, by successive interference cancellation techniques). In this work, we propose a physical layer model for wireless packet networks that allows for such flexibility at the receivers. We assume that the transmitters will be aware of the state of the channel (i.e. when and where collisions occur, or an unintended receiver overhears the signal) with some delay, and propose several coding opportunities that can be utilized by the transmitters to exploit the available signal at the receivers for interference management (as opposed to discarding them). We analyze the achievable throughput of our strategy in a canonical interference channel with two transmitter-receiver pairs, and demonstrate the gain over conventional schemes. By deriving an outer-bound, we also prove the optimality of our scheme for the corresponding model.

We establish the sum degrees of freedom of the multiple-input multiple-output X-channel with delayed Channel State Information at the transmitters (CSIT), assuming linear coding strategies at the transmitters. The converse is based on developing a novel rank-ratio inequality that upper bounds the ratio between the dimensions of received linear subspaces at the two receivers. The achievability is based on a three-phase strategy that optimally exploits delayed CSIT in each phase.

We consider the problem of broadcast over wireless erasure networks. To understand the challenges and opportunities of these setups, we study a two-hop erasure broadcast channel consisting of a single source, two relays, and two destinations desiring independent messages. In our network, no transmitter has channel state knowledge of erasures on outgoing links (i.e., no CSIT): The source has no knowledge of any channel state, each relay only has knowledge of the channel states of its incoming link, and destinations are provided with full channel knowledge. We propose a scheme, referred to as Align-and-Forward, that exploits the (unknown) common subspace of received signals at the relays, which results from the source-to-relay broadcast, in order to minimize the dimension of the interference subspace at each destination. We show that Align-and-Forward outperforms available alternative schemes in terms of sum-rate. We also present new outer-bounds and demonstrate the optimality of Align-and-Forward in certain regimes.

We consider the Gaussian wiretap channel with a transmitter, a legitimate receiver, and k eavesdroppers (k ∈ ℕ), where the secure communication is aided via a jammer. We focus on the setting where the transmitter and the jammer are blind with respect to the state of channels to eavesdroppers, and only have access to delayed channel state information (CSI) of the legitimate receiver, which is referred to as “blind cooperative wiretap channel with delayed CSIT”. We show that a strictly positive secure Degrees of Freedom (DoF) of 1 over 3 is achievable irrespective of the number of eavesdroppers (k) in the network, and further, 1 over 3 is optimal assuming linear coding strategies at the transmitters. The converse proof is based on two key lemmas. The first lemma, named Rank Ratio Inequality, shows that if two distributed transmitters employ linear strategies, the ratio of the dimensions of received linear sub-spaces at the two receivers cannot exceed 3/2, due to delayed CSI. The second lemma implies that once the transmitters in a network have no CSI with respect to a receiver, the least amount of alignment will occur at that receiver, meaning that transmit signals will occupy the maximal signal dimensions at that receiver. Finally, we show that once the transmitter and the jammer form a single transmitter with two antennas, which we refer to as MISO wiretap channel, 1 over 2 is the optimal secure DoF when using linear schemes.

We consider the problem of spectrum sharing in device-to-device communication systems. Based on the recently-found condition for the optimality of treating interference as noise, we introduce the new notion of information-theoretic independent set (ITIS) which denotes a subset of users in a wireless network that are information-theoretically eligible to transmit data at the same time. This leads to our novel spectrum sharing scheme called information-theoretic link scheduling (ITLinQ) which at each time slot schedules the users in a single ITIS to transmit simultaneously. We perform a capacity analysis of ITLinQ and in a network model with a random placement of nodes in a cell, we characterize a lower bound on the fraction the information theoretic capacity region that it is able to achieve to within a gap. We will show that ITLinQ can outperform the conventional independent set scheduling by a multiplicative gain that scales with the number of users. We also present a distributed way of implementing ITLinQ and show that it yields a sum-rate gain of higher than 100% over similar state-of-the-art spectrum sharing mechanisms, such as FlashLinQ.

We present a new outer bound for the sum capacity of general multi-unicast deterministic networks. Intuitively, this bound can be understood as applying the cut-set bound to concatenated copies of the original network with a special restriction on the allowed transmit signal distributions. We first study applications to finite-field networks, where we obtain a general outer-bound expression in terms of ranks of the transfer matrices. We then show that, even though our outer bound is for deterministic networks, a result from [1] relating the capacity of AWGN K×K×K networks and the capacity of a deterministic counterpart allows us to establish an outer bound to the DoF of K×K×K wireless networks with general connectivity. This bound is tight in the case of the “adjacent-cell interference” topology, and yields graph-theoretic necessary and sufficient conditions for K DoF to be achievable in general topologies.

We characterize the capacity region of the symmetric two-user Binary Fading Interference Channel where transmitters have no knowledge of the channel state information. We show that the entire capacity region is achieved by applying point-to-point erasure codes with appropriate rates at each transmitter, and using either treat-interference-as-erasure or interference-decoding at each receiver, based on the channel parameters. The result is obtained by developing a novel outer-bound that has three main steps. We first create a contracted channel that has fewer states compared to the original channel, in order to make the analysis tractable. Using a Correlation Lemma, we then show that an outer-bound on the capacity region of the contracted channel also serves as an outer-bound for the original channel. Finally, using a Conditional Entropy Leakage Lemma, we derive our outer-bound on the capacity region of the contracted channel, and show that it coincides with the achievable region by either treat-interference-as-erasure or interference-decoding at each receiver.

We consider the problem of spectrum sharing in device-to-device communication systems. Inspired by the recent optimality condition for treating interference as noise, we define a new concept of information-theoretic independent sets (ITISs), which indicates the sets of links for which simultaneous communication and treating the interference from each other as noise is information-theoretically optimal (to within a constant gap). Based on this concept, we develop a new spectrum sharing mechanism, called information-theoretic link scheduling (ITLinQ), which at each time schedules those links that form an ITIS. We first provide a performance guarantee for ITLinQ by characterizing the fraction of the capacity region that it can achieve in a network with sources and destinations randomly located within a fixed area. Furthermore, we demonstrate how ITLinQ can be implemented in a distributed manner, using an initial two-phase signaling mechanism that provides the required channel state information at all the links. Through numerical analysis, we show that distributed ITLinQ can outperform similar state-of-the-art spectrum sharing mechanisms, such as FlashLinQ, by more than 100% of sum-rate gain, while keeping the complexity at the same level. Finally, we discuss a variation of the distributed ITLinQ scheme, which can also guarantee fairness among the links in the network and numerically evaluate its performance.

The layered interference network is investigated with delayed channel state information (CSI) at all nodes. It is demonstrated how multihopping can be utilized to increase the achievable degrees of freedom (DoF). In particular, a multiphase transmission scheme is proposed for the K-user 2K-hop interference network to systematically exploit the layered structure of the network and delayed CSI to achieve DoF values that scale with K. This result provides the first example of a network with distributed transmitters and delayed CSI whose DoF scales with the number of users.

Computing optimal half-duplex schedules in Gaussian relay networks is a challenging problem due to the lack of an exact capacity characterization and the large number of transmit-receive configurations that must be considered. We approach the problem using a constant-gap capacity approximation based on the cut-set bound with independent encoding at the nodes. We formulate an optimization problem to obtain the cut-set optimal half-duplex schedule and find that it is hard to solve in general. This is because it involves an exponential number of variables, since the number of ways to assign each node to either transmitter or receiver mode is exponential in the number of nodes. We present a general technique that takes advantage of specific structures in the topology of a given network and allows us to reduce the complexity of this problem. In certain classes of network topologies, our approach yields polynomial time algorithms for finding half-duplex schedules that achieve capacity within a constant gap. We use simulations to show running time improvements over alternative methods and compare the performance of various half-duplex scheduling approaches in different SNR regimes.

We establish the degrees of freedom (DoF) of the two-user X-channel with delayed channel knowledge at transmitters [i.e., delayed channel state information at the transmitters (CSIT)], assuming linear coding strategies at the transmitters. We derive a new upper bound and characterize the linear DoF of this network to be 6/5. The converse builds upon our development of a general lemma that shows that, if two distributed transmitters employ linear strategies, the ratio of the dimensions of received linear subspaces at the two receivers cannot exceed 3/2, due to delayed CSIT. As a byproduct, we also apply this general lemma to the three-user interference channel with delayed CSIT, thereby deriving a new upper bound of 9/7 on its linear DoF. This is the first bound that captures the impact of delayed CSIT on the DoF of this network, under the assumption of linear encoding strategies.

We show that fully connected two-hop wireless networks with K sources, K relays, and K destinations have K degrees of freedom both in the case of time-varying channel coefficients and constant channel coefficients (in which case the result holds for almost all values of constant channel coefficients). Our main contribution is a new achievability scheme which we call Aligned Network Diagonalization. This scheme allows the data streams transmitted by the sources to undergo a diagonal linear transformation from the sources to the destinations, thus being received free of interference by their intended destination. In addition, we extend our scheme to multihop networks with fully connected hops, and multihop networks with MIMO nodes, for which the degrees of freedom are also fully characterized.

When data traffic in a wireless network is bursty, small amounts of data sporadically become available for transmission, at times that are unknown at the receivers, and an extra amount of energy must be spent at the transmitters to overcome this lack of synchronization between the network nodes. In practice, predefined header sequences are used with the purpose of synchronizing the different network nodes. However, in networks where relays must be used for communication, the overhead required for synchronizing the entire network may be very significant. In this paper, we study the fundamental limits of energy-efficient communication in an asynchronous diamond network with two relays. We formalize the notion of relay synchronization by saying that a relay is synchronized if the conditional entropy of the arrival time of the source message given the received signals at the relay is small. We show that the minimum energy-per-bit for bursty traffic in diamond networks is achieved with a coding scheme where each relay is either synchronized or not used at all. A consequence of this result is the derivation of a lower bound to the minimum energy-per-bit for bursty communication in diamond networks. This bound allows us to show that schemes that perform the tasks of synchronization and communication separately (i.e., with synchronization signals preceding the communication block) can achieve the minimum energy-per-bit to within a constant fraction that ranges from 2 in the synchronous case to 1 in the highly asynchronous regime.

To study the effect of lack of up-to-date channel state information at the transmitters (CSITs), we consider two-user binary fading interference channels with Delayed-CSIT. We characterize the capacity region for such channels under homogeneous assumption, where channel gains have identical and independent distributions across time and space, eliminating the possibility of exploiting time/space correlation. We introduce and discuss several novel coding opportunities created by outdated CSIT that can enlarge the achievable rate region. The capacity-achieving scheme relies on accurate combination, concatenation, and merging of these opportunities, depending on the channel statistics. The outer-bounds are based on an extremal inequality we develop for a binary broadcast channel with delayed-CSIT. We further extend the results and characterize the capacity region when output feedback links are available from the receivers to the transmitters in addition to the delayed knowledge of the channel state information. We also discuss the extension of our results to the nonhomogeneous setting.

Current works on Information Centric Networking assume the spectrum of caching strategies under the Least Recently/Frequently Used (LRFU) scheme as the de-facto standard, due to the ease of implementation and easier analysis of such strategies. In this paper we predict the popularity distribution of YouTube videos within a campus network. We explore two broad approaches in predicting the popularity of videos in the network: consensus approaches based on aggregate behavior in the network, and social approaches based on the information diffusion over an implicit network. We measure the performance of our approaches under a simple caching framework by picking the k most popular videos according to our predicted distribution and calculating the hit rate on the cache. We develop our approach by first incorporating video inter-arrival time (based on the power-law distribution governing the transmission time between two receivers of the same message in scale-free networks) to the baseline (LRFU), then combining with an information diffusion model over the inferred latent social graph that governs diffusion of videos in the network. We apply techniques from latent social network inference to learn the sharing probabilities between users in the network and apply a virus propagation model borrowed from mathematical epidemiology to estimate the number of times a video will be accessed in the future. Our approach gives rise to a 14% hit rate improvement over the baseline.

The multi-hop layered interference network is investigated with delayed knowledge of channel state information (CSI) at all nodes. It is demonstrated how multi-hopping can be utilized to increase the achievable degrees of freedom (DoF). In particular, for the K-user 2K-hop interference network, a multi-phase transmission scheme is proposed which systematically exploits the layered structure of the network and delayed CSI to achieve DoF values which scale with K. As such, this result provides the first example of a network with distributed transmitters and delayed CSI whose DoF scales with the number of users, although sub-linearly.

We consider the problem of communicating a distributed correlated memoryless source over a memoryless network, from source nodes to destination nodes, under quadratic distortion constraints. We show the following two complementary results: (a) for an arbitrary memoryless network, among all distributed memoryless sources with a particular correlation, Gaussian sources are the worst compressible, that is, they admit the smallest set of achievable distortion tuples, and (b) for any arbitrarily distributed memoryless source to be communicated over a memoryless additive noise network, among all noise processes with a fixed correlation, Gaussian noise admits the smallest achievable set of distortion tuples. In each case, given a coding scheme for the corresponding Gaussian problem, we provide a technique for the construction of a new coding scheme that achieves the same distortion at the destination nodes in a non-Gaussian scenario with the same correlation structure.

Computing the cut-set bound in half-duplex (HD) relay networks is a challenging optimization problem that involves an exponential number of variables and constraints (exponential in the number of nodes in the network). We present a general technique for efficiently computing the HD schedule that maximizes the cut-set bound (with i.i.d. input distribution) in layered Gaussian relay networks. We use simulations to show running time improvements over alternative methods and compare the performance of various HD scheduling approaches in different SNR regimes.

We consider the two-hop interference channel (IC) with constant real channel coefficients, which consists of two source-destination pairs, separated by two relays. We analyze the achievable degrees of freedom (DoF) of such network when relays are restricted to perform scalar amplify-forward (AF) operations, with possibly time-varying coefficients. We show that, somewhat surprisingly, by providing the flexibility of choosing time-varying AF coefficients at the relays, it is possible to achieve 4/3 sum-DoF. We also develop a novel outer bound that matches our achievability, hence characterizing the sum-DoF of two-hop interference channels with time-varying AF relaying strategies.

We study the symmetric degrees-of-freedom (DoF) of partially connected K-user interference networks in which the transmitters are unaware of the actual channel gain values. Several linear algebraic and graph theoretic concepts are introduced to derive new outer and inner bounds on the symmetric DoF for arbitrary network topologies. We evaluate the bounds for a class of networks, showing that the bounds are tight for most topologies in that class, and we also quantify the gains obtained over benchmark schemes.

Summary form only given. Among other extremal properties, Gaussian sources are hardest to compress and communicate over. We review the main results of and exhibiting the generality in which such extremal properties hold in compression, communication and coding over networks. These properties are established via operational arguments, bypassing elusive characterizations of fundamental performance limits: schemes tailored for the Gaussian case are harnessed for constructions of schemes that provably do essentially as well under any other source of the same covariance. The talk will highlight the main ideas behind these constructions and how the results, which were established for memoryless sources and channels, carry over to the presence of memory.

A network where three users want to establish multiple unicasts between each other via a relay is considered. This network is called the Y-channel and resembles an elemental ingredient of future wireless networks. The sum-capacity of this network is studied. A characterization of the sum-capacity within an additive gap of 2 bits, and a multiplicative gap of 4, for all values of channel gains and transmit powers is obtained. Contrary to similar setups where the cut-set bounds can be achieved within a constant gap, they cannot be achieved in our case, where they are dominated by our new genie-aided bounds. Furthermore, it is shown that a time-sharing strategy, in which at each time two users exchange information using coding strategies of the bidirectional relay channel, achieves the upper bounds to within a constant gap. This result is further extended to the${\rm K}$-user case, where it is shown that the same scheme achieves the sum-capacity within$2\log (K-1)$bits.

The proliferation of different wireless access technologies, together with the growing number of multi-radio wireless devices suggest that the opportunistic utilization of multiple connections at the users can be an effective solution to the phenomenal growth of traffic demand in wireless networks. In this paper, we consider the downlink of a wireless network with$N$access points (${\ssr AP}$s) and$M$clients, where each client is connected to several out-of-band${\ssr AP}$s, and requests delay-sensitive traffic (e.g., real-time video). We adopt the framework of Houand study the maximum total timely throughput of the network, denoted by$C_{{\ssr T}^{3}}$, which is the maximum average number of packets delivered successfully before their deadline. Solving this problem is challenging since even the number of different ways of assigning packets to the${\ssr AP}$s is$N^{M}$. We overcome the challenge by proposing a deterministic relaxation of the problem, which converts the problem to a network with deterministic delays in each link. We show that the additive gap between the capacity of the relaxed problem, denoted by$C_{\rm det}$and$C_{{\ssr T}^{3}}$is bounded by$2\sqrt{N(C_{\rm det}+{{N}\over{4}})}$, which is asymptotically negligible compared to$C_{\rm det}$, when the network is operating at high-throughput regime. In addition, our numerical results show that the actual gap between$C_{{\ssr T}^{3}}$and$C_{\rm det}$is in most cases much less than the worst-case gap proven analytically. Moreover, using LP rounding methods we prove that the relaxed problem can be approximated within additive gap of$N$. We extend the analytical results to the case of time-varying channel states, real-time traffic, prioritized traffic, and optimal online policies. Finally, we generalize the model for deterministic relaxation to consider fading, rate adaptation, and multiple simultaneous transmissions.

We consider two-source two-destination (i.e., two-unicast) multihop wireless networks that have a layered structure with arbitrary connectivity. We show that, if the channel gains are chosen independently according to continuous distributions, then, with probability 1, two-unicast layered Gaussian networks can only have 1, 3/2, or 2 sum degrees of freedom (unless both source–destination pairs are disconnected, in which case no degrees of freedom can be achieved). We provide sufficient and necessary conditions for each case based on network connectivity and a new notion of source–destination paths with manageable interference. Our achievability scheme is based on forwarding the received signals at all nodes, except for a small fraction of them in at most two key layers. Hence, we effectively create a “condensed network” that has at most four layers (including the sources layer and the destinations layer). We design the transmission strategies based on the structure of this condensed network. The converse results are obtained by developing information-theoretic inequalities that capture the structures of the network connectivity. Finally, we extend this result and characterize the full degrees of freedom region of two-unicast layered wireless networks.

A classical result in information theory states that the Gaussian noise is the worst-case additive noise in point-to-point channels, meaning that, for a fixed noise variance, the Gaussian noise minimizes the capacity of an additive noise channel. In this paper, we significantly generalize this result and show that the Gaussian noise is also the worst-case additive noise in wireless networks with additive noises that are independent from the transmit signals. More specifically, we show that if we fix the noise variance at each node, then the capacity region with Gaussian noises is a subset of the capacity region with any other set of noise distributions. We prove this result by showing that a coding scheme that achieves a given set of rates on a network with Gaussian additive noises can be used to construct a coding scheme that achieves the same set of rates on a network that has the same topology and traffic demands, but with non-Gaussian additive noises.

In this paper we consider the down link of a heterogeneous wireless network with N Access Points (AP's) and M clients, where each client is connected to several out-of-band AP's, and requests delay-sensitive traffic (e.g., real-time video). We adopt the framework of Hou, Borkar, and Kumar, and study the maximum total timely throughput of the network, denoted by C(T3), which is the maximum average number of packets delivered successfully before their deadline. We propose a deterministic relaxation of the problem, which converts the problem to a network with deterministic delays in each link. We show that the additive gap between the capacity of the relaxed problem denoted by Cdet, and C(T3) is bounded by 2√(N(Cdet+ N/4)), which is asymptotically negligible compared to Cdet, when the network is operating at high-throughput regime. Moreover, using LP rounding methods we prove that the relaxed problem can be approximated in polynomial time with additive gap of N.

An important classical result in Information Theory states that the Gaussian noise is the worst-case additive noise in point-to-point channels. In this paper, we significantly generalize this result and show that, under very mild assumptions, Gaussian noise is also the worst-case additive noise in general wireless networks with additive noises that are independent from the transmit signals. More specifically, we prove that, given a coding scheme with finite reading precision for an AWGN network, one can build a coding scheme that achieves the same rates on an additive noise wireless network with the same topology, where the noise terms may have any distribution with same mean and variance as in the AWGN network.

When data traffic in a wireless network is bursty, small amounts of data sporadically become available for transmission, and the energy cost associated with synchronizing the network nodes prior to each communication block is not negligible. Therefore, designing energy-efficient communication schemes for such asynchronous scenarios is of particular importance. In this paper, we show that, for symmetric diamond networks, by performing the tasks of synchronization and communication separately, it is possible to achieve the minimum energy-per-bit to within a factor that ranges from 2 in the synchronous case to 1 in the highly asynchronous regime.

In this paper, we study the capacity region of the two-user binary fading interference channel with delayed network state information at the transmitters and a noiseless output feedback link from each receiver to its corresponding transmitter. Our results include a new achievability strategy that systematically utilizes the stale network state information and the previously received signals at the receivers, in order to enhance the achievable rate region. We also derive new outer-bounds on the capacity region of such network, and we show that the delay in learning network state information results in some loss in the capacity region.

This paper establishes a connection between the capacity region of the K × K × K wireless network under the AWGN channel model and under a truncated deterministic channel model, which allows any outer bound on the capacity region of the truncated network to be translated into an outer bound on the capacity region of the AWGN network. The result is obtained through the utilization of a recent worst-case noise theorem [1], which shows that perturbing the noise distribution in AWGN networks only increases the capacity region.

We consider the k-encoder source coding problem with a quadratic distortion measure. We show that among all source distributions with a given covariance matrix K, the jointly Gaussian source requires the highest rates in order to meet a given set of distortion constraints.

The capacity region of multi-pair bidirectional relay networks, in which a relay node facilitates the communication between multiple pairs of users, is studied. This problem is first examined in the context of the linear shift deterministic channel model. The capacity region of this network when the relay is operating at either full-duplex mode or half-duplex mode for arbitrary number of pairs is characterized. It is shown that the cut-set upper-bound is tight and the capacity region is achieved by a so called divide-and-conquer relaying strategy. The insights gained from the deterministic network are then used for the Gaussian bidirectional relay network. The strategy in the deterministic channel translates to a specific superposition of lattice codes and random Gaussian codes at the source nodes and successive interference cancelation at the receiving nodes for the Gaussian network. The achievable rate of this scheme with two pairs is analyzed and it is shown that for all channel gains it achieves to within 3 bits/sec/Hz per user of the cut-set upper-bound. Hence, the capacity region of the two-pair bidirectional Gaussian relay network to within 3 bits/sec/Hz per user is characterized.

We consider the two-user interference channel with rate-limited feedback. Related prior works focus on the case where feedback links have infinite capacity, while no research has been done for the rate-limited feedback problem. Several new challenges arise due to the capacity limitations of the feedback links, both in deriving inner bounds and outer bounds. We study this problem under three different interference models: the El Gamal-Costa deterministic model, the linear deterministic model, and the Gaussian model. For the first two models, we develop an achievable scheme that employs three techniques: Han-Kobayashi message splitting, quantize-and-binning, and decode-and-forward. We also derive new outer bounds for all three models and we show the optimality of our scheme under the linear deterministic model. In the Gaussian case, we propose a transmission strategy that incorporates lattice codes, inspired by the ideas developed in the first two models. For symmetric channel gains, we prove that the gap between the achievable sum rate of the proposed scheme and our new outer bounds is bounded by a constant number of bits, independent of the channel gains.

In this paper, we investigate the maximum achievable sum-rate of the two-user Gaussian interference channel with Gaussian superposition coding and successive decoding. We first examine an approximate deterministic formulation of the problem, and introduce the complementarity conditions that capture the use of Gaussian coding and successive decoding. In the deterministic channel problem, we find the constrained sum-capacity and its achievable schemes with the minimum number of messages, first in symmetric channels, and then in general asymmetric channels. We show that the constrained sum-capacity oscillates as a function of the cross link gain parameters between the information theoretic sum-capacity and the sum-capacity with interference treated as noise. Furthermore, we show that if the number of messages of either of the two users is fewer than the minimum number required to achieve the constrained sum-capacity, the maximum achievable sum-rate drops to that with interference treated as noise. We provide two algorithms to translate the optimal schemes in the deterministic channel model to the Gaussian channel model. We also derive two upper bounds on the maximum achievable sum-rate of the Gaussian Han-Kobayashi schemes, which automatically upper bound the maximum achievable sum-rate using successive decoding of Gaussian codewords. Numerical evaluations show that, similar to the deterministic channel results, the maximum achievable sum-rate with successive decoding in the Gaussian channels oscillates between that with Han-Kobayashi schemes and that with single message schemes.

Determining the susceptibility distribution from the magnetic field measured in a magnetic resonance (MR) scanner is an ill-posed inverse problem, because of the presence of zeroes in the convolution kernel in the forward problem. An algorithm called morphology enabled dipole inversion (MEDI), which incorporates spatial prior information, has been proposed to generate a quantitative susceptibility map (QSM). The accuracy of QSM can be validated experimentally. However, there is not yet a rigorous mathematical demonstration of accuracy for a general regularized approach or for MEDI specifically. The error in the susceptibility map reconstructed by MEDI is expressed in terms of the acquisition noise and the error in the spatial prior information. A detailed analysis demonstrates that the error in the susceptibility map reconstructed by MEDI is bounded by a linear function of these two error sources. Numerical analysis confirms that the error of the susceptibility map reconstructed by MEDI is on the same order of the noise in the original MRI data, and comprehensive edge detection will lead to reduced model error in MEDI. Additional phantom validation and human brain imaging demonstrated the practicality of the MEDI method.

We consider two-source two-destination (i.e., two-unicast) multi-hop wireless networks that have a layered structure with arbitrary connectivity. We show that, if the channel gains are independently drawn from continuous distributions, then, with probability 1, two-unicast layered Gaussian networks can only have 1, 3/2 or 2 sum degrees-of-freedom. We provide necessary and sufficient conditions for each case based on the network topology and a new notion of source-destination paths with manageable interference.

In this paper, we investigate the sum-capacity of the two-user Gaussian interference channel with Gaussian superposition coding and successive decoding. We first examine an approximate deterministic formulation of the problem, and introduce the complementarity conditions that capture the use of Gaussian coding and successive decoding. In the deterministic channel problem, we show that the constrained sum-capacity oscillates as a function of the cross link gain parameters between the information theoretic sum-capacity and the sum-capacity with interference treated as noise. Furthermore, we show that if the number of messages of either user is fewer than the minimum number required to achieve the constrained sum-capacity, the maximum achievable sum-rate drops to that with interference treated as noise. We translate the optimal schemes in the deterministic channel model to the Gaussian channel model, and also derive two upper bounds on the constrained sum-capacity. Numerical evaluations show that the constrained sum-capacity in the Gaussian channels oscillates between the sum-capacity with Gaussian Han-Kobayashi schemes and that with single message schemes.

“If we know more, we can achieve more.” This adage also applies to communication networks, where more information about the network state translates into higher sum-rates. In this paper, we formalize this increase of sum-rate with increased knowledge of the network state. The knowledge of network state is measured in terms of the number of hops,h, of information available to each transmitter and is labeled ash-local view. To understand how much capacity is lost due to limited information, we propose to use the metric of normalized sum-capacity, which is theh-local view sum-capacity divided by global-view sum capacity. For the cases of one and two-local view, we characterize the normalized sum-capacity for many classes of deterministic and Gaussian interference networks. In many cases, a scheduling scheme called maximal independent graph scheduling is shown to achieve normalized sum-capacity. We also show that its generalization for 1-local view, labeled coded set scheduling, achieves normalized sum-capacity in some cases where its uncoded counterpart fails to do so.

In a wireless network with a single source and a single destination and an arbitrary number of relay nodes, what is the maximum rate of information flow achievable? We make progress on this long standing problem through a two-step approach. First, we propose a deterministic channel model which captures the key wireless properties of signal strength, broadcast and superposition. We obtain an exact characterization of the capacity of a network with nodes connected by such deterministic channels. This result is a natural generalization of the celebrated max-flow min-cut theorem for wired networks. Second, we use the insights obtained from the deterministic analysis to design a new quantize-map-and-forward scheme for Gaussian networks. In this scheme, each relay quantizes the received signal at the noise level and maps it to a random Gaussian codeword for forwarding, and the final destination decodes the source's message based on the received signal. We show that, in contrast to existing schemes, this scheme can achieve the cut-set upper bound to within a gap which is independent of the channel parameters. In the case of the relay channel with a single relay as well as the two-relay Gaussian diamond network, the gap is 1 bit/s/Hz. Moreover, the scheme is universal in the sense that the relays need no knowledge of the values of the channel parameters to (approximately) achieve the rate supportable by the network. We also present extensions of the results to multicast networks, half-duplex networks, and ergodic networks.

This paper studies the capacity of single-source single-sink noiseless networks under adversarial or arbitrary errors on no more thanzedges. Unlike prior papers, which assume equal capacities on all links, arbitrary link capacities are considered. Results include new upper bounds, network error-correction coding strategies, and examples of network families where our bounds are tight. An example is provided of a network where the capacity is 50% greater than the best rate that can be achieved with linear coding. While coding at the source and sink suffices in networks with equal link capacities, in networks with unequal link capacities, it is shown that intermediate nodes may have to do coding, nonlinear error detection, or error correction in order to achieve the network error-correction capacity.

Cross-layer optimization is a key step in wireless network design that coordinates the resources allocated to different layers in order to achieve globally optimal network performance. Existing work on cross-layer optimization for wireless networks often adopts simplistic physical-layer models for wireless channels, such as treating interference as noise or interference avoidance. This crude modeling of physical layer often leads to inefficient utilization of resources. In this paper, we adopt a deterministic channel model proposed in,, a simple abstraction of the physical layer that effectively captures the effect of channel strength, broadcast and superposition in wireless channels. This model allows us to go beyond “treating interference as noise” and as a consequence are able to achieve higher throughput and utility. Within the network utility maximization (NUM) framework, we study the cross-layer optimization for wireless networks based on this deterministic channel model. First, we extend the well-studied conflict graph model to capture the flow interactions over the deterministic channels and characterize the feasible rate region. Then we study distributed algorithms for general wireless multi-hop networks with both link-centric formulation and node-centric formulation. The convergence of algorithms is proved by applying Lyapunov stability theorem and stochastic approximation method. Further, we show the convergence to the bounded neighborhood of optimal solutions with probability one under constant step sizes and constant update intervals. Our numerical evaluations validate the analytical results and show the advantage of deterministic channel model over simple physical layer models such as treating interference as noise.

It is now well understood that the ℓ1minimization algorithm is able to recover sparse signals from incomplete measurements and sharp recoverable sparsity thresholds have also been obtained for the ℓ1minimization algorithm. However, even though iterative reweighted ℓ1minimization algorithms or related algorithms have been empirically observed to boost the recoverable sparsity thresholds for certain types of signals, no rigorous theoretical results have been established to prove this fact. In this paper, we try to provide a theoretical foundation for analyzing the iterative reweighted ℓ1algorithms. In particular, we show that for a nontrivial class of signals, the iterative reweighted ℓ1minimization can indeed deliver recoverable sparsity thresholds larger than that given in. Our results are based on a high-dimensional geometrical analysis (Grassmann angle analysis) of the null-space characterization for ℓ1minimization and weighted ℓ1minimization algorithms.

Existing work on cross-layer optimization for wireless networks adopts simple physical-layer models, i.e., treating interference as noise. In this paper, we adopt a deterministic channel model proposed in, a simple abstraction of the physical layer that effectively captures the effect of channel strength, broadcast and superposition in wireless channels. Within the Network Utility Maximization (NUM) framework, we study the cross-layer optimization for wireless networks based on this deterministic channel model. First, we extend the well-applied conflict graph model to capture the flow interactions over the deterministic channels and characterize the feasible rate region. Then we study distributed algorithms for general wireless multi-hop networks. The convergence of algorithms is proved by Lyapunov stability theorem and stochastic approximation method. Further, we show the convergence to the bounded neighborhood of optimal solutions with probability one under constant steps and constant update intervals. Our numerical evaluation validates the analytical results.

In distributed wireless networks, nodes often do not have access to complete network information (e.g. network topology, channel gains, etc.). As a result, they have to execute their transmission and reception strategies with partial information about the network, in a distributed fashion. Thus, the key question is how good are the distributed decisions in comparison to the optimal decisions based on full network knowledge. In this paper, we formalize the concept of partial-information sum-capacity by defining normalized sum-capacity, which is defined as the maximum achievable fraction of full-information sum-capacity with a given amount of partial information. We then examine four deterministic networks, multiple access, multiuser Z-channel chain, one-to-many and many-to-one interference channel, and characterize the normalized sum-capacity. For each network, two cases of partial network information are analyzed: (a) each transmitter only knows the channel gains to its receiver, and (b) transmitters knows the channel gains of all links which are no more than two hops away. Quite interestingly, we show that in all eight cases (4 networks × 2 forms of partial information), the normalized sum-capacity is achieved by scheduling subnetworks for which there exist a universally optimal distributed strategy with the available partial information. Furthermore, we show that while actual sum-capacity is not known in all cases, normalized sum-capacity can be in fact be exactly characterized.

It is well known that ℓ1minimization can be used to recover sufficiently sparse unknown signals from compressed linear measurements. In fact, exact thresholds on the sparsity, as a function of the ratio between the system dimensions, so that with high probability almost all sparse signals can be recovered from iid Gaussian measurements, have been computed and are referred to as “weak thresholds”. In this paper, we introduce a reweighted ℓ1recovery algorithm composed of two steps: a standard ℓ1minimization step to identify a set of entries where the signal is likely to reside, and a weighted ℓ1minimization step where entries outside this set are penalized. For signals where the non-sparse component has iid Gaussian entries, we prove a “strict” improvement in the weak recovery threshold. Simulations suggest that the improvement can be quite impressive-over 20% in the example we consider.

In this paper we study the effect of rate-limited feedback on the sum-rate capacity of the deterministic interference channel. We characterize the sum-rate capacity of this channel in the symmetric case and show that having feedback links can increase the sum-rate capacity by at most the rate of the available feedback. Our proof includes a novel upper-bound on the sum-rate capacity and a set of new achievability strategies.

In this paper, we generalize the lossless coded side information problem from the three-node network of Ahlswede and Korner to more general network scenarios. We derive inner and outer bounds on the achievable rate region in the general network scenario and show that they are tight for some families of networks. Our approach demonstrates how solutions to canonical source coding problems can be used to derive bounds for more complex networks and reveals an interesting connection between networks with side information, successive refinement, and network coding.

We study the capacity of the Gaussian two-pair fullduplex directional (or two-way) relay network with a single-relay supporting the communication of the pairs. This network is a generalization of the well known bidirectional relay channel, where we have only one pair of users. We propose a novel transmission technique which is based on a specific superposition of lattice codes and random Gaussian codes at the source nodes. The relay attempts to decode the Gaussian codewords and the superposition of the lattice codewords of each pair. Then it forwards this information to all users. We analyze the achievable rate of this scheme and show that for all channel gains it achieves to within 2 bits/sec/Hz per user of the cut-set upper bound on the capacity region of the two-pair bidirectional relay network.

In this paper we study the compressed sensing problem of recovering a sparse signal from a system of underdetermined linear equations when we have prior information about the probability of each entry of the unknown signal being nonzero. In particular, we focus on a model where the entries of the unknown vector fall into two sets, each with a different probability of being nonzero. We propose a weighted ¿1minimization recovery algorithm and analyze its performance using a Grassman angle approach. We compute explicitly the relationship between the system parameters (the weights, the number of measurements, the size of the two sets, the probabilities of being non-zero) so that an iid random Gaussian measurement matrix along with weighted ¿1minimization recovers almost all such sparse signals with overwhelming probability as the problem dimension increases. This allows us to compute the optimal weights. We also provide simulations to demonstrate the advantages of the method over conventional ¿1optimization.

In this paper we study the capacity of the half-duplex wireless butterfly network, in which a relay node facilitates the communication between two interfering transmitter-receiver pairs. We use the deterministic approach to make progress towards approximating the capacity region of this network. We use the insights obtained from the analysis of the corresponding deterministic problem to derive a new upper bound on the capacity of this network. We also propose a transmission strategy and show that for symmetric channel gains the gap between its achievable rate region and the upper bound is at most equation bits/sec/Hz per user.

In this paper we study the capacity region of the multi-pair bidirectional (or two-way) wireless relay network, in which a relay node facilitates the communication between multiple pairs of users. This network is a generalization of the well known bidirectional relay channel, where we have only one pair of users. We examine this problem in the context of the deterministic channel interaction model, which eliminates the channel noise and allows us to focus on the interaction between signals. We characterize the capacity region of this network when the relay is operating at either full-duplex mode or half-duplex mode (with non adaptive listen-transmit scheduling). In both cases we show that the cut-set upper bound is tight and, quite interestingly, the capacity region is achieved by a simple equation-forwarding strategy.

We present an achievable rate for general Gaussian relay networks. We show that the achievable rate is within a constant number of bits from the information-theoretic cut-set upper bound on the capacity of these networks. This constant depends on the topology of the network, but not the values of the channel gains. Therefore, we uniformly characterize the capacity of Gaussian relay networks within a constant number of bits, for all channel parameters.

We present a deterministic channel model which captures several key features of multiuser wireless communication. We consider a model for a wireless network with nodes connected by such deterministic channels , and compute the end-to-end capacity when there is a single source and a single destination and an arbitrary number of relay nodes. This capacity has the interpretation of the in ax-flow min-cut solution of a wireline network naturally associated with the deterministic wireless network.

In slow-fading scenarios, cooperation between nodes can increase the amount of diversity for communication. We study the performance limit in such scenarios by analyzing the outage capacity of slow fading relay channels. Our focus is on the low signal-to-noise ratio (SNR) and low outage probability regime, where the adverse impact of fading is greatest but so are the potential gains from cooperation. We showed that while the standard Amplify-Forward protocol performs very poorly in this regime, a modified version we called the Bursty Amplify-Forward protocol is optimal and achieves the outage capacity of the network. Moreover, this performance can be achieved without a priori channel knowledge at the receivers. In contrast, the Decode-Forward protocol is strictly suboptimal in this regime. Our results directly yield the outage capacity per unit energy of fading relay channels

In this paper we analyze the outage performance of a slow fading relay channel in the low SNR regime. We present a scheme, called bursty amplify and forward, which achieves the epsi-outage capacity of the relay channel for small outage probabilities epsi, and we give a simple characterization of the outage capacity. Our results directly yield the epsi-outage capacity per unit energy of the channel

We study the reliability of sequential codes in a two-state Markov fading AWGN channel under the assumption of noiseless feedback and an average power constraint. We present a capacity achieving scheme with a doubly exponential anytime reliability function with respect to delay for every bit. The scheme is represented by a hybrid control system at the encoder in which the discrete system dynamics evolves based only on the channel state information while the continuous part of the state at the encoder reflects the evolution of the message uncertainty at the decoder. Whereas the classical Schalkwijk-Kailath scheme achieves double exponential reliability by exploiting the average nature of the power constraint to combat atypicality of the AWGN noise, our scheme also uses it to combat atypical fading realizations

We present the most general form for error control coding using finite field multirate filters. This method shows how different types of codes can easily be generated by multirate filters and filter banks. In all previous works, codes and syndromes were generated using prefilters. We present simple multirate structures for encoding and generating syndromes. We show that all kinds of arbitrary rate K/L, circulant linear codes can be generated by these structures. Then we claim that a similar simple structure exists for syndrome generation in all presented cases.