My research interests center on convex optimization. I am currently investigating the theoretical foundations of generative AI models. I have worked on semidefinite relaxations, polynomial and sum of squares optimization, and the global landscape of non-convex optimization problems.
Denoising diffusion models achieve state of the art quality on image generation tasks. In this line of work we introduce a deterministic framework for reasoning about, improving and potentially discovering new applications of diffusion models. We interpret diffusion models as projection onto the support of the training set, with sampling as approximate gradient descent on the distance function to this set. Applying this interpretation, we derive a simple yet efficient diffusion sampler, as well as a framework for incorporating constraints (such as minimizing the drag coefficient of vehicle images) into the generation process.
Semidefinite programming is powerful but slow, can we speed it up by using first order methods? By factorizing the PSD variable \(X = UU^\top\), we can optimize over \(U\) using first-order methods. However this formulation is nonconvex and these methods may get stuck in local minima. We show that this does not happen in the setting of univariate sum of squares decomposition: all local minima are global. In addition, using an interpolation representation we can compute gradients in near-linear time (using TrigPolys.jl), finding the sum of squares decomposition of a million-degree polynomial in less than 30 minutes.
This line of work studies convex relaxations of functions of the form \(f(x^T A_1 x, \ldots, x^T A_d x)\). For very high degree but structured polynomials we derive intermediate relaxations interpolating between spectral and Sum-of-Squares relaxations, as well as randomized rounding schemes (see picture on the right). We also analyze rounding schemes for different functions \(f\), making a connection to Max-Cut.
We found a connection between approximating the permanent of a PSD matrix and approximating the maximum of a polynomial optimization problem on the sphere. By doing so our analysis improve the approximation factor, in addition to simplifying its proof.
Masters thesis work on characterizing classes of polynomial optimization problems on the sphere that can be compressed by a random projection. Introduced the notion of polynomials generated from focused cones, and the reduced dimension depends on the Gaussian width of the focused cones.
Class project for 6.850 (Geometric Computing) together with with Kyriakos Axiotis and Aleksandar Makelov. We prove a new hardness result for the DGT (used in physical simulations, evaluating and optimizing over Gaussian kernels) assuming the Strong Exponential Time Hypothesis. [pdf]
Undergrad research in Alex Bayen’s group at UC Berkeley studying the effect of attacks on mobility as a service networks (such as Uber or Lyft) by an adversary gaining control of a fraction of the network, and how we can deter these attacks. We model this problem as a queueing network and the attacker or operator aims to optimally control a fraction of the agents in the network to meet some objective.