Zeroth-Order

Follow this topic Ask about this topic

Momentum

3 papers in the last four weeks, level with the four weeks before. 0.0% of all new papers.

Jul 6Week of Sep 21

Latest papers 33

Oct 1, 2026cs.LG

Trust the Direction, Search the Step: Zero-and-First-Order Methods for LLM Fine-Tuning

Step-size selection remains a central challenge in large-scale neural network optimization; conservative steps slow convergence, while aggressive steps can destabilize it. We combine \textbf{Z}ero-and-\textbf{F}irst-\textbf{O}rder optimization~(ZFO) and propose a lightweight framework that decouples direction selection from step-size. ZFO uses a trusted first-order optimizer to determine the direction and performs zeroth-order evaluations only along this one-dimensional subspace to choose how far to move. Using the current {gradient information} and two additional objective function evaluations, ZFO instances construct a local model of the objective function along the proposed direction and select a curvature-aware step within a bounded search interval. This yields an adaptive step-selection mechanism that costs less than a full line search. We provide theoretical guarantees to show that shared-sample evaluations produce reliable finite-difference curvature estimates, that the induced local model selects a near-optimal step along the search interval, and that ZFO converges to a neighborhood of a stationary point. Across the evaluated settings, language models and datasets, ZFO frequently improves optimization and final performance relative to fixed-step first-order baselines, with the magnitude and preferred local model depending on the objective. Our code is publicly available at: https://github.com/nizswan/Zeroth-First-Order-Framework.

Cristian McGee, El Houcine Bergou, Aritra Dutta

University of Central Florida Orlando, FL, USA · Mohammed VI Polytechnic University Ben Guerir, Morocco

Zeroth-Order Optimization Zeroth-Order Large Language Model Fine-Tuning Neural Network Optimization Model Fine-Tuning

Sep 29, 2026math.OC

A Parameter-Free Zeroth-Order Method with Covariance Matrix Adaptation and Effective Dimension

Zeroth-order optimization methods are essential for solving black-box problems where gradient information is unavailable or expensive to compute. This paper presents POEM-CMA, a novel parameter-free stochastic zeroth-order algorithm that extends the recent POEM method by integrating covariance matrix alignment and the notion of effective dimension. In contrast to traditional zeroth-order approaches that rely on isotropic random directions, POEM-CMA performs anisotropic sampling by constructing a covariance matrix from gradient estimates. This enables the algorithm to focus sampling efforts on the most informative directions. We introduce the use of the empirical effective dimension

d^* = \frac{\operatorname{tr}(\hatΣ)}{λ_{\max}(\hatΣ)}

, which reflects the intrinsic dimensionality of the problem and replaces the ambient dimension in both sampling and complexity analysis. We prove that POEM-CMA achieves a near-optimal convergence rate, requiring only

\tilde{\mathcal{O}}\left(\frac{d^* κ(\hatΣ) L^2 D_{\mathcal{X}}^2}{\varepsilon^2}\right)

stochastic zeroth-order oracle queries. The method remains fully parameter-free and demonstrates significant improvements over the original POEM in problems with low-rank structure where

d^* \ll d

. Numerical experiments on hinge-loss binary classification tasks using LibSVM datasets confirm the practical superiority of the proposed approach.

Alexander Sholokhov, Alexander Rogozin

Moscow Institute of Physics and Technology, Russia

Zeroth-Order Low-Rank Structure Covariance Poetry

Sep 28, 2026cs.LG

AIM-ZO: Activation-Informed Subspace Maintenance for Zeroth-Order LLM Fine-Tuning

Zeroth-order (ZO) optimization offers a memory-efficient alternative for LLM fine-tuning by estimating updates only from forward evaluations of perturbed parameters, without backpropagation or activation storage. However, in billion-parameter LLMs, isotropic perturbations often waste many forward evaluations on weakly informative directions. To make these evaluations more informative, existing ZO methods restrict perturbations to low-dimensional subspaces. Yet the quality of these subspaces is critical: overly compressed or poorly maintained spaces can miss useful update directions. To obtain a high-quality subspace for ZO updates, this paper proposes AIM-ZO, a ZO fine-tuning method based on Activation-Informed Subspace Maintenance. AIM-ZO uses forward activations as local directional information and continuously integrates them into a broad, evolving subspace over training. To access broader gradient-relevant structure while keeping individual perturbations low-dimensional, AIM-ZO activates only a smaller set of shared and sampled directions, decoupling the maintained width from the active width. We evaluate AIM-ZO across 5 LLMs and 11 downstream tasks under matched forward-evaluation budgets; its six-task average exceeds the strongest fully evaluated ZO baseline by 1.26 percentage points on OPT-2.7B and MeZO by 2.85 percentage points on OPT-30B. Our code is available at https://github.com/EkkoXy/AIM-ZO

Yue Xie, Zhi Zheng, Yunpeng Ba +5

Southern University of Science and Technology · National University of Singapore · Huawei Technologies Ltd. +1

Large Language Model Fine-Tuning Continual Fine-Tuning Model Fine-Tuning Zeroth-Order Subspace

Sep 27, 2026cs.LG

TerMeZO: Ternary Sparse Zeroth-Order Optimization for Fine-tuning BitNet Models at the Edge

Fine-tuning anguage models (LLMs) with first-order optimizers requires a memory several times larger than that required for inference. Memory-efficient zeroth-order optimization (MeZO) sidesteps this cost by estimating gradients from forward passes only. However, for BitNet architectures, a family of LLMs with ternary {-1,0,1} weights and 8-bit activations, fine-tuning requires updating full-precision latent weights, and thus the memory footprint of MeZO no longer matches that of inference. A promising solution is to finetune only a subset of the latent weights, but existing sparse zeroth-order (ZO) methods either ignore the ternary structure or require first-order gradient information to build a sparse mask, which is at odds with the purpose of ZO fine-tuning. We propose TerMeZO, a sparse MeZO scheme that exploits the geometry of the ternary quantizer itself to identify the latent weights that are more likely to change values during fine-tuning, at no additional data or memory cost. Our convergence analysis shows that TerMeZO can converge faster than full-parameter MeZO, owing to its optimized reduction of the fine-tuning effective dimension. We run extensive experiments on BitNet models ranging from 1B to 3B parameters, spanning classification, instruction-following, and mathematical reasoning tasks. TerMeZO matches or exceeds the performance of full-parameter MeZO while substantially reducing the fine-tuning memory footprint.

Houssem Sifaou, Prabodh Katti, Bipin Rajendran +1

Institute for Intelligent Networked Systems, Northeastern University London, UK

Zeroth-Order Optimization Zeroth-Order Large Language Model Quantization Model Weights

Sep 16, 2026cs.CL

A Zeroth-Order Paradigm for LLM Preference Alignment

Direct preference alignment methods are widely used to align large language models (LLMs) with human preferences because of their computational and memory efficiency. However, likelihood displacement motivates alternative ways to extract information from preference pairs with small likelihood margins. In this paper, we propose and analyze Comparison-based Preference Optimization (ComPO), a zeroth-order alignment method based on comparison oracles. ComPO extracts directional information from these pairs without directly optimizing a differentiable preference loss on them. We establish a convergence guarantee for its basic offline scheme under smoothness, gradient sparsity, and compatibility between the oracle and a latent objective. We further introduce online ComPO, which retains the offline comparison mechanism and uses unlabeled policy generations for reverse-KL control relative to a reference policy. Following the coverage perspective of preference fine-tuning, we establish a performance guarantee for a basic constrained scheme under local coverage and in-distribution pairwise reward accuracy. Experiments on Mistral, Llama, Gemma-2, Qwen3, and Gemma-3 models demonstrate improvements over existing direct alignment methods, including length-controlled win rates, with pair-level diagnostics providing evidence consistent with mitigating likelihood displacement.

Peter Chen, Xi Chen, Wotao Yin +1

Department of Electrical Engineering and Computer Sciences (EECS) University of California, Berkeley Berkeley, CA 94720, USA · Stern School of Business New York University New York, NY 10012, USA · Decision Intelligence Lab (Seattle) DAMO Academy, Alibaba Group U.S. Bellevue, WA 98004, USA +1

Preference Alignment Sequential Preference Optimization Zeroth-Order Differentiable Optimization

Sep 8, 2026cs.LG

Adaptively Incorporating Directional Hints into Zeroth-Order Optimization

We study zeroth-order optimization of non-convex functions with the aid of directional hints, which are cheap but potentially inaccurate approximations of the true gradient direction, given by linear subspaces at each iteration. To leverage these hints adaptively while maintaining robustness to their quality, we introduce Control-Variate Zeroth-Order Descent (CV-ZOD), a new framework that refines the classical zeroth-order gradient estimator with a control variate that can be set based on the directional hints. We first show that the oracle algorithm that optimally sets the reference vector and step size at each iteration achieves a convergence rate that interpolates between the first-order

O(1/T)

rate and the zeroth-order

O(d/T)

rate, depending on the quality of the hints along the trajectory. We then develop a practical variant of CV-ZOD that achieves the same oracle guarantee up to logarithmic factors, without any prior knowledge of the hint quality. We validate the method empirically on simulation-based scientific optimization tasks, demonstrating sustained progress on non-convex landscapes where zeroth-order descent is slower and existing guided methods stall as guidance deteriorates.

Alexander Ryabchenko, Jian Qian, Wenlong Mou

University of Toronto and Vector Institute · University of Hong Kong

Zeroth-Order Optimization Zeroth-Order Optimization Landscape

Aug 16, 2026cs.LG

SubZero+: Memory-Efficient Adaptive Zeroth-Order LLM Fine-Tuning in Random Subspaces

Zeroth-order (ZO) optimization with SGD in random subspaces enables memory-efficient fine-tuning of large language models without backpropagation. However, high gradient estimation noise fundamentally undermines adaptive optimizers like Adam. We propose SubZero+, which achieves practical adaptive ZO optimization through a carefully designed dual low-dimensionality strategy: (i) multi-query forward-difference gradient estimation in periodically refreshed random subspaces to mitigate noise amplification in moment buffers, and (ii) Adam updates with periodic restarts performed directly in low-dimensional space rather than full-parameter space. In experiments, this dual design retains memory overhead comparable to momentum-free ZO methods while achieving stronger optimization performance than the evaluated ZO baselines. Theoretically, in the exact-directional limit,

K

-query averaging preserves conditional unbiasedness, while the coefficient estimator's covariance and mean-squared error, as well as query-induced second-moment inflation, scale exactly as

1/K

. Extensive experiments across SuperGLUE with models from 1.3B to 32B parameters under both full fine-tuning and LoRA schemes demonstrate consistent improvements over competing ZO methods. SubZero+ significantly narrows the performance gap with first-order optimization while preserving ZO's inference-time memory efficiency.

Ziming Yu, Shuyao Xiao, Xingyu Zhao +6

Beijing Normal University · Singapore Management University · Xiaomi Inc. +2

Zeroth-Order Large Language Model Fine-Tuning Subspace Bounded-Memory

Aug 12, 2026cs.CV

Curvature-Aware Zeroth-Order Optimization for Memory-Efficient Test-Time Adaptation

Test-time adaptation (TTA) aims to enhance the cross-domain performance of pre-trained models by adapting to unlabeled test data. While most existing TTA methods rely on backpropagation (BP) for finetuning, BP-free methods such as zeroth-order (ZO) methods are more desired in practical on-device scenarios. ZO methods rely only on forward computation, which can largely reduce the complexity and memory overhead of on-device deployment. However, ZO methods suffer from much higher variance compared with first-order methods in estimating the gradient. To address this, we propose an improved ZO method to substantially boost the performance of ZO optimization based TTA. First, we provide an observation to reveal the persistent low-rank Hessian structure of the loss during the adaptation process. Based on this insight, we then propose a loss-landscape curvature-aware zeroth-order (CAZO) method, which leverages a sliding-average estimation of the diagonal Hessian to construct a covariance matrix for anisotropic perturbation sampling. CAZO operates by freezing pretrained weights and optimizing minimal adapter parameters via forward-only passes based gradient estimation, which can substantially reduce the memory overhead compared to BP-based methods. Extensive experiments demonstrate that CAZO significantly outperforms existing TTA methods, achieving state-of-the-art performance while maintaining an excellent balance between accuracy and memory efficiency. Code is available at https://github.com/Hollyming/CAZO.

Junming Zhang, Shuyu Yin, Peilin Liu +2

Shanghai Jiao Tong University, China

Test-Time Adaptation Zeroth-Order Optimization Zeroth-Order Curvature-Aware Spectral Framework Pretraining

Aug 11, 2026math.OC

A lower bound for stepsize-based acceleration of gradient descent

Recent work has shown that, for smooth convex optimization, plain gradient descent can be accelerated from its textbook convergence rate of

O(T^{-1})

(where

T

denotes the number of iterations) to

O\big(T^{-\log_2(1+\sqrt{2})}\big)

using carefully designed stepsize schedules alone, without resorting to momentum or other algorithmic modifications. Despite this progress, however, little was known about lower bounds for such methods beyond the classical

Ω(T^{-2})

benchmark for general first-order methods. In this work, we present a new lower bound of

Ω(T^{-1.9319})

for the last-iterate convergence rate of gradient descent with predetermined nonnegative stepsize schedules. This result provides rigorous evidence that stepsize schedules alone cannot accelerate plain GD to the optimal

O(T^{-2})

convergence rate. The proof was developed by GPT-5.6 Sol Pro under the authors' guidance.

Jianhao Ma, Yuxin Chen

Department of Industrial Engineering, Tsinghua University · Department of Statistics and Data Science, Wharton School, University of Pennsylvania

Step Accuracy Gradient Descent Convergence Lower Bounds Zeroth-Order

Jul 1, 2026cs.LG

ZO-Act: Efficient Zeroth-Order Fine-Tuning via One-Shot Activation-Informed Low-Rank Subspaces

Zeroth-order (ZO) optimization enables fine-tuning large language models when backpropagation is unavailable or memory-prohibitive, but existing methods often perturb full model weights or randomly constructed low-dimensional subspaces, yielding high-variance estimates and limited performance. We propose ZO-Act, an activation-informed ZO fine-tuning method that restricts perturbations to a fixed low-rank subspace derived from input activations. For each linear layer, ZO-Act computes a small activation basis once at initialization and optimizes only lightweight coefficient matrices using forward-only loss evaluations. This reduces the effective perturbation dimension, exposes explicit trainable variables compatible with momentum-based optimizers such as Adam, and naturally supports quantized LLM fine-tuning by keeping low-bit weights frozen. We analyze ZO-Act as zeroth-order optimization over a restricted coefficient space and show that perturbing the low-dimensional coefficients reduces both the variance-dependent convergence term and the finite-difference error of the ZO estimator, at the cost of a controlled subspace approximation bias that is mitigated by the low-rank structure of LLM activations and gradients. Experiments on Llama-3-8B, OPT-13B, and INT4 Llama-3-8B show consistent gains over strong ZO fine-tuning baselines across language understanding, question answering, and commonsense reasoning.

Xun Dong, Yibo Xu, Naigang Wang +3

University at Albany, SUNY · IBM T. J. Watson Research Center

Zeroth-Order Optimization Zeroth-Order Continual Fine-Tuning Large Language Model Fine-Tuning Large Language Model Quantization Subspace+1

Jun 26, 2026cs.GT

Non-Linear Strategic Classification Made Practical

Algorithmic developments in Strategic Classification have been mostly limited to linear classifiers in settings where the best response has a closed-form solution or can be easily approximated. While some work has explored the role of non-linear classifiers in strategic settings, progress in this direction is impeded by the computational intractability of the strategic behaviour. Addressing this, we present a novel method for approximating the best response by exploiting Lagrangian duality. By reformulating the strategic response as a constrained optimisation problem, we can construct a Lagrangian that is amenable to first order optimisation methods. This approach reproduces closed-form strategic behaviour in linear settings and can be straight-forwardly applied to non-linear settings. We show how the Implicit Function Theorem can be used in conjunction with our proposed response formulation during classifier learning to compute the total gradient of the loss. This connects the classifier parameters directly to the consequent strategic behaviour, yielding a novel training algorithm that can exploit this relationship. Experimental evaluation shows that the resulting models achieve improved strategic accuracy on common machine learning datasets.

Jack Geary, Boyan Gao, Henry Gouk

School of Informatics, University of Edinburgh, Edinburgh, United Kingdom · Department of Engineering Science, University of Oxford, Oxford, United Kingdom

Strategic Reasoning Classifier Primal-Dual Methods Zeroth-Order

Jun 26, 2026cs.NE

MMAO: A Metabolic Multi-Agent Optimizer with Endogenous Resource Allocation for Continuous and Discrete Optimization

Traditional meta-heuristics often rely on fixed population sizes, manually chosen search scales, and externally attached parameter-control modules. This paper presents the \textit{Metabolic Multi-Agent Optimizer} (MMAO), a cross-domain optimization framework in which adaptation is derived endogenously from a private-public metabolic resource loop. Each agent carries internal energy, a continuous role state, motion or structural memory, and local search history, while the population shares a communal resource pool. Fitness improvements are converted into normalized metabolic gains through a robust progress scale and a recent success statistic; the same closed loop then regulates sensing intensity, search amplitude, role drift, branching, pruning, respawning, and elite reinvestment. In the continuous setting, MMAO uses energy-regulated symmetric zero-order probing and role-interpolated motion. In the discrete setting, the same control law is instantiated through structural sensing, local route improvement, guided perturbation, and energy-weighted edge reuse. The paper combines an implementation-faithful formulation with a reproducible experimental study on a CEC2017 subset (10D/30D, 20 seeds) and five TSPLIB instances (100 discrete runs in total). The current evidence supports MMAO primarily as a parameter-light, self-calibrating optimization framework whose main validated originality lies in metabolically endogenous resource allocation across heterogeneous search behaviors, rather than as a universally superior optimizer.

Jinliang Xu, Liping Ma

Department of Disease Control and Prevention, The Seventh Medical Center of Chinese PLA General Hospital, Beijing, China

Metaheuristics Agentic Optimization Metabolic Combinatorial Optimization Zeroth-Order

Jun 12, 2026cs.LG

Zero-order Parameter-free Optimization for LMO-based Methods: Novel Approach for Efficient Fine-tuning

Fine-tuning large language models (LLMs) has become a central application of modern optimization, enabling pretrained models to adapt to diverse downstream tasks and domain-specific data. A major obstacle in large-scale fine-tuning is the memory overhead of backpropagation, which requires storing activations, gradients, and optimizer states. Zeroth-order (ZO) optimization offers a memory-efficient alternative, but its performance is highly sensitive to the stepsize and smoothing parameter, often requiring costly task-specific tuning. Parameter-free (PF) optimization addresses this issue by adapting algorithmic parameters without prior knowledge of problem-dependent constants. Moreover, large-scale fine-tuning can benefit from geometry-aware updates that account for the heterogeneous structure of parameter blocks, which can be modeled through methods that exploit linear minimization oracle (LMO). In this work, we study PF adaptation for LMO-based ZO optimization and introduce

\texttt{AdaNAGED}

, a method that unifies gradient-free training, adaptive tuning, and non-Euclidean update geometry. We establish convergence guarantees and validate the method on large-scale LLM fine-tuning task with

\texttt{OPT}-1.3\mathrm{B}

model.

Dmitriy Bystrov, Daniil Medyakov, Dmitry Bylinkin +1

1Moscow Independent Research Institute of Artificial Intelligence · 2Basic Research of Artificial Intelligence Laboratory (BRAIn Lab) · 3Innopolis University

Parameter-Efficient Fine-Tuning Methods Zeroth-Order Optimization Large Language Model Fine-Tuning Model Fine-Tuning Adaptive Optimizers Zeroth-Order+2

Jun 4, 2026cs.LG

Flatland: The Adventures of Gradient Descent with Large Step Sizes

The training of neural networks often entails objective functions that are not globally

L

-smooth. For these functions, it is both theoretically and practically difficult to reply to the question: what is the largest possible step size that ensures the convergence of gradient descent (GD)? We address this longstanding open question in deep learning by providing a unifying definition of "large" step sizes that requires only local Lipschitz (or even Hölder) continuity of the gradient. We design first-order adaptive methods that provably yield large step sizes and show that they operate at the edge of stability (EoS) right from the start of the training. In particular, the loss decreases nonmonotonically and the product between the step size and sharpness, i.e., the largest eigenvalue of the Hessian, stays above the EoS threshold of 2 throughout training. Using our method, we are also able to minimize the sharpness all the way down to its global minimum. Contrary to expectation, we find that encountering globally-flat regions too early in the training may both slow down convergence and jeopardize the generalization ability of the network. Exploiting a self-stabilization argument, we allow GD to enter slightly sharper valleys and turn unsuccessful training runs into very successful ones.

Leonardo Galli, Curtis Fox, Wiebke Bartolomaeus +2

LMU Munich · Munich Center for Machine Learning · University of British Columbia +1

Gradient Descent Step Accuracy Stabilization Zeroth-Order

Jun 3, 2026cs.LG

Dominant-Layer ZO: A Single Layer Dominates Zeroth-Order Fine-Tuning of LLMs

Zeroth-order (ZO) optimization enables memory-efficient fine-tuning of large language models (LLMs) using only forward passes, but it remains unclear how useful adaptation is distributed across layers. In this work, we reveal a surprising phenomenon: ZO fine-tuning is sharply dominated by a single decoding layer. Across multiple LLM families and downstream tasks, fine-tuning this dominant layer alone consistently matches or even exceeds full-model ZO fine-tuning. We further show that the dominant layer is task-agnostic but model-specific, and can be identified before training through a simple inference-only analysis of activation outliers. Specifically, the dominant layer consistently aligns with the first activation-outlier layer in the pre-trained model. To explain this phenomenon, we analyze how perturbation effects propagate under ZO optimization. We find that the dominant layer combines two key properties: high perturbation sensitivity and early placement in the residual stream, allowing perturbation-induced effects to propagate and accumulate through remaining subsequent decoding layers. As a result, this layer produces disproportionately strong and stable optimization signals under forward-only updates. Extensive experiments on LLaMA2-7B and Qwen3-8B across nine benchmarks show that dominant-layer ZO fine-tuning improves average performance over full-model MeZO and LoRA-based ZO fine-tuning while achieving up to 4.52

\times

training speedup.

Wanhao Yu, Ziyan Wang, Zheng Wang +7

University of North Carolina at Charlotte · University of Houston · State University of New York at Binghamton +2

Continual Fine-Tuning Zeroth-Order Layer-Wise

Jun 1, 2026cs.LG

GRZO: Group-Relative Zeroth-Order Optimization for Large Language Model Fine-Tuning

Zeroth-order (ZO) optimization is a memory-efficient alternative to backpropagation for fine-tuning large language models, but its deployment is limited by the high variance of gradient estimation. We propose GRZO, a Group-Relative Zeroth-Order optimizer that draws one pseudo-independent perturbation per mini-batch example and aggregates the per-example losses through group-relative normalization, raising the effective gradient-direction count from one to the batch size at no additional forward cost while preserving inference-level memory. We prove that GRZO is directionally unbiased with variance shrinking proportionally to the batch size, yielding a tighter nonconvex convergence bound than MeZO. Across RoBERTa-large, Llama3-8B, and OPT-13B over multiple tasks, GRZO improves average accuracy on Llama3-8B by

+3.0

over MeZO at

23\%

lower peak GPU memory; as a drop-in replacement for the MeZO core, it lifts sparse, low-rank, and quantized ZO variants by

+6.0

on average.

Liyan Tan, Yequan Zhao, Yifan Yang +3

University of California, Santa Barbara

Zeroth-Order Optimization Zeroth-Order Large Language Model Fine-Tuning

May 29, 2026cs.LG

Revisiting Zeroth-Order Hessian Approximation: A Single-Step Policy Optimization Lens

Accurate Zeroth-Order (ZO) Hessian estimation is a cornerstone of derivative-free methods, essential for tasks such as bilevel optimization, Bayesian inference, and uncertainty quantification. However, obtaining a complete suite of low-variance estimators for the Hessian and its inverse in high-dimensional settings remains a significant challenge. To address this, we propose a unified framework that reinterprets ZO Hessian approximation through the lens of single-step Policy Optimization (PO). This perspective establishes a theoretical equivalence between general ZO Hessian estimators and the Hessian of a smoothed PO objective, unifying distinct classical randomized estimators as specific instances of baseline selection. Building on this foundation, we introduce ZoVH, a comprehensive suite of variance-reduced estimators for the full Hessian matrix, its regularized inverse, and the bias-corrected inverse Hessian-gradient product. ZoVH leverages two key techniques: (1) a unique optimal baseline derived to provably minimize variance, and (2) a query reuse strategy that incorporates historical function queries to enhance sample efficiency without inflating costs. Our rigorous theoretical analysis confirms the unbiasedness of the Hessian estimator, validates the variance optimality of our baseline, provides error bounds for the entire ZoVH suite, and establishes convergence guarantees for the resulting curvature-aware ZO algorithm. Extensive empirical results validate our theoretical findings, demonstrating that ZoVH achieves superior estimation accuracy and convergence performance in real-world applications. Code is available at https://github.com/Qjbtiger/ZoVH

Junbin Qiu, Zhaowei Hong, Renzhe Xu +1

Hong Kong University of Science and Technology (Guangzhou) · Shanghai University of Finance and Economics

Hessian Zeroth-Order Variance Reduction Frictive Policy Optimization Curvature-Aware Spectral Framework

May 27, 2026cs.LG

Inference-Native Zeroth-Order Optimization for LLMs

Zeroth-order (ZO) methods train large language models using only forward passes, yet common ZO execution paths perform substantial work beyond what the algorithm itself requires. To remove this extra execution overhead, we present Infer-ZO, which separates the evaluations required by the algorithm from how they are executed, allowing them to reuse existing inference-engine optimizations. After removing inherited execution work, a complete Infer-ZO step on Qwen3-14B adds only 1.16% wall-clock time over matched inference, bringing ZO execution close to its fundamental inference workload. With Infer-ZO, ZO evaluations run at near-inference cost with frozen base weights and can share GPU batches with ordinary inference requests. In co-serving experiments, foreground and background throughput remain within 1-3% of the corresponding background-request baseline. Across 15 Qwen3, Llama, and OPT models, Infer-ZO achieves 2.10x-9.94x end-to-end step speedups over released LoZO. Code is available at https://github.com/playeriv65/zo-vllm.

Zelin Li, Caiwen Ding

University of Minnesota

Large Language Model Fine-Tuning Model Fine-Tuning LLM Inference Optimization Zeroth-Order Inference Workloads Inference-Time

May 19, 2026cs.LG

AR1-ZO: Topology-Aware Rank-1 Zeroth-Order Queries for High-Rank LoRA Fine-Tuning

Zeroth-order (ZO) optimization enables large-language-model fine-tuning without storing backpropagation activations, while LoRA supplies compact trainable adapters. Combining them creates a rank paradox: increasing LoRA rank improves adapter capacity, but standard two-point ZO either perturbs a rank-dependent number of coordinates or, under atomwise updates, can make the finite-difference signal unobservable. This paper shows that the bottleneck is a measurement-topology problem rather than a need for an external subspace. LoRA already decomposes into matched rank-

1

atoms, each a complete factor-coordinate block of dimension

d_\text{out}+d_\text{in}

. Querying one atom per step keeps the stored adapter rank

r

while removing

r

from the single-query perturbation dimension. The naive atomwise query is still miscalibrated: if it inherits canonical LoRA scaling

α/r

, the active finite-difference signal shrinks as

1/r

and the active finite-difference signal-to-noise ratio (FD-SNR) as

1/r^2

, producing directional collapse under a fixed residual evaluation-noise floor. AR1-ZO pairs alternating rank-

1

atom queries with topology-aware scaling

γ=αr

, restoring rank-invariant active signal without auxiliary bases, activation hooks, curvature estimates, or extra forward queries. Theory proves atom minimality, rank-independent active query dimension, directional collapse and restoration, and the remaining rank dependence as an amortized coverage cost. Experiments on OPT and Qwen3 models validate the signal mechanism and show that AR1-ZO makes high-rank LoRA effective among matched-budget ZO methods under the standard two-forward-pass query budget.

Ziye Chen, Hongbin Lin, Chenyu Zhang +3

Zeroth-Order Model Fine-Tuning Large Language Model Quantization Bottlenecks Topology

May 15, 2026cs.MA

Distributed Zeroth-Order Policy Gradient for Networked Multi-agent Reinforcement Learning from Human Feedback

We study a networked multi-agent reinforcement learning (NMARL) problem with human feedback in an infinite-horizon setting, where agents interact over an underlying network with localized state dependencies and aim to collaboratively maximize the average discounted return. Existing approaches with preference feedback are primarily developed for single-agent settings and rely on centralized training, which limits their scalability and applicability to large-scale networked multi-agent systems. To address this, we introduce a novel human feedback mechanism based on spatiotemporally truncated trajectories, defined as

H

-horizon trajectory pairs aggregated over each agent's

κ

-hop neighborhood. Building on this, we develop a distributed zeroth-order policy gradient algorithm, where each agent estimates its local policy gradient using human preference feedback generated from both the current joint policy and a perturbed joint policy drawn from zero-mean Gaussian distribution. Specifically, the algorithm is fully distributed, as the feedback received by each agent depends solely on the state-action information within its

κ

-hop neighborhood and does not require explicit reward signals or centralized control. We further rigorously establish that the proposed algorithm converges to an

ε

-stationary point with polynomial sample complexity. Finally, simulation results in a stochastic GridWorld environment and a predator-prey environment further demonstrate that the effectiveness and scalability of the proposed algorithm in achieving collaborative optimization based solely on human preference feedback.

Pengcheng Dai, He Wang, Dongming Wang +2

Singapore University of Technology and Design, Singapore 487372, Singapore · Southeast University, Nanjing 211189, China · University of California, Riverside, CA 92521, USA +2

Multi-Agent Reinforcement Learning Reinforcement Learning From Human Feedback Neural Policies Long-Horizon Trajectories Zeroth-Order

May 15, 2026cs.LG

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

Zeroth-order (ZO) optimization, learning from finite differences of function evaluations without backpropagation, has recently regained attention in deep learning due to its memory efficiency and applicability to gray- or black-box pipelines. Yet, ZO methods are often dismissed as fundamentally unscalable because of estimator variance and unfavorable query complexity. We argue that this conclusion might be misguided: ZO optimization is underexplored, not underpowered. We show that many perceived limitations stem from myopic development practices, most notably full-space, element-wise, estimator-centric designs. We articulate six positions spanning the algorithmic, systems, and evaluation stack. First, we revisit the feasibility boundaries of estimator-centric ZO methods through variance control, variance-query tradeoffs, and directional-derivative lenses. Then, we identify three underexplored opportunities: (i) subspace and spectral views of ZO that enable interpretable variance reduction with graceful query scaling, (ii) the forward-only nature of ZO as a systems advantage for communication-efficient, pipeline-friendly, and resource-constrained training, and (iii) the need to de-obfuscate ZO evaluations from task complexity. We strongly advocate rethinking ZO optimization around its unique strengths and acting accordingly, opening a viable path toward large-scale, system-aware, and resource-efficient learning with ZO optimization.

Sijia Liu, Yicheng Lang, Soumyadeep Pal +6

1OPTML Lab, Michigan State University, USA · 2Lawrence Livermore National Laboratory, USA

Zeroth-Order Optimization Zeroth-Order Deep Learning Variance Position

May 11, 2026cs.LG

Compander-Aligned Query Geometry for Quantized Zeroth-Order Optimization

Low-bit forward evaluation is an attractive route to memory-efficient zeroth-order (ZO) adaptation: the optimizer needs only scalar losses, and the model can be queried near deployment precision. The obstacle is that a quantized ZO query is not a continuous finite difference followed by harmless storage rounding. The query chooses endpoints, the low-precision engine rounds them, and the loss difference is measured along the rounded chord. For nonuniform companding quantizers, this makes the codebook insufficient to predict ZO behavior: a fixed weight-space radius can collapse in dense cells, over-span sparse cells, or assign a rounded chord to an unrounded update direction. We identify the missing object as query geometry and model scalar nonuniform quantization as

Q = φ^{-1} \circ U \circ φ

. CAQ-ZO (Compander-Aligned Queries for Zeroth-Order Optimization) forms one-grid-step Rademacher stencils

z \pm Δr

in

z = φ(x)

, maps endpoints back through

φ^{-1}

, and updates in

z

. Our theory proves the grid-span mismatch, decomposes endpoint-rounding estimator residuals, and gives stationarity bounds in which generic off-grid queries retain a

Δ^2/μ^2

residual channel while CAQ-ZO makes the query-time residual exactly zero. Synthetic experiments isolate this channel, and matched NF4 Qwen/Llama fine-tuning shows that CAQ-ZO improves the trained NF4 baseline under the same quantizer and evaluation budget.

Yao Shu, Zilin Zhu

HKUST-GZ

Zeroth-Order Zeroth-Order Optimization Backward Passes Geometric Constraints

May 11, 2026cs.LG

Why Zeroth-Order Adaptation May Forget Less: A Randomized Shaping Theory

Continual learning requires new-task adaptation without damaging previously acquired capabilities. Recent forward-pass and zeroth-order (ZO) results show that low-query adaptation may retain better than first-order (FO) descent, but the usual view of ZO as noisy FO estimation does not explain why. We give a local randomized gradient-shaping analysis: finite differences expose a raw shape that is mean-aligned with FO, while the norm-matched comparator fixes the expected squared adaptation norm. Under this controlled comparison, forgetting depends on how the adaptation shape exposes retention curvature. For norm-matched ZO, the expected shaped retention curvature obeys an exact identity that preserves the isotropic retention floor while contracting only the anisotropic component. Projecting this identity onto the incoming gradient yields the observable FO--ZO quadratic forgetting gap: ZO improves mean forgetting precisely when the FO direction has above-average retention curvature, by a query-dependent fraction of that curvature excess. A practical finite-query accounting separates the mean mechanism from one-batch sampling and smoothing perturbations. As an algorithmic transfer, RISE applies the calibrated ZO shape to exact FO gradients inside parameter blocks. Its target is a stability--plasticity tradeoff: randomized shaping may reduce the retention exposure paid by FO, exact gradients remove finite-smoothing bias from finite-difference ZO, and blockwise sampling supplies many local shaping directions after one gradient computation. The blockwise analysis separates mean-step damage from centered random exposure, showing how block-diagonal curvature, cross-block coupling, and local shaping diagnostics specify where this exact-gradient transfer is most likely to be visible.

Yao Shu, Jian Mu, Zhongxiang Dai

HKUST(GZ)

Zeroth-Order Zeroth-Order Optimization Catastrophic Forgetting Continual Learning Local Curvature Shaping+1

May 10, 2026cs.LG

Adversary-Robust Learning from Fully Asynchronous Directional Derivative Estimates

We propose FAR-SIGN (Fully Asynchronous Robust optimization via SIGNed directional projections) for adversary-resilient learning in parameter-server--worker systems. FAR-SIGN achieves robustness through sign-based updates along carefully designed directions and mitigates the resulting bias via a two-timescale mechanism. It admits both first-order and zeroth-order implementations and enables fully asynchronous execution without requiring a private reference dataset at the server. We establish almost-sure convergence of FAR-SIGN to the set of stationary points for smooth, nonconvex objectives. Moreover, we prove the near-optimal rate of

O(n^{-1/4+ε})

in the first-order setting and the standard

O(n^{-1/6+ε})

in the zeroth-order setting, where

n

is the iteration count and

ε>0

can be chosen arbitrarily small. Experiments on MNIST show that FAR-SIGN outperforms robust aggregation-based methods in both accuracy and wall-clock time.

Anik Kumar Paul, Nibedita Roy, Nagesh Talagani +3

Computer Science and Automation, Indian Institute of Science, Bengaluru · Edwardson School of Industrial Engineering, Purdue University · Department of Computer Science, IMT Atlantique

Learning-Augmented Algorithms Zeroth-Order Projection

May 9, 2026cs.LG

Accelerating Zeroth-Order Spectral Optimization with Partial Orthogonalization from Power Iteration

Zeroth-order (ZO) optimization has become increasingly popular and important in fine-tuning large language models (LLMs), especially on edge devices due to its ability to adjust the model to local data without the need for memory-intensive back-propagation. Recent works try to reduce ZO variance through low-dimensional subspace search, but subspace restriction alone leaves key optimization geometry under-exploited, motivating additional acceleration. In this work, we focus on the hidden layer training problem in which spectral optimizers like Muon outperform AdamW due to its ability to exploit weak spectral directions by orthogonalization. However, we have discovered that unlike in the first-order setting, full orthogonalization works poorly in the ZO setting since the gradient estimates are highly noisy and unreliable. To address this issue, we propose applying partial spectral orthogonalization to accelerate ZO optimization. To do so, we replace the iconic Newton-Schulz procedure in Muon with the faster, more concentrated power-iteration method so that it only amplifies dominant spectral directions. Furthermore, to improve the efficiency and generalization of the algorithm, we adopted a streaming variant of power-iteration that requires low variance in gradients, which was achieved through constraining our search inside a subspace obtained through the projection of momentum, echoing recent advances. Experiments on LLM fine-tuning show that our method can achieve from 1.5x to 4x the convergence speed of ZO-Muon, the current SOTA algorithm, across SuperGlue datasets in the OPT-13B model. Across different models, we also reach competitive final accuracies with less time in most cases compared with strong ZO baselines such as MeZO, LOZO and ZO-Muon. Code is available at https://github.com/MOFA-LAB/ZO-MOPI.git.

Jiahe Chen, Ziye Ma

Department of Computer Science City University of Hong Kong

Zeroth-Order Optimization Zeroth-Order Muon Orthogonality Newton

May 7, 2026cs.LG

PACZero: PAC-Private Fine-Tuning of Language Models via Sign Quantization

We introduce PACZero, a family of PAC-private zeroth-order mechanisms for fine-tuning large language models that delivers usable utility at

I(S^*; Y_{1:T})=0

. This privacy regime bounds the membership-inference attack (MIA) posterior success rate at the prior, an MIA-resistance level the DP framework matches only at

\varepsilon=0

and infinite noise. All DP-ZO comparisons below are matched at the MIA posterior level. The key insight is that PAC Privacy charges mutual information only when the release depends on which candidate subset is the secret. Sign-quantizing subset-aggregated zeroth-order gradients creates frequent unanimity, steps at which every candidate subset agrees on the update direction; at these steps the released sign costs zero conditional mutual information. We propose two variants that span the privacy-utility trade-off: PACZero-MI (budgeted MI via exact calibration on the binary release) and PACZero-ZPL (

I=0

via a uniform coin flip on disagreement steps). We evaluate on SST-2 and SQuAD with OPT-1.3B and OPT-6.7B in both LoRA and full-parameter tracks. On SST-2 OPT-1.3B full fine-tuning at

I=0

, PACZero-ZPL reaches

{88.99\pm0.91}

, within

2.1

pp of the non-private MeZO baseline (

91.1

FT). No prior method produces usable utility in the high-privacy regime

\varepsilon<1

, and PACZero-ZPL obtains competitive SST-2 accuracy and nontrivial SQuAD F1 across OPT-1.3B and OPT-6.7B at

I=0

.

Murat Bilgehan Ertan, Xiaochen Zhu, Phuong Ha Nguyen +2

CWI Amsterdam · ∗Affiliated with Vrije Universiteit Amsterdam. · MIT +1

Zeroth-Order Membership Inference Attacks

May 5, 2026cs.LG

Learning Dynamics of Zeroth-Order Optimization: A Kernel Perspective

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.

Zhe Li, Bicheng Ying, Zidong Liu +1

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 Zeroth-Order Neural Tangent Kernel Learning Dynamics

Apr 28, 2026math.OC

From Cursed to Competitive: Closing the ZO-FO Gap via Input-to-State Stability

While it is generally understood that zeroth-order (ZO) algorithms have an extra dependency on their number of iterations for any choice of parameters, compared to their first-order (FO) counterparts, in this work, we show that under several conditions, in expectation, ZO methods do not suffer from extra dimension dependencies in their convergence rates with respect to their FO counterparts. We look at optimisation algorithms from the dynamical systems perspective and analyse the conditions under which one can formulate the average of a ZO algorithm as the average of its FO counterpart with bounded perturbations with values dependent on design parameters. Then, using input-to-state stability properties, we show ZO methods follow the same decay rate as their FO counterparts and converge to a neighbourhood of the fixed point of FO methods, where its radius depends on the bound of the norm of the perturbations, which can be made arbitrarily small. The theoretical findings are illustrated via numerical examples.

Amir Ali Farzin, Philipp Braun, Iman Shames

School of Engineering · Australian National University · Canberra, ACT 2601 +3

Zeroth-Order Lyapunov Function Convergence Dynamical Systems Scale Gap Competition

Apr 22, 2026cs.CV

Beyond ZOH: Advanced Discretization Strategies for Vision Mamba

Vision Mamba, as a state space model (SSM), employs a zero-order hold (ZOH) discretization, which assumes that input signals remain constant between sampling instants. This assumption degrades temporal fidelity in dynamic visual environments and constrains the attainable accuracy of modern SSM-based vision models. In this paper, we present a systematic and controlled comparison of six discretization schemes instantiated within the Vision Mamba framework: ZOH, first-order hold (FOH), bilinear/Tustin transform (BIL), polynomial interpolation (POL), higher-order hold (HOH), and the fourth-order Runge-Kutta method (RK4). We evaluate each method on standard visual benchmarks to quantify its influence in image classification, semantic segmentation, and object detection. Our results demonstrate that POL and HOH yield the largest gains in accuracy at the cost of higher training-time computation. In contrast, the BIL provides consistent improvements over ZOH with modest additional overhead, offering the most favorable trade-off between precision and efficiency. These findings elucidate the pivotal role of discretization in SSM-based vision architectures and furnish empirically grounded justification for adopting BIL as the default discretization baseline for state-of-the-art SSM models.

Fady Ibrahim, Guangjun Liu, Guanghui Wang

Toronto Metropolitan University, 350 Victoria St, Toronto, ON M5B 2K3

Vision State Space Models Vision Foundation Models Mamba Discretization Time Discretization Zeroth-Order

Apr 20, 2026cs.LG

Universally Empowering Zeroth-Order Optimization via Adaptive Layer-wise Sampling

Zeroth-Order optimization presents a promising memory-efficient paradigm for fine-tuning Large Language Models by relying solely on forward passes. However, its practical adoption is severely constrained by slow wall-clock convergence and high estimation variance. In this work, we dissect the runtime characteristics of ZO algorithms and identify a critical system bottleneck where the generation of perturbations and parameter updates accounts for over 40% of the training latency. We argue that the standard uniform exploration strategy is fundamentally flawed as it fails to account for the heterogeneous sensitivity of layers in deep networks, resulting in computationally wasteful blind searches. To address this structural mismatch, we propose AdaLeZO, an Adaptive Layer-wise ZO optimization framework. By formulating the layer selection process as a non-stationary Multi-Armed Bandit problem, AdaLeZO dynamically allocates the limited perturbation budget to the most sensitive parameters. We further introduce an Inverse Probability Weighting mechanism based on sampling with replacement, which guarantees unbiased gradient estimation while effectively acting as a temporal denoiser to reduce variance. Extensive experiments on LLaMA and OPT models ranging from 6.7B to 30B parameters demonstrate that AdaLeZO achieves 1.7x to 3.0x wall-clock acceleration compared to state-of-the-art methods. Crucially, AdaLeZO functions as a universal plug-and-play module that seamlessly enhances the efficiency of existing ZO optimizers without incurring additional memory overhead.

Fei Wang, Li Shen, Liang Ding +3

South China University of Technology · Shenzhen Campus of Sun Yat-sen University · University of Sydney +2

Zeroth-Order Optimization Zeroth-Order

Apr 16, 2026cs.LG

Zeroth-Order Optimization at the Edge of Stability

Zeroth-order (ZO) methods are widely used when gradients are unavailable or prohibitively expensive, including black-box learning and memory-efficient fine-tuning of large models, yet their optimization dynamics in deep learning remain underexplored. In this work, we provide an explicit step size condition that exactly captures the (mean-square) linear stability of a family of ZO methods based on the standard two-point estimator. Our characterization reveals a sharp contrast with first-order (FO) methods: whereas FO stability is governed solely by the largest Hessian eigenvalue, mean-square stability of ZO methods depends on the entire Hessian spectrum. Since computing the full Hessian spectrum is infeasible in practical neural network training, we further derive tractable stability bounds that depend only on the largest eigenvalue and the Hessian trace. Empirically, we find that full-batch ZO methods operate at the edge of stability: ZO-GD, ZO-GDM, and ZO-Adam consistently stabilize near the predicted stability boundary across a range of deep learning training problems. Our results highlight an implicit regularization effect specific to ZO methods, where large step sizes primarily regularize the Hessian trace, whereas in FO methods they regularize the top eigenvalue.

Minhak Song, Liang Zhang, Bingcong Li +3

KAIST · KRAFTON · ETH Zurich +2

Zeroth-Order Optimization Zeroth-Order Hessian Regularization Deep Learning Edge

Mar 25, 2026cs.LG

Stochastic Dimension Zeroth-Order Estimator: Stable and Memory-Efficient Training of PINNs

Physics-Informed Neural Networks (PINNs) for high-dimensional and high-order partial differential equations (PDEs) are primarily constrained by the

\mathcal{O}(d^k)

spatial derivative complexity and the

\mathcal{O}(P)

memory overhead of backpropagation (BP). While randomized spatial estimators successfully reduce the spatial complexity to

\mathcal{O}(1)

, their reliance on first-order optimization still leads to prohibitive memory consumption at scale. Zeroth-order (ZO) optimization offers a BP-free alternative; however, naively combining randomized spatial operators with ZO perturbations triggers a variance explosion of

\mathcal{O}(1/\varepsilon^2)

, leading to numerical divergence. To address these challenges, we propose the \textbf{S}tochastic \textbf{D}imension-free \textbf{Z}eroth-order \textbf{E}stimator (\textbf{SDZE}), a unified framework that achieves dimension-independent complexity in both space and memory. Specifically, SDZE leverages \emph{Common Random Numbers Synchronization (CRNS)} to algebraically cancel the

\mathcal{O}(1/\varepsilon^2)

variance by locking spatial random seeds across perturbations. Furthermore, an \emph{implicit matrix-free subspace projection} is introduced to reduce parameter exploration variance from

\mathcal{O}(P)

to

\mathcal{O}(r)

while maintaining an

\mathcal{O}(1)

optimizer memory footprint. Empirical results demonstrate that SDZE enables the training of 10-million-dimensional PINNs on a single NVIDIA A100 GPU, delivering significant improvements in speed and memory efficiency over state-of-the-art baselines.

Zhangyong Liang, Huanhuan Gao

National Center for Applied Mathematics, Tianjin University, Tianjin 300072, China. · School of Mechanical and Aerospace Engineering, Jilin University, Changchun 130025, China

Zeroth-Order Partial Differential Equations Implicit Differentiation

May 4, 2025math.OC

Minimisation of Quasar-Convex Functions Using Random Zeroth-Order Oracles

This paper explores the performance of a random Gaussian smoothing zeroth-order (ZO) scheme for minimising quasar-convex (QC) and strongly quasar-convex (SQC) functions in both unconstrained and constrained settings. For the unconstrained problem, we establish the ZO algorithm's convergence to a global minimum along with its complexity when applied to both QC and SQC functions. For the constrained problem, we introduce the new notion of proximal-quasar-convexity and prove analogous results to the unconstrained case. Specifically, we derive complexity bounds and prove convergence of the algorithm to a neighbourhood of a global minimum whose size can be controlled under a variance reduction scheme. Beyond the theoretical guarantees, we demonstrate the practical implications of our results on several machine learning problems where quasar-convexity naturally arises, including linear dynamical system identification and generalised linear models.

Amir Ali Farzin, Yuen-Man Pun, Philipp Braun +1

School of Engineering Australian National University · Department of Electrical and Electronic Engineering University of Melbourne · Department of Electrical and Electronic Engineering22 University of Melbourne

Nonconvex Zeroth-Order First Order Oracle Complexity Flat Minima Random