# Fast, Parallel, Query-Efficient Binary Classification

arXiv: https://arxiv.org/abs/2607.04062 · HTML: https://mlsanity.com/paper/2607.04062/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 34 of its 61 references that are in the map.
- First posted on arXiv 5 Jul 2026.

## Builds on (most cited first, 30 of 34)

- [Solving Linear Programs in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1810.07896/) (2018)
- [Stochastic Variance Reduction Methods for Saddle-Point Problems](https://mlsanity.com/paper/1605.06398/) (2016)
- [An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications](https://mlsanity.com/paper/2004.04250/) (2020)
- [A Universal Catalyst for First-Order Optimization](https://mlsanity.com/paper/1506.02186/) (2015)
- [A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization](https://mlsanity.com/paper/1508.04874/) (2015)
- [Variance Reduction for Matrix Games](https://mlsanity.com/paper/1907.02056/) (2019)
- [Optimal approximate matrix product in terms of stable rank](https://mlsanity.com/paper/1507.02268/) (2015)
- [Generalized Self-Concordant Functions: A Recipe for Newton-Type Methods](https://mlsanity.com/paper/1703.04599/) (2017)
- [Acceleration with a Ball Optimization Oracle](https://mlsanity.com/paper/2003.08078/) (2020)
- [More Asymmetry Yields Faster Matrix Multiplication](https://mlsanity.com/paper/2404.16349/) (2024)
- [Stochastic Bias-Reduced Gradient Methods](https://mlsanity.com/paper/2106.09481/) (2021)
- [Global linear convergence of Newton's method without strong-convexity or Lipschitz gradients](https://mlsanity.com/paper/1806.00413/) (2018)
- [Optimal and Adaptive Monteiro-Svaiter Acceleration](https://mlsanity.com/paper/2205.15371/) (2022)
- [Complexity of Highly Parallel Non-Smooth Convex Optimization](https://mlsanity.com/paper/1906.10655/) (2019)
- [Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization](https://mlsanity.com/paper/1506.07512/) (2015)
- [Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss](https://mlsanity.com/paper/2105.01778/) (2021)
- [ReSQueing Parallel and Private Stochastic Convex Optimization](https://mlsanity.com/paper/2301.00457/) (2023)
- [Coordinate Methods for Matrix Games](https://mlsanity.com/paper/2009.08447/) (2020)
- [Distributionally Robust Optimization via Ball Oracle Acceleration](https://mlsanity.com/paper/2203.13225/) (2022)
- [Quantum speedups for stochastic optimization](https://mlsanity.com/paper/2308.01582/) (2023)
- [Optimal Embedding Dimension for Sparse Subspace Embeddings](https://mlsanity.com/paper/2311.10680/) (2023)
- [Improved Iteration Complexities for Overconstrained p-Norm Regression](https://mlsanity.com/paper/2111.01848/) (2021)
- [Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations](https://mlsanity.com/paper/1811.10722/) (2018)
- [Minimizing Quasi-Self-Concordant Functions by Gradient Regularization of Newton Method](https://mlsanity.com/paper/2308.14742/) (2023)
- [Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning](https://mlsanity.com/paper/2405.05865/) (2024)
- [Optimal Oblivious Subspace Embeddings with Near-optimal Sparsity](https://mlsanity.com/paper/2411.08773/) (2024)
- [The Oracle Complexity of Simplex-based Matrix Games](https://mlsanity.com/paper/2412.06990/) (2024)
- [A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions](https://mlsanity.com/paper/2311.10886/) (2023)
- [Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimization](https://mlsanity.com/paper/2406.07373/) (2024)
- [Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure](https://mlsanity.com/paper/2507.11724/) (2025)

## Abstract (arXiv)

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 ∈ ℝn × d denote the feature matrix and γ the margin of the maximum-margin separating hyperplane, we present a randomized algorithm that solves this problem in tildeO(γ-2/3, operatornamennz(Phi) + γ-2(ω+1)/3)-sequential running time (work), tildeO(γ-2/3)-parallel (computational) depth, and accesses Phi only through tildeO(γ-2/3)-matrix-vector queries (matvecs). We also present a second, faster randomized algorithm with a tildeO(γ-2/3, operatornamennz(Phi) + γ-2)-sequential running time that uses tildeO(γ-2/3)-matvecs to Phi, but achieves only tildeO(γ-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.