Smoothness assumption

Let's consider a real-valued function f(x) and the corresponding metric spaces X and Y. Such a function is said to be Lipschitz-continuous if:

In other words, if two points x₁ and x₂ are near, the corresponding output values y₁ and y₂ cannot be arbitrarily far from each other. This condition is fundamental in regression problems where a generalization is often required for points that are between training samples. For example, if we need to predict the output for a point x_t : x₁ < x_t < x₂ and the regressor is Lipschitz-continuous, we can be sure that y_t will be correctly bounded by y₁ and y₂. This condition is often called general smoothness, but in semi-supervised it's useful to add a restriction (correlated with the cluster assumption): if two points are in a high density region (cluster) and they are close, then the corresponding outputs must be close too. This extra condition is very important because, if two samples are in a low density region they can belong to different clusters and their labels can be very different. This is not always true, but it's useful to include this constraint to allow some further assumptions in many definitions of semi-supervised models.