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

4:30pm talk today on information-theoretic approaches to neural network compression, clustering, and concept learning
by Jennifer Rexford 29 Jan '18

29 Jan '18

Title: Information-Theoretic Approaches to Neural Network Compression, Clustering, and Concept Learning Speaker: Lav Varshney (University of Illinois at Urbana-Champaign) Location: B205 Engneering Quadrangle Date/Time: Monday, January 29, 2018 - 4:30pm Abstract: Deep neural networks have shown incredible performance for inference tasks in a variety of domains, but unfortunately are often enormous cloud-based structures, require significant training data, and are hard for people to interpret. To work towards addressing these challenges, we present three lines of information-theoretic investigation. We discuss optimal quantization of synaptic weights and universal lossless compressed representations of feedforward neural networks, taking inferential purpose into account. The basic insight yielding considerable rate reduction is a kind of permutation invariance to the labeling of nodes. We also discuss optimal energy allocation in specialized hardware implementations of neural networks. In considering unsupervised learning, we present asymptotically-optimal algorithms for universal clustering and joint registration/clustering that involve optimization of novel empirical multivariate information measures. Finally we present algorithms for hierarchical, human-interpretable concept learning that iteratively optimize empirical information measures. Such concept learning may act in support of computational creativity. Bio: Lav Varshney is an assistant professor of electrical and computer engineering, computer science, and neuroscience at the University of Illinois at Urbana-Champaign. He is also leading curriculum initiatives for the new B.S. degree in Innovation, Leadership, and Engineering Entrepreneurship in the College of Engineering. He received the B.S. degree (magna cum laude) in electrical and computer engineering with honors from Cornell University in 2004. He received the S.M., E.E., and Ph.D. degrees, all in electrical engineering and computer science, from the Massachusetts Institute of Technology, in 2006, 2008, and 2010, where his theses received the E. A. Guillemin Thesis Award and the J.-A. Kong Award Honorable Mention. He was a research staff member at the IBM Thomas J. Watson Research Center from 2010 until 2013, where he led the design and development of the Chef Watson computational creativity system. His research interests include information and coding theory; data science; limits of nanoscale, social, and neural computing; human decision making and collective intelligence; and creativity. Dr. Varshney is a founding member of the IEEE Special Interest Group on Big Data in Signal Processing and served on the Shannon Centenary Committee of the IEEE Information Theory Society. He also serves on the advisory board of the AI XPRIZE. He received the IBM Faculty Award in 2014 and was a finalist for the Bell Labs Prize in 2014 and 2016. He and his students have won several best paper awards, including a 2015 Data for Good Exchange Paper Award. His work appears in the anthology, The Best Writing on Mathematics 2014, and he was selected to present at the 2017 World Science Festival. He appears on the List of Teachers Ranked as Excellent and has been named a Center for Advanced Study Fellow at the University of Illinois.

1 0

Muhammad Shahbaz will present his PRe FPO on Friday, March 2, 2018 at 2pm in CS 302.
by Nicki Gotsis 23 Jan '18

23 Jan '18

Muhammad Shahbaz will present his PRe FPO on Friday, March 2, 2018 at 2pm in CS 302. Committee Members: Nick Feamster (advisor), Jen Rexford (reader), Ben Pfaff (VMware), Mike Freedman and Wyatt Lloyd (non-readers) Time: Friday, March 2nd from 2 to 4 pm ET Title: Programmable Services on Software Switches Abstract: Software switches, such as Open vSwitch (OVS), play a critical role in modern data centers: with few exceptions, every packet that passes to or from a virtual machine (VM) passes through a software switch. These switches frequently need upgrading and customization to support new encapsulation headers, improved troubleshooting and debugging features, more sophisticated routing such as source-controlled routing, and virtual-to-physical gateway and middlebox-like functions such as load balancing, address virtualization, and encryption. Today, modifying these switches requires both intimate knowledge of the switch codebase (including kernel code) and extensive expertise in network protocol design, making the bar for customizing these software switches prohibitively high. Changing how a software switch forwards packets should not require intimate knowledge of its implementation. Instead, it should be possible to specify how packets are processed and transmitted in a high-level domain-specific language (DSL), such as P4, and compiling the resulting program to run on a software switch. This decoupling of forwarding behavior from underlying switch code would enable protocol designers to develop proprietary customizations without having to track the evolution of the (larger and more complex) underlying software switch codebase. This thesis addresses these challenges by (1) providing a programmable software switch whose behavior is customizable using a high-level DSL, and (2) demonstrating the benefits of such switches by building a new network service. Together these contributions show how programmable switches provide greater flexibility to network administrators and protocol designers, and to allow them to innovate and improve their systems. The first part of the dissertation presents the design and implementation of PISCES, a programmable, protocol-independent software switch. PISCES allows a protocol designer to specify a software switch’s custom packet-processing behavior in a high-level, domain-specific language (in our case, P4); a compiler then produces source code for the underlying target software switch (in our case, OVS). Our evaluation shows that PISCES programs are on average about 40 times shorter than equivalent changes to OVS source code and—with appropriate compiler optimizations—incur a forwarding performance (i.e., throughput) overhead of only about 2%. The second part demonstrates the benefits of these programmable switches by building a new network service, Baseerat, that requires custom modifications to switch forwarding behavior. Baseerat adds support for native multicast in data center networks using both software (e.g., PISCES) and hardware (e.g., Barefoot’s Tofino) programmable switches. In Baseerat, a PISCES switch encodes multicast routing information inside packets, and intermediate switches act on this information to route packets to recipients. Baseerat obviates the need for maintaining state per switch, allowing it to scale to many multicast groups. Our experiments show that for a data center with more than 25,000 hosts, Baseerat can support one million groups while utilizing a packet header size of 300 bytes and requiring only 1,000 multicast entries in leaf switches, with a traffic overhead of about 1%.

1 0

Irene Lo, Jan 23rd (tomorrow) @ 12:30pm, Sherrerd 101
by Emily Lawrence 22 Jan '18

22 Jan '18

Irene Lo is giving a colloquium in ORFE on Tuesday January 23rd at 12:30pm in Sherrerd 101. She works broadly in mechanism design, with a focus on matching markets. Title and abstract are below if anyone is interested in attending. Thanks! -Matt Abstract: As market design theory increasingly shapes the design and operations of real-life marketplaces, it is important for designers to provide simple policy levers that practitioners can use to optimize platform objectives. In the school choice market, where scarce public school seats are assigned to students, a key operational issue is how to reassign seats that are vacated after an initial round of centralized assignment. Practical solutions to the reassignment problem must be simple to implement, truthful, efficient and fair while also alleviating costly student movement between schools. In this talk, I will propose and axiomatically justify a class of reassignment mechanisms, the Permuted Lottery Deferred Acceptance (PLDA) mechanisms. Our mechanisms generalize the commonly used Deferred Acceptance (DA) school choice mechanism to a two-round setting and retain its desirable incentive, fairness and efficiency properties. School choice systems typically run Deferred Acceptance with a lottery number assigned to each student to break ties in school priorities. I will show that under natural conditions on demand, correlating the tie-breaking lotteries across rounds preserves allocative welfare, and reversing the first-round lottery order minimizes reassignment among all PLDA mechanisms. Empirical investigations based on data from NYC high school admissions support our theoretical findings. This is based on joint work with Itai Feigenbaum, Yash Kanoria and Jay Sethuraman. Bio: Irene Lo is a 5th year Ph.D. student in the Industrial Engineering & Operations Research department at Columbia University, advised by Jay Sethuraman, Jacob Leshno and Yash Kanoria. Her main research interests are in operational and algorithmic issues in marketplace design, particularly in using theory to provide practical solutions for markets with social value. Her current focus is on operational challenges in school choice mechanisms. She is also interested in platform-based marketplaces, mechanism design for social good, graph theory, and games on networks. She graduated from Princeton University in 2013 with an A.B. in mathematics.

1 0

Colloquium Speaker Natalie Enright Jerger, TODAY at 11:00AM
by Emily C. Lawrence 18 Jan '18

18 Jan '18

Joint EE and CS Colloquium Speaker Prof. Natalie Enright Jerger, University of Toronto Thursday, January 18, 2018 - 11:00AM *please note, lunch will NOT be served at this talk* Computer Science - Room 105 Host: Prof. Margaret Martonosi “Architectural Techniques to Efficiently Handle Big Data Challenges” As Moore’s Law continues in the post-Dennard scaling era, architects and programmers must consider energy efficiency even more carefully as part of their designs. The energy cost of moving and storing data exceeds that of computing with that data. At the same time, we expect to see 100s of zettabytes of digital data in the next decade. This explosion of data that must be analyzes creates numerous challenges for current designs. In this talk, we will look at two techniques to address big data challenges facing computer architecture. One promising approach to boost both energy efficiency and performance is approximate computing. The approximate computing paradigm trades-off correctness for improvements in energy and/or performance by targeting key applications that do not require 100% accurate execution such as image processing and machine learning. We propose a microarchitectural technique, load value approximation that selectively predicts memory values in order to forego expensive accesses to the memory hierarchy. By predicting instead of moving data, we can save energy and improve the performance when a small amount of error is tolerable. In the second part of my talk, I will discuss the performance-cost trade-offs of interposer-based multi-chip, multi-core systems. Connecting multiple disparate chips via a silicon interposer allows us to tightly couple processors and memory within the same package for efficient data movement. I will briefly present our network solutions to realize these systems. Considering solutions that span technology, architecture and software opens up new opportunities to solve energy and performance challenges facing next generation systems. Bio: Natalie Enright Jerger is the Percy Edward Hart Professor of Electrical and Computer Engineering at the University of Toronto. Prior to joining the University of Toronto, she received her MSEE and PhD from the University of Wisconsin-Madison in 2004 and 2008, respectively. She received her Bachelor's degree from Purdue University in 2002. She is a recipient of the Ontario Ministry of Research and Innovation Early Researcher Award in 2012, the 2014 Ontario Professional Engineers Young Engineer Medal recipient and the 2015 Borg Early Career Award winner. She served as the program co-chair of the 7th Network-on-Chip Symposium and as the program chair of the 20th International Symposium on High Performance Computer Architecture. She is currently serving as the ACM SIGMICRO Vice Chair and an ACM SIGARCH Executive Committee member. Her current research explores on-chip networks, approximate computing, IoT architectures and machine learning acceleration. She is also passionate about increasing the representation of women in computing, particular in computer architecture. She currently chairs the organizing committee for the Women in Computer Architecture group (WICARCH). In 2017, she co-authored the second edition of the Computer Architecture Synthesis Lecture on On-Chip Networks with Li-Shiuan Peh and Tushar Krishna. Her research is supported by NSERC, Intel, CFI, AMD, Huawei and Qualcomm.

1 0

Reminder: Colloquium Speaker Natalie Enright Jerger, tomorrow at 11:00AM
by Emily C. Lawrence 17 Jan '18

17 Jan '18

Joint EE and CS Colloquium Speaker Prof. Natalie Enright Jerger, University of Toronto Thursday, January 18, 2018 - 11:00AM *please note, lunch will NOT be served at this talk* Computer Science - Room 105 Host: Prof. Margaret Martonosi “Architectural Techniques to Efficiently Handle Big Data Challenges” As Moore’s Law continues in the post-Dennard scaling era, architects and programmers must consider energy efficiency even more carefully as part of their designs. The energy cost of moving and storing data exceeds that of computing with that data. At the same time, we expect to see 100s of zettabytes of digital data in the next decade. This explosion of data that must be analyzes creates numerous challenges for current designs. In this talk, we will look at two techniques to address big data challenges facing computer architecture. One promising approach to boost both energy efficiency and performance is approximate computing. The approximate computing paradigm trades-off correctness for improvements in energy and/or performance by targeting key applications that do not require 100% accurate execution such as image processing and machine learning. We propose a microarchitectural technique, load value approximation that selectively predicts memory values in order to forego expensive accesses to the memory hierarchy. By predicting instead of moving data, we can save energy and improve the performance when a small amount of error is tolerable. In the second part of my talk, I will discuss the performance-cost trade-offs of interposer-based multi-chip, multi-core systems. Connecting multiple disparate chips via a silicon interposer allows us to tightly couple processors and memory within the same package for efficient data movement. I will briefly present our network solutions to realize these systems. Considering solutions that span technology, architecture and software opens up new opportunities to solve energy and performance challenges facing next generation systems. Bio: Natalie Enright Jerger is the Percy Edward Hart Professor of Electrical and Computer Engineering at the University of Toronto. Prior to joining the University of Toronto, she received her MSEE and PhD from the University of Wisconsin-Madison in 2004 and 2008, respectively. She received her Bachelor's degree from Purdue University in 2002. She is a recipient of the Ontario Ministry of Research and Innovation Early Researcher Award in 2012, the 2014 Ontario Professional Engineers Young Engineer Medal recipient and the 2015 Borg Early Career Award winner. She served as the program co-chair of the 7th Network-on-Chip Symposium and as the program chair of the 20th International Symposium on High Performance Computer Architecture. She is currently serving as the ACM SIGMICRO Vice Chair and an ACM SIGARCH Executive Committee member. Her current research explores on-chip networks, approximate computing, IoT architectures and machine learning acceleration. She is also passionate about increasing the representation of women in computing, particular in computer architecture. She currently chairs the organizing committee for the Women in Computer Architecture group (WICARCH). In 2017, she co-authored the second edition of the Computer Architecture Synthesis Lecture on On-Chip Networks with Li-Shiuan Peh and Tushar Krishna. Her research is supported by NSERC, Intel, CFI, AMD, Huawei and Qualcomm.

1 0

Timothy Murphy will present his General Exam on Tuesday January 23, 2018 at 12pm in CS 401.
by Nicki Gotsis 16 Jan '18

16 Jan '18

Timothy Murphy will present his General Exam on Tuesday January 23, 2018 at 12pm in CS 401. The members of his committee are as follows: Zak Kincaid (Advisor), Aarti Gupta, and David Walker. Please find his reading list and abstract below. Papers / Chapters: 1. "Well Structured Transition Systems Everywhere." A Finkel and Ph. Schnoebelen. 1999. 2. "An axiomatic Proof Technique for Parallel Programs I." Susan Owici and David Gries. 1976. 3. "Resources, Concurrency and Local Reasoning." Peter W O'Hearn. 2004. 4. "Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints." Patric Cousot and Radhia Cousot. 1977. 5. "Lazy Abstraction with Interpolants." K. L. McMillan. 2006. 6. "Proof Spaces for Unbounded Parallelism." Azadeh Farzan, Zak Kincaid, and Andreas Podelski. 2015. 7. "The rely-Gaurantee Method for Verifying Shared Variable Programs." Qiwen Xu, Willem-Paul de Rolver and Jifeng He. 1997. 8. "A filtering Algorithm for Constraints of difference in CSPs." Jean-Charles Regin. 1996. 9. "Synethesizing Software Verifies from Proof Rules." Sergey Grebenshchikov, Nuno P. Lopes, Corneliu Popeea, and Andrey Rybalchenko. 2012. 10. "Artificial Intelligence: A Modern Approach" Chapter 6. (CSPs). Peter Norvig and Stuart J. Russel. 1994. Textbooks: 1. "The Calculus of Computation." Bradley and Manna. 2. "Principles of Program Analysis." Nielson, Nielson, and Hankin Abstract: I will start by introducing the concept of Predicate Automata and their use in concurrent program verification. Next, I'll describe the challenge of emptiness checking for such Predicate Automata --- How does one determine when to stop expanding a configuration of states? To do this, I introduce the notion of covering. If a configuration is covered by another already expanded configuration, then we can safely stop expanding. I will then show that the problem of determining coverability between two configurations is equivalent to the structure embedding problem. Finally, I’ll present MatchEmbeds, an algorithm for the structure embedding problem: given two finite first-order structures over a common relational vocabulary, does there exist an injective homomorphism from one to the other? The structure embedding problem is NP-complete in the general case, but for monadic structures (each predicate has arity 1) I observe that it can be solved in polytime by reduction to bipartite graph matching. My algorithm extends the bipartite matching approach to the general case by using it as the foundation of a backtracking search procedure. I show that MatchEmbeds outperforms state-of-the-art constraint satisfaction solvers on difficult random instances and significantly improves the performance of a client model checker for multi-threaded programs.

1 0

Yuanzhi Li will present his Pre FPO on Friday, January 19, 2018 at 1:30pm in CS 302.
by Nicki Gotsis 16 Jan '18

16 Jan '18

Yuanzhi Li will present his Pre FPO on Friday, January 19, 2018 at 1:30pm in CS 302. The members of his committee are as follows: Sanjeev Arora (advisor), Elad Hazan (reader), Yingyu Liang (U. Wisconsin, reader), Matt Weinberg (non-reader), Yoram Singer (non-reader) Please see below for talk abstract. All are welcome to join. Abstract: The recent success of machine learning has posed a great challenge for theoreticians: we lack a strong theoretical understanding of non-linear models and non-convex objective functions, which, in turn, are widely used in practice. My research goal is to bridge the gap between theory and practice in machine learning by building new and principled methods to better explain and enhance the empirical success of these models and algorithms. In the first part I will talk about modeling. In particular, I will focus on over-parametrization: A widely used method to build models with more parameters than the number of training examples. I will show, through the example of matrix sensing, how (stochastic) gradient descent can learn an over-parametrized model much faster than the under-parametrized one, without over-fitting the data. In the next part I will talking about algorithms for non-convex machine learning tasks. I will show, through the example of non-negative matrix factorization, how to use special structures of the data to design simple, provable, efficient and practical algorithms for the learning tasks.

1 0

Colloquium Speaker Natalie Enright Jerger, Thursday Jan 18
by Emily Lawrence 09 Jan '18

09 Jan '18

Colloquium Speaker Prof. Natalie Enright Jerger, University of Toronto Thursday, January 18, 2018 - 11:00AM *please note, lunch will NOT be served at this talk* Computer Science - Room 105 Host: Prof. Margaret Martonosi & Electrical Engineering "Architectural Techniques to Efficiently Handle Big Data Challenges" As Moore's Law continues in the post-Dennard scaling era, architects and programmers must consider energy efficiency even more carefully as part of their designs. The energy cost of moving and storing data exceeds that of computing with that data. At the same time, we expect to see 100s of zettabytes of digital data in the next decade. This explosion of data that must be analyzes creates numerous challenges for current designs. In this talk, we will look at two techniques to address big data challenges facing computer architecture. One promising approach to boost both energy efficiency and performance is approximate computing. The approximate computing paradigm trades-off correctness for improvements in energy and/or performance by targeting key applications that do not require 100% accurate execution such as image processing and machine learning. We propose a microarchitectural technique, load value approximation that selectively predicts memory values in order to forego expensive accesses to the memory hierarchy. By predicting instead of moving data, we can save energy and improve the performance when a small amount of error is tolerable. In the second part of my talk, I will discuss the performance-cost trade-offs of interposer-based multi-chip, multi-core systems. Connecting multiple disparate chips via a silicon interposer allows us to tightly couple processors and memory within the same package for efficient data movement. I will briefly present our network solutions to realize these systems. Considering solutions that span technology, architecture and software opens up new opportunities to solve energy and performance challenges facing next generation systems. Bio: Natalie Enright Jerger is the Percy Edward Hart Professor of Electrical and Computer Engineering at the University of Toronto. Prior to joining the University of Toronto, she received her MSEE and PhD from the University of Wisconsin-Madison in 2004 and 2008, respectively. She received her Bachelor's degree from Purdue University in 2002. She is a recipient of the Ontario Ministry of Research and Innovation Early Researcher Award in 2012, the 2014 Ontario Professional Engineers Young Engineer Medal recipient and the 2015 Borg Early Career Award winner. She served as the program co-chair of the 7th Network-on-Chip Symposium and as the program chair of the 20th International Symposium on High Performance Computer Architecture. She is currently serving as the ACM SIGMICRO Vice Chair and an ACM SIGARCH Executive Committee member. Her current research explores on-chip networks, approximate computing, IoT architectures and machine learning acceleration. She is also passionate about increasing the representation of women in computing, particular in computer architecture. She currently chairs the organizing committee for the Women in Computer Architecture group (WICARCH). In 2017, she co-authored the second edition of the Computer Architecture Synthesis Lecture on On-Chip Networks with Li-Shiuan Peh and Tushar Krishna. Her research is supported by NSERC, Intel, CFI, AMD, Huawei and Qualcomm.

1 0