Breaking the Barrier of Self-Concordant Barriers: Faster Interior Point Methods for M-Matrices

We study two fundamental optimization problems: (1) scaling a symmetric positive definite matrix by a positive diagonal matrix so that the resulting matrix has row and column sums equal to 1; and (2) minimizing a quadratic function subject to hard non-negativity constraints. Both problems lend themselves to efficient algorithms based on interior point methods (IPMs). For general instances, standard self-concordance theory places a limit on the iteration complexity of these methods at $\tilde{O}\left(n^{1\mathrm{/}2}\right)$, where $n$ denotes the matrix dimension. We show via an amortized analysis that, when the input matrix is an M-matrix, an IPM with adaptive step sizes solves both problems in only $\tilde{O}\left(n^{1\mathrm{/}3}\right)$ iterations. As a corollary, using fast Laplacian solvers, we obtain an ${\mathrm{\ell }}_2$ flow diffusion algorithm with depth $\tilde{O}\left(n^{1\mathrm{/}3}\right)$ and work $\tilde{O}$$(n^{1\mathrm{/}3}\cdot \text{nnz})$. This result marks a significant instance in which a standard log-barrier IPM permits provably fewer than $\mathrm{\Theta }\left(n^{1\mathrm{/}2}\right)$ iterations.