Why is a 0-1 loss function intractable? In Ian Goodfellow's Deep Learning book, it is written that 

Sometimes, the loss function we actually care about (say, classification error) is not one that can be optimized efficiently. For example, exactly minimizing expected 0-1 loss is typically intractable (exponential in the input dimension), even for a linear classifier. In such situations, one typically optimizes
  a surrogate loss function instead, which acts as a proxy but has advantages.

Why is 0-1 loss intractable, or how is it exponential in the input dimensions?
 A: The 0-1 loss function is non-convex and discontinuous, so (sub)gradient methods cannot be applied. For binary classification with a linear separator, this loss function can be formulated as finding the $\beta$ that minimizes the average value of the indicator function $\mathbf{1}(y_{i}\beta\mathbf{x}_{i} \leq 0)$ over all $i$ samples. This is exponential in the inputs, as since there are two possible values for each pair, there are $2^{n}$ possible configurations to check for $n$ total sample points. This is known to be NP-hard. Knowing the current value of your loss function doesn’t provide any clue as to how you should possibly modify your current solution to improve, as you could derive if gradient methods for convex or continuous functions were available.
A: The classification error is in fact sometimes tractable. It can be
optimized efficiently - though not exactly - using the Nelder-Mead
method, as shown in this article:
https://www.computer.org/csdl/trans/tp/1994/04/i0420-abs.html
"Dimension reduction is the process of transforming multidimensional
vectors into a low-dimensional space. In pattern recognition, it is
often desired that this task be performed without significant loss of
classification information. The Bayes error is an ideal criterion for
this purpose; however, it is known to be notoriously difficult for
mathematical treatment. Consequently, suboptimal criteria have been
used in practice. We propose an alternative criterion, based on the
estimate of the Bayes error, that is hopefully closer to the optimal
criterion than the criteria currently in use. An algorithm for linear
dimension reduction, based on this criterion, is conceived and
implemented. Experiments demonstrate its superior performance in
comparison with conventional algorithms."
The Bayes error mentioned here is basically the 0-1 loss.
This work was done in the context of linear dimension reduction. I
don't know how effective it would be for training deep learning
networks. But the point is, and the answer to the question: 0-1 loss
is not universally intractable. It can be optimized relatively well
for at least some types of models.
