VC 维度 1 概念类的差分隐私学习器最优解

我们提出了首个针对 VC 维度 1 和 Littlestone 维度 d 的概念类的近乎最优差分隐私 PAC 学习器。该算法实现了Õε,δ,α,δ(log∗d)的样本复杂度，基本匹配 Alon 等人在 STOC19 上证明的Ω(log∗d)下界。在本文工作之前，Ghazi 等人在 STOC21 上展示的最佳已知上界是针对通用 VC 类的Õ(VC·d^5)。

更多精彩内容 请关注我的个人公众号 公众号（办公 AI 智能小助手）公众号二维码

办公AI智能小助手