  We propose a multistart algorithm to identify all local minima of a
constrained, nonconvex stochastic optimization problem. The algorithm uniformly
samples points in the domain and then starts a local stochastic optimization
run from any point that is the "probabilistically best" point in its
neighborhood. Under certain conditions, our algorithm is shown to
asymptotically identify all local optima with high probability; this holds even
though our algorithm is shown to almost surely start only finitely many local
stochastic optimization runs. We demonstrate the performance of an
implementation of our algorithm on nonconvex stochastic optimization problems,
including identifying optimal variational parameters for the quantum
approximate optimization algorithm.
