{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T08:23:35Z","timestamp":1775031815182,"version":"3.50.1"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,5,27]],"date-time":"2020-05-27T00:00:00Z","timestamp":1590537600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["1637598"],"award-info":[{"award-number":["1637598"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["1518941"],"award-info":[{"award-number":["1518941"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100008536","name":"Amazon Web Services","doi-asserted-by":"publisher","award":["Amazon AWS AI Fellowship"],"award-info":[{"award-number":["Amazon AWS AI Fellowship"]}],"id":[{"id":"10.13039\/100008536","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":[[2020,5,27]]},"abstract":"<jats:p>We study online optimization in a setting where an online learner seeks to optimize a per-round hitting cost, which may be non-convex, while incurring a movement cost when changing actions between rounds. We ask:under what general conditions is it possible for an online learner to leverage predictions of future cost functions in order to achieve near-optimal costs? Prior work has provided near-optimal online algorithms for specific combinations of assumptions about hitting and switching costs, but no general results are known. In this work, we give two general sufficient conditions that specify a relationship between the hitting and movement costs which guarantees that a new algorithm, Synchronized Fixed Horizon Control (SFHC), achieves a 1+O(1\/w) competitive ratio, where w is the number of predictions available to the learner. Our conditions do not require the cost functions to be convex, and we also derive competitive ratio results for non-convex hitting and movement costs. Our results provide the first constant, dimension-free competitive ratio for online non-convex optimization with movement costs. We also give an example of a natural problem, Convex Body Chasing (CBC), where the sufficient conditions are not satisfied and prove that no online algorithm can have a competitive ratio that converges to 1.<\/jats:p>","DOI":"10.1145\/3379484","type":"journal-article","created":{"date-parts":[[2020,5,28]],"date-time":"2020-05-28T04:29:21Z","timestamp":1590640161000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Online Optimization with Predictions and Non-convex Losses"],"prefix":"10.1145","volume":"4","author":[{"given":"Yiheng","family":"Lin","sequence":"first","affiliation":[{"name":"Tsinghua University, Beijing, China"}]},{"given":"Gautam","family":"Goel","sequence":"additional","affiliation":[{"name":"California Institute of Technology, Pasadena, CA, USA"}]},{"given":"Adam","family":"Wierman","sequence":"additional","affiliation":[{"name":"California Institute of Technology, Pasadena, CA, USA"}]}],"member":"320","published-online":{"date-parts":[[2020,5,27]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465529.2465533"},{"key":"e_1_2_1_2_1","volume-title":"LATIN 2016: Theoretical Informatics","author":"Antoniadis Antonios","unstructured":"Antonios Antoniadis , Neal Barcelo , Michael Nugent , Kirk Pruhs , Kevin Schewior , and Michele Scquizzato . 2016. Chasing convex bodies and functions . In LATIN 2016: Theoretical Informatics . Springer , 68--81. Antonios Antoniadis, Neal Barcelo, Michael Nugent, Kirk Pruhs, Kevin Schewior, and Michele Scquizzato. 2016. Chasing convex bodies and functions. In LATIN 2016: Theoretical Informatics. Springer, 68--81."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the International Workshop on Approximation and Online Algorithms. Springer, 164--175","author":"Antoniadis Antonios","year":"2017","unstructured":"Antonios Antoniadis and Kevin Schewior . 2017 . A tight lower bound for online convex optimization with switching costs . In Proceedings of the International Workshop on Approximation and Online Algorithms. Springer, 164--175 . Antonios Antoniadis and Kevin Schewior. 2017. A tight lower bound for online convex optimization with switching costs. In Proceedings of the International Workshop on Approximation and Online Algorithms. Springer, 164--175."},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"David Ardia Kris Boudt Peter Carl Katharine M Mullen and Brian Peterson. 2010. Differential evolution (deoptim) for non-convex portfolio optimization. (2010).  David Ardia Kris Boudt Peter Carl Katharine M Mullen and Brian Peterson. 2010. Differential evolution (deoptim) for non-convex portfolio optimization. (2010).","DOI":"10.32614\/RJ-2011-005"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.8"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.93"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a006"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1756006.1953023"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2015.7403279"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2015.7403279"},{"key":"e_1_2_1_11_1","volume-title":"Potential-function proofs for first-order methods. arXiv preprint arXiv:1712.04581","author":"Bansal Nikhil","year":"2017","unstructured":"Nikhil Bansal and Anupam Gupta . 2017. Potential-function proofs for first-order methods. arXiv preprint arXiv:1712.04581 ( 2017 ). Nikhil Bansal and Anupam Gupta. 2017. Potential-function proofs for first-order methods. arXiv preprint arXiv:1712.04581 (2017)."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.","author":"Bansal Nikhil","year":"2015","unstructured":"Nikhil Bansal , Anupam Gupta , Ravishankar Krishnaswamy , Kirk Pruhs , Kevin Schewior , and Cliff Stein . 2015 . A 2-competitive algorithm for online convex optimization with switching costs . In Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Nikhil Bansal, Anupam Gupta, Ravishankar Krishnaswamy, Kirk Pruhs, Kevin Schewior, and Cliff Stein. 2015. A 2-competitive algorithm for online convex optimization with switching costs. In Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258667"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007621832648"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146588"},{"key":"e_1_2_1_16_1","volume-title":"et almbox","author":"Bubeck S\u00e9bastien","year":"2012","unstructured":"S\u00e9bastien Bubeck , Nicolo Cesa-Bianchi , et almbox . 2012 . Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends\u00ae in Machine Learning , Vol. 5 , 1 (2012), 1--122. S\u00e9bastien Bubeck, Nicolo Cesa-Bianchi, et almbox. 2012. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends\u00ae in Machine Learning , Vol. 5, 1 (2012), 1--122."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188798"},{"key":"e_1_2_1_18_1","volume-title":"Yuanzhi Li, and Mark Sellke.","author":"Bubeck S\u00e9bastien","year":"2018","unstructured":"S\u00e9bastien Bubeck , Yin Tat Lee , Yuanzhi Li, and Mark Sellke. 2018 b. Chasing nested convex bodies nearly optimally. arXiv preprint arXiv:1811.00999 (2018). S\u00e9bastien Bubeck, Yin Tat Lee, Yuanzhi Li, and Mark Sellke. 2018b. Chasing nested convex bodies nearly optimally. arXiv preprint arXiv:1811.00999 (2018)."},{"key":"e_1_2_1_19_1","volume-title":"Improved path-length regret bounds for bandits. arXiv preprint arXiv:1901.10604","author":"Bubeck S\u00e9bastien","year":"2019","unstructured":"S\u00e9bastien Bubeck , Yuanzhi Li , Haipeng Luo , and Chen-Yu Wei . 2019. Improved path-length regret bounds for bandits. arXiv preprint arXiv:1901.10604 ( 2019 ). S\u00e9bastien Bubeck, Yuanzhi Li, Haipeng Luo, and Chen-Yu Wei. 2019. Improved path-length regret bounds for bandits. arXiv preprint arXiv:1901.10604 (2019)."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.7"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2796314.2745854"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2964791.2901464"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of Conference On Learning Theory (COLT). 1574--1594","author":"Chen Niangjun","year":"2018","unstructured":"Niangjun Chen , Gautam Goel , and Adam Wierman . 2018 . Smoothed Online Convex Optimization in High Dimensions via Online Balanced Descent . In Proceedings of Conference On Learning Theory (COLT). 1574--1594 . Niangjun Chen, Gautam Goel, and Adam Wierman. 2018. Smoothed Online Convex Optimization in High Dimensions via Online Balanced Descent. In Proceedings of Conference On Learning Theory (COLT). 1574--1594."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3322205.3311087"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2010.109"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2017.8263834"},{"key":"e_1_2_1_27_1","volume-title":"Advances in Neural Information Processing Systems 32, H. Wallach, H. Larochelle, A. Beygelzimer, F. dtextquotesingle Alch\u00e9-Buc","author":"Goel Gautam","year":"1873","unstructured":"Gautam Goel , Yiheng Lin , Haoyuan Sun , and Adam Wierman . 2019. Beyond Online Balanced Descent: An Optimal Algorithm for Smoothed Online Optimization . In Advances in Neural Information Processing Systems 32, H. Wallach, H. Larochelle, A. Beygelzimer, F. dtextquotesingle Alch\u00e9-Buc , E. Fox, and R. Garnett (Eds.). Curran Associates, Inc. , 1873 --1883. http:\/\/papers.nips.cc\/paper\/8463-beyond-online-balanced-descent-an-optimal-algorithm-for-smoothed-online-optimization.pdf Gautam Goel, Yiheng Lin, Haoyuan Sun, and Adam Wierman. 2019. Beyond Online Balanced Descent: An Optimal Algorithm for Smoothed Online Optimization. In Advances in Neural Information Processing Systems 32, H. Wallach, H. Larochelle, A. Beygelzimer, F. dtextquotesingle Alch\u00e9-Buc, E. Fox, and R. Garnett (Eds.). Curran Associates, Inc., 1873--1883. http:\/\/papers.nips.cc\/paper\/8463-beyond-online-balanced-descent-an-optimal-algorithm-for-smoothed-online-optimization.pdf"},{"key":"e_1_2_1_28_1","first-page":"2504","article-title":"An Online Algorithm for Smoothed Regression and LQR Control","volume":"89","author":"Goel Gautam","year":"2019","unstructured":"Gautam Goel and Adam Wierman . 2019 . An Online Algorithm for Smoothed Regression and LQR Control . In Proceedings of the Machine Learning Research , Vol. 89. 2504 -- 2513 . http:\/\/proceedings.mlr.press\/v89\/goel19a.html Gautam Goel and Adam Wierman. 2019. An Online Algorithm for Smoothed Regression and LQR Control. In Proceedings of the Machine Learning Research, Vol. 89. 2504--2513. http:\/\/proceedings.mlr.press\/v89\/goel19a.html","journal-title":"Proceedings of the Machine Learning Research"},{"key":"e_1_2_1_29_1","first-page":"3","article-title":"Introduction to online convex optimization","volume":"2","author":"Elad Hazan","year":"2016","unstructured":"Elad Hazan et almbox. 2016 . Introduction to online convex optimization . Foundations and Trends in Optimization , Vol. 2 , 3 -- 4 (2016), 157--325. Elad Hazan et almbox. 2016. Introduction to online convex optimization. Foundations and Trends in Optimization , Vol. 2, 3--4 (2016), 157--325.","journal-title":"Foundations and Trends in Optimization"},{"key":"e_1_2_1_30_1","volume-title":"et almbox","author":"Jain Prateek","year":"2017","unstructured":"Prateek Jain , Purushottam Kar , et almbox . 2017 . Non-convex optimization for machine learning. Foundations and Trends\u00ae in Machine Learning , Vol. 10 , 3--4 (2017), 142--336. Prateek Jain, Purushottam Kar, et almbox. 2017. Non-convex optimization for machine learning. Foundations and Trends\u00ae in Machine Learning , Vol. 10, 3--4 (2017), 142--336."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2012.6195799"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSG.2016.2539948"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783356"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.21314\/JOR.2002.057"},{"key":"e_1_2_1_35_1","volume-title":"Online optimization with predictions and switching costs: Fast algorithms and the fundamental limit. arXiv preprint arXiv:1801.07780","author":"Li Yingying","year":"2018","unstructured":"Yingying Li , Guannan Qu , and Na Li. 2018a. Online optimization with predictions and switching costs: Fast algorithms and the fundamental limit. arXiv preprint arXiv:1801.07780 ( 2018 ). Yingying Li, Guannan Qu, and Na Li. 2018a. Online optimization with predictions and switching costs: Fast algorithms and the fundamental limit. arXiv preprint arXiv:1801.07780 (2018)."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.23919\/ACC.2018.8431296"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/IGCC.2012.6322266"},{"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.1145\/2160803.2160862"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCNS.2014.2309732"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCNS.2014.2323634"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90003-W"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007697429651"},{"key":"e_1_2_1_44_1","unstructured":"Arkadii Semenovich Nemirovsky and David Borisovich Yudin. 1983. Problem complexity and method efficiency in optimization. (1983).  Arkadii Semenovich Nemirovsky and David Borisovich Yudin. 1983. Problem complexity and method efficiency in optimization. (1983)."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.92"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341617.3326136"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3224420"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1785481.1785532"},{"key":"e_1_2_1_49_1","volume-title":"Proceedings of the 20th International Conference on Machine Learning (ICML-03)","author":"Zinkevich Martin","year":"2003","unstructured":"Martin Zinkevich . 2003 . Online convex programming and generalized infinitesimal gradient ascent . In Proceedings of the 20th International Conference on Machine Learning (ICML-03) . 928--936. Martin Zinkevich. 2003. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning (ICML-03) . 928--936."},{"key":"e_1_2_1_50_1","first-page":"119","article-title":"Jensen's inequality for nonconvex functions","volume":"9","author":"Zlobec Sanjo","year":"2004","unstructured":"Sanjo Zlobec . 2004 . Jensen's inequality for nonconvex functions . Mathematical Communications , Vol. 9 , 2 (2004), 119 -- 124 . Sanjo Zlobec. 2004. Jensen's inequality for nonconvex functions. Mathematical Communications , Vol. 9, 2 (2004), 119--124.","journal-title":"Mathematical Communications"}],"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\/3379484","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3379484","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3379484","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:22Z","timestamp":1750197742000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3379484"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,27]]},"references-count":50,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,5,27]]}},"alternative-id":["10.1145\/3379484"],"URL":"https:\/\/doi.org\/10.1145\/3379484","relation":{},"ISSN":["2476-1249"],"issn-type":[{"value":"2476-1249","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,5,27]]},"assertion":[{"value":"2020-05-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}