AQC 2016 - An Optimal Stopping Approach for Benchmarking Probabilistic Optimizers

A Google TechTalk, June 27, 2016, presented by Walter Vinci (USC) ABSTRACT: We propose a strategy for benchmarking probabilistic optimizers based on an optimal stopping approach. We seek to optimize both the objective function and the number of calls to the solver. A crucial advantage of the figure of merit we propose is that it can be defined without knowledge of the global minimum. This allows for benchmarking hard optimization problems when it is not possible to use the time-to-solution metric. It can also be seen as a generalization of time-to-target approaches which avoids the introduction of possible biases due the choice of the target. We present our ideas by performing benchmarking experiments using both classical optimization algorithms and a DW2X quantum optimizer. Daniel Lidar, University of Southern California Presented at the Adiabatic Quantum Computing Conference, June 26-29, 2016, at Google's Los Angeles office.