[Colloquium] REMINDER: 10/25 Young Researcher Seminar Series: Ashia Wilson, UC Berkeley

[Mary Marre via Colloquium]

When:     Wednesday, October 25th at 11:00 am

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

Who:       Ashia Wilson, UC Berkeley


Title:      A Dynamical View of Optimization Algorithms



Abstract:  Optimization is a core primitive in statistics, machine
learning, and data analytics. Within these fields, the rapid growth in the
scale and complexity of modern datasets has led to a focus on two classes
of algorithms: gradient methods and momentum methods (also referred to as
accelerated methods). Momentum methods, first proposed by Nesterov in 1983,
achieve faster convergence rates than gradient methods. However, unlike
gradient methods, they are not descent methods and providing robust
performance guarantees remains a challenge. In the Euclidean setting,
momentum methods can be understood as modeling the dynamics of a damped
harmonic oscillator; making this intuition precise however, and
generalizing it to other geometries has been difficult. Furthermore,
derivations of momentum methods do not flow from a single underlying
principle, but tend to rely on case-specific algebra using a technique -
considered by many to be esoteric - called *estimate sequences.*



The first part of our work introduces a variational, continuous-time
framework for understanding momentum methods. We show that there is a
family of Lagrangian functionals, that we call *Bregman Lagrangians*, which
generate dynamics corresponding to momentum methods in continuous time. In
particular, momentum methods can be understood as arising from various
discretization techniques applied to these continuous time dynamics. The
second part of our work strengthens this connection. We demonstrate how to
derive families of Lyapunov functions which can certify* rates of
convergence* for the continuous time momentum dynamics. We further
demonstrate how the proofs of convergence of momentum methods can be
understood as bounding discretization errors of the Lyapunov function when
moving to discrete time. Along the way, we prove an equivalence between
these family of Lyapunov functions and the technique of estimate sequences.
The following is joint work with Andre Wibisono, Stephen Tu, Shivaram
Venkataraman, Alex Gittens, Benjamin Recht, and Michael I. Jordan.


Host:  Nathan Srebro <nati at ttic.edu>

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



The TTIC Young Researcher Seminar Series (http://www.ttic.edu/young-
researcher.php) features talks by Ph.D. students and postdocs whose research is
of broad interest to the computer science community. The series provides an
opportunity for early-career researchers to present recent work to and meet
with students and faculty at TTIC and nearby universities.


The seminars are typically held on Wednesdays at 11:00am in TTIC Room 526.

For additional information, please contact Matthew Walter (mwalter 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 Tue, Oct 24, 2017 at 12:48 PM, Mary Marre <mmarre at ttic.edu> wrote:

> When:     Wednesday, October 25th at 11:00 am
>
> Where:    TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526
>
> Who:       Ashia Wilson, UC Berkeley
>
>
> Title:      A Dynamical View of Optimization Algorithms
>
>
>
> Abstract:  Optimization is a core primitive in statistics, machine
> learning, and data analytics. Within these fields, the rapid growth in the
> scale and complexity of modern datasets has led to a focus on two classes
> of algorithms: gradient methods and momentum methods (also referred to as
> accelerated methods). Momentum methods, first proposed by Nesterov in 1983,
> achieve faster convergence rates than gradient methods. However, unlike
> gradient methods, they are not descent methods and providing robust
> performance guarantees remains a challenge. In the Euclidean setting,
> momentum methods can be understood as modeling the dynamics of a damped
> harmonic oscillator; making this intuition precise however, and
> generalizing it to other geometries has been difficult. Furthermore,
> derivations of momentum methods do not flow from a single underlying
> principle, but tend to rely on case-specific algebra using a technique -
> considered by many to be esoteric - called *estimate sequences.*
>
>
>
> The first part of our work introduces a variational, continuous-time
> framework for understanding momentum methods. We show that there is a
> family of Lagrangian functionals, that we call *Bregman Lagrangians*,
> which generate dynamics corresponding to momentum methods in continuous time.
> In particular, momentum methods can be understood as arising from various
> discretization techniques applied to these continuous time dynamics. The
> second part of our work strengthens this connection. We demonstrate how
> to derive families of Lyapunov functions which can certify* rates of
> convergence* for the continuous time momentum dynamics. We further
> demonstrate how the proofs of convergence of momentum methods can be
> understood as bounding discretization errors of the Lyapunov function
> when moving to discrete time. Along the way, we prove an equivalence
> between these family of Lyapunov functions and the technique of estimate
> sequences. The following is joint work with Andre Wibisono, Stephen Tu,
> Shivaram Venkataraman, Alex Gittens, Benjamin Recht, and Michael I. Jordan.
>
>
> Host:  Nathan Srebro <nati at ttic.edu>
>
> ************************************************************
> **************************************
>
>
>
> The TTIC Young Researcher Seminar Series (http://www.ttic.edu/young-
> researcher.php) features talks by Ph.D. students and postdocs whose
> research is of broad interest to the computer science community. The
> series provides an opportunity for early-career researchers to present
> recent work to and meet with students and faculty at TTIC and nearby
> universities.
>
>
> The seminars are typically held on Wednesdays at 11:00am in TTIC Room 526.
>
> For additional information, please contact Matthew Walter (
> mwalter at ttic.edu).
>
>
>
>
>
> Mary C. Marre
> Administrative Assistant
> *Toyota Technological Institute*
> *6045 S. Kenwood Avenue*
> *Room 504*
> *Chicago, IL  60637*
> *p:(773) 834-1757 <(773)%20834-1757>*
> *f: (773) 357-6970 <(773)%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/20171025/790775bd/attachment-0001.html>