Differentially Private Stochastic Optimization: New Results in Convex\n and Non-Convex Settings

2021/07/12 by Raef Bassily, Bassily, Raef, Cristóbal Guzmán +3 · 3 citations
Computer Science · Economics, Econometrics and Finance · #Stochastic Gradient Optimization Techniques #Privacy-Preserving Technologies in Data #Economic and Environmental Valuation

paper · pdf · doi:10.48550/arxiv.2107.05585

Abstract

We study differentially private stochastic optimization in convex and\nnon-convex settings. For the convex case, we focus on the family of non-smooth\ngeneralized linear losses (GLLs). Our algorithm for the \ℓ₂ setting\nachieves optimal excess population risk in near-linear time, while the best\nknown differentially private algorithms for general convex losses run in\nsuper-linear time. Our algorithm for the \ℓ₁ setting has nearly-optimal\nexcess population risk\n\O\(\√ frac\logdn\ε\), and circumvents the\ndimension dependent lower bound of citeAsi:2021 for general non-smooth\nconvex losses. In the differentially private non-convex setting, we provide\nseveral new algorithms for approximating stationary points of the population\nrisk. For the \ℓ₁-case with smooth losses and polyhedral constraint, we\nprovide the first nearly dimension independent rate, nO\( frac\log^2/3d(n\ε)^1/3\) in linear time. For\nthe constrained \ℓ₂-case with smooth losses, we obtain a linear-time\nalgorithm with rate nO\( frac1n^1/3+ fracd^1/5(n\ε)^2/5\). Finally,\nfor the \ℓ₂-case we provide the first method for em non-smooth weakly\nconvex stochastic optimization with rate nO\( frac1n^1/4+ fracd^1/6(n\ε)^1/3\) which\nmatches the best existing non-private algorithm when d= O(\√(n)). We also\nextend all our results above for the non-convex \ℓ₂ setting to the\n\ℓ_p setting, where 1 < p \≤ 2, with only polylogarithmic (in the\ndimension) overhead in the rates.\n

Citations

• Smooth minimization of non-smooth functions

Cited by

• Towards Understanding Generalization in DP-GD: A Case Study in Training Two-Layer CNNs
• Understanding Private Learning From Feature Perspective
• PrAda-GAN: A Private Adaptive Generative Adversarial Network with Bayes Network Structure

Related

• Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Time
• Private Stochastic Convex Optimization with Optimal Rates
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time
• Differentially Private Stochastic Convex Optimization in (Non)-Euclidean Space Revisited
• Faster Rates of Private Stochastic Convex Optimization