Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: Under the assumption of a smooth loss function, this paper investigates a new online-to-batch conversion method for private stochastic optimization.
strengths_and_weaknesses: This paper offers a fresh look at stochastic optimization with DP guarantees. However, it appears to have been rushed and does not demonstrate well. Even though the smoothness assumption is a limitation, experiments for the smooth loss case and comparison with other existing methods are preferred to provide a sense of the utility advantage claimed in this paper.
questions: Is the cardinality of I_t an r.v. in Line 13 of Algorithm 1? If not, can we simplify the part involved I_t? If it is a r.v., can we use the randomness to amplify privacy?
limitations: The writing could be improved to make it more reader-friendly, and experiments are encouraged..
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper proposes a novel online-to-batch conversion algorithm with theoretical guarantees, which aims to achieve optimal convergence rate of expected risk under differential privacy constraints. Relationships between regret bound and expected risk are also provided under different conditions of loss function.
strengths_and_weaknesses: Strengths:

1.	This work is well-motivated with theoretical analyses. 

2.	Online-to-batch conversion technology is an important topic in online learning, and differentially private is also important in streaming data.

3.	Regret bound and expected risk are analyzed under different conditions of loss function.

Weaknesses:

1.	Some efforts have been made to the topic of differentially private online learning (DPOL) in [Jain et al., 2012]. The comparison with DPOL is missing.

2.	Lack of analysis of computational complexity.

3.	The paper lacks mostly discussion and insights for the theoretical results. 

4.	This paper lacks empirical analyses, which limits the reproducibility of the proposed algorithms.

[Jain et al., 2012] Differentially private online learning, COLT 2012.

questions: What is the relationship between the proposed algorithm and existing differentially private online learning algorithms? 
limitations: My major concern is about the reproducibility of the proposed algorithm. This paper proposes a novel online-to-batch algorithm with theoretical guarantees rather than only provides theoretical analyses for existing learning algorithms. Thus, empirical analyses are essential for demonstrating the effectiveness and efficiency of the novel algorithm with differential privacy constraints. Besides, some important related works about differentially private online learning are missing.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: Online to batch conversions are a classical reduction from adversarial online learning to stochastic optimization. This work introduces the use of such reductions in the context of Differentially Private Stochastic Convex Optimization (DP-SCO). This extension is nontrivial, as it is known that in this context classical online to batch leads to suboptimal rates. Therefore, in this work a more careful weighted regret scheme (known as anytime online to batch conversions, Cutkosky 2019) is used. This method is used in conjunction with a tree aggregation DP mechanism (Dwork et al. 2010), that allows for optimal noise addition of partial sums; and with a recursive stochastic gradient estimator, which has been proved useful in DP-SCO (Asi et al. 2021, Bassily et al. 2021). It is interesting that the technique is quite general, and it is applicable to settings beyond $\ell_2$ DP-SCO, which by now is well understood.  The work includes extensions to strongly convex losses and rates for which (the non-private $O(1/\sqrt{n})$ term) adapts to the level of noise. 

* Asi, Feldman, Koren, Talwar. Private stochastic convex optimization: Optimal rates in l1 geometry (ICML'21) https://arxiv.org/ abs/2103.01516.
* Bassily, Guzman, Nandi. Non-Euclidean Differentially Private Stochastic Optimization (COLT'21) https://arxiv.org/pdf/2103.01278.pdf
* Cutkosky. Anytime online-to-batch, optimism and acceleration (ICML'19) https://arxiv.org/pdf/1903.00974.pdf
* Dwork, Naor Pitassi, Rothblum. Differential Privacy under Continual Observation (STOC'10)

strengths_and_weaknesses: Strengths:

1. The unifying perspective on DP-SCO, capable to recover optimal rates without specialized arguments, or reductions between convex and strongly convex losses through regularization.
2. The perspective of online to batch conversions provides a rather straightforward extension to non-Euclidean norms, for which optimal methods are still scarce (Bassily et al. 2021).
3. Adaptivity to the noise level. All kinds of adaptivity in differential privacy are challenging, and not well understood, so this result in itself is significant.
4. The paper is fairly well written, and the proofs and analyses are not complicated and principled.

Weaknesses:

1. I think this unifying perspective becomes more interesting in geometries which are not $\ell_2$. More exploration of the consequences of the results of the paper to these settings would have been an interesting addition.
2. Aside from the noise adaptive rates and the parameter free algorithm, the rates derived in the paper are not new (namely, optimal rates have already been established). I don't think this is a major problem though, mostly because making these methods more broadly applicable is interesting and necessary to better understand DP-SCO.
questions: 1. Assumption 1, page 2. It seems that the strong convexity inequality is incorrectly written. Shouldn't it be $\|y\|^2\geq \|x\|^2+\langle g,y-x\rangle+\frac{\lambda}{2}\|y-x\|^2$? It should also be said that this function is strongly convex with respect to $\|\cdot\|$.
2. Algorithm 1, page 4. The subroutine NOISE is somewhat confusing, and I expect that any reader unfamiliar with the tree aggregation mechanism will have difficulties following it. What is the binary expression of $t$? do you mean ``binary expansion'', and then does this mean the bit encoding? I think a brief description of tree aggregation with references can go a long way. As well as adding a short lemma that elaborates on the connections between the binary encoding, $s_t$, $I_t$, $S_t$, etc. (e.g., that $S_t$'s partition $[t]$).
3. Equation (3). It is unclear to me why you use triangle inequality and Holder here. I thought the point is that these are zero mean conditional random variables (in fact, in the previous page this is exactly what is done in the last paragraph). I am not saying that dependencies on the norms of these vectors would not affect the final rates (because they do), but upper bounding in this way here is misleading to what is ultimately done in the analysis.
4. Main Result, page 5 (and other places). I understand it is possible to choose different values of $k$ for the averaging, but it is never thoroughly discussed why would one want this level of generality. A couple of results use particular choices of $k$, but it is never discussed why this choice matters.
5. Theorem 6, page 6. What is the value of $k$ for this result? What is the importance of the $3/2$ exponent of $T$ in the average weighted regret?
6. Definition of sub-Gaussianity, Page 8. What is $R_i$ here? Reading this feels out of context.
7. Theorem 10, page 8. What is the importance of $k=3$ here?
8. Conclusion, Page 9. It is said that ``we cannot tolerate large $H$.'' This issue is never discussed in the paper, neither its nature or whether it seems inherent. I am afraid Theorem statements neither make this limitation clear. Please elaborate where it corresponds.
9. Line 391-392, Page 13. Please remove $\nabla$ in various terms where they shouldn't be (I believe it was meant to be ${
cal L}$, rather than $\nabla {\cal L}$).
10. Lemma 15, page 14. Say that $\|\cdot\|^2$ must be strongly convex ``with respect to $\|\cdot\|$''. And add the expectation sign to $\|\delta_t\|_{\ast}$ (o.w. it is not true). Also add the conditional expectation to $\mathbb{E}[\|X_i\|_{\ast}^2]$ in (iii), to be consistent with (ii).
11. Proof of Theorem 3. The quick preliminaries of the tree aggregation procedure should be converted into a short Lemma. That would make it easier to find for the interested reader (these notations and claims are used beyond this theorem).
12. Theorem 19, page 19. Is this result ever used?
13. Line 546, page 20. Use the expectation operator on $\|\delta_t\|_{\ast}$.
14. Could the authors elaborate on the comparison with a recent work on DP-SCO with streaming data: Han et al. 2022 (On Private Online Convex Optimization: Optimal Algorithms in lp-Geometry and High Dimensional Contextual Bandits, https://arxiv.org/pdf/2206.08111.pdf). Maybe the results of the current submission subsume some of these results?

limitations: There are two technical aspects of this work that are worth a more extensive discussion:

1. Are the new online to batch conversion results presented in this paper capable of addressing $\ell_1$-geometry (Asi et al. 2021, Bassily et al. 2021). This is an important question, since this is the only general case where we can avoid polynomial dependence on $d$ in the rates. This is not a direct corollary of what is currently done in the paper, as the stochastic Frank-Wolfe algorithms of the references above are not clearly applicable to the online setting.

2. The issue about the smoothness constant $H$ is currently lacking a more thorough discussion.
review_title: null

Meta-review: metareview: The paper made original contributions to DP learning of convex and smooth differentially private learning problem by connecting to the vast parameter-free online learning literature. One of the reviewers read the paper  with great details and carefully checked the correctness of the results. The AC also took a close look and find the results very nice. The reviewers and the AC further discussed the work and clarified some of the concerns raised, e.g., regarding computation; but the missing experiments make it hard to vouch for the practicality of the approach.  Based on the theoretical contribution alone, we believe the paper is above the bar and would happily recommend accept. 

The authors are encouraged to take into account the points below and consider adding benchmarking experiments.

---------------

Some additional feedback / comments out of the discussion:

1. For DP-SCO as the optimal rates are known to be achievable by a linear time algorithm (FKT'20). The proposed new algorithm thus does not improve over existing methods in either statistical or computational complexity.

2. If computation is not a concern, Noisy Gradient Descent with O(n^2) iterations (thus n^3 incremental gradient oracle calls) is known to provide an even stronger excess *empirical* risk bound that is optimal (without that additional log T in this paper). It also is very hard to beat in practice.

3. The main contribution of the proposed algorithm is then about new algorithmic techniques borrowed from adaptive online learning. This approach gives rise to the unified treatment of general convex and strongly convex problems and they discussed how it helps to tap into other more adaptive / more parameter-free online learners.

4.  Tree-aggregation for releasing gradient sequences by leveraging smoothness (and stability implied by the anytime online-to-batch reduction) is cute. I think technically this is the most interesting idea.

5. I think the paper contains enough good results to be considered as a purely theoretical work for acceptance. That said, I do think the algorithm has the potential to be practical. It is a pity that the authors did not try. Though with the several layers of reductions and the binary-tree approach, it won't surprise me if the proposed method is not competitive against methods such as NoisyGD or NoisySGD.

6. Another positive aspect about this paper is that it is polished and the writing is pretty good. I particularly liked how the authors accurately describe their contribution in the title / abstract by clearly highlighting the key assumption on the smoothness.



confidence: Certain
Decision: Accept