Distinguished ADSE Seminar Series
New Theory and Improved Computational Performance of the Frank-Wolfe Method for Data Science Applications
| Date | 1 DEC 2021 (Wed) |
|---|---|
| Time | 10:30am |
| Speaker | Professor Robert M. Freund Theresa Seley Professor in Management Science Sloan School of Management Massachusetts Institute of Technology, USA |
| Venue | Online via Zoom |
Abstract
The Frank-Wolfe method has emerged in the last decade as a very attractive algorithm for optimization in data science applications because the algorithm itself encourages desirable solution structure (such as sparsity or low-rank) without sacrificing computational guarantees. This talk will report on two ongoing research projects related to the Frank-Wolfe method. The first project is focused on the Frank-Wolfe method for empirical risk minimization in the linearly-structured setting (the most often occurring in practice) in the regime where the number of samples n is huge and computing an exact gradient is unattractive. In this setting the most efficient stochastic Frank-Wolfe methods depend linearly on n , even though their proximal counterparts (such as stochastic gradient descent (SGD)) scale independent of n . Here we present a new deterministic approximate-gradient Frank-Wolfe method that substantially reduces the dependence on the sample size n , with improved computational complexity bounds and demonstrably improved computational performance in practice.
The second project is a new generalized Frank-Wolfe method for the class of composite optimization problems (P): minimize_x f(𝖠x) + h(x) , where f is a θ-logarithmically-homogeneous self-concordant barrier, 𝖠 is a linear operator, and the convex function h has bounded domain but is possibly non-smooth. Problem instances of (P) include the D-optimal design problem in experimental design, the minimum volume covering ellipsoid problems in convex geometry, Poisson image deblurring problems with TV (Total Variation) regularization, and PET (positron emission tomography) image reconstruction. The lack of smoothness of the objective function of (P) has been a bottleneck to the development of both theory and practical computational performance for the Frank-Wolfe method as well as other first-order methods that would otherwise be attractive when the problem dimensions are huge. We develop a new theory that yields attractive computational complexity for this class of problems. Our theoretical results rely on just a few problem-instance measures that arise naturally for this problem class, and that point to certain intrinsic connections between θ-logarithmically homogeneous barriers and the Frank-Wolfe method. Last of all, we present computational experiments that point to the potential usefulness of our generalized Frank-Wolfe method on Poisson image de-blurring problems with TV regularization, and on simulated PET problem instances.
This research is joint with students Renbo Zhao and Zikai Xiong of the MIT Operations Research Center.
About the Speaker
Robert Freund is the Theresa Seley Professor in Management Science at the Sloan School of Management at MIT, where he teaches courses in data science to MBA students, as well as optimization methods/theory courses to doctoral students at MIT. His research interests are in convex optimization, computational complexity and related computational science, convex geometry, large-scale nonlinear optimization, data science and machine learning, and related mathematical systems. He received his B.A. in Mathematics from Princeton University and M.S. and Ph.D. in Operations Research from Stanford University. He received the Longuet-Higgins Prize for contributions to computer vision in 2007, as well as numerous teaching awards over the last thirty years. He is an INFORMS Fellow, former Co-Editor and currently Associate Editor of Mathematical Programming A, and has served in numerous leadership roles in operations research and optimization, including former Co-Director of the MIT Operations Research Center, the MIT Program in Computation for Design and Optimization, and the former Chair of the INFORMS Optimization Section. He served a term as Deputy Dean for faculty at the Sloan School at MIT for the term 2008-11. He is the co-author (with Dimitris Bertsimas) of the MBA textbook Data, Models, and Decisions: the Fundamentals of Management Science (Dynamic Ideas, LLC 2004).
Enquiry: 3442 8422
All are welcome!
Last modified on 24 November, 2021