Learning Eigenvectors for Free
We extend the classical problem of predicting a sequence of outcomes from a finite alphabet to the matrix domain. In this extension, the alphabet of $n$ outcomes is replaced by the set of all dyads, i.e. outer products $\u\u^\top$ where $\u$ is a vector in $\R^n$ of unit length. Whereas in the classical case the goal is to learn (i.e. sequentially predict as well as) the best multinomial distribution, in the matrix case we desire to learn the density matrix that best explains the observed sequence of dyads. We show how popular online algorithms for learning a multinomial distribution can be extended to learn density matrices. Intuitively, learning the $n^2$ parameters of a density matrix is much harder than learning the $n$ parameters of a multinomial distribution. Completely surprisingly, we prove that the worst-case regrets of certain classical algorithms and their matrix generalizations are identical. The reason is that the worst-case sequence of dyads share a common eigensystem, i.e. the worst case regret is achieved in the classical case. So these matrix algorithms learn the eigenvectors without any regret.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Learning Linear Symmetries in Data Using Moment Matching
It is common in machine learning and statistics to use symmetries derived from expert knowledge to simplify problems or improve performance, using methods like data augmentation or penalties. In this paper we consider th…
Data AugmentationThe Laplacian in RL: Learning Representations with Efficient Approximations
The smallest eigenvectors of the graph Laplacian are well-known to provide a succinct representation of the geometry of a weighted graph. In reinforcement learning (RL), where the weighted graph may be interpreted as the…
Reinforcement LearningReinforcement Learning (RL)Representation LearningSpectral Clustering via Orthogonalization-Free Methods
While orthogonalization exists in current dimensionality reduction methods in spectral clustering on undirected graphs, it does not scale in parallel computing environments. We propose four orthogonalization-free methods…
ClusteringDimensionality ReductionSpecNet2: Orthogonalization-free spectral embedding by neural networks
Spectral methods which represent data points by eigenvectors of kernel matrices or graph Laplacian matrices have been a primary tool in unsupervised data analysis. In many application scenarios, parametrizing the spectra…
Computational EfficiencyMachine learning in spectral domain
Deep neural networks are usually trained in the space of the nodes, by adjusting the weights of existing links via suitable optimization protocols. We here propose a radically new approach which anchors the learning proc…
BIG-bench Machine Learning