机器算法验证 - L1 正则化强制凸函数的稀疏性 - 吾爱随笔录

L1 正则化强制凸函数的稀疏性

机器算法验证套索正则化凸的

2022-03-24 21:56:26

我有一个凸函数 $f \colon \mathbb{R}^n \to \mathbb{R}$ 我使用 L1 正则化最小化： $\DeclareMathOperator*{\argmin}{arg\,min}$

x^{*} = \underset{x}{a r g m i n} f (x) + λ | | x | |_{1}

$x^*=\argmin_x f(x) + \lambda ||x||_1$

我可以假设我实现了稀疏性，即 $x^* \in \mathbb{R}^n$ 会有几个非零条目？更明确地说，我可以假设 $||x^*||_0 := |\{i \mid x_i \neq 0\}|$ 是小？

特例：套索

众所周知，在以下情况下答案是肯定的 $f(x)=\frac{1}{N} \sum_{i=1}^N ||y-Xx||_2^2$ --- 这是套索。但是一般凸函数呢 $f$ ?

我的想法

如果有更好的方法来解决这个问题，请随意忽略问题的其余部分。

第 1 步：在我看来，以下最小化问题产生的非零条目很少：

\underset{| | x | |_{1} \leq δ}{a r g m i n} f (x)

$\argmin_{||x||_1\leq\delta} f(x)$ 对此的推理是标准的（例如，“统计学习的要素”，图 3.11）。我不完全确定它是否真的适用于一般凸

f

$f$ ，但至少对“大多数”而言，认为它确实如此似乎是合理的

f

$f$ （这里有任何额外的见解表示赞赏）。

第 2 步：我对这种方法的主要担忧是是否确实存在 $\delta$ （这取决于 $\lambda$ )，这样：

x^{*} \in \underset{| | x | |_{1} \leq δ}{a r g m i n} f (x)

$x^* \in \argmin_{||x||_1 \leq \delta} f(x)$

我将如何展示这个？

2个回答

关于你关于一般凸函数的问题，你将得到一个稀疏的解决方案，因为你应用了一个稀疏诱导范数（其中 l1 是一个这样的范数）。如需更多信息，请在此处阅读第 1.3 节（包括）：https ://hal.archives-ouvertes.fr/hal-00613125v1/document

一般来说（取自链接）：

如果您有一个凸优化问题，例如：
$min_{ω \in> R^{p}} f (ω) + λ Ω (ω)$ $\min_{\omega \in > \mathbb{R}^p} f(\mathbf{\omega}) + \lambda \Omega(\mathbf{\omega})$ 其中是凸可微函数，是稀疏诱导范数，你会得到一个稀疏的解决方案。 $f:\mathbb{R}^p \rightarrow \mathbb{R}$ $\Omega:\mathbb{R}^p \rightarrow\mathbb{R}$

如果你把问题写成一个约束问题，你可以看到它：在最优情况下，的梯度在任何解属于正锥。换句话说，对于足够小的值，即约束是有效的，f 的水平集 ( 相切
$min_{ω \in R^{p}} f (ω) such that Ω (ω) \leq μ, for some μ \in R_{+}$ $\min_{\omega \in \mathbb{R}^p} f(\mathbf{\omega}) \quad \textrm{such that} \quad \Omega(\mathbf{\omega}) \leq \mu, \\ \textrm{for some}\;\mu \in \mathbb{R}_{+}$ $f$ $\hat{\mathbf{\omega}}$ $\mathcal{B} =\{{\mathbf{\omega} \in \mathbb{R}^p; \; \Omega(\mathbf{\omega}) \leq \mu\}}$ $\mu$ $f$ $f(\hat{\mathbf{\omega}})$ $\mathcal{B}$ .

因此，球的性质直接相关。例如，当是对应于二维的菱形图案和三维的金字塔。特别是，的非光滑性而表现出一些奇异点。这些奇异点位于的轴上，因此如果的水平集恰好在这些点之一相切，则获得稀疏解。 $\mathcal{B}$ $\hat{\mathbf{\omega}}$ $\Omega$ $l_1$ $\mathcal{B}$ $\mathcal{B}$ $\Omega$ $\mathbb{R}^p$ $f$

弗朗西斯·巴赫、鲁道夫·杰纳顿、朱利安·梅拉尔、纪尧姆·奥博津斯基。使用 SparsityInducing Penalties 进行优化。2011. ffhal-00613125v1

不，f(x) = (|x|-1)**2 是凸的，并且有无数个零。

其它你可能感兴趣的问题

上一篇从 GAMLSS 中的系数和结创建样条下一篇您可以在分析时间序列数据集之前删除缺失值吗？