A common challenge in machine learning and related fields is the need toefficiently explore high dimensional parameter spaces using small numbers ofsamples. Typical examples are hyper-parameter optimization in deep learning andsample mining in predictive modeling tasks. All such problems trade-offexploration, which samples the space without knowledge of the target function,and exploitation where information from previous evaluations is used in anadaptive feedback loop. Much of the recent focus has been on the exploitationwhile exploration is done with simple designs such as Latin hypercube or evenuniform random sampling. In this paper, we introduce optimal space-fillingsample designs for effective exploration of high dimensional spaces.Specifically, we propose a new parameterized family of sample designs calledspace-filling spectral designs, and introduce a framework to choose optimaldesigns for a given sample size and dimension. Furthermore, we present anefficient algorithm to synthesize a given spectral design. Finally, we evaluatethe performance of spectral designs in both data space and model spaceapplications. The data space exploration is targeted at recovering complexregression functions in high dimensional spaces. The model space explorationfocuses on selecting hyper-parameters for a given neural network architecture.Our empirical studies demonstrate that the proposed approach consistentlyoutperforms state-of-the-art techniques, particularly with smaller designsizes.