Fast, Parallel, Query-Efficient Binary Classification
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.04062
curl -X POST /api/v1/records/arxiv/2607.04062/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.04062/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'