随机坐标下降与坐标曲率

全梯度的Lipschitz常数理路Lipschitz 梯度Lipschitz gradient · Lipschitz continuous gradient梯度映射的变化量由点间距离乘统一常数控制的正则性条件。控制所有方向；$L_i$只控制第 $i$ 坐标单独移动时同一偏导的变化。对 $f(x)=x^{T}Qx/2-c^{T}x$、$Q⪰0$，可取 $L_i=Q_{ii}$；最小全局欧氏常数却是 ${\lambda }_{max}(Q)$。对有耦合的矩阵，它们不能互换。

由沿坐标线段积分理路微积分基本定理Fundamental theorem of calculus积分与求导在适当连续性条件下互为逆过程。，式(1)给

把右侧二次式最小化，就得到式(2)，且下降至少为 $[{\partial }_{i}f(x){]}^2/(2L_i)$。高曲率坐标单次步子小，但按 $L_i$ 更频繁地访问它，恰好让期望中的分母相消。这是对变量索引抽样；SGD理路随机梯度下降Stochastic gradient descent · SGD · 随机梯度法在已知历史下用无偏随机梯度更新，推导凸目标期望界与二次噪声底，并按真实梯度查询比较批量和停止保证。通常对样本或梯度oracle抽样，随机性的来源不同。

两种曲率与两种抽样 ​

取 $f(x)=(x_1^2+9x_2^2)/2$、$x_0=(1,1)$。$L_1=1,L_2=9,S=10,\mu =1$，初始目标为 $5$。抽到坐标1会把它精确置零，留下目标 $9/2$；抽到坐标2会留下目标 $1/2$。按 $p=(1/10,9/10)$ 抽样，一步期望目标为 $9/10$；均匀抽样的一步期望为 $5/2$。

由于某个坐标一旦访问就归零，$k$ 次访问后的精确期望是

式(3)的上界 $5(9/10{)}^k$ 比实际值保守。取 $k=2$，实际为 $0.45$，上界为 $4.05$。这既核对抽样，也说明最坏界不能代替实例计算。若初值改为 $(1,0)$，均匀抽样更快消掉唯一误差；按曲率抽样优化的是一类统一保证，不是每个初值的最佳策略。

单坐标安全，不代表同时更新安全 ​

令 $f(x)=(x_1+x_2+x_3{)}^2/2$。每个 $L_i=1$，但全局光滑常数为 $3$。从 $(1,1,1)$ 开始，单独更新一个坐标给 $(-2,1,1)$，目标降至零。若三个坐标都用旧点偏导 $3$、各自按步长1同时更新，结果为 $(-2,-2,-2)$，目标从 $9/2$ 升至 $18$。把三条安全的单坐标规则并行执行，会重复使用同一份未更新的耦合信息。

若把变量分成不相交块 $I_b$，应给块梯度的常数 $L_b$：$\Vert {\mathrm{\nabla }}_{b}f(x+U_{b}d)-{\mathrm{\nabla }}_{b}f(x)\Vert \le L_b\Vert d\Vert$。每轮只选一块，沿该块按 $1/L_b$ 更新，前述证明把标量平方换成块范数平方即可。二次问题的 $L_b={\lambda }_{max}(Q_{bb})$，通常不是该块对角元的最大值。多个块同时更新还需新的耦合上界，本页不为它提供串行率。

坐标曲率为零时不能使用除法。若该方向为常数，可固定不动；若为非零线性函数，在无约束空间上没有有限最小点，与本页假设冲突。也可以选严格正的保守上界，但必须明确它是否真正满足式(1)。

从单步下降到两个速率 ​

条件于 ${\mathcal{F}}_k$，$x_k$固定。按式(1)的下降求期望：

强凸性理路强凸性Strong convexity · Strongly convex function函数在一阶凸下界之外还保留统一二次增长量的曲率性质。给 $f(z)\ge f(x)+⟨\mathrm{\nabla }f(x),z-x⟩+\mu \Vert z-x{\Vert }^2/2$。将右侧对整个空间最小化，得到 $f^{\ast }\ge f(x)-\Vert \mathrm{\nabla }f(x){\Vert }^2/(2\mu )$。代入式(4)再取全期望，得到误差每轮至少收缩因子 $1-\mu /S$，归纳即式(3)。

没有强凸性时，若已知整个初始下水平集到某个最优点 $x^{\ast }$ 的距离至多 $0<R_0<\mathrm{\infty }$，逐次下降保证迭代留在其中。凸性给 $f(x_k)-f^{\ast }\le R_0\Vert \mathrm{\nabla }f(x_k)\Vert$。记 $a_k=\mathbb{E}[f(x_k)-f^{\ast }]$，用 $\mathbb{E}{Z}^2\ge (\mathbb{E}Z{)}^2$ 得

若某步 $a_k=0$，目标误差已经几乎必然为零；否则 $a_{k+1}\le a_k$，故 $1/a_{k+1}-1/a_k\ge 1/(2S{R}_0^2)$。求和得到 $a_k\le 2S{R}_0^2/k$。最小点存在并不自动保证所需下水平集有界，必须单独检查这个条件。

可分惩罚的接口与成本 ​

对 $F=f+\sum _i{h}_i(x_i)$，可把式(2)换成 $x_i^{+}={\mathrm{prox}}_{h_i/L_i}(x_i-{\partial }_{i}f(x)/L_i)$。它精确最小化这一坐标的二次上模型，因而保证 $F$不增；要建立随机复合率，需保留惩罚差和近端映射，不能把式(4)里的普通梯度范数直接照抄。Lasso坐标下降理路Lasso 坐标下降Lasso coordinate descent · Lasso cyclic coordinate minimization用部分残差和列范数逐坐标精确最小化 Lasso，并保持残差缓存与可行对偶证书一致。是平方损失加绝对值惩罚的具体执行方案，给出真实残差缓存和循环证明。

一次偏导未必便宜：若查询器先计算完整梯度，随机坐标节省的只是更新算术。平方损失维护残差后，访问第 $i$ 列需 $O(1+\mathrm{nnz}(A_i))$；初始化残差、曲率表、抽样表以及最终全量证书都另计。固定抽样分布可用 $O(n)$预处理建立累计概率表，每次二分抽样为 $O(\log n)$；这些费用也在预算内。报告 $k$ 次坐标访问不能直接与 $k$ 次全梯度比较。

两道短自测 ​

1. $f=(4x_1^2+x_2^2)/2$，从 $(1,1)$按曲率抽样，一步期望目标是多少？答案：概率为 $(4/5,1/5)$，两种剩余目标为 $1/2,2$，期望 $4/5$。
2. 对 $f=(x_1+x_2+x_3{)}^2/2$，把三坐标合为一个块时能否取块常数1？答案：不能；该块Hessian为全1矩阵，最大特征值3，常数至少3。对角元1只适用于单坐标移动。