随机化块坐标梯度下降（Randomized Block Coordinate Gradient Descent）在凸优化问题求解中的应用
我将讲解 随机化块坐标梯度下降（Randomized Block Coordinate Gradient Descent, RBCGD） 这一算法。它在求解大规模凸优化问题时，通过随机选择变量的子集（块）进行更新，显著降低了单次迭代的计算成本。
1. 问题描述
考虑以下形式的无约束凸优化问题：
\[\min_{x \in \mathbb{R}^n} f(x) \]
其中，目标函数 \(f: \mathbb{R}^n \to \mathbb{R}\) 是凸可微的。当变量维度 \(n\) 非常大时，标准的梯度下降（GD）每次迭代需要计算全梯度 \(\nabla f(x)\)，计算代价可能过高。
核心思想：将变量 \(x\) 划分为 \(M\) 个“块”（blocks）。每次迭代中，随机选择一个或几个块，仅计算和更新这些块对应的部分梯度，而保持其他块不变。这能大大降低单次迭代的计算量，尤其适合 \(f\) 具有某种可分离或部分可分离的结构。
2. 算法准备与假设
为了确保算法的收敛性，我们通常需要一些假设条件：
- 块划分：将变量 \(x\) 分解为 \(M\) 个块：\(x = (x_1, x_2, \dots, x_M)\)，其中 \(x_i \in \mathbb{R}^{n_i}\)，且 \(\sum_{i=1}^M n_i = n\)。
- 块Lipschitz连续梯度：假设对于每个块 \(i\)，存在常数 \(L_i > 0\)，使得对于任意的 \(x \in \mathbb{R}^n\) 和任意的 \(d_i \in \mathbb{R}^{n_i}\)，有：
\[ \| \nabla_i f(x + U_i d_i) - \nabla_i f(x) \| \le L_i \| d_i \| \]
这里，$ \nabla_i f(x) $ 表示目标函数 $ f $ 关于块 $ x_i $ 的偏导数（梯度），$ U_i $ 是一个 $ n \times n_i $ 的矩阵，其作用是将 $ d_i $ “放置”到 $ x $ 的第 $ i $ 个块的位置上，其他位置为零。这意味着，当只改变第 $ i $ 块时，该块的梯度变化是受控的。
- 块采样规则：通常假设在每次迭代 \(k\) 中，我们以概率 \(p_i > 0\) 独立随机地选择一个块索引 \(i_k \in \{1, 2, \dots, M\}\) 进行更新。最简单的规则是均匀采样，即 \(p_i = 1/M\)。
3. 算法步骤详解
随机化块坐标梯度下降（RBCGD）的核心迭代格式如下：
步骤1：初始化
- 选择初始点 \(x^{(0)} \in \mathbb{R}^n\)。
- 设置最大迭代次数 \(K\) 或精度阈值 \(\epsilon\)。
- \(k \leftarrow 0\)。
步骤2：迭代循环（直到满足停止条件）
- 随机选择块：根据预定义的概率分布 \(\{p_i\}\)（例如均匀分布），随机选取一个块索引 \(i_k\)。
- 计算部分梯度：计算目标函数在当前迭代点 \(x^{(k)}\) 处关于被选中块 \(i_k\) 的梯度：\(g_{i_k} = \nabla_{i_k} f(x^{(k)})\)。
- 更新选中块：沿着该块梯度的负方向（可能带有步长）进行更新：
\[ x_{i_k}^{(k+1)} = x_{i_k}^{(k)} - \eta_k \cdot g_{i_k} \]
其中，$ \eta_k > 0 $ 是步长（学习率）。步长可以是一个固定值，也可以根据块 Lipschitz 常数 $ L_{i_k} $ 自适应选择。
**最优步长选择（理论保证）**：如果我们已知每个块的 Lipschitz 常数 $ L_i $，通常可以设置步长为 $ \eta_k = 1 / L_{i_k} $。这相当于在选中的块上执行一次精确的**块坐标下降**（对于二次函数，是最优步长）。
- 保持其他块不变：对于所有 \(j \neq i_k\)，令 \(x_j^{(k+1)} = x_j^{(k)}\)。
- 迭代计数：\(k \leftarrow k + 1\)。
步骤3：输出
- 输出最后一次迭代的结果 \(x^{(k)}\) 作为近似最优解。有时也会输出所有迭代的平均值或历史最优值。
4. 一个直观的例子与解释
假设目标函数是 \(f(x, y, z) = x^2 + 2y^2 + 3z^2 + xy + yz\)（这是一个简单的凸二次函数）。我们将三个变量 \(x, y, z\) 分别视为三个块（\(M=3\)）。
- 全梯度下降：每次迭代需要计算三个偏导数：\(\frac{\partial f}{\partial x} = 2x + y\)，\(\frac{\partial f}{\partial y} = 4y + x + z\)，\(\frac{\partial f}{\partial z} = 6z + y\)。然后同时更新 \(x, y, z\)。
- 随机块坐标梯度下降：
- 假设第 \(k\) 次迭代随机选中了块 \(y\)（即 \(i_k = 2\)）。
- 我们只计算关于 \(y\) 的偏导数：\(g_2 = \frac{\partial f}{\partial y} (x^{(k)}, y^{(k)}, z^{(k)}) = 4y^{(k)} + x^{(k)} + z^{(k)}\)。
- 然后只更新 \(y\)：\(y^{(k+1)} = y^{(k)} - \eta \cdot g_2\)，而 \(x^{(k+1)} = x^{(k)}\)，\(z^{(k+1)} = z^{(k)}\)。
- 下次迭代可能选到不同的块。平均来看，每次迭代只需要计算一个偏导数，计算量是全梯度下降的 \(1/3\)。
5. 收敛性分析（关键思想）
RBCGD的收敛性证明通常依赖于以下观察：
- 期望下降（Progress in Expectation）：由于每一步是随机选择块，我们关注每次迭代后目标函数值的期望下降。数学上可以证明，在凸且梯度满足Lipschitz连续的条件下，存在步长策略（如 \(\eta = 1/L_{\max}\) 或 \(\eta = 1/L_{i_k}\)），使得：
\[ \mathbb{E}[f(x^{(k+1)}) | x^{(k)}] \le f(x^{(k)}) - \frac{\eta}{2} \| \nabla f(x^{(k)}) \|^2_{\text{weighted}} \]
这里的期望是对随机选择的块 $ i_k $ 取的，加权范数与采样概率 $ p_i $ 和 Lipschitz 常数 $ L_i $ 有关。
- 收敛速率：对于凸且光滑的 \(f\)，RBCGD可以达到 \(O(1/k)\) 的次线性收敛速率（对于非强凸函数），或者线性收敛速率（对于强凸函数）。具体来说：
- 若 \(f\) 是 \(\mu\)-强凸的，且采用适当步长，则：
\[ \mathbb{E}[f(x^{(k)}) - f(x^*)] \le (1 - c)^k [f(x^{(0)}) - f(x^*)] \]
其中 $ c $ 是一个依赖于 $ \mu, L_i, p_i $ 的正常数（小于1）。$ x^* $ 是最优解。
收敛速率虽然可能比全梯度下降慢（体现在常数 $ c $ 上），但**单次迭代成本显著降低**，使得在达到相同精度时，总的计算时间（或浮点运算次数）往往更少。这是随机化/坐标类算法的核心优势。
6. 算法变体与扩展
- 随机块坐标下降（RBCD）：对于复合优化问题 \(\min_x f(x) + g(x)\)，其中 \(g(x)\) 可能是非光滑但可分离的（如L1正则项 \(\lambda \|x\|_1\)），可以将梯度下降步骤替换为近端梯度更新。当选中第 \(i\) 块时，更新为：
\[ x_i^{(k+1)} = \text{prox}_{\eta g_i}(x_i^{(k)} - \eta \nabla_i f(x^{(k)})) \]
其中 $ \text{prox} $ 是近端算子。这被称为**随机块坐标近端梯度下降**。
-
块采样策略：除了均匀采样，还可以采用与块Lipschitz常数 \(L_i\) 成比例的概率 \(p_i \propto L_i\)，这有时能带来更好的理论收敛常数。
-
多块/批量更新：每次迭代随机选择多个块（一个小批量）同时更新，可以减小方差，有时能加速收敛。
-
加速变体：借鉴Nesterov动量的思想，有随机块坐标梯度下降的加速版本（如APPROX、APCG算法），对于强凸问题可以达到更优的 \(O((1-\sqrt{\mu/L_{\text{avg}}})^k)\) 线性收敛速率。
总结
随机化块坐标梯度下降通过将高维优化问题分解为对低维块的随机、序列更新，巧妙地平衡了计算效率与收敛保证。其核心在于利用问题的结构（块可分性）和随机采样的期望下降性质。在处理大规模机器学习问题（如逻辑回归、线性回归、深度学习中的部分参数更新）时，它是一种非常有效的基础工具。理解其从随机块选择、部分梯度计算到收敛性分析的全过程，是掌握现代大规模优化算法的关键一步。