Indexed Learning for Large-Scale Linear Classification

Linear classification has achieved complexity linear to the data size. However, in many applications, large-scale data contains only a few samples that can improve the target objective. In this paper, we propose a sublinear-time algorithm that uses Nearest-Neighbor-based Coordinate Descent method to solve Linear SVM with truncated loss. In particular, we propose a sequential relaxation that solves prob-lem with general truncated-loss by a series of sparse convex programs. Then we solve each program using indexed dual coordinate descent, which avoids I/O of unnecessary data by searching coordinates of large gradient. We show the pro-posed algorithm has linear convergence rate, and has sublinear complexity for each iteration. We also demonstrates its empirical success in sufficient and limit-ed memory conditions. In both cases, the indexed learning algorithm learns times faster than state-of-the-art linear hinge-loss and ramp-loss solvers without sacri-ficing accuracy.