Approximating Two-Layer ReLU Networks for Hidden State Analysis in Differential Privacy

Authors: Antti Koskela
Primary area: alignment, fairness, safety, privacy, and societal considerations
Keywords: Differential privacy, machine learning, hidden state threat model, privacy amplification by iteration, DP-SGD

Abstract:
The hidden state threat model of differential privacy (DP) assumes that the adversary has access only to the final trained machine learning (ML) model, without seeing intermediate states during training. Current privacy analyses under this model, however, are limited to convex optimization problems, reducing their applicability to multi-layer neural networks, which are essential in modern deep learning applications. Additionally, the most successful applications of the hidden state privacy analyses in classification tasks have been for logistic regression models. We demonstrate that it is possible to privately train convex problems with privacy-utility trade-offs comparable to those of one hidden-layer ReLU networks trained with DP stochastic gradient descent (DP-SGD). We achieve this through a stochastic approximation of a dual formulation of the ReLU minimization problem which results in a strongly convex problem. This enables the use of existing hidden state privacy analyses, providing accurate privacy bounds also for the noisy cyclic mini-batch gradient descent (NoisyCGD) method with fixed disjoint mini-batches. Our experiments on benchmark classification tasks show that NoisyCGD can achieve privacy-utility trade-offs comparable to DP-SGD applied to one-hidden-layer ReLU networks. Additionally, we provide theoretical utility bounds that highlight the speed-ups gained through the convex approximation.

Decision: reject
Reviewer scores: 5, 3, 5, 6

Reviews and discussion:
<thread>
creation date:
1729780478822

thread_type:
official_review

<thread_object>
creator: reviewer_qa9d

<content>
summary:
This paper considers the hidden state threat model, in which the adversary doesn't have access to intermediate outputs during training. Under this model, previous works have demonstrates that the privacy cost of DP-SGD (or DP-CyclicGD) converges for convex and smooth minimization problems (no additional privacy cost for training the model for additional gradient descent steps). However, in practice, these conditions (convexity and smoothness) are not always met. A simple example of a non-convex optimization problem is the training of a two-layer ReLU network under square loss and L2 regularization. 

This work focuses on addressing this issue by leveraging recent findings, which show that with square loss and L2 regularization, the 2-layer ReLU minimization problem becomes equivalent to a strongly convex minimization problem, provided the number of neurons is sufficiently large. This reformulation, being both convex and smooth, allows for the application of convergent privacy analysis under the hidden state threat model.

The authors show this DP-CGD of the alternative convex formulation enjoys similar utility-privacy tradeoff as solving the original non-convex problem with DP-SGD (under the threat model where the adversary can see all intermediate results). Specifically, they demonstrate that if the data follows a normal distribution, DP-CGD of the convex equivalence enjoys utility guarantee of the order $O(1/\sqrt{n}\epsilon)$. They also provide experimental results to support their claims.

strengths:
Privacy analysis under the hidden state model is challenging for non-convex problems, as the privacy loss is typically intractable in such cases. The authors cleverly leverage recent findings that show certain non-convex problems can be reformulated as convex ones. Even though this work does not give general recipe for all non-convex problems, it is a first step towards privacy analysis under hidden state models for non-convex problems.

weaknesses:
- A limitation of this work, which perhaps coincides with its advantage, is that it offers a restricted solution for privacy analysis in non-convex problems. The approach still relies on tools for convex and smooth problems, meaning that only non-convex problems that can be reformulated as convex can be analyzed. However, determining whether a non-convex problem has a convex formulation is inherently challenging.

- The preliminary section lacks coherence and is somewhat difficult to follow. Although the key concepts are introduced, their relevance to the privacy analysis is less clearly explained.

questions:
1. In Figure 3, ReLU with DP-SGD outperforms DP-SGD and NosiyCGD for larger $\epsilon$. Is there any intuition for this phenomenon?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730240147191

thread_type:
official_review

<thread_object>
creator: reviewer_ahym

<content>
summary:
The paper investigates a hidden state threat model in differential privacy, where it assumes the adversary can only access the final model. By leveraging convex reformulation of ReLU networks and privacy amplification via iterative DP analysis, the paper presents a privacy-utility trade-off in the hidden state setting.

strengths:
The paper addresses an interesting problem in the differential privacy community. I am particularly intrigued by the transition from a two-layer neural network model to a convex formulation, which I have raised questions about below.

weaknesses:
- The writing of the paper could be improved, as several aspects are unclear. In my opinion, the paper's structure should be: In the hidden state setting, the authors aim to achieve privacy preservation through convex approximation and privacy amplification by iteration. Specifically:
  - For the DP algorithms, the authors use NoiseCGD.
  - For convex approximation, the ReLU output is rewritten as a set of diagonal Boolean matrices, and the transition from Eq(3.2) to Eq(3.3) is made. However, I lost track in section 3.3. Several definitions and lemmas, in my opinion, should be moved to the appendix.

- There is a grammatical error in lines 270-271.

- The conclusion primarily relies on previous results.

questions:
- In the hidden state setting, the authors claim that the adversary only accesses the final model. Does this mean only the final model is privatized? If not, how does this differ from the regular setting in terms of the results? Could you provide some explanations and insights?

- How should one understand the transition from Eq(3.2) to Eq(3.3)? Why does the hidden width $m$ disappear in Eq(3.3)? What is the significance of the range of $|D_x|$, even though it is related to rank, as mentioned in line 267?

- Regarding Theorem 4.1, what is $d_1$, and why is it needed? How do your results compare to DPERM with convex functions? I am confused by this result. Also, Theorem 4.1 pertains to Algorithm 1 (DP-SGD), but I am unsure if this is a typo or if I misunderstood, as I thought the authors were analyzing NoiseCGD.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730362380466

thread_type:
official_review

<thread_object>
creator: reviewer_jprt

<content>
summary:
This paper works on the hidden state threat model of differential privacy, which means the adversary only has access to the final trained machine learning model. The authors consider the model of two-layer Relu activate neural networks, which has not been studied under the hidden state threat model. The idea is to first relax the two-layer network to a stochastic convex program, then solve the relaxaztion with noisy cyclic mini-batch gradient descent. Experiment results show that the proposed method has similar performance as DP-SGD.

strengths:
This paper extends the study of the hidden state threat model  to non-convex models, which is novel and interesting.

weaknesses:
- The novelty seems to be limited. The major technical components, the (stochastic) convexification of 2-layer neural networks and privacy guarantee of NoisyCGD, are from previous works. This main result of this work seems to be a combination of the two components and feels incremental. Also, the paper claims that the proposed method can obtain similar privacy-utility trade-offs as DP-SGD, but actually there is no formal statement on the privacy-utility tradeoff. That is, in order to achieve $(\epsilon,\delta)$-DP in the hidden state threat model, how large the regularization parameter $\lambda$ and noise variance $\sigma^2$ we shall pick up. I do not follow how we can compare the theoretical results with DP-SGD.

- It is not clear how we shall interpret the experiment results. If I understand correctly, the hidden state threat model is a weaker threat model, because the intermediate states are not known to the adversary. So under the same privacy level, we shall need smaller noise and hence observe better utility. But the experiment result is that DP-SGD has similar or even better utility. Why is it the case? What is the advantage of introducing the hidden state threat model then?

questions:
- It is hard to distinguish existing results and new finds. For instance, Theorem 5.1 appears with neither reference nor proof. If it is known, please cite where it comes from.
- In Section 3.4 you explicitly mentioned about clipping the gradients. I am not sure if this will break the privacy guarantees of NoisyCGD. [1] discussed about this point and said "...in general, clipped gradients do not correspond to gradients of a convex loss, in which case our results (as well as all other works in the literature that aim at proving convergent privacy bounds) do not apply''. Can you explain a bit more on this?

[1] Altschuler, Jason, and Kunal Talwar. "Privacy of noisy stochastic gradient descent: More iterations without more privacy loss." Advances in Neural Information Processing Systems 35 (2022): 3788-3800.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730537087164

thread_type:
official_review

<thread_object>
creator: reviewer_vyiy

<content>
summary:
This paper investigates a privacy algorithm for the two-layer ReLU minimization problem by using a convex dual formulation and privacy amplification through iterative DP analysis.

strengths:
The technical approach appears largely sound (though I have not conducted a detailed verification). The core idea of transforming the two-layer ReLU network into a stochastic convex formulation to enable privacy analysis is interesting.

weaknesses:
Under the restricted setting of the two-layer ReLU network, it theoretically yields an improved utility-privacy tradeoff by resorting to a dual form of the original problem. However, its applicability is limited since the approach does not extend to more general non-convex formulations. I would expect papers in this area to provide implications for broader non-convex cases, an aspect that is missing here.

questions:
Can this method outperform the method of directly applying DP-SGD to a state-of-the-art (non-convex) neural network, in terms of utility-privacy tradeoff?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732626360698

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Rebuttal

comment:
We would like to thank all the reviewers for their constructive comments! 

Below, we have addressed most of the questions and comments individually. We have also uploaded an updated version of the paper with two major modifications:

* Adding a section to the appendix (Appendix A). We explicitly demonstrate that the strongly convex loss function we derive corresponds to the loss function of a GLM. Together with the results of Song et al. (2021), this shows the existence of another convex loss function whose gradients match the clipped gradients and that the privacy amplification by iteration analysis is applicable. This addresses the concern raised by reviewer JPrt regarding the validity of the privacy amplification by iteration analysis when clipping gradients.

* Adding a section in the appendix (Appendix J). We illustrate that, in our experimental settings, the state-of-the-art shuffling amplification upper bounds are worse than the privacy bounds of the Gaussian mechanism. This indicates that the results we obtain with NoisyCGD push the state-of-the-art in the privacy-utility trade-off of DP-SGD with disjoint batches. Adding this section is in response to reviewers who questioned the need for convex approximation and hidden state analysis when DP-SGD with the non-convex ReLU problem is competitive. As we also highlight in invidual responses, this is because it facilitates the analysis of other practically relevant algorithms, such as DP-SGD with disjoint batches (NoisyCGD). 

We have also made minor modifications based on the reviewers' feedback. These include adding references for future work in the conclusions section and clarifying that the theoretical utility bound, in addition to providing a classical DP-ERM convergence rate, incorporates the approximability of ReLU networks as the minimum loss in the bound approaches zero.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The reviewers generally agree that the paper has some merits but falls short of the acceptance threshold.  The main concerns are the limited novelty, lack of generalizability to broader non-convex cases, and unclear practical advantages compared to DP-SGD. 
  
Specifically, reviewers question whether the method can outperform DP-SGD in terms of utility-privacy tradeoff and whether it has broader implications beyond the two-layer ReLU network.  The authors' response, while acknowledging these limitations, emphasizes the practical value of their approach for DP-SGD with fixed disjoint batches of data (NoisyCGD), which is common in practice.  However, the reviewers seem unconvinced and still find the novelty and contribution insufficient for acceptance.