Theses & Reports

Instructions for submitting a technical report or thesis.

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

Title

Authors

Year

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.
M.S. Thesis 2023 On Certified Isotopic Approximation of Space Curves Dogan, Caglar Abstract | PDF

Title: On Certified Isotopic Approximation of Space Curves

Candidate: Dogan, Caglar

Advisor(s): Chee Yap

Abstract:

The approximation of implicitly defined curves or surfaces is a problem of interest for many fields. As a result, this problem has been explored using algebraic, geometric, and numerical methods. Amongst these, a numerical method called Marching Cubes Algorithm ([4]) has been the primary choice in implementations because of its efficiency and implementability, even though a guarantee for topological correctness was not generally present.

Research in this area has largely focused on approximations of 𝑛 − 1 dimensional manifolds in 𝑛 dimensional Euclidean space. These are called co-dimension 1 manifolds, defined as the zero sets of single equations in 𝑛 variables. Plantinga and Vegter (2004) [8] derived the first algorithms with guaranteed topological correctness using interval arithmetic and adaptive subdivision for 𝑛 = 2, 3. Faster variants of such algorithms were described by Yap et al. (2009, 2014) [10] [11]. Galehouse (2008) [9] succeeded in producing such algorithms for all 𝑛.

This thesis addresses the problem of computing isotopic approximations of co-dimension 2 manifolds, i.e., 𝑛 − 2 dimensional manifolds in 𝑛 dimensional Euclidean space. Such manifolds are the intersection of the zero sets of two equations in 𝑛 variables. The first interesting case is 𝑛 = 3, i.e., the problem of computing an isotopic approximation of a space curve in 3D. We work on devising new algorithms by extending the previous interval techniques in co-dimension 1. Moreover, we implement and visualize such curves in order to verify their practical efficiency.
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.