Are there any supervised learning methods that do NOT boil down to optimizing a loss function? All of supervised learning methods I can think of amount to optimizing a loss function (RMSE, AIC, Cross-Entropy,...) against a labeled data set. One would think that "learning = optimizing loss functions". 
Are there any learning methods that don't amount to an optimization problem? 
 A: In the dark ages before statistical methods were in widespread use, qualitative assessments and expert judgements were the only source of the kinds of risk assessment that supervised learning provided. Indeed, the "supervised learning" process was not a metaphor for optimization but the core task of the analyst: become familiar with the subject, learn from history and experiments where possible, and make reasoned analysis.
A: In one sense, the answer is tautologically "no". This is because the point of supervised methods is to have optimal predictions, so they are all an attempt to minimize a predictive loss function.
However, not all methods are using optimization routines (i.e., L-BFGS, gradient descent, etc.) to achieve this. The most striking example is Bayesian methods, in which integration, rather than optimization, is used to make inference. Other examples are anything in which the solution is in closed form; linear regression and random forests are two such examples. 
A: Estimating equations solve systems of linear equations. While, you could take the antiderivative of the estimating function and say that's a loss function, they're not entirely theoretically or practically equivalent.
$$ 0 = \sum_{i=1}^n w_i (\theta X_i - Y_i))$$
For instance, it's true OLS minimizes $$\sum_{i=1}^n (Y_i - \beta \mathbf{X}_i)^2$$
But it also solves: $$ 0 = (\mathbf{X}^T\mathbf{X}^{-1})\mathbf{X}^T(Y - \mathbf{X}\beta)$$ and it turns out this gives us a nice interpretation of the regression coefficient.
Also Bayesian methods update subjective evidence with data. This also has some ties to optimization routines, but like EEs that is not theoretically or practically equivalent.
