Incremental p-margin algorithm for classification with arbitrary norm

• We propose a novel algorithm for large p  -margin classification problems, for 1≤p≤∞1≤p≤∞.
• The approach is based on an unified perceptron-based formulation.
• Soft-margin in primal variables is introduced for non-linearly separable problems.
• An efficient incremental strategy is used to construct the large p-margin solution.

This paper presents a new algorithm to approximate large margin solutions in binary classification problems with arbitrary q-norm or p-margin, where p and q are Holder conjugates. We begin by presenting the online fixed p-margin perceptron algorithm (FMPp) that solves linearly separable classification problems in primal variables and consists of a generalization of the fixed margin perceptron algorithm (FMP). This algorithm is combined with an incremental margin strategy called IMAp, which computes an approximation of the maximal p-margin. To achieve this goal, IMAp executes FMPp several times with increasing p-margin values. One of the main advantages of this approach is its flexibility, which allows the use of different p-norms in the same primal formulation. For non-linearly separable problems, FMPp can be used with a soft margin in primal variables. The incremental learning strategy always guarantees a good approximation of the optimal p-margin and avoids the use of linear or higher order programming methods. IMAp was tested in different datasets obtaining similar results when compared to classical L1 and L∞L∞ linear programming formulations. Also, the algorithm was compared to ALMAp and presents superior results.