从私有候选对象中进行私有选择

Differentially Private 算法通常需要在众多候选选项中选择最佳者。关于该选择问题的经典研究要求候选对象的优度（以实值评分函数衡量）在单个个体的数据发生改变时不会产生太大变化。在诸如超参数优化等众多应用中，这种稳定性假设过于严苛。在本项工作中，我们在对候选对象弱得多的稳定性假设下研究了该选择问题，即评分函数本身具有差分隐私性。在此假设下，我们提出了在三个相关维度上均接近最优的算法：隐私性、效用和计算效率。