Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Limit theorems for simulation-based optimization via random search
Chia Y., Glynn P. ACM Transactions on Modeling and Computer Simulation23 (3):1-18,2013.Type:Article
Date Reviewed: Oct 8 2013

It is important to know if a random search for an optimal solution converges or not. Furthermore, if it does converge, then it is important to be able to determine the rate of convergence and the distribution.

A broad range of applications can be modeled for finding the optimal solution of an objective function &agr;(&thgr;), where &thgr; ∈ Λ ∈ Rd. However, for many real-world applications, the analytic form of &agr;(&thgr;) is unknown, rather than a random variable &agr; related to &thgr;. This is due to incomplete information in modeling and possibly some stochastic factors. Therefore, random search has been applied to estimate the expected optimum in practice. In this paper, n independent simulations, or estimations, are assumed. In each of them, the expected value of &agr;(&thgr;), X(&thgr;), is evaluated at m sample exploration points &thgr;1, &thgr;2, &thgr;3, ... , &thgr;(m-1), &thgr;m. Then, the maximum of the sample mean σjn Xj(&thgr;i) n yields the estimated empirical maximum of &agr;(&thgr;i) for i between 1 and m.

The authors of this paper present and prove several theorems to answer the important questions about random search stated at the beginning of this review. Among these theorems, the most significant one is the large sample limit theory for simple (non-adaptive) simulation-based random search for the optimizer of an objective function. That is, under three general assumptions, the maximum of the sample mean σjn Xj(&thgr;i) n converges to the maximum of &agr;(&thgr;) when (log m)/n approaches zero and m*n approaches infinity, as stated in Theorem 2.1 (i). Theorem 2.1 also provides insight into the rates of convergence and the random error associated with such search methods as described in Theorem 3.2.

Although this is a theoretical paper, requiring a strong mathematics background to understand the details, practitioners in the fields of data mining, machine learning, modeling, and simulation will find it worthwhile reading. The theorems presented provide insights on setting the values of exploration (m) and estimation (n) for a simulator with understanding, and on possible estimation of the trade-off in terms of convergence, and more importantly, limit distribution.

Reviewer:  Chenyi Hu Review #: CR141626 (1312-1117)
Bookmark and Share
  Featured Reviewer  
 
Probability And Statistics (G.3 )
 
Would you recommend this review?
yes
no
Other reviews under "Probability And Statistics": Date
Probabilities from fuzzy observations
Yager R. (ed) Information Sciences 32(1): 1-31, 1984. Type: Article
Mar 1 1985
Randomness conservation inequalities; information and independence in mathematical theories
Levin L. Information and Control 61(1): 15-37, 1984. Type: Article
Sep 1 1985
The valuing of management information. Part I: the Bayesian approach
Carter M. Journal of Information Science 10(1): 1-9, 1985. Type: Article
May 1 1986
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy