1. 多种迭代算法支持#

1.1. 已实现的求解器#

skscope 提供了几种求解器，每种求解器都有相似的接口，用于解决稀疏约束优化问题：

\[\arg\min\limits_{\theta \in R^p} f(\theta) \text{ s.t. } ||\theta||_0 \leq s.\]

以下是当前可用的求解器列表：

  • GraspSolver: 实现了梯度支持追踪（GraSP）算法，该算法推广了压缩采样匹配追踪（CoSaMP）算法 [1]。

  • ScopeSolver: 实现了稀疏约束优化切片迭代（SCOPE）算法，该算法推广了自适应最佳子集选择（ABESS）算法 [10]。

  • HTPSolver: 实现了硬阈值追踪（HTP）算法 [2] [3]。

  • IHTSolver: 实现了迭代硬阈值（IHT）算法 [4] [5]。

  • FobaSolver: 实现了前向-后向贪心算法 [6].

  • OMPSolver: 实现了正交匹配追踪（OMP）算法 [7] [8]。

  • ForwardSolver: 实现了统计学文献中的前向逐步算法 [9]。

1.1.1. ForwardSolver 和 OMPSolver 的详细信息#

OMPSolver 和 ForwardSolver 相似但不完全相同，尽管这两种方法都是通过依次添加最重要的变量来解决SCO。它们的区别在于“重要性”的数学定义。

  • 对于OMPSolver，重要性定义为：

    \[\arg\max_{j\in \{1, \ldots, p\}}|\nabla_{\boldsymbol{\theta}_j} f(\boldsymbol{\theta}^{(t)})|\]

    其中\(\boldsymbol{\theta}^{(t)}\)是当前估计的参数。

  • 至于ForwardSolver，重要性是通过以下方式衡量的：

    \[\arg\max_{j\in \{1, \ldots, p\}} \big( f(\boldsymbol{\theta}^{(t)}) - \min_{ \left\{ \boldsymbol{\theta} \in \mathbb{R}^p: \textup{supp}(\boldsymbol{\theta}) = \{j\} \cup \mathcal{A}^{(t)} \right\} } f(\boldsymbol{\theta}) \big)\]

    其中\(\mathcal{A}^{(t)}\)是\(\boldsymbol{\theta}^{(t)}\)的支持集。

我们可以看到，在ForwardSolver中计算重要性涉及更多的密集计算，因为它必须解决优化问题：

\[\min_{ \{ \boldsymbol{\theta}: \textup{supp}(\boldsymbol{\theta}) = \mathcal{A}^{(t)} \cup \{j\} \} } f(\boldsymbol{\theta}).\]

对于每一个\(j \in \{1, \ldots, p\}\)。另一方面，OMPSolver中使用的准则可以被视为ForwardSolver准则的一阶近似，并且可以以更低的成本计算。然而，我们可以预期ForwardSolver会比OMPSolver带来更好的统计性能。

最后，对于在OMPSolver和ForwardSolver之间的选择，我们提供以下指南：

  • 如果 p 很小（例如，小于10），在小样本情况下 ForwardSolver 是诱人的选择；否则，首选应该是 OMPSolver。

1.2. 参考#

  • [1]: Bahmani, S., Raj, B., & Boufounos, P. T. (2013). 贪婪稀疏约束优化. 机器学习研究杂志, 14(1), 807-841.

  • [2] Foucart, S. (2011). 硬阈值追踪：一种用于压缩感知的算法。SIAM数值分析杂志, 49(6), 2543-2563.

  • [3] 袁, X. T., 李, P., & 张, T. (2017). 梯度硬阈值追踪. J. Mach. Learn. Res., 18(1), 6027-6069.

  • [4] Blumensath, T., & Davies, M. E. (2009). 压缩感知的迭代硬阈值方法。应用与计算谐波分析, 27(3), 265-274.

  • [5] Jain, P., Tewari, A., & Kar, P. (2014). 关于高维m估计的迭代硬阈值方法。神经信息处理系统进展，27。

  • [6] Liu, J., Ye, J., & Fujimaki, R. (2014). 针对基数约束下的一般凸光滑函数的前向后向贪心算法。在国际机器学习会议上（第503-511页）。PMLR。

  • [7] Wang, J., Kwon, S., & Shim, B. (2012). 广义正交匹配追踪. IEEE信号处理汇刊, 60(12), 6202-6216.

  • [8] Tropp, J. A., & Gilbert, A. C. (2007). 通过正交匹配追踪从随机测量中恢复信号。IEEE信息理论汇刊, 53(12), 4655-4666.

  • [9] Hastie, T., Tibshirani, R., Friedman, J. H., & Friedman, J. H. (2009). 统计学习的要素：数据挖掘、推理和预测（第2卷，第1-758页）。纽约：施普林格。

  • [10] 朱, J., 温, C., 朱, J., 张, H., & 王, X. (2020). 一种用于最佳子集选择问题的多项式算法。美国国家科学院院刊, 117(52), 33117-33123.