{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,22]],"date-time":"2026-03-22T06:42:05Z","timestamp":1774161725016,"version":"3.50.1"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2019,3,26]],"date-time":"2019-03-26T00:00:00Z","timestamp":1553558400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1617698, 1717588, 1730128, 1633299, 1612501"],"award-info":[{"award-number":["1617698, 1717588, 1730128, 1633299, 1612501"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2019,3,26]]},"abstract":"<jats:p>Due to mainstream adoption of cloud computing and its rapidly increasing usage of energy, the efficient management of cloud computing resources has become an important issue. A key challenge in managing the resources lies in the volatility of their demand. While there have been a wide variety of online algorithms (e.g. Receding Horizon Control, Online Balanced Descent) designed, it is hard for cloud operators to pick the right algorithm. In particular, these algorithms vary greatly on their usage of predictions and performance guarantees. This paper aims at studying an automatic algorithm selection scheme in real time. To do this, we empirically study the prediction errors from real-world cloud computing traces. Results show that prediction errors are distinct from different prediction algorithms, across virtual machines, and over the time horizon. Based on these observations, we propose a simple prediction error model and prove upper bounds on the dynamic regret of several online algorithms. We then apply the empirical and theoretical results to create a simple online meta-algorithm that chooses the best algorithm on the fly. Numerical simulations demonstrate that the performance of the designed policy is close to that of the best algorithm in hindsight.<\/jats:p>","DOI":"10.1145\/3322205.3311087","type":"journal-article","created":{"date-parts":[[2020,3,26]],"date-time":"2020-03-26T13:12:37Z","timestamp":1585228357000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":25,"title":["Online Optimization in Cloud Resource Provisioning"],"prefix":"10.1145","volume":"3","author":[{"given":"Joshua","family":"Comden","sequence":"first","affiliation":[{"name":"Stony Brook University, Stony Brook, NY, USA"}]},{"given":"Sijie","family":"Yao","sequence":"additional","affiliation":[{"name":"Stony Brook University, Stony Brook, NY, USA"}]},{"given":"Niangjun","family":"Chen","sequence":"additional","affiliation":[{"name":"Institute of High Performance Computing, Singapore, Singapore"}]},{"given":"Haipeng","family":"Xing","sequence":"additional","affiliation":[{"name":"Stony Brook University, Stony Brook, NY, USA"}]},{"given":"Zhenhua","family":"Liu","sequence":"additional","affiliation":[{"name":"Department of Applied Mathematics &amp; Statistics, Stony Brook University, NY, USA"}]}],"member":"320","published-online":{"date-parts":[[2019,3,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSC.2017.2711009"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2494621.2494630"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465529.2465533"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1811099.1811044"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/SYNASC.2014.66"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/CloudCom.2012.6427605"},{"key":"e_1_2_1_7_1","volume-title":"et almbox","author":"Badger Lee","year":"2012"},{"key":"e_1_2_1_8_1","unstructured":"Jeff Barr. 2018. New AWS Auto Scaling -- Unified Scaling For Your Cloud Applications. https:\/\/aws.amazon.com\/blogs\/aws\/aws-auto-scaling-unified-scaling-for-your-cloud-applications\/.  Jeff Barr. 2018. New AWS Auto Scaling -- Unified Scaling For Your Cloud Applications. https:\/\/aws.amazon.com\/blogs\/aws\/aws-auto-scaling-unified-scaling-for-your-cloud-applications\/."},{"key":"e_1_2_1_9_1","volume-title":"Non-stationary stochastic optimization. Operations research","author":"Besbes Omar","year":"2015"},{"key":"e_1_2_1_10_1","volume-title":"Kevin Canini, Armando Fox, Michael Jordan, and David A Patterson.","author":"Bodik Peter","year":"2008"},{"key":"e_1_2_1_11_1","unstructured":"Allan Borodin and Ran El-Yaniv. 2005. Online computation and competitive analysis .cambridge university press.   Allan Borodin and Ran El-Yaniv. 2005. Online computation and competitive analysis .cambridge university press."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28435"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146588"},{"key":"e_1_2_1_14_1","volume-title":"The Changing Faces of the Cloud","author":"Brinda Mark","year":"2017"},{"key":"e_1_2_1_15_1","volume-title":"Model predictive control","author":"Camacho Eduardo F"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Eddy Caron Fr\u00e9d\u00e9ric Desprez and Adrian Muresan. 2010. Forecasting for Cloud computing on-demand resources based on pattern matching. (2010).  Eddy Caron Fr\u00e9d\u00e9ric Desprez and Adrian Muresan. 2010. Forecasting for Cloud computing on-demand resources based on pattern matching. (2010).","DOI":"10.1109\/CloudCom.2010.65"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2796314.2745854"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2896377.2901464"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 31st Conference On Learning Theory (Proceedings of Machine Learning Research), , S\u00e9bastien Bubeck, Vianney Perchet, and Philippe Rigollet (Eds.)","volume":"75","author":"Chen Niangjun","year":"2018"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2015.06.014"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/1251203.1251223"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3322205.3311087"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132747.3132772"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCC.2014.6912590"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/356733.356735"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1273440.1250665"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0005-1098(89)90002-2"},{"key":"e_1_2_1_28_1","first-page":"9","article-title":"PRESS: PRedictive Elastic ReSource Scaling for cloud systems","volume":"10","author":"Gong Zhenhuan","year":"2010","journal-title":"CNSM"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSTSP.2015.2404790"},{"key":"e_1_2_1_30_1","volume-title":"Communications and Networks (CECNet), 2012 2nd International Conference on. IEEE","author":"Huang Jinhui","year":"2012"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2011.05.027"},{"key":"e_1_2_1_32_1","unstructured":"Ali Jadbabaie Alexander Rakhlin Shahin Shahrampour and Karthik Sridharan. 2015. Online optimization: Competing with dynamic comparators. In Artificial Intelligence and Statistics. 398--406.  Ali Jadbabaie Alexander Rakhlin Shahin Shahrampour and Karthik Sridharan. 2015. Online optimization: Competing with dynamic comparators. In Artificial Intelligence and Statistics. 398--406."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1555228.1555261"},{"key":"e_1_2_1_34_1","volume-title":"Advanced Communication Technology (ICACT), 2016 18th International Conference on . IEEE, 478--483","author":"Kan Chuanqi","year":"2016"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/VECIMS.2010.5609349"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/IGCC.2012.6322266"},{"key":"e_1_2_1_37_1","volume-title":"2011 Proceedings IEEE INFOCOM .","author":"Lin Minghong"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2012.2226216"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1009"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCGRID.2010.80"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/SCC.2010.69"},{"key":"e_1_2_1_42_1","doi-asserted-by":"crossref","DOI":"10.1109\/9.262032","volume-title":"Robust receding horizon control of constrained nonlinear systems","author":"Michalska Hanna","year":"1993"},{"key":"e_1_2_1_43_1","unstructured":"Laura R Moore Kathryn Bean and Tariq Ellahi. 2013. A coordinated reactive and predictive approach to cloud elasticity. (2013).  Laura R Moore Kathryn Bean and Tariq Ellahi. 2013. A coordinated reactive and predictive approach to cloud elasticity. (2013)."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/CLOUD.2011.42"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2014.6848208"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2017.2743462"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2788402.2788405"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1998582.1998623"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/MASCOTS.2011.70"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2009.5062123"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2016.2607840"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2017.8057118"},{"key":"e_1_2_1_54_1","volume-title":"Proceedings of the 20th International Conference on Machine Learning (ICML-03)","author":"Zinkevich Martin","year":"2003"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3322205.3311087","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3322205.3311087","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3322205.3311087","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:25:55Z","timestamp":1750206355000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3322205.3311087"}},"subtitle":["Predictions, Regrets, and Algorithms"],"short-title":[],"issued":{"date-parts":[[2019,3,26]]},"references-count":53,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,3,26]]}},"alternative-id":["10.1145\/3322205.3311087"],"URL":"https:\/\/doi.org\/10.1145\/3322205.3311087","relation":{},"ISSN":["2476-1249"],"issn-type":[{"value":"2476-1249","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,3,26]]},"assertion":[{"value":"2019-03-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}