It is proved that testing is no more efficient than learning for halfspaces in the distribution-free sample-based model, and it is established that two-sided halfspace testers in this model have no advantage over one-sided testers.
Abstract
We prove a tight $\Theta(n/\epsilon)$ lower bound on the number of samples required for testing halfspaces over $\mathbb{R}^n$, in the distribution-free sample-based model where the underlying probability distribution is unknown to the algorithm, and the algorithm only receives random samples (i.e., it cannot make queries). This shows that testing is no more efficient than learning for halfspaces. We also show a matching upper bound for one-sided testers, improving on the standard (two-sided) testing-by-learning reduction, establishing that two-sided halfspace testers in this model have no advantage over one-sided testers.
In this note, we introduce the notion of ranked spreadness, a strengthening of the usual spread condition in which the elements of each member can be ordered so that their one-coordinate marginals decay geometrically with their rank. This additional structure removes the dependence on the maximum set size in random-con...
First proposed in 1968, quadratic probing has stood for more than half a century as one of the simplest and most widely used hash-table designs in computer science. It is conjectured that, at load factor $1 - \epsilon$, the hash table achieves $O(\epsilon^{-1})$ expected insertion time. But even proving a bound of the...
Yang Hu, William Kuszmaul, Jingxun Liang et al.· 0 citations
The optimal query complexity up to constant factors is determined: while the noiseless complexity matches the classical complexity of sorting, each untruthful counterexample incurs an additional cost of order $n$.
We prove a filtration-level conversion from uniform fixed-time testing to all-sample one-sided error control and uniform future-tail control. Given an adapted deterministic binary test whose worst-case fixed-time error tends to zero, the construction selects update times with prescribed summable error budgets and holds...
This model shows that adding correctly labeled examples can make learning harder by a logarithmic factor, even for classes that admit finite mistake bounds in online learning.
The characterisation shows that the two information costs can be quite different and identifies three parameter regimes, with optimal protocols based respectively on clean samples, a noisy binary symmetric channel, and an asymmetric $Z$-channel.
H. Kazemi, Varun Jog· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
