Madeleine Udell | Academic
The problem of maximizing a sum of sigmoidal functions over a convex constraint set arises in many application areas. This objective captures the idea of decreasing marginal returns to investment, and has applications in mathematical marketing, network bandwidth allocation, revenue optimization, optimal bidding, and lottery design. It turns out that the general problem is NP-hard to approximate, but our branch-and-bound algorithm often finds solutions in reasonable time. To illustrate the power of this approach, we compute the optimal positions which might have allowed the candidates in the 2008 United States presidential election to maximize their vote shares. Manuscript available here
Optimization provides a powerful framework for solving problems ranging from machine learning to supply chain optimization. However, convex optimization procedures, whose solutions are computationally efficient and provide guarantees of optimality, are currently limited to problems with fewer than 100,000 variables. In order to solve the large-scale problems that frequently arise in machine learning and statistical applications, a distributed approach is needed.
The alternating directions method of multipliers (ADMM) is one technique for distributed optimization being explored by Professor Stephen Boyd at Stanford. ADMM partitions the variables across different nodes, each of which performs a separate optimization over its variables, while holding the values of the other variables fixed. Between iterations, the nodes compare their answers, update the values of the variables held fixed, and recompute until convergence is reached.
How should the variables be partitioned in order to converge as quickly as possible? One can think of the variables and constraints in a problem as a bipartite graph, and use ideas from graph theory in order to find the optimal partition. I am currently investigating whether graph clustering and graph coloring heuristics based on the spectrum of the matrices associated with the graph may improve the convergence time of the algorithm.
The general problem of mapping a data set in a high-dimensional space into a lower-dimensional space occurs frequently in scientific applications. Examples include visualizing high-dimensional data in 3D, finding the path a protein takes as it unfolds, and discovering the shape of a molecule using cryo-electron microscopy. Traditional linear approaches to such problems include regression analysis and PCA. However, in cases where the data are drawn from a manifold that is not isomorphic to Rn, linear techniques are bound to fail: no straight line is a good fit through a circle. Diffusion mapping techniques, of which Laplacian eigenfunctions are an example, present a way to find these nonlinear manifolds in large data sets by setting up a diffusion on the dataset, and using the eigenvectors of this diffusion operator as a basis for a lower-dimensional representation of the space.
With Professor Peter Jones at Yale, I studied a recent proof that helped to explain the empirical robustness of diffusion mapping methods, which rarely come with performance guarantees, by abstracting to a continuous setting, where one can show that diffusion coordinates provide a low-distortion mapping for neighborhoods of arbitrary smooth Riemannian manifolds. I also studied the application of eigenfunction maps to a problem in cryo-electron microscopy, in which the challenge was to recover the shape of the underlying molecule from its projected images taken at random, unknown angles. In this case the underlying manifold is the 2-sphere: the set of angles from which the pictures can be taken. By identifying the neighbors of each radial line in each projected image, we were able to construct a diffusion on the radial lines that allowed the reconstruction of the original 3D density map. My senior essay [.pdf] was awarded the Henry Edward Ellsworth Prize.
I began my research career the summer after my freshman year in a computational physics lab, studying the electronic properties of gallium nitride nanowires with Yale Professor Sohrab Ismail-Beigi under a grant from Yale's Perspectives on Science program. Using the tight-binding approximation to the Schrodinger equation, we simulated wires of various different sizes and geometries to understand and predict how the presence of edges and corners changed the electric properties of the nanowire compared with bulk gallium nitride. We hoped to link experimental results in nanowires fabrication with theoretical predictions, advancing understanding of these novel structures. Since computer simulations can run much more quickly than physical experiments can be conducted, we hoped to help guide experimental goals in synthesizing nanowires for use in computers or in light emitting diodes.
I studied the effects of hydrodynamic correlations on particle motion with Yale Professor Eric Dufresne during the spring and summer of 2008. Our research was inspired by the observation that sedimenting particles can create patterns that look highly disordered and chaotic, although their motion is governed by the non-turbulent limit of the Navier-Stokes equation, in which the nonlinear term in the equation is taken to zero. We hoped that by understanding this limit, we might better understand the origins of chaos in the full equation. I simulated the motions of particles sedimenting under gravity to create chaotic trajectories, using the Matlab scripting language. I also performed an experiment using holographic optical tweezers to measure the correlations in the motions of polystyrene particles in aqueous solution.
I spent summer 2007 at Caltech with the Laser Interferometer Gravitational Wave Observatory (LIGO) under an NSF REU. My work at LIGO stimulated much of my interest in statistical techniques for finding a signal in very noisy data. Among other projects, LIGO is trying to capture the stochastic gravitational wave background (SGWB) produced during the earliest moments after the big bang. The data would be a tremendous boon to cosmologists, since the universe was opaque to electromagnetic radiation - but transparent to gravitational waves - until it cooled enough for atoms to form about 300,000 years after the big bang. Theorists describe the SGWB using the spherical harmonics basis, and so at LIGO I worked with the data analysis team to create software to express the signal (and the noise) measured in that basis. I was glad to have the opportunity to present my research at a Caltech summer research colloquium, at the Yale Physics Club, and at the 2008 Conference for Undergraduate Women in Physics.
Papers and Presentations
- Bounding Duality Gap for Problems with Separable Objective [paper]
- Flexible Objectives in Flux Balance Analysis [paper]
- Maximizing a Sum of Sigmoids [paper] [slides]
- Analyzing Patterns of Drug Use in Clinical Notes for Patient Safety [paper]
- Introduction to Discrete Mathematics [slides]
- Partitioning Problems in Distributed Optimization [poster] [paper]
- Notes on Spectral Graph Theory [paper]
- Laplacian Eigenfunction Maps [paper]
- Summer 2013: Instructor for EE364a: Convex Optimization.
- Fall 2012: Instructor for the ICME discrete math refresher course.
- Winter 2012: Teaching assistant for EE364a: Convex Optimization.
- Fall 2011: Instructor for the ICME discrete math refresher course. My slides are posted here. I tried to make the class more interesting for people of widely varying levels by asking students to collaborate on problems, so that those who knew the solutions could help teach and guide those for whom the material was new. If you took the class, I'd love to hear what you thought: this survey should take about 3 minutes to complete.
- Winter 2011: Teaching assistant for CME305: Discrete Mathematics and Algorithms. I proposed a new unit on spectral graph theory and designed and delivered the first lecture on the topic. In office hours I help students systematize their knowledge so they can solve novel problems.
- Fall 2010: Created and taught two courses at Stanford Splash! for advanced high school students. One introduced students to axiomatic mathematical proofs; the second derived the principles of classical tonal harmony from the wave equation on a string via fourier decomposition.