coordinate descent是什么意思？

坐标轴下降法顾名思义，是沿着坐标轴的方向去下降，这和梯度下降不同。梯度下降是沿着梯度的负方向下降。不过梯度下降和坐标轴下降的共性就都是迭代法，通过启发式的方式一步步迭代求解函数的最小值。

　　　　坐标轴下降法的数学依据主要是这个结论（此处不做证明）：一个可微的凸目标函数$J(\theta)$, 其中$\theta$是$nx\times 1$的向量，即有$n$个维度。如果在某一点$\bar \theta$，使得$J(\theta)$在每一个坐标轴$\bar \theta_i$，($i = 1,2,\cdots,n$)上都是最小值，那么$J(\bar \theta_i)$就是一个全局的最小值。

　　　　于是我们的优化目标就是在$\theta$的$n$个坐标轴上(或者说向量的方向上)对损失函数做迭代的下降，当所有的坐标轴上的$\theta_i$($i = 1,2,\cdots,n$)都达到收敛时，我们的损失函数最小，此时的$\theta$即为我们要求的结果。

　　　　下面我们看看具体的算法过程：

　　　　1. 首先，我们把$\theta$向量随机取一个初值。记为$\theta^{(0)}$ ，上面的括号里面的数字代表我们迭代的轮数，当前初始轮数为0.

　　　　2. 对于第$k$轮的迭代。我们从$\theta^{(k)}_1$开始，到$\theta^{(k)}_n$为止，依次求$\theta^{(k)}_i$。$\theta^{(k)}_i$的表达式如下：

　　　　$$\theta^{(k)}_i = \text{argmin}_{\theta_i} J(\theta^{(k)}_1,\theta^{(k)}_2,\cdots,\theta^{(k)}_{i−1},\theta_i,\theta^{(k−1)}_{i+1},\cdots,\theta^{(k−1)}_n)$$

也就是说$\theta^{(k)}_i$是使$J(\theta^{(k)}_1,\theta^{(k)}_2,\cdots,\theta^{(k)}_{i−1},\theta_i,\theta^{(k−1)}_{i+1},\cdots,\theta^{(k−1)}_n)$最小化时候的$\theta_i$的值。此时$J(\theta)$只有$\theta^{(k)}_i$是变量，其余均为常量，因此最小值容易通过求导求得。

如果上面这个式子不好理解，我们具体一点，在第$k$轮，$\theta$向量的$n$个维度的迭代式如下：

　　　　$$\theta^{(k)}_1=\text{argmin}_{\theta_1} J(\theta_1,\theta^{(k−1)}_2,...,\theta^{(k−1)}n)$$

　　　　$$\theta^{(k)}_2=\text{argmin}_{\theta_2} J(\theta^{(k)}_1,\theta_2,\theta^{(k−1)}_3...,\theta^{(k−1)}_n)$$

　　　　$$\cdots$$

　　　　$$\theta^{(k)}_n=\text{argmin}_{\theta_n} J(\theta^{(k)}_1,\theta^{(k)}_2,...,\theta^{(k)}_{n−1},\theta_n)$$

　　　　3. 检查$\theta^{(k)}$向量和$\theta^{(k−1)}$向量在各个维度上的变化情况，如果在所有维度上变化都足够小，那么$\theta^{(k)}$即为最终结果，否则转入2，继续第$k+1$轮的迭代。

以上就是坐标轴下降法的求极值过程，可以和梯度下降做一个比较：

a) 坐标轴下降法在每次迭代中在当前点处沿一个坐标方向进行一维搜索 ，固定其他的坐标方向，找到一个函数的局部极小值。而梯度下降总是沿着梯度的负方向求函数的局部最小值。

b) 坐标轴下降优化方法是一种非梯度优化算法。在整个过程中依次循环使用不同的坐标方向进行迭代，一个周期的一维搜索迭代过程相当于一个梯度下降的迭代。

c) 梯度下降是利用目标函数的导数来确定搜索方向的，该梯度方向可能不与任何坐标轴平行。而坐标轴下降法法是利用当前坐标方向进行搜索，不需要求目标函数的导数，只按照某一坐标方向进行搜索最小值。

d) 两者都是迭代方法，且每一轮迭代，都需要$O(mn)$的计算量($m$为样本数，$n$为系数向量的维度)

转自这里

另外两位说得很清楚了，我就插个图。简单地说就是按照坐标轴方向下降的。

Gradient descent是Coordinate descent的特殊情况。每一个待求变量都是个坐标。n个变量就形成在n维空间找最优解的问题。CD每一步只计算一个或一部分待求变量上的gradient，其余变量保持不变。如果每步都改变全部变量，就是GD。

CD最大的优点是第k步计算都用了之前最新的值，而GD相当于每n步才更新一次数据。

至于CD和GD有同一最优解，是靠把问题“设计”成凸优化来实现的。