June 2023 - talks - lists.cs.princeton.edu

Princeton Robotics Seminar: Vikas Sindhwani, Friday June 9 at 11am
by Emily C. Lawrence 12 Sep '23

12 Sep '23

Speaker: Vikas Sindhwani, Senior Staff Research Scientist, Google Deepmind Date: Friday, June 9, 2023 Time: 11am ET Location: Virtual, Zoom link: [ https://princeton.zoom.us/my/robotics | https://princeton.zoom.us/my/robotics ] Event page: [ https://robo.princeton.edu/seminar | https://robo.princeton.edu/seminar ] Title: Large Language Models with Eyes, Arms and Legs Abstract: To become useful in human-centric environments, robots must demonstrate language comprehension, semantic understanding and logical reasoning capabilities working in concert with low-level physical skills. With the advent of modern "foundation models" trained on massive datasets, the algorithmic path to developing general-purpose “robot brains” is (arguably) becoming clearer, though many challenges remain. In the first part of this talk, I will attempt to give a flavor of how state-of-the-art multimodal foundation models are built, and how they can be bridged with low-level control. In the second part of the talk, I will summarize a few surprising lessons on control synthesis observed while solving a collection of Robotics benchmarks at Google. I will end with some emerging open problems and opportunities at the intersection of dynamics, control and foundation models. Bio: Vikas Sindhwani is Research Scientist at Google Deepmind in New York where he leads a research group focused on solving a range of planning, perception, learning, and control problems arising in Robotics. His interests are broadly in core mathematical foundations of statistical machine learning, and in end-to-end design aspects of building large-scale and robust AI systems. He received the best paper award at Uncertainty in Artificial Intelligence (UAI-2013), the IBM Pat Goldberg Memorial Award in 2014, and was finalist for Outstanding Planning Paper Award at ICRA-2022. He serves on the editorial board of Transactions on Machine Learning Research (TMLR) and IEEE Transactions on Pattern Analysis and Machine Intelligence; he has been area chair and senior program committee member for NeurIPS, International Conference on Learning Representations (ICLR) and Knowledge Discovery and Data Mining (KDD). He previously headed the Machine Learning group at IBM Research, NY. He has a PhD in Computer Science from the University of Chicago and a B.Tech in Engineering Physics from Indian Institute of Technology (IIT) Mumbai. His publications are available at: http://vikas.sindhwani.org/

1 5

Clayton Thomas will present his FPO "Explainable Mechanism Design" on Wednesday, July 5, 2023 at 10am in CS 105.
by Nicki Mahler 29 Jun '23

29 Jun '23

Clayton Thomas will present his FPO "Explainable Mechanism Design" on Wednesday, July 5, 2023 at 10am in CS 105. Please see below for the members of his committee: Readers: Huacheng Yu, Ran Raz Examiners: Matt Weinberg (Adviser), Mark Braverman, and Leeat Yariv (Princeton Economics) Talk abstract follows below. All are welcome to join. Abstract: Mechanism design strives to construct protocols that achieve desirable outcomes in the presence of strategic behavior. Algorithmic mechanism design additionally factors in notions from theoretical computer science—the study of how efficiently these algorithms can communicate between and be implemented on computers. This thesis largely takes a different direction. We study how to effectively explain these algorithms and protocols to real humans. In Part I, we directly confront the objective of better explaining a certain canonical and widely-deployed class of algorithms, namely, matching mechanisms. To begin, we study certain prior frameworks for explanation, and find them to be very restrictive in this setting. Thus, we introduce a new framework for describing these algorithms to participants in a fundamentally different way, with the goal of exposing strategy proofness, a crucial property dictating one’s optimal behavior in these mechanisms. We propose new descriptions, conduct a laboratory experiment on real participants to test our framework, and prove rigorous theorems about the limits of simple descriptions in our framework (according to context-relevant formal notions of simplicity). Then, we investigate a host of additional types of descriptions and explanations using the theoretical tools we have developed. In Part II, we investigate other novel directions in algorithmic mechanism design that stem from running mechanisms in the real world. We provide two new, worst case separations in the communication requirements of certain canonical mechanism design problems: first, for incentivizing mechanisms vs. simply computing them; second, for providing strong incentive grantees vs. providing weak ones. We provide a framework for running more complex mechanisms with computationally limited bidders; this framework allows for a broad class of reasonable behaviors of the bidders, and guarantees good performance under modest computational resources. In Part III, we investigate perhaps more-traditional properties of matching mechiii anisms, the vital class of mechanisms studied in Part I. We provide new proofs of classical results on both the structure and dynamics of these mechanisms—some of these proofs are far simpler than known ones. Finally, we investigate a new random distribution over the preferences of agents in these mechanisms, characterizing the effect of heterogeneous attractiveness across different agents.

1 1

Jiaxin Guan will present his FPO "Cryptography against Space-Bounded Adversaries" on July 12, 2023 at 1pm in CS 105
by Nicki Mahler 22 Jun '23

22 Jun '23

Jiaxin Guan will present his FPO "Cryptography against Space-Bounded Adversaries" on July 12, 2023 at 1pm in CS 105 The members of his committee are as follows: Examiners: Mark Zhandry (Advisor), Gillat Kol, Ran Raz Readers: Mark Braverman, Matt Weinberg Abstract: Traditionally in cryptography, we consider adversaries that are time-bounded by making specific computational assumptions. In this thesis, I examine the scenario where the adversaries are space-bounded instead, i.e. the adversary can only use up to a certain amount of memory bits. Under these scenarios, we can achieve either unconditional security properties or never-before-possible results. First, we start off with Maurer's Bounded Storage Model. It is a model where the adversary abides to a certain memory bound throughout the entire game. Under this model, I show simple constructions of a key-agreement protocol, a commitment scheme, and an oblivious transfer protocol, all based on Raz's lower bound on parity learning. These constructions have several advantages over prior work, including an improved number of rounds and enhanced correctness. Subsequently, I show that if we combine computational assumptions with the bounded storage model, we can achieve results that are not possible in the standard model. I define a new object named Online Obfuscation, and show how to use it to construct disappearing encryption and signature schemes where the ciphertext and the signature effectively "disappear" after transmission. Lastly, I notice that in the Bounded Storage Model, the memory bound on the adversary is enforced throughout the entire game. One can imagine a variant where the bound is only enforced for long-term storage, allowing the adversary to use an arbitrary amount of memory during the transmission phase. I define incompressible cryptography to capture this intuition and show constructions using randomness extractors and other cryptographic tools. Furthermore, I show that under the multi-user setting, we can still achieve desired incompressible security if we simply replace the randomness extractor with a special "somewhere randomness extractor".

1 1

Ruairidh Battleday will present his FPO "The Role Of Nonparametric Inference In Computational Models Of Categorization And Analogy" on Thursday, June 29, 2023 at 1:00 PM in COS 401 and Zoom.
by gradinfo＠cs.princeton.edu 15 Jun '23

15 Jun '23

Ruairidh Battleday will present his FPO "The Role Of Nonparametric Inference In Computational Models Of Categorization And Analogy" on Thursday, June 29, 2023 at 1:00 PM in COS 401 and Zoom. Location: Zoom link: https://princeton.zoom.us/j/91969001576 The members of Ruairidh's committee are as follows: Examiners: Tom Griffiths (Adviser), Ryan Adams, Barbara Engelhardt Readers: Olga Russakovsky, Tania Lombrozo 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: This dissertation presents a computational investigation into the nature of human learning and inference. Its central thesis is that humans make good predictions in novel environments because they possess flexible abilities for inductive inference that can be used to generalize and update relevant knowledge abstracted from the past. This thesis is first explored in the context of natural image categorization. Here, participants' judgments are best captured by models that use probabilistic strategies to relate novel stimuli to existing category members, and techniques from deep learning to represent these stimuli in high-dimensional mathematical spaces. The second context is generalization, where the underlying structure of different training games is shown to affect participants' predictive generalizations on a final test game. These behaviors are accounted for by a nonparametric Bayesian model that aggregates mathematical abstractions of particular training environments, and then weights their predictions about unobserved interactions by their analogical relevance. Common to both lines of inquiry is the idea of using probabilistic models to account for flexible inferential behaviors, and tools from statistics and machine learning to abstract relevant mathematical representations from past experiences or stimuli.

1 0

Diana Cai will present her FPO "Probabilistic Inference When the Model is Wrong" on Wednesday, July 5, 2023 at 3:00 PM in COS 105.
by gradinfo＠cs.princeton.edu 15 Jun '23

15 Jun '23

Diana Cai will present her FPO "Probabilistic Inference When the Model is Wrong" on Wednesday, July 5, 2023 at 3:00 PM in COS 105. Location: COS 105 The members of Diana's committee are as follows: Examiners: Ryan Adams (Adviser), Barbara Engelhardt (Adviser), Olga Russakovsky Readers: Tom Griffiths, Tamara Broderick (MIT) A copy of her 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 her talk. Abstract follows below: By simplifying complex real-world phenomena, probabilistic methods have proven able to accelerate applications in discovery and design. However, classical theory often evaluates models under the assumption that they are perfect representations of the observed data. There remains the danger that these simplifications might sometimes lead to failure under real-world conditions. This dissertation identifies popular data analyses that can yield unreliable conclusions-and in some cases ones that are arbitrarily unreliable-under such "misspecification." But we also show how to practically navigate misspecification. To begin, we consider clustering, a mainstay of modern unsupervised data analysis, using Bayesian finite mixture models. Some scientists are interested not only in finding meaningful groups of data but also in learning the number of such clusters. We provide novel theoretical results and empirical studies showing that, no matter how small the misspecification, some common approaches, including Bayesian robustness procedures, for learning the number of clusters give increasingly wrong answers as one receives more data. But using imperfect models need not be hopeless. For instance, we consider a popular Bayesian modeling framework for graphs based on the assumption of vertex exchangeability. A consequence of this assumption is that the resulting graph models generate dense graphs with probability 1 and are therefore misspecified for sparse graphs, a common property of many real-world graphs. To address this undesirable scaling behavior, we introduce an alternative generative modeling framework and prove that it generates a range of sparse and dense scaling behaviors; we also show empirically that it can generate graphs with sparse power law scaling behavior. Finally, we consider the case where a researcher has access to a sequence of approximate models that become arbitrarily more complex at the cost of more computation, which is common in applications with simulators of physical dynamics or models requiring numerical approximations of some fidelity. In this case, we show how to obtain estimates as though one had access to the most complex model. In particular, we propose a framework for constructing Markov chain Monte Carlo algorithms that asymptotically simulates from the most complex model while only ever evaluating models from the sequence of approximate models.

1 0

Manik Dhar will present his FPO "Beyond the polynomial method: Kakeya sets over finite rings and high dimensional variants" on Friday, June 30, 2023 at 12pm in CS 105.
by Nicki Mahler 01 Jun '23

01 Jun '23

Manik Dhar will present his FPO "Beyond the polynomial method: Kakeya sets over finite rings and high dimensional variants" on Friday, June 30, 2023 at 12pm in CS 105. The members of his committee are as follows: Readers: Ran Raz and Huacheng Yu; Examiners: Zeev Dvir (adviser), Bernard Chazelle, and Noga Alon (Math Department) All are welcome to attend. Abstract follows below: A Kakeya Set in Fn is a set that contains a line in every direction. It has been known for over a decade that such sets must be large. This goes back to Dvir’s proof of the finite field Kakeya conjecture as posed by Wolff. Dvir’s proof uses the polynomial method to solve this problem. The problem over finite fields also has applications in psuedorandomness and is crucially used in the construction of currently state-of-the-art seeded mergers and extractors. Wolff’s motivation was to pose a possibly simpler problem whose resolution might help with solving the notoriously difficult Euclidean Kakeya conjecture. The Euclidean Kakeya problem also has many connections with analysis, PDEs, and combinatorics. This thesis will look at two generalizations of the finite field Kakeya problem. One where Fq is replaced by the ring Z/N Z and another where we look at higher dimensional analogues of this problem. In both cases, the polynomial method does not work - as over Z/N Z polynomials do not represent all functions and in the other case a degree d polynomial can have much larger than d roots over a higher dimensional affine flat. We will cover a series of results that solve these problems by extending and in some cases going beyond the polynomial method. We will also cover recent applications of the higher dimensional Kakeya problem to give a tight analysis of the behaviour of linear hashes. At a high level, we show that if we pick subspaces of large enough dimension in comparison to the size of a set then for a large fraction of them their every shift intersects with the set in close to the expected number of points.

1 1