[Colloquium] REMINDER: Talks at TTIC: Dan Garber, Technion

[Dawn Ellis]

When:     Tuesday, May 5th at 11am

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

Who:       Dan Garber, Technion

Title:       Projection-free Learning and Optimization

Abstract:

The computational bottle-neck in solving many problems of interest that
arise in machine learning and optimization is the computation of
projections onto a feasible set.
In this talk I will present a line of research that seeks to replace
expensive projections with a potentially much cheaper step: linear
optimization over the feasible set. Indeed in many problems that involve
matrices or certain combinatorial structures, a linear optimization oracle
admits a much more efficient implementation than a projection oracle.
I will focus in on the problem of online learning with polyhedral sets,
presenting an algorithm that requires solving a single linear optimization
problem per iteration while attaining optimal regret, resolving an open
question of Kalai & Vempala [COLT’03] and Hazan & Kale [ICML’12].
The online algorithm is based on a new algorithm for (offline) convex
optimization using a linear oracle that converges exponentially faster than
previous such methods. The development of such an offline algorithm was an
ongoing research effort since the 1950’s. The online algorithm also gives
rise to algorithms for other optimization settings such as stochastic
optimization, with the same rates as more expensive projection-based
methods.

Host:  Nati Srebro,  nati at ttic.edu
<javascript:_e(%7B%7D,'cvml','nati at ttic.edu');>



-- 
*Dawn Ellis*
Administrative Coordinator,
Bookkeeper
773-834-1757
dellis at ttic.edu <javascript:_e(%7B%7D,'cvml','dellis at ttic.edu');>

TTIC
6045 S. Kenwood Ave.
Chicago, IL. 60637


-- 
*Dawn Ellis*
Administrative Coordinator,
Bookkeeper
773-834-1757
dellis at ttic.edu

TTIC
6045 S. Kenwood Ave.
Chicago, IL. 60637
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20150504/028fa7d7/attachment.htm