Revisiting Differentially Private ReLU Regression
Authors: Meng Ding
Mingxi Lei
Liyang Zhu
Shaowei Wang
Di Wang
Jinhui Xu
Venue: NeurIPS 2024 poster (2024)
Keywords: Differential Privacy
Generalized Linear Model
Primary area: privacy

Abstract: As one of the most fundamental non-convex learning problems, ReLU regression under differential privacy (DP) constraints, especially in high-dimensional settings, remains a challenging area in privacy-preserving machine learning. Existing results are limited to the assumptions of bounded norm $ \|\mathbf{x}\|_2 \leq 1$, which becomes meaningless with increasing data dimensionality. In this work, we revisit the problem of DP ReLU regression in high-dimensional regimes. We propose two innovative algorithms DP-GLMtron and DP-TAGLMtron that outperform the conventional DPSGD. 
DP-GLMtron is based on a generalized linear model perceptron approach, integrating adaptive clipping and Gaussian mechanism for enhanced privacy. To overcome the constraints of small privacy budgets in DP-GLMtron, represented by $\widetilde{O}(\sqrt{1/N})$ where $N$ is the sample size, we introduce DP-TAGLMtron, which utilizes a tree aggregation protocol to balance privacy and utility effectively, showing that DP-TAGLMtron achieves comparable performance with only an additional factor of $O(\log N)$ in the utility upper bound.
Moreover, our theoretical analysis extends beyond Gaussian-like data distributions to settings with eigenvalue decay, showing how data distribution impacts learning in high dimensions. Notably, our findings suggest that the utility upper bound could be independent of the dimension $d$, even when $d \gg N$. 
Experiments on synthetic and real-world datasets also validate our results.

Revisiting Differentially Private ReLU Regression
Meng Ding University at Buffalo
Mingxi Lei University at Buffalo
Liyang Zhu KAUST
Shaowei Wang Guangzhou University
Di Wang" KAUST
Jinhui Xu" University at Buffalo
Abstract
As one of the most fundamental non-convex learning problems, ReLU regression under differential privacy (DP) constraints, especially in high-dimensional settings, remains a challenging sults are limited to the assumptions of bounded norm ||x||2 S 1, which becomes stringent and strong with increasing data dimensionality. In this work, we revisit the problem of DP ReLU regression in overparameterized regimes. We propose two innovative algorithms, DP-GLMtron and DP-TAGLMtron, that outperform the conventional DPSGD. DP-GLMttrn is based on generalized linear model perceptron approach, integrating adaptive clipping and Gaussian mechanism for enhanced privacy. To overcome the constraints of small privacy budgets in DP-
in privacy-preserving machine learning. Existing
GLMtron, represented by Ö(/I/N) where N is the sample size, introduce DA-LAGL which utilizes a tree aggregation protocol to balance privacy and utility effectively. showing that MP-TAGLMMrrn achieves comparable performance with only an additional factor of Olog N) in the utility upper bound. Moreover, theoretical analysis extends beyond Gaussian-lid data distributions to settings with eigenvalue decay, showing how data distribution impacts learning in high di- mensions. Notably, our findings suggest that the utility bound could be independent of the dimension d, even when > N. Experiments on synthetic and real-world datasets also validate our results.
1 Introduction
Protecting individual privacy in data analysis has emerged critical concern. In light of the vast quantities personal and sensitive information involved, traditional methods ensuring privacy encountering significant challenges. Differential Privacy (DP), introduced by [13], has gained widespread recognition as a method for preserving privacy by adding a controlled amount of random noise the data query responses, thereby effectively concealing the details of any individual.
Differentially Private Stochastic Optimization (DP-SO) and empirical form, Differentially Private Empirical Risk Minimization (DP-ERM), are foundational models extensively studied in the DP community. Although there a substantial body of research on DP-SO and DP-ERM with convex loss functions [10] 46
35 37 26 36 38 39), the understanding of nonconvex optimization DP context remains limited. Recent efforts have developed private algorithms with established proven utility bounds for differentially private nonconvex optimization [51 46
16
4
52 8 47).
However, most of the current work employs the gradient norm of the population risk function as measurement instead of excess population risk, commonly used in convex scenarios. Recently, 3 comprehensively studied different instances of non-convex learning, such as generalized linear
"Correspondence Wang <di <di. wang kaust.edu.s:: Jinhui <jinhui gjinui@buffalo.ddu bbuffalo.euu
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

models, ReLU regression, and multi-layer neural networks. However, for each problem, they imposed different strong assumptions, which left big room to further understanding DP non-convex learning. In this paper, we consider the most fundamental one, the ReI.U (Rectified Linear Unit) regression model.
As one of the most fundamental non-convex models, ReLU regression stands out due to its widespread use and effectiveness in deep learning. Despite its prevalence in industry, theoretical exploration of ReLU regression has been relatively limited. [31 studies the DP ReLU regression problem in both well-specified and misspecified settings. However, the problem is still far from well-understood. By and large, several challenges need to be addressed. Their analysis, for instance, heavily relies on strong assumptions about bounded norms of feature vectors and labels, i.e. ||x|| I ( and lvl I ((1, which does not hold even for normal Gaussian distributions. Secondly, while they
d'/2 provide utility upper bound of Ō O' + min [Ne)azz (Nejars }) with sample size N and dimension d, their comeension-indepente dependent upper bound when considering Bernoulli or O(1) SubGausiannn data where ||x|| S O(vd) with high probability. That means when d > N, ie.. when in the overparameterization regime, previous results become trivial.
results heavily rely on their data assumption, leading to a dimension-
In this paper, we revisit the DP ReLU regression problem in the overparameterizee regime. Specifi- cally, we provide a general analysis under the well-specified setting and propose two novel algorithms (DP-GLMtron and DP-TAGLMtron). Our contributions are three-fold, see Table I for details.
1) We propose an innovative algorithm, DP-GLMtron, built upon the Generalized Linear Model Perceptron (GLM-tron) algorithm of [23]. Specifically, DP-GLMtron operates by making a single pass over the dataset and processes one data point at a time by integrating appropriate clipping and adding Gaussian noise to maintain privacy. Additionally, we provide an excess population risk upper
bound of ( D&g +
D N2.2) where Dan (D is the (private) effective dimension. It is noticed that
Den and Det are defined in a way that does not directly rely on the dimension d. Furthermore, our results are applicable not only to Gaussian-like data, typically considered in the traditional differential privacy community, but also to data distributions that exhibit either polynomial or exponential decay, In these cases, we demonstrate that the utility bound is independent of the dimension d, which marks a significant departure from the traditional one (see more discussions in Remark Ap. Finally, we also DM show that our analysis on DP-GLMtron is almost tight by providing a lower bound of 5 Par + N²
2) A significant issue with DP-GLMtron is its upper bound only holds with small privacy budget Ō VV (for further details, see Remark 3), which is due privacy amplification via shuffling. To tackle this limitation, we propose DP-TAC ITGL.Mtron, which utilizes the tree aggregation protocol to introduce noise into the sum of mini-batch gradients instead of using privacy amplification. Our analysis reveals that the utility upper bound of DP-TAGLMtron is closely comparable to that of DP-GLMtron only with additional factor of Ollog N). This finding indicates that DP-TAGLMtron can offer similar performance benefits while potentially being applicable in settings with larger privacy budgets.
3) We conducted experiments with both synthetic data and real data on the ReLU regression model across various algorithms and privacy budgets. Specifically, in the first part, synthetic data was generated under two eigenvalue decay scenarios, X; x i-2 and X x 8-3 The results revealed that faster eigenvalue decay consistently resulted in lower excess risk compared to slower decay, indicating that it may suffer less from dimensionality with respect to utility. Additionally, in both synthetic and real data, DP-GLMtron and DP- OP-TAGLMrron outperformed DP-SGD and DP-FTRL (22), especially as the sample size increased, highlighting the effectiveness of our proposed methods.
Due to space limitations, we have included the algorithms and proofs in the appendix.
2 Related Work
Private Nonconvex Optimization Previous research focusing on the utility of DP-SO/DP-ERN with convex loss functions predominantly employed excess population risk as the metric of utility. In contrast, for non-convex scenarios, utility assessment can be broadly categorized into three types: first-order stationary-based second-order stationary-
and excess population risk. The first-order g 52 50) involves evaluating the l fn-n of the gradient of
Mationary-basee method [43 [33 34
2

---

Table 1: Comparison of work with related studies on (e, 8)-DP ReLU regression in the statistical estimation setting. Here, N represents the sample size, refers to the dimension and Dett. Drr are the (private) effective dimensions. It is noticed that Der and Deff are defined in a way that does not directly rely on the dimension d. Instead, they segment the feature space into an effective subspace. For further discussion, please see Remark
Method
Upper Bound
Lower Bound
Privacy Constraints
Data Assumptions
DP-PGD
O(min(
d//2 (Ne)a72 (Ne)a75
||*||a S
33
DP-GLMtron
Dutt Ō
N
D
C Datt N
D NZ
e
0 VN
DP-TAGLMtron
Ö +
Par N
D DDft N2g2
the population risk function. This method, however, encounters several challenges. For example, 2 shows that the gradient norm tends to approach zero as the sample size increases indefinitely, while there exists no assurance that a differentially private estimator will converge to or even be near any significant local minimum. The Second-order stationary-based method [42 45] employs the norm of the gradient and the Hessian matrix minimal eigenvalue of the population risk function. However, this approach is particularly suited to specific scenarios where any second-order stationary point is a local minimum of the problem, and all the local minima are the global minimum, such as matrix completion and dictionary learning. The third approach involves directly employing the excess population risk as the measure of utility 33 43 and our work aligns with this direction. However, as mentioned these bounds either need strong assumptions or become trivial when d >> N.
Private Generalized Linear Models DP-SO and DP-ERM with generalized linear loss (DP-GLL and generalized linear models (DP-GLM) have gained significant attention in recent years. The key developments in this area can be regarded as three aspects: 1) For convex loss functions, an early study on DP-GLL 21 revealed that, assuming features have bounded l2 norm, the error bound can reach Ö( 1 ). contrasting with the general convex DP-ERM bound of O va ). A subsequent study /Ne
25 found that constrained cases, the error bound depends on the Gaussian width of the constraint
set. [34] improved the bound to O Ne. under the assumption that the data space is bounded set, where 6 is the rank of the expectation of the data matrix. 2) For constrained DP-GLM, 8 explored various scenarios, including smooth/non-smoothh losses and losses in l, space for S 2. [5] provided the optimal rates of DP-GLM in unconstrained settings, identifying different rates depending on the nature of the loss function (smooth and non-negative but necessarily Lipschitz, or Lipschitz). 3) For non-convex losses, [34] 77) provided dimension-inded indeeeedenn bounds for the gradient E2 norm of the population risk function. As specific instance of GLM, this work focuses on the overparameterized regime with sub-Gaussian data rather than bounded data.
3 Preliminaries
Notations: In this paper, we adhere consistent notation style for clarity. We boldface lower letters such as x, w for vectors, and boldface capital letters (e.g. A, H) for matrices. Let ||Al| denote the spectral norm of A. For two matrices A and B of appropriate dimension, their inner product is defined as (A, B) == tr(A B). For a positive semiidefinite (PSD) matrix A and a vector v of appropriate dimension, we write ||vl = v Av. The outer product is denoted by 8.
with each data point has feature vector x; E X C Rd and a response variable yi E V. In this paper, we assume that {(,,, yı J are i.i.d. sampled from ReLU regression model, i.c., each (x; 9:) is a realization of the ReLU regression model y = ReLU(x zero mean randomized noise; w. E Rd is the optimal model parameter. Our goal is to output a model priv that maintains privacy while minimizing the excess population risk, i.c., L(Wpiv) - L(w,), where
Given a dataset D ((x,,
+ z, where ReLU(-) == maxf-:0f 0} is the Rectified Linear Unit (ReLU); & is a
((w)= = E DI w) y)
(1)
In this paper, we will focus classic Differential Privacy to ensure privacy.
3

---

Definition 3.1 (Differential Privacy [3).. Given a data universe A' we say that two datasets D, S X are neighbors if they differ by only one element, which is denoted as D D'. A randomized algorithm A is (s, 6) d)-differenttilly private (DP) if for all adjacent datasets D, D' and for all events the output space of A, we have ((A(DD) $) I e P(A(D") E -
In the following, we will introduce some definitions and assumptions related to the model. Definition 3.2 (Well- (Well-specified Condition). Assume that there exists parameter w. E I such that Fly x ReLU(x' w.), and the variance of the model noise can be denoted by o² [v (x w.
In the literature, the well-specified setting is also extensively referred as the "noisy teacher" setting [18] or the well-structured noise mode [19]. It has been widely studied previously [56] 41 33 12
Assumption 3.3 (Data Covariance). Define H [[xx]
]]
as the expected data covariance matrix.
Denote the eigen decomposition of the data covariance by H = =; A.v.v. where (A:) are eigenvalues in nonincreasing order and (vi) are the corresponding eigenvectors. Define H Hay imply that H
as H k :kg Σx, <isk> \vv,v, and allow lo2
A.v...
In the case of a Gaussian distribution, the data covariance matrix reduces to an identity matrix scaled by variance.
Assumption 3.4 (Fourth moment conditions). Define that the fourth moment of x as M:
(A) There exists a constant a > such that for any Positive Semi-Definite (PSD) matrix A, the following holds:
E [xxx Axx 3 a tr(HA) H.
(B) There exists constant 3 0, such that for every PSD matrix A, the following holds:
E [[xx Axx HAH Ž B tr(HA) H.
Remark 1. For Gaussian distribution, it can verified that Assumption 3.4 holds with a = 3 and
B 3=1 [6 Furthermore, the assumption
sub-Gaussianiry in data, specifically that H H is a
31 for private linear regression model, can be shown to imply Assumption 3.4pptionnn.4.... (A) [56]. It is important to note that
sub- Go--saassian random vector, as posited in previous work [44 41 [54] (28
[55 20
32
Assumption 3.4 (B4 is specifically utilized in our analysis for establishing the lower bound only.
Definition 3.5 ((H, C22, a, -Tiia,,, Let both H and M exist and are finite. A random vector x
satisfies (H, C22 -ail if the the following holds:
3a 0 s.t. with probability 2 - b.
||x| < ||| log 20 (1/b),
(2)
We have,
max Elexp(( v) v 1/20]] < 1, v
C2 H
That is, for any fixed v, with probability 2 b:
((x C
| |||l|||]| logo0 (1/b).
Both conditions above provide Gaussian-like tail bounds determining the resilience of the dataset. Note that Definition 3.5 is widely used in the recent literature on DP analysis for the sub-Gaussian
type of data such as [4 29 27]. In this work, we will assume each sample x satisfying (H. C2. a, b)- Tail and the distribution of the inherent noise satisfies (o², C2, baiT, which could capture more statistical properties beyond expectations. Additionally, according to Assumption 3.4 (A) it holds that ||x|| I a tr(H) log (1/b) in Equation (2)
Assumption 3.6 (Symmetricity conditions). Assume that for every u, Rdd it holds that:
Exxxx 1
x
0,x 0] E[xx [[x
0, T < 0]]
B((xTv)3
1|x 0,x > 0] = vx 1 < 0,x < 0].
Remark 2. Here we require that both the second and fourth moments of remain symmetric. It can be shown that Assumption 3.6 satisfied when x and -x follow the same distribution, which can apply to symmetric sub-Gaussian such symmetric Bernoulli or Gaussian distributions.

---

2.0
15
1.0
1.0
0.0
0.0
0.5
-0.5
-1.0
-0
-15
-1.0
-05
0.0
0.5
1.0
1.5
2.0
-20
-1.
-1.0
-0.5
0.0
05
1.0
1.5
2.0
(a) Trajectory with smaller noise
(b) Trajectory with larger noise
Figure I: Training trajectories of DP-SGD and DP-GLMtron 2D noiseless ReLU regression with symmetric Bernoulli data.
Proposed DP-GLMtron Algorithm
Before presenting the analysis of DP ReLU regression problem, we first introduce our novel algorithm: Mp-L (Algorithm [T]. which is inspired by and built upon the Generalized Linear Model
Perceptron (GLM-tron algorithm of [23].
The fundamental distinction between SGD and GLMtron lies in their respective update rules. Specifi- cally, it takes the following rules:
SGD:
We W 17 (RcLU(x, w - y1)xx [ w.-1 > 0]
GLMtrom: Wi W 77 (ReLU(x, Wt-1) -11)x..
where the algorithm commence from initial point Wo and iterate from / to / = N with stepsize 1). In contrast to the update rule of SGD, GLMtron diverges by changing the derivative of the ReLU function in its update mechanism. Typically, in neural network training, the gradient of the activation function, such as ReLU, is critical component of the backpropagation process. The exclusion of this derivative in GLMtron's 's framework not only simplifies the computational process but also enhances efficiency. Our motivation for developing the MPrGLMtron algorithm stems from observations regarding the limitations DP-SGD, as it sometimes fails to reach the optimal solution and can struggle with convergence under conditions of high noise, often settling at a saddle point instead (as illustrated in Figure 4). This issue particularly pronounced when considering a low privacy budget. Furthermore, [23 demonstrates that this specific omission plays significant role in GLMtron'ss 's ability to efficiently identify predictor that closely approximates the optimal solution.
Building upon these foundations, we now present the detailed implementation of our proposed DP-GL Mtron. For Algorithm[[] [ we begin with a random permutation of the dataset, ensuring that each data point is treated independently and uniformly. Also, such shuffling can amplify privacy [17]. Subsequently, the algorithm performs a single pass over the dataset. Throughout this pass, we need to determine the clipping threshold before undergoing iterative updates for w. Establishing an appropriate clipping threshold is crucial for balancing the trade-off between utility and privacy. If the clipping threshold is set excessively low, it results in loss of gradient information, consequently Consequently, we propose an advanced Algorithm Daammaaaa based on the residual estimator in 28 to achieve an adaptive clipping 44) by utilizing a small batch of data points.
leading to high bias 30 3
Recall that the clipping term is product of the residual, (ReLU(x; (x; - -y)). and the covariate, xx. Based Definition 3.5 and Assumption 3.4 we understand that ||x S a tr(H) log 20 (1/b) with probability of at least - b. Thus, is sufficient to get upper bound of ReLU we) yel- To bound this, we consider three cases, 1) x, Wt 0, W. 0: 2) x w. < x, w. > 0; 3) x__ W. > 0, w. < O, corresponding to d; dZ, and de in step 2 of Algorithm It is noticed that the inherent model noise not considered when initially calculating the residual for the third case at step 2, while this noise is taken into account at step 15. Moreover, when considering special case that x w, < 0, x w. < O, the clipping threshold integrated into the third scenario. For each residual, we first partition the dataset into K batches, compute an estimate for each batch, and form a histogram with over those K estimates. We then apply a private histogram mechanism with geometrically increasing bin sizes. The bin with the most estimates is used, ensuring constant factor
5

---

approximation of the distance to the optimum. Finally, we take the maximum among the three private residual estimates.
Upon determining the clipping threshold "ts it is subsequently incorporated into the existing clipping list y. Following this, Gaussian noise with standard deviation of 2/ is introduced to the clipped It and then the weight vector Wx+1 will be updated. Finally, the algorithm culminates by computing the average of the iterates.
Theorem 4.1 (Privacy Guarantee). Suppose DP-GLMtron is applied to N input samples with a noise multiplier set 0 (OOR( Under these conditions, the algorithm satisfies (z, didfiferrltta eVN privacy for E = = (o)() with e'
/SNNog(2//8 8'
22 in Algorithm 2
Remark 3. For general data distributions, DP-GLMtron necessitates a more complex approach to clipping decisions. To this end, we incorporate Algorithm which uses the magnitude of the residual along with privacy parameters s' and 0', as means to estimate the private threshold. Additionally, we take only one pass over random shuffling data for Algorithm known method of privacy amplification. Hence, we need to add noise
13 17
which well-
where "/ is the
CVN
clipping threshold and must be restricted to 1 1/VN, to satisfy the requirement of and to ensure differential privacy.
Theorem 4.2 (Utility Guarantee Upper). Consider a dataset D ((xi, W1 )) where each x; is drawn from a distribution satisfying (H, C2.0. a. -Taiill and the distribution of the inherent noise satisfies (o², C22 a, bYTiil. Given Assumptions 3.4 an4and3.. 3.6 if we set step size T) S
20 tr(H)) log (N))
a noise multiplier f = O (og(N(8)) estimating data size m = 52( (ogg (og(N/6")), then with a
eVN
e'
probability of 1/N, the output of Algorithm 7 will satisfy:
B[L(wN)] L(w.) S bias variance + privacy,
where the bias, variance, and private terms are upper bounded by
bias N l|wo w.lli + llwo w. ww.lii......
+( |
Wo w. Baas Nq
-4,0,00 ) Def
T²
variance 2 N Day private S
D
where the effective dimensions are given by
Nº
N 4
DΦs k
Σ
X2
D
Σ tck
x7
Σ A
4
C>
G
with k- max(k: (A: d 2 and max
Remark 4. The utility bound is typically decomposed into three terms: the bias term, which is associated with the initial value of the model: the variance term, stemming from the inherent noise intrinsic to the model itself; and the privacy term, introduced by the privacy-preserving Notably, the results contain two crucial factors: the effective dimension Der and the private effective dimension Deri which can be regarded as the function of data covariance matrix's 's eigenvalues.
mechanism.
Technical Understanding Under Simplified Cases To provide more intuitive explanation, we explore two simplified scenarios. 1) | $ 1: In this scenario, where the norm of the data is constrained, the trace of the covariance matrix tr(H) < 1. This condition indicates that the sum of the eigenvalues, A; is less than 1. Given that the eigenvalues are ordered non-increasingly (refer to Assumption (.3), the majority of these eigenvalues must be very small. Assuming the step size is sufficiently small and scaled with the square root of the data size, VN, the optimal number of iterations A* must be confined within scope proportional to VN. If not, the inequality (r(H)= 2 k= 2. 2 would contradict the data assumptions. Furthermore, the clipping threshold, Nn
which depends on ir (r(H), remains a constant term, and the private effective dimension D is bounded above by N. Therefore, the total utility is Ō V + tr(H N= ). 2) sub- Gaussian tail: In this case, the eigenvalue of the covariance matrix corresponds to the variance of nub-Gaussian data. Both the effective dimension, Den, and the private effective dimension, Den effectively reduce to the feature dimension d. Moreover, the clipping threshold contributes factor of d, leading to a total utility bound of N
d

---

The Role of Eigenvalue in High- -ineh-imension Setting Existing work in the DP community primarily relies on data assumptions satisfying Gaussian-like distributions, as discussed in Remark which reduces the data covariance matrix to an identity matrix scaled by variance. Such an assumption may cause the case to be overlooked when the spectrum exhibits decay. Theorem 442 offers a novel perspective by elucidating the interplay between the feature space and the utility bound. Notice the crucial cut-off index k- = max AR 2 2 J. which separates the entire space into a h* 7,
dimensional subspace. It enables us to obtain a bound that does not directly depend on the feature dimension d in the overparameterized regime. To achieve a diminishing bound, it is necessary for k' to be o(N) and for the tail summation of cigenvalues to be (1//N), which indicates that is possible to achieve improved results without suffering the dimension d in the overparameterized regime.
To better understand the effective dimension, we offer examples of data spectra where the excess risk diminishes under certain conditions.
lla is bounded, it Corollary 4.3. Given the same assumptions in Theorem 4.2 and suppose |wo w' holds that:
1. If the spectrum of H satisfies A = -- for some > 1, then with probability at least 1/N, the utility is upper bounded by O(N 1f (1 + N ) ))-
2. If the spectrum of H satisfies A e then with probability at least 1/N, the utility is upper bounded by O(N-1(1+ (E-2)=))))
Remark 5. Corollary 4.3 indicates that utility bound in the overparameterized setting can still vanish if the spectrum exhibits either polynomial or exponential decay. Specifically, a constant privacy budget= = = O(1) can yield utility bounds of ((N-+/(+++) for polynomial decay and for exponential decay. Notably, faster eigenvalue decay (e.g. r 2, 3) consistently resulted in lower excess risk compared to slower decay, indicating that it may suffer less from dimensionality with respect to utility. This insight cannot be derived when considering only traditional Gaussian- like data. Our experiment in Section also validates the conclusion. Moreover, increasing the privacy budget to = = ((N2/(2+2)) for polynomial decay and 0/21/2) for exponential decay improves utility bounds to O(N O(N-r/(1+)) and Ö(N-1), respectively, matching non-private and linear regression
scenario results 49 48
In the following, show that previous analysis for Algorithm i almost tight.
Theorem 4.4 (Utility Guarantee Lower). Consider a dataset D = (xx, y.) where each x, is drawn from a distribution D satisfying (H, C2 a. b)-Tail and the distribution of the inherent noise satisfies (o2. C2, a. b)-Tail. Given Assumptions 3.44and3.3 3.6 if we set the same parameters as in Theorem then with probability of 1/N, the output of Algorithm Hathmmmwwiilr will satisfy:
B[L(WN)) ((w.)= 2 bias + variance + privacy,
where
bias
1
|l
woll + || w. w.llis
wo w- l Ny -H,1,00 ) Def
N2
p2p²
variance
2
N Det private 2
D
N
where the effective dimensions. ki, are defined same as in Theorem 4.2 and denotes F min())]==
Remark 6. Similar to the Theorem 4.2 the lower bound stated here consists of three terms: the bias term, the variance term, and the privacy term. It is noticed that Theorem 4.4 providee the algorithmic lower bound Algorithm [ applicable both under parameterize and over- parameterized settings. Notably, our lower bound aligns with the upper bound, differing only by absolute constants.
5 Advanced DP-TAGLMtron
pivotal concern with Algorithm D DDP DDD-GLMMron lies its primary applicability in the setting where the privacy budget is small, which could potentially limit its practical utility (see Remark for more details). To address this challenge, we introduce DP-TAGL.Mron (Algorithm 3 this section, which is designed to attain an improved trade-off between privacy and utility.
7

---

In Algorithm 3, the process starts with setting the initial weights. For each iteration t, a private residual is determined by Algorithm 2 on the estimating samples, current weights, and privacy parameters. Subsequently, the clipping bound is computed as the product of the private residual and the covariate, analogous to the previous case. Once this clipping bound "Y for the current iteration is computed, it is added to the existing clipping list With Yr in place, the clipped "gradient" (4;) calculated. The maximum value from this list selected as the clipping threshold I' for our next step. The "gradient" I, is then forwarded to the differentially private tree-aggregation mechanism with noise multiplier| f and the maximal clipping threshold r.
It is noticed that our proposed algorithm, DP-TAGLMtron, does not depend on privacy amplification. Instead, it primarily involves employing tree aggregation [14] 22 40] to introduce noise into the sum of mini-batch gradients. At the beginning of training, we construct a binary tree consisting of (2 (2[ N N7+1 - 1) nodes, corresponding to N leaves. Each leaf node is assigned a label 4, and the value of each internal node represents the sum of its child nodes. In each iteration, the tree receives vector 4, derived from the current data pair (X,, Me). which is used to update the tree, incorporating the new node. The final output, denoted as l'gr. is obtained by aggregating the gradients accumulated in the binary tree and adding Gaussian noise to this aggregate. As a result, we can understand that 2' is the private estimation of Ei=o4 Li generated by tree aggregation protocol as follows:
1'
Σ 4 + v., where L, = c (x, (ReLU(x, w.) y:)). 1=0
and v, is combination of most O(1lgg2 t]) Gaussian. Therefore, each 4 influences only its ancestor nodes, affecting at most [log t] + nodes. By introducing Gaussian noise with a standard deviation of (logt/E)) to each node, the entire tree achieves (s, ddddifferlltial privacy.
When receiving the output of Algorithm 4 the optimization objective at step 9 is to determine the weight parameter w. This objective function is composed of two key components: the first term, (K'g+ w). represents the inner product of l',, and the weight parameter w. The second term, 2nj 1 |w]] 1|2
introduces a regularization mechanism, where controls the balance between fitting the training data and constraining the magnitude of the parameters to prevent overfitting. One common method find the optimal solution for this optimization problem is to take the derivative of the objective function and set it to zero. Therefore, for the given problem step 9, we have the following update:
We+1 <- -1 1'2, = -7 Σ 4 vv).
1=
It should be noted that in Algorithm T if the initialization is set to wo = 0, then the update rule of w can be considered equivalent to the one presented here, provided that the variance of the noise and the clipping threshold are disregarded. Upon completing all iterations, the final model weights are determined by averaging all the updated weights from each iteration.
Theorem 5.1 (Privacy Guarantee). Suppose DP- P--ron is applied to N imput samples with a
noise multiplier set to f = (2]]g(++1) lm(1/8) Under these conditions, the Algorithm 3 satisfies and 8'
(e, -diffferrelt privacy, with e' VEN log(2/8)
8 in Algorithm 2
2N
Remark 7. Differing from Algorithm| I the update rule of DP-TAGLMtron mainly utilizes the De-Tree-Aggregatinn mechanism, which involves aggregating the "gradients" collected in bi- nary tree and then adding Gaussian noise to this aggregate. Based on [22). Algorithm 4 achieves
(c, diifferrrellt privacy with appropriate noise multiplier f /2[1g(N+11 In(1/6) ensuring that
Algorithm 3 also upholds (E,8)-Di 8DP under similar settings with é', 8' Algorithm 2
Theorem 5.2 (Utility Guarantee). Consider dataset D {(x,, 14) J.) where each x, is drawn from a distribution D satisfying (H, Co a, -TaTiil and the distribution of the inherent noise z satisfies (02, C2, a, b)- Tail. Given Assumptions 3.4 and hold, if we set stepsize < </((a tr(H)), noise multiplier f will satisfy:
/ /2 1)] ln(1/8) then with a probability of 1/N, the output of Algorithm
[[W(WN)] L(W,) S bias variance + privacy,
8

---

where
1.
bias E
-l/w -wolinni + llwo w. w.llite- + Wu -w.lligs- +H ). Der
N/2
a² Degs private X N
f flog N (anlog,, N (r((H) + +1²) (Day + D())
variance 2 N
where the effective dimensions and k- are defined same as in Theorem 4.2
Remark 8. noteworthy that in Theorem 5.2 both the bias term and the variance term are consistent with those in Theorem 4.2 This alignment extends to the non-private results, with the only differences being in the absolute constants. Additionally, the private term in Theorem (.2 closely aligns with that Theorem 4.2] with the primary difference being factor of log, N. It is intuitive that the tree aggregation mechanism utilized in DP-TAGLMtron indicates that the noise added for privacy is derived from combination of most [log2 N + 1] and at least one random Gaussian vector. This aspect suggests that DP-TAGLMtron diverges from the upper bound of DP-GLMtron at most by a factor logg N and adheres to the same lower bound as DP-ro with a different noise variance. Moreover, in contrast to Algorithm [ DP-TAGLMMrrn does not necessitate O(1//N) to maintain differential privacy, allowing a broader range of privacy budget settings in terms of flexibility and applicability.
Empirical Simulation
In this section, we first conduct experiments with synthetic data validate the theoretical insights related to the role of eigenvalues in a -igh-dimensional setting. Additionally, due to space con-
straints, we present real-data experiment on the MNIST dataset in Appendix [ demonstrate the performance of our proposed method.
Bernoulli /-2 [e= 0.05)
Bemoulli x/ (e 0.2)
Bernuull A, x/ 0.5)
1.4
2.0
DP-SGD
DP-SGD
1.4 DP-SGD
DP-CI
DP-GI
DP-GLMtron
Excess Risk
DF-TAGLMtron
DP-TAGLMtron
1.2
DP-TAGLMtron
1.5
1.0
DP-FTRL
1.0
DP-FTRL
Excess
1.0
0.8
0.6
0.4
100
200
300
400
500
100
200
300
400
500
100
200
300 Epoch
400
500
Epoch
Epoch
(a)
(b)
(c)
Bernoulli Case xx {e= 0.05)
Berouuli Case / (E 0.2)
Bernuulli Case A, x/ (e 0.5)
DP:SGD
1.0
DP-SGD
DP-SGD DF-GLMtion DP-TAGLMtron DF-FTRL
DP-GLMtron
DP-GLMtron
Excess Rick
0.8
Mrrrn
DF-TAGE
DP-FTRL
DP-FTRL
Excces
Excees
0.6
100
400
500
100
400
500
200
500
Epoch
(d)
(c)
Figure 2: Comparative Performance of Various Differential Privacy Algorithms Across Different Data Spectrum and Privacy Budgets. This figure illustrates the performance of four differential privacy Digorithms-DP-SSS DP-GLMtron, DP-TAGLMtron, and DP-FTRL-on generated Bernoulli distributed data, comparing excess risk across different sample sizes and privacy budgets.
Experiment Setup. The experiments were designed with varying privacy budgets (s) set at 0.05, 0.2, and 0.5 with 5 = ....1 to observe the impact of differential privacy constraints on the learning process. We generated the data with two eigenvalue decay scenarios, X; 2-2, simulating different distributions of feature importance. The dimensionality of the data was fixed 1,024 to maintain consistency across trials. The learning rate initially set 10-2 with N representing

---

the sample size, which varied from 50 to 550 and increased in steps to 100. We utilized ReLU regression model with noise to be trained using the previously mentioned algorithms. integrating noise adjustments. The algorithms underwent a single iteration over generated data. The primary metric for evaluation was the average excess risk across varying dataset sizes and & values. For each experiment, we also consider DP-SGD [ and DP-FTRI. [22 as baselines.
Empirical Findings. Compared with Figures (2a 2ch. which illustrate data with eigenvalue decay A x , Figures (2 2eh. which illustrate data with eigenvalue decay X x i exhibit the lower excess risk under the same training algorithms and conditions regardless of privacy budget. This indicates that fast eigenvalue decay suffers less from the dimensionality with respect to utility. thereby validating our results Section Additionally. results in both data with eigenvalue decay X i-2 and data with eigenvalue decay X; x xi= show that DP-GLMtron and DP- OP-TAGLMtron consistently outperform DP-SGD and DP-FTRI regarding excess risk, particularly as the sample size increased. Moreover, it is noticed that the DP-SGD and DP-FTRI exhibit poor convergence performance even with comparatively large data sizes. Finally, in both figures, increasing the privacy budget from 0.05 to 0.5 resulted in lower excess risks for both algorithms. This observation confirms the anticipated trade-off between privacy and learning performance, with a looser privacy constraint leading to more accurate models.
7 Conclusions
In conclusion, our study significantly advances the field of differential privacy in ReLU regression problems. Our first proposed algorithm, DP-GLM, provides an excess population risk upper
bound of Ö - + NE ) offering a novel perspective on utility decomposition and highlighting the impact of eigenvalues in overparameterized settings. Our results apply not only to Gaussian-like data, typically considered in traditional differential privacy studies, but also to data distributions with polynomial or exponential decay. To address limitations with small privacy budgets. we developed DP-TAGLMrron, which offers performance comparable to DP-GLMtron but supports broader privacy budgets. Empirical results from both synthetic and real data experiments demonstrate that DPGLMtron and DP-TAGLMtron consistently outperform DP-SGD and DP-FTRL.
D
Acknowledgments
The research of Meng Ding and Jinhui Xu was supported in part by KAUST through grant CRG10- 4663.2. Di Wang was supported in part by the baseline funding BAS/1/1669-01 0089-01-01, funding from the CRG grand URF/1/4663-01
RE1/1/233-011-0, RE1/1/5332-01-001 FCC/1/197--49-01 from CBRC of King Abdullah University of Science and Technology (KAUST), Di Wang was also supported by the funding RGC/3/4886-0 16-09-01 of the SDAIA-KAUST Center of Excellence in Data Science and Artificial Intelligence (SDAIA-KAUSE AI).
Impact Statements
This paper presents work whose goal is to advance the field of Machine Learning, There many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
Limitations
While this study advances previous work by relaxing certain assumptions and providing both synthetic and real-data validations of the theoretical findings, the analysis specifically confined to the ReLU regression problem. Consequently, it remains uncertain whether these conclusions can be generalized to other nonconvex optimization scenarios. Future research could explore whether similar patterns hold across broader range of nonconvex problems.
10

---

References
[1] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308-318, 2016.
[2] Naman Agarwal, Zeyuan Allen-Zhu, Brian Bullins, Elad Hazan, and Tengyu Ma. Finding approximate local minima faster than gradient descent. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 1195-1199, 2017.
[3] Kareem Amin, Alex Kulesza, Andres Munoz, and Sergei Vassilvtiskii. Bounding user contribu- tions: A bias-variance trade-off in differential privacy. In International Conference on Machine Learning, pages 263-271. PMLR, 2019.
[4] Galen Andrew, Om Thakkar, Brendan McMahan, and Swaroop Ramaswamy. Differentially private learning with adaptive clipping. Advances in Neural Information Processing Systems, 14:17455-17466 2021.
[5] Raman Arora, Raef Bassily, Cristóbal Guzmán, Michael Menart, and Enayat Ullah. Differen- tially private generalized linear models revisited. Advances in Neural Information Processing Systems, 35:22505-22511 2022.
[6] Hilal Asi, John Duchi, Alireza Fallah, Omid Javidbakht, and Kunal Talwar. Private adaptive gradient methods for convex optimization. In International Conference on Machine Learning, pages 383-392. PMLR, 2021.
[7] Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Guha Thakurta. Private stochastic convex optimization with optimal rates. Advances in neural information processing systems, 32, 2019.
[8] Raef Bassily, Cristóbal Guzmán, and Michael Menart. Differentially private stochastic opti- mization: New results in convex and non-convex settings. Advances Neural Information Processing Systems, 34:9317-9329, 2021.
[9] Raef Bassily, Cristóbal Guzmán, and Anupama Nandi. Non-euclidean differentially private stochastic convex optimization. In Conference on Learning Theory, pages 474-499. PMLR, 2021.
[10] Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error error bounds. In 20/4 55th annual symposium on foundations
of computer science, pages 463-473. IEEE, 2014.
[11] T-H Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. ACM Transactions on Information and System Security (TISSEC), 14(3):1-24, 2011.
[12] Meng Ding, Kaiyi Ji, Di Wang, and Jinhui Xu, Understanding forgetting in continual learning with linear regression. arXiv preprint arXiv:2405.17583 2024.
[13] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pages 265-284, Springer, 2006.
[14] Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy Rothblum. Differential privacy under continual observation. In Proceedings of the forty-second ACM symposium Theory of computing, pages 715-724, 2010.
[15] Úlfar Erlingsson, Ilya Mironov, Ananth Raghunathan, and Shuang Song. That which we call private. arXiv preprint arXiv: /906,0366, 2019.
[16] Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: optimal rates in linear time. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 439-449, 2020.

---

[17] Vitaly Feldman, Audra McMillan, and Kunal Talwar. Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 954 964. IEFE, 2022.
[18) Spencer Frei, Yuan Cao, and Quanquan Gu. Agnostic learning of a single neuron with gradient descent. Advances in Neural Information Processing Systems, 33:5417-5444 2020.
[19] Surbhi Goel and Adam Klivans. Learning neural networks with two nonlinear layers in polynomial time. In Conference on Learning Theory, pages 1470-1499. PMLR, 2019.
[20] Lijie Hu, Shuo Ni, Hanshen Xiao, and Di Wang. High dimensional differentially private stochastic optimization with heavy-tailed data. In Proceedings of the 4 ACM SIGMOD- SIGACT-SIGAL Symposium on Principles of Database Systems, pages 227-236, 2022.
[21] Prateek Jain and Abhradeep Guha Thakurta. (near) dimension independent risk bounds for differentially private learning. In International Conference on Machine Learning, pages 476- 484. PMLR, 2014.
[22] Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and private (dcep) learning without sampling or shuffling. In International Conference on Machine Learning, pages 5213-5225. PMLR, 2021.
[23] Sham M Kakade, Varun Kanade, Ohad Shamir, and Adam Kalai. Efficient learning of general- ized linear and single index models with isotonic regression. Advances in Neural Information Processing Systems, 24, 2011.
[24] Vishesh Karwa and Salil Vadhan. Finite sample differentially private confidence intervals. arXiv preprint 17Xiv:1711.03900 2017.
[25] Shiva Prasad Kasiviswanathan and Hongxia Jin. Efficient private empirical risk minimization for high-dimensional learning. In International Conference on Machine Learning, pages 488-497. PMLR, 2016.
[26] Janardhan Kulkarni, Yin Tat Lee, and Daogao Liu. Private non-smooth empirical risk minimiza- tion and stochastic convex optimization in subquadratic steps. arXiv preprint arXiv:2103.15352. 2021.
[27] Xiyang Liu, Prateek Jain, Weihao Kong, Sewoong Oh, and Arun Suggala. Label robust and differentially private linear regression: Computational and statistical efficiency. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
[28] Xiyang Liu, Prateek Jain, Weihao Kong, Sewoong Oh, and Arun Sai Suggala. Near optimal private and robust linear regression. arXiv preprint arXiv:2301.1327 2023.
[29] Xiyang Liu, Weihao Kong, Prateek Jain, and Sewoong Oh. Dp-pea: Statistically optimal and differentially private pea. Advances in Neural Information Processing Systems, 35:29929-2999 29943, 2022.
[30] H Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. arXiv preprint arXiv: 1ttp:://100000 071006666,,, 2017.
[31] Yuan Qiu, Jinyan Liu, and Di Wang. Truthful generalized linear models. In Kristoffer Arnsfelt Hansen. Tracy Xiao Liu, and Azarakhsh Malekian, editors, Web and Internet Economics 18th International Conference, WINE 2022, Troy, NY, USA, December 12-15, 2022, Proceedings, volume 13778 of Lecture Notes in Computer Science, pages 369-370. Springer, 2022.
[32] Yuan Qiu, Jinyan Liu, and Di Wang. Truthful and privacy-preserving generalized linear models. Information and Computation, 301:105225, 2024.
[33] Hanpu Shen, Cheng-Long Wang. Zihang Xiang, Yiming Ying, and Di Wang. Differentially private non-convex learning for multi-layer neural networks, arXiv preprint arXiv:23 20..04002 2023.
12

---

[34] Shuang Song, Thomas Steinke, Om Thakkar. and Abhradeep Thakurta. Evading the curse of dimensionality in unconstrained private glms. International Conference on Artificial Intelligence and Statistics, pages 8638-2646, PMLR, 2021.
[35] Shuang Song, Om Thakkar, and Abhradeep Thakurta. Characterizing private clipped gradient descent on convex generalized linear problems. arXiv preprint arXiv:2006. 06783, 2020.
[36] Jinyan Su, Lijie Hu, and Di Wang. Faster rates of differentially private stochastic convex optimization. Journal of Machine Learning Research, 25(1 14):1-41, 2024.
[37] Jinyan Su and Di Wang. Faster rates of differentially private stochastic convex optimization. arXiv preprint arXiv, 2108, 2021.
[38] Jinyan Su, Changhong Zhao, and Di Wang. Differentially private stochastic convex optimization in (nccldenn space revisited. In Uncertainty in Artificial Intelligence, pages 2026 2035. PMLR, 2023.
[39] Youming Tao, Yulian Wu, Xiuzhen Cheng, and Di Wang. Private stochastic convex optimization and sparse learning with heavy-tailed data revisited. In I/CAI, pages 3947-3953, ijcai.org, 2022.
[40] Hoang Tran and Ashok Cutkosky. Momentum aggregation for private non-convex erm. Advances in Neural Information Processing Systems, 35:10996-11000 11008 2022.
[41] Prateek Varshney, Abhradeep Thakurta, and Prateek Jain. (nearly) optimal private linear regression via adaptive clipping. arXiv preprint arXiv:2207.04688 2022.
[42] Di Wang, Changyou Chen, and Jinhui Xu. Differentially private empirical risk minimization with non-convex loss functions. In International Conference on Machine Learning, pages 6526 6535. PMLR, 2019.
[43] Di Wang and Jinhui Xu. Differentially private empirical risk minimization with smooth non- convex loss funetions: A non-stationary view. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 1182-1189, 2019.
[44] Di Wang and Jinhui Xu. On sparse linear regression in the local differential privacy model. In International Conference on Machine Learning, pages 6628 (238-6637. PMIR, 2019.
[45] Di Wang and Jinhui Xu. Escaping saddle points of empirical risk privately and scalably via dp- trust region method. In Machine Leurning and Knowledge Discovery in Dutabuses: European Conference, ECML PKDD 2020, Ghent, Belgium, September 14-18, 2020, Proceedings, Purt III, pages 90- Springer, 2021.
Faster and more general. Advances in Neural Information Processing Systems, 30, 2017. [46] Di Wang, Minwei Ye, and Jinhui Xu. Differentially private empirical risk minimization revisited:
[47] Lingxiao Wang, Bargav Jayaraman, David Evans, and Quanquan Gu. Efficient privacy- preserving stochastic nonconvex optimization. In Uncertainty in Artificial Intelligence, pages 2203-2213. PMLR, 2023.
[48] Lingxiao Wang, Difan Zou, Kumar Kshitij Patel, Jingfeng Wu, and Nathan Srebro. Private overparameterized linear regression without suffering in high dimensions, 2024.
[49] Jingfeng Wu, Difan Zou, Zixiang Chen, Vladimir Braverman, Quanquan Gu, and Sham M Kakade, Finite-sample analysis of learning high-dimensional single relu neuron. 2023.
[50] Hanshen Xiao, Zihang Xiang, Di Wang, and Srinivas Devadas. A theory to instruct differentially- private learning via clipping bias reduction. In 2023 IEEE Symposium on Security and Privacy (SP), pages 2170-2189, IEBE Computer Society, 2023.
[51] Jiaqi Zhang, Kai Zheng, Wenlong Mou, and Liwei Wang. Efficient private erm for smooth objectives. arXiv preprint 17X1v:1703.09947, 2017.
[52] Qiuchen Zhang, Jing Ma, Jian Lou, and Li Xiong. Private stochastic non-convex optimization with improved utility rates. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, 2021.
13

---

[53] Yingxue Zhou, Zhiwei Steven Wu, and Arindam Banerjee. Bypassing the ambient dimension: Private sgd with gradient subspace identification. arXiv preprint arXiv:2007.08813, 2020.
[54] Liyang Zhu, Meng Ding, Vaneet Aggarwal, Jinhui Xu, and Di Wang. Improved analysis of sparse linear regression in local differential privacy model. arXiv preprint arXiv:2310.07367, 2023.
[55] Liyang Zhu, Amina Manseur, Meng Ding, Jinyan Liu, Jinhui Xu, and Di Wang. Truthful high dimensional sparse linear regression. arXiv preprint arXiv:2410. 13046, 2024.
[56] Difan Zou, Jingfeng Wu, Vladimir Braverman, Quanquan Gu, and Sham Kakade. Benign overfitting of constant-stepsize sgd for linear regression. In Conference on Learning Theory, pages 4633-4635. PMLR, 2021.
14

---

A
Algorithms
Algorithm 1 DP-GLMtron
1: Input: Training Samples: ((r,, yt) = Estimating Samples: {(1,, ) Learning Rate: 7
DP Noise Multiplier: f. Expected x Norm: /a tr(H), Privacy Parameters: e', 8', Clipping list
γ -0
2: Randomly permute y:))
3: Initialize wo - 0
4: for = O...............................
do
5: 8; + D--DD-Thhhstt (hrrshhhlldl ( wens',8'
6:
22x tr(H)C22 log N 88
7: Sample g: ~ (0, Laxd)
8: Wi+1 W. - 774 + (g))
9: where 4 = clip,, (x, (ReLU(x]] wt) v.))
end for
N Ei N-1
11: return w
Algorithm DP-Threshold
1: Input: Estimating Samples:
(Ir 1/) 1m Privacy Parameters: E', Model w, Distribution
Parameters: a, in Definition 3.5
2: Vi E [m]. d, 4- (x, w yi) 10.0000 de +- yr di + (x7 w) vi [m]
(m 3: Partition {d) j==1: J==1 and (d into three K [C] (og((((8))/ subsets of equal and {D})
size separately, namely (D)) (D))K
4: for p=1,2,3 do
5: (de) ΣiEny de DDIDD.. [K]
6: Partition 10. 00) into geometrically
increasing intervals
(...,[1- [2-1 12- 2). (2. (10,0))
Compute de EjEdę ddd S (d2))//Dg) where DE is the interval Q"
7:
8:
if th E loo.2)og(1/)))
(1/K)) then
9:
dh + di + + where of Lap(0, 2/(sk))
10:
else
11:
dh +-0 0 end if
12:
13:
Let [s s
be the nonempty interval containing the largest d.
14:
if p=3 then
set 8D = 2( + o² log 20 (1/ba))
15:
16: else
17:
set SP = 20
18:
end if
19:
end for
return 3
15

---

Algorithm 3 DP-TAGLMuron
I: Input: Training Samples: ((ri, ye) ) Estimating Samples: {114, v/) Learning Rate: "
DP Noise Multiplier: f. Expected x Norm: Vatr(H), Privacy Parameters: s', Clipping list
==
2: Initialize wh +
3: for t -
4: 81 DD--Threshold (( (/));,, we,
5: + 22a Cr log 2a N 8t
6:
add ?/e the list v and - max
7:
4 f clip,,, (x. (ReLU(x, we) Mr))
8:
L'c, f ----ree-ggrregationn f
9:
1 Update Wi+1 argmin (w, 4,, 2n /|ll
end for
return WN c N N--1 W.
11:
Algorithm Sup-Tre-AAgregatiin
Input: Vectors: (4:)-) Noise Paramters: f,r
2: Initialization Create binary T of size 20lgg, N1+1 with N leaf nodes, and each node is sampled i.i.d. from ff (xr))
At t-th iteration, do:
4: Accept 4, and add it to all the nodes along the path to the root of T.
5: Let (e1, .t.....Ch, ei,] be the list of nodes from the root of to the t-th leaf node, with node ej being the root node and node e,, being the leaf node, where h is the height of tree.
6: Let l',, 0d and (bI....,h bn} the bit binary representation of
7: for E [h] do
8:
if 6, then
9: L' + U'sx + Ej, where e, is the value in left sibling of e, node.
end if
11: end for
12: return l'z
16

---

B Additional Experiment
<= 0.05
E= 0.2
0.5
35
DP-SGD
DP-SGD
DR-5GD
DP-GLMtron
26
DP-GLMtron
24
DP-GLMMron
Excess Risk
DP TAGLMMtonn
Excoss Risk
DI- DP-TAGLMrron
DP.LTL
24
DP.FTRL
DP.FTRL
22
20
20
1000
2000
3000
4000
0
1000
2000
3000
4000
0
1000
2000
3000
4000
Epoch
Epoch
Epoch
(a)
(h)
(c)
Figure 3: Comparative Performance of Various Differential Privacy Algorithms on MNIST Across Different Privacy Budgets. This figure illustrates the performance of four differential privacy algorithms-DPP -DPSSD,, DP-GLMtron, DP-TAGLMtron, and DP-FTRL-on generated Bernoulli distributed data, comparing excess risk across different sample sizes and privacy budgets (s 0.05, 0.2, 0.5).
In our second experiment, we evaluate the performance of four different differential privacy (DP) algorithms- DP-SGD, DP- DP- MArroMn,,,,,,, and AP-FFRRL-siiE across varying sample sizes and privacy budgets denoted by E, with values set at 0.05, 0.2, and 0.5. The learning rate initially set to 0.05, with N representing the sample size, which varied from 0 to 1000 and increased in steps to 100. We utilized a ReLUU regression model with noise to be trained using the previously mentioned algorithms, integrating primary metric for evaluation was the average excess risk across varying dataset sizes and values.
the MNIST dataset
noise adjustments. The
The key insights from our findings are: Under Tight Privacy Constraints (s 0.05): DP-TAGLMtron demonstrated superior performance across all sample sizes, achieving the lowest excess risk, while DP-GLMtron's is excess risk increased with larger sample sizes. Under Moderate Privacy Constraints (E = 0.2): The performance differential between our MP-GLMtron and the baseline narrowed, and DP-TAGLMtron continued to exhibit lower excess risks. DP-SGD's performance suffered with larger sample sizes, highlighting its sensitivity to sample size under moderate privacy levels. Under Relaxed Privacy Constraints (e 0.5): Our proposed methods markedly outperformed both DP-SGI) and DP-FTRL, showcasing their enhanced risk mitigation capabilities when privacy constraints are loosened. These insights demonstrate the effectiveness of proposed algorithms, MP-TAGLMMron and DP-GLMtron, in optimizing the balance between privacy protection and model accuracy.
1.80
DP-SGD
1.00
x=0.05
1.05
DP-TAGLMiron
2-0.20
C-0.20
1.02
0.60
1.60
--0.50
0.80
e-0.50
1.00
r-0.50
c-0.50
5.40
$..88
0.50
1.30
0.995
0.40
0.40
0.93
1.00
400
200
400
200
400
200
400
Eooch
Epoch
Epoch
Spoch
Figure 4: Performance of Different Algorithms under Various Privacy Budgets.
Sensitivity of Privacy Budgets. Here, we also included additional experimental results related to the performance of different algorithms under various privacy budgets. we demonstrate the sensitivity of the privacy budget for each algorithm, and clear that DP-SGD faces the same issue. When E is small, the tree mechanism in DP-FTRL allows it to add less noise compared to the naive Gradient Descent or GLMtron algorithm, resulting in similar performance between DP-FTRL and DP-GLMtron. Additionally, it is important to note that DP-FTRL should be compared with DP- MA-G rather than DP-GLMtron, as both DP-FTRL and DP-TAGLMME utilize the tree mechanism, whereas DP-GLMtrov does not. Moreover, even though DP-FTRL converges at the end of the training, it can be observed that the excess risk for DP-FTRI significantly larger than that of DP-TAGLMtron, indicating that it may converge suboptimal solution.
17

---

C Supported Lemmas
Here, provide some relaxation for Assumption 3.6 Assumption C.1 (Moment symmetricity conditions
49
Assume that:
1. For every u E H, it holds that
Exxx" 1[x u > 0]] Exxx 1[x u <O]]
2. For every u E H and v E IHI, it holds that
E|xx 1[x 0,x > 0]] Exxx 1[x u 0, < 0j]
3. For every u E H, it holds that
0xx 1 u > 0]] Exx 1[x < OJ].
4. For every u E H and v E HH, it holds that
E[(x" xxx
1xx u 0, 0]] B[(x v) 1[x 0, < O]].
Lemma C.2 49).
The following results are direct consequences of Assumption C.1
1. Under Assumption
C.1
it holds that: for every vector H.
E xxx
1[x = Exxx = H.
2. Under Assumption C.1
it holds that: for every vector H.
8[x04 1[x
0]
Ex 04 = M 0x
D DP-GLMtron
D.1 Privacy Guarantee
To guarantee the privacy of Algorithm we should first ensure that each step of DP-GLMtron private.
Lemma D.1. Each update step of DP-GLMtron (Algorithm 1 Jensures (Eo, doffeiefernt privacy, provided that f = E.
- where /2 (1.0g111///)) and 7 denotes the clipping norm.
Proof. We first consider (w:)
Each update step (excluding the DP-noise addition) of the form:
We+1 & w, 7 clip,, (xt (ReLU((x) w.) vt)),
where clip,, (v) maxf1, (1, [|v||a }. Consequently, the local Lg sensitivity of We41 is determined
by analyzing the variation in the tth iteration data sample, follows:
A₂ || We+1ll
||yclip,, (x((ReLU(x) w.) - v()) cx (xe(RUU((()) w.) vc)l
< 2nl clip,, (x, (ReLU(xx (x]wx:)xT-))-) w.) yc)ill
217
Moreover, denoting el 50/ V 8N log(2/2 and 8' 6u/(2N), according to Lemma 2.3 in (24] could know that J.W is (E', 8')
Lemma D.2 (117). For u domain D, let R(,) f D + s(i) for i [n] (where S(i is the range space (+)) be a sequence of algorithms such that (+) (21:1-1. is (Eo, 80) -D local randomizer
18

---

for all values of auxiliary inputs 21:1-1 E 8(1) x ... x Sti-1), Let Ag: DD + S( x .... x S(n) be the algorithm that given dataset 2 D", samples uniformly random permutaaion then sequentially computes 2 (215-11 (()) for E [m], and outputs 21m Then for any 5 E [0, such that Eo S log( T61o8(288) ) Ag is (E, 8 + (o -DD where e is:
= c e log(1/6)
c0
n ))
vn
We are now prepared to prove Theorem utilizing the lemmas discussed above.
Firstly, we reformulate the update rule into a sequence of one-step algorithms as follows:
((+1)) (uoar (x, v)) := Ws41 f (r((uo:)-n))hl (X=(t) (ReLU(x ((1)
where u denotes auxiliary inputs, and (() represents the sample the (-th iteration after randomly permuting the input data.
From Lemma D.1 each R(t++)()ooo is a (Ep, 6o)-DP local randomizer algorithm, where Eg I log( (2 ). The output of DP-GLMtron derived through
of the shuffled
outputs U++1 = (((())))ooo (x, y)) for 1. E 0,...,N! N 1. Therefore, by Lemma D.2 Algorithm DP-GLMtron adheres to (2,8 + O (oN)))D where:
= -= eco log(1/8)
+ eco N
))
VN
Assuming Eo S 2. we can infer the existence of some constant e > such that:
8 3< (1 (1-e Veco logg//)(1/))
log(1/0)
VN
N
lox(1/0) N
}
1 - - (
+ (E - 1)
N
log(1/ 1/
((1 + 250) -1) 1
< (((1 + 50) -(1 -11- (1-00/2))
-1)
(4)
N
())
2
c1 Eol
+
N
N
(1.2//)) 50
By setting f independently satisfies 6D) based on standard Gaussian mechanism. Replacing ep = / /2lgg(1 25 25/66) we obtain:
in Lemma D.I we ensure that each update step of DP-GLMtron
2 log(( (1.g(1..5///) 25/))))) log(1/5)
E5 el
JVN
To satisfy overall (c, set 8 8= have:
and 60 = C2 cPN for some constant C2 >> 0. From this, we
2.
2 log(c2 1.25 e N/8) log(2/8)
85 cI
(6)
JVN
(o/( For any S 1, setting f c3
for sufficiently large C3 ensures that E S E. Additionally, to fulfill Lemma D.2 assumption, < Y/z must be satisfied, which is
eVN
C3
y MogiN/8) log(1/0)
e/N
attainable by setting : = =O( los(N(8)
N
This implies that for f = 2
(og())))) DP-GLMtron achieves (c,5)-DP as long as = cVN
O()
log (N/6) thereby completing the proof.
N
19

---

D.2
Utility Guarantee
Here we first provide several results that will be used in our DL-roM utility bound.
Lemma
D.3
(28). Let
m = || f
12gblog (b/8))))))))))) log N/E') and denote V = + o² l|wellif fr + o²}, with probability at least 1 1/b, Al-
max w- H + 1o
gorithm returns St. such that V 7 S 2V.
Consider each sample x; D satisfying (H, C22 a, ba-Tail and the inherent noise i; satisfying (a?, C2 a, baiT. It implies the following facts with Assumption 3.4
Proof.
3a 0 s.t. with probability 2 0 such that ||x| - (r) log 20 (1/bx).
3a s.t. with probability 2 b such that (xx v)² < Civ T Hv log(l/bb))
3a > 0 s.t. with probability 2 1 by. such that || v o² .log 2a (1/ba).
Additionally, we know that
(XxLUXX( w.) y=)ll = ||xx (max(0, x we) we)ll = ||xxl](mmxx(( x w.) x[w.)
ye
According to the aforementioned facts, holds that with probability 2 1 - bx. such that
|xx12 S a (r() (ogg((11/xx)))
Moreover,
/ S max ( ( (((xx((w;) ww)) + =2), v 2((x) )2 + +1), V ((x w,)2 + =?)}
s 1/2 log (log2"((1/))) (1/b)- max muxx///lw" w. 1l+ 00 / //w 1 02 / ww: 11 + +
The second part of the proof can be directly derived from Lemma 2.3 in 24 and Theorem 5 in 28 because each part of df, with high probability, holds that
/ 2 max V //ww - w. + o
| 11 0d, y [wwll + o2]
Therefore, we have the following clipping results:
(ReLU((( w.) - 2
< trH)r(H) log (1/bxx C log (1/b)- max[[lw" welli 0², ||w*|li II +
+02,
|[ + o
< 2ox (rH) log 40 (1/b) C² S
Lemma D.4 (Generic bounds on the DP-GLMtron iterates [49). Suppose that Assumption 3.6 holds.
Considering the MMGGLM algorithm, we have the following recursion:
A A [HA + H) 72 A
02 12
A. > A J(HA,- + A, H) + = A
where A, E(w,- ww.) T
Now consider the recursion of A, given in Lemma D.4 Note that A, is related to A,-1 through a linear operator, therefore A, can be understood as the sum of two iterates, i.c., A, := B, + C., where
B ス (I n -((2)) o B- B We 8.)
C < [I - 3 T(22)) C. + P C. 0
4n T2 c
2
and
{
B, x (I T())
о B
C ž [I - 3 -TT)) +
Bo (wo- w.)
02
C = 0
(8)
20

---

where
{ II - 3 ((n))) o 2--11-1-4 (HA, H + M Ac-1i
II ---3 T(2) := - (HA,-1 A + 4MM A1-1
Besides, since our DP-GLM-uron is run with constant stepsize 7 and outputs the average of the iterates:
N-1
Wt-
Then, the following lemma holds:
Lemma D.5. Suppose that Assumption 3.6
hold. For WN defined in Equation 9
we huve that
N-1N-1
E WN w.)
NN (II
17 2 A.)
N
BHH, -w)
((I
7 H) k- H, A.).
H)
N2
2
kmt
Proof.
E[w, w. we-1]=E[[1 - 1/1 |x] w,- > 0|x;X] )( (w - -w.) [w-1]++ 2yTTTEEB We-1]
+ 1.((1(11)))) |x] w. > 0] 1 [x, w.-1 > 0))x,X; w.
|w.-1] + + w
[I 1/1 [ W,-1 > 0jx,x,] (W -w.) /w:1]
=(1 (W W.)
The remaining proof simply follows [56]
From the decomposition presented in Equation 7 and Equation (8) we know that Σ A, E B, + E C, With this foundation, now bound the bias and variance terms separately. Upper bound for variance error
no For = 0 we have Co = 0 = I-n(a (H))
4nl p2 - (H))
H
We then assume that Ct-1 1 (r(H)
no²
I+ (-n(att(H)))
4n 12
and exam C, based on Equation (7):
C. < (I 1 T(n)) C, + 7/² 2 + T
C.-1 [H C, H) 17 M C, + 1/ 2 H
4n 1
2
11²
2
< - (())
I
H n - 7 t H)
H +
1 - t)()tr(H)) I)
1 1- n(atr(H))
1102
2
+ (arr(()))
H
+ 1/
H 12
(r())(HH)
1- ((tt((H)) H))
no²
4nl
1 1 (--n(tr(HH)) H
I (()t((H))
For the simplicity, we define
:= o + 2 By the definitions of T and T, we have:
7 -((2)) o +c-1+
C = [I-
2
11 -((2)) c CC-1+ +
7 ?M 1 MM C--I+1²
[I-
2
4
11 ((2m) C. + Mo -, +
3 [I-
2
21

---

where the last inequality is due to the fact that M is PSD mapping. Then by the iteration of variance, we have for all 0,
n0² 2
4 H 1 n1 (r))))H))))))))))))))))){))))( H+ ((r
MoC, 1 (M n1 tr H))
17( (H))
- (atr(H))
1 1- ((a
Substituting above into Appendix
D.2 we obtain:
(((a)r((H)
C 3 (I ! 2 T(2n)) C2-1+ 1 ((t(((H
4 +
7 (atr((H)
(I ! [(2n) C2-1
(o'H ""oo
2
1 ((arr(H))
(I- ! ((2)) o C.-1+
2
1 - (atr(H)
1-1
3 1 7/ tr H))
of
[I-
"
-(2n))** o o 4T
(10)
2
H)
1 ((a)r(HH)
2
2
n²2
7 (o 121
1 na (H))
k=
no²
(I (I クー
H)
2
(())) -I- (I 7 ")) HH-1
((atr)(H)
2
Consequently, the variance error can be represented as follows, in accordance with Lemma D.5
N
Variance error S (I
1/V2 (I
7
C2)
2
0=0
1 (I-
(I
"
H)
N
N
no²
(I- (I ? "))))
2
NNV
2
n(a (H))
t=0
1
[
(I
" H N
Σ
2n
(H))(HH) (I (I- 7
"H)") H (1)
N222
2
S (1 - ((atr(H))
I (I
" 'H) N (I (I (I-"H)*
('HN"))
42
" H)* (I (I ! ~
(1 - n((ttr(H)) N [I- (I
2
Noting that for any (0, we have 1 (1 nr) N s min (1, then
I (I HH) N 3 Losk N'' " Ha
2
22

---

Final results can be obtained:
variance error:
o²
1²
Tr(H N212
(1 ((at((H)) (K*
Xg) + (1 77 tr (r))
X1)
D:b.
4
(12)
0² (1 (()n(or(H)))
+ N2212 1
N2112
x + N(1 - 1/ tr (H))
Σ
Ai)
4
4
$>
1>k"
(13)
r2
(k' + 1? Σ
x +
+ 22? Σ x))
1>
Kck*
isk'
(k* N² Σ
Nn
X;)
i>k
where the second inequality holds since tr H = >i= Lower bound for variance error
Xo S Nn- k- and X 2 n
Similarly, we derive a recursion for the variance term to establish the lower bound:
C (I (TT(r)) o C + n²Σ
= (I - (..
7 M) C
= (I o(o f22
It implies that
f-1
C 1
102 -
! 2)2 2k
2
2
k=
(-1
2 1/²
H)
(0"H
2 H + (2
k=0
2 H) 1 + 41j 2 f2 (I (I
1/ HH)
0² (I- (I-
"
H) 21 (nI
- 2)2 2*
"
(n
2
= no0 (I- (I " H1) 21
4m
2 f² (I (I- (1
" H) 21 .
2
where the last inequality comes from n/I
2² II
23

---

Applying Lemma D.5
we could derive the lower bound for variance error:
N-1N-1
" "H)* C,)
variance error
NT [I
2
N-1
(I
" H) N-t
(I 2
))
N2
1=0
2 f
N-1
Σ
[
(I 2 H) N - (I (I -
2 " H
N
1=0
0²
N-1 Σ
(1
2
N - -(1 (1- 77 22))
2
4 f
N-1
ΣΣ
(1 (1-
"x,)
7
x1) N Nー )1 - (1-
- 2 "
2
2
2
1=0
2
N-1
!
N - (1- ? (,)"))
(1 - (1
N2
2
2
(=0
2 1
N-1
Σ Σ
(1 - (1- N-) -1)
(1 (1 (1-2 (1- "
"
+
N²
2
1=
By defining f(x) = E/= (1 (1 - 2) N-t )1 (1 - xz) and according to Lemma C.3 in (56.
we have:
variance error 2
Σ f(nAi)+
+
N2
N
0²
Nk
2N3
N
2N3
11
x²)
Σ
X
+
7/2
Σ
X1)
N2
10
25
N2
10
25
Kck*
4>
(14)
o²
2 f2
(k* + +N2172
x²) +
Σ
x + N2p2 Σ A1)
15N
15N
1>K*
ick
1>
2²
r2
N (k* + n2
Σ 1
x
Σ x
+
N2
Σ A.)
N
K<k
i>k
Upper and Lower bound for bias error
According to Theorem B.5 in 49. the upper and lower bounds on the bias error can be directly derived:
Lemma D.6. Suppose Assumption 3.6 holds and the step size satisfies 1) S 1/>I, then it holds that
bias
|wo- w.
+ Iwo walliee...
1) N2
a() alIlwo w.ll?..- + NillWoo w. w.llih
k* N
+
Nn²
Σ x?)
N1
bias 2 1
|wo- w-1l o.k-
+ |wo w. I.
N2
B(llwa w.l.? 1R + Nnll w.
E N
Nn² Σ x?)
+
N1
1>k"
By integrating the aforementioned results, we thus complete the proof.
24

---

E DP-TAGLMtron
E.1 Privacy Guarantee
Lemma E.1 ((22) Algorithm guarantees (T, 5 [[R(N-1)) 1)]
Rényi differential privacy, where N
20¹ the number of samples. Setting o /2 [gll + lm(1/8) privacy, for S 2mm(1/)).
one can guarantee (E, (..-)-ffffeenttall
To guarantee the privacy of Algorithm 3 we should first ensure that each step of DP-TAGLMtron is private.
We first consider (4 (4.) N-1 According to Lemma E.1 it ensures that DP-rree-gggregation step is
/ //[lgg(N++) +1) (11/8)
(E, 6DD with
Moreover, denoting 8 = e/ 8N log(2/0) and 8' = 8//(NN, according to Lemma 2.3 in [24] we could know that { is (e', -DP
Combining with the advanced composition theorem, it holds that Algorithm 3 is (s, 0)-P.
E.2 Utility Guarantee
Here we introduce several lemmas for future proof.
Lemma F.2. Given a sequence of Positive Semi-IDefinite (PSD) matrices Pt,-= = O...N N, where
P. P,= (I- 2 T(2n)) Pi-1 and Po if - 1/3 tr(H) log N), then for any E [0, N). the following inequality holds:
tr (HHP) 2. 52
NN Iusk + He I),
where k* E [N] can be arbitrarily chosen.
Lemma E.3. Under Assumption A. for every A > 0, il holds that
2xx tr(A)
(M (M
. to
1 (M)
Lemma E.4 (Generic bounds the GLM-tron iterates [4)). Suppose that Assumption 3.6 holds.
Consider the GLM-tron algorithm, we have the following recursion:
A. A o2
A. > A
Mo -I- o
o2
where Ar E(w, w.)(w::w.. T. T 0.
Lemma E.S (Generic bounds on the DP-TAGLMtron iterates). Suppose that Assumptions 3.6 (A) hold. Consider the DP-TAGLMtron algorithm, we have the following recursion:
A (I " T(2m)) o A + 2 + f (2oog, N1 + 1) (1) + + 2 + 122 222 N1 + 1)(
Σ (I T(2))) o I 4nj 2(t) tr (r(H) (I- 7 HH jE
2
A z A
"
(HA + A, H) + 1/2
M o A 4, 2
2
4
where A, == E(w, (w; (. T. 0.
-
Proof of Lemmal
B.5 According to the update rule of DP- OP-LAnLr,o,,, we know:
W1+1 Wo nl'
25

---

where l's, is the private estimation of Ei=0 4 generated by tree aggregation protocol. From [22].
we notice l'sx = Di-ol l + Vo, where 4; (x, (ReLU(x w.) - ye)) and Vy is a combination of at most O( f1) Gaussian noise. If we set wo = O, then holds that:
W++ wo n.
4 vo)
i=0
Wn 17.
Σ
(x, (ReLU(x, w.) -v)) 17 Ve.
0
W, - (RLLUxX w.) - Me) + Vr V.-1).
By denoting T, Vt Ve-1 and noticing that V; is combination noise, it implies that r, is combination of at most [log, t + 1] random Gaussian vectors, i.c.
most ([oog t1) Gaussian
r, = Eger(e) T gg, g. where Q(t) an index set and 2(t) = [2Q-1, 20-1+20-22 2Q 2Q-2 +... + 2 when / 2 with Q E N and 7(4) = max max(71 (71, ........ 74). Moreover, we know
8y ~ (O0, Idxa), indicating:
W, w. n W 0|x;X; (Wi-1 w.) (1(11xx w. 0J 1[x; Wi-1 0f)x,x, we + 72,2, - TT
Let us consider the expected outer product:
A. B|l|w, w.
| B[(w, w. w.)(ww W
< 711 | W 0] xxx,) (wi-1 w (- m1(x/ Wi-1 > -x(xxxx)) (Wi-1 W.))
(quadratic term 1)
2 E (1 W. 0] 1xx wi-1 0)} (x,x, W (x1xx W.)
(quadratic term 2)
2n E(1 T W. 0] 1 W 0}) 1 X Wi-1 XxX,
w.)
(crossing
-1 (B[(I 7/ll 1 W x (w: w. W. + E[T,(W:
( 1[x/ We-1 0/ ))
(crossing 2)
- (B[(1 W. 1xx W.-1 xxxx w. w.
ET
w. 0J 1xx, W 0)))
(crossing 3)
+ E(0 x.) +rp².
E
(quadratic 3)
(quadratic 4)
It can be observed that quadratic terms 1,2.3 and crossing term are original terms for non-private problems, where the remaining are introduced by the private noise.
According to Assumption 3.6 Lemma C.2 and the independence of w., we have:
(crossing term 3) 0,
(crossing term 2) [I 7 | wi-1 > xxx,X - (I 1[x] wr-1 0]1x;x]] ]]-
Now we examine the crossing term 2, denoting R, = (I (1-111(x Wr-1 > 0jxix,) According to the update rule, we have:
Wi-1 -1 (ReLU(x,,....... w.-1) - 3/ xx: + Ii
(I 1--mh - W x 1 1x + r
Σ ... 11,------,,(xx-111----1 + ((زー)) + 18-t- + t
26

---

Hence, we have:
w.T RR -1))- ) + +
ve-1 v
By multiplying both sides by A and taking the expected value, we can obtain:
E[(T xxxxx W. [w R, RR R
E/y 2.
We first consider the second term, notice that:
- (1 w. > 0] xix, w. + xx,)r,] 0.
Furthermore, considering T, and Tj when j < l and j Q()), it follows that E 0. otherwise, we have:
p = E 7a) 8n)( Σ (d)fgg.)
(EQU-1)
d'EQ())
These results arise because only F, is dependent on 8g for E @()). Hence, denoting Ri::] R.... Rj, we have:
R Σ
R RR--RR R,22" .......R.. R
1=1
R
R R
JEQ(1)
T)El Σ
R
Risll(
Σ
(1)ffgg)
Σ
(g)))
jEQ())
4EQ(-1)
('EQ(I)
= =n
Σ
R
Σ
( 878
Σ (1()))())58
JEQ())
474'
= n15²
Σ
Σ
( Resl
JEQ()) (eEQ(-1)nnq
For the last term of crossing term 3, we could also derive:
El (EQ(1-1))(()
Σ
Eb. (R)
Combining the above results with the symmetric of R,, implies that:
-croossing term = 21 Σ Σ
( + R()
JEQ() (EQU-I)NQ())
1 ( N1 +1)
Σ EJR. R,R, ... R.j + f² (2 N1 1)E((>(()) (
jEQ
Recall R, = (I 171l x W > 0jx,x,] and the lemma in
indicates that:
ER R,R, ... Rdj 3 (II-
3I- !
((2 o I.
27

---

We first consider Pp- = (I T(2n)) о Pp-1 and Po = I. Then, it follows that:
Pp 3 (I !! T(2))) Pp-1 + PM - M) p-1
2
1 (I ! ((2)) o Pp-1 +
2
= (I !
{(2n)) [ 1+ 2n tr Σ
!
-(22)) 'H
2
2
!] T(2n)) I Anjo - (I - -1-221) )
"
3 2
where the term HP p-1 can be bounded by Lemma Now, we could derive:
Σ ER R,R, R. 3 Σ (I- (22)) 4na](((())
((n))
(r( (I -1-21) ")
JEQ())
JEQ(()
As results, the generic bounds the DP-TAGLMtron iterate could have the following recursion:
A, 3 (I- " ((2n)) A + 0 " { N1 + 1)E (t) + (t)]..
+ n²² ( MI + 1
Σ (I 2 (21))) I 4nj 2()) (r(H) - (I (I- (1-- "H)"))) jEQ()
We now move on the second part. In light of the T, definition, we know it is at least random Gaussian vector such that r [g. where I min 7. Moreover, holds that
E[(1 - xx w.r,]] R,
Σ (R. R .. - El 18hh j=1
E r 0.
Since E[T for any j # Therefore, the iteration of A, will be the same case in DP- GLMtron.
Consequently, analogous the previous case, we can decompose A, into bias term B, and variance term C..
B: (I ! T(2n)) o BB-1, Bo = -Wwo- - w") -w)
2
C (I 1) T(2m)) o + Co = 0
2
where
M. 1 H f N1 (1)+
+ + N1 1)(
Σ (I " T(2))) o 4njo 2()))((()))))))))) (r()(( -(I -I- 7 - M)) JEQ())
Lemma E.6. Let M represent union upper bound for Mo..... My Under Assumptions (A)
and 3.6 and provided that the step size satisfies 1) S 1/(tr(H) log N), the following holds:
C. < - CN 1 or H)
Sanj
II- (I-(--
" HH)* .M- (I
" H 2
+
-I-
II-
((mm)
7
2
t=
(15)
Proof of Lemma E.6, Our proofs follow the main idea of [48], we include them here for complete- ness. According to the update rule of C₁, it follows that:
N-1
C = "
17
T(2n)) o M,
2
t=0
It can be observed that Co C 3 ... CN since (I - T(27)) is PSD mapping.
28

---

Let M be an union upper bound of (Mo..... My-1h. we will have:
N-1 Σ 1=0
CN 3f
T(2)) 2 o (I 7 . ((2))) M MoM 3 T
(I- -I- TT.T)) JoM.
The last inequality comes from ( -T,, (I -.. and (I -(2)) are PSD mappings. Hence, it implies that:
C++1 (I "
T(2n)) o C. + n (M - -M) C. M
3 (I " T(2))) o C, 122 (M -M) CN + 7
2
3 (I- !
T(21)) 0 CC++ + n²= (M MM-Mi -M) 21 T o (I - (I - ! )((2))))
M ++
2
3 (I-
!
2 T(2n)) o C. on ir(H)
4am"
7 H) v, M) H
where the last inequality comes from Lemma
E.3
Therefore, we have:
CN 3 1 on H))
40mg
(I
"
H
M
(I n T(2))) (222 N-1-1 à o HH+ 1/2
N-1
' (I
" -(21)) M
2
Sanz
(I " N M) (I (I |
N-1
Σ
[I
"
=(2)))* M.
1 an tr H
2
2
0=
Lemma E.7. Variance error] If the step size satisfies S H/(tr(H) log N), then the following holds for any 1,
variance error
(2))
(Tox- + Nn Ha M)-(k* + 4
x2)
N
H
Ha M):
N(1 on tr(H))
2
N
D.k
4
i>k
where
No Hx.:00)+ + 12 N- (BN)())
M M Hoa (logz 2))tt(( +
Proof. According Lemma
D.5 we have:
16an
[I (I- " H) M C.)
variance error
(1 an tu (H))
2
< N(1 az) (H))
16an
(I - (I
"
H M) -I- (I- 7
H
I - (I - 7 ~
-
2
2
N-1
+
"
[ (I
! H)
II- T(2))) o M))
N
1=0
16am
(I
"
H) N M) II - -I-"
"H)
I (I " ")
N(1
an (H())
2
2
N-1
+
7
[I
-(2)))
- (I - ! H) N M)
N
2
2
1=
16am
(I (I - " H) N. M) (I (1- 7
HD
I (I " ")
マタ
N(1 on tr (H))
2
2
! 2 M)
(II (I
N
29

---

Furthermore, Lemma E.5 implies that, for any t S N:
M. 3 o (Rog2 N1 + 1) (1) + 7
+ ((1ogg M + 1)(
Σ (I
tr " {(2)) P oI [ (I -2 (H)))),
2
(E)(()
Now we consider an arbitrary PSD mapping A commuting with H, it holds that:
MA - 0² AH + f log, N EE + (t)) f N) tr(H) (A,I (I- " H ?
2
Moreover, noting that for any æ E (0, 2/n), we have 1 - (1 _ < min Nnp/2), then
I [I " H) 3 Toa 2
N H Ho
2
for any k- 2 0. Therefore, we can define a new matrix as follows:
M = 0² H + na (log2 N) tr(H) (Jo.s- + Nn
H oo0) + f² logg N (Bh(N)) + I.
2
Combining the previous results, we obtain
variance
Nu
N21p²
N211
(To:k
H so M) (k" +
Σ
x²)
(H
H
M)
N(1 an (H)
2
N
D:k"
:00
1>k
N1
N2
N + am Σ
A +
Σ
x2)) (k** +
Σ
x?)
4 i>
ick
k>
f Pogg N
Nn
N212
+
(an N (r(H) + Bn(N) + x(N)*)) (am(k" +
Σ
A
Σ x
x)))
N
4
ick"
Now, we introduce the lemma in 49 to complete the proof.
Lemma E.S
(4 If the step size satisfies 1) S 1/ then it holds that for any ks* 2 1.
bias < 1 N2 ||wo w HHp.. + +l/wo- wI
a(1 Wo w IIl + Nnl wo - w w'Il
N211
(k"
x2)
N2n(1 W2n(1-annt((H1)
1
E.3 Specific Disrtibutions
Proof of Corollary.
1. if A =r by the definition of k., we have k (1r)1/r then:
N
h-
2 k
A (Nm) + Nn (Nn) (Nn)
2
R>
For the sake of simplicity, we assume || l|wo- w 2 S 2 then it hold that:
W2
W2
W2
+ a²
r2
Utility S Nn
+
+
N2 (Nm)+.
Nn
Ny
N
If we choose the step size as follows:
= min
min + N # 2 }
which indicates:
Utility E ( - + (W2 + +T2) NF- ाी..
Thus, it holds that Utility Ö(N if (1 + (f )frr)
30

---

2. If X =E we have ks = log((N)) then:
12
de log(NN) + Nn
11 2 + Nn Σ
(Nn) -1 log(Nn))
2
kSkk
Hence,
W/2
W
W
0²
1
W
W
12
Utility
N1j
N
N1
N
+
N2
log S
N1
N
N2
If we choose the following step size 'l = min (1, /NF ). then we complete our results:
Utility = Ö(N 1 (1 + (5 22)
31

---

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 paper's main contributions and scope are included in the abstract and introduction.
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 or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The paper provides discussion on the limitation and future direction.
Guidelines:
The answer NA means that the paper has no 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 a separate "Limitations" section 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 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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low 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 of 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 used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
32

---

Justification:
All assumptions and proof' are included in the submission.
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 referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch 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 to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: All experiments can be reproduced.
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 be 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 to make their results reproducible or 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 is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility 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.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
33

---

Answer:
[Yes]
Justification:
All data and code will be released after acceptance.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
ceiiionnoicccc 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 new 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
/ /pippe.cc/pullic/guuii wwwiiccgguie//eeeeeeee CoodeSubeiiieeee ssi wswonnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how 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 are reproducible, they 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 possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We provide the detailed experiment setup
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
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: The factors that will influence the experiment are discussed.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call 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.
34

---

It is OK to report 1-sigma error bars, but one 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 enrors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables or
error bars are reported in tables or plots, The authors should explain 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 on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The Experiments Compute Resources are discussed in the Appendix.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of individual experimental runs as well 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 make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics httpppp///errrpp..ccppppaatetaae
Answer: [Yes]
Justification:
The authors have reviewed the NeurIPS 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 cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., - if there is special consid- eration due to laws or regulations their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which feel must be specifically highlighted here.
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
35

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is 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 out 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 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
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 or 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
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?
Question:
Answer: [Yes]
Justification: All related works cited correctly and explicitly.
Guidelines:
The answer NA means that the paper does not existing assets.
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 (c.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.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
36

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was 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 details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, 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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing 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 we expect authors to adhere to the NeurlPS 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.
37


Reviews:
[{"review_id": "Nw0QMftnaI", "reviewer": "Reviewer_7Kd7", "summary": "This paper revisits the problem of differentially private (DP) ReLU regression in overparameterized regimes. The authors propose two novel algorithms, DP-GLMtron and DP-TAGLMtron, which outperform conventional methods like DPSGD. The paper provides theoretical analysis of these algorithms, including privacy guarantees and utility bounds. The authors extend their analysis beyond Gaussian-like data distributions to settings with eigenvalue decay, showing how data distribution impacts learning in high dimensions. The paper also includes empirical results on both synthetic and real-world datasets to validate their theoretical findings.", "questions": "- Can the authors provide the specific location of the claimed rate $\\widetilde{O}(\\frac{1}{\\sqrt{N}}+\\min \\left(\\frac{d^{1 / 2}}{(N \\varepsilon)^{1 / 2}}, \\frac{1}{(N \\varepsilon)^{2 / 3}}\\right)) $ in [1]? I scanned the paper and don't see how this rate appears. Thanks in advance :).\n- What is the role of ReLU regression? Does it serve as a fundamental simplified problem for neural network optimization?\n- The authors provide special cases of $D_{eff}^{priv}$. However, I would appreciate an explanation of its form. For instance, compared to $D_{eff}$, why is it not squared over $\\lambda_i$, and why did the sum of inverse $\\lambda_i$ appear?\n- In the simulation (Figure 1), I noticed that in some cases (especially Figure 1(a)), the excess risk is increasing with respect to sample sizes. How does this happen?\n- Again in the simulation, DP-GLMtron gradually matches the performance of DP-TAGLMtron as $\\varepsilon$ increases, while this is not true for the theory, where DP-GLMtron does not have a guarantee when $\\varepsilon$ is large. How does this happen?\n- Following the last two questions, it seems that DP-GLMtron and DP-TAGLMtron are more sensitive to variations of $\\varepsilon$ than DP-SGD. This is also true for the theory (for instance, Table 1 suggests that for the proposed methods and DPSGD, dependence is $\\varepsilon^2$ and $\\varepsilon^{2/3}$, respectively).\n- Why did the authors choose the settings for $i^{-2}$ and $i^{-3}$ in the simulation?\n\n\n[1] Differentially Private Non-convex Learning for Multi-layer Neural Networks.", "limitations": "The limitations should appear in the main text.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "- The proposed algorithm is noval and intuitive.\n- The authors provide comprehensive theoretical analysis, and the results are concisely conveyed.\n- The writing is good.", "weaknesses": "- The assumptions used in this paper are, though relaxed, strong and may not always hold in practice.\n- The simulation is weak and contains some mismatches with the theory.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer 7Kd7 for the careful and detailed review as well as the constructive feedback.\n\n**Response to the Weakness 1**\n\n**We kindly disagree with the reviewer's opinion.** It is important to note that our work is theoretical, and our assumptions are standard in theoretical studies of ReLU regression or linear regression. As we mentioned in the paper, most assumptions are weaker than the sub-Gaussian data assumption. Even for linear regression models, certain assumptions are necessary to provide analysis on private estimation, such as [1,2,3].\n\n**Response to the Weakness 2**\n\nWe understand the reviewer's concern about our experimental results and we hope to address this in the following answers (Question 4 part).\n\n**Response to the Question 1**\n\nYes, the rate is provided in Theorem 5 of [4], which analyzes the performance of the DP-Projected Gradient Descent for ReLU regression :).\n\n**Response to the Question 2**\n\nPrevious studies on differentially private (DP) statistical estimation have primarily focused on convex models, such as linear models or linear regression, with less attention given to non-convex models. ReLU regression is one of the most fundamental non-convex models in neural networks, which is why we chose to focus on it in our paper. More specifically, ReLU regression, as discussed in our paper, can be viewed as the same as a two-layer neural network model with a rectified linear unit (ReLU) activation function and a single neuron in the hidden layer, as described in [5]. Specifically, they consider:\n$$\nf(\\mathbf{W}, \\mathbf{a}, \\mathbf{x})=\\frac{1}{\\sqrt{m}} \\sum_{r=1}^m a_r \\sigma\\left(\\mathbf{w}_r^{\\top} \\mathbf{x}\\right),\n$$\nwhere $\\mathbf{w}_r \\in \\mathbb{R}^d$ is the weight vector of the first layer, $a_r \\in \\mathbb{R}$ is the output weight, and $\\sigma(\\cdot)$ is the ReLU activation function defined as $\\sigma(z) = z$ if $z \\geq 0$ and $\\sigma(z) = 0$ if $z < 0$. Since they assume that $a_r$ is not trained and focus on the empirical risk minimization problem with quadratic loss, it is equivalent to ReLU regression when setting $m = 1$. Therefore, ReLU regression can be considered as a basic and simplified problem in neural network optimization[6,7,8].\n\n**Response to the Question 3**\n\nWe are glad to see the reviewer notice this difference. The term $D_{eff}$ arises from the variance error term, which is related to model noise. Specifically, it takes the form of $\\mathbf{x}^{\\top} z$. In contrast, $D_{eff}^{priv}$ originates from the private error introduced by the private noise $\\mathbf{g}$. Thus, when considering how the noise terms interact with the data points $\\mathbf{x}$, we observe the following: 1) model noise leads to $\\mathbf{H}$; 2) private noise results in $\\mathbf{I}$. This is the main reason why $D_{eff}^{priv}$ lacks the component $\\lambda_i$ compared to $D_{eff}$. We provide more details in the Appendix (Lemma D.4).\n\n**Response to the Question 4 and Weakness 2**\n\nThis phenomenon for DP-SGD is actually our motivation for studying the private ReLU regression problem. As we mentioned in our paper section 4 (equation 3), the SGD and GLMtron follow the different update rules:\n$$SGD: \\mathbf{w}\\_t=\\mathbf{w}\\_{t-1}-\\eta \\cdot (\\operatorname{ReLU} (\\mathbf{x}\\_t^{\\top} \\mathbf{w}\\_{t-1})-y\\_t) \\mathbf{x}\\_t \\cdot \\mathbb{1}[\\mathbf{x}\\_t^{\\top} \\mathbf{w}\\_{t-1}>0] $$\n$$GLMtron:  \\mathbf{w}\\_t=\\mathbf{w}\\_{t-1}-\\eta \\cdot (\\operatorname{ReLU} (\\mathbf{x}\\_t^{\\top} \\mathbf{w}\\_{t-1} )-y\\_t ) \\mathbf{x}\\_t $$\nThis indicates that if $\\mathbf{x}\\_t^{\\top} \\mathbf{w}\\_{t-1} \\leq 0$, the gradient for SGD becomes zero. Then, in DP-SGD, noise added on gradient can significantly influence the update direction, especially with a low privacy budget. Indeed, we visualized the training trajectories of DP-SGD and DP-GLMtron on a 2D noiseless ReLU regression (Please check the files in the global rebuttal). The visualization demonstrates that DP-SGD struggles to converge under large noise conditions and is more likely to settle at a saddle point rather than reach the optimal solution. This observation motivated us to propose the DP-GLMtron algorithm.\n\n**Response to the Question 5**\n\nExactly, the DP-GLMtron can not provide the privacy guarantee when $\\varepsilon$ is large, but here the performance refers to the utility/excess risk. A large $\\varepsilon$ implies that less noise is added to the gradient, which means the gradient is less impacted by noise, improving performance. The primary difference between DP-GLMtron and DP-TAGLmtron lies in the method of noise accumulation. Therefore, when the noise is reduced, the performance gap between these two algorithms narrows.\n\n**Response to the Question 6**\n\n**We kindly disagree with the reviewer's opinion.** The utility bound depends not only on the privacy budget but also on the data size $n$ and the dimension $d$. It is not possible to separate these factors to independently demonstrate the efficiency of the algorithms. Thus, our results $O(\\frac{1}{n^2\\epsilon^2})$ is better than  $O(\\frac{1}{(n\\epsilon)^\\frac{2}{3}})$. Additionally, the rate in Table 1 for [1] is for DP-PGD rather than DP-SGD.\n\n**Response to the Question 7**\n\nThe setting with two eigenvalue decay scenarios $i^{-2}$ and $i^{-3}$ satisfy our assumptions and we would like to validate our theoretical insights on the role of eigenvalues in a high-dimensional setting, as detailed in Corollary 4.3. \nAs discussed previously, existing work in the DP community primarily relies on data assumptions satisfying Gaussian-like distributions, which reduces the data covariance matrix to an identity matrix scaled by variance. Such an assumption may cause the case to be overlooked when the spectrum exhibits decay. \nTherefore, our paper chooses one of the eigenvalue decay scenarios $i^{-2}$ and $i^{-3}$ in our stimulation to examine the effect of eigenvalue.\n\nDue to space limitations, we will include references in the comment section, please check it in the following.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "185RnH3Vg1", "reviewer": "Reviewer_JyY5", "summary": "The paper provides an algorithm for differentially private RELU regression. They claim that their results outperform DPSGD. Additionally, for the case of a small privacy budget, they provide a tree aggregation protocol that balances privacy and utility. Finally, extensive experimental results are provided to support the claims.", "questions": "1) Can the authors propose ideas on how the proposed approach be extended to models with higher complexity such as deep neural networks?\n2) The authors analyze the privacy-utility tradeoff in their work. They should also mention similar papers involving privacy-utility tradeoff algorithms such as\n\n[a] Alireza Fallah, Ali Makhdoumi, Azarakhsh Malekian, and Asuman Ozdaglar Optimal and Differentially Private Data Acquisition: Central and Local Mechanisms Operations Research 2024 72:3, 1105-1123\n[b] Ameya Anjarlekar, Rasoul Etesami, & R. Srikant. (2023). Striking a Balance: An Optimal Mechanism Design for Heterogenous Differentially Private Data Acquisition for Logistic Regression.\n[c] Andrew Lowy, Zeman Li, Tianjian Huang, & Meisam Razaviyayn. (2024). Optimal Differentially Private Model Training with Public Data.\n\n3) Typo on line 335", "limitations": "NA", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1) A novel algorithm is provided for differentially private RELU regression which outperforms DPSGD.\n\n2) Detailed theoretical analysis is provided for the proposed algorithms.\n\n3) Sufficient experimental evaluation is provided for the proposed algorithms with experiments on both synthetic and real-world data", "weaknesses": "1) There are a lot of recent works on privacy-utility tradeoffs which seem relevant to this paper. A literature survey involving works in that area can be helpful for future readers to further extend this work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer JyY5 for the valuable review as well as the positive feedback!\n\n**Response to the Weakness 1**\n\nThank you for your suggestion. We agree that adding a literature survey on privacy-utility tradeoffs would be beneficial. We will include more related work in the revised paper and hope to provide valuable context for readers.\n\n**Response to the Question 1**\n\nYes. ReLU regression, as discussed in our paper, can be viewed as the same as a two-layer neural network model with a rectified linear unit (ReLU) activation function and a single neuron in the hidden layer, as described in [2]. In particular, [2] considers the following formulation:\n$$\nf(\\mathbf{W}, \\mathbf{a}, \\mathbf{x})=\\frac{1}{\\sqrt{m}} \\sum_{r=1}^m a_r \\sigma\\left(\\mathbf{w}_r^{\\top} \\mathbf{x}\\right),\n$$\nwhere $\\mathbf{x} \\in \\mathbb{R}^d$ is the input, $\\mathbf{w}_r \\in \\mathbb{R}^d$ is the weight vector of the first layer, $a_r \\in \\mathbb{R}$ is the output weight, and $\\sigma(\\cdot)$ is the ReLU activation function defined as $\\sigma(z) = z$ if $z \\geq 0$ and $\\sigma(z) = 0$ if $z < 0$. Since they assume that $a_r$ is not trained and focus on the empirical risk minimization problem with quadratic loss, it is equivalent to ReLU regression when setting $m = 1$. Therefore, ReLU regression can be considered a basic simplified problem in neural network optimization[1,2,3].\n\n**Response to the Question 2**\n\nThank you for pointing out these relevant works. We will include references to these papers in our revised manuscript to provide a broader context for the privacy-utility tradeoff algorithms discussed in our study.\n\n**Response to the Question 3**\n\nThank you for catching the typo on line 335. We will correct it (\"simulation\") in the revised paper.\n\n[1] Wu, Jingfeng, et al. \"Finite-sample analysis of learning high-dimensional single ReLU neuron.\" International Conference on Machine Learning. PMLR, 2023.\n\n[2] Frei, Spencer, Yuan Cao, and Quanquan Gu. \"Agnostic learning of a single neuron with gradient descent.\" Advances in Neural Information Processing Systems 33 (2020): 5417-5428.\n\n[3] Diakonikolas, Ilias, et al. \"Learning a single neuron with adversarial label noise via gradient descent.\" Conference on Learning Theory. PMLR, 2022.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Mf5ltRnKzp", "reviewer": "Reviewer_M8TJ", "summary": "This paper studies the problem of learning a planted (student-teacher) ReLU regression model, privately. The paper proposes two algorithms (DP-GLMtron and DP-TAGLMtron) to do this. For both algorithms, privacy utility tradeoffs are computed. The results do not explicitely contain the ambient dimension $d$, while they contain other terms as the \"effective dimension\", which allow to have bounds explicitely vacuous in the regime where there are more parameters (in this case, equal to the number of input dimensions $d$) than number of samples $N$", "questions": "Can the authors provide extensive comparison with [4]?\n\nWhy didn't the authors focused on DP-SGD? Why it is useful to introduce these two algorithms?\n\nCan the authors comment on their implicit assumption on $\\Gamma$?\n\nCan the authors elaborate on the experimental settings used for DP-SGD on MNIST data?", "limitations": "No potential negative societal impact.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "This paper tackles a difficult and theoretically interesting problem, i.e. (in its generality) private, non-convex optimization. This paper focuses on the case of a planted ReLU regression model. The initial assumptions (see basically page 4) are, in my opinion, reasonable for this setting.", "weaknesses": "The paper has, in my opinion, 4 major weaknesses:\n\n- Its fit with the related literature is not always clear. The main improvement with respect to previous results is remarked in Table1, and the baseline is the recent and unpublished work [1]. In line 98, results on convex optimization are presented [2, 3]. This results are not presented with the dependence on the $l_2$ norm of the solution, and it is not mentioned that both results assume the input samples to have bounded $l_2$ norm, which is not the case in this work. This makes the comparison with the convex baseline unclear. Furthermore, comparison with [4] is not provided, which definitely offers a more solid baseline than [1].\n\n- The analysis is not well motivated. The authors contribution is based on the two proposed algorithms, namely DP-GLMtron and DP-TAGLMtron. Considering the arguable practicality of such algorithms in realistic deep learning problems, why didn't the authors focused, for example, on providing bounds on DP-SGD instead? This makes the results being very specific to the toy setting of ReLU regression, for which the two algorithms are specifically designed for.\n\n- While it is true that the provided bounds do not contain explicitely $d$, it is unclear the true dependence with the ambient dimension through other terms. Namely, in line 222 the authors set $\\|x\\|_2 \\leq 1$, argued to be the improvement with respect to [1]. This allows to remove the dependence of $d$ from the trace of the covariance $H$. Authors also assume $\\|w_0 - w^*\\|_2$ to be bounded in corollary 4.3. Furthermore, the bounds also depend on $\\Gamma$, which does not receive discussion on how this term is reasonably small.\n\n- Empirical validation of the claims is relatively weak. In particular, in the main body, empirical results are presented on a synthetic dataset with quickly decaying covariance eigenvalues. The experiments on MNIST are pushed in Appendix B (there might be a typo in the third line of the caption of Figure 2, where it's mentioned that the data is Bernoulli), where the results are, in my opinion, puzzling. The baseline of DP-SGD is presented (which has to be improved with the two proposed algorithms to motivate the analysis), and the excess risk for $\\varepsilon = 0.5$ increases as the number of samples increases (!). Furthermore, this excess risk is approximately $\\sim 24$, which seems larger than simply random guessing. This dubious results make me suspect of a bad comparison with standard and well established algorithms as DP-SGD, pointing towards the second weakness mentioned in this list.\n\n\n\n[1] - https://arxiv.org/pdf/2310.08425\n\n[2] - https://proceedings.mlr.press/v32/jain14.pdf\n\n[3] - https://arxiv.org/pdf/2006.06783\n\n[4] - https://proceedings.mlr.press/v97/wang19c/wang19c.pdf", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer M8TJ for the thorough review and the insightful comments.\n\n**Response to the Weakness 1 and Question 1**\n\nWe thank reviewer M8TJ for the constructive feedback and we will include these comments in the updated version, thanks! We acknowledge that our main improvement is highlighted in Table 1, with [1] as the baseline. While [4] also studies DP-GLM with non-convex loss, it is not directly comparable to our work. Specifically, Theorem 5 of [4] assumes $\\lVert x_i \\rVert_2 \\leq 1$, while we consider $x$ has a sub-Gaussian tail, meaning $\\lVert x_i \\rVert_2 \\leq O(\\sqrt{d})$ with high probability. Moreover, [4] provides a bound of $\\tilde{O}(\\frac{\\sqrt[4]{d}}{\\sqrt{n\\epsilon}})$ dependent on $\\sqrt[4]{d}$, which we aim to mitigate in the overparameterized setting. For Theorem 6 in [4], it still needs to assume $\\lVert x \\rVert_\\infty \\leq 1$ while we consider more general distributions that could be unbounded. Moreover, it needs a very strong assumption that $\\lVert w^* \\rVert_1 \\leq 1$ as it uses DP-Frank Wolfe. \n\nRegarding the results on convex optimization in lines 98 and references [2, 3], we will revise our paper to clarify differences in assumptions, particularly regarding the bounded norm of input samples, ensuring clear distinctions between our work and the convex baseline.\n\n**Response to the Weakness 2 and Question 2**\n\nWe appreciate the reviewer's attention to our motivation. Before analyzing DP-GLMtron, we noticed DP-SGD sometimes fails to converge and reaches suboptimal solutions (as seen in our experiments). Therefore, we try to visualize the training trajectories of DP-SGD and DP-GLMtron on a 2D noiseless ReLU regression with symmetric Bernoulli data (we put the figures in the PDF file, please check it). The visualization demonstrates that DP-SGD struggles to converge under large noise conditions and is more likely to settle at a saddle point rather than reach the optimal solution. \nAs we mentioned in our paper section 4 (equation 3), the SGD and GLMtron follow the different update rules:\n$$SGD: \\mathbf{w}\\_t=\\mathbf{w}\\_{t-1}-\\eta \\cdot (\\operatorname{ReLU} (\\mathbf{x}\\_t^{\\top} \\mathbf{w}\\_{t-1})-y\\_t) \\mathbf{x}\\_t \\cdot \\mathbb{1}[\\mathbf{x}\\_t^{\\top} \\mathbf{w}\\_{t-1}>0] $$\n$$GLMtron:  \\mathbf{w}\\_t=\\mathbf{w}\\_{t-1}-\\eta \\cdot (\\operatorname{ReLU} (\\mathbf{x}\\_t^{\\top} \\mathbf{w}\\_{t-1} )-y\\_t ) \\mathbf{x}\\_t $$\nWhen $\\\\mathbf{x}\\_t^{\\top} \\\\mathbf{w}\\_{t-1} \\leq 0$, the SGD gradient is zero, and DP-SGD's direction is heavily influenced by noise, especially with a low privacy budget (see Figure 1a). Therefore, these observations motivated us to propose the DP-GLMtron and DP-TAGLMtron algorithms.\n\n**Response to the Weakness 3 and Question 3**\n\nWe appreciate the reviewer's attention to our approach to addressing dimension independence. **However, the reviewer may misunderstood our paper.** Generally, our bounds depend on the trace of the covariance matrix $\\mathbf{H}$ rather than $\\\\|x\\\\|_2\\leq 1$. In line 222, we just aim to provide a simple example to illustrate how the bounds behave under the assumption $\\\\|\\mathbf{x}\\\\|_2 \\leq 1$. However, this does not imply that our bounds improve previous results with this setting. Our main contributions are:\n\n1. We provided the first analysis beyond data assumptions that satisfy Gaussian-like distributions, which may overlook cases where the spectrum exhibits decay.\n\n2. Our results offer nearly dimension-independent bounds without assuming $\\\\|\\mathbf{x}\\\\|_2 \\leq 1$. This indicates that as long as $k^*$ is $o(N)$ and the tail summation of eigenvalues is $o(1/N)$, it is possible to achieve diminishing bounds without being affected by the dimension $d$ in the over-parameterized regime.\n\nWhy do we focus on the covariance matrix $\\mathbf{H}$? We provide some examples here. If $\\mathbf{H} = \\operatorname{diag}\\\\{1, 1, \\ldots, 1\\\\}$, its trace satisfies $\\operatorname{Tr}(\\mathbf{H}) = \\mathcal{O}(d)$. If $\\mathbf{H} = \\operatorname{diag}\\\\{1, 1/2, \\ldots, 1/d\\\\}$, its trace satisfies $\\operatorname{Tr}(\\mathbf{H}) = \\mathcal{O}(\\log d)$. These examples illustrate that only the effective rank influences utility, which explains why we can mitigate the impact of dimension $d$ in some cases.\n\nAdditionally, $\\\\|\\mathbf{w}_0-\\mathbf{w}^*\\\\|_2 $ (i.e., $\\\\|\\mathbf{w}^*\\\\|_2$) to be bounded by a constant is a common assumption in the DP estimation even for the linear regression model such as [5,6,7].\n\nRegarding the $\\Gamma$ term, we provide analysis in Lemma D.3 for detailed discussion, where we establish that each $\\gamma_t$ is effectively bounded by the $\\mathbf{H}$ norm term $(\\\\|\\\\mathbf{w}\\_*-\\\\mathbf{w}\\_t\\\\|\\_{\\\\mathbf{H}})$. This crucial detail ensures that our results remain controlled. Furthermore, by decomposing our analysis into the head and tail subspaces of $\\mathbf{H}$, we can achieve bounded results analogous to those observed in non-private scenarios, as detailed in references [8,9,10,11].\n\n**Response to the Weakness 4 and Question 4**\n\nWe understand your concern regarding our experimental setup. Below, we hope to address your concerns as follows:\n\n1. Why do we have a synthetic dataset with spectrum decay in the main body? The simulation in our main body aims to validate the theoretical insights related to the role of eigenvalues in a high-dimensional setting, as we discussed in Section 4.\n\n2. Typo of MNIST. Thanks for pointing out the typo, we will correct it in our revised version.\n\n3. Why are results increasing with data size and approximately $\\sim 24$? The observed increase in excess risk as data size grows, along with its approximation to 24, stems from the nature of our experimental setup. We are considering a ReLU regression model, as outlined in the Preliminary Section and Equation 1, without incorporating any neural network architecture.\n\nDue to space limitations, we will include more explanations, experiment setup, and references in the comment section, please check it in the following.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
To all reviewers:

We would like to thank all the reviewers for their great efforts and insightful comments! Based on their suggestions, we address some common concerns and discuss them in the revised paper.

**1. Motivation for Proposing the DP-GLMtron Algorithm and Focus Away from DP-SGD:**

Our motivation for developing the DP-GLMtron algorithm stems from observations regarding the limitations of DP-SGD. Initially, we noticed that DP-SGD sometimes fails to reach the optimal solution and can even struggle to converge, as evidenced by our experimental results. To further explore this issue, we visualized the training trajectories of both DP-SGD and DP-GLMtron on a 2D noiseless ReLU regression with symmetric Bernoulli data. Please refer to the figures in the PDF for detailed illustrations.

The visualization in the attached PDF file shows that DP-SGD encounters difficulties in converging under conditions of high noise, often settling at a saddle point instead of reaching the optimal solution. This behavior is particularly evident when using a low privacy budget, as shown in Figure 1(a) in our paper.

As discussed in our paper (Section 4, Equation 3), SGD and GLMtron follow different update rules:
$$SGD: \mathbf{w}\_t=\mathbf{w}\_{t-1}-\eta \cdot (\operatorname{ReLU} (\mathbf{x}\_t^{\top} \mathbf{w}\_{t-1})-y\_t) \mathbf{x}\_t \cdot \mathbb{1}[\mathbf{x}\_t^{\top} \mathbf{w}\_{t-1}>0] $$
$$GLMtron:  \mathbf{w}\_t=\mathbf{w}\_{t-1}-\eta \cdot (\operatorname{ReLU} (\mathbf{x}\_t^{\top} \mathbf{w}\_{t-1} )-y\_t ) \mathbf{x}\_t $$
This indicates that when $\\mathbf{x}\_t^{\top} \\mathbf{w}\_{t-1} \leq 0$, the gradient for SGD becomes zero. When considering DP-SGD, noise is added to the gradient, and the direction of DP-SGD is significantly influenced by random Gaussian noise. These observations motivated us to propose the DP-GLMtron and DP-TAGLMtron algorithms, which address these convergence issues and provide more reliable results under different noise conditions.

**2. Increase in Experimental Results with Data Size and Approximation to 24.**

The observed increase in excess risk as data size grows, along with its approximation to 24,  stems from the nature of our experimental setup. We are considering a ReLU regression model, as outlined in the Preliminary Section and Equation 1, without incorporating any neural network architecture.

Moreover, according to the updated rules of algorithms (see Equation 3) and the above discussion, this behavior illustrates that DP-SGD struggles to converge effectively in this context. As data size increases, the challenges with convergence lead to an increase in error, which highlights the limitations of DP-SGD in handling certain high-dimensional regression tasks.

Another potential reason for the error approximating ~24 is that our model is a regression model. Regression models output continuous values, but classification problems require discrete class labels. This can result in predictions that aren't directly usable for classification, which may contribute to the observed large values in excess risk.

Meta-review: The paper studies the problem of learning a planted (student-teacher) ReLU regression model, privately. It does achieve nice theoretical contributions but its experiments leave much to be desired. While the experimental side does seem on the weaker side, all reviewers agree that the theoretical contribution is sound and has merit. It is therefore our recommendation to accept the paper as a poster to NeurIPS 24.
Decision: Accept (poster)