This chapter provides a theoretical foundation for the Sampling-and-Learning (SAL) and Sampling-and-Classification (SAC) frameworks in derivative-free optimization (DFO). It introduces the concept of \((\epsilon, \delta)\) -query complexity, which measures the number of function evaluations required to find an \(\epsilon \) -optimal solution with probability \(1-\delta \) . The chapter derives general performance bounds for the SAL framework and identifies two key factors influencing the SAC framework’s efficiency: error-target dependence and shrinking rate. These factors measure the alignment between the learned model and the target solution set, and the reduction in the search space volume, respectively. The analysis shows that SAC algorithms can achieve polynomial query complexity for functions with local Lipschitz continuity and bounded packing/covering numbers. The chapter concludes by discussing practical implications for designing efficient DFO algorithms, emphasizing the importance of model alignment and problem geometry in optimization performance.