Learner-Private Convex Optimization
Learner-Private Convex Optimization
复制标题
DOI：
10.1109/tit.2022.3203989
复制
发表时间：
2021-02
影响因子：
2.5
通讯作者：
Jiaming Xu;Kuang Xu;Dana Yang
中科院分区：
文献类型：
--
作者：
Jiaming Xu;Kuang Xu;Dana Yang
带有反馈的凸优化是一个框架，其中学习者依赖于迭代查询和反馈来达到凸函数的最小值。由于其在大规模优化和机器学习方面的可扩展性，它已经获得了相当大的普及。然而，重复的交互会使学习器暴露在监视提交查询的窃听对手的隐私风险中。在本文中，我们研究了如何在一阶反馈凸优化中最优地模糊学习者的查询，使其学习到的最优值对于窃听对手来说是难以估计的。我们考虑了两种学习者隐私的表述：一种是随机绘制凸函数的贝叶斯表述，另一种是函数是固定的，对手的错误概率是根据极大极小准则测量的极大值表述。假设学习者希望确保对手不能以大于$1/L$的概率对某些$1/L$进行准确估计。我们的主要结果表明，查询复杂性开销在maximin公式中在$L$中是相加的，而在贝叶斯公式中在$L$中是相乘的。与现有的具有二元反馈的学习者-私有序列学习模型相比，我们的结果适用于具有全梯度反馈的更丰富的一般凸函数族。我们的证明依赖于狄利克雷过程理论的工具，以及一种在全梯度预言下测量信息泄漏的新策略。
Convex optimization with feedback is a framework where a learner relies on iterative queries and feedback to arrive at the minimizer of a convex function. It has gained considerable popularity thanks to its scalability in large-scale optimization and machine learning. The repeated interactions, however, expose the learner to privacy risks from eavesdropping adversaries that observe the submitted queries. In this paper, we study how to optimally obfuscate the learner’s queries in convex optimization with first-order feedback, so that their learned optimal value is provably difficult to estimate for an eavesdropping adversary. We consider two formulations of learner privacy: a Bayesian formulation in which the convex function is drawn randomly, and a maximin formulation in which the function is fixed and the adversary’s probability of error is measured with respect to a minimax criterion. Suppose that the learner wishes to ensure the adversary cannot estimate accurately with probability greater than $1/L$ for some $L > 0$ . Our main results show that the query complexity overhead is additive in $L$ in the maximin formulation, but multiplicative in $L$ in the Bayesian formulation. Compared to existing learner-private sequential learning models with binary feedback, our results apply to the significantly richer family of general convex functions with full-gradient feedback. Our proofs rely on tools from the theory of Dirichlet processes, as well as a novel strategy designed for measuring information leakage under a full-gradient oracle.