Technical Program

Paper Detail

Paper Title Harmonic Coding: An Optimal Linear Code for Privacy-Preserving Gradient-Type Computation
Paper IdentifierTU3.R5.3
Authors Qian Yu, Amir Salman Avestimehr, University of Southern California, United States
Session Private Computation I
Location Saint Victor, Level 3
Session Time Tuesday, 09 July, 14:30 - 16:10
Presentation Time Tuesday, 09 July, 15:10 - 15:30
Manuscript  Click here to download the manuscript
Abstract We consider the problem of distributedly computing a general class of functions, referred to as \emph{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 \emph{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 \emph{harmonic series}. 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).