论文标题
私有$ \ ell_1 $ -norm线性回归与重尾数据
Differentially Private $\ell_1$-norm Linear Regression with Heavy-tailed Data
论文作者
论文摘要
我们研究了具有重尾数据的差异私有随机凸优化（DP-SCO）的问题。具体来说，我们专注于$ \ ell_1 $ -norm线性回归中的$ε$ -DP模型。尽管以前的大多数工作都集中在损失函数是Lipschitz的情况下，但在这里我们只需要假设变体具有有限的矩。首先，我们研究了$ \ ell_2 $数据规范的二阶订单时刻的情况。我们提出了一种基于指数机制的算法，并表明可以实现$ \ tilde {o}的上限（\ sqrt {\ frac {\ frac {d} {nε}}}}）$（具有很高的概率）。接下来，我们放宽了（1，2）$中的一些$θ\的限制$θ$ -th订单力矩的假设，并证明可以实现$ \ tilde {o}的上限（（（（{\ frac {d} {d} {nε}} {nε}}} {nε}}}} {nε}}）我们的算法也可以扩展到更轻松的情况，只有数据的每个坐标都有界限，并且我们可以得到$ \ tilde {o}的上限（{\ frac {d} $ \ tilde {o}（{\ frac {d} {（{nε}）^\ frac {θ-1}θ}}}}}}）$分别在$θ$ - thenmments案例中。
We study the problem of Differentially Private Stochastic Convex Optimization (DP-SCO) with heavy-tailed data. Specifically, we focus on the $\ell_1$-norm linear regression in the $ε$-DP model. While most of the previous work focuses on the case where the loss function is Lipschitz, here we only need to assume the variates has bounded moments. Firstly, we study the case where the $\ell_2$ norm of data has bounded second order moment. We propose an algorithm which is based on the exponential mechanism and show that it is possible to achieve an upper bound of $\tilde{O}(\sqrt{\frac{d}{nε}})$ (with high probability). Next, we relax the assumption to bounded $θ$-th order moment with some $θ\in (1, 2)$ and show that it is possible to achieve an upper bound of $\tilde{O}(({\frac{d}{nε}})^\frac{θ-1}θ)$. Our algorithms can also be extended to more relaxed cases where only each coordinate of the data has bounded moments, and we can get an upper bound of $\tilde{O}({\frac{d}{\sqrt{nε}}})$ and $\tilde{O}({\frac{d}{({nε})^\frac{θ-1}θ}})$ in the second and $θ$-th moment case respectively.
