Efficient Multi-start Strategies for Local Search Algorithms.

Levente Kocsis, András GyörgyECML/PKDD 2009 · DOI · OpenReview

TL;DR

This paper introduces novel multi-start strategies for local search algorithms that dynamically allocate computational resources to multiple algorithm instances. These strategies, inspired by bandit problems and Lipschitz optimization, aim to efficiently escape local optima and find global optima with theoretical guarantees and practical improvements, often achieving near-logarithmic increases in function evaluations compared to theoretical quadratic bounds.

What Problem Does This Paper Address?

Local search algorithms are powerful tools for optimization, but they often get stuck in local optima, failing to find the true global optimum. A common workaround is to restart the algorithm multiple times. This paper tackles the challenge of making this multi-start approach more efficient by intelligently managing multiple instances of a local search algorithm. Instead of simply restarting, the authors propose strategies that dynamically decide which instances to allocate more computational resources to and when to introduce new ones, based on their estimated potential performance. This is crucial when evaluating the objective function is expensive, as it aims to minimize the total number of evaluations needed to achieve a good solution.

Methods

The core of the proposed solution lies in the METAMAX family of algorithms. These strategies are inspired by:

  • Multi-armed Bandit Problems: Each local search instance is treated like an "arm" of a bandit machine. The algorithm learns which "arm" (instance) is most promising by observing its performance.
  • Lipschitz Optimization with Unknown Constant: The strategies estimate the potential performance of each instance by assuming a convergence rate up to an unknown constant. This allows for an optimistic estimation of future performance.

The METAMAX algorithms (METAMAX(K) for a fixed number of instances, and METAMAX(∞) and METAMAX for an unbounded number of instances) work by:

  1. Initialization: Starting multiple instances of a local search algorithm.
  2. Dynamic Resource Allocation: In each round, they estimate the potential performance of each active instance using a function h that decays over time. They then select instances that appear most promising for a range of potential convergence rates.
  3. Exploration-Exploitation Balance: The strategies balance exploring new instances with exploiting promising ones, aiming to find the global optimum efficiently.
  4. Theoretical Analysis: The paper provides asymptotic bounds on the performance, proving that optimal instances are utilized frequently and that the total number of function evaluations is bounded, often with a logarithmic penalty.

Datasets

The paper evaluates its proposed strategies on:

  • Synthetic Function: A modified version of the Griewank function, used to demonstrate basic properties and performance.
  • Real-World Datasets:
    • UCI Machine Learning Repository:
      • Vehicle dataset: Used for tuning the parameters of a Multilayer Perceptron (MLP) classifier.
  • Letter dataset: Also used for tuning MLP parameters.
  • k-Means Clustering: Applied to a dataset from the UCI Machine Learning Repository (also used by Arthur & Vassilvitskii, 2007) to partition data points.

Key Insights and Ideas

  • Optimistic Performance Estimation: The core idea of estimating potential performance optimistically, even with unknown convergence rates, is key to effectively managing multiple search instances. This allows the algorithm to explore promising directions without being overly conservative.
  • Dynamic Resource Allocation is Crucial: Simply restarting is less efficient than dynamically allocating resources based on observed performance and estimated potential. The METAMAX strategies demonstrate this by prioritizing instances that show promise.
  • Theoretical Guarantees for Efficiency: The paper provides strong theoretical backing, showing that optimal instances are used frequently and that the overall cost (function evaluations) is significantly better than naive approaches, often achieving near-logarithmic overhead.
  • Practical Performance Outperforms Theory: While theoretical bounds suggest a quadratic increase in function evaluations, experiments show a much better logarithmic increase, indicating the practical effectiveness of the METAMAX strategies.
  • Explore-and-Exploit Can Be Pathological: The authors highlight that simple explore-and-exploit strategies can exhibit pathological behavior on certain functions, where their performance can degrade with increased iterations, a problem METAMAX seems to avoid.

Key Results

  • Theoretical Bounds: The paper proves that METAMAX strategies achieve performance comparable to a single optimal local search algorithm with at most a quadratic increase in function evaluations asymptotically.
  • Experimental Results:
    • Synthetic Function: METAMAX algorithms consistently converged fastest on the modified Griewank function.
  • Machine Learning Parameter Tuning: METAMAX demonstrated superior performance in tuning parameters for Multilayer Perceptrons on the vehicle and letter datasets, often finding the global optimum in fewer steps.
  • k-Means Clustering: METAMAX also outperformed a serial strategy for k-means clustering, especially with the k-means++ initialization.
  • Logarithmic Penalty Observed: In practice, the observed increase in function evaluations was logarithmic, significantly better than the theoretical quadratic bound.

Limitations and Future Work

  • Theoretical Bounds are Asymptotic: The theoretical guarantees are asymptotic, meaning they hold for a large number of rounds. The paper acknowledges that bounding thresholds for these results to hold with reasonable values is a direction for future work.
  • Parameter Selection for h: The paper notes that the theoretical results do not provide sufficient guidance on how to choose the parameter function h (or its time-varying version hr). A fast exponential decay is generally required, but the optimal choice is problem-dependent and not determined in advance.
  • Connection between gs and h: Further investigation into the connection between the convergence rate of local search algorithms (gs) and the exploration function (h) is suggested.
  • Finite Sample Analysis: The authors believe a finite sample analysis would be beneficial, as experiments suggest good performance even with a relatively small number of steps.
  • More General Scenarios: While the paper focuses on a simpler scenario for experiments, it acknowledges that METAMAX strategies could be applied to more general scenarios (e.g., varying parameters, using different local search algorithms) and that their behavior in these cases warrants further study.

Summary updated

Abstract

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.
BibTeX
@inproceedings{kocsis2009efficient,
  author = {Levente Kocsis and András György},
  title = {{Efficient Multi-start Strategies for Local Search Algorithms.}},
  booktitle = {ECML/PKDD},
  year = {2009},
  doi = {10.1613/jair.3313},
}
Figure