Private Online Prediction from Experts with Small Losses

Bo Li; Peng Ye

Source-linked AI summary

Private Online Prediction from Experts with Small Losses

Bo Li, Peng Ye

arXiv:2610.29575v1Oct 21, 2026cs.LGstat.ML

TL;DR

Private online prediction from experts has worst-case regret guarantees that do not capture the low-loss regime, and prior private methods do not adapt to small best-expert loss. This paper proposes a data-dependent private algorithm for oblivious inputs and proves that adaptively generated inputs still require large regret, even when the best expert has zero loss.

Problem
Existing private OPE guarantees are unfavorable when the best expert’s cumulative loss is much smaller than T, while privacy constraints prevent direct use of the larger learning rate used for non-private adaptation.
Source: §1 · p. 1
Method
The paper proposes the first differentially private OPE algorithm with a data-dependent regret bound for oblivious input sequences.
Source: §1.1 · p. 2
Results
The bound nearly matches the non-private lower bound up to poly-logarithmic factors for constant privacy parameters, while adaptive inputs require ˜Ω(√T) regret even when L⋆ = 0.
Source: §5 · p. 10
Takeaways & Limitations
For oblivious inputs, the paper’s result suggests privacy incurs only a mild cost in the low-loss regime.
Source: §5 · p. 10
When L⋆ = Θ(T), a term in the paper’s bound is larger than Asi et al.’s pure-DP bound by O(log T/ε).
Source: §5 · p. 10

Abstract

from arXiv · show

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$.

1 Introduction

Online prediction from experts compares a learner’s cumulative loss with the best expert’s loss, but private worst-case regret is poorly suited to low-loss settings. The paper introduces a private data-dependent bound for oblivious inputs and establishes a separate adaptive-input lower bound.

1 Introduction

Worst-case regret can exceed the best expert’s loss substantially when that loss is small, making existing private O(√T)-type guarantees inadequate in this regime.For L⋆ = T^1/4, the cited example says an algorithm with regret √T may incur loss T^1/4 times the best expert’s loss.Source: §1 · p. 1
Existing private algorithms constrain the learning rate to preserve differential privacy, preventing direct adaptation to small L⋆.The non-private larger-learning-rate remedy achieves O(√(L⋆ log N) + log N), but the introduction says it cannot be applied directly under DP.Source: §1 · p. 2

1.1 Our contribution

The paper proposes the first private OPE algorithm with data-dependent regret that nearly matches the non-private low-loss lower bound.The result applies to oblivious inputs; the paper also establishes that adaptive inputs preclude the same improvement, even when L⋆ = 0.Source: §1.1 · p. 2
The paper’s adaptive-input lower bound extends the impossibility of small-loss improvement beyond pure differential privacy.Prior work established an Ω(T) lower bound under pure DP; this paper additionally proves a ˜Ω(√T) lower bound under approximate DP, including when L⋆ = 0.Source: §1.1 · p. 2

1.2 Related work

Non-private OPE methods achieve O(√(L⋆ log N) + log N), and this rate is asymptotically optimal.The passage names multiplicative weights and follow-the-perturbed-leader as methods attaining this bound.Source: §1.2 · p. 2
Prior work gives private OPE regret of ˜O(√T), while realizable-setting algorithms extend to agnostic inputs with a ˜O(L⋆) bound.The paper contrasts these guarantees with its low-loss result and notes that the agnostic bound is far from optimal.Source: §1.2 · pp. 2–3, §1.1 · p. 2

2 Preliminaries

The preliminaries define the oblivious online prediction game and its privacy framework. They also introduce multiplicative weights and AboveThreshold as tools relevant to the paper’s analysis.

2 Preliminaries

An oblivious adversary fixes T loss functions in advance, and the learner chooses an expert before seeing each round’s loss.Each expert’s loss lies in [0,1], and the learner’s performance is assessed by expected regret.Source: §2 · p. 3
The best expert’s cumulative loss is fixed in advance under an oblivious adversary, but remains unknown to the learner until the sequence ends.The passage defines this comparator loss as L⋆.Source: §2 · p. 3
Multiplicative weights samples an expert each round using a learning rate η, with a stated expected-regret upper bound.The supplied passage identifies the method and parameter but does not include the bound’s expression.Source: §2 · p. 3
Differential privacy bounds how output distributions can change between input sequences differing in one loss function.When δ = 0 the definition is pure DP; when δ > 0 it is approximate DP.Source: §2 · p. 3
AboveThreshold privately identifies the first sensitivity-1 query that exceeds a prespecified threshold.Its accuracy guarantee bounds positive and negative threshold-crossing outcomes within α.Source: §2 · p. 3
Each multiplicative-weights sampling step is the exponential mechanism with privacy parameter 2η.The passage connects this property with advanced composition in private OPE algorithms.Source: §2 · p. 4

3 Algorithm and analysis

The algorithm reduces data-dependent updates by delaying them until losses reach a threshold, using AboveThreshold to implement the delay. Its privacy analysis treats the process as an interactive transcript with multiple mechanisms.

3 Algorithm and analysis

Earlier private shrinking-dartboard approaches force data-independent updates, which constrain the learning rate and yield a ˜O(T^1/3) regret bound.The cited account says this bound exceeds the desired ˜O(√L⋆) regime.Source: §3 · p. 4
Delayed, probabilistic updates let the algorithm use a larger learning rate while retaining the shrinking-dartboard approach’s potential for smaller regret.The design makes updates after the selected expert incurs sufficiently large loss and uses AboveThreshold for the delay; update-probability bounds and an update cap are also imposed for privacy.Source: §3 · p. 4

3.1 Privacy analysis

Algorithm 1 is (ε, δ)-differentially private for ε = ε1 + max(η, ε2) + Compδ(V, 2η).The composition term accounts for V mechanisms with privacy parameter 2η.Source: §3.1 · p. 4
The proof analyzes an augmented transcript containing the initial expert, AboveThreshold outputs, Z values, and experts sampled during resampling.The learner’s output sequence is a post-processing of that transcript.Source: §3.1 · p. 4
The privacy proof treats the algorithm as concurrent composition of threshold mechanisms, Z generation, and at most V resampling mechanisms.For neighboring inputs differing at one round, it analyzes a common prefix of the interaction transcript.Source: §3.1 · p. 4

28 end

The analysis bounds the algorithm’s privacy loss across its interactive mechanisms and shows that the number of updates scales with the best expert’s loss. This update bound permits a larger learning rate and supports a regret bound tuned to L⋆.

28 end

The proof combines AboveThreshold instances, Z_u generation, and at most V resampling steps; concurrent composition gives an (ε, δ)-differentially private transcript.The learner’s output sequence inherits this guarantee by post-processing.Source: §28 · pp. 5–6
Only one Z_j can contribute privacy loss across neighboring inputs because the intervals for generated Z_u values are disjoint and later Z_u values have identical conditional distributions.The Z_u generation is therefore max(η, ε2)-differentially private.Source: §28 · pp. 5–6

3.2 Regret analysis

With high probability, the number of updates is ˜O(ηL⋆), allowing the algorithm to work normally with V = ˜O(ηL⋆) and choose η to minimize regret.The analysis identifies this update bound as the basis for the learning-rate choice under composition.Source: §3.2 · p. 6
The regret analysis bounds the update count’s tail by a Chernoff bound, setting n = 70m + 280 ln(1/β2) when 0.03n ≥ 2m.Here, m is the smallest positive integer with s_m = T.Source: §3.2 · pp. 6–7

19 end

The analysis compares Algorithm 1’s output distribution with multiplicative weights to derive a regret bound. A doubling trick addresses the fact that L⋆ is unknown at the start.

19 end

With high probability, Algorithm 1’s output distribution at each round is pointwise at most e^{O(η(τ+log T/ε1))} times the multiplicative-weights distribution, leading to a regret bound.The passage also approximates this factor as 1 + O(ητ + η log T/ε1).Source: §19 · p. 9
Fixing AboveThreshold randomness induces a delay function under which Algorithm 1 and Algorithm 2 behave identically before round t when V ≥ T.The comparison is used to relate Algorithm 1’s output distribution to that of multiplicative weights.Source: §19 · p. 9
Because L⋆ is unknown initially, the paper uses a doubling trick that assumes it is small and doubles the estimate once it becomes inaccurate.The detailed implementation is deferred to Appendix A.Source: §19 · p. 10

4 Lower bound for adaptive adversaries

For adaptive inputs, the lower-bound argument reduces the privacy parameter through Bernoulli subsampling and applies an existing regret lower bound. The resulting reduction gives a lower bound on the original algorithm’s regret.

4 Lower bound for adaptive adversaries

For adaptive inputs, [3] states that every adaptively (ε, δ)-differentially private OPE algorithm with N ≥ 2T experts incurs Ω(T) regret in the high-privacy regime.Source: §4 · p. 10
The reduction shows that an algorithm with regret RA(T) yields a subsampled algorithm with privacy O(qε) and regret at most RA(T)/q.The subsampled algorithm forwards the original algorithm’s outputs while feeding it Bernoulli(q)-scaled losses.Source: §4 · p. 10
Applying the adaptive lower bound from [3] to the subsampled algorithm yields RA(T) = Ω(qT).The passage rewrites this as ˜Ω(min(T, …)), but the expression is truncated there.Source: §4 · p. 10
The privacy-amplification argument for adaptive inputs requires a more sophisticated analysis than the oblivious-input case.The formal proof is deferred to Appendix C.Source: §4 · p. 10

5 Discussion and future work

The paper gives a differentially private OPE algorithm with data-dependent regret that matches the non-private lower bound up to polylogarithmic factors for constant privacy parameters. It also identifies limits of the result for adaptive inputs and for some large-loss parameter ranges.

5 Discussion and future work

The proposed private OPE algorithm matches the non-private lower bound up to polylogarithmic factors for constant privacy parameters.The authors describe the privacy cost as mild in the low-loss regime.Source: §5 · p. 10
An adaptive adversary prevents the low-loss improvement: the paper proves that regret of ˜Ω(T) is necessary even when L⋆ = 0.The result rules out this improvement for adaptively generated inputs.Source: §5 · p. 10
For large L⋆, the bounds are slightly worse than those of Asi et al. [3] [4] in certain parameter ranges.The paper identifies improving these bounds to match prior results as a future direction.Source: §5 · p. 10

A Algorithm without prior knowledge of L⋆

The appendix constructs an algorithm without prior knowledge of L⋆ by first analyzing algorithms given an estimate L′ ≥ L⋆. It provides pure- and approximate-DP guarantees for those estimates.

A Algorithm without prior knowledge of L⋆

The appendix establishes an ε-differentially private OPE algorithm with an expected-regret guarantee when an estimate L′ ≥ L⋆ is supplied.Theorem A.1 assumes ε ≤ 1 and L′ > 0.Source: A Algorithm without prior knowledge of… · p. 12
For the pure-DP construction, the proof chooses η to satisfy privacy and threshold constraints, then applies composition to establish ε-differential privacy.The proof also invokes L⋆ ≤ L′ to bound expected regret.Source: A Algorithm without prior knowledge of… · pp. 12–13
Theorem A.2 gives an expected-regret guarantee for an (ε, δ)-differentially private algorithm when L′ > 0.Its stated parameter range is ε ≤ 1 and 0 < δ ≤ 1/2.Source: A Algorithm without prior knowledge of… · p. 12
The algorithm uses AboveThreshold to test the current estimate and starts a new learning instance when the estimate is increased.The appendix’s construction is intended to remove the need for prior knowledge of L⋆.Source: A Algorithm without prior knowledge of… · p. 13

15 end

Algorithm 3 combines AboveThreshold tests with learning instances run on successive portions of the loss sequence. The lemma analyzes privacy through composition and utility by bounding regret across the resulting buckets.

15 end

The privacy proof combines the private termination-time transcript with the learning instances’ outputs to establish the algorithm’s (ε, δ)-differential privacy.Conditioned on termination times, at most one learning instance receives the differing loss, permitting parallel composition.Source: §15 · p. 14
With probability 1 − 1/T, all AboveThreshold applications are α-accurate, and the utility proof first conditions on this event.At each threshold crossing, the learning instance’s regret is bounded by R(3·2^kα).Source: §15 · p. 14
The proof bounds the number of buckets by K and sums the regret bounds over them.The final bucket also satisfies the regret bound when no ⊤ is returned.Source: §15 · p. 14
Because regret is at most T, the proof bounds unconditional expected regret using this worst-case limit.The bound is introduced after the utility analysis conditioned on the accuracy event.Source: §15 · p. 14

B Construction of the delay function

The delay function records when a fixed AboveThreshold instance first returns ⊤ for a specified start round, expert index, and instance number. The construction fixes the random variables in advance and assigns T + 1 when no such round exists.

B Construction of the delay function

The construction fixes the round-wise ν values and the ξ value associated with each AboveThreshold instance before defining the delay function.ξ_u is the ξ variable used by the u-th mechanism.Source: B Construction of the delay function · p. 14
For each tuple of start round, expert index, and instance number, the delay is the first round satisfying the mechanism’s ⊤ condition, or T + 1 if none exists.The construction defines this mapping for every tuple in [T] × [N] × [T].Source: B Construction of the delay function · p. 14
Algorithm 4 implements AboveThreshold by checking each incoming query against the threshold with its random offsets.The displayed steps receive q_t and test q_t + ν_t ≥ τ + ξ.Source: B Construction of the delay function · p. 15

C Lower bound for adaptive adversaries

The appendix proves that adaptive inputs constrain private online prediction even when a best expert has zero loss. It uses Poisson sampling to transfer a high-privacy lower bound into a regret lower bound.

C Lower bound for adaptive adversaries

The proof applies a high-privacy lower bound requiring ε ≤ 1/(T ln T) to show expected cumulative loss Ω(T).The cited lower bound assumes sufficiently large T and N ≥ 2T.Source: C Lower bound for adaptive adversaries · pp. 15, 17
The proof concludes that the adaptive-input improvement cannot be achieved even under approximate differential privacy.The construction uses a realizable sequence, so the best expert has zero loss.Source: C Lower bound for adaptive adversaries · p. 15
Poisson sampling converts an algorithm A into A_q by feeding it losses Z_tℓ_t, with independent Z_t ∼ Ber(q), while forwarding A’s output.On realizable inputs, A_q remains realizable and its expected cumulative loss is bounded by R_A(T)/q.Source: C Lower bound for adaptive adversaries · pp. 15–17
If A is adaptively (ε, δ)-differentially private, A_q is adaptively (ln(1 + q(e^ε − 1)), qδ)-differentially private.The proof compares auxiliary adversary-view distributions and uses post-processing to establish the privacy guarantee.Source: C Lower bound for adaptive adversaries · pp. 15–16
For sufficiently large T and N ≥ 2T, any adaptively (ε, δ)-differentially private OPE algorithm with ε ≤ 1 and δ ≤ T^-3 admits an adaptive adversary generating losses with L⋆ = 0.Source: C Lower bound for adaptive adversaries · p. 17