analiza aiqbench
This arXiv paper gives the first differentially private algorithm for online prediction from experts with regret scaling as $\tilde{O}(\sqrt{L^\star})$ instead of $\tilde{O}(\sqrt{T})$, which matters most when the best expert's cumulative loss is small. The authors argue the bound nearly matches the non-private lower bound, so privacy costs little in that regime. The result holds only for oblivious input sequences, and the authors show that adaptive inputs force $\tilde{\Omega}(\sqrt{T})$ regret, a limitation practitioners should weigh.
Private Online Prediction from Experts with Small Losses
arXiv:2610.29575v1 Announce Type: new 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{\Omega}(\sqrt{T})$ regret is inevitable for adaptively generated inputs, even when $L^\star = 0$.
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{\Omega}(\sqrt{T})$ regret is inevitable for adaptively generated inputs, even when $L^\star = 0$.
Machine Learning (cs.LG); Machine Learning (stat.ML)
arXiv:2610.29575 [cs.LG]
(or arXiv:2610.29575v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2610.29575 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Text integral sub licența deschisă a publicației · 232 cuvinte
Subiecte conexe
Certification-Based Differentially Private Learning
arXiv · 1 oct. 2026
Private Prediction via PAC Privacy
arXiv · 15 iun. 2026
Private online learning and prediction for Littlestone classes
arXiv · 6 oct. 2026
PAC-Private Autoregressive Generation: Calibrating Noise to Ensemble Disagreement
arXiv · 9 sept. 2026