Online Two-Stage Submodular Maximization

• URL: http://arxiv.org/abs/2510.19480v1
• Date: Wed, 22 Oct 2025 11:18:54 GMT
• Title: Online Two-Stage Submodular Maximization
• Authors: Iasonas Nikolaou, Miltiadis Stouras, Stratis Ioannidis, Evimaria Terzi,
• Abstract summary: We introduce the Online Two-Stage Submodular Maximization (O2SSM) problem, in which the submodular objectives are revealed in an online fashion.<n>We empirically validate performance of our online algorithm with experiments on real datasets.
• Score: 15.29193118676418
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Given a collection of monotone submodular functions, the goal of Two-Stage Submodular Maximization (2SSM) [Balkanski et al., 2016] is to restrict the ground set so an objective selected u.a.r. from the collection attains a high maximal value, on average, when optimized over the restricted ground set. We introduce the Online Two-Stage Submodular Maximization (O2SSM) problem, in which the submodular objectives are revealed in an online fashion. We study this problem for weighted threshold potential functions, a large and important subclass of monotone submodular functions that includes influence maximization, data summarization, and facility location, to name a few. We design an algorithm that achieves sublinear $(1 - 1/e)^2$-regret under general matroid constraints and $(1 - 1/e)(1-e^{-k}k^k/k!)$-regret in the case of uniform matroids of rank $k$; the latter also yields a state-of-the-art bound for the (offline) 2SSM problem. We empirically validate the performance of our online algorithm with experiments on real datasets.

Related papers

• Effective Policy Learning for Multi-Agent Online Coordination Beyond Submodular Objectives [64.16056378603875]
  We present two policy learning algorithms for multi-agent online coordination problem.<n>The first one, textttMA-SPL, can achieve the optimal $(fracce)$-approximation for the MA-OC problem.<n>The second online algorithm named textttMA-MPL can simultaneously maintain the same approximation ratio.
  arXiv  Detail & Related papers  (2025-09-26T17:16:34Z)
• Automatic Rank Determination for Low-Rank Adaptation via Submodular Function Maximization [56.78271181959529]
  SubLoRA is a rank determination method for Low-Rank Adaptation (LoRA) based on submodular function.<n>Our method combines solid theoretical foundations, second-order accuracy, and practical computational efficiency.
  arXiv  Detail & Related papers  (2025-07-02T15:56:40Z)
• Corporate Needs You to Find the Difference: Revisiting Submodular and Supermodular Ratio Optimization Problems [3.637365301757111]
  We study the problem of minimizing or maximizing the average value $ f(S)/|S| $ of a submodular or supermodular set function f: 2V to math $ over non-empty subsets $ S subseteq V.<n>This generalizes classical problems such as Densest Subgraph (DSG), Densest Supermodular Set (DSS), and Submodular Minimization (SFM)
  arXiv  Detail & Related papers  (2025-05-23T03:55:11Z)
• Dynamic Non-monotone Submodular Maximization [11.354502646593607]
  We show a reduction from maximizing a non-monotone submodular function under the cardinality constraint $k$ to maximizing a monotone submodular function under the same constraint. Our algorithms maintain an $(epsilon)$-approximate of the solution and use expected amortized $O(epsilon-3k3log3(n)log(k)$ queries per update.
  arXiv  Detail & Related papers  (2023-11-07T03:20:02Z)
• Data Summarization beyond Monotonicity: Non-monotone Two-Stage Submodular Maximization [11.296845424426062]
  The objective of a two-stage submodular problem is to reduce the ground set using provided training functions that are submodular. This problem has applications in various domains including data summarization.
  arXiv  Detail & Related papers  (2023-09-11T01:00:10Z)
• Non-monotone Sequential Submodular Maximization [13.619980548779687]
  We aim to select and rank a group of $k$ items from a ground set $V$ such that the weighted assortment of $k$ is maximized. The results of this research have implications in various fields, including recommendation systems and optimization.
  arXiv  Detail & Related papers  (2023-08-16T19:32:29Z)
• Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedback [98.29086113546045]
  We investigate the problem of unconstrained multi-armed bandits with full-bandit feedback and rewards for submodularity. We show that RGL empirically outperforms other full-bandit variants in submodular and non-submodular settings.
  arXiv  Detail & Related papers  (2023-02-02T18:52:14Z)
• Submodular + Concave [53.208470310734825]
  It has been well established that first order optimization methods can converge to the maximal objective value of concave functions. In this work, we initiate the determinant of the smooth functions convex body $$F(x) = G(x) +C(x)$. This class of functions is an extension of both concave and continuous DR-submodular functions for which no guarantee is known.
  arXiv  Detail & Related papers  (2021-06-09T01:59:55Z)
• The Power of Subsampling in Submodular Maximization [51.629656762796564]
  We show that this approach leads to optimal/state-of-the-art results despite being much simpler than existing methods. We empirically demonstrate the effectiveness of our algorithms on video summarization, location summarization, and movie recommendation tasks.
  arXiv  Detail & Related papers  (2021-04-06T20:25:57Z)
• Continuous Submodular Function Maximization [91.17492610120324]
  Continuous submodularity is a class of functions with a wide spectrum of applications. We identify several applications of continuous submodular optimization, ranging from influence, MAP for inferences to inferences to field field.
  arXiv  Detail & Related papers  (2020-06-24T04:37:31Z)
• Streaming Submodular Maximization under a $k$-Set System Constraint [42.31117997337689]
  We propose a novel framework that converts streaming for monotone submodular into streaming for non-monotone submodular. We also propose the first algorithm for monotone submodular streaming subject to $k$ible $k$-set system constraints.
  arXiv  Detail & Related papers  (2020-02-09T12:32:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.