mlsanityData to 7 Oct 2026

Solving SDP Faster: A Robust IPM Framework and Efficient Implementation

arXiv 2101.08208 ↗First posted 20 Jan 2021math.OC cs.DScited by 33

Not on the map. Why?

Abstract (arXiv)

This paper introduces a new robust interior point method analysis for semidefinite programming (SDP). This new robust analysis can be combined with either logarithmic barrier or hybrid barrier. Under this new framework, we can improve the running time of semidefinite programming (SDP) with variable size n × n and m constraints up to ε accuracy. We show that for the case m = Omega(n2), we can solve SDPs in mω time. This suggests solving SDP is nearly as fast as solving the linear system with equal number of variables and constraints. This is the first result that tall dense SDP can be solved in the nearly-optimal running time, and it also improves the state-of-the-art SDP solver [Jiang, Kathuria, Lee, Padmanabhan and Song, FOCS 2020]. In addition to our new IPM analysis, we also propose a number of techniques that might be of further interest, such as, maintaining the inverse of a Kronecker product using lazy updates, a general amortization scheme for positive semidefinite matrices.

Key facts. Cited by 33 papers in the map (data through 7 Oct 2026). First posted on arXiv 20 Jan 2021.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

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

33 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. 2023An Iterative Algorithm for Rescaled Hyperbolic Functions Regressioncited by 35
  6. 2024LazyDiT: Lazy Learning for the Acceleration of Diffusion Transformerscited by 35
  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. 2022Training Overparametrized Neural Networks in Sublinear Timecited by 22
  12. 2022A Sublinear Adversarial Training Algorithmcited by 22
21 more
  1. 2021Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structurescited by 19
  2. 2024A Tighter Complexity Analysis of SparseGPTcited by 19
  3. 2022Federated Adversarial Learning: A Framework with Convergence Analysiscited by 17
  4. 2022Dynamic Tensor Product Regressioncited by 17
  5. 2023A General Algorithm for Solving Rank-one Matrix Sensingcited by 15
  6. 2022Adaptive and Dynamic Multi-Resolution Hashing for Pairwise Summationscited by 14
  7. 2023Federated Empirical Risk Minimization via Second-Order Methodcited by 9
  8. 2024Oja's Algorithm for Streaming Sparse PCAcited by 9
  9. 2024Fast John Ellipsoid Computation with Differential Privacy Optimizationcited by 7
  10. 2023Convergence of Two-Layer Regression with Nonlinear Unitscited by 6
  11. 2023Structured and Fast Optimization: The Kronecker SGD Algorithmcited by 5
  12. 2023Matrix Completion in Almost-Verification Timecited by 4
  13. 2024Learning multivariate Gaussians with imperfect advicecited by 4
  14. 2025The Structural Complexity of Matrix-Vector Multiplicationcited by 4
  15. 2022Efficient Algorithms for Sparse Moment Problems without Separationcited by 3
  16. 2021A Worker-Task Specialization Model for Crowdsourcing: Efficient Inference and Fundamental Limitscited by 2
  17. 2024Binary Hypothesis Testing for Softmax Models and Leverage Score Modelscited by 1
  18. 2025Accept More, Reject Less: Reducing up to 19% Unnecessary Desk-Rejections over 11 Years of ICLR Datacited by 1
  19. 2024Variational Inference on the Boolean Hypercube with the Quantum Entropycited by 0
  20. 2026Lifted Relational Probabilistic Inference via Implicit Learningcited by 0
  21. 2026Combinatorial Sparse PCA Beyond the Spiked Identity Modelcited by 0