Proximal Algorithms 3 Interpreta

作者: 馒头and花卷 | 来源:发表于2019-06-08 22:51 被阅读0次

Proximal Algorithms 3 Interpreta
Proximal Algorithms 4 Algorithms
Proximal Algorithms 7 Examples a
Proximal Algorithms 5 Parallel a
Proximal Algorithms 2 Properties
Proximal Algorithms 6 Evaluating
Proximal Algorithms 1 介绍
讲解：Data Structures、Algorithms、ja
Introduction to Algorithms, 3rd
远端与近端

Proximal Algorithms

这一节，作者总结了一些关于proximal的一些直观解释

Moreau-Yosida regularization

内部卷积(infimal convolution)：
$(f \: \Box \: g)(v)=\inf_x (f(x)+g(v-x))$

Moreau-Yosida envelope 或者 Moreau-Yosida regularization 为:
$M_{\lambda f}=\lambda f \: \Box \: (1/2)\|\cdot\|_2^2$ ，于是:

在这里插入图片描述
事实上，这就是，我们在上一节提到过的东西。就像在上一节一样，可以证明:

以及:

虽然上面的我不知道在不可微的条件下怎么证明.
于是有与上一节同样的结果:

在这里插入图片描述
总结一下就是，近端算子，实际上就是最小化, 等价于，即:

这个，需要通过Moreau分解得到.

与次梯度的联系 $\mathbf{prox}_{\lambda f} = (I + \lambda \partial f)^{-1}$

在这里插入图片描述
上面的式子，有一个问题是，这个映射是单值函数吗（论文里也讲，用关系来讲更合适），因为的原因，不过，论文的意思好像是的，不过这并不影响证明:

在这里插入图片描述

改进的梯度路径

就像在第一节说的，和之前有关Moreau envelope表示里讲的:
$\mathbf{prox}_{\lambda f} (x) = x - \lambda \nabla M_{\lambda f}(x)$
实际上， $\mathbf{prox}_{\lambda f}$ 可以视为最小化Moreau envelope的一个迭代路径，其步长为 $\lambda$ . 还有一些相似的解释.
假设 $f$ 是二阶可微的,且 $\nabla^2 f(x) \succ0$ （表正定）,当 $\lambda \rightarrow 0$ :
$\mathbf{prox}_{\lambda f} (x) = (I + \lambda \nabla f)^{-1} (x) = x - \lambda \nabla f(x)+o(\lambda)$
这个的证明，我觉得是用到了变分学的知识:
$\delta(I+\lambda \nabla f)^{-1}|_{\lambda=0}=-\frac{\nabla f}{(I+\lambda \nabla f)^{-2}}|_{\lambda =0}= -\nabla f$
所以上面的是一阶距离的刻画.

我们先来看 $f$ 的一阶泰勒近似:

在这里插入图片描述
其近端算子为:

在这里插入图片描述
感觉，实际上是为:

相应的，还有二阶近似：

在这里插入图片描述

这个是Levenberg-Marquardt update的牛顿方法，虽然我不知道这玩意儿是什么.

上面的证明都是容易的，直接更具定义便能导出.

信赖域问题

proximal还可以用信赖域问题来解释:

在这里插入图片描述
而普通的proximal问题：

在这里插入图片描述
约束条件变成了惩罚项, 论文还指出，通过指定不同的参数和，俩个问题能互相达到对方的解.

Proximal Algorithms 3 Interpreta
Proximal Algorithms 这一节，作者总结了一些关于proximal的一些直观解释 Moreau-Y...
Proximal Algorithms 4 Algorithms
Proximal Algorithms 这一节介绍了一些利用proximal的算法. Proximal minim...
Proximal Algorithms 7 Examples a
本节介绍一些例子. LASSO 考虑如下问题:其中. proximal gradient method proxi...
Proximal Algorithms 5 Parallel a
Proximal Algorithms 这一节，介绍并行算法的实现. 问题的结构令. 给定, 让表示向量的一个子...
Proximal Algorithms 2 Properties
可分和如果可分为俩个变量:, 于是: 这个性质在并行算法的设计中非常有用。基本的运算如果, : 如果, : ...
Proximal Algorithms 6 Evaluating
Proximal Algorithms 需要注意的一点是，本节所介绍的例子可以通过第二节的性质进行延展. 一般方法...
Proximal Algorithms 1 介绍
Proximal Algorithms 定义令为闭的凸函数，即其上镜图:为非空闭的凸集，定义域：近端算子(是这...
讲解：Data Structures、Algorithms、ja
Project #3 (STREET MAPPING)Data Structures and Algorithms...
Introduction to Algorithms, 3rd
下载地址：Introduction to Algorithms, 3rd Edition[www.rejoiceb...
远端与近端
Proximal. This is a (reational) term that defines somethi...

Proximal Algorithms 3 Interpreta

Moreau-Yosida regularization

与次梯度的联系 $\mathbf{prox}_{\lambda f} = (I + \lambda \partial f)^{-1}$

改进的梯度路径

信赖域问题

相关文章

Proximal Algorithms 3 Interpreta

Proximal Algorithms 4 Algorithms

Proximal Algorithms 7 Examples a

Proximal Algorithms 5 Parallel a

Proximal Algorithms 2 Properties

Proximal Algorithms 6 Evaluating

Proximal Algorithms 1 介绍

讲解：Data Structures、Algorithms、ja

Introduction to Algorithms, 3rd

远端与近端

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读