Probabilistic Tools for the Analysis of Randomized Optimization Heuristics

Abstract

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.

91 pages. Microscopic changes over the previous version

References in corpus (3)

• Probabilistic Tools for the Analysis of Randomized Optimization Heuristics
• Improved Runtime Bounds for the Univariate Marginal Distribution Algorithm via Anti-Concentration
• An Elementary Analysis of the Probability That a Binomial Random Variable Exceeds Its Expectation

Cited by in corpus (46)

• Probabilistic Tools for the Analysis of Randomized Optimization Heuristics
• Better Runtime Guarantees Via Stochastic Domination
• Runtime Analysis for the NSGA-II: Proving, Quantifying, and Explaining the Inefficiency For Many Objectives
• Does Comma Selection Help To Cope With Local Optima
• A Mathematical Runtime Analysis of the Non-dominated Sorting Genetic Algorithm III (NSGA-III)
• The Runtime of the Compact Genetic Algorithm on Jump Functions
• Theoretical Analyses of Multiobjective Evolutionary Algorithms on Multimodal Objectives
• Working Principles of Binary Differential Evolution
• A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching
• Multiplicative Up-Drift
• Stagnation Detection with Randomized Local Search
• A Simplified Run Time Analysis of the Univariate Marginal Distribution Algorithm on LeadingOnes
• Lower Bounds from Fitness Levels Made Easy
• A Rigorous Runtime Analysis of the $(1+(\lambda ,\lambda ))$ GA on Jump Functions
• Analysis of Evolutionary Algorithms on Fitness Function with Time-linkage Property
• Exponential Slowdown for Larger Populations: The $(\mu +1)$-EA on Monotone Functions
• Runtime Analysis of Probabilistic Crowding and Restricted Tournament Selection for Bimodal Optimisation
• Near-Tight Runtime Guarantees for Many-Objective Evolutionary Algorithms
• ITSO: A novel Inverse Transform Sampling-based Optimization algorithm for stochastic search
• Runtime Analysis of Restricted Tournament Selection for Bimodal Optimisation
• How Well Does the Metropolis Algorithm Cope With Local Optima?
• First Steps Towards a Runtime Analysis When Starting With a Good Solution
• Local Fast Rerouting with Low Congestion: A Randomized Approach
• Runtime Analysis of Single- and Multi-Objective Evolutionary Algorithms for Chance Constrained Optimization Problems with Normally Distributed Random Variables
• Bivariate Estimation-of-Distribution Algorithms Can Find an Exponential Number of Optima
• Phase Transition of a Non-Linear Opinion Dynamics with Noisy Interactions
• Data-Dependent Coresets for Compressing Neural Networks with Applications to Generalization Bounds
• Simple Genetic Operators are Universal Approximators of Probability Distributions (and other Advantages of Expressive Encodings)
• Runtime Analysis of Evolutionary Algorithms via Symmetry Arguments
• Evolutionary Algorithms for the Chance-Constrained Knapsack Problem
• Evolutionary Algorithms with Self-adjusting Asymmetric Mutation
• Fourier Analysis Meets Runtime Analysis: Precise Runtimes on Plateaus
• A Flexible Evolutionary Algorithm With Dynamic Mutation Rate Archive
• Asymmetric list sizes in bipartite graphs
• On Negative Dependence Properties of Latin Hypercube Samples and Scrambled Nets
• Extremal bipartite independence number and balanced coloring
• Specific Single- and Multi-Objective Evolutionary Algorithms for the Chance-Constrained Knapsack Problem
• Network Coding with Myopic Adversaries
• Mixability made efficient: Fast online multiclass logistic regression
• A Tight Runtime Analysis for the $(\mu +\lambda )$ EA
• Tail Probabilities for Randomized Program Runtimes via Martingales for Higher Moments
• Polynomially Over-Parameterized Convolutional Neural Networks Contain Structured Strong Winning Lottery Tickets
• Cardinality constrained submodular maximization for random streams
• Subspace exploration: Bounds on Projected Frequency Estimation
• Recommendation on a Budget: Column Space Recovery from Partially Observed Entries with Random or Active Sampling
• Capacity and Stability Regions for Layered Packet Erasure Broadcast Channels with Feedback