AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Tsinghua Science and Technology Article
PDF (667.1 KB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

Online Weakly DR-Submodular Optimization Under Stochastic Cumulative Constraints

Beijing Institute for Scientific and Engineering Computing, Beijing University of Technology, Beijing 100124, China
Show Author Information

Abstract

In this paper, we study a class of online continuous optimization problems. At each round, the utility function is the sum of a weakly diminishing-returns (DR) submodular function and a concave function, certain cost associated with the action will occur, and the problem has total limited budget. Combining the two methods, the penalty function and Frank-Wolfe strategies, we present an online method to solve the considered problem. Choosing appropriate stepsize and penalty parameters, the performance of the online algorithm is guaranteed, that is, it achieves sub-linear regret bound and certain mild constraint violation bound in expectation.

Keywords

online maximizationweakly DR-submodularregretstochastic

References

[1]

E. Hazan, Introduction to online convex optimization, Found. Trends Optim., vol. 2, nos. 3&4, pp. 157–325, 2016.
Crossref Google Scholar
[2]
E. Hazan and E. Minasyan, Faster projection-free online learning, arXiv preprint arXiv: 2001.11568, 2020.
[3]

F. Bach, Submodular functions: From discrete to continuous domains, Math. Program., vol. 175, nos. 1&2, pp. 419–459, 2019.
Crossref Google Scholar
[4]
A. Bian, J. M. Buhmann, and A. Krause, Optimal continuous DR-submodular maximization and applications to provable mean field inference, PMIR, vol. 97, pp. 644−653, 2018.
[5]
A. Bian, K. Levy, A. Krause, and J. M. Buhmann, Non-monotone continuous DR-submodular maximization: Structure and algorithms, in Proc. 31 st Int. Conf. Neural Information Processing Systems, Long Beach, CA, USA, 2017.
Crossref
[6]
H. Hassani, M. Soltanolkotabi, and A. Karbasi, Gradient methods for submodular maximization, in Proc. 31 st Int. Conf. Neural Information Processing Systems, Long Beach, CA, USA, 2017.
[7]
A. Mokhtari, H. Hassani, and A. Karbasi, Conditional gradient method for stochastic submodular maximization: Closing the gap, arXiv preprint arXiv: 1711.01660, 2017.
[8]
R. Niazadeh, T. Roughgarden, and J. R. Wang, Optimal algorithms for continuous non-monotone submodular and DR-submodular maximization, arXiv preprint arXiv: 1805.09480, 2018.
[9]
N. Buchbinder and M. Feldman, Deterministic algorithms for submodular maximization problems, in Proc. 27 th Annual ACM-SIAM Symp. on Discrete Algorithms, Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, 2016.
Crossref
[10]

N. Buchbinder, M. Feldman, J. Seffi, and R. Schwartz, A tight linear time (1/2)-approximation for unconstrained submodular maximization, SIAM J. Comput., vol. 44, no. 5, pp. 1384–1402, 2015.
Crossref Google Scholar
[11]
C. Durr, N. K. Thang, A. Srivastav, and L. Tible, Non-monotone DR-submodular maximization: Approximation and regret guarantees, arXiv preprint arXiv: 1905.09595, 2019.
Crossref
[12]
L. Chen, H. Hassani, and A. Karbasi, Online continuous submodular maximization, Proc. 21 st Int. Conf. Artificial Intelligence and Statistics, Lanzarote, Spain, 2018.
[13]
D. L. Du, Lyapunov function approach for approximation algorithm design and analysis: with applications in submodular maximization, arXiv preprint arXiv: 2205.12442, 2022.
[14]

N. K. Thắng and A. Srivastav, Online non-monotone DR-submodular maximization, in Proc. AAAI Conf. Artif. Intell. , vol. 35, no. 11, pp. 9868–9876, 2021.
Crossref Google Scholar
[15]
J. Feng, R. Yang, H. Zhang, and Z. Zhang, Online non-monotone DR-submodular maximization: 1/4 approximation ratio and sublinear regret, in Lecture Notes in Computer Science, Y. Zhang, D. Miao, and R. Möhring, eds. New York, NY, USA: Springer, 2022, pp. 118–125.
Crossref
[16]
P. S. Raut, O. Sadeghi, and M. Fazel, Online DR-submodular maximization with stochastic cumulative constraints, arXiv preprint arXiv: 2005.14708, 2020.
[17]
J. Feng, R. Yang, Y. Zhang, and Z. Zhang, Online weakly DR-submodular optimization with Stochastic long-term constraints, in Theory and Applications of Models of Computation, D. Z. Du, D. Du, C. Wu, and D. Xu, eds. New York, NY, USA: Springer, 2022, pp. 32–42.
Crossref
[18]
O. Sadeghi and M. Fazel, Online continuous DR-submodular maximization with long-term budget constraints, in Proc. 23 th Int. Conf. Artificial Intelligence and Statistics, Palermo, Italy, 2020, vol. 108, pp. 4410-4419.
[19]
R. Jenatton, J. Huang, D. Csiba, and C. Archambeau, Online optimization and regret guarantees for non-additive long-term constraints, arXiv preprint arXiv: 1602.05394, 2016.
Tsinghua Science and Technology
Volume 29 Issue 6,
December 2024
Pages 1667-1673
DOI: 10.26599/TST.2023.9010039
Cite this article:
Feng J, Yang R, Zhang Y, et al. Online Weakly DR-Submodular Optimization Under Stochastic Cumulative Constraints. Tsinghua Science and Technology, 2024, 29(6): 1667-1673. https://doi.org/10.26599/TST.2023.9010039

252

Views

50

Downloads

0

Crossref

0

Web of Science

0

Scopus

0

CSCD

Altmetrics
Received: 01 February 2023
Revised: 18 April 2023
Accepted: 05 May 2023
Published: 12 February 2024
© The Author(s) 2024.

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).
Return