diff options
Diffstat (limited to 'paper')
| -rw-r--r-- | paper/figures/n_cascades_running_time.pdf | bin | 13257 -> 14005 bytes | |||
| -rw-r--r-- | paper/sections/model.tex | 26 |
2 files changed, 11 insertions, 15 deletions
diff --git a/paper/figures/n_cascades_running_time.pdf b/paper/figures/n_cascades_running_time.pdf Binary files differindex 1d221ca..ca4e6c2 100644 --- a/paper/figures/n_cascades_running_time.pdf +++ b/paper/figures/n_cascades_running_time.pdf diff --git a/paper/sections/model.tex b/paper/sections/model.tex index 575f88c..fd25c27 100644 --- a/paper/sections/model.tex +++ b/paper/sections/model.tex @@ -289,12 +289,12 @@ measurements and not the number of cascades. \paragraph{Regularity assumptions} -We would like program~\eqref{eq:pre-mle} to be convex in order to -solve it efficiently. A sufficient condition is to -assume that $\mathcal{L}_i$ is a concave function, which is the case if $f$ and -$(1-f)$ are both log-concave functions. Remember that a twice-differentiable -function $f$ is log-concave iff. $f''f \leq f'^2$. It is easy to verify this -property for $f$ and $(1-f)$ in the Independent Cascade Model and Voter Model. +To solve program~\eqref{eq:pre-mle} efficiently, we would like it to be convex. +A sufficient condition is to assume that $\mathcal{L}_i$ is concave, which is +the case if $f$ and $(1-f)$ are both log-concave. Remember that a +twice-differentiable function $f$ is log-concave iff. $f''f \leq f'^2$. It is +easy to verify this property for $f$ and $(1-f)$ in the Independent Cascade +Model and Voter Model. Furthermore, the data-dependent bounds in Section~\ref{sec:main_theorem} will require the following regularity assumption on the inverse link function $f$: @@ -329,14 +329,10 @@ $\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. +model is only defined when $\Theta_{i,j}> 0$. Because the likelihood function +$\mathcal{L}_i$ is equal to $-\infty$ when the parameters are outside of the +domain of definition of the models, these contraints do not need to appear +explicitly in 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 @@ -345,7 +341,7 @@ 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 +- 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 |