Loading Events
  • This event has passed.
Stochastics and Statistics Seminar

Project and Forget: Solving Large-Scale Metric Constrained Problems

November 3, 2023 @ 11:00 am - 12:00 pm

Anna Gilbert (Yale University)


Many important machine learning problems can be formulated as highly constrained convex optimization problems. One important example is metric constrained problems. In this paper, we show that standard optimization techniques can not be used to solve metric constrained problems.

To solve such problems, we provide a general active set framework, called Project and Forget, and several variants thereof that use Bregman projections. Project and Forget is a general purpose method that can be used to solve highly constrained convex problems with many (possibly exponentially) constraints. We provide a theoretical analysis of Project and Forget and prove that our algorithms converge to the global optimal solution and have a linear rate of convergence. We demonstrate that using our method, we can solve large problem instances of general weighted correlation clustering, metric nearness, information theoretic metric learning and quadratically regularized optimal transport; in each case, out-performing the state of the art methods with respect to CPU times and problem sizes.

Joint work with Rishi Sonthalia (UCLA)

Anna Gilbert is the John C. Malone Professor of Mathematics and Professor of Statistics & Data Science, working in the Department of Electrical Engineering at Yale University, with previous positions at the University of Michigan and AT&T Labs-Research.
She has received several awards, including a Sloan Research Fellowship (2006), an NSF CAREER award (2006), the National Academy of Sciences Award for Initiatives in Research (2008), the Association of Computing Machinery (ACM) Douglas Engelbart Best Paper award (2008), the EURASIP Signal Processing Best Paper award (2010), and the SIAM Ralph E. Kleinman Prize (2013).
She received an S.B. degree from the University of Chicago and a Ph.D. from Princeton University, both in Mathematics.  Her research interests include analysis, probability, discrete mathematics, and algorithms. She is especially interested in randomized algorithms with applications to harmonic analysis, signal and image processing, and massive datasets.

MIT Statistics + Data Science Center
Massachusetts Institute of Technology
77 Massachusetts Avenue
Cambridge, MA 02139-4307