Property Testing for Linear Separability: Theory, Implementation, and Empirical Evaluation

Abstract

Linear separability is a fundamental concept in machine learning that underlies many classification models and geometric decision procedures. While exact deterministic tests for linear separability are well studied and practical, they can become computationally expensive on large or high-dimensional datasets. In many practical settings, however, an exact answer is not necessary; it is often sufficient to determine whether data are linearly separable or far from separable. Property testing provides a framework for this type of approximate decision-making by allowing algorithms to inspect only a small fraction of the input. Although property testers for linear separability have been studied theoretically and can achieve sublinear time complexity, their practical behavior and empirical relationship to exact methods remain relatively underexplored. This thesis presents an empirical study of linear separability testing from a property testing perspective. It compares efficient deterministic algorithms with both two-sided and one-sided sublinear testers. In addition, it develops a practical LP-based implementation of a one-sided tester motivated by VC-dimension theory and investigates its empirical behavior across multiple data regimes. The evaluation includes both synthetic and real-world datasets. For two-dimensional synthetic data, we construct instances with exactly controlled distance to linear separability. In higher dimensions, we generate non-separable instances by perturbing an ε-fraction of points from an initially separable dataset, which guarantees that the resulting dataset is at most ε-far from separable, although the exact distance may be smaller. This setting differs from the exact formulation of a property testing problem but provides controlled empirical evaluation. Experimental results show that sublinear property testers can achieve high accuracy while requiring substantially less computation time than exact baselines on larger datasets, especially when instances are clearly separable or clearly nonseparable. Their reliability decreases when the data are very close to separable, particularly at separation distances below 0.01. The thesis identifies the conditions under which propertytesting-based methods are useful as fast pre-screening tools and evaluates their empirical performance relative to theoretical guarantees.