Efficient Multi-Start Strategies for Local Search Algorithms

By András György, Levente Kocsis. 2009

95 citations recorded by the source corpus.

Local search algorithms for global optimization often suffer from getting trapped in a local optimum. The common solution for this problem is to restart the algorithm when no progress is observed. Alternatively, one can start multiple instances of a local search algorithm, and allocate computational resources (in particular, processing time) to the instances depending on their behavior. Hence, a multi-start strategy has to decide (dynamically) when to allocate additional resources to a particular instance and when to start new instances. In this paper we propose a consistent multi-start strategy that assumes a convergence rate of the local search algorithm up to an unknown constant, and in every phase gives preference to those instances that could converge to the best value for a particular range of the constant. Combined with the local search algorithm SPSA (Simultaneous Perturbation Stochastic Approximation), the strategy performs remarkably well in practice, both on synthetic tasks and on tuning the parameters of learning algorithms.

Subfields: Artificial Intelligence, Computer Networks and Communications, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Management Science and Operations Research

Citations in the corpus

Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization (2016, methodology): “unlike prior configuration evaluation approaches (Domhan et al., 2015; Swersky et al., 2014; György and Kocsis, 2011; Agarwal et al., 2011; Sparks et al., 2015; Jamieson and Talwalkar, 2015).”
Population Based Training of Neural Networks (2017, background): “…order to reduce the number of optimisation steps required for each optimisation process and to better explore the space of promising hyperparameters (Gy¨orgy & Kocsis, 2011; Agarwal et al., 2011; Sabharwal et al., 2016; Swersky et al., 2013, 2014; Domhan et al., 2015; Klein et al., 2016; Snoek et…”
A System for Massively Parallel Hyperparameter Tuning (2018, methodology): “Previous methods like Gy¨orgy & Kocsis (2011); Agarwal et al. (2011); Sabharwal et al. (2016) provide theoretical guarantees under strong assumptions on the convergence behavior of intermediate losses.”
Hyperband: Bandit-Based Configuration Evaluation for Hyperparameter Optimization (2016, methodology): “Several works propose methods that make strong assumptions on the convergence behavior of training algorithms, providing theoretical performance guarantees under these assumptions (Gy¨orgy & Kocsis, 2011; Agarwal et al., 2011; Swersky et al., 2013; 2014; Domhan et al., 2015; Sabharwal et al., 2016).”
LEAPSANDBOUNDS: A Method for Approximately Optimal Algorithm Configuration (2018, background): “Our 1Related, but different problems are considered, e.g., by Luby et al. (1993); Adam (2001); Mnih et al. (2008); Audibert & Bubeck (2010); György & Kocsis (2011); Li et al. (2016). main technical contributions are as follows: We present an (arguably simpler) algorithm (LEAPSANDBOUNDS) that finds…”