Tracking The Best Expert Privately

We thank the reviewer for their comments. We address the reviewer's concerns and questions below and hope that they will reevaluate their score accordingly.

No experimental results

We acknowledge the reviewer’s concern regarding the lack of experiments. However, our work is intentionally theoretical, aimed at understanding fundamental rates and limits of private learning from experts. Theoretical contributions often provide key insights that guide future empirical research. While experimental validation is certainly valuable, we believe that our results are meaningful in their own right and align with the norms of theoretical research in this area.

There is a lot of work on adversarial bandit in the literature. The author should pick a typical algorithm, such as Exp3 [1], to explain why it can or cannot be adapted to the current setting of dynamic regret with DP.

We note that our work focuses on the setting of experts where we have full-information rather than the setting of bandits. There are many papers that study our problem (dynamic experts under full-information feedback) in the non-private setting which we discuss in our related work section. We will add a discussion on the challenges in privatizing these existing algorithms. We briefly mention one challenge here with regards to the modified multiplicative weights algorithm of (Lu and Zhang (2019)). Their algorithm basically applies the same update as multiplicative weights and then projects to the clipped simplex. Unfortunately, this clipping operation is challenging for privacy as now we have to privatize each gradient separately instead of privatizing the sum of gradients via the binary tree mechanism. We will discuss this more carefully in the final version.

Lu, Shiyin, and Lijun Zhang. "Adaptive and efficient algorithms for tracking the best expert." arXiv preprint arXiv:1909.02187 (2019).

Motivation for dynamic regret

Dynamic regret is stronger notion than static regret that compares the performance of the algorithm to a sequence of changing experts (rather than a fixed expert). This is extremely important in scenarios where there is a distribution shift which results in a new optimal expert. For example, in recommendation systems, the user's preferences might change over time.

To highlight the importance of dynamic regret, lets consider the following example. Consider the setting of two experts, where the first $T/2$ losses are such that $\ell_t(1) = 0$ and $\ell_t(2)=1$, and for the last $T/2$ losses we have $\ell_t(1) = 1$ and $\ell_t(2) = 0$. For this sequence of losses, a simple algorithm that gets $0$ static regret is one that plays expert $1$ for all rounds. However, the dynamic regret of this algorithm is $T/2$ because the optimal strategy for dynamic regret would play expert $1$ for $T/2$ rounds before switching to expert $2$. For this sequence of losses, one can generalize this argument to the Multiplicative Weights (MW) algorithm, which would obtain sublinear static regret, but linear dynamic regret since MW would wait roughly $T/2 - \sqrt{T}$ rounds before switching to expert $2$. This shows a scenario where an algorithm aimed at static regret suffers suboptimal dynamic regret.

Definition of dynamic regret

As for the reviewer's example and question about the definition, we first clarify that the definition of expected regret in Lines 145 to 152 is the definition of static regret which does not involve any switching. The definition for dynamic regret is provided in lines 175-181 and the constraint on the number of switches $S$ is made explicit in the definition of regret here. Note that our definition of dynamic regret (lines 175 - 181) crucially relies on limiting the number of changes in the set of best experts we compare to ($S$ upper bounds this). Indeed, we mention in line 161 in the paper that "To make the problem tractable, we constrain the comparison sequence of experts to have at most $S$ changes". This is crucial as otherwise we end up having linear regret, which is exactly what is happening in the reviewer's example.

When $S=0$, dynamic regret becomes equivalent to static regret since the sequence of comparison experts must consist of a single expert. When $S=1$, we allow to compare our algorithm to sequences of experts than change at most once, e.g. as in the example above, expert $1$ for the first $T/2$ rounds and expert $2$ for the last $T/2$ rounds. The larger $S$ is, the stronger is the notion of the regret. However, as $S$ becomes too large, it becomes hard to provide meaningful guarantees on the regret.

We will add more clarification and intuitions regarding the parameter $S$ and its importance for the dynamic setting in the introduction.

We thank the reviewer for their positive feedback and finding our techniques to be broad and interesting. We address the reviewer's concerns and questions below and hope that they will reevaluate their score accordingly.

Computational inefficiency

This is a good question and an important direction of future work. First, we note that despite its inefficiency, this result is important on its own because it is the first known upper bound for oblivious adversaries and it establishes a separation in the achievable rates between oblivious and adaptive adversaries. Unfortunately, our current attempts at designing efficiency private algorithms against oblivious adversaries have been unsuccessful, as it is not clear how to privatize existing efficient non-private algorithms for dynamic regret. Perhaps central to the difficulty is the tension between lazy updating and obtaining small dynamic regret. Existing techniques for obtaining private online learning algorithms under static regret rely on privatizing existing (non-private) lazy algorithms that do not switch their played experts too often [1, 2]. Unfortunately, it is reasonable that such lazy algorithms cannot obtain good dynamic regret, as switching which expert is played is crucial to ``tracking" the best expert. We will make sure to add a discussion of this in the camera-ready version.

That said, we do note that our algorithm against adaptive adversaries is efficient and also gives guarantees in the oblivious settings.

[1] Asi, Hilal, et al. "Private Online Learning via Lazy Algorithms." Advances in Neural Information Processing Systems 37 (2024): 112158-112183.

[2] Asi, Hilal, et al. "Private online prediction from experts: Separations and faster rates." The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023.

Tightness of the result for oblivious and adaptive adversary

This is an important point of our work and we will clarify it in our final version. First, note that our bounds for oblivious adversaries are not tight as can be seen from Table 1 in the paper. As for adaptive adversaries, the bounds are tight in the following sense. Assume we ask the question of what is the best privacy (smallest $\varepsilon$) we can guarantee while being able to learn anything useful (e.g. obtain sublinear regret)? Our upper and lower bounds provide tight answer for this question: indeed, the lower bound implies that sublinear regret requires $\varepsilon = \Omega(\sqrt{S/T})$ and our upper bound (theorem 5.2) shows that the dynamic regret is sublinear whenever $\varepsilon = \Omega(\sqrt{S/T})$. This shows that our setting has $\varepsilon \ge \sqrt{S/T}$ as a fundamental threshold for learning.

Comments about lack of clarity and typos

We will fix these comments in the final version. More specifically, we will add the missing $\log(T)$ factor in theorem 3.1 and rewrite Lemma A.3 more clearly. We will also revise Section 2 by removing comments regarding ``abuse of notation" and be more explicit with our definitions.

$\log(N/S) \gg \log(N)$"

The reviewer is right. When we wrote that $S \ll N$, we meant that $S$ is actually polynomial smaller than $N$ in the sense that $S = O(N^{1-\delta})$. We will clarify this in the final version.

(Q1) Extension of the lower bound of (Asi et al., 2024)

The family or algorithms used in the lower bound proof of (Asi et al. 2024) are those that are lazy, in the sense that they do not switch their played expert frequently. While this is suitable for static regret, for dynamic regret, we do want to switch experts since we are competing with a sequence of switching experts. That said, it could be extended, but it would likely not be as meaningful.

(Q2) Small $N$ regime

Our focus in this work was on the high-dimensional regime where $N$ is large. However, we agree with the reviewer and believe the small $N$ regime is also of interest. Our algorithms work in that setting but are probably sub-optimal. Similarly to the static regret setting, we believe that versions on the binary tree mechanism are going to be optimal for small $N$. These algorithms usually have a worse dependence on $N$ ($N$ instead of $\log N$) but a much better dependence on $T$. We leave this question for future research.

(Q3) what is $j_t$ in Lemma A.2?

Lemma A.2 proves certain properties about Algorithm 1 and uses notation from that algorithm ($j_t$ was defined in Algorithm 1). We will clarify this in the paper.

We thank the reviewer for their comments. We address the reviewer's concerns and questions below and hope that they will reevaluate their score accordingly.

Authors may give details of the proof for differential privacy of algorithms...

We will make sure to include theorems about basic privacy mechanisms and their privacy/utility guarantees in the camera-ready version. That said, we do prove the privacy guarantees for all our algorithms. For example, on lines 332-334 in the right column, we provide the proof of the privacy guarantee in Theorem 4.1. Similar privacy proofs for the other Theorems can be found in the Appendix.

Authors may provide experiments

This paper is theoretical in nature as we aim at rigorously understanding fundamental limits in the context of dynamic regret minimization. While empirical validation can be valuable, our contributions stand independently as theoretical results that advance understanding in this area. Future work may explore experimental verification, but our primary goal here is to establish a solid theoretical foundation.

(Q1) Can these results be extended to the bandit setting?

Yes, we do think that some of these results can be extended to the bandit setting, especially the results for stochastic and adaptive adversaries. With regards to oblivious adversaries, more care needs to be taken as one often uses unbiased estimates of the true loss under bandit feedback. This can cause issues in the privacy analysis as the sensitivity of the unbiased estimator can be large.

(Q2) Is this a typo...

Yes, we thank the reviewer for catching this typo. We will make sure to fix it in the camera-ready version.

We thank the reviewer for their comments. We address their concerns below and hope they will reevaluate their score accordingly.

Is it possible to design an efficient algorithm that attains same-order regret bounds in this setting?

This is a good question and an important direction of future work. First, we note that despite its inefficiency, this result is important on its own because it is the first known upper bound for oblivious adversaries and it establishes a separation in the achievable rates between oblivious and adaptive adversaries. Unfortunately, our current attempts at designing efficient private algorithms against oblivious adversaries have been unsuccessful, as it is not clear how to privatize existing efficient non-private algorithms for dynamic regret. Perhaps central to the difficulty is the tension between lazy updating and obtaining small dynamic regret. Existing techniques for obtaining private online learning algorithms under static regret rely on privatizing existing (non-private) lazy algorithms that do not switch their played experts too often [1, 2]. Unfortunately, it is reasonable that such lazy algorithms cannot obtain good dynamic regret, as switching which expert is played is crucial to ``tracking" the best expert. We will make sure to add a discussion of this in the camera-ready version.

That said, we do note that our algorithm against adaptive adversaries is efficient and also gives guarantees in the oblivious settings.

[1] Asi, Hilal, et al. "Private Online Learning via Lazy Algorithms." Advances in Neural Information Processing Systems 37 (2024): 112158-112183.

[2] Asi, Hilal, et al. "Private online prediction from experts: Separations and faster rates." The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023.