- talks - lists.cs.princeton.edu

Colloquium Speaker: Dimitris Papailiopoulos Monday, March 7- 12:30pm
by Nicole E. Wagenblast 01 Mar '16

01 Mar '16

Please note: The Large Auditorium does not permit food, therefore lunch will not be served. Colloquium Speaker Dimitris Papailiopoulos , University of California, Berkeley Monday, March 7, 2016 - 12:30pm Computer Science Large Auditorium, 104 Less Talking, More Learning: Avoiding Coordination In Parallel Machine Learning Algorithms The recent success of machine learning (ML) in both science and industry has generated an increasing demand to support ML algorithms at scale. In this talk, I will discuss strategies to gracefully scale machine learning on modern parallel computational platforms. A common approach to such scaling is coordination-free parallel algorithms, where individual processors run independently without communication, thus maximizing the time they compute. However, analyzing the performance of these algorithms can be challenging, as they often introduce race conditions and synchronization problems. In this talk, I will introduce a general methodology for analyzing asynchronous parallel algorithms. The key idea is to model the effects of core asynchrony as noise in the algorithmic input. This allows us to understand the performance of several popular asynchronous machine learning approaches, and to determine when asynchrony effects might overwhelm them. To overcome these effects, I will propose a new framework for parallelizing ML algorithms, where all memory conflicts and race conditions can be completely avoided. I will discuss the implementation of these ideas in practice, and demonstrate that they outperform the state-of-the-art across a large number of ML tasks on gigabyte-scale data sets. Dimitris Papailiopoulos is a postdoctoral researcher in the Department of Electrical Engineering and Computer Sciences at UC Berkeley and a member of the AMPLab. His research interests span machine learning, coding theory, and parallel and distributed algorithms, with a current focus on coordination-free parallel machine learning, large-scale data and graph analytics, and the use of codes to speed up distributed computation. Dimitris completed his Ph.D. in electrical and computer engineering at UT Austin in 2014. At Austin he worked under the supervision of Alex Dimakis. In 2015, he received the IEEE Signal Processing Society, Young Author Best Paper Award.

1 0

date correction. March 3rd, Colloquium Speaker-Rachit Agarwal, 12:30PM
by Mitra D. Kelly 01 Mar '16

01 Mar '16

Colloquium Speaker Rachit Agarwal, AMPLab at UC Berkeley March 3rd, 12:30 Computer Science 105 Title: Building Systems that Query on Compressed Data Abstract: Web services today want to support sophisticated queries, with stringent interactivity constraints. Many recent studies have argued that in-memory query execution is one of the keys to achieving query interactivity. However, as web services scale to larger data sizes, executing queries in memory becomes increasingly challenging. As a result, existing systems fall short of supporting sophisticated interactive queries at scale. In this talk, we present Succinct, a distributed data store that supports functionality comparable to state-of-the-art NoSQL stores and yet, enables query interactivity for an order of magnitude larger data sizes than what is possible today (or, alternatively, up to two orders of magnitude faster queries at scale). Succinct accomplishes this by executing a wide range of queries -- e.g., search, range, and even regular expressions -- directly on compressed data. Succinct achieves scale by storing the input data in a compressed form, and interactivity by avoiding data scans and data decompression. We will also discuss how Succinct's approach of executing queries on compressed data enables a new "lens" for exploring several classical systems problems -- e.g., failure recovery, load spikes during transient failures, skewed workloads, etc. --, and leads to previously unachievable operating points in the system design space. Succinct is open-sourced, and is already being adopted in production clusters of several large-scale web services. Bio: Rachit Agarwal is a postdoc in AMPLab at UC Berkeley, where he leads the Succinct project along with Ion Stoica. His research focuses on the core problems in distributed data-intensive systems, with the goal of building systems that not only aim for practical impact but also have a strong theoretical foundation. He completed his PhD at UIUC, working with Brighten Godfrey and Matthew Caesar, and his undergraduate from IIT Kanpur. During his PhD, he received 2012 UIUC Rambus research award and 2010 Wang-Chung research award for outstanding performance in computer engineering research, and was listed in 2010 UIUC List of Teachers ranked as excellent. 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-Rachit Agarwal , Thursday Feb 3, 12:30PM
by Mitra D. Kelly 01 Mar '16

01 Mar '16

Colloquium Speaker Rachit Agarwal, AMPLab at UC Berkeley March 3rd, 12:30 Computer Science 105 Title: Building Systems that Query on Compressed Data Abstract: Web services today want to support sophisticated queries, with stringent interactivity constraints. Many recent studies have argued that in-memory query execution is one of the keys to achieving query interactivity. However, as web services scale to larger data sizes, executing queries in memory becomes increasingly challenging. As a result, existing systems fall short of supporting sophisticated interactive queries at scale. In this talk, we present Succinct, a distributed data store that supports functionality comparable to state-of-the-art NoSQL stores and yet, enables query interactivity for an order of magnitude larger data sizes than what is possible today (or, alternatively, up to two orders of magnitude faster queries at scale). Succinct accomplishes this by executing a wide range of queries -- e.g., search, range, and even regular expressions -- directly on compressed data. Succinct achieves scale by storing the input data in a compressed form, and interactivity by avoiding data scans and data decompression. We will also discuss how Succinct's approach of executing queries on compressed data enables a new "lens" for exploring several classical systems problems -- e.g., failure recovery, load spikes during transient failures, skewed workloads, etc. --, and leads to previously unachievable operating points in the system design space. Succinct is open-sourced, and is already being adopted in production clusters of several large-scale web services. Bio: Rachit Agarwal is a postdoc in AMPLab at UC Berkeley, where he leads the Succinct project along with Ion Stoica. His research focuses on the core problems in distributed data-intensive systems, with the goal of building systems that not only aim for practical impact but also have a strong theoretical foundation. He completed his PhD at UIUC, working with Brighten Godfrey and Matthew Caesar, and his undergraduate from IIT Kanpur. During his PhD, he received 2012 UIUC Rambus research award and 2010 Wang-Chung research award for outstanding performance in computer engineering research, and was listed in 2010 UIUC List of Teachers ranked as excellent. 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 -Greg Durrett, Tuesday March 1, 12:30pm
by Mitra D. Kelly 29 Feb '16

29 Feb '16

Colloquium Speaker Greg Durrett, UC Berkeley Tuesday March 1, 12:30pm Computer Science 105 riven Text Analysis with Joint Models One reason that analyzing text is hard is that it involves dealing with deeply entangled linguistic variables: objects like syntactic structures, semantic types, and discourse relations depend on one another in complex ways. Our work tackles several facets of text analysis using joint modeling, combining model components both across and within the various subtasks of this analysis. This model structure allows us to pass information between these entangled subtasks and propagate high-confidence predictions rather than errors. Critically, our models have the capacity to learn key linguistic phenomena as well as other important patterns in the data; that is, linguistics tells us how to structure these models, then the data injects knowledge into them. We describe state-of-the-art systems for a range of tasks, including syntactic parsing, entity resolution, and document summarization. Bio: Greg is a Ph.D. candidate at UC Berkeley working on natural language processing with Dan Klein. He is interested in building structured machine learning models for a wide variety of text analysis problems and downstream NLP applications. His work is comprised of two broad thrusts: first, designing joint models that combine information across different tasks or different views of a problem, and second, building systems that strike a balance between being linguistically motivated and data-driven 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 Yuxin Chen, TODAY, 4:30pm
by Nicole E. Wagenblast 29 Feb '16

29 Feb '16

Colloquium Speaker Yuxin Chen, Stanford University Monday, February 29, 4:30pm Computer Science 104- large auditorium The Power of Nonconvex Paradigms for High-Dimensional Estimation In various scenarios in the information sciences, one wishes to estimate a large number of parameters from highly incomplete / imperfect data samples. A growing body of recent work has demonstrated the effectiveness of convex relaxation --- in particular, semidefinite programming --- for solving many problems of this kind. However, the computational cost of such convex paradigms is often unsatisfactory, which limits applicability to large-dimensional data. This talk follows another route: by formulating the problems into nonconvex programs, we attempt to optimize the nonconvex objectives directly. To illustrate the power of this strategy, we present two concrete stories. The first involves solving a random quadratic system of equations, which spans many applications ranging from the century-old phase retrieval problem to various latent-variable models in machine learning. The second is about recovering a collection of discrete variables from noisy pairwise difference measurements, which arises when one wishes to jointly align multiple images or to retrieve the genome phases from paired sequencing reads. We propose novel nonconvex paradigms for solving these two problems. In both cases, the proposed solutions can be accomplished within linear time, while achieving a statistical accuracy that is nearly un-improvable. Yuxin Chen is currently a postdoctoral scholar in the Department of Statistics at Stanford University, supervised by Prof. Emmanuel Candès. He received the Ph.D. degree in Electrical Engineering and M.S. in Statistics from Stanford University, M.S. in Electrical and Computer Engineering from the University of Texas at Austin, and B.E. in microelectronics from Tsinghua University. His research interests include high-dimensional structured estimation, convex and nonconvex optimization, statistical learning, and information theory.

1 0

Colloquium speaker Yuxin Chen, Monday Feb 29, 4:30pm- reminder
by Nicole E. Wagenblast 26 Feb '16

26 Feb '16

Colloquium Speaker Yuxin Chen, Stanford University Monday, February 29, 4:30pm Computer Science 104- large auditorium The Power of Nonconvex Paradigms for High-Dimensional Estimation In various scenarios in the information sciences, one wishes to estimate a large number of parameters from highly incomplete / imperfect data samples. A growing body of recent work has demonstrated the effectiveness of convex relaxation --- in particular, semidefinite programming --- for solving many problems of this kind. However, the computational cost of such convex paradigms is often unsatisfactory, which limits applicability to large-dimensional data. This talk follows another route: by formulating the problems into nonconvex programs, we attempt to optimize the nonconvex objectives directly. To illustrate the power of this strategy, we present two concrete stories. The first involves solving a random quadratic system of equations, which spans many applications ranging from the century-old phase retrieval problem to various latent-variable models in machine learning. The second is about recovering a collection of discrete variables from noisy pairwise difference measurements, which arises when one wishes to jointly align multiple images or to retrieve the genome phases from paired sequencing reads. We propose novel nonconvex paradigms for solving these two problems. In both cases, the proposed solutions can be accomplished within linear time, while achieving a statistical accuracy that is nearly un-improvable. Yuxin Chen is currently a postdoctoral scholar in the Department of Statistics at Stanford University, supervised by Prof. Emmanuel Candès. He received the Ph.D. degree in Electrical Engineering and M.S. in Statistics from Stanford University, M.S. in Electrical and Computer Engineering from the University of Texas at Austin, and B.E. in microelectronics from Tsinghua University. His research interests include high-dimensional structured estimation, convex and nonconvex optimization, statistical learning, and information theory.

1 0

Colloquium Speaker Nikolay Atanasov, Today, 3:30pm
by Nicole E. Wagenblast 26 Feb '16

26 Feb '16

Colloquium Speaker Dr. Nikolay Atanasov Acquiring Metric and Semantic Information using Autonomous Robots Friday, February 26th at 3:30 PM Maeder Hall, ACEE Recent years have seen impressive progress in robot control and perception including adept manipulation, aggressive quadrotor maneuvers, dense metric map reconstruction, and object recognition in real time. The grand challenge in robotics today is to capitalize on these advances in order to enable autonomy at a higher-level of intelligence. It is compelling to envision teams of autonomous robots in environmental monitoring, precision agriculture, construction and structure inspection, security and surveillance, and search and rescue. In this talk, I will emphasize that many such applications can be addressed by thinking about how to coordinate robots in order to extract useful information about the environment. More precisely, I will formulate a general active estimation problem that captures the common characteristics of the aforementioned scenarios. I will show how to manage the complexity of the problem over metric information spaces with respect to long planning horizons and large robot teams. These results lead to computationally scalable, non-myopic algorithms with quantified performance for problems such as distributed source seeking and active simultaneous localization and mapping (SLAM). I will then focus on acquiring information using both metric and semantic observations (e.g., object recognition). In this context, there are several new challenges such as missed detections, false alarms, and unknown data association. To address them, I will model semantic observations via random sets and will discuss filtering using such models. A major contribution of our approach is in proving that the complexity of the problem is equivalent to computing the permanent of a suitable matrix. This enables us to develop and experimentally validate algorithms for semantic localization, mapping, and planning on mobile robots, Google's project Tango phone, and the KITTI visual odometry dataset.

1 0

Colloquium Speaker Bryan Parno Today, 12:30pm
by Nicole E. Wagenblast 26 Feb '16

26 Feb '16

Colloquium Speaker Bryan Parno, Microsoft Research Friday, February 26, 12:30pm Computer Science 105 Fully Verified Outsourced Computation Frequent headline-grabbing data breaches suggest that current best practices for safeguarding personal data are woefully inadequate. To try to move beyond the cycle of attacks and patches we see today, I design and build systems with formal end-to-end guarantees. For example, to provide strong guarantees for outsourced computations, I developed a new cryptographic framework, verifiable computation, which allows clients to outsource general computations to completely untrusted services and efficiently verify the correctness of each returned result. Through improvements to the theory and the underlying systems, we reduced the costs of verification by over twenty orders of magnitude. As a result, verifiable computation is now a thriving research area that has produced several startups, as well as enhancements to the security and privacy of X.509, MapReduce, and Bitcoin. While verifiable computation provides strong guarantees, even the best cryptographic system is useless if implemented badly, applied incorrectly, or used in a vulnerable system. Thus, I have led a team of researchers and engineers in the Ironclad project, working to expand formal software verification to provide end-to-end guarantees about the security and reliability of complex systems. By creating a set of new tools and methodologies, Ironclad produced the first complete stack of verified-secure software. We also recently developed the first methodology for verifying both the safety and liveness of complex distributed systems implementations. While interesting challenges remain, I expect that verification will fundamentally improve the software that underpins our digital and physical infrastructure. Bryan Parno is a Researcher in the Security and Privacy Group at Microsoft Research. After receiving a Bachelor's degree from Harvard College, he completed his PhD at Carnegie Mellon University, where his dissertation won the 2010 ACM Doctoral Dissertation Award. In 2011, he was selected for Forbes' 30-Under-30 Science List. He formalized and worked to optimize verifiable computation, receiving a Best Paper Award at the IEEE Symposium on Security and Privacy his advances. He coauthored a book on Bootstrapping Trust in Modern Computers, and his work in that area has been incorporated into the latest security enhancements in Intel CPUs. His research into security for new application models was incorporated into Windows and received a Best Paper Awards at the IEEE Symposium on Security and Privacy and the USENIX Symposium on Networked Systems Design and Implementation. He has recently extended his interest in bootstrapping trust to the problem of building practical, formally verified secure systems. His other research interests include user authentication, secure network protocols, and security in constrained environments (e.g., RFID tags, sensor networks, or vehicles).

1 0

Colloquium Speaker Nikolay Atanasov, Friday Feb 26, 3:30pm
by Nicole E. Wagenblast 25 Feb '16

25 Feb '16

Colloquium Speaker Dr. Nikolay Atanasov Acquiring Metric and Semantic Information using Autonomous Robots Friday, February 26th at 3:30 PM Maeder Hall, ACEE Recent years have seen impressive progress in robot control and perception including adept manipulation, aggressive quadrotor maneuvers, dense metric map reconstruction, and object recognition in real time. The grand challenge in robotics today is to capitalize on these advances in order to enable autonomy at a higher-level of intelligence. It is compelling to envision teams of autonomous robots in environmental monitoring, precision agriculture, construction and structure inspection, security and surveillance, and search and rescue. In this talk, I will emphasize that many such applications can be addressed by thinking about how to coordinate robots in order to extract useful information about the environment. More precisely, I will formulate a general active estimation problem that captures the common characteristics of the aforementioned scenarios. I will show how to manage the complexity of the problem over metric information spaces with respect to long planning horizons and large robot teams. These results lead to computationally scalable, non-myopic algorithms with quantified performance for problems such as distributed source seeking and active simultaneous localization and mapping (SLAM). I will then focus on acquiring information using both metric and semantic observations (e.g., object recognition). In this context, there are several new challenges such as missed detections, false alarms, and unknown data association. To address them, I will model semantic observations via random sets and will discuss filtering using such models. A major contribution of our approach is in proving that the complexity of the problem is equivalent to computing the permanent of a suitable matrix. This enables us to develop and experimentally validate algorithms for semantic localization, mapping, and planning on mobile robots, Google's project Tango phone, and the KITTI visual odometry dataset.

1 0

Colloquium Speaker Bryan Parno Friday Feb 26, 12:30pm- reminder
by Nicole E. Wagenblast 25 Feb '16

25 Feb '16

Colloquium Speaker Bryan Parno, Microsoft Research Friday, February 26, 12:30pm Computer Science 105 Fully Verified Outsourced Computation Frequent headline-grabbing data breaches suggest that current best practices for safeguarding personal data are woefully inadequate. To try to move beyond the cycle of attacks and patches we see today, I design and build systems with formal end-to-end guarantees. For example, to provide strong guarantees for outsourced computations, I developed a new cryptographic framework, verifiable computation, which allows clients to outsource general computations to completely untrusted services and efficiently verify the correctness of each returned result. Through improvements to the theory and the underlying systems, we reduced the costs of verification by over twenty orders of magnitude. As a result, verifiable computation is now a thriving research area that has produced several startups, as well as enhancements to the security and privacy of X.509, MapReduce, and Bitcoin. While verifiable computation provides strong guarantees, even the best cryptographic system is useless if implemented badly, applied incorrectly, or used in a vulnerable system. Thus, I have led a team of researchers and engineers in the Ironclad project, working to expand formal software verification to provide end-to-end guarantees about the security and reliability of complex systems. By creating a set of new tools and methodologies, Ironclad produced the first complete stack of verified-secure software. We also recently developed the first methodology for verifying both the safety and liveness of complex distributed systems implementations. While interesting challenges remain, I expect that verification will fundamentally improve the software that underpins our digital and physical infrastructure. Bryan Parno is a Researcher in the Security and Privacy Group at Microsoft Research. After receiving a Bachelor's degree from Harvard College, he completed his PhD at Carnegie Mellon University, where his dissertation won the 2010 ACM Doctoral Dissertation Award. In 2011, he was selected for Forbes' 30-Under-30 Science List. He formalized and worked to optimize verifiable computation, receiving a Best Paper Award at the IEEE Symposium on Security and Privacy his advances. He coauthored a book on Bootstrapping Trust in Modern Computers, and his work in that area has been incorporated into the latest security enhancements in Intel CPUs. His research into security for new application models was incorporated into Windows and received a Best Paper Awards at the IEEE Symposium on Security and Privacy and the USENIX Symposium on Networked Systems Design and Implementation. He has recently extended his interest in bootstrapping trust to the problem of building practical, formally verified secure systems. His other research interests include user authentication, secure network protocols, and security in constrained environments (e.g., RFID tags, sensor networks, or vehicles).

1 0