acceptodds
Under review as a conference paper at ICLR 2027

Data Poisoning Attack against Batch Online Learners via Duplication and Deletion

Abstract

The recent trend in modern predictive models, such as LLMs, has prompted a change in the data source from curated datasets to a stream of real-time data. This change introduces a new vulnerability that an adversary could exploit to cause substantial damage while evading detection. However, the adversary is constrained in designing attacks based solely on observations available at decision time. Understanding the optimal attack strategy provides critical insights for designing defense mechanisms that secure predictive models and improve their resilience. In this paper, we study a white-box data poisoning attack against an online learner, where the adversary seeks to steer the learner's parameters toward a specific target. The adversary is restricted to deleting and duplicating existing observations within each incoming batch, without modifying their features and labels. We frame the attacker-defender interaction as a constrained Markov Decision Process (MDP) and propose a reinforcement learning (RL) agent that approximately derives the near-optimal attack. We provide theoretical analysis and numerical experiments to show that our algorithm achieves lower cumulative attack cost than a generic model-free RL baseline.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Adversarial Machine Learning, Data Poisoning, Online Learning, Reinforecement Learning, Combinatorial Optimization

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_EuNzOpenReview ↗
Rating
4
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The authors consider a setting where an attacker sees batches of data being fed into a sequential learning algorithm and perturbs the data so as to drive the learned parameters toward the attacker's target. The attacker has full knowledge of the non-adaptive attacker is able to duplicate and remove points. After formalizing the scenario as an MDP, the authors present an efficient attack and analyze it both empirically and theoretically.

Critical strengths
  • The paper is very clearly written and easy to follow (although it would benefit from having a notation table).
  • The threat model is restricted enough to be mathematically friendly to work with while also being realistic enough to be applicable.
  • The theoretical analysis is both elegant and useful.

Overall it's a nice paper that performs a standard-methods attack for an interesting and novel setting. While the method alone is probably not efficient or powerful enough to immediately applicable in real-world settings, the manuscript lays the groundwork for future work (including theoretical and empirical analysis, as well as addressing the engineering challenges of deploying the solution and further settings such as an adaptive defender).

Critical weaknesses
  • There is a bit of a bait-and-switch. The first line of the abstract motivates the topic using LLMs, but then experiments are all on linear regression and logistic regression (on as high as 30-dimensional data).
  • The experiments are lacking. Logistic and linear regression are the simplest of learners, and only extremely simple datasets, none of which are from canonically sequential domains are evaluated.
  • The method seems slow. The authors highlight the computational difficulty of solving the combinatorial optimization problem and describe how they address this challenge in section 3.4. However, given that even MNIST was PCA'd down to d=30, I'm guessing the method is too slow for even moderately sized data.
Questions for authors
  1. Am I right in that it's too slow to run on MNIST in its native dimension?
  2. What's the limitation holding you back from running on e.g., MLPs or other (non-linear) learners?
  3. In the third bullet point of the listed main contributions, you say "up to function-approximation and surrogate errors." What does that mean?
3 comments

We appreciate the reviewer’s thoughtful suggestions. We have adjusted our manuscript and experiments to show that our approach is efficient and powerful enough for higher-dimensional datasets and complex learning models of the victim.

(W1) Misleading abstract opening

We thank the reviewer for pointing this out. We agree that the abstract’s opening can cause a misleading impression that our method is evaluating an enormous-scale learner like an LLM. We have removed the confusing opening and clarified the scope of our study in the revised abstract.

(W3, Q1) Runtime on native-dimension MNIST

Our use of 30-dimensional PCA features is consistent with the experimental setup of Zhang, Zhu, and Lessard (2020) and Margiotta et al. (2023). To validate the runtime in a higher dimension, we ran the experiments on the full-dimensional MNIST and included the result in Section 5 with the full-dimensional experiment. The new result has shown that the FEVI incurs the lowest distance to target and the validation cost, while using the least amount of training time.

(W2, Q2) Extension to MLP

We also realize the value of providing more validation on the MLP-based victim models. The same concern was also raised by the other two reviewers. Therefore, we conducted the following experiments on the MLP victim model. We implemented a small MLP victim with a single 8-node hidden layer and a tanh activation layer for a regression task on a noisy sinusoidal wave. The result shown in the revised manuscript highlights how our proposed approach can handle a more complex learning model that the victim deploys. Compared with the model-free RL baselines, the FEVI achieves the lowest cumulative test cost by a slight margin. It consistently achieves the lowest parameter distance to the target. Our approach also attains the lowest validation cost throughout all the training episodes.

(Q3) Ambiguous wording in the main contribution

Thank you for catching this slip in our draft. When we said “up to”, we meant “derived from”. Our finite-sample bound on the optimality gap is derived from the function-approximation and surrogate errors, which results in O(n−0.5)O(n^{-0.5}) decay rate. We realized the confusion in the wording and, thus, we have updated the third bullet point in the main contribution to the following

...derived from the function-approximation and surrogate errors. Our analysis also reveals how the problem specification affects the upper bound of the surrogate approximation error.

I thank the authors for their response. I maintain my (high) assessment of the work.

AuthorsOpenReview ↗

Thank you!

We appreciate your encouraging evaluation of this exciting work!

Reviewer_YDEyOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies targeted data poisoning against online learners through deletion and duplication of existing samples, without modifying their features or labels. The attacker aims to steer the learner's parameters toward a specified target while preserving batch size and respecting edit and replication limits. The problem is formulated as a finite-horizon Markov decision process. The proposed Fitted Expected-Value Iteration method exploits the known learner update to estimate future costs and selects actions using a linearized surrogate and constrained greedy allocation. The paper provides theoretical error analysis and experiments with online linear and logistic regression victims.

Critical strengths
  1. The paper studies a clearly constrained attack that only deletes and duplicates existing samples while preserving batch size. This formulation helps characterize how manipulating sample frequencies can influence online learning even when individual features and labels remain unchanged.

  2. The method accounts for the effects of current edits on subsequent learning and exploits the known learner update to reduce the input space of the fitted value function. Combining this representation with constrained action selection is a useful technical design. The theoretical analysis and comparisons with myopic and reinforcement learning baselines provide support for its effectiveness in the evaluated settings.

Critical weaknesses
  1. The connection between the parameter-distance objective and practical attack consequences is insufficiently established. Section 3.1 combines squared distance to a specified target parameter with an editing penalty. Although this objective is convenient for analysis, reducing parameter distance does not directly establish degraded predictive performance or the realization of an intended malicious behavior. Reporting primarily cumulative cost also makes it difficult to separate improved target attainment from reduced editing expenditure. This limits the interpretation of the reported gains as evidence of practical attack impact.

  2. The empirical evaluation provides limited evidence beyond the method's idealized data assumptions and small-scale settings. The expected-value formulation relies on independent batches from a fixed distribution, whereas online data can exhibit temporal dependence and distribution shift. The experiments use linear and logistic regression victims; the synthetic setting has batches of 10 samples and an attack horizon of 10 steps. These results support effectiveness within the studied settings, but leave robustness to departures from the data assumptions and scalability to larger problems unclear. The current comparisons also do not fully isolate the benefits of the reduced value representation, batch averaging, and differing data-reuse mechanisms.

Questions for authors
  1. How does reducing distance to the target parameters translate into the intended malicious predictive behavior?

  2. How sensitive is the method to temporal dependence or distribution shift in the data stream?

  3. How does the method scale to larger batches, longer attack horizons, and deeper victim models?

2 comments

We thank the reviewer for raising these points and for the careful consideration of our paper. We address the raised concerns as follows:

(W1, Q1): Connection between distance objective and the intended malicious behavior

We agree that the connection between our parameter-distance objective and the attacker’s intended behavior needs to be established. For linear regression, the predictions vary linearly with the estimated parameters. This directly implies that the convex performance metrics, such as MSE, will change according to the distance between the estimates and the true parameter.

For non-linear models, such as logistic regression and MLP, we cannot readily derive such a connection. Thus, we conducted additional experiments with logistic regression and MLP on the MNIST dataset. We assume the attacker intends a label-flipping behavior on the 1-vs-all MNIST (label 1 for the image of 1 and label 0 for the others). To derive the target parameters θ~\tilde{\theta} that result in the flipped label, we train the corresponding logistic or MLP models on the label-flipped dataset to get an estimate of the target parameters. Then, we perturbed the target in a random direction with a fixed distance and measured the accuracy on the label-flipped test dataset. The results of this experiment are partially shown in the table below. The full plot is included in the Appendix of our revised manuscript.

Logistic: ∥∥θ−θ~∥∥\|\|\theta - \tilde{\theta}\|\|Logistic: accuracyNeural network: ∥∥θ−θ~∥∥\|\|\theta - \tilde{\theta}\|\|Neural network: accuracy
0.000.9929 ± 0.00000.000.9973 ± 0.0000
4.390.9252 ± 0.01342.180.9968 ± 0.0003
8.780.8019 ± 0.02994.350.9930 ± 0.0016
13.170.7261 ± 0.03576.530.9813 ± 0.0074
17.560.6810 ± 0.03768.700.9583 ± 0.0181

This experiment has shown explicitly how the label-flipped accuracy gradually drops as the distance from the target parameters grows. The effect is more pronounced in logistic regression due to a smaller dimension of θ\theta.

We also acknowledge the difficulty in distinguishing each figure in the cumulative cost plot since the figures are overlapping. Therefore, we include the plot showing the decomposition into the perturbation cost and the distance to target in the Appendix.

(Q2) Dependence data stream

Our formulation assumes the independent batches drawn from a fixed distribution. This assumption allows us to construct the Markovian state and formulate the problem as an MDP. We agree that it is important to consider temporal dependencies and distribution shifts in the data stream in many practical applications. However, this paper intends to lay the theoretical foundation for batch manipulation attacks, and hence the coverage of temporal dependence and distribution shift remains future work.

In practice, the data stream can exhibit both effects. Temporal dependence may require augmenting the states to incorporate the process’s evolution, while distribution shift can make the fitted functions inaccurate. A potential extension to this study is to learn the model of the evolving data distribution and update the fitted function accordingly. We clarified the scope of the current assumptions and this limitation in the revision.

(W2, Q3) Scalability of the proposed method

We provide an extensive sensitivity analysis on batch size mm (5 to 50) and horizon TT (5 to 50), and extend it to an MLP victim. The cumulative cost normalized by the null baseline of our approach generally decreases with the batch size in linear and logistic victims, performing similarly to TRPO, but with a faster training time. Hence, our method exhibits better scalability on larger mm than the baseline methods.

The scaling on the horizon TT has revealed a decreasing trend in the cumulative test cost across all approaches as TT increases in the logistic and MLP victims, while we can observe a U-shaped cost on the test set in the linear victim. For the linear and logistic victims, our approach leads to the lowest test cost in almost all horizons and the lowest training time.

Regarding the deeper victim, we implemented a small MLP victim for the regression task. The result shown in the revised manuscript highlights how our proposed approach can handle a more complex victim. That is, the FEVI achieves the lowest cumulative test cost by a slight margin; moreover, it also attains the lowest validation cost throughout all the training episodes. Therefore, our approach can scale well into the setting with larger batch size, longer horizon, and deeper model.

The additional MLP experiment is included in Section 5 of the revised manuscript, and the batch-size and horizon sensitivity analyses are reported in the revised appendix.

Thank you for your comments. We have revised our manuscript to include additional experiments as follows:

  • A toy experiment to show the connection between the distance objective and intended malicious behavior in Appendix E.
  • A clarification of the limitation in our study regarding the temporal dependence or distribution shift between batches in the conclusion.
  • An additional experiment with MLP in Section 5.
  • A sensitivity analysis on the batch size mm and horizon TT is included in Appendix D.1 and D.2.
Reviewer_DQwbOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies a white-box data poisoning attack against online learners in which the adversary is restricted to deleting and duplicating observations within each incoming batch, without modifying features or labels. The attacker-defender interaction is formulated as a constrained finite-horizon Markov Decision Process (MDP) with batch-size preservation and per-sample replication budgets. The authors propose FEVI (Fitted Expected-Value Iteration), which exploits the known one-step learner update and constructs a linearized surrogate objective that decomposes the combinatorial action space into a separable convex resource allocation problem, solvable in O(m2)O(m^2) via greedy allocation rather than O((L+1)m)O((L+1)^m) by brute force. Two main theoretical results are provided: Theorem 1 bounds the per-step surrogate approximation error, and Theorem 2 establishes a finite-sample optimality gap of O(n−1/2)O(n^{-1/2}) up to function-approximation and surrogate errors. Experiments on simulated (online linear and logistic regression) and real datasets (Wine, Airfoil, Breast Cancer, MNIST) show that FEVI achieves lower cumulative attack cost and substantially faster training than model-free RL baselines (TRPO, BDQ) and a myopic greedy attacker.

Critical strengths
  1. Clean problem formulation with principled decomposition. The MDP formulation for delete/duplicate poisoning is natural and well-motivated. The key technical insight — that the linearized surrogate decomposes into a separable convex objective amenable to greedy allocation — reduces an exponential-sized action space to O(m2)O(m^2) computation per step. This is the paper's main contribution and it is executed cleanly with rigorous supporting theory (approximation error bounds and finite-sample optimality gap).

  2. Computational efficiency advantage is convincing. FEVI trains in a fraction of the time required by TRPO and BDQ (often 3-10x faster) while achieving equal or lower cumulative attack cost. This practical advantage is well-demonstrated across both simulated and real datasets, making the method a clear improvement over applying generic model-free RL to this structured problem.

Critical weaknesses
  1. Narrow scope of victim models and threat model. All experiments use simple parametric models — online linear regression and online logistic regression on datasets with at most 30 features (after PCA for MNIST). The white-box assumption (full knowledge of the victim's parameters, update rule, and current batch) is strong. The paper does not discuss or experiment with more complex victims (e.g., neural networks trained with mini-batch SGD), nor does it address how the surrogate quality degrades as model complexity increases. This significantly limits the practical relevance of the contribution, since most deployed online learning systems use more expressive models.

  2. Model-free RL baselines are disadvantaged by design. TRPO and BDQ must learn the transition dynamics from scratch, while FEVI exploits the known update function directly. This comparison, while legitimate, makes it difficult to assess FEVI's contribution beyond the observation that exploiting problem structure helps. A comparison against other model-based approaches or planning algorithms that also exploit the known update rule would better isolate the benefit of the surrogate decomposition specifically. The greedy attacker, which does exploit the update rule, is the most informative baseline, and FEVI's margin over it (especially on the logistic task) is relatively modest.

Questions for authors
  1. How does the surrogate approximation quality degrade when the victim uses a more complex model (e.g., a small neural network)? Assumption 2 (smoothness of the fitted value function) may become much harder to satisfy. Can you provide any empirical evidence or discussion on this?

  2. The batch size is fixed at m=10m = 10 in all experiments. How sensitive is FEVI's advantage over the greedy attacker to larger batch sizes? The greedy allocation becomes a better approximation to the true objective as the per-sample perturbation magnitude decreases relative to batch effects.

  3. The paper restricts the duplication factor to L=2L = 2. Is this a fundamental limitation of the approach, or could FEVI handle larger replication budgets? How does the greedy allocation quality scale with LL?

2 comments

We thank the reviewer for valuable comments and insights. We address the concerns with additional experiments on an MLP victim and sensitivity analyses for batch size BB and replication constraints LL.

1. More complex victims and discussion regarding approximation error (Q1, W1) Thank you for raising this question. We ran an additional experiment with an online multi-layer perceptron (MLP) victim, comparing FEVI, null, greedy, TRPO, and BDQ attackers. We will describe the MLP victim in detail in the revised manuscript. In short, the victim’s MLP approximates a noisy sinusoidal wave and is trained by a stream of online batches through gradient descent. In Section 5 of our revised manuscript, the FEVI shows that it achieves the lowest final cumulative cost by a small margin and ends closest to the target parameters.

The model complexity affects our proposed threat model through Assumption 2, as identified. Whether this smoothness assumption is satisfied depends on the chosen parametric model. That is, this assumption is violated when the gradient of the fitted function is discontinuous. The smoothness constant Λt\Lambda_t depends on the attacker's fitted value function and parameter domain. Increasing victim complexity does not by itself invalidate the assumption or imply a larger Λt\Lambda_t. In the revised manuscript, we will provide the plot of the cumulative cost on the test set and validation cost across training episodes for the MLP as a representative of the non-linear predictive model in addition to the current linear and logistic regression experiments. We can observe that the validation cost of the FEVI is lower than that of all other methods; however, the cumulative cost of the FEVI is marginally better than that of the other methods on the test set.

2. Model-based comparisons and the contribution of the surrogate decomposition (W2) Our formulation considers an attacker who modifies each incoming batch before the victim performs its gradient-based update via SGD. Under our white-box assumptions, the update rule and current parameters directly provide transition information. For a fair comparison, we have already provided a score ϕi,t\phi_{i,t} scaled by the victim’s learning rate and its residual as the features being fed into TRPO and BDQ, as specified in Appendix A.5. Therefore, both model-free baselines are provided with the same information as the FEVI has been given.

The model-free baselines considered in our study provide a comparison to established approaches in the sequential poisoning literature, including DDPG in Zhang et al. (2020) and TD3 in Margiotta et al. (2023). However, we agree that their results alone cannot isolate the benefit of the surrogate decomposition. FEVI’s specific contribution is to turn the combinatorial action optimization into a tractable separable allocation problem. FEVI’s improvement over the greedy attacker is prominent in the linear victim, supporting the benefit of accounting for future rewards. However, the margin is smaller in the original logistic and MLP experiments due to an increase in approximation error.

3. Sensitivity to batch size (mm) (Q2) We provided an additional experiment, varying mm from 5 to 70 for the linear and logistic victims (figures in new appendix). Normalized by the null attack’s cost, test cost decreases slightly with mm for every attacker, and FEVI’s decreases much faster than greedy’s and BDQ’s. TRPO follows FEVI’s pattern, but FEVI needs less than a tenth of its training time at m=70m = 70. We agree that one edit matters less in a larger averaged update, which improves local approximations; FEVI benefits from this too. Smaller individual effects do not remove the value of planning: greedy optimizes only the immediate effect, whereas FEVI accounts for later updates and costs, and larger batches offer more observations for coordinated edits. Hence, a larger m need not close the gap.

4. Sensitivity to the duplication factor (LL) and per-batch budget (BB) (Q3) Thanks for raising the concern regarding the duplication factor. The FEVI can accommodate a duplication factor larger than 2. The replication constraints are jointly represented by LL and BB. We varied LL from 2 to 5 with no budget BB. FEVI matches or outperforms the baselines on the linear victim but deteriorates at larger LL on the nonlinear victims. A likely cause is that concentrated replication permits larger parameter changes, where the first-order approximation is less accurate if the fitted value has curvature. We then varied BB fixing L=2L = 2. FEVI matches or outperforms the baselines on the linear and logistic victims; on the neural network it is comparable for B≤4B \le 4 and degrades beyond. In practice, a large LL is easier to detect, since the batch contains many copies of one observation. An attacker wanting a larger effective LL can instead apply our algorithm repeatedly on the corrupted dataset.

Thank you for your comments. We have revised our manuscript to include additional experiments as follows:

  • An additional experiment with an MLP victim in Section 5.
  • A sensitivity analysis on the batch size mm, edit budget BB, and repetition limit LL is included in Appendix D.1, D.2, and D.4.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.