Private Online Learning against an Adaptive Adversary: Realizable and Agnostic Settings

We thank the reviewer for the constructive comments, and our detailed responses are listed below.

In many online learning scenarios, the time horizon $T$ is not known in advance. I noticed that several parameters—such as the threshold in Algorithm 2 and the number of experts in Section 4.2—depend explicitly on $T$. Is it possible to remove this dependency?

Yes, this dependency can be removed by the classical "doubling trick" -- splitting the input sequence into buckets of sizes $1,2,4,8,\cdots$ and running our algorithm on each bucket separately (with parameter $T=1,2,4,8,\cdots$). It can be shown that the resulting algorithm have the same regret bound while not requiring knowledge of the entire time horizon in advance [Cesa-Bianchi and Lugosi, 2006].

We will include the above comment in the revision.

Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge University Press, 2006.

We thank the reviewer for the constructive comments and provide our detailed responses below.

Can you justify the necessity of including the condition over the dual Littlestone dimension in Theorem 4.2/ Corollary 4.3? This condition (if I am not mistaken) is required also for the results in "Sample-efficient proper PAC learning with approximate differential privacy" and I would like to have an intuitive explanation.

Our derived bounds in Theorem 4.2/ Corollary 4.3 depend on the dual Littlestone dimension because our algorithm is based on sanitization. As proved in "Sample-efficient proper PAC learning with approximate differential privacy" (their Theorem 6.7), the sample complexity of sanitization grows at least polynomially in the dual Littlestone dimension. Below we provide an intuitive explanation for a special case of their result.

Consider a domain $X=\\{0,1\\}^D$ and a class $H=\\{h_1,\dots,h_D\\}$ where $h_i(x) = x_i$. The Littlestone dimension of $H$ is $\log D$ and the dual Littlestone dimension is $D$. For this class, sanitizing a dataset is equivalent to privately estimating its $D$-dimensional mean, which requires $\Omega(\sqrt{D})$ samples (Steinke, T., & Ullman, J. (2015) ).

Steinke, T., & Ullman, J. (2015). Between Pure and Approximate Differential Privacy. ArXiv, abs/1501.06095. Presented at the First Workshop on the Theory and Practice of Differential Privacy (TPDP ‘15), London, UK, April 2015.

Do you believe it is possible to eliminate the $2^{2^{O(d)}}$ factor in the Littlestone dimension? Just, your opinion about it.

Yes, we believe that this factor can be improved to polynomial in $d$, as in "Sample-efficient proper PAC learning with approximate differential privacy" for PAC learning.

Negative points: As mentioned, the paper is dense. Without a knowledge of many results in the literature, it becomes a bit hard to follow some passages, even if the authors do their best to sum everything up. Also, I noticed that the main result cited at the beginning is not referenced again in Section 3 and that can be confusing.

Minor comments: Typo in algorithm 2: failuare -> failure. Typo in Theorem 2.6 Pirvate -> Private.

Thank you for pointing out these issues. We will fix the typos and reference our main result in Section 3 in the revision.

We thank the reviewer for the constructive comments and provide our detailed responses below.

How close to proper can the algorithm handling the realizable case be made? E.g., by replacing SOA hypotheses with Hanneke-Livni-Moran's construction?

By replacing the SOA with Hanneke-Livni-Moran's construction, we can obtain a learner whose output is always a majority vote of $O(d_V^\star)$ hypotheses from the given class, where $d_V^\star$ is the dual VC dimension.

More generally, the output space of our algorithm is exactly the output space of the deterministic online learner it invokes. Thus, how close to proper the algorithm can be made depends on how close to proper a deterministic online learner can be made. For classes that can be properly learned by a deterministic online learner (e.g., thresholds over a finite domain), the resulting private online learner is also proper. However, there are some classes that cannot be properly learned by a deterministic online learner (e.g., point functions). For these classes, our algorithm (Algorithm 2) is improper.

Additionally, our first algorithm for the agnostic setting (Algorithm 3) can also yield a proper learner. Though it works for all Littlestone classes, it incurs a large regret ($T^{3/4}$). We believe this can be improved and leave it as future work.

We will include the above discussion in the revision.

I understand you're space-constrained, but seeing as Section 4.2 reflects most of the paper's algorithmic novelty, I would have liked to have seen a more detailed description of that algorithm in the main body of the paper in place of the algorithm described in Section 3.

Thank you for your suggestion. We will allocate more space for Section 4.2 and provide a detailed description of our agnostic learner in the revision to better highlight our algorithmic contributions.

We thank the reviewer for the constructive comments and provide our detailed responses below.

The authors would benefit from reallocating space from the extensive Preliminaries section to provide a more detailed explanation of Algorithm 2 and its different components.

Thank you for your suggestion, we will elaborate on the details of Algorithm 2 to better explain it in Section 3 in the revision.

don’t you have to re-initialize the SOA algorithm after every lazy update?

We do not reinitialize the SOA. During the update, every $S_{i}^{s+1}$ is obtained by appending an example to some $S_{j}^s$ (as seen in line 7 of Algorithm 1). Hence, $SOA(S_{i}^{s+1})$ can be seen as feeding a new example to $SOA(S_{j}^s)$ rather than reinitializing it.

the shared randomness across lazy updates could introduce correlations between historical predictions and current outputs, potentially creating exploitable patterns for adversaries.

We believe this sentence and its subsequent description in this review is a misunderstanding, possibly caused by our (overly) concise writing due to the page limit. We present more technical details in Appendix B. We are confident that there is no mistake in our derivation.

While correlations exist between historical predictions and current outputs, they do not compromise the correctness of our algorithm.

The correctness of our algorithm is based solely on the fact that a constant fraction of the sequences ($S_1^s,\dots,S_{N_s}^s$) remain consistent with the input (Lemma B.1). We prove this through concentration bounds only over the permutation $\pi$ and label $\bar{y}_i$ in the update (Algorithm 1). Since they are generated during the update and are independent of any prior randomness, the correctness can be directly established.

We emphasize that shared randomness is crucial for achieving a small mistake bound -- without it, the only way to ensure privacy is by advanced composition (as in the work of Golowich and Livni (2021) ), which results in a $\sqrt{T}$ mistake bound. The primary challenge in private online learning is how to effectively leverage shared randomness to mitigate privacy cost while achieving a small mistake bound.

the privacy analysis extends beyond straightforward composition arguments and involves more nuanced considerations.

The privacy analysis remains straightforward considering the following three facts:

1. the AboveThreshold mechanism is private against an adaptive adversary.
2. the PrivateHistogram is private and non-sequential (thus also private against an adaptive adversary).
3. the composition theorem holds for an adaptive adversary.

Consequently, the entire algorithm is private against an adaptive adversary. Note that the randomness involved in the update is only for utility purpose and does not affect the privacy analysis.

We thank the reviewer for the constructive comments and provide our detailed responses below.

they give a summary of the online learning of Golowich and Livni and explain why it is insufficient for achieving the desired $O(\log T)$ mistake bounds, but I don’t know how helpful this summary would be for those who are not already familiar with the algorithm.

We include a description of Golowich and Livni's algorithm because our work builds upon their framework (specifically, constructing tournament examples). A detailed explanation will help clarify how and why our algorithm works against an adaptive adversary. We will revise the presentation to enhance accessibility for non-experts.

It would be good to have a theorem statement in Section 3 with the parameters necessary for privacy and the stated mistake bounds specified.

Thank you for your suggestion. We will include a formal theorem stating the privacy/utility guarantee of our algorithm and the choice of parameter $N_0$.

Some minor notes/typos:

Thank you for identifying the typos. We will correct them in the revision.