Sparse Extreme Multi-label Learning with Oracle Property

Weiwei Liu, Xiaobo ShenICML 2019 · OpenReview

Extreme Multi-label Learning (XML) is the challenging task of assigning the most relevant labels to a data point from an exceptionally large pool of candidates—often numbering in the millions. Applications range from product categorization on e-commerce platforms like Amazon to tagging millions of Wikipedia articles.

A leading approach for this task is Sparse Local Embeddings for Extreme Classification (SLEEC). SLEEC works by learning local, distance-preserving embeddings to capture label correlations, avoiding the restrictive assumption that the entire label matrix is low-rank. However, SLEEC has historically suffered from a "theory gap." It typically relies on $l_1$ regularization (Lasso), which is known to introduce estimation bias. Consequently, the statistical convergence rates of SLEEC were not fully understood, and it was unclear if the method could ever achieve "oracle" performance—the theoretical gold standard where an algorithm performs as accurately as if it already knew the true underlying model.

Eliminating Bias with Nonconvex Penalties

To address this theoretical gap, researchers have proposed a unified framework for SLEEC that replaces the standard $l_1$ penalty with nonconvex penalties. Specifically, the authors utilize:

  • SCAD (Smoothly Clipped Absolute Deviation)
  • MCP (Minimax Concave Penalty)

Unlike $l_1$ regularization, these nonconvex penalties are mathematically designed to eliminate estimation bias. The authors formulate a new objective function combining a squared loss term (for the regression between features and embeddings) with these nonconvex regularizers.

Because this introduces a non-trivial, non-smooth, and nonconvex optimization problem, the team adapted an Accelerated Proximal Gradient (APG) method. This solver efficiently handles the complex objective while maintaining the computational speed required for massive datasets.

The Oracle Property and Convergence

The most significant theoretical breakthrough in this work is the proof that, under mild conditions, the proposed estimator achieves the Oracle Property. This means the algorithm effectively "discovers" the true support of the model during learning, performing as well as an oracle that knows the true labels in advance.

Furthermore, the authors established refined convergence rates. They demonstrated that if the entries in the underlying model are sufficiently large, the statistical convergence rate improves from $O(\frac{\sigma\sqrt{\varpi} + \sqrt{s^*}}{\mu\sqrt{n}})$ to a sharper $O(\frac{\sqrt{s^*}}{\mu\sqrt{n}})$, where $s^*$ is the number of true labels and $n$ is the number of samples. This provides a mathematical guarantee that the model's accuracy scales efficiently with more data.

Empirical Results

The proposed methods, SML-SCAD and SML-MCP, were evaluated against strong baselines (including the original SLEEC, FastXML, and LEML) on six real-world datasets from the Extreme Classification Repository, ranging from medium-scale (Bibtex, Mediamill) to large-scale (Amazon, Wiki10).

Precision@k comparison

The theoretical benefits translated directly into state-of-the-art empirical performance. For instance, on the Bibtex dataset, SML-MCP achieved a Precision@1 of 67.39%, outperforming the original SLEEC (65.08%).

nDCG@k comparison

Across both medium and massive datasets like Amazon, the nonconvex approaches consistently topped the charts for both Precision@k and normalized Discounted Cumulative Gain (nDCG). The empirical results strongly validated the "sharper" convergence rates predicted by the theory, particularly on datasets with strong label signals.

Limitations and Future Directions

While this research provides a robust theoretical framework for the regression component of the SLEEC pipeline, it does not deeply explore the initial embedding-learning step (the $k$-nearest neighbor graph construction), which remains critical to overall performance.

Future work may involve applying these nonconvex "oracle" properties to other XML architectures beyond local embeddings, and exploring the computational trade-offs of nonconvex penalties on even larger datasets where the overhead of the APG method might become a bottleneck.

Summary updated

Abstract

The pioneering work of sparse local embeddings for extreme classification (SLEEC) (Bhatia et al., 2015) has shown great promise in multi-label learning. Unfortunately, the statistical rate of conve...
BibTeX
@inproceedings{liu2019sparse,
  author = {Weiwei Liu and Xiaobo Shen},
  title = {{Sparse Extreme Multi-label Learning with Oracle Property}},
  booktitle = {International Conference on Machine Learning},
  year = {2019},
  url = {https://openreview.net/forum?id=S1Z1JoWuZS},
}
Figure