Learning Complexity of Simulated Annealing
Learning Complexity of Simulated Annealing
复制标题
DOI：
--
复制
发表时间：
2020-03
期刊：
影响因子：
--
通讯作者：
Avrim Blum;Chen Dan;Saeed Seddighin
中科院分区：
文献类型：
--
作者：
Avrim Blum;Chen Dan;Saeed Seddighin
模拟退火算法是一种有效而通用的优化方法。它实际上受到冶金学的启发，材料的温度决定了其在热力学中的行为。同样，在模拟退火中，算法采取的行动完全取决于捕获温度概念的变量的值。通常，模拟退火从高温开始，这使得算法非常不可预测，并逐渐冷却温度以变得更加稳定。在模拟退火的性能中起关键作用的关键组件是温度变化的标准，即冷却时间表。受此启发，我们在这项工作中研究了以下问题："给定足够的样本到特定类别的优化问题的实例，我们是否可以设计最佳（或近似最佳）的冷却时间表，最小化运行时间或最大化平均算法的成功率，当底层问题是从同一类中随机均匀抽取时？"我们在样本复杂性和模拟复杂性方面都提供了积极的结果。对于样本的复杂性，我们证明了$\tilde O（\sqrt {m}）$样本足以找到长度为$m $的近似最优冷却时间表。我们补充这一结果，给出了一个下界$\tilde\Omega（m ^{1/3}）$的样本复杂性的任何学习算法，提供了一个几乎最佳的冷却时间表。这些结果是一般性的，不依赖于任何假设。然而，对于模拟的复杂性，我们做了额外的假设来衡量算法的成功率。为此，我们引入了模拟退火的性能模型的单调固定图。基于这个模型，我们提出了多项式时间算法的学习问题的可证明的保证。
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.