In this paper we propose a novel boosting based classification algorithm, SODA-Boosting (where SODA stands for Second Order Discriminant Analysis). Unlike the conventional AdaBoost based algorithms widely applied in computer vision, SODA-Boosting does not involve time consuming procedures to search a huge feature pool in every iteration during the training stage. Instead, in each iteration SODA-Boosting efficiently computes discriminative weak classifiers in closed-form, based on reasonable hypotheses on the distribution of the weighted training samples. As an application, SODA-Boosting is employed for image based gender recognition. Experimental results on publicly available FERET database are reported. The proposed algorithm achieved accuracy comparable to state-of-the-art approaches, and demonstrated superior performance to relevant boosting based algorithms.