A new incremental learning algorithm is described which 
approximates the maximal margin hyperplane w.r.t. norm p >= 2 for 
a set of linearly separable data.
Our algorithm, called Alma_p (Approximate Large Margin algorithm w.r.t. norm p),
takes $O( (p-1) / (a^2 g^2 ) )
corrections to separate the data with p-norm margin larger than (1-a)g,
where g is the (normalized) p-norm margin of the data.
Alma_p avoids quadratic (or higher-order) programming methods. It is
very easy to implement and is as fast as on-line algorithms, such as
Rosenblatt's Perceptron algorithm.
We performed extensive experiments on both real-world and artificial datasets.
We compared Alma_2 (i.e., Alma_p with p = 2) to standard 
Support vector Machines (SVM) and to 
two incremental algorithms: the Perceptron algorithm and Li and Long's ROMMA.
The accuracy levels achieved by Alma_2 are superior to those
achieved by the Perceptron algorithm and ROMMA, but slightly inferior to 
SVM's. On the other hand, Alma_2 is quite faster and easier 
to implement than standard SVM training algorithms.
When learning sparse target vectors, Alma_p with $p > 2$ largely 
outperforms Perceptron-like algorithms, such as Alma_2.