Complexity of zero-one loss vs logistic loss functions

Question

In Machine Learning: The Basics, Alexander Jung, Spinger, the author states that using the zero-one loss function defined by:$$\mathit{L}((\mathbf{x}, y), h)= \begin{cases} 1, y \ne \hat{y}\\ 0\ otherwise, \end{cases}\\ (with\ \hat{y}=1\ for\ h(\mathbf{x}) \ge 0, and\ \hat{y} = −1 \ for \ h(\mathbf{x})\lt0). $$

results in computationally challenging problems and the logistic loss is a computationally attractive alternative.

However, consider(ing) that the logistic function defined as follows:

$$L((\mathbf{x}, y), h) := log(1 + exp(−yh(\mathbf{x}))),$$

I don't see any "disadvantages" of the zero-one loss in terms of computational efficiency. To my understanding, for each training example (or instance), the zero-one loss function needs only 2 operations (1 comparison and 1 assignment) and it's done. Meanwhile with the logistic loss, it's a bunch of operations (1 multiplication and exponentiate with base e and then 1 addition, and taking log). And not only the number of operations is larger the complexity of those operations is also higher.

Can someone help to point out what I'm missing here?

Answer 1

Training is a crucial step of machine learning, where You take Your model (hypothesis) and find values for its parameters such that it fits Your training data well enough. The error between model and data is measured by a loss function. Training boils down to minimizing the loss function with respect to the parameters. It is a mathematical optimization problem.

The most efficient optimization algorithms are all gradient-based. The gradient of the zero-one loss function (w.r.t. its parameters) is zero for almost all inputs, making it useless for gradient-based optimization. The logistic loss function, on the other hand, is continuously differentiable and very well suited for gradient-based optimization.

You are absolutely right that the logistic function is computationally more expensive, but gradient-based optimization (usually) requires much fewer iterations than any evolutionary algorithm, which makes training with the logistic loss function faster in the end.