Implicit Annealing in Kernel Spaces: A Strongly Consistent Clustering Approach.

Area of Science:

• Machine Learning
• Data Mining
• Computational Statistics

Background:

• Kernel k-means clustering is effective for unsupervised learning on non-linearly separable data.
• A key challenge is the tendency of these algorithms to converge to local minima due to non-convex objective functions.

Purpose of the Study:

• To generalize existing methods using a family of means to address local minima in kernel and multi-kernel settings.
• To introduce Kernel Power k-Means, an algorithm designed to more effectively solve non-convex clustering problems.

Main Methods:

• Utilizes majorization-minimization (MM) for solving the non-convex optimization problem.
• Implicitly performs annealing in kernel feature space with efficient, closed-form updates.
• Employs modern learning theory tools to analyze convergence and statistical properties.

Main Results:

• Rigorously characterizes computational and statistical convergence properties.
• Establishes strong consistency guarantees for large sample behavior.
• Provides finite-sample bounds on excess risk, demonstrating efficacy on simulated and real data.

Conclusions:

• Kernel Power k-Means offers a robust approach to kernel clustering, overcoming local minima issues.
• The method demonstrates strong theoretical guarantees and practical effectiveness in diverse experimental settings.