图形LASSO中算法解法与MATLAB CVX解法的区别？

Question

图形最小绝对收缩和选择算子，由 Jerome Friedman、Trevor Hastie 和 Robert Tibshirani 引入（“使用图形套索进行稀疏逆协方差估计”，2014 年）。他们建议使用块坐标下降算法来解决问题（参见 Rahul Mazumder 和 Trevor Hastie 的“图形套索：新见解和替代方案”）。我使用 CVX 编写了这个简单的 MATLAB 代码，给定

X

（大小为

m,n

的回归矩阵）：

S = cov(X,0);

cvx_begin
    variable theta(n,n) semidefinite
    minimize (trace(S*theta)-log_det(theta)+lambda*norm(theta,1))
cvx_end

块坐标下降算法解法和CVX解法有什么区别？ CVX 可以设置为给出完全相同的解决方案吗？ 该问题涉及图形 LASSO 算法，但可以扩展到其他类似问题，其中作者建议特定算法（例如 ADMM），但可以通过优化包找到解决方案。

Answer 1

已提供

1. 有一个独特的解决方案（如果你的目标是正则化的，这应该是正确的，这似乎是最后一项的结果。）
2. 两种实现都没有错误。

两种实现都应该返回完全相同的解决方案，因为问题是凸半定程序。您应该观察到的差异是

1. 运行时，一个可能会比另一个运行时间更长，我敢打赌你的实现使用通用求解器包（CVX），所以应该更慢。
2. 内存使用情况，我再次预计通用（未调整）包应该消耗更多内存。
3. 数值稳定性，一般来说，某些实现在数值上会更加稳定。也就是说，如果您使用弱正则化（非常小的 lambda），您可能会发现某些实现无法收敛，而其他实现仍然有效。

对于小问题和玩具问题，这应该不是什么大问题（如果您是学者，通常会出现这种情况。）如果您是一个试图在现实世界中做一些有用的事情的人，那么运行时和内存使用往往非常重要，因为它们控制您可以用您的方法解决哪些尺寸问题。

了解每种方法的相对局限性的唯一方法是同时实施并尝试这两种方法！至少，我会实现并运行这两种方法作为健全性检查，以确保两种实现都可能是正确的（两种实现都不正确并在输入范围内报告相同结果的可能性非常低。）