Private online prediction gets better with fewer mistakes
Private Online Prediction from Experts with Small Losses
Machine Learning
Summary
Online prediction means choosing the best option by learning from experts, but keeping these predictions private is tricky. Earlier methods worked well overall but slowed down when the best expert made very few mistakes. The authors created a new method that stays private while doing almost as well as the best expert, even when that expert barely makes errors. This change means privacy doesn’t cost much extra in these cases, but only when the data is fixed ahead of time, not changing based on what the algorithm predicts.
What this means in practice
- •For machine learning engineers: Design private prediction models that adapt efficiently when the best option rarely errs in fixed data scenarios.
- •For data privacy teams: Improve privacy guarantees for sequential decision-making systems where input data is predetermined and not influenced by prior outputs.
A theory result. No direct application yet.
Authors
Bo Li, Peng Ye
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$.