Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model

• URL: http://arxiv.org/abs/2002.05477v1
• Date: Thu, 13 Feb 2020 12:33:46 GMT
• Title: Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model
• Abstract summary: We present the first lower bound on the approximation ratios for cardinality and matroid constraints that beat $1-frac1e$ in the single-pass streaming model. We show weak-oracle streaming algorithms for cardinality and matroid constraints with approximation ratios $fracK2K-1$ and $frac12$, respectively.
• Score: 22.637004266371545
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Maximizing a monotone submodular function under various constraints is a classical and intensively studied problem. However, in the single-pass streaming model, where the elements arrive one by one and an algorithm can store only a small fraction of input elements, there is much gap in our knowledge, even though several approximation algorithms have been proposed in the literature. In this work, we present the first lower bound on the approximation ratios for cardinality and matroid constraints that beat $1-\frac{1}{e}$ in the single-pass streaming model. Let $n$ be the number of elements in the stream. Then, we prove that any (randomized) streaming algorithm for a cardinality constraint with approximation ratio $\frac{2}{2+\sqrt{2}}+\varepsilon$ requires $\Omega\left(\frac{n}{K^2}\right)$ space for any $\varepsilon>0$, where $K$ is the size limit of the output set. We also prove that any (randomized) streaming algorithm for a (partition) matroid constraint with approximation ratio $\frac{K}{2K-1}+\varepsilon$ requires $\Omega\left(\frac{n}{K}\right)$ space for any $\varepsilon>0$, where $K$ is the rank of the given matroid. In addition, we give streaming algorithms when we only have a weak oracle with which we can only evaluate function values on feasible sets. Specifically, we show weak-oracle streaming algorithms for cardinality and matroid constraints with approximation ratios $\frac{K}{2K-1}$ and $\frac{1}{2}$, respectively, whose space complexity is exponential in $K$ but is independent of $n$. The former one exactly matches the known inapproximability result for a cardinality constraint in the weak oracle model. The latter one almost matches our lower bound of $\frac{K}{2K-1}$ for a matroid constraint, which almost settles the approximation ratio for a matroid constraint that can be obtained by a streaming algorithm whose space complexity is independent of $n$.

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)
• Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids: From Robust Offline Optimization to Full-Bandit Learning [55.29259818039367]
  We study the nonnegative submodular subject to a general matroid when the offline algorithm is given an arbitrary controlled value oracle.<n>Our algorithm retains limiting approximation factors $1/e$ for non-monotone objectives and $1-1/e$ for monotone objectives.<n>As a consequence, the offline-to-online reduction yields single-bandit CMAB algorithms for general matroid-constrained submodular rewards.
  arXiv  Detail & Related papers  (2026-08-12T14:54:15Z)
• Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory [65.64123585249297]
  We prove two lower bounds for the first order complexity of minimizing a $d$-dimensional $1$-Lipschitz convex function over the unit ball with $m$ bits of memory.<n>We first show that any such (possibly randomized) algorithm must make $tilde(fracd2sqrtm)$ oracle queries.<n>For deterministic optimization algorithms, we show that $tilde(mind1.6,fracd8/3m2/3)$ queries are required.
  arXiv  Detail & Related papers  (2026-07-21T00:40:59Z)
• Guessing Efficiently for Constrained Subspace Approximation [49.83981776254246]
  We introduce a general framework for constrained subspace approximation. We show it provides new algorithms for partition-constrained subspace approximation with applications to $k$-means clustering, and projected non-negative matrix factorization.
  arXiv  Detail & Related papers  (2025-04-29T15:56:48Z)
• Discretely Beyond $1/e$: Guided Combinatorial Algorithms for Submodular Maximization [13.86054078646307]
  For constrained, not necessarily monotone submodular, all known approximation algorithms with ratio greater than $1/e$ require continuous ideas. For algorithms, the best known approximation ratios for both size and matroid constraint are obtained by a simple randomized greedy algorithm.
  arXiv  Detail & Related papers  (2024-05-08T16:39:59Z)
• 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)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  We introduce efficient $(1+varepsilon)$-approximation algorithms for the binary matrix factorization (BMF) problem. The goal is to approximate $mathbfA$ as a product of low-rank factors. Our techniques generalize to other common variants of the BMF problem.
  arXiv  Detail & Related papers  (2023-06-02T18:55:27Z)
• 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)
• Deletion Robust Non-Monotone 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. In the streaming setting we provide a $(9.435 + O(varepsilon))$-approximation algorithm with summary size and memory.
  arXiv  Detail & Related papers  (2022-08-16T07:51:58Z)
• 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)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  We study the problem of PAC learning halfspaces on $mathbbRd$ with Massart noise under Gaussian marginals. Our results qualitatively characterize the complexity of learning halfspaces in the Massart model.
  arXiv  Detail & Related papers  (2021-08-19T16:16:48Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  We show that the C$2$UCB algorithm has the optimal regret bound $tildeO(dsqrtkT + dk)$ for the partition matroid constraints. For general constraints, we propose an algorithm that modifies the reward estimates of arms in the C$2$UCB algorithm.
  arXiv  Detail & Related papers  (2021-01-20T04:29:18Z)
• 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)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  Given an MDP with $S$ states, $A$ actions, the discount factor $gamma in (0,1)$, and an approximation threshold $epsilon > 0$, we provide a model-free algorithm to learn an $epsilon$-optimal policy. For small enough $epsilon$, we show an improved algorithm with sample complexity.
  arXiv  Detail & Related papers  (2020-06-06T13:34:41Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  We study the problem of finding a basis $S$ of $M$ such that $det(sum_i in Sv_i v_i v_itop)$ is maximized. This problem appears in a diverse set of areas such as experimental design, fair allocation of goods, network design, and machine learning.
  arXiv  Detail & Related papers  (2020-04-16T19:16:38Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  We exploit the finite noise structure of finite sums to derive a matching $O(n2)$-upper bound under the global oracle model. Following a similar approach, we propose a novel adaptation of SVRG which is both emphcompatible with oracles, and achieves complexity bounds of $tildeO(n2+nsqrtL/mu)log (1/epsilon)$ and $O(nsqrtL/epsilon)$, for $mu>0$ and $mu=0$
  arXiv  Detail & Related papers  (2020-02-09T03:39:46Z)

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.