Black-box optimization of noisy functions with unknown smoothness

• URL: http://arxiv.org/abs/2605.02462v1
• Date: Mon, 04 May 2026 11:04:31 GMT
• Title: Black-box optimization of noisy functions with unknown smoothness
• Abstract summary: We study the problem of black-box optimization of a function f of any dimension, given function evaluations perturbed by noise.<n>Our contribution is an adaptive optimization algorithm, POO or parallel optimistic optimization, that is able to deal with this setting.<n>We provide a finite-time analysis of POO's performance, which shows that its error after n evaluations is at most a factor of sqrt(ln n) away from the error of the best known optimization algorithms.
• Score: 28.994787715086872
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of black-box optimization of a function f of any dimension, given function evaluations perturbed by noise. The function is assumed to be locally smooth around one of its global optima, but this smoothness is unknown. Our contribution is an adaptive optimization algorithm, POO or parallel optimistic optimization, that is able to deal with this setting. POO performs almost as well as the best known algorithms requiring the knowledge of the smoothness. Furthermore, POO works for a larger class of functions than what was previously considered, especially for functions that are difficult to optimize, in a very precise sense. We provide a finite-time analysis of POO's performance, which shows that its error after n evaluations is at most a factor of sqrt(ln n) away from the error of the best known optimization algorithms using the knowledge of the smoothness.

Related papers

• Bandits attack function optimization [30.108594392153744]
  We consider an algorithm inspired by a continuous version of a multi-armed bandit problem which attacks this optimization problem.<n>We introduce the so-called Simultaneous Optimistic Optimization (SOO), a deterministic algorithm that works by domain partitioning.<n>We present this machine learning approach to optimization, and provide the empirical assessment of SOO on the CEC'2014 competition.
  arXiv  Detail & Related papers  (2026-05-05T08:33:44Z)
• Stochastic simultaneous optimistic optimization [70.50540950403109]
  We study the problem of evaluations of a function f given a finite number of perturbed by noise.<n>Our algorithm, StoSOO, follows an optimistic strategy to construct upper confidence bounds over the hierarchical partitions of the function domain to decide which point to sample next.<n>A finite-time analysis of StoSOO shows that it performs almost as well as the best specifically-tuned algorithms even though the local smoothness of the function is not known.
  arXiv  Detail & Related papers  (2026-04-27T14:34:24Z)
• Non-Convex Optimization with Certificates and Fast Rates Through Kernel Sums of Squares [68.8204255655161]
  We consider potentially non- optimized approximation problems. In this paper, we propose an algorithm that achieves close to optimal a priori computational guarantees.
  arXiv  Detail & Related papers  (2022-04-11T09:37:04Z)
• Online Calibrated and Conformal Prediction Improves Bayesian Optimization [10.470326550507117]
  This paper studies which uncertainties are needed in model-based decision-making and in Bayesian optimization. Maintaining calibration, however, can be challenging when the data is non-stationary and depends on our actions. We propose using simple algorithms based on online learning to provably maintain calibration on non-i.i.d. data.
  arXiv  Detail & Related papers  (2021-12-08T23:26:23Z)
• Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information [78.78486761923855]
  In many real world problems, we want to infer some property of an expensive black-box function f, given a budget of T function evaluations. We present a procedure, InfoBAX, that sequentially chooses queries that maximize mutual information with respect to the algorithm's output. On these problems, InfoBAX uses up to 500 times fewer queries to f than required by the original algorithm.
  arXiv  Detail & Related papers  (2021-04-19T17:22:11Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  We study the problem of zero-order optimization of a strongly convex function. We consider a randomized approximation of the projected gradient descent algorithm. Our results imply that the zero-order algorithm is nearly optimal in terms of sample complexity and the problem parameters.
  arXiv  Detail & Related papers  (2020-06-14T10:42:23Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope. Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
  arXiv  Detail & Related papers  (2020-06-11T17:43:19Z)
• Incorporating Expert Prior in Bayesian Optimisation via Space Warping [54.412024556499254]
  In big search spaces the algorithm goes through several low function value regions before reaching the optimum of the function. One approach to subside this cold start phase is to use prior knowledge that can accelerate the optimisation. In this paper, we represent the prior knowledge about the function optimum through a prior distribution. The prior distribution is then used to warp the search space in such a way that space gets expanded around the high probability region of function optimum and shrinks around low probability region of optimum.
  arXiv  Detail & Related papers  (2020-03-27T06:18:49Z)
• Composition of kernel and acquisition functions for High Dimensional Bayesian Optimization [0.1749935196721634]
  We use the addition-ality of the objective function into mapping both the kernel and the acquisition function of the Bayesian Optimization. This ap-proach makes more efficient the learning/updating of the probabilistic surrogate model. Results are presented for real-life application, that is the control of pumps in urban water distribution systems.
  arXiv  Detail & Related papers  (2020-03-09T15:45:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.