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

2025/04/29 by Vladu, Adrian
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2504.20619

Abstract

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

Citations

• Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
• Faster Maxflow via Improved Dynamic Spectral Vertex Sparsifiers
• Faster Sparse Minimum Cost Flow by Electrical Flow Localization
• Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg-Rao
• Solving Linear Programs in the Current Matrix Multiplication Time
• Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs
• p-Norm Flow Diffusion for Local Graph Clustering
• Circulation Control for Faster Minimum Cost Flow in Unit-Capacity Graphs
• Solving Tall Dense Linear Programs in Nearly Linear Time
• Faster Energy Maximization for Faster Maximum Flow
• Perron-Frobenius Theory in Nearly Linear Time: Positive Eigenvectors, M-matrices, Graph Kernels, and Other Applications
• An homotopy method for ℓ_p regression provably beyond self-concordance and in input-sparsity time
• Matrix Scaling and Balancing via Box Constrained Newton's Method and Interior Point Methods
• Much Faster Algorithms for Matrix Scaling
• Computing Maximum Flow with Augmenting Electrical Flows
• Geometric Median in Nearly Linear Time
• Sparsified Cholesky and Multigrid Solvers for Connection Laplacians
• The entropic barrier: a simple and optimal universal self-concordant barrier
• An Efficient Parallel Solver for SDD Linear Systems
• Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back
• Faster Approximate Lossy Generalized Flow via Interior Point Algorithms

Related

• Interior Point Methods with a Gradient Oracle
• No self-concordant barrier interior point method is strongly polynomial
• Matrix Scaling and Balancing via Box Constrained Newton's Method and Interior Point Methods
• Solving Linear Programs with Sqrt(rank) Linear System Solves
• Solving SDP Faster: A Robust IPM Framework and Efficient Implementation