Convex Approximation of Two-Layer ReLU Networks for Hidden State Differential Privacy
Authors: Rob Romijnders
Antti Koskela
Venue: NeurIPS 2025 poster ()
Keywords: Differential privacy
DP machine learning
hidden state analysis
Primary area: general_machine_learning
TL;DR: We approximate ReLU networks for hidden-state DP analysis; the results on practical noisy cyclic GD are on par with 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. However, the current privacy analyses under this model are restricted to convex optimization problems, reducing their applicability to multi-layer neural networks, which are essential in modern deep learning applications. Notably, the most successful applications of the hidden state privacy analyses in classification tasks have only 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 2-layer ReLU networks trained with DP stochastic gradient descent (DP-SGD). This is achieved through a stochastic approximation of a dual formulation of the ReLU minimization problem, resulting in a strongly convex problem. This enables the use of existing hidden state privacy analyses and provides accurate privacy bounds also for the noisy cyclic mini-batch gradient descent (NoisyCGD) method with fixed disjoint mini-batches. Empirical results on benchmark classification  tasks demonstrate that NoisyCGD can achieve privacy-utility trade-offs on par with DP-SGD applied to 2-layer ReLU networks.

Convex Approximation of Two-Layer ReLU Networks for Hidden State Differential Privacy
Rob Romijnders University of Amsterdam
Antti Koskela Nokia Bell Labs
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. However, the current privacy analyses under this model are restricted convex optimization problems, reducing their applicability to multi-layer neural networks, which are essential in modern deep learning applications. Notably, the most successful applications the hidden state privacy analyses in classification tasks have only 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 2-layer ReLU networks trained with DP stochastic gradient descent (DP-SGD). This is achieved through stochastic approximation of dual formulation of the ReLU minimization problem, resulting in a strongly convex problem. This enables the use of existing hidden state privacy analyses and provides accurate privacy bounds also for the noisy cyclic mini-batch gradient descent (NoisyCGD) method with fixed disjoint mini-batches. Empirical results on benchmark classification tasks demonstrate that NoisyCGD can achieve privacy-utility trade-offs on par with DP-SGD applied to 2-layer ReLU networks.
1 Introduction
In differentially private (DP) machine learning (ML), the DP-SGD algorithm (see e.g., Abbdi et al. 2016) has become ubiquitous tool to obtain ML models with strong privacy guarantees. The guarantees for DP-SGD are obtained by clipping gradients and by adding normally distributed noise to the randomly sampled mini-batch of gradients. The parameters for the DP guarantee are then found by composition analysis of the iterative algorithm (see, e.g., Zhu et al. 2022).
One weak point of the composition analysis of DP-SGD is the assumption that the adversary has access to all the intermediate results of the training iteration. This assumption unnecessarily strict as in many practical scenarios only the final model needs to be revealed (Andrew et al.) (024). Another weakness is that DP-SGD requires either full batch training or random subsampling. Both are computationally not favourable, as full batch usually does not fit in memory and random subsampling implies an unbalanced use of compute resources and increased implementation complexity (Chual et al. 2024a). In contrast, for noisy eyclic gradient descent (NoisyGD) with disjoint mini-batches the compute is balanced between mini-batchi and can be implemented efficiently. Having high privacy-utilin ML models trained with NoisyCGD would give alternative for DP-SGD that is more practical and efficient to implement (Chua et al. 2024a).
The so-called hidden state threat model of DP considers releasing only the final model of the training iteration. Existing (e, 5) -DP analyses in the literature are only applicable for convex problems such as logistic regression which is the highest performing model considered in the literature (see, e.g.. Chourasia et al.] 2021 Bok et al. 2024). When training models with DP-SGD, however, one quickly finds that the model performance of commonly used convex models is inferior compared to neural networks. A natural question arises whether convex approximations of minimization problems for
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

multi-layer neural networks can be made while preserving model performance under privacy. This work explores such an approximation for the two-layer ReLU neural network. We build on the findings of Pilanci and Ergen (2020), which demonstrate the existence of convex dual formulation for the two-layer ReI.U minimization problem when the hidden layer has sufficient width.
The privacy amplification by iteration analysis for convex private optimization, introduced by Feldman et al. (2018), provides privacy guarantees the hidden state threat model. However,
these anal analyses yses (Sordello et al. 202T Asoodeh et al. 2020 Chourasia et al.) 2021; Altschuler and
Talwar 2022) remain challenging to apply in practice, as they typically require a large number of
training iterations to obtain tighter DP guarantees than those of DP-SGD, Chourasia et al. (2021)
improve this analysis using Rényi DP for full- training with DP guarantees, while Ye and Shokri (2022) offer a similar analysis for shuffled mini- batch DP-SGD. Recently, Bokk et al. (2024) provided an J-DP analysis for a class of algorithms, which we will leverage to analyze NoisyCGID.
Our main contributions are the following:
By integrating two seemingly unrelated approaches, convex reformulation of ReLU networks and the privacy amplification by iteration DP analysis, we show that it is possible to obtain similar privacy-utiiity trade-off's in the hidden state threat model of DP as by applying DP-SGD to two-layer ReLU networks and using well- composition results.
We provide approximations for the convex reformulation to facilitate DP analysis and show that the resulting strongly convex model has the required properties for hidden state analysis.
We give the first high-priiih privacy-utility trade-off results for image classification tasks using a hidden state DP analysis. In particular, we present results for NoisyCGD with disjoint mini- mini-batches. This allows for more practical applications of DP ML.
We run a theoretical utility analysis of gradient descent with DP guarantees when applied to the convex approximation, in the context of the random data model.
1.1 Further Related Literature
Differentially private machine learning has been extensively studied in recent years. The most widely used approach is DP-SGD (Abadi et al. 2016), which clips and adds noise gradients during training. Several works have analyzed and improved DP-SGD through techniques such as adaptive
clipping (Andrew et al. 202T), better composition analyses (Dong al., 2022; Koskela et al.
2020
Zhu et al.] 2022 Gopi et al. (021]. or privacy amplification by iteration (Feldman et al.]
2018).
For convex problems, alternative approaches include sufficient statisties perturbation (Wang 2018
Amin et al. 2023), objective perturbation (Chaudhuri et al. 201T), and output perturbation [Wu
ct al. 2017). Most prior work focuses on the standard DP definition rather than hidden state DP. Another alternative to DP-SGD is the Differentially Private Follow-the Secllo--thh-Reguaariie ReguRReezzul--eeeeeo Leader (Kairouz al.] 2021), but it comes with significant additional memory and compute cost due to sampling of correlated noise from a matrix mechanism, and potentially significant communication overhead in the federated learning setting. A recent line of work considers DP guarantees for DP-SGD with
disjoint batches. Chua et al. (2025) and Choquettee CChto et al.) (2025) use Monte Carlo methods to estimate privacy guarantees under the so-called balls-and-Be -nd--ins sampling, where Poisson sampling assigns data points to disjoint batches. However, these simulations are computationally intensive and do not lead to provable upper bounds on DP parameters. Feldman and Shenfeld (2025) provide provable bounds for generalization of this scheme, though their method also results in randomly sized batches. Thus, existing analyses do not accommodate fixed-size batches and, in particular, unshuffled data, further motivating our approach, which yields high-utility convex models for which NoisyCGD can be analyzed accurately.
Our work builds on recent advances in convex approximations of neural networks. The connection between two-layer ReLU networks and convex optimization was established by |Bengio al. (2005); Bach (2017) and further developed by Pilanci and Ergen (2020). Several works propose methods to train neural networks through convex optimization (Ergen and Pilancil 2020 Ergen et al. 2023).
However, the privacy implications of these convex formulations have not been thoroughly explored before our work. The closest related work is (Kim and Pilanci| 2024), which analyzes connections between stochastic dual forms and ReLU networks but does not consider privacy.

---

2 Preliminaries
We denote a dataset containing n data points as D (21,..., 2n). We say D and D' are neighboring datasets if they differ in exactly one element (denoted as D ~ D'). A mechanism M X + O is (e, 6) if the output distributions for neighboring datasets are always () indistinguishable (Dwork et al., 2006).
Definition 2.1. Let E 2 0 and 8 E [o, 1]. Mechanism M X' - O is (c, 6)-DP if for every pair of neighboring datasets D D' and for every measurable set C C.O.
P(M(D) E) S e P(M((DD)) E E)
We call M tightly (e, 6)-DP, if there does not exist 8' å such that M is (e, 8'D-D.
The DP guarantees can alternatively be described using the hockey-stick divergence. For >> 0 the hockey-stick divergence Ha from a distribution P to distribution Q defined H, (PIIQ) [ a Q(t), 0} dt. The (s, DD guarantee, in Def. 2.1 can be characterized using the hockey-stick divergence: we can bound the divergence H (A (MD)) obtain accurate A(e) --boudds. We also refer to (M) == maxD Hes (M(Di)IM((D) as the privacy profile of mechanism M.. To accurately bound the hockey-stick divergence of compositions, we need to so-called dominating pairs of distributions.
accurately, we also
Definition 2.2 (Zhu et al. (022). A pair of distributions (P, (P, is a dominating pair of distributions for mechanism M(D) for all neighboring datasets and D' and for all a > O,
Ha(M(D)IM(D)) S (PlIQ)..
If the equality holds for all a for some D ~ D', then (P,Q) is tightly dominating pair of distributions. We get upper bounds for DP-SGD compositions using the dominating pairs of distributions using the following composition result.
Theorem 2.3 (Zhu et al. 2022). If (P, Q) dominates M and (P', dominates M', then (P x P". Q x Q') dominates the adaptive composition M o M'.
To convert the hockey-stick divergence from P x P' to Q Q' into an efficiently computable form, we consider so called privacy loss random variables (PRVs) and use Fast Fourier Technique- based methods (Koskela et al. 202 Gopi et al. 2021 to numerically evaluate the convolutions appearing when summing the PRVs s and evaluating (()) ) for the compositions.
Gaussian Differential Privacy. For the privacy accounting of the noisy cyclic mini-batch GD, we use the bounds by [ook et al. (2024) that are stated using the Gaussian differential privacy (GDP). Informally speaking, mechanism M is μ-GDP, μ 0, if for all neighboring datasets the outcomes of M are not more distinguishable than two unit-variance Gaussians μ apart from each other (Dong al. 2022). We consider the following formal characterizatton of GDP.
Lemma 2.4 (Dong al. 2022 Cor. 2.13). mechanism M H-GDP if and only it is (s, D)-D for all e 2 0, where
(-e 1 2) e
(_E
1
((e)
1 2
2.1 DP-SGD with Poisson Subsampling
One iteration of DP-SGD with Poisson subsampling is given by
0 0 = 0, - (
E.en, Cip(V
where C. > 0 denotes the clipping constant, clip(:, C) the clipping function that clips gradients to have the 2-norm at most C, L the loss function, A the model parameters, the learning rate at iteration j. Bj the mini-batch at iteration j sampled with Poisson subsampling with the subsampling ratio b/n, the expected size of each mini-batch and Z₁ ~ NO, c²0² 8 Ia) the noise vector.
We adopt the substitute neighborhood relation and apply the result of Lebeda al. (024)):
3

---

Lemma 2.5 Lebeda et al. 2024). Suppose pair of distributions (P,Q) is a dominating pair of distributions for a mechanism M and denote the Poisson subsampled mechanism M = S Poisson where S Poisson denotes the Poisson subsampling with subsampling ratio Then, under the n-eiihhourring relation, the pair of distributions (P. Q), where P = (1-9) (2) q- + (M111, is dominating pair of distributions for M.
and Q q) (N(00 02)
Combined with Lemma 2.3 and numerical accountants, this yields tight (c, 6) bounds for DP-SGD with Poisson subsampling under the substitute neighborhood relation.
2.2 Guarantees for the Final Model and Noisy Cyclic Mini-Batch GD
We next consider privacy amplification by iteration (Feldman et al., 2018). which gives privacy guarantees for the final model of the training iteration. Recent results by Bok et al. (2024) are applicable the noisy cyclic mini-batch gradient descent (NoisyCGD) for which one epoch of training is described by the iteration:
00 (t Sen, Vol(O +2,)
where Z, ~ (O, L2) and the data D is divided into disjoint batches Bi...., BR. each of size b. The analysis by Bok et al. (2024) also considers the substitute neighborhood relation of datasets. A central element for the DP analysis the gradient sensitivity:
Definition 2.6. A loss function family F has gradient sensitivity if s.ge [V Vgll S L.
For example, for a family of loss functions of the form h2 +r, where hi's 's are L-Lipschitz loss functions and r is regularization function, the sensitivity equals 2L. We will use the following result to analyse the DP guarantees of NoisyCGD. Recall that a function is 3-smooth if V is 3-Lipschitz, and it is A-strongly convex if the function g(x) f(x) - - || is convex.
Theorem 2.7 (Bok et al. 2024, Thm. 4.5). Consider >-strongly convex, 3-smooth loss functions with gradient sensitivity L. Then, for any 1j (0, B). NoisyCGD is μ-GDP for
L
1 ④ 1 ((E-)) (1- (+ c (EEE1)
1 2h
bo
where k = n//, c= maxf/1 m711 1 m and E denotes the number of epochs.
We could alternatively the RDP analysis by Ye and Shokri (022). However, as also illustrated by the experiments of Bok et al. 2024),, the bounds given by Thm. 2.7 lead to slightly lower (e. 8)-DP
bounds for NoisyCGD. To benefit from the privacy analysis of Thm. 2.7 for NoisyCGD, we add an L2 Lg-regularization term with coefficient 5. This makes the loss function X-strongly convex.
Finding suitable hyperparameter values for the learning rate 77 and regularization parameter is complicated by two aspects. The larger the regularization parameter À and the learning rate 1) are, the faster the model 'forgets' the past updates and the quicker the e-values converge. This is reflected the GDP bound of Thm. 2.7 in the constant which generally equals
1.2-
NolayCGID, A 5.4- 10-6
n/ To benefit from the bounds of Thm. 2.7 the product π7λ should not be too small. Altenaaively, when y7 is too large, the 'orgettiigg affects the model performance. We experimentally observe that the plateauing of the model accuracy and privacy guarantees occurs approximately simultaneously.
NolayOGD, 1 1-
0.4-
NoIayOGID v 2-A22-100 2-
DP-SGD
0.2
100
200
300
400
Epecks
Figure 1: Values of the product of the learning rate n and the Lezregularization constant that lead to tighter privacy bounds for the final model using Thm. 2.7 compared to the whole sequence of updates using the DP-SGD analysis. Here n 6 10 1000, o 15.0 and 10-5
Figure I illustrates the privacy guarantees of NoisyCGD for a range of values for the product 17À. The (s, 0)DP guarantees given by

---

Thm. b.cemmm smaller than those given by the Poisson subsampled DP-SGD with an equal batch size 1000 when 15.0 and training for 400 epochs. For a given learning rate 77, we can always adjust the value of X to have desirable (s, 6)-DP guarantees. To put the values of Fig. [ into perspective, in experiments we observe that 7/À 2 10-1 is experimentally found to affect the model performance already considerably whereas 7/ = 1 10-1 affects only weakly.
Computational advantages of NoisyCGD. NoisyCGD offers significant computational benefits over traditional DP-SGD. The standard DP-SGD requires Poisson sampling where each sample is included in batch with an independent probability, leading to variable batch sizes. This variability creates practical challenges: For a target physical batch size of 256, one typically needs to set the expected batch size 230 handle size variations, resulting in an 1 % throughput reduction. Additionally, approximately 4% of batches exceed the physical limit and must be processed separately as stragglers. This further reduces efficiency and increases the engineering complexity of experimental code.
While Chua et al. (2024b) proposed truncating oversized batches and accounting for this in the ò parameter of (e, 0D-P, this approach also impacts throughput. For example, with physical batch size of 256, = 8, 8 = 10-6, and 10 training epochs, the expected batch size must be reduced to 166 according to their theorem. This constitutes 35% loss of throughput. In contrast, NoisyCGD maintains constant batch sizes (except for possibly the final batch). This enables simpler implementation in code and higher throughput while preserving privacy guarantees.
3 Convex Approximation of Two-Layer ReLU Networks
This section derives the strongly convex approximation of the 2-layer ReLU minimization problem and shows that the derived problem is amenable to privacy amplification by iteration analysis. Without loss of generality, we consider a I-dimensional output network (e.g.. binary classifier), which can be extended to multivariate output networks later (see also Ergen et al. 2023).
3.1 Convex Duality of Two-layer ReLU Problem
Consider training ReLU network (with hidden-width m)) f Rd + R PPilanci and Ergen 2020).
f(x) 5=
E s(u) x)ay-
(3.1)
The weights are u, E RRd, i E [m] and a E Rmm The ReLU activation function is x(() = max mnax(0.4 (}. For vector x, o is applied element-wise, i.c. o(z), Φ(z,).
Suppose the dataset D consists of n tuples of the form 2; = (I, M.). o2 E Rd. y: E R, for i E [m]] Using the squared loss and I-zregularization with regularization constant À >> O, the 2-layer ReLU minimization problem can be written as
min (Mc ps
1
Σn me
((Xu)a; V/
A
(11u +a)),
(3.2)
2
2 1=1
where X E R denotes the matrix of the feature vectors, i.e., X (x] [nl and E R denotes the vector of labels.
The convex reformulation of the ReLU problem 3.2 is based on enumerating all the possible activation patterns of Φ(Xu) u E Rd. The set of activation patterns that a ReLU output Φ (X)) can take for data feature matrix X Ruxd described by the set of diagonal boolean matrices
Dx {A (1 2 0)) u RR).
(3.3)
where for E [n]. (1(Xu 2 0)2 = 1, if (X=); 2 0 and 0 otherwise. The number of regions in partition of R by hyperplanes that pass through the origin and are perpendicular the rows of X is [Dx]. We have by Pilanci and Ergen (020)
|Dxl < 2r (((-1)) where rank(X).
Notice that Dx defined in Eq. (3.3) the set of all possible boolean matrices, where each boolean matrix corresponds to a different pattern of ReLU activations for the features of the dataset (the rows of the matrix X E RRnxd). Thus, the bound for [Dx] is bound for the number of possible hyperplane arrangements, and thus it is only determined by the feature matrix X.
5

---

Let the number of activation patterns be Dx M, and denote Dx = {Ai...., Aart. Let A > 0. The parameter space can then be partitioned into convex cones Vi....: Vas. where V; { u F (2A, X)Xx 2 0.. We consider the following convex optimization problem with group 1 regularization:
min Pa
1 2
Σ KENA A;X(m; w;) - + Σ (E[M (1lusl12 + (|wsll2)
(3.4)
subject to 0s Wa E V; for all i E [M]. i.e., (2),-1)Xr; 2 0 and (2A, 1) N); 2 0 for all i E [M]
Interestingly, for sufficiently large hidden width m, the ReLU minimization problem (3.2) and the convex problem (3.4) attain the same minimal value (see Pilanci and Ergen 2020 Thm. 1). Moreover, Pilanci and Ergen (2020) show that the optimal ReLU network weights can be recovered from the solution of the convex problem (34)). Hence, for large enough m, the convex problem can be viewed equivalent convex reformulation of the ReLU problem (3.2). where {er and {w act as dual-like variables. Subsequent work, such as Mishkin et al. (2022), extends this equivalence to general convex loss functions L. For simplicity,
restrict our discussion to the squared loss.
We also note that similar convex formulations have been developed for two-layer convolutional networks (Bartan and Pilanci 2019) and for multi-layer ReLU networks (Ergen and Pilanci 2021).
3.2 Stochastic Approximation
Since |Dx] is generally an enormous number, stochastic approximations to the problem (3.4) have been considered (Pilanci and Ergen 2020; Wang et al.) [2022] Mishkin et al.] [2022] Kim and Pilanci 2024). Vectors u, ~ N(, Ia). diagonal matrices Ai,.... Ap, A; diag(1 (Xu;" 2 0)), and the problem (3.4) is replaced by
Pl. P & M, are then sampled randomly to construct the boolean
min 12,
Σ i=
A:X(1; w;), + +
(Ileslla + (|wa)1a)
(3.5)
such that for all i E [P] :4 E V;, i.e., (2A, (2A,-7)x: T)xw; 2 0. and (2A; T)Xe; 2 0 for all i E [P] These constraints, however, are data-dependent, which makes private learning of the problem (3.5) difficult. Moreover, the overall loss function given by Eq. 3.5 is not generally strongly convex. This prevents using privacy amplification results such as Theorem 2.7 for NoisyCGD, We thus consider a strongly convex problem without any constraints and with squared regularization term.
3.3 Stochastic Strongly Convex Approximation
Motivated by the needs of the DP analysis and the formulation given in (Wang et al. 2022). consider global minimization of the loss function
((v,X,))
_ Σ 1=1 (1, U1).
(3.6)
ni
with
((v, = 2 Σ (Ai)sfzJu Us - yU
P + 2 E
1lul (Ad)s = 1[x u, 2 0), (3.7)
where {u,),_1 U/ Rdd for i E [P] denote the learnable parameters. We note that due to the convention of the literature, the regularization is added term-wise (Bok et al. 2024). The diagonal boolean matrices A!...., Ap R"*x are again constructed by taking first P L..dd samples W1, up, Us ~ A (0, Ia), and then setting the diagonals of A (Az) = max (0, sign(x) u:)).
The Model at Inference Time. Having a sample x E Rd at inference time, one uses the P vectors U1..... ...., up that were used for constructing the boolean diagonal matrices A,, i E [P] during training. The prediction is carried out similarly using the function g(æ, v) = E 11 (u,J x 2 0) x c.
Practical Considerations. In the experiments, we use the cross cross-entropy loss instead of the mean squared error for the loss function f. For K K-dimensional outputs and labels, we employ K independent linear models in parallel, each predicting one output dimension. The resulting model has parameter dimensionality d K, where d the feature dimension and P the number of randomly chosen hyperplanes.

---

3.4 Meeting the Requirements of DP Analysis
In Eq. (3.7p each loss function f(v. 3y). j [n]. depends only on the data entry (z 8j). By clipping the data sample-wiss wise gradients V.h(v, Mj), where h(u, 2z U₁)
(A))))) 04 y/ 1|: the loss function becomes 2T.-seneitive (see Def. 2.6 Appendix shows that the loss function E(U, 22,,,,,,), U/4) is a loss function of a generalized linear model and thus we are allowed to use the analysis Bok et al. (2024) when clipping the gradients since then the clipped gradients are gradients another convex loss (Song et al. 2021). For the DP analysis, we must also analyze the loss function's 's convexity properties (3.7).
We have the following Lipschitz bound for the gradients.
Lemma 3.1. The gradients of the loss function {(v,T,.)) given in Eq. 3.7 are 3-Lipschitz continuous for 3 = ||= 112 + X.
Due to In-regularization, the loss function (3. is X-strongly convex. The properties of X- strong convexity and 3-smoothness are preserved when clipping the sample-wise gradients v.h(v,zj, 25,3;) (Section E.2, Redberg et al.) 2024).. Therefore, the DP accounting Thm. 2.7 is applicable with the same convexity parameters when clipping the gradients V,h(v, (z.
Theoretical Analysis
From a theoretical standpoint, convex models are advantageous over non-convex ones in private optimization. State-of-the-art empirical risk minimization (ERM) bounds for private convex optimization are of the order 0 v en vP), where is the number of training data entries, p the dimension of the parameter space and the DP parameter (Bassily et al. 2019). contrast, the bounds for non-convex optimization, which focus finding stability points, much worse, such as 1
O( 1773 + (em)a75) Bassily et al. 2021) and O
p2// (ex))73
(Arora et al.
2023 Lowy et al. 2024
We consider utility bounds with random data for the problem (3.7 The random data model is also commonly used in the analysis of private linear regression (see, e.g., Varshney et al. 2022).
Leveraging classical DP-ERM results, we derive utility bounds that are tighter than those obtainable for 2-layer ReLU networks via non-convex optimization. In addition to the convexity benefits of DR-ERM, we utilize the approximability of our convex models: with enough random hyperplanes, the global minimum L("", D) goes to zero with high probability.
4.1 Utility Bound for the Convex ReLU Approximation in the Random Data Model
Recently, Kim and Pilanci (2024) have given several results for convex problems under the assumption of random feature data, T.e., when E IR" is fixed and X.j ~ (0, 1) i.i.d. Based on their results, using P= O(n log n)/ hyperplane arrangements, the stochastic objective in (3.7) attains a global minimum of zero with high probability. Consequently, standard DP-ERM bounds yield the result of Thm. 4. In future work, it will be interesting to see whether techniques from private linear regression (Liu al. 2023 Avella-Medina et al. 2023 Varshney al. 2022 Cai al. 2021 could be used to eliminate the assumption of bounded gradients. Notice that Thm. 4.1 |4.1eeexiii exhibits feature
dimension- dimenssonninneppedeene unlike existing DP-SGD bounds for the linear regression under the random data assumption that are Ō( (Ar)) (Thm. 1.2. Brown et al. 2024).
Theorem 4.1. Consider the random data model where y E R" and the elements of the data matrix X E Roxd are i.i.d. distributed as Xs; ~ (0,0 1) and consider applying the private gradient descent (repeated from literature in Alg. 1 to the strongly convex loss (3.6) with P ( log n) /) hyperplane arrangements, and assume That the gradients are bounded by constant L > 0. Let the ratio e n
à 2 be fixed. For any > O, there exists dj such that for all d 2 d1, with probability at
least 1 7 (2 (with Ô omitting the logarithmic factors)
L(B D) D)
VT=E
7

---

Remark 1. In Thm. 4.1 we assume that the ratio с = nı/d stays constant in order to be able to use the results of Kim and Pilanci (2024). One motivation for the assumption e z comes from having a similar setting as Brown et al. (2024) since we make an explicit comparison to their utility bounds, where the dependency on the feature dimension d appears. Brronn et al. (2024) assume that (Q(d) (Thm. 1.2, Brown et al. 2024), which is implied by the assumption n/ d 1. The results are in this sense comparable, whereas with the assumption n/d < there is no implication in anyy direction. As our Thm. 4.1 indicates, it is possible to get rid of the dependency when training our proposed model with DP-SGD, and in this sense, our approach is better in the random data model than the private linear regression analyzed by Brown et al. (2024). Notice also that in our Thm. 4.1 there is no randonness assumption on the label vector y E R" unlike
the parameter
in (Thm. 1.2, Brown al. 2024).
Another motivation for the assumption n/ n/d2 1, or rather requirement, comes from the matematical analysis: the current results by Kim and Pilanci (2024) that we use have to assume n/d 2 for the model loss to have, with high probability, a unique zero global minimum for every possible label vector y with limited number of random hyperplanes P = On log nggg. If we assume n/dd < 1, in a sense the problem becomes easier since the feature matrix X becomes column rank deficient with high probability. Then, there also can be infinite number of global minimizers. Moreover, the DP- SGD convergence results by Bassily et al. (2014) and Talwar et al. (2014). which we use in our analysis, do not require unique global minimizer. It is interesting question for future work how to include the case n/d < in the utility analysis.
5 Experimental Results
We compare the methods on standard image classification benchmarks: MNIST (LeCun et al. 1998), FashionMNIST (Xiao al.) 2017). and CIFARIO (Krizhevsky et al. 2009). The MNIST dataset has training dataset of 6 10 samples and a test dataset of 10 samples. CIFARIO 10 has training dataset size of 5 10 and a test dataset of 10a samples. All samples in MNIST datasets are 28 x 28 size gray-level images, and in CIFAR 10 32 32 color images (with three color channels each). We compare three alternatives: DP-SGD applied to 2-layer ReLU network, DP-SGD applicd to the stochastic convex model (3.6) without regularization (A 0), and NoisyCGD applied to the stochastic convex model (3.6) with À > O. We use the cross-entropy loss for all the models considered. To simplify the comparisons, epochs. We compare the results on two noise levels, o = 5.0 and a = 15.0, which correspond to privacy parameter e 1.33 and 4.76 d = 10 5 In all experiments, the model parameters always initialized to zero.
set the batch size to 1000 for all methods and train them for 400
Although 2-layer networks with tempered sigmoid activations (Papernot et al. 2021 would likely yield improved results, we focus on ReLU networks as baselines for consistency. This allows us to compare the methods in the context of ReLU-based architectures and will not affect our main finding. which is that we can find improved models for the hidden state privacy analysis. Unlike [Abadi] et al. (2166), we do not use pre-trained convolutive layers for obtaining higher test accuracies in the CIFARIO 10 experiment, as we experimentally observe that the DP-SGD trained logistic regression gives similar accuracies the DP-SGD trained ReLU network. We consider the much more difficult problem of training the models from scratch using the vectorized CIFAR1O images as features.
We also compare the hyperparameter tuning under differential privacy and describe this in Appendix G The experimental results in this section use the hyperparameter from the private tuning process. The hyperparameter tuning of NoisyCGD is simplified by the fact that the bound of Thm. (2.7) depends monotonously on the parameter e = 1- 17- A. If the hyperparameters b and noise scale a are fixed, fixing the GDP parameter μ also fixes the value of Thus, grid of learning rate candidates also determines the values of X's. The hyperparameter grids are noted in Appendix G.I
Baselines. As the stochastic approximation yields convex problem, we compare, a baseline, to a linear regression model that uses the same features. In contrast to the iterative methods, we use the Sufficient Statistics Perturbation method, which is a one-step solution (SSP[Amin et al. (223).. SSP a state of the art model for linear regression with Differential Privacy guarantees, and the details are provided in Appendix H. We consider three sets of features: a) the stochastic approximation features in the GLM formulation of Equation (37 (Convex approx.), b) the activation patterns of Equation 3.3 (Random ReLU), and c) Random Fourier Features of the input images Rahimi and Recht 2007
8

---

Table 1: A comparison of model accuracies vs. e-values. The iterative methods generally score better than SSP and have comparable accuracy, which shows a high-utility result for hidden-state privacy analysis of 2-layer neural network. The results are the mean accuracy among five random restarts.
MNIST
CIFAR-10 8 8 1.33
8
1.33
8
4.76
6 = 4.76
Sufficient Statistics Perturbation (Convex Approx.)
51.911.1
11. 17.0
23.3
Sufficient Statistics Perturbation (Random ReI.U)
52.5+0.9
65.6
19.3
25.9+0.3
Sufficient Statistics Perturbation (RFF)
64.1
77.4
21.3+0.5
28.5+0.3
DP-SGD + Convex Approximation
93.1
94.9
41.510.2
45.510.2
DP-SGD + ReLU
91.7
94.3=0.1
42.5
47.0+0.2
NoisyCGD + Convex Approximation
92.4
94.4
41.0
45.4
Main Results. Figures and 3 show the accuracies of the models along training of 400 epochs for the MNIST and CIFAR TO dataset. The results for FashionMNIST are in Appendix []] The figures also include the accuracies for the learning rate-optimized logistic regression models. We observe that the proposed convex model significantly outperforms logistic regression, which has been the most accurate model considered in the literature for hidden state DP analysis. The hyperparameters for this experiment were found with Differentially Private hyperparameter tuning (Appendix G
Figure 2 shows that the convexification helps in the MNIST experiment: both DP-SGD and the noisy cyclic mini-batch GD applied the stochastic dual problem lead to better utility models than DP-SGD applied to the ReLU network. Notice also that the final accuracies for DP-SGD are not far from the accuracies obtained by Abadi et al. (2016) using a three-layer network for corresponding e-values which can be compared using the fact that there is approximately multiplicative difference of 2 between the two relations: the add/remove neighborhood relation used by (Abadi et al. 2016 and the substitute neighborhood relation used in work.
The results of Figures 2 3 and Section are averaged over five trials. The error bars on both sides of the mean values indicate 1.96 times the standard error. In all experiments, we set 5 = 10-5.
The proposed method is also compared to non-iterative baseline methods. Table compares NoisyCGD and DP-SGD against Sufficient Statistics Perturbation on random and non-linear features. For each dataset and privacy setting, even the best linear regression model has lower accuracy than any of the iterative methods. This shows that iterative methods for non-linear models can achieve higher accuracy, and we believe that NoisyCGD is an important step this direction.
MNIST (a 5.0)
MNIST 15.0)
0.92
Accurory
Test Accurey
0.90
0.90
0.88
Couvex Model, DP-SGD
Convex Model, DP-SGD
0.88
Convex Model, NoisyOGD
0.86
Convex Model, NoisyCGD
ReLU Network. DP-SGD
ReLU Network, DP SGD
Logistic Regression, DP-SCD
Logistic Regression DP-SGD
0.96
0.84
0.2
0.4
0.6
0.8
1.0
Figure 2: MNIST: Test accuracy versus the spent privacy budget e, when each model is trained for 400 epochs. NoisyCGD and DP-SGD generally have comparable performance for the 2-layer ReLU network and much higher accuracy than logistic regression.

---

CIFAR-10 (a=5.0)
CIFAR-I0 (a=15.0)
0.473
0.125
0.450
0.400
Test Acmray
Tost Accuracy
0.375
0.400
0.350
0.375
0.325
Couvex Model, DP-SGD
Convex Model, DP-SGD
Convex Model, NolsyOG
0.300
Convex Model, NoisyOGD
0.350
ReLU Network, DP:SGD
ReLU Network, DP-SGD
0.325
Logistic Regression, DP-SGD
0.275
Logistic Regression, DP-SGD
2
3
0.2
0.4
0.6
1.0
1.2
Figure 3: CIFARIO Test accuracy versus the spent privacy budget e, when each model is trained for 400 epochs. NoisyCGD and DP-SGD generally have comparable performance for the 2-layer ReLU network and much higher accuracy than logistic regression.
6 Conclusions and Outlook
We have shown how to privately approximate the two-layer ReLU network, and we have given the first high privacy-utility trade-off results using the hidden state privacy analysis. In particular, we have provided results for the noisy cyclic mini- nani-batch GD, which is more suitable for practical applications of private ML model training than variants of DP-SGD that carry out random subsampling each iteration. Experimentally, on benchmark image classification datasets, the results for the convex problems have similar privacy-utility trade-off's as those obtained by applying DP-SGD for 2-layer ReI.U network and using the composition analysis. An interesting task for future research to obtain hidden state privacy guarantees for 'deeper' neural networks, for example, by developing convex models that approximate deeper neural networks, including those with convolutional layers (Ergen and Pilanci 2020) and different activation functions (Ergen et al. 2023).
References
Abadi, M., Chu, A., Goodfellow, I., McMahan, H. B., Mironov, I., Talwar, K., and Zhang, I.. (2016). Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308-318.
Altschuler, J. and Talwar, K. (2022). Privacy of noisy stochastic gradient descent: More iterations without more privacy loss. Advances Neural Information Processing Systems (NeurIPS). 35:3788-3800.
Amin, K., Joseph, M., Ribero, M., and Vassilvitskii, S. (2023), Easy differentially private linear regression. In International Conference on Learning Representations (ICLR).
Andrew, G., Kairouz, P., Oh, S., Oprea, A., McMahan, H. B., and Suriyakumar, V. M. (2024). One-shot empirical privacy estimation for federated learning. In International Conference on Learning Representations (ICLR).
Andrew, G., Thakkar, O., McMahan, B., and Ramaswamy, (2021). Differentially private learning with adaptive clipping. Advances in Neural Information Processing Systems (NeurIPS).
Arora, R., Bassily, R., González, T., Guzmán, C. A., Menart, M., and Ullah, E. (2023). Faster rates of convergence stationary points in differentially private optimization. In International Conference on Machine Learning (ICML), pages 1060-1092. PMLR.
Asoodeh, S., Diaz, M., and Calmon, F. P. (2020). Privacy amplification of iterative algorithms via contraction coefficients. In 2020 IEEE International Symposium on Information Theory (ISIT), pages 896-901. IEEE.
Avella-Medina, M., Bradshaw, C., and Loh, P.-.. (2023). Differentially private inference via noisy optimization. The Annals of Statistics, 5155)220772002.
10

---

Bach, F. R. (2017). Breaking the curse of dimensionality with convex neural networks. The Journal of Machine Learning Research (JMLR).
Bagdasaryan, E., Poursaeed, O., and Shmatikov, V. (2019). Differential privacy has disparate impact on model accuracy. In Advances Neural Information Processing Systems (NeurIPS).
Bartan, B. and Pilanci, M. (2019). Convex relaxations of convolutional neural nets. In ICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 1928-4932. IEEE
Bassily, R., Feldman, V., Talwar, K., and Guha Thakurta, A. (2019). Private stochastic convex optimization with optimal rates, Advances in Neural Information Processing Systems (NeurIPS), 32.
Bassily, R., Guzmán, C., and Menart, M. (2021). Differentially private stochastic optimization: New results in convex and non-convex settings. Advances Neural Information Processing Systems (NeurlPS), 34.
Bassily, R., Smith, A., and Thakurta, A. (2014). Private empirical risk minimization: Efficient algorithms and tight error bounds. In Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, FOCS 14, pages 464-473, Washington, DC, USA. IEEE Computer Society.
Bengio, Y., Roux, N. L., Vincent, P., Delalleau, O., and Marcotte, P. (2005). Convex neural networks. In Advances Neural Information Processing Systems (NeurIPS).
Bok, J., Su, W. J., and Altschuler, J. (2024). Shifted interpolation for differential privacy. In International Conference on Machine Learning, pages 4230 4266. PMLR.
Brown, G. R., Dvijotham, K. D., Evans, G., Liu, D., Smith, A., and Thakurta, A. G. (2024). Private gradient descent for linear regression: Tighter enror bounds and instance speciffc uncertainty estimation. In Forty-first International Conference on Machine Learning.
Cai, T. T., Wang, Y., and Zhang, L. (2021). The cost privacy: Optimal rates of convergence for parameter estimation with differential privacy. The Annals of Statistics, 49(5):2855-2850.
Chaudhuri, K., Monteleoni, C., and Sarwate, A. D. (2011). Differentially private empirical risk minimization. The Journal of Machine Learning Research (JMLR), 12:1069-11
Choquette-Chon Choo, C. A., Ganesh, A., Haque, S., Steinke, T., and Thakurta, A. (2025). Near exact privacy amplification for matrix mechanisms. In International Conference Learning Representations (ICLR).
Chourasia, R., Ye, J., and Shokri, R. (2021). Differential privacy dynamics of langevin diffusion and noisy gradient descent. Advances in Neural Information Processing Systems (NeurIPS), 34.
Chua, L., Ghazi, B., Harrison, C., Kamath, P., Kumar, R., Leeman, E. J., Manurangsi, P., Sinha, A., and Zhang, C. (2025). Balls-and-bint sampling for DP-SGD. In The 28th International Conference Artificial Intelligence and Statistics.
Chua, L., Ghazi, B., Kamath, P., Kumar, R., Manurangsi, P., Sinha. A., and Zhang, C. (2024a). How private are DP-SGD implementations? In International Conference on Machine Learning (ICML).
Chua, L., Ghazi, B., Kamath, P., Kumar, R., Manurangsi, P., Sinha, A., and Zhang, C. (2024b). Scalable DP-SGD: Shuffling vs. poisson subsampling. In Advances in Neural Information Processing Systems (NeurIPS).
Dong, J., Roth, A., and Su, J. (2022). Gaussian differential privacy. Journal of the Royal Statistical Society Series B.
Dwork, C., McSherry, F., Nissim, K., and Smith, (2006). Calibrating noise to sensitivity in private data analysis. In Proc. TCC 2006. Springer Berlin Heidelberg.

---

Ergen. T., Gulluk, H. L, Lacotte, J., and Pilanci, M. (2023). Globally optimal training of neural networks with threshold activation functions. In International Conference on Learning Representations (ICIR)..
Ergen, T. and Pilanci, M. (2020). Training convolutional relu neural networks in polynomial time: Exact convex optimization formulations. arXiv: 14798.
Ergen, T. and Pilanci, M. (2021). Global optimality beyond two layers: Training deep relu networks via convex programs. In International Conference on Machine Learning (ICML), pages 2993-3003. PMLR.
Farrand, T., Mireshghallah, F., Singh, S., and Trask, A. (2020). Neither private nor fair: Impact of data imbalance on utility and fairness in differential privacy. In Proceedings of the 2020 workshop on privacy-preserving machine learning practice.
Feldman, V., McMillan, A., and Talwar, K. (2021). Hiding among the clones: simple and nearly optimal analysis of privacy amplification by shuffling. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science. IEEE.
Feldman, V., McMillan, A., and Talwar, K. (2023). Stronger privacy amplification by shuffling for rényi and approximate differential privacy. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4966-4988 SIAM.
Feldman, V., Mironov, I., Talwar, K., and Thakurta, (2018). Privacy amplification by iteration. In 2018 IEEE 59th Annual Symposium Foundations of Computer Science (FOCS), pages 521-532. IEEE.
Feldman, V. and Shenfeld, M. (2025). Privacy amplification by random allocation. arXiv: 2502.08202.
Gopi, S., Lee, Y. T., and Wutschitz, L. (2021). Numerical composition of differential privacy. In Advances in Neurul Information Processing Systems (NeurIPS).
Kairouz, P., McMahan, B., Song, S., Thakkar, O., Thakurta, A., and Xu, Z. (2021). Practical and private (deep) learning without sampling or shuffling. International Conference on Machine Learning (ICML). PMLR.
Kim, S. and Pilanci, M. (2024). Convex relaxations of relu neural networks approximate global optima in polynomial time. In International Conference on Machine Learning (ICML).
Koskela, A., Jälkö, J., and Honkela, A. (2020). Computing tight differential privacy guarantees using FFT. In International Conference on Artificial Intelligence and Statistics (AISTA7S), pages 2560-2569. PMLR.
Koskela, A., Jälkö, J., Prediger, L., and Honkela, A. (2021). Tight differential privacy for discrete- valued mechanisms and for the subsampled gaussian mechanism using FFT. In International Conference on Artificial Intelligence and Statistics (AISTATS), pages 3358-3366. PMLR.
Koskela, A., Redberg, R. E., and Wang, Y.-X. (2024). Privacy profiles for private selection. In International Conference Machine Learning (ICML).
Krizhevsky, A., Hinton, G., et al. (2009). Learning multiple layers of features from tiny images. -eattee--eeeeeeree------
Dataset, cs. cx.toronto.edd edu/
Lebeda, J., Regehr, M., Kamath, G., and Steinke, T. (2024). Avoiding pitfalls for privacy accounting of subsampled mechanisms under composition. arXiv: 2405.20769.
LeCun, Y., Bottou, L., Bengio, Y., and Haffner, P. (1998). Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):228-22324
Liu, and Talwar, K. (2019). Private selection from private candidates. In Proceedings of the 1 Annual ACM SIGACT Symposium Theory of Computing, pages 298-309.
Liu, X., Jain, P., Kong, W., Oh, S., and Suggala, A. (2023). Label robust and differentially private linear regression: Computational and statistical efficiency. Advances in Neural Information Processing Systems (NeurIPS), 36.
12

---

Lowy, A., Ullman, J., and Wright, S. (2024). How to make the gradients small privately: Improved rates for differentially private non-convex optimization. In International Conference on Machine Learning (ICML).
Mishkin, A., Sahiner, A., and Pilanci, M. (2022). Fast convex optimization for two-layer relu networks: Equivalent model classes and cone decompositions. In International Conference on Machine Learning (ICML), pages 17876.1586.. PMLR.
Papernot, N. and Steinke, T. (2022). Hyperparameter tuning with renyi differential privacy. In International Conference on Learning Representations (ICLR).
Papernot, N., Thakurta, A., Song, S., Chien, S., and Erlingsson, U. (2021). Tempered sigmoid activations for deep learning with differential privacy. In Association for the Advancement of Artificial Intelligence (AAAT), volume 35, pages 9312-9321.
Pilanci, M. and Ergen, T. (2020). Neural networks are convex regularizers: Exact polynomial-tin convex optimization formulations for two-layer networks, In International Conference on Machine Learning (ICML), pages 7695-7705, PMLR.
Rahimi, A. and Recht, B. (2007). Random features for large-scale kernel machines. Advances in Neural Information Processing Systems (NeurIPS).
Redberg, R., Koskela, A., and Wang, Y.-X. (2024). Improving the privacy and practicality of objective perturbation for differentially private linear learners. Advances in Neural Information Processing Systems (NeurIPS), 36.
Sommer, D. M., Meiser, S., and Mohammadi, E. (2019). Privacy loss classes: The central limit theorem in differential privacy. Proceedings on Privacy Enhancing Technologies, 201 (2)-())):44-269
Song, S., Steinke, T., Thakkar, O., and Thakurta, A. (2021). Evading the curse of dimensionality in unconstrained private GLMs. In International Conference on Artificial Intelligence and Statisties (AISTATS), pages
PMLR.
Sordello, M., Bu, Z., and Dong, J. (2021). Privacy amplification via iteration for shuffled and online PNSGD. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 796-813. Springer.
Talwar, K., Thakurta, A., and Zhang, L. (2014). Private empirical risk minimization beyond the worst case: The effect of the constraint set geometry. arXiv: 1411.550 1.5417.
Varshney, P., Thakurta, A., and Jain, P. (2022). (nearly) optimal private linear regression for sub- gaussian data via adaptive clipping. In Conference on Learning Theory, pages 1126-1166. PMLR.
Wang, Y. (2018). Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domain. In Conference on Uncertainty in Artificial Inielligence (UAI).
Wang, Y., Lacotte, J., and Pilanci, M. (2022). The hidden convex optimization landscape of regularized two-layer relu networks: an exact characterization of optimal solutions. International Conference on Learning Representations (ICLR).
Wu, X., Li, F., Kumar, A., Chaudhuri, K., Jha, S., and Naughton, J. F. (2017). Bolt-on differential privacy for scalable stochastic gradient descent-basse analytics. In Proceedings of the International Conference on Management of Data, SIGMOD. ACM.
Xiao, H., Rasul, K., and Vollgraf, R. (2017). Fashion-MNIST: novel image dataset for benchmarking machine learning algorithms. arXiv: 1708.07747.
Ye, J. and Shokri, R. (2022). Differentially private learning needs hidden state (or much faster convergence). Advances in Neural Information Processing Systems (NeurIPS), 35:703-715.
Zhu, Y., Dong, J., and Wang, Y.-. (2022). Optimal accounting of differential privacy via characteristic function. International Conference on Artificial Intelligence and Statistics (AISTATS).
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main claims made in the abstract are about a theoretically viable approach to train 2-layer ReLU network with DP guarantees, where the DP guarantees are obtained by using the NoisyCGD analysis. This is established by showing the conditions for Theorem 2.7 The second claim is that the empirical results for the proposed method are on par with the state-of-the-an aht methods. This is supported by the experimental results in Section 5 c.f., Table 2 Future steps for hidden-state analysis are delineated Section 6
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The paper discusses the method's limitations in Section 6
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proof's
14

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: The paper provides the full set of assumptions for Theorem 2.7 Section
mentions the assumptions for the utility bounds in Theorem 4.1
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question:
Does the paper fully disclose all the information needed reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: The submission includes Python code to reproduce the paper's 's results. Textually, the appendix includes section on the hyperparameter tuning, Section G.I and section on the experimental details of the baselines, Section
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibilityy can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the partieular way they provide for reproducibiliity In the case of closed-source models, it may be that access to the model is limited in
15

---

reproducible, they some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in the supplemental material?
Answer: [Yes]
Justification: The code is included in the supplementary material on OpenReview. The README file contains instructions how run the experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
public/ wwtpc///giiisseeeeeeeeeee Codee/ooddSSSeee ss oon oolccy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
//nips. cc www.cc/ccccc..cc.cc...occ.ooeece celliic///uiessseeee Coo//ooeSuuii Sublisubmiiee subbiisiin sessssionPe ssinnnolicyy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: Section G.I describes the hyperparameter search. Section describes the experimental settings for the baseline methods.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined, or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Table 2 reports the standard deviation of the accuracy the five random reruns for the proposed method and baselines. Figures 2 3 and g similarly report the standard deviation of the accuracy over the five random reruns for the proposed method.
Guidelines:
The answer NA means that the paper does not include experiments.
16

---

The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eπror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
As we explaing in Appendix G the results of the private hyperparameter presented in Table were the most computationally intensive part of the project and were run on eight NVIDIA GeForce RTX 3090 GPUs for 3 days each.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't It make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http://ttws.eee.e........//apaaa
Answer: [Yes]
Justification:
The research project and manuscript adhere the Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consideration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [Yes]
17

---

Justification: Appendix B contains the impact statement. While our paper focuses on theoretical aspect of Differential Privacy, the section references two papers that have investigated the societal impact in practical context.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation. generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Question: Does the paper describe safeguards that have been put place for the responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: The paper does not release data or models. We release the code and hope it will enable and encourage further research in Differential Privacy.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: we have credited an author whose code served as foundation for our code. There were no licences in their code.
Guidelines:
The answer NA means that the paper does not existing assets.
18

---

The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of the package should be provided. For popular datasets, papersw thoode. com data has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- re-packaedd, both the original license and the license of the derived asset (if has changed) should provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We attach code for reproducibility. The code is clearly documented and includes README provide an overview of the code library.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Not applicable.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material fine, but if the main contribution of the paper involves human subjects, then much detail possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: NA
19

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: NA
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (ht /tte::///rrrriie cct..cofeeeenccc////////ooooca// 20257
L.M) for what should or should not be described.
20

---

A Appendix
In the appendix, we provide detailed proofs and additional results that complement the main text. Section [ contains the impact statement, and Section C clarifies the connection between the Strongly Convex Approximation and Generalized Linear Models. In Section D we prove that the gradients of our loss function are Lipschitz continuous. In Section E. we provide detailed convergence analysis to minimize the loss function within the random data model, and Section [.. presents the discusses reference algorithm for the utility bounds. Appendix diseeuseedsscuussss the approximability of the stochastic
approximation for the dual problem in the non-private case. Finally, Appendices G anddd contain details on the hyperparameter tuning and experimental setting, respectively.
B Broader impact statement
Our work advances the differentially private machine learning field by providing improved privacy- utility trade-offs and theoretical understanding. This has positive societal implications as it enables training machine learning models while better protecting individual privacy. Differential privacy increasingly important machine learning systems process more sensitive personal data in healthcare, finance, and other domains.
However, it is important to acknowledge potential limitations and risks. Prior research has shown that differentially private training methods can disproportionately impact model performance on minority classes and underrepresented groups in the data (Farrand et al. [2200] Bagdasaryan et al.) 2019). One hypothesis is that the additive noise tends to have larger relative effect on patterns that appear less frequently in the training set. While our theoretical advances do not directly address this issue, we believe future work DP must investigate techniques for ensuring fairness and equal utility across different subgroups.
Additionally, we note that improved privacy-utility trade-offs, while generally beneficial, could potentially promote more widespread adoption of machine learning in sensitive domains. The broader deployment should be approached carefully considering the societal implications and ethical guidelines for each application setting.
C Formulating the Strongly Convex Approximation as GLM
We first show that the strongly convex loss function given in Eq. (366) corresponds loss function
of convex generalized linear model. The loss function in Eq. 3.6 is of the form
1 - (v
where
X
((,,,,,,)) = 2
Σ (A) v2 - y
+ 2
11.12. (A,,; = 1axJ 100==(aTuu 2 0).
The u, 's are the randomly sampled vectors that determine the boolean matrices A, 's (and the functions ()), and we denote the vector
U1
R
P.d
This is actually generalized linear model: if we denote
(A1)
i,
(AP))503
we see that
1 ||
(v (0.. 1,)
|
21

---

which shows that we are actually minimizing loss function of GLM when we are minimizing the loss [(v, X, 3) w.r.t.
By the results of (Song et al. 2021), we know that the clipped gradients are gradients of an auxiliary convex loss, which allows using the privacy amplification by iteration analysis by Bok et al. (2024).
Moreover, the convexity properties of the GLM loss function are preserved under gradient clipping. This is shown in Appendix E.2 of (Redberg al. 2024). In summary, we can use the convexity properties shown in our Section 3.4 for the privacy analysis.
D Proof of Lemma 3.1
Lemma D.1. The gradients of the loss function
1 Σ :=1
2
t(u, J.j M1) are B-Lipschitz continuous for 3 = ||:;
(At)
v1
1/
+ 2
11
i=1
Proof. For the quadratic function
h(w) = Σ (Ab)jaa] - Vj
the Hessian matrix is of the diagonal block form
2 h diag Ap).
where A; = (A))55 = (A)))) Since for all i E [P]. xz (A:)) & xIJaJ, v2h x xzac
and furthermore for the spectral norm of 42h we have that | S [æ,=]]] 112 = ||0,112.
E
Utility Bound within the Random Data Model
E.1 Reference Algorithm for the Utility Bounds
We consider the following form of DP gradient descent (DP-GD) for the theoretical utility analysis.
Algorithm Differentially Private Gradient Descent (Repeated from [Song al. 2021)
Input: dataset D { loss function R x > R, gradient fo-m bound L,
constraint set C C I"," number of iterations T, noise variance o², learning rate
2: 0g +- 0.
3: for 1. = 0,
T T do
4: gt priv
n Σ Ogl(Or, + be. where b, ~ N000
5: 8.41 Ile θ: - 17 gf where Ie(()) = argmingec ||0 r112-
6: end for
7: return (eriv
Oz.
We have the following classical result for Alg.
Theorem E.1 (Bassily et al. 2014 Talwar al. 2014). If the constraining set C convex. the data sample-wise loss function ((0 z) is convex function of the parameters E R., (v < T for all 0 E C and 2 E D = (21...., 2n), then for the objective function L(O, D) = Σn {(0 2i) under appropriate choices of the learning rate and the number of iterations in the gradient descent algorithm (Alg. 7 we have with probability at least 1 - -3,
L 1
1011, v log)
L(goni D) C(8 D)
nE
22

---

E.2
Utility Analysis
We give convergence analysis for the minimization of the loss function 3.5 with À = 0, i.e., our minimization problem is
P
1
min h(v)
Σ N
(E.1)
i=1
where the diagonal boolean matrices , Ap Raxa are constructed by taking first Lid. samples Mi...., Up, u, Na), and then setting the diagonals A,'s: (Ad)s
max (0, sign(z) u.)
Kim and Pilanci (2024) have recently given several results for the minimization problem (34 The analysis uses the condition number к defined as
Amax (XX))
Amin (2)
where
Σ 1=-BooAttot,n(diig(1(1
diag(( 2 0)]
and Amax and Amin denote the largest and smallest eigenvalues of matrix, respectively. Kim and Pilanci (2024) provide the following lower bound on the number of random hyperplanes required, in terms of the condition number for the problem (E.T to attain zero minimum.
Lemma E.2 (Kim and Pilanci 2024 Proposition 2). Suppose sample > 2x log 3 hyperplane arrangement patierny and assume M is invertible. Then, with probability at least 6, for any y E R", there exist U1.... Up Id such that
Σ Axx
(E.2)
Furthermore, if we assume random data, i... Xz ~ NO, 1) ii.dd, then for sufficiently large d we have the following bound for K.
Lemma E.3 (Kim and Pilanci 2024 Corollary 3). Let the ratio c = y 2 be fixed. For any y > O, there exists d1 such that for all 2 d1 with probability at least 1 - (2m)a.
$ 10V2
Combining Lemmas E.2 and gives us high-probability lower bound for the number of
hyperplanes in random data model, for the problem (E.I) to attain a zero minimum. Assuming the gradients stay bounded by a constant L,, by applying the DP-ERM result of Thm. E. givess us the main result (Theorem 4.1 in the main paper):
Theorem E.4. Consider applying the private gradient descent (Alg. 7 the strongly convex loss 3.6 and assume that the gradients are bounded by constant O. Tet the ratio c à 2 be fixed.
For any 7 > 0, there exists d1 such that for all d 2 dj. with probability at least 7 (2n)s (with Ö omitting the factors)
C(prr D) < Ō
Tis
Proof. From Lemmas E.2 and E.3 follows that by taking d and n large enough (such that n 2 d).
hyperplane arrangements there exists u E RRd-P such that Eq. (F.2) (2n)s- Applying Thm. E.1 with the ambient dimension p d. p= ===0 On log )) then shows the claim.
we have that with = O( log
holds with probability at least
23

---

Illustrations of the Stochastic Approximation
F.1
Illustration with SGD Applied MNIST
Figure SesureAillusreen Aillustrates the approximability of the stochastic approximation for the dual problem in the non-private case, when the number of random hyperplanes is varied, for the MNIST classification problem described in Section 5 We apply SGD with batch size 1000 to both the stochastic dual problem and fully connected ReLU network with hidden-layer width 200. For each model, optimize the learning rate using the grid (10-1/2,, Z. This comparison shows that the approximability of the stochastic dual problem increases with increasing P.
0.99
0.98
Test Accuracy
0.97
0.96
SGD, Couvexified, P-16 16
SGD, Convexified, P-32
0.95
SGD, Convexified, P-64
SGD, Convexified, P 128
0.94
SGD, Convexified, P-256
SGD, ReLU network
0.93
0
100
200
300
400
epochs
Figure 4: Test accuracies number of epochs, when all models are trained using SGD with batch size 1000. The number of random hyperplanes P varies for the stochastic dual problem. The ReLU network is 2-layer fully connected ReLU network with a hidden-layer width of 200. Cross-entropy loss is used for all models.
F22 Illustration with DP-SGD Applied to MNIST
Figure 5 iillustrates the approximability of the stochastic approximation for the dual problem in the private case, when the number of random hyperplanes P is varied, for the MNIST classification problem described in Section We apply DP-SGD with batch size 1000 to both the stochastic dual problem and to fully connected ReLU network with hidden-layer width 200, and for each model, optimize the learning rate using the grid {10- E Z. Based on these comparisons, we conclude that P= 128 not far from optimum, as increasing the dimension means that the adverse effect of the DP noise becomes larger.
24

---

MNIST, a 5.0
MNIST. o 15.0
0.94
0.90
Test Acnurey
0.92
Test Accuracy
0.85
0.90
DP-SGD, Convexified, P-64
DP-SGD, Convexified, P-64
0.88
DP-SGD, Convexified, P-128
DP-SCD, Convexified, P-128
DP-SGD, Convexified, P-206
0.75
DP-SGD, Convexifid, P-256
DP SGD, ReLU network
SGD, RoLU network
0.86
0.2
0.4
0.6
Figure 5: Test accuracies vs. number of epochs, when all models are trained using DP-SGD with batch size 1000, for two different noise levels a. The number of random hyperplanes P varies for the stochastic dual problem. The ReLU network is a 2-layer fully connected ReLU network with hidden-layer width 200.
G DP Hyperparameter Tuning for DP-SGD and NoisyCGD
When comparing DP optimization methods empirically, it is also important to consider the effect of the hyperparameter tuning the privacy costs. Most relevant to work are the private selection methods given by Liu and Talwar (2019) and Papernot and Steinke (2022) that are applicable to private hyperparameter tuning and the privacy profile- prosile-based analysis of those methods by Koskela et al. (2024). These results apply to tuning algorithms that return the best model of IC randomly chosen alternatives, where K. also random variable. We consider the case where K. is Poisson distributed. However, other alternatives exist that allow adjusting the balance between compute cost of training. privacy and accuracy (Papernot and Steinke 2022 Koskela et al. 2024). The DP bounds for Poisson distributed IC can be described as follows. Let Q(v) be the density function of the quality score of the base mechanism (y denoting the score) and A(y) be the density function of the tuning algorithm that outputs the best model of the I. alternatives. Let A and A' denote the output distributions of the tuning algorithm evaluated on neighboring datasets D and D', respectively. Then, the hockey-stick divergence between A and A' can be bounded using the following result.
Theorem G.1 (Koskela et al. 2024). Let K. Poisson((a) for some define the privacy profile of the base mechanism Q. Then, for all E > 0 and for all E 2 0.
N, and let ö(e1), e E IR
He. (AllA'))) S m (()),
(G.1)
where E = 5 (eet - 1) - mmm m 8(81).
Theorem G.1 says that the hyperparameter tuning algorithm is (E,m m mechanism is (E1, ((E))(( If we can evaluate the privacy profile for different values of e, we also optimize the upper bound (G.I). When comparing DP-SGD and NoisyCGD,, fact that DP-SGD privacy profiles are approximately those of the Gaussian mechanism for large compositions (Sommer et al. 2019) as follows. Suppose DP-SGD of the batch size b noise scale a and number of iterations T. Then, we fix the value of the constant 17 À for NoisyCGD such that it is also (s* -DP for the same hyperparameter values b, and T, giving some GDP parameter μ²" Along the GDP privacy profile determined by μ², we find ((1)) that optimizes the bound of Eq. (G.I). and then evaluate the DP-SGD-0 using that same value E1. giving some value 8(Ez). Taking the maximum of 6(E1) and 8(E1) for the evaluation of E in the bound of Eq. (G.I) will then give privacy profile that bounds the DP oP-guarantees of the hyperparameter tuning of both DP-SGD and NoisyCGD.
in case the base
the
(=*,," for some values
Overall, in case the batch size, number of epochs and are fixed, in addition to the learning rate n) we have in all alternatives only one hyperparameter to tune: the hidden-layer width W for the ReL.U networks and the number of hyperplanes P for the convex models.
25

---

Table 2: Model accuracies e-values for the DP hyperparameter tuning algorithm. The number of candidate models K. is Poisson distributed with mean m = 20. The iterative methods generally have comparable accuracy and score better than SSP -imilar the conclusions from Table T
MNIST
CIFAR-10
8 2.88
8 8.91
8 2.88
6 = 8.91
Sufficient Statistics Perturbation (Convex Approx.)
62.8 L.4
71.9
21.7
24.5..77
Sufficient Statisties Perturbation (Random ReL.U)
61.7
68.3
23.2
28.5
Sufficient Statistics Perturbation (RFF)
73.5
80.1
25.6
31.1
DP-SGD + Convex Approximation
92.8
94.8
41.6
45.62.3
DP-SGD + ReLU
91.64.3
94.1
42.5
47.2.t.2
NoisyCGD + Convex Approximation
92.4
94.3
41.1
45.6
G.1 Hyperparameter Grids Used for the Experiments
The hyperparameter grids for the number of random hyperplanes P for the convex model and the hidden width W for the ReLU network are chosen based on the GPU memory of the available machines.
The learning rate 1) is tuned in all alternatives using the grid
{10-3.0 10-21--..... 2.5 10020-1.. -200 10 10-1. 10 10-0.5)
(G.2)
For MNIST and PashionMNISST, tune the number of random hyperplanes P over
{32, 64}
and for CIFAR10 over
{16, 32, 64).
For MNIST and FashionMNISTT, tume the hidden width W of the ReLU network over
2200,500, 800}
and for CIFAR10 10 over
400).
G.2 Results on DP Hyperparameter Tuning
Table 2 shows the accuracies of the best models obtained using the DP hyperparameter tuning algorithm. With the noise scale values
5.0 and 15.0, the DP-SGD trained models are (1.33, 10-5)-DP and (4.76, 10-5)-DP, respectively. To have similar privacy guarantees for the base models trained using NoisyCGD,
adjust the regularization constant À accordingly (as depicted in Section G). which leads to equal final (c, 6)D guarantees for the hyperparameter tuning algorithms. We see from Tables 2 the convex models are on par accuracy with the ReLU network. Notice also from the results of Section 5 that the learning rate tuned logistic regression cannot reach similar accuracies as the NoisyCGD trained convex model.
The results of Table were the most computationally intensive part of our experiments and were run on eight NVIDIA GeForce RTX 3090 GPUs for approximately 3 days each.
G.3 Batch Size Ablation
To justify the choice of batch size 1000 for all experiments of Section 5 consider ablation experiment for MNIST where we study the effect of the batch size.
Figures 6 and 7 show the effect of the batch size the final test accuracy for three alternatives, when we train all models for 400 epochs. Each point is an average of three runs, and the learning rate for each model is optimized using the grid (.2
26

---

Convex Model, CGD Ablation
DP-SGD on Convex Model
0.9300
0.946
0.9475
0.5450
Test Accurary
0,942
0.9425
0.940
0.038
0.9075
0.530
0.5350
Model, NoigyUGD
0.935
250
500
1000
2000
8000
12000
26000
250
500
2000
2000
8000
12000
24000
Botch Sioe
Batch Size
Figure 6: Ablation of batch size for MNIST: test accuracy vs. batch size with 6 = 10-3 and 400 training epochs. Left: DP-SGD on the convexified model. Right: NoisyCGD on the convexified model.
DP-SGD ReLU Network
0.346
0.9400
0.0050
0.9325
0.50300
113227
1000 2000
Size
Figure 7: MNIST Comparisons: Test accuracies vs, batch size for DP-SGD applied ReLU network with hidden layer width 500, when 5 = 10-5 and each model is trained for 400 epochs.
H Experimental Details for Baselines
H.1 Sufficient Statistics Perturbation (SSP)
We compare the proposed method with private linear regression using Sufficient Statistics Perturbation (SSP) from Amin al. (2023). SSP is one-step method that computes and perturbs the sufficient statistics without requiring iterations. This has the advantage that computation only scales linearly with the number of samples and cubically with the number of features, i.e., for calculating the inverse of the sample covariance matrix. The method clips input features adaptively and adds noise to the sufficient statistics as part of achieving differential privacy. Following (Wang) 2018), we estimate the clipping norm directly from data rather than setting it ahead of time. This simplification yields optimistic results compared to pre-determined clipping in theory, one should set the clipping norm ahead of time. However, it allows direct evaluation of the baseline experiment across datasets without introducing another hyperparameter. This does not affect our conclusions, since no result from SSP outperforms the iterative methods in our experiments.
All the datasets are multi-class classification problems, and run multiple one-versus-all linear regressions. For example, for MNIST with 10 classes, we run the SSP method ten times one for each class, by predicting 1 for the specific class and for all other classes. The number of features is the same as the number of features in the other comparing method. This means that for MNIST and FashionMNIST, there are either 100 random hyperplanes for the ReLU methods, or 100 random Fourier features. For CIFAR10, 100 we use only 64 random features for comparability with the iterative methods which have computational constraints. The SSP has one hyperparameter (parameter p in Amin et al. 2023) and we set it to the recommended default value of 0.05.
27

---

H.2 Logistic Regression with DP-SGD
Previous work shows that DP-SGD applied to logistic regression combined with composition analysis leads to similar urivacy-utility trade-offs as Noisy cyclic GD comgined with the hidden- state analysis (Bok al., 2024). To this end, we compare against DP-SGD applied to logistic regression in our experiments, and provide the details of the experiment in this section.
The logistic regression model uses softmax classification for multi-class prediction, defined
3 x+b,
f());
(H.1)
Ek= e m++bb
where f(z) is the predicted probability for class j. wj R is the weight vector for class by E R the bias term for class j. and K' the number of classes. The model parameters are trained jointly using the cross-entropy loss
bW,,,,,,1) Σ My log(f());),
(H.2)
where y {0, 1}K K is the one-hot encoded label vector, W [wi,..... ........ wx] E RRxd is the weight matrix containing all class weight vectors, and b [bi....,bu bb]] RK contains all bias terms.
I Additional Experimental Results on FashionMNIST
Figure 8 shows the accuracies of the best models along the training iteration of 400 epochs for the FashionMNIST experiment.
For comparison, we train linear regression model with SSP. At = 4.76, this results in 67.9 a and 73. 73.2+0.3 % accuracy for Random ReLU and RFF, respectively, At 1.33, the baseline accuracies are 1.0 and 66.4+1.1 %, respectively.
MNSSI (a 5.0)
FashionMNNIST (0=15.0)
0.82
0.84
0.80
Accuncy
0.82
Test Accuracy
0.78
0.76
0.50
Convex Model, DP-SGD Convex Model, CDD
0.72-
Convex Model, DP-SCD
Convex Model, NGD
ReLU Network, DP-SGD
0.70
ReLU Network, DP-SGD
0.2
0.1
0.6
0.8
1.0
1.2
Figure 8: FashionMNIIS:: Test accuracies vs. the spent privacy budget e, when each model is trained for 400 epochs. The model is a 2-layer ReLU network. Similar to Figures and NoisyCGD and DP-SGD achieve comparable accuracies and score a lot higher than baseline regression models.
28

---

Further Motivation for NoisyCGD Analysis: Evaluation of Shuffling Amplification Bounds
When using disjoint batches of data, currently the best option for obtaining rigorous guarantees is to use shuffling amplification (Feldman et al. 202T). However, as shown by Chua al. (2024a ()), the data shuffling combined with disjoint batches leads to an inferior privacy-urility trade-ofi compared to random mini-batch sampling. And, as we experimentally show that the method we propose (strongly convex approximation of ReLU problem NoisyCGD) has similar privacy-utility trade-off as random mini-batch sampling applied to 2-layer ReLU networks, we believe that our approach would be superior compared to the shuffling approach.
To illustrate the (e, O)DP shuffling amplification bounds of (Thm. 3.8 Feldman al., 2021 | for DP-SGD with disjoint mini nini-bathces, we consider setting in one of our experiments where we use noise parameter
5.0. Similarly to the experiments of al. (2024b), we use the numerical method presented in Feldman et (202T) to accurately compute the shuffling bounds. Further, we combine the bounds off (Thm. 3.8 Feldman al., 2021) with the improved bounds of (Thm. 3.1
Feldman et al. 2023)
In our experiments of Section we batch size of 1000 translating 50 or 60 disjoint batches per epoch. For computing the shuffling bounds using (Thm. 3.8 Feldman et al. (021). one can see that this is small number of batches for the conditions of the analysis hold. We also that the shuffling privacy guarantee clearly improves as the number of batches per epoch grows (see, e.g.. the comparisons by Chua et al., 2024b). To obtain lower bound for the (s, 6DD upper bound, consider 1000 batches per epoch instead.
The comparison to the bounds of the Gaussian mechanism (i.e., without any amplification, using parallel composition) is depicted in Fig. which shows that the privacy guarantees of shuffling worse than the privacy bounds of the Gaussian mechanism, which indicates that the privacy- utility trade-offs would be inferior when using data shuffling and shuffling amplification for the DP guarantees when using state-of-art amplification bounds for shuffling.
10
10-6
10-8
10-10-
Shuffte Bound (Feldman al., 2021)
10-12
Ganssian Mechanism (No Amplification)
0.8
1.0
1.1
1.2
1.3
1.4
Figure 9: (E, 6DD guarantees for single epoch training when using 1000 disjoint batches and noise parameter 5.0 obtained using the shuffling amplification of (Thm 3.8, Feldman al. 2021). In experiments, we use 50 or 60 batches per epoch, in which case the DP guarantees of the shuffling would be even worse.
29

---

K
Summary of Notation
d: feature dimensionality, i.e., each data feature a R
number of training samples (introduced in Section 2
X E Rnxd; matrix of feature vectors, i.c., X [x]
nnI
E R": vector of labels;
A(e, Ty. Uy): sample-wise loss;
C(v, X, y): loss function for parameter vector v, data matrix X containing examples zj. and label vector with entries yy:
6: parameter in the definition of DP, set to 10-5 in all experiments;
5: parameter in the definition of DP:
~ D': two adjacent datasets (datasets are adjacent if they differ in one sample);
μ:: privacy parameter in Gaussian DP:
E: number of training epochs;
By: mini-batch at iteration j;
3: smoothness parameter (Lemma 3.1:
function f is f-smooth if V is B-Lipschitz;
C > 0: clipping constant: clip(', C*) denotes the clipping function that limits gradient
2-norms to at most C;
t/: learning rate;
(PllQ))): hockey-stick divergence between distributions P and Q;
K: number of classes in the multi-class model;
k: condition number used in the convex approximation analysis;
f : Rd R: one-layer MLP mapping d-dimensional input features scalar prediction;
A: parameter of strong convexity; a function ʃ(-) is X-strongly convex if g(x) [(x)
2 ||=:1i is convex; with overloaded notation, Amax and Amin denote the largest and smallest
eigenvalues of a matrix;
A₁: diagonal Boolean matrix representing the ith ReLU activation pattern;
L: gradient sensitivity (Definition 2.6p:
|| ||: Euclidean norm;
I(C 2 0): Iverson bracket for (C 2 0): equal to if 2 0 and 0 otherwise; applied elementwise when Ç is vector;
M |Dx:: number of possible ReLU activation patterns in two-layer ReLU network, i.e., the number of regions in a partition of RRd by hyperplanes through the origin perpendicular the rows of X R
(-): Notation for Big-O that omits logarithmic factors;
P: number of randomly sampled normal vectors (hyperplanes) the convex approximation
of the ReLU network, number of Fourier components in the RFF model;
(v) arg minsee ||0 ul12: projection of vector v onto the set C:
= rank X): rank the matrix X;
ut vector of trainable parameters in the convex approximation;
Us, wa Rd: learnable d-dimensional vector lying in V.:
Zj NO(, o² Ia): Gaussian noise vector.
30


Reviews:
[{"review_id": "SptUKvq43X", "reviewer": "Reviewer_ty3e", "summary": "This paper studies differentially private training of 2-layer ReLU networks under the hidden state threat model by leveraging a convex approximation of the original non-convex objective. Two previously distinct ideas are integrated: convex approximation of 2-layer ReLU networks and privacy amplification by iteration. They propose a strongly convex surrogate model to facilitate the privacy analysis and apply NoisyCGD with disjoint mini-batches to achieve both strong privacy and utility guarantees.", "questions": "See weakness, especially, \ncould the authors focus on answering the following two questions.\n\n1. Does network width affect the privacy and utility results in this setting? Is there some tradeoff between utility and network width $m$?\n\n2. Could the author conclude the novelty of the paper?", "limitations": "NA", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strength: \n\nThe topic of improving the theoretical performance of DP-SGD is both interesting and meaningful, particularly in the context of privacy-preserving machine learning. This paper contributes to this effort by providing utility analysis for 2-layer ReLU networks problem which is nonconvex.  \n\n\n \n\nWeakness:\n\n1. The paper appears to be largely an integration and reapplication of results from previous studies. While the extension to ReLU networks is positioned as a novel contribution, the core theoretical results—such as the privacy bounds, convex reformulations, and the utility guarantees—are primarily based on established techniques and theorems from prior work. Although the context (applying these results to two-layer ReLU networks) may be new, the technical novelty and theoretical depth introduced by this paper appear limited. \n\n\n\n2. The paper studies DP-SGD for 2-layer ReLU networks. While it confused me that even the studied nonconvex problem is equal to a convex approximation problem under some conditions (e.g., the networks width $m$ is large enough), to achieve DP, in each iteration, DP-SGD adds Gaussian noise to each weight, that is, in each iteration, there are $m$ noise added to the gradient since there is $m$ neurons and $m$ weights. Since there are $m$ neurons in the hidden layer, this results in adding $m$ independent noise terms to the gradient at each step. Intuitively, as $m$ increases, the amount of injected noise also increases, which should degrade the performance of DP-SGD. However, both the privacy and utility bounds presented in the paper appear to be independent of $m$. This  puzzling me a lot.", "was_revised": true, "final_justification": "I appreciate the authors responses. My main concern has been addressed. I will increase my score", "rebuttal": "We thank the reviewer for their positive summary and for describing our work as \"interesting and meaningful.\"\n\nRegarding the trade-off between utility and model size: the reviewer is correct to point out that there is a trade-off between the utility and the parameter dimensionality in DP-SGD trained models. Notice that in our final approximation (loss function given in Eq. (3.6)), we have $P$ randomly chosen hyperplanes to approximate the ReLU network of width $m$. By clipping the per-example gradients of this loss, the sensitivity of the gradients is bounded, and the privacy analysis becomes independent of parameter dimensionality, as is common in privacy analysis of DP-SGD in general. For the utility analysis, the reviewer is correct to point out that the model size does not explicitly show up in the statement of Thm 4.1. That connection is given in the paragraph leading to the statement of Thm 4.1: with the choice of $P = O\\big((n \\log n\\big)/d)$ random hyperplanes ($n$ denoting the number of data points and $d$ the feature dimension), we get the statement of Thm 4.1. We will add that assumption to the statement of Thm 4.1. Then, the resulting number of parameters is given by $p = P \\cdot d$. Plugging that $p$ in the existing DP-SGD convergence bounds (Appendix E.1) gives the statement of Thm 4.1, so the parameter dimensionality is implicitly in there.\n\nFigures 4 and 5 in the appendix give an experimental illustration of the trade-off between the model size and the utility. While the model approximability seems to grow with growing $P$ (Fig. 4), the utility of the DP trained model does not seem to increase after a certain point (Fig. 5). The plot of Fig. 5 assumes an equal privacy budget and adjusts the DP noise accordingly.\n\nRegarding novelty: private learning of neural networks is important with the growing adoption of deep learning. With DP-SGD and its variants, the options are limited, and there is a big need for a hidden-state analysis of the privacy loss. Although we make use of existing works, we are the first to show that one can learn models with a utility similar to one hidden-layer ReLU networks in the hidden-state threat model of DP. In particular, we significantly improve upon the logistic regression that is the state-of-the-art model in this threat model of DP. We believe this is a very important first step towards new modes of privacy-preserving deep learning. \n\nThe technical novelty comes from combining the theory from one field [1] (analysis of non-linear function learning) with the privacy analysis of iterative algorithms from another field [2]. There is a growing need for learning non-linear functions under the formal guarantees of DP, and we present an important milestone in that endeavour. While the reviewer might deem the combination trivial, the papers stem from 2018 and 2020, and no paper since has made this connection. We also remark that this also aligns with the NeurIPS 2025 guidelines on originality and novelty [3]. Unlike the prior work that focused on theory [1,2], we show that convexifying 2-layer ReLUs enables analysis in the hidden-state threat model of the DP setting where non-convex models fall short.\n\n[1] [Pilanci and Ergen. Neural networks are convex regularizers: Exact polynomial-time convex optimization formulations for two-layer networks. ICML 2020](https://arxiv.org/abs/2002.10553). \n\n[2] [Feldman, Mironov, Talwar, and Thakurta. Privacy amplification by iteration. Annual Symposium on Foundations of Computer Science (FOCS) 2018](https://arxiv.org/abs/1808.06651).\n\n[3] https://neurips.cc/Conferences/2025/ReviewerGuidelines"}, {"review_id": "IbY7YYFQqH", "reviewer": "Reviewer_k3aB", "summary": "The paper studies the hidden-state DP threat model, which has been limited to the Logistic Regression model. In particular, the work studies the threat model for the 2-layer ReLU network by introducing a stochastic approximation of a dual formulation of the ReLU minimization problem. The analysis helps further analysis of the NoisyCGD defense method.", "questions": "See weaknesses.", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1) The paper is well-written: well-defined problem, clear prelims with rigorous theoretical results.\n2) While the experiments are limited to MNIST and CIFAR10 only, they are well designed. I also find the results reasonable and supportive toward the theoretical claims.\n3) I find the studied problem of hidden-state privacy is interesting and of great interests.\n\nWeaknesses:\nI find the practical implication of the theoretical analysis is limited: (1) while the authors showcase the usage of the theoretical analysis in NoisyCGD, I find that implication is niche and is not strictly beneficial (I find NoisyCGD is actually significantly lower in performance compared to DP-SGD, not \"on par\" as the authors stated). (2) I understand that improving the analysis from logistic regression to 2-layer ReLU is novelty, but the results are still very far-away from practicality for real-world neural networks. How is the analysis look like for N-layer networks?", "was_revised": true, "final_justification": "After consideration, I've decided to keep my rejection decision.", "rebuttal": "We thank the reviewer for highlighting our \"clear prelims,\" \"rigorous theoretical results,\" and \"well designed\" experiments.\n\nDP learning of neural networks is important with the growing adoption of deep learning. With DP-SGD and variants, the options are limited, and there is a big need for a hidden-state analysis of the privacy loss. There are no results for $N$-layer networks yet, but we believe that this paper is an important first step in this direction. Also, we think that the steps taken to convexify a 2-layer network are non-trivial and deserve their own study. Two-layer ReLU networks can represent a much richer class of models than logistic regression, allowing them to solve a much broader variety of problems.\n\nOn niche of NoisyCGD: there are several recent papers in top venues addressing the practical limitations of the random mini-batch DP-SGD, which is the predominant algorithm used for training ML models under DP constraints. For example, the line of research on so-called shufflers [1] aims to remove the need for random mini-batches, while recent works [2,3] compare its utility against random mini-batch data sampling in gradient-based DP model training. Several recent works tackle the privacy analysis of DP-SGD with random-sized disjoint mini-batches [4,5,6] obtained from randomly shuffled data. However, none of the above papers are able to give high-utility models trained with disjoint equal-sized mini-batches of data – something that would be very useful in practical implementations. This is also addressed in our Introduction: “...existing analyses do not accommodate fixed-size batches and in particular unshuffled data, further motivating our approach, which yields high-utility convex models for which NoisyCGD can be analyzed accurately.” We believe there is great practical value for the large-scale setting in being able to train the models with pre-defined disjoint batches, as is also expressed in the introduction of the paper [3]: “In practice, almost all deep learning systems generate mini-batches of fixed-size by sequentially going over the dataset, possibly applying a global shuffling of all the examples in the dataset for each training epoch; each epoch corresponds to a single pass over the dataset, and the ordering of the examples may be kept the same or resampled between different epochs. However, performing the privacy analysis for such a mechanism has appeared to be technically difficult due to the correlation between the different mini-batches.”\n\n\n[1] [Feldman, McMillan, and Talwar. Stronger privacy amplification by shuffling for Rényi and approximate differential privacy. In Proceedings of the Annual Symposium on Discrete Algorithms (SODA 2023).](https://arxiv.org/abs/2208.04591)\n\n[2] [Chua, Ghazi, Kamath, Kumar, Manurangsi, Sinha, and Zhang. How private are DP-SGD implementations? ICML 2024.](https://arxiv.org/abs/2403.17673)\n\n[3] [Chua, Ghazi, Kamath, Kumar, Manurangsi, Sinha, and Zhang. Scalable DP-SGD: Shuffling vs. poisson subsampling. NeurIPS 2024.](https://arxiv.org/abs/2411.04205)\n\n[4] [Feldman and Shenfeld  (2025). Privacy amplification by random allocation. arXiv.](https://arxiv.org/abs/2502.08202)\n\n[5] [Chua, Ghazi, Harrison, Kamath, Kumar, Leeman, Manurangsi, Sinha, and Zhang. Balls-and-bins sampling for DP-SGD. AISTATS 2025.](https://arxiv.org/abs/2412.16802)\n\n[6] [Choquette-Choo, C. A., Ganesh, A., Haque, S., Steinke, T., and Thakurta, A. Near exact privacy amplification for matrix mechanisms. ICLR 2025.](https://arxiv.org/abs/2410.06266)"}, {"review_id": "g5X5ZRUvtI", "reviewer": "Reviewer_5hye", "summary": "Summary\nThis paper studies a scenario in which the adversary only has access to the final model and asks whether two-layer ReLU networks can be trained with strong hidden-state DP guarantees. The approach proceeds in three main steps:\n\n1. Convex reformulation\n\nUsing Pilanci \\& Ergen's dual perspective, the two-layer ReLU objective is rewritten as a convex program that enumerates all activation patterns. For sufficiently wide hidden layers, this convex formulation attains the same optimum as the original nonconvex problem.\n\n2. Stochastic, strongly convex approximation\n\nThe intractable full pattern set is replaced by $P \\ll M$ random hyperplanes, and an $\\ell_2$ regularization term is added. This yields the smooth, $\\lambda$-strongly convex objective in (3.6)-(3.7).\n\n3. Noisy Cyclic Gradient Descent (NoisyCGD)\n\nThe convex approximation is trained using fixed, disjoint mini-batches with added Gaussian noise. Privacy loss is tracked via Bok et al.'s $\\mu$-GDP accountant.", "questions": "Questions\n\n1. Line 194: Equation (3.2) includes a regularization term. Is this added specifically to prepare for the strongly convex approximation that follows?\n\n2. Line 202: Why does the bound on the matrices $D_X$ depend only on $\\operatorname{rank}(X)$ and not on the parameter $u$, given the definition of $D_X$ ?\n\n3. Line 205: Is equation (3.4) the dual form of (3.2)? It would be helpful to include a brief explanation of the roles of $v_i$ and $w_i$.\n\n4. Line 277 (Section 4.1): What does the constant $c$ represent? Additionally, what are the implications in the high-dimensional regime (when $n \\ll d$ )?", "limitations": "NA", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n1. The authors tackle an important DP setting-where the attacker observes only the final model-and develop both theoretical and practical tools under convexity assumptions. Their techniques successfully extend to two-layer ReLU networks.\n\n2. Mapping a two-layer ReLU network to a convex program and integrating it with DP yields an improved privacy-utility trade-off. This insight is both novel and significant.\n\n3. The writing is well structured, and the related work section is comprehensive and detailed.\n\nWeaknesses:\n\nI did not identify any major flaws; overall, I find the work interesting and well executed. However, I have a few questions and suggestions for clarification:", "was_revised": true, "final_justification": "My concerns have been addressed, and thus I would like to increase my score to confirm acceptance.", "rebuttal": "We thank the reviewer for identifying our paper as studying \"an important setting\" in privacy-preserving machine learning and the insights given by our paper \"both novel and significant\".\n\nHere are our answers to the questions: \n\n>Line 194: Equation (3.2) includes a regularization term. Is this added specifically to prepare for the strongly convex approximation that follows?\n\nYes, the $L_2$-regularized ReLU problem of Eq. (3.2) is part of the motivation: for sufficiently wide ReLU networks, that problem is equivalent to the convex problem given Eq. (3.4) that has the $\\ell_2$ - $\\ell_1$ - regularization (so-called group lasso regularization). We make further approximations, including changing the $\\ell_2$ - $\\ell_1$ - regularization to $L_2$-regularization, which ensures strong convexity of the final approximation given in Eq. (3.6).\n\n> Line 202: Why does the bound on the matrices $D_X$ depend only on $\\operatorname{rank}(X)$ and not on the parameter $u$, given the definition of $D_X$ ?\n\nNotice that $\\mathcal{D}_X$ defined in Eq. (3.3) is the set of all possible boolean matrices, where each boolean matrix corresponds to a different pattern of ReLU activations for the features of the dataset (the rows of the matrix $X \\in \\mathbb{R}^{n \\times d}$). Thus, the bound for $| \\mathcal{D}_X |$ on line 202 is a bound for the number of possible hyperplane arrangements, and thus it is only determined by the feature matrix $X$. We will add 1-2 clarifying sentences to this part in the updated version of the paper.\n\n> Line 205: Is equation (3.4) the dual form of (3.2)? It would be helpful to include a brief explanation of the roles of $v_i$ and $w_i$.\n\nThank you for the suggestion - we will also clarify this more in the updated paper. Since we remove the constraints for $v_i$ and $w_i$, we can merge them together into the variables $v_i$ in the final approximation given in Eq. (3.6).\n\n> Line 277 (Section 4.1): What does the constant $c$ represent? Additionally, what are the implications in the high-dimensional regime (when $n \\ll d$)?\n\nWe thank the reviewer for this valuable comment. Let us look at this in more detail.\n\nConstant $c$ equals $n/d$, where $n$ is the number of data points and $d$ is the feature dimension. We assume that the ratio $n/d$ stays constant in order to be able to use the results of [1]. One motivation for the assumption $c > 1$ comes from having a similar setting as in prior work: as we state in the last sentence before Thm. 4.1, we make an explicit comparison to the existing bounds in the random data model for the DP-SGD trained linear regression [1], where the dependency on the parameter dimension p appears. In the baseline work [1] it is assumed that $n = \\Omega (d)$ (see e.g. Thm. 1.2 of [1]), which is implied by the assumption $n/d \\geq 1$. The results are in this sense comparable in case $n/d \\geq 1$ (with the assumption $n/d < 1$ there is no implication in any direction, we cannot compare them). As our Thm. 4.1 indicates, it is possible to get rid of the dependency parameter dimension on $p$ when training our proposed model with DP-SGD, and in this sense, our proposed model is better in the random data model than the private linear regression analyzed in [1].\n\nAnother motivation, or rather requirement, comes from the mathematical analysis: the current analysis of [2] that is applicable to our proposed model has to assume $n/d \\geq 1$ for the model loss to have, with high probability, zero global minimum for every possible label vector y with a limited number of random hyperplanes $P = O\\big((n \\log n) / d\\big)$. This seems to be mainly a limitation of the analysis. If we assume $n/d < 1$, in a sense, the problem becomes easier since the feature matrix $X$ becomes column rank deficient with high probability. Then, there also might be an infinite number of global minimizers. Also, the DP-SGD convergence results [3] and [4], which we combine with the analysis of our proposed model, do not require a unique global minimizer. While the more difficult case $n/d \\geq 1$ might be more interesting, it is an interesting question how to extend the results to $n/d < 1$. We will mention this as a remark after Thm. 4.1 in the updated version of the paper.\n\n\n[1] [Brown, G., Dvijotham, K., Evans, G., Liu, D., Smith, A., & Thakurta, A. Private Gradient Descent for Linear Regression: Tighter Error Bounds and Instance-Specific Uncertainty Estimation. ICML 2024.](https://arxiv.org/abs/2402.13531)\n\n[2] [Kim, S., & Pilanci, M. Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Time. ICML 2024.](https://arxiv.org/abs/2402.03625)\n\n[3] [Bassily, R., Smith, A., & Thakurta, A. Private empirical risk minimization: Efficient algorithms and tight error bounds. FOCS 2014.](https://arxiv.org/abs/1405.7085)\n\n[4] [Talwar, K., Thakurta, A., & Zhang, L. (2014). Private empirical risk minimization beyond the worst case: The effect of the constraint set geometry. arXiv.](https://arxiv.org/abs/1411.5417)"}]

Author rebuttal:

Meta-review: This paper extends the hidden state privacy analyses only applicable currently in classification tasks for logistic regression models to 2-layer ReLU networks trained with DP stochastic gradient descent (DP-SGD). This is novel and important extension of private optimization analysis. Reviewers concerns on the DP noise increasing with the model size and novelty of the techniques have been addressed in the authors' rebuttal. However, a reviewer's concern about the practical significance of the proposed method still remains questionable. Overall, this is a solid paper with important contributions in the series of work in improving the analysis of DP optimization. This is the reason for my decision.
Decision: Accept (poster)