Model Evolution Under Zeroth-Order Optimization: A Neural Tangent Kernel Perspective

Chen Zhang; Yuxin Cheng; Chenchen Ding; Shuqi Wang; Jingreng Lei; Runsheng Yu; Yik-Chung WU; Ngai Wong

cs.LGMar 22, 2026

Model Evolution Under Zeroth-Order Optimization: A Neural Tangent Kernel Perspective

Authors: Chen Zhang, Yuxin Cheng, Chenchen Ding, Shuqi Wang, Jingreng Lei, Runsheng Yu, Yik-Chung WU, Ngai Wong

Organizations: The University of Hong Kong · The Hong Kong University of Science and Technology

Abstract

Zeroth-order (ZO) optimization enables memory-efficient training of neural networks by estimating gradients via forward passes only, eliminating the need for backpropagation. However, the stochastic nature of gradient estimation significantly obscures the training dynamics, in contrast to the well-characterized behavior of first-order methods under Neural Tangent Kernel (NTK) theory. To address this, we introduce the Neural Zeroth-order Kernel (NZK) to describe model evolution in function space under ZO updates. For linear models, we prove that the expected NZK remains constant throughout training and depends explicitly on the first and second moments of the random perturbation directions. This invariance yields a closed-form expression for model evolution under squared loss. We further extend the analysis to linearized neural networks. Interpreting ZO updates as kernel gradient descent via NZK provides a novel perspective for potentially accelerating convergence. Extensive experiments across synthetic and real-world datasets (including MNIST, CIFAR-10, and Tiny ImageNet) validate our theoretical results and demonstrate acceleration when using a single shared random vector.

Figures & tables

Panel of Figure 1 — Figure 1: Comparison of losses in 2-D tasks under FO and ZO with varying $\sigma_{\bm{z}}$ for sampling. “Independent” indicates that $\bm{z}$ and $\mathcal{\bm{\zeta}}$ are sampled independently, while “Identical” denotes that $\bm{\zeta}$ remains the same as $\bm{z}$ .

Appendix figures & tables14 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 4: Comparison of the final linear models trained with FO and ZO after 16,000 iterations, with different

\sigma_{\bm{z}}

. The vectors

\bm{\zeta}

and

\bm{z}

are sampled independently.

Panel of Figure 5 — Figure 5: Evolution of linear models under FO and ZO in a 2-D fitting task. The vectors $\bm{\zeta}$ and $\bm{z}$ are independently sampled. (a) Evolution under FO. (b-d) Evolution under ZO with (b) $\sigma_{\bm{z}}=1$ , (c) $\sigma_{\bm{z}}=0.5$ , and (d) $\sigma_{\bm{z}}=1.5$ .

Panel of Figure 6 — Figure 6: Comparison of NTK and expected NZK with varying $\sigma_{\bm{z}}$ for the case of $d=2$ , using identical $\bm{\zeta}$ and $\bm{z}$ .

Panel of Figure 7 — Figure 7: Comparison of linear model evolution under FO and ZO with different $\sigma_{\bm{z}}$ for $d=2$ , using identical $\bm{\zeta}$ and $\bm{z}$ .

Panel of Figure 8 — Figure 8: Comparison of linear model evolution under FO and ZO with varying $d$ , projected into 2-D space. Identical $\bm{\zeta}$ and $\bm{z}$ are used.

Panel of Figure 9 — Figure 9: Comparison of the loss for the linear model under FO and ZO, with varying $d$ and identical $\bm{\zeta}$ and $\bm{z}$ .

Panel of Figure 10 — Figure 10: Comparison of NTK and expected NZK for the linear model under FO and ZO, with different values of $d$ and identical $\bm{\zeta}$ and $\bm{z}$ .

Figure 11: Comparison of losses in 2-D fitting tasks under FO and ZO with different distributions, while keeping

\bm{\zeta}

and

\bm{z}

identical.

Panel of Figure 12 — Figure 12: Comparison of linear model evolution under FO and ZO with different distributions for $d=2$ . Identical $\bm{\zeta}$ and $\bm{z}$ are used. The second row shows similar performance.

Figure 13: Comparison of the final linear models under FO and ZO after 16,000 iterations with different distributions, for

d=2

, using identical

\bm{\zeta}

and

\bm{z}

Panel of Figure 14 — Figure 14: Comparison of NTK and expected NZK with different distributions for $d=2$ , and identical $\bm{\zeta}$ and $\bm{z}$ are taken.

Figure 15: Comparison of losses for the linear model under FO and ZO in 24-dimensional classification tasks on MNIST, with identical

\bm{\zeta}

and

\bm{z}

Figure 16: Comparison of NZK for the 24-dimensional linear model under FO and ZO for MNIST classification, with identical $\bm{\zeta}$ and $\bm{z}$ .

Zeroth-Order Optimization

Zeroth-order optimization uses function values or comparisons, rather than gradients, to optimize objectives when differentiation is unavailable or costly.

See all 86 papers

Learning Dynamics of Zeroth-Order Optimization: A Kernel Perspective
May 5, 2026Zhe Li, Bicheng Ying, Zidong Liu +1Zeroth-Order Optimization LLM Fine-Tuning
Department of Computing and Information Sciences Ph.D., Rochester Institute of Technology, Rochester, NY, USA · Google Inc., Los Angeles, CA, USA · ComboCurve Inc., Houston, TX, USA
Zeroth-Order Optimization at the Edge of Stability
Apr 16, 2026Minhak Song, Liang Zhang, Bingcong Li +3Edge of Stability Zeroth-Order Optimization
KAIST · KRAFTON · ETH Zurich +2
Turning Stale Gradients into Stable Gradients: Coherent Coordinate Descent with Implicit Landscape Smoothing for Lightweight Zeroth-Order Optimization
May 14, 2026Chen Liang, Xiatao Sun, Qian Wang +1Zeroth-Order Optimization
Department of Computer Science, Yale University, New Haven, USA.

May 5, 2026J/K move · Enter open · S save

Learning Dynamics of Zeroth-Order Optimization: A Kernel Perspective

Zhe Li, Bicheng Ying, Zidong Liu, Haibo Yang

Department of Computing and Information Sciences Ph.D., Rochester Institute of Technology, Rochester, NY, USA · Google Inc., Los Angeles, CA, USA · ComboCurve Inc., Houston, TX, USA

Zeroth-Order Optimization LLM Fine-Tuning Neural Network Training Dynamics Neural Tangent Kernel

Open paper AskPDF arXiv

Classical optimization theory establishes that zeroth-order (ZO) algorithms suffer from a dimension-dependent slowdown, with convergence rates typically scaling with the model dimension compared to first-order methods. However, in contrast to these theoretical expectations, a growing body of recent work demonstrates the successful application of ZO methods to fine-tuning Large Language Models (LLMs) with billions of parameters. To explain this paradox, we derive the one-step learning dynamics of ZO SGD, where the empirical Neural Tangent Kernel (eNTK) naturally emerges as the key term governing the learning behavior. Inspection of the eNTK produced by ZO SGD reveals that each element corresponds to the inner product of neural tangent vectors projected onto a random low-dimensional subspace. Thus, by invoking the Johnson-Lindenstrauss Lemma, our analysis shows that the fidelity of the ZO eNTK is governed primarily by the number of perturbations. Crucially, the approximation error depends on the model output size rather than the massive parameter dimension. This dimension-free property provides a theoretical justification for the scalability of ZO methods to LLMs finetuning tasks. We believe that this kernel-based framework offers a novel perspective for understanding ZO methods within the context of learning dynamics.

Abstract

Zeroth-Order Optimization

Explore similar work

Learning Dynamics of Zeroth-Order Optimization: A Kernel Perspective

Zeroth-Order Optimization at the Edge of Stability

Turning Stale Gradients into Stable Gradients: Coherent Coordinate Descent with Implicit Landscape Smoothing for Lightweight Zeroth-Order Optimization