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

Colloquium Speaker Yin-Tat Lee, Tuesday April 5th- 12:30pm
by Mitra D. Kelly 31 Mar '16

31 Mar '16

Colloquium Speaker Yin-Tat Lee, Massachusetts Institute of Technology April 5th, 12:30 Computer Science 105 Title: Faster algorithms for fundamental convex problems and their applications in combinatorial optimization Abstract: Convex optimization has been studied extensively and is a prominent tool in various areas such as combinatorial optimization, data analysis, operations research, and scientific computing. Each field has developed specialized tools including data structures, sampling methods, and dimension reduction. In the past several years, I have been combining and improving the optimization techniques from different fields to design faster optimization algorithms. In this talk, I will discuss my work in this direction and illustrate it through my results on linear programming and general convex optimization. In particular, I will present a new algorithm for solving linear programs, which gives the first improvement to the running time for linear programming in 25 years. Then, I will present the first nearly cubic time algorithm for solving general convex optimization problems. Furthermore, I will discuss how these two results can be used to improve the running time of many classical combinatorial problems such as maximum flow and submodular function minimization. This talk will assume no prior knowledge of optimization. Bio: Yin Tat Lee is a Ph.D. candidate in the department of mathematics at the Massachusetts Institute of Technology. He is interested in designing faster algorithms, particularly for problems in optimization. Since he began his Ph.D. in 2012, he has combined ideas from continuous and discrete mathematics to substantially advance the state-of-the-art for solving many fundamental problems in computer science, such as linear programming, maximum flow, and submodular function minimization. He has received a variety of awards, including the Best Student Paper Award at FOCS 2015, Best Paper Award at SODA 2014, Best Paper Award and Best Student Paper Award at FOCS 2014, and Notable Article in Computing in 2014 by Computing Reviews. Mitra Kelly Academic Secretary Princeton University Computer Science Dept 35 Olden Street Princeton NJ 08540 mkelly(a)cs.princeton.edu <mailto:mkelly@cs.princeton.edu> 609-258-4562

1 0

Colloquium Speaker Philipp Kräehenbüehl, Monday April 4, 12:30pm
by Nicole E. Wagenblast 31 Mar '16

31 Mar '16

Colloquium Speaker Philipp Kräehenbüehl, University of California, Berkeley Monday, April 4, 2016 - 12:30pm Computer Science 105 The many ways to understand the pixels The field of computer vision is arguably seeing one of its most transformative changes in recent history. Convolutional neural networks (CNNs) have revolutionized the field, reaching super-human performance on some long-standing computer vision tasks, such as image classification. The success of these networks is fueled by massive amounts of human-labeled data. However this paradigm does not scale to a deeper and more detailed understanding of images, as it is simply too hard to collect enough human-labeled data. The issue is not that we humans don't understand the image, but we often struggle to convey enough information to successfully supervise a vision system. In this talk I show how computer vision can go beyond massive human supervision. This involves designing better models that deal with fewer labels, exploiting easier and more intuitive annotations, or coming up with novel optimizations to train deep architectures with far fewer human annotations, or even without any at all. I'll focus on three long standing computer vision problems: semantic segmentation, intrinsic image decomposition and dense semantic correspondences. Philipp Krähenbühl is a postdoctoral researcher at UC Berkeley. He received a B.S. in Computer Science from ETH Zurich in 2009, and a PhD in Computer Science from Stanford University in 2014. Philipp's research interests lie in Computer vision, Machine learning and Computer Graphics. He is particularly interested in deep learning, efficient optimization techniques, and structured output prediction.

1 0

Subject: Colloquium Speaker Roger Grosse, Thursday April 7th- 12:30pm
by Mitra D. Kelly 31 Mar '16

31 Mar '16

Colloquium Speaker Roger Grosse, the University of Toronto April 7th- 12:30pm Computer Science 105 Exploiting compositionality to explore a large space of model structures I will present flexible algorithms for model discovery and model fitting which apply to broad, open-ended classes of models, yet which also incorporate model-specific algorithmic insights. First, I will introduce a framework for building probabilistic models compositionally out of common modeling motifs, such as clustering, sparsity, and dimensionality reduction. This compositional framework yields a variety of existing models as special cases. We can flexibly perform posterior inference across this large, open-ended space of models by composing sophisticated inference algorithms carefully designed for the individual modeling motifs. An automatic structure search procedure over this space of models yields sensible analyses of datasets as diverse as motion capture, natural image patches, and Senate voting records, all using a single software package with no hand-tuned metaparameters. Applying a similar compositional structure search procedure to Gaussian Process models yields interpretable decompositions of diverse time series datasets and enables automatic generation of natural language reports. Finally, compositional structure search depends crucially on the estimation of intractable likelihoods. I will briefly outline an approach for obtaining precise likelihood estimates with rigorous tail bounds by sandwiching the true value between stochastic upper and lower bounds. BIO: Roger Grosse is a Postdoctoral Fellow in the University of Toronto machine learning group. He received his Ph.D. in computer science from MIT under the supervision of of Bill Freeman. He is a recipient of the NDSEG Graduate Fellowship, the Banting Postdoctoral Fellowship, and outstanding paper awards at the International Conference of Machine Learning (ICML) and the Conference for Uncertainty in AI (UAI). He is also a co-creator of Metacademy, an open-source web site for developing personalized learning plans in machine learning and related fields. Mitra Kelly Academic Secretary Princeton University Computer Science Dept 35 Olden Street Princeton NJ 08540 mkelly(a)cs.princeton.edu <mailto:mkelly@cs.princeton.edu> 609-258-4562

1 0

Colloquium Speaker, Matt Weinberg Today, 12:30pm
by Nicole E. Wagenblast 31 Mar '16

31 Mar '16

Colloquium Speaker Matt Weinberg, Princeton University Thursday, March 31, 2016 - 12:30pm Computer Science 105 Algorithms for Strategic Agents When real people interact with algorithms (e.g. in auctions, crowdsourcing, Bitcoin, etc.), they impose additional objectives beyond simply that the algorithm is correct, fast, and uses little storage. People strategize during these interactions, so algorithms deployed in these settings must be robust against potential manipulation. Additionally, people prefer transparent interactions, so these algorithms must also be as simple as possible. My research addresses these, and other novel challenges that arise when algorithms interact with strategic agents. In this talk, I will focus on one aspect of this agenda and present a new algorithmic framework to solve any optimization problem in a way that is robust to strategic manipulation. I will further apply this framework to extend Myerson's celebrated characterization of optimal single-item auctions to multiple items (Myerson 1981), design mechanisms for job scheduling (Nisan and Ronen 1999), and resolve other problems at the interface of algorithms and game theory. Finally, I will briefly show how strategic considerations motivate nice questions in "traditional" areas of algorithm design as well, and present some of my work in online algorithms, convex optimization, and parallel algorithms. Matt received his PhD in EECS from MIT in 2014, where he was advised by Costis Daskalakis. He is now a postdoc at Princeton University in the Computer Science department. His research focuses on designing algorithms that address constraints imposed by the strategic nature of people that interact with them. For his thesis work on this topic, he received MIT's George M. Sprowls award and the SIGecom Doctoral Dissertation award. Matt received his B.A. in Math from Cornell University.

1 0

Colloquium Speaker, Matt Weinberg Thursday, March 31, 12:30pm- reminder
by Nicole E. Wagenblast 30 Mar '16

30 Mar '16

Colloquium Speaker Matt Weinberg, Princeton University Thursday, March 31, 2016 - 12:30pm Computer Science 105 Algorithms for Strategic Agents When real people interact with algorithms (e.g. in auctions, crowdsourcing, Bitcoin, etc.), they impose additional objectives beyond simply that the algorithm is correct, fast, and uses little storage. People strategize during these interactions, so algorithms deployed in these settings must be robust against potential manipulation. Additionally, people prefer transparent interactions, so these algorithms must also be as simple as possible. My research addresses these, and other novel challenges that arise when algorithms interact with strategic agents. In this talk, I will focus on one aspect of this agenda and present a new algorithmic framework to solve any optimization problem in a way that is robust to strategic manipulation. I will further apply this framework to extend Myerson's celebrated characterization of optimal single-item auctions to multiple items (Myerson 1981), design mechanisms for job scheduling (Nisan and Ronen 1999), and resolve other problems at the interface of algorithms and game theory. Finally, I will briefly show how strategic considerations motivate nice questions in "traditional" areas of algorithm design as well, and present some of my work in online algorithms, convex optimization, and parallel algorithms. Matt received his PhD in EECS from MIT in 2014, where he was advised by Costis Daskalakis. He is now a postdoc at Princeton University in the Computer Science department. His research focuses on designing algorithms that address constraints imposed by the strategic nature of people that interact with them. For his thesis work on this topic, he received MIT's George M. Sprowls award and the SIGecom Doctoral Dissertation award. Matt received his B.A. in Math from Cornell University.

1 0

Colloquium Speaker: Joel Tropp, Today- 12:30pm
by Nicole E. Wagenblast 29 Mar '16

29 Mar '16

Colloquium Speaker Joel Tropp, California Institute of Technology Tuesday, March 29, 12:30pm Computer Science 105 Finding structure with randomness Computer scientists have long known that randomness can be used to improve the performance of algorithms. A familiar application is the process of dimension reduction, in which a random map transports data from a high-dimensional space to a lower-dimensional space while approximately preserving some geometric properties. By operating with the compact representation of the data, it is possible to produce approximate solutions to certain large problems very efficiently. It has been observed that dimension reduction has powerful applications in numerical linear algebra and numerical analysis. This talk will discuss randomized techniques for constructing standard matrix factorizations, such as the truncated singular value decomposition. In practice, the algorithms are so effective that they compete with—or even outperform—classical algorithms. These methods are already making a significant impact in large-scale scientific computing and learning systems. Joint work with P.-G. Martinsson and N. Halko.

1 0

Colloquium Speaker Stephanie Mueller, TODAY at 12:30pm. March 28th
by Mitra D. Kelly 28 Mar '16

28 Mar '16

Colloquium Speaker Stephanie Mueller, Human-Computer Interaction Lab at Hasso Plattner Institute March 28, 12:30pm Computer Science 105 Talk Title: Interacting with Personal Fabrication Machines In anticipation of 3D printers reaching millions of users, I am investigating how to allow future users to interact with the new hardware. I present a series of interactive software+hardware systems that I created to answer this question. They are characterized by two main properties. First, they produce physical output quickly, allowing users not only to see their results, but also to touch and test their mechanical properties as users work towards a solution. Second, the systems allow users to interact directly with the workpiece, i.e., rather than using a digital 3D editor, users manipulate the workpiece located inside the 3D printer by pointing at it, causing the machine to then modify the workpiece accordingly. I put my research into perspective by drawing analogies to the evolution of interactive computing from batch processing, to turn taking, to direct manipulation. Bio: Stefanie Mueller is a PhD student working with Patrick Baudisch at the Human-Computer Interaction Lab at Hasso Plattner Institute. In her research, she develops novel hardware and software systems that advance personal fabrication technologies. Stefanie has published 10 papers at the most selective HCI venues CHI and UIST, for which she received a best paper award and two best paper nominees. She is also serving on the CHI and UIST program committees as an associate chair. In addition, Stefanie has been an invited speaker at universities and research labs, such as MIT, Stanford, UC Berkeley, Microsoft Research, Disney Research, and Adobe Research. Mitra Kelly Academic Secretary Princeton University Computer Science Dept 35 Olden Street Princeton NJ 08540 mkelly(a)cs.princeton.edu <mailto:mkelly@cs.princeton.edu> 609-258-4562

1 0

Topic Change: Colloquium Speaker: Joel Tropp, Tuesday, March 29- 12:30pm
by Nicole E. Wagenblast 28 Mar '16

28 Mar '16

Colloquium Speaker Joel Tropp, California Institute of Technology Tuesday, March 29, 12:30pm Computer Science 105 Finding structure with randomness Computer scientists have long known that randomness can be used to improve the performance of algorithms. A familiar application is the process of dimension reduction, in which a random map transports data from a high-dimensional space to a lower-dimensional space while approximately preserving some geometric properties. By operating with the compact representation of the data, it is possible to produce approximate solutions to certain large problems very efficiently. It has been observed that dimension reduction has powerful applications in numerical linear algebra and numerical analysis. This talk will discuss randomized techniques for constructing standard matrix factorizations, such as the truncated singular value decomposition. In practice, the algorithms are so effective that they compete with—or even outperform—classical algorithms. These methods are already making a significant impact in large-scale scientific computing and learning systems. Joint work with P.-G. Martinsson and N. Halko.

1 0

Colloquium Speaker: Joel Tropp, Tuesday, March 29- 12:30pm- reminder
by Nicole E. Wagenblast 28 Mar '16

28 Mar '16

Colloquium Speaker Joel Tropp, California Institute of Technology Tuesday, March 29, 12:30pm Computer Science 105 Universality laws for randomized dimension reduction Dimension reduction is the process of embedding high-dimensional data into a lower dimensional space to facilitate its analysis. In the Euclidean setting, one fundamental technique for dimension reduction is to apply a random linear map to the data. The question is how large the embedding dimension must be to ensure that randomized dimension reduction succeeds with high probability. This talk describes a phase transition in the behavior of the dimension reduction map as the embedding dimension increases. The location of this phase transition is universal for a large class of datasets and random dimension reduction maps. Furthermore, the stability properties of randomized dimension reduction are also universal. These results have many applications in numerical analysis, signal processing, and statistics. Joint work with Samet Oymak.

1 0

Colloquium Speaker, Matt Weinberg Thursday, March 31, 12:30pm
by Nicole E. Wagenblast 25 Mar '16

25 Mar '16

Colloquium Speaker Matt Weinberg, Princeton University Thursday, March 31, 2016 - 12:30pm Computer Science 105 Algorithms for Strategic Agents When real people interact with algorithms (e.g. in auctions, crowdsourcing, Bitcoin, etc.), they impose additional objectives beyond simply that the algorithm is correct, fast, and uses little storage. People strategize during these interactions, so algorithms deployed in these settings must be robust against potential manipulation. Additionally, people prefer transparent interactions, so these algorithms must also be as simple as possible. My research addresses these, and other novel challenges that arise when algorithms interact with strategic agents. In this talk, I will focus on one aspect of this agenda and present a new algorithmic framework to solve any optimization problem in a way that is robust to strategic manipulation. I will further apply this framework to extend Myerson's celebrated characterization of optimal single-item auctions to multiple items (Myerson 1981), design mechanisms for job scheduling (Nisan and Ronen 1999), and resolve other problems at the interface of algorithms and game theory. Finally, I will briefly show how strategic considerations motivate nice questions in "traditional" areas of algorithm design as well, and present some of my work in online algorithms, convex optimization, and parallel algorithms. Matt received his PhD in EECS from MIT in 2014, where he was advised by Costis Daskalakis. He is now a postdoc at Princeton University in the Computer Science department. His research focuses on designing algorithms that address constraints imposed by the strategic nature of people that interact with them. For his thesis work on this topic, he received MIT's George M. Sprowls award and the SIGecom Doctoral Dissertation award. Matt received his B.A. in Math from Cornell University.

1 0