Is Interaction Necessary for Distributed Private Learning?
Is Interaction Necessary for Distributed Private Learning?
复制标题
DOI：
10.1109/sp.2017.35
复制
发表时间：
2017-05
期刊：
影响因子：
--
通讯作者：
Adam D. Smith;Abhradeep Thakurta;Jalaj Upadhyay
中科院分区：
文献类型：
--
作者：
Adam D. Smith;Abhradeep Thakurta;Jalaj Upadhyay
最近大规模部署的差分私有算法采用本地隐私模型（有时称为PRAM或随机响应），其中数据在每个人的设备上随机化，然后发送到计算近似汇总统计数据的服务器。服务器在隐私方面无需信任，将数据控制权交给用户。对于一类重要的凸优化问题（包括逻辑回归、支持向量机和欧几里得中值），最著名的局部微分私有算法是高度交互的，需要尽可能多的来回轮，因为协议中有用户。我们的问题是：在局部DP模型中优化凸函数需要多少交互作用？现有的下界要么不适用于凸优化，要么对交互作用一无所知。我们提供的新算法要么是非交互式的，要么使用相对较少的交互轮。我们还展示了一类重要的非交互算法的精度下界，这表明在有交互和没有交互的情况下是可能的。
Recent large-scale deployments of differentially private algorithms employ the local model for privacy (sometimes called PRAM or randomized response), where data are randomized on each individual's device before being sent to a server that computes approximate, aggregate statistics. The server need not be trusted for privacy, leaving data control in users' hands. For an important class of convex optimization problems (including logistic regression, support vector machines, and the Euclidean median), the best known locally differentially-private algorithms are highly interactive, requiring as many rounds of back and forth as there are users in the protocol. We ask: how much interaction is necessary to optimize convex functions in the local DP model? Existing lower bounds either do not apply to convex optimization, or say nothing about interaction. We provide new algorithms which are either noninteractive or use relatively few rounds of interaction. We also show lower bounds on the accuracy of an important class of noninteractive algorithms, suggesting a separation between what is possible with and without interaction.