Dynamic Algorithms for Matroid Submodular Maximization
- URL: http://arxiv.org/abs/2306.00959v2
- Date: Tue, 26 Dec 2023 12:30:52 GMT
- Title: Dynamic Algorithms for Matroid Submodular Maximization
- Authors: Kiarash Banihashem, Leyla Biabani, Samira Goudarzi, MohammadTaghi
Hajiaghayi, Peyman Jabbarzade, Morteza Monemizadeh
- Abstract summary: 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
- Score: 11.354502646593607
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Submodular maximization under matroid and cardinality constraints are
classical problems with a wide range of applications in machine learning,
auction theory, and combinatorial optimization. In this paper, we consider
these problems in the dynamic setting, where (1) we have oracle access to a
monotone submodular function $f: 2^{V} \rightarrow \mathbb{R}^+$ and (2) we are
given a sequence $\mathcal{S}$ of insertions and deletions of elements of an
underlying ground set $V$.
We develop the first fully dynamic $(4+\epsilon)$-approximation algorithm for
the submodular maximization problem under the matroid constraint using an
expected worst-case $O(k\log(k)\log^3{(k/\epsilon)})$ query complexity where $0
< \epsilon \le 1$. This resolves an open problem of Chen and Peng (STOC'22) and
Lattanzi et al. (NeurIPS'20).
As a byproduct, for the submodular maximization under the cardinality
constraint $k$, we propose a parameterized (by the cardinality constraint $k$)
dynamic algorithm that maintains a $(2+\epsilon)$-approximate solution of the
sequence $\mathcal{S}$ at any time $t$ using an expected worst-case query
complexity $O(k\epsilon^{-1}\log^2(k))$. This is the first dynamic algorithm
for the problem that has a query complexity independent of the size of ground
set $V$.
Related papers
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$.
As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
arXiv Detail & Related papers (2024-10-26T06:21:42Z) - A Dynamic Algorithm for Weighted Submodular Cover Problem [11.354502646593607]
We study the submodular cover problem in dynamic setting where elements of the ground set are inserted and deleted.
We propose a randomized algorithm that, in expectation, obtains a $(epsilon), O(epsilon-1)$-bicriteria approximation using polylogarithmic query complexity per update.
arXiv Detail & Related papers (2024-07-13T21:00:41Z) - 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 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) - Fast algorithms for k-submodular maximization subject to a matroid
constraint [10.270420338235237]
We apply a Threshold-Decreasing Algorithm to maximize $k$-submodular functions under a matroid constraint.
We give a $(frac12 - epsilon)$-approximation algorithm for $k$-submodular function.
arXiv Detail & Related papers (2023-07-26T07:08:03Z) - Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
We consider the problem of minimizing the number of matrix-vector queries needed for accurate trace estimation in the dynamic setting where our underlying matrix is changing slowly.
We provide a novel binary tree summation procedure that simultaneously estimates all $m$ traces up to $epsilon$ error with $delta$ failure probability.
Our lower bounds (1) give the first tight bounds for Hutchinson's estimator in the matrix-vector product model with Frobenius norm error even in the static setting, and (2) are the first unconditional lower bounds for dynamic trace estimation.
arXiv Detail & Related papers (2022-09-30T04:15:44Z) - The First Optimal Acceleration of High-Order Methods in Smooth Convex
Optimization [88.91190483500932]
We study the fundamental open question of finding the optimal high-order algorithm for solving smooth convex minimization problems.
The reason for this is that these algorithms require performing a complex binary procedure, which makes them neither optimal nor practical.
We fix this fundamental issue by providing the first algorithm with $mathcalOleft(epsilon-2/(p+1)right) $pth order oracle complexity.
arXiv Detail & Related papers (2022-05-19T16:04:40Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
We give a sketching-based iterative algorithm that computes $1+varepsilon$ approximate solutions for the ridge regression problem.
We also show that this algorithm can be used to give faster algorithms for kernel ridge regression.
arXiv Detail & Related papers (2022-04-13T22:18:47Z) - 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) - 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.