Private Zeroth-Order Optimization with Public Data
Authors: Xuchen Gong
Tian Li
Venue: NeurIPS 2025 poster ()
Keywords: Zeroth-Order Optimization
Differential Privacy
Primary area: social_and_economic_aspects_of_machine_learning

Abstract: One of the major bottlenecks for deploying popular first-order differentially private (DP) machine learning algorithms (e.g., DP-SGD) lies in their high computation and memory cost, despite the existence of optimized implementations.  Zeroth-order methods have promise in mitigating the overhead, as they leverage function evaluations to approximate the gradients, hence significantly easier to privatize. While recent works have explored zeroth-order approaches in both private and non-private settings,  they still suffer from relatively low utilities compared with DP-SGD, and have only been evaluated in limited application domains. 
In this work, we propose to leverage public information to guide and improve gradient approximation of private zeroth-order algorithms. We explore a suite of \underline{p}ublic-data-\underline{a}ssisted \underline{z}eroth-\underline{o}rder optimizers (PAZO) with minimal overhead. We provide theoretical analyses of the PAZO framework under an assumption of the similarity between public and private data. Empirically, we demonstrate that PAZO achieves superior privacy/utility tradeoffs across vision and text tasks in both pre-training and fine-tuning settings, outperforming the best first-order baselines (with public data) especially in highly private regimes, while offering up to $16\times$ runtime speedup.

Private Zeroth-Order Optimization with Public Data
Xuchen Gong Tian Li
University of Chicago
{xuchengo, Jitiian//uchicago..ee. edu
Abstract
One of the major bottlenecks for deploying popular first-order differentially private (DP) machine learning algorithms (e.g., DP-SGD) lies in their high computation and memory cost, despite the existence of optimized implementations. Zeroth- order methods have promise in mitigating the overhead, as they leverage function evaluations to approximate the gradients, hence significantly easier to privatize. While recent works have explored zeroth-order approaches in both private and non-private settings, they still suffer from relatively low utilities compared with DP-SGD, and have only been evaluated in limited application domains. In this work, we propose to leverage public information to guide and improve gradient approximation of private zeroth-order algorithms. We explore suite of public- data-assisted zeroth-order optimizers (PAZO) with minimal overhead. We provide theoretical analyses of the PAZO framework under an assumption of the similarity between public and private data. Empirically, we demonstrate that PAZO achieves superior privacy/utility tradeoffs across vision and text tasks in both pre- pre-training and fine-tuning settings, outperforming the best first-order baselines (with public data) especially in highly private regimes, while offering up to 16x runtime speedup.
Introduction
Differentially private (DP) is widely-used framework protect sensitive information so that adversaries cannot infer if any user or sample participates in the computation. When applied to machine learning tasks, popular DP algorithms based on privatizing first-order gradients (such as DP-SGD (I) fundamentally rely on per-sample gradient clipping. which can be computationally expensive and impractical in large-scale settings. While there exist optimized implementations of DP-SGD, they are limited in their generality to handle all model architectures and often incur other overheads, such as trading extra memory for computation 2
To tackle this, zeroth-order optimization offers an attractive alternative for DP training, as it leverages function queries (scalar values) to approximate the gradients and is hence inherently amenable to privatization [4] (). However, randomly searching in a potentially high-dimensional space based on function query feedback can be rather inefficient 44] Prior work has demonstrated competitive performance of (private) zeroth-order methods only in the limited context of language model fine- tuning with prompts 6
10 or models with extreme sparsity [ In addition, there still utility gap between private zeroth order and first-order approaches on challenging tasks [8].
In this work, aim to narrow the gap between zeroth-order and first-order methods in private training leveraging public data. Zeroth-order outputs are bigh-variance estimators of the first-order gradients and suffer from slow convergence in terms of the total number of iterations. However, there usually exists non-sensitive public data, whose batch gradients provide informative guidance on perturbing the parameter space. We thus introduce PAZO, a suite of zeroth-order DP algorithms that leverage a small amount of public data with similar distributions as private data along with their first-order gradients to guide augment the zeroth-order outputs. In particular, explore (1) PAZO-M, a mix (convex combination) of private zeroth-order estimates and public first-order gradients, (2) PAZO-P,
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

First-arder:
70
SGD
DOPE-SGD
Accuracy (86)
GEP
DPMD
Accuroty
05
60
Zerath-arde arder:
DPZero
PAZO-M -M
PAZO-P
50-
PAZO-5
0.2
0.4
0.6
0.8
Speed (s/iter)
FD+PUB
Figure 1: Results of CIFAR-IO with NFResNet18 trained from scratch under privacy budget 3. Left:
Zeroth-order methods demonstrate consistent accuracies under various privacy budgets compared with the best first-order method with public data. Right: Proposed zeroth-order approaches (PAZO-*) *) are more accurate than vanilla DPZero, and significantly more efficient than all the public data augmented first-order baselines.
constraining the sampling of random directions in the public gradient subspace, and (3) PAZO-S, selecting the best public gradient based on function queries on private data. When designing PAZO, ensure that privatization only operates top of function evaluations preserve the efficiency of zeroth-order approaches, while still satisfying desired privacy guarantees.
Unlike recent zeroth-order work that mostly focuses on language model tuning with prompts, investigate both image and text domains, and both pre-training and fine-tuning scenarios. We show that without access public data, DP zeroth-order methods may underperform DP first-order approaches (e.g., DP-SGD (I). whereas even modest amounts of public data can significantly close the gap, especially in highly private regimes. In particular, the best zeroth-orde method with public data can match or even outperform the best public-data-ane assisted first-order counterpart, while being significantly faster train. Our results highlight the broader potential of zeroth-order methods for DP training with public data: enabling improved privacy/utility tradeoffs, applicability across diverse domains, and achieving up 16x speedup compared traditional first-order methods. Our contributions are summarized as follows:
Algorithm design. We propose the first set of private zeroth-order optimization algorithms (PAZO-(M.P.)) augmented with public data (gradients) to construct better gradient estimates in a more constrained space. PAZO helps close the gap between zeroth- and first-order methods in the settings where zeroth-order approaches underperform first-order ones.
2. Theoretical analysis. We present the privacy and utility guarantees for each method, all with improved convergence rate in terms of model dimension d. PAZO-M improves the vanilla zeroth-order method by factor of log d, and PAZO-((PS) obtain d-independent rates.
3. Empirical validation. We evaluate our methods on both image and text domains and in both pre-training and fine-tuning scenarios. We find that zeroth-order methods robust privacy budgets whereas first-order methods are sensitive. Our methods consistently have superior privacy/utility tradeoffs and outperform the best public-augmented first-order method in highly privacy regimes, while achieving up to 16x speedup.
various
Related Work and Preliminaries
Differential privacy. In this work, we focus on the popular definition of sample-level DP
Definition 2.1 (Differential privacy [12). A randomized algorithm M is (s, -eff)-diffeenttaaly private for all neighboring datasets D, D' differing by one element, and every possible subset of outputs O,
Pr(M(D)EO) PrCMID)E0OXePPMMMM)))00000
We follow the classic DP model where the neighboring datasets D and D' differ by adding/removing one training sample. Typically, noise is added ensure scales with the model dimensions, resulting in degraded and unusable model utilities [3]. Extensive prior research has been proposed

---

to improve privacy/utility tradeoffs, including increasing the batch size [14 15]. using public or
side information [16] 17 [8], and reducing the dimensionality of gradients 19 Another bottleneck
of deploying DP algorithms at scale lies in the computation (or memory) cost (2]. For example, vanilla DP-SGD computes and stores per-sample clipped gradients, leading to memory consumption Obbd) where h is the private batch size and d is the model dimension. Existing methods, such as wiagttiigg/bboooeeepiiii
[20], reduce layer-wise gradient storage to min (2b,, bd], where d' is the layer dimension and p is the feature dimension of this layer, i.e. sequence length for text data. In this work, we propose to mix zeroth-order (on sensitive private data) and first-order oracles (on public data) to mitigate these two challenges at once.
Zeroth-order optimization. Zeroth-order approaches use (stochastic) function queries to estimate the true gradients. They are particularly suitable for applications where gradient information is
difficult to obtain, such as adversarial attacks and defenses [21 22 23). hyperparameter tuning [24], and data-driven science workloads (25). One fundamental challenge of zeroth-order methods is the need for large number of function queries to reduce the variance of the estimate 4 Existing work has explored various techniques to improve the estimate, such incorporating the previous estimated gradient directions [26] and sparsifying gradients [[]]. Our work focuses on private training, and the proposed techniques can be combined with those prior methods. Given the current model parameter
x E Id and loss function ff R + R, the widely used two-poin zeroth-order gradient estimator [4] involves two evaluations of function values:
gx (x;x;) f(x + xu; - f(x Au; E) U
(I)
2\
where & is a randomly sampled training data point, u E Id is uniformly sampled from the Euclidean sphere Vd and A > 0 is the smoothing parameter. Let be uniformly sampled from the Euclidean ball VaBd = {x E [=]|| S vd). Define the smoothed version of f(-) as fa (z)
E. + {.)]. We have that (1) fx(x) is differentiable and (2) E,, [xxx(x;; &,]] = V (a) 4 g.
indicates that by using the zeroth-order gradient estimator, we are asymptotically optimizing a
smoothed version of the original objective f()), where the smoother is a ball with radius Avd.
Differentially private zeroth-order optimization. The desired private gradients expensive to obtain in DP training, because gradients have to be generated and privatized at a granularity of samples as opposed to mini-batches. Therefore, recent work has considered privatizing zeroth-order algorithms [8] 7 27 28 by first clipping the function queries and then adding proper Gaussian noise. Specifically, based on the non-private two-point estimator on one sample (Eq. (I), the private zeroth-order gradient (I; B) is computed by
1 5
[(x + Au: f(x )u;E) +
(x; =
clipe EEB
u
2A
where b = BB| is batch size, ~~ sampled uniformly from sphere Vdsd-1 We can query the raw data multiple times per iteration by sampling multiple u's to improve the estimate (Section 3). Prior private zeroth-order work mostly focuses language model tuning with prompts, and additionally there still exists a big performance gap between zeroth- and first-order methods 7 27]. In PAZO, we use public information to guide the gradient estimate on private data, as discussed in the next section.
is privacy noise, and u is random direction, e.g..
3 PAZO: Public-Data-Assitee Private Zeroth-Order Optimization
Given zeroth-order oracles on private data and first-order oracles on public data, we aim to blend public gradients into the private zeroth- veroth-order framework to improve privacy/utility tradeoffs, while retaining the efficiency benefits of vanilla zeroth-order updates. In this section, we propose three approaches using this public prior that significantly outperform zeroth-order baselines without public data and result in competitive/superior performance relative to DP-SGD with public data. We analyze their convergence properties in Section
3

---

3.1 PAZO-M: Mixing Zeroth-Order Estimates and First-Order Gradients
PAZO-M linearly combines the public gradient with the private two-point estimator (Eq. 22 At each iteration t, sample public batch, obtain its batch gradient, and mix it with the private two-point gradient estimate. We run private two-point estimation @ times to reduce its variance. Since we query the same raw private mini-batch q times, we need to add more privacy noise (q times more variance) to ensure the same DP as querying once. The updating rule is summarized in Algorithm bbelow.
We note that the norm of two-point gradient estimates is approximately d times that of the true private gradient [6), so it is important to align their norms so that tuning the mixing coefficient can be casier. To achieve this, we sample u uniformly from the sphere r with radius r = d' so that E.,, [=)])()))]] = I (z)]l The proof is detailed in Appendix A The mixing coefficient a can be adjusted to change the emphasis on the public gradient. Although is introduced hyperparameter. as shown in experiments (Section(5). 5). PAZO-M is robust to a wide range of a values in (0, 1) as well the public batch size U/ long the L2 norms of 9pab and ğ/q are aligned.
Despite its simplicity. PAZO-M M demonstrates competitive performance among all three PAZO variants (Section()). While prior work has explored mixing gradients and zeroth-order estimates for memory efficiency in non non-privee private settings [29]. PAZO-M differs from this work in terms of the effective optimization objectives, bias-variance tradeoffs, analyses, and application settings.
Algorithm PAZO-M
Input: T. noise multiplier a, clipping threshold C, stepsize 1,, smoothing parameter X, mixing coefficient initialization Zo E IR",, number of queries g. private and public batch sizes b and B 2: for t = -,...
do 3: Sample a mini-batch B (B b) of private training data {fI,...,Eu Eo}
4: Sample a mini-batch B' BB'' b/) of public data and obtain its gradient Ipub
5: + Od
6:
for each of the q queries do
Sample uniformly from the sphere d
7:
8:
g g g + E+ clipo (( f(x, -(us)) )o15)))
+ 2) u, where 2 ~ (N((0,0200))
2A
9: end for
10: I++1 < - (Cr + +1--a)0/a)
11: end for
3.2 PAZO-P: Sampling Public Gradient Subspace
Recall that the two-point estimator samples perturbations u in the sphere Vdga-1_ Such random exploration along two directions Au and -u can result in loose estimation of the real gradients in high-dimensional settings. In this section, we assume the true gradient on private data close to the space formed by public gradients. Based on this assumption, estimates to lie in the subspace spanned by the public gradients, and use function queries to learn the coefficients associated with the components of the public gradient subspace (named PAZO-P). This gives us a much lwwer-dimensional optimization problem.
constrain the private gradient
Formally, suppose we have access to & (k < d) mini-batch stochastic gradients obtained on public data. Denote a concatenation of them as a matrix G E dd Let u E I be a random vector that is uniformly sampled from the sphere / Vks*-1, We propose the following update rule (sampling only one u as an example) in the non-private case:
[( xGu; -((-))((e) 10(x-(xxcca -AGu; Gu,
(x:
2A
which can be interpreted as learning the coefficient R linearly combine the public gradients. Further, if we orthonormalize the columns of G. g (x; {) estimates the orthogonal projection of the true gradient the public gradient subspace when À 0, i.e.,
E. (z) = E., [x)x) GuGul Proje (z)())).

---

We compare the visualization of sampling in the full dilenssonn space and public gradient subspace in Figure 7 For private training, we privatize each estimate (in the public gradient subspace) using the standard subsampled Gaussian mechanism, described in Algorithm 2
Algorithm PAZO-P
Input: Same as Algorithm| 1 and number of public batches < d
2: for 6= 0,... 1 do
3: Sample a mini-batch B( B b) private training data (6)
4: Sample & batches of public data and obtain their normalzeed gradients (01.... 9
5: G < [g......90 9k) : < 0d
6: for each of the q queries do
7:
Sample u uniformly from the sphere Vks*-1
-+ (i [ (?Ei=,clip
((se+tGGu.))-fee ( ) Gu, where 2~ ((0.CCC2))
8:
9: end for
J++1 Tz ng/9
11:
end for
PAZO-P is conceptually related to the idea of model soup, where extensive research has shown that simple convex combination of the model parameters can result souped model that generalizes well even in out-of -iito---iitribttion tasks [30 31.
Previous work proposes constraining the random search the principal components of surrogate gradients [32]. PAZO-P differs from theirs in allowing to use non-orthonormalized G. Section presents the performance of PAZO-P with orthonormalization, and the complete results in Tables demonstrate the competitive performance of PAZO-P without orthonormalization.
3.3 PAZO-S: Select the Best Public Gradient
PAZO-P offers ways to better combine public gradients via zeroth-order function evaluations, while in this section, we take an alternative approach by optimizing an approximation of the problem. Note that for convex function f. for any probability distribution Ak. k public gradients {gi...., and model parameter E Rdd, we have that
k
min f AE
x
aj9i
S
min Caff(z 19;) = min f(x 795). acA; j=1
jE[k]
where the upper bound minje(M] f(x ng,) can be easily optimized and privatized (as long as small) with access queries of f(-) evaluated private data. Inspired by this observation, propose PAZO-S, method that selects the best public gradients based on loss values on private data, i... solving minje(k] f(x (19;) (Line 5-8 in Algorithm 3). Considering the residual error between
Algorithm 3 PAZO-S
1: Input: Same as Algorithm 2 and perturbation scale
2: for 0, ..... - do
3: Sample a mini-batch B b) of private training data (EI,,..,Es)
4: Sample l mini-batches of public data and obtain their gradients {g1, ... g
5: for j 1...., & do
6:
f - E/m clipe (f(x= (.)) + where ~ WN(0, (k: 1)
7:
end for
8:
- arg minje(t) fj
9:
9k+1 9j + where 2/ NN(,
10:
[K+1 + Σb clipo (f(x+ 11)+) + where LN(1 (k 1)(202)
j* +- arg mi+
12:
It+1
13: end for

---

the public and private subspace, we create an additional noise vector 2' (Line 9), add it to the best public gradient (indexed with j). and perform another comparison between private f(r - n93) and private f(x v(93 + z²)) (Line 11). While PAZO-S is motivated by the arguments under convex f (Eq. 3 ). we apply it to all the tasks and models that are non-convex.
3.4 Privacy Guarantees of PAZO
The privacy guarantees of all three methods can be analyzed in the same way. At each iteration, guarantee the Le sensitivity of the sum the function queries by C, and we add Gaussian noise with variance qC'2a² where q the number of queries the sampled data. Therefore, the privacy bound per iteration is the same for any q. following the n-fold composition corollary of the Gaussian mechanism [33]. Applying standard moments accountant method [ to compose across T rounds with sampling ratio b/ n. we have that there exist constants C₁ and C2 such that for any E < C/bTT/n?,
byTlog(1/6)
all three Algorithms
private for any 8 > 0 2 C2
RE
Convergence Analysis
In this section, we study the convergence properties of three PAZO algorithms. We first define the similarity between public and private data through the distance between the full gradients follows.
Definition 4.1 (ry-similarity). Denote (xx) and V f (2x) the gradient for model xa at time step t under the full public and private data, respectively. We call public and private data 7-similar if [[V fxx))] S 7 for all L.
We note that such similarity is defined top of the full gradients, weaker requirement than defining on the stochastic gradients. There are previous similarity metrics based on coordinate- wise gradient norm alignment [16). Together with their assumption on the bounded gradient norm, their similarity condition implies ours and is thus a stronger assumption. Next, we present additional assumptions.
Assumption 1. f(x; E) is M-Lipschitz for any x E RRd and any subset data E.
Assumption 2. f(;; is L-smooth for any E IRd and any subset data &. Assumption 3. The variance of private stochastic gradients is bounded, i.e., B[IVf[(m ff(x)) S for any private sample & and any t.
Assumption 4. The variance of public stochastic gradients is bounded, i.e., Vf (=((=))) for any public sample E and any t.
Theorem 4.1 (Convergence of PAZO-M). Assume public and private data are --smmilar Let Assumptions 1-4 hold. For possibly non-convex (()), running Algorithm 7 Junder fixed learning rate for T rounds gives
1 T
$o (+) +)+00 +0
( (22
o²
(4)
b
b2
t=
Additionally, let 0j and 02 be the constants that make PAZO-M satisfy (c, 8) didfffeerettaa privacy for any e, c/bTT/n² > O. Then PAZO-M obtains the error rate
a v- +0 +0
avd
of (1-o)V of a²
2(1 a) avd (1 -1-a) ()=a)Vd+a & (1 (1-a)Vd+al1--0
a(1
by choosing the parameters
2(1 aovd
A La
0=1+ /2di M, and
T= (ne((1-avol + a
2Llf(z)) - f(x.)]
c,C12(11 a) + avd
Vdlog(1/0)

---

We present several discussions on the results. First, we see that the first term in the error rate has dependence (²- Vd), which saves factor of log d compared to DPZero, together with constant improvement if a > 1/2 Due to the usage of biased public gradients, we additionally have error O()2avd Vd/b'), which decreases to 0 as a decreases to O. Second, there is term related to the variance of the stochastic gradients of /b, which is standard when we assume constant learning rates (34) and would reduce as the batch size increases. Third, we provide a conservative upper bound by choosing the clipping threshold C' larger than needed. We can also naturally extend our current analysis to incorporate more advanced clipping analysis [8].
Theorem 4.2 (Convergence of PAZO-P). Let assumptions in Theorem 4.1 hold. For possibly non-convex ((),, running Algorithm 2 under fifixed learning rate for T rounds gives
T-1 BIIVI
(+)
(V
02 + 6
0²
T Σ
(5)
b
62
Additionally, let ej and 02 be the constants that make PAZO-P satisfy (e, 8) -ddiferrenti privacy for any e < <, n2Ttn2,00 O. Then PAZO-P obtains the error rate
O(k)+0 (V o2 of
by choosing the parameters
1 2Lh
nE C2O
(L f(xx)) (188)
A
C=1+V2kM and T
LK=2"
This shows that we have d-independent error rate O(k), with the dimension of the subspace being small a constant is < log d in practice. We additionally have the error term O(~² + o /b) from the biased stochastic public gradients and O /b) from the stochastic private gradients.
Theorem 4.3 (Convergence of PAZO-S). Let assumptions in Theorem 4.1 hold. For possibly non-convex [()), rumning Algorithm 3 under a fixed learning rate for T rounds gives
T-1
B[IV S o ( +0 10
+
of 6'
Σ t=0
+ +
(6)
T
This allows us to take T - oc, 17 = 1/(4)), and S <1/Vd to achieve a d-independent error bound O(1² /B)."). When y + 0, the remaining term 02/6'' is due to stochastic public data sampling.
We give complete statements and proofs for Theorem 4.1 4.2 and 4.3
Appendix B.2
B.3 and B.4
Additionally, if we further assume the bounded loss that for some constant S, (f
S S for all f.
we can use smaller noise in proofs under the same privacy budget. This yields improved error bounds
that O 1- d()) for PAZO-M and O Te log k) for PAZO-P, whose complete statements and proofs
given in Appendix B.5 and B.6 We summarize the baselines and our error bounds in Table I
5 Empirical Evaluation
In this section, we present the empirical performance of PAZO-(M.P.S) across both vision and language domains, and pre- pre-training, fine-tuning, and prompt tuning tasks. In Scction we introduce experiment setups including datasets and models. In Section [.2] we present the privacy/utility tradeoffss of PAZO, showing that PAZO performs comparably to public data augmented first-order methods over a number of tasks in moderate privacy regimes and outperforms them in highly private regimes. In Section [.3] highlight the time efficiency of PAZO. In Section 5.4 we present the sensitivity study of the hyperparameters, showing that PAZO is non-sensitive to introduced hyperparameters. Our code is publicly available at gightt......... ctt.uub..om/uuccheee www.xuchengoog//////cc/ccccc (aazgggoooooooo//o/o
5.1 Experimental Setups
The settings of our experiments cover and follow the experiments in the existing DP literature, including (1) Training NFResNet18 on CIFAR-10 (35] from scratch, (2) fine-tuning Places365
7

---

pre-trained VīT-S on Tiny-ImageNer (3),, (3) training LSTM on IMDB [37 from scratch, and (4) fine-tuning RoBERTa-base with prompts on MNLI 38 We introduce distribution shifts between private and public data, such class imbalance and semantic context shifts of various extents. The details of public data generation and the impact of different public data distribution shifts on algorithm performance and 7-similarity values are presented in Appendix
5.2 Improved Privacy/Utiliity Tradeoffs
CIFAR-10
Tiny-ImageNet
40
70
Accuraty (80
Accuracy (SG)
35
30-
50-
25-
IMDB
MNLI
Accuneyy (86)
70
Accuracy
60
50
50-
8.0.5
/=1 2-2
8-2
DP-SGD
DOPE-SGD
DPZeem
PAZO-P
DPMD
GEP
PAZO-M
PAZO-S
Figure 2: Performance of PAZO and the baselines in four settings. It shows that (1) all three PAZO variants outperform DPZero across all datasets, (2) all of the first-order methods (DP-SGD, DPMD, DOPE-SGD, and GEP), with or without public data, are more sensitive to smaller e's than zeroth- order ones, and (3) when e's are small, PAZO is superior to first-order baselines. "Fail" indicates failure to converge; the detailed accuracy numbers are in Tables 2
CIFAR-10
Tiny-ImageNeet
IMDB
38
80
75
Accuracy (8)
60
Z0++UB (PAZO)
ro
TO-PUB
32
(50
70
Accuracy
60-
6.5
35
20
60
28
55
26
50
50-
Privacy cy budget
Privacy budget
Privacy budget
Privacy budget 8
Figure 3:
We compare the best private zeroth-order (70) methods with the best private first-order
(FO) methods, with public data (+PUB) or without. Note that 7O+PUB is PAZO. shows that (1) with or without public data, the performance gap between ZO and FO decreases using public data expands the range of s's where ZO methods outperform FO ones, and (3) ZO+PUB (PAZO) achieves better privacy/utility tradcoff than FO+PUB when e's are small.
decreases, (2)
First, we compare PAZO with vanilla zeroth-order methods and various strong first-order baselines with public data under various privacy budgets ε = {0.1, 0.5, 1, 2, 3}. In Figure 2 we compare with (I) DP-SGD [ the plain first-order method without public data, (2) DPZero (8), the plain zeroth-order method without public data, and (3) the state-of state-of-the-ar first-order algorithms with public
data, including DPMD (3), GEP 40). and DOPE-SGD 4
We observe that all three PAZO variants outperform DPZero across the four datasets, though there not single PAZO algorithm that dominates other PAZO instances in all settings. In addition, all of the first-order methods (DD-SGD, DPMD, DOPF-SGID, and GEP), with or without public data, much more sensitive to more strict privacy requirements (smaller e's) than zeroth-order ones.
8

---

CIFAR-10
Tny-imageNett
IMDB
MML
0.65
Acouracy (66)
0.60
0.55
2.5
0.24
0.50
0.55
0.4
D02emo
0.20
0.5
0.40
Stops (x 4)
Steps (x4]
Steps (x4)
Staps (x4)
Figure 4: Convergence speed of private zeroth-order methods with (PAZO) without (DPZero) public data. We observe that PAZO variants have slightly different convergence speed, but they are all consistently faster than the baseline. The reported are smoothed test accuracies under privacy 1.
CIFAR-10
Tiny-ImageNet
IMDB
MNLI
75.0
70
67.5
Accuracy (9)
65
Putter
32
70.0
65.0
60-
30
62.5
65.0
60.0
0.25
0.50
0.75
0.2
0.4
0.1
0.2
1.0
1.5
2.0
Speed (s/iter)
Speed (silter)
Speed (sliter)
Speed (sfiter)
DP.SGD DPMD
DOPE-SGD
DPZero PAZO M
PAZO
GEP
PAZO S
Figure 5: The utility/speed tradeoffs of different methods. shows that PAZO is up to 16x faster in each training iteration than FO and FO+PUB while being comparably performant. The reported results are under privacy budget e = 1, and the detailed numbers are in Table g
This suggests that PAZO (and zeroth-order methods in general) possess more robust privacy/utility tradeoffss than the first-order methods across model types, training types, and task domains. Under small =", PAZO is superior to first-order baselines by a large margin. We provide concrete accuracy numbers in Tables
in the appendix.
Furthermore, we report performance the best PAZO variant among three (denoted as 'ZO+PUB') and performance of the best different 3 shows that although vanilla zeroth-order (ZO) may underperform first-order (FO) methods, if we augment both with public data, PAZO performs comparably or even superior to the best first-order approach with public data (FO+PUB), while being more memory-effiiient.
first-order method (denoted as 'FO+PUB') under
5.3
Time Efficiency
In this section, we present the time efficiency of PAZO. It is faster than private first-order methods (with or without public data) as does not require per-sample gradient clipping, and also converges faster than private zeroth-orde baselines.
# IIterations to converge. MeZO and DPZero present results with zeroth-order methods running 100x and 10x more steps than first-order ones 66] g but PAZO converges much faster due to assistance from public data. Figure plots the convergence speed of DPZero and PAZO-(M P. S), illustrating that public information significantly accelerates the convergence of (private) zeroth- order methods. This property is particularly favorable to differentially private training as smaller accumulative noise would be added due fewer iterations needed to converge.
Runtime per iteration. Theoretically, we compare the number of different operations in each method in Table Since the number forward and backward passes in first-order methods depends on the private batch size, first-order methods can be dramatically slow since large-batch training is favorable in DP [4 42 Empirically, we compare speed of each method in terms of training time per iteration. Each experiment is conducted on one 48GB L40S GPU. For fair comparison,

---

we adopt optimized implementations to speed up first-order DP algorithms, including vectorization, just-in-time compilation, and static graph optimization 22. In practice, due to the memory burden of parallelization and compilation overhead, a hybrid of vmap and sequential processing is often faster. We choose the fastest implementation for each first- and zeroth-order method under memory constraints. By comparing the utility/speed tradeoff (Figure 5). we observe that PAZO is comparable to or more performant than the baselines, while being 2 ~ 16x faster in each training iteration.
5.4 Robustness to Hyperparameters
CIAA-110
MNLI
0.25
0.5
0.75
0.25
0.5
0.25
We have each method's hyperparameters tuned via grid search, and the detailed grid values are in Appendix C.3 Zeroth-order methods sample q random directions to duce variance in each iteration, so we perform preliminary studies on q E {1, 5) for each setting and choose q if the performance gap is negligible. As shown in Table DPZero benefits from increased q for improved accuracy, while PAZO has reduced dependence on q's due to the guidance from public information.
70.3
70.5
70.2
67.4
66.9
32
66.8
68.4
67.2
32
67.5
67.1
67.5
6
10
6
10
70.3
PAZ040
16
67.8
68.1
68.1
16
69.2
68.8
69.7
32 68.6
68.0
67.7
32
69.7
70.3
68.9
16
128
16:2
67.2
67.5
68.8
19200-5
11e-3
69.7
68.5
68.9
16-3
68.1
68.1
68.5
Furthermore, compared to vanilla zeroth-order methods, PAZO has additional hyperparameters due public data sampling, including the public batch size b', the mixing coefficient a, number public candidates k, and the per- turbation scale e. However, as presented in Figure 6 and Figure the performance of all PAZO variants is robust the values of these hyperparameters. In fact, wide range of combinations of these hyperparameter values can yield performance close to the best performance we report.
1e-d
69.8
67.8
68.1
1e-8
68.8
67.3
68.1
69.5
68.2
69.0
66.9
67.3
66.5
Figure 6: PAZO is non-sensitive their introduced hyperparameters. Each num- ber represents the best accuracy after the standard hyperparameters for zeroth- order private optimization (C and 7)) are tuned. Blue cells indicate PAZO-S per- formance w/o noisy candidate.
6 Conclusion and Future Work
We propose PAZO, a suite of public-dtta-assisee zeroth-order optimization methods for differentially private training. By leveraging modest amounts of public data and their gradients to guide zeroth- updates, PAZO significantly improves the privacy/utility tradeoff over prior zeroth-order approaches while preserving their computational efficiencies. Through theoretical analysis and experiments across vision and language tasks, we demonstrate that PAZO closes the gap between zeroth- and first-order methods moderate privacy regimes and even surpasses the best first-order baselines with public data under high privacy constraints. Our results position public-atta-assisted zeroth-order optimization as a practical and scalable alternative for private training, especially in settings where private first-order methods are costly infeasible. Future work could include sharpening the current convergence bounds by considering other similarity metries and exploring a broader set of public and private dataset pairs in practical DP training applications.
Acknowledgement
We thank Kamalika Chaudhuri, Chuan Guo, Saeed Mahloujifar, and Manzil Zaheer for helpful discussions at early stages of this project. We acknowledge the NAIRR Pilot program and AWS for contributing cloud credits support this research project.
References
[1] 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 on computer and communications security, pages 308-318, 2016
[2] Pranav Subramani, Nicholas Vadivelu, and Gautam Kamath. Enabling fast differentially private sgd via just-in-time compilation and vectorization. Advances in Neural Information Processing Systems, 14:26409-264211 2021.
10

---

[3] Sebastian Rodriguez Beltran, Marlon Tobaben, Joonas Jälkö, Niki Andreas Loppi, and Antti Honkela, Towards efficient and scalable implementation of differentially private deep learning.
[4] John C Duchi, Michael Jordan, Martin J Wainwright, and Andre Wibisono. Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Transactions Information Theory, (155:27788-288 2806, 2015.
[5] Jack Kiefer and Jacob Wolfowitz. Stochastic estimation of the maximum of a regression function. The Annals of Mathematical Statistics, pages 462-466, 1952.
[6] Sadhika Malladi, Tianyu Gao, Eshaan Nichani, Alex Damian, Jason D Lee, Danqi Chen, and Sanjeev Arora. Fine-tuning language models with just forward passes. Advances in Neural Information Processing Systems, 01555338-53077 2023.
[7] Xinyu Tang, Ashwinee Panda, Milad Nasr, Saeed Mahloujifar, and Prateek Mittal. Pri- vate fine-tuning of large language models with zeroth-order optimization. arXiv preprint arXiv:2401. 04343, 2024.
[8] Liang Zhang, Bingcong Li, Kiran Koshy Thekumparampil, Sewoong Oh, and Niao He Dpzero: Private fine-tuning of language models without backpropagation. arXiv preprint arXiv:2310.09639, 2023.
[9] Shaocong Ma and Heng Huang. Revisiting zeroth-order optimization: Minimum-variange two-point estimators and directionally aligned perturbations. In The Thirteenth International Conference on Learning Representations.
[10] Yihua Zhang. Pingzhi Li, Junyuan Hong, Jiaxiang Li, Yimeng Zhang, Wenqing Zheng, Pin- Yu Chen, Jason D Lee, Wotao Yin, Mingyi Hong, et al. Revisiting zeroth-order optimization for memory-efficient IIm fine-tuning: A benchmark. arXiv preprint arXiv:2402.1 1592, 2024.
[11] Aochuan Chen, Yimeng Zhang, Jinghan Jia, James Diffenderfer, Jiancheng Liu, Konstantinos Parasyris, Yihua Zhang. Zheng Zhang, Bhavya Kailkhura, and Sijia Liu. Deepzero: Scaling up zeroth-order optimization for deep model training. arXiv preprint arXiv:23 23.002230000225: 2023.
[12] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography Conference, 2006.
[13] Kamalika Chaudhuri, Claire Monteleoni, and Anand D) Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12(3), 2011.
[14] H Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. arXiv preprint
2017.
[15] Tom Sander, Yaodong Yu, Maziar Sanjabi, Alain Durmus, Yi Ma, Kamalika Chaudhuri, and Chuan Guo. Differentially private representation learning via image captioning. arXiv preprint arXiv:2403.02506, 2024.
[16] Tian Li, Manzil Zaheer, Sashank Reddi, and Virginia Smith. Private adaptive optimization with side information. In International Conference on Machine Learning, pages 13086-1333 13105. PMLR, 2022.
[17] Hilal Asi, John Duchi, Alireza Fallah, Omid Javidbakht, and Kunal Talwar. Private adaptive gradient methods for convex optimization. In International Conference on Machine Learning, pages 383-392. PMLR, 2021.
[18] Xuechen Li, Florian Tramer, Percy Liang, and Tatsunori Hashimoto. Large language models be strong differentially private learners. arXiv preprint arXiv:21 2021.
[19] Yingxue Zhou, Zhiwei Steven Wu, and Arindam Banerjee. Bypassing the ambient dimension: Private sgd with gradient subspace identification. arXiv preprint arXiv:2007.038)) 2020.
[20] Zhiqi Bu, Yu-Xiang Wang, Sheng Zha, and George Karypis. Differentially private optimization on large model at small cost. In International Conference on Machine Learning, pages 3192- 3218. PMLR, 2023.

---

[21] Pin- Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh. Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM workshop artificial intelligence and security, pages 15-26,
2017.
[22] Andrew Ilyas, Logan Engstrom, Anish Athalye, and lessy Lin. Black-box adversarial attacks with limited queries and information. In International conference on machine learning, pages 2137-2146. PMLR, 2018.
[23] Astha Verma, AV Subramanyam, Siddhesh Bangar, Naman Lal, Rajiv Ratn Shah, and Shin ichi Satoh. Certified zeroth-order black-box defense with robust unet denoiser. arXiv preprint wrXiv:2304.06450 2023.
[24] Bin Gu, Guodong Liu, Yanfu Zhang, Xiang Geng, and Heng Huang. Optimizing large-scale hyperparameters via automated learning algorithm. arXiv preprint arXiv:2102.09026, 2021.
[25] Samuel C Hoffman, Vijil Chenthamarakshan, Kahini Wadhawan, Pin-Yu Chen, and Payel Das. Optimizing molecules using efficient queries from property evaluations. Nature Machine Intelligence, 4(1):21-31, 2022.
[26] Florian Meier, Asier Mujika, Marcelo Matheus Gauy, and Angelika Steger. Improving gradient estimation in evolutionary strategies with past descent directions. arXiv preprint arXiv:1910.05268, 2019.
[27] Zhihao Liu, Jian Lou, Wenjie Bao, Yuke Hu, Bo Li, Zhan Qin, and Kui Ren. Differentially private zeroth-order methods for scalable large language model finetuning. arXiv preprint arXiv:2402.07781 078.88 2024.
[28] Qinzi Zhang, Hoang Tran, and Ashok Cutkosky. Private zeroth-order nonsmooth nonconvex optimization. In The Twelfth International Conference on Learning Representations, 2024. URL httthttt/////errettttt
aet//forumt id -dw.miidd--22222222000
[29] Zeman Li, Xinwei Zhang, Peilin Zhong, Yuan Deng. Meisam Razaviyayn, and Vahab Mirrokni. Addax: Utilizing zeroth-order gradients to improve memory efficiency and performance of sgd for fine-tuning language models. arXiv preprint arXiv:2410.06441, 2024.
[30] Mitchell Wortsman, Gabriel Ilharco, Samir Ya Gadre, Rebecca Roelofs, Raphael Gontijo-Lopes. Ari S Morcos, Hongseok Namkoong, Ali Farhadi, Yair Carmon, Simon Kornblith, et al. Model soups: averaging weights of multiple fine-tuned models improves accuracy without increasing PMLR,
inference time. In International conference on machine learning, pages 2022.
[31] Francesco Croce, Sylvestre-Alvise Rebuffi, Evan Shelhamer, and Sven Gowal. Seasoning model soups for robustness to adversarial and natural distribution shifts. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 12313-12323, 2023.
[32] Niru Maheswaranathan, Luke Metz, George Tucker, Dami Choi, and Jascha Sohl- Schl-Dickstein. Guided evolutionary strategies: Augmenting random search with surrogate gradients. In International Conference on Machine Learning, pages 4264-4273. PMLR, 2019.
[33] Jinshuo Dong, Aaron Roth, and Weijie J Su. Gaussian differential privacy. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 84(1):3-37, 2022.
[34] Manzil Zaheer, Sashank Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive methods for nonconvex optimization. Advances in neural information processing systems, 31, 2018.
[35] Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar- (canadian institute for advanced research). URL http::/www cs wwwottooooooooooo wwwpettt..ddurrrii//eeee html
[36] mnmoustafa and Mohammed Ali. Tiny imagenet. ftips://kagglee wtt.:agggl...oommommtttttooooooe
ting-imagenet 2017. Kaggle.
12

---

[37] Andrew L. Maas, Raymond E. Daly, Peter T. Pham, Dan Huang, Andrew Y. Ng. and Christopher Potts, Learning word vectors for sentiment analysis. Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pages 142-
150, Portland, Oregon, USA, June 2011. Association for Computational Linguistics. URL http://www aclweb.
[38] Adina Williams, Nikita Nangia, and Samuel R Bowman. A broad-coverage challenge corpus for sentence understanding through inference. arXiv preprint arXiv:1704.0553 2017.
[39] Ehsan Amid, Arun Ganesh, Rajiv Mathews, Swaroop Ramaswamy, Shuang Song, Thomas Steinke, Vinith M Suriyakumar, Om Thakkar, and Abhradeep Thakurta. Public data-assisted mirror descent for private model training. In International Conference on Machine Learning, pages 517-535. PMLR, 2022.
[40] Da Yu, Huishuai Zhang, Wei Chen, and Tie- Yan Liu. Do not let privacy overbill utility: Gradient embedding perturbation for private learning. arXiv preprint arXiv:2102.126% 2021.
[41] Milad Nasr, Saced Mahloujifar, Xinyu Tang, Prateek Mittal, and Amir Houmansadr. Effectively using public data in privacy preserving machine learning. In International Conference on Machine Learning, pages 25718-25733 PMLR, 2023.
[42] Yaodong Yu, Maziar Sanjabi, Yi Ma, Kamalika Chaudhuri, and Chuan Guo. Vip: A differentially private foundation model for computer vision. arXiv preprins arXiv:2306.088842 2023.
[43] Andy Brock, Soham De, Samuel I. Smith, and Karen Simonyan. High-performance large-scale image recognition without normalization. In International conference on machine learning. pages 1059-1071. PMLR, 2021.
[44] Alexey Kurakin, Shuang Song, Steve Chien, Roxana Geambasu, Andreas Terzis, and Abhradeep Thakurta. Toward training at imagenet scale with differential privacy, 2022. URL https://arxiv. (t//abxs/200.123288 2022.
[45] Bolei Zhou, Agata Lapedriza, Aditya Khosla, Aude Oliva, and Antonio Torralba. Places: A 10 million image database for scene recognition. IEEE transactions on pattern analysis and machine intelligence, 40(6):1452-14) 1464, 2017.
[46] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition scale. arXiv preprint arXiv:2010.119299 2020.
[47] Xiang Zhang, Junbo Zhao, and Yann LeCun. Character-level convolutional networks for text classification. Advances neural information processing systems, 28, 2015.
[48] Samuel R Bowman, Gabor Angeli, Christopher Potts, and Christopher Manning. A large annotated corpus for learning natural language inference. arXiv preprint 1oXiv:1508.0533 2015.
[49] Soham De, Leonard Berrada, Jamie Hayes, Samuel Smith, and Borja Balle. Unlock- ing high-accuracy differentially private image classification through scale. arXiv preprint arXiv:2204. 13650, 2022.
13

---

A Algorithm Details
A.1 PAZO-M Norm Alignment
To jusify sampling the perturbation from the sphere with radius dt, we present the following analysis. For a random direction sampled uniformly from sphere of radius r, the two-point estimator gx (2) has the squared norm
2 ,² (1)(1)) [f Au) A Xu) )
2A
The Taylor expansion of f with O(A²) terms ignored gives f(x + Aw) ~ f(x) + (V)(() Tu,
u, hence
[=)()))| ()f(x)))33+
Since Eu [wu Bu[uu]] 1 2² L
Eulllaa(<)11) R ( = ->v[(<(x) Bm (VS(x) - |V
We thus have 1lgx (z) ~ |V](')] ifr d
A.2 PAZO-P Perturbation Sampling
We visualize the sampled perturbation set of the vanilla zeroth-order methods and PAZO-P as follows. We set d 3, i 2 and generate G E R3322 with normalized columns represent the public gradients. The vanilla zeroth-order method samples the perturbations u in the full-dimensional sphere (R*),, while PAZO-P samples in the column space of G. When G orthonormal, we sample fairly in every direction in the public gradient subspace; when G is not orthonormal, we have larger effective learning rates in the directions which the public gradients agree.
V83a
Guar Guoly/KK (RT 2)
Gan(VEa 9)
14
M2
2
59
54
Figure 7: Comparison of the sampled perturbations full-dimensional space and the public gradient subspace. in and u2 denote the top-2 left singular vectors of normalized G. Left: Vanilla zeroth-order perturbation sampling from d Middle: Sampling from G G(Vīs*-1) where G has normalized columns, which is functionally the border of a sphere elongated in the directions of top public gradient singular vectors. Right Sampling from G( G(Kks=11 where G is orthonormal.
B Detailed Convergence Analysis
In this section, we provide detailed proof of convergence for PAZO-(M,PS) with and without the bounded loss assumption that f(x))] < S, vt. We summarize the convergence of DP-SGD, DPZero, and our method in Table Without the bounded loss assumption, we choose the clipping threshold C' larger than needed, which results in more pessimistic bounds. With the bounded loss assumption, we follow Zhang et [8] to upper-bound the probability of the event that clipping ever happens throughout the training, which results in better choices of clipping threshold and thus tighter bound.
14

---

Table 1: Convergence enror rate of DP-SGD, DPZero, and PAZO-(M.P,S) in terms of model dimension d, with and without the assumption that [f(x))] I S, vt. We denote as some constant independent of the model dimension d and number of public gradients k.
Method
Without [f(x)) - S
With [f()) S
DP-SGD
O(va)
/ OlVdlog d)
DPZero
PAZO-M
0 v B.2
0 0
BBB
PAZO-P
((k) 1S B.3
Ol k log k) 1 B.6
PAZO-S
(c)) [$B.4
B.1 Lemmas
Lemma B.1. Let the private and public data be 7-similar and Assumption 3 3and hold. Denote
b b= and D' |B as the private and public batch sizes, respectively. Denote gt = (x+) and g. = V (xx) as the gradient under full private and public data, respectively. Due to the stochasticity of sampling, the private and public batch gradients are
Vf(z;; = b
Σ (gr Ges) and (Tr; iE
1
Σ SEB
(gl + (.i)
D'
where St.s is independently sampled from some noise distribution D with zero mean and bounded variance of: Se, is independently sampled from some noise distribution D' with zero mean and bounded variance oz: B2 and B; are private and public batch at step I, respectively. So we have
| B1) (x BI1l1 < IE[l V f B,) v f B
EEll. 1617+BB +E
1 1
Σ
Gr. iEB.
+
Σ Gr. iE
< 2²² of oz
1/
where the first inequality is due to Jensen's 's inequality.
Lemma B.2 (Zhang et al. 8, Lemma C.I and C.2). Let u uniformly sampled from the Euclidean
sphere v dddd-1 and v be uniformly sampled from the Euclidean ball v /d = {z E Rd || S vd). Let a E Bdd be some fixed vector independent of u. We have
1. E., [u] = and E,, |uu " Ia-
2. [u,[u [llTaal a] O. Eu((u T a)² ||a|12, and EE, (auuju =a.
3. For any function f(x) : Idd + R and X > O, we define its zeroth-order gradient estimator as
(x(x)) [[=-Xa)-[(E-auj) and the smoothed function as fx(x) E, [f + du)). Then
2X the following properties hold
(a) fx(x) is differentiable and E, = -VAx)))
(b) If f() is L-smooth, then we have
I [V - - 3/23/2
1
(. 24 |Vf(())1
xzd.
15

---

B.2 Convergence of PAZO-M
Theorem B.3 (Full statement of Theorem 4.1p. Let the private and public data be --siillar and Assumption and hold. For possibly non-convex f(-), running Algorithm forr T rounds gives
( (2o) f(x.))
(1-a) +2LAd
1-a
f(.)))
M
T
(2(1-a)
2(1 2(1-a)-avd
avd
12 ofvd
1-a
+2
2(1 (11a))t +ayd
b
262
(1 (1-a)vdta
02 advd
LAdiy
LAd
+ 2 (1-a)-Vdta(1-a))
+
7+
M
a
2
2
(1-a)vdta
Additionally, let ej and 02 be the constants that make PAZO-M satisfy (s, 3)-difeerentia privucy for any E / 8 0. Then PAZO-M obtains the error rate
o a Vd +0 o
(??
avd
of alva
of a²va & (1-0)/(+t(1-aa)
2(1 a) + avvd b (1-a)va++ +
by choosing the parameters
- a)
C= 1+ V2d M, and
=
4L((1 - (1(110)3V]+au a))
Ld
+
2L[f(xx) f(x))
c2C12(1 a) + avdd
Vdlog(1/8)
Proof. We choose the clipping threshold C' large enough such that clipping does not happen, then the
update rule 2441 It (() (A(r; ue B₂) 21 21)ur + ag' (zz; B()) where
fare + Awa; E,) f(ra Aug Es)
A ue Bi)
Σ
21
E.
At a step 1, let Je be a fixed parameter. We apply the update to the property of L-smooth objectives and take expectation over all the randomness at this iteration, i.e., E, := B.. We have
L <((x)) + (1.)) xzl) + - Ex 1|| - xrll
2
= -(xx)) - (1 - a) (xx) T E.[A(ari us, Be Be)ue] + (1- a1= Vd
E, A (181; ue, BB)
Tb
a Lote E, Ellg' (z); (2; BDJ
on (zx),) gi a(1 a) Loj [A un B.)uy gxx B()
T3
(1 - Lnn C
262
16

---

For Tı, note that (m upu| = E, (2x ue B:)u] and when A + 0, it holds that fx(2)) =
E. (Zr Luru fx(x))] Ja ff(z)) for u, gnif(d We thus obtain
-V((x))) T E.,,
=- -VV.f(x=)' (Ara::))
+ +(1-1/ 11) V
< +11
Eu, (u.lA(2)
dd ((()))
3
76
where T3 satisfies
f(xx Aua) -f(a xwee) U1
v(())) - E,,, (1rs
S Ex
2x
dt
E, [I (f(2; + Aue) f(x: Au)) - 22 Twa)
2x
di
1 E, [I (f(zz + Awo) - -f(r)) - (x) Tu:) |]
2x
d
+
E, (f(())) - f(xx - - AV u.) |]
2
LAd
due to L-smoothness applied to the last inequality. Therefore, - (R, ue, B.)uel s
Va f(x))l + LAdd M.
For T2, note that per-sample L smootheess implies batch L-smoothness. Therefore, we follow Zhang et al. 8 by noting that
A(rru) B,)2 f( -
4X2
( (U( Aws; B.) 2
/ (x);;
2X2
(Jaa Aug Bt) (11;; B.) Au, V (I(x;;
2²
+ (f(xx:B)) f( Aug; BB) Au, Vf(z; ((),V(((
2²
( L2X2d +2( B.)r;
where (a) and (b) follow (a + 6)² < 2(a² + b² and (c) follows If Au) -u S
d/2d/2 and [f(x) f(x Au)= - Au Vf(x) < d/2 due to L-smoothness. Therefore,
Eu, [1 Ue 2 (0)
-2
2
Vf
2)11
2
Vd
L 22
2
20 byd
[
(8)
2
Vd
where (a) follows Lemma B.2 (2).
For Ts. applying the equalities
oz
E3 1llg' (zx; 1 = 11g6'12
+
b'
17

---

vf(x)) Le =2 (1ls:11² + +[+((x))1 - 11ol (((+))
B,,,B, ( u. B.)u, g (ee Bij] (fA(=))) of
- -[VA(==)))- 1l01 (.x(2)111
gives
aLnb [11
|l,Eel + -1--0) a1 IV a) 1l11 V/((E)1 + Ts. (9)
T3
LTpe
where
TTT T4
2 11% vs(x))]1
a² LLLm om
an7
2
2
a² Ln
$ q
03]
[V
(10)
2
2
We take and Th so that aLm < 1, which implies 1 Imp
1
< 1 a. We thus have
Ta Ι a(1 Lnk
|| + [V llol - V +Ta
2
= a11 - a)(g/, (9/, (xxx)) +
< a11 a)) |ل [xxx) +
S aa(1 - a) (1la) - VV +
(// +T
a ()) /2 (n/vd+ Ltd /2)M + [V(==
(11)
Combining Ti
77 T2
88 T's and T4 10
yields
nh a)
+ n Ln a)² Ln)a(1-a) [()(())]]
vd
Vd
(1 (1-a)dmdddMM (1 (1-ai an-a)
< f(x)) - [,[[((+++]]]
+ (1 -1 12
(1 - 322 Lip am717
4
21
2
+
0. Lm 03
a(1 ()) I.2 dd +
+ + am)
7
+
Ltd
28
2
Vil
2
Choosing 7t 2(1 2(1-a)+avi
have aLn, a < - 3vd-3
Denote Ezi
aL((1=a)>V
3vd-2
Eugnrer B where U=t is the set (uo..... 1 and similarly for Zet, Bet. and B' We up from t t= T - 1, telescope terms, and divide both sides by T to obtain
T
16VāL1S(zo)
a) -1- a(1 a))
+ 2TAd M
a 2(1 (1-a) avd
T
(2 - a) + =avd2=
=2Vd>
L2
olvd do?ca
1-a
+
b + 26
2(1 - -a) +avd
4
(1 - avVd+a
Vdo2
a²
LAd1
Ltd
+
+
4+
M
(1-alvd+a (12)
2
(1-
0 a))
2
2
18

---

we take o and 02 such that PAZO-M is (e, 8) -differentiall private for any < //b > O. We apply te and Eq. 12
By privacy analysis in Section 3
and then there exist constants
and obtain
T
1-0
16vdLLf(zo) f(x))((x))))))))))))( (1 aa) -) aa)
(2 22(1-a++an aVdd2 + 2LAd 1-a
T
a)1- avd
1222 olvā 3c
+ +2Vdg
+
+
- a
2(1 - (1) +avd
4
b
2n?e²
(1 - vv) +a
Vdo3
LAdin
LAd
+
+ Y 2
M
(1 (1-a)Vd+a (13)
26' (1-a)3vdl a(1 a)
2
To choose the optimal T, we organize the terms involving T, which are of the form & + qf. We
solve min7s0 $ + uT = pd by taking T = vp/g, which yields
T Ane[(1 a)vd + a] c2C a) + av Vdlog(1/6)
- -
By A A u, 5,,,, L2X2d + 2 V ( and per-sample M-Lipschitz, we have
2VdM2 S + /2d M vD / for p. q 2 0 and choosing X s -
A [1; ut, 4 S V /
due to vp
We choose 1=1+ V2d M and
LA
thus have
T
f
T
t=
402
+ 2dd M) - a)d?
1 1-a
(2Ll(xz)) f(x.)())))))))))) log (1/6) 2M
ne 2(1 a) + avd
2(1- a) + avd
avd
1
+ o7vo 1-a
+ 2
+
2(1 a) + avd
PVd
b
(1- a1-a)va+a
02
o²Vd
$12 + (
1
+
M
25' (1 (1-a)3 + a(l-a)
2
(1-a\v0ta
which indicates that the error depends on d, 01, 02 and y by avd 2(1 2(1-a)+aVi
o | a Vd +0
)
( of (1 (1-a)Vd
of B' (1-a)Vata(1-a)
a²
(1-a\vd+a
Therefore, we have error dependence 0 a vd). which saves factor of log d compared DPZero's O(v d), together with constant improvement if a > 1.- We additionally have the error term 0(72 + +z2/b') that reduces as decreases due to using biased public gradients.
B.3 Convergence of PAZO-P
Theorem B.4 (Full statement of Theorem 4.2p. Let the private and public data be simiill and and hold. For possibly non-convex f(.), running Algorithm forr T rounds gives
Assumption 7
2
3
4LK (f(av) - f(xx)] + 2M
0
E [l
+
T
T
4
t=
o?
o²C²
LAK M +
+
4
b
262
19

---

Additionally, let 01 and be the constants that make PAZO-M satisfy (s, 8C- privacy for any e //bT//n, 0. Then PAZO-P obtains the error rate
O(k) +0 (
0
of
by choosing the parameters
1
C=1+ C=1+V2kM, and ne c²C
[Lk(f((a)) - f(x))
1) 2T
AS
LK
log(1/6)
Proof. We choose the clipping threshold C' large enough such that clipping does not happen, then the It -1/e (ar,; ut, B.) + Gu where
update rule is M441
f(x, AG E,) - f(z, xG)
A un B.)
Σ
24
SER,
At a step t, let 2y be fixed parameter. We apply the update to the property of L-smooth objectives and take expectation over all the randomness at this iteration, i.e., E, == Bu,,,, BB We have
1x]4(114)
E. = 12
-f(
(V (3,..,
L E, Lid E, (Z,1)A( 11 1
2 Gr
|
(6)
Vf(x)) E, ( B.(
LAb 2 E, I. (1,,,,
Lnfo2
(14)
212
where (a) is due to the orthonormality of G. and thus ||Goul] ||uel| Vk.
For Tú, we proceed by
(v)(),, f(x)) - E. (x, un B.) [T(c=)]II E [ ue Guull
< [ E.G.G. (f(=))]] [EE.G EA[A(2 ur Be)
Ts
Th
For Gr. we denote its un-orthonormmllize columns as {g' (a; B,,1)..... ........g'((e. g BB,b)}. Note that for any public candidate index i E [k), we have
① of (m5 Bl,)) Col(G.)
(ii E, [ = E, B,,)) de g. v((x=))]
(a)
2E. () Bl,,) o' 11 |1 vx(x)))
- 2 bb + +
where (a) holds due (a + b)2 < 2(x² (2) and (b) follows the 7-similar assumption. Therefore,
(a)
([= -. G.G.
E. (xx)) G.G. G.G. v==)))
(f(()) - -g(x:: B(,)
< 32
20

---

where (a) follows Jensen's 's inequality and (b) is due to the fact that - [x)) - æ for any x E Col(G,)
For T3, thus have
[V E,G,GG, Vfxx.) S E. -
2 +
(15)
For T1, we have
VF(G. E. (2x u, B.)
[[E) Gru.Gru Geu, - A(r un Gruell
Es [[(vv(a))TGu flae + (G(u))
- f(z+ 2Gru)) Grul
2A
V
E (f + AG - f(0, - -G -2V G(u)
2A
Vk
E, (1( + AGru) ((1))) - AV (V. G.u.) |]
21
Vk
Er [[((())) - 1(x - AGrw) - (V)(x)) T G.ue)
2X
LARE
2
where the last inequality is due to L-smoothness. Therefore,
( (V2603/1 + ++2)+ + LAK
S M N
(16)
For T2, note that
A
(f(x, + XGou; Bi) f(x, AG B₂) 22u,, +2N
412
(2) (f( + AGru;; - f(x+ (0x+- -XG 22u, V. (/G..))
2X2
(f(x + (f(=+ AG f(x;; B,) - A G, ff(
(f(x; - Au B,);
2u G, (();
X2
(0) 22
2 + 2 ((r()
where (a) and (b) are implied by (a b)2 < 2(a² + 12) and (c) uses the facts [f(x + Au) - (x)
Au f(() < d/2 and f(() f(z Au) - Xu vf(z) < LX2d/2 due to L-smoothness.
Therefore, applying Lemma B.2 (2) gives us
2²
[. un, 1
21 BE En, [n, G. ( B.))
1?
+ B. |||| G. V B)]
2
I?22R²
+ 2E By /V f(x B,) T ff(;;;
2.
2E By fzx; Proja ( fmy B))]
2
L2
+ 2E ( B
21

---

22
+2 (1V/(((2)))+++
7
(17)
2
Applying Ti 16
and 72 17 to Eq.
(1) yields
V 21 03
LAke
(nt - (n (f+)))] & f(x)) (e([(( + M
+ +
2
L L' 13
Lnkko b
Lnj
+ 4
202
We choose 17 2LE so that 1): -
Ln nt Denote Esr Eu B'c where Ust the set
{uo..... 1e-13 and similarly for 2c1, Bets and B'zr- Then we have
Bet [VflV|l
f(x++1)) -((x+1)+++MM 2M 22/22 (
0 +2))
LAK
2²
of
o²C²
4
26
Summing up from = to T 1 and dividing both sides by T yields
T
4LK
02
Eei [a]l\V/())))
T [f(0o) - [(x.)) + 2M
+
T
1,222
of
r²C²
LA M +
+
(18)
4
b
262
By privacy analysis in Section 3 we take o = c2by T (og(11/)/ (ne))))()))))))//))) (ne) and then there exist constants
er and 02 such that PAZO-P is (s, -iiffeerrntiill private for any < c/bTT/n2, O. We apply N and Eq. 18 and obtain the RHS of Eq. (18
-Lo - f(x.)] + 2M
0 &
+2
+ L
M +
L2X2R
+
of +
Og log
T
4
b
2n?
Choosing the optimal T agaaiin requires solving arg min 4 TT
vp/g. which yields
[Lk(J(ro) - s(x))]
T
C₂C
log(1/5)
By A(r u., (.) < 12
2(u, G. V[(x;;))) and per-sample M-Lipschitz, we have
M 4 - / 2kM < 1+ V2kM
due to choosing
< 1
We take C 1 + 2k: and thus the RHS of Eq.
18 becomes
LE
2(1 + c2 (2LA(f(Zo)) - f log + 2M
o +22 b
+ of
+
M
+
4k
b
which indicates that the error depends on k, σ1, 02, and y bb
(Voz 0
of b
O(k) +
+ + +
Therefore, we have d-independent error rate Okk), which is improvement due to k: being small constant & log d in practice. We additionally have the error term O(72 o2/b') from the biased public gradients and O(ai/b) /b) from the stochastic private gradients.
D
22

---

B.4
Convergence of PAZO-S
Theorem B.5 (Full statement of Theorem 4.3). Let the private and public data be --millar and 3 and 4 hold. For possibly non-convex J(C), running Algorithm for T rounds
Assumption 7
using a fixed step size y at. and c S 1/vd gives
Ecr E (L f(x+)) 2M (1+ t=0
02 VB
+
27
+
20 1
T
V
2
Additionally; ej and e2 the constants that make PAZO-S satisfy (e, -)differreetla privacy for any /n? 8 0. Then by taking T + oc, PAZO-S obtains the error rate O + o2//6).
Proof. Our public data sampling process is equivalent first sampling Bj and then dividing into & non-overlapping partitions. We choose the clipping threshold C large enough such that clipping does not happen, then the update rule is #++1 2z -ne (z₃; B ) 1=²)²²) where == arg min (f nng(;;; B;,;): B₂) + 2 is the index of public batch that yields the best public gradients and (=²) is an indicator variable denoting whether the proposal of adding z' ((0, Ia) is adopted.
At step let Fe be fixed parameter. We apply the update the property of L-smooth objectives and take expectation over all the randomness at this iteration, i.c., E, == B,,,,, We have
[x Exlf(xr (e (2; Bl,) - 1(2')20))
Laf E. Belll (ay; BB,r) + (=')='11²
s f(())) - ./ (v)())) R. (ax B(,)) ((2))=1)>
T
Liie Ti
f(x)) - T. (V)(x)) 12 Eg (2) B1) +
2
Laf Ti
f(x)) - /
(z)))) vf(xz)) - 18 (xre B1,))) +
2
Lafi
fx+) n: VVf
B. Vf o' (m: BB,
Tí.
Ta
For Tı, have
Eellg' (Ie: B,,)) 1(2)22' 2E.llls (mr (B 2de
I 2Ellll (m,; B[,,)
Rell (m:; B²,,) V/(x:)]]]+4]]][(<>>>> 2de
= 4Relllot - + F
Σ
- (11++//\)1 2de
jEB
Soz < 8- + 1f + / (xx)) + 2de
For T2, we note that for a sampled public batch [k]. its gradient is of (2x;; Bl,)) gi+ + < (1)' where C the stochastic gradient noise for the public sample in the i-th batch. We denote the selected best batch as and thus
1b g'(x; B(,))1 EB;
17 EB
1
23

---

By assumption, Eg; || |
- o for any batch Therefore,
EBg ||<5"7]]] E. EBG 11' (ppl]]
[1=i s So²z
Therefore, (E.l 9: g (dr:: B3,,) 11)2 B.lllr - (w B1 0 and
fell)f((,)) - o (z IIl & B.1l f.llV الله EE - و (or: B(,)
5
Denote E.ge = R Ber where 2ςt is the (=o: ..... 2-13 and similarly for Bet and B'ze- We have
02 de 72+
(n) 2T Bec ( ((s)))))-((()))-)))))) (
+4Tai
2
D +
4
We set e S. <1/Vd and choose Th t so that 2 - 11/22. We sum up from / = to T dividing both sides by yields
1, and
Ee E
8L ( s(x))) 2M (1+
02
20 1 + 27 +
T
V 2
We take 7 + oo and achieve a d-independent error bound 0(>² + o3/b'). When approaches zero, the remaining term o2/6 is due stochastic public data sampling.
B.5 Convergence of PAZO-M under Bounded Loss
Theorem B.6 (PAZO-M under Bounded Loss). Assume public and private data are 7-similar. Let and hold. Assume that (f(x)) I S for all t, then for possibly non-comvex f(-) and any Algorithm has the error rate
Assumption 7 2
a (1-adt d's dt (100000000)
T
4avd of (1-a)v7 b (1-a)Vd+a (1-a)3(tt((1-a)
of 2²v7
+0
4(1 4(1-a)+av3 (1
by choosing the parameters
4(1 - (1) " 8L(1
T= - (ne((1-avve + a)
2L
- (1)
12[4(1-04 + avd Vdlog(1/6)
2(v2 - 2(V2-1)C0
32v T.TTTms
X A
O² = =22 16M2 log
where
Ld
c2|4(1 - a) + +
$ 128 1281222111111 - a)
avva a + 8d(1 a) a) + +oval(( - -
+ adM(7 + M)[4(1-00 - +av2..
Proof. The update rule is xt+1 - 23 = (m - (A(riz ue, B.) + 21 21)u, + ag' (ax; B()) where
1 Σ
f(re + Auns E1) f(re deas Es)
Á un, B,) b
clipe
2X
E.B.,
24

---

When clipping is ineffective due to large C, we denote the non-clipped version as A(r; ue B₂). Since f(z; {) ssmoohhh we have
If(x++ f(æ, Amx < ue [((=s()))++ + -(=x)((())))--00- Au, (z(iit))
2A
21
[5 - A - ((resi)) (.sossii)
22
< S/u + LAVA
Therefore, by the per-sample Lipschitz assumption, we have
IP [[(zaa Xu
f(== Au;
LAVa
2X 2 Cu
PPu Vf(r(it) 2 Co)
CO
2V exp
8 (x)
C
2V exp
8M2
Denote Qr.i as the event that clipping happens for sample & iteration and Q the event that clipping happens for some & at some iteration t. Then, following Zhang et al. [8] we choose the clipping threshold C 2 Co + LAvd/2 2/2, /2, the probability of event Q is upper-bounded By the union bound, we have
S 2 exp (-
(- C8
P(Â) P
UUQ (=0 i=1
Qr.
(19)
8.22
At a step t, let xe be a fixed parameter. We apply the update to the property of L-smooth objectives and take expectation over all the randomness this iteration, i.c., E, = Eu.,,,,,, Note that the scalar noise is independent of ut, Å., and the event Qt, i.e., clipping does not happen for any & at iteration t. Conditioned on Qt. Á(z ue, B,) is equal to A A(x; ue, BB) and we have
L -0
(V(
(1 (L Vd
-f(x))(1-a)) Vzx)) T (x Qu
E, BI)
a Tnf
E. E.lllg (Blloo(( +f ( (x.
2
a-) 2)2 T. C2
(20)
202
For Ti, note that E. (ar; u) = W. (are ue B.)uz] and when A + 0, it holds that fx()) = E, [(z Eu, u (x:)) Ja fx())) for un Unif(d-gd-1), We thus have
Vf(xs) EE, (x1j B.)we
=>Vf(x;) TE,, A (1) )ue]
= |Ma
1 E.,, [A
+ +(1- 12) MVS(EII (21)
vd vf(x))
25

---

where T4 satisfies
1 Vf(az) Eu, (m
s E, ( (f(ls)) u f(xx + Aua) f(xe dese)
22
dt
E, [f(x + Aue) - f(x - Au)) - 22V (xiz) uw))
21
d'
Es [I (f(z; + Aue) - f(x)) fVf( uu) |]
2
d#
+
B, [f(((z)) - f(z== - Au) - (zz) u.) |]
2X
LAd
2
due to L-smoothness applied to the last inequality. Therefore, ", Bo)aol s
Ja [[ + LAM d
By the law of total expectation, have
Ex ue, Be)eel EsA(a (.) [1 un Be)
and thus
f((zs) B1 (2xs; ue Be Qcl
v((x)) E, A (xx;; ue, Be Beuuel
vf(x)) E,, | Ju (()(.)))))
IP(Q.)
I((..)
LAM da M2VaP(Q.) [ + 2I)(Q.)
S VdP(Qu)
I(Q2.)
For T2, note that per-sample L-smoothness implies batch L-smoothness. Therefore, we have
(xx Au;; B,) 2Au,
A A(Ieu,,B,)
412
(0) (f(x - B:) 2 B.) BB)
2X2
2 (f(x+ Au;;; (It; Au [.)x
22
(f) - f Au; uu VS +2( (.);
X²
(0) 12X²d
+2(u, (.);;
where (a) and (b) follow (a bb2 < 2(a² + b2) and (c) follows If Xu)
- f(x) Au Vf()) s
LX2d/2 and [x()) f(x Au) Au vf(x)) < LA2d/2 due to L-smoothness. Therefore,
(a) L2
[A(T; ue, B.
EB (1;; B.)
2
Vd
2d
20
< 2
|V +
(22)
byd
where (a) follows Lemma B.2 (2). By the law of total expectation,
E [11 ur B.)
E, (2x: u. (.) + |A ". (.))12.)1(())))
E, (zx u. (Q..
26

---

so we have
Er B Izi (Tx ue, B.)
E. ue 1c) <
P(Q+)
x222ad
2
[f(xa)] + 20
+ V)P(Q.)
21((2))
bvdP(Q.)
For T3, note that
Bu,,B, (Tre ue, B.) (2 [B] = vfA(z+)) Tt
2 (1lo611 + (=V\\( 11 vf((E))13)
so by the law of total expectation,
E, Aiz ue, B, o (zx; BJ) 1]]
E, (A we Be)u uel [q]] gh
E, Marei ue, u.) T gí
PP(2:) E, A un B.)US Q.] 9
P(Q+)
P(Q.)
E, [A u4 Ba) u.] T g/
P(()))
M MVvd(++MM
P(Q()
IPQ)))
P(Q.)
2P(Q.) (11o/11 [[Vfx(x))]] 1191 V[a(z=))1
M Mvd(y + M). P(Q.)
Additionally,
EB; 1llg (z: B) l|g'l12 + of
b'
vx(x)) ge (1osil) + |1 f2()))1
so we apply the above to Eq. 20 and have
Belf(re+1) 1(x
1
LAM
di + Mv
(1 a)m
V)P(Q))
2P(Q))
P(Q))
a) L Va L2X2d
[+ 209
2P()2))
2
Vd
bvd.
Ln?
amk
(Issll 2 + +1[ -
+
2P((2.)
8
2
a(1 - LT?
1
(11g,11
(x) - u1 V -
P(Qi)
2
(1 an)
C2
26²P(Q.))
which is
1 ((aN)))(())))))
LAM d + VVP((Q()
5(1-a) a))
+a +Q(1--))nnT(T(Q))
Vd
(1 - (3) L Vd
T,2Pd
2
2071
a²
(1 (1-a)² C
[f(x)))
+Ts
2
2
Vd
bvd
28'
21
27

---

where
a² Lnk ||1611
an:)(Q.) (x=)) 11%. -19g1 {s(+))113
T3
2
+ a(1
-a)
[l061] + +[VA(())) )| - 1l0% - V/((=a))
2
aLmi 2
1
P(Qi)
110/11 + Tn
11g [)(x))) amP(Q1)
[
2
Lm
2
2
+ a(1
Lnk
[IVf((=))] -191 - -VA((=)))
2
If we have C/ 2 8M log( (2))) then P(Q.)- P (U'-. Qni) S 222xbexp
c
S 2
8M
and thus P(Q() = P())) 2 2' We choose T) and a such that Lnja I 2/2 which implies that 1 :(Q:)
Em < 1 Then we have
T3 v a(1 a) LT
||o%0| + [ - 1196 - V(((=)))
+ amnn
[V)(2))
2
2 4
=a(1 - a) Ln vf2(2)))
[xx))
2
4
Sa(1 a) AMl [2+)) + am
[V{(2:)]1
Sa(1 - Lnk (1lg - Vf [+)))))
1
V)(.a)
+ Vā [V
Vd
am
+ 2 4
\f(x))|1
Ltd
<a( - Lnk (7 + [x(+)]))
+ Vd
[
+
V fxx))
2
2
4
< - Ln?
LL
+
+
LAd
M +
[
07
aTi
[
2
Vd
2
vd
2
4
Additionally, by the assumption that [f(xz)] S for all t, we have
[x) - 100-ff((+4-- ((===1)Q)))((0.)
-
[x[((x)) - 1
$ [{[(())) - [(==+))1))(((+++55577)
We additionally apply P(Q.) v P()) and obtain
T1 - a)
Vd 4 - LI² - a)2 unfa(L-a) aa) a [V({2))
a
Vd
(x. f( + (1 - al) (1 - a) Ln!oo?
(1 (1- 11=
(1- T
+ ami7?
212
2
a² LnLoo
a(1 - a(1-a)L² 1H 7x
Vd + Ltd
+ aa1 an) M
28'
2
2
+ (1 a)n, M ViTP(Q) + a(1 a) M V + M)T((Q) + 2STP(
Choosing Tt [1(1o)((1o))yaoo))
have aTm 1/ for any a (0, (0, 3). Denote Egt BucedesnBess B', where Uus is the set (uo...., 1 and similarly for zet, Bet. and B' By
4(1-a)tavd
28

---

privacy analysis in Section 3 we take o / (1//)/ (n=) and then there exist constants Ci and 02 such that PAZO-M is (a, 6) -iffferrrntiill private for any e < cjb2T/n², 8 > O. We apply nh and o, sum up from 0 to T and divide both sides by I to obtain
Bedl [S(+))] T
64v (avaLif(oo--flee
(L-a))(ta(())))) LAd
4(1-a)
M
T
(4(1-a)+aVdf
4(1 4(1-a)+avd
4ova
T222d2
ofPa dc3)og(1/0)C*T
1-a
ty²
+
4(1 ((1-a)+avB
4
2n?g²
(1-a)v+ta
do3
a²
LAdin
LAd
a
7+
M
2//
(1 (1-o)3/dta(1-0)
2
2
(1-a)Vd+a
128 1200
8d(1-a)M2
cdM()+M)
CB 8M2
+
2v 2TbTexp
(a(1-a)+aVd)
4(1-a)+avd (L-a)vd+a
A < - (10 and = V2Cg, then C' 2 Co + LAv holds. So we choose
X 2(v2 - 1))oo
Co
<
and =²=20h²
Ld
Ld
Additionally, let
T 8nc((1-a)
2L +aV Vdlog(1/6)
32v 32VLTbeES (V//)-a))///VVaalgl))
LitnES
-8
where
$ = 128 a) af2 8d(1 a) a) a) -ava|(1-a)\aa+
+ +adM(7+ -))
This yields
T-1
T 1=0
402(1 addi / 21 log
4(1 a)va
-f 0 MC
nE(4(1 a) + avd
4(1 - a) aad
4avd
C of (1 (1-00 a)va
of
adVd
2
+
4(1 a) +avd
b (1 a-aa 25 01-1 a1=))
70 ( Vd
Co
avd
M
[og(1/8)d
(1 (1-aoVito
with C and Cf defined as above. Since C² 208 0 (log (I-a)'dtad 0 (log (-a))² the error depends on d, σ1, 02 and by
a(l-o)v(tood)
(1-aaat) dtt +0 +0(1² "2 4avd a
of (1-o)vd of ad
4(1 ((1-a)+aV)
(1-a)Vd+a (1-
Therefore, we have error dependence O(L=ad)) d!), which saves a factor of d log d compared to DPZero's OVV d), together with constant improvement if > 1. We additionally have the error term 0(7² + aō/6') that reduces as decreases due to using biased public gradients.
a
D
29

---

B.6 Convergence of PAZO-P under Bounded Loss
Theorem B.7 (PAZO-P under Bounded Loss). Let the private and public data be 7-similar and
Assumption 7 3 and $ hold. Assume that (f(x))) S S for all I, then for possibly non-convex
Algorithm has the error rate
O(Vklogk)+ (v
7 + of D
by choosing the parameters
T 4nE
2Lk
A 2(V2 1)Co
1/t 4TK.
log(1/0)
Lk3/2
and
128 Skbnn?
C² 20 16M² log
G log(116)
The update rule is 21+1 and
Proof.
2t -mo(A(ai ue B,) + G( where us (nif(vkk*-1)
f( + AGrutiE) f(re AGruniE))
A the B₂) = Σ clipe
S.EB.
When clipping is ineffective due large C, we denote the non-clipped version as A(r;; ut, B₃). We abbreviate A (1x;; ue Bi) as A and Å (Ix ut, B,) as Å. Since f(x; {) is L-smooth, we have
[f + AGruriE)
f(a, &.r
21
$ 1/ Gi &.)+ [f + AG (1xt:))) - Au., (f(A))))
2X
+ |f(xr (GrrriE) - f(xrits) + Xu, G. (f(rriE))
2X
LAk
$ S/u G, (() +
2
Therefore, by the per-sample Lipschitz assumption, we have
PP [f AGruiiE))
f(x AGrun:Ei) 2 Co
LAk
<Plu, (
2x
CB
<2 22Vxpp
Cj
2Texp
8M2
due to ||G, (I( || < [V 32 M Denote Qt, as the event that clipping happens for sample & iteration I, and Q as the event that clipping happens for some at some iteration I. Then if we choose the clipping threshold 2 Co + LAk/2, 2, the probability of event Q is bounded. By the union bound, we have
(-C C3
P(2) =P
UUQ mmll
22 exp
(23)
8.M²
At a step f, let at be fixed parameter. We apply the update to the property of L-smooth objectives and take expectation over all the randomness this iteration, ie.. E, == Eu,,,, Note that the
scalar noise is independent of Ge, U4, Å. and the event Qt, i.c. clipping does not happen for any
30

---

at iteration t. Conditioned on Q₁, As is equal to A and we have
{((x) + [,411 + _ - 1Qc)
-
f((z)) V B + Lnk E,
Lin E, G1a [2]]
|1A.Grue Q1)
2
@ f(x)) - Th V + nh (Vf(z)) (((())) - E. (elllGuulleil)
T1
Laf k
Cnp
| 2
Qi
(24)
21
T2
where (a) is due to the orthonormality of G. and thus ||Gau]] For TT, we proceed by
||ue|| vk.
fV())) fx() E, (.,l
[Vf(2))] - G.A
[V]((z)] [ V + -
[V](2z]] V E,G.G, fz,)))] (.G.GTTT(()) - A.G
+ VfG.G]
T4
For Gt, we denote its mn-orthonormalized columns as (x) B,,).... (z) Bl,,). Note that for any public candidate index i E [k), we have
(i (0 Bl,,) Col(G,)
(ii E, ( Bl.,)
= B(,,) - g. g. vf(=:)]]
(a)
2E, [ By,,) s.ll l1g vf(x))
< 2(02 /b' +
where (a) holds due to (a + b)2 < 2(a² + (2) and (b) follows the 7-similar assumption. Therefore,
Vf (4)
E,
E, Vf(x.) - - V..
Vf(x.) - g(zri B(,,)
2 +,?),
where (a) follows Jensen's inequality and (b) is due the fact that V
[V - æ]| for any x E Col(G.). We thus have
T, < E Vf(x)) - vf(x)) v 2(02/b +
(25)
For T4. by the law of total expectation, it holds for any random variable A 2 0 that
E,[4] = EA E (. 2 [AIQ..
31

---

Therefore.
- Vf(G,, - A B
Guul
s Be [l| ([(()) Gru-
Mes + (G(u)) - f(x - \Gru))
Grutt
Qt
2X
[[( (VF[(a)) Grue f(z + \Grue) - -f(xe - \Gru))
- P(Q+)
Gau
21
V
Er [f((x) + (GGuu) - f(x;= - -G - 2XV G,u)) I
21P(Q1)
Vk
< 2)P((1))
E. [1(rt + AGrua) (1()) (VI(aa) []
Vk
E. (f(x)) - f(se - -AG(u) - AV G.u)) |
2XP(Q.)
LAKE
2F(Q.) where the last inequality is due to L-smoothness. Therefore.
Ti S M (2103/18+ 100///0+)2)1 + 2P().)
LAke
(26)
For T2, note that
A (f(x, + ((an
4X2
(a) (f(x; + (Gru;:B) - AGru;: -(x;- 2Au, G. (.) G, V.../ol V.(a,;;; B.))²
21²
2 +,G,u; fIz;; B,) Au,7 G,
X2
(f(rr:B)) BaaBBB)-(ii 1G14; BB) du, VI,TV(( + +2(,, G, B();
+
22
(e) 22
2 +2 G. (.)s,
where (a) and (b) are implied by (a + b)2 < 2( + b²) and (c) uses the facts f(x + AGu)
((x) Au G (()( < TX2k/2 and [sxx) f(x AGu) Au TG (z)() < T22k/22 due to
L-smoothness. Therefore, applying Lemma B.2 (2) gives us
L² E2 [ <
+ B. Ey,, [1u G. Vf(a, B,))
2
1²X2
+ B. Ill G. f(zz B
2
1?X21?
+ +2EB,,
[e [z B,) G.G. (xx;; B:)l
2
1!X222
+ B.
[f B,) Projo ( fz(;
2
1,2X212
<
+ 2E
V / BB)1
2
L²X2R2
+2 [IV[(x))) + )
By the law of total expectation, we have
A
2
1222112
2
(IV
+ of -1)
E, [A S
<
(27)
P(Q:)
2T((Q.)
P(Q.)
32

---

If we have C 2 8M2 (og(4 then P(Q)) - 2v2mb exp
CR
S and thus P(Q2)
8M
1 1 P(P))) 2 Therefore, applying T1 26 and T2 (27 to Eq.
(4 yields
[e(5(Z++1)QO)) & f(z)) - n
LiN
LnA C²
V [f(x))]
+ mill +
T2
21)(Q()
2
P(2)(Q.)
S f(+)
U
[++()))
T.M
(V2003/1 + + +
L.kE
(Q)
P(Q.)
2
L P(Q+)
22
of
LnkoP
4 + +[V])())
+
(28)
2 212P((Q:)
Additionally, by the assumption that [f(x))] - for t, we have
E. [x(())) - [(===1)Q.)P((..)
[x( -
[x()( - B.j ( s (x)) - (
and thus
(hh Link) [Vf(())) < (z))(z)) f(=+1)11)P(() + M (12
a
+22)
LAki
+
2
L \
Lni 2
+ 262 + 2ST((Q).
4
b
We choose 7/ IPK that Th Lon 4. Denote Ect = Bec where uher is
the set {wo, ..., u } and similarly for 2ct, Bei. and B' By privacy analysis in Section 3 take a /Tb/Tlog (og(1/8)/
and then there exist constants ei and c2 such that PAZO-M (e, 83 differenniiay private for any c/b2T/n2
O. We apply ne 0, and Eq. (23 sum up from t = T - 1, telescope terms, and divide both sides by T to obtain
202 22k (og(0))
o
(s(xo) f(x.) + C2 4M 2
+
72
T
b
b
L2
512SLkbns
TLk log(1/8) exp
C2
2LAR M
4
C2
8.M2
by choosing T
[og[1/8]
27.
If choose A < 2(v2-1)CB and C² 20 then C 2 Co +
Lb
LAA
2
satisfied. Then we choose C² 203 16M1 log
128 of log(1/6)
and have
202v 2Lklog(1/6)
2T +1
E [[]))()))))
((80)-((r)+166M))
nE
c5log(188)
+ 0f
+2LAA M+ 2²
+4M
+7²
202 2 1/8)
128 128
f - +666
+1
nE
cg0g((18)
+ of
CØ
+4M 2
02
+22
2M
b
4h:
by choosing X 2(vI-1)Co
Co 2b
This indicates that the error depends on k. d1, 0z and by
O OlVBlogk) +0 (v
of
+
33

---

with parameters
4nE
2Lk
A 2(v2 -1)Co
? 4LK*
log(1/8)
Lk
and
128 2 E (og{
C² 20 16M log
Therefore, we have d-independent error rate log which improves DPZero's O(vdlog d) due to k being small constant < d in practice. We additionally have the error term 0 + / from the biased public gradients and (aa from the stochastic private gradients.
C Experiment Details
C.1 Datasets
The four pairs of datasets and models closely follow the experiments in the existing DP literature. We provide the details of public data generation as follows.
CIFAR-10. We follow previous work [41] that uses 4% of the training samples public data and warm-start on the public data by training on it for a small number of epochs. Additionally, we create class imbalances among the 10 classes for public data. We treat this imbalance mild distribution shift from the private data. To avoid information leakage from the batchnorm layer, we start from a randomly initialized NEResNet18 433
We follow Kurakin et al. which first pre-trains a ResNet18 on Places365 45
and then fine-tunes the model on Tiny-ImageNet with differential privacy. We randomly sample 4% of the Tiny- EmngeemeeNet training samples as public data, which thus comprises 20 samples per class. We small VIT model (10M) [46] with random initialization.
477 samples as disti--iistiiuution (OOD) public data to guide the private learning on IMDB. We build the vocabulary based on the top 10K tokens in the IMDB training set and construct the Amazon Polarity public dataset with size 4% of the IMDB training size, which gives us 2,000 public samples.
IMDB. We follow Li et al. [6], which uses Amazon Polarity
MNLI We follow the few-shot setting in the past work 6 and sample 512 MNLI training examples per class. We adopt the same prompt template and start from pre-trained RoBERTa-bas model. We randomly sample 100 training examples per class from SNLI 48 as the OOD public data.
C.2 Experiment Results
We present detailed results on four datasets Table 2 privacy budgets (e, 8 1/ #trin samples) and the non-private performance, which corresponds to accuracies of SGD and MeZO. All results are obtained under the same random seed Entries with '_' indicate failure converge. The best accuracies are in bold and the second places underlined.
We report the performance under multiple
Implementation details. For each first-order methods with public data, we vectorize the per-sample gradient computation and privatization using vmap. For the method with open-sourced code (GEP [4)), we adopt their provided implementation and privacy accounting.
The experiment on MNLI utilizes the codebase from Malladi et al. [6). including their dataset processing and prompt tuning workflow. Following MeZO and DPZero, we sample the zeroth-orde order direction u4 from Gaussian distribution (0, Ia) in the experiments. since prior work verifies that it produces very similar performance [8] to sampling from V Similar to the first-order methods, we apply vmap for speedup by vectoring the q forward calls. However, given that PAZO needs smaller q's than the vanilla zeroth-order methods, do not need to employ this memory- memory-inefficient implementation in most settings.
PAZO-P vs. PAZO-P'. Table 2 shows the performance of PAZO-P with orthonormalized public gradients (row 'PAZO-P') and with normalized public gradients (row 'PAZO-P"). PAZO-P and PAZO-P' have similar performance, with the deviation being 0.1% 2.5%.
34

---

Table Training NFResNet18 on CIFAR- 10 from scratch.
Type
Method
0.1
0.5
=
==
Non-privare
FO
DP-SGD
46.7
49.7
50.8
54.2
54.5
86.3
DPMD
64.3
66.6
67.8
68.5
69.8
FO+PUB
DOPE-SGD
64.8
69.3
70.9
73.0
72.9
GEP
49.9
50.7
52.9
53.8
ZO
DPZero
47.0
48.1
48.2
48.2
48.1
49.0
PAZO-M
70.9
71.3
71.3
71.2
70.5
ZO+PUB
PAZO-P
69.5
69.6
69.0
68.7
68.1
(ours)
PAZO-P'
69.6
69.2
69.2
68.9
68.0
PAZO-S
70.3
70.3
70.2
69.8
69.7
Table Fine- tine-tuning Places365 pre-trained ViT-small on Imny-ImageNet.
Type
Method
0.1
0.5
1
2
Non-private
FO
DP-SGD
24.8
29.2
31.4
38.0
52.9
DPMD
30.5
31.4
34.2
35,5
FO+PUB
DOPE-SGD
30.7
31.8
32.5
34.4
GEP
30.9
30.5
31.4
ZO
DPZero
25.1
27.6
27.5
27.9
28.6
PAZO-M
30.8
30.8
30.7
30,8
ZO+PUB
PAZO-P
30.9
31.0
31.0
31.2
(ours)
PAZO-P'
30.7
30.8
30.8
30.9
PAZO-S
30.6
30.6
30.6
30.7
Table 4: Training LSTM on IMDB from scratch.
Type
Method
0.1
0.5
1
= 3
Non-private
FO
DP-SGD
50.0
66.4
69.9
73.5
75.5
89.5
DPMD
71.0
72.1
73.4
76.6
76.6
FO+PUB
DOPE-SGD
70.2
73.2
75.0
75.9
77.9
GEP
60.0
71.0
74.0
77.2
78.6
ZO
DPZero
59.0
62.4
62.6
63.2
63.8
63.8
PAZO-M
73.4
73.2
74.5
73.2
73.6
ZO+PUB (ours)
PAZO-P
71.0
73.7
73.2
73.0
72.7
PAZO-P'
69.4
69.8
70.7
70.0
70.5
PAZO-S
74.6
74.2
73.8
73.9
74.2
Table 5: Prompt-tuning RoBERTa-base on MNLI.
Type
Method
6 0.1
0.5
3
Non-private
FO
DP-SGD
52.6
59.3
63.5
68.4
72.0
78.9
DPMD
56.5
67.0
68.1
71.5
72.8
FO+PUB
DOPE-SGD
59.7
67.2
68.0
70.1
72.5
GEP
ZO
DPZero
55.2
58.2
60.4
62.6
68.4
PAZO-M
67.1
67.3
67.8
67.7
67.5
ZO+PUB
PAZO-P
63.5
68.3
69.8
69.7
70.3
(ours)
PAZO-P'
61.0
68.1
68.8
69.0
69.4
PAZO-S
68.2
68.6
68.9
68.6
69.0
35

---

Performance of public only. We demonstrate that the improvements of using public data are not due to overfitting to public data. We train on public data alone using SGD with batch size, learning rate, and weight-decay tuned, and the optimal hyperparameter for each setting gives accuracies equal to 66. 1% for CIFAR-10. 10, 27.1% 1 % for Tiny- 68.4% for IMDB, and 60.8% for MNL.. We denote these results as 'public only' and pick the best first-order with public data (FO+PUB) and zeroth-order with public data (PAZO) algorithm for each dataset. In Table we present the performance gain when private data is included (i.e., 'F+PPBB/PAZ minus 'public only" across E = 0.1, 0.5, 1, 2, 3). Note that 'public only' accuracies come with severe overfitting due to the small number of public samples, while the DP accuracies are not overfit.
Table 6: Performance of training with public data only and the improvements from using private data via first-order (FO+PUB) and zeroth-order (PAZO) methods. We observe that (1) FO enjoys up to 12.0% performance gain and ZO enjoys up to 8.2% when private data is included: (2) ZO consistently enjoys performance gain when private data is included, while FO does not, since private first-order gradients can be too noisy under tight privacy.
CIFAR-I0
Iny-ImageNet
IMDB
MNLI
Public only
66.1
27.1 3.6 ~ 8.4
68.4
60.8
FO+PUB improvement
-1.3 ~ 6.8
2.6 ~ 10.2
-1.1 ~ 12.0
PAZO improvement
4.4 5.2
3,8 ~ 4.1
5.3 ~ 6.2
7.4 ~ 9.5
Performance under various % We demonstrate that PAZO performs better when public data is closer to the private data in two settings: pre-training on CIFAR-10 10 and fine-tuning with prompts on MNLI. To create public data of different extents of distribution shifts (different y's), we mix ID public data and OOD public data with different proportions. For CIFAR-10 10, we use non-overlapped training samples with small class imbalance as ID public data and those with big class imbalance as OOD public data. The slight class imbalance has class-size ratios [1 :...: 0.85) and big class imbalance has class-size ratios [1.0 0.9 0.8 :...: 0.2 0.1]. For MNLI, we use non-overlapped MNLI training samples as ID public data and SNLI training samples as OOD public data. We present the performance and 7 of PAZO under these scenarios T We observe that (1) the range y is method--deenndnt and (2) for any fixed PAZO variant, the accuracy increases as the data become more similar (smaller
Table 7: Performance under different public data with y under privacy & 1.0. We observe that though the range of 7-similarity depends on specific methods, the values are consistently bounded and small. For a fixed PAZO variant, as the public data becomes more in-distribution, performance improves and y decreases (i.e., gradients for public and private data become more similar).
Private Data
Public Data
PAZO-M
PAZO-P
PAZO-S
Slight imbalance
71.3 (7 4.3)
69.0 (r = 3.4)
70.2 = 1.6)
CIFAR-10
Half-half
69.9 (7 4.8)
67.3 (7 = 4.1)
67.3 = 1.8)
Big imbalance
66.7 (7 6.2)
63.8 (7 = 4.8)
63.0 (7 = 221)
MNLI only
75.7 (7 39)
74.1 (7 41)
74.0 (? 49)
MNLI
Half-half
73.2 (7 = 50)
73.8 (7 = 43)
73.1 (7 67)
SNLI only
67.8 (7 = 71)
69.8 (7 65)
68.9 (7 81)
Runetime efficiency. Theoretically, we list the number of different types of operations involved in each algorithm in Table 9 Since the first-order methods require per-sample gradient computation and clipping, the number of "ggradient backward", the slowest operation, is dependent on the private batch size. This is discouraging feature since large batch sizes offer better utility/privacy tradeoff's
14 42), creating an additional tradeoff between utility and efficiency. In contrast, the number of gradient backward steps is either 1 or k(k < b) in zeroth-order methods. Together with the fact that the forward calls are more memory-effiieent than the backward ones when vectorized, zeroth- methods are principally more scalable.
Empirically, we evaluate the runtime each training iteration in all settings (Table We vectorize the three settings other than the IMDB-LSTM experiment due to incompatibility between the model
36

---

architecture and vmap. Although the MNLI experiments enjoys only 2 of speedup by using PAZO, Malladi al. [6] show that zeroth-order methods will be significantly faster as the model scales up.
Table 8: Speed of each method on different datasets (in s/iter). It shows that PAZO offers up to 16x runtime speedup per training iteration compared to the baselines. All numbers averaged over 20 iterations. Note that we report the speed of each method under optimal (k, D' q). DPZero is occasionally slower than PAZO because we try y {1, 5) for each method and observe that DPZero needs = 5 while PAZO can take g = to achieve competitive accuracies.
CIFAR-10 Tiny-ImageNet
IMDB
MNLI
DP-SGD
0,420
0.366
0.173
1.697
DPMD
0.462
0.404
0.183
1.761
DOPE-SGD
0.424
0.365
0.172
2.187
GEP
0.830
0.548
0.252
DPZero
0.081
0.132
0.016
1.934
PAZO-M
0,051
0,073
0,019
0,852
PAZO-P
0.149
0.168
0.042
1.244
PAZO-S
0.102
0.142
0.019
1.118
Speedup
16x
7x
15x
2x
Memory efficiency. Table 9 presents the number of different operations needed per iteration of each method, showing that PAZO-(M,P,S has memory overhead to store public gradients compared to DPZero. PAZO-M requires one batch of public gradient, the memory overhead is (d), where is the number of model parameters. PAZO-S also O(d) since we can compute the & public batch gradients sequentially. Though PAZO-P has ((kd) memory overhead than DPZero, it is still more memory- and computation-effict
than the first-order DP methods since the latter generally requires (bb)) memory to maintain per-sample gradients. Our experimental results are obtained using k = {3. 6} while = 64. Such entangled dependence on and d is also restrictive since larger batch sizes improve performance
49
Table 9: Number of different operations per iteration of each method.
# Private forward
# Public for+backward
# Private backward
DP-SGD
b
b
DPMD
b
b
DOPE-SGD
b
1
b
GEP
b
R'
b
DPZero
24
PAZO-M
24
PAZO-P
24
k
PAZO-S
k
k
C33
Hyperparameter Tuning
This section presents our hyperparameter search grid and the results of our methods under different hyperparameter values.
Hyperparameter selection. For all the first-order methods and PAZO, we set the number of epochs 100. Since the vanilla zeroth-order methods benefit from training for more iterations [8] 6 we try training for 100, 200, and 300 epochs with their corresponding correct noise multiplier applied. Due to increased noise added when more epochs are allowed, we observe that the epoch number of 200 produces the best performance across settings. We thus train for 200 epochs in all DPZero experiments. The values of the smoothing parameter are presented in Table TO We also report the hyperparameter search grid for each method in Table 12
13 where the batch size b is only tuned for
37

---

non crii-rivate methods (SGD and MeZO); We fix the private batch size to 64 for all private methods, including zeroth-order and first-order, with and without public data.
Table 10: Values of the smoothing parameter in each experiment.
CIFAR-10
Tmag-mmageNet
IMDB
MNLI
MeZO
10-2
10-2
10-2
10 3
DPZero
10-2
10-2
10-2
10 3
PAZO-M
10
10
10
10-3
PAZO-P
10
10-2
10
10-2
Sensitivity to g. Table shows that the performance of the vanilla private zeroth-order method relies setting q > 1. which slows down the training and harms utility due to increased noise added for privatization. In contrast, PAZO is less dependent on increased due to the assistance from public data. This implies that PAZO has approximately the same workload of hyperparameter tuning as DPZero: Under a reasonable or intuitive choice of the hyperparameters for public data sampling, one only needs find good combination of clipping norm C' and learning rate f).
Table Performance vs. q in different settings. each cell, the first row represents the accuracy under 1 and the second represents that under g = 5. We observe that DPZero benefits from increased q in accuracies by 1.0%, 2.4%, 4.8%, and 7.2% on four datasets. contrast, PAZO has stable performance under different q.
CIFAR-10 Imag-
IMDB
MNLI
47.1
25.5
59,0
55.4
DPZero
48.1
27.9
63.8
62.6
70.1
30.8
72.9
67.5
PAZO-M
70.3
30.8
73.6
68.3
68.1
31.2
72.7
68.6
PAZO-P
68.6
31.0
72.7
70.9
Sensitivity to introduced hyperparameters. Apart from Figure 6 we also present the hyperparam- eter sensitivity study the other datasets Tiny-Imagell ImageNet and IMDB in Figure 8 The conclusion the same as in the main text: PAZO is not sensitive to the values of the introduced hyperparameters.
Influence of in PAZO-S. Figure and Figure show that the performance of PAZO-S is robust to different 6 values. Since having no noisy candidate is equivalent to setting c = 0. we compare the best performance of having noisy candidate (purple cells) with none (blue cells). The conclusion is consistent: Having * 0 offers the opportunity to improve performance general, but it does not harm significantly to leave it less tuned.
38

---

Tiny-InageNed
IMDB
0.25
0.5
0.75
0.25
0.5
0.75
30.7
30.6
30.8
73.0
73.6
73.2
32
30.7 30.7
30.7
32
73.5
73.4
73.3
10
6
10
30.5
32
70.7
64
72.5
32
31.2
31.0
30.9
128
71.4
71.5
72.7
1e-3
30.7
30.6
30.7
1e:2
12.0
72.1
71.4
PAZO-S
1ee4
30.6
30.6
30.7
1e:3
74.2
73.2
72.8
30.7
30.6
30.7
73.6
74.5
71.8
Figure 8: All PAZO methods are robust to different values of their introduced hyperparameters. Each number represents the best accuracy with standard hyperparameters for zeroth-order private methods (C and 17) tuned. Blue cells indicate PAZO-S performance without having a noisy candidate.
Table 12: The hyperparameter search grid for CIFAR-10 and Enn-lImaeNet.
Algorithm
CIFAR-I0
Tiny- Imageem
[0.01, 0.02, 0.05, 0.2, 0.5)
(0.001, 0.005, 0.01, 0.05, 0.1) (64)
SGD
b
(8, 32, 64)
[0.01, 0.02, 0.05, 0.1, 0.2)
(0.01, 0.02, 0.05, 0.1, 0.2, 0.5, 1.0. 2.0) (0.01, 0.1, 0.5, 2.0]
DP-SGD
C
[0.1, 0.5, 1.0, 2.0]
?
[0.01, 0.02, 0.05, 0.1,
(0.001, 0.005, 0.01, 0.02, 0.05, 0.1,
DOPE-SGD
(8, 32, 128)
(8, 32, 128)
(0.1, 0.5, 1.0, 2.0J
(0.1, 0.5, 1.0, 4.0)
[0.02, 0.05, 0.1, 0.2, 0.5)
(0.005, 0.01, 0.02, 0.05, 0.1,
DPMD
6'
[8, 32, 128)
(8, 32, 128
C
(0.1. 0.5. 2.0)
(0.01, 0.1. 0.5. 1.0)
1
(0.005, 0.01, 0.02, 0.05, 0.1, 0.2.
(0.01, 0.02, 0.05, 0.1, 0.2, 0.5]
GEP
(8, 32, 128)
(8. 32, 128)
C1
(0.1, 0.5. 2.0)
(0.1, 1.0, 1.0,
[0.001, 0.002, 0.005, 0.01, 0.02, 0.05, 0.1)
(1e-4, 2e-4, 5e-4, le-3, 2c-3) (64)
MeZO
b
[64)
[0.01, 0.02, 0.05, 0.1, 0.2, 0.5, 1.0) [1.0)
(le-4, 2c-4, 5e-4, 1o-3, 20-3) (1.0)
DPZem
(0.1, 0,2. 0.5) [8, 32)
(1c-5, 2c-5, 5e-5, 1e-4, 2c-4, Sc-4) [8.
PAZO-M
[0.25, 0.5, 0.75) (1.0)
(0.25, 0.5, (1.0)
[0.2, 0.5, 1.0, 2.0)
(0.2, 0.5, 1.0, 1.5, 2.0)
(8, 16,
(8, 16, 32)
PAZO-P
63, 6, 10)
(3, 6, 10)
C
(0.5, 1.0, 2.0J
(0.5, 1.0, 2.0}
"
(0.01, 0.02, 0.05, 0.1. 0.2)
(0.001, 0.005, 0.01. 0.02, 0.05, 0.1, 0.2,
(8, 16, 32)
(8. 32, 128) [3) (0.001. 0.0001)
PAZO-S
(3)
[0.01, 0.001]
(0.5. 1.0. 2.0. 2.0. 4.0)
(0.5, 1.0, 2.0, 4.0)
39

---

Table 13: The hyperparameter search grid for IMDB and MNLI
Algorithm
IMDB
MNLI
[0.1, 0.2. 0.5, 1.0. 1.5) (64)
[1e-6, 1e-5, le-4. 1e:3, Se-3, 1e-2)
SGD
[8. 32, 64)
[0.01, 0.02, 0,05, 0.1, 0.2, 0.1)
[2e-6, Se-6, le-5, Se-5, le-4) [10. 20. 50, 100, 150, 200, 250)
DP-SGD
C
[0.1, 0.5, 1.0, 2.0.
[0.005, 0.01, 0.02, 0.05, 0.1)
{5e-6, le-5, 2e-5, 5e-5, le-4) [8. 32]
DOPE-SGD
[8, 32, 128)
C
[0.1, 0.5, 1.0, 2.0,,
[10, 20, 50, 100, 150, 200, 250)
(0.005, 0.01, 0.02, 0.05, 0.1)
[2e-6, 5e-6, 1e-5, 2e-5, 5e-5, le-4, 2e-4) [8, 32]
DPMD
(8, 32, 128)
(0.1, 0.5. 2.0, 4.0)
[10, 20. 50, 100, 150, 200, 250)
[0.01, 0.02, 0.05, 0.1)
[2e-6, Se-6, le-5, 2e-5, 5e-5, le-4, 2e-4) [8, 32)
GEP
(8, 32)
C1
(0.1, 0.5, 1.0, 2.0
{10, 20, 50, 100, 150, 200, 250]
McZO
7
[0.002, 0.005, 0.01, 0.02, 0.05, 0.1)
[1e-7, 1c-6, 26-6. 5e-6, 1e-5, lc-4) (64)
(64)
[0.002, 0.005, 0.01, 0.02. 0.05, 0.1)
[1e-6, 2e-6. Se-6, le-5, 2e-5. 5e-5) [10. 20. 50, 100, 150, 200, 250)
DPZero
(0.1. 0.5. 2.0)
1
[1.0, 1.5, 2.0, 3.0, 4.0)
[le-4, 2e-4, Se.4, 1e-3, 2e-3) 38.
[8. 32)
PAZO-M
(0.25, 0.5,0.75)
(0.25, 0.5, 0.75)
(0.1, 0.5, 2.0, 4.0)
{10, 20, 100, 150, 200, 250)
(0.1, 0,2, 0.5, 1.0, 2.0)
[5c-5, Ic-4, 2c-4, 5c-4, 1c-3, 2c-3)
[32, 64, 128)
[8, 16, 32)
PAZO-P
[3. 6, 10)
[3, 6, 10)
C
[0.5, 1.0, 2.0,
110, 20, 50, 100, 150, 200, 250]
[0.1, O.2. O.S, 1.0, 1.5, 3.. 4.0)
[1c4, 2c-4, 5c-4 1o-3, 2c-3, 5c-3) [8, (2)
V
[8, 32, 128)
PAZO-S
[3]
[3]
10.01,
0.001)
C
(.51 1.0)
0.5. 1.0)
40

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We summarize the contributions in the abstract and introduction, with our proposed algorithm described in Section 3 theoretical analyses made in Section and
experiments detailed in Section 5
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations in Section
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 a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-specfiiatiinn 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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails 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 faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to 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?
41

---

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

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
Datasets are publicly accessible and code released on GitHub.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.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 NeurlPS code and data submission guidelines (https for more details.
/tips.cccpubllc/gu..doo
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 as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We describe the algorithm details in Section 3 experimental setup in Section 5 the full experiment results in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, 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: The paper does not report error bars in experimental evaluation. However, all the experiments use the random seed 0, so the results are not biased. Importantly, we report the results under multiple hyperparameters in Section (aaiion/Saand and Appendix C.3 Results show that the performance of our methods consistent across different hyperparameter values, which illustrates the statistical significance of the experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
43

---

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).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
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 not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог 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 or tables text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We discuss the compute type we use and the runtime of both our methods and the baselines Section 5 and Appendix C.2
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics p http:///wwrpppccopp..i.c/cccccaa
Answer: [Yes]
Justification: We have reviewed Code and Ethies, and confirm that submission conforms with it.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., s if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We discuss the broader social impacts in abstract and Section !
Guidelines:
The answer NA means that there is no societal impact of the work performed.
44

---

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 generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there 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 system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
We have properly cited the data and models we use in the paper.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URI.
The name of the license (e.g., CC-BY 4.0) should be 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.
45

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
batasets.papersstt
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is available online, the authors encouraged to reach out the asset's s creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We use open-sourced data and models in work and they properly
referred.
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This 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 contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending 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.
46

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere 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
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: This paper uses LLM only for grammar editing and formatting improvement, declaration is not made.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM for what should or should not be described.
47


Reviews:
[{"review_id": "2dnG3cKn7m", "reviewer": "Reviewer_bY4V", "summary": "In this paper, the authors proposed combining public first-order gradients with private zeroth-order gradients for differentially private training.  The paper proposes three ways of mixing the gradients: 1. naive weighted averaging; 2. projecting ZO direction to FO gradient subspace; 3.   using zeroth-order evaluation to determine the optimal public gradient direction. The paper provides both convergence and privacy analyses of the proposed algorithms, and presents numerical results on CV and NLP datasets.", "questions": "Please address the weakness.\n\nI believe the theoretical analysis is limited and may contain errors. If my concerns about the theoretical analysis can be addressed, I would love to increase my score.", "limitations": "N/A", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strength:\n1. The paper provides novel ways of mixing zeroth and first-order gradients for differentially private optimization.\n2. The paper introduces $\\gamma$-similarity to measure the dissimilarity between the public and private data distributions.\n3. The paper provides a theoretical analysis for the privacy and convergence guarantee of all three proposed algorithms under reasonable assumptions.\n4. Numerical results show that the proposed algorithms outperform the baseline algorithm DPZero and are less sensitive to $\\epsilon$.\n\nWeakness:\n1. For PAZO-P and PAZO-S, how does the memory consumption compare with DP-Zero or PAZO-M? A key benefit of using ZOO is its memory-saving. If the FO gradient matrix G uses too much memory, there might be no point in using the ZO gradient. \n2. For PAZO-M, clipping the function value itself does not make sense to me. In the case that $f$ is very large (or very small), clipping it to C does not provide any information. It might be more reasonable to clip the function difference. \n3. Is argmin the best operator for PAZO-S? The author fails to investigate other smoothed versions of argmin to avoid directly dropping the other gradient information.\n\n4. For theoretical analysis, the convergence results rely on the clipping being inactive. While in DPZero, the effect of clipping is taken into consideration with the concentration bound. Therefore, the analysis requires further refinement to avoid assuming the clipping is inactive and the bounded gradient Assumption 1.\n5. The paper does not provide the final privacy-utility trade-off, i.e., the optimal choice of steps $T$ for convergence. \n6. In the proof in B.4 for PAZO-S, in lines 550 and 551, it is unclear to me why the expected value of $g_t - g'(x_t;B'_{*})$ is bounded by $\\sigma^2_2$. Since after argmin, $g'$ is no longer unbiased.\n\n7. I didn't find the choice of $b$ in Table 8. Also, for DP-SGD, why is $b$ not an integer?\n8. Since the paper introduced $\\gamma$, it is good to have a set of experiments demonstrating how the algorithm performs with different $\\gamma$'s for one dataset.", "was_revised": true, "final_justification": "Based on the rebuttal discussion and clarification. I believe the issues in the theoretical analysis are minor and can be fixed during final revision. The numercial experiment details have also been clarified. Therefore, I would raise my score.", "rebuttal": "We appreciate the reviewer’s time and detailed feedback. We address the concerns and clarification questions as follows.\n\n**[Memory cost of PAZO]** While we agree that PAZO requires memory for public gradients, it eliminates the memory/computation/implementation bottleneck of maintaining per-sample gradients in private settings. PAZO is more efficient (and sometimes more accurate) than differentially-private first-order methods, and is more accurate than vanilla DP zeroth-order methods without public data.\n\nIn Table 6 of our submission, we present the number of different operations needed per iteration of each method. Specifically, PAZO-M requires one batch of public gradient, so the memory overhead is $O(d)$, where $d$ is the number of model parameters. PAZO-S is also $O(d)$ since we can compute the $k$ public batch gradients sequentially. Though PAZO-P has an $O(kd)$ memory overhead than DPZero, it is still more memory- and computation-efficient than the first-order DP methods because the latter generally require $O(bd)$ memory to maintain per-sample gradients, where $b$ is the private batch-size. Our experimental results are obtained using $k=\\\\{3,6\\\\}$ while $b=64$. Such dependence on $b$ is also restrictive since larger batch-sizes improve performance [3,4]. \n\nTherefore, compared to first-order DP with public data, PAZO 1) enjoys time- and memory-efficiency and 2) performs better under tight privacy; compared to DPZero, PAZO converges faster to better accuracies, at the cost of computing public batch gradients.\n\n**[Clipping difference]** We’d like to clarify that for PAZO-M, we indeed clip the function difference (Algorithm 1 line 8). Please let us know if the reviewer still has concerns. \n\n**[argmin in PAZO-S]** We motivate the design of argmin as in Eq. (3) where in that particular setting, argmin is optimal. We note that a smoothed version of argmin (linearly combining the public gradients) is explored in PAZO-P, where the final update direction is a linear combination of the public gradients. We acknowledge that this is a promising direction, and we leave it as future work to explore other ways to determine the coefficients.\n\n**[Refined bounds with active clipping and final privacy/utility tradeoffs]** We note that we did not incorporate effective clipping in the original submission as we were using weaker assumptions. In particular, DPZero uses our Assumption 1 ([1] page 37, the equation above Eq. 21), in addition to a stronger per-sample Lipschitz assumption (Assumption 3.1 in [1]). Our submission assumed inactive clipping also because 1) it is a common assumption in DP literature [2] and 2) our novelty is not proposing/analyzing clipping methods but exploring leveraging public information in zeroth-order optimization both theoretically and empirically.\n\nHowever, for a clearer comparison with DPZero, we thank the reviewer for suggesting this and provide the refined error bounds considering active clipping and privacy/utility tradeoffs under exactly the same assumptions as DPZero:\n\n**PAZO-M.** For any $\\varepsilon>0$ and $\\delta\\in(0,1)$, PAZO-M is $(\\varepsilon,\\delta)$-DP. Under Assumption 3.5 in [1], suppose $\\max_{0\\leq t\\leq T} |F_S(x_t)|\\leq B$, the output $x_{\\tau}$ satisfies \n$$  \\mathbb{E}[\\Vert\\nabla F_S(x_{\\tau})\\Vert^2] \\leq \\frac{\\sqrt{r\\log(e + \\varepsilon/\\delta)}}{n\\varepsilon} \\left[ 64((F_S(x_0) - F_S^*)l + (1-\\alpha)^2\\tilde{L}^2)+ 2L^2 \\right] + 4(\\alpha(\\gamma^2+\\sigma_2^2/b^{\\prime}) ) + \\frac{\\alpha^2(\\gamma^2+\\sigma_2^2/(2b'))}{4(1-\\alpha)^2(r+2)}$$\n\nwhere we define $\\tilde{L}^2 = L^2\\log\\left(\\frac{2\\sqrt{2\\pi}n^3\\varepsilon^2(r+2)((1-\\alpha)d+\\alpha+8(1-\\alpha)^2lB(r+2)/L^2)}{r\\log(e+\\varepsilon/\\delta)}\\right)$\n\nand choose the parameters to be\n$$\\eta = \\frac{1}{4(1-\\alpha)^2l(r+2)}, \\quad T=\\frac{(1-\\alpha)^2n(r+2)\\varepsilon}{4\\sqrt{r\\log(e+\\varepsilon/\\delta)}}, \\quad \\lambda\\leq \\frac{L}{ld^{\\frac{3}{2}}}\\left(\\frac{\\sqrt{r\\log(e+\\varepsilon/\\delta)}}{n\\varepsilon}\\right)^{\\frac{1}{2}}, \\quad C=4\\tilde{L}.$$\n\nThis shows that our dependence on $d$ and $r$ becomes $O((1-\\alpha)^2\\sqrt{r}\\log((1-\\alpha)d))$. Compared to DPZero's $O(\\sqrt{r}\\log d)$, if $\\alpha>0$, our error has a smaller dependence on $d$ but additional errors $O(\\alpha^2/(1-\\alpha)^2(\\gamma^2+\\sigma_2^2/b^{\\prime}))$ due to using biased public gradients.\n\n**PAZO-P.** For any $\\varepsilon>0$ and $\\delta\\in(0,1)$, PAZO-P is $(\\varepsilon,\\delta)$-DP. Under the same assumptions as stated above, the output $x_{\\tau}$ satisfies \n$$ \\mathbb{E}[\\Vert\\nabla F_S(x_{\\tau})\\Vert^2] \\leq \\frac{\\sqrt{r\\log(e + \\varepsilon/\\delta)}}{n\\varepsilon} \\left[ 64((F_S(x_0) - F_S^*)l + \\tilde{L}^2)+ 3L^2 \\right] + 8(\\gamma^2+\\sigma_2^2/b^{\\prime}) $$\nwhere we define $\\tilde{L}^2 = L^2\\log\\left(\\frac{2\\sqrt{2\\pi}n^3\\varepsilon^2(r+2)(k+8lB(r+2)/L^2)}{r\\log(e+\\varepsilon/\\delta)}\\right)$ and choose $C=4\\tilde{L}$ and $\\eta, T$, and $\\lambda$ the same as in DPZero Theorem 3 [1]. This shows that we achieve a $d$-independent error bound $O(\\sqrt{r}\\log k) + O(\\gamma^2+\\sigma_2^2/b^{\\prime}), k\\ll d$.\n\n**[Proof in B.4]** We thank the reviewer for pointing out the typo—the upper bound should be $2\\sigma_2^2$, and all the remaining analysis still holds (differing by a constant). We provide step-by-step derivation for the claim $\\mathbb{E}[\\Vert g_t^{\\prime}−g^{\\prime}(x_t;B_∗^{\\prime})\\Vert^2] \\leq 2\\sigma_2^2/b^{\\prime}$ as follows:\n\nRecall that $b'$ is the public batch-size and $g_t^{\\prime}$ is the full public gradient. For a sampled public batch index $i\\in[k+1]$, its gradient is $g(x_t;B_{t,i}^{\\prime}) = g_t^{\\prime} + \\frac{1}{b^{\\prime}} \\sum_{j=1}^{b^{\\prime}} \\zeta_{t,j}^{(i)}$ where $\\zeta_{t,j}^{(i)}$ is the stochastic gradient noise for the public sample $j$ in the $i$-th batch. We denote the selected best batch as $I$ and thus\n\n$$ \\mathbb{E}\\_{B_t^{\\prime}}[\\Vert g_t^{\\prime}-g^*(x_t;B_t^{\\prime})\\Vert^2]  = \\mathbb{E}\\_{B_t^{\\prime}} \\left[\\Vert\\frac{1}{b^{\\prime}}\\sum_{j=1}^{b^{\\prime}}\\zeta_{t,j}^{(I)}\\Vert^2\\right]  = \\frac{1}{b^{\\prime}} \\mathbb{E}\\_{B_t^{\\prime}} \\left[\\Vert\\zeta_{t}^{(I)}\\Vert^2\\right] = \\frac{1}{b^{\\prime}} \\left( \\Vert\\mathbb{E}\\_{B_t^{\\prime}} \\left[\\zeta_{t}^{(I)}\\right]\\Vert^2 + \\mathbb{E}\\_{B_t^{\\prime}} \\left[\\Vert\\zeta_t^{(I)} - \\mathbb{E}\\_{B_t^{\\prime}}[\\zeta_{t}^{(I)}]\\Vert^2\\right] \\right).$$\n\nBy assumption, $\\mathbb{E}\\_{B_t^{\\prime}} \\left[\\Vert\\zeta_{t}^{(i)}\\Vert^2\\right] \\leq \\sigma_2^2$ for any batch $i$. The choice of $I$ is dependent on the private data batch $B_t$. Therefore, by the law of total expectation,\n\n$$\\Vert\\mathbb{E}\\_{B_t^{\\prime}} \\left[\\zeta_{t}^{(I)}\\right]\\Vert^2 = \\Vert\\mathbb{E}\\_i \\left[ \\mathbb{E}\\_{B_t^{\\prime}} [\\zeta_{t}^{(I)}|I=i]\\right]\\Vert^2 \\leq \\mathbb{E}\\_i \\left[ \\Vert\\mathbb{E}\\_{B_t^{\\prime}} [\\zeta_{t}^{(I)}|I=i] \\Vert^2 \\right] \\leq \\mathbb{E}\\_i [\\sigma_2^2] = \\sigma_2^2.$$\n\nFor the variance term,\n$$ \\mathbb{E}\\_{B_t^{\\prime}} \\left[\\Vert\\zeta_{t}^{(I)} - \\mathbb{E}\\_{B_t^{\\prime}}[\\zeta_{t}^{(I)}]\\Vert^2\\right] \\leq \\mathbb{E}\\_{B_t^{\\prime}} \\left[\\Vert\\zeta_{t}^{(I)}\\Vert^2\\right] = \\mathbb{E}\\_i \\left[ \\mathbb{E}\\_{B_t^{\\prime}} \\left[\\Vert\\zeta_{t}^{(I)}\\Vert^2\\right] |I=i \\right] \\leq \\sigma_2^2.$$\n\nSubstituting the bias and variance bounds, we obtain $\\mathbb{E}\\_{B_t^{\\prime}}[\\Vert g_t^{\\prime}-g^*(x_t;B_t^{\\prime})\\Vert^2] \\leq 2\\sigma_2^2/b^{\\prime}.$\n\n**[Choice of b in Table 8]** In hyperparameter tuning, $b$ is tuned only for non-private methods (MeZO and SGD). We fixed the private batch-size to 64 for all private methods, including zeroth-order and first-order, with and without public data. We will make it clear in our appendix. We thank the reviewer for finding the typo in the line for DP-SGD in Table 8—the $b$ should have been $\\eta$.\n\n**[Performance under various $\\gamma$]** To create public data of different extents of distribution shifts (different $\\gamma$), we mix ID public data (MNLI) and OOD public data (SNLI) with different proportions. We present the performance and $\\gamma$ of PAZO ($\\varepsilon=1.0$) under these scenarios. We observe that 1) the range of $\\gamma$ is method-dependent and 2) for any fixed PAZO variant, the accuracy increases as the data become more similar (smaller $\\gamma$).\n| Pub data \\ Method  | PAZO-M | PAZO-P | PAZO-S |\n| -- | -- | -- | -- | \n| MNLI only | 75.9 ($\\gamma=38$) | 73.2 ($\\gamma=43$) | 74.0 ($\\gamma=49$) |\n| Half-half | 73.5 ($\\gamma=49$) | 72.7 ($\\gamma=45$) | 73.1 ($\\gamma=67$) |\n| SNLI only | 67.7 ($\\gamma=72$) | 68.8 ($\\gamma=68$) | 68.9 ($\\gamma=81$) |\n\nWe also present results on CIFAR10 with public data of different extents of distribution shifts, where we observe similar trends. The public data with slight class imbalance has class_size ratios $[1:...:0.85]$. To create public data with more distribution shift, we enforce big class imbalance (with class_size ratios $[1.0:0.9:0.8:...:0.2:0.1]$).\n| Pub data \\ Method  | PAZO-M | PAZO-P | PAZO-S |\n| -- | -- | -- | -- | \n| Slight imbalance | 70.2 ($\\gamma=4.5$) | 69.2 ($\\gamma=3.3$) | 70.2 ($\\gamma=1.6$) |\n| Half-half | 69.8 ($\\gamma=4.9$) | 67.6 ($\\gamma=3.8$) | 67.3 ($\\gamma=1.8$) |\n| Big imbalance | 65.5 ($\\gamma=6.4$) | 64.1 ($\\gamma=4.7$) | 63.0 ($\\gamma=2.1$) |\n\n[1] DPZero: Dimension-Independent and Differentially Private Zeroth-Order Optimization. ICML 2024. \\\n[2] Do Not Let Privacy Overbill Utility: Gradient Embedding Perturbation for Private Learning. ICLR 2021. \\\n[3] Learning Differentially Private Recurrent Language Models. ICLR 2018. \\\n[4] Unlocking High-Accuracy Differentially Private Image Classification through Scale. ICML 2022."}, {"review_id": "qRejXJPIDR", "reviewer": "Reviewer_97FF", "summary": "The paper considers to use public data to assist private zeroth-order optimization. Existing works have shown that zeroth-order methods can be applied to differentially private training or fine-tuning. However, there is still a gap in terms of performance compared with first-order methods. This work proposes a suite of public data assisted zeroth-order optimizers (PAZO), including PAZO-{M,P,S}. PAZO-M simply uses a convex combination of private zeroth-order estimations and public gradient as the descent step. PAZO-P narrows the search space of zeroth-order optimization into a subspace constructed using public gradient. PAZO-S uses private data to select the best public gradient. Convergence analysis shows that all three methods match the worst-case upper bound of existing results. Empirical experiments show that all three methods match or even outperform exising public data assisted first-order methods, while offering speedup in time.", "questions": "Major questions are already asked in weakness. Other minor:\n\n1. Typos: should it be \"rely on\" instead of \"reply on\" in line 21 and line 132? I guess it should be \"combined with these prior methods\" in line 88.\n\n2. The paper uses random direction uniformly on the sphere when introducing the algorithm. Random search directions from Gaussian are also extensively used in previous work. Which noise is used in the experiments? How do these two compare in both the theory and experiments?\n\n3. Isn't it costly to sample $k$ mini-batches in PAZO-P and PAZO-S? What is the value of $k$ and batch size $b$ used for each method when comparing time efficiency in Figure 5?", "limitations": "Limitations are already discussed in the weakness, including dimension dependence in theoretical results and memory consumption.", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper is clearly written, and the studied topic is interesting and important for the community. The claims are supported by evidence, and the results look good to me. My concerns are following.\n\n1. Why is $\\gamma$ similarity used? A more natural measure to me is the cosine similarity. In all convergence results, there is dependence on $\\sigma$. I understand the meaning of $\\sigma_1$ and $\\sigma_2$, but what is $\\sigma$? What is the dependence on $q$ and the dimension $d$ in all theoretical results? The dependence on the dimension $d$ is crucial in zeroth-order methods and should be highlighted and well discussed.\n\n2. In several places of the paper, the authors say existing zeroth-order methods only consider prompt tuning for language models, like [6,7,8,10]. I think this is not a correct statement. Prompt tuning is one efficient way of doing language model fine-tuning, where only prompt embeddings are updated and the base model is frozen. This is not what [6,7,8,10] do. In these related works, all trainable model parameters are updated and thus considered to be full parameter fine-tuning. The authors should correct all these wrong statements.\n\n3. One of the major reasons that previous works propose to use zeroth-order methods is to save memory by avoid gradient computations. In PAZO, public gradients are anyway required, and thus this benefit of saving memory is lost. Is there a comparison in terms of GPU memory for all methods, including vanilla DPZero and DPSGD, PAZO-{M,P,S}, and public-data assisted first-order methods?\n\n4. The authors claim in the contribution that improved convergence can be guaranteed using a proper choice of parameters. It is not clear in the main text how the rates can be improved. Is this improvement only in terms of constants or also in terms of key parameters like $T$ and $d$?", "was_revised": true, "final_justification": "My major concern is on the memory efficiency of the proposed method, as public gradient is required but the main motivation to use zeroth-order methods is to save memory by avoiding gradient computation. The author replied in the rebuttal that the saving in memory is on the private data compared with public data assisted DP first-order methods. This makes some sense but not fully resolved this limitation. However, there might be some settings where the proposed methods provide clear advantage. I think the paper proposes an interesting and new observations that public data can greatly improve the performance of private zeroth-order methods. The reasons to accept outweight reasons to reject, so I keep my score 4 for acceptance.", "rebuttal": "We are grateful to the reviewer for the careful reading and valuable comments. We present our responses as follows.\n\n**[$\\gamma$- vs. cosine similarity]** We thank the reviewer for this suggestion. Cosine similarity measures angular alignment, while Euclidean distance captures both scale and angle mismatch. Since $\\Vert a−b\\Vert\\leq\\gamma$ ensures $b$ stays within a $\\gamma$-radius ball around $a$, it more directly controls the absolute error of gradient updates in convergence analysis, which is also adopted by existing literature [2,3]. Empirically, we observe that our Euclidean similarities consistently correlate positively with performance (Table 1-2 in rebuttal). However, we acknowledge that cosine similarity could complement our analysis: If we assume $\\Vert a\\Vert\\leq M_1$ and $\\Vert b\\Vert\\leq M_2$, then the cosine similarity lower bound $\\text{cos⁡}(a,b)\\geq \\varphi$ implies $\\Vert a-b\\Vert\\leq\\gamma=\\max(M_1, M_2, \\sqrt{M_1^2+M_2^2-2M_1M_2\\varphi})$, which can be plugged into our current analysis. We leave more geometric-aware similarity measures and their relations to the convergence of our methods and those of others for future work.\n\n**[Clarification on $\\sigma$]** We clarify that $\\sigma$ is the variance of the noise we add to guarantee differential privacy (Section 3.4 in our submission, line 171). \n\n**[Dependence on $q$, $T$, $d$, and improved convergence]** We achieve either constant improvements or better dependence on $d$, depending on the specific PAZO variant. Specifically, if we choose $T=\\frac{(1-\\alpha)^2n(r+2)\\varepsilon}{4\\sqrt{r\\log(e+\\varepsilon/\\delta)}}$, PAZO-M achieves $O((1−\\alpha)^2\\sqrt{d} \\log((1−\\alpha)d))$, which has a better dependence on $d$ than DPZero if the errors from public data $O(\\alpha^2/(1-\\alpha)^2(\\gamma^2+\\sigma_2^2/b'))$ do not dominate. If we choose $T=\\frac{n(r+2)\\varepsilon}{4\\sqrt{r\\log(e+\\varepsilon/\\delta)}}$, PAZO-P has $d$-independent error rate $O(\\sqrt{d} \\log k)$ with an additional error $O(\\gamma^2 + \\sigma_2^2/b')$ where $k \\ll d$ is the number of bases of $G$. PAZO-S has an error rate that is $d$-independent since it selects the best public gradient as the update direction.\n\nWhen $q>1$, the error of zeroth-order optimization reduces by $O(1/q)$ while the variance of the noise $z$ increases by $q$-times. The resultant error term will be of the form $Aq+B/q$ for some $A$ and $B$, so the optimal $q$ can be chosen as $q=\\sqrt{B/A}$. \n\n**[Wording on prompt tuning]** We thank the reviewer for pointing it out. We would like to clarify that we use “prompt tuning” to refer to the task of full-parameter fine-tuning with prompts. Our argument is that (which also aligns with [5]) ZO may not work in standard full-model fine-tuning without prompts where 1) the input sequence is not modified with task-specific natural language templates or 2) a task-specific classification head is added on top of the final \\<s\\> embedding. We will replace “prompt tuning” with “full fine-tuning with prompts” to eliminate the vagueness.\n\n**[Memory cost of PAZO]** While we agree that PAZO requires memory for public gradients, it eliminates the memory/computation/implementation bottlenecks when we consider private settings. PAZO is more efficient (and sometimes more accurate) than differentially-private first-order methods, and is more accurate than vanilla DP zeroth-order methods without public data. \n\nIn Table 6 of our submission, we present the number of different operations needed per iteration of each method. Specifically, PAZO-M requires one batch of public gradient, so the memory overhead is $O(d)$, where $d$ is the number of model parameters. PAZO-S is also $O(d)$ since we can compute the $k$ public batch gradients sequentially. Though PAZO-P has an $O(kd)$ memory overhead than DPZero, it is still more memory- and computation-efficient than the first-order DP methods because the latter generally requires $O(bd)$ memory to maintain per-sample gradients, where $b$ is the private batch-size. Our experimental results are obtained using $k=\\\\{3,6\\\\}$ while $b=64$. Such dependence on $b$ is also restrictive since larger batch-sizes improve performance [6,7]. \n\nTherefore, compared to first-order DP with public data, PAZO 1) enjoys time- and memory-efficiency and 2) performs better under tight privacy; compared to DPZero, PAZO converges faster to better accuracies, at the cost of computing public batch gradients.\n\n**[Perturbation sampling]** We would like to clarify that we use Gaussian perturbations in our experiments (line 570-572 in our submission) as most of the other ZO work does [1,4,5]. Our rationales are two-fold. (1) Theoretically, uniform sampling from the sphere and sampling from Gaussian are closely related: To sample from $\\text{Uni}(\\sqrt{d}S^{d-1})$, it is equivalent to sample a vector from $\\mathcal{N}(0, I_d)$ and then scales it to have norm $\\sqrt{d}$. Since the norm of $v\\sim\\mathcal{N}(0, I_d)$ concentrates on $\\sqrt{d}$ with variance $O(1/d)$, we can expect that sampling from these two distributions does not give us much different vectors when $d\\gg 1$ with high probability. \n\n(2) Empirically, prior work [1] has shown that Gaussian and sphere perturbations produce very similar results. The following table shows that this also holds for PAZO, where we present the accuracy of sampling from Gaussian minus that of sampling from the sphere ($\\varepsilon=1$).\n\n| Method | CIFAR10 |Tiny-ImgNet |IMDB |MNLI |\n| -- | :--: | :--: | :--: | :--: |\n| PAZO-M | 0.9 | 0.2 | 0.5 | -0.3 |\n| PAZO-P | 0.7 | -0.1 | -0.7 | 1.1|\n| PAZO-S | 0.4 | 0.5 | -0.4 | 0.9 |\n\n**[Figure 5 hyperparameter]** We would like to clarify that each run plotted in Figure 5 is the one with the best accuracy of the corresponding method after $\\\\{k, b^{\\prime}\\\\}$ are tuned. DPZero is occasionally slower than PAZO because we try $q=\\\\{1,5\\\\}$ for each method and use $q=1$ if $q=5$ does not bring significant improvements. As presented in Table 7 in our submission, we observe that the optimal $q$ for DPZero is $5$ while public information allows PAZO to use $q=1$ to achieve competitive accuracies. \n\nThough the runs of PEZO-P and PAZO-S in Figure 5 require computing $k$ batch gradients, $k=\\\\{3,6\\\\}$ are small. $q=1$ for PAZO and $q=5$ for DPZero. The values of $b^{\\prime}$ of each method are presented below. \n\n| Method | CIFAR10 |Tiny-ImgNet |IMDB |MNLI |\n| -- | :--: |:--: |:--: |:--: |\n| DPMD | 8 | 8 | 8 | 8 |\n| DOPE-SGD | 8 | 32 | 8 | 8 |\n| GEP | 32 | 32 | 32 | --|\n| PAZO-M | 8 | 8 | 4 | 32 |\n| PAZO-P | 32 | 16| 64| 32|\n| PAZO-S | 8 | 8 | 8 | 8|\n\n[1] DPZero: Dimension-Independent and Differentially Private Zeroth-Order Optimization. ICML 2024. \\\n[2] Train Faster, Generalize Better: Stability of Stochastic Gradient Descent. ICML 2016. \\\n[3] Optimization Methods for Large-Scale Machine Learning. SIAM Review 2018. \\\n[4] Revisiting Zeroth-Order Optimization for Memory-Efficient LLM Fine-Tuning: A Benchmark. ICML 2024. \\\n[5] Fine-Tuning Language Models with Just Forward Passes. NeurIPS 2023. \\\n[6] Learning Differentially Private Recurrent Language Models. ICLR 2018. \\\n[7] Unlocking High-Accuracy Differentially Private Image Classification through Scale. ICML 2022."}, {"review_id": "Vin8jNKmfi", "reviewer": "Reviewer_5rKD", "summary": "The authors present a novel zero-order optimization algorithm that is guided by some first-order information (i.e., gradients) of publicly available data. They introduce three different ways of integrating such information in the zero-order optimization process and show that they can achieve faster convergence while still keeping the privacy advantages coming with zero-order optimization.", "questions": "- wouldn't a repeated querying of the same function lead to a much higher privacy budget needed to ensure DP?", "limitations": "The work should explicilty discuss current limitations (at least briefly).", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n- The idea is interesting and reasonable in distributed environments where data privacy is important\n- the paper is written clearly\n- a convergence analysis is provided\n- empirical results look promising\n\n**Weaknesses**\n\n- in Algo. 1 it is unclear how the batch of public data is obtained. Since it should match with the private batch as good as possible, the authors should describe how they ensure that both batches exhibit similar data characteristics (if they exhibit conflicting characteristics, divergence might even happen)\n- in the unnumbered between 141-142 it is not clear to me why with the presented equation, the coefficients $u$ are learned. Please clarify this.\n- in the Equation before line 142, why is it $\\mathbb{E}_u[\\nabla f(x)^T GuGu]$? Isn't it only $Gu$? If so, the subsequent equations are also wrong. A brief derivation would be helpful here.\n- The authors claim an equivalence between their projection of the gradient and the expectation of gradient approximations when sampling from a ball induced by $G$ (see lines 143-144). Please provide proof of this equivalence.\n\nSince I am not familiar with the field of DP and zero-order optimization, my review should be used with care for the final decision.", "was_revised": true, "final_justification": "As I have written in my initial review, I think the authors' work is a significant contribution towards efficient zero-order optimization in privacy restricted regimes. The use of publicly available data is a promising direction to advance optimization algorithms under privacy constraints. In their rebuttal, the reviewers have addressed all my points raised in the initial review. Although I didn't read the other reviews in full detail, it seems the authors have addressed major concnerns in the rebuttal.", "rebuttal": "We appreciate the reviewer’s valuable feedback and positive assessment of our work. We present our responses below.\n\n**[Choice of public batch]** We thank the reviewer for carefully noticing this. In practice, public data can be obtained via users who opt out of private training or other side information/statistics of the sensitive data [1], which would guarantee certain similarities.\n\nSince there is no prior work that leverages public information in private zeroth-order optimization, we present all three PAZO methods, each with different properties. PAZO-M (Algorithm 1) indeed simply aggregates the private ZO gradient with a randomly sampled public batch gradient, which is fast and memory-efficient. Empirically, we show that if we pick reasonable public data with mild distribution shifts, PAZO-M performs well. Theoretically, we show that if the public gradient is not close to the private gradient, one should reduce $\\alpha$ for better convergence.\n\nDue to the need for selecting good public gradients, we have proposed PAZO-P that allows for larger weights on good public gradients and smaller weights on less related public gradients. We also propose PAZO-S, which directly selects the public gradient that incurs the lowest loss. They may offer better performance in some scenarios (Section 5) while having more computational cost.\n\n[1] Private Adaptive Optimization with Side Information. ICML 2022.\n\n**[Learning coefficients]** We thank the reviewer for the careful reading and pointing out the vagueness. We are learning the coefficient in a zeroth-order fashion, i.e., relying on function evaluations. Specifically, when we sample $q$ $u$’s, each sampled $u$ is an aggregation proposal (for how to linearly combine the columns of $G$), and the loss difference is the feedback that indicates how good this proposal is. The update direction in PAZO-P, in essence, is a weighted average of the columns of $G$, with the weights (i.e., coefficients) depending on the loss differences. Since we take the feedback from $f$ to weigh and aggregate the public gradients, we interpret the coefficients to be learned. We will clarify this in the next version.\n\n**[Why GuGu]** A more detailed derivation is as follows: The term $\\Delta := [f(x + \\lambda Gu) - f(x - \\lambda Gu)]/(2\\lambda)$ is a central difference approximation to the directional derivative of $f$ at $x$ in the direction $Gu$. As $λ \\rightarrow 0$, this converges to $\\nabla f(x)^{\\top}Gu$. Therefore, \n$$\\mathbb{E}[\\Delta Gu]=\\mathbb{E}[\\nabla f(x)^{\\top} GuGu]=\\mathbb{E}[Gu\\nabla f(x)^{\\top}Gu]=\\mathbb{E}[Guu^{\\top}G^{\\top}\\nabla f(x)]$$ as claimed. \n\n**[Proof of equivalence]** We present the derivation as follows. Note that the expectation of the two-point zeroth-order gradient estimator is the same as that of one-point due to the symmetry of the sampling distribution:\n\n$$ \\mathbb{E}_u \\left[\\frac{f(x+\\lambda u) - f(x-\\lambda u)}{2\\lambda}u \\right] = \\mathbb{E}_u \\left[\\frac{f(x+\\lambda u) }{2\\lambda}u \\right] + \\mathbb{E}_u \\left[\\frac{ f(x + \\lambda (-u))}{2\\lambda}(-u) \\right] = \\mathbb{E}_u  \\left[\\frac{f(x+\\lambda u) }{\\lambda}u \\right].$$\n\nTherefore, the goal is to show $\\nabla_x \\mathbb{E}\\_{v\\sim\\text{Unif}(G(\\sqrt{k}B^k))}[f(x+\\lambda v)] = \\mathbb{E}\\_{u\\sim\\text{Unif}(\\sqrt{k}S^{k-1})}[\\frac{f(x+\\lambda u)}{\\lambda}u]$. According to the divergence theorem in higher dimensions, we define the body $\\Omega =G(\\sqrt{k}B^k) \\subset \\mathbb{R}^d$ and its boundary $\\partial\\Omega=G(\\sqrt{k}S^{k-1})$, and then we have\n\n$$ \\int_{\\Omega} \\nabla_v f(x+\\lambda v) dv = \\int_{\\partial\\Omega} f(x+\\lambda u) \\frac{u}{\\Vert u\\Vert} du = \\frac{1}{\\sqrt{k}} \\int_{\\partial\\Omega} f(x+\\lambda u) u du. $$\n\nNote that $\\nabla_v f(x+\\lambda v) = \\lambda \\nabla_x f(x+\\lambda v)$ and $\\text{Area}(r S^{d-1}) = \\frac{d}{r} \\cdot \\text{Vol} (r B^d)$. Since an orthonormal $G$ is area- and volume-preserving, we have $\\text{Area}(\\partial\\Omega) = \\sqrt{k} \\cdot \\text{Vol} (\\Omega)$. Combining the above, we obtain\n\n$$ \\nabla_x \\mathbb{E}\\_{v\\sim\\text{Unif}(\\Omega)}[f(x+\\lambda v)] = \\frac{1}{\\lambda \\text{Vol}(\\Omega)} \\int_{\\Omega} \\nabla_vf(x+\\lambda v) dv = \\frac{1}{\\lambda \\sqrt{k}\\text{Vol}(\\Omega)}  \\int_{\\partial\\Omega} f(x+\\lambda u) u du  = \\frac{\\text{Area}(\\partial\\Omega)}{\\lambda\\sqrt{k} \\text{Vol}(\\Omega)} \\mathbb{E}\\_{u\\sim \\text{Unif}(\\partial\\Omega)}[f(x+\\lambda u) u] = \\frac{1}{\\lambda} \\mathbb{E}\\_{u\\sim \\text{Unif}(\\partial\\Omega)}[f(x+\\lambda u) u]$$\nas desired.\n\n**[Privacy implications of $q$]** We thank the reviewer for emphasizing that and would like to clarify that we have already taken that into account by multiplying the variance of noise $z$ in each step by $q$ (Algorithm 1-3 in our submission). We present the privacy guarantees in Section 3.4.\n\n**[Limitations]** In Section 6, we acknowledge the limitation that the current convergence bound can be further sharpened by considering other similarity metrics, e.g., angle-based metrics. Further, a broader and larger-scale benchmark of public and private dataset pairs will enhance the significance of our empirical results."}, {"review_id": "quoOOQomuy", "reviewer": "Reviewer_jMhd", "summary": "This paper aims to accelerate zeroth-order differentially private optimization while improving gradient approximation by leveraging public data. The authors propose three PAZO variants and validate them both theoretically and empirically.", "questions": "- Why is the noise added to the scalar directional derivative $\\{f(x+\\lambda u)- f(x -\\lambda u)\\} / 2\\lambda$, instead of $\\text{clip}(\\{f(x+\\lambda u)- f(x -\\lambda u)\\} / 2\\lambda) \\cdot u$ as DPZero[7]? DPZero added noise to the vector after clipping, resulting in the noise added in all $d$ dimensions. However, in this paper, scalar noise is added and then multiplied by the random vector. This makes the direction of $u$ preserved. What are the privacy implications of preserving the direction of $u$? Even though the vector $u$ is random, it is used as an input in the directional derivative $f(x+\\lambda u)- f(x -\\lambda u) / 2\\lambda$, and thus may potentially leak private information. How can this be justified from a privacy perspective?\n- Figure 4 only reports PAZO-S. However, the convergence theorems show different upper bounds for PAZO-M, P, and S. Based on these, we would expect different convergence behaviors. Can the authors provide convergence plots for each variant?", "limitations": "More interpretation of experimental results is needed regarding robustness and the privacy-utility tradeoff.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths \n- Proposed three versions of the optimization method to utilize public data in zeroth-order settings.\n- The proposed methods often achieve performance comparable to first-order DP methods that use public data, while significantly improve the speed of private learning.\n- The privacy-utility trade-off is mitigated, which implies that PAZO can be useful where $\\epsilon$ is small.\n\n## Weaknesses\n- PAZO improves performance by using public data under the γ-similarity assumption. However, this raises the question: isn't the improvement mostly due to the public data alone? That is, isn’t it possible that the private data contributed very little during training? In fact (1) The performance does not vary much with the privacy budget. (2) The results are not very sensitive to hyperparameters.\nIn first-order methods, private gradients are clipped, whereas public gradients are not, meaning public gradients may dominate the update. As a result, private gradients might have a negligible impact. To address this, the authors should conduct an experiment using only public data (i.e., no private data, hence no privacy concerns), and explicitly report how much performance improves when private data is included.\n\n- In the vision domain, the authors assume in-distribution public data, while in the language domain, they assume out-of-distribution (OOD) public data. This seems to be done to satisfy the γ-similarity assumption. Perhaps in language tasks, even OOD data still lies in a similar feature space. If that is the case, the paper should discuss domain-specific similarity more clearly or unify the assumption across domains. If in-distribution public data is assumed, this should be clearly stated at the beginning of the paper.\n\n\n### Minor weaknesses\n- Notation should be changed. The notation of the model is $x$, while that of the data is $\\xi$. Normally, the use of the notation $x$ refers to data and $\\theta$ or $w$ to parameters. \n- Comparisons between methods using public data and those that do not (e.g., Figures 2 and 5) are unclear. As done in Tables 1–4, figures should visually differentiate methods that use public data (e.g., using distinct colors or styles).", "was_revised": true, "final_justification": "In the rebuttal, my major concern about the privacy guarantee was addressed. I raised my score from 3 to 4", "rebuttal": "We appreciate the reviewer's time and detailed feedback. We present our responses and address the concerns as follows.\n\n**[Performance of public only]** We thank the reviewer for this question. Indeed, we view the robustness of PAZO across various privacy budgets and hyperparameters as one advantage. Next, we demonstrate that the improvements are not due to overfitting to public data. As suggested, we train on public data alone using SGD with BS, LR, and WD tuned. We denote the optimal accuracy in each dataset as ‘public only’ and pick the best first-order with public data (FO+PUB) and zeroth-order with public data (PAZO) algorithm for each dataset. We present the performance gain when private data is included (i.e., ‘FO+PUB/PAZO’ minus ‘public only’ across $\\varepsilon=\\\\{0.1,0.5,1,2,3\\\\}$).\n\n|    | CIFAR10 | Tiny-ImgNet | IMDB | MNLI |\n| --- | :---: | :---: | :---: | :--: |\n| Public only  | 66.1 | 27.1 | 68.4 | 60.8 |\n| FO+PUB improvement | -1.3 ~ 6.8   | 3.4 ~ 8.4 | 1.8 ~ 9.5 | -4.3 ~ 12.0 |\n| PAZO improvement | 4.0 ~ 4.5  | 3.8 ~ 4.0 | 5.4 ~ 6.2 | 7.4 ~ 8.2 |\n\nNote that these ‘public only’ accuracies come with severe overfitting due to the small number of public samples. In contrast, the DP accuracies come without overfitting. We observe that 1) FO enjoys up to 12.0 performance gain and ZO enjoys up to 8.2 when public data is included; 2) ZO consistently enjoys performance gain when private data is included, while FO does not, since private gradient can be too noisy when privacy is tight.\n\n**[OOD vision public data]** We thank the reviewer for suggesting this. In our submission, for vision tasks, we did use public data with slight class imbalance (with class_size ratio $[1:...:0.85]$) and treated this as a mild distribution shift from the private data (Section 5.1 line 228). Our $\\gamma$ similarity assumption is an upper bound of the distribution gap, which is unified across different domains. To verify that vision OOD data also provide gradients with bounded distance from private gradient (i.e., reasonable $\\gamma$-similarity), we create a public dataset with big class imbalance (with class_size ratio $[1.0:0.9:0.8:...:0.2:0.1]$). (Running SGD on this imbalanced public data alone produces a test accuracy of 50.1 on balanced test data.) We report the test accuracies and $\\gamma$-similarity of PAZO below ($\\varepsilon=1$). We observe that while the range of $\\gamma$-similarity depends on specific methods, the values are consistently small. For a fixed PAZO variant, as the public data becomes more in-distribution, performance improves and $\\gamma$ decreases (i.e., gradients for public and private data become more similar). \n\n| Pub data \\ Method | PAZO-M | PAZO-P| PAZO-S | \n| --- | :---: | :---: | :---: | \n| Slight imbalance  | 70.2 ($\\gamma=4.5$) | 69.2 ($\\gamma=3.3$) | 70.2 ($\\gamma=1.6$) |\n| Half-half | 69.8 ($\\gamma=4.9$)   | 67.6 ($\\gamma=3.8$) | 67.3 ($\\gamma=1.8$) |\n| Big imbalance | 65.5 ($\\gamma=6.4$) | 64.1 ($\\gamma=4.7$) | 63.0 ($\\gamma=2.1$) |\n\nTo demonstrate improvements of PAZO under more out-of-distribution public data, we report the performance of PAZO compared with the best first-order methods with public data (Best FO+PUB, a.k.a. DOPE-SGD) under big class imbalance. It shows that 1) OOD vision public data improves the performance of all the methods; 2) ZO+PUB also outperforms FO+PUB under tight privacy budgets ($\\varepsilon\\leq 1$), even when the public data is OOD.\n\n| Type | Method | $\\varepsilon=0.1$ | $\\varepsilon=0.5$ | $\\varepsilon=1.0$ | $\\varepsilon=2.0$ | $\\varepsilon=3.0$ | \n| --- | --- | :---: | :---: | :---: | :---: | :---: | \n| FO | DP-SGD  | 46.7 | 49.7 | 50.8 | 54.2 | 54.5| \n| Best FO+PUB | DOPE-SGD|  54.8 | 60.1 | 64.2| **67.6** | **68.3** | \n|ZO | DPZero | 47.0 | 48.1 | 48.2 | 48.2 | 48.1 |\n| (ours) | PAZO-M | **65.3** | **65.6** | **65.5** | 65.9 | 66.3 |\n| (ours) | PAZO-P | 64.3 | 64.0 | 64.1 | 64.3 | 65.1 |\n| (ours) | PAZO-S | 63.2| 62.9 | 63.0 | 64.1 | 63.8 |\n\n**[Adding noise $z$]** Thank you for this question. We’d like to clarify that PAZO-M adds a scalar noise $z$ to the clipped scalar $\\text{clip}((f(x+\\lambda u)−f(x−\\lambda u))/(2\\lambda))$ (Algorithm 1 line 8 in our submission), following similar designs as in DPZero ([1] Algorithm 2 line 3). We note that another option of adding noise to the vector $\\text{clip}(f(x+\\lambda u)−f(x−\\lambda u)/(2\\lambda) )\\cdot u$ ([1] Algorithm 1 line 3) appeared in DPZero as one baseline, not their actual proposed algorithm ([1] Algorithm 2); and they show that adding noise to the scalar derivative is preferred ([1] Section 4 and Appendix E “Privacy guarantee”). The reviewer is correct that $(f(x+\\lambda u)−f(x−\\lambda u))/(2\\lambda) $ is data-dependent, which is exactly why we privatize this term (Line 8) to satisfy differential privacy. \n\n[1] DPZero: Dimension-Independent and Differentially Private Zeroth-Order Optimization. ICML 2024.\n\n**[Convergence speed]** Since figures cannot be uploaded here, we present the accuracy that DPZero converges to and compare the evaluation step index at which each ZO/ZO+PUB method achieves that accuracy ($\\varepsilon=1$). We observe that PAZO variants have slightly different convergence behaviors, but they are all consistently faster than ZO without public data.\n\n|    | CIFAR10 (acc 48.2) | Tiny-ImgNet (acc 27.5) | IMDB (acc 62.6) | MNLI (acc 58.2) |\n| --- | :---: | :---: | :---: | :--: |\n| DPZero  | 393 | 272 | 379 | 496 |\n| PAZO-M | 10  | 16 | 80 | 14 |\n| PAZO-P | 7 | 14 | 118 | 16 |\n| PAZO-S | 11  | 9 | 10 | 15 |\n\nWe will present the convergence plot of all variants in the revised paper. \n\n**[Notation and figure format]** We appreciate these suggestions and will adopt the new notation in our revised version. We will also update the figures by using more distinct colors and styles to differentiate methods with and without public data."}]

Author rebuttal:

Meta-review: After the discussion phase all reviewers agree that the submission is of high enough quality for publication to NeurIPS. As Area Chair, I agree and recommend acceptance.
Decision: Accept (poster)