🤖 machine learning

Position: Zeroth-Order Optimization in Deep Learning Is Underexplored, Not Underpowered

This paper argues that zeroth-order optimization in deep learning is not inherently unscalable but rather underexplored due to myopic design practices, advocating for a paradigm shift toward subspace methods, system-aware advantages, and de-obfuscated evaluations to unlock its potential for large-scale, resource-efficient learning.

Original authors: Sijia Liu, Yicheng Lang, Soumyadeep Pal, Changsheng Wang, Yancheng Huang, Chongyu Fan, James Diffenderfer, Bhavya Kailkhura, Yihua Zhang

Published 2026-05-18

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Sijia Liu, Yicheng Lang, Soumyadeep Pal, Changsheng Wang, Yancheng Huang, Chongyu Fan, James Diffenderfer, Bhavya Kailkhura, Yihua Zhang

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 Idea: It's Not Broken, We Just Haven't Learned How to Use It Yet

Imagine you are trying to find the lowest point in a giant, pitch-black valley (this represents training a complex AI model).

The Old Way (First-Order Optimization): You have a magical flashlight that not only shows you the ground but also tells you exactly which way is "down" (the gradient). This is how most AI is trained today. It's fast, but the flashlight requires a massive battery (huge computer memory) and breaks easily if you try to use it on weird, non-standard terrain (like simulators or black-box systems).
The "Zeroth-Order" (ZO) Way: You don't have a flashlight. You only have a stick. To figure out which way is down, you poke the ground in different directions with the stick. If the ground feels lower, you step that way. This is Zeroth-Order (ZO) optimization. It uses very little memory and works on any terrain, even if you can't see the ground.

The Problem: For a long time, people thought the "stick method" was too slow and clumsy for big mountains. They believed it would take forever to poke the ground enough times to find the bottom.

The Paper's Claim: The authors say, "Stop! You're judging the stick method unfairly." They argue that ZO isn't weak; it's just underexplored. We've been using the stick in the wrong way (poking every single inch of the ground one by one). If we change how we poke, we can make it just as powerful as the flashlight, but without the heavy battery.

The Six Key Points (The "How-To" Guide)

The authors propose six new ways to think about using the "stick" to make it work better.

1. Don't Poke Randomly Everywhere (P1 & P2)

The Analogy: Imagine you are trying to find the best spot to plant a tree in a massive field.

The Mistake: Most people poke the ground randomly in every direction at once. This creates a lot of "noise" (confusion) and requires poking millions of times.
The Fix: The paper says, "Be smarter about where you poke." Instead of poking everywhere, poke in specific, structured patterns. Also, realize that poking more times reduces confusion but costs more time. You need to find the perfect balance between "how many pokes" and "how clear the signal is."

2. Use a Compass, Not Just a Stick (P3)

The Analogy: When you poke the ground, you are actually measuring the slope in one specific direction (like a compass needle).

The Insight: The authors say we should stop pretending we are just guessing. We should treat these "pokes" as measuring the slope in a specific direction. If we compare our "stick method" against a theoretical "perfect compass" (called a directional derivative), we can see exactly how good our method really is. This helps us stop blaming the tool when the task is actually just really hard.

3. Zoom In on the Important Stuff (P4)

The Analogy: Imagine trying to navigate a city by looking at a map of the entire planet. It's overwhelming.

The Fix: Instead of poking the whole planet, zoom in on a small neighborhood (a subspace). The authors suggest that AI models often have hidden patterns where only a few directions matter. If we only poke in those specific "neighborhoods" (low-dimensional subspaces), we get a clear answer with far fewer pokes. It's like navigating a city by only looking at the main streets instead of every single alley.

4. The "Invisible Team" Advantage (P5)

The Analogy: Imagine a team of workers trying to move a heavy couch.

The Old Way (Flashlight): They all need to see the exact same blueprint and talk constantly to coordinate. This takes a lot of time and bandwidth.
The ZO Way: Because the "stick method" only requires sending a single number (like "it's lower here!") rather than a whole blueprint, the workers can communicate much faster. They can even use a shared secret code (a random seed) to know where to poke without talking. This makes ZO optimization incredibly fast for teams working on different computers, and it saves a lot of energy.

5. Don't Blame the Tool for a Too-Easy Task (P6)

The Analogy: Imagine a student taking a test.

The Issue: Sometimes, the teacher gives the student a cheat sheet (called task alignment) that makes the test super easy. The student gets an A, but you don't know if they are smart or just lucky.
The Fix: The authors say, "Stop giving the cheat sheet!" We need to test the "stick method" on hard problems where the cheat sheet isn't allowed. If the method still works, then we know the tool is actually powerful. If it fails, we know the tool needs work. This stops us from thinking the tool is great just because the test was rigged.

The Call to Action: What Should We Do Next?

The authors aren't just complaining; they are giving a roadmap for the future:

Change the Rules of the Game: Stop testing these methods with "cheat sheets" (task alignment) and without measuring how many "pokes" (queries) it takes. We need fair tests.
Stop Poking the Whole World: Move away from poking every single parameter. Start poking in smaller, smarter groups (subspaces) or use "spectral" tricks to find the most important directions.
Build New Tools for the Stick: We are currently trying to fit the "stick method" into tools built for the "flashlight." We need to build new computer systems designed specifically for the stick method. These systems would be lighter, faster, and work on cheaper computers.
Look Beyond AI: This method isn't just for AI. It's perfect for things where you can't use a flashlight at all, like:
- Quantum Computers: Where the laws of physics make "flashlights" (gradients) impossible to use.
- Scientific Simulators: Where you are testing a physical model (like a bridge or a weather system) and can't mathematically calculate the slope.

The Bottom Line

The paper argues that Zeroth-Order optimization is a Ferrari that we've been driving in a parking lot. We've been using it clumsily, thinking it's slow and weak. But if we build the right roads (systems), drive in the right lanes (subspaces), and stop using cheat sheets (task alignment), it turns out to be a incredibly powerful, memory-efficient, and scalable way to train the next generation of AI.

Technical Summary: Zeroth-Order Optimization in Deep Learning Is Underexplored, Not Underpowered

1. Problem Statement

Zeroth-order (ZO) optimization, which approximates gradients using finite differences of function evaluations without backpropagation (BP), has regained attention for its memory efficiency and applicability to black-box or gray-box pipelines. Despite these advantages, ZO methods are frequently dismissed as fundamentally unscalable for deep learning due to high estimator variance and unfavorable query complexity.

The paper argues that this skepticism is misplaced. The perceived limitations of ZO optimization do not stem from intrinsic weaknesses of gradient-free learning but from "myopic development practices." Specifically, the community has overemphasized estimator-centric designs operating in the full parameter space with element-wise perturbations. This narrow focus has obscured broader algorithmic, systems-level, and evaluation opportunities that could unlock the scalability of ZO methods.

2. Methodology and Positioning Framework

Rather than proposing a single new algorithm, the paper articulates a comprehensive positioning framework consisting of six arguments (P1–P6) spanning the algorithmic, systems, and evaluation stacks. These positions reframe the feasibility boundaries and opportunities for ZO optimization.

Foundations and Feasibility Boundaries (P1–P3)

The authors first revisit the theoretical limits of current estimator-centric designs:

(P1) Random Direction Choice Matters: The choice of perturbation direction $u$ is critical. While standard Gaussian or Bernoulli vectors are common, they result in variance scaling linearly with dimension $d$ . The paper highlights that structured designs (e.g., sparse or preconditioned perturbations) can reduce variance but often introduce computational or query overheads that must be weighed.
(P2) Query-Variance Tradeoff: Variance reduction cannot be considered in isolation. Increasing the number of queries (e.g., via mini-batching) reduces variance but increases cost. The paper argues that effective ZO optimization must achieve sublinear query cost growth relative to problem dimension, avoiding the linear scaling of coordinate-wise estimators.
(P3) Directional-Derivative Viewpoint: The finite-difference estimator should be benchmarked against the directional derivative (DD) baseline (forward gradients). The DD provides a principled upper bound on performance and helps disentangle whether failures are due to the ZO method or the inherent difficulty of the task.

Opportunities for Advancement (P4–P6)

The paper then proposes three underexplored directions to advance ZO optimization:

(P4) Subspace and Spectral View: Instead of operating in the full $d$ -dimensional space, ZO methods should leverage subspace projection (e.g., $S$ -RGE). By projecting perturbations into a low-dimensional subspace ( $r \ll d$ ), variance is reduced by a factor of $r$ . This approach connects ZO to spectral optimization methods (like Muon), exploiting the low-rank structure often found in deep model gradients.
(P5) System-Level Simplicity: The "forward-only" nature of ZO is a systems advantage, not just a memory saver. It enables:
- Communication Efficiency: In distributed settings, workers can transmit only scalar finite-difference values and shared random seeds, reconstructing perturbation vectors locally without transmitting full vectors.
- Pipeline Parallelism: Eliminating backpropagation removes the tight coupling between forward and backward passes, allowing for unidirectional schedules with near-zero "pipeline bubbles."
- Privacy: The inherent stochasticity of ZO (via Gaussian perturbations) offers natural differential privacy benefits without requiring explicit noise injection.
(P6) Task-Aligned De-obfuscation: Current successes in ZO fine-tuning often rely on task alignment (using prompts to align downstream tasks with pre-training objectives). The paper argues this acts as an implicit obfuscation, making it difficult to assess the true optimization power of ZO. Evaluations must explicitly compare performance with and without task alignment to avoid attributing gains to the optimizer when they stem from task simplification.

3. Key Contributions and Evidence

The paper provides a structured critique of the current state of ZO research and offers a roadmap for future work:

Empirical Analysis of Recent Works: The authors analyze recent papers (e.g., from ICML'25, NeurIPS'25, ICLR'26) and find that while most address (P1) via variance reduction, they largely ignore (P2) (query tradeoffs) and (P3) (DD baselines). Table 1 in the paper demonstrates that few works simultaneously satisfy all three foundational positions.
De-obfuscation Experiments: Figure 2 presents fine-tuning results on SST-2, RTE, and WiC tasks using models like Gemma2-2B. The data shows that ZO methods (e.g., MeZO, Sparse-MeZO) experience significant accuracy drops when task alignment is removed. Furthermore, the relative ranking of methods changes between aligned and unaligned settings, confirming that task alignment can obscure the intrinsic capabilities of different ZO algorithms.
Actionable Calls to Action (A1–A5): The paper outlines concrete steps for the community:
- A1: Establish rigorous evaluation protocols with fixed query budgets and forward-gradient baselines.
- A2: Move beyond full-space optimization by integrating subspace and spectral methods, and consider hybrid FO-ZO approaches.
- A3: Explore generative models (e.g., diffusion models) as learned gradient estimators to denoise ZO estimates.
- A4: Build ZO-native system stacks rather than porting ZO to FO-centric frameworks (like DeepSpeed). This includes prioritizing perturbation parallelism and dense pipeline scheduling.
- A5: Broaden applications to inference-accelerated stacks (e.g., vLLM) and quantum/hybrid quantum-classical optimization, where ZO is a native paradigm.

4. Results and Claims

The paper does not present a new SOTA algorithm but rather a position paper that reframes the discourse. Its primary "results" are analytical:

Reframing Limitations: It demonstrates that scalability barriers are often artifacts of design choices (full-space, estimator-centric) rather than fundamental impossibilities.
System Synergy: It argues that ZO's simplicity aligns naturally with distributed and resource-constrained environments, offering advantages in communication and pipeline efficiency that FO methods cannot match.
Evaluation Bias: It provides evidence that current benchmarks may overstate ZO performance due to task alignment, urging a shift toward more honest, de-obfuscated evaluation.

5. Significance and Conclusion

The paper claims that ZO optimization is underexplored, not underpowered. By shifting focus from merely refining gradient estimators to leveraging subspace structures, system-level simplicity, and rigorous evaluation, the community can unlock a viable path for large-scale, resource-efficient learning.

The authors conclude that ZO optimization has the potential to transform from a niche workaround into a practical paradigm for training modern AI systems in constrained, hybrid, and emerging environments (e.g., digital twins, physics-informed systems, and quantum computing). The significance lies in democratizing access to large-model training (by reducing memory and hardware requirements) and enabling learning in non-differentiable systems where backpropagation is impossible. The paper calls for a systematic rethinking of the algorithmic, systems, and evaluation stacks to fully realize these potential gains.