Nearly-Optimal Private LASSO *
We present a nearly optimal differentially private version of the well known LASSO estimator. Our algorithm provides privacy protection with respect to each training example. The excess risk of our algorithm, compared to the non-private version, is O(1/n 2/3 ), assuming all the input data has bounded ∞ norm. This is the first differentially private algorithm that achieves such a bound without the polynomial dependence on p under no additional assumptions on the design matrix. In addition, we show that this error bound is nearly optimal amongst all differentially private algorithms.
This paper introduces differentially private Frank-Wolfe algorithms, which allows to conduct LASSO with differential privacy constraints. The proposal method is designed by taking account of the fact that the constraints induced by LASSO forms a polytope. As a result, the excess empirical risk of the proposal learning algorithm is bounded above by nearly O(1/n^{2/3}) under l1-Lipschitz continuous assumption of loss functions. This bound is better than O(polylog(n)/n^(1/3)) by [31]. The bound on the excess empirical risk is higher than O(polylog(n)/n) by [32,37]. However considering that this is derived without strong assumptions (e.g., restricted strong convexity and mutual incoherence as required in [32,37]), this can be a new contribution. Furthermore, the authors show that the bound of the excess empirical risk is near optimal under epsilon<=0.1 and delta=o(1/n^2). The authors also derive a differentially private Frank-Wolfe algorithm that can work with any convex constraint region.The derivation of the near-optimality of the proposed algorithm is an original contribution while the derivations of the differential privacy and the excess empirical risk seems to be applications of existing results.In terms of privacy preservation, assumptions on the parameter, epsilon<=0.1 and delta=o(1/n^2), are adequate. On the other hand, in terms of utility, derivation of the constant term of the excess risk is needed. The noise added by the mechanism can occupy the domain of the prediction yin realistic situations if the constant term of the bound on the excess empirical risk is not small.Say, suppose the constant term of the bound of the excess empirical risk is 1 (i.e., the excess empirical risk <= log(np/delta)/(n epsilon)^(2/3) ). Suppose privacy parameters are set to epsilon=0.1delta=1/n^2, and p=2. Then,we have excess empirical risk <= 0.5 if n<=4000 by Corollary 2.7. Since the domain of the prediction y is [-1,1], the half of the domain can be covered with not a small probability. This can be improved with a larger size of samples, but n=4000 is not a small sample size in practice. Consequently, the assumptions on privacy parameters, epsilon=0.1 and delta=1/n^2, might not be practical in some situations.