Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper is in the continuation of recent line of work that studies private algorithms when it has access to some public data. They also achieve a dimension independent bound as in some of the previous work. The idea of the paper is very simple: they use public data as the mirror map in the private mirror descent algorithm. 
main_review: This is a beautiful paper! It is well written, easy to follow, covers the literature very well. The results are nice and for me and the approach very natural. It is an easy accept. 

I have few comments about the paper though. Since the paper works in the public-private data setting, it would be nice to know (even theoretically) the comparison between how much public data is used by previous work and we have access to equivalent data, what is the performance of the current submission. Likewise, if we have a given utility to aim for, what is the difference between the number of public data samples in the current submission vs previous works. This would put the work in a very precise light as to whether it is improving the state-of-the-art or not.  

The paper mentions in the appendix that they compare SoTA with Asi et al. and they made a best effort to match their experiment set up. Asi et al. is a published work in ICML 2021 and I am surprised by the claim of the authors that the code is not publicly available -- given that ICML requires code submission in the supplementary material. If it is indeed so, I would suggest the authors to reach out to the authors of Asi et al. to get their code because the hyperparameters used in this submission can be very different from what Asi et al. did and hence the claim may or may not be true. 

One question I have to the authors is also with regards to some other works that came out in different geometry (Bassily et al. (COLT 21), Asi, Feldman, Koren, and Talwar ICML 21 (AFKT to differentiate from Asi et al. mentioned in this paper), and Kulkarni et al. (https://arxiv.org/abs/2103.15352). Granted they do not consider public-private data setting, at least to my memory, AFKT do consider mirror descent and study in any \ell_p space, I think it would be interesting to see the comparison of their work with this work. 
summary_of_the_review: The approach in the paper is very natural and I think the algorithm would be very easy to deploy in large-scale system. The proof is very simple and elegant, which I think is another big bonus.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this paper, a new algorithm has been proposed which leverages in-distribution public data to provide improvements in private training. The algorithm uses the loss on public data (with a strongly convex loss function) as a “mirror map” to implement private mirror descent on the private data. It is shown to give dimension independent bounds in certain regimes. Empirically, on both synthetic and real world datasets it is shown to perform favourably compared to recent work.
main_review: Strengths:
1. This paper proposes a new idea to use public data implicitly by using the public data loss as the mirror map in DP mirror descent.
2. The empirical results of this paper on real world datasets seem to beat current baselines.

Questions/Clarifications:

1. In my opinion, this paper needs better writing. At many places, mathematical notation is either used but not defined explicitly or sometimes not consistent. A short notation section, would make its easier to read. I will point out a few places where I found it particularly confusing.

    a. I couldn't find the definition of $||\cdot||_Q$, although it maybe standard, its better to explicitly define it to clear any confusion.
    b. In lemma 3.3, how is $\ell(\theta;D)$ defined? It doesn't parse with the definition of $\ell$ in the first line.
    c. Usually $\mathcal{L}$ denotes the population loss and $\hat{\mathcal{L}}$ denotes the empirical loss, this notation is overloaded and causes confusion


2. The way to bound the excess population risk seems non-standard. If I understand correctly, first the difference of empirical loss of the estimate and the population optimum is bounded, lemma 3.3 is supposed to relate the population optimum to the sample (empirical) optimum, and then Lemma 3.4 is used to relate the excess population risk and excess empirical loss. Is there some intuition as to why this path was chosen? Why can one not directly either give an algorithm with population loss bound or give an excess empirical loss bound and add the generalization error?

3. One of the biggest causes of concern for me is the Assumption 3.1, it assumes that some minimizer of the private loss is also the (unique) minimizer of the public loss. Can the authors give a real world example where the two losses are not the same but this holds?

4. Overall, the paper lacks toy examples which would help understand the theory better and clear doubts that arise when reading assumptions. Some simple toy examples could be linear regression, logistic regression, LASSO, etc. I'd be curious to see what are the choices of private and public loss for these cases, what is the Gaussian width and what does the guarantee look like for these values?

5. Since the minimizers of the public loss and one of the minimizers of the private loss is the same, one trivial baseline to compare against is doing non-private training using only public data. It seems the setting here is that of public data being a constant but small fraction of the private data. What is the comparison of errors for this setting?

6. In the proof of Theorem 3.2, if $\nabla \Phi(\theta_0) = 0$, since $\Phi$ is the public loss, which is strongly convex, this would imply $\theta_0$ needs to be the empirical public loss minimizer? It would be better if a formal argument is made for this.
summary_of_the_review: There are some issues with the writing and some questions regarding the validity of assumptions and the validity the claim of dimension independence in usual settings, as detailed in the main review. Thus my score of 5.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors study differentially private empirical risk minimization (DP-ERM). Specifically, they study the case where the constraint set $\mathcal{C}$ has additional geometric structure, i.e., its Gaussian width could much lower than the underlying dimension $p$, such as the $\ell_1$-norm ball. The paper has been studied previously. However, this paper assume there are some additional public data. Specifically, they apply Mirror Descent with the loss generated by the public data as the *mirror map*, and using DP gradients of the loss generated by the private (sensitive) data. They also provide some experiments to show the performance of their algorithm.
main_review: Strengths:
1. The authors use public data as the mirror map to provide improved bounds compared with the SOTA. This idea is quite interesting and may be used to other problems. 
2. They further show that their algorithm has a natural "noise stability" property.
3. Although DP Mirror Descent has been studied before, they were no experimental result. This paper provide some experimental results. 

Weakness: 
1. Compared with the classical case ("Private empirical risk minimization beyond the
worst case: The effect of the constraint set geometry") The improvement on the upper bound is limited if there is not enough data. 

2. To achieve the upper bound, the running time needs to be $O(n^3)$, which is lower than the SOTA $O(n^{1.5})$  [1]. 

3. The paper did not compared with the SOTA ("Private empirical risk minimization beyond the
worst case: The effect of the constraint set geometry") in experiments. I think this is necessary as this is the most close method, instead of DP-SGD. 

Moreover, the authors left the reference [1], which also studied the problem. 
[1]Wang, Di, Minwei Ye, and Jinhui Xu. "Differentially private empirical risk minimization revisited: Faster and more general." arXiv preprint arXiv:1802.05251 (2018).
summary_of_the_review: As I mentioned, due to high time complexity (which is impractical), lack of comparison with SOTA in experiments and limited improvement on the upper bound. I tend to reject the paper. 
--------
After the rebuttal, the reviewer solved mots of my concerns instead of the time complexity. So I raise the score to 5.
review_title: null

Meta-review: This paper proposes a new algorithm for private ERM, when given access to public data, with a dimension-independent risk guarantee if  (A) the public and private datasets are of the same distribution, (B) public dataset size exceeds the dimensionality (or, rather, the squared Gaussian width of an appropriate set), and (C) the public and private loss functions share a minimizer (and the gradients at the shared minimizer must satisfy some variance bounds). The algorithm uses the public data as the Bregman mirror map within private mirror descent (where Gaussian noise is added to the gradients), thus implicitly affecting the geometry, as opposed to explicitly learning the geometry as done in earlier works.

One reviewer was very positive, but two hovered around the borderline and expressed some reservations about the theory and experiments. Regarding the experiments, they did not compare to the ICML'21 paper by Asi et al --- however the authors of that paper have (surprisingly) still not released their code, so I think this is forgivable. Since the paper was on the borderline, I read it myself, with a focus on the theoretical aspects. I find myself agreeing with the second reviewer that the assumptions are strong, and their justification is weak and unrealistic. 

Regardless of whether the paper, is accepted or not, I strongly recommend the authors to add condition (C) to their abstract (just the part about the shared minimizer) --- currently the abstract mentions two of the above but not the critical third one. I think (A) is already a strong assumption --- their justification that some users opt-in to reveal their data does not justify this, because the opt-in will not be random (if the opt-in depends on covariates like gender/age/..., the datasets will not be identically distributed). On top of that, (C) is also a strong assumption --- indeed usually the loss functions would be different (for eg, the private one would be clipped, and clipping will rarely preserve the population minimizer, as well as regularized) --- their justification that for a linear model with symmetric noise, clipping does not change the minimizer may be true (though not proved), but we would never expect the linear model to be true in practice even if we employ it as a working model. Last, assumption (B) restricts its use in many common high-dimensional data problems. Overall, I am pressed into a corner to find situations in which all three assumptions would be true.

Nevertheless, supposing that these assumptions hold, the algorithm is indeed clean, and the empirics appear reasonable. Overall, the paper remains on the borderline. Whether accepted or rejected, I expect the authors to do a much better job of carefully justifying their assumptions, with realistic and not far-fetched examples (as suggested by the second reviewer).
Decision: Reject