Logarithmic loss minimization leads to well-behaved probabilistic outputs.

Hinge loss leads to some (not guaranteed) sparsity on the dual, but it doesn't help at probability estimation. Instead, it punishes misclassifications (that's why it's so useful to determine margins): diminishing hinge-loss comes with diminishing across margin misclassifications.

So, summarizing:

• Logarithmic loss ideally leads to better probability estimation at the cost of not actually optimizing for accuracy

• Hinge loss ideally leads to better accuracy and some sparsity at the cost of not actually estimating probabilities

In ideal scenarios, each respective method would excel in their domain (accuracy vs probability estimation). However, due to the No-Free-Lunch Theorem, it is not possible to know, a priori, if the model choice is optimal.

They are both discriminative models, yes. The logistic regression loss function is conceptually a function of all points. Correctly classified points add very little to the loss function, adding more if they are close to the boundary. The points near the boundary are therefore more important to the loss and therefore deciding how good the boundary is.

SVM uses a hinge loss, which conceptually puts the emphasis on the boundary points. Anything farther than the closest points contributes nothing to the loss because of the "hinge" (the max) in the function. Those closest points are the support vectors, simply. Therefore it actually reduces to picking a boundary that creates the largest margin -- distance to closest point. The theory is that the boundary case is all that really matters to generalization.

The downside is that hinge loss is not differentiable, but that just means it takes more math to discover how to optimize it via Lagrange multipliers. It doesn't really handle the case where data isn't linearly separable. Slack variables are a trick that lets this possibility be incorporated cleanly into the optimization problem.

You can use hinge loss with "deep learning", e.g. http://arxiv.org/pdf/1306.0239.pdf

Some of my thoughts, may not be correct though.

I understand the reason we have such design (for hinge and logistic loss) is we want the objective function to be convex.

Convexity is surely a nice property, but I think the most important reason is we want the objective function to have non-zero derivatives, so that we can make use of the derivatives to solve it. The objective function can be non-convex, in which case we often just stop at some local optima or saddle points.

and interestingly, it also penalize correctly classified instances if they are weakly classified. It is a really strange design.

I think such design sort of advises the model to not only make the right predictions, but also be confident about the predictions. If we don't want correctly classified instances to get punished, we can for example, move the hinge loss (blue) to the left by 1, so that they no longer get any loss. But I believe this often leads to worse result in practice.

what are the prices we need to pay by using different "proxy loss functions", such as hinge loss and logistic loss?

IMO by choosing different loss functions we are bringing different assumptions to the model. For example, the logistic regression loss (red) assumes a Bernoulli distribution, the MSE loss (green) assumes a Gaussian noise.

Following the least squares vs. logistic regression example in PRML, I added the hinge loss for comparison.

As shown in the figure, hinge loss and logistic regression / cross entropy / log-likelihood / softplus have very close results, because their objective functions are close (figure below), while MSE is generally more sensitive to outliers. Hinge loss does not always have a unique solution because it's not strictly convex.

However one important property of hinge loss is, data points far away from the decision boundary contribute nothing to the loss, the solution will be the same with those points removed.

The remaining points are called support vectors in the context of SVM. Whereas SVM uses a regularizer term to ensure the maximum margin property and a unique solution.