%0 Journal Article
%T Fast Label Embeddings via Randomized Linear Algebra
%A Paul Mineiro
%A Nikos Karampatziakis
%J Computer Science
%D 2014
%I arXiv
%X Many modern multiclass and multilabel problems are characterized by increasingly large output spaces. For these problems, label embeddings have been shown to be a useful primitive that can improve computational and statistical efficiency. In this work we utilize a correspondence between rank constrained estimation and low dimensional label embeddings that uncovers a fast label embedding algorithm which works in both the multiclass and multilabel settings. The result is a randomized algorithm whose running time is exponentially faster than naive algorithms. We demonstrate our techniques on two large-scale public datasets, from the Large Scale Hierarchical Text Challenge and the Open Directory Project, where we obtain state of the art results.
%U http://arxiv.org/abs/1412.6547v7