April 2022 - talks - lists.cs.princeton.edu

Nanqinqin Li will present his General Exam "Achieving Cheap, Highly Available Fault Tolerance with Disaggregated Storage" on Friday, April 29, 2022 at 9:00 AM via Zoom
by Louis W. Riehl 27 Apr '22

27 Apr '22

Nanqinqin Li will present his General Exam "Achieving Cheap, Highly Available Fault Tolerance with Disaggregated Storage" on Friday, April 29, 2022 at 9:00 AM via Zoom. Zoom link: [ https://princeton.zoom.us/j/7608328107 | https://princeton.zoom.us/j/7608328107 ] Committee Members: Michael J. Freedman (advisor), Amit Levy, Ravi Netravali Abstract: High availability has long been achieved by replication at the application level. In a classic scheme called Primary-Backup, the primary application instance handles all client requests and forwards the execution log to the backup instances. Application-level replication, however, provides high availability at the cost of maintaining fully redundant replicas: they require as many resources (CPU, RAM, disk, etc.) as the primary. The ubiquity of disaggregated storage in cloud computing offers an attractive alternative. Instead of maintaining live replicas, a newly-launched backup instance recovers the application state from the underlying disaggregated storage where data is already replicated for high durability. This alternative provides fault tolerance at a much lower cost but suffers from long failover periods because it must sequentially first detects the primary failure and only then starts recovery on a backup instance. We propose speculative recovery to accelerate failover and improve the availability of this alternative. Instead of proceeding with failover sequentially, speculative recovery safely and efficiently parallelizes detecting primary failure and running recovery on a backup by using a clone of the application storage. Our implementation and evaluation show that speculative recovery reduces failover time considerably with similarly lower costs than application-level replication Reading List: [ https://docs.google.com/document/d/1gY1RS2JFBWmgG-X1TWq8JOxLnfZJ1eeiOX2Vtgm… | https://docs.google.com/document/d/1gY1RS2JFBWmgG-X1TWq8JOxLnfZJ1eeiOX2Vtgm… ] Everyone is invited to attend the talk, and those faculty wishing to remain for the oral exam following are welcome to do so. Louis Riehl Graduate Administrator Computer Science Department, CS213 Princeton University (609) 258-8014

1 0

Riley Simmons-Edler will present his FPO "Overcoming Sampling and Exploration Challenges in Deep Reinforcement Learning" on Tuesday, May 3, 2022 at 5:00 PM in CS 402 and Zoom.
by Louis W. Riehl 26 Apr '22

26 Apr '22

Riley Simmons-Edler will present his FPO "Overcoming Sampling and Exploration Challenges in Deep Reinforcement Learning" on Tuesday, May 3, 2022 at 5:00 PM in CS 402 and Zoom. Location: Zoom link: https://princeton.zoom.us/j/91838854729?pwd=MXhZOGtiem8wQkoyMjA4Z3hJNWxVQT09 and CS 402 The members of Riley’s committee are as follows: Examiners: H. Sebastian Seung (Adviser), Olga Russakovsky, Szymon Rusinkiewicz Readers: Karthik Narasimhan, Daniel Lee (Cornell Tech) A copy of his thesis is available upon request. Please email gradinfo(a)cs.princeton.edu if you would like a copy of the thesis. Everyone is invited to attend his talk. Abstract follows below: The combination of deep neural networks with reinforcement learning (RL) shows great promise for solving otherwise intractable learning tasks. However, practical demonstrations of deep reinforcement learning remain scarce. The challenges in using deep RL for a given task can be grouped into two categories, broadly “What to learn from experience?” and “What experience to learn from?” In this thesis, I describe work to address the second category. Specifically, problems of sampling actions, states, and trajectories which contain information relevant to learning tasks. I examine this challenge at three levels of algorithm design and task complexity, from algorithmic components to hybrid combination algorithms that break common RL conventions. In the first chapter, I describe 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 stability in training, computational efficiency, and precise inference. In the second chapter, I describe work on reward-aware exploration, the discovery of desirable behaviors where common sampling methods are insufficient. A teacher “exploration” agent discovers 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. In the third chapter, I describe 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. By combining deep Q-learning with a best-first tree search algorithm, it is possible to find solutions to program synthesis problems with dramatically fewer samples than with common search algorithms or RL alone. Lastly, I conclude with a summary of the major takeaways of this work, and discuss extensions and future directions for efficient sampling in RL. Louis Riehl Graduate Administrator Computer Science Department, CS213 Princeton University (609) 258-8014

1 0

Austin Hounsel will present his FPO "Measuring the Feasibility of DNS Privacy and Security" on Tuesday, 5/3/2022 at 1:00pm via Zoom.
by Nicki Mahler 26 Apr '22

26 Apr '22

Austin Hounsel will present his FPO "Measuring the Feasibility of DNS Privacy and Security" on Tuesday, 5/3/2022 at 1:00pm via Zoom. Zoom link: [ https://princeton.zoom.us/j/ | https://princeton.zoom.us/j/99974051371 ] His committee is as follows: Nick Feamster (adviser); Readers: Prateek Mittal and Kyle Jamieson; Examiners: Nick Feamster, Jennifer Rexford, Ravi Netravali. All are welcome to attend. Nearly every service on the Internet relies on the Domain Name System (DNS), which translates humanreadable names to IP addresses. Originally, the DNS was designed without security and privacy concerns in mind. This has left users’ DNS trac subject to eavesdropping, tampering, and censorship. In response, encrypted DNS protocols and DNS Security Extensions (DNSSEC) have seen increased deployment. Although these developments stand to improve users’ security and privacy, two questions remain unanswered. First, it is unclear whether encrypted DNS protocols yield acceptable performance for popular applications, such as web browsers. Second, it is unclear whether users can reliably retrieve and validate DNS records that are supposedly protected by DNSSEC. Without answers to these questions, popular applications may choose to not utilize these technologies, compromising the security and privacy of their users. This thesis studies the feasibility of deploying DNS security and privacy technologies for everyday use through various Internet measurements. We first measure the performance of encrypted DNS protocols from data centers and home networks through query response times and page load times. We find that although encrypted DNS protocols generally result in longer query response times than traditional, unencrypted DNS, these protocols can perform comparably with well-chosen connection timeouts, connection reuse, and the usage of popular recursive resolvers. We also find that despite generally higher query response times, web pages can load faster with encrypted DNS protocols. We then collaborate with a major browser vendor to measure how often users can successfully retrieve and validate records with DNSSEC. To do so, we deploy a measurement add-on to a globally-distributed random sample of the browser’s release users. The add-on issues requests for various records types for a domain name that we control using the browser’s locally configured recursive resolver. We find that many users were unable to retrieve the correct DNSSEC records they needed to perform validation. Such failure prevents users from being able to reliably determine whether their DNS trac is under attack or not.

1 0

Daniel Greenidge will present his General Exam "Efficient decoding of large-scale neural population responses with Gaussian-process multiclass regression" on Friday, April 29, 2022 at 3:00 PM via Zoom.
by Louis W. Riehl 26 Apr '22

26 Apr '22

Daniel Greenidge will present his General Exam "Efficient decoding of large-scale neural population responses with Gaussian-process multiclass regression" on Friday, April 29, 2022 at 3:00 PM via Zoom. Zoom link: [ https://princeton.zoom.us/j/99012342978 | https://princeton.zoom.us/j/99012342978 ] Committee Members: Jonathan Pillow (advisor), Adji Bousso Dieng, Ben Raphael Abstract: Linear classifiers are a tool used by neuroscientists to quantify the information content of neural population codes and the limits imposed by correlations in neural activity. However, the most commonly used classification methods are prone to overfitting on the high-dimensional, noisy datasets produced by modern neuroimaging technologies. Here, we introduce a novel classifier (also called “decoder” in the neuroscience literature) to overcome these limitations. Our approach, the Gaussian process multi-class decoder (GPMD), is well-suited to decoding a continuous low-dimensional variable from high-dimensional population activity, and provides a platform for assessing the importance of correlations in neural population codes. The GPMD is a multinomial logistic regression model with a Gaussian Process prior over the decoding weights. We provide a spectral variational inference method for fitting the GPMD to data, which scales to datasets with hundreds or thousands of neurons and performs especially well in datasets with more neurons than trials. We apply the GPMD to recordings from primary visual cortex in three different species: monkey, ferret, and mouse. Our classifier achieves state-of-the-art accuracy on all three datasets, and substantially outperforms independent Bayesian decoding, showing that knowledge of the correlation structure is essential for optimal decoding in all three species. We then use our classifier to examine the problems of model mismatch, cortical microcolumn structure, and how neural coding strategies are modulated in the presence of noise. Reading List: [ https://docs.google.com/document/d/1euprtAlmBXa7wBaI4u0kznMw5GfGDeyzB3Lb0jj… | https://docs.google.com/document/d/1euprtAlmBXa7wBaI4u0kznMw5GfGDeyzB3Lb0jj… ] Everyone is invited to attend the talk, and those faculty wishing to remain for the oral exam following are welcome to do so. Louis Riehl Graduate Administrator Computer Science Department, CS213 Princeton University (609) 258-8014

1 0

Thomas Macrina will present his FPO "Precise Alignment of Serial Section Electron Microscopy Images and Analysis of Neural Circuits" on Monday, May 2, 2022 at 6:00 PM via Zoom.
by Louis W. Riehl 26 Apr '22

26 Apr '22

Thomas Macrina will present his FPO "Precise Alignment of Serial Section Electron Microscopy Images and Analysis of Neural Circuits" on Monday, May 2, 2022 at 6:00 PM via Zoom. Zoom link: [ https://princeton.zoom.us/j/95405661874 | https://princeton.zoom.us/j/95405661874 ] The members of his committee are as follows: Examiners: H. Sebastian Seung (Adviser), Mala Murthy, Felix Heide Readers: Kai Li, Stephan Saalfeld (HHMI Janelia) A copy of his thesis is available upon request. Please email gradinfo(a)cs.princeton.edu if you would like a copy of the thesis. Everyone is invited to attend his talk. Abstract follows below: Neural circuits provide a means to test how the structure of a brain is related to its function, but reconstructing complete circuits in a whole mammalian brain is currently not possible. A promising path is to image a brain with serial section electron microscopy and use automatic methods to reconstruct circuits from the data. The imaging process introduces significant physical distortion that causes the automatic methods to make errors, so it’s crucial to remove the distortion in a step called alignment. There are existing approaches to alignment, and by augmenting them with human-in-the-loop intervention we were able to produce a very accurate alignment of a five teravoxel mouse cortex dataset. This approach failed to correct distortion caused by cracks and folds, and the amount of human effort involved made it prohibitively expensive to process larger datasets. To overcome these limitations, our group developed a new alignment pipeline that uses deep optic flow models to predict more precise distortion measurements. Using this new alignment pipeline, we have been able to accurately align much larger datasets, including a 100 teravoxel whole fly brain and a one petavoxel cubic millimeter of mouse cortex. These alignments enabled high quality automatic reconstructions that are now being proofread with manageable human effort to produce some of the largest neural circuits to date. With improvements in the reconstruction technology, like our new alignment pipeline, neural circuits are becoming more accessible, and there will be more effort put toward analyzing them. We analyzed a neural circuit reconstructed from the terascale mouse cortex dataset, finding that sizes of synapses in a shared layer 2/3 pyramidal neuron connection have a correlated binary component, and that the network of these pyramidal neurons is well-described by a configuration model. Both results may have implications for how to constrain biological models of memory or neural network organization. Louis Riehl Graduate Administrator Computer Science Department, CS213 Princeton University (609) 258-8014

1 0

Anja Kalaba will present her General Exam "Achieving High Availability for Cloud Applications with Disaggregated Storage" on 5/10/22 at 2pm via Zoom.
by Nicki Mahler 25 Apr '22

25 Apr '22

Anja Kalaba will present her General Exam "Achieving High Availability for Cloud Applications with Disaggregated Storage" on 5/10/22 at 2pm via Zoom. Zoom link: https://princeton.zoom.us/j/9544802809 Committee members: Amit Levy (adviser), Wyatt Lloyd, Ravi Netravali Abstract: The ubiquity of disaggregated storage in cloud computing has led to a nascent technique for fault tolerance: instead of utilizing application-level replication, newly-launched backup instances recover application state from disaggregated storage (REDS) after a primary’s failure. Attractively, REDS provides fault tolerance at much lower cost than traditional replication schemes, wherein at least two instances are running. Failover in REDS is slow, however, because it sequentially first detects primary failure and only then starts recovery on a backup. We propose speculative recovery to accelerate failover and thus increase the availability of applications using REDS. Instead of proceeding with failover sequentially, speculative recovery safely and efficiently parallelizes detecting primary failure and running recovery on a backup, by employing our new super and collapse primitives for disaggregated storage. Our implementation and evaluation of speculative recovery demonstrate that it considerably reduces failover time. [ https://docs.google.com/document/d/1R3sTjOaTBvFijwbzwy1kCDiGKYLuWvHjA_3NWDd… | https://docs.google.com/document/d/1R3sTjOaTBvFijwbzwy1kCDiGKYLuWvHjA_3NWDd… ]

1 0

Nicolas Koh will present his General Exam "A theory of non-linear integer arithmetic" on May 3, 2022 at 3pm in CS 302 and via Zoom
by Nicki Mahler 25 Apr '22

25 Apr '22

Nicolas Koh will present his General Exam "A theory of non-linear integer arithmetic" on May 3, 2022 at 3pm in CS 302 and via Zoom Zoom link: https://princeton.zoom.us/j/9776564874 The members of his committee are as follows: Zak Kincaid (adviser), David Walker, Aarti Gupta A theory of non-linear integer arithmetic Inferring and verifying non-linear arithmetic invariants in programs is fundamentally challenging not only because of high computational complexity, but in the case of integers, the theory is not even recursively axiomatizable. Nevertheless, invariants that arise in practice and the attendant reasoning involved may be far more tractable. In this talk, we give an axiomatization of a “weak” theory of non-linear integer arithmetic, and show how satisfiability for this theory can be decided using a mix of polynomial algebra and polyhedral geometry. At heart, the axioms enable the reduction of non-linear arithmetic to the linear setting, allowing standard techniques to be employed. [ https://docs.google.com/document/d/1yeSMXQq_-JWJDxNxSG2M8BzCOrAjgSrnTAa_kGM… | https://docs.google.com/document/d/1yeSMXQq_-JWJDxNxSG2M8BzCOrAjgSrnTAa_kGM… ] [ https://docs.google.com/document/d/1FWtbJwFMBV41njmMRS2IvtWa7i1s1OoFMnKPaED… | https://docs.google.com/document/d/1FWtbJwFMBV41njmMRS2IvtWa7i1s1OoFMnKPaED… ]

1 0

Sobhan Mir Yoosefi will present his FPO "Provable Reinforcement Learning with Constraints and Function Approximation" on Monday, 5/2/2022 at 3pm via Zoom.
by Nicki Mahler 25 Apr '22

25 Apr '22

Sobhan Mir Yoosefi will present his FPO "Provable Reinforcement Learning with Constraints and Function Approximation" on Monday, 5/2/2022 at 3pm via Zoom. Zoom Link: https://princeton.zoom.us/j/5269962765 Committee Members: Examiners: Chi Jin (adviser), Matthew Weinberg, Karthik Narasimhan Readers: Elad Hazan, Jason Lee All are welcome to attend. Abstract: Reinforcement learning (RL) has gained a surge of interest over the past years, fueled mainly by practical success and new applications in various domains. However, there is still a gap between our theoretical understanding of these RL techniques and their empirical success. In this thesis, we advance our understanding by studying reinforcement learning from a primarily theoretical point of view and designing provably efficient algorithms for two challenging settings of 1) reinforcement learning with constraints and 2) reinforcement learning with function approximation. 1) In standard reinforcement learning (RL), a learning agent seeks to optimize the overall reward. However, many key aspects of the desired behavior are more naturally expressed as constraints. For instance, the designer may want to limit the use of unsafe actions, increase the diversity of trajectories to enable exploration, or approximate expert trajectories when rewards are sparse. First, we propose an algorithmic scheme that can handle RL tasks with general convex constraints improving upon prior works that are either limited to linear constraints or lack theoretical guarantees. Second, focusing on sample-efficient exploration, we develop the first provably efficient algorithm for tabular episodic constrained RL with the ability to handle convex constraints as well as the knapsack setting. Finally, motivated by recent advances in reward-free RL, we propose a simple meta-algorithm such that given any reward-free RL oracle, the constrained RL problems can be directly solved with negligible overheads in sample complexity. 2) Finding the minimal structural assumptions that empower sample-efficient learning is one of RL's most important research directions. This thesis advances our understanding of this fundamental question by introducing a new complexity measure---Bellman Eluder (BE) dimension. We show that the family of RL problems of low BE dimension is remarkably rich, which subsumes a vast majority of existing tractable RL problems, including but not limited to tabular MDPs, linear MDPs, reactive POMDPs, low Bellman rank problems as well as low Eluder dimension problems. We further design a new optimization-based algorithm—GOLF, and reanalyze a hypothesis elimination-based algorithm—OLIVE (proposed in Jiang et al., 2017) . We prove that both algorithms learn the near-optimal policies of low BE dimension problems in a number of samples that is polynomial in all relevant parameters but independent of the size of state-action space. Our regret and sample complexity results match or improve the best existing results for several well-known subclasses of low BE dimension problems. Furthermore, moving towards a more challenging setting of partially observable RL, we study a new subclass of Partially Observable Markov Decision Processes (POMDPs). More specifically, motivated by the problem structure in several physical applications and a commonly used technique known as "frame stacking'', this work proposes to study a new subclass of POMDPs, whose latent states can be decoded by the most recent history of a short length m. We establish a set of upper and lower bounds on the sample complexity for learning near-optimal policies for this class of problems in both tabular and rich-observation settings (where the number of observations is enormous). Our results show that a short-term memory suffices for reinforcement learning in these environments.

1 0

Zeyu Ma will present his General Exam "Multiview Stereo with Cascaded Epipolar RAFT" on Monday, May 2, 2022 at 10:00 AM in CS 402 and via zoom.
by Louis W. Riehl 25 Apr '22

25 Apr '22

Zeyu Ma will present his General Exam "Multiview Stereo with Cascaded Epipolar RAFT" on Monday, May 2, 2022 at 10:00 AM in CS 402 and via zoom. Zoom link: https://princeton.zoom.us/j/4673688313 Committee Members: Jia Deng (advisor), Szymon Rusinkiewicz, Felix Heide Abstract: Multiview stereo (MVS) is an important task in 3D computer vision. It seeks to reconstruct a full 3D model, typically in the form of a dense 3D point cloud, from multiple RGB images with known camera intrinsics and poses. It is a difficult task that remains unsolved; the main challenge is producing a 3D model that is not only accurate but also complete, that is, no parts should be missing and all fine details should be recovered. Classical methods essentially formulate multiview stereo as an optimization problem, which seeks to find a 3D model that is most compatible with the observed images. The compatibility is typically based on some hand-designed notion of photo-consistency, assuming that pixels that are projections of the same 3D point should have similar appearance. Many of the latest results of multiview stereo are achieved by deep networks. In particular, many recent leading methods are variants of MVSNet, a deep architecture that consists of two main steps: (1) constructing a 3D cost volume in the frustum of a reference view, by warping features from other views, and (2) using 3D convolutional layers to transform, or regularize, the cost volume before using it to predict a depth map. The resulting depth maps, one from each reference view, are then combined to form a single 3D point cloud through a heuristic procedure. However, a drawback of MVSNet is that regularizing the 3D plane-sweeping cost volume using 3D convolutions can be costly in terms of computation and memory. Therefore, We propose CER-MVS (Cascaded Epipolar RAFT Multiview Stereo), a new approach based on the RAFT (Recurrent All-Pairs Field Transforms) architecture developed for optical flow. CER-MVS introduces five new changes to RAFT: epipolar cost volumes, cost volume cascading, multiview fusion of cost volumes, dynamic supervision, and multiresolution fusion of depth maps. CER-MVS is significantly different from prior work in multiview stereo as it operates by updating a disparity field. Experiments show that our approach achieves state-of-the-art performance on the DTU and Tanks-and-Temples benchmarks (both intermediate and advanced set). Reading List: https://docs.google.com/document/d/1ELU3MmNlojf4FnyrLcFScN7AsARx7cJCA0VvAnQ… Everyone is invited to attend the talk, and those faculty wishing to remain for the oral exam following are welcome to do so. Louis Riehl Graduate Administrator Computer Science Department, CS213 Princeton University (609) 258-8014

1 0

Joshua Gardner will present his MSE talk "The Prophet Paradox: Optimal Stopping with Multi-Dimensional Comparative Loss Aversion." on April 22, 2022 at 1:50pm via Zoom
by Nicki Mahler 22 Apr '22

22 Apr '22

Joshua Gardner will present his MSE talk "The Prophet Paradox: Optimal Stopping with Multi-Dimensional Comparative Loss Aversion." on April 22, 2022 at 1:50pm via Zoom Zoom link: [ https://princeton.zoom.us/j/7993507333 | https://princeton.zoom.us/j/7993507333 ] Committee members: Matt Weinberg (adviser) and Mark Braverman (reader) All are welcome to attend. Abstract: Recent work by Kleinberg et al. [9] explores the effects of loss aversion and reference dependence on the prophet inequality problem, where an online decision maker sees options one by one in sequence and must decide immediately whether to select the current option or forego it and lose it forever. In their model, the online decision-maker forms a reference point equal to the best candidate previously rejected, and the decision-maker suffers from loss aversion based on the quality of their reference point, and a parameter 1 that quantifies their loss aversion. We consider the same prophet inequality setup, but with options that have multiple features. The decision maker still forms a reference point, and still suffers loss aversion in comparison to that reference point as a function of 1, but now that reference point is a (hypothetical) combination of the best candidate seen so far in each feature. Despite having the same basic prophet inequality setup and model of loss aversion, conclusions in our multi-dimensional model differs drastically from the one-dimensional model of Kleinberg et al. [9]. For example, Kleinberg et al. [9] gives a tight closed-form on the competitive ratio that an online decision-maker can achieve as a function of 1, for any 1 ≥ 0. In our multi-dimensional model, there is a sharp phase transition: if k denotes the number of dimensions, then when ^ ≥ 7_,, no non-trivial competitive ratio is possible. On the other hand, when 1 <E, we give a tight bound on the achievable competitive ratio (similar to [91). As another example, 9 uncovers an exponential improvement in their competitive ratio for the random- order vs. worst-case prophet inequality problem. In our model with k ≥ 2 dimensions, the gap is at most a constant-factor. We uncover several additional key differences in the multi- and single-dimensional models.

1 0