L$^3$-SVMs: Landmarks-based Linear Local Support Vectors Machines

One of the most famous and commonly used Machine Learning techniques for classification are the Support Vector Machines (SVMs) [7]. This popularity is due to their robustness, simplicity, efficiency (even in non linear scenarios by means of the kernel trick) as well as their theoretical foundations via generalization guarantees. Despite those nice properties, SVMs may face some drawbacks: Kernel SVMs are known to be expensive in terms of time complexity and memory usage when the number of training examples is large, both at training and at testing time. For training, the full Gram matrix needs to be evaluated (i.e., compute and store all pairwise training sample similarities), and then inverted. For testing, the time complexity depends on the number of support vectors which typically grows linearly with the number of training instances [21].