Online Learning of Eigenvectors
Authors: Dan Garber, Elad Hazan, Tengyu Ma
ICML 2015 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper we present new algorithms that avoid both issues. On one hand they do not require any expensive matrix decompositions and on the other, they guarantee regret rates with a mild dependence on the dimension at most. We extend our results to also handle non-symmetric matrices. Our main result is an online algorithm that takes the so called oracle approach and is based on the Follow the Perturbed Leader meta-algorithm. We also consider a somewhat easier stochastic setting, in which we assume that the sequence of matrices is sampled from a fixed and unknown distribution. We present an algorithm that takes the so called iterative approach and is analogues to the Power algorithm for the offline setting, i.e. it computes a single matrix-vector product on each iteration. |
| Researcher Affiliation | Academia | Dan Garber DANGAR@TX.TECHNION.AC.IL Technion Israel Institute of Technology Elad Hazan EHAZAN@CS.PRINCETON.EDU Princeton University Tengyu Ma TENGYUL@CS.PRINCETON.EDU Princeton University |
| Pseudocode | Yes | Algorithm 1 Asymmetric to Symmetric Conversion Algorithm, Algorithm 2 Epoch Power Method, Algorithm 3 Follow the Perturbed Leader |
| Open Source Code | No | The paper does not contain any explicit statement about releasing source code for the described methodologies, nor does it provide a link to a code repository. |
| Open Datasets | No | The paper is theoretical and does not describe empirical experiments using specific datasets. Therefore, it does not provide information about public dataset availability or access. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with data. Consequently, it does not specify training, validation, or test dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not describe any hardware specifications used for running experiments. |
| Software Dependencies | No | The paper is theoretical and does not specify software dependencies with version numbers required for replication. |
| Experiment Setup | No | The paper is theoretical and does not describe a concrete experimental setup, including hyperparameters or system-level training settings. |