Fast, Parallel, Query-Efficient Binary Classification

Abstract

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 Φ∈ℝ^n × d denote the feature matrix and γ the margin of the maximum-margin separating hyperplane, we present a randomized algorithm that solves this problem in Õ(γ^-2/3 nnz(Φ) + γ^-2(ω+1)/3)-sequential running time (work), Õ(γ^-2/3)-parallel (computational) depth, and accesses Φ only through Õ(γ^-2/3)-matrix-vector queries (matvecs). We also present a second, faster randomized algorithm with a Õ(γ^-2/3 nnz(Φ) + γ^-2)-sequential running time that uses Õ(γ^-2/3)-matvecs to Φ, but achieves only Õ(γ^-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.