求解非重叠组Lasso惩罚函数的对偶函数

我来帮你一步步推导这个非重叠组Lasso惩罚函数的对偶函数，咱们从定义出发，结合凸分析的基本不等式来完成：

1. 明确约束集合与对偶问题形式 #

根据Hölder对偶的定义，我们需要计算：
$$
\bar{\mathfrak{h}}(a) = \sup\left{ \langle a,c \rangle : c \in \mathbb{R}^p, \sum_{j=1}^k |c_{\mathscr{A}_j}|_2 \leq 1 \right}
$$
其中$\mathscr{A}_1,...,\mathscr{A}_k$是${1,...,p}$的不相交划分，$\langle a,c \rangle$是标准内积。

2. 拆分内积并应用柯西-施瓦茨不等式 #

由于$\mathscr{A}j$是不相交划分，我们可以把内积按组拆分：
$$
\langle a,c \rangle = \sum{j=1}^k \langle a_{\mathscr{A}j}, c{\mathscr{A}j} \rangle
$$
对每个组$j$，由柯西-施瓦茨不等式可得：
$$
\langle a{\mathscr{A}j}, c{\mathscr{A}j} \rangle \leq |a{\mathscr{A}_j}|2 \cdot |c{\mathscr{A}j}|2
$$
将所有组的结果累加，得到内积的上界：
$$
\langle a,c \rangle \leq \sum{j=1}^k |a{\mathscr{A}_j}|2 \cdot |c{\mathscr{A}_j}|_2
$$

3. 进一步收紧上界 #

令$M = \max_{1 \leq j \leq k} |a_{\mathscr{A}_j}|2$，那么对于所有$j$都有$|a{\mathscr{A}j}|2 \leq M$，代入上式可得：
$$
\sum{j=1}^k |a{\mathscr{A}_j}|2 \cdot |c{\mathscr{A}j}|2 \leq M \cdot \sum{j=1}^k |c{\mathscr{A}j}|2
$$
而约束条件是$\sum{j=1}^k |c{\mathscr{A}j}|2 \leq 1$，因此：
$$
\langle a,c \rangle \leq M = \max{1 \leq j \leq k} |a{\mathscr{A}_j}|_2
$$

4. 验证上界的可达性 #

我们需要找到一个满足约束$\sum_{j=1}^k |c_{\mathscr{A}_j}|_2 \leq 1$的$c$，使得$\langle a,c \rangle$恰好等于$M$：

• 假设$j_0$是满足$|a_{\mathscr{A}_{j_0}}|_2 = M$的组（如果有多个这样的组，任选其一即可）。
• 构造$c$：令$c_{\mathscr{A}{j_0}} = \frac{a{\mathscr{A}{j_0}}}{M}$（当$M \neq 0$时），其余所有组的$c{\mathscr{A}_j} = 0$。
• 此时$\sum_{j=1}^k |c_{\mathscr{A}j}|2 = |c{\mathscr{A}{j_0}}|2 = 1$，满足约束；同时内积：
  $$
  \langle a,c \rangle = \langle a{\mathscr{A}{j_0}}, \frac{a{\mathscr{A}{j_0}}}{M} \rangle = \frac{|a{\mathscr{A}_{j_0}}|_2^2}{M} = M
  $$
• 如果$M = 0$（即所有组的$a_{\mathscr{A}_j}$都是零向量），那么$\langle a,c \rangle = 0 = M$，显然成立。

最终结论 #

非重叠组Lasso惩罚函数$\mathfrak{h}(a) = \sum_{j=1}^k |a_{\mathscr{A}j}|2$的Hölder对偶函数为：
$$
\bar{\mathfrak{h}}(a) = \max{1 \leq j \leq k} |a{\mathscr{A}j}|2
$$
这个结果可以理解为**$\ell\infty(\ell_2)$范数**，是组Lasso对应的$\ell_1(\ell_2)$范数的对偶，和向量$\ell_1$范数对偶是$\ell\infty$范数的结论完全平行。

备注：内容来源于stack exchange，提问作者Mai Khanh Truong