Yao's principle

In computational complexity theory, Yao's principle (also called Yao's minimax principle or Yao's lemma) relates the performance of randomized algorithms to deterministic (non-random) algorithms. It states that, for certain classes of algorithms, and certain measures of the performance of the algorithms, the following two quantities are equal:

The optimal performance that can be obtained by a deterministic algorithm on a random input, for a probability distribution on inputs chosen to be as hard as possible and for an algorithm chosen to work as well as possible against that distribution
The optimal performance that can be obtained by a random algorithm on a deterministic input, for an algorithm chosen to have the best performance on its worst case inputs, and the worst case input to the algorithm

Yao's principle is often used to prove limitations on the performance of randomized algorithms, by finding a probability distribution on inputs that is difficult for deterministic algorithms, and inferring that randomized algorithms have the same limitation on their worst case performance.

This principle is named after Andrew Yao, who first proposed it in a 1977 paper.^[1] It is closely related to the minimax theorem in the theory of zero-sum games, and to the duality theory of linear programs.

Formulation

Consider any cost or performance measure of an algorithm that can be expressed as an expected value, over a distribution of random inputs to the algorithm or of random behaviors of the algorithm, of some outcome. For instance, the expected time of an algorithm is the expected value of the time taken by a single run of the algorithm. Consider, also, a class ${\mathcal {A}}$ of deterministic algorithms for which the number of distinct behaviors that are possible, for inputs of a given size, is finite, such as the decision tree model, and in which a randomized algorithm may be interpreted as generating an arbitrary probability distribution over these same potential behaviors. Let ${\mathcal {R}}$ be the class of randomized algorithms, defined in this way. Let ${\mathcal {X}}_{n}$ denote, for each input size $n$ , a finite set of inputs of size $n$ , and let $c(A,x)$ measure the cost or performance of algorithm $A$ on input $x$ . Let ${\mathcal {D}}_{n}$ denote the class of probability distributions on ${\mathcal {X}}_{n}$ . Then, Yao's principle states that:

$\max _{D\in {\mathcal {D}}_{n}}\min _{A\in {\mathcal {A}}}\mathbb {E} _{x\sim D}[c(A,x)]=\min _{R\in {\mathcal {R}}}\max _{x\in {\mathcal {X}}_{n}}\mathbb {E} [c(R,x)].$

Here, finiteness of the class of algorithms and inputs (for a fixed input size) allows ${\mathcal {D}}_{n}$ and ${\mathcal {R}}$ to be interpreted as compact spaces (simplices of probability vectors), implying that the minima and maxima in these formulas exist. The optimally-hard input distribution maximizing the left hand side of this equality and the optimal randomized algorithm minimizing the right hand side of the equality may not be easy to describe, as their calculation may involve the solution of very large linear programs.^[2]^[3] Nevertheless, the same principle can be used to convert any input distribution (regardless of its optimality) into a lower bound on the cost of all randomized algorithms, regardless of their implementability. It follows from the equality above that, if $D\in {\mathcal {D}}_{n}$ is any specific choice of a hard input distribution, and $R$ is any specific randomized algorithm in ${\mathcal {R}}$ , then $\min _{A\in {\mathcal {A}}}\mathbb {E} _{x\sim D}[c(A,x)]\leq \max _{x\in {\mathcal {X}}_{n}}\mathbb {E} [c(R,x)].$ That is, the best possible deterministic performance against distribution $D$ is a lower bound for the performance of algorithm $R$ against its worst-case input, regardless of what $R$ is. One may also observe this weaker version of Yao's principle directly, as $\min _{A\in {\mathcal {A}}}\mathbb {E} _{x\sim D}[c(A,x)]\leq \mathbb {E} _{x\sim D}[c(R,x)]\leq \max _{x\in {\mathcal {X}}_{n}}\mathbb {E} [c(R,x)],$ by linearity of expectation and the principle that $\min \leq \mathbb {E} \leq \max$ for any distribution. By avoiding maximization and minimization over ${\mathcal {D}}_{n}$ and ${\mathcal {R}}$ , this version of Yao's principle can apply in some cases where ${\mathcal {X}}$ or ${\mathcal {A}}$ are not finite.^[4]

Applications and examples

Time complexity

When the cost $c$ denotes the running time of an algorithm, Yao's principle states that the best possible running time of a deterministic algorithm, on a hard input distribution, gives a lower bound for the expected time of any Las Vegas algorithm on its worst-case input. Here, a Las Vegas algorithm is a randomized algorithm whose runtime may vary, but for which the result is always correct.^[5]^[6] For example, this form of Yao's principle has been used to prove the optimality of certain Monte Carlo tree search algorithms for the exact evaluation of game trees.^[6]

Query complexity

One of the original applications by Yao of his principle was to the evasiveness of graph properties, the number of tests of the adjacency of pairs of vertices needed to determine whether a graph has a given property, when the only access to the graph is through such tests. As Yao showed, for graph properties that are true of the empty graph but false for some other graph on $n$ vertices with only a bounded number of edges, such as planarity, a randomized algorithm must probe a quadratic number of pairs of vertices. The proof uses Yao's principle, with a hard distribution of inputs consisting of permutations of the graph that does not have the property.^[1]

The complexity of comparison-based sorting and selection algorithms is often measured in the number of comparisons made between pairs of data elements. For these problems, an averaging argument identifies the hardest input distributions: they are the distributions on $n$ distinct elements for which all permutations are equally likely. Yao's principle extends lower bounds for the average case number of comparisons made by deterministic algorithms, for this input distribution, to the worst case analysis of randomized comparison algorithms.^[1]

In black-box optimization, the problem is to determine the minimum or maximum value of a function, from a given class of functions, accessible only through calls to the function on arguments from some finite domain. In this case, the cost to be optimized is the number of calls. Yao's principle has been described as "the only method available for proving lower bounds for all randomized search heuristics for selected classes of problems".^[3]

Communication complexity

In communication complexity, an algorithm describes a communication protocol between two or more parties, and its cost may be the number of bits or messages transmitted between the parties. In this case, Yao's principle describes an equality between the average-case complexity of deterministic communication protocols, on an input distribution that is the worst case for the problem, and the expected communication complexity of randomized protocols on their worst-case inputs.^[2]^[7]

Online algorithms

Yao's principle has also been applied to the competitive ratio of online algorithms. An online algorithm must respond to a sequence of requests, without knowledge of future requests, incurring some cost or profit per request depending on its choices. The competitive ratio is the ratio of its cost or profit to the value that could be achieved achieved by an offline algorithm with access to knowledge of all future requests, for a worst-case request sequence that causes this ratio to be as far from one as possible. Here, one must be careful to formulate the ratio with the algorithm's performance in the numerator and the optimal performance of an offline algorithm in the denominator, so that the cost measure can be formulated as an expected value rather than as the reciprocal of an expected value.^[4]

An example given by Borodin & El-Yaniv (2005) concerns page replacement algorithms, which respond to requests for pages of computer memory by using a cache of $k$ pages, for a given parameter $k$ . If a request matches a cached page, it costs nothing; otherwise one of the cached pages must be replaced by the requested page, at a cost of one page fault. A difficult distribution of request sequences for this model can be generated by choosing each request uniformly at random from a pool of $k+1$ pages. For any deterministic algorithm, the expected number of page faults, over a sequence of $n$ pages, is $n/(k+1)$ . However, an offline algorithm can divide the request sequence into phases within which only $k$ pages are used, incurring only one fault at the start of a phase to replace the one page that is unused within the phase. By standard analysis of the coupon collector's problem, the expected number of requests in a phase is $(k+1)H_{k}$ , where $H_{k}=1+1/2+\cdots +1/k$ is the $k$ th harmonic number. It follows from renewal theory that the optimal number of page faults behaves in the limit for large $n$ as $n/(k+1)H_{k}$ , and therefore that the competitive ratio of any deterministic algorithm against this input distribution is $H_{k}$ . By Yao's principle, $H_{k}$ is also a lower bound on the competitive ratio of any randomized page replacement algorithm against a request sequence chosen by an oblivious adversary to be a worst case for the algorithm but without knowledge of the algorithm's random choices.^[8]

Game-theoretic interpretation

Yao's principle may be interpreted in game theoretic terms, via a two-player zero-sum game in which one player, Alice, selects a deterministic algorithm, the other player, Bob, selects an input, and the payoff is the cost of the selected algorithm on the selected input. Any randomized algorithm R may be interpreted as a randomized choice among deterministic algorithms, and thus as a mixed strategy for Alice. Similarly, a non-random algorithm may be thought of as a pure strategy for Alice. In any two-player zero-sum game, if one player fixes a fixed mixed strategy, then there is an optimal pure strategy that the other player can choose against it. By the minimax theorem of John von Neumann, there exists a game value $c$ , and mixed strategies for each player, such that the players can guarantee expected value $c$ or better by playing those strategies, and such that the optimal pure strategy against either mixed strategy produces expected value exactly $c$ . Thus, the minimax mixed strategy for Alice, set against the best opposing pure strategy for Bob, produces the same expected game value $c$ as the minimax mixed strategy for Bob, set against the best opposing pure strategy for Alice. This equality of expected game values, for the game described above, is Yao's principle in its form as an equality.^[4] Yao's 1977 paper, originally formulating Yao's principle, proved it in this way.^[1]

References

^ ^a ^b ^c ^d Yao, Andrew (1977), "Probabilistic computations: Toward a unified measure of complexity", Proceedings of the 18th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 222–227, doi:10.1109/SFCS.1977.24
^ ^a ^b Fortnow, Lance (October 16, 2006), "Favorite theorems: Yao principle", Computational Complexity
^ ^a ^b Wegener, Ingo (2005), "9.2 Yao's minimax principle", Complexity Theory: Exploring the Limits of Efficient Algorithms, Springer-Verlag, pp. 118–120, doi:10.1007/3-540-27477-4, ISBN 978-3-540-21045-0, MR 2146155
^ ^a ^b ^c Borodin, Allan; El-Yaniv, Ran (2005), "8.3 Yao's principle: A technique for obtaining lower bounds", Online Computation and Competitive Analysis, Cambridge University Press, pp. 115–120, ISBN 9780521619462
^ Moore, Cristopher; Mertens, Stephan (2011), "Theorem 10.1 (Yao's principle)", The Nature of Computation, Oxford University Press, p. 471, ISBN 9780199233212
^ ^a ^b Motwani, Rajeev; Raghavan, Prabhakar (2010), "Chapter 12: Randomized Algorithms", in Atallah, Mikhail J.; Blanton, Marina (eds.), Algorithms and Theory of Computation Handbook: General Concepts and Techniques (2nd ed.), CRC Press, pp. 12-1 – 12-24; see in particular Section 12.5: The minimax principle and lower bounds, pp. 12-8 – 12-10
^ Wigderson, Avi (2019), Mathematics and Computation: A Theory Revolutionizing Technology and Science, Princeton University Press, p. 210, ISBN 9780691189130
^ Borodin & El-Yaniv (2005), pp. 120–122, 8.4 Paging revisited.