\section{Average-case Teaching Complexity} \label{sec:avgtd}
In this section, we study the generic problem of teaching convex polytopes via halfspace queries as illustrated in \figref{fig:example.polytope}. Before establishing our main result, we first introduce two important results inherently connected to the average teaching complexity: the number of regions (which corresponds to the target hypotheses) induced by the intersections of $n$ halfspaces, 
and the number of faces 
(which corresponds to the teaching sets) induced by the hyperplane arrangement. 
Our proofs are inspired by ideas from combinatorial geometry and affine geometry, as detailed below. 

\subsection{Regions and Faces Induced by Intersections of Halfspaces}\label{subsection: count regions}
Consider a set of $n$ hyperplanes $\Hnd$ in $\Rd$. 
Generally, it is non-trivial to count the number of regions induced by an arbitrary hyperplane arrangement $\cA\parenb{\Hnd}$. When the hyperplane arrangement is in general position  (\defref{defn general position}, \figref{fig:example.3general}), \cite{miller2007geometric} established an exact result for counting the induced regions. However, it remains a challenging problem to identify the number of regions for more general hyperplane arrangements. However, we show that under the relaxed condition of \defref{defn relaxed general position}, which accounts for various non-trivial arrangements as shown in \figref{fig:example.3general}-\ref{fig:example.1general}, one can exactly count the number of regions.
\begin{theorem}[\bf Regions induced by $d'$-relaxed general position arrangement]\label{thm:d'-general}
Consider a set $\Hnd$ of $n$ hyperplanes in $\mathbb{R}^d$. If the hyperplane arrangement $\mathcal{A}(\Hnd)$ is in $d'$-relaxed general position for some $d' \in \left[d\right]$, then the following holds: $\fr\parenb{\mathcal{A}(\Hnd)} = \sum_{i=0}^{d'} \binom{n}{i}.$
\end{theorem}
\looseness -1 In the following we sketch the proof of \thmref{thm:d'-general}.

The key insight for the proof is
in reducing it to the special case of general position in some $d'$ subspace where $d'\leq d$. We show the reduction by constructing a subspace $\mathbb{N}$ defined as:
$$\mathbb{N} \triangleq \textbf{span}\tuple{\curlybracket{\eta_h \bigm\vert h \in \Hnd,\: h \coloneqq \eta_h\cdot \h{}+ b_h = 0,\: \h{}\in \mathbb{R}^d}}.$$
As a key observation, note that $\mathbb{N}$ is $d'$-dimensional. Let $\Hndd$ be the induced set of hyperplanes in the subspace $\mathbb{N}$ formed by the intersections of $\Hnd$ with $\mathbb{N}$. Therefore, the number of regions induced\footnote{ This idea is more formally studied in the hyperplane arrangement literature as \tt{essentialization} \citep[see][chap: An introduction to hyperplane arrangement]{miller2007geometric}. See \appref{appendixsub: bijection} for further discussion.} by the arrangement of $\Hndd$, denoted as $\fr\parenb{\cA(\Hndd)}$, is exactly $\fr\parenb{\cA(\Hnd)}$. Thus, informatively, it is sufficient to rely on $\cA(\Hndd)$ in $\mathbb{N}$ to understand the intersection of halfspaces induced by $\cA(\Hnd)$ in $\Rd$. We observe that every region $\hat{r} \in \mathcal{A}(\Hndd)$ is contained in exactly one region in $\mathcal{A}(\Hnd)$.
With this observation, we construct the following map $\mathcal{B}$ from the regions induced by the hyperplane arrangement $\mathcal{A}(\Hndd)$, to those induced by $\mathcal{A}(\Hnd)$:
\begin{align*}
  \mathcal{B}:\:\boldsymbol{\mathfrak{R}}\parenb{\mathcal{A}(\Hndd)} &
  \longrightarrow \boldsymbol{\mathfrak{R}}\parenb{\mathcal{A}( \Hnd)} \quad :\quad
  \hat{r} 
  \longmapsto \mathbf{region}_{\mathcal{A}(\Hnd)}(\hat{r}),
\end{align*}
where $\mathbf{region}_{\mathcal{A}(\Hnd)}(\hat{r}) \coloneqq r$ for some $r \in \regionset$ such that $\hat{r} \subseteq r$. 
The following proposition shows that $\mathcal{B}$ is bijective, thereby providing an alternate way to count $\regionset$.
\begin{proposition}\label{bijection}
The map $\mathcal{B}$ (as defined above) is a bijection. Thus,  $\fr\parenb{\mathcal{A}(\Hnd)} = \fr\parenb{\mathcal{A}(\Hndd)}$.
\end{proposition}
Note that, if we can resolve $\fr\parenb{\mathcal{A}(\Hndd)}$ induced by the hyperplane arrangement $\cA\parenb{\Hndd}$, then $\fr\parenb{\mathcal{A}(\Hnd)}$ can be ascertained too. 
The following key lemma, proved in \iftoggle{longversion}{\appref{appendixsub: key lemma}}{the supplemental materials}, shows that $\mathcal{A}(\Hndd)$ is in $d'$-relaxed general position. 
\begin{lemma}
\label{key lemma}
The induced hyperplane arrangement $\mathcal{A}(\Hndd)$ is in $d'$-relaxed general position. 
\end{lemma}
This implies that $\cA\parenb{\Hndd}$ is  structurally the same as $d'$-general position arrangement of $n$ hyperplanes (\tt{i.e.} \defref{defn general position}) in $\mathbb{R}^{d'}$ because any $d'$-dimensional subspace of $\mathbb{R}^{d}$ is \tt{isomorphic} to $\mathbb{R}^{d'}$. Thus, from the relaxed definition of general position, we reduce the problem of counting $\rnd$ to counting 
$\fr\parenb{\cA\parenb{\Hndd}}$ which has the special arrangement of general position. By 
\cite{miller2007geometric} we therefore conclude that $\fr\parenb{\cA\parenb{\Hnd}}$ can be ascertained in an exact form as in \thmref{thm:d'-general}. We defer the full proof of \thmref{thm:d'-general} to \iftoggle{longversion}{\appref{appendix: regions relaxed general position}}{the supplemental materials}.

\paragraph{Faces Induced by $\cA(\Hnd)$} 
We denote by $\ff\parenb{\cA(\Hnd)}$ the number of faces (i.e. regions induced on the hyperplanes) induced by $\cA(\Hnd)$ in $\Rd$.
Consider an arbitrary $h^* \in \regionset$. Note if $\cA(\Hnd)$ is in $d'$-relaxed general position for 
$d' > 1$ then $\forall h \in \Hnd\setminus \{h^*\}$, intersection of $h$ and $h^*$ forms a $(d-2)$-dimensional \tt{flat} on $h^*$ by definition (see \iftoggle{longversion}{\appref{appendixsub: affine geometry}}{supplemental materials} for formal definitions of the relevant affine geometry concepts).
To count the regions induced on $h^*$ is to analyze, $\mathrm{wrt}$  $\Hnd\setminus \{h^*\}$, the $n-1$ \tt{flats} of dimension $(d-2)$; thereby reducing the problem to the case of $n-1$ hyperplanes in $\mathbb{R}^{d-1}$. We would show that these \tt{newly} induced hyperplanes (\tt{i.e. flats}) are in relaxed general position, and thus one can invoke \thmref{thm:d'-general} to count the faces. 

\propref{faces_teach}, as proved in \iftoggle{longversion}{\appref{appendix: faces teaching}}{the supplemental materials}, provides the exact count of faces induced by $\cA(\Hnd)$.
\begin{proposition}[\bf Faces induced by hyperplane arrangement]\label{faces_teach}
Consider a set $\Hnd$ of $n$ hyperplanes in $\mathbb{R}^d$. If the hyperplane arrangement $\mathcal{A}(\Hnd)$ is in $d'$-relaxed general position for some $d' \in \left[d\right]$, the number of faces induced by the arrangement satisfies the recursion:
 
     $\ff\parenb{\cA(\Hnd)} =  n\cdot \sum_{i=0}^{d'-1}\binom{n-1}{i}.$
 
\end{proposition}
\subsection{Bound for Average Teaching Complexity: $\bigTheta{d'}$}\label{subsection: main theorem}
\looseness -1
We are now ready to provide our main result on the average-case teaching complexity, when considering teaching convex polytopes induced by hyperplanes in $d'$-\tt{relaxed general position}.
We show that using results in \secref{subsection: count regions}, 

we achieve an \tt{average-case} teaching complexity of $\Theta(d')$ by \algoref{algo: teaching halfspace}. 
\paragraph{Teaching algorithm}


\begin{wrapfigure}{R}{0.4\textwidth}
\scalebox{0.8}{
    \begin{minipage}{0.5\textwidth}
    \vspace{-5mm}
\begin{algorithm}[H]


\nl {\bf Input}: $\Hnd$; random target region $\rgn \in \regionset$  {\label{lst:line:dual01}}\\
\Begin{
\tcp{indentifies  $\mathcal{TS}(\Hnd,\rgn)$ via linear programming} 
\nl $\mathcal{TS}(\Hnd,\rgn) \leftarrow$ {\bf FindTS}$\parenb{\rgn}${\label{lst:line:dual02}}\\
\nl\For {$(h,l)$ $\in$ $\mathcal{TS}(\Hnd,\rgn)$ {\label{lst:line:dual03}}}{
teacher provides halfspace queries $(h,l)$
}
}

\caption{Teaching algorithm}\label{algo: teaching halfspace}
\end{algorithm}
\vspace{-6mm}
\end{minipage}
}
\end{wrapfigure}


Let $\rgn \sim \mathcal{U}$ be a region sampled uniformly at random from $\regionset$. 
To teach $\rgn$, a teacher 
has to provide the halfspace queries in $\mathcal{TS}(\Hnd,\rgn)$. Note that these labels is sufficient to teach $\rgn$ since the version space $\mathrm{VS}(\mathcal{TS}(\Hnd, \rgn)) = \{\rgn\}$. In \algoref{algo: teaching halfspace}, the teacher first collects $\mathcal{TS}(\Hnd,\rgn)$ via subroutine \textbf{FindTS}($\cdot$), and then provides labels to the learner. In particular, the subroutine \textbf{FindTS}($\cdot$) identifies $\mathcal{TS}(\Hnd,\rgn)$ via linear programming:
It checks if each hyperplane intersects the convex body defined by all the $n-1$ constraints (one linear constraint for each hyperplane); each iteration takes polynomial time as it requires solving a linear equation system. In total, it takes $n$ iterations to decide whether any hyperplane is in the teaching set. Thus, the overall computational complexity of this algorithm is $\cO(\textbf{poly}(d)\cdot\textbf{poly}(n))$ (assuming $d$ is smaller than $n$).


\paragraph{Average-case analysis} 
Recall that in section \secref{section: teaching framework}, we defined $B_{r^*}$ to be the bounding set of hyperplanes for the polytope that contains $r^*$.  
To teach $r^*$,  
the teacher has to \tt{identify} the \tt{exact} subset of hyperplanes in $B_{r^*}$ 
(\tt{i.e.} the \tt{faces of the polytope}), 
and provides the halfspace labels corresponding to the hyperplanes in $B_{r^*}$. 
Thus, teaching a target region corresponds to providing labels for the faces of the bounding set. One can ask if there are \tt{pathological} arrangements, where teacher has to provide all the $n$ labels? It turns out that, one can construct arrangements of the hyperplane set $\Hnd$ in $\Rd$ where the \tt{worst-case} teaching complexity is $\bigOmega{n}$ as shown in \thmref{theorem: Main Theorem}. This calls for analyzing the teaching problem under the \tt{average-case}.\vspace{6pt}\\
\noindent
Intuitively, the average teaching complexity of convex polytopes reduces to the average number of faces per region, 


\tt{i.e.} the ratio of number of faces induced on $\Hnd$ to number of regions induced in $\Rd$ by $\cA\parenb{\Hnd}$. In \tt{arbitrary} arrangement of hyperplanes, it is challenging to bound the ratio \ref{eqn:tag:a.1}, as one needs to provide upper bound and lower bound for both terms, and it is unclear how $\ff\parenb{\cA(\Hnd)}$ and $\fr\parenb{\cA(\Hnd)}$ are correlated. However, by imposing the $d'$-\tt{relaxed general position} condition (for any $d' \in \bracket{d}$ ) on the hyperplane arrangement, we can leverage our exact results on counting the regions and faces using \thmref{thm:d'-general} and \propref{faces_teach}:
\begin{align}
    
    \expctover{\rgn\sim\cU}{|\mathcal{TS}(\Hnd,\rgn)|}
    = \underbrace{\frac{2\cdot\ff\parenb{\cA(\Hnd)}}{\fr\parenb{\cA(\Hnd)}} = 
    \frac{ \text{\propref{faces_teach}}}{\text{\thmref{thm:d'-general}}} }_{\textbf{$d'$-relaxed general position}}.
    \tag{A.1}\label{eqn:tag:a.1}
    \nonumber
\vspace{-5mm}
\end{align}
Ideally, to bound \ref{eqn:tag:a.1}, $\ff(\cdot)$ and $\fr(\cdot)$ need to be appropriately bounded. 
We further show (\iftoggle{longversion}{in the \appref{appendix: main theorem}}{in supplemental}) that for a relaxed general position of hyperplane arrangement, $\ff\parenb{\cA(\Hnd)}$ can be rewritten in terms of $\fr(\cdot)$ 

in lower dimensional space.
Thus, to bound the ratio in \ref{eqn:tag:a.1}, it suffices to bound $\fr(\cdot)$. \corref{cor: bounds regions}, as proved in \iftoggle{longversion}{\appref{appendix: main theorem}}{the supplemental materials}, provides 
tight bounds on $\fr(\cdot)$.
\begin{corollary}\label{cor: bounds regions}
If $\cA(\Hnd)$ is in $d'$-relaxed general position, then $\rnd$ satisfies the following for $n > 2d'$:
$ \binom{n-1}{d'} \le\:\:\rnd\:\: \le \binom{n}{d'}\cdot\frac{n-d'+1}{n-2d'+1}$


\end{corollary}
Let $M_n$ denote the sample size of $\mathcal{TS}(\Hnd, \rgn)$ from \algoref{algo: teaching halfspace} to teach $\rgn\sim \mathcal{U}$, then $\expctover{\cU}{M_n} = \expctover{r\sim\cU}{|\mathcal{TS}(\Hnd,r)|}$. Combining \eqref{eqn:tag:a.1} and \corref{cor: bounds regions}, we obtain our main result below.
\begin{theorem}[\bf Main theorem]\label{theorem: Main Theorem}
Assume $\Hnd$ is in $d'$-\tt{relaxed general position}. Assume $\rgn$ $\sim$ $\mathcal{U}$. Let the random variable $M_n$ denote the number of halfspace queries that are requested in the teaching \algoref{algo: teaching halfspace}, then, 
$\expctover{\cU}{M_n} = \bigTheta{d'},$
\tt{i.e.} the average teaching complexity of convex polytopes is $\bigTheta{d'}$. Furthermore, the worst-case teaching complexity of convex polytopes is $\bigTheta{n}$.
\end{theorem}

\paragraph{Arbitrary position arrangements of hyperplanes} For general position arrangement, exact forms have been established \citep{miller2007geometric,trove.nla.gov.au/work/10888269,10.2307/2303424} for $\rnd$. But it is mentioned in \cite{Fukuda1991BoundingTN} that for \tt{any} arbitrary arrangement one cannot explicitly give a simple formula for $\rnd$ since 
\citet{Vergnas1980ConvexityIO} and \citet{trove.nla.gov.au/work/10888269}
showed that $\rnd$ depends on the underlying matroid structure. Interestingly, via \thmref{thm:d'-general} we establish an exact form for a non-trivial ($d'$-relaxed general position) setting. Apparently, $\mathrm{Theorem}$ 1.2 of \:\citet{Fukuda1991BoundingTN} establishes that for \tt{any} hyperplane arrangement, average teaching complexity of convex polytopes is $\bigO{d}$. In contrast, \thmref{theorem: Main Theorem} provides a stronger bound of $\bigTheta{d'}$ in the $d'$-relaxed general position setting since $d'\le d$. In addition, as further discussed \iftoggle{longversion}{in the \appref{appsubsec: discussion on extension}}{in the supplemental materials} the geometrical insights in the proof of \thmref{thm:d'-general} can be leveraged for extending to more general teaching complexity results. 
\looseness -3


\vspace{-1mm}
{"config": "arxiv", "file": "2006.14677/3.hyperplane_general.tex"}