Please use this identifier to cite or link to this item:
Title: A block coordinate gradient descent method for regularized convex separable optimization and covariance selection
Authors: Yun, S.
Tseng, P.
Toh, K.-C. 
Keywords: ℓ1- penalization
Block coordinate gradient descent
Convex optimization
Covariance selection
Global convergence
Linear rate convergence
Maximum likelihood estimation
Issue Date: Oct-2011
Citation: Yun, S., Tseng, P., Toh, K.-C. (2011-10). A block coordinate gradient descent method for regularized convex separable optimization and covariance selection. Mathematical Programming 129 (2) : 331-355. ScholarBank@NUS Repository.
Abstract: We consider a class of unconstrained nonsmooth convex optimization problems, in which the objective function is the sum of a convex smooth function on an open subset of matrices and a separable convex function on a set of matrices. This problem includes the covariance selection problem that can be expressed as an ℓ1-penalized maximum likelihood estimation problem. In this paper, we propose a block coordinate gradient descent method (abbreviated asBCGD)for solving this class of nonsmooth separable problems with the coordinate block chosen by a Gauss-Seidel rule. The method is simple, highly parallelizable, and suited for large-scale problems. We establish global convergence and, under a local Lipschizian error bound assumption, linear rate of convergence for this method. For the covariance selection problem, the method can terminate in O(n3/ε) iterations with an ε-optimal solution. We compare the performance of the BCGD method with the first-order methods proposed by Lu (SIAM J Optim 19:1807-1827, 2009; SIAM J Matrix Anal Appl 31:2000-2016, 2010) for solving the covariance selection problem on randomly generated instances. Our numerical experience suggests that the BCGD method can be efficient for largescale covariance selection problems with constraints. © Springer and Mathematical Optimization Society 2011.
Source Title: Mathematical Programming
ISSN: 00255610
DOI: 10.1007/s10107-011-0471-1
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Jan 31, 2023


checked on Jan 31, 2023

Page view(s)

checked on Feb 2, 2023

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.