(Near) Dimension Independent Risk Bounds for Differentially Private Learning

In this paper, we study the problem of differen-tially private risk minimization where the goal is to provide differentially private algorithms that have small excess risk. In particular we address the following open problem: Is it possible to de-sign computationally efficient differentially pri-vate risk minimizers with excess risk bounds that do not explicitly depend on dimensionality (p) and do not require structural assumptions like re-stricted strong convexity? In this paper, we answer the question in the af-firmative for a variant of the well-known output and objective perturbation algorithms (Chaud-huri et al., 2011). In particular, we show that un-der certain assumptions, variants of both output and objective perturbation algorithms have no ex-plicit dependence on p; the excess risk depends only on the L2-norm of the true risk minimizer and that of training points. Next, we present a novel privacy preserving algo-rithm for risk minimization over simplex in the generalized linear model, where the loss func-tion is a doubly differentiable convex function. Assuming that the training points have bounded L∞-norm, our algorithm provides risk bound that has only logarithmic dependence on p. We also apply our technique to the online learning setting and obtain a regret bound with similar logarithmic dependence on p. In contrast, the ex-isting differentially private online learning meth-ods incur O( p) dependence. 1