Black-box optimization corresponds to a class of optimization problems with a complicated or an unknown objective function, i.e. a “black-box” function, such that its output values at specific inputs can only be measured by expensive or time-consuming processes. They are very challenging and cannot be tackled by conventional optimization algorithms which are based on the knowledge of a known objective function. Nevertheless, they are crucial in a wide range of applications in science and engineering. Yet, unlike conventional “white-box” optimization problems where physicists have devoted decades of efforts in developing a fundamental understanding of their macroscopic properties which has led to insightful developments, the awareness of black-box problems in the physics community and the attempts to address them are very limited. This is partly because an unknown objective function is incompatible with conventional statistical physics tools. As a result, research on black-box optimization is dominated by algorithm-oriented approaches without a thorough understanding underlying black-box optimization problems. In the proposed research, we will overcome the obstacle of an unknown objective function and apply statistical physics tools to (1) develop a fundamental understanding of the nature of black-box optimization problems, (2) derive a macroscopic description of their behaviors and understand the effectiveness of their existing solution methods, and (3) apply these insights to improve existing solution methods, and devise new physics-inspired and understanding-driven algorithms for black-box problems. Specifically, we will establish a theoretical framework to study black-box optimization problems with statistical physics. We will apply tools from statistical physics to (a) understand the effectiveness of various sampling strategies in relation with the nature of black-box objective functions, (b) reveal the relation between the objective function fitting stage and the subsequent optimization stage in conventional modeling-fitting-optimizing approaches for black-box problems, (c) map black-box problems to spin glasses and disordered systems of noisy information retrieval and associate memory, (d) coarse-grain black-box problems and examine the validity of the coarse-grained systems as representatives of the original systems with reduced dimensionality, and finally (e) use all the above theoretical insights to improve and inform existing black-box solution methods, and devise new physics-inspired and understanding-driven algorithms for black-box optimization problems.