mlsanityData to 7 Oct 2026

A Faster Interior Point Method for Semidefinite Programming

arXiv 2009.10217 ↗First posted 21 Sep 2020cs.DS math.OCcited by 53

Not on the map. Why?

Abstract (arXiv)

Semidefinite programs (SDPs) are a fundamental class of optimization problems with important recent applications in approximation algorithms, quantum complexity, robust learning, algorithmic rounding, and adversarial deep learning. This paper presents a faster interior point method to solve generic SDPs with variable size n × n and m constraints in time beginalign* widetildeO(√n( mn2 + mω + nω) log(1 / ε) ), endalign* where ω is the exponent of matrix multiplication and ε is the relative accuracy. In the predominant case of m ≥ n, our runtime outperforms that of the previous fastest SDP solver, which is based on the cutting plane method of Jiang, Lee, Song, and Wong [JLSW20]. Our algorithm's runtime can be naturally interpreted as follows: widetildeO(√n log (1/ε)) is the number of iterations needed for our interior point method, mn2 is the input size, and mω + nω is the time to invert the Hessian and slack matrix in each iteration. These constitute natural barriers to further improving the runtime of interior point methods for solving generic SDPs.

Key facts. Cited by 53 papers in the map (data through 7 Oct 2026). First posted on arXiv 21 Sep 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 8; 2022: 7; 2023: 16; 2024: 13; 2025: 6; 2026: 3.

53 papers.

Sort:

By area:

  1. 2023H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Modelscited by 805
  2. 2021Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Timecited by 62
  3. 2023Attention Scheme Inspired Softmax Regressioncited by 49
  4. 2023Solving Regularized Exp, Cosh and Sinh Regression Problemscited by 44
  5. 2024LazyDiT: Lazy Learning for the Acceleration of Diffusion Transformerscited by 35
  6. 2021Does Preprocessing Help Training Over-parameterized Neural Networks?cited by 32
  7. 2023Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Timecited by 31
  8. 2023A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Timecited by 30
  9. 2023A Mathematical Abstraction for Balancing the Trade-off Between Creativity and Reality in Large Language Modelscited by 29
  10. 2023InfoPrompt: Information-Theoretic Soft Prompt Tuning for Natural Language Understandingcited by 29
  11. 2022A Sublinear Adversarial Training Algorithmcited by 22
  12. 2021Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structurescited by 19
38 more
  1. 2024A Tighter Complexity Analysis of SparseGPTcited by 19
  2. 2022Federated Adversarial Learning: A Framework with Convergence Analysiscited by 17
  3. 2022Dynamic Tensor Product Regressioncited by 17
  4. 2023A General Algorithm for Solving Rank-one Matrix Sensingcited by 15
  5. 2022Adaptive and Dynamic Multi-Resolution Hashing for Pairwise Summationscited by 14
  6. 2023Solving Dense Linear Systems Faster Than via Preconditioningcited by 12
  7. 2023Optimal Embedding Dimension for Sparse Subspace Embeddingscited by 11
  8. 2023Federated Empirical Risk Minimization via Second-Order Methodcited by 9
  9. 2024Oja's Algorithm for Streaming Sparse PCAcited by 9
  10. 2024Fast John Ellipsoid Computation with Differential Privacy Optimizationcited by 7
  11. 2022Sketch-and-Lift: Scalable Subsampled Semidefinite Program for K-means Clusteringcited by 6
  12. 2023Structured and Fast Optimization: The Kronecker SGD Algorithmcited by 5
  13. 2021Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Timecited by 4
  14. 2023Matrix Completion in Almost-Verification Timecited by 4
  15. 2024Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioningcited by 4
  16. 2025The Structural Complexity of Matrix-Vector Multiplicationcited by 4
  17. 2025Online Decision-Focused Learningcited by 4
  18. 2025Quantum thermodynamics and semi-definite optimizationcited by 3
  19. 2021Spectral Robustness for Correlation Clustering Reconstruction in Semi-Adversarial Modelscited by 2
  20. 2021A Worker-Task Specialization Model for Crowdsourcing: Efficient Inference and Fundamental Limitscited by 2
  21. 2022Community Detection in the Hypergraph SBM: Exact Recovery Given the Similarity Matrixcited by 2
  22. 2022Likelihood Adjusted Semidefinite Programs for Clustering Heterogeneous Datacited by 2
  23. 2024Faster Convergence with Less Communication: Broadcast-Based Subgraph Sampling for Decentralized Learning over Wireless Networkscited by 2
  24. 2024Overlay-based Decentralized Federated Learning in Bandwidth-limited Networkscited by 2
  25. 2025Constrained free energy minimization for the design of thermal states and stabilizer thermodynamic systemscited by 2
  26. 2025Estimating Ising Models in Total Variation Distancecited by 2
  27. 2021Conditional Linear Regression for Heterogeneous Covariancescited by 1
  28. 2021Faster Algorithms and Constant Lower Bounds for the Worst-Case Expected Errorcited by 1
  29. 2023Information-Theoretic Limits and Strong Consistency on Binary Non-uniform Hypergraph Stochastic Block Modelscited by 1
  30. 2023When Collaborative Filtering is not Collaborative: Unfairness of PCA for Recommendationscited by 1
  31. 2024Energy-efficient Decentralized Learning via Graph Sparsificationcited by 1
  32. 2024RedEx: Beyond Fixed Representation Methods via Convex Optimizationcited by 1
  33. 2024Quantum Speedup for Spectral Approximation of Kronecker Productscited by 1
  34. 2024A Sub-Quadratic Time Algorithm for Robust Sparse Mean Estimationcited by 1
  35. 2024Binary Hypothesis Testing for Softmax Models and Leverage Score Modelscited by 1
  36. 2025Accept More, Reject Less: Reducing up to 19% Unnecessary Desk-Rejections over 11 Years of ICLR Datacited by 1
  37. 2026On the Expressive Power of GNNs to Solve Linear SDPscited by 1
  38. 2026Active Learning for Stochastic Contextual Linear Banditscited by 1

50 most cited of 53 All 53 (JSON)