Escaping the Local Minima via Simulated Annealing: Optimization of Approximately Convex Functions

Alexandre Belloni, Tengyuan Liang, Hariharan Narayanan, Alexander Rakhlin
Proceedings of The 28th Conference on Learning Theory, PMLR 40:240-265, 2015.

Abstract

We consider the problem of optimizing an approximately convex function over a bounded convex set in \mathbbR^n using only function evaluations. The problem is reduced to sampling from an \emphapproximately log-concave distribution using the Hit-and-Run method, which is shown to have the same \mathcalO^* complexity as sampling from log-concave distributions. In addition to extend the analysis for log-concave distributions to approximate log-concave distributions, the implementation of the 1-dimensional sampler of the Hit-and-Run walk requires new methods and analysis. The algorithm then is based on simulated annealing which does not relies on first order conditions which makes it essentially immune to local minima. We then apply the method to different motivating problems. In the context of zeroth order stochastic convex optimization, the proposed method produces an ε-minimizer after \mathcalO^*(n^7.5ε^-2) noisy function evaluations by inducing a \mathcalO(ε/n)-approximately log concave distribution. We also consider in detail the case when the “amount of non-convexity” decays towards the optimum of the function. Other applications of the method discussed in this work include private computation of empirical risk minimizers, two-stage stochastic programming, and approximate dynamic programming for online learning.

Cite this Paper

BibTeX
@InProceedings{pmlr-v40-Belloni15, title = {Escaping the Local Minima via Simulated Annealing: Optimization of Approximately Convex Functions}, author = {Belloni, Alexandre and Liang, Tengyuan and Narayanan, Hariharan and Rakhlin, Alexander}, booktitle = {Proceedings of The 28th Conference on Learning Theory}, pages = {240--265}, year = {2015}, editor = {Grünwald, Peter and Hazan, Elad and Kale, Satyen}, volume = {40}, series = {Proceedings of Machine Learning Research}, address = {Paris, France}, month = {03--06 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v40/Belloni15.pdf}, url = {https://proceedings.mlr.press/v40/Belloni15.html}, abstract = {We consider the problem of optimizing an approximately convex function over a bounded convex set in \mathbbR^n using only function evaluations. The problem is reduced to sampling from an \emphapproximately log-concave distribution using the Hit-and-Run method, which is shown to have the same \mathcalO^* complexity as sampling from log-concave distributions. In addition to extend the analysis for log-concave distributions to approximate log-concave distributions, the implementation of the 1-dimensional sampler of the Hit-and-Run walk requires new methods and analysis. The algorithm then is based on simulated annealing which does not relies on first order conditions which makes it essentially immune to local minima. We then apply the method to different motivating problems. In the context of zeroth order stochastic convex optimization, the proposed method produces an ε-minimizer after \mathcalO^*(n^7.5ε^-2) noisy function evaluations by inducing a \mathcalO(ε/n)-approximately log concave distribution. We also consider in detail the case when the “amount of non-convexity” decays towards the optimum of the function. Other applications of the method discussed in this work include private computation of empirical risk minimizers, two-stage stochastic programming, and approximate dynamic programming for online learning.} }
Endnote
%0 Conference Paper %T Escaping the Local Minima via Simulated Annealing: Optimization of Approximately Convex Functions %A Alexandre Belloni %A Tengyuan Liang %A Hariharan Narayanan %A Alexander Rakhlin %B Proceedings of The 28th Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2015 %E Peter Grünwald %E Elad Hazan %E Satyen Kale %F pmlr-v40-Belloni15 %I PMLR %P 240--265 %U https://proceedings.mlr.press/v40/Belloni15.html %V 40 %X We consider the problem of optimizing an approximately convex function over a bounded convex set in \mathbbR^n using only function evaluations. The problem is reduced to sampling from an \emphapproximately log-concave distribution using the Hit-and-Run method, which is shown to have the same \mathcalO^* complexity as sampling from log-concave distributions. In addition to extend the analysis for log-concave distributions to approximate log-concave distributions, the implementation of the 1-dimensional sampler of the Hit-and-Run walk requires new methods and analysis. The algorithm then is based on simulated annealing which does not relies on first order conditions which makes it essentially immune to local minima. We then apply the method to different motivating problems. In the context of zeroth order stochastic convex optimization, the proposed method produces an ε-minimizer after \mathcalO^*(n^7.5ε^-2) noisy function evaluations by inducing a \mathcalO(ε/n)-approximately log concave distribution. We also consider in detail the case when the “amount of non-convexity” decays towards the optimum of the function. Other applications of the method discussed in this work include private computation of empirical risk minimizers, two-stage stochastic programming, and approximate dynamic programming for online learning.
RIS
TY - CPAPER TI - Escaping the Local Minima via Simulated Annealing: Optimization of Approximately Convex Functions AU - Alexandre Belloni AU - Tengyuan Liang AU - Hariharan Narayanan AU - Alexander Rakhlin BT - Proceedings of The 28th Conference on Learning Theory DA - 2015/06/26 ED - Peter Grünwald ED - Elad Hazan ED - Satyen Kale ID - pmlr-v40-Belloni15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 40 SP - 240 EP - 265 L1 - http://proceedings.mlr.press/v40/Belloni15.pdf UR - https://proceedings.mlr.press/v40/Belloni15.html AB - We consider the problem of optimizing an approximately convex function over a bounded convex set in \mathbbR^n using only function evaluations. The problem is reduced to sampling from an \emphapproximately log-concave distribution using the Hit-and-Run method, which is shown to have the same \mathcalO^* complexity as sampling from log-concave distributions. In addition to extend the analysis for log-concave distributions to approximate log-concave distributions, the implementation of the 1-dimensional sampler of the Hit-and-Run walk requires new methods and analysis. The algorithm then is based on simulated annealing which does not relies on first order conditions which makes it essentially immune to local minima. We then apply the method to different motivating problems. In the context of zeroth order stochastic convex optimization, the proposed method produces an ε-minimizer after \mathcalO^*(n^7.5ε^-2) noisy function evaluations by inducing a \mathcalO(ε/n)-approximately log concave distribution. We also consider in detail the case when the “amount of non-convexity” decays towards the optimum of the function. Other applications of the method discussed in this work include private computation of empirical risk minimizers, two-stage stochastic programming, and approximate dynamic programming for online learning. ER -
APA
Belloni, A., Liang, T., Narayanan, H. & Rakhlin, A.. (2015). Escaping the Local Minima via Simulated Annealing: Optimization of Approximately Convex Functions. Proceedings of The 28th Conference on Learning Theory, in Proceedings of Machine Learning Research 40:240-265 Available from https://proceedings.mlr.press/v40/Belloni15.html.

Related Material