Faster Convex Optimization: Simulated Annealing with an Efficient Universal Barrier

Jacob Abernethy, Elad Hazan
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:2520-2528, 2016.

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 entropic 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v48-abernethy16, title = {Faster Convex Optimization: Simulated Annealing with an Efficient Universal Barrier}, author = {Abernethy, Jacob and Hazan, Elad}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {2520--2528}, year = {2016}, editor = {Balcan, Maria Florina and Weinberger, Kilian Q.}, volume = {48}, series = {Proceedings of Machine Learning Research}, address = {New York, New York, USA}, month = {20--22 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v48/abernethy16.pdf}, url = {https://proceedings.mlr.press/v48/abernethy16.html}, 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 entropic 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.} }
Endnote
%0 Conference Paper %T Faster Convex Optimization: Simulated Annealing with an Efficient Universal Barrier %A Jacob Abernethy %A Elad Hazan %B Proceedings of The 33rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Maria Florina Balcan %E Kilian Q. Weinberger %F pmlr-v48-abernethy16 %I PMLR %P 2520--2528 %U https://proceedings.mlr.press/v48/abernethy16.html %V 48 %X 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 entropic 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.
RIS
TY - CPAPER TI - Faster Convex Optimization: Simulated Annealing with an Efficient Universal Barrier AU - Jacob Abernethy AU - Elad Hazan BT - Proceedings of The 33rd International Conference on Machine Learning DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-abernethy16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 2520 EP - 2528 L1 - http://proceedings.mlr.press/v48/abernethy16.pdf UR - https://proceedings.mlr.press/v48/abernethy16.html AB - 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 entropic 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. ER -
APA
Abernethy, J. & Hazan, E.. (2016). Faster Convex Optimization: Simulated Annealing with an Efficient Universal Barrier. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:2520-2528 Available from https://proceedings.mlr.press/v48/abernethy16.html.

Related Material