Computationally lightweight classifiers with frequentist bounds on predictions

2026/03/23 by Shreeram Murali, Cristian R. Rojas, Dominik Baumann · 1 voice
Computer Science · Mathematics · #cs.LG #stat.ML

paper · pdf · doi:10.48550/arxiv.2603.22128

arxiv published 2026/03/23 · arxiv updated 2026/04/09

Abstract

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 >\SI96\percent 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.

Citations

• Safety and optimality in learning-based control at low computational cost
• Safe exploration in reproducing kernel Hilbert spaces
• Enhancing Electrocardiography Data Classification Confidence: A Robust Gaussian Process Approach (MuyGPs)
• Kernel-based learning with guarantees for multi-agent applications
• Safe reinforcement learning in uncertain contexts
• A computationally lightweight safe learning algorithm
• A Deep Bayesian Neural Network for Cardiac Arrhythmia Classification with Rejection from ECG Recordings
• Safe Learning in Robotics: From Learning-Based Control to Safe Reinforcement Learning
• MuyGPs: Scalable Gaussian Process Hyperparameter Estimation Using Local Cross-Validation
• Multi-class Gaussian Process Classification with Noisy Inputs
• On Calibration of Modern Neural Networks
• Lazily Adapted Constant Kinky Inference for Nonparametric Regression and\n Model-Reference Adaptive Control
• Dropout as a Bayesian Approximation: Representing Model Uncertainty in Deep Learning
• Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithms
• The MNIST Database of Handwritten Digit Images for Machine Learning Research [Best of the Web]
• Online Least Squares Estimation with Self-Normalized Processes: An Application to Bandit Problems
• An efficient method for finding the minimum of a function of several variables without calculating derivatives
• On Estimating Regression

Discussions

• The preprint of our paper “Computationally lightweight classifiers with frequentist bounds on predictions” is up on arXiv: arxiv.org/abs/2603.22128 This work was accepted to AISTATS 2026. See you in T [bsky, 1 points, 0 comments]

Related

• Enhancing Electrocardiography Data Classification Confidence: A Robust Gaussian Process Approach (MuyGPs)
• Reservoir Computing Models for Patient-Adaptable ECG Monitoring in Wearable Devices
• Benchmarking Uncertainty Quantification on Biosignal Classification Tasks under Dataset Shift
• An Uncertainty Estimation Framework for Risk Assessment in Deep Learning-based Atrial Fibrillation Classification
• Generalization Studies of Neural Network Models for Cardiac Disease Detection Using Limited Channel ECG