2016/03/14 by Cédric Malherbe, Malherbe, Cédric, Nicolas Vayatis +1 · 6 citations
Computer Science · Decision Sciences · Mathematics · #Advanced Bandit Algorithms Research #Advanced Optimization Algorithms Research #Algorithm #Artificial intelligence #Bipartite graph #Computer science #Convergence (economics) #FOS: Computer and information sciences #Function (biology) #Global optimization #Machine Learning (stat.ML) #Machine Learning and Algorithms #Mathematical optimization #Mathematics #Optimization problem #Ranking (information retrieval) #Set (abstract data type) #Space (punctuation) #Theoretical computer science #stat.ML
paper · pdf · doi:10.48550/arxiv.1603.04381
published in arXiv (Cornell University), 1539-1547 (Cornell University)
openalex publication_date 2016/03/14 · arxiv created 2017/03/07 · arxiv updated 2017/03/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the problem of maximizing an unknown function over a compact and convex set using as few observations as possible. We observe that the optimization of the function essentially relies on learning the induced bipartite ranking rule of f. Based on this idea, we relate global optimization to bipartite ranking which allows to address problems with high dimensional input space, as well as cases of functions with weak regularity properties. The paper introduces novel meta-algorithms for global optimization which rely on the choice of any bipartite ranking method. Theoretical properties are provided as well as convergence guarantees and equivalences between various optimization methods are obtained as a by-product. Eventually, numerical evidence is given to show that the main algorithm of the paper which adapts empirically to the underlying ranking structure essentially outperforms existing state-of-the-art global optimization algorithms in typical benchmarks.