Large-scale problems in data science are often modeled with optimization and solved with first-order methods that may converge at a sublinear rate. It is of interest to terminate the optimization algorithm as soon as the underlying data science task is accomplished. We analyze the complexity of first-order methods for support vector machines (SVMs) in terms of the accuracy required to obtain a useful classifier rather than solve the underlying optimization problem. For a perturbed SVM formulation, we derive a stopping condition certifying individual points as correctly classified without data assumptions. Under a geometric model consisting of two clusters, one per class, together with noisy observations, certifying one point guarantees that the current classifier separates the clusters given a modest number of samples. We additionally derive a data-dependent accuracy threshold guaranteeing this separation. Computable bounds on distance to the optimum allow evaluation of our stopping condition for FISTA and coordinate descent. For FISTA, we derive data-dependent iteration complexity bounds for certification and separation. We demonstrate that LIBLINEAR’s stopping condition can be overly conservative or terminate prematurely with a poor classifier. Experiments demonstrate robust termination and show that a simple FISTA implementation using our condition is competitive with widely used SVM solvers.
Data-Dependent Complexity of First-Order Methods for Support Vector Machines
\(\)