GeoClip: Geometry-Aware Clipping for Differentially Private SGD
Authors: Atefeh Gilani
Naima Tasnim
Lalitha Sankar
Oliver Kosut
Venue: NeurIPS 2025 poster ()
Keywords: Differential Privacy
Gradient Clipping
Adaptive Clipping
DP-SGD
Private Machine Learning
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: GeoClip makes DP-SGD geometry-aware by adapting clipping to the structure of the gradients. It reduces noise and improves convergence and utility without additional privacy cost.

Abstract: Differentially private stochastic gradient descent (DP-SGD) is the most widely used method for training machine learning models with provable privacy guarantees. A key challenge in DP-SGD is setting the per-sample gradient clipping threshold, which significantly affects the trade-off between privacy and utility. While recent adaptive methods improve performance by adjusting this threshold during training, they operate in the standard coordinate system and fail to account for correlations across the coordinates of the gradient. We propose GeoClip, a geometry-aware framework that clips and perturbs gradients in a transformed basis aligned with the geometry of the gradient distribution. GeoClip adaptively estimates this transformation using only previously released noisy gradients, incurring no additional privacy cost. We provide convergence guarantees for GeoClip and derive a closed-form solution for the optimal transformation that minimizes the amount of noise added while keeping the probability of gradient clipping under control. Experiments on both tabular and image datasets demonstrate that GeoClip consistently outperforms existing adaptive clipping methods under the same privacy budget.

GeoClip: Geometry-Aware Clipping for Differentially Private SGD
Atefeh Gilani
Naima Tasnim Arizona State University Tempe, AZ, USA ntasnim2@asu. edu
Lalitha Sankar Arizona State University Tempe, AZ, USA 1sankar@asu. edu
Arizona State University Tempe AZ, USA
agilani 2@asu. edu
Oliver Kosut
Arizona State University
Tempe, AZ, USA okosut@asu.c edu
Abstract
Differentially private stochastic gradient descent (DP-SGD) is the most widely used method for training machine learning models with provable privacy guarantees, A key challenge in DP-SGD is setting the per-sample gradient clipping threshold, which significantly affects the trade-off between privacy and utility. While recent adaptive methods improve performance by adjusting this threshold during training, they operate in the standard coordinate system and fail to account for correlations across the coordinates of the gradient. We propose GeoClip, geometry-awan framework that clips and perturbs gradients in a transformed basis aligned with the geometry of the gradient distribution. GeoClip adaptively estimates this transformation using only previously released noisy gradients. incurring no additional privacy cost. We provide convergence guarantees for GeoClip and derive closed-form solution for the optimal transformation that minimizes the amount of noise added while keeping the probability of gradient clipping under control. Experiments both tabular and image datasets demonstrate that GeoClip consistently outperforms existing adaptive clipping methods under the same privacy budget.
Introduction
As machine learning models are increasingly trained sensitive data, ensuring strong privacy guarantees during training is essential to reduce the risk of misuse, discrimination, or unintended data exposure. Differential privacy (DP) [1, 2] offers principled framework for protecting individual data, and has become a cornerstone of privacy-preserving machine learning. In deep learning, the most widely used approach for DP is differentially private stochastic gradient descent (DP-SGD) [3], which clips per-sample gradients and adds calibrated noise to their average.
Despite its widespread use, standard DP-SGD has key limitation: it relies fixed clipping threshold to bound the sensitivity individual gradients. Selecting this threshold poses a challenging privacy-utility tradeoff medtoff-setting it too low discards useful gradient information, while setting too high increases sensitivity and necessitates injecting more noise, ultimately degrading model performance. This trade-off was observed empirically by McMahan et al. [4] and later analyzed theoretically and shown to be a fundamental limitation of differentially private learning by Amin et al. [5]. Moreover, the optimal threshold vary over the course of training, across tasks, and between datasets, limiting the effectiveness of fixed setting.
39th Conference on Neural Information Processing Systems (NeurIPS 2025).

---

To address this, recent work has proposed adaptive strategies that dynamically adjust the clipping threshold during training. One class of methods uses decay schedules reduce the threshold over time. Yu et al. [6] and Du et al. [7] propose linear and near-linear decay rules, respectively, where the schedule predefined and does not depend on the dataset-
no privacy budget is required. Lin et al. [8] introduce a nonlinear decay schedule, along with transfer strategy that leverages public data to guide threshold selection. Recently, methods have been introduced which set the clipping level based on the data during the training process. These include AdaClip [9], which applies coordinate-wiss clipping based on estimated gradient variances. Yet another is quantile-based clipping [10], which sets the threshold using differentially private quantiles of per-sample gradient norms. Although [10] was designed for federated learning. it can be adapted to centralized DP-SGD. These adaptive strategies have been shown to improve model utility while preserving privacy guarantees.
Despite these advances, existing adaptive clipping methods remain agnostic to the geometry of the gradient distribution. They operate in the standard masis-treating each coordinate independently. This overlooks dependencies between coordinates, especially when gradients exhibit strong correlations across dimensions. In such cases, independently clipping and perturbing each coordinate can introduce redundant noise without improving privacy, ultimately degrading model utility. To address this, we propose GeoClip, method that transforms gradients into decorrelated basis that better reflects their underlying geometry. By applying DP mechanisms in this transformed space, GeoClip allocates noise more effectively, achieving better privacy-utiliit tradeoff.
different approach to correlations in gradients from the literature considers introducing corre- lations dependeciess across iterations and between entries of the noise vector-into the noise, rather than injecting i.i.d. Gaussian noise. This has been shown to improve the utility of private training [11, 12]. Siaquette-Chho et al. [13] strengthen this direction by analytically characteriz- ing near-optimal spatio-temporal correlation structures that lead to provably tighter privacy-utility tradeoffs. However, these approaches have been developed independently of adaptive clipping, and the effect of combining both methods remains unexplored. addition, [13] uses pre-determined correlations in the noise, rather than being tailored to the data, our approach is.
GeoClip data-driven but does not require any additional privacy budget to compute the clipping transformation. Instead, it reuses the noisy gradients already released during training to estimate the mean and the covariance of the gradient distribution. By reusing these privatized gradients, GeoClip adapts its basis over time without accessing raw data or incurring additional privacy cost.
We list our main contributions below:
1. We propose GeoClip, a novel framework that applies differential privacy in a transformed basis rather than the standard coordinate system. To guide the choice of transformation, we derive convergence theorem (Theorem 1) showing how the basis impacts convergence under DP-SGD, providing theoretical guidance for selecting transformations that improve utility.
2. Building on this insight, we formulate a convex optimization problem to find the transformation, and derive closed-fore form solution (Theorem 2).
3. We introduce two algorithms to estimate the transformation using only previously released noisy gradients. The first is based on a moving average to estimate the gradient covariance matrix.
4. For large-scale models, the full gradient covariance matrix is prohibitively large to store. Thus, our second algorithm uses a streaming low-rank approximation of the covariance matrix. This second algorithm is thus suitable for deep models with large parameter counts.
5. We validate GeoClip through experiments on synthetic, tabular, and image datasets, showing that it consistently outperforms existing adaptive clipping methods under the same privacy budget.
Notation. We denote the d x d identity matrix by Ia. The notation N ~ (O IaIa) denotes d-dimensional Gaussian with zero mean and covariance o I We use ||ж|| for the Euclidean norm of a vector x, A- for the inverse of matrix A, and AT for its transpose. The trace of a matrix A is denoted by Tr(A), and Cov(z y) refers to the conditional covariance of x given y.

---

2 General Framework
Let D J be a dataset of N examples, and let f: R + IR denote the empirical loss function defined as the average of per-sample losses:
N f(0) N fa()),
(1)
where 0 E IRd is the model parameter vector and each fa corresponds the loss the k-th data point Th. In DP-SGD, the algorithm updates 0 using a noisy clipped stochastic gradient to ensure privacy. Let gr IRd denote the stochastic gradient at iteration L. The update rule
O++1 02 19h,
where It is the privatized version of gt. obtained by clipping and adding noise.
GeoClip builds on the DP-SGD framework but changes how gradients are processed before clipping and adding noise. It begins by shifting and projecting the gradient into a new coordinate system:
Me(g: ax),
where a E I& is a reference point and M, Raxd is a full-rank transformation matrix that defines the new basis. To enforce differential privacy, we clip the transformed gradient wi to unit norm and add Gaussian noise:
We
+ No. N₂ N00,
W/
max (1, [1]]12)
where a is set based on the desired privacy guarantee. We then map the noisy, clipped gradient back to the original space:
g. M, + aq.
(5)
Remark 1. GeoClip generalizes AdaClip of Pichapati al. [9], which itself extends standard DP-SGD. AdaClip essentially assumes that M, is diagonal for per-coordinate scaling, whereas GeoClip allows M, be any full-rank matrix. This added flexibility allows GeoClip account for correlations between gradient components and inject noise along more meaningful directions.
A key feature of our framework is that the privacy guarantees remain unaffected by the choice of Mj and ag, as long as no privacy budget used to compute them. This allows M, and a to be chosen entirely based on utility, without compromising privacy. The main challenge. then, is how to select these parameters effectively. To address this, we first define performance metric for GeoClip. Inspired by Pichapati et al. [9], we derive the following convergence bound for our framework and it to guide the design of M, and a, ultimately improving both convergence and training efficiency.
Theorem (Convergence of GeoClip). Assume I has an L-Lipschitz continuous gradient. Further, assume the stochastic gradients are bounded, i.e., [e)] G. and have bounded variance, i.e., Eg Vx f()Il < o². Let l = arg mingeR* f(0) denote the optimal solution, and suppose the learning rate satisfies 7 < 3T.
Then, for the iterates { (01)T-11 produced by GeoClip with batch size I using the update rule fc+1 = 0₂ 7ht. where ge is defined in (5), the average squared gradiens norm satisfies:
2
(1())) < f(0o) - ((0))
LL 3
Lagz
T-1 ET
Σ
[MMTTM M.) -17 M:)-
+
T "LD²
2 3Lm
T(2
3Lm)
Gradient variance term
Noise-injeetion
Optimization gop
2 + T(2 ((2-LLm)
Σ
E [((aa) (Tr (M, M,E)) + (E[g 18y) az)
t=0
Clipping evror term
(6)
3

---

where 8³ = (fu...., .1) represents the history of parameter values up to iteration t, Σ, = Cov and
((a)) = (G ||xell) G+ 3/ (G + +(all))))
The above result generalizes Theorem 2 in Pichapati et al. [9]; proof details are in Appendix A.
Theorem provides insight into how we should choose the transformation parameters and M, In particular, we want to choose the transformation parameters a, and M,, for all t, to minimize the right-hand side of (6). The reference point directly affects the clipping error by setting the center around which gradients are clipped, thereby influencing how much of each gradient is truncated. In contrast, the noise injection term remains independent of de, as noise is added regardless of the gradient's position relative to a, From Theorem 1, the clipping error at iteration takes the form
B(az) (Tr (M, M, Σx) + [E 8*) a))1))
(8)
where ((ae) is a scale factor that grows with ||aell. natural choice is to set a Elg. 0*] which eliminates the bias term [.M 09 az = Given this choice, since gradients are norm-bounded by G, can apply Jensen's inequality also bound the norm of their mean, obtain the bound
(ax) 2G (1 + 3Tn).
We now show that the remaining contribution to the clipping error term Tr (M, M,2i)) in fact serves as an upper bound on the probability that the gradient clipped (i.e., ||l||| > 1). We do so using Markov's is inequality detailed below:
Tr (M, M, E.) = ||I (g: - E[ge 00)) 6*)
(10)
= ||||w||2 |
(11)
2 Pr[[[]]] > 1 0*).
(12)
We can now interpret the clipping error term as the likelihood that clipping occurs-ideally, the lower the better the gradient information will be better preserved. However, in setting clipping level, we must also be aware of the amount of noise: if M, is scaled down, there effectively more noise, as captured by the noise-injection term in (6). We handle this tradeoff via the following optimization problem for the transformation matrix My:
minimize Md.
Tr Tr (M, M.)
subject to
Tr (M. M. E.) S7
(13)
Theorem 2. Let = Cov(ge 8') be positive definite matrix. The optimal transformation matrix M; E Rdd iteration for the optimization problem in (13), along with its corresponding objective value, are given by:
(
1/2
A ATT, (M, (Ein VTa
7
M =
(14)
Ed
VX.
where H, = U.A.U is the eigendecomppsitiinnd of the covariance matrix, with A, diag (A containing its eigenvalues.
Aa)
Remark Applying the optimal transformation MC to the gradient gt at iteration t, the covariance of the transformed gradient W. M7 (gt- Eigt O'1), conditioned on the history 0*, is
1//2 EdEVa vT.
Cov(ws (0) M; E, M
ddaag
E1=1
X
Thus, the optimal transformation decorrelates and scales down the gradients while preserving the relative ordering of variance across directions, in contrast to traditional whitening, which eliminates
all variance structure. Note that setting at =E[ge | 00] and choosing Mc =

---

would amount to a whitening of the gradients and ensures that the constraint in (13) is active, i.e., Tr (M, M, 2x) ". Under this choice, the objective becomes:
d Tr(A.) 7
d
Tr (M, M.)
(15)
7
Comparing our objective in (14) with the objective resulting from the whitening transformation, we observe that applying the Scuchy-Schwand inequality yields:
d
A
1 7
Σ
EvA
(16)
with equality if and only if X1 objective than whitening in all non-isotropic cases, where the gradient distribution exhibits unequal variance along the eigenbasis directions.
Aa. This shows that our solution achieves a strictly smaller
The proof of Theorem is provided in Appendix B.
3 Algorithm Overview
Algorithm outlines our proposed GeoClip method. We explain its key steps below.
Moving average for mean and covariance estimation. While the theoretical results from Section assume access to the true gradient distribution, in practice this distribution is unknown, and it must be estimated using only privatized gradients. We estimate the mean and covariance using exponential moving averages computed from those privatized gradients. This enables to estimate the geometry of the gradients without consuming additional privacy budget. Specifically, we maintain estimates at of the mean, and E, of the covariance matrix, which updated according to:
a++1 < B1 + -1-B1)5r B1)9.
(17)
E1+1 + B.E, + (2) az) a
(18)
where 31 and 32 are constants close to 1 (e.g., 81 = 0.99, B3 = 0.999). The eigenvalues and eigenvectors used for the transformation are then computed from the estimated covariance.
Clamping eigenvalues. The covariance matrix is positive semi-definite and may contain zero eigenvalues, which can numerical instability. To address this, clamp eigenvalues from below at a small threshold h; (e.g., 10-15). Since we only observe privatized gradients, which may be noisy and unstable, we also clamp from above at h2 to prevent extreme scaling.
Covariance update with mini-batch. Let B denote a mini-batch of training examples sampled at each iteration, with [B] indicating the batch size. When using mini-batch gradient descent with [B] > 1, we must estimate the mean and covariance from the privatized batch averages of the per-sample gradients. Let 9i be the random variable representing the gradient of the i-th sample in the batch. Let g = |al| ΣiEB 9: be the batch average gradient. Assuming that the Ji are i.i.d., with the same distribution as g, the covariance of the average gradient satisfies
Cov (g) = Cov
B
9i IEB
= B
Cov(g)-
(19)
The same principle applies when we observe only the privatized average gradient g. To account for this averaging effect, the covariance update is scaled by the batch size; i.e., line 11 of GeoClip in Algorithm becomes
E++ + 32E, 3
B[ 32) aa) T.
(20)
Low-Rank PCA. When the dimensionality high, computing and storing the full gradient covariance matrix becomes impractical. To address this, we propose a method to maintain a low-rank approxi- mation using a simple and efficient procedure we refer to as Streaming Rank-k PCA (Algorithm 2). Specifically, maintain approximate cigendecomposition of the covariance in the form U,A,U,".
5

---

Algorithm GeoClip
Require: Dataset D, model Sa. loss L, learning rate y,, noise scale o, steps T, hyperparameters
h1, h2, S1
1: Initialize 0, mean vector og covariance Eg la. transform Mo M Ia
2: for 0 to T do
3: Sample a data point (1t,, yt)
4: Compute gradient 9: + VoL(fo(
5: Center and transform: W₁ < Met at)
6: Clip: We < we/ max(1, ||a0e l12)
7:
Add noise: We - We + N, where N NN
8:
Map back: Dt 4- MM w a₁
9:
Update model: 0s+1 t 01 179t
Update mean: ac+1 8i + (1 Bi)āt
11:
Update covariance: E1+1 f- 3,20 + (1- - B2) - az) - ar)
12:
Eigendecompose: Σt+1 UrAUU
13:
Clamp eigenvalues: A; x- Clamp( Ai min h1, max = h12)
Set M₁-1* -- (7/ Σ; Ax.) 1/2 A, -1/AUT
14:
Set M f (n/E: vA. -1/2 U.A!" 1/4
15:
16:
end for return Final parameters 0
Algorithm 2 STREAMING RANK-A PCA
Require: Eigenvectors Ur E R& eigenvalues A, E R gradient ÿt E Rdd, mean a++1 E Rd
factor Bg IR, rank k.
Center: < Ôt- -G+1
2: Form augmented matrix: Unug + UUg z]
3: Compute: Z + aug diag( V BzA1..... BBAKE VI Ba)
4: Perform SVD: Z VSR
5: Set Ut+1 + first & columns of V
6: Set Ac+1 < squares of the first singular values in S
7: Return: U141, A441
where U2 E Rdxk contains the top-k eigenvectors and A, E R the corresponding eigenvalues,
where t & d. Upon receiving new gradient ÿt, center using the running mean d1+1, yielding Jt a1+1, and perform a weighted update to the covariance:
AaA. 0
Σ BUAUU +(1 - Ba)22 (U, 2]
U 2)
(21)
1- Bz
Rather than forming this full matrix, we compute its square root:
Z UU, diag( (3dd...... V BadEs V1 BB) Rdx(k+1),
(22)
We then perform an SVD Z and retain the top singular vectors and squared singular values the updated eigenvectors and eigenvalues. We note that this computation takes O(dk² + 1-3) time [14], highlighting that it is only linear in d. The rest of the procedure follows Algorithm by replacing the moving average over the full covariance matrix in line 11 of Algorithm 1 with the low-rank approximation described above. Another necessary change to the algorithm the following: since U, no longer square matrix, the transformation M, takes the gradient into the lower k-dimensional space clip and add noise, such that the resulting Miny returns to the full d-dimensional space. The complete version of this variant is provided Algorithm in Appendix C.

---

20.0
GeaClip
AdaCIpp
17.5
DP
0.35
Quantile
15.0
Privacy parameter (e)
0.30
MSE
12.5
10.0
7.5-
0.20
5.0
2.5-
0.15
0.0
5
6
10
2
3
8
9 10
Epech
Epoch
Figure I: GeoClip results for the synthetic Gaussian dataset with 10 features. The left plot shows the average test MSE for each method over 10 epochs, with shaded regions representing the standard deviation across 20 random seeds. We observe that GeoClip achieves the fastest convergence and lowest average test MSE. The right plot shows the overall privacy budget expended for 10-5 This plot applies to all four algorithms, as they are tuned to achieve the same privacy level for a given number epochs.
Experimental Results
We present empirical results demonstrating the benefits of our proposed GeoClip framework compared to AdaClip, quantile-based clipping, and standard DP-SGD. For quantile-based clipping, we use the median of per-sample norms, which has been shown perform well across various learning tasks [10]. All (e, 6D- guarantees are computed using the Connect-the- accountant [15]. All experiments were conducted on Google Colab using CPU resources. The code implementation is available on GitHub [16].
We start with a synthetic dataset to demonstrate how GeoClip accelerates convergence, reflecting its design motivation from Theorem 1, and then evaluate its performance on real-world datasets. All datasets are split into 80-10-10 10 srain-validation-tes sets for consistent evaluation. The results in Sections 4. 4.2, and 4.3 are derived from Algorithm We present the results using the low-rank PCA variant in Section 4.4.
Our results indicate that our framework in Algorithm is robust the choice of hyperparameters' 81, 32, and kt. Standard values commonly used in optimization, such as 81 = 0.99 and 32 = 0.999, work well in setting. The parameter in only needs to be small positive constant (e.g., 10-15) to ensure numerical stability. Since the eigenvalues are clamped to the range [h,, h2] (line 13 in Algorithm 1), the trace term Σ, V\; is bounded between dyhn and dy/22, where d is the dimensionality. This allows to set the parameter h2. For /22, we have observed that the values and 10 perform consistently well across datasets. Throughout all experiments, tune only he to select between these options. A similar setup is used in Algorithm with 32 replaced by 3g (set to 0.99), which is also robust across experiments.
1, its effect can be absorbed by tuning
4.1 Synthetic Dataset
GeoClip is designed to improve convergence, particularly in the presence of feature correlation. To empirically demonstrate this, we evaluate it on a synthetic Gaussian dataset with 20,000 samples and 10 features-five of which are correlated, while the remaining five are independent. To obtain the correlated features, we first generate an 20,000 x 5 matrix Z and 5 x 5 matrix A, each with entries drawn independently from the standard normal distribution. The correlated features are obtained by multiplying Z by A. The remaining 5 features are drawn independently from a standard multivariate normal distribution. The full feature matrix X constructed by concatenating these two blocks. The target is generated using linear function with Gaussian noise: y Xw + b + where w ~ N (0, /10) a weight vector, b ~ A/0 1) a scalar bias term, and e ~ (O, 0.012) is i.i.d. noise. We train linear regression model using various private training methods for 10 epochs with
7

---

batch size of 1024, tuning the learning rate for each method to ensure stable convergence. As shown Figure (left), GeoClip converges as early as epoch 2, while the next best method -eaaodd-uannntbbaaaseee nearly twice as many epochs. Figure 1 (right) plots the privacy cost (E) versus epoch, showing how faster convergence helps minimize overall privacy cost.
Although GeoClip introduces some computational and memory overhead, this cost is well justified by its empirical gains. GeoClip converges considerably faster than baseline methods, requiring fewer training iterations to reach comparable utility. While each iteration is slightly more expensive than in other baselines, this cost is partially offset by the reduced number of iterations. Combined with improved privacy, these benefits make the additional overhead a worthwhile trade-off.
As illustrated by the standard deviation bands in Figure 1, GeoClip not only achieves faster convergence but also demonstrates more stable training with reduced variance-an an important property when privacy constraints limit training to single run. In such scenarios, lower variability across enhances the reliability of the final model without requiring additional privacy budget.
4.2 Tabular Datasets
In addition to the synthetic dataset, we run experiments to compare the performance of different clipping strategies on three real-world datasets: Diabetes [17], Breast Cancer [18), and Android Malware [19]. We briefly describe each dataset and its corresponding learning task below.
The Diabetes dataset contains 442 samples and 10 standardized features. The continuous valued target variable indicates disease progression, making this a regression task. The Breast Cancer dataset contains 569 samples and 30 numerical features, which are standardized zero mean and unit variance before training. The target is to predict a binary label indicating the presence or absence of cancer. The Android Malware dataset contains 4465 samples and 241 integer attributes. The target is to classify whether program is malware or not.
For each of the three datasets, we perform grid search over the relevant hyperparameters identify the best model under given (s, d) privacy budget. We train for 5 epochs using 20 random seeds and report the average performance along with the standard deviation in Tables 1, 2, and 3. We observe that our proposed GeoClip framework consistently outperforms all baseline methods across both regression and classification tasks. GeoClip achieves better performance with noticeably smaller standard deviations, indicating greater stability across random seeds.
Table Diabetes dataset test MSE comparison for 10 10-5, batch size = 32, and model dimension d 11.
Framework
0.50
0.86
0.93
GeoClip (ours)
0.073 0.015
0.044
0.039-100009
AdaClip
0.077100007
0.062.10.028
0.055-10.01
Quantile
0.090=+0.027
0.083:40.044
0.072++0.014
DP-SGD
0.108
0.095::00047
0.072-10.40
Table 2: Breast Cancer dataset test accuracy (%) model dimension 62.
comparison for = 10-5, batch size 64, and
Framework
0.67
0.8
0.87
GeoClip (ours)
87.8711..32
88.37113.37
93.63.11.63
AdaClip
84.90+5.91
85.42+55.4
87.71+5.87
Quantile
11.51
11.63
92.2811.68
DP-SGD
77.32-16.17
79.42-49.71
85.95
8

---

Table Malware dataset test accuracy (%) comparison for 6 = 10-5, batch size 512, and model dimension 484.
Framework
0.26
0.49
= 0.67
GeoClip (ours)
90.77:11.83
91.64:11.26
92.67:11.63
AdaClip
88.35:+3.27
90.23++.11 1.335
Quantile
77.84111.29
78.8411.27
81.8611.31
DP-SGD
88.04:22.21
90.55+1.55
90.57=1.61
4.3 Final Layer Fine-Tuning
In many transfer learning scenarios, fine-tuning only the final layer is standard practice due to both its computational efficiency and minimal privacy cost. Last-layer fine-tuning a well-suited application of GeoClip, it involves small number of trainable parameters, making covariance estimation more tractable. This setup also benefits from GeoClip's faster convergence, which is particularly valuable in privacy-constraince settings where only limited training iterations are feasible.
To demonstrate this, we design an experiment where a convolutional neural network (CNN) first trained on MNIST [20] using the Adam optimizer and then transferred to Fashion-MNIST [21] by freezing all layers except the final fully connected layer. The CNN consists of two convolutional and pooling layers followed by linear compression layer that reduces the feature size to 50, resulting in total of only 510 trainable parameters. We fine-tune this layer using different methods under varying privacy budgets, and present the results in Table 4.
Table 4: Final layer DP fine-tuning on Fashion-MNIST for epochs and d = 10-6 over 5 seeds.
Framework
= 0.6
6=1
GeoClip (Ours)
73.0911.72
73.09110.63
AdaClip
68.35-+0.41
69.24410.28
Quantile-based
71.78:11.28
72.0911.12
DP-SGD
69.40:0.82
69.83+0.83
4.4 Low-Rank PCA Results
To evaluate our low-rank PCA algorithm (Algorithm 2), we construct synthetic binary classification dataset with 20,000 samples and 400 Gaussian features, where 50 correlated and 350 are uncorrelated. The feature matrix is constructed in the same manner as Scction 4.1. Labels are generated by applying linear function to the features, adding Gaussian noise, and thresholding the sigmoid output. We train a logistic regression model with 802 parameters and compare our method against existing benchmarks using rank-50 low-rank PCA approximation. As shown in the left panel of Figure 2, our approach converges faster than competing methods, even with this low-rank approximation.
We also evaluate our method on the USPS dataset [22] using logistic regression with 2,570 trainable parameters (256 input features x 10 classes 10 biases). The USPS dataset contains 9,298 grayscale handwritten digit images (0-9), each size 16 16 pixels. This compact benchmark is commonly used for evaluating digit classification models. For this dataset, apply low-rank PCA approximation with rank 100. Results are shown in the right panel of Figure 2. As with the synthetic dataset, GeoClip with low-rank PCA also achieves faster convergence on USPS compared to baseline methods. We provide e- c-vs-iteration plots for both datasets, illustrating how faster convergence reduces overall privacy cost in Appendix D.
We compare the accuracy of GeoClip using Algorithm and Algorithm with A = 50 on the same synthetic dataset, with the results shown in Figure 3 in Appendix D. The results demonstrate that even with = 50, Algorithm 2 achieves accuracy comparable to Algorithm which computes the full covariance.

---

90
90-
80-
70
Accuracy
Test Accuracy
70-
50-
60
30-
GeoCilp
GeoClip
50
AdaClpp
AdaClip
DP-SGD
10-
DP-SGD
Quantile
Quantil
10
30
40
50
60
70
80
1
10
15
20
25
iteration
lteration
Figure 2: The left panel shows results on the synthetic Gaussian dataset with 400 features using rank-50 PCA approximation for GeoClip. The plot displays average test accuracy (%) over 80 iterations with a batch size 1024. GeoClip achieves the fastest convergence and highest average accuracy. The right panel shows results on the USPS dataset using rank-100 approximation over 25 iterations with batch size of 1024, where a similar convergence trend is observed. Shaded regions represent standard deviation across 20 random seeds.
We also conduct an ablation study on 7, h1, and he using the USPS dataset under the same experimental settings. The results are presented in Appendix E. The findings show that varying results in only minor performance changes. Likewise, hı has noticeable impact, and h2 introduces small variations.
Conclusions
We have introduced GeoClip, geometry-aware framework for differentially private SGD that leverages the structure of the gradient distribution to improve both utility and convergence. By operating in a basis adapted the estimated noisy gradients, GeoClip injects noise more strategically, thereby reducing distortion without incurring additional privacy cost. We have provided a formal analysis of convergence guarantees which characterizes the optimal transformation. Our empirical results synthetic and world datasets show that GeoClip consistently converges faster and outperforms existing adaptive clipping methods, improving both the mean and standard deviation of the performance metrics over multiple runs. Via low-rank approximation method, we have shown that GeoClip scales the high-dimensional data setting, thus making it suitable for practical deployment in large, privacy-sensite models.
Limitations. The linear transformation involved in GeoClip requires an additional computation via an eigendecomposition. Our low-rank approximation addresses that to some extent. The algorithm introduces additional hyperparameters (most notably h2) compared standard DP-SGD, which must be tuned for optimal performance. Our experiments have been performed on limited collection of datasets; additional testing needed see how our algorithm performs in more generality.
Broader impact. As discussed in the Introduction, our work is motivated by societal concerns, with a focus on improving the theoretical limits of differentially private optimization.
Acknowledgements
We thank the anonymous reviewers for their valuable feedback, which significantly improved the quality this paper. This work was supported by the National Science Foundation under Grant Nos. CIF-1901243 243, (1F-2312666 and CIF-2007688.
10

---

References
[1] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Proc. Theory of Cryptography (TCC), pages 265-284, Berlin, Heidelberg, 2006. ISBN 3-540-32731-2, 978-3-540-32731-8
[2] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. Serge Vaudenay, editor, EUROCRYPT, pages 486-503, 2006.
[3] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference computer and communications security, pages 318, 2016.
[4] H. Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. In International Conference on Learning Representations, 2018. URL https: htttpp:://ppereee /ttp////ppeeeeeee/e/eeeee net formmiddddmm 120b.
[5] Kareem Amin, Alex Kulesza, Andres Munoz, and Sergei Vassilvitskii. Bounding user con- tributions: A bias-variance trade-off in differential privacy. In Proceedings of the 36th International Conference on Machine Learning. volume 97 of Proceedings of Machine Learn- ing Research, pages 263-271. PMLR, 2019, URL http://proceedingss smm.eedddingmmmrr............ mlr press/v97/ amin19a. html.
[6] Dongsheng Yu, Hao Zhang, and Wei Chen. Improve the gradient perturbation approach for differentially private optimization. In NeurlPS 2018 Workshop Privacy Preserving Machine Learning. 2018. Workshop paper.
[7] Jian Du, Song Li, Fengran Mo, and Siheng Chen. Dynamic differential-privacy preserving sgd. ArXiv, abs/2111.00172. 2021. URL https://api. semanticscholar.c wwwpcccooaarrrgoCoooeooee OrrgCCopuSIID: 240354620.
[8] Guanbiao Lin, Hongyang Yan, Guang Kou, Teng Huang, Shiyu Peng, Yingying Zhang, and Changyu Dong. Understanding adaptive gradient clipping in dp-sgd, empirically. International Journal of Intelligent Systems, (7(11):9674-9700 2022. doi: https://doi.org wttg//1...o 1...0022m/..3000000000 URL https://onlinelll iirrrrrrrrrrrlr.e wiley. cww/doi/ aas/ 10. 1002/int. http:/itt.200000 23601.
[9]
Venkatadheeraj Pichapati, Ananda Theertha Suresh, Felix Yu, Sashank Reddi, and Sanjiv Kumar. Adaclip: Adaptive clipping for private sgd. arXiv preprint arXiv:1908.0740 170449008.744, 2019.
[10] Galen Andrew, Om Thakkar, Brendan McMahan, and Swaroop Ramaswamy. Dif- ferentially private learning with adaptive clipping. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural In- formation Processing Systems, volume 34, pages 17455-17466. Curran Associates, Inc., 2021. URL htrphtttss/pprrceeeiing neurips. petprips.ccppapp...cm accppapr_fiiess www.ffiies/aeeee www.f//eeppppe/e/.1111 2lcff00.66600224/777777550188889
pdf.
[11] Sergey Denisov, H Brendan McMahan, John Rush, Adam Smith, and Abhradeep Guha Thakurta. Improved differential privacy for sgd via optimal private linear operators on adaptive streams. In Advances in Neural Information Processing Systems, volume 35, pages 5910-5924, 2022. wtt.ttts:: httpps///pooeeeeiingg neurips cc wwtpppppe..lllleepppeeee/eee///e /iles//pper//002// Abstract Confereoooeeeeeeeeeeeee html.
[12] Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and private (deep) learning without sampling or shuffling. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 5213-5225. PMLR, 18-24 wttp:sss.w........eeeeeeeeeeeeee
Jul 2021. URL https::/pproceeednngg mlr wrw.ss /vvsss///// 1 html.
[13] Christopher A. Choquette-Choo, Krishnamurthy Dvijotham, Krishna Pillutla, Arun Ganesh, Thomas Steinke, and Abhradeep Guha Thakurta. Correlated noise provably beats independent noise for differentially private learning. In Proceedings of the Twelfth International Conference on Learning Representations (ICLR), 2024. URL xHmCdSArUC.
wet.ee...eeeeeeeeeeeeeeeeeeeeeee www.://unteeeoeme//e//e ftr.mformmc i
[14) Xiaocan Li, Shuo Wang, and Yinghao Cai. Tutorial: Complexity analysis of singular value decomposition and its variants, 2019. URL ittps://arxiv.ot wwtp:/s.////oota..o.ooo..o... abs abs/1906. 12085.
11

---

[15] Vadym Doroshenko, Badih Ghazi, Pritish Kamath, Ravi Kumar, and Pasin Manurangsi. Connect the dots: Tighter discrete approximations of privacy loss distributions, 2022. URL https://arxiv.orrt wwt./oggggabb..eee /00./22277704000...
[16]
GeoClip Implementation. https://ght /hwpbbb.ihhbb...o///ege www.atefeh-aaeeeet www.effeehgllammm/eolllllpp May 2025.
[17]
Bradley Efron, Trevor Hastie, lain Johnstone, and Robert Tibshirani. Least angle regression.
The Annals of Statistics, 2004.
[18] William H. Wolberg, Olvi L. Mangasarian, and W. Nick Street. Breast cancer wisconsin (diagnostic). UCI Machine Learning Repository, 1993. DOI: https://doi. http//ii.oggg//////// C5DW2B.
.rg. 24432/
[19] Parthajit Borah and Dhruba K. Bhattacharyya. TUANDROMD (Tezpur University Android Malware Dataset). UCI Machine Learning Repository, 2020. DOI: https://6oi.orr//10 24432/C5560H.
[20] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied
to document recognition. Proceedings of the IEEE, 86(L1):227--2222 1998.
[21] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv: /0...0000777770 07747, 2017.
[22] Jonathan Hull. A database for handwritten text recognition research. IEEE Transactions on Pattern Analysis and Machine Intelligence, 16(5):550-554, 1994.
12

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: The abstract and introduction clearly state the paper's main contributions, including the GeoClip algorithm, its convergence guarantees, and empirical evidence of its improved privacy-utility trade-off.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in 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 be expected to generalize to other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
In the last part of the Conclusions section, we discuss the limitations of our work.
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency 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 acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
13

---

Answer: [Yes]
Justification: The assumptions are clearly stated within the theorem statements, and complete proofs are provided in the supplementary material.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: For the reproducibility of the experimental results, the paper provides detailed steps to implement the proposed algorithms, specifies the setup for each dataset, and lists all relevant parameters.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
be accomplished in various ways. For example, if the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, may be necessary to either make it 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 to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
Depending on the contribution, reproducibility
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on nature the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (c.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but should be possible for other researchers have some path reproducing verifying the results.
14

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Due to anonymity and other constraints, we are currently unable to release the code. However, the real-world datasets used are publicly available, and the experimental procedures are described in sufficient detail for reproducibility.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code. Please see the NeurIPS code and data submission guidelines (https://nips.c cc/
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://nips.c htce//ublccgguue
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,
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 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: [Ys]]
Justification: All training and test details including data splits and hyperparameters are discussed in the Experimental Results section. We either custom optimizer updates as outlined in our proposed algorithms, or specify it otherwise.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification: For all our experiments, we report average performance with standard deviation over different seeds.
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, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
15

---

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, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but 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 errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (c.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification: We state in the Experimental Results section that all experiments were conducted on Google Colab using only CPU resources. The computational demands are modest, and specialized hardware (e.g., GPU or TPU) is required reproduce the reported results. In addition, we discusss the order of the computation time of our algorithm in Section 3.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't make it 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 https://neurips wttpp//ccc//tticceaaiiiiiiiiaiaa
Answer: [Yes]
Justification: We have reviewed the NeurlPS Code Ethics and confirm that our research fully complies with its principles and guidelines.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consideration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
Answer: [Yes]
16

---

Justification:
We adddress the societal impacts of our work in the last part of the Conclusions section. We do not anticipate any negative societal impacts.
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 societal impact or 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.
The conference expects that many papers will be foundational research and not tied to 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 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 train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question:
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)?
Answer: [NA]
Our work does not involve the release of models or datasets that pose a high risk of misuse. We use publicly available datasets and do not distribute any new generative or potentially harmful models.
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse 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 access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: All datasets used in the paper are publicly available and have been properly cited with their original sources.
Guidelines:
The answer NA means that the paper does not existing assets.
17

---

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

---

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

---

A Proof of Theorem 1
Theorem (Convergence of GeoClip). Assume f has an L-Lipschitz continuous gradient. Further, assume the stochastic gradients are bounded, i.e., fx)]l G. and have bounded variance, i.e., E& (x) f(0) S og. Let 0 = arg mingeR= f(0) denote the optimal solution, and suppose 2 Then, for the iterates {0s 1to produced by GeoClip with batch size using the update rule 0u+1 = 0t 79t, where ge defined in (5), the average squared gradient
the learning rate satisfies y 3L
norm satisfies:
Vf(0))1 = f(0o) f(0)
3Lm d²
Lnj²
T-1 Σ ET (M, Mi) -1
+
T "at²
2 3Lm
T(2 3Lr)
t=
Gradient variance term
Noise-injection
Optimization gop
2 T(2 3Lm)
E ((a,) (Tr (M, M,E,) (1, - a2)]
Clipping error term
(23)
where 8 = (Bu...., 0.) represents the history of parameter values up to iteration t, Σ, = Cov(g:)0")
and
B(ac) = (G + ||ael) (+
3L4 (G + [la.1))
(24)
2
Proof.
We can express the noisy gradient as:
g. = M, 1, W. + at
(25)
M, Ww
M -N, az
(26)
max (1, ||w21]]
9t at max (
+ M₁ MM.-N, N2 + at.
(27)
Thus, the parameter update takes the form
Oc+1 0, 119h
(28)
0: "
9: a max (e)Me a)]l,
+ M, N, + at
(29)
We define the following quantities:
9t a2
Ct max (g - at) 11,
(30)
A, G (g: az)
(31)
is the clipped version of A, quantifies the distortion due to clipping, being zero when no clipping occurs and negative when clipping applied. By the L-Lipschitz continuity of the gradient of f(0). we have:
L 110 111
f(0 f(..) (V.()))) 6.41 -8,) +
(32)
20

---

Let lr = (0) describe the entire history of states. Taking the expectation conditioned on 0*,
we obtain:
E 1 (0t+1) 0*)
S (0.) + E (B.), (8.), 01) 00) +
I.
E
[10 0,11 gd)
(33)
2
f (0)) E [VV (0:), Mr a1>109
+ Lnd²
2 EE
||0 M,¹ N₂ + ael
ae12100
(34)
2n
+ Ln
= f (0.) - E (v) + a=)
B
||ce + aal1/100
||, "Nil1" 0c)
(35)
2
2
= f (0+) - a (Vf an) 10' + Ln²
E
||c + 10
1||00
+ 2
Lnfo²
||M -1,
(36)
2
f (0:) a (V] + 2,) 00 + Ln²
Lnfo²
E
|19t + A. 12 (0)
|| -
||
(37)
2
2
= (0:) - / (0)]l n (V/ / (0.) A1) |0"]
+ Tnp E
Lnpo ||M,
|19. - Vf
VV (0)) + V (0:) + A 11? gr]
+ 2
(38)
2
where (35) follows from E[N.] = 0 and the independence of N₂ from Jr (and thus from a + az).
The equality (36) follows because E[NN = o² la. and ||M represents the Frobenius norm of M,¹ The equality (37) follows from c + 0 = A. + 9c- The last equality follows because
E (VS (0t), 9t + A = E [(V/ (0t) 0')
+ E. [(V) (0t) ()))..)))0) [0]
(39)
E (V/ (0:) A)) 10"] V (0.) T Elg. [0']
(40)
E [ : + | (0.) 11?
(41)
where (41) follows because 9s is an unbiased estimator of the true gradient, i.e., Esg | 104] = (0().
From Jensen's inequality, we have:
E |19. vf(0.) v.(( Arll 8+]
<3 E ( [0] + |V +E [1A.11(0*1]
(42)
From the Cauchy- -Sahah-- inequality, we have:
E (V)()))) A 0* = (())) E [[A+1||0]
(43)
Plugging (42) and (43) into (38), we obtain:
E [f (0++1) 1)00 f (0,) - 7 V (0,))1 2 + n IV (0,) E [1 |
3 + 2
E
|19. V ((.)))) gd] + [V
|
Laj²0²
||
(44)
2
To bound E [||A+1] and E
|||.|| 3 |r] we first bound Pr (1 > 010*) and || given 0 and
|| 0. Using Markov's inequality, we obtain:
Pr (1(l > 0
Pr (l a² > 1
(45)
< Pr (e - a.) a;)]l² 2 1 10
(46)
S [I] Me 2
(47)
E JIMa (o+ - Elg 104] + Elgr 0-) - aa)) 112 112/0z)
(48)
EE |IMe (oe - Elgo 1| gr + || ('') 10'1 az))
(49)
Tr (Cov (Megrlo)) + | (E(g, -
(50)
21

---

Using (30) and (31), we obtain:
max {llMe - =0)]l, - 1) (gc - az)
1
|
(51)
$ |1:: Azll
(52)
- |1 + ||ae||
(53)
G + | Il
(54)
where the final inequality follows from || V fx())ll S G. Therefore,
E [IA 0"] Pr (I > 0 0
E [IA > 0,
(55)
S SG + ||x|l) Tr (Cov (Mas (0)) + ( ( aa))
(56)
Similarly, obtain the following bound: |1011//00 = (G + [|a])2
E
Tr (Cov (Mag 0²)) + [[ aa))))
(57)
By plugging (56) and (57) into (44) and rearranging the terms, obtain
[f (0t+1) 109
S (0,) + 3Ld² -0) + ((laall) (++
3Lm (G + [[a!ll)
([+(aalll))
2
Tr (Cov (Mage 0²)) + ( -+)11
-
+
3Tap2
[1oe - V +
Tnpo²
M|, 11
2
2
(58)
Above, we have used the fact that [|)) < G. which itself follows from Jensen's inequality and the assumption that fx)) & G. Let
B(a:) (G + ||aell) (++
3 3TM (G (G [|..
(59)
2
Rearranging the terms, applying the law of total expectation (now taking expectation over the entire history of states 8¹), and using the bound
- 2 - og. we obtain:
3Lm²
Vf())) < (f.) Ef(+++1) + 3L12oz Lnjo0²
E E
n E [$(at) (Tr (Cov (Magi ((0) + [| - at at))l
(60)
Summing over 1 to T and applying the telescoping sum, we get:
3Lm² 17
T-1
3L o 2T 2n T-1
B Σ
< f(0.) (E((r))+
Σ [EI[M,-'11
2
E [3(a)) (Ir (Cov (Mege(0") + [IM 10' - az)l
7
(61)
Dividing by T, assuming 7/ S 3z applying the identity ||M, -1 =Tr (MMTMM)) and using the fact that Ef(Or) (8"), obtain:
2
T
E 1(0,)1
T
1=
f(O)) - f(0))
3Lm o2
Lnd²
E Tr (M,TM.)
(1) 3Lm² 2
2 3Lm
T(2 3L4)
2
T-1
+ 7(2 - -3Tm)
E [B(x)) (Tr (M, M,Cov(gr(0*)) + [E(g - -ax)
(62)
t
22

---

B Proof of Theorem 2
We would like to solve the following optimization
minimize Mr
Tr (M, Mc) -1
subject to Tr (M₃ Me Ex) S
(63)
Defining A, as the Gram matrix of M. i.e., At = Mi Mr we can reformulate the optimization problem as:
minimize Tr(A7')
subject to Tr(A, Mx) 5.
(64)
Both the objective and the constraint convex in A, so solve the problem, we introduce the Lagrangian function:
((Ar,)) p)) TT(A7") μ (T+(A,))) -)),
(65)
Taking the derivative of E(A,, p1) with respect to A, and setting the derivative to zero for optimality, we get
A, p Ex.
(66)
and so
A VP
(67)
Substituting A, in the constraint Tr (A, 2x) 7 we get
Σイ = y
(68)
Solving for μz:
_ Tr E
vp
(69)
7
Thus, the optimal A, is:
A 7
(70)
Tr
Using the eigen decomposition, we write Mn as:
Σ, = U,A.U
(71)
where U, is orthogonal matrix whose columns the eigenvectors of E, and
A₂ = diag(A1...... Xa)
is a diagonal matrix containing the corresponding eigenvalues. We now have
Σ = UUAFU
Σ = U,A,
(72)
Thus, the final expression for A is:
U,A, U,A Uū;..
A,
(73)
Tr(A
Therefore, we have
M, Mr
UAA-;Ui U.,
(74)
Tr(A,)
and
1/2
A, A
Mr
(75)
TY(A?)
Since Tr(A!/3)- = =Ld Vr, we can simplify M, as follows:
1/2
Mi
A, 1/T
(76)
dd VX
23

---

Algorithm 3 GEOCLIP WITH RANK-k PCA
Require: Dataset D, model Sa. loss L. learning rate 1/, noise scale a, steps T' rank k. hyperparameters h1, h2, 91.83
1: Initialize 0, mean vector ao 0, Uo -e....., en] where E, IR is the i-th standard basis
vector, Ag &
2: Compute transform Mo t- (7/k) 2/2 Ao UO and M +- (7/k)-11 1/2 Un
3: for = 0 to 7 do
4: Sample data point (Ita V1)
5: Compute gradient 9r -- VoL(fo
6: Center and transform: We f (gc ac)
7: Clip: We < wt/ max(1, ||ws ll2)
8:
Add noise: We We + N, where N o7,00²
9:
Map back: Tt MM Wr az
Update model: 0c+1 < 01 119t
11:
Update mean: ae+11 + B10; + (1 -
(1-BB)). BI)āec
12:
Update eigenspace: (U++1, A++1)=
STREAMING RANK-R PCA(U,, At, 0. B3, Clamp (Ai, min h1, max h2)
Clamp eigenvalues:
14:
Set M + (7/ Vi
1/2
A+1
-1/4UT
U+1
15:
Set M + (7/E. v U U141 1411
1/2
1/4
end for
17:
return Final parameters
C GeoClip with Low-Rank PCA
Computing and storing the full gradient covariance matrix becomes infeasible high dimensions. To address this, propose low-rank approximation method in Algorithm 3, which incorporates rank-& PCA step described in the STREAMING RANK- PCA algorithm.
To compute Mn and Min in line of Algorithm 3, we use the simplification Tr 1/2 = Σ = k. Also, in line 13, each X; depends but we omit the subscript for notational simplicity.
STREAMING RANK-k PCA
Require: Eigenvectors U, Ridkk, eigenvalues A, E kx gradient ÿt E Rd., mean a++1 E Rd
factor B3 E R, rank &
1: Center: + Jt- a++1
2: Form augmented matrix: Unug [Ue 2]
3: Compute: % Unng diag( / Ba.i...., VBade, v1 - -Ba)
4: Perform SVD: VSR
5: Set U141 + first & columns of V
6: Set A4+1 <- squares of the first & singular values in S
7: Return: U141,
D Additional Plots Related to Section 4.4
The middle and left panels of Figure show the privacy cost (e) versus iteration eurves corresponding to the accuracy-iteratio plots in Figure (Section 4.4, Low-Rank PCA Results). These plots highlight how faster convergence reduces overall privacy cost. For example, on the USPS dataset (Figure 2), GeoClip achieves high accuracy within the first few iterations, requiring only e as 0.15, whereas quantile-based clipping takes about 24 iterations to reach similar accuracy, incurring a higher privacy cost of s s 0.5.
24

---

03
0.35
Prieacyy parameter (e)
50-
0.30
0.41
Test Pest-Accurrry
70
20
0.15
0.2
GeoCap
Geot (km50)
10
Itoration
Ioration
Beewtoon
Figure 3: The left plot shows the overall privacy budget spent training the synthetic Gaussian dataset with 400 features for 8 = 10-5, while the middle plot shows the same for the USPS dataset with 10-5, These plots apply all four algorithms, which are tuned achieve the same privacy level for given number of iterations. The right panel compares GeoClip's performance using the full-covariance and low-rank approximation algorithms.
We compare the accuracy of GeoClip using Algorithm and Algorithm 2 with A: = 50 on the same synthetic dataset described in Section 4.4, as shown in the right panel of Figure The results show that even with k = 50, Algorithm 2 achieves accuracy comparable to Algorithm which computes the full covariance.
Ablation Study
We conduct ablation study y, h, and h2 using the USPS dataset, under the same settings in Section 4.4. As shown, varying 7 does not significantly affect performance. The results indicate no noticeable impact from hi, and only minor variations with h2.
Table 5: Test accuracy (%) for different values of y on the USPS dataset with h2 10 and h1 = 10-15
Method
7
0.2
?
0.6
7 1.0
GeoClip (k = 50)
85.537
86.182
85.752
Table 6: Test accuracy (%) for different values h2 on the USPS dataset with h1 15-15 and 7
Method
h2 1
10
h12
100
l/2 1000
GeoClip (k: 50)
86.021
85.752
85.752
85.752
Table 7: Test accuracy (%) for different values of hu on the USPS dataset with h2
10 and =
Method
h1 = 10
h1 = 10-10
h1 = 10-15
GeoClip (k: = 50)
85.752
85.752
85.752
25


Reviews:
[{"review_id": "Fg4bnd48Um", "reviewer": "Reviewer_Y5Ye", "summary": "This paper introduces a new method called GeoCLIP to obtain better privacy/utility tradeoffs in the DP-SGD algorithm. This is an improvement over Adapclip, which is a baseline they compare against.   \n \nTheir hypothesis is the following: noise + clipping operations operate on the coordinates disjointly, failing to recognize situations in which they are correlated. They may yield to an excessive amount of noise added and may degrade utility. Therefore, the authors propose to apply an affine transformation to the gradients before the noise+clipping operation and to invert this transformation after to project back into the gradient space.  The goal of this affine transformation is to decorrelate the coordinates of the gradients, to allow DP-SGD to operate in a regime it is the most comfortable with.  \n\nMore precisely:\n- the gradient is transformed as $M(g-a)$\n- it is clipped and noisified: $\\text{clip}(g)+\\text{noise}$\n- the gradient is projected back $M^{-1}g+a$\n\nAn analysis of the error introduced is performed. Several terms are identified:\n- optimization gap\n- gradient variance term\n- noise injection term\n- clipping error term  \nThis allows the optimization of each term separately, by solving the corresponding optimization program. Authors found something akin to whitening transformation (but not quite the same), and showed that their version outperforms whitenening in this scenario.\n\nMoreover, since the optimal form relies on mean/covariance statistics of gradients (which are private), the authors propose to rely on an exponential moving average. Finally, storing the full covariance matrix is prohibitively expensive, so the author proposes to rely on a new algorithm called *Streaming Rank-kPCA* to update it timestep after timestep.  \n\nThe evaluation is performed on:\n- synthetic data, in which some coordinates are artificially correlated\n- tabular data (Android Malware, Diabetes, Breast Cancer) in low dimension and small sample size \n- USPS dataset on images  \n  \nThe baselines are DP-SGD, AdapClip, and a method based on quantiles.  \nThe privacy is computed using *Connect-the-Dots* accountant.", "questions": "### Decorrelation sanity check\n\nIf you modify the experiment of Section 4.1 so that *all the features are decorrelated*, do you observe a difference between your method, Adaclip, DP-SGD and quantiles? Which one performs best here?\n\n### Quantile-based clipping\n\nDoes it make sense to combine your method with *quantile-based clipping*? Do you expect to witness an improvement?\n\n### Full covariance\n\nYour method essentially leverages the full covariance matrix, even though you propose a way to relax this constraint. Are you aware of other privacy-preserving algorithms in the literature that leverage the full covariance, and could benefit from your *Streaming Rank-kPCA* trick?", "limitations": "The authors discussed all the main limitations:\n* \"**additional testing is needed to see how our algorithm performs in more generality**\"\n* \"The linear transformation involved in GeoClip requires an additional computation via an eigendecomposition\"\n* \"The algorithm introduces additional hyperparameters (most notably h2) compared to standard DP-SGD, which must be tuned for optimal performance\"", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "## Strength\n\n### Principled method\n\nThe method is well-motivated. It follows the strategy of Adaclip: decompose the error in terms when applying a transformation to the gradients. Formulating the optimal choice of affine transformation as an optimization problem is clever. The extension to situations in which the full covariance is not available is also interesting. The method looks sound (I did not check the proofs).  \n\n### Convincing small-scale experiments \n\nThe experiments displayed here are very convincing, showing a clear improvement over AdaClip and DP-SGD baselines, on small-scale datasets.    \n\n## Weakness\n\n### Unsufficient evaluation at medium and large scale\n\n**Small datasets**. The biggest dataset is USPS which is: (i) easy (ii) small and low dimensional. It is unclear if the benefits observed would transfer to bigger datasets that are higher dimensional. \n\n**Streaming Rank-kPCA**: as it stands, a benchmark is lacking on the memory usage/speed of the algorithm. How big can the network be on a standard GPU, before *Streaming Rank-kPCA* becomes a bottleneck? How does that compare to competitors?\n\n**Decorreleted basis.** The motivation of the work - correlated coordinates in gradients - is believable for some highly structured datasets like USPS, which have patch of pixels that tend to look the same, at the same places. However, for datasets like CIFAR-10 or TinyImageNet, images are more decorrelated; and so maybe are the gradients too! \n\n**LLM**. It could be interesting to take a small LLM (e.g. transformer with <40M parameters, small vocabulary, autoregressive training) on a small text dataset (any subset from The Pile would do, for example) and see how your method compares against DP-SGD on it.  \n\n### Missing baselines and related work\n\nAdapclip is not the only improvement over DP-SGD for privacy training. Some other papers could be discussed or compared against:\n  \n* Lee, Jaewoo, and Daniel Kifer. \"Scaling up differentially private deep learning with fast per-example gradient clipping.\" arXiv preprint arXiv:2009.03106 (2020).  \n* Li, Xuechen, Florian Tramer, Percy Liang, and Tatsunori Hashimoto. \"Large Language Models Can Be Strong Differentially Private Learners.\" In International Conference on Learning Representations (2022).\n* Bu, Zhiqi, Jialin Mao, and Shiyun Xu. \"Scalable and efficient training of large convolutional neural networks with differential privacy.\" Advances in Neural Information Processing Systems 35 (2022): 38305-38318.  \n* Bu, Zhiqi, Yu-Xiang Wang, Sheng Zha, and George Karypis. \"Differentially private optimization on large model at small cost.\" In International Conference on Machine Learning, pp. 3192-3218. PMLR, 2023.  \n* Béthune, Louis, Thomas Massena, Thibaut Boissin, Aurélien Bellet, Franck Mamalet, Yannick Prudent, Corentin Friedrich, Mathieu Serrurier, and David Vigouroux. \"DP-SGD Without Clipping: The Lipschitz Neural Network Way.\" In The Twelfth International Conference on Learning Representations (2024).  \n\n# Recommendation\n\nOverall, the paper looks correct and improves the DP-SGD and AdapClip by considering a full rank affine transformation, instead of a diagonal rescaling. Extending Adapclip to the full rank setup is non-trivial when considering the technical difficulties implied (e.g. covariance estimation, efficient storage, solving the optimization problem to find the\"withening\"), so this work *is not* incremental.  The algorithm is more tedious to implement (necessitating the use of online PCA) but this yields significant improvements over the competitor, on small-scale benchmarks.  \n  \nThat being said, it is unclear how the method performs beyond this small scale. If authors can do a commanding job of demonstrating feasability at larger scale for the rebuttal, I'd be happy to increase my score even more. In any case, the paper is interesting and I am leaning toward acceptance.", "was_revised": true, "final_justification": "I found the rebuttal very satisfactory on the central contribution of the paper: the motivation behind correlated gradients that pop up during training. Authors did a good job at providing an additional sanity check, and pedagogical examples.", "rebuttal": "**We thank the reviewer for the constructive and detailed feedback. The recognition of the principled motivation behind the method and the acknowledgment that extending Adaclip to the full-rank setting is a non-trivial and meaningful contribution are appreciated. It is encouraging that the resulting improvements were found to be significant, and that the experiments on small-scale datasets were seen as very convincing, demonstrating clear gains over the baselines.**\n\nWe address the reviewer’s concerns below.\n\n**Q1) Small dataset**\n\nWe appreciate the reviewer’s comment. While much of modern ML focuses on high-dimensional data, tabular datasets have long been, and continue to be, a central part of ML landscape. These datasets typically have a relatively small number of features, making small models sufficient in many cases. At the same time, tabular data—particularly in healthcare—often involve highly sensitive information, necessitating strict privacy. High privacy requirements limit the number of training iterations and lead to reduced utility. In such settings,  Algorithm 1 is well suited: it allows to compute the full covariance matrix efficiently due to the manageable model size, and its fast convergence enables improved utility in just a few iterations. \n\nWe kindly refer the reviewer to our response to Question 6 from reviewer 6gkB, where we compare our two algorithms and show that even with a small $k$, the performance of Streaming Rank-$k$ PCA (Algorithm 2) remains comparable to that of Algorithm 1, which uses the full covariance matrix. This indicates that Algorithm 2 is effective under resource constraints.\n\n We acknowledge that more experiments on large-scale settings would strengthen the scalability claims of Algorithm 2. This work serves as a proof of concept, and the results are encouraging enough to motivate applying the method to larger models.\n\n---\n\n**Q2) Streaming Rank-k PCA**\n\nOur implementation maintains only the top-$k$ eigenvectors (out of $d$ total model parameters) and updates them using an $\\mathcal{O}(dk^2 + k^3)$ SVD at each step (see the “Low-Rank PCA” section above Section 4). Since $k \\ll d$, the cost is dominated by the linear dependence on $d$, making this step efficient even for large models if $k$ is small.\n\nThe memory overhead is also modest. For example, in USPS experiment (Section 4.4), using a logistic regression model with $d = 2570$ and $k = 100$, Streaming Rank-$k$ PCA only stores a $d \\times k$ eigenvector matrix and a length-$k$ eigenvalue vector—far smaller than the full $d \\times d$ covariance matrix.\n\nAlthough it introduces some overhead, we believe it is well-justified by the practical gains. It converges significantly faster than baseline methods (see Figure 2), requiring fewer training iterations to reach target accuracy. While each iteration may be slightly more expensive than DP-SGD, this is partially offset by the reduced number of steps. Combined with improved privacy—since fewer steps lead to lower total privacy loss—these benefits make the overhead worthwhile.\n\nIf accepted, we will conduct more extensive benchmarking to compare the computation time and memory usage of GeoClip to the other versions of DP-SGD.\n\n---\n\n**Q3) Decorreleted basis**\n\nWhile there may be a more direct relationship between input feature correlations and gradient coordinate correlations in linear models, this connection does not generally hold in nonlinear architectures. Nonlinear activations, weight sharing, and depth introduce interactions that can create dependencies between gradient coordinates—even when the input features are uncorrelated.\n\nConsider a simple MLP with two independent inputs $x_1$ and $x_2$, a hidden layer computing  \n$h = \\mathrm{ReLU}(w_1 x_1 + w_2 x_2)$,  \nand output  \n$y = \\nu \\cdot h$,  \nwhere $\\nu$ is the output-layer weight. With squared error loss, the gradients are:\n\n$$\n\\frac{\\partial L}{\\partial w_1} = \\alpha(x_1, x_2) \\cdot x_1, \\quad \n\\frac{\\partial L}{\\partial w_2} = \\alpha(x_1, x_2) \\cdot x_2,\n$$\n\nwhere\n\n$$\n\\alpha(x_1, x_2) = \\left( \\nu \\cdot \\mathrm{ReLU}(w_1 x_1 + w_2 x_2) - y_{\\text{true}} \\right) \\cdot \\nu \\cdot \\mathbf{1}_{w_1 x_1 + w_2 x_2 > 0}.\n$$\n\nAlthough $x_1$ and $x_2$ are uncorrelated, both gradient components are scaled by the same nonlinear factor $\\alpha(x_1, x_2)$, introducing dependency. These effects are amplified in deeper networks. Prior work shows that gradients often concentrate in low-dimensional subspaces [1], resulting in geometry that GeoClip is designed to exploit.\n\n[1] Gur-Ari et al. Gradient Descent Happens in a Tiny Subspace. \n\n---\n\n**Q4) LLM**\n \nWe agree that evaluating the method on small LLMs would be a valuable direction to explore. This work was intended as a proof of concept, and our focus was on demonstrating the benefits of the proposed method in controlled settings. We plan to extend our experiments to include such models, particularly in the context of fine-tuning LLMs on sensitive datasets.\n\n---\n\n**Q5) Missing baselines and related work**\n\nWe appreciate the wide-ranging references provided by the reviewer. Our primary goal in comparing against existing variations of DP-SGD was to focus specifically on methods related to clipping. We acknowledge that some of the references pointed out by the reviewer make improvements to DP-SGD, but in aspects other than the clipping. For example, the first four references [Lee \\& Kifer (2020), Li et al. (2022), Bu et al. (2022), Bu et al. (2023)] focus on practical aspects such as improving speed, reducing memory usage, and lowering computational cost—directions that are orthogonal to our focus on the privacy-utility trade-off. On a different note, Béthune et al. (2024) takes a different approach by avoiding clipping altogether through Lipschitz-constrained networks, which is also complementary to our method. In the interest of maintaining focus, we elected not to include comparisons to these methods.\n\n---\n\n**Q6) Decorrelation sanity check**\n\nThe experiment in Section 4.1 involves linear regression on a synthetic Gaussian dataset with 10 features (five correlated). As suggested, we repeated the experiment with the same setup but with all 10 features drawn independently. We have collated our results in the Tables below.\n\nIn linear regression with uncorrelated features, gradient coordinates tend to become uncorrelated as the model is learned. Let \n\n$x \\sim \\mathcal{N}(0, I_d)$ \n\nand \n\n$y = (w^*)^\\top x + \\epsilon$   \n\nwhere $\\epsilon$ \nis zero-mean noise with variance $\\sigma^2$, independent of $x$. The gradient is\n$\n\\nabla_w L = (w^\\top x - y) \\cdot x = e \\cdot x,\n$\nwhere\n$\ne = w^\\top x - y = (w - w^*)^\\top x - \\epsilon.\n$\n\nAs training progresses and  $w \\to w^*$, the term \n\n$(w - w^*)^\\top x$ \n\nvanishes, and the residual becomes $e \\approx -\\epsilon$, which is independent of $x$. In this regime, the gradient simplifies to $\\nabla_w L \\approx -\\epsilon x$, and the gradient covariance becomes\n$$\n\\mathbb{E}[\\nabla_w L (\\nabla_w L)^\\top] \\approx \\mathbb{E}[\\epsilon^2 x x^\\top] = \\mathbb{E}[\\epsilon^2] \\cdot \\mathbb{E}[x x^\\top] = \\sigma^2 I_d.\n$$\nThis reflects uncorrelated gradient coordinates. This structure becomes more accurate later in training; during early iterations, the residual $e$ may still depend on $x$, and the gradient coordinates can be correlated. Thus, GeoClip tends to outperform AdaClip in the early stages of training (where only a small portion of the privacy budget has been consumed and the model operates in a higher privacy regime), and behaves similarly as the model converges. GeoClip consistently outperforms the baseline, as shown in Table 1.\n\n**Table 1 (Test MSE over 10 seeds)**\n| Method    | Epoch 1           | Epoch 3           | Epoch 5           | Epoch 7           |\n|-----------|--------------------|--------------------|--------------------|--------------------|\n| GeoClip   | 2.22 ± 0.34   | 0.00027 ± 0.00004| 0.0001 ± 0.000002| 0.0001 ± 0.000003|\n| AdaClip   | 2.52 ± 0.30     | 0.0087 ± 0.005    | 0.003 ± 0.001   | 0.003 ± 0.002    |\n| DP-SGD    | 6.96 ± 0.69     | 4.04 ± 0.54     | 1.91 ± 0.37     | 0.58 ± 0.20     |\n| Quantile  | 8.46 ± 0.77   | 4.04 ± 0.47   | 0.11 ± 0.02   | 0.0006 ± 0.0002|\n\nWe also conducted an additional experiment using the synthetic dataset from Section 4.4 (400 Gaussian features with logistic regression), this time with all features drawn independently. This illustrates how the nonlinearity induced by a sigmoid can introduce gradient correlations even under feature independence—structure that GeoClip is able to exploit. The results, shown in Table 2, align with our response to the reviewer’s earlier comment on the decorrelated basis.\n\n**Table 2 (%) (Test Accuracy over 10 seeds)**\n| Method               | Iter 10         | Iter 30         | Iter 50         | Iter 70         |\n|----------------------|------------------|------------------|------------------|------------------|\n| GeoClip ($k=50$) | 81.26 ± 1.20     | 84.03 ± 0.68     | 83.92 ± 0.77     | 83.51 ± 0.53     |\n| AdaClip              | 53.95 ± 2.90     | 65.06 ± 2.25     | 74.07 ± 1.48     | 79.50 ± 1.23     |\n| DP-SGD               | 54.67 ± 2.88     | 62.74 ± 2.53     | 69.05 ± 1.89     | 73.85 ± 1.67     |\n| Quantile             | 49.77 ± 1.67     | 51.26 ± 1.75     | 57.31 ± 1.74     | 68.34 ± 1.27     |\n\n---\n\n**Q7) Quantile-based clipping**\n\nCombining with quantile-based clipping is unlikely to help, as our method already derives an optimal transformation matrix that includes both a change of basis and clipping.\n\n***\n**Q8) Full covariance**\n\nAt this point, we are not aware of differentially private algorithms that explicitly use the full gradient covariance; however, there is a growing interest in enhancing Adam-like optimizers with methods that require full gradient covariance matrices. Such approaches, with or without privacy could directly benefit from our Streaming Rank-$k$ PCA.\n\n**We hope these responses convincingly address the reviewer's concerns.**"}, {"review_id": "Y2shGpit1Q", "reviewer": "Reviewer_6gkB", "summary": "The paper proposes a method to improve the utility of differentially private stochastic gradient descent (DP-SGD) by transforming gradients into an appropriate coordinate system where clipping can be performed more effectively. Theoretical analysis is provided to justify the approach, and experimental results on synthetic data and fine-tuning tasks demonstrate its potential. However, its applicability to larger model training is required.", "questions": "See weaknesses", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths: \n- The paper tackles an important challenge in differentially private stochastic gradient descent (DP-SGD), namely improving gradient clipping, which is a critical bottleneck for utility. \n- The proposed method (transforming gradients to a more appropriate coordinate system) is clean and intuitive. The theoretical exposition and writing are clear and easy to follow. \n\nWeaknesses: \n1. While the idea of coordinate transformation is novel in presentation, the resulting theoretical insights appear closely related to prior work such as AdaCLIP, potentially limiting the originality of the contribution. \n\n2. A key concern is the limited scope of empirical validation. Unlike AdaCLIP, which demonstrated results on MNIST and CelebA using CNNs and ResNets, this paper restricts experiments to synthetic data or simple final-layer fine-tuning. This raises questions about practical utility in the settings where DP-SGD is most challenged (low performance in practical models). \n\n3. Related works that project gradients into lower-dimensional subspaces for utility improvement (see [1, 2]) are not discussed or compared. Including them would provide important context and highlight the positioning of this method within the broader landscape.\nEspecially with Low-Rank PCA results (Algorithm 2).\n\n4. The choice of the parameter $\\gamma$ remains unclear, even when combined with $h_2$. \n\n5. A more principled or empirical justification of $h_1$ and $h_2$ is necessary. \n\n6. If many eigenvalues of the covariance matrix are near zero, it raises the question of why the method does not project gradients onto the effective low-dimensional subspace directly, which could further reduce noise and improve utility. This question requires the comparison between Algorithm 1 and Algorithm 2.\n\n[1] Bu, Zhiqi, et al. \"Fast and memory efficient differentially private-sgd via jl projections.\" NeurIPS 2021\n[2] Zhou, Yingxue, Steven Wu, and Arindam Banerjee. \"Bypassing the Ambient Dimension: Private SGD with Gradient Subspace Identification.\" ICLR 2021", "was_revised": true, "final_justification": "I still have concerns about the practical applicability of the method, but the paper presents reasonable theoretical results, and therefore I am increasing my rating.", "rebuttal": "**We thank the reviewer for their valuable feedback. We are glad that the paper’s focus on improving gradient clipping in DP-SGD was recognized as important, and that our proposed coordinate transformation was seen as clean and intuitive. We also appreciate the positive feedback on the clarity of our theory and writing.**\n\n Below, we address the reviewer’s remaining comments.\n\n**Q1) While the idea of coordinate ...**\n\nWe appreciate the reviewer’s comment. While our method can be seen as a generalization of AdaClip—as discussed in the paper—we emphasize that this extension is non-trivial, both conceptually and theoretically. Our analysis handles the complexity introduced by the basis transformation, going beyond AdaClip's coordinate-wise scaling.\n\nWhereas AdaClip constructs clipping thresholds using only the coordinate-wise mean and variance of the gradients, our method estimates a structured transformation based on the eigen-decomposition of the gradient covariance matrix. Estimating eigenvalues and eigenvectors is a more sophisticated approach which then assures significantly better results. \nTo this end, we designed an efficient streaming algorithm to estimate the top eigenvalues and eigenvectors in a scalable manner. Moreover, to the best of our knowledge, this is the first work to combine two lines of research: adaptive clipping and projection onto gradient subspace representations. We hope that our contributions in these directions are recognized as distinct and meaningful.\n\n---\n\n**Q2) A key concern is the limited scope of empirical validation...**\n\nWe appreciate the reviewer’s comment. To address this, we first clarify the experimental setups used in AdaClip [1] and in our work, and then highlight a challenging setting where GeoClip shows a clear advantage over existing baselines.\n\nThe AdaClip paper evaluated a synthetic regression task and MNIST, using only logistic regression and a one-hidden-layer neural network. For logistic regression, the full 784-dimensional MNIST input was used. For the neural network, the input was first reduced to 60 dimensions using differentially private PCA, followed by training a fully connected layer with 1000 hidden units. The privacy budget was split between the PCA step and model training. As far as we can determine from the cited paper, no CNNs or other deep architectures such as ResNets were evaluated, and MNIST was the only real-world dataset considered.\n\nGeoClip with the full covariance estimator (Algorithm 1) was evaluated on synthetic, tabular, and image datasets. For tabular data, we used logistic or linear regression on Diabetes (10 features), Breast Cancer (30 features), and Android Malware (241 features). We also transferred a convolutional network pretrained on MNIST to Fashion-MNIST and fine-tuned the final fully connected layer under DP. This setting involved 510 trainable parameters. For higher-dimensional cases, Algorithm 2 (with streaming rank-$k$ PCA) was evaluated on a synthetic dataset and on USPS (256 features) using multiclass logistic regression (2570 parameters).\n\nRegarding the practicality of GeoClip in challenging settings, we offer the following clarification. While much of modern ML focuses on high-dimensional data and large models, tabular datasets have long been, and continue to be, a central part of the ML landscape. These datasets typically have a relatively small number of features, making small models sufficient in many cases. At the same time, tabular data—particularly in domains like healthcare—often involve highly sensitive information, necessitating strict privacy guarantees. High privacy requirements typically limit the number of training iterations and lead to reduced utility. In such settings, Algorithm 1 is well suited: it allows for full covariance computation and benefits from GeoClip’s fast convergence, enabling improved utility in just a few training steps. We refer the reviewer to Tables 1–3 (tabular datasets) and Figure 1 (fast convergence) for supporting evidence.\n\nFor larger models and datasets, Algorithm 2 addresses similar challenges under strong privacy constraints. Our proposed streaming rank-$k$ PCA enables faster convergence, allowing a given level of utility to be achieved in fewer iterations. Please see Figure 2 in the main paper, as well as the privacy curves in Figure 4 of the supplementary material, which illustrate how fast convergence supports stronger privacy guarantees. We hope these helps address the reviewer’s concerns about the practicality of GeoClip.\n\nWe acknowledge that more experiments on large-scale settings would further support the scalability claims of Algorithm 2. This work serves as a proof of concept, and the results are encouraging enough to motivate applying the method to larger models.\n\n[1] Pichapati, Venkatadheeraj, et al. ``AdaClip: Adaptive Clipping for Private SGD.'' arXiv preprint arXiv:1908.07643 (2019).\n\n---\n\n**Q3) Related works that project gradients into lower-dimensional subspaces for utility improvement (see [1, 2]) ...**\n\nWe appreciate the references provided by the reviewer. In what follows, we discuss the key differences.\n\nA key difference between our approach and DP-SGD-JL [Bu et al., 2021] lies in the objective. DP-SGD-JL aims to improve computational efficiency—specifically memory and speed—by approximating per-sample gradient norms using Johnson–Lindenstrauss projections, while maintaining similar utility to standard DP-SGD. In contrast, our method is designed to improve the privacy–utility tradeoff.\n\nWe also differ from the approach in [Zhou et al., 2021], which assumes access to a public dataset drawn from the same distribution as the private data in order to estimate a low-dimensional gradient subspace, thereby avoiding additional privacy cost. Obtaining such a representative public dataset may not always be practical, and their analysis shows that the quality of the estimated subspace—and thus the effectiveness of the projection—depends on the size of the public data. In contrast, our method does not require a public dataset and incurs no additional privacy cost for identifying the subspace. Instead, we estimate the gradient geometry by reusing previously released noisy gradients.\n\nIf accepted, we will incorporate these comparisons into the paper.\n\n---\n\n**Q4) The choice of the parameter $\\gamma$ remains unclear, even when combined with $h_2$**\n\nIn our formulation, $\\gamma$ bounds the probability that a gradient is clipped (see the discussion above Equation (13)). The parameter $h_2$ also affects the clipping probability by influencing the clamped eigenvalues and consequently, the transformation matrix $M$.  To simplify hyperparameter tuning, we set $\\gamma = 1$ and tuned only $h_2$, since both parameters have similar effects.\n\nWe conducted an ablation study on $\\gamma$ in our response to Question 3 from reviewer u6Le, and we kindly refer the reviewer to that discussion due to space limitations. If accepted, we will include a more extensive ablation study varying both $\\gamma$ and $h_2$ independently.\n\n---\n\n**Q5) A more principled or empirical justification of $h_1$ and $h_2$  is necessary.**\n\nWe thank the reviewer for this comment. As noted on page 5, we introduce $h_1$ and $h_2$ to stabilize the transformation by avoiding issues from near-zero eigenvalues and limiting the influence of large, noisy ones. We had such ablation studies performed but missed adding them to the paper. We included them in our response to Question 3 from reviewer u6Le, and we kindly refer the reviewer to that discussion due to space limitations. The results show no impact from varying $h_1$, and only minor changes with $h_2$. We also refer the reviewer to our earlier response regarding the effect of $h_2$ on clipping.\n\n---\n\n**Q6) If many eigenvalues of the covariance matrix are near zero...**\n\nWe emphasize that both of our algorithms adapt noise and clipping to the geometry of the gradient distribution. Algorithm 2 (streaming rank-$k$ PCA) projects gradients from the $d$-dimensional space onto a $k$-dimensional subspace aligned with the top-$k$ eigenvectors of the gradient covariance. In contrast, Algorithm 1 (with full covariance) transforms gradients into the full eigenbasis and retains all $d$ directions. Crucially, noise is scaled by the corresponding eigenvalue, so directions with near-zero eigenvalues receive little to no noise. This makes Algorithm 1 a soft generalization of Algorithm 2: it retains all directions while still emphasizing dominant ones and is at least as expressive.\n\nTo support this, we compare the accuracy of GeoClip using Algorithm 1 and Algorithm 2 with $k=50$ on the same synthetic dataset from Section 4.4. As shown in Figure 2 of our paper, Algorithm 2 already outperforms other baselines. In the table below, we show that even with $k=50$, Algorithm 2 achieves comparable accuracy to Algorithm 1, which computes the full covariance. All results are averaged over 20 random seeds.\n\n| Method                    | Iter 10       | Iter 30       | Iter 50       | Iter 70       |\n|--------------------------|---------------|---------------|---------------|---------------|\n| GeoClip ( Algorithm 2, k = 50) | 85.51 ± 0.83 | 87.93 ± 0.52 | 88.02 ± 0.60 | 88.11 ± 0.67 |\n| GeoClip  (Algorithm 1)                | 87.34 ± 0.75 | 89.09 ± 0.48 | 89.24 ± 0.40 | 89.26 ± 0.42 |\n\nIf accepted, these comparisons along with the corresponding plots, will be provided in the final version to further illustrate their relationship.\n\n**We hope these responses are satisfactory and convincing to the reviewer.**"}, {"review_id": "u5MSk78oih", "reviewer": "Reviewer_u6Le", "summary": "This paper observes that if the gradient coordinates are correlated over a datasets, then we should not need to add as much noise during DP training; to leverage this they propose (and note this generalizes past methods) first transforming the gradient, then making it private, then inverting the transform before using SGD. In order to find the best transform they formulate an optimization problem which minimizes the effective amount of noise added while not adding significant error by clipping in the transformed space; this optimization comes from a convergence analysis and minimizing an upper-bound on error. They then provide a closed form solution to the optimization, and further a low-rank approximation for high dimension settings. Algorithmically they use the privatized gradients to estimate the covariance matrix and other terms for the transform, introducing no privacy overhead. All experiments showed improvements over the baselines.", "questions": "I could not find some minor experimental details in the main paper or supplementary. Below is a list of some details, and I suggest the authors consider adding a section in the appendix providing more details for reproducability.\n\n\n1.  How was the lr tuned for experiments in section 4.1?\n2. Could authors provide exact details on the synthetic datasets used through the experimental section: e.g., what’s the exact distribution (i.e., how are the features correlated), what was the function for y given x? \n3. Could authors add what the grid search for hyperparameters were over for the various experiments, and details on the validation set (if it's not just the training set)\n4. Related, how was the batch size chosen in section 4.2 (it seems to be fixed for all methods?)\n5. How many trials were done for the experiments in section 4.1 and section 4.4", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths:\n\n1) Novel and insightful methodology \n2) Strong empirical results\n3) Well-written\n\nWeaknesses:\n1) some minor experimental details seem to be missing, see questions for details", "was_revised": true, "final_justification": "The strengths from my original review hold, as my only concern was how the hyperparameters and evaluations were run. I saw no issues in these.\n\nAs such I maintain my original recommendation of acceptance.", "rebuttal": "**We thank the reviewer for their positive feedback and helpful comments. We are pleased that the reviewer found our methodology to be novel and insightful, appreciated the strong empirical results, and considered the paper well-written.**\n\n We respond to the reviewer’s comments in detail below.\n\n**I could not find some minor experimental details in the main paper or supplementary. The following is a list of some details, and I suggest the authors consider adding a section in the appendix providing more details for reproducibility.**\n\nWe thank the reviewer for pointing this out—we agree that including these details is important for reproducibility. If accepted, we will add a dedicated section in the supplementary material that consolidates all relevant experimental details discussed here and includes additional information to improve clarity and completeness.\n\n---\n\n**Q1) How was the lr tuned for experiments in section 4.1?**\n\nWe tuned the learning rate via grid search over a logarithmic scale ranging from 0.0001 to 10.\n\n---\n\n**Q2) Could authors provide exact details on the synthetic datasets used through the experimental section: e.g., what’s the exact distribution (i.e., how are the features correlated), what was the function for $y$ given $x$?**\n\nWe appreciate the reviewer's comment. The synthetic dataset used in Section 4.1 consists of $n = 20{,}000$ samples and 10 features. To obtain the 5 correlated features, we first generate an $n \\times 5$ matrix $Z$ and a $5 \\times 5$ matrix $A$, each with entries drawn independently from the standard normal distribution. The correlated features are obtained by multiplying $Z$ by $A$. The remaining 5 features are drawn independently from a standard multivariate normal distribution. The full feature matrix $X$ is constructed by concatenating these two blocks. The target $y$ is generated using a linear function with Gaussian noise: $y = Xw + b + \\epsilon$, where $w \\sim \\mathcal{N}(0, I_{10})$ is a weight vector, $b \\sim \\mathcal{N}(0, 1)$ is a scalar bias term, and $\\epsilon \\sim \\mathcal{N}(0, 0.01^2)$ is i.i.d. noise.\n\n\nFor the synthetic dataset used in Section 4.4, the feature matrix $X$ is constructed in the same way. The logits are computed using the same linear function as before. The probabilities $p$ are then obtained via the sigmoid function, and binary labels are generated as $y = \\mathbf{1}(p > 0.5)$  where $\\mathbf{1}$ is the indicator function.\n\nIf accepted, we will add these details in the final version.\n\n---\n\n**Q3) Could authors add what the grid search for hyperparameters were over for the various experiments, and details on the validation set (if it's not just the training set)**\n\nWe thank the reviewer for the suggestion. In what follows, we explain how we tuned our hyperparameters for all experiments. If accepted, we will also include these details in the paper for completeness.\n\n\n**Parameter $\\gamma$:** As mentioned in the experimental results section on page 6, we set the parameter $\\gamma$ to $1$, as its effect can be absorbed by tuning $h_2$. Therefore, we only tune $h_2$. We have also provided an explanation of how tuning $\\gamma$ would have a similar effect as tuning $h_2$ in our response to Question 4 from Reviewer 6gkB, and we kindly refer the reviewer to that discussion.\n\n**Parameter $h_1$:**  We initially ran experiments using several different $h_1$ values within the range $[10^{-15}, 10^{-6}]$, and observed that our algorithms are robust to changes in $h_1$. Therefore, as stated in Section 4, we set $h_1 = 10^{-15}$ across all experiments.\n\n**Parameter $h_2$:** We first tried $h_2$ values over a logarithmic scale in the range $[1, 1000]$, and observed that $h_2 = 1$ and $10$ perform consistently well across all datasets. Therefore, we select the best of these two values for each dataset in the final experiments.  \n\n**Parameters $\\beta_1, \\beta_2, \\beta_3$:**  We again tried several different values of $\\beta_1, \\beta_2$, and $\\beta_3$ over the range $[0.9, 0.999]$, and observed that our algorithms are robust to the choice of these parameters. As stated in Section 4, we used standard values commonly used in optimization, such as $\\beta_1 = 0.99, \\beta_2 = 0.999$, and $\\beta_3 = 0.999$, in all experiments. \n  \n\n **Validation set:** We would like to clarify that we used a separate validation set for tuning hyperparameters and choosing the best model for each dataset. As stated in Section 4, we split each dataset into 80-10-10 train-validation-test sets. For all experiments, we selected the best hyperparameters based on the model's performance on the validation set, trained the best model using different random seeds, and reported the average performance on the test set. \n\nTo further explore the questions raised by the reviewer, we also conducted an ablation study on $\\gamma$, $h_1$, and $h_2$ using the USPS dataset, under the same settings as in Section 4.4.\nAs shown, varying $\\gamma$ does not significantly affect performance. The results indicate no noticeable impact from $h_1$, and only minor variations with $h_2$.\n\n**Test Accuracy (%) ( ablation study on $\\gamma$ with $h_2 = 10$ and $h_1 = 10^{-15}$)**\n\n| Method                     | γ = 0.2 | γ = 0.6 | γ = 1.0 |\n|---------------------------|--------:|--------:|--------:|\n| GeoClip (Algorithm 2, k = 50)  | 85.537 | 86.182 | 85.752 |\n\n\n\n**Test Accuracy (%)  (ablation study on $h_2$ with $h_1 = 10^{-15}$ and $\\gamma = 1$)**\n\n| Method                    | h₂ = 1   | h₂ = 10  | h₂ = 100 | h₂ = 1000 |\n|--------------------------|---------:|---------:|---------:|----------:|\n| GeoClip (Algorithm 2, k = 50) | 86.0215  | 85.7526  | 85.7526  | 85.7526   |\n\n\n\n**Test Accuracy (%)  (ablation study on $h_1$  with $h_2 = 10$ and $\\gamma = 1$)**\n\n| Method                    | $h_1 = 10^{-6}$ | $h_1 = 10^{-10}$ | $h_1 = 10^{-15}$ |\n|--------------------------|----------------:|-----------------:|-----------------:|\n| GeoClip (Algorithm 2, k = 50) | 85.752         | 85.752          | 85.752          |\n\n---\n\n**Q4) Related, how was the batch size chosen in section 4.2 (it seems to be fixed for all methods?)**\n\nWe specified the batch size used for each dataset in Section 4.2, within the captions of the tables presenting experimental results: batch size 32 for Diabetes, 64 for Breast Cancer, and 512 for Malware. If accepted, we will make these details more clearly stated in the main text.\n\n---\n\n**Q5) How many trials were done for the experiments in section 4.1 and section 4.4?**\nFor the experiments in Section 4.1 and Section 4.4, we selected the best hyperparameters based on the model's performance on the validation set, trained the best model using $20$ different seeds, and reported the average performance on the test set. If the reviewer meant something else by ``trials\", we humbly ask them to clarify it. \n\n**We hope our responses adequately address the reviewer's concerns.**"}, {"review_id": "bJyPNDGo87", "reviewer": "Reviewer_ocmc", "summary": "This paper introduces a novel method for adaptive clipping in large-scale differentially private optimization. The proposed approach accounts for correlations across gradient vectors, specifically addressing scenarios where gradients exhibit varying underlying geometries. The authors provide theoretical guarantees for their method and demonstrate improved empirical performance over existing algorithms that do not incorporate geometric information during the clipping process.", "questions": "1. **Convergence Under Approximation**:  What is the final convergence rate of GeoClip when combined with streaming PCA? How does the convergence analysis differ from the case without approximation? Additionally, under a low-rank Hessian assumption as explored in [1,2], is it possible to obtain improved dependencies in the utility gap, akin to the theoretical gains demonstrated in those works?\n\n2. **Utility of Chosen Preconditioner**: In Theorem 2, what is the final utility guarantee corresponding to the specific choice of the preconditioning matrix $M_t$? Is this choice theoretically optimal in terms of convergence or privacy-utility trade-off?\n\n3. **Faster Preconditioning**:  Is it possible to prove faster convergence to optimal utility by leveraging geometry-aware techniques? More specifically, can one characterize the optimal choice of $M_t$ that minimizes the number of iterations $T$ required to achieve a desired utility, and does this lead to any fundamental improvements in convergence rate?\n\n---\n\n**References**:  \n[1] Li, X., Liu, D., Hashimoto, T. B., Inan, H. A., Kulkarni, J., Lee, Y. T., & Guha Thakurta, A. (2022). *When does differentially private learning not suffer in high dimensions?* Advances in Neural Information Processing Systems, 35, 28616–28630.  \n[2] Zhang, L., Li, B., Thekumparampil, K. K., Oh, S., & He, N. (2023). *DPZero: Private fine-tuning of language models without backpropagation.* arXiv preprint arXiv:2310.09639.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "### **Strengths**\n\n1. **Clarity and Theoretical Foundation**: The paper is clearly written and provides a well-structured overview of the theoretical underpinnings of the proposed algorithm. This clarity allows the reader to follow the motivation, construction, and justification of the technique with ease.\n\n2. **Innovative Use of Statistical Tools**: The authors successfully integrate concepts from algorithmic statistics—particularly streaming PCA—into the framework of adaptive clipping. This combination leads to a novel and principled approach to differentially private optimization.\n\n3. **Strong Empirical Performance**: The proposed method demonstrates empirical improvements over existing baselines on standard benchmark tasks, showcasing its practical effectiveness.\n\n4. **Theoretical Depth and Ablation**: The paper includes thoughtful theoretical components such as the use of low-rank approximation, which are well-explained and demonstrate the authors' careful consideration of the algorithm's efficiency and design.\n\n5. **Novel Impact**: The algorithm addresses a meaningful gap in the literature by handling general gradient geometries in a computationally aware manner. This increases the practicality of adaptive clipping in broader settings.\n\n---\n\n### **Weaknesses**\n\n1. **Resource Overhead**: A primary limitation of the method is its computational and memory overhead. Storing and updating a full covariance matrix of gradients can be prohibitive, especially in large-scale settings such as training language models. Even with low-rank approximations, convergence may suffer due to the inherent noise in the estimates, which can delay the stabilization of the approximation.\n\n2. **Lack of Large-Scale Experiments**: While the technique is promising, the experiments are confined to relatively simple models. It would significantly strengthen the paper to include results on larger models, such as transformers or LLMs, to better understand the practical scalability and robustness of the method in high-dimensional regimes.\n\n3. **Missing Utility Guarantees**: The paper does not provide explicit utility bounds or performance guarantees in terms of key DP parameters such as the dimensionality ($d$), dataset size ($n$), and privacy budget ($\\epsilon$). Including such an analysis would give a clearer picture of the theoretical trade-offs involved.", "was_revised": true, "final_justification": "The authors responded to the comments effectively, and I remain confident in the score I assigned. While I initially found the convergence analysis somewhat confusing, the paper overall makes a strong contribution. The authors' feedback helped clarify the individual components of the analysis and how the approach preserves the standard DP-SGD guarantees, despite the algorithm’s complexity. That said, as noted by the authors, some theoretical aspects of the work remain open for future exploration and may require more advanced technical tools to fully grasp. Nonetheless, the intuition provided is solid and the paper offers a novel perspective, particularly in its geometry-aware approach, which has not been explored before.", "rebuttal": "**We thank the reviewer for their thoughtful and encouraging feedback. We appreciate the recognition of our paper’s clarity, the theoretical depth of our analysis, and the novelty of integrating streaming PCA into adaptive clipping for differentially private optimization. We are especially grateful for the acknowledgment of our method’s strong empirical performance  and the practical significance of addressing gradient geometries in a computationally efficient way.**\n\n We respond to the specific points raised below.\n\n**Q1) Resource Overhead: A primary limitation of the method is ...** \n\nWe thank the reviewer for raising this important point regarding the computational and memory overhead of our method. We acknowledge that storing and updating a full gradient covariance matrix can be expensive in large-scale settings. While much of modern ML focuses on high-dimensional data and large models, tabular datasets have long been, and continue to be, a central part of the ML landscape. These datasets typically have a relatively small number of features, making small models sufficient in many cases. At the same time, tabular data—particularly in domains like healthcare—often involve highly sensitive information, necessitating strict privacy guarantees. High privacy requirements typically limit the number of training iterations and lead to reduced utility. In such settings, our Algorithm 1 (with a full covariance matrix) is well suited: we can compute the full covariance matrix efficiently due to the manageable model size, and GeoClip’s fast convergence enables improved utility in just a few training iterations. We refer the reviewer to Tables 1–3 for results on tabular datasets, Figure 1 (left) for evidence of fast convergence, and Figure 1 (right) for how this fast convergence helps maintain strong privacy.\n\nFor larger models, our implementation of Streaming Rank-$k$ PCA maintains only the top-$k$ eigenvectors (out of $d$ total model parameters) and updates them using an $\\mathcal{O}(dk^2 + k^3)$ SVD at each step (see the “Low-Rank PCA” section above Section 4). Since $k \\ll d$, the cost is dominated by the linear dependence on $d$, making this step efficient even for large models. The memory overhead is also modest. For example, in our USPS experiment (Section 4.4), using a logistic regression model with $d = 2570$ and $k = 100$, Streaming Rank-$k$ PCA only stores a $d \\times k$ eigenvector matrix and a length-$k$ eigenvalue vector—far smaller than the full $d \\times d$ covariance matrix. \n\nAlthough GeoClip introduces some computational and memory overhead, we believe this is well justified by the practical benefits. GeoClip converges significantly faster than baseline methods (see Figures 1 and 2), requiring fewer training steps to reach the target accuracy. While each iteration may be slightly more expensive than standard DP-SGD, this is partially offset by the reduced number of steps. Combined with improved privacy—since fewer steps lead to lower total privacy loss—these benefits make the overhead worthwhile.\n\nRegarding the convergence of Streaming Rank-$k$ PCA, we empirically find that GeoClip with Streaming Rank-$k$ PCA maintains strong convergence behavior even for small $k$. As shown in Figure 2, the method still significantly outperforms baseline methods. A direct comparison between the full (Algorithm 1) and low-rank (Algorithm 2) approaches is included in our response to Reviewer 6gkB (Question 6), and we kindly ask the reviewer to refer to it. The results demonstrate that even with small $k$, the performance of Streaming Rank-$k$ PCA remains comparable to that of the full covariance method.\n\n---\n\n**Q2) Lack of Large-Scale Experiments: While the technique is promising...**\n\nWe thank the reviewer for highlighting this important direction. We agree that evaluating GeoClip on larger models is a valuable next step to further demonstrate the scalability of Algorithm 2 with Streaming Rank-$k$ PCA. This work serves as a proof of concept, and the results are encouraging enough to motivate applying the method to larger-scale models.\n\n---\n\n**Q3) Missing Utility Guarantees: The paper does not provide explicit utility bounds ...**\n\nTo relate our convergence bound to DP parameters, we note that the bound in Theorem 1 depends on the noise scale $\\sigma$. Abadi et al. [1] show the following relationship between $\\sigma$ and the privacy parameters $(\\varepsilon, \\delta)$, for some constant $c$, number of iterations $T$, and dataset size $n$:\n$$\n\\sigma = c \\frac{\\sqrt{T \\log(1/\\delta)}}{n \\varepsilon}.\n$$\nSubstituting this into our convergence bound allows us to express it as a function of $\\varepsilon$, $\\delta$, and $n$.\n\nRegarding the dependency of our convergence bound on dimensionality, if we simplify the expression in Theorem 1 using the bound on $\\beta(a_t)$ from Equation (9) and the optimal transformation derived in Theorem 2 (note that the optimal solution occurs when the constraint in Equation (13) is active, i.e., $\\operatorname{Tr}(M_t^\\top M_t \\Sigma_t) = \\gamma$), the convergence bound depends on the dimensionality $d$ only through the term $\\sum_{i=1}^d \\sqrt{\\lambda_{i}}$, where $\\lambda_{i}$ is the $i$-th eigenvalue of the gradient covariance matrix. This reflects the effective dimension rather than the ambient dimension. In particular, if $\\lambda_{i} = 0$ for some $i$, then that coordinate contributes nothing to the convergence rate. Thus, our bound naturally adapts to the structure of the gradient covariance and degrades gracefully in high-dimensional settings where the spectrum is concentrated in a low-dimensional subspace. \n\nIf accepted, we will include this discussion in the final version.\n \n\n[1] Abadi et al., *Deep Learning with Differential Privacy*, in Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (CCS).\n\n---\n\n**Q4) Convergence Under Approximation: What is the final convergence rate of GeoClip ...**\n\nWe would like to highlight that although the proof of Theorem 1 assumes that $M_t$ is a full-rank $d \\times d$ matrix, the same analytical steps extend to the case where $M_t$ is a $k \\times d$ matrix with $k < d$, corresponding to a projection onto a lower-dimensional subspace. This is precisely the setting used in streaming rank-$k$ PCA. In this case, Equation (5) becomes:\n$$\n\\tilde{g}_t = M_t^+ \\tilde{\\omega}_t + a_t,\n$$\nwhere $M_t^+$ denotes the (left) Moore-Penrose pseudoinverse of $M_t$. Consequently, in the convergence bound of Theorem 1, the term $\\operatorname{Tr}\n\\left[(M_t^\\top M_t)^{-1}\\right]$ is replaced by $\\operatorname{Tr}\n\\left[(M_t^\\top M_t)^+\\right]$, accounting for the lower-rank structure.\n\nWe thank the reviewer for highlighting this relevant line of work. While our current analysis does not explicitly assume a low-rank Hessian, our method is naturally aligned with this perspective. Intuitively, the directions where the loss changes most rapidly—i.e., those with high curvature—are also the directions where the gradients tend to vary most across data points. As a result, if the Hessian is approximately low-rank, most of the gradient activity is concentrated in the corresponding low-dimensional subspace. This helps explain why the principal components identified by Streaming PCA tend to align with the top eigenspace of the Hessian. Although we do not yet provide a formal analysis under this assumption, the connection is intuitive, and we see this as an interesting direction for future exploration.\n\n---\n\n**Q5) Utility of Chosen Preconditioner: In Theorem 2, what is the final utility guarantee ...**\n\nWe appreciate the reviewer’s comment. The final convergence bound for the optimal transformation matrix can be obtained by substituting the bound on $\\beta(a_t)$ from Equation (9) and the optimal transformation derived in Theorem 2 into the expression in Theorem 1. We note that the optimal solution in Theorem 2 occurs when the constraint in Equation (13) is active, i.e., $\\operatorname{Tr}(M_t^\\top M_t \\Sigma_t) = \\gamma$.\n\nThe transformation matrix presented in Theorem 2 is chosen to minimize the convergence rate, given a fixed noise scale $\\sigma$ determined by the $(\\varepsilon, \\delta)$-DP budget. While convergence rate is not a direct measure of utility, faster convergence implies that a target utility (e.g., loss or accuracy) can be achieved in fewer iterations. Since privacy loss accumulates over iterations, achieving convergence more quickly results in lower overall privacy cost. Therefore, this choice of preconditioner indirectly improves the privacy-utility trade-off.\n\n---\n\n**Q6) Faster Preconditioning: Is it possible to prove faster convergence to optimal utility ...**\n\nWe thank the reviewer for raising this question. In fact, our analysis in Theorem 1 was motivated by the intuition that faster convergence should enable the algorithm to reach a desired utility level in fewer iterations. While we did not explicitly optimize for the number of iterations, we focused on minimizing the convergence rate, which serves a similar purpose in practice. By accelerating convergence through a well-chosen preconditioner, we reduce the number of iterations required. These two objectives can be seen as closely related approaches to achieving efficient learning.\n\n**We hope this rebuttal effectively addresses the reviewer's concerns.**"}]

Author rebuttal:

Meta-review: This paper proposes a theoretically principled algorithm to improve differentially private machine learning from the perspective of minimizing the upper bound of the convergence error. One of the closest prior works is AdaClip, which this work generalizes by leveraging the full covariance matrix as opposed to a diagonal matrix. It develops methods to estimate the covariance matrix without incurring extra privacy loss. Though on some datasets empirical improvements are not significant and it might be difficult to scale to large-scale settings (due to the decomposition of large matrices), I think there are many merits in the proposed theory and methods as mentioned by the reviewers, hence recommend acceptance.
Decision: Accept (poster)