Private Learning Fast and Slow: Two Algorithms for Prediction with Expert Advice Under Local Differential Privacy

Thank you for your helpful comments and kind words about the importance of our problem! We respond to all of your questions and concerns one-by-one below:

W1: We understand and sympathize with this frustration. One of the struggles in writing this paper has been that the main results we prove are very difficult to express in a clean, decontextualized way. We can say a lot about the privacy amplification of RW-AdaBatch both theoretically and empirically, but there’s no closed form expression for the exact tradeoff function that we can present as a standalone theorem. Similarly, the regret bound of RW-Meta is difficult to understand until the reader has the context to understand the meaning of the $\Sigma^*$ matrix. We absolutely understand that this makes things more difficult for the reader, and as part of our revision have tried to do a better job of highlighting our results in a simple and direct way at the beginning of each section whenever possible (e.g. “We show that the expected regret of RW-AdaBatch is at most $(1+\sqrt{2}\alpha)$ times greater than the expected regret of RW-FTPL”). To some extent, however, we fear that this weakness might be a necessary consequence of the kinds of results that we prove.

W2: This is a valid observation, and so we have added in an explicit comparison with the FTPL algorithm of Agarwal and Singh 2017, which is the state of the art central-DP algorithm in the sorts of low-dimensional settings that we target. We agree that this comparison can help shed light on the cost of satisfying local DP, as well as the relative benefit of moving beyond the existing paradigm of data-independent experts used in prior work.

W3: In the case of RW-AdaBatch, we wish to emphasize that the privacy gain we provide is very nearly free - there is only minimal computational overhead, and the impact on regret is provably insignificant. In that context, we would argue that even a moderate increase in privacy is noteworthy, particularly because a constant-factor improvement in privacy can normally only be achieved by a constant-factor degradation in utility.

In the case of RW-Meta, we would push back against the characterization that we improve utility only by a small constant factor. In terms of absolute performance, we improve over RW-FTPL by a factor of more than 2x in most settings, and improve over the state of the art central DP algorithm by 50% or more. We feel that this constitutes a significant improvement, especially because in many settings we actually achieve negative static regret - given the fundamental limitations of data-independent experts, the gap in performance we observe is almost certainly not surmountable by future algorithmic improvements to static experts algorithms.

Q1: The regret is with respect to the non-noisy data - this is defined slightly earlier at the beginning of the utility analysis section (line 352 of the updated version).

Q2: This is a very good question which gets to the heart of our technical contribution. The key issue is that we need our entire system to satisfy DP, not just a single component. If we want to identify learners that have done well on the data so far, we need to expend privacy budget to do that. But at the same time, if we want non-trivial learners that can change their predictions based on the data so far, then we need to expend privacy budget on that too. If we treat these two components separately, then we’ll be forced to split the privacy budget between them and accept some combination of A) less accurate learners overall or B) less precise identification of the best learners.

RW-Meta can basically be thought of as a technique to avoid having to make that choice. We expend 100% of our privacy budget on making the learners as accurate as possible, but still manage to select strong learners with reasonable accuracy by exploiting some useful properties of Gaussian noise as well as the linearity of our gain functions. This gives us higher overall utility at the same privacy cost compared to just using RW-FTPL over the learners directly.

Q3: Thank you for the suggestion! We have revised Table 1 to include a column for the best-performing linear model in each setting, alongside the newly added central-DP algorithms.

Q4: This is a typo, thank you for catching it!

Q5: Yes, this has been clarified in the revision.

Q6: These are the same $\alpha$ and $\beta$ functions as in the immediately preceding lemma (now 4.2.2), defined in terms of the specific mixture of Gaussians that we prove is a lower bound for RW-AdaBatch’s tradeoff function. We have added some extra text to clarify this.

Thank you for your positive comments and insightful questions! We address all of your questions one-by-one below:

W1: We have reorganized the introductory sections of our paper to address this issue. In particular, we now have an explicit section on our Problem Setting which describes the specific communication model we have in mind. To answer the questions specifically, we do not consider any communication or coordination between clients: at each time step, they merely compute private functions of their local data and send them to the central server for post-processing into noisy gain vectors.

W2: This is a really interesting question! Currently, our privacy analysis treats all of our algorithms as post-processings of Gaussian mechanisms, which don’t satisfy pure DP for any value of epsilon. So, if we wanted to provide pure DP guarantees, we would need to either change our algorithms or change something about our analysis.

On the algorithmic side, the most obvious extension would be to replace our Gaussian noise with Laplacian. This would work reasonably well for RW-FTPL - the sum of independent Laplacians should converge to be approximately Gaussian fairly quickly, and so we would likely end up with a similar overall regret bound plus some error term. Conceptually, we could also imagine deriving a variant of RW-AdaBatch for this setting, but the proof techniques would look different (in particular, the analogue to continuous Brownian motion would no longer hold), and we expect that the overall level of privacy amplification would be weaker because Laplacian tails are heavier than Gaussian tails, necessitating more conservative batch sizes. Finally, we are skeptical that this approach would work at all for RW-Meta - our design and evaluation of that algorithm relies very heavily on the particular algebraic properties of Gaussians in a way that would be difficult to extend to any non-stable distribution.

On the analysis side, the most plausible approach to our eyes would be to set aside local DP and focus on satisfying pure DP in the central setting. For a fixed time horizon, the set of possible outputs our algorithm can produce is finite (if exponentially large), and so it should certainly be true that our outputs satisfy pure DP for some finite epsilon. It’s less clear whether they could be made to satisfy pure DP with a small epsilon, however, or whether those guarantees could hold over arbitrary time horizons: there’s been some interesting recent work in this vein on the pure DP properties of Gaussian Noisy Max [1], but directly translating those results to our setting and using composition theorems would lead to an extremely high privacy cost very quickly. Getting a stronger guarantee would almost certainly require analyzing the entire sequence of outputs as a unit instead of reasoning timestep-by-timestep as we do currently.

Overall, our feeling is that it is probably easiest to provide pure DP guarantees when designing algorithms in the FTRL regime, as in both recent papers by Asi et al. In the context of FTPL, there are a lot of reasons to want to use Gaussians, including stronger utility guarantees [2; Theorem 3.15], and that naturally pushes us towards approximate DP.

[1] Lebensold, Jonathan, Doina Precup, and Borja Balle. "On the Privacy of Selection Mechanisms with Gaussian Noise." International Conference on Artificial Intelligence and Statistics. PMLR, 2024.

[2] Lee, Chansoo. Analysis of perturbation techniques in online learning. Diss. 2018.

W3: While Asi et al. (2023b) do prove lower bounds that are specific to pure DP, Theorem 9 and Theorem 11 of that paper show that approximate DP algorithms can also be forced to suffer linear regret by adaptive adversaries in some circumstances. We are open to being corrected on this, but at the moment we believe that the statement accurately reflects the results in that paper.

Thank you for your many helpful and constructive suggestions! We largely agree with all issues raised and have done our best to address them in the revision. We respond point-by-point below:

W1: This is a very valid criticism, and we appreciate being pushed to be more exact! We have substantially revised several aspects of our presentation to make it more clear how our algorithms fit into our target setting. In particular, we have added a new Problem Setting section that addresses these questions directly and better connects our presentation of background material with our particular setting. As part of this, we also formally state the model of communication we consider and have incorporated this model into the presentation of our algorithms. We hope that these changes are able to address all of the issues you raise.

Q1: We agree that these details were not explicit enough in our original paper. We have revised our presentation of differential privacy to be more specific to our particular setting. In particular, we now define adjacent datasets and DP explicitly in terms of the local statistics used to compute gain functions in our setting. We have also added an explicit statement in our evaluation section describing the precise adjacency definition we use for Covid data (i.e. two datasets are adjacent at a given time step if they differ only in whether an individual went to the hospital or in the hospital that individual went to).

Q2: We have rewritten the relevant section of our contributions to make it more clear that the amplified privacy guarantees of RW-AdaBatch refer specifically to its outputs. More importantly, we have significantly rewritten and expanded the preamble to the privacy analysis of RW-AdaBatch to draw a more explicit connection between our work and the established literature on privacy amplification by shuffling, which studies the circumstances in which local DP algorithms can satisfy central DP with stronger privacy parameters. Our revisions should hopefully clarify that this is the specific form of privacy amplification we are interested in.

Q3: We politely disagree with the characterization that RW-AdaBatch assumes a trusted central party. Although our analysis is focused on its amplified central-DP guarantee, the algorithm satisfies local DP with exactly the same parameters as RW-FTPL, and therefore does not require any additional trust assumptions.

That said, reviewer qnzh has also commented on the lack of quantitative comparison with prior work in the central model, and so we have performed some additional experiments comparing our algorithms with the FTPL algorithm of Agarwal and Singh 2017. We did consider evaluating against Asi et al. 2023, but their algorithm is heavily tuned for high dimensional data and large time scales in a way that would make fair comparison very challenging. In contrast, Agarwal and Singh represent the current state of the art in the sorts of low-dimensional settings we target, and have the added benefit of naturally satisfying Gaussian DP.

Q4: We have done our best to incorporate this suggestions as described above.

Q5: Thank you for letting us know! We have updated the reference accordingly.

Q6: We are not making any specific assumption here. The gain of learner $i$ is defined to be $\langle x_{t,i}, g_t \rangle$, and so the fact that $\langle x_{t,i}, \tilde{g}_t \rangle$ is an unbiased estimate follows from the fact that $\tilde{g}$ follows a multivariate normal distribution with mean $g_t$.

Thank you for your insightful questions and positive comments about the strengths of our paper! We address the weaknesses and questions you list one-by-one below:

W1: Beyond the medical forecasting task that we consider in our evaluation, we also believe our methods could be of interest for forecasting population movement and regional energy usage. Local differential privacy is attractive in these settings because individual level records can be highly revealing, while prediction with expert advice is a natural model for any forecasting task because it’s relatively easy to observe aggregate behavior after the fact. We have altered the description of our contributions in section 1.1 to highlight these other domains.

Separately, because prediction with expert advice is one of the most fundamental problems in online learning, we believe it is a natural starting point to explore new methods or proof techniques for online learning generally. We have included some discussion along these lines in Appendix A.1.

W2: We have added a section on computational complexity for both RW-AdaBatch and RW-Meta. While both algorithms involve non-trivial computations as subroutines, these computations don’t necessarily become more complex as the dataset grows in size. For instance, RW-AdaBatch only ever needs to find a root of a one-dimensional function regardless of how large $n$ and $T$ are. In fact, it should generally become computationally cheaper as $T$ increases because batch sizes generally increase over time, and no meaningful computation has to be performed in the middle of a batch.

Meanwhile, RW-Meta only needs to find the eigenvector corresponding to the maximum eigenvalue rather than the whole eigensystem, which is substantially cheaper. Asymptotically speaking, the biggest challenge for scalability is that RW-Meta requires $O(m^2 + mn)$ memory and computation simply to compute and store the matrices it uses. However, the fact that the regret of RW-Meta with respect to the best learner is $O(\sqrt{m})$ in the worst case is already a good reason to avoid taking $m$ too large. In our own evaluation, we found that by far the biggest computational bottleneck came from constantly re-fitting our rolling regression models, while the metalearning itself took only a few milliseconds per iteration.

W3: This is a very good question, and we have revised our presentation of our utility bounds for RW-FTPL and RW-Meta to make this more explicit in the paper itself. In both cases, the regret bounds are expressed in terms of the noise scale $\eta$ which implicitly depends on both our privacy parameter $\mu$ and the sensitivity $\Delta$. In some contexts (including our Covid evaluation), $\Delta$ is a fixed constant that doesn’t depend on $n$, and so we do in fact recover regret bounds that are within a multiplicative factor (based on $\mu$) of the non-private baseline. In the worst case, however, $\Delta$ can be as large as $\sqrt{n}$ and we get a regret bound of $O(\sqrt{Tn\log n})$. This matches known lower bounds on expected $\ell_\infty$ error for mean estimation under local DP[1; Proposition 4].

Q1: There may be some misunderstanding here: the batch size $B$ isn’t directly set as a hyperparameter. During runtime, RW-AdaBatch selects batch sizes dynamically based on the current gap between the top 2 experts as well as our maximum tolerance for errors, which we set through the hyperparameter $\alpha$. This computation gets repeated every time a batch ends and a new batch size must be chosen. We have added a new section to the appendix (A.3) presenting this in more explicit detail.

In practice, we find that the algorithm is not particularly sensitive to the exact choice of $\alpha$ - with $\alpha=0.01$, we have never witnessed RW-AdaBatch suffer higher regret than RW-FTPL, and setting $\alpha$ as high as 1 gives only very small improvements in privacy. We would therefore recommend just using $\alpha=0.01$ in most applications without any tuning.

At the suggestion of reviewer 2XWn, we have added highlighting to draw attention to our changes. This appears to have slightly perturbed the vertical spacing of the text, forcing Table 1 to be placed on page 11. The current text can fit in 10 pages without the highlighting, as demonstrated by the previous version, and so we hope this minor violation of the style guide during the rebuttal process won't be an issue.