Graphical Nonconvex Optimization via an Adaptive Convex Relaxation
We consider the problem of learning high-dimensional Gaussian graphical models. The graphical lasso is one of the most popular methods for estimating Gaussian graphical models. However, it does not achieve the oracle rate of convergence. In this paper, we propose the graphical nonconvex optimization for optimal estimation in Gaussian graphical models, which is then approximated by a sequence of convex programs. Our proposal is computationally tractable and produces an estimator that achieves the oracle rate of convergence. The statistical error introduced by the sequential approximation using a sequence of convex programs is clearly demonstrated via a contraction property. The proposed methodology is then extended to modeling semiparametric graphical models. We show via numerical studies that the proposed estimator outperforms other popular methods for estimating Gaussian graphical models.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
GNCGCP - Graduated NonConvexity and Graduated Concavity Procedure
In this paper we propose the Graduated NonConvexity and Graduated Concavity Procedure (GNCGCP) as a general optimization framework to approximately solve the combinatorial optimization problems on the set of partial perm…
Combinatorial OptimizationGraph MatchingA Graphical Global Optimization Framework for Parameter Estimation of Statistical Models with Nonconvex Regularization Functions
Optimization problems with norm-bounding constraints arise in a variety of applications, including portfolio optimization, machine learning, and feature selection. A common approach to these problems involves relaxing th…
feature selectionglobal-optimizationparameter estimationPortfolio OptimizationStatistical Limits of Convex Relaxations
Many high dimensional sparse learning problems are formulated as nonconvex optimization. A popular approach to solve these nonconvex optimization problems is through convex relaxations such as linear and semidefinite pro…
Sparse LearningStochastic Block ModelContinuous Relaxation of MAP Inference: A Nonconvex Perspective
In this paper, we study a nonconvex continuous relaxation of MAP inference in discrete Markov random fields (MRFs). We show that for arbitrary MRFs, this relaxation is tight, and a discrete stationary point of it can be …
Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution under Random Designs
We investigate the effectiveness of convex relaxation and nonconvex optimization in solving bilinear systems of equations under two different designs (i.e.$~$a sort of random Fourier design and Gaussian design). Despite …