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 Õ(n^1/2), 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 Õ(n^1/3) iterations. As a corollary, using fast Laplacian solvers, we obtain an ℓ_2 flow diffusion algorithm with depth Õ(n^1/3) and work Õ(n^1/3·nnz). This result marks a significant instance in which a standard log-barrier IPM permits provably fewer than Θ(n^1/2) iterations.