Theses & Reports

---

Instructions for submitting a technical report or thesis.

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

• Ph.D. Thesis 2023 On Matching Problems in Large Settings Agarwal, Ishan Abstract | PDF

  Title: On Matching Problems in Large Settings

  Candidate: Agarwal, Ishan

  Advisor(s): Richard Cole

  Abstract:

  Matching problems arise in several settings in practice and have been a longstanding subject of theoretical analysis. Typically, the settings of interest involve a large number of agents. We further the study of matching problems in two settings: the stable matching setting, which has been studied since the seminal work of Gale and Shapley, and a setting where agents' values to prospective partners degrade over time, leading them to have to balance the trade-off between searching for a better partner versus deciding to match.
  
  In the stable matching setting, we extend a line of research that seeks to explain the dichotomy between the fact that Gale and Shapley's Deferred Acceptance algorithm seems to work well in practice, even when agents only submit a short list of prospective partners to the centralized matching algorithm, and the fact that if the agents' preferences are allowed to be arbitrary, complete lists of all agents' preferences are needed in order to guarantee a stable matching. To this end, we consider probabilistically generated preference lists and we show that under fairly general assumptions and in a variety of models, with high probability, short lists of prospective partners, namely length $\Theta (\log n)$ instead of $n$, suffice for most of the agents. We prove our bounds are tight up to constant factors. Furthermore, we construct a simple set of $\Theta (\log n)$ possible matches per agent for almost all agents and demonstrate (in the form of an approximate equilibrium result) that they can afford to restrict their proposals to this set, while incurring only a small loss in utility.
  
  In the time discounted utilities setting, we consider a dynamic matching market, and study how agents should balance accepting a proposed match with the cost of continuing their search. Our model has two new features: finite agent lifetimes with linear loss in utility over time, and a discrete population model, aspects which are underexplored in the literature. We quantify how well the agents can do by providing upper and lower bounds on the collective losses of the agents, with a polynomially small failure probability, where the notion of loss is with respect to a plausible baseline we define. These bounds are also tight up to constant factors.
  
  In both settings, we complement our theoretical results with numerical simulations.
   

• Ph.D. Thesis 2023 Function Space Reasoning in Gaussian Processes and Neural Networks Benton, Gregory Abstract | PDF

  Title: Function Space Reasoning in Gaussian Processes and Neural Networks

  Candidate: Benton, Gregory

  Advisor(s): Andrew Gordon Wilson

  Abstract:

  In a typical modeling setting we have prior notions of what types of functions we want to learn. For example, in regression we may want to learn a smooth function or a periodic function and in image classification we may want to learn a function that is invariant to rotations. While function space provides us the benefit of being able to reason about traits like invariance or smoothness, it is often difficult to directly quantify the functional properties of models, in particular for large parametric models like neural networks.
  
  In this thesis we leverage our ability to reason about function space to build more powerful models in both Gaussian processes (GPs) and neural networks. By generating GP kernels as functions themselves of latent processes, we introduce methods for providing uncertainty over what types of functions we produce, not just over the functions themselves in GP models. We also introduce methods for learning levels of invariance and equivariance in neural networks, enabling us to imbue the functions our models produce with soft or limited equivariance constraints. Finally, we show how we can leverage our understanding of parameter space in neural networks to efficiently ensemble diverse collections of functions to improve the accuracy and robustness of our models. Through the introduction of these methods we show that by carefully considering the types of functions we are producing we can describe models with a range of desirable properties. These properties include more flexible models, models that better align with domain knowledge, and models that are both accurate and robust. We demonstrate these results on a broad range of problems, including time series forecasting, image classification, and reinforcement learning.
   

• Ph.D. Thesis 2023 Bridging the Gap from Supervised Learning to Control Brandfonbrener, David Abstract | PDF

  Title: Bridging the Gap from Supervised Learning to Control

  Candidate: Brandfonbrener, David

  Advisor(s): Joan Bruna

  Abstract:

  he combination of deep learning and internet-scale data with supervised
  learning has led to impressive progress in recent years. However, the
  potential of this progress has yet to be realized in the context of
  control problems beyond games that are easy to simulate. This thesis
  attempts to bridge this gap so as to leverage tools from supervised
  learning to solve control problems. To do this, we focus on the offline
  reinforcement learning setting which attempts to learn a control policy
  from a fixed dataset rather than requiring the policy to learn and
  collect data at the same time. This removes issues of non-stationary
  training data and exploration from the control problem, which allows the
  more straightforward application of tools from supervised learning.
  
  We study this intersection between supervised learning and control from
  several angles. In the first part of the thesis, we present work on
  policy learning, focusing on simplified algorithms that look more like
  standard supervised algorithms. In the second part, we move one step
  earlier in the pipeline and consider how to best collect datasets for
  offline reinforcement learning. And in the last part, we consider how to
  design pretraining objectives to learn representations for downstream
  offline policy learning. Taken together, these contributions present a
  view of the promise and challenges that face the application of machine
  learning to control problems.
   

• Ph.D. Thesis 2023 Provably Robust and Accurate Methods for Rigid and Deformable Simulation with Contact Ferguson, Zachary Abstract | PDF

  Title: Provably Robust and Accurate Methods for Rigid and Deformable Simulation with Contact

  Candidate: Ferguson, Zachary

  Advisor(s): Daniele Panozzo

  Abstract:

  Contacts are essential to virtually every aspect of life and play a vital role in many physical phenomena. Because of this, the study of contact mechanics has a deep wealth of knowledge. Surprisingly, however, simulating contact is a challenge with many parameters to carefully adjust. Incorrect parameters can result in numerical explosions, intersections, and other failures. Our research seeks to address these problems by developing robust methods that can handle arbitrary scenarios with guaranteed success.
  
  In this thesis, we introduce the Incremental Potential Contact (IPC) method. IPC is the first simulation algorithm for deformable and rigid bodies that is unconditionally robust, requires minimal parameter tuning, and provides a direct way of controlling the trade-off between running time and accuracy. We further back up these claims by providing a large-scale benchmark of continuous collision detection (CCD) algorithms (a core component of the IPC method) based on their efficiency and correctness. As part of this study, we introduce the first efficient CCD algorithm that is provably conservative. For extended accuracy and efficiency, we show how nonlinear geometry and function spaces can be used within the IPC framework. Finally, we introduce the first physically-based adaptive meshing strategy which produces more accurate discretizations depending on elastic, contact, and frictional forces.
  
  This work and our open-source implementations have quickly garnered attention from the computer graphics, mechanical engineering, and biomechanical engineering communities for their robustness and ability to seamlessly handle scenarios that have long been a challenge. This marks a large step towards democratizing simulation tools for design, robotics, biomechanical, and visual effects applications, among others.
  
   

• Ph.D. Thesis 2023 Understanding and Incorporating Mathematical Inductive Biases in Neural Networks Finzi, Marc Abstract | PDF

  Title: Understanding and Incorporating Mathematical Inductive Biases in Neural Networks

  Candidate: Finzi, Marc

  Advisor(s): Andrew Gordon Wilson

  Abstract:

  To overcome the enormous sample complexity of deep learning models, we can leverage basic elements of human and scientific knowledge and imbue these elements into our models. By doing so, we can short-circuit the thousands of years of evolutionary development that has enabled such rapid learning in humans, and the development of science which provides a framework to fit new knowledge into. In this work I develop new methods for incorporating mathematical inductive biases into our models, biasing them towards solutions that reflect our priors and our knowledge. This work helps to broaden the scope and automation of equivariant model construction across diverse domains, uncover the role of inductive biases in learning and generalization, and developing new machine learning models for scientific applications, capturing relevant scientific knowledge.

• Ph.D. Thesis 2023 Deconstructing Models and Methods in Deep Learning Izmailov, Pavel Abstract | PDF

  Title: Deconstructing Models and Methods in Deep Learning

  Candidate: Izmailov, Pavel

  Advisor(s): Andrew Gordon Wilson

  Abstract:

  Machine learning models are ultimately used to make
  decisions in the real world, where mistakes can be incredibly costly.
  We still understand surprisingly little about neural networks and the
  procedures that we use to train them, and, as a result, our models are
  brittle, often rely on spurious features, and generalize poorly under
  minor distribution shifts. Moreover, these models are often unable to
  faithfully represent uncertainty in their predictions, further
  limiting their applicability. In this dissertation, I present results
  on neural network loss surfaces, probabilistic deep learning,
  uncertainty estimation and robustness to distribution shifts. In each
  of these works, we aim to build foundational understanding of models,
  training procedures, and their limitations, and then use this
  understanding to develop practically impactful, interpretable, robust
  and broadly applicable methods and models.

• Ph.D. Thesis 2023 Learning structured and stable reduced models from data with operator inference Sawant, Nihar Abstract | PDF

  Title: Learning structured and stable reduced models from data with operator inference

  Candidate: Sawant, Nihar

  Advisor(s): Benjamin Peherstorfer

  Abstract:

  Operator inference learns low-dimensional dynamical-system models with polynomial nonlinear terms from trajectories of high-dimensional physical systems (non-intrusive model
  reduction). This work focuses on the large class of physical systems that can be well described by models with quadratic and cubic nonlinear terms and proposes a regularizer for
  operator inference that induces a stability bias onto learned models. The proposed regularizer is physics informed in the sense that it penalizes higher-order terms with large norms and
  so explicitly leverages the polynomial model form that is given by the underlying physics.
  This means that the proposed approach judiciously learns from data and physical insights
  combined, rather than from either data or physics alone. A formulation of operator inference
  is proposed that enforces model constraints for preserving structure such as symmetry and
  definiteness in linear terms. Additionally, for a system of nonlinear conservation laws, we
  enforce model constraints that preserve the entropy stability of the dynamical system. Numerical results demonstrate that models learned with operator inference and the proposed
  regularizer and structure preservation are accurate and stable even in cases where using no
  regularization and Tikhonov regularization leads to models that are unstable.

• Ph.D. Thesis 2023 Continuous LWE and its Applications Song, Min Jae Abstract | PDF

  Title: Continuous LWE and its Applications

  Candidate: Song, Min Jae

  Advisor(s): Oded Regev/Joan Bruna

  Abstract:

  Efficiently extracting useful information from high-dimensional data is a major challenge in machine learning (ML). Oftentimes, the challenge comes not from a lack of data, but from its high dimensionality and computational constraints. For instance, when data exhibits a low-dimensional structure, one could in principle exhaustively search over all candidate structures, and obtain estimators with strong statistical guarantees. Of course, such brute-force approach is prohibitively expensive in high dimensions, necessitating the need for computationally efficient alternatives. When our problem, however, *persistently* eludes efficient algorithms, we may find ourselves asking the following perplexing question: is the failure due to our lack of algorithmic ingenuity or is the problem just too hard? Is there a *gap* between what we can achieve statistically and what we can achieve computationally?
  
  This thesis is one attempt at answering such questions on the computational complexity of statistical inference. We provide results of both positive and negative nature on the complexity of canonical learning problems by establishing connections between ML and lattice-based cryptography. The Continuous Learning with Errors (CLWE) problem, which can be seen as a continuous variant of the well-known Learning with Errors (LWE) problem from lattice-based cryptography, lies at the center of this fruitful connection.
  
  In the first part of this thesis, we show that CLWE enjoys essentially the same average-case hardness guarantees as LWE. This result has several important applications. For example, it shows that estimating the density of high-dimensional Gaussian mixtures is computationally hard, and gives rise to "backdoored" Gaussian distributions that can be used to plant undetectable backdoors in ML models and construct novel public-key encryption schemes.
  
  Next, we focus on the "backdoored" Gaussian distributions, which we refer to as Gaussian Pancakes, and the problem of distinguishing these distributions from the standard Gaussian. We provide several evidence for the hardness of this distinguishing problem based on a reduction from CLWE and lower bounds against restricted classes of algorithms, such as algorithms that compute low-degree polynomials of the observations.
  
  Finally, we end on a positive note by showing that the Lenstra-Lenstra-Lovasz (LLL) algorithm, commonly used in computational number theory and lattice-based cryptography, has surprising implications for noiseless inference. In particular, we show that LLL solves both CLWE and Gaussian Pancakes in the noiseless setting, in spite of the low-degree lower bound for Gaussian Pancakes. Furthermore, we show that LLL surpasses Sum-of-Squares and Approximate Message Passing algorithms, two methods often conjectured to be optimal among polynomial-time algorithms, on other noiseless problems such as Gaussian Clustering and Gaussian Phase Retrieval. These results highlight the crucial but subtle role of noise and hidden algebraic structure in the onset of statistical-to-computational gaps.

• Ph.D. Thesis 2023 Expanding Structural Design through Shape Optimization and Microstructures Tozoni, Davi Colli Abstract | PDF

  Title: Expanding Structural Design through Shape Optimization and Microstructures

  Candidate: Tozoni, Davi Colli

  Advisor(s): Denis Zorin

  Abstract:

  3D printing and other modern manufacturing tools allow users to design and produce customized objects for their needs at a considerably low cost. However, designing structures that are able to perform well is not an easy task and doing it manually can be a very slow and tedious process. In this context, structural optimization techniques can be very useful and help automating the design and analysis process.
  
  This thesis describes techniques that can expand the usage of structural optimization for digital fabrication by formulating optimization to be used with simulation models that are closer to reality, through the addition of contact and friction. Moreover, we show a fast method to compute gradients from differentiable simulations, which can be used to optimize shape, material and physical properties of our domain. In addition, we provide ways of expanding the use of two-scale topology optimization by presenting microstructures that have a smooth map from material to geometry and which can be used on curved shapes defined by irregular lattices with close to rhombic cells. Finally, we introduce two low-parametric microstructures that together are able to cover almost the whole possible range of elastic properties for isotropic metamaterials.
  
  Our results in simulation and physical experiments, both for static and time-dependent scenarios, show the advantages of our techniques and how they can be used in practice.