We study the fundamental classification problem of computing a separating hyperplane for a binary-labeled dataset of size n with normalized d-dimensional features. Letting Φ∈Rn×d denote the feature matrix and γ the margin of the maximum-margin separating hyperplane, we present a randomized algorithm that solves this problem in O~(γ−2/3nnz(Φ)+γ−2(ω+1)/3)-sequential running time (work), O~(γ−2/3)-parallel (computational) depth, and accesses Φ only through O~(γ−2/3)-matrix-vector queries (matvecs). We also present a second, faster randomized algorithm with a O~(γ−2/3nnz(Φ)+γ−2)-sequential running time that uses O~(γ−2/3)-matvecs to Φ, but achieves only O~(γ−4/3)-parallel depth. Both algorithms match the near-optimal deterministic matvec complexity recently established by Kornowski and Shamir [2025], Karmarkar et al. [2026] and achieve improved sequential runtime and parallel depth, albeit at the expense of using randomness.
Given a binary-labeled linearly separable dataset, and the objective is to compute the maximum-margin separating hyperplane, also known as the hard-margin Support Vector Machine (SVM) classifier. This paper investigates whether, if given an initial separating hyperplane, can it be exploited to reach this unique optimum more efficiently. We present a geometric approach that gradually improves the alignment of the hyperplane, starting from an initial separating hyperplane, while preserving separation and continuously increasing its margin until convergence to the global optimum. At each iteration, the method considers only local information, namely the current active set, and aims to re-align the hyperplane according to the optimal separating hyperplane of this reduced subset. Consequently, the original convex quadratic optimization problem is addressed through a sequence of smaller subproblems. The paper presents the algorithm in detail, together with a preliminary experimental evaluation and several theoretical findings. The results suggest that, when an initial separating hyperplane is available, the proposed method can be competitive on larger datasets and, in some cases, can outperform state-of-the-art approaches that solve the optimization problem directly.
We consider the problem of constructing a K-class classifier from the combination of O(logK) simple binary classifiers -- this is a natural paradigm to construct a sophisticated classifier in a distributed manner with each agent performing a relatively straightforward task. We study the fundamental performance limits of such a classifier when the corresponding binary classifiers are hyperplanes. For a stylized Gaussian setting where the K class centers are independent Gaussian points in Rd and the observations are corrupted by Gaussian noise, we derive explicit performance bounds across several decoding and dimensional regimes. Extensive simulation experiments provide strong empirical validation of the presented theoretical results.
Ioannis Papageorgiou, Srinivas Nomula, Ayalvadi Ganesh +2
While the optimal sample complexity of binary classification in terms of the VC dimension is well-established, determining the optimal sample complexity of multiclass classification has remained open. The appropriate complexity parameter for multiclass classification is the DS dimension, and despite significant efforts, a gap of DS has persisted between the upper and lower bounds on sample complexity. Recent work by Hanneke et al. (2026) shows a novel algebraic characterization of multiclass hypothesis classes in terms of their DS dimension. Building up on this, we show that the maximum hypergraph density of any multiclass hypothesis class is upper-bounded by its DS dimension. This proves a longstanding conjecture of Daniely and Shalev-Shwartz (2014). As a consequence, we determine the optimal dependence of the sample complexity on the DS dimension for multiclass as well as list learning.