diff options
Diffstat (limited to 'finale')
| -rw-r--r-- | finale/project_proposal.tex | 164 | ||||
| -rw-r--r-- | finale/sparse.bib | 507 |
2 files changed, 602 insertions, 69 deletions
diff --git a/finale/project_proposal.tex b/finale/project_proposal.tex index 5e0d21c..c8607e6 100644 --- a/finale/project_proposal.tex +++ b/finale/project_proposal.tex @@ -1,96 +1,122 @@ -\documentclass[8pt]{article} +\documentclass[10pt]{article} +\usepackage[utf8x]{inputenc} \usepackage{fullpage, amsmath, amssymb, amsthm} +\usepackage{bbm} +\DeclareMathOperator*{\argmax}{argmax} -\title{Regression Analysis with Network data} -\author{Jean Pouget-Abadie, Thibaut Horel} -\date{} +\title{Regression Analysis with Network Data} +\author{Thibaut Horel \and Jean Pouget-Abadie} \begin{document} \maketitle -\subsection*{The Network Inference problem} +\section{Background: Cascade Models and Network Inference} -The network inference problem concerns itself with learning the edges and the -edge weights of an unknown network. Each edge weight $\theta_e, e\in E$ is a -parameter to be estimated. The information at our disposal is the result of a -cascade process on the network. Here, we will focus on the Generalized Linear -Cascade (GLC) model introduced in~\cite{paper} presented below. +The Network Inference Problem concerns itself with learning the edges and the +edge weights of an unknown network on the set of vertices $V$. Formally, the +set of parameters to learn is a matrix $\theta\in\mathbb{R}^{V\times V}$ where +$\theta_{u,v}$ is the weight corresponding to the pair of vertices $(u, v)$. +The observations at our disposal for this learning task are samples drawn for +a probabilistic cascade model. In this project, we will focus on the +Generalized Linear Cascade (GLC) model introduced in~\cite{pouget} that we +briefly present below. -\paragraph{The GLC model} - -Consider a graph $\mathcal{G} = (N, E)$, where nodes $N$ can be one of three -possible states: susceptible, infected, and immune. Let $x^t$ be the indicator -variable of ``infected nodes'' at time step $t$. A \emph{generalized linear -cascade model} is a cascade model such that for each ``susceptible'' node $i$ at -time step $t$, the probability of $i$ becoming ``infected'' at time step $t+1$ -conditioned on $x^t$ is a Bernoulli variable of parameter $f(\theta_i -\cdot X^t)$: +\paragraph{GLC model.} The nodes in $V$ can be in one of three possible states: +susceptible, infected, and immune. Let $x^t$ be the indicator variable of +``infected nodes'' at time step $t$ and $S_t$ be the set of susceptible nodes +at time step $t$. A \emph{generalized linear cascade model} is a discrete-time +random process in which the conditional law of $x^{t+1}$ given $x^t$ takes the +following form: for each ``susceptible'' node $i$ at time step $t$, the +probability of $i$ becoming ``infected'' at time step $t+1$ conditioned on +$x^t$ is a Bernoulli variable of parameter $f(\theta_i \cdot x^t)$: \begin{equation} - \mathbb{P}(x^{t+1}_i = 1|x^t) = f(\theta_i \cdot x^t) + \label{eq:model} + \mathbb{P}(x^{t+1}_i = 1\,|\,x^t) = f(\theta_i \cdot x^t), + \quad i\in S_t \end{equation} -where $f: \mathbb{R} \rightarrow [0,1]$. There is no a priori rule for the -transition from and to the immune and susceptible state, but the most commonly -studied GLC model, known as the Independent Cascade model, assumes that all +for some function $f: \mathbb{R} \rightarrow [0,1]$ and where $\theta_i += (\theta_{u, i})_{u\in V}$. There is no a priori rule for the transition from +and to the immune and susceptible state, but the most commonly studied GLC +model, known as the Independent Cascade model \cite{Kempe:03}, assumes that all infected nodes at time step $t$ are immune for all time steps $t' \geq t+1$. Under this assumption, a cascade ends when no ``infected'' nodes remain. The designer is also free to decide the initial state of graph $\mathcal{G}$ at the -beginning of every cascade process. For simplicity, we will suppose that, at the -start of each cascade, one node is chosen uniformly at random to be +beginning of every cascade process. For simplicity, we will suppose that, at +the start of each cascade, one node is chosen uniformly at random to be ``infected'', and that all other nodes are in the ``susceptible'' state. -\bigskip -The network inference problem can therefore be formalized as finding the support -of the edge weight vector $\theta$ from the observation of ${(x^c_t)}_{c\in -\mathcal{C}, t\in \mathcal{T}_C}$, where $\mathcal{C}$ indexes the cascade -number, and $\mathcal{T}_C$ the time step in that cascade. Prior work has -observed that the network inference problem is decomposable node-by-node -i.e.~solving for $\beta_{i} = \{\theta_{i,j} | j \in N\}$ for node $i$. This can -easily be formulated as the following maximum likelihood program: -$$ \theta_{i} \in \arg \max_\theta \log -\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(\theta_i\cdot x^{t}) + (1 - -x_i^{t+1})\log\big(1-f(\theta_i \cdot x^t)\big)$$ -where $\mathcal{T}_i = \{\text{node i is ``susceptible'' at time step } t\}$. -The reader will note the above problem boils down to fitting a generalized -linear model. In particular, if $f$ is the sigmoid function, we are performing +\paragraph{Inference.} A cascade is the collection of vectors $x^t$ for all +time steps until the cascade ends. Given a sample of independent cascades, the +parameters $\theta$ can be estimated using maximum likelihood estimation. Prior +work has observed that the MLE problem can be decomposed node-by-node +\emph{i.e}, $\theta_i$ can be learned independently for each node $i$ by +solving the following optimization program: +\begin{equation} + \label{eq:mle} + \hat{\theta}_{i} \in \argmax_\theta + \log \mathcal{L}_i(\theta_i) = + \sum_{t:i\in S_t} x_i^{t+1}\log f(\theta_i\cdot x^{t}) + + (1 - x_i^{t+1})\log\big(1-f(\theta_i \cdot x^t)\big) +\end{equation} +The reader will observe that the above problem reduces to fitting a generalized +linear model. It is important to note that even though the cascades are +independent, the vectors $x^t$ observed within a cascade are not independent +since they follow the Markov process described in \eqref{eq:model}. In the +particular case where $f$ is the sigmoid function, we are performing logistic regression: -$$ +\begin{displaymath} \begin{cases} -y_i^* = \theta_i \cdot x_i + \epsilon \text{~where~} \epsilon\sim -Logistic(0, 1) \text{~and~} x = {(x^t)}_{t \in \mathcal{T}_i}\\ -y_i = [y_i^* > 0] \text{~where~} y_i^t = x_i^{t+1} + y^t = \theta_i \cdot x^t + \varepsilon^t + &\text{where } \varepsilon^t\sim \text{Logistic}(0, 1)\\ + \tilde{y}^t = \mathbf{1}\{y^t > 0\} &\text{where } x_i^{t+1} = \tilde{y}^t \end{cases} -$$ +\end{displaymath} -\subsection*{Objectives} +\section{Problem Statement} +A growing series of work (see for example \cite{Netrapalli:2012, +Daneshmand:2014, pouget}) has focused on solving the Network Inference Problem +under different cascade models and obtaining estimators with close-to-optimal +convergence rates. However, these works often rely on hard-to-interpret +assumptions which often hide subtle properties of the probabilistic model +\eqref{eq:model}. The overarching goal of the current project is to analyze the +fundamental statistical properties of observations coming from model +\eqref{eq:model} and of the MLE estimator \eqref{eq:mle}. In particular we are +interested in the following questions: \begin{itemize} -\item Try a Bayesian approach to estimate these parameters. Use the posterior -predictive distribution to obtain confidence intervals for the edge parameters. -Validate this with bootstrapping. How does this perform in different networks? -Can you intuitively link certain node-level/graph-level properties with the -resulting variance on the estimated parameter? -\item Do the previous observations correspond with the theoretical result, given -by the Fisher information matrix: $$\hat \beta \sim \mathcal{N}(\beta, -I{(\theta)}^{-1})$$ where $I(\theta) = - {\left(\frac{\partial^2\log -\mathcal{L}}{\partial \theta^2} \right)}^{-1}$ +\item Is the model \eqref{eq:model} identifiable and is the MLE estimator + \eqref{eq:mle} consistent? Are there networks which are fundamentally + ambiguous and for which the Network Inference Problem is unsolvable? +\item Use a Bayesian approach to estimate the parameters. Use the posterior + predictive distribution to obtain confidence intervals for the edge + parameters. Validate this with bootstrapping. +\item Are there networks which are harder to learn than others? Can the + variance of the MLE estimator be related to certain graph theoretic + properties of the network? +\item Do the previous observations match with the theoretical result, given +by the Fisher information matrix: +\begin{displaymath} + \hat{\theta}_i \sim \mathcal{N}(\theta_i, I{(\theta_i)}^{-1}) + \quad \text{where}\; + I(\theta) = - \left(\frac{\partial^2\log \mathcal{L}_i}{\partial \theta^2} + \right)^{-1} +\end{displaymath} \item Are there networks in which the Fisher information matrix is singular? -What happens to the estimation of $\beta$ in this case? -\item What if the generative process is generated with a different link -function? Is there a regularization scheme which can mitigate any bias/exploding -variance in the estimated parameters? +What happens to the estimation of $\theta_i$ in this case? +\item Is the estimator \eqref{eq:mle} robust to the choice of $f$? What if the + observations are generated with $f_1$, but \eqref{eq:mle} is solved with + $f_2\neq f_1$? Is there a regularization scheme which can mitigate any bias + or lack of convergence in the estimated parameters? \end{itemize} -\subsection*{Program plan} - -The project will be a series of simulations to answer each of the above -questions? When possible, we will try to explain the results found in the -simulation with a simplified analysis on toy-networks. Thibaut and I have worked -together in the past, and have kept our contributions balanced. +\paragraph{Roadmap.} We plan to answer the above question by a mixture of +a theoretical-based and a simulation-based approaches. We expect some of these +questions to be hard from the theoretical standpoint. In those cases, the +hardness can be mitigated by using simulations or focusing on specific cases: +toy-networks (star graph, cycle, complete graph, etc.) or simpler cascades +models (the Voter Model for example). -\begin{thebibliography}{1} -\bibitem{paper} Pouget-Abadie, J. and Horel, T. \emph{Inferring Graphs from -Cascades: A Sparse Recovery Framework}, ICML 2015 -\end{thebibliography} +\bibliography{sparse} +\bibliographystyle{abbrv} \end{document} diff --git a/finale/sparse.bib b/finale/sparse.bib new file mode 100644 index 0000000..f50a0d2 --- /dev/null +++ b/finale/sparse.bib @@ -0,0 +1,507 @@ +@article {CandesRomberTao:2006, +author = {Candès, Emmanuel J. and Romberg, Justin K. and Tao, Terence}, +title = {Stable signal recovery from incomplete and inaccurate measurements}, +journal = {Communications on Pure and Applied Mathematics}, +volume = {59}, +number = {8}, +publisher = {Wiley Subscription Services, Inc., A Wiley Company}, +issn = {1097-0312}, +pages = {1207--1223}, +year = {2006}, +} + + +@inproceedings{GomezRodriguez:2010, + author = {Gomez Rodriguez, Manuel and Leskovec, Jure and Krause, Andreas}, + title = {Inferring Networks of Diffusion and Influence}, + booktitle = {Proceedings of the 16th ACM SIGKDD International Conference on + Knowledge Discovery and Data Mining}, + series = {KDD '10}, + year = {2010}, + isbn = {978-1-4503-0055-1}, + location = {Washington, DC, USA}, + pages = {1019--1028}, + numpages = {10}, + publisher = {ACM}, + address = {New York, NY, USA}, +} + +@inproceedings{pouget, + title={Inferring graphs from cascades: A Sparse Recovery Framework}, + author={Pouget-Abadie, Jean and Horel, Thibaut}, + booktitle = {ICML}, + year={2015} +} + +@inproceedings{du2013uncover, + title={Uncover topic-sensitive information diffusion networks}, + author={Du, Nan and Song, Le and Woo, Hyenkyun and Zha, Hongyuan}, + booktitle={Proceedings of the Sixteenth International Conference on + Artificial Intelligence and Statistics}, + pages={229--237}, + year={2013} +} + +@inproceedings{du2014influence, + title={Influence function learning in information diffusion networks}, + author={Du, Nan and Liang, Yingyu and Balcan, Maria and Song, Le}, + booktitle={Proceedings of the 31st International Conference on Machine + Learning (ICML-14)}, + pages={2016--2024}, + year={2014} +} + + +@article{Netrapalli:2012, + author = {Netrapalli, Praneeth and Sanghavi, Sujay}, + title = {Learning the Graph of Epidemic Cascades}, + journal = {SIGMETRICS Perform. Eval. Rev.}, + volume = {40}, + number = {1}, + month = {June}, + year = {2012}, + issn = {0163-5999}, + numpages = {12}, + publisher = {ACM}, + address = {New York, NY, USA}, + keywords = {cascades, epidemics, graph structure learning}, +} + +@article{Negahban:2009, + author = {Negahban, Sahand N. and Ravikumar, Pradeep and Wrainwright, Martin J. and Yu, Bin}, + title = {A Unified Framework for High-Dimensional Analysis of M-Estimators with Decomposable Regularizers}, + Journal = {Statistical Science}, + year = {2012}, + month = {December}, + volume = {27}, + number = {4}, + pages = {538--557}, +} + +@article{Zhao:2006, + author = {Zhao, Peng and Yu, Bin}, + title = {On Model Selection Consistency of Lasso}, + journal = {J. Mach. Learn. Res.}, + issue_date = {12/1/2006}, + volume = {7}, + month = dec, + year = {2006}, + issn = {1532-4435}, + pages = {2541--2563}, + numpages = {23}, + acmid = {1248637}, + publisher = {JMLR.org}, +} + +@inproceedings{Daneshmand:2014, + author = {Hadi Daneshmand and + Manuel Gomez{-}Rodriguez and + Le Song and + Bernhard Sch{\"{o}}lkopf}, + title = {Estimating Diffusion Network Structures: Recovery Conditions, Sample + Complexity {\&} Soft-thresholding Algorithm}, + booktitle = {ICML}, + year = {2014}, + timestamp = {Fri, 07 Nov 2014 20:42:30 +0100}, + bibsource = {dblp computer science bibliography, http://dblp.org} +} + +@inproceedings{Kempe:03, + author = {David Kempe and + Jon M. Kleinberg and + {\'{E}}va Tardos}, + title = {Maximizing the spread of influence through a social network}, + booktitle = {KDD}, + year = {2003}, + timestamp = {Mon, 13 Feb 2006 15:34:20 +0100}, + bibsource = {dblp computer science bibliography, http://dblp.org} +} + +@inproceedings{Abrahao:13, + author = {Bruno D. Abrahao and + Flavio Chierichetti and + Robert Kleinberg and + Alessandro Panconesi}, + title = {Trace complexity of network inference}, + booktitle = {The 19th {ACM} {SIGKDD} International Conference on Knowledge Discovery + and Data Mining, {KDD} 2013, Chicago, IL, USA, August 11-14, 2013}, + pages = {491--499}, + year = {2013}, + timestamp = {Tue, 10 Sep 2013 10:11:57 +0200}, + bibsource = {dblp computer science bibliography, http://dblp.org} +} + + +@article{vandegeer:2009, +author = "van de Geer, Sara A. and B{\"u}hlmann, Peter", +fjournal = "Electronic Journal of Statistics", +journal = "Electron. J. Statist.", +pages = "1360--1392", +publisher = "The Institute of Mathematical Statistics and the Bernoulli Society", +title = "On the conditions used to prove oracle results for the Lasso", +volume = "3", +year = "2009" +} + +@article{vandegeer:2011, +author = "van de Geer, Sara and Bühlmann, Peter and Zhou, Shuheng", +fjournal = "Electronic Journal of Statistics", +journal = "Electron. J. Statist.", +pages = "688--749", +publisher = "The Institute of Mathematical Statistics and the Bernoulli Society", +title = "The adaptive and the thresholded Lasso for potentially misspecified + models (and a lower bound for the Lasso)", +volume = "5", +year = "2011" +} + +@article{Zou:2006, +author = {Zou, Hui}, +title = {The Adaptive Lasso and Its Oracle Properties}, +journal = {Journal of the American Statistical Association}, +volume = {101}, +number = {476}, +pages = {1418-1429}, +year = {2006}, +} + +@article{Jacques:2013, + author = {Laurent Jacques and + Jason N. Laska and + Petros T. Boufounos and + Richard G. Baraniuk}, + title = {Robust 1-Bit Compressive Sensing via Binary Stable Embeddings of + Sparse Vectors}, + journal = {{IEEE} Transactions on Information Theory}, + volume = {59}, + number = {4}, + pages = {2082--2102}, + year = {2013}, + timestamp = {Tue, 09 Apr 2013 19:57:48 +0200}, + bibsource = {dblp computer science bibliography, http://dblp.org} +} + +@inproceedings{Boufounos:2008, + author = {Petros Boufounos and + Richard G. Baraniuk}, + title = {1-Bit compressive sensing}, + booktitle = {42nd Annual Conference on Information Sciences and Systems, {CISS} + 2008, Princeton, NJ, USA, 19-21 March 2008}, + pages = {16--21}, + year = {2008}, + timestamp = {Wed, 15 Oct 2014 17:04:27 +0200}, + bibsource = {dblp computer science bibliography, http://dblp.org} +} + +@inproceedings{Gupta:2010, + author = {Ankit Gupta and + Robert Nowak and + Benjamin Recht}, + title = {Sample complexity for 1-bit compressed sensing and sparse + classification}, + booktitle = {{IEEE} International Symposium on Information Theory, {ISIT} 2010, + June 13-18, 2010, Austin, Texas, USA, Proceedings}, + pages = {1553--1557}, + year = {2010}, + timestamp = {Thu, 15 Jan 2015 17:11:50 +0100}, + bibsource = {dblp computer science bibliography, http://dblp.org} +} + +@article{Plan:2014, + author = {Yaniv Plan and + Roman Vershynin}, + title = {Dimension Reduction by Random Hyperplane Tessellations}, + journal = {Discrete {\&} Computational Geometry}, + volume = {51}, + number = {2}, + pages = {438--461}, + year = {2014}, + timestamp = {Tue, 11 Feb 2014 13:48:56 +0100}, + bibsource = {dblp computer science bibliography, http://dblp.org} +} + +@article{bickel:2009, +author = "Bickel, Peter J. and Ritov, Ya’acov and Tsybakov, Alexandre B.", +fjournal = "The Annals of Statistics", +journal = "Ann. Statist.", +month = "08", +number = "4", +pages = "1705--1732", +publisher = "The Institute of Mathematical Statistics", +title = "Simultaneous analysis of Lasso and Dantzig selector", +volume = "37", +year = "2009" +} + +@article{raskutti:10, + author = {Garvesh Raskutti and + Martin J. Wainwright and + Bin Yu}, + title = {Restricted Eigenvalue Properties for Correlated Gaussian Designs}, + journal = {Journal of Machine Learning Research}, + volume = {11}, + pages = {2241--2259}, + year = {2010}, + timestamp = {Wed, 15 Oct 2014 17:04:32 +0200}, + bibsource = {dblp computer science bibliography, http://dblp.org} +} + +@article{rudelson:13, + author = {Mark Rudelson and + Shuheng Zhou}, + title = {Reconstruction From Anisotropic Random Measurements}, + journal = {{IEEE} Transactions on Information Theory}, + volume = {59}, + number = {6}, + pages = {3434--3447}, + year = {2013}, + timestamp = {Tue, 21 May 2013 14:15:50 +0200}, + bibsource = {dblp computer science bibliography, http://dblp.org} +} + +@article{bipw11, + author = {Khanh Do Ba and + Piotr Indyk and + Eric Price and + David P. Woodruff}, + title = {Lower Bounds for Sparse Recovery}, + journal = {CoRR}, + volume = {abs/1106.0365}, + year = {2011}, + timestamp = {Mon, 05 Dec 2011 18:04:39 +0100}, + bibsource = {dblp computer science bibliography, http://dblp.org} +} + +@inproceedings{pw11, + author = {Eric Price and + David P. Woodruff}, + title = {{(1} + eps)-Approximate Sparse Recovery}, + booktitle = {{IEEE} 52nd Annual Symposium on Foundations of Computer Science, + {FOCS} 2011, Palm Springs, CA, USA, October 22-25, 2011}, + pages = {295--304}, + year = {2011}, + crossref = {DBLP:conf/focs/2011}, + timestamp = {Tue, 16 Dec 2014 09:57:24 +0100}, + bibsource = {dblp computer science bibliography, http://dblp.org} +} + +@proceedings{DBLP:conf/focs/2011, + editor = {Rafail Ostrovsky}, + title = {{IEEE} 52nd Annual Symposium on Foundations of Computer Science, {FOCS} + 2011, Palm Springs, CA, USA, October 22-25, 2011}, + publisher = {{IEEE} Computer Society}, + year = {2011}, + isbn = {978-1-4577-1843-4}, + timestamp = {Mon, 15 Dec 2014 18:48:45 +0100}, + bibsource = {dblp computer science bibliography, http://dblp.org} +} + +@inproceedings{pw12, + author = {Eric Price and + David P. Woodruff}, + title = {Applications of the Shannon-Hartley theorem to data streams and + sparse recovery}, + booktitle = {Proceedings of the 2012 {IEEE} International Symposium on Information + Theory, {ISIT} 2012, Cambridge, MA, USA, July 1-6, 2012}, + pages = {2446--2450}, + year = {2012}, + crossref = {DBLP:conf/isit/2012}, + timestamp = {Mon, 01 Oct 2012 17:34:07 +0200}, + bibsource = {dblp computer science bibliography, http://dblp.org} +} + +@proceedings{DBLP:conf/isit/2012, + title = {Proceedings of the 2012 {IEEE} International Symposium on Information + Theory, {ISIT} 2012, Cambridge, MA, USA, July 1-6, 2012}, + publisher = {{IEEE}}, + year = {2012}, + isbn = {978-1-4673-2580-6}, + timestamp = {Mon, 01 Oct 2012 17:33:45 +0200}, + bibsource = {dblp computer science bibliography, http://dblp.org} +} + +@article{Leskovec:2010, + author = {Jure Leskovec and + Deepayan Chakrabarti and + Jon M. Kleinberg and + Christos Faloutsos and + Zoubin Ghahramani}, + title = {Kronecker Graphs: An Approach to Modeling Networks}, + journal = {Journal of Machine Learning Research}, + volume = {11}, + pages = {985--1042}, + year = {2010}, + timestamp = {Thu, 22 Apr 2010 13:26:26 +0200}, + bibsource = {dblp computer science bibliography, http://dblp.org} +} + +@article{Holme:2002, + author= {Petter Holme and Beom Jun Kim}, + title = {Growing scale-free networks with tunable clustering}, + journal = {Physical review E}, + volume = {65}, + issue = {2}, + pages = {026--107}, + year = {2002} +} + + +@article{watts:1998, + Annote = {10.1038/30918}, + Author = {Watts, Duncan J. and Strogatz, Steven H.}, + Date = {1998/06/04/print}, + Isbn = {0028-0836}, + Journal = {Nature}, + Number = {6684}, + Pages = {440--442}, + Read = {0}, + Title = {Collective dynamics of `small-world' networks}, + Volume = {393}, + Year = {1998}, +} + +@article{barabasi:2001, + author = {R{\'{e}}ka Albert and + Albert{-}L{\'{a}}szl{\'{o}} Barab{\'{a}}si}, + title = {Statistical mechanics of complex networks}, + journal = {CoRR}, + volume = {cond-mat/0106096}, + year = {2001}, + timestamp = {Mon, 05 Dec 2011 18:05:15 +0100}, + bibsource = {dblp computer science bibliography, http://dblp.org} +} + + +@article{gomezbalduzzi:2011, + author = {Manuel Gomez{-}Rodriguez and + David Balduzzi and + Bernhard Sch{\"{o}}lkopf}, + title = {Uncovering the Temporal Dynamics of Diffusion Networks}, + journal = {CoRR}, + volume = {abs/1105.0697}, + year = {2011}, + timestamp = {Mon, 05 Dec 2011 18:05:23 +0100}, + bibsource = {dblp computer science bibliography, http://dblp.org} +} + +@article{Nowell08, + author = {Liben-Nowell, David and Kleinberg, Jon}, + eprint = {http://www.pnas.org/content/105/12/4633.full.pdf+html}, + journal = {Proceedings of the National Academy of Sciences}, + keywords = {SNA graph networks}, + number = 12, + pages = {4633-4638}, + timestamp = {2008-10-09T10:32:56.000+0200}, + title = {{Tracing information flow on a global scale using Internet chain-letter data}}, + volume = 105, + year = 2008 +} + +@inproceedings{Leskovec07, + author = {Jure Leskovec and + Mary McGlohon and + Christos Faloutsos and + Natalie S. Glance and + Matthew Hurst}, + title = {Patterns of Cascading Behavior in Large Blog Graphs}, + booktitle = {Proceedings of the Seventh {SIAM} International Conference on Data + Mining, April 26-28, 2007, Minneapolis, Minnesota, {USA}}, + pages = {551--556}, + year = {2007}, + timestamp = {Wed, 12 Feb 2014 17:08:15 +0100}, + bibsource = {dblp computer science bibliography, http://dblp.org} +} + + +@inproceedings{AdarA05, + author = {Eytan Adar and + Lada A. Adamic}, + title = {Tracking Information Epidemics in Blogspace}, + booktitle = {2005 {IEEE} / {WIC} / {ACM} International Conference on Web Intelligence + {(WI} 2005), 19-22 September 2005, Compiegne, France}, + pages = {207--214}, + year = {2005}, + timestamp = {Tue, 12 Aug 2014 16:59:16 +0200}, + bibsource = {dblp computer science bibliography, http://dblp.org} +} + +@inproceedings{Kleinberg:00, + author = {Jon M. Kleinberg}, + title = {The small-world phenomenon: an algorithm perspective}, + booktitle = {Proceedings of the Thirty-Second Annual {ACM} Symposium on Theory + of Computing, May 21-23, 2000, Portland, OR, {USA}}, + pages = {163--170}, + year = {2000}, + timestamp = {Thu, 16 Feb 2012 12:06:08 +0100}, + bibsource = {dblp computer science bibliography, http://dblp.org} +} + +@article{zhang2014, + title={Confidence intervals for low dimensional parameters in high dimensional + linear models}, + author={Zhang, Cun-Hui and Zhang, Stephanie S}, + journal={Journal of the Royal Statistical Society: Series B (Statistical + Methodology)}, + volume={76}, + number={1}, + pages={217--242}, + year={2014}, + publisher={Wiley Online Library} +} + +@article{javanmard2014, + title={Confidence intervals and hypothesis testing for high-dimensional + regression}, + author={Javanmard, Adel and Montanari, Andrea}, + journal={The Journal of Machine Learning Research}, + volume={15}, + number={1}, + pages={2869--2909}, + year={2014}, + publisher={JMLR. org} +} + +@article{donoho2006compressed, + title={Compressed sensing}, + author={Donoho, David L}, + journal={Information Theory, IEEE Transactions on}, + volume={52}, + number={4}, + pages={1289--1306}, + year={2006}, + publisher={IEEE} +} + +@article{candes2006near, + title={Near-optimal signal recovery from random projections: Universal + encoding strategies?}, + author={Candes, Emmanuel J and Tao, Terence}, + journal={Information Theory, IEEE Transactions on}, + volume={52}, + number={12}, + pages={5406--5425}, + year={2006}, + publisher={IEEE} +} + +@article{bickel2009simultaneous, + title={Simultaneous analysis of Lasso and Dantzig selector}, + author={Bickel, Peter J and Ritov, Ya'acov and Tsybakov, Alexandre B}, + journal={The Annals of Statistics}, + pages={1705--1732}, + year={2009}, + publisher={JSTOR} +} + +@article{bagnoli2005log, + title={Log-concave probability and its applications}, + author={Bagnoli, Mark and Bergstrom, Ted}, + journal={Economic theory}, + volume={26}, + number={2}, + pages={445--469}, + year={2005}, + publisher={Springer} +} + + |