Closed-Loop Generative Selection: Convergence, Memory, and Noisy Oracles

Technical Summary: Closed-Loop Generative Selection

Problem Statement
Closed-loop generative selection has emerged as a primary methodology in computational drug discovery. In this workflow, a learned generative model proposes candidate molecules, a fitness oracle (e.g., docking or assay) scores them, and the best candidates are retained to retrain the model for the next round. Despite its practical utility, the method lacks a rigorous convergence theory. Classical evolutionary algorithm analysis relies on the Markov property of the population process; however, in generative selection, the model $G_t$ is retrained at every round based on the history of elite pools. This adaptation breaks the Markov property of the population sequence $(P_t)$, rendering standard analytical tools inapplicable. Furthermore, the field lacks a unified theory addressing the role of memory (how much past data informs the model), the impact of noisy oracles, and the true cost of the search measured in oracle evaluations rather than algorithmic rounds.

Methodology and Mathematical Framework
The authors develop a self-contained theory by reformulating the problem on an enlarged state space to recover a Markov structure.

1. Markov Formulation: Instead of analyzing the population $P_t$ alone, the authors define an augmented state $Z_t = (P_t, G_t)$ or a history process $H_t = (P_0, \dots, P_t)$. They prove that under deterministic update rules, these augmented processes are time-homogeneous Markov chains.
2. Elitism and Absorption: The algorithm employs an elitist selection rule (retaining the top-$N$ molecules), ensuring the elite fitness $f(P_t)$ is non-decreasing. This creates an absorbing structure where the target set of $\epsilon$-optimal molecules is an absorbing state.
3. Fitness-Level Method: The analysis decomposes the search into "sojourns" at discrete fitness levels. The expected hitting time is bounded by the sum of the expected times to escape each level. The escape probability at level $k$ depends on the generative kernel's ability to propose molecules strictly fitter than the current level.
4. Memory Models: The paper analyzes three regimes:
   • Static/Single-step: $G_t$ depends only on $P_t$.
   • Full-memory: $G_t$ depends on the entire history.
   • Finite $m$-step memory: $G_t$ depends on the last $m$ pools.
5. Noise Handling: The theory extends to noisy oracles by replacing single evaluations with replicated queries and robust estimators (e.g., median-of-means, sign tests) to certify fitness gaps under sub-Gaussian and heavy-tailed noise distributions.

Key Contributions and Results

• Convergence and Hitting-Time Bounds:
  The paper proves almost-sure convergence for any generative selection algorithm satisfying a uniform positivity condition (a floor of uniform exploration). It establishes a "Layered Hitting-Time Bound" where the expected number of rounds is bounded by the sum of inverse escape probabilities across fitness levels. This bound is sharper than standard geometric tail bounds as it accounts for the landscape structure.

• Memory Hierarchy and Monotone Learning:
  Under a "monotone-learning" condition (where conditioning on additional past data never decreases the probability of proposing a better molecule), the authors prove a memory hierarchy: deeper memory strictly improves (or at least does not hurt) the escape probabilities and reduces the expected hitting time. In this regime, full memory is optimal, and the benefit of memory exhibits diminishing returns, saturating exponentially.

• Non-Monotone Learning and Optimal Memory Depth:
  The paper identifies that monotone learning often fails in practice (e.g., when averaging noisy pools introduces staleness bias). In the absence of monotonicity, the authors derive a non-monotone exit-time theory. They define a "learning profile" $\rho_k(j)$ representing the escape probability as a function of the number of current-level pools in the window. The expected sojourn time is shown to be a U-shaped function of memory depth $m$. Consequently, there exists a finite optimal memory depth $m^*$ that balances the variance reduction of more data against the bias of stale data. This optimal depth corresponds to the first peak of the learning profile.

• Evaluation-Minimal Strategy:
  Recasting the theory in terms of oracle evaluations (the true bottleneck in drug design), the authors prove that sequential operation ($M=1$) minimizes the total number of evaluations. While larger batch sizes ($M > 1$) reduce the number of rounds, they waste evaluations on candidates that are scored even after a better candidate has already been found in the same batch. The optimal strategy is to propose one candidate at a time, potentially combined with memoization and early stopping.

• Noisy Oracles:
  For sub-Gaussian noise, the cost of certification inflates by a factor proportional to $\sigma^2/\Delta^2$, where $\Delta$ is the fitness gap. For heavy-tailed noise (where variance may be infinite), the sample mean is shown to be insufficient. The authors demonstrate that robust estimators (median-of-means) or distribution-free sign tests restore correctness, with query costs that degrade gracefully with the tail heaviness.

Significance and Claims
The paper claims to provide the first rigorous convergence and runtime analysis for closed-loop generative selection that accounts for adaptive learning kernels. Its significance lies in:

1. Resolving the Markov Break: By constructing an augmented state space, it bridges the gap between adaptive generative models and classical evolutionary algorithm theory.
2. Quantifying Memory: It moves beyond the heuristic "more data is better" to provide a precise bias-variance trade-off analysis, identifying conditions under which finite memory is optimal.
3. Resource Optimization: It establishes that for cost-constrained drug discovery, sequential evaluation ($M=1$) is theoretically optimal for minimizing oracle calls, challenging the common practice of large-batch parallel evaluation.
4. Robustness: It offers a framework for handling realistic, noisy experimental data, including heavy-tailed distributions common in biological assays, without sacrificing convergence guarantees.

The authors conclude that while the theory is abstract and relies on lower bounds for escape probabilities that depend on specific model implementations, it provides a foundational framework for analyzing and designing generative selection algorithms. They identify three open problems: quantifying escape probabilities for specific neural architectures, designing learners that are both non-monotone and composition-homogeneous to realize level-adaptive memory gains, and extending robust certification to continuous latent spaces and asymmetric noise.