A mathematical function is said to be a black-box when its mathematical formula does not exist or is unknown. Their function values can be evaluated but not of their derivatives. One approach to optimize these functions is to use function values to approximate the black-box objective function with a function that has known mathematical formula, then optimize the approximation function instead. Certainly, the accuracy of the approximation would be crucial to the performance of the algorithm. Several optimization algorithms using this approach will be presented in this talk, followed by the analyses their approximation accuracies. Specifically, the gradient approximation accuracies of several sample average approximation methods will be presented, followed by a discussion of the use of polynomial interpolation in black-box optimization.