Online non-monotone diminishing return submodular maximization in the bandit setting

In this paper, we study online diminishing return submodular (DR-submodular for short) maximization in the bandit setting. Our focus is on problems where the reward functions can be non-monotone, and the constraint set is a general convex set. We first present the Single-sampling Non-monotone Frank-Wolfe algorithm. This algorithm only requires a single call to each reward function, and it computes the stochastic gradient to make it suitable for large-scale settings where full gradient information might not be available. We provide an analysis of the approximation ratio and regret bound of the proposed algorithm. We then propose the Bandit Online Non-monotone Frank-Wolfe algorithm to adjust for problems in the bandit setting, where each reward function returns the function value at a single point. We take advantage of smoothing approximations to reward functions to tackle the challenges posed by the bandit setting. Under mild assumptions, our proposed algorithm can reach \(\frac{1}{4} (1- \min _{x\in {\mathcal {P}}'}\Vert x\Vert _\infty )\)-approximation with regret bounded by \(O (T^{\frac{5 \min \{1, \gamma \}+5 }{6 \min \{1, \gamma \}+5}})\), where the positive parameter \(\gamma \) is related to the “safety domain” \({\mathcal {P}}'\). To the best of our knowledge, this is the first work to address online non-monotone DR-submodular maximization over a general convex set in the bandit setting.

This research has no associated data.

1. The set \({\mathcal {P}}'\) is a \(\delta \)-interior of \({\mathcal {P}}\) if it holds for every \(x\in {\mathcal {P}}'\) that \(B(x,\delta )\subseteq {\mathcal {P}}\).

Authors and Affiliations

1. Beijing Institute for Scientific and Engineering Computing, Beijing University of Technology, Beijing, 100124, China

   Jiachen Ju & Dachuan Xu

2. Peng Cheng Laboratory, Shenzhen, 518066, China

   Jiachen Ju & Xiao Wang

Corresponding author

Correspondence to Xiao Wang.

Statements & Declarations

This research was partially supported by the National Natural Science Foundation of China (Nos. 12131003, 12271278), the Major Key Project of PCL (No. PCL2022A05) and the Talent Program of Guangdong Province (No. 2021QN02X160). The authors have no relevant financial or non-financial interests to disclose.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendix A: Proof of Lemma 3.5

Proof

It follows from the setting of \(d_q^k\) in Step 14 of Algorithm 1 that

for any \(q\in [Q]\) and \(k =2,~3,~\ldots , K.\) For brevity, denote \(A_q^k:= \nabla \bar{F}_{q, k-1}(x_q^{k})-{\tilde{\nabla }} F_{t_{q, k}}(x_q^{k})\), \(B_q^k:= \nabla \bar{F}_{q, k-1}(x_q^{k}) -\nabla \bar{F}_{q, k-2}(x_q^{k-1}) \), then

Let us focus on the terms in R.H.S. of above equality separately. Recall that \({\mathcal {F}}_{q,k}= \sigma (t_{q,1},\ldots , t_{q,k})\).

For the first term \( \textbf{E} \left[ \left\| A_q^k \right\| ^2\right] \), it can be expressed as

Due to (7), the first term in \( \textbf{E} \left[ \left\| A_q^k \right\| ^2\right] \) is upper bounded by

Following Assumption 3.1, the second term in \( \textbf{E} \left[ \left\| A_q^k \right\| ^2\right] \) is upper bounded by

For the third term in \( \textbf{E} \left[ \left\| A_q^k \right\| ^2\right] \), it follows from the definition of \(\bar{F}_{q,k-1} \) and Assumption 3.1 that

Therefore, we obtain

Secondly, we consider \( \textbf{E}\left[ \left\| B_q^{k} \right\| ^2 \right] \). Note that

where the second inequality is due to the fact that

Then from Young’s Inequality, it implies

Thirdly, for \(\textbf{E}\left[ \langle A_q^k, \Delta _q^{k-1} \rangle \right] \), we obtain from (7) and Assumption 3.1 that

Similarly, we have \( \textbf{E}\left[ \langle A_q^k, B_q^{k} \rangle \right] =0\) which together with (A1)-(A3) yields

Hence, we derive (15).

For the case \(1 \le k \le \frac{K}{2}+1\), it holds from the setting of \(\rho ^k \) in (16) that

where the second inequality is due to

We shall prove by induction that \(\textbf{E}\left[ \Vert \Delta _q^{k}\Vert ^2\right] \le \frac{N_1}{(k+4)^{2 / 3}}\) for \(1 \le k \le \frac{K}{2}+1\). We start with \(k=1\). Note that it follows from Assumption 3.1 and \(\rho ^1\le 1 \) that

Suppose that the argument is valid for \(k-1\). Then we have

where the last inequality is due to

Let us now move to the other case \(\frac{K}{2}+2 \le k \le K\). Observe that \(\rho ^k=\frac{1.5}{(K-k+2)^{2 / 3}}\), and \( \rho ^k \le \frac{1.5}{2^{2/3}} \le 1\). Then we obtain

We shall prove by induction that \(\textbf{E}\left[ \Vert \Delta _q^{k}\Vert \right] \le \frac{N_3}{(K-k+1)^{2 / 3}}\) for \(\frac{K}{2}+1 \le k \le K\). When \(k=\frac{K}{2}+1\), based on previous results, it holds that

Suppose that the statement is valid for \(k-1\), where \(\frac{K}{2}+1 \le k-1 \le K\). Then we can derive

where the third inequality holds because

The proof is completed. \(\square \)

Appendix B: Proof of Lemma 4.2

Proof

Since \({\tilde{F}}_{q,k-1}\) is nonnegative, \(L_1\)-smooth and DR-submodular, it follows from (2), (3) and (20) that

for any \(q\in [Q]\), \(k\in [K+1]\). Then it derives from Step 5 of Algorithm 2, the definition of \( {\textrm{d}({\mathcal {P}})}\), (B5), the setting of \(a^{k}\), and Young’s Inequality that

for any \(q\in [Q]\), \(k\in [K]\). \(\square \)

Appendix C: Proof of Lemma 4.4

Proof

Following from \( x_q^1:=z\), \(x_q^{K+1}:=x_q\), \(a^{K+1}=4\) and \(a^1=1\), taking total expectation on both sides of (23), applying Lemma 4.1 (i), and summing up this inequality over all \(k\in [K]\) yields

In consideration of \({\tilde{F}}_{q }(z)\ge 0,\) we sum the inequality over q from 1 to Q, then obtain

Since \(x_{\delta }^*\in {\mathcal {P}}' \), we can apply Lemma 4.3 to yield

Therefore, by \({a^k}\le 4\), we deduce

It indicates (24) from (22), the definition of \(\tilde{F}_{q }\) in (19), and \(T=QL\). \(\square \)

Appendix D: Proof of Lemma 4.5

Proof

Note that from the setting of \(d_q^k\) in Step 18 of Algorithm 2,

for any \(q\in [Q]\) and \(k=2,\ldots ,K.\) For convenience, we denote \(C_q^k:= \nabla {\tilde{F}}_{q, k-1}(x_q^{k})-g_q^{k}\), \(D_q^k:= \nabla {\tilde{F}}_{q, k-1}(x_q^{k}) -\nabla {\tilde{F}}_{q, k-2}(x_q^{k-1}) \). Then we express \([ \Vert \Lambda _q^{k}\Vert ^2 ]\) as

Next we handle these terms respectively. For the first term of (D6), it holds from Lemma 4.1 (ii) and \(L_0\)-Lipschitz continuity of \( \hat{F_t}\) that

where we use the fact that \( 2 \textbf{E} [ \langle \nabla {\tilde{F}}_{q, k-1}(x_q^{k}) -\nabla \hat{F}_{t_{q, k}}(x_q^{k}), \nabla \hat{F}_{t_{q, k}}(x_q^{k}) -g_q^{k} \rangle ]=0 \) by Remark 4.2. For the third term of (D6), it follows from \(L_0\)-Lipschitz continuity and \(L_1\)-smoothness of \(\hat{F}_t\) that

where the second inequality is due to \(L\ge 2K\) and

For the fourth term and the fifth term of (D6), in the light of the definition of \(\tilde{F}_{q,k-1} \) and Lemma 4.1 (iii), we can mimic the proof of (A4) and derive

For the sixth term of (D6), it yields from Young’s Inequality that

Above all, (D7)-(D10) jointly guarantee

where we use the fact that \(\left( 1-\rho ^k\right) ^2 (1+\frac{2}{ \rho ^k })\le \frac{2}{\rho ^k}-2 \) and \(\left( 1-\rho ^k\right) ^2 (1+\frac{\rho ^k}{ 2 })\le 1-\rho ^k \).

If \( \rho ^k=\,\frac{2}{(k+2)^{2/3}}\), then \( \rho ^k \le \frac{2}{ 2.08 } \le 1 \). When \(k\ge 2\), it follows from (25) that

Next we prove (26) by induction on k. When \(k=1\), it follows from \(L_0\)-Lipschitz continuity of \(F_t \) and the definition of \(\bar{\sigma }\) in Lemma 4.5 that

We now assume \( \textbf{E}\left[ \Vert \Lambda _q^{k-1}\Vert ^2\right] \le \frac{N_4}{(k+2)^{2 / 3}}. \) Then we can obtain from (D11) and

that

\(\square \)

Appendix E: Proof of Theorem 4.1

Proof

By Lemma 4.2 with \( \beta ^{k} = \frac{1}{\delta (k+3)^{1 / 3} }\), for the fourth term of the R.H.S. of (24), it yields from Lemma 4.5 that

For the third term of the R.H.S. of (24), we have

Hence, it implies

which by the parameter settings derives the conclusion. \(\square \)

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions