Time+Place: Monday 28/11/2016 10:30 Room 337 Taub Bld.
Title: Faster Projection-free Machine Learning and Optimization
Speaker: Dan Garber - CS-Lecture - NOTE UNUSUAL DAY AND HOUR http://ttic.uchicago.edu/~dgarber/
Affiliation: Toyota Technological Institute at Chicago


Projected gradient descent (PGD), and its close variants, are often 
considered the methods of choice for solving a large variety of machine 
learning optimization problems, including empirical risk minimization, 
statistical learning, and online learning. This is not surprising, since 
PGD is often optimal in a very appealing information-theoretic sense. 
However, for many problems PGD is infeasible both in theory and practice 
since each step requires to compute an orthogonal projection onto the 
feasible set. In many important cases, such as when the feasible set is 
a non-trivial polytope, or a convex surrogate for a low-rank structure, 
computing the projection is computationally inefficient in 
high-dimensional settings. An alternative is the conditional gradient 
method (CG), aka Frank-Wolfe algorithm, that replaces the expensive 
projection step with a linear optimization step over the feasible set. 
Indeed in many problems of interest, the linear optimization step admits 
much more efficient algorithms than the projection step, which is the 
reason to the substantial regained interest in this method in the past 
decade. On the downside, the convergence rates of the CG method often 
fall behind that of PGD and its variants.

In this talk I will survey an ongoing effort to design CG variants that 
on one hand enjoy the cheap iteration complexity of the original method, 
and on the other hand converge provably faster, and are applicable to a 
wider variety of machine learning settings. In particular I will focus 
on the cases in which the feasible set is either a polytope or a convex 
surrogate for low-rank matrices. Results will be demonstrated on 
applications including: LASSO, video co-localization, optical character 
recognition, matrix completion, and multi-class classification.

Short Bio:

Dan's research interests lie in the intersection of machine learning and 
continuous optimization. Dan's main focus is on the development of 
efficient algorithms with novel and provable performance guarantees for 
machine learning, data analysis, decision making and optimization 

Dan is currently a Research Assistant Professor at Toyota Technological 
Institute at Chicago, a philanthropically endowed academic computer 
science institute located on the University of Chicago campus. 
Previously, he received both his Ph.D and his M.Sc degrees from the 
Technion - Israel Institute of Technology, where he worked under the 
supervision of Prof. Elad Hazan. Before that, Dan completed his 
bachelor's degree in electrical engineering, also in the Technion.