Stochastic Localization Methods for Convex Discrete Optimization via Simulation

The authors greatly appreciate the comments and suggestions from the anonymous reviewers and editors, which all have significantly benefited this work. A preliminary version of the results has been published in the conference version Zhang et al. (2021) at the Conference on Neural Information Processing Systems 2021. Compared with the conference version, in the current work, the authors propose two novel algorithms for the one-dimensional convex discrete optimization via simulation problems. The authors prove that one of the algorithms, namely, the shrinking uniform sampling algorithm, is able to achieve the optimal information-theoretical lower bound up to a constant, which, to the authors’ knowledge, is the first known algorithm achieving such optimality. In addition, the construction of confidence intervals in other algorithms is refined, which is able to improve both the convergence guarantee and the empirical performance of the proposed algorithms. Moreover, the authors provide a more comprehensive set of numerical experiments to demonstrate the theoretical results and illustrate the usefulness of the proposed algorithms, especially on larger scale problems.