English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We examine the task of locating a target region among those induced byintersections of $n$ halfspaces in $\mathbb{R}^d$. This generic task connectsto fundamental machine learning problems, such as training a perceptron andlearning a $\phi$-separable dichotomy. We investigate the average teachingcomplexity of the task, i.e., the minimal number of samples (halfspace queries)required by a teacher to help a version-space learner in locating a randomlyselected target. As our main result, we show that the average-case teachingcomplexity is $\Theta(d)$, which is in sharp contrast to the worst-caseteaching complexity of $\Theta(n)$. If instead, we consider the average-caselearning complexity, the bounds have a dependency on $n$ as $\Theta(n)$ for\tt{i.i.d.} queries and $\Theta(d \log(n))$ for actively chosen queries by thelearner. Our proof techniques are based on novel insights from computationalgeometry, which allow us to count the number of convex polytopes and faces in aEuclidean space depending on the arrangement of halfspaces. Our insights allowus to establish a tight bound on the average-case complexity for$\phi$-separable dichotomies, which generalizes the known $\mathcal{O}(d)$bound on the average number of "extreme patterns" in the classicalcomputational geometry literature (Cover, 1965).

Average-case Complexity of Teaching Convex Polytopes via Halfspace Queries