{"ID":5938066,"CreatedAt":"2026-07-07T03:14:33.014478982Z","UpdatedAt":"2026-07-07T23:54:33.395952201Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.04062","arxiv_id":"2607.04062","title":"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 $Φ\\in \\mathbb{R}^{n \\times d}$ denote the feature matrix and $γ$ the margin of the maximum-margin separating hyperplane, we present a randomized algorithm that solves this problem in $\\tilde{O}(γ^{-2/3}\\, \\operatorname{nnz}(Φ) + γ^{-2(ω+1)/3})$-sequential running time (work), $\\tilde{O}(γ^{-2/3})$-parallel (computational) depth, and accesses $Φ$ only through $\\tilde{O}(γ^{-2/3})$-matrix-vector queries (matvecs). We also present a second, faster randomized algorithm with a $\\tilde{O}(γ^{-2/3}\\, \\operatorname{nnz}(Φ) + γ^{-2})$-sequential running time that uses $\\tilde{O}(γ^{-2/3})$-matvecs to $Φ$, but achieves only $\\tilde{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.","short_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 $Φ\\in \\mathbb{R}^{n \\times d}$ denote the feature matrix and $γ$ the margin of the maximum-margin separating hyperplane, we present a randomized...","url_abs":"https://arxiv.org/abs/2607.04062","url_pdf":"https://arxiv.org/pdf/2607.04062v1","authors":"[\"Ishani Karmarkar\",\"Liam O'Carroll\",\"Aaron Sidford\"]","published":"2026-07-05T00:18:56Z","proceeding":"math.OC","tasks":"[\"math.OC\",\"cs.DS\",\"cs.LG\"]","methods":"[]","has_code":false}