July 2018 - talks - lists.cs.princeton.edu

Joshua Wetzel will present his Pre FPO "Structure-aware approaches for deciphering sequence-specific protein-DNA interactions" on August 2, 2018 at 2:30pm in CS 302.
by Nicki Gotsis 30 Jul '18

30 Jul '18

Joshua Wetzel will present his Pre FPO " Structure-aware approaches for deciphering sequence-specific protein-DNA interactions" on August 2, 2018 at 2:30pm in CS 302. The members of his committee are Mona Singh (adviser), Barbara Engelhardt, Olga Troyanskaya, Ben Raphael, and Stanislav Shvartsman (CBE). All are welcome to attend. Title: Structure-aware approaches for deciphering sequence-specific protein-DNA interactions Abstract: Interactions between proteins and specific genomic loci are critical to the proper functioning of all cells. The ability of DNA-binding proteins to distinguish between their target binding sites and other regions of the genome has been demonstrated to be responsible for directing processes as fundamental as development, meiotic recombination, chromatin regulation, and even organization of the genome into a condensed three-dimensional nuclear structure. Highly precise X-ray or NMR co-complex structural studies have provided great insight into biochemical and stereo-chemical principles guiding such interactions; however, such studies are inherently low-throughput and provide us with the binding behavior of a protein with respect to only a single DNA target. Meanwhile, high-throughput experimental methodologies continue to scale, allowing us to examine a protein’s relative binding preferences across enormous libraries of DNA sequences, albeit at lower-resolution and with decreased interpretability of the interactions. Indeed, while we continue to characterize the individual DNA-binding preferences of large quantities of naturally-occurring or synthetic proteins, the fundamental relationship between the amino acid sequence of the protein and its DNA-binding preferences remains largely elusive. In this talk, I will describe three projects that further our understanding of the relationship between amino acid sequence and DNA-binding preferences (specificities): First, I will discuss a combined experimental-computational effort to systematically determine the DNA-binding landscape across an extremely large library of randomized protein variants of the Cys2His2zinc finger (C2H2-ZF) family, the most abundant group of DNA-binding proteins in eukaryotes. From an integrative analysis of the resulting data, I inferred the largest set of specificities to date for C2H2-ZFs, developed a state-of-the-art structurally-inspired method for predicting specificities for C2H2-ZFs based on amino acid sequence alone, and confirmed or discovered various fundamental and complex characteristics of DNA recognition for this protein family. Second, while specificities of proteins within a single family are related to one another via a common underlying structural DNA-binding interface; this fact is routinely ignored when inferring specificities. Accounting for such relationships should allow considerably more robust estimation in the presence of noise or under-sampling: common properties of high throughput data. To address this, I have developed a platform-independent method for joint inference of specificities for related proteins via enforcement of global within-dataset consistency, according to a structural interface model. Among other results, I will demonstrate that enforcing global consistency within a dataset increases agreement of specificities with an external gold standard beyond the level of agreement achieved via either individual inference of specificities or simple enforcement of local consistency. Finally, individual protein-DNA interaction screens do not provide any direct information that maps amino acid residue positions within the protein to particular DNA base positions in the derived specificities. Such mappings are valuable for learning protein-DNA recognition rules from high-throughput data and would provide insight into which binding site positions may be affected by point mutations in the protein. To help close this gap, I have created an unsupervised statistical framework for mapping groups of proteins from a given family, along with their corresponding specificities, onto structural interface models derived from aggregated family-level co-complex data. The framework outputs a multiple-motif alignment across proteins with potentially diverse DNA-binding specificities, along with a specificity prediction model consistent with the alignment. I will demonstrate proof of principle for this approach by showing that the multiple motif alignment produced for a group of mouse homeodomain proteins with diverse binding preferences is consistent with a known (experimentally-determined) alignment for related homeodomain proteins in fruit fly.

1 0

Yuanzhi Li will present his FPO "On the ability of gradient descent to learn neural networks" on Friday, 8/3/2018 at 11am in CS 301
by Nicki Gotsis 30 Jul '18

30 Jul '18

Yuanzhi Li will present his FPO "On the ability of gradient descent to learn neural networks" on Friday, 8/3/2018 at 11am in CS 301. The members of his committee are as follows:Sanjeev Arora (Adviser); Readers: Elad Hazan and Yingyu Liang (University of Wisconsin- Madison); Examiners: Yoram Singer, Matthew Weinberg, Sanjeev Arora All are welcome to attend. A copy of his thesis will be available in CS 310. Abstract is below. Neural networks stand in the center of the recent breakthrough in Machine Leaming. In the past few years, neural networks have found enormous of applications in various areas. However, due to the intrinsic non-convexity in the networks, theoretical understandings of them remain rather limited. The following major questions are largely unsolved: 1. Why can we train a neural network by minimizing a non-convex objective using local search algorithms? 2. Why does the training result generalizes instead of memorizing? On the theory side, the answer to these questions were rather pessimistic: It is known that even training a 2 layer neural network is NP-hard, and modem neural networks have so large capacity that allow them to fit arbitrary labels, so overfitting seems to be unavoidable. However, on the practice side, the answers to these questions are completely different: In practice, gradient descent (and its variants SGD, Momentum, Adagrad, Adam, RMSProp and AdamDelta) are quite effective in minimizing the training loss, moreover, the solutions found by these algorithms also often generalize well, even on neural networks with trillions of parameters. This thesis aims to build new theorems to address these questions in a way that matches the practical observations. We first consider neural networks with "identity mapping' (Resnet). We show that by adding this mapping to the network, the loss function becomes "locally convex" in a neighborhood of the optimal. We then consider neural networks with "quadratic activations". We show that even if we over-parametrize the network arbitrarily, the set of solutions given by gradient descent will remain on a manifold with small intrinsic dimensions, thus they will generalize. Next we consider neural networks with multiple outputs. We show that as long as the inputs and the labels are actually "structured" and the network is trained using gradient descent, the result will still generalize. In the end we extend our result to non-negative matrix factorization. We show that if we initialize the weights using "pure samples", and train it using an analog of gradient descent, then we are able to recover the hidden structures in the data almost optimally.

1 0

Ryan Beckett will present his FPO, "Network Control Plane Verification and Synthesis" on Monday, 7/23/2018 at 2pm, 101 Marx Hall
by Nicki Gotsis 16 Jul '18

16 Jul '18

Ryan Beckett will present his FPO, "Network Control Plane Verification and Synthesis" on Monday, 7/23/2018 at 2pm, 101 Marx Hall. The members of his committee are as follows: Nonreaders: David Walker (adviser), Aarti Gupta, Jennifer Rexford, Nick Feamster, and Ratul Mahajan (Intentionet); Readers: Aarti Gupta and Ratul Mahajan (Intentionet) All are welcome to attend. Please see abstract below. Computer networks have become an integral part of modern infrastructure, and as the world continues to become increasingly interconnected and more devices come online, the importance of networks will only continue to grow. A critical component of networks is a process called routing, whereby the network determines how to move data from point A to point B as changes occur dynamically (e.g., when new devices connect or equipment fails). Routing is traditionally achieved through the manual configuration of one or more distributed protocols that exchange messages about available routes to different destinations. Manual configuration lets a network operator tune various low-level protocol parameters to accommodate the different economic-, performance-, and robustness-related objectives that they may have for the network. Unfortunately, the low-level nature of existing configuration primitives and the scale of modern networks makes it difficult for humans to predict the impact of configuration on all possible runtime behaviors of the network, often resulting in configuration bugs. This dissertation develops two complementary techniques for proactively finding and preventing bugs in configurations. The first technique is verification. Given a collection of router configurations and a high-level specification of what the network should do (e.g., certain devices should be reachable), verification aims to ensure that the configurations implement this high-level specification correctly for all possible network behaviors. To address this problem, we develop a formal model of network routing protocols and show how many common protocols can be translated to logic constraints that existing constraint solvers can solve to find (or prove the absence of) bugs. The second technique is synthesis. Given a high-level specification of what the network should do, synthesis aims to produce a collection of configurations that faithfully implement the specification for all possible dynamic network conditions. We develop a new high-level language for describing end-to-end network behavior and demonstrate an efficient synthesis algorithm that can generate correct configurations. Throughout the development of both techniques, we show the importance of “abstraction” in speeding up each technique by several orders of magnitude.

1 2

Naman Agarwal will present his FPO "Second-Order Optimization Methods for Machine Learning" on Wednesday, 7/18/2018 at 2:00 PM in CS 402
by Nicki Gotsis 10 Jul '18

10 Jul '18

Naman Agarwal will present his FPO "Second-Order Optimization Methods for Machine Learning" on Wednesday, 7/18/2018 at 2:00 PM in CS 402 The members of his committee are as follows: Readers: Yoram Singer and Yuxin Chen; Nonreaders: Elad Hazan (Adviser), Sanjeev Arora and Mark Braverman All are welcome to attend. Please see below for abstract. In recent years first-order stochastic methods have emerged as the state-of-the-art in largescale machine learning optimization. This is primarily due to their efficient per-iteration complexity. Second-order methods, while able to provide faster convergence, are less popular due to the high cost of computing the second-order information. The main problem considered in this thesis is can efficient second-order methods for optimization problems arising in machine learning be developed that improve upon the best known first-order methods. We consider the ERM model of learning and propose linear time second-order algorithms for both convex as well as non-convex settings which improve upon the state-of-the-art first-order algorithms. In the non-convex setting second-order methods are also shown to converge to better quality solutions efficiently. For the convex case the proposed algorithms make use of a novel estimator for the inverse of a matrix and better sampling techniques for stochastic methods derived out of the notion of leverage scores. For the non-convex setting we propose an efficient implementation of the cubic regularization scheme proposed by Nesterov and Polyak. Furthermore we develop second-order methods for achieving approximate local minima on Riemannian manifolds which match the convergence rate of their Euclidean counterparts. Finally we show the limitations of second/higher-order methods by deriving oracle complexity lower bounds for such methods on sufficiently smooth convex functions.

1 0

Arpit Gupta will present his Pre FPO on Thursday, July 12, 2018 at 10am in CS402
by Nicki Gotsis 06 Jul '18

06 Jul '18

Arpit Gupta will present his Pre FPO on Thursday, July 12, 2018 at 10am in CS402. The members of his committee are as follows: Nick Feamster (advisor), Jennifer Rexford (reader), Walter Willinger (reader), Kyle Jamieson (non-reader), Marshini Chetty (non-reader). His abstract follows below. All are welcome to attend. Abstract: The proliferation of Internet-connected devices, services, and applications makes it more critical than ever to make sure that the network they depend on is reliable, performant, and secure. At the same time, their increasing complexity and diversity have made even simple network management tasks, such as debugging performance or detecting attacks, more complicated than ever. Modern network management needs to provide operators with better ways to (1) monitor what is going on in their networks; (2) take real-time preventive or corrective actions based on this information, to improve reliability, performance, and security of the networks and the services that run on them. Achieving these goals given the limited compute and storage resources available on modern network devices is challenging. This talk describes two projects that address the challenges of better information gathering, and more flexible control, respectively. First, I will present SDX, a Software-Defined Internet Exchange Point that allows an operator to apply fine-grained control over specific network paths in a way that interacts harmoniously with the Internet’s routing protocols. Second, I will present Sonata, a streaming network telemetry system that gathers information based directly on the queries that operators write; Sonata exploits the programmability of the network switches to offload expensive operations inline, whenever possible, ensuring that queries can run online, in real-time. In both cases, I will describe: (1) the abstractions that allow operators to express flexible programs for monitoring and control; (2) the algorithms and data structures that make the best use of limited compute and storage resources; and (3) the systems that glue the high-level abstractions to the low-level algorithms.

1 0