The Unrestricted Black-Box Complexity of Jump Functions

Area of Science:

• Computer Science
• Algorithm Analysis
• Computational Complexity

Background:

• Black-box optimization problems are common in machine learning and operations research.
• Understanding the inherent difficulty (complexity) of these problems is crucial for algorithm design.

Purpose of the Study:

• To analyze the unrestricted black-box complexity of Jump function classes.
• To establish tight upper and lower bounds for different jump sizes.

Main Methods:

• Development of three algorithms for small, medium, and extreme jump sizes to determine upper bounds.
• Proving a novel matrix lower bound theorem to improve upon classic information theory bounds.
• Applying the theorem to derive lower bounds for Jump functions.

Main Results:

• Established upper bounds using new algorithms for various jump sizes.
• Derived lower bounds using the matrix lower bound theorem, closely matching the upper bounds.
• Demonstrated that for extreme jump functions, algorithms gain limited insight in initial evaluations.

Conclusions:

• The black-box complexity for extreme jump functions is determined to be [Formula: see text].
• The developed matrix lower bound theorem offers a more powerful tool for complexity analysis than traditional methods.