Reading some papers, I start dealing with the differentiability of a function. For a point $x\in \mathbb R^d$, a finite set $S \subset \mathbb R^d$ and a function on it $W: S \to \mathbb R^d$ (which can be seen as a vector in $\mathbb R^{|S|}$), I want to show that the function $$h: W \mapsto \min_{s\in S} \left(\|x-s\|^2 - W(s) \right)$$ is almost everywhere differentiable. I guess then it holds $$\frac{\partial h}{\partial W(s)}(W) = \begin{cases} -1 &\mbox{if } s = argmin_{\tilde s \in S}\|x-\tilde s\|^2 - W(\tilde s) \\ 0 & \mbox{else } \end{cases}. $$
The intuition behind this question, is on how do the "power diagrams" vary when changing its weights W. Power diagrams are generalizations of Voronoi diagrams. Here the cells are given by $cell_W(s) = \{x\in \mathbb R^d: pow(s,x) < pow(\tilde s, x), \text{ for all } \tilde s \in S \setminus \{s\} \}$, where $pow(s,x) = \|x-s\|^2 -W(s)$.
As an idea, I was thinking of not fixing the point $x\in \mathbb R^d$, and considering the the function $$ \tilde h (W,x) \mapsto \min_{s\in S} \left(\|x-s\|^2 - W(s) \right).$$ For every $W \in \mathbb R^{|S|}$, $\tilde h (W,\cdot) $ is a simple function, and thus almost everywhere differentiable (because it is constant in every power cell).
I think a got a proof. Defining $$\mathbb 1 _{T_W(x)=s} = \begin{cases} 1 &\mbox{if } T_W(x) := argmin_{\tilde s\in S} \|x− \tilde s\|^2−W(\tilde s)= s \\ 0 & \mbox{else } \end{cases} $$ and denoting by $(1 _{T_W(x)=s} )_{s\in S}$ the vector in $\mathbb R^{|S|}$, I show the differentiability of $\tilde h$ at any point $W\in \mathbb R^{|S|}$ and for any $x\in \mathbb R^d$ which doesn't lie in the boundary of of a power cell, i.e. any point $x\in \mathbb R^d$ such that $$ \|x-s\|^2 -W(s) \neq \|x- \tilde s\|^2 -W(\tilde s), \quad \text{for any two different } s,\tilde s\in S. $$ Recall that for this, we need to show the existence of a linear function $Dh_{W} : \mathbb R^{|S|} \to \mathbb R$ which satisfies $$\lim_{\|t\| \to 0} \frac{|h(W+t) - h(W) - Dh_{W}(t) |}{\|t\|} = 0. $$ This is attain by the linear map $DF_{W} : t \mapsto \langle (\mathbb - 1_{T_W(x)=s})_{s\in S} , t \rangle $, where $(\mathbb 1_{T_W(x)=s})_{s\in S}$ is defined as above. Indeed, because of the conditions of $x$ we get for very small $\|t\|$ $$ \tilde s := argmin_{s\in S} \left( \| x-s \|^2 - W(s) + t(s) \right) = argmin_{s\in S} \left( \| x-s \|^2 - W(s) \right) ,$$ and hence $$ \left| \widetilde h(W+t,x) - h(W,x) - D\widetilde h_W(t) \right| = \left| \min_{s\in S} \left( \| x-s \|^2 - W(s) - t(s) \right) - \min_{s\in S} \left( \| x-s \|^2 - W(s) \right) - \langle (-\mathbb 1_{T_W(x)=s})_{s\in S}, t \rangle \right | = \left| \left( \| x- \tilde s \|^2 - W(s) - t(s) \right) - \left( \| x- \tilde s \|^2 - W(s) \right) - \langle (-\mathbb 1_{T_W(x)=s})_{s\in S}, t \rangle \right | = \left| -t(s) + t(s) \right | = 0 $$