[Colloquium] Re: REMINDER: 10/28 Research at TTIC: Dan Garber, TTIC

[Mary Marre via Colloquium]

When:     Friday, October 28th at noon

Where:    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room 526

Who:       Dan Garber; TTIC


Title: Faster Projection-free Optimization and Learning

Abstract:
Projected gradient descent (PGD), and its close variants, are often
considered the methods of choice for solving a very large variety of
machine learning optimization problems, including empirical risk
minimization problems, stochastic optimization, and online convex
optimization. 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 (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.


************************************************************
****************************************************


*Research at TTIC Seminar Series*

TTIC is hosting a weekly seminar series presenting the research currently
underway at the Institute. Every week a different TTIC faculty member will
present their research.  The lectures are intended both for students
seeking research topics and adviser, and for the general TTIC and
University of Chicago communities interested in hearing what their
colleagues are up to.

To receive announcements about the seminar series, please subscribe to the
mailing list: https://groups.google.com/a/ttic.edu/group/talks/subscribe

Speaker details can be found at: http://www.ttic.edu/tticseminar.php.

For additional questions, please contact Nathan Srebro at nati at ttic.edu
<mcallester at ttic.edu>


Mary C. Marre
Administrative Assistant
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Room 504*
*Chicago, IL  60637*
*p:(773) 834-1757*
*f: (773) 357-6970*
*mmarre at ttic.edu <mmarre at ttic.edu>*

On Thu, Oct 27, 2016 at 2:52 PM, Mary Marre <mmarre at ttic.edu> wrote:

> When:     Friday, October 28th at noon
>
> Where:    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room 526
>
> Who:       Dan Garber; TTIC
>
>
> Title: Faster Projection-free Optimization and Learning
>
> Abstract:
> Projected gradient descent (PGD), and its close variants, are often
> considered the methods of choice for solving a very large variety of
> machine learning optimization problems, including empirical risk
> minimization problems, stochastic optimization, and online convex
> optimization. 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 (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.
>
>
> ************************************************************
> ****************************************************
>
>
> *Research at TTIC Seminar Series*
>
> TTIC is hosting a weekly seminar series presenting the research currently
> underway at the Institute. Every week a different TTIC faculty member will
> present their research.  The lectures are intended both for students
> seeking research topics and adviser, and for the general TTIC and
> University of Chicago communities interested in hearing what their
> colleagues are up to.
>
> To receive announcements about the seminar series, please subscribe to the
> mailing list: https://groups.google.com/a/ttic.edu/group/talks/subscribe
>
> Speaker details can be found at: http://www.ttic.edu/tticseminar.php.
>
> For additional questions, please contact Nathan Srebro at nati at ttic.edu
> <mcallester at ttic.edu>
>
>
>
> Mary C. Marre
> Administrative Assistant
> *Toyota Technological Institute*
> *6045 S. Kenwood Avenue*
> *Room 504*
> *Chicago, IL  60637*
> *p:(773) 834-1757 <%28773%29%20834-1757>*
> *f: (773) 357-6970 <%28773%29%20357-6970>*
> *mmarre at ttic.edu <mmarre at ttic.edu>*
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20161028/0cde407b/attachment-0001.html>