Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPoint Location and Active Learning: Learning Halfspaces Almost Optimally
73
0
0.0
(
0
)
Added by
Max Hopkins
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Given a finite set $X subset mathbb{R}^d$ and a binary linear classifier $c: mathbb{R}^d to {0,1}$, how many queries of the form $c(x)$ are required to learn the label of every point in $X$? Known as textit{point location}, this problem has inspired over 35 years of research in the pursuit of an optimal algorithm. Building on the prior work of Kane, Lovett, and Moran (ICALP 2018), we provide the first nearly optimal solution, a randomized linear decision tree of depth $tilde{O}(dlog(|X|))$, improving on the previous best of $tilde{O}(d^2log(|X|))$ from Ezra and Sharir (Discrete and Computational Geometry, 2019). As a corollary, we also provide the first nearly optimal algorithm for actively learning halfspaces in the membership query model. En route to these results, we prove a novel characterization of Barthes Theorem (Inventiones Mathematicae, 1998) of independent interest. In particular, we show that $X$ may be transformed into approximate isotropic position if and only if there exists no $k$-dimensional subspace with more than a $k/d$-fraction of $X$, and provide a similar characterization for exact isotropic position.
rate research
Read More
We present self-adjusting data structures for answering point location queries in convex and connected subdivisions. Let $n$ be the number of vertices in a convex or connected subdivision. Our structures use $O(n)$ space. For any convex subdivision $S$, our method processes any online query sequence $sigma$ in $O(mathrm{OPT} + n)$ time, where $mathrm{OPT}$ is the minimum time required by any linear decision tree for answering point location queries in $S$ to process $sigma$. For connected subdivisions, the processing time is $O(mathrm{OPT} + n + |sigma|log(log^* n))$. In both cases, the time bound includes the $O(n)$ preprocessing time.
We propose a dynamic data structure for the distribution-sensitive point location problem. Suppose that there is a fixed query distribution in $mathbb{R}^2$, and we are given an oracle that can return in $O(1)$ time the probability of a query point falling into a polygonal region of constant complexity. We can maintain a convex subdivision $cal S$ with $n$ vertices such that each query is answered in $O(mathrm{OPT})$ expected time, where OPT is the minimum expected time of the best linear decision tree for point location in $cal S$. The space and construction time are $O(nlog^2 n)$. An update of $cal S$ as a mixed sequence of $k$ edge insertions and deletions takes $O(klog^5 n)$ amortized time. As a corollary, the randomized incremental construction of the Voronoi diagram of $n$ sites can be performed in $O(nlog^5 n)$ expected time so that, during the incremental construction, a nearest neighbor query at any time can be answered optimally with respect to the intermediate Voronoi diagram at that time.
We give a computationally-efficient PAC active learning algorithm for $d$-dimensional homogeneous halfspaces that can tolerate Massart noise (Massart and Nedelec, 2006) and Tsybakov noise (Tsybakov, 2004). Specialized to the $eta$-Massart noise setting, our algorithm achieves an information-theoretically near-optimal label complexity of $tilde{O}left( frac{d}{(1-2eta)^2} mathrm{polylog}(frac1epsilon) right)$ under a wide range of unlabeled data distributions (specifically, the family of structured distributions defined in Diakonikolas et al. (2020)). Under the more challenging Tsybakov noise condition, we identify two subfamilies of noise conditions, under which our efficient algorithm provides label complexity guarantees strictly lower than passive learning algorithms.
We study efficient PAC learning of homogeneous halfspaces in $mathbb{R}^d$ in the presence of malicious noise of Valiant~(1985). This is a challenging noise model and only until recently has near-optimal noise tolerance bound been established under the mild condition that the unlabeled data distribution is isotropic log-concave. However, it remains unsettled how to obtain the optimal sample complexity simultaneously. In this work, we present a new analysis for the algorithm of Awasthi~et~al.~(2017) and show that it essentially achieves the near-optimal sample complexity bound of $tilde{O}(d)$, improving the best known result of $tilde{O}(d^2)$. Our main ingredient is a novel incorporation of a matrix Chernoff-type inequality to bound the spectrum of an empirical covariance matrix for well-behaved distributions, in conjunction with a careful exploration of the localization schemes of Awasthi~et~al.~(2017). We further extend the algorithm and analysis to the more general and stronger nasty noise model of Bshouty~et~al.~(2002), showing that it is still possible to achieve near-optimal noise tolerance and sample complexity in polynomial time.
We study how to dynamize the Trapezoidal Search Tree - a well known randomized point location structure for planar subdivisions of kinetic line segments. Our approach naturally extends incremental leaf-level insertions to recursive methods and allows adaptation for the online setting. Moreover, the dynamization carries over to the Trapezoidal Search DAG, offering a linear sized data structure with logarithmic point location costs as a by-product. On a set $S$ of non-crossing segments, each update performs expected ${mathcal O}(log^2|S|)$ operations. We demonstrate the practicality of our method with an open-source implementation, based on the Computational Geometry Algorithms Library, and experiments on the update performance.
suggested questions
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
