标题： 模拟退火的学习复杂度 显示英文标题

标题： Learning Complexity of Simulated Annealing

摘要： 模拟退火是一种有效且通用的优化方法。 它实际上受到冶金学的启发，在冶金学中，材料的温度决定了其在热力学中的行为。 同样地，在模拟退火中，算法采取的动作完全取决于一个变量的值，这个变量捕捉了温度的概念。 通常，模拟退火从一个高温开始，这使得算法相当不可预测，然后逐渐降低温度以变得更为稳定。 在模拟退火性能中起关键作用的一个组成部分是温度变化的标准，即冷却计划。 受此启发，我们在本工作中研究以下问题：“给定特定类别的优化问题的足够样本，我们能否设计出最优（或近似最优）的冷却计划，使得当底层问题从同一类中均匀随机抽取时，算法的运行时间最小化或成功率最大化？” 我们在样本复杂性和模拟复杂性方面都提供了积极的结果。 在样本复杂性方面，我们证明$\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.