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

Atsuki Sato; Martin Aumüller; Yusuke Matsui

cs.LGFeb 28, 2026

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

Authors: Atsuki Sato, Martin Aumüller, Yusuke Matsui

Organizations: Graduate School of Information Science and Technology, The University of Tokyo, Tokyo, Japan · Algorithms Group, IT University of Copenhagen, Copenhagen, Denmark

Abstract

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.

Figures & tables

	Original Setting ( Definition 2 )		Relaxed Setting ( Definition 2 )
Algorithm	Time Complexity	Empirical Performance (Ratio)	Time Complexity	Empirical Performance (Ratio)
Greedy ( Kornaropoulos et al., 2022 )	$\mathcal{O}(n\lambda)$	$\geq\!0.933$	-	-
Exact Seg+E (Ours)	$\mathcal{O}(n\lambda^{3})$	$1$	$\mathcal{O}(n\lambda)$	$1$
Heuristic Seg+E (Ours)	$\mathcal{O}(n\lambda)$	$\geq\!0.998$	-	-
Optimal (Ours)	$\mathcal{O}\!\left((n+\lambda)\binom{2n-2+\lambda}{\lambda}\right)$	1	$\mathcal{O}\!\left((n+\lambda)\binom{n+\lambda-1}{\lambda}\right)$	1
Upper Bound (Ours)	$\mathcal{O}(T(n+\lambda))$ or $\mathcal{O}((n+\lambda)\log(n+\lambda))$	$\leq\!1.092$	$\mathcal{O}(T(n+\lambda))$ or $\mathcal{O}((n+\lambda)\log(n+\lambda))$	$\leq\!1.087$

Table 1. Overview over time complexity and empirical performance of poisoning attacks and upper-bounding methods under the original setting ( Kornaropoulos et al., 2022 ) (duplicate keys disallowed; Definition 2 ) and the relaxed setting (duplicate keys allowed; Definition 2 ). Here,

n

is the number of legitimate keys,

\lambda

is the poisoning budget, and

T

is the number of iterations in our upper-bounding methods. Empirical Performance (Ratio) is the achieved MSE (attacks) or the bound (upper bounds) normalized by the optimal-attack MSE over

3{,}000

cases in Section 6.6 (values closer to

1

indicate a better attack or a tighter upper bound).

Panel of Figure 1 — Figure 1. Single-point poisoning attack on $\mathcal{K}=\{2,11,13,19,32,36,39\}$ . By inserting a poison point, the rank of every key greater than the poison increases by one. The linear regression model is fitted on the poisoned key set, leading to a change in MSE.

Figure 2. Proof of Theorem 1 . Lemma 2 implies that either $E(\mathcal{K}\cup\{p^{\ast}-1\})$ or $E(\mathcal{K}\cup\{p^{\ast}+1\})$ is greater than $E(\mathcal{K}\cup\{p^{\ast}\})$ .

Panel of Figure 3 — Figure 3. Multi-point poisoning attack. The greedy two-point attack ( Kornaropoulos et al., 2022 ) injects the poison point $12$ first ( Figure 3(a) ), followed by the injection of the poison point $10$ ( Figure 3(b) ). In contrast, the optimal attack is $\{37,38\}$ , resulting in a higher MSE ( Figure 3(c) ).

Figure 4. Proof of Theorem 1 . Lemma 1 implies that $E(\mathcal{K}\cup\mathcal{P}_{-})$ or $E(\mathcal{K}\cup\mathcal{P}_{+})$ is greater than $E(\mathcal{K}\cup\mathcal{P}^{\ast})$ .

Figure 5. Examples of the Segment + Endpoint (Seg+E) attack in original and relaxed settings.

Figure 6.

\mathrm{MSE}_{\mathrm{UB}}

(our upper bound),

\mathrm{MSE}_{\mathrm{G}}

(greedy attack), and

\mathrm{MSE}_{\mathrm{L}}

(legitimate) for seed = 0. We set

n=1{,}000

and

R=100{,}000

. We observe that

\mathrm{MSE}_{\mathrm{UB}}\geq\mathrm{MSE}_{\mathrm{G}}

in all cases and the gap is small, which indicates that our upper bound is tight and greedy attack is close to the optimal attack.

Figure 7. Boxplots of

\mathrm{MSE}_{\mathrm{G}}/\mathrm{MSE}_{\mathrm{UB}}

over 100 seeds for each dataset and poisoning percentage. We set

n=1{,}000

and

R=100{,}000

. The ratio never exceeds 1 and is always greater than

0.8

. In particular, for Exponential, Amzn, Face, and Osmc, the median ratio is

\geq 0.99

, which indicates that our upper bound is tight and greedy attack is close to the optimal attack.

Figure 8. Boxplots of

\mathrm{MSE}_{\mathrm{G}}/\mathrm{MSE}_{\mathrm{Seg+E}}

over 100 seeds for each dataset and poisoning percentage. We set

n=1{,}000

and

R=100{,}000

. The ratio never exceeds 1, that is, the Seg+E attack is never worse than the greedy attack.

Figure 9. Boxplots of

\mathrm{MSE}_{\mathrm{Seg+E(H)}}/\mathrm{MSE}_{\mathrm{Seg+E}}-1

over 100 seeds for each dataset and poisoning percentage (for better visibility, we plot the value obtained by subtracting 1 from the ratio). We set

n=1{,}000

and

R=100{,}000

. The ratio consistently remains very close to 1, indicating that our heuristic algorithm yields solutions nearly identical to those of the exact Seg+E algorithm.

Figure 10. Running time vs poisoning percentage. We set

n=1{,}000

and

R=100{,}000

. The running time of the greedy poisoning method grows linearly with the poisoning percentage (consistent with

\mathcal{O}((n+\lambda)\lambda)

time complexity), whereas our upper-bound methods (Golden, Binary, Strict) are nearly flat (consistent with

\mathcal{O}(n+\lambda)

\mathcal{O}((n+\lambda)\log(n+\lambda))

time complexity).

Figure 11. Running time vs

n

. We set the poisoning percentage to 10% and

R=100{,}000

. The running time of the greedy poisoning method grows quadratically with

n

(consistent with

\mathcal{O}((n+\lambda)\lambda)

time complexity), whereas our upper-bound methods (Golden, Binary, Strict) grow linearly with

n

(consistent with

\mathcal{O}(n+\lambda)

\mathcal{O}((n+\lambda)\log(n+\lambda))

time complexity).

Figure 12.

\mathrm{MSE}_{\mathrm{G}}/\mathrm{MSE}_{\mathrm{UB}}

n

. We set the poisoning percentage to 10% and

R=100{,}000

. As

n

increases,

\mathrm{MSE}_{\mathrm{G}}/\mathrm{MSE}_{\mathrm{UB}}

shows a slight tendency to decrease.

Figure 13.

\mathrm{MSE}_{\mathrm{G}}/\mathrm{MSE}_{\mathrm{UB}}

R

for synthetic data. We set the poisoning percentage to 10% and

n=1{,}000

for all datasets. When

R

is quite small, the ratio tends to decrease.

Figure 14. Boxplots of the ratios

\rho_{\mathrm{G}}

\rho_{\mathrm{R}}

, and

\rho_{\mathrm{UB}}

, defined in Equation 15 , over 100 seeds for each dataset and poisoning percentage. We set

n=50

and

R=1{,}000

. All ratios remain close to

1

(minimum

0.92

), with

\mathrm{MSE}_{\mathrm{OPT}}/\mathrm{MSE}_{\mathrm{ROPT}}

particularly tight.

Figure 15. The ratios (

\rho_{\mathrm{G}}

\rho_{\mathrm{R}}

, and

\rho_{\mathrm{UB}}

) vs

R

for synthetic data. We set the poisoning percentage to 10% and

n=50

\rho_{\mathrm{UB}}

and

\rho_{\mathrm{G}}

remain stable as

R

varies, whereas

\rho_{\mathrm{R}}

stays close to

1

for large

R

but drops when

R

is small.

Figure 16. A counter example where the exact Seg+E solution is not globally optimal. The legitimate key set is

\mathcal{K}=\{0,1,\dots,16,48,49,\dots,64\}\setminus\{1,8,56,63\}

. The optimal solution is

\mathcal{P}=\{8,56\}

, but the exact Seg+E solution is

\mathcal{P}=\{1,8\}

Figure 17. Lookup time. The lookup time includes both regression inference and exponential search. We measure it 10 times for each key and report the average. We set

n=1{,}000

and

R=100{,}000

. Poisoning increases the lookup time by up to 1.6 times.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 18. Proof of Theorem 3 . Lemma 1 implies that $E(\mathcal{K}\cup\mathcal{P}_{-})$ or $E(\mathcal{K}\cup\mathcal{P}_{+})$ is greater than $E(\mathcal{K}\cup\mathcal{P}^{\ast})$ .

Figure 19. Empirical observations, conjectures, and counterexamples. All examples (especially those in the second and third columns) illustrate Observation 3 , showing that poisons tend to appear either near the endpoints or around the intersection between the regression line and the sequence of points formed by the legitimate keys. Columns 1–4 correspond to Seg+E configurations that satisfy Observation 4 , whereas columns 5–7 show artificially constructed corner cases that violate Observation 4 . In all examples, the optimal poisons in the relaxed setting are Seg+E, supporting Conjecture 1 .

Data Poisoning Attacks

Data poisoning attacks manipulate training or retrieval data to corrupt model behavior, implant backdoors, or undermine reliability.

See all 125 papers

Theory of Continual Learning Against Data Poisoning Attacks
Jun 29, 2026Yiting Hu, Lingjie DuanRegularization-Based Continual Learning Continual Learning
Singapore University of Technology and Design, Singapore · The Hong Kong University of Science and Technology (Guangzhou), Guangzhou, China.
Active Regression for Single-Index Models with Unknown Link Functions
Aug 2, 2026Chansophea Wathanak In, Yi Li, Wai Ming Tai +1Single-Index Models Active Learning
School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore · Independent Researcher · John Hopcroft Center for Computer Science, Shanghai Jiao Tong University, China
Are Targeted Data Poisoning Attacks as Effective as We Think?
Sep 8, 2025William Xu, Chenyu Zhang, Yihan Wang +5Data Poisoning Attacks
Waabi AI · University of Waterloo · Carnegie Mellon University +3

Jun 29, 2026J/K move · Enter open · S save

Theory of Continual Learning Against Data Poisoning Attacks

Yiting Hu, Lingjie Duan

Singapore University of Technology and Design, Singapore · The Hong Kong University of Science and Technology (Guangzhou), Guangzhou, China.

Regularization-Based Continual Learning Continual Learning Adversarial Robustness Online Continual Learning Data Poisoning Attacks

Open paper AskPDF arXiv

Continual learning (CL), where a model is trained on a sequence of data tasks, is increasingly being adopted across key fields such as large language models and image recognition, yet it remains highly vulnerable to data poisoning that triggers learning divergence or severe excess risk. Despite these threats, a principled theoretical foundation in CL for understanding attack and defense remains lacking. In this paper, we develop a theoretical framework to analyze strategic attacks and defenses in regularization-based CL, a cornerstone of recent CL theory. By framing the adversary-defender interaction as an online zero-sum game, we first establish a fundamental performance limit: no defense succeeds when an adversary poisons a linear proportion of tasks by injecting unbounded noise or pattern shifts in regularization-based CL. We then analyze two possibly defensible scenarios: infrequent attacks and bounded noise per attack. For the former regime, we propose a task-to-task verification mechanism to detect data poisoning and reduce cumulative bias for learning convergence. For the latter regime, we derive a robust defense that minimizes the model's sensitivity to poisoned features, provably accelerating the convergence rate. Extensive experiments on realistic tasks further validate our theoretical results.

Abstract

Data Poisoning Attacks

Explore similar work

Theory of Continual Learning Against Data Poisoning Attacks

Active Regression for Single-Index Models with Unknown Link Functions

Are Targeted Data Poisoning Attacks as Effective as We Think?