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.
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).