Skip to main content

Faster convex optimization: Simulated annealing with an efficient universal barrier

Author(s): Abernethy, J; Hazan, Elad

To refer to this page use:
Abstract: This paper explores a surprising equivalence between two seemingly-distinct convex optimization methods. We show that simulated annealing, a well-studied random walk algorithms, is directly equivalent, in a certain sense, to the central path interior point algorithm for the the en- tropic universal barrier function. This connection exhibits several benefits. First, we are able improve the state of the art time complexity for convex optimization under the membership oracle model by devising a new temperature schedule for simulated annealing motivated by central path following interior point methods. Second, we get an efficient randomized interior point method with an efficiently computable universal barrier for any convex set described by a membership oracle. Previously, efficiently computable barriers were known only for particular convex sets.
Publication Date: 2016
Citation: Abernethy, J, Hazan, E. (2016). Faster convex optimization: Simulated annealing with an efficient universal barrier. 6 (3734 - 3746
Pages: 3734 - 3746
Type of Material: Conference Article
Journal/Proceeding Title: 33rd International Conference on Machine Learning
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.