GIST: Greedy Independent Set Thresholding for Diverse Data Summarization

• URL: http://arxiv.org/abs/2405.18754v2
• Date: Mon, 10 Feb 2025 21:17:29 GMT
• Title: GIST: Greedy Independent Set Thresholding for Diverse Data Summarization
• Authors: Matthew Fahrbach, Srikumar Ramalingam, Morteza Zadimoghaddam, Sara Ahmadian, Gui Citovsky, Giulia DeSalvo,
• Abstract summary: We introduce a novel subset selection problem called min-distance diversification with monotone submodular utility ($textsfMDMS$) Given a set of points in a metric space, the goal of $textsfMDMS$ is to maximize an objective function combining a monotone submodular utility term and a min-distance diversity term between any pair of selected points.
• Score: 21.69260104523751
• License:
• Abstract: We introduce a novel subset selection problem called min-distance diversification with monotone submodular utility ($\textsf{MDMS}$), which has a wide variety of applications in machine learning, e.g., data sampling and feature selection. Given a set of points in a metric space, the goal of $\textsf{MDMS}$ is to maximize an objective function combining a monotone submodular utility term and a min-distance diversity term between any pair of selected points, subject to a cardinality constraint. We propose the $\texttt{GIST}$ algorithm, which achieves a $\frac{1}{2}$-approximation guarantee for $\textsf{MDMS}$ by approximating a series of maximum independent set problems with a bicriteria greedy algorithm. We also prove that it is NP-hard to approximate to within a factor of $0.5584$. Finally, we demonstrate that $\texttt{GIST}$ outperforms existing benchmarks for on a real-world image classification task that studies single-shot subset selection for ImageNet.

Related papers

• Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
  We present a $textbfMA-OSMA$ algorithm to transfer the discrete submodular problem into a continuous optimization. We also introduce a projection-free $textbfMA-OSEA$ algorithm, which effectively utilizes the KL divergence by mixing a uniform distribution. Our algorithms significantly improve the $(frac11+c)$-approximation provided by the state-of-the-art OSG algorithm.
  arXiv  Detail & Related papers  (2025-02-07T15:57:56Z)
• Fair Submodular Cover [18.37610521373708]
  We present the study of Fair Submodular Cover (FSC), where given a ground set $U$, a monotone submodular function $f:2UtomathbbR_ge 0$, a threshold $tau$. We first introduce discrete algorithms for FSC that achieve a bicriteria approximation ratio of $(frac1epsilon, 1-O(epsilon))$. We then present a continuous algorithm that achieves a $(frac1epsilon, 1-O(epsilon))$-
  arXiv  Detail & Related papers  (2024-07-05T18:37:09Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  We propose a novelgreedy bandit (SGB) algorithm for multi-armed bandit problems when no extra information other than the joint reward of the selected set of $n$ arms at each time $tin [T]$ is observed. SGB adopts an optimized-explore-then-commit approach and is specifically designed for scenarios with a large set of base arms.
  arXiv  Detail & Related papers  (2023-12-13T11:08:25Z)
• Max-Min Diversification with Fairness Constraints: Exact and Approximation Algorithms [17.57585822765145]
  We propose an exact algorithm that is suitable for small datasets as well as a $frac1-varepsilon integer integer5$-approximation algorithm for any $varepsilon in (0, 1)$ that scales to large datasets. Experiments on real-world datasets demonstrate the superior performance of our proposed algorithms over existing ones.
  arXiv  Detail & Related papers  (2023-01-05T13:02:35Z)
• 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)
• Streaming Algorithms for Diversity Maximization with Fairness Constraints [4.53279507109072]
  A streaming algorithm should process $X$ sequentially in one pass and a return subset with maximum emph orders while guaranteeing the fairness constraint. Since diversity is NP-hard in general, we propose two algorithms for fair diversity in data streams. Experimental results show that both algorithms provide solutions of comparable quality to the state-of-the-art algorithms.
  arXiv  Detail & Related papers  (2022-07-30T11:47:31Z)
• Minimax Optimal Algorithms with Fixed-$k$-Nearest Neighbors [13.231906521852718]
  We consider a distributed learning scenario in which a massive dataset is split into smaller groups. We propose emphoptimal rules to aggregate the fixed-$k$-NN information for classification, regression, and density estimation. We show that the distributed algorithm with a fixed $k$ over a sufficiently large number of groups attains a minimax optimal error rate up to a multiplicative logarithmic factor.
  arXiv  Detail & Related papers  (2022-02-05T01:59:09Z)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  The fuzzy or soft objective is a popular generalization of the well-known $k$-means problem. We show that by making few queries, the problem becomes easier to solve.
  arXiv  Detail & Related papers  (2021-06-04T02:32:26Z)
• 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)
• Sampling from a $k$-DPP without looking at all items [58.30573872035083]
  Given a kernel function and a subset size $k$, our goal is to sample $k$ out of $n$ items with probability proportional to the determinant of the kernel matrix induced by the subset (a.k.a. $k$-DPP) Existing $k$-DPP sampling algorithms require an expensive preprocessing step which involves multiple passes over all $n$ items, making it infeasible for large datasets. We develop an algorithm which adaptively builds a sufficiently large uniform sample of data that is then used to efficiently generate a smaller set of $k$ items.
  arXiv  Detail & Related papers  (2020-06-30T16:40:44Z)

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.