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.
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?
Questions
In Algorithm 1, it is required that $\lambda_{\max}(M_i)\in [1,2]$. Is it just for convenience?
What is the runtime bottleneck of Algorithm 1?
Rating
8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Limitations
The limitations are addressed.