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

This paper introduces the notion of upper-linearizable/quadratizable functions, a class that extends concavity and DR-submodularity in various settings, including monotone and non-monotone cases over different types of convex sets. A general meta-algorithm is devised to convert algorithms for linear/quadratic maximization into ones that optimize upper-linearizable/quadratizable functions, offering a unified approach to tackling concave and DR-submodular optimization problems. The paper extends these results to multiple feedback settings, facilitating conversions between semi-bandit/first-order feedback and bandit/zeroth-order feedback, as well as between first/zeroth-order feedback and semi-bandit/bandit feedback. Leveraging this framework, new algorithms are derived using existing results as base algorithms for convex optimization, improving upon state-of-the-art results in various cases. Dynamic and adaptive regret guarantees are obtained for DRsubmodular maximization, marking the first algorithms to achieve such guarantees in these settings. Notably, the paper achieves these advancements with fewer assumptions compared to existing state-of-the-art results, underscoring its broad applicability and theoretical contributions to non-convex optimization. DR-submodular (or more generally, up-concave) optimization with semi-bandit feedback/first order feedback in the respective cases. Then, the meta-algorithms for conversion of first-order/semi-bandit to zeroth-order/bandit are used to get result with zeroth-order/bandit feedback. In the cases where the algorithms are full-information and not (semi-)bandit, we use another meta-algorithm to obtain algorithms in (semi-)bandit feedback setting. In the next application, we use the "Improved Ader" algorithm of (Zhang et al., 2018a) which is a projection based algorithm providing dynamic regret guarantees for the convex optimization. Afterwards, the same approach as above are used to obtain the results in the three scenarios of up-concave optimization with first-order feedback. Technical Novelty: The main technical novelties in this work are as follows. 1. We proposes a novel notion of linearizable/quadratizable functions and extend the metaalgorithm framework of (Pedramfar and Aggarwal, 2024) from convex functions to linearizable/quadratizable functions. This allows us to relates a large class of algorithms and regret guarantees for optimization of linear/quadratic functions to that for linearizable/quadratizable functions. 2. We show that the class of quadratizable function optimization is general, and includes not only concave, but up-concave optimization in several cases. For some of the cases, this proof uses a generalization of the idea of boosting ((Zhang et al., 2022 ((Zhang et al., , 2024)) ) which was proposed for DR-submodular maximization, as mentioned in Corollaries 2 and 3. 3. We design a new meta-algorithm, namely SFTT, that captures the idea of random permutations (sometimes referred to as blocking) as used in several papers such as (Zhang et al., 2019 (Zhang et al., , 2023;; Pedramfar et al., 2024a) . While previous works used this idea in specific settings, our meta-algorithm is applicable in general settings. 4. We note the generality of the above results in this paper. Our results are general in the following three aspects: a) In this work, we improve results for projection-free static regret guarantees for DRsubmodular optimization in all considered cases and obtain the first results for dynamic and adaptive regret. Moreover, these guarantees follow from existing algorithms for the linear optimization, using only the statement of the regret bounds and simple properties of the algorithms. b) We consider 3 classes of DR-submodular functions in this work. However, to extend these results to another function class, all one needs to do is to (i) prove that the function class is quadratizable; and (ii) provide an unbiased estimator of g (as described in Equation 1 ). c) We consider 2 different feedback types in offline setting (first/zero order) and 4 types of feedback in the online setting (first/zero order and full-information/trivial query). Converting results between different cases is obtained through meta-algorithms and guarantees for the meta-algorithms which only relies on high level properties of the base algorithms (See Theorems 5, 7, 6 and 8) Key contributions: The key contributions in this work are summarized as follows.