Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper presents differentially private algorithms with dimension-independent margin guarantees for various classification problems such as linear classification, kernel-based classification, and feed-forward neural network classification. The key to the algorithm for linear classification is using the FAST JL transform for feature space reduction and then using the DP-ERM algorithm from  [BGM21] for solving the convex optimization problem (along with standard boosting techniques). The key to the algorithm for private kernel-based classification is to first approximate the feature map by a finite-dimensional map determined via Random Fourier Features. Finally, for  Feed Forward Neural Networks classification, the authors rely once again on the JL transform to reduce the dimensionality before each layer and apply the exponential mechanism to achieve pure differential privacy.

Overall, this is a compressive and systematic study on differentially private classification and I recommend it be expected.
strengths_and_weaknesses: The paper provides a bunch of elegant algorithms for differentially private classification. While the technical components used in the algorithms are well known, the literature review, as well as results, are comprehensive. 
questions: None.
limitations: Yes.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper introduces several new differentially private learning algorithms with performance guarantees that are independent from the data input dimension and instead given in terms of a confidence margin parameter.
Algorithms are presented for linear classification, kernel classifiers, and neural networks. One of the key tools of the analysis is to use the JL transform to map the hypotheses to a lower-dimensional space, perform learning there, and then to “invert” the transform.
strengths_and_weaknesses: This paper provides interesting results regarding a relevant topic. While many of the main ideas appear to be similar to prior work, the analysis requires non-standard technical extensions, and the resulting bounds are clear improvements.
The models that are studied cover a wide variety of use cases, and both inefficient algorithms, but which are stronger in terms of privacy guarantees, as well as computationally efficient algorithms, at the cost of weaker privacy guarantees, are considered.

In terms of weaknesses, the practicality of the results and limitations could be discussed to a further extent. The bound in Theorem 5.1 could be further discussed to elucidate the role of the parameters—it appears that $r$ is not even defined here.
questions: What is $r$ in Theorem 5.1? It appears undefined in the main text.  
Can the algorithm for learning the NN be efficiently implemented? What is the significance of the bounded norm assumption?

Minor comments: The sentence in lines 102-104 should be fixed  
111 and 112: yields/makes: remove s  
128: “gave construction”  
138 and 139: the term “$\rho$-hinge loss” is overloaded  
Alg. 1 line 4: “an”  
186: “empirical $\rho$-margin” should be “empirical $\rho$-margin loss”?  
limitations: The impact of the assumptions that are made is not extensively discussed in the paper.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper develops several differentially private algorithms with dimension-independent utility guarantees. The results include a pure DP-algorithm and an efficient private algorithm for linear classification. The paper further extends these results to kernel-based hypotheses with shift-invariant kernels and feed-forward neural networks. For all the algorithms, the paper develops margin guarantees independent of the dimension.
strengths_and_weaknesses: Strength:

The existing DP algorithms suffer from a bound with a dependency on either the dimension or the norm of the optimal model, which would not be effective if the dimension or the norm of the optimal model is large. This paper shows that these dependency can be removed and develops several algorithms based on margin guarantees. Therefore, the results are interesting to the differential privacy community.

Weakness:
- The bound in Theorem 5.1 suffers from an exponential dependency on the depth. Therefore, the result is not efficient if $L$ is moderately large.
- For the pure DP algorithm, the bounds have a quadratic dependency on $1/\rho$. The bounds would not be effective if $\rho$ is small.
- The paper presents a series of results. While these results are comprehensive, they may make the paper not focused.

questions: Question
- In the introduction, the authors say that learning guarantee necessarily admits a dependency on $d$ for constrained setting. However, it seems that the paper considers a constrained problem setting: Algorithm 2 involves a minimization over $B^k(2\Lambda)$, the linear predictors are also constrained as $w\in B^d(\Lambda)$. Therefore, it is a bit confusing to me whether the dimension-independent bounds contradict with existing results.
- The paper uses the technique of margin and random projection. It is not clear to me which one is essential to develop dimension-independent guarantee. It would be helpful if the authors could comment on how the margin technique is useful in improving the DP guarantee.

Typos:

Section 4: $(\tilde{\Psi}(x),y))$

Section 4: can designed

Section 4: builds on on

Lemma A.2: the meaning of fat is not rigorous
limitations: Yes.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper proposes a series of DP algorithms for learning linear classifiers, kernel classifiers, and neural-network classifiers with dimension-independent and confidence-margin guarantees. It leverages JL-transform and a faster DP-ERM algorithm to design the faster DP linear classifier with margin guarantees. It combines kernel approximation with the use of the JL-transform to design the DP kernel classifiers with margin guarantees. And in the end, the authors propose a DP neural network learning algorithm for a family of feed-forward neural networks for which they prove a confidence-margin bound that is independent of the input dimension via embedding-based ``network compression'' technique. This enables a broader analysis of DP neural network in the future.
strengths_and_weaknesses: Strengths:
1. This paper introduces its DP algorithms step by step from the DP linear classifer, to the DP kernel classifier and finally the DP neural nework with a very large input dimension and margin guarantees, which makes it easier to understand.
2. Using fast JL-transform to reduce the high dimensionality to improve the time complexity is a nice optimization.
3. Using the embedding-based network compreesion technique to improve the DP neural network learning algorithm.

Weakness:
1. There is no experiments to enhance the theoretical conclusions. It will be better even if the authors can run toy experiments on some small datasets.
2.  It is possible to improve the privacy leakage via advanced composition.
questions: 1. Is it possible to apply advanced composition during the privacy leakage analysis?
limitations: Yes. The authors have addressed  potential negative societal impact.
review_title: null

Meta-review: metareview: After the internal discussion, all reviewers agreed that the paper should be accepted. Please take into account the reviewers' comments while preparing the camera-ready version of the paper.
confidence: Certain
Decision: Accept