mlsanityData to 14 Oct 2026

Probabilistic Tools for the Analysis of Randomized Optimization Heuristics

arXiv 1801.06733 ↗First posted 20 Jan 2018cs.DS cs.DM cs.NEcited by 24

Not on the map. Why?

Abstract (arXiv)

This chapter collects several probabilistic tools that proved to be useful in the analysis of randomized search heuristics. This includes classic material like Markov, Chebyshev and Chernoff inequalities, but also lesser known topics like stochastic domination and coupling or Chernoff bounds for geometrically distributed random variables and for negatively correlated random variables. Most of the results presented here have appeared previously, some, however, only in recent conference publications. While the focus is on collecting tools for the analysis of randomized search heuristics, many of these may be useful as well in the analysis of classic randomized algorithms or discrete random structures.

Key facts. Cited by 24 papers in the map (data through 14 Oct 2026). First posted on arXiv 20 Jan 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 5; 2022: 5; 2023: 7; 2024: 2; 2025: 1; 2026: 4.

24 papers.

Sort:

By area:

  1. 2021Mixability made efficient: Fast online multiclass logistic regressioncited by 12
  2. 2022Expected Worst Case Regret via Stochastic Sequential Coveringcited by 12
  3. 2021Lazy Parameter Tuning and Control: Choosing All Parameters Randomly From a Power-Law Distributioncited by 11
  4. 2022A Mathematical Runtime Analysis of the Non-dominated Sorting Genetic Algorithm III (NSGA-III)cited by 11
  5. 2021Mathematical Runtime Analysis for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II)cited by 8
  6. 2025Position: Scaling LLM Agents Requires Asymptotic Analysis with LLM Primitivescited by 7
  7. 2022A Theory of Unsupervised Translation Motivated by Understanding Animal Communicationcited by 6
  8. 2022Runtime Analysis for the NSGA-II: Proving, Quantifying, and Explaining the Inefficiency For Many Objectivescited by 6
  9. 2021Lower Bounds from Fitness Levels Made Easycited by 5
  10. 2021Choosing the Right Algorithm With Hints From Complexity Theorycited by 5
  11. 20233-Objective Pareto Optimization for Problems with Chance Constraintscited by 5
  12. 2023Runtime Analyses of Multi-Objective Evolutionary Algorithms in the Presence of Noisecited by 5
12 more
  1. 2023Polynomially Over-Parameterized Convolutional Neural Networks Contain Structured Strong Winning Lottery Ticketscited by 3
  2. 2022Approximation Guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II)cited by 2
  3. 2023How Well Does the Metropolis Algorithm Cope With Local Optima?cited by 2
  4. 2023Fourier Analysis Meets Runtime Analysis: Precise Runtimes on Plateauscited by 1
  5. 2023(1+1) Genetic Programming With Functionally Complete Instruction Sets Can Evolve Boolean Conjunctions and Disjunctions with Arbitrarily Small Errorcited by 1
  6. 2024The Runtime of Random Local Search on the Generalized Needle Problemcited by 1
  7. 2026When Switching Algorithms Helps: A Theoretical Study of Online Algorithm Selectioncited by 1
  8. 2023Convergence and scaling of Boolean-weight optimization for hardware reservoirscited by 0
  9. 2024A Block-Coordinate Descent EMO Algorithm: Theoretical and Empirical Analysiscited by 0
  10. 2026On the Probability of First Success in Differential Evolution: Hazard Identities and Tail Boundscited by 0
  11. 2026Parent Selection Mechanisms in Elitist Crossover-Based Algorithmscited by 0
  12. 2026A Fresh Look at Lamarckian Evolution and the Baldwin Effectcited by 0