We propose a non-parametric regression method that does not rely on the structure of the ground-truth, but only on its regularity properties. The methodology can be readily used for learning surrogate models of nonlinear dynamical systems from data, while providing bounds on the prediction error. In contrast with the well known Set Membership and Kinky Inference techniques that yield non-differentiable functions, the approach presented herein produces a smooth regressor. Consequently, it is more suitable to optimization-based controllers that heavily rely on gradient computations. A numerical example is provided to show the effectiveness of the method we call Smooth Lipschitz Interpolation (SLI) when compared to the aforementioned alternatives in a Model Predictive Control problem.