Private Inner Product Retrieval for Distributed Machine Learning

Mohammad Hossein Mousavi, Mohammad Ali Maddah-Ali, Mahtab Mirmohseni

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations


In this paper, we argue that in many basic algorithms for machine learning, including support vector machine (SVM) for classification, principal component analysis (PCA) for dimensionality reduction, and regression for dependency estimation, we need the inner products of the data samples, rather than the data samples themselves.Motivated by the above observation, we introduce the problem of private inner product retrieval for distributed machine learning, where we have a system including a database of some files, duplicated across some non-colluding servers. A user intends to retrieve a subset of specific size of the set of the inner product of every pair of data items in the database with minimum communication load, without revealing any information about the identity of the requested subset. For achievability, we use the algorithms for multi-message private information retrieval. For converse, we establish that as the length of the files becomes large, the set of all inner products converges to independent random variables with uniform distribution hence we find asymptotic capacity for this problem. We also derive the rate of this convergence. To prove that, we construct special dependencies among sequences of the sets of all inner products with different length, which forms a time-homogeneous irreducible Markov chain, without affecting the marginal distribution. We show that this Markov chain has a uniform distribution as its unique stationary distribution, with rate of convergence dominated by the second largest eigenvalue of the transition probability matrix. This allows us to develop a converse, which converges to a tight bound in some cases, as the size of the files becomes large.

Original languageEnglish (US)
Title of host publication2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages5
ISBN (Electronic)9781538692912
StatePublished - Jul 2019
Externally publishedYes
Event2019 IEEE International Symposium on Information Theory, ISIT 2019 - Paris, France
Duration: Jul 7 2019Jul 12 2019

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8095


Conference2019 IEEE International Symposium on Information Theory, ISIT 2019

Bibliographical note

Publisher Copyright:
© 2019 IEEE.


Dive into the research topics of 'Private Inner Product Retrieval for Distributed Machine Learning'. Together they form a unique fingerprint.

Cite this