Data-Dependent Robust Termination of First-Order Methods for Support Vector Machines

Optimization algorithms used to train machine-learning models are typically terminated according to optimality conditions of the optimization problem. However, high optimization accuracy may be unnecessary once the underlying learning task has already been accomplished. Conversely, more difficult learning problems may require substantially greater optimization accuracy. Thus, the accuracy required should depend on the difficulty of the learning problem. We study this distinction for support vector machines using a strongly concave dual formulation under a geometric model consisting of two clusters together with noisy observations. We derive a data-dependent accuracy threshold such that any dual solution satisfying it yields a hyperplane that strictly separates the two clusters. Additionally, we show that the points in each cluster can be identified from the approximate dual solution. We specialize these results to FISTA, obtaining a data-dependent iteration complexity for solving the classification problem. We also provide practical termination conditions tied to progress on the classification task rather than to a predefined optimization tolerance. Numerical experiments on benchmark problems illustrate that data-dependent early termination can provide a robust alternative to conventional optimization-based stopping criteria.