Mistake Bounds for Binary Matrix Completion
We study the problem of completing a binary matrix in an online learning setting. On each trial we predict a matrix entry and then receive the true entry. We propose a Matrix Exponentiated Gradient algorithm [1] to solve this problem. We provide a mistake bound for the algorithm, which scales with the margin complexity [2, 3] of the underlying matrix. The bound suggests an interpretation where each row of the matrix is a prediction task over a finite set of objects, the columns. Using this we show that the algorithm makes a number of mistakes which is comparable up to a logarithmic factor to the number of mistakes made by the Kernel Perceptron with an optimal kernel in hindsight. We discuss applications of the algorithm to predicting as well as the best biclustering and to the problem of predicting the labeling of a graph without knowing the graph in advance.
The paper concerns completing binary matrix in the online manner: in each trial, the learner predicts the label in {-1,1}, the nature reveals the outcome and the learner suffers 0/1 loss. The interpretation is that each row is a task, and each column is an object, and the complexity of the problem is measures in terms of the margin complexity of the matrix. It is assumed that the problem is consistent in the sense that the entry seen multiple times alway receives the same label. The proposed algorithm to solve this problem is a version of the Matrix Exponentiated Gradient algorithm: a mistake bound in terms of margin complexity is provided, and it is shown that the algorithm makes a number of mistakes which is comparable up to a logarithmic factor to the number of mistakes made by the Kernel Perceptron with an optimal kernel in hindsight. Some applications are discussed: predicting as well as the best biclustering, and predicting the labeling of a graph without knowing the graph in advance. 
The paper is clearly written and easy to follow. The technical quality is sounds and the proofs seem correct (except one issue in the proof of Lemma A.4, mentioned below).   I am not entirely sure, whether there are any underlying assumptions on the data apart from the fact that the labels related to a given matrix entry are consistent (i.e., the same)? The authors claim that their setting is less general than in the previous papers on this topic, as they assume that there exists an underlying consistent predictor. Given the labels are consistent for each entry, is it sufficient to say that a consistent predictor exists? If so, I do not find this setting to be very restrictive, as in the real-life applications of matrix completion we often observe a given entry only once. I would be glad to get some feedback from the authors on this question.  While the basic mistake bound for matrix exponentiated gradient algorithm makes use of the analysis the previous work on MEG, the embedding of the comparators (sign-consistent matrices) to the space of positive matrices, and the outcomes to the space of symmetric matrices looks very interesting and original. I also liked the interpretation of the comparator class in terms of linear predictors with any weights over any features for each object, which permits competing with the Kernel Perceptron with an optimal kernel in hindsight.  One drawback is computational complexity of the algorithm, which can hinder the use of the algorithm in practical applications. I think, however, that the computational complexity could be somewhat improved by making use of the fact that the observed outcome matrices have rank one. Then, the eigenvalue decomposition of the exponent in the definition of W^(t) (Algorithm 1) can be maintained and updated using a faster algorithm for rank-one update of the eigenvalues and eigenvectors.  I think the paper brings significant contribution to matrix completion and online learning, and thus I am in favor of accepting it for publication.  Minor remarks:  - Lemma A.4: How is Tr(W^(t-1) X^(t)) bounded in the lemma when \hat{y} = -1? It seems to lower-bounded by 1/(n+m), while according to the Algorithm it is below 1/(n+m) when \hat{y} = -1.  - I think that part of the proof of Theorem 3.1, lines 129-135, is a quite standard bound on quantum relative entropy for matrices with unit trace (see, e.g., [1]), so it is probably not necessary to present it in full detail.  - l. 88-89: "the quantity 1/ mc(U) represents the margin of the worst linear classifier in the best embedded space" -- why is it the worst linear classifier -- from the definition, it looks as if the inverse margin is minimized (= the margin is maximized) over both the classifier's weights and the embedding; shouldn't it be "the best linear classifier"?   ============================  I have read the rebuttal, which clarified all the issues raised in my review. Thank you.