Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms

In stochastic zeroth-order optimization, a problem of practical relevance is understanding how to fully exploit the local geometry of the underlying objective function. We consider a fundamental setting in which the objective function is quadratic, and provide the first tight characterization of the optimal Hessiandependent sample complexity. Our contribution is twofold. First, from an information-theoretic point of view, we prove tight lower bounds on Hessiandependent complexities by introducing a concept called energy allocation, which captures the interaction between the searching algorithm and the geometry of objective functions. A matching upper bound is obtained by solving the optimal energy spectrum. Then, algorithmically, we show the existence of a Hessianindependent algorithm that universally achieves the asymptotic optimal sample complexities for all Hessian instances. The optimal sample complexities achieved by our algorithm remain valid for heavy-tailed noise distributions, which are enabled by a truncation method. As an initial step, we investigate the following natural questions: • For zeorth-order bandit optimization problems of quadratic functions of the form 1 2 (xx 0 ) ⊤ A(x -x 0 ), what is the optimal instance-dependent upper bound with respect to A? 37th Conference on Neural Information Processing Systems (NeurIPS 2023).