Extreme Multi-label Classification (XMC) involves assigning relevant tags from a pool of millions of possibilities. While deep learning is a dominant trend, this research demonstrates that optimized "one-vs-rest" (OvR) linear models can match state-of-the-art performance by leveraging hardware-aware execution. By addressing memory bottlenecks in multicore systems through NUMA-aware management and employing Mean-Separating Initialization (MSI), the proposed approach achieves significant training speedups and competitive accuracy on massive datasets.
The XMC Challenge
In applications such as tagging Wikipedia articles or categorizing Amazon products, the label set can reach millions of entries. Traditional XMC solutions often rely on OvR reductions, where a separate classifier is trained for every label. While this process is "embarrassingly parallel," the sheer scale creates massive computational costs and hardware inefficiencies. On modern multicore servers, the memory bus becomes a bottleneck as cores compete for access to large feature matrices.
A standard Feed-Forward Network (FFN) architecture. While deep learning models like these are the current trend, optimized linear models remain a competitive baseline for XMC.
The researchers focused on optimizing frameworks like DiSMEC and ProXML by combining algorithmic shifts with low-level hardware awareness:
NUMA-Aware Memory Management: To prevent the memory bus from becoming a bottleneck, the feature matrix is replicated across different Non-Uniform Memory Access (NUMA) domains. This localization reduces latency and ensures CPU cores are efficiently utilized.
Mean-Separating Initialization (MSI): Instead of zero-initialization, MSI starts the optimization with a vector that separates the means of positive and negative instances. This accelerates the emergence of data sparsity, slashing computation time.
Implicit Hard-Instance Mining: Using a squared hinge loss allows the algorithm to focus on "hard" examples near the decision boundary. Combined with MSI, this reduces the number of expensive calculations required during training.
Feature Sorting: Reordering features based on frequency improves cache locality, minimizing the time the CPU spends waiting for data from RAM.
Key Results
Empirical studies on benchmarks like AmazonCat and Wikipedia-500K revealed that MSI alone can provide speedups between 150% and 500%. The system showed near-perfect linear scaling up to 32 threads on high-end AMD Rome systems before hitting memory bandwidth limits. Furthermore, the hardware-optimized DiSMEC achieved precision scores remarkably close to state-of-the-art deep learning models like LightXML and AttentionXML, despite being significantly simpler.
Challenges and Limitations
Despite these gains, several hurdles remain:
The Memory Wall: Even with NUMA optimizations, adding more cores beyond a certain point yields diminishing returns as RAM bandwidth is exhausted.
Thermal Throttling: Running all cores at 100% capacity can cause CPUs to downclock to manage heat, limiting theoretical maximum speedups.
Tail Labels: Categories with very few examples remain a statistical challenge that hardware optimization alone cannot solve.
Conclusion
The success of these optimized linear models highlights that for many large-scale classification tasks, the bottleneck is not necessarily the model's complexity, but its interaction with hardware. By acknowledging physical constraints like NUMA latency and memory bandwidth, researchers can achieve high-performance results with simpler, more interpretable models.
Summary updated
Abstract
Feed-Forward Networks (FFNs), or multilayer perceptrons, are fundamental network structures for deep learning. Although feed-forward networks are structurally uncomplicated, their training procedure is computationally expensive. It is challenging to design customized hardware for training due to the diversity of operations in forwardand backward-propagation processes. In this contribution, we present an approach to train such networks using Field-Programmable Gate Arrays (FPGAs). This approach facilitates the design of reconfigurable architectures by reusing the same set of hardware resources for different operations in backpropagation. In our empirical study, a prototype implementation of the architecture on a Xilinx UltraScale+ VU9P FPGA achieves up to a 5.2 times speedup over the PyTorch platform running on 8 threads on a workstation with two Intel Xeon E5-2643 v4 CPUs.During the last decade, the compilation of database queries to machine code has emerged as a very efficient alternative to classical, interpretation-based query processing modes [529]. Compiled code can better utilize advanced features of modern CPU instruction sets; avoid interpretation overhead; and-most importantly-minimize data I/O (e.g., to main memory). This success story raises the hope that compilation strategies can be lifted to nonstandard architectures, such as GPUs or other accelerators, as well as to support other data-intensive processing tasks. However, as we shall see in this section, the dataparallel nature of the devices is at odds with established techniques in query compilation, resulting in massive resource under-utilization if compilation strategies are applied too naively. As a remedy, we propose two novel mechanisms that re-establish compute efficiency of compiled code on data-parallel hardware: Lane Refill and Push-Down Parallelism are “virtual operators” that participate in optimization and code generation just like true query operators (making our approach seamlessly integrate with existing systems). At runtime, they compensate for lurking resource under-utilization by adapting parallelization strategies on-the-go. The outcome is a resource utilization that is close to the hardware’s maximum, while causing negligible overhead even in unfavorable situations. Lane Refill and Push-Down Parallelism are part of our compiler platform DogQC, which leverages modern graphics processors for efficient database query processing.There are classification problems, such as assigning categories to aWikipedia article, where the possible set of labels is very large, numbering in the millions. Somewhat surprisingly, these so-called Extreme-Multilabel Classification (XMC) problems can be solved quite successfully by applying a linear classifier to each label individually. This decomposition into binary problems is called a one-vs-rest reduction. As these problems are completely independent, the reduced task is embarrassingly parallel and can be trivially spread across multiple cores and nodes. After training, the model can be sparsified by culling small weights to only require a fraction of the memory and computational power for prediction on new samples.This section demonstrates how the integration of knowledge about underlying hardware platforms and learning algorithms can provide results that would not be feasible by using the knowledge of only one type. In particular, this section presents the optimization of ML algorithms on multicore systems, and in this way addresses the same type of architectures as in Section 6.3. The optimization is based on resourceaware scheduling strategies for parallel machine learning algorithms. The focus is on Model-Based Optimization (MBO), also known as Bayesian optimization, which is an ML algorithm with huge resource demands, including a large number of computational jobs. Execution times of these jobs are estimated in order to enable their scheduling on parallel processors. The section demonstrates that this scheduling enables the processing of larger problem sizes within a given time budget and reduces the end-toend wall-clock time for a constant problem size.
BibTeX
@inproceedings{schultheis2022extreme,
author = {Erik Schultheis and Rohit Babbar},
title = {{Extreme Multicore Classification}},
booktitle = {Mach. Learn. Under Resour. Constraints Vol. 1},
year = {2022},
url = {https://openreview.net/forum?id=FTMMaWY9BE},
}