High Dimensional Differentially Private Stochastic Optimization with
Heavy-tailed Data
- URL: http://arxiv.org/abs/2107.11136v1
- Date: Fri, 23 Jul 2021 11:03:21 GMT
- Title: High Dimensional Differentially Private Stochastic Optimization with
Heavy-tailed Data
- Authors: Lijie Hu and Shuo Ni and Hanshen Xiao and Di Wang
- Abstract summary: We provide the first study on the problem of DP-SCO with heavy-tailed data in the high dimensional space.
We show that if the loss function is smooth and its gradient has bounded second order moment, it is possible to get a (high probability) error bound (excess population risk) of $tildeO(fraclog d(nepsilon)frac13)$ in the $epsilon$-DP model.
In the second part of the paper, we study sparse learning with heavy-tailed data.
- Score: 8.55881355051688
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: As one of the most fundamental problems in machine learning, statistics and
differential privacy, Differentially Private Stochastic Convex Optimization
(DP-SCO) has been extensively studied in recent years. However, most of the
previous work can only handle either regular data distribution or irregular
data in the low dimensional space case. To better understand the challenges
arising from irregular data distribution, in this paper we provide the first
study on the problem of DP-SCO with heavy-tailed data in the high dimensional
space. In the first part we focus on the problem over some polytope constraint
(such as the $\ell_1$-norm ball). We show that if the loss function is smooth
and its gradient has bounded second order moment, it is possible to get a (high
probability) error bound (excess population risk) of $\tilde{O}(\frac{\log
d}{(n\epsilon)^\frac{1}{3}})$ in the $\epsilon$-DP model, where $n$ is the
sample size and $d$ is the dimensionality of the underlying space. Next, for
LASSO, if the data distribution that has bounded fourth-order moments, we
improve the bound to $\tilde{O}(\frac{\log d}{(n\epsilon)^\frac{2}{5}})$ in the
$(\epsilon, \delta)$-DP model. In the second part of the paper, we study sparse
learning with heavy-tailed data. We first revisit the sparse linear model and
propose a truncated DP-IHT method whose output could achieve an error of
$\tilde{O}(\frac{s^{*2}\log d}{n\epsilon})$, where $s^*$ is the sparsity of the
underlying parameter. Then we study a more general problem over the sparsity
({\em i.e.,} $\ell_0$-norm) constraint, and show that it is possible to achieve
an error of $\tilde{O}(\frac{s^{*\frac{3}{2}}\log d}{n\epsilon})$, which is
also near optimal up to a factor of $\tilde{O}{(\sqrt{s^*})}$, if the loss
function is smooth and strongly convex.
Related papers
- Mirror Descent Algorithms with Nearly Dimension-Independent Rates for
Differentially-Private Stochastic Saddle-Point Problems [6.431793114484429]
We propose $sqrtlog(d)/sqrtn + log(d)/[nvarepsilon]2/5$ to solve the problem of differentially-private saddle-points in the polyhedral setting.
We show that our algorithms attain a rate of $sqrtlog(d)/sqrtn + log(d)/[nvarepsilon]2/5$ with constant success.
arXiv Detail & Related papers (2024-03-05T12:28:00Z) - Scaling Up Differentially Private LASSO Regularized Logistic Regression
via Faster Frank-Wolfe Iterations [51.14495595270775]
We adapt the Frank-Wolfe algorithm for $L_1$ penalized linear regression to be aware of sparse inputs and to use them effectively.
Our results demonstrate that this procedure can reduce runtime by a factor of up to $2,200times$, depending on the value of the privacy parameter $epsilon$ and the sparsity of the dataset.
arXiv Detail & Related papers (2023-10-30T19:52:43Z) - Improved Analysis of Sparse Linear Regression in Local Differential
Privacy Model [38.66115499136791]
We revisit the problem of sparse linear regression in the local differential privacy (LDP) model.
We propose an innovative NLDP algorithm, the very first of its kind for the problem.
Our findings reveal fundamental differences between the non-private case, central DP model, and local DP model in the sparse linear regression problem.
arXiv Detail & Related papers (2023-10-11T10:34:52Z) - Optimal Sketching Bounds for Sparse Linear Regression [116.30196615349226]
We study oblivious sketching for $k$-sparse linear regression under various loss functions such as an $ell_p$ norm, or from a broad class of hinge-like loss functions.
We show that for sparse $ell$vareps regression, there is an oblivious distribution over sketches with $Theta(klog(d/k)/varepsilon2)$ rows, which is tight up to a constant factor.
We also show that sketching $O(mu2 klog(mu n d/varepsilon)/var
arXiv Detail & Related papers (2023-04-05T07:24:19Z) - Efficient Sampling of Stochastic Differential Equations with Positive
Semi-Definite Models [91.22420505636006]
This paper deals with the problem of efficient sampling from a differential equation, given the drift function and the diffusion matrix.
It is possible to obtain independent and identically distributed (i.i.d.) samples at precision $varepsilon$ with a cost that is $m2 d log (1/varepsilon)$
Our results suggest that as the true solution gets smoother, we can circumvent the curse of dimensionality without requiring any sort of convexity.
arXiv Detail & Related papers (2023-03-30T02:50:49Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
This work considers the sample complexity of obtaining an $varepsilon$-optimal policy in an average reward Markov Decision Process (AMDP)
We prove an upper bound of $widetilde O(H varepsilon-3 ln frac1delta)$ samples per state-action pair, where $H := sp(h*)$ is the span of bias of any optimal policy, $varepsilon$ is the accuracy and $delta$ is the failure probability.
arXiv Detail & Related papers (2022-12-01T15:57:58Z) - Efficient Private SCO for Heavy-Tailed Data via Clipping [31.37972684061572]
We consider convex optimization for heavy-tailed data with the guarantee of gradients of being differentially private (DP)
For general convex problems, we derive excess population risks $TildeOleft(fracd1/7sqrtlnfrac(n epsilon)2beta d(nepsilon)2/7right)$ and $TildeOleft(fracd1/7lnfrac(nepsilon)2beta d(nepsilon)2
arXiv Detail & Related papers (2022-06-27T01:39:15Z) - Differentially Private $\ell_1$-norm Linear Regression with Heavy-tailed
Data [22.233705161499273]
We focus on the $ell_1$-norm linear regression in the $epsilon$-DP model.
We show that it is possible to achieve an upper bound of $tildeO(sqrtfracdnepsilon)$ with high probability.
Our algorithms can also be extended to more relaxed cases where only each coordinate of the data has bounded moments.
arXiv Detail & Related papers (2022-01-10T08:17:05Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
Up to logarithmic factors the optimal excess population loss of any $(varepsilon,delta)$-differently private is $sqrtlog(d)/n + sqrtd/varepsilon n.$
We show that when the loss functions satisfy additional smoothness assumptions, the excess loss is upper bounded (up to logarithmic factors) by $sqrtlog(d)/n + (log(d)/varepsilon n)2/3.
arXiv Detail & Related papers (2021-03-02T06:53:44Z) - On Differentially Private Stochastic Convex Optimization with
Heavy-tailed Data [18.351352536791453]
We consider the problem of designing Differentially Private (DP) algorithms for Convex Optimization (SCO) on heavy-tailed data.
The irregularity of such data violates some key assumptions used in almost all existing DP-SCO and DP-ERM methods.
We show that our algorithms can effectively deal with the challenges caused by data irregularity.
arXiv Detail & Related papers (2020-10-21T15:45:27Z) - Curse of Dimensionality on Randomized Smoothing for Certifiable
Robustness [151.67113334248464]
We show that extending the smoothing technique to defend against other attack models can be challenging.
We present experimental results on CIFAR to validate our theory.
arXiv Detail & Related papers (2020-02-08T22:02:14Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.