A New Minimax Theorem for Randomized Algorithms (Extended Abstract)

The celebrated minimax principle of Yao (1977) says that for any Boolean-valued function f with finite domain, there is a distribution µ over the domain of f such that computing f to error ǫ against inputs from µ is just as hard as computing f to error ǫ on worst-case inputs. Notably, however, the distribution µ depends on the target error level ǫ: the hard distribution which is tight for bounded error might be trivial to solve to small bias, and the hard distribution which is tight for a small bias level might be far from tight for bounded error levels.

In this work, we introduce a new type of minimax theorem which can provide a hard distribution µ that works for all bias levels at once. We show that this works for randomized query complexity, randomized communication complexity, some randomized circuit models, quantum query and communication complexities, approximate polynomial degree, and approximate logrank. We also prove an improved version of Impagliazzo's hardcore lemma.

Our proofs rely on two innovations over the classical approach of using Von Neumann's minimax theorem or linear programming duality. First, we use Sion's minimax theorem to prove a minimax theorem for ratios of bilinear functions representing the cost and score of algorithms.

Second, we introduce a new way to analyze low-bias randomized algorithms by viewing them as "forecasting algorithms" evaluated by a certain proper scoring rule. The expected score of the forecasting version of a randomized algorithm appears to be a more fine-grained way of analyzing the bias of the algorithm. We show that such expected scores have many elegant mathematical properties: for example, they can be amplified linearly instead of quadratically. We anticipate forecasting algorithms will find use in future work in which a fine-grained analysis of small-bias algorithms is required.

Yao's minimax principle [Yao77] is a central tool in the analysis of randomized algorithms in many different models of computation. In its most commonly-used form, it states that for every Booleanvalued function f with a finite domain, if R (c) denotes the set of randomized algorithms with worst-case cost at most c and ∆ denotes the set of distributions over the domain of f , then

with both probabilities being over the choice of x drawn from µ and the internal randomness of R. This identity implies that there exists a distribution µ for which any algorithm that computes f with bounded error over inputs drawn from µ must have cost at least R(f ), the cost of computing f to worst-case bounded error. But it does not say anything else about µ itself. Notably, I. The minimax principle does not guarantee that the resulting distribution µ must be balanced on the sets f -1 (0) and f -1 (1).

II. More generally, it does not rule out the possibility that f is very easy to compute by randomized algorithms that are only required to output the correct value with probability at least 1+γ 2 for some small bias measure γ > 0 over inputs drawn from the distribution µ.

A separate application of the minimax principle can be used to show that there is a distribution µ ′ for which all randomized algorithms computing f with bias γ over µ ′ have cost at least R 1-γ 2 (f ) (the cost of computing f to worst-case error (1 -γ)/2), but then there is no guarantee that randomized algorithms with bounded error over µ ′ must have cost anywhere close to R(f ).

Intuitively, it seems reasonable to expect that for every function f , there is a distribution µ for f that addresses issues I and II: a distribution that is balanced on f -1 (0) and f -1 (1), and which is at least slightly hard even to solve to a small bias level γ.