Inequalities for a lipschitz function

174 Views Asked by At

Given the set $E = \left \{ z_{i} \in \mathbb{R}^{d} \: , \:1 \leq i \leq N \:\:\: and \:\:\: N\in\mathbb{N} \right \}$, a matrix $W \in \mathbb{R}^{d' \times d}$ such that $d' < d$, a binary matrix $A \in \left \{0,1 \right \}^{N \times N}$, a vector $b \in \mathbb{R}^{d'}$, and two functions $f$ and $L$:

\begin{aligned} f: \:\: & \mathbb{R}^{d} \rightarrow \mathbb{R}^{d'} \\ & z_{i} \mapsto \text{max}(W z_{i} + b, 0) \end{aligned}

\begin{aligned} \:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:L: \:\: & \mathbb{R}^{d} \rightarrow \mathbb{R} \\ & z_{i} \mapsto \frac{1}{2} \sum_{ 1\leq j \leq N} a_{ij} (z_{i}-z_{j})^{T}(z_{i}-z_{j}) \end{aligned}

I want to study the sign of $S$ such that:

$$S(z_{i}) = \sum_{1 \leq j, j' \leq N} \: a_{i,j} \: a_{i,j'} \: (z_{i} - z_{j})^{T} \bigg( \left \| \triangledown_{z_{i}} L(z_{i}) \right \|_{2} \: (f(z_{i}) - f(z_{j'})) - \left \| \triangledown_{z_{i}} L(f(z_{i})) \right \|_{2} \: (z_{i} - z_{j'}) \bigg)$$

So far I computed the gradients $ \triangledown_{z_{i}} L(z_{i}) $ and $\triangledown_{z_{i}} L(f(z_{i})) $ and I have made several trials based on Lipschitz continuity of $f$. A complete answer is not required; even a recommendation or a reference on how to start solving a similar problem would be quite helpful.

What I found so far:

$$\triangledown_{z_{i}} L(z_{i}) = \sum_{1 \leq j \leq N} a_{ij} (z_{i} - z_{j})$$ $$\triangledown_{z_{i}} L(f(z_{i})) = \sum_{1 \leq j \leq N} a_{ij} (f(z_{i}) - f(z_{j})) \: . \: \text{diag}(\text{sign}(f(z_{i}))) \: . \: W$$ $f$ is a Lipschitzian function and the spectral norm of $W$ is an upper bound on $f$ Lipschitz constant. Thus: $$ (z_i-z_j)^T(f(z_i)-f(z_j))\leq \left \| W \right \|\Vert z_i-z_j\Vert^2$$

Is there a certain constraint on $z_{j'}$, apart from $z_{j'} = z_{j}$, so that this statement becomes valid:

$$(z_i-z_j)^T(f(z_i)-f(z_{j'}))\leq \left \| W \right \| (z_i-z_{j})^T(z_i-z_{j'}) $$