Online Weakly DR-Submodular Optimization Under Stochastic Cumulative Constraints

作     者：Junkai Feng Ruiqi Yang Yapu Zhang Zhenning Zhang 

作者机构：Beijing Institute for Scientific and Engineering ComputingBeijing University of TechnologyBeijing 100124China 

出 版 物：《Tsinghua Science and Technology》 (清华大学学报自然科学版（英文版）)

年 卷 期：2024年第29卷第6期

页      面：1667-1673页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：supported by the National Natural Science Foundation of China(Nos.12101587,12001025,and 12131003) the China Postdoctoral Science Foundation(No.2022M720329) the Postdoctoral Research Foundation of Chaoyang District(Nos.Q1006E11202301 and Q1006E11202302) 

主　　题：online maximization weakly DR-submodular regret stochastic 

摘      要：In this paper,we study a class of online continuous optimization *** 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 *** the two methods,the penalty function and Frank-Wolfe strategies,we present an online method to solve the considered *** 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.