Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

GGAM Ph.D. Exit Seminar: On the Smoothed Analysis of Frank-Wolfe Methods

Special Events

Speaker: Chang Shu
Location: Zoom
Start time: Fri, Aug 20 2021, 4:10PM

On the Smoothed Analysis of Frank-Wolfe Methods

Abstract: We study the smoothed complexity of Frank-Wolfe methods via conditioning of random matrices and polytopes. Frank-Wolfe methods are popular for optimization over a polytope. One of the reasons is because they do not need projection onto the polytope but only linear optimization over it. To understand its complexity, a fruitful approach in many works has been the use of condition measures of polytopes. Lacoste-Julien and Jaggi introduced a condition number for polytopes and showed linear convergence for several variations of the method. The actual running time can still be exponential in the worst case (when the condition number is exponential). We study the smoothed complexity of the condition number, namely the condition number of small random perturbations of the input polytope and show that it is polynomial for any simplex and exponential for general polytopes. Our argument for polytopes is a refinement of an argument that we develop to study the conditioning of random matrices.The basic argument shows that for c>1 a dxn random Gaussian matrix has a dxd submatrix with minimum singular value that is exponentially small with high probability. This also has consequences on known results about the robust uniqueness of tensor decompositions, the complexity of the simplex method and the diameter of polytopes.

Zoom link: