# Fourier Analysis Meets Runtime Analysis: Precise Runtimes on Plateaus

arXiv: https://arxiv.org/abs/2302.08021 · HTML: https://mlsanity.com/paper/2302.08021/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 106 references that are in the map.
- First posted on arXiv 16 Feb 2023.

## Builds on (most cited first, 24 of 24)

- [Fast Genetic Algorithms](https://mlsanity.com/paper/1703.03334/) (2017)
- [Probabilistic Tools for the Analysis of Randomized Optimization Heuristics](https://mlsanity.com/paper/1801.06733/) (2018)
- [Benchmarking Discrete Optimization Heuristics with IOHprofiler](https://mlsanity.com/paper/1912.09237/) (2019)
- [Better Runtime Guarantees Via Stochastic Domination](https://mlsanity.com/paper/1801.04487/) (2018)
- [Self-Adjusting Mutation Rates with Provably Optimal Success Rules](https://mlsanity.com/paper/1902.02588/) (2019)
- [The Runtime of the Compact Genetic Algorithm on Jump Functions](https://mlsanity.com/paper/1908.06527/) (2019)
- [Theoretical Analyses of Multiobjective Evolutionary Algorithms on Multimodal Objectives](https://mlsanity.com/paper/2012.07231/) (2020)
- [Fixed-Target Runtime Analysis](https://mlsanity.com/paper/2004.09613/) (2020)
- [Level-based Analysis of Genetic Algorithms and other Search Processes](https://mlsanity.com/paper/1407.7663/) (2014)
- [On the Limitations of the Univariate Marginal Distribution Algorithm to Deception and Where Bivariate EDAs might help](https://mlsanity.com/paper/1907.12438/) (2019)
- [Significance-based Estimation-of-Distribution Algorithms](https://mlsanity.com/paper/1807.03495/) (2018)
- [Level-Based Analysis of the Univariate Marginal Distribution Algorithm](https://mlsanity.com/paper/1807.10038/) (2018)
- [Analysing the Robustness of Evolutionary Algorithms to Noise: Refined Runtime Bounds and an Example Where Noise is Beneficial](https://mlsanity.com/paper/1812.00966/) (2018)
- [Lower Bounds from Fitness Levels Made Easy](https://mlsanity.com/paper/2104.03372/) (2021)
- [Choosing the Right Algorithm With Hints From Complexity Theory](https://mlsanity.com/paper/2109.06584/) (2021)
- [Precise Runtime Analysis for Plateau Functions](https://mlsanity.com/paper/1806.01331/) (2018)
- [The Query Complexity of a Permutation-Based Variant of Mastermind](https://mlsanity.com/paper/1812.08480/) (2018)
- [Multiplicative Up-Drift](https://mlsanity.com/paper/1904.05682/) (2019)
- [Lower Bounds for Non-Elitist Evolutionary Algorithms via Negative Multiplicative Drift](https://mlsanity.com/paper/2005.00853/) (2020)
- [Running Time Analysis of the (1+1)-EA for OneMax and LeadingOnes under Bit-wise Noise](https://mlsanity.com/paper/1711.00956/) (2017)
- [Exponential Upper Bounds for the Runtime of Randomized Search Heuristics](https://mlsanity.com/paper/2004.05733/) (2020)
- [Fast Re-Optimization via Structural Diversity](https://mlsanity.com/paper/1902.00304/) (2019)
- [On Non-Elitist Evolutionary Algorithms Optimizing Fitness Functions with a Plateau](https://mlsanity.com/paper/2004.09491/) (2020)
- [Improved Fixed-Budget Results via Drift Analysis](https://mlsanity.com/paper/2006.07019/) (2020)

## Built on by (most cited first, 1 of 1)

- [The Runtime of Random Local Search on the Generalized Needle Problem](https://mlsanity.com/paper/2403.08153/) (2024)

## Abstract (arXiv)

We propose a new method based on discrete Fourier analysis to analyze the time evolutionary algorithms spend on plateaus. This immediately gives a concise proof of the classic estimate of the expected runtime of the (1+1) evolutionary algorithm on the Needle problem due to Garnier, Kallel, and Schoenauer (1999). We also use this method to analyze the runtime of the (1+1) evolutionary algorithm on a new benchmark consisting of n/ℓ plateaus of effective size 2ℓ-1 which have to be optimized sequentially in a LeadingOnes fashion. Using our new method, we determine the precise expected runtime both for static and fitness-dependent mutation rates. We also determine the asymptotically optimal static and fitness-dependent mutation rates. For ℓ = o(n), the optimal static mutation rate is approximately 1.59/n. The optimal fitness dependent mutation rate, when the first k fitness-relevant bits have been found, is asymptotically 1/(k+1). These results, so far only proven for the single-instance problem LeadingOnes, thus hold for a much broader class of problems. We expect similar extensions to be true for other important results on LeadingOnes. We are also optimistic that our Fourier analysis approach can be applied to other plateau problems as well.