DeepZero: Scaling Up Zeroth-Order Optimization for Deep Model Training
Authors: Aochuan Chen
Yimeng Zhang
Jinghan Jia
James Diffenderfer
Konstantinos Parasyris
Jiancheng Liu
Yihua Zhang
Zheng Zhang
Bhavya Kailkhura
Sijia Liu
Venue: ICLR 2024 poster (2024)
Keywords: gradient-free learning
zeroth-order optimization
gradient sparsity
Primary area: optimization

Abstract: Zeroth-order (ZO) optimization has become a popular technique for solving machine learning (ML) problems when first-order (FO) information is difficult or impossible to obtain. However, the scalability of ZO optimization remains an open problem: Its use has primarily been limited to relatively small-scale ML problems, such as sample-wise adversarial attack generation. To our best knowledge, no prior work has demonstrated the effectiveness of ZO optimization in training deep neural networks (DNNs) without a significant decrease in performance. To overcome this roadblock, we develop DeepZero, a principled and practical ZO deep learning (DL) framework that can scale ZO optimization to DNN training from scratch through three primary innovations. First, we demonstrate the advantages of coordinate-wise gradient estimation (CGE) over randomized vector-wise gradient estimation in training accuracy and computational efficiency. Second, we propose a sparsity-induced ZO training protocol that extends the model pruning methodology using only finite differences to explore and exploit the sparse DL prior in CGE. Third, we develop the methods of feature reuse and forward parallelization to advance the practical implementations of ZO training. Our extensive experiments show that DeepZero achieves state-of-the-art (SOTA) accuracy on ResNet-20 trained on CIFAR-10, approaching FO training performance for the first time. Furthermore, we show the practical utility of DeepZero in applications of certified adversarial defense and DL-based partial differential equation error correction, achieving 10-20% improvement over SOTA. We believe our results will inspire future research on scalable ZO optimization and contribute to advancing deep learning.

Published as a conference paper at ICLR 2024
DEEPZERO: SCALING UP ZEROTH-ORDER OPTIMIZA- TION FOR DEEP MODEL TRAINING
Aochuan Chen Yimeng Zhang Jinghan Jia James Diffenderfer! Jiancheng Liu
Zheng Zhang i Michigan State University, 'Lawrence Livermore National Laboratory. UCC Santa Barbara
Konstantinos Parasyris' Yihua Zhang
Bhavya Kailkhura² Sijia Liu
"Equal contributions
ABSTRACT
Zeroth-order (ZO) optimization has become a popular technique for solving ma- chine learning (ML) problems when first-order (FO) information is difficult or im- possible to obtain. However, the scalability of ZO optimization remains an open problem: Its use has primarily been limited to relatively small-scale ML problems, such as sample-wise adversarial attack generation. To our best knowledge, no prior work has demonstrated the effectiveness of ZO optimization in training deep neural networks (DNNs) without a significant decrease in performance. To over- come this roadblock, we develop DeepZero, a principled ZO deep learning (DL) framework that can scale ZO optimization to DNN training from scratch through three primary innovations. First, we demonstrate the advantages of coordinate- wise gradient estimation (CGE) over randomized vector-wise gradient estimation in training accuracy and computational efficiency. Second, we propose a sparsity- induced ZO training protocol that extends the model pruning methodology using only finite differences to explore and exploit the sparse DL prior in CGE. Third, we develop the methods of feature reuse and forward parallelization to advance the practical implementations of ZO training. Our extensive experiments show that DeepZero achieves state-of-the-art (SOTA) accuracy on ResNet-20 trained CIFAR-10, approaching FO training performance for the first time. Furthermore, we show the practical utility DeepZero in applications of certified adversarial defense and DL-based partial differential equation error correction, achieving 10- 20% improvement over SOTA. We believe our results will inspire future research on scalable ZO optimization and contribute to advancing DL with black box. Codes are available at athttpss: //tgt//ggttt////// com/ OP comm/PPTii--rrruu///eeeeeer
INTRODUCTION
In the realm of machine learning (ML), optimization algorithms have played a crucial role in en- abling the training of complex models, yielding unprecedented insights and predictive capabilities across diverse domains. Over the years, first-order (FO) gradient-bass based methods, such as stochastic gradient descent (SGD) and its variants (Gardner 1984 Amari 1993; Bottou 2010 2012), have be- come the default choice for model training. These methods rely on gradient information to iteratively update model parameters, aiming to minimize given loss function. Nonetheless, several practical settings exist where FO gradient information is either unavailable or infeasible to compute, call- ing for alternative strategies. Zeroth-order (ZO) optimization (Flaxman et al., 2005 Shamir 2013 Ghadimi & Lan| 2013; Nesterov & Spokoiny 2013 Duchi et al. al.] 2015] Liu et al.) 2018b; Ilyss et al. 2018n] al. (2024) has emerged
promising approach address these challenges, as leverages finite differences of function values to estimate gradients, rather than requesting explicit gradient information. Therefore, with minor modifications to FO algorithms, 70 optimization can be applied to various real-world circumstances where FO gradients are difficult to obtain. For ex- ample, in disciplines like physics and chemistry, ML models may interact with intricate simulators or experiments where the underlying systems non-differentiable (Thelen et al. 2022 Tsaknakis
jtt al. 2022; Louppe et al.] 2019 Abreu de Souza et al. 2023 Baydin et al. 2020). Addition-
ally, black-box learning scenarios often arise when deep learning (DL) models are integrated with
third-part APIs, such as adversarial attack and defense against black-bon DL models (Chen et al.)
2017
Ilyas al. 2018al Zhang al. 2022c Verma al. 2023) and black-box prompt learning

---

Published as a conference paper at ICLR 2024
2(
Dacnat Dare.
Femoud Poot
Batypreaptan Gridden Edteaaion
B
Model Pruning Guided Sparsity
Query Based ZO Optimization
CIFAX 10 Tealing Accuracy (86)
Prinns
Frevme
Prooss
20.30
Prione
Elication
v...
Frecms
Compattionl
Corputationl
Acceloratio:: Paralldiizatin and Feeture Reuse
Ardee
Proms heetar
Network
TALTIM
Compartson
Figure 1: Overview of our DeepZero framework, A: 70 gradient estimation via model queries (Sec. 3 B: Model pruning guides gradient sparsity (Sec.4). C: Acceleration by parallelization and feature reuse (Sec.
5)
D: DeepZero comparison with the computational graph free baseline Pattern Search (Chiang al. 2023 and computational graph dependent methods without BP, Align-Ada (Boopathy & Fiete 2022) LG-FG-A and FG-
W (Ren et 2022). on CIFAR-10.
for language- segguuage-mdeelaase model-as-a-serviec (Diao et al.
2022 Sun al. 2022). Furthermore, the principled
backpropagation (BP) mechanism (Amari 1993; Rumelhart et al. 1995) for calculating FO gradi-
ents may also not be supported when implementing DL models on hardware systems (Gu et al.
2021b Tavanaei et al.] 22119] Greengard 2020: Jabri & Flower 1992 Gu et al. 2021c). In addition
ZO optimization, another relevant research direction the field of DL focuses on developing Hiologically-plausii
BP-free methods. Examples include forward mudient-baseed methods (Ren al., 2022, [Baydin et al. 2022, Silver et al.) 2021 Belouze 2022), greedy layer-wise learning (Nokland & Fidnes] 2019). and Hebbian learning (Isomura & Toyoizumi, 2018 Moraitis et al., 2022]. However, these techniques require access to computational graphs and are highly dependent on the used DL software frameworks and/or model architectures. In contrast, ZO optimization solely relies on model queries and is free of computational graphs utilized. As a result, ZO optimization has broad applicability to DL problems that involve black-box query-only components. Despite the promise of ZO optimization, scalability bottlenecks hinder its application in medium or large-scale DNN training (Wang al. 2017 Liu et 2018b Ohta et al. [2020) Cai al. 2021 Zhang al.) 2022ch. As problem dimensionality increases, the accuracy and efficiency of traditional ZO meth- ods deteriorate. This is because 70 finite iiteeennee-basee gradient estimates are biased estimators of FO gradients. and the bias becomes more pronounced in sisher-dimensioall spaces (Liu et al.
2018b
Cai al. 202T Balasubramanian & Ghadimi 2018).
These challenges motivate the central question addressed in this work: (Q) How to scale ZO optimization for training deep models? To address (Q), we propose a novel framework, 'DeepZero', which infuses novel model pruning and parallel computing techniques to scale up ZO DNN training (see Fig. for a schematic overview). Our main contributions are summarized below.
I We show that deterministic coordinate- wise gradient estimation (CGE) outperforms rester-wise randomized gradient estimation (RGE) in both accuracy and computation efficiency when scaling to deep model training. Further, CGE becomes increasingly advantageous model depth increases.
We show that sparsity crucial for realizing model training via CGE with finite differences. In contrast to prior work, we find that sparsity for black-box models can be obtained for 'free" by ex- tending the current pruning-at-ine antiintialiiztion technique to the ZO learning paradigm. The established synergy between pruning and CGE presents promising avenue for efficient ZO training of DNNs.
We identify the parallelization-f fit property inherent to Caeed ZO optimization and propose a novel forward parallelization method based this property. Our framework enables feature reuse in deep learning, which further accelerates parallel training by eliminating redundant computations.
O We introduce our proposed ZO deep model training framework, 'DeepZero'. To demonstrate the empirical superiority of DeepZero, we conduct extensive experiments on both standard image classification benchmarks and real-world black-box DI. applications. For example, when employing
2

---

Published as a conference paper at ICLR 2024
DeepZero train ResNet20 on CIFAR-10, we obtain 86.94% testing accuracy, the best reported in the literature of gradient-free model training. We also exemplify the vast potential and practi- cal impact of DeepZero in two real-world DL tasks: black-box defense for adversarial robustness (Zhang et al. 2022ch and physics-informed DL with solver-in-the-loop (Um et al. 2020
To clarify, work aims to extend the scalability of ZO optimization for DL applications, address- ing cases where FO optimization becomes challenging or infeasible. Yet, it is essential to note that the proposed advancements in ZO training are not intended to overcome the ultimate scalability challenges to train deep networks at any scale.
2 RELATED WORK
Classical gradient-free optimization. Early research efforts can be broadly categorized into two
groups: direct search-based methods (DSMs) and model-based methods (MBMs) (Wright et al.
1999 Conn et al. 2009) Rios & Sahinidis] [2033] Larson et al. (219)). DSMs include techniques like
coordinate (Fermil )952) and pattern search [Torezon| 1991) methods and the Nelder-Mead simplex method (Nelder & Mead 1965). MBMs consist of model-based descent (Bortz & Kelley 1998)
and trust region (Conn et al. 2000) methods. Evolutionary optimization offers a generic population- based gradient-free computational framework including genetic algorithms (Grefenstette 1993) and particle swarm optimization (Vaz& & Vicente, 2209). Bayesian optimization (Shahriari et al., 2015]
Eriksson et al. 2019) has garnered recent attention by using Gaussian process (GP) to fit a black- box objective function and estimate an optimization solution. However, acquiring an accurate GP is computationally intensive.
Zeroth-order optimization. In contrast classical gradient-free methods, ZO optimization ap- proximates gradients using finite differences, simplifying implementation by minimizing modifica- tions of FO gradient-based algorithms. Like FO methods, ZO enjoys provable convergence guar- antees (Nestervv & Spokoiny 2017 Duchi et al. 2015] Liu et al. 2020a). ZO optimization has gained significant attention for its success in solving various emerging ML problems (Ghadimi & Lan 2013 Nesterov & Spokoiny 2015) Flaxman et al. 2005 Duchi et (015). Examples in-
clude adversarial attack and defense (Chen et al.) 2017] Tu al. (009 9 Ye et | 2018: Ilyas et al.,
201 Sal IZhang et al. [222cc] Verma et al., [023] Zhao et al. 20199] Hogan & Kailkhura 2018 Shu ctt al. 2022), model-agnostic contrastive ex explanation (Dhurandhar et al. 2019), visual prompting for transfer learning (Tsai et al. 2020), computational graph unrolling ( (Vicol et al. 2023), automated
ML (uu et al. 2021a; Wang et al. 2022). ). policy search in reinforcement learning (Vemula et al.,
2019 network resource management (Liu et al. (0188), ML- scientific workflow optimiza- tion Tsaknakis et al., 2022), and on-chip learning (Gu et al. 2021b). Despite ZO's successes in solving ML problems, its application has been limited relatively small scales. For instance, 70 optimizers used for generating adversarial attacks, contrastive explanations, and visual prompts only operate in the input parameter space, which has the dimension of a single input example. Some ac- celeration techniques have been developed to improve ZO performance in larger problems, such as using historical information to enhance ZO gradient estimator (Meier et al. 2019 Cheng et al. 2021). and exploiting gradient sparsity to reduce ZO dependence on problem size (Wang et al. 2017]]
Cai et al. 2022, 2021; [Balasbbramaninn & Ghadimi 2018 Ohta et al. 2020 Gu et al.J (022bb)
While gradient sparsity has been used to improve scalability (Bartoldson et al. 2023), we propose an advanced strategy that leverages model pruning techniques to identify and exploit sparsity in neu- ral network parameters effectively. Our approach is less restrictive than traditional gradient sparsity assumptions and allows for greater flexibility in selecting what to prune. To the best of our knowl- edge, no prior work has demonstrated the practicality of scalable ZO optimization for deep model training without significant performance loss compared to the FO counterpart.
DL without backpropagation. Forward gradient learning (Baydin et al. [022] Ren et al., 2022 Sil- ver et al. 2021 Belouze 2022), which builds upon the forward mode automatic differentiation (AD) capabilities of current DL software frameworks. does not rely on finite differences to approximate FO gradients like ZO optimization. Instead, relies on forward-mode AD to calculate forward (directional) gradient. This gradient is obtained by projecting the FO gradient onto a direction vec- tor and is an unbiased estimator of the FO gradient (Baydin et al., (022). In contrast, ZO gradient estimation based on finite differences is biased (Duchi et al., 2015 Liu et al. 2020a). However, one main limitation of forward gradient learning is that it requires full access to AD software and the deep model, making it impractical for solving black-box DL problems. Recent advances in (Ren (et al. 2022) further improved the scalability of forward gradient learning by using finer-level model information to design architecture-specife local objective functions. Other BP-free DL methods are
3

---

Published as a conference paper at ICLR 2024
motivated by seeking biological interpretation of DL but share similar limitations with forward gradient learning. Some examples include greedy layer-wise learning (Nokland & Eidnes 2019).
input-weight alignment for wide neural networks in the neural tangent kernel (NTK) regime (Boopa-
thy & Fiete, 2022), the Forward- Forwaadd algorithm (Hinton] 2022), Hebbian Learning (Isomura &
TToooizumi 2018 Moraitis et al. 2022), and synthetic gradients (Jaderberg et 2017).
ZO OPTIMIZATION THROUGH FUNCTION VALUE-BASED GRADIENT
ESTIMATION: RANDOMIZED OR COORDINATE-WISE?
We now introduce the Z0 optimization setup and discuss two 70 gradient estimation schemes: deterministic coordinate-wii gradient estimation (CGE) and randomized vector-wise gradient es- timation (RGE). We will demonstrate the advantage of CGE over RGE for DNN training. This inspires further improvements for scaling CGE-based ZO optimization.
Zo optimization and gradient estimation. Let E(O) denote a loss function that we want to mini- mize over the optimization variables & IR (e.g., model parameters of a neural network). The ZO optimizer interacts with the objective function E only by submitting inputs (i.e.. realizations of 0) and receiving the corresponding function values. It slightly modifies the commonly-used first-order (FO) gradient-based algorithm by approximating the FO gradient through function salue-based gra- dient estimates (Liu et al. 2020a}. This is essential when explicit differentiation is difficult due to the black-box nature of the loss function (Zhang al. 2022c Liu al. al.] 2020bb Chen
201 7), or when explicit differentiation is undesired due to concerns about energy efficiency (Gu et al. 202 lb
Liu et al. [018a). RGE (Nesterov & Spokoiny| 2017 Ghadimi & Lan 2013 Duchi et al. 2015
Spall, 1992) and CGE (Kiefer & Wolfowitz [952; Lian et al. 2016 B
Berahas et al. [2022] are two commonly-used gradient estimators based on finite differences of ?. RGE acquires finite differences
via random perturbations of O while CGE uses deterministic coordinate-wise perturbations of 0 (Liu
et al. 2020a). Their formal definitions are given by
(RGE) Vol(O)= 1
E(( + puu)) ((0) n, (CGE) Vol(o)
E(0 + p..) {())
(I)
1
where Vol denotes an estimation of the FO gradient Vol with respect to 0. In (RGE), u, denotes a randomized perturbation
80
76.04
77.63
Tasting Accuracy (%)
7655
70.69
vector, e.g., drawn from the standard Gaussian distribution (O, 1). μ > is a perturbation size (a.k.a. smoothing pa- rameter), and q is the number of random directions used to
70
70.05
60.4
60
50.66
quire finite differences. In (CGE), C; denotes a standard basis vector, and [(0+ue,)- (())) provides the finite-difference esti-
30
Training
41
20 CGB
M mation of the partial derivative of (() at the ith coordinate 0,. Finite difference approximations in (I) are motivated by di- rectional derivatives. Take RGE (with q 1) example. As μ 0, finite difference in RGE converges to directional derivative (0) := u' Vo(( = limz-o +(0+)u,)- of the function f at the point 0 in the direction (Urruty & Lemaréchal 1993). As result, the expression ((O)) yields (0)m) = E[(uu )oE(O) [()) =
a0
20 RGE
730
3700 6670
9640 12610
Number of Model Parameters
Figure 2:
Performance comparison of training simple CNN with vary- ing numbers of parameters on CIFAR- 10 using different training methods.
Vol(O) (recall that E ['uu"] = I). This implies that (((O)u is unbiased gradient estimator of Vel(O) and its biased finite difference approximation is given by (Duchi et al. (0155).
RGE or CGE? First, the function query costs for RGE and CGE differ, with RGE taking O(g) queries and CGE taking O(d) queries based on ① Compared to CGE, RGE has the flexibility to specify q < d to reduce the number of function evaluations. Despite the query efficiency, remains uncertain whether RGE can deliver satisfactory accuracy when training a deep model from scratch. To this end, we undertake a preliminary investigation wherein we train a basic convolutional neural network (CNN) of different sizes on CIFAR- 10, employing both RGE and CGE. To ensure fair comparison in query complexity, we set the query number q in RGE equal to the problem size used in CGE. 2 presents the test accuracy of the learned CNN against the number of model parameters (equivalent to the number of model queries). Here the training recipe is specified by the FO SGD, the ZO RGE-based SGD, and the ZO CGE-based SGD. We observe that CGE can achieve test accuracy comparable to FO training and significantly outperforms RGE. This experi- ment highlights the superiority of CGE over RGE in terms of optimization accuracy even when the
4

---

Published as a conference paper at ICLR 2024
latter uses q d. This accuracy merit of CGE is particularly valuable when training more com- plex neural networks. In Appx. C we provide a detailed analysis of the computational costs using CGE vs. RGE. The time cost relative to model depth is shown in Fig And Tab. AT assesses gradient estimation time costs. We find that CGE demonstrates greater time efficiency than RGE. The computation efficiency loss of RGE is in that it needs to generate and integrate d-dimension perturbation vector into the entire model at once every query. It is worth noting that the recent work (Malladi al., 2024) suggested reducing the memory cost of RGE by storing only the random seed and regenerating the random vector when required. Yet, we argue that this may further hamper the computation efficieccy of RGE due to the need for repeated generation. Based on the advantages of CGE over RGE in terms of both accuracy and computation efficiency, we choose CGE as the pre- ferred ZO gradient estimator. However, query complexity of CGE is still bottleneck, as it scales with model size d.
4 SPARSITY- - ZO TRAINING: A PRUNING LENS AND BEYOND
One valuable property of CGE is the disentanglement of finite differences across coordinates, which suggests that reducing CGE's s query complexity is aligned with pruning the model weights that are being optimized. With this in mind, we propose integrating 7O optimization with pruned gradients to design a more effective inductive bias for 70 deep model training. is worth noting that the spar- sity has been explored in several existing ZO optimization methods to improve the query efficiency of gradient estimation (Wang et al., 2017 Cai et al. 2022 2021 Balasubramanian & Ghadimi 2018 Ohta al.) 2020 Gu al.] (02Tb). However, prior work suffered from two main limita- tions. Firstly, exact sparsity was assumed in the original FO gradients, which required an additional sparse learning method (such as LASSO (Wang et al.) (017)) to recover these sparse gradients from function queries. Secondly, it remains unclear how to optimize the sparsity pattern via a ZO oracle, as the existing method calls for overly heuristics-
pruning methods (e.g., random (Gu et al.) 2021b) or magnitude (Ohta et al. 2020; Zhang et al., 2022b) pruning). Overly increasing sparsity ultimately limits optimization performance. In what follows, we propose a new pruning approach that relies only on model queries, enjoys computation efficiency, and can improve ZO optimization accuracy by inducing an appropriate gradient sparsity.
ZO-GraSP: Model pruning via ZO oracle. The compressibility of model weights for DL has
been extensively studied (Han et al., 2015] Frankle & Carbin, 2018 Ma et al.) 2021 Zhang et al.
2022a by Blalock et al.) 2020 Tanaka et al. [020]] Lee et al. 2018 Wang et al.) 2020 Su et al.
2020 Diffenderfer et al. 2021) h. For instance, the lottery ticket hypothesis (Frankle Carbin 2018)
demonstrated that a randomly initialized, dense neural network contains high-quality sparse sub-
network. However, current effective pruning methods incorporate model training as an intermediate
step (Frankle& & Carbin 2018 Ma et al. 2021 Zhang et al. [022aa] Diffenderfer & Kailkhura 2021 Thus, they are not well-suited for finding sparsity via a 20 oracle.
To address the above challenge, we draw inspiration from training-free pruning methods, known as pruning-at-initte -nnitaaaiiiittiazattionn (Tanaka et al. 2020 Lee et al., (0018) Wang et al., 2020). Within this family, gradient signal preservation (GraSP) (Wang et al. 2020) is a method to identify the sparsity prior of DL through the gradient flows of randomly-imttialzzed network. While GraSP still requires the FO and second-order derivative information, we can estimate these derivatives using only function queries to design the ZO version of GraSP (termed ZO-GraSP). Specifically, GraSP (Wang et al. 2020) assigns pruning scores (denoted by S) to model initialization O. These scores reflect the change gradient flow after pruning the weights:
S 0 (Hg),
Vo,0((0), g= Vol(O).
where recall that l is the loss function of model training, @ denotes the entry-wise multiplication, and Hg represents the Hessian- Hessian-gradient product. Using the ZO learning paradigm, we can first approxi- mate the Hessian- gradient product as the finite difference between two gradients (i.e., Vol( 0 + pg) and (o)())), in the direction g with the smoothing parameter μ. Second, we replace the FO gradient Vel with the ZO gradient estimate Vol given in (L. Combining this yields ZO-GraSP:
vel(o μg) vol(o)
$ :
(3)
In practice, we found that the pruning mask determined by ranking the entries in S is resilient to the ZO gradient estimation error. Therefore, utilize RGE with relatively small number of queries (q < d) to implement ZO-GraSP. This reduces the function query cost without compromis- ing pruning performance; see Tab and Tab. A3 for empirical justifications. Our results show
5

---

Published as a conference paper at ICLR 2024
that ZO-GraSP significantly outperforms random pruning and yields pruned models with accuracy comparable to FO-GraSP.
Integrating sparsity with CGE. As finite differences in CGE (1 are decomposable over weights, it is easy to incorporate sparsity into CGE. To retain the accuracy benefits of training dense models, we incorporate gradient sparsity (in CGE) rather than weight sparsity. This ensures that we train a dense model in the weight space, rather than training a sparse model where the sparsity determined by ZO-GraSP is directly applied. Let Szo-Gras be the coordinate set of unpruned model weights found by ZO-GraSP. The sparsity-induce induced CGE given by
Vol(O)
Σ
8
pe,) E())
(Sparse-CGE)
It is clear that (Sparse-CGF) reduces the query complexity of the original CGE from ((d) to ((S20)-aa)))) where |Szo-GrasP| denotes the cardinality of the coordinate set Szo-Grosp. There may exist two direct methods for integrating (Sparse-CGE) into ZO optimization. MM This method involves altermating between ZO-GraSP and CGE-based ZO optimization. At each iter- ation, S20-GrasP is updated based on the model weights from the previous iteration and then used to construct Sppare-CGEs for updating at the current iteration. M2: This method involves perform- ing praning before ZO training. That is, ZO-GraSP is conducted at model initialization, and the resulting S20-GrasP is applied to (Spars-CGEE) and kept fixed during training. Both M₁ and M2 have limitations. M1 requires repeated calls ZO-GraSP to update Szo-GraSP. leading to a higher query cost for ZO model training. M2 addresses the query complexity by performing ZO-GraSP be- fore training, but it can only produce a smaller model after training. It is known that heavill-prunee models suffers from performance degradation (e.g.. 95% sparse model in Tab.[A2jin Appx.D). Thus, it is nontrivial to integrate ZO-GraSP with ZO training due to the requirement of balancing query efficiency and training effectivvness. To address this, we propose ZO-GraSP-orientee sparsity pattern, which leverages ZO-GraSP to determine layer-wise pruning ratios (LPRs) that can capture DNN compressibility. This approach shares similar essence with smart ratio intro- duced in Su et al. 2020). Specifically, we acquire LPRs from ZO-GraSP at randomly initialized weights prior to 70 training, which is query-efficient like M2. However, unlike M2, LPRs allow for random shufflig of sparse gradient positions in 0 only if these LPRS are oheyed. This allows us to mimic M, to alternate between model weight updates and Szo-GraSP updates, with the lat- ter achieved by LPR-guided randomly updated sparsity patterns. Thus, ZO optimization can train the dense model using uupatte (Sparse- -GE) with LPRs-guided dynamic sparsity pat- terns. Overall, our proposal has the query effciincyy of M2 with the training effectiveness of M1, resulting in a balanced integration of ZO-GraSP into ZO training. We summarize the algorithmic pipeline in Algorithm[] I in Appx. D. where CGE and Z0-GraSP-orientee are clearly described in a unified framework. We also refer readers to Appx. D [oor more explanation and comparisons with M₁ and M2. We provide convergence rate analysis in Appx.AA
dynamic
dynamic sparsity pattern
5 IMPROVING SCALABILITY: FEATURE REUSE & FORWARD PARALLEL
We investigate two characteristics of ZO training that can further enhance implementation scalability: feature reuse and forward par- allelization. The former disentangles intermediate features from weight perturbations, while the latter uses the finite-difference na- ture in CGE to enable scalable distributed implementation.
Trennag Thize (anurs)
GRB with faatsm moree
70 20
C:0 witteut tootin misso
60
80
28
20
Reusing intermediate features. As shown in I.. CGE perturbs each parameter element-wise. Thus, one reuse the feature im- mediately preceding the perturbed layer and carry out the remaining forward pass operations instead of starting from the input layer, as illustrated in [ig.[] The above characteristic of CGE-based model training is referred to 'feature reuse'. More concretely, let fe (x) be a deep model with parameters 0 and input x. We can express fx() as a multi-layer composite function
730
3700 6670 9640
12610
Number Model Parametors
Figure 3: Computation cost of CGE-based ZO training w/ fea- ture reuse vs. w/o feature reuse. The setup follows Fig.
fo(x) soz, (z)) for fol-, o... so o
o fo.o
for (x).
(o22(.)
where for denotes the model's /th layer, L is the total number of model layers, and is the function composition operation. Based on (4). if coordinate-wise weight perturbations are applied to the

---

Published as a conference paper at ICLR 2024
(1 + 1)th layer and its subsequent layers (i.e,, 0>1), the model's outputs corresponding to these perturbed weights can be efficiently obtained by keeping the intermediate features up to the /th layer (i.e., zz) intact. This efficiency becomes more pronounced when perturbing the parameters of deeper layers (ie., for a larger 1). Tig.3coompare the runtime of CGE-based ZO training with and without feature reuse. Empirically, CGE with feature reuse exhibits 2x reduction in training time.
Parallelization of coordinate-wise finite differences. CGE enables parallelization of model train- ing due to its alignment of parameter perturbations with forward passes. If there exist M processes (across multiple GPUs), we can decompose CGE
① based on its parameter coordinates yielding
M
[(O me,) E(0)
Vol(O)
E JES,
1
where S; is the set of active parameters assigned to process S. M. Hence, each process can take [ forward passes. This decoupling property enables scaling forward passes via distributed machines, which can significantly improve training speed. We refer to this parallelization for finite differences as 'forward parallelization'. It is worth noting that forward parallelization is different from the conventional data parallelization used for FO distributed training (Goyal et al. 2017 You et al.] 2018). Our method avoids any performance loss that may result from data parallelization using an overly large batch size, which can cause the optimizer to get stuck in suboptimal local minima due to a lack of stochasticity.
6 EXPERIMENTS
In this section, we first train ResNet-20 for standard image classification on CIFAR-TO, demonstrat- ing scalability and generalization capability over existing gradient-free learning methods. Second, apply DeepZero enhance the robustness of black-box DNN against adversarial attacks, where limited access to the model is available on the defender's end. Lastly, we leverage DeepZero to de- sign physics-informed MI. system by incorporating a scientific PDE solver into the training loop for reducing numerical errors, highlighting its capability to address complex scientific problems.
6.1 IMAGE CLASSIFICATION TASK
Experiment setup. This study focuses on training ResNet- 20 (with 270K parameters) CIFAR-I0 for image classi- fication. We adopt SGD (stochastic gradient descent) as the FO training recipe, with weight decay of 5 x 10-4 and a momentum of 0.9. The learning rate is 0.1, governed by cosine decay scheduler. In the 70 training scenario, we replace the FO gradient by (Sparse-CGF) with a smoothing parameter μ 5 x 10- 3 When implementing ZO-GraSP 3). we set the query budget q = 192 and use the same as CGE. Unless specified otherwise, the weight sparsity ra- tio is chosen to be 90% and the specific sparsity patterns are determined by SR (Smart Ratio). When implementing DeepZero (Algorithm)). we choose the number of epochs 50. Experiments are run on 4 NVIDIA V100 GPUs if not specified otherwise. We compare DeepZero with FO training and two SOTA BP-free training: Pattern Scarch (Chiang et al. 2023) and Seeptt
900
86.55
Testing Accurace 0y
85
66.91
86.25
78.
80
75
PO truning
70-
training
PO training with Sparse Gradient
60.5
Deepteco (Ours)
80
90
95 99
Sparsity (%)
Comparison between DeepZero and FO training baselines on a ResNet-20 for CIFAR-10. We report the mean and standard deviation of 3 inde- pendent runs for each experiment.
Figure 4:
Alignment (Align-ada) (Boopathy & Fiete 2022).
Comparison with FO training. In Fig, 4 compare the accuracy of DeepZero-trained 2e with two variants trained by FO recipes: (1) dense ResNet-20 acquired through FO training and (2) a sparse ResNet- 20 acquired through FO training under FO-GraSP spar- sity pattern. As we can see, the accuracy gap still exists between (I) and the model trained with DeepZero in the sparsity regime of 80% to 99%. This highlights the challenge of ZO optimization for deep model training, where achieving high sparsity is desired to reduce the number of model queries in (Sparse-CGE) for scaling to ResNet-20. Notably, in the sparsity regime of 90%
Accurtic Tize Card
Despllaro Inttam Seardh
Tostin Acounccy (5g)
2 t 12
1800
2203
4303
35303
33350
Dataset
Figure 5: Comparison of DeepZero and Pat- tern Search on ResNet-20 for CIFAR-10 with varying dataset sizes. All experiments done on a single NVIDIA A6000 GPU.
7

---

Published as a conference paper at ICLR 2024
to 99%, DeepZero outperforms (2), showcasing the superiority of gradient sparsity in DeepZero compared to weight sparsity (i.e. directly training a sparse model). In F we provide the DeepZero training trajectory (Fig. performanc vs. data batch setup (Fig. A5) and training time
vs. GPU count (F)..AA6).
Comparison with pattern search (Chiang et al., 2023). In Fig. 5 we compare the accuracy and runtime cost of DeepZero with Pattern Search (Chiang al. 2023) for deep model training. Pattern Search has been shown to achieve comparable test accuracy to SGD in low sample regimes, how- ever, effectiveness as the number of data samples increases remains unclear. To investigate this, we conducted experiments using DeepZero (with 90% gradient sparsity) and pattern search on ResNet- 20 with CIFAR-10, 10, with varying dataset sizes from 100 to 32K. We maintained a fixed total epoch number of 40 for both methods to ensure fair comparison. The results demonstrate DeepZero out- performs Pattern Search in all data regimes, except in the case of 100. Further, the improvement of DeepZero over pattern search (in both accuracy and efficiency) expands dramatically with increasing dataset sizes, indicating the superior scalability of DeepZero.
Comparison with input- alignment (Boopathy & Fiete, 2022). In Tab.[] we present a comparison between DeepZero and the Align-ada approach (Boopathy & Fiete| 2022) for training neural networks without BP on CIFAR-10. While
Table 1: Performance of DeepZero vs. Br-free methods on 8-layer CNN w/ different widths
Boopathy & Ficte 2022).
Method
DeepZemo
PA
DFA
Align-ada
Width
32
64
64
5122
64
[12
64
512
other BP-free training methods (Lillicrap et al.
Accuracy
57.7
64.1
46.5
45.4
54.1
58.0
2014 Nøkland, 2016; Baydin et al., (0222) exist,
Time (h)
4.34
28.15
0.36
3.79
0.42
3.52
0.48
4.59
Align-ada stands out as it applies to training wide
neural networks and achieves state-of-the-art performance on CIFAR-IO, e.g., surpassing methods such as feedback alignment (FA) (Lillicrap et al. (014) and direct feedback alignment (DFA) [Nøkland (016). To ensure fairness, we apply DeepZero to the 8-layer CNN architecture from (Boopathy & Ficte (022) and compare performance with Align-ada at varying model widths. We note that the 51 512-width network was the widest model trained using Align-ada. In contrast, the largest width network we train with DeepZero is 64. Our results clearly show that DeepZero achieves significantly higher testing accuracy compared to Align-ada, even when training with narrower networks. This demonstrates that the improved performance of DeepZero is attributed to its inherent optimization advantages, rather than relying solely on the use of wider networks. Lastly, it is worth noting that Align-ada and other BP-free methods rely on access to computational graphs, making them efficient but unsuitable for black- box applications.
6.2 OTHER BLACK-BOR BOX APPLICATIONS
Black-box defense against adversarial attacks. The black-box defense problem arises when the owner of an ML model is unwilling to share the model details with the defender against adversarial attacks (Zhang et al. 2022c Verma et al., 2023). This poses challenge for existing ro-
Table 2: CA (%) vs. fo-norm based per- turbation radius on ImageNet- using FO DS-based defense (FO-DS) (Salman et al. 2020 ZO-AE-DS (Zhang et al. 2022c and our proposed Deep/Zer.
bustness enhancement algorithms (Madry et al. [017 Co- hen et al. 2019: Salman et al., 2020) that directly robus- tify woxte-box ML models using FO training. To overcome this challenge, ZO optimization was introduced in (Zhang) et al. 2022c) to design a white-box defense operation given a query-based black-box image classifier. To address di- mensionality challenges with ZO, ZO-AE-DS (Zhang et al.
ImageNet (10 classes)
Radius
FO-DS
ZO-AE-DS
DeepZero
0.0
89.33
63.60
86.02
0.25
81.67
$2.80
76.61
0.5
68.87
43.13
61.80
0.75
49.80
32.73
43,05
2022ch introduces an autoencoder (AE) between the white-box denoised smoothing (DS) defense op- eration (to be learned) and the black-box image classifier. By merging AE's encoder with the black- box module, the dimension of ZO optimization is reduced; see Fig. A7 in A for a schematic overview and (Zhang et al. 2022c) for details. The downside of ZO-AE-DS is poor scaling to high- resolution datasets (e.g., ImageNet) due to the use of AE, which compromises the fidelity of the image input to the black-box image classifier and leads to inferior defense performance. In contrast, DeepZero can directly learn the defense operation integrated with the black-box classifier, without needing AE. Tab. compares the defense performance of DeepZero with FO defense (DS (Salman et al. )020 and ZO-AE-DS (Zhang et al. 2022c). To ensure a fair comparison. number of queries (1152) per gradient estimation. Following (Zhang et al. 2022c). we selected a 10- class subset of ImageNet as the training set. The AE is given by DnCNN (Zhang al. 2017) and the
used the same
8

---

Published as a conference paper at ICLR 2024
black-box classifier is specified by ResNet-50. Defense performance is evaluated by certified accu- racy (CA), following the setup of (Salman et al. 2020; Zhang et al. (022c). CA is defined using the l2 norm-based input perturbation radius where larger indicates a stronger adversarial threat. We refer readers to Appx. G for more experiment details. Tab.2 2 highlights that DeepZero consis- tently outperforms ZO-AE-DS in terms of CA for all values of when r = 0, CA is equivalent to the standard testing accuracy. This indicates that DeepZero excels over ZO-AE-DS not only in adversarial robustness but also in overall generalization performance.
O. It is important to note that
Simulation-coupled DL for discretized PDE error correc- tion. Numerical methods, while instrumental in providing physies-informed simulations, come with their own challenge: the discretization unavoidably produces numerical errors. DI. has gained significant attention for addressing this error cor- rection problem. The feasibility of training a corrective neural network through looping interactions with the iterative partial differential equation (PDE) solver, coined (SOL), has been demonstrated in (Um et al.] 2020). While existing work focused on using or developing differentiable simulators for model training, we extend SOL by leveraging DeepZero, enabling its use with non-differentiable or black- box simulators. We name our method ZO-SOL and refer read- ers to Fig. A8 in Appx. for a schematic overview. In this experimental Tramework, the goal to correct the output of low fidelity (i.e., coarse mesh) sim- ulation using a learned DNN so that the corrected simulation more closely aligns with output of a high fidelity (i.e., fine mesh) simulation. In an effort to reduce the amount of correction required by DNN, this correction is applied at each simulation timestep and the corrected simulation state is provided to the simulator to compute the next timestep. For our experiments, we consider 2D unsteady wake flow fluid dynamics benchmark from (Um et al. 2020), in which there is a static rod around which fluid is flowing, and utilize PhiFlow (Holl et al. (2020] as the simulator. Additional de- tails on the PDE, the solver-in-the-lopy loss, and the DNN architecture are given in Appx H Fig. 6 compares the test error correction performance of ZO-SOL (via DeepZero) with three differentiable approaches methods considered in (Um et al. 2020p: SRC (low fidelity simulation without error correction), NON (non-interactive training out of the simulation loop using pre-generated low and high fidelity simulation data), and FO-SOL (FO training for SOL given a differentiable simulator). The simulation error for each method in Vig.blis measured as the average across the five test simula- tions (with varying Reynold's 's numbers that were not utilized in the training set of simulation data). The error for each test simulation is computed as the mean absolute error (MAF) of the corrected simulation compared to the high fidelity simulation averaged across all simulation timesteps. We implement DeepZero for ZO-SOL following the setup used in the image classification task, except for choosing a 95% gradient sparsity. The ZO-SOL and FO-SOL use 16 unrolling steps in the loss function to allow the correction function to interact with the simulator during training. The results demonstrate that ZO-SOL achieved by DeepZero outperforms the SRC and NON baselines, and narrows the performance gap with FO-SOL, despite only having query- query-based access to the simula- tor. Comparing ZO-SOL with NON highlights the promise of ZO-SOL even when integrated with black-box simulators.
Mean Absolate Hrror
0.20
6.20
0.15
0.10
6.N
0.05
0.00
SRC
NON 20-SOL FO-SOL
-n-te-oooo---
Figure 6: Average MAE of cor- rected low-fidelity simulations com- pared to high-fidelity simulations over 5 test simulations using different cor- rection methods. Error bar is variance of MAE across test simulations.
7 CONCLUSION
This paper introduces DeepZero, a framework designed to enhance the scalability of ZO optimiza- tion for deep network training. Specifically, DeepZero integrates coordinate-wise gradient estima- tion, ZO pruning-enabled gradient sparsity, feature reuse, and forward parallelization into a unified training pipeline. Leveraging these innovations, DeepZero showcases both efficiency and effec- tiveness in a wide range of applications. including image classification tasks and various practical black-box DL scenarios. While DeepZerr has made remarkable progress in training DI, models on datasets like ResNet-20 and C10AR-10, it is important to acknowledge that scalability remains a significant challenge when dealing with even larger models and more extensive datasets. Future studies to accelerate ZO optimization for DL are necessary. Additionally, it is worthwhile to ex- plore the applicability of DeepZero in other domains, such as digital twin applications that involve non-differentiable physical entities, and on-device training where the computational overhead of establishing computational graphs and backpropagation is not feasible. Lastly, we refer readers to Appx. for discussion of the broader impact of this paper.
9

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENT
We thank the U.S. Department of Energy via Lawrence Livermore National Laboratory under Con- tract DE-AC52- 07NA27344 and the LLNL-LDRD Program under Project No. 23-ER-030 (LLNL- CONF-849161) for their support.
REFERENCES
Fernando Abreu de Souza, Miguel Crispim Romão, Nuno Filipe Castro, Mehraveh Nikjoo, and Werner Porod. Exploring parameter spaces with artificial intelligence and machine learning black- box optimization algorithms. Phys. Rev. D, 107:035004, Feb 2023. doi: 10.1103/hhsseev..10 035004. htt.l:tttt::/iiit aps.
wttp:o/////oooooooooo http://i.........//....oo//ooooa 1103 1103//hysee/0////0/1 10w.. 035004)
Shun-ichi Amari. Backpropagation and stochastic gradient descent method. Neurocomputing, (4-5):185-19, 1993.
Krishnakumar Balasubramanian and Saeed Ghadimi. Zeroth-order (non)-convex stochastic opti- mization via conditional gradient and gradient updates. NeurlPS, 31, 2018.
Brian R Bartoldson, Bhavya Kailkhura, and Davis Blalock. Compute-efficien deep learning: Algo- rithmic trends and opportunities. Journal of Machine Learning Research, 24:1-77, 2023.
Atilum Günes Baydin, Kyle Cranmer NYU, Matthew Feickert, Lindsey Gray, Lukas Heinrich, Alexander Held NYU, Andrew Melo Vanderbilt Mark Neubauer, Jannicke Pearkes, Nathan Simp- son, Nick Smith, et al. Differentiable programming in high-energy physics. Submitted as a Snow- mass LOI, 2020.
Atilim Güneş Baydin, Barak A Pearlmutter, Don Syme, Frank Wood, and Philip Torr. without backpropagation. arXiv preprint (rXiv:2202.08887, 2022.
Gradients
Gabriel Belouze. Optimization without backpropagation. arXiv preprint 200.0020,, 2022.
Albert S Berahas, Liyuan Cao, Krzysztof Choromanski, and Katya Scheinberg. A theoretical and empirical comparison of gradient approximations in derivative-free optimization. Foundations of Computational Mathematics, 22(2):507-560) 2022.
Davis Blalock, Jose Javier Gonzalez Ortiz, Jonathan Frankle, and John Guttag. What is the state of neural network pruning? Proceedings of machine learning and systems, 2:129-146, 2020.
Akhilan Boopathy and Ila Fiete. How to train your wide neural network without backprop: input-weight alignment perspective. In ICML, pp. 2178-2205. PMLR, 2022.
David Matthew Bortz and Carl Tim Kelley. The simplex gradient and noisy optimization prob- lems. In Computational Methods for Optimal Design and Control: Proceedings of the AFOSR Workshop on Optimal Design and Control Arlington, Virginia 30 September-3 October, 1997, pp- 77-90. Springer, 1998.
Léon Bottou. Large-scale machine learning with stochastic gradient descent. In Proceedings of COMPSTAT'2010. 19th International Conference on Computational StatisticsParis France, Au- gust 22-27, 2010 Keynote, Invited and Contributed Papers, pp. 177-186. Springer, 2010.
Léon Bottou. Stochastic gradient descent tricks. Neural Networks: Tricks of the Trade: Second Edition, pp. 421-436, 2012.
HanQin Cai, Yuchen Lou, Daniel McKenzie, and Wotao Yin. A zeroth-order block coordinate descent algorithm for huge-scale black-box optimization. arXiv preprint arX1v:2102.10707, 2021.
HanQin Cai, Daniel Mckenzie, Wotao Yin, and Zhenliang Zhang. Zeroth-order regularized opti- mization (zoro): Approximately sparse gradients and adaptive sampling. SIAM Journal on Opti- mization, 32(2))687-7144 2022.
Pin-Yu Yu Chen, Huan Zhang, Yash Sharma. Jinfeng Yi, and Cho-Jui Hsich. Zoo: Zeroth order opti- mization based black-box attacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM workshop artificial intelligence and security, pp. 15-26, 2017.
10

---

Published as a conference paper at ICLR 2024
Shuyu Cheng, Guoqiang Wu, and Jun Zhu. On the convergence of prior-guidee zeroth-order op- timization algorithms. Advances in Neural Information Processing Systems, 34:14620-1400 2021.
Ping-yeh Chiang, Renkun Ni, David Yu Miller, Arpit Bansal, Jonas Geiping, Micah Goldblum, and Tom Goldstein. Loss landscapes are all you need: Neural network generalization can be explained without the implicit bias of gradient descent. In The Eleventh International Conference on Learning Representations, 2023.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. international conference on machine learning, pp. 1310-1320. PMLR, 2019.
A. R. Conn, K. Scheinberg, and L. N. Vicente. Introduction to derivative-free optimization, vol- ume 8. Siam, 2009.
Andrew R Conn, Nicholas IM Gould, and Philippe Toinn.. Trust region methods. SIAM, 2000.
Amit Dhurandhar, Tejaswini Pedapati, Avinash Balakrishnan, Pin-Yu Chen, Karthikeyan Shan- mugam, and Ruchir Puri. Model agnostic contrastive explanations for structured data. arXiv preprint arXiv11966000117 2019.
Shizhe Diao, Zhichao Huang, Ruijia Xu, Xuechun Li, Yong Lin, Xiao Zhou, and Tong Zhang. Black-box prompt learning for pre-trained language models. arXiv preprint 1rXiv:2201.08531, 2022.
James Diffenderfer and Bhavya Kailkhura. Multi-prize lottery ticket hypothesis: Finding ac- curate binary neural networks by pruning randomly weighted network. arXiv preprint arXiv:2103.09377, 2021.
James Diffenderfer, Brian Bartoldson, Shreya Chaganti, Jize Zhang, and Bhavya Kailkhura. A winning hand: Compressing deep networks can improve out-of-distribution robustness. Advances in Neural Information Processing Systems, 34:664-615 676, 2021.
John C Duchi, Michael Jordan, Martin J Wainwright, and Andre Wibisono. Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Transactions on Information Theory, 6155:27788-2806 2015.
David Eriksson, Michael Pearce, Jacob Gardner, Ryan D Turner, and Matthias Poloczek. Scalable global optimization via local bayesian optimization. Advances in neural information processing systems, 32, 2019.
Yu Fang, Jiancheng Liu, Mingrui Zhang, Jiasheng Zhang, Yidong Ma, Minchen Li, Yuanming Hu, Chenfanfu Jiang, and Tiantian Liu. Complex locomotion skill learning via differentiable physics. arXiv preprint arXiv:2206. 224.022006.,344, 2022.
Enrico Fermi. Numerical solution minimum problem. Technical report, Los Alamos Scientific Lab., Los Alamos, NM, 1952.
A. D. Flaxman, A. T. Kalai, and H. B. McMahan. Online convex optimization in the bandit set- ting: Gradient descent without a gradient. Proceedings of the sixteenth annual ACM-SIAM symposium Discrete algorithms,, pp. 385 385-394, 2005.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. arXiv preprini arXiv: 1803.036333 2018.
William A Gardner. Learning characteristics of stochasti--rradint--esss algorithms: A general study, analysis, and critique. Signal processing, ((2):113-1333 1984.
Ghadimi and G. Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic pro- gramming. SIAM Journal Optimization, 23(4):2341-233 2013.
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, An- drew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet in hour. arXiv preprint arXiv: /76.v 2017.

---

Published as a conference paper at ICLR 2024
Samuel Greengard. Neuromorphic chips take shape. Communications of the ACM, 63(8)99-1, 2020.
John J Grefenstette. Genetic algorithms and machine learning. In Proceedings of the sixth annual conference on Computational learning theory, pp. 3-4, 1993.
Bin Gu, Guodong Liu, Yanfu Zhang, Xiang Geng, and Heng Huang. Optimizing large-scale hyper- parameters via automated learning algorithm. arXiv preprint w7Xi:22022.00026, 2021a.
Jiaqi Gu, Chenghao Feng, Zheng Zhao, Zhoufeng Ying, Ray T Chen, and David Z Pan. Efficient on- chip learning for optical neural networks through power-aware sparse zeroth-order optimization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 7583-7591, 2021b.
Jiaqi Gu, Hanqing Zhu, Chenghao Feng, Zixuan Jiang, Ray Chen, and David Pan. L2ight: Enabling on-chip learning for optical neural networks via efficient in-situ subspace optimization, Advances in Neural Information Processing Systems, 34:8649-B8 18661, 2021c.
Song Han, Huizi Mao, and William J Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. arXiv preprint arXiv:1510.00149, 2015.
Geoffrey Hinton. The heward-ffrwart algorithm: Some preliminary investigations. arXiv preprint arXiv:2212.13345 2022.
Thomas A Hogan and Bhavya Kailkhura. Universal decision-based black-box perturbations: Break- ing security-through through-obscurity defenses. arXiv preprint arXiv: /.03333, 2018.
Philipp Holl, Vladlen Koltun, and Nils Thuerey. Learning to control pdes with differentiable physics, 2020.
Yuanming Hu, Jiancheng Liu, Andrew Spielberg, Joshua B Tenenbaum, William Freeman, Jia- jun Wu, Daniela Rus, and Wojeiech Matusik. Chainqueen: A real-time differentiable physical simulator for soft robotics. ICRA, pp. 6265-6271, IEEE, 2019.
Andrew Ilyas, Logan Engstrom, Anish Athalye, and Jessy Lin. Black-box adversarial attacks with limited queries and information. In International conference on machine learning, pp. 2137- 2146. PMLR, 2018a.
Andrew Iyas, Logan Engstrom, and Aleksander Madry. Prior convictions: Black-box adversarial attacks with bandits and priors. arXiv preprint arXiv: 1807.00788 2018b.
Takuya Isomura and Taro Toyoizumi. Error-gated hebbian rule: A local learning rule for principal and independent component analysis. Scientific reports, 8(1):1835, 2018.
Marwan Jabri and Barry Flower. Weight perturbation: An optimal architecture and learning tech- nique for analog visi feedforward and recurrent multilayer networks. IEEE Transactions on Neu- ral Networks, 3(1):154-157, 1992.
Max Jaderberg, Wojciech Marian Czarnecki, Simon Osindero, Oriol Vinyals, Alex Graves, David Silver, and Koray Kavukcuoglu. Decoupled neural interfaces using synthetic gradients. In Inter- national conference on machine learning, pp. 1627-1635. PMLR, 2017.
Jack Kiefer and Jacob Wolfowitz. Stochastic estimation of the maximum of regression function. The Annals of Mathematical Statistics, pp. 462-466, 1952.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 22698206.00 2014.
Jeffrey Larson, Matt Menickelly, and Stefan M Wild. Derivative-free optimization methods. Acta Numerica, 28:287-404, 2019.
Namhoon Lee. Thalaiyasingam Ajanthan, and Philip HS Torr. Snip: Single-shot network pruning based connection sensitivity. arXiv preprint arXiv: arXiv:1810.00 1810.02340 2018
12

---

Published as a conference paper at ICLR 2024
X. Lian, H. Zhang, C.-J. Hsieh, Y. Huang, and J. Liu. A comprehensive linear speedup analysis for asynchronous stochastic parallel optimization from zeroth-order to first-order. In Advances in Neural Information Processing Systems, pp. 3054-3062 2016.
Timothy P Lillicrap. Daniel Cownden, Douglas Tweed, and Colin Akerman. Random feedback weights support learning in deep neural networks. arXiv preprint arXiv: 2014.
Sijia Liu, Jie Chen, Pin- Yu Chen, and Alfred Hero. Zeroth-order online alternating direction method of multipliers: Convergence analysis and applications. In International Conference Artificial Intelligence and Statistics, pp. 288-297. PMLR, 2018a.
Sijia Liu, Bhavya Kailkhura, Pin- Yu Chen, Paishun Ting, Shiyu Chang, and Lisa Amini. Zeroth- order stochastic variance reduction for nonconvex optimization. Advances in Neural Information Processing Systems, 31, 2018b.
Sijia Liu, Pin- Yu Chen, Bhavya Kailkhura, Gaoyuan Zhang, Alfred Hero III, and Pramod K Varshney. A primer zeroth-order optimization in signal processing and machine learning: Principals, recent advances, and applications. IEEE Signal Processing Magazine, 37(5):43-54, 2020a.
Sijia Liu, Songtao Lu, Xiangyi Chen, Yao Feng, Kaidi Xu, Abdullah Al-Dujaili, Mingyi Hong, and Una-May O'Reilly. Min-max optimization without gradients: Convergence and applications to black-box evasion and poisoning attacks. In International conference on machine learning, pp- 6282-6293, PMLR, 2020b.
Gilles Louppe, Joeri Hermans, and Kyle Cranmer. Adversarial variational optimization of non- differentiable simulators. In The 22nd International Conference Artificial Intelligence and Statistics, pp. 1438-1447. PMLR, 2019.
Xiaolong Ma, Geng Yuan, Xuan Shen, Tianlong Chen, Xuxi Chen, Xiaohan Chen, Ning Liu, Ming- hai Qin, Sijia Liu, Zhangyang Wang, et al. Sanity checks for lottery tickets: Does your winning ticket really win the jackpot? Advances in Neural Information Processing Systems, 34:12749- 12760, 2021.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint 17Xiv:1706.000 06083, 2017.
Sadhika Malladi, Tianyu Gao, Eshaan Nichani, Alex Damian, Jason D Lee, Danqi Chen, and Sanjeev Arora. Fine-tuning language models with just forward passes. arXiv preprint arXiv:2305.1 17333, 2023.
Sadhika Malladi, Tianyu Gao, Eshaan Nichani, Alex Damian, Jason Lee, Danqi Chen, and Sanjeev Arora. Fine-tuning language models with just forward passes. Advances in Neural Information Processing Systems, 36, 2024.
Florian Meier, Asier Mujika, Marcelo Matheus Gauy, and Angelika Steger. Improving gradient esti- mation in evolutionary strategies with past descent directions. arXiv preprint 100.221910.05268, 2019.
Timoleon Moraitis, Dmitry Toichkin, Adrien Journé, Yansong Chua, and Qinghai Guo. Softhebb: Bayesian inference unsupervised hebbian soft winner-take-all networks. Neuromorphic Com- puting and Engineering. 2(4):044017, 2022.
John A Nelder and Roger Mead. A simplex method for function minimization. The computer journal, 7(4):308-31,, 1965.
Y. Nesterov and V. Spokoiny. Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 2(17):5275566, 2015.
Yurii Nesterov and Vladimir Spokoiny. Random gradient- free minimization of convex functions. Foundations of Computational Mathematics, 17:527-566, 2017.
13

---

Published as a conference paper at ICLR 2024
Arild Nokland. Direct feedback alignment provides learning in deep neural networks. Advances in neural information processing systems, 29, 2016.
Arild Nøkland and Lars Hiller Eidnes. Training neural networks with local error signals. In Inter- national conference on machine learning, pp. 4839 4850. PMLR, 2019.
Mayumi Ohta, Nathaniel Berger, Artem Sokolov, and Stefan Riezler. Sparse perturbations for im- proved convergence in stochastic zeroth-order optimization. In Machine Learning. Optimization, and Data Science: 6th International Conference, L.D 2020, Siena, Italy, July 19-23, 2020, Re- vised Selected Papers, Part II 6, pp. 39-64. Springer, 2020.
Mengye Ren, Simon Kornblith, Renjie Liao, and Geoffrey Hinton. Scaling forward gradient with local losses. arXiv preprint arXi::2210.0333 2022.
L. M. Rios and N. V. Sahinidis. Derivative-free optimization: a review of algorithms and comparison of software implementations. Journal of Global Optimization, 56(3):1247-1299) 2013.
David E Rumelhart, Richard Durbin, Richard Golden, and Yves Chauvin. Backpropagation: The
basic theory. Backpropagation: Thheory, architectures and applications, pp. 1 1-34, 1995.
Hadi Salman, Mingjie Sun, Greg Yang, Ashish Kapoor, and Zico Kolter. Denoised smoothing: provable defense for pretrained classifiers. Advances in Neural Information Processing Systems, 33:21945 21957, 2020.
Bobak Shahriari, Kevin Swersky, Ziyu Wang, Ryan P Adams, and Nando De Freitas. Taking the human out of the loop: A review of bayesian optimization. Proceedings of the IEEE, 104(1); 148-175, 2015.
O. Shamir. On the complexity bandit and derivative-free stochastic convex optimization. In Conference Learning Theory, pp. 3 3-24, 2013.
Yao Shu, Zhongxiang Dai, Weicong Sng, Arun Verma, Patrick Jaillet, and Bryan Kian Hsiang Low. Zeroth-order optimization with trajectory-informedd derivative estimation. In ICLR, 2022.
David Silver, Anirudh Goyal, Ivo Danihelka, Matteo Hessel, and Hado van Hasselt. Learning by
directional gradient descent. In International Conference Learning Representations, 2021.
James Spall. Multivariate stochastic approximation using a simultaneous perturbation gradient approximation. IEEE transactions on automatic control, 37(3)332-341, 1992.
Jingtong Su, Yihang Chen, Tianle Cai, Tianhao Wu, Ruiqi Gao, Liwei Wang, and Jason D Lee. Sanity-checking pruning methods: Random tickets can win the jackpot. Advances in Neural Information Processing Systems, 33:20390-20401, 2020.
Tianxiang Sun, Yunfan Shao, Hong Qian, Xuanjing Huang, and Xipeng Qiu. Black-box tuning for asseeee--eell-----eeeeeee In International Conference on Machine Learning, pp. 20841 20855. PMLR, 2022.
Hidenori Tanaka, Daniel Kunin, Daniel L Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. Advances in neural information pro- cessing systems, 33:6377-6388 2020.
Amirhossein Tavanaei, Masoud Ghodrati, Saeed Reza Kheradpisheh, Timothée Masquelier, and Anthony Maida. Deep learning in spiking neural networks. Neural networks, 111:47-63, 2019.
Adam Thelen, Xiaoge Zhang, Olga Fink, Yan Lu, Sayan Ghosh, Byeng Youn, Michael D Todd, Sankaran Mahadevan, Chao Hu, and Zhen Hu. A comprehensive review of digital twin-part 1: modeling and twinning enabling technologies. Structural and Multidissiplinary Optimization, 65 (12):354, 2022.
Virginia Torezon. On the convergence of the multidirectional search algorithm. SIAM journal on Optimization, 1(1):123-145, 145, 1991.
14

---

Published as a conference paper at ICLR 2024
Yun-Yun Tsai, Pin- Yu Chen, and Tsung- Yi Ho. Transfer learning without knowing: Reprogramming black-box machine learning models with searce data and limited resources. In International Conference on Machine Learning, pp. 9614-9624, PMLR, 2020.
Ioannis Tsaknakis, Bhavya Kailkhura, Sijia Liu, Donald Loveland, James Diffenderfer, Anna Maria Hiszpanski, and Mingyi Hong. Zeroth-order sciml: Non-intrusive integration of scientific soft- ware with deep learning. arXiv preprint arXiv:2206.02788 2022.
Chun-Chen Tu, Paishun Ting, Pin- Yu Chen, Sijia Liu, Huan Zhang, Jinfeng Yi, Cho-Jui Hsieh, and Shin-Ming Cheng. Autozoom: Autoencoder-baase zeroth order optimization method for attack- ing black-box neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 742-749, 2019.
Kiwon Um, Robert Brand, Yun Raymond Fei, Philipp Holl, and Nils Thuerey. Solver-in-the-lowt Learning from differentiable physics to interact with iterative pde-solvers. NeurlPS, 33:6111- 6122, 2020.
Jean-Baptiste Hiriart Urruty and Claude Lemaréchal. Convex analysis and minimization algorithms. Springer-Venlle 1993.
A Ismael F Vaz and Luís Nunes Vicente. Pswarm: a hybrid solver for linearly constrained global derivative-free optimization. Optimization Methods & Software, 24(4-5):669-638 2009.
Anirudh Vemula, Wen Sun, and Bagnell. Contrasting exploration in parameter and action space: A zeroth-order optimization perspective. In The 22nd International Conference Artificial In- telligence and Statistics, pp. 2926-2935. PMLR, 2019.
Astha Verma, Siddhesh Bangar, AV Subramanyam, Naman Lal, Rajiv Ratn Shah, and Shin'ichi Satoh. Certified zeroth-order black-box defense with robust unet denoiser. arXiv preprint 2rXiv:2304.066400, 2023.
Paul Vicol, Zico Kolter, and Kevin Swersky. Low-variance gradient estimation in unrolled compu- tation graphs with es-single. arXiv preprint arXiv:2304. 2023.
Chaoqi Wang, Guodong Zhang, and Roger Grosse. Picking winning tickets before training by preserving gradient flow. arXiv preprint arXiv:2002.07376 2020.
Xiaoxing Wang, Wenxuan Guo, Jianlin Su, Xiaokang Yang. and Junchi Yan. Zarts: On zero-order optimization for neural architecture search. Advances in Neural Information Processing Systems, 35:12868 -22188 2022.
Yining Wang, Simon Du, Sivaraman Balakrishnan, and Aarti Singh. Stochastic zeroth-order opti- mization in high dimensions. arXiv preprint arXiv: 10551, 2017.
Stephen Wright, Jorge Nocedal, et al. Numerical optimization. Springer Science, 35(67-68):7, 1999.
Haishan Ye, Zhichao Huang, Cong Fang, Chris Junchi Li, and Tong Zhang. Hessian-aware zeroth- 2018
order optimization for black-box adversarial attack. arXiv preprint
Yang You, Zhao Zhang, Cho-Jui Hsich, James Demmel, and Kurt Keutzer. Imagenet training in minutes. In Proceedings of the 47th International Conference Parallel Processing, pp. 1-10, 2018.
Kai Zhang, Wangmeng Zuo, Yunjin Chen, Deyu Meng, and Lei Zhang. Beyond gaussian denoiser: Residual learning of deep enn for image denoising. IEEE transactions on image processing, 26 (7):3142-3155, 2017.
Yihua Zhang, Yuguang Yao, Parikshit Ram, Pu Zhao, Tianlong Chen, Mingyi Hong, Yanzhi Wang, and Sijia Liu. Advancing model pruning via bi-level optimization. Advances in Neural Infor- mation Processing Systems, 2022a.
Yihua Zhang, Pingzhi Li, Junyuan Hong, Jiaxiang Li, Yimeng Zhang, Wenqing Zheng, Pin- Yu Chen, Jason D Lee, Wotao Yin. Mingyi Hong. et al. Revisiting zeroth-order optimization for memory-efficient Ilm fine-tuning: A benchmark. arXiv preprint arXiv:2402. //52, 2024.
15

---

Published as a conference paper at ICLR 2024
Yimeng Zhang, Akshay Karkal Kamath, Qiucheng Wu, Zhiwen Fan, Wuyang Chen, Zhangyang Wang, Shiyu Chang, Sijia Liu, and Cong Hao. Data felta-model-aae hardware tri-design for energy- efficient video intelligence. arXiv preprint arXiv:2210.08577 2022b.
Yimeng Zhang, Yuguang Yao, Jinghan Jia, Jinfeng Yi, Mingyi Hong, Shiyu Chang, and Sijia Liu. How to robustify black-box ml models? zeroth-order optimization perspective. ICLR, 2022c.
Pu Zhao, Sijia Liu, Pin- Yu Chen, Nghia Hoang, Kaidi Xu, Bhavya Kailkhura, and Xue Lin. On the design of black-box adversarial examples by leveraging gradient-free optimization and operator splitting method. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 121-130, 2019.
16

---

Published as a conference paper at ICLR 2024
APPENDIX
A REMARK ON CONVERGENCE RATE.
For rigorous convergence analysis, we can perceive the sparsity-enhanced ZO training method in- troduced above as a specific instantiation within the broader framework of ZO stochastic coordinate descent (Lian et al. 2016). Thus, under necessary theoretical assumptions regarding Lipschitz con- tinuity, gradient smoothness, and bounded gradient variance, we can obtain an upper bound for the convergence rate of our proposal terms of the the gradient norm, serving as a stationarity-ban convergence measure for non-convex optimization:
ΣK O
SO K(1-p) K - p)
(AI)
where i represents the iteration index, K signifies the total number of iterations, O is used in the context of big O notation, p denotes the gradient sparsity ratio, and a stands for the upper bound on the variance of the stochastic gradients. The above highlights that as p increases, the convergence error of the proposed approach also grows. However, it's important to note that increased sparsity leads to reduced number of funetion queries. Consequently, the convergence error and the query efficiency, aligning well with our understanding.
provable tradeoff between
B THE SIMPLE CNN ARCHITECTURE CONSIDERED FOR TRAINING w/ CGE VS. RGE
Conv Block
CNN of varying depth
Conv Block
Cony Block 2
Conv Block
Conv
BN
ReL.U
Pooling
Avg Pooling
FC
Figure Al: Illustration the simple CNN considered with different depths.
As illustrated in Fig. A1 the depth-adjustable simple CNN architecture comprises multiple conv blocks, an average pooling layer, and a fully-connected layer. Each conv block consists of four distinct layers, including @ convolutional layer, @ batch normalization layer, @ ReLU layer, @ max pooling layer. our experiments, the simple CNN networks are trained over a course of 50 epochs utilizing three distinct optimization strategies: FO (first-order) SGD (stochastic gradient descent) training. ZO RGE-based SGD training, and ZO CGE-based SGD training, together with a cosine learning rate scheduler is used.
C COMPUTATION TIME COMPARISON BETWEEN RGE AND CGE
We find that CGE also has computatoin efficiency merit RGE when training CNNs in F A2 presents the com- putation time of different training methods against the model
Training Time (hours)
200
20 CGE
20 RGE
200 24
size and highlights that CGE is more computationally effi-
150
148 92
cient than RGE. To examine the efficiency merit of CGE in
100
detail, we dissect the computation of a single ZO gradient es- timate into four stages: @ generation of directional vectors, ie., u; or e; in (T). @ perturbation of model weights, i.e., + μu; or 0 + μed model inference for calculating fi- nite differences, and ① other arithmetic operations for gradi- ent estimation. Our results show that RGE takes much longer than CGE in stages ① and @ This is because, each model query, RGE needs to generate a directional perturbation vec- for with the same dimension 0 and apply this perturbation
88.1
50
27.18
45.22
48358
$2.08
28.03
730
3700
6670
9640
12610
Number of Model Parameters
Figure A2: The computation cost of using CGE and RGE to train sim- ple CNN in Fig.2 over 50 epochs on CIFAR- 10 against parameter size.
17

---

Published as a conference paper at ICLR 2024
to O. By contrast, CGE can generate the basis vector for 'free' and perturb the model weights using a coordinate- wise indexing operation. A1 shows a comparison of RGE and CGE in D-Q. is also worth noting that concurrent study (Malladi et al. (023) argues that language model fine- tuning using RGE only necessitates the query budget = 1. However, it is important to highlight that their approach has certain restrictions, as it relies having high-quality pretraining model and meticulously crafted prompt.
Tab A1 provides a comparison of the average computation time per iteration for RGE and CGE- based ZO training across four stages: @ genera- tion of directional vectors, i..,, or in I @ perturbation of model weights, i.e., 0 ynu or 0 + μ.e, @ model inference for calculating finite differences, and other arithmetic operations for gradient estimation. The comparison is conducted for training models of different numbers of param- eters (d), ranging from 730 12610. In stage W RGE incurs computation time due to the genera- tion of random Gaussian vectors, whereas CGE free of this step since it estimates gradients in a coordinate-we manner. In stage @,, RGE requires
Table Al: Average per-iteration computation time comparison (seconds) between RGE and CGE. Here gradient estimation process dissected into 4 stages: @ generation of directional vectors (DV), @ model weights perturbation (WP). @ model inference (MI) for calculating finite differ- ences, and other arithmetic operations (AO) for gradient estimation.
RGE (g dy/ /CG
Parameter *
(4)
@ DV
2 WP
MI
30 AO
730
0.17370
0.022/0.06
0.202 0.221
0.149 70.0012
1.1/0.124
6670
3/49/0
4.8474.33
2025
9640
6.74/0
5.47/ 0.246
8.39
4.97 10.336
12610
10.270
8.86 0.457
13.17 14.6
8.05 70.566
more computation time compared to CGE across all parameter sizes. This because RGE perturbs all model weights in single query, while CGE only perturbs single model weight coordinate per query. stage @, the computation times for both 70 algorithms increase with the number of param- eters, with similar time consumption. In stage @ RGE continues to require more computation time than CGE for all parameter sizes. This is because RGE needs to perform extra arithmetic operations (such as the sum operation) to aggregate multiple queries, whereas CGE handles multiple queries coordinate- wise, resulting in a more efficient computation.
D PERFORMANCE OF MODEL PRUNING VIA ZO-GRASP
We implement ZO-GraSP using RGE with the query number g 192 (smaller than the model size d) and compare its performance with random pruning and FO-GraSP. All GraSP variants are performed over randomly initialized model parameters (0). Tab A2 and Tab, present the pruning performance vs. model pruning ratios in the data-model setup of (CIFAR- Io, ResNet-20) and (CIFAR- 10, ResNet-18), respectively. Here the pruning performance is evaluated by measuring the testing accuracy of a sparse model on CIFAR-10. To assess the impact of model pruning, we utilize FO SGD as the optimizing method for sparse model training. As we can see, our proposed ZO-GraSP method demonstrates comparable testing accuracy to FO-GraSP across various pruning ratios and significantly outperforms random pruning.
Table A2: Performance comparison of different model pruning methods (CIFAR-10,, ResNet-20).
(CIFAR-IO, ReeNer-20)
Pruning
1065
00%
90%
Random
92.71 + 0.18
9263 +
90.40 + 0.14
91.94
0.3
91.77 0.16 91.11 0.20 90.7 +
80.35 + 0.19
86 0.15
80.51 -
PO-GraSP
92.64 a 0.30
92.44 + 0.06
92.34
0.111
92.35
0.14
92.07 4 0.11
92.00 D43
91.63 4 0.16
90.75
D07
88.55 0.09
$5.48 1.26
20-GraSP
92.74 a 0.7
9235 a 0.10
92.58
0.20
92.46
008
92.09
0.10
91.1
013
91.48
0.22
90.21 a 0.16
88.08 1 0.09
$1.50 = 0.10
Table A3: Performance comparison of different model pruning methods (CIFAR- 10, ResNet- -8)).
(CIFAR-ID, ResNet-18)
Proning ratio
500%
70%
90%
Random
95.4510.06
0..1
05.30.0015
95,34.10 10
95.40:0.20
95.0910.133
94.9210.14
04.5810006
93.53:10.10
13:13:
FO-GraSP
95 0410000
0.30
95.53_00.66
95.6910005
95.4610.08
95.86.10.99
95.9910.17
95.97.0005
95.91.10.03
96. 191000000
20-GraSP
95.65 43+0.00
95.53
95.53-0.03
95.53-0.14
95.56-0..8 18
05.50+00.6
95. 24+0.09
95 36.666
95.28=005
94.94-0008
94.39+0.13
18

---

Published as a conference paper at ICLR 2024
E ALGORITHM DETAILS
Algorithm 720-Gra9P-oiieeccd-PP--iiieeeee ZO training
1: Get Sz0-GaSP through ZO-GraSP 3
2: Obtain layer-wise pruning ratio Stayer based Szo-GraSP
. 7 4: Randomly generate sparse coordinate set S according to Staee
3: for Epoch / 0, ...
do
5: for Iterations per epoch do
6: Obtain (Sparse-CGE)
(o( based on S
7: Update model weights: +- 0 a vo
8: end for
9:
end for
ZO-GraSP-oriess GrraS--orenteedLPPR-eeiiiee ZO training Algorithm I shows the algorithmic steps ful- fill the ZO-Gr ZO-GraSP-ooe -wwess--oreeeed-LPP LoanteddLLRRguideed guidee ZO training. At initialization, the algorithm acquires the coordinate set of unpruned model weights Szo-GraSP by applying our proposed ZO-GraSP as shown in G3. Subsequently, it computes the layer-wise pruning ratios, denoted as Suaer derived from Szo-GraSP. The Spar (o( then estimated using Stayer- The model weights are then up- dated by subtracting the estimated sparse gradient to the current weight 0. This process iteratively refines the weights for optimizing the model's performance.
Fig.AA demonstrates the superiority of SR-guided training to another alternative methods, Mj built on alternative op-
Performance (%)
timization between ZO-GraSP and sparse training, and M22 based on pruning before model training. To examine the ef- fectiveness of SR in integrating ZO-GraSP with model train-
90
Dense Model
M₁
ing, we compare the pruning performance in FO train-
M2
ing regime (i.e., the resulting sparse model is trained using FO methods). As we can see, SR-guided training consis- tently outperforms methods MM and M2, with the accuracy improvement becoming more pronounced as the pruning ra- tio increases. As the pruning ratio increases, the performance gap with the original dense model also widens. However, our method achieves the smallest performance gap compared to the FO baseline.
SR guided training
80
90
95
Woight Pruning Ratio (%)
Figure A3:
Performance (test- ing accuracy) of SR-guided training vs. pruning ratios on (CIFAR-10, ResNer20).
DeepZero framework. We introduce the DeepZero frame-
work, a novel approach designed to train models using 70 optimization. This framework assimilates three key features: the implementation features, and the adoption of parallel computation techniques. These components the DeepZero framework are expounded in Algorithm
-gggiddeedddg ZO training, the reuse of
Algorithm DeepZero Framework
Initialize: Total epochs T, sparsity update interval K Kaparse LPRs via ZO-GraSP
. .........".. 3: if f. mod K Ssparse
2: for Epoch t = 0, 1, ...........
do
then Update sparse coordinate index set S₁ according to R b> Sparsity inducing
4:
5: end
6: for Process i 1, 2, ......M..................M do
> M processes
7: Based on S,, parallelized forward evaluations with feature reuse
8: end for
9: [Sparse-CCo CGE) estimation using above model evaluations
10: Model weights updating and synchronization
11: end for
19

---

Published as a conference paper at ICLR 2024
F ADDITIONAL EXPERIMENTS OF IMAGE CLASSIFICATION
Fig. A4 presents the training trajectory comparison between DeepZero and the dense FO training baseline. We observe that despite the marginal performance drop. DeepZero achieves competitive convergence rate as the FO counterpart. Besides, it is important to highlight that due to the small variance of CGE on a reduced dimension (parameters after pruning). DeepZero achieves competi- tively stable training as the FO baseline, as indicated by similar standard deviations.
Fig. presents the performance and the time consumption of DeepZero various batch size set- tings. The impact of batch size on model performance has been well-documented in FO training, with larger batch sizes often leading to decreased performance. We sought to examine the effect of batch size selection on ZO training and determine whether increasing the size could reduce training time. As depicted Fig.AS. we observed a marked decline in performance when the batch size exceeded 2048. Additionally, when the batch size set to 512, it reached constant time sumption of 60 minutes per epoch, rendering any further reduction in training time infeasible due to the limitations of GPU computational capacity. We stress that reaching this constant time consump- tion signs the full utilization of each GPU, which easily achieved by forward parallelization.
Fig. A6 presents DeepZero's training speed (iterations per hour) CIFAR-10 10 and ResNet-20 when using different counts of GPUs. We observe training speed scaling linearly with regard to the GPU counts, which justifies the efficiency of acceleration by forward pass and feature reuse.
100-
Juntin Accuracy
Taxe Per Spech
300
(1r gpoda sadd eart.
per hour
250
a5.88 as
2:00
80
Testing Accuracy
200
Accurary
Daeptten Anorwyy Ancurecy
200
60-
DeepZaco Loss PO Loss
860g
70
150
100
60
60
60
20
Epech
50
0.0
128
235
Batch Size
1028 2010
50
2
GPU counts
6
8
Figure A4: Training trajec- tory of DeepZero and FO train- ing on (CIFAR-10. ResNet-20).. DeepZero adopts SSa of 90% sparsity. The mean and stan- dard deviation of independent runs are reported.
Figure A5: Accuracy performance
Figure A6: The training speed of DeepZero on (CIFAR-10. ResNet-20) against GPU counts. Experiments are conducted under NVIDIA TESLA V100 16G GPU resources.
and computation time DeepZero on (CIFAR-10, ResNet-20) against dif- ferent batch sizes. Other settings are consistent with Fig. A4
G ADDITIONAL ILLUSTRATION OF BLACK-BOX DEFENSE AGAINST ADVERSARIAL ATTACKS
Trainable
Fixed
we compare our method, DeepZero, with the baseline method ZO-AF-DS (Zhang al. (022c). Z0-AE- DS utilizes an autoencoder (AE) to reduce the dimensional- ity of the ZO gradient estimation by merging the AE's de- coder with the black-box classifier and integrating the AE's encoder with the white-box defense operation. However, ZO-AE-DS suffers from poor scalability to high-resolution datasets like ImageNet due the use of AE, which compro- mises the fidelity of the image input to the black-box classi- fier. contrast, DeepZero directly optimizes the white-box defense operation without the need for an AE, as demon- strated in Fig A7
Fig. A7
Existing:
New Defense Operation
New Black box Module
White-box
Decoder
Black-bax Classifier
Operation
Chain Rule
White-box
Black box Classifirr
Defense
Operation
DeepZero Optimizer
Following Salman al. 2020 Zhang et al. 2022c
model the defense operation as denoiser given by DnCNN (Zhang al. 2017). To optimize for black-box defense, we adopt the "pretraining + fine- tne-ttning' approach, as de- tailed in (Zhang al., 2022c). We first employ the Adam
Figure A7: Schematic overview of base- line ZO-AE-DS (Zhang et al. 2022c) and DeepZero-enabled black-box defense.
20

---

Published as a conference paper at ICLR 2024
optimizer (Kingma & Ba 2014) to pretrain the denoiser over 90 epochs, based the mean squared error (MSE) loss function. The pre-training stage excludes the optimization with the black-box im- age classifier. After the pretraining phase, apply ZO-GraSP to the pretrained denoiser, with the pruning ratio of 95%. Notably, the percentage of unpruned parameters of the denoiser tends to be almost zero for all layers, except the first and the last layers. With this insight in mind, we specify the finetuning strategy as partial finetuning, which targets only the last layer of the denoiser. However, we still need to address the black-box optimization challenge, provided by the black-box classifier fx). Let 0 represent the denoiser to be finetuned, DeepZero then solves the following black-box optimization problem:
minimize Ex,x (ox]((((((((((x++)))))) 0
(A2)
where x signifies the input, lCE refers to the Cross-Entropy (CE) loss, and ò E (0 represents the standard Gaussian noise with variance o². We apply DeepZero to solve problem (A2) under 20
training epochs, and use a learning rate of 10 which is reduced by a factor of 10 every four epochs.
H SIMULATION-COUPLED DL FOR DISCRETIZED PDE ERROR CORRECTION
The feasibility of training a corrective NN through looping interactions with the iterative partial differ- ential equation (PDE) solver, coined 'solver-in-the loop' (SOL), has been demonstrated in (Um et al., 2020). By leveraging DeepZero, we can enable the of SOL with non-differentiable, or black-box, simulators Hu et al. (2019); Fang et al. (2022). We name our method ZO-SOL. A8g.lA8prrseenn presents com- parison with the baseline method NON, given by non-interactive training out of the simulation loop using pre-generated low and high-fidelity simulation data.
Curnecthy NN
Simulodar mis Astodiff
((0)
NON: Non-Interactive training out of the simulation loop
Currective
((0)
ZO-SOL: Solver-in-lhe-log training via DeepZero
Figure A8: Schematic overview of the base- line approach NON given by training over pre- generated simulation data and ZO-SOL by lever- aging DeepZero address the solver-in-the in-thh---ttoo training challenge.
In our experiments, we consider unsteady wake flow simulation-4 standard benchmark case for fluid dynamies (Um et al. 2020) to assess the effi- cacy of our method. The corrective neural network, adopted from (Um al. 2020), is sequential volutional network consisting two convolutional layers with 5 x 5 kernels, totaling 56,898 param- eters. The SOL problem can then be formulated as the optimization problem
arg min
ET" (Pa(()))) + Co(P. y1+141
(A3)
0
where P. denotes the PDE solver used for the low-fidelity simulation, Co signifies the corrective neural network parameterized by 0, Yt4; stands for the high-precision simulation state (regarded as the ground truth) at time + i, T is the number of timesteps for the ground truth simulation, n is the number of unrolling steps used in SOL, and št4s signifies the output from SOL at the ith step, namely,
_:_ = (1) o Ps. o [[1 + Co) o o
... ... [(1 + Co) o Ps](y.),
times
where is the function composition operation, 1 is identity function and (1l Co) stands for function expressed as (1(-) + Co).).. Note that in our experiments, we take n = 16 during training, that is we have 16 unrolling steps.
For the unsteady wake flow simulation, we follow the details outlined (Um et al. 2020 which include here for completeness. Namely, the unsteady wake flow simulation solves discretized
21

---

Published as a conference paper at ICLR 2024
version the the incompressible Navier-Stoker equations given by:
due 01
+ uu U2
Vp + VV Vu.
(A4)
Juy at
+ u Vuy
Vp+μV. Vuy
(A5)
V u 0,
(A6)
where t is time, is density, is viscosity, p is pressure, tions), and V- denotes the divergence operator. The domain is f2 = [0, 1] x [0, 2] with open boundary conditions and an initial state of circular rod of diameter 0.1 at position (0.5, 0.5)* E.. The domain 52 for the low and high fidelity simulations is discretized using a staggered grid of dimensions [32, 64] and [64, 128), respectively. Additionally, we take T 500 timesteps. We utilized the Phiflow (Holl et al. 2020) simulation code as the solver for our experiments and we based our implementation off the solver in the loop training process from the code httee:ttss///cm github......... com/ cum pbs/ ver -neer-intthh-ooooo
(Mzz Myy My)" T is velocity (xr and y direc-
(0, 1)" along E [0, 1] and y 0. Additionally, there is
For simplicity, the loss in (A3) is only expressed for a single simulation with T timesteps. In our experiments, we utilize different simulations in the training dataset each of which have different Reynolds numbers (which affects fluid flow turbulence and can altered by varying V in (A4) and (A5) in the set (97.7, 195.3, 390.6, 781.3, 1562.5, 3125.0), consistent with (Um et al. 2020 Hence, during training the loss function has an additional outer summation to account for the different training simulations. The test consists of five different simulations computed using
Reynolds numbers in the set (146.5, 293.0, 585.9, 1171.9. .9, 2343.8), also consistent with (Um et al. 2020
To solve problem (A3), DeepZero under the Adam optimization framework is used with a learning rate of 10 over training epochs.
I BROADER IMPACTS AND LIMITATIONS
Broader Impacts. Our proposed ZO learning for deep model training offers valuable solution for various ML problems that involve interactions with black-box APIs, such as language models as a service, and on-chip learning problems where gradient calculation infeasible on resource- hardware. The applications of DeepZero and its black-box approaches explored in this work can also contribute advancements in optimization theory and model pruning other fields. The insights gained from studying DeepZero's 's scalability, efficiency, and effectiveness can have far-reaching implications beyond the realm of deep learning.
Limitations. One limitation of our approaches is the high number of model queries required, which is inherent to 70 optimization general. Improving query efficiency is an important area for future research and compute-efficient techniques from (Bartoldson et al., 2023) likely will be helpful. Additionally, the infusion of sparse deep priors in ZO training may not be suitable for non- deep learning models. Therefore, it remains crucial to develop more generic and model-agnostic ZO training methods that can handle large-scale and extreme- scale problems effectively.
22


Reviews:
[{"review_id": "n3P5aOprsv", "reviewer": "Reviewer_xr4D", "summary": "This is the comments from the fast reviewer. The paper presents a well-constructed framework introducing a sparsity-induced, BP-free optimization method for ML tasks that lack explicit first-order information, such as  black-box prompt learning and adversarial attack and defense. The method adeptly balances query efficiency and training effectiveness, outperforming existing techniques while also extending the scalability of zeroth-order optimization.", "questions": "refer to the weakness.\nIn general I would expect the authors to explain the results:\n\n[1] whether the results in Fig. 4 is SOTA or not. Shall we expect ZO is comparable or better than FO in full weight network? (not only sparse network). \n\n[2] How should we expect ZO v.s. FO with sparsified weights/gradients? do the authors think this is SOTA or not.\n\n[3] How's the ZO applied to other CNNs or even other variants of ResNet beyond resent-20, and resnet-18? This shows that the ZO is not speficially tuned for Resnet-18 or resent-20. It can be applied to various structure/dataset.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "[Strengths] \n\n  -[1] The paper provides a comprehensive and well-designed comparison between CGE and RGE, demonstrate CGE becomes increasingly advantageous as model depth increases.\n\n  -[2] They find one valuable property of CGE is the disentanglement of finite differences across coordinates, which suggests that reducing CGE’s query complexity is aligned with pruning the model weights that are being optimized. And the ZO-GraSP method leverages the flow of gradient signals to determine the sparsity prior of model weights at initialization.", "weaknesses": "[Weaknesses] \n\n  -[1] While the paper is generally well-explained, certain components of the proposed method could benefit from further elucidation for increased clarity. For instance, formalizing the derivation process for the layer-wise pruning rate, even if based on a pre-existing method, would significantly enhance the method's understanding and reproducibility. This improvement would fortify the paper's pivotal contribution, ensuring its effective delivery to the audience.\n\n  -[2] In the paper, the introduction of improved inductive biases for ZO deep model training is mentioned, and the authors may need to carefully balance to ensure that these biases do not overly constrain the model's generalization performance. This may involve appropriately controlling the strength of inductive biases during model training to strike a balance between performance on specific tasks and generalization. Considering the advantages and disadvantages of inductive biases in the context of specific application scenarios and tasks is crucial.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "iqlMzCIJQQ", "reviewer": "Reviewer_X34v", "summary": "This paper shows that zeroth-order optimization methods (where gradients are calculated using finite differences) can be applied to deep neural networks. They prune the network at initialization using GraSP but use finite differences to compute the Hessian. They only sparsify the gradients and not the weights so that they can train a dense model while reducing the training cost. They apply their method to non-differentiable applications such as black-box defense against adversarial attacks, and simulation-coupled DL for discretized PDE error correction.", "questions": "I don't quite understand the rationale behind the comparison of CGE vs. RGE for q=d. Random sampling is a compromise you make when an exhaustive search of the whole space (q=d) is prohibitive. It is obvious that CGE would be better if you can afford to sample the whole space with orthogonal directions (e_i). It is also obvious why RGE is less efficient when q=d. Since the random vectors (u_i) are not orthogonal, the samples are not independent. The real question is how you can increase the accuracy   of estimating the gradient when q << d.\n\nIn the experiments the smoothing function mu is set to 5e-3, which seems fairly large. Since the gradient is exact at the limit of mu -> 0, it would seem like a smaller value would be better. How was this value chosen, and what is the motivation for not using a smaller value?\n\nIf I understand correctly, both the “black-box defense against adversarial attacks” and “simulation-coupled DL for discretized PDE error correction” involve deep neural networks where part of the forward function is non-differentiable. If so, would it be possible to use finite difference just for the part that is non-differentiable, while using automatic differentiation for the modules that are differentiable? Theoretically, you just need to compute one of the chained Jacobians during backprop for the non-differentiable part using finite difference. I know such an implementation would be practically very painful, but if you could limit the number of parameters that you need to differentiate with finite difference it would result in a much larger reduction than pruning the whole network with GraSP.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Zeroth-order optimization methods can be applied to non-differentiable problems, and are a powerful tool for such applications that would otherwise untrainable. There is increasing interest in incorporating PDE-based simulations into deep neural networks, and zeroth-order optimization is an effective tool for training such non-differentiable networks. The description of their approach is clear, and the paper is easy to follow.", "weaknesses": "The experiments on differentiable networks like ResNet-20 is distracting and seems unnecessary. If CGE is used with a small enough mu, the gradient should match that of backprop, so it is obvious that the accuracy will match that of first order methods as shown in Figure 2. If the goal of this comparison is to show the effect of sparsification and approximation errors in the finite difference, the authors should perform a thorough ablation study for the values of mu, q, and the sparsity ratio. Otherwise, I recommend removing the experiments on differentiable networks, since the aim of this paper is not to show how zeroth-order methods compare to first-order methods for differentiable problems. Having this comparison at the beginning of the experiments section may lead the readers to think about this comparison and get distracted from the true message of this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0PMWp8RVkh", "reviewer": "Reviewer_pJQr", "summary": "This paper proposed to improve Zero-Order optimization in deep nerual network learning. It first points out that Coordinate-wise Gradient Estimation (CGE) is better than Randomized Vector-wise Gradient (RGE). Then due to the query complexity of CGE is related to the parameter dimension, it propsed to introduce sparsity during ZO training. It used a combination of ZO and GraSP to measure the importance of parameters for pruning.", "questions": "1. It seems impossible that ResNet-20 with 99% reach a 70% accuracy.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Connection between motivation and corresponding method is clear and sound: the fessibility of a better ZO algorithm leads to a sparse solution.\n2. Combination of GraSP and ZO is interesting.", "weaknesses": "1. Sparsity acts as a tradeoff between performance and fessibility: to get faster training speed require more sparse neural network. A more ideal method is to update portion of parameters at a time while keeping model dense.\n2. Author should consider combination of ZO and other sparsity-inducing method, such as OBD [1] and OBS [2] (approximated by ZO). It would add novelty if the proposed method is disentangled with specific pruning method, or it can be provided that ZO take effect only with GraSP,\n\n[1] https://proceedings.neurips.cc/paper/1989/hash/6c9882bbac1c7093bd25041881277658-Abstract.html\n[2] https://arxiv.org/abs/1705.07565", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TmdHuHtRA0", "reviewer": "Reviewer_r5je", "summary": "This paper proposes DeepZero, a framework that aims for scalable training from scratch with ZO. The main contributions are in 2-fold: \n\n(1) the authors demonstrate that coordinate-wise gradient estimation (CGE) would outperform randomized gradient estimation (RGE) under the same number of model queries, and CGE is more computationally-efficient and performs better under the same number of model queries than RGE. In addition, the authors propose to reuse the layerwise features before the perturbed parameter's model layer, and parallelize the forward computation in multiple processes. \n\n(2) the authors propose the ZO-GraSP algorithm that uses ZO to estimate Hessian-gradient product for each parameter for the GraSP algorithm, and select a subset of parameters to perform the ZO update with CGE. \n\nThe authors perform experiments on ResNet-20 (and 8-layer CNN) on CIFAR10, black-box defense against adversarial attacks with DnCNN and ResNet-50 on ImageNet-10, and corrective NN with iterative PDE solver for simulating unsteady wake flow. In the image classification task, the authors also perform comprehensive scaling experiments with different sparsity ratio, parameter size, dataset size, batch size, and number of GPUs, and demonstrate the performance and scalability of deepzero framework.", "questions": "- Is it possible to use other pruning methods to select sparse subset with ZO than only GraSP method?\n\nBalancing the strength and weakness of this paper, I am inclined to give a weak accept score. But I am happy to raise my score if the above concerns are addressed.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The motivation of this paper is good as the problem is interesting for the wider optimization community: traditional ZO methods do not focus on training a large NN from scratch due to a dependency over $d$. \n\nThe method of reusing intermediate features is effective in accelerating CGE. This method is also tailored to CGE instead of RGE as RGE would perturb all layers, and therefore change the intermediate features of all layers per each query. \n\nChoosing a sparse set of indices to perform ZO update would be computationally-efficient to the ZO-CGE method. I also believe the DeepZero could be more general than only the ZO-GraSP method. In this case, DeepZero could be a general framework for training deep models with ZO from scratch. \n\nThe scaling experiments in the image-classification task are quite comprehensive.", "weaknesses": "- Although the authors make a good comparison of CGE vs. RGE with the same number of queries in Figure 2 and Table A1 and argue the computational efficiency of CGE when $q = d$, the authors do not propose a variant to CGE that would require the number of model queries sub-linear to the parameter size (the linear relationship still holds even we have sparse subset of parameters and parallelization). This issue could be fatal as if we have a model with more than 1 million parameters, DeepZero will still take significant wall-clock time to pretrain even under 90% sparsity (in fact, it already takes 28 hrs with 12k parameters in Figure 3).\n\n- An ablation study missing in this paper is to show the performance of RGE versus the number of queries. We should expect such curve to plateau quickly, and still below the performance of CGE across multiple tasks to show the competitiveness of CGE. Ideally, this comparison should be done across models and tasks, as the statement on the advantage of CGE over RGE when $q$ = $d$ is quite strong and we will need a strong evidence to justify this argument.\n\n- The authors claim the idea of \"forward parallelization\" for ZO-CGE as the novelty of this paper. Prior research (e.g. the last sentence of section 3 in Ruan et al., 2019; the second paragraph of section 1.2 in Cai et al. 2021) have indicated that the gradient estimator of ZO (both CGE and RGE) is parallelizable. However, I did not find any prior literature indicating the intermediate feature reuse of CGE, and I would accept this novelty claim at this moment.\n\n\nReferences:\n\n- Ruan, Yangjun, et al. \"Learning to Learn by Zeroth-Order Oracle.\" International Conference on Learning Representations. 2019.\n\n- Cai, HanQin, et al. \"A zeroth-order block coordinate descent algorithm for huge-scale black-box optimization.\" International Conference on Machine Learning. PMLR, 2021.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qPoIj7PPmw", "reviewer": "Reviewer_2ocP", "summary": "The authors proposed a zeroth-order neural network training method that combines forward-parallelized coordinate-wise difference evaluation and zeroth-order signal-based sparsification at initialization.  They presented experimental results on Resnet-20 trained on CIFAR10.", "questions": "See above.", "limitations": "", "rating": 3, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- Zeroth-order optimization holds promise in explaining the biological plausibility of gradient-free learning.  Combined with network pruning, which is another biologically prominent feature, it might be useful for computational neuroscientific work.  \n- Coordinate-based finite difference estimation coupled with forward parallelization is potentially useful in achieving practicality.", "weaknesses": "- Chosen model for experimentation is not complex enough to make a convincing demonstration of the effectiveness of the method.  How does it perform on training transformer architectures of larger size?  \n- How much sparsification and CGE individually contributed to closing the gap between dense-FO training and sparse-ZO training is not systematically studied.  Independent ablation studies.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XArOmEE1o4", "reviewer": "Reviewer_4mR9", "summary": "The paper introduces DeepZero, a framework designed to enhance the scalability of zeroth-order optimization for deep neural network training. The integration of coordinate-wise gradient estimation, sparsity-inducing pruning, feature reuse, and forward parallelization into a unified training pipeline is a novel approach to addressing the scalability challenge of zeroth-order optimization. The paper showcases the effectiveness and efficiency of DeepZero in a wide range of applications, including image classification tasks and practical black-box deep learning scenarios.", "questions": "1. Provide clearer explanations of the individual components of the DeepZero framework and how they work together.\n2. Organize the experimental results in a more easily interpretable format, such as tables or graphs.\n3. Conduct a more thorough and detailed analysis of how DeepZero compares to other state-of-the-art methods.\n4. Provide a more detailed discussion of the limitations and potential drawbacks of the proposed approach.\n5. Expand on the potential impact of DeepZero in other domains, such as digital twin applications and on-device training.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper presents a novel and innovative approach to addressing the scalability challenge of zeroth-order optimization in deep neural network training.\nThe proposed DeepZero framework is shown to be effective and efficient in a wide range of applications, demonstrating its potential for practical use.\nThe paper provides a thorough and detailed analysis of the performance of DeepZero, including comparisons to other state-of-the-art approaches.", "weaknesses": "1. Lack of clarity and organization in the presentation of the proposed framework and experimental results.\n  - The paper could benefit from clearer explanations of the individual components of the DeepZero framework and how they work together.\n  - The experimental results could be better organized and presented in a more easily interpretable format.\n2. Insufficient comparison to other state-of-the-art approaches.\n  - While the paper does provide some comparisons to other approaches, it could benefit from a more thorough and detailed analysis of how DeepZero compares to other state-of-the-art methods.\n  - The paper could also benefit from a more detailed discussion of the limitations and potential drawbacks of the proposed approach.\n3. Lack of clarity on the broader impact of the paper.\n  - The paper briefly mentions the potential impact of DeepZero in other domains, but could benefit from a more detailed discussion of the broader implications of the proposed approach.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)