Differentially Private Online Prediction from Experts: Near-Optimal Regret Bounds with Small Losses

Title

Differentially Private Online Prediction from Experts: Near-Optimal Regret Bounds with Small Losses

Meta Description

New differentially private online prediction from experts algorithm achieves Õ(√L*) regret under oblivious inputs, approaching the non-private optimum for small losses; also proves Ω̃(√T) regret is unavoidable under adaptive inputs.

Article Content

Online Prediction from Experts is a fundamental problem in machine learning, with broad applications in scenarios such as ad recommendation and portfolio selection. When differential privacy constraints are introduced, existing algorithms can achieve a near-optimal Õ(√T) regret bound (where T is the number of time steps). However, when the cumulative loss L* of the best expert is much smaller than T, this bound becomes suboptimal. A recent paper proposes the first differentially private algorithm that achieves an Õ(√L*) regret bound in the small-loss regime, significantly improving performance in the low-loss region, and proves that under constant privacy parameters, it differs from the non-private lower bound by only polylogarithmic factors.

Problem Background: Online Prediction from Experts and Differential Privacy

In the online prediction from experts problem, the learner selects one of N experts each round and incurs the loss of the chosen expert. The goal is to minimize the difference between the cumulative loss and the cumulative loss L* of the best expert (i.e., the regret). Classic algorithms such as Hedge achieve O(√(T log N)) regret under oblivious inputs (where the input sequence is fixed in advance), and this bound is tight in general.

Differential privacy requires that the algorithm's output be insensitive to changes in any single input, in order to protect user data. Existing private algorithms achieve privacy by adding noise, but this often leads to degraded regret bounds. The previous best private algorithm had a regret bound of Õ(√T), which is far above the non-private lower bound of Õ(√L*) when L* ≪ T.

Core Contribution: A Near-Optimal Private Algorithm for Small Losses

The paper proposes the first differentially private algorithm that achieves an Õ(√L*) regret bound under oblivious inputs. This bound differs from the non-private lower bound by only polylogarithmic factors under constant privacy parameters, indicating that the cost of privacy is very small in the small-loss regime. The algorithm is based on the differentially private Follow-the-Regularized-Leader framework, adaptively adjusting the learning rate and noise scale to leverage the concentration of the loss sequence when L* is small, thereby reducing the impact of noise.

Theoretical analysis shows that the algorithm's regret upper bound is O(√(L* log N) + √(T log N)/ε), where ε is the privacy parameter. When L* is small, the first term dominates, approaching the non-private optimum. This result applies to oblivious inputs, i.e., where the input sequence is independent of the algorithm's outputs.

The Unavoidability of Adaptive Inputs

The paper further proves that for adaptively generated inputs (i.e., inputs that may depend on the algorithm's previous outputs), even when L* = 0, no differentially private algorithm can avoid Ω̃(√T) regret. This shows that the cost of privacy is unavoidable in adaptive settings, in stark contrast to the oblivious case. This lower bound is proven by constructing an adversarial environment in which the loss sequence is dynamically adjusted based on the algorithm's outputs, forcing the algorithm to explore.

This result clarifies the limitations of private online learning: in adaptive scenarios, the small-loss advantage cannot be achieved, and privacy necessarily leads to increased regret.

Significance and Outlook

This work fills the gap in private online learning in the low-loss regime, providing a more efficient privacy protection scheme for practical applications with small losses (e.g., concentrated user interests in recommendation systems). Future directions include relaxing the oblivious assumption, studying more general privacy models (such as local differential privacy), and extending the techniques to other online learning problems (such as bandit feedback).

One-line Summary

The first differentially private online experts algorithm achieves Õ(√L*) regret for small losses and proves Ω̃(√T) is unavoidable under adaptive inputs.

Paragraph Summary

This paper studies online prediction from experts under differential privacy constraints. Existing private algorithms have a regret bound of Õ(√T), which is suboptimal when the best expert's cumulative loss L* is much smaller than T. The paper proposes the first differentially private algorithm that achieves Õ(√L*) regret under oblivious inputs, differing from the non-private lower bound by only polylogarithmic factors. The algorithm is based on the differentially private FTRL framework, adaptively adjusting the learning rate and noise scale to leverage the concentration of the loss sequence under small losses to reduce the impact of noise. The theoretical bound is O(√(L* log N) + √(T log N)/ε). The paper further proves that for adaptive inputs, even when L*=0, no differentially private algorithm can avoid Ω̃(√T) regret, indicating that the cost of privacy is unavoidable in adaptive settings. This work fills the gap in private online learning in the low-loss regime.