Average-case Complexity of Teaching Convex Polytopes via Halfspace Queries
We examine the task of locating a target region among those induced by intersections of $n$ halfspaces in $\mathbb{R}^d$. This generic task connects to fundamental machine learning problems, such as training a perceptron and learning a $\phi$-separable dichotomy. We investigate the average teaching complexity 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 randomly selected target. As our main result, we show that the average-case teaching complexity is $\Theta(d)$, which is in sharp contrast to the worst-case teaching complexity of $\Theta(n)$. If instead, we consider the average-case learning 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 the learner. Our proof techniques are based on novel insights from computational geometry, which allow us to count the number of convex polytopes and faces in a Euclidean space depending on the arrangement of halfspaces. Our insights allow us 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 classical computational geometry literature (Cover, 1965).
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Accelerated Frank-Wolfe Algorithms: Complementarity Conditions and Sparsity
We develop new accelerated first-order algorithms in the Frank-Wolfe (FW) family for minimizing smooth convex functions over compact convex sets, with a focus on two prominent constraint classes: (1) polytopes and (2) ma…
Approximation Depth of Convex Polytopes
We study approximations of polytopes in the standard model for computing polytopes using Minkowski sums and (convex hulls of) unions. Specifically, we study the ability to approximate a target polytope by polytopes of a …
Convex Decomposition And Efficient Shape Representation Using Deformable Convex Polytopes
Decomposition of shapes into (approximate) convex parts is essential for applications such as part-based shape representation, shape matching, and collision detection. In this paper, we propose a novel convex decompositi…
A simplex-based measure of symmetry
For compact convex sets $L,K \subset \mathbb{R}^n$, denote by $λ_K(L)$ the smallest size of a homothet of $K$ that contains $L$. We define a measure of symmetry based on the $n$-simplex $Δ= Δ^n \subset \mathbb{R}^n$ as t…
Estimation of Convex Polytopes for Automatic Discovery of Charge State Transitions in Quantum Dot Arrays
In spin based quantum dot arrays, material or fabrication imprecisions affect the behaviour of the device, which must be taken into account when controlling it. This requires measuring the shape of specific convex polyto…
Active Learning