A Stability-based Validation Procedure for Differentially Private Machine Learning
Differential privacy is a cryptographically motivated definition of privacy which has gained considerable attention in the algorithms, machine-learning and datamining communities. While there has been an explosion of work on differentially private machine learning algorithms, a major barrier to achieving end-to-end differential privacy in practical machine learning applications is the lack of an effective procedure for differentially private parameter tuning, or, determining the parameter value, such as a bin size in a histogram, or a regularization parameter, that is suitable for a particular application. In this paper, we introduce a generic validation procedure for differentially private machine learning algorithms that apply when a certain stability condition holds on the training algorithm and the validation performance metric. The training data size and the privacy budget used for training in our procedure is independent of the number of parameter values searched over. We apply our generic procedure to two fundamental tasks in statistics and machine-learning -training a regularized linear classifier and building a histogram density estimator that result in end-toend differentially private solutions for these problems.
A Stability-Based Validation Procedure for 
      Differentially Private Machine Learning 
      ------------------------------------------------------------------------------------------------------ 
      The paper discusses the problem of finding in a differentially private 
      manner which hypothesis out of a given set of k hypotheses (often 
      represented as k potential values for a parametrized learning problem, 
      like SVM) gives a better score on a separate validation set. The overall 
      approach is straight-forward: you try all k hypothesis and publish the one 
      that achieves minimal error perturbed by Laplace noise (or highest 
      perturbed score). Clearly, such approach is differentially private only if 
      one has the guarantees that a single person cannot have a significant 
      effect on the score of the best hypothesis (or the hypothesis itself), a 
      premise which the authors refer to as stability. The authors then apply 
      their paradigm to the specific cases of linear classifiers and histogram 
      estimators. Finally, the authors evaluate their technique empirically 
      comparing it to various other differentially private estimators (like 
      naively trying all k assumptions with \alpha=\alpha/k, or splitting the 
      data into k random chunks training each hypothesis on a different chunk). 
      The paper address an important problem and gives a nice and clean 
      solution to it. The authors take the time to compare their technique to a 
      non-private version of the algorithm, and the paper is really well 
      written. Also, the general problem statement is nice. If we want to learn 
      the best of k hypotheses while preserving \alpha-DP, there are 2 strawmen 
      algorithms: to learn each while preserving (\alpha/k)-DP, which leads to 
      poly(k)-degradation in performance, or to learn each in a manner that 
      preserves \alpha-DP on a 1/k fraction of the data, which causes the sample 
      bounds to grow by a factor of k. The authors' observation is that DP 
      machine learners often output an hypothesis that only slightly changes 
      w.r.t a change of a single individual, so the validation score of each of 
      the k-hypothesis isn't prone to change by much and adding a small amount 
      of noise to the validation score of each hypothesis is therefore enough to 
      preserve DP. The two major disadvantages of the paper, in my 
      opinion, lie in the fact that the observation is cute but not very 
      surprising -- the stability is a by-product of the fact that the learning 
      algorithms are DP. Because the hypotheses outputted by the learning on any 
      two neighboring training datasets are close, then their validation score 
      is close too. The second problem is in the experiment: for small \alpha 
      (the more interesting regime) is seems that this approach does almost as 
      well as picking a random hypothesis. (Also, why doesn't hypothesis 
      "control" has \alpha=0?) I would much rather see a different experiment, 
      in which the data is synthetically generated so that some hypothesis best 
      explains it, and the authors check how many examples are required in each 
      technique until each of the \alpha-DP algorithms reached 
      error<\epsilon. If indeed the number of samples improves dramatically 
      with the new technique, that would serve as a demonstration that this 
      approach is best. Also, I object to the use of the term stability. 
      Since q is a function, I do not understand what's wrong with the more 
      concrete notion of Lipfshitzness or smoothness. Still, all in all 
      it is an interesting paper. I recommend weak acceptance.