Greedy Convex Ensemble
  We consider learning a convex combination of basis models, and present some
new theoretical and empirical results that demonstrate the effectiveness of a
greedy approach. Theoretically, we first consider whether we can use linear,
instead of convex, combinations, and obtain generalization results similar to
existing ones for learning from a convex hull. We obtain a negative result that
even the linear hull of very simple basis functions can have unbounded
capacity, and is thus prone to overfitting; on the other hand, convex hulls are
still rich but have bounded capacities. Secondly, we obtain a generalization
bound for a general class of Lipschitz loss functions. Empirically, we first
discuss how a convex combination can be greedily learned with early stopping,
and how a convex combination can be non-greedily learned when the number of
basis models is known a priori. Our experiments suggest that the greedy scheme
is competitive with or better than several baselines, including boosting and
random forests. The greedy algorithm requires little effort in hyper-parameter
tuning, and also seems able to adapt to the underlying complexity of the
problem. Our code is available at https://github.com/tan1889/gce.
