Certified Multi-Fidelity Zeroth-Order Optimization
We consider the problem of multi-fidelity zeroth-order optimization, where one can evaluate a function $f$ at various approximation levels (of varying costs), and the goal is to optimize $f$ with the cheapest evaluations possible. In this paper, we study certified algorithms, which are additionally required to output a data-driven upper bound on the optimization error. We first formalize the problem in terms of a min-max game between an algorithm and an evaluation environment. We then propose a certified variant of the MFDOO algorithm and derive a bound on its cost complexity for any Lipschitz function $f$. We also prove an $f$-dependent lower bound showing that this algorithm has a near-optimal cost complexity. As a direct example, we close the paper by addressing the special case of noisy (stochastic) evaluations, which corresponds to $\eps$-best arm identification in Lipschitz bandits with continuously many arms.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
How to Robustify Black-Box ML Models? A Zeroth-Order Optimization Perspective
The lack of adversarial robustness has been recognized as an important issue for state-of-the-art machine learning (ML) models, e.g., deep neural networks (DNNs). Thereby, robustifying ML models against adversarial attac…
Adversarial Robustnessimage-classificationImage ClassificationImage ReconstructionStochastic Subspace Descent Accelerated via Bi-fidelity Line Search
Efficient optimization remains a fundamental challenge across numerous scientific and engineering domains, especially when objective function and gradient evaluations are computationally expensive. While zeroth-order opt…
Wall-Clock Complexity for Zeroth-Order Optimization with Tunable Oracle Fidelity
Zeroth-order (black-box) optimization is applied when gradients are unavailable and objective evaluations rely on expensive simulations. In many such applications, the oracle fidelity is tunable: higher-accuracy queries …
Distributed Zeroth-Order Optimization: Convergence Rates That Match Centralized Counterpart
Zeroth-order optimization has become increasingly important in complex optimization and machine learning when cost functions are impossible to be described in closed analytical forms. The key idea of zeroth-order o…
Gaussian Loss Smoothing Enables Certified Training with Tight Convex Relaxations
Training neural networks with high certified accuracy against adversarial examples remains an open challenge despite significant efforts. While certification methods can effectively leverage tight convex relaxations for …