Mistake Bounds for Binary Matrix Completion
Authors: Mark Herbster, Stephen Pasteris, Massimiliano Pontil
NeurIPS 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. |
| Researcher Affiliation | Academia | Mark Herbster University College London Department of Computer Science London WC1E 6BT, UK m.herbster@cs.ucl.ac.uk Stephen Pasteris University College London Department of Computer Science London WC1E 6BT, UK s.pasteris@cs.ucl.ac.uk Massimiliano Pontil Istituto Italiano di Tecnologia 16163 Genoa, Italy and University College London Department of Computer Science London WC1E 6BT, UK m.pontil@cs.ucl.ac.uk |
| Pseudocode | Yes | Algorithm 1 Predicting a binary matrix. Parameters: Learning rate 0 < γ 1 . Initialization: W (0) I (m+n), where I is the (m + n) (m + n) identity matrix. For t = 1, . . . , T Get pair (it, jt) 2 Nm Nn. Define X(t) := 1 2(eit + em+jt)(eit + em+jt)>, where ek is the k-th basis vector of Rm+n. Predict 1 if Tr(W (t 1)X(t)) 1 m+n, 1 otherwise. Receive label yt 2 { 1, 1} and if ˆyt 6= yt update W (t) W (t 1)exp( γ 2 (yt ˆyt)X(t)) |
| Open Source Code | No | The paper does not provide any concrete access to source code (no specific repository link, explicit code release statement, or code in supplementary materials) for the methodology described. |
| Open Datasets | No | The paper describes a theoretical online learning setting and does not refer to specific, publicly available datasets for training or experimentation. Therefore, no concrete access information is provided. |
| Dataset Splits | No | The paper is theoretical and does not describe empirical experiments involving dataset splits. Therefore, no specific dataset split information for validation is provided. |
| Hardware Specification | No | The paper is theoretical and does not describe experiments that would require specific hardware. Therefore, no hardware specifications are provided. |
| Software Dependencies | No | The paper is theoretical and does not describe empirical implementations that would require specific software dependencies with version numbers. Therefore, no such details are provided. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithm design and mistake bounds, not empirical experimentation. As such, it does not contain specific experimental setup details like hyperparameter values or training configurations. |