Lian, Yuefang, Wang, Xiao, Xu, Dachuan, and Zhao, Zhongrui (2024) Zeroth-order Stochastic Approximation Algorithms for DR-submodular Optimization. Journal of Machine Learning Research, 25. pp. 1-55.

Preview

PDF (Published Version) - Published Version Available under License Creative Commons Attribution. Download (823kB) | Preview

Abstract

In this paper, we study approximation algorithms for several classes of DR-submodular optimization problems, where DR is short for diminishing return. Following a newly introduced algorithm framework for zeroth-order stochastic approximation methods, we first propose algorithms {\bf CG-ZOSA} and {\bf RG-ZOSA} for smooth DR-submodular optimization based on the coordinate-wise gradient estimator and the randomized gradient estimator, respectively. Our theoretical analysis proves that \rm{\bf{CG-ZOSA}} can reach a solution whose expected objective value exceeds (1−e−1−ϵ2)OPT−ϵ after O(ϵ−2) iterations and O(N2/3dϵ−2) oracle calls, where d represents the problem dimension. On the other hand, \rm{\bf{RG-ZOSA}} improves the approximation ratio to (1−e−1−ϵ2/d) while maintaining the same overall oracle complexity. For non-smooth up-concave maximization problems, we propose a novel auxiliary function based on a smoothed objective function and introduce the \rm{\bf{NZOSA}} algorithm. This algorithm achieves an approximation ratio of (1−e−1−ϵlnϵ−1−ϵ2lnϵ−1) with O(dϵ−2) iterations and O(N2/3d3/2ϵ−3) oracle calls. We also extend \rm{\bf{NZOSA}} to handle a class of robust DR-submodular maximization problems. To validate the effectiveness of our proposed algorithms, we conduct experiments on both synthetic and real-world problems. The results demonstrate the superior performance and efficiency of our methods in solving DR-submodular optimization problems.

Actions (Repository Staff Only)

Item Control Page