Face representation based on 2D Gabor has attracted much attention. However, due to the fact that Gabor features currently are redundant and too high dimensional, selection of optimal Gabor features for face recognition appears to be paramount. Margin-based algorithms which use the large margin principle for feature selection have already played a crucial role in current machine learning research. In this paper, based on iterative search margin-based algorithm (Simba), we introduce a new selection algorithm: Conjugated gradient margin-based algorithm (Cgmba), which can find optimal solution at less iteration. Experiments were carried out on IMM face database. Results indicate that Cgmba and Simba can provide 3.75, 1.25 percent improvement in classification rate respectively, though less than half of all features are used. Moreover, superiority of our proposed approach to Simba is also demonstrated. Finally, the distribution of Gabor features selected by Cgmba is analyzed. It is inferred that the features in the larger scales have the same importance as those in the smaller scales in discriminating nuance of faces and features in vertical, and 135°orientations have more discriminative power.