Optimally Stopped Optimization

We combine the fields of heuristic optimization and optimal stopping. We propose a strategy for benchmarking randomized optimization algorithms that minimizes the expected total cost for obtaining a good solution with an optimal number of calls to the solver. To do so, rather than letting the objective function alone define a cost to be minimized, we introduce a further cost-per-call of the algorithm. We show that this problem can be formulated using optimal stopping theory. The expected cost is a flexible figure of merit for benchmarking probabilistic solvers that can be computed when the optimal solution is not known and that avoids the biases and arbitrariness that affect other measures. The optimal stopping formulation of benchmarking directly leads to a real-time optimal-utilization strategy for probabilistic optimizers with practical impact. We apply our formulation to benchmark simulated annealing on a class of maximum-2-satisfiability (MAX2SAT) problems. We also compare the performance of a D-Wave 2X quantum annealer to the Hamze-Freitas-Selby (HFS) solver, a specialized classical heuristic algorithm designed for low-tree-width graphs. On a set of frustrated-loop instances with planted solutions defined on up to $N=1098$ variables, the D-Wave device is 2 orders of magnitude faster than the HFS solver, and, modulo known caveats related to suboptimal annealing times, exhibits identical scaling with problem size.

Figure 1

(a) Empirical quality functions (energy histograms) obtained running simulated annealing (SA) $10^5$ times on an instance of the optimization problem (16) with $N=1000$ variables. As expected, increasing the number of spin updates per run pushes the energy histogram towards lower-energy values. (b) Optimal total cost $C_c^{*}$ computed from the empirical energy distributions $\mathcal{P}$ of Fig. 1, after subtracting the ground-state energy $E_0$ for the given problem instance. The lower envelope gives the optimal number of spin updates per run $n_{\mathrm{SF}}^{*}$ as a function of $c$. Error bars are computed via bootstrapping. The red parts correspond to values of the optimal total cost that fall into the lower tail (defined as the 0.1th percentile) of the energy distributions. Note that large errors due to the undersampling of the lower tail do not imply large errors in the large-$c$ region.

Figure 2

(a) Optimal cost $C_c^{*}$ (blue), optimal energy $E_c^{*}$ (red), and optimal computational cost $T_c^{*}$ (yellow) computed by running SA with a fixed (solid lines) and optimized (dashed lines) number of spin updates (corresponding to the lower envelope of $C_c^{*}$ as described in Fig. 1). (b) Trade-off between optimal stopping time $n_c^{*}{n}_{\mathrm{SF}}$ (with optimized $n_{\mathrm{SF}}$) and solution quality $E_c^{*}$. The color code shows a monotonic inverse dependence of the stopping time on the unit cost $c$. Overlapping dots corresponding to very small $c$ (dark red colors) effectively have $E_c^{*}=E_0$; their common value on the vertical axis is the optimal time to solution. Data shown here correspond to the same representative instance as in Fig. 1.

Figure 3

(a) Optimal total cost $C_c^{*}$ for the four different problem sizes considered. Each point in the plot is the mean optimal total cost of the sample of 100 instances. Error bars (small in the figure) are the standard deviation of the mean optimal total cost. (b) Trade-off between mean stopping time $n_c^{*}{n}_{\mathrm{SF}}$ and solution quality $E_c^{*}$ averaged over the 100-instance sample. The color code gives the $c$ value. The colored streaks are guides to the eye connecting dots with the same color (same value of $c$). The four curves are ordered by problem size with $N=1000$ at the top. (c) Scaling of the optimal total cost $C_c^{*}$ relative to the global optimum $E_0$. At fixed problem size, the optimal total cost $C_c^{*}$ grows relative to $E_0$ as a function of the cost $c$. This is a necessary price to pay to keep the computational cost at the optimal level. (d) The red horizontal line is $C_c^{*}=E_1$. Regression fits reveal a region of quadratic scaling (above the line) and a region of exponential scaling (below the line). Fit parameters are given in the legend.

Figure 4

(a) Optimal number of spin updates $n_{\mathrm{SF}}$ per SA run, as a function of the unit cost (per spin update) $c$. As expected, this number grows with both decreasing $c$ and increasing problem size $N$. The figure suggests a subpolynomial scaling with $c$. (b) Optimal number of spin updates $n_{\mathrm{SF}}$ per SA run as a function of the problem size $N$. While this number is expected to grow when the computational cost is negligible (small $c$, warm colors), it is seen to saturate for intermediate and large values of $c$ (cold colors).

Figure 5

(a) Optimal cost for HFS (blue) and DW2X (red) averaged over 100 instances with planted solutions defined on the full Chimera graph. (b) Scaling of the optimal total cost for HFS (blue) and DW2X (red) as a function of the problem size for $c={10}^{-6}$ (solid lines below the red horizontal line) and $c=10^1$ (dashed lines above the horizontal line). The red horizontal line $C_c^{*}=E_1$ separates the regions of exponential (below the line) and linear (above the line) scaling. Note that DW2X and HFS have identical exponential scaling, but the DW2X prefactor is 2.2 orders of magnitude smaller.

Figure 6

Ideal (thin lines) and empirical (thick lines) optimal total cost for a representative instance on $N=1000$ variables and for different values of the number of spin updates $n_{\mathrm{SF}}$. The empirical optimal total costs are computed for the burn-in regime with (a) the maximum-likelihood fit method and (b) the Bayesian method. For the class of problems studied, the prior knowledge obtained by knowing the behavior of other instances in the same family is good enough to make the Bayesian method almost exact in the large- and intermediate-$c$ regions.

Figure 7

(a) Optimal cost $C_c^{*}$ for the same instance as in Fig. 1 computed running SA with $5\times 10^6$ spin updates and different parallelization strategies. The black dashed line is the optimal stopping step $n_{c/100}^{*}$ corresponding to perfect parallelization. Embarrassing parallelization is notably worse than perfect parallelization when $n_{c/100}^{*}<100$. (b) Stopping step $n_c^{*}$ computed after optimizing the number of spin updates and averaged over the 100 instances of each size $N$ indicated in the legend. According to the discussion in the main text, large values of $n_c^{*}$ allow for efficient embarrassing parallelization.

Figure 8

Hardware connectivity of the DW2X device installed at the University of Southern California. Red circles represent usable qubits, while white circles represent the 54 deactivated qubits. Black lines represent all the available couplings between active qubits.