This research proposes a novel approach for learning kernel Support Vector Machines (SVM) from large-scale data with reduced computation time. The proposed approach, termed as Subclass Reduced Set SVM (SRS-SVM), utilizes the subclass structure of data to effectively estimate the candidate support vector set. Since the candidate support vector set cardinality is only a fraction of the training set cardinality, learning SVM from the former requires less time without significantly changing the decision boundary. SRS-SVM depends on a domain knowledge related input parameter, i.e. number of subclasses. To reduce the domain knowledge dependency and to make the approach less sensitive to the subclass parameter, we extend the proposed SRS-SVM to create a robust and improved hierarchical model termed as the Hierarchical Subclass Reduced Set SVM (HSRS-SVM). SinceSRS-SVM and HSRS-SVM split non-linear optimization problem into multiple (smaller) linear optimization problems, both of them are amenable to parallelization. The effectiveness of the proposed approaches is evaluated on four synthetic and six real-world datasets. The performance is also compared with traditional solver (LibSVM) and state-of-the-art approaches such as divide-and-conquer SVM, FastFood, and LLSVM. The experimental results demonstrate that the proposed approach achieves similar classification accuracies while requiring fewer folds of reduced computation time as compared to existing solvers. We further demonstrate the suitability and improved performance of the proposed HSRS-SVM with deep learning features for face recognition using Labeled Faces in the Wild (LFW) dataset.