Learning from personal or sensitive data is a cornerstone of several experimental sciences, such as medicine and sociology. It has also become a commonplace, and controversial, aspect of the Internet economy. The monetary and societal benefits of learning from personal data are often off-set by privacy costs incurred by participating individuals. In this talk, we study these issues from the point of view of mechanism design. We consider a learner that wishes to regress a linear function over sensitive data provided by strategic agents. We show that, when agents may misreport their privacy costs, or even purposefully distort their data out of privacy concerns, a learner with a finite budget can still (a) incentivize truthful reporting and (b) learn models that are asymptotically accurate.

This is joint work with Rachel Cummings, Thibaut Horel, Patrick Loiseau, S. Muthukrishnan, and Katrina Ligett.