# Low-Regret and Low-Complexity Learning for Hierarchical Inference

arXiv: https://arxiv.org/abs/2508.08985 · HTML: https://mlsanity.com/paper/2508.08985/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 42 references that are in the map.
- First posted on arXiv 12 Aug 2025.

## Builds on (most cited first, 19 of 19)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [EfficientNet: Rethinking Model Scaling for Convolutional Neural Networks](https://mlsanity.com/paper/1905.11946/) (2019)
- [MobileNetV2: Inverted Residuals and Linear Bottlenecks](https://mlsanity.com/paper/1801.04381/) (2018)
- [A Baseline for Detecting Misclassified and Out-of-Distribution Examples in Neural Networks](https://mlsanity.com/paper/1610.02136/) (2016)
- [ShuffleNet V2: Practical Guidelines for Efficient CNN Architecture Design](https://mlsanity.com/paper/1807.11164/) (2018)
- [Gemma: Open Models Based on Gemini Research and Technology](https://mlsanity.com/paper/2403.08295/) (2024)
- [A Survey of Uncertainty in Deep Neural Networks](https://mlsanity.com/paper/2107.03342/) (2021)
- [BranchyNet: Fast Inference via Early Exiting from Deep Neural Networks](https://mlsanity.com/paper/1709.01686/) (2017)
- [Towards Out-Of-Distribution Generalization: A Survey](https://mlsanity.com/paper/2108.13624/) (2021)
- [Quantized Neural Networks: Training Neural Networks with Low Precision Weights and Activations](https://mlsanity.com/paper/1609.07061/) (2016)
- [Confidence Calibration and Predictive Uncertainty Estimation for Deep Medical Image Segmentation](https://mlsanity.com/paper/1911.13273/) (2019)
- [Edge AI: On-Demand Accelerating Deep Neural Network Inference via Edge Computing](https://mlsanity.com/paper/1910.05316/) (2019)
- [MLPerf Tiny Benchmark](https://mlsanity.com/paper/2106.07597/) (2021)
- [Improving model calibration with accuracy versus uncertainty optimization](https://mlsanity.com/paper/2012.07923/) (2020)
- [Learning for Single-Shot Confidence Calibration in Deep Neural Networks through Stochastic Inferences](https://mlsanity.com/paper/1809.10877/) (2018)
- [Online Algorithms for Hierarchical Inference in Deep Learning applications at the Edge](https://mlsanity.com/paper/2304.00891/) (2023)
- [The Case for Hierarchical Deep Learning Inference at the Network Edge](https://mlsanity.com/paper/2304.11763/) (2023)
- [Improved Decision Module Selection for Hierarchical Inference in Resource-Constrained Edge Devices](https://mlsanity.com/paper/2406.09424/) (2024)

## Abstract (arXiv)

This work focuses on Hierarchical Inference (HI) in edge intelligence systems, where a compact Local-ML model on an end-device works in conjunction with a high-accuracy Remote-ML model on an edge-server. HI aims to reduce latency, improve accuracy, and lower bandwidth usage by first using the Local-ML model for inference and offloading to the Remote-ML only when the local inference is likely incorrect. A critical challenge in HI is estimating the likelihood of the local inference being incorrect, especially when data distributions and offloading costs change over time -- a problem we term Hierarchical Inference Learning (HIL). We introduce a novel approach to HIL by modeling the probability of correct inference by the Local-ML as an increasing function of the model's confidence measure, a structure motivated by empirical observations but previously unexploited. We propose two policies, HI-LCB and HI-LCB-lite, based on the Upper Confidence Bound (UCB) framework. We demonstrate that both policies achieve order-optimal regret of O(log T), a significant improvement over existing HIL policies with O(T2/3) regret guarantees. Notably, HI-LCB-lite has an O(1) per-sample computational complexity, making it well-suited for deployment on devices with severe resource limitations. Simulations using real-world datasets confirm that our policies outperform existing state-of-the-art HIL methods.