SMOOTH OPTIMIZATION APPROACH FOR SPARSE COVARIANCE SELECTION
SMOOTH OPTIMIZATION APPROACH FOR SPARSE COVARIANCE SELECTION
复制标题
DOI：
10.1137/070695915
复制
发表时间：
2009-01-01
影响因子：
3.1
通讯作者：
Lu, Zhaosong
中科院分区：
文献类型：
--
作者：
Lu, Zhaosong
本文首先研究了一类目标函数允许光滑凸极小化重新表述的非光滑严格凹极小化问题的光滑优化方法。特别地，我们应用Nesterov平滑优化技术[Y。E.涅斯捷罗夫博士Akad。Nauk SSSR, 269(1983)，第543-547页；Y. E. Nesterov，数学。程序设计，103 (2005),pp. 127-152]到它们的对偶对应的光滑凸问题。结果表明，该方法对原始问题和对偶问题的最优解的迭代复杂度均为0（1根）。然后，我们讨论了该方法在稀疏协方差选择中的应用，该方法近似解决为l(1)范数惩罚最大似然估计问题，并且还提出了该方法的一种变体，该方法在我们的计算实验中大大优于后者。最后，我们将这些方法与其他一阶方法，即Nesterov的O（1/epsilon）光滑逼近方案和[A]研究的块坐标下降法的性能进行了比较。d’aspremont， O. Banerjee， L. El Ghaoui, SIAM J. Matrix Anal。达成。， 30(2008)，第56-66页；J. Friedman， T. Hastie和R. Tibshirani，生物统计学，9 (2008),pp. 432-441]在一组随机生成的实例上的稀疏协方差选择。它表明，我们的平滑优化方法实质上优于上述第一种方法，而且，它的变体实质上优于上述两种方法。
In this paper we first study a smooth optimization approach for solving a class of nonsmooth strictly concave maximization problems whose objective functions admit smooth convex minimization reformulations. In particular, we apply Nesterov's smooth optimization technique [Y. E. Nesterov, Dokl. Akad. Nauk SSSR, 269 (1983), pp. 543-547; Y. E. Nesterov, Math. Programming, 103 (2005), pp. 127-152] to their dual counterparts that are smooth convex problems. It is shown that the resulting approach has O(1 root epsilon) iteration complexity for finding an epsilon-optimal solution to both primal and dual problems. We then discuss the application of this approach to sparse covariance selection that is approximately solved as an l(1)-norm penalized maximum likelihood estimation problem, and also propose a variant of this approach which has substantially outperformed the latter one in our computational experiments. We finally compare the performance of these approaches with other first-order methods, namely, Nesterov's O(1/epsilon) smooth approximation scheme and block-coordinate descent method studied in [A. d'Aspremont, O. Banerjee, and L. El Ghaoui, SIAM J. Matrix Anal. Appl., 30 (2008), pp. 56-66; J. Friedman, T. Hastie, and R. Tibshirani, Biostatistics, 9 (2008), pp. 432-441] for sparse covariance selection on a set of randomly generated instances. It shows that our smooth optimization approach substantially outperforms the first method above, and moreover, its variant substantially outperforms both methods above.