Paper ID: | 1544 |
---|---|

Title: | Differentially Private Empirical Risk Minimization Revisited: Faster and More General |

Summary: The paper revisits the problem of differentially private empirical risk minimization and claims to provide algorithms with tighter gradient complexity (i.e., the number of gradient evaluations to obtain the optimal error). The main algorithm they use is a differentially private variant of the stochastic variance reduced gradient descent (SVRGD) algorithm. Furthermore, they provide excess empirical risk guarantees for non-convex loss functions that satisfy Polyak-Lojasiewicz condition.
Positive aspects of the paper: SVRGD has become very popular in the convex optimization literature, and this paper provides the first differentially private variant of it. Furthermore, the analysis for the non-convex case is very interesting.
Other comments:
i) I believe all the bounds in Table 2 and Table 3 (in terms of gradient complexity) is already known in the literature (up to logarithmic factors). See, the paper "Is Interaction Necessary for Distributed Private Learning?". The main point is that differentially private gradient descent algorithms converge at the same rate as their non-private counter parts up to the optimal error.
ii) I am unclear about the Polyak-Lojasiewicz condition. I am sure it is my ignorance of the topic, but the paper does not provide enough intuition into the condition.
Given that gradient complexity results are already known, I am worried about the impact of the paper.

Summary:
A large number of machine learning models are trained on potentially sensitive
data, and it is often import to guarantee privacy of the training data.
Chaudhuri and Monteleoni formulated the differentially private ERM problem and
started a line of work on designing differentially private optimization
algorithms for variants of ERM problems. Recent works have gotten nearly optimal
tradeoffs between the additional error introduced by the DP algorithm (the
privacy risk) and the privacy parameter, for a large class of settings. In this
work, these results are improved in the additional axis of computational
efficiency. For smooth and strongly convex losses, this work gets privacy risk
bounds that are essentially the best known, but do so at a computational cost
that is essentially (n+ \kappa) gradient computaitons, instead of n\kappa, where
\kappa is the condition number. Similar improvements are presented for other
settings of interest, when the loss function is not strongly convex, or when the
constraint set has small complexity.
A different viewpoint on the results is that the authors show that DP noise
addition techniques and modern optimization methods can be made to work well
together. Speficially, one can use SVRG with noise addition at each step and the
authors show that this noisy SVRG also gets near optimal privacy risk. Similarly
for the case of constraint sets with small Gaussian width (such as l_1), where
previous work used noisy mirror descent, the authors show that one can use an
accelerated noisy mirror descent and get faster runtimes without paying in the
privacy cost.
I think the problem is very important and interesting. While the tools are somewhat
standard, I think this paper advances the state of the art sufficiently that I
am compelled to recommend acceptance.

This paper gives several algorithm for ERM in convex optimization that satisfy differential privacy. The algorithms improve on known bounds in terms of number of necessary gradient computations and handle some some general settings such as non-convex functions satisfying a certain condition.
As far as I can tell from the presentation the results are obtained by plugging the known analyses of gradient perturbation using Gaussian noise into well-known faster algorithms than those previously considered (e.g. SVRG). The stochastic methods naturally deal with randomized estimates of the gradient so accounting for additional randomization due to Gaussian noise is relatively straightforward.
These results are useful to have but I think that both technical and conceptual contributions are not quite significant enough for publication in NIPS. (The paper does not contain any discussion of ideas they needed to employ to make the analysis go through so I assume there is not much to discuss).
Some minor additional comments:
32. The bound was not "broken" but rather refined using additional structural assumptions.
Table 1 caption: L is undefined (I guess it should be the smoothness parameter that you assume to be 1)