Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for label embedding trees for large multi-class tasks. In one aspect, a method includes mapping each image in a plurality of images and each label in a plurality of labels into a multi-dimensional label embedding space. A tree of label predictors is trained with the plurality of mapped images such that an error function is minimized in which the error function counts an error for each mapped image if any of the label predictors at any depth of the tree incorrectly predicts that the mapped image belongs to the label predictor's respective label set.