The stochastic root-finding problem: overview, solutions, and open questions. Pasupathy, R. & Kim, S. *ACM TOMACS*, 21(3):23, 2011.

Paper doi abstract bibtex

Paper doi abstract bibtex

The stochastic root-finding problem (SRFP) is that of finding the zero(s) of a vector function, that is, solving a nonlinear system of equations when the function is expressed implicitly through a stochastic simulation. SRFPs are equivalently expressed as stochastic fixed-point problems, where the underlying function is expressed implicitly via a noisy simulation. After motivating SRFPs using a few examples, we review available methods to solve such problems on constrained Euclidean spaces. We present the current literature as three broad categories, and detail the basic theoretical results that are currently known in each of the categories. With a view towards helping the practitioner, we discuss specific variations in their implementable form, and provide references to computer code when easily available. Finally, we list a few questions that are worthwhile research pursuits from the standpoint of advancing our knowledge of the theoretical underpinnings and the implementation aspects of solutions to SRFPs.

@article{2011paskim, author = {R. Pasupathy and S. Kim}, title = {The stochastic root-finding problem: overview, solutions, and open questions}, journal = {ACM TOMACS}, year = {2011}, volume = {21}, number = {3}, article = {19}, doi = {10.1145/1921598.1921603}, pages = {23}, url = {http://web.ics.purdue.edu/~pasupath/PAPERS/2011paskim.pdf}, keywords = {stochastic root-finding, literature reviews and tutorials}, abstract = {The stochastic root-finding problem (SRFP) is that of finding the zero(s) of a vector function, that is, solving a nonlinear system of equations when the function is expressed implicitly through a stochastic simulation. SRFPs are equivalently expressed as stochastic fixed-point problems, where the underlying function is expressed implicitly via a noisy simulation. After motivating SRFPs using a few examples, we review available methods to solve such problems on constrained Euclidean spaces. We present the current literature as three broad categories, and detail the basic theoretical results that are currently known in each of the categories. With a view towards helping the practitioner, we discuss specific variations in their implementable form, and provide references to computer code when easily available. Finally, we list a few questions that are worthwhile research pursuits from the standpoint of advancing our knowledge of the theoretical underpinnings and the implementation aspects of solutions to SRFPs.}}

Downloads: 0

{"_id":{"_str":"5342a5ef0e946d920a002346"},"__v":1,"authorIDs":["2LsNCSfcuCHZ2bwwk","34rFneKbNhk4MTKFS","3GdCmHtparmeFqq3f","3XoF8DfqJsYFoDYhe","3vW8cvryNS2mm2jBM","4QjGv7n8jm6s54wNw","4WE9bofLYdCkqGsGd","4Y8czGNHCDwAq5yDH","4o9qwLRCQY4absaEb","4teGyL2jzd7wNLJxY","5456dd008b01c8193000000b","5PuuuqCvjCG9cLtzL","5de6d25fabd988de010000a8","5de6e251abd988de010001f3","5de704a645c10edf0100004c","5de7296e97054edf010000d6","5de8368c8cf0fbde01000040","5de851c68ff138de0100001e","5de8f925d5dfa2e00100000d","5de90676d5dfa2e0010000f5","5de9107dd5dfa2e0010001cc","5de95707d574c6de010000bd","5de99b3d59feb7f201000123","5dea64fdddb5e6df0100021a","5deaaf6303c11ade01000148","5ded8dc85fefb3de010000d9","5dedb465e47c43de0100001c","5dee71ac773914de010001ef","5deebb5c0ddb85de01000107","5def1e4cc5ae39f201000194","5def3576e83f7dde01000105","5deff7c414db5cdf0100016f","5df0601be4ce32df0100009e","5df1ecff78da84de01000082","5df20e7fe4cb4ede010000fd","5df42a559d2522de0100012f","5df4756c95416ade0100009f","5df4f25dfc47dbde01000133","5df53020fd245cde0100005d","5df55da3ff5784de01000147","5df5b606a0eab8de01000156","5df7ab64f3cb28df010001b4","5df81fa9d74ee7df01000168","5dfaf58bfa2bbbde010000e1","5dfb5859012925de01000066","5dfb7ea1c2820bdf01000107","5dfba59a749b8bde01000164","5dfbba9ff6f0aede01000124","5dfbfbffb371afde0100001f","5dfc6b1c4a82f3f201000004","5dfccc4f7a3608de0100009d","5dfd1b69ece35ede01000054","5dfd2a23ece35ede01000153","5dfdbb97cdf7c8de010000ef","5dfeeccf5dd8e7df01000085","5e001ed39292b5de010000a9","5e014c336afa18de0100004e","5e0181a6aa04bede01000042","5e044485705486df0100006a","5e04e4fffff612df0100002c","5e056c974b4c94de010000cb","5e05fd62e95bcdde01000022","5e0661287da1d1de0100020a","5e06d44aa0810cde01000093","5e06e1232eda19df01000042","5e075d62764d8ede0100009a","5e080c67cdee3adf01000097","5e08b0dc7dc1dcdf010000a0","5e08dfebcbe70cdf0100006a","5e096462ade67ddf01000016","5e0993db83a3f3de01000090","5e0a0cfb52fbd9de0100001e","5e0a59cace3ebce4010000df","5e0abafa27625ede0100003c","5e0bb52d94c532f301000024","5e0e587dac7d11df01000058","5e0eb12103f891de0100003a","5e1241abc196d3de0100011f","5e134506697554de01000003","5e14ed2cb46f1bdf0100001b","5e15043db46f1bdf0100017c","5e151bb588b10dde0100012b","5e161f09f67f7dde010007cf","5e177d85cf35a4de010000b9","5e192771eaca22df01000017","5e1a17149fbdddde01000024","5e1bd6e44c869ade01000001","5e1c697192587bde01000068","5e1cb74c7723aadf0100017a","5e1d0c1bfeb115df01000001","5e1d3fbc6b18c4df01000102","5e1d8fd93a6d8cde01000178","5e1db3f2d9acfbde010001eb","5e1dc7bb8d71ddde0100013c","5e1dcbbc8d71ddde01000185","5e1e1aeef6dca7f20100013c","5e1e20fdf6dca7f2010001c2","5e1e40cb407a20de01000268","5e1e575b2e41a7de0100013a","5e1e9865bedb58de01000021","5e1f259007379ade0100004b","5e1f4b899ddd0fde01000120","5e1f6ef1e8f5ddde010001bf","5e1ffff214d3c9de01000149","5e2038f302c04cde01000171","5e20a682bdda1fde0100018e","5e20b0485c2065de01000038","5e20dcf1b46c27ee01000122","5e217c6fc7842fde010000b3","5e221fab71dcf8df01000057","5e24e2250e3b0adf01000062","5e250bef2e79a1f2010000e8","5e25c8aaf299d4de01000161","5e25ef17a6f19fde01000276","5e262dba24c8a6de01000036","5e27467118178ede0100002a","5e27b689328b80de0100001a","5e27c523328b80de010000c5","5e28f86441639df301000062","5e29a547fed3e7df01000142","5e2b5bcf6366e2df0100008d","5e2d212d4e7fefde01000048","5e2e568627ce0ade01000051","5e2f89e248b7a4df010000f4","5e3022e57e0df1de01000156","5e302e8546a666df01000050","5e303c8446a666df010001d3","5e30560f57a222df0100012c","5e30cdb02a1e4bde010001d6","5e31fdc67c8d24df0100012c","5e324bfee45eb5df010000bb","5e325105e45eb5df010000f7","5e32d6ed150c84df0100006e","5e32f849c1389bde01000165","5e3443860c807ede010000d1","5e3478d6fae8b9de0100007b","5e385c05ccda85de01000180","5e38773d1f8af9e00100013b","5e388b69030bcadf01000092","5e389cc2030bcadf010001ed","5e38a43d645ed2de01000060","5e38d7b781a46ade01000001","5e3acde7f2a00cdf010001b9","5e3ad6221b85fadf01000051","5e3b0f63ba2e16df0100004a","5e3b83b3184d6ede01000073","5e3b912f184d6ede01000120","5e3c247a34cd37de0100001c","5e3c2eb034cd37de010000e7","5e3cf9fead8243de010000a6","5e3d8eee96e576de010001d1","5e3da0c7f33211df010000ec","5e3dabd9f33211df010001af","5e3dbf3d07ca74de01000102","5e3e13304cdb49de0100008d","5e3e4358018e1dde01000039","5e3f4a5377baf5df010000b6","5e3f532ccd8fe2de01000001","5e42d01be7fe39df010001a5","5e43071baefe1adf01000186","5e434e7ba37866de01000044","5e435ceda37866de010000f8","5e437511b5e412df010000c5","5e43915e639a35de010000cd","5e442947e5a34dde01000029","5e447260084293df01000128","5e448fabec14b3de010000ee","5e44b42430d0bbde0100011f","5e44d347ab9cedde01000015","5e44f43303c52dde01000046","5e44fc2f03c52dde010000ad","5e450b26501a51de0100001c","5e452d6c605639de0100005d","5e4553aca96575df01000165","5e45b9970920e8de0100007b","5e46186fb57382df010000b5","5e46b3888573d1de0100004a","5e49689916841dde010000dd","5e4a03d6cc11a8df01000061","5e4afb99332a9bde0100002c","5e4b486aa44fbbde01000111","5e4bf4df8f0677df01000199","5e4d795d08a8e5de01000194","5e4dab1de671efde010001a5","5e4dc50d682c99de010000bb","5e4e08e9cc196bde010001c3","5e4ea5b564b624de010000e1","5e4f0a6ee5389bde01000022","5e5015c0933046de010000cc","5e5027418c3a2cde01000035","5e545c8488d190df010000c0","5e556b2be11ab9df01000025","5e5603c9819fabdf01000079","5e568bddeb2916df01000115","5e574023bf9f82de010000e0","5e57cb565d5d52de0100012b","5e594017e60e02de010001c9","5e596f1e56d60ade0100018f","5e5a89cfb6725cde010000be","5e5b519474a3e7df0100012d","5e5c359d15d8f5de010000e8","5e5d77a30b73f6de010000d0","5e5dc297c64f0ede01000002","5e5dd063c64f0ede010000a8","5e5e48b0d3955dde01000174","5e5e5c6a5f9e7bee0100011e","5e5fd7f66b32b0f20100021d","5e600b0e13e3aede010001b0","5e602266c064fcde01000264","5e6271e111ac5fde010001e0","5e6579926e5f4cf30100007c","5e66a24e44d2c4de010001f6","5e66b95f4b4a62de01000121","5e6a95dd0e8744de010001aa","5e6b5628e9cf32de010000f0","5eukLewyvtHJ4WPT7","6hj49bCTP57FjutjL","82gBBwyJR2WCNWPWm","9k3X5crnHa5xJ4p7a","AjG6eiMp43eKLk2Yx","BPGmMaEX9pHFcwzrs","BSbB972EuqxRSxK4q","BWawN4hTNFAWjMjHQ","BZn4si3dP7J3H9fky","CcADyySGr39q8rimi","DWYv3xvTzwq9KAjDp","EiCaXco5a7djZngEx","Ey3dnH6u8SFBZSrRS","FCNTJyX4Y757fHDmf","FfpBpZgrPK6GzWzg8","FzE5MgxndyPuqq7uj","GSGoyxizKMrQAYfq7","GguCXKi2NxMS4tNph","KNeor84tRiAGBckxK","KQqLGaFRpAbpBskBQ","KYEFo9TJpP86AhCAr","Lshk7Ffyqph79sBSC","MaifQ9BJT2ed2dZGQ","N5tWeDGAZb5gWkkDp","NBqzAQnD3yAHrJ2xc","NFgFx8pEH8SSsBfeY","NxFbiZ5KXwcqamDsn","NzNpe39Q5DnjHYfXH","Pi7yiWLLHLXG3nQKS","QMz9YsqYMv2FxcrWR","QSqaE2cp2FrPiQW4N","QipRTRhBEJbKr5r5p","QmEqPPCm3CYaeT5sz","RLeConBCygYyJYFjZ","RPFzPgD6mGvvLYagB","RSP7HPs5tD2qvcieu","RZHiDpYi8b2SNKWvW","ReXQXH2CdCDw8CGSa","Ro9bQKrb6shDGMAdv","S6MinMfG29rqRYQA9","SPqCLTdy73wgYcnQq","SSd2xTrkAZtytoyza","SbxH6ZekW7syy7bRy","TSvwARqENambxnPrm","WMvuyWXseWigM3xmR","WPh2SBoox3kFYreuv","WTEpbvXWYyWaLP9fR","WohTL5e4xTKvafcgZ","Xeza9s8dXbXYpiXCF","XgT4w8FQ9GkEwKs4Z","XzSrze7ZA49N8pPiY","Y8f8mN4haHr8RLSHq","YyuePc45BLAbaHYSe","ZA852k8x6E2z78EKG","ZJW3AoAJebLMWuP9e","ZTLzLyaEuYkvrihhG","ZiczJGfQdyYQNodsx","akaiiw9kM3uc3g9w4","avF2hdaGEEAM98DSX","bSLBYQaQ4kKqoatFw","cKdmzfYuhRo469Bmu","cbXkRN6TDnPYEdaDq","cqdiSz7b8NGALu2r4","e5xB5BgjaDsiWNQeH","eJqK7mmamEkYP724x","fDmXj9dfDwJtywS4R","gBzw4TZeaZBiEMuny","giqfvfiFYi6bvnnYB","gjSfEPLukj5tbToTD","gwjZBg4y7YxprKrod","gyB9wdPsiWhZuZB3S","hTJtzpXBRfPtLyahg","hmidXFcMyt4C4yn94","iM2mYTcCiHBmRAkRe","iMRnJkytnZJMAAc5f","iSkAFqqy6ZM5z8rcD","ibBdNBZw79ekcSBLz","kABfYsS38CsgdWfcc","kGiCdK6hwjbt8zbpY","kLrFsm9XJzWKg94Xc","kdYcvNWv7ejC7aRke","kdxhy7dNM6Y7BsmSt","kiejYFiwMiTdLPpLi","mLG769TSC6Nx5jet3","nuLZLT2mGTSaZk8Hn","nzzoR37EXqhbC6wYS","o4GjXhX2JeFovdSwH","oPjFKW9xzDcb2aF6h","p372M7LbgPjAtHFe6","pE86fXX97JPRkRXmh","pnEa7DuEQ8Coe3Cwn","q2GhjiCM95xxsoAgZ","rJJizDq9EQ4nD8vMT","sR38HmZ7bsXuAMSmu","sYCtfEdGGjCWxezsx","t7AdsRiupiQQhetS5","tQXNeq3DmxAYj4iaG","tbirRndbLp4maBSzS","tgCg2KndQiSxduqXp","tkXbW9FMr4dBv2psC","trzPWfze2ysu27QGQ","tupoFJpu7aySR9uR4","ui4w4B9v2H2KfZ36g","uwSXdm9fgEkS8wvhv","vTPqfZG5YeBngrebd","vYnLp8Qk499SgMHX3","vaMBFQq5rkSWq8HoR","vpgPj5ZqG4QWDWBgq","wfXprfNd5cxAnbJqa","x6FX2icxtLjmxSsEM","xededTNbkQkcnyzkK","xreej3aHEdqNvyrTk","y867chrGxEuu8ZsWR","yNwK2BcFRaZ5zdKmA","yTKirEsJv57GFkDEa","zErqDaNgwPAAmXaZ9","za8HG9n7wYCafScuE"],"author_short":["Pasupathy, R.","Kim, S."],"bibbaseid":"pasupathy-kim-thestochasticrootfindingproblemoverviewsolutionsandopenquestions-2011","bibdata":{"bibtype":"article","type":"article","author":[{"firstnames":["R."],"propositions":[],"lastnames":["Pasupathy"],"suffixes":[]},{"firstnames":["S."],"propositions":[],"lastnames":["Kim"],"suffixes":[]}],"title":"The stochastic root-finding problem: overview, solutions, and open questions","journal":"ACM TOMACS","year":"2011","volume":"21","number":"3","article":"19","doi":"10.1145/1921598.1921603","pages":"23","url":"http://web.ics.purdue.edu/~pasupath/PAPERS/2011paskim.pdf","keywords":"stochastic root-finding, literature reviews and tutorials","abstract":"The stochastic root-finding problem (SRFP) is that of finding the zero(s) of a vector function, that is, solving a nonlinear system of equations when the function is expressed implicitly through a stochastic simulation. SRFPs are equivalently expressed as stochastic fixed-point problems, where the underlying function is expressed implicitly via a noisy simulation. After motivating SRFPs using a few examples, we review available methods to solve such problems on constrained Euclidean spaces. We present the current literature as three broad categories, and detail the basic theoretical results that are currently known in each of the categories. With a view towards helping the practitioner, we discuss specific variations in their implementable form, and provide references to computer code when easily available. Finally, we list a few questions that are worthwhile research pursuits from the standpoint of advancing our knowledge of the theoretical underpinnings and the implementation aspects of solutions to SRFPs.","bibtex":"@article{2011paskim,\n\tauthor = {R. Pasupathy and S. Kim},\n\ttitle = {The stochastic root-finding problem: overview, solutions, and open questions},\n\tjournal = {ACM TOMACS},\n\tyear = {2011},\n\tvolume = {21},\n\tnumber = {3},\n\tarticle = {19},\n\tdoi = {10.1145/1921598.1921603},\n\tpages = {23},\n\turl = {http://web.ics.purdue.edu/~pasupath/PAPERS/2011paskim.pdf},\n\tkeywords = {stochastic root-finding, literature reviews and tutorials},\n\tabstract = {The stochastic root-finding problem (SRFP) is that of finding the zero(s) of a vector function, that is, solving a nonlinear system of equations when the function is expressed implicitly through a stochastic simulation. SRFPs are equivalently expressed as stochastic fixed-point problems, where the underlying function is expressed implicitly via a noisy simulation. After motivating SRFPs using a few examples, we review available methods to solve such problems on constrained Euclidean spaces. We present the current literature as three broad categories, and detail the basic theoretical results that are currently known in each of the categories. With a view towards helping the practitioner, we discuss specific variations in their implementable form, and provide references to computer code when easily available. Finally, we list a few questions that are worthwhile research pursuits from the standpoint of advancing our knowledge of the theoretical underpinnings and the implementation aspects of solutions to SRFPs.}}\n\n\n","author_short":["Pasupathy, R.","Kim, S."],"key":"2011paskim","id":"2011paskim","bibbaseid":"pasupathy-kim-thestochasticrootfindingproblemoverviewsolutionsandopenquestions-2011","role":"author","urls":{"Paper":"http://web.ics.purdue.edu/~pasupath/PAPERS/2011paskim.pdf"},"keyword":["stochastic root-finding","literature reviews and tutorials"],"metadata":{"authorlinks":{"pasupathy, r":"https://bibbase.org/show?bib=http://web.ics.purdue.edu/~pasupath/rpVitapublist.bib"}},"html":""},"bibtype":"article","biburl":"http://web.ics.purdue.edu/~pasupath/rpVitapublist.bib","downloads":44,"keywords":["stochastic root-finding","literature reviews and tutorials"],"search_terms":["stochastic","root","finding","problem","overview","solutions","open","questions","pasupathy","kim"],"title":"The stochastic root-finding problem: overview, solutions, and open questions","year":2011,"dataSources":["qnbhPCpdghcXAQgXA"]}