Tata Institute of Fundamental Research
Randomized Interior Point Methods for Sampling and Optimization
Seminar
Speaker:
Hariharan Narayanan (University of Washington
Department of Statistics and
Department of Mathematics
Padelford Hall, Room C-301
Seattle, WA 98105
United States of America)
Organiser:
Jaikumar Radhakrishnan
Date:
Tuesday, 5 Aug 2014, 14:30 to 15:30
Venue:
AG69
(Scan to add to calendar)
Abstract:
Abstract: Interior point methods are algorithms that optimize convex functions over high dimensional convex sets. From one point of view, an interior point method first equips a convex set with a Riemannian metric and then performs a steepest descent to minimize the objective on the resulting Riemannian manifold. We will describe a randomized variant of an interior point method known as ``the affine scaling algorithm" introduced by I.I.Dikin. This variant corresponds to a natural random walk on the same manifold on which affine scaling would perform steepest descent. We discuss applications to sampling and optimization and prove polynomial bounds on the mixing time of the associated Markov Chain. This talk includes work done in collaboration with Ravi Kannan and Alexander Rakhlin.
| Speaker: | Hariharan Narayanan (University of Washington Department of Statistics and Department of Mathematics Padelford Hall, Room C-301 Seattle, WA 98105 United States of America) |
| Organiser: | Jaikumar Radhakrishnan |
| Date: | Tuesday, 5 Aug 2014, 14:30 to 15:30 |
| Venue: | AG69 |
(Scan to add to calendar)
Abstract:
Abstract: Interior point methods are algorithms that optimize convex functions over high dimensional convex sets. From one point of view, an interior point method first equips a convex set with a Riemannian metric and then performs a steepest descent to minimize the objective on the resulting Riemannian manifold. We will describe a randomized variant of an interior point method known as ``the affine scaling algorithm" introduced by I.I.Dikin. This variant corresponds to a natural random walk on the same manifold on which affine scaling would perform steepest descent. We discuss applications to sampling and optimization and prove polynomial bounds on the mixing time of the associated Markov Chain. This talk includes work done in collaboration with Ravi Kannan and Alexander Rakhlin.