Contact Us

Give us a call or drop by anytime, we endeavor to answer all inquiries within 24 hours.


Find us

PO Box 16122 Collins Street West Victoria, Australia

Email us /

Phone support

Phone: + (066) 0760 0260 / + (057) 0760 0560

Loading Events

« All Events

  • This event has passed.
Event Series Event Series: Colloquia Lecture Series

On the complexity of Frank-Wolfe methods

May 31 @ 2:00 pm - 3:30 pm

Abstract: 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. This talk has two parts.

The first part will be about the complexity of Wolfe’s method, an algorithm closely related to Frank-Wolfe methods. In 1974 Phillip Wolfe proposed a method to find the minimum Euclidean-norm point in a convex polyhedron. The method is essentially the same as the Lawson-Hanson algorithm for non-negative least squares. The complexity of Wolfe’s method has remained unknown since he proposed it. The method is important because it is used as a subroutine for one of the most practical algorithms for submodular function minimization. We present the first example that Wolfe’s method takes exponential time. Additionally, we improve previous results to show that linear programming reduces in strongly-polynomial time to the minimum norm point problem over a simplex.

The second part will be about the smoothed complexity of Frank-Wolfe methods. To understand their 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 d-by-n random Gaussian matrix with n >= cd has a d-by-d 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.


May 31
2:00 pm - 3:30 pm
Event Category:


HDSI General


Luis Rademacher


SDSC, The Auditorium
9836 Hopkins Dr, La Jolla
San Diego, CA United States
+ Google Map