A Theoretical Framework for Zeroth-Order Budget Convex Optimization

This paper studies a natural generalization of the problem of minimizing a convex function f by querying its values sequentially. At each time-step t, the optimizer selects a query point X_t and invests a budget b_t (chosen by the environment) to obtain a fuzzy evaluation of f at X_t whose accuracy depends on the amount of budget invested in X_t across times. This setting is motivated by the minimization of objectives whose values can only be determined approximately through lengthy or expensive computations, where it is paramount to recycle past information. In the univariate case, we design ReSearch, an anytime parameter-free algorithm for which we prove near-optimal optimization-error guarantees. Then, we present two applications of our univariate analysis. First, we show how to use ReSearch for stochastic convex optimization, obtaining theoretical and empirical improvements on state-of-the-art benchmarks. Second, we handle the d-dimensional budget problem by combining ReSearch with a coordinate descent method, presenting theoretical guarantees and experiments.