We study the problem of differentially private (DP) secure multiplication in distributed computing systems, focusing on regimes where perfect privacy and perfect accuracy cannot be simultaneously achieved. Specifically, N nodes collaboratively compute the product of M private inputs while guaranteeing epsilon-DP against any collusion of up to T nodes. Prior work has characterized the fundamental privacy-accuracy trade-off for the multiplication of two multiplicands. In this paper, we extend these results to the more general setting of computing the product of an arbitrary number M of multiplicands. We propose a secure multiplication framework based on carefully designed encoding polynomials combined with layered noise injection. The proposed construction generalizes existing schemes and enables the systematic cancellation of lower-order noise terms, leading to improved estimation accuracy. We explore two regimes: (M-1)T+1 <= N <= MT and N = T+1. For (M-1)T+1 <= N <= MT, we characterize the optimal privacy--accuracy trade-off. When N = T+1, we derive nontrivial achievability and converse bounds that are asymptotically tight in the high-privacy regime.

We consider a private distributed multiplication problem involving$N$computation nodes and$T$colluding nodes. Shamir's secret sharing algorithm provides perfect informationtheoretic privacy, while requiring an honest majority, i.e.,$\mathrm{N} \geq 2 \mathrm{T}+1$. Recent work has investigated approximate computation and characterized privacy-accuracy trade-offs for the honest minority setting ($N \leq 2 \mathrm{T}$) for real-valued data, quantifying privacy leakage via the differential privacy (DP) framework and accuracy via the mean squared error. However, it does not incorporate the error correction capabilities of Shamir's secret-sharing algorithm. This paper develops a new polynomialbased coding scheme for secure multiplication with an honest minority, and characterizes its achievable privacy-utility tradeoff, showing that the tradeoff can approach the converse bound as closely as desired. Unlike previous schemes, the proposed scheme inherits the capability of the Reed-Solomon (RS) code to tolerate erasures and adversaries. We utilize a modified Berlekamp-Welch algorithm over the real number field to detect adversarial nodes.

Distributed computing, which leverages distributed storage and computing resources, is a promising paradigm for handling large-scale computational tasks. However, its potential is often hindered by high communication latency due to limited network bandwidth. In this paper, we study the computation-communication tradeoff of multi-cluster MapReduce systems where a central server connects to multiple clusters, each comprising a set of workers that jointly perform a MapReduce task. Workers can exchange information directly within their cluster (inner-cluster communication) or indirectly through the central server (cross-cluster communication). To reduce the communication load, we propose a nested coded distributed computing (CDC) scheme that is feasible for the heterogeneous scenario where different clusters could have arbitrary numbers of workers and computation loads. It is shown that our scheme can greatly reduce communication load compared to all existing schemes, and could achieve the optimal cross-cluster communication load. In addition, the proposed scheme can significantly reduce the computational complexity of the conventional CDC schemes, whose computational complexity exponentially increases with the computation load.

Distributed multi-task learning (MTL) is a learning paradigm where distributed users simultaneously learn multiple tasks by leveraging the correlations among tasks. However, distributed MTL suffers from a more severe communication bottleneck than single-task learning as more than one models need to be transmitted in the communication phase. To address this issue, we investigate the hierarchical MTL system where distributed users wish to jointly learn different learning models orchestrated by a central server with the help of multiple relays. We propose a coded distributed computing scheme for hierarchical MTL systems that jointly exploits the network topology and relays’ computing capability to create coded multicast opportunities to improve communication efficiency. We theoretically prove that the proposed scheme can significantly reduce the communication loads both in the uplink and downlink transmissions between relays and the server. To further illustrate the optimality of the proposed scheme, we derive information-theoretic lower bounds on the minimum uplink and downlink communication loads and prove that the gaps between achievable upper bounds and lower bounds are within the minimum number of connected users among all relays. In particular, when the network topology can be delicately designed, the proposed scheme can achieve the information-theoretic optimal communication loads. Experiments on real-world datasets show that our proposed scheme can greatly reduce the overall training time compared to the conventional hierarchical MTL scheme.

In this paper, we consider a hierarchical distributed multi-task learning (MTL) system where distributed users wish to jointly learn different models orchestrated by a central server with the help of a layer of multiple relays. Since the users need to download different learning models in the downlink transmission, the distributed MTL suffers more severely from the communication bottleneck compared to the single-task learning system. To address this issue, we propose a coded hierarchical MTL scheme that exploits the connection topology and introduces coding techniques to reduce communication loads. It is shown that the proposed scheme can significantly reduce the communication loads both in the uplink and downlink transmissions between relays and the server. Moreover, we provide informationtheoretic lower bounds on the optimal uplink and downlink communication loads, and prove that the gaps between achievable upper bounds and lower bounds are within the minimum number of connected users among all relays.

Distributed multi-task learning (MTL) can jointly learn multiple models and achieve better generalization performance by exploiting relevant information between the tasks. However, distributed MTL suffers from communication bottlenecks, in particular for large-scale learning with a massive number of tasks. This paper considers distributed MTL systems where distributed workers wish to learn different models orchestrated by a central server. To mitigate communication bottlenecks both in the uplink and downlink, we propose coded computing schemes for flexible and fixed data placements, respectively. Our schemes can significantly reduce communication loads by exploiting workers’ local information and creating multicast opportunities for both the server and workers. Moreover, we establish information-theoretic lower bounds on the optimal downlink and uplink communication loads, and prove the approximate optimality of the proposed schemes. For flexible data placement, our scheme achieves theoptimaldownlink communication load, and theorder optimaluplink communication load that is smaller than 2 times of the information-theoretic optimum. For fixed data placement, the gaps between our communication load and the optimum are within the minimum computation load among all workers, regardless of the number of workers. Experiments demonstrate that our schemes can significantly speed up the training process compared to the traditional approach.

Consider a distributed multi-task learning (MTL) framework where the distributed users first train their own models based on the local data and then send the local updates to the server, and the server sends back helpful information by which each user can learn its task independently. Compared to the single-task case, the distributed MTL suffers more severely from the communication bottleneck, because the users wish to learn multiple models, causing the downlink communication load to linearly increase with the total number of tasks. In this paper, we propose a novel scheme named coded distributed multi-task learning, to reduce the communication loads both in the uplink and downlink. The key idea is to exploit the local information stored at the users during the local training, and utilize a particular repetitive placement and computation on the publicly shared dataset such that coded multicasting opportunities can be created at the server and users. Our method for the first time applies coding strategy to reduce the communication cost for distributed MTL framework. Experiments on real-world dataset show that the proposed scheme can substantially reduce the communication load compared to the traditional uncoded approach.