论文标题
重新启动算法：有时有免费午餐
Restarting Algorithms: Sometimes there is Free Lunch
论文作者
论文摘要
在本概述文章中，我们将考虑算法的故意重新启动元素技术，以提高算法的性能，例如收敛率或近似保证。主要优点之一是重新启动是相对黑的框，不需要重新启动的基础算法或基本论点的任何（重大）更改，同时导致了潜在的显着改进，例如从跨线性到线性收敛速率。重新启动被广泛用于不同的字段，并已成为利用尚未直接合并到基本算法或参数中的其他信息的强大工具。我们将在各种设置中从连续优化，离散优化和下函数最大化，在各种设置中审查重新启动，从而取得了令人印象深刻的结果。
In this overview article we will consider the deliberate restarting of algorithms, a meta technique, in order to improve the algorithm's performance, e.g., convergence rates or approximation guarantees. One of the major advantages is that restarts are relatively black box, not requiring any (significant) changes to the base algorithm that is restarted or the underlying argument, while leading to potentially significant improvements, e.g., from sublinear to linear rates of convergence. Restarts are widely used in different fields and have become a powerful tool to leverage additional information that has not been directly incorporated in the base algorithm or argument. We will review restarts in various settings from continuous optimization, discrete optimization, and submodular function maximization where they have delivered impressive results.
