In surveillance applications, cameras are usually set up with wide fields of view to capture as much of the scene as possible. This normally results in low-resolution images of the objects of interest. Since most image analysis applications require high or medium resolution inputs, the development of approaches aiming at improving the quality of these image regions has been an active research area in the last few years. A new family of approaches, based on statistical machine learning, aims at analyzing large data sets of images of a particular class of objects and learning the mapping from low-quality to high-quality images of that class. This enables them to infer, for example, the most likely high-resolution face image depicting the same person as a low-resolution image given as input. These super-resolution algorithms are time-consuming, due to the need for exhaustive search in a database of models. This work improves the efficiency of face image super-resolution using stochastic search for local modeling. Experimental results show that the proposed algorithm generates high-quality face images from low-resolution inputs while reducing the computation time dramatically.