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⋅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 Rn, where we show this assumption is naturally satisfied for a family of "optimistic" posterior distributions. To reach global ε-optimality, this implies a sample complexity of O(log1/ε), 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.
Figures & tables
Figure 1: Optimization error trajectories ( ∣∣μ−x∗∣∣ ) versus iteration for ALDrIFT and TopIFT . (Left) Parameters: μd=0.5,A=2.0,ω=3.0,x0=6,μ0=0.1 . (Center) Parameters: μd=1.0,A=0.5,ω=4.0,x0=1.35,μ0=2.0 . (Right) Pr[\mboxAccept] of a sample versus the temperature τ in ALDrIFT .
Figure 2: Success rate of the models in finding a length k -cycle in a graph as a function of k . For each k , the graph is constructed by starting with a cycle of length k and randomly adding ⌈k/2⌉ other edges. For each cycle length k , we generate 50 random instances and compute the success rate, i.e., the fraction of times the model returns a length- k cycle. See Appendix B for the exact prompt used.
Figure 3: Box-plots of algorithm’s cost for the setting where the LLM’s visit time constraint is [1,20] . In (a), for 20 runs of TopIFT , the left two plots are the distribution of the algorithm’s cost for Best-of-LLM (N) baseline, while the right four plots are for TopIFT after r iterations. In (b), for one run of TopIFT , for different values of iteration r , the box-plot “ r:M ” is the distribution of the m⋅M=48 samples generated by the previous model, while “ r:T ” is the distribution of m=4 samples among these which have lowest algorithm’s cost (waiting time), and which are used for fine-tuning the new model.
Figure 4: Input graph and outputs of TopIFT and the various baselines. Note that (b) is simply the output of the base model L0 . The output of Best-of-ALG for N=600 and random spanning trees is comparable to (e), which means the model L0 assigns comparable probabilities to different random spanning trees.
Zeroth-order optimization uses function values or comparisons, rather than gradients, to optimize objectives when differentiation is unavailable or costly.
Zeroth-order (ZO) optimization offers a memory-efficient alternative to backpropagation for fine-tuning large language models. However, existing ZO methods typically sample training examples uniformly, overlooking their evolving importance and leaving avoidable estimation variance. To address this limitation, we propose Sample-Adaptive Zeroth-Order Optimization (SAZO), which learns sample importance online and adaptively allocates queries to accelerate convergence. SAZO extracts gradient-norm information from existing directional differences to estimate sample importance without access to true gradients. Furthermore, to track evolving importance from sparse minibatch feedback, SAZO maintains per-example exponential moving averages that aggregate observations across updates. The method requires no additional model evaluations and only O(N) additional scalar state compared with MeZO. We prove that SAZO asymptotically matches the leading convergence term of the minimum-variance sampling oracle, and achieves a strictly faster convergence rate than standard methods. Extensive experiments across four model families demonstrate improved average downstream performance and up to 6× faster convergence to the same training loss in terms of query count.
Haiyuan Wan, Yanyi Li, Weicheng Lin +1
School of Physics, Peking University · School of Intelligence Science and Technology, Peking University
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 (ZO) optimization is pivotal for scenarios where backpropagation is unavailable, such as memory-constrained on-device learning and black-box optimization. However, existing methods face a stark trade-off: they are either sample-inefficient (e.g., standard finite differences) or suffer from high variance due to randomized estimation (e.g., random subspace methods). In this work, we propose Coherent Coordinate Descent (CoCD), a deterministic, sample-efficient, and budget-aware ZO optimizer. Theoretically, we formalize the notion of gradient coherence and demonstrate that CoCD is equivalent to Block Cyclic Coordinate Descent (BCCD) with ``warm starts,'' effectively converting historical (stale) gradients from a liability into a computational asset. This mechanism enables O(1) query complexity per step while maintaining global descent directions. Furthermore, we derive error bounds revealing a counter-intuitive insight: larger finite-difference step sizes can induce an implicit smoothing effect on the optimization landscape by reducing the effective smoothness constant, thereby improving convergence stability. Experiments on MLP, CNN, and ResNet architectures (up to 270k parameters) demonstrate that CoCD significantly outperforms BCCD in terms of sample efficiency and convergence loss/accuracy, and exhibits superior stability over randomized ZO methods. Our results suggest that deterministic, structure-aware updates offer a superior alternative to randomization for lightweight ZO optimization.
Chen Liang, Xiatao Sun, Qian Wang +1
Department of Computer Science, Yale University, New Haven, USA.