Evading Curse of Dimensionality in Unconstrained Private GLMs via Private Gradient Descent

Abstract

We revisit the well-studied problem of differentially private empirical risk minimization (ERM). We show that for unconstrained convex generalized linear models (GLMs), one can obtain an excess empirical risk of $\tilde{O}\left(\sqrt{\text{rank}}/\epsilon n\right)$, where $\text{rank}$ is the rank of the feature matrix in the GLM problem, $n$ is the number of data samples, and $\epsilon$ is the privacy parameter. This bound is attained via differentially private gradient descent (DP-GD). Furthermore, via the first lower bound for unconstrained private ERM, we show that our upper bound is tight. In sharp contrast to the constrained ERM setting, there is no dependence on the dimensionality of the ambient model space ($p$). (Notice that $\text{rank}\le \min \{n,p\}$.) Besides, we obtain an analogous excess population risk bound which depends on $\text{rank}$ instead of $p$. For the smooth non-convex GLM setting (i.e., where the objective function is non-convex but preserves the GLM structure), we further show that DP-GD attains a dimension-independent convergence of $\tilde{O}\left(\sqrt{\text{rank}}/\epsilon n\right)$ to a first-order-stationary-point of the underlying objective. Finally, we show that for convex GLMs, a variant of DP-GD commonly used in practice (which involves clipping the individual gradients) also exhibits the same dimension-independent convergence to the minimum of a well-defined objective. To that end, we provide a structural lemma that characterizes the effect of clipping on the optimization profile of DP-GD.

References in corpus (16)

• Deep Learning with Differential Privacy
• On the difficulty of training Recurrent Neural Networks
• Renyi Differential Privacy
• Learning Differentially Private Recurrent Language Models
• Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
• Privacy Amplification by Iteration
• Differentially Private Learning with Adaptive Clipping
• Why gradient clipping accelerates training: A theoretical justification for adaptivity
• Private Stochastic Convex Optimization with Optimal Rates
• AdaCliP: Adaptive Clipping for Private SGD
• Understanding Gradient Clipping in Private SGD: A Geometric Perspective
• Private Empirical Risk Minimization Beyond the Worst Case: The Effect of the Constraint Set Geometry
• Tempered Sigmoid Activations for Deep Learning with Differential Privacy
• Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses
• The Cost of Privacy in Generalized Linear Models: Algorithms and Minimax Lower Bounds
• Fast Dimension Independent Private AdaGrad on Publicly Estimated Subspaces

Cited by in corpus (6)

• Understanding Gradient Clipping in Private SGD: A Geometric Perspective
• Differentially Private Accelerated Optimization Algorithms
• Chasing Your Long Tails: Differentially Private Prediction in Health Care Settings
• Fast Dimension Independent Private AdaGrad on Publicly Estimated Subspaces
• Differentially Private (Gradient) Expectation Maximization Algorithm with Statistical Guarantees
• High-Dimensional Differentially-Private EM Algorithm: Methods and Near-Optimal Statistical Guarantees