Parameterized Approximation for Robust Clustering in Discrete Geometric
Spaces
- URL: http://arxiv.org/abs/2305.07316v1
- Date: Fri, 12 May 2023 08:43:28 GMT
- Title: Parameterized Approximation for Robust Clustering in Discrete Geometric
Spaces
- Authors: Fateme Abbasi, Sandip Banerjee, Jaros{\l}aw Byrka, Parinya
Chalermsook, Ameet Gadekar, Kamyar Khodamoradi, D\'aniel Marx, Roohani
Sharma, and Joachim Spoerhase
- Abstract summary: We show that even the special case of $k$-Center in dimension $Theta(log n)$ is $(sqrt3/2- o(1))$hard to approximate for FPT algorithms.
We also show that even the special case of $k$-Center in dimension $Theta(log n)$ is $(sqrt3/2- o(1))$hard to approximate for FPT algorithms.
- Score: 0.6732660670243813
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the well-studied Robust $(k, z)$-Clustering problem, which
generalizes the classic $k$-Median, $k$-Means, and $k$-Center problems. Given a
constant $z\ge 1$, the input to Robust $(k, z)$-Clustering is a set $P$ of $n$
weighted points in a metric space $(M,\delta)$ and a positive integer $k$.
Further, each point belongs to one (or more) of the $m$ many different groups
$S_1,S_2,\ldots,S_m$. Our goal is to find a set $X$ of $k$ centers such that
$\max_{i \in [m]} \sum_{p \in S_i} w(p) \delta(p,X)^z$ is minimized.
This problem arises in the domains of robust optimization [Anthony, Goyal,
Gupta, Nagarajan, Math. Oper. Res. 2010] and in algorithmic fairness. For
polynomial time computation, an approximation factor of $O(\log m/\log\log m)$
is known [Makarychev, Vakilian, COLT $2021$], which is tight under a plausible
complexity assumption even in the line metrics. For FPT time, there is a
$(3^z+\epsilon)$-approximation algorithm, which is tight under GAP-ETH [Goyal,
Jaiswal, Inf. Proc. Letters, 2023].
Motivated by the tight lower bounds for general discrete metrics, we focus on
\emph{geometric} spaces such as the (discrete) high-dimensional Euclidean
setting and metrics of low doubling dimension, which play an important role in
data analysis applications. First, for a universal constant $\eta_0 >0.0006$,
we devise a $3^z(1-\eta_{0})$-factor FPT approximation algorithm for discrete
high-dimensional Euclidean spaces thereby bypassing the lower bound for general
metrics. We complement this result by showing that even the special case of
$k$-Center in dimension $\Theta(\log n)$ is $(\sqrt{3/2}- o(1))$-hard to
approximate for FPT algorithms. Finally, we complete the FPT approximation
landscape by designing an FPT $(1+\epsilon)$-approximation scheme (EPAS) for
the metric of sub-logarithmic doubling dimension.
Related papers
- Memory-Constrained Algorithms for Convex Optimization via Recursive
Cutting-Planes [23.94542304111204]
First class of algorithms that provides a positive trade-off between gradient descent and cutting-plane methods in any regime with $epsilonleq 1/sqrt d$.
In the regime $epsilon leq d-Omega(d)$, our algorithm with $p=d$ achieves the information-theoretic optimal memory usage and improves the oracle-complexity of gradient descent.
arXiv Detail & Related papers (2023-06-16T17:00:51Z) - 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) - Low-degree learning and the metric entropy of polynomials [49.1574468325115]
We prove that any (deterministic or randomized) algorithm which learns $mathscrF_nd$ with $L$-accuracy $varepsilon$ requires at least $Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon) satisfies the two-sided estimate $$c (1-varepsilon)2dlog
arXiv Detail & Related papers (2022-03-17T23:52:08Z) - FPT Approximation for Socially Fair Clustering [0.38073142980733]
We are given a set of points $P$ in a metric space $mathcalX$ with a distance function $d(.,.)$.
The goal of the socially fair $k$-median problem is to find a set $C subseteq F$ of $k$ centers that minimizes the maximum average cost over all the groups.
In this work, we design $(5+varepsilon)$ and $(33 + varepsilon)$ approximation algorithms for the socially fair $k$-median and $k$-means
arXiv Detail & Related papers (2021-06-12T11:53:18Z) - Locally Private $k$-Means Clustering with Constant Multiplicative
Approximation and Near-Optimal Additive Error [10.632986841188]
We bridge the gap between the exponents of $n$ in the upper and lower bounds on the additive error with two new algorithms.
It is possible to solve the locally private $k$-means problem in a constant number of rounds with constant factor multiplicative approximation.
arXiv Detail & Related papers (2021-05-31T14:41:40Z) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
We show that there exists an $epsilon$-cover for $S$ of cardinality $M = (k/epsilon)O_d(k1/d)$.
Building on our structural result, we obtain significantly improved learning algorithms for several fundamental high-dimensional probabilistic models hidden variables.
arXiv Detail & Related papers (2020-12-14T18:14:08Z) - 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) - Sets Clustering [25.358415142404752]
We prove that a core-set of $O(logn)$ sets always exists, and can be computed in $O(nlogn)$ time.
Applying an inefficient but optimal algorithm on this coreset allows us to obtain the first PTAS ($1+varepsilon$ approximation) for the sets-$k$-means problem.
Open source code and experimental results for document classification and facility locations are also provided.
arXiv Detail & Related papers (2020-03-09T13:30:30Z) - Agnostic Q-learning with Function Approximation in Deterministic
Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
We study the problem of agnostic $Q$-learning with function approximation in deterministic systems.
We show that if $delta = Oleft(rho/sqrtdim_Eright)$, then one can find the optimal policy using $Oleft(dim_Eright)$.
arXiv Detail & Related papers (2020-02-17T18:41:49Z) - Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast
Algorithm [100.11971836788437]
We study the fixed-support Wasserstein barycenter problem (FS-WBP)
We develop a provably fast textitdeterministic variant of the celebrated iterative Bregman projection (IBP) algorithm, named textscFastIBP.
arXiv Detail & Related papers (2020-02-12T03:40:52Z)
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.