Theses & Reports

---

Instructions for submitting a technical report or thesis.

You can find technical reports published prior to 1990 archived here.

• Ph.D. Thesis 2022 Enhancing Robustness through Domain Faithful Deep Learning Systems Balashankar, Ananth Abstract | PDF

  Title: Enhancing Robustness through Domain Faithful Deep Learning Systems

  Candidate: Balashankar, Ananth

  Advisor(s): Lakshminarayanan Subramanian

  Abstract:

  In high-stakes domains like health, socio-economic inference, and content moderation, a fundamental roadblock for relying on deep learning systems is that models' predictions diverge from established domain knowledge when deployed in the real world and fail to faithfully incorporate domain-specific structure. In this talk, I will focus on the design of Domain Faithful Deep Learning Systems, that translate expert-understandable domain knowledge and constraints to be faithfully incorporated into learning robust deep learning models. Through methodological contributions in causal-aware ML model design, constrained optimization, counterfactual data augmentation, and feature selection, I have addressed core research questions of “What data distributions do domain practitioners care about?'', “How to faithfully convert domain knowledge into model constraints for better generalization?'' and finally ``How to evaluate whether the ML models we learn are grounded in the domain knowledge and in what ways do they deviate?''. I will demonstrate how, through these new approaches to incorporating domain knowledge, I have been able to meaningfully improve performance in four real-world applications of news-based famine forecasting, medication recommendations, causal question answering, and toxicity detection in online social media. These causal-aware and robust prediction models I have developed in collaboration with the World Bank and Google have shown that incorporating domain-specific structure is essential for building robust predictive models.

• M.S. Thesis 2022 Symbolic Execution of GRASShopper Programs Cox, Eric Abstract | PDF

  Title: Symbolic Execution of GRASShopper Programs

  Candidate: Cox, Eric

  Advisor(s): Thomas Wies

  Abstract:

  Symbolic execution is a more efficient and viable alternative to implementing deductive verification tools to fully automate the formal verification of programs. Symbolic execution in many cases can provide performance gains over verification condition generation (VCG) based verification tools due to the fact that symbolic execution directly manipulates in-memory data structures.

   

  This thesis presents the design and implementation of a symbolic execution engine for the GRASSHopper programming language which already supports verification using VCG. The goal of this work was to adapt ideas from the symbolic execution engine from the Viper verification infrastructure language to the semantics of GRASSHopper and to demonstrate its utility on sample programs. We present a rigorous description of the operational semantics of the symbolic interpreter, discuss implementation details and illustrate the symbolic execution behavior on a set of sample programs.

   

  In order to explore interesting details around implementing a symbolic execution backend for GRASSHopper, this work introduced a method to support encoding of snapshots at the struct field level using injective functions. In addition, several language extensions were added to the GRASSHopper user-facing language and the intermediate representation. A few of these extensions will now allow support for finer-grained permissions for individual fields rather than granting permissions to all fields of structures, unfolding and folding of recursive predicates, and support for if-then-else expressions in predicate and heap-dependent functions.

   

• M.S. Thesis 2022 Program Unrolling by Abstract Interpretation for Probabilistic Proofs Feldan, Daniel Abstract | PDF

  Title: Program Unrolling by Abstract Interpretation for Probabilistic Proofs

  Candidate: Feldan, Daniel

  Advisor(s): Patrick Cousot

  Abstract:

  Zero-knowledge proofs are cryptographic protocols that enable one party to prove the validity of a statement to another party while revealing no additional information beyond the statement’s truth. These protocols have a myriad of applications, especially within the realm of cloud computing. Zero-knowledge protocols can be used to probabilistically verify cloud-computed program by first converting an input program into a boolean circuit, then using this circuit in a zero-knowledge proof system to show the correctness of the computed output. This work focuses on enhancing zero-knowledge proofs for practical implementation, as many of the current protocols are currently very computationally expensive.

  
  The primary contribution of this thesis is a formalization of a program transformation technique that combines abstract interpretation and program unrolling to analyze, transform and optimize a program before transforming it into a boolean circuit. By analyzing a program with an abstract interpreter while simultaneously unrolling it, we achieve a significantly more precise static analysis without the need for traditional widening and narrowing operations. This approach enables aggressive optimization of the unrolled program, reducing both the cost of transforming the program into a circuit, and the resulting circuit’s size

• Ph.D. Thesis 2022 Unstructured Mesh Generation and Repairing in the Wild Hu, Yixin Abstract | PDF

  Title: Unstructured Mesh Generation and Repairing in the Wild

  Candidate: Hu, Yixin

  Advisor(s): Daniele Panozzo

  Abstract:

  A mesh is a representation used to digitally represent the boundary or volume of an object for manipulation and analysis. Meshes can be used in many fields, including physical simulation in manufacturing, architecture design, medical scan analysis. In this thesis, we propose a series of meshing algorithms, named WildMeshing, that tackles one of the long-standing, yet fundamental, problems in geometry modeling: robustly and automatically generating high-quality triangle and tetrahedral meshes and repairing imperfect geometries in the wild. Different from existing methods that have assumptions about the input and thus often fail on real-world input geometries, WildMeshing provides strict guarantees of termination and is a black box that can be easily integrated into any geometry processing pipelines in research or industry.

  This thesis first investigates the problem of tetrahedralizing 3D geometries represented by piecewise linear surfaces. We propose an algorithm, TetWild, that is unconditionally robust, requires no user interaction, and can directly convert a triangle soup into an analysis-ready volumetric tetrahedral mesh. It relies on three core principles: hybrid geometric kernel, tolerance of the mesh relative to the surface input, and iterative mesh optimization with guarantees on the output validity. We then consider improving the algorithm efficiency for tetrahedralizing large-scale geometries. We design a new algorithm, fTetWild, that is based on the principles of TetWild but replaces the hybrid kernel with a floating-point kernel, which largely reduces runtime while keeping the same robustness. Next, this thesis explores meshing curved geometries. We start from the problem of triangulating 2D planar shapes whose boundaries are represented by curves. We introduce TriWild, an algorithm to robustly generate curved triangle meshes reproducing smooth feature curves, which leads to coarse meshes designed to match the simulation requirements necessary by applications and avoids the geometrical errors introduced by linear meshes.

  We test our algorithms on over ten thousand real-world input geometries and they achieve 100% success rate. Our methods generate meshes without any assumptions about the input while repairing the imperfect geometries, opening the door to automatic, large-scale processing of real-world geometric data.

• Ph.D. Thesis 2022 Data-driven Solutions for Addressing Two Pressing Urban Sustainability Challenges: Air Pollution Reduction and Traffic Management Iyer, Shiva Abstract | PDF

  Title: Data-driven Solutions for Addressing Two Pressing Urban Sustainability Challenges: Air Pollution Reduction and Traffic Management

  Candidate: Iyer, Shiva

  Advisor(s): Lakshmi Subramanian

  Abstract:

  Data Science and AI-driven solutions are abundant today for a large variety of practical applications. With a continuing focus on urban development and sustainability, in this thesis, I present our attempts in addressing two prominent urban challenges – urban air pollution control and road traffic congestion management. For both these applications, we have developed novel methods, such as the message-passing recurrent neural network, for predictive analytics and inference. The city of Delhi has 32 air quality monitors over an area of about 900 sq km, but we do not have information on fine-grained variations in air quality in the city in order to reason about citizen exposure and identify hotspots. We have installed 28 low-cost sensors, many of them concentrated in the south Delhi region. We have developed a generic definition of "hotspots" in terms of spatio-temporal variations, using which we validate some known hotspots and discover new ones. We have also designed a novel model combining geostatistics and deep learning that is able to make spatio-temporal pollution predictions by the hour with an MAPE of about 10% across all locations.

  In the context of urban traffic management, we first show that road networks can experience traffic jams over prolonged periods such as several hours due to sudden traffic bursts over short time scales. We illustrate this using real data from two different cities – New York and Nairobi. We provide a formalism for understanding the phenomena of traffic collapse and sudden jams. In the second work, we devise a novel model called the message-passing neural network for modeling the propagation of congestion within a road network and forecasting congestion. The MPRNN achieves the lowest mean error of < 0.3 mph when predicting ahead in 10 minute intervals, for up to 3 road segments ahead (message passing across 3 hops). Finally, in the third work, we describe an algorithm for signal control in free-flow road networks, inspired from congestion control in computer networks. Our proposed method significantly enhances the operational capacity of free-flow road networks in the real world by several orders of magnitude (between 3× and 5×) and prevents congestion collapse.

• Ph.D. Thesis 2022 Synergistic Geometry Processing: from Robust Geometric Modeling to Scalable Physical Simulation Jiang, Zhongshi Abstract | PDF

  Title: Synergistic Geometry Processing: from Robust Geometric Modeling to Scalable Physical Simulation

  Candidate: Jiang, Zhongshi

  Advisor(s): Daniele Panozzo

  Abstract:

  Various applications, from artistic creation, to scientific computing,
  require the processing and reasoning of 3D digital objects.
  The computational modeling of 3D geometric shapes, materials, and
  textures, as well as the simulation of their deformation and
  interactions, is essential to bring the algorithmic power of computing
  to real-life manufacture, architecture, and medical device design.
  Depending on the specific numerical properties, better algorithm
  designs might prefer 3D data with different representations, for
  example, in planes, surfaces, or inside volumes.

  This thesis investigates the problem related to the representations of
  data on 3D shapes and across different domains,
  so computations for different stages within a pipeline, may come
  together synergistically without manual tuning that disrupts an
  automated data flow.
  
  I propose novel geometrical principles in various geometric modeling
  and processing stages.  I also showcase various geometric computing
  applications that easily integrate such principles to guarantee the
  geometry validity and algorithm effectiveness of surface
  parameterization, rendering, deformation/animation, and mechanical
  simulation.
  In addition, we can finally explore creative solutions that reliably
  coarsen the surface. Such simplification accelerates everyday
  geometric modeling operations; the contribution also includes a
  scalable method to construct coarse and curved meshes for fast
  animation and scientific computing.
  
  Furthermore, the thesis provides a declarative way to formulate mesh
  processing and adaptation algorithms to facilitate the practical
  development of robust and reliable mesh processing software.
  Finally, the thesis includes extensive numerical validations involving
  tens of thousands of complex geometry shapes. And to maintain
  replicability and foster further research in this direction, I also
  released the implementation and generated data to be open source and
  accessible.
  
  Finally, the thesis includes extensive numerical validations involving
  tens of thousands of complex geometry shapes. %And to maintain
  replicability and foster further research in this direction, I also
  released the implementation and generated data to be open source and
  accessible.
   

• Ph.D. Thesis 2022 Cryptography: From Practice to Theory Karthikeyan, Harish Abstract | PDF

  Title: Cryptography: From Practice to Theory

  Candidate: Karthikeyan, Harish

  Advisor(s): Yevgeniy Dodis

  Abstract:

  This work is yet another attempt to turn an age-old adage on its head by deriving inspiration for theoretical research from problems that are germane to practitioners and real-world deployment. This could be viewed as a departure from the practice of creating real-world solutions that trace their origin to a theoretical research, or alternatively ex post facto theoretical analyses of practically deployed solutions that can be rather ad-hoc. Specifically, we look at four different problems that are relevant for practical deployment - random number generation, provably secure block ciphers, searching over encrypted data, and forward-secure group messaging.

• Ph.D. Thesis 2022 Scalable Distributed Payment Systems with Minimal Trust Assumptions Kattis, Assimakis Abstract | PDF

  Title: Scalable Distributed Payment Systems with Minimal Trust Assumptions

  Candidate: Kattis, Assimakis

  Advisor(s): Prof. Joseph Bonneau

  Abstract:

  Over the last decade, the security and resilience of Bitcoin
  as a stable payment network has motivated substantial study of the
  viability of distributed payment protocols, with many works focusing on their suitability as alternatives to centralized payment processing. We investigate the design of scalable distributed payment systems in the permissionless setting, where no actors in the protocol can be trusted or identified with out-of-band information. Scalability is identified with two desirable properties: high transaction processing rate (or throughput) and low confirmation latency (or settlement times). We analyze the trade-offs inherent to distributed protocols that prevent
  naive optimization of the above parameters and study techniques from verifiable computation as potential tools for overcoming these
  bottlenecks.
  
  One technique to increase throughput in distributed payment systems
  involves the use of Succinct Non-interactive ARguments of Knowledge
  (SNARKs, or SNARK proofs) to verify the integrity of transactions.
  Transaction rollups are one such solution, using SNARK computations to achieve scalability. Many instantiations of rollups leveraging SNARKs show encouraging evidence that this technique could achieve commercial- capacity throughput rates if implemented on top of current distributed payment systems, even in the smart-contract setting. Although promising, all rollup approaches require the resolution of an additional yet crucial question. For protocols operating in the permissionless setting, we need to ensure that a system relying on proof generation to scale also incentivizes actors to compute proofs cheaply and quickly. This is a governance problem, as the protocol needs to decide on how participants will be chosen to perform these (expensive) computations. We pose the question of who will compute the proofs, identify it as a consensus problem and provide a technical proposal towards its resolution.
  
  Our main contributions are twofold: in Part I, we design a
  permissionless consensus protocol that solves the problem of state
  verification for resource-limited clients in an incentive-compatible way. We show formal proofs of security and achieve minimal resource requirements for full ledger verification. This protocol showcases our key contribution: the design of a proof-of-work (PoW) process that computes SNARK proofs as valid outputs. Suitably choosing the statement whose proof is generated through PoW provides an incentive-compatible way to enforce the computation required by proof-based scaling techniques. In Part II, we look at one of the key components of SNARK- based throughput optimization: the non-interactive proof itself. We design a novel proof system which provides security guarantees in the trustless setting, while still being small and efficiently computable.
  This proof system (a transparent SNARK, or STARK) can be used directly for scaling throughput in distributed payments through transaction rollups. In conjunction with an incentivized PoW process, it also demonstrates a way for participants in consensus to quickly generate the rollup proofs in a permissionless way.
   

• Ph.D. Thesis 2022 Characterizing and Resolving Degeneracies in Neural Autoregressive Text Generation Kulikov, Ilia Abstract | PDF

  Title: Characterizing and Resolving Degeneracies in Neural Autoregressive Text Generation

  Candidate: Kulikov, Ilia

  Advisor(s): Kyunghyun Cho, Jason Weston

  Abstract:

  Autoregressive neural networks have shown great success as part of the sequence to sequence framework solving a diverse set of sequence generation tasks. These tasks include machine translation, dialogue modeling, question answering, text summarization, and sequence completion. In spite of the visible success, many challenges remain to be solved and are reported across these tasks. These challenges are usually discussed as visible deviations in the predicted sequence compared to the given reference. It is, however, not always possible to do the comparison, because interactive tasks, such as dialogue modeling, do not come together with reference sequences in the middle of the conversation at the test time. We refer to such deviations as \textit{degeneracies} which result in degenerate sequences. In this thesis, we work on reducing widely reported degeneracies within specific tasks or in text generation in general. To do so, we often first need to formulate the degeneracy in a measurable way and hypothesize what is the major cause behind it.
  We investigate the issue of oversmoothing, where the model assigns high probability to overly short sequences. We address this degeneracy from the learning aspect by proposing a novel regularization which minimizes the newly proposed oversmoothing rate directly. We show the effectiveness of the proposed method in the context of neural machine translation. Still concentrating on the learning aspect, we next address the problem of repetition in the context of sequence completion, where the generated sequences have unreasonably many repetitive substrings compared to the ones we see in the data. We propose a novel unlikelihood training procedure which allows to penalize undesired continuations, such as repetitive substrings. Unlikelihood training significantly reduces the number of repetitions and improves the naturalness of the generated continuations. One issue with the repetition degeneracy is that it can also lead to non-termination. We study if the original model is able to terminate the repetitive loop itself even if we do not enforce the maximum generated length during decoding. We connect this problem of non-termination with the consistency of the distribution induced by the chosen decoding algorithm. After proving that an incomplete decoding algorithm, such as beam search, may induce the inconsistent distribution when paired with a consistent model, we propose an alternative parametrization which guarantees the decoding-induced distribution to be consistent. After that, we switch to a more complicated scenario of conversation modeling, where the model has to generate a response in a multi-turn setting. We investigate the issue of unengaging or dull responses by highlighting the importance of the decoding algorithm. We observe a low diversity of beam search candidates compared to iterative beam search which explores a wider search subspace via efficient pruning. We find that the selection criterion is as important as the decoding strategy. Along the way, we stress the importance of careful human evaluation in the presence of annotator bias and calibrate the observed scores using Bayesian inference. While we address different kinds of degeneracy, the list we tackle is not exhaustive. For instance, neural machine translation is known to produce hallucinated translations or copy large parts of the input sentence. Furthermore, degeneracies exist past autoregressive modeling in both non-autoregressive and semi-autoregressive settings. We believe our contributions will be helpful for future research solving new problems.

   

• Ph.D. Thesis 2022 Finding and Fixing Undesirable Behaviors in Pretrained Language Models Perez, Ethan Abstract | PDF

  Title: Finding and Fixing Undesirable Behaviors in Pretrained Language Models

  Candidate: Perez, Ethan

  Advisor(s): Kyunghyun Cho

  Abstract:

  Natural Language Processing (NLP) promises to deliver tools for a variety of impactful applications, ranging from automatic summarization to question-answering systems and conversational assistants. Recently, NLP has been revolutionized by the advent of Pretrained Language Models (PLMs). We train PLMs using "self-supervised" learning objectives -- prediction tasks that operate on unlabeled text alone, such as next word prediction or missing word prediction. As a result, PLMs are able to learn from large quantities of internet text, to obtain strong performance on many NLP tasks.

  Despite the success of self-supervised objectives, they face a fundamental limitation: they train PLMs to behave in ways that are misaligned with human preferences. PLMs learn to repeat internet misinformation, offensive jokes, and personal contact information, and it is hard to control or guide the text that PLMs generate. Next, we show that PLM-based classifiers are effective at predicting which texts humans prefer. As a result, it is possible to use such classifiers as a learning signal to automatically correct the PLM. We showcase this approach to train a high-quality retrieval system, obtaining strong performance across a variety of tasks using Retrieval-Augmented Generation (RAG). Even after such training schemes, some undesirable behaviors may remain undetected during training. We thus go a step further and generate inputs that elicit undesirable behaviors from the PLM using other PLMs, to preemptively find and fix such behaviors. Overall, we find that some of the most powerful tools for aligning PLMs with human preferences are PLMs themselves.

• Ph.D. Thesis 2022 Identifying, Addressing, and Understanding Challenging Cases in Machine Learning Resnick, Cinjon Abstract | PDF

  Title: Identifying, Addressing, and Understanding Challenging Cases in Machine Learning

  Candidate: Resnick, Cinjon

  Advisor(s): Kyunghyun Cho/Joan Bruna

  Abstract:

  Machine learning has advanced tremendously this past decade. Object
  detection systems routinely perform beyond human-level accuracy with
  no loss in speed, game-playing agents play at superhuman level in real
  time, and generative models write language useful enough for
  downstream products. And yet, autonomous vehicles (AV) crash due to
  surprising mistakes, the best gaming agents lose to simple strategies,
  and our language models produce nonsensical utterances at a
  surprisingly high rate. I could have chosen examples from any field
  because these failures are not endemic to just vision, games, or
  language. There are always challenging cases remaining after training
  our system, and these cases are where the systems fail.

  This thesis focuses on the challenging cases in a machine learning
  system in order to improve its overall capabilities. In the first
  part, we study methods for identifying the challenging cases, an
  important precursor for improving the system. In the second part, we
  then study methods for addressing the challenging cases, arguably the
  most important part of this thesis for real-world applicability. And
  in the third part, we study methods for understanding the root cause
  of challenging cases, an important step in attaining guarantees about
  our system's capabilities. As machine learning is practiced in many
  different settings, our study does too. We explore these questions in
  the context of computer vision, language learning, and task learning.
  The connecting thread among them is the drive towards creating a
  communicative and visually aware robot that can capably complete
  household tasks. In that context, we present in parallel the Machine
  Learning Application Framework that highlights where our contributions
  improve downstream applications.

  All together, this work studies how to identify, address, and
  understand the most challenging cases over a diverse array of machine
  learning systems. This research is imperative towards deploying many
  systems that we care about, including most autonomous vehicles and
  health assistants. Consequently, it represents an important step
  towards society's technological goals.

• Ph.D. Thesis 2022 Constrained Surface Parameterization Methods with Guarantees Shen, Hanxiao Abstract | PDF

  Title: Constrained Surface Parameterization Methods with Guarantees

  Candidate: Shen, Hanxiao

  Advisor(s): Denis Zorin/Daniele Panozzo

  Abstract:

  Surface parameterization for piecewise-linear surfaces is a
  fundamental problem in computer graphics and geometry processing. The
  generation of surface parameterization is a key step in numerous
  applications like texture mapping, remeshing, quadrangulation,
  inter-surface mapping, and shape-analysis.

  Due to its popularity, the robustness of mapping
  generation methods plays a major role in its applicability. In
  addition, depending on the specific requirements of the application at
  hand, various formulations of constraints are used to control or guide
  the parameterization.
  Typical examples of the constraints are point constraints, curvature
  constraints, and topological constraints. In many practical cases, to
  ensure that the input assumptions of downstream algorithms are
  satisfied, the constraints, such as need to be imposed exactly (as
  opposed, e.g., to approximation via penalties).

  In this work, we investigate different
  constraint formulations suitable for various applications and present
  algorithms with guarantees to generate parameterization fully
  satisfying these constraints. In the first part of this thesis, we
  develop an algorithm that solves the
  classical problem of mapping a disk domain with boundary constraints;
  in the special case of domains with convex boundary, it improves, in
  terms of robustness, on the classical Tutte's algorithm. Utilizing it
  as a building block, we design a parameterization method that supports
  arbitrary positional constraints. In the second part, building on
  recent developments in the theory of discrete uniformization, we
  develop a highly robust algorithm for discrete conformal maps that
  satisfy prescribed curvature constraints. In the third part, we
  provide a constructive proof for the existence of globally seamless
  parameterization that matches admissible user-prescribed cone position
  and curvature constraints. Lastly, we generalize this to constraints
  on holonomy angles on a homology basis of loops, which fully capture
  the topology of seamless parameterizations. This method yields
  parameterizations that are very close to field-aligned
  parametrizations obtained using commonly used methods but, in contrast
  to these methods, guarantees the existence of solution satisfying all
  constraints.

• Ph.D. Thesis 2022 On deep learning tools for scientific discovery in healthcare Sudarshan, Mukund Abstract | PDF

  Title: On deep learning tools for scientific discovery in healthcare

  Candidate: Sudarshan, Mukund

  Advisor(s): Rajesh Ranganath/Oded Regev

  Abstract:

  Scientists validate hypotheses by building mathematical models of the
  real world. They make inferences by checking if their models are
  supported by data. Often, the models are hand-crafted and do not
  accurately reflect real processes. This often leads to low power to
  make scientific discoveries or even false discoveries.

  
  Machine learning can solve these issues in several ways. By allowing
  data to inform the construction of models, scientists can use machine
  learning to create more powerful statistical hypothesis testing
  procedures, or build more realistic models of underlying processes.
  
  This thesis details techniques to address both of these approaches.
  First we address the creation of machine learning-based statistical
  discovery procedures for scientific discovery. Specifically, we
  discuss how machine learning can be used to construct conditional
  independence tests, which are used to identify causal links in data.
  
  We detail how such methods can be used to control the false discovery
  rate when testing multiple hypotheses. We then apply these techniques
  to two important domains. We solve a timely problem in medical
  informatics: identifying a small set of variables that are highly
  informative of whether an ICU patient with Covid will experience an
  adverse event. At the height of Covid in 2020, NYU doctors used a
  deployed version of this tool to quickly identify patients to
  discharge and free up beds in the ICU. We also apply our methods to a
  problem in cancer genomics, where the goal is to identify a set of
  gene mutations that are most predictive of tumor metastasis. In the
  near future, we expect tools like ours to lead to targeted gene
  therapies that tailor treatments to the mutations present in an
  individual's tumor.

  
  Next we detail the construction of an interpretable machine learning
  model that helps understand an important step in the creation of
  proteins. Specifically, we build a model to understand RNA splicing,
  which involves removing non-coding regions from precursor messenger
  mRNA (pre-mRNA) and joining coding regions together. Our model
  accurately models splicing outcomes across a large dataset of
  sequences, but more importantly leads to several biologically
  validated insights. We use the interpretable nature of our model to
  infer that most splicing decisions are a function of a small set of
  short sequence features. We also learn that certain pre-mRNA secondary
  structures strongly inhibit the inclusion of a coding region in the
  final mRNA transcript. Finally, we validate these model-driven
  findings by carefully designing experiments for the wet lab.

   

• Ph.D. Thesis 2022 Efficient Verification of Untrusted Services Tzialla, Ioanna Abstract | PDF

  Title: Efficient Verification of Untrusted Services

  Candidate: Tzialla, Ioanna

  Advisor(s): Michael Walfish

  Abstract:

  Using a third-party service today requires trusting that it is executing as promised. Meanwhile, the correct execution of services is regularly impeded by failures, bugs, misconfigurations, operational mistakes, and insider attacks. Is it possible to verify, instead of trust, that a third-party service executes correctly?
  
  We study this question for two services that execute on remote servers: transparency dictionaries, a foundational infrastructure for end-to-end encryption and other applications, and event-driven web applications. For each of these two services, we leverage their workloads to introduce a practical system that allows a verifier to get a strong security guarantee that the service executes correctly.
  
  In the case of a transparency dictionary, this guarantee is in the form of a cryptographic proof provided by the service. Producing cryptographic proofs typically requires high resource costs. We show that tailoring the cryptographic tools used by the transparency dictionary for its use case mitigates these costs and results in a system, Verdict, that scales to dictionaries with millions of entries while imposing modest overheads on the service and its clients.
  
  In the case of outsourced event-driven web applications, the verifier gets the required guarantee by replaying the requests on a trusted machine using Karousos, a novel record-replay system in which the service has the role of the untrusted recorder. Karousos takes advantage of the particular characteristics of event-driven web applications to enable the replayer (the verifier) to use less computational resources than the recorder (the service), while imposing tolerable overheads on the
  recorder and keeping communication small.

• Ph.D. Thesis 2022 NLP Evaluation in the Time of Large Language Models Wang, Alex Abstract | PDF

  Title: NLP Evaluation in the Time of Large Language Models

  Candidate: Wang, Alex

  Advisor(s): Kyunghyun Cho

  Abstract:

  The field of natural language processing (NLP) has been
  >dramatically impacted by the creation and proliferation of large
   language models that are pretrained on Internet-scale text data. These
   models have led to significant improvements on a myriad of NLP tasks.
   However, as the capabilities of these models drive up performance on
   existing task benchmarks, there is a critical need for evaluation
   metrics that are up-to-date with current models. In this dissertation,
   we develop NLP evaluation methodologies that benchmark and leverage
   pretrained language models. We first present two multi-task benchmarks
   for evaluating the generalization ability of NLP models and discuss
   the role of these benchmarks in the development of large language
   models. Next, we demonstrate that we can leverage the capabilities of
   pretrained language models to develop new automatic evaluation metrics
   that better measure the semantics of model-generated text.
   Specifically, we make use of the question answering abilities of
   pretrained models to evaluate the faithfulness of automatically
   generated summaries. Finally, we explore methods for crowdsourcing
   high-quality and challenging text generation data to address issues of
   data quality that have been surfaced by the ability of language models
   to replicate noise in benchmark datasets. Overall, we show that the
   rise of pretrained language models presents both challenges and
   opportunities in how we evaluate NLP systems, and that incorporating
   these very models into our evaluation methodologies offers a promising
   path forward.

• Ph.D. Thesis 2022 Improving Sample Efficiency in Off-policy and Offline Deep Reinforcement Learning Wu, Yanqiu (Autumn) Abstract | PDF

  Title: Improving Sample Efficiency in Off-policy and Offline Deep Reinforcement Learning

  Candidate: Wu, Yanqiu (Autumn)

  Advisor(s): Keith Ross

  Abstract:

  Reinforcement Learning (RL) is an area of Machine Learning, where agents are trained through trial and error to make a sequence of decisions in some given environment to achieve a goal. Traditional reinforcement learning methodology suffers from the curse of dimensionality. Fortunately, with the help of deep learning, Deep Reinforcement Learning (DRL) can overcome the issue and can often find high performing policies for applications with large state and action spaces. Over the past few years, DRL has achieved major breakthroughs in complex tasks, such as outperforming human players in video games [Mnih et al. 2013; Vinyals et al. 2019], defeating the human world champion in Go [Silver et al. 2016, 2018] and autonomous robotics control [Lillicrap et al. 2019; Haarnoja et al. 2018a].
  
  Despite the recent breakthroughs, sample efficiency remains an important issue in deep reinforcement learning. In some complex tasks, where data collection is very expensive and agents require relatively few interactions with the environment for training, sample efficiency is of central concern for making DRL practical for applications. This thesis addresses the sample efficiency problem in the context of off-policy and offline Deep Reinforcement Learning. We develop training algorithms which not only lead to high asymptotic performing policies, but are also highly sample efficient in both on-line and offline settings. We demonstrate the performance of our methods in simulated robotic locomotion environments.
  
  In the first part of this thesis, we develop a streamlined off-policy algorithm that utilizes an output normalization scheme and non-uniform sampling. We identify the squashing exploration problem and show how maximum entropy DRL [Haarnoja et al. 2018a,b] helps to resolve it. Based on our observation, we develop an alternative output normalization scheme to maximum entropy algorithms. We show that this normalization scheme can then be combined with non-uniform sampling, resulting in high performing policies. Next, we develop a simple off-policy algorithm that takes advantage of a high update-to-data (UTD) ratio and Q-ensembles which demonstrates superior sample efficiency in early-stage training and also achieve high asymptotic performance in late-stage training. We employ Q-ensembles and keep several lowest values for updating to address the overestimation bias. Finally, we consider offline deep reinforcement learning. We introduce the novel notion of “upper envelope of the data” and then develop an Imitation-Learning based algorithm based on the notion. Our algorithm is computationally much faster and achieves state-of-the art performance.
   

• Ph.D. Thesis 2022 On-Policy Deep Reinforcement Learning — The Discounted and Average Reward Criteria Zhang, Yiming Abstract | PDF

  Title: On-Policy Deep Reinforcement Learning — The Discounted and Average Reward Criteria

  Candidate: Zhang, Yiming

  Advisor(s): Keith Ross

  Abstract:

  Reinforcement Learning (RL) is the study of sequential decision making where an agent attempts to maximize its overall cumulative reward in some given environment. Combined with deep learning, reinforcement learning has made remarkable strides in the past decade in complex tasks such as playing video games (Mnih et al. 2013, Vinyals et al. 2019), playing Go (Silver et al. 2016, 2018), robotics (Lillicrap et al. 2016, Haarnoja et al. 2018), and chip design (Mirhoseini et al. 2021). However despite these successes, modern RL algorithms often suffer from poor sample efficiency and lack of safety guarantees. In this thesis we tackle these issues in the context of on-policy Deep Reinforcement Learning (DRL), both theoretically and algorithmically. This work addresses both the discounted and average reward criteria. In the first part of this thesis, we develop theory for average reward on-policy reinforcement learning by extending recent results for local policy search. We show that previous work based on the discounted return (Schulman et al. 2015, Achiam et al. 2017) results in a non-meaningful bound in the average-reward setting. By addressing the average-reward criterion directly, we derive a novel bound which depends on the average divergence between the two policies and Kemeny's constant. Based on this bound, we develop an iterative procedure which produces a sequence of monotonically improved policies for the average reward criterion. We show that this iterative procedure can then be combined with classic deep reinforcement learning methods, resulting in practical DRL algorithms that target the long-run average reward criterion. Next, we develop a unifying framework for the on-policy sample efficiency problem. This methodology uses a two-step approach which first learns an optimal policy in the non-parameterized policy space before projecting said policy back into the parameter space. Our approach is general in that it applies to both discrete and continuous action spaces, and can handle a wide variety of proximity constraints. Finally we address the problem of reinforcement learning with safety constraints. We provide theoretical support that trust region-based methods can be applied to problems with both discounted and non-discounted cost constraints. We then propose a novel first-order algorithm for policy optimization for maximizing an agent's cumulative reward while at the same time satisfying a set of cost constraints. Our algorithm is extremely simple to implement and has an approximate upper bound for worst-case constraint violation throughout training.