Breaking the Barrier of Self-Concordant Barriers: Faster Interior Point Methods for M-MatricesOberseminar Discrete Optimization
by
Arithmeum, Lennéstr., 2 - Seminarraum
Arithmeum / Research Institute for Discrete Mathematics
We study two fundamental problems in optimization: (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 limits the iteration complexity of IPMs to $\widetilde{O}(n^{1/2})$, where $n$ is 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 $\widetilde{O}(n^{1/3})$ iterations. As a corollary, using fast Laplacian solvers, we obtain an $\ell_{2}$ flow diffusion algorithm with depth $\widetilde{O}(n^{1/3})$ and work $\widetilde{O}(n^{1/3}\cdot \mathrm{nnz})$. This marks a significant instance where a standard log-barrier IPM permits provably fewer than $O(n^{1/2})$ iterations.
The Oberseminar takes place in the Seminarraum, 1st floor. Participants are invited to have coffee or tea in the lounge before.
S. Held, S. Hougardy, L. Végh, J. Vygen