Differentially private learning and strategy implication

Abstract

With the low-cost collection of individual's information and the extensive application of machine learning, privacy has received a rapidly growing attention in both academia and industry, and differential privacy is a widely accepted criterion. In this thesis, we focus on differentially private learning problems. We firstly consider how to achieve better privacy and approximation in the $k$-means clustering problem. In addition to privacy issue, differential privacy has one potential property of stability. We then study how to make use of this property in a repeated auction to affect players' strategy.

We preserve differential privacy in $k$-means clustering. For the objective of minimizing the Wasserstein distance between the output and the optimum, we show a polynomial-time $(\epsilon,\delta)$-differentially private algorithm which with error $\O( \phi^2)$ for any sufficiently large $\phi^2$ well-separated datasets. Furthermore, we prove a matching lower bound. For minimizing the $k$-means objective, we propose a polynomial-time private local search algorithm that outputs an $\alpha n$-additive approximation when the dataset is sufficiently large and the dimension is bounded.

We apply differential privacy in the auction for learning price. Consider the problem of learning optimal reserve price in repeated auctions against non-myopic bidders, who may bid strategically in order to gain in future rounds even if the single-round auctions are truthful. We introduce algorithms that obtain a small regret either when the market is large, or when the bidders are impatient. Building on techniques of differentially private online learning and jointly differentially private algorithms, our approach carefully controls what information is revealed to bidders, and incentivizes them to report bids with bounded deviation to true values.