A General Framework for Dynamic Consistent Submodular Maximization

• URL: http://arxiv.org/abs/2606.04946v1
• Date: Wed, 03 Jun 2026 14:35:13 GMT
• Title: A General Framework for Dynamic Consistent Submodular Maximization
• Abstract summary: Consistency is an important property in dynamic submodular algorithms.<n>We develop a general framework for designing algorithms for this setting.<n>For cardinality constraints, we propose a $frac 12 - O(varepsilon)$ approximation that is $Oleft(frac1varepsilon2right)$ consistent.<n>For rank-$k$ matroid constraints, we construct a $frac 14 - O(varepsilon)$ approximation to the dynamic optimum that is $Oleft(fraclog kvarepsilon2right)
• Score: 29.25075734513064
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Consistency is an important property in dynamic submodular maximization and entails maintaining a near-optimal solution at all times, making only a small number of adjustments to the solution in each step. Prior work has explored this question for the insertion-only case, where the algorithm faces a stream of $n$ insertions, and has established lower and upper bounds for the cardinality-constrained version of the problem. We consider this question in the fully dynamic setting, where the stream of operations may contain both insertions and deletions. We develop a general framework for designing algorithms for this setting, and instantiate it to obtain the first constant-factor approximations with sublinear consistency. For cardinality constraints, we propose a $\frac 12 - O(\varepsilon)$ approximation that is $O\left(\frac{1}{\varepsilon^2}\right)$ consistent. For rank-$k$ matroid constraints, we construct a $\frac 14 - O(\varepsilon)$ approximation to the dynamic optimum that is $O\left(\frac{\log k}{\varepsilon^2}\right)$ consistent.

Related papers

• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  We study tradeoff between solution quality and stability when elements arrive over time.<n>Our algorithm has a future implementation for rational oracle$ with $O(varepsilon-1)$ recourse and separate the existence of universal-price certificates from their efficient algorithms.
  arXiv  Detail & Related papers  (2026-09-09T10:13:43Z)
• On the Convergence of Single-Timescale Actor-Critic [49.19842488693726]
  We analyze the global convergence of the single-timescale actor-critic (AC) algorithm for the infinite-horizon discounted Decision Processes (MDs) with finite state spaces.<n>We demonstrate that the step sizes for both the actor and critic must decay as ( O(k-Pfrac12) ) with $k$ diverging from the conventional ( O(k-Pfrac12) ) rates commonly used in (non- optimal) Markov framework optimization.
  arXiv  Detail & Related papers  (2024-10-11T14:46:29Z)
• Enhanced Deterministic Approximation Algorithm for Non-monotone Submodular Maximization under Knapsack Constraint with Linear Query Complexity [0.0]
  We improve the approximation factor of the fastest deterministic algorithm from $6+epsilon$ to $5+epsilon$. Our technique is based on optimizing the performance of two components: the threshold greedy subroutine and the building of two disjoint sets as candidate solutions.
  arXiv  Detail & Related papers  (2024-05-20T02:24:58Z)
• 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)
• A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
  In this paper we consider finding an approximate second-order stationary point (SOSP) that minimizes a twice different subject general non conic optimization. In particular, we propose a Newton-CG based-augmentedconjugate method for finding an approximate SOSP.
  arXiv  Detail & Related papers  (2023-01-10T20:43:29Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  We investigate the problem of best identification in discounted linear Markov+Delta Decision in the fixed confidence setting under a generative model. The lower bound as the solution of an intricate non- optimization program can be used as the starting point to devise such algorithms.
  arXiv  Detail & Related papers  (2022-08-11T04:12:50Z)
• The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimization [88.91190483500932]
  In this paper, we revisit the smooth and strongly-strongly-concave minimax optimization problem. Existing state-of-the-art methods do not match lower bound $Omegaleft(sqrtkappa_xkappa_ylog3 (kappa_xkappa_y)logfrac1epsilonright)$. We fix this fundamental issue by providing the first algorithm with $mathcalOleft( sqrtkappa_xkappa_ylog
  arXiv  Detail & Related papers  (2022-05-11T17:33:07Z)
• On the Complexity of Dynamic Submodular Maximization [15.406670088500087]
  We show that any algorithm that maintains a $(0.5+epsilon)$-approximate solution under a cardinality constraint, for any constant $epsilon>0$, must have an amortized query complexity that is $mathitpolynomial$ in $n$. This is in sharp contrast with recent dynamic algorithms of [LMNF+20, Mon20] that achieve $(0.5-epsilon)$-approximation with a $mathsfpolylog(n)$ amortized query complexity.
  arXiv  Detail & Related papers  (2021-11-05T00:04:29Z)
• Beyond Pointwise Submodularity: Non-Monotone Adaptive Submodular Maximization in Linear Time [17.19443570570189]
  We study the non-monotone adaptive submodular problem subject to a cardinality constraint. We show that the adaptive random greedy algorithm achieves a $1/e$ approximation ratio under adaptive submodularity. We propose a faster algorithm that achieves a $1-1/e-epsilon$ approximation ratio in expectation with $O(nepsilon-2log epsilon-1)$ value oracle queries.
  arXiv  Detail & Related papers  (2020-08-11T21:06:52Z)
• Linear-Time Algorithms for Adaptive Submodular Maximization [17.19443570570189]
  First, we develop a well-studied adaptive submodular problem subject to a cardinality constraint. Second, we introduce the concept of fully adaptive submodularity. Our algorithm achieves a $frac1-1/e-epsilon4-2/e-2epsilon$ approximation ratio using only $O(nlogfrac1epsilon)$ number of function evaluations.
  arXiv  Detail & Related papers  (2020-07-08T15:54:28Z)
• Streaming Complexity of SVMs [110.63976030971106]
  We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
  arXiv  Detail & Related papers  (2020-07-07T17:10:00Z)
• Continuous Submodular Maximization: Beyond DR-Submodularity [48.04323002262095]
  We first prove a simple variant of the vanilla coordinate ascent, called Coordinate-Ascent+. We then propose Coordinate-Ascent++, that achieves tight $(1-1/e-varepsilon)$-approximation guarantee while performing the same number of iterations. The computation of each round of Coordinate-Ascent++ can be easily parallelized so that the computational cost per machine scales as $O(n/sqrtvarepsilon+nlog n)$.
  arXiv  Detail & Related papers  (2020-06-21T06:57:59Z)

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.