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 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.
Code (0)
등록된 구현이 없습니다.
Tasks
Binary ClassificationSimilar Papers 제목 키워드 기반
Efficient Querying from Weighted Binary Codes
Binary codes are widely used to represent the data due to their small storage and efficient computation. However, there exists an ambiguity problem that lots of binary codes share the same Hamming distance to a query. To…
Fast Cosine Similarity Search in Binary Space with Angular Multi-index Hashing
Given a large dataset of binary codes and a binary query point, we address how to efficiently find $K$ codes in the dataset that yield the largest cosine similarities to the query. The straightforward answer to this prob…
Laplacian Regularized Few-Shot Learning
We propose a transductive Laplacian-regularized inference for few-shot tasks. Given any feature embedding learned from the base classes, we minimize a quadratic binary-assignment function containing two terms: (1) a unar…
ClusteringFew-Shot Image ClassificationFew-Shot LearningGraph Clustering+1Laplacian Regularized Few-Shot Learning
We propose a transductive Laplacian-regularized inference for few-shot tasks. Given any feature embedding learned from the base classes, we minimize a quadratic binary-assignment function containing two terms: (1) a unar…
ClusteringFew-Shot Image ClassificationFew-Shot LearningGraph Clustering+1ensemblQueryR: fast, flexible and high-throughput querying of Ensembl LD API endpoints in R
We present ensemblQueryR, a package providing an R interface to the Ensembl REST API that facilitates flexible, fast, user-friendly and R workflow integrable querying of Ensembl REST API linkage disequilibrium (LD) endpo…