{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T14:28:01Z","timestamp":1778855281424,"version":"3.51.4"},"reference-count":16,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2012,1,4]],"date-time":"2012-01-04T00:00:00Z","timestamp":1325635200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMETRICS Perform. Eval. Rev."],"published-print":{"date-parts":[[2012,12,4]]},"abstract":"<jats:p>We consider algorithms for \"smoothed online convex optimization (SOCO)\" problems. SOCO is a variant of the class of \"online convex optimization (OCO)\" problems that is strongly related to the class of \"metrical task systems\", each of which have been studied extensively. Prior literature on these problems has focused on two performance metrics: regret and competitive ratio. There exist known algorithms with sublinear regret and known algorithms with constant competitive ratios; however no known algorithms achieve both. In this paper, we show that this is due to a fundamental incompatibility between regret and the competitive ratio -- no algorithm (deterministic or randomized) can achieve sublinear regret and a constant competitive ratio, even in the case when the objective functions are linear.<\/jats:p>","DOI":"10.1145\/2425248.2425275","type":"journal-article","created":{"date-parts":[[2013,1,8]],"date-time":"2013-01-08T15:34:16Z","timestamp":1357659256000},"page":"98-100","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Online optimization with switching cost"],"prefix":"10.1145","volume":"40","author":[{"given":"Minghong","family":"Lin","sequence":"first","affiliation":[{"name":"CMS, California Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adam","family":"Wierman","sequence":"additional","affiliation":[{"name":"CMS, California Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alan","family":"Roytman","sequence":"additional","affiliation":[{"name":"UCLA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adam","family":"Meyerson","sequence":"additional","affiliation":[{"name":"UCLA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lachlan L.H.","family":"Andrew","sequence":"additional","affiliation":[{"name":"Swinburne University of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,1,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-9965.1991.tb00002.x"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/777412.777420"},{"key":"e_1_2_1_3_1","volume-title":"Efficient algorithms for universal portfolios,\" in Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS)","author":"Kalai A.","year":"2000","unstructured":"A. Kalai and S. Vempala , \" Efficient algorithms for universal portfolios,\" in Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS) , 2000 . A. Kalai and S. Vempala, \"Efficient algorithms for universal portfolios,\" in Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS), 2000."},{"key":"e_1_2_1_4_1","unstructured":"M. Zinkevich \"Online convex programming and generalized in finitesimal gradient ascent \" 2003.  M. Zinkevich \"Online convex programming and generalized in finitesimal gradient ascent \" 2003."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-007-5016-8"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2011.5934885"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/IGCC.2012.6322266"},{"key":"e_1_2_1_8_1","first-page":"3728","article-title":"Variability aware network utility maximization","volume":"1111","author":"Joseph V.","year":"2011","unstructured":"V. Joseph and G. de Veciana , \" Variability aware network utility maximization ,\" CoRR , vol. abs\/ 1111 . 3728 , 2011 . V. Joseph and G. de Veciana, \"Variability aware network utility maximization,\" CoRR, vol. abs\/1111.3728, 2011.","journal-title":"CoRR"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/JLT.2005.855663"},{"key":"e_1_2_1_10_1","volume-title":"Characteristics and costs,\" Congressional Research Service","author":"Kaplan S.","year":"2008","unstructured":"S. Kaplan , \"Power plants : Characteristics and costs,\" Congressional Research Service , 2008 . S. Kaplan, \"Power plants: Characteristics and costs,\" Congressional Research Service, 2008."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/9.486316"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02930-1_41"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146588"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62243"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1992.267772"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374411"}],"container-title":["ACM SIGMETRICS Performance Evaluation Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2425248.2425275","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2425248.2425275","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:14:09Z","timestamp":1750277649000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2425248.2425275"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1,4]]},"references-count":16,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,12,4]]}},"alternative-id":["10.1145\/2425248.2425275"],"URL":"https:\/\/doi.org\/10.1145\/2425248.2425275","relation":{},"ISSN":["0163-5999"],"issn-type":[{"value":"0163-5999","type":"print"}],"subject":[],"published":{"date-parts":[[2012,1,4]]},"assertion":[{"value":"2012-01-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}