Towards hyperparameter-free optimization with differential privacy

Authors: Ruixuan Liu, Zhiqi Bu
Primary area: alignment, fairness, safety, privacy, and societal considerations
Keywords: Differential privacy, optimization, hyper-parameter tuning

Abstract:
Differential privacy (DP) is a privacy-preserving paradigm that protects the training data when training deep learning models. Critically, the performance of models is determined by the training hyperparameters, especially those of the learning rate schedule, thus requiring fine-grained hyperparameter tuning on the data. In practice, it is common to tune the learning rate hyperparameters through the grid search that (1) is computationally expensive as multiple runs are needed, and (2) increases the risk of data leakage as the selection of hyperparameters is data-dependent. In this work, we adapt the automatic learning rate schedule to DP optimization for any models and optimizers, so as to significantly mitigate or even eliminate the cost of hyperparameter tuning when applied together with automatic per-sample gradient clipping. Our hyperparameter-free DP optimization is almost as computationally efficient as the standard non-DP optimization, and achieves state-of-the-art DP performance on various language and vision tasks.

Decision: accept (spotlight)
Reviewer scores: 8, 6, 8, 8

Reviews and discussion:
<thread>
creation date:
1730142085947

thread_type:
official_review

<thread_object>
creator: reviewer_2fnr

<content>
summary:
This paper proposes a method for differentially private training that eliminates the need for hyperparameter tuning, addressing a core challenge in DP deep learning. The authors provide clear discussions on the method’s efficiency, privacy guarantees, and utility. Both theoretical and empirical analyses are well-founded and straightforward.

strengths:
This is a well-written paper that effectively present its methods. The motivation is clear, the connections to previous work are discussed, and the experimental results are comprehensive and convincing. The method is simple yet effective in terms of efficiency and utility. The theoretical results are presented clearly, avoiding unnecessary complications, and the experiments are solid.

weaknesses:
See below.

questions:
1. In Theorem 1, when $R_l \approx L$, the clipping bias is close to zero, where $L = \frac{1}{B} \sum_i L_i$ is the public per-sample gradient (right?), which seems to be a CLT-based result (please correct me if I’m wrong). My questions are: 
- (1) Could the authors provide guidance on minimum batch sizes needed (to make CLT works) in practice, based on their empirical observations? Although one always wants large batch sizes but due to limited computational resources, one often can't afford super large batch sizes.
- (2) I understand why you set $\tilde{L}\_{t-1}^{(0)}$ as $R\_l$ for the next iteration, given that the loss values are similar. However, while $L\_{t-1}$ might be close to $L\_{t}$,  I worry that $\tilde{L}\_{t-1}$ could differ significantly from $\tilde{L}_{t}$ because of the clipping and noising, which might not give bias $\approx 0$. Some discussion or empirical results on this would be valuable.
- (3) What was the rationale for choosing $\tilde{L}\_{t-1}^{(0)}$ specifically? Did the authors experiment with other options like $\tilde{L}\_{t-1}^{(+1)}$ or $\tilde{L}\_{t-1}^{(-1)}$, and if so, what were the results?

2. In the main algorithm, I assumed $\eta_i \in \\{-1, 0, +1\\}$ represents the series of potential lrs. Is there a specific reason for this choice? I understand the need for at least two $\eta_i$'s, but $\{-1, +1\}$ seems more intuitive to me...? Could the authors explain the rationale behind including 0 in the set of potential learning rates? Are there specific benefits for this choice? Also, I’m unclear about how to fit eqn. (6). In Section 4.4, the authors mention that solving this is quite efficient, with the cost "mainly arising from additional forward passes." Could the authors provide more details on the practical implementation of solving equation (6), and specifically, what optimization method was used, and how much computations were typically required to find a solution?

3. Could the authors provide insights into why D-adaption and Prodigy struggle in low-$\epsilon$ regimes for full finetuning, as seen in the first table of Table 2 and Table 3? Are there specific aspects of these methods that make them less suitable for differentially private optimization? Also, for clarity, could the authors specify the value of $K$ used for HyFreeDP results in Tables 2 and 3? I assumed $K=10$ throughout these experiments, but If it varies, a note explaining the choice for each experiment would be helpful.

4. I noticed in Table 2 that NonDP-GS w/ LS outperforms HyFreeDP, especially on CIFAR-10, and in Table 3, NonDP-GS and HyFreeDP show similar performance. Do authors have any intuitions behind? I’m particularly curious why NonDP-GS w/ LS performs so well on CIFAR-10 dataset - is it because the task is too simple? If I understand correctly, NonDP-GS does not account for privacy loss from hyperparameter tuning, so the $\epsilon$ values for NonDP-GS might be underestimated. It would be great to include the results for NonDP-GS, considering the privacy cost of tuning. I imagine that HyFreeDP would then strictly outperform it...?

5. It seems to me that this method works for per-batch clipping (since it also ensures dp [1]) as well, except that eqn (7) needs to be modified. It would be particularly useful for differentially privately training models with non-deomposbale loss [1, 2].

[1] Huang, Alyssa, Peihan Liu, Ryumei Nakada, Linjun Zhang, and Wanrong Zhang. "Safeguarding data in multimodal ai: A differentially private approach to clip training." arXiv preprint arXiv:2306.08173 (2023).
[2] Kong, William, Andrés Muñoz Medina, and Mónica Ribero. "DP-SGD for non-decomposable objective functions." arXiv preprint arXiv:2310.03104 (2023).
</content>
</thread_object>

</thread>
<thread>
creation date:
1730489431470

thread_type:
official_review

<thread_object>
creator: reviewer_e2ge

<content>
summary:
This paper discusses how to improve the performance of DP optimization by improving the private selection of hyperparameters. This is done by always scaling the gradient to norm 1 and adjusting the learning rate for each training step privately. The selection of learning rate is done by adapting a rule used in non-DP literature which solves an approximate objective for the best learning rate, but making this private by privatizing the loss evaluation used in this learning rate objective. Extensive experiments shows this improves performance over alternative DP hyperparameter selections, and is often comparable to a non-DP grid search of hyperparameters. Further experiments show the computational overhead is minimal. Certain experimental details are missing in the text, though I believe this can be easily addressed.

strengths:
1) Hyperparameter selection in DP does not inherit the same rules of thumb as non-DP, and hence understanding hyperparameter selection for DP training is a core problem
2) The results are strong and seemingly near optimal (given the non DP grid search results)
3) The observation that a specific generic ML hyperparameter selection approach translates well to the DP setting seems important and novel to the DP community

weaknesses:
1) In my opinion the presentation can be improved: in the questions I try and clarify several possible typos. I emphasize this as I originally had more issues with the claims made in the paper but was able to answer these by cross-examining statements elsewhere, which could have been more easily resolved with some changes to writing.

2) Certain details about the experimental setup are missing, such as exact DP $\delta$ values used, and the range of hyperparameter grid search. I ask questions about these in the questions section (labelled Major), and believe they can be easily addressed, and am willing to increase my score given they are addressed in the rebuttal.

questions:
1) The line numbers are missing in the pdf, the authors may want to fix this. In the following I will try my best to describe the location of the typo


2) In equation 6, I believe you mean to also use the privatized loss for L(w), currently it is un-privatized and hence the objective is not private. I can see from the algorithm you input to equation 6 privatized losses, so I presume this is a typo in equation 6

3) In the opening paragraph of section 4.1, I do not believe saying Auto Clipping is equivalent to Rg = 0 is correct. This would mean you always clip to 0 gradient norm. I believe you can replace this by saying you always clip to gradient norm 1, which is consistent with equation 1.

4) In algorithm 1 could you write the inputs to algorithm, which I take as initial values for: $\eta$, $R_l$. This would help with reading/understanding the algorithm

5) In line 8 of algorithm 1, can you replace $(-\eta,0,\eta)$ with set notation {$\eta, 0,\eta$} to be clearer how equation 6 is instantiated; at first I thought it was run over an interval.

6) In line 9 of algorithm 1 I find it vague as stated; more precisely can you say you minimize the previous fitted quadratic?

7) (Major) In section 5.1 experiment setup paragraph, can you explicitly state the deltas used in the experiments; I could not find this in the appendix either.

8) (Major) In table 2, can you add error bars for the experiments? E.g., report 1 standard deviation

9) (Major) Can you report the grid search range in the appendix?

10) Can you explain what BitFit is briefly in the experimental setup paragraph; I believe this will clarify better the differing results for full finetuning

11) I found the figures hard to read when I printed the paper; consider increasing the size and possibly moving one figure to the appendix.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730678138315

thread_type:
official_review

<thread_object>
creator: reviewer_yg4l

<content>
summary:
The paper proposes to tune learning rate privately based on quadratic approximation during DP-SGD training. It is shown that the proposed algorithm can achieve comparable performance with non-DP learning rate search.

strengths:
1. The proposed algorithm works pretty well in the experiment with not much additional cost in computation cost and privacy.
2. The idea is simple yet effective, factorizing learning rate tuning during training using quadratic approximation.

weaknesses:
The proposed algorithm seems to still require a initial learning rate and the algorithm's sensitivity to the initialization seems missing.

questions:
For DP hyper-parameter optimization, have the authors considered using gradients from backpropagation w.r.t learning rate to tune the learning rate privately?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730678263466

thread_type:
official_review

<thread_object>
creator: reviewer_uuab

<content>
summary:
This paper proposed a method to estimate hyperparameters (i.e., learning rate) in differentially private optimization with gradient normalization (instead of gradient clipping). As learning rate is the main tuning parameter, the proposed optimizer is hyperparameter free. The proposed additionally differentially privatizes the loss (a scalar) for estimating the learning rate.

strengths:
- Setting hyperparameters in DP optimization is an important topic for both modeling and privacy.  
- Experiments demonstrate the advantage of the proposed method compared to naively applying parameter free optimization methods like D-adaptation in DP optimization, and DP-hyper style algorithm by differentially privatizing hyperparameter search.

weaknesses:
The technical part of the paper is generally hard to read. I am not confident the proposed method is technically correct.

questions:
I have to read GeN Bu et al. (2023) again to understand the proposed method in this paper. And I cannot find Eq (5) of this draft in GeN Bu et al. (2023). What is \omega in Eq (5) and (6)? Could you write the closed form solution for estimating \eta? If not, why? 

I request the authors to clarify privacy accounting of their proposed method. Starting from the DP definition, e.g., what are their mechanism input and output? How are their “Loss Privatization” and “Gradient Privatization” composed? It looks to me Line 9 in Alg 1 is data dependent, but it is unclear whether it is considered in the DP algorithm or accounting. It is OK to use GDP and/or autoDP library, but I request the authors to detail how GDP/autoDP is used for this specific algorithm.

Minor: the authors might consider the usage difference of \citep and \citet in writing.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733349773596

thread_type:
public_comment

<thread_object>
creator: ~ashwinee_panda1

<content>
title:
Minor Comment on Related Work

comment:
I enjoyed reading the paper. I have a couple of minor comments on related work for DP HPO. The authors state "The more explored approach is to assign a small amount of privacy budget to privatize the hyperparameter tuning. Examples include:..." on Lines 059-060, and include a citation to one of our papers, which I appreciate. I would just like to point to a couple of previously published papers that I think are relevant.

(NeurIPS 2023) https://proceedings.neurips.cc/paper_files/paper/2023/hash/59b9582cd35f555ea8415030073e7b22-Abstract-Conference.html
(ICML 2024) https://icml.cc/virtual/2024/poster/34966 {**Disclaimer: This is our own paper**}

I understand that this paper is clearly distinct, in that the authors present a method for determining an automatic learning rate schedule. However, our ICML 2024 paper does include results for eps=1 privacy budget full finetuning of Vit-small / Vit-base on CIFAR10 and CIFAR100, so they are in some sense comparable. Although, this work clearly has lower runtime overhead. 

I would also comment on the statement in Lines 431; "LoRA typically requires a LR that is 10x larger than FFT" -this is a tricky statement, because the LR in LoRA is really two hyperparameters: the alpha term and the learning rate itself. As prior work has shown (TMLR 2024 https://openreview.net/forum?id=aloEru2qCG&noteId=Jb3PQNQDI2) if alpha is scaled appropriately as alpha=2*rank, then the learning rate doesn't actually need to be much larger. I think this is probably a point that could work in favor of the paper, because as one reviewer noted, there is a hyperparameter, which is the base learning rate.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper discusses how to improve the performance of DP optimization by improving the private selection of hyperparameters. This is done by always scaling the gradient to norm 1 and adjusting the learning rate for each training step privately. The selection of learning rate is done by adapting a rule used in non-DP literature which solves an approximate objective for the best learning rate, but making this private by privatizing the loss evaluation used in this learning rate objective. Extensive experiments shows this improves performance over alternative DP hyperparameter selections, and is often comparable to a non-DP grid search of hyperparameters. Further experiments show the computational overhead is minimal. Certain experimental details are missing in the text, though I believe this can be easily addressed.

All the reviewers agree that this paper has enough novelty and contribution to be published at ICLR.