Wei-Ting Chang

Mohamed Seif, Wei-Ting Chang, Ravi Tandon

In this paper, we study the problem of federated learning over a wireless channel with user sampling, modeled by a Gaussian multiple access channel, subject to central and local differential privacy (DP/LDP) constraints. It has been shown that the superposition nature of the wireless channel provides a dual benefit of bandwidth efficient gradient aggregation, in conjunction with strong DP guarantees for the users. Specifically, the central DP privacy leakage has been shown to scale as $\mathcal{O}(1/K^{1/2})$, where $K$ is the number of users. It has also been shown that user sampling coupled with orthogonal transmission can enhance the central DP privacy leakage with the same scaling behavior. In this work, we show that, by join incorporating both wireless aggregation and user sampling, one can obtain even stronger privacy guarantees. We propose a private wireless gradient aggregation scheme, which relies on independently randomized participation decisions by each user. The central DP leakage of our proposed scheme scales as $\mathcal{O}(1/K^{3/4})$. In addition, we show that LDP is also boosted by user sampling. We also present analysis for the convergence rate of the proposed scheme and study the tradeoffs between wireless resources, convergence, and privacy theoretically and empirically for two scenarios when the number of sampled participants are $(a)$ known, or $(b)$ unknown at the parameter server.

Chao-Lin Liu, Chang-Ting Chu, Wei-Ting Chang et al.

We consider three major text sources about the Tang Dynasty of China in our experiments that aim to segment text written in classical Chinese. These corpora include a collection of Tang Tomb Biographies, the New Tang Book, and the Old Tang Book. We show that it is possible to achieve satisfactory segmentation results with the deep learning approach. More interestingly, we found that some of the relative superiority that we observed among different designs of experiments may be explainable. The relative relevance among the training corpora provides hints/explanation for the observed differences in segmentation results that were achieved when we employed different combinations of corpora to train the classifiers.

Wei-Ting Chang, Ravi Tandon

In this work, we study the problem of federated learning (FL), where distributed users aim to jointly train a machine learning model with the help of a parameter server (PS). In each iteration of FL, users compute local gradients, followed by transmission of the quantized gradients for subsequent aggregation and model updates at PS. One of the challenges of FL is that of communication overhead due to FL's iterative nature and large model sizes. One recent direction to alleviate communication bottleneck in FL is to let users communicate simultaneously over a multiple access channel (MAC), possibly making better use of the communication resources. In this paper, we consider the problem of FL learning over a MAC. In particular, we focus on the design of digital gradient transmission schemes over a MAC, where gradients at each user are first quantized, and then transmitted over a MAC to be decoded individually at the PS. When designing digital FL schemes over MACs, there are new opportunities to assign different amount of resources (such as rate or bandwidth) to different users based on a) the informativeness of the gradients at each user, and b) the underlying channel conditions. We propose a stochastic gradient quantization scheme, where the quantization parameters are optimized based on the capacity region of the MAC. We show that such channel aware quantization for FL outperforms uniform quantization, particularly when users experience different channel conditions, and when have gradients with varying levels of informativeness.

Wei-Ting Chang, Ravi Tandon

In this paper, we study the problem of secure and private distributed matrix multiplication. Specifically, we focus on a scenario where a user wants to compute the product of a confidential matrix $A$, with a matrix $B_θ$, where $θ\in\{1,\dots,M\}$. The set of candidate matrices $\{B_1,\dots,B_M\}$ are public, and available at all the $N$ servers. The goal of the user is to distributedly compute $AB_θ$, such that $(a)$ no information is leaked about the matrix $A$ to any server; and $(b)$ the index $θ$ is kept private from each server. Our goal is to understand the fundamental tradeoff between the upload vs download cost for this problem. Our main contribution is to show that the lower convex hull of following (upload, download) pairs: $(U,D)=(N/(K-1),(K/(K-1))(1+(K/N)+\dots+(K/N)^{M-1}))$ for $K=2,\dots,N$ is achievable. The scheme improves upon state-of-the-art existing schemes for this problem, and leverages ideas from secret sharing and coded private information retrieval.

Wei-Ting Chang, Ravi Tandon

Matrix multiplication is a fundamental building block for large scale computations arising in various applications, including machine learning. There has been significant recent interest in using coding to speed up distributed matrix multiplication, that are robust to stragglers (i.e., machines that may perform slower computations). In many scenarios, instead of exact computation, approximate matrix multiplication, i.e., allowing for a tolerable error is also sufficient. Such approximate schemes make use of randomization techniques to speed up the computation process. In this paper, we initiate the study of approximate coded matrix multiplication, and investigate the joint synergies offered by randomization and coding. Specifically, we propose two coded randomized sampling schemes that use (a) codes to achieve a desired recovery threshold and (b) random sampling to obtain approximation of the matrix multiplication. Tradeoffs between the recovery threshold and approximation error obtained through random sampling are investigated for a class of coded matrix multiplication schemes.

Wei-Ting Chang, Ravi Tandon

Matrix multiplication is one of the key operations in various engineering applications. Outsourcing large-scale matrix multiplication tasks to multiple distributed servers or cloud is desirable to speed up computation. However, security becomes an issue when these servers are untrustworthy. In this paper, we study the problem of secure distributed matrix multiplication from distributed untrustworthy servers. This problem falls in the category of secure function computation and has received significant attention in the cryptography community. However, the fundamental limits of information-theoretically secure matrix multiplication remain an open problem. We focus on information-theoretically secure distributed matrix multiplication with the goal of characterizing the minimum communication overhead. The capacity of secure matrix multiplication is defined as the maximum possible ratio of the desired information and the total communication received from $N$ distributed servers. In particular, we study the following two models where we want to multiply two matrices $A\in\mathbb{F}^{m\times n}$ and $B\in\mathbb{F}^{n\times p}$: $(a)$ one-sided secure matrix multiplication with $\ell$ colluding servers, in which $B$ is a public matrix available at all servers and $A$ is a private matrix. $(b)$ fully secure matrix multiplication with $\ell$ colluding servers, in which both $A$ and $B$ are private matrices. The goal is to securely multiply $A$ and $B$ when any $\ell$ servers can collude. For model $(a)$, we characterize the capacity as $C_{\text{one-sided}}^{(\ell)}=(N-\ell)/N$ by providing a secure matrix multiplication scheme and a matching converse. For model $(b)$, we propose a novel scheme that lower bounds the capacity, i.e., $C_{\text{fully}}^{(\ell)}\geq (\lceil \sqrt{N}-\ell \rceil)^2/(\lceil \sqrt{N}-\ell \rceil+\ell)^2$.