Sampling-Based Zero-Order Optimization Algorithms

Xicheng Zhang · 2025

Read Sampling-Based Zero-Order Optimization Algorithms by Xicheng Zhang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-18201.txt.

Introduction

Xicheng Zhang presents a sampling-based method to find the best point of a function with no slope data. His 2025 paper deals with zeroth-order optimization, used when a task gives values only, not gradients. Mild smoothness terms on the task set the frame for the proof work.

He proves firm rates for how fast the method closes on the best point. Wide tests back the claims on famous bench tasks, smooth and rough alike. The method held up past a hundred dims, a scale where many such tools fade. It also coped with jumps and breaks in the task shape, which suits black-box tasks.

Catalog record

CREATORXicheng Zhang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE76 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-18201

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Sampling-Based Zero-Order Optimization Algorithms Thanks: Keywords: Zero-order optimization algorithm, Sampling, Monte-Carlo approximation Thanks: This work is supported by National Key R&D program of China (No. 2023YFA1010103) and NNSFC grant of China (No. 12131019) and the DFG through the CRC 1283 “Taming uncertainty and profiting from randomness and low regularity in analysis, stochastics and their applications”. Xicheng Zhang Abstract . We propose a novel zeroth-order optimization algorithm based on an efficient sampling strategy. Under mild global regularity conditions on the objective function, we establish non-asymptotic convergence rates for the proposed method. Comprehensive numerical experiments demonstrate the algorithm’s effectiveness, highlighting three key attributes: (i) Scalability: consistent performance in high-dimensional settings (exceeding 100 dimensions); (ii) Versatility: robust convergence across a diverse suite of benchmark functions, including Schwefel, Rosenbrock, Ackley, Griewank, Lévy, Rastrigin, and Weierstrass; and (iii) Robustness to discontinuities: reliable performance on non-smooth and discontinuous landscapes. These results illustrate the method’s strong potential for black-box optimization in complex, real-world scenarios. 1. Introduction Optimization constitutes a fundamental mathematical and computational discipline that arises across diverse fields including engineering, economics, machine learning, and operations research. Traditional optimization methodologies primarily focus on identifying the minimum or maximum of a given objective function, often subject to constraints. In its broadest sense, optimization refers to the process of systematically adjusting inputs to a system or model to achieve optimal performance as measured by a predefined criterion. This criterion is typically expressed through an objective function , which may be either maximized (e.g., profit, efficiency) or minimized (e.g., cost, error, time) [ 17 ] . Formally, a standard optimization problem in \mathbb{R}^{d} can be expressed as: \displaystyle x^{*}=\arg\max_{x\in\mathbb{R}^{d}}f(x)\quad\text{or}\quad x_{*}=\arg\min_{x\in\mathbb{R}^{d}}f(x) (1.1) subject to \displaystyle g_{i}(x)\leqslant 0,\quad i=1,\dots,m\quad\text{or}\quad h_{j}(x)=0,\quad j=1,\dots,p, (1.2) where f(x) denotes the objective function, g_{i}(x) represent inequality constraints, and h_{j}(x) equality constraints. Optimization problems can be classified according to various criteria: • Linear vs. Nonlinear: If both the objective function and all constraints are linear, the problem constitutes a linear program (LP); otherwise, it is a nonlinear program (NLP) [ 3 ] . • Convex vs. Non-convex: A problem is convex if the objective function is convex and the feasible region forms a convex set. Convex problems generally admit efficient solutions with guaranteed global optimality [ 3 ] . • Unconstrained vs. Constrained: Unconstrained optimization imposes no restrictions on variables, while constrained optimization requires solutions to satisfy additional equality or inequality constraints as specified in ( 1.2 ). • Deterministic vs. Stochastic: Deterministic optimization assumes perfectly known parameters, whereas stochastic optimization incorporates randomness or uncertainty in model data [ 20 ] . • Discrete vs. Continuous: Discrete optimization restricts variables to discrete values (e.g., integers), while continuous optimization permits variables to assume any real values within specified ranges. The selection of an appropriate optimization methodology is primarily determined by the underlying problem structure: • Gradient-Based Methods: These techniques utilize derivative information to guide the optimization process. Notable examples include: – Gradient descent: Iteratively moves in the direction of steepest descent x_{k+1}=x_{k}-\alpha\nabla f(x_{k}), (1.3) where \alpha denotes the learning rate. – Newton’s method: Incorporates second-order derivative information for accelerated convergence x_{k+1}=x_{k}-[\nabla^{2}f(x_{k})]^{-1}\nabla f(x_{k}). (1.4) – Stochastic gradient descent (SGD): Introduces controlled noise for improved generalization x_{k+1}=x_{k}-\alpha\nabla f(x_{k})+\sqrt{\alpha\varepsilon}\xi_{k}, (1.5) where \xi_{k}\sim\mathcal{N}(0,I_{d}) are independent Gaussian random variables. Comprehensive treatments can be found in [ 17 ] . • Derivative-Free Methods: These approaches are particularly valuable when gradient information is unavailable or computationally prohibitive. Prominent methods include the Nelder-Mead simplex algorithm, pattern search techniques, and Powell’s conjugate direction method [ 23 ] . • Metaheuristic Algorithms: These high-level strategies excel in complex optimization landscapes characterized by non-convexity, non-differentiability, or high dimensionality. Representative techniques include evolutionary algorithms (e.g., genetic algorithms), swarm intelligence methods (e.g., particle swarm optimization), and physics-inspired algorithms (e.g., simulated annealing). See [ 5 ] for a comprehensive overview. • Convex Optimization Techniques: For problems exhibiting convexity, specialized methods such as interior-point algorithms and barrier methods provide theoretically guaranteed polynomial-time convergence [ 3 ] . Despite their widespread utility, optimization methods face several fundamental challenges including computational complexity in high-dimensional spaces, convergence guarantees in non-convex landscapes, and sensitivity to noise and numerical instabilities. Contemporary research focuses on promising directions such as integration with machine learning paradigms, exploitation of problem structure (e.g., sparsity, separability), and development of parallel and distributed optimization frameworks [ 2 ] . The increasing computational capabilities and algorithmic innovations have significantly expanded the application domains of optimization techniques. Today, they form the computational backbone of numerous fields including large-scale machine learning model training [ 8 ] , complex systems design and control, operations research and logistics planning, and quantitative finance and portfolio optimization. The continued development of efficient, robust, and scalable optimization algorithms remains a critical research frontier as we confront increasingly complex problems across science and engineering disciplines. This paper develops a novel global zero-order optimization algorithm that builds upon recent advances in sampling techniques [ 24 ] . The proposed method offers three significant advantages over conventional optimization approaches: (i) Minimal regularity requirements: The algorithm imposes only weak assumptions on the target distribution, making it applicable to a broad class of optimization problems. (ii) High-dimensional non-convex optimization: The method maintains its effectiveness even for challenging, non-convex landscapes in high-dimensional spaces. (iii) Initialization robustness: Unlike many existing methods, our approach demonstrates low sensitivity to initial conditions, ensuring more reliable convergence. 1.1. Intuitive Foundation Let f:\mathbb{R}^{d}\rightarrow[0,\infty) be a probability density function. Given N independent samples \{X_{i}\}_{i=1}^{N} drawn from f , the maximum likelihood principle ensures that for any \varepsilon>0 and sufficiently large N , the following holds with high probability: \exists X_{k}\in\{X_{i}\}_{i=1}^{N}\text{ such that }\|X_{k}-x^{*}\|<\varepsilon, where x^{*}=\arg\max_{x\in\mathbb{R}^{d}}f(x) denotes the global maximizer, and \|\cdot\| represents the Euclidean norm in \mathbb{R}^{d} . Defining the empirical maximizer: \xi^{*}_{N}=\arg\max_{1\leqslant i\leqslant N}f(X_{i}), (1.6) we establish the following convergence result (see Theorem 2.3 ): \lim_{N\to\infty}\left(N^{2/d}\|f(\xi^{*}_{N})-f(x^{*})\|_{L^{p}(\Omega)}\right)<\infty, (1.7) provided \|\nabla^{2}f\|_{\infty}<\infty . However, this intuitive estimate becomes computationally infeasible for high-dimensional problems due to the excessively large sample size N required. Instead, we consider the minimization problem of a potential function via exponential tilting. Let U:\mathbb{R}^{d}\to[0,\infty] be a measurable function satisfying the integrability condition: \int_{\mathbb{R}^{d}}\mathrm{e}^{-U(x)}{\mathord{{\rm d}}}x<\infty. For any \theta\geqslant 1 , we define the probability measure: \mu_{\theta}({\mathord{{\rm d}}}x)\propto\mathrm{e}^{-\theta U(x)}{\mathord{{\rm d}}}x. A fundamental fact is that: \lim_{\theta\to\infty}\left(\int_{\mathbb{R}^{d}}\mathrm{e}^{-\theta U(x)}{\mathord{{\rm d}}}x\right)^{1/\theta}=\mathrm{e}^{-U_{*}}, where U_{*}=\inf_{x\in\mathbb{R}^{d}}U(x) . Moreover, as established in [ 9 ] , we have the weak convergence: \displaystyle\mu_{\theta}\xrightarrow{w}\mu\quad\text{as}\quad\theta\to\infty, (1.8) where \mu is supported on the minimizing manifold: {\mathscr{N}}:=\{x\in\mathbb{R}^{d}:U(x)=U_{*}\}. The characterization of the measure \mu on {\mathscr{N}} was originally established in [ 9 ] through an analysis of the Hessian matrix \nabla^{2}U . We note that while the existence result in ( 1.8 ) guarantees convergence, it does not yield explicit convergence rate estimates. Nevertheless, under the polynomial growth condition: for some \kappa_{0},\kappa_{1},m>0 , \displaystyle\kappa_{0}|x|^{m}\leqslant U(x)\leqslant\kappa_{1}|x|^{m}, (1.9) where 0 is the unique minimizer (without regularity assumptions on U ), we derive quantitative bounds for the convergence of the objective function U(x) to its minimum value U_{*} along the sampling points, and the convergence of the empirical minimizers to the true minimizer x_{*} . More precisely, for i.i.d. samples (X^{\theta}_{n})_{n=1,\cdots,N}\sim\mu_{\theta} and any p,\theta\geqslant 1 (see Corollary 2.9 ): \displaystyle\left\|1-\mathrm{e}^{-\min_{1\leqslant n\leqslant N}U(X^{\theta}_{n})}\right\|_{L^{p}(\Omega)}\leqslant\frac{d}{\theta m}+\mathrm{e}^{-N(\kappa_{0}/\kappa_{1})^{d/m}/(2p)}, (1.10) and for \alpha\in(0,\frac{1}{m}) , there exists C=C(p,d,\alpha,\kappa_{0},\kappa_{1},m)>0 such that (see Theorem 2.11 ) \displaystyle\|X^{\theta}_{n}-x_{*}\|_{L^{p}(\Omega)}\leqslant C\theta^{-\alpha},\quad\theta\geqslant 1. (1.11) In practical implementation,

Read the complete text