What happens is they first synthesize the texture at a coarse resolution, and then up-sample it to a higher resolution through interpolation after the synthesis has reach convergence. Moreover, at each resolution level, the synthesis algorithm is run using multiple neighborhood sizes from largest to smallest (they used 32x32, 16x16, 8x8).
To summarize the whole algorithm:
- Initialize target texture to random.
- For each 32x32, 16x16, 8x8: run optimization until convergence.
- Up-sample to higher resolution by interpolation.
- Go back to step 2. Repeat until resolution is at desired level.