Are loss functions necessarily additive in observations? In all of the contexts I've seen loss functions in statistics/machine learning so far, loss functions are additive in observations. i.e.: loss $Q_D$ of dataset $D$ is an additive aggregation of losses at observations $i\in D$: $Q_D(\beta)=\sum_{i\in D}Q_i(\beta)$. e.g. in the loss that is a simple sum of squared residuals: $Q_D=\sum_i(y_i-X_i\beta)^2$.
This seems sensible, but I am wondering: Are there contexts in statistics/machine learning in which it happens (or reasons in theory why one might want) that a loss function is used that is not additive (or even separable) in observations?
 A: Loss functions are not always additive in observations: A loss function is function of an estimator (or predictor) and the thing it is estimating (predicting).  The loss function is often, but not always, a distance function.  Moreover, the estimator (predictor) sometimes, but not always, involves a sum of terms involving a single observation.  Generally speaking, the loss function does not always have a form that is additive with respect to the observations.  For prediction problems, deviation from this form occurs because of the form of the loss function.  For estimation problems, it occurs either because of the form of the loss function, or because of the form of the estimator appearing in the loss function.
To see the generality of the loss form for a prediction problem, consider the general case where we have an observed data $\mathbf{y} = (y_1,...,y_n)$ and we want to predict the observable vector $\mathbf{y}_* = (y_{n+1},...,y_{n+k})$ using the predictor $\hat{\mathbf{y}}_* = \mathbf{H}(\mathbf{y})$.  We can write the loss for this prediction problem as:
$$L(\hat{\mathbf{y}}_*, \mathbf{y}_*) = L(\mathbf{H}(\mathbf{y}), \mathbf{y}_*).$$
The loss function in your question is the Euclidean distance between the prediction vector and the observed data vector, which is $L(\hat{\mathbf{y}}_*, \mathbf{y}_*) = ||\hat{\mathbf{y}}_* - \mathbf{y}_*||^2 = \sum_i (\hat{y}_{*i} - y_{*i})^2$.  That particular form is composed of a sum of terms involving the observed values being predicted, and so the additivity property holds in that case.  However, there are many other examples of loss functions that give rise to a form that does not have this additivity property. 
A simple example of two loss functions that are not additive in the observations are when the loss is equal to the prediction error either from the best prediction, or from the worst prediction.  In the case of "loss from best prediction" we have the loss function $L(\hat{\mathbf{y}}_*, \mathbf{y}_*) = \min_i |\hat{y}_{*i} - y_{*i}|$, and in "loss from worse prediction" we have the loss function $L(\hat{\mathbf{y}}_*, \mathbf{y}_*) = \max_i |\hat{y}_{*i} - y_{*i}|$.  In either case, the loss function is not additive for the individual terms.
A: There are two most common causes for loss function being a sum/average.
First, you may simply define your loss as average of some metric. It's related to concept of risk minimization.
Second reason is that you use Maximum Likelihood or something related, like Maximum A Posteriori. Additivity comes from the fact that Maximum Likelihood solves
$$\arg\max_{\theta} P_{\theta}(Dataset) = \arg\max_{\theta} \prod_{x \in Dataset} P_{\theta}(x)$$
which is equal to $$\arg\min_{\theta} \sum_{x \in Dataset} -log(P_{\theta}(x)).$$
For example, if $P_{\theta}$ is Gaussian you'll get exactly mean squared error.
