Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a new learning methodology for training neural networks based on Prover-Verifier Games (PVGs), which are inspired by interactive proof systems (IPS). PVG consists of two learners, which work in both collaborative and adversarial manners, and the hope is that two learners together could achieve more reliable predictions. This paper studies eight possible game instantiations, depending on player order and when the problem instance is revealed, and the theoretical analysis shows that two instantiations are superior to others, which is also confirmed by an empirical evaluation. This paper also discovers that stress-testing of verifier's robustness is a more meaningful measurement of the learning success in contrast to prediction accuracy during training. 
main_review: Strengths:
- the new learning methodology is novel and built on top of solid theoretical foundations, namely, interactive proof systems and game theoretic optimizations;
- the effectiveness of different instantiations are backed up by both theoretical analyses and empirical studies;
- the writing is very easy to follow, even though there is quite an amount of theoretical stuff.

Weaknesses:
- chosen tasks in the evaluation seem fairly simple, so whether there is a great practical potential of the new methodology is not yet clear;
- the claim of learning in a "checkable" or "verifiable" manner could be somewhat misleading, as it seems _not_ really verifiable in the sense of classic software analysis and verification (i.e., a piece of code meets its formal specification for all possible executions). The naming might be standard in the theoretical computer science research community, which I am not quite familiar with;
- the motivation of learning robust protocols is not well-addressed. Basically, why does learning protocols matter in practice? The learned protocol and messages seem to be embedded in neural networks and real-valued vectors, so how could they be interpretable?

summary_of_the_review: The idea proposed in this paper is novel, and its effectiveness is backed up by theoretical analysis and experimental evaluations. Although no strong practical results have been shown yet, the idea deserves to be published soon. I would like to recommend acceptance for this paper.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper explores the idea of learning a game-theory-inspired prover-verifier system to augment neural networks with verifiable predictions.   In this paper, the authors set up a differentiable prover-verifier game and establish conditions on the formulation of the game to ensure the learned verifier satisfies the soundness and completeness constraints. The paper has the following results:
- All verifier leading Stackelberg equilibria in a verifier-leading sequential PVG formulation in which the problem instance is revealed after the verifier picks its strategy give a desirable proof-verification protocol.
- For the BEC-based prover-verifier system, the paper also guarantees that alternate gradient descent ascent converges to equilibrium under suitable learning rates verifier-leading PVG formulations.
- Empirical evidence from the BEC experiments and the FindThePlus experiments show the effectiveness of the learning scheme in a practical setting.
main_review: Strengths
- The paper does a good job of formalizing the various PVG settings and relates the effectiveness of the settings in realizing the goal of finding a desirable prover-verifier system. The analysis of the various equilibria in the context of completeness and soundness of the verifier provides good insight into the problem and might help future research.
- The empirical method of freezing the verifier to allow the prover more time to adjust to the verifier and hide its "tells" provides a more compelling case for the system's effectiveness. 
 
Weakness
- Most of the theoretical analysis of achievable equilibria in the paper only applies to the case of BEC-based example prover-verifier systems. It is not clear if this would transfer well to more complicated settings. Although the theorems stated in the PVG formulation apply to a more general setting, the convergence guarantees for the games seem to need a lot more work.
- For the empirical evidence justifying the effectiveness of this strategy, I would like to see it applied to a more practical setting. The current approach seems to heavily depend on human intervention to limit the prover and verifier strategy space severely. I would like to see more theoretical work justifying the importance of expert intervention in the game design process or more experimental evidence in the absence of such interventions.
summary_of_the_review: I feel the paper introduces a novel approach for learning prover-verifier systems. Still, I think the theoretical and experimental treatment of the topic in the current version of the paper is not rigorous enough at the moment. I feel the authors need to address the comments above.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: Based on the ideas lying behind interactive proof systems (IPS), this paper proposes a prover-verifier games (PVG) framework, which aims at solving decision problems in a verifiable manner, where two learning agents interact with competing goals: a trusted verifier agent tries to get a correct answer to the problem while an untrusted (but more effective) prover tries to convince the verifier that its answer is correct, regardless of its actual correctness. The paper studies the framework under several (sequential and simultaneous) game scenarios.
main_review: First of all, I have to admit that I am no expert in this area and hence I do not feel qualified to fully assess the merits of this paper. Also, for this reason, I find the paper really hard to follow. The presentation of the material does not offer a reader any help in this regard. The paper is not self-contained and a reader is supposed to go from one paper to another in hope of grasping what the authors are talking about.

Unfortunately, what is worse is that the paper delivers not a single example of a game that the authors are talking about. I do believe this makes the presentation suffer a lot (granted that I am from a different research area). The notation and the problem being studied aren't exemplified nor well-motivated either (as an example, what is PAC verification?).

Having said that, the paper seems to offer a rigorous theoretical study with a wealth of propositions, theorems and their proofs (there are several appendices attached). (In this sense, I am inclined to think that another venue might possibly fit this work better than ICLR.) Additionally, theoretical findings are confirmed by experimental analysis performed.
summary_of_the_review: To summarise, although I personally find the paper close to impossible to follow, I don't really feel in a position to judge it based solely on this fact simply because I am not an expert in the area, and it is unclear to me what presentation is deemed standard here and what level of preliminary descriptions is accepted as adequate.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors propose a framework for training networks, such that justification of the answers can automatically emerge from it. Specifically, they propose a training framework where a prover's objective is to persuade the verifier network while the verifier network's objective is answering correctly based on both the original input and the prover's message. The authors analyze when the two-agents training network would converge and identify when the solution derived would become trivial. The authors also applied their framework in two experimental settings: the binary erasure task and the cross detection task, and show that the method would results in robust and interpretable decision rule.
main_review: **Pros:**
- Coming up with a way to learn a network such that it is able to justify its answer is very important and useful in the real world
- It seems like the authors have done a good job analyzing the dynamics of the particular game in Table 1. I don't have a good sense of the significance of the theoretical contribution and would allow the other reviewers who are more familiar with the topic to comment on this point. 

**Cons:**
- The toy examples seem too naive to demonstrate the effectiveness of the framework with respect to interpretability and robustness. Both of these directions are heavily researched, and the authors should be able to find other more realistic settings to convince us of the value of the framework.
- It is quite difficult for me to identify the practical usage of the framework when reading through the paper, perhaps the authors could have been more concrete with respect to the potential applications?

**Request for clarification:**

I am having some trouble understanding the practical usefulness of the proposed framework, and could really use some clarification from the authors. From my understanding, the main usages of the proposed framework are the **interpretability** and **robustness** of the network's decision. However, I don't think the experiments have demonstrated effectiveness in these two settings. Please correct me if I understand the purpose of the proposed framework incorrectly.

The authors try to demonstrate the interpretability of the prover's message by examing the gaze of the verifier, which depends on the prover's message. The author claims that the verifier's gaze is interpretable because it always focuses on the region of the image where a blue cross is present. However, the same behavior can be achieved quite easily with other techniques. For example, one can simply look at the saliency map of a naive classifier on the dataset and should be able to identify the cross-region quite easily or one can simply ablate each region of the image and study how the ablation changes the model's prediction.

With respect to robustness, the author demonstrated the robustness of the verifier's answer with respect to the prover's message, but I am having trouble understanding why being robust to the prover's message is important. For the most part, we care about robustness with respect to changes in the input distribution as machine learning systems are deployed in a different environment, but in what scenario would robustness to an internal prover's message be useful? Does robustness to the prover's message translate to robustness in settings that we care about? 

-----updates after rebuttal------

After the author's clarification, I am able to understand the theoretical contribution more, and found it to be a valuable contribution. The empirical weakness of the paper remains. However, I have updated my scores to a 6.

summary_of_the_review: The goal of coming up with a neural network that can justify its decision is an important task. The authors have done a thorough job of technically analyzing the proposed framework, but experiments could be strengthened by using more realistic settings.
review_title: null

Meta-review: The reviewers are split about this paper and did not come to a consensus: on one hand they agreed that the paper has valuable theoretical contributions and addresses an important problem in current ML literature, on the other hand they would have liked to see empirical results on a real-world problem setting. After going through the paper and the discussion I have decided to vote to reject for the following reason: I believe the reviewers' concerns about empirical results is not just a request for applying this to more datasets (which is easy to satisfy and I don't think is grounds for rejection), but is actually for a clearer connection for how this work would be used in the machine learning problems described in the introduction and related work sections. What would really help this paper is a real-world running example, in place of the blue plus example, in Figure 1 (I think the blue plus problem is still a useful experimental tool and should be evaluated, but it doesn't clarify the real-world use-cases of this work. This led the reviewers to look to the experimental section for clarification on this, but this wasn't clarified there either. The authors' response to these concerns was an out-of-scope argument: the goal of this paper is to derive/test theoretical results, and there are a number of possible use cases we could apply this to. The authors argue that the current work sends 'a strong signal to the ICLR community that the Prover-Verifier Game is interesting and promising'. I'm sorry but I disagree here: the authors need to do more to convince the ICLR community that this is a framework that will solve outstanding problems in ML. This is solved if the authors (a) run their approach on a real-world dataset in a paper they cite in the related work, (b) they include baselines in this experiment, and (c) if they add this as a running example throughout with a figure that explains this real-world example. With these additions the paper will be a much stronger submission.
Decision: Reject