Data-Dependent Complexity of First-Order Methods for Binary Classification
Matthew Hough, Stephen A. Vavasis · 2025
Read Data-Dependent Complexity of First-Order Methods for Binary Classification by Matthew Hough, Stephen A. Vavasis (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-03947.txt.
Introduction
Training a support vector machine means running an optimisation algorithm, and knowing when to stop is worth money at scale. Matthew Hough and Stephen A. Vavasis analyse that stopping problem in a 2025 preprint. Their core idea: stop not at a fixed accuracy, but when the current classifier is certified to agree with the optimal one on points that matter.
For a perturbed SVM formulation, they derive a stopping condition that certifies points correctly classified by both classifiers, with no assumptions on the data at all. Under a geometric model of two clean clusters plus noise, certifying one point can guarantee the whole well-behaved set is separated. They add computable bounds for two algorithms, FISTA and coordinate descent. The analysis exposes flaws in the stopping rule of the popular LIBLINEAR package, which can stop too early or too late.
Catalog record
| CREATOR | Matthew Hough, Stephen A. Vavasis |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 101 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-03947
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Data-Dependent Complexity of First-Order Methods for Binary Classification Thanks: Supported in part by a Discovery Grant from the Natural Sciences and Engineering Research Council (NSERC) of Canada. Matthew Hough, Stephen A. Vavasis Abstract Large-scale problems in data science are often modeled with optimization, and the optimization model is usually solved with first-order methods that may converge at a sublinear rate. Therefore, it is of interest to terminate the optimization algorithm as soon as the underlying data science task is accomplished. We consider FISTA for solving two binary classification problems: the ellipsoid separation problem (ESP), and the soft-margin support-vector machine (SVM). For the ESP, we cast the dual second-order cone program into a form amenable to FISTA and show that the FISTA residual converges to the infimal displacement vector of the primal-dual hybrid gradient (PDHG) algorithm, that directly encodes a separating hyperplane. We further derive a data-dependent iteration upper bound scaling as 𝒪 ( 1 / δ 𝒜 2 ) \mathcal{O}(1/\delta_{\mathcal{A}}^{2}) , where δ 𝒜 \delta_{\mathcal{A}} is the minimal perturbation that destroys separability. For the SVM, we propose a strongly-concave perturbed dual that admits efficient FISTA updates under a linear time projection scheme, and with our parameter choices, the objective has small condition number, enabling rapid convergence. We prove that, under a reasonable data model, early-stopped iterates identify well-classified points and yield a hyperplane that exactly separates them, where the accuracy required of the dual iterate is governed by geometric properties of the data. In particular, the proposed early-stopping criteria diminish the need for hard-to-select tolerance-based stopping conditions. Our numerical experiments on ESP instances derived from MNIST data and on soft-margin SVM benchmarks indicate competitive runtimes and substantial speedups from stopping early. 1 Introduction Binary classification is a central task in machine learning with numerous applications. Given data separated into two classes, the task is to construct a decision boundary called a classifier that separates the classes completely, or with minimal misclassifications. Since many binary classification models, including the support vector machine (SVM), can be modeled as convex optimization problems, first-order methods are a popular choice for training these models, especially in large-scale settings. Typically, algorithms for binary classification are guaranteed to yield a classifier under the assumption that numerical convergence of the underlying optimization problem is achieved. In practice, however, high-accuracy optimization is often unnecessary to correctly classify most points: a hyperplane that correctly classifies “well-separated” or “easy to classify” points may emerge after only a small number of iterations. One would expect that the ability to obtain such an approximate separator in few iterations depends on the classifiability of the data, i.e. the extent to which the data contain points that are robustly separable from the opposite class. In such cases, the computational effort required to find a useful classifier is not solely determined by worst-case complexity bounds of the optimization problem, but can instead be characterized in terms of data-dependent complexity , where the number of iterations required to obtain a classifier scales with geometric properties of the dataset rather than purely algorithmic constants. The work herein investigates data-dependent complexity in two related binary classification tasks. The first is the ellipsoid separation problem (ESP), in which each class is represented by a finite family of ellipsoids, and the task is to determine a separating hyperplane that completely separates one class of ellipsoids from the other. This problem can be seen as an extension of classic binary classification, where the locations of the data are known only up to an ellipsoid, and a separating hyperplane must be found which separates all possible locations of the data. Modeling data uncertainty in this way is a form of robust classification, and was considered by Shivaswamy et al. in [ 26 ] . In the ellipsoid separation setting, we show that the FISTA algorithm [ 3 ] applied to a second-order cone program (SOCP), which models the dual of the ESP, yields iterates whose residual vectors encode a separating hyperplane. Furthermore, we prove that the ESP can be solved in \mathcal{O}(1/\delta_{\mathcal{A}}^{2}) iterations, where \delta_{\mathcal{A}} represents the smallest perturbation to the ellipsoid centers, such that the ellipsoids are no longer separable. The second problem we consider is the soft-margin support vector machine (SVM) for non-separable data introduced in [ 10 ] . Here, a perfect separator does not exist, but many points may still be classifiable. We propose a perturbed dual formulation of the soft-margin SVM that is strongly concave and converges quickly in FISTA due to the objective having a condition number \kappa=L/\mu\leq 513 . We prove that, under a suitable data model, an approximate solution to the perturbed dual can be used to identify all well-classified points, and furthermore we show how one can construct a separating hyperplane from this approximate dual solution that can separate the well-classified points exactly. The degree of approximation required of the dual solution is also itself dependent on the geometry of the data. For both the ESP and soft-margin SVM, we perform numerical experiments that show considerable speedup can be achieved using our methods. In particular, our method for approximately solving soft-margin support vector machines performs similarly to LIBSVM [ 9 ] and LIBLINEAR [ 13 ] , and on average outperforms Pegasos [ 25 ] in terms of runtime in seconds and accuracy on select problems from the UCI Machine Learning Dataset [ 18 ] . Binary classification has been extensively studied in the contexts of convex optimization and machine learning, most notably through the development of the soft-margin support vector machine by Cortes and Vapnik [ 10 ] . Various specialized algorithms to solve the SVM have been proposed over time. Osuna, Freund, and Girosi [ 22 ] developed a decomposition method for the dual SVM, which partitions the quadratic program (QP) into smaller subproblems and makes training feasible even when the number of support vectors is large. Platt then refined this work in his development of Sequential Minimal Optimization (SMO) [ 23 ] , which instead decomposes the QP into the smallest possible subproblems, allowing them to be solved analytically. Around the same time, Joachims independently developed SVMlight [ 17 ] , a more general decomposition framework than Platt’s. Further refinements to the decomposition ideas of Osuna et al., Platt, and Joachims were proposed in [ 14 ] , which forms the basis of the widely used LIBSVM library for solving SVMs [ 9 ] . In parallel, primal-based algorithms were also developed, most notably Pegasos [ 25 ] , which employs stochastic subgradient descent to solve the primal SVM efficiently on very large-scale datasets. Shortly after, the LIBLINEAR solver was developed specifically for large-scale linear classification [ 13 ] . Beyond algorithmic advances, there is also a line of research analyzing the data-dependent complexity of algorithms. These ideas have been investigated recently in [ 12 , 1 , 20 , 21 , 27 ] , but are related to earlier work done by Freund and Vera [ 15 ] , and Cucker and Peña [ 11 ] on convergence rates for optimization algorithms that depend on the conditioning of the problem instance. However, all these works focus on the optimization problem itself, without an underlying data science problem such as