Venue: NeurIPS 2022 Conference

Reviews:

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: 
The paper considers differential privacy convex optimization in high-dimensional settings. Early theoretical results on private convex optimization say that empirical and population risk depends on the model size. However, empirical observations showed that the error could be much smaller in practice. Further theoretical work showed that if the gradients of the underlying loss function lie in a fixed low-rank space, then the risk can be bounded by its rank. 
 
This paper is motivated by the empirical observation that given a pre-trained model, then using private gradient descent to fine-tune the model has good performance independent of model size. In a sense, this empirical observation contradicts theoretical results that state that differentially private convex learning degrades with model size. 
 
The paper provides bounds independent of the model size on the empirical and population risk of private convex optimization. This result extends from prior work [JT14, STT20] that assumes that gradients belong to a fixed low-rank space. Furthermore, other results require learning the gradients subspace to get improved results or using public data to approximate the gradient subspace. Finally, the paper analyzes DP stochastic gradient descent without modification and only requires a condition called restricted Lipschitz continuity. 
 
The analysis follows by partitioning the solution space into different orthogonal sub-spaces and then decomposing the gradient into a sum such that each term falls into a subspace. By the restricted Lipschitz continuity condition, each gradient term can be bounded by a constant.

strengths_and_weaknesses: 
The paper analyzes a practical algorithm (DP-SGD) for convex optimization and provides improved risk bounds under certain conditions that are more general than prior work. In addition, the bounds provided recover bounds from prior work that requires a low gradient subspace.
The idea of using restricted Lipschitz continuity conditions is new to my knowledge, and the analysis that follows is novel. Furthermore, experiments validate the theoretical claims. 

The paper also motivates the theory in the convex setting to justify the high performance of pre-trained models in a non-convex setting. The paper claims and provides evidence that since pre-trained models are already close to a local optimum, they could lie in a small subspace. This argument gives some optimism about the future of private training large models. 

questions: Could more intuition be provided about the is the effect of regularization in the analysis?

limitations: Yes
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 proposes an analysis that captures the behavior that DP-SGD’s utility performance does not deteriorate with the increasing dimension under a specific assumption. Such assumption generally states that if the gradient lies in a limited subspace of the ambient space, then the excess risk is then dimension-independent.
This paper gives some evidence for the fact that when fine-tuning a DL model, such an assumption holds. By such observation, the theoretical result explains some phenomena.


strengths_and_weaknesses: The error analysis technique is not new, and the key assumption proposed in this paper is a variant of the assumption that gradient lies in a limited subspace (which is not new either), however, from such an assumption to deriving the error bound seems like non-trivial. And such result has an implication.
questions: See the limitations for details 
limitations: This paper assumes that it is in the convex setting, however, even in the fine-turning stage, it is not guaranteed in the convex setting as is the case for deep learning model. Hence, such result has a limited implication.
Another important point is that, when doing fine-tuning, it is still not guaranteed to be near the local optimal point (we still don’t how to quantify “near” either). The experiment gives positive evidence, however, I think more experiment should be done to validate the hypothesis that fine-tuning starts from a near-optimal point.
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: Recent advances in natural language processing have witnessed the advantage of a large language model in private fine-tuning, which can achieve state-of-the-art performance even compared to non-private algorithms. Since the theoretical understanding of success is still lacking so far, this paper fills the gap to understand why the curse of dimension does not happen in the large-model fine-tuning. By using the novel notion of restricted Lipschitz-continuity, the authors proved a refined dimension-independent bound on the excess empirical error and excess population error by differentially-private stochastic gradient descent. Empirically, the authors show that the near-optimal models (e.g., pre-trained models) tend to produce gradients concentrated in a few principal components of the gradient subspace, which confirm the assumption of the restricted Lipschitz-continuity.
strengths_and_weaknesses: Strength
1. The paper asked an important and novel question: why the curse of dimension does not happen with private fine-tuning of pre-trained models? Prior empirical results have demonstrated the phenomenon, yet a theoretical understanding was not available. The paper fill the gap and clearly give an explanation of the source of the success.
2. Both the theoretical studies and empirical evaluations are insightful and sound and could inspire future works in the community of private learning.
3. The paper is well written and the experiments are well designed to support the theoretic results.

Weakness
1. My major concern is the experiment part. More large models should be evaluated to demonstrate the rationality of the restricted Lipschitz continuity assumption.
questions: 1. The definition of the convex domain diameter D is not clearly stated. It was first used in Line 129 to state the prior bounds. In Theorem 3.3, D is defined to be the upper bound of the difference between x and x^*. It is confusing if the two D's denotes the same or related things. In the final excess error bounds, the D is used intensively both in prior arts and the paper's results. The authors may clarify the notation here.
2. In Line 267 of the Experiment section, why the DistillRoBERTa is selected? Do the results generalize to other large models? In the [LTLH21] which is the major empirical motivation for the work, the large RoBERTa was used. Some clarification may help the readers to understand the generality of the empirical studies. Since the restricted Lipschitz continuity is the major assumption of the paper, stronger empirical evidence is essential here.
3. How does the private fine-tuning of all attention parameters compared to more parameter-efficient fine-tuning? Since the dimension is a major concern for private learning in the scope of the paper, some advanced parameter-efficient fine-tuning should gain some advantage in the privacy-accuracy trade-off. By parameter-efficient fine-tuning, e.g., Prompt, the dimension of parameters to be privately trained could be effectively reduced. As a result, I believe that the authors may provide some empirical or theoretical results discussing the connection between the studied (almost) full fine-tuning and the parameter-efficient fine-tuning.
limitations: I did not find obvious negative social impacts of the work. The authors bring up the limitation of their work on the bound tightness. I believe the limitation is beyond the scope of the paper, which is reasonable to be left there.
review_title: null

Meta-review: metareview: The paper considers DP convex optimization in high-dimension, providing bounds independent of the model size on the empirical and population risk (extending prior work that assumes that gradients belong to a fixed low-rank space). All the reviewers agree that this is an important problem and the results are interesting, and support accepting this paper.
confidence: Certain
Decision: Accept