How do ensemble methods outperform all their constituents? I am a bit confused about ensemble learning. In a nutshell, it runs k models and gets the average of these k models. How can it be guaranteed that the average of the k models would be better than any of the models by themselves? I do understand that the bias is "spread out" or "averaged". However, what if there are two models in the ensemble (i.e. k = 2) and one of the is worse than the other - wouldn't the ensemble be worse than the better model?
 A: In your example, your ensemble of two models could be worse than a single model itself. But your example is artificial, we generally build more than two in our ensemble. 
There is no absolute guarantee a ensemble model performs better than an individual model, but if you build many of those, and your individual classifier is weak. Your overall performance should be better than an individual model.
In machine learning, training multiple models generally outperform training a single model. That's because you have more parameters to tune.
A: It's not guaranteed. As you say, the ensemble could be worse than the individual models. For example, taking the average of the true model and a bad model would give a fairly bad model.
The average of $k$ models is only going to be an improvement if the models are (somewhat) independent of one another. For example, in bagging, each model is built from a random subset of the data, so some independence is built in. Or models could be built using different combinations of features, and then combined by averaging.
Also, model averaging only works well when the individual models have high variance. That's why a random forest is built using very large trees. On the other hand, averaging a bunch of linear regression models still gives you a linear model, which isn't likely to be better than the models you started with (try it!)
Other ensemble methods, such as boosting and blending, work by taking the outputs from individual models, together with the training data, as inputs to a bigger model. In this case, it's not surprising that they often work better than the individual models, since they are in fact more complicated, and they still use the training data.
A: I just want to throw something that is seldom discussed in this context, and it should give you food for thought.
Ensemble also works with humans!
It has been observed that averaging human predictions gives better predictions than any individual prediction. This is known as the wisdom of the crowd.
Now, you could argue that it is because some people have different information, so you are effectively averaging information. But no, this is true even for tasks such as guessing the number of beans in a jar.
There are plenty of books and experiments written on this, and the phenomenon still puzzles researchers.
This being said, as @Flounderer pointed out, the real gains come from so-called unstable models such as decisions trees, where each observation usually has an impact on the decision boundary. More stable ones like SVMs do not gain as much because resampling usually does not affect support vectors much.
A: It is actually quite possible for single models to be better than ensembles.
Even if there are no points in your data where some of your models are overestimating and some are underestimating (in that case you might hope that average error would be negated), some of the most popular loss functions (like mean squared loss) are penalizing single big deviations more than some number of moderate deviations. If models you are averaging are somewhat different you might hope that variance becomes "less" as average kills outstanding deviations. Probably it is explainable with that.
A: Yes, it might be the case but the idea for ensembling is to train simpler models to avoid over fitting while capturing different characteristics of data from different ensembles. Of course there is no guarantee of an ensemble model to outperform a single model while trained with same training data. 
The outperformance can be gained by combining ensemble models and boosting(e.g. AdaBoost). By boosting you train each next ensemle model by assigning weights on each data point and updating them according to error. So think of it as a coordinate descent algorithm, it allows the training error to go down with each iteration while maintaining a constant average model complexity. In overall this makes an impact on the performance. There are many
