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 O 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 O n 1/3 iterations. As a corollary, using fast Laplacian solvers, we obtain an ℓ 2 flow diffusion algorithm with depth O n 1/3 and work O 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.