提出两种快速并行的二分类算法，显著降低查询次数和运行时间。
Fast, Parallel, Query-Efficient Binary Classification
- 基于随机化方法，通过少量矩阵-向量查询求解二分类问题。
- 在保持低查询次数前提下，实现比已有方法更快的串行运行时间和更低的并行深度。
- 适合大规模数据中需高效并行处理的场景，尤其关注查询效率的工程应用。
我们研究了大小为 $n$、特征维度为 $d$ 且归一化的二分类数据集的分离超平面计算问题。设特征矩阵为 $Φ\in \mathbb{R}^{n \times d}$，最大间隔超平面的间隔为 $γ$。本文提出一种随机算法，在 $\tilde{O}(γ^{-2/3}\, \operatorname{nnz}(Φ) + γ^{-2(ω+1)/3})$ 的串行时间内完成计算，具有 $\tilde{O}(γ^{-2/3})$ 的并行深度，并仅通过 $\tilde{O}(γ^{-2/3})$ 次矩阵-向量查询（matvecs）访问 $Φ$。此外，我们还提出第二种更快的随机算法，其串行时间为 $\tilde{O}(γ^{-2/3}\, \operatorname{nnz}(Φ) + γ^{-2})$，使用 $\tilde{O}(γ^{-2/3})$ 次 matvecs，但并行深度为 $\tilde{O}(γ^{-4/3})$。两种算法均达到最近由 Kornowski 和 Shamir [2025]、Karmarkar 等 [2026] 建立的近似最优确定性 matvec 复杂度，且在串行时间与并行深度上均有改进，代价是引入随机性。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。