🤖 machine learning

On Adaptivity in Zeroth-Order Optimization

This paper demonstrates that standard adaptive zeroth-order optimizers like ZO-Adam offer no convergence advantage over ZO-SGD for memory-constrained LLM fine-tuning due to a lack of coordinate-wise gradient heterogeneity in high dimensions, leading to the proposal of MEAZO, a memory-efficient alternative that tracks only a single scalar for global step size adaptation while matching performance and improving robustness.

Original authors: Hassan Dbouk, Nidham Gazagnadou, Matthias Reisser, Christos Louizos

Published 2026-05-06

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Hassan Dbouk, Nidham Gazagnadou, Matthias Reisser, Christos Louizos

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 Picture: Tuning a Giant Radio Without a Manual

Imagine you have a massive, complex radio with millions of knobs (these are the "parameters" of a Large Language Model, or LLM). You want to tune it to play a specific song perfectly (fine-tuning the model).

Usually, to tune a radio, you need a manual that tells you exactly which way to turn each knob and how much. In AI, this manual is called a gradient. Calculating this manual requires a lot of memory and computing power, which is expensive and slow.

Zeroth-Order (ZO) Optimization is a clever trick: instead of reading the manual, you just nudge the knobs randomly, listen to the result, and see if the music got better or worse. You do this by pushing the knobs forward and backward to guess the direction. It's much cheaper on memory, but it's "noisy" because you are guessing.

The Problem: The "Over-Engineered" Compass

For a long time, researchers thought that because this guessing game is noisy, you needed a super-smart, memory-hungry compass to help you. This is what Adaptive Optimizers (like ZO-Adam) do. They try to remember the history of every single knob to decide how fast to turn it. They keep a separate "memory log" for every single one of the millions of knobs.

The Paper's Big Discovery:
The authors found that in high-dimensional settings (like giant AI models), this super-smart compass is actually useless.

The Analogy: Imagine you are in a foggy field trying to find the bottom of a valley.
- First-Order (Standard AI): You have a clear map showing that the ground slopes steeply down to the left but is flat to the right. You need a different strategy for each direction.
- Zeroth-Order (The Guessing Game): Because you are guessing by nudging randomly in a huge, foggy space, the "noise" of your guess is so loud that it drowns out the specific details of the terrain. The signal looks the same in every direction. It's like the fog is so thick that the ground looks perfectly flat and uniform everywhere.
The Result: Because the "terrain" looks the same in every direction, keeping a separate memory log for every single knob is a waste of time and memory. The fancy "adaptive" methods (ZO-Adam) don't actually help you get to the bottom of the valley any faster than a simple method (ZO-SGD). In fact, they just make your backpack heavier.

The Solution: MEAZO (The Minimalist Compass)

Since the fancy compass is unnecessary, the authors built a new tool called MEAZO.

How it works: Instead of tracking millions of individual logs for every knob, MEAZO tracks just one single number for the whole group. It asks, "On average, how much did the music change when we nudged everything?"
The Benefit: It keeps the "smart" part of the adaptive method (adjusting the speed of the nudge based on how rough the terrain feels) but throws away the heavy baggage.
The Analogy: Imagine you are hiking.
- ZO-Adam: You carry a GPS, a barometer, a compass, and a detailed map for every single step you take. It's heavy, and you get tired.
- ZO-SGD: You just walk forward. It's light, but if the path gets rocky, you might trip.
- MEAZO: You carry a simple pedometer that tells you the average steepness of the path. If the path gets rocky, you slow down. If it's smooth, you speed up. You don't need a map for every rock; you just need to know the general vibe of the trail.

What the Experiments Showed

The team tested this on real Large Language Models (like Llama and Qwen) and synthetic math problems.

Performance: When they tuned the settings correctly, the simple method (ZO-SGD) performed just as well as the fancy method (ZO-Adam).
Memory: MEAZO used the same tiny amount of memory as the simple method, whereas the fancy method used much more.
Robustness (The "Safety Net"): This is the most important finding. While the simple method works great if you pick the perfect walking speed, it falls apart if you pick a speed that is too fast or too slow. The fancy methods (and MEAZO) are much more forgiving. If you pick a "bad" speed, MEAZO still gets you to the destination without crashing. It's like a car with cruise control that adjusts automatically to hills, whereas the simple car just keeps going at a fixed speed and might crash into a bump.

Summary

The Myth: "We need complex, memory-heavy adaptive tools to make zeroth-order AI training work well."
The Reality: In high-dimensional AI models, the noise makes the terrain look uniform, so complex tools are a waste of memory.
The Fix: MEAZO is a new tool that tracks just one global number instead of millions. It uses very little memory (like the simple method) but is much more stable and forgiving with settings (like the complex method).

This allows researchers to fine-tune massive AI models on devices with limited memory (like edge devices) without needing supercomputers, while still getting stable, high-quality results.

Technical Summary: On Adaptivity in Zeroth-Order Optimization

Problem Statement

The paper addresses the challenge of memory-constrained fine-tuning of Large Language Models (LLMs). While backpropagation is the standard for fine-tuning, it requires significant memory for activation caching and high-precision floating-point operations. Zeroth-order (ZO) optimization has emerged as a memory-efficient alternative, approximating gradients via forward passes on randomly perturbed parameters. However, ZO methods suffer from high variance, leading to slower convergence compared to first-order (FO) methods.

Recent work has attempted to mitigate this variance by introducing adaptive ZO optimizers (e.g., ZO-Adam), which mimic FO adaptive methods by tracking first and second moments of gradients per coordinate. The authors question the efficacy of this approach, hypothesizing that the coordinate-wise heterogeneity required for adaptive methods to succeed may be absent in high-dimensional ZO settings.

Methodology and Analysis

Theoretical Analysis of ZO Gradients

The authors analyze the statistical properties of ZO gradient estimators in high dimensions. They demonstrate that due to the isotropic nature of random perturbations, ZO gradient estimates lack the coordinate-wise heterogeneity found in FO gradients.

Proposition 3.1: The authors prove that the expected squared ZO gradient is dominated by a global term dependent on the squared norm of the true gradient, rather than individual coordinate values. Specifically, the bias introduced by the estimator scales with $1/q$ (where $q$ is the number of noise samples) and becomes coordinate-agnostic in high dimensions ( $q \ll d$ ).
Implication: Adaptive mechanisms that track per-coordinate statistics (like Adam's second moment) are misaligned with the underlying statistics of ZO gradients, rendering them memory-inefficient without providing convergence benefits.

Proposed Method: MEAZO

Leveraging the insight that global step size adaptation is sufficient, the authors propose MEAZO (Memory-Efficient Adaptive Zeroth-order optimizer).

Design: Unlike ZO-Adam, which maintains a vector of second moments for every parameter, MEAZO tracks only a single scalar representing the global squared norm of the projected gradient.
Update Rule: The update scales the global step size by this scalar, effectively adapting the learning rate based on global curvature without per-parameter memory overhead.
Grouped Extension: MEAZO naturally extends to grouped (block-coordinate) ZO settings, maintaining a scalar per block rather than per parameter, further reducing memory while capturing block-level heterogeneity.

Theoretical Guarantees

The paper provides formal convergence guarantees for MEAZO under standard assumptions (L-smoothness, bounded variance, bounded gradients).

The analysis treats the ZO gradient as an unbiased estimator of a smoothed objective function.
Theorem 4.7: Establishes a convergence rate for MEAZO that matches the standard rates for adaptive SGD in the presence of affine variance bounds. The convergence rate is shown to be $O(\frac{1}{T} + \frac{\sigma^2}{T} + \frac{d}{q}\sigma^2 + \frac{d^2}{q}\epsilon^2)$ , confirming that the method converges to a stationary point with a noise neighborhood size dependent on the number of samples $q$ and perturbation magnitude $\epsilon$ .

Experimental Results

Synthetic Experiments

Second Moment Behavior: In synthetic quadratic problems, the authors observe that as dimensionality increases, the second-moment vector of ZO-Adam collapses to a single value (global norm), whereas FO-Adam maintains distinct coordinate-wise values. This empirically validates the theoretical claim that per-coordinate adaptation is redundant in high-dimensional ZO settings.
Robustness: MEAZO demonstrates enhanced robustness to step size choices compared to ZO-SGD, particularly in heterogeneous block-structured settings, matching the stability of ZO-Adam.

LLM Fine-Tuning

Experiments were conducted on multiple model families (Llama-3.2, Qwen-3, Ministral) and tasks (XSum, SST-2, SQuAD) using both LoRA and prompt tuning.

Performance vs. Memory:
- ZO-SGD vs. ZO-Adam: With proper step size tuning, ZO-SGD matches or surpasses ZO-Adam in high-dimensional LoRA fine-tuning, confirming that coordinate-wise adaptivity offers limited benefit.
- MEAZO Performance: MEAZO achieves performance comparable to ZO-Adam but with a memory footprint equivalent to ZO-SGD (tracking one scalar vs. a full vector).
Robustness: While well-tuned ZO-SGD performs well, it is brittle to suboptimal step sizes. MEAZO retains the robustness of adaptive methods (widening the stable learning rate window) without the memory cost.
Grouped Settings: In grouped ZO settings, MEAZO adapts to group-specific statistics (e.g., earlier layers showing higher sensitivity), maintaining stable convergence where grouped ZO-SGD can diverge.

Key Contributions

Theoretical Insight: The paper establishes that ZO gradients in high dimensions are essentially homogeneous, rendering per-coordinate adaptive mechanisms (like those in ZO-Adam) memory-inefficient and theoretically unnecessary for convergence.
Algorithmic Innovation: The introduction of MEAZO, a scalar-based adaptive ZO optimizer that achieves global step size adaptation with negligible memory overhead.
Empirical Validation: Comprehensive experiments across diverse LLMs and tasks demonstrating that MEAZO matches the performance of adaptive baselines (ZO-Adam) while maintaining the memory efficiency of non-adaptive baselines (ZO-SGD).
Convergence Analysis: Formal convergence guarantees for MEAZO under non-convex settings, bridging the gap between adaptive SGD theory and zeroth-order optimization.

Significance and Claims

The authors claim that their work re-evaluates the necessity of complex adaptive mechanisms in zeroth-order optimization. They argue that for high-dimensional LLM fine-tuning, the primary advantage of adaptivity lies not in per-coordinate scaling, but in global step size robustness.

The significance of MEAZO is framed around memory-constrained environments (e.g., edge devices). By achieving the robustness of adaptive methods with the memory efficiency of SGD, MEAZO enables more researchers and practitioners with limited resources to participate in fine-tuning large models. The paper modestly concludes that while ZO-SGD is sufficient when perfectly tuned, MEAZO offers a practical, stable, and scalable alternative that mitigates the brittleness of step size selection without incurring memory penalties. Future work is suggested to refine convergence to exact stationary points and extend MEAZO to subspace ZO frameworks.