Re-evaluating Evaluation
"What we observe is not nature itself, but nature exposed to our method of questioning." -Werner Heisenberg Progress in machine learning is measured by careful evaluation on problems of outstanding common interest. However, the proliferation of benchmark suites and environments, adversarial attacks, and other complications has diluted the basic evaluation model by overwhelming researchers with choices. Deliberate or accidental cherry picking is increasingly likely, and designing well-balanced evaluation suites requires increasing effort. In this paper we take a step back and propose Nash averaging. The approach builds on a detailed analysis of the algebraic structure of evaluation in two basic scenarios: agent-vs-agent and agentvs-task. The key strength of Nash averaging is that it automatically adapts to redundancies in evaluation data, so that results are not biased by the incorporation of easy tasks or weak agents. Nash averaging thus encourages maximally inclusive evaluation -since there is no harm (computational cost aside) from including all available tasks and agents.
The paper proposes a new way to evaluate algorithms given their performance either on tasks or in a match against each other. Many papers evaluate new algorithms and tasks in ad-hoc ways, and it is often unclear which algorithm is better than which, and under what circumstances. The authors bring an educated approach to this issue by borrowing techniques from game theory. They consider a meta-game where one player chooses a team / distribution of algorithm and the other a team / distribution of tasks and propose ranking methods based on this game. There are two somewhat different approaches given in the paper. The first describes a decomposition of the algorithm-vs-task (AvT) or algorithm-vs-algorithm (AvA) matrix that lead to a low-rank approximation of sorts, giving ‘latent vectors’ for each algorithm that act as a multi-dimensional ranking. These provide a better representation of the algorithms than a one-dimensional ranking such as Elo, at the cost of being less interpretable. In particular they do not force a total order. The second method provides a ranking that tries to maintain a set of properties that seem very reasonable. This method provides each algorithm a score based on its comparison to the min-max strategy in the above mentioned game. The ranking is done according to the score.     Summary: This is somewhat of a non-standard paper as it doesn’t bring any new technique or develop a new mathematical tool. Rather it adapts known techniques in game theory and attempts to bring order to a somewhat chaotic area of algorithm evaluation. I suspect that the decision of accepting / rejecting the paper could be somewhat subjective but my opinion is to accept the paper.  Writing: The paper is a pleasure to read. The authors take time to explain their approach and the intuition for their decisions is presented clearly.   Related literature: The authors should relate their work to the field of dueling bandits. The dueling bandit problem, motivated by IR where algorithms are compared against each other has very similar issue. It is a common case there that the preference between pairs is not transitive meaning alg1 > alg2, alg2 > alg3, alg3 > alg1. Despite that, the bandit problem requires a notion of the best algorithm and of regret, meaning a sub optimality measure for a non-optimal algorithm. The issue is typically solved there by assuming the existence of a Condorcet winner, meaning an algorithm that is likely to beat any other algorithm in a match w.p. larger than 1/2. Given that, the regret associated with a sub-optimal algorithm is determined by how likely it is to lose to this winner. This definition exactly matches the Nash averaging score given here. In fact, there is a paper for dueling bandits titled “Instance-dependent Regret Bounds for Dueling Bandits” that discusses the case where there is no Condorcet winner, and they propose a notion of regret that is strongly related to the Nash averaging score.  Comments: * Equation at 157: Why are the Eigenvalues assumed to be approximately -i,i? Could you add an explanation?  * Line 165: The norm of P is not one - but depends on the number of players. It would be more helpful to discuss something normalized like |P-P’|/|P|. Also, the objective is not to reconstruct P in the Frobenius norm but with logistic loss. Is it possible to present that instead? Finally, why is there a ‘slight’ improvement? 0.85 to 0.35 seems like a pretty big improvement..  * line 168: Add one line to describe what the algorithms are meant to solve  * Is it true that n_A(i) is the payoff of algorithm i against the maxent NE strategy? This could be mentioned explicitly to demonstrate interpretability   * Theorem 1: The proposed score is the Nash Averaging n_A, but the theorem gives properties of p^*. I understand that the proofs go through p^* but shouldn’t the main statement be written in terms of n_A? Also, the notation \eps-Nash should be defined before used in a theorem.  * Normalizing scores (in AvT) seem like an important issue that is somewhat avoided - is there any educated way of doing that? Perhaps converting to quantiles so outliers will not be an issue?