Suppose I am doing multi-class classification (for example on MNIST), but I only give a single labeled example of each class. So like the training set has only a single 0, a single 1, a single 2, and so on, and then I examine accuracy on a held-out test set. I assume it wouldn't do very well. But is this even possible? I know this wouldn't be so useful, but I'm just interested in what's happening behind the scenes when I do this. I know that many algorithms can do one-shot learning, but I've never heard of SVM doing this, and can't find much on what would be actually happening if you did this. I also know about Exemplar-SVMs, which seem similar in principle but still aren't really what I'm talking about. Any help?
SVMs 's separate classes by a hyperplane, which is a form of clustering. Given a single example, each digit will likely reside somewhere near the cluster centroid for the class.
Therefore, as mentioned in the comments, a single example should still learn better than random.
SVMs learn classification by defining a hyperplane using whatever kernel you are using (the case that is easiest to understand is a linear kernel where the hyperplane is just a linear plane).
To visualize what would happen, you can take a look at the image below (for the simple example with only two classes and two predictor dimensions x and y) and imagine that you only have the observations with the red arrow pointing at them. You can see how SVM can still find a hyperplane (in this case, a line) to separate the two classes.
Yes, this is possible. Assuming your data is not degenerate and you have enough input variables (or a suitable kernel), your data will be separable and the SVM will be a hard-margin solution. In this case the separating hyperplane lies exactly between pairs of observations (in kernel space). In fact, each of your observations will necessarily be a support vector, and since you know what the support vectors are, you can find the weights simply by solving a linear system. This follows directly from the KKT conditions of the primal problem.
Whether this yields something better than random depends on the amount of noise in your data. If labels are 95% random, a single observation does not add a lot of information to your model, and most such "single shot" SVMs will split out wrong labels. However, in ML it is common to assume that the labels are near to noise-free, and then you are likely (but not guaranteed) to perform better than random.