Access Restriction

Author Banerjee, S. ♦ Hegde, N. ♦ Massoulie, L.
Sponsorship IEEE Signal Processing Society
Source IEEE Xplore Digital Library
Content type Text
Publisher Institute of Electrical and Electronics Engineers, Inc. (IEEE)
File Format PDF
Copyright Year ©2007
Language English
Subject Domain (in DDC) Natural sciences & mathematics ♦ Physics ♦ Electricity & electronics
Subject Keyword Privacy ♦ Recommender systems ♦ Data privacy ♦ Signal processing algorithms ♦ Clustering algorithms ♦ Databases ♦ Mutual information ♦ recommender systems ♦ Data privacy
Abstract Recent increase in online privacy concerns prompts the following question: can a recommender system be accurate if users do not entrust it with their private data? To answer this, we study the problem of learning item-clusters under local differential privacy, a powerful, formal notion of data privacy. We develop bounds on the sample-complexity of learning item-clusters from privatized user inputs. Significantly, our results identify a sample-complexity separation between learning in an information-rich and an information-scarce regime, thereby highlighting the interaction between privacy and the amount of information (ratings) available to each user. In the information-rich regime, where each user rates at least a constant fraction of items, a spectral clustering approach is shown to achieve a sample-complexity lower bound derived from a simple information-theoretic argument based on Fano's inequality. However, the information-scarce regime, where each user rates only a vanishing fraction of items, is found to require a fundamentally different approach both for lower bounds and algorithms. To this end, we develop new techniques for bounding mutual information under a notion of channel-mismatch. These techniques may be of broader interest, and we illustrate this by applying them to (i) learning based on 1-bit sketches, and (ii) adaptive learning. Finally, we propose a new algorithm, MaxSense, and show that it achieves optimal sample-complexity in the information-scarce regime.
Description Author affiliation :: Dept. of Manage. Sci. & Eng., Stanford Univ., Stanford, CA, USA
Author affiliation :: Inria Joint Centre, Microsoft Res., Palaiseau, France
Author affiliation :: Bell Labs., Alcatel-Lucent, Nozay, France
ISSN 19324553
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2015-01-01
Publisher Place U.S.A.
Rights Holder Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Volume Number 9
Issue Number 7
Size (in Bytes) 2.65 MB
Page Count 13
Starting Page 1319
Ending Page 1331

Source: IEEE Xplore Digital Library