research-article

Understand Dynamic Regret with Switching Cost for Online Decision Making

Authors:

Qian Zhao, Xingxing Zhang,

Jianping YinAuthors Info & Claims

ACM Transactions on Intelligent Systems and Technology (TIST), Volume 11, Issue 3

Article No.: 28, Pages 1 - 21

https://doi.org/10.1145/3375788

Published: 18 April 2020 Publication History

Abstract

As a metric to measure the performance of an online method, dynamic regret with switching cost has drawn much attention for online decision making problems. Although the sublinear regret has been provided in much previous research, we still have little knowledge about the relation between the dynamic regret and the switching cost. In the article, we investigate the relation for two classic online settings: Online Algorithms (OA) and Online Convex Optimization (OCO). We provide a new theoretical analysis framework that shows an interesting observation; that is, the relation between the switching cost and the dynamic regret is different for settings of OA and OCO. Specifically, the switching cost has significant impact on the dynamic regret in the setting of OA. But it does not have an impact on the dynamic regret in the setting of OCO. Furthermore, we provide a lower bound of regret for the setting of OCO, which is same with the lower bound in the case of no switching cost. It shows that the switching cost does not change the difficulty of online decision making problems in the setting of OCO.

References

[1]

Jacob Abernethy, Peter L. Bartlett, Niv Buchbinder, and Isabelle Stanton. 2010. A regularization approach to metrical task systems. In Proceedings of the 21st International Conference on Algorithmic Learning Theory (ALT’10). Springer-Verlag, Berlin, 270--284.

Digital Library

[2]

Lachlan Andrew, Siddharth Barman, Katrina Ligett, Minghong Lin, Adam Meyerson, Alan Roytman, and Adam Wierman. 2013. A tale of two metrics: Simultaneous bounds on competitiveness and regret. In Proceedings of the ACM International Conference on Measurement and Modeling of Computer Systems. 329--330.

Digital Library

[3]

Antonios Antoniadis, Kevin Schewior, and Rudolf Fleischer. 2018. A tight lower bound for online convex optimization with switching costs. In Approximation and Online Algorithms. Springer International Publishing, Cham, 164--175.

[4]

Nikhil Bansal, Niv Buchbinder, and Joseph Naor. 2010. Metrical task systems and the K-server problem on HSTs. In Proceedings of the 37th International Colloquium Conference on Automata, Languages and Programming.

Digital Library

[5]

Amir Beck and Marc Teboulle. 2003. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operat. Res. Lett. 31, 3 (2003), 167--175.

Digital Library

[6]

Andrey Bernstein, Shie Mannor, and Nahum Shimkin. 2010. Online classification with specificity constraints. In Proceedings of Advances in Neural Information Processing Systems (NIPS’10), J. D. Lafferty, C. K. I. Williams, J. Shawe-Taylor, R. S. Zemel, and A. Culotta (Eds.). 190--198.

[7]

Omar Besbes, Yonatan Gur, and Assaf J. Zeevi. 2015. Non-stationary stochastic optimization. Operations Research 63, 5 (2015), 1227--1244.

Digital Library

[8]

Avrim Blum and Carl Burch. 2000. On-line learning and the metrical task system problem. Mach. Learn. 39, 1 (Apr. 2000), 35--58.

Digital Library

[9]

Sébastien Bubeck. 2015. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning 8, 3 (Nov 2015), 231--357.

Digital Library

[10]

Sébastien Bubeck, Michael B. Cohen, James R. Lee, and Yin Tat Lee. 2019. Metrical task systems on trees via mirror descent and unfair gluing. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA’19).

[11]

Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee, James R. Lee, and Aleksander Mkadry. 2018. K-server via multiscale entropic regularization. In Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC’18). ACM, New York, NY, 3--16.

Digital Library

[12]

Niv Buchbinder, Shahar Chen, Joshep (Seffi) Naor, and Ohad Shamir. 2012. Unified algorithms for online learning and competitive analysis. In Proceedings of the 25th Annual Conference on Learning Theory (COLT’12), Shie Mannor, Nathan Srebro, and Robert C. Williamson (Eds.), Vol. 23, 5.1--5.18.

[13]

Niangjun Chen, Anish Agarwal, Adam Wierman, Siddharth Barman, and Lachlan L. H. Andrew. 2015. Online convex optimization using predictions. In Proceedings of the ACM International Conference on Measurement and Modeling of Computer Systems. 191--204.

[14]

Niangjun Chen, Joshua Comden, Zhenhua Liu, Anshul Gandhi, and Adam Wierman. 2016. Using predictions in online optimization: Looking forward with an eye on the past. In Proceedings of the 2016 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Science. 193--206.

Digital Library

[15]

Niangjun Chen, Gautam Goel, and Adam Wierman. 2018. Smoothed online convex optimization in high dimensions via online balanced descent. In Proceedings of the 31st Conference On Learning Theory (COLT’18), Vol. 75. 1574--1594.

[16]

Tianyi Chen, Qing Ling, and Georgios B. Giannakis. 2017. An online convex optimization approach to proactive network resource allocation. IEEE Trans. Sign. Process. 65, 24 (2017), 6350--6364.

Digital Library

[17]

Chao Kai Chiang, Tianbao Yang, Chia Jung Lee, Mehrdad Mahdavi, Chi Jen Lu, Rong Jin, and Shenghuo Zhu. 2012. Online optimization with gradual variations. In Proceedings of the 25th Annual Conference on Learning Theory (COLT'12). 1--20.

[18]

Koby Crammer, Jaz Kandola, and Yoram Singer. 2004. Online classification on a budget. In Proceedings of Advances in Neural Information Processing Systems (NIPS’04). 225--232.

[19]

Xiand Gao, Xiaobo Li, and Shuzhong Zhang. 2018. Online learning with non-convex losses and non-stationary regret. In Proceedings of the 21st International Conference on Artificial Intelligence and Statistics (AISTATS’18), Amos Storkey and Fernando Perez-Cruz (Eds.), Vol. 84. 235--243.

[20]

András György and Csaba Szepesvári. 2016. Shifting regret, mirror descent, and matrices. In Proceedings of the 33rd International Conference on Machine Learning (ICML’16). 2943--2951.

[21]

Eric C. Hall and Rebecca Willett. 2013. Dynamical models and tracking regret in online convex programming. In Proceedings of International Conference on International Conference on Machine Learning (ICML’13).

[22]

Eric C. Hall and Rebecca M. Willett. 2015. Online convex optimization in dynamic environments. IEEE J. Select. Top. Sign. Process. 9, 4 (2015), 647--662.

[23]

Elad Hazan. 2016. Introduction to online convex optimization. Found. Trends Optimiz. 2, 3–4 (2016), 157--325.

Digital Library

[24]

Ali Jadbabaie, Alexander Rakhlin, Shahin Shahrampour, and Karthik Sridharan. 2015. Online optimization: Competing with dynamic comparators. In Proceedings of International Conference on Artificial Intelligence and Statistics (AISTATS’15). 398--406.

[25]

Rodolphe Jenatton, Jim Huang, and Cedric Archambeau. 2016. Adaptive algorithms for online convex optimization with long-term constraints. In Proceedings of the 33rd International Conference on Machine Learning (ICML’16), Vol. 48. 402--411.

[26]

James R. Lee. 2018. Fusible HSTs and the randomized k-server conjecture. In Proceedings of the IEEE 59th Annual Symposium on Foundations of Computer Science.

[27]

Bin Li and Steven C. H. Hoi. 2014. Online portfolio selection: A survey. Comput. Surv. 46, 3 (2014), 35:1--35:36.

Digital Library

[28]

Bin Li, Steven C. H. Hoi, Peilin Zhao, and Vivekanand Gopalkrishnan. 2013. Confidence weighted mean reversion strategy for online portfolio selection. ACM Trans. Knowl. Discov. Data 7, 1 (Mar. 2013), 4:1--4:38.

Digital Library

[29]

C. Li, P. Zhou, L. Xiong, Q. Wang, and T. Wang. 2018. Differentially private distributed online learning. IEEE Trans. Knowl. Data Eng. 30, 8 (Aug. 2018), 1440--1453.

[30]

Yingying Li, Guannan Qu, and Na Li. 2018. Online optimization with predictions and switching costs: Fast algorithms and the fundamental limit. In Proceedings of the Annual American Control Conference (ACC'18). 3008--3013.

[31]

M. Lin, A. Wierman, L. L. H. Andrew, and E. Thereska. 2011. Dynamic right-sizing for power-proportional data centers. In Proceedings of IEEE International Conference on Computer Communications (INFOCOMM’11). 1098--1106.

[32]

Minghong Lin, Adam Wierman, Alan Roytman, Adam Meyerson, and Lachlan L. H. Andrew. 2012. Online optimization with switching cost. SIGMETRICS Perf. Eval. Rev. 40, 3 (2012), 98--100.

Digital Library

[33]

T. Lu, M. Chen, and L. L. H. Andrew. 2013. Simple and effective dynamic provisioning for power-proportional data centers. IEEE Trans. Parallel Distrib. Syst. 24, 6 (Jun. 2013), 1161--1171.

Digital Library

[34]

Aryan Mokhtari, Shahin Shahrampour, Ali Jadbabaie, and Alejandro Ribeiro. 2016. Online optimization in dynamic environments: Improved regret rates for strongly convex problems. In Proceedings of IEEE Conference on Decision and Control (CDC’16). IEEE, 7195--7201.

Digital Library

[35]

Reetabrata Mookherjee, Benjamin F. Hobbs, Terry Lee Friesz, and Matthew A. Rigdon. 2008. Dynamic oligopolistic competition on an electric power network with ramping costs and joint sales constraints. J. Industr. Manage. Optimiz. 4, 3 (11 2008), 425--452.

[36]

Manfred Morari and Jay H. Lee. 1999. Model predictive control: Past, present and future. Comput. Chem. Eng. 23, 4 (1999), 667--682.

[37]

Marc P. Renault and Adi Rosén. 2012. On online algorithms with advice for the k-server problem. In Approximation and Online Algorithms, Roberto Solis-Oba and Giuseppe Persiano (Eds.). Springer, Berlin, 198--210.

[38]

Shai Shalev-Shwartz. 2012. Online learning and online convex optimization. Found. Trends Mach. Learn. 4, 2 (2012), 107--194.

Digital Library

[39]

Y. Sun, K. Tang, L. L. Minku, S. Wang, and X. Yao. 2016. Online ensemble learning of data streams with gradually evolved classes. IEEE Trans. Knowl. Data Eng. 28, 6 (Jun. 2016), 1532--1545.

Digital Library

[40]

Hao Wang, Jianwei Huang, Xiaojun Lin, and Hamed Mohsenian-Rad. 2014. Exploring smart grid and data center interactions for electric power load balancing. SIGMETRICS Perf. Eval. Rev. 41, 3 (Jan. 2014), 89--94.

[41]

Liang Wang, Kuang-chih Lee, and Quan Lu. 2016. Improving advertisement recommendation by enriching user browser cookie attributes. In Proceedings of the 25th ACM International on Conference on Information and Knowledge Management (CIKM’16). 2401--2404.

Digital Library

[42]

M. Wang, C. Xu, X. Chen, H. Hao, L. Zhong, and S. Yu. 2019. Differential privacy oriented distributed online learning for mobile social video prefetching. IEEE Trans. Multimedia 21, 3 (Mar. 2019), 636--651.

[43]

Haiqin Yang, Michael R. Lyu, and Irwin King. 2013. Efficient online learning for multitask feature selection. ACM Trans. Knowl. Discov. Data 7, 2 (Aug. 2013), 6:1--6:27.

Digital Library

[44]

Tianbao Yang, Lijun Zhang, Rong Jin, and Jinfeng Yi. 2016. Tracking slowly moving clairvoyant—Optimal dynamic regret of online learning with true and noisy gradient. In Proceedings of the 34th International Conference on Machine Learning (ICML’16).

[45]

Lijun Zhang, Shiyin Lu, and Zhi-Hua Zhou. 2018. Adaptive online learning in dynamic environments. In Advances in Neural Information Processing Systems 31, S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (Eds.). 1323--1333.

[46]

Lijun Zhang, Tianbao Yang, rong jin, and Zhi-Hua Zhou. 2018. Dynamic regret of strongly adaptive methods. In Proceedings of the 35th International Conference on Machine Learning (ICML’18). 5882--5891.

[47]

Lijun Zhang, Tianbao Yang, Jinfeng Yi, Rong Jin, and Zhi-Hua Zhou. 2017. Improved dynamic regret for non-degenerate functions. In Proceedings of the Conference on Neural Information Processing Systems (NIPS’17).

[48]

Lijun Zhang, Tianbao Yangt, Jinfeng Yi, Rong Jin, and Zhi-Hua Zhou. 2017. Improved dynamic regret for non-degenerate functions. In Proceedings of the 31st International Conference on Neural Information Processing Systems. 732--741.

Digital Library

[49]

Q. Zhang, Q. Zhu, M. F. Zhani, and R. Boutaba. 2012. Dynamic service placement in geographically distributed clouds. In Proceedings of the IEEE 32nd International Conference on Distributed Computing Systems (ICDCS’12). 526--535.

[50]

Yawei Zhao, Shuang Qiu, and Ji Liu. 2018. Proximal online gradient is optimum for dynamic regret. CoRR cs.LG (Oct. 2018). arXiv:cs.LG/1810.03594.

[51]

Martin Zinkevich. 2003. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of International Conference on Machine Learning (ICML’03). 928--935.

Cited By

Zhang YLiu QSun JWu C(2023) The optimal dynamic regret for smoothed online convex optimization with squared norm switching costs Journal of the Franklin Institute10.1016/j.jfranklin.2023.02.013360:6(4297-4330)Online publication date: Apr-2023
https://doi.org/10.1016/j.jfranklin.2023.02.013
Liu QZhang Y(2022) Optimal Dynamic Regret for Online Convex Optimization with Squared l 2 Norm Switching Cost 2022 American Control Conference (ACC)10.23919/ACC53348.2022.9867328(2104-2109)Online publication date: 8-Jun-2022
https://doi.org/10.23919/ACC53348.2022.9867328

Index Terms

Understand Dynamic Regret with Switching Cost for Online Decision Making
1. Computing methodologies
  1. Machine learning
    1. Machine learning algorithms
2. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
      1. Continuous optimization
        Convex optimization

Recommendations

Online convex optimization with switching cost and delayed gradients
Abstract
We consider the online convex optimization (OCO) problem with quadratic and linear switching cost in the limited information setting, where an online algorithm can choose its action using only gradient information about the previous objective ...
Online Bin Packing with Overload Cost
Algorithms and Discrete Applied Mathematics
Abstract
In the classical online bin packing problem, items arriving one by one with a given size not greater than 1 must be packed into unit-capacity bins such that the total size of items packed in a bin does not exceed its capacity; the objective is to ...
Online Results for Black and White Bin Packing

In online bin packing problems, items of sizes in [0, 1] are to be partitioned into subsets of total size at most 1, called bins. We introduce a new variant where items are of two types, called black and white, and the item types must alternate in each ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Intelligent Systems and Technology

ACM Transactions on Intelligent Systems and Technology Volume 11, Issue 3

Survey Paper and Regular Papers

June 2020

286 pages

ISSN:2157-6904

EISSN:2157-6912

DOI:10.1145/3392081

Editor:
Yu Zheng
JD Finance, China

Issue’s Table of Contents

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 April 2020

Accepted: 01 December 2019

Revised: 01 November 2019

Received: 01 June 2019

Published in TIST Volume 11, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

National Natural Science Foundation of China
National Key R 8 D Program of China

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
327
Total Downloads

Downloads (Last 12 months)30
Downloads (Last 6 weeks)2

Reflects downloads up to 24 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang YLiu QSun JWu C(2023) The optimal dynamic regret for smoothed online convex optimization with squared norm switching costs Journal of the Franklin Institute10.1016/j.jfranklin.2023.02.013360:6(4297-4330)Online publication date: Apr-2023
https://doi.org/10.1016/j.jfranklin.2023.02.013
Liu QZhang Y(2022) Optimal Dynamic Regret for Online Convex Optimization with Squared l 2 Norm Switching Cost 2022 American Control Conference (ACC)10.23919/ACC53348.2022.9867328(2104-2109)Online publication date: 8-Jun-2022
https://doi.org/10.23919/ACC53348.2022.9867328

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Issue’s Table of Contents