Improved Fixed-Budget Results via Drift Analysis
Fixed-budget theory is concerned with computing or bounding the fitness value achievable by randomized search heuristics within a given budget of fitness function evaluations. Despite recent progress in fixed-budget theory, there is a lack of general tools to derive such results. We transfer drift theory, the key tool to derive expected optimization times, to the fixed-budged perspective. A first and easy-to-use statement concerned with iterating drift in so-called greed-admitting scenarios immediately translates into bounds on the expected function value. Afterwards, we consider a more general tool based on the well-known variable drift theorem. Applications of this technique to the LeadingOnes benchmark function yield statements that are more precise than the previous state of the art.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Learning under Distributional Drift: Prequential Reproducibility as an Intrinsic Statistical Resource
Statistical learning under distributional drift remains poorly characterized, especially in closed-loop settings where learning alters the data-generating law. We introduce an intrinsic drift budget $C_T$ that quantifies…
Optimize Wider, Not Deeper: Consensus Aggregation for Policy Optimization
Proximal policy optimization (PPO) approximates the trust region update using multiple epochs of clipped SGD. Each epoch may drift further from the natural gradient direction, creating path-dependent noise. To understand…
Continuous ControlWHERE to Generate Matters: Budget-Aware Synthetic Augmentation for Label Skewed Federated Learning
Label skew in federated learning (FL) causes client drift and degrades global accuracy. Synthetic data augmentation can reduce this imbalance; however, full class balancing requires substantial computation cost. We propo…
Federated LearningData AugmentationUnlimited Budget Analysis of Randomised Search Heuristics
Performance analysis of all kinds of randomised search heuristics is a rapidly growing and developing field. Run time and solution quality are two popular measures of the performance of these algorithms. The focus of thi…
Objective Matters: Fine-Tuning Objectives Shape Safety, Robustness, and Persona Drift
Fine-tuning LLMs on benign data can still degrade alignment and adversarial robustness, yet direct analysis of the role of fine-tuning objectives in shaping these safety outcomes remain limited. We present a controlled c…
Adversarial Robustness