ARC-ML Colloquium: Yin-Tat Lee - University of Washington

Event Details
  • Date/Time:
    • Wednesday November 9, 2016
      12:00 pm - 1:00 pm
  • Location: Klaus 1116 East
  • Phone:
  • URL: Klaus 1116
  • Email:
  • Fee(s):
    N/A
  • Extras:
Contact
No contact information submitted.
Summaries

Summary Sentence: Geodesic Walks (Klaus 1116E at noon)

Full Summary: No summary paragraph submitted.

Please note that this talk is held at noon on a Wednesday.

                         Algorithms & Randomness Center (ARC) and

                                 Machine Learning Group present

                                          ARC - ML Colloquium

               Yin-Tat Lee University of Washington

                                     Wednesday, November 9

                                     Klaus 1116 East – Noon

Title:    Geodesic Walks

Abstract:
We introduce the geodesic walk for sampling Riemannian manifolds and apply it to the problem of generating uniform random points from polytopes in R^n specified by m inequalities. The walk is a discrete-time simulation of a stochastic differential equation (SDE) on the Riemannian manifold. The resulting sampling algorithm for polytopes mixes in O*(mn^{3/4}) steps. This is the first walk that breaks the quadratic barrier for mixing in high dimension, improving on the previous best bound of O*(mn) by Kannan and Narayanan for the Dikin walk. We also show that each step of the geodesic walk (solving an ODE) can be implemented efficiently, thus improving the time complexity for sampling polytopes.

Additional Information

In Campus Calendar
No
Groups

ARC, College of Computing, School of Computer Science

Invited Audience
Faculty/Staff, Public, Undergraduate students, Graduate students
Categories
Seminar/Lecture/Colloquium
Keywords
machine learning, Randomized Algorithms, geometry
Status
  • Created By: Eric Vigoda
  • Workflow Status: Published
  • Created On: Oct 13, 2016 - 9:59pm
  • Last Updated: Apr 13, 2017 - 5:14pm