Every Call is Precious: Global Optimization of Black-Box Functions with Unknown Lipschitz Constants

• URL: http://arxiv.org/abs/2502.04290v1
• Date: Thu, 06 Feb 2025 18:34:40 GMT
• Title: Every Call is Precious: Global Optimization of Black-Box Functions with Unknown Lipschitz Constants
• Authors: Fares Fourati, Salma Kharrat, Vaneet Aggarwal, Mohamed-Slim Alouini,
• Abstract summary: We introduce Call Precious (P), a novel approach for global optimization of Lipschitz continuous functions. P eliminates the need to estimate the Lipschitz constant, thereby minimizing additional function. EC guarantees no-regret performance for evaluation budgets.
• Score: 72.47160195925056
• License:
• Abstract: Optimizing expensive, non-convex, black-box Lipschitz continuous functions presents significant challenges, particularly when the Lipschitz constant of the underlying function is unknown. Such problems often demand numerous function evaluations to approximate the global optimum, which can be prohibitive in terms of time, energy, or resources. In this work, we introduce Every Call is Precious (ECP), a novel global optimization algorithm that minimizes unpromising evaluations by strategically focusing on potentially optimal regions. Unlike previous approaches, ECP eliminates the need to estimate the Lipschitz constant, thereby avoiding additional function evaluations. ECP guarantees no-regret performance for infinite evaluation budgets and achieves minimax-optimal regret bounds within finite budgets. Extensive ablation studies validate the algorithm's robustness, while empirical evaluations show that ECP outperforms 10 benchmark algorithms including Lipschitz, Bayesian, bandits, and evolutionary methods across 30 multi-dimensional non-convex synthetic and real-world optimization problems, which positions ECP as a competitive approach for global optimization.

Related papers

• Optimal Rates for Robust Stochastic Convex Optimization [12.620782629498812]
  We develop novel algorithms that achieve minimax-optimal excess risk under the $epsilon$-contamination model. Our algorithms do not require restrictive assumptions, and can handle nonsmooth but Lipschitz population loss functions.
  arXiv  Detail & Related papers  (2024-12-15T00:52:08Z)
• Generalizing Bayesian Optimization with Decision-theoretic Entropies [102.82152945324381]
  We consider a generalization of Shannon entropy from work in statistical decision theory. We first show that special cases of this entropy lead to popular acquisition functions used in BO procedures. We then show how alternative choices for the loss yield a flexible family of acquisition functions.
  arXiv  Detail & Related papers  (2022-10-04T04:43:58Z)
• Algorithmic Foundations of Empirical X-risk Minimization [51.58884973792057]
  This manuscript introduces a new optimization framework machine learning and AI, named bf empirical X-risk baseline (EXM). X-risk is a term introduced to represent a family of compositional measures or objectives.
  arXiv  Detail & Related papers  (2022-06-01T12:22:56Z)
• 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)
• Low Regret Binary Sampling Method for Efficient Global Optimization of Univariate Functions [0.0]
  We study the cumulative regret of the algorithm instead of the simple regret between our best query and the optimal value of the objective function. Although our approach has similar regret results with the traditional lower-bounding algorithms, it has a major computational cost advantage.
  arXiv  Detail & Related papers  (2022-01-18T18:11:48Z)
• Regret Bounds for Gaussian-Process Optimization in Large Domains [40.92207267407271]
  We provide upper bounds on the suboptimality (Bayesian simple regret) of the solution found by optimization strategies. These regret bounds illuminate the relationship between the number of evaluations, the domain size, and the optimality of the retrieved function value. In particular, they show that even when the number of evaluations is far too small to find the global optimum, we can find nontrivial function values.
  arXiv  Detail & Related papers  (2021-04-29T05:19:03Z)
• Finding Global Minima via Kernel Approximations [90.42048080064849]
  We consider the global minimization of smooth functions based solely on function evaluations. In this paper, we consider an approach that jointly models the function to approximate and finds a global minimum.
  arXiv  Detail & Related papers  (2020-12-22T12:59:30Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  Motivated by recent increased interest in analysis of optimization algorithms for non- optimization in deep networks and other problems in data, we give an overview of recent results of theoretical optimization algorithms for non- optimization.
  arXiv  Detail & Related papers  (2020-12-11T08:28:51Z)
• Off-Policy Interval Estimation with Lipschitz Value Iteration [29.232245317776723]
  We propose a provably correct method for obtaining interval bounds for off-policy evaluation in a general continuous setting. We go on to introduce a Lipschitz value iteration method to monotonically tighten the interval, which is simple yet efficient and provably convergent.
  arXiv  Detail & Related papers  (2020-10-29T07:25:56Z)
• 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.