March 2013 - talks - lists.cs.princeton.edu

Colloquium Speaker Jacob Abernethy, Tues April 2, 4:30pm
by Nicole E. Wagenblast 02 Apr '13

02 Apr '13

Learning in an Adversarial World, with Connections to Pricing, Hedging, and Routing Jacob Duncan Abernethy , University of Pennsylvania Tuesday, April 2, 2013 , 4:30pm Computer Science 105 Machine Learning is often viewed through the lens of statistics, where one tries to model or fit a set of data under stochastic conditions; for example, it is typical to assume one's observations were sampled IID. However, dating back to results of Blackwell and Hannan from the 1950s we know how to construct learning and decision strategies that possess robust guarantees even under adversarial conditions. Within this setting the goal of the learner is to "minimize regret" against any sequence of inputs. In this talk we lay out the framework, discuss some recent results, and we finish by exploring a couple of surprising applications and connections, including: (a) market making in combinatorial prediction markets, (b) routing with limited feedback, and (c) hedging derivative securities (e.g. European option contracts) in the worst-case, with a connection to the classical Black-Scholes option-pricing model. Jake received his undergraduate degree in Mathematics from MIT in 2002 and a Master's degree in Computer Science from TTI-C in 2006. He recently finished a PhD in Computer Science at UC Berkeley, advised by Peter Bartlett, and he is now the Simons Postdoctoral Fellow at University of Pennsylvania. Jake has a particular focus on the intersection between machine learning, games and markets.

1 3

Colloquium speaker, Daniel Hsu, Thurs March 28, 4:30pm
by Nicole E. Wagenblast 28 Mar '13

28 Mar '13

Fast learning algorithms for discovering the hidden structure in data Daniel Hsu , Microsoft Research New England Thursday, March 28, 2013, 4:30pm Computer Science 105 A major challenge in machine learning is to reliably and automatically discover hidden structure in data with minimal human intervention. For instance, one may be interested in understanding the stratification of a population into subgroups, the thematic make-up of a collection of documents, or the dynamical process governing a complex time series. Many of the core statistical estimation problems for these applications are, in general, provably intractable for both computational and statistical reasons; and therefore progress is made by shifting the focus to realistic instances that rule out the intractable cases. In this talk, I'll describe a general computational approach for correctly estimating a wide class of statistical models, including Gaussian mixture models, Hidden Markov models, Latent Dirichlet Allocation, Probabilistic Context Free Grammars, and several more. The key idea is to exploit the structure of low-order correlations that is present in high-dimensional data. The scope of the new approach extends beyond the purview of previous algorithms; and it leads to both new theoretical guarantees for unsupervised machine learning, as well as fast and practical algorithms for large-scale data analysis. Daniel Hsu is a postdoc at Microsoft Research New England. Previously, he was a postdoc with the Department of Statistics at Rutgers University and the Department of Statistics at the University of Pennsylvania from 2010 to 2011, supervised by Tong Zhang and Sham M. Kakade. He received his Ph.D. in Computer Science in 2010 from UC San Diego, where he was advised by Sanjoy Dasgupta; and his B.S. in Computer Science and Engineering in 2004 from UC Berkeley. His research interests are in algorithmic statistics and machine learning.

1 3

Shi Li preFPO
by Melissa M. Lawson 25 Mar '13

25 Mar '13

Shi Li will present his preFPO on Thursday March 28 at 1:30 PM in Room 401 (note room!). The members of his committee are: Moses Charikar, advisor; Mark Braverman and Julia Chuzhoy (Toyota Tech Inst), readers; Zeev Dvir and Bernard Chazelle, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ------------------------ title : Approximation Algorithms for Facility Location and Network Routing Problems abstract : My thesis is about approximation algorithms for two different classes of optimization problems. The first class is facility location problems. Two important problems in this category are uncapacitated facility location and k-median, both having long histories and numerous applications. We give improved approximation ratios for both problems. In the first part of my talk, I will focus on my recent work with Svensson (LS13) about an improved approximation algorithm for k-median. Our algorithm, which gives a 1+sqrt(3)+eps-approximation for k-median, is based on two rather surprising components. First, we show that it suffices to find an \alpha-approximate solution that contains k+O(1) medians. Second, we give such a pseudo-approximation algorithm with \alpha=1+sqrt(3)+eps. The second class is network routing problems. These are an important class of optimization problems, among which the Edge-Disjoint Paths (EDP) problem is one of the central and most extensively studied. In spite of its rich history, there is still a huge gap between the sqrt(log n)-hardness of approximation. In the second part of my talk, I will give an overview of my joint work with Chuzhoy (CL12), which gives a poly-logarithmic approximation for EDP by slightly relaxing the edge-disjointness constraint : we allow each edge in the network to be used twice (i.e, we allow congestion 2). This culminates a long line of research on the EDP with congestion problem.

1 0

Colloquium Speaker Daniel Licata Mon March 25, 4:30pm
by Nicole E. Wagenblast 25 Mar '13

25 Mar '13

Programming and Proving in Homotopy Type Theory Daniel Licata , Carnegie Mellon University & Institute for Advanced Study Monday, March 25, 2013, 4:30pm Computer Science 105 There is a strong correspondence between mathematics and programming, under which mathematical proofs correspond to programs. A _proof assistant_ is a tool that a mathematician/programmer can use to represent proofs/programs, in such a way that a computer can verify whether or not they are correct. The use of proof assistants in math and computer science is becoming ever more important for managing the increasing complexity of proofs and programs. Proof assistants have been used to check significant mathematical theorems, such as the Four Color Theorem and the Feit-Thompson Odd-Order Theorem, as well as large pieces of software, such as a C compiler and the definition of the Standard ML programming language. In this talk, I will describe my work on Homotopy Type Theory, which is a new foundation for proof assistants. Homotopy Type Theory extends type theory, the basis of several successful proof assistants, with new principles that bring it closer to informal mathematical practice. Moreover, it is based on an exciting new correspondence between type theory and the mathematical disciplines of homotopy theory and category theory, and consequently can be used to directly describe structures in these areas of math. I will describe computer-checked proofs of some basic results in algebraic topology, including calculations of homotopy groups of spheres and Eilenberg-MacLane spaces. Homotopy Type Theory is also a programming language, in which the new mathematical principles correspond to new programming techniques, which make certain programs easier to write. I will also describe my work on using Homotopy Type Theory as a programming language and its applications in computer science. Dan Licata received his PhD from Carnegie Mellon University in 2011, advised by Robert Harper. His dissertation, Dependently Typed Programming with Domain-Specific Logics, won the FoLLI E.W. Beth Dissertation Award in 2012. After graduating, he spent three semesters as a teaching fellow at Carnegie Mellon, designing and delivering a new introductory course on functional programming, parallelism, and verification. This year, he is a post-doctoral member at the Institute for Advanced Study, which is hosting a year-long program on an exciting new connection between programming languages and mathematics. His research focuses on creating better tools for computer-checked mathematics and software verification.

1 2

4:30pm Wed Apr 10 talk on NetFPGA platform in room CS 402
by Jennifer Rexford 17 Mar '13

17 Mar '13

Andrew Moore (http://www.cl.cam.ac.uk/~awm22/) from U. Cambridge will be giving a one-hour tutorial on the NetFPGA (http://netfpga.org/) platform on Wednesday April 10. If you are interested in meeting with the speaker, follow up with me at jrex(a)cs.princeton.edu. Andrew's research focuses on Internet measurement, energy-aware networks, and software-defined networking. Speaker: Andrew Moore (University of Cambridge) Title: NetFPGA: The Flexible Open-Source Networking Platform Time: 4:30pm Wednesday April 10 Place: CS 402 Abstract: The NetFPGA is an open platform enabling researchers and instructors to build high-speed, hardware-accelerated networking systems. The NetFPGA is the de-facto experimental platform for line-rate implementations of network research and it continues with a new generation platform capable of 4x10Gbps. The target audience is not restricted to hardware researchers: the NetFPGA provides the ideal platform for research across a wide range of networking topics from architecture to algorithms and from energy-efficient design to routing and forwarding. The most prominent NetFPGA success is OpenFlow, which in turn has reignited the Software Defined Networking movement. NetFPGA enabled OpenFlow by providing a widely available open-source development platform capable of line-rate and was, until its commercial uptake, the reference platform for OpenFlow. NetFPGA enables high-impact network research. This seminar will combine presentation and demonstration; no knowledge of hardware programming languages (eg Verilog/VHDL) is required. A NetFPGA 10G card will be awarded as a door-prize amongst the seminar attendees.

1 0

Colloquium Speaker Jianxiong Xiao, Wed March 13, 4:30pm
by Nicole E. Wagenblast 13 Mar '13

13 Mar '13

A 2D + 3D Rich Data Approach to Scene Understanding Jianxiong Xiao , Massachusetts Institute of Technology Wednesday, March 13, 2013, 4:30pm Computer Science 105 On your one-minute walk from the coffee machine to your desk each morning, you pass by dozens of scenes -- a kitchen, an elevator, your office -- and you effortlessly recognize them and perceive their 3D structure. But this one-minute scene-understanding problem has been an open challenge in computer vision for decades. Recently, researchers have come to realize that big data is critical for building scene-understanding systems that can recognize the semantics and reconstruct the 3D structure. In this talk, I will share my experience in leveraging big data for scene understanding, shifting the paradigm from 2D view-based categorization to 3D place-centric representations. To push the traditional 2D representation to the limit, we built the Scene Understanding (SUN) Database, a large collection of images that exhaustively spans all scene categories. However, the lack of a "rich" representation still significantly limits the traditional recognition pipeline. While an image is a 2D array, the world is 3D and our eyes see it from a viewpoint, but this is not traditionally modeled. This paradigm shift toward rich representation also opens up new challenges that require a new kind of big data -- data with extra descriptions, namely rich data. Specifically, we focus on a highly valuable kind of rich data -- multiple viewpoints in 3D -- and we build the SUN3D database to obtain an integrated "place-centric" representation of scenes. This novel representation with rich data opens up exciting new opportunities for integrating scene recognition over space and for obtaining a scene-level reconstruction of large environments. It also has many applications such as organizing big visual data to provide photo-realistic indoor 3D maps. Finally, I will discuss some open challenges and my future plans for rich data and representation. Jianxiong Xiao is a Ph.D. candidate in the Computer Science and Artificial Intelligence Laboratory (CSAIL) at Massachusetts Institute of Technology (MIT). Before that, he received a B.Eng. and a M.Phil. from the Hong Kong University of Science and Technology. His research interests are in computer vision, with a focus on scene understanding. His work has received the Best Student Paper Award at the European Conference on Computer Vision (ECCV) in 2012, and has appeared in popular press. Jianxiong was awarded the Google U.S./Canada Ph.D. Fellowship in Computer Vision in 2012 and MIT CSW Best Research Award in 2011. More information can be found on his website: http://mit.edu/jxiao .

1 3

Colloquium Speaker Anshul Kundaje Tues March 12, 4:30pm
by Nicole E. Wagenblast 12 Mar '13

12 Mar '13

Unraveling the heterogeneity and dynamics of regulatory elements in the human genome Anshul Kundaje , Massachusetts Institute of Technology Tuesday, March 12, 2013, 4:30pm Computer Science 105 In 2003, the Human Genome Project marked a major scientific milestone by releasing the first consensus DNA sequence of the human genome. The ENCODE Project (Encyclopedia of DNA elements) was launched to pick up where the Human Genome Project left off, with the ambitious goal of systematically deciphering the potential function of every base (letter) in the genome. ENCODE has generated the largest collection of functional genomic data in humans to date, measuring the cellular activity of thousands of cellular moieties in a variety of normal and diseased cellular contexts. In this talk, I will describe novel computational and machine learning approaches that I developed for integrative analysis of massive compendia of diverse biological data such as ENCODE to unravel the functional heterogeneity and variation of regulatory elements in the human genome and their implications in human disease. I will begin with a gentle introduction to the diversity and scale of ENCODE data and a brief overview of robust, statistical methods that we developed for automated detection of DNA binding sites of hundreds of regulatory proteins from noisy, experimental data. Regulatory proteins can perform multiple functions by interacting with and co-binding DNA with different combinations of other regulatory proteins. I developed a novel discriminative machine learning formulation based on regularized Rule-based ensembles that was able to sort through the combinatorial complexity of possible regulatory interactions and learn statistically significant item-sets of co-binding events at an unprecedented level of detail. I found extensive evidence that regulatory proteins could switch partners at different sets of genomic domains within a single cell-type and across different cell-types affecting structural and chemical properties of DNA and regulating different functional categories of target genes. Using regulatory elements discovered from ENCODE data, we were also able to provide putative functional interpretations for up to 81% of all publicly available sequence variants (mutations) identified in large-scale disease studies and generate new hypotheses by integrating multiple sources of data. Finally, I will present a brief overview of my recent efforts on using multivariate Hidden Markov models to analyze the dynamics of various chemical modifications to DNA across three key axes of variation - across multiple species, across different cell-types in a single species (human), and across multiple human individuals for the same cell-type. Our results indicate a remarkable universality of chemical modifications defining hidden regulatory states across the animal kingdom with dramatic differences in the variation and functional impact of these regulatory elements between cell-types and individuals. Together, these efforts take us one step closer to learning comprehensive models of gene regulation in humans in order to improve our system-level understanding of cellular processes and complex diseases.

1 3

Colloquium speaker Aditya Parameswaran, Mon March 12, 4:30pm
by Nicole E. Wagenblast 11 Mar '13

11 Mar '13

Human-Powered Data Management Aditya Parameswaran , Stanford University Monday, March 12, 2013, 4:30pm Computer Science 105 Fully automated algorithms are inadequate for a number of data analysis tasks, especially those involving images, video, or text. Thus, there is a need to combine “human computation” (or crowdsourcing), together with traditional computation, in order to improve the process of understanding and analyzing data. My thesis addresses several topics in the general area of human-powered data management. I design algorithms and systems for combining human and traditional computation for: (a) data processing, e.g., using humans to help sort, cluster, or clean data; (b) data extraction, e.g., having humans help create structured data from information in unstructured web pages; and (c) data gathering, i.e., asking humans to provide data that they know about or can locate, but that would be difficult to gather automatically. My focus in all of these areas is to find solutions that expend as few resources as possible (e.g., time waiting, human effort, or money spent), while still providing high quality results. In this talk, I will first present a broad perspective of our research on human-powered data management, and I will describe some systems and applications that have motivated our research. I will then present details of one of the problems we have addressed: filtering large data sets with the aid of humans. Finally I will argue that human-powered data management is an area in its infancy, by describing a number of open problems I intend to address in my future research program. Aditya Parameswaran is a Ph.D. student in the InfoLab at Stanford University, advised by Prof. Hector Garcia-Molina. He is broadly interested in data management, with research results in human computation, information extraction, and recommendation systems. Aditya is a recipient of the Key Scientific Challenges Award from Yahoo! Research (2010), two best-of-conference citations (VLDB 2010 and KDD 2012), and the Terry Groswith graduate fellowship at Stanford University.

1 3

S Sachdeva preFPO
by Melissa M. Lawson 07 Mar '13

07 Mar '13

Sushant Sachdeva will present his preFPO on Tuesday March 12 at 11AM in Room 302 (note room!). The members of his committee are: Sanjeev Arora, advisor; Moses Charikar and Nisheeth Vishnoi (MSR India) readers; Beranrd Chazelle and Mark Braverman, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ============================================== New Results in Graph Partitioning and Optimal Inapproximability sans UGC This thesis consists of two parts. The first part contains improved algorithms for graph partitioning problems, both for well-studied classical problems (Balanced Separator) and for more practically motivated problems (Identifying Communities). The second part contains new results towards achieving optimal inapproximability results without assuming the Unique Games Conjecture. A. Graph Partitioning We give the first near-linear time algorithm for Balanced Separator with the best possible guarantee for spectral algorithms. The algorithm combines SDP rounding techniques with continuous time random walks on the graph. We show how to approximate these walks, or equivalently, the matrix exponential e^{-tL}, where L is the graph Laplacian, in near-linear time, by combining techniques from approximation theory and numerical linear algebra. We give a novel approach to the problem of identifying communities in a graph representing a social network. We model the network as being described by overlapping communities with certain local structure; and under these assumptions, we provably and efficiently recover the underlying communities. B. Optimal Inapproximability without assuming UGC We study the inapproximability of some classic scheduling problems viz. Concurrent Open Shop and the Assembly Line problem, and prove an optimal 2-inapproximability for both problems assuming P != NP. Previously, the best NP-hardness factors known were 6/5 and 1+eps respectively. We also study the inapproximability of Hypergraph Vertex Cover on k-uniform k-partite hypergraphs, and prove a nearly optimal NP-hardness of approximating it within k/2-1, where a k/2-approximation is known due to Lovász. The results in this talk are based on joint works with Sanjeev Arora, Rong Ge, Lorenzo Orecchia, Rishi Saket, Grant Schoenebeck, Madhur Tulsiani, and Nisheeth K. Vishnoi.

1 0

R Ge preFPO
by Melissa M. Lawson 06 Mar '13

06 Mar '13

Rong Ge will present his preFPO on Monday March 11 at Noon in Room 401 (note room!) The members of his committee are: Sanjeev Arora, advisor; Moses Charikar and Sham Kakade (MSR New England), readers; Mark Braverman and Zeev Dvir, nonreaders. Everyone is invited to attend his talk. His abstract follows below. --------------------------- Title: Provable Algorithms for Machine Learning Many tasks in machine learning are computationally intractable. Nevertheless, researchers have developed heuristic algorithms that successfully solve these problems in practice. This phenomena can be explained using average case complexity. However, in many situations the details supporting this explanation are still missing: what properties of the input make it possible to be solved efficiently? What is the chance that real-life inputs satisfy these properties and how robust is the algorithm if they don't? In this talk I use topic modeling as an example to show our attempts of answering these problems. The first part of the talk gives a new algorithm for learning topic models with provable guarantees. This algorithm relies on a reasonable simplifying assumption, and runs 20 times faster than existing software like mallet with comparable output quality. The second part of the talk gives a new analysis for method of moments algorithms (AHK12, AFHKL12) using tensor decomposition. The new algorithm has a better perturbation analysis and can therefore tolerate more modeling error.

1 0