Scalable Kernel Ordinal Regression via Doubly Stochastic Gradients.

Area of Science:

• Machine Learning
• Statistical Modeling

Background:

• Ordinal regression (OR) is a key machine learning task for ordered outcomes.
• Kernel methods enable nonlinear OR but face efficiency challenges with multiple thresholds and high computational costs.
• Existing doubly stochastic gradient (DSG) algorithms are efficient but limited to single reproducing kernel Hilbert spaces (RKHS).

Purpose of the Study:

• To develop an efficient and scalable kernel learning algorithm for ordinal regression problems with multiple thresholds.
• To address the limitations of existing DSG algorithms in handling multiple RKHSs inherent in OR.

Main Methods:

• Constructed a novel kernel whose RKHS accommodates decision functions with multiple thresholds.
• Proposed a new DSG-like algorithm, DSGOR, which updates decision functionals and biases iteratively with tailored learning rates.
• Theoretically analyzed DSGOR to establish an O(1/t) convergence rate.

Main Results:

• DSGOR achieves a convergence rate of O(1/t), comparable to DSG, despite addressing a more complex problem.
• The algorithm demonstrates significantly higher efficiency compared to traditional kernel OR solvers, particularly on large-scale datasets.
• Experimental results validate the effectiveness and scalability of the proposed DSGOR algorithm.

Conclusions:

• DSGOR offers an efficient and scalable solution for kernel-based ordinal regression with multiple thresholds.
• The novel kernel construction and iterative update strategy overcome the limitations of previous DSG methods.
• DSGOR represents a significant advancement for tackling complex, large-scale ordinal regression tasks in machine learning.