Truthful Linear Regression
This addresses the challenge of data collection from privacy-aware users in machine learning, though it appears incremental as it builds on existing differential privacy and mechanism design frameworks.
The paper tackles the problem of fitting a linear model to data from privacy-sensitive individuals by designing a mechanism that incentivizes truthful reporting while ensuring differential privacy, overcoming the bias introduced by private computation.
We consider the problem of fitting a linear model to data held by individuals who are concerned about their privacy. Incentivizing most players to truthfully report their data to the analyst constrains our design to mechanisms that provide a privacy guarantee to the participants; we use differential privacy to model individuals' privacy losses. This immediately poses a problem, as differentially private computation of a linear model necessarily produces a biased estimation, and existing approaches to design mechanisms to elicit data from privacy-sensitive individuals do not generalize well to biased estimators. We overcome this challenge through an appropriate design of the computation and payment scheme.