Private Convex Optimization for Empirical Risk Minimization with Applications to High-dimensional Regression

By Daniel Kifer, Adam D. Smith, Abhradeep Thakurta. 2012

298 citations recorded by the source corpus.

Subfields: Optimization & Training, 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 Optimization & Training

In Privacy & Security

Citations in the corpus

Practical and Private (Deep) Learning without Sampling or Shuffling (2021, background): “Differentially private empirical risk minimization (ERM) and private online learning are well-studied areas in the privacy literature [1, 2, 3, 6, 7, 14, 29, 35, 37, 38, 43, 51, 57, 58, 65, 67, 68, 74]7.”
Differentially Private Learning Needs Better Features (or Much More Data) (2020, background): “For CIFAR-10, Data 2Yu et al. (2019a) show that DP-SGD outperforms other algorithms for private convex optimization, e.g., logistic regression with output or objective perturbation (Chaudhuri et al., 2011; Bassily et al., 2014; Kifer et al., 2012).”
Data Poisoning against Differentially-Private Learners: Attacks and Defenses (2019, methodology): “Objective perturbation injects noise into the objective function of a vanilla machine learner to train a randomized model [5, 11, 17].”
Privacy Amplification by Iteration (2018, background): “, output perturbation [16] and objective perturbation [16], [18]) require finding a global optimum of an optimization problem to argue privacy and utility, while the others are based on the variants of noisy stochastic gradient descent.”
Differential Privacy for Growing Databases (2018, background): “Private ERM has been previously studied by [CMS11, KST + 12, BST14]; we compare our accuracy bounds in the dynamic setting to their static bounds in Table 1.”
Differentially Private Distributed Optimization (2014, methodology): “In [1, 9] the authors solve a privacy preserving optimization problem with two methods: output perturbation and objective perturbation.”
To Drop or Not to Drop: Robustness, Consistency and Differential Privacy Properties of Dropout (2015, background): “…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): “Standard differential privacy arguments for Gaussian noise addition (see [34, 40]) will ensure that with probability 1− δ 2 (over the randomness of the random variables bt’s and conditioned on the randomness due to sampling),Wt ≤ 2 √ log(1/δ) for all t ∈ [n2].”
Towards Practical Differentially Private Convex Optimization (2019, methodology): “Here, for small values of γ (for example, γ = O ( 1 n2 ) ), the excess empirical risk of Approximate Minima Perturbation is asymptotically the same as that of objective perturbation [9], and has a better dependence on n than that of Private Permutationbased SGD [12].”
Privacy for Free: Posterior Sampling and Stochastic Gradient Monte Carlo (2015, methodology): “Objective perturbation is originally proposed in Chaudhuri et al. (2011) and the ( (cid:15), δ ) version that we refer to ﬁrst appears in Kifer et al. (2012).”
Private Stochastic Convex Optimization with Optimal Rates (2019, methodology): “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.”
Learning with Differential Privacy: Stability, Learnability and the Sufficiency and Necessity of ERM Principle (2015, background): “The same formulation has been studied before in the context of differentially private machine learning (Chaudhuri et al., 2011; Kifer et al., 2012), but our focus is more generic and does not require the objective function to be convex, differentiable, continuous, or even have a finite dimensional E”
Differentially Private Hypothesis Transfer Learning (2018, background): “Besides, there has been a large body of systematic theoretical work in the differentially private ERM literature deriving error bounds and efficiency [2] and investigating high-dimensional sparse regression problems [18].”
Nearly Optimal Private LASSO (2015, background): “First [20] and then [24] studied the LASSO estimator with differential privacy guarantee.”
Differentially Private Distributed Convex Optimization via Functional Perturbation (2015, methodology): “It is shown in [11] that this method also works in the presence of constraints and non-differentiable regularizers.”
Differentially Private Model Selection via Stability Arguments and the Robustness of the Lasso (2013, methodology): “In this work we significantly extend and improve on the results of Kifer et al. (2012) (see “Our Contributions” for a comparison).”