Overview

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

100 papers12 papers in the last four weeks, down 20% on the four weeks before. 0.1% of all new papers.

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(N(1+PˉN))O(\sqrt{N(1+\bar{P}_N)}) online duality gap, where NN is the number of iterations and PˉN\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.
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⁡x∈Rdf(x)\max_{\boldsymbol{x} \in \mathbb{R}^d} f(\boldsymbol{x}) through maximizing a Gaussian-smoothed surrogate FN,σ(μ)=Ex∼N(μ,σ2Id)[eNf(x)]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σ>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,528d=150{,}528), where it substantially improves over other smoothing-based zeroth-order methods.
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.
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.
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≥2p \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 O(pd2/pε−3)\mathcal{O}(p d^{2/p}ε^{-3}) for p∈[2,2ln⁡d]p \in [2,2\ln d] and O(ln⁡d ε−3)\mathcal{O}(\ln d\,ε^{-3}) for p>2ln⁡dp > 2\ln d. These bounds reduce the dimension dependence in the leading term. When p=2p=2, our method recovers the Euclidean setting with an oracle complexity of O(dε−3)\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 O(1+log⁡log⁡(e/ε))\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.
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)d(s) while maintaining high probability under a complex generative prior L(s)L(s) (e.g., a parameterized model). This reduces to sampling from a target distribution proportional to L(s)e−T⋅d(s)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 RnR^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 O~(log⁡1/ε)\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.
Feb 5, 2025

Bilevel ZOFO: Efficient LLM Fine-Tuning and Meta-Training

Fine-tuning pre-trained Large Language Models (LLMs) for downstream tasks using First-Order (FO) optimizers presents significant computational challenges. Parameter-Efficient Fine-Tuning (PEFT) methods address these by freezing most model parameters and training only a small subset. However, PEFT often underperforms compared to full fine-tuning when high task-specific accuracy is required. Zeroth-Order (ZO) methods fine-tune the entire pre-trained model without back-propagation, estimating gradients through forward passes only. While memory-efficient, ZO methods suffer from slow convergence and high sensitivity to prompt selection. We bridge these two worlds with Bilevel-ZOFO, a bilevel optimization method that couples fast, local FO-PEFT adaptation at the inner level with stable, memory-efficient ZO updates of the full backbone at the outer level. The FO-PEFT inner loop performs fast, low-memory local adaptation that reduces the variance of ZO estimates and stabilizes the search, guiding the outer ZO updates of the full backbone and reducing prompt sensitivity. In the mean time, the outer ZO provides better generalization ability for PEFT. We provide theoretical convergence guarantees and empirically demonstrate that Bilevel-ZOFO significantly outperforms existing ZO and FO-PEFT methods, achieving 2-4 times faster training while maintaining similar memory efficiency. Additionally, we show by updating the backbone with ZO and adapting only a tiny FO-PEFT block per task, Bilevel-ZOFO combines full-model capacity with few-shot efficiency, making it a very efficient meta-learning algorithm that quickly adapts to new tasks.
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.
Sep 24, 2024

A Historical Trajectory Assisted Optimization Method for Zeroth-Order Federated Learning

Federated learning heavily relies on distributed gradient descent techniques. In the situation where gradient information is not available, the gradients need to be estimated from zeroth-order information, which typically involves computing finite-differences along isotropic random directions. This method suffers from high estimation errors, as the geometric features of the objective landscape may be overlooked during the isotropic sampling. In this work, we propose a non-isotropic sampling method to improve zeroth-order gradient estimation. The method uses historical solution trajectories to identify a promising subspace and constructs a non-isotropic Gaussian smoothing that balances exploitation in this subspace with global exploration. We implement this method in zeroth-order federated settings, and show that the convergence rate aligns with existing ones while introducing no significant overheads in communication or local computation. The effectiveness of our proposal is verified on several numerical experiments in comparison to several commonly-used zeroth-order federated optimization algorithms. The experiments cover both independent and identically distributed data and heterogeneous client data distributions.
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 ⁣:Rn→Rf\colon\mathbb R^n\to\mathbb R, x∈Rn\mathbf{x}\in\mathbb R^n, and ε>0\varepsilon>0, we design a gradient testing algorithm that determines whether the normalized gradient ∇f(x)/∥∇f(x)∥\nabla f(\mathbf{x})/\|\nabla f(\mathbf{x})\| is ε\varepsilon-close or 2ε2\varepsilon-far from a given unit vector v\mathbf{v} using O(1)O(1) queries, as well as a gradient estimation algorithm that outputs an ε\varepsilon-estimate of ∇f(x)/∥∇f(x)∥\nabla f(\mathbf{x})/\|\nabla f(\mathbf{x})\| using O(nlog⁡(1/ε))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/ε))O(\log (n/\varepsilon)) queries.