Fast, Parallel, Query-Efficient Binary Classification

Ishani Karmarkar, Liam O’Carroll, Aaron Sidford
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3906-3949, 2026.

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 $\Phi \in \mathbb{R}^{n \times d}$ denote the feature matrix and $\gamma$ the margin of the maximum-margin separating hyperplane, we present a randomized algorithm that solves this problem in $\tilde{O}(\gamma^{-2/3}\, \operatorname{nnz}(\Phi) + \gamma^{-2(\omega+1)/3})$-sequential running time (work), $\tilde{O}(\gamma^{-2/3})$-parallel (computational) depth, and accesses $\Phi$ only through $\tilde{O}(\gamma^{-2/3})$-matrix-vector queries (matvecs). We also present a second, faster randomized algorithm with a $\tilde{O}(\gamma^{-2/3}\, \operatorname{nnz}(\Phi) + \gamma^{-2})$-sequential running time that uses $\tilde{O}(\gamma^{-2/3})$-matvecs to $\Phi$, but achieves only $\tilde{O}(\gamma^{-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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-karmarkar26a, title = {Fast, Parallel, Query-Efficient Binary Classification}, author = {Karmarkar, Ishani and O'Carroll, Liam and Sidford, Aaron}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {3906--3949}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/karmarkar26a/karmarkar26a.pdf}, url = {https://proceedings.mlr.press/v336/karmarkar26a.html}, 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 $\Phi \in \mathbb{R}^{n \times d}$ denote the feature matrix and $\gamma$ the margin of the maximum-margin separating hyperplane, we present a randomized algorithm that solves this problem in $\tilde{O}(\gamma^{-2/3}\, \operatorname{nnz}(\Phi) + \gamma^{-2(\omega+1)/3})$-sequential running time (work), $\tilde{O}(\gamma^{-2/3})$-parallel (computational) depth, and accesses $\Phi$ only through $\tilde{O}(\gamma^{-2/3})$-matrix-vector queries (matvecs). We also present a second, faster randomized algorithm with a $\tilde{O}(\gamma^{-2/3}\, \operatorname{nnz}(\Phi) + \gamma^{-2})$-sequential running time that uses $\tilde{O}(\gamma^{-2/3})$-matvecs to $\Phi$, but achieves only $\tilde{O}(\gamma^{-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.} }
Endnote
%0 Conference Paper %T Fast, Parallel, Query-Efficient Binary Classification %A Ishani Karmarkar %A Liam O’Carroll %A Aaron Sidford %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-karmarkar26a %I PMLR %P 3906--3949 %U https://proceedings.mlr.press/v336/karmarkar26a.html %V 336 %X 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 $\Phi \in \mathbb{R}^{n \times d}$ denote the feature matrix and $\gamma$ the margin of the maximum-margin separating hyperplane, we present a randomized algorithm that solves this problem in $\tilde{O}(\gamma^{-2/3}\, \operatorname{nnz}(\Phi) + \gamma^{-2(\omega+1)/3})$-sequential running time (work), $\tilde{O}(\gamma^{-2/3})$-parallel (computational) depth, and accesses $\Phi$ only through $\tilde{O}(\gamma^{-2/3})$-matrix-vector queries (matvecs). We also present a second, faster randomized algorithm with a $\tilde{O}(\gamma^{-2/3}\, \operatorname{nnz}(\Phi) + \gamma^{-2})$-sequential running time that uses $\tilde{O}(\gamma^{-2/3})$-matvecs to $\Phi$, but achieves only $\tilde{O}(\gamma^{-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.
APA
Karmarkar, I., O’Carroll, L. & Sidford, A.. (2026). Fast, Parallel, Query-Efficient Binary Classification. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:3906-3949 Available from https://proceedings.mlr.press/v336/karmarkar26a.html.

Related Material