One embodiment of the present invention provides a system that performs high-level parallelization of large scale quadratic-problem (QP) optimization. During operation, the system receives a training dataset comprised of a number of data vectors. The system first determines to what extent each data vector violates conditions associated with a current support vector machine (SVM). The system then sorts the data vectors based on each data vector's degree of violation. Next, the system partitions the sorted data vectors into a number of prioritized subsets, wherein the subset with the highest priority contains the largest number of violators with the highest degree of violation. The system subsequently solves in parallel a QP optimization problem for each subset based on the subset's priority. The system then constructs a new SVM to replace the current SVM based on the QP optimization solution for each subset.