stat.MLJul 29, 2026

Expected Survival-Time Bounds for Robust Optimization Over Time under Isotropic Gaussian Dynamics

Authors: Pavel Novoa-Hernández

Organizations: Dept. Computer Engineering and Systems Universidad de La Laguna Spain

Abstract

Robust Optimization Over Time (ROOT) is a recent branch of evolutionary dynamic optimization that seeks solutions capable of remaining effective across multiple consecutive environments. Unlike the traditional track-the-moving-optimum (TMO) paradigm, which reoptimizes after every environmental change, ROOT explicitly values persistence. Although the field has grown considerably, most contributions remain algorithmic and empirical, leaving several fundamental properties poorly understood from a theoretical perspective. One such property is survival time, defined as the number of future environments in which a deployed solution continues to satisfy a prescribed quality threshold. While survival time is widely used as a measure of temporal robustness, little is known about how its expected value depends on environmental dynamics, deployment quality, or problem characteristics. This paper studies expected survival time for a fixed deployed solution under isotropic Gaussian environmental dynamics. Modeling survival as a discrete first-exit problem, we derive a rigorous lower bound and a computable multi-step upper bound. The analysis shows that expected survival scales as Θ(σ−2)Θ(σ^-{2}) in slowly varying environments and approaches its minimum value of one future change in high dimensions. A comprehensive Monte Carlo study validates the theoretical predictions, examines sensitivity to modeling assumptions and parameter uncertainty, and illustrates how the bounds can support deployment decisions after optimization. The resulting framework provides an analytical characterization of deployment lifetime and identifies when a required deployment horizon can be guaranteed, ruled out, or remains analytically unresolved.

Explore similar work

CardsList
Jun 11, 2026cs.NE

The (1 + 1)-EA in Dynamic Environments

We study the (1+1)(1 + 1)-EA in dynamic linear environments, where in every generation selection is performed with respect to a freshly sampled linear function with positive weights. We consider the Dynamic Binary Value problem, where each generation uses a uniformly random permutation of 1,2,4,…,2n−11,2,4,\dots,2^{n-1}, and a Uniform weight variant, where the weights are drawn independently from Unif(0,1)\mathrm{Unif}(0,1). Both of them have recently been integrated into the IOHprofiler platform and empirically studied. For both models we prove a sharp threshold in the mutation parameter χχ for mutation rate χ/nχ/n. Below the threshold, the expected optimisation time is O(nlog⁡n)\mathcal{O}(n\log n), whereas above it the runtime becomes 2Ω(n)2^{Ω(n)}. For the Dynamic Binary Value problem in the exponential regime, we also quantify at what distance from the optimum the optimisation process stagnates. We show that there is a second threshold: a distance that is efficiently reached, but reaching any smaller distance takes exponential time. This quantifies and proves previous empirical findings.
Georg Hasebe, Johannes Lengler, Raghu Raman Ravi
Low-Data RegimesRandomDynamic EnvironmentsEnvironment
AskPDF
Jul 15, 2026cs.NE

Asymptotical Analysis of the (1+(λ,λ)) GA Escape Time from Local Optima on Jump Functions

The paper develops the approach to the runtime analysis of evolutionary algorithms on the basis of limit theorems from probability theory. We consider the family of Jumpk_k benchmark functions, defined on the search space of binary strings of length nn, parametrized by the integer kk, which have a plateau of multiple local optima at the Hamming distance kk from a unique global optimum. In this work, we consider the genetic algorithm (1+(λ,λ))GA(1+(λ,λ)) GA from (Doerr, Doerr and Ebel, 2015) with tunable parameters of the mutation rate pp, crossover bias cc, and two intermediate population sizes λMλ_M and λCλ_C. We study the time it escapes from the plateau of local optima and reaches the global optimum in the case of Jumpk_k fitness function and tighten the upper bounds on the expected escape time, known from the work of Antipov, Doerr and Karavaev (2022). The obtained bounds also apply to a wider range of algorithmic parameters. The main result of this work applies to the case when k→∞k\to \infty as n→∞.n \to \infty. The case of finite kk is investigated quite simply and considered tangentially.
Anton V. Eremeev, Valentin A. Topchii
Genetic AlgorithmsAsymptoticsLarge Deviations TheoryOptimalRuntime
AskPDF
Apr 30, 2026math.OC

Sampler-Robust Optimization under Generative Models

Modern stochastic optimization pipelines increasingly rely on learned generative models to represent uncertainty, while downstream decisions are evaluated almost entirely through Monte Carlo scenarios. This shifts the operational object of uncertainty from an explicit probability law to the sampler induced by the learned generator. Reliability therefore depends on two errors: sampler misspecification and finite-simulation error. We propose Sampler-Robust Optimization (SRO), which optimizes decisions against the worst-case sampler induced by perturbing the learned generator. This sampler-first formulation aligns with simulation-based decision pipelines and admits a sharpness-aware interpretation: it favors decisions whose performance is stable under generator perturbations, rather than merely under the nominal sampler. Under a coverage assumption, we show that the empirical worst-case objective provides a high-probability upper certificate for the true population objective, with finite-simulation error partially absorbed by the robustification used to guard against sampler misspecification. The framework accommodates generative models with or without explicit densities and admits efficient minimax procedures. Portfolio-optimization experiments show that SRO produces more stable decisions and improves out-of-sample performance under distribution shift.
Ziwei Zhang, Jonathan Yu-Meng Li
Stochastic OptimizationMulti-Objective OptimizationPortfolio OptimizationGenerative ModelsDecisions
AskPDF