(Near) Dimension Independent Risk Bounds for Differentially Private Learning

By Prateek Jain, Abhradeep Thakurta. 2014

145 citations recorded by the source corpus.

Subfields: Statistical Learning Theory, Privacy & Security

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Statistical Learning Theory

In Privacy & Security

Citations in the corpus

Practical and Private (Deep) Learning without Sampling or Shuffling (2021, background): “[37] Prateek Jain and Abhradeep Guha Thakurta.”
To Drop or Not to Drop: Robustness, Consistency and Differential Privacy Properties of Dropout (2015, methodology): “…private optimization (learning) algorithms have received signiﬁcant attention Chaudhuri and Monteleoni [2008], Dwork and Lei [2009], Chaudhuri et al. [2011], Jain et al. [2012], Kifer et al. [2012], Duchi et al. [2013], Song et al. [2013], Jain and Thakurta [2014], Bassily et al. [2014].”
Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds (2014, background): “Kifer et al. [34], Smith and Thakurta [45] considered parameter convergence for high-dimensional sparse regression (where p n).”
Towards Practical Differentially Private Convex Optimization (2019, methodology): “From prior works [11], [17], we know that both objective perturbation and the private Frank-Wolfe have near dimension-independent utility guarantees when the loss is of a GLM, and we indeed observe this expected behavior from our experiments.”
Private Stochastic Convex Optimization with Optimal Rates (2019, background): “The problem of ERM with differential privacy (DP-ERM) has been well-studied and asymptotically tight upper and lower bounds on excess loss 1 are known [CM08, CMS11, JKT12, KST12, ST13, SCS13, DJW13, Ull15, JT14, BST14, TTZ15, STU17, WLK + 17, WYX17, INS + 19].”
Improving the Privacy and Accuracy of ADMM-Based Distributed Algorithms (2018, methodology): “…( δ > 0 ) of violating (cid:15) -differential privacy and adopt a weaker variant ( (cid:15) , δ )-differential privacy, we can adopt methods from works such as (Kifer et al., 2012; Jain & Thakurta, 2014; Bassily et al., 2014), by adding Gaussian noise to achieve tighter bounds on privacy loss.”
Private Multiplicative Weights Beyond Linear Queries (2014, background): “[24] D. Kifer, A. D. Smith, and A. Thakurta.”
Estimating Smooth GLM in Non-interactive Local Differential Privacy Model with Public Unlabeled Data (2019, background): “While there are many results on GLM in the DP and interactive LDP models (Chaud-huri et al., 2011; Bassily et al., 2014; Jain and Thakurta, 2014; Kasiviswanathan and Jin, 2016), GLM in NLDP is still not well understood due to the limitation of the model.”
When Relaxations Go Bad: "Differentially-Private" Machine Learning (2019, unknown): “…has also been a considerable progress in generalizing privacy-preserving machine learning to more complex scenarios such as learning in high dimensional settings [34,35,65], learning without strong convexity assumptions [66], or relaxing the assumptions on data and objective functions [63, 70, 79].”
Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds (2014, background): “[23] gave dimension-independent expected excess risk bounds for the special case of “generalized linear models” with a strongly convex regularizer, assuming that C = R (that is, unconstrained optimization).”
Characterizing Private Clipped Gradient Descent on Convex Generalized Linear Problems (2020, unknown): “While [22] proved a similar dimension-independent risk guarantee for two other differentially private algorithms, namely output perturbation [9] and objective perturbation [9, 25], our result is notable in the following aspects.”
Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses (2020, background): “…studied extensively for over a decade (see, e.g., (Chaudhuri and Monteleoni, 2008; Chaudhuri et al., 2011; Jain et al., 2012; Kifer et al., 2012; Smith and Thakurta, 2013; Bassily et al., 2014; Ullman, 2015; Jain and Thakurta, 2014; Talwar et al., 2015; Bassily et al., 2019; Feldman et al., 2020)).”
Private Empirical Risk Minimization, Revisited (2014, background): “Jain and Thakurta [23] gave dimension-independent expected excess risk bounds for the special case of “generalized linear models” with a strongly convex regularizer, assuming that C = Rp (that is, unconstrained optimization).”
Nearly Optimal Private LASSO (2015, methodology): “For the special case of linear loss functions, which are interesting primarily in the online prediction setting, the techniques of [19, 25] provide a bound of O(polylog p/n).”