TBH I never found the claim that the kernel trick is all about efficiency compelling. Learning is costly in num examples, not num dims.