Relationship between L1 penalty and margin in SVM

Question

Expanding on "Why aren't there there two regularization terms in SVC?" and "Meaning of penalty and loss in LinearSVM":

It appears that LinearSVC in Python also supports $l_1$ regularisation ("penalty") of the class boundary vector $\mathbf{w}$, in addition to the usual $l_2$ regularisation. The documentation claims (and it is in line with what we know about LASSO) that $l_1$ regularisation leads to a sparse vector of coefficients. But I wonder what effect does it have on the margin and on the generalisation properties of the classifier. I'd appreciate links to publications discussing this question.

Also, is there a deep, mathematical reason why LinearSVC wouldn't support the combination of penalty='l2' and loss='hinge' (the standard combination in SVC) when dual=False (i.e. when optimising the primal), or is it simply a design choice by the authors?

Answer 1

Addressing only the following, as an extended comment:

The documentation claims (and it is in line with what we know about LASSO) that $l_1$ regularisation leads to a sparse vector of coefficients. But I wonder what effect does it have on the margin and on the generalisation properties of the classifier. I'd appreciate links to publications discussing this question.

Where I'd start looking would be some book length specialist treatments of support vector machines. That is,

Cristianini, N., Shawe-Taylor, J. (2000). An Introduction to Support Vector Machines and Other Kernel Based Learning Methods. Cambridge University Press.

Steinwart, I., Christmann, A. (2008). Support Vector Machines. Springer.

A search for "1-norm" in the former reveals the following attribution on p91:

Mangasarian's early work mainly focused on minimising the 1-norm of the solution $\mathbf{w}$.

SVMs with $l_1$ regularisation have also been referred to as linear programming support vector machines, and are incidentally treated as part of a broader generalisation of support vector machines in:

Mangasarian, O. (1999). Generalized support vector machines. In AJ. Smola, P. Bartlett, B. Schölkopf, and C. Schuurmans (eds.) Advances in Large Margin Classifiers. MIT Press.

The above seems to be corroborated in the reference below. References to works related to theoretical study of, and generalisation error bounds on $L_1$ norm SVMs are given in this more recent reference:

Peng, B. Wang, L, Wu, Y. (2016). An error bound for $L_1$-norm support vector machine coefficients in ultra-high dimensions. Journal of Machine Learning Research 17: 1-26. http://users.stat.umn.edu/~wangx346/research/SVM_bound.pdf

In particular, there are a plethora of further references in the introduction of the above.