Improved Classification Rates for Localized Algorithms under Margin Conditions

Description

Support vector machines (SVMs) are one of the most successful algorithms on small and medium-sized data sets, but on large-scale data sets their training and predictions become computationally infeasible. The author considers a spatially defined data chunking method for large-scale learning problems, leading to so-called localized SVMs, and implements an in-depth mathematical analysis with theoretical guarantees, which in particular include classification rates. The statistical analysis relies on a new and simple partitioning based technique and takes well-known margin conditions into account that describe the behavior of the data-generating distribution. It turns out that the rates outperform known rates of several other learning algorithms under suitable sets of assumptions. From a practical point of view, the author shows that a common training and validation procedure achieves the theoretical rates adaptively, that is, without knowing the margin parameters in advance. Danksagung Contents Abbreviations List of Figures Summary Kurzfassung 1. Introduction 2. Preliminaries 2.1. Introduction to Statistical Learning Theory 2.1.1. Losses and Risks 2.1.2. Learning Methods 2.2. From Global to Localized SVMs 2.2.1. Kernels and RKHSs 2.2.2. The Localized SVM Approach 2.3. Advanced Statistical Analysis 2.3.1. Margin Conditions 2.3.2. General Oracle Inequalities 3. Histogram Rule: Oracle Inequality and Learning Rates 3.1. Motivation 3.2. Statistical Refinement and Main Results 3.3. Comparison of Learning Rates 4. Localized SVMs: Oracle Inequalities and Learning Rates 4.1. Motivation 4.2. Local Statistical Analysis 4.2.1. Approximation Error Bounds 4.2.2. Entropy Bounds 4.2.3. Oracle Inequalities and Learning Rates 4.3. Main Results 4.3.1. Global Learning Rates 4.3.2. Adaptivity 4.4. Comparison of Learning Rates 5. Discussion A. Appendix Bibliography