Budget Learning via Bracketing
  Conventional machine learning applications in the mobile/IoT setting transmit
data to a cloud-server for predictions. Due to cost considerations (power,
latency, monetary), it is desirable to minimise device-to-server transmissions.
The budget learning (BL) problem poses the learner's goal as minimising use of
the cloud while suffering no discernible loss in accuracy, under the constraint
that the methods employed be edge-implementable.
  We propose a new formulation for the BL problem via the concept of
bracketings. Concretely, we propose to sandwich the cloud's prediction, $g,$
via functions $h^-, h^+$ from a `simple' class so that $h^- \le g \le h^+$
nearly always. On an instance $x$, if $h^+(x)=h^-(x)$, we leverage local
processing, and bypass the cloud. We explore theoretical aspects of this
formulation, providing PAC-style learnability definitions; associating the
notion of budget learnability to approximability via brackets; and giving
VC-theoretic analyses of their properties. We empirically validate our theory
on real-world datasets, demonstrating improved performance over prior gating
based methods.
