Large-scale image classification with trace-norm regularization

With the advent of larger image classification datasets such as ImageNet, designing scalable and efficient multi-class classification algorithms is now an important chal-lenge. We introduce a new scalable learning algorithm for large-scale multi-class image classification, based on the multinomial logistic loss and the trace-norm regularization penalty. Reframing the challenging non-smooth optimiza-tion problem into a surrogate infinite-dimensional optimiza-tion problem with a regular `1-regularization penalty, we propose a simple and provably efficient accelerated coor-dinate descent algorithm. Furthermore, we show how to perform efficient matrix computations in the compressed domain for quantized dense visual features, scaling up to 100,000s examples, 1,000s-dimensional features, and 100s of categories. Promising experimental results on the “Fun-gus”, “Ungulate”, and “Vehicles ” subsets of ImageNet are presented, where we show that our approach performs sig-nificantly better than state-of-the-art approaches for Fisher vectors with 16 Gaussians. 1