spectral norm on sub-blocks of Hessian

96 Views Asked by At

Let $~f(x_1,\ldots,x_p) : \mathbb{R}^n \rightarrow \mathbb{R}$, $x_i \in \mathbb{R}^{d_i}$ for all $i=1,\ldots,p$ and $n=\sum_{i=1}^p d_i$. Suppose that for the $i$-th block variables $x_i,x_i' \in \mathbb{R}^{d_i}$, we have $$\| \nabla_i f(x_1,\ldots,x_{i-1},x_i,x_{i+1},\ldots,x_p) - \nabla_i f(x_1,\ldots,x_{i-1},x_i',x_{i+1},\ldots,x_p) \|_2 \leq L_i \| x_i - x_i'\|_2$$ and for the entire variables $x,x' \in \mathbb{R}^{n}$, we have $$\| \nabla f(x) - \nabla f(x') \|_2 \leq L \|x - x'\|_2,$$ then is it correct that for the Hessian of $f$, defined as $$\nabla^2 f(x) = H = \left[ \begin{array}{cccc} H_{11} & H_{12} & \cdots & H_{1p} \\ H_{21} & H_{22} & \cdots & H_{2p} \\ \vdots & \vdots & \vdots & \vdots \\ H_{p1} & H_{p2} & \cdots & H_{pp} \end{array} \right],$$ where $H_{ij} \in \mathbb{R}^{d_i \times d_j}$, the spectral norms satisfy$$\| H_{ij} \|_2 \leq \sqrt{L_i \cdot L_j}$$ and $$\| H_{*j} \|_2 \leq \sqrt{L \cdot L_j},$$ where $H_{*j} = \left[ \begin{array}{c} H_{1j} \\ H_{2j} \\ \vdots \\ H_{pj} \end{array} \right] \in \mathbb{R}^{n \times d_j}?$ Why? If not, what are the tight upper bounds of $H_{ij}$ and $H_{*j}$ in terms of $L_i,L_j$ and $L$?