A Rigorous Runtime Analysis for Quasi-Random Restarts and Decreasing Stepsize

Marc Schoenauer, Fabien Teytaud, Olivier TeytaudArtificial Evolution 2011 · DOI

TL;DR

This paper introduces a theoretically grounded restart strategy for multimodal optimization that significantly outperforms random restarts. By combining quasi-random initialization with a decreasing step-size, the proposed method achieves state-of-the-art performance while being computationally more efficient than existing approaches.

What Problem Does This Paper Address?

Multi-Modal Optimization (MMO) aims to find all global optima of a function, a challenging task in fields like engineering and machine learning. Many algorithms tackle this using "restart" strategies, where a local search is repeatedly initiated from different starting points. However, existing research has largely overlooked the crucial aspects of how these restarts are initialized and how the search parameters evolve. Specifically, there's a lack of rigorous analysis comparing different restart strategies and a need for methods that offer theoretical guarantees. This paper addresses this gap by proposing and analyzing a novel restart strategy that leverages quasi-random sequences for initialization and a decreasing step-size to ensure convergence.

Methods

The core of this paper is the development and analysis of a generic restart algorithm, dubbed QRDS (Quasi-Random Decreasing Stepsize). This algorithm can encapsulate any local optimization algorithm (referred to as ES). The key innovations are:

  • Quasi-Random (QR) Initialization: Instead of random starting points, QRDS uses sequences like Halton sequences with scrambling. These sequences are known to have better uniformity properties, which theoretically leads to faster coverage of the search space.
  • Decreasing Stepsize: The "step-size" parameter of the local optimizer is systematically decreased with each restart. This is crucial for ensuring that the algorithm eventually converges to all optima, as proven by the theoretical analysis.
  • Theoretical Guarantees: The paper provides rigorous mathematical proofs demonstrating that QRDS is consistent (i.e., it finds all optima) and that it offers a theoretical speed-up over random restarts, particularly in terms of the number of restarts required.
  • Optional "Murder" Operator: An additional "murder" operator is introduced, which kills a local search run if it gets too close to an already discovered optimum. This further enhances efficiency but introduces a parameter that requires tuning.

Datasets

The paper evaluates its proposed methods on two benchmark functions:

  • Multi-dimensional Sine Function: A function with an increasing number of optima (5, 50, 500, 1000) in varying dimensions (1 to 3). This function is used to test the scalability and efficiency of QRDS as the complexity of the search landscape increases.
  • Hump Function: A challenging 25-dimensional function with 50 optima, known for its difficulty and for being hard to overfit. This benchmark is used to compare QRDS with state-of-the-art methods from previous research.

Key Insights and Ideas

  • Quasi-randomness matters: The paper provides strong theoretical and experimental evidence that using quasi-random sequences for initialization significantly improves performance compared to random restarts. This is attributed to the better space-filling properties of QR sequences.
  • Decreasing step-size is key for consistency: The theoretical analysis highlights that a decreasing step-size is essential for guaranteeing that the algorithm will eventually find all optima, especially when combined with the locality property of the underlying local search.
  • Simplicity can be powerful: The proposed QRDS algorithm, despite its theoretical rigor and strong performance, is conceptually simple and can be applied to various local optimizers. This suggests that complex, specialized MMO algorithms might not always be necessary.
  • The "murder" operator is highly effective but parameter-dependent: While the murder operator dramatically speeds up convergence by avoiding redundant searches, its effectiveness relies on a parameter that needs careful tuning, which is a drawback.

Key Results

  • Theoretical Speed-up: The paper proves that QRDS requires fewer restarts than random restarts to find all optima, with the improvement being logarithmic in the number of optima.
  • Experimental Performance:
    • On the multi-dimensional sine function, QRDS consistently outperformed random restarts (RDS), with the advantage increasing as the number of optima grew. For 1000 optima, QRDS was up to 655% more efficient than RDS.
  • When the "murder" operator was included (QRDS+M), performance improved dramatically, achieving speed-ups of over 700% for 500 optima.
  • On the challenging 25-dimensional hump function, QRDS (with or without murder) found almost all 50 optima on average, outperforming previous methods that struggled to find even a single optimum.
  • QRDS achieved comparable or better results than modified clearing (a state-of-the-art method from [23]) while having a linear computational cost, whereas modified clearing had a higher cost.

Limitations and Future Work

  • Parameter Tuning: The "murder" operator introduces a parameter (distance threshold d) that is sensitive and requires tuning. The authors acknowledge this as a drawback, noting that similar parameters exist in other successful MMO algorithms.
  • Benchmark Specificity: The analysis and experiments, particularly on the hump function, rely on specific properties of the embedded (1+1)-ES and the nature of the test functions. The authors suggest that future work could explore other local optimizers and more diverse benchmark functions.
  • Parallelization: The paper briefly mentions that parallelization might be a scenario where clearing approaches could outperform QRDS, suggesting that future research could investigate parallel MMO strategies.
  • Generalization: While the theoretical framework is generic, the experimental validation is primarily on a specific (1+1)-ES. Extending the validation to other local search algorithms would be beneficial.

Summary updated

BibTeX
@inproceedings{schoenauer2011rigorous,
  author = {Marc Schoenauer and Fabien Teytaud and Olivier Teytaud},
  title = {{A Rigorous Runtime Analysis for Quasi-Random Restarts and Decreasing Stepsize}},
  booktitle = {Artificial Evolution},
  year = {2011},
  doi = {10.1007/978-3-642-35533-2\_4},
}
Figure