提出可私密学习决策列表与大间隔半空间的新算法，兼顾效率与隐私保护。
Privately Learning Decision Lists and a Differentially Private Winnow
- 基于差分隐私设计新算法，样本开销接近非私密最优水平
- 在线模型中实现误判次数仅随维度对数增长，且与边界大小相关
- 适用于需保护数据隐私的机器学习场景，如医疗、金融建模
我们为经典的学习问题——决策列表和大间隔半空间，在PAC模型和在线模型中提出了新的差分隐私算法。在PAC模型中，给出了一个计算高效的算法，学习决策列表的样本开销几乎与最优非私密算法持平。在在线模型中，提出了一个私密版的著名Winnow算法，能够学习半空间，其误判次数在维度上为多对数级，在边界大小上为多项式倒数级。作为应用，描述了如何在在线模型中私密学习决策列表，其性能定性上达到当前非私密最优水平。
原文摘要 · Abstract (English)
We give new differentially private algorithms for the classic problems of learning decision lists and large-margin halfspaces in the PAC and online models. In the PAC model, we give a computationally efficient algorithm for learning decision lists with minimal sample overhead over the best non-private algorithms. In the online model, we give a private analog of the influential Winnow algorithm for learning halfspaces with mistake bound polylogarithmic in the dimension and inverse polynomial in the margin. As an application, we describe how to privately learn decision lists in the online model, qualitatively matching state-of-the art non-private guarantees.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。