组 Lasso 的块收缩与对偶证书

形式陈述

给定 $A\in\mathbb R^{m\times p}$ 、 $b\in\mathbb R^m$ ，其中 $m,p\ge1$ 。把全部坐标划分为有限个非空、两两不相交的组 $\mathcal G$ ；每组权重 $w_g>0$ ， $\lambda>0$ 。记 $x_g$ 为该组坐标， $A_g$ 为对应列。无截距、未除以样本数的组 Lasso 是

P(x)=\frac12\|b-Ax\|_2^2+\lambda J(x), \qquad J(x)=\sum_{g\in\mathcal G}w_g\|x_g\|_2. \tag{1}

它在最小二乘中对整组长度收费。 $J(x)\ge(\min_gw_g)\|x\|_2$ ，因此目标连续且强制增长，最小点存在。满列秩足以保证解唯一；组惩罚本身并不保证系数或活动组唯一。

令 $r=b-Ax$ 。由次微分最优性， $x$ 最优当且仅当每组满足

\begin{cases} A_g^{\mathsf T}r=\lambda w_g x_g/\|x_g\|_2,&x_g\ne0,\\ \|A_g^{\mathsf T}r\|_2\le\lambda w_g,&x_g=0. \end{cases} \tag{2}

非零组不仅要求相关性长度正确，还要求方向一致。零组允许的是一个闭球；逐坐标都小于 $\lambda w_g$ 并不足以落在这个球内。例如两个分量均为 $4\lambda w_g/5$ 时，组长度仍超过阈值。

本页同时给出两个可执行接口：对任意输入 $z$ ，精确计算组惩罚的近端映射；对任意候选 $x$ ，计算可行下界。令 $\tau>0$ ，则

\bigl(\operatorname{prox}_{\tau J}(z)\bigr)_g= \begin{cases} (1-\tau w_g/\|z_g\|_2)z_g,&\|z_g\|_2>\tau w_g,\\ 0,&\|z_g\|_2\le\tau w_g. \end{cases} \tag{3}

第二分支包括 $z_g=0$ ，不计算 $0/0$ 。若 $\theta\in\mathbb R^m$ 满足所有约束 $\|A_g^{\mathsf T}\theta\|_2\le\lambda w_g$ ，则

D(\theta)=b^{\mathsf T}\theta-\frac12\|\theta\|_2^2, \qquad 0\le P(x)-P^*\le P(x)-D(\theta). \tag{4}

这里 $P-D$ 认证给定训练问题的优化误差，不认证真实组支持。

直觉

标量软阈值减去每个坐标的绝对幅度；块收缩先量整组的欧氏长度，再保持组内方向缩短它。输入 $(3,4)$ 、阈值 $2$ 时，输出是 $(9/5,12/5)$ ，长度从 $5$ 减到 $3$ 。逐坐标软阈值会输出 $(1,2)$ ，既改变方向，也解了另一项惩罚。

组内正交换基不改变欧氏长度，因此块收缩与同组正交变换可交换。任意坐标缩放却会改变长度；权重、单位与分组是模型输入，不能在认证时再悄悄改变。常见的 $w_g=\sqrt{|g|}$ 是一种建模选择，不是块收缩公式的必需条件。

惩罚按组可分不意味着损失按组可分。组间相关的列会让一次梯度候选依赖全部系数。下面的三列例子在第一轮留下第二组，最终证书却要求它为零；近端一步与整个回归解是不同产物。

例子与边界

两组耦合设计的一轮与终点

取 $\mathcal G=\{\{1,2\},\{3\}\}$ 、权重均为一、 $\lambda=1$ ，并令

A=\begin{pmatrix}1&0&3/5\\0&1&0\\0&0&4/5\end{pmatrix}, \qquad b=(18/5,24/5,0)^{\mathsf T}. \tag{5}

$A^{\mathsf T}A$ 的特征值为 $2/5,1,8/5$ ，所以可取固定步长 $\alpha=5/8$ 。从 $x_0=0$ 开始，梯度候选和组阈值为

z_0=\alpha A^{\mathsf T}b=(9/4,3,27/20),\qquad \tau=\alpha\lambda=5/8.

第一组长度为 $15/4$ ，收缩因子为 $5/6$ ；第二组是单坐标，故

x_1=(15/8,5/2,29/40). \tag{6}

代回原数据，而不是复用旧点残差，得到

r_1=(129/100,23/10,-29/50),\qquad A^{\mathsf T}r_1=(129/100,23/10,31/100).

第一组相关性长度为 $\sqrt{69541}/100>1$ ，所以 $r_1$ 不是合法对偶点。令

\rho=\sqrt{69541}/100,\quad\theta_1=r_1/\rho.

此时两组相关性长度分别为 $1$ 和 $31/\sqrt{69541}$ ，均合法。完整账本是

P(x_1)=\frac{29981}{4000},\qquad D(\theta_1)=\frac{3921}{250\rho}-\frac{14581}{4000\rho^2}, \qquad G_1=P(x_1)-D(\theta_1). \tag{7}

这些分数分别来自 $\|r_1\|^2=14581/2000$ 、 $J(x_1)=77/20$ 和 $b^{\mathsf T}r_1=3921/250$ 。给出 $\rho$ 才能复算证书；只报一个目标值不能知道还差多少。

现在检查候选 $x^*=(3,4,0)$ 。其残差为 $r^*=(3/5,4/5,0)$ ，相关性为 $(3/5,4/5,9/25)$ 。第一组恰为 $x_g^*/5$ ，第二组长度为 $9/25<1$ 。因此满足 (2)，且

P(x^*)=\frac{11}{2}=D(r^*).

零间隙证明最优，满列秩再保证唯一。第一轮第二组非零没有推翻最终零组；它只是尚未最优的候选。第一组下一轮的两个分量受到不同耦合反馈，不能把整个轨道当作一个固定方向上的标量阈值例子。

改权重后的迁移

在独立去噪模型 $A=I_4$ 中，取两组输入 $(3,4)$ 与 $(0,3)$ ， $\lambda=1$ 、 $w_1=2,w_2=1$ 。一次块收缩给

x^*=((9/5,12/5),(0,2)),\quad r^*=((6/5,8/5),(0,1)).

残差组长度分别为 $2,1$ ，恰等于不同的组阈值。目标为 $P=\tfrac12(4+1)+2\cdot3+2=21/2$ 。对偶内积为 $10+3=13$ ，故 $D=13-5/2=21/2$ 。统一使用阈值一会解错第一个组；若目标整体改为除以四，惩罚参数与停止间隙也应同步除以四。

重叠组不能照抄独立块公式

令两组为 $\{1,2\}$ 与 $\{2,3\}$ ，输入 $z=(0,3,0)$ 、两权重及近端参数均为一。真实近端问题为

\min_x\ \frac12\|x-z\|^2+\sqrt{x_1^2+x_2^2}+\sqrt{x_2^2+x_3^2}.

固定 $x_2$ 时，令 $x_1=x_3=0$ 同时减少平方项和惩罚；剩下 $\min_t(t-3)^2/2+2|t|$ ，唯一解 $t=1$ 。若把两组各自对原输入独立收缩，它们都会建议共享坐标取二。这给出的 $(0,2,0)$ 不是答案。不相交划分是 (3) 的计算条件；一般重叠惩罚需要另外求解共享变量的一致性问题。

推论与应用

从零点的球到径向收缩

对 $f(u)=\|u\|_2$ ，非零点的梯度是 $u/\|u\|_2$ 。在零点， $s$ 是次梯度当且仅当 $\langle s,v\rangle\le\|v\|_2$ 对所有 $v$ 成立。Cauchy–Schwarz 证明 $\|s\|_2\le1$ 足够；取 $v=s$ 则证明必要。因此零点次微分正是闭单位球。

对于单块 $\min_u\|u-z\|^2/2+a\|u\|_2$ 、 $a>0$ ，零点最优恰当且仅当 $\|z\|_2\le a$ 。若解非零，最优性变为

z=u+a\frac{u}{\|u\|_2}.

右边与 $u$ 同向，故 $\|z\|_2=\|u\|_2+a$ ，恢复 $u=(1-a/\|z\|_2)z$ 。两分支覆盖全部输入，平方项的严格凸性保证唯一。不相交组使平方距离与惩罚都能分组相加，逐块使用该结果即得 (3)。对 (1) 加上损失的梯度 $-A^{\mathsf T}r$ ，便得到 (2)。

组对偶的消元与间隙恒等式

对任意向量 $s$ ，逐组 Cauchy–Schwarz 给

(\lambda J)^*(s)= \begin{cases} 0,&\|s_g\|_2\le\lambda w_g\text{ 对所有 }g,\\ +\infty,&\text{否则}. \end{cases}

球内每项 $\langle s_g,x_g\rangle-\lambda w_g\|x_g\|_2\le0$ ；若某组越界，沿 $s_g$ 的方向任意放大该组便趋于正无穷。这是共轭的直接计算，标量 Lasso 的盒子现在换成一组欧氏球。

引入 $r=b-Ax$ ，消去拉格朗日表达式中的 $r$ 得 $-\|\theta\|^2/2$ ，消去 $x$ 得约束 $\|A_g^{\mathsf T}\theta\|_2\le\lambda w_g$ 。因此得到 (4)，并且直接展开有

P(x)-D(\theta)=\frac12\|r-\theta\|_2^2+ \sum_g\bigl(\lambda w_g\|x_g\|_2- \langle x_g,A_g^{\mathsf T}\theta\rangle\bigr). \tag{8}

合法 $\theta$ 使右侧各项非负；KKT 成立时取 $\theta=r$ 得零。因此不仅有弱对偶界，还构造了最优点的等值证书。

对于任何候选，用

\rho=\max\left\{1,\max_g\frac{\|A_g^{\mathsf T}r\|_2}{\lambda w_g}\right\}, \qquad\theta=r/\rho \tag{9}

即可生成合法对偶点。若某组权重为零，(9) 的除法不适用；该未惩罚组需要等式 $A_g^{\mathsf T}\theta=0$ 。本页正权重假设避免了这个额外接口。

可停止算法与成本

初始化 $x_0=0$ ，选 $L\ge\|A\|_2^2$ 、 $L>0$ ，固定 $0<\alpha\le1/L$ 。每轮在当前点维护 $r=b-Ax$ ，先用 (9) 计算 $P,D,G$ ；若 $G\le\varepsilon$ ，返回该点和证书。否则计算 $z=x+\alpha A^{\mathsf T}r$ ，对每组施加参数 $\alpha\lambda w_g$ 的收缩，更新 $x$ 并重新计算或正确增量更新残差。预算用尽时返回当前 gap 与“未达标”，不以小位移冒充精度。

这满足近端梯度的全部条件：损失凸且梯度 $L$ -Lipschitz，组惩罚连续凸且最小点存在。其三点不等式给出目标不增、到最优点的距离不增，以及

P(x_k)-P^*\le\frac{\|x_0-x^*\|^2}{2\alpha k}.

该先验界并未给未知 $x^*$ 的可计算距离；实际停止仍用 gap。每轮完整矩阵乘法与转置乘法在稠密情形为 $O(mp)$ ，块范数和缩放共 $O(p)$ ；稀疏存储为 $O(s+m+p)$ ， $s$ 为实际保存的矩阵条目数。认证新点需其自己的 $r,A^{\mathsf T}r$ ，可与下一轮共享，不能免费省掉全组检查。 $k$ 轮总费用按上述每轮成本相乘，内存另需存储矩阵及 $O(m+p)$ 工作向量。

另取 $\lambda=w_1=w_2=1$ 。若设计包含两个相同的组矩阵 $A=(I_2\ I_2)$ ，且 $b=2u$ 、 $\|u\|_2=1$ ，则 $(tu,(1-t)u)$ 对全部 $0\le t\le1$ 都最优，残差都是 $u$ ，目标都是 $3/2$ 。活动组可以不同而 gap 同为零。故训练证书、优化解唯一性和生成模型的真实组识别，必须分别提出条件。

两道短自测

一个零组的相关性为 $(3/5,4/5)$ ， $\lambda w_g=1$ 。能据等号断言该组必须非零吗？答案：不能；零组 KKT 使用闭球，边界仍允许零。
$z=(6,8)$ 、 $\alpha\lambda w_g=5$ ，输出与残差分别是什么？答案： $u=(3,4)$ ， $z-u=(3,4)$ ；残差长度为五，且方向与非零输出一致。逐坐标减五会得到 $(1,3)$ ，不能通过同一最优性关系。

参考资料

Neal Parikh and Stephen Boyd, Proximal Algorithms，作者版，§6.5.1（印刷页187）及 §6.5.4（189）：欧氏块收缩与不相交组；§4.2：近端梯度。本页另推导加权分组的对偶消元并给出耦合设计证书。
Jerome Friedman, Trevor Hastie and Robert Tibshirani, A Note on the Group Lasso and a Sparse Group Lasso，2010，§2：非正交组设计及求解条件。组内一般设计不意味着整块回归子问题可直接欧氏收缩；本页把收缩用于梯度后的欧氏近端子问题。
Stephen Boyd and Lieven Vandenberghe, Convex Optimization，2004，§3.3.1、Example 3.26（印刷页93）：范数共轭为对偶单位球的指标函数；上文明确区分对偶范数与共轭函数。

形式陈述 ​

两组耦合设计的一轮与终点 ​

改权重后的迁移 ​

重叠组不能照抄独立块公式 ​

从零点的球到径向收缩 ​

组对偶的消元与间隙恒等式 ​

可停止算法与成本 ​

两道短自测 ​

反向链接