Add convex constraints

1 files changed, 24 insertions, 0 deletions

diff --git a/paper/sections/model.tex b/paper/sections/model.tex
index f1d9585..575f88c 100644
--- a/paper/sections/model.tex
+++ b/paper/sections/model.tex
@@ -326,3 +326,27 @@ for some $\alpha\in(0, 1)$ and for all $z_x\defeq\inprod{\theta^*}{x}$ such
 that $f(z_x)\notin\{0,1\}$. It is again easy to see that this condition is
 verified for the Independent Cascade Model and the Voter model for the same
 $\alpha\in(0,1)$.
+
+\paragraph{Convex constraints} The voter model is only defined when
+$\Theta_{i,j}\in (0,1)$ for all $(i,j)\in E$. Similarly the independent cascade
+model is only defined when $\Theta_{i,j}> 0$. One could wonder whether or not
+these constraints need to explicitly appear in the optimization
+program~\eqref{eq:pre-mle}, otherwise the program could return an estimate
+$\hat{\theta}_i$ for which the models are undefined. We claim that adding these
+constraints is unnecessary since the likelihood function $\mathcal{L}_i$ is
+equal to $-\infty$ when the parameters are outside of the domain of definition
+of the models. Hence those ``bad'' estimates will never be returned by the
+optimization program.
+
+In the specific case of the voter model the constraint $\sum_j \Theta_{i,j}
+= 1$ will not necessarily be verified by the estimator obtained in
+\eqref{eq:pre-mle}. In some applications, the experimenter might not need this
+constraint to be verified, in which case the results in
+Section~\ref{sec:results} still give a bound on the recovery error. If this
+constraint needs to be satisfied, then by Lagrangian duality, there exists
+a $\lambda\in \reals$ such that adding $\lambda\big(\sum_{j}\theta_j
+- 1\big)$ to the objective function of \eqref{eq:pre-mle} enforces the
+constraint. Then, it suffices to apply the results of Section~\ref{sec:results}
+to the augmented objective to obtain the same recovery guarantees. Note that
+the added term is linear and will easily satisfy all the required regularity
+assumptions.