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

Divyarthi Mohan will present her Pre-FPO "Simplicity and Optimality in Algorithmic Economics: Multi-item Mechanism Auctions and Social Learning" on Wednesday, March 24 at 10.30am via Zoom.
by Nicki Mahler 16 Mar '21

16 Mar '21

Divyarthi Mohan will present her Pre-FPO " Simplicity and Optimality in Algorithmic Economics: Multi-item Mechanism Auctions and Social Learning" on Wednesday, March 24 at 10.30am via Zoom. Zoom link: [ https://princeton.zoom.us/j/95620223131?pwd=SWJIOFhQOGd1djR2a0ZVWm8rQUJ0QT09 | https://princeton.zoom.us/j/95620223131?pwd=SWJIOFhQOGd1djR2a0ZVWm8rQUJ0QT09 ] Committee Members: Prof. Matt Weinberg (Advisor) Prof. Bernard Chazelle (Examiner) Prof. Ran Raz (Examiner) Prof. Mark Braverman (Reader) Dr. Nicole Immorlica (Reader) Title: " Simplicity and Optimality in Algorithmic Economics: Multi-item Mechanism Auctions and Social Learning" Abstract. Designing mechanisms to maximize revenue is a fundamental question in mathematical economics, motivated by numerous practical applications like pricing goods, online ad auctions, and spectrum auctions. In his seminal work, Myerson resolved the single-dimensional case by proving that simply posting a take-it-or-leave-it price is the optimal mechanism. Unfortunately, optimal auctions for selling multiple items can be unreasonably complex and computationally intractable. In response, the past decade has seen a long line of work in theoretical computer science studying simple and computationally-efficient auctions through the lens of approximation. These works study particular simple auctions and show that they can get approximately optimal revenue (usually a constant factor). More recently, there are works that move away from this binary take on simplicity and instead explore the trade-off between simplicity and optimality. In this talk, we consider a revenue-maximizing seller with n items facing a single unit-demand buyer. Our work shows that simple mechanisms can achieve almost optimal revenue. We approached the tradeoffs of simplicity formally through the lens of computation and "menu size". Our main result provides a mechanism that gets a (1 − ε)-approximation to the optimal revenue in time quasi-polynomial in n. We introduce the notion of symmetric menu complexity of a mechanism, which counts the number of distinct options the buyer may purchase, up to permutations of the items. We show that the above approximately optimal mechanism has quasi-polynomial symmetric menu complexity. Prior to our work, no sub-exponential upper bounds (or super-polynomial lower bounds) were known in any multi-dimensional setting, for either measure. I will also discuss recent work on social learning between two Bayesian agents with limited/simple communication. In our model, to reflect real social exchanges, agents simply share a signal/anecdote they observed instead of sending arbitrary messages. When the agents have a fundamental difference, we show that the optimal communication scheme can vary drastically (from sending the most representative anecdote to an extremely biased anecdote) depending on whether the receiver can observe the communication scheme used by the sender.

1 0

CS Colloquium Speaker: Riad Wahby, Monday, March 22 at 12:30
by Emily C. Lawrence 15 Mar '21

15 Mar '21

CS Colloquium Speaker Riad Wahby, Stanford University Host: Andrew Appel Date: Monday, March 22 Time: 12:30pm EST Event page: [ https://www.cs.princeton.edu/events/26050 | https://www.cs.princeton.edu/events/26050 ] Register for Zoom webinar here: [ https://princeton.zoom.us/webinar/register/WN_SMKdFMoQRo2Cj3zvU57zyw | https://princeton.zoom.us/webinar/register/WN_SMKdFMoQRo2Cj3zvU57zyw ] Title: Probabilistic Proofs: Theory, Hardware, and Everything in Between Abstract: In the past decade, systems that use probabilistic proofs in real-world applications have seen explosive growth. These systems build upon some of the crown jewels of theoretical computer science---interactive proofs, probabilistically checkable proofs, and zero-knowledge proofs---to solve problems of trust and privacy in a wide range of settings. This talk describes my work building systems that answer questions ranging from "how can we build trustworthy hardware that uses untrusted components?" to "how can we reduce the cost of verifying smart contract execution in blockchains?" Along the way, I will discuss the pervasive challenges of efficiency, expressiveness, and scalability in this research area; my approach to addressing these challenges; and future directions that promise to bring this exciting technology to bear on an even wider range of applications. Bio: Riad S. Wahby is a Ph.D. candidate at Stanford, advised by Dan Boneh and Keith Winstein. His research interests include systems, computer security, and applied cryptography. Prior to attending Stanford, Riad spent ten years as an analog and mixed-signal integrated circuit designer. Riad and his collaborators received a 2016 IEEE Security and Privacy Distinguished Student Paper award; his work on hashing to elliptic curves is being standardized by the IETF.

1 0

CS Colloquium Speaker: Fraser Brown, Thursday, March 18 at 12:30
by Emily C. Lawrence 11 Mar '21

11 Mar '21

CS Colloquium Speaker Fraser Brown, Stanford University Host: Wyatt Lloyd Date: Thursday, March 18 Time: 12:30pm EST Event page: [ https://www.cs.princeton.edu/events/26053 | https://www.cs.princeton.edu/events/26053 ] Register for Zoom webinar here: [ https://princeton.zoom.us/webinar/register/WN_zrh31QWnTI2rkKRYabO8rg | https://princeton.zoom.us/webinar/register/WN_zrh31QWnTI2rkKRYabO8rg ] Title: Eliminating Bugs in Real Systems Abstract: Software is everywhere, and almost everywhere, software is broken. Some bugs just crash your printer; others hand an identity thief your bank account number; still others let nation-states spy on dissidents and persecute minorities. This talk outlines my work preventing bugs using a blend of programming languages techniques and systems design. First, I'll talk about securing massive, security-critical codebases without clean slate rewrites. This means rooting out hard-to-find bugs---as in Sys, which scales symbolic execution to find exploitable bugs in systems like the twenty-million line Chrome browser. It also means proving correctness of especially vulnerable pieces of code---as in VeRA, which automatically verifies part of the Firefox JavaScript engine. Finally, I'll discuss work on stronger foundations for new systems---as in CirC, a recent project unifying compiler infrastructure for program verification, cryptographic proofs, optimization problems, and more. Bio: Fraser Brown is a PhD student at Stanford advised by Dawson Engler, occasional visiting student at UCSD with Deian Stefan, and NSF graduate research fellowship recipient. She works at the intersection of programming languages, systems, and security, and her research has been used by several companies. She holds an undergraduate degree in English from Stanford.

1 0

Andrew Or will present his Pre FPO "Abstracting systems challenges from distributed deep learning" on Wednesday, March 17, 2021 at 1pm via Zoom.
by Nicki Mahler 10 Mar '21

10 Mar '21

Andrew Or will present his Pre FPO " Abstracting systems challenges from distributed deep learning" on Wednesday, March 17, 2021 at 1pm via Zoom. Zoom link: [ https://princeton.zoom.us/j/91618635317?pwd=cyt5WmdFQ2xaWmNGb2U0bTNlZXBYZz09 | https://princeton.zoom.us/j/91618635317?pwd=cyt5WmdFQ2xaWmNGb2U0bTNlZXBYZz09 ] Committee: Michael J. Freedman (advisor, examiner) Kai Li (examiner) Wyatt Lloyd (examiner) Amit Levy (reader) Ravi Netravali (reader) Talk abstract follows below. All are welcome to attend. Abstract: State-of-the-art distributed deep learning systems tightly couple model execution with the underlying hardware. Existing frameworks assume resource allocations must be fixed throughout the lifetime of a job, often leading to inefficiency in the usage of cluster resources. Further, model hyperparameters need to be retuned across different hardware configurations in order to achieve the same training result. In a world where the scale of deep learning workloads is growing rapidly, this requirement poses significant barriers to experimentation on smaller test beds and reproducing results across different hardware. In this thesis, we demonstrate that the above assumptions are not fundamental to distributed deep learning, and we resolve these limitations by proposing two systems built on top of TensorFlow. The first is an autoscaling engine that, through trial-and-error, automatically determines the most resource-efficient hardware configuration for a given job. We propose pluggable heuristics tailored for deep learning workloads that incrementally guide the system towards such a configuration. Instead of repeatedly stopping the job and restarting it from checkpoints, which can lead to GPUs or TPUs going idle for minutes every time, our system adjusts the all-reduce membership dynamically in between batches without interrupting the job. The second system is VirtualFlow, which leverages a novel abstraction between the model and the underlying hardware called virtual node processing. From the perspective of the model, virtual nodes, instead of physical devices (GPUs or TPUs), perform the computation. When multiple virtual nodes are mapped to a physical device, they are processed sequentially on that device. This representation allows users to train a model using the same batch size (and other hyperparameters) across different hardware, thereby preserving application-level semantics while hiding hardware-level details from the user. Using this technique, VirtualFlow also enables a variety of new important use cases that improve resource efficiency, including resource elasticity and heterogeneous training (using different types of GPUs in the same job).

1 0

CS Colloquium Speaker: Deepak Narayanan, today at 4:30pm EST
by Emily C. Lawrence 10 Mar '21

10 Mar '21

CS Colloquium Speaker Deepak Narayanan, Stanford University Host: Kyle Jamieson Date: Wednesday, March 10 Time: 4:30pm EST Event page: [ https://www.cs.princeton.edu/events/26048 | https://www.cs.princeton.edu/events/26048 ] Register for Zoom webinar here: [ https://princeton.zoom.us/webinar/register/WN_Gry8g80-S06bARgqKzko_Q | https://princeton.zoom.us/webinar/register/WN_Gry8g80-S06bARgqKzko_Q ] Title: Resource-Efficient Execution for Deep Learning Abstract: Deep Learning models have enabled state-of-the-art results across a broad range of applications; however, training these models is extremely time- and resource-intensive, taking weeks on clusters with thousands of expensive accelerators in the extreme case. In this talk, I will describe two systems that improve the resource efficiency of model training. The first system, PipeDream, proposes the use of pipelining to accelerate distributed training. Pipeline parallelism facilitates model training with lower communication overhead than previous methods while still ensuring high compute resource utilization. Pipeline parallelism also enables the efficient training of large models that do not fit on a single worker. Pipeline parallelism is being used at Facebook, Microsoft, OpenAI, and Nvidia for efficient large-scale model training. The second system, Gavel, determines how resources in a shared cluster with heterogeneous compute resources (e.g., different types of hardware accelerators) should be partitioned among different users to optimize objectives specified over multiple training jobs. Gavel can improve various scheduling objectives, such as average completion time, makespan, or cloud computing resource cost, by up to 3.5x. I will conclude the talk with discussion on future directions for optimizing Machine Learning systems. Bio: Deepak Narayanan is a final-year PhD student at Stanford University advised by Prof. Matei Zaharia. He is interested in designing and building software to improve the runtime performance and efficiency of emerging machine learning and data analytics workloads on modern hardware. His work is supported by a NSF graduate fellowship.

1 0

Reminder: Deepak Narayanan, tomorrow at 4:30
by Emily C. Lawrence 09 Mar '21

09 Mar '21

CS Colloquium Speaker Deepak Narayanan, Stanford University Host: Kyle Jamieson Date: Wednesday, March 10 Time: 4:30pm EST Event page: [ https://www.cs.princeton.edu/events/26048 | https://www.cs.princeton.edu/events/26048 ] Register for Zoom webinar here: [ https://princeton.zoom.us/webinar/register/WN_Gry8g80-S06bARgqKzko_Q | https://princeton.zoom.us/webinar/register/WN_Gry8g80-S06bARgqKzko_Q ] Title: Resource-Efficient Execution for Deep Learning Abstract: Deep Learning models have enabled state-of-the-art results across a broad range of applications; however, training these models is extremely time- and resource-intensive, taking weeks on clusters with thousands of expensive accelerators in the extreme case. In this talk, I will describe two systems that improve the resource efficiency of model training. The first system, PipeDream, proposes the use of pipelining to accelerate distributed training. Pipeline parallelism facilitates model training with lower communication overhead than previous methods while still ensuring high compute resource utilization. Pipeline parallelism also enables the efficient training of large models that do not fit on a single worker. Pipeline parallelism is being used at Facebook, Microsoft, OpenAI, and Nvidia for efficient large-scale model training. The second system, Gavel, determines how resources in a shared cluster with heterogeneous compute resources (e.g., different types of hardware accelerators) should be partitioned among different users to optimize objectives specified over multiple training jobs. Gavel can improve various scheduling objectives, such as average completion time, makespan, or cloud computing resource cost, by up to 3.5x. I will conclude the talk with discussion on future directions for optimizing Machine Learning systems. Bio: Deepak Narayanan is a final-year PhD student at Stanford University advised by Prof. Matei Zaharia. He is interested in designing and building software to improve the runtime performance and efficiency of emerging machine learning and data analytics workloads on modern hardware. His work is supported by a NSF graduate fellowship.

1 0

TOMORROW 3/9/2021 ECE Seminar - Maria Apostolaki, ETH
by Emily C. Lawrence 08 Mar '21

08 Mar '21

ECE SEMINAR Speaker: Maria Apostolaki, ETH Title: Building secure distributed systems atop the insecure Internet Day: Tuesday, March 9, 2021 Time: 4:30 pm Room: Please register at [ https://princeton.zoom.us/meeting/register/tJUlc-2oqTwiHdZVqHbVqzMkeIX1y6v7… | https://princeton.zoom.us/meeting/register/tJUlc-2oqTwiHdZVqHbVqzMkeIX1y6v7… ] Host: Prateek Mittal Abstract: Distributed systems are increasingly important for our everyday life, allowing for high performance, fault tolerance, and flexibility. Many of these systems nowadays rely on the inherently insecure Internet infrastructure. Surely though, they should have been designed to take this into account...? In this talk, I will answer negatively to this question using a concrete example: public blockchain systems such as Bitcoin. These are novel distributed systems that are designed according to stringent failure models. In this context, I will explain how an adversary controlling pieces of Internet infrastructure can practically compromise: (i) Bitcoin's consensus protocol (by partitioning the network); (ii) Bitcoin's anonymity guarantees (by mapping pseudonyms to real-world identities); and (iii) Bitcoin's availability (by eclipsing clients). While these attacks are worrying, I will also introduce practical and effective defenses to counter them both at the network and the application layer. Beyond Bitcoin, this work teaches essential lessons for distributed-system design. Bio: Maria Apostolaki is a PhD Student at ETH Zurich advised by Laurent Vanbever. During her studies, she has been a visiting student at MIT (2019) and a research intern at Microsoft Research (2018) and Google (2017). Before joining ETH, she earned her diploma in Electrical and Computer Engineering at the National Technical University of Athens, Greece. Her research focuses on building secure, performant, and deployable networked systems using both hardware and software. Her research led to discovering significant vulnerabilities in the Bitcoin system and spearheaded changes to the Bitcoin codebase. Maria’s work received widespread media coverage and was awarded an Applied Networking Research Prize by IETF.

1 0

CS Colloquium Speaker: Amy Zhang, today at 4:30pm
by Emily C. Lawrence 08 Mar '21

08 Mar '21

CS Colloquium Speaker Amy Zhang, McGill University and the Mila Institute Date: Monday, March 8 Time: 4:30pm EST Host: Tom Griffiths Event page: [ https://www.cs.princeton.edu/events/26041 | https://www.cs.princeton.edu/events/26041 ] Register for Zoom webinar here: [ https://princeton.zoom.us/webinar/register/WN_yb-TRAQJSwyBTo7RSDfhUA | https://princeton.zoom.us/webinar/register/WN_yb-TRAQJSwyBTo7RSDfhUA ] Title: Exploiting Latent Structure and Bisimulation Metrics for Better Generalization in Reinforcement Learning Abstract: The advent of deep learning has shepherded unprecedented progress in various fields of machine learning. Despite recent advances in deep reinforcement learning (RL) algorithms, however, there is no method today that exhibits anywhere near the generalization that we have seen in computer vision and NLP. Indeed, one might ask whether deep RL algorithms are even capable of the kind of generalization that is needed for open-world environments. This challenge is fundamental and will not be solved with incremental algorithmic advances. In this talk, we propose to incorporate different assumptions that better reflect the real world and allow the design of novel algorithms with theoretical guarantees to address this fundamental problem. We first present how state abstractions can accelerate reinforcement learning from rich observations, such as images, without relying either on domain knowledge or pixel-reconstruction. Our goal is to learn state abstractions that both provide for effective downstream control and invariance to task-irrelevant details. We use bisimulation metrics to quantify behavioral similarity between states, and learn robust latent representations which encode only the task-relevant information from observations. We provide theoretical guarantees for the learned approximate abstraction and extend this notion to families of tasks with varying dynamics. Bio: I am a final year PhD candidate at McGill University and the Mila Institute, co-supervised by Profs. Joelle Pineau and Doina Precup. I am also a researcher at Facebook AI Research. My work focuses on bridging theory and practice through learning approximate state abstractions and learning representations for generalization in reinforcement learning. I previously obtained an M.Eng. in EECS and dual B.Sci. degrees in Mathematics and EECS from MIT.

1 0

Reminder: Amy Zhang, tomorrow at 4:30pm
by Emily C. Lawrence 07 Mar '21

07 Mar '21

CS Colloquium Speaker Amy Zhang, McGill University and the Mila Institute Date: Monday, March 8 Time: 4:30pm EST Host: Tom Griffiths Event page: [ https://www.cs.princeton.edu/events/26041 | https://www.cs.princeton.edu/events/26041 ] Register for Zoom webinar here: [ https://princeton.zoom.us/webinar/register/WN_yb-TRAQJSwyBTo7RSDfhUA | https://princeton.zoom.us/webinar/register/WN_yb-TRAQJSwyBTo7RSDfhUA ] Title: Exploiting Latent Structure and Bisimulation Metrics for Better Generalization in Reinforcement Learning Abstract: The advent of deep learning has shepherded unprecedented progress in various fields of machine learning. Despite recent advances in deep reinforcement learning (RL) algorithms, however, there is no method today that exhibits anywhere near the generalization that we have seen in computer vision and NLP. Indeed, one might ask whether deep RL algorithms are even capable of the kind of generalization that is needed for open-world environments. This challenge is fundamental and will not be solved with incremental algorithmic advances. In this talk, we propose to incorporate different assumptions that better reflect the real world and allow the design of novel algorithms with theoretical guarantees to address this fundamental problem. We first present how state abstractions can accelerate reinforcement learning from rich observations, such as images, without relying either on domain knowledge or pixel-reconstruction. Our goal is to learn state abstractions that both provide for effective downstream control and invariance to task-irrelevant details. We use bisimulation metrics to quantify behavioral similarity between states, and learn robust latent representations which encode only the task-relevant information from observations. We provide theoretical guarantees for the learned approximate abstraction and extend this notion to families of tasks with varying dynamics. Bio: I am a final year PhD candidate at McGill University and the Mila Institute, co-supervised by Profs. Joelle Pineau and Doina Precup. I am also a researcher at Facebook AI Research. My work focuses on bridging theory and practice through learning approximate state abstractions and learning representations for generalization in reinforcement learning. I previously obtained an M.Eng. in EECS and dual B.Sci. degrees in Mathematics and EECS from MIT.

1 0

Riley Simmons-Edler will present his Pre FPO "Overcoming Sampling and Exploration Challenges in Deep Reinforcement Learning" on Friday, March 12, 2021 at 4pm via Zoom
by Nicki Mahler 05 Mar '21

05 Mar '21

Riley Simmons-Edler will present his Pre FPO "Overcoming Sampling and Exploration Challenges in Deep Reinforcement Learning" on Friday, March 12, 2021 at 4pm via Zoom [ https://princeton.zoom.us/j/92165806242?pwd=VWhvWW1DZXpqWUsvY0pVclE1eklVZz09 | https://princeton.zoom.us/j/92165806242?pwd=VWhvWW1DZXpqWUsvY0pVclE1eklVZz09 ] Committee: Sebastian Seung (advisor, examiner) Olga Russokovsky (examiner) Szymon Rusinkiewicz (examiner) Daniel Lee (external- Cornell, reader) Karthik Narasimhan (reader) Talk abstract follows below. All are welcome to attend. Abstract: The combination of deep neural networks with the algorithms and formalisms of reinforcement learning (RL) shows great promise for solving otherwise intractable learning tasks. However, practical applications of deep reinforcement learning remain scarce. The outstanding challenges of deep RL can be broadly grouped into two categories, broadly described as "What to learn from experiences?" and "What experiences to learn from?" In this thesis, I will describe the work I have done to address the second category, which is historically the less-studied domain. Specifically, I address problems of sampling- whether actions, states, or trajectories- which contain information sufficient for learning a task. I examine this challenge at three levels of algorithm design and task complexity, from algorithmic submodules to combinations of algorithms to hybrid algorithms that violate common RL conventions. First, I will present my work on stable and efficient sampling of actions that optimize a Q-function of continuous-valued actions. By combining a sample-based optimizer with neural network approximation, it is possible to obtain both stability in training as well as computational efficiency and precision in inference. Second, I will present my work on reward-aware exploration, the discovery of highly-rewarding states in tasks where commonly-used sampling methods are insufficient. A teacher "exploration" agent can discover states and trajectories which maximize the amount a student "exploitation" agent learns on those experiences, and can enable the student agent to solve hard tasks which are otherwise impossible for it. Third, I will present my work combining reinforcement learning with heuristic search, for use in task domains where the transition model is known, but where the combinatorics of the state space are intractable for traditional search algorithms. I show that by combining deep Q-learning with a best-first tree search algorithm, it is possible to find solutions to simple program synthesis problems with dramatically fewer samples than common search algorithms require. Lastly, I will conclude with a summary of the major takeaways of this work, and discuss potential extensions and future directions for the efficient sampling of useful experiences in RL.

1 0