# Computationally lightweight classifiers with frequentist bounds on predictions

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 60 references that are in the map.
- First posted on arXiv 23 Mar 2026.

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

- [On Calibration of Modern Neural Networks](https://mlsanity.com/paper/1706.04599/) (2017)
- [Dropout as a Bayesian Approximation: Representing Model Uncertainty in Deep Learning](https://mlsanity.com/paper/1506.02142/) (2015)
- [Safe Learning in Robotics: From Learning-Based Control to Safe Reinforcement Learning](https://mlsanity.com/paper/2108.06266/) (2021)
- [Explainable Artificial Intelligence (XAI) 2.0: A Manifesto of Open Challenges and Interdisciplinary Research Directions](https://mlsanity.com/paper/2310.19775/) (2023)
- [ECG Heartbeat Classification: A Deep Transferable Representation](https://mlsanity.com/paper/1805.00794/) (2018)
- [Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/1405.4758/) (2014)
- [Multi-class Gaussian Process Classification with Noisy Inputs](https://mlsanity.com/paper/2001.10523/) (2020)
- [Safe exploration in reproducing kernel Hilbert spaces](https://mlsanity.com/paper/2503.10352/) (2025)
- [MuyGPs: Scalable Gaussian Process Hyperparameter Estimation Using Local Cross-Validation](https://mlsanity.com/paper/2104.14581/) (2021)
- [Lazily Adapted Constant Kinky Inference for Nonparametric Regression and Model-Reference Adaptive Control](https://mlsanity.com/paper/1701.00178/) (2016)
- [A computationally lightweight safe learning algorithm](https://mlsanity.com/paper/2309.03672/) (2023)
- [A Deep Bayesian Neural Network for Cardiac Arrhythmia Classification with Rejection from ECG Recordings](https://mlsanity.com/paper/2203.00512/) (2022)
- [Safety and optimality in learning-based control at low computational cost](https://mlsanity.com/paper/2505.08026/) (2025)
- [Safe reinforcement learning in uncertain contexts](https://mlsanity.com/paper/2401.05876/) (2024)
- [Kernel-based learning with guarantees for multi-agent applications](https://mlsanity.com/paper/2404.09708/) (2024)

## Built on by (most cited first, 1 of 1)

- [Computationally efficient safe exploration in reinforcement learning](https://mlsanity.com/paper/2609.22919/) (2026)

## Abstract (arXiv)

While both classical and neural network classifiers can achieve high accuracy, they fall short on offering uncertainty bounds on their predictions, making them unfit for safety-critical applications. Existing kernel-based classifiers that provide such bounds scale with mathcal O (n~3) in time, making them computationally intractable for large datasets. To address this, we propose a novel, computationally efficient classification algorithm based on the Nadaraya-Watson estimator, for whose estimates we derive frequentist uncertainty intervals. We evaluate our classifier on synthetically generated data and on electrocardiographic heartbeat signals from the MIT-BIH Arrhythmia database. We show that the method achieves competitive accuracy >SI96percent at mathcal O(n) and mathcal O(log n) operations, while providing actionable uncertainty bounds. These bounds can, e.g., aid in flagging low-confidence predictions, making them suitable for real-time settings with resource constraints, such as diagnostic monitoring or implantable devices.