Search

We study the low rank regression problem $\my = M\mx + \epsilon$, where $\mx$ and $\my$ are $d_1$ and $d_2$ dimensional vectors respectively. We consider the extreme high-dimensional setting where the number of observations $n$ is less than $d_1 + d_2$. Existing algorithms are designed for settings where $n$ is typically as large as $\Rank(M)(d_1+d_2)$. This work provides an efficient algorithm which only involves two SVD, and establishes statistical guarantees on its performance. The algorithm decouples the problem by first estimating the precision matrix of the features, and then solving the matrix denoising problem. To complement the upper bound, we introduce new techniques for establishing lower bounds on the performance of any algorithm for this problem. Our preliminary experiments confirm that our algorithm often out-performs existing baselines, and is always at least competitive., Comment: 36 pages

Discovering statistical structure from links is a fundamental problem in the analysis of social networks. Choosing a misspecified model, or equivalently, an incorrect inference algorithm will result in an invalid analysis or even falsely uncover patterns that are in fact artifacts of the model. This work focuses on unifying two of the most widely used link-formation models: the stochastic blockmodel (SBM) and the small world (or latent space) model (SWM). Integrating techniques from kernel learning, spectral graph theory, and nonlinear dimensionality reduction, we develop the first statistically sound polynomial-time algorithm to discover latent patterns in sparse graphs for both models. When the network comes from an SBM, the algorithm outputs a block structure. When it is from an SWM, the algorithm outputs estimates of each node's latent position., Comment: To appear in NIPS 2017

Discriminating between correct and incorrect substrates is a core process in biology but how is energy apportioned between the conflicting demands of accuracy ($\mu$), speed ($\sigma$) and total entropy production rate ($P$)? Previous studies have focussed on biochemical networks with simple structure or relied on simplifying kinetic assumptions. Here, we use the linear framework for timescale separation to analytically examine steady-state probabilities away from thermodynamic equilibrium for networks of arbitrary complexity. We also introduce a method of scaling parameters that is inspired by Hopfield's treatment of kinetic proofreading. Scaling allows asymptotic exploration of high-dimensional parameter spaces. We identify in this way a broad class of complex networks and scalings for which the quantity $\sigma\ln(\mu)/P$ remains asymptotically finite whenever accuracy improves from equilibrium, so that $\mu_{eq}/\mu \to 0$. Scalings exist, however, even for Hopfield's original network, for which $\sigma\ln(\mu)/P$ is asymptotically infinite, illustrating the parametric complexity. Outside the asymptotic regime, numerical calculations suggest that, under more restrictive parametric assumptions, networks satisfy the bound, $\sigma\ln(\mu/\mu_{eq})/P < 1$, and we discuss the biological implications for discrimination by ribosomes and DNA polymerase. The methods introduced here may be more broadly useful for analysing complex networks that implement other forms of cellular information processing.

This undergraduate thesis is concerned with developing the tools of differential geometry and semiclassical analysis needed to understand the the quantum ergodicity theorem of Schnirelman (1974), Zelditch (1987), and Colin de Verdi\`ere (1985) and the quantum unique ergodicity conjecture of Rudnick and Sarnak (1994). The former states that, on any Riemannian manifold with negative curvature or ergodic geodesic flow, the eigenfunctions of the Laplace-Beltrami operator equidistribute in phase space with density 1. Under the same assumptions, the latter states that the eigenfunctions induce a sequence of Wigner probability measures on fibers of the Hamiltonian in phase space, and these measures converge in the weak-* topology to the uniform Liouville measure. If true, the conjecture implies that such eigenfunctions equidistribute in the high-eigenvalue limit with no exceptional "scarring" patterns. This physically means that the finest details of chaotic Hamiltonian systems can never reflect their quantum-mechanical behaviors, even in the semiclassical limit. The main contribution of this thesis is to contextualize the question of quantum ergodicity and quantum unique ergodicity in an elementary analytic and geometric framework. In addition to presenting and summarizing numerous important proofs, such as Colin de Verdi\`ere's proof of the quantum ergodicity theorem, we perform graphical simulations of certain billiard flows and expositorily discuss several themes in the study of quantum chaos., Comment: 92 pages, 6 figures

We revisit the problem of predicting directional movements of stock prices based on news articles: here our algorithm uses daily articles from The Wall Street Journal to predict the closing stock prices on the same day. We propose a unified latent space model to characterize the "co-movements" between stock prices and news articles. Unlike many existing approaches, our new model is able to simultaneously leverage the correlations: (a) among stock prices, (b) among news articles, and (c) between stock prices and news articles. Thus, our model is able to make daily predictions on more than 500 stocks (most of which are not even mentioned in any news article) while having low complexity. We carry out extensive backtesting on trading strategies based on our algorithm. The result shows that our model has substantially better accuracy rate (55.7%) compared to many widely used algorithms. The return (56%) and Sharpe ratio due to a trading strategy based on our model are also much higher than baseline indices.

Motivated by recent increases in network traffic, we propose a decentralized network edge-based solution to peak-hour broadband congestion that incentivizes users to moderate their bandwidth demands to their actual needs. Our solution is centered on smart home gateways that allocate bandwidth in a two-level hierarchy: first, a gateway purchases guaranteed bandwidth from the Internet Service Provider (ISP) with virtual credits. It then self-limits its bandwidth usage and distributes the bandwidth among its apps and devices according to their relative priorities. To this end, we design a credit allocation and redistribution mechanism for the first level, and implement our gateways on commodity wireless routers for the second level. We demonstrate our system's effectiveness and practicality with theoretical analysis, simulations and experiments on real traffic. Compared to a baseline equal sharing algorithm, our solution significantly improves users' overall satisfaction and yields a fair allocation of bandwidth across users.

We study user behavior in the courses offered by a major Massive Online Open Course (MOOC) provider during the summer of 2013. Since social learning is a key element of scalable education in MOOCs and is done via online discussion forums, our main focus is in understanding forum activities. Two salient features of MOOC forum activities drive our research: 1. High decline rate: for all courses studied, the volume of discussions in the forum declines continuously throughout the duration of the course. 2. High-volume, noisy discussions: at least 30% of the courses produce new discussion threads at rates that are infeasible for students or teaching staff to read through. Furthermore, a substantial portion of the discussions are not directly course-related. We investigate factors that correlate with the decline of activity in the online discussion forums and find effective strategies to classify threads and rank their relevance. Specifically, we use linear regression models to analyze the time series of the count data for the forum activities and make a number of observations, e.g., the teaching staff's active participation in the discussion increases the discussion volume but does not slow down the decline rate. We then propose a unified generative model for the discussion threads, which allows us both to choose efficient thread classifiers and design an effective algorithm for ranking thread relevance. Our ranking algorithm is further compared against two baseline algorithms, using human evaluation from Amazon Mechanical Turk. The authors on this paper are listed in alphabetical order. For media and press coverage, please refer to us collectively, as "researchers from the EDGE Lab at Princeton University, together with collaborators at Boston University and Microsoft Corporation."

Data from Online Social Networks (OSNs) are providing analysts with an unprecedented access to public opinion on elections, news, movies etc. However, caution must be taken to determine whether and how much of the opinion extracted from OSN user data is indeed reflective of the opinion of the larger online population. In this work we study this issue in the context of movie reviews on Twitter and compare the opinion of Twitter users with that of the online population of IMDb and Rotten Tomatoes. We introduce new metrics to show that the Twitter users can be characteristically different from general users, both in their rating and their relative preference for Oscar-nominated and non-nominated movies. Additionally, we investigate whether such data can truly predict a movie's box-office success., Comment: 6 pages, 4 figures