Differential Privacy without Sensitivity
The exponential mechanism is a general method to construct a randomized estimator that satisfies (ε, 0)-differential privacy. Recently, Wang et al. showed that the Gibbs posterior, which is a data-dependent probability distribution that contains the Bayesian posterior, is essentially equivalent to the exponential mechanism under certain boundedness conditions on the loss function. While the exponential mechanism provides a way to build an (ε, 0)-differential private algorithm, it requires boundedness of the loss function, which is quite stringent for some learning problems. In this paper, we focus on (ε, δ)-differential privacy of Gibbs posteriors with convex and Lipschitz loss functions. Our result extends the classical exponential mechanism, allowing the loss functions to have an unbounded sensitivity.
Exponential mechanism is a universal differentially private algorithm, i.e., every differentially private algorithm can be represented as an exponential mechanism. Exponential mechanism requires defining a loss (score) function over the output space parameterized by the data set, and then sampling a candidate from a distribution induced by the score function. Often times the loss function is required to be of bounded range for the privacy analysis. This paper tries to alleviate this concern by sampling from a Gibb’s posterior distribution, with strongly convex prior. The strong convexity of the prior helps to control the tail behavior of the sampling distribution, and hence obtain a (\epsilon,\delta)-differential privacy guarantee. 
One major concern I have with the paper is the amount of complexity introduced. I am not convinced whether a simpler algorithm / analysis would suffice. In the following, I qualify my above statement.  In the notation of the paper, let L = \sum \ell(\theta;d_i). If \theta \in R_\Theta (a bounded convex set) and \ell is L-Lipschitz, then one can show that sampling from exp(-\eps/\beta L(\theta)) is \eps differentially private (see [3]). Furthermore, adding a strongly convex regularizer should remove the bound on R_\Theta. by the same argument described in this paper. How does this compare to Section 3.2 in this paper?  On a general note, how the utility guarantees of this paper compare to the existing results [8, 14, 3]?  More specific comments are as follows:  1. I believe the idea of introducing a strongly convex prior to control the tail distribution of exponential mechanism is an interesting idea. Also the analysis to control the tail behavior of exponential mechanism (in order to obtain a bound on the privacy parameter \delta), seems novel in my opinion.    2. I am concerned with the title mentioning 'without sensitivity'. It seems too catchy to be factually correct. The paper does assume a bound on the gradient of the loss function (instead of the value of the loss function). Even the bound on the gradient can be considered as sensitivity.  3. In  Line 31, the paper forgot to mention that [3] also does posterior sampling on the output distribution via exponential mechanism.  4. The exposition of the shrinkage concept (in lines 57-61) can be improved for readability by describing it in terms of regularization.  5. The related work requires significant work. The paper needs to describe the prior work in much more detail in order to place the novelty of their results in perspective. The area of private convex optimization is very well studied.  6. In Line 153, I am concerned with the value of the delta parameter. Typically, for semantic correctness of differential privacy \eps is a small constant (around 0.1) and \delta is a value much small than 1/ n^2 (n is the number of data samples).  7. The bound in Line 199 needs more justification.  Since in machine learning typically \lambda is chosen to be around 1/\sqrt n, \beta seems to  scale as n^{1/4}. Is this good or bad ?  8. In Line 42 it should be analysis instead of analyzes.