Dr. Xiaoming Huo, 'A Homotopic Method to Solve the Lasso Problems with an Improved Upper Bound of Convergence Rate', TADS Lunch-n-Learn

Thursday, December 3, 2020 - 12:00pm to 1:00pm

Presenter: Dr. Xiaoming Huo

Xiaoming Huo 

Title: A Homotopic Method to Solve the Lasso Problems with an Improved Upper Bound of Convergence Rate

Abstract: In optimization, it is known that when the objective functions are strictly convex and well-conditioned, gradient based approaches can be extremely effective, e.g., achieving the exponential rate in convergence. On the other hand, the existing Lasso-type of estimator in general cannot achieve the optimal rate due to the undesirable behavior of the absolute function at the origin. A homotopic method is to use a sequence of surrogate functions to approximate the $\ell_1$ penalty that is used in the Lasso-type of estimators. The surrogate functions will converge to the $\ell_1$ penalty in the Lasso estimator. At the same time, each surrogate function is strictly convex, which enables provable faster numerical rate of convergence. In this work, we demonstrate that by meticulously defining the surrogate functions, one can prove faster numerical convergence rate than any existing methods in computing for the Lasso-type of estimators. Namely, the state-of-the-art algorithms can only guarantee $O(1/\epsilon)$ or $O(1/\sqrt{\epsilon)}$ convergence rates, while we can prove an $O([\log(1/\epsilon)]^2)$ for the newly proposed algorithm. Our numerical simulations show that the new algorithm also performs better empirically. This work is at the interface of statistics and computing.

Bio: Xiaoming Huo is an A. Russell Chandler III Professor at the Stewart School of Industrial & Systems Engineering at Georgia Tech. Huo received a Ph.D. degree in statistics from Stanford University, Stanford, CA, in 1999. In August 1999, he joined the School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA, USA, where he advanced through the ranks and became a chair professor. From 2013 to 2015, he was a program director at the National Science Foundation, managing data science related programs. He is the director of the Transdisciplinary Research Institute for Advancing Data Science at Georgia Institute of Technology (https://triad.gatech.edu/). He is a fellow of the American Statistical Association.

Huo’s research interests include statistics and data science. He has made numerous contributions on topics such as sparse representation, wavelets, and statistical detectability. His papers appeared in top journals, and some of them are highly cited.

Huo won the Georgia Tech’s Sigma Xi Young Faculty Award in 2005. His work has led to an interview by Emerging Research Fronts in June 2006 in the field of Mathematics — every two months, one paper is selected. He participated in the 30th International Mathematical Olympiad (IMO), which was held in Braunschweig, Germany, in 1989, and received a golden prize.

After the presentation, there will be a short time for discussion and questions afterwards.

Talks are recorded live via Zoom and are available for viewing later after the talk.