这一章干货比较多,看起来比较累,收获也比较大。
坚持看,坚持写。
写公式真累,希望segmentfault能尽快支持输入latex公式
一直拿不下最优化这块东西,理论和实践都有欠缺,争取这回能拿下。
$2.1 Introduction
$2.1.1 loss函数和稀疏性Inducing范数
$$\min_{\omega\in\mathbb{R}}f(\omega)+\lambda\Omega(\omega)$$
这一章介绍在一般的优化目标(loss function)下,增加参数的稀疏结构。通过通过引入1范数实现。$$\Omega(\omega)=||\omega||_1$$
通过引入group wise的范数,实现group之间的稀疏性,而group内部则没有稀疏性。
。这里G是{1,...,p}的划分函数(partition function),
是weight
更一般的,有范数
$2.1.2 最优化工具
$2.1.2.1 次梯度subgradients
定义次梯度:
。当g可导时,次梯度就为g的导数。
prop 2.1: 对函数f,w是f的最小值点
proof: 根据次梯度的定义可以直接得出
问题 的最优解为
proof:w可以取正、负、0,分别对应绝对值函数的次梯度为1、-1、[-1,1],
目标函数的次梯度为
$$w-x+\lambda(w>0)$$
$$w-x-\lambda(w<0)$$
$$-x+\lambda* [-1,1](w=0)$$
$$ 即 sgn(w)(|w|+\lambda)-x (w!=0),\ \lambda[-1,1]-x (w=0)$$
所以当$$|x| <= \lambda$$ 时,w=0。当$$ |x| > \lambda$$ 时, $$|w| = sgn(x)*x-\lambda, w = x - sgn(x)* \lambda $$
$2.1.2.2 对偶范数与最优化条件
定义对偶范数: s.t.
由范数的性质,上面的max必定是在的w上取到。
可以证明,
其实上面两个式子可以合并成一个,因为w=0时,第二个式子也是等价的。
proof: 根据定义,
对任意w’成立。
令$$w'=(1+\lambda)w$$, 得$$\lambda z^T w \leq \lambda\Omega(w)$$ 对任意比较小的成立,所以$$ z^T = \Omega(w)$$ 。
代回去后得到$$ z^T w' \leq \Omega(w')$$恒成立。即$$z^T w' \leq 1$$ 对$$\Omega(w')=1$$的w'恒成立。即$$\Omega^*(z) \leq 1$$
原最优问题的最优解满足条件:$$-\frac{1}{\lambda}\delta f(w) \in \partial\Omega(w) $$
特别的,对
\Omega(w)为1范数时,要求
$$ z^w = \sum z_i w_i \leq ||w||{1} = \sum |w_i|且\Omega^*(z)=||z||{\infinity}=max |z_i| \leq 1$$
所以$$z_i=sgn(w_i) \ if\ w_i \neq 0;\ |z_i| \leq 1\ if\ w_i=0$$
特别的对lasso问题,$$f(w) = \frac{1}{2}||y-Xw||_2^2, z = -\frac{1}{\lambda}\delta f(w) = X^T(y-Xw)$$
$2.1.2.3 Frenchel共轭与对偶gap
定义 $$ f^*(z) = sup_{w\in\mathbb{R}}<z,w>-f(w) $$
有关Frenchel共轭函数的更多介绍,以及共轭函数的推导,见Convex conjugate
注:对偶gap可以算是凸优化里的核心,但这里我们只说结论。而且结论也不仅完全,需要查阅更多的资料
疑点:
- 无约束问题的对偶形式 vs 带约束问题的对偶形式
- 对偶变量与原函数梯度的关系
- 线性变换后的对偶问题推导
Prop 2.2: $$ min_w f(w)+\lambda \Omega(w) \geq max_{\Omega^(z)\leq \lambda} -f^(z) $$
当f可微,凸时,上述等式成立。且在各自的最优解处
$$ z^* = \Delta f(w^*)$$
注:优化z类似优化f(w)的梯度?
带一个线性变换的对偶形式(见原书)