{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,23]],"date-time":"2024-09-23T03:55:54Z","timestamp":1727063754694},"reference-count":33,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Operations Research"],"published-print":{"date-parts":[[2015,10]]},"abstract":" We consider a non-stationary variant of a sequential stochastic optimization problem, in which the underlying cost functions may change along the horizon. We propose a measure, termed variation budget, that controls the extent of said change, and study how restrictions on this budget impact achievable performance. We identify sharp conditions under which it is possible to achieve long-run average optimality and more refined performance measures such as rate optimality that fully characterize the complexity of such problems. In doing so, we also establish a strong connection between two rather disparate strands of literature: (1) adversarial online convex optimization and (2) the more traditional stochastic approximation paradigm (couched in a non-stationary setting). This connection is the key to deriving well-performing policies in the latter, by leveraging structure of optimal policies in the former. Finally, tight bounds on the minimax regret allow us to quantify the \u201cprice of non-stationarity,\u201d which mathematically captures the added complexity embedded in a temporally changing environment versus a stationary one. <\/jats:p>","DOI":"10.1287\/opre.2015.1408","type":"journal-article","created":{"date-parts":[[2015,9,14]],"date-time":"2015-09-14T17:40:04Z","timestamp":1442252404000},"page":"1227-1244","source":"Crossref","is-referenced-by-count":169,"title":["Non-Stationary Stochastic Optimization"],"prefix":"10.1287","volume":"63","author":[{"given":"Omar","family":"Besbes","sequence":"first","affiliation":[{"name":"Columbia University, New York, New York 10027"}]},{"given":"Yonatan","family":"Gur","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, California 94305"}]},{"given":"Assaf","family":"Zeevi","sequence":"additional","affiliation":[{"name":"Columbia University, New York, New York 10027"}]}],"member":"109","reference":[{"key":"B1","first-page":"28","volume-title":"Proc. 23rd Ann. Conf. Learn. Theory, COLT \u201910","author":"Agarwal A","year":"2010"},{"key":"B2","doi-asserted-by":"publisher","DOI":"10.1137\/110850827"},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1002\/9780470400531.eorms0728"},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1287\/moor.23.4.769"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-75894-2"},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1137\/080734510"},{"key":"B7","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.1120.1654"},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1100.0867"},{"key":"B9","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1956.6.1"},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1120.1057"},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546921"},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2009.2019797"},{"key":"B13","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.2013.1788"},{"key":"B14","first-page":"385","volume-title":"Proc. Sixteenth Ann. ACM-SIAM Sympos. Discrete Algorithms","author":"Flaxman AD","year":"2005"},{"key":"B15","first-page":"97","volume-title":"Contubotions to the Theory of Games","volume":"3","author":"Hannan J","year":"1957"},{"key":"B16","doi-asserted-by":"publisher","DOI":"10.1002\/0471221546"},{"key":"B17","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-010-5175-x"},{"key":"B18","first-page":"421","volume":"19","author":"Hazan E","year":"2011","journal-title":"J. Machine Learn. Res. Proceedings Track"},{"key":"B19","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-007-5016-8"},{"key":"B20","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1080.0355"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45167-9_4"},{"key":"B22","first-page":"35","volume":"81","author":"Kalman RE","year":"1960","journal-title":"J. Fluids Engrg."},{"key":"B23","doi-asserted-by":"publisher","DOI":"10.1111\/1467-937X.00095"},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2014.1294"},{"key":"B25","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729392"},{"key":"B26","first-page":"697","volume-title":"Adv. Neural Inform. Processing Systems 17","author":"Kleinberg RD","year":"2004"},{"key":"B27","volume-title":"Stochastic Approximation and Recursive Algorithms and Applications","author":"Kushner HJ","year":"2003"},{"key":"B28","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1051027873"},{"key":"B29","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27819-1_8"},{"key":"B30","volume-title":"Problem Complexity and Method Efficiency in Optimization","author":"Nemirovski A","year":"1983"},{"key":"B31","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729586"},{"key":"B32","volume-title":"Introduction to Nonparametric Estimation","author":"Tsybakov AB","year":"2008"},{"key":"B33","first-page":"928","volume-title":"20th Internat. Conf. Machine Learn.","author":"Zinkevich M","year":"2003"}],"container-title":["Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/opre.2015.1408","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,2]],"date-time":"2023-04-02T11:19:53Z","timestamp":1680434393000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/opre.2015.1408"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,10]]},"references-count":33,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2015,10]]}},"alternative-id":["10.1287\/opre.2015.1408"],"URL":"https:\/\/doi.org\/10.1287\/opre.2015.1408","relation":{},"ISSN":["0030-364X","1526-5463"],"issn-type":[{"value":"0030-364X","type":"print"},{"value":"1526-5463","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,10]]}}}