论文标题
贪婪坐标下降的高维私人经验风险最小化
High-Dimensional Private Empirical Risk Minimization by Greedy Coordinate Descent
论文作者
论文摘要
在本文中，我们研究了不同的私人经验风险最小化（DP-erm）。已经表明，随着尺寸的增加，DP-erm的最坏情况下的效用会降低多项式。这是私下学习大型机器学习模型的主要障碍。在高维度中，某些模型的参数通常比其他参数更多的信息是常见的。为了利用这一点，我们提出了一个差异化的私有贪婪坐标下降（DP-GCD）算法。在每次迭代中，DP-GCD私人沿梯度（大约）最大的条目执行坐标梯度步骤。从理论上讲，DP-GCD可以通过自然利用其结构属性（例如quasi-sparse解决方案）来实现对广泛问题的对数依赖性。我们在合成数据集和实际数据集上以数值为单位说明了这种行为。
In this paper, we study differentially private empirical risk minimization (DP-ERM). It has been shown that the worst-case utility of DP-ERM reduces polynomially as the dimension increases. This is a major obstacle to privately learning large machine learning models. In high dimension, it is common for some model's parameters to carry more information than others. To exploit this, we propose a differentially private greedy coordinate descent (DP-GCD) algorithm. At each iteration, DP-GCD privately performs a coordinate-wise gradient step along the gradients' (approximately) greatest entry. We show theoretically that DP-GCD can achieve a logarithmic dependence on the dimension for a wide range of problems by naturally exploiting their structural properties (such as quasi-sparse solutions). We illustrate this behavior numerically, both on synthetic and real datasets.
