Towards hyperparameter-free optimization with differential privacy

We thank the reviewer for the comments and all your questions are well-received! Here is our point-to-point response.

Q1-[loss clipping threshold]: In Theorem 1, $L$ is the mean of non-privatized per-sample losses (not gradients).

• (1) We empirically observe $B>100$ suffices, though this is law of large numbers rather than CLT. On the computation side, libraries like fastDP allows the same computation efficiency for DP compared to standard non-DP training. Especially, the large batch can be fitted in GPU with the gradient accumulation technique, by breaking into smaller micro batches.
• (2) In current Figure 2 (by comparing dots to stars), we empirically demonstrate the influence of clipping and noising on each loss values (and corresponding curve fitting), which illustrates that clipping and noise have little impact.
• (3) As we stated in Sec 4.1 (Line 267), we have tried $\sum \overset{\sim}{L}_{t-1}^{(k)}$ to further avoid clipping bias. As we can observe in Figure 2 that there is almost no gap between "w/o clipping w/o noise" and "w/ clipping w/o noise".

Q2-[choise of $\eta$ range]:

• We need at least 3 points to solve the quadratic function uniquely (with the form $ax^2 + bx + c$) in Eq (6).
• Including $L^0$ (via $\eta_i=0$) is crucial because sampling points around $\eta_i=0$ allows the quadratic function to capture the local behavior of the loss at $w_t$ effectively.
• Implementation for Eq(6): Given the x-list $\{-\eta, 0, \eta\}$ and the y-list $\{L^{-1}, L^0, L^{+1}\}$ for the quadratic function $y=ax^2+bx+c$, we input them into the the out-of-box function via from scipy.optimize import curve_fit and obtain the corresponding value for a, b, and c.
  • Internally, it uses nonlinear least squares optimization, typically via the Levenberg-Marquardt algorithm (by default in SciPy).
  • The operations are lightweight, which take microseconds on a decent GPU.

Q3-[Presentation]: We stated the intuition for why methods as D-adaptation do not work in current Section 2.3. In short, these methods require some quantities to be accurately estimated that are very sensitive to the noise, especially in high dimension when model is large. We updated the $K=5$ configuration in revision Sec 4.1.

Q4-[Intuition on results]: To clarify, both NonDP-GS and NonDP-GS w/ LS do not take privacy cost in hyper-parameter tuning, and should serve almost as an upper bound of performance, given that these methods trade-off the privacy guarantee. That is, $\epsilon$ in these methods are indeed underestimated. The "results for NonDP-GS, considering the privacy cost of tuning" is DP-hyper (as we introduced in Line 370).

And HyFreeDP indeed strictly outperforms DP-hyper (as shown in Figure 2).

Q5-[non-deomposable]: Thanks for the insights! We are glad that reivewer finds it useful for non-depmposable loss. We note that loss clipping in Eq(7) is general and not influenced by gradient privatization.

We thank the reviewer for the comments and all your questions are well-received! Here is our point-to-point response.

W1 & minors-[presentation]: We greatly appreciate your efforts and we fixed every presentation issue in the Questions (Q1-Q6, Q10-Q11) in our revision. Specifically,

• Q3: We agree that we need to both setting $R_g\to 0^+$ and enlarging $\eta \to \eta/R_g$, so as to normalize the gradients. We kindly suggest that this is different than setting $R_g\to 1$, which does not enlarge per-sample gradients whose norms are smaller than 1. We modify Sec 4.1 to include this point.
• Q6: We change Line 10/11 in Algorithm 1 to help understanding the algorithm.
• Q10: We add a brief introduction of BitFit and LoRA in the first paragraph of Sec 5.

W2 & majors-[experimental details]:

• Q7: We follow the standard setting to ensure $\delta<1/n$. We specifically use $\delta=n^{-1.1}$ as declared in the first paragraph of Sec 5.
• Q9: We ensure the range is wide enough to cover the optimal choice inside. For clarity, we added detailed setups with references in the second paragraph of Sec 5.
• Q8: Due to time limit, we first show the error bars for one set of main results in table 2 as below. We will update all cells in Table 2 in future revision. The advantage compared to previous works are still significant.

Please kindly let us know if our response addresses your concerns or if there are more questions.

We thank the reviewer for the comments! We would make every effort to improve the presentation and to asssure that our method is technically correct.

Q1-[cannot find Eq(5)]: The quadratic function in our Eq(5) is an equivalent form of Eq (2.3) in GeN [Bu et al. 2024]. We fixed and clarified the citation in the revision Sec 2.3, thus our paper is self-contained without the necessity to read their work.

Q1-[$w$ in Eq(5-6)]: As we stated in Sec 2.1, $w$ is the model parameters.

Q2-[closed solution for $\eta$]: The closed from of $\eta$ for non-DP case is written in our Eq (4). The closed form for DP case is given in Line 173 as well as Algorithm 1 (line 11).

Q3-[privacy accounting]: The major part of privacy accounting is elaborated in Appendix C. The “Loss Privatization” and “Gradient Privatization” are composed by existing theories, e.g. via GDP in Equation 9. To improve clarity, we append detailed pseudo code in revision Appendix Alg 2 with detailed functions to implement.

• For privacy accounting, as we have shown in Figure 1 with the green box, the input includes total DP privacy budget $(\epsilon, \delta)$, constant $K$ (e.g., 3), and other data-independent hyper-parameters $B, N, T$; The output includes noise magnitude for gradient and loss $\sigma_g$ and $\sigma_l$.

• For the whole algorithm, the input is the training dataset $D$, the output is the trained model parameters $w$ and all hyper-parameters, following previous works [Papernot et al. 2021, Wang et al. 2023]. We clarified it in the revision Sec 2.2.

  Following the framework of previous works [Liu et al. 2019, Papernot et al.], suppose there are $m$ privacy-preserving training algorithms $\mathcal{M}_1, \cdots, \mathcal{M}_m$ which corresponds to $m$ possible hyper-parameters. Denoting the whole process of training and hyper-parameter tuning as $\mathcal{M}$, it takes input as a training dataset $D$ and outputs the best outcome over a finite set of $m$ possible hyper-parameters by running $\mathcal{M}_1, \cdots, \mathcal{M}_m$. The end-to-end DP ensures that $\mathcal{M}$ satisfies $(\epsilon, \delta)$-DP with respect to any neighboring datasets and any outcome. And the outcome includes the best model parameters and the corresponding hyper-parameters. In our hyper-parameter-free solution, there is a single training with $m=1$, and the output hyper-parameters are data-independent.

• Line 9 in Alg 1 has been accounted in total privacy cost, as $\tilde{L}$ is privatized.

Please kindly let us know if our response clears your concern about the correctness of our method.

We appreciate the reviewer's detailed comments! Here is our response to your new concerns:

Q1: As shown in Figure 2, the effective noise scale on the loss value is about 0.1 to 0.5, which depends on $\sigma_l, R_l$ and batch size $B$. Specifically, we demonstrated $\sigma_l$ (for loss) and $\sigma_g$ (for gradient) in Figure 3, with respect to different update interval $K$. Generally speaking, we recommend a relatively large K (e.g., 5) and 3 to 5 points for good fitting.

Q2: The values in Line 10 Algorithm 1 can be solved by Eq(6). More specifically,

• While mathematically equivalent, we opted to use scipy.optimize.curve_fit for better numerical stability. Given the x-list $\{-\eta, 0, \eta\}$ and the y-list $\{L^{-1}, L^0, L^{+1}\}$ for the quadratic function $y=ax^2+bx+c$, we can get (a, b, c) using curve_fit. Internally, it uses nonlinear least squares optimization, typically via the Levenberg-Marquardt algorithm (by default in SciPy).
• The closed-form solution is very complicated in general for this minimization problem. Yet, we give it for three points (with details to be added in the camera-ready):

$\frac{\eta}{2}\frac{\tilde{L}(w+\eta g_\text{DP})-\tilde{L}(w-\eta g_\text{DP})}{\tilde{L}(w+\eta g_\text{DP})-2\tilde{L}(w)+\tilde{L}(w-\eta g_\text{DP})}$ where $\tilde{L}$ is the privatized loss and $g_\text{DP}$ is the privatized gradient.

Q3: We appreciate your constructive suggestions. We will add experimental analysis on the robustness to $\eta_0$ and initial $R_{l}$ in our future version (may finish after discussion period). In this work, we have demonstrated the robustness by fixing $\eta_0=1e-4$ and initial $R_l=1$, then varying different models and datasets. While this is different to an experiment that fixes a model/dataset and then varies $\eta_0$ and initial $R_l$, we think the robustness is (maybe indirectly) observed and we have provided a default configuration as a guideline for practitioners.

Please kindly let us know if you have more comments. We are glad to solve them all. Thanks!

We thank the reviewer for the comments and liking this work! Here are our point-to-point response.

W1-[initial learning rate]: We have empirically observed that an initial learning rate $1e-4$ is robust to work well for all tasks (making it a data-independent choice). Besides, we note that previous work in the non-DP regime shows that the performance is robust to initial learning rates (see Figure 14 in [Bu et al. 2024]). In the revision, we highlight such choice in Sec 5 and Algorithm 1.

Q1-[other approaches]: We have considered back-propagation on $\eta$, i.e. updating the model with $\eta$ and simultaneously updating $\eta$ with gradient descent under another meta-learning rate. However, the introduction of this meta-learning rate keeps the number of hyperparameters the same and could be more sensitive to tuning than $\eta$. Therefore we opted out this idea.

Hi Ashwinee, Thank you for your comment and sharing your appreciation of our work! We agree these papers are relevant and include all of them in our camera ready. It is generally exciting to read and work on DP optimization/hyperparameter tuning. Please feel free to reach out if you would like to extend the discussion.