🤖 machine learning

Learning Dynamics of Zeroth-Order Optimization: A Kernel Perspective

This paper resolves the paradox of zeroth-order optimization's success in fine-tuning large language models by demonstrating that its learning dynamics are governed by an empirical Neural Tangent Kernel whose approximation error depends on the model output size rather than the massive parameter dimension, thereby explaining its scalability.

Original authors: Zhe Li, Bicheng Ying, Zidong Liu, Haibo Yang

Published 2026-05-06

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Zhe Li, Bicheng Ying, Zidong Liu, Haibo Yang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Mystery: The "Blind" vs. The "Sighted"

Imagine you are trying to find the lowest point in a vast, foggy valley (this is the goal of training an AI model).

First-Order (FO) Methods: These are like a hiker with a compass and a map. They can see exactly which way is "down" (the gradient) and walk straight there. This is fast and efficient, but it requires carrying a heavy map (computing gradients), which is impossible if the valley is too huge or if you are in a "black box" where you can't see the map.
Zeroth-Order (ZO) Methods: These are like a blind hiker. They don't have a compass. Instead, they take a small step forward, check if they are lower, take a step backward, and check again. By comparing these two points, they guess which way is down. This is "memory-efficient" because they don't need the heavy map, but traditional math says this should be incredibly slow, especially if the valley is huge (high-dimensional).

The Paradox:
For years, math textbooks told us that the "blind hiker" (ZO) would take forever to find the bottom if the valley was massive (like modern Large Language Models with billions of parameters). Yet, in the real world, researchers have successfully used this "blind" method to fine-tune these massive models. How is this possible?

The Paper's Solution: The "Shadow" Analogy

The authors solve this mystery by looking at the problem not through the lens of "steps taken," but through the lens of "learning dynamics" (how the model's confidence changes).

They use a tool called the Neural Tangent Kernel (eNTK). Think of the eNTK as a shadow cast by the model's learning process.

The "Sighted" hiker (FO) casts a perfect, detailed shadow of the terrain.
The "Blind" hiker (ZO) casts a shadow that is a projected, slightly blurry version of the perfect one.

The paper argues that the "blind" method works because it doesn't need to see the entire massive valley to cast a useful shadow. It only needs to project the shadow onto a random, low-dimensional slice of the world.

The Magic Trick: The "Johnson-Lindenstrauss" Lemma

The paper relies on a mathematical concept called the Johnson-Lindenstrauss (JL) Lemma. Here is the analogy:

Imagine you have a giant, complex 3D sculpture (the model with billions of parameters). You want to take a photo of it, but your camera can only take 2D pictures.

Old Theory: You thought you needed a camera with a sensor as big as the sculpture to get a good picture. If the sculpture is huge, the photo would be blurry and useless.
The Paper's Insight: The JL Lemma says that if you take a photo from a random angle, you can actually capture the essential relationships of the sculpture perfectly, even if the photo is much smaller than the sculpture.

The Key Discovery:
The quality of this "blind" photo (the ZO learning) depends on how many random angles (perturbations) you take, not on how big the sculpture is.

The "Perturbations" (P): These are the number of times the blind hiker pokes the ground to guess the direction.
The "Output Size" (V): This is the size of the final answer the model gives (e.g., the vocabulary size of a language model).

The paper proves that as long as you poke the ground enough times (increase P), the "blind" hiker's path will look almost identical to the "sighted" hiker's path. Crucially, the number of pokes needed depends on the size of the answer (V), not the size of the model (d).

Three Main Takeaways

Count the Pokes, Not the Size:
The success of the "blind" method isn't about the massive size of the AI model (which could be billions of parameters). It's about the number of random guesses (perturbations) you make. If you make enough guesses, the model learns just as well as if it had a map.
The Shape of the Guess Doesn't Matter:
Does it matter if the "blind hiker" pokes the ground in a smooth, continuous circle (Gaussian distribution) or in sharp, binary jumps (Rademacher distribution)? The paper shows it doesn't matter much. Both work almost equally well. The "blind" method is robust; it doesn't care about the specific shape of the noise, as long as there is enough of it.
Why It Works on Huge Models:
This explains why ZO works on Large Language Models (LLMs). Even though the model has billions of parameters (a huge d), the output vocabulary is relatively small (a moderate V). Because the "blind" method's accuracy depends on V and not d, it remains efficient and effective even for the biggest models.

The Bottom Line

This paper changes the story. It says the "curse of dimensionality" (the idea that big models are too hard for blind methods) is a myth when you look at the learning process correctly.

By viewing the learning process as a geometric projection, the authors show that a "blind" optimizer can learn just as effectively as a "sighted" one, provided you give it enough random samples. It's not about the size of the mountain; it's about how many times you look at it from different angles.

Technical Summary: Learning Dynamics of Zeroth-Order Optimization: A Kernel Perspective

Problem Statement

Classical optimization theory posits that Zeroth-Order (ZO) algorithms suffer from a "curse of dimensionality," where convergence rates scale linearly with the model dimension $d$ . This theoretical limitation suggests that ZO methods should be prohibitively slow for high-dimensional models, such as Large Language Models (LLMs) with billions of parameters. However, recent empirical breakthroughs contradict this pessimistic outlook, demonstrating that ZO methods can successfully fine-tune LLMs with performance competitive to First-Order (FO) methods. The central problem addressed by this paper is to resolve this paradox: why do ZO methods scale effectively to massive parameter spaces despite theoretical bounds suggesting otherwise?

Methodology

The authors propose a novel framework that analyzes ZO optimization through the lens of learning dynamics and the Empirical Neural Tangent Kernel (eNTK), rather than focusing solely on parameter-space convergence or scalar loss values.

Derivation of ZO Learning Dynamics: The paper derives the one-step learning dynamics of ZO Stochastic Gradient Descent (SGD). By applying a Taylor expansion to the log-probability of model predictions, the authors show that the update rule is governed by a projected eNTK.
Kernel Projection Formulation: The core theoretical insight is that the effective kernel induced by ZO optimization (termed ZO-eNTK) is a geometric projection of the standard FO eNTK onto a random low-dimensional subspace spanned by the perturbation vectors.
Johnson-Lindenstrauss (JL) Lemma Application: The authors invoke the Johnson-Lindenstrauss Lemma to analyze the fidelity of this projection. They establish that the approximation error between the ZO-eNTK and the true FO-eNTK depends on the preservation of inner products in high-dimensional spaces.
Theoretical Bounds: The analysis derives rigorous bounds showing that the approximation error $\epsilon$ scales as $O(\sqrt{\ln V / P})$ , where $V$ is the output vocabulary size and $P$ is the number of perturbations. Crucially, this bound is independent of the massive model parameter dimension $d$ .
Empirical Validation: The framework is validated through experiments on:
- LeNet (MNIST): Visualizing the convergence of ZO-eNTK to FO-eNTK as $P$ increases, using heatmaps and Frobenius norm errors.
- OPT Models (SST-2): Testing models ranging from 125M to 1.3B parameters to verify dimension-independence.
- Distribution Comparison: Comparing Gaussian and Rademacher perturbation distributions.

Key Contributions

1. Theoretical Resolution of the ZO Paradox

The paper provides a theoretical justification for the scalability of ZO methods to LLMs. By shifting the analysis from parameter space to function space (via eNTK), the authors demonstrate that the fidelity of ZO updates is governed by the output vocabulary size $V$ and the number of perturbations $P$ , rather than the model dimension $d$ . This "dimension-free" property explains why ZO methods remain efficient even when $d$ is in the billions.

2. The Role of Perturbation Count ( $P$ )

The analysis identifies the number of perturbations as the primary factor governing the fidelity of the ZO-eNTK. Theoretical bounds and empirical results show that increasing $P$ reduces the kernel approximation error at a rate of $O(1/\sqrt{P})$ . Once $P$ exceeds a threshold determined by $V$ , the ZO learning trajectory aligns closely with the FO trajectory.

3. Distribution Robustness

The paper investigates the impact of perturbation distributions (Gaussian vs. Rademacher). While classical optimization views often suggest differences in variance reduction, the kernel-based analysis reveals that both distributions yield comparable concentration constants in the context of the JL Lemma. Empirical results confirm that the choice of distribution has a negligible impact on long-term convergence, provided $P$ is sufficient.

4. Input Similarity Sensitivity

The study highlights that the convergence rate of the ZO-eNTK approximation is sensitive to the semantic similarity between input pairs. Pairs with high similarity (e.g., semantically similar digits or text) converge to the FO ground truth faster than structurally distinct pairs, though both eventually converge as $P$ increases.

Results

Convergence of eNTK: Experiments on LeNet show that as $P$ increases from 1 to 125, the ZO-eNTK visually and numerically recovers the block-diagonal structure of the FO-eNTK. The relative Frobenius norm error decreases monotonically.
Dimension Independence: In experiments with OPT models (125M, 350M, 1.3B), the threshold of $P$ required to recover FO dynamics remained virtually constant despite the model dimension $d$ increasing by an order of magnitude. This confirms that the learning dynamics are decoupled from $d$ .
Output Size Scaling: A controlled synthetic experiment varying the output size $V$ (from 2 to 1000) while keeping $P$ fixed showed that the approximation error increases at a rate consistent with $\sqrt{V}$ , validating the theoretical bound.
Distribution Parity: The convergence curves for Gaussian and Rademacher distributions were nearly indistinguishable across all metrics (Frobenius Norm, CKA, and Spectral Distance), supporting the claim that simple binary perturbations are sufficient for effective kernel approximation.

Significance and Claims

The paper claims to offer a novel perspective for understanding derivative-free learning dynamics by complementing the existing optimization-centric view with a kernel-based framework.

Theoretical Justification: The primary significance is the provision of a rigorous theoretical explanation for the empirical success of ZO fine-tuning in LLMs, resolving the discrepancy between worst-case theoretical bounds (dependent on $d$ ) and practical performance.
Practical Guidance: The findings suggest that practitioners should focus on tuning the number of perturbations $P$ relative to the output vocabulary size $V$ , rather than worrying about the massive parameter count $d$ .
Limitations and Scope: The authors modestly note that their analysis relies on the "lazy training" regime (where features remain stable), which is typical for fine-tuning but may not hold for training-from-scratch scenarios. They also acknowledge that the framework currently addresses standard supervised fine-tuning and may require extension for tasks with strong sequential dependencies (e.g., long-horizon reasoning) where the effective output dimension grows with sequence length.

In summary, the paper argues that the success of ZO optimization in high-dimensional settings is not a fluke but a consequence of the geometric properties of the Neural Tangent Kernel, which allows for dimension-free approximation through random projections.