坐标下降法在稀疏学习中的循环与随机选择收敛性对比

坐标下降法是一种迭代优化算法，每次只更新目标函数中的一个坐标（变量），而固定其他坐标。在稀疏学习问题（例如Lasso回归）中，这种方法效率极高。坐标的选择策略直接影响收敛速度：最常用的是循环选择（按固定顺序轮流）和随机选择（均匀随机抽取）。下面我们通过具体步骤分析两者的收敛性差异。

1. 理解问题设定

目标函数：考虑一个典型的稀疏学习问题——Lasso回归。其目标函数为凸函数：
$$f(\mathbf{x}) = \frac{1}{2} \| A\mathbf{x} - \mathbf{b} \|_2^2 + \lambda \|\mathbf{x}\|_1$$
其中 $A \in \mathbb{R}^{m \times n}$，$\mathbf{x} \in \mathbb{R}^n$，$\mathbf{b} \in \mathbb{R}^m$，$\lambda > 0$ 是正则化系数。
坐标下降更新：在第 $k$ 次迭代中，若选择第 $i$ 个坐标，则更新公式为：
$$x_{i}^{(k+1)} = \text{prox}_{\lambda \|\cdot\|_1} \left( x_i^{(k)} - \frac{1}{L_{ii}} \nabla_i f(\mathbf{x}^{(k)}) \right)$$
其中 $L_{ii}$ 是第 $i$ 个坐标的Lipschitz常数（通常取矩阵 $A$ 第 $i$ 列的范数平方），$\nabla_i f$ 是 $f$ 对 $x_i$ 的偏导数，prox是软阈值算子。
选择策略差异：循环选择按固定顺序（如1→2→...→n→1）遍历坐标；随机选择每次独立均匀随机抽取一个坐标。

步骤：

初始化：设定初始点 $\mathbf{x}^{(0)}$，迭代次数 $T$，坐标维数 $n$。
循环更新：对 $k = 0, 1, \dots, T-1$，按顺序执行以下子步骤：
- 计算当前所有坐标的偏导数 $\nabla_i f(\mathbf{x}^{(k)})$。
- 更新坐标 $i = (k \mod n) + 1$ 的值为软阈值后的结果。
- 固定其他坐标不变。
输出：最终 $\mathbf{x}^{(T)}$。

收敛性特点：

线性收敛：当目标函数强凸时，循环选择能达到线性收敛率，但常数依赖于问题条件数。
最坏情况：若存在“坏”坐标方向，循环顺序可能使收敛变慢（例如某些坐标更新后抵消之前的进展）。理论上，循环选择的收敛率上界为 $O(n \cdot \kappa \cdot \log(1/\epsilon))$，其中 $\kappa$ 是条件数。
实际表现：通常比随机选择更稳定，但前期收敛可能较慢。

步骤：

初始化：设定初始点 $\mathbf{x}^{(0)}$，迭代次数 $T$，坐标维数 $n$。
随机更新：对 $k = 0, 1, \dots, T-1$：
- 随机抽取一个坐标 $i_k \in \{1,\dots,n\}$，服从均匀分布。
- 计算该坐标的偏导数 $\nabla_{i_k} f(\mathbf{x}^{(k)})$。
- 更新 $x_{i_k}$ 为软阈值后的值。
输出：最终 $\mathbf{x}^{(T)}$。

收敛性特点：

期望线性收敛：在强凸假设下，随机选择的期望收敛率也是线性的，且常数与 $n$ 无关。具体地，期望迭代次数为 $O(\kappa \cdot \log(1/\epsilon))$。
优势：避免了循环策略中可能出现的“坏顺序”问题；尤其在稀疏数据中，随机选择往往比循环更快。
方差问题：由于随机性，收敛路径波动较大，但期望表现优异。

理论结果：

循环选择的收敛率最坏情况下与 $n$ 成正比（需遍历所有坐标才能获得一次有效下降），而随机选择的期望收敛率与 $n$ 无关（因为每次更新都能期望降低目标函数值）。
证明思路（仅需理解关键）：
- 循环选择：每次更新后，目标函数下降量至少为 $\frac{1}{2L_{\max}} \| \nabla f(\mathbf{x}) \|_2^2$，但因一次只更新一个坐标，下一个更新可能被其他坐标的误差抵消，导致总下降需乘以 $n$。
- 随机选择：每次更新后的期望下降为 $\frac{1}{n} \cdot \frac{1}{2L_{\max}} \| \nabla f(\mathbf{x}) \|_2^2$（因为均匀随机），但迭代一次只做一次更新，因此期望下降量和 $n$ 无关（分母的 $n$ 被分子随机选中的概率抵消）。
具体数值：设 $L$ 为最大Lipschitz常数，则：
- 循环选择：$\mathcal{O}\left( n \kappa \log \frac{1}{\epsilon} \right)$（最坏情况）。
- 随机选择：$\mathbb{E} \left[ \text{迭代次数} \right] = \mathcal{O}\left( \kappa \log \frac{1}{\epsilon} \right)$（期望）。

实验观察：