From Linear to Linearizable Optimization: A Novel Framework with Applications to Stationary and Non-stationary DR-submodular Optimization

Thank you for your review.

W1. Our notion of linearizable/quadratizable functions generalizes both DR-submodularity and convexity. There are many applications for DR-submodular maximization. Example applications include experimental design [7], resource allocation [Designing smoothing functions for improved worst-case competitive ratio in online optimization - Eghbali, R. and Fazel, M. (2016)], influence maximization [Maximizing the spread of influence through a social network - Kempe et al., 2003], [Influence estimation and maximization in continuous-time diffusion networks - Gomez-Rodriguez et al., 2016] mean-field inference in probabilistic models [3], and MAP inference in determinantal point processes (DPPs) [Determinantal point processes for machine learning - Kulesza et al., 2012] as well as more recently identified applications like serving heterogeneous learners under networking constraints [Experimental design networks: A paradigm for serving heterogeneous learners under networking constraints - Li et al. 2023] and joint optimization of routing and caching in networks [Jointly optimal routing and caching with bounded link capacities - Li et al., 2023]. We will add a section to the appendix and include some of such applications as discussed in the literature.

W2. Note that our framework is so general that, as corollaries (Specifically Corollaries 7 and 8 and Theorem 8), we obtain 33 (14 + 10 + 9) algorithms covering 41 (12 + 12 + 8 + 9) cases where there is only 1 case where there exists an algorithm in the literature that (both with more assumptions and in a more limited settings) can obtain a better regret bound than our result. (There are also 3 of the results of [35], mentioned in Table 2, which require both more assumptions and also obtain worse sample complexity for $\gamma=1$ than our result, but obtain a better approximation coefficient when $\gamma < 1$.)This makes it a bit difficult to run experiments that cover a meaningful subset of results without adding significantly more to the paper. Given the theoretical focus of this paper, we hope that future application papers related to these 41 cases will evaluate and compare the described algorithm in their works.

W3. There are several types of lower bounds one can consider. Approximation coefficient, time complexity, sample complexity, static regret, dynamic regret and adaptive regret. Approximation coefficients discussed in this work are either proven or conjectured to be optimal. For monotone functions over convex sets containing the origin, given full-information first order feedback, it is known that $T^{1/2}$ is the optimal $(1-1/e)$-regret. In general, as long as the approximation factor $\alpha$ is optimal, we expect $\alpha$-regret of $T^{1/2}$ to be a lower bound. Note that this is the first work the obtains sublinear dynamic regret or adaptive regret over DR-submodular functions. The base algorithms that are used here are known to be optimal in the context of convex optimization. However, proving lower bound would require a more detailed analysis which we will leave to a future work. We will write a discussion on the lower bound based on the above in the final version.

Thank you for your review.

We will expand the explanations for each theorem to make the core ideas more clear. We will also expand section 6 to include more explanations and intuition about the applications in the final version.

Thank you for your review.

We will correct the typos in the final version.

Q1. Currently, there is no result showing linearizability of non-monotone functions over downward closed sets, with a better approximation coefficient/sample complexity than that can be specialized from the results of general convex sets. However, we believe this framework to be general enough to allow for such results. All we needs is to show that such functions are linearizable (i.e., something similar to Lemmas 1, 2, or 3 for non-monotone functions over downward closed convex sets) and almost all of the results that are valid for linearizable functions would follow through even in this case.

Q2. Note that, in the literature, the notion of curvature or gamma-weakly DR-submodular is almost always considered in the context of monotone functions. In fact, we only define curvature for monotone functions in this paper. In order to properly address the question, we would need to formalize and justify appropriate definitions for gamma-weakly non-monotone functions with non-zero curvature and also generalize Lemma 3 so that it would be applied to such functions.

Specifically, for a continuous monotone function $f : \mathcal{K} \to \mathbb{R}$, we define the curvature to be the smallest number $c \in [0, 1]$ such that $f(y + z) - f(y) \geq (1 - c) (f(x + z) - f(x)),$ for all $x, y \in \mathcal{K}$ and $z \geq 0$ such that $x + z, y + z \in \mathcal{K}$. This is already a generalization of what is commonly considered in the literature where the function $f$ is assumed to be differentiable and the curvature is defined as $c := 1 - \inf_{x, y \in \mathcal{K}, 1 \leq i \leq d}\{ \frac{\nabla_i f(y)}{\nabla_i f(x)} \},$ where $\nabla_i$ is the $i$-th component of the gradient vector. Moreover, the definition of curvature and $\gamma$-weakly, in the non-monotone case, should be formulated in a way that would allow for a version of Lemma 3 to work. We leave the extension of this notion for non-monotone functions and proving the variant of Lemma 3 in this case as a future work.