ProtoBandit: Efficient Prototype Selection via Multi-Armed Bandits
- URL: http://arxiv.org/abs/2210.01860v4
- Date: Wed, 23 Aug 2023 15:22:04 GMT
- Title: ProtoBandit: Efficient Prototype Selection via Multi-Armed Bandits
- Authors: Arghya Roy Chaudhuri, Pratik Jawanpuria, and Bamdev Mishra
- Abstract summary: ProtoBandit is a multi-armed bandit-based framework for identifying a compact set of informative data instances from a source dataset.
Our algorithm reduces the number of similarity computation calls by several orders of magnitudes ($100-1000 times) while obtaining solutions similar in quality to those from state-of-the-art approaches.
- Score: 9.333087475006003
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this work, we propose a multi-armed bandit-based framework for identifying
a compact set of informative data instances (i.e., the prototypes) from a
source dataset $S$ that best represents a given target set $T$. Prototypical
examples of a given dataset offer interpretable insights into the underlying
data distribution and assist in example-based reasoning, thereby influencing
every sphere of human decision-making. Current state-of-the-art prototype
selection approaches require $O(|S||T|)$ similarity comparisons between source
and target data points, which becomes prohibitively expensive for large-scale
settings. We propose to mitigate this limitation by employing stochastic greedy
search in the space of prototypical examples and multi-armed bandits for
reducing the number of similarity comparisons. Our randomized algorithm,
ProtoBandit, identifies a set of $k$ prototypes incurring $O(k^3|S|)$
similarity comparisons, which is independent of the size of the target set. An
interesting outcome of our analysis is for the $k$-medoids clustering problem
$T = S$ setting) in which we show that our algorithm ProtoBandit approximates
the BUILD step solution of the partitioning around medoids (PAM) method in
$O(k^3|S|)$ complexity. Empirically, we observe that ProtoBandit reduces the
number of similarity computation calls by several orders of magnitudes
($100-1000$ times) while obtaining solutions similar in quality to those from
state-of-the-art approaches.
Related papers
- Variance Alignment Score: A Simple But Tough-to-Beat Data Selection
Method for Multimodal Contrastive Learning [17.40655778450583]
We propose a principled metric named Variance Alignment Score (VAS), which has the form $langle Sigma_texttest, Sigma_irangle$.
We show that applying VAS and CLIP scores together can outperform baselines by a margin of $1.3%$ on 38 evaluation sets for noisy dataset DataComp and $2.5%$ on VTAB for high-quality dataset CC12M.
arXiv Detail & Related papers (2024-02-03T06:29:04Z) - 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) - Stochastic Approximation Approaches to Group Distributionally Robust
Optimization [96.26317627118912]
Group distributionally robust optimization (GDRO)
Online learning techniques to reduce the number of samples required in each round from $m$ to $1$, keeping the same sample.
A novel formulation of weighted GDRO, which allows us to derive distribution-dependent convergence rates.
arXiv Detail & Related papers (2023-02-18T09:24:15Z) - Piecewise-Stationary Multi-Objective Multi-Armed Bandit with Application
to Joint Communications and Sensing [7.0997346625024]
We propose a generic upper confidence bound (UCB)-based algorithm with change detection to solve this problem.
We also formulate an energy-efficient waveform design problem in an integrated communication and sensing system as a toy example.
arXiv Detail & Related papers (2023-02-10T14:10:14Z) - Differentially-Private Hierarchical Clustering with Provable
Approximation Guarantees [79.59010418610625]
We study differentially private approximation algorithms for hierarchical clustering.
We show strong lower bounds for the problem: that any $epsilon$-DP algorithm must exhibit $O(|V|2/ epsilon)$-additive error for an input dataset.
We propose a private $1+o(1)$ approximation algorithm which also recovers the blocks exactly.
arXiv Detail & Related papers (2023-01-31T19:14:30Z) - 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) - FANOK: Knockoffs in Linear Time [73.5154025911318]
We describe a series of algorithms that efficiently implement Gaussian model-X knockoffs to control the false discovery rate on large scale feature selection problems.
We test our methods on problems with $p$ as large as $500,000$.
arXiv Detail & Related papers (2020-06-15T21:55:34Z) - Breaking the Sample Size Barrier in Model-Based Reinforcement Learning
with a Generative Model [50.38446482252857]
This paper is concerned with the sample efficiency of reinforcement learning, assuming access to a generative model (or simulator)
We first consider $gamma$-discounted infinite-horizon Markov decision processes (MDPs) with state space $mathcalS$ and action space $mathcalA$.
We prove that a plain model-based planning algorithm suffices to achieve minimax-optimal sample complexity given any target accuracy level.
arXiv Detail & Related papers (2020-05-26T17:53:18Z)
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.