Better Runtime Guarantees Via Stochastic Domination
Apart from few exceptions, the mathematical runtime analysis of evolutionary algorithms is mostly concerned with expected runtimes. In this work, we argue that stochastic domination is a notion that should be used more frequently in this area. Stochastic domination allows to formulate much more informative performance guarantees, it allows to decouple the algorithm analysis into the true algorithmic part of detecting a domination statement and the probability-theoretical part of deriving the desired probabilistic guarantees from this statement, and it helps finding simpler and more natural proofs. As particular results, we prove a fitness level theorem which shows that the runtime is dominated by a sum of independent geometric random variables, we prove the first tail bounds for several classic runtime problems, and we give a short and natural proof for Witt's result that the runtime of any $(\mu,p)$ mutation-based algorithm on any function with unique optimum is subdominated by the runtime of a variant of the \oea on the \onemax function. As side-products, we determine the fastest unbiased (1+1) algorithm for the \leadingones benchmark problem, both in the general case and when restricted to static mutation operators, and we prove a Chernoff-type tail bound for sums of independent coupon collector distributions.
Code (0)
등록된 구현이 없습니다.
Tasks
Evolutionary AlgorithmsSimilar Papers 제목 키워드 기반
Improved Runtime Guarantees for the SPEA2 Multi-Objective Optimizer
Together with the NSGA-II, the SPEA2 is one of the most widely used domination-based multi-objective evolutionary algorithms. For both algorithms, the known runtime guarantees are linear in the population size; for the N…
Almost sure convergence rates of stochastic gradient methods under gradient domination
Stochastic gradient methods are among the most important algorithms in training machine learning problems. While classical assumptions such as strong convexity allow a simple analysis they are rarely satisfied in applica…
Policy Gradient Methodsreinforcement-learningReinforcement LearningKrADagrad: Kronecker Approximation-Domination Gradient Preconditioned Stochastic Optimization
Second order stochastic optimizers allow parameter update step size and direction to adapt to loss curvature, but have traditionally required too much memory and compute for deep learning. Recently, Shampoo [Gupta et al.…
Stochastic OptimizationRisk-Aware MPC for Stochastic Systems with Runtime Temporal Logics
This paper concerns the risk-aware control of stochastic systems with temporal logic specifications dynamically assigned during runtime. Conventional risk-aware control typically assumes that all specifications are prede…
Model Predictive ControlMotion PlanningWithout-Replacement Sampling for Stochastic Gradient Methods: Convergence Results and Application to Distributed Optimization
Stochastic gradient methods for machine learning and optimization problems are usually analyzed assuming data points are sampled \emph{with} replacement. In practice, however, sampling \emph{without} replacement is very …
Distributed OptimizationLearning TheoryStochastic OptimizationTransductive Learning