How are the various guarantees provided to SVMs by Statistical Learning Theory affected by the Kernel Function I never studied the field in depth, but I am very aware that state of the art performance in most ML tasks is now achieved by various flavors of neural networks.  At the same time, Vladimir Vapnik, the co-founder Statistical Learning Theory (SLT), and the co-inventor of SVMs is continuing to play around with various marginal improvements to SVMs, such a privileged information (https://www.youtube.com/watch?v=5mvfpSdWsOo) or using location information (https://www.youtube.com/watch?v=LEYglsxKclo). In this interview he seems explicitly hostile to deep learning, claiming that the problems it might be solving are actually easy (https://www.youtube.com/watch?v=STFcvzoxVw4#t=23m39s). To my untrained eye, the biggest benefit of NNs is that they produce their own kernels from the ground up, which in the SVM framework have to be designed by hand. In some sense, SVMs push the task of intelligence once step back, to the problem of kernel design.
Which brings me to my question: How are the guarantees of SLT dependent on the kernels? Obviously the right kernel can transform a problem from one requiring slack variables to one lacking them, but if theory itself cannot provide rigorous and mechanical method of producing kernels, then it seems SLT is severely incomplete as a theory of inference. Am I misunderstanding something?
 A: Some thoughts on your interesting question:
Good features are problem dependent. So seems difficult (if possible) to incorporate feature engineering into any rigorous mathematical framework.
To me, pushing the problem of finding good features to finding good kernels is a way to separate the problem in two parts.
First, the mathematics (learning from good/noisy features), and second, the practical nature of your data (finding features from your observations - sometimes using an arbitrary off-the-shelf mapping, but sometimes using your knowledge and understanding of how the data was generated).
It is indeed very nice that neural networks can find their own feature mappings. However this is an empirical observation, it is not the case that we mathematically understand how or why these features should be good.
You may call SLT "severely incomplete as a theory of inference", but our understanding of why neural networks should work is even more incomplete.
Finally, as you stated, the state of the art results are achieved by using various different architectures for neural networks.
While some neural networks achieve stellar performance, others perform poorly on the same datasets.
So, to me, the situation for SVM ad neural networks is similar: your performance will be strongly influenced by the choice of kernel or the network.
However if you go for SVM, then at least we can mathematically understand something - the "learning" step ;-)
A: A lot of the theoretical underpinnings of the SVM are based on the linear maximum margin classifier.  However, the advantage of a kernel is that the SVM can be viewed as a linear maximum margin classifier that is constructed in a feature space that is implicitly defined by the kernel.  As imposing a fixed kernel is equivalent to a fixed transformation of the data, which is equivalent to just solving some other fixed classification problem.  This means that any theory that holds for a linear classifier also holds for a fixed kernel.
However, in most practical cases, we don't use a fixed kernel.  In general, the kernel has some hyper-parameters that we also learn from the data, e.g. via cross-validation.  As soon as we tune the kernel parameters, we have immediately invalidated a lot of the theory on which it is based.  Theoretical results become much harder to obtain as soon as you include
learning the kernel.
Having said which (IMHO) the main reason that the SVM works so well is that it really encourages us to think about regularisation and doing something (SRM) about over-fitting.  That doesn't really rely too heavily on the theoretical justification.
