Computing and Mathematical Sciences Colloquium

Monday November 9, 2015 4:00 PM

Faster Convex Optimization: Simulated Annealing with an Efficient Universal Barrier

Speaker: Professor Elad Hazan, Department of Computer Science, Princeton University
Location: Annenberg 105
Interior point methods and random walk approaches have been long considered disparate approaches for convex optimization. We show how simulated annealing, one of the most common random walk algorithms, is equivalent, in a certain sense, to the central path interior point algorithm applied to the entropic universal barrier function. Using this observation we improve the state of the art in polynomial time convex optimization in the membership-oracle model.
Series Computing and Mathematical Sciences Colloquium Series

Contact: Carmen Nemer-Sirois at (626) 395-4561