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

Korean

우리는 기계 학습에서 근본적인 문제인 온라인 예측을 고려합니다. 차별적 개인 정보 보호 제한에 따라 기존 개인 알고리즘은 거의 최적의 후회 $\tilde{O}(\sqrt{T})$를 보고 있지만, $T$는 시간 지평선입니다. 그러나이 약속은 $L^\star$, 최상의 전문가의 누적 손실이 $T$보다 훨씬 적습니다. 이 작업에서 우리는 $\tilde{O}(\sqrt{O})$를 후회 $\sqrt{L^\star})$로 첫 번째 차별적 개인 알고리즘을 제시하여 낮은 손실 제도에서 상당한 개선을 제공합니다. 우리의 약속은 $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