Non-rigid registration of 3D facial surfaces is a crucial step in a variety of applications. Outliers, i.e., features in a facial surface that are not present in the reference face, often perturb the registration process. In this paper, we present a novel method which registers facial surfaces reliably also in the presence of huge outlier regions. A cost function incorporating several channels (red, green, blue, etc.) is proposed. The weight of each point of the facial surface in the cost function is controlled by a weight map, which is learned iteratively. Ideally, outliers will get a zero weight so that their disturbing effect is decreased. Results show that with an intelligent initialization the weight map improves the registration results considerably.