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

99 papers13 papers in the last four weeks, down 7% on the four weeks before. 0.1% of all new papers.

Nov 12, 2026

Wanda-Guided Sparse Perturbations for Efficient Zeroth-Order Optimization

Zeroth-order (ZO) optimization enables memory-efficient fine-tuning of large language models through forward-only evaluations, but high-dimensional random perturbations can limit optimization efficiency. Sparse perturbations reduce the search dimension, making the selection of informative coordinates critical. We propose Wanda-Importance Sparsity-MeZO (WIS-MeZO), which uses Wanda weight--activation saliency to construct task-conditioned sparse perturbation masks while keeping the pretrained model dense. We analyze support quality through gradient energy capture and relate it to gradient estimation and convergence. Across 16 benchmarks with LLaMA and Qwen models ranging from 3B to 32B parameters, WIS-MeZO achieves higher aggregate scores than MeZO and reaches comparable validation losses in fewer optimization steps. Comparisons with random and magnitude-based sparse perturbations further highlight the importance of informative support selection.
Nov 7, 2026

Zeroth-Order Riemannian Optimization on Fixed-Rank Manifolds for LLM Fine-Tuning

Zeroth-order (ZO) optimization estimates descent directions from function values alone, which removes the activation storage required by backpropagation and makes it attractive for memory-efficient fine-tuning of large language models (LLMs). Existing low-rank ZO methods either parameterize the additive update through Euclidean factors with a non-unique representation, or restrict each finite-difference direction to be low-rank. In this work, we propose to constrain each additive update block to a fixed-rank matrix manifold while keeping the pretrained weights frozen, so the learned update remains rank-constrained throughout fine-tuning. On this geometry, we build a Riemannian ZO gradient estimator that projects a random matrix onto the tangent space, normalizes it to correct the scale mismatch induced by projection, and further propose Zeroth-order Riemannian Gradient Descent (ZO-RGD) and its smoothed variant, ZO-RGD-S. We show that the ambient finite difference matches its retracted counterpart, the normalized estimator recovers the Riemannian gradient in expectation, and ZO-RGD converges under trajectory-regularity conditions. Experiments on LLM fine-tuning tasks show that the proposed algorithms are competitive with strong forward-only baselines across model families and tasks, with gains in several settings.
Nov 7, 2026

Breaking Precision Walls in First-, Second-, and Zeroth-Order Optimizers: One Constant, Set in Advance

Under power-law signal decay across directions, an optimizer can fit strong directions and miss weak ones while average loss hides it. A precision wall measures the steepest decay where the weakest direction recovers within 5% in a fixed budget. On low-rank matrix sensing and quadratics one constant sets the wall: once it dominates the denominator, Adam or grafted Shampoo is momentum descent at step η/cη/c, setting the wall; in Shampoo, matching grafting's constant to damping restores the wall after three hypotheses failed. In zeroth-order Adam, ε\varepsilon acts against ε∗\varepsilon^\ast from a mean-square spectral model; below ε∗\varepsilon^\ast error hits a noise floor. Set from true curvature or spectrum on new shapes, the rule raised the wall above the same-step default by a forecast amount: on two sensing shapes by 1.96,1.151.96, 1.15 (Adam) and 1.59,1.741.59, 1.74 (grafted Shampoo), and on two Hadamard-rotated quadratics by 1.12,0.731.12, 0.73 (zeroth-order Adam, longer budget), rising on all seeds; fixed-step momentum at that step reaches those walls. A cosine-scheduled default (small constant giving weak modes large steps) is higher on one sensing shape, matched on new seeds of the other, and lower with the rule's constant. A default step retuned per budget catches up on rotated quadratics and population logistic regression, fails at 1 query/step on two diagonal quadratics (catching up at 16), and exceeds the rule on digits logistic regression (full-batch and minibatches, where gradient noise sets the η=0.01,0.1η= 0.01, 0.1 default walls). On logistic regression the rule did not raise the first-order wall: same-step default Adam was higher (its wall on 4 new shapes at the forecast stability limit), while in zeroth order on the population loss setting ε\varepsilon raised the wall by 0.98,0.880.98, 0.88.
Nov 7, 2026

Zeroth-Order Langevin Dynamics for Stochastic Nonconvex Optimization: Curvature Regularization and Non-Asymptotic Guarantees

Zeroth-order methods provide a way to optimize stochastic nonconvex objectives using only noisy function evaluations. However, the smoothing inherent in their gradient estimators effectively modifies the objective being optimized. In particular, Gaussian smoothing with smoothing parameter η>0η>0 induces, to leading order, an implicit Hessian-trace regularization, which motivates the study of the curvature-regularized objective of the form f(x)+(η2/2)tr(∇2f(x))f(x)+(η^2/2) tr(\nabla^2 f(x)). We develop a non-asymptotic theory in the nonconvex setting for a class of algorithms called stochastic zeroth-order Langevin dynamics (ZOLD), which use only noisy function evaluations and do not have access to first- or higher-order derivative information, and derive excess-risk guarantees for the curvature-regularized objective. We first control the finite-time distribution of the ZOLD iterates in Wasserstein distance with respect to the Gibbs measure associated with the Gaussian-smoothed objective. An explicit coupling between the smoothing and inverse temperature parameters then quantifies the proximity of this measure to the Gibbs measure associated with the corresponding Hessian-trace-regularized objective. These distributional estimates in Wasserstein distance lead to excess-risk bounds for the curvature-regularized objective. Our analysis accommodates assumptions under which the stochastic function evaluations are allowed to have non-uniform dependence on the data stream. In addition, the constants in the non-asymptotic bounds do not rely on log-Sobolev or Poincaré inequalities as in prior zeroth-order Langevin analyses. To the best of our knowledge, this is the first non-asymptotic analysis of a zeroth-order Langevin method that simultaneously establishes excess-risk guarantees for a curvature-regularized objective and Wasserstein guarantees for the associated Gibbs measure in the nonconvex setting.
Nov 5, 2026

An Educated Guess: Deriving Statistically Aligned Gradient Estimates for Zeroth-Order Optimisation

As novel hardware architectures are explored for the purposes of machine learning, including neuromorphic chips, asynchronous systems, and ASICs, effective learning algorithms are highly desirable. While backpropagation is the standard for differentiation on standard hardware, its requirement for global synchrony and exact differentiability limits the exploration of exotic algorithms on non-traditional substrates and devices. Zeroth-order (ZO) optimisation methods, such as SPSA and weight perturbation, offer a compelling alternative by estimating gradients through inference-only passes; however, these methods have historically suffered due to the `curse of dimensionality', where random perturbations become increasingly misaligned with the true gradient in high-dimensional spaces. In this work, we move beyond blind random noise by deriving zeroth-order search directions from activation geometry available during the forward pass. This leads to a family of Spectral Zeroth-Order methods, SZO-κκ, whose directions solve local response-based gradient-guessing objectives under explicit stochastic assumptions. These methods explore feature-supported directions that are more likely to produce informative loss responses. Using multilayer and convolutional networks, we analyse gradient alignment, bias-variance structure, and training stability of these methods relative to standard perturbation baselines and backpropagation.
Nov 5, 2026

Randomized Parallel Complexity of Weakly Convex Optimization

We study the minimum number of query rounds needed to find approximate stationary points of nonsmooth weakly convex functions, measured by the gradient of the Moreau envelope. Each round permits multiple simultaneous queries. In the stated parameter regime, the standard subgradient rate is optimal in sufficiently high dimensions, even for randomized algorithms making polynomially many parallel queries per round. We then show how the order structure of the real line enables faster search: a deterministic algorithm using only function values achieves logarithmic round complexity, with a further reduction through parallel queries. Matching lower bounds hold even when each query returns the entire subdifferential. Together, these results clarify the role of dimension in determining the benefits of parallel queries for weakly convex optimization.
Nov 3, 2026

Training Specialist LLMs on Your Phone: Forward-Only Optimization via Block-Spectral Coordinates

Large language models (LLMs) on personal devices keep user data local, but limited memory restricts their general capability. Since most user-specific tasks do not require the breadth of frontier models, a practical solution is to adapt a shared on-device model into lightweight specialists. However, backpropagation is prohibitive in memory, and users rarely provide labeled data. We present MobileSpec, a system that trains specialists with forward passes alone and learns from automatically checked task outcomes, as in reinforcement learning with verifiable rewards (RLVR). Because forward-only updates are built from random perturbations, training is efficient only when these perturbations resemble the weight changes of RLVR, which largely preserve the singular values of pretrained weights and rotate their singular vectors. The core algorithm of MobileSpec, FuRA-S, produces such perturbations while training only the block-spectral coordinates of pretrained weights, namely the singular values of their column blocks. As we show theoretically and empirically, rescaling these blocks independently shifts their relative contributions to each weight matrix and thereby rotates its singular vectors. Since this update can be rewritten as a transformation of the layer input, FuRA-S also adapts INT4 models without modifying their weights. With specialists of only 1-5 MB that update 0.015-0.05% of the parameters, MobileSpec raises the success rate of a phone-use agent from 6-23% up to 89-100% and trains a personalized 8B model on an iPhone 16 Pro overnight. On RLVR benchmarks, FuRA-S is competitive with full-parameter evolution strategies (ES) and outperforms ES over LoRA adapters and quantized ES on INT4 models.
Nov 2, 2026

ENGINE: Endogenous Variational MultiScale Optimization for Zeroth-Order LLM Fine-Tuning

Zeroth-order (ZO) optimization enables memory-efficient large language model (LLM) fine-tuning, and recent methods incorporate curvature-aware strategies. However, in the high-dimensional parameter space of LLMs, these methods inherently suffer from exploding gradient variance and prohibitive costs. Conversely, confining updates to a low-dimensional subspace reduces variance but discards critical high-dimensional information, degrading performance. This creates a fundamental dilemma: full-space optimization is informative but has high variance, while subspace optimization has low variance but loses information. To break this trade-off, we propose ENGINE (Endogenous Variational MultiScale). Inspired by computational mechanics, we adapt static Variational MultiScale (VMS) theory to dynamic optimization, treating low- and high-dimensional spaces as resolved coarse and unresolved fine scales. Through a multigrid-style V-cycle, ENGINE alternates between spaces, dynamically probing fine-grained information in the high-dimensional space and injecting it to correct the efficient low-dimensional sampling process. Under appropriate assumptions, statistical analysis characterizes variance reduction and correction of curvature-induced bias, and convergence analysis establishes a stationarity bound for the corrected coarse updates. Evaluations on standard LLM benchmarks show that ENGINE achieves higher accuracy and faster convergence than existing ZO methods, achieving up to a 2.61×2.61\times speed-up in forward passes with zero additional peak memory overhead. Code is available at https://github.com/AI4Science-WestlakeU/ENGINE.
Nov 2, 2026

The Cost of Mismatch: Noise Amplification in Zeroth-Order Reinforcement Learning

Zeroth-order (ZO) optimization has emerged as a promising approach for memory-efficient large language model (LLM) post-training, yet its reliability in reinforcement learning with verifiable rewards (RLVR) remains largely unexplored. Motivated by the distinct data regimes of on-policy RL and fixed-data optimization, we develop a generic variance-theoretic framework to investigate what limits the reliability of ZO gradient estimation. Our analysis reveals that estimation reliability is structurally determined by whether the two finite-difference evaluations are performed on matched data. On-policy reinforcement learning (RL) under the mismatched-data regime produces a 1/μ21/μ^2 oracle-noise amplification that sets an irreducible noise floor as the perturbation scale μμ decreases, whereas Boltzmann Targeted SFT (BOLT) under the matched-data regime eliminates this amplification via noise cancellation. We further derive convergence guarantees with explicit constants that cleanly separate the two regimes. These results motivate the ZO-BOLT algorithm, which builds on BOLT's matched-data advantage for reliable ZO optimization of an RLVR-aligned objective. Controlled perturbation-scale sweeps and matched-versus-mismatched end-to-end comparisons validate the predicted effect of data matching. Experiments across three models and two mathematical reasoning benchmarks further show that ZO-BOLT consistently improves over the pretrained baseline while retaining a near-inference memory footprint. The code is publicly available at https://github.com/lianmin-chen/the_cost_of_mismatch.
Nov 2, 2026

Accelerating LLM Pretraining with Zeroth-Order Curvature on Idle Serving Compute

LLM pretraining is increasingly compute-intensive, while substantial inference serving compute remains idle during off-peak periods. However, such serving hardware is difficult to use for conventional first-order training due to its memory, networking and other system requirements. Zeroth-order (ZO) optimization offers a natural interface to this forward-only compute resource, but its gradient estimates break down in pretraining. Unlike fine-tuning, which can confine updates to a small parameter subspace, pretraining must update every parameter, and the alignment of a ZO gradient estimate with the true gradient shrinks as the number of updated parameters grows. We make a different observation: noisy ZO estimates can still provide useful curvature information, even when they are too inaccurate to serve as gradients. Based on this insight, we propose ZO-Curv, which leverages idle forward-only devices to estimate curvature and uses it to adapt and refine the update used during first-order training, thereby accelerating the process. We provide convergence guarantees that characterize the effect of finite-query curvature estimation. Experiments on LLMs from 125M to 1.5B parameters show that ZO-Curv consistently accelerates pretraining. At 770M parameters, ZO-Curv reaches AdamW's 20K-step validation loss in 3.9 hours instead of 7.5 hours, while achieving a lower final loss of 2.70 versus 2.84 under the same step budget. These results show that idle model serving compute can accelerate LLM pretraining when zeroth-order queries are used to estimate curvature rather than gradients directly.
Oct 20, 2026

Lower Bounds for Smooth Nonconvex Zeroth-Order Optimization: The Price of Determinism under Low Curvature Trace

Low curvature trace, an effective rank condition, is a common explanation for why randomized zeroth-order methods scale to high-dimensional tasks such as language model fine-tuning. Can deterministic methods achieve the same savings? We show that they cannot. We study finding ε\varepsilon-stationary points of LL-smooth nonconvex functions on Rd\mathbb{R}^d from exact function values, assuming that below the starting value the Hessian is dominated by a fixed matrix with trace at most LELE; this is a fixed-matrix form of the effective rank condition used to explain zeroth-order fine-tuning. When ET≤dET\le d, the Gaussian two-point method that such fine-tuning uses needs only O(ET)O(ET) calls if it rejects steps that raise ff, where T=LΔ/ε2T=LΔ/\varepsilon^2 is the iteration count of gradient descent from initial gap ΔΔ, and we prove that every randomized method needs Ω(ET)Ω(ET) calls, so this cost is optimal up to constants. In contrast, every deterministic method needs Ω~(dmin⁡{T,ET})\widetildeΩ(d\min\{T,\sqrt{ET}\}) calls, and adaptive subspace search attains O(dmin⁡{T,ET})O(d\min\{T,\sqrt{ET}\}): a deterministic method pays about dd calls per discovered direction, and the trace budget allows about ET\sqrt{ET} directions. Determinism thus multiplies the cost by a factor of order d/(E+ET)d/(E+\sqrt{ET}) up to logarithmic factors, which grows linearly with dd for fixed EE and TT; once EE exceeds TT by a logarithmic factor, deterministic methods need Ω(dT)Ω(dT) calls, as without any trace budget. Our lower bounds hold for C∞C^\infty functions with the matrix bound on all of Rd\mathbb{R}^d, even when each call also returns gradient projections priced by rank.
Oct 19, 2026

Training with ML-labeled Data via Stochastic First- and Zeroth-Order Optimization

Training a machine learning (ML) model is an optimization process that typically requires a set of examples with ground-truth labels beforehand. Obtaining these ground truths usually requires laborious human effort and can be costly. The scalability of human labeling becomes a concern when there are a large number of data points that need to be labeled. To address this practical issue, we consider an optimization setting where a subset of samples has ground-truth labels, while the remaining data points were labeled by an ML predictor, which could potentially assign incorrect labels to those points. We propose both first-order and zeroth-order stochastic optimization methods for training on datasets consisting of a mix of true-labeled and ML-labeled samples. We further conduct comprehensive empirical studies from training a linear regression model to fine-tuning a large language model (LLM) to showcase the effectiveness of the proposed algorithms for training with ML-labeled data.
Oct 14, 2026

On Global Joint Lower Bounds in Zeroth-Order Nonconvex Optimization

Must the dimension and accuracy costs of zeroth-order optimization multiply? Global upper bounds for smooth stochastic nonconvex optimization scale as O(dε−4)O(dε^{-4}), with both factors separately necessary. We show that their product is unavoidable. We establish an Ω(dε−4)Ω(dε^{-4}) lower bound for smooth stochastic nonconvex optimization, yielding an Ω(dδ−1ε−3)Ω(dδ^{-1}ε^{-3}) bound for nonsmooth Goldstein stationarity. Both match the best-known full-space upper bounds, establishing joint minimax optimality in dimension and accuracy. These bounds hold against fully adaptive randomized algorithms with unrestricted queries and outputs, even under arbitrary sample reuse. As a byproduct, we establish noiseless exact-value lower bounds for both smooth and Goldstein stationarity, even against randomized algorithms.
Oct 12, 2026

StructZO: Structured Zeroth-Order Optimization for Memory-Efficient LLM Fine-Tuning

Fine-tuning large language models at scale is increasingly limited by the memory cost of backpropagation. Zeroth-Order (ZO) optimizers reduce this burden by relying only on forward function evaluations, but they still exhibit a substantial performance gap to first-order (FO) optimizers such as Adam. We argue that this gap does not arise solely from the absence of explicit gradients: FO fine-tuning also benefits from informative low-rank optimization geometry, large-scale signal aggregation, and well-conditioned update directions. Motivated by this, we introduce StructZO, a structured Zeroth-Order optimization framework for memory-efficient LLM fine-tuning. StructZO performs large-query ZO estimation within an activation-induced informative subspace and applies spectral control to the resulting reduced-space update before mapping it back to the original parameters. This lets ZO aggregate useful directional signals in a compact, geometry-aware space while avoiding the activation and optimizer-state memory costs of backpropagation. We show theoretically that, when the induced subspace captures concentrated optimization-relevant directions, StructZO reduces the effective ZO estimation dimension from mnmn to mrmr, with the remaining projection error governed by the spectral tail of the activation Gram matrix. Empirically, across OPT-series and Llama3.1-8B on diverse downstreamtasks, StructZO improves over the strongest existing ZO baselines by up to 8.78.7% relative on average and up to 26.926.9% relative on individual tasks, while remaining within 1.51.5% of FO-Adam on average. These results suggest that structured and spectrally controlled ZO updates can substantially narrow the gap between ZO and FO optimization.
Oct 10, 2026

Zeroth-Order Fine-Tuning of LLMs in Learnable Low-Rank Subspaces

Zeroth-order (ZO) optimization enables memory-efficient fine-tuning of large language models (LLMs). However, ZO optimization suffers from high variance in high-dimensional parameter spaces. While recent methods restrict perturbations to random low-rank subspaces, these subspaces often misalign with task-specific descent directions. We propose AdaSub-ZO, a novel forward-only fine-tuning framework in learnable low-rank subspaces. Instead of relying on fixed random matrices, AdaSub-ZO iteratively learns layer-wise projection matrices directly from finite-difference feedback to track task-aware descent directions. Furthermore, AdaSub-ZO incorporates a subspace momentum acceleration mechanism to smooth noisy gradient estimates across evolving subspace bases. Extensive experiments on natural language understanding tasks demonstrate that AdaSub-ZO outperforms existing ZO baselines, substantially reducing gradient estimation variance and accelerating convergence.
Oct 9, 2026

Partially Informed Stochastic Optimization via Zeroth-Order Residual Tracking

Many optimization problems provide direct access to only part of the gradient, while the remaining component must be inferred from function evaluations. This structure arises in performative prediction, performative reinforcement learning, and bilevel optimization with a black-box lower level. We introduce Partially Informed Stochastic Optimization (PISO), which combines the available gradient component with a running estimate of the residual. By centring each zeroth-order observation on this estimate, PISO makes the variance due to random probing depend on the tracking error rather than the residual's magnitude. This yields a randomized sketch iteration with an explicit contraction mechanism and a principled interpretation of momentum. For smooth nonconvex objectives, we establish convergence guarantees that depend on the residual's variation and initial magnitude, without requiring a uniform bound on the unavailable gradient component. With independently sampled function evaluations and Gaussian or spherical probes, PISO attains leading function-evaluation complexities of O(d2ε−6)O(d^{2}\varepsilon^{-6}) under Lipschitz gradients and O(d2ε−5)O(d^{2}\varepsilon^{-5}) under an additional Lipschitz-Hessian assumption. These rates require only one probe direction, two function samples, and one known-component sample per update. The analysis also quantifies how batching trades observations for fewer deployments. Across five settings, PISO variants improve on the tested baselines with comparable oracle access in three, reach a comparable solution faster in bilevel routing, and perform best among methods without response-model derivatives in performative reinforcement learning.
Oct 9, 2026

Optimal Algorithms for Nonsmooth Nonconvex Stochastic Optimization with Constraints

We present new algorithms for stochastic optimization problems in which the objective is neither smooth nor convex, subject to a convex constraint set. Our algorithms return a (δ,ε)(δ,\varepsilon)-Goldstein stationary point, as recently defined for constrained problems by Liu et al. (2024), with improved complexities, and are the first to achieve optimal convergence rates for this task in several settings. In particular, we design projection-based and projection-free algorithms that achieve a O~(δ−1ε−3)\widetilde O(δ^{-1}\varepsilon^{-3}) rate using stochastic gradients, which we show to be optimal, and a O~(dδ−1ε−3)\widetilde O(dδ^{-1}\varepsilon^{-3}) rate using zeroth-order queries, which is also optimal in its dependence on the dimension dd and improves over prior work. Notably, our lower bound is given in terms of the Frank-Wolfe gap and holds even for smooth problems, which is of independent interest. These results show that in nonconvex stochastic optimization, the convergence rate is degraded neither by the presence of constraints nor by nonsmoothness. Our analysis is based on a reduction to online linear optimization, extending a related technique from unconstrained optimization.
Oct 8, 2026

Sample-Adaptive Zeroth-Order Post-Training

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)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×6\times faster convergence to the same training loss in terms of query count.
Oct 5, 2026

VLA-ZO: Fast Zeroth-Order Adaptation for Vision-Language-Action Models

Adapting vision-language-action (VLA) models to deployment-time distribution shifts is important for reliable robotic operation, but conventional first-order adaptation can exceed the memory budget of inference-oriented deployment platforms. Zeroth-order (ZO) optimization offers a forward-only alternative with inference-level memory, but accurate gradient estimation requires many perturbation queries, making naive ZO prohibitively slow for large VLA models. We present VLA-ZO, a framework for fast ZO adaptation that exploits the structure of VLA computation. By confining adaptation to the action side, VLA-ZO keeps the expensive vision-language prefix frozen and reuses its conditioning states across perturbation queries and optimizer steps, while schedule-aware prefetching hides state-transfer overhead. On LIBERO camera-viewpoint shifts, VLA-ZO reduces end-to-end adaptation time by 25.59×\times at q=16q=16 and 32.54×\times at q=64q=64 relative to baseline ZO, while improving average task success from 48.27% without adaptation to 58.17% and 63.58%, respectively. These results show that making ZO faster can make larger query budgets practical, providing a promising path toward resource-efficient VLA adaptation on deployment platforms.
Oct 1, 2026

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 Zero-and-First-Order 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.
Sep 30, 2026

Manifold-Constrained Initial Noise Optimization for Efficient Generative Model Alignment

Recent advances in distillation and flow-map models have enabled deterministic one- or few-step generation for high-quality data, facilitating a new branch of reward alignment approaches that directly optimize the initial noise from a Gaussian distribution. However, most existing initial-noise optimization methods rely on first-order gradient information, which is either inapplicable or suffers from instability and inefficiency in black-box reward scenarios. Here, we introduce ZeNOVA, a stable and efficient initial noise alignment method in a gradient-free manner. Specifically, we address existing algorithms' major challenge in black-box scenarios through annealed soft-value guidance, manifold-constrained hyperspherical Langevin dynamics, and Metropolis-Hastings jumping. Extensive experiments on image and video generative models show that ZeNOVA outperforms all evaluated zeroth-order baselines by optimizing the initial noise toward higher rewards substantially more stably while exploiting the geometry of the Gaussian prior, demonstrating its practical applicability to various black-box reward alignment.
Sep 29, 2026

Parameter-Free Zeroth-Order Optimization with Ellipsoidal Sampling

Zeroth-order optimization methods are essential for solving black-box problems where gradient information is unavailable or expensive to compute. This paper presents POEM-ES, a novel parameter-free stochastic zeroth-order algorithm that extends the recent POEM method by integrating subspace preconditioning with ellipsoidal randomized sampling. In contrast to traditional zeroth-order approaches that rely on isotropic random directions, POEM-ES performs anisotropic sampling guided by a fixed structural symmetric positive semi-definite (SPSD) preconditioner Σ^\hatΣ that encodes the underlying low-dimensional geometry. Under a standard structural spectral normalization where λmax⁡(Σ^)=1λ_{\max}(\hatΣ) = 1, we introduce the use of the empirical effective dimension d∗=tr⁡(Σ^)d^* = \operatorname{tr}(\hatΣ), which reflects the intrinsic dimensionality of the problem and guides both the sampling and randomized smoothing parameter schedules. In practice, such a preconditioner can be effectively obtained via pilot sampling, historical trajectories, or domain-specific expert knowledge. We prove that POEM-ES achieves a dimension-reduced convergence rate under low-rank structural assumptions, requiring only O~((r2κ(Σ^)+d∗)L2DX2ε2)\tilde{\mathcal{O}}\left( \frac{\left( r^2 κ(\hatΣ) + d^* \right) 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∗≪dd^* \ll d. Numerical experiments on hinge-loss binary classification tasks using LibSVM datasets confirm the practical superiority of the proposed approach.
Sep 29, 2026

Probe-Space Preconditioning for Fast and Stable Zero-Order Training

Backpropagation (BP) dominates deep learning but imposes a massive memory tax. For example, training OPT-30B with Adam requires ≈\approx 600GB of GPU memory (assuming batch size 8 and sequence length 2048). Alternatively, zero-order optimization (ZOO) trains in inference-mode (requiring only ≈\approx 60GB for the same model): no stored activations, no gradients, and no optimizer states. However, ZOO convergence has lagged behind BP. In this work, we evaluate two methods to close this gap. First, we show that reallocating training compute budget from many steps to large effective batch sizes with many perturbations (or probes) but fewer steps, allows 1SPSA (Spall, 1992) to outperform zero order methods like MeZO (Malladi et al., 2023) with less training compute. Next, we introduce 1.5-SPSA, adding a single "clean" forward-pass per step to 1SPSA to calculate a cheap diagonal preconditioner in probe-space, which improves convergence rate and convergence by down-weighting high curvature directions. Benchmarking on 6 post-training datasets on both Qwen3 and OPT model families, we show that 1.5-SPSA achieves State-of-the-Art results over previous ZOO solvers with much less optimization steps. For example, we train OPT-13B (for direct comparison to MeZO) and find 1.5-SPSA achieves +3.1% accuracy on SST-2 over both MeZO and BP in only 70 steps vs. MeZO's 100,000 steps. Finally, we combine an 8-bit-packing random generator, triton fused unpack/apply kernels, and distributed parallelism to achieve fast and stable training of models as large as OPT-30B in-place on commodity GPUs (e.g. A100).
Sep 29, 2026

Scaling Zero-Order Pretraining through Model Sharding

Zero-order optimization (ZO) trains without backpropagation, making it relevant to forward-only hardware and non-differentiable loss, but its gradient variance grows with perturbed dimension, inhibiting large-model training. Sharded Optimization Mixture of Assemblies (SOMA) trains LSTM experts independently on NN data clusters using simultaneous perturbation stochastic approximation (SPSA), without exchanging gradients, activations or optimizer state. Its separable loss removes cross-expert perturbation noise at the cost of jointly learned representations across domains. Using 80,000 estimated RTX 5090 GPU-hours, we show modest sharding improves training compute efficiency over all tested monolithic ZO controls. At 8.44M parameters and 150 aggregate GPU-hours, SOMA N=2N=2 with 64 perturbations reaches 1.76 test nats/byte, versus 2.00--2.11 for monolithic SPSA at 64, 256 or 1,024 perturbations and 2.21 for EGGROLL. On WikiText-103, these frozen checkpoints reach 2.07, 2.25--2.36 and 2.49, respectively. On a fixed separable objective with equal-size blocks, we prove independent losses reduce relative gradient variance to approximately 1/N1/N of a shared-loss estimator's. Holding starting weights, data, perturbations and compute fixed, independent rather than summed losses lower SOMA N=4N=4 test loss by 0.035 nats/byte after 1,000 updates across three seeds. Larger ensembles offer a separate inference benefit: at similar model size with top-kk routing (k=4k=4), SOMA N=256N=256 achieves 2.36M tokens/s versus 257k for SOMA N=8N=8 (9.19×9.19\times, including routing), at lower test loss (1.68 versus 1.71), albeit using 59.9×59.9\times as much aggregate training compute. We release all training and evaluation code and checkpoints.
Sep 28, 2026

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
Sep 27, 2026

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.
Sep 26, 2026

PolyStepOR: Learning to Decide Without Optimal Decisions

Decision-focused learning (DFL) trains predictors for downstream decision quality, but often relies on optimal reference decisions that are expensive to obtain. We present PolyStepOR, which trains directly from realized decision costs without pre-computed optima and extends to in-constraint predictions through repair or infeasibility penalties. To handle piecewise-constant losses, PolyStepOR perturbs predictor parameters, evaluates the resulting decisions, and uses optimal transport to favor lower-cost directions, requiring no derivatives. Without task-specific tuning, PolyStepOR performs strongly on classical optimization benchmarks and competitively on predicted-constraint and real-world problems. Theoretically, we characterize decision-preserving perturbations and boundary detection, bound sensitivity to cost errors, and establish stationarity guarantees for a smoothed objective. PolyStepOR thus replaces optimal reference decisions and derivatives with forward evaluations.
Sep 15, 2026

Derivative-Free Structured Updates for Muon

Muon updates matrix-valued neural-network parameters by orthogonalizing a gradient-based momentum matrix. Its reliance on derivatives limits its use when gradients are unavailable or unreliable. We develop a derivative-free framework that constructs Muon-style updates from structured finite differences. Four variants are considered: full entrywise recovery, random low-rank surrogates, basis-aligned rank-one probing, and direct structured search. Exhaustive basis-aligned probing is equivalent, up to positive scaling before ideal polar orthogonalization, to coordinate finite differences. Matrix-regression experiments show that random rank-one probing can reduce the number of function evaluations substantially, at the cost of less accurate updates. Controlled noisy-gradient experiments on regression and a neural network illustrate when accurate function values can compensate for an unreliable gradient oracle. A small CartPole study further examines orthogonal rank-one probes under a fixed episode budget. These results support structured probing as a practical option for selected black-box problems; they do not establish a general convergence guarantee or an advantage over accurate, inexpensive gradients.
Sep 8, 2026

Adaptively Incorporating Directional Hints into Zeroth-Order Optimization

We study zeroth-order optimization of nonconvex 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)O(1/T) rate and the zeroth-order O(d/T)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 nonconvex landscapes where zeroth-order descent is slower and existing guided methods stall as guidance deteriorates.
Sep 7, 2026

MpSub: A Momentum pp-Dimensional Subspace Trust-Region Method for Derivative-Free Fine-Tuning of Large Language Models

Full-parameter fine-tuning of large language models has substantial memory costs because backpropagation stores activations and gradients. Zeroth-order optimization avoids this by estimating update directions from loss evaluations, but existing methods require tuning a sensitive learning rate for each model and task. We propose the momentum pp-dimensional subspace trust-region method (MpSub). At each iteration, MpSub searches within a pp-dimensional subspace: one direction preserves historical momentum from the most recent accepted step, while the remaining directions explore via fresh random sampling. The subspace gradient is estimated by central differences, a trial step is computed from a linear trust-region model, and the trust-region radius adapts according to the agreement between predicted and observed loss reduction, eliminating the learning rate. For LLM fine-tuning, evaluations within an iteration share a minibatch, and directions are regenerated in place from seeds, using forward passes alone. For smooth deterministic objectives under unorthogonalized Gaussian directions, we bound the finite-difference error, quantify gradient energy captured by the subspace, and prove that lim⁡k→∞∥∇f(xk)∥2=0\lim_{k\to\infty} \|\nabla f(x_k)\|_2 = 0 almost surely under a safeguarded radius update. Under a matched budget of 8,400 training-objective forward passes, we fine-tune OPT-125M and OPT-350M on CommitmentBank. With the same preset parameters at both model sizes, MpSub attains mean test accuracies of 0.673 and 0.690 over three seeds, matching tuned MeZO (0.685) without any learning-rate search.