Pairwise learning problems with regularization networks and Nyström subsampling approach.

Area of Science:

• Machine Learning
• Computational Statistics

Background:

• Pairwise learning problems, including ranking and similarity learning, face scalability challenges in large datasets.
• Existing methods often struggle with high computational costs for large-scale pairwise data analysis.

Purpose of the Study:

• To develop a computationally efficient and flexible method for large-scale pairwise learning using kernel networks.
• To improve the theoretical performance guarantees of pairwise learning algorithms.

Main Methods:

• Integration of the Nyström sampling approach with coefficient-based regularized pairwise algorithms.
• Development of theorems to establish minimax error rates for the Nyström estimator.
• Derivation of the relationship between subsampling level and regularization parameter for optimal performance and efficiency.
• Application to bipartite ranking problems.

Main Results:

• The Nyström estimator achieves minimax error rates comparable to using the entire dataset, given adequate subsampling.
• The proposed method offers reduced computation costs and maintains asymptotic optimality.
• The algorithm demonstrates flexibility by not requiring symmetric or positive semi-definite kernels.
• State-of-the-art theoretical results are improved for bipartite ranking.

Conclusions:

• Nyström sampling provides an effective strategy for overcoming computational challenges in large-scale pairwise learning.
• The method enhances flexibility and adaptivity in kernel network applications.
• New mathematical tools, including probability inequalities for U-statistics on Hilbert-Schmidt operators, are introduced for pairwise learning analysis.