mlsanityData to 7 Oct 2026

Fast, Parallel, Query-Efficient Binary Classification

arXiv 2607.04062 ↗First posted 5 Jul 2026math.OC cs.DS cs.LGcited by 0

Not on the map. Why?

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.

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

Builds on

34 of 61 references.

References · 34

  1. 2018Solving Linear Programs in the Current Matrix Multiplication Timecited by 100
  2. 2016Stochastic Variance Reduction Methods for Saddle-Point Problemscited by 57
  3. 2020An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applicationscited by 57
  4. 2015A Universal Catalyst for First-Order Optimizationcited by 54
  5. 2015A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimizationcited by 50
  6. 2015Optimal approximate matrix product in terms of stable rankcited by 37
  7. 2019Variance Reduction for Matrix Gamescited by 37
  8. 2017Generalized Self-Concordant Functions: A Recipe for Newton-Type Methodscited by 33
  9. 2020Acceleration with a Ball Optimization Oraclecited by 31
  10. 2024More Asymmetry Yields Faster Matrix Multiplicationcited by 27
  11. 2021Stochastic Bias-Reduced Gradient Methodscited by 25
  12. 2018Global linear convergence of Newton's method without strong-convexity or Lipschitz gradientscited by 24
22 more
  1. 2022Optimal and Adaptive Monteiro-Svaiter Accelerationcited by 23
  2. 2015Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimizationcited by 21
  3. 2019Complexity of Highly Parallel Non-Smooth Convex Optimizationcited by 21
  4. 2021Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Losscited by 17
  5. 2023ReSQueing Parallel and Private Stochastic Convex Optimizationcited by 17
  6. 2020Coordinate Methods for Matrix Gamescited by 15
  7. 2022Distributionally Robust Optimization via Ball Oracle Accelerationcited by 14
  8. 2023Quantum speedups for stochastic optimizationcited by 12
  9. 2023Optimal Embedding Dimension for Sparse Subspace Embeddingscited by 11
  10. 2021Improved Iteration Complexities for Overconstrained p-Norm Regressioncited by 8
  11. 2018Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizationscited by 7
  12. 2023Minimizing Quasi-Self-Concordant Functions by Gradient Regularization of Newton Methodcited by 7
  13. 2024Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioningcited by 4
  14. 2024Optimal Oblivious Subspace Embeddings with Near-optimal Sparsitycited by 4
  15. 2024The Oracle Complexity of Simplex-based Matrix Gamescited by 4
  16. 2023A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functionscited by 3
  17. 2024Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimizationcited by 3
  18. 2025Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structurecited by 2
  19. 2026Solving Matrix Games with Near-Optimal Matvec Complexitycited by 2
  20. 2024Extracting Dual Solutions via Primal Optimizerscited by 1
  21. 2025Reusing Samples in Variance Reductioncited by 1
  22. 2025Solving Zero-Sum Games with Fewer Matrix-Vector Productscited by 1

Built on by

Not cited yet.