The Price of Differential Privacy For Online Learning

1. Introduction

• Online learning offers distribution-free guarantees for dynamic, adversarial environments, where algorithms may interact with sensitive user data.Differential privacy is presented as a natural privacy notion for these settings.Source: §1 · p. 1

1.1. Full-Information Setting: Privacy for Free

• In full information, the regret matches the non-private optimum in one privacy regime and remains sub-constant per round in a regime where existing guarantees are vacuous.The analysis also adapts to problem geometry and removes polynomial dependence on N from the sqrt(T) term in some cases.Source: §1.1 · p. 1

1.2. Bandits: Reduction to the Non-private Setting

• The bandit reduction yields private algorithms while retaining the regret bound’s dependence on the number of rounds, and gives the first private bandit linear-optimization algorithm with near-optimal regret.The approach also applies to non-stochastic multi-armed bandits and improves on the previously best bound.Source: §1.2 · p. 2

1.3. Related Work

• Earlier work studied privacy for individual loss-vector entries and later for entire loss vectors; the paper matches an independent non-stochastic multi-armed-bandit result and generalizes it to arbitrary convex sets.The stated earlier privacy settings and results are described in the related-work discussion.Source: §1.3 · p. 2

1.4. Overview of Our Techniques

• The full-information algorithms use tree-based aggregation and analyze per-step noise as a single noise sample, placing its magnitude in the bias term rather than the stability term.For bandit feedback, the reduction adds zero-mean noise to the loss sequence and uses the equality of expected regret on noisy and original sequences.Source: §1.4 · p. 2

Full-Information Setting

• Online linear optimization chooses an action each round, observes a loss vector, and incurs its inner-product loss; regret compares performance with the least-loss fixed action in hindsight.Sublinear regret corresponds to doing almost as well, on average, as that fixed action.Source: §2 · p. 3

Problem Instantiations

• The framework includes prediction with expert advice on the simplex, online linear optimization over the sphere, and online linear optimization over the cube.The passages specify the decision and loss sets for these instances.Source: §2 · p. 3

Partial-Information Setting

• Bandit feedback reveals only the chosen action’s loss, unlike full information, which reveals the complete loss vector.The section notes that this limited feedback makes algorithm design challenging.Source: §2 · p. 3

Differential Privacy

• The privacy definition compares loss sequences differing in one complete loss vector and applies to the algorithm’s entire prediction sequence.The section also notes that online learning typically offers distribution-free guarantees and suits dynamic, adversarial settings.Source: §2 · p. 4

3. Full-Information Setting: Privacy for Free

• The FTRL template uses tree-based private loss estimates to ensure ε-differential privacy, while its linear-loss regret incurs an additive cost.The theorem specifies Laplace noise with scale λ = ∥Y∥1 log T / ε and privacy for the full prediction sequence.Source: §3 · p. 4, §3.1 · p. 5
• The corollary specializes the regret bound to specific online linear optimization instances.It derives each instance’s bound by substituting choices of the regularizer and noise parameter.Source: §3 · p. 4

3.1. Proof of Theorem 3.1

• Tree-based aggregation makes the released prefix sums ε-differentially private, and post-processing transfers that guarantee to the algorithm’s predictions.Identically distributed noise across outputs simplifies the regret analysis but is not essential to privacy.Source: §3.1 · p. 5
• The proof shows that per-step noise and a one-shot noise injection have the same expected regret, so the noise need not be paid at every step in the stability analysis.The analysis uses the FTL-BTL lemma and standard FTRL stability bounds.Source: §3.1 · pp. 5–6

3.2. Regret Bounds for FTPL

• FTPL uses perturbations to obtain differential privacy and O(√T) regret for all instances, but its dimension dependence is suboptimal.Its linear optimization each round may be computationally less expensive than FTRL’s convex program.Source: §3.2 · p. 6

4. Differentially Private Multi-Armed Bandits

• Theorem 4.1 analyzes Algorithm 4 for non-stochastic multi-armed bandits with loss vectors bounded by 1 in l∞ and states a regret guarantee.The supplied theorem passage does not include the bound's complete expression.Source: §4 · p. 6

Bandit Feedback: Reduction to the Non-private Setting

• The bandit reduction adds Laplace noise to feedback from a non-private algorithm to produce an ε-differentially private algorithm.Algorithm 4 forwards the observed scalar loss plus a noise inner product to the inner algorithm.Source: Bandit Feedback: Reduction to the… · p. 7
• With independent zero-mean noise added to each loss vector, expected regret matches the input algorithm's regret on the perturbed sequence.The section's lemma states this relation for full-information or bandit algorithms.Source: Bandit Feedback: Reduction to the… · p. 7

4.1. Proof of Theorem 4.1

• For Algorithm 4, setting λ = 1/ε is sufficient for ε-differential privacy under the stated multi-armed-bandit conditions.The proof invokes the privacy lemma and bounds the action-coordinate loss by 1.Source: §4.1 · p. 7

4.2. Differentially Private Bandit Linear Optimization

• For general convex decision sets, Algorithm 4 with SCRiBLe is ε-private and has a regret guarantee parameterized by the set's self-concordance parameter ν.The passage also specifies the loss bound M and noise scale, but the regret expression is incomplete.Source: §4.2 · p. 8

5. Conclusion

• Differential privacy adds only a constant amount to regret in full-feedback online linear optimization, while the bandit bounds are nearly optimal in T.The authors identify semi-bandit, combinatorial bandit, and contextual bandit extensions, as well as additive separation of ε and T for adversarial bandits, as open questions.Source: §5 · p. 8

A. Proofs for FTPL (Theorem 3.5)

• Theorem A.1 states that the released sequence is (ε, δ)-differentially private and that each cumulative release has Gaussian noise variance ⌈log T⌉σ²I_N.The distribution is stated as N(∑_{s=1}^t l_s, ⌈log T⌉σ²I_N).Source: A. Proofs for FTPL (Theorem 3.5) · p. 10
• The proof obtains privacy for the released sequence by post-processing a sequence already shown to be (ε, δ)-differentially private.The cited proof attributes the earlier privacy result to Jain et al. (2012).Source: A. Proofs for FTPL (Theorem 3.5) · p. 10

B. Noisy OCO Theorem Proof

• The proof uses that the current decision is independent of the round's noise and that the noise has zero mean.It also notes that the algorithm's randomness does not depend on that noise.Source: B. Noisy OCO Theorem Proof · p. 10

• The section states a simple fact for Laplacian distributions, with general versions said to follow immediately.Source: C. Facts about Norms of Laplace Vectors · p. 10
• The proof reduces a probability bound to controlling an exponential random variable with parameter λ.Source: C. Facts about Norms of Laplace Vectors · p. 10
• A union bound completes the proof after the exponential-tail probability is bounded.Source: C. Facts about Norms of Laplace Vectors · p. 10

• D = LapN(λ) ensures ε-differential privacy by Lemma 4.2.Source: D. Proof for Bandit Linear Optimization · p. 10
• For regret analysis, the proof defines pseudo-loss vectors as the losses plus independent Laplace noise.Source: D. Proof for Bandit Linear Optimization · pp. 10–11
• The proof conditions on the complement of the failure event, where the noise vectors remain conditionally independent and Lemma 4.3 still applies.Source: D. Proof for Bandit Linear Optimization · p. 11
• The regret argument invokes a SCRiBLe theorem for compact convex sets with a self-concordant barrier and bounded losses.Source: D. Proof for Bandit Linear Optimization · p. 11