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$:
- Lower Bracket ($h^-$): Aiming to stay below the cloud's prediction $g$.
- Upper Bracket ($h^+$): Aiming to stay above the cloud's prediction $g$.
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.
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