Noninteractive Locally Private Learning of Linear Models via Polynomial Approximations
Noninteractive Locally Private Learning of Linear Models via Polynomial Approximations
复制标题
DOI：
--
复制
发表时间：
2018-12
期刊：
影响因子：
--
通讯作者：
Di Wang;Adam D. Smith;Jinhui Xu
中科院分区：
文献类型：
--
作者：
Di Wang;Adam D. Smith;Jinhui Xu
最小化凸风险函数是许多基本学习算法的主要步骤。我们研究凸优化协议，可证明泄漏很少的个别数据点，构成损失函数。具体来说，我们考虑在本地模型中运行的差分私有算法，其中每个数据记录存储在单独的用户设备上，并且由这些设备在本地执行随机化。我们给出了新的协议\n {noninteractive} LDP凸优化-即，协议只需要每个用户向不可信聚合器提交一份随机报告。我们研究了我们的算法在预期损失方面的性能-无论是在手头的数据集（经验风险）还是在假设我们的数据集来自的更大的人群中。我们的误差范围取决于个人对预期损失的贡献形式。对于广义线性损失（如铰链损失和逻辑损失）的情况，我们给出了一个LDP算法，其样本复杂度仅在维数$p$上是线性的，在其他项（隐私参数$\delta $和期望的超额风险$\alpha$）上是拟多项式的.这是第一个算法的非光滑损失与次指数依赖于$p$。对于欧几里得中位数问题，其中的损失是由欧几里得距离给定的数据点，我们给出了一个协议，其样本复杂性增长quasipolynomially $p$。这是第一个协议与次指数依赖$p$的损失，这不是一个广义线性损失。我们的铰链损失的结果是基于一种技术，称为多项式的内积近似，这可能适用于其他问题。我们的广义线性损失和欧氏中位数的结果是基于新的减少铰链损失的情况下。
Minimizing a convex risk function is the main step in many basic learning algorithms. We study protocols for convex optimization which provably leak very little about the individual data points that constitute the loss function. Specifically, we consider differentially private algorithms that operate in the local model, where each data record is stored on a separate user device and randomization is performed locally by those devices. We give new protocols for \emph{noninteractive} LDP convex optimization---i.e., protocols that require only a single randomized report from each user to an untrusted aggregator. We study our algorithms' performance with respect to expected loss---either over the data set at hand (empirical risk) or a larger population from which our data set is assumed to be drawn. Our error bounds depend on the form of individuals' contribution to the expected loss. For the case of \emph{generalized linear losses} (such as hinge and logistic losses), we give an LDP algorithm whose sample complexity is only linear in the dimensionality $p$ and quasipolynomial in other terms (the privacy parameters $\epsilon$ and $\delta$, and the desired excess risk $\alpha$). This is the first algorithm for nonsmooth losses with sub-exponential dependence on $p$. For the Euclidean median problem, where the loss is given by the Euclidean distance to a given data point, we give a protocol whose sample complexity grows quasipolynomially in $p$. This is the first protocol with sub-exponential dependence on $p$ for a loss that is not a generalized linear loss . Our result for the hinge loss is based on a technique, dubbed polynomial of inner product approximation, which may be applicable to other problems. Our results for generalized linear losses and the Euclidean median are based on new reductions to the case of hinge loss.