Low Regret Binary Sampling Method for Efficient Global Optimization of Univariate Functions
원문 초록
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 $L\log (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.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
NeRF-based CBCT Reconstruction needs Normalization and Initialization
A Hybrid GA LLM Framework for Structured Task Optimization
A Divide-and-Conquer Approach for Global Orientation of Non-Watertight Scene-Level Point Clouds Using 0-1 Integer Optimization
Improving LLM-based Global Optimization with Search Space Partitioning
Physics-guided and fabrication-aware inverse design of photonic devices using diffusion models
SUDO: Enhancing Text-to-Image Diffusion Models with Self-Supervised Direct Preference Optimization
토론
이 논문과 연결된 포럼 글이 아직 없습니다.