mlsanityData to 7 Oct 2026

Structured Semidefinite Programming for Recovering Structured Preconditioners

arXiv 2310.18265 ↗First posted 27 Oct 2023cs.DS cs.LG math.OCcited by 5

Not on the map. Why?

Abstract (arXiv)

We develop a general framework for finding approximately-optimal preconditioners for solving linear systems. Leveraging this framework we obtain improved runtimes for fundamental preconditioning and linear system solving problems including the following. We give an algorithm which, given positive definite K ∈ ℝd × d with nnz(K) nonzero entries, computes an ε-optimal diagonal preconditioner in time widetildeO(nnz(K) · poly(kappa^star,ε-1)), where kappa^star is the optimal condition number of the rescaled matrix. We give an algorithm which, given M ∈ ℝd × d that is either the pseudoinverse of a graph Laplacian matrix or a constant spectral approximation of one, solves linear systems in M in widetildeO(d2) time. Our diagonal preconditioning results improve state-of-the-art runtimes of Omega(d3.5) attained by general-purpose semidefinite programming, and our solvers improve state-of-the-art runtimes of Omega(dω) where ω > 2.3 is the current matrix multiplication constant. We attain our results via new algorithms for a class of semidefinite programs (SDPs) we call matrix-dictionary approximation SDPs, which we leverage to solve an associated problem we call matrix-dictionary recovery.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 12 of its 112 references that are in the map. First posted on arXiv 27 Oct 2023.

Builds on

12 of 112 references.

References · 12

  1. 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 401
  2. 2020Robust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packingcited by 35
  3. 2023New Bounds for Matrix Multiplication: from Alpha to Omegacited by 34
  4. 2015Algorithms for Lipschitz Learning on Graphscited by 16
  5. 2020Fast and Near-Optimal Diagonal Preconditioningcited by 9
  6. 2017Leverage Score Sampling for Faster Accelerated Regression and ERMcited by 7
  7. 2022Optimal Diagonal Preconditioningcited by 7
  8. 2017Follow the Compressed Leader: Faster Online Learning of Eigenvectors and Faster MMWUcited by 4
  9. 2018Learning Networks from Random Walk-Based Node Similaritiescited by 3
  10. 2018Efficient Structured Matrix Recovery and Nearly-Linear Time Algorithms for Solving Inverse Symmetric M-Matricescited by 1
  11. 2020Positive Semidefinite Programming: Mixed, Parallel, and Width-Independentcited by 1
  12. 2020Interpretable Personalization via Policy Learning with Linear Decision Boundariescited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 4; 2026: 1.

5 papers.

  1. 2025Model Immunization from a Condition Number Perspectivecited by 8
  2. 2025The Power of Iterative Filtering for Supervised Learning with (Heavy) Contaminationcited by 7
  3. 2025Learning Noisy Halfspaces with a Margin: Massart is No Harder than Randomcited by 5
  4. 2025Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structurecited by 2
  5. 2026Combinatorial Sparse PCA Beyond the Spiked Identity Modelcited by 0