nips nips2011 nips2011-274 nips2011-274-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Shulin Yang, Ali Rahimi
Abstract: We describe a family of global optimization procedures that automatically decompose optimization problems into smaller loosely coupled problems. The solutions of these are subsequently combined with message passing algorithms. We show empirically that these methods produce better solutions with fewer function evaluations than existing global optimization methods. To develop these methods, we introduce a notion of coupling between variables of optimization. This notion of coupling generalizes the notion of independence between random variables in statistics, sparseness of the Hessian in nonlinear optimization, and the generalized distributive law. Despite its generality, this notion of coupling is easier to verify empirically, making structure estimation easy, while allowing us to migrate well-established inference methods on graphical models to the setting of global optimization. 1
Aji, S. and McEliece, R. The generalized distributive law and free energy minimization. IEEE Transaction on Informaion Theory, 46(2), March 2000. Bacchus, F. and Grove, A. Utility independence in a qualitative decision theory. In Proceedings of the 6th International Conference on Principles of Knowledge Representation and Reasoning, pp. 542–552, 1996. Fan, R. E. and Lin, C. J. A study on threshold selection for multi-label classification. Technical report, National Taiwan University, 2007. Hazen, M. and Gupta, M. Gradient estimation in global optimization algorithms. Congress on Evolutionary Computation, pp. 1841–1848, 2009. Huang, C. and Darwiche, A. Inference in belief networks: A procedural guide. International Journal of Approximate Reasoning, 15(3):225–263, 1996. Jensen, F. and Graven-Nielsen, T. Bayesian Networks and Decision Graphs. Springer, 2007. Keeney, R. L. and Raiffa, H. Decisions with Multiple Objectives: Preferences and Value Trade-offs. Wiley, 1976. Koller, D. and Friedman, N. Probabilistic Graphical Models: Principles and Techniques. MIT Press, 2009. Lewis, D., Yang, Y., Rose, T., and Li, F. RCV1: A new benchmark collection for text categorization research. Journal of Machine Learning Research, 2004. Mendes, R., Kennedy, J., and Neves, J. The fully informed particle swarm: Simpler, maybe better. IEEE Transactions on Evolutionary Computation, 1(1):204–210, 2004. Nocedal, J. and Wright, S. Numerical Optimization. Springer, 2nd edition, 2006. Oliva, A. and Torralba, A. Modeling the shape of the scene: a holistic representation of the spatial envelope. International Journal of Computer Vision, 43:145–175, 2001. Pearl, J. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, 1997. Perttunen, C., Jones, D., and Stuckman, B. Lipschitzian optimization without the Lipschitz constant. Journal of Optimization Theory and Application, 79(1):157–181, 1993. Srinivas, N., Krause, A., Kakade, S., and Seeger, M. Gaussian process optimization in the bandit setting: No regret and experimental design. In International Conference on Machine Learning (ICML), 2010. Tague, J. M. The pragmatics of information retrieval experimentation. Information Retrieval Experiment, pp. 59–102, 1981. 9