## 2 Materials and Methods
### Surrogate Fourier Modeling with surf  
Periodic functions, as well as functions defined only on a limited domain, can be represented via a weighted sum of frequencies by computing their Fourier transform. Representing a function via frequencies allows for performing some interesting manipulations. For example, removing higher frequencies has a smoothing effect on the signal. This effect is being employed by the recently introduced _Fitness Landscape Surrogate Modeling with Fourier Filtering (surF)_ technique [PERSON] et al. (2018). There, a surrogate model of the fitness landscape is produced by \"smoothing out\" the original landscape with the intention of removing local optima where the optimization might stop. Let \(D\) be the number of dimensions of the search, space and let the search space itself be the hypercube \([\ell,u]^{D}\subset\mathbb{R}^{D}\). Let \(f\colon[\ell,u]^{D}\to\mathbb{R}\) be the objective function, i.e., \(f\) represents the fitness landscape. Since \(f\) is usually not known in an analytical form, we work with _samples_ of \(f\) and, consequently, we employ a discrete version of the Fourier transform, the _discrete cosine transform_ (DCT) [PERSON] et al. (2018). It is worth noting that the time and space complexity of surf mainly depends on the choice of method used to compute the Fourier  
Figure 4: (**Left**): different examples of the linear transformation \(l_{p}\) with different values of \(p\). (**Right**): examples of _folding operators_ with varying values of \(p\) and \(r\). transform; thus, different approaches would give different space and time complexity bounds. 1. **Discrete Cosine Transform. ** To recall the DCT, let us start with the simpler case of a single dimension, i.e., \(D=1\). Hence, we have a function \(f\colon[\ell,u]\to\mathbb{R}\) and \(\rho\in\mathbb{N}\) equally spaced points \(z_{0},\ldots,z_{p-1}\) in the interval \([\ell,u]\), where \(f\) is the sample. That is, we know \(f(z_{0}),\ldots,f(z_{p-1})\). The DFT is used to represent each of these points as a weighted sum of frequencies: \[f(z_{k})=\sum_{j=0}^{\rho-1}\psi_{j}e^{2\pi i\frac{\beta}{\rho}} \text{for }0\leq k<\rho.\] Notice how the entire set of \(\rho\) points is entirely determined by the coefficients \(\psi_{0},\ldots,\psi_{\rho-1}\) representing the amplitudes of the different frequencies. That is, given \(\psi_{0},\ldots,\psi_{\rho-1}\), it is possible to recover the values \(f(z_{0}),\ldots,f(z_{\rho-1})\) via the _inverse DFT_. Working with frequencies, however, has some advantages: since each \(\psi_{j}\) is associated with a different frequency, we can manipulate it. One of the simplest modifications can be performed by zeroing out all but the first \(\gamma\in\{0,\ldots,\rho-1\}\) coefficients. The effect is that all of the \(\rho-\gamma\) higher frequencies are removed. When computing the inverse DFT on the coefficients \(\psi_{0},\ldots,\psi_{\gamma-1},0,\ldots,0\) we obtain \(\rho\) points \(y_{0},\ldots,y_{\rho-1}\) as a \"smoothed\" version of \(f(z_{0}),\ldots,f(z_{\rho-1})\). While we have only obtained \(\rho\) points, we can define a surrogate of \(f\) as a function \(\hat{f}\colon[\ell,u]\to\mathbb{R}\) performing a linear interpolation among the points \(y_{0},\ldots,y_{\rho-1}\). Since \(\hat{f}\) is a smoothed version of \(f\), it might have a reduced amount of local optima, thus helping the optimization process. The procedure can be extended in any number \(D\) of dimensions. Instead of having \(\rho\) points sampled from \(f\), there will be \(\rho^{D}\) points sampled from \(f\) in an equally spaced grid in \([\ell,u]^{D}\). Consequently, \(\rho^{D}\) coefficients are obtained via DFT and of those, only \(\gamma^{D}\) are preserved (i.e., all \(\psi_{i_{1},\ldots,i_{D}}\) with \(i_{j}<\gamma\) for all \(1\leq j\leq D\)). Hence, the fitness landscape reconstructed by surf has a tunable level of non-zero high-frequency components, which can be controlled by means of the \(\gamma\) hyperparameter. 2. **Reducing the number of samples.