- talks - lists.cs.princeton.edu

Colloquium Speaker Alekh Agarwal TuesFeb 28, 4:30pm
by Nicole E. Wagenblast 22 Feb '12

22 Feb '12

Computation meet Statistics: Trade-offs and fundamental limits Alekh Agarwal , University of California, Berkeley Tuesday, February 28, 2012 , 4:30 PM Computer Science Small Auditorium (Room 105) The past decade has seen the emergence of datasets of an unprecedented scale, with both large sample sizes and dimensionality. Massive data sets arise in various domains, among them computer vision, natural language processing, computational biology, social networks analysis and recommendation systems, to name a few. In many such problems, the bottleneck is not just the number of data samples, but also the computational resources available to process the data. Thus, a fundamental goal in these problems is to characterize how estimation error behaves as a function of the sample size, number of parameters, and the computational budget available. In this talk, I present two research threads that provide complementary lines of attack on this broader research agenda: lower bounds for statistical estimation with computational constraints, and (ii) distributed algorithms for statistical inference. The first characterizes fundamental limits in a uniform sense over all methods, whereas the latter provides explicit algorithms that exploits the interaction of computational and statistical considerations in a distributed computing environment. [Joint work with John Duchi, Pradeep Ravikumar, Peter Bartlett and Martin Wainwright] Alekh Agarwal is a fifth year PhD student at UC Berkeley, jointly advised by Peter Bartlett and Martin Wainwright. Alekh has received PhD fellowships from Microsoft Research and Google. His main research interests are in the areas of machine learning, convex optimization, high-dimensional statistics, distributed machine learning and understanding the computational trade-offs in machine learning problems.

1 0

Colloquium Speaker Michael Bernstein Wed Feb 22 4:30pm
by Nicole E. Wagenblast 21 Feb '12

21 Feb '12

Crowd-Powered Systems Michael Bernstein , MIT Wednesday, February 22, 2012 , 4:30 PM - 5:30 PM Computer Science Small Auditorium (Room 105) Crowd-powered systems combine computation with human intelligence, drawn from large groups of people connecting and coordinating online. These hybrid systems enable applications and experiences that neither crowds nor computation could support alone. Unfortunately, crowd work is error-prone and slow, making it difficult to incorporate crowds as first-order building blocks in software systems. I introduce computational techniques that decompose complex tasks into simpler, verifiable steps to improve quality, and optimize work to return results in seconds. These techniques advance crowdsourcing into a platform that is reliable and responsive to the point where crowds can be used in interactive systems. In this talk, I will present two crowd-powered systems to illustrate these ideas. The first, Soylent, is a word processor that uses paid micro-contributions to aid writing tasks such as text shortening and proofreading. Using Soylent is like having access to an entire editorial staff as you write. The second system, Adrenaline, is a camera that uses crowds to help amateur photographers capture the exact right moment for a photo. It finds the best smile and catches subjects in mid-air jumps, all in realtime. These systems point to a future where social and crowd intelligence are central elements of interaction, software, and computation. Michael Bernstein is a PhD candidate in Computer Science at the Massachusetts Institute of Technology. His research in human-computer interaction focuses on crowdsourcing and social computing systems. He has been awarded Best Student Paper at UIST 2010, Best Paper at ICWSM 2011, the NSF graduate research fellowship and the Microsoft Research PhD fellowship. His work has appeared in venues like the New York Times, Slate, CNN and The Atlantic. He earned his masters in Computer Science at MIT, and a bachelors degree in Symbolic Systems at Stanford University.

1 1

Colloquium Speaker Ohad Shamir Tues Feb 21 4:30pm
by Nicole E. Wagenblast 17 Feb '12

17 Feb '12

Machine Learning: Higher, Faster, Stronger Ohad Shamir , Microsoft Research New England Computer Science Small Auditorium (Room 105) Tuesday, February 21, 2012 , 4:30 PM - 5:30 PM Over the past decade, machine learning has emerged as a major and highly influential discipline of computer science and engineering. As the scope and variety of its applications increase, it faces novel and increasingly challenging settings, which go beyond classical learning frameworks. In this talk, I will present two recent works which fall under this category. The first work introduces a new model of sequential decision making with partial information. The model interpolates between two well-known online learning settings ("experts" and multi-armed bandits), and trades-off between the information obtained per round and the total number of rounds required to reach the same performance. The second work discusses the problem of parallelizing gradient-based learning algorithms, which is increasingly important for web-scale applications, but is highly non-trivial as these algorithms are inherently sequential. We show how this can be done using a generic and simple protocol, prove its theoretical optimality, and substantiate its performance experimentally on large-scale data. Ohad Shamir is a postdoctoral researcher at Microsoft Research New England. He joined Microsoft in 2010 after receiving a Ph.D. in computer science from the Hebrew university, advised by Prof. Naftali Tishby. His research focuses on machine learning, with emphasis on novel algorithms which combine practical applicability and theoretical insight. His work was recognized by several awards, such as the Hebrew University's Schlomiuk Ph.D. thesis prize, the COLT 2010 best paper award, and the Wolf foundation scholarship.

1 0

B Kapicioglu preFPO
by Melissa M. Lawson 16 Feb '12

16 Feb '12

Berk Kapicioglu will present his preFPO on Wednesday February 22 at 11AM in Room 402. The members of his committee are: Rob Schapire, advisor; David Blei and Tony Jebara (Columbia), readers; Jennifer Rexford and Andrea LaPaugh, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ----- Original Message ----- Title: Applications of Machine Learning to Location Data. Abstract: First, we introduce a new graphical model for tracking radio-tagged animals and learning their movement patterns. The model provides a principled way to combine radio telemetry data with an arbitrary set of user-deﬁned, spatial features. We describe an efﬁcient stochastic gradient algorithm for ﬁtting model parameters to data and demonstrate its eﬀectiveness via asymptotic analysis and synthetic experiments. We also apply our model to real datasets, and show that it outperforms the most popular radio telemetry software package used in ecology. We conclude that integration of different data sources under a single statistical framework, coupled with appropriate parameter and state estimation procedures, produces both accurate location estimates and an interpretable statistical model of animal movement. Second, we present the “Place Discovery” problem, where the goal is to provide a context-dependent and personalized ranking of nearby places. To the best of our knowledge, we are the first to pose this as a machine learning problem. We provide a new matrix approximation algorithm that leverages implicit bipartite ranking and spatial constraints. We demonstrate on real location datasets that our methods significantly improve on the amount of personalization achieved by state-of-the-art matrix approximation methods, such as Maximum-Margin Matrix Factorization. Lastly, we talk about “Location Prediction”. Here, the goal is to predict the coordinates (i.e. latitude and longitude) of a user at an arbitrary time in the future. We design an unsupervised hierarchical Bayesian graphical model for location prediction that learns natural topics such as home and work from unlabeled location data. We apply our model both to data gathered from mobile applications, where there are many users but each user has sparse location points, and to data gathered from cellular carriers. Our model outperforms existing methods in both cases.

1 0

P Jiang preFPO
by Melissa M. Lawson 13 Feb '12

13 Feb '12

Peng Jiang will present his preFPO on Friday February 17 at Noon in Lewis Thomas Lab 118 (note location). The members of his committee are: Mona Singh, advisor; Hilary Coller (MOL) and Olga Troyanskaya, readers; Leonid Kruuglyak (Genomics) and Bernard Chazelle, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ----- Original Message ----- Title: Computational Analysis of Transcriptional and post-Transcriptional regulation Abstract: Transcription factors (TFs) and miRNAs are regulators for a wide range of biological processes. While binding speciﬁcities for numerous D. melanogaster TFs have been experimentally determined, the genomic binding targets for the majority of them are unknown, with even less known about the transcriptional regulators of miRNAs and the network-level interplay between TFs and miRNAs. We computationally constructed a large-scale transcriptional regulatory network for D. melanogaster. Based on several lines of experimental data, we annotated the transcription start sites for 37 integenic miRNAs. We uncovered conserved binding sites for TFs with known speciﬁcities in promoters of miRNAs and protein-coding genes. The inferred D. melanogaster transcriptional network is the largest to date, and consists of regulatory targets for 267 TFs, covering 56 intergenic miRNA loci and 11,232 protein-coding genes. Using this network, we predicted GO biological processes for miRNAs based upon their upstream regulators and downstream targets. Finally, we found that the network exhibits a surprisingly diverse array of network motifs consisting of both miRNAs and TFs. On the level of post-Transcriptional regulation, transcript degradation is a widespread and important mechanism for regulating protein abundance. Two major regulators of transcript degradation are RNA Binding Proteins (RBPs) and microRNAs (miRNAs). We computationally explored whether RBPs and miRNAs cooperate to promote transcript decay. We defined five RBP motifs based on the evolutionary conservation of their recognition sites in 3' UTRs as the binding motifs for Pumilio (PUM), U1A, Fox-1, Nova, and AU-rich element (ARE) binding proteins. Recognition sites for some of these RBPs tended to localize at the beginning or end of 3' UTRs. A specific group of miRNA recognition sites were enriched within 50 nts upstream and downstream of the RBP recognition sites of PUM, ARE, Fox-1 and U1A. The presence of both a PUM recognition site and a recognition site for preferentially co-occurring miRNAs was associated with faster decay of the associated transcripts. For PUM and its co-occurring miRNAs, binding of the RBP to its recognition sites was predicted to rescue nucleotides within nearby miRNA recognition sites from hybridization with other nucleotides at a higher rate than expected. miRNAs that preferentially co-occur with PUM binding sites tended to have recognition sites that are reverse complements to the PUM recognition motif. These sites have the potential to form hairpin secondary structures that would normally limit RISC accessibility, but would be more accessible to miRNAs in response to the binding of PUM. In sum, our computational analyses suggest that PUM can coordinately fine-tune the accessibility of multiple microRNA recognition sites.

1 0

11am Tue Feb 7 talk on distributed streaming algorithms
by Jennifer Rexford 07 Feb '12

07 Feb '12

Speaker: Zhenming Liu, Harvard Title: Continuous Distributed Counting for Non-monotonic Streams Date/time: 11am-noon, Tuesday February 7 Location: room 302 in the CS building Abstract: We consider the problem of tracking a sum of values in a distributed environment where the input values arrive from k distributed streams. It is required that an estimate of the sum is maintained by a coordinator node that is within a prescribed relative error tolerance, at any time with high probability. The goal is to achieve such objective with small total communication with the coordinator node, in order to minimize the use of network bandwidth that may be a scarce resource. This is a basic distributed computation problem that is of interest for various applications including data aggregation and iterative solving of various computational problems. Specifically, we consider a setting where the input values are selected and assigned to sites by an adversary but the arrival order of the input items is random. We show a randomized protocol with a sub-linear total communication with respect to the number of updates and its matching lower bound. This result stands in between the previously known results that for monotonic partial sums (all value updates either positive or negative), the expected total communication is logarithmic in the number of updates, and that for general worst-case inputs, the total required communication is linear in the number of updates. Finally, we also discuss applications of the sum tracking module for tracking the second frequency moment and for solving a Bayesian linear regression. Bio: Zhenmin Liu is a PhD candidate in the theory of computation group at Harvard, working with Michael Mitzenmacher. His research focuses on stochastic processes, optimization, and algorithm design, as well as their applications to distributed computation and big data analytics.

1 0

W Jiang FPO
by Melissa M. Lawson 06 Feb '12

06 Feb '12

Joe Wenjie Jiang will present his FPO on thursday February 9 at 1:15PM in Room 402. The members of his committee are: Jennifer Rexford, advisor. Mung Chiang co-advisor; Andrea LaPaugh and Augustin Chaintreau (Columbia) readers; Michael Freedman and Mung Chiang, nonreaders. A copy of his thesis, "Wide-Area Traffic Management for Cloud Services", is on display in Room 310. Everyone is invited to attend his talk.

1 0

Colloquium speaker Tim Roughgarden Wed Feb 8, 4:30pm
by Nicole E. Wagenblast 03 Feb '12

03 Feb '12

Porting the Computer Science Toolbox to Game Theory and Economics Tim Roughgarden , Stanford University Wednesday, February 8, 2012 , 4:30 PM - 5:30 PM Computer Science Small Auditorium (Room 105) Theoretical computer science has brought new ideas and techniques to game and economic theory. A primary signature of the computer science approach is {em approximation} --- the idea of building credibility for a proposed solution by proving that its performance is always within a small factor of an ideal (and typically unimplementable) solution. We explain two of our recent contributions in this area, one motivated by networks and one by auctions. We first discuss the "price of anarchy": how well does decentralized (or "selfish") behavior approximates centralized optimization? This concept has been analyzed in many applications, including network routing, resource allocation, network formation, health care, and even models of basketball. We highlight a new theory of robust price of anarchy bounds, which apply even to systems that are not in equilibrium. Second, we consider auction design: for example, what selling procedure should be used to maximize the revenue of a seller? On the analysis side, we highlight a new framework that explicitly connects average-case (i.e., Bayesian) analysis, the dominant paradigm in economics, with the worst-case analysis approach common in computer science. On the design side, we provide a distribution-independent auction that performs, for a wide class of input distributions, almost as well as the distribution-specific optimal auction. Tim Roughgarden received his Ph.D. from Cornell University in 2002 and joined the Stanford CS department in 2004, where he is currently an associate professor. His research interests are in theoretical computer science, especially its interfaces with game theory and networks. He wrote the book "Selfish Routing and the Price of Anarchy" (MIT Press, 2005) and co-edited the book "Algorithmic Game Theory", with Nisan, Tardos, and Vazirani (Cambridge, 2007). His significant awards include the 2002 ACM Doctoral Dissertation Award (Honorable Mention), the 2003 Tucker Prize, the 2003 INFORMS Optimization Prize for Young Researchers, speaking at the 2006 International Congress of Mathematicians, a 2007 PECASE Award, the 2008 Shapley Lectureship of the Game Theory Society, and the 2009 ACM Grace Murray Hopper Award. He's currently developing a free online course on the design and analysis of algorithms, which has over 50,000 students.

1 0

11am Tue Feb 7 talk on distributed streaming algorithms
by Jennifer Rexford 01 Feb '12

01 Feb '12

Speaker: Zhenming Liu, Harvard Title: Continuous Distributed Counting for Non-monotonic Streams Date/time: 11am-noon, Tuesday February 7 Location: room 302 in the CS building Abstract: We consider the problem of tracking a sum of values in a distributed environment where the input values arrive from k distributed streams. It is required that an estimate of the sum is maintained by a coordinator node that is within a prescribed relative error tolerance, at any time with high probability. The goal is to achieve such objective with small total communication with the coordinator node, in order to minimize the use of network bandwidth that may be a scarce resource. This is a basic distributed computation problem that is of interest for various applications including data aggregation and iterative solving of various computational problems. Specifically, we consider a setting where the input values are selected and assigned to sites by an adversary but the arrival order of the input items is random. We show a randomized protocol with a sub-linear total communication with respect to the number of updates and its matching lower bound. This result stands in between the previously known results that for monotonic partial sums (all value updates either positive or negative), the expected total communication is logarithmic in the number of updates, and that for general worst-case inputs, the total required communication is linear in the number of updates. Finally, we also discuss applications of the sum tracking module for tracking the second frequency moment and for solving a Bayesian linear regression. Bio: Zhenmin Liu is a PhD candidate in the theory of computation group at Harvard, working with Michael Mitzenmacher. His research focuses on stochastic processes, optimization, and algorithm design, as well as their applications to distributed computation and big data analytics.

1 0

11am Wed Jan 18 talk on information-centric networking
by Jennifer Rexford 14 Jan '12

14 Jan '12

Speaker: Yan Shvartzshnaider, NICTA Title: A Case for a Global Information Network Date/time: 11am-noon Wed Jan 18 Location: CS 302 Abstract There is an ever increasing gap between how the “common man” would describe the Internet and how a network researcher would. This is not surprising, as the “packet with a label identifying the receiver” model seems to be an ill fitting abstraction for popular services provided by companies such as Google, Facebook, YouTube, or Twitter. These services are primarily about information dissemination and a suitable network service abstraction should really do more than deliver individual packets with minimal latency. We argue that we should adopt an information-centric system model instead of the current service oriented one. Instead of dealing with information exchange between specific services on a case by case bases, we should instead consider a global information storage and dissemination network on which individual applications and services are built. In this talk I will discuss our vision the future architecture and give a brief overview on our progress so far. Bio: Yan Shvartzshnaider is a PhD Candidate in the school of Engineering and Information Technologies in the University of Sydney and a graduate researcher in National ICT Australia (NICTA), Networking Group in ATP lab. His research focus is on large scale networking systems, in particular, developing a fully distributed information-centric networking abstraction.

1 0