Target encoding plays a central role when learning Convolutional NeuralNetworks. In this realm, One-hot encoding is the most prevalent strategy due toits simplicity. However, this so widespread encoding schema assumes a flatlabel space, thus ignoring rich relationships existing among labels that can beexploited during training. In large-scale datasets, data does not span the fulllabel space, but instead lies in a low-dimensional output manifold. Followingthis observation, we embed the targets into a low-dimensional space,drastically improving convergence speed while preserving accuracy. Ourcontribution is two fold: (i) We show that random projections of the labelspace are a valid tool to find such lower dimensional embeddings, boostingdramatically convergence rates at zero computational cost; and (ii) we proposea normalized eigenrepresentation of the class manifold that encodes the targetswith minimal information loss, improving the accuracy of random projectionsencoding while enjoying the same convergence rates. Experiments on CIFAR-100,CUB200-2011, Imagenet, and MIT Places demonstrate that the proposed approachdrastically improves convergence speed while reaching very competitive accuracyrates.