Incremental Gradient, Subgradient, and Proximal Methods for Convex Optimization... Special Guest Lecture by Dimitri Bertsekas, MIT

Note:  Room changed to AERL 120 (2202 Main Mall) (http://www.maps.ubc.ca/PROD/index_detail.php?locat1=316)

Speaker: Dimitri Bertsekas, McAfee Professor of Engineering, Laboratory for Information and Decision Systems, Massachusetts Institute of Technology

Webpage: http://www.mit.edu/~dimitrib/home.html 

Title: Incremental Gradient, Subgradient, and Proximal Methods for Convex Optimization: A Unified Framework  

Host:  Mark Schmidt, UBC Computer Science  

Abstract:

We survey incremental methods for minimizing a sum $sum_{i=1}^mf_i(x)$, either unconstrained or subject to a set intersection constraint $X=cap_{i=1}^m X_i$, where $f_i$ and $X_i$ are convex cost and constraint components respectively. Our methods consist of iterations applied to single cost components and, as an option, projection on single constraint components. We introduce a flexible unified algorithmic framework for a variety of such methods, some involving gradient, subgradient, and proximal iterations. For the constrained case, we provide a convergence analysis, based on a coupled supermartingale convergence theorem, which shows that the convergence relies on an interplay between two coupled processes: progress towards feasibility and progress towards optimality. We also discuss the rate of convergence properties of the methods, including the advantages offered by randomization in the selection of components. Based in part on joint work with Mengdi Wang.  

Biography:

Dimitri P. Bertsekas' undergraduate studies were in engineering at the National Technical University of Athens, Greece. He obtained his MS in electrical engineering at the George Washington University, Wash. DC in 1969, and his Ph.D. in system science in 1971 at the Massachusetts Institute of Technology.

Dr. Bertsekas has held faculty positions with the Engineering-Economic Systems Dept., Stanford University (1971-1974) and the Electrical Engineering Dept. of the University of Illinois, Urbana (1974-1979). Since 1979 he has been teaching at the Electrical Engineering and Computer Science Department of the Massachusetts Institute of Technology (M.I.T.), where he is currently McAfee Professor of Engineering. He has held editorial positions in several journals. His research at M.I.T. spans several fields, including optimization, control, large-scale computation, and data communication networks, and is closely tied to his teaching and book authoring activities. He has written numerous research papers, and fifteen books, several of which are used as textbooks in MIT classes.

Professor Bertsekas was awarded the INFORMS 1997 Prize for Research Excellence in the Interface Between Operations Research and Computer Science for his book 'Neuro-Dynamic Programming' (co-authored with John Tsitsiklis), the 2000 Greek National Award for Operations Research, the 2001 ACC John R. Ragazzini Education Award, the 2009 INFORMS Expository Writing Award, the 2014 ACC Richard E. Bellman Control Heritage Award for 'contributions to the foundations of deterministic and stochastic optimization-based methods in systems and control,' and the 2014 Khachiyan Prize for Life-Time Accomplishments in Optimization. In 2001, he was elected to the United States National Academy of Engineering for 'pioneering contributions to fundamental research, practice and education of optimization/control theory, and especially its application to data communication networks.'

Dr. Bertsekas' recent books are "Introduction to Probability: 2nd Edition" (2008), "Convex Optimization Theory" (2009), "Dynamic Programming and Optimal Control, Vol. II: Approximate Dynamic Programming" (2012), and "Abstract Dynamic Programming" (2013), all published by Athena Scientific.