The importance of feature preprocessing for differentially private linear optimization

We thank the reviewer for acknowledging that our work is a good connection between theory and practice. Below we address the reviewer’s questions on our work.

[The study subject - linear model - is relatively simple and less representative compared to SOTA ML models.] [Except the Fashion-MNIST dataset (released in recent few years), original MNIST and CIFAR-100 datasets are relatively outdated compared to other image datasets.]

We believe the main contribution of our work is to formally prove that feature preprocessing can help DPSGD-based algorithms to obtain better optimization guarantees. While the considered model and datasets are simple, we believe these will serve as important first steps to study more complex SOTA models and modern datasets.

On the other hand, while without privacy, these tasks have been studied a lot and SOTA results have been advanced over the years, these tasks still remain challenging tasks for private image classification. For example, to the best of our knowledge, no good classification model has been privately trained from scratch on CIFAR-100. Current results solve classification on CIFAR-100 by private finetuning using pre-trained models on larger datasets (e.g. ImageNet1K). For this, [De et al 2022] showed that fine tuning the last layer of a WRN network achieves an accuracy of 70.3% on CIFAR-100 at $\varepsilon = 1$. Note that fine tuning the last layer of an advanced model like WRN is the same as training a linear model. With our technique, we are able to improve the accuracy to 71.6%, which is close to the current SOTA result of 71.9% [Bu et al 22] for the task of fine tuning on CIFAR-100 with pretrained models from ImageNet1K. This shows that for private training of models, linear models may not be just a simplified model, but rather a useful model in practice, especially given its equivalence to private fine tuning of the last layer of any neural models.

[Omega tilde in Theorem 1]

Tilde was used to hide logarithmic factors in the big O expression. In the updated draft, we have removed the tilde notation and written out the specific log factors. Now the term inside Omega represents an up-to-constant bound on the required number of samples to obtain the result in Theorem 1.

[Can you explain more about what the “uninformative” means in Theorem 3?]

The term "uninformative initialization" is mainly used to require that the initialization should be not be chosen depending on the input dataset so that it will benefit the optimization for specific datasets instead of all. In the case of $D'$ in Theorem 3, we mean $w_0 = (w_0(1), w_0(2))$ should satisfy that $w0(2) ≤ 0$ since the optimal $w^*$ for $D'$ has $w^*(2) > 0$. Similarly for $D''$ we require $w_0(2) ≥ 0$.

[High-level ideas on correctness for lemmas in Section 5.]

Thanks for the great suggestion. Lemma 3 and 4 mainly come from prior work, and the results are direct corollaries. Proof of Lemma 5 is short and provided in the section. We have added a high-level explanation on why Lemma 6 and Lemma 7 hold in the update draft (marked in red).

We thank the reviewer for agreeing to the novelty of the work and raising important questions regarding the result. Below we address the concerns raised by the reviewer.

[The performance of DPSGD-F (Theorem 1) on the counterexample.]

Thank the reviewer for pointing out that Theorem 1 in the submitted manuscript can only show that DPSGD-F achieves a constant error for the counterexample in Section 4. After a careful examination of our result, we are able to obtain an improved performance guarantee of our proposed algorithm DPSGD-F with a more involved analysis. We have marked the updated result (Theorem 1) and analysis (Appendix B.5) in red in the updated draft. In short, we are able to improve the dependence on $R$ and $diam(D)$ to roughly $(diam(D) + R/n^2) \cdot \sqrt{rank(M)}/(n\varepsilon)$, ignoring other constants that don’t depend on $R$ and $diam(D)$. In this form, it can be seen that DPSGD-F strictly improves upon DPSGD by achieving a $o(1)$ error when $\sqrt{\mu} \ll n < \mu/\varepsilon$.

[Whether the counterexample still holds when $x_1 = e_1 + 1/\mu e_2$ and $x_2 = e_1 - 1/\mu e_2$.]

The result holds under any rescaling of $x_1$ and $x_2$. To see this, the standard deviation of the noise for DP-SGD scales linearly with the norm of $x$ and hence any scaling won’t change the relative scale between the added noise and the gradient vector.

[The upper bound in Theorem 1 is dimension-dependent since the authors required that $n\geq O(\sqrt{d}/\varepsilon)$.]

We agree that this is a limitation of our work. This constraint mainly comes from the requirement on $n$ for the private mean estimation step. To the best of our knowledge, the requirement is needed for state-of-the-art mean estimation algorithms. We leave studying whether the constraint can be improved as a future direction.

[Given that the counterexample doesn't fully convince the reviewer, it is recommended that the authors conduct an empirical evaluation of DPSGD-F on a wider range of datasets]

We hope the improved performance guarantee and analysis on the algorithm resolves the reviewer's concern on the counterexample. This work is mainly a theoretical investigation of the importance of feature preprocessing for private optimization. We believe the theoretical result (especially the improved version in the updated draft) and the set of experiments already give decent evidence on our claim. Moreover, some of the experiments already demonstrate the potential of our approach for challenging classification problems. For example, for the task of privately finetuning the last layer of a pretrained model (using ImageNet1K) on CIFAR-100 under $\varepsilon=1$, our result improves the previous best accuracy from 70.6% (De et al., 2022) to 71.6%. This being said, we agree that conducting more extensive experiments would make the empirical result more convincing. We could add more experiments in the final version if the reviewer still has concern on the theoretical and empirical contribution of the work.

We thank the reviewer for the very positive feedback and acknowledging the contributions of our work. Below we address the concern the reviewer raised about the experiment part of our paper.

[The algorithm is significantly modified for the experiment section. …… The part I am concerned about is the normalization of the features before computing the mean.]

Thanks for raising the valid concern. Both algorithms we use for the theoretical analysis and experimental evaluations follow the same procedure of (1) private mean estimation and translation of the features; (2) perform DPSGD on the new features. The main difference is on the private mean estimation step. In the modified algorithm (Algorithm 3), we normalize the features to a fixed norm and use the private Gaussian mechanism for computing the mean.

We note that the modified algorithm with a fixed normalization norm satisfies differential privacy guarantee as claimed in Lemma 9. In experiments, we treat the normalization norm as a hyperparameter and search over a small set of values: {1, 10, 100, 1000}. We then report the maximum accuracy achieved within the set. We agree that this hyperparameter search might leak extra information about the dataset and this is not taken into account in our reported privacy parameter. However, ignoring the privacy leakage in the hyperparameter search step is commonly used in current empirical evaluations of private training algorithms, e.g., in (De et al 2022). In fact, how to best evaluate the privacy leakage for hyperparameter search is an active area of research, e.g., in (Papernot and Steinke 2022), which is beyond the scope of this work.

Hence, while modifications to the algorithm are made in the experiment section, we believe the result still demonstrates the importance of feature pre-processing for private linear classification tasks, which is the main message of our work.

Nicolas Papernot and Thomas Steinke Hyperparameter Tuning with Renyi Differential Privacy ICLR 2022

We thank the reviewer for the positive feedback and constructive comments. Below we discuss the technical questions raised by the reviewer.

[Comparison between Lemma 1 (prior result) and Theorem 1 in different regimes of $rank(M), n, \delta$, and other parameters?]

Thanks for raising the important point. After a careful examination of our result, we are able to obtain an improved performance guarantee of our proposed algorithm DPSGD-F with a more involved analysis. We have marked the updated result (Theorem 1) and analysis (Appendix B.5) in red in the updated draft. In short, we are able to improve the dependence on $R$ and $diam(D)$ to roughly $(diam(D) + R/n^2) \cdot \sqrt{rank(M)}/(n\varepsilon)$, ignoring other constants that don’t depend on $R$ and $diam(D)$. In this form, our result strictly improves upon the prior result. When $diam(D) > R/n^2$, $diam(D)$ is the leading term in the optimality gap and the dependence on $R$ is at most logarithmic (only appears in the requirement on the $n$). When $diam(D) < R/n^2$, the dependence on $R$ is improved by a factor of $n^2$, which also improves upon the prior result. Moreover, the $\frac{R}{n^2}$ term can be reduced to any inverse polynomial function of $n$ by increasing the requirement on $n$ in the assumption by a constant factor. We use $R/n^2$ mainly for presentation purposes.

[Relation between feature pre-processing for DP linear optimization and feature pre-processing for DP linear classification.]

This is a great question. We agree that the main focus of this paper is on linear classification models. However, since linear classification is a special case of linear optimization with specific requirements on the type of loss functions used, we believe our result also hints on the role of feature pre-processing for linear optimization problems. The main property that we use about linear classification tasks is that the final minimizer satisfies assumption 2, which requires that the linear model should predict values with different signs for at least one pair of the samples at the minimizer. This may not hold for other linear optimization problems in general, e.g., linear regression. We suspect that some processing of the labels might help linear regression to satisfy this condition, e.g., subtracting the mean from the labels, but this might need further investigation since the mean needs to be noised to guarantee privacy. We leave studying whether linear optimization can help for general linear optimization problems as important future directions.

[Suggestions on improving the presentation.]

Thanks for the suggestions on improving the presentation. We have added an explanation for the norms used and revisited the definition of $G$ when necessary. Changes are marked in red.