面向专家的差分隐私在线预测：低损失情形下实现 Õ(√L⋆) 遗憾界

该论文提出首个在专家在线预测中达到 Õ(√L⋆) 遗憾界的差分隐私算法，其中 L⋆ 为最优专家的累计损失，在低损失情形下显著优于既有 Õ(√T) 界。当隐私参数为常数时，该界与非隐私下界仅差多对数因子，表明此设定下隐私代价很小。结果依赖输入序列为 oblivious（预先固定且与算法输出无关），作者同时证明自适应生成的输入即使 L⋆ = 0 也无法避免 Õ(√T) 遗憾。