Dual function non-overlapping Group Lasso's penalty function

Question

I'm trying to find the dual function of this function (non-overlapping Group Lasso's penalty function): $$ \mathfrak{h}: \mathbb{R}^p \to [0,\infty], \ a \mapsto \sum_{j=1}^{k} \left\| a_{\mathscr{A}_j} \right\|_{2}$$ where $\mathscr{A_1},\dots, \mathscr{A_k}$ are disjoint partitions of $\left\{ 1,\dots,p \right\}$, that is $\bigcup_{j=1}^{k} \mathscr{A}_j=\left\{ 1,\dots,p \right\},\ \mathscr{A}_j \not=\emptyset \ \forall j, \text{and} \ \mathscr{A}_i \cap \mathscr{A}_j \not= 0, \ \forall i\not= j. $

The (Hölder) dual function definition is (according to https://link.springer.com/book/10.1007/978-3-030-73792-4):

Given a function $\mathfrak{h}: \mathbb{R}^p \to \mathbb{R}$, we define $\bar{\mathfrak{h}}:\mathbb{R}^p \to [-\infty,\infty]$ through $$\bar{\mathfrak{h}}: a \mapsto \sup \left\{ \langle a,c \rangle: c \in \mathbb{R}^p, \mathfrak{h}(c) \le 1 \right\}, $$ where $\langle a,c \rangle = \sum_{j=1}^{p} a_{j}c_{j}$ is the standard inner product. We call $\bar{\mathfrak{h}}$ the dual function of $\mathfrak{h}$.

Does anyone have an idea?

Answer 1

Fix some $a\in \mathbb R^p$. For any $c\in \mathbb R^p$ that satisfies $h(c)\leq 1$,

$$\begin{aligned} a^\top c &= \sum_{j=1}^k \sum_{k\in A_j} a_k c_k \\&\leq \sum_{j=1}^k \|a_{A_j} \|_2 \cdot \|c_{A_j} \|_2 \\&\leq (\max_{1\leq j \leq k}\|a_{A_j} \|_2) \sum_{j=1}^k \|c_{A_j} \|_2 \\&= \max_{1\leq j \leq k}\|a_{A_j}\|_2 h(c) \\&\leq \max_{1\leq j \leq k}\|a_{A_j}\|_2. \end{aligned}$$

This bound is attained (I let you fill in the details), hence $\bar h: a \mapsto \max_{1\leq j \leq k}\|a_{A_j}\|_2$.

Sanity check:

• when there is a single group, we find that the dual norm of the Euclidean norm is itself.
• when there are $p$ groups, we find that the dual norm of the $\ell^1$ norm is the $\ell^\infty$ norm.