Improved Classification Rates for Localized Algorithms under Margin Conditions

1. Front Matter

   Pages I-XV

   PDF

2. Introduction

   • Ingrid Karin Blaschzyk

   Pages 1-4

3. Preliminaries

   • Ingrid Karin Blaschzyk

   Pages 5-34

4. Histogram Rule: Oracle Inequality and Learning Rates

   • Ingrid Karin Blaschzyk

   Pages 35-57

5. Localized SVMs: Oracle Inequalities and Learning Rates

   • Ingrid Karin Blaschzyk

   Pages 59-113

6. Discussion

   • Ingrid Karin Blaschzyk

   Pages 115-116

7. Back Matter

   Pages 117-126

   PDF

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.

• Classification
• Learning Rates
• Gaussian Kernel
• Tsybakov Noise
• Localized SVMs
• Support Vector Machines (SVMs)
• Hinge Loss
• Spatial Decomposition
• Histogram Rule
• Oracle Inequality

• Stuttgart, Germany

  Ingrid Karin Blaschzyk

Ingrid Karin Blaschzyk is a postdoctoral researcher in the Department of Mathematics at the University of Stuttgart, Germany.​

Policies and ethics