Ranking-Based Black-Box Complexity

Benjamin Doerr, Carola WinzenAlgorithmica 2014 · OpenReview

TL;DR

This paper introduces a new "ranking-based" black-box complexity model for randomized search heuristics, which better reflects how these algorithms actually work by only considering the relative quality of solutions. They show this model provides more realistic complexity estimates, making some problems appear harder (like binary-value functions) and others not harder (like OneMax functions) than in previous models.

What Problem Does This Paper Address?

Randomized search heuristics (like evolutionary algorithms) are widely used for optimization but are notoriously hard to analyze theoretically. Existing "black-box" models assume algorithms can access the exact objective values of solutions. However, many practical heuristics only use this information to rank solutions and compare their relative performance. This gap between theoretical models and practical algorithms leads to potentially unrealistic complexity estimates. The authors aim to bridge this gap by proposing a new complexity model that captures this "ranking-based" behavior.

Methods

The core contribution is the introduction of a ranking-based black-box model. In this model, algorithms can only query the rank of a solution relative to others already evaluated, not its absolute objective value. They then analyze two key function classes:

  • BINARYVALUE: A class of functions where the exact objective value is crucial for efficient optimization in standard models.
  • ONEMAX: A class of functions that are simpler and often used as benchmarks.

They develop specific algorithms and use theoretical tools like Chernoff bounds and Yao's minimax principle to derive upper and lower bounds for these classes within their new model. They also compare these bounds to existing "unrestricted" and "unbiased" black-box models.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis of function classes rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Ranking is Key: Many practical heuristics don't need exact fitness values; they just need to know which solutions are better than others. This paper formalizes that intuition.
  • More Realistic Complexity: The ranking-based model provides complexity estimates that better align with the observed performance of real-world algorithms.
  • BINARYVALUE Becomes Harder: For binary-value functions, the ranking restriction makes the problem significantly harder (from O(log n) to $\Theta(n)$), suggesting that exact values are indeed crucial for efficient optimization here.
  • ONEMAX Remains Tractable: For OneMax functions, the ranking restriction doesn't increase complexity, remaining at $\Theta(n/\log n)$, indicating that relative comparisons are sufficient for this problem.
  • Unbiased Operators Matter: The paper also considers "unbiased" variation operators, which are common in evolutionary computation, and analyzes complexity within this constraint as well.

Key Results

  • BINARYVALUE Complexity: The unrestricted ranking-based black-box complexity of BINARYVALUE functions is $\Theta(n)$, a significant increase from the $\mathcal{O}(\log n)$ complexity in previous models.
  • ONEMAX Complexity: The unary unbiased ranking-based black-box complexity of ONEMAX functions is $\Theta(n/\log n)$, matching the complexity of previous unrestricted models. For $k$-ary unbiased operators, it's $\mathcal{O}(n/\log k)$.
  • Algorithm Development: The paper presents novel algorithms for optimizing these function classes within the ranking-based framework, achieving the derived complexity bounds.

Limitations and Future Work

  • Model Equivalence: While the authors introduce ranking-based models, they note that proving the exact equivalence between their ranking-based model and a "monotone perturbation" model (where the oracle returns a monotonically transformed fitness value) is an open problem.
  • Algorithm Applicability: The ranking-based model captures many common heuristics but not all (e.g., simulated annealing).
  • Future Work: The paper suggests exploring other function classes and further investigating the relationship between different black-box complexity models. They also highlight that their results for BINARYVALUE show a significant difference in complexity between models that use exact values versus only ranks.

Summary updated

Abstract

Randomized search heuristics such as evolutionary algorithms, simulated annealing, and ant colony optimization are a broadly used class of general-purpose algorithms. Analyzing them via classical methods of theoretical computer science is a growing field. While several strong runtime analysis results have appeared in the last 20 years, a powerful complexity theory for such algorithms is yet to be developed. We enrich the existing notions of black-box complexity by the additional restriction that not the actual objective values, but only the relative quality of the previously evaluated solutions may be taken into account by the black-box algorithm. Many randomized search heuristics belong to this class of algorithms.We show that the new ranking-based model can give more realistic complexity estimates. The class of all binary-value functions has a black-box complexity of O(logn) in the previous black-box models, but has a ranking-based complexity of Θ(n).On the other hand, for the class of all OneMax functions, we present a ranking-based black-box algorithm that has a runtime of Θ(n/logn), which shows that the OneMax problem does not become harder with the additional ranking-basedness restriction.
BibTeX
@inproceedings{doerr2014ranking,
  author = {Benjamin Doerr and Carola Winzen},
  title = {{Ranking-Based Black-Box Complexity}},
  booktitle = {Algorithmica},
  year = {2014},
  url = {https://openreview.net/forum?id=DoYLQ0yeRzD},
}
Figure