# Low Regret Binary Sampling Method for Efficient Global Optimization of Univariate Functions

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 55 references that are in the map.
- First posted on arXiv 18 Jan 2022.

## Builds on (most cited first, 8 of 8)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Non-convex Optimization for Machine Learning](https://mlsanity.com/paper/1712.07897/) (2017)
- [Global optimization of Lipschitz functions](https://mlsanity.com/paper/1703.02628/) (2017)
- [A simple parameter-free and adaptive approach to optimization under a minimal local smoothness assumption](https://mlsanity.com/paper/1810.00997/) (2018)
- [Sequential Outlier Detection based on Incremental Decision Trees](https://mlsanity.com/paper/1803.03674/) (2018)
- [Regret analysis of the Piyavskii-Shubert algorithm for global Lipschitz optimization](https://mlsanity.com/paper/2002.02390/) (2020)
- [Cumulative Regret Analysis of the Piyavskii--Shubert Algorithm and Its Variants for Global Optimization](https://mlsanity.com/paper/2108.10859/) (2021)

## Built on by (most cited first, 11 of 11)

- [Nonconvex Extension of Generalized Huber Loss for Robust Learning and Pseudo-Mode Statistics](https://mlsanity.com/paper/2202.11141/) (2022)
- [A Linearithmic Time Locally Optimal Algorithm for the Multiway Number Partition Optimization](https://mlsanity.com/paper/2203.05618/) (2022)
- [Efficient Minimax Optimal Global Optimization of Lipschitz Continuous Multivariate Functions](https://mlsanity.com/paper/2206.02383/) (2022)
- [Blind Source Separation for Mixture of Sinusoids with Near-Linear Computational Complexity](https://mlsanity.com/paper/2203.14324/) (2022)
- [Merging Knockout and Round-Robin Tournaments: A Flexible Linear Elimination Tournament Design](https://mlsanity.com/paper/2203.12011/) (2022)
- [Robust, Nonparametric, Efficient Decomposition of Spectral Peaks under Distortion and Interference](https://mlsanity.com/paper/2204.08411/) (2022)
- [1D to nD: A Meta Algorithm for Multivariate Global Optimization via Univariate Optimizers](https://mlsanity.com/paper/2209.03246/) (2022)
- [A 2-opt Algorithm for Locally Optimal Set Partition Optimization](https://mlsanity.com/paper/2303.08219/) (2023)
- [Efficient Lipschitzian Global Optimization of H"older Continuous Multivariate Functions](https://mlsanity.com/paper/2303.14293/) (2023)
- [A Note On Nonlinear Regression Under L2 Loss](https://mlsanity.com/paper/2303.17745/) (2023)
- [Sequential Linearithmic Time Optimal Unimodal Fitting When Minimizing Univariate Linear Losses](https://mlsanity.com/paper/2304.02141/) (2023)

## Abstract (arXiv)

In this work, we propose a computationally efficient algorithm for the problem of global optimization in univariate loss functions. For the performance evaluation, 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 such as the Piyavskii-Shubert method for the Lipschitz continuous or Lipschitz smooth functions, it has a major computational cost advantage. In Piyavskii-Shubert method, for certain types of functions, the query points may be hard to determine (as they are solutions to additional optimization problems). However, this issue is circumvented in our binary sampling approach, where the sampling set is predetermined irrespective of the function characteristics. For a search space of [0,1], our approach has at most Llog (3T) and 2.25H regret for L-Lipschitz continuous and H-Lipschitz smooth functions respectively. We also analytically extend our results for a broader class of functions that covers more complex regularity conditions.