Does zero-one loss correspond to any maximum likelihood procedure? Squared loss for linear regression corresponds to a MLE of a Gaussian model, and cross entropy loss corresponds to MLE of a logistic model with discrete probabilities. 

Can zero-one loss be justified by MLE of any probability model? Why or why not? 

That's the main question. This question also has to do with intuition for zero-one loss, but doesn't have anything to do with MLE.  but also I'd like to state some things I believe are true about zero-one loss, and please correct me if I'm wrong:


*

*MAP is Bayes optimal for zero-one loss 

*Logistic regression models probabilities directly, and classifies to the largest, but its parameters are optimized based on maximum likelihood (leading to cross-entropy) rather than optimizing zero-one loss directly

*The performance of logistic regression could be improved by using zero-one loss, or you could ditch logistic regression entirely and use frequency tables to approximate $P(\text{class} | X)$, though both of these options are entirely intractable

 A: Minimizing the zero-one loss
$$
L(\theta, \widehat{\theta})
= 1 - \mathbf{1}_{\{\theta\}}(\widehat{\theta})
= \begin{cases}
0 & \text{if $\theta = \widehat{\theta}$} \\
1 & \text{otherwise}
\end{cases}
$$
is the same as maximum likelihood estimation with a family of Dirac distributions: discrete distributions with probability mass function
$$
p(x \mid \theta)
= \mathbf{1}_{\{\theta\}}(x)
= \begin{cases}
1 & \text{if $x = \theta$} \\
0 & \text{otherwise.}
\end{cases}
$$
Here $\mathbf{1}_A$ denotes the indicator function of a set $A$.

Regarding your beliefs about zero-one loss:

MAP is Bayes optimal for zero-one loss

Consider a parametric family of distributions $\{P_\theta : \theta \in \Omega\}$ and a prior $\pi$.
The risk of any estimator $\widehat{\theta}$ of $\theta$ is
$$
\begin{aligned}
R(\theta, \widehat{\theta})
&= E_\theta[L(\theta, \widehat{\theta})] \\
&= E_\theta[1 - \mathbf{1}_{\{\theta\}}(\widehat{\theta})] \\
&= P_\theta(\widehat{\theta} \neq \theta),
\end{aligned}
$$
and so the Bayes risk is
$$
\begin{aligned}
R_\pi(\widehat{\theta})
&= \int_\Omega R(\theta, \widehat{\theta}) \, d\pi(\theta) \\
&= \int_\Omega P_\theta(\widehat{\theta} \neq \theta) \, d\pi(\theta).
\end{aligned}
$$
A priori it is not clear to me why a MAP estimator $\widehat{\theta}$ would minimize this Bayes risk in this general setup.

Logistic regression models probabilities directly, and classifies to the largest, but its parameters are optimized based on maximum likelihood (leading to cross-entropy) rather than optimizing zero-one loss directly

This is correct.

The performance of logistic regression could be improved by using zero-one loss, or you could ditch logistic regression entirely and use frequency tables to approximate P(class|X), though both of these options are entirely intractable

Zero-one loss is not differentiable and not convex, so the tradiitonal optimization methods used to train models like logistic regression don't apply to it.
The problem with frequency tables is that as soon as you have a point X that isn't in the training data, you can't make any inference about P(class|X) as you would like.
A: In general surrogate losses used in place of 0-1 loss are chosen to be Fisher consistent. There are established results regarding this matter:
http://statistics.berkeley.edu/sites/default/files/tech-reports/638.pdf
This means that optimization using the surrogate loss will yield the model that will also minimize the expected 0-1 loss.
