General Descent Methods

Definition

Formally, the descent direction is defined as follows.

$$\boxed{{\displaystyle \begin{array}{rl}& \mathbf{\text{Definition 4 (Descent Direction)}}\\ \\ & \text{boldsymbol}d\mathrm{is}\mathrm{a}\mathrm{descent}\mathrm{direction}\mathrm{for}f\mathrm{at}x\mathrm{if}f(\text{boldsymbol}x+t\text{boldsymbol}d)<f(\text{boldsymbol}x)\text{ for all }t>0\text{ sufficiently small.}\end{array}}}$$

Also , the following proposition is easy to obtain:

$$\boxed{{\displaystyle \begin{array}{rl}& \mathbf{\text{Propsition 5 (Descent Direction)}}\\ \\ & \text{if }f\text{ is continuously differentiable in a neighborhood of }x\text{,then any }d\text{ such that}\\ & \text{boldsymbol}{d}^{\mathrm{\top }}\mathrm{\nabla }f(\text{boldsymbol}x)<0\text{ is a descent direction.}\end{array}}}$$

Steepest Descent Direction

给定一个范数 $\Vert \cdot \Vert$，我们就可以定义这个范数意义下的 steepest descent direction。

$$ \boxed{ \begin{aligned} &\textbf{Definition 5 (Steepest Descent Direction)} \newline &\newline &\Delta_{|\cdot|}\boldsymbol{x}\triangleq\underset{\boldsymbol{v}:|\boldsymbol{v}|\leq1}{\operatorname{argmin}}\langle\boldsymbol{v},\nabla f(\boldsymbol{x})\rangle \end{aligned} } $$ Note*:

1. 其实，我们是希望让 ${\mathrm{\Delta }}_{\Vert \cdot \Vert }\text{boldsymbol}x\triangleq \underset{\text{boldsymbol}v:\Vert \text{boldsymbol}v\Vert \le 1}{\mathrm{argmin}}f(\text{boldsymbol}x+\text{boldsymbol}v)$ 的。但是由于直接最小化是不现实的，因此我们只能采用近似策略：$f(\text{boldsymbol}x+\text{boldsymbol}v)\approx f(\text{boldsymbol}x)+⟨\text{boldsymbol}v,\mathrm{\Delta }f(\text{boldsymbol}x)⟩,\text{where }f(\text{boldsymbol}x)\text{ is constant}$
2. 显然，如果使用 2-范数的话，那么这个 domain 就是 high-dimensional sphere，等价于梯度下降

Examples: Different Norms

$$\begin{array}{rl}& {\mathrm{\Delta }}_{\Vert \cdot {\Vert }_2}\text{boldsymbol}x=-\mathrm{\nabla }f(\text{boldsymbol}x),\\ & {\mathrm{\Delta }}_{\Vert \cdot {\Vert }_1}\text{boldsymbol}x=-\mathrm{sign}\left(\frac{\partial f(\text{boldsymbol}x)}{\partial \text{boldsymbol}{x}_l}\right)\text{boldsymbol}{e}_l,l=\underset{i\in 1,\dots ,n}{\mathrm{argmax}}\left|\frac{\partial f(\text{boldsymbol}x)}{\partial \text{boldsymbol}{x}_i}\right|,\\ & {\mathrm{\Delta }}_{\Vert \cdot {\Vert }_A}\text{boldsymbol}x=-\Vert \mathrm{\nabla }f(\text{boldsymbol}x){\Vert }_{A^{-1}}^{-1}{A}^{-1}\mathrm{\nabla }f(\text{boldsymbol}x)\end{array}$$

证明

因此，对于三种范数，descent direction $\text{boldsymbol}d$ 就是：

$$\begin{array}{rl}& d_{gd}=-\frac{1}{\Vert \mathrm{\nabla }f(\text{boldsymbol}x)\Vert }\mathrm{\nabla }f(\text{boldsymbol}x),\\ & d_{cd}=-\mathrm{sign}\left(\frac{\partial f(\text{boldsymbol}x)}{\partial \text{boldsymbol}{x}_l}\right)\text{boldsymbol}{e}_l,l=\underset{i\in 1,\dots ,n}{\mathrm{argmax}}\left|\frac{\partial f(\text{boldsymbol}x)}{\partial \text{boldsymbol}{x}_i}\right|,\\ & d_A=-\Vert \mathrm{\nabla }f(\text{boldsymbol}x){\Vert }_{A^{-1}}^{-1}{A}^{-1}\mathrm{\nabla }f(\text{boldsymbol}x)\end{array}$$

Example: TRPO

TRPO 是强化学习的一个最优化方式。

Let ${\pi }_{\theta }$ denote a policy with parameters $\theta$. The theoretical TRPO update is:

$$\begin{array}{rl}{\theta }_{k+1}=\arg \underset{\theta }{max}& \mathcal{L}({\theta }_k,\theta )\\ \text{ s.t. }& {\overline{D}}_{KL}(\theta \Vert {\theta }_k)\le \delta \end{array}$$

where $\mathcal{L}({\theta }_k,\theta )$ is the surrogate advantage, a measure of how policy ${\pi }_{\theta }$ performs relative to the old policy ${\pi }_{{\theta }_k}$ using data from the old policy:

$$\mathcal{L}({\theta }_k,\theta )=\underset{\tau \sim {\pi }_{{\theta }_k}}{\mathrm{E}}[\sum _{t=0}^T{\gamma }^t{A}^{{\pi }_{{\theta }_k}}(s_t,a_t)]$$

and ${\overline{D}}_{KL}(\theta \Vert {\theta }_k)$ is an average KL-divergence between policies across states visited by the old policy:

$${\overline{D}}_{KL}(\theta \Vert {\theta }_k)=\underset{s\sim {\pi }_{{\theta }_k}}{\mathrm{E}}\left[D_{KL}({\pi }_{\theta }(\cdot |s)\Vert {\pi }_{{\theta }_k}(\cdot |s))\right]$$

The theoretical TRPO update isn't the easiest to work with, so TRPO makes some approximations to get an answer quickly. We Taylor expand the objective and constraint to leading order around ${\theta }_k$ :

$$\begin{array}{rl}\mathcal{L}({\theta }_k,\theta )& \approx g^T(\theta -{\theta }_k)\\ {\overline{D}}_{KL}(\theta \Vert {\theta }_k)& \approx \frac{1}{2}{(\theta -{\theta }_k)}^{T}H(\theta -{\theta }_k)\end{array}$$

• $g={\mathrm{\nabla }}_{{\theta }_k}\mathcal{L}({\theta }_k,\theta )$
• By the property of KL-divergence, $D_{KL}({\pi }_{{\theta }_k}\Vert {\pi }_{\theta }){|}_{{\theta }_k=\theta }=0,{\mathrm{\nabla }}_{{\theta }_k}{D}_{KL}({\pi }_{{\theta }_k}\Vert {\pi }_{\theta }){|}_{{\theta }_k=\theta }=\overrightarrow{0}$, thus the second order Taylor expansion of $D_{KL}$ only consists of the Hessian matrix

resulting in an approximate optimization problem,

$$\begin{array}{rl}{\theta }_{k+1}=\arg \underset{\theta }{max}& g^T(\theta -{\theta }_k)\\ \text{ s.t. }& \frac{1}{2}{(\theta -{\theta }_k)}^{T}H(\theta -{\theta }_k)\le \delta \end{array}$$

Randomized Schemes

Coordinate Descent

For coordinate descent method, the direction of $f$ at $\text{boldsymbol}x$ can be randomly chosen, and is given by $$ d_{c d-\text { rand }} \triangleq-[\nabla f(\boldsymbol{x})]{i_k} \boldsymbol{e}{i_k}, $$ where $i_k$ chosen uniformly at random from $\{1,2,\dots ,n\}$ at each $k$.

Note: 由于 $⟨-[\mathrm{\nabla }f(\text{boldsymbol}x){]}_{i_k}\text{boldsymbol}{e}_{i_k},\mathrm{\nabla }f(\text{boldsymbol}x)⟩=-\mathrm{\nabla }f(\text{boldsymbol}x{)}_{i_k}^2\le 0$，因此满足条件

Stochastic Gradient

For stochastic gradient method, the direction of $f$ at $\text{boldsymbol}x$ is given by $$ d_{s g c} \triangleq-g\left(\boldsymbol{x}_k, \xi_k\right), $$ where ${\xi }_k$ is a random variable, such that ${\mathbb{E}}_{{\xi }_k}g(\text{boldsymbol}{x}_k,{\xi }_k)=\mathrm{\nabla }f\left(\text{boldsymbol}{x}_k\right)$. That is, $g(\text{boldsymbol}{x}_k,{\xi }_k)$ is an unbiased ( but often very noisy ) estimate of the true gradient $\mathrm{\nabla }f\left(\text{boldsymbol}{x}_k\right)$.

Note: 最常见的，就是 batch gradient descent。均匀（不重复）抽样一组 batch，然后进行 descent。