# A Faster Interior Point Method for Semidefinite Programming

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

## Key facts

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

## Built on by (most cited first, 30 of 53)

- [H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models](https://mlsanity.com/paper/2306.14048/) (2023)
- [Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time](https://mlsanity.com/paper/2112.07628/) (2021)
- [Attention Scheme Inspired Softmax Regression](https://mlsanity.com/paper/2304.10411/) (2023)
- [Solving Regularized Exp, Cosh and Sinh Regression Problems](https://mlsanity.com/paper/2303.15725/) (2023)
- [LazyDiT: Lazy Learning for the Acceleration of Diffusion Transformers](https://mlsanity.com/paper/2412.12444/) (2024)
- [Does Preprocessing Help Training Over-parameterized Neural Networks?](https://mlsanity.com/paper/2110.04622/) (2021)
- [Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time](https://mlsanity.com/paper/2302.11068/) (2023)
- [InfoPrompt: Information-Theoretic Soft Prompt Tuning for Natural Language Understanding](https://mlsanity.com/paper/2306.04933/) (2023)
- [A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Time](https://mlsanity.com/paper/2309.07418/) (2023)
- [A Mathematical Abstraction for Balancing the Trade-off Between Creativity and Reality in Large Language Models](https://mlsanity.com/paper/2306.02295/) (2023)
- [A Sublinear Adversarial Training Algorithm](https://mlsanity.com/paper/2208.05395/) (2022)
- [Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structures](https://mlsanity.com/paper/2111.15139/) (2021)
- [A Tighter Complexity Analysis of SparseGPT](https://mlsanity.com/paper/2408.12151/) (2024)
- [Federated Adversarial Learning: A Framework with Convergence Analysis](https://mlsanity.com/paper/2208.03635/) (2022)
- [Dynamic Tensor Product Regression](https://mlsanity.com/paper/2210.03961/) (2022)
- [A General Algorithm for Solving Rank-one Matrix Sensing](https://mlsanity.com/paper/2303.12298/) (2023)
- [Adaptive and Dynamic Multi-Resolution Hashing for Pairwise Summations](https://mlsanity.com/paper/2212.11408/) (2022)
- [Solving Dense Linear Systems Faster Than via Preconditioning](https://mlsanity.com/paper/2312.08893/) (2023)
- [Optimal Embedding Dimension for Sparse Subspace Embeddings](https://mlsanity.com/paper/2311.10680/) (2023)
- [Federated Empirical Risk Minimization via Second-Order Method](https://mlsanity.com/paper/2305.17482/) (2023)
- [Oja's Algorithm for Streaming Sparse PCA](https://mlsanity.com/paper/2402.07240/) (2024)
- [Fast John Ellipsoid Computation with Differential Privacy Optimization](https://mlsanity.com/paper/2408.06395/) (2024)
- [Sketch-and-Lift: Scalable Subsampled Semidefinite Program for K-means Clustering](https://mlsanity.com/paper/2201.08226/) (2022)
- [Structured and Fast Optimization: The Kronecker SGD Algorithm](https://mlsanity.com/paper/2305.08001/) (2023)
- [Quantum thermodynamics and semi-definite optimization](https://mlsanity.com/paper/2505.04514/) (2025)
- [Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time](https://mlsanity.com/paper/2107.08090/) (2021)
- [Matrix Completion in Almost-Verification Time](https://mlsanity.com/paper/2308.03661/) (2023)
- [Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning](https://mlsanity.com/paper/2405.05865/) (2024)
- [The Structural Complexity of Matrix-Vector Multiplication](https://mlsanity.com/paper/2502.21240/) (2025)
- [Online Decision-Focused Learning](https://mlsanity.com/paper/2505.13564/) (2025)

## 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.