Learning Complexity of Simulated Annealing
  Simulated annealing is an effective and general means of optimization. It is
in fact inspired by metallurgy, where the temperature of a material determines
its behavior in thermodynamics. Likewise, in simulated annealing, the actions
that the algorithm takes depend entirely on the value of a variable which
captures the notion of temperature. Typically, simulated annealing starts with
a high temperature, which makes the algorithm pretty unpredictable, and
gradually cools the temperature down to become more stable.
  A key component that plays a crucial role in the performance of simulated
annealing is the criteria under which the temperature changes namely, the
cooling schedule. Motivated by this, we study the following question in this
work: "Given enough samples to the instances of a specific class of
optimization problems, can we design optimal (or approximately optimal) cooling
schedules that minimize the runtime or maximize the success rate of the
algorithm on average when the underlying problem is drawn uniformly at random
from the same class?"
  We provide positive results both in terms of sample complexity and simulation
complexity. For sample complexity, we show that $\tilde O(\sqrt{m})$ samples
suffice to find an approximately optimal cooling schedule of length $m$. We
complement this result by giving a lower bound of $\tilde \Omega(m^{1/3})$ on
the sample complexity of any learning algorithm that provides an almost optimal
cooling schedule. These results are general and rely on no assumption. For
simulation complexity, however, we make additional assumptions to measure the
success rate of an algorithm. To this end, we introduce the monotone stationary
graph that models the performance of simulated annealing. Based on this model,
we present polynomial time algorithms with provable guarantees for the learning
problem.
