min_x E(x; x0) + R(x)
I thought that E(x; x0) would denote the error/difference between original and corrupted images, and R(x) be the (searched-for) correction. But this doesn't seem to make sense with the next parts of their explanation.
R(x) is a regularization term to avoid overfitting. For example, in the denoising example, it could be a measure of the variation in color of x. Clearly, just taking x = x0, the squared error (E(x; x0)) is 0, but it will have high R(x) because of all the noise. That's why they try to minimize both quantities combined, so we get min_x E(x; x0) + R(x), to get close to the objective but also not overfit.
and they pose x = f_theta(z), where f_theta is a neural net.
So they can avoid overfitting by stopping the training at the right moment.
So they're not really trying to minimize E(x, x0), but rather to get a small enough value, so that they obtain good results. A too small value means overfitting.