Majorization Minimization

直到我作业完全做不出来，我才意识到那天翘的不到两小时的一门课有多难。

先把作业的题目放下，于是我可以试着从零开始重新学一下这东西。老师还说这些东西很简单的，因为都是向量的形式，那些东西到矩阵了之后才会有意思，但是觉得我们太菜了所以不讲矩阵。可是向量我也不会啊。

不过前几天强化学习课上讲TRPO/PPO的时候感觉好像就用到了这东西，得学的，得好好学的。

Majorization Minimization

一种算法

简单来说，如果我要最小化函数 $f(x)$，现在迭代在 $x_k$ 的位置，那么我可以找一个函数 $g_k(x)$

$g_k(x)$ 满足，$f(x)\le g_k(x).\forall x \in C$ , $f(x_k)=g_k(x_k)$。

那么使得 $x{k+1}=\arg \min {x \in C} gk(x)$，得到的 $f(x{k+1}) \le f(x_k)$，当然为了收敛还需要更多的性质。

---

从某种意义上，TRPO的算法就是满足这个性质的，通过增加了一个 $C\mathrm{KL}(\pi,\pi_{ref})$ ，熟悉TRPO的同学应该能感受到，不熟悉的等我先挖个坑。

majorant function

为了求出这样的 $g_k$，有这么几种替代函数可能会被提到。

Lipschitz Gradient Surrogate

• globally majorant

建立在 descent lemma 上的一个 surrogate

descent lemma: 如果实值函数 $f(x)$ 是 $L$-smooth function, 也即 $||\nabla f(x)-\nabla f(y)|| \le L||x-y||$，那么我们有：

$$f(x) \le f(x_k)+\left<\nabla f(x_k),x-x_k\right>+\frac{L}{2}||x-x_k||^2 \triangleq g_k(x)$$

如果直接考虑 $g_k$ 的最小值，求导得到 $\nabla f(x_k)+L(x-x_k) =0 \implies x=x_k-\frac{1}{L}\nabla f(x_k)$。与梯度下降类似。如果限制定义域的话，其实是projected gradient descent，也就是

$$x=\mathcal{P_{C}}\left(x_k-\frac{1}{L}\nabla f(x_k)\right)$$

• locally majorant

有时候也没这么强的限制，还是定义一个函数，但是看局部

$$\tilde g_k(x)= f(x_k)+\left<\nabla f(x_k),x-x_k\right>+\frac{1}{2\alpha}||x-x_k||^2$$

这里考虑 $\alpha$ 的取值，我要让 $f(x{k+1})=f(x_k-\alpha \nabla f(x_k))<\tilde g_k(x{k+1})$，使用backtracking的方法，不满足就让 $\alpha \leftarrow \mu \alpha .(\mu \in (0,1))$. 容易发现如果 $\alpha$ 足够小还是容易满足的。

Quadratic Surrogate

注意到我不一定一定要满足上面的样子，就是后面那个不一定是 $||x-x_k||^2$，我可以是一些别的比如一个正定的矩阵

如果 $\mathrm H_k\succ \nabla^2 f$, 我应该有

$$g_k(x)=f(x_k)+\left<\nabla f(x_k),x-x_k\right>+\frac{1}{2}(x-x_k)^T\mathrm H_k(x-x_k)$$

那么还是求导求最优解，迭代的公式就变成了（如果定义域 $R^n$）。

$$x_{k+1}=x_k-\mathrm{H}_k^{-1}\nabla f$$

显然当 $H_k$ 取hessen矩阵的时候这就是牛顿法。

如果不能直接有上面的假设，也就是假设弱一点，但是如果有 $\mathrm {\tilde{H}}_k\succ 0$，那么就应该存在一个 $\alpha _k >0$ 满足 $\alpha_k^{-1} \mathrm{\tilde H}_k \succ \nabla ^2 f(x_k)$，就能满足上面的式子。

这时候迭代的公式就变成了（$\mathcal C=\mathbb R^2$）

$$x_{k+1}=x_k-\alpha_k\mathrm{\tilde H}_k^{-1}\nabla f$$

你可以看到这就是 Quasi-Newton method. 代表方法有 DFP，BFGS.

当然我个人是觉得这里可以换成一个Bregman divergence，有机会推一推看看是不是就是mirror descent。

Jensen Surrogate

对于广义线性函数，我还是要最小化 $f(x)$，具体表现为

$$f(x)\triangleq \tilde f(\theta^Tx)$$

这里的 $\tilde f$ 是 convex 的。

那么这时候我的函数选择是

$$g_k(x)=\sum_{i=1}^n w_i \tilde f(\frac{\theta_i}{w_i}(x_i-x_{k,i})+\theta^T x_k)$$

where $w \in \mathbb R_{+}^n, ||w||_1=1,w_i\not =0 \text{ whenever }\theta_i\not=0$

证明不难，就是利用凸的性质，把 $w_i$ 分配进去

$$g_k(x)\ge \tilde f(\sum_{i=1}^n \theta_i(x_i-x_{k,i})+\theta^T x_k)= \tilde f(\theta^Tx)$$

有一个著名的算法 EM Algorithm, Expectation Maximization Algorithm

convex-concave

• 一类问题是 $\min_{x\in\mathcal C} f(x)+h(x)$，其中 $f(x)$ convex 而 $h(x)$ concave.

• 我可以定义

• $$g_k(x)=f(x)+\left<\partial h(x_k),x-x_k\right>+h(x_k)$$

• 其中 $\partial h$ 是 super-gradient of h，可以理解成把 h 看成一个切面。

有了上面简单的介绍，下面的方法会好理解很多，我们看一下简单的性质，然后再介绍几种常见的surrogate。

Optimization with first-order surrogate functions^[1]^

一种scheme叫MISO: minimizing strongly convex objective functions

一个 first-order surrogate 有两个性质

• 一个是Majorization，对应前文提到的，要么是全局都有 $g \ge f$，要么对于$\arg \min_\theta g(\theta)$ 里的元素存在 $g(\theta) \ge f(\theta)$。
• 另一个叫 Smoothness，要求 $h \triangleq g-f$ 是可微的且梯度是 L-Lipschitz 连续。

满足性质的surrogate构成一个集合，其中一部分是强凸的surrogate。之所以要强凸是为了后续有机会收敛性保证。注意到假设某个点位于 $\kappa$ ，那么 $h(\kappa)=0,\nabla h(\kappa)=0$。

性质就是说

$$|h(\theta)| \le \frac{L}{2}||\theta-\kappa||_2^2$$

同样的如果我们取 $\theta’$ 表示 $\arg \min_{\theta \in \Theta} g(\theta)$，我们有

$$f(\theta') \le g(\theta') \le g(\theta)=f(\theta)+\frac{L}{2}||\theta-\kappa||_2^2$$

如果 $g$ 是 $\rho$ 强凸的，那么有

$$f(\theta')+\frac{\rho}{2}||\theta'-\theta||_2^2\le f(\theta)+\frac{L}{2}||\theta-\kappa||_2^2$$

我每次取找一个新的 $\theta$ 取迭代，得到的一系列点 $(\thetan){n \ge 0}$，可以发现 $f(\theta_n)$ 单调递减，以及 $\theta_n$ satisfies asymptotic stationary point condition.

直接迭代的复杂度结论

抱歉没看懂证明，所以只放结论。

如果 $f$ 是一个凸函数，对于 $||\theta-\theta^*||_2 \le R$ 有 $f(\theta) \le f(\theta_0)$ ，我们有，任何一个 $L$-smooth的函数，根据迭代产生的点列，满足

$$f(\theta_n) - f^* \le \frac{2LR^2}{n+2}$$

如果 $f$ 是 $\mu$-强凸，不需要上述条件直接有

$$f(\theta_n)-f^* \le \beta^n(f(\theta_0)-f^*)$$ $$\beta\triangleq \cases{\frac{L}{\mu}&$\mu>2L$\\1-\frac{\mu}{4L}}$$

如果选择的surrogate是强凸的话

$$f(\theta_n) - f^* \le \frac{L||\theta_0-\theta^*||_2^2}{2n}$$

如果这时候 $f$ 是 $\mu$-强凸的话，则同时有 $f$ 收敛和 $\theta_n$ 收敛

$$||\theta_n-\theta^*||_2^2 \le (\frac{L}{\rho+\mu})^n||\theta_0-\theta^*||_2^2\\ ||f(\theta_n)-f^*||_2^2 \le (\frac{L}{\rho+\mu})^{n-1}\frac{L||\theta_0-\theta^*||_2^2}{2}$$

更进一步，如果海森矩阵 $\nabla^2 hn=\nabla^2(g_n-f)$ 是 M-Lipschitz，并且 $\nabla h_n(\theta{n-1})=0$ 的话

$$f(\theta_n)-f^* \le \frac{9MR^3}{2(n+3)^2}$$

如果此时 f 还是 $\mu$-strongly convex，收敛速度是superlinear的3/2.

Proximal Gradient Surrogates

这其实也就是一种surrogate，但是怀疑会有点难。

假设 $f=f_1+f_2$，那么 $g(\theta)=f_1(\kappa)+\nabla f_1(\kappa)^T(\theta-\kappa)+\frac{L}{2}||\theta-\kappa||_2^2+f_2(\theta)$

收敛性分析同 $h=g-f$。

Variational surrogate

如果这时候最小化的函数 $f(x)$ ，可以这样有 $f(x)=\min_{y \in \mathcal Y} h(x,y)$

那么定义

$$g_k(x)=h(x,y_{k}^*), \text{where } y_k^*=\arg \min_{y \in \mathcal Y} h(x_k,y)$$

Saddle Point surrogate

如果 $\theta2 \rightarrow f(\theta_1,\theta_2)$ 是concave的，$\theta_1 \rightarrow f(\theta_1,\theta_2)$ 是convex的，并且 $\tilde f(\theta_1)=\max{\theta_2} f(\theta_1,\theta_2)$，如果 $f(*,\theta_2)$ 是 $L’$-Lipschitz.

那么定义 $g(\theta_1)=f(\theta_1,\kappa_2^*)+\frac{L’’}{2}||\theta_1-\kappa_1||_2^2$, $L’’=\max(2L^2/\mu,L’)$

Algorithms

这部分介绍一些算法以及surrogate的应用

直接迭代

• 上述已介绍

Block Coordinate Descent Scheme:

对于高维向量的优化，一种方法是对于每个维度都建立一个单独的surrogate，然后把他们加起来

$$g_n(\theta)=\sum_{i=1}^k g_n^i(\theta^i)$$

然后每次随机对一个维度求argmin，从而更新。

Incremental Scheme:

对于有增量形式

$$f(\theta)=\frac{1}{T}\sum_{t=1}^T f^t(\theta)$$

常见的光滑的常用 stochastic gradient descent，非光滑 stochastic mirror descent，但是也可以用surrogate的方法，具体而言是每次都pick一个index，然后设置第 n 个 surrogate，第 n 个surrogate $gn$ 和 $g{n-1}$ 只在index的位置不一样。求argmin的时候还是需要把gn的平均策略记录下来。

EM Algorithm

和K-means一样知名，号称机器学习十大算法

考虑最大似然的原理

$$\begin{align*} \max_{\theta} \log \int_z p(x,z\mid \theta) \mathrm dz&=\max_{\theta} \log \int_z q(z)\frac{p(x,z\mid \theta)}{q(z)} \mathrm dz\\ &=\max_{\theta} \log \mathrm E _{z \sim q} \frac{p(x,z\mid \theta)}{q(z)} \mathrm dz\\ &\ge \max_{\theta} \mathrm E _{z \sim q} \log \frac{p(x,z\mid \theta)}{q(z)} \mathrm dz\\ &=\max [\int q(z)\log p(x,z\mid \theta) \mathrm dz - \int q(z) \log q(z) \mathrm dz] \end{align*}$$

所以分成两步，一个是E，一个是M

E步骤是选择最大的 $q(z)$，直观上理解负的最小化reverse KL（就是一个Jensen Surrogate的形式），相等是最小的 $q$，在这里选择

$$q(z)=\frac{p(x,z\mid \theta)}{\int p(x,z\mid \theta)\mathrm dz}=p(z\mid x,\theta) \propto p(x,z\mid \theta)$$

M步骤是求出最大的 $\theta$

EM算法就是迭代上面两个步骤直到收敛。

Trust Region Policy Optimization(Proximal minimization的特例)

在TRPO中，真正要优化的是 $J(\theta’)$

$$J(\theta')=E_{\tau \sim p_\theta'(\tau)}\left[\sum_t r(s_t,a_t)\right]$$

上一步所在位置为 $\theta$，下一步的位置是 $\theta’$

• 当在策略空间中两个策略差距不超过 $\epsilon$ 时，定义 $c=\frac{4\epsilon \gamma}{(1-\gamma)^2}$

$$L_{\theta}(\theta')= J(\theta)+\sum_t \mathbb{E}_{s_t \sim p_\theta(s_t)}\left[\mathbb{E}_{a_t\sim \pi_\theta(a_t\mid s_t)}\left[\frac{\pi_{\theta'}(a_t\mid s_t)}{\pi_\theta(a_t\mid s_t)}\gamma^t A^{\pi_\theta}(s_t,a_t)\right]\right]$$

有

$$J(\theta') \ge L_\theta(\theta') - C\cdot D_{KL}^{max}(\theta,\theta')$$

注意到我们是要最大化reward，所以 $g\theta=L\theta(.) - C\cdot D_{KL}^{max}(\theta,. )$ 是一个surrogate。

我怀疑策略空间和函数空间的映射是非常优美的。

关于这个surrogate为什么满足这个不等式，可以参考各大教科书（？

DCProgramming and Concave-Convex Procedure

Majorization-Minimization Algorithms in Signal Processing, Communications, and Machine Learning^[3]^

我每次迭代可以不用找最优的，也就是理论上可以用广义梯度法，可以用quasi-Newton method

$$\min _x &f_0(x)-h_0(x)\\$$

subject to $f_i(x)-h_i(x) \le 0,i=1,…,m.$

大概是

$$g_i(x \mid x_t)=f_i(x) - (h_i(x_t)+\nabla h_i(x_t)^T(x-x_t))$$

然后 最小化 $g_0$，subject to $g_i\le 0$，容易发现 $g$ 是一个上界。

Proximal Minimization

$$\min_{x,y} g(x,y)=f(x)+\frac{1}{2c}||y-x||_2^2$$ $$\begin{align*} x_{t+1}&=\mathrm{prox}_{A(x_t),f} (x_t)\\ &:=\arg \min_{x\in X} f(x)+\frac{1}{2}||x-x_t||^2_{A(x_t)}\\ &||x||_{A(x_t)}^2:=x^TA(x_t)x \end{align*}$$

Variable Metric Splitting Method for Non-Smooth Optimization

$$\min f(x)+h(x)$$

$f$ 是可微的，$h$ 是convex的，如果有一个系列的 $A_t$ 为正定矩阵

$$g^f(x \mid x_t)=f(x_t)+\nabla f(x_t)^T(x-x_t)+\frac{1}{2}||x-x_t||_{A_t}^2 \ge f(x)$$

由此再去优化 $g(x \mid x_t)=g^f(x\mid x_t)+h(x)$

注意到这里的 $A_t$ 的选择，如果 $f$ 是 L-smooth的，可以设置 $\mathrm{A}_t=L\mathrm{I}$

MM algorithm - Wikipedia

[1] Julien Mairal, Optimization with first-order surrogate functions. ICML, 2013.

[2] Lu et al., Nonconvex Nonsmooth Low Rank Minimization via Iteratively Reweighted Nuclear Norm, IEEE Trans. Image Processing, 2016.

• $$\min_\mathbf{X} \sum_{i=1}^{\min(m,n)}h(\sigma_i(\mathbf X))+f(\mathbf X)$$ $$h(\sigma_i) \le h(\sigma_i^k) +w_i^k(\sigma_i-\sigma_i^k)$$

[3] Ying Sun, Prabhu Babu, and Daniel P. Palomar, Majorization-Minimization Algorithms in Signal Processing, Communications, and Machine Learning, IEEE T. Signal Processing, Vol. 65, No. 3, 2017

[4] Chen Xu, Zhouchen Lin , and Hongbin Zha, Relaxed Majorization-Minimization for Non-smooth and Non-convex Optimization, AAAI 2016