Herbster, MJ; Pasteris, S; Pontil, M; (2016) Mistake Bounds for Binary Matrix Completion. In: Lee, DD and Sugiyama, M and Luxburg, UV and Guyon, I and Garnett, R and Garnett, R, (eds.) Proceedings of the 29th Conference on Neural Information Processing Systems (NIPS 2016). NIPS Proceedings: Barcelona, Spain.

Preview

Text cf-star-2-full.pdf - Accepted Version Download (305kB) | Preview

Abstract

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.

Download activity - last month

Export as XMLCSVJSON

Download activity - last 12 months

Export as XMLCSVJSON

Downloads by country - last 12 months

Export as XMLJSONCSV

Archive Staff Only

View Item