> The naive approach (start at a "random" weight setting, use gradient descent) that works on a convex error surface fails catastrophically on deep, complex neural nets. (Shallow neural net training is a non-convex problem as well, but seems to be "less non-convex" in practice.)
Starting at a random (no scare quotes needed) point in weight space and SGD'ing is exactly what Alex Krizhevsky, and all of the derivative convnets over the last two years, did and do. It works just fine; I sit at work doing it all day long. You need to have enough data to train on, big enough models, and enough flops to train the big models on the big data before your interns' grandchildren die. We have all of the above now. Aside: even single-layer neural networks do not have convex error surfaces; convexity, and funky error surface geometry, is not a relevant distinction between shallow and deep nets. There have been no magical optimization breakthroughs, it's still SGD with the same herbs and spices that were used in the 90's (momentum, e.g.).
> The problem is that convergence, for single-layer nets, can be very slow (especially given that you're often doing stochastic gradient descent when working large data sets).
"Stochastic" gradient descent just means doing lots of weight updates per epoch. Ceteris paribus, training on large, redundant data sets, stochastic converges faster than batch because it gets to consider more points in the weight space than batch per pass over the data. The problem with single-layer neural nets is not that they converge slowly; the problem is that the layer size needs to grow exponentially with the task size. Single-layer neural nets' universal approximation power is thus not of great practical consequence. The power of deep nets is the power of composition: f(g(h(x))) is a strictly more powerful model than f(x) holding the number of parameters constant.
> Even now, making deep neural nets not sensitive to initial starting conditions is an unsolved problem, but there's been a lot of progress.
You just initialize with a Gaussian ball around zero and explore whatever valley in the error surface you happen to be in. Works 100% dandy.
> I would hazard the guess that the convolutional technique is a lot more useful in deep neural networks than it is in single-hidden-layer neural nets.
It doesn't really make sense to talk about a "single layer convolutional net", because if you only have a single layer, and all you can do is convolve with it, then the output of your net will necessarily be a big pile of filtered versions of the input image. Unless your task is specifically to learn a target set of filters, it would make no sense to have a single layer convnet.