Matrix Scaling and Balancing via Box Constrained Newton's Method and Interior Point Methods

By Michael B. Cohen, Aleksander Madry, Dimitris Tsipras, Adrian Vladu. 2017

123 citations recorded by the source corpus.

In this paper, we study matrix scaling and balancing, which are fundamental problems in scientific computing, with a long line of work on them that dates back to the 1960s. We provide algorithms for both these problems that, ignoring logarithmic factors involving the dimension of the input matrix and the size of its entries, both run in time \widetilde{O}(m\log \kappa \log^2 (1/≥ilon)) where ≥ilon is the amount of error we are willing to tolerate. Here, \kappa represents the ratio between the largest and the smallest entries of the optimal scalings. This implies that our algorithms run in nearly-linear time whenever \kappa is quasi-polynomial, which includes, in particular, the case of strictly positive matrices. We complement our results by providing a separate algorithm that uses an interior-point method and runs in time \widetilde{O}(m^{3/2} \log (1/≥ilon)).In order to establish these results, we develop a new second-order optimization framework that enables us to treat both problems in a unified and principled manner. This framework identifies a certain generalization of linear system solving that we can use to efficiently minimize a broad class of functions, which we call second-order robust. We then show that in the context of the specific functions capturing matrix scaling and balancing, we can leverage and generalize the work on Laplacian system solving to make the algorithms obtained via this framework very efficient.

Subfields: Computational Mathematics, Computational Theory and Mathematics, Numerical Analysis

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mathematics

In Computational Theory and Mathematics

In Numerical Analysis

Citations in the corpus

How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD (2018, background): “2 In matrix scaling [7, 10], given a non-negative matrix, one wants to re-scale its rows and columns to make it doubly stochastic.”
Solving linear programs in the current matrix multiplication time (2018, background): “As for many important linear programs (and convex programs), the number of iterations has been decreased, including maximum ﬂow [Mad13, Mad16], minimum cost ﬂow [CMSV17], geometric median [CLM + 16], matrix scaling and balancing [CMTV17], and (cid:96) p regression [BCLL18].”
Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm (2018, background): “While the entropy-regularized OT problem allows to use other matrix-scaling algorithms such as (Allen-Zhu et al., 2017; Cohen et al., 2017) with theoretical guarantees, the authors do not provide any experimental re-sults, so the practical implementability of these algorithms is questionable.”
Global linear convergence of Newton's method without strong-convexity or Lipschitz gradients (2018, methodology): “We were inspired by [10] who obtain an efficient algorithm for matrix scaling using ideas very similar to here.”
Learning Two Layer Rectified Neural Networks in Polynomial Time (2018, background): “It has frequently been observed in practice that many pre-trained neural-networks exhibit correlation and a low-rank structure Denil et al. (2013); Denton et al.”
How To Make the Gradients Small Stochastically (2018, background): “” Another example is matrix scaling [4, 7], where given a non-negative matrix A ∈ Rn×m, we want to find positive diagonal matrices X ∈ Rn×n, Y ∈ Rm×m such that XAY is close to being doubly-stochastic.”