Zeroth-Order Optimization

Follow this topic Ask about this topic

Zeroth-order optimization studies how to improve an objective using only its evaluations, making it useful when gradients are unavailable, expensive, or incompatible with black-box systems. Common approaches estimate directions with finite differences or random perturbations, then reduce cost and noise through variance reduction, adaptive sampling, low-dimensional subspaces, or structured updates. The methods are used in settings such as language-model fine-tuning, robotics, test-time adaptation, and optimization under privacy or communication limits, alongside theoretical work on convergence and query complexity. A central tension is that avoiding backpropagation can save memory and enable broader access, but noisy estimates and many required evaluations can make optimization slower or less reliable than first-order methods.

Latest papers

86 papers15 papers in the last four weeks, up 200% on the four weeks before. 0.1% of all new papers.

Apr 20, 2026

Efficient Federated RLHF via Zeroth-Order Policy Optimization

This paper considers reinforcement learning from human feedback in a federated learning setting with resource-constrained agents, such as edge devices. We propose an efficient federated RLHF algorithm, named Partitioned, Sign-based Stochastic Zeroth-order Policy Optimization (Par-S

^2

ZPO). The algorithm is built on zeroth-order optimization with binary perturbation, resulting in low communication, computation, and memory complexity by design. Our theoretical analysis establishes an upper bound on the convergence rate of Par-S

^2

ZPO, revealing that it is as efficient as its centralized counterpart in terms of sample complexity but converges faster in terms of policy update iterations. Our experimental results show that it outperforms a FedAvg-based RLHF on four MuJoCo RL tasks.

Deyi Wang, Qining Zhang, Lei Ying

University of Michigan, Ann Arbor

Federated RL Communication-Efficient Distributed Training Zeroth-Order Optimization Policy Learning RL from Human Feedback

Apr 16, 2026

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

Edge of Stability Zeroth-Order Optimization Neural Network Training Dynamics Implicit Regularization Neural Network Stability

Apr 14, 2026

Evolution of Optimization Methods: Algorithms, Scenarios, and Evaluations

Balancing convergence speed, generalization capability, and computational efficiency remains a core challenge in deep learning optimization. First-order gradient descent methods, epitomized by stochastic gradient descent (SGD) and Adam, serve as the cornerstone of modern training pipelines. However, large-scale model training, stringent differential privacy requirements, and distributed learning paradigms expose critical limitations in these conventional approaches regarding privacy protection and memory efficiency. To mitigate these bottlenecks, researchers explore second-order optimization techniques to surpass first-order performance ceilings, while zeroth-order methods reemerge to alleviate memory constraints inherent to large-scale training. Despite this proliferation of methodologies, the field lacks a cohesive framework that unifies underlying principles and delineates application scenarios for these disparate approaches. In this work, we retrospectively analyze the evolutionary trajectory of deep learning optimization algorithms and present a comprehensive empirical evaluation of mainstream optimizers across diverse model architectures and training scenarios. We distill key emerging trends and fundamental design trade-offs, pinpointing promising directions for future research. By synthesizing theoretical insights with extensive empirical evidence, we provide actionable guidance for designing next-generation highly efficient, robust, and trustworthy optimization methods. The code is available at https://github.com/APRIL-AIGC/Awesome-Optimizer.

Tong Zhang, Jiangning Zhang, Zhucun Xue +9

Zhejiang University, APRIL Lab · Fudan University · Shanghai Jiaotong University +1

Deep Learning Optimization Adaptive Gradient Methods Stochastic Gradient Descent Second-Order Optimization Zeroth-Order Optimization

Apr 6, 2026

Optimizing Service Operations via LLM-Powered Multi-Agent Simulation

Service system performance depends on how participants respond to design choices, but modeling these responses is hard due to the complexity of human behavior. We introduce an LLM-powered multi-agent simulation (LLM-MAS) framework for optimizing service operations. We pose the problem as stochastic optimization with decision-dependent uncertainty: design choices are embedded in prompts and shape the distribution of outcomes from interacting LLM-powered agents. By embedding key numerical information in prompts and extracting it from LLM-generated text, we model this uncertainty as a controlled Markov chain. We develop an on-trajectory learning algorithm that, on a single simulation run, simultaneously constructs zeroth-order gradient estimates and updates design parameters to optimize steady-state performance. We also incorporate variance reduction techniques. In a sustainable supply chain application, our method outperforms benchmarks, including blackbox optimization and using LLMs as numerical solvers or as role-playing system designers. A case study on optimal contest design with real behavioral data shows that LLM-MAS is both as a cost-effective evaluator of known designs and an exploratory tool that can uncover strong designs overlooked by traditional approaches.

Yanyuan Wang, Xiaowei Zhang

Department of Industrial Engineering and Decision Analytics, The Hong Kong University of Science and Technology, Clear Water Bay, Hong Kong SAR

Stochastic Optimization Decision-Making under Uncertainty Multi-Agent LLM Systems Large Language Model-Based Social Simulation Zeroth-Order Optimization

Apr 4, 2026

One-Shot Localisation of the Global Minimum of a Noisy One-Dimensional Function: An Iterative Neural Minimizer Compared with Set Transformers and Classical Estimators

We study a passive form of global optimisation: from twenty noisy samples of an unknown one-dimensional function, predict where its global minimum lies, with no further queries. We introduce the Neural Function Minimizer (NFM), an iterative model that walks a position across the domain and, at every step, reads the samples near that position and attends to all twenty of them, and we compare it with two Set Transformers of the same size trained on the same data, one that answers with a single point and one that answers with a mixture of candidate locations, and with classical zero-query estimators, over three training seeds per learned model. On held-out cases from the training families the three learned models are tied on location error, and each is more accurate on average than every classical estimator; against the Gaussian-process posterior argmin the NFM's error is lower by 1.3 points of the domain. The NFM has lower regret than the single-point Set Transformer, and its per-case uncertainty has a better likelihood than that model's and orders the cases by error better than the mixture model's. The Gaussian process and the mixture model have lower regret, and on functions outside the training families the Gaussian process is the most accurate estimator. Where two valleys are equally deep, the form of an estimator's answer, not its architecture, decides whether it commits to a valley or answers between them: every estimator that returns one point fitted to distance, learned or spline-based, hedges in a fifth to nearly a third of exact ties, while estimators that name a mode commit, and one Gaussian-process posterior does both, depending on whether it is summarised by its median or its mode. We will release the benchmark and a self-checking harness; its cases are identical on different machines and its results agree to rounding.

Qusay Muzaffar, David Levin, Michael Werman

Department of Computer Science, The Hebrew University of Jerusalem, Israel · Department of Applied Mathematics, Tel Aviv University, Israel

Black-Box Optimization Zeroth-Order Optimization Learning to Optimize Global Optimization

Mar 31, 2026

Finite-time analysis of Multi-timescale Stochastic Optimization Algorithms

We present a finite-time analysis of two smoothed functional stochastic approximation algorithms for simulation-based optimization. The first is a two time-scale gradient-based method, while the second is a three time-scale Newton-based algorithm that estimates both the gradient and the Hessian of the objective function

J

. Both algorithms involve zeroth order estimates for the gradient/Hessian. Although the asymptotic convergence of these algorithms has been established in prior work, finite-time guarantees of two-timescale stochastic optimization algorithms in zeroth order settings have not been provided previously. For our Newton algorithm, we derive mean-squared error bounds for the Hessian estimator and establish a finite-time bound on

\min\limits_{0 \le m \le T} \mathbb{E}\| \nabla J(θ(m)) \|^2

, showing convergence to first-order stationary points. The analysis explicitly characterizes the interaction between multiple time-scales and the propagation of estimation errors. We further identify step-size choices that balance dominant error terms and achieve near-optimal convergence rates. We also provide corresponding finite-time guarantees for the gradient algorithm under the same framework. The theoretical results are further validated through experiments on the Continuous Mountain Car environment.

Kaustubh Kartikey, Shalabh Bhatnagar

Stochastic Optimization Stochastic Optimization Convergence Two-Timescale Stochastic Approximation Second-Order Optimization Zeroth-Order Optimization

Mar 25, 2026

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 Stochastic Dimension-free Zeroth-order Estimator (SDZE), a unified framework that achieves dimension-independent complexity in both space and memory. Specifically, SDZE leverages Common Random Numbers Synchronization (CRNS) to algebraically cancel the

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

variance by locking spatial random seeds across perturbations. Furthermore, an 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 Optimization Neural Network Optimization Partial Differential Equations Physics-Informed ML Variance Reduction

Mar 23, 2026

CurvZO: Adaptive Curvature-Guided Sparse Zeroth-Order Optimization for Efficient LLM Fine-Tuning

Fine-tuning large language models (LLMs) with backpropagation achieves high performance but incurs substantial memory overhead, limiting scalability on resource-constrained hardware. Zeroth-order (ZO) optimization provides a memory-efficient alternative by relying solely on forward passes, yet it typically suffers from slow or unstable convergence due to high-variance gradient estimates. Sparse ZO updates partially address this issue by perturbing only a subset of parameters, but their effectiveness hinges on selecting informative parameters, which is challenging in ZO optimization because each query yields only scalar feedback. We propose Adaptive Curvature-Guided Sparse Zeroth-Order Optimization (CurvZO), which tracks curvature signals online from scalar ZO feedback and leverages these signals to construct a parameter-wise sampling distribution for selecting coordinates at each update, reducing the variance of the sparse ZO gradient estimator. Moreover, CurvZO dynamically adapts the perturbation budget to the evolving curvature signal distribution, yielding sparse ZO updates that remain both focused and sufficiently exploratory. Extensive experiments on OPT and Llama across diverse NLP tasks show that CurvZO consistently improves fine-tuning performance and reduces training time over ZO baselines. It improves accuracy by up to 4.4 points and achieves up to a

2\times

speedup, while preserving memory efficiency.

Shuo Wang, Ziyu Chen, Ming Tang

Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen, China. · Department of Mathematics, Southern University of Science and Technology, Shenzhen, China.

Zeroth-Order Optimization Memory-Efficient Fine-Tuning LLM Fine-Tuning Sparse Fine-Tuning

Mar 22, 2026

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

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

Chen Zhang, Yuxin Cheng, Chenchen Ding +5

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

Zeroth-Order Optimization Neural Network Training Dynamics Neural Tangent Kernel

Mar 16, 2026

HO-SFL: Hybrid-Order Split Federated Learning with Backprop-Free Clients and Dimension-Free Aggregation

Fine-tuning large models on edge devices is severely hindered by the memory-intensive backpropagation (BP) in standard frameworks like federated learning and split learning. While substituting BP with zeroth-order optimization can significantly reduce memory footprints, it typically suffers from prohibitively degraded convergence speed. To resolve this dilemma, we propose Hybrid-Order Split Federated Learning (HO-SFL). By reformulating the split learning process within a Lagrangian framework, HO-SFL decouples the optimization landscape: The server performs precise first-order updates (i.e., BP), whereas clients conduct memory-efficient zeroth-order optimization. This hybrid design not only eliminates the need for client-side BP but also enables dimension-free model aggregation, drastically lowering communication costs. Crucially, we provide a theoretical convergence analysis, demonstrating that HO-SFL mitigates the dimension-dependent convergence slowdown of zeroth-order optimization, achieving a convergence rate comparable to first-order methods. Extensive experiments on tasks across vision and language modalities validate that HO-SFL achieves convergence speeds comparable to first-order baselines while significantly reducing communication costs and client memory footprints.

Qiyuan Chen, Xian Wu, Yi Wang +1

Department of Electrical and Computer Engineering, The University of Hong Kong, Hong Kong SAR, China.

Communication-Efficient Distributed Training Zeroth-Order Optimization Split Federated Learning Efficient Language Model Training Memory-Efficient Training Federated Learning

Mar 15, 2026

ZOTTA: Test-Time Adaptation with Gradient-Free Zeroth-Order Optimization

Test-time adaptation (TTA) aims to improve model robustness under distribution shifts by adapting to unlabeled test data, but most existing methods rely on backpropagation (BP), which is computationally costly and incompatible with non-differentiable models such as quantized models, limiting practical deployment on numerous edge devices. Recent BP-free approaches alleviate overhead but remain either architecture-specific or limited in optimization capacity to handle high-dimensional models. We propose ZOTTA, a fully BP-free TTA framework that performs efficient adaptation using only forward passes via Zeroth-Order Optimization (ZOO). While ZOO is theoretically appealing, naive application leads to slow convergence under high-dimensional parameter spaces and unstable optimization due to the lack of labels. ZOTTA overcomes these challenges through 1) Distribution-Robust Layer Selection, which automatically identifies and freezes layers that already extract distribution-invariant features, updating only domain-sensitive layers to reduce the optimization dimensionality and accelerate convergence; 2) Spatial Feature Aggregation Alignment, which stabilizes ZOO by aligning globally aggregated spatial features between source and target to reduce gradient variance. Together, these components enable architecture-agnostic and stable BP-free adaptation. Extensive experiments on ImageNet-C/R/Sketch/A show that ZOTTA outperforms or matches BP-based methods, e.g., it reduces memory usage by 84% and improves accuracy by 3.9% over SAR on ImageNet-C. Code:https://github.com/Zhang-Ronghao/zotta.

Ronghao Zhang, Shuaicheng Niu, Qi Deng +3

South China University of Technology, Guangzhou, 510000, China. · Nanyang Technological University, 639798, Singapore. · Xi’an Jiaotong University, Xi’an, 710049, China. +1

Test-Time Adaptation Zeroth-Order Optimization Image Classification

Mar 13, 2026

ZO-SAM: Zero-Order Sharpness-Aware Minimization for Efficient Sparse Training

Deep learning models, despite their impressive achievements, suffer from high computational costs and memory requirements, limiting their usability in resource-constrained environments. Sparse neural networks significantly alleviate these constraints by dramatically reducing parameter count and computational overhead. However, existing sparse training methods often experience chaotic and noisy gradient signals, severely hindering convergence and generalization performance, particularly at high sparsity levels. To tackle this critical challenge, we propose Zero-Order Sharpness-Aware Minimization (ZO-SAM), a novel optimization framework that strategically integrates zero-order optimization within the SAM approach. Unlike traditional SAM, ZO-SAM requires only a single backpropagation step during perturbation, selectively utilizing zero-order gradient estimations. This innovative approach reduces the backpropagation computational cost by half compared to conventional SAM, significantly lowering gradient variance and effectively eliminating associated computational overhead. By harnessing SAM's capacity for identifying flat minima, ZO-SAM stabilizes the training process and accelerates convergence. These efficiency gains are particularly important in sparse training scenarios, where computational cost is the primary bottleneck that limits the practicality of SAM. Moreover, models trained with ZO-SAM exhibit improved robustness under distribution shift, further broadening its practicality in real-world deployments.

Jie Ji, Gen Li, Kaiyuan Deng +2

Clemson University · University of Arizona

Sharpness-Aware Minimization Sparse Neural Networks Zeroth-Order Optimization

Mar 5, 2026

FOZO: Forward-Only Zeroth-Order Prompt Optimization for Test-Time Adaptation

Test-Time Adaptation (TTA) is essential for enabling deep learning models to handle real-world data distribution shifts. However, current approaches face significant limitations: backpropagation-based methods are not suitable for low-end deployment devices, due to their high computation and memory requirements, as well as their tendency to modify model weights during adaptation; while traditional backpropagation-free techniques exhibit constrained adaptation capabilities. In this work, we propose Forward-Only Zeroth-Order Optimization (FOZO), a novel and practical backpropagation-free paradigm for TTA. FOZO leverages a memory-efficient zeroth-order prompt optimization, which is led by objectives optimizing both intermediate feature statistics and prediction entropy. To ensure efficient and stable adaptation over the out-of-distribution data stream, we introduce a dynamically decaying perturbation scale during zeroth-order gradient estimation and theoretically prove its convergence under the TTA data stream assumption. Extensive continual adaptation experiments on ImageNet-C, ImageNet-R, and ImageNet-Sketch demonstrate FOZO's superior performance, achieving 59.52% Top-1 accuracy on ImageNet-C (5K, level 5) and outperforming main gradient-based methods and SOTA forward-only FOA (58.13%). Furthermore, FOZO exhibits strong generalization on quantized (INT8) models. These findings demonstrate that FOZO is a highly competitive solution for TTA deployment in resource-limited scenarios.

Xingyu Wang, Tao Wang

College of Computer Science, Sichuan University

Test-Time Adaptation Continual Test-Time Adaptation Test-Time Prompt Tuning Zeroth-Order Optimization

Feb 26, 2026

Zeroth-Order Stackelberg Control in Combinatorial Congestion Games

We study Stackelberg (leader--follower) tuning of network parameters (tolls, capacities, incentives) in combinatorial congestion games, where selfish users choose discrete routes (or other combinatorial strategies) and settle at a congestion equilibrium. The leader minimizes a system-level objective (e.g., total travel time) evaluated at equilibrium, but this objective is typically nonsmooth because the set of used strategies can change abruptly. We propose ZO-Stackelberg, which couples a projection-free Frank--Wolfe equilibrium solver with a zeroth-order outer update, avoiding differentiation through equilibria. We prove convergence to generalized Goldstein stationary points of the true equilibrium objective, with explicit dependence on the equilibrium approximation error, and analyze subsampled oracles: if an exact minimizer is sampled with probability

κ_m

, then the Frank--Wolfe error decays as

\mathcal{O}(1/(κ_m T))

. We also propose stratified sampling as a practical way to avoid a vanishing

κ_m

when the strategies that matter most for the Wardrop equilibrium concentrate in a few dominant combinatorial classes (e.g., short paths). Experiments on real-world networks demonstrate that our method achieves orders-of-magnitude speedups over a differentiation-based baseline while converging to follower equilibria.

Saeed Masiha, Sepehr Elahi, Negar Kiyavash +1

EPFL School of Management of Technology · EPFL Department of Computer and Communications Sciences

Frank-Wolfe Algorithms Stackelberg Games Congestion Games Game Theory Zeroth-Order Optimization Constrained Optimization

Feb 23, 2026

AdaEvolve: Adaptive LLM Driven Zeroth-Order Optimization

The paradigm of automated program generation is shifting from one-shot generation to inference-time search, where Large Language Models (LLMs) function as semantic mutation operators within evolutionary loops. While effective, these systems are currently governed by static schedules that fail to account for the non-stationary dynamics of the search process. This rigidity results in substantial computational waste, as resources are indiscriminately allocated to stagnating populations while promising frontiers remain under-exploited. We introduce AdaEvolve, a framework that reformulates LLM-driven evolution as a hierarchical adaptive optimization problem. AdaEvolve uses an "accumulated improvement signal" to unify decisions across three levels: Local Adaptation, which dynamically modulates the exploration intensity within a population of solution candidates; Global Adaptation, which routes the global resource budget via bandit-based scheduling across different solution candidate populations; and Meta-Guidance which generates novel solution tactics based on the previously generated solutions and their corresponding improvements when the progress stalls. We demonstrate that AdaEvolve consistently outperforms the open-sourced baselines across 185 different open-ended optimization problems including combinatorial, systems optimization and algorithm design problems.

Mert Cemri, Shubham Agrawal, Akshat Gupta +9

University of California, Berkeley · Bespoke Labs

Large Language Model-Guided Optimization LLMs for Evolutionary Optimization Evolutionary Optimization LLM-Based Program Synthesis Zeroth-Order Optimization

Feb 23, 2026

Generalized Random Direction Newton Algorithms for Stochastic Optimization

We present a family of generalized Hessian estimators of the objective using random direction stochastic approximation (RDSA) by utilizing only noisy function measurements. The form of each estimator and the order of the bias depend on the number of function measurements. In particular, we demonstrate that estimators with more function measurements exhibit lower-order estimation bias. We show the asymptotic unbiasedness of the estimators. We also perform asymptotic and non-asymptotic convergence analyses for stochastic Newton methods that incorporate our generalized Hessian estimators. Finally, we perform numerical experiments to validate our theoretical findings.

Soumen Pachal, Prashanth L. A., Shalabh Bhatnagar +1

Indian Institute of Technology Madras · Indian Institute of Science, Bangalore · TCS Research, Chennai, India

Stochastic Optimization Stochastic Optimization Convergence Zeroth-Order Optimization Stochastic Approximation

Feb 20, 2026

SeedFlood: A Step Toward Scalable Decentralized Fine-Tuning of LLMs

This work presents SeedFlood, a new approach to decentralized LLM fine-tuning designed to scale across large models, large collaborations, and complex network topologies while achieving global consensus with negligible communication overhead. Traditional methods suffer from high communication costs that grow with model size, while information decay over network hops renders global consensus inefficient. SeedFlood takes a significant departure from these practices by exploiting the seed-reconstructible structure of zeroth-order gradients and effectively making the messages to transmit near-zero in size, allowing them to be flooded to every client in the network, and thereby enhancing scalability of decentralized training. Consequently, SeedFlood enables training in regimes previously considered impractical, such as billion-parameter scale models or distributed across hundred of clients. Our experiments on decentralized LLM fine-tuning demonstrate that SeedFlood consistently outperforms the standard zeroth-order baselines in both communication efficiency and generalization performance, and even achieves results comparable to first-order gossip-based methods in large-scale settings, while requiring orders-of-magnitude less communication cost. We also provide theoretical analysis to formalize that SeedFlood avoids topology-dependent consensus terms in the convergence bound while retaining the acceleration enabled by increased client participation.

Jihun Kim, Dongyeop Lee, Namhoon Lee

POSTECH, pohang, Republic of Korea.

Communication-Efficient Distributed Training Zeroth-Order Optimization LLM Fine-Tuning Decentralized Learning

Feb 19, 2026

Powering Up Zeroth-Order Training via Subspace Gradient Orthogonalization

Zeroth-order (ZO) optimization provides a gradient-free alternative to first-order (FO) methods by estimating gradients via finite differences of function evaluations, and has recently emerged as a memory-efficient paradigm for fine-tuning large-scale models by avoiding backpropagation. However, ZO optimization has a fundamental tension between accuracy and query efficiency. In this work, we show that ZO optimization can be substantially improved by unifying two complementary principles: (i) a projection-based subspace view that reduces gradient estimation variance by exploiting the intrinsic low-rank structure of model updates, and (ii) Muon-style spectral optimization that applies gradient orthogonalization to extract informative spectral structure from noisy ZO gradients. These findings form a unified framework of subspace gradient orthogonalization, which we instantiate in a new method, ZO-Muon, admitting a natural interpretation as a low-rank Muon optimizer in the ZO setting. Extensive experiments on large language models (LLMs) and vision transformers (ViTs) demonstrate that ZO-Muon significantly accelerates convergence and achieves a win-win improvement in accuracy and query/runtime efficiency. Notably, compared to the popular MeZO baseline, ZO-Muon requires only 24.7% of the queries to reach the same SST-2 performance for LLM fine-tuning, and improves accuracy by 25.1% on ViT-B fine-tuning on CIFAR-100.

Yicheng Lang, Changsheng Wang, Yihua Zhang +4

Michigan State University · University of Minnesota · University of California, Santa Barbara +2

Zeroth-Order Optimization Memory-Efficient Fine-Tuning LLM Fine-Tuning Muon Optimizer

Jan 29, 2026

Solving the Offline and Online Min-Max Problem of Non-smooth Submodular-Concave Functions: A Zeroth-Order Approach

We consider max-min and min-max problems with objective functions that are possibly non-smooth, submodular with respect to the minimiser and concave with respect to the maximiser. We investigate the performance of a zeroth-order method applied to this problem. The method is based on the subgradient of the Lovász extension of the objective function with respect to the minimiser and based on Gaussian smoothing to estimate the smoothed function gradient with respect to the maximiser. In expectation sense, we prove the convergence of the algorithm to an

ε

-saddle point in the offline case. Moreover, we show that, in the expectation sense, in the online setting, the algorithm achieves

O(\sqrt{N(1+\bar{P}_N)})

online duality gap, where

N

is the number of iterations and

\bar{P}_N

is the path length of the sequence of optimal decisions. The complexity analysis and hyperparameter selection are presented for all the cases. The theoretical results are illustrated via numerical examples.

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

School of Engineering, Australian National University, Canberra, Australia · Department of Mechanical Engineering, University of Texas at Dallas, Richardson, Texas, USA · Department of Electrical and Electronic Engineering, The University of Melbourne, Parkville, Australia

Min-Max Optimization Submodular Optimization Zeroth-Order Optimization

Nov 17, 2025

Power Homotopy for Zeroth-Order Non-Convex Optimizations

The existing method of GS-PowerOpt solves the non-convex optimization problem of the form

\max_{\boldsymbol{x} \in \mathbb{R}^d} f(\boldsymbol{x})

through maximizing a Gaussian-smoothed surrogate

F_{N,σ}(\boldsymbolμ) = \mathbb{E}_{\boldsymbol{x}\sim\mathcal{N}(\boldsymbolμ,σ^2 I_d)}[e^{N f(\boldsymbol{x})}]

. We analyze the role of the smoothing radius

σ>0

and identify a limitation of the fixed-

σ

design used in GS-PowerOpt. Specifically,

σ

induces an inherent exploration--refinement tradeoff: a larger

σ

improves global exploration and finite-time surrogate optimization, but may distort the location of the surrogate maximizer; in contrast, a smaller

σ

better preserves local structure but can weaken gradient signals away from high-value regions. To address this limitation, we propose GS-PowerHP, a power-smoothed homotopy method with an incrementally decaying

σ

schedule. The proposed mechanism uses larger smoothing radii in early iterations to maintain informative gradient signals when the iterate is far from high-value regions, and gradually decreases

σ

to improve local refinement near the maximizer. We provide theoretical results showing that this decaying schedule improves the exploration--refinement tradeoff of fixed-

σ

power smoothing. Empirically, GS-PowerHP consistently outperforms the fixed-

σ

baseline and exhibits robust performance across different optimization tasks, including adversarial attacks on ImageNet (

d=150{,}528

), where it substantially improves over other smoothing-based zeroth-order methods.

Chen Xu

Department of Engineering, Shenzhen MSU-BIT University, China.

Zeroth-Order Optimization Nonconvex Optimization

Jun 27, 2025

An Introduction to Zero-Order Optimization Techniques for Robotics

Zero-order optimization techniques are becoming increasingly popular in robotics due to their ability to handle non-differentiable functions and escape local minima. These advantages make them particularly useful for trajectory optimization and policy optimization. In this work, we propose a mathematical tutorial on random search. It offers a simple and unifying perspective for understanding a wide range of algorithms commonly used in robotics. Leveraging this viewpoint, we classify many trajectory optimization methods under a common framework and derive novel competitive RL algorithms.

Armand Jordana, Jianghan Zhang, Joseph Amigo +1

Machines in Motion Laboratory, New York University, USA

Zeroth-Order Optimization Robotic Optimization Robotic RL Trajectory Optimization

May 4, 2025

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

Zeroth-Order Optimization Constrained Optimization

Apr 13, 2025

Mirror Descent Linearized Augmented Lagrangian Methods for Nonconvex Constrained Stochastic Zeroth-Order Optimization

In this paper, we study nonconvex constrained stochastic zeroth-order optimization problems with exact constraints and stochastic objective evaluations. To solve this class of problems, we propose a framework of mirror descent linearized augmented Lagrangian methods that employs two-point stochastic zeroth-order gradient estimators and exploits non-Euclidean mirror descent geometry. Under mild assumptions, we establish oracle complexity guarantees for finding an

ε

-KKT point parameterized by

p \geq 2

. Under Rademacher smoothing, our analysis reveals a trade-off between the variance of the zeroth-order gradient estimators and the smoothness of the mirror map. In the high-accuracy regime, the resulting effective oracle complexity is

\mathcal{O}(p d^{2/p}ε^{-3})

for

p \in [2,2\ln d]

and

\mathcal{O}(\ln d\,ε^{-3})

for

p > 2\ln d

. These bounds reduce the dimension dependence in the leading term. When

p=2

, our method recovers the Euclidean setting with an oracle complexity of

\mathcal{O}(dε^{-3})

, improving the

ε

-dependence over existing methods. Furthermore, to eliminate initial near-feasibility requirements, we introduce a multi-stage scheme that finds an

ε

-KKT point within

\mathcal{O}(1+\log\log(e/ε))

stages while maintaining the leading-order complexity. Numerical tests on QCQPs, black-box adversarial attacks, and fairness-constrained classification demonstrate the effectiveness of our proposed method.

Qiankun Shi, Han Yuan, Xiao Wang +1

Sun Yat-sen University, Guangzhou, 510006, China · Pengcheng Laboratory, Shenzhen, 518066, China · Sun Yat-sen University, Guangzhou, 518066, China +1

Zeroth-Order Optimization Augmented Lagrangian Method Mirror Descent Constrained Optimization

Mar 10, 2025

Sample-Efficient Optimization over Generative Priors via Coarse Learnability

We study zeroth-order optimization where solutions must minimize a cost

d(s)

while maintaining high probability under a complex generative prior

L(s)

(e.g., a parameterized model). This reduces to sampling from a target distribution proportional to

L(s) e^{-T \cdot d(s)}

. Since classical model-based optimization (MBO) lacks finite-sample guarantees for expressive approximate learners, we introduce "coarse learnability", a flexible statistical assumption requiring only that a learned model covers the target's probability mass within a polynomial factor. Leveraging this assumption, we design an iterative MBO algorithm called \alift with a sample correction step that provably approximates the target using only a polynomial number of samples. We apply this framework to globally optimizing non-convex objectives bounded by a quadratic envelope in

R^n

, where we show this assumption is naturally satisfied for a family of "optimistic" posterior distributions. To reach global

\varepsilon

-optimality, this implies a sample complexity of

\widetilde{O}(\log 1/\varepsilon)

, a rate characteristic of optimistic space-partitioning methods. We further justify coarse learnability as an assumption for generative priors theoretically, proving that in simple settings, parametric maximum likelihood estimation and over-smoothed kernel density estimators naturally satisfy it. Finally, one motivation for our framework comes from inference-time alignment. Though our primary contribution pertains to the theoretical foundations of MBO, we provide qualitative evidence that, in simple settings, even primitive LLMs can shift their distributions toward lower-cost regions when fine-tuned with zeroth-order feedback.

Pranjal Awasthi, Sreenivas Gollapudi, Ravi Kumar +1

Google Research, Mountain View, USA · Department of Computer Science, Duke University, Durham, USA

Zeroth-Order Optimization

Sep 25, 2024

Risk-averse learning with delayed feedback

In real-world scenarios, risk-averse learning is valuable for mitigating potential adverse outcomes. However, the delayed feedback makes it challenging to assess and manage risk effectively. In this paper, we investigate risk-averse learning using Conditional Value at Risk (CVaR) as risk measure, while incorporating feedback with random but bounded delays. We develop two risk-averse learning algorithms that rely on one-point and two-point zeroth-order optimization approaches, respectively. The dynamic regrets of the algorithms are analyzed in terms of the cumulative delay and the number of total samplings. In the absence of delay, the regret bounds match the established bounds of zeroth-order stochastic gradient methods for risk-averse learning. Furthermore, the two-point risk-averse learning outperforms the one-point algorithm by achieving a smaller regret bound. We provide numerical experiments on a dynamic pricing problem to demonstrate the performance of the algorithms.

Siyi Wang, Zifan Wang, Karl Henrik Johansson +1

Division of Decision and Control Systems, School of Electrical Engineering and Computer Science, KTH Royal Institute of Technology, 10044 Stockholm, Sweden · Chair of Information-oriented Control (ITR), Technical University of Munich, Germany

Dynamic Regret Minimization Zeroth-Order Optimization Conditional Value-at-Risk

May 19, 2024

Gradient Testing and Estimation by Comparisons

We study gradient testing and gradient estimation of smooth functions using only a comparison oracle that, given two points, indicates which one has the larger function value. For any smooth

f\colon\mathbb R^n\to\mathbb R

,

\mathbf{x}\in\mathbb R^n

, and

\varepsilon>0

, we design a gradient testing algorithm that determines whether the normalized gradient

\nabla f(\mathbf{x})/\|\nabla f(\mathbf{x})\|

is

\varepsilon

-close or

2\varepsilon

-far from a given unit vector

\mathbf{v}

using

O(1)

queries, as well as a gradient estimation algorithm that outputs an

\varepsilon

-estimate of

\nabla f(\mathbf{x})/\|\nabla f(\mathbf{x})\|

using

O(n\log(1/\varepsilon))

queries which we prove to be optimal. Furthermore, we study gradient estimation in the quantum comparison oracle model where queries can be made in superpositions, and develop a quantum algorithm using

O(\log (n/\varepsilon))

queries.

Xiwen Tao, Chenyi Zhang, Helin Wang +2

School of Electronics Engineering and Computer Science, Peking University · Computer Science Department, Stanford University · Center on Frontiers of Computing Studies, Peking University +1

Black-Box Optimization Zeroth-Order Optimization