Unified Projection-Free Algorithms for Adversarial DR-Submodular Optimization

Thanks a lot for your time and the great comments. Regarding experiments, we note that the focus of the paper is on the theoretical results. We have provided evaluations on non-convex/non-concave quadratic maximization which has also been used in the prior works. We note that we consider a unified approach for 16 cases in this paper. In 9 of these cases, ours is the first algorithm, and thus there are no baselines to compare. Furthermore, one would need to find different real world examples for different settings, since each real-world example often matches the assumption of only a few of the 16 cases. While practically important, we chose a case where the assumptions are satisfied to demonstrate the benefits of our approach and where we had relevant baselines to perform the comparison. Thus, we leave this comparison to the experts in different domains (e.g., profit maximization in social networks, advertising, experimental design, resource allocation, mean-field inference in probabilistic models, MAP inference in determinantal point processes, etc) where such algorithms could be used in realistic setups. Regarding the text-wrapping layout, that is indeed due to the space constraint. We have followed your advice and have used the algorithm2e package in the revision to enhance readability.

Thank you for your time in reviewing our paper. **Q1**: As we mentioned in the introduction and elaborated on in Sections 3.1-3.2 and Appendix A.2, our main technical novelties include: **(i)** a novel combination of the idea of meta-actions and random permutations to obtain a new algorithm in the full-information setting; **(ii)** handling stochastic (gradient/value) feedback *without* using variance reduction techniques like momentum, which in turn leads to state of the art regret bounds; and **(iii)** a unified approach that specializes to multiple scenarios considered in this paper. (In our submission, we described novelties (ii) and (iii) together; for clarity, we now describe them separately.) **(i)** Except for the full-information algorithm of (Niazadeh et al., 2021) which uses a completely different approach, all of the referenced algorithms in prior works designed for the full-information setting with $T^\beta > 1$ gradient samples available for each function $F_t$ used meta-actions, specifically with $K=T^\beta$ online linear optimization (OLO) oracles. So the number of oracles $K$ used was set equal to the number of samples $T^\beta$ available as feedback. We prove that using $K = T^\beta$ OLO oracles is sub-optimal. We do so by designing and analyzing the first random permutations plus meta-action based procedure for this setting. Using random permutations, we add a degree of freedom where we can choose the number $K$ of OLO oracles separately from the number of queries $T^\beta$. This results in significant improvements in regret bounds. For example, in the limit of the number of gradient queries per function $T^\beta$ tending to one, for monotone functions over convex sets containing the origin (Meta-Frank-Wolfe in (Chen et al., 2018a)) and for non-monotone functions over downward closed sets (Meta-MFW in (Zhang et al., 2023)), our novel approach using random permutations results in an improvement of $O(T^{1/5})$. (Note that this is the improvement due solely from combining random permutations with meta-actions, without considering the effect of removing momentum, which also reduces regret and which we will describe in detail below. In the aforementioned settings, when the number of gradient queries per function $T^\beta$ is more than one, our final result improves the state of the art by a factor of $O(T^{1/3})$.) Intuitively, our approach harmonizes "Meta" algorithms (designed for $T^\beta > 1$ gradient samples per function $F_t$) with "Mono" algorithms (designed for a single, $T^\beta = 1$, gradient sample per function $F_t$), which have never been combined before. We strove for our methods to be as simple as possible---the simplicity in combining these ideas is only evident in hindsight and is not evident from the prior works, despite the regret bounds for Meta-algorithms as $T^\beta\to 1$ being clearly sub-optimal. Even in the most recent work with both types of algorithms, (Zhang et al., 2023), separate Meta and Mono algorithms were proposed and they were also analyzed separately, despite a regret bound gap for $\beta=0$ (see Figure 1 in our paper with $\beta=0$ for a visual depiction of (Zhang et al., 2023)'s Meta-MFW algorithm's regret bound gap compared to that of their Mono-MFW algorithm). In regards to **(ii)**, one of our main technical novelties is to handle stochastic feedback without relying on variance reduction techniques. In particular, not only do we show for all cases that noisy feedback (gradients/values) can be handled without momentum, but more so for a fixed number of queries (fixed $T^\beta$), using momentum leads to higher regret. Almost all previous Frank-Wolfe type algorithms in online DR-submodular maximization that handle stochastic feedback employ some form of momentum (a common variance reduction method). We believe this was largely due to a misinterpretation of the counter-example described in (Hassani et al., 2017) where they show that in the offline setting, directly replacing the exact gradient with an unbiased estimator of the gradient could result in arbitrarily bad outputs of the algorithm. This is mentioned in Section 3.2 of (Chen et al., 2018b) as the reason why their version of Meta-Frank-Wolfe may not be used with a stochastic gradient and is later solved in (Chen et al., 2018a) by using momentum which results in considerable loss in performance. The version of Meta-Frank-Wolfe described in (Mualem et al., 2023), for non-monotone functions over general convex, works with stochastic gradient oracles without using momentum, which partially inspired this technical novelty of our work. However, we note that their work focused only on regret bounds, not query complexity, and if query complexity is ignored it does not matter whether momentum is used-- $O(T^{1/2})$ can be achieved.

(The fact that their algorithm obtains $O(T^{1-\beta})$ regret for $T^{\beta}$ queries per function follows from the first part of Theorem 4.1 together with the last sentence of Section 4 and the first paragraph of the proof Theorem 3.1 in their paper.) While they state their algorithm and proof for an arbitrary number of queries per function, they have no analysis or discussion on query complexity, nor on the possibility of extending that approach to other settings. To the best of our knowledge, our paper is the first to realize that removing momentum could result in improved regret bound for a fixed query complexity. We prove that for online DR-submodular optimization, in all cases, even when the feedback is stochastic, using meta-actions alone (i.e., without momentum) is *sufficient* to obtain sublinear $\alpha$-regret bounds and using momentum decreases the performance. We extend this analysis to Mono-Frank-Wolfe, where we improve the state of the art by $O(T^{2/15})$. If the idea of random permutations is used as we have described in (i), together with momentum, the regret will likely be bounded from above by $O(T^{4/5 - \beta/5})$. By removing momentum, we achieve $O(T^{2/3 - \beta/3})$ regret, i.e. a likely improvement of $O(T^{2(1 - \beta)/15})$ over the result one would obtain by using (i) with momentum. For **(iii)**, we note that many papers and results add more complexity to the field of research, but our result tries to move in the opposite direction. Algorithm 1 (for full-information feedback) generalizes, simplifies and improves 8 previous algorithms, while Algorithm 2 (for semi-bandit feedback) does this for 3 previous algorithms. We developed a unified analysis which is more modular and simpler than analyses in prior works. This modularity allows us to *(a)* obtain better insight for how elements of the algorithm design and problem setting interact in bringing about the $\alpha$ approximation ratio separately from the $\alpha$-regret bounds; and as consequence, results in *(b)* proof for regret guarantees for 16 algorithms in shorter space than other papers proved regret guarantees for just one or two algorithms. Regarding *(iii).(a)* on how the modularity of the analysis yields clearer insight, in Appendix E we show an essential lemma (Lemma 8) that makes explicit why the update rules and the step sizes should be the way they are. Lemma 8 only considers a single DR-submodular function and captures how certain update rules result in certain approximation coefficients. In fact, besides the two algorithms in this paper, Lemma 8 may be directly used in the proof of at least 18 algorithms in the literature as the part of the proof which derives the approximation coefficients: (Chen et al., 2018b) (Chen et al., 2018a) (Zhang et al., 2019) (Niazadeh et al., 2021) (Thang et al., 2021) (Zhang et al., 2023) (Mualem et al., 2023) (Bian et al., 2017b) (Mokhtari et al,. 2020) (Bian et al., 2017a) (Du et al., 2022) (Pedramfar et al., 2023) Regarding *(iii).(b)*, as an example of how much the modularity of our analysis leads to brevity, in the paper (Zhang et al., 2019), where the idea of random permutations is first used for DR-submodular maximization with full-information single sample gradient $T^\beta=1$ feedback, the proof of their result for the full-information setting is 8.5 pages (Appendix B in their paper). That proof only covers the (simpler) case of monotone functions over convex sets containing the origin, with a single evaluation of gradient oracle. They use another 9 pages to prove their result for monotone functions over downward closed convex sets in the bandit setting. (We are only considering the proofs that involve the ideas of meta-actions and random permutations, not general statements about convex sets or DR-submodular functions.) In contrast, the only part of our proofs that deals explicitly with the online setting are in Appendix F and G, a total of 4 pages, which, together with Lemma 9, prove the regret bounds for 16 problem variations listed in Table 1. **Q2**: We cannot speak for authors of other papers on why they did not propose a unified framework. Instead, we partly address a related question -- in what way is this work unified and what more work would some authors have needed to do in order to unify their separately described and analyzed algorithms. In general, that would depend on how one defined the notion of "unification". There are several different forms of unification appearing in our work: **(a)** Unification of value/gradient oracle settings: Algorithm 1 is the first algorithm for adversarial DR-submodular maximization with full information feedback given a value oracle. Except for (Chen et al., 2018b) which uses a projection-based method, Algorithm 2 is the first algorithm for adversarial DR-submodular maximization with semi-bandit feedback given a gradient oracle. This is arguably the simplest form of unification present in our work.