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)

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 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.

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.

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.

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.

In this paper, we study the problem of optimal topology design in wireless networks equipped with highly-directional transmission antennas. We use the 1-2-1 network model to characterize the optimal placement of two relays that assist the communication between a source-destination pair. We analytically show that under some conditions on the distance between the source-destination pair, the optimal topology in terms of maximizing the network throughput is to place the relays as close as possible to the source and the destination.

Millimeter wave (mmWave) communication is expected to play a central role in next generation mobile systems (5G) and beyond, by providing multi-Gbps data rates. However, the severe pathloss and sensitivity to blockages at mmWave frequencies significantly challenge practical implementations. One effective way to mitigate these effects and to increase the communication range is beamforming in combination with relaying. In this paper, we study the beam scheduling problem for mmWave half-duplex (HD) relay networks, where the relay topology can be arbitrary. Based on theoretically optimal scheduling results, we first implement a network simplification procedure to reduce the network topology complexity, and then propose two practically relevant beam scheduling schemes: the deterministic edge coloring (EC) scheduler and the adaptive backpressure (BP) scheduler. The former consists of a very simple one-time computation of the sequence of scheduling states, which is then repeated periodically. The one-time computation depends on the underlying network topology, and therefore it must be repeated when such topology changes. As such, this approach is more suited to quasi-static scenarios. The latter is an “online” approach which updates scheduling weights and solves at each time slots a weighted sum rate maximization. Hence, it's computational complexity may be significantly higher than that of EC, but it is better suited to dynamic time-varying scenarios. With the aid of computer simulations, we show that both the proposed schedulers guarantee network stability within the network capacity. Particularly, in comparison with two baseline schemes, the proposed schedulers achieve much smaller queuing backlogs, much smaller backlog fluctuations, and much lower packet end-to-end delays.

This paper proposes a new model for wireless relay networks referred to as “1-2-1 network”, where two nodes can communicate only if they point “beams” at each other, otherwise no signal can be exchanged or interference can be generated. This model is motivated by millimeter wave communications where, due to the high path loss, a link between two nodes can exist only if beamforming gain at both sides is established, while in the absence of beamforming gain the signal is received well below the thermal noise floor. The main contributions in this paper include: (a) the development of a constant gap approximation for the unicast and multicast capacities of the proposed network model, i.e., a characterization of the network unicast and multicast capacities to within an additive gap, which only depends on the number of nodes and is independent of the channel coefficients and operating SNR; and (b) the design of algorithms that run in polynomial time in the number of nodes and compute the approximate unicast and multicast capacities, as well as their corresponding optimal beam scheduling strategies. These results are derived both forfull-duplexandhalf-duplexmodes of operation at the relays: while in full-duplex the transmit and receive beams at a relay can be simultaneously active, in half-duplex only one can be active at each point in time. The relation between the approximate multicast capacity and minimum unicast capacity is explored in full-duplex 1-2-1 networks and shown to be dependent on the network structure and the number of destinations, unlike in classical wireless (i.e., without 1-2-1 constraints) full-duplex networks. Finally, network simplification results are proved for the 1-2-1 network model by exploiting the structure of the linear program that represents the approximate capacity.

Fully autonomous vehicles need the ability to localize without external help, for instance by using visual sensors together with a pre-loaded map of landmarks. In this paper we connect self-localization using landmarks with coding theory. This connection enables to translate Hamming distance properties to probabilistic localization guarantees given a certain number of errors in landmark identification; it also enables to leverage existing polynomial time decoding algorithms for localization. We present promising numerical evaluation results by simulating vehicle traveling paths along a road network generated from real data of a region in Washington D.C.

In this work, we study bounds on the capacity of full-duplex Gaussian 1-2-1 networks with imperfect beamforming. In particular, different from the ideal 1-2-1 network model introduced in [1], in this model beamforming patterns result in side-lobe leakage that cannot be perfectly suppressed. The 1-2-1 network model captures the directivity of mmWave network communications, where nodes communicate by pointing main-lobe "beams" at each other. We characterize the gap between the approximate capacities of the imperfect and ideal 1-2-1 models for the same channel coefficients and transmit power. We show that, under some conditions, this gap only depends on the number of nodes. Moreover, we evaluate the achievable rate of schemes that treat the resulting side-lobe leakage as noise, and show that they offer suitable solutions for implementation.

This paper studies the problem of secure communication over noiseless 1-2-1 networks, an abstract model for networks with directional communication capabilities such as mmWave networks. A secure transmission scheme is designed and shown to achieve a secure rate that is larger than state-of-the-art lower bounds for a class of 1-2-1 network topologies. The proposed scheme leverages the scheduling nature of 1-2-1 networks, the network topology, as well as storage at intermediate nodes to create shared randomness with the source to improve the secure rate. Finally, a novel outer bound is derived and shown to match the achievability bound under certain network conditions, hence characterizing the secure capacity in such regimes.

This paper investigates the problem of characterizing the capacity of Half-Duplex (HD) line networks, where a source node communicates to a destination node through a multihop path of N relays. If the relays operate in Full-Duplex (FD), it is well known that the capacity of the line network equals the minimum among the point-to-point link capacities in the path. In contrast, this paper considers a different case where the relays operate in HD. In the first part of the paper, it is shown that the approximate capacity (optimal up to a constant additive gap that only depends on the number of nodes in the network) of an HD N-relay line network equals half the minimum of the harmonic means of the point-to-point link capacities of each two consecutive links in the path. It is then proved that the N +1 listen/transmit states (out of the 2Npossible ones) sufficient to characterize the approximate capacity can be found in linear time. In the second part of the paper, it is shown that the problem of finding the path that has the largest HD approximate capacity in a network that can be represented as a graph is NP-hard. However, if the number of cycles in the network is polynomial in the number of nodes, then a polynomial-time algorithm can indeed be designed.

This paper explores the network simplification problem for Gaussian full-duplex relay networks with arbitrary topology. Particularly, given an N-relay Gaussian full-duplex network, the network simplification problem seeks to find fundamental guarantees on the capacity of the best subnetwork, among a particular class of subnetworks, as a fraction of the full-network capacity. The focus of this work is the case when the selected subnetwork class is a path from the source to the destination. The main result of the paper shows that for an N-relay Gaussian networks with arbitrary topology, the best route can in the worst case guarantee an approximate fraction 1/(⌊N/2⌋ + 1) of the capacity of the full network, independently of the channel coefficients and/or operating SNR. Furthermore, this guarantee is shown to be fundamental, i.e., it is the highest worst-case guarantee that can be provided for routing in relay networks. A key step in the proof of the main result lies in the derivation of a simplification result for antenna selection in MIMO channels that may also be of independent interest. To the best of our knowledge, this is the first result that characterizes the performance of routing in comparison to physical layer cooperation techniques that approximately achieve the network capacity for general wireless network topologies. The results in this paper show that routing can, in the worst case, result in an unbounded gap from the network capacity - or reversely, physical layer cooperation can offer unbounded gains over routing.

This paper studies the 1-2-1 half-duplex network model, where two half-duplex nodes can communicate only if they point "beams" at each other; otherwise, no signal can be exchanged or interference can be generated. The main result of this paper is the design of two polynomial-time algorithms that: (i) compute the approximate capacity of the 1-2-1 half-duplex network and, (ii) find the network schedule optimal for the approximate capacity. The paper starts by expressing the approximate capacity as a linear program with an exponential number of constraints. A core technical component consists of building a polynomial-time separation oracle for this linear program, by using algorithmic tools such as perfect matching polytopes and Gomory-Hu trees.

This paper studies the multicast capacity of full-duplex 1-2-1 networks. In this model, two nodes can communicate only if they point "beams" at each other; otherwise, no signal can be exchanged. The main result of this paper is that the approximate multicast capacity can be computed by solving a linear program in the activation times of links connecting pairs of nodes. This linear program has two appealing features: (i) it can be solved in polynomial-time in the number of nodes; (ii) it allows to efficiently find a network schedule optimal for the approximate capacity. Additionally, the relation between the approximate multicast capacity and the minimum approximate unicast capacity is studied. It is shown that the ratio between these two values is not universally equal to one, but it depends on the number of destinations in the network, as well as graph-theoretic properties of the network.

In many machine learning applications, once we have learned a classifier, in order to apply it, we may still need to gather features from distributed sensors over communication constrained channels. In this paper, we propose a polynomial complexity algorithm for feature quantization tailored to minimizing the classification error of a linear classifier. Our scheme produces scalar quantizers that are well-tailored to delay-sensitive applications, operates on the same training data used to learn the classifier, and allows each distributed sensor to operate independently of each other. Numerical evaluation indicates up to 65% benefits over alternative approaches. Additionally, we provide an example where, jointly designing the linear classifier and the quantization scheme, can outperform sequential designs.

This paper explores the network simplification problem in the context of Gaussian half-duplex diamond networks. Specifically, given an N-relay diamond network, this problem seeks to derive fundamental guarantees on the capacity of the best k-relay subnetwork, as a function of the full network capacity. Simplification guarantees are presented in terms of a particular approximate capacity, termed Independent-Gaussian (IG) approximate capacity, that characterizes the network capacity to within an additive gap, which is independent of the channel coefficients and operating SNR. The main focus of this work is when k = N-1 relays are selected out of N relays in a diamond network. First, a simple algorithm is proposed which selects all relays except the one with the minimum IG approximate half-duplex capacity. It is shown that the selected (N -1)-relay subnetwork has an IG approximate half-duplex capacity that is at least 1/2 of the IG approximate half-duplex capacity of the full network and that for the proposed algorithm, this guarantee is tight. Furthermore, this work proves the following tight fundamental guarantee: there always exists a subnetwork of k = N - 1 relays that have an IG approximate half-duplex capacity that is at least equal to (N - 1)/N of the IG approximate half-duplex capacity of the full network. Finally, these results are extended to derive lower bounds on the fraction guarantee when k ∈ [1 : N] relays are selected. The key steps in the proofs lie in the derivation of properties of submodular functions, which provide a combinatorial handle on the network simplification problem for Gaussian half-duplex diamond networks.

This paper starts by assuming a 1-2-1 network, the abstracted noiseless model of mmWave networks that was shown to closely approximate the Gaussian capacity in [1], and studies secure communication. First, the secure capacity is derived for 1-2-1 networks where a source is connected to a destination through a network of unit capacity links. Then, lower and upper bounds on the secure capacity are derived for the case when source and destination have more than one beam, which allow them to transmit and receive in multiple directions at a time. Finally, secure capacity results are presented for diamond 1-2-1 networks when edges have different capacities.

This paper proposes a new model for wireless relay networks referred to as “1-2-1 network”, where two nodes can communicate only if they point “beams” at each other, while if they do not point beams at each other, no signal can be exchanged or interference can be generated. This model is motivated by millimeter wave communications where, due to the high path loss, a link between two nodes can exist only if beamforming gain at both sides is established, while in the absence of beamforming gain the signal is received well below the thermal noise floor. The main result in this paper is that the 1-2-1 network capacity can be approximated by routing information along at most 2N + 2 paths, where N is the number of relays connecting a source and a destination through an arbitrary topology.

The problem of operating a Gaussian Half-Duplex (HD) relay network optimally is challenging due to the exponential number of listen/transmit network states that need to be considered. Recent results have shown that, for the class of Gaussian HD networks with N relays, there always exists a simple schedule, i.e., with at most N+1 active states, that is sufficient for approximate (i.e., up to a constant gap) capacity characterization. This paper investigates how to efficiently find such a simple schedule over line networks. Towards this end, a polynomial-time algorithm is designed and proved to output a simple schedule that achieves the approximate capacity. The key ingredient of the algorithm is to leverage similarities between network states in HD and edge coloring in a graph. It is also shown that the algorithm allows to derive a closed-form expression for the approximate capacity of the Gaussian line network that can be evaluated distributively and in linear time.

In this paper, we revisit the communication vs. distributed computing trade-off, studied within the framework of MapReduce in [1]. An implicit assumption in the aforementioned work is that each server performs all possible computations on all the files stored in its memory. Our starting observation is that, if servers can compute only the intermediate values they need, then storage constraints do not directly imply computation constraints. We examine how this affects the communication-computation trade-off and suggest that the trade-off be studied with a predetermined storage constraint. We then proceed to examine the case where servers need to perform computationally intensive tasks, and may not have sufficient time to perform all computations required by the scheme in [1]. Given a threshold that limits the computational load, we derive a lower bound on the associated communication load, and propose a heuristic scheme that achieves in some cases the lower bound.

We consider an arbitrary layered Gaussian relay network with L layers of N relays each, from which we select subnetworks with K relays per layer. We prove that: (i) For arbitrary L;N and K = 1, there always exists a subnetwork that approximately achieves 2/(L-1)N+4 (resp. 2/LN+2) of the network capacity for odd L (resp. even L), (ii) For L = 2; N = 3; K = 2, there always exists a subnetwork that approximately achieves 1/2 of the network capacity. We also provide example networks where even the best subnetworks achieve exactly these fractions (up to additive gaps). Along the way, we derive some results on MIMO antenna selection and capacity decomposition that may also be of independent interest.

In this paper, PNCR, a routing framework based on Physical Network Coding is proposed. PNCR enables shared utilization of the channel during the broadcast and multiple access phases of transmissions. These additional transmission opportunities can be observed as performance gains in terms of less packet delays and better network throughput. In this paper, we discuss the details of our proposed framework to utilize the virtues presented by Physical Network Coding. Existing work on Physical Network Coding is theoretic and does not present itself as a tool for multi-hop network deployment except for limited network topologies. Our work in this paper is an effort to utilize such techniques for networks of arbitrary structure. We evaluate the performance of our proposed framework using simulations and show that it achieves better throughput and less delivery delay per packet than conventional wireless routing solutions without Physical Network Coding.

In this paper, we investigate a spectrum-sensing algorithm for detecting spatial dimension holes in Multiple-Input Multiple-Output (MIMO) transmissions for OFDM systems using Compressive Sensing (CS) tools. This extends the energy detector to allow for detecting transmission opportunities even if the band is already energy filled. We show that the task described above is not performed efficiently by regular MIMO decoders (such as MMSE decoder) due to possible sparsity in the transmit signal. Since CS reconstruction tools take into account the sparsity order of the signal, they are more efficient in detecting the activity of the users. Building on successful activity detection by the CS detector, we show that the use of a CS-aided MMSE decoder yields better performance rather than using either CS-based or MMSE decoders separately.