Private Sequential Learning
Private Sequential Learning
复制标题
私人顺序学习
DOI：
10.1287/opre.2020.2021
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Zhi Xu
中科院分区：
文献类型：
--
作者：
J. Tsitsiklis;Kuang Xu;Zhi Xu
我们能否通过连续的互动来私下高效地学习？制定私人学习模型来研究顺序学习中隐私和查询复杂性之间的内在权衡。该公式涉及一个学习者，其目标是通过顺序查询外部数据库并接收二进制响应来学习标量值。与此同时，对手会观察学习者的查询（尽管不是响应），并试图从中推断出兴趣的标量值。学习者的目标是仅使用少量查询来获得标量值的准确估计，同时通过使对手难以学习标量值来保护他或她的隐私。主要结果提供了学习者查询复杂性的严格上限和下限，作为所需隐私级别和估计准确性的函数。作者还构建了显式查询策略，其复杂性在加性常数范围内是最佳的。
Can we learn privately and efficiently through sequential interactions? A private learning model is formulated to study an intrinsic tradeoff between privacy and query complexity in sequential learning. The formulation involves a learner who aims to learn a scalar value by sequentially querying an external database and receiving binary responses. In the meantime, an adversary observes the learner’s queries, although not the responses, and tries to infer from them the scalar value of interest. The objective of the learner is to obtain an accurate estimate of the scalar value using only a small number of queries while simultaneously protecting his or her privacy by making the scalar value provably difficult to learn for the adversary. The main results provide tight upper and lower bounds on the learner’s query complexity as a function of desired levels of privacy and estimation accuracy. The authors also construct explicit query strategies whose complexity is optimal up to an additive constant.