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

Spanish

Consideramos la predicción en línea de los expertos, un problema fundamental en el aprendizaje automático, bajo restricciones de privacidad diferenciales. Los algoritmos privados existentes reportan un lamento casi óptimo $\tilde{O}(\sqrt{T})$, donde $T$ es el horizonte del tiempo. Sin embargo, este vínculo se vuelve suboptimal cuando $L^star$, la pérdida acumulativa del mejor experto, es significativamente menor que $T$. En este trabajo, presentamos el primer algoritmo privado diferencial con lamento $\tilde{O}(\sqrt{L^\star})$, ofreciendo una mejora sustancial en el régimen de baja pérdida. Nuestro vínculo de lamento coincide con la pérdida no privada ligada a factores poli-logarítmicos

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