DR-Submodular Function Maximization with Adaptive Stepsize

The DR-submodular function maximization problem has been gaining increasing attention due to its important applications in many fields. In [1], a framework was proposed to describe algorithms using differential dynamical systems and discretization to obtain implementable algorithms. In this framework, the time domain is discretized with equal stepsizes, which also determined the computational complexity of the algorithm. In this paper, we propose an adaptive approach to determine the stepsize, which is applicable for various scenarios. With the guarantee of achieving the same approximation ratio as the state-of-art results, the iteration complexity of our stepsize selection strategy is \( O(\frac{\Vert \nabla F(\textbf{0})\Vert _1}{\epsilon }) \) when the objective function is monotone and \(O(n+\frac{\Vert \nabla F(\textbf{0})\Vert _1}{\epsilon } )\) when it is non-monotone, where F denotes the objective function, and \(\epsilon \) represents the approximation loss by discretization process. This strategy has been shown to have lower computational complexity in some of the most common application scenarios for DR-submodular function maximization.