# From Linear to Linearizable Optimization: A Novel Framework with Applications to Stationary and Non-stationary DR-submodular Optimization arXiv: https://arxiv.org/abs/2405.00065 · HTML: https://mlsanity.com/paper/2405.00065/ ## Key facts - Cited by 9 papers in the map (data through 14 Oct 2026). - Builds on 36 of its 68 references that are in the map. - First posted on arXiv 27 Apr 2024. ## Builds on (most cited first, 30 of 36) - [Non-stationary Stochastic Optimization](https://mlsanity.com/paper/1307.5449/) (2013) - [Adaptive Online Learning in Dynamic Environments](https://mlsanity.com/paper/1810.10815/) (2018) - [Strongly Adaptive Online Learning](https://mlsanity.com/paper/1502.07073/) (2015) - [Dynamic Regret of Convex and Smooth Functions](https://mlsanity.com/paper/2007.03479/) (2020) - [Stochastic Conditional Gradient Methods: From Convex Minimization to Submodular Maximization](https://mlsanity.com/paper/1804.09554/) (2018) - [Bandit Convex Optimization in Non-stationary Environments](https://mlsanity.com/paper/1907.12340/) (2019) - [Faster Projection-free Online Learning](https://mlsanity.com/paper/2001.11568/) (2020) - [Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization](https://mlsanity.com/paper/2102.11050/) (2021) - [Online Continuous Submodular Maximization](https://mlsanity.com/paper/1802.06052/) (2018) - [Gradient Methods for Submodular Maximization](https://mlsanity.com/paper/1708.03949/) (2017) - [Online Continuous Submodular Maximization: From Full-Information to Bandit Feedback](https://mlsanity.com/paper/1910.12424/) (2019) - [Guaranteed Non-convex Optimization: Submodular Maximization over Continuous Domains](https://mlsanity.com/paper/1606.05615/) (2016) - [Projection-Free Online Optimization with Stochastic Gradient: From Convexity to Submodularity](https://mlsanity.com/paper/1802.08183/) (2018) - [Efficient Projection-Free Online Convex Optimization with Membership Oracle](https://mlsanity.com/paper/2111.05818/) (2021) - [New Projection-free Algorithms for Online Convex Optimization with Adaptive Regret Guarantees](https://mlsanity.com/paper/2202.04721/) (2022) - [Continuous DR-submodular Maximization: Structure and Algorithms](https://mlsanity.com/paper/1711.02515/) (2017) - [Stochastic Continuous Submodular Maximization: Boosting via Non-oblivious Function](https://mlsanity.com/paper/2201.00703/) (2022) - [Efficient Projection-Free Online Methods with Stochastic Recursive Gradient](https://mlsanity.com/paper/1910.09396/) (2019) - [Projection-Free Bandit Convex Optimization](https://mlsanity.com/paper/1805.07474/) (2018) - [Improved Regret Bounds for Projection-free Bandit Convex Optimization](https://mlsanity.com/paper/1910.03374/) (2019) - [Resolving the Approximability of Offline and Online Non-monotone DR-Submodular Maximization over General Convex Sets](https://mlsanity.com/paper/2210.05965/) (2022) - [Submodular + Concave](https://mlsanity.com/paper/2106.04769/) (2021) - [Projection-free Adaptive Regret with Membership Oracles](https://mlsanity.com/paper/2211.12638/) (2022) - [Non-stationary Projection-free Online Learning with Dynamic and Adaptive Regret Guarantees](https://mlsanity.com/paper/2305.11726/) (2023) - [Bandit Multi-linear DR-Submodular Maximization and Its Applications on Adversarial Submodular Bandits](https://mlsanity.com/paper/2305.12402/) (2023) - [A Unified Approach for Maximizing Continuous DR-submodular Functions](https://mlsanity.com/paper/2305.16671/) (2023) - [Fast First-Order Methods for Monotone Strongly DR-Submodular Maximization](https://mlsanity.com/paper/2111.07990/) (2021) - [Improved Projection-free Online Continuous Submodular Maximization](https://mlsanity.com/paper/2305.18442/) (2023) - [Profit Maximization in Social Networks and Non-monotone DR-submodular Maximization](https://mlsanity.com/paper/2212.06646/) (2022) - [Boosting Gradient Ascent for Continuous DR-submodular Maximization](https://mlsanity.com/paper/2401.08330/) (2024) ## Built on by (most cited first, 9 of 9) - [Decentralized Projection-free Online Upper-Linearizable Optimization with Applications to DR-Submodular Optimization](https://mlsanity.com/paper/2501.18183/) (2025) - [BAGEL: Adversarially Constrained Online Convex Optimization under Separation Oracle Access](https://mlsanity.com/paper/2502.16744/) (2025) - [Upper-Linearizability of Online Non-Monotone DR-Submodular Maximization over Down-Closed Convex Sets](https://mlsanity.com/paper/2602.20578/) (2026) - [Online Convex Optimization with Dueling Feedback](https://mlsanity.com/paper/2608.15050/) (2026) - [Online Learning for Approximately-Convex Functions with Long-term Adversarial Constraints](https://mlsanity.com/paper/2508.16992/) (2025) - [Improved Approximate Regret for Decentralized Online Continuous Submodular Maximization via Reductions](https://mlsanity.com/paper/2602.09502/) (2026) - [γ-weakly θ-up-concavity: A Unified Framework for Non-Convex Optimization Beyond DR-Submodular and OSS Functions](https://mlsanity.com/paper/2602.13506/) (2026) - [Dec-BFTRL: Squre-Root Regret for Decentralized Online Upper-Linearizable Optimization under Separation Access with Application to Continuous Submodular Maximization](https://mlsanity.com/paper/2608.30271/) (2026) - [Geometry-Dependent Bounds for Online Non-Monotone DR-Submodular Maximization](https://mlsanity.com/paper/2610.00545/) (2026) ## Abstract (arXiv) 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. 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 DR-submodular 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.