- talks - lists.cs.princeton.edu

Shilpa Nadimpalli Kobren FPO TOMORROW Thursday, May 31, 2018 at 10:00am in CS402.
by Barbara A. Mooring 31 May '18

31 May '18

Shilpa Nadimpalli Kobren will present her FPO TOMORROW Thursday, May 31, 2018 at 10:00am in CS402. All are welcomed to attend. Committee members: Mona Singh (adviser), Barbara Engelhardt (examiner), Stanislav Shvartsman (examiner), Olga Troyanskaya (reader), and Benjamin J. Raphael (reader) Title: Detecting and Analyzing Variation in Protein Interactions Abstract: Proteins carry out a dazzling multitude of functions by interacting with DNA, RNA, other proteins and various other molecules within our cells. Together these interactions comprise complex networks that differ naturally across cells within an organism, across individuals in a population, and across species. Although such variation is critical for normal organismal functioning, mutations affecting protein interactions are also known to underlie a wide range of human diseases. In this dissertation, I introduce novel computational approaches that explore the extent to which specific protein interactions vary across species, across healthy individuals, and across individuals with cancer. To start, I focus on interaction variation across species. It is well established that changes in protein-DNA interactions underlie a wide range of observable differences across species. These differences are primarily thought to stem from changes in the DNA sites that transcription factor (TF) proteins bind to, although changes in the binding properties of TFs themselves have also been observed. Determining the prevalence of such TF changes, however, remains infeasible using current experimental approaches. Here, I develop and apply a comparative genomics framework to systematically quantify changes in the DNA-binding properties of orthologous TFs across species spanning ~45 million years of evolutionary divergence. I demonstrate that, contrary to expectation, cross-species regulatory network divergence resulting from changes in non-duplicated DNA-binding proteins is pervasive. These findings reveal a widespread yet largely unstudied source of divergence across transcriptional regulatory programs in animals. Next, I turn my attention to interaction variation across individuals. In order to comprehensively quantify this, I first combine large-scale sequence, domain and structure information to pinpoint sites within protein domains---the fundamental structural units in proteins---that are involved in binding DNA, RNA, peptides, ions, metabolites, or other small molecules. This domain-based approach enables us to identify putative interaction sites in over 60% of human genes, representing a 2.4-fold improvement over comparable state-of-the-art approaches for this task. I next demonstrate that whereas domain-inferred interaction sites are significantly depleted of natural variants across ~60,000 healthy individuals, these same sites are significantly enriched for cancer mutations across ~11,000 tumor samples. My analysis demonstrates that the cellular network variation that occurs across healthy individuals is unlikely to be due to changes within proteins; in contrast, mutations acquired in cancers appear to preferentially alter cellular networks by perturbing the proteins themselves. Finally, I show how we can leverage an interaction-based viewpoint to uncover mutated genes that play causal roles in human cancers. In particular, I aim to uncover genes whose interaction interfaces are significantly altered in tumors. Towards this end, I develop a robust computational framework that integrates my per-domain-position binding propensities with additional sources of biological data regarding protein functionality. I demonstrate that by analytically computing the significance of patterns of mutations, my approach is able to achieve a dramatic improvement in runtime over a typical empirical permutation test for this task. Moreover, my interaction-based method not only recapitulates known cancer driver genes faster and with greater precision than previous methods, but it also uncovers relatively rarely-mutated genes with likely roles in cancer. Through focusing on the somatic alteration of protein interaction interfaces in tumors, my method can inform the perturbed molecular mechanisms across known and putative cancer genes, thereby enabling valuable insights that may help guide personalized cancer treatments. Barbara A. Mooring Interim Graduate Coordinator Computer Science Department Princeton University

1 1

Yi Zhang General Exam Presentation TODAY Tuesday, May 29, 2018 10:00 am CS 302
by Barbara A. Mooring 29 May '18

29 May '18

Yi Zhang General Exam Presentation TODAY Tuesday, May 29, 2018 10:00 am CS 302 Committee: Prof. Sanjeev Arora (advisor), Prof. Elad Hazan, Prof. Sebastian Seung Title: Theory and Practice of Generative Adversarial Networks (GANs) Abstract: I will discuss the (in)ability of GANs to learn the data generating distribution. A theoretical analysis of various GAN architectures will be presented, along with a principled and practical test for the support size of Generator’s distribution. In the first part of my talk, I'll show training of GAN architectures may appear successful but the trained distribution may be far from target distribution in standard metrics. The presented theory prophecies the notorious “mode collapse” failure mode of GANs. It is also shown that an approximate pure equilibrium exists in the discriminator/generator game for a special class of generators with natural training objectives when generator capacity and training set sizes are moderate. This existence of equilibrium inspires MIX+GAN protocol, which can be combined with any existing GAN training, and empirically shown to improve some of them. In the second part, I’ll extend the theoretical analysis to more recent encoder-decoder GANs architectures (e.g., BiGAN/ALI), which were proposed to learn more meaningful features via GANs and (consequently) to also solve the mode-collapse issue. Specifically, I’ll show that such encoder-decoder training objectives still cannot guarantee learning of the full distribution. More seriously, they cannot prevent learning meaningless codes for data, contrary to usual intuition. In addition, I’ll also propose a novel test for estimating support size using the birthday paradox of discrete probability. Using this, empirical evidence is presented that well-known GANs approaches do learn distributions of fairly low support. Barbara A. Mooring Interim Graduate Coordinator Computer Science Department Princeton University

1 0

Colloquium Speaker-Daniel Sanchez, TODAY at 12:30pm
by Emily C. Lawrence 29 May '18

29 May '18

Daniel Sanchez from MIT Tuesday, May 29, 2018 - 12:30pm Computer Science - Room 105 Host: Margaret Martonosi "Making Parallelism Pervasive with the Swarm Architecture" Abstract: With Moore's Law coming to an end, architects must find ways to sustain performance growth without technology scaling. The most promising path is to build highly parallel systems that harness thousands of simple and efficient cores. But this approach will require new techniques to make massive parallelism practical, as current multicores fall short of this goal: they squander most of the parallelism available in applications and are too hard to program. I will present Swarm, a new architecture that successfully parallelizes algorithms that are often considered sequential and is much easier to program than conventional multicores. Swarm programs consist of tiny tasks, as small as tens of instructions each. Parallelism is implicit: all tasks follow a programmer-specified total or partial order, eliminating the correctness pitfalls of explicit synchronization (e.g., deadlock, data races, etc.). To scale, Swarm executes tasks speculatively and out of order, and efficiently speculates thousands of tasks ahead of the earliest active task to uncover enough parallelism. Swarm builds on decades of work on speculative architectures and contributes new techniques to scale to large core counts, including a new execution model, speculation-aware hardware task management, selective aborts, and scalable ordered task commits. Swarm also incorporates new techniques to exploit locality and to harness nested parallelism, making parallel algorithms easy to compose and uncovering abundant parallelism in large applications. Swarm accelerates challenging irregular applications from a broad set of domains, including graph analytics, machine learning, simulation, and databases. At 256 cores, Swarm is 53-561x faster than a single-core system, and outperforms state-of-the-art software-only parallel algorithms by one to two orders of magnitude. Besides achieving near-linear scalability, the resulting Swarm programs are almost as simple as their sequential counterparts, as they do not use explicit synchronization. Bio: Daniel Sanchez is an Associate Professor of Electrical Engineering and Computer Science at MIT. His research interests include parallel computer systems, scalable and efficient memory hierarchies, architectural support for parallelization, and architectures with quality-of-service guarantees. He earned a Ph.D. in Electrical Engineering from Stanford University in 2012 and received the NSF CAREER award in 2015.

1 0

Reminder: Colloquium Speaker-Daniel Sanchez, tomorrow at 12:30pm
by Emily C. Lawrence 28 May '18

28 May '18

Daniel Sanchez from MIT Tuesday, May 29, 2018 - 12:30pm Computer Science - Room 105 Host: Margaret Martonosi "Making Parallelism Pervasive with the Swarm Architecture" Abstract: With Moore's Law coming to an end, architects must find ways to sustain performance growth without technology scaling. The most promising path is to build highly parallel systems that harness thousands of simple and efficient cores. But this approach will require new techniques to make massive parallelism practical, as current multicores fall short of this goal: they squander most of the parallelism available in applications and are too hard to program. I will present Swarm, a new architecture that successfully parallelizes algorithms that are often considered sequential and is much easier to program than conventional multicores. Swarm programs consist of tiny tasks, as small as tens of instructions each. Parallelism is implicit: all tasks follow a programmer-specified total or partial order, eliminating the correctness pitfalls of explicit synchronization (e.g., deadlock, data races, etc.). To scale, Swarm executes tasks speculatively and out of order, and efficiently speculates thousands of tasks ahead of the earliest active task to uncover enough parallelism. Swarm builds on decades of work on speculative architectures and contributes new techniques to scale to large core counts, including a new execution model, speculation-aware hardware task management, selective aborts, and scalable ordered task commits. Swarm also incorporates new techniques to exploit locality and to harness nested parallelism, making parallel algorithms easy to compose and uncovering abundant parallelism in large applications. Swarm accelerates challenging irregular applications from a broad set of domains, including graph analytics, machine learning, simulation, and databases. At 256 cores, Swarm is 53-561x faster than a single-core system, and outperforms state-of-the-art software-only parallel algorithms by one to two orders of magnitude. Besides achieving near-linear scalability, the resulting Swarm programs are almost as simple as their sequential counterparts, as they do not use explicit synchronization. Bio: Daniel Sanchez is an Associate Professor of Electrical Engineering and Computer Science at MIT. His research interests include parallel computer systems, scalable and efficient memory hierarchies, architectural support for parallelization, and architectures with quality-of-service guarantees. He earned a Ph.D. in Electrical Engineering from Stanford University in 2012 and received the NSF CAREER award in 2015.

1 0

Shilpa Nadimpalli Kobren FPO Thursday, May 31, 2018 at 10:00 am CS402
by Mike Freedman 25 May '18

25 May '18

Shilpa Nadimpalli Kobren will present her FPO on Thursday, May 31, 2018 at 10:00am in CS402. All are welcomed to attend. *Committee members:* Mona Singh (adviser), Barbara Engelhardt (examiner), Stanislav Shvartsman (examiner), Olga Troyanskaya (reader), and Benjamin J. Raphael (reader) *Title: *Detecting and Analyzing Variation in Protein Interactions *Abstract: * Proteins carry out a dazzling multitude of functions by interacting with DNA, RNA, other proteins and various other molecules within our cells. Together these interactions comprise complex networks that differ naturally across cells within an organism, across individuals in a population, and across species. Although such variation is critical for normal organismal functioning, mutations affecting protein interactions are also known to underlie a wide range of human diseases. In this dissertation, I introduce novel computational approaches that explore the extent to which specific protein interactions vary across species, across healthy individuals, and across individuals with cancer. To start, I focus on interaction variation across species. It is well established that changes in protein-DNA interactions underlie a wide range of observable differences across species. These differences are primarily thought to stem from changes in the DNA sites that transcription factor (TF) proteins bind to, although changes in the binding properties of TFs themselves have also been observed. Determining the prevalence of such TF changes, however, remains infeasible using current experimental approaches. Here, I develop and apply a comparative genomics framework to systematically quantify changes in the DNA-binding properties of orthologous TFs across species spanning ~45 million years of evolutionary divergence. I demonstrate that, contrary to expectation, cross-species regulatory network divergence resulting from changes in non-duplicated DNA-binding proteins is pervasive. These findings reveal a widespread yet largely unstudied source of divergence across transcriptional regulatory programs in animals. Next, I turn my attention to interaction variation across individuals. In order to comprehensively quantify this, I first combine large-scale sequence, domain and structure information to pinpoint sites within protein domains---the fundamental structural units in proteins---that are involved in binding DNA, RNA, peptides, ions, metabolites, or other small molecules. This domain-based approach enables us to identify putative interaction sites in over 60% of human genes, representing a 2.4-fold improvement over comparable state-of-the-art approaches for this task. I next demonstrate that whereas domain-inferred interaction sites are significantly depleted of natural variants across ~60,000 healthy individuals, these same sites are significantly enriched for cancer mutations across ~11,000 tumor samples. My analysis demonstrates that the cellular network variation that occurs across healthy individuals is unlikely to be due to changes within proteins; in contrast, mutations acquired in cancers appear to preferentially alter cellular networks by perturbing the proteins themselves. Finally, I show how we can leverage an interaction-based viewpoint to uncover mutated genes that play causal roles in human cancers. In particular, I aim to uncover genes whose interaction interfaces are significantly altered in tumors. Towards this end, I develop a robust computational framework that integrates my per-domain-position binding propensities with additional sources of biological data regarding protein functionality. I demonstrate that by analytically computing the significance of patterns of mutations, my approach is able to achieve a dramatic improvement in runtime over atypical empirical permutation test for this task. Moreover, my interaction-based method not only recapitulates known cancer driver genes faster and with greater precision than previous methods, but it also uncovers relatively rarely-mutated genes with likely roles in cancer. Through focusing on the somatic alteration of protein interaction interfaces in tumors, my method can inform the perturbed molecular mechanisms across known and putative cancer genes, thereby enabling valuable insights that may help guide personalized cancer treatments.

1 0

Wei Hu General Exam Presentation - Friday, May 25, 2018 1:00 pm CS331
by Barbara A. Mooring 25 May '18

25 May '18

Wei Hu will present his General Exam Presentation on Friday, May 25, 2018 at 1:00 pm in CS331. Committee: Sanjeev Arora (adviser), Elad Hazan, Yoram Singer Title: Advances in Convex and Non-Convex Approaches to Low-Rank Matrix Optimization Abstract: Low-rank matrix estimation is a fundamental class of problems that find a wide range of applications in machine learning. In this talk, I will present two recent results on the optimization side of such problems, one using a convex approach and another using a non-convex approach. Faster optimization over trace-norm balls Minimizing a convex matrix function over a trace-norm ball usually serves as a convex surrogate to low-rank matrix optimization. In this work, we propose a rank-k variant of the classical Frank-Wolfe algorithm to solve this problem. Our algorithm replaces the top singular vector computation (1-SVD) in Frank-Wolfe with a top-k singular vector computation (k-SVD), which can be done by repeatedly applying 1-SVD k times. Alternatively, our algorithm can be viewed as a rank-k restricted version of projected gradient descent. We show that our algorithm has a linear convergence rate when the objective function is smooth and strongly convex, and the optimal solution has rank at most k. This improves the convergence rate and the total time complexity of the Frank-Wolfe method and its variants. Implicit regularization of gradient descent on learning multi-layer homogeneous models We consider directly using gradient descent to solve the low-rank matrix factorization problem, i.e., minimizing ||UV-M||_F^2 over the two factors U and V simultaneously. This problem, together with many multi-layer models such as deep neural networks with ReLU activation, have the property of homogeneity. A direct consequence of homogeneity is that a solution can produce small function value while being unbounded, which poses significant difficulty in analyzing first-order optimization methods like (stochastic) gradient descent. In this work, we prove that for a large class of deep homogeneous models, gradient descent with infinitesimal step size effectively enforces the differences between the squared L2 norms across different layers to remain invariant, and thus different layers are automatically balanced. Inspired by this finding, we show that for matrix factorization, gradient descent with random initialization and positive step size converges to a bounded global minimum. The first result is joint work with Zeyuan Allen-Zhu (MSR), Elad Hazan (Princeton) and Yuanzhi Li (Princeton). The second result is joint work with Simon S. Du (CMU) and Jason D. Lee (USC). Barbara A. Mooring Interim Graduate Coordinator Computer Science Department Princeton University

1 2

Daniel Suo General Exam Presentation TOMORROW May 25, 2018 10:00 am CS 233
by Barbara A. Mooring 25 May '18

25 May '18

Daniel Suo will present his General Exam Presentation TOMORROW May 25, 2018 at 10:00 am in CS 233. Committee Kai Li (Adviser) Jennifer Rexford Brian Kernighan Title: Deadlines for streaming machine learning applications Abstract: Within the last decade, advances in machine learning have created opportunities for streaming systems to act more effectively on incoming data. However, the typical metrics system designers optimize—throughput and latency—are not sufficient for a large, diverse class of machine learning applications (e.g., real-time neurofeedback., autonomous driving, fusion energy reactors) that demand highly predictable latency, or deadlines. These important applications, not possible before the recent developments in machine learning, face three unattractive options for meeting their deadlines: 1) rely on hand-tuned and job-specific allocation and scheduling, 2) limit their computational model to use traditional real-time algorithms and restrict many of the critical machine learning methods, or 3) suffer priority inversions and unnecessary overhead with low-latency systems. Their fourth option—missing deadlines—can result in catastrophic loss of life and property. In this talk, we make the case for a stream processing system that explicitly defines and reasons about deadlines and discuss some of our early work in the area. In particular, we describe techniques for efficiently identifying and remediating late tasks as early as possible. We show some illustrative results that suggest that the standard low-latency approach meets deadlines less reliably (by up to one third) or consumes more resources (by a factor of 1.5x) than a deadline-centric approach. Barbara A. Mooring Interim Graduate Coordinator Computer Science Department Princeton University

1 2

DISREGARD EMAIL re DANIEL SUO presenting today, it's TOMORROW
by Barbara A. Mooring 24 May '18

24 May '18

Barbara A. Mooring Interim Graduate Coordinator Computer Science Department Princeton University

1 0

Matheus Ferriera General Exam Presentation May 24, 2018 2:00 pm CS 302
by Barbara A. Mooring 23 May '18

23 May '18

Matheus Ferriera will present his General Exam Presentation on May 24, 2018 at 2:00 pm in CS 302. Commttee: Matt Weinberg, Adviser Ran Raz Ed Felten Title: To Mitigate Insecure IoT Devices, Regulate Manufacturers or Consumers? Abstract: The area of Algorithmic Mechanism Design focuses on designing efficient economic mechanisms where players act rationally towards their own selfish goals. Under this model, in the domain of auction design, the auction designer wants to maximize their revenue while guaranteeing that bidders are truthful. In this work, we propose a model where a third-party, with a distinct objective from the auctioneer, can influence the prior distribution of bidders in the single buyer, single seller setting. As motivation, we model the problem of a policy maker that can regulate either the manufacturer, by imposing minimum security standards, or the consumer, by imposing fines, with the goal to mitigate insecure IoT devices and still provide minimum revenue guarantees to the manufacturer. We prove that under some distribution assumptions, it is either optimal for a policy maker to regulate only manufacturers or only consumers. We also prove that when our assumptions are not present, we might have an unbounded penalty for not regulating both consumers and manufactures. As future directions, we would like to study approximation guarantees for general distributions. In addition, we propose empirical experiments in an online marketplace to validate the model. Joint work with Matt Weinberg, Nick Feamster, Danny Yuxing Huang, Tithi Chattopadhyay Barbara A. Mooring Interim Graduate Coordinator Computer Science Department Princeton University

1 0

Robert Harrison General Exam Presentation Wednesday, May 23, 2018 at 1:00 pm CS402
by Barbara A. Mooring 23 May '18

23 May '18

Robert Harrison will present his General Exam Presentation on Wednesday, May 23, 2018 at 1:00 pm in CS402. Committee: Jennifer Rexford (Adviser) Nick Feamster Mike Freedman Title: Query-Driven, Network-Wide Monitoring with Sonata Abstract: Managing and securing modern networks requires collecting and analyzing network traffic in real time. This collection and analysis allows operators to identify conditions that might indicate attack, misconfiguration, or failure. Some approaches for performing this collection and analysis scale well to high traffic rates by relying on the high-throughput, but limited, packet processing available on network switches; other approaches can support a wider range of analyses by relying on the lower-throughput, but rich, packet processing available on general purpose servers. We present Sonata, an expressive and scalable network telemetry system that performs the collection and analysis of network traffic using the compute resources of both network switches and stream-processing servers. Sonata provides a declarative interface to express queries using dataflow operators for a wide range of common telemetry tasks. To enable real-time execution, Sonata partitions queries across a stream processor and a switch data plane, running as much of the query as it can on the network switch, at line rate. To optimize the use of limited switch memory, Sonata models the constraints of Protocol Independent Switch Architecture (PISA) targets and solves an optimization problem to compile high-level dataflow operators to low-level PISA primitives. To generalize this compilation for network-wide query execution, we also describe the challenges inherent to distributed query execution and techniques for overcoming those challenges. Our evaluation shows that, for the single-switch case, Sonata can support a wide range of monitoring tasks while reducing the workload on the stream processor by as much as seven orders of magnitude compared to existing telemetry systems. Barbara A. Mooring Interim Graduate Coordinator Computer Science Department Princeton University

1 1