Online Pairwise Learning Algorithms.

Area of Science:

• Machine Learning
• Optimization Theory
• Reproducing Kernel Hilbert Spaces (RKHS)

Background:

• Pairwise learning tasks, including bipartite ranking, metric learning, and AUC maximization, typically utilize loss functions dependent on example pairs.
• Existing online algorithms for pairwise learning often impose constraints on bounded domains or require strongly convex loss functions.
• The unconstrained setting in reproducing kernel Hilbert spaces (RKHS) presents challenges for developing robust online learning algorithms.

Purpose of the Study:

• To develop and analyze an online algorithm for pairwise learning with a least-square loss function in an unconstrained RKHS setting.
• To address limitations of existing methods by removing the need for bounded domains or strongly convex objectives.
• To establish theoretical guarantees for the convergence of the proposed algorithm.

Main Methods:

• Introduction of the Online Pairwise lEaRning Algorithm (OPERA) for unconstrained pairwise learning.
• Characterization of RKHS using associated integral operators and probability inequalities for Hilbert space-valued random variables.
• Derivation of convergence rates under polynomially decaying step sizes.

Main Results:

• Establishment of a general theorem guaranteeing almost sure convergence for the last iterate of OPERA without distribution assumptions.
• Derivation of explicit convergence rates contingent on polynomially decaying step sizes.
• Identification of a useful property for commonly used kernels in pairwise learning settings.

Conclusions:

• OPERA provides a theoretically sound and effective method for online pairwise learning in unconstrained RKHS.
• The algorithm overcomes limitations of prior work by handling non-strongly convex objectives and unconstrained domains.
• The findings contribute to the theoretical understanding of online learning algorithms within RKHS.