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:
"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.