Reviews: A General Framework for Robust Interactive Learning

The paper proposes a general framework for interactive learning. In the framework, the machine learning models are represented as the nodes in a graph G and the user feedback are represented as weighted edges in G. Under the assumption of "if s, s* are the proposed and target models, then any (correct) user feedback s' must lie on the shortest s-s* path in G", the author showed that the Multiplicative Weights Update algorithm can efficiently learn the target model. The framework can be applied to three important machine learning tasks: ranking, clustering, and classification. The problem investigated in the paper is interesting and important. The theoretical results of the paper is convincing.