Structured Semidefinite Programming for Recovering Structured Preconditioners
Authors: Arun Jambulapati
Jerry Li
Christopher Musco
Kirankumar Shiragur
Aaron Sidford
Kevin Tian
Venue: NeurIPS 2023 poster (2023)
Keywords: preconditioning
semidefinite programming
numerical linear algebra
linear regression
semi-random models
TL;DR: We give the first near-linear time constructions of optimal diagonal preconditioners and families of structured linear system solvers, improving the state-of-the-art by factors polynomial in the dimension.

Abstract: 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:
Diagonal preconditioning. We give an algorithm which, given positive definite $\mathbf{K} \in \mathbb{R}^{d \times d}$ with $\mathrm{nnz}(\mathbf{K})$ nonzero entries, computes an $\epsilon$-optimal diagonal preconditioner in time $\widetilde{O}(\mathrm{nnz}(\mathbf{K}) \cdot \mathrm{poly}(\kappa^\star,\epsilon^{-1}))$, where $\kappa^\star$ is the optimal condition number of the rescaled matrix.
Structured linear systems. We give an algorithm which, given $\mathbf{M} \in \mathbb{R}^{d \times d}$ that is either the pseudoinverse of a graph Laplacian matrix or a constant spectral approximation of one, solves linear systems in $\mathbf{M}$ in $\widetilde{O}(d^2)$ time. 
Our diagonal preconditioning results improve state-of-the-art runtimes of $\Omega(d^{3.5})$ attained by general-purpose semidefinite programming, and our solvers improve state-of-the-art runtimes of $\Omega(d^{\omega})$ where $\omega > 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.

Structured Semidefinite Programming for Recovering Structured Preconditioners
Arun Jambulapati Simons Institute" jmblpati@@erkeley.ooo
Christopher Musco New York University
Jerry Li Microsoft Research
cmusco@nyu.c edu
perr@@microsof com
Kirankumar Shiragur
Aaron Sidford
Broad Institute of MIT and Harvard shiragurOstanf ord.odd.dd
Stanford University
eidfordestanfore edu
Kevin Tian
University of Texas at Austin kjt kjtianecs. utexas.e..... edu
Abstract
We develop a general framework for finding opproximately-optinee preconditioners for solving linear systems. Leveraging this framework obtain improved runtimes for fundamental preconditioning and linear system solving problems including:
Diagonal preconditioning. We give an algorithm which, given positive definite K E aadd with nnz(K) nonzero entries, computes an c-optimal
diagonal preconditioner in time O(mnz(K) poly(s",, where x² is the optimal condition number of the rescaled matrix.
Structured linear systems. We give an algorithm which, given M E Raxd that either the pseudoinverse of graph Laplacian matrix constant spectral approximation of one, solves linear systems in M Ö(d) time.
Our diagonal preconditioning results improve state-of-the-art runtimes of (d attained by general-purpose purpose semidefinite programming, and our solvers improve state-of-the- runtimes of (2d") where w 2.3 is the current matrix multiplica- tion constant. We attain results via algorithms for class of semidefinite programs (SDPs) we call matrix-dictinary approximation SDPs, which we lever- age solve an associated problem call matrix- dictiooarry recovery.
Introduction
Preconditioning is fundamental primitive in the theory and practice of numerical linear algebra, optimization, and data science. Broadly, its goal is to improve conditioning properties (e.g., the range of eigenvalues) of matrix M by finding another matrix N which approximates the inverse of M and is more efficient to construct and apply than computing M-1, This strategy underpins a variety of popular revellly-develoeed tools, such adaptive gradient methods for machine learning (e.g.. Adagrad and Adam [DHSTI KB15),, and near-linear time solvers for combinatoriallyysstctuure
"Work completed at Stanford and the University of Washington.
Work completed Stanford. I Work completed at Stanford and Microsoft Research.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

matrices (e.g., graph Laplacians (ST04).. Despite widespread practical adoption of such techniques, there is surprising lack of provably efficient algorithms for preconditioning.
Our work introduces a new tool, matrix-dictionary recovery, and leverages it to obtain the first near- linear time algorithms for several structured preconditioning problems in well-studied applications. Informally, the problem we study is as follows (see Section for the formal definition).
Given a malrix M and a "matrix-dictionar" { find the best preconditioner
N Σ w,M, of M expressible as a nonnegative linear combination of {M:).
(I)
We develop general-purpon solvers for the problem (I. We further apply these solvers obtain state- of-the-art algorithms for fundamental tasks such as preconditioning linear systems and regression, and approximately recovering structured matrices, including the following results.
Diagonal preconditioning. We consider the classical numerical linear algebra problem of diagonal preconditioning [vdS69]. Given K E Sy-0- the goal is to find a diagonal W E 8 minimizing the condition number of W W W'WW Theorem obtains the first near-linear time algorithms for this problem when the optimal condition number of the rescaled matrix is small.
Semi-random regression. We consider a related problem, motivated by semi-random noise models, which takes full-rank A E IRaxd with 2 d and seeks W S minimizing the condition number of A WA. Theorem 2 gives the first near-linear time algorithm for this problem, and applications reduce risk bounds for statistical linear regression.
Structured linear systems. We robustify Laplacian system solvers, e.g., STO4, to obtain near- linear time solvers for systems in dense matrices well-approximated spectrally by Laplacians in Theorem 3 We also give new near-linear time solvers for several families of structured matrices, e.g., dense inverse Laplacians and M-matrices in Theorems and
For the preconditioning problems considered in Theorems
and 3 we give the first runtimes
faster than generic SDP solver, for which, state-of-the-art runtimes [JKI 20 HJJS-22 are highly
superlinear ($25)) for diagonal preconditioning and 5 ((d2w) for approximating Laplacians, where
is the matrix dimension and w > 2.3 is the current matrix multiplication constant (AW1I) l). For the corresponding linear system solving problems in each case, as well as in Theorems
and the prior lfte-of-theeart was to treat the linear system as generic and ran in M(d time.
Organization. We begin by overviewing the main applications of our matrix-dictiona recovery framework in Sections 2 and which respectively cover our results on diagonal preconditioning and structured linear algebra. These sections are self-contained (with some definitions of the matrix families we study
to the supplementary material), and can be read independently. In Section 4 we contextualize and formalize the general matrix-dictionary recovery problem (I) we introduce and study. We also provide our main meta-algorithm and its guarantees, and an overview of how the results of Sections 2
and follow from applications of it. We finally compare our framework to related algorithms and give a more thorough runtime comparison Scction 5
Notation. In Section (focusing on diagonal preconditioning and semi-random regression) only, we refer to the matrices be preconditioned as K or A. This is for consistency with the numerical linear algebra literature, where K represents a positive definite kernel matrix, and A denotes the data in regression problem min, ||A. bll2- the rest of the paper, our notation will be consistent with { The d x d symmetric matrices are Sd the positive semidefinite (PSD) and definite (PD) cones S and Sd the remainder of our notation is standard and deferred to Section 2 of the supplement.
Diagonal preconditioning
When solving linear systems via iterative methods, one of the most popular preconditioning strategies use diagonal matrix. This is appealing because diagonal matrices be applied and inverted quickly. Determining the best diagonal preconditioner is a classical numerical linear algebra problem studied since the 1950s [F555 vdS69 PG90], and has gained recent popularity due to its in adaptive gradient methods [DHS KB15). In Section 4 we discuss how diagonal preconditioning
Inverse M-matrices necessarily dense, Appendix B of the supplementary material.

---

is an instance of (I in the matrix- dictionary M, = =,,, where e; is the 1th basis vector. Leveraging this viewpoint, we design algorithms for two natural instantiations of diagonal preconditioning.
Outer scaling, One formulation of the optimal diagonal preconditioning problem, which we refer to as outer scaling, asks optimally reduce the condition number of positive definite K Raxd with diagonal matrix W, i.c., return diagonal W = diag (w) for w E B5.00 such tha
k( W 3 kW K. (K) :=
min K: x(W diagoral W
Given W, solution to K. can be obtained by solving the better-condine contitecodd W
W and returning w The optimal W can be obtained via semidefinite program (SDP) [QZZ20], but the computational cost of general-purpose SDP solvers outweighs benefits for solving linear systems. Outer scaling is poorly understood algorithmically; prior our work, even attaining a constant-factor approximation to (K) without a generic SDP solver was unknown.
This state of affairs has resulted in the widespread preconditioning [vdS69] [R89] and matrix scaling [AZLOW17 CMTV17al [O188. The former strategy, where the preconditioner is taken as the inverse diagonal to K, was notably highlighted by Adagrad [HST]] which used Jacobi preconditioning to improve computational costs. However, both heuristics have clear drawbacks from theoretical or practical perspectives.
of heuristics for constructing W, such as Jacobi
Prior to our work the best approximation guarantee known for Jacobi preconditioning was a result of van der Sluis [vdS69 GR89), which shows the Jacobi preconditioner is m-factor approximation to the optimal preconditioning problem where m S d is the maximum number of non-zeros in any row of K: in dense matrices this is linear in the problem dimension and can be much larger than K (K). We review and slightly strengthen this result in Appendix C of the supplement. We also prove a new dimension condition number no worse than (x,, (K))². Unfortunately, we exhibit a family of matrices showing this bound is tight, dashing hopes they solve outer scaling near-optimally. On the other hand, while sometimes effective as a heuristic [KU144, matrix scaling algorithms target a different objective (normalizing row and column sums) and do not yield provable guarantees on K( x(W à KW?).
dimeesioon-indepedder independent baseline result of independent interest: the Jacobi preconditioner obtains
Inner scaling, Another formulation of diagonal preconditioning, which we refer to as inner scaling, takes as input full-rank A E Rxx and asks to find an n x n positive diagonal W with
x(A WA) (A)
min diagonal W
<(A WA).
As comparison. when outer scaling is applied to the kernel matrix K A W can be seen as rescaling the columns of A. On the other hand, in inner scaling we instead rescale rows of A. Inner scaling has natural applications to improving risk bounds a robust statistical variant of linear regression, which we comment upon shortly. Nonetheless, as in the outer scaling case, no algorithms faster than general SDP solvers are known to obtain even a constant- factor approximation k; (A). Further, despite clear problem similarities, it is unclear how to best extend heuristics (e.g.. Jacobi preconditioning and matrix scaling) for outer scaling to inner scaling.
Our results. We give the first nontrivial approximation algorithms (beyond generic SDP solvers) for both the outer and inner scaling problems, yielding diagonal preconditioners attaining constant- factor approximations to KN and ne in near- near-lineat linear time Tmv (M) denotes the time required to multiply a vector by M; this is at most the sparsity of M, but can be substantially faster for structured M.
Theorem 1 (Outer scaling). Let e > 0 be a fixed constant There is an algorithm, which given full-rank K E Sd computes w E RR such that k( kW:) S (1 + (K)) with probability
2 1 8 in time (TTme(K) (K)) polylog( (mn,(k)) 1)-
Theorem 2 (Inner scaling). Let e > 0 be fixed constant. There is an algorithm, which given
full-rank A E x for n 2 d computes w E IR2, such that k(A T WA) S (1 c)n} (A) with
probability 2 8 in time (A) (x)(
polylog( (MAT(A)))
*x(M) is the condition number of positive definite M. i.c. the eigenvalue ratio Amax /mii (M)/Amin(MM
'We are not currently aware of a variant of our matrix dictionary recovery framework which extends to simultaneous inner and outer scaling, though it is worth noting that prior work (QGH 22) does obtain such result via semidefinite programming. Obtaining such a variant is an interesting open problem for future work. We do not focus on the dependence and instead take it to be constant since. in applications involving solving linear systems, there is little advantage obtaining better than 2 2-approximation (i.e.. 1).
3

---

Our methods pay a small polynomial overhead in the quantities KC and kY but notably suffer no dependence on the original conditioning of the matrices. Typically, the interesting use case for diagonal preconditioning is when K (K) or K (A) is small but < ((() or *(A A) is large, a regime where our runtimes are near-linear and substantially faster than directly applying iterative methods.
It is worth noting that in light of our new results on Jacobi preconditioning, the end-to-end runtime of Theorem for solving linear systems (rather than optimal preconditioning) can be improved: accelerated gradient methods on preconditioned system with condition number (x²)² have runtimes scaling as kg- That said, when repeatedly solving multiple systems in the same matrix, Theorem [ may offer an advantage over Jacobi preconditioning. Our framework also gives a potential route to achieve the optimal end-to-end runtime scaling as VKy, detailed in Appendix D of the supplement.
Beyond that which is obtainable by black-box using general SDP solvers, we are not aware of any other claimed runtime in the literature for solving the inner and outer scaling problems considered in Theorems I and 2 Directly using state-of-the-an SDP solvers [J 22) incurs substantial
overhead (1 vd + ndd2.5) or 12 + d + n1² Vd), where w < 2.372 is the current matrix multiplication constant [Wil12] Gall4 AW21 DW723 WXXZ23] For outer scaling, where n d, this implies an (2(d5.5) runtime; for other applications, e.g., preconditioning d x d perturbed Laplacians where n d², the runtime is (dd22)) Applying state-of-the-arr approximate SDP solvers (rather than our custom ones, i.c., Theorems 6 and 7 appears to yield runtimes 52 (Z(zz A) dd2-5,, as described in Appendix E.2 of [LSTZ20]. This is in contrast with our Theorems T 2 which achieve
Ô (A) (..)). Hence, we improve existing tools by poly(d) factors in the main regime of interest where the optimal rescaled condition number x* is small. Concurrent to our work, [QGH* 22) gave algorithms for constructing optimal diagonal preconditioners using interior point methods for SDPs, which run in at least the superlinear times discussed previously.
Statistical aspects of preconditioning. Unlike an outer scaling, a good inner scaling does not speed up a least squares regression problem min, Ar bll2. Instead, it allows for a faster solution to the reweighted problem ming [W (Az b) This has a number of implications from a statistical perspective. We explore interesting connection between inner scaling preconditoning and semi-random noise models for least-squares regression, situated in the literature in Section [
As motivating example of our noise model, consider the case when there is a hidden parameter vector Tim E Rdd that we want to recover, and we have a "good" set of consistent observations A, = by. in the sense that xi( [A] A,) is small. Here, we can think of Ag as being drawn from a well-conditioned distribution. Now, suppose an adversary gives us a superset of these observations (A, b) such that Avimme = b, and A, are an (unknown) subset of rows of A, but x(A A) > k(A,
g Ag)- This can
occur when rows are sampled from heterogeneous sources. Perhaps counterintuitively, by giving additional consistent data, the adversary can arbitrarily hinder the cost of iterative methods. This failure can be interpreted as being due to overfitting to generative assumptions (e.g., sampling rows from well-conditioned covariance, instead of mixture): standard iterative methods assume too much structure, where ideally they would use as little as iiformation-theoreiice
possible.
Our inner scaling methods random noise models (by finding W yielding a rescaled condition number comparable or better than the indicator of the rows of A.,. which are not known a priori). In Section 6 of the supplement, we demonstrate applications of inner scaling in reducing the mean-squared error risk in statistical regression settings encompassing our semi-random noise model, where the observations b are corrupted by (homoskedastic or heteroskedastic) noise. In all settings, our preconditioning algorithms yield computational gains, improved risk bounds, or both, by factors of roughly <(AA A) /x) (A).
be viewed as "robustifying" linear system solving to such semi-
3 Robust linear algebra for structured matrices
Over the past decade, the theoretical computer science and numerical linear algebra communities have dedicated substantial effort to developing faster solvers for regression problems in various families of combinatorially-struutt gave a near-linear time solver for linear systems in graph Laplacian matrices 8 A long line of exciting
matrices. Perhaps the most prominent example (ST04), who
We recall definitions of the families of matrices we study here. We call square matrix A Z-matrix if Aiy S 0 for all A j. We call a matrix L Laplacian it a symmetric Z-matrix with L1 We call M an invertible M M-matrix if M sl A where > 0. A udxd. and p(A) where p is the spectral radius.

---

work has obtained improved solvers for these systems [MРPО KMPII KOSZI3 LS13 CKM 14 PS14 KLP 16, KST [S2[], which have been used to improve the runtimes for a wide variety of
graph-structured problems, including maximum flow [CKM+1] Mad13 LS14), sampling random
spanning trees M09 MST13 DKP+17
Sch18), graph Clustering [ST04 OV OSV12], and
more [S08 KRSS15 CMSV17 CMTVI7b Additionally, efficient linear system solvers have been
developed for solving systems in other types of structured matrices, e.g., block diagonally dominant
systems KKLP 16), M-matrices [AJSS19], and directed Laplacians [CKP 16 CKPT 17 CKK+18
Perturbations of structured matrices. Despite the importance of these matrices with combinatorial structure. greviously-developee solvers are in some ways quite brittle. For example. there are simple matrix families closely related to Laplacians for which the best-known runtimes for solving linear systems are achieved by ignoring problem structure, and using generic matrix multiplication techniques as a black box. Perhaps the simplest example is solving systems in perturbed I. Laplacians, i.e., matrices which admit constant-factor approximations by Laplacian matrix, but which are not Laplacians themselves. This situation can arise when Laplacian used to approximate a physical phenomenon (BHV08. We show that the framework we develop for (I yields, as consequence, robustificatiios and recovery routines building upon previously-developed solvers for structured linear systems. As first example, we give the following perturbed Laplacian solver.
Theorem 3 (Perturbed Laplacian solver). Let M = Rax= be such that there exists an (unknown) Laplacian L with M I L I x K*M, and that L corresponds to a graph with edge weights between Wmin and Wmax, with Winax I U. For any
(0, 1) and e > there is an algorithm recovering
altenin
a Laplacian L' with M 3 L' 3 (1 + e)n² M with probability 2 1 - 5 in time O(n² (I=) )a
poly( log Dett }). Consequently, there is an algorithm for solving linear systems in M to e-relative accuracy with probability ò, in time O( (x*)2- polylog( P 6,
dc
Theorem 3 can be viewed as solving a preconditioner construction problem, where we know there exists a Laplacian matrix L which spectrally resembles M, and wish to efficiently recover a Laplacian with similar guarantees. Our matrix-dictionary recovery framework (T) captures the setting of Theorem 3 by leveraging an appropriate maarix-dictionas The conceptual message of Theorem 3 is that near-lineal time solvers for Laplacians robustly extend through our preconditioning framework to efficiently solve matrices approximated by Laplacians. Beyond this specific application, our framework could be used to solve perturbed generalizations of future families of structured matrices.
of edge Laplacians, discussed in Section 4
Recovery of structured matrices. In addition directly spectrally approximating and solving in matrices which are well-approximated by preconditioners with diagonal or combinatorial structure, our framework also yields solvers for new families of matrices. We show that our preconditioning techniques can be used in conjunction with properties of graph-structured matrices to provide solvers and spectral approximations for inverse M-matrices and Laplacian pseudoinverses. Recovering Laplacians from their pseudoinverses and solving linear systems in the Laplacian pseudoinverse arise when trying to fit a graph to data or recover a graph from effective resistances, a natural distance measure (see [MMTT8] for motivation and discussion of related problems). More broadly, the problem of solving linear systems in inverse symmetric M-matrices prevalent and corresponds to statistical inference problems involving distributions that are multivariate totally positive of order 2 (MTP,) 2) [R83 [SH44, FLS+ 17]. Our main results are the following.
Theorem 4 (M-matrix recovery and inverse M-matrix solver). Let M be the inverse of an unknown invertible symmetric M-matrix, let i upper bound its condition number, and let U be the multiplicative range of M1
10 For any ā E (0, 1) and e >> 0, there is an algorithm recovering a (1 + <)-spectral
approximation to M in time O(n² poly(" log -))) )) Consequently, there is an algorithm for solving linear systems in M to c-relative accuracy with probability 2 21- 1-55, 5, in time O(n² polylog( (nd)) ))-
Theorem 5 (Laplacian recovery and Laplacian pseudoinverse solver). Let M be the pseudoinverse of unknown Laplacian L, and that L corresponds to a graph with edge weights between Wminn and Wmax- with
Emaz < U. For any 8 E (0, and > O, there is an algorithm recovering Laplacian L' with
Wanin
M < L' 3 (I+ in time O(n² poly( log all )). Consequently there is an algorithm for solving c
linear systems in M to e-relative accuracy with probability 2 1 1-ô, in time O(r²² polylog( (nll)) )).
9 SSe 6 and the following discussion for the definition of solving to relative accuracy.
10 "Mi is entrywise positive, as shown in Appendix B of the supplement.
5

---

Theorems and 5 are perhaps surprising demonstration of the utility of our techniques: just because matrix family well-approximated by structured preconditioners. it is not priori clear that their inverses also are. However, we show that by applying recursive preconditioning tools in conjunction with our recovery methods, we can obtain analogous results for these inverse families. These results add to the extensive list of combinatorially-strucurrs linear algebra primitives. We view our approach as a proof-of-concept of further implications in designing near-linear time system solvers for structured families via algorithms for (
matrix families admitting efficient
Similarly to our results in Section 2 our results on solving natrix-dictionary recovery for graph- structured matrices (Theorems 3 and (5) are the first we are aware of with runtimes improving upon black-box generic algorithms. In particular, for key matrices in each of these cases (e.g.. constant- factor spectral approximations of Laplacians, inverse M-matrices, and Laplacian pseudoinverses)
we obtain (n²) time algorithms for solving linear systems in these matrices to inverse polynomial accuracy. This runtime is near-linear when the input is dense and in each case when the input is dense the state-of the art prior methods were to run general linear system solvers using O(n") time.
4 Matrix-dictionary recovery: a general preconditioning framework
Our general strategy for
recovery, i.e., recovering preconditioners in the sense of (I). is via applications of a new custom approximate solver we develop for family of structured SDPs. SDPs are fundamental optimization problems that have been the source of extensive study for decades [VB96), with numerous applications across operations research and theoretical computer science GW95.. statistical modeling [WSV00, GM12), and machine learning [SSL18] Though there have been recent advances solving general SDPs (e.g., [JKI. HJS and references therein). the current tate-of-thhear solvers have superlinear runtimes, prohibitive in large-scale applications. Consequently, there has been extensive research on designing faster approximate SDP
solvers under different assumptions [KV05 WK06 AK07 BBNI3 GHMI5 ALI7 CDST19].
We now provide context for our solver for structured "matrix-dice dictionary approximation" SDPs, state our algorithm and its guarantees, and summarize how it is used to obtain Theorems !
and
Positive SDPs. One prominent class of structured SDPs are what refer to as positive SDPs, namely SDPs in which the cost and constraint matrices are all positive semidefinite (PSD), a type of structure
present in many important applications [GW95] ARV09 NOWIT LS17 CG18. CDG19 CFB19
CMY20), including those in this paper. Positive SDPs generalize positive linear programming, itself a well-studied problem over the past several decades [LN93] PST95 YouOl MRWZ16, A019] It
was recently shown that a prominent special case of positive SDPs known as packing SDPs can be solved in nearly-linear time (LO16 PTZ16), fact that has had numerous applications in robust learning and estimation [CGIS CDG19 CFB19, CM220 as well as in combinatorial optimization [LS17]. However, extending known packing SDP solvers to broader classes of positive SDPs, e-g. mixed packing-coveringg SDPs has been elusive (Y12) J and is key open problem in the algorithmic theory of structured optimization The mixed backing-covering SDP problem parameterized by "packing" and "covering" matrices [Pi)eem), P. (C.))en C E Sy and asks to find the smallest μ 0 such that there exists 12 with LiE(n] W.P 3 uP (packing into μP)
and Eienn C; 2 C (covering C). Redefining P; - 1. -.------- PP, i, C, - c- for all
i [m). (a slight strengthening of) this problem is equivalent to finding w R2 such that
Σ KE(M)
w. P
Σ C,, xE(m]
or refuting its existence. This was studied by [ 20) and an important open problem in structured convex programming is designing a "width-independent" solver for testing feasibility of (2) up to a 1 + e factor (i.e. testing whether (2) is approximately feasible with an iteration count polynomial in e and polylogarihhii in other parameters). Such solvers have remained clusive beyond pure packing SDPs [ALO16] PTZ16 JLT20), even for basic extensions such as pure covering.
Matrix-dictionar approximation SDPs. In Theorem 6 we develop our main meta-algorithm, an ef- ficient solver for specializations of ( where the packing and covering matrices (Pr)e { (C, )e([))
A faster solver for general positive (mixed -overinno SDPs was claimed in JLL but an error was later discovered in that work, as is recorded in the most recent arXiv version [JL

---

are multiples of each other. As we will see, this family of structured SDPs, which we call matrix- dictionary approximation SDPs, is highly effective for capturing the forms of approximation required by (1) All our aforementioned preconditioning results follow via careful applications of our matrix- dictionary approximation SDP solver Theorem (and generalization of Theorem 7
Specifically, we develop efficient algorithms for the following main meta-problem we study, Given of matrices "matrix-dcttiin (nattix-dictionary")) (Mi]ve[n) - constraint matrix B St a tolerance parameter (0, 1). and x** 2 1 such that there exists w* E R20 with
B
Σ
w M; 3 R
(3)
iE(N]
the goal of matrix dictio-dr approximation is to return weights E R2 such that
B
Σ RE
wy M, = + c)+
(4)
When B I, the problem 3 special case of 2 where each M, C; p*P;; we call
this the isotropic case. We further handle general B, and demonstrate that our formulation captures many interesting applications. We refer to the problem in 3 as matrix-dictionary recovery.
Our results: matrix-dictionary recovery. Our results concerning (3) and 4 assume that the
matrix-dictionary (Mo is "simple" in two respects. First, assume that have explicit
factorizations
M. V.V.. V, E Bdxm
Our applications in Sections 2 and 3 satisfy this assumption with m = 1. Second, denoting approximately solve systems in MMww) + AI for any assume there is linear operator .M which
M(w)= = Eiejn w,M,, IR and X 2 0. Concretely, for any compute and apply in TM log time
12 and that MW.A. ze (M(w) + A in that:
(M(w) AI) ( +
S (MM()))
-1)-11//
w/1 for all v E Rd.
(6)
In this case, say "we solve in M to e-relative accuracy in TMl loog time." M is single matrix M, we say "we can solve in M to e-relative aceuracy in TM log time." Notably, for the deatrx-dicttonaaicn in our applications, e.g., diagonal L-sparse matrices or edge Laplacians, such access Jeje exists we obtain end-to-end efficient algorithms. Ideally (for near-linear time algorithms), TM is roughly the total sparsity of <ee)) which holds all our applications.
Under these assumptions, we give the following novel meta-solvers for matrix- dictionary recovery
Theorem 6 (Matrix dictionary recovery, isotropic case). Given matrices [Meseja with explicit fuctorizations (5), such that 3 is feasible for B = I and some x² 1, can return weights w E RS satisfying 4 with probability 2 8 in time
log mndu." o
A
Tav (IVe(Veeie(n)) (xt)). poly
Here Tmy ((V.) Viemn) denotes the computational complexity of multiplying arbitrary vector by all matrices in ( Vi)e Notably, in the isotropic case B = I. Theorem [ does not require solvers in the sense of (6). We next state our solver which handles the case of general under access (6).
12 We use this notation because, if T is the complexity of solving the system to constant error c < then we can use an iterative refinement procedure to solve the system to accuracy in time 7X log for any >> 0. We did not heavily optimize logarithmic factors and dependences; for many applications (notably Theorems 2). e is constant, so our runtimes are near linear for natural representation the problem under the assumption 5 In several applications (e.g.. [ the most important parameter is the "relative condition number" x in the promise 3 primarily optimized for the dependence k*.
7

---

Theorem 7 (Matrix dictionary recovery, general case). Given matrices (Miriel)) with explicit factorizations (5) such that (3) is feasible for some n²* and we can solve in M to e relative accuracy in TM log time, and B satisfying
B B3 M(1) 3 aB and I B = SI,
we can return weights w E R2 satisfying 4 with probability 2 1 ô in time
o o Two (x=)2 poly
log mndn' aB )) where Tio := Tav ((Vilse(m) U (B)) + +TM-
The first condition in is no more general than assuming we have a "warm start" reweighting Wo E R2 (not necessarily 1) satisfying B =
[[o]]MM 3 aB, by exploiting scale invariance
of the problem and setting M, < M, The second bound in 7 is equivalent to k(B) < 8 up to constant factors, since given a bound 9. we can use the power method to shift the scale of B so it is spectrally larger than I. The operation requires just a logarithmic number of matrix vector multiplications with B, which does not impact the runtime in Theorem 7
Proof sketches of Theorems 6 and 7 We defer full proofs of Theorems 6 and 7 to Section 3 of the supplement, but overview our techniques here. Our main workhorse is the following Algorithm which solves a decision variant of the isotropic matrix-dictionary recovery problem (i.e., B leveraging any subroutine Apack for solving pure packing instances of 22) from the literature
We define our approximation notions (used in Lines 6 and 10 of Algorithm I in Section 2 of the supplement. In Section 3.1 of the supplement, we analyze correctness of Algorithm T usiig regret bounds for the matrix multiplicative weights framework [Z.015, which Lines 4-12 are an instance of, and demonstrate tolerance to the stated approximations. Our proof shows that Algorithm [ meets its output guarantees, which directly implies solver for the matrix-dictional recovery problem (4) in the isotropic case B = I, provided we can efficiently implement the algorithm's 's steps
By carefully combining polynomial approximations to the exponential, Johnson-Lindenstraut sketches, and the power method, we obtain the needed approximations in Lines 6 and 10 of Algo- rithm [ which combined with our correctness proof yields Theorem O Our proof of Theorem 7 in Section 3.2 of the supplement builds upon Theorem 6 and recursive preconditioning, based on the observation that if we could efficiently apply B 1, setting M; < B à reduces to the isotropic case. We show that at a VR* overhead, we can use (6) to efficiently simulate (B + +AII) for À values which are recursively halved, allowing of Theorem 6 each recursive call. This general type of adaptive regularization strategy, which we term a homotopy method, is reminiscent of techniques used by other recent works in the literature numerical linear algebra and structured continuous optimization, such as [MP[3] KLM
BCLL18 AKPS19].
Preconditioning applications. Formal proofs of our applications in Section 2 are given in Section 5 of the supplement. Theorem 2 follows immediately from Theorem 6 with the dictionary M, = a;a, where {a: heejn) are rows of A, which satisfies (5)
with = 1. Specifically, note for w By
M(w)
Σ w sE(n]
Σ w.a,a A TAA xE(m]
result analogous to Theorem but depending quadratically on Ki (K), follows from applying Ni (K), and B _KK (i.e., using the dictionary of 1-sparse diagonal matrices to approximate K, which satisfies (5) with m = and (6) with T = d). Compared to inner scaling, this application exchanges the role of the dictionary and the constraint matrix. Theorem I
Theorem 7 with n d, M, E,e;
goes beyond this black-box use via a homotopy method for simulating access to matrix square roots (to reduce to the isotropic case), yielding an improved (R. (k)) dependence.
"For simplicity, we assume each matrix dictionary element's top eigenvalue is in a bounded range. We explicitly bound the cost of achieving this in applications (via rescaling by a constant- factor approximation to the top eigenvalue of each matrix using the power method, see Fact 3 of the supplement), and this does not dominate the runtime. The runtime bottleneck in all our applications is the cost approximate packing SDP oracles in Line 7 this is an active research area and improvements therein would also reflect in our algorithm's 's runtime. We show how to search for x² in using an incremental search over small number of calls to Algorithm
8

---

Algorithm 1: DecideStucturraMMP(([1] (in[n), Apack Apack.. 8,c)
Input:
(Maliejo) E % with Amax (M,) [1, for all i [n], 1, ò (0, , c (0,
Apeck which on input E I2 returns or E 20 with M(w) 3 I that to --uuliplliaaiielly 27' Output: With probability 2 o: "yes"" or "no" is returned. If there exists E R
approximates M(e) =I with probability 1 -
6 T O logd
20 with
max
Σ W,M, S c))dddmiin
Σ w,M, iE(m)
(8)
VEin]
the algorithm must return "yes." If "yes" is returned, vector is given with
Amax
Σ w,M,
S (1 Ee)cdmin
Σ
w.MM
(9)
iE|m]
iE(m)
17
10x
c T
10
Me
Yo 11 So
for 0 S 1 do
Y, f exp(Sr)
Tr.)
Dt - entrywise (0 10kn aaprroximmaiinn to {M, Y.) Himm)) with probability 2 1 Tt f- Apack (KUr)
47
R (Ze, U1) <
then return "no"
Se41 f S; (xx))
log d additive approximation to Amia (-ia()))41)))) with probability 2
if 12 log then return ("yes", 7) for T = T+I Eocost
11
12
end
13 return ("yes", 2) I == Eoseet
Our applications in Section are deferred to Section of the supplement. Robust linear system solvers for perturbed variants of structured matrix families follow directly from Theorem 7 taking the matrix dictionary to be suitable basis for the relevant non-perturbed structured family, which naturally satisfy (6). As an example, to prove Theorem 3 we use Theorem with the dictionary of all b. for edges of complete graph, where be is the associated incidence vector; the access (6) is then afforded by known Laplacian solvers. Finally, Theorems 4 and follow by combining 3
Theorems 6 7 with homotopy techniques, alongside structural facts about M --mtricess and Laplacians.
Further work. A natural open question is if, e.g., for outer scaling, the x (K) dependence in Theorem can be reduced further, ideally to //t(()), This would match the most efficient solvers in K under diagonal rescaling, if the best known outer scaling goal, we prove in Appendix D of the supplement that if width-independent variant Theorem 6 is developed. it achieve such improved runtimes for Theorem [ (with analogous improvement for Theorem 2). We also give generalizations of this improvement to finding rescalings which minimize natural average notions of conditioning, under existence of such conjectured solver.
known in advance. Towards this
5 Additional related work
Matrix-dictionary recovery. Our algorithm for Theorem i based on matrix multiplicative weights [WK06] AK07 AHK12), a popular meta-algorithm for approximately solving SDPs, with carefully chosen gain matrices formed by using packing SDP solvers
black box. In this sense, it is efficient reduction from structured SDP instances of the form 3 to pure packing instances.
Similar ideas were previously used in [LS17 (repurposed in (CG18) for solving graph-structured -ictix-dictionary recovery problems. Our Theorems 6 and improve upon these results both in generality (prior works only handled B I, and x* I + for sufficiently small e) and efficiency (our reduction calls packing solver log d times for constant K*, while [LS17] used as log" d

---

calls). Perhaps the most direct analog of Theorem Theorem 3.1 of [CGI8), which builds upon the proof of Lemma 3.5 of [LS17] (but lifts the sparsity constraint). The primary qualitative difference with Theorem is that Theorem 3.1 of [CG]8] only handles the case where the optimal rescaling s* in 1. whereas we handle general K=*. This restriction important in the proof technique of (CGT8), as their approach relies on bounding the change in potential functions based on the matrix exponential of dictionary linear combinations (c.g., the Taylor expansions in their Lemma B. which scales poorly with large k", Moreover, our method is a natural application of the MMW framework, and is arguably simpler. This simplicity is useful diagonal scaling applications, as it allows us to obtain tighter characterization of our Λ² dependence, the primary quantity of interest. Finally, to our knowledge Theorem 7 (which handles general constraint matrices B, crucial for our applications in Theorems and has analog in prior work, which focused on the isotropic case.
Semi-random models. The semi-random noise model we introduce Section 2 for linear system solving, presented in more detail and formality in Section 6 of the supplement, follows a line of noise models originating (BS95). semi-random model consists of an (unknown) planted instance which a classical algorithm performs well against, augmented by additional information given by "monotone" " or "helpful" adversary masking the planted instance. Conceptually, when an algorithm fails given this "helpful" information, it may have overfit to its generative assumptions. This model has been studied in various statistical settings [Jer92 FK00 FKO1 MPW 16 MMV12). Of particular relevance to work, which studies robustness to semi-rase random noise in the context of fast algorithms (as opposed to the distinction between polynomial time algorithms and computational intractability) is (CGI8), which developed an algorithm for semi-randon matrix completion.
Acknowledgments
AS was supported in part by a Microsoft Research Faculty Fellowship. NSF CAREER Award CCF- 1844855, NSF Grant was supported by a Stanford Data Science Scholarship and Dantzig-Liebermaan Operations Research Fellowship. KT supported by Google Ph.D. Fellowship, Simons-Berkele VMware Research Fellowship, a Microsoft Research Faculty Fellowship, NSF CAREER Award CCF-1844855, NSF and PayPal research award.
PayPal research award, and Sloan Research Fellowship. KS
Grant
We would like to thank Huishuai Zhang for his contributions to an earlier version of this project, Moses Charikar and Yin Tat Lee for helpful conversations, and anonymous reviewers for feedback on carlier variations of this paper.
10

---

References
[AHKI2]
Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta-algorithm and applications. Theory Comput., 8(1):121-164, 2012.
[AISS19] AmirMahdi Ahmadinejad, Arun Jambulapati, Amin Saberi, and Aaron Sidford. Perron- frobenius theory in nearly linear time: Positive eigenvectors, m-matrices, graph kernels, and other applications. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1387-1404, 2019.
[AK07] Sanjeev Arora and Satyen Kale. A combinatorial, primal-dual approach to semidefinite programs. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing. San Diego, California, USA, June 1 11-13, 2007, pages 227-236, 2007.
[AKPS19] Deeksha Adil, Rasmus Kyng, Richard Peng, and Sushant Sachdeva. Iterative re- finement for p-norm regression. In Proceedings of the Thirtieth Annual (CM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California. USA, January 6-9, 2019, pages 1405-1424, 2019.
[AL17] Zeyuan Allen-Zhu and Yuanzhi Li. Follow the compressed leader: Faster online learning of eigenvectors and faster MMWU. In Proceedings of the 34th International Conference on Machine Learning. ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, pages 116-125, 2017.
[ALO16] Zeyuan Allen Zhu, Yin Tat Lee, and Lorenzo Orecchia. Using optimization to obtain width-independdet, parallel, simpler, and faster positive SDP solver. In Proceedings of the Twenty-Sevente Annual ACM-SIAM Symposium Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1824-1831, 2016.
[A019] Zeyuan Allen-Zhu and Lorenzo Orecchia. Nearly linear-tims time packing and covering LP solvers achieving width-independence and -convergence. Math. Program., 175(1- 2):307-353, 2019.
[ARV09] Sanjeev Arora, Satish Rao, and Umesh V. Vazirani. Expander flows, geometric embeddings and graph partitioning. J. ACM, 56(2):5:1-5:37) 2009.
[AW21] Josh Alman and Virginia Vassilevska Williams. A refined laser method and faster matrix multiplication. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 13, 2021, pages 522-539. SIAM, 2021.
(AZLOW11) Zeyuan Allen-Zhu, Yuanzhi Li, Rafael Oliveira, and Avi Wigderson. Much faster algorithms for matrix scaling. In Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 890-901, 2017.
[BBN13] Michel Baes, Michael Bürgisser, and Arkadi Nemirovski. A randomized mirror-prox method for solving structured large-scale matrix saddle-point problems. SIAM J. Optimization, 23(2):934-96 2013.
[BCLL18] Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee, and Yuanzhi Li. An homotopy method for Ip regression provably beyond eeffcconcordance and in input-sparsity time. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 1130-1137, 2018
[BHV08] Erik G. Boman, Bruce Hendrickson, and Stephen A. Vavasis. Solving elliptic finite element systems in near-lineal time with support preconditioners. SIAM J. Numerical Analysis, 46(6)):264-3284. 2008.
[BS95] Avrim Blum and Joel Spencer. Coloring random and semi-random k-colorable graphs. J. Algorithms, 19(2):204-234 1995.

---

[CDG19] Yu Cheng, llias Diakonikolas, and Rong Ge. High-dimensiona, robust mean estimation in nearly-lineal time. In Proceedings of the Thirtieth Anmual ACM-SIAM Symposium Discrete Algorithms, SODA 2019, San Diego California, USA, January 6-9, 2019, pages 2755-2771, 2019.
[CDST19] Yair Carmon, John C. Duchi, Aaron Sidford, and Kevin Tian. A rank-1 sketch for matrix multiplicative weights. In Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, pages 589-623, 2019.
[CFB19] Yeshwanth Cherapanamjeri, Nicolas Flammarion, and Peter L. Bartlett. Fast mean estimation with sub-gaussian rates. In Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, pages 786-806, 2019.
[CG18] Yu Cheng and Rong Ge. Non-convex matrix completion against a semi-random adversary. In Conference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018, pages 1362-1394, 2018.
[CKK+18] Michael B. Cohen, Jonathan A. 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. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 898 11989999,220000 2018
[CKM+1I] 11] Paul F. Christiano, Jonathan A. Kelner, Aleksander Madry, Daniel A. Spielman, and Shang-Huz Teng. Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs. In Proceedings of the 43rd ACM Symposium on Theory of Computing. STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages 273-282, 2011.
[CKM+14) 14] Michael B. Cohen, Rasmus Kyng, Gary L. Miller, Jakub W. Pachocki, Richard Peng, Anup B. Rao, and Shen Chen Xu. Solving SDD linear systems in nearly mlog 1/2,, time. In Symposium Theory of Computing, STOC 2014, New York, NY, USA, May 31- June 03, 2014, pages 332-552,000 2014.
[CKP+16] 16] Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Aaron Sidford, and Adrian Vladu. Faster algorithms for computing the stationary distribution, simu- lating random walks, and more. In IEEE 57th Anmual Symposium Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 583-592, 2016.
[CKP+17) 17] Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford, and Adrian Vladu. Almost-linear-te linear- time algorithms for markov chains and new spectral primitives for directed graphs. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017 pages 410-419, 2017.
[CMSV17] Michael B. Cohen, Aleksander Madry, Piotr Sankowski, and Adrian Vladu. Negative- weight shortest paths and unit capacity minimum cost flow in 6 (m 10/7 log W) time (extended abstract). In Proceedings of the Twenty-Eighth Annual ACM-SIAM Sympo- sium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 752-771, 2017.
[CMTV17a] Michael B. Cohen, Aleksander Madry, Dimitris Tsipras, and Adrian Vladu. Matrix scaling and balancing via box constrained newton's 's method and interior point methods. In Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 902-913, 2017.
[CMTV17b] Michael B. Cohen, Aleksander Madry, Dimitris Tsipras, and Adrian Vladu. Matrix scaling and balancing via box constrained newton's 's method and interior point methods. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA. USA October 15-17, 2017, pages 902-913, 2017.
12

---

[CMY20] Yeshwanth Cherapanamjeri, Sidhanth Mohanty, and Morris Yau. List decodable mean estimation nearly linear time. In 61st IEEE Anmual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 141-148, 2020.
[DHS1I] John C. Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12:2121-21521 2011.
[DKP+ 17) David Durfee, Rasmus Kyng, John Peebles, Anup B. Rao, and Sushant Sachdeva. Sampling random spanning trees faster than matrix multiplication. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 730-742, 2017.
[DS08] Samuel I. Daitch and Daniel A. Spielman. Faster approximate lossy generalized flow via interior point algorithms. In Proceedings of the 40th Annual ACM Symposium Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pages 451 160, 2008
[DW723] Ran Duan, Hongxun Wu, and Renfei Zhou. Faster matrix multiplication via asymmetric hashing. In 64th IEFE Annual Symposium on Foundations of Computer Science, FOCS 2023. IEEE, 2023.
[FK00] Uriel Feige and Robert Krauthgamer. Finding and certifying a large hidden clique in semirandom graph. Random Struct. Algorithms, 16(2):195-208, 2000.
[FK01] Uriel Feige and Joe Kilian. Heuristics for semirandom graph problems. J. Comput. Syst. Sci., 63(4):639-671, 2001.
[FLS+17] Shaun Fallat, Steffen Lauritzen, Kayvan Sadeghi, Caroline Uhler, Nanny Wermuth, and Piotr Zwiernik. Total positivity in markov structures. Ann. Statist., 45(3):1152-1184, 06 2017.
[FS55] G. E. Forsythe and E. G. Straus. On best conditioned matrices. Proceedings of the American Mathematical Society, 6(3):340-345, 1955.
[Gal14] François Le Gall. Powers of tensors and fast matrix multiplication. In International Symposium on Symbolic and Algebraic Computation, ISSAC '14, Kobe, Japan, July 23-25, 2014, pages 296-303. ACM, 2014.
[GHM15] Dan Garber, Elad Hazan, and Tengyu Ma. Online learning of eigenvectors. In Proceedings of the 32nd International Conference Machine Learning, ICMI. 2015, Lille, France, 6-11 July 2015, pages 560-568, 2015.
[GM12] Bernd Gartner and Jiri Matousek. Approximation Algorithms and Semidefinite Pro- gramming. Springer, 2012.
[GO18] Ankit Garg and Rafael Oliveira. Recent progress on scaling algorithms and applications. Bulletin of EATCS, 2(125), 2018
[GR89] A. Greenbaum and G. H. Rodrigue. Optimal preconditioners of a given sparsity pattern. BIT Numerical Mathematics. 29(4):610 0-34,, 1989.
[GW95] Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM, 155-111 1995.
H2S+22 Baihe Huang, Shunhua Jiang, Zhao Song. Runzhou Tao, and Ruizhe Zhang. Solving SDP faster: A robust IPM framework and efficient implementation. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31- November 3, 2022, pages 233 23-224..122 IEEE, 2022.
[HMMT18] Jeremy G. Hoskins, Cameron Musco, Christopher Musco, and Charalampos E. Tsourakakis. Learning networks from random walk-based node similarities. CoRR, 2018.
13

---

[Jer92] Mark Jerrum. Large cliques elude the metropolis process. Random Struct. Algorithms, 3(4):347-360, 1992.
[JJUWIL] Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, and John Watrous. QIP PSPACE. J. ACM, 5866):30:1130:27, 2011.
[J] Haotian Jiang, Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan, and Zhao Song. A faster interior point method for semidefinite programming, In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 910-918, 2020.
[JL Arun Jambulapati, Yin Tat Lee, Jerry Li, Swati Padmanabhan, and Kevin Tian. Positive semidefinite programming: Mixed, parallel, and width-independent. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. STOC 2020,
2020.
[JLI+21]] Arun Jambulapati, Yin Tat Lee, Jerry Li, Swati Padmanabhan, and Kevin Tian. Pos- itive semidefinite programming: Mixed, parallel, and bidth-independent. CoRR, abs/2002.04830v3, 2021.
[JLT20] Arun Jambulapati, Jerry Li, and Kevin Tian. Robust sub gaussian principal component analysis and iidth-independent schatten packing. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
[JS21] Arun Jambulapati and Aaron Sidford. Ultrasparse ultrasparsifiers and faster laplacian system solvers. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 1021, Virtual Conference, January 10 13, 2021, pages 540-559, 2021.
[JY12] Rahul Jain and Penghui Yao. A parallel approximation algorithm for mixed packing and covering semidefinite programs. CoRR, abs/1201.6000 2012.
[B15] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. Proceedings of the 3rd International Conference on Learning Representations (ICLR), 2015.
KKL 14] Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, and Aaron Sidford. Single pass spectral sparsification in dynamic streams. In 55th IEEE Annual Symposium Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 561-570, 2014.
[KLP+16 16] Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdeva, and Daniel A. Spielman. Sparsified cholesky and multigrid solvers for connection laplacians. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing. STOC 2016, Cambridge, MA. USA, June 18-21, 2016, pages 842- 250. 2016.
[KM09] Jonathan A. Kelner and Aleksander Madry. Faster generation of random spanning trees. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA, pages 13-21, 2009.
[KMP10] Ioannis Koutis, Gary L. Miller, and Richard Peng. Approaching optimality for solving SDD linear systems. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 235-244, 2010.
[KMP11] Joannis Koutis, Gary L. Miller, and Richard Peng. A nearly-m log time solver for SDD linear systems. In IEEE 52nd Annual Symposium Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 201 I, pages 590-598. 2011.
14

---

[KOSZI3] Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford, and Zeyuan Allen Zhu. A simple, combinatorial algorithm for solving SDD systems nearly-lines -iinear time. In Symposium on Theory of Computing Conference, STOC"13, Palo Alto, CA, USA, June 1-4, 2013, pages 91 12000, 2013.
[KR83] Samuel Karlin and Yosef Rinott. M-matrices as covariance matrices of multinormal distributions. Linear Algebra and its Applications, 52-53:419 438, 1983.
[KRSS15] Rasmus Kyng, Anup Rao, Sushant Sachdeva, and Daniel A. Spielman. Algorithms for lipschitz learning on graphs. In Proceedings of The 28th Conference on Learning Theory, COLT 2015, Paris, France, July 3-6, 2015, pages 1190-1223, 2015.
[KRU14] Philip A. Knight, Daniel Ruiz, and Bora Uçar. A symmetry preserving algorithm for matrix scaling. SIAM Journal Matrix Analysis and Applications, 35(3):931-955, 2014.
[KS16] Rasmus Kyng and Sushant Sachdeva. Approximate gaussian elimination for laplacians fast, sparse, and simple. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 573-582, 2016.
[KV05] Adam Tauman Kalai and Santosh S. Vempala. Efficient algorithms for online decision problems. J. Comput. Syst. Sci., 71(3):291-307, 2005.
[LMP13] Mu Li, Gary L.. Miller, and Richard Peng. Iterative sampling. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 127-136, 2013.
[LN93] Michael Luby and Noam Nisan. A parallel approximation algorithm for positive linear programming. In Proceedings of the Twenty-Fifi Annual ACM Symposium on Theory of Computing, May 16-18, 1993, San Diego, CA, USA, pages 448 457, 1993.
[LS13] Yin Tat Lee and Aaron Sidford. Efficient accelerated coordinate descent methods and faster algorithms for solving linear systems. In 54th Annual IEEE Symposium Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 147-156, 2013.
[LS14] Yin Tat Lee and Aaron Sidford. Path finding methods for linear programming: Solving linear programs in ō(vrank) iterations and faster algorithms for maximum flow. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 424 433, 2014.
[LS17] Yin Tat Lee and He Sun. An sdp-based algorithm for linear-sized spectral sparsification. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 678-687, 2017.
[LST720) Jerry Li, Aaron Sidford, Kevin Tian, and Huishuai Zhang. Well-conditioned meth- ods for ill-conditioned systems: Linear regression with semi-random noise. CoRR, abs/2008.01 017.22 2020.
[Mad13] Aleksander Madry. Navigating central path with electrical flows: From flows to matchings, and back. In 54th Annual IEFE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA. USA, pages 253-262, 2013.
[MVV12] Konstantin Makarychev, Yury Makarychev, and Aravindan Vijayaraghavan. Approxi- mation algorithms for semi-random partitioning problems. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19- 22, 2012, pages 367-384. 2012.
[MPW16] Ankur Moitra, William Perry, and Alexander S. Wein. How robust are reconstruction thresholds for community detection? In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 228-841,2 2016.
15

---

[MRWZ16] Michael W. Mahoney, Satish Rao, Di Wang, and Peng Zhang. Approximating the solu- tion to mixed packing and covering Ips in parallel ( time. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, pages 12:14-5:
[MST15] Aleksander Madry, Damian Straszak, and Jakub Tarnawski. Fast generation of random spanning trees and the effective resistance metric. In Proceedings of the Twenty-Sinn Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA. USA, Jamuary 4-6, 2015, pages 2019-2036, 2015.
[OSV12] Lorenzo Orecchia, Sushant Sachdeva, and Nisheeth K. Vishnoi. Approximating the exponential, the lanczos method and an 6(m)-time spectral algorithm for balanced separator. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 22, 2012, pages 1141-1160, 2012.
[OV11] Lorenzo Orecchia and Nisheeth K. Vishnoi. Towards an sdp-based approach spectral methods: A hearly-linear-ting algorithm for graph partitioning and decomposition. In Proceedings of the Teenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1011, San Francisco, Califorria,, USA, January 23-25, 201 I, pages 332-545,20 2011.
[PG90] Giorgio Pini and Giuseppe Gambolati. Is a simple diagonal scaling the best precon- ditioner for conjugate gradients supercomputers? Advances in Water Resources, 13(3):147-153, 1990.
[PS14] Richard Peng and Daniel A. Spielman. An efficient parallel solver for SDD linear systems. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31- June 03, 2014, pages 333-342, 2014.
[PST95] Serge A. Plotkin, David B. Shmoys, and Eva Tardos. Fast approximation algorithms for fractional packing and covering problems. Math. Oper. Res., 20(2):257-301, 1995.
[PTZ16] Richard Peng, Kanat Tangwongsan, and Peng Zhang. Faster and simpler width- independent parallel algorithms for positive semidefinite programming. CORR, abs/1201.51333 2016.
[QGH+22] Zhaonan Qu, Wenzhi Gao, Oliver Hinder, Yinyu Ye, and Zhengyuan Zhou. Optimal diagonal preconditioning: Theory and practice. CoRR, abs/2209.00809, 2022.
[QYZ20] Zhaonan Qu, Yinyu Ye, and Zhengyuan Zhou. Diagonal preconditioning: Theory and algorithms. (arXin:0003.07545) 2020.
[RSL18] Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Semidefinite relaxations for certifying robustness to adversarial examples. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pages 10900-10910, 2018.
[Sch18] Aaron Schild. An almost-linear time algorithm for uniform random spanning tree generation. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 214-227, 2018.
[SH14] Martin Slawski and Matthias Hein. Estimation of positive definite m-matrices and structure learning for attractive gaussian markov random fields. 473, 04 2014.
[ST04] Daniel A. Spielman and Shang-Huz Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16. 2004, pages 81 81-90, 2004.
[VB96] Lieven Vandenberghe and Stephen Boyd. Semidefinite programming. SIAM Review, 38(1):49-95 1996.
16

---

[vdS69] A. van der Sluis. Condition numbers and equilibration of matrices. Numerische Mathematik, 14(1):14 23, 1969.
[Wil12] Virginia Vassilevska Williams. Multiplying matrices faster than coppersmitt-winognad In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 22, 2012. pages 887-898. ACM, 2012.
[WK06] Manfred K. Warmuth and Dima Kuzmin. Randomized PCA algorithms with regret bounds that logarithmic in the dimension. In Advances in Neural Information Processing Systems 19, Proceedings of the Twentieth Annual Conference on Neural Information Processing Systems, Vancouver, British Columbia, Canada, December 4-7, 2006, pages 1481-1488, 2006.
[WSV00] Henry Wolkowicz, Romesh Saigal, and Lieven Vandenberghe. Handbook of Semidefi- nite Programming: Theory, Algorithms, and Applications. Springer Nature, 2000.
[WXXZ23] Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. New bounds for matrix multiplication: from alpha to omega. CoRR, abs/2307.07970 2023.
[YouO1] Neal E. Young. Sequential and parallel algorithms for mixed packing and covering. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA, pages 538-546, 2001.
[ZLO15] Zeyuan Allen Zhu, Zhenyu Liao, and Lorenzo Orecchia. Spectral sparsification and regret minimization beyond matrix multiplicative updates. In Proceedings of the Forty- Seventh Annual ACM on Symposium Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 17, 2015, pages 237-245, 2015.
17


Reviews:
[{"review_id": "j4NNgDDaLy", "reviewer": "Reviewer_HjkM", "summary": "This is a theoretical paper that studies the problem of diagonal matrix preconditioning, where given a PSD matrix $A$, the goal is to find a (positive) diagonal scaling $W$, such that $WAW$ has a small condition number, given the promise that such scaling exists. This problem can be solved using SDP, but that is too expensive. Following previous work that uses spectral sparsification techniques, the authors give improved guarantees for this problem. In particular, previously it was only known how to compute an approximately optimal scaling when the resulting condition number is $\\leq 1.1$, while the authors' result works for any condition number (and has a polynomial condition number dependency in the runtime). The authors use the matrix multiplicative weights algorithm, together with sketching techniques to efficiently implement its iterations, leading to a near-linear time algorithm for bounded condition number. The results can be generalized to other problem classes like graph-structured preconditioning.", "questions": "- Do the results extend to the case when we have both outer and inner preconditioning?\n- Since the algorithm is based on multiplicative weights, it seems natural to try and generalize this to the online setting. Are there any significant difficulties there?\n- Are there potential implications for preconditioned optimizers such as Adagrad, Shampoo, etc?", "limitations": "No", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- Preconditioning is a fundamental problem and this is a significant and original contribution to it. It is significantly stronger than previously known results.\n- The analysis looks correct and technically strong.\n- The presentation is thorough and the intro is well written.", "weaknesses": "- There is no empirical evaluation of the proposed algorithm, e.g. compared to Jacobi iteration, and so the practical impact of this approach is not clear.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your kind review of our paper and your insightful questions. \n\nWe are currently not aware of a variant of our algorithm (and matrix dictionary recovery framework) which extends to simultaneous inner and outer scaling, though it is worth noting that prior work [QGH+22] does obtain such a result via semidefinite programming. Obtaining such a variant is indeed an interesting open problem for future work. In practice, one could potentially alternate inner and outer scaling algorithms until they cease to make progress (as the algorithm gives a constant-factor approximation to $\\kappa^\\star$ as a certificate), but it is unclear to us how to prove the convergence rate of such a procedure.\n\nRegarding online variants, this is another intriguing extension of our algorithm (we assume the reviewer means that e.g., the matrix dictionary arrives online and we maintain a set of weights). This extension does not appear compatible with the way multiplicative weights is currently used in our algorithm, where it is called as a regret minimization procedure to reweight an estimate in response to “gain matrices” produced through a packing oracle, roughly measuring currently violated constraints. Our reduction requires knowledge of the set of matrices used in the dictionary in advance. Nevertheless, finding some type of online variant of our results is indeed an interesting open problem.\n\nRegarding Adagrad, etc. diagonal approximations to the full gradient second moment matrix are discussed in the original Adagrad paper as a method to improve runtimes at a hopefully-low overhead on the regret guarantees. The quality of the regret bound for the diagonal variant of Adagrad degrades from that obtained for the full matrix variant. However, the degradation factor (a ratio between traces of matrix square roots) is not directly comparable to our notion of approximation (a relative condition number), so our method does not have immediate implications for Adagrad (or related preconditioning techniques, e.g., Shampoo). We find the questions of 1) obtaining a diagonal preconditioning algorithm directly targeting the degradation notion in Adagrad, and 2) whether our optimal diagonal preconditioners obtain improvements in practice for adaptive gradient methods, to be interesting directions for future exploration.\n\nThank you again for raising these multiple interesting directions for future work. We may add some discussion of these directions in the final version. We hope that the appeal of these questions highlights the utility of this submission in facilitating future research."}, {"review_id": "ZlyqwtrIVk", "reviewer": "Reviewer_1BXc", "summary": "In this paper, a framework is presented to compute approximately-optimal preconditioners in order to solve linear systems. \n\nIn the case of diagonal preconditioning, an algorithm is provided whose runtime is (up to log factors) polynomial in the desired accuracy, optimal condition number of the re-scaled matrix (thus in the output conditioning) and the number of nonzero entries of the input matrix. This is explicitly stated in Theorem 1 and Theorem 2 for outer and inner scaling, respectively.\n\nIn the case of structured linear systems, an algorithm is provided whose runtime is (up to log factors) quadratic in the size of the input matrix.\n\nThe underlying algorithms are based on the so-called \"matrix-dictionary\" approximation semidefinite programs. They rely on these algorithms to solve a related problem called \"matrix-dictionary recovery\".\n", "questions": "l43: What is an M-matrix? The definition should be recalled.", "limitations": "There is no limitation section provided by the authors in the main submission.", "rating": 3, "confidence": 1, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "If they would be correct, the resulting algorithms improve current runtime of the best solvers given by SDP (by a factor of d sqrt(d)). \n\nThe comparison with existing literature seems well-explained.", "weaknesses": "Not being an expert in this field and with a very limited amount of time (too short to read the 63 pages of supplementary material), it is completely impossible to judge whether the framework is correct or not. The authors just state the theorems and do not provide neither proof sketches nor hints that could possibly convince the reader. I believe that this work, possibly sound and surely interesting, is not a good fit at all, considering the currently requested NeurIPS format.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are glad you found our comparison to the literature well-explained, and that our results were interesting. We agree with your comment on M-matrices, which will be addressed in a revision.\n\nLike many theoretical papers that appear at NeurIPS, due to space constraints, the technical details of our proofs were moved to the supplemental material. We provided proof sketches for Theorems 6 and 7, the workhorse results for all of our preconditioning applications, on Page 7 (a full analysis of Algorithm 1 is in Pages 11-14 in the supplement). The remaining components of our framework (approximate matrix-vector access and recursive preconditioning), though technically tedious, are fairly routine in the literature. We believe our overall framework provides value to the community and should be verifiable to experts, and hence NeurIPS is an appropriate venue for publication. We hope our discussion elevates your view of our paper."}, {"review_id": "tdltDOnZHb", "reviewer": "Reviewer_pK6D", "summary": "This paper studies preconditioning, which is one of the most important techniques in numerical linear algebra with numerous applications in optimization and machine learning. It proposes a general framework based on the matrix-dictionary recovery problem, where are given a matrix $M$ and $M_1,\\dots, M_n$, and the goal is to find $w$ such that $\\sum_{i\\in [n]}w_i M_i$ approximates the optimal preconditioner for $M$. This paper develops a general-purpose solver for this problem. Then, they apply this framework to propose nearly linear-time algorithms for diagonal preconditioning (including outer scaling and inner scaling), semi-random regression, and structured liner systems (including dense matrix approximated by graph Laplacians, dense inverse Laplacians, and dense inverse M-matrices). Technically, their meta-solver for the matrix-dictionary recovery problem is based on the matrix multiplicative weights update method and employs packing SDP solvers to form the gain matrices. They also use other techniques, such as JL sketching, the homotopy method, etc., to implement their solvers.", "questions": "In Algorithm 1, it is required that $\\lambda_{\\max}(M_i)\\in [1,2]$. Is it just for convenience? \n\nWhat is the runtime bottleneck of Algorithm 1?", "limitations": "The limitations are addressed.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "This research question considered in this paper is crucial for many applications in both theory and practice. Their results show that a bunch of numerical linear algebra problems can be solved in nearly linear time, which was not known before. More specifically, for the diagonal preconditioning problem, prior to this work, we did not know how to $O(1)$-approximate the optimal condition number of the rescaled matrix without using a generic SDP solver, which takes $\\Omega(d^{3.5})$-time. They improve it to a linear dependence on the number of non-zero entries of the matrix ($\\leq d^2$). In addition, they also provide a tighter analysis of the Jacobi preconditioning method. For numerically solving linear systems, when the matrix is a perturbed Laplacians, prior to this work, the only approach is to apply generic matrix multiplication, which runs in $d^{\\omega}$-time. Their new algorithm runs in about $d^2$-time when the matrix is well-approximated by some unknown Laplacian. Moreover, their algorithm also generalizes to larger families of dense matrices, which are very useful in many different applications. The framework of matrix dictionary recovery is also very interesting and useful. There are some previous results concerning the isotropic case with some restrictions on the condition number. In this paper, their solver works not only for the non-isotropic case but also for general condition numbers. This framework and the general-purpose solver will be very helpful in future studies of numerical linear algebra algorithms.", "weaknesses": "The running times of their preconditioning algorithms depend on $\\kappa^{1.5}$, which may not be optimal. Moreover, the accuracy dependence is $poly(1/\\epsilon)$. Also, the paper does not discuss the practical implications of their algorithms, e.g., is it possible to implement them in practice?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your encouraging review; we are similarly optimistic of the utility of the tools we provide for future numerical linear algebra problems. Regarding Algorithm 1, indeed the eigenvalue assumption was just for simplicity in stating our error bounds. Each $\\mathbf{M}_i$ can always be rescaled to have maximum eigenvalue in $[1, 2]$. This can be accomplished via the power method (see Fact 3 in the supplement), whose runtime cost is dominated by other components of the algorithm. In particular, as you asked, the runtime bottleneck of Algorithm 1 (in terms of polylogarithmic factors and factors of $\\epsilon^{-1}$) is the cost of calling approximate packing SDP oracles from prior work on Line 7, though this is an active area of research and any improvements therein would also reflect in our algorithm’s runtime. We also wanted to mention that while we do not achieve the optimal dependence on $\\kappa^\\star$, we do outline an approach to improve our dependence to $\\sqrt{\\kappa^\\star}$ in Appendix D of the supplement."}, {"review_id": "J1QRzFqduk", "reviewer": "Reviewer_2VGS", "summary": "This paper develops a general preconditioning framework called matrix-dictionary recovery. This framework follows the matrix multiplicative weights update method and is applied to solve two classes of problems:  \n(1) Two diagonal preconditioning problems: outer scaling and inner scaling  \nThis paper gives the first nontrivial approximation algorithms in nearly linear time, which is beyond the generic SDP solvers.  \n(2) Graph-structured matrix families  \nThis paper proposes algorithms for perturbed Laplacian solver and the recovery of two structured matrices: M-matrix and Laplacian matrix. \n", "questions": "The proposed method for graph-structured matrices has running time $\\widetilde{O}(n^2)$ which is nearly linear when the input is dense.  \n(1) Can it be further improved when the input is sparse?  \n(2) The existing work has complexity $O(n^\\omega)$. Is it still $O(n^\\omega)$ when the input is sparse? ", "limitations": "See Weaknesses. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(1) The proposed algorithm for computing diagonal preconditioners (Theorem 1 and Theorem 2) improves the method using general SDP solvers by $\\text{poly}(d)$ factors when $\\kappa_o^\\star (\\mathbf{K})$ and $\\kappa_i^\\star (\\mathbf{A})$ are small.  \n(2) The proposed framework for solving graph-structured matrices (Theorem 3, 4, and 5) obtains $\\widetilde{O}(n^2)$ running time and improves the state-of-the-art methods which have running time $O(n^\\omega)$ by virtue of general linear systems solvers.  \n(2) This paper is well-written and easy to understand. \n ", "weaknesses": "(1) The algorithms for diagonal preconditioning improve the existing method by a factor of $\\text{poly}(d)$ at the cost of $(\\kappa^\\star)^{1.5}$. The applicable scenario is when $\\kappa^\\star$ is small but $\\kappa$ is large.  \n(2) The algorithms for solving graph-structured matrices have time complexity $\\widetilde{O}(n^2)$ that improves $O(n^\\omega)$. They work for the case when the input is dense but in practice, the input is often sparse.  \n(3) Section 5 is placed at the end of the manuscript. It would be better to show the comparison with existing work in the Introduction part so that we can clearly know your contributions and advantages. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your reviewing efforts. We are glad that you found the paper easy to understand. \n\nRegarding weakness (1), we note that our method computes a (constant-factor) optimal diagonal preconditioner, and typically algorithmic or statistical applications of diagonal preconditioning are interesting when the rescaled condition number $\\kappa^\\star$ is small (and hence the $\\kappa^\\star$ overhead of our runtime is also small). While we do not achieve the optimal dependence on $\\kappa^\\star$, we do outline an approach to improve our dependence to $\\sqrt{\\kappa^\\star}$ in Appendix D of the supplement. \n\nRegarding weakness (3), we agree with your suggestion and will move various portions of Section 5 to appear shortly after the relevant results (i.e., Theorems 1-7) for improved readability.\n\nRegarding your questions concerning sparsity, the $n^2$ dependence in our algorithm is due to the inclusion of all $n^2$ single-edge Laplacians in our matrix dictionary, due to the possibility of there being any of the edges present. If the graph to be recovered has a known sparsity structure (i.e. it is known that all edges belong to a set $S$ with $|S| \\ll n^2$), then we can restrict our matrix dictionary and obtain a runtime near-linear in $|S|$, but it is an interesting open direction to obtain a near-linear runtime on sparse graphs without this assumption. We note that in general, the inverse of the Laplacian of a sparse graph is not necessarily sparse. Further, in the case of M-matrices, the inverse is necessarily dense (Lemma 33, supplement).\n\nFinally, we discuss your question regarding existing work for sparse inputs. Current algorithms with runtimes listed as $\\ge n^\\omega$ are at least bottlenecked by solving sparse linear systems. Such algorithms with improved running times do exist in the recent literature (see e.g. “Solving Sparse Linear Systems Faster than Matrix Multiplication” and “Matrix anti-concentration inequalities with applications”), but these assume very sparse matrices, and yield runtimes which remain superquadratic (e.g., roughly $n^{2.27}$ time for $O(n)$-sparse matrices)."}]

Author rebuttal:
Reviewers HjkM and pK6D asked about practical implementations of our algorithm. We agree that experiments are an important next step towards bringing the results of our paper to practice. Our primary motivation was theoretical: existing guarantees for the problems we study are off from linear time by (sometimes large) polynomial factors in the problem dimension. We close these gaps through our main results, which pave the way for more practical implementations. Our framework builds upon several tools in lines of active research with existing implementations, such as packing SDP solvers and sketching techniques, but which need to be combined in a careful way in order to obtain fast implementations of our overall algorithm; we leave this endeavor to interesting future work.

We also note that Appendix C of the supplement provides a new constant-factor optimal analysis of the Jacobi preconditioner, which is already widely-used in practice for outer scaling.

Meta-review: Three reviewers agree unanimously that the paper is solid and worthy of acceptance. The one dissenting reviewer confesses that they are "not [an] expert in this field and with a very limited amount of time". From my own reading, I am also very impressed by the progress made in this work compared to prior work. Please incorporate reviewer feedback into the final camera-ready version.
Decision: Accept (poster)