Newest papers

Private Online Prediction from Experts with Small Losses

Bo Li, Peng Ye · 2026 · arXiv (Cornell University)

DOI: 10.48550/arxiv.2610.29575 · cited by 0 works (OpenAlex) · open-access PDF

Chinese

我们认为专家的在线预测,在机器学习中的一个根本问题,在差异性隐私限制下。现有的私人算法报告近于最佳的遗憾 $\tilde{O}(\sqrt{T})$,在那里 $T$是时间地平线。然而,当 $L^\star$,最好的专家的累积损失,显著小于 $T$时,这种约束变得不优化。在这项工作中,我们介绍了第一个差异性私人算法与遗憾 $\tilde{O}(\sqrt{L^\star})$,在低损失模式中提供了显着的改进。我们的遗憾约束匹配了非私人低约束到聚合逻辑学因素的恒定的隐私参数,这表明隐私在这种设置中只产生了小

Machine translation (Meta M2M100); the English original follows.

Abstract

We consider online prediction from experts, a fundamental problem in machine learning, under differential privacy constraints. Existing private algorithms achieve near-optimal regret $\tilde{O}(\sqrt{T})$, where $T$ is the time horizon. However, this bound becomes suboptimal when $L^\star$, the cumulative loss of the best expert, is significantly less than $T$. In this work, we present the first differentially private algorithm with regret $\tilde{O}(\sqrt{L^\star})$, offering a substantial improvement in the low-loss regime. Our regret bound matches the non-private lower bound up to poly-logarithmic factors for constant privacy parameters, demonstrating that privacy incurs only a small cost in this setting. Our result assumes that the input sequence is oblivious, i.e., it is fixed in advance and independent of the algorithm's outputs. We also prove that an $\tildeΩ(\sqrt{T})$ regret is inevitable for adaptively generated inputs, even when $L^\star = 0$.

Read in: English · Spanish · Chinese · Hindi · Arabic · Portuguese · French · German · Japanese · Russian · Korean · Indonesian · Vietnamese

Topics: Regret, Differential privacy, Upper and lower bounds, Constant (computer programming), Computer science, Private information retrieval

Sources: OpenAlex (CC0), arXiv, Crossref. Agent Exchange