Fully Dynamic Submodular Maximization over Matroids

• URL: http://arxiv.org/abs/2305.19918v1
• Date: Wed, 31 May 2023 14:55:47 GMT
• Title: Fully Dynamic Submodular Maximization over Matroids
• Abstract summary: maximizing monotone submodular functions under a matroid constraint is a classic algorithmic problem with multiple applications in data mining and machine learning. We study this classic problem in the fully dynamic setting, where elements can be both inserted and deleted in real-time. Our main result is a randomized algorithm that maintains an efficient data structure with an $tildeO(k2)$ amortized update time (in the number of additions and deletions) and yields a $4$-approximate solution, where $k$ is the rank of the matroid.
• Score: 27.83996903538686
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Maximizing monotone submodular functions under a matroid constraint is a classic algorithmic problem with multiple applications in data mining and machine learning. We study this classic problem in the fully dynamic setting, where elements can be both inserted and deleted in real-time. Our main result is a randomized algorithm that maintains an efficient data structure with an $\tilde{O}(k^2)$ amortized update time (in the number of additions and deletions) and yields a $4$-approximate solution, where $k$ is the rank of the matroid.

Related papers

• Online Two-Stage Submodular Maximization [15.29193118676418]
  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.
  arXiv  Detail & Related papers  (2025-10-22T11:18:54Z)
• 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)
• 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)
• Reconstructing $S$-matrix Phases with Machine Learning [49.1574468325115]
  We apply modern machine learning techniques to studying the unitarity constraint. We find a new phase-ambiguous solution which pushes the known limit on such solutions significantly beyond the previous bound.
  arXiv  Detail & Related papers  (2023-08-18T10:29:26Z)
• Dynamic Algorithms for Matroid Submodular Maximization [11.354502646593607]
  Submodular complexity under matroid and cardinality constraints are problems with a wide range of applications in machine learning, auction theory, and optimization. In this paper, we consider these problems in the dynamic setting, where we have access to a monotone submodular function $f: 2V rightarrow mathbbR+$ and we are given a sequence $calmathS$ of insertions and deletions of elements of an underlying ground set $V$. We develop the first fully dynamic algorithm for the submodular problem under the matroid constraint
  arXiv  Detail & Related papers  (2023-06-01T17:54:15Z)
• 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)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  We consider learning in an adversarial Decision Process (MDP) where the loss functions can change arbitrarily over $K$ episodes. This paper provides two algorithms that improve the regret to $tildemathcal O(K2/3)$ in the same setting.
  arXiv  Detail & Related papers  (2023-01-30T14:37:21Z)
• Deletion Robust Submodular Maximization over Matroids [27.83996903538686]
  We study the deletion robust version of the problem under the classic matroids constraint. We present constant-factor approximation algorithms, whose space complexity depends on the rank $k$ of the matroid. We complement our theoretical results with an in-depth experimental analysis showing the effectiveness of our algorithms on real-world datasets.
  arXiv  Detail & Related papers  (2022-01-31T11:15:56Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  We propose a new algorithm for the min-player against smooth algorithms deployed by an adversary. Our algorithm is guaranteed to make monotonic progress having no limit cycles, and to find an appropriate number of gradient ascents.
  arXiv  Detail & Related papers  (2021-06-02T22:03:36Z)
• Solving weakly supervised regression problem using low-rank manifold regularization [77.34726150561087]
  We solve a weakly supervised regression problem. Under "weakly" we understand that for some training points the labels are known, for some unknown, and for others uncertain due to the presence of random noise or other reasons such as lack of resources. In the numerical section, we applied the suggested method to artificial and real datasets using Monte-Carlo modeling.
  arXiv  Detail & Related papers  (2021-04-13T23:21:01Z)
• A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm for Bilevel Optimization [112.59170319105971]
  We propose a new algorithm -- the Momentum- Single-timescale Approximation (MSTSA) -- for tackling problems. MSTSA allows us to control the error in iterations due to inaccurate solution to the lower level subproblem.
  arXiv  Detail & Related papers  (2021-02-15T07:10:33Z)
• Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint [13.357957711519134]
  Constrained submodular problems encompass a variety of applications, including personalized recommendation, team formation, and revenueimation via viral marketing. We present a simple greedy algorithm that achieves a $5.83 randomized approximation and runs in $O(n log n)$ prohibitively time time i.e., at least factor $n$ faster than other state-of-the-art algorithms. There, we obtain a 9-approximation, which is the first constant approximation for non-monotone$ objectives. Experimental evaluation of our algorithms showcases their improved performance on real and synthetic data.
  arXiv  Detail & Related papers  (2020-07-09T18:15:01Z)
• Fast and Private Submodular and $k$-Submodular Functions Maximization with Matroid Constraints [27.070004659301162]
  We study the problem of maximizing monotone submodular functions subject to matroid constraints in the framework of differential privacy. We give the first $frac12$-approximation algorithm that preserves $k$submodular functions subject to matroid constraints.
  arXiv  Detail & Related papers  (2020-06-28T23:18:58Z)

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.