Abstract
Ordinal regression (OR) is a fundamental machine learning task for predicting categories with a natural order, such as age groups or ratings. A prevalent strategy involves learning a one-dimensional transformation (1DT) and partitioning it using thresholds. Finding the optimal thresholds typically requires Dynamic Programming (DP), which is inherently sequential and computationally expensive for large datasets. This paper introduces an Independent Optimization (IO) algorithm that allows for parallel threshold calculation. We prove that for convex loss functions, IO guarantees optimal, ordered thresholds. Experimental results on large-scale facial age estimation datasets demonstrate that our Parallel IO (PIO) algorithm significantly reduces computation time—by approximately 40% in total training pipelines—without compromising accuracy.
Introduction
Ordinal regression occupies the middle ground between classification and regression, dealing with discrete labels that possess a meaningful ranking. The threshold method is a popular approach where a model maps high-dimensional input data onto a one-dimensional line. This line is then "sliced" by a set of thresholds to determine the predicted category.
The primary challenge in this framework is finding the optimal thresholds that minimize empirical risk on training data. Traditionally, researchers have relied on Dynamic Programming (DP) to solve this optimization problem. However, DP's sequential nature creates a significant bottleneck as datasets scale to hundreds of thousands of samples and dozens of classes, especially since thresholds often need to be recalculated at every training epoch to monitor validation performance.
Methodology: Independent Optimization
To address the computational bottleneck of DP, we propose the Independent Optimization (IO) algorithm. The core innovation lies in the mathematical decomposition of the empirical risk. We demonstrate that the global optimization problem can be broken down into a sum of independent functions, one for each threshold.
Because these functions are independent, the optimal position for every threshold can be calculated simultaneously across multiple CPU or GPU cores. A critical concern with independent optimization is "threshold crossing," where the ordering of thresholds is violated (e.g., $t_2 < t_1$). We provide theoretical guarantees showing that if the task loss function is convex—as is the case with common metrics like Mean Absolute Error—the IO algorithm is guaranteed to produce thresholds in the correct order, matching the optimality of the slower DP method.
Experimental Evaluation
We evaluated the proposed algorithm on three large-scale facial age estimation datasets: MORPH-2 (55,013 images), CACD (159,402 images), and AFAD (164,418 images). We utilized ResNet18 and ResNet34 architectures to learn the initial 1DT before applying the thresholding algorithms.
Results and Performance Gains
The quantitative results highlight the efficiency of the parallel approach. As shown in the table below, the Parallel IO (PIO) algorithm consistently outperforms the traditional DP method across all datasets.
In the CACD dataset experiment, the traditional DP algorithm required approximately 186 minutes for threshold optimization. In contrast, the PIO algorithm completed the same task in just 24 minutes. When considering the entire learning pipeline—including neural network training, threshold optimization, and validation—the use of PIO reduced total computation time to roughly 60% of the DP-based baseline.
Conclusion
The Independent Optimization algorithm provides a robust and efficient alternative to sequential dynamic programming for ordinal regression. By leveraging the convexity of common loss functions, we enable massive parallelization without sacrificing theoretical optimality. While the current approach is limited to convex loss functions, it offers a significant practical speedup for modern large-scale deep learning tasks. Future work will explore extending these parallelization techniques to non-decomposable metrics like the Quadratic Weighted Kappa.
Summary updated