Proceedings

Derivative-Free Optimization of High-Dimensional Non-Convex Functions by Sequential Random Embeddings

Download BibTeX Cite

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 1946-1951.

© 2016 International Joint Conferences on Artificial Intelligence

Abstract

Derivative-free optimization methods are suitable for sophisticated optimization problems, while are hard to scale to high dimensionality (e.g., larger than 1,000). Previously, the random embedding technique has been shown successful for solving high-dimensional problems with low effective dimensions. However, it is unrealistic to assume a low effective dimension in many applications. This paper turns to study high-dimensional problems with low optimal epsilon-effective dimensions, which allow all dimensions to be effective but many of them only have a small bounded effect. We characterize the properties of random embedding for this kind of problems, and propose the sequential random embeddings (SRE) to reduce the embedding gap while running optimization algorithms in the low-dimensional spaces. We apply SRE to several state-of-the-art derivative-free optimization methods, and conduct experiments on synthetic functions as well as non-convex classification tasks with up to 100,000 variables. Experiment results verify the effectiveness of SRE.

  1. [Blake et al., 1998] C. L. Blake, E. Keogh, and C. J. Merz. UCI Repository of machine learning databases. [http://www.ics.uci.edu/ ⇠ mlearn/MLRepository.html], 1998. Link
  2. [Brochu et al., 2010] Eric Brochu, Vlad M. Cora, and Nando de Freitas. A tutorial on bayesian optimization of ex- pensive cost functions, with application to active user modeling and hierarchical reinforcement learning. CoRR, abs/1012.2599, 2010.
  3. [Bubeck et al., 2009] Sébastien Bubeck, Rémi Munos, and Gilles Stoltz. Pure exploration in multi-armed bandits problems. In Proceedings of the 20th International Con- ference on Algorithmic Learning Theory, pages 23-37, Porto, Portugal, 2009.
  4. [Bubeck et al., 2011] Sébastien Bubeck, Gilles Stoltz, and Jia Yuan Yu. Lipschitz bandits without the lipschitz con- stant. In Proceedings of the 22nd International Conference on Algorithmic Learning Theory, pages 144-158, Espoo, Finland, 2011.
  5. [Carpentier and Munos, 2012] Alexandra Carpentier and Rémi Munos. Bandit theory meets compressed sensing for high dimensional stochastic linear bandit. In Proceed- ings of the 15th International Conference on Artificial Intelligence and Statistics, pages 190-198, La Palma, Canary Islands, 2012.
  6. [Chen et al., 2012] Bo Chen, Rui M. Castro, and Andreas Krause. Joint optimization and variable selection of high-dimensional gaussian processes. In Proceedings of the 29th International Conference on Machine Learning, pages 1423-1430, Edinburgh, Scotland, 2012.
  7. [Collobert et al., 2006] Ronan Collobert, Fabian Sinz, Jason Weston, and Léon Bottou. Trading convexity for scalabil- ity. In Proceedings of the 23rd International Conference on Machine Learning, pages 201-208, Pittsburgh, Penn- sylvania, 2006.
  8. [Djolonga et al., 2013] Josip Djolonga, Andreas Krause, and Volkan Cevher. High-dimensional gaussian process ban- dits. In Advances in Neural Information Processing Sys- tems 26, pages 1025-1033, Lake Tahoe, Nevada, 2013.
  9. [Friesen and Domingos, 2015] Abram L. Friesen and Pe- dro M. Domingos. Recursive decomposition for noncon- vex optimization. In Proceedings of the 24th Interna- tional Joint Conference on Artificial Intelligence, pages 253-259, 2015.
  10. [Hansen et al., 2003] Nikolaus Hansen, Sibylle D. Müller, and Petros Koumoutsakos. Reducing the time complex- ity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES). Evolutionary Computation, 11(1):1-18, 2003.
  11. [Jones et al., 1993] D. R. Jones, C. D. Perttunen, and B. E. Stuckman. Lipschitzian optimization without the lipschitz constant. Journal of Optimization Theory and Applica- tions, 79(1):157-181, 1993.
  12. [Kandasamy et al., 2015] Kirthevasan Kandasamy, Jeff Schneider, and Barnabás Póczos. High dimensional bayesian optimisation and bandits via additive models. In Proceedings of the 32nd International Conference on Machine Learning, pages 295-304, Lille, France, 2015.
  13. [Kawaguchi et al., 2015] Kenji Kawaguchi, Leslie Pack Kaelbling, and Tomás Lozano-Pérez. Bayesian optimiza- tion with exponential convergence. In Advances in Neu- ral Information Processing Systems 28, pages 2791-2799, Montreal, Canada, 2015.
  14. [Munos, 2014] Rémi Munos. From bandits to Monte-Carlo Tree Search: The optimistic principle applied to optimiza- tion and planning. Foundations and Trends in Machine Learning, 7(1):1-130, 2014.
  15. [Pintér, 1996] János D. Pintér. Global Optimization in Ac- tion, Continuous and Lipschitz Optimization: Algorithms, Implementations and Applications. Nonconvex Optimiza- tion and Its Applications. Kluwer Academic Publishers, Dordrecht, Boston, London, 1996.
  16. [Qian and Yu, 2016] Hong Qian and Yang Yu. Scaling si- multaneous optimistic optimization for high-dimensional non-convex functions with low effective dimensions. In Proceedings of the 30th AAAI Conference on Artificial In- telligence, Phoenix, AZ, 2016.
  17. [Snoek et al., 2012] Jasper Snoek, Hugo Larochelle, and Ryan P. Adams. Practical bayesian optimization of ma- chine learning algorithms. In Advances in Neural Infor- mation Processing Systems 25, pages 2960-2968, Lake Tahoe, Nevada, 2012.
  18. [Vapnik, 2000] Vladimir Vapnik. The Nature of Statistical Learning Theory. Springer Science & Business Media, 2000.
  19. [Wang et al., 2013] Ziyu Wang, Masrour Zoghi, Frank Hut- ter, David Matheson, and Nando De Freitas. Bayesian op- timization in high dimensions via random embeddings. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence, pages 1778-1784, Beijing, China, 2013. IJCAI
  20. [Yu et al., 2016] Yang Yu, Hong Qian, and Yi-Qi Hu. Derivative-free optimization via classification. In Proceed- ings of the 30th AAAI Conference on Artificial Intelligence, Phoenix, AZ, 2016.
  21. [Yuille and Rangarajan, 2001] Alan L. Yuille and Anand Rangarajan. The concave-convex procedure (CCCP). In Advances in Neural Information Processing Systems 14, pages 1033-1040, Vancouver, British Columbia, Canada, 2001.
  22. [Zhang et al., 2013] Lijun Zhang, Mehrdad Mahdavi, Rong Jin, Tianbao Yang, and Shenghuo Zhu. Recovering the optimal solution by dual random projection. In Proceed- ings of the 26th Conference on Learning Theory, pages 135-157, Princeton, NJ, 2013.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards