diff options
| -rw-r--r-- | paper/sections/appendix.tex | 20 |
1 files changed, 20 insertions, 0 deletions
diff --git a/paper/sections/appendix.tex b/paper/sections/appendix.tex index eef3f45..1d22402 100644 --- a/paper/sections/appendix.tex +++ b/paper/sections/appendix.tex @@ -1,3 +1,23 @@ +It is easy to compute the gradient and Hessian matrix of $\mathcal{L}$: +\begin{multline*} + \nabla \mathcal{L}(\theta) = + \frac{1}{|\mathcal{T}|}\sum_{t\in \mathcal{T}}x^t\bigg[ + x_i^{t+1}\frac{f'}{f}(\inprod{\theta_i}{x^t})\\ + - (1-x_i^{t+1})\frac{f'}{1-f}(\inprod{\theta_i}{x^t})\bigg] +\end{multline*} +\begin{multline*} + \nabla^2 \mathcal{L}(\theta) = + \frac{1}{|\mathcal{T}|}\sum_{t\in \mathcal{T}}x^t(x^t)^T\bigg[ + x_i^{t+1}\frac{f''f - f'^2}{f^2}(\inprod{\theta_i}{x^t})\\ + - (1-x_i^{t+1})\frac{f''(1-f) + f'^2}{(1-f)^2}(\inprod{\theta_i}{x^t})\bigg] +\end{multline*} + +Since $\E[x_i^{t+1}|x^t] = f(\inprod{\theta_i}{x^t})$, +$\nabla\mathcal{L}(\theta)$ can be written +$\frac{1}{|\mathcal{T}|}\sum_{t\in\mathcal{T}} Y_t$ where $\E[Y_t|Y_{t-1}] += 0$. It follows from the law of expected iterations that +$\E[\nabla\mathcal{L}(\theta)] = 0$. + \subsection{Upper-bound for $\|\nabla f(\theta^*)\|_\infty$} We show an upper-bound for $ 2 \|\nabla f(\theta^*) \|_\infty$. If we only consider the first measurement of every cascade, this can be done easily. Let $N$ be the number of cascades (to distinguish from $n$ number of total measurements). Begin by noting that for a node $\alpha$: |