A proximal Newton framework for composite minimization: Graph learning without Cholesky decompositions and matrix inversions
This work addresses graph learning challenges for researchers and practitioners by offering a more efficient method, though it appears incremental as it builds on existing proximal Newton frameworks.
The authors tackled the problem of convex composite minimization by proposing a proximal Newton algorithm with local quadratic convergence, and applied it to sparse inverse covariance estimation to avoid Cholesky decompositions and matrix inversions, making it suitable for parallel and distributed implementations.
We propose an algorithmic framework for convex minimization problems of a composite function with two terms: a self-concordant function and a possibly nonsmooth regularization term. Our method is a new proximal Newton algorithm that features a local quadratic convergence rate. As a specific instance of our framework, we consider the sparse inverse covariance matrix estimation in graph learning problems. Via a careful dual formulation and a novel analytic step-size selection procedure, our approach for graph learning avoids Cholesky decompositions and matrix inversions in its iteration making it attractive for parallel and distributed implementations.