A framework for co-optimization algorithm performance and its application to worst-case optimization

Traditional black-box optimization searches a set of potential solutions for those optimizing the value of a function whose analytical or algebraic form is unknown or inexistent, but whose value can be queried for any input. Co-optimization is a generalization of this setting, in which fully evaluating a potential solution may require querying some function more than once, typically a very large number of times. When that's the case, co-optimization poses unique difficulties to designing and assessing algorithms. A generally-applicable approach is to judge co-optimization algorithm performance via an aggregate over all possible functions in the problem domain. We establish formal definitions of such aggregate performance and then investigate the following questions concerning algorithm design: 1) are some algorithms strictly better than others? i.e. is there “free lunch”? 2) do optimal algorithms exist? and 3) if so, are they practical? We formally define free lunch and aggregate optimality of co-optimization algorithms and derive generic conditions for their existence. We review and explain prior (no) free lunch results from the perspective of these conditions; we also show how this framework can be used to bridge several fields of research, by allowing formalization of their various problems and views on performance. We then apply and extend the generic results in a context involving a particular type of co-optimization called worst-case optimization. In this context we show that there exist algorithms that are aggregately-optimal for any budget (allowed number of function calls) and any starting point (set of previously uncovered function call outcomes), and also non-trivially strictly optimal for many budgets and starting points; moreover, we formalize the operation of such optimal algorithms and show that for certain domains, budgets and starting points this operation is equivalent to a simple procedure with tractable implementation-a first-of-its-kind result for co-optimization.