Tracking The Best Expert Privately
Authors: Hilal Asi, Vinod Raman, Aadirupa Saha
ICML 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We design differentially private algorithms for the problem of prediction with expert advice under dynamic regret, also known as tracking the best expert. Our work addresses three natural types of adversaries, stochastic with shifting distributions, oblivious, and adaptive, and designs algorithms with sub-linear regret for all three cases. We develop new algorithms and lower bounds for each of these adversaries, demonstrating the near-optimality of our algorithms in several settings, and the hardness of the dynamic setting compared to the well-studied static setting. |
| Researcher Affiliation | Collaboration | 1Apple 2Department of Statistics, University of Michigan, Ann Arbor. Work done while interning at Apple 3University of Illinios, Chicago. The majority of the work was done while the author was with Apple Research. |
| Pseudocode | Yes | Algorithm 1 Limited Updates for Online Optimization with Stochastic Adversaries. Algorithm 2 SVT-based algorithm. Algorithm 3 Private Online Learner for Adaptive Adversaries. |
| Open Source Code | No | The paper does not provide any statement about releasing source code, nor does it include links to a code repository or mention code in supplementary materials. |
| Open Datasets | No | The paper is theoretical, presenting algorithm design, proofs, and bounds for differentially private online prediction. It does not describe any empirical studies or use specific datasets for experimentation. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical evaluation on datasets, thus no dataset splits are discussed. |
| Hardware Specification | No | The paper describes theoretical algorithms and their mathematical properties, including regret bounds and privacy guarantees. It does not mention any experimental evaluation or specific hardware used for computations. |
| Software Dependencies | No | The paper focuses on theoretical contributions and does not describe any specific software implementations or dependencies with version numbers for its algorithms. |
| Experiment Setup | No | The paper is theoretical, presenting algorithms, lower bounds, and upper bounds for differentially private online prediction. It does not include an experimental section with details on hyperparameters, training configurations, or system-level settings. |