论文检索

Optimization · Zero-order and Black-box Optimization

Mingyue Qin, Shuyu Yin, Qinghai Guo, Xiaolin Huang, Peilin Liu, Fei Wen

The human brain is a biologically instantiated on-device neural system that integrates both learning and inference in a unified architecture, which enables rapid and flexible learning on-the-fly. This extraordinary capability is achieved through non-BP learning mechanisms, whereas BP is computationally and memory intensive that unsuitable for on-chip edge learning. Zeroth-order (ZO) optimization methods, which resemble biologically plausible perturbation-based learning, offer a promising alternative that enables learning with only forward passes and hence can significantly reduce the complexity of on-chip hardware implementation. However, in this work we show that applying ZO methods to spiking neural networks (SNNs) is non-trivial due to the step-function nature of spiking activation. We analyze the challenges posed by the spiking activation, and reveal a variance amplification effect of it. Based on this insight, we propose a subspace-based ZO (SZO) method that leverages the intrinsic low-dimensional structure of the SNN optimization trajectory. By learning in a low-dimensional subspace, SZO substantially enhances ZO learning efficacy, achieving accuracy comparable to first-order (FO) methods with faster learning speed than full-space BP. We evaluate SZO on model training from scratch, continual training, and unsupervised adaptation. Experimental results demonstrate that SZO closely approaches FO training performance for the first time while offering fast learning speed.

Optimization · Zero-order and Black-box Optimization

Muqi Han, Ruoqi Xing, KAI WU, Xiaoyu Zhang, Handing Wang, Zilong Wang

Meta Black-Box Optimization (MetaBBO) has emerged as a promising paradigm by employing meta learning to automatically optimize the configurations of low-level black-box optimizers. Despite its potential, the generalization of MetaBBO remains significantly constrained when facing unseen, complex objective landscapes. We identify that this bottleneck stems from a restricted performance upper bound inherent in current training mechanisms: by learning from scratch in a self-supervised or unsupervised manner, meta optimizers are never exposed to advanced, high-quality optimization behaviors, forcing them to converge on suboptimal strategies. In this paper, we propose $\texttt{MetaDistill}$, a general MetaBBO training framework designed to lift the strategy ceiling through pretraining and test-time fine-tuning. In the pretraining stage, we represent high-quality strategies from classical algorithms as expert optimization trajectories and utilize them for diversity-preserving distillation, enabling the learnable optimizer to internalize advanced optimization behaviors. In the optional fine-tuning stage, we perform self-supervised fine-tuning as a warm-start procedure to further refine the distilled knowledge on unseen tasks. We evaluate our $\texttt{MetaDistill}$ framework on the BBOB test suite and three control tasks. The results demonstrate that $\texttt{MetaDistill}$ significantly improves the generalization ability of various learnable optimizers compared to their original training paradigms.

Optimization · Zero-order and Black-box Optimization

Yuxuan Ren, Abhishek Roy, Shiqian Ma

Dueling optimization considers optimizing an objective with access to only a comparison oracle of the objective function. It finds important applications in emerging fields such as recommendation systems and robotics. Existing works on dueling optimization mainly focused on unconstrained problems in the Euclidean space. In this work, we study dueling optimization over Riemannian manifolds, which covers important applications that cannot be solved by existing dueling optimization algorithms. In particular, we propose a Riemannian Dueling Normalized Gradient Descent (RDNGD) method and establish its iteration complexity when the objective function is geodesically $L$-smooth or geodesically (strongly) convex. We also propose a projection-free algorithm, named Riemannian Dueling Frank–Wolfe (RDFW) method, to deal with the situation where projection is prohibited. We establish the iteration and oracle complexities for RDFW. We illustrate the effectiveness of the proposed algorithms through numerical experiments on both synthetic and real applications.

Optimization · Zero-order and Black-box Optimization

Amir Ali Farzin, Yuen-Man Pun, Philipp Braun, Tyler Summers, Iman Shames

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 $\epsilon$-saddle point in the offline case. Moreover, we show that, in the expectation sense, in the online setting, the algorithm achieves $O(\sqrt{N\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.

Optimization · Zero-order and Black-box Optimization

Chen Wang, Sijie Ma, Zeyuan Ma, Yue-Jiao Gong

Benchmark Design in Black-Box Optimization (BBO) is a fundamental yet open-ended topic. Early BBO benchmarks are predominantly human-crafted, introducing expert bias and constraining diversity. Automating this design process can relieve the human-in-the-loop burden while enhancing diversity and objectivity. We propose Evolution of Benchmark (EoB), an automated BBO benchmark designer empowered by the large language model (LLM) and its program evolution capability. Specifically, we formulate benchmark design as a bi-objective optimization problem towards maximizing (i) landscape diversity and (ii) algorithm-differentiation ability across a portfolio of BBO solvers. Under this paradigm, EoB iteratively prompts LLM to evolve a population of benchmark programs and employs a reflection-based scheme to co-evolve the landscape and its corresponding program. Comprehensive experiments validate our EoB is a competitive candidate in multi-dimensional usages: 1) Benchmarking BBO algorithms; 2) Training and testing learning-assisted BBO algorithms; 3) Extending proxy for expensive real-world problems.

Optimization · Zero-order and Black-box Optimization

Yan Zhang, Xuefeng Liu, Sipeng Chen, Sascha Ranftl, Chong Liu, Shibo Li

Standard Bayesian Optimization (BO) assumes uniform smoothness across the search space—an assumption violated in multi-regime problems such as molecular conformation search through distinct energy basins or drug discovery across heterogeneous molecular scaffolds. A single GP either oversmooths sharp transitions or hallucinates noise in smooth regions, yielding miscalibrated uncertainty. We propose RAMBO, a Dirichlet Process Mixture of Gaussian Processes that automatically discovers latent regimes during optimization, each modeled by an independent GP with locally-optimized hyperparameters. We derive collapsed Gibbs sampling that analytically marginalizes latent functions for efficient inference, and introduce adaptive concentration parameter scheduling for coarse-to-fine regime discovery. Our acquisition functions decompose uncertainty into intra-regime and inter-regime components. Experiments on synthetic benchmarks and real-world applications—including molecular conformer optimization, virtual screening for drug discovery, and fusion reactor design—demonstrate consistent improvements over state-of-the-art baselines on multi-regime objectives.

Optimization · Zero-order and Black-box Optimization

Mingqian Li, Sina Zadeh, Raymundo Arroyave, Xiaoning Qian

In batch multi-objective Bayesian optimization (MOBO), it is often desirable to identify the whole Pareto optimal set, especially when considering the complicated interplay between different design criteria and constraints. This poses unique challenges in acquiring batches of both high quality and diversity to cover the Pareto front. We propose a novel acquisition strategy, Probability of Matching (POM), which evaluates both batch candidate quality and diversity by explicitly capturing the likelihood that all batch points are Pareto optimal, and the probability that they collectively cover the full Pareto set. To estimate the coverage probability and promote diversity, we incorporate non-replacement sampling principles, resulting in our new POM-guided batch MOBO method. Across synthetic benchmarks and real-world tasks, our method consistently outperforms state-of-the-art baselines on standard MOBO metrics as well as a new design-space coverage metric, Expected Minimum Distance (EMD), with comparable computational efficiency.

Optimization · Zero-order and Black-box Optimization

Kairun Zhang, Haoyu Li, Yanjun Zhao, Yifan Sun, Huan Zhang

Zeroth-order optimizers have recently emerged as an attractive approach for fine-tuning large language models (LLMs), as they avoid backpropagation and can substantially reduce memory overhead relative to standard first-order training. However, existing zeroth-order methods rely on hand-crafted, static sampling strategies that are not adaptable to model-specific structures. To address this, we propose ZO Fine-tuner, a learning-based zeroth-order optimizer for LLMs that automatically learns efficient perturbation strategies through a compact and memory-efficient design. Motivated by the fact that a small set of base LLMs is repeatedly fine-tuned across tasks, ZO Fine-tuner supports one-time per-model training and reuse across downstream tasks with minimal overhead. Therefore, learning the optimizer once for a given LLM and reusing it across diverse downstream tasks is both feasible and highly desirable. Accordingly, ZO Fine-tuner is designed to scale learning to learn (L2L) to the foundation-model era by supporting one-time per-model training with minimal overhead. Experiments on 4 LLMs and 7 datasets show that ZO Fine-tuner outperforms prior zeroth-order baselines in 82.1\% of task-model combinations, thereby demonstrating strong performance and scalability for efficient LLM fine-tuning.

Optimization · Zero-order and Black-box Optimization

Johannes Ackermann, Stefano Peluchetti

When gradient information is unavailable, black-box optimization (BBO) methods provide a practical alternative. While Evolution Strategies (ES), Consensus-Based Optimization (CBO), Optimization via Integration (OVI), and related methods have each been studied independently, their connections remain underexplored. We unify these approaches within a common theoretical framework, revealing that they differ primarily in two design choices: fitness aggregation (controlling sharpness preference) and consensus scope (controlling modality). Leveraging these insights, we introduce hybrid optimizers that interpolate between existing methods. Our ES-OVI hybrid allows explicit control over the preference for flat minima, enabling a trade-off between performance and robustness in continuous control tasks. Our CBO-OVI hybrids combine the high-dimensional efficiency of parametric methods with the multimodal capabilities of particle-based approaches, achieving competitive results on language model merging under limited evaluation budgets. We validate our methods on standard BBO benchmarks and high-dimensional locomotion tasks, demonstrating that the hybrid methods can outperform their constituent algorithms.

Optimization · Zero-order and Black-box Optimization

Yiyi Zhu, Yaolin Wen, Xiang Xia, Xin An, Hanyi Si, Xiang Shu, Yangde Fu, Liang Dou, Hong Qian

Multi-objective optimization (MOO) has emerged as a powerful approach to solving complex optimization problems involving multiple objectives. In many practical scenarios, function evaluations are unavailable or prohibitively expensive, necessitating optimization solely based on a fixed offline dataset. In this setting, known as offline MOO, the goal is to find out the Pareto set without access to the true objective functions. This setting suffers from the out-of-distribution (OOD) issue, where the surrogate model is not accurate for unseen designs. Due to the OOD issue, surrogate errors may cause the optimizer to select solutions that do not lie on the true Pareto front and are biased toward its extremes. To address this, this paper proposes Diversity-driven Offline Multi-Objective Optimization (DOMOO), which aims to find out a diverse and high-quality set of solutions. Firstly, DOMOO incorporates an accumulative risk control module that estimates the potential risk of candidate solutions and alleviates the OOD issue between the training data and the generated solutions. In addition, a nested Pareto set learning (PSL) strategy is proposed to jointly learn preference and PSL parameters, then optimize them, enabling adaptation to diverse Pareto front geometries. To further enhance solution quality, we design a diversity-driven selection strategy that extracts a representative and well-distributed set of final solutions. To achieve this diversity-driven selection strategy, we propose $\text{IGD}\_{\text{offline}}$, a tailored indicator for the offline setting that considers both diversity and convergence, and avoids the bias of hypervolume indicator. Extensive experiments on synthetic and real-world benchmarks, such as neural architecture search, show that, on average across benchmarks, DOMOO achieves a 1.44× improvement in convergence and diversity over comparable methods.

Optimization · Zero-order and Black-box Optimization

Geng Li, Yuxin Peng

While Multimodal Large Language Models (MLLMs) demonstrate impressive general capabilities, they struggle with fine-grained perception in ultra-high-resolution (UHR) images, particularly for tiny objects in cluttered scenes. Existing methods face a dilemma: they either rely on inefficient prior-free scanning, or depend on static prior-driven heuristics that lack posterior correction to rectify initial model biases. To address this, we propose **BVS** (**B**ayesian **V**isual **S**earch), a framework that formulates perception as a global optimization problem over a continuous spatial-scale manifold. Specifically, BVS bridges prior guidance with posterior correction: it utilizes an early-stop attention rollout of MLLM to construct reasoning-aware priors, while employing a scale-aware non-stationary kernel and GP-UCB to dynamically rectify noise and recover missing information in the prior through iterative local observations. We provide theoretical guarantees via sub-linear regret bounds, and extensive experiments demonstrate that BVS significantly outperforms state-of-the-art baselines with a superior trade-off between accuracy and efficiency.

Optimization · Zero-order and Black-box Optimization

Minhak Song, Liang Zhang, Bingcong Li, Niao He, Michael Muehlebach, Sewoong Oh

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 CNNs, ResNets, and Transformers on vision tasks. 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.

Optimization · Zero-order and Black-box Optimization

Sichen Wang, Zhipeng Lu

Noisy evolution strategies commonly mitigate ranking uncertainty by improving per-generation fidelity—for example, by allocating budget to resampling candidates or using robust aggregation to stabilize the within-generation ordering. Under strict fixed evaluation budgets, however, any additional intra-generation querying directly reduces the number of generations the algorithm can execute, shortening the optimization trajectory. This dynamic can be characterized as prioritizing fidelity over depth. We propose a paradigm shift in fixed-budget regimes toward depth over fidelity, arguing that the cumulative progress from a long sequence of noise-smoothed updates often outweighs that of a short sequence of rigorously denoised ones. We operationalize this principle via probabilistic elite membership, replacing hard truncation with conditional expected rank weights that integrate over ranking uncertainty. This shifts noise handling from the evaluation stage to the selection stage: rather than repeatedly reevaluating candidates to denoise their objective values, we directly smooth the selection signal driving the update. We instantiate this approach using residual bootstrapping: we perform sparse reevaluations near the selection boundary, store standardized noise residuals in a reusable pool, and generate bootstrap rankings to estimate expected weights. Recognizing that residual pool mismatch constitutes a potential statistical risk, we derive a falsifiable error decomposition and provide runtime diagnostics to ensure estimator validity. To prevent oversmoothing in low-noise regimes, we introduce an adaptive probe-and-switch mechanism that leverages a low-cost rank disagreement metric to dynamically select between standard CMA-ES and our bootstrap-based updates. Extensive evaluations across the COCO bbob-noisy suite and diverse external tasks—including RL policy search and noisy HPO—demonstrate consistent gains. Specifically, in high-misranking regimes constrained by strict budgets, our residual-bootstrap approach achieves substantially steeper progress curves than both uncertainty-handling CMA-ES and fixed-k resampling baselines. These results substantiate a testable thesis: when budgets are limited and ranking uncertainty is high, integrating uncertainty at the selection stage is more sample-efficient than reducing it at the evaluation stage.

Optimization · Zero-order and Black-box Optimization

Wei LIN, Yining Jiang, Qingyu Song, Qiao Xiang, Hong Xu

Zeroth-Order (ZO) optimization has emerged as a promising solution for fine-tuning LLMs under strict memory constraints, as it avoids the prohibitive memory cost of storing activations for backpropagation. However, existing ZO methods typically employ isotropic perturbations, neglecting the rich structural information available during the forward pass. In this paper, we identify a crucial link between gradient formation and activation structure: the gradient of a linear layer is confined to the subspace spanned by its input activations. Leveraging this insight, we propose Activation-Guided Zeroth-Order optimization (AGZO). Unlike prior methods, AGZO extracts a compact, activation-informed subspace on the fly during the forward pass and restricts perturbations to this low-rank subspace. We provide a theoretical framework showing that AGZO optimizes a subspace-smoothed objective and provably yields update directions with higher cosine similarity to the true gradient than isotropic baselines. Empirically, we evaluate AGZO on Qwen3 and Pangu models across various benchmarks. AGZO consistently outperforms state-of-the-art ZO baselines and significantly narrows the performance gap with first-order fine-tuning, while maintaining almost the same peak memory footprint as other ZO methods.

Optimization · Zero-order and Black-box Optimization

Jingzhe Jing, Zheyi Fan, Szu Hui Ng, Qingpei Hu

Bayesian optimization (BO) for high-dimensional constrained problems remains a significant challenge due to the curse of dimensionality. We propose **L**ocal **C**onstrained **B**ayesian **O**ptimization (LCBO), a novel framework tailored for such settings. Unlike trust-region methods that are prone to premature shrinking when confronting tight or complex constraints, LCBO leverages the differentiable landscape of constraint-penalized surrogates to alternate between rapid local descent and uncertainty-driven exploration. Theoretically, we prove that LCBO achieves a convergence rate for the Karush-Kuhn-Tucker (KKT) residual that depends polynomially on the dimension $d$ for common kernels under mild assumptions, offering a rigorous alternative to global BO where regret bounds typically scale exponentially. Extensive evaluations on high-dimensional benchmarks (up to 100D) demonstrate that LCBO consistently outperforms state-of-the-art baselines.

Optimization · Zero-order and Black-box Optimization

Zhe Li, Bicheng Ying, Zidong Liu, Haibo Yang

Classical optimization theory establishes that zeroth-order (ZO) algorithms suffer from a dimension-dependent slowdown, with convergence rates typically scaling with the model dimension compared to first-order methods. However, in contrast to these theoretical expectations, a growing body of recent work demonstrates the successful application of ZO methods to fine-tuning Large Language Models (LLMs) with billions of parameters. To explain this paradox, we derive the one-step learning dynamics of ZO SGD, where the empirical Neural Tangent Kernel (eNTK) naturally emerges as the key term governing the learning behavior. Inspection of the eNTK produced by ZO-SGD reveals that each element corresponds to the inner product of neural tangent vectors projected onto a random low-dimensional subspace. Thus, by invoking the Johnson-Lindenstrauss Lemma, our analysis shows that the fidelity of the ZO eNTK is governed primarily by the number of perturbations. Crucially, the approximation error depends on the model output size rather than the massive parameter dimension. This dimension-free property provides a theoretical justification for the scalability of ZO methods to LLMs finetuning tasks. We believe that this kernel-based framework offers a novel perspective for understanding ZO methods within the context of learning dynamics.

Optimization · Zero-order and Black-box Optimization

Chao Wang, Licheng Jiao, Lingling Li, Jiaxuan Zhao, Guanchun Wang, Fang Liu, Shuyuan Yang

Handcrafted optimizers become prohibitively inefficient for complex black-box optimization (BBO) tasks. MetaBBO addresses this challenge by meta-learning to automatically configure optimizers for low-level BBO tasks, thereby eliminating heuristic dependencies. However, existing methods typically require extensive handcrafted training tasks to learn meta-strategies that generalize to target tasks, which poses a critical limitation for realistic applications with unknown task distributions. To overcome the issue, we propose the Adaptive meta Black-box Optimization Model (ABOM), which performs online parameter adaptation using solely optimization data from the target task, obviating the need for predefined task distributions. Unlike conventional metaBBO frameworks that decouple meta-training and optimization phases, ABOM introduces a closed-loop adaptive parameter learning mechanism, where parameterized evolutionary operators continuously self-update by leveraging generated populations during optimization. This paradigm shift enables zero-shot optimization: ABOM achieves competitive performance on synthetic BBO benchmarks and realistic unmanned aerial vehicle path planning problems without any handcrafted training tasks. Visualization studies reveal that parameterized evolutionary operators exhibit statistically significant search patterns, including natural selection and genetic recombination.

Optimization · Zero-order and Black-box Optimization

Bryon Tjanaka, Henry Chen, Matthew Fontaine, Stefanos Nikolaidis

Quality diversity (QD) optimization searches for a collection of solutions that optimize an objective while attaining diverse outputs of a user-specified, vector-valued measure function. Contemporary QD algorithms are typically limited to low-dimensional measures because high-dimensional measures are prone to distortion, where many solutions found by the QD algorithm map to similar measures. For example, the state-of-the-art CMA-MAE algorithm guides measure space exploration with a histogram in measure space that records so-called discount values. However, CMA-MAE stagnates in domains with high-dimensional measure spaces because solutions with similar measures fall into the same histogram cell and hence receive the same discount value. To address these limitations, we propose Discount Model Search (DMS), which guides exploration with a model that provides a smooth, continuous representation of discount values. In high-dimensional measure spaces, this model enables DMS to distinguish between solutions with similar measures and thus continue exploration. We show that DMS facilitates new capabilities for QD algorithms by introducing two new domains where the measure space is the high-dimensional space of images, which enables users to specify their desired measures by providing a dataset of images rather than hand-designing the measure function. Results in these domains and on high-dimensional benchmarks show that DMS outperforms CMA-MAE and other existing black-box QD algorithms.

Optimization · Zero-order and Black-box Optimization

Shanwen Mao, Hao Zhang, Jiasheng Li, Haoyu Qiao, Chenxin Cai, Tingting Wu, Jie Liu

With the rapid scaling of large language models, achieving efficient compression while maintaining model performance has become a critical challenge. To address the limitations of existing non-uniform quantization methods, which typically rely on fixed codebooks and require costly optimization, we propose a novel arbitrary bit-width non-uniform Quantization (NuBitQ). The framework enables flexible, layer-specific quantization strategies, significantly enhancing adaptability and efficiency. Notably, traditional outlier compensation methods used in uniform quantization are ill-suited for the anomalous distribution characteristics encountered in our context. To address this, we design a novel outlier evaluation metric that integrates weight perturbation, activation distribution, and perturbation propagation. Based on this metric, we further develop an Outlier Compensation Plugin (OCP) that implements multi-level, fine-grained outlier compensation strategies, effectively mitigating performance degradation caused by outliers. Our approach avoids direct complex Hessian computation and fine-tuning, offering strong applicability and scalability. Extensive experiments on multiple tasks and across various model series demonstrate the effectiveness of the proposed approach.

Optimization · Zero-order and Black-box Optimization

Shengminjie Chen, Xiaoming Sun, Wenguo Yang, Jialin Zhang, Zihan Zhao

In this work, we investigate DR-submodular maximization using stochastic biased gradients, which is a more realistic but challenging setting than stochastic unbiased gradients. We first generalize the Lyapunov framework to incorporate biased stochastic gradients, characterizing the adverse impacts of bias and noise. Leveraging this framework, we consider not only conventional constraints but also a novel constraint class: convex sets with a largest element, which naturally arises in applications such as resource allocations. For this constraint, we propose an $1/e$ approximation algorithm for non-monotone DR-submodular maximization, surpassing the hardness result $1/4$ for general convex constraints. As a direct application of stochastic biased gradients, we consider zero-order DR-submodular maximization and introduce both classical and quantum gradient estimation algorithms. In each constraint we consider, while retaining the same approximation ratio, the iteration complexity of our classical zero-order algorithms is $O(\epsilon^{-3})$, matching that of stochastic unbiased gradients; our quantum zero-order algorithms reach $O(\epsilon^{-1})$ iteration complexity, on par with classical first-order algorithms, demonstrating quantum acceleration and validated in numerical experiments.