Towards Efficient Black-box Optimization

Black-box optimization is a fundamental problem in various domains, from engineering to machine learning, from economics to robotics. In this problem, the goal is to minimize or maximize a target function without having direct access to its properties and gradients. In the literature, different techniques have been proposed to tackle such limitations. These algorithms rely solely on function evaluations to guide the optimization process. These techniques are generally called zeroth-order or derivative-free methods. Finite-difference methods are a class of zeroth-order algorithms that mimic first-order strategies by approximating the gradient of the target function. In particular, we can distinguish two classes of finite-difference methods: structured and unstructured. These classes differ in how gradient approximations are built. Empirical evidence suggests that structured methods yield more accurate gradient approximations compared to their unstructured counterparts. However, theoretical and empirical analyses of structured methods are relatively scarce, particularly in stochastic and non-smooth settings. In many practical scenarios, target functions are highly non-convex. In these settings, finite-difference methods may provide poor performance since they mimic gradient methods, and other classes of algorithms have been proposed. Bayesian Optimization is one of them. For functions defined on $\mathbb{R}^d$, Bayesian Optimization algorithms must rely on either a fixed discretization of the domain or on the solution of a non-convex auxiliary optimization problem at each evaluation, making this approach unfeasible for high-dimensional spaces. In this thesis, we focus on addressing the main limitations of these approaches. We provide the first non-smooth analysis of structured finite-difference methods and extend the smooth analysis to the stochastic setting. We tackle the scalability limitations of Bayesian Optimization methods by introducing and analyzing an algorithm that exploits adaptive discretization of the function domain. The focus then shifts from the analysis of zeroth-order methods to the development of various machine-learning applications, with specific emphasis on high-energy physics and biology. In the biological domain, this thesis addresses two key challenges: plankton monitoring and olfactory navigation. Plankton species identification poses a significant challenge due to the vast amount of image data generated by current acquisition devices. Manual annotation of such data is impractical. To tackle this issue, we propose an efficient unsupervised pipeline for clustering plankton images, offering a novel approach to species identification without the need of annotated data. In the context of olfactory navigation, our goal is to investigate the capability of animals to navigate solely based on odor signals. Recent studies have shown that turbulent odors, in conjunction with spatial perception, can effectively guide animals to their target. However, this navigation strategy requires animals to use a spatial map. In this thesis, we propose a model-free reinforcement learning algorithm that can learn to navigate without using a map of the space. In the field of high-energy physics, the thesis addresses two significant problems: the new physics learning problem and the data quality monitoring problem. We introduce an efficient anomaly detector to tackle both challenges. Unlike existing model-dependent approaches, which rely on specific types of anomalies and may avoid to detect unspecified discrepancies, our proposed method adopts a model-independent approach. Despite the diversity of these applications, they all share a common challenge: the black-box optimization problem of hyperparameter tuning. Examining these diverse applications, it becomes evident that zeroth-order methods are pervasive and essential across different domains.