Accelerating Evolutionary Strategy via Rao-Blackwellizing Realization of Uncertain Input

Noisy evolution strategies under fixed evaluation budgets face a depth-fidelity trade-off: spending evaluations to denoise intra-generation rankings reduces the number of distribution updates the optimizer can execute. We argue for depth over fidelity and propose probabilistic elite membership (PEM), which replaces hard rank-based weights in evolution strategies with conditional expected rank weights that integrate over ranking uncertainty. PEM preserves the conditional mean update while reducing conditional update dispersion, a Rao-Blackwellization of the noisy rank-based step. We instantiate PEM via residual bootstrapping (RB-PEM) with capped per-generation overhead, complemented by an adaptive probe-and-switch mechanism for low-noise regimes. Across the COCO bbob-noisy suite and external tasks including RL policy search and hyperparameter optimization, RB-PEM achieves consistent gains in high-misranking, budget-constrained settings.

We consider the optimization of the Optimized Certainty Equivalent (OCE) risk, with applications including portfolio optimization in finance, and uncertainty quantification, classification, and regression in machine learning. Our contributions cover popular special cases of OCE, such as entropic risk, mean-variance risk, and smooth variants of Conditional Value-at-Risk. Our treatment sets out the conditions that facilitate the extension of OCE to unbounded r.v.s.. We provide a useful characterization of OCE that links OCE to utility-based shortfall risk (UBSR). Our characterization enables us to form an OCE estimator from the classic sample-average approximation (SAA) of UBSR. We derive mean-squared error (MSE) bounds for our proposed OCE estimator. For OCE optimization, we first derive an expression for the OCE gradient using the characterization linking OCE to UBSR. This expression serves as the basis for a gradient estimator for the OCE. We derive non-asymptotic bounds on the MSE for the proposed OCE gradient estimator. We incorporate the aforementioned gradient estimator into a stochastic gradient (SG) algorithm to optimize OCE and quantify its convergence rate using non-asymptotic bounds that we derive. Finally, we present three experiments that use our OCE optimization algorithm to solve portfolio optimization and uncertainty quantification problems.

Real-world optimization problems often involve black-box functions and uncertainties in their evaluation, widely referred to as noisy optimization problems (NOPs). Evolutionary algorithms (EA), including Evolutionary Strategies (ES) and genetic algorithms (GA) have been commonly adopted to solve these problems in the contemporary literature. An ongoing challenge is the computational expense involved, given the number of evaluations required for good fitness estimation and ranking. Two fundamental methods commonly used for fitness estimation for NOPs are implicit averaging and explicit averaging. Explicit averaging uses resampling of solutions to improve the estimates, while implicit averaging typically uses a large population size with low resampling. Implicit averaging has been shown to have theoretical advantages for certain cases, which has motivated some recent approaches to use them. However, a recent study demonstrated that its performance is highly dependent on certain assumptions about the function, such as steepness and constant noise level, which may not apply for majority of the real world problems. Moreover, most existing algorithms have only considered homoscedastic noise, where the amplitude of variation is uniform across the entire search space, as opposed to more generic case of heteroscedastic noise. To address these issues, we introduce a set of heteroscedastic test problems and propose a novel confidence ranking method that employs a computationally efficient explicit averaging strategy with sampling budget adaptation. It is implemented within the Covariance Matrix Adaptation ES (CMA-ES) and GA frameworks to demonstrate its effectiveness and versatility. The resulting algorithm is evaluated on a range of problems with both homoscedastic and heteroscedastic noise, and it demonstrates superior performance compared to state-of-the-art approaches.