  Modeling the dependence between outputs is a fundamental challenge in
multilabel classification. In this work we show that a generic regularized
nonlinearity mapping independent predictions to joint predictions is sufficient
to achieve state-of-the-art performance on a variety of benchmark problems.
Crucially, we compute the joint predictions without ever obtaining any
independent predictions, while incorporating low-rank and smoothness
regularization. We achieve this by leveraging randomized algorithms for matrix
decomposition and kernel approximation. Furthermore, our techniques are
applicable to the multiclass setting. We apply our method to a variety of
multiclass and multilabel data sets, obtaining state-of-the-art results.
