At the core of our base algorithm is the computation of the John ellipsoid [1]}, [2]}, the maximal volume ellipsoid contained in a convex body.Some authors refer to the minimal volume ellipsoid containing a convex body as the John ellipsoid. It is well-known that given a polytope in \(\mathbb {R}^d\) , the John ellipsoid can be computed in time polynomial in \(d\)  and the number of faces [3]}. In particular, we compute the John ellipsoid of the version space, \(\mathcal {F}_t\) , where for any time \(t\) , we let \(\mathcal {F}_t = \lbrace f \in \mathcal {F}_{\mathrm {lin}}^d | f(x_s) = y_s \text{ for all } s < t\rbrace \) , which is a polytope with \(t \le T\)  faces. An important concept in our analysis is the notion of Hausdorff measure, which generalizes the standard notions of volume and surface area in \(\mathbb {R}^d\) ; we will denote the \(k\) -dimensional Hausdorff measure (see def:hausdorff) by \(\operatorname{vol}_k(\cdot )\) . More detail on both the John ellipsoid and the Hausdorff measure can be found in app:prelims.
