Concavity condition

1 files changed, 13 insertions, 9 deletions

diff --git a/paper/sections/model.tex b/paper/sections/model.tex
index cd7485d..25f55e0 100644
--- a/paper/sections/model.tex
+++ b/paper/sections/model.tex
@@ -138,7 +138,7 @@ log-likelihood function, we consider the following $\ell_1$-regularized MLE
 problem:
 \begin{displaymath}
     \hat{\Theta} \in \argmax_{\Theta} \frac{1}{n} \mathcal{L}(\Theta\,|\,x^1,\ldots,x^n)
-    + \lambda\|\Theta\|_1
+    - \lambda\|\Theta\|_1
 \end{displaymath}
 where $\lambda$ is the regularization factor which helps at preventing
 overfitting as well as controlling for the sparsity of the solution.
@@ -150,15 +150,19 @@ Since this is equally true for $\|\Theta\|_1$, each column $\theta_i$ of
 $\Theta$ can be estimated by a separate optimization program:
 \begin{equation}\label{eq:pre-mle}
     \hat{\theta}_i \in \argmax_{\theta} \frac{1}{n}\mathcal{L}_i(\theta_i\,|\,x^1,\ldots,x^n)
-    + \lambda\|\theta_i\|_1
+    - \lambda\|\theta_i\|_1
 \end{equation}
 where we denote by ${\cal T}_i$ the time steps at which node $i$ is susceptible and:
-\begin{multline}
-    \mathcal{L}_i(\theta_i\,|\,x^1,\ldots,x^n) = \frac{1}{|{\cal T}_i|} \sum_{t\in {\cal T}_i } x_i^{t+1}\log f(\inprod{\theta_i}{x^{t}}) + \dots \nonumber \\
-    (1 - x_i^{t+1})\log\big(1-f(\inprod{\theta_i}{x^t})\big)  + \lambda\|\theta_i\|_1  \nonumber
-\end{multline}
+\begin{multline*}
+    \mathcal{L}_i(\theta_i\,|\,x^1,\ldots,x^n) = \frac{1}{|{\cal T}_i|} \sum_{t\in {\cal T}_i } x_i^{t+1}\log f(\inprod{\theta_i}{x^{t}}) \\
+    + (1 - x_i^{t+1})\log\big(1-f(\inprod{\theta_i}{x^t})\big)
+\end{multline*}
 
-Note that in the case of the voter model, TODO horizon time. In the case of the independent cascade model...
+A sufficient condition for program~\eqref{eq:pre-mle} to be a convex program is
+that $\mathcal{L}_i$ is a concave function. This will be the case if, for
+example, $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.
 
-TODO: discuss conditions on $f$ under which this program is convex. For LC and
-VM it is convex.
+Note that in the case of the voter model, TODO horizon time. In the case of the independent cascade model...