An Uplink Communication-Efficient Approach to Featurewise Distributed Sparse Optimization With Differential Privacy

In sparse empirical risk minimization (ERM) models, when sensitive personal data are used, e.g., genetic, healthcare, and financial data, it is crucial to preserve the differential privacy (DP) in training. In many applications, the information (i.e., features) of an individual is held by different organizations, which give rise to the prevalent yet challenging setting of the featurewise distributed multiparty model training. Such a setting is also beneficial to the scalability when the number of features exceeds the computation and storage capacity of a single node. However, existing private sparse optimizations are limited to centralized and samplewise distributed datasets only. In this article, we develop a differentially private algorithm for the sparse ERM model training under the featurewise distributed datasets setting. Our algorithm comes with guaranteed DP, nearly optimal utility, and reduced uplink communication complexity. Accordingly, we present a more generalized convergence analysis for block-coordinate Frank–Wolfe (BCFW) under arbitrary sampling (denoted as BCFW-AS in short), which significantly extends the known convergence results that apply to two specific sampling distributions only. To further reduce the uplink communication cost, we design an active private feature sharing scheme, which is new in both design and analysis of BCFW, to guarantee the convergence of communicating Johnson–Lindenstrauss transformed features. Empirical studies justify the new convergence as well as the nearly optimal utility theoretical results.

I. Introduction

Sparse empirical risk minimization (ERM) [1]–[4] is an important machine learning model, which learns from data collected from individuals. Despite its usefulness and the large body of research for improving its efficiency [5]–[7], its involvement of sensitive individual data poses increasing privacy concerns, especially in applications of healthcare, financial, and biomedicine. To avoid breaching the privacy of the individuals, privacy-preserving techniques have been developed to ensure that the adversary cannot infer any individual data from the output of the learning process. Beginning with the seminal work [8], which proposes to carry out the private ERM training under the formal statistical differential privacy (DP) notion [9], different types of differentially private optimization algorithms have been developed to suit various computing contexts. In particular, existing works focus on training the model with centralized datasets [10]–[14] and samplewise distributed datasets [15]–[18]. For example, when samples distribute among user sites, Lou et al. [16] and Han et al. [18] proposed privacy-preserving strategies for the stochastic (sub) gradient (SGD) method to avoid sensitive user information leakage during distributed optimization. Agarwal et al. [15] and Jin et al. [17] further reduced the uplink communication cost by utilizing gradient quantization techniques [19]–[24]. These existing research studies, although providing a decent privacy-preserving guarantee with optimal utility and efficiency for centralized and samplewise distributed settings, leave the featurewise distributed private training barely studied.