# Mathematical Foundations of Poisoning Attacks on Linear Regression over Cumulative Distribution Functions

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 77 references that are in the map.
- First posted on arXiv 28 Feb 2026.

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

- [The Case for Learned Index Structures](https://mlsanity.com/paper/1712.01208/) (2017)
- [ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms](https://mlsanity.com/paper/1807.05614/) (2018)
- [A Model for Learned Bloom Filters, and Optimizing by Sandwiching](https://mlsanity.com/paper/1901.00902/) (2019)
- [ALEX: An Updatable Adaptive Learned Index](https://mlsanity.com/paper/1905.08898/) (2019)
- [RadixSpline: A Single-Pass Learned Index](https://mlsanity.com/paper/2004.14541/) (2020)
- [FITing-Tree: A Data-aware Index Structure](https://mlsanity.com/paper/1801.10207/) (2018)
- [Learning Multi-dimensional Indexes](https://mlsanity.com/paper/1912.01668/) (2019)
- [Benchmarking Learned Indexes](https://mlsanity.com/paper/2006.12804/) (2020)
- [Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads](https://mlsanity.com/paper/2006.13282/) (2020)
- [Adaptive Learned Bloom Filter (Ada-BF): Efficient Utilization of the Classifier](https://mlsanity.com/paper/1910.09131/) (2019)
- [Updatable Learned Index with Precise Positions](https://mlsanity.com/paper/2104.05520/) (2021)
- [Partitioned Learned Bloom Filter](https://mlsanity.com/paper/2006.03176/) (2020)
- [APEX: A High-Performance Learned Index on Persistent Memory](https://mlsanity.com/paper/2105.00683/) (2021)
- [Bounding the Last Mile: Efficient Learned String Indexing](https://mlsanity.com/paper/2111.14905/) (2021)
- [On Distribution Dependent Sub-Logarithmic Query Time of Learned Indexing](https://mlsanity.com/paper/2306.10651/) (2023)
- [Learning to Optimize LSM-trees: Towards A Reinforcement Learning based Key-Value Store for Dynamic Workloads](https://mlsanity.com/paper/2308.07013/) (2023)
- [The Price of Tailoring the Index to Your Data: Poisoning Attacks on Learned Index Structures](https://mlsanity.com/paper/2008.00297/) (2020)
- [PACE: Poisoning Attacks on Learned Cardinality Estimation](https://mlsanity.com/paper/2409.15990/) (2024)
- [A Survey of Learned Indexes for the Multi-dimensional Space](https://mlsanity.com/paper/2403.06456/) (2024)
- [Accelerating String-Key Learned Index Structures via Memoization-based Incremental Training](https://mlsanity.com/paper/2403.11472/) (2024)
- [Theoretical Analysis of Learned Database Operations under Distribution Shift through Distribution Learnability](https://mlsanity.com/paper/2411.06241/) (2024)
- [NFL: Robust Learned Index via Distribution Transformation](https://mlsanity.com/paper/2205.11807/) (2022)
- [Algorithmic Complexity Attacks on Dynamic Learned Indexes](https://mlsanity.com/paper/2403.12433/) (2024)
- [Why Are Learned Indexes So Effective but Sometimes Ineffective?](https://mlsanity.com/paper/2410.00846/) (2024)
- [FlexFlood: Efficiently Updatable Learned Multi-dimensional Index](https://mlsanity.com/paper/2411.09205/) (2024)
- [A Scalable Learned Index Scheme in Storage Systems](https://mlsanity.com/paper/1905.06256/) (2019)
- [Learning-augmented count-min sketches via Bayesian nonparametrics](https://mlsanity.com/paper/2102.04462/) (2021)
- [Learned-Database Systems Security](https://mlsanity.com/paper/2212.10318/) (2022)
- [Learned Indexes with Distribution Smoothing via Virtual Points](https://mlsanity.com/paper/2408.06134/) (2024)
- [A New Paradigm in Tuning Learned Indexes: A Reinforcement Learning Enhanced Approach](https://mlsanity.com/paper/2502.05001/) (2025)

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

- [Poisoning Attacks on the PGM-index](https://mlsanity.com/paper/2609.02328/) (2026)

## Abstract (arXiv)

Learned indexes are a class of index data structures that enable fast search by approximating the cumulative distribution function (CDF) using machine learning models (Kraska et al., SIGMOD'18). However, recent studies have shown that learned indexes are vulnerable to poisoning attacks, where injecting a small number of poison keys into the training data can significantly degrade model accuracy and reduce index performance (Kornaropoulos et al., SIGMOD'22). In this work, we provide a rigorous theoretical analysis of poisoning attacks targeting linear regression models over CDFs, one of the most basic regression models and a core component in many learned indexes. Our main contributions are as follows: (i) We present a theoretical proof characterizing the optimal single-point poisoning attack and show that the existing method yields the optimal attack. (ii) We show that in multi-point attacks, the existing greedy approach is not always optimal, and we rigorously derive the key properties that an optimal attack should satisfy. (iii) We propose a method to compute an upper bound of the multi-point poisoning attack's impact and empirically demonstrate that the loss under the greedy approach is often close to this bound. Our study deepens the theoretical understanding of attack strategies against linear regression models on CDFs and provides a foundation for the theoretical evaluation of attacks and defenses on learned indexes.