Budget Learning via Bracketing.

Aditya Gangrade, Durmus Alp Emre Acar, Venkatesh SaligramaarXiv 2020 · OpenReview

Abstract

Conventional machine learning applications in mobile and IoT settings often transmit data to cloud servers for high-accuracy predictions. However, this incurs significant costs in terms of power, latency, and monetary expense. Budget learning (BL) aims to minimize cloud usage without sacrificing accuracy by leveraging local, edge-implementable models. We introduce a novel formulation for BL using the concept of "bracketing." By sandwiching a complex cloud model's predictions between two simpler edge functions, we decouple the traditionally difficult optimization problem into manageable tasks. Our approach demonstrates theoretical soundness through PAC-style analysis and empirical superiority over existing gating-based methods, achieving 1.2x–1.4x better efficiency on real-world datasets.

Introduction

The "location dilemma" in modern AI pits the high accuracy of massive cloud-based models against the resource constraints of edge devices. While cloud offloading provides intelligence, the communication overhead often becomes the primary bottleneck for battery life and responsiveness. Budget Learning (BL) addresses this by using a local predictor for "easy" instances and querying the cloud only when necessary.

Historically, BL has been framed as a joint optimization of a "gate" (to decide when to transmit) and a "local predictor." This formulation is notoriously difficult to optimize due to its non-convex nature. We propose Bracketing as a more efficient alternative that simplifies the learning process while maintaining functional equivalence to traditional gating.

The Bracketing Framework

Instead of learning a single gate and predictor, the bracketing approach learns two simple functions, $h^-$ and $h^+$, from a local hypothesis class $\mathcal{H}$. These functions are trained to "sandwich" the cloud's prediction $g$:

  1. Lower Bracket ($h^-$): Aiming to stay below the cloud's prediction $g$.
  2. Upper Bracket ($h^+$): Aiming to stay above the cloud's prediction $g$.
A single bracket 'sandwiching' the cloud's prediction region.

When $h^-(x) = h^+(x)$, the cloud's prediction is trapped, and the device can safely predict locally. If $h^-(x) < h^+(x)$, the device is uncertain and queries the cloud.

Decoupled Optimization

The core advantage of bracketing is that finding the optimal brackets is equivalent to solving two independent one-sided learning problems. This decoupling allows for the use of standard convex surrogate losses and Stochastic Gradient Descent (SGD), bypassing the non-convexity issues of joint gating-prediction models.

Theoretical Foundations and Results

We establish the theoretical validity of bracketing through PAC-style definitions for budget learnability, linking it to the Vapnik-Chervonenkis (VC) dimension. If a local class has finite VC dimension, it is "one-sided learnable," ensuring that the brackets can be effectively trained.

Visualizing decision boundaries and query regions for different local hypothesis classes on synthetic 2D data.

On MNIST and CIFAR, bracketing achieved >98% relative accuracy while querying the cloud for only 20–40% of instances. Bracketing outperformed state-of-the-art methods like SelectiveNet and Alternating Minimization by 1.2x to 1.4x in cloud usage reduction. In IoT scenarios, these reductions translate to a 2.5x to 5x increase in device operational lifetime.

Conclusion

Bracketing offers a mathematically elegant and computationally efficient solution to the budget learning problem. By transforming a complex joint optimization into two independent one-sided tasks, it enables high-performance edge-cloud hybrid systems that are easier to train and deploy.

Summary updated

Abstract

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.
BibTeX
@misc{gangrade2020budget,
  author = {Aditya Gangrade and Durmus Alp Emre Acar and Venkatesh Saligrama},
  title = {{Budget Learning via Bracketing.}},
  year = {2020},
  eprint = {2004.06298},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2004.06298},
}
Figure