Approximate Maximum Halfspace Discrepancy
- URL: http://arxiv.org/abs/2106.13851v1
- Date: Fri, 25 Jun 2021 19:14:45 GMT
- Title: Approximate Maximum Halfspace Discrepancy
- Authors: Michael Matheny and Jeff M. Phillips
- Abstract summary: We consider the range space $(X, mathcalH_d)$ where $X subset mathbbRd$ and $mathcalH_d$ is the set of ranges defined by $d$ halfspaces.
For each halfspace $h in mathcalH_d$ define a function $Phi(h)$ that measures the "difference" between the fraction of red and fraction of blue points which fall in the range $h$.
- Score: 6.35821487778241
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Consider the geometric range space $(X, \mathcal{H}_d)$ where $X \subset
\mathbb{R}^d$ and $\mathcal{H}_d$ is the set of ranges defined by
$d$-dimensional halfspaces. In this setting we consider that $X$ is the
disjoint union of a red and blue set. For each halfspace $h \in \mathcal{H}_d$
define a function $\Phi(h)$ that measures the "difference" between the fraction
of red and fraction of blue points which fall in the range $h$. In this context
the maximum discrepancy problem is to find the $h^* = \arg \max_{h \in (X,
\mathcal{H}_d)} \Phi(h)$. We aim to instead find an $\hat{h}$ such that
$\Phi(h^*) - \Phi(\hat{h}) \le \varepsilon$. This is the central problem in
linear classification for machine learning, in spatial scan statistics for
spatial anomaly detection, and shows up in many other areas. We provide a
solution for this problem in $O(|X| + (1/\varepsilon^d) \log^4
(1/\varepsilon))$ time, which improves polynomially over the previous best
solutions. For $d=2$ we show that this is nearly tight through conditional
lower bounds. For different classes of $\Phi$ we can either provide a
$\Omega(|X|^{3/2 - o(1)})$ time lower bound for the exact solution with a
reduction to APSP, or an $\Omega(|X| + 1/\varepsilon^{2-o(1)})$ lower bound for
the approximate solution with a reduction to 3SUM.
A key technical result is a $\varepsilon$-approximate halfspace range
counting data structure of size $O(1/\varepsilon^d)$ with $O(\log
(1/\varepsilon))$ query time, which we can build in $O(|X| + (1/\varepsilon^d)
\log^4 (1/\varepsilon))$ time.
Related papers
- Fast, robust approximate message passing [2.668787455520979]
We give a fast, spectral procedure for implementing approximate-message passing (AMP) algorithms robustly.
Our algorithm performs a spectral pre-processing step and mildly modifies the perturbeds of $mathcal A$.
arXiv Detail & Related papers (2024-11-05T03:20:14Z) - Efficient Continual Finite-Sum Minimization [52.5238287567572]
We propose a key twist into the finite-sum minimization, dubbed as continual finite-sum minimization.
Our approach significantly improves upon the $mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$ requires.
We also prove that there is no natural first-order method with $mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$, establishing that the first-order complexity of our method is nearly tight.
arXiv Detail & Related papers (2024-06-07T08:26:31Z) - For Kernel Range Spaces a Constant Number of Queries Are Sufficient [13.200502573462712]
A kernel range space concerns a set of points $X subset mathbbRd$ and the space of all queries by a fixed kernel.
Anvarepsilon$-cover is a subset of points $Q subset mathbbRd$ for any $p in mathbbRd$ that $frac1n |R_p - R_q|leq varepsilon$ for some $q in Q$.
arXiv Detail & Related papers (2023-06-28T19:19:33Z) - 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) - Improved Coresets for Euclidean $k$-Means [24.850829728643923]
Given a set of $n$ points in $d$ dimensions, the Euclidean $k$-means problem (resp. the Euclidean $k$-median problem) consists of finding $k$ centers.
In this paper, we improve the upper bounds $tilde O(min(k2 cdot varepsilon-2,kcdot varepsilon-4)$ for $k$-means and $tilde O(min(k4/3 cdot varepsilon
arXiv Detail & Related papers (2022-11-15T14:47:24Z) - Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
We study iterative methods based on Krylov subspaces for low-rank approximation under any Schatten-$p$ norm.
Our main result is an algorithm that uses only $tildeO(k/sqrtepsilon)$ matrix-vector products.
arXiv Detail & Related papers (2022-02-10T16:10:41Z) - Learning low-degree functions from a logarithmic number of random
queries [77.34726150561087]
We prove that for any integer $ninmathbbN$, $din1,ldots,n$ and any $varepsilon,deltain(0,1)$, a bounded function $f:-1,1nto[-1,1]$ of degree at most $d$ can be learned.
arXiv Detail & Related papers (2021-09-21T13:19:04Z) - 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) - Infinite-Horizon Offline Reinforcement Learning with Linear Function
Approximation: Curse of Dimensionality and Algorithm [46.36534144138337]
In this paper, we investigate the sample complexity of policy evaluation in offline reinforcement learning.
Under the low distribution shift assumption, we show that there is an algorithm that needs at most $Oleft(maxleft fracleftVert thetapirightVert _24varepsilon4logfracddelta,frac1varepsilon2left(d+logfrac1deltaright)right right)$ samples to approximate the
arXiv Detail & Related papers (2021-03-17T18:18:57Z) - 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) - 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.