Sparse Extreme Multi-label Learning with Oracle Property

The pioneering work of sparse local embeddings on multilabel learning has shown great promise in multilabel classification. Unfortunately, the statistical rate of convergence and oracle property of sparse local embeddings are still not well understood. To fill this gap, we present a unified framework for this method with nonconvex penalty. Theoretically, we rigorously prove that our proposed estimator enjoys oracle property (i.e., performs as well as if the underlying model were known beforehand), and obtains a desirable statistical convergence rate. Moreover, we show that under a mild condition on the magnitude of the entries in the underlying model, we are able to obtain an improved convergence rate. Extensive numerical experiments verify our theoretical findings and the superiority of our proposed estimator.