Natural Perturbations for Black-box Training of Neural Networks by Zeroth-Order Optimization
Authors: Hiroshi Sawada
Kazuo Aoyama
Yuya Hikima
Venue: ICML 2025 poster (2025)
Keywords: Zeroth-order optimization
Multivariate normal distribution
Covariance matrix
Fisher information matrix
Primary area: optimization->zeroorder_and_blackbox_optimization
TL;DR: This paper proposes a novel concept and method for black-box training of neural networks by zeroth-order optimization.

Abstract: This paper proposes a novel concept of natural perturbations for black-box training of neural networks by zeroth-order optimization. When a neural network is implemented directly in hardware, training its parameters by backpropagation ends up with an inaccurate result due to the lack of detailed internal information. We instead employ zeroth-order optimization, where the sampling of parameter perturbations is of great importance. The sampling strategy we propose maximizes the entropy of perturbations with a regularization that the probability distribution conditioned by the neural network does not change drastically, by inheriting the concept of natural gradient. Experimental results show the superiority of our proposal on diverse datasets, tasks, and architectures.

Natural Perturbations for Black-box Training of Neural Networks by Zeroth-Order Optimization
Hiroshi Sawada'
Kazuo Aoyama
Yuya Hikima
Abstract
Parameter
Target vector
This paper proposes novel concept of natural perturbations for black-box training of neural net- works by zeroth-orde optimization. When a neu- ral network is implemented directly in hardware, training its parameters by backpropagation ends up with an inaccurate result due to the lack of detailed internal information. We instead employ zeroth-order optimization, where the sampling of parameter perturbations is of great importance. The sampling strategy we propose maximizes the entropy of perturbations with a regularization that the probability distribution conditioned by the neural network does not change drastically, by inheriting the concept of natural gradient. Exper- imental results show the superiority of our pro- posal on diverse datasets, tasks, and architectures.
Input vector I
Output vector y
Probability distribution
Neural network (black box)
Loss
p(z y) (white box)
Figure I. Training neural network implemented in hardware
nal information cannot be accurately obtained when the hardware is simulated by ordinary computer, for ex- ample, due to hardware-specifie manufacturing variations (Fang et al., 2019; Banerjee et al., 2023).
For such above cases, several black-box optimization meth- ods have been used to train the parameters of neural net- works on hardware, including genetic algorithm (Zhang et al., 2019; 2021), bacterial foraging optimization (Cong et al., 2022), covariance matrix adaptation evolution strat- egy (CMA-ES) (Chen et al., 2022; Lupo et al., 2023), and zeroth-order (ZO) optimization (Shen et al., 2017; Zhou et al., 2020; Gu et al., 2020; 2021; Bandyopadhyay et al., 2022). Among these methods, this paper focuses on ZO optimization (Liu et al., 2020) because it local search based (approximate) gradient vectors like backpropaga- tion and is expected to scale training neural networks with a moderately large number N of parameters.
1. Introduction
The backpropagation algorithm (Rumelhart et al., 1986; Amari, 1993; LeCun et al., 2015) is a standard technique for training the parameters of neural network on CPU or GPU-based ordinary computers. It computes the gradient vectors with respect to the parameters by backpropagat- ing the gradient information from the loss function defined at the output. For the computation, it is necessary to ob- tain detailed internal information, such as the derivatives of component-wii activation functions and layer-wise in- puts to neurons generated during the forward computation. On the other hand, when neural networks implemented directly in hardware (Figure 1), such optical neural net- works (Shen al., 2017; Ashtiani et al., 2022) and analog- based in-memory computing (Li et al., 2018; Aguirre et al., 2024), training the parameters by backpropagation ends up with an inaccurate result. This is because detailed inter-
The core operation of the ZO optimization for computing approximate gradient vectors is to slightly perturb the pa- rameter vector 0 E RR-V to 0 + pau with a smoothing hyper- parameter μ > and perturbation vector E R. and perform query to evaluate how the loss function changes from {(O) to E(O + pm)). Here, the perturbation vector is sampled from some distribution, typically from a multivari- ate standard normal distribution (O, I) with an identity matrix I (Duchi et al., 2015; Nesterov & Spokoiny, 2017) or similarly from uniform distribution on a unit sphere (Fazel et al., 2018). While these sampling strategies are plausible for shallow neural network, they are not the best way for deep neural network because the parameters correlated in the optimization landscape. The reason for the correlation is that many parameters are involved in a path from an input element to an output element of the neural network (Sawada et al., 2025). To mitigate the correlation of parameters, the use of coordinate- wise perturbations (Lian
'NTT Communication Science Laboratories, NTT Corpo- ration, Kyoto, Japan. Correspondence to: Hiroshi Sawada sawaaaa.iroshhi icec.org>.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Natural Perturbations for Black-box Training of Neural Networks by Zeroth-Order Optimization
What to maximize
Regularization
by
Parameter Space Discrepancy (PSD)
+ Function Space Discrepancy (FSD)
require detailed internal information and are therefore not applicable our black-box ZO optimization method. In- stead, we propose to simply partition large parameter set into small blocks. This makes perturbation vectors block coordinate and thus the FIM that we need block diagonal, whose inversion can be computed practically.
Loss decrease (steepest descent)
Natural gradient descent
Gradient descent
Distribution entropy (exploration)
Perturbations from (0, I)
Ours: Natural perturbations
This work builds on (Sawada et al., 2025), which points out that the parameters of an optical neural network are layered and thus correlated, and proposes method to perturb the parameters of a linear module. The advancement of this work over the previous work is substantial as follows.
Figure 2. Criteria for methods computing gradient or perturbations
et al., 2016; Berahas et al., 2022; Chen et al., 2024) is effec- tive, where perturbation vector u has only one non-zero element. However, the disadvantage is that it requires as many queries the number of parameters to change the entire parameters.
The concept of natural perturbations is newly proposed as Figure 2 shows clear relations to the existing methods (gradient or perturbation and natural or not).
Returning to the situation where we can use backpropaga- tion, the natural gradient method (Amari, 1998; Pascanu & Bengio, 2013; Martens, 2020) known to be effective especially when the parameters are correlated. It modifies the gradient vector computed by backpropagation based the Fisher information matrix (FIM), which describes how the parameters are correlated. Regarding ZO optimization, some methods (Zhao et al., 2020; Sawada et al., 2024) have been proposed to introduce the idea of natural gradient. Al- though these methods modify the 70 gradient vector based on the natural gradient criterion, they do not suggest an ap- propriate distribution from which sample perturbations.
A black-box method to compute FIMs is newly proposed in Section 4.1, whereas the previous work needs to simu- late the internal information, which may be inaccurate.
The new Zo optimization method can efficiently handle convolutional neural networks (CNNs) and recurrent neu- ral networks (RNNs), which the previous work cannot do because FIMs are computed in a module-wise manner.
The rest of this paper is organized as follows. Section 2 formulates neural network, and explains natural gradient and ZO optimization. We then newly propose natural per- turbations in Section 3, and describe a practical method for ZO optimization using them in Section 4. Section 5 shows the experimental results to demonstrate the effectiveness of our proposal. Section 6 concludes the paper.
This paper proposes a novel concept of natural perturba- tions and a way to design the distribution from which we sample them. The term "natural" refers to the same meaning as natural gradient, but the criterion of natural perturbations different and newly introduced in this paper. As sum- marized in Figure 2. natural gradient descent aims at the steepest descent direction by taking care not only of the parameter space discrepancy (PSD), which is the only regu- larization in gradient descent, but also of the function space discrepancy (FSD) defined with the FIM, as will be detailed with (5). Analogously, natural perturbations are sampled by considering not only the PSDs but also the FSDs. What to maximize in this sampling strategy is the entropy of the distribution, making the sampled perturbations explore as widely as possible. As will be shown in Section 3.1, the existing sampling strategy from (O, I) can be considered to maximize the entropy only under the PSD regularization.
2. Preliminaries
2.1. Neural Network and Loss Function
As shown in Figure 1, we consider neural network f with parameter vector O E RN that transforms an input vec- tor æ E R.K to an output vector = fæx 0) E RR- A probabilistic interpretation can be given that the neural net- work expresses conditional distribution po(= ax) = =z)=p(z) I f (xx, 0)) with a probability distribution p(= yy defined at the output. Given a training dataset D,, = {(2 t)}. each element of which is pair of an input vector and target vector t, the loss function for mini-batch DD C Drr can be defined as
Our proposed method and natural evolution strategies (NES) (Wierstra et al., 2014) are both black-box optimization meth- ods that use the FIM. However, they are fundamentally different described in Appendix B.
(0) == - p(t f(x, 0))]
(1)
where In represents the natural logarithm, i.e., In = logg.
2.2. Natural Gradient
For neural networks with large number N of parameters, computing and inverting the FIM introduced above is prac- tically prohibited because the matrix size is 2 For natural gradient, sophisticated approximation methods (Martens & Grosse, 2015; Benzing, 2022) have been proposed, which
For a small change 80 E R. of 0, we measure how the conditional distribution changes using the Kullback-Leible (KL) divergence dKL (po (x pe)))o (x
x)). The func-
tion space discrepancy (FSI) is the expected value of the
2

---

Natural Perturbations for Black-box Training of Neural Networks by Zeroth-Order Optimization
measurements over a subset 'D of the training dataset
Algorithm ZO optimization for training a neural network
Input: training dataset Dtr = {(x,, t)], hyperparameters Q,
(D(60) == Re (ddk. az), (2 (2))))
2: Initialize the parameter vector 0
3: while not converged do
Note that the target vectors t are not used here (Kunstner et al., 2019). Let us approximate the above by the Taylor series expansion of dıL. up to the second order (Pascanu & Bengio, 2013; Martens, 2016). Then it is given as
4: Sample mini-batch D from D..
5: Evaluate loss ( by (1)
6:
Sample perturbations ug. 9 = I....... from (0,
7:
Compute the approximate gradient (ol by (10)
8: Update the parameter vector 0 by (9)
9: end while
1 T Fo 50 ED (00) = 50
tr - (Fo0050T)
(3)
2
with the Fisher information matrix (FIM)
compute the gradient VelD(O) precisely. Still, we can ap- proximate the gradient by
Fe = Em Ex Ve po x)) Vo Inp(( xx
(4)
(D + uu) (0) u
(1) (0(0) := BuuA((o.))
where the expectation notations in concise forms E= Eaw and Ez[-] = (x=
/
(8)
With parameter update 0 < 0 + 50 in mind, natural gradient descent as well as ordinary gradient descent can be formulated as the minimization problem (Bae et al., 2022)
which is derived from Gaussian smoothing of (D( with multivariate standard normal distribution (0, I) and a smoothing hyperparameter μ (Nesterov Spokoiny,
50 + arg min (e +r} with
(5)
2017: Berahas et al., 2022).
50
Ap (NG)
(NG) ||00 + A T
Algorithm I shows a procedure for training neural network with ZO optimization. For each mini-batch D, we update the parameter vector 0 by
r: 21)
ED()
(6)
where || is the parameter space discrepancy (PSD) defined by the squared 12-nomm, and y) serves as a learning rate hyperparameter. The PSD and FSD are weighted by hyperparameters X > 0 and X (NG) 2 0. By solving (5) with the first-order approximation of the loss term ( + 50)= x (0) + T0 (olD( and (3), we have
0 t 0 1 (0)
(9)
with a realization of the approximate gradient (8)
Q
lp + pma) - (D(
Volo(0) =
Uug (10)
50 -1 (^p (1 I (NG). Fo) (o) (7)
where Q perturbation vectors uh E R 1,... Q are sampled from NN 1). The query consumption cost for (10) is Q one for (0) and Q for ( pug).
If P (NG) = 0. (7) reduces to ordinary gradient descent. Nat- ural gradient corresponds to when (NG) 0. A sufficiently large value of x (NG), c.g., x (NG) = 1, ensures that the ma- trix to be inverted is full rank, even the computed FIM is not full rank.
As discussed in Section 1, if the neural network has deep structure, the sampling strategy for perturbation vectors Ug from (O, I) is not the best way because it ignores the parameter correlation represented by the FIM. One way to mitigate the parameter correlation is to sample coordinate- wise perturbations with one-hot vectors
The term (O) in (7) is the gradient vector for the loss function with respect to the parameters, and typically com- puted by backpropagation. However, when neural networks are implemented directly in hardware, we cannot use back- propagation and need to rely on a black-box method. In this paper, we compute approximate gradient vectors by ZO optimization explained in the next subsection.
U, - : [0...., .,, (1 entry). .OT R
(11)
where indices ng. q = 1,..., Q are sampled from the set (1....,N) without replacement. Indeed, the coordinate- wise sampling strategy is often more effective than that from NO,, I), as shown by the experimental results in Section 5, However, it consumes as many queries as N to change the entire parameter elements because there is only one non- zero element the perturbation vector.
2.3. Zeroth-Order (ZO) Optimization
zo optimization is a black-box optimization method for function (0) that we do not have full access to. Specifi- cally, we can query a function value (f), but we cannot
3

---

Natural Perturbations for Black-box Training of Neural Networks by Zeroth-Orde Optimization
3. Natural Perturbations
Ap O
1000
Ap
Aiming to solve the two issues just mentioned, namely miti- gating the parameter correlation and having multiple non- zero elements in perturbation vector, we propose novel strategy that samples natural perturbations.
Entropy
Ap
10
800
600
3.1. Criterion and Main Result
200
500
10
100
Expected PSD
Expected FSD
We consider that a good sampling strategy for ZO optimiza- tion is somehow maximize the entropy of the distribution so that the sampled perturbations explore widely as pos- sible (Figure 2). To simplify the discussion, we restrict the distributions to N-dimensional multivariate normal distribu- tions (0, Σ) with an arbitrary positive definite covariance matrix Σ E N.Nx xN Then, the entropy of random vectors u drawn from (0, Σ) is given as
Figure 3. Experimental examples on the relations among the en- tropy, the expected PSD, and the expected FSD.
as the optimal Σ that minimizes C(E).
From (13) and (18), understand that the existing sam- pling strategy from (O, I) is special case with Ap 1 and = and takes into account the expected PSD (14) but not the expected FSD (15). In contrast, our proposed sampling strategy takes into account the expected FSD as well by setting AF > 0.
h( h(E)=
1. In p())
1 NN (n + det E + N].
(12)
2
Analogously to (5), the sampling strategy for natural per- turbations u ~ (0, Σ) is formulated as minimizing the criterion
3.2. Metrics
To see how well the term A in (18) works with Af >> 0, let us experimentally investigate the relations among the three terms in the criterion (13), namely the entropy (12), the expected PSD (14), and the expected FSD (15).
Ap Eu [2122 +Ap Bu [u)) (13)
(())== + 2
where the expectation is written concisely as E.[-1 Eu-N((o.)) [-] The first term is the negative entropy. The second term with a weight hyperparameter Ap > 0 is the expected PSD, and the third term with a weight hyperpa- rameter X 2 0 is the expected FSD.
We trained small-size CNN having N 816 parameters with the MNIST handwritten digits (LeCun & Cortes, 2010), We stopped the training at the 5-th epoch to see a situation on the way (the test accuracy was still 0.662). We examined three values for AR as shown by colors/styles in Figure 3. For Ap, we examined various values ranging from to 5 that the tendencies can be observed visually with many dots. Note that the values of Xp are not visible in Figure 3, For each pair of X and Xp values, we computed Σ as (18) and sampled Q = 20 perturbations uy from (0, E). The expected PSD (14) and FSD (15) were actually calculated by the averages over Q perturbations:
Let us derive the covariance matrix that minimizes the crite- rion (13). The last two terms, without the weight hyperpa- rameters, can be written as
1 str(Eu (uul)) tr(()), 2
Eu [u 2
(14)
2
(3)
Eu (ulk((u)]
tr FL [uu] II)
tr (F
(15)
2
} E. [1
1
because Eu "u T E by definition. By ignoring constant terms in (12) that do not depend on Σ, (13) becomes
2Q q=1
Utg
2
(19)
11 Q
C(E) - - det Σ +
1
A S/ 2
ir(E) + X tr tr(Fo)). (16)
BulEo(u) ~
2Q Ug
2
T
F Fou
(20)
2
The gradient matrix with respect to E is given by
We observe the followings in Figure 3. The existing sam- pling strategy with X = attained the largest entropy under (17) the same expected PSD (see left hand plot vertically). How- ever, this was at a cost with the largest expected FSD for attaining the same entropy among the three XP values (see the right hand plot horizontally). Our sampling strategy for (18) natural perturbations with Xr > 0 (blue and green symbols),
OC(2) iΣ
1 シー
dp 2
d Fe.
2
Setting this to a zero matrix gives
Σ (Ap. I AF Fo)
4

---

Natural Perturbations for Black-box Training of Neural Networks by Zeroth-Order Optimization
on the other hand, reduced the expected FSD for attaining the same entropy (see the right hand plot horizontally) by paying a little cost of reducing the entropy (see left hand plot vertically) under the same expected PSD.
second issue is managed by partitioning the parameters into small blocks, explained in Section 4.2. But let start this section with the FIM computation, assuming that the number N of parameters is not so large.
Too large an FSD) leads to unstable training because the probability distribution conditioned by the neural network changes drastically. Natural perturbations as well as natural gradient prevent such situations.
4.1. FIM Computation
The derived result (18) for sampling natural perturbations requires to compute the FIM Fg as in the case of natural gradient. If we are allowed to perform backpropagation, there are ways (Dangel et al., 2020; Martens, 2020) to ap- proximately compute the FIM efficiently. However, in our black-box context, we need to develop another practical way to compute the FIM, this subsection proposes.
3.3. Theoretical Property
This subsection shows the approximation error bound of the 70 gradient approximation
((NP) LD (0) = (o.E)
(D + pu)- (0) u
The FIM Fe defined in (4) can be expressed (Park et al., 2000; Martens, 2020) as
11
(21)
Fe Es J y J we y f(m,0)) E ENNN
(25)
by natural perturbations u ~ NO Σ) with E being (18), to the natural gradient
with a collection of Jacobian matrices
(NG) (0) (Ap (2P
.ING).I+
(NG), Fo) I+ x
(o)
By 0f 0) Jyo
ae =
ae
ERMXN
(26)
(22)
and collection of the FIMs with respect to the output
extracted from (7).
F == E Bxppl(sl) V p(=ly) Vylnp(zlu)] ER MxM
Assumption 3.1. &D (0) is L-smooth, i.e.
(27)
1o(0+pu pm) < (0) + (lD( (Hu)) - 11 (23)
4.1.1. WHITE-BOX OUTPUT FIM COMPUTATION
for any 0 E IRN, u E ERN, and > 0.
The computation of F, can be performed a white-box manner because we have complete information on the prob- ability distribution p( y) used at the output (see Figure 1).
Theorem 3.2. When we assume Xp X Ap, X (NG)_ Xx
and Assumption 3.1, the differencc between the ZO gradient approximation by natural perturbations and the natural gradient is bounded by
When
multivariate standard normal distribution as p(z y) for regression task, the output FIM is simply given as = with an identity matrix (Malagò & Pistone, 2015). When we use a categorical distribution (a multino- mial distribution for a single observation) as p( (1y) with logits (g)m, m = 1,..., .,, for a classification task, the output FIM can be computed (Sawada et al., 2024) by
A ((NP) ED(
(NG) -
V(NGi VINC)ED(00
nl.
3 + N
3/2
<
2
Ap
(24)
The proof is shown in Appendix A.
F = Ex(=1y) 1nn(2/np//11 Inp(2/ Inp(lly)) (28)
Therefore, the ZO gradient approximation by natural per- turbations well approximates the natural gradient as long as the smoothing hyperparameter ja is small enough and the PSD weight Ap is not very small. We actually set 0.00.0 and Ap 1 in the experiments reported in Section 5.2.
xET
00...................... 0, 1, is a set of where T = {11 0, 0.
all possible outcomes, and
V In p( (y) = z softmax())
(29)
4. Method for ZO Optimization
[softmar(y))
exp((y)m)
(30)
M A exp((y]k)
To practically use natural perturbutions for 70 optimiza- tion of neural networks with many parameters, we need to overcome two related issues. The first is how to compute the FIM Fo in a black-box manner. The second is then how to avoid the inverse (18) of a big matrix including Fo. The
4.1.2. BLACK-Boo JACOBIAN COMPUTATION
The computation of the Jacobian matrices Jye should be performed in a black-box manner. We adopt column-wise
5

---

Natural Perturbations for Black-box Training of Neural Networks by Zeroth-Order Optimization
U1
222
U/3
U4
Ug
4.2.2. BLOCK DIAGONAL COVARIANCE MATRIX
E
As a consequence of block coordinate perturbations, we are allowed to make the covariance matrix Σ block diagonal, whose blocks are covariance matrices Σs, b I,..., B of small size No. x N₂ defined as
Σ
Σ3
Figure Block coordinate perturbations when 3 and Q Colored partitioned vectors are sampled using Eg and white parti- tioned vectors are filled with zero.
Σg == (Ap Ap Eg(s))
(34)
Here, the FIM also becomes block diagonal with blocks Fom. whose definition differs slightly from (4):
(parameter-wise) computation
g == Ex Ez [
0:0) In po x>) Vet In po & x>) ']]
(35)
Jyo = [oy....... SyN].
(31)
Its computational procedure similar to that based on (25):
and each column is computed by evaluating function values for multivariate difference quotients
F F = IE J your F yor
FyJwors
(36)
The computation of Fy is the w=f(x,0)
those deseribed in
öyn f(x, 0 + pen) f(x,0) E R
Section 4.1.1. The computation of your is similar to (31):
(32)
J y01
|oy (b)
NyN R AxN.
(b)
(37)
with coordinate-wist perturbations using one-hot vectors en = ... 1 (n-th entry)...., E , n
5y! = f(x,0 0 + uen - f(x,00 0)
R
(38)
Assuming that f(x 0) is already evaluated, the query con- sumption cost is N for the computation of yyo. This cost is large for a large number N of parameters. We will explain how to reduce the query cost in the rest of Section 4.
( [O..... (n'th entry), 0JT R
(39)
with n' E N
4.2. Partitioning Parameters into Small Blocks
4.3. Overall Procedure
When the number of parameters N is large, the inverse computation (18) for the covariance matrix E is practically infeasible. To overcome this issue, we adopt a block coordi- nate approach (Cai et al., 2021; Zhang et al., 2024). Figure 4 shows examples of block coordinate perturbations, where the block coordinate nature adopted not only for sampling perturbations but also for computing the covariance matrix.
Let us summarize aforementioned techniques as Algo- rithm 2, which derived from Algorithm 1. The key opera- tions are in lines 13 and 17, which compute the covariance matrices Eg and sample natural perturbations (0, Es). The matrices Eg are initialized as identity matri- ces in line 4, and eventually updated in line 13, depending on which index b is sampled in line 9.
(*) from
What we need to take care if the cost of ZO queries. In line 10, the query cost to compute the Jacobian J y and consequently Σg, is Ng. In line 20, the additional query cost to compute the approximate gradient is Q. To achieve effective black-box local search with fixed budget for total queries, we should consume many queries as possible for the approximate gradient. Therefore, we reduce the update frequency of Σ, by introducing a hyperparameter Tud > 1 in line We have experimentally confirmed in Section 5.3.5 that Tua 100 is appropriate.
4.2. BLOCK COORDINATE PERTURBATIONS
Let Nmax be the maximum number of parameters allowed for each block. We partition a parameter vector 0 E R into small blocks @(b), b = 1...., .....,, B, so that
(1))
( E ERR and N₂ S Nmax- (33)
=
((B)
For parameter vector 0, perturbations uy E RN q ..... Q, are made in block coordinate manner, where only one block (b) E N corresponding to (b)) is allowed to have non-zero elements. The block indices are sampled
5. Experiments
This section reports the experimental results to show the superiority of the proposed method over the existing ones. We coded our programs with PoTch (Paszke et al., 2019), and ran them on an NVIDIA RTX A6000 (48 GB).
with replacement B- < Q, and without replacement if B 2 Q to totally perturb as many parameters as possible.
6

---

Natural Perturbations for Black-box Training of Neural Networks by Zeroth-Order Optimization
Algorithm 2 ZO optimization for training neural network with block coordinate natural perturbations
Optical Neural Network (ONN)
Parameler vector 0
Output vector y
Absolute
Unitary matrix
Diagonal matrix
Unilary
1: Input: training dataset D., = {zx, }) hyperparameters Q, Nmax, Tud, Ap, Ap
matrix
MSE loss
2: Initialize the parameter vector 0
T Complex random ingut vector
3: Partition 0 into blocks {0(1)
0 [ according to (33)
Fixed complex
Absolute
4: Initialize Σ. = I for b = 1...,, B
matrix
Target vector t.
5: while not converged. in 5-th iteration do
6: Sample mini-batch 2 from Di.
Figure 5. Equalization task
7: Evaluate loss (0) by (1)
8: if (r mod Tnd) = then
9:
Sample b ~ (1,...,7)) B}
The Copying memory task tests how well an RNN remem- bers data seen many time steps before, An example of input and target output sequences is
10:
Compute J yo(t) by (37)
11:
Compute F3 by (28) or Set F,
12:
Compute F Fa()) by (36)
13:
Compute Nσ by (34)
Input: 38612
14:
end if
15:
for q
1,. Q do
Target:
38612
16:
Sample {1, f1...., B}
17:
Sample perturbation u from (0, Es) Set 14g = (O...., (b)
where 38612 is the data to remember, with possible alpha- bet symbols from 1 to 8. And and are special symbols meaning 'blank' and 'start', respectively. In total, the RNN has a 10-dimensional output. The details are described in (Arjovsky al., 2016; Lezcano-Casado & Martinez-Rubie 2019). The task is particularly well tested when the RNN's s hidden unit is realized by a unitary matrix, where the abso- lute values of all eigenvalues are one. In our experiment, the data length and the time steps to 'start' after the data were 10 and 100, respectively. The size of the unitary matrix used in the hidden unit was 32 x 32.
18:
19:
end for
20:
Compute the approximate gradient (0) by (10) with
uy q = I..... Q computed above.
21:
Update the paramcter vector 0 by (9)
22:
end while
5.1. Datasets/Tasks and Architectures
The first two columns of Table 1 list the five datasets/tasks we examined and the corresponding neural network archi- tectures with N parameters. We used a CNN for MNIST (LeCun & Cortes, 2010) and FashionMNIST (Xiao et al., 2017), and MLP-Mixer (Tolstikhin et al., 2021) for CI- FAR10 (Krizhevsky, 2009). For these datasets, the comput- ing elements are parameterized by matrices in the most general cases. For Equalization and Copying memory tasks, on the other hand, we used a hardware specific ar- chitecture based on Mach-Zehnder interferometers (MZIs) (Reck& & Zeilinger, 1994; Clements et al., 2016) assuming optical neural networks (ONNs). The MZI parameteriza- tion is completely different from that of matrix: a linear module realizes a unitary matrix and has a deep structure (see Appendix C for the details), which leads where many parameters are involved in path from an input element to an output element even in single linear module.
We generated the training and test datasets for the Equal- ization and Copying memory tasks with our own programs. As in the case of MNIST and FashionMNIST, the number of samples in the training and test datasets were 60000 and 10000, respectively.
5.2. Methods and Overall Results
We compared three ZO optimization methods: ZO-I and 70-co are the existing methods, and ZO-NP is our proposed method using natural perturbations. We treat that ZO-1 is special case of ZO-NP with Ap = and A = 0 (34), and lines from to 14 are skipped in Algorithm 2. In ZO-co, perturbation vectors are sampled as coordinate-wis. from set of one-hot vectors. The number Q of perturbation vectors were set for each task as the sixth column shows. The smoothing hyperparameter was set as = 0.001.
situation
The Equalization task is a kind of regression task. As Figure shows, the ONN on the upper path tries to realize given fixed matrix on the lower path. The ONN was in form of the singular value decomposition UDVH, where U and V are unitary matrices and D is diagonal matrix. The absolute values of the complex signals were obtained at the output to convert the optical signals to electrical signals by photodetectors. The loss function was the mean squared error (MSE) loss. In the experiment, the dimensionality of the matrix was set to 16.
Instead of the stochastic gradient descent form (9) with ap- proximate gradients, we used the Adam optimizer (Kingma & Ba, 2014) with approximate gradients. The size of mini- batch D was 100 for all tasks. The learning rate (Ir) was appropriately set for each task as the seventh column of Table shows. The results with varying learning rates are summarized in Appendix D.I.
Regarding ZO-I and ZO-NP using the block coordinate per- turbations explained in Section. 4.2.1, 1, we set the maximum
7

---

Natural Perturbations for Black-box Training of Neural Networks by Zeroth-Order Optimization
Table 1. Overview of our experiments and the test accuracies (mean + standard deviation of five runs). For Equalization, the test R²'s (coefficients of determination) are shown instead, whose best possible value is 1.0 as the test accuracy. The bold values indicate that they are the best and statistically different from the others according to the one-sided Mann- Whitney U test at significance level of p 0.008.
Hyperparameters
Test accuracy (1)
dataset/task
architecture
N
Mmxx
B
Q
Ir
Ax
ZO-I
ZO-co
ZO-NP
MNIST
CNN (matrix)
2586
431
6
20
0.0005
100
0.961
#0.004
0.966
=0.001
0.978
+0.002
FNShionMNIST
CNN (matrix)
2586
431
6
20
0.0005
100
0.796
10.013
0.814
10.005
0.858 10.004
Equalization
FeedForward (MZI)
560
280
2
20
0.005
10
0.944
10.007
0.944
10.008
0.993 100003
Copying memory
RNN (MZI)
3168
453
7
20
0.0001
10
0,965
10.026
0.985
10.002
0.993 1..003
CIFARIO
MLP-mixer (matrix)
33642
510
66
200
0.001
100
0.595 +0.002
0.601 #0.004
0.625 +..004
number Nmax of parameters allowed for each block, and consequently had the number B of blocks as shown in the fourth and fifth columns of Table 1. For ZO-NP, the FSD weight hyperparameter Xp was set appropriately for each task as shown in the eighth column. The other hyperparam- eters were set as Ap and Tud 100 for all tasks.
Training loss (1)
Test accuracy (1)
0.625
Z0-1
1.4
20
0.600
ZO.NP
1.2
0.575
0.550
1.0
Z0-1
0.225
70-co
The existing methods ZO-I and ZO-co completed 1000 epochs for CIFARIO and 100 epochs for the other four tasks. However, ZO-NP finished with fewer epochs than these numbers under the same query budget. This was due to the fact that ZO-NP consumed extra queries for the black-box Jacobian computation.
ZO-NP
0.8
0.200
250
500 Epoch
750
1000
0
10000
20000
30000
40000
Elapsed time (seconds)
Figure 6. Convergence behavior for CIFARIO
0.88
ZO-1
20-co
Table shows the overall results. The proposed method ZO-NP outperformed the existing ones with statistical sig- nificance in all cases. Also, ZO-NP outperformed CMA-ES (Hansen, 2016; Hansen et al., 2019), which is another black- box optimization method, as shown in Appendix D.2.
Test accuracy
0.84
Z0-NP
0.82
0.80
10P
101
102
5.3. Discussion with Detailed Results
Nasx
1. CONVERGENCE BELIAIIR
Figure 7. FashionMNIST test accuracies by varying the maximum block size Nmax for ZO-I and ZO-NP. The size for ZO-co is only valid at Nuaa 10 but is stretched horizontally for easy comparison. Shaded arcas show one standard deviation over five independent runs.
Figure shows the convergence behavior for CIFARIO (see Appendix D.3 for the other tasks). The left plot shows how the training loss decreased as the number of epochs increased. ZO-NP completed fewer epochs (975) than the other two (1000) with the same query budget of 1.005 x 1 The right plot shows how the test accuracies improved along the elapsed time. Although ZO-NP had computational overhead over the other two, it was worth paying because ZO-NP outperformed the other two even with the same elapsed time.
under Nmax - -N - because the perturbation vectors were one-hot vectors (with =1 non-zero element) in all methods. The plot shows this empirically at Nuax 10 = 1. As we increased N the performance of ZO-NP steadily increased. This was due to two effects. The first was to increase the number of changing parameters per iteration. The second was to mitigate the parameter correlation repre- sented by the FIM F Farsy in (35). While the proposed method 7O-NP did both, 70-co did not do the first, and 70-I did the first but not the second.
5.3.2. EFFECT OF BLOCK SIZE
Figure 7 compares 70-co with Z0-I and ZO-NP with vary- ing the maximum block size Nmax. To make the compari- son, we slightly modified Algorithm 2 as inserting
5.3.3. COMPUTATIONAL OVERHEAD OF 70-NP
u (b) /oNo/// 12) Z
(40)
Table shows the average elapsed times per epoch and the memory footprints for the three methods. Looking at the left numbers, we observe that the elapsed time overhead
which made the norm of (b) be VN, after line 17. Then the behavior of 70-co and the other two became the same
8

---

Natural Perturbations for Black-box Training of Neural Networks by Zeroth-Order Optimization
Table The average elapsed times in seconds per epoch (left) and the memory footprints in gigabytes (right) for the three methods, under the same experimental conditions shown in Table 1.
Table 4, Second to fourth rows: FashionMNIST test accuracies (mean of five runs) by varying the number Q of perturbation vec- tors. Fifth row: query budget determined by the number queries that ZO-I and ZO-co consumed for 100 epochs. Sixth row: the number of epochs allowed for ZO-NP with the same budget.
dataset/task
Zo-1
ZO-co
ZO-NP
MNIST
4.74
0.57
4.52
0.57
5,04
2.74
FaSHionMNIST
4.66
0.57
4.43
0.57
5.04
2.74
Q
2 5
10
20
50
100
Equalization
3.25
0.04
3.20
0.04
3.36
0.05
ZO-1
0.717
0.736
0.763
0.782
0.796
0.816
0.830
Copying memory
84.89
0.36
84.22
0.36
90.89
2.57
20-co
0.714
0.746
0.773
0.798
0.814
0.833
0.845
CIFARIO
43.10
1.92
40.31
1.92
45.79
3.83
ZO-NP
0,714
0.776
0.824
0.841
0.858
0.865
0.873
budget (x 10%)
0.12
0.18
0.36
0.66
1.26
3.06
6.06
ZO-NP epochs
31
41
58
71
82
92
95
Table MNIST memory footprints in gigabytes for the
1.00
1,00
ZO-NP settings of Figure 7.
0.98
0.98
Nmax
8
16
32
64
124
236
431
memory
0.57
0.57 0.57
0.57
0.59
0.94
1.60
2.74
0.96
0.94
0.94
0.92
0.92
MNIIT
of ZO-NP over the two existing methods was up to around 10 %. which was offset by the efficient training as already shown by the right plot of Figure 6. Looking at the right numbers, we observe that the memory footprint overhead of ZO-NP over the two existing methods was substantial for the tasks except Equalization where the maximum block size Nmax was not large. We can reduce the overhead to negligible amount by decreasing Nmax shown in Table 3. Together with Figure 7, we understand that ZO-NP trades off the test accuracy and the memory overhead.
Equalization
0.90
0.90
Copying memory
0
10 20 100
10
50
100 200 500 1000
FSD weight Xy
Update frequency Tie
Figure 8, Left: test accuracies obtained by ZO-1 (Ar 0) and ZO-NP with varying the FSD hyperparameter. Right: those by Zo- NP with varying the update frequency hyperparameter. Vertical bars show one standard deviation over three independent runs.
Both hyperparameters had wide ranges of appropriate set- tings that outperformed the 70-I results, although the ap- propriate ranges for Xp were different depending on the task and we actually customized A as Table I shows. Regard- ing the update frequency, consider that Tua 100 is an appropriate setting working generally.
Appendix D.4 reports the computational overhead of ZO-NP for an MLP-mixer with N 1, 706, 762 parameters, which is much larger than the MLP-mixer reported in the last row of Table 1. We observe that the proposed method scales to some extent, but network with one million parameters might be practical limitation.
6. Conclusion
5.3.4. VARIOUS NUMBERS Q OF PERTURBATIONS
We have newly proposed an efficient sampling strategy for ZO optimization, where perturbations u are sampled from (0, Σ) with covariance matrix Σ designed by regular- izing not only the expected PSD (14) but also the expected FSD (15). We call such sampled u natural perturbations since the regularization inherits from the concept of natural gradient. We then have proposed a new 2O optimization method based on the sampling strategy, where the block coordinate approach allows us to compute the covariance matrix efficiently. Experimental results show that the pro- posed method elearly outperformed the existing ones for variety of datasets, tasks, and neural network architectures.
Table 4 shows FaShionMNIST test accuracies with various numbers Q of perturbations. The bold values indicate that they are the best and statistically different from the others according to the one-sided Mann-Whitme U test at a sig- nificance level of p = 0.004. We observe that the proposed method ZO-NP consistently outperformed the other two methods, except in the extreme case (Q = 1), where the number of epochs allowed for ZO-NP was small since the relative query consumption cost for the black-box Jacobian computation was large.
5.3.5. ROBUSTNESS TO HYPERPARAMETER SETTINGS
Future work includes the development of a much stronger approximation of the FIM than making it block diagonal. This would enable the method to scale to networks with more than millions of parameters, and to be applied ZO- based large language model (LLM) fine- fine-tuning (Zhang et al., 2024).
Figure 8 shows the test accuracies for three tasks by ZO-NP with varying hyperparameters, namely the FSD weight XP on the left and the update frequency Tua of Σ, on the right. The leftmost results with Ap= = correspond to those of ZO-I with fewer epochs (82, 88, and 82 for the three tasks).
9

---

Natural Perturbations for Black-box Training of Neural Networks by Zeroth-Order Optimization
Impact Statement
Cai, H., Lou, Y., McKenzie, D., and Yin, W. A zeroth- order block coordinate descent algorithm for huge-scale black-box optimization. In Proceedings of the Inter- national Conference on Machine Learning (ICML), PP. 1 1193-1203, 2021.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Chen, A., Zhang, Y., Jia, J., Diffenderfer, J., Parasyris, K., Liu, J.. Zhang. Y., Zhang, Z., Kailkhura, B., and Liu, S. DeepZero: Scaling up zeroth-order optimization for deep model training. In Proceedings of the International Conference on Learning Representations (ICLR), 2024.
References
Aguirre, F., Sebastian, A., Le Gallo, M., Song, W., Wang.
T., Yang, J. J., Lu, W., Chang, M.-F., lelmini, D., Yang, Y., et al. Hardware implementation of memristor-based artificial neural networks. Nature Communications, 15 (1):1974, 2024.
Chen, M. K., Liu, X., Sun, Y., and Tsai, D. P. Artificial intelligence in meta-optics. Chemical Reviews, 122(19): 15356-15413, 2022.
Amari, S. Backpropagation and stochastic gradient descent method. Neurocomputing, 144-5):18--196 1993.
Clements, W. R., Humphreys, P. C., Metcalf, B. J., Koltham- mer, W. S., and Walmsley, I. A. Optimal design for universal multiport interferometers. Optica, 3(12): 1460- 1465, 2016
Amari, S. Natural gradient works efficiently in learning. Neural Computation, 10(2):251-2777 1998.
Cong, G., Yamamoto, N., Inoue, T., Maegami, Y., Ohno, M., Kita, S., Namiki, S., and Yamada, K. On-chip bac- terial foraging training in silicon photonic circuits for projection-enablee nonlinear classification. Nature Com- munications, (3(1)33611 2022.
Arjovsky, M., Shah, A., and Bengio, Y. Unitary evolution recurrent neural networks. In Proceedings of the Inter- national Conference on Machine Learning (ICML), pp- 1120-1128, 2016.
Dangel, F., Kunstner, F., and Hennig, P. BackPACK: Pack- ing more into backprop. Proceedings of the Interna- tional Conference on Learning Representations (ICLR), 2020.
Ashtiani, F., Geers, A. J., and Aflatouni, F. An on-chip photonic deep neural network for image classification. Nature, 606:501-506, 2022.
Bae, J., Vicol, P., HaoChen, J. Z., and Grosse, R. B. Amor- tized proximal optimization. Advances in Neural Infor- mation Processing Systems (NeurIPS). 35:8982-8997, 2022.
Duchi, J. C., Jordan, M. I., Wainwright, M. J., and Wibisono, A. Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Transactions on Information Theory, 61)))) 2015.
Bandyopadhyay, S., Sludds, A., Krastanov, S., Hamerly, R., Harris, N., Bunandar, D., Streshinsky, M., Hochberg, M., and Englund, D. Single chip photonic deep neu- ral network with accelerated training. arXiv preprint NrXii:2208.0162.0 2022.
Fang, M. Y.-S., Manipatruni, S., Wierzynski, C., Khosrow- shahi, A., and DeWeese, M. R. Design of optical neural networks with component imprecisions. Optical Express, 27(10): 4000-,49909, 2019.
Fazel, M., Ge, R., Kakade, S., and Mesbahi, M. Global convergence of policy gradient methods for the linear quadratic regulator. In Proceedings of the International Conference on Machine Learning (ICML), pp. 1467- 1476, 2018
Banerjee, S., Nikdast, M., and Chakrabarty, K. Characteriz- ing coherent integrated photonic neural networks under imperfections. Journal of Lightwave Technology, 41(5): 1479, 2023. doi: 10.1109/11120022:119356
Gu, J., Zhao, Z., Feng, C., Li, W., Chen, R. T., and Pan, Z. FLOPS: Efficient on-chip learning for optical neural networks through stochastic zeroth-order optimization. In Proceedings of the 57th ACM/EDAC//EHH Design Automation Conference, 2020.
Benzing, F. Gradient descent on neurons and its link to approximate second-order optimization. In Proceedings of the International Conference on Machine Learning (ICML), pp. 1817-1853, 2022.
Berahas, A. S., Cao, I.,, Choromanski, K., and Scheinberg, K. A theoretical and empirical comparison of gradient approximations derivative- free optimization. Foun- dations of Computational Mathematics, 22(2):077-560, 2022.
Gu, J., Feng, C.,, Zhao, Z., Ying, 7.,, Chen, R. T., and Pan, D. Z. Efficient on-chip learning for optical neural net- works through power-aware aware sparse zeroth-order optimiza- tion. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 7583-7591, 2021.
10

---

Natural Perturbations for Black-box Training of Neural Networks by Zeroth-Order Optimization
Hansen, N. The CMA evolution strategy: A tutorial. arXiv 2016.
Malagò, L. and Pistone, G. Information geometry of the Gaussian distribution in view of stochastic optimization. In Proceedings of the ACM Conference Foundations of Genetic Algorithms XIlI, pp. 150-162, 2015.
preprint orxiv:
Hansen, N., Akimoto, Y., and Baudis, P. CMA-ES/pyema Github. Zenodo, D01::00.5281/eceood22233333 Febru- 5281/
ary 2019. URL attpss:/ddon
Martens, J. Second-orde optimization for neural networks. University of Toronto (Canada), 2016.
zenodo... 2559634.
Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. arXiv preprint urXiv::412.000 2014.
Martens, J. New insights and perspectives the natural gradient method. The Journal of Machine Learning Re- search, 21(1):5776-585 2020.
Krizhevsky, A.
Learning multiple layers of fea- tures from tiny images. TR-2009, University of Toronto, 2009. URL
Technical Report
Martens, J. and Grosse, R. Optimizing neural networks with Kronecker-factoree approximate curvature. In Pro- ceedings of the International Conference on Machine 2015.
https: //t:://wwwww htww://wwcc////o////co wtwp:w.cs..oooooo. www.nto.oooo..oooo... edunkkrzz Learning-features 2009---00------ pdf.
Learning (ICML), pp.
Kunstner, F., Hennig, P., and Balles, L. Limitations of the empirical Fisher approximation for natural gradient descent. Advances in Neural Information Processing Systems (NeurIPS), 32, 2019.
Nesterov, Y. and Spokoiny, V. Random gradient-free mini- mization of convex functions. Foundations of Computa- tional Mathematics, 17(2):277-566, 2017.
LeCun, Y. and Cortes, C. MNIST handwritten digit database, 2010. URL http://yann, lecun. com/ exdb/mnist.
Park, H., Amari, S., and Fukumizu, K. Adaptive natural gra- dient learning algorithms for various stochastic models. Neural Networks, 13(7):755-764, 2000.
LeCun, Y., Bengio, Y., and Hinton, G. Deep learn- ing. Nature, 521:436-444, 2015. doi: 10.1038/ nature14539. URL https:: http:://ddoioooo http:////0...rr11.00000000 nature14539.
Pascanu, R. and Bengio, Y. Revisiting natural gradient for deep networks. arXiv preprint arXiv:1301.3884 2013.
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J.,
Cezcano-Casade M. and Martmez-Rubio, D. Cheap orthogonal constraints in neural networks: simple parametrization of the orthogonal and unitary group. In Proceedings of the International Conference on Machine Learning (ICML), pp. 17994-803,, 2019.
Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, I.,, al. Pytorch: imperative style, high-performance deep learning library. Advances in Neural Information Processing Systems (NeurIPS), 32, 2019.
Petersen, K. and Pedersen, M. The matrix cookbook. Tech- nical University of Denmark, 7(15):510, 2008
Li, C., Belkin, D., Li, Y., Yan, P., Hu, M., Ge, N., Jiang, H., Montgomery, E., Lin, P., Wang, Z., et al. Efficient and self- aelf-adeptive in-situ learning in multilayer memristor neural networks. Nature Communications, 91):2385, 2018.
Reck, M. and Zeilinger, A. Experimental realization of any discrete unitary operator. Phys. Rev. Lett., 73(1):58-61 61, 1994.
Lian, X., Zhang, H., Hsich, C.-J,, Huang, Y., and Liu, J. A comprehensive linear speedup analysis for asynchronous stochastic parallel optimization from zeroth-order first- order. Advances in Neural Information Processing Sys- tems (NeurIPS), 29,229, 2016.
Rumelhart, E., Hinton, G. E., and Williams, R. J. Learn- ing representations by pack-propagating errors. Nature, (2336088):533-536 1986.
Sawada, H., Aoyama, K., and Ikeda, K. Zeroth-order opti- mization of optical neural networks with linear combina- tion natural gradient and calibrated model. In Proceedings of the 61st ACM/IEEE Design Automation Conference, 2024.
Liu, S., Chen, P.-... Kailkhura, B., Zhang, G., Hero III, A. O., and Varshney, P. K. A primer zeroth-order optimization in signal processing and machine learning: Principals, recent advances, and applications. IEEE Sig- nal Processing Magazine, 3755):3354, 2020.
Sawada, H., Aoyama, K., and Notomi, M. Layered- parameter perturbation for zeroth-order optimization of optical neural networks. In Proceedings of the AAAI Con- ference on Artificial Intelligence, volume 39, pp. 20292- 20301, 2025.
Lupo, A., Picco, E., Zajnulina, M., and Massar, S. Deep pho- tonic reservoir computer based on frequency multiplexing with fully analog connection between layers. Optica, 10 (11):1477- 1485, 2023.

---

Natural Perturbations for Black-box Training of Neural Networks by Zeroth-Order Optimization
Shen, Y., Harris, N. C., Skirlo, S., Prabhu, M., Baehr-Jones, T., Hochberg, M., Sun, X., Zhao, S., Larochelle, H., En- glund, D., and Soljačié, M. Deep learning with coherent nanophotonic circuits. Nature Photonics, 11:441-444 2017.
Tolstikhin, I., Houlsby, N., Kolesnikov, A., Beyer, I.., Zhai, X.. Unterthiner, T., Yung, J., Steiner, A., Keysers, D., Uszkoreit, J., et al. MiP-mixer: An all-MLP architecture for vision. Advances in Neural Information Processing Systems (NeurIPS), 34:24261-24272, 2021.
Wierstra, D., Schaul, T., Glasmachers, T., Sun, Y., Peters, J., and Schmidhuber, J. Natural evolution strategies. The Journal of Machine Learning Research, 15(1):999-980, 2014.
Xiao, H., Rasul, K., and Vollgraf, R. Fashion-MNIS. novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv:100..07744 2017.
Zhang, H., Thompson, Gu, M., Jiang, X., Cai, H.,, Liu, P., Shi, Y., Zhang, Y., Karim, M., Lo, G., Luo, X., Dong. B., Kwek, I.,, and Liu, A. Efficient on-chip training of optical neural networks using genetic algorithm. ACS Photonics, 86)):6662-177) 1672, 2021.
Zhang, T., Wang. J., Dan, Y., Lanqiu, Y., Dai, J., Han, X., Sun, X., and Xu, K. Efficient training and design of photonic neural network through neuroevolution. Optics Express, 27(26):3715033716 2019.
Zhang, Y., Li, P., Hong, J., Li, J., Zhang, Y., Zheng, W., Chen, P.-Y., Lee, J. D., Yin, W. Hong, M., et al. Re- visiting zeroth-orde order optimization for memory memory-effccient efficient LLM fine-tuning: A benchmark. In Proceedings of the International Conference on Machine Learning (ICML), pp. 59173-59190, 2024.
Zhao, P., Chen, P.-Y., Wang. S., and Lin, X. Towards query- efficient black-box adversary with zeroth-order natural gradient descent. Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 6909-6916, 2020.
Zhou, H., Zhao, Y., Wang, X., Gao, D., Dong. J., and Zhang, X. Self-confguringg and reconfigurable silicon photonic signal processor. ACS Photonics, 733)7922-79,, 2020.
12

---

Natural Perturbations for Black-box Training of Neural Networks by Zeroth-Order Optimization
A. Proof of Theorem 3.2
When we assume Xp xp Ap, AF (NG) AF and Assumption 3.1, the difference between the ZO gradient approximation by natural perturbations and the natural gradient is bounded by
((N)) 1 -
(0(0)
pb /3
3/2
(41)
2 Ap
Proof. From the assumptions y (NG) Ap and Xo (NG)) = (22) can be written using (18) as
V [G) ( = VooD(())
(42)
Then, considering (0,)(0.E)) uu Σ as its definition, we have
V (NG) (0) = Eu- uuu" VolD(O) = Eu,V [uu Vol
(43)
The difference between 4 NP) (0) defined in (21) and the above, measured by the lo-norm, can be expressed
(0 - | (0)
Eu-N(o,
(p + vm) (0)
Eu--N(o |uu VolvvuVooooo VolD(
(44)
p
(p ( + )m)
(
EunA(o,
u u VolD(0))
(45)
"
Lp ( + nm)
(0) nm T Volp(0) u
(46)
(23)
L
E (o,
| 11
(47)
| 2
|E~N((
l1z
(48)
2
uL
Bun
[1/
[1/l2]]]
(49)
2
We have applied Assumption 3.1 in the transition from (46) to (47). Now, by generating w via a linear transformation // v with sampled v (O I), we have
nt
(NP) 0
(0) - V (NG) ez 0
<
Em-N(o.T)
To Ev
12
2
(50)
2
nT.
|>///]
Bo-Nio.
TT Ev [10112]
(51)
2
2
μL
|>\/||
|Eح| E. Fo-N
||
|000
(52)
where the matrix norm is the spectral norm and thus the maximum eigenvalue. From the structure (18) of E, we have
Σ 2 max (eig (E))= = max (ig (App I+ Ap (D.FF) F)) min (eig (Ap I+ dF Fo)) & Xp
(53)
from (Petersen & Pedersen, 2008) and similarly | S xpp1/2 For N-dimensional vectors v, we have
E 1 112 |11|||| (3++2)3/2
(54)
from Lemma 1 of (Nesterov & Spokoiny, 2017). Therefore,
0 (D))
(0))
PL 3 N 2 Xp
3/2
(55)
13

---

Natural Perturbations for Black-box Training of Neural Networks by Zeroth-Order Optimization
B. Differences between Natural perturbations and Natural evolution strategies
Natural evolution strategies (NES) (Wierstra et al., 2014) are a family of black-box optimization algorithms that use the natural gradient, and are closely related covariance matrix adaptation evolution strategy (CMA-ES) (Hansen, 2016; Hansen al., 2019). Since our proposed ZO optimization with natural perturbations and NES are both black-box optimization methods that use the Fisher information matrix (FIM), here clarify the differences between them in Table 5 in terms of the FIM. As the table shows, the definitions and usage of the FIMs are fundamentally different. Due to the size of the FIM, our proposed method using natural perturbations can be applied to larger problems with more parameters than NES.
Table 5. Differences between Natural perturbations and Natural evolution strategies (NES)
Natural perturbations
Natural evolution strategies (NES)
distributions that
FIM is computed for FIM is used for
sampling distribution
the neural network expresses
iteratively updating the parameters of the sampling distribution with small learning rate a natural gradient manner all kinds of parameters of sampling distribution,
directly the covariance matrix of the sampling distribution
neural network parameters, whose number is N, to be optimized
FIM of
e.g., mean and covariance matrix for multivariate normal distribution
(N + N x (N + N for multivariate normal distribution
size of FIM
N N
C. Optical neural network (ONN) based on Mach-Zehnder interferometers (MZIs)
This appendix explains an ONN based on MZIs, which we assumed in the experiments as described in 5.1.
Figure shows the structure. We used the Clements mesh (Clements et al., 2016) for linear module. It consists of layered array of MZIs colored light blue. An MZI consists of two pairs of phase shifters and beam splitters, whose functionalities shown in the 2 2 matrices. An MZI realizes 2 2 unitary matrix depending the settings of the phase parameters 0 colored in orange. The Clements mesh realizes unitary matrix of larger size by structurally combining multiple MZIs.
Linear module with parameters 0
Input vector T
Output vector y
PS: Phase shifter
Maach-Zehnder interferometer (MZI)
BS: Beam splitter
50
1
0
1
PS
BS
BS
V2
Figure 9. Optical neural network (ONN) based Mach-Zehnde interferometers (MZIs)
14

---

Natural Perturbations for Black-box Training of Neural Networks by Zeroth-Order Optimization
D. Additional Experimental Results
This appendix reports additional experimental results. The test accuracy values for the Equalization were actually computed by the test R (coefficients of determination), whose best possible value is 1.0 as the test accuracy.
D.I. Results with Various Learning Rates
The results reported in Section 5.3 were obtained by setting the learning rate (Ir) as shown in Table 1. Here, Figure shows the results with various learning rates for all tasks except CIFARIO. Specifically, we examined five learning rates for each task, where the third (middle) one corresponds to the setting reported in Section 5.3. We observe that ZO-NP consistently outperformed the other two methods with various learning rates, except for the extreme cases at both ends in the Copying memory task.
MNIST
FashionMNIST
Equalization
Copying memory
0.98
1.0
1.00
Text accuraty
0.90
0.9
0.94
0.50
0.95
0.82
0.8
70-1
0.90
+
ZO.NP
ZO-co
0.75
0.90
0.88
0.0001
0.0002 0,0006 0.001
0.002
0.0001 0.0002 0.0005 0.001 0.002 Learning rate (Ir)
0.001
0.002
0.005
0.01
0.02
26-05
5c-06
0.0001 O. 0.0002 0.0005
Learning rate (Ir)
Learning rabe (Ir)
Learning rate (Ir)
Figure 10. The effects of learning rate (Ir) on test accuracies for the MNIST, FashionMNIST, Equalization, and Copying memory tasks. Vertical bars show standard deviation over three independent runs.
D.2. Comparisons to CMA-ES
In addition to the comparison summary reported in Table here compare the results with covariance matrix adaptation evolution strategy CMA-ES (Hansen, 2016), which is well-known black-box optimization method. It computes covariance matrix using selected solutions from the population, in a fundamentally different way from ours Σ (18) and E, (34). For performing CMA-ES, we used a python package (Hansen et al., 2019). Since it was difficult for the CMA-ES python package to introduce the block coordinate approach used in ZO-1 and ZO-NP, we examined tasks with small numbers N of parameters, namely the MNIST and FashionMNIST dataset with the same CNN used in Section 3.2 (N 816) and the Equalization task (N 560). The initial standard deviation hyperparameter of CMA-FS was appropriately set to sigma0 0.005, sigma0 0.002, and sigma0 = 0.009 for the MNIST, FashionMNIST, and Equalization tasks, respectively. These numbers were chosen as the best out of six different values for each task. Figure 11 shows the results. The proposed method ZO-NP consistently outperformed the other three methods.
MNIST
FashionMNIST
Equalization lizaaizaioon
1.00
0.96
0.82
Z0-1
0.98
Zo-co
Test accuracy
0.94
0.50
0.96
ZO-NP
0.78
0.94
CMA-ES
0.92
0.92
0.76
0.90
0.90
0.74
Figure 11. Box plots for the test accuracies obtained by the four methods including CMA-ES. Each box shows the distribution of the results by five independent runs. The number of parameters were 816, 816, and 560 for the MNIST, FashionMNIST, and Equalization tasks, respectively.
15

---

Natural Perturbations for Black-box Training of Neural Networks by Zeroth-Order Optimization
D.3. Convergence Behavior
The convergence behavior for CIFARIO is reported in Section 5.3.1. Here, Figure 12 shows those for the other four tasks. The upper plots show that ZO-NP completed fewer epochs (82, 82, 88, and 82 for the four tasks) than the other methods (100, 100, 100, and 100 for the four tasks). This because the query budget was 1.26 x 10% and ZO-NP consumed extra queries for the black-box Jacobian computation. The lower plots show how the test accuracies improved along the elapsed time. The times of ZO-NP were shorter than those of the other two in most cases. The reason was that ZO-NP was allowed fewer epochs as described above and the computational overhead of ZO-NP over the other two methods was not large.
MNIST
FaSHI
Equalization
Copying memory
zo.co
0.8
Z0-co
0.8
20-co
0.8
Z0.co
ZO-NP
Z0-NP
20-NP
ZO-NP
0.3
0.7
Training
0.6
0.4
0.4
0.2
0.5
0.4
50
25
Epoch
Epoch
Epoch
Epoch
1.00
1.00
0.98
0.85
accuracy
0.96
0.95
0.95
0.94
0.82
20-1
0.85
0.85
0.70
0.90
ZO-NP
ZO-NP
0.80
Z0-NP
0.80
Z0-NP
200
400
200
400
0
100
200
300
2000
4000
6000
8000
Elapsed time (seconds)
Elapsed time (seconds)
Elapsed time (seconds)
Elapsed
time (secands)
Figure 12. Convergence behaviors for the MNIST, FashionMNIST, Equalization, and Copying memory tasks. Each column corresponds each task. Top and bottom rows correspond the training losses and the accuracies, respectively.
16

---

Natural Perturbations for Black-box Training of Neural Networks by Zeroth-Order Optimization
D.4. Computational costs for neural network with one million parameters
This appendix part shows the computational scalability of our proposed method ZO-NP for neural network with one million parameters, well its limitations.
The largest neural network reported in the main body is the MIP--iier with N = 33, 642 parameters, as shown at the last row of Table 1. Here, we report the computational costs of the three ZO methods applied to a much larger neural network. Specifically, for the CIFAR1O 10 task with the MLP-mixer, we increased the number of mixers from 3 to 12, the channel width from 32 to 256, and consequently the number N of parameters from 33,642 to 1.706, Table shows the computational cost of the enlarged MLP-mixer. We can observe the computational overhead of ZO-NP over ZO-I and ZO-co by looking the second to fourth rows. While the elapsed time (reported seconds/epoch) overhead of ZO-NP over ZO-co was 650.79- 393.84 56.95, which was less than 10% of 593.84, the memory footprint overhead was 31.10 12.10 19.00, which was considerable. We could reduce the memory footprint overhead by decreasing the maximum block size Nmax as shown in the last two rows. As tradeoff, however, this increased the number B of blocks and consequently the elapsed time in seconds per epoch.
Table The elapsed times in seconds per epoch and the memory footprints in gigabytes for the CIFAR10 task using the enlarged MI.P-mxxe with N 706, 762 parameters.
method
Nmax
B
seconds/epoch memory (GB)
70-I
512
3334
636.85
12.10
ZO-co
512
3334
593.84
12.10
ZO-NP
512
3334
650.79
31.10
ZO-NP
256
6668
693.11
16.55
ZO-NP
128
13335
772.62
13.73
A more critical problem of ZO-NP for the enlarged network with a large number B of blocks is that computing the FIM for all blocks takes a significant amount of epochs and practically does not finish. In other words, the FIMs of many blocks remain unchanged as the initialized identity matrix I. Table 7 shows such situations. The second row corresponds to the last row in Table 1, where the number B was not so large. The third to fifth rows correspond the above introduced enlarged MI.-mixer. Since the number B of blocks was very large in these enlarged networks, many blocks remained initialized even after 1000 epochs with the update frequency hyperparameter Tua 100.
Table 7. The number of blocks where the FIM was updated from the initialized identity matrix I as epochs proceeded in ZO-NP.
epochs
network
B
1
2
5
10
20
50
100
200
500
1000
MLP-mixer in Table
66
5
10
22
36
52
66
66
66
66
66
Enlarged MLP-mixer
3334
5
10
25
49
98
237
465
871
1751
2580
Enlarged MLP-mixer
6668
100
249
488
939
2086
3530
Enlarged MLP MLP-mixer
13335
5
10
25
50
100
248
493
966
2285
4176
17


Reviews:
[{"review_id": "xD1Veb5Wto", "reviewer": "Reviewer_VAny", "summary": "The paper proposed an sampling strategy for ZO optimization, where the perturbation is sampled from a multivariate Gaussian distribution with a covariance matrix. The covariance matrix is designed by not only minimize the expected PSD but also FSD. Adopting the concept of natural gradient, this perturbation is named natural perturbation. To work around large cost in computing for the covariance matrix explicit, the authors propose to use block coordinate approach for a more efficient computation. Experiments show that the proposed method is superior in convergence speed and ending test accuracy compared to existing methods.\n\n## update after rebuttal\nThe authors have addressed most of my questions and I thus updated the score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our paper and evaluating that the concept of natural perturbation is well established.\n\n> It would be interesting to see if the proposed method outperforms the baseline with the same computation budget, or the proposed method gives an interesting trade-off.\n\nThe computation cost can be characterized by the elapsed time and the memory footprint. For the former, we already show the corresponding results in the right plot of Figure 6 and the bottom plots of Figure 12. These show that the proposed method ZO-NP outperformed the baselines with the same elapsed time. For the latter, we newly report the results in the reply to Reviewer 2tFg (please see the first two tables). With these tables and Figure 7, we understand that ZO-NP trades off test accuracy and memory overhead. Thanks for raising this issue. We will include these memory footprint results in the revised manuscript.\n\n> Why in Table 1, ZO-I also uses blocking. Can we add the comparison to the most naive baseline i.e. ZO-I without blocking?\n\nThe reason to use blocking also for ZO-I is that the performance gets better with an appropriate block size $N_\\mathrm{max}$, as Figure 7 shows. And we already have some results without blocking in Figure 11 in Appendix D.2. While the main intention there was to compare with CMA-ES, we can also compare the results with ZO-I.\n\n> For ZO-co and ZO-NP, are they using the same Q? ... Since ZO-NP has a higher computation overhead, it seems to make sense to compare it with ZO-co with a larger Q (which have similar computation cost to ZO-NP) for a fair comparison.\n\nWe used the same Q for ZO-co and ZO-NP, and ZO-co results in a sparse perturbation (a sparse estimated gradient as a weighted sum of perturbations to be exact) as you pointed out. For more related information, see the discussion on _the number of changing parameters_ in Section 5.3.2. Regarding the computational overhead of ZO-NP, we have already made a fair comparison in terms of elapsed time (the right plot of Figure 6 and the bottom plots of Figure 12).\n\n> In figure 6, it looks like it is not fully converged and I am wondering what happens if we increase the epochs till it fully converges. I am wondering if ZO-NP has the advantage just in convergence speed, or also in the ending test accuracy.\n\nThe two tables below show the situations with more epochs (three times more). The epochs allowed for ZO-NP, which consumed extra queries for the Jacobian computation, are shown in the parentheses. The training losses continued to decrease, but the speed efficiency was ZO-I < ZO-co < ZO-NP. The test accuracies converged in ZO-co and ZO-NP but not in ZO-I. It seems that ZO-NP entered the range of overfitting.\n\n### Training loss\n| epochs | 1000 (975) | 2000 (1950) | 3000 (2925) | 4000 (3900) |\n|---|:---:|:---:|:---:|:---:|\n| ZO-I  | 1.039 | 0.962 | 0.919 | 0.889 |\n| ZO-co | 0.966 | 0.881 | 0.826 | 0.787 |\n| ZO-NP | 0.824 | 0.731 | 0.672 | 0.631 |\n### Test accuracy\n| epochs | 1000 (975) | 2000 (1950) | 3000 (2925) | 4000 (3900) |\n|---|:---:|:---:|:---:|:---:|\n| ZO-I  | 0.592 | 0.614 | 0.614 | 0.621 |\n| ZO-co | 0.604 | 0.623 | 0.633 | 0.633 |\n| ZO-NP | 0.622 | 0.632 | 0.636 | 0.632 |\n\n> In line 167 left column, it mentions that a good sampling strategy should maximize the entropy of the distribution. Why is that? Is there theoretical or empirical evidence supporting it? Actually, in the experiment, can you add another baseline with sampling from another distribution with a smaller entropy?\n\nThe reason is to make the sampled perturbations explore as widely as possible. This statement is our new way of understanding the sampling in ZO optimization. Section 3.1, especially the paragraph starting from line 213 left column, provides theoretical support as the existing sampling strategy from $\\mathcal{N}(\\mathbf{0}, \\mathbf{I})$ can be derived from this statement. We could perform some experiments where the entropy of a sampling distribution is randomly reduced independent of the FIM. Please let us know in a further reply if you prefer to see the results.\n\n> In line 321left column, it mentions that FIM also becomes block diagonal. Why?\n\nThis is because the block matrix size is the same for $\\Sigma_b$ and $\\mathbf{F}_{\\theta^{(b)}}$ by (34).\n\n> In line 216 right column, it mentions a too large FSD leads to unstable training. Is there evidence to support it?\n\nA good lecture note can be found at https://www.cs.toronto.edu/~rgrosse/courses/csc2541_2022/readings/L03_metrics.pdf and Figure 1 there on the Rosenbrock function is very intuitive.\n\n> In line 87 right column, what is z and what does p(z|y) means?\n\nThe specific form of p(z|y) depends on the type of task the neural network performs. For example, if the neural network performs a classification task, p(z|y) is a multinomial distribution as explained in Section 4.1.1. And z is a random vector that is marginalized in the FIM computation (28) and specified by a target vector in the loss computation (1).", "claims_and_evidence": "The concept of natural perturbation - the motivation, intuition and derivation - is well presented, and I am convinced that this concept is well established.\n\nThe efficient block-box method of computing FIM (and then the covariance matrix) is also well presented. The algorithm and the motivation and intuition behind it is made clear.\n\nAs to the empirical results part that showing the proposed method is superior, overall the establishment of the experiments is solid, but I have some questions which I will elaborate in the \"Methods And Evaluation Criteria\" section. \n\nThe main concern is that since the proposed method introduces a large computation overhead (even after applying block coordinate approach), the comparison is only fair when the computation cost is the same. It would be interesting to see if the proposed method outperforms the baseline with the same computation budget, or the proposed method gives an interesting trade-off. I don't feel the discussion around the computation overhead is sufficient, nor the comparison is \"fair\". If the authors can address that in the revisions I would be happy to update my review score.", "methods_and_evaluation_criteria": "Overall it is good. But I have some questions/concerns. Beside the major concern already mentioned in \"Claims And Evidence\", questions are:\n\n1. Why in Table 1, ZO-I also uses blocking. Can we add the comparison to the most naive baseline i.e. ZO-I without blocking?\n2. For ZO-co and ZO-NP, are they using the same Q? If so I wonder if using such small Q causes the perturbation being quite sparse resulting in slow convergence. Since ZO-NP has a higher computation overhead, it seems to make sense to compare it with ZO-co with a larger Q (which have similar computation cost to ZO-NP) for a fair comparison. \n3. In figure 6, it looks like it is not fully converged and I am wondering what happens if we increase the epochs till it fully converges. I am wondering if ZO-NP has the advantage just in convergence speed, or also in the ending test accuracy.", "theoretical_claims": "Yes and I don't find any major issue. There are a few questions though:\n1. In line 167 left column, it mentions that a good sampling strategy should maximize the entropy of the distribution. Why is that? Is there theoretical or empirical evidence supporting it? Actually, in the experiment, can you add another baseline with sampling from another distribution with a smaller entropy?\n\n2. In line 321left column, it mentions that FIM also becomes block diagonal. Why?\n\n3. In line 216 right column, it mentions a too large FSD leads to unstable training. Is there evidence to support it?\n\n4. In line 87 right column, what is z and what does p(z|y) means?", "experimental_designs_or_analyses": "Overall it is solid, for questions please refer to \"Methods And Evaluation Criteria\"", "relation_to_broader_scientific_literature": "Zero-order optimization has a broad application in many fields. Proposed in this paper is a general approach to achieve a better performance in zero-order optimization which I believe has a large impact to broader literature.", "essential_references_not_discussed": "References are sufficiently discussed in the paper.", "other_strengths_and_weaknesses": "I am not sure what a point authors trying to make in section 3.2 and figure 3. As (13) already well expressed the trade-off between entropy, PSD and FSD, seeing the results in figure 3 is not surprising but almost a bit trivial.", "other_comments_or_suggestions": "None.\n\n## update after rebuttal\nThe authors have addressed most of my questions and I thus updated my score accordingly.", "questions_for_authors": "I already listed my questions in \"Claims And Evidence\", \"Methods And Evaluation Criteria\", and \"Theoretical Claims\". I hope the authors can help addressing these questions and I would happy to update my score accordingly.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nBHFqFKhx4", "reviewer": "Reviewer_Z8PN", "summary": "This paper introduces the concept of natural perturbations for black-box training of neural networks using zeroth-order (ZO) optimization. The authors propose a novel sampling strategy for parameter perturbations that maximizes entropy while regularizing the distribution to prevent drastic changes in the neural network's conditional probability distribution while considering both parameter space discrepancy (PSD) and function space discrepancy (FSD), inspired by the natural gradient method. The approach involves partitioning parameters into blocks to efficiently compute the Fisher information matrix (FIM) and update the covariance matrix for perturbation sampling. Experimental results demonstrate the superiority of this method over existing zeroth-order optimization techniques across various datasets and architectures.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our paper and evaluating that the proposed method makes sense, experimental improvements are consistent, and the theoretical analysis provides a solid foundation.\n\n> How does the proposed natural perturbations method scale to larger neural network architectures, particularly in terms of computational resources and training time?\n\nStemming from the experimental condition of the last row (CIFAR10) of Table 1, we additionally performed experiments with a larger MLP-mixer. The number of mixers has increased from 3 to 12 and the channel width has increased from 32 to 256, making the number of parameters increased from 33,642 to 1,706,762. The following table shows how the computational resources in terms of memory footprint and training time (seconds per epoch) have increased with the 50 times larger number of parameters.\n\n### Memory footprint and elapsed time in seconds per epoch for CIFAR10 with MLP-mixers\n| method | #mixers | channel width | $N$ | $N_\\mathrm{max}$ | $B$ | memory footprint (GB) | seconds/epoch |\n|---|---:|---:|---:|---:|---:|---:|---:|\n| ZO-I  | 3  | 32  | 33,642    | 510 | 66 | 3.95 | 42.1 |\n| ZO-co | 3  | 32  | 33,642    | 510 | 66 | 3.95 | 40.0 |\n| ZO-NP | 3  | 32  | 33,642    | 510 | 66 | 7.36 | 45.4 |\n| ZO-I  | 12 | 256 | 1,706,762 | 512 | 3,334 | 15.68 | 638.8 |\n| ZO-co | 12 | 256 | 1,706,762 | 512 | 3,334 | 14.35 | 588.0 |\n| ZO-NP | 12 | 256 | 1,706,762 | 512 | 3,334 | 40.87 | 656.5 |\n\nWe observe that the memory footprint and the training time have increased by 5.5 and 14.5 times, respectively, which is rather mild considering the 50 times larger number of parameters. More critical is a linearly increasing (50 times) number $B=3334$ of blocks. This is due to the nature of the block coordinate approach with the same $N_\\mathrm{max}$, and it takes many epochs to compute the FIMs for all $B=3334$ blocks. See the second table in the reply to Reviewer 73sf for a related experimental result. We think that the proposed natural perturbations method scales to larger networks to some extent but a network with one million parameters might be a limitation. We will include such a discussion in the revised manuscript. Thanks for raising this issue.\n\n> -- The experiments primarily focus on small datasets, and it would be beneficial to explore performance on larger datasets and more diverse tasks including NLP.\n\nAs reported above, we have tested a larger neural network with one million parameters. However, it is difficult for our current algorithm to perform experiments on larger datasets like with LLMs that have much larger number of parameters (perhaps hundreds of millions at the smallest). We feel that we need a different strategy, e.g., a much stronger approximation of the FIM than making it block diagonal, and would like to contribute as future work in another paper.\n\n> -- The paper could benefit from more detailed ablation studies to disentangle the effects of sample number.\n\nWe might misunderstood this comment, but if 'sample number' means the number $Q$ of perturbations in Eq. (10), we agree that we should additionally report some results with varying numbers $Q$. So, we have obtained the following results. The query budget for each $Q$ was determined by the number of queries that ZO-I and ZO-co consumed for 100 epochs. We observe that the proposed method ZO-NP consistently outperformed the other two methods, except the extreme cases ($Q=1,2$), where the number of epochs allowed was small since the relative query consumption cost for the black-box Jacobian computation becomes large. We will include such results in the revised manuscript. Thanks for the comment.\n\n### Test accuracies of FashionMNIST with varying the number $Q$ of perturbations in (10)\n| $Q$ | 1 | 2 | 5 | 10 | 20 | 50 | 100 |\n|---|:---:|:---:|:---:|:---:|:---:|:---:|:---:|\n| ZO-I | 0.710 | 0.744 | 0.775 | 0.788 | 0.794 | 0.818 | 0.832 |\n| ZO-co | 0.730 | 0.760 | 0.778 | 0.803 | 0.820 | 0.841 | 0.847 |\n| ZO-NP | 0.716 | 0.763 | 0.822 | 0.840 | 0.858 | 0.869 | 0.873 |\n| query budget ($\\times 10^6$) | 0.12 | 0.18 | 0.36 | 0.66 | 1.26 | 3.06 | 6.06 |\n| #epochs allowed for ZO-NP | 31 | 41 | 58 | 71 | 82 | 92 | 95 |", "claims_and_evidence": "The paper makes several claims regarding the effectiveness of natural perturbations for ZO optimization. These claims are supported by experimental results on various datasets and tasks, including MNIST, FashionMNIST, CIFAR10, Equalization, and Copying memory tasks. The authors show that their method outperforms existing ZO optimization techniques such as ZO-I and ZO-co, as well as other black-box optimization methods like CMA-ES. The results are statistically significant and consistent across different experimental settings.", "methods_and_evaluation_criteria": "The proposed methods for natural perturbations and block coordinate perturbations make sense for the problem of black-box training of neural networks. The sampling strategy and block diagonal covariance matrix approach are logical extensions of existing ZO optimization techniques, designed to address specific challenges such as parameter correlation and computational efficiency. The evaluation criteria, including test accuracy and training loss, are appropriate for assessing the performance of optimization algorithms in this context.", "theoretical_claims": "The paper provides theoretical analysis for the approximation error bound of the zeroth-order gradient approximation by natural perturbations. The proof appears sound and is based on standard assumptions from non-convex optimization literature.", "experimental_designs_or_analyses": "The experimental design involves training the proposed method alongside baseline methods like ZO-I and ZO-co, using identical configurations to ensure a fair comparison. However, the experiments primarily focus on small datasets, and it would be beneficial to explore performance on larger datasets and more diverse tasks including NLP.", "relation_to_broader_scientific_literature": "The paper contributes to the broader scientific literature by addressing the challenge of efficient zeroth-order optimization for neural networks implemented in hardware. This work aligns with recent efforts in black-box optimization techniques and natural gradient methods.", "essential_references_not_discussed": "N/A.", "other_strengths_and_weaknesses": "Strengths:\n\n++ The paper addresses an important practical problem in neural network training for hardware implementations.\n\n++ The proposed method shows consistent improvement over existing techniques across multiple benchmarks.\n\n++ The theoretical analysis provides a solid foundation for the proposed sampling strategy.\n\nWeaknesses:\n\n-- The paper could benefit from more detailed ablation studies to disentangle the effects of sample number.\n\n-- The experiments primarily focus on small datasets, and it would be beneficial to explore performance on larger datasets and more diverse tasks including NLP.", "other_comments_or_suggestions": "I suggest the authors conduct more comprehensive experiments across diverse scenarios, including NLP tasks. This would help validate the effectiveness of natural perturbations in real-world applications.", "questions_for_authors": "How does the proposed natural perturbations method scale to larger neural network architectures, particularly in terms of computational resources and training time?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OXdG1MQmLy", "reviewer": "Reviewer_73sf", "summary": "This paper proposed a novel sampling strategy for zeroth-order optimizaiton for training neural networks. Specifically, the authors propose natural perturbations that incorporate not only the parameter space discrepancy but also a function space discrepancy. To make the approach practical for networks with large-scale parameters, the paper proposes a block coordinate method that partitions the parameters into smaller groups, thereby enabling efficient computation of an approximate block-diagonal Fisher Information Matrix. Experiments on diverse tasks demonstrate taht the proposed method outperforms baseline methods.\n\n## update after rebuttal\n\nMost of my questions and concerns are solved during the author rebuttal and I have no other questions.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our paper and evaluating the idea of designing the sampling distribution as innovative.\n\n> Can the authors elaborate on how the method might be adapted or scaled for neural networks with orders of magnitude more parameters (e.g., in the millions), especially regarding the computational cost of Jacobian and FIM estimation?\n\nYes, stemming from the experimental condition of the last row (CIFAR10) of Table 1, we additionally performed experiments with a larger MLP-mixer. The number of mixers has increased from 3 to 12 and the channel width has increased from 32 to 256, making the number of parameters increased from 33,642 to 1,706,762. The following table shows the computational cost with the million parameters. The difference between ZO-I and ZO-NP roughly corresponds to the cost of Jacobian and FIM estimation. While the elapsed time (reported as seconds/epoch) overhead is less than 3%, the memory footprint cost is significant. We can reduce the memory footprint cost by decreasing the maximum block size $N_\\mathrm{max}$ as shown in the last two rows. As a tradeoff, however, this increased the number $B$ of blocks and consequently the elapsed time in seconds per epoch.\n\n### Elapsed time in seconds per epoch and memory footprint for CIFAR10 with a larger MLP-mixers\n| method | $N_\\mathrm{max}$ | $B$ | seconds/epoch | memory footprint (GB) |\n|---|---|---|---:|---:|\n| ZO-I  | 512 | 3,334 | 638.8 | 15.68 |\n| ZO-co | 512 | 3,334 | 588.0 | 14.35 |\n| ZO-NP | 512 | 3,334 | 656.5 | 40.87 |\n| ZO-NP | 256 | 6,668 | 698.2 | 23.77 |\n| ZO-NP | 128 | 13,335 | 790.8 | 21.80 |\n\n> One minor potential concern is the additional query cost for computing the FIM, which is addressed via block partitioning—but its impact on extremely large-scale networks remains to be further validated. ... Although the block-coordinate method mitigates query costs, it remains to be seen how the approach scales to very large-scale networks (e.g., millions of parameters).\n\nAccording to our current procedure for computing the FIM shown in Algorithm 2, the additional query cost is not affected by the scale of a network (the number $N$ of parameters) as long as the block size $N_b\\leq N_\\mathrm{max}$ is the same. This is because only one block $b$ is sampled in line 9. The problem for a large-scale network instead is that the number $B$ of blocks is large and it takes many epochs to compute the FIMs for all blocks. In other words, the FIMs of many blocks remain as the initialized identity matrix $\\mathbf{I}$ until many epochs have passed.\n\nThe following table shows such situations. The second row corresponds to the last row in Table 1, where the number $B$ is not so large. The third row corresponds to the above introduced larger MLP-mixer with million parameters. Since the number $B$ is large in this larger network, some blocks remained as initialized even after 1000 epochs with the update frequency hyperparameter $T_\\mathrm{ud}=100$. We feel that we can show the scalability and also some limitations of our current method/algorithm by additionally reporting the results like these two tables in the revised manuscript. Thanks for raising these issues.\n\n### The number of epochs (1st row) and the number of blocks (the remaining rows) whose FIM are computed.\n| | $N$ | $B$ | 1 | 2 | 5 | 10 | 20 | 50 | 100 | 200 | 500 | 1000 |\n|---|---:|---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|\n| MLP-mixer in Table 1 | 33,642 | 66 | 5 | 10 | 21 | 36 | 51 | 63 | 66 | 66 | 66 | 66 |\n| Larger MLP-mixer | 1,706,762 | 3,334 | 5 | 10 | 25 | 50 | 98 | 240 | 469 | 878 | 1767 | 2594 |\n\n> Essential References Not Discussed: Wierstra D, Schaul T, Glasmachers T, et al. Natural evolution strategies[J]. The Journal of Machine Learning Research, 2014, 15(1): 949-980.\n\nWe will refer to this paper in the revised manuscript and discuss the differences described in the following table.\nIt shows that the proposed method of natural perturbations is superior in the sense that it can be used for a larger problem with a larger number $N$ of parameters than natural evolution strategies due to the size of FIM. Thanks for suggesting the reference.\n\n### Differences between Natural perturbations and Natural evolution strategies\n| | Natural perturbations | Natural evolution strategies |\n|---|---|---|\n| FIM is computed for | distributions that the neural network expresses | sampling distribution |\n| FIM is used for | directly as the covariance matrix of the sampling distribution | iteratively updating the parameters of the sampling distribution with a small learning rate in a natural gradient manner |\n| FIM of | neural network parameters, whose number is $N$, to be optimized | all kinds of parameters of sampling distribution, e.g., mean and covariance matrix for a multivariate normal distribution |\n| size of FIM | $N\\times N$ | $(N+N^2)\\times (N+N^2)$ for a multivariate normal distribution |", "claims_and_evidence": "The paper claims that standard ZO perturbation sampling strategy is suboptimal for deep neural networks because it ignores the correlation among parameters. he claims are supported by both mathematical derivations and comprehensive empirical results. One minor potential concern is the additional query cost for computing the FIM, which is addressed via block partitioning—but its impact on extremely large-scale networks remains to be further validated.", "methods_and_evaluation_criteria": "These methods and evaluation criteria are appropriate for the target application—black-box training.", "theoretical_claims": "The paper’s primary theoretical contribution is Theorem 3.2, which establishes that the error between the approximate ZO gradient with natural perturbations and the natural gradient is bounded under an L-smooth assumption. I have checked the proof of this theorem.", "experimental_designs_or_analyses": "The experimental design appears sound. A potential area for further investigation is the scalability of the method to very large-scale networks.", "relation_to_broader_scientific_literature": "This paper successfully integrates and extends ideas from both natural gradient literature and black-box optimization to address a practical problem in hardware-based neural networks.", "essential_references_not_discussed": "Wierstra D, Schaul T, Glasmachers T, et al. Natural evolution strategies[J]. The Journal of Machine Learning Research, 2014, 15(1): 949-980.", "other_strengths_and_weaknesses": "Strengths:\n\n1) The idea of designing the sampling distribution by regularizing both PSD and FSD is innovative. The derivation of the optimal covariance and the accompanying error bound lend strong theoretical support.\n\n2) Evaluations across multiple datasets and architectures, along with sensitivity analyses, provide robust empirical evidence.\n\nWeakness:\n\n Although the block-coordinate method mitigates query costs, it remains to be seen how the approach scales to very large-scale networks (e.g., millions of parameters).", "other_comments_or_suggestions": "N/A", "questions_for_authors": "Can the authors elaborate on how the method might be adapted or scaled for neural networks with orders of magnitude more parameters (e.g., in the millions), especially regarding the computational cost of Jacobian and FIM estimation?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sMTgi71nW1", "reviewer": "Reviewer_2tFg", "summary": "This paper extends the idea of natural gradient descent from back-propagation based training (first-order) to zero-order based training of neural networks. Specific care is taken to enable efficient approximations to the Fisher-Information-Matrix for deep neural networks by using block-wise FIM. Several experiments across a variety of settings demonstrate the convergence benefits of their method compared to standard sampling from a standard uniform gaussian.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our paper and evaluating that the contribution is sufficient and the paper is very well written.\n\n> If the authors include a discussion on the memory-costs of their algorithm and provide experimental results on (a subsection of) the ZO-Bench datasets with LLM fine-tuning, it would widen the audience of their method\n\nBelow, we report and discuss the memory costs of our algorithm not only for already reported neural networks but also for a newly constructed larger-size neural network with one million parameters. However, it is difficult for our current algorithm to perform experiments on the ZO-Bench datasets with LLMs that have much larger number of parameters (perhaps hundreds of millions at the smallest). We feel that we need a different strategy, e.g., a much stronger approximation of the FIM than making it block diagonal, and would like to contribute as future work in another paper.\n\n> What I am missing is a study for the memory-usage of this method. ... While this paper explicitly doesn't target memory-reductions, it would have been a great addition to make this method appealing to a wider audience.\n\nThe table below shows the memory cost corresponding to the settings of Table 1. The difference between ZO-I and ZO-NP roughly corresponds to the additional memory cost of introducing natural perturbations.\n\n### Memory footprint (GB) corresponding to the settings of Table 1\n| dataset/task | architecture | $N_\\mathrm{max}$ | $B$ | ZO-I | ZO-co | ZO-NP |\n|---|---|:---:|:---:|:---:|:---:|:---:|\n| MNIST, FashionMNIST | CNN (matrix) | 431 | 6 | 1.08 | 1.08 | 3.79 |\n| Equalization | FeedForward (MZI) | 280 | 2 | 0.39 | 0.39 | 0.42 |\n| Copying | RNN (MZI) | 453 | 7 | 0.75 | 0.75 | 1.91 |\n| CIFAR10 | MLP-mixer (matrix) | 510 | 66 | 3.95 | 3.95 | 7.36 |\n\nWe can reduce the memory cost by decreasing the maximum block size $N_\\mathrm{max}$, as the following table shows. Together with Figure 7 in the submitted main text, we understand that ZO-NP trades off the test accuracy and the memory cost overhead.\n\n### Memory footprint (GB) for FashionMNIST corresponding to the setting of Figure 7\n| $N_\\mathrm{max}$ | 1 | 2 | 4 | 8 | 16 | 32 | 64 | 124 | 236 | 431 |\n|---|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|\n| ZO-NP | 1.11 | 1.11 | 1.11 | 1.11 | 1.11 | 1.15 | 1.48 | 1.90 | 3.07 | 3.79 |\n\nWe also measured the memory footprints of a larger MLP-mixer for CIFAR10, as shown in the table below. The number of mixers has increased from 3 to 12 and the channel width has increased from 32 to 256, making the number of parameters increased from 33,642 to 1,706,762. Again, the difference between ZO-I and ZO-NP roughly corresponds to the additional memory cost of introducing natural perturbations, and we can reduce the memory cost by decreasing the maximum block size $N_\\mathrm{max}$.\n\n### Memory footprint for CIFAR10 with a larger MLP-mixers\n| method | $N_\\mathrm{max}$ | $B$ | memory footprint (GB) |\n|---|---|---:|---:|\n| ZO-I  | 512 | 3,334 | 15.68 |\n| ZO-co | 512 | 3,334 | 14.35 |\n| ZO-NP | 512 | 3,334 | 40.87 |\n| ZO-NP | 256 | 6,668 | 23.77 |\n| ZO-NP | 128 | 13,335 | 21.80 |\n\nWe will include these results in the revised manuscript to clarify the memory cost of the proposed algorithm for a wide variety of neural networks.\n\n> In terms of datasets, many papers in this literature study ZO for LLM fine-tuning on datasets mentioned here: https://github.com/ZO-Bench/ZO-LLM It would be great to see Natural Perturbations ZO applied to those.\n\nWe will include the references to ZO-LLM and the corresponding paper [1] in the revised manuscript, and state that applying the idea of natural perturbations to ZO-based LLM fine-tuning is a future work.\n\n[1] Zhang, Yihua, et al. \"Revisiting zeroth-order optimization for memory-efficient LLM fine-tuning: A benchmark.\" arXiv preprint arXiv:2402.11592 (2024).\n\nThanks for the nice suggestions to widen the audience of our method.", "claims_and_evidence": "The authors claim to have developed a new method through the concept of natural perturbations. Even though this papers shares common themes with yet-unpublished work provided in the appendix, the present paper provides sufficient new elements to be a convincing contribution.", "methods_and_evaluation_criteria": "Yes, the methods and evaluation criteria makes sense. Specifically, studying the convergence behavior normalized by compute time (E.g. Figure 6) captures an important aspect of ZO optimization. \nWhat I am missing is a study for the memory-usage of this method. While this paper explicitly targets black-box functions as a motivating argument for ZO, the reality of many ZO-applications is that they applied because of their reduced memory-consumption compared to back-propagation based methods. While this paper explicitly doesn't target memory-reductions, it would have been a great addition to make this method appealing to a wider audience. \n\nIn terms of datasets, many papers in this literature study ZO for LLM fine-tuning on datasets mentioned here: https://github.com/ZO-Bench/ZO-LLM\nIt would be great to see Natural Perturbations ZO applied to those.", "theoretical_claims": "I checked all derivations in the paper excluding Section 3.3 and its corresponding appendix.", "experimental_designs_or_analyses": "I checked the experiments and analyses I am familiar with, which excludes the MZI-related experiments, about which I understand very little. There are no issues related to these experiments. \n\nAs stated above, I would appreciate an extension of the experiment section to include tasks from the ZO-Bench, which would appeal to a wider audience.", "relation_to_broader_scientific_literature": "The broader scientific literature in this domain tries to accelerate convergence of ZO methods. There are many orthogonal ideas to achieve this goal, which have not been explicitly discussed, which I think is fine. There seems to be some related work in the optical NNs literature, which I was not aware of - and I'm glad for the references.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "The paper is very well written, the math is laid-out in an extremely intuitive manner in terms of notation and accompanying text.", "other_comments_or_suggestions": "NA", "questions_for_authors": "If the authors include a discussion on the memory-costs of their algorithm and provide experimental results on (a subsection of) the ZO-Bench datasets with LLM fine-tuning, it would widen the audience of their method - and I will raise my score.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "NA"}}]

Author rebuttal:

Meta-review: This paper proposes a sampling strategy for zeroth-order optimization called natural perturbations. The proposed natural perturbations adopt the parameter space discrepancy and function space discrepancy. Also, it introduces a block coordinate method to handle the high-dimensional parameters and reduce the computational cost. The experimental results on several tasks and architectures demonstrate the superiority of the proposed method.

This paper is well-written and motivated. The proposed method sounds, and its effectiveness is shown through numerical experiments. As the experimental evaluations are limited to relatively small datasets and architectures, it would be better to show the effectiveness of the proposed method on larger datasets and architectures, which might be future work. I also recommend the authors include the additional result regarding computational cost and memory footprint provided in the rebuttal.

As all reviewers give a positive score, I would recommend accepting this paper.
Decision: Accept (poster)