On the Probability of First Success in Differential Evolution: Hazard Identities and Tail Bounds
Dimitar Nedanovski, Svetoslav Nenov, Dimitar Pilev · 2026
Read On the Probability of First Success in Differential Evolution: Hazard Identities and Tail Bounds by Dimitar Nedanovski, Svetoslav Nenov, Dimitar Pilev (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-11499.txt.
Introduction
Dimitar Nedanovski, Svetoslav Nenov, and Dimitar Pilev time the first success in evolution. Their 2026 preprint studies Differential Evolution, a search heuristic. First-hitting times mark when a search first finds its target. The team frames them through conditional hazards.
Past analysis used Markov-chain kernels or drift arguments. The hazard frame skips both of those classic routes. Survival odds of a target set split into a product. Each factor is a conditional first-hit chance at one step. Hazard identities then give tail bounds for the wait. Those bounds tell how long success may take to arrive. Such results help set budgets for stochastic search runs.
Catalog record
| CREATOR | Dimitar Nedanovski, Svetoslav Nenov, Dimitar Pilev |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 71 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-11499
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the Probability of First Success in Differential Evolution: Hazard Identities and Tail Bounds Dimitar Nedanovski, Svetoslav Nenov, Dimitar Pilev Abstract We study first-hitting times in Differential Evolution (DE) through a conditional hazard framework. Instead of analyzing convergence via Markov-chain transition kernels or drift arguments, we express the survival probability of a measurable target set A A as a product of conditional first-hit probabilities (hazards) p t = ℙ ( E t ∣ ℱ t − 1 ) p_{t}=\mathbb{P}(E_{t}\mid\mathcal{F}_{t-1}) . This yields distribution-free identities for survival and explicit tail bounds whenever deterministic lower bounds on the hazard hold on the survival event. For the L-SHADE algorithm with current-to- p p best/1 mutation, we construct a checkable algorithmic witness event ℒ t \mathcal{L}_{t} under which the conditional hazard admits an explicit lower bound depending only on sampling rules, population size, and crossover statistics. This separates theoretical constants from empirical event frequencies and explains why worst-case constant-hazard bounds are typically conservative. We complement the theory with a Kaplan–Meier survival analysis on the CEC2017 benchmark suite. Across functions and budgets, we identify three distinct empirical regimes: (i) strongly clustered success, where hitting times concentrate in short bursts; (ii) approximately geometric tails, where a constant-hazard model is accurate; and (iii) intractable cases with no observed hits within the evaluation horizon. The results show that while constant-hazard bounds provide valid tail envelopes, the practical behavior of L-SHADE is governed by burst-like transitions rather than homogeneous per-generation success probabilities. Keywords Differential Evolution, First-Hitting Time, Conditional Hazard, Success Probability, Tail Bounds, Plateau Functions, Stochastic Optimization 1 Introduction Differential Evolution (DE) is a widely used population-based algorithm for continuous optimization. Adaptive variants such as L-SHADE have demonstrated strong empirical performance across diverse problem classes, yet theoretical understanding of their convergence behavior remains limited. A key difficulty is that these algorithms are inherently non-stationary: the population size, parameter distributions, and archive contents all evolve dynamically during optimization, making standard analytical tools difficult to apply. In this paper we study L-SHADE in terms of first-hitting times . Let A_{\varepsilon}=\{x\in[l,u]^{d}:f(x)\leq f^{\star}+\varepsilon\},\qquad l<u,\ \varepsilon>0 denote \varepsilon -sublevel set of the global minimum f^{\star} . Let \tau_{A} denote the first generation at which the population contains a point in A . When runs are terminated by a budget of B function evaluations (NFEVs), we also consider the evaluation-indexed hitting time \tau_{A}^{\mathrm{eval}} and the induced maximal generation n(B) determined by the (possibly time-varying) population size. Our starting point is an exact identity for the survival probability \mathbb{P}(\tau_{A}>n) in terms of conditional first-hit hazards . Let E_{t} denote the event that the first hit of A occurs at generation t , and let \mathcal{F}_{t-1} be the post-generation filtration encoding the full algorithmic history up to time t-1 . Define the conditional first-hit probability (hazard) p_{t}=\mathbb{P}(E_{t}\mid\mathcal{F}_{t-1}),\qquad t\geq 1, and the survival event H_{t-1}=\{\tau_{A}>t-1\} . Without any independence or stationarity assumptions, the survival function admits a product representation in terms of the survival-only hazards h_{t}=\mathbb{P}(E_{t}\mid H_{t-1}) . This yields distribution-free tail bounds whenever one can lower bound h_{t} on survival. To turn this viewpoint into a usable bound for L-SHADE, we construct a measurable witness event L_{t} (depending only on the state at time t-1 ) that certifies a favorable configuration for current-to- p best/1 with binomial crossover. On H_{t-1}\cap L_{t} we show that the conditional hazard admits a deterministic lower bound of the form p_{t}\geq a_{t}>0, where a_{t} is explicit and depends only on (i) discrete sampling rules (index choices and memory slot selection), (ii) population/archive sizes, and (iii) crossover tail probabilities. Crucially, this separates the one-step success probability into: 1. an explicit theoretical factor a_{t}>0 (typically small and conservative), and 2. an empirical frequency factor describing how often the witness configuration occurs along the run. Writing \gamma_{t}=\mathbb{P}(L_{t}\mid H_{t-1}), we obtain a survival-only hazard lower bound of the form h_{t}\;=\;\mathbb{P}(E_{t}\mid H_{t-1})\;\geq\;a_{t}\,\gamma_{t}, and consequently an explicit survival envelope \mathbb{P}(\tau_{A}>n)\;\leq\;\mathbb{P}(E_{0}^{c})\prod_{t=1}^{n}(1-a_{t}\gamma_{t})\;\leq\;\mathbb{P}(E_{0}^{c})\exp\!\Bigl(-\sum_{t=1}^{n}a_{t}\gamma_{t}\Bigr). This “constant \times frequency” decomposition makes precise why worst-case constant-hazard bounds can be valid yet pessimistic: even if a_{t} is tiny, the cumulative intensity \sum_{t\leq n}a_{t}\gamma_{t} can become large when L_{t} occurs frequently (often in short clusters). A three-step scheme for understanding success within a finite budget. The paper is organized around the following scheme, which directly targets success within a finite evaluation budget: 1. Empirical success-by-budget (good functions). For a fixed budget B NFEVs we study the success probability \mathbb{P}(\tau_{A_{\varepsilon}}^{\mathrm{eval}}\leq B) . Functions for which this probability is close to 1 are “good” at budget B in the practical sense that a finite NFEV budget suffices with high probability. 2. Witness frequency on survival. For each generation t we quantify (and, in principle, estimate from repeated runs) the survival-conditional frequency \gamma_{t}=\mathbb{P}(L_{t}\mid H_{t-1}) , i.e., how often L-SHADE enters a configuration where the one-step hazard admits an explicit certified lower bound. 3. Certification via the hazard product. Combining h_{t}\geq a_{t}\gamma_{t} with the exact survival product yields a certified tail bound for \mathbb{P}(\tau_{A_{\varepsilon}}>n) and, via n=n(B) , for \mathbb{P}(\tau_{A_{\varepsilon}}^{\mathrm{eval}}>B) . Thus, for “good” functions, high success probability within a finite budget is explained by the build-up of the cumulative witness intensity \sum_{t\leq n(B)}a_{t}\gamma_{t} . Empirical survival regimes. To connect the theory with practice we perform a Kaplan–Meier survival analysis on the CEC2017 benchmark suite in dimension d=10 under standard L-SHADE parameters and two evaluation budgets. The survival curves reveal three distinct empirical regimes: (i) strongly clustered success, where the survival function collapses in short bursts; (ii) approximately geometric tails, where a constant-hazard model is accurate; and (iii) intractable cases with no observed hits within the evaluation horizon. These results support the central message: mathematically valid constant-hazard envelopes are often conservative because L-SHADE’s practical success is governed by configuration-dependent transitions rather than homogeneous per-generation progress. Contributions. Our contributions are: (i) a hazard-based formulation of first-hitting times for DE yielding exact survival identities and distribution-free tail bounds; (ii) a concrete witness event L_{t} for L-SHADE/current-to- p best/1 that yields an explicit hazard floor on survival; and (iii) an empirical survival study (Kaplan–Meier and geometric envelopes) that characterizes clustered versus near-geometric success regimes and explains the observed conservatism of worst-case constant-hazard bounds. Supplementary Material. Supplementary Material is publically available at https://github.com/snenovgmailcom/lshade_hazard_project online and contains additional empirical analyses, including cluster geometry at hitting times and Kaplan–Meier validation of hazard bounds. 2 Success Events and Probability Space The constructions in this section introduce the notations. One may find complete standard constructions of this type for example in [ 16 , Section 2.1.4, Section 4.2] , [ 37 ] , [ 14 , Section 13.1] , [ 2 ] , [ 3 , Section 33] . Let [l,u]^{d} be the search cuboid, and let \left\{P^{(t)}\right\}_{t\geq 0} denote the population process produced by the DE variant under study, where P^{(t)}=\left\{{\boldsymbol{x}}^{(t)}_{1},\dots,{\boldsymbol{x}}^{(t)}_{\kappa_{t}}\right\}\subset[l,u]^{\kappa_{t}} and \kappa_{t} is the (possibly time-varying) population size. We model the algorithm on a filtered probability space \left(\Omega,\mathcal{F},\left\{\mathcal{F}_{t}\right\}_{t\geq 0},\mathbb{P}\right) , where \mathcal{F}_{t} represents the information available after completing generation t (including all random draws used in that generation and all derived state variables such as the population, archive, and parameter memories). A concrete probability product-space construction supporting full adaptivity is given in Appendix A . Let S_{t} denote the full algorithmic state after generation t (e.g. population, objective values, archive, parameter memories). We take the