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^Tw > 0$ or a certificate for the dual problem which is a probability distribution $p: Ap = 0$. Inspired by the continued importance of large margin classifiers in machine learning, this paper aims to deepen our understanding of a condition measure of $A$ called \textit{margin} that determines the difficulty of both the above problems. To aid geometrical intuition, we establish new characterizations of the margin in terms of relevant balls, cones and hulls. Our main contribution is analytical, where we present generalizations of Gordan's theorem, and beautiful variants of Hoffman's theorems, both using margins. We end with shedding some new light on two classical iterative schemes, the Perceptron and Von-Neumann or Gilbert algorithms, whose convergence rates famously depend 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.

论文研究的是使用余量来评估矩阵A的特定条件，并探索了在机器学习中具有重要意义的大余量分类器的新特性。

探索间隔的更深层次几何，分析和算法理解