Private Online Learning via Lazy Algorithms

Summary

This paper studies private online prediction from experts (OPE) and online convex optimization (OCO) problems and proposes a general transformation that converts lazy (non-private) algorithms into private algorithms. By applying it to existing lazy algorithms, they obtain improved regret bounds for both problems. A lower bound for lazy algorithms is also provided, suggesting that new techniques other than lazy algorithms are needed if one wants a better regret.

Strengths

1. The proposed method is a general transformation, namely, it applies to any algorithms that satisfy certain properties. 2. The results obtained outperform previous bounds, especially in the high privacy regime ($\varepsilon \ll 1$). 3. A matching lower bound is provided.

Weaknesses

1. The improvement made in this paper may not be very significant. It only improves the dependency on $\varepsilon$, while in many scenarios $\varepsilon$ is treated as a constant. 2. The lower bound may not be essentially matched -- Theorem 4.2 requires the algorithm to be $\varepsilon^2$-CDP instead of $(\varepsilon,\delta)$-DP. It does not mean that every $(\varepsilon,\delta)$-DP algorithm should have that lower bound.

Questions

1. The paper assumes an oblivious adversary. Can the results be extended to the adaptive adversarial setting? 2. It looks like Condition 4.1 is not limited to algorithms with a small number of switches. It only requires that once the algorithm resamples, the resampling distribution depends only on past loss functions and not on internal randomness. Is my understanding correct?

Rating

7

Confidence

4

Soundness

3

Presentation

4

Contribution

3

Limitations

Irrelevant.

Summary

This paper investigates private online learning, focusing on online prediction from experts (OPE) and online convex optimization (OCO). The authors propose a new transformation that translates lazy, low-switching online learning algorithms into private algorithms. Based on this transformation, their resulting algorithms attain regret bounds that significantly improve over prior art in the high privacy regime. Furthermore, they complement their results with a lower bound for DP-OPE, showing that these rates are optimal for a natural family of low-switching private algorithms.

Strengths

* The improvements in results for DP-OPE and DP-OCO are highly valuable. * The research motivation of this work is clear, and the proposed transformation (L2P) is a very solid contribution to DP online learning.

Weaknesses

* The transformation in this work is based on low-switching online algorithms, and is only applicable to oblivious adversaries. In contrast, previous DP-OCO algorithms [ST13, AS17, KMS+21] can adapt to non-oblivious setting. * The theoretical innovation in this paper is limited, as it largely follows previous work [AFKT23b].

Questions

* In footnote 2, the authors state that their algorithms will satisfy a stronger notion of differential privacy against adaptive adversaries. However, I believe that for non-oblivious adversaries, the proposed DP online algorithms in this work cannot provide regret guarantees. Is this correct? If so, I would like to understand why the low-switching private algorithms cannot handle non-oblivious adversaries, whereas previous work using binary tree techniques [ST13, AS17, KMS+21] can. * From Theorem 3.2, it is evident that $\epsilon$ of L2P increases over time, meaning that its privacy weakens progressively. Could this be a concern for the proposed DP algorithm? * The authors established a lower bound for low-switching private online algorithms based on **CDP** analysis, whereas the upper bound provided in this paper is based on **DP** analysis, i.e, Theorem 3.2 and 3.9. Could you clarify the implications of this difference?

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

See above

Summary

The paper studies the differentially private (DP) variants of the classical online prediction form experts problem (OPE) and online convex optimization (OCO) problem. The main contribution is a (black-box) approach to transform lazy (i.e. slow-varying) online learning algorithms into private algorithms. The paper shows that the transformation only incurs a small additional regret as compared to the regret for the classical OPE/OCO regret. In particular, for the DP-OPE and DP-OCO, the proposed algorithms improve the O(1/eps) regret in previous works to O(1/eps^{2/3}). In addition, a matching regret lower bound is provided for the family of low-switching private algorithms for the DP-OPE problem.

Strengths

The paper is well-written with all claims supported by proofs. Compared to previous works, the L2P algorithm proposed uses a new correlated sampling strategy to avoid accumulation of privacy cost, and the paper improves the regret of lazy algorithms due to batching. In addition, the paper provides a lower bound for the DP-OPE problem, showing that limited switching is not enough to obtain faster rate, suggesting the need for other techniques.

Weaknesses

The lower bound is only valid for the family of slow-varying algorithms, thus the algorithms proposed might not be optimal.

Questions

The paper is relatively dense, with many definitions related to differential privacy (section 2), which might be unfamiliar for people who have little knowledge about differential privacy before. I’m wondering if all those definitions are necessary for the main part of the paper (maybe some can be moved to the appendix)?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Yes the paper has discussed the limitations and provides improvement in the appendix.

Summary

This paper proposes a new mechanism that converts lazy online learning algorithms into private algorithms. Unlike previous private online algorithms that use individualized privatized methods, the paper's new mechanism is a black box private algorithm that can be applied to many popular non-private methods such as the lazy shrinking dartboard algorithm or the regularized multiplicative weights algorithms.

Strengths

- The problem is well-motivated. Even though previous private algorithms have good theoretical guarantees, their privatized mechanism is usually tailor-made to solve a specific problem, which limits their applicability. The new black box algorithm makes converting a non-private to a private one simple and seamless. - The private term has improved dependence in the $\epsilon$ term which could be valuable in the high privacy regime (where $\epsilon \ll 1$). - The authors also provide lower bounds that match their upper bound. - The paper is well-written overall.

Weaknesses

- I'm not sure if I agree with the claim that the new bound is an improvement over the previous bound. Obviously, the high privacy regime is very important, and as the authors have mentioned, this would allow for the composition of more instances. However, as far as I know, a lot of practical application of DP algorithm uses $\epsilon \approx O(1)$ so the new bound could be worse than previous results. - It would be nice if there are some proof of concept experiments to compare the new mechanism with the algorithms in previous works.

Questions

- Can the author provide some intuition on why we would want to use concentrated DP to prove the lower bound? How does concentrated DP make it easier for us to construct the lower bound? - What are some non-lazy algorithms that satisfy Assumption 3.1? What would the regret bound look like for these non-lazy algorithms. - I'm a bit confused about the setting of $\epsilon$ in Theorem 3.2. To get the optimal regret bound, we need to set $\epsilon$ using the provided formula which I think is roughly $O(1)$. Doesn't that defeat the point of the proposed framework where we only see improvement when $\epsilon <<1$.

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

N/A