# Prediction with Expert Advice under Local Differential Privacy

arXiv: https://arxiv.org/abs/2512.06971 · HTML: https://mlsanity.com/paper/2512.06971/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 25 of its 46 references that are in the map.
- First posted on arXiv 7 Dec 2025.

## Builds on (most cited first, 25 of 25)

- [Membership Inference Attacks against Machine Learning Models](https://mlsanity.com/paper/1610.05820/) (2016)
- [Extracting Training Data from Diffusion Models](https://mlsanity.com/paper/2301.13188/) (2023)
- [Practical and Private (Deep) Learning without Sampling or Shuffling](https://mlsanity.com/paper/2103.00039/) (2021)
- [Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity](https://mlsanity.com/paper/1811.12469/) (2018)
- [Improved Differential Privacy for SGD via Optimal Private Linear Operators on Adaptive Streams](https://mlsanity.com/paper/2202.08312/) (2022)
- [(Amplified) Banded Matrix Factorization: A unified approach to private training](https://mlsanity.com/paper/2306.08153/) (2023)
- [The Price of Differential Privacy For Online Learning](https://mlsanity.com/paper/1701.07953/) (2017)
- [The Power of Factorization Mechanisms in Local and Central Differential Privacy](https://mlsanity.com/paper/1911.08339/) (2019)
- [Local Privacy, Data Processing Inequalities, and Statistical Minimax Rates](https://mlsanity.com/paper/1302.3203/) (2013)
- [Online Linear Optimization via Smoothing](https://mlsanity.com/paper/1405.6076/) (2014)
- [Private Online Prediction from Experts: Separations and Faster Rates](https://mlsanity.com/paper/2210.13537/) (2022)
- [Privacy Amplification for Matrix Mechanisms](https://mlsanity.com/paper/2310.15526/) (2023)
- [Continuous Release of Data Streams under both Centralized and Local Differential Privacy](https://mlsanity.com/paper/2005.11753/) (2020)
- [Unified Enhancement of Privacy Bounds for Mixture Mechanisms via f-Differential Privacy](https://mlsanity.com/paper/2310.19973/) (2023)
- [Curating a COVID-19 data repository and forecasting county-level death counts in the United States](https://mlsanity.com/paper/2005.07882/) (2020)
- [Concentrated Differential Privacy for Bandits](https://mlsanity.com/paper/2309.00557/) (2023)
- [Prediction by Random-Walk Perturbation](https://mlsanity.com/paper/1302.5797/) (2013)
- [Secure Random Sampling in Differential Privacy](https://mlsanity.com/paper/2107.10138/) (2021)
- [Private Continual Release of Real-Valued Data Streams](https://mlsanity.com/paper/1811.03197/) (2018)
- [Privacy-Preserving Multi-Party Contextual Bandits](https://mlsanity.com/paper/1910.05299/) (2019)
- [Improved Differentially Private and Lazy Online Convex Optimization](https://mlsanity.com/paper/2312.11534/) (2023)
- [Private Online Learning via Lazy Algorithms](https://mlsanity.com/paper/2406.03620/) (2024)
- [Federated Online Prediction from Experts with Differential Privacy: Separations and Regret Speed-ups](https://mlsanity.com/paper/2409.19092/) (2024)
- [Tracking the Best Expert Privately](https://mlsanity.com/paper/2503.09889/) (2025)
- [How to Securely Shuffle? A survey about Secure Shufflers for privacy-preserving computations](https://mlsanity.com/paper/2507.01487/) (2025)

## Abstract (arXiv)

We study the classic problem of prediction with expert advice under the constraint of local differential privacy (LDP). In this context, we first show that a classical algorithm naturally satisfies LDP and then design two new algorithms that improve it: RW-AdaBatch and RW-Meta. For RW-AdaBatch, we exploit the limited-switching behavior induced by LDP to provide a novel form of privacy amplification that grows stronger on easier data, analogous to the shuffle model in offline learning. Drawing on the theory of random walks, we prove that this improvement carries essentially no utility cost. For RW-Meta, we develop a general method for privately selecting between experts that are themselves non-trivial learning algorithms, and we show that in the context of LDP this carries no extra privacy cost. In contrast, prior work has only considered data-independent experts. We also derive formal regret bounds that scale inversely with the degree of independence between experts. Our analysis is supplemented by evaluation on real-world data reported by hospitals during the COVID-19 pandemic; RW-Meta outperforms both the classical baseline and a state-of-the-art textitcentral DP algorithm by 1.5-3× on the task of predicting which hospital will report the highest density of COVID patients each week.