Bregman divergences and surrogates for learning.

Area of Science:

• Machine Learning
• Computational Statistics

Background:

• Classification calibration is a key condition for surrogate functions, linking their minimization to classification risk.
• Algorithmic challenges in minimizing these surrogates remain an open problem.

Purpose of the Study:

• To address the algorithmic minimization of classification calibrated surrogates intersecting with Murata et al.'s (2004) work.
• To provide a unified algorithmic framework for a broad set of surrogates satisfying common assumptions.

Main Methods:

• Derived equivalent expressions for convex and concave surrogates used in linear separators and decision trees.
• Developed novel minimization algorithms for these surrogates, proving their convergence properties.

Main Results:

• Identified a unified "master" algorithm underlying seemingly different minimization approaches.
• Demonstrated that these algorithms encompass popular methods like additive regression and decision tree induction (CART, C4.5).
• Showcased that the induction process exhibits boosting features irrespective of the specific surrogate used.

Conclusions:

• The research offers a unified perspective on surrogate minimization algorithms in machine learning.
• The developed algorithms provide provable convergence guarantees for a wide range of classifiers.
• Experimental validation on 40 domains supports the practical utility and broad applicability of the findings.