Towards A Deeper Geometric, Analytic and Algorithmic Understanding of Margins

Abstract

Given a matrix $A$, a linear feasibility problem (of which linear classification is a special case) aims to find a solution to a primal problem $w:A^{T}w>\text{0}$ or a certificate for the dual problem which is a probability distribution $p:Ap=\text{0}$. Inspired by the continued importance of "large-margin classifiers" in machine learning, this paper studies a condition measure of $A$ called its \textit{margin} that determines the difficulty of both the above problems. To aid geometrical intuition, we first establish new characterizations of the margin in terms of relevant balls, cones and hulls. Our second contribution is analytical, where we present generalizations of Gordan's theorem, and variants of Hoffman's theorems, both using margins. We end by proving some new results on a classical iterative scheme, the Perceptron, whose convergence rates famously depends on the margin. Our results are relevant for a deeper understanding of margin-based learning and proving convergence rates of iterative schemes, apart from providing a unifying perspective on this vast topic.

18 pages, 3 figures

References in corpus (2)

• On the Linear Convergence of the Alternating Direction Method of Multipliers
• Margins, Kernels and Non-linear Smoothed Perceptrons

Cited by in corpus (6)

• Gradient Descent Maximizes the Margin of Homogeneous Neural Networks
• Accelerated Sampling Kaczmarz Motzkin Algorithm for The Linear Feasibility Problem
• Heavy Ball Momentum Induced Sampling Kaczmarz Motzkin Methods for Linear Feasibility Problems
• An algorithm to compute the Hoffman constant of a system of linear constraints
• Sampling Kaczmarz Motzkin Method for Linear Feasibility Problems: Generalization & Acceleration
• Equivalence and invariance of the chi and Hoffman constants of a matrix