Master Class: Large-Scale Distributed Optimization for Machine Learning (Carlos Guestrin)

SpeakerCarlos Guestrin
AffiliationUniversity of Washington
DateFriday, 03 Jul 2015
Time12:00 - 13:00
LocationRoberts 508
Event seriesMaster Class: Carlos Guestrin (2-3 July 2015)

Constraint Impact Lower Bounds for Efficient & Principled Algorithms

Working set methods and screening rules can radically improve convergence times for sparse and constrained optimization. By reducing optimization to a sequence of small subproblems, working set methods achieve fast convergence times for many challenging problems. Despite excellent performance, theoretical understanding of working sets is limited, and implementations often resort to heuristics to determine subproblem size, makeup, and stopping criteria.

In this talk, we will first present BLITZ, a fast working set algorithm accompanied by useful guarantees. Making no assumptions on data, our theory relates subproblem size to progress toward convergence. We will then generalize the proof path for BLITZ with the concept of a constraint’s impact lower bound (ILBO). The ILBO provides a recipe for the design of new optimization algorithms with theoretical guarantees for a wide range of optimization problems. Applied to a range of real-world, large-scale optimization problems, this approach convincingly outperforms existing solvers in sequential, limited-memory, and distributed settings.

Lunch will be provided after the talk in Roberts 422 (4th Floor)

iCalendar csml_id_238.ics