Is there a "binding" between loss functions and models? For me a model (the way we calculate an output given an input) and a loss function (the way we estimate the accuracy of a model) always were two different (independent, "orthogonal") things.  In other words, I though that any model can be trained and evaluated with any loss function.
However, it looks to me that there is some "binding" between models and loss functions.  For example here I see the following statement:

You can also create your own loss function. Some examples of existing
  losses are: LinearRegressionOutput, which computes the l2-loss between
  it’s input symbol and the labels provided to it; SoftmaxOutput, which
  computes the categorical cross-entropy.

So, it looks like softmax function is somehow "bound" with the "cross-entropy" and linear regression is bound to the l2-loss. But what does this binding mean? In what way are they bound? I thought that softmax is just a way to normalize output (so that all the values are forced to sum up to one, so that they can be interpreted as probabilities). Is it incorrect to measure accuracy of softmax using squared deviations? Or, alternatively, can't we measure accuracy of linear regression by something other that l2-loss?
 A: It may be important to define what a model is. For example the full model of linear regression is not just $Y=\beta X$ but:


*

*$Y=\beta X+\epsilon$

*$\epsilon$ has normal distribution with mean 0 and variance $\sigma$

*$X$ and $\epsilon$ are independent


This defines totally the distribution of $Y$ given $X$ and you can define the likelihood $p(y|x,\beta,\sigma)$ of a single line, and then the likelihood of the full training set: $L(\beta,\sigma)=\Pi_i p(y_i|x_i,\beta,\sigma)$
There is special loss function derived from the likelihood $L$. It is simply $-\log(L)$. For linear regression this loss function happens to be OLS (modulo a few constants you don't care about and where $\sigma$ disappears magically). As a consequence, maximizing the likelihood for linear regression is the same as minimizing OLS.
In most models where $Y$ depends on $X$, a fully specified model is the distribution of $Y$ given $X$ (and a parameter). Thus every model has a likelihood. There is always a "canonical" way to create a loss function from a model: $-\log(L)$ (or any decreasing function instead of $-\log$ which does not change the solution of the minimization problem).
A very common way to fit models is to use maximum likelihood, hence implicitly minimize this loss function. It is called maximum likelihood estimation (MLE). Logistic regression is most often fitted with MLE. More generally, generalized linear models are fitted with MLE. Same for Gaussian mixtures... 
But it is not the only way to do. If you think MLE is canonical, then yes, models come with a canonical loss function. But sometimes MLE is not used and another loss function can be used.
