# Global optimization of Lipschitz functions

arXiv: https://arxiv.org/abs/1703.02628 · HTML: https://mlsanity.com/paper/1703.02628/

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Mar 2017.

## Built on by (most cited first, 30 of 39)

- [Statistical, Robustness, and Computational Guarantees for Sliced Wasserstein Distances](https://mlsanity.com/paper/2210.09160/) (2022)
- [Task Facet Learning: A Structured Approach to Prompt Optimization](https://mlsanity.com/paper/2406.10504/) (2024)
- [Discrepancy-Based Active Learning for Domain Adaptation](https://mlsanity.com/paper/2103.03757/) (2021)
- [Deep Learning for Bayesian Optimization of Scientific Problems with High-Dimensional Structure](https://mlsanity.com/paper/2104.11667/) (2021)
- [On Safety in Safe Bayesian Optimization](https://mlsanity.com/paper/2403.12948/) (2024)
- [GoTube: Scalable Stochastic Verification of Continuous-Depth Models](https://mlsanity.com/paper/2107.08467/) (2021)
- [Low Regret Binary Sampling Method for Efficient Global Optimization of Univariate Functions](https://mlsanity.com/paper/2201.07164/) (2022)
- [On the Generalization for Transfer Learning: An Information-Theoretic Analysis](https://mlsanity.com/paper/2207.05377/) (2022)
- [Max-Sliced Mutual Information](https://mlsanity.com/paper/2309.16200/) (2023)
- [Cumulative Regret Analysis of the Piyavskii--Shubert Algorithm and Its Variants for Global Optimization](https://mlsanity.com/paper/2108.10859/) (2021)
- [Instance-Dependent Bounds for Zeroth-order Lipschitz Optimization with Error Certificates](https://mlsanity.com/paper/2102.01977/) (2021)
- [Global Optimization with Parametric Function Approximation](https://mlsanity.com/paper/2211.09100/) (2022)
- [Comparative analysis of machine learning methods for active flow control](https://mlsanity.com/paper/2202.11664/) (2022)
- [Boosting Soft Q-Learning by Bounding](https://mlsanity.com/paper/2406.18033/) (2024)
- [Optimised one-class classification performance](https://mlsanity.com/paper/2102.02618/) (2021)
- [Query Attack by Multi-Identity Surrogates](https://mlsanity.com/paper/2105.15010/) (2021)
- [Certified Multi-Fidelity Zeroth-Order Optimization](https://mlsanity.com/paper/2308.00978/) (2023)
- [Every Call is Precious: Global Optimization of Black-Box Functions with Unknown Lipschitz Constants](https://mlsanity.com/paper/2502.04290/) (2025)
- [Efficient Minimax Optimal Global Optimization of Lipschitz Continuous Multivariate Functions](https://mlsanity.com/paper/2206.02383/) (2022)
- [Stein Boltzmann Sampling: A Variational Approach for Global Optimization](https://mlsanity.com/paper/2402.04689/) (2024)
- [Parameter-Free Algorithms for Performative Regret Minimization under Decision-Dependent Distributions](https://mlsanity.com/paper/2402.15188/) (2024)
- [ECPv2: Fast, Efficient, and Scalable Global Optimization of Lipschitz Functions](https://mlsanity.com/paper/2511.16575/) (2025)
- [Wave-Informed Matrix Factorization with Global Optimality Guarantees](https://mlsanity.com/paper/2107.09144/) (2021)
- [Combining Lipschitz and RBF Surrogate Models for High-dimensional Computationally Expensive Problems](https://mlsanity.com/paper/2204.14236/) (2022)
- [A unified weighting framework for evaluating nearest neighbour classification](https://mlsanity.com/paper/2311.16872/) (2023)
- [Active Bipartite Ranking with Smooth Posterior Distributions](https://mlsanity.com/paper/2602.24263/) (2026)
- [Training Deep Neural Networks via Branch-and-Bound](https://mlsanity.com/paper/2104.01730/) (2021)
- [High-Dimensional Simulation Optimization via Brownian Fields and Sparse Grids](https://mlsanity.com/paper/2107.08595/) (2021)
- [Power of human-algorithm collaboration in solving combinatorial optimization problems](https://mlsanity.com/paper/2107.11784/) (2021)
- [1D to nD: A Meta Algorithm for Multivariate Global Optimization via Univariate Optimizers](https://mlsanity.com/paper/2209.03246/) (2022)

## Abstract (arXiv)

The goal of the paper is to design sequential strategies which lead to efficient optimization of an unknown function under the only assumption that it has a finite Lipschitz constant. We first identify sufficient conditions for the consistency of generic sequential algorithms and formulate the expected minimax rate for their performance. We introduce and analyze a first algorithm called LIPO which assumes the Lipschitz constant to be known. Consistency, minimax rates for LIPO are proved, as well as fast rates under an additional H"older like condition. An adaptive version of LIPO is also introduced for the more realistic setup where the Lipschitz constant is unknown and has to be estimated along with the optimization. Similar theoretical guarantees are shown to hold for the adaptive LIPO algorithm and a numerical assessment is provided at the end of the paper to illustrate the potential of this strategy with respect to state-of-the-art methods over typical benchmark problems for global optimization.