Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 21 min ago
PreprintCC BY 4.0arXiv

Private Online Prediction from Experts with Small Losses

  • Bo Li
  • Peng Ye
Open at sourcePDFDOICite

Abstract

We consider online prediction from experts, a fundamental problem in machine learning, under differential privacy constraints. Existing private algorithms achieve near-optimal regret Õ(√T), where T is the time horizon. However, this bound becomes suboptimal when L⋆, the cumulative loss of the best expert, is significantly less than T. In this work, we present the first differentially private algorithm with regret Õ(√(L⋆)), 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 Ω̃(√T) regret is inevitable for adaptively generated inputs, even when L⋆ = 0.

Related

  1. Tracking a Small Set of Experts in Online Convex Optimization
    Angelos Assos, Anand Brahmbhatt, Elad Hazan
    arXivPreprintCC BY 4.0Full textOptimisation & controlStatisticsarXiv
  2. Private online learning and prediction for Littlestone classes
    Amartya Sanyal
    arXivPreprintCC BY 4.0Full textStatisticsarXiv
  3. Online Learning with LLM Experts from Limited Feedback
    Wang Wei, Soumyabrata Pal, Koyel Mukherjee +4
    arXivPreprintCC BY 4.0Full textStatisticsarXiv
  4. Online Quantile Omniprediction for Proper Losses
    Hyunsuk Kim, Isaac Gibbs, Michael W. Mahoney +1
    arXivPreprintarXiv licenceFull textStatisticsarXiv
  5. Online Learning-to-Defer with Varying Experts
    Dang Hoang Duy, Yannis Montreuil, Maxime Meyer +3
    arXivPreprintCC BY 4.0Full textStatisticsarXiv

Cite

BibTeXRIS
BibTeX
@misc{li2026private,
  title = {{Private Online Prediction from Experts with Small Losses}},
  author = {Bo Li and Peng Ye},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.29575},
  eprint = {2610.29575},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.29575},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Private Online Prediction from Experts with Small Losses
AU  - Bo Li
AU  - Peng Ye
PY  - 2026
DA  - 2026/10/24
PB  - arXiv
DO  - 10.48550/arxiv.2610.29575
UR  - https://arxiv.org/abs/2610.29575
AB  - We consider online prediction from experts, a fundamental problem in machine learning, under differential privacy constraints. Existing private algorithms achieve near-optimal regret Õ(√T), where T is the time horizon. However, this bound becomes suboptimal when L^⋆, the cumulative loss of the best expert, is significantly less than T. In this work, we present the first differentially private algorithm with regret Õ(√(L^⋆)), 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 Ω̃(√T) regret is inevitable for adaptively generated inputs, even when L^⋆ = 0.
ER  -