ISyE Seminar Series: Mingyi Hong

"Distributed Non-Convex First-Order Optimization and Information Processing: Lower Complexity Bounds and Rate Optimal Algorithms"

Presentation by Professor Mingyi Hong
Department of Electrical and Computer Engineering
University of Minnesota—Twin Cities

Wednesday, September 5
3:15pm - Refreshments, Lind Hall 305
3:30pm - Graduate Seminar, Lind Hall 305

 

About:

We consider a class of distributed non-convex optimization problems, in which a number of agents are connected by a network, and they collectively optimize a sum of smooth (possibly non-convex) local objective functions. We address the following general question: What is the fastest rate that any distributed algorithms can achieve (to compute first-order stationary solution), and how to achieve those rates. To address this question, we consider a class of unconstrained non-convex problems, and allow the agents to access local (first-order) gradient information. We develop a lower bound analysis that identifies difficult problem instances for any first-order method. We show that in the worst-case it takes any first-order algorithm O(D/epsilon) iterations to achieve certain epsilon-solution, where D is the network diameter. Further, we develop one of the first rate-optimal distributed method whose rate precisely matches the lower bound (up to a ploylog factor). The algorithm combines ideas from distributed consensus, nonlinear optimization, as well as classical fast solvers for linear systems. Extension on how to compute high-order stationary solutions will also be discussed.

 

Bio:

Mingyi Hong received his Ph.D. degree from University of Virginia in 2011. Since August 2017, he has been an Assistant Professor in the Department of Electrical and Computer Engineering, University of Minnesota. From 2014-2017 he has been an Assistant Professor with the Department of Industrial and Manufacturing Systems Engineering, Iowa State University. He is serving on the IEEE Signal Processing for Communications and Networking (SPCOM), and Machine Learning for Signal Processing (MLSP) Technical Committees. He has coauthored works that have been selected as finalists for the Best Paper Prize for Young Researchers in Continuous Optimization in 2013, 2016. His research interests are primarily in optimization theory and applications in signal processing and machine learning.

 

Seminar Video:

Category
Start date
Wednesday, Sept. 5, 2018, 3:15 p.m.
Location

Lind Hall
Room 305

Share