# Scalable and adaptive prediction bands with kernel sum-of-squares

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 79 references that are in the map.
- First posted on arXiv 27 May 2025.

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

- [Normalizing Flows for Probabilistic Modeling and Inference](https://mlsanity.com/paper/1912.02762/) (2019)
- [An overview of gradient descent optimization algorithms](https://mlsanity.com/paper/1609.04747/) (2016)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Conformalized Quantile Regression](https://mlsanity.com/paper/1905.03222/) (2019)
- [A Rewriting System for Convex Optimization Problems](https://mlsanity.com/paper/1709.04494/) (2017)
- [Adan: Adaptive Nesterov Momentum Algorithm for Faster Optimizing Deep Models](https://mlsanity.com/paper/2208.06677/) (2022)
- [Learning by Transduction](https://mlsanity.com/paper/1301.7375/) (2013)
- [Localized Conformal Prediction: A Generalized Inference Framework for Conformal Prediction](https://mlsanity.com/paper/2106.08460/) (2021)
- [Adaptive, Distribution-Free Prediction Intervals for Deep Networks](https://mlsanity.com/paper/1905.10634/) (2019)
- [Improving Conditional Coverage via Orthogonal Quantile Regression](https://mlsanity.com/paper/2106.00394/) (2021)
- [Conformal prediction with local weights: randomization enables local guarantees](https://mlsanity.com/paper/2310.07850/) (2023)
- [Non-parametric Models for Non-negative Functions](https://mlsanity.com/paper/2007.03926/) (2020)
- [Practical heteroskedastic Gaussian process modeling for large simulation experiments](https://mlsanity.com/paper/1611.05902/) (2016)
- [Boosted Conformal Prediction Intervals](https://mlsanity.com/paper/2406.07449/) (2024)
- [Minimum Volume Conformal Sets for Multivariate Regression](https://mlsanity.com/paper/2503.19068/) (2025)
- [Group kernels for Gaussian process metamodels with categorical inputs](https://mlsanity.com/paper/1802.02368/) (2018)
- [Finding Global Minima via Kernel Approximations](https://mlsanity.com/paper/2012.11978/) (2020)
- [PSD Representations for Effective Probability Models](https://mlsanity.com/paper/2106.16116/) (2021)
- [Operator splitting for a homogeneous embedding of the linear complementarity problem](https://mlsanity.com/paper/2004.02177/) (2020)
- [Optimal Transport-based Conformal Prediction](https://mlsanity.com/paper/2501.18991/) (2025)
- [A Dimension-free Computational Upper-bound for Smooth Optimal Transport Estimation](https://mlsanity.com/paper/2101.05380/) (2021)
- [Guaranteed Coverage Prediction Intervals with Gaussian Process Regression](https://mlsanity.com/paper/2310.15641/) (2023)
- [UTOPIA: Universally Trainable Optimal Prediction Intervals Aggregation](https://mlsanity.com/paper/2306.16549/) (2023)
- [Conformal Approach To Gaussian Process Surrogate Evaluation With Coverage Guarantees](https://mlsanity.com/paper/2401.07733/) (2024)
- [Learning PSD-valued functions using kernel sums-of-squares](https://mlsanity.com/paper/2111.11306/) (2021)
- [Universal Prediction Band via Semi-Definite Programming](https://mlsanity.com/paper/2103.17203/) (2021)
- [E-LMC: Extended Linear Model of Coregionalization for Spatial Field Prediction](https://mlsanity.com/paper/2203.00525/) (2022)
- [Approximation of optimization problems with constraints through kernel Sum-Of-Squares](https://mlsanity.com/paper/2301.06339/) (2023)
- [Elastic Bayesian Model Calibration](https://mlsanity.com/paper/2305.08834/) (2023)
- [Easy Conditioning far beyond Gaussian](https://mlsanity.com/paper/2409.16003/) (2024)

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

- [Non-asymptotic confidence regions on RKHS. The Paley-Wiener and standard Sobolev space cases](https://mlsanity.com/paper/2507.06657/) (2025)

## Abstract (arXiv)

Conformal Prediction (CP) is a popular framework for constructing prediction bands with valid coverage in finite samples, while being free of any distributional assumption. A well-known limitation of conformal prediction is the lack of adaptivity, although several works introduced practically efficient alternate procedures. In this work, we build upon recent ideas that rely on recasting the CP problem as a statistical learning problem, directly targeting coverage and adaptivity. This statistical learning problem is based on reproducible kernel Hilbert spaces (RKHS) and kernel sum-of-squares (SoS) methods. First, we extend previous results with a general representer theorem and exhibit the dual formulation of the learning problem. Crucially, such dual formulation can be solved efficiently by accelerated gradient methods with several hundreds or thousands of samples, unlike previous strategies based on off-the-shelf semidefinite programming algorithms. Second, we introduce a new hyperparameter tuning strategy tailored specifically to target adaptivity through bounds on test-conditional coverage. This strategy, based on the Hilbert-Schmidt Independence Criterion (HSIC), is introduced here to tune kernel lengthscales in our framework, but has broader applicability since it could be used in any CP algorithm where the score function is learned. Finally, extensive experiments are conducted to show how our method compares to related work. All figures can be reproduced with the accompanying code.