Tracking Regret Bounds for Online Submodular Optimization

Tatsuya Matsuoka, Shinji Ito, Naoto Ohsaka
Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, PMLR 130:3421-3429, 2021.

Abstract

In this paper, we propose algorithms for online submodular optimization with tracking regret bounds. Online submodular optimization is a generic framework for sequential decision making used to select subsets. Existing algorithms for online submodular optimization have been shown to achieve small (static) regret, which means that the algorithm’s performance is comparable to the performance of a fixed optimal action. Such algorithms, however, may perform poorly in an environment that changes over time. To overcome this problem, we apply a tracking-regret-analysis framework to online submodular optimization, one by which output is assessed through comparison with time-varying optimal subsets. We propose algorithms for submodular minimization, monotone submodular maximization under a size constraint, and unconstrained submodular maximization, and we show tracking regret bounds. In addition, we show that our tracking regret bound for submodular minimization is nearly tight.

Cite this Paper

BibTeX
@InProceedings{pmlr-v130-matsuoka21a, title = { Tracking Regret Bounds for Online Submodular Optimization }, author = {Matsuoka, Tatsuya and Ito, Shinji and Ohsaka, Naoto}, booktitle = {Proceedings of The 24th International Conference on Artificial Intelligence and Statistics}, pages = {3421--3429}, year = {2021}, editor = {Banerjee, Arindam and Fukumizu, Kenji}, volume = {130}, series = {Proceedings of Machine Learning Research}, month = {13--15 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v130/matsuoka21a/matsuoka21a.pdf}, url = {https://proceedings.mlr.press/v130/matsuoka21a.html}, abstract = { In this paper, we propose algorithms for online submodular optimization with tracking regret bounds. Online submodular optimization is a generic framework for sequential decision making used to select subsets. Existing algorithms for online submodular optimization have been shown to achieve small (static) regret, which means that the algorithm’s performance is comparable to the performance of a fixed optimal action. Such algorithms, however, may perform poorly in an environment that changes over time. To overcome this problem, we apply a tracking-regret-analysis framework to online submodular optimization, one by which output is assessed through comparison with time-varying optimal subsets. We propose algorithms for submodular minimization, monotone submodular maximization under a size constraint, and unconstrained submodular maximization, and we show tracking regret bounds. In addition, we show that our tracking regret bound for submodular minimization is nearly tight. } }
Endnote
%0 Conference Paper %T Tracking Regret Bounds for Online Submodular Optimization %A Tatsuya Matsuoka %A Shinji Ito %A Naoto Ohsaka %B Proceedings of The 24th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2021 %E Arindam Banerjee %E Kenji Fukumizu %F pmlr-v130-matsuoka21a %I PMLR %P 3421--3429 %U https://proceedings.mlr.press/v130/matsuoka21a.html %V 130 %X In this paper, we propose algorithms for online submodular optimization with tracking regret bounds. Online submodular optimization is a generic framework for sequential decision making used to select subsets. Existing algorithms for online submodular optimization have been shown to achieve small (static) regret, which means that the algorithm’s performance is comparable to the performance of a fixed optimal action. Such algorithms, however, may perform poorly in an environment that changes over time. To overcome this problem, we apply a tracking-regret-analysis framework to online submodular optimization, one by which output is assessed through comparison with time-varying optimal subsets. We propose algorithms for submodular minimization, monotone submodular maximization under a size constraint, and unconstrained submodular maximization, and we show tracking regret bounds. In addition, we show that our tracking regret bound for submodular minimization is nearly tight.
APA
Matsuoka, T., Ito, S. & Ohsaka, N.. (2021). Tracking Regret Bounds for Online Submodular Optimization . Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 130:3421-3429 Available from https://proceedings.mlr.press/v130/matsuoka21a.html.

Related Material