Evaluation Dependency and Parallelism

The deepest dividing line between parameter-search methods is not how they pick points but whether one evaluation depends on another's result. That single property — the evaluation dependency structure — decides how well a method parallelizes, how reproducible it is, and how its wall-clock time scales. [L]

Two dependency structures

Open-loop: independent evaluations

In grid and random search the entire set of trial points is determined before any evaluation runs. No point's evaluation needs any other point's result. Such a workload is embarrassingly parallel: little or no communication is needed between tasks, so it splits across as many workers as are available. [L]

flowchart LR
  ENUM["Enumerate all trial points"] --> E1["Evaluate point 1"]
  ENUM --> E2["Evaluate point 2"]
  ENUM --> EN["Evaluate point N"]
  E1 --> COL["Collect results"]
  E2 --> COL
  EN --> COL

With enough workers the wall-clock time approaches the cost of a single evaluation, and the result is independent of completion order — so it reproduces exactly regardless of scheduling. [L]

Closed-loop: dependent evaluations

Every adaptive method — Bayesian optimization, evolutionary algorithms, CMA-ES — chooses its next trial(s) from results already seen. That creates a data dependency from each step to the next: a chain that cannot be collapsed by adding workers. [L]

flowchart LR
  INIT["Initialize batch"] --> EVAL["Evaluate batch"]
  EVAL --> UPD["Update model or breed"]
  UPD --> CONV{"Converged?"}
  CONV -->|no| EVAL
  CONV -->|yes| BEST["Return best"]

Parallelism is possible only within a batch or generation; between generations there is a synchronization barrier — every evaluation of a generation must finish before the next can be proposed. [L]

Why the structure bounds speedup

The sequential fraction of a computation caps how much parallel hardware can help: Amdahl's law states that the speedup of a program is limited by the part that cannot be parallelized — even with infinitely many workers, a job that is 1% sequential can be sped up at most 100-fold. [L] An open-loop search has a near-zero sequential fraction (only the final collection step). A closed-loop search has an irreducible sequential fraction set by the number of generations: with g sequential generations, wall-clock time is at least g times the cost of one batch, no matter how wide each batch is. [L]

Property	Open-loop (grid / random)	Closed-loop (adaptive)
Inter-trial dependency	none	each step depends on prior results
Parallelism	embarrassingly parallel	within a batch only, barriers between
Wall-clock floor	one evaluation	generations times one batch
Reproducibility	order-independent	needs fixed seed and evaluation order
Sample efficiency	lower	higher

Reproducibility note

Independent evaluations reproduce regardless of the order in which workers finish them. A dependent search reproduces only if both the random seed and the order of evaluation are pinned, because a different order changes which results inform the next proposal. [L] This is why deterministic adaptive search takes more care than deterministic open-loop search.

Hybrids

Population-based adaptive methods are batch-parallel within a generation, sequential across generations — they recover much of the parallel throughput of open-loop search while keeping the sample efficiency of adaptivity, trading a fixed number of barriers for it. [C]

Claim legend

[L] law / exact — a definition, identity, or theorem that does not vary.
[C] convention — a practitioner rule of thumb that varies by context.

References

Embarrassingly parallel. Wikipedia. https://en.wikipedia.org/wiki/Embarrassingly_parallel
Amdahl's law. Wikipedia. https://en.wikipedia.org/wiki/Amdahl%27s_law
Bayesian optimization. Wikipedia. https://en.wikipedia.org/wiki/Bayesian_optimization
Genetic algorithm. Wikipedia. https://en.wikipedia.org/wiki/Genetic_algorithm

Home

Backtesting Engine Architecture

Strategy Analysis & Validation