A proximal Newton framework for composite minimization - Graph learning without Cholesky decompositions and matrix inversions

Aug 6, 2026

Algorithmic framework for convex minimization of a composite objective with a self-concordant term and a potentially nonsmooth regularizer. A new proximal Newton method provides local quadratic convergence. As an application, the framework addresses sparse inverse covariance estimation for graph learning via a careful dual formulation and an analytic step-size selection rule. The resulting graph learning iterations avoid Cholesky decompositions and matrix inversions, improving suitability for parallel and distributed implementations.

LanguageEnglish

CategoryTechnology

FormatPDF

Pages11

Reading Time28 min

AccessFree to download

Introduction

Sparse inverse covariance and graph learning formulation

Existing optimization methods and their complexity

Proposed proximal-Newton framework

View metadata, citation and similar [papers at ](papers at core.ac.uk)[core.ac.uk](papers at core.ac.uk) brought to you by CORE provided by Infoscience- École polytechnique fédérale de Lausanne A proximal Newton framework for composite minimization: Graph learning without Cholesky decompositions and matrix inversions Quoc Tran Dinh [quoc.trandinh@epfl.ch](quoc.trandinh@epfl.ch) Anastasios Kyrillidis [anastasios.kyrillidis@epfl.ch](anastasios.kyrillidis@epfl.ch) Volkan Cevher [volkan.cevher@epfl.ch](volkan.cevher@epfl.ch) 􀀓 Laboratory for Information and Inference Systems, Ecole Polytechnique F􀀓ed􀀓erale de Lausanne, Switzerland Abstract 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 speci􀀌c 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. 1. Introduction Sparse inverse covariance matrix estimation is a key step in graph learning problems. To understand the setup, let us consider learning a Gaussian Markov random 􀀌eld (GMRF) of p nodes/variables from adataset D := fx1 ; x2 ; : : : ; xmg, where xj 2 D is a pdimensional random vector with Gaussian distribution N (􀀖 ; 􀀆) . Let 􀀂 = 􀀆 􀀀1 be the inverse covariance (orthe precision) matrix for the model. To satisfy the conditional dependencies with respect to the GMRF, 􀀂 must have zero in 􀀂ij corresponding to the absence of an edge between node i and node j (Dempster, 1972) . To this end, one can use the empirical covariance matfsroiixrtncuetathoeellyem,earthpinirsitchaalepuprestnoideacmrlhatyieissngfcuognnrdvaphamergeestnttorualtctlyheuirltelr-u.pUose cnedo-- Laboratory for Information and Inference Systems (LIONS), EPFL, Lausanne, Switzerland. Copyright 2013 by the author(s) . variance at a (1= pm)-rate (Dempster, 1972) . Hence, inferring the true graph structure accurately requires an overwhelming number of samples. Unsurprisingly, we usually have less samples than the ambient dimension, compounding the di􀀎culty of estimation. While the possible GMRF structures are exponentially large, the most interesting graphs are rather simple with a sparse set of edges. Provable learning of such graphs can be achieved by ` 1-norm regularization in the maximum log-likelihood estimation: 􀀂 􀀃 2 arg􀀂 m0in n~~ ~~log~~ ~~det()+tr(􀀂})+kvec{z(􀀂)k1} o ; (1) =:f (􀀂) =:g(􀀂) where 􀀚 > 0 is a parameter to balance the 􀀌delity error and the sparsity of the solution and vec is the vectorization operator. Here, f (􀀂) corresponds to the empirical log-likelihood and g (􀀂) is the sparsitypromoting term. Under this setting, the authors in (Ravikumar et al. , 2011) prove that m = O (d2 log p) is su􀀎cient for correctly estimating the GMRF, where dis the graph node-degree. Moreover, the above formulation still makes sense for learning other graph models, such as the Ising model, due to the connection off (􀀂) to the Bregman distance (Banerjee et al. , 2008) . Numerical solution methods for solving problem (1) have been widely studied in the literature now. For instance, in (Banerjee et al. , 2008; Scheinberg & Rish, 2009; Scheinberg et al. , 2010; Hsieh et al. , 2011; Rolfset al. , 2012; Olsen et al. , 2012) the authors proposed 􀀌rst order primal and dual approaches to (1) and used state-of-the-art structural convex optimization techniques such as coordinate descent methods and Lassobased procedures. Alternatively, the authors in (Hsieh et al. , 2011; Olsen et al. , 2012) focused on the second order methods and, practically, achieved fast m

FAQs

What type of optimization problem does the proposed framework address?

It targets convex minimization of a composite function with two terms: a self-concordant function and a possibly nonsmooth regularization term.

What convergence behavior does the proximal Newton algorithm achieve?

The method is designed to have local quadratic convergence, with a phase that transitions into a provable quadratic region.

How does the approach help in graph learning compared with prior methods?

In graph learning for sparse inverse covariance estimation, the method avoids Cholesky decompositions and matrix inversions in its iterations, which supports parallel and distributed computation.

Aug 6, 2026

Upload by Olivia Brown