Pith. sign in

REVIEW 4 minor 64 references

Fast, Parallel, Query-Efficient Binary Classification

T0 review · 0 major / 4 minor · reviewed 2026-07-11 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Randomized algorithms find maximum-margin separators with near-optimal matvec queries, better work, and parallel depth down to ρ^{-2/3}.

desk verdict Solid randomized algorithms that match the known matvec optimum for hard-margin SVM while improving work and depth via careful reductions and sample reuse. read the letter →

arxiv 2607.04062 v1 pith:7HSV6QQZ submitted 2026-07-05 math.OC cs.DScs.LG

Ishani Karmarkar , Liam O'Carroll , Aaron Sidford This is my paper · ORCID
classification math.OCcs.DScs.LG MSC 90C2568Q2568W2065F10
keywords binaryclassificationmaximum-marginseparatormatrixgamessubspaceembeddingsballaccelerationparallelalgorithmsmatveccomplexity
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Finding a linear separator that nearly achieves the maximum margin γ of a binary-labeled data set is a classical problem. The paper reduces it to an ℓ₂-ℓ₁ matrix game and then shows that the game can be solved by a short sequence of regularized linear systems. Those systems are solved with randomized sparse subspace embeddings and preconditioned iterative methods, reusing a single embedding across all systems. The result is two randomized algorithms that match the best known (near-optimal) number of matrix-vector queries while improving total sequential work and, in one case, parallel depth to ρ^{-2/3}. A sympathetic reader cares because the same query complexity that was previously known only for deterministic methods can now be realized with better running times and genuine parallelism once randomness is allowed.

What carries the argument

Ball-oracle acceleration that reduces the smoothed matrix game to Õ(ρ^{-2/3}) regularized linear systems, each solved by a pair of sparse oblivious subspace embeddings plus a rank-one Woodbury correction, with a single embedding reused across every system via sample-reuse.

What would settle it

Construct a data set whose Hessians make the reused embedding fail to be a constant-factor spectral approximation for more than a constant fraction of the outer-loop centers; the observed work or query count would then jump by a ρ^{-2/3} factor.

Watch

Extended reading notes

Core claim

There exist randomized algorithms that, with constant success probability, solve the ρ-separating-hyperplane problem using only Õ(ρ^{-2/3}) matrix-vector queries to the feature matrix while simultaneously achieving either Õ(ρ^{-2/3} nnz(Φ)+ρ^{-2(ω+1)/3}) work and Õ(ρ^{-2/3}) depth, or Õ(ρ^{-2/3} nnz(Φ)+ρ^{-2}) work and Õ(ρ^{-4/3}) depth.

Load-bearing premise

A single fixed random embedding can be safely reused for every adaptively chosen linear system that arises, without destroying the high-accuracy guarantees needed by the outer acceleration loop.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 4 minor

Summary. The paper studies the ρ-maximum-margin separating hyperplane problem (Definition 1.1) for a binary-labeled dataset of size n with normalized d-dimensional features. It reduces the problem to an ϵ-ℓ₂-ℓ₁ matrix game (Lemma 3.2) and then, via ball-oracle acceleration, Hessian-stable Newton methods, and approximate linear-system solves (Sections 4–5), obtains two randomized algorithms. Theorem 1.2 achieves Õ(ρ^{-2/3} nnz(Φ_D) + ρ^{-2(ω+1)/3}) work, Õ(ρ^{-2/3}) depth and Õ(ρ^{-2/3}) matvecs; Theorem 1.3 improves the work to Õ(ρ^{-2/3} nnz(Φ_D) + ρ^{-2}) at the cost of Õ(ρ^{-4/3}) depth. Both match the near-optimal deterministic matvec lower bound of recent work while improving sequential and parallel complexity through randomness and sample reuse of oblivious subspace embeddings.

Significance. If correct, the results close a natural gap left by the recent deterministic matvec-optimal algorithms of Karmarkar et al. and Kornowski–Shamir: they show that the same Õ(ρ^{-2/3}) matvec bound can be realized with near-linear work in nnz(Φ) (plus a mild poly(ρ^{-1}) term) and with substantially improved parallel depth. The reduction chain is fully explicit, the sample-reuse argument is carefully justified against the three hypotheses of Jin et al. (2026), and the comparison table (Table 1) cleanly situates the new bounds against the prior art. The work therefore constitutes a solid algorithmic advance for a classical problem in optimization and learning theory.

minor comments (4)
  1. In the abstract and Theorems 1.2–1.3 the margin parameter is written γ while the body (and Definition 1.1) uses ρ; a single consistent symbol would avoid confusion.
  2. Section 3.5 and Lemma 6.1 invoke the sample-reuse framework of [38] black-box; a one-sentence reminder of the precise statement of Theorem 2.6 of that paper would make the argument self-contained for readers who have not yet absorbed the reference.
  3. Table 1 caption states that the abstract complexities follow from ρ = γ_D/2; this is correct but could be cross-referenced more explicitly to the reduction in Appendix A.
  4. A few typographical slips remain (e.g., “fulling guarantee” in the paragraph before Lemma 5.16, occasional missing spaces after periods).

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: pure complexity reductions with verified black-box application of prior frameworks

full rationale

The paper is a self-contained algorithmic complexity result. The derivation chain (Definition 1.1 o Lemma 3.2 reduction to ℓ2-ℓ1 games o Lemma 3.3 / Section 4 ball-acceleration reduction to linear systems o Section 5 subspace-embedding + Woodbury + preconditioned FMM/SVRG solvers o Section 6 sample-reuse) consists of explicit reductions, matrix identities (Facts 5.1-5.2), and standard numerical-linear-algebra tools. All parameters (ρ, γ, ω, ε) are either problem inputs or universal constants. The sole potential soft spot—the black-box invocation of the sample-reuse framework of Jin et al. [38] (overlapping authors)—is not circular: the paper supplies the three required conditions (oblivious embedding distribution P2 depending only on sketch size, ℓ∞-robustness via Lemma 6.1, and polylog high-accuracy solvers via Lemmas 5.17-5.18) before citing Theorem 2.6 of [38]. Matching the deterministic matvec lower bound of [42,43] is an external comparison, not a self-referential derivation. No fitted parameters, self-definitional equalities, uniqueness theorems imported as external facts, or ansatzes smuggled via citation appear. Score 0 is therefore the correct outcome.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper is a pure complexity result resting on standard numerical-linear-algebra and convex-optimization primitives. No free parameters are fitted; the only external constants are the matrix-multiplication exponent omega and the existence of sparse oblivious subspace embeddings of the stated size, both taken from the literature. No new physical or mathematical entities are postulated.

assumptions (4)
  • standard math Existence of sparse oblivious (s,b,delta,lambda)-embeddings with s = O~(k) and b = O~(polylog(k/delta)) for matrices of Frobenius norm at most sqrt(k lambda) (Corollary 5.6, citing Chenakkod et al. and Cohen).
    Used to construct the low-rank preconditioners that reduce every linear system to an s x s system with s = O~(rho^{-2/3}).
  • standard math The softmax function is 1-Lipschitz, 1/alpha-smooth and 2/alpha-quasi-self-concordant (Lemma 4.13, citing Carmon et al.).
    Enables the Hessian-stability argument that lets ball-constrained Newton reduce to a constant number of quadratic subproblems.
  • standard math Ball-oracle acceleration reduces minimization of a convex Lipschitz function to O~(r^{-2/3}) regularized ball-constrained subproblems (Proposition 4.16, citing Carmon et al.).
    Supplies the outer-loop iteration count that produces the overall rho^{-2/3} factor.
  • domain assumption Sample-reuse framework of Jin et al. (2026) permits a single oblivious embedding to be shared across an adaptive sequence of high-accuracy linear systems that are ell_infty-robust.
    Invoked black-box in Section 6 to amortize the cost of constructing AT across all outer iterations; without it the leading nnz term would be larger by a rho^{-2/3} factor.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Fast, Parallel, Query-Efficient Binary Classification." pith.science (2026). https://pith.science/paper/7HSV6QQZ

@misc{pith2026260704062,
  author       = {Pith},
  title        = {Pith review of: Fast, Parallel, Query-Efficient Binary Classification},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7HSV6QQZ}},
  note         = {Machine review of arXiv:2607.04062}
}
abstract

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 \in \mathbb{R}^{n \times d}$ denote the feature matrix and $\gamma$ the margin of the maximum-margin separating hyperplane, we present a randomized algorithm that solves this problem in $\tilde{O}(\gamma^{-2/3}\, \operatorname{nnz}(\Phi) + \gamma^{-2(\omega+1)/3})$-sequential running time (work), $\tilde{O}(\gamma^{-2/3})$-parallel (computational) depth, and accesses $\Phi$ only through $\tilde{O}(\gamma^{-2/3})$-matrix-vector queries (matvecs). We also present a second, faster randomized algorithm with a $\tilde{O}(\gamma^{-2/3}\, \operatorname{nnz}(\Phi) + \gamma^{-2})$-sequential running time that uses $\tilde{O}(\gamma^{-2/3})$-matvecs to $\Phi$, but achieves only $\tilde{O}(\gamma^{-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.

Figures

Figures reproduced from arXiv: 2607.04062 by the authors.

Figure 1
Figure 1. Overview of approach. Dark-colored boxes highlight the main problems and subproblems in the method. Solid colored arrows indicate reduction steps within a single problem, while solid black arrows denote transitions between nested problems. Dotted arrows represent two alternative algorithmic approaches for solving the resulting linear systems. Here, S ∈ R s×n and T ⊤ ∈ R s×d are oblivious subspace embeddings of size … view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

64 extracted references · 5 linked inside Pith

  1. [1]

    More asymmetry yields faster matrix multiplication

    Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. More asymmetry yields faster matrix multiplication. InProceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2005–2039. SIAM, 2025

    2025

  2. [2]

    Stochastic bias- reduced gradient methods.Advances in Neural Information Processing Systems, 34:10810–10822, 2021

    Hilal Asi, Yair Carmon, Arun Jambulapati, Yujia Jin, and Aaron Sidford. Stochastic bias- reduced gradient methods.Advances in Neural Information Processing Systems, 34:10810–10822, 2021

    2021

  3. [3]

    Stochastic bias- reduced gradient methods

    Hilal Asi, Yair Carmon, Arun Jambulapati, Yujia Jin, and Aaron Sidford. Stochastic bias- reduced gradient methods. InProceedings of the 35th International Conference on Neural Information Processing Systems, NIPS ’21, Red Hook, NY, USA, 2021. Curran Associates Inc

    2021

  4. [4]

    A cutting plane algorithm for convex programming that uses analytic centers.Mathematical Programming, 69(1-3):1–43, 1995

    David S Atkinson and Pravin M Vaidya. A cutting plane algorithm for convex programming that uses analytic centers.Mathematical Programming, 69(1-3):1–43, 1995

    1995

  5. [5]

    Self-concordant analysis for logistic regression.Electronic Journal of Statistics, 4:384–414, 2010

    Francis Bach. Self-concordant analysis for logistic regression.Electronic Journal of Statistics, 4:384–414, 2010

    2010

  6. [6]

    Mirror descent and nonlinear projected subgradient methods for convex optimization.Operations Research Letters, 31(3):167–175, 2003

    Amir Beck and Marc Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization.Operations Research Letters, 31(3):167–175, 2003. ISSN 0167-6377

    2003

  7. [7]

    Curran Associates Inc., Red Hook, NY, USA, 2019

    S´ ebastien Bubeck, Qijia Jiang, Yin Tat Lee, Yuanzhi Li, and Aaron Sidford.Complexity of highly parallel non-smooth convex optimization. Curran Associates Inc., Red Hook, NY, USA, 2019

    2019

  8. [8]

    Distributionally robust optimization via ball oracle acceleration

    Yair Carmon and Danielle Hausler. Distributionally robust optimization via ball oracle acceleration. InarXiv preprint arXiv:2203.13225, 2022

    arXiv 2022

Show all 64 references
  1. [9]

    Variance reduction for matrix games

    Yair Carmon, Yujia Jin, Aaron Sidford, and Kevin Tian. Variance reduction for matrix games. InAdvances in Neural Information Processing Systems 32 (NeurIPS), 2019

    2019

  2. [10]

    Acceleration with a ball optimization oracle

    Yair Carmon, Arun Jambulapati, Qijia Jiang, Yujia Jin, Yin Tat Lee, Aaron Sidford, and Kevin Tian. Acceleration with a ball optimization oracle. InAdvances in Neural Information Processing Systems 33 (NeurIPS), 2020. 35

    2020

  3. [11]

    Coordinate methods for matrix games

    Yair Carmon, Yujia Jin, Aaron Sidford, and Kevin Tian. Coordinate methods for matrix games. In61st Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2020

    2020

  4. [12]

    Thinking inside the ball: Near-optimal minimization of the maximal loss

    Yair Carmon, Arun Jambulapati, Yujia Jin, and Aaron Sidford. Thinking inside the ball: Near-optimal minimization of the maximal loss. In34th Annual Conference on Computational Learning Theory (COLT), 2021

    2021

  5. [13]

    Optimal and adaptive monteiro-svaiter acceleration

    Yair Carmon, Danielle Hausler, Arun Jambulapati, Yujia Jin, and Aaron Sidford. Optimal and adaptive monteiro-svaiter acceleration. InProceedings of the 36th International Conference on Neural Information Processing Systems, NIPS ’22, Red Hook, NY, USA, 2022. Curran Associates Inc

    2022

  6. [14]

    Resqueing parallel and private stochastic convex optimization

    Yair Carmon, Arun Jambulapati, Yujia Jin, Yin Tat Lee, Daogao Liu, Aaron Sidford, and Kevin Tian. Resqueing parallel and private stochastic convex optimization. In64th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 2031–2058. IEEE, 2023

  7. [15]

    A whole new ball game: A primal accelerated method for matrix games and minimizing the maximum of smooth functions

    Yair Carmon, Arun Jambulapati, Yujia Jin, and Aaron Sidford. A whole new ball game: A primal accelerated method for matrix games and minimizing the maximum of smooth functions. In35th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2024

    2024

  8. [16]

    Extracting dual solutions via primal optimizers.arXiv preprint arXiv:2412.02949, 2024

    Yair Carmon, Arun Jambulapati, Liam O’Carroll, and Aaron Sidford. Extracting dual solutions via primal optimizers.arXiv preprint arXiv:2412.02949, 2024

    2024 arXiv

  9. [17]

    Optimal oblivious subspace embeddings with near-optimal sparsity.arXiv preprint arXiv:2411.08773, 2024

    Shabarish Chenakkod, Michal Derezinski, and Xiaoyu Dong. Optimal oblivious subspace embeddings with near-optimal sparsity.arXiv preprint arXiv:2411.08773, 2024

    2024 arXiv

  10. [18]

    Optimal em- bedding dimension for sparse subspace embeddings

    Shabarish Chenakkod, Michal Derezinski, Xiaoyu Dong, and Mark Rudelson. Optimal em- bedding dimension for sparse subspace embeddings. InProceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1106–1117, 2024

    2024

  11. [19]

    Low-rank approximation and regression in input sparsity time.Journal of the ACM (JACM), 63(6):1–45, 2017

    Kenneth L Clarkson and David P Woodruff. Low-rank approximation and regression in input sparsity time.Journal of the ACM (JACM), 63(6):1–45, 2017

    2017

  12. [20]

    Sublinear optimization for machine learning

    Kenneth L Clarkson, Elad Hazan, and David P Woodruff. Sublinear optimization for machine learning. InJournal of the ACM (JACM), 2012

    2012

  13. [21]

    Nearly tight oblivious subspace embeddings by trace inequalities

    Michael B Cohen. Nearly tight oblivious subspace embeddings by trace inequalities. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pages 278–287. SIAM, 2016

    2016

  14. [22]

    Optimal approximate matrix product in terms of stable rank.arXiv preprint arXiv:1507.02268, 2015

    Michael B Cohen, Jelani Nelson, and David P Woodruff. Optimal approximate matrix product in terms of stable rank.arXiv preprint arXiv:1507.02268, 2015

    2015 arXiv

  15. [23]

    Solving directed laplacian systems in nearly-linear time through sparse lu factorizations

    Michael B Cohen, Jonathan Kelner, Rasmus Kyng, John Peebles, Richard Peng, Anup B Rao, and Aaron Sidford. Solving directed laplacian systems in nearly-linear time through sparse lu factorizations. In2018 IEEE 59th annual symposium on foundations of computer science (FOCS), pag...

    2018

  16. [24]

    Solving linear programs in the current matrix multiplication time.Journal of the ACM (JACM), 68(1):1–39, 2021

    Michael B Cohen, Yin Tat Lee, and Zhao Song. Solving linear programs in the current matrix multiplication time.Journal of the ACM (JACM), 68(1):1–39, 2021

    2021

  17. [25]

    Conn, Nicholas I

    Andrew R. Conn, Nicholas I. M. Gould, and Philippe L. Toint.Trust Region Methods. MOS- SIAM Series on Optimization. SIAM, Philadelphia, PA, 2000. 36

    2000

  18. [26]

    Approaching optimality for solving dense linear systems with low-rank structure

    Michal Derezinski and Aaron Sidford. Approaching optimality for solving dense linear systems with low-rank structure. InProceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 925–938. SIAM, 2026

    2026

  19. [27]

    Faster linear systems and matrix norm approximation via multi-level sketched preconditioning

    Michal Derezinski, Christopher Musco, and Jiaming Yang. Faster linear systems and matrix norm approximation via multi-level sketched preconditioning. InProceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1972–2004. SIAM, 2025

    2025

  20. [28]

    Minimizing quasi-self-concordant functions by gradient regularization of newton method, 2023

    Nikita Doikov. Minimizing quasi-self-concordant functions by gradient regularization of newton method, 2023

    2023

  21. [29]

    Randomized smoothing for stochastic optimization.SIAM Journal on Optimization, 22(2):674–701, 2012

    John C Duchi, Peter L Bartlett, and Martin J Wainwright. Randomized smoothing for stochastic optimization.SIAM Journal on Optimization, 22(2):674–701, 2012

    2012

  22. [30]

    Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization

    Roy Frostig, Rong Ge, Sham Kakade, and Aaron Sidford. Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization. InInternational Conference on Machine Learning, pages 2540–2548. PMLR, 2015

    2015

  23. [31]

    The convergence of inexact chebyshev and richardson iterative methods for solving linear systems.Numerische Mathematik, 53(5):571–593, 1988

    Gene H Golub and Michael L Overton. The convergence of inexact chebyshev and richardson iterative methods for solving linear systems.Numerische Mathematik, 53(5):571–593, 1988

    1988

  24. [32]

    Gene H Golub and Richard S Varga. Chebyshev semi-iterative methods, successive overrelax- ation iterative methods, and second order richardson iterative methods.Milestones in Matrix Computation-Selected Works of Gene H. Golub, with Commentaries, pages 45–67, 2007

    2007

  25. [33]

    A sublinear-time randomized approximation algorithm for matrix games

    Michael D Grigoriadis and Leonid G Khachiyan. A sublinear-time randomized approximation algorithm for matrix games. InOperations Research Letters, 1995

    1995

  26. [34]

    Liu, and Aaron Sidford

    Arun Jambulapati, Yang P. Liu, and Aaron Sidford. Improved iteration complexities for overconstrained p-norm regression. InProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, pages 529–542, New York, NY, USA, 2022. Association for Computing M...

    2022

  27. [35]

    Closing the computational-query depth gap in parallel stochastic convex optimization

    Arun Jambulapati, Aaron Sidford, and Kevin Tian. Closing the computational-query depth gap in parallel stochastic convex optimization. InThe Thirty Seventh Annual Conference on Learning Theory, pages 2608–2643. PMLR, 2024

    2024

  28. [36]

    Closing the computational-query depth gap in parallel stochastic convex optimization

    Arun Jambulapati, Aaron Sidford, and Kevin Tian. Closing the computational-query depth gap in parallel stochastic convex optimization. InAnnual Conference Computational Learning Theory, 2024

    2024

  29. [37]

    An improved cutting plane method for convex optimization, convex-concave games, and its applications

    Haotian Jiang, Yin Tat Lee, Zhao Song, and Sam Chiu-wai Wong. An improved cutting plane method for convex optimization, convex-concave games, and its applications. InProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, page 944–953, New York, ...

    2020 doi

  30. [38]

    Reusing samples in variance reduction

    Yujia Jin, Ishani Karmarkar, Aaron Sidford, and Jiayi Wang. Reusing samples in variance reduction. InAlgorithmic Learning Theory, 2026

    2026

  31. [39]

    Accelerating stochastic gradient descent using predictive variance reduction.Advances in neural information processing systems, 26, 2013

    Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction.Advances in neural information processing systems, 26, 2013. 37

    2013

  32. [40]

    Stich, and Martin Jaggi

    Sai Praneeth Karimireddy, Sebastian U. Stich, and Martin Jaggi. Global linear conver- gence of newton’s method without strong-convexity or lipschitz gradients. InarXiv preprint arXiv:1806.00413, 2018

    2018 arXiv

  33. [41]

    Solving zero-sum games with fewer matrix-vector products

    Ishani Karmarkar, Liam O’Carroll, and Aaron Sidford. Solving zero-sum games with fewer matrix-vector products. In66th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2025

    2025

  34. [42]

    Solving matrix games with near-optimal matvec complexity.58th Annual ACM Symposium on Theory of Computing (STOC), pages arXiv–2601, 2026

    Ishani Karmarkar, Liam O’Carroll, and Aaron Sidford. Solving matrix games with near-optimal matvec complexity.58th Annual ACM Symposium on Theory of Computing (STOC), pages arXiv–2601, 2026

    2026

  35. [43]

    The oracle complexity of simplex-based matrix games: Linear separability and nash equilibria

    Guy Kornowski and Ohad Shamir. The oracle complexity of simplex-based matrix games: Linear separability and nash equilibria. In38th Annual Conference on Computational Learning Theory (COLT), 2025

    2025

  36. [44]

    The oracle complexity of simplex-based matrix games: Linear separability and nash equilibria

    Guy Kornowski and Ohad Shamir. The oracle complexity of simplex-based matrix games: Linear separability and nash equilibria. InarXiv preprint 2412.06990 [v3], 2025

    2025

  37. [45]

    A faster cutting plane method and its implications for combinatorial and convex optimization

    Yin Tat Lee, Aaron Sidford, and Sam Chiu-Wai Wong. A faster cutting plane method and its implications for combinatorial and convex optimization. In2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 1049–1065, 2015. doi: 10.1109/FOCS.2015.68

    2015 doi

  38. [46]

    A universal catalyst for first-order optimiza- tion.Advances in neural information processing systems, 28, 2015

    Hongzhou Lin, Julien Mairal, and Zaid Harchaoui. A universal catalyst for first-order optimiza- tion.Advances in neural information processing systems, 28, 2015

    2015

  39. [47]

    A logical calculus of the ideas immanent in nervous activity

    Warren S McCulloch and Walter Pitts. A logical calculus of the ideas immanent in nervous activity. InThe bulletin of mathematical biophysics, 1943

    1943

  40. [48]

    Kernel-based svm

    MN Murty and Rashmi Raghava. Kernel-based svm. InSupport vector machines and perceptrons: Learning, optimization, classification, and application to social networks, pages 57–67. Springer, 2016

    2016

  41. [49]

    Osnap: Faster numerical linear algebra algorithms via sparser subspace embeddings

    Jelani Nelson and Huy L Nguyˆ en. Osnap: Faster numerical linear algebra algorithms via sparser subspace embeddings. In2013 ieee 54th annual symposium on foundations of computer science, pages 117–126. IEEE, 2013

    2013

  42. [50]

    On parallel complexity of nonsmooth convex optimization.Journal of Complexity, 10(4):451–463, 1994

    Arkadi Nemirovski. On parallel complexity of nonsmooth convex optimization.Journal of Complexity, 10(4):451–463, 1994

    1994

  43. [51]

    Prox-method with rate of convergence o(1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems

    Arkadi Nemirovski. Prox-method with rate of convergence o(1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):229–251, 2004

    2004

  44. [52]

    Problem complexity and method efficiency in optimization

    Arkadij Semenoviˇ c Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. InWiley-Interscience, 1983

    1983

  45. [53]

    Smooth minimization of non-smooth functions

    Yu Nesterov. Smooth minimization of non-smooth functions. InMathematical programming, 2005

    2005

  46. [54]

    Dual extrapolation and its applications to solving variational inequalities and related problems.Mathematical Programming, 109(2):319–344, Mar 2007

    Yurii Nesterov. Dual extrapolation and its applications to solving variational inequalities and related problems.Mathematical Programming, 109(2):319–344, Mar 2007. 38

    2007

  47. [55]

    Stochastic variance reduction methods for saddle-point problems

    Balamurugan Palaniappan and Francis Bach. Stochastic variance reduction methods for saddle-point problems. InAdvances in Neural Information Processing Systems 29 (NeurIPS), 2016

    2016

  48. [56]

    Victor Y. Pan. Complexity of parallel matrix computations.Theoretical Computer Science, 54: 65–85, 1987

    1987

  49. [57]

    Pan and John H

    Victor Y. Pan and John H. Reif. Efficient parallel solution of linear systems. InProceedings of the 17th Annual ACM Symposium on Theory of Computing, pages 143–152. ACM, 1985

    1985

  50. [58]

    Rakhlin and K

    A. Rakhlin and K. Sridharan. Online learning with predictable sequences. InProceedings of the 26th Annual Conference on Learning Theory, volume 30 ofProceedings of Machine Learning Research, pages 993–1019. PMLR, 2013

    2013

  51. [59]

    The perceptron: a probabilistic model for information storage and organiza- tion in the brain

    Frank Rosenblatt. The perceptron: a probabilistic model for information storage and organiza- tion in the brain. InPsychological review, 1958

    1958

  52. [60]

    Improved approximation algorithms for large matrices via random projections

    Tamas Sarlos. Improved approximation algorithms for large matrices via random projections. In2006 47th annual IEEE symposium on foundations of computer science (FOCS’06), pages 143–152. IEEE, 2006

    2006

  53. [61]

    Quantum speedups for stochastic optimization

    Aaron Sidford and Chenyi Zhang. Quantum speedups for stochastic optimization. InProceedings of the 37th International Conference on Neural Information Processing Systems, NIPS ’23, Red Hook, NY, USA, 2023. Curran Associates Inc

    2023

  54. [62]

    Generalized self-concordant functions: a recipe for newton- type methods.Mathematical Programming, 178(1-2):145–213, 2019

    Tianxiao Sun and Quoc Tran-Dinh. Generalized self-concordant functions: a recipe for newton- type methods.Mathematical Programming, 178(1-2):145–213, 2019

    2019

  55. [63]

    Pravin M. Vaidya. A new algorithm for minimizing convex functions over convex sets (extended abstract). InFOCS, pages 338–343, 1989

    1989

  56. [64]

    Minimum cost flows, mdps, and l1-regression in nearly linear time for dense instances

    Jan Van Den Brand, Yin Tat Lee, Yang P Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang. Minimum cost flows, mdps, and l1-regression in nearly linear time for dense instances. InProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021. ...

    2021

Pith tools

Reviewed July 11, 2026 · model on record in the stance chip above.